1 /* -*- mode: c; c-basic-offset: 8; -*- 2 * vim: noexpandtab sw=8 ts=8 sts=0: 3 * 4 * alloc.c 5 * 6 * Extent allocs and frees 7 * 8 * Copyright (C) 2002, 2004 Oracle. All rights reserved. 9 * 10 * This program is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU General Public 12 * License as published by the Free Software Foundation; either 13 * version 2 of the License, or (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 * General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public 21 * License along with this program; if not, write to the 22 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 23 * Boston, MA 021110-1307, USA. 24 */ 25 26 #include <linux/fs.h> 27 #include <linux/types.h> 28 #include <linux/slab.h> 29 #include <linux/highmem.h> 30 #include <linux/swap.h> 31 32 #define MLOG_MASK_PREFIX ML_DISK_ALLOC 33 #include <cluster/masklog.h> 34 35 #include "ocfs2.h" 36 37 #include "alloc.h" 38 #include "aops.h" 39 #include "dlmglue.h" 40 #include "extent_map.h" 41 #include "inode.h" 42 #include "journal.h" 43 #include "localalloc.h" 44 #include "suballoc.h" 45 #include "sysfile.h" 46 #include "file.h" 47 #include "super.h" 48 #include "uptodate.h" 49 50 #include "buffer_head_io.h" 51 52 static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc); 53 54 /* 55 * Structures which describe a path through a btree, and functions to 56 * manipulate them. 57 * 58 * The idea here is to be as generic as possible with the tree 59 * manipulation code. 60 */ 61 struct ocfs2_path_item { 62 struct buffer_head *bh; 63 struct ocfs2_extent_list *el; 64 }; 65 66 #define OCFS2_MAX_PATH_DEPTH 5 67 68 struct ocfs2_path { 69 int p_tree_depth; 70 struct ocfs2_path_item p_node[OCFS2_MAX_PATH_DEPTH]; 71 }; 72 73 #define path_root_bh(_path) ((_path)->p_node[0].bh) 74 #define path_root_el(_path) ((_path)->p_node[0].el) 75 #define path_leaf_bh(_path) ((_path)->p_node[(_path)->p_tree_depth].bh) 76 #define path_leaf_el(_path) ((_path)->p_node[(_path)->p_tree_depth].el) 77 #define path_num_items(_path) ((_path)->p_tree_depth + 1) 78 79 /* 80 * Reset the actual path elements so that we can re-use the structure 81 * to build another path. Generally, this involves freeing the buffer 82 * heads. 83 */ 84 static void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root) 85 { 86 int i, start = 0, depth = 0; 87 struct ocfs2_path_item *node; 88 89 if (keep_root) 90 start = 1; 91 92 for(i = start; i < path_num_items(path); i++) { 93 node = &path->p_node[i]; 94 95 brelse(node->bh); 96 node->bh = NULL; 97 node->el = NULL; 98 } 99 100 /* 101 * Tree depth may change during truncate, or insert. If we're 102 * keeping the root extent list, then make sure that our path 103 * structure reflects the proper depth. 104 */ 105 if (keep_root) 106 depth = le16_to_cpu(path_root_el(path)->l_tree_depth); 107 108 path->p_tree_depth = depth; 109 } 110 111 static void ocfs2_free_path(struct ocfs2_path *path) 112 { 113 if (path) { 114 ocfs2_reinit_path(path, 0); 115 kfree(path); 116 } 117 } 118 119 /* 120 * Make the *dest path the same as src and re-initialize src path to 121 * have a root only. 122 */ 123 static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src) 124 { 125 int i; 126 127 BUG_ON(path_root_bh(dest) != path_root_bh(src)); 128 129 for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) { 130 brelse(dest->p_node[i].bh); 131 132 dest->p_node[i].bh = src->p_node[i].bh; 133 dest->p_node[i].el = src->p_node[i].el; 134 135 src->p_node[i].bh = NULL; 136 src->p_node[i].el = NULL; 137 } 138 } 139 140 /* 141 * Insert an extent block at given index. 142 * 143 * This will not take an additional reference on eb_bh. 144 */ 145 static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index, 146 struct buffer_head *eb_bh) 147 { 148 struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)eb_bh->b_data; 149 150 /* 151 * Right now, no root bh is an extent block, so this helps 152 * catch code errors with dinode trees. The assertion can be 153 * safely removed if we ever need to insert extent block 154 * structures at the root. 155 */ 156 BUG_ON(index == 0); 157 158 path->p_node[index].bh = eb_bh; 159 path->p_node[index].el = &eb->h_list; 160 } 161 162 static struct ocfs2_path *ocfs2_new_path(struct buffer_head *root_bh, 163 struct ocfs2_extent_list *root_el) 164 { 165 struct ocfs2_path *path; 166 167 BUG_ON(le16_to_cpu(root_el->l_tree_depth) >= OCFS2_MAX_PATH_DEPTH); 168 169 path = kzalloc(sizeof(*path), GFP_NOFS); 170 if (path) { 171 path->p_tree_depth = le16_to_cpu(root_el->l_tree_depth); 172 get_bh(root_bh); 173 path_root_bh(path) = root_bh; 174 path_root_el(path) = root_el; 175 } 176 177 return path; 178 } 179 180 /* 181 * Allocate and initialize a new path based on a disk inode tree. 182 */ 183 static struct ocfs2_path *ocfs2_new_inode_path(struct buffer_head *di_bh) 184 { 185 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; 186 struct ocfs2_extent_list *el = &di->id2.i_list; 187 188 return ocfs2_new_path(di_bh, el); 189 } 190 191 /* 192 * Convenience function to journal all components in a path. 193 */ 194 static int ocfs2_journal_access_path(struct inode *inode, handle_t *handle, 195 struct ocfs2_path *path) 196 { 197 int i, ret = 0; 198 199 if (!path) 200 goto out; 201 202 for(i = 0; i < path_num_items(path); i++) { 203 ret = ocfs2_journal_access(handle, inode, path->p_node[i].bh, 204 OCFS2_JOURNAL_ACCESS_WRITE); 205 if (ret < 0) { 206 mlog_errno(ret); 207 goto out; 208 } 209 } 210 211 out: 212 return ret; 213 } 214 215 enum ocfs2_contig_type { 216 CONTIG_NONE = 0, 217 CONTIG_LEFT, 218 CONTIG_RIGHT 219 }; 220 221 222 /* 223 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and 224 * ocfs2_extent_contig only work properly against leaf nodes! 225 */ 226 static int ocfs2_block_extent_contig(struct super_block *sb, 227 struct ocfs2_extent_rec *ext, 228 u64 blkno) 229 { 230 u64 blk_end = le64_to_cpu(ext->e_blkno); 231 232 blk_end += ocfs2_clusters_to_blocks(sb, 233 le16_to_cpu(ext->e_leaf_clusters)); 234 235 return blkno == blk_end; 236 } 237 238 static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left, 239 struct ocfs2_extent_rec *right) 240 { 241 u32 left_range; 242 243 left_range = le32_to_cpu(left->e_cpos) + 244 le16_to_cpu(left->e_leaf_clusters); 245 246 return (left_range == le32_to_cpu(right->e_cpos)); 247 } 248 249 static enum ocfs2_contig_type 250 ocfs2_extent_contig(struct inode *inode, 251 struct ocfs2_extent_rec *ext, 252 struct ocfs2_extent_rec *insert_rec) 253 { 254 u64 blkno = le64_to_cpu(insert_rec->e_blkno); 255 256 if (ocfs2_extents_adjacent(ext, insert_rec) && 257 ocfs2_block_extent_contig(inode->i_sb, ext, blkno)) 258 return CONTIG_RIGHT; 259 260 blkno = le64_to_cpu(ext->e_blkno); 261 if (ocfs2_extents_adjacent(insert_rec, ext) && 262 ocfs2_block_extent_contig(inode->i_sb, insert_rec, blkno)) 263 return CONTIG_LEFT; 264 265 return CONTIG_NONE; 266 } 267 268 /* 269 * NOTE: We can have pretty much any combination of contiguousness and 270 * appending. 271 * 272 * The usefulness of APPEND_TAIL is more in that it lets us know that 273 * we'll have to update the path to that leaf. 274 */ 275 enum ocfs2_append_type { 276 APPEND_NONE = 0, 277 APPEND_TAIL, 278 }; 279 280 struct ocfs2_insert_type { 281 enum ocfs2_append_type ins_appending; 282 enum ocfs2_contig_type ins_contig; 283 int ins_contig_index; 284 int ins_free_records; 285 int ins_tree_depth; 286 }; 287 288 /* 289 * How many free extents have we got before we need more meta data? 290 */ 291 int ocfs2_num_free_extents(struct ocfs2_super *osb, 292 struct inode *inode, 293 struct ocfs2_dinode *fe) 294 { 295 int retval; 296 struct ocfs2_extent_list *el; 297 struct ocfs2_extent_block *eb; 298 struct buffer_head *eb_bh = NULL; 299 300 mlog_entry_void(); 301 302 if (!OCFS2_IS_VALID_DINODE(fe)) { 303 OCFS2_RO_ON_INVALID_DINODE(inode->i_sb, fe); 304 retval = -EIO; 305 goto bail; 306 } 307 308 if (fe->i_last_eb_blk) { 309 retval = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk), 310 &eb_bh, OCFS2_BH_CACHED, inode); 311 if (retval < 0) { 312 mlog_errno(retval); 313 goto bail; 314 } 315 eb = (struct ocfs2_extent_block *) eb_bh->b_data; 316 el = &eb->h_list; 317 } else 318 el = &fe->id2.i_list; 319 320 BUG_ON(el->l_tree_depth != 0); 321 322 retval = le16_to_cpu(el->l_count) - le16_to_cpu(el->l_next_free_rec); 323 bail: 324 if (eb_bh) 325 brelse(eb_bh); 326 327 mlog_exit(retval); 328 return retval; 329 } 330 331 /* expects array to already be allocated 332 * 333 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and 334 * l_count for you 335 */ 336 static int ocfs2_create_new_meta_bhs(struct ocfs2_super *osb, 337 handle_t *handle, 338 struct inode *inode, 339 int wanted, 340 struct ocfs2_alloc_context *meta_ac, 341 struct buffer_head *bhs[]) 342 { 343 int count, status, i; 344 u16 suballoc_bit_start; 345 u32 num_got; 346 u64 first_blkno; 347 struct ocfs2_extent_block *eb; 348 349 mlog_entry_void(); 350 351 count = 0; 352 while (count < wanted) { 353 status = ocfs2_claim_metadata(osb, 354 handle, 355 meta_ac, 356 wanted - count, 357 &suballoc_bit_start, 358 &num_got, 359 &first_blkno); 360 if (status < 0) { 361 mlog_errno(status); 362 goto bail; 363 } 364 365 for(i = count; i < (num_got + count); i++) { 366 bhs[i] = sb_getblk(osb->sb, first_blkno); 367 if (bhs[i] == NULL) { 368 status = -EIO; 369 mlog_errno(status); 370 goto bail; 371 } 372 ocfs2_set_new_buffer_uptodate(inode, bhs[i]); 373 374 status = ocfs2_journal_access(handle, inode, bhs[i], 375 OCFS2_JOURNAL_ACCESS_CREATE); 376 if (status < 0) { 377 mlog_errno(status); 378 goto bail; 379 } 380 381 memset(bhs[i]->b_data, 0, osb->sb->s_blocksize); 382 eb = (struct ocfs2_extent_block *) bhs[i]->b_data; 383 /* Ok, setup the minimal stuff here. */ 384 strcpy(eb->h_signature, OCFS2_EXTENT_BLOCK_SIGNATURE); 385 eb->h_blkno = cpu_to_le64(first_blkno); 386 eb->h_fs_generation = cpu_to_le32(osb->fs_generation); 387 388 #ifndef OCFS2_USE_ALL_METADATA_SUBALLOCATORS 389 /* we always use slot zero's suballocator */ 390 eb->h_suballoc_slot = 0; 391 #else 392 eb->h_suballoc_slot = cpu_to_le16(osb->slot_num); 393 #endif 394 eb->h_suballoc_bit = cpu_to_le16(suballoc_bit_start); 395 eb->h_list.l_count = 396 cpu_to_le16(ocfs2_extent_recs_per_eb(osb->sb)); 397 398 suballoc_bit_start++; 399 first_blkno++; 400 401 /* We'll also be dirtied by the caller, so 402 * this isn't absolutely necessary. */ 403 status = ocfs2_journal_dirty(handle, bhs[i]); 404 if (status < 0) { 405 mlog_errno(status); 406 goto bail; 407 } 408 } 409 410 count += num_got; 411 } 412 413 status = 0; 414 bail: 415 if (status < 0) { 416 for(i = 0; i < wanted; i++) { 417 if (bhs[i]) 418 brelse(bhs[i]); 419 bhs[i] = NULL; 420 } 421 } 422 mlog_exit(status); 423 return status; 424 } 425 426 /* 427 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth(). 428 * 429 * Returns the sum of the rightmost extent rec logical offset and 430 * cluster count. 431 * 432 * ocfs2_add_branch() uses this to determine what logical cluster 433 * value should be populated into the leftmost new branch records. 434 * 435 * ocfs2_shift_tree_depth() uses this to determine the # clusters 436 * value for the new topmost tree record. 437 */ 438 static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el) 439 { 440 int i; 441 442 i = le16_to_cpu(el->l_next_free_rec) - 1; 443 444 return le32_to_cpu(el->l_recs[i].e_cpos) + 445 ocfs2_rec_clusters(el, &el->l_recs[i]); 446 } 447 448 /* 449 * Add an entire tree branch to our inode. eb_bh is the extent block 450 * to start at, if we don't want to start the branch at the dinode 451 * structure. 452 * 453 * last_eb_bh is required as we have to update it's next_leaf pointer 454 * for the new last extent block. 455 * 456 * the new branch will be 'empty' in the sense that every block will 457 * contain a single record with cluster count == 0. 458 */ 459 static int ocfs2_add_branch(struct ocfs2_super *osb, 460 handle_t *handle, 461 struct inode *inode, 462 struct buffer_head *fe_bh, 463 struct buffer_head *eb_bh, 464 struct buffer_head *last_eb_bh, 465 struct ocfs2_alloc_context *meta_ac) 466 { 467 int status, new_blocks, i; 468 u64 next_blkno, new_last_eb_blk; 469 struct buffer_head *bh; 470 struct buffer_head **new_eb_bhs = NULL; 471 struct ocfs2_dinode *fe; 472 struct ocfs2_extent_block *eb; 473 struct ocfs2_extent_list *eb_el; 474 struct ocfs2_extent_list *el; 475 u32 new_cpos; 476 477 mlog_entry_void(); 478 479 BUG_ON(!last_eb_bh); 480 481 fe = (struct ocfs2_dinode *) fe_bh->b_data; 482 483 if (eb_bh) { 484 eb = (struct ocfs2_extent_block *) eb_bh->b_data; 485 el = &eb->h_list; 486 } else 487 el = &fe->id2.i_list; 488 489 /* we never add a branch to a leaf. */ 490 BUG_ON(!el->l_tree_depth); 491 492 new_blocks = le16_to_cpu(el->l_tree_depth); 493 494 /* allocate the number of new eb blocks we need */ 495 new_eb_bhs = kcalloc(new_blocks, sizeof(struct buffer_head *), 496 GFP_KERNEL); 497 if (!new_eb_bhs) { 498 status = -ENOMEM; 499 mlog_errno(status); 500 goto bail; 501 } 502 503 status = ocfs2_create_new_meta_bhs(osb, handle, inode, new_blocks, 504 meta_ac, new_eb_bhs); 505 if (status < 0) { 506 mlog_errno(status); 507 goto bail; 508 } 509 510 eb = (struct ocfs2_extent_block *)last_eb_bh->b_data; 511 new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list); 512 513 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be 514 * linked with the rest of the tree. 515 * conversly, new_eb_bhs[0] is the new bottommost leaf. 516 * 517 * when we leave the loop, new_last_eb_blk will point to the 518 * newest leaf, and next_blkno will point to the topmost extent 519 * block. */ 520 next_blkno = new_last_eb_blk = 0; 521 for(i = 0; i < new_blocks; i++) { 522 bh = new_eb_bhs[i]; 523 eb = (struct ocfs2_extent_block *) bh->b_data; 524 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 525 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); 526 status = -EIO; 527 goto bail; 528 } 529 eb_el = &eb->h_list; 530 531 status = ocfs2_journal_access(handle, inode, bh, 532 OCFS2_JOURNAL_ACCESS_CREATE); 533 if (status < 0) { 534 mlog_errno(status); 535 goto bail; 536 } 537 538 eb->h_next_leaf_blk = 0; 539 eb_el->l_tree_depth = cpu_to_le16(i); 540 eb_el->l_next_free_rec = cpu_to_le16(1); 541 /* 542 * This actually counts as an empty extent as 543 * c_clusters == 0 544 */ 545 eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos); 546 eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno); 547 /* 548 * eb_el isn't always an interior node, but even leaf 549 * nodes want a zero'd flags and reserved field so 550 * this gets the whole 32 bits regardless of use. 551 */ 552 eb_el->l_recs[0].e_int_clusters = cpu_to_le32(0); 553 if (!eb_el->l_tree_depth) 554 new_last_eb_blk = le64_to_cpu(eb->h_blkno); 555 556 status = ocfs2_journal_dirty(handle, bh); 557 if (status < 0) { 558 mlog_errno(status); 559 goto bail; 560 } 561 562 next_blkno = le64_to_cpu(eb->h_blkno); 563 } 564 565 /* This is a bit hairy. We want to update up to three blocks 566 * here without leaving any of them in an inconsistent state 567 * in case of error. We don't have to worry about 568 * journal_dirty erroring as it won't unless we've aborted the 569 * handle (in which case we would never be here) so reserving 570 * the write with journal_access is all we need to do. */ 571 status = ocfs2_journal_access(handle, inode, last_eb_bh, 572 OCFS2_JOURNAL_ACCESS_WRITE); 573 if (status < 0) { 574 mlog_errno(status); 575 goto bail; 576 } 577 status = ocfs2_journal_access(handle, inode, fe_bh, 578 OCFS2_JOURNAL_ACCESS_WRITE); 579 if (status < 0) { 580 mlog_errno(status); 581 goto bail; 582 } 583 if (eb_bh) { 584 status = ocfs2_journal_access(handle, inode, eb_bh, 585 OCFS2_JOURNAL_ACCESS_WRITE); 586 if (status < 0) { 587 mlog_errno(status); 588 goto bail; 589 } 590 } 591 592 /* Link the new branch into the rest of the tree (el will 593 * either be on the fe, or the extent block passed in. */ 594 i = le16_to_cpu(el->l_next_free_rec); 595 el->l_recs[i].e_blkno = cpu_to_le64(next_blkno); 596 el->l_recs[i].e_cpos = cpu_to_le32(new_cpos); 597 el->l_recs[i].e_int_clusters = 0; 598 le16_add_cpu(&el->l_next_free_rec, 1); 599 600 /* fe needs a new last extent block pointer, as does the 601 * next_leaf on the previously last-extent-block. */ 602 fe->i_last_eb_blk = cpu_to_le64(new_last_eb_blk); 603 604 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; 605 eb->h_next_leaf_blk = cpu_to_le64(new_last_eb_blk); 606 607 status = ocfs2_journal_dirty(handle, last_eb_bh); 608 if (status < 0) 609 mlog_errno(status); 610 status = ocfs2_journal_dirty(handle, fe_bh); 611 if (status < 0) 612 mlog_errno(status); 613 if (eb_bh) { 614 status = ocfs2_journal_dirty(handle, eb_bh); 615 if (status < 0) 616 mlog_errno(status); 617 } 618 619 status = 0; 620 bail: 621 if (new_eb_bhs) { 622 for (i = 0; i < new_blocks; i++) 623 if (new_eb_bhs[i]) 624 brelse(new_eb_bhs[i]); 625 kfree(new_eb_bhs); 626 } 627 628 mlog_exit(status); 629 return status; 630 } 631 632 /* 633 * adds another level to the allocation tree. 634 * returns back the new extent block so you can add a branch to it 635 * after this call. 636 */ 637 static int ocfs2_shift_tree_depth(struct ocfs2_super *osb, 638 handle_t *handle, 639 struct inode *inode, 640 struct buffer_head *fe_bh, 641 struct ocfs2_alloc_context *meta_ac, 642 struct buffer_head **ret_new_eb_bh) 643 { 644 int status, i; 645 u32 new_clusters; 646 struct buffer_head *new_eb_bh = NULL; 647 struct ocfs2_dinode *fe; 648 struct ocfs2_extent_block *eb; 649 struct ocfs2_extent_list *fe_el; 650 struct ocfs2_extent_list *eb_el; 651 652 mlog_entry_void(); 653 654 status = ocfs2_create_new_meta_bhs(osb, handle, inode, 1, meta_ac, 655 &new_eb_bh); 656 if (status < 0) { 657 mlog_errno(status); 658 goto bail; 659 } 660 661 eb = (struct ocfs2_extent_block *) new_eb_bh->b_data; 662 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 663 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); 664 status = -EIO; 665 goto bail; 666 } 667 668 eb_el = &eb->h_list; 669 fe = (struct ocfs2_dinode *) fe_bh->b_data; 670 fe_el = &fe->id2.i_list; 671 672 status = ocfs2_journal_access(handle, inode, new_eb_bh, 673 OCFS2_JOURNAL_ACCESS_CREATE); 674 if (status < 0) { 675 mlog_errno(status); 676 goto bail; 677 } 678 679 /* copy the fe data into the new extent block */ 680 eb_el->l_tree_depth = fe_el->l_tree_depth; 681 eb_el->l_next_free_rec = fe_el->l_next_free_rec; 682 for(i = 0; i < le16_to_cpu(fe_el->l_next_free_rec); i++) 683 eb_el->l_recs[i] = fe_el->l_recs[i]; 684 685 status = ocfs2_journal_dirty(handle, new_eb_bh); 686 if (status < 0) { 687 mlog_errno(status); 688 goto bail; 689 } 690 691 status = ocfs2_journal_access(handle, inode, fe_bh, 692 OCFS2_JOURNAL_ACCESS_WRITE); 693 if (status < 0) { 694 mlog_errno(status); 695 goto bail; 696 } 697 698 new_clusters = ocfs2_sum_rightmost_rec(eb_el); 699 700 /* update fe now */ 701 le16_add_cpu(&fe_el->l_tree_depth, 1); 702 fe_el->l_recs[0].e_cpos = 0; 703 fe_el->l_recs[0].e_blkno = eb->h_blkno; 704 fe_el->l_recs[0].e_int_clusters = cpu_to_le32(new_clusters); 705 for(i = 1; i < le16_to_cpu(fe_el->l_next_free_rec); i++) 706 memset(&fe_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec)); 707 fe_el->l_next_free_rec = cpu_to_le16(1); 708 709 /* If this is our 1st tree depth shift, then last_eb_blk 710 * becomes the allocated extent block */ 711 if (fe_el->l_tree_depth == cpu_to_le16(1)) 712 fe->i_last_eb_blk = eb->h_blkno; 713 714 status = ocfs2_journal_dirty(handle, fe_bh); 715 if (status < 0) { 716 mlog_errno(status); 717 goto bail; 718 } 719 720 *ret_new_eb_bh = new_eb_bh; 721 new_eb_bh = NULL; 722 status = 0; 723 bail: 724 if (new_eb_bh) 725 brelse(new_eb_bh); 726 727 mlog_exit(status); 728 return status; 729 } 730 731 /* 732 * Should only be called when there is no space left in any of the 733 * leaf nodes. What we want to do is find the lowest tree depth 734 * non-leaf extent block with room for new records. There are three 735 * valid results of this search: 736 * 737 * 1) a lowest extent block is found, then we pass it back in 738 * *lowest_eb_bh and return '0' 739 * 740 * 2) the search fails to find anything, but the dinode has room. We 741 * pass NULL back in *lowest_eb_bh, but still return '0' 742 * 743 * 3) the search fails to find anything AND the dinode is full, in 744 * which case we return > 0 745 * 746 * return status < 0 indicates an error. 747 */ 748 static int ocfs2_find_branch_target(struct ocfs2_super *osb, 749 struct inode *inode, 750 struct buffer_head *fe_bh, 751 struct buffer_head **target_bh) 752 { 753 int status = 0, i; 754 u64 blkno; 755 struct ocfs2_dinode *fe; 756 struct ocfs2_extent_block *eb; 757 struct ocfs2_extent_list *el; 758 struct buffer_head *bh = NULL; 759 struct buffer_head *lowest_bh = NULL; 760 761 mlog_entry_void(); 762 763 *target_bh = NULL; 764 765 fe = (struct ocfs2_dinode *) fe_bh->b_data; 766 el = &fe->id2.i_list; 767 768 while(le16_to_cpu(el->l_tree_depth) > 1) { 769 if (le16_to_cpu(el->l_next_free_rec) == 0) { 770 ocfs2_error(inode->i_sb, "Dinode %llu has empty " 771 "extent list (next_free_rec == 0)", 772 (unsigned long long)OCFS2_I(inode)->ip_blkno); 773 status = -EIO; 774 goto bail; 775 } 776 i = le16_to_cpu(el->l_next_free_rec) - 1; 777 blkno = le64_to_cpu(el->l_recs[i].e_blkno); 778 if (!blkno) { 779 ocfs2_error(inode->i_sb, "Dinode %llu has extent " 780 "list where extent # %d has no physical " 781 "block start", 782 (unsigned long long)OCFS2_I(inode)->ip_blkno, i); 783 status = -EIO; 784 goto bail; 785 } 786 787 if (bh) { 788 brelse(bh); 789 bh = NULL; 790 } 791 792 status = ocfs2_read_block(osb, blkno, &bh, OCFS2_BH_CACHED, 793 inode); 794 if (status < 0) { 795 mlog_errno(status); 796 goto bail; 797 } 798 799 eb = (struct ocfs2_extent_block *) bh->b_data; 800 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 801 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); 802 status = -EIO; 803 goto bail; 804 } 805 el = &eb->h_list; 806 807 if (le16_to_cpu(el->l_next_free_rec) < 808 le16_to_cpu(el->l_count)) { 809 if (lowest_bh) 810 brelse(lowest_bh); 811 lowest_bh = bh; 812 get_bh(lowest_bh); 813 } 814 } 815 816 /* If we didn't find one and the fe doesn't have any room, 817 * then return '1' */ 818 if (!lowest_bh 819 && (fe->id2.i_list.l_next_free_rec == fe->id2.i_list.l_count)) 820 status = 1; 821 822 *target_bh = lowest_bh; 823 bail: 824 if (bh) 825 brelse(bh); 826 827 mlog_exit(status); 828 return status; 829 } 830 831 /* 832 * This is only valid for leaf nodes, which are the only ones that can 833 * have empty extents anyway. 834 */ 835 static inline int ocfs2_is_empty_extent(struct ocfs2_extent_rec *rec) 836 { 837 return !rec->e_leaf_clusters; 838 } 839 840 /* 841 * This function will discard the rightmost extent record. 842 */ 843 static void ocfs2_shift_records_right(struct ocfs2_extent_list *el) 844 { 845 int next_free = le16_to_cpu(el->l_next_free_rec); 846 int count = le16_to_cpu(el->l_count); 847 unsigned int num_bytes; 848 849 BUG_ON(!next_free); 850 /* This will cause us to go off the end of our extent list. */ 851 BUG_ON(next_free >= count); 852 853 num_bytes = sizeof(struct ocfs2_extent_rec) * next_free; 854 855 memmove(&el->l_recs[1], &el->l_recs[0], num_bytes); 856 } 857 858 static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el, 859 struct ocfs2_extent_rec *insert_rec) 860 { 861 int i, insert_index, next_free, has_empty, num_bytes; 862 u32 insert_cpos = le32_to_cpu(insert_rec->e_cpos); 863 struct ocfs2_extent_rec *rec; 864 865 next_free = le16_to_cpu(el->l_next_free_rec); 866 has_empty = ocfs2_is_empty_extent(&el->l_recs[0]); 867 868 BUG_ON(!next_free); 869 870 /* The tree code before us didn't allow enough room in the leaf. */ 871 if (el->l_next_free_rec == el->l_count && !has_empty) 872 BUG(); 873 874 /* 875 * The easiest way to approach this is to just remove the 876 * empty extent and temporarily decrement next_free. 877 */ 878 if (has_empty) { 879 /* 880 * If next_free was 1 (only an empty extent), this 881 * loop won't execute, which is fine. We still want 882 * the decrement above to happen. 883 */ 884 for(i = 0; i < (next_free - 1); i++) 885 el->l_recs[i] = el->l_recs[i+1]; 886 887 next_free--; 888 } 889 890 /* 891 * Figure out what the new record index should be. 892 */ 893 for(i = 0; i < next_free; i++) { 894 rec = &el->l_recs[i]; 895 896 if (insert_cpos < le32_to_cpu(rec->e_cpos)) 897 break; 898 } 899 insert_index = i; 900 901 mlog(0, "ins %u: index %d, has_empty %d, next_free %d, count %d\n", 902 insert_cpos, insert_index, has_empty, next_free, le16_to_cpu(el->l_count)); 903 904 BUG_ON(insert_index < 0); 905 BUG_ON(insert_index >= le16_to_cpu(el->l_count)); 906 BUG_ON(insert_index > next_free); 907 908 /* 909 * No need to memmove if we're just adding to the tail. 910 */ 911 if (insert_index != next_free) { 912 BUG_ON(next_free >= le16_to_cpu(el->l_count)); 913 914 num_bytes = next_free - insert_index; 915 num_bytes *= sizeof(struct ocfs2_extent_rec); 916 memmove(&el->l_recs[insert_index + 1], 917 &el->l_recs[insert_index], 918 num_bytes); 919 } 920 921 /* 922 * Either we had an empty extent, and need to re-increment or 923 * there was no empty extent on a non full rightmost leaf node, 924 * in which case we still need to increment. 925 */ 926 next_free++; 927 el->l_next_free_rec = cpu_to_le16(next_free); 928 /* 929 * Make sure none of the math above just messed up our tree. 930 */ 931 BUG_ON(le16_to_cpu(el->l_next_free_rec) > le16_to_cpu(el->l_count)); 932 933 el->l_recs[insert_index] = *insert_rec; 934 935 } 936 937 /* 938 * Create an empty extent record . 939 * 940 * l_next_free_rec may be updated. 941 * 942 * If an empty extent already exists do nothing. 943 */ 944 static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el) 945 { 946 int next_free = le16_to_cpu(el->l_next_free_rec); 947 948 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 949 950 if (next_free == 0) 951 goto set_and_inc; 952 953 if (ocfs2_is_empty_extent(&el->l_recs[0])) 954 return; 955 956 mlog_bug_on_msg(el->l_count == el->l_next_free_rec, 957 "Asked to create an empty extent in a full list:\n" 958 "count = %u, tree depth = %u", 959 le16_to_cpu(el->l_count), 960 le16_to_cpu(el->l_tree_depth)); 961 962 ocfs2_shift_records_right(el); 963 964 set_and_inc: 965 le16_add_cpu(&el->l_next_free_rec, 1); 966 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 967 } 968 969 /* 970 * For a rotation which involves two leaf nodes, the "root node" is 971 * the lowest level tree node which contains a path to both leafs. This 972 * resulting set of information can be used to form a complete "subtree" 973 * 974 * This function is passed two full paths from the dinode down to a 975 * pair of adjacent leaves. It's task is to figure out which path 976 * index contains the subtree root - this can be the root index itself 977 * in a worst-case rotation. 978 * 979 * The array index of the subtree root is passed back. 980 */ 981 static int ocfs2_find_subtree_root(struct inode *inode, 982 struct ocfs2_path *left, 983 struct ocfs2_path *right) 984 { 985 int i = 0; 986 987 /* 988 * Check that the caller passed in two paths from the same tree. 989 */ 990 BUG_ON(path_root_bh(left) != path_root_bh(right)); 991 992 do { 993 i++; 994 995 /* 996 * The caller didn't pass two adjacent paths. 997 */ 998 mlog_bug_on_msg(i > left->p_tree_depth, 999 "Inode %lu, left depth %u, right depth %u\n" 1000 "left leaf blk %llu, right leaf blk %llu\n", 1001 inode->i_ino, left->p_tree_depth, 1002 right->p_tree_depth, 1003 (unsigned long long)path_leaf_bh(left)->b_blocknr, 1004 (unsigned long long)path_leaf_bh(right)->b_blocknr); 1005 } while (left->p_node[i].bh->b_blocknr == 1006 right->p_node[i].bh->b_blocknr); 1007 1008 return i - 1; 1009 } 1010 1011 typedef void (path_insert_t)(void *, struct buffer_head *); 1012 1013 /* 1014 * Traverse a btree path in search of cpos, starting at root_el. 1015 * 1016 * This code can be called with a cpos larger than the tree, in which 1017 * case it will return the rightmost path. 1018 */ 1019 static int __ocfs2_find_path(struct inode *inode, 1020 struct ocfs2_extent_list *root_el, u32 cpos, 1021 path_insert_t *func, void *data) 1022 { 1023 int i, ret = 0; 1024 u32 range; 1025 u64 blkno; 1026 struct buffer_head *bh = NULL; 1027 struct ocfs2_extent_block *eb; 1028 struct ocfs2_extent_list *el; 1029 struct ocfs2_extent_rec *rec; 1030 struct ocfs2_inode_info *oi = OCFS2_I(inode); 1031 1032 el = root_el; 1033 while (el->l_tree_depth) { 1034 if (le16_to_cpu(el->l_next_free_rec) == 0) { 1035 ocfs2_error(inode->i_sb, 1036 "Inode %llu has empty extent list at " 1037 "depth %u\n", 1038 (unsigned long long)oi->ip_blkno, 1039 le16_to_cpu(el->l_tree_depth)); 1040 ret = -EROFS; 1041 goto out; 1042 1043 } 1044 1045 for(i = 0; i < le16_to_cpu(el->l_next_free_rec) - 1; i++) { 1046 rec = &el->l_recs[i]; 1047 1048 /* 1049 * In the case that cpos is off the allocation 1050 * tree, this should just wind up returning the 1051 * rightmost record. 1052 */ 1053 range = le32_to_cpu(rec->e_cpos) + 1054 ocfs2_rec_clusters(el, rec); 1055 if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range) 1056 break; 1057 } 1058 1059 blkno = le64_to_cpu(el->l_recs[i].e_blkno); 1060 if (blkno == 0) { 1061 ocfs2_error(inode->i_sb, 1062 "Inode %llu has bad blkno in extent list " 1063 "at depth %u (index %d)\n", 1064 (unsigned long long)oi->ip_blkno, 1065 le16_to_cpu(el->l_tree_depth), i); 1066 ret = -EROFS; 1067 goto out; 1068 } 1069 1070 brelse(bh); 1071 bh = NULL; 1072 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), blkno, 1073 &bh, OCFS2_BH_CACHED, inode); 1074 if (ret) { 1075 mlog_errno(ret); 1076 goto out; 1077 } 1078 1079 eb = (struct ocfs2_extent_block *) bh->b_data; 1080 el = &eb->h_list; 1081 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 1082 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); 1083 ret = -EIO; 1084 goto out; 1085 } 1086 1087 if (le16_to_cpu(el->l_next_free_rec) > 1088 le16_to_cpu(el->l_count)) { 1089 ocfs2_error(inode->i_sb, 1090 "Inode %llu has bad count in extent list " 1091 "at block %llu (next free=%u, count=%u)\n", 1092 (unsigned long long)oi->ip_blkno, 1093 (unsigned long long)bh->b_blocknr, 1094 le16_to_cpu(el->l_next_free_rec), 1095 le16_to_cpu(el->l_count)); 1096 ret = -EROFS; 1097 goto out; 1098 } 1099 1100 if (func) 1101 func(data, bh); 1102 } 1103 1104 out: 1105 /* 1106 * Catch any trailing bh that the loop didn't handle. 1107 */ 1108 brelse(bh); 1109 1110 return ret; 1111 } 1112 1113 /* 1114 * Given an initialized path (that is, it has a valid root extent 1115 * list), this function will traverse the btree in search of the path 1116 * which would contain cpos. 1117 * 1118 * The path traveled is recorded in the path structure. 1119 * 1120 * Note that this will not do any comparisons on leaf node extent 1121 * records, so it will work fine in the case that we just added a tree 1122 * branch. 1123 */ 1124 struct find_path_data { 1125 int index; 1126 struct ocfs2_path *path; 1127 }; 1128 static void find_path_ins(void *data, struct buffer_head *bh) 1129 { 1130 struct find_path_data *fp = data; 1131 1132 get_bh(bh); 1133 ocfs2_path_insert_eb(fp->path, fp->index, bh); 1134 fp->index++; 1135 } 1136 static int ocfs2_find_path(struct inode *inode, struct ocfs2_path *path, 1137 u32 cpos) 1138 { 1139 struct find_path_data data; 1140 1141 data.index = 1; 1142 data.path = path; 1143 return __ocfs2_find_path(inode, path_root_el(path), cpos, 1144 find_path_ins, &data); 1145 } 1146 1147 static void find_leaf_ins(void *data, struct buffer_head *bh) 1148 { 1149 struct ocfs2_extent_block *eb =(struct ocfs2_extent_block *)bh->b_data; 1150 struct ocfs2_extent_list *el = &eb->h_list; 1151 struct buffer_head **ret = data; 1152 1153 /* We want to retain only the leaf block. */ 1154 if (le16_to_cpu(el->l_tree_depth) == 0) { 1155 get_bh(bh); 1156 *ret = bh; 1157 } 1158 } 1159 /* 1160 * Find the leaf block in the tree which would contain cpos. No 1161 * checking of the actual leaf is done. 1162 * 1163 * Some paths want to call this instead of allocating a path structure 1164 * and calling ocfs2_find_path(). 1165 * 1166 * This function doesn't handle non btree extent lists. 1167 */ 1168 int ocfs2_find_leaf(struct inode *inode, struct ocfs2_extent_list *root_el, 1169 u32 cpos, struct buffer_head **leaf_bh) 1170 { 1171 int ret; 1172 struct buffer_head *bh = NULL; 1173 1174 ret = __ocfs2_find_path(inode, root_el, cpos, find_leaf_ins, &bh); 1175 if (ret) { 1176 mlog_errno(ret); 1177 goto out; 1178 } 1179 1180 *leaf_bh = bh; 1181 out: 1182 return ret; 1183 } 1184 1185 /* 1186 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation. 1187 * 1188 * Basically, we've moved stuff around at the bottom of the tree and 1189 * we need to fix up the extent records above the changes to reflect 1190 * the new changes. 1191 * 1192 * left_rec: the record on the left. 1193 * left_child_el: is the child list pointed to by left_rec 1194 * right_rec: the record to the right of left_rec 1195 * right_child_el: is the child list pointed to by right_rec 1196 * 1197 * By definition, this only works on interior nodes. 1198 */ 1199 static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec, 1200 struct ocfs2_extent_list *left_child_el, 1201 struct ocfs2_extent_rec *right_rec, 1202 struct ocfs2_extent_list *right_child_el) 1203 { 1204 u32 left_clusters, right_end; 1205 1206 /* 1207 * Interior nodes never have holes. Their cpos is the cpos of 1208 * the leftmost record in their child list. Their cluster 1209 * count covers the full theoretical range of their child list 1210 * - the range between their cpos and the cpos of the record 1211 * immediately to their right. 1212 */ 1213 left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos); 1214 left_clusters -= le32_to_cpu(left_rec->e_cpos); 1215 left_rec->e_int_clusters = cpu_to_le32(left_clusters); 1216 1217 /* 1218 * Calculate the rightmost cluster count boundary before 1219 * moving cpos - we will need to adjust clusters after 1220 * updating e_cpos to keep the same highest cluster count. 1221 */ 1222 right_end = le32_to_cpu(right_rec->e_cpos); 1223 right_end += le32_to_cpu(right_rec->e_int_clusters); 1224 1225 right_rec->e_cpos = left_rec->e_cpos; 1226 le32_add_cpu(&right_rec->e_cpos, left_clusters); 1227 1228 right_end -= le32_to_cpu(right_rec->e_cpos); 1229 right_rec->e_int_clusters = cpu_to_le32(right_end); 1230 } 1231 1232 /* 1233 * Adjust the adjacent root node records involved in a 1234 * rotation. left_el_blkno is passed in as a key so that we can easily 1235 * find it's index in the root list. 1236 */ 1237 static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el, 1238 struct ocfs2_extent_list *left_el, 1239 struct ocfs2_extent_list *right_el, 1240 u64 left_el_blkno) 1241 { 1242 int i; 1243 1244 BUG_ON(le16_to_cpu(root_el->l_tree_depth) <= 1245 le16_to_cpu(left_el->l_tree_depth)); 1246 1247 for(i = 0; i < le16_to_cpu(root_el->l_next_free_rec) - 1; i++) { 1248 if (le64_to_cpu(root_el->l_recs[i].e_blkno) == left_el_blkno) 1249 break; 1250 } 1251 1252 /* 1253 * The path walking code should have never returned a root and 1254 * two paths which are not adjacent. 1255 */ 1256 BUG_ON(i >= (le16_to_cpu(root_el->l_next_free_rec) - 1)); 1257 1258 ocfs2_adjust_adjacent_records(&root_el->l_recs[i], left_el, 1259 &root_el->l_recs[i + 1], right_el); 1260 } 1261 1262 /* 1263 * We've changed a leaf block (in right_path) and need to reflect that 1264 * change back up the subtree. 1265 * 1266 * This happens in multiple places: 1267 * - When we've moved an extent record from the left path leaf to the right 1268 * path leaf to make room for an empty extent in the left path leaf. 1269 * - When our insert into the right path leaf is at the leftmost edge 1270 * and requires an update of the path immediately to it's left. This 1271 * can occur at the end of some types of rotation and appending inserts. 1272 */ 1273 static void ocfs2_complete_edge_insert(struct inode *inode, handle_t *handle, 1274 struct ocfs2_path *left_path, 1275 struct ocfs2_path *right_path, 1276 int subtree_index) 1277 { 1278 int ret, i, idx; 1279 struct ocfs2_extent_list *el, *left_el, *right_el; 1280 struct ocfs2_extent_rec *left_rec, *right_rec; 1281 struct buffer_head *root_bh = left_path->p_node[subtree_index].bh; 1282 1283 /* 1284 * Update the counts and position values within all the 1285 * interior nodes to reflect the leaf rotation we just did. 1286 * 1287 * The root node is handled below the loop. 1288 * 1289 * We begin the loop with right_el and left_el pointing to the 1290 * leaf lists and work our way up. 1291 * 1292 * NOTE: within this loop, left_el and right_el always refer 1293 * to the *child* lists. 1294 */ 1295 left_el = path_leaf_el(left_path); 1296 right_el = path_leaf_el(right_path); 1297 for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) { 1298 mlog(0, "Adjust records at index %u\n", i); 1299 1300 /* 1301 * One nice property of knowing that all of these 1302 * nodes are below the root is that we only deal with 1303 * the leftmost right node record and the rightmost 1304 * left node record. 1305 */ 1306 el = left_path->p_node[i].el; 1307 idx = le16_to_cpu(left_el->l_next_free_rec) - 1; 1308 left_rec = &el->l_recs[idx]; 1309 1310 el = right_path->p_node[i].el; 1311 right_rec = &el->l_recs[0]; 1312 1313 ocfs2_adjust_adjacent_records(left_rec, left_el, right_rec, 1314 right_el); 1315 1316 ret = ocfs2_journal_dirty(handle, left_path->p_node[i].bh); 1317 if (ret) 1318 mlog_errno(ret); 1319 1320 ret = ocfs2_journal_dirty(handle, right_path->p_node[i].bh); 1321 if (ret) 1322 mlog_errno(ret); 1323 1324 /* 1325 * Setup our list pointers now so that the current 1326 * parents become children in the next iteration. 1327 */ 1328 left_el = left_path->p_node[i].el; 1329 right_el = right_path->p_node[i].el; 1330 } 1331 1332 /* 1333 * At the root node, adjust the two adjacent records which 1334 * begin our path to the leaves. 1335 */ 1336 1337 el = left_path->p_node[subtree_index].el; 1338 left_el = left_path->p_node[subtree_index + 1].el; 1339 right_el = right_path->p_node[subtree_index + 1].el; 1340 1341 ocfs2_adjust_root_records(el, left_el, right_el, 1342 left_path->p_node[subtree_index + 1].bh->b_blocknr); 1343 1344 root_bh = left_path->p_node[subtree_index].bh; 1345 1346 ret = ocfs2_journal_dirty(handle, root_bh); 1347 if (ret) 1348 mlog_errno(ret); 1349 } 1350 1351 static int ocfs2_rotate_subtree_right(struct inode *inode, 1352 handle_t *handle, 1353 struct ocfs2_path *left_path, 1354 struct ocfs2_path *right_path, 1355 int subtree_index) 1356 { 1357 int ret, i; 1358 struct buffer_head *right_leaf_bh; 1359 struct buffer_head *left_leaf_bh = NULL; 1360 struct buffer_head *root_bh; 1361 struct ocfs2_extent_list *right_el, *left_el; 1362 struct ocfs2_extent_rec move_rec; 1363 1364 left_leaf_bh = path_leaf_bh(left_path); 1365 left_el = path_leaf_el(left_path); 1366 1367 if (left_el->l_next_free_rec != left_el->l_count) { 1368 ocfs2_error(inode->i_sb, 1369 "Inode %llu has non-full interior leaf node %llu" 1370 "(next free = %u)", 1371 (unsigned long long)OCFS2_I(inode)->ip_blkno, 1372 (unsigned long long)left_leaf_bh->b_blocknr, 1373 le16_to_cpu(left_el->l_next_free_rec)); 1374 return -EROFS; 1375 } 1376 1377 /* 1378 * This extent block may already have an empty record, so we 1379 * return early if so. 1380 */ 1381 if (ocfs2_is_empty_extent(&left_el->l_recs[0])) 1382 return 0; 1383 1384 root_bh = left_path->p_node[subtree_index].bh; 1385 BUG_ON(root_bh != right_path->p_node[subtree_index].bh); 1386 1387 ret = ocfs2_journal_access(handle, inode, root_bh, 1388 OCFS2_JOURNAL_ACCESS_WRITE); 1389 if (ret) { 1390 mlog_errno(ret); 1391 goto out; 1392 } 1393 1394 for(i = subtree_index + 1; i < path_num_items(right_path); i++) { 1395 ret = ocfs2_journal_access(handle, inode, 1396 right_path->p_node[i].bh, 1397 OCFS2_JOURNAL_ACCESS_WRITE); 1398 if (ret) { 1399 mlog_errno(ret); 1400 goto out; 1401 } 1402 1403 ret = ocfs2_journal_access(handle, inode, 1404 left_path->p_node[i].bh, 1405 OCFS2_JOURNAL_ACCESS_WRITE); 1406 if (ret) { 1407 mlog_errno(ret); 1408 goto out; 1409 } 1410 } 1411 1412 right_leaf_bh = path_leaf_bh(right_path); 1413 right_el = path_leaf_el(right_path); 1414 1415 /* This is a code error, not a disk corruption. */ 1416 mlog_bug_on_msg(!right_el->l_next_free_rec, "Inode %llu: Rotate fails " 1417 "because rightmost leaf block %llu is empty\n", 1418 (unsigned long long)OCFS2_I(inode)->ip_blkno, 1419 (unsigned long long)right_leaf_bh->b_blocknr); 1420 1421 ocfs2_create_empty_extent(right_el); 1422 1423 ret = ocfs2_journal_dirty(handle, right_leaf_bh); 1424 if (ret) { 1425 mlog_errno(ret); 1426 goto out; 1427 } 1428 1429 /* Do the copy now. */ 1430 i = le16_to_cpu(left_el->l_next_free_rec) - 1; 1431 move_rec = left_el->l_recs[i]; 1432 right_el->l_recs[0] = move_rec; 1433 1434 /* 1435 * Clear out the record we just copied and shift everything 1436 * over, leaving an empty extent in the left leaf. 1437 * 1438 * We temporarily subtract from next_free_rec so that the 1439 * shift will lose the tail record (which is now defunct). 1440 */ 1441 le16_add_cpu(&left_el->l_next_free_rec, -1); 1442 ocfs2_shift_records_right(left_el); 1443 memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 1444 le16_add_cpu(&left_el->l_next_free_rec, 1); 1445 1446 ret = ocfs2_journal_dirty(handle, left_leaf_bh); 1447 if (ret) { 1448 mlog_errno(ret); 1449 goto out; 1450 } 1451 1452 ocfs2_complete_edge_insert(inode, handle, left_path, right_path, 1453 subtree_index); 1454 1455 out: 1456 return ret; 1457 } 1458 1459 /* 1460 * Given a full path, determine what cpos value would return us a path 1461 * containing the leaf immediately to the left of the current one. 1462 * 1463 * Will return zero if the path passed in is already the leftmost path. 1464 */ 1465 static int ocfs2_find_cpos_for_left_leaf(struct super_block *sb, 1466 struct ocfs2_path *path, u32 *cpos) 1467 { 1468 int i, j, ret = 0; 1469 u64 blkno; 1470 struct ocfs2_extent_list *el; 1471 1472 BUG_ON(path->p_tree_depth == 0); 1473 1474 *cpos = 0; 1475 1476 blkno = path_leaf_bh(path)->b_blocknr; 1477 1478 /* Start at the tree node just above the leaf and work our way up. */ 1479 i = path->p_tree_depth - 1; 1480 while (i >= 0) { 1481 el = path->p_node[i].el; 1482 1483 /* 1484 * Find the extent record just before the one in our 1485 * path. 1486 */ 1487 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) { 1488 if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) { 1489 if (j == 0) { 1490 if (i == 0) { 1491 /* 1492 * We've determined that the 1493 * path specified is already 1494 * the leftmost one - return a 1495 * cpos of zero. 1496 */ 1497 goto out; 1498 } 1499 /* 1500 * The leftmost record points to our 1501 * leaf - we need to travel up the 1502 * tree one level. 1503 */ 1504 goto next_node; 1505 } 1506 1507 *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos); 1508 *cpos = *cpos + ocfs2_rec_clusters(el, 1509 &el->l_recs[j - 1]); 1510 *cpos = *cpos - 1; 1511 goto out; 1512 } 1513 } 1514 1515 /* 1516 * If we got here, we never found a valid node where 1517 * the tree indicated one should be. 1518 */ 1519 ocfs2_error(sb, 1520 "Invalid extent tree at extent block %llu\n", 1521 (unsigned long long)blkno); 1522 ret = -EROFS; 1523 goto out; 1524 1525 next_node: 1526 blkno = path->p_node[i].bh->b_blocknr; 1527 i--; 1528 } 1529 1530 out: 1531 return ret; 1532 } 1533 1534 static int ocfs2_extend_rotate_transaction(handle_t *handle, int subtree_depth, 1535 struct ocfs2_path *path) 1536 { 1537 int credits = (path->p_tree_depth - subtree_depth) * 2 + 1; 1538 1539 if (handle->h_buffer_credits < credits) 1540 return ocfs2_extend_trans(handle, credits); 1541 1542 return 0; 1543 } 1544 1545 /* 1546 * Trap the case where we're inserting into the theoretical range past 1547 * the _actual_ left leaf range. Otherwise, we'll rotate a record 1548 * whose cpos is less than ours into the right leaf. 1549 * 1550 * It's only necessary to look at the rightmost record of the left 1551 * leaf because the logic that calls us should ensure that the 1552 * theoretical ranges in the path components above the leaves are 1553 * correct. 1554 */ 1555 static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path, 1556 u32 insert_cpos) 1557 { 1558 struct ocfs2_extent_list *left_el; 1559 struct ocfs2_extent_rec *rec; 1560 int next_free; 1561 1562 left_el = path_leaf_el(left_path); 1563 next_free = le16_to_cpu(left_el->l_next_free_rec); 1564 rec = &left_el->l_recs[next_free - 1]; 1565 1566 if (insert_cpos > le32_to_cpu(rec->e_cpos)) 1567 return 1; 1568 return 0; 1569 } 1570 1571 /* 1572 * Rotate all the records in a btree right one record, starting at insert_cpos. 1573 * 1574 * The path to the rightmost leaf should be passed in. 1575 * 1576 * The array is assumed to be large enough to hold an entire path (tree depth). 1577 * 1578 * Upon succesful return from this function: 1579 * 1580 * - The 'right_path' array will contain a path to the leaf block 1581 * whose range contains e_cpos. 1582 * - That leaf block will have a single empty extent in list index 0. 1583 * - In the case that the rotation requires a post-insert update, 1584 * *ret_left_path will contain a valid path which can be passed to 1585 * ocfs2_insert_path(). 1586 */ 1587 static int ocfs2_rotate_tree_right(struct inode *inode, 1588 handle_t *handle, 1589 u32 insert_cpos, 1590 struct ocfs2_path *right_path, 1591 struct ocfs2_path **ret_left_path) 1592 { 1593 int ret, start; 1594 u32 cpos; 1595 struct ocfs2_path *left_path = NULL; 1596 1597 *ret_left_path = NULL; 1598 1599 left_path = ocfs2_new_path(path_root_bh(right_path), 1600 path_root_el(right_path)); 1601 if (!left_path) { 1602 ret = -ENOMEM; 1603 mlog_errno(ret); 1604 goto out; 1605 } 1606 1607 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, &cpos); 1608 if (ret) { 1609 mlog_errno(ret); 1610 goto out; 1611 } 1612 1613 mlog(0, "Insert: %u, first left path cpos: %u\n", insert_cpos, cpos); 1614 1615 /* 1616 * What we want to do here is: 1617 * 1618 * 1) Start with the rightmost path. 1619 * 1620 * 2) Determine a path to the leaf block directly to the left 1621 * of that leaf. 1622 * 1623 * 3) Determine the 'subtree root' - the lowest level tree node 1624 * which contains a path to both leaves. 1625 * 1626 * 4) Rotate the subtree. 1627 * 1628 * 5) Find the next subtree by considering the left path to be 1629 * the new right path. 1630 * 1631 * The check at the top of this while loop also accepts 1632 * insert_cpos == cpos because cpos is only a _theoretical_ 1633 * value to get us the left path - insert_cpos might very well 1634 * be filling that hole. 1635 * 1636 * Stop at a cpos of '0' because we either started at the 1637 * leftmost branch (i.e., a tree with one branch and a 1638 * rotation inside of it), or we've gone as far as we can in 1639 * rotating subtrees. 1640 */ 1641 while (cpos && insert_cpos <= cpos) { 1642 mlog(0, "Rotating a tree: ins. cpos: %u, left path cpos: %u\n", 1643 insert_cpos, cpos); 1644 1645 ret = ocfs2_find_path(inode, left_path, cpos); 1646 if (ret) { 1647 mlog_errno(ret); 1648 goto out; 1649 } 1650 1651 mlog_bug_on_msg(path_leaf_bh(left_path) == 1652 path_leaf_bh(right_path), 1653 "Inode %lu: error during insert of %u " 1654 "(left path cpos %u) results in two identical " 1655 "paths ending at %llu\n", 1656 inode->i_ino, insert_cpos, cpos, 1657 (unsigned long long) 1658 path_leaf_bh(left_path)->b_blocknr); 1659 1660 if (ocfs2_rotate_requires_path_adjustment(left_path, 1661 insert_cpos)) { 1662 mlog(0, "Path adjustment required\n"); 1663 1664 /* 1665 * We've rotated the tree as much as we 1666 * should. The rest is up to 1667 * ocfs2_insert_path() to complete, after the 1668 * record insertion. We indicate this 1669 * situation by returning the left path. 1670 * 1671 * The reason we don't adjust the records here 1672 * before the record insert is that an error 1673 * later might break the rule where a parent 1674 * record e_cpos will reflect the actual 1675 * e_cpos of the 1st nonempty record of the 1676 * child list. 1677 */ 1678 *ret_left_path = left_path; 1679 goto out_ret_path; 1680 } 1681 1682 start = ocfs2_find_subtree_root(inode, left_path, right_path); 1683 1684 mlog(0, "Subtree root at index %d (blk %llu, depth %d)\n", 1685 start, 1686 (unsigned long long) right_path->p_node[start].bh->b_blocknr, 1687 right_path->p_tree_depth); 1688 1689 ret = ocfs2_extend_rotate_transaction(handle, start, 1690 right_path); 1691 if (ret) { 1692 mlog_errno(ret); 1693 goto out; 1694 } 1695 1696 ret = ocfs2_rotate_subtree_right(inode, handle, left_path, 1697 right_path, start); 1698 if (ret) { 1699 mlog_errno(ret); 1700 goto out; 1701 } 1702 1703 /* 1704 * There is no need to re-read the next right path 1705 * as we know that it'll be our current left 1706 * path. Optimize by copying values instead. 1707 */ 1708 ocfs2_mv_path(right_path, left_path); 1709 1710 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, 1711 &cpos); 1712 if (ret) { 1713 mlog_errno(ret); 1714 goto out; 1715 } 1716 } 1717 1718 out: 1719 ocfs2_free_path(left_path); 1720 1721 out_ret_path: 1722 return ret; 1723 } 1724 1725 /* 1726 * Do the final bits of extent record insertion at the target leaf 1727 * list. If this leaf is part of an allocation tree, it is assumed 1728 * that the tree above has been prepared. 1729 */ 1730 static void ocfs2_insert_at_leaf(struct ocfs2_extent_rec *insert_rec, 1731 struct ocfs2_extent_list *el, 1732 struct ocfs2_insert_type *insert, 1733 struct inode *inode) 1734 { 1735 int i = insert->ins_contig_index; 1736 unsigned int range; 1737 struct ocfs2_extent_rec *rec; 1738 1739 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 1740 1741 /* 1742 * Contiguous insert - either left or right. 1743 */ 1744 if (insert->ins_contig != CONTIG_NONE) { 1745 rec = &el->l_recs[i]; 1746 if (insert->ins_contig == CONTIG_LEFT) { 1747 rec->e_blkno = insert_rec->e_blkno; 1748 rec->e_cpos = insert_rec->e_cpos; 1749 } 1750 le16_add_cpu(&rec->e_leaf_clusters, 1751 le16_to_cpu(insert_rec->e_leaf_clusters)); 1752 return; 1753 } 1754 1755 /* 1756 * Handle insert into an empty leaf. 1757 */ 1758 if (le16_to_cpu(el->l_next_free_rec) == 0 || 1759 ((le16_to_cpu(el->l_next_free_rec) == 1) && 1760 ocfs2_is_empty_extent(&el->l_recs[0]))) { 1761 el->l_recs[0] = *insert_rec; 1762 el->l_next_free_rec = cpu_to_le16(1); 1763 return; 1764 } 1765 1766 /* 1767 * Appending insert. 1768 */ 1769 if (insert->ins_appending == APPEND_TAIL) { 1770 i = le16_to_cpu(el->l_next_free_rec) - 1; 1771 rec = &el->l_recs[i]; 1772 range = le32_to_cpu(rec->e_cpos) 1773 + le16_to_cpu(rec->e_leaf_clusters); 1774 BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range); 1775 1776 mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >= 1777 le16_to_cpu(el->l_count), 1778 "inode %lu, depth %u, count %u, next free %u, " 1779 "rec.cpos %u, rec.clusters %u, " 1780 "insert.cpos %u, insert.clusters %u\n", 1781 inode->i_ino, 1782 le16_to_cpu(el->l_tree_depth), 1783 le16_to_cpu(el->l_count), 1784 le16_to_cpu(el->l_next_free_rec), 1785 le32_to_cpu(el->l_recs[i].e_cpos), 1786 le16_to_cpu(el->l_recs[i].e_leaf_clusters), 1787 le32_to_cpu(insert_rec->e_cpos), 1788 le16_to_cpu(insert_rec->e_leaf_clusters)); 1789 i++; 1790 el->l_recs[i] = *insert_rec; 1791 le16_add_cpu(&el->l_next_free_rec, 1); 1792 return; 1793 } 1794 1795 /* 1796 * Ok, we have to rotate. 1797 * 1798 * At this point, it is safe to assume that inserting into an 1799 * empty leaf and appending to a leaf have both been handled 1800 * above. 1801 * 1802 * This leaf needs to have space, either by the empty 1st 1803 * extent record, or by virtue of an l_next_rec < l_count. 1804 */ 1805 ocfs2_rotate_leaf(el, insert_rec); 1806 } 1807 1808 static inline void ocfs2_update_dinode_clusters(struct inode *inode, 1809 struct ocfs2_dinode *di, 1810 u32 clusters) 1811 { 1812 le32_add_cpu(&di->i_clusters, clusters); 1813 spin_lock(&OCFS2_I(inode)->ip_lock); 1814 OCFS2_I(inode)->ip_clusters = le32_to_cpu(di->i_clusters); 1815 spin_unlock(&OCFS2_I(inode)->ip_lock); 1816 } 1817 1818 static int ocfs2_append_rec_to_path(struct inode *inode, handle_t *handle, 1819 struct ocfs2_extent_rec *insert_rec, 1820 struct ocfs2_path *right_path, 1821 struct ocfs2_path **ret_left_path) 1822 { 1823 int ret, i, next_free; 1824 struct buffer_head *bh; 1825 struct ocfs2_extent_list *el; 1826 struct ocfs2_path *left_path = NULL; 1827 1828 *ret_left_path = NULL; 1829 1830 /* 1831 * This shouldn't happen for non-trees. The extent rec cluster 1832 * count manipulation below only works for interior nodes. 1833 */ 1834 BUG_ON(right_path->p_tree_depth == 0); 1835 1836 /* 1837 * If our appending insert is at the leftmost edge of a leaf, 1838 * then we might need to update the rightmost records of the 1839 * neighboring path. 1840 */ 1841 el = path_leaf_el(right_path); 1842 next_free = le16_to_cpu(el->l_next_free_rec); 1843 if (next_free == 0 || 1844 (next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) { 1845 u32 left_cpos; 1846 1847 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, right_path, 1848 &left_cpos); 1849 if (ret) { 1850 mlog_errno(ret); 1851 goto out; 1852 } 1853 1854 mlog(0, "Append may need a left path update. cpos: %u, " 1855 "left_cpos: %u\n", le32_to_cpu(insert_rec->e_cpos), 1856 left_cpos); 1857 1858 /* 1859 * No need to worry if the append is already in the 1860 * leftmost leaf. 1861 */ 1862 if (left_cpos) { 1863 left_path = ocfs2_new_path(path_root_bh(right_path), 1864 path_root_el(right_path)); 1865 if (!left_path) { 1866 ret = -ENOMEM; 1867 mlog_errno(ret); 1868 goto out; 1869 } 1870 1871 ret = ocfs2_find_path(inode, left_path, left_cpos); 1872 if (ret) { 1873 mlog_errno(ret); 1874 goto out; 1875 } 1876 1877 /* 1878 * ocfs2_insert_path() will pass the left_path to the 1879 * journal for us. 1880 */ 1881 } 1882 } 1883 1884 ret = ocfs2_journal_access_path(inode, handle, right_path); 1885 if (ret) { 1886 mlog_errno(ret); 1887 goto out; 1888 } 1889 1890 el = path_root_el(right_path); 1891 bh = path_root_bh(right_path); 1892 i = 0; 1893 while (1) { 1894 struct ocfs2_extent_rec *rec; 1895 1896 next_free = le16_to_cpu(el->l_next_free_rec); 1897 if (next_free == 0) { 1898 ocfs2_error(inode->i_sb, 1899 "Dinode %llu has a bad extent list", 1900 (unsigned long long)OCFS2_I(inode)->ip_blkno); 1901 ret = -EIO; 1902 goto out; 1903 } 1904 1905 rec = &el->l_recs[next_free - 1]; 1906 1907 rec->e_int_clusters = insert_rec->e_cpos; 1908 le32_add_cpu(&rec->e_int_clusters, 1909 le16_to_cpu(insert_rec->e_leaf_clusters)); 1910 le32_add_cpu(&rec->e_int_clusters, 1911 -le32_to_cpu(rec->e_cpos)); 1912 1913 ret = ocfs2_journal_dirty(handle, bh); 1914 if (ret) 1915 mlog_errno(ret); 1916 1917 /* Don't touch the leaf node */ 1918 if (++i >= right_path->p_tree_depth) 1919 break; 1920 1921 bh = right_path->p_node[i].bh; 1922 el = right_path->p_node[i].el; 1923 } 1924 1925 *ret_left_path = left_path; 1926 ret = 0; 1927 out: 1928 if (ret != 0) 1929 ocfs2_free_path(left_path); 1930 1931 return ret; 1932 } 1933 1934 /* 1935 * This function only does inserts on an allocation b-tree. For dinode 1936 * lists, ocfs2_insert_at_leaf() is called directly. 1937 * 1938 * right_path is the path we want to do the actual insert 1939 * in. left_path should only be passed in if we need to update that 1940 * portion of the tree after an edge insert. 1941 */ 1942 static int ocfs2_insert_path(struct inode *inode, 1943 handle_t *handle, 1944 struct ocfs2_path *left_path, 1945 struct ocfs2_path *right_path, 1946 struct ocfs2_extent_rec *insert_rec, 1947 struct ocfs2_insert_type *insert) 1948 { 1949 int ret, subtree_index; 1950 struct buffer_head *leaf_bh = path_leaf_bh(right_path); 1951 struct ocfs2_extent_list *el; 1952 1953 /* 1954 * Pass both paths to the journal. The majority of inserts 1955 * will be touching all components anyway. 1956 */ 1957 ret = ocfs2_journal_access_path(inode, handle, right_path); 1958 if (ret < 0) { 1959 mlog_errno(ret); 1960 goto out; 1961 } 1962 1963 if (left_path) { 1964 int credits = handle->h_buffer_credits; 1965 1966 /* 1967 * There's a chance that left_path got passed back to 1968 * us without being accounted for in the 1969 * journal. Extend our transaction here to be sure we 1970 * can change those blocks. 1971 */ 1972 credits += left_path->p_tree_depth; 1973 1974 ret = ocfs2_extend_trans(handle, credits); 1975 if (ret < 0) { 1976 mlog_errno(ret); 1977 goto out; 1978 } 1979 1980 ret = ocfs2_journal_access_path(inode, handle, left_path); 1981 if (ret < 0) { 1982 mlog_errno(ret); 1983 goto out; 1984 } 1985 } 1986 1987 el = path_leaf_el(right_path); 1988 1989 ocfs2_insert_at_leaf(insert_rec, el, insert, inode); 1990 ret = ocfs2_journal_dirty(handle, leaf_bh); 1991 if (ret) 1992 mlog_errno(ret); 1993 1994 if (left_path) { 1995 /* 1996 * The rotate code has indicated that we need to fix 1997 * up portions of the tree after the insert. 1998 * 1999 * XXX: Should we extend the transaction here? 2000 */ 2001 subtree_index = ocfs2_find_subtree_root(inode, left_path, 2002 right_path); 2003 ocfs2_complete_edge_insert(inode, handle, left_path, 2004 right_path, subtree_index); 2005 } 2006 2007 ret = 0; 2008 out: 2009 return ret; 2010 } 2011 2012 static int ocfs2_do_insert_extent(struct inode *inode, 2013 handle_t *handle, 2014 struct buffer_head *di_bh, 2015 struct ocfs2_extent_rec *insert_rec, 2016 struct ocfs2_insert_type *type) 2017 { 2018 int ret, rotate = 0; 2019 u32 cpos; 2020 struct ocfs2_path *right_path = NULL; 2021 struct ocfs2_path *left_path = NULL; 2022 struct ocfs2_dinode *di; 2023 struct ocfs2_extent_list *el; 2024 2025 di = (struct ocfs2_dinode *) di_bh->b_data; 2026 el = &di->id2.i_list; 2027 2028 ret = ocfs2_journal_access(handle, inode, di_bh, 2029 OCFS2_JOURNAL_ACCESS_WRITE); 2030 if (ret) { 2031 mlog_errno(ret); 2032 goto out; 2033 } 2034 2035 if (le16_to_cpu(el->l_tree_depth) == 0) { 2036 ocfs2_insert_at_leaf(insert_rec, el, type, inode); 2037 goto out_update_clusters; 2038 } 2039 2040 right_path = ocfs2_new_inode_path(di_bh); 2041 if (!right_path) { 2042 ret = -ENOMEM; 2043 mlog_errno(ret); 2044 goto out; 2045 } 2046 2047 /* 2048 * Determine the path to start with. Rotations need the 2049 * rightmost path, everything else can go directly to the 2050 * target leaf. 2051 */ 2052 cpos = le32_to_cpu(insert_rec->e_cpos); 2053 if (type->ins_appending == APPEND_NONE && 2054 type->ins_contig == CONTIG_NONE) { 2055 rotate = 1; 2056 cpos = UINT_MAX; 2057 } 2058 2059 ret = ocfs2_find_path(inode, right_path, cpos); 2060 if (ret) { 2061 mlog_errno(ret); 2062 goto out; 2063 } 2064 2065 /* 2066 * Rotations and appends need special treatment - they modify 2067 * parts of the tree's above them. 2068 * 2069 * Both might pass back a path immediate to the left of the 2070 * one being inserted to. This will be cause 2071 * ocfs2_insert_path() to modify the rightmost records of 2072 * left_path to account for an edge insert. 2073 * 2074 * XXX: When modifying this code, keep in mind that an insert 2075 * can wind up skipping both of these two special cases... 2076 */ 2077 if (rotate) { 2078 ret = ocfs2_rotate_tree_right(inode, handle, 2079 le32_to_cpu(insert_rec->e_cpos), 2080 right_path, &left_path); 2081 if (ret) { 2082 mlog_errno(ret); 2083 goto out; 2084 } 2085 } else if (type->ins_appending == APPEND_TAIL 2086 && type->ins_contig != CONTIG_LEFT) { 2087 ret = ocfs2_append_rec_to_path(inode, handle, insert_rec, 2088 right_path, &left_path); 2089 if (ret) { 2090 mlog_errno(ret); 2091 goto out; 2092 } 2093 } 2094 2095 ret = ocfs2_insert_path(inode, handle, left_path, right_path, 2096 insert_rec, type); 2097 if (ret) { 2098 mlog_errno(ret); 2099 goto out; 2100 } 2101 2102 out_update_clusters: 2103 ocfs2_update_dinode_clusters(inode, di, 2104 le16_to_cpu(insert_rec->e_leaf_clusters)); 2105 2106 ret = ocfs2_journal_dirty(handle, di_bh); 2107 if (ret) 2108 mlog_errno(ret); 2109 2110 out: 2111 ocfs2_free_path(left_path); 2112 ocfs2_free_path(right_path); 2113 2114 return ret; 2115 } 2116 2117 static void ocfs2_figure_contig_type(struct inode *inode, 2118 struct ocfs2_insert_type *insert, 2119 struct ocfs2_extent_list *el, 2120 struct ocfs2_extent_rec *insert_rec) 2121 { 2122 int i; 2123 enum ocfs2_contig_type contig_type = CONTIG_NONE; 2124 2125 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 2126 2127 for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { 2128 contig_type = ocfs2_extent_contig(inode, &el->l_recs[i], 2129 insert_rec); 2130 if (contig_type != CONTIG_NONE) { 2131 insert->ins_contig_index = i; 2132 break; 2133 } 2134 } 2135 insert->ins_contig = contig_type; 2136 } 2137 2138 /* 2139 * This should only be called against the righmost leaf extent list. 2140 * 2141 * ocfs2_figure_appending_type() will figure out whether we'll have to 2142 * insert at the tail of the rightmost leaf. 2143 * 2144 * This should also work against the dinode list for tree's with 0 2145 * depth. If we consider the dinode list to be the rightmost leaf node 2146 * then the logic here makes sense. 2147 */ 2148 static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert, 2149 struct ocfs2_extent_list *el, 2150 struct ocfs2_extent_rec *insert_rec) 2151 { 2152 int i; 2153 u32 cpos = le32_to_cpu(insert_rec->e_cpos); 2154 struct ocfs2_extent_rec *rec; 2155 2156 insert->ins_appending = APPEND_NONE; 2157 2158 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 2159 2160 if (!el->l_next_free_rec) 2161 goto set_tail_append; 2162 2163 if (ocfs2_is_empty_extent(&el->l_recs[0])) { 2164 /* Were all records empty? */ 2165 if (le16_to_cpu(el->l_next_free_rec) == 1) 2166 goto set_tail_append; 2167 } 2168 2169 i = le16_to_cpu(el->l_next_free_rec) - 1; 2170 rec = &el->l_recs[i]; 2171 2172 if (cpos >= 2173 (le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters))) 2174 goto set_tail_append; 2175 2176 return; 2177 2178 set_tail_append: 2179 insert->ins_appending = APPEND_TAIL; 2180 } 2181 2182 /* 2183 * Helper function called at the begining of an insert. 2184 * 2185 * This computes a few things that are commonly used in the process of 2186 * inserting into the btree: 2187 * - Whether the new extent is contiguous with an existing one. 2188 * - The current tree depth. 2189 * - Whether the insert is an appending one. 2190 * - The total # of free records in the tree. 2191 * 2192 * All of the information is stored on the ocfs2_insert_type 2193 * structure. 2194 */ 2195 static int ocfs2_figure_insert_type(struct inode *inode, 2196 struct buffer_head *di_bh, 2197 struct buffer_head **last_eb_bh, 2198 struct ocfs2_extent_rec *insert_rec, 2199 struct ocfs2_insert_type *insert) 2200 { 2201 int ret; 2202 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; 2203 struct ocfs2_extent_block *eb; 2204 struct ocfs2_extent_list *el; 2205 struct ocfs2_path *path = NULL; 2206 struct buffer_head *bh = NULL; 2207 2208 el = &di->id2.i_list; 2209 insert->ins_tree_depth = le16_to_cpu(el->l_tree_depth); 2210 2211 if (el->l_tree_depth) { 2212 /* 2213 * If we have tree depth, we read in the 2214 * rightmost extent block ahead of time as 2215 * ocfs2_figure_insert_type() and ocfs2_add_branch() 2216 * may want it later. 2217 */ 2218 ret = ocfs2_read_block(OCFS2_SB(inode->i_sb), 2219 le64_to_cpu(di->i_last_eb_blk), &bh, 2220 OCFS2_BH_CACHED, inode); 2221 if (ret) { 2222 mlog_exit(ret); 2223 goto out; 2224 } 2225 eb = (struct ocfs2_extent_block *) bh->b_data; 2226 el = &eb->h_list; 2227 } 2228 2229 /* 2230 * Unless we have a contiguous insert, we'll need to know if 2231 * there is room left in our allocation tree for another 2232 * extent record. 2233 * 2234 * XXX: This test is simplistic, we can search for empty 2235 * extent records too. 2236 */ 2237 insert->ins_free_records = le16_to_cpu(el->l_count) - 2238 le16_to_cpu(el->l_next_free_rec); 2239 2240 if (!insert->ins_tree_depth) { 2241 ocfs2_figure_contig_type(inode, insert, el, insert_rec); 2242 ocfs2_figure_appending_type(insert, el, insert_rec); 2243 return 0; 2244 } 2245 2246 path = ocfs2_new_inode_path(di_bh); 2247 if (!path) { 2248 ret = -ENOMEM; 2249 mlog_errno(ret); 2250 goto out; 2251 } 2252 2253 /* 2254 * In the case that we're inserting past what the tree 2255 * currently accounts for, ocfs2_find_path() will return for 2256 * us the rightmost tree path. This is accounted for below in 2257 * the appending code. 2258 */ 2259 ret = ocfs2_find_path(inode, path, le32_to_cpu(insert_rec->e_cpos)); 2260 if (ret) { 2261 mlog_errno(ret); 2262 goto out; 2263 } 2264 2265 el = path_leaf_el(path); 2266 2267 /* 2268 * Now that we have the path, there's two things we want to determine: 2269 * 1) Contiguousness (also set contig_index if this is so) 2270 * 2271 * 2) Are we doing an append? We can trivially break this up 2272 * into two types of appends: simple record append, or a 2273 * rotate inside the tail leaf. 2274 */ 2275 ocfs2_figure_contig_type(inode, insert, el, insert_rec); 2276 2277 /* 2278 * The insert code isn't quite ready to deal with all cases of 2279 * left contiguousness. Specifically, if it's an insert into 2280 * the 1st record in a leaf, it will require the adjustment of 2281 * cluster count on the last record of the path directly to it's 2282 * left. For now, just catch that case and fool the layers 2283 * above us. This works just fine for tree_depth == 0, which 2284 * is why we allow that above. 2285 */ 2286 if (insert->ins_contig == CONTIG_LEFT && 2287 insert->ins_contig_index == 0) 2288 insert->ins_contig = CONTIG_NONE; 2289 2290 /* 2291 * Ok, so we can simply compare against last_eb to figure out 2292 * whether the path doesn't exist. This will only happen in 2293 * the case that we're doing a tail append, so maybe we can 2294 * take advantage of that information somehow. 2295 */ 2296 if (le64_to_cpu(di->i_last_eb_blk) == path_leaf_bh(path)->b_blocknr) { 2297 /* 2298 * Ok, ocfs2_find_path() returned us the rightmost 2299 * tree path. This might be an appending insert. There are 2300 * two cases: 2301 * 1) We're doing a true append at the tail: 2302 * -This might even be off the end of the leaf 2303 * 2) We're "appending" by rotating in the tail 2304 */ 2305 ocfs2_figure_appending_type(insert, el, insert_rec); 2306 } 2307 2308 out: 2309 ocfs2_free_path(path); 2310 2311 if (ret == 0) 2312 *last_eb_bh = bh; 2313 else 2314 brelse(bh); 2315 return ret; 2316 } 2317 2318 /* 2319 * Insert an extent into an inode btree. 2320 * 2321 * The caller needs to update fe->i_clusters 2322 */ 2323 int ocfs2_insert_extent(struct ocfs2_super *osb, 2324 handle_t *handle, 2325 struct inode *inode, 2326 struct buffer_head *fe_bh, 2327 u32 cpos, 2328 u64 start_blk, 2329 u32 new_clusters, 2330 struct ocfs2_alloc_context *meta_ac) 2331 { 2332 int status, shift; 2333 struct buffer_head *last_eb_bh = NULL; 2334 struct buffer_head *bh = NULL; 2335 struct ocfs2_insert_type insert = {0, }; 2336 struct ocfs2_extent_rec rec; 2337 2338 mlog(0, "add %u clusters at position %u to inode %llu\n", 2339 new_clusters, cpos, (unsigned long long)OCFS2_I(inode)->ip_blkno); 2340 2341 mlog_bug_on_msg(!ocfs2_sparse_alloc(osb) && 2342 (OCFS2_I(inode)->ip_clusters != cpos), 2343 "Device %s, asking for sparse allocation: inode %llu, " 2344 "cpos %u, clusters %u\n", 2345 osb->dev_str, 2346 (unsigned long long)OCFS2_I(inode)->ip_blkno, cpos, 2347 OCFS2_I(inode)->ip_clusters); 2348 2349 memset(&rec, 0, sizeof(rec)); 2350 rec.e_cpos = cpu_to_le32(cpos); 2351 rec.e_blkno = cpu_to_le64(start_blk); 2352 rec.e_leaf_clusters = cpu_to_le16(new_clusters); 2353 2354 status = ocfs2_figure_insert_type(inode, fe_bh, &last_eb_bh, &rec, 2355 &insert); 2356 if (status < 0) { 2357 mlog_errno(status); 2358 goto bail; 2359 } 2360 2361 mlog(0, "Insert.appending: %u, Insert.Contig: %u, " 2362 "Insert.contig_index: %d, Insert.free_records: %d, " 2363 "Insert.tree_depth: %d\n", 2364 insert.ins_appending, insert.ins_contig, insert.ins_contig_index, 2365 insert.ins_free_records, insert.ins_tree_depth); 2366 2367 /* 2368 * Avoid growing the tree unless we're out of records and the 2369 * insert type requres one. 2370 */ 2371 if (insert.ins_contig != CONTIG_NONE || insert.ins_free_records) 2372 goto out_add; 2373 2374 shift = ocfs2_find_branch_target(osb, inode, fe_bh, &bh); 2375 if (shift < 0) { 2376 status = shift; 2377 mlog_errno(status); 2378 goto bail; 2379 } 2380 2381 /* We traveled all the way to the bottom of the allocation tree 2382 * and didn't find room for any more extents - we need to add 2383 * another tree level */ 2384 if (shift) { 2385 BUG_ON(bh); 2386 mlog(0, "need to shift tree depth " 2387 "(current = %d)\n", insert.ins_tree_depth); 2388 2389 /* ocfs2_shift_tree_depth will return us a buffer with 2390 * the new extent block (so we can pass that to 2391 * ocfs2_add_branch). */ 2392 status = ocfs2_shift_tree_depth(osb, handle, inode, fe_bh, 2393 meta_ac, &bh); 2394 if (status < 0) { 2395 mlog_errno(status); 2396 goto bail; 2397 } 2398 insert.ins_tree_depth++; 2399 /* Special case: we have room now if we shifted from 2400 * tree_depth 0 */ 2401 if (insert.ins_tree_depth == 1) 2402 goto out_add; 2403 } 2404 2405 /* call ocfs2_add_branch to add the final part of the tree with 2406 * the new data. */ 2407 mlog(0, "add branch. bh = %p\n", bh); 2408 status = ocfs2_add_branch(osb, handle, inode, fe_bh, bh, last_eb_bh, 2409 meta_ac); 2410 if (status < 0) { 2411 mlog_errno(status); 2412 goto bail; 2413 } 2414 2415 out_add: 2416 /* Finally, we can add clusters. This might rotate the tree for us. */ 2417 status = ocfs2_do_insert_extent(inode, handle, fe_bh, &rec, &insert); 2418 if (status < 0) 2419 mlog_errno(status); 2420 else 2421 ocfs2_extent_map_insert_rec(inode, &rec); 2422 2423 bail: 2424 if (bh) 2425 brelse(bh); 2426 2427 if (last_eb_bh) 2428 brelse(last_eb_bh); 2429 2430 mlog_exit(status); 2431 return status; 2432 } 2433 2434 static inline int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb) 2435 { 2436 struct buffer_head *tl_bh = osb->osb_tl_bh; 2437 struct ocfs2_dinode *di; 2438 struct ocfs2_truncate_log *tl; 2439 2440 di = (struct ocfs2_dinode *) tl_bh->b_data; 2441 tl = &di->id2.i_dealloc; 2442 2443 mlog_bug_on_msg(le16_to_cpu(tl->tl_used) > le16_to_cpu(tl->tl_count), 2444 "slot %d, invalid truncate log parameters: used = " 2445 "%u, count = %u\n", osb->slot_num, 2446 le16_to_cpu(tl->tl_used), le16_to_cpu(tl->tl_count)); 2447 return le16_to_cpu(tl->tl_used) == le16_to_cpu(tl->tl_count); 2448 } 2449 2450 static int ocfs2_truncate_log_can_coalesce(struct ocfs2_truncate_log *tl, 2451 unsigned int new_start) 2452 { 2453 unsigned int tail_index; 2454 unsigned int current_tail; 2455 2456 /* No records, nothing to coalesce */ 2457 if (!le16_to_cpu(tl->tl_used)) 2458 return 0; 2459 2460 tail_index = le16_to_cpu(tl->tl_used) - 1; 2461 current_tail = le32_to_cpu(tl->tl_recs[tail_index].t_start); 2462 current_tail += le32_to_cpu(tl->tl_recs[tail_index].t_clusters); 2463 2464 return current_tail == new_start; 2465 } 2466 2467 static int ocfs2_truncate_log_append(struct ocfs2_super *osb, 2468 handle_t *handle, 2469 u64 start_blk, 2470 unsigned int num_clusters) 2471 { 2472 int status, index; 2473 unsigned int start_cluster, tl_count; 2474 struct inode *tl_inode = osb->osb_tl_inode; 2475 struct buffer_head *tl_bh = osb->osb_tl_bh; 2476 struct ocfs2_dinode *di; 2477 struct ocfs2_truncate_log *tl; 2478 2479 mlog_entry("start_blk = %llu, num_clusters = %u\n", 2480 (unsigned long long)start_blk, num_clusters); 2481 2482 BUG_ON(mutex_trylock(&tl_inode->i_mutex)); 2483 2484 start_cluster = ocfs2_blocks_to_clusters(osb->sb, start_blk); 2485 2486 di = (struct ocfs2_dinode *) tl_bh->b_data; 2487 tl = &di->id2.i_dealloc; 2488 if (!OCFS2_IS_VALID_DINODE(di)) { 2489 OCFS2_RO_ON_INVALID_DINODE(osb->sb, di); 2490 status = -EIO; 2491 goto bail; 2492 } 2493 2494 tl_count = le16_to_cpu(tl->tl_count); 2495 mlog_bug_on_msg(tl_count > ocfs2_truncate_recs_per_inode(osb->sb) || 2496 tl_count == 0, 2497 "Truncate record count on #%llu invalid " 2498 "wanted %u, actual %u\n", 2499 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, 2500 ocfs2_truncate_recs_per_inode(osb->sb), 2501 le16_to_cpu(tl->tl_count)); 2502 2503 /* Caller should have known to flush before calling us. */ 2504 index = le16_to_cpu(tl->tl_used); 2505 if (index >= tl_count) { 2506 status = -ENOSPC; 2507 mlog_errno(status); 2508 goto bail; 2509 } 2510 2511 status = ocfs2_journal_access(handle, tl_inode, tl_bh, 2512 OCFS2_JOURNAL_ACCESS_WRITE); 2513 if (status < 0) { 2514 mlog_errno(status); 2515 goto bail; 2516 } 2517 2518 mlog(0, "Log truncate of %u clusters starting at cluster %u to " 2519 "%llu (index = %d)\n", num_clusters, start_cluster, 2520 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, index); 2521 2522 if (ocfs2_truncate_log_can_coalesce(tl, start_cluster)) { 2523 /* 2524 * Move index back to the record we are coalescing with. 2525 * ocfs2_truncate_log_can_coalesce() guarantees nonzero 2526 */ 2527 index--; 2528 2529 num_clusters += le32_to_cpu(tl->tl_recs[index].t_clusters); 2530 mlog(0, "Coalesce with index %u (start = %u, clusters = %u)\n", 2531 index, le32_to_cpu(tl->tl_recs[index].t_start), 2532 num_clusters); 2533 } else { 2534 tl->tl_recs[index].t_start = cpu_to_le32(start_cluster); 2535 tl->tl_used = cpu_to_le16(index + 1); 2536 } 2537 tl->tl_recs[index].t_clusters = cpu_to_le32(num_clusters); 2538 2539 status = ocfs2_journal_dirty(handle, tl_bh); 2540 if (status < 0) { 2541 mlog_errno(status); 2542 goto bail; 2543 } 2544 2545 bail: 2546 mlog_exit(status); 2547 return status; 2548 } 2549 2550 static int ocfs2_replay_truncate_records(struct ocfs2_super *osb, 2551 handle_t *handle, 2552 struct inode *data_alloc_inode, 2553 struct buffer_head *data_alloc_bh) 2554 { 2555 int status = 0; 2556 int i; 2557 unsigned int num_clusters; 2558 u64 start_blk; 2559 struct ocfs2_truncate_rec rec; 2560 struct ocfs2_dinode *di; 2561 struct ocfs2_truncate_log *tl; 2562 struct inode *tl_inode = osb->osb_tl_inode; 2563 struct buffer_head *tl_bh = osb->osb_tl_bh; 2564 2565 mlog_entry_void(); 2566 2567 di = (struct ocfs2_dinode *) tl_bh->b_data; 2568 tl = &di->id2.i_dealloc; 2569 i = le16_to_cpu(tl->tl_used) - 1; 2570 while (i >= 0) { 2571 /* Caller has given us at least enough credits to 2572 * update the truncate log dinode */ 2573 status = ocfs2_journal_access(handle, tl_inode, tl_bh, 2574 OCFS2_JOURNAL_ACCESS_WRITE); 2575 if (status < 0) { 2576 mlog_errno(status); 2577 goto bail; 2578 } 2579 2580 tl->tl_used = cpu_to_le16(i); 2581 2582 status = ocfs2_journal_dirty(handle, tl_bh); 2583 if (status < 0) { 2584 mlog_errno(status); 2585 goto bail; 2586 } 2587 2588 /* TODO: Perhaps we can calculate the bulk of the 2589 * credits up front rather than extending like 2590 * this. */ 2591 status = ocfs2_extend_trans(handle, 2592 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC); 2593 if (status < 0) { 2594 mlog_errno(status); 2595 goto bail; 2596 } 2597 2598 rec = tl->tl_recs[i]; 2599 start_blk = ocfs2_clusters_to_blocks(data_alloc_inode->i_sb, 2600 le32_to_cpu(rec.t_start)); 2601 num_clusters = le32_to_cpu(rec.t_clusters); 2602 2603 /* if start_blk is not set, we ignore the record as 2604 * invalid. */ 2605 if (start_blk) { 2606 mlog(0, "free record %d, start = %u, clusters = %u\n", 2607 i, le32_to_cpu(rec.t_start), num_clusters); 2608 2609 status = ocfs2_free_clusters(handle, data_alloc_inode, 2610 data_alloc_bh, start_blk, 2611 num_clusters); 2612 if (status < 0) { 2613 mlog_errno(status); 2614 goto bail; 2615 } 2616 } 2617 i--; 2618 } 2619 2620 bail: 2621 mlog_exit(status); 2622 return status; 2623 } 2624 2625 /* Expects you to already be holding tl_inode->i_mutex */ 2626 static int __ocfs2_flush_truncate_log(struct ocfs2_super *osb) 2627 { 2628 int status; 2629 unsigned int num_to_flush; 2630 handle_t *handle; 2631 struct inode *tl_inode = osb->osb_tl_inode; 2632 struct inode *data_alloc_inode = NULL; 2633 struct buffer_head *tl_bh = osb->osb_tl_bh; 2634 struct buffer_head *data_alloc_bh = NULL; 2635 struct ocfs2_dinode *di; 2636 struct ocfs2_truncate_log *tl; 2637 2638 mlog_entry_void(); 2639 2640 BUG_ON(mutex_trylock(&tl_inode->i_mutex)); 2641 2642 di = (struct ocfs2_dinode *) tl_bh->b_data; 2643 tl = &di->id2.i_dealloc; 2644 if (!OCFS2_IS_VALID_DINODE(di)) { 2645 OCFS2_RO_ON_INVALID_DINODE(osb->sb, di); 2646 status = -EIO; 2647 goto out; 2648 } 2649 2650 num_to_flush = le16_to_cpu(tl->tl_used); 2651 mlog(0, "Flush %u records from truncate log #%llu\n", 2652 num_to_flush, (unsigned long long)OCFS2_I(tl_inode)->ip_blkno); 2653 if (!num_to_flush) { 2654 status = 0; 2655 goto out; 2656 } 2657 2658 data_alloc_inode = ocfs2_get_system_file_inode(osb, 2659 GLOBAL_BITMAP_SYSTEM_INODE, 2660 OCFS2_INVALID_SLOT); 2661 if (!data_alloc_inode) { 2662 status = -EINVAL; 2663 mlog(ML_ERROR, "Could not get bitmap inode!\n"); 2664 goto out; 2665 } 2666 2667 mutex_lock(&data_alloc_inode->i_mutex); 2668 2669 status = ocfs2_meta_lock(data_alloc_inode, &data_alloc_bh, 1); 2670 if (status < 0) { 2671 mlog_errno(status); 2672 goto out_mutex; 2673 } 2674 2675 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE); 2676 if (IS_ERR(handle)) { 2677 status = PTR_ERR(handle); 2678 mlog_errno(status); 2679 goto out_unlock; 2680 } 2681 2682 status = ocfs2_replay_truncate_records(osb, handle, data_alloc_inode, 2683 data_alloc_bh); 2684 if (status < 0) 2685 mlog_errno(status); 2686 2687 ocfs2_commit_trans(osb, handle); 2688 2689 out_unlock: 2690 brelse(data_alloc_bh); 2691 ocfs2_meta_unlock(data_alloc_inode, 1); 2692 2693 out_mutex: 2694 mutex_unlock(&data_alloc_inode->i_mutex); 2695 iput(data_alloc_inode); 2696 2697 out: 2698 mlog_exit(status); 2699 return status; 2700 } 2701 2702 int ocfs2_flush_truncate_log(struct ocfs2_super *osb) 2703 { 2704 int status; 2705 struct inode *tl_inode = osb->osb_tl_inode; 2706 2707 mutex_lock(&tl_inode->i_mutex); 2708 status = __ocfs2_flush_truncate_log(osb); 2709 mutex_unlock(&tl_inode->i_mutex); 2710 2711 return status; 2712 } 2713 2714 static void ocfs2_truncate_log_worker(struct work_struct *work) 2715 { 2716 int status; 2717 struct ocfs2_super *osb = 2718 container_of(work, struct ocfs2_super, 2719 osb_truncate_log_wq.work); 2720 2721 mlog_entry_void(); 2722 2723 status = ocfs2_flush_truncate_log(osb); 2724 if (status < 0) 2725 mlog_errno(status); 2726 2727 mlog_exit(status); 2728 } 2729 2730 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ) 2731 void ocfs2_schedule_truncate_log_flush(struct ocfs2_super *osb, 2732 int cancel) 2733 { 2734 if (osb->osb_tl_inode) { 2735 /* We want to push off log flushes while truncates are 2736 * still running. */ 2737 if (cancel) 2738 cancel_delayed_work(&osb->osb_truncate_log_wq); 2739 2740 queue_delayed_work(ocfs2_wq, &osb->osb_truncate_log_wq, 2741 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL); 2742 } 2743 } 2744 2745 static int ocfs2_get_truncate_log_info(struct ocfs2_super *osb, 2746 int slot_num, 2747 struct inode **tl_inode, 2748 struct buffer_head **tl_bh) 2749 { 2750 int status; 2751 struct inode *inode = NULL; 2752 struct buffer_head *bh = NULL; 2753 2754 inode = ocfs2_get_system_file_inode(osb, 2755 TRUNCATE_LOG_SYSTEM_INODE, 2756 slot_num); 2757 if (!inode) { 2758 status = -EINVAL; 2759 mlog(ML_ERROR, "Could not get load truncate log inode!\n"); 2760 goto bail; 2761 } 2762 2763 status = ocfs2_read_block(osb, OCFS2_I(inode)->ip_blkno, &bh, 2764 OCFS2_BH_CACHED, inode); 2765 if (status < 0) { 2766 iput(inode); 2767 mlog_errno(status); 2768 goto bail; 2769 } 2770 2771 *tl_inode = inode; 2772 *tl_bh = bh; 2773 bail: 2774 mlog_exit(status); 2775 return status; 2776 } 2777 2778 /* called during the 1st stage of node recovery. we stamp a clean 2779 * truncate log and pass back a copy for processing later. if the 2780 * truncate log does not require processing, a *tl_copy is set to 2781 * NULL. */ 2782 int ocfs2_begin_truncate_log_recovery(struct ocfs2_super *osb, 2783 int slot_num, 2784 struct ocfs2_dinode **tl_copy) 2785 { 2786 int status; 2787 struct inode *tl_inode = NULL; 2788 struct buffer_head *tl_bh = NULL; 2789 struct ocfs2_dinode *di; 2790 struct ocfs2_truncate_log *tl; 2791 2792 *tl_copy = NULL; 2793 2794 mlog(0, "recover truncate log from slot %d\n", slot_num); 2795 2796 status = ocfs2_get_truncate_log_info(osb, slot_num, &tl_inode, &tl_bh); 2797 if (status < 0) { 2798 mlog_errno(status); 2799 goto bail; 2800 } 2801 2802 di = (struct ocfs2_dinode *) tl_bh->b_data; 2803 tl = &di->id2.i_dealloc; 2804 if (!OCFS2_IS_VALID_DINODE(di)) { 2805 OCFS2_RO_ON_INVALID_DINODE(tl_inode->i_sb, di); 2806 status = -EIO; 2807 goto bail; 2808 } 2809 2810 if (le16_to_cpu(tl->tl_used)) { 2811 mlog(0, "We'll have %u logs to recover\n", 2812 le16_to_cpu(tl->tl_used)); 2813 2814 *tl_copy = kmalloc(tl_bh->b_size, GFP_KERNEL); 2815 if (!(*tl_copy)) { 2816 status = -ENOMEM; 2817 mlog_errno(status); 2818 goto bail; 2819 } 2820 2821 /* Assuming the write-out below goes well, this copy 2822 * will be passed back to recovery for processing. */ 2823 memcpy(*tl_copy, tl_bh->b_data, tl_bh->b_size); 2824 2825 /* All we need to do to clear the truncate log is set 2826 * tl_used. */ 2827 tl->tl_used = 0; 2828 2829 status = ocfs2_write_block(osb, tl_bh, tl_inode); 2830 if (status < 0) { 2831 mlog_errno(status); 2832 goto bail; 2833 } 2834 } 2835 2836 bail: 2837 if (tl_inode) 2838 iput(tl_inode); 2839 if (tl_bh) 2840 brelse(tl_bh); 2841 2842 if (status < 0 && (*tl_copy)) { 2843 kfree(*tl_copy); 2844 *tl_copy = NULL; 2845 } 2846 2847 mlog_exit(status); 2848 return status; 2849 } 2850 2851 int ocfs2_complete_truncate_log_recovery(struct ocfs2_super *osb, 2852 struct ocfs2_dinode *tl_copy) 2853 { 2854 int status = 0; 2855 int i; 2856 unsigned int clusters, num_recs, start_cluster; 2857 u64 start_blk; 2858 handle_t *handle; 2859 struct inode *tl_inode = osb->osb_tl_inode; 2860 struct ocfs2_truncate_log *tl; 2861 2862 mlog_entry_void(); 2863 2864 if (OCFS2_I(tl_inode)->ip_blkno == le64_to_cpu(tl_copy->i_blkno)) { 2865 mlog(ML_ERROR, "Asked to recover my own truncate log!\n"); 2866 return -EINVAL; 2867 } 2868 2869 tl = &tl_copy->id2.i_dealloc; 2870 num_recs = le16_to_cpu(tl->tl_used); 2871 mlog(0, "cleanup %u records from %llu\n", num_recs, 2872 (unsigned long long)le64_to_cpu(tl_copy->i_blkno)); 2873 2874 mutex_lock(&tl_inode->i_mutex); 2875 for(i = 0; i < num_recs; i++) { 2876 if (ocfs2_truncate_log_needs_flush(osb)) { 2877 status = __ocfs2_flush_truncate_log(osb); 2878 if (status < 0) { 2879 mlog_errno(status); 2880 goto bail_up; 2881 } 2882 } 2883 2884 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE); 2885 if (IS_ERR(handle)) { 2886 status = PTR_ERR(handle); 2887 mlog_errno(status); 2888 goto bail_up; 2889 } 2890 2891 clusters = le32_to_cpu(tl->tl_recs[i].t_clusters); 2892 start_cluster = le32_to_cpu(tl->tl_recs[i].t_start); 2893 start_blk = ocfs2_clusters_to_blocks(osb->sb, start_cluster); 2894 2895 status = ocfs2_truncate_log_append(osb, handle, 2896 start_blk, clusters); 2897 ocfs2_commit_trans(osb, handle); 2898 if (status < 0) { 2899 mlog_errno(status); 2900 goto bail_up; 2901 } 2902 } 2903 2904 bail_up: 2905 mutex_unlock(&tl_inode->i_mutex); 2906 2907 mlog_exit(status); 2908 return status; 2909 } 2910 2911 void ocfs2_truncate_log_shutdown(struct ocfs2_super *osb) 2912 { 2913 int status; 2914 struct inode *tl_inode = osb->osb_tl_inode; 2915 2916 mlog_entry_void(); 2917 2918 if (tl_inode) { 2919 cancel_delayed_work(&osb->osb_truncate_log_wq); 2920 flush_workqueue(ocfs2_wq); 2921 2922 status = ocfs2_flush_truncate_log(osb); 2923 if (status < 0) 2924 mlog_errno(status); 2925 2926 brelse(osb->osb_tl_bh); 2927 iput(osb->osb_tl_inode); 2928 } 2929 2930 mlog_exit_void(); 2931 } 2932 2933 int ocfs2_truncate_log_init(struct ocfs2_super *osb) 2934 { 2935 int status; 2936 struct inode *tl_inode = NULL; 2937 struct buffer_head *tl_bh = NULL; 2938 2939 mlog_entry_void(); 2940 2941 status = ocfs2_get_truncate_log_info(osb, 2942 osb->slot_num, 2943 &tl_inode, 2944 &tl_bh); 2945 if (status < 0) 2946 mlog_errno(status); 2947 2948 /* ocfs2_truncate_log_shutdown keys on the existence of 2949 * osb->osb_tl_inode so we don't set any of the osb variables 2950 * until we're sure all is well. */ 2951 INIT_DELAYED_WORK(&osb->osb_truncate_log_wq, 2952 ocfs2_truncate_log_worker); 2953 osb->osb_tl_bh = tl_bh; 2954 osb->osb_tl_inode = tl_inode; 2955 2956 mlog_exit(status); 2957 return status; 2958 } 2959 2960 /* This function will figure out whether the currently last extent 2961 * block will be deleted, and if it will, what the new last extent 2962 * block will be so we can update his h_next_leaf_blk field, as well 2963 * as the dinodes i_last_eb_blk */ 2964 static int ocfs2_find_new_last_ext_blk(struct inode *inode, 2965 unsigned int clusters_to_del, 2966 struct ocfs2_path *path, 2967 struct buffer_head **new_last_eb) 2968 { 2969 int next_free, ret = 0; 2970 u32 cpos; 2971 struct ocfs2_extent_rec *rec; 2972 struct ocfs2_extent_block *eb; 2973 struct ocfs2_extent_list *el; 2974 struct buffer_head *bh = NULL; 2975 2976 *new_last_eb = NULL; 2977 2978 /* we have no tree, so of course, no last_eb. */ 2979 if (!path->p_tree_depth) 2980 goto out; 2981 2982 /* trunc to zero special case - this makes tree_depth = 0 2983 * regardless of what it is. */ 2984 if (OCFS2_I(inode)->ip_clusters == clusters_to_del) 2985 goto out; 2986 2987 el = path_leaf_el(path); 2988 BUG_ON(!el->l_next_free_rec); 2989 2990 /* 2991 * Make sure that this extent list will actually be empty 2992 * after we clear away the data. We can shortcut out if 2993 * there's more than one non-empty extent in the 2994 * list. Otherwise, a check of the remaining extent is 2995 * necessary. 2996 */ 2997 next_free = le16_to_cpu(el->l_next_free_rec); 2998 rec = NULL; 2999 if (ocfs2_is_empty_extent(&el->l_recs[0])) { 3000 if (next_free > 2) 3001 goto out; 3002 3003 /* We may have a valid extent in index 1, check it. */ 3004 if (next_free == 2) 3005 rec = &el->l_recs[1]; 3006 3007 /* 3008 * Fall through - no more nonempty extents, so we want 3009 * to delete this leaf. 3010 */ 3011 } else { 3012 if (next_free > 1) 3013 goto out; 3014 3015 rec = &el->l_recs[0]; 3016 } 3017 3018 if (rec) { 3019 /* 3020 * Check it we'll only be trimming off the end of this 3021 * cluster. 3022 */ 3023 if (le16_to_cpu(rec->e_leaf_clusters) > clusters_to_del) 3024 goto out; 3025 } 3026 3027 ret = ocfs2_find_cpos_for_left_leaf(inode->i_sb, path, &cpos); 3028 if (ret) { 3029 mlog_errno(ret); 3030 goto out; 3031 } 3032 3033 ret = ocfs2_find_leaf(inode, path_root_el(path), cpos, &bh); 3034 if (ret) { 3035 mlog_errno(ret); 3036 goto out; 3037 } 3038 3039 eb = (struct ocfs2_extent_block *) bh->b_data; 3040 el = &eb->h_list; 3041 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 3042 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); 3043 ret = -EROFS; 3044 goto out; 3045 } 3046 3047 *new_last_eb = bh; 3048 get_bh(*new_last_eb); 3049 mlog(0, "returning block %llu, (cpos: %u)\n", 3050 (unsigned long long)le64_to_cpu(eb->h_blkno), cpos); 3051 out: 3052 brelse(bh); 3053 3054 return ret; 3055 } 3056 3057 /* 3058 * Trim some clusters off the rightmost edge of a tree. Only called 3059 * during truncate. 3060 * 3061 * The caller needs to: 3062 * - start journaling of each path component. 3063 * - compute and fully set up any new last ext block 3064 */ 3065 static int ocfs2_trim_tree(struct inode *inode, struct ocfs2_path *path, 3066 handle_t *handle, struct ocfs2_truncate_context *tc, 3067 u32 clusters_to_del, u64 *delete_start) 3068 { 3069 int ret, i, index = path->p_tree_depth; 3070 u32 new_edge = 0; 3071 u64 deleted_eb = 0; 3072 struct buffer_head *bh; 3073 struct ocfs2_extent_list *el; 3074 struct ocfs2_extent_rec *rec; 3075 3076 *delete_start = 0; 3077 3078 while (index >= 0) { 3079 bh = path->p_node[index].bh; 3080 el = path->p_node[index].el; 3081 3082 mlog(0, "traveling tree (index = %d, block = %llu)\n", 3083 index, (unsigned long long)bh->b_blocknr); 3084 3085 BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0); 3086 3087 if (index != 3088 (path->p_tree_depth - le16_to_cpu(el->l_tree_depth))) { 3089 ocfs2_error(inode->i_sb, 3090 "Inode %lu has invalid ext. block %llu", 3091 inode->i_ino, 3092 (unsigned long long)bh->b_blocknr); 3093 ret = -EROFS; 3094 goto out; 3095 } 3096 3097 find_tail_record: 3098 i = le16_to_cpu(el->l_next_free_rec) - 1; 3099 rec = &el->l_recs[i]; 3100 3101 mlog(0, "Extent list before: record %d: (%u, %u, %llu), " 3102 "next = %u\n", i, le32_to_cpu(rec->e_cpos), 3103 ocfs2_rec_clusters(el, rec), 3104 (unsigned long long)le64_to_cpu(rec->e_blkno), 3105 le16_to_cpu(el->l_next_free_rec)); 3106 3107 BUG_ON(ocfs2_rec_clusters(el, rec) < clusters_to_del); 3108 3109 if (le16_to_cpu(el->l_tree_depth) == 0) { 3110 /* 3111 * If the leaf block contains a single empty 3112 * extent and no records, we can just remove 3113 * the block. 3114 */ 3115 if (i == 0 && ocfs2_is_empty_extent(rec)) { 3116 memset(rec, 0, 3117 sizeof(struct ocfs2_extent_rec)); 3118 el->l_next_free_rec = cpu_to_le16(0); 3119 3120 goto delete; 3121 } 3122 3123 /* 3124 * Remove any empty extents by shifting things 3125 * left. That should make life much easier on 3126 * the code below. This condition is rare 3127 * enough that we shouldn't see a performance 3128 * hit. 3129 */ 3130 if (ocfs2_is_empty_extent(&el->l_recs[0])) { 3131 le16_add_cpu(&el->l_next_free_rec, -1); 3132 3133 for(i = 0; 3134 i < le16_to_cpu(el->l_next_free_rec); i++) 3135 el->l_recs[i] = el->l_recs[i + 1]; 3136 3137 memset(&el->l_recs[i], 0, 3138 sizeof(struct ocfs2_extent_rec)); 3139 3140 /* 3141 * We've modified our extent list. The 3142 * simplest way to handle this change 3143 * is to being the search from the 3144 * start again. 3145 */ 3146 goto find_tail_record; 3147 } 3148 3149 le16_add_cpu(&rec->e_leaf_clusters, -clusters_to_del); 3150 3151 /* 3152 * We'll use "new_edge" on our way back up the 3153 * tree to know what our rightmost cpos is. 3154 */ 3155 new_edge = le16_to_cpu(rec->e_leaf_clusters); 3156 new_edge += le32_to_cpu(rec->e_cpos); 3157 3158 /* 3159 * The caller will use this to delete data blocks. 3160 */ 3161 *delete_start = le64_to_cpu(rec->e_blkno) 3162 + ocfs2_clusters_to_blocks(inode->i_sb, 3163 le16_to_cpu(rec->e_leaf_clusters)); 3164 3165 /* 3166 * If it's now empty, remove this record. 3167 */ 3168 if (le16_to_cpu(rec->e_leaf_clusters) == 0) { 3169 memset(rec, 0, 3170 sizeof(struct ocfs2_extent_rec)); 3171 le16_add_cpu(&el->l_next_free_rec, -1); 3172 } 3173 } else { 3174 if (le64_to_cpu(rec->e_blkno) == deleted_eb) { 3175 memset(rec, 0, 3176 sizeof(struct ocfs2_extent_rec)); 3177 le16_add_cpu(&el->l_next_free_rec, -1); 3178 3179 goto delete; 3180 } 3181 3182 /* Can this actually happen? */ 3183 if (le16_to_cpu(el->l_next_free_rec) == 0) 3184 goto delete; 3185 3186 /* 3187 * We never actually deleted any clusters 3188 * because our leaf was empty. There's no 3189 * reason to adjust the rightmost edge then. 3190 */ 3191 if (new_edge == 0) 3192 goto delete; 3193 3194 rec->e_int_clusters = cpu_to_le32(new_edge); 3195 le32_add_cpu(&rec->e_int_clusters, 3196 -le32_to_cpu(rec->e_cpos)); 3197 3198 /* 3199 * A deleted child record should have been 3200 * caught above. 3201 */ 3202 BUG_ON(le32_to_cpu(rec->e_int_clusters) == 0); 3203 } 3204 3205 delete: 3206 ret = ocfs2_journal_dirty(handle, bh); 3207 if (ret) { 3208 mlog_errno(ret); 3209 goto out; 3210 } 3211 3212 mlog(0, "extent list container %llu, after: record %d: " 3213 "(%u, %u, %llu), next = %u.\n", 3214 (unsigned long long)bh->b_blocknr, i, 3215 le32_to_cpu(rec->e_cpos), ocfs2_rec_clusters(el, rec), 3216 (unsigned long long)le64_to_cpu(rec->e_blkno), 3217 le16_to_cpu(el->l_next_free_rec)); 3218 3219 /* 3220 * We must be careful to only attempt delete of an 3221 * extent block (and not the root inode block). 3222 */ 3223 if (index > 0 && le16_to_cpu(el->l_next_free_rec) == 0) { 3224 struct ocfs2_extent_block *eb = 3225 (struct ocfs2_extent_block *)bh->b_data; 3226 3227 /* 3228 * Save this for use when processing the 3229 * parent block. 3230 */ 3231 deleted_eb = le64_to_cpu(eb->h_blkno); 3232 3233 mlog(0, "deleting this extent block.\n"); 3234 3235 ocfs2_remove_from_cache(inode, bh); 3236 3237 BUG_ON(ocfs2_rec_clusters(el, &el->l_recs[0])); 3238 BUG_ON(le32_to_cpu(el->l_recs[0].e_cpos)); 3239 BUG_ON(le64_to_cpu(el->l_recs[0].e_blkno)); 3240 3241 if (le16_to_cpu(eb->h_suballoc_slot) == 0) { 3242 /* 3243 * This code only understands how to 3244 * lock the suballocator in slot 0, 3245 * which is fine because allocation is 3246 * only ever done out of that 3247 * suballocator too. A future version 3248 * might change that however, so avoid 3249 * a free if we don't know how to 3250 * handle it. This way an fs incompat 3251 * bit will not be necessary. 3252 */ 3253 ret = ocfs2_free_extent_block(handle, 3254 tc->tc_ext_alloc_inode, 3255 tc->tc_ext_alloc_bh, 3256 eb); 3257 3258 /* An error here is not fatal. */ 3259 if (ret < 0) 3260 mlog_errno(ret); 3261 } 3262 } else { 3263 deleted_eb = 0; 3264 } 3265 3266 index--; 3267 } 3268 3269 ret = 0; 3270 out: 3271 return ret; 3272 } 3273 3274 static int ocfs2_do_truncate(struct ocfs2_super *osb, 3275 unsigned int clusters_to_del, 3276 struct inode *inode, 3277 struct buffer_head *fe_bh, 3278 handle_t *handle, 3279 struct ocfs2_truncate_context *tc, 3280 struct ocfs2_path *path) 3281 { 3282 int status; 3283 struct ocfs2_dinode *fe; 3284 struct ocfs2_extent_block *last_eb = NULL; 3285 struct ocfs2_extent_list *el; 3286 struct buffer_head *last_eb_bh = NULL; 3287 u64 delete_blk = 0; 3288 3289 fe = (struct ocfs2_dinode *) fe_bh->b_data; 3290 3291 status = ocfs2_find_new_last_ext_blk(inode, clusters_to_del, 3292 path, &last_eb_bh); 3293 if (status < 0) { 3294 mlog_errno(status); 3295 goto bail; 3296 } 3297 3298 /* 3299 * Each component will be touched, so we might as well journal 3300 * here to avoid having to handle errors later. 3301 */ 3302 status = ocfs2_journal_access_path(inode, handle, path); 3303 if (status < 0) { 3304 mlog_errno(status); 3305 goto bail; 3306 } 3307 3308 if (last_eb_bh) { 3309 status = ocfs2_journal_access(handle, inode, last_eb_bh, 3310 OCFS2_JOURNAL_ACCESS_WRITE); 3311 if (status < 0) { 3312 mlog_errno(status); 3313 goto bail; 3314 } 3315 3316 last_eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; 3317 } 3318 3319 el = &(fe->id2.i_list); 3320 3321 /* 3322 * Lower levels depend on this never happening, but it's best 3323 * to check it up here before changing the tree. 3324 */ 3325 if (el->l_tree_depth && el->l_recs[0].e_int_clusters == 0) { 3326 ocfs2_error(inode->i_sb, 3327 "Inode %lu has an empty extent record, depth %u\n", 3328 inode->i_ino, le16_to_cpu(el->l_tree_depth)); 3329 status = -EROFS; 3330 goto bail; 3331 } 3332 3333 spin_lock(&OCFS2_I(inode)->ip_lock); 3334 OCFS2_I(inode)->ip_clusters = le32_to_cpu(fe->i_clusters) - 3335 clusters_to_del; 3336 spin_unlock(&OCFS2_I(inode)->ip_lock); 3337 le32_add_cpu(&fe->i_clusters, -clusters_to_del); 3338 3339 status = ocfs2_trim_tree(inode, path, handle, tc, 3340 clusters_to_del, &delete_blk); 3341 if (status) { 3342 mlog_errno(status); 3343 goto bail; 3344 } 3345 3346 if (le32_to_cpu(fe->i_clusters) == 0) { 3347 /* trunc to zero is a special case. */ 3348 el->l_tree_depth = 0; 3349 fe->i_last_eb_blk = 0; 3350 } else if (last_eb) 3351 fe->i_last_eb_blk = last_eb->h_blkno; 3352 3353 status = ocfs2_journal_dirty(handle, fe_bh); 3354 if (status < 0) { 3355 mlog_errno(status); 3356 goto bail; 3357 } 3358 3359 if (last_eb) { 3360 /* If there will be a new last extent block, then by 3361 * definition, there cannot be any leaves to the right of 3362 * him. */ 3363 last_eb->h_next_leaf_blk = 0; 3364 status = ocfs2_journal_dirty(handle, last_eb_bh); 3365 if (status < 0) { 3366 mlog_errno(status); 3367 goto bail; 3368 } 3369 } 3370 3371 if (delete_blk) { 3372 status = ocfs2_truncate_log_append(osb, handle, delete_blk, 3373 clusters_to_del); 3374 if (status < 0) { 3375 mlog_errno(status); 3376 goto bail; 3377 } 3378 } 3379 status = 0; 3380 bail: 3381 3382 mlog_exit(status); 3383 return status; 3384 } 3385 3386 static int ocfs2_writeback_zero_func(handle_t *handle, struct buffer_head *bh) 3387 { 3388 set_buffer_uptodate(bh); 3389 mark_buffer_dirty(bh); 3390 return 0; 3391 } 3392 3393 static int ocfs2_ordered_zero_func(handle_t *handle, struct buffer_head *bh) 3394 { 3395 set_buffer_uptodate(bh); 3396 mark_buffer_dirty(bh); 3397 return ocfs2_journal_dirty_data(handle, bh); 3398 } 3399 3400 static void ocfs2_zero_cluster_pages(struct inode *inode, loff_t isize, 3401 struct page **pages, int numpages, 3402 u64 phys, handle_t *handle) 3403 { 3404 int i, ret, partial = 0; 3405 void *kaddr; 3406 struct page *page; 3407 unsigned int from, to = PAGE_CACHE_SIZE; 3408 struct super_block *sb = inode->i_sb; 3409 3410 BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb))); 3411 3412 if (numpages == 0) 3413 goto out; 3414 3415 from = isize & (PAGE_CACHE_SIZE - 1); /* 1st page offset */ 3416 if (PAGE_CACHE_SHIFT > OCFS2_SB(sb)->s_clustersize_bits) { 3417 /* 3418 * Since 'from' has been capped to a value below page 3419 * size, this calculation won't be able to overflow 3420 * 'to' 3421 */ 3422 to = ocfs2_align_bytes_to_clusters(sb, from); 3423 3424 /* 3425 * The truncate tail in this case should never contain 3426 * more than one page at maximum. The loop below also 3427 * assumes this. 3428 */ 3429 BUG_ON(numpages != 1); 3430 } 3431 3432 for(i = 0; i < numpages; i++) { 3433 page = pages[i]; 3434 3435 BUG_ON(from > PAGE_CACHE_SIZE); 3436 BUG_ON(to > PAGE_CACHE_SIZE); 3437 3438 ret = ocfs2_map_page_blocks(page, &phys, inode, from, to, 0); 3439 if (ret) 3440 mlog_errno(ret); 3441 3442 kaddr = kmap_atomic(page, KM_USER0); 3443 memset(kaddr + from, 0, to - from); 3444 kunmap_atomic(kaddr, KM_USER0); 3445 3446 /* 3447 * Need to set the buffers we zero'd into uptodate 3448 * here if they aren't - ocfs2_map_page_blocks() 3449 * might've skipped some 3450 */ 3451 if (ocfs2_should_order_data(inode)) { 3452 ret = walk_page_buffers(handle, 3453 page_buffers(page), 3454 from, to, &partial, 3455 ocfs2_ordered_zero_func); 3456 if (ret < 0) 3457 mlog_errno(ret); 3458 } else { 3459 ret = walk_page_buffers(handle, page_buffers(page), 3460 from, to, &partial, 3461 ocfs2_writeback_zero_func); 3462 if (ret < 0) 3463 mlog_errno(ret); 3464 } 3465 3466 if (!partial) 3467 SetPageUptodate(page); 3468 3469 flush_dcache_page(page); 3470 3471 /* 3472 * Every page after the 1st one should be completely zero'd. 3473 */ 3474 from = 0; 3475 } 3476 out: 3477 if (pages) { 3478 for (i = 0; i < numpages; i++) { 3479 page = pages[i]; 3480 unlock_page(page); 3481 mark_page_accessed(page); 3482 page_cache_release(page); 3483 } 3484 } 3485 } 3486 3487 static int ocfs2_grab_eof_pages(struct inode *inode, loff_t isize, struct page **pages, 3488 int *num, u64 *phys) 3489 { 3490 int i, numpages = 0, ret = 0; 3491 unsigned int csize = OCFS2_SB(inode->i_sb)->s_clustersize; 3492 unsigned int ext_flags; 3493 struct super_block *sb = inode->i_sb; 3494 struct address_space *mapping = inode->i_mapping; 3495 unsigned long index; 3496 u64 next_cluster_bytes; 3497 3498 BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb))); 3499 3500 /* Cluster boundary, so we don't need to grab any pages. */ 3501 if ((isize & (csize - 1)) == 0) 3502 goto out; 3503 3504 ret = ocfs2_extent_map_get_blocks(inode, isize >> sb->s_blocksize_bits, 3505 phys, NULL, &ext_flags); 3506 if (ret) { 3507 mlog_errno(ret); 3508 goto out; 3509 } 3510 3511 /* Tail is a hole. */ 3512 if (*phys == 0) 3513 goto out; 3514 3515 /* Tail is marked as unwritten, we can count on write to zero 3516 * in that case. */ 3517 if (ext_flags & OCFS2_EXT_UNWRITTEN) 3518 goto out; 3519 3520 next_cluster_bytes = ocfs2_align_bytes_to_clusters(inode->i_sb, isize); 3521 index = isize >> PAGE_CACHE_SHIFT; 3522 do { 3523 pages[numpages] = grab_cache_page(mapping, index); 3524 if (!pages[numpages]) { 3525 ret = -ENOMEM; 3526 mlog_errno(ret); 3527 goto out; 3528 } 3529 3530 numpages++; 3531 index++; 3532 } while (index < (next_cluster_bytes >> PAGE_CACHE_SHIFT)); 3533 3534 out: 3535 if (ret != 0) { 3536 if (pages) { 3537 for (i = 0; i < numpages; i++) { 3538 if (pages[i]) { 3539 unlock_page(pages[i]); 3540 page_cache_release(pages[i]); 3541 } 3542 } 3543 } 3544 numpages = 0; 3545 } 3546 3547 *num = numpages; 3548 3549 return ret; 3550 } 3551 3552 /* 3553 * Zero the area past i_size but still within an allocated 3554 * cluster. This avoids exposing nonzero data on subsequent file 3555 * extends. 3556 * 3557 * We need to call this before i_size is updated on the inode because 3558 * otherwise block_write_full_page() will skip writeout of pages past 3559 * i_size. The new_i_size parameter is passed for this reason. 3560 */ 3561 int ocfs2_zero_tail_for_truncate(struct inode *inode, handle_t *handle, 3562 u64 new_i_size) 3563 { 3564 int ret, numpages; 3565 loff_t endbyte; 3566 struct page **pages = NULL; 3567 u64 phys; 3568 3569 /* 3570 * File systems which don't support sparse files zero on every 3571 * extend. 3572 */ 3573 if (!ocfs2_sparse_alloc(OCFS2_SB(inode->i_sb))) 3574 return 0; 3575 3576 pages = kcalloc(ocfs2_pages_per_cluster(inode->i_sb), 3577 sizeof(struct page *), GFP_NOFS); 3578 if (pages == NULL) { 3579 ret = -ENOMEM; 3580 mlog_errno(ret); 3581 goto out; 3582 } 3583 3584 ret = ocfs2_grab_eof_pages(inode, new_i_size, pages, &numpages, &phys); 3585 if (ret) { 3586 mlog_errno(ret); 3587 goto out; 3588 } 3589 3590 if (numpages == 0) 3591 goto out; 3592 3593 ocfs2_zero_cluster_pages(inode, new_i_size, pages, numpages, phys, 3594 handle); 3595 3596 /* 3597 * Initiate writeout of the pages we zero'd here. We don't 3598 * wait on them - the truncate_inode_pages() call later will 3599 * do that for us. 3600 */ 3601 endbyte = ocfs2_align_bytes_to_clusters(inode->i_sb, new_i_size); 3602 ret = do_sync_mapping_range(inode->i_mapping, new_i_size, 3603 endbyte - 1, SYNC_FILE_RANGE_WRITE); 3604 if (ret) 3605 mlog_errno(ret); 3606 3607 out: 3608 if (pages) 3609 kfree(pages); 3610 3611 return ret; 3612 } 3613 3614 /* 3615 * It is expected, that by the time you call this function, 3616 * inode->i_size and fe->i_size have been adjusted. 3617 * 3618 * WARNING: This will kfree the truncate context 3619 */ 3620 int ocfs2_commit_truncate(struct ocfs2_super *osb, 3621 struct inode *inode, 3622 struct buffer_head *fe_bh, 3623 struct ocfs2_truncate_context *tc) 3624 { 3625 int status, i, credits, tl_sem = 0; 3626 u32 clusters_to_del, new_highest_cpos, range; 3627 struct ocfs2_extent_list *el; 3628 handle_t *handle = NULL; 3629 struct inode *tl_inode = osb->osb_tl_inode; 3630 struct ocfs2_path *path = NULL; 3631 3632 mlog_entry_void(); 3633 3634 down_write(&OCFS2_I(inode)->ip_alloc_sem); 3635 3636 new_highest_cpos = ocfs2_clusters_for_bytes(osb->sb, 3637 i_size_read(inode)); 3638 3639 path = ocfs2_new_inode_path(fe_bh); 3640 if (!path) { 3641 status = -ENOMEM; 3642 mlog_errno(status); 3643 goto bail; 3644 } 3645 3646 ocfs2_extent_map_trunc(inode, new_highest_cpos); 3647 3648 start: 3649 /* 3650 * Check that we still have allocation to delete. 3651 */ 3652 if (OCFS2_I(inode)->ip_clusters == 0) { 3653 status = 0; 3654 goto bail; 3655 } 3656 3657 /* 3658 * Truncate always works against the rightmost tree branch. 3659 */ 3660 status = ocfs2_find_path(inode, path, UINT_MAX); 3661 if (status) { 3662 mlog_errno(status); 3663 goto bail; 3664 } 3665 3666 mlog(0, "inode->ip_clusters = %u, tree_depth = %u\n", 3667 OCFS2_I(inode)->ip_clusters, path->p_tree_depth); 3668 3669 /* 3670 * By now, el will point to the extent list on the bottom most 3671 * portion of this tree. Only the tail record is considered in 3672 * each pass. 3673 * 3674 * We handle the following cases, in order: 3675 * - empty extent: delete the remaining branch 3676 * - remove the entire record 3677 * - remove a partial record 3678 * - no record needs to be removed (truncate has completed) 3679 */ 3680 el = path_leaf_el(path); 3681 if (le16_to_cpu(el->l_next_free_rec) == 0) { 3682 ocfs2_error(inode->i_sb, 3683 "Inode %llu has empty extent block at %llu\n", 3684 (unsigned long long)OCFS2_I(inode)->ip_blkno, 3685 (unsigned long long)path_leaf_bh(path)->b_blocknr); 3686 status = -EROFS; 3687 goto bail; 3688 } 3689 3690 i = le16_to_cpu(el->l_next_free_rec) - 1; 3691 range = le32_to_cpu(el->l_recs[i].e_cpos) + 3692 ocfs2_rec_clusters(el, &el->l_recs[i]); 3693 if (i == 0 && ocfs2_is_empty_extent(&el->l_recs[i])) { 3694 clusters_to_del = 0; 3695 } else if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_highest_cpos) { 3696 clusters_to_del = ocfs2_rec_clusters(el, &el->l_recs[i]); 3697 } else if (range > new_highest_cpos) { 3698 clusters_to_del = (ocfs2_rec_clusters(el, &el->l_recs[i]) + 3699 le32_to_cpu(el->l_recs[i].e_cpos)) - 3700 new_highest_cpos; 3701 } else { 3702 status = 0; 3703 goto bail; 3704 } 3705 3706 mlog(0, "clusters_to_del = %u in this pass, tail blk=%llu\n", 3707 clusters_to_del, (unsigned long long)path_leaf_bh(path)->b_blocknr); 3708 3709 BUG_ON(clusters_to_del == 0); 3710 3711 mutex_lock(&tl_inode->i_mutex); 3712 tl_sem = 1; 3713 /* ocfs2_truncate_log_needs_flush guarantees us at least one 3714 * record is free for use. If there isn't any, we flush to get 3715 * an empty truncate log. */ 3716 if (ocfs2_truncate_log_needs_flush(osb)) { 3717 status = __ocfs2_flush_truncate_log(osb); 3718 if (status < 0) { 3719 mlog_errno(status); 3720 goto bail; 3721 } 3722 } 3723 3724 credits = ocfs2_calc_tree_trunc_credits(osb->sb, clusters_to_del, 3725 (struct ocfs2_dinode *)fe_bh->b_data, 3726 el); 3727 handle = ocfs2_start_trans(osb, credits); 3728 if (IS_ERR(handle)) { 3729 status = PTR_ERR(handle); 3730 handle = NULL; 3731 mlog_errno(status); 3732 goto bail; 3733 } 3734 3735 status = ocfs2_do_truncate(osb, clusters_to_del, inode, fe_bh, handle, 3736 tc, path); 3737 if (status < 0) { 3738 mlog_errno(status); 3739 goto bail; 3740 } 3741 3742 mutex_unlock(&tl_inode->i_mutex); 3743 tl_sem = 0; 3744 3745 ocfs2_commit_trans(osb, handle); 3746 handle = NULL; 3747 3748 ocfs2_reinit_path(path, 1); 3749 3750 /* 3751 * The check above will catch the case where we've truncated 3752 * away all allocation. 3753 */ 3754 goto start; 3755 3756 bail: 3757 up_write(&OCFS2_I(inode)->ip_alloc_sem); 3758 3759 ocfs2_schedule_truncate_log_flush(osb, 1); 3760 3761 if (tl_sem) 3762 mutex_unlock(&tl_inode->i_mutex); 3763 3764 if (handle) 3765 ocfs2_commit_trans(osb, handle); 3766 3767 ocfs2_free_path(path); 3768 3769 /* This will drop the ext_alloc cluster lock for us */ 3770 ocfs2_free_truncate_context(tc); 3771 3772 mlog_exit(status); 3773 return status; 3774 } 3775 3776 /* 3777 * Expects the inode to already be locked. This will figure out which 3778 * inodes need to be locked and will put them on the returned truncate 3779 * context. 3780 */ 3781 int ocfs2_prepare_truncate(struct ocfs2_super *osb, 3782 struct inode *inode, 3783 struct buffer_head *fe_bh, 3784 struct ocfs2_truncate_context **tc) 3785 { 3786 int status, metadata_delete, i; 3787 unsigned int new_i_clusters; 3788 struct ocfs2_dinode *fe; 3789 struct ocfs2_extent_block *eb; 3790 struct ocfs2_extent_list *el; 3791 struct buffer_head *last_eb_bh = NULL; 3792 struct inode *ext_alloc_inode = NULL; 3793 struct buffer_head *ext_alloc_bh = NULL; 3794 3795 mlog_entry_void(); 3796 3797 *tc = NULL; 3798 3799 new_i_clusters = ocfs2_clusters_for_bytes(osb->sb, 3800 i_size_read(inode)); 3801 fe = (struct ocfs2_dinode *) fe_bh->b_data; 3802 3803 mlog(0, "fe->i_clusters = %u, new_i_clusters = %u, fe->i_size =" 3804 "%llu\n", le32_to_cpu(fe->i_clusters), new_i_clusters, 3805 (unsigned long long)le64_to_cpu(fe->i_size)); 3806 3807 *tc = kzalloc(sizeof(struct ocfs2_truncate_context), GFP_KERNEL); 3808 if (!(*tc)) { 3809 status = -ENOMEM; 3810 mlog_errno(status); 3811 goto bail; 3812 } 3813 3814 metadata_delete = 0; 3815 if (fe->id2.i_list.l_tree_depth) { 3816 /* If we have a tree, then the truncate may result in 3817 * metadata deletes. Figure this out from the 3818 * rightmost leaf block.*/ 3819 status = ocfs2_read_block(osb, le64_to_cpu(fe->i_last_eb_blk), 3820 &last_eb_bh, OCFS2_BH_CACHED, inode); 3821 if (status < 0) { 3822 mlog_errno(status); 3823 goto bail; 3824 } 3825 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; 3826 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 3827 OCFS2_RO_ON_INVALID_EXTENT_BLOCK(inode->i_sb, eb); 3828 3829 brelse(last_eb_bh); 3830 status = -EIO; 3831 goto bail; 3832 } 3833 el = &(eb->h_list); 3834 3835 i = 0; 3836 if (ocfs2_is_empty_extent(&el->l_recs[0])) 3837 i = 1; 3838 /* 3839 * XXX: Should we check that next_free_rec contains 3840 * the extent? 3841 */ 3842 if (le32_to_cpu(el->l_recs[i].e_cpos) >= new_i_clusters) 3843 metadata_delete = 1; 3844 } 3845 3846 (*tc)->tc_last_eb_bh = last_eb_bh; 3847 3848 if (metadata_delete) { 3849 mlog(0, "Will have to delete metadata for this trunc. " 3850 "locking allocator.\n"); 3851 ext_alloc_inode = ocfs2_get_system_file_inode(osb, EXTENT_ALLOC_SYSTEM_INODE, 0); 3852 if (!ext_alloc_inode) { 3853 status = -ENOMEM; 3854 mlog_errno(status); 3855 goto bail; 3856 } 3857 3858 mutex_lock(&ext_alloc_inode->i_mutex); 3859 (*tc)->tc_ext_alloc_inode = ext_alloc_inode; 3860 3861 status = ocfs2_meta_lock(ext_alloc_inode, &ext_alloc_bh, 1); 3862 if (status < 0) { 3863 mlog_errno(status); 3864 goto bail; 3865 } 3866 (*tc)->tc_ext_alloc_bh = ext_alloc_bh; 3867 (*tc)->tc_ext_alloc_locked = 1; 3868 } 3869 3870 status = 0; 3871 bail: 3872 if (status < 0) { 3873 if (*tc) 3874 ocfs2_free_truncate_context(*tc); 3875 *tc = NULL; 3876 } 3877 mlog_exit_void(); 3878 return status; 3879 } 3880 3881 static void ocfs2_free_truncate_context(struct ocfs2_truncate_context *tc) 3882 { 3883 if (tc->tc_ext_alloc_inode) { 3884 if (tc->tc_ext_alloc_locked) 3885 ocfs2_meta_unlock(tc->tc_ext_alloc_inode, 1); 3886 3887 mutex_unlock(&tc->tc_ext_alloc_inode->i_mutex); 3888 iput(tc->tc_ext_alloc_inode); 3889 } 3890 3891 if (tc->tc_ext_alloc_bh) 3892 brelse(tc->tc_ext_alloc_bh); 3893 3894 if (tc->tc_last_eb_bh) 3895 brelse(tc->tc_last_eb_bh); 3896 3897 kfree(tc); 3898 } 3899