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 #include <linux/quotaops.h> 32 #include <linux/blkdev.h> 33 34 #include <cluster/masklog.h> 35 36 #include "ocfs2.h" 37 38 #include "alloc.h" 39 #include "aops.h" 40 #include "blockcheck.h" 41 #include "dlmglue.h" 42 #include "extent_map.h" 43 #include "inode.h" 44 #include "journal.h" 45 #include "localalloc.h" 46 #include "suballoc.h" 47 #include "sysfile.h" 48 #include "file.h" 49 #include "super.h" 50 #include "uptodate.h" 51 #include "xattr.h" 52 #include "refcounttree.h" 53 #include "ocfs2_trace.h" 54 55 #include "buffer_head_io.h" 56 57 enum ocfs2_contig_type { 58 CONTIG_NONE = 0, 59 CONTIG_LEFT, 60 CONTIG_RIGHT, 61 CONTIG_LEFTRIGHT, 62 }; 63 64 static enum ocfs2_contig_type 65 ocfs2_extent_rec_contig(struct super_block *sb, 66 struct ocfs2_extent_rec *ext, 67 struct ocfs2_extent_rec *insert_rec); 68 /* 69 * Operations for a specific extent tree type. 70 * 71 * To implement an on-disk btree (extent tree) type in ocfs2, add 72 * an ocfs2_extent_tree_operations structure and the matching 73 * ocfs2_init_<thingy>_extent_tree() function. That's pretty much it 74 * for the allocation portion of the extent tree. 75 */ 76 struct ocfs2_extent_tree_operations { 77 /* 78 * last_eb_blk is the block number of the right most leaf extent 79 * block. Most on-disk structures containing an extent tree store 80 * this value for fast access. The ->eo_set_last_eb_blk() and 81 * ->eo_get_last_eb_blk() operations access this value. They are 82 * both required. 83 */ 84 void (*eo_set_last_eb_blk)(struct ocfs2_extent_tree *et, 85 u64 blkno); 86 u64 (*eo_get_last_eb_blk)(struct ocfs2_extent_tree *et); 87 88 /* 89 * The on-disk structure usually keeps track of how many total 90 * clusters are stored in this extent tree. This function updates 91 * that value. new_clusters is the delta, and must be 92 * added to the total. Required. 93 */ 94 void (*eo_update_clusters)(struct ocfs2_extent_tree *et, 95 u32 new_clusters); 96 97 /* 98 * If this extent tree is supported by an extent map, insert 99 * a record into the map. 100 */ 101 void (*eo_extent_map_insert)(struct ocfs2_extent_tree *et, 102 struct ocfs2_extent_rec *rec); 103 104 /* 105 * If this extent tree is supported by an extent map, truncate the 106 * map to clusters, 107 */ 108 void (*eo_extent_map_truncate)(struct ocfs2_extent_tree *et, 109 u32 clusters); 110 111 /* 112 * If ->eo_insert_check() exists, it is called before rec is 113 * inserted into the extent tree. It is optional. 114 */ 115 int (*eo_insert_check)(struct ocfs2_extent_tree *et, 116 struct ocfs2_extent_rec *rec); 117 int (*eo_sanity_check)(struct ocfs2_extent_tree *et); 118 119 /* 120 * -------------------------------------------------------------- 121 * The remaining are internal to ocfs2_extent_tree and don't have 122 * accessor functions 123 */ 124 125 /* 126 * ->eo_fill_root_el() takes et->et_object and sets et->et_root_el. 127 * It is required. 128 */ 129 void (*eo_fill_root_el)(struct ocfs2_extent_tree *et); 130 131 /* 132 * ->eo_fill_max_leaf_clusters sets et->et_max_leaf_clusters if 133 * it exists. If it does not, et->et_max_leaf_clusters is set 134 * to 0 (unlimited). Optional. 135 */ 136 void (*eo_fill_max_leaf_clusters)(struct ocfs2_extent_tree *et); 137 138 /* 139 * ->eo_extent_contig test whether the 2 ocfs2_extent_rec 140 * are contiguous or not. Optional. Don't need to set it if use 141 * ocfs2_extent_rec as the tree leaf. 142 */ 143 enum ocfs2_contig_type 144 (*eo_extent_contig)(struct ocfs2_extent_tree *et, 145 struct ocfs2_extent_rec *ext, 146 struct ocfs2_extent_rec *insert_rec); 147 }; 148 149 150 /* 151 * Pre-declare ocfs2_dinode_et_ops so we can use it as a sanity check 152 * in the methods. 153 */ 154 static u64 ocfs2_dinode_get_last_eb_blk(struct ocfs2_extent_tree *et); 155 static void ocfs2_dinode_set_last_eb_blk(struct ocfs2_extent_tree *et, 156 u64 blkno); 157 static void ocfs2_dinode_update_clusters(struct ocfs2_extent_tree *et, 158 u32 clusters); 159 static void ocfs2_dinode_extent_map_insert(struct ocfs2_extent_tree *et, 160 struct ocfs2_extent_rec *rec); 161 static void ocfs2_dinode_extent_map_truncate(struct ocfs2_extent_tree *et, 162 u32 clusters); 163 static int ocfs2_dinode_insert_check(struct ocfs2_extent_tree *et, 164 struct ocfs2_extent_rec *rec); 165 static int ocfs2_dinode_sanity_check(struct ocfs2_extent_tree *et); 166 static void ocfs2_dinode_fill_root_el(struct ocfs2_extent_tree *et); 167 static struct ocfs2_extent_tree_operations ocfs2_dinode_et_ops = { 168 .eo_set_last_eb_blk = ocfs2_dinode_set_last_eb_blk, 169 .eo_get_last_eb_blk = ocfs2_dinode_get_last_eb_blk, 170 .eo_update_clusters = ocfs2_dinode_update_clusters, 171 .eo_extent_map_insert = ocfs2_dinode_extent_map_insert, 172 .eo_extent_map_truncate = ocfs2_dinode_extent_map_truncate, 173 .eo_insert_check = ocfs2_dinode_insert_check, 174 .eo_sanity_check = ocfs2_dinode_sanity_check, 175 .eo_fill_root_el = ocfs2_dinode_fill_root_el, 176 }; 177 178 static void ocfs2_dinode_set_last_eb_blk(struct ocfs2_extent_tree *et, 179 u64 blkno) 180 { 181 struct ocfs2_dinode *di = et->et_object; 182 183 BUG_ON(et->et_ops != &ocfs2_dinode_et_ops); 184 di->i_last_eb_blk = cpu_to_le64(blkno); 185 } 186 187 static u64 ocfs2_dinode_get_last_eb_blk(struct ocfs2_extent_tree *et) 188 { 189 struct ocfs2_dinode *di = et->et_object; 190 191 BUG_ON(et->et_ops != &ocfs2_dinode_et_ops); 192 return le64_to_cpu(di->i_last_eb_blk); 193 } 194 195 static void ocfs2_dinode_update_clusters(struct ocfs2_extent_tree *et, 196 u32 clusters) 197 { 198 struct ocfs2_inode_info *oi = cache_info_to_inode(et->et_ci); 199 struct ocfs2_dinode *di = et->et_object; 200 201 le32_add_cpu(&di->i_clusters, clusters); 202 spin_lock(&oi->ip_lock); 203 oi->ip_clusters = le32_to_cpu(di->i_clusters); 204 spin_unlock(&oi->ip_lock); 205 } 206 207 static void ocfs2_dinode_extent_map_insert(struct ocfs2_extent_tree *et, 208 struct ocfs2_extent_rec *rec) 209 { 210 struct inode *inode = &cache_info_to_inode(et->et_ci)->vfs_inode; 211 212 ocfs2_extent_map_insert_rec(inode, rec); 213 } 214 215 static void ocfs2_dinode_extent_map_truncate(struct ocfs2_extent_tree *et, 216 u32 clusters) 217 { 218 struct inode *inode = &cache_info_to_inode(et->et_ci)->vfs_inode; 219 220 ocfs2_extent_map_trunc(inode, clusters); 221 } 222 223 static int ocfs2_dinode_insert_check(struct ocfs2_extent_tree *et, 224 struct ocfs2_extent_rec *rec) 225 { 226 struct ocfs2_inode_info *oi = cache_info_to_inode(et->et_ci); 227 struct ocfs2_super *osb = OCFS2_SB(oi->vfs_inode.i_sb); 228 229 BUG_ON(oi->ip_dyn_features & OCFS2_INLINE_DATA_FL); 230 mlog_bug_on_msg(!ocfs2_sparse_alloc(osb) && 231 (oi->ip_clusters != le32_to_cpu(rec->e_cpos)), 232 "Device %s, asking for sparse allocation: inode %llu, " 233 "cpos %u, clusters %u\n", 234 osb->dev_str, 235 (unsigned long long)oi->ip_blkno, 236 rec->e_cpos, oi->ip_clusters); 237 238 return 0; 239 } 240 241 static int ocfs2_dinode_sanity_check(struct ocfs2_extent_tree *et) 242 { 243 struct ocfs2_dinode *di = et->et_object; 244 245 BUG_ON(et->et_ops != &ocfs2_dinode_et_ops); 246 BUG_ON(!OCFS2_IS_VALID_DINODE(di)); 247 248 return 0; 249 } 250 251 static void ocfs2_dinode_fill_root_el(struct ocfs2_extent_tree *et) 252 { 253 struct ocfs2_dinode *di = et->et_object; 254 255 et->et_root_el = &di->id2.i_list; 256 } 257 258 259 static void ocfs2_xattr_value_fill_root_el(struct ocfs2_extent_tree *et) 260 { 261 struct ocfs2_xattr_value_buf *vb = et->et_object; 262 263 et->et_root_el = &vb->vb_xv->xr_list; 264 } 265 266 static void ocfs2_xattr_value_set_last_eb_blk(struct ocfs2_extent_tree *et, 267 u64 blkno) 268 { 269 struct ocfs2_xattr_value_buf *vb = et->et_object; 270 271 vb->vb_xv->xr_last_eb_blk = cpu_to_le64(blkno); 272 } 273 274 static u64 ocfs2_xattr_value_get_last_eb_blk(struct ocfs2_extent_tree *et) 275 { 276 struct ocfs2_xattr_value_buf *vb = et->et_object; 277 278 return le64_to_cpu(vb->vb_xv->xr_last_eb_blk); 279 } 280 281 static void ocfs2_xattr_value_update_clusters(struct ocfs2_extent_tree *et, 282 u32 clusters) 283 { 284 struct ocfs2_xattr_value_buf *vb = et->et_object; 285 286 le32_add_cpu(&vb->vb_xv->xr_clusters, clusters); 287 } 288 289 static struct ocfs2_extent_tree_operations ocfs2_xattr_value_et_ops = { 290 .eo_set_last_eb_blk = ocfs2_xattr_value_set_last_eb_blk, 291 .eo_get_last_eb_blk = ocfs2_xattr_value_get_last_eb_blk, 292 .eo_update_clusters = ocfs2_xattr_value_update_clusters, 293 .eo_fill_root_el = ocfs2_xattr_value_fill_root_el, 294 }; 295 296 static void ocfs2_xattr_tree_fill_root_el(struct ocfs2_extent_tree *et) 297 { 298 struct ocfs2_xattr_block *xb = et->et_object; 299 300 et->et_root_el = &xb->xb_attrs.xb_root.xt_list; 301 } 302 303 static void ocfs2_xattr_tree_fill_max_leaf_clusters(struct ocfs2_extent_tree *et) 304 { 305 struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci); 306 et->et_max_leaf_clusters = 307 ocfs2_clusters_for_bytes(sb, OCFS2_MAX_XATTR_TREE_LEAF_SIZE); 308 } 309 310 static void ocfs2_xattr_tree_set_last_eb_blk(struct ocfs2_extent_tree *et, 311 u64 blkno) 312 { 313 struct ocfs2_xattr_block *xb = et->et_object; 314 struct ocfs2_xattr_tree_root *xt = &xb->xb_attrs.xb_root; 315 316 xt->xt_last_eb_blk = cpu_to_le64(blkno); 317 } 318 319 static u64 ocfs2_xattr_tree_get_last_eb_blk(struct ocfs2_extent_tree *et) 320 { 321 struct ocfs2_xattr_block *xb = et->et_object; 322 struct ocfs2_xattr_tree_root *xt = &xb->xb_attrs.xb_root; 323 324 return le64_to_cpu(xt->xt_last_eb_blk); 325 } 326 327 static void ocfs2_xattr_tree_update_clusters(struct ocfs2_extent_tree *et, 328 u32 clusters) 329 { 330 struct ocfs2_xattr_block *xb = et->et_object; 331 332 le32_add_cpu(&xb->xb_attrs.xb_root.xt_clusters, clusters); 333 } 334 335 static struct ocfs2_extent_tree_operations ocfs2_xattr_tree_et_ops = { 336 .eo_set_last_eb_blk = ocfs2_xattr_tree_set_last_eb_blk, 337 .eo_get_last_eb_blk = ocfs2_xattr_tree_get_last_eb_blk, 338 .eo_update_clusters = ocfs2_xattr_tree_update_clusters, 339 .eo_fill_root_el = ocfs2_xattr_tree_fill_root_el, 340 .eo_fill_max_leaf_clusters = ocfs2_xattr_tree_fill_max_leaf_clusters, 341 }; 342 343 static void ocfs2_dx_root_set_last_eb_blk(struct ocfs2_extent_tree *et, 344 u64 blkno) 345 { 346 struct ocfs2_dx_root_block *dx_root = et->et_object; 347 348 dx_root->dr_last_eb_blk = cpu_to_le64(blkno); 349 } 350 351 static u64 ocfs2_dx_root_get_last_eb_blk(struct ocfs2_extent_tree *et) 352 { 353 struct ocfs2_dx_root_block *dx_root = et->et_object; 354 355 return le64_to_cpu(dx_root->dr_last_eb_blk); 356 } 357 358 static void ocfs2_dx_root_update_clusters(struct ocfs2_extent_tree *et, 359 u32 clusters) 360 { 361 struct ocfs2_dx_root_block *dx_root = et->et_object; 362 363 le32_add_cpu(&dx_root->dr_clusters, clusters); 364 } 365 366 static int ocfs2_dx_root_sanity_check(struct ocfs2_extent_tree *et) 367 { 368 struct ocfs2_dx_root_block *dx_root = et->et_object; 369 370 BUG_ON(!OCFS2_IS_VALID_DX_ROOT(dx_root)); 371 372 return 0; 373 } 374 375 static void ocfs2_dx_root_fill_root_el(struct ocfs2_extent_tree *et) 376 { 377 struct ocfs2_dx_root_block *dx_root = et->et_object; 378 379 et->et_root_el = &dx_root->dr_list; 380 } 381 382 static struct ocfs2_extent_tree_operations ocfs2_dx_root_et_ops = { 383 .eo_set_last_eb_blk = ocfs2_dx_root_set_last_eb_blk, 384 .eo_get_last_eb_blk = ocfs2_dx_root_get_last_eb_blk, 385 .eo_update_clusters = ocfs2_dx_root_update_clusters, 386 .eo_sanity_check = ocfs2_dx_root_sanity_check, 387 .eo_fill_root_el = ocfs2_dx_root_fill_root_el, 388 }; 389 390 static void ocfs2_refcount_tree_fill_root_el(struct ocfs2_extent_tree *et) 391 { 392 struct ocfs2_refcount_block *rb = et->et_object; 393 394 et->et_root_el = &rb->rf_list; 395 } 396 397 static void ocfs2_refcount_tree_set_last_eb_blk(struct ocfs2_extent_tree *et, 398 u64 blkno) 399 { 400 struct ocfs2_refcount_block *rb = et->et_object; 401 402 rb->rf_last_eb_blk = cpu_to_le64(blkno); 403 } 404 405 static u64 ocfs2_refcount_tree_get_last_eb_blk(struct ocfs2_extent_tree *et) 406 { 407 struct ocfs2_refcount_block *rb = et->et_object; 408 409 return le64_to_cpu(rb->rf_last_eb_blk); 410 } 411 412 static void ocfs2_refcount_tree_update_clusters(struct ocfs2_extent_tree *et, 413 u32 clusters) 414 { 415 struct ocfs2_refcount_block *rb = et->et_object; 416 417 le32_add_cpu(&rb->rf_clusters, clusters); 418 } 419 420 static enum ocfs2_contig_type 421 ocfs2_refcount_tree_extent_contig(struct ocfs2_extent_tree *et, 422 struct ocfs2_extent_rec *ext, 423 struct ocfs2_extent_rec *insert_rec) 424 { 425 return CONTIG_NONE; 426 } 427 428 static struct ocfs2_extent_tree_operations ocfs2_refcount_tree_et_ops = { 429 .eo_set_last_eb_blk = ocfs2_refcount_tree_set_last_eb_blk, 430 .eo_get_last_eb_blk = ocfs2_refcount_tree_get_last_eb_blk, 431 .eo_update_clusters = ocfs2_refcount_tree_update_clusters, 432 .eo_fill_root_el = ocfs2_refcount_tree_fill_root_el, 433 .eo_extent_contig = ocfs2_refcount_tree_extent_contig, 434 }; 435 436 static void __ocfs2_init_extent_tree(struct ocfs2_extent_tree *et, 437 struct ocfs2_caching_info *ci, 438 struct buffer_head *bh, 439 ocfs2_journal_access_func access, 440 void *obj, 441 struct ocfs2_extent_tree_operations *ops) 442 { 443 et->et_ops = ops; 444 et->et_root_bh = bh; 445 et->et_ci = ci; 446 et->et_root_journal_access = access; 447 if (!obj) 448 obj = (void *)bh->b_data; 449 et->et_object = obj; 450 451 et->et_ops->eo_fill_root_el(et); 452 if (!et->et_ops->eo_fill_max_leaf_clusters) 453 et->et_max_leaf_clusters = 0; 454 else 455 et->et_ops->eo_fill_max_leaf_clusters(et); 456 } 457 458 void ocfs2_init_dinode_extent_tree(struct ocfs2_extent_tree *et, 459 struct ocfs2_caching_info *ci, 460 struct buffer_head *bh) 461 { 462 __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_di, 463 NULL, &ocfs2_dinode_et_ops); 464 } 465 466 void ocfs2_init_xattr_tree_extent_tree(struct ocfs2_extent_tree *et, 467 struct ocfs2_caching_info *ci, 468 struct buffer_head *bh) 469 { 470 __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_xb, 471 NULL, &ocfs2_xattr_tree_et_ops); 472 } 473 474 void ocfs2_init_xattr_value_extent_tree(struct ocfs2_extent_tree *et, 475 struct ocfs2_caching_info *ci, 476 struct ocfs2_xattr_value_buf *vb) 477 { 478 __ocfs2_init_extent_tree(et, ci, vb->vb_bh, vb->vb_access, vb, 479 &ocfs2_xattr_value_et_ops); 480 } 481 482 void ocfs2_init_dx_root_extent_tree(struct ocfs2_extent_tree *et, 483 struct ocfs2_caching_info *ci, 484 struct buffer_head *bh) 485 { 486 __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_dr, 487 NULL, &ocfs2_dx_root_et_ops); 488 } 489 490 void ocfs2_init_refcount_extent_tree(struct ocfs2_extent_tree *et, 491 struct ocfs2_caching_info *ci, 492 struct buffer_head *bh) 493 { 494 __ocfs2_init_extent_tree(et, ci, bh, ocfs2_journal_access_rb, 495 NULL, &ocfs2_refcount_tree_et_ops); 496 } 497 498 static inline void ocfs2_et_set_last_eb_blk(struct ocfs2_extent_tree *et, 499 u64 new_last_eb_blk) 500 { 501 et->et_ops->eo_set_last_eb_blk(et, new_last_eb_blk); 502 } 503 504 static inline u64 ocfs2_et_get_last_eb_blk(struct ocfs2_extent_tree *et) 505 { 506 return et->et_ops->eo_get_last_eb_blk(et); 507 } 508 509 static inline void ocfs2_et_update_clusters(struct ocfs2_extent_tree *et, 510 u32 clusters) 511 { 512 et->et_ops->eo_update_clusters(et, clusters); 513 } 514 515 static inline void ocfs2_et_extent_map_insert(struct ocfs2_extent_tree *et, 516 struct ocfs2_extent_rec *rec) 517 { 518 if (et->et_ops->eo_extent_map_insert) 519 et->et_ops->eo_extent_map_insert(et, rec); 520 } 521 522 static inline void ocfs2_et_extent_map_truncate(struct ocfs2_extent_tree *et, 523 u32 clusters) 524 { 525 if (et->et_ops->eo_extent_map_truncate) 526 et->et_ops->eo_extent_map_truncate(et, clusters); 527 } 528 529 static inline int ocfs2_et_root_journal_access(handle_t *handle, 530 struct ocfs2_extent_tree *et, 531 int type) 532 { 533 return et->et_root_journal_access(handle, et->et_ci, et->et_root_bh, 534 type); 535 } 536 537 static inline enum ocfs2_contig_type 538 ocfs2_et_extent_contig(struct ocfs2_extent_tree *et, 539 struct ocfs2_extent_rec *rec, 540 struct ocfs2_extent_rec *insert_rec) 541 { 542 if (et->et_ops->eo_extent_contig) 543 return et->et_ops->eo_extent_contig(et, rec, insert_rec); 544 545 return ocfs2_extent_rec_contig( 546 ocfs2_metadata_cache_get_super(et->et_ci), 547 rec, insert_rec); 548 } 549 550 static inline int ocfs2_et_insert_check(struct ocfs2_extent_tree *et, 551 struct ocfs2_extent_rec *rec) 552 { 553 int ret = 0; 554 555 if (et->et_ops->eo_insert_check) 556 ret = et->et_ops->eo_insert_check(et, rec); 557 return ret; 558 } 559 560 static inline int ocfs2_et_sanity_check(struct ocfs2_extent_tree *et) 561 { 562 int ret = 0; 563 564 if (et->et_ops->eo_sanity_check) 565 ret = et->et_ops->eo_sanity_check(et); 566 return ret; 567 } 568 569 static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt, 570 struct ocfs2_extent_block *eb); 571 static void ocfs2_adjust_rightmost_records(handle_t *handle, 572 struct ocfs2_extent_tree *et, 573 struct ocfs2_path *path, 574 struct ocfs2_extent_rec *insert_rec); 575 /* 576 * Reset the actual path elements so that we can re-use the structure 577 * to build another path. Generally, this involves freeing the buffer 578 * heads. 579 */ 580 void ocfs2_reinit_path(struct ocfs2_path *path, int keep_root) 581 { 582 int i, start = 0, depth = 0; 583 struct ocfs2_path_item *node; 584 585 if (keep_root) 586 start = 1; 587 588 for(i = start; i < path_num_items(path); i++) { 589 node = &path->p_node[i]; 590 591 brelse(node->bh); 592 node->bh = NULL; 593 node->el = NULL; 594 } 595 596 /* 597 * Tree depth may change during truncate, or insert. If we're 598 * keeping the root extent list, then make sure that our path 599 * structure reflects the proper depth. 600 */ 601 if (keep_root) 602 depth = le16_to_cpu(path_root_el(path)->l_tree_depth); 603 else 604 path_root_access(path) = NULL; 605 606 path->p_tree_depth = depth; 607 } 608 609 void ocfs2_free_path(struct ocfs2_path *path) 610 { 611 if (path) { 612 ocfs2_reinit_path(path, 0); 613 kfree(path); 614 } 615 } 616 617 /* 618 * All the elements of src into dest. After this call, src could be freed 619 * without affecting dest. 620 * 621 * Both paths should have the same root. Any non-root elements of dest 622 * will be freed. 623 */ 624 static void ocfs2_cp_path(struct ocfs2_path *dest, struct ocfs2_path *src) 625 { 626 int i; 627 628 BUG_ON(path_root_bh(dest) != path_root_bh(src)); 629 BUG_ON(path_root_el(dest) != path_root_el(src)); 630 BUG_ON(path_root_access(dest) != path_root_access(src)); 631 632 ocfs2_reinit_path(dest, 1); 633 634 for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) { 635 dest->p_node[i].bh = src->p_node[i].bh; 636 dest->p_node[i].el = src->p_node[i].el; 637 638 if (dest->p_node[i].bh) 639 get_bh(dest->p_node[i].bh); 640 } 641 } 642 643 /* 644 * Make the *dest path the same as src and re-initialize src path to 645 * have a root only. 646 */ 647 static void ocfs2_mv_path(struct ocfs2_path *dest, struct ocfs2_path *src) 648 { 649 int i; 650 651 BUG_ON(path_root_bh(dest) != path_root_bh(src)); 652 BUG_ON(path_root_access(dest) != path_root_access(src)); 653 654 for(i = 1; i < OCFS2_MAX_PATH_DEPTH; i++) { 655 brelse(dest->p_node[i].bh); 656 657 dest->p_node[i].bh = src->p_node[i].bh; 658 dest->p_node[i].el = src->p_node[i].el; 659 660 src->p_node[i].bh = NULL; 661 src->p_node[i].el = NULL; 662 } 663 } 664 665 /* 666 * Insert an extent block at given index. 667 * 668 * This will not take an additional reference on eb_bh. 669 */ 670 static inline void ocfs2_path_insert_eb(struct ocfs2_path *path, int index, 671 struct buffer_head *eb_bh) 672 { 673 struct ocfs2_extent_block *eb = (struct ocfs2_extent_block *)eb_bh->b_data; 674 675 /* 676 * Right now, no root bh is an extent block, so this helps 677 * catch code errors with dinode trees. The assertion can be 678 * safely removed if we ever need to insert extent block 679 * structures at the root. 680 */ 681 BUG_ON(index == 0); 682 683 path->p_node[index].bh = eb_bh; 684 path->p_node[index].el = &eb->h_list; 685 } 686 687 static struct ocfs2_path *ocfs2_new_path(struct buffer_head *root_bh, 688 struct ocfs2_extent_list *root_el, 689 ocfs2_journal_access_func access) 690 { 691 struct ocfs2_path *path; 692 693 BUG_ON(le16_to_cpu(root_el->l_tree_depth) >= OCFS2_MAX_PATH_DEPTH); 694 695 path = kzalloc(sizeof(*path), GFP_NOFS); 696 if (path) { 697 path->p_tree_depth = le16_to_cpu(root_el->l_tree_depth); 698 get_bh(root_bh); 699 path_root_bh(path) = root_bh; 700 path_root_el(path) = root_el; 701 path_root_access(path) = access; 702 } 703 704 return path; 705 } 706 707 struct ocfs2_path *ocfs2_new_path_from_path(struct ocfs2_path *path) 708 { 709 return ocfs2_new_path(path_root_bh(path), path_root_el(path), 710 path_root_access(path)); 711 } 712 713 struct ocfs2_path *ocfs2_new_path_from_et(struct ocfs2_extent_tree *et) 714 { 715 return ocfs2_new_path(et->et_root_bh, et->et_root_el, 716 et->et_root_journal_access); 717 } 718 719 /* 720 * Journal the buffer at depth idx. All idx>0 are extent_blocks, 721 * otherwise it's the root_access function. 722 * 723 * I don't like the way this function's name looks next to 724 * ocfs2_journal_access_path(), but I don't have a better one. 725 */ 726 int ocfs2_path_bh_journal_access(handle_t *handle, 727 struct ocfs2_caching_info *ci, 728 struct ocfs2_path *path, 729 int idx) 730 { 731 ocfs2_journal_access_func access = path_root_access(path); 732 733 if (!access) 734 access = ocfs2_journal_access; 735 736 if (idx) 737 access = ocfs2_journal_access_eb; 738 739 return access(handle, ci, path->p_node[idx].bh, 740 OCFS2_JOURNAL_ACCESS_WRITE); 741 } 742 743 /* 744 * Convenience function to journal all components in a path. 745 */ 746 int ocfs2_journal_access_path(struct ocfs2_caching_info *ci, 747 handle_t *handle, 748 struct ocfs2_path *path) 749 { 750 int i, ret = 0; 751 752 if (!path) 753 goto out; 754 755 for(i = 0; i < path_num_items(path); i++) { 756 ret = ocfs2_path_bh_journal_access(handle, ci, path, i); 757 if (ret < 0) { 758 mlog_errno(ret); 759 goto out; 760 } 761 } 762 763 out: 764 return ret; 765 } 766 767 /* 768 * Return the index of the extent record which contains cluster #v_cluster. 769 * -1 is returned if it was not found. 770 * 771 * Should work fine on interior and exterior nodes. 772 */ 773 int ocfs2_search_extent_list(struct ocfs2_extent_list *el, u32 v_cluster) 774 { 775 int ret = -1; 776 int i; 777 struct ocfs2_extent_rec *rec; 778 u32 rec_end, rec_start, clusters; 779 780 for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { 781 rec = &el->l_recs[i]; 782 783 rec_start = le32_to_cpu(rec->e_cpos); 784 clusters = ocfs2_rec_clusters(el, rec); 785 786 rec_end = rec_start + clusters; 787 788 if (v_cluster >= rec_start && v_cluster < rec_end) { 789 ret = i; 790 break; 791 } 792 } 793 794 return ret; 795 } 796 797 /* 798 * NOTE: ocfs2_block_extent_contig(), ocfs2_extents_adjacent() and 799 * ocfs2_extent_rec_contig only work properly against leaf nodes! 800 */ 801 static int ocfs2_block_extent_contig(struct super_block *sb, 802 struct ocfs2_extent_rec *ext, 803 u64 blkno) 804 { 805 u64 blk_end = le64_to_cpu(ext->e_blkno); 806 807 blk_end += ocfs2_clusters_to_blocks(sb, 808 le16_to_cpu(ext->e_leaf_clusters)); 809 810 return blkno == blk_end; 811 } 812 813 static int ocfs2_extents_adjacent(struct ocfs2_extent_rec *left, 814 struct ocfs2_extent_rec *right) 815 { 816 u32 left_range; 817 818 left_range = le32_to_cpu(left->e_cpos) + 819 le16_to_cpu(left->e_leaf_clusters); 820 821 return (left_range == le32_to_cpu(right->e_cpos)); 822 } 823 824 static enum ocfs2_contig_type 825 ocfs2_extent_rec_contig(struct super_block *sb, 826 struct ocfs2_extent_rec *ext, 827 struct ocfs2_extent_rec *insert_rec) 828 { 829 u64 blkno = le64_to_cpu(insert_rec->e_blkno); 830 831 /* 832 * Refuse to coalesce extent records with different flag 833 * fields - we don't want to mix unwritten extents with user 834 * data. 835 */ 836 if (ext->e_flags != insert_rec->e_flags) 837 return CONTIG_NONE; 838 839 if (ocfs2_extents_adjacent(ext, insert_rec) && 840 ocfs2_block_extent_contig(sb, ext, blkno)) 841 return CONTIG_RIGHT; 842 843 blkno = le64_to_cpu(ext->e_blkno); 844 if (ocfs2_extents_adjacent(insert_rec, ext) && 845 ocfs2_block_extent_contig(sb, insert_rec, blkno)) 846 return CONTIG_LEFT; 847 848 return CONTIG_NONE; 849 } 850 851 /* 852 * NOTE: We can have pretty much any combination of contiguousness and 853 * appending. 854 * 855 * The usefulness of APPEND_TAIL is more in that it lets us know that 856 * we'll have to update the path to that leaf. 857 */ 858 enum ocfs2_append_type { 859 APPEND_NONE = 0, 860 APPEND_TAIL, 861 }; 862 863 enum ocfs2_split_type { 864 SPLIT_NONE = 0, 865 SPLIT_LEFT, 866 SPLIT_RIGHT, 867 }; 868 869 struct ocfs2_insert_type { 870 enum ocfs2_split_type ins_split; 871 enum ocfs2_append_type ins_appending; 872 enum ocfs2_contig_type ins_contig; 873 int ins_contig_index; 874 int ins_tree_depth; 875 }; 876 877 struct ocfs2_merge_ctxt { 878 enum ocfs2_contig_type c_contig_type; 879 int c_has_empty_extent; 880 int c_split_covers_rec; 881 }; 882 883 static int ocfs2_validate_extent_block(struct super_block *sb, 884 struct buffer_head *bh) 885 { 886 int rc; 887 struct ocfs2_extent_block *eb = 888 (struct ocfs2_extent_block *)bh->b_data; 889 890 trace_ocfs2_validate_extent_block((unsigned long long)bh->b_blocknr); 891 892 BUG_ON(!buffer_uptodate(bh)); 893 894 /* 895 * If the ecc fails, we return the error but otherwise 896 * leave the filesystem running. We know any error is 897 * local to this block. 898 */ 899 rc = ocfs2_validate_meta_ecc(sb, bh->b_data, &eb->h_check); 900 if (rc) { 901 mlog(ML_ERROR, "Checksum failed for extent block %llu\n", 902 (unsigned long long)bh->b_blocknr); 903 return rc; 904 } 905 906 /* 907 * Errors after here are fatal. 908 */ 909 910 if (!OCFS2_IS_VALID_EXTENT_BLOCK(eb)) { 911 ocfs2_error(sb, 912 "Extent block #%llu has bad signature %.*s", 913 (unsigned long long)bh->b_blocknr, 7, 914 eb->h_signature); 915 return -EINVAL; 916 } 917 918 if (le64_to_cpu(eb->h_blkno) != bh->b_blocknr) { 919 ocfs2_error(sb, 920 "Extent block #%llu has an invalid h_blkno " 921 "of %llu", 922 (unsigned long long)bh->b_blocknr, 923 (unsigned long long)le64_to_cpu(eb->h_blkno)); 924 return -EINVAL; 925 } 926 927 if (le32_to_cpu(eb->h_fs_generation) != OCFS2_SB(sb)->fs_generation) { 928 ocfs2_error(sb, 929 "Extent block #%llu has an invalid " 930 "h_fs_generation of #%u", 931 (unsigned long long)bh->b_blocknr, 932 le32_to_cpu(eb->h_fs_generation)); 933 return -EINVAL; 934 } 935 936 return 0; 937 } 938 939 int ocfs2_read_extent_block(struct ocfs2_caching_info *ci, u64 eb_blkno, 940 struct buffer_head **bh) 941 { 942 int rc; 943 struct buffer_head *tmp = *bh; 944 945 rc = ocfs2_read_block(ci, eb_blkno, &tmp, 946 ocfs2_validate_extent_block); 947 948 /* If ocfs2_read_block() got us a new bh, pass it up. */ 949 if (!rc && !*bh) 950 *bh = tmp; 951 952 return rc; 953 } 954 955 956 /* 957 * How many free extents have we got before we need more meta data? 958 */ 959 int ocfs2_num_free_extents(struct ocfs2_super *osb, 960 struct ocfs2_extent_tree *et) 961 { 962 int retval; 963 struct ocfs2_extent_list *el = NULL; 964 struct ocfs2_extent_block *eb; 965 struct buffer_head *eb_bh = NULL; 966 u64 last_eb_blk = 0; 967 968 el = et->et_root_el; 969 last_eb_blk = ocfs2_et_get_last_eb_blk(et); 970 971 if (last_eb_blk) { 972 retval = ocfs2_read_extent_block(et->et_ci, last_eb_blk, 973 &eb_bh); 974 if (retval < 0) { 975 mlog_errno(retval); 976 goto bail; 977 } 978 eb = (struct ocfs2_extent_block *) eb_bh->b_data; 979 el = &eb->h_list; 980 } 981 982 BUG_ON(el->l_tree_depth != 0); 983 984 retval = le16_to_cpu(el->l_count) - le16_to_cpu(el->l_next_free_rec); 985 bail: 986 brelse(eb_bh); 987 988 trace_ocfs2_num_free_extents(retval); 989 return retval; 990 } 991 992 /* expects array to already be allocated 993 * 994 * sets h_signature, h_blkno, h_suballoc_bit, h_suballoc_slot, and 995 * l_count for you 996 */ 997 static int ocfs2_create_new_meta_bhs(handle_t *handle, 998 struct ocfs2_extent_tree *et, 999 int wanted, 1000 struct ocfs2_alloc_context *meta_ac, 1001 struct buffer_head *bhs[]) 1002 { 1003 int count, status, i; 1004 u16 suballoc_bit_start; 1005 u32 num_got; 1006 u64 suballoc_loc, first_blkno; 1007 struct ocfs2_super *osb = 1008 OCFS2_SB(ocfs2_metadata_cache_get_super(et->et_ci)); 1009 struct ocfs2_extent_block *eb; 1010 1011 count = 0; 1012 while (count < wanted) { 1013 status = ocfs2_claim_metadata(handle, 1014 meta_ac, 1015 wanted - count, 1016 &suballoc_loc, 1017 &suballoc_bit_start, 1018 &num_got, 1019 &first_blkno); 1020 if (status < 0) { 1021 mlog_errno(status); 1022 goto bail; 1023 } 1024 1025 for(i = count; i < (num_got + count); i++) { 1026 bhs[i] = sb_getblk(osb->sb, first_blkno); 1027 if (bhs[i] == NULL) { 1028 status = -ENOMEM; 1029 mlog_errno(status); 1030 goto bail; 1031 } 1032 ocfs2_set_new_buffer_uptodate(et->et_ci, bhs[i]); 1033 1034 status = ocfs2_journal_access_eb(handle, et->et_ci, 1035 bhs[i], 1036 OCFS2_JOURNAL_ACCESS_CREATE); 1037 if (status < 0) { 1038 mlog_errno(status); 1039 goto bail; 1040 } 1041 1042 memset(bhs[i]->b_data, 0, osb->sb->s_blocksize); 1043 eb = (struct ocfs2_extent_block *) bhs[i]->b_data; 1044 /* Ok, setup the minimal stuff here. */ 1045 strcpy(eb->h_signature, OCFS2_EXTENT_BLOCK_SIGNATURE); 1046 eb->h_blkno = cpu_to_le64(first_blkno); 1047 eb->h_fs_generation = cpu_to_le32(osb->fs_generation); 1048 eb->h_suballoc_slot = 1049 cpu_to_le16(meta_ac->ac_alloc_slot); 1050 eb->h_suballoc_loc = cpu_to_le64(suballoc_loc); 1051 eb->h_suballoc_bit = cpu_to_le16(suballoc_bit_start); 1052 eb->h_list.l_count = 1053 cpu_to_le16(ocfs2_extent_recs_per_eb(osb->sb)); 1054 1055 suballoc_bit_start++; 1056 first_blkno++; 1057 1058 /* We'll also be dirtied by the caller, so 1059 * this isn't absolutely necessary. */ 1060 ocfs2_journal_dirty(handle, bhs[i]); 1061 } 1062 1063 count += num_got; 1064 } 1065 1066 status = 0; 1067 bail: 1068 if (status < 0) { 1069 for(i = 0; i < wanted; i++) { 1070 brelse(bhs[i]); 1071 bhs[i] = NULL; 1072 } 1073 mlog_errno(status); 1074 } 1075 return status; 1076 } 1077 1078 /* 1079 * Helper function for ocfs2_add_branch() and ocfs2_shift_tree_depth(). 1080 * 1081 * Returns the sum of the rightmost extent rec logical offset and 1082 * cluster count. 1083 * 1084 * ocfs2_add_branch() uses this to determine what logical cluster 1085 * value should be populated into the leftmost new branch records. 1086 * 1087 * ocfs2_shift_tree_depth() uses this to determine the # clusters 1088 * value for the new topmost tree record. 1089 */ 1090 static inline u32 ocfs2_sum_rightmost_rec(struct ocfs2_extent_list *el) 1091 { 1092 int i; 1093 1094 i = le16_to_cpu(el->l_next_free_rec) - 1; 1095 1096 return le32_to_cpu(el->l_recs[i].e_cpos) + 1097 ocfs2_rec_clusters(el, &el->l_recs[i]); 1098 } 1099 1100 /* 1101 * Change range of the branches in the right most path according to the leaf 1102 * extent block's rightmost record. 1103 */ 1104 static int ocfs2_adjust_rightmost_branch(handle_t *handle, 1105 struct ocfs2_extent_tree *et) 1106 { 1107 int status; 1108 struct ocfs2_path *path = NULL; 1109 struct ocfs2_extent_list *el; 1110 struct ocfs2_extent_rec *rec; 1111 1112 path = ocfs2_new_path_from_et(et); 1113 if (!path) { 1114 status = -ENOMEM; 1115 return status; 1116 } 1117 1118 status = ocfs2_find_path(et->et_ci, path, UINT_MAX); 1119 if (status < 0) { 1120 mlog_errno(status); 1121 goto out; 1122 } 1123 1124 status = ocfs2_extend_trans(handle, path_num_items(path)); 1125 if (status < 0) { 1126 mlog_errno(status); 1127 goto out; 1128 } 1129 1130 status = ocfs2_journal_access_path(et->et_ci, handle, path); 1131 if (status < 0) { 1132 mlog_errno(status); 1133 goto out; 1134 } 1135 1136 el = path_leaf_el(path); 1137 rec = &el->l_recs[le16_to_cpu(el->l_next_free_rec) - 1]; 1138 1139 ocfs2_adjust_rightmost_records(handle, et, path, rec); 1140 1141 out: 1142 ocfs2_free_path(path); 1143 return status; 1144 } 1145 1146 /* 1147 * Add an entire tree branch to our inode. eb_bh is the extent block 1148 * to start at, if we don't want to start the branch at the root 1149 * structure. 1150 * 1151 * last_eb_bh is required as we have to update it's next_leaf pointer 1152 * for the new last extent block. 1153 * 1154 * the new branch will be 'empty' in the sense that every block will 1155 * contain a single record with cluster count == 0. 1156 */ 1157 static int ocfs2_add_branch(handle_t *handle, 1158 struct ocfs2_extent_tree *et, 1159 struct buffer_head *eb_bh, 1160 struct buffer_head **last_eb_bh, 1161 struct ocfs2_alloc_context *meta_ac) 1162 { 1163 int status, new_blocks, i; 1164 u64 next_blkno, new_last_eb_blk; 1165 struct buffer_head *bh; 1166 struct buffer_head **new_eb_bhs = NULL; 1167 struct ocfs2_extent_block *eb; 1168 struct ocfs2_extent_list *eb_el; 1169 struct ocfs2_extent_list *el; 1170 u32 new_cpos, root_end; 1171 1172 BUG_ON(!last_eb_bh || !*last_eb_bh); 1173 1174 if (eb_bh) { 1175 eb = (struct ocfs2_extent_block *) eb_bh->b_data; 1176 el = &eb->h_list; 1177 } else 1178 el = et->et_root_el; 1179 1180 /* we never add a branch to a leaf. */ 1181 BUG_ON(!el->l_tree_depth); 1182 1183 new_blocks = le16_to_cpu(el->l_tree_depth); 1184 1185 eb = (struct ocfs2_extent_block *)(*last_eb_bh)->b_data; 1186 new_cpos = ocfs2_sum_rightmost_rec(&eb->h_list); 1187 root_end = ocfs2_sum_rightmost_rec(et->et_root_el); 1188 1189 /* 1190 * If there is a gap before the root end and the real end 1191 * of the righmost leaf block, we need to remove the gap 1192 * between new_cpos and root_end first so that the tree 1193 * is consistent after we add a new branch(it will start 1194 * from new_cpos). 1195 */ 1196 if (root_end > new_cpos) { 1197 trace_ocfs2_adjust_rightmost_branch( 1198 (unsigned long long) 1199 ocfs2_metadata_cache_owner(et->et_ci), 1200 root_end, new_cpos); 1201 1202 status = ocfs2_adjust_rightmost_branch(handle, et); 1203 if (status) { 1204 mlog_errno(status); 1205 goto bail; 1206 } 1207 } 1208 1209 /* allocate the number of new eb blocks we need */ 1210 new_eb_bhs = kcalloc(new_blocks, sizeof(struct buffer_head *), 1211 GFP_KERNEL); 1212 if (!new_eb_bhs) { 1213 status = -ENOMEM; 1214 mlog_errno(status); 1215 goto bail; 1216 } 1217 1218 status = ocfs2_create_new_meta_bhs(handle, et, new_blocks, 1219 meta_ac, new_eb_bhs); 1220 if (status < 0) { 1221 mlog_errno(status); 1222 goto bail; 1223 } 1224 1225 /* Note: new_eb_bhs[new_blocks - 1] is the guy which will be 1226 * linked with the rest of the tree. 1227 * conversly, new_eb_bhs[0] is the new bottommost leaf. 1228 * 1229 * when we leave the loop, new_last_eb_blk will point to the 1230 * newest leaf, and next_blkno will point to the topmost extent 1231 * block. */ 1232 next_blkno = new_last_eb_blk = 0; 1233 for(i = 0; i < new_blocks; i++) { 1234 bh = new_eb_bhs[i]; 1235 eb = (struct ocfs2_extent_block *) bh->b_data; 1236 /* ocfs2_create_new_meta_bhs() should create it right! */ 1237 BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb)); 1238 eb_el = &eb->h_list; 1239 1240 status = ocfs2_journal_access_eb(handle, et->et_ci, bh, 1241 OCFS2_JOURNAL_ACCESS_CREATE); 1242 if (status < 0) { 1243 mlog_errno(status); 1244 goto bail; 1245 } 1246 1247 eb->h_next_leaf_blk = 0; 1248 eb_el->l_tree_depth = cpu_to_le16(i); 1249 eb_el->l_next_free_rec = cpu_to_le16(1); 1250 /* 1251 * This actually counts as an empty extent as 1252 * c_clusters == 0 1253 */ 1254 eb_el->l_recs[0].e_cpos = cpu_to_le32(new_cpos); 1255 eb_el->l_recs[0].e_blkno = cpu_to_le64(next_blkno); 1256 /* 1257 * eb_el isn't always an interior node, but even leaf 1258 * nodes want a zero'd flags and reserved field so 1259 * this gets the whole 32 bits regardless of use. 1260 */ 1261 eb_el->l_recs[0].e_int_clusters = cpu_to_le32(0); 1262 if (!eb_el->l_tree_depth) 1263 new_last_eb_blk = le64_to_cpu(eb->h_blkno); 1264 1265 ocfs2_journal_dirty(handle, bh); 1266 next_blkno = le64_to_cpu(eb->h_blkno); 1267 } 1268 1269 /* This is a bit hairy. We want to update up to three blocks 1270 * here without leaving any of them in an inconsistent state 1271 * in case of error. We don't have to worry about 1272 * journal_dirty erroring as it won't unless we've aborted the 1273 * handle (in which case we would never be here) so reserving 1274 * the write with journal_access is all we need to do. */ 1275 status = ocfs2_journal_access_eb(handle, et->et_ci, *last_eb_bh, 1276 OCFS2_JOURNAL_ACCESS_WRITE); 1277 if (status < 0) { 1278 mlog_errno(status); 1279 goto bail; 1280 } 1281 status = ocfs2_et_root_journal_access(handle, et, 1282 OCFS2_JOURNAL_ACCESS_WRITE); 1283 if (status < 0) { 1284 mlog_errno(status); 1285 goto bail; 1286 } 1287 if (eb_bh) { 1288 status = ocfs2_journal_access_eb(handle, et->et_ci, eb_bh, 1289 OCFS2_JOURNAL_ACCESS_WRITE); 1290 if (status < 0) { 1291 mlog_errno(status); 1292 goto bail; 1293 } 1294 } 1295 1296 /* Link the new branch into the rest of the tree (el will 1297 * either be on the root_bh, or the extent block passed in. */ 1298 i = le16_to_cpu(el->l_next_free_rec); 1299 el->l_recs[i].e_blkno = cpu_to_le64(next_blkno); 1300 el->l_recs[i].e_cpos = cpu_to_le32(new_cpos); 1301 el->l_recs[i].e_int_clusters = 0; 1302 le16_add_cpu(&el->l_next_free_rec, 1); 1303 1304 /* fe needs a new last extent block pointer, as does the 1305 * next_leaf on the previously last-extent-block. */ 1306 ocfs2_et_set_last_eb_blk(et, new_last_eb_blk); 1307 1308 eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data; 1309 eb->h_next_leaf_blk = cpu_to_le64(new_last_eb_blk); 1310 1311 ocfs2_journal_dirty(handle, *last_eb_bh); 1312 ocfs2_journal_dirty(handle, et->et_root_bh); 1313 if (eb_bh) 1314 ocfs2_journal_dirty(handle, eb_bh); 1315 1316 /* 1317 * Some callers want to track the rightmost leaf so pass it 1318 * back here. 1319 */ 1320 brelse(*last_eb_bh); 1321 get_bh(new_eb_bhs[0]); 1322 *last_eb_bh = new_eb_bhs[0]; 1323 1324 status = 0; 1325 bail: 1326 if (new_eb_bhs) { 1327 for (i = 0; i < new_blocks; i++) 1328 brelse(new_eb_bhs[i]); 1329 kfree(new_eb_bhs); 1330 } 1331 1332 return status; 1333 } 1334 1335 /* 1336 * adds another level to the allocation tree. 1337 * returns back the new extent block so you can add a branch to it 1338 * after this call. 1339 */ 1340 static int ocfs2_shift_tree_depth(handle_t *handle, 1341 struct ocfs2_extent_tree *et, 1342 struct ocfs2_alloc_context *meta_ac, 1343 struct buffer_head **ret_new_eb_bh) 1344 { 1345 int status, i; 1346 u32 new_clusters; 1347 struct buffer_head *new_eb_bh = NULL; 1348 struct ocfs2_extent_block *eb; 1349 struct ocfs2_extent_list *root_el; 1350 struct ocfs2_extent_list *eb_el; 1351 1352 status = ocfs2_create_new_meta_bhs(handle, et, 1, meta_ac, 1353 &new_eb_bh); 1354 if (status < 0) { 1355 mlog_errno(status); 1356 goto bail; 1357 } 1358 1359 eb = (struct ocfs2_extent_block *) new_eb_bh->b_data; 1360 /* ocfs2_create_new_meta_bhs() should create it right! */ 1361 BUG_ON(!OCFS2_IS_VALID_EXTENT_BLOCK(eb)); 1362 1363 eb_el = &eb->h_list; 1364 root_el = et->et_root_el; 1365 1366 status = ocfs2_journal_access_eb(handle, et->et_ci, new_eb_bh, 1367 OCFS2_JOURNAL_ACCESS_CREATE); 1368 if (status < 0) { 1369 mlog_errno(status); 1370 goto bail; 1371 } 1372 1373 /* copy the root extent list data into the new extent block */ 1374 eb_el->l_tree_depth = root_el->l_tree_depth; 1375 eb_el->l_next_free_rec = root_el->l_next_free_rec; 1376 for (i = 0; i < le16_to_cpu(root_el->l_next_free_rec); i++) 1377 eb_el->l_recs[i] = root_el->l_recs[i]; 1378 1379 ocfs2_journal_dirty(handle, new_eb_bh); 1380 1381 status = ocfs2_et_root_journal_access(handle, et, 1382 OCFS2_JOURNAL_ACCESS_WRITE); 1383 if (status < 0) { 1384 mlog_errno(status); 1385 goto bail; 1386 } 1387 1388 new_clusters = ocfs2_sum_rightmost_rec(eb_el); 1389 1390 /* update root_bh now */ 1391 le16_add_cpu(&root_el->l_tree_depth, 1); 1392 root_el->l_recs[0].e_cpos = 0; 1393 root_el->l_recs[0].e_blkno = eb->h_blkno; 1394 root_el->l_recs[0].e_int_clusters = cpu_to_le32(new_clusters); 1395 for (i = 1; i < le16_to_cpu(root_el->l_next_free_rec); i++) 1396 memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec)); 1397 root_el->l_next_free_rec = cpu_to_le16(1); 1398 1399 /* If this is our 1st tree depth shift, then last_eb_blk 1400 * becomes the allocated extent block */ 1401 if (root_el->l_tree_depth == cpu_to_le16(1)) 1402 ocfs2_et_set_last_eb_blk(et, le64_to_cpu(eb->h_blkno)); 1403 1404 ocfs2_journal_dirty(handle, et->et_root_bh); 1405 1406 *ret_new_eb_bh = new_eb_bh; 1407 new_eb_bh = NULL; 1408 status = 0; 1409 bail: 1410 brelse(new_eb_bh); 1411 1412 return status; 1413 } 1414 1415 /* 1416 * Should only be called when there is no space left in any of the 1417 * leaf nodes. What we want to do is find the lowest tree depth 1418 * non-leaf extent block with room for new records. There are three 1419 * valid results of this search: 1420 * 1421 * 1) a lowest extent block is found, then we pass it back in 1422 * *lowest_eb_bh and return '0' 1423 * 1424 * 2) the search fails to find anything, but the root_el has room. We 1425 * pass NULL back in *lowest_eb_bh, but still return '0' 1426 * 1427 * 3) the search fails to find anything AND the root_el is full, in 1428 * which case we return > 0 1429 * 1430 * return status < 0 indicates an error. 1431 */ 1432 static int ocfs2_find_branch_target(struct ocfs2_extent_tree *et, 1433 struct buffer_head **target_bh) 1434 { 1435 int status = 0, i; 1436 u64 blkno; 1437 struct ocfs2_extent_block *eb; 1438 struct ocfs2_extent_list *el; 1439 struct buffer_head *bh = NULL; 1440 struct buffer_head *lowest_bh = NULL; 1441 1442 *target_bh = NULL; 1443 1444 el = et->et_root_el; 1445 1446 while(le16_to_cpu(el->l_tree_depth) > 1) { 1447 if (le16_to_cpu(el->l_next_free_rec) == 0) { 1448 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 1449 "Owner %llu has empty " 1450 "extent list (next_free_rec == 0)", 1451 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci)); 1452 status = -EIO; 1453 goto bail; 1454 } 1455 i = le16_to_cpu(el->l_next_free_rec) - 1; 1456 blkno = le64_to_cpu(el->l_recs[i].e_blkno); 1457 if (!blkno) { 1458 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 1459 "Owner %llu has extent " 1460 "list where extent # %d has no physical " 1461 "block start", 1462 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), i); 1463 status = -EIO; 1464 goto bail; 1465 } 1466 1467 brelse(bh); 1468 bh = NULL; 1469 1470 status = ocfs2_read_extent_block(et->et_ci, blkno, &bh); 1471 if (status < 0) { 1472 mlog_errno(status); 1473 goto bail; 1474 } 1475 1476 eb = (struct ocfs2_extent_block *) bh->b_data; 1477 el = &eb->h_list; 1478 1479 if (le16_to_cpu(el->l_next_free_rec) < 1480 le16_to_cpu(el->l_count)) { 1481 brelse(lowest_bh); 1482 lowest_bh = bh; 1483 get_bh(lowest_bh); 1484 } 1485 } 1486 1487 /* If we didn't find one and the fe doesn't have any room, 1488 * then return '1' */ 1489 el = et->et_root_el; 1490 if (!lowest_bh && (el->l_next_free_rec == el->l_count)) 1491 status = 1; 1492 1493 *target_bh = lowest_bh; 1494 bail: 1495 brelse(bh); 1496 1497 return status; 1498 } 1499 1500 /* 1501 * Grow a b-tree so that it has more records. 1502 * 1503 * We might shift the tree depth in which case existing paths should 1504 * be considered invalid. 1505 * 1506 * Tree depth after the grow is returned via *final_depth. 1507 * 1508 * *last_eb_bh will be updated by ocfs2_add_branch(). 1509 */ 1510 static int ocfs2_grow_tree(handle_t *handle, struct ocfs2_extent_tree *et, 1511 int *final_depth, struct buffer_head **last_eb_bh, 1512 struct ocfs2_alloc_context *meta_ac) 1513 { 1514 int ret, shift; 1515 struct ocfs2_extent_list *el = et->et_root_el; 1516 int depth = le16_to_cpu(el->l_tree_depth); 1517 struct buffer_head *bh = NULL; 1518 1519 BUG_ON(meta_ac == NULL); 1520 1521 shift = ocfs2_find_branch_target(et, &bh); 1522 if (shift < 0) { 1523 ret = shift; 1524 mlog_errno(ret); 1525 goto out; 1526 } 1527 1528 /* We traveled all the way to the bottom of the allocation tree 1529 * and didn't find room for any more extents - we need to add 1530 * another tree level */ 1531 if (shift) { 1532 BUG_ON(bh); 1533 trace_ocfs2_grow_tree( 1534 (unsigned long long) 1535 ocfs2_metadata_cache_owner(et->et_ci), 1536 depth); 1537 1538 /* ocfs2_shift_tree_depth will return us a buffer with 1539 * the new extent block (so we can pass that to 1540 * ocfs2_add_branch). */ 1541 ret = ocfs2_shift_tree_depth(handle, et, meta_ac, &bh); 1542 if (ret < 0) { 1543 mlog_errno(ret); 1544 goto out; 1545 } 1546 depth++; 1547 if (depth == 1) { 1548 /* 1549 * Special case: we have room now if we shifted from 1550 * tree_depth 0, so no more work needs to be done. 1551 * 1552 * We won't be calling add_branch, so pass 1553 * back *last_eb_bh as the new leaf. At depth 1554 * zero, it should always be null so there's 1555 * no reason to brelse. 1556 */ 1557 BUG_ON(*last_eb_bh); 1558 get_bh(bh); 1559 *last_eb_bh = bh; 1560 goto out; 1561 } 1562 } 1563 1564 /* call ocfs2_add_branch to add the final part of the tree with 1565 * the new data. */ 1566 ret = ocfs2_add_branch(handle, et, bh, last_eb_bh, 1567 meta_ac); 1568 if (ret < 0) { 1569 mlog_errno(ret); 1570 goto out; 1571 } 1572 1573 out: 1574 if (final_depth) 1575 *final_depth = depth; 1576 brelse(bh); 1577 return ret; 1578 } 1579 1580 /* 1581 * This function will discard the rightmost extent record. 1582 */ 1583 static void ocfs2_shift_records_right(struct ocfs2_extent_list *el) 1584 { 1585 int next_free = le16_to_cpu(el->l_next_free_rec); 1586 int count = le16_to_cpu(el->l_count); 1587 unsigned int num_bytes; 1588 1589 BUG_ON(!next_free); 1590 /* This will cause us to go off the end of our extent list. */ 1591 BUG_ON(next_free >= count); 1592 1593 num_bytes = sizeof(struct ocfs2_extent_rec) * next_free; 1594 1595 memmove(&el->l_recs[1], &el->l_recs[0], num_bytes); 1596 } 1597 1598 static void ocfs2_rotate_leaf(struct ocfs2_extent_list *el, 1599 struct ocfs2_extent_rec *insert_rec) 1600 { 1601 int i, insert_index, next_free, has_empty, num_bytes; 1602 u32 insert_cpos = le32_to_cpu(insert_rec->e_cpos); 1603 struct ocfs2_extent_rec *rec; 1604 1605 next_free = le16_to_cpu(el->l_next_free_rec); 1606 has_empty = ocfs2_is_empty_extent(&el->l_recs[0]); 1607 1608 BUG_ON(!next_free); 1609 1610 /* The tree code before us didn't allow enough room in the leaf. */ 1611 BUG_ON(el->l_next_free_rec == el->l_count && !has_empty); 1612 1613 /* 1614 * The easiest way to approach this is to just remove the 1615 * empty extent and temporarily decrement next_free. 1616 */ 1617 if (has_empty) { 1618 /* 1619 * If next_free was 1 (only an empty extent), this 1620 * loop won't execute, which is fine. We still want 1621 * the decrement above to happen. 1622 */ 1623 for(i = 0; i < (next_free - 1); i++) 1624 el->l_recs[i] = el->l_recs[i+1]; 1625 1626 next_free--; 1627 } 1628 1629 /* 1630 * Figure out what the new record index should be. 1631 */ 1632 for(i = 0; i < next_free; i++) { 1633 rec = &el->l_recs[i]; 1634 1635 if (insert_cpos < le32_to_cpu(rec->e_cpos)) 1636 break; 1637 } 1638 insert_index = i; 1639 1640 trace_ocfs2_rotate_leaf(insert_cpos, insert_index, 1641 has_empty, next_free, 1642 le16_to_cpu(el->l_count)); 1643 1644 BUG_ON(insert_index < 0); 1645 BUG_ON(insert_index >= le16_to_cpu(el->l_count)); 1646 BUG_ON(insert_index > next_free); 1647 1648 /* 1649 * No need to memmove if we're just adding to the tail. 1650 */ 1651 if (insert_index != next_free) { 1652 BUG_ON(next_free >= le16_to_cpu(el->l_count)); 1653 1654 num_bytes = next_free - insert_index; 1655 num_bytes *= sizeof(struct ocfs2_extent_rec); 1656 memmove(&el->l_recs[insert_index + 1], 1657 &el->l_recs[insert_index], 1658 num_bytes); 1659 } 1660 1661 /* 1662 * Either we had an empty extent, and need to re-increment or 1663 * there was no empty extent on a non full rightmost leaf node, 1664 * in which case we still need to increment. 1665 */ 1666 next_free++; 1667 el->l_next_free_rec = cpu_to_le16(next_free); 1668 /* 1669 * Make sure none of the math above just messed up our tree. 1670 */ 1671 BUG_ON(le16_to_cpu(el->l_next_free_rec) > le16_to_cpu(el->l_count)); 1672 1673 el->l_recs[insert_index] = *insert_rec; 1674 1675 } 1676 1677 static void ocfs2_remove_empty_extent(struct ocfs2_extent_list *el) 1678 { 1679 int size, num_recs = le16_to_cpu(el->l_next_free_rec); 1680 1681 BUG_ON(num_recs == 0); 1682 1683 if (ocfs2_is_empty_extent(&el->l_recs[0])) { 1684 num_recs--; 1685 size = num_recs * sizeof(struct ocfs2_extent_rec); 1686 memmove(&el->l_recs[0], &el->l_recs[1], size); 1687 memset(&el->l_recs[num_recs], 0, 1688 sizeof(struct ocfs2_extent_rec)); 1689 el->l_next_free_rec = cpu_to_le16(num_recs); 1690 } 1691 } 1692 1693 /* 1694 * Create an empty extent record . 1695 * 1696 * l_next_free_rec may be updated. 1697 * 1698 * If an empty extent already exists do nothing. 1699 */ 1700 static void ocfs2_create_empty_extent(struct ocfs2_extent_list *el) 1701 { 1702 int next_free = le16_to_cpu(el->l_next_free_rec); 1703 1704 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 1705 1706 if (next_free == 0) 1707 goto set_and_inc; 1708 1709 if (ocfs2_is_empty_extent(&el->l_recs[0])) 1710 return; 1711 1712 mlog_bug_on_msg(el->l_count == el->l_next_free_rec, 1713 "Asked to create an empty extent in a full list:\n" 1714 "count = %u, tree depth = %u", 1715 le16_to_cpu(el->l_count), 1716 le16_to_cpu(el->l_tree_depth)); 1717 1718 ocfs2_shift_records_right(el); 1719 1720 set_and_inc: 1721 le16_add_cpu(&el->l_next_free_rec, 1); 1722 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 1723 } 1724 1725 /* 1726 * For a rotation which involves two leaf nodes, the "root node" is 1727 * the lowest level tree node which contains a path to both leafs. This 1728 * resulting set of information can be used to form a complete "subtree" 1729 * 1730 * This function is passed two full paths from the dinode down to a 1731 * pair of adjacent leaves. It's task is to figure out which path 1732 * index contains the subtree root - this can be the root index itself 1733 * in a worst-case rotation. 1734 * 1735 * The array index of the subtree root is passed back. 1736 */ 1737 int ocfs2_find_subtree_root(struct ocfs2_extent_tree *et, 1738 struct ocfs2_path *left, 1739 struct ocfs2_path *right) 1740 { 1741 int i = 0; 1742 1743 /* 1744 * Check that the caller passed in two paths from the same tree. 1745 */ 1746 BUG_ON(path_root_bh(left) != path_root_bh(right)); 1747 1748 do { 1749 i++; 1750 1751 /* 1752 * The caller didn't pass two adjacent paths. 1753 */ 1754 mlog_bug_on_msg(i > left->p_tree_depth, 1755 "Owner %llu, left depth %u, right depth %u\n" 1756 "left leaf blk %llu, right leaf blk %llu\n", 1757 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 1758 left->p_tree_depth, right->p_tree_depth, 1759 (unsigned long long)path_leaf_bh(left)->b_blocknr, 1760 (unsigned long long)path_leaf_bh(right)->b_blocknr); 1761 } while (left->p_node[i].bh->b_blocknr == 1762 right->p_node[i].bh->b_blocknr); 1763 1764 return i - 1; 1765 } 1766 1767 typedef void (path_insert_t)(void *, struct buffer_head *); 1768 1769 /* 1770 * Traverse a btree path in search of cpos, starting at root_el. 1771 * 1772 * This code can be called with a cpos larger than the tree, in which 1773 * case it will return the rightmost path. 1774 */ 1775 static int __ocfs2_find_path(struct ocfs2_caching_info *ci, 1776 struct ocfs2_extent_list *root_el, u32 cpos, 1777 path_insert_t *func, void *data) 1778 { 1779 int i, ret = 0; 1780 u32 range; 1781 u64 blkno; 1782 struct buffer_head *bh = NULL; 1783 struct ocfs2_extent_block *eb; 1784 struct ocfs2_extent_list *el; 1785 struct ocfs2_extent_rec *rec; 1786 1787 el = root_el; 1788 while (el->l_tree_depth) { 1789 if (le16_to_cpu(el->l_next_free_rec) == 0) { 1790 ocfs2_error(ocfs2_metadata_cache_get_super(ci), 1791 "Owner %llu has empty extent list at " 1792 "depth %u\n", 1793 (unsigned long long)ocfs2_metadata_cache_owner(ci), 1794 le16_to_cpu(el->l_tree_depth)); 1795 ret = -EROFS; 1796 goto out; 1797 1798 } 1799 1800 for(i = 0; i < le16_to_cpu(el->l_next_free_rec) - 1; i++) { 1801 rec = &el->l_recs[i]; 1802 1803 /* 1804 * In the case that cpos is off the allocation 1805 * tree, this should just wind up returning the 1806 * rightmost record. 1807 */ 1808 range = le32_to_cpu(rec->e_cpos) + 1809 ocfs2_rec_clusters(el, rec); 1810 if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range) 1811 break; 1812 } 1813 1814 blkno = le64_to_cpu(el->l_recs[i].e_blkno); 1815 if (blkno == 0) { 1816 ocfs2_error(ocfs2_metadata_cache_get_super(ci), 1817 "Owner %llu has bad blkno in extent list " 1818 "at depth %u (index %d)\n", 1819 (unsigned long long)ocfs2_metadata_cache_owner(ci), 1820 le16_to_cpu(el->l_tree_depth), i); 1821 ret = -EROFS; 1822 goto out; 1823 } 1824 1825 brelse(bh); 1826 bh = NULL; 1827 ret = ocfs2_read_extent_block(ci, blkno, &bh); 1828 if (ret) { 1829 mlog_errno(ret); 1830 goto out; 1831 } 1832 1833 eb = (struct ocfs2_extent_block *) bh->b_data; 1834 el = &eb->h_list; 1835 1836 if (le16_to_cpu(el->l_next_free_rec) > 1837 le16_to_cpu(el->l_count)) { 1838 ocfs2_error(ocfs2_metadata_cache_get_super(ci), 1839 "Owner %llu has bad count in extent list " 1840 "at block %llu (next free=%u, count=%u)\n", 1841 (unsigned long long)ocfs2_metadata_cache_owner(ci), 1842 (unsigned long long)bh->b_blocknr, 1843 le16_to_cpu(el->l_next_free_rec), 1844 le16_to_cpu(el->l_count)); 1845 ret = -EROFS; 1846 goto out; 1847 } 1848 1849 if (func) 1850 func(data, bh); 1851 } 1852 1853 out: 1854 /* 1855 * Catch any trailing bh that the loop didn't handle. 1856 */ 1857 brelse(bh); 1858 1859 return ret; 1860 } 1861 1862 /* 1863 * Given an initialized path (that is, it has a valid root extent 1864 * list), this function will traverse the btree in search of the path 1865 * which would contain cpos. 1866 * 1867 * The path traveled is recorded in the path structure. 1868 * 1869 * Note that this will not do any comparisons on leaf node extent 1870 * records, so it will work fine in the case that we just added a tree 1871 * branch. 1872 */ 1873 struct find_path_data { 1874 int index; 1875 struct ocfs2_path *path; 1876 }; 1877 static void find_path_ins(void *data, struct buffer_head *bh) 1878 { 1879 struct find_path_data *fp = data; 1880 1881 get_bh(bh); 1882 ocfs2_path_insert_eb(fp->path, fp->index, bh); 1883 fp->index++; 1884 } 1885 int ocfs2_find_path(struct ocfs2_caching_info *ci, 1886 struct ocfs2_path *path, u32 cpos) 1887 { 1888 struct find_path_data data; 1889 1890 data.index = 1; 1891 data.path = path; 1892 return __ocfs2_find_path(ci, path_root_el(path), cpos, 1893 find_path_ins, &data); 1894 } 1895 1896 static void find_leaf_ins(void *data, struct buffer_head *bh) 1897 { 1898 struct ocfs2_extent_block *eb =(struct ocfs2_extent_block *)bh->b_data; 1899 struct ocfs2_extent_list *el = &eb->h_list; 1900 struct buffer_head **ret = data; 1901 1902 /* We want to retain only the leaf block. */ 1903 if (le16_to_cpu(el->l_tree_depth) == 0) { 1904 get_bh(bh); 1905 *ret = bh; 1906 } 1907 } 1908 /* 1909 * Find the leaf block in the tree which would contain cpos. No 1910 * checking of the actual leaf is done. 1911 * 1912 * Some paths want to call this instead of allocating a path structure 1913 * and calling ocfs2_find_path(). 1914 * 1915 * This function doesn't handle non btree extent lists. 1916 */ 1917 int ocfs2_find_leaf(struct ocfs2_caching_info *ci, 1918 struct ocfs2_extent_list *root_el, u32 cpos, 1919 struct buffer_head **leaf_bh) 1920 { 1921 int ret; 1922 struct buffer_head *bh = NULL; 1923 1924 ret = __ocfs2_find_path(ci, root_el, cpos, find_leaf_ins, &bh); 1925 if (ret) { 1926 mlog_errno(ret); 1927 goto out; 1928 } 1929 1930 *leaf_bh = bh; 1931 out: 1932 return ret; 1933 } 1934 1935 /* 1936 * Adjust the adjacent records (left_rec, right_rec) involved in a rotation. 1937 * 1938 * Basically, we've moved stuff around at the bottom of the tree and 1939 * we need to fix up the extent records above the changes to reflect 1940 * the new changes. 1941 * 1942 * left_rec: the record on the left. 1943 * left_child_el: is the child list pointed to by left_rec 1944 * right_rec: the record to the right of left_rec 1945 * right_child_el: is the child list pointed to by right_rec 1946 * 1947 * By definition, this only works on interior nodes. 1948 */ 1949 static void ocfs2_adjust_adjacent_records(struct ocfs2_extent_rec *left_rec, 1950 struct ocfs2_extent_list *left_child_el, 1951 struct ocfs2_extent_rec *right_rec, 1952 struct ocfs2_extent_list *right_child_el) 1953 { 1954 u32 left_clusters, right_end; 1955 1956 /* 1957 * Interior nodes never have holes. Their cpos is the cpos of 1958 * the leftmost record in their child list. Their cluster 1959 * count covers the full theoretical range of their child list 1960 * - the range between their cpos and the cpos of the record 1961 * immediately to their right. 1962 */ 1963 left_clusters = le32_to_cpu(right_child_el->l_recs[0].e_cpos); 1964 if (!ocfs2_rec_clusters(right_child_el, &right_child_el->l_recs[0])) { 1965 BUG_ON(right_child_el->l_tree_depth); 1966 BUG_ON(le16_to_cpu(right_child_el->l_next_free_rec) <= 1); 1967 left_clusters = le32_to_cpu(right_child_el->l_recs[1].e_cpos); 1968 } 1969 left_clusters -= le32_to_cpu(left_rec->e_cpos); 1970 left_rec->e_int_clusters = cpu_to_le32(left_clusters); 1971 1972 /* 1973 * Calculate the rightmost cluster count boundary before 1974 * moving cpos - we will need to adjust clusters after 1975 * updating e_cpos to keep the same highest cluster count. 1976 */ 1977 right_end = le32_to_cpu(right_rec->e_cpos); 1978 right_end += le32_to_cpu(right_rec->e_int_clusters); 1979 1980 right_rec->e_cpos = left_rec->e_cpos; 1981 le32_add_cpu(&right_rec->e_cpos, left_clusters); 1982 1983 right_end -= le32_to_cpu(right_rec->e_cpos); 1984 right_rec->e_int_clusters = cpu_to_le32(right_end); 1985 } 1986 1987 /* 1988 * Adjust the adjacent root node records involved in a 1989 * rotation. left_el_blkno is passed in as a key so that we can easily 1990 * find it's index in the root list. 1991 */ 1992 static void ocfs2_adjust_root_records(struct ocfs2_extent_list *root_el, 1993 struct ocfs2_extent_list *left_el, 1994 struct ocfs2_extent_list *right_el, 1995 u64 left_el_blkno) 1996 { 1997 int i; 1998 1999 BUG_ON(le16_to_cpu(root_el->l_tree_depth) <= 2000 le16_to_cpu(left_el->l_tree_depth)); 2001 2002 for(i = 0; i < le16_to_cpu(root_el->l_next_free_rec) - 1; i++) { 2003 if (le64_to_cpu(root_el->l_recs[i].e_blkno) == left_el_blkno) 2004 break; 2005 } 2006 2007 /* 2008 * The path walking code should have never returned a root and 2009 * two paths which are not adjacent. 2010 */ 2011 BUG_ON(i >= (le16_to_cpu(root_el->l_next_free_rec) - 1)); 2012 2013 ocfs2_adjust_adjacent_records(&root_el->l_recs[i], left_el, 2014 &root_el->l_recs[i + 1], right_el); 2015 } 2016 2017 /* 2018 * We've changed a leaf block (in right_path) and need to reflect that 2019 * change back up the subtree. 2020 * 2021 * This happens in multiple places: 2022 * - When we've moved an extent record from the left path leaf to the right 2023 * path leaf to make room for an empty extent in the left path leaf. 2024 * - When our insert into the right path leaf is at the leftmost edge 2025 * and requires an update of the path immediately to it's left. This 2026 * can occur at the end of some types of rotation and appending inserts. 2027 * - When we've adjusted the last extent record in the left path leaf and the 2028 * 1st extent record in the right path leaf during cross extent block merge. 2029 */ 2030 static void ocfs2_complete_edge_insert(handle_t *handle, 2031 struct ocfs2_path *left_path, 2032 struct ocfs2_path *right_path, 2033 int subtree_index) 2034 { 2035 int i, idx; 2036 struct ocfs2_extent_list *el, *left_el, *right_el; 2037 struct ocfs2_extent_rec *left_rec, *right_rec; 2038 struct buffer_head *root_bh = left_path->p_node[subtree_index].bh; 2039 2040 /* 2041 * Update the counts and position values within all the 2042 * interior nodes to reflect the leaf rotation we just did. 2043 * 2044 * The root node is handled below the loop. 2045 * 2046 * We begin the loop with right_el and left_el pointing to the 2047 * leaf lists and work our way up. 2048 * 2049 * NOTE: within this loop, left_el and right_el always refer 2050 * to the *child* lists. 2051 */ 2052 left_el = path_leaf_el(left_path); 2053 right_el = path_leaf_el(right_path); 2054 for(i = left_path->p_tree_depth - 1; i > subtree_index; i--) { 2055 trace_ocfs2_complete_edge_insert(i); 2056 2057 /* 2058 * One nice property of knowing that all of these 2059 * nodes are below the root is that we only deal with 2060 * the leftmost right node record and the rightmost 2061 * left node record. 2062 */ 2063 el = left_path->p_node[i].el; 2064 idx = le16_to_cpu(left_el->l_next_free_rec) - 1; 2065 left_rec = &el->l_recs[idx]; 2066 2067 el = right_path->p_node[i].el; 2068 right_rec = &el->l_recs[0]; 2069 2070 ocfs2_adjust_adjacent_records(left_rec, left_el, right_rec, 2071 right_el); 2072 2073 ocfs2_journal_dirty(handle, left_path->p_node[i].bh); 2074 ocfs2_journal_dirty(handle, right_path->p_node[i].bh); 2075 2076 /* 2077 * Setup our list pointers now so that the current 2078 * parents become children in the next iteration. 2079 */ 2080 left_el = left_path->p_node[i].el; 2081 right_el = right_path->p_node[i].el; 2082 } 2083 2084 /* 2085 * At the root node, adjust the two adjacent records which 2086 * begin our path to the leaves. 2087 */ 2088 2089 el = left_path->p_node[subtree_index].el; 2090 left_el = left_path->p_node[subtree_index + 1].el; 2091 right_el = right_path->p_node[subtree_index + 1].el; 2092 2093 ocfs2_adjust_root_records(el, left_el, right_el, 2094 left_path->p_node[subtree_index + 1].bh->b_blocknr); 2095 2096 root_bh = left_path->p_node[subtree_index].bh; 2097 2098 ocfs2_journal_dirty(handle, root_bh); 2099 } 2100 2101 static int ocfs2_rotate_subtree_right(handle_t *handle, 2102 struct ocfs2_extent_tree *et, 2103 struct ocfs2_path *left_path, 2104 struct ocfs2_path *right_path, 2105 int subtree_index) 2106 { 2107 int ret, i; 2108 struct buffer_head *right_leaf_bh; 2109 struct buffer_head *left_leaf_bh = NULL; 2110 struct buffer_head *root_bh; 2111 struct ocfs2_extent_list *right_el, *left_el; 2112 struct ocfs2_extent_rec move_rec; 2113 2114 left_leaf_bh = path_leaf_bh(left_path); 2115 left_el = path_leaf_el(left_path); 2116 2117 if (left_el->l_next_free_rec != left_el->l_count) { 2118 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 2119 "Inode %llu has non-full interior leaf node %llu" 2120 "(next free = %u)", 2121 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 2122 (unsigned long long)left_leaf_bh->b_blocknr, 2123 le16_to_cpu(left_el->l_next_free_rec)); 2124 return -EROFS; 2125 } 2126 2127 /* 2128 * This extent block may already have an empty record, so we 2129 * return early if so. 2130 */ 2131 if (ocfs2_is_empty_extent(&left_el->l_recs[0])) 2132 return 0; 2133 2134 root_bh = left_path->p_node[subtree_index].bh; 2135 BUG_ON(root_bh != right_path->p_node[subtree_index].bh); 2136 2137 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path, 2138 subtree_index); 2139 if (ret) { 2140 mlog_errno(ret); 2141 goto out; 2142 } 2143 2144 for(i = subtree_index + 1; i < path_num_items(right_path); i++) { 2145 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 2146 right_path, i); 2147 if (ret) { 2148 mlog_errno(ret); 2149 goto out; 2150 } 2151 2152 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 2153 left_path, i); 2154 if (ret) { 2155 mlog_errno(ret); 2156 goto out; 2157 } 2158 } 2159 2160 right_leaf_bh = path_leaf_bh(right_path); 2161 right_el = path_leaf_el(right_path); 2162 2163 /* This is a code error, not a disk corruption. */ 2164 mlog_bug_on_msg(!right_el->l_next_free_rec, "Inode %llu: Rotate fails " 2165 "because rightmost leaf block %llu is empty\n", 2166 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 2167 (unsigned long long)right_leaf_bh->b_blocknr); 2168 2169 ocfs2_create_empty_extent(right_el); 2170 2171 ocfs2_journal_dirty(handle, right_leaf_bh); 2172 2173 /* Do the copy now. */ 2174 i = le16_to_cpu(left_el->l_next_free_rec) - 1; 2175 move_rec = left_el->l_recs[i]; 2176 right_el->l_recs[0] = move_rec; 2177 2178 /* 2179 * Clear out the record we just copied and shift everything 2180 * over, leaving an empty extent in the left leaf. 2181 * 2182 * We temporarily subtract from next_free_rec so that the 2183 * shift will lose the tail record (which is now defunct). 2184 */ 2185 le16_add_cpu(&left_el->l_next_free_rec, -1); 2186 ocfs2_shift_records_right(left_el); 2187 memset(&left_el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 2188 le16_add_cpu(&left_el->l_next_free_rec, 1); 2189 2190 ocfs2_journal_dirty(handle, left_leaf_bh); 2191 2192 ocfs2_complete_edge_insert(handle, left_path, right_path, 2193 subtree_index); 2194 2195 out: 2196 return ret; 2197 } 2198 2199 /* 2200 * Given a full path, determine what cpos value would return us a path 2201 * containing the leaf immediately to the left of the current one. 2202 * 2203 * Will return zero if the path passed in is already the leftmost path. 2204 */ 2205 int ocfs2_find_cpos_for_left_leaf(struct super_block *sb, 2206 struct ocfs2_path *path, u32 *cpos) 2207 { 2208 int i, j, ret = 0; 2209 u64 blkno; 2210 struct ocfs2_extent_list *el; 2211 2212 BUG_ON(path->p_tree_depth == 0); 2213 2214 *cpos = 0; 2215 2216 blkno = path_leaf_bh(path)->b_blocknr; 2217 2218 /* Start at the tree node just above the leaf and work our way up. */ 2219 i = path->p_tree_depth - 1; 2220 while (i >= 0) { 2221 el = path->p_node[i].el; 2222 2223 /* 2224 * Find the extent record just before the one in our 2225 * path. 2226 */ 2227 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) { 2228 if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) { 2229 if (j == 0) { 2230 if (i == 0) { 2231 /* 2232 * We've determined that the 2233 * path specified is already 2234 * the leftmost one - return a 2235 * cpos of zero. 2236 */ 2237 goto out; 2238 } 2239 /* 2240 * The leftmost record points to our 2241 * leaf - we need to travel up the 2242 * tree one level. 2243 */ 2244 goto next_node; 2245 } 2246 2247 *cpos = le32_to_cpu(el->l_recs[j - 1].e_cpos); 2248 *cpos = *cpos + ocfs2_rec_clusters(el, 2249 &el->l_recs[j - 1]); 2250 *cpos = *cpos - 1; 2251 goto out; 2252 } 2253 } 2254 2255 /* 2256 * If we got here, we never found a valid node where 2257 * the tree indicated one should be. 2258 */ 2259 ocfs2_error(sb, 2260 "Invalid extent tree at extent block %llu\n", 2261 (unsigned long long)blkno); 2262 ret = -EROFS; 2263 goto out; 2264 2265 next_node: 2266 blkno = path->p_node[i].bh->b_blocknr; 2267 i--; 2268 } 2269 2270 out: 2271 return ret; 2272 } 2273 2274 /* 2275 * Extend the transaction by enough credits to complete the rotation, 2276 * and still leave at least the original number of credits allocated 2277 * to this transaction. 2278 */ 2279 static int ocfs2_extend_rotate_transaction(handle_t *handle, int subtree_depth, 2280 int op_credits, 2281 struct ocfs2_path *path) 2282 { 2283 int ret = 0; 2284 int credits = (path->p_tree_depth - subtree_depth) * 2 + 1 + op_credits; 2285 2286 if (handle->h_buffer_credits < credits) 2287 ret = ocfs2_extend_trans(handle, 2288 credits - handle->h_buffer_credits); 2289 2290 return ret; 2291 } 2292 2293 /* 2294 * Trap the case where we're inserting into the theoretical range past 2295 * the _actual_ left leaf range. Otherwise, we'll rotate a record 2296 * whose cpos is less than ours into the right leaf. 2297 * 2298 * It's only necessary to look at the rightmost record of the left 2299 * leaf because the logic that calls us should ensure that the 2300 * theoretical ranges in the path components above the leaves are 2301 * correct. 2302 */ 2303 static int ocfs2_rotate_requires_path_adjustment(struct ocfs2_path *left_path, 2304 u32 insert_cpos) 2305 { 2306 struct ocfs2_extent_list *left_el; 2307 struct ocfs2_extent_rec *rec; 2308 int next_free; 2309 2310 left_el = path_leaf_el(left_path); 2311 next_free = le16_to_cpu(left_el->l_next_free_rec); 2312 rec = &left_el->l_recs[next_free - 1]; 2313 2314 if (insert_cpos > le32_to_cpu(rec->e_cpos)) 2315 return 1; 2316 return 0; 2317 } 2318 2319 static int ocfs2_leftmost_rec_contains(struct ocfs2_extent_list *el, u32 cpos) 2320 { 2321 int next_free = le16_to_cpu(el->l_next_free_rec); 2322 unsigned int range; 2323 struct ocfs2_extent_rec *rec; 2324 2325 if (next_free == 0) 2326 return 0; 2327 2328 rec = &el->l_recs[0]; 2329 if (ocfs2_is_empty_extent(rec)) { 2330 /* Empty list. */ 2331 if (next_free == 1) 2332 return 0; 2333 rec = &el->l_recs[1]; 2334 } 2335 2336 range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec); 2337 if (cpos >= le32_to_cpu(rec->e_cpos) && cpos < range) 2338 return 1; 2339 return 0; 2340 } 2341 2342 /* 2343 * Rotate all the records in a btree right one record, starting at insert_cpos. 2344 * 2345 * The path to the rightmost leaf should be passed in. 2346 * 2347 * The array is assumed to be large enough to hold an entire path (tree depth). 2348 * 2349 * Upon successful return from this function: 2350 * 2351 * - The 'right_path' array will contain a path to the leaf block 2352 * whose range contains e_cpos. 2353 * - That leaf block will have a single empty extent in list index 0. 2354 * - In the case that the rotation requires a post-insert update, 2355 * *ret_left_path will contain a valid path which can be passed to 2356 * ocfs2_insert_path(). 2357 */ 2358 static int ocfs2_rotate_tree_right(handle_t *handle, 2359 struct ocfs2_extent_tree *et, 2360 enum ocfs2_split_type split, 2361 u32 insert_cpos, 2362 struct ocfs2_path *right_path, 2363 struct ocfs2_path **ret_left_path) 2364 { 2365 int ret, start, orig_credits = handle->h_buffer_credits; 2366 u32 cpos; 2367 struct ocfs2_path *left_path = NULL; 2368 struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci); 2369 2370 *ret_left_path = NULL; 2371 2372 left_path = ocfs2_new_path_from_path(right_path); 2373 if (!left_path) { 2374 ret = -ENOMEM; 2375 mlog_errno(ret); 2376 goto out; 2377 } 2378 2379 ret = ocfs2_find_cpos_for_left_leaf(sb, right_path, &cpos); 2380 if (ret) { 2381 mlog_errno(ret); 2382 goto out; 2383 } 2384 2385 trace_ocfs2_rotate_tree_right( 2386 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 2387 insert_cpos, cpos); 2388 2389 /* 2390 * What we want to do here is: 2391 * 2392 * 1) Start with the rightmost path. 2393 * 2394 * 2) Determine a path to the leaf block directly to the left 2395 * of that leaf. 2396 * 2397 * 3) Determine the 'subtree root' - the lowest level tree node 2398 * which contains a path to both leaves. 2399 * 2400 * 4) Rotate the subtree. 2401 * 2402 * 5) Find the next subtree by considering the left path to be 2403 * the new right path. 2404 * 2405 * The check at the top of this while loop also accepts 2406 * insert_cpos == cpos because cpos is only a _theoretical_ 2407 * value to get us the left path - insert_cpos might very well 2408 * be filling that hole. 2409 * 2410 * Stop at a cpos of '0' because we either started at the 2411 * leftmost branch (i.e., a tree with one branch and a 2412 * rotation inside of it), or we've gone as far as we can in 2413 * rotating subtrees. 2414 */ 2415 while (cpos && insert_cpos <= cpos) { 2416 trace_ocfs2_rotate_tree_right( 2417 (unsigned long long) 2418 ocfs2_metadata_cache_owner(et->et_ci), 2419 insert_cpos, cpos); 2420 2421 ret = ocfs2_find_path(et->et_ci, left_path, cpos); 2422 if (ret) { 2423 mlog_errno(ret); 2424 goto out; 2425 } 2426 2427 mlog_bug_on_msg(path_leaf_bh(left_path) == 2428 path_leaf_bh(right_path), 2429 "Owner %llu: error during insert of %u " 2430 "(left path cpos %u) results in two identical " 2431 "paths ending at %llu\n", 2432 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 2433 insert_cpos, cpos, 2434 (unsigned long long) 2435 path_leaf_bh(left_path)->b_blocknr); 2436 2437 if (split == SPLIT_NONE && 2438 ocfs2_rotate_requires_path_adjustment(left_path, 2439 insert_cpos)) { 2440 2441 /* 2442 * We've rotated the tree as much as we 2443 * should. The rest is up to 2444 * ocfs2_insert_path() to complete, after the 2445 * record insertion. We indicate this 2446 * situation by returning the left path. 2447 * 2448 * The reason we don't adjust the records here 2449 * before the record insert is that an error 2450 * later might break the rule where a parent 2451 * record e_cpos will reflect the actual 2452 * e_cpos of the 1st nonempty record of the 2453 * child list. 2454 */ 2455 *ret_left_path = left_path; 2456 goto out_ret_path; 2457 } 2458 2459 start = ocfs2_find_subtree_root(et, left_path, right_path); 2460 2461 trace_ocfs2_rotate_subtree(start, 2462 (unsigned long long) 2463 right_path->p_node[start].bh->b_blocknr, 2464 right_path->p_tree_depth); 2465 2466 ret = ocfs2_extend_rotate_transaction(handle, start, 2467 orig_credits, right_path); 2468 if (ret) { 2469 mlog_errno(ret); 2470 goto out; 2471 } 2472 2473 ret = ocfs2_rotate_subtree_right(handle, et, left_path, 2474 right_path, start); 2475 if (ret) { 2476 mlog_errno(ret); 2477 goto out; 2478 } 2479 2480 if (split != SPLIT_NONE && 2481 ocfs2_leftmost_rec_contains(path_leaf_el(right_path), 2482 insert_cpos)) { 2483 /* 2484 * A rotate moves the rightmost left leaf 2485 * record over to the leftmost right leaf 2486 * slot. If we're doing an extent split 2487 * instead of a real insert, then we have to 2488 * check that the extent to be split wasn't 2489 * just moved over. If it was, then we can 2490 * exit here, passing left_path back - 2491 * ocfs2_split_extent() is smart enough to 2492 * search both leaves. 2493 */ 2494 *ret_left_path = left_path; 2495 goto out_ret_path; 2496 } 2497 2498 /* 2499 * There is no need to re-read the next right path 2500 * as we know that it'll be our current left 2501 * path. Optimize by copying values instead. 2502 */ 2503 ocfs2_mv_path(right_path, left_path); 2504 2505 ret = ocfs2_find_cpos_for_left_leaf(sb, right_path, &cpos); 2506 if (ret) { 2507 mlog_errno(ret); 2508 goto out; 2509 } 2510 } 2511 2512 out: 2513 ocfs2_free_path(left_path); 2514 2515 out_ret_path: 2516 return ret; 2517 } 2518 2519 static int ocfs2_update_edge_lengths(handle_t *handle, 2520 struct ocfs2_extent_tree *et, 2521 int subtree_index, struct ocfs2_path *path) 2522 { 2523 int i, idx, ret; 2524 struct ocfs2_extent_rec *rec; 2525 struct ocfs2_extent_list *el; 2526 struct ocfs2_extent_block *eb; 2527 u32 range; 2528 2529 /* 2530 * In normal tree rotation process, we will never touch the 2531 * tree branch above subtree_index and ocfs2_extend_rotate_transaction 2532 * doesn't reserve the credits for them either. 2533 * 2534 * But we do have a special case here which will update the rightmost 2535 * records for all the bh in the path. 2536 * So we have to allocate extra credits and access them. 2537 */ 2538 ret = ocfs2_extend_trans(handle, subtree_index); 2539 if (ret) { 2540 mlog_errno(ret); 2541 goto out; 2542 } 2543 2544 ret = ocfs2_journal_access_path(et->et_ci, handle, path); 2545 if (ret) { 2546 mlog_errno(ret); 2547 goto out; 2548 } 2549 2550 /* Path should always be rightmost. */ 2551 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data; 2552 BUG_ON(eb->h_next_leaf_blk != 0ULL); 2553 2554 el = &eb->h_list; 2555 BUG_ON(le16_to_cpu(el->l_next_free_rec) == 0); 2556 idx = le16_to_cpu(el->l_next_free_rec) - 1; 2557 rec = &el->l_recs[idx]; 2558 range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec); 2559 2560 for (i = 0; i < path->p_tree_depth; i++) { 2561 el = path->p_node[i].el; 2562 idx = le16_to_cpu(el->l_next_free_rec) - 1; 2563 rec = &el->l_recs[idx]; 2564 2565 rec->e_int_clusters = cpu_to_le32(range); 2566 le32_add_cpu(&rec->e_int_clusters, -le32_to_cpu(rec->e_cpos)); 2567 2568 ocfs2_journal_dirty(handle, path->p_node[i].bh); 2569 } 2570 out: 2571 return ret; 2572 } 2573 2574 static void ocfs2_unlink_path(handle_t *handle, 2575 struct ocfs2_extent_tree *et, 2576 struct ocfs2_cached_dealloc_ctxt *dealloc, 2577 struct ocfs2_path *path, int unlink_start) 2578 { 2579 int ret, i; 2580 struct ocfs2_extent_block *eb; 2581 struct ocfs2_extent_list *el; 2582 struct buffer_head *bh; 2583 2584 for(i = unlink_start; i < path_num_items(path); i++) { 2585 bh = path->p_node[i].bh; 2586 2587 eb = (struct ocfs2_extent_block *)bh->b_data; 2588 /* 2589 * Not all nodes might have had their final count 2590 * decremented by the caller - handle this here. 2591 */ 2592 el = &eb->h_list; 2593 if (le16_to_cpu(el->l_next_free_rec) > 1) { 2594 mlog(ML_ERROR, 2595 "Inode %llu, attempted to remove extent block " 2596 "%llu with %u records\n", 2597 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 2598 (unsigned long long)le64_to_cpu(eb->h_blkno), 2599 le16_to_cpu(el->l_next_free_rec)); 2600 2601 ocfs2_journal_dirty(handle, bh); 2602 ocfs2_remove_from_cache(et->et_ci, bh); 2603 continue; 2604 } 2605 2606 el->l_next_free_rec = 0; 2607 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 2608 2609 ocfs2_journal_dirty(handle, bh); 2610 2611 ret = ocfs2_cache_extent_block_free(dealloc, eb); 2612 if (ret) 2613 mlog_errno(ret); 2614 2615 ocfs2_remove_from_cache(et->et_ci, bh); 2616 } 2617 } 2618 2619 static void ocfs2_unlink_subtree(handle_t *handle, 2620 struct ocfs2_extent_tree *et, 2621 struct ocfs2_path *left_path, 2622 struct ocfs2_path *right_path, 2623 int subtree_index, 2624 struct ocfs2_cached_dealloc_ctxt *dealloc) 2625 { 2626 int i; 2627 struct buffer_head *root_bh = left_path->p_node[subtree_index].bh; 2628 struct ocfs2_extent_list *root_el = left_path->p_node[subtree_index].el; 2629 struct ocfs2_extent_list *el; 2630 struct ocfs2_extent_block *eb; 2631 2632 el = path_leaf_el(left_path); 2633 2634 eb = (struct ocfs2_extent_block *)right_path->p_node[subtree_index + 1].bh->b_data; 2635 2636 for(i = 1; i < le16_to_cpu(root_el->l_next_free_rec); i++) 2637 if (root_el->l_recs[i].e_blkno == eb->h_blkno) 2638 break; 2639 2640 BUG_ON(i >= le16_to_cpu(root_el->l_next_free_rec)); 2641 2642 memset(&root_el->l_recs[i], 0, sizeof(struct ocfs2_extent_rec)); 2643 le16_add_cpu(&root_el->l_next_free_rec, -1); 2644 2645 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data; 2646 eb->h_next_leaf_blk = 0; 2647 2648 ocfs2_journal_dirty(handle, root_bh); 2649 ocfs2_journal_dirty(handle, path_leaf_bh(left_path)); 2650 2651 ocfs2_unlink_path(handle, et, dealloc, right_path, 2652 subtree_index + 1); 2653 } 2654 2655 static int ocfs2_rotate_subtree_left(handle_t *handle, 2656 struct ocfs2_extent_tree *et, 2657 struct ocfs2_path *left_path, 2658 struct ocfs2_path *right_path, 2659 int subtree_index, 2660 struct ocfs2_cached_dealloc_ctxt *dealloc, 2661 int *deleted) 2662 { 2663 int ret, i, del_right_subtree = 0, right_has_empty = 0; 2664 struct buffer_head *root_bh, *et_root_bh = path_root_bh(right_path); 2665 struct ocfs2_extent_list *right_leaf_el, *left_leaf_el; 2666 struct ocfs2_extent_block *eb; 2667 2668 *deleted = 0; 2669 2670 right_leaf_el = path_leaf_el(right_path); 2671 left_leaf_el = path_leaf_el(left_path); 2672 root_bh = left_path->p_node[subtree_index].bh; 2673 BUG_ON(root_bh != right_path->p_node[subtree_index].bh); 2674 2675 if (!ocfs2_is_empty_extent(&left_leaf_el->l_recs[0])) 2676 return 0; 2677 2678 eb = (struct ocfs2_extent_block *)path_leaf_bh(right_path)->b_data; 2679 if (ocfs2_is_empty_extent(&right_leaf_el->l_recs[0])) { 2680 /* 2681 * It's legal for us to proceed if the right leaf is 2682 * the rightmost one and it has an empty extent. There 2683 * are two cases to handle - whether the leaf will be 2684 * empty after removal or not. If the leaf isn't empty 2685 * then just remove the empty extent up front. The 2686 * next block will handle empty leaves by flagging 2687 * them for unlink. 2688 * 2689 * Non rightmost leaves will throw -EAGAIN and the 2690 * caller can manually move the subtree and retry. 2691 */ 2692 2693 if (eb->h_next_leaf_blk != 0ULL) 2694 return -EAGAIN; 2695 2696 if (le16_to_cpu(right_leaf_el->l_next_free_rec) > 1) { 2697 ret = ocfs2_journal_access_eb(handle, et->et_ci, 2698 path_leaf_bh(right_path), 2699 OCFS2_JOURNAL_ACCESS_WRITE); 2700 if (ret) { 2701 mlog_errno(ret); 2702 goto out; 2703 } 2704 2705 ocfs2_remove_empty_extent(right_leaf_el); 2706 } else 2707 right_has_empty = 1; 2708 } 2709 2710 if (eb->h_next_leaf_blk == 0ULL && 2711 le16_to_cpu(right_leaf_el->l_next_free_rec) == 1) { 2712 /* 2713 * We have to update i_last_eb_blk during the meta 2714 * data delete. 2715 */ 2716 ret = ocfs2_et_root_journal_access(handle, et, 2717 OCFS2_JOURNAL_ACCESS_WRITE); 2718 if (ret) { 2719 mlog_errno(ret); 2720 goto out; 2721 } 2722 2723 del_right_subtree = 1; 2724 } 2725 2726 /* 2727 * Getting here with an empty extent in the right path implies 2728 * that it's the rightmost path and will be deleted. 2729 */ 2730 BUG_ON(right_has_empty && !del_right_subtree); 2731 2732 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path, 2733 subtree_index); 2734 if (ret) { 2735 mlog_errno(ret); 2736 goto out; 2737 } 2738 2739 for(i = subtree_index + 1; i < path_num_items(right_path); i++) { 2740 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 2741 right_path, i); 2742 if (ret) { 2743 mlog_errno(ret); 2744 goto out; 2745 } 2746 2747 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 2748 left_path, i); 2749 if (ret) { 2750 mlog_errno(ret); 2751 goto out; 2752 } 2753 } 2754 2755 if (!right_has_empty) { 2756 /* 2757 * Only do this if we're moving a real 2758 * record. Otherwise, the action is delayed until 2759 * after removal of the right path in which case we 2760 * can do a simple shift to remove the empty extent. 2761 */ 2762 ocfs2_rotate_leaf(left_leaf_el, &right_leaf_el->l_recs[0]); 2763 memset(&right_leaf_el->l_recs[0], 0, 2764 sizeof(struct ocfs2_extent_rec)); 2765 } 2766 if (eb->h_next_leaf_blk == 0ULL) { 2767 /* 2768 * Move recs over to get rid of empty extent, decrease 2769 * next_free. This is allowed to remove the last 2770 * extent in our leaf (setting l_next_free_rec to 2771 * zero) - the delete code below won't care. 2772 */ 2773 ocfs2_remove_empty_extent(right_leaf_el); 2774 } 2775 2776 ocfs2_journal_dirty(handle, path_leaf_bh(left_path)); 2777 ocfs2_journal_dirty(handle, path_leaf_bh(right_path)); 2778 2779 if (del_right_subtree) { 2780 ocfs2_unlink_subtree(handle, et, left_path, right_path, 2781 subtree_index, dealloc); 2782 ret = ocfs2_update_edge_lengths(handle, et, subtree_index, 2783 left_path); 2784 if (ret) { 2785 mlog_errno(ret); 2786 goto out; 2787 } 2788 2789 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data; 2790 ocfs2_et_set_last_eb_blk(et, le64_to_cpu(eb->h_blkno)); 2791 2792 /* 2793 * Removal of the extent in the left leaf was skipped 2794 * above so we could delete the right path 2795 * 1st. 2796 */ 2797 if (right_has_empty) 2798 ocfs2_remove_empty_extent(left_leaf_el); 2799 2800 ocfs2_journal_dirty(handle, et_root_bh); 2801 2802 *deleted = 1; 2803 } else 2804 ocfs2_complete_edge_insert(handle, left_path, right_path, 2805 subtree_index); 2806 2807 out: 2808 return ret; 2809 } 2810 2811 /* 2812 * Given a full path, determine what cpos value would return us a path 2813 * containing the leaf immediately to the right of the current one. 2814 * 2815 * Will return zero if the path passed in is already the rightmost path. 2816 * 2817 * This looks similar, but is subtly different to 2818 * ocfs2_find_cpos_for_left_leaf(). 2819 */ 2820 int ocfs2_find_cpos_for_right_leaf(struct super_block *sb, 2821 struct ocfs2_path *path, u32 *cpos) 2822 { 2823 int i, j, ret = 0; 2824 u64 blkno; 2825 struct ocfs2_extent_list *el; 2826 2827 *cpos = 0; 2828 2829 if (path->p_tree_depth == 0) 2830 return 0; 2831 2832 blkno = path_leaf_bh(path)->b_blocknr; 2833 2834 /* Start at the tree node just above the leaf and work our way up. */ 2835 i = path->p_tree_depth - 1; 2836 while (i >= 0) { 2837 int next_free; 2838 2839 el = path->p_node[i].el; 2840 2841 /* 2842 * Find the extent record just after the one in our 2843 * path. 2844 */ 2845 next_free = le16_to_cpu(el->l_next_free_rec); 2846 for(j = 0; j < le16_to_cpu(el->l_next_free_rec); j++) { 2847 if (le64_to_cpu(el->l_recs[j].e_blkno) == blkno) { 2848 if (j == (next_free - 1)) { 2849 if (i == 0) { 2850 /* 2851 * We've determined that the 2852 * path specified is already 2853 * the rightmost one - return a 2854 * cpos of zero. 2855 */ 2856 goto out; 2857 } 2858 /* 2859 * The rightmost record points to our 2860 * leaf - we need to travel up the 2861 * tree one level. 2862 */ 2863 goto next_node; 2864 } 2865 2866 *cpos = le32_to_cpu(el->l_recs[j + 1].e_cpos); 2867 goto out; 2868 } 2869 } 2870 2871 /* 2872 * If we got here, we never found a valid node where 2873 * the tree indicated one should be. 2874 */ 2875 ocfs2_error(sb, 2876 "Invalid extent tree at extent block %llu\n", 2877 (unsigned long long)blkno); 2878 ret = -EROFS; 2879 goto out; 2880 2881 next_node: 2882 blkno = path->p_node[i].bh->b_blocknr; 2883 i--; 2884 } 2885 2886 out: 2887 return ret; 2888 } 2889 2890 static int ocfs2_rotate_rightmost_leaf_left(handle_t *handle, 2891 struct ocfs2_extent_tree *et, 2892 struct ocfs2_path *path) 2893 { 2894 int ret; 2895 struct buffer_head *bh = path_leaf_bh(path); 2896 struct ocfs2_extent_list *el = path_leaf_el(path); 2897 2898 if (!ocfs2_is_empty_extent(&el->l_recs[0])) 2899 return 0; 2900 2901 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, path, 2902 path_num_items(path) - 1); 2903 if (ret) { 2904 mlog_errno(ret); 2905 goto out; 2906 } 2907 2908 ocfs2_remove_empty_extent(el); 2909 ocfs2_journal_dirty(handle, bh); 2910 2911 out: 2912 return ret; 2913 } 2914 2915 static int __ocfs2_rotate_tree_left(handle_t *handle, 2916 struct ocfs2_extent_tree *et, 2917 int orig_credits, 2918 struct ocfs2_path *path, 2919 struct ocfs2_cached_dealloc_ctxt *dealloc, 2920 struct ocfs2_path **empty_extent_path) 2921 { 2922 int ret, subtree_root, deleted; 2923 u32 right_cpos; 2924 struct ocfs2_path *left_path = NULL; 2925 struct ocfs2_path *right_path = NULL; 2926 struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci); 2927 2928 if (!ocfs2_is_empty_extent(&(path_leaf_el(path)->l_recs[0]))) 2929 return 0; 2930 2931 *empty_extent_path = NULL; 2932 2933 ret = ocfs2_find_cpos_for_right_leaf(sb, path, &right_cpos); 2934 if (ret) { 2935 mlog_errno(ret); 2936 goto out; 2937 } 2938 2939 left_path = ocfs2_new_path_from_path(path); 2940 if (!left_path) { 2941 ret = -ENOMEM; 2942 mlog_errno(ret); 2943 goto out; 2944 } 2945 2946 ocfs2_cp_path(left_path, path); 2947 2948 right_path = ocfs2_new_path_from_path(path); 2949 if (!right_path) { 2950 ret = -ENOMEM; 2951 mlog_errno(ret); 2952 goto out; 2953 } 2954 2955 while (right_cpos) { 2956 ret = ocfs2_find_path(et->et_ci, right_path, right_cpos); 2957 if (ret) { 2958 mlog_errno(ret); 2959 goto out; 2960 } 2961 2962 subtree_root = ocfs2_find_subtree_root(et, left_path, 2963 right_path); 2964 2965 trace_ocfs2_rotate_subtree(subtree_root, 2966 (unsigned long long) 2967 right_path->p_node[subtree_root].bh->b_blocknr, 2968 right_path->p_tree_depth); 2969 2970 ret = ocfs2_extend_rotate_transaction(handle, subtree_root, 2971 orig_credits, left_path); 2972 if (ret) { 2973 mlog_errno(ret); 2974 goto out; 2975 } 2976 2977 /* 2978 * Caller might still want to make changes to the 2979 * tree root, so re-add it to the journal here. 2980 */ 2981 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 2982 left_path, 0); 2983 if (ret) { 2984 mlog_errno(ret); 2985 goto out; 2986 } 2987 2988 ret = ocfs2_rotate_subtree_left(handle, et, left_path, 2989 right_path, subtree_root, 2990 dealloc, &deleted); 2991 if (ret == -EAGAIN) { 2992 /* 2993 * The rotation has to temporarily stop due to 2994 * the right subtree having an empty 2995 * extent. Pass it back to the caller for a 2996 * fixup. 2997 */ 2998 *empty_extent_path = right_path; 2999 right_path = NULL; 3000 goto out; 3001 } 3002 if (ret) { 3003 mlog_errno(ret); 3004 goto out; 3005 } 3006 3007 /* 3008 * The subtree rotate might have removed records on 3009 * the rightmost edge. If so, then rotation is 3010 * complete. 3011 */ 3012 if (deleted) 3013 break; 3014 3015 ocfs2_mv_path(left_path, right_path); 3016 3017 ret = ocfs2_find_cpos_for_right_leaf(sb, left_path, 3018 &right_cpos); 3019 if (ret) { 3020 mlog_errno(ret); 3021 goto out; 3022 } 3023 } 3024 3025 out: 3026 ocfs2_free_path(right_path); 3027 ocfs2_free_path(left_path); 3028 3029 return ret; 3030 } 3031 3032 static int ocfs2_remove_rightmost_path(handle_t *handle, 3033 struct ocfs2_extent_tree *et, 3034 struct ocfs2_path *path, 3035 struct ocfs2_cached_dealloc_ctxt *dealloc) 3036 { 3037 int ret, subtree_index; 3038 u32 cpos; 3039 struct ocfs2_path *left_path = NULL; 3040 struct ocfs2_extent_block *eb; 3041 struct ocfs2_extent_list *el; 3042 3043 3044 ret = ocfs2_et_sanity_check(et); 3045 if (ret) 3046 goto out; 3047 /* 3048 * There's two ways we handle this depending on 3049 * whether path is the only existing one. 3050 */ 3051 ret = ocfs2_extend_rotate_transaction(handle, 0, 3052 handle->h_buffer_credits, 3053 path); 3054 if (ret) { 3055 mlog_errno(ret); 3056 goto out; 3057 } 3058 3059 ret = ocfs2_journal_access_path(et->et_ci, handle, path); 3060 if (ret) { 3061 mlog_errno(ret); 3062 goto out; 3063 } 3064 3065 ret = ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et->et_ci), 3066 path, &cpos); 3067 if (ret) { 3068 mlog_errno(ret); 3069 goto out; 3070 } 3071 3072 if (cpos) { 3073 /* 3074 * We have a path to the left of this one - it needs 3075 * an update too. 3076 */ 3077 left_path = ocfs2_new_path_from_path(path); 3078 if (!left_path) { 3079 ret = -ENOMEM; 3080 mlog_errno(ret); 3081 goto out; 3082 } 3083 3084 ret = ocfs2_find_path(et->et_ci, left_path, cpos); 3085 if (ret) { 3086 mlog_errno(ret); 3087 goto out; 3088 } 3089 3090 ret = ocfs2_journal_access_path(et->et_ci, handle, left_path); 3091 if (ret) { 3092 mlog_errno(ret); 3093 goto out; 3094 } 3095 3096 subtree_index = ocfs2_find_subtree_root(et, left_path, path); 3097 3098 ocfs2_unlink_subtree(handle, et, left_path, path, 3099 subtree_index, dealloc); 3100 ret = ocfs2_update_edge_lengths(handle, et, subtree_index, 3101 left_path); 3102 if (ret) { 3103 mlog_errno(ret); 3104 goto out; 3105 } 3106 3107 eb = (struct ocfs2_extent_block *)path_leaf_bh(left_path)->b_data; 3108 ocfs2_et_set_last_eb_blk(et, le64_to_cpu(eb->h_blkno)); 3109 } else { 3110 /* 3111 * 'path' is also the leftmost path which 3112 * means it must be the only one. This gets 3113 * handled differently because we want to 3114 * revert the root back to having extents 3115 * in-line. 3116 */ 3117 ocfs2_unlink_path(handle, et, dealloc, path, 1); 3118 3119 el = et->et_root_el; 3120 el->l_tree_depth = 0; 3121 el->l_next_free_rec = 0; 3122 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 3123 3124 ocfs2_et_set_last_eb_blk(et, 0); 3125 } 3126 3127 ocfs2_journal_dirty(handle, path_root_bh(path)); 3128 3129 out: 3130 ocfs2_free_path(left_path); 3131 return ret; 3132 } 3133 3134 /* 3135 * Left rotation of btree records. 3136 * 3137 * In many ways, this is (unsurprisingly) the opposite of right 3138 * rotation. We start at some non-rightmost path containing an empty 3139 * extent in the leaf block. The code works its way to the rightmost 3140 * path by rotating records to the left in every subtree. 3141 * 3142 * This is used by any code which reduces the number of extent records 3143 * in a leaf. After removal, an empty record should be placed in the 3144 * leftmost list position. 3145 * 3146 * This won't handle a length update of the rightmost path records if 3147 * the rightmost tree leaf record is removed so the caller is 3148 * responsible for detecting and correcting that. 3149 */ 3150 static int ocfs2_rotate_tree_left(handle_t *handle, 3151 struct ocfs2_extent_tree *et, 3152 struct ocfs2_path *path, 3153 struct ocfs2_cached_dealloc_ctxt *dealloc) 3154 { 3155 int ret, orig_credits = handle->h_buffer_credits; 3156 struct ocfs2_path *tmp_path = NULL, *restart_path = NULL; 3157 struct ocfs2_extent_block *eb; 3158 struct ocfs2_extent_list *el; 3159 3160 el = path_leaf_el(path); 3161 if (!ocfs2_is_empty_extent(&el->l_recs[0])) 3162 return 0; 3163 3164 if (path->p_tree_depth == 0) { 3165 rightmost_no_delete: 3166 /* 3167 * Inline extents. This is trivially handled, so do 3168 * it up front. 3169 */ 3170 ret = ocfs2_rotate_rightmost_leaf_left(handle, et, path); 3171 if (ret) 3172 mlog_errno(ret); 3173 goto out; 3174 } 3175 3176 /* 3177 * Handle rightmost branch now. There's several cases: 3178 * 1) simple rotation leaving records in there. That's trivial. 3179 * 2) rotation requiring a branch delete - there's no more 3180 * records left. Two cases of this: 3181 * a) There are branches to the left. 3182 * b) This is also the leftmost (the only) branch. 3183 * 3184 * 1) is handled via ocfs2_rotate_rightmost_leaf_left() 3185 * 2a) we need the left branch so that we can update it with the unlink 3186 * 2b) we need to bring the root back to inline extents. 3187 */ 3188 3189 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data; 3190 el = &eb->h_list; 3191 if (eb->h_next_leaf_blk == 0) { 3192 /* 3193 * This gets a bit tricky if we're going to delete the 3194 * rightmost path. Get the other cases out of the way 3195 * 1st. 3196 */ 3197 if (le16_to_cpu(el->l_next_free_rec) > 1) 3198 goto rightmost_no_delete; 3199 3200 if (le16_to_cpu(el->l_next_free_rec) == 0) { 3201 ret = -EIO; 3202 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 3203 "Owner %llu has empty extent block at %llu", 3204 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 3205 (unsigned long long)le64_to_cpu(eb->h_blkno)); 3206 goto out; 3207 } 3208 3209 /* 3210 * XXX: The caller can not trust "path" any more after 3211 * this as it will have been deleted. What do we do? 3212 * 3213 * In theory the rotate-for-merge code will never get 3214 * here because it'll always ask for a rotate in a 3215 * nonempty list. 3216 */ 3217 3218 ret = ocfs2_remove_rightmost_path(handle, et, path, 3219 dealloc); 3220 if (ret) 3221 mlog_errno(ret); 3222 goto out; 3223 } 3224 3225 /* 3226 * Now we can loop, remembering the path we get from -EAGAIN 3227 * and restarting from there. 3228 */ 3229 try_rotate: 3230 ret = __ocfs2_rotate_tree_left(handle, et, orig_credits, path, 3231 dealloc, &restart_path); 3232 if (ret && ret != -EAGAIN) { 3233 mlog_errno(ret); 3234 goto out; 3235 } 3236 3237 while (ret == -EAGAIN) { 3238 tmp_path = restart_path; 3239 restart_path = NULL; 3240 3241 ret = __ocfs2_rotate_tree_left(handle, et, orig_credits, 3242 tmp_path, dealloc, 3243 &restart_path); 3244 if (ret && ret != -EAGAIN) { 3245 mlog_errno(ret); 3246 goto out; 3247 } 3248 3249 ocfs2_free_path(tmp_path); 3250 tmp_path = NULL; 3251 3252 if (ret == 0) 3253 goto try_rotate; 3254 } 3255 3256 out: 3257 ocfs2_free_path(tmp_path); 3258 ocfs2_free_path(restart_path); 3259 return ret; 3260 } 3261 3262 static void ocfs2_cleanup_merge(struct ocfs2_extent_list *el, 3263 int index) 3264 { 3265 struct ocfs2_extent_rec *rec = &el->l_recs[index]; 3266 unsigned int size; 3267 3268 if (rec->e_leaf_clusters == 0) { 3269 /* 3270 * We consumed all of the merged-from record. An empty 3271 * extent cannot exist anywhere but the 1st array 3272 * position, so move things over if the merged-from 3273 * record doesn't occupy that position. 3274 * 3275 * This creates a new empty extent so the caller 3276 * should be smart enough to have removed any existing 3277 * ones. 3278 */ 3279 if (index > 0) { 3280 BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0])); 3281 size = index * sizeof(struct ocfs2_extent_rec); 3282 memmove(&el->l_recs[1], &el->l_recs[0], size); 3283 } 3284 3285 /* 3286 * Always memset - the caller doesn't check whether it 3287 * created an empty extent, so there could be junk in 3288 * the other fields. 3289 */ 3290 memset(&el->l_recs[0], 0, sizeof(struct ocfs2_extent_rec)); 3291 } 3292 } 3293 3294 static int ocfs2_get_right_path(struct ocfs2_extent_tree *et, 3295 struct ocfs2_path *left_path, 3296 struct ocfs2_path **ret_right_path) 3297 { 3298 int ret; 3299 u32 right_cpos; 3300 struct ocfs2_path *right_path = NULL; 3301 struct ocfs2_extent_list *left_el; 3302 3303 *ret_right_path = NULL; 3304 3305 /* This function shouldn't be called for non-trees. */ 3306 BUG_ON(left_path->p_tree_depth == 0); 3307 3308 left_el = path_leaf_el(left_path); 3309 BUG_ON(left_el->l_next_free_rec != left_el->l_count); 3310 3311 ret = ocfs2_find_cpos_for_right_leaf(ocfs2_metadata_cache_get_super(et->et_ci), 3312 left_path, &right_cpos); 3313 if (ret) { 3314 mlog_errno(ret); 3315 goto out; 3316 } 3317 3318 /* This function shouldn't be called for the rightmost leaf. */ 3319 BUG_ON(right_cpos == 0); 3320 3321 right_path = ocfs2_new_path_from_path(left_path); 3322 if (!right_path) { 3323 ret = -ENOMEM; 3324 mlog_errno(ret); 3325 goto out; 3326 } 3327 3328 ret = ocfs2_find_path(et->et_ci, right_path, right_cpos); 3329 if (ret) { 3330 mlog_errno(ret); 3331 goto out; 3332 } 3333 3334 *ret_right_path = right_path; 3335 out: 3336 if (ret) 3337 ocfs2_free_path(right_path); 3338 return ret; 3339 } 3340 3341 /* 3342 * Remove split_rec clusters from the record at index and merge them 3343 * onto the beginning of the record "next" to it. 3344 * For index < l_count - 1, the next means the extent rec at index + 1. 3345 * For index == l_count - 1, the "next" means the 1st extent rec of the 3346 * next extent block. 3347 */ 3348 static int ocfs2_merge_rec_right(struct ocfs2_path *left_path, 3349 handle_t *handle, 3350 struct ocfs2_extent_tree *et, 3351 struct ocfs2_extent_rec *split_rec, 3352 int index) 3353 { 3354 int ret, next_free, i; 3355 unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters); 3356 struct ocfs2_extent_rec *left_rec; 3357 struct ocfs2_extent_rec *right_rec; 3358 struct ocfs2_extent_list *right_el; 3359 struct ocfs2_path *right_path = NULL; 3360 int subtree_index = 0; 3361 struct ocfs2_extent_list *el = path_leaf_el(left_path); 3362 struct buffer_head *bh = path_leaf_bh(left_path); 3363 struct buffer_head *root_bh = NULL; 3364 3365 BUG_ON(index >= le16_to_cpu(el->l_next_free_rec)); 3366 left_rec = &el->l_recs[index]; 3367 3368 if (index == le16_to_cpu(el->l_next_free_rec) - 1 && 3369 le16_to_cpu(el->l_next_free_rec) == le16_to_cpu(el->l_count)) { 3370 /* we meet with a cross extent block merge. */ 3371 ret = ocfs2_get_right_path(et, left_path, &right_path); 3372 if (ret) { 3373 mlog_errno(ret); 3374 return ret; 3375 } 3376 3377 right_el = path_leaf_el(right_path); 3378 next_free = le16_to_cpu(right_el->l_next_free_rec); 3379 BUG_ON(next_free <= 0); 3380 right_rec = &right_el->l_recs[0]; 3381 if (ocfs2_is_empty_extent(right_rec)) { 3382 BUG_ON(next_free <= 1); 3383 right_rec = &right_el->l_recs[1]; 3384 } 3385 3386 BUG_ON(le32_to_cpu(left_rec->e_cpos) + 3387 le16_to_cpu(left_rec->e_leaf_clusters) != 3388 le32_to_cpu(right_rec->e_cpos)); 3389 3390 subtree_index = ocfs2_find_subtree_root(et, left_path, 3391 right_path); 3392 3393 ret = ocfs2_extend_rotate_transaction(handle, subtree_index, 3394 handle->h_buffer_credits, 3395 right_path); 3396 if (ret) { 3397 mlog_errno(ret); 3398 goto out; 3399 } 3400 3401 root_bh = left_path->p_node[subtree_index].bh; 3402 BUG_ON(root_bh != right_path->p_node[subtree_index].bh); 3403 3404 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path, 3405 subtree_index); 3406 if (ret) { 3407 mlog_errno(ret); 3408 goto out; 3409 } 3410 3411 for (i = subtree_index + 1; 3412 i < path_num_items(right_path); i++) { 3413 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 3414 right_path, i); 3415 if (ret) { 3416 mlog_errno(ret); 3417 goto out; 3418 } 3419 3420 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 3421 left_path, i); 3422 if (ret) { 3423 mlog_errno(ret); 3424 goto out; 3425 } 3426 } 3427 3428 } else { 3429 BUG_ON(index == le16_to_cpu(el->l_next_free_rec) - 1); 3430 right_rec = &el->l_recs[index + 1]; 3431 } 3432 3433 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, left_path, 3434 path_num_items(left_path) - 1); 3435 if (ret) { 3436 mlog_errno(ret); 3437 goto out; 3438 } 3439 3440 le16_add_cpu(&left_rec->e_leaf_clusters, -split_clusters); 3441 3442 le32_add_cpu(&right_rec->e_cpos, -split_clusters); 3443 le64_add_cpu(&right_rec->e_blkno, 3444 -ocfs2_clusters_to_blocks(ocfs2_metadata_cache_get_super(et->et_ci), 3445 split_clusters)); 3446 le16_add_cpu(&right_rec->e_leaf_clusters, split_clusters); 3447 3448 ocfs2_cleanup_merge(el, index); 3449 3450 ocfs2_journal_dirty(handle, bh); 3451 if (right_path) { 3452 ocfs2_journal_dirty(handle, path_leaf_bh(right_path)); 3453 ocfs2_complete_edge_insert(handle, left_path, right_path, 3454 subtree_index); 3455 } 3456 out: 3457 ocfs2_free_path(right_path); 3458 return ret; 3459 } 3460 3461 static int ocfs2_get_left_path(struct ocfs2_extent_tree *et, 3462 struct ocfs2_path *right_path, 3463 struct ocfs2_path **ret_left_path) 3464 { 3465 int ret; 3466 u32 left_cpos; 3467 struct ocfs2_path *left_path = NULL; 3468 3469 *ret_left_path = NULL; 3470 3471 /* This function shouldn't be called for non-trees. */ 3472 BUG_ON(right_path->p_tree_depth == 0); 3473 3474 ret = ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et->et_ci), 3475 right_path, &left_cpos); 3476 if (ret) { 3477 mlog_errno(ret); 3478 goto out; 3479 } 3480 3481 /* This function shouldn't be called for the leftmost leaf. */ 3482 BUG_ON(left_cpos == 0); 3483 3484 left_path = ocfs2_new_path_from_path(right_path); 3485 if (!left_path) { 3486 ret = -ENOMEM; 3487 mlog_errno(ret); 3488 goto out; 3489 } 3490 3491 ret = ocfs2_find_path(et->et_ci, left_path, left_cpos); 3492 if (ret) { 3493 mlog_errno(ret); 3494 goto out; 3495 } 3496 3497 *ret_left_path = left_path; 3498 out: 3499 if (ret) 3500 ocfs2_free_path(left_path); 3501 return ret; 3502 } 3503 3504 /* 3505 * Remove split_rec clusters from the record at index and merge them 3506 * onto the tail of the record "before" it. 3507 * For index > 0, the "before" means the extent rec at index - 1. 3508 * 3509 * For index == 0, the "before" means the last record of the previous 3510 * extent block. And there is also a situation that we may need to 3511 * remove the rightmost leaf extent block in the right_path and change 3512 * the right path to indicate the new rightmost path. 3513 */ 3514 static int ocfs2_merge_rec_left(struct ocfs2_path *right_path, 3515 handle_t *handle, 3516 struct ocfs2_extent_tree *et, 3517 struct ocfs2_extent_rec *split_rec, 3518 struct ocfs2_cached_dealloc_ctxt *dealloc, 3519 int index) 3520 { 3521 int ret, i, subtree_index = 0, has_empty_extent = 0; 3522 unsigned int split_clusters = le16_to_cpu(split_rec->e_leaf_clusters); 3523 struct ocfs2_extent_rec *left_rec; 3524 struct ocfs2_extent_rec *right_rec; 3525 struct ocfs2_extent_list *el = path_leaf_el(right_path); 3526 struct buffer_head *bh = path_leaf_bh(right_path); 3527 struct buffer_head *root_bh = NULL; 3528 struct ocfs2_path *left_path = NULL; 3529 struct ocfs2_extent_list *left_el; 3530 3531 BUG_ON(index < 0); 3532 3533 right_rec = &el->l_recs[index]; 3534 if (index == 0) { 3535 /* we meet with a cross extent block merge. */ 3536 ret = ocfs2_get_left_path(et, right_path, &left_path); 3537 if (ret) { 3538 mlog_errno(ret); 3539 return ret; 3540 } 3541 3542 left_el = path_leaf_el(left_path); 3543 BUG_ON(le16_to_cpu(left_el->l_next_free_rec) != 3544 le16_to_cpu(left_el->l_count)); 3545 3546 left_rec = &left_el->l_recs[ 3547 le16_to_cpu(left_el->l_next_free_rec) - 1]; 3548 BUG_ON(le32_to_cpu(left_rec->e_cpos) + 3549 le16_to_cpu(left_rec->e_leaf_clusters) != 3550 le32_to_cpu(split_rec->e_cpos)); 3551 3552 subtree_index = ocfs2_find_subtree_root(et, left_path, 3553 right_path); 3554 3555 ret = ocfs2_extend_rotate_transaction(handle, subtree_index, 3556 handle->h_buffer_credits, 3557 left_path); 3558 if (ret) { 3559 mlog_errno(ret); 3560 goto out; 3561 } 3562 3563 root_bh = left_path->p_node[subtree_index].bh; 3564 BUG_ON(root_bh != right_path->p_node[subtree_index].bh); 3565 3566 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path, 3567 subtree_index); 3568 if (ret) { 3569 mlog_errno(ret); 3570 goto out; 3571 } 3572 3573 for (i = subtree_index + 1; 3574 i < path_num_items(right_path); i++) { 3575 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 3576 right_path, i); 3577 if (ret) { 3578 mlog_errno(ret); 3579 goto out; 3580 } 3581 3582 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, 3583 left_path, i); 3584 if (ret) { 3585 mlog_errno(ret); 3586 goto out; 3587 } 3588 } 3589 } else { 3590 left_rec = &el->l_recs[index - 1]; 3591 if (ocfs2_is_empty_extent(&el->l_recs[0])) 3592 has_empty_extent = 1; 3593 } 3594 3595 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, right_path, 3596 path_num_items(right_path) - 1); 3597 if (ret) { 3598 mlog_errno(ret); 3599 goto out; 3600 } 3601 3602 if (has_empty_extent && index == 1) { 3603 /* 3604 * The easy case - we can just plop the record right in. 3605 */ 3606 *left_rec = *split_rec; 3607 3608 has_empty_extent = 0; 3609 } else 3610 le16_add_cpu(&left_rec->e_leaf_clusters, split_clusters); 3611 3612 le32_add_cpu(&right_rec->e_cpos, split_clusters); 3613 le64_add_cpu(&right_rec->e_blkno, 3614 ocfs2_clusters_to_blocks(ocfs2_metadata_cache_get_super(et->et_ci), 3615 split_clusters)); 3616 le16_add_cpu(&right_rec->e_leaf_clusters, -split_clusters); 3617 3618 ocfs2_cleanup_merge(el, index); 3619 3620 ocfs2_journal_dirty(handle, bh); 3621 if (left_path) { 3622 ocfs2_journal_dirty(handle, path_leaf_bh(left_path)); 3623 3624 /* 3625 * In the situation that the right_rec is empty and the extent 3626 * block is empty also, ocfs2_complete_edge_insert can't handle 3627 * it and we need to delete the right extent block. 3628 */ 3629 if (le16_to_cpu(right_rec->e_leaf_clusters) == 0 && 3630 le16_to_cpu(el->l_next_free_rec) == 1) { 3631 3632 ret = ocfs2_remove_rightmost_path(handle, et, 3633 right_path, 3634 dealloc); 3635 if (ret) { 3636 mlog_errno(ret); 3637 goto out; 3638 } 3639 3640 /* Now the rightmost extent block has been deleted. 3641 * So we use the new rightmost path. 3642 */ 3643 ocfs2_mv_path(right_path, left_path); 3644 left_path = NULL; 3645 } else 3646 ocfs2_complete_edge_insert(handle, left_path, 3647 right_path, subtree_index); 3648 } 3649 out: 3650 ocfs2_free_path(left_path); 3651 return ret; 3652 } 3653 3654 static int ocfs2_try_to_merge_extent(handle_t *handle, 3655 struct ocfs2_extent_tree *et, 3656 struct ocfs2_path *path, 3657 int split_index, 3658 struct ocfs2_extent_rec *split_rec, 3659 struct ocfs2_cached_dealloc_ctxt *dealloc, 3660 struct ocfs2_merge_ctxt *ctxt) 3661 { 3662 int ret = 0; 3663 struct ocfs2_extent_list *el = path_leaf_el(path); 3664 struct ocfs2_extent_rec *rec = &el->l_recs[split_index]; 3665 3666 BUG_ON(ctxt->c_contig_type == CONTIG_NONE); 3667 3668 if (ctxt->c_split_covers_rec && ctxt->c_has_empty_extent) { 3669 /* 3670 * The merge code will need to create an empty 3671 * extent to take the place of the newly 3672 * emptied slot. Remove any pre-existing empty 3673 * extents - having more than one in a leaf is 3674 * illegal. 3675 */ 3676 ret = ocfs2_rotate_tree_left(handle, et, path, dealloc); 3677 if (ret) { 3678 mlog_errno(ret); 3679 goto out; 3680 } 3681 split_index--; 3682 rec = &el->l_recs[split_index]; 3683 } 3684 3685 if (ctxt->c_contig_type == CONTIG_LEFTRIGHT) { 3686 /* 3687 * Left-right contig implies this. 3688 */ 3689 BUG_ON(!ctxt->c_split_covers_rec); 3690 3691 /* 3692 * Since the leftright insert always covers the entire 3693 * extent, this call will delete the insert record 3694 * entirely, resulting in an empty extent record added to 3695 * the extent block. 3696 * 3697 * Since the adding of an empty extent shifts 3698 * everything back to the right, there's no need to 3699 * update split_index here. 3700 * 3701 * When the split_index is zero, we need to merge it to the 3702 * prevoius extent block. It is more efficient and easier 3703 * if we do merge_right first and merge_left later. 3704 */ 3705 ret = ocfs2_merge_rec_right(path, handle, et, split_rec, 3706 split_index); 3707 if (ret) { 3708 mlog_errno(ret); 3709 goto out; 3710 } 3711 3712 /* 3713 * We can only get this from logic error above. 3714 */ 3715 BUG_ON(!ocfs2_is_empty_extent(&el->l_recs[0])); 3716 3717 /* The merge left us with an empty extent, remove it. */ 3718 ret = ocfs2_rotate_tree_left(handle, et, path, dealloc); 3719 if (ret) { 3720 mlog_errno(ret); 3721 goto out; 3722 } 3723 3724 rec = &el->l_recs[split_index]; 3725 3726 /* 3727 * Note that we don't pass split_rec here on purpose - 3728 * we've merged it into the rec already. 3729 */ 3730 ret = ocfs2_merge_rec_left(path, handle, et, rec, 3731 dealloc, split_index); 3732 3733 if (ret) { 3734 mlog_errno(ret); 3735 goto out; 3736 } 3737 3738 ret = ocfs2_rotate_tree_left(handle, et, path, dealloc); 3739 /* 3740 * Error from this last rotate is not critical, so 3741 * print but don't bubble it up. 3742 */ 3743 if (ret) 3744 mlog_errno(ret); 3745 ret = 0; 3746 } else { 3747 /* 3748 * Merge a record to the left or right. 3749 * 3750 * 'contig_type' is relative to the existing record, 3751 * so for example, if we're "right contig", it's to 3752 * the record on the left (hence the left merge). 3753 */ 3754 if (ctxt->c_contig_type == CONTIG_RIGHT) { 3755 ret = ocfs2_merge_rec_left(path, handle, et, 3756 split_rec, dealloc, 3757 split_index); 3758 if (ret) { 3759 mlog_errno(ret); 3760 goto out; 3761 } 3762 } else { 3763 ret = ocfs2_merge_rec_right(path, handle, 3764 et, split_rec, 3765 split_index); 3766 if (ret) { 3767 mlog_errno(ret); 3768 goto out; 3769 } 3770 } 3771 3772 if (ctxt->c_split_covers_rec) { 3773 /* 3774 * The merge may have left an empty extent in 3775 * our leaf. Try to rotate it away. 3776 */ 3777 ret = ocfs2_rotate_tree_left(handle, et, path, 3778 dealloc); 3779 if (ret) 3780 mlog_errno(ret); 3781 ret = 0; 3782 } 3783 } 3784 3785 out: 3786 return ret; 3787 } 3788 3789 static void ocfs2_subtract_from_rec(struct super_block *sb, 3790 enum ocfs2_split_type split, 3791 struct ocfs2_extent_rec *rec, 3792 struct ocfs2_extent_rec *split_rec) 3793 { 3794 u64 len_blocks; 3795 3796 len_blocks = ocfs2_clusters_to_blocks(sb, 3797 le16_to_cpu(split_rec->e_leaf_clusters)); 3798 3799 if (split == SPLIT_LEFT) { 3800 /* 3801 * Region is on the left edge of the existing 3802 * record. 3803 */ 3804 le32_add_cpu(&rec->e_cpos, 3805 le16_to_cpu(split_rec->e_leaf_clusters)); 3806 le64_add_cpu(&rec->e_blkno, len_blocks); 3807 le16_add_cpu(&rec->e_leaf_clusters, 3808 -le16_to_cpu(split_rec->e_leaf_clusters)); 3809 } else { 3810 /* 3811 * Region is on the right edge of the existing 3812 * record. 3813 */ 3814 le16_add_cpu(&rec->e_leaf_clusters, 3815 -le16_to_cpu(split_rec->e_leaf_clusters)); 3816 } 3817 } 3818 3819 /* 3820 * Do the final bits of extent record insertion at the target leaf 3821 * list. If this leaf is part of an allocation tree, it is assumed 3822 * that the tree above has been prepared. 3823 */ 3824 static void ocfs2_insert_at_leaf(struct ocfs2_extent_tree *et, 3825 struct ocfs2_extent_rec *insert_rec, 3826 struct ocfs2_extent_list *el, 3827 struct ocfs2_insert_type *insert) 3828 { 3829 int i = insert->ins_contig_index; 3830 unsigned int range; 3831 struct ocfs2_extent_rec *rec; 3832 3833 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 3834 3835 if (insert->ins_split != SPLIT_NONE) { 3836 i = ocfs2_search_extent_list(el, le32_to_cpu(insert_rec->e_cpos)); 3837 BUG_ON(i == -1); 3838 rec = &el->l_recs[i]; 3839 ocfs2_subtract_from_rec(ocfs2_metadata_cache_get_super(et->et_ci), 3840 insert->ins_split, rec, 3841 insert_rec); 3842 goto rotate; 3843 } 3844 3845 /* 3846 * Contiguous insert - either left or right. 3847 */ 3848 if (insert->ins_contig != CONTIG_NONE) { 3849 rec = &el->l_recs[i]; 3850 if (insert->ins_contig == CONTIG_LEFT) { 3851 rec->e_blkno = insert_rec->e_blkno; 3852 rec->e_cpos = insert_rec->e_cpos; 3853 } 3854 le16_add_cpu(&rec->e_leaf_clusters, 3855 le16_to_cpu(insert_rec->e_leaf_clusters)); 3856 return; 3857 } 3858 3859 /* 3860 * Handle insert into an empty leaf. 3861 */ 3862 if (le16_to_cpu(el->l_next_free_rec) == 0 || 3863 ((le16_to_cpu(el->l_next_free_rec) == 1) && 3864 ocfs2_is_empty_extent(&el->l_recs[0]))) { 3865 el->l_recs[0] = *insert_rec; 3866 el->l_next_free_rec = cpu_to_le16(1); 3867 return; 3868 } 3869 3870 /* 3871 * Appending insert. 3872 */ 3873 if (insert->ins_appending == APPEND_TAIL) { 3874 i = le16_to_cpu(el->l_next_free_rec) - 1; 3875 rec = &el->l_recs[i]; 3876 range = le32_to_cpu(rec->e_cpos) 3877 + le16_to_cpu(rec->e_leaf_clusters); 3878 BUG_ON(le32_to_cpu(insert_rec->e_cpos) < range); 3879 3880 mlog_bug_on_msg(le16_to_cpu(el->l_next_free_rec) >= 3881 le16_to_cpu(el->l_count), 3882 "owner %llu, depth %u, count %u, next free %u, " 3883 "rec.cpos %u, rec.clusters %u, " 3884 "insert.cpos %u, insert.clusters %u\n", 3885 ocfs2_metadata_cache_owner(et->et_ci), 3886 le16_to_cpu(el->l_tree_depth), 3887 le16_to_cpu(el->l_count), 3888 le16_to_cpu(el->l_next_free_rec), 3889 le32_to_cpu(el->l_recs[i].e_cpos), 3890 le16_to_cpu(el->l_recs[i].e_leaf_clusters), 3891 le32_to_cpu(insert_rec->e_cpos), 3892 le16_to_cpu(insert_rec->e_leaf_clusters)); 3893 i++; 3894 el->l_recs[i] = *insert_rec; 3895 le16_add_cpu(&el->l_next_free_rec, 1); 3896 return; 3897 } 3898 3899 rotate: 3900 /* 3901 * Ok, we have to rotate. 3902 * 3903 * At this point, it is safe to assume that inserting into an 3904 * empty leaf and appending to a leaf have both been handled 3905 * above. 3906 * 3907 * This leaf needs to have space, either by the empty 1st 3908 * extent record, or by virtue of an l_next_rec < l_count. 3909 */ 3910 ocfs2_rotate_leaf(el, insert_rec); 3911 } 3912 3913 static void ocfs2_adjust_rightmost_records(handle_t *handle, 3914 struct ocfs2_extent_tree *et, 3915 struct ocfs2_path *path, 3916 struct ocfs2_extent_rec *insert_rec) 3917 { 3918 int ret, i, next_free; 3919 struct buffer_head *bh; 3920 struct ocfs2_extent_list *el; 3921 struct ocfs2_extent_rec *rec; 3922 3923 /* 3924 * Update everything except the leaf block. 3925 */ 3926 for (i = 0; i < path->p_tree_depth; i++) { 3927 bh = path->p_node[i].bh; 3928 el = path->p_node[i].el; 3929 3930 next_free = le16_to_cpu(el->l_next_free_rec); 3931 if (next_free == 0) { 3932 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 3933 "Owner %llu has a bad extent list", 3934 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci)); 3935 ret = -EIO; 3936 return; 3937 } 3938 3939 rec = &el->l_recs[next_free - 1]; 3940 3941 rec->e_int_clusters = insert_rec->e_cpos; 3942 le32_add_cpu(&rec->e_int_clusters, 3943 le16_to_cpu(insert_rec->e_leaf_clusters)); 3944 le32_add_cpu(&rec->e_int_clusters, 3945 -le32_to_cpu(rec->e_cpos)); 3946 3947 ocfs2_journal_dirty(handle, bh); 3948 } 3949 } 3950 3951 static int ocfs2_append_rec_to_path(handle_t *handle, 3952 struct ocfs2_extent_tree *et, 3953 struct ocfs2_extent_rec *insert_rec, 3954 struct ocfs2_path *right_path, 3955 struct ocfs2_path **ret_left_path) 3956 { 3957 int ret, next_free; 3958 struct ocfs2_extent_list *el; 3959 struct ocfs2_path *left_path = NULL; 3960 3961 *ret_left_path = NULL; 3962 3963 /* 3964 * This shouldn't happen for non-trees. The extent rec cluster 3965 * count manipulation below only works for interior nodes. 3966 */ 3967 BUG_ON(right_path->p_tree_depth == 0); 3968 3969 /* 3970 * If our appending insert is at the leftmost edge of a leaf, 3971 * then we might need to update the rightmost records of the 3972 * neighboring path. 3973 */ 3974 el = path_leaf_el(right_path); 3975 next_free = le16_to_cpu(el->l_next_free_rec); 3976 if (next_free == 0 || 3977 (next_free == 1 && ocfs2_is_empty_extent(&el->l_recs[0]))) { 3978 u32 left_cpos; 3979 3980 ret = ocfs2_find_cpos_for_left_leaf(ocfs2_metadata_cache_get_super(et->et_ci), 3981 right_path, &left_cpos); 3982 if (ret) { 3983 mlog_errno(ret); 3984 goto out; 3985 } 3986 3987 trace_ocfs2_append_rec_to_path( 3988 (unsigned long long) 3989 ocfs2_metadata_cache_owner(et->et_ci), 3990 le32_to_cpu(insert_rec->e_cpos), 3991 left_cpos); 3992 3993 /* 3994 * No need to worry if the append is already in the 3995 * leftmost leaf. 3996 */ 3997 if (left_cpos) { 3998 left_path = ocfs2_new_path_from_path(right_path); 3999 if (!left_path) { 4000 ret = -ENOMEM; 4001 mlog_errno(ret); 4002 goto out; 4003 } 4004 4005 ret = ocfs2_find_path(et->et_ci, left_path, 4006 left_cpos); 4007 if (ret) { 4008 mlog_errno(ret); 4009 goto out; 4010 } 4011 4012 /* 4013 * ocfs2_insert_path() will pass the left_path to the 4014 * journal for us. 4015 */ 4016 } 4017 } 4018 4019 ret = ocfs2_journal_access_path(et->et_ci, handle, right_path); 4020 if (ret) { 4021 mlog_errno(ret); 4022 goto out; 4023 } 4024 4025 ocfs2_adjust_rightmost_records(handle, et, right_path, insert_rec); 4026 4027 *ret_left_path = left_path; 4028 ret = 0; 4029 out: 4030 if (ret != 0) 4031 ocfs2_free_path(left_path); 4032 4033 return ret; 4034 } 4035 4036 static void ocfs2_split_record(struct ocfs2_extent_tree *et, 4037 struct ocfs2_path *left_path, 4038 struct ocfs2_path *right_path, 4039 struct ocfs2_extent_rec *split_rec, 4040 enum ocfs2_split_type split) 4041 { 4042 int index; 4043 u32 cpos = le32_to_cpu(split_rec->e_cpos); 4044 struct ocfs2_extent_list *left_el = NULL, *right_el, *insert_el, *el; 4045 struct ocfs2_extent_rec *rec, *tmprec; 4046 4047 right_el = path_leaf_el(right_path); 4048 if (left_path) 4049 left_el = path_leaf_el(left_path); 4050 4051 el = right_el; 4052 insert_el = right_el; 4053 index = ocfs2_search_extent_list(el, cpos); 4054 if (index != -1) { 4055 if (index == 0 && left_path) { 4056 BUG_ON(ocfs2_is_empty_extent(&el->l_recs[0])); 4057 4058 /* 4059 * This typically means that the record 4060 * started in the left path but moved to the 4061 * right as a result of rotation. We either 4062 * move the existing record to the left, or we 4063 * do the later insert there. 4064 * 4065 * In this case, the left path should always 4066 * exist as the rotate code will have passed 4067 * it back for a post-insert update. 4068 */ 4069 4070 if (split == SPLIT_LEFT) { 4071 /* 4072 * It's a left split. Since we know 4073 * that the rotate code gave us an 4074 * empty extent in the left path, we 4075 * can just do the insert there. 4076 */ 4077 insert_el = left_el; 4078 } else { 4079 /* 4080 * Right split - we have to move the 4081 * existing record over to the left 4082 * leaf. The insert will be into the 4083 * newly created empty extent in the 4084 * right leaf. 4085 */ 4086 tmprec = &right_el->l_recs[index]; 4087 ocfs2_rotate_leaf(left_el, tmprec); 4088 el = left_el; 4089 4090 memset(tmprec, 0, sizeof(*tmprec)); 4091 index = ocfs2_search_extent_list(left_el, cpos); 4092 BUG_ON(index == -1); 4093 } 4094 } 4095 } else { 4096 BUG_ON(!left_path); 4097 BUG_ON(!ocfs2_is_empty_extent(&left_el->l_recs[0])); 4098 /* 4099 * Left path is easy - we can just allow the insert to 4100 * happen. 4101 */ 4102 el = left_el; 4103 insert_el = left_el; 4104 index = ocfs2_search_extent_list(el, cpos); 4105 BUG_ON(index == -1); 4106 } 4107 4108 rec = &el->l_recs[index]; 4109 ocfs2_subtract_from_rec(ocfs2_metadata_cache_get_super(et->et_ci), 4110 split, rec, split_rec); 4111 ocfs2_rotate_leaf(insert_el, split_rec); 4112 } 4113 4114 /* 4115 * This function only does inserts on an allocation b-tree. For tree 4116 * depth = 0, ocfs2_insert_at_leaf() is called directly. 4117 * 4118 * right_path is the path we want to do the actual insert 4119 * in. left_path should only be passed in if we need to update that 4120 * portion of the tree after an edge insert. 4121 */ 4122 static int ocfs2_insert_path(handle_t *handle, 4123 struct ocfs2_extent_tree *et, 4124 struct ocfs2_path *left_path, 4125 struct ocfs2_path *right_path, 4126 struct ocfs2_extent_rec *insert_rec, 4127 struct ocfs2_insert_type *insert) 4128 { 4129 int ret, subtree_index; 4130 struct buffer_head *leaf_bh = path_leaf_bh(right_path); 4131 4132 if (left_path) { 4133 /* 4134 * There's a chance that left_path got passed back to 4135 * us without being accounted for in the 4136 * journal. Extend our transaction here to be sure we 4137 * can change those blocks. 4138 */ 4139 ret = ocfs2_extend_trans(handle, left_path->p_tree_depth); 4140 if (ret < 0) { 4141 mlog_errno(ret); 4142 goto out; 4143 } 4144 4145 ret = ocfs2_journal_access_path(et->et_ci, handle, left_path); 4146 if (ret < 0) { 4147 mlog_errno(ret); 4148 goto out; 4149 } 4150 } 4151 4152 /* 4153 * Pass both paths to the journal. The majority of inserts 4154 * will be touching all components anyway. 4155 */ 4156 ret = ocfs2_journal_access_path(et->et_ci, handle, right_path); 4157 if (ret < 0) { 4158 mlog_errno(ret); 4159 goto out; 4160 } 4161 4162 if (insert->ins_split != SPLIT_NONE) { 4163 /* 4164 * We could call ocfs2_insert_at_leaf() for some types 4165 * of splits, but it's easier to just let one separate 4166 * function sort it all out. 4167 */ 4168 ocfs2_split_record(et, left_path, right_path, 4169 insert_rec, insert->ins_split); 4170 4171 /* 4172 * Split might have modified either leaf and we don't 4173 * have a guarantee that the later edge insert will 4174 * dirty this for us. 4175 */ 4176 if (left_path) 4177 ocfs2_journal_dirty(handle, 4178 path_leaf_bh(left_path)); 4179 } else 4180 ocfs2_insert_at_leaf(et, insert_rec, path_leaf_el(right_path), 4181 insert); 4182 4183 ocfs2_journal_dirty(handle, leaf_bh); 4184 4185 if (left_path) { 4186 /* 4187 * The rotate code has indicated that we need to fix 4188 * up portions of the tree after the insert. 4189 * 4190 * XXX: Should we extend the transaction here? 4191 */ 4192 subtree_index = ocfs2_find_subtree_root(et, left_path, 4193 right_path); 4194 ocfs2_complete_edge_insert(handle, left_path, right_path, 4195 subtree_index); 4196 } 4197 4198 ret = 0; 4199 out: 4200 return ret; 4201 } 4202 4203 static int ocfs2_do_insert_extent(handle_t *handle, 4204 struct ocfs2_extent_tree *et, 4205 struct ocfs2_extent_rec *insert_rec, 4206 struct ocfs2_insert_type *type) 4207 { 4208 int ret, rotate = 0; 4209 u32 cpos; 4210 struct ocfs2_path *right_path = NULL; 4211 struct ocfs2_path *left_path = NULL; 4212 struct ocfs2_extent_list *el; 4213 4214 el = et->et_root_el; 4215 4216 ret = ocfs2_et_root_journal_access(handle, et, 4217 OCFS2_JOURNAL_ACCESS_WRITE); 4218 if (ret) { 4219 mlog_errno(ret); 4220 goto out; 4221 } 4222 4223 if (le16_to_cpu(el->l_tree_depth) == 0) { 4224 ocfs2_insert_at_leaf(et, insert_rec, el, type); 4225 goto out_update_clusters; 4226 } 4227 4228 right_path = ocfs2_new_path_from_et(et); 4229 if (!right_path) { 4230 ret = -ENOMEM; 4231 mlog_errno(ret); 4232 goto out; 4233 } 4234 4235 /* 4236 * Determine the path to start with. Rotations need the 4237 * rightmost path, everything else can go directly to the 4238 * target leaf. 4239 */ 4240 cpos = le32_to_cpu(insert_rec->e_cpos); 4241 if (type->ins_appending == APPEND_NONE && 4242 type->ins_contig == CONTIG_NONE) { 4243 rotate = 1; 4244 cpos = UINT_MAX; 4245 } 4246 4247 ret = ocfs2_find_path(et->et_ci, right_path, cpos); 4248 if (ret) { 4249 mlog_errno(ret); 4250 goto out; 4251 } 4252 4253 /* 4254 * Rotations and appends need special treatment - they modify 4255 * parts of the tree's above them. 4256 * 4257 * Both might pass back a path immediate to the left of the 4258 * one being inserted to. This will be cause 4259 * ocfs2_insert_path() to modify the rightmost records of 4260 * left_path to account for an edge insert. 4261 * 4262 * XXX: When modifying this code, keep in mind that an insert 4263 * can wind up skipping both of these two special cases... 4264 */ 4265 if (rotate) { 4266 ret = ocfs2_rotate_tree_right(handle, et, type->ins_split, 4267 le32_to_cpu(insert_rec->e_cpos), 4268 right_path, &left_path); 4269 if (ret) { 4270 mlog_errno(ret); 4271 goto out; 4272 } 4273 4274 /* 4275 * ocfs2_rotate_tree_right() might have extended the 4276 * transaction without re-journaling our tree root. 4277 */ 4278 ret = ocfs2_et_root_journal_access(handle, et, 4279 OCFS2_JOURNAL_ACCESS_WRITE); 4280 if (ret) { 4281 mlog_errno(ret); 4282 goto out; 4283 } 4284 } else if (type->ins_appending == APPEND_TAIL 4285 && type->ins_contig != CONTIG_LEFT) { 4286 ret = ocfs2_append_rec_to_path(handle, et, insert_rec, 4287 right_path, &left_path); 4288 if (ret) { 4289 mlog_errno(ret); 4290 goto out; 4291 } 4292 } 4293 4294 ret = ocfs2_insert_path(handle, et, left_path, right_path, 4295 insert_rec, type); 4296 if (ret) { 4297 mlog_errno(ret); 4298 goto out; 4299 } 4300 4301 out_update_clusters: 4302 if (type->ins_split == SPLIT_NONE) 4303 ocfs2_et_update_clusters(et, 4304 le16_to_cpu(insert_rec->e_leaf_clusters)); 4305 4306 ocfs2_journal_dirty(handle, et->et_root_bh); 4307 4308 out: 4309 ocfs2_free_path(left_path); 4310 ocfs2_free_path(right_path); 4311 4312 return ret; 4313 } 4314 4315 static int ocfs2_figure_merge_contig_type(struct ocfs2_extent_tree *et, 4316 struct ocfs2_path *path, 4317 struct ocfs2_extent_list *el, int index, 4318 struct ocfs2_extent_rec *split_rec, 4319 struct ocfs2_merge_ctxt *ctxt) 4320 { 4321 int status = 0; 4322 enum ocfs2_contig_type ret = CONTIG_NONE; 4323 u32 left_cpos, right_cpos; 4324 struct ocfs2_extent_rec *rec = NULL; 4325 struct ocfs2_extent_list *new_el; 4326 struct ocfs2_path *left_path = NULL, *right_path = NULL; 4327 struct buffer_head *bh; 4328 struct ocfs2_extent_block *eb; 4329 struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci); 4330 4331 if (index > 0) { 4332 rec = &el->l_recs[index - 1]; 4333 } else if (path->p_tree_depth > 0) { 4334 status = ocfs2_find_cpos_for_left_leaf(sb, path, &left_cpos); 4335 if (status) 4336 goto exit; 4337 4338 if (left_cpos != 0) { 4339 left_path = ocfs2_new_path_from_path(path); 4340 if (!left_path) { 4341 status = -ENOMEM; 4342 mlog_errno(status); 4343 goto exit; 4344 } 4345 4346 status = ocfs2_find_path(et->et_ci, left_path, 4347 left_cpos); 4348 if (status) 4349 goto free_left_path; 4350 4351 new_el = path_leaf_el(left_path); 4352 4353 if (le16_to_cpu(new_el->l_next_free_rec) != 4354 le16_to_cpu(new_el->l_count)) { 4355 bh = path_leaf_bh(left_path); 4356 eb = (struct ocfs2_extent_block *)bh->b_data; 4357 ocfs2_error(sb, 4358 "Extent block #%llu has an " 4359 "invalid l_next_free_rec of " 4360 "%d. It should have " 4361 "matched the l_count of %d", 4362 (unsigned long long)le64_to_cpu(eb->h_blkno), 4363 le16_to_cpu(new_el->l_next_free_rec), 4364 le16_to_cpu(new_el->l_count)); 4365 status = -EINVAL; 4366 goto free_left_path; 4367 } 4368 rec = &new_el->l_recs[ 4369 le16_to_cpu(new_el->l_next_free_rec) - 1]; 4370 } 4371 } 4372 4373 /* 4374 * We're careful to check for an empty extent record here - 4375 * the merge code will know what to do if it sees one. 4376 */ 4377 if (rec) { 4378 if (index == 1 && ocfs2_is_empty_extent(rec)) { 4379 if (split_rec->e_cpos == el->l_recs[index].e_cpos) 4380 ret = CONTIG_RIGHT; 4381 } else { 4382 ret = ocfs2_et_extent_contig(et, rec, split_rec); 4383 } 4384 } 4385 4386 rec = NULL; 4387 if (index < (le16_to_cpu(el->l_next_free_rec) - 1)) 4388 rec = &el->l_recs[index + 1]; 4389 else if (le16_to_cpu(el->l_next_free_rec) == le16_to_cpu(el->l_count) && 4390 path->p_tree_depth > 0) { 4391 status = ocfs2_find_cpos_for_right_leaf(sb, path, &right_cpos); 4392 if (status) 4393 goto free_left_path; 4394 4395 if (right_cpos == 0) 4396 goto free_left_path; 4397 4398 right_path = ocfs2_new_path_from_path(path); 4399 if (!right_path) { 4400 status = -ENOMEM; 4401 mlog_errno(status); 4402 goto free_left_path; 4403 } 4404 4405 status = ocfs2_find_path(et->et_ci, right_path, right_cpos); 4406 if (status) 4407 goto free_right_path; 4408 4409 new_el = path_leaf_el(right_path); 4410 rec = &new_el->l_recs[0]; 4411 if (ocfs2_is_empty_extent(rec)) { 4412 if (le16_to_cpu(new_el->l_next_free_rec) <= 1) { 4413 bh = path_leaf_bh(right_path); 4414 eb = (struct ocfs2_extent_block *)bh->b_data; 4415 ocfs2_error(sb, 4416 "Extent block #%llu has an " 4417 "invalid l_next_free_rec of %d", 4418 (unsigned long long)le64_to_cpu(eb->h_blkno), 4419 le16_to_cpu(new_el->l_next_free_rec)); 4420 status = -EINVAL; 4421 goto free_right_path; 4422 } 4423 rec = &new_el->l_recs[1]; 4424 } 4425 } 4426 4427 if (rec) { 4428 enum ocfs2_contig_type contig_type; 4429 4430 contig_type = ocfs2_et_extent_contig(et, rec, split_rec); 4431 4432 if (contig_type == CONTIG_LEFT && ret == CONTIG_RIGHT) 4433 ret = CONTIG_LEFTRIGHT; 4434 else if (ret == CONTIG_NONE) 4435 ret = contig_type; 4436 } 4437 4438 free_right_path: 4439 ocfs2_free_path(right_path); 4440 free_left_path: 4441 ocfs2_free_path(left_path); 4442 exit: 4443 if (status == 0) 4444 ctxt->c_contig_type = ret; 4445 4446 return status; 4447 } 4448 4449 static void ocfs2_figure_contig_type(struct ocfs2_extent_tree *et, 4450 struct ocfs2_insert_type *insert, 4451 struct ocfs2_extent_list *el, 4452 struct ocfs2_extent_rec *insert_rec) 4453 { 4454 int i; 4455 enum ocfs2_contig_type contig_type = CONTIG_NONE; 4456 4457 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 4458 4459 for(i = 0; i < le16_to_cpu(el->l_next_free_rec); i++) { 4460 contig_type = ocfs2_et_extent_contig(et, &el->l_recs[i], 4461 insert_rec); 4462 if (contig_type != CONTIG_NONE) { 4463 insert->ins_contig_index = i; 4464 break; 4465 } 4466 } 4467 insert->ins_contig = contig_type; 4468 4469 if (insert->ins_contig != CONTIG_NONE) { 4470 struct ocfs2_extent_rec *rec = 4471 &el->l_recs[insert->ins_contig_index]; 4472 unsigned int len = le16_to_cpu(rec->e_leaf_clusters) + 4473 le16_to_cpu(insert_rec->e_leaf_clusters); 4474 4475 /* 4476 * Caller might want us to limit the size of extents, don't 4477 * calculate contiguousness if we might exceed that limit. 4478 */ 4479 if (et->et_max_leaf_clusters && 4480 (len > et->et_max_leaf_clusters)) 4481 insert->ins_contig = CONTIG_NONE; 4482 } 4483 } 4484 4485 /* 4486 * This should only be called against the righmost leaf extent list. 4487 * 4488 * ocfs2_figure_appending_type() will figure out whether we'll have to 4489 * insert at the tail of the rightmost leaf. 4490 * 4491 * This should also work against the root extent list for tree's with 0 4492 * depth. If we consider the root extent list to be the rightmost leaf node 4493 * then the logic here makes sense. 4494 */ 4495 static void ocfs2_figure_appending_type(struct ocfs2_insert_type *insert, 4496 struct ocfs2_extent_list *el, 4497 struct ocfs2_extent_rec *insert_rec) 4498 { 4499 int i; 4500 u32 cpos = le32_to_cpu(insert_rec->e_cpos); 4501 struct ocfs2_extent_rec *rec; 4502 4503 insert->ins_appending = APPEND_NONE; 4504 4505 BUG_ON(le16_to_cpu(el->l_tree_depth) != 0); 4506 4507 if (!el->l_next_free_rec) 4508 goto set_tail_append; 4509 4510 if (ocfs2_is_empty_extent(&el->l_recs[0])) { 4511 /* Were all records empty? */ 4512 if (le16_to_cpu(el->l_next_free_rec) == 1) 4513 goto set_tail_append; 4514 } 4515 4516 i = le16_to_cpu(el->l_next_free_rec) - 1; 4517 rec = &el->l_recs[i]; 4518 4519 if (cpos >= 4520 (le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters))) 4521 goto set_tail_append; 4522 4523 return; 4524 4525 set_tail_append: 4526 insert->ins_appending = APPEND_TAIL; 4527 } 4528 4529 /* 4530 * Helper function called at the beginning of an insert. 4531 * 4532 * This computes a few things that are commonly used in the process of 4533 * inserting into the btree: 4534 * - Whether the new extent is contiguous with an existing one. 4535 * - The current tree depth. 4536 * - Whether the insert is an appending one. 4537 * - The total # of free records in the tree. 4538 * 4539 * All of the information is stored on the ocfs2_insert_type 4540 * structure. 4541 */ 4542 static int ocfs2_figure_insert_type(struct ocfs2_extent_tree *et, 4543 struct buffer_head **last_eb_bh, 4544 struct ocfs2_extent_rec *insert_rec, 4545 int *free_records, 4546 struct ocfs2_insert_type *insert) 4547 { 4548 int ret; 4549 struct ocfs2_extent_block *eb; 4550 struct ocfs2_extent_list *el; 4551 struct ocfs2_path *path = NULL; 4552 struct buffer_head *bh = NULL; 4553 4554 insert->ins_split = SPLIT_NONE; 4555 4556 el = et->et_root_el; 4557 insert->ins_tree_depth = le16_to_cpu(el->l_tree_depth); 4558 4559 if (el->l_tree_depth) { 4560 /* 4561 * If we have tree depth, we read in the 4562 * rightmost extent block ahead of time as 4563 * ocfs2_figure_insert_type() and ocfs2_add_branch() 4564 * may want it later. 4565 */ 4566 ret = ocfs2_read_extent_block(et->et_ci, 4567 ocfs2_et_get_last_eb_blk(et), 4568 &bh); 4569 if (ret) { 4570 mlog_errno(ret); 4571 goto out; 4572 } 4573 eb = (struct ocfs2_extent_block *) bh->b_data; 4574 el = &eb->h_list; 4575 } 4576 4577 /* 4578 * Unless we have a contiguous insert, we'll need to know if 4579 * there is room left in our allocation tree for another 4580 * extent record. 4581 * 4582 * XXX: This test is simplistic, we can search for empty 4583 * extent records too. 4584 */ 4585 *free_records = le16_to_cpu(el->l_count) - 4586 le16_to_cpu(el->l_next_free_rec); 4587 4588 if (!insert->ins_tree_depth) { 4589 ocfs2_figure_contig_type(et, insert, el, insert_rec); 4590 ocfs2_figure_appending_type(insert, el, insert_rec); 4591 return 0; 4592 } 4593 4594 path = ocfs2_new_path_from_et(et); 4595 if (!path) { 4596 ret = -ENOMEM; 4597 mlog_errno(ret); 4598 goto out; 4599 } 4600 4601 /* 4602 * In the case that we're inserting past what the tree 4603 * currently accounts for, ocfs2_find_path() will return for 4604 * us the rightmost tree path. This is accounted for below in 4605 * the appending code. 4606 */ 4607 ret = ocfs2_find_path(et->et_ci, path, le32_to_cpu(insert_rec->e_cpos)); 4608 if (ret) { 4609 mlog_errno(ret); 4610 goto out; 4611 } 4612 4613 el = path_leaf_el(path); 4614 4615 /* 4616 * Now that we have the path, there's two things we want to determine: 4617 * 1) Contiguousness (also set contig_index if this is so) 4618 * 4619 * 2) Are we doing an append? We can trivially break this up 4620 * into two types of appends: simple record append, or a 4621 * rotate inside the tail leaf. 4622 */ 4623 ocfs2_figure_contig_type(et, insert, el, insert_rec); 4624 4625 /* 4626 * The insert code isn't quite ready to deal with all cases of 4627 * left contiguousness. Specifically, if it's an insert into 4628 * the 1st record in a leaf, it will require the adjustment of 4629 * cluster count on the last record of the path directly to it's 4630 * left. For now, just catch that case and fool the layers 4631 * above us. This works just fine for tree_depth == 0, which 4632 * is why we allow that above. 4633 */ 4634 if (insert->ins_contig == CONTIG_LEFT && 4635 insert->ins_contig_index == 0) 4636 insert->ins_contig = CONTIG_NONE; 4637 4638 /* 4639 * Ok, so we can simply compare against last_eb to figure out 4640 * whether the path doesn't exist. This will only happen in 4641 * the case that we're doing a tail append, so maybe we can 4642 * take advantage of that information somehow. 4643 */ 4644 if (ocfs2_et_get_last_eb_blk(et) == 4645 path_leaf_bh(path)->b_blocknr) { 4646 /* 4647 * Ok, ocfs2_find_path() returned us the rightmost 4648 * tree path. This might be an appending insert. There are 4649 * two cases: 4650 * 1) We're doing a true append at the tail: 4651 * -This might even be off the end of the leaf 4652 * 2) We're "appending" by rotating in the tail 4653 */ 4654 ocfs2_figure_appending_type(insert, el, insert_rec); 4655 } 4656 4657 out: 4658 ocfs2_free_path(path); 4659 4660 if (ret == 0) 4661 *last_eb_bh = bh; 4662 else 4663 brelse(bh); 4664 return ret; 4665 } 4666 4667 /* 4668 * Insert an extent into a btree. 4669 * 4670 * The caller needs to update the owning btree's cluster count. 4671 */ 4672 int ocfs2_insert_extent(handle_t *handle, 4673 struct ocfs2_extent_tree *et, 4674 u32 cpos, 4675 u64 start_blk, 4676 u32 new_clusters, 4677 u8 flags, 4678 struct ocfs2_alloc_context *meta_ac) 4679 { 4680 int status; 4681 int uninitialized_var(free_records); 4682 struct buffer_head *last_eb_bh = NULL; 4683 struct ocfs2_insert_type insert = {0, }; 4684 struct ocfs2_extent_rec rec; 4685 4686 trace_ocfs2_insert_extent_start( 4687 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 4688 cpos, new_clusters); 4689 4690 memset(&rec, 0, sizeof(rec)); 4691 rec.e_cpos = cpu_to_le32(cpos); 4692 rec.e_blkno = cpu_to_le64(start_blk); 4693 rec.e_leaf_clusters = cpu_to_le16(new_clusters); 4694 rec.e_flags = flags; 4695 status = ocfs2_et_insert_check(et, &rec); 4696 if (status) { 4697 mlog_errno(status); 4698 goto bail; 4699 } 4700 4701 status = ocfs2_figure_insert_type(et, &last_eb_bh, &rec, 4702 &free_records, &insert); 4703 if (status < 0) { 4704 mlog_errno(status); 4705 goto bail; 4706 } 4707 4708 trace_ocfs2_insert_extent(insert.ins_appending, insert.ins_contig, 4709 insert.ins_contig_index, free_records, 4710 insert.ins_tree_depth); 4711 4712 if (insert.ins_contig == CONTIG_NONE && free_records == 0) { 4713 status = ocfs2_grow_tree(handle, et, 4714 &insert.ins_tree_depth, &last_eb_bh, 4715 meta_ac); 4716 if (status) { 4717 mlog_errno(status); 4718 goto bail; 4719 } 4720 } 4721 4722 /* Finally, we can add clusters. This might rotate the tree for us. */ 4723 status = ocfs2_do_insert_extent(handle, et, &rec, &insert); 4724 if (status < 0) 4725 mlog_errno(status); 4726 else 4727 ocfs2_et_extent_map_insert(et, &rec); 4728 4729 bail: 4730 brelse(last_eb_bh); 4731 4732 return status; 4733 } 4734 4735 /* 4736 * Allcate and add clusters into the extent b-tree. 4737 * The new clusters(clusters_to_add) will be inserted at logical_offset. 4738 * The extent b-tree's root is specified by et, and 4739 * it is not limited to the file storage. Any extent tree can use this 4740 * function if it implements the proper ocfs2_extent_tree. 4741 */ 4742 int ocfs2_add_clusters_in_btree(handle_t *handle, 4743 struct ocfs2_extent_tree *et, 4744 u32 *logical_offset, 4745 u32 clusters_to_add, 4746 int mark_unwritten, 4747 struct ocfs2_alloc_context *data_ac, 4748 struct ocfs2_alloc_context *meta_ac, 4749 enum ocfs2_alloc_restarted *reason_ret) 4750 { 4751 int status = 0, err = 0; 4752 int need_free = 0; 4753 int free_extents; 4754 enum ocfs2_alloc_restarted reason = RESTART_NONE; 4755 u32 bit_off, num_bits; 4756 u64 block; 4757 u8 flags = 0; 4758 struct ocfs2_super *osb = 4759 OCFS2_SB(ocfs2_metadata_cache_get_super(et->et_ci)); 4760 4761 BUG_ON(!clusters_to_add); 4762 4763 if (mark_unwritten) 4764 flags = OCFS2_EXT_UNWRITTEN; 4765 4766 free_extents = ocfs2_num_free_extents(osb, et); 4767 if (free_extents < 0) { 4768 status = free_extents; 4769 mlog_errno(status); 4770 goto leave; 4771 } 4772 4773 /* there are two cases which could cause us to EAGAIN in the 4774 * we-need-more-metadata case: 4775 * 1) we haven't reserved *any* 4776 * 2) we are so fragmented, we've needed to add metadata too 4777 * many times. */ 4778 if (!free_extents && !meta_ac) { 4779 err = -1; 4780 status = -EAGAIN; 4781 reason = RESTART_META; 4782 goto leave; 4783 } else if ((!free_extents) 4784 && (ocfs2_alloc_context_bits_left(meta_ac) 4785 < ocfs2_extend_meta_needed(et->et_root_el))) { 4786 err = -2; 4787 status = -EAGAIN; 4788 reason = RESTART_META; 4789 goto leave; 4790 } 4791 4792 status = __ocfs2_claim_clusters(handle, data_ac, 1, 4793 clusters_to_add, &bit_off, &num_bits); 4794 if (status < 0) { 4795 if (status != -ENOSPC) 4796 mlog_errno(status); 4797 goto leave; 4798 } 4799 4800 BUG_ON(num_bits > clusters_to_add); 4801 4802 /* reserve our write early -- insert_extent may update the tree root */ 4803 status = ocfs2_et_root_journal_access(handle, et, 4804 OCFS2_JOURNAL_ACCESS_WRITE); 4805 if (status < 0) { 4806 mlog_errno(status); 4807 need_free = 1; 4808 goto bail; 4809 } 4810 4811 block = ocfs2_clusters_to_blocks(osb->sb, bit_off); 4812 trace_ocfs2_add_clusters_in_btree( 4813 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 4814 bit_off, num_bits); 4815 status = ocfs2_insert_extent(handle, et, *logical_offset, block, 4816 num_bits, flags, meta_ac); 4817 if (status < 0) { 4818 mlog_errno(status); 4819 need_free = 1; 4820 goto bail; 4821 } 4822 4823 ocfs2_journal_dirty(handle, et->et_root_bh); 4824 4825 clusters_to_add -= num_bits; 4826 *logical_offset += num_bits; 4827 4828 if (clusters_to_add) { 4829 err = clusters_to_add; 4830 status = -EAGAIN; 4831 reason = RESTART_TRANS; 4832 } 4833 4834 bail: 4835 if (need_free) { 4836 if (data_ac->ac_which == OCFS2_AC_USE_LOCAL) 4837 ocfs2_free_local_alloc_bits(osb, handle, data_ac, 4838 bit_off, num_bits); 4839 else 4840 ocfs2_free_clusters(handle, 4841 data_ac->ac_inode, 4842 data_ac->ac_bh, 4843 ocfs2_clusters_to_blocks(osb->sb, bit_off), 4844 num_bits); 4845 } 4846 4847 leave: 4848 if (reason_ret) 4849 *reason_ret = reason; 4850 trace_ocfs2_add_clusters_in_btree_ret(status, reason, err); 4851 return status; 4852 } 4853 4854 static void ocfs2_make_right_split_rec(struct super_block *sb, 4855 struct ocfs2_extent_rec *split_rec, 4856 u32 cpos, 4857 struct ocfs2_extent_rec *rec) 4858 { 4859 u32 rec_cpos = le32_to_cpu(rec->e_cpos); 4860 u32 rec_range = rec_cpos + le16_to_cpu(rec->e_leaf_clusters); 4861 4862 memset(split_rec, 0, sizeof(struct ocfs2_extent_rec)); 4863 4864 split_rec->e_cpos = cpu_to_le32(cpos); 4865 split_rec->e_leaf_clusters = cpu_to_le16(rec_range - cpos); 4866 4867 split_rec->e_blkno = rec->e_blkno; 4868 le64_add_cpu(&split_rec->e_blkno, 4869 ocfs2_clusters_to_blocks(sb, cpos - rec_cpos)); 4870 4871 split_rec->e_flags = rec->e_flags; 4872 } 4873 4874 static int ocfs2_split_and_insert(handle_t *handle, 4875 struct ocfs2_extent_tree *et, 4876 struct ocfs2_path *path, 4877 struct buffer_head **last_eb_bh, 4878 int split_index, 4879 struct ocfs2_extent_rec *orig_split_rec, 4880 struct ocfs2_alloc_context *meta_ac) 4881 { 4882 int ret = 0, depth; 4883 unsigned int insert_range, rec_range, do_leftright = 0; 4884 struct ocfs2_extent_rec tmprec; 4885 struct ocfs2_extent_list *rightmost_el; 4886 struct ocfs2_extent_rec rec; 4887 struct ocfs2_extent_rec split_rec = *orig_split_rec; 4888 struct ocfs2_insert_type insert; 4889 struct ocfs2_extent_block *eb; 4890 4891 leftright: 4892 /* 4893 * Store a copy of the record on the stack - it might move 4894 * around as the tree is manipulated below. 4895 */ 4896 rec = path_leaf_el(path)->l_recs[split_index]; 4897 4898 rightmost_el = et->et_root_el; 4899 4900 depth = le16_to_cpu(rightmost_el->l_tree_depth); 4901 if (depth) { 4902 BUG_ON(!(*last_eb_bh)); 4903 eb = (struct ocfs2_extent_block *) (*last_eb_bh)->b_data; 4904 rightmost_el = &eb->h_list; 4905 } 4906 4907 if (le16_to_cpu(rightmost_el->l_next_free_rec) == 4908 le16_to_cpu(rightmost_el->l_count)) { 4909 ret = ocfs2_grow_tree(handle, et, 4910 &depth, last_eb_bh, meta_ac); 4911 if (ret) { 4912 mlog_errno(ret); 4913 goto out; 4914 } 4915 } 4916 4917 memset(&insert, 0, sizeof(struct ocfs2_insert_type)); 4918 insert.ins_appending = APPEND_NONE; 4919 insert.ins_contig = CONTIG_NONE; 4920 insert.ins_tree_depth = depth; 4921 4922 insert_range = le32_to_cpu(split_rec.e_cpos) + 4923 le16_to_cpu(split_rec.e_leaf_clusters); 4924 rec_range = le32_to_cpu(rec.e_cpos) + 4925 le16_to_cpu(rec.e_leaf_clusters); 4926 4927 if (split_rec.e_cpos == rec.e_cpos) { 4928 insert.ins_split = SPLIT_LEFT; 4929 } else if (insert_range == rec_range) { 4930 insert.ins_split = SPLIT_RIGHT; 4931 } else { 4932 /* 4933 * Left/right split. We fake this as a right split 4934 * first and then make a second pass as a left split. 4935 */ 4936 insert.ins_split = SPLIT_RIGHT; 4937 4938 ocfs2_make_right_split_rec(ocfs2_metadata_cache_get_super(et->et_ci), 4939 &tmprec, insert_range, &rec); 4940 4941 split_rec = tmprec; 4942 4943 BUG_ON(do_leftright); 4944 do_leftright = 1; 4945 } 4946 4947 ret = ocfs2_do_insert_extent(handle, et, &split_rec, &insert); 4948 if (ret) { 4949 mlog_errno(ret); 4950 goto out; 4951 } 4952 4953 if (do_leftright == 1) { 4954 u32 cpos; 4955 struct ocfs2_extent_list *el; 4956 4957 do_leftright++; 4958 split_rec = *orig_split_rec; 4959 4960 ocfs2_reinit_path(path, 1); 4961 4962 cpos = le32_to_cpu(split_rec.e_cpos); 4963 ret = ocfs2_find_path(et->et_ci, path, cpos); 4964 if (ret) { 4965 mlog_errno(ret); 4966 goto out; 4967 } 4968 4969 el = path_leaf_el(path); 4970 split_index = ocfs2_search_extent_list(el, cpos); 4971 if (split_index == -1) { 4972 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 4973 "Owner %llu has an extent at cpos %u " 4974 "which can no longer be found.\n", 4975 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 4976 cpos); 4977 ret = -EROFS; 4978 goto out; 4979 } 4980 goto leftright; 4981 } 4982 out: 4983 4984 return ret; 4985 } 4986 4987 static int ocfs2_replace_extent_rec(handle_t *handle, 4988 struct ocfs2_extent_tree *et, 4989 struct ocfs2_path *path, 4990 struct ocfs2_extent_list *el, 4991 int split_index, 4992 struct ocfs2_extent_rec *split_rec) 4993 { 4994 int ret; 4995 4996 ret = ocfs2_path_bh_journal_access(handle, et->et_ci, path, 4997 path_num_items(path) - 1); 4998 if (ret) { 4999 mlog_errno(ret); 5000 goto out; 5001 } 5002 5003 el->l_recs[split_index] = *split_rec; 5004 5005 ocfs2_journal_dirty(handle, path_leaf_bh(path)); 5006 out: 5007 return ret; 5008 } 5009 5010 /* 5011 * Split part or all of the extent record at split_index in the leaf 5012 * pointed to by path. Merge with the contiguous extent record if needed. 5013 * 5014 * Care is taken to handle contiguousness so as to not grow the tree. 5015 * 5016 * meta_ac is not strictly necessary - we only truly need it if growth 5017 * of the tree is required. All other cases will degrade into a less 5018 * optimal tree layout. 5019 * 5020 * last_eb_bh should be the rightmost leaf block for any extent 5021 * btree. Since a split may grow the tree or a merge might shrink it, 5022 * the caller cannot trust the contents of that buffer after this call. 5023 * 5024 * This code is optimized for readability - several passes might be 5025 * made over certain portions of the tree. All of those blocks will 5026 * have been brought into cache (and pinned via the journal), so the 5027 * extra overhead is not expressed in terms of disk reads. 5028 */ 5029 int ocfs2_split_extent(handle_t *handle, 5030 struct ocfs2_extent_tree *et, 5031 struct ocfs2_path *path, 5032 int split_index, 5033 struct ocfs2_extent_rec *split_rec, 5034 struct ocfs2_alloc_context *meta_ac, 5035 struct ocfs2_cached_dealloc_ctxt *dealloc) 5036 { 5037 int ret = 0; 5038 struct ocfs2_extent_list *el = path_leaf_el(path); 5039 struct buffer_head *last_eb_bh = NULL; 5040 struct ocfs2_extent_rec *rec = &el->l_recs[split_index]; 5041 struct ocfs2_merge_ctxt ctxt; 5042 struct ocfs2_extent_list *rightmost_el; 5043 5044 if (le32_to_cpu(rec->e_cpos) > le32_to_cpu(split_rec->e_cpos) || 5045 ((le32_to_cpu(rec->e_cpos) + le16_to_cpu(rec->e_leaf_clusters)) < 5046 (le32_to_cpu(split_rec->e_cpos) + le16_to_cpu(split_rec->e_leaf_clusters)))) { 5047 ret = -EIO; 5048 mlog_errno(ret); 5049 goto out; 5050 } 5051 5052 ret = ocfs2_figure_merge_contig_type(et, path, el, 5053 split_index, 5054 split_rec, 5055 &ctxt); 5056 if (ret) { 5057 mlog_errno(ret); 5058 goto out; 5059 } 5060 5061 /* 5062 * The core merge / split code wants to know how much room is 5063 * left in this allocation tree, so we pass the 5064 * rightmost extent list. 5065 */ 5066 if (path->p_tree_depth) { 5067 struct ocfs2_extent_block *eb; 5068 5069 ret = ocfs2_read_extent_block(et->et_ci, 5070 ocfs2_et_get_last_eb_blk(et), 5071 &last_eb_bh); 5072 if (ret) { 5073 mlog_errno(ret); 5074 goto out; 5075 } 5076 5077 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; 5078 rightmost_el = &eb->h_list; 5079 } else 5080 rightmost_el = path_root_el(path); 5081 5082 if (rec->e_cpos == split_rec->e_cpos && 5083 rec->e_leaf_clusters == split_rec->e_leaf_clusters) 5084 ctxt.c_split_covers_rec = 1; 5085 else 5086 ctxt.c_split_covers_rec = 0; 5087 5088 ctxt.c_has_empty_extent = ocfs2_is_empty_extent(&el->l_recs[0]); 5089 5090 trace_ocfs2_split_extent(split_index, ctxt.c_contig_type, 5091 ctxt.c_has_empty_extent, 5092 ctxt.c_split_covers_rec); 5093 5094 if (ctxt.c_contig_type == CONTIG_NONE) { 5095 if (ctxt.c_split_covers_rec) 5096 ret = ocfs2_replace_extent_rec(handle, et, path, el, 5097 split_index, split_rec); 5098 else 5099 ret = ocfs2_split_and_insert(handle, et, path, 5100 &last_eb_bh, split_index, 5101 split_rec, meta_ac); 5102 if (ret) 5103 mlog_errno(ret); 5104 } else { 5105 ret = ocfs2_try_to_merge_extent(handle, et, path, 5106 split_index, split_rec, 5107 dealloc, &ctxt); 5108 if (ret) 5109 mlog_errno(ret); 5110 } 5111 5112 out: 5113 brelse(last_eb_bh); 5114 return ret; 5115 } 5116 5117 /* 5118 * Change the flags of the already-existing extent at cpos for len clusters. 5119 * 5120 * new_flags: the flags we want to set. 5121 * clear_flags: the flags we want to clear. 5122 * phys: the new physical offset we want this new extent starts from. 5123 * 5124 * If the existing extent is larger than the request, initiate a 5125 * split. An attempt will be made at merging with adjacent extents. 5126 * 5127 * The caller is responsible for passing down meta_ac if we'll need it. 5128 */ 5129 int ocfs2_change_extent_flag(handle_t *handle, 5130 struct ocfs2_extent_tree *et, 5131 u32 cpos, u32 len, u32 phys, 5132 struct ocfs2_alloc_context *meta_ac, 5133 struct ocfs2_cached_dealloc_ctxt *dealloc, 5134 int new_flags, int clear_flags) 5135 { 5136 int ret, index; 5137 struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci); 5138 u64 start_blkno = ocfs2_clusters_to_blocks(sb, phys); 5139 struct ocfs2_extent_rec split_rec; 5140 struct ocfs2_path *left_path = NULL; 5141 struct ocfs2_extent_list *el; 5142 struct ocfs2_extent_rec *rec; 5143 5144 left_path = ocfs2_new_path_from_et(et); 5145 if (!left_path) { 5146 ret = -ENOMEM; 5147 mlog_errno(ret); 5148 goto out; 5149 } 5150 5151 ret = ocfs2_find_path(et->et_ci, left_path, cpos); 5152 if (ret) { 5153 mlog_errno(ret); 5154 goto out; 5155 } 5156 el = path_leaf_el(left_path); 5157 5158 index = ocfs2_search_extent_list(el, cpos); 5159 if (index == -1) { 5160 ocfs2_error(sb, 5161 "Owner %llu has an extent at cpos %u which can no " 5162 "longer be found.\n", 5163 (unsigned long long) 5164 ocfs2_metadata_cache_owner(et->et_ci), cpos); 5165 ret = -EROFS; 5166 goto out; 5167 } 5168 5169 ret = -EIO; 5170 rec = &el->l_recs[index]; 5171 if (new_flags && (rec->e_flags & new_flags)) { 5172 mlog(ML_ERROR, "Owner %llu tried to set %d flags on an " 5173 "extent that already had them", 5174 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5175 new_flags); 5176 goto out; 5177 } 5178 5179 if (clear_flags && !(rec->e_flags & clear_flags)) { 5180 mlog(ML_ERROR, "Owner %llu tried to clear %d flags on an " 5181 "extent that didn't have them", 5182 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5183 clear_flags); 5184 goto out; 5185 } 5186 5187 memset(&split_rec, 0, sizeof(struct ocfs2_extent_rec)); 5188 split_rec.e_cpos = cpu_to_le32(cpos); 5189 split_rec.e_leaf_clusters = cpu_to_le16(len); 5190 split_rec.e_blkno = cpu_to_le64(start_blkno); 5191 split_rec.e_flags = rec->e_flags; 5192 if (new_flags) 5193 split_rec.e_flags |= new_flags; 5194 if (clear_flags) 5195 split_rec.e_flags &= ~clear_flags; 5196 5197 ret = ocfs2_split_extent(handle, et, left_path, 5198 index, &split_rec, meta_ac, 5199 dealloc); 5200 if (ret) 5201 mlog_errno(ret); 5202 5203 out: 5204 ocfs2_free_path(left_path); 5205 return ret; 5206 5207 } 5208 5209 /* 5210 * Mark the already-existing extent at cpos as written for len clusters. 5211 * This removes the unwritten extent flag. 5212 * 5213 * If the existing extent is larger than the request, initiate a 5214 * split. An attempt will be made at merging with adjacent extents. 5215 * 5216 * The caller is responsible for passing down meta_ac if we'll need it. 5217 */ 5218 int ocfs2_mark_extent_written(struct inode *inode, 5219 struct ocfs2_extent_tree *et, 5220 handle_t *handle, u32 cpos, u32 len, u32 phys, 5221 struct ocfs2_alloc_context *meta_ac, 5222 struct ocfs2_cached_dealloc_ctxt *dealloc) 5223 { 5224 int ret; 5225 5226 trace_ocfs2_mark_extent_written( 5227 (unsigned long long)OCFS2_I(inode)->ip_blkno, 5228 cpos, len, phys); 5229 5230 if (!ocfs2_writes_unwritten_extents(OCFS2_SB(inode->i_sb))) { 5231 ocfs2_error(inode->i_sb, "Inode %llu has unwritten extents " 5232 "that are being written to, but the feature bit " 5233 "is not set in the super block.", 5234 (unsigned long long)OCFS2_I(inode)->ip_blkno); 5235 ret = -EROFS; 5236 goto out; 5237 } 5238 5239 /* 5240 * XXX: This should be fixed up so that we just re-insert the 5241 * next extent records. 5242 */ 5243 ocfs2_et_extent_map_truncate(et, 0); 5244 5245 ret = ocfs2_change_extent_flag(handle, et, cpos, 5246 len, phys, meta_ac, dealloc, 5247 0, OCFS2_EXT_UNWRITTEN); 5248 if (ret) 5249 mlog_errno(ret); 5250 5251 out: 5252 return ret; 5253 } 5254 5255 static int ocfs2_split_tree(handle_t *handle, struct ocfs2_extent_tree *et, 5256 struct ocfs2_path *path, 5257 int index, u32 new_range, 5258 struct ocfs2_alloc_context *meta_ac) 5259 { 5260 int ret, depth, credits; 5261 struct buffer_head *last_eb_bh = NULL; 5262 struct ocfs2_extent_block *eb; 5263 struct ocfs2_extent_list *rightmost_el, *el; 5264 struct ocfs2_extent_rec split_rec; 5265 struct ocfs2_extent_rec *rec; 5266 struct ocfs2_insert_type insert; 5267 5268 /* 5269 * Setup the record to split before we grow the tree. 5270 */ 5271 el = path_leaf_el(path); 5272 rec = &el->l_recs[index]; 5273 ocfs2_make_right_split_rec(ocfs2_metadata_cache_get_super(et->et_ci), 5274 &split_rec, new_range, rec); 5275 5276 depth = path->p_tree_depth; 5277 if (depth > 0) { 5278 ret = ocfs2_read_extent_block(et->et_ci, 5279 ocfs2_et_get_last_eb_blk(et), 5280 &last_eb_bh); 5281 if (ret < 0) { 5282 mlog_errno(ret); 5283 goto out; 5284 } 5285 5286 eb = (struct ocfs2_extent_block *) last_eb_bh->b_data; 5287 rightmost_el = &eb->h_list; 5288 } else 5289 rightmost_el = path_leaf_el(path); 5290 5291 credits = path->p_tree_depth + 5292 ocfs2_extend_meta_needed(et->et_root_el); 5293 ret = ocfs2_extend_trans(handle, credits); 5294 if (ret) { 5295 mlog_errno(ret); 5296 goto out; 5297 } 5298 5299 if (le16_to_cpu(rightmost_el->l_next_free_rec) == 5300 le16_to_cpu(rightmost_el->l_count)) { 5301 ret = ocfs2_grow_tree(handle, et, &depth, &last_eb_bh, 5302 meta_ac); 5303 if (ret) { 5304 mlog_errno(ret); 5305 goto out; 5306 } 5307 } 5308 5309 memset(&insert, 0, sizeof(struct ocfs2_insert_type)); 5310 insert.ins_appending = APPEND_NONE; 5311 insert.ins_contig = CONTIG_NONE; 5312 insert.ins_split = SPLIT_RIGHT; 5313 insert.ins_tree_depth = depth; 5314 5315 ret = ocfs2_do_insert_extent(handle, et, &split_rec, &insert); 5316 if (ret) 5317 mlog_errno(ret); 5318 5319 out: 5320 brelse(last_eb_bh); 5321 return ret; 5322 } 5323 5324 static int ocfs2_truncate_rec(handle_t *handle, 5325 struct ocfs2_extent_tree *et, 5326 struct ocfs2_path *path, int index, 5327 struct ocfs2_cached_dealloc_ctxt *dealloc, 5328 u32 cpos, u32 len) 5329 { 5330 int ret; 5331 u32 left_cpos, rec_range, trunc_range; 5332 int wants_rotate = 0, is_rightmost_tree_rec = 0; 5333 struct super_block *sb = ocfs2_metadata_cache_get_super(et->et_ci); 5334 struct ocfs2_path *left_path = NULL; 5335 struct ocfs2_extent_list *el = path_leaf_el(path); 5336 struct ocfs2_extent_rec *rec; 5337 struct ocfs2_extent_block *eb; 5338 5339 if (ocfs2_is_empty_extent(&el->l_recs[0]) && index > 0) { 5340 ret = ocfs2_rotate_tree_left(handle, et, path, dealloc); 5341 if (ret) { 5342 mlog_errno(ret); 5343 goto out; 5344 } 5345 5346 index--; 5347 } 5348 5349 if (index == (le16_to_cpu(el->l_next_free_rec) - 1) && 5350 path->p_tree_depth) { 5351 /* 5352 * Check whether this is the rightmost tree record. If 5353 * we remove all of this record or part of its right 5354 * edge then an update of the record lengths above it 5355 * will be required. 5356 */ 5357 eb = (struct ocfs2_extent_block *)path_leaf_bh(path)->b_data; 5358 if (eb->h_next_leaf_blk == 0) 5359 is_rightmost_tree_rec = 1; 5360 } 5361 5362 rec = &el->l_recs[index]; 5363 if (index == 0 && path->p_tree_depth && 5364 le32_to_cpu(rec->e_cpos) == cpos) { 5365 /* 5366 * Changing the leftmost offset (via partial or whole 5367 * record truncate) of an interior (or rightmost) path 5368 * means we have to update the subtree that is formed 5369 * by this leaf and the one to it's left. 5370 * 5371 * There are two cases we can skip: 5372 * 1) Path is the leftmost one in our btree. 5373 * 2) The leaf is rightmost and will be empty after 5374 * we remove the extent record - the rotate code 5375 * knows how to update the newly formed edge. 5376 */ 5377 5378 ret = ocfs2_find_cpos_for_left_leaf(sb, path, &left_cpos); 5379 if (ret) { 5380 mlog_errno(ret); 5381 goto out; 5382 } 5383 5384 if (left_cpos && le16_to_cpu(el->l_next_free_rec) > 1) { 5385 left_path = ocfs2_new_path_from_path(path); 5386 if (!left_path) { 5387 ret = -ENOMEM; 5388 mlog_errno(ret); 5389 goto out; 5390 } 5391 5392 ret = ocfs2_find_path(et->et_ci, left_path, 5393 left_cpos); 5394 if (ret) { 5395 mlog_errno(ret); 5396 goto out; 5397 } 5398 } 5399 } 5400 5401 ret = ocfs2_extend_rotate_transaction(handle, 0, 5402 handle->h_buffer_credits, 5403 path); 5404 if (ret) { 5405 mlog_errno(ret); 5406 goto out; 5407 } 5408 5409 ret = ocfs2_journal_access_path(et->et_ci, handle, path); 5410 if (ret) { 5411 mlog_errno(ret); 5412 goto out; 5413 } 5414 5415 ret = ocfs2_journal_access_path(et->et_ci, handle, left_path); 5416 if (ret) { 5417 mlog_errno(ret); 5418 goto out; 5419 } 5420 5421 rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec); 5422 trunc_range = cpos + len; 5423 5424 if (le32_to_cpu(rec->e_cpos) == cpos && rec_range == trunc_range) { 5425 int next_free; 5426 5427 memset(rec, 0, sizeof(*rec)); 5428 ocfs2_cleanup_merge(el, index); 5429 wants_rotate = 1; 5430 5431 next_free = le16_to_cpu(el->l_next_free_rec); 5432 if (is_rightmost_tree_rec && next_free > 1) { 5433 /* 5434 * We skip the edge update if this path will 5435 * be deleted by the rotate code. 5436 */ 5437 rec = &el->l_recs[next_free - 1]; 5438 ocfs2_adjust_rightmost_records(handle, et, path, 5439 rec); 5440 } 5441 } else if (le32_to_cpu(rec->e_cpos) == cpos) { 5442 /* Remove leftmost portion of the record. */ 5443 le32_add_cpu(&rec->e_cpos, len); 5444 le64_add_cpu(&rec->e_blkno, ocfs2_clusters_to_blocks(sb, len)); 5445 le16_add_cpu(&rec->e_leaf_clusters, -len); 5446 } else if (rec_range == trunc_range) { 5447 /* Remove rightmost portion of the record */ 5448 le16_add_cpu(&rec->e_leaf_clusters, -len); 5449 if (is_rightmost_tree_rec) 5450 ocfs2_adjust_rightmost_records(handle, et, path, rec); 5451 } else { 5452 /* Caller should have trapped this. */ 5453 mlog(ML_ERROR, "Owner %llu: Invalid record truncate: (%u, %u) " 5454 "(%u, %u)\n", 5455 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5456 le32_to_cpu(rec->e_cpos), 5457 le16_to_cpu(rec->e_leaf_clusters), cpos, len); 5458 BUG(); 5459 } 5460 5461 if (left_path) { 5462 int subtree_index; 5463 5464 subtree_index = ocfs2_find_subtree_root(et, left_path, path); 5465 ocfs2_complete_edge_insert(handle, left_path, path, 5466 subtree_index); 5467 } 5468 5469 ocfs2_journal_dirty(handle, path_leaf_bh(path)); 5470 5471 ret = ocfs2_rotate_tree_left(handle, et, path, dealloc); 5472 if (ret) { 5473 mlog_errno(ret); 5474 goto out; 5475 } 5476 5477 out: 5478 ocfs2_free_path(left_path); 5479 return ret; 5480 } 5481 5482 int ocfs2_remove_extent(handle_t *handle, 5483 struct ocfs2_extent_tree *et, 5484 u32 cpos, u32 len, 5485 struct ocfs2_alloc_context *meta_ac, 5486 struct ocfs2_cached_dealloc_ctxt *dealloc) 5487 { 5488 int ret, index; 5489 u32 rec_range, trunc_range; 5490 struct ocfs2_extent_rec *rec; 5491 struct ocfs2_extent_list *el; 5492 struct ocfs2_path *path = NULL; 5493 5494 /* 5495 * XXX: Why are we truncating to 0 instead of wherever this 5496 * affects us? 5497 */ 5498 ocfs2_et_extent_map_truncate(et, 0); 5499 5500 path = ocfs2_new_path_from_et(et); 5501 if (!path) { 5502 ret = -ENOMEM; 5503 mlog_errno(ret); 5504 goto out; 5505 } 5506 5507 ret = ocfs2_find_path(et->et_ci, path, cpos); 5508 if (ret) { 5509 mlog_errno(ret); 5510 goto out; 5511 } 5512 5513 el = path_leaf_el(path); 5514 index = ocfs2_search_extent_list(el, cpos); 5515 if (index == -1) { 5516 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 5517 "Owner %llu has an extent at cpos %u which can no " 5518 "longer be found.\n", 5519 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5520 cpos); 5521 ret = -EROFS; 5522 goto out; 5523 } 5524 5525 /* 5526 * We have 3 cases of extent removal: 5527 * 1) Range covers the entire extent rec 5528 * 2) Range begins or ends on one edge of the extent rec 5529 * 3) Range is in the middle of the extent rec (no shared edges) 5530 * 5531 * For case 1 we remove the extent rec and left rotate to 5532 * fill the hole. 5533 * 5534 * For case 2 we just shrink the existing extent rec, with a 5535 * tree update if the shrinking edge is also the edge of an 5536 * extent block. 5537 * 5538 * For case 3 we do a right split to turn the extent rec into 5539 * something case 2 can handle. 5540 */ 5541 rec = &el->l_recs[index]; 5542 rec_range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec); 5543 trunc_range = cpos + len; 5544 5545 BUG_ON(cpos < le32_to_cpu(rec->e_cpos) || trunc_range > rec_range); 5546 5547 trace_ocfs2_remove_extent( 5548 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5549 cpos, len, index, le32_to_cpu(rec->e_cpos), 5550 ocfs2_rec_clusters(el, rec)); 5551 5552 if (le32_to_cpu(rec->e_cpos) == cpos || rec_range == trunc_range) { 5553 ret = ocfs2_truncate_rec(handle, et, path, index, dealloc, 5554 cpos, len); 5555 if (ret) { 5556 mlog_errno(ret); 5557 goto out; 5558 } 5559 } else { 5560 ret = ocfs2_split_tree(handle, et, path, index, 5561 trunc_range, meta_ac); 5562 if (ret) { 5563 mlog_errno(ret); 5564 goto out; 5565 } 5566 5567 /* 5568 * The split could have manipulated the tree enough to 5569 * move the record location, so we have to look for it again. 5570 */ 5571 ocfs2_reinit_path(path, 1); 5572 5573 ret = ocfs2_find_path(et->et_ci, path, cpos); 5574 if (ret) { 5575 mlog_errno(ret); 5576 goto out; 5577 } 5578 5579 el = path_leaf_el(path); 5580 index = ocfs2_search_extent_list(el, cpos); 5581 if (index == -1) { 5582 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 5583 "Owner %llu: split at cpos %u lost record.", 5584 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5585 cpos); 5586 ret = -EROFS; 5587 goto out; 5588 } 5589 5590 /* 5591 * Double check our values here. If anything is fishy, 5592 * it's easier to catch it at the top level. 5593 */ 5594 rec = &el->l_recs[index]; 5595 rec_range = le32_to_cpu(rec->e_cpos) + 5596 ocfs2_rec_clusters(el, rec); 5597 if (rec_range != trunc_range) { 5598 ocfs2_error(ocfs2_metadata_cache_get_super(et->et_ci), 5599 "Owner %llu: error after split at cpos %u" 5600 "trunc len %u, existing record is (%u,%u)", 5601 (unsigned long long)ocfs2_metadata_cache_owner(et->et_ci), 5602 cpos, len, le32_to_cpu(rec->e_cpos), 5603 ocfs2_rec_clusters(el, rec)); 5604 ret = -EROFS; 5605 goto out; 5606 } 5607 5608 ret = ocfs2_truncate_rec(handle, et, path, index, dealloc, 5609 cpos, len); 5610 if (ret) { 5611 mlog_errno(ret); 5612 goto out; 5613 } 5614 } 5615 5616 out: 5617 ocfs2_free_path(path); 5618 return ret; 5619 } 5620 5621 /* 5622 * ocfs2_reserve_blocks_for_rec_trunc() would look basically the 5623 * same as ocfs2_lock_alloctors(), except for it accepts a blocks 5624 * number to reserve some extra blocks, and it only handles meta 5625 * data allocations. 5626 * 5627 * Currently, only ocfs2_remove_btree_range() uses it for truncating 5628 * and punching holes. 5629 */ 5630 static int ocfs2_reserve_blocks_for_rec_trunc(struct inode *inode, 5631 struct ocfs2_extent_tree *et, 5632 u32 extents_to_split, 5633 struct ocfs2_alloc_context **ac, 5634 int extra_blocks) 5635 { 5636 int ret = 0, num_free_extents; 5637 unsigned int max_recs_needed = 2 * extents_to_split; 5638 struct ocfs2_super *osb = OCFS2_SB(inode->i_sb); 5639 5640 *ac = NULL; 5641 5642 num_free_extents = ocfs2_num_free_extents(osb, et); 5643 if (num_free_extents < 0) { 5644 ret = num_free_extents; 5645 mlog_errno(ret); 5646 goto out; 5647 } 5648 5649 if (!num_free_extents || 5650 (ocfs2_sparse_alloc(osb) && num_free_extents < max_recs_needed)) 5651 extra_blocks += ocfs2_extend_meta_needed(et->et_root_el); 5652 5653 if (extra_blocks) { 5654 ret = ocfs2_reserve_new_metadata_blocks(osb, extra_blocks, ac); 5655 if (ret < 0) { 5656 if (ret != -ENOSPC) 5657 mlog_errno(ret); 5658 goto out; 5659 } 5660 } 5661 5662 out: 5663 if (ret) { 5664 if (*ac) { 5665 ocfs2_free_alloc_context(*ac); 5666 *ac = NULL; 5667 } 5668 } 5669 5670 return ret; 5671 } 5672 5673 int ocfs2_remove_btree_range(struct inode *inode, 5674 struct ocfs2_extent_tree *et, 5675 u32 cpos, u32 phys_cpos, u32 len, int flags, 5676 struct ocfs2_cached_dealloc_ctxt *dealloc, 5677 u64 refcount_loc, bool refcount_tree_locked) 5678 { 5679 int ret, credits = 0, extra_blocks = 0; 5680 u64 phys_blkno = ocfs2_clusters_to_blocks(inode->i_sb, phys_cpos); 5681 struct ocfs2_super *osb = OCFS2_SB(inode->i_sb); 5682 struct inode *tl_inode = osb->osb_tl_inode; 5683 handle_t *handle; 5684 struct ocfs2_alloc_context *meta_ac = NULL; 5685 struct ocfs2_refcount_tree *ref_tree = NULL; 5686 5687 if ((flags & OCFS2_EXT_REFCOUNTED) && len) { 5688 BUG_ON(!(OCFS2_I(inode)->ip_dyn_features & 5689 OCFS2_HAS_REFCOUNT_FL)); 5690 5691 if (!refcount_tree_locked) { 5692 ret = ocfs2_lock_refcount_tree(osb, refcount_loc, 1, 5693 &ref_tree, NULL); 5694 if (ret) { 5695 mlog_errno(ret); 5696 goto bail; 5697 } 5698 } 5699 5700 ret = ocfs2_prepare_refcount_change_for_del(inode, 5701 refcount_loc, 5702 phys_blkno, 5703 len, 5704 &credits, 5705 &extra_blocks); 5706 if (ret < 0) { 5707 mlog_errno(ret); 5708 goto bail; 5709 } 5710 } 5711 5712 ret = ocfs2_reserve_blocks_for_rec_trunc(inode, et, 1, &meta_ac, 5713 extra_blocks); 5714 if (ret) { 5715 mlog_errno(ret); 5716 goto bail; 5717 } 5718 5719 mutex_lock(&tl_inode->i_mutex); 5720 5721 if (ocfs2_truncate_log_needs_flush(osb)) { 5722 ret = __ocfs2_flush_truncate_log(osb); 5723 if (ret < 0) { 5724 mlog_errno(ret); 5725 goto out; 5726 } 5727 } 5728 5729 handle = ocfs2_start_trans(osb, 5730 ocfs2_remove_extent_credits(osb->sb) + credits); 5731 if (IS_ERR(handle)) { 5732 ret = PTR_ERR(handle); 5733 mlog_errno(ret); 5734 goto out; 5735 } 5736 5737 ret = ocfs2_et_root_journal_access(handle, et, 5738 OCFS2_JOURNAL_ACCESS_WRITE); 5739 if (ret) { 5740 mlog_errno(ret); 5741 goto out_commit; 5742 } 5743 5744 dquot_free_space_nodirty(inode, 5745 ocfs2_clusters_to_bytes(inode->i_sb, len)); 5746 5747 ret = ocfs2_remove_extent(handle, et, cpos, len, meta_ac, dealloc); 5748 if (ret) { 5749 mlog_errno(ret); 5750 goto out_commit; 5751 } 5752 5753 ocfs2_et_update_clusters(et, -len); 5754 ocfs2_update_inode_fsync_trans(handle, inode, 1); 5755 5756 ocfs2_journal_dirty(handle, et->et_root_bh); 5757 5758 if (phys_blkno) { 5759 if (flags & OCFS2_EXT_REFCOUNTED) 5760 ret = ocfs2_decrease_refcount(inode, handle, 5761 ocfs2_blocks_to_clusters(osb->sb, 5762 phys_blkno), 5763 len, meta_ac, 5764 dealloc, 1); 5765 else 5766 ret = ocfs2_truncate_log_append(osb, handle, 5767 phys_blkno, len); 5768 if (ret) 5769 mlog_errno(ret); 5770 5771 } 5772 5773 out_commit: 5774 ocfs2_commit_trans(osb, handle); 5775 out: 5776 mutex_unlock(&tl_inode->i_mutex); 5777 bail: 5778 if (meta_ac) 5779 ocfs2_free_alloc_context(meta_ac); 5780 5781 if (ref_tree) 5782 ocfs2_unlock_refcount_tree(osb, ref_tree, 1); 5783 5784 return ret; 5785 } 5786 5787 int ocfs2_truncate_log_needs_flush(struct ocfs2_super *osb) 5788 { 5789 struct buffer_head *tl_bh = osb->osb_tl_bh; 5790 struct ocfs2_dinode *di; 5791 struct ocfs2_truncate_log *tl; 5792 5793 di = (struct ocfs2_dinode *) tl_bh->b_data; 5794 tl = &di->id2.i_dealloc; 5795 5796 mlog_bug_on_msg(le16_to_cpu(tl->tl_used) > le16_to_cpu(tl->tl_count), 5797 "slot %d, invalid truncate log parameters: used = " 5798 "%u, count = %u\n", osb->slot_num, 5799 le16_to_cpu(tl->tl_used), le16_to_cpu(tl->tl_count)); 5800 return le16_to_cpu(tl->tl_used) == le16_to_cpu(tl->tl_count); 5801 } 5802 5803 static int ocfs2_truncate_log_can_coalesce(struct ocfs2_truncate_log *tl, 5804 unsigned int new_start) 5805 { 5806 unsigned int tail_index; 5807 unsigned int current_tail; 5808 5809 /* No records, nothing to coalesce */ 5810 if (!le16_to_cpu(tl->tl_used)) 5811 return 0; 5812 5813 tail_index = le16_to_cpu(tl->tl_used) - 1; 5814 current_tail = le32_to_cpu(tl->tl_recs[tail_index].t_start); 5815 current_tail += le32_to_cpu(tl->tl_recs[tail_index].t_clusters); 5816 5817 return current_tail == new_start; 5818 } 5819 5820 int ocfs2_truncate_log_append(struct ocfs2_super *osb, 5821 handle_t *handle, 5822 u64 start_blk, 5823 unsigned int num_clusters) 5824 { 5825 int status, index; 5826 unsigned int start_cluster, tl_count; 5827 struct inode *tl_inode = osb->osb_tl_inode; 5828 struct buffer_head *tl_bh = osb->osb_tl_bh; 5829 struct ocfs2_dinode *di; 5830 struct ocfs2_truncate_log *tl; 5831 5832 BUG_ON(mutex_trylock(&tl_inode->i_mutex)); 5833 5834 start_cluster = ocfs2_blocks_to_clusters(osb->sb, start_blk); 5835 5836 di = (struct ocfs2_dinode *) tl_bh->b_data; 5837 5838 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated 5839 * by the underlying call to ocfs2_read_inode_block(), so any 5840 * corruption is a code bug */ 5841 BUG_ON(!OCFS2_IS_VALID_DINODE(di)); 5842 5843 tl = &di->id2.i_dealloc; 5844 tl_count = le16_to_cpu(tl->tl_count); 5845 mlog_bug_on_msg(tl_count > ocfs2_truncate_recs_per_inode(osb->sb) || 5846 tl_count == 0, 5847 "Truncate record count on #%llu invalid " 5848 "wanted %u, actual %u\n", 5849 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, 5850 ocfs2_truncate_recs_per_inode(osb->sb), 5851 le16_to_cpu(tl->tl_count)); 5852 5853 /* Caller should have known to flush before calling us. */ 5854 index = le16_to_cpu(tl->tl_used); 5855 if (index >= tl_count) { 5856 status = -ENOSPC; 5857 mlog_errno(status); 5858 goto bail; 5859 } 5860 5861 status = ocfs2_journal_access_di(handle, INODE_CACHE(tl_inode), tl_bh, 5862 OCFS2_JOURNAL_ACCESS_WRITE); 5863 if (status < 0) { 5864 mlog_errno(status); 5865 goto bail; 5866 } 5867 5868 trace_ocfs2_truncate_log_append( 5869 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, index, 5870 start_cluster, num_clusters); 5871 if (ocfs2_truncate_log_can_coalesce(tl, start_cluster)) { 5872 /* 5873 * Move index back to the record we are coalescing with. 5874 * ocfs2_truncate_log_can_coalesce() guarantees nonzero 5875 */ 5876 index--; 5877 5878 num_clusters += le32_to_cpu(tl->tl_recs[index].t_clusters); 5879 trace_ocfs2_truncate_log_append( 5880 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, 5881 index, le32_to_cpu(tl->tl_recs[index].t_start), 5882 num_clusters); 5883 } else { 5884 tl->tl_recs[index].t_start = cpu_to_le32(start_cluster); 5885 tl->tl_used = cpu_to_le16(index + 1); 5886 } 5887 tl->tl_recs[index].t_clusters = cpu_to_le32(num_clusters); 5888 5889 ocfs2_journal_dirty(handle, tl_bh); 5890 5891 osb->truncated_clusters += num_clusters; 5892 bail: 5893 return status; 5894 } 5895 5896 static int ocfs2_replay_truncate_records(struct ocfs2_super *osb, 5897 handle_t *handle, 5898 struct inode *data_alloc_inode, 5899 struct buffer_head *data_alloc_bh) 5900 { 5901 int status = 0; 5902 int i; 5903 unsigned int num_clusters; 5904 u64 start_blk; 5905 struct ocfs2_truncate_rec rec; 5906 struct ocfs2_dinode *di; 5907 struct ocfs2_truncate_log *tl; 5908 struct inode *tl_inode = osb->osb_tl_inode; 5909 struct buffer_head *tl_bh = osb->osb_tl_bh; 5910 5911 di = (struct ocfs2_dinode *) tl_bh->b_data; 5912 tl = &di->id2.i_dealloc; 5913 i = le16_to_cpu(tl->tl_used) - 1; 5914 while (i >= 0) { 5915 /* Caller has given us at least enough credits to 5916 * update the truncate log dinode */ 5917 status = ocfs2_journal_access_di(handle, INODE_CACHE(tl_inode), tl_bh, 5918 OCFS2_JOURNAL_ACCESS_WRITE); 5919 if (status < 0) { 5920 mlog_errno(status); 5921 goto bail; 5922 } 5923 5924 tl->tl_used = cpu_to_le16(i); 5925 5926 ocfs2_journal_dirty(handle, tl_bh); 5927 5928 /* TODO: Perhaps we can calculate the bulk of the 5929 * credits up front rather than extending like 5930 * this. */ 5931 status = ocfs2_extend_trans(handle, 5932 OCFS2_TRUNCATE_LOG_FLUSH_ONE_REC); 5933 if (status < 0) { 5934 mlog_errno(status); 5935 goto bail; 5936 } 5937 5938 rec = tl->tl_recs[i]; 5939 start_blk = ocfs2_clusters_to_blocks(data_alloc_inode->i_sb, 5940 le32_to_cpu(rec.t_start)); 5941 num_clusters = le32_to_cpu(rec.t_clusters); 5942 5943 /* if start_blk is not set, we ignore the record as 5944 * invalid. */ 5945 if (start_blk) { 5946 trace_ocfs2_replay_truncate_records( 5947 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, 5948 i, le32_to_cpu(rec.t_start), num_clusters); 5949 5950 status = ocfs2_free_clusters(handle, data_alloc_inode, 5951 data_alloc_bh, start_blk, 5952 num_clusters); 5953 if (status < 0) { 5954 mlog_errno(status); 5955 goto bail; 5956 } 5957 } 5958 i--; 5959 } 5960 5961 osb->truncated_clusters = 0; 5962 5963 bail: 5964 return status; 5965 } 5966 5967 /* Expects you to already be holding tl_inode->i_mutex */ 5968 int __ocfs2_flush_truncate_log(struct ocfs2_super *osb) 5969 { 5970 int status; 5971 unsigned int num_to_flush; 5972 handle_t *handle; 5973 struct inode *tl_inode = osb->osb_tl_inode; 5974 struct inode *data_alloc_inode = NULL; 5975 struct buffer_head *tl_bh = osb->osb_tl_bh; 5976 struct buffer_head *data_alloc_bh = NULL; 5977 struct ocfs2_dinode *di; 5978 struct ocfs2_truncate_log *tl; 5979 5980 BUG_ON(mutex_trylock(&tl_inode->i_mutex)); 5981 5982 di = (struct ocfs2_dinode *) tl_bh->b_data; 5983 5984 /* tl_bh is loaded from ocfs2_truncate_log_init(). It's validated 5985 * by the underlying call to ocfs2_read_inode_block(), so any 5986 * corruption is a code bug */ 5987 BUG_ON(!OCFS2_IS_VALID_DINODE(di)); 5988 5989 tl = &di->id2.i_dealloc; 5990 num_to_flush = le16_to_cpu(tl->tl_used); 5991 trace_ocfs2_flush_truncate_log( 5992 (unsigned long long)OCFS2_I(tl_inode)->ip_blkno, 5993 num_to_flush); 5994 if (!num_to_flush) { 5995 status = 0; 5996 goto out; 5997 } 5998 5999 data_alloc_inode = ocfs2_get_system_file_inode(osb, 6000 GLOBAL_BITMAP_SYSTEM_INODE, 6001 OCFS2_INVALID_SLOT); 6002 if (!data_alloc_inode) { 6003 status = -EINVAL; 6004 mlog(ML_ERROR, "Could not get bitmap inode!\n"); 6005 goto out; 6006 } 6007 6008 mutex_lock(&data_alloc_inode->i_mutex); 6009 6010 status = ocfs2_inode_lock(data_alloc_inode, &data_alloc_bh, 1); 6011 if (status < 0) { 6012 mlog_errno(status); 6013 goto out_mutex; 6014 } 6015 6016 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE); 6017 if (IS_ERR(handle)) { 6018 status = PTR_ERR(handle); 6019 mlog_errno(status); 6020 goto out_unlock; 6021 } 6022 6023 status = ocfs2_replay_truncate_records(osb, handle, data_alloc_inode, 6024 data_alloc_bh); 6025 if (status < 0) 6026 mlog_errno(status); 6027 6028 ocfs2_commit_trans(osb, handle); 6029 6030 out_unlock: 6031 brelse(data_alloc_bh); 6032 ocfs2_inode_unlock(data_alloc_inode, 1); 6033 6034 out_mutex: 6035 mutex_unlock(&data_alloc_inode->i_mutex); 6036 iput(data_alloc_inode); 6037 6038 out: 6039 return status; 6040 } 6041 6042 int ocfs2_flush_truncate_log(struct ocfs2_super *osb) 6043 { 6044 int status; 6045 struct inode *tl_inode = osb->osb_tl_inode; 6046 6047 mutex_lock(&tl_inode->i_mutex); 6048 status = __ocfs2_flush_truncate_log(osb); 6049 mutex_unlock(&tl_inode->i_mutex); 6050 6051 return status; 6052 } 6053 6054 static void ocfs2_truncate_log_worker(struct work_struct *work) 6055 { 6056 int status; 6057 struct ocfs2_super *osb = 6058 container_of(work, struct ocfs2_super, 6059 osb_truncate_log_wq.work); 6060 6061 status = ocfs2_flush_truncate_log(osb); 6062 if (status < 0) 6063 mlog_errno(status); 6064 else 6065 ocfs2_init_steal_slots(osb); 6066 } 6067 6068 #define OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL (2 * HZ) 6069 void ocfs2_schedule_truncate_log_flush(struct ocfs2_super *osb, 6070 int cancel) 6071 { 6072 if (osb->osb_tl_inode && 6073 atomic_read(&osb->osb_tl_disable) == 0) { 6074 /* We want to push off log flushes while truncates are 6075 * still running. */ 6076 if (cancel) 6077 cancel_delayed_work(&osb->osb_truncate_log_wq); 6078 6079 queue_delayed_work(ocfs2_wq, &osb->osb_truncate_log_wq, 6080 OCFS2_TRUNCATE_LOG_FLUSH_INTERVAL); 6081 } 6082 } 6083 6084 static int ocfs2_get_truncate_log_info(struct ocfs2_super *osb, 6085 int slot_num, 6086 struct inode **tl_inode, 6087 struct buffer_head **tl_bh) 6088 { 6089 int status; 6090 struct inode *inode = NULL; 6091 struct buffer_head *bh = NULL; 6092 6093 inode = ocfs2_get_system_file_inode(osb, 6094 TRUNCATE_LOG_SYSTEM_INODE, 6095 slot_num); 6096 if (!inode) { 6097 status = -EINVAL; 6098 mlog(ML_ERROR, "Could not get load truncate log inode!\n"); 6099 goto bail; 6100 } 6101 6102 status = ocfs2_read_inode_block(inode, &bh); 6103 if (status < 0) { 6104 iput(inode); 6105 mlog_errno(status); 6106 goto bail; 6107 } 6108 6109 *tl_inode = inode; 6110 *tl_bh = bh; 6111 bail: 6112 return status; 6113 } 6114 6115 /* called during the 1st stage of node recovery. we stamp a clean 6116 * truncate log and pass back a copy for processing later. if the 6117 * truncate log does not require processing, a *tl_copy is set to 6118 * NULL. */ 6119 int ocfs2_begin_truncate_log_recovery(struct ocfs2_super *osb, 6120 int slot_num, 6121 struct ocfs2_dinode **tl_copy) 6122 { 6123 int status; 6124 struct inode *tl_inode = NULL; 6125 struct buffer_head *tl_bh = NULL; 6126 struct ocfs2_dinode *di; 6127 struct ocfs2_truncate_log *tl; 6128 6129 *tl_copy = NULL; 6130 6131 trace_ocfs2_begin_truncate_log_recovery(slot_num); 6132 6133 status = ocfs2_get_truncate_log_info(osb, slot_num, &tl_inode, &tl_bh); 6134 if (status < 0) { 6135 mlog_errno(status); 6136 goto bail; 6137 } 6138 6139 di = (struct ocfs2_dinode *) tl_bh->b_data; 6140 6141 /* tl_bh is loaded from ocfs2_get_truncate_log_info(). It's 6142 * validated by the underlying call to ocfs2_read_inode_block(), 6143 * so any corruption is a code bug */ 6144 BUG_ON(!OCFS2_IS_VALID_DINODE(di)); 6145 6146 tl = &di->id2.i_dealloc; 6147 if (le16_to_cpu(tl->tl_used)) { 6148 trace_ocfs2_truncate_log_recovery_num(le16_to_cpu(tl->tl_used)); 6149 6150 *tl_copy = kmalloc(tl_bh->b_size, GFP_KERNEL); 6151 if (!(*tl_copy)) { 6152 status = -ENOMEM; 6153 mlog_errno(status); 6154 goto bail; 6155 } 6156 6157 /* Assuming the write-out below goes well, this copy 6158 * will be passed back to recovery for processing. */ 6159 memcpy(*tl_copy, tl_bh->b_data, tl_bh->b_size); 6160 6161 /* All we need to do to clear the truncate log is set 6162 * tl_used. */ 6163 tl->tl_used = 0; 6164 6165 ocfs2_compute_meta_ecc(osb->sb, tl_bh->b_data, &di->i_check); 6166 status = ocfs2_write_block(osb, tl_bh, INODE_CACHE(tl_inode)); 6167 if (status < 0) { 6168 mlog_errno(status); 6169 goto bail; 6170 } 6171 } 6172 6173 bail: 6174 if (tl_inode) 6175 iput(tl_inode); 6176 brelse(tl_bh); 6177 6178 if (status < 0 && (*tl_copy)) { 6179 kfree(*tl_copy); 6180 *tl_copy = NULL; 6181 mlog_errno(status); 6182 } 6183 6184 return status; 6185 } 6186 6187 int ocfs2_complete_truncate_log_recovery(struct ocfs2_super *osb, 6188 struct ocfs2_dinode *tl_copy) 6189 { 6190 int status = 0; 6191 int i; 6192 unsigned int clusters, num_recs, start_cluster; 6193 u64 start_blk; 6194 handle_t *handle; 6195 struct inode *tl_inode = osb->osb_tl_inode; 6196 struct ocfs2_truncate_log *tl; 6197 6198 if (OCFS2_I(tl_inode)->ip_blkno == le64_to_cpu(tl_copy->i_blkno)) { 6199 mlog(ML_ERROR, "Asked to recover my own truncate log!\n"); 6200 return -EINVAL; 6201 } 6202 6203 tl = &tl_copy->id2.i_dealloc; 6204 num_recs = le16_to_cpu(tl->tl_used); 6205 trace_ocfs2_complete_truncate_log_recovery( 6206 (unsigned long long)le64_to_cpu(tl_copy->i_blkno), 6207 num_recs); 6208 6209 mutex_lock(&tl_inode->i_mutex); 6210 for(i = 0; i < num_recs; i++) { 6211 if (ocfs2_truncate_log_needs_flush(osb)) { 6212 status = __ocfs2_flush_truncate_log(osb); 6213 if (status < 0) { 6214 mlog_errno(status); 6215 goto bail_up; 6216 } 6217 } 6218 6219 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE); 6220 if (IS_ERR(handle)) { 6221 status = PTR_ERR(handle); 6222 mlog_errno(status); 6223 goto bail_up; 6224 } 6225 6226 clusters = le32_to_cpu(tl->tl_recs[i].t_clusters); 6227 start_cluster = le32_to_cpu(tl->tl_recs[i].t_start); 6228 start_blk = ocfs2_clusters_to_blocks(osb->sb, start_cluster); 6229 6230 status = ocfs2_truncate_log_append(osb, handle, 6231 start_blk, clusters); 6232 ocfs2_commit_trans(osb, handle); 6233 if (status < 0) { 6234 mlog_errno(status); 6235 goto bail_up; 6236 } 6237 } 6238 6239 bail_up: 6240 mutex_unlock(&tl_inode->i_mutex); 6241 6242 return status; 6243 } 6244 6245 void ocfs2_truncate_log_shutdown(struct ocfs2_super *osb) 6246 { 6247 int status; 6248 struct inode *tl_inode = osb->osb_tl_inode; 6249 6250 atomic_set(&osb->osb_tl_disable, 1); 6251 6252 if (tl_inode) { 6253 cancel_delayed_work(&osb->osb_truncate_log_wq); 6254 flush_workqueue(ocfs2_wq); 6255 6256 status = ocfs2_flush_truncate_log(osb); 6257 if (status < 0) 6258 mlog_errno(status); 6259 6260 brelse(osb->osb_tl_bh); 6261 iput(osb->osb_tl_inode); 6262 } 6263 } 6264 6265 int ocfs2_truncate_log_init(struct ocfs2_super *osb) 6266 { 6267 int status; 6268 struct inode *tl_inode = NULL; 6269 struct buffer_head *tl_bh = NULL; 6270 6271 status = ocfs2_get_truncate_log_info(osb, 6272 osb->slot_num, 6273 &tl_inode, 6274 &tl_bh); 6275 if (status < 0) 6276 mlog_errno(status); 6277 6278 /* ocfs2_truncate_log_shutdown keys on the existence of 6279 * osb->osb_tl_inode so we don't set any of the osb variables 6280 * until we're sure all is well. */ 6281 INIT_DELAYED_WORK(&osb->osb_truncate_log_wq, 6282 ocfs2_truncate_log_worker); 6283 atomic_set(&osb->osb_tl_disable, 0); 6284 osb->osb_tl_bh = tl_bh; 6285 osb->osb_tl_inode = tl_inode; 6286 6287 return status; 6288 } 6289 6290 /* 6291 * Delayed de-allocation of suballocator blocks. 6292 * 6293 * Some sets of block de-allocations might involve multiple suballocator inodes. 6294 * 6295 * The locking for this can get extremely complicated, especially when 6296 * the suballocator inodes to delete from aren't known until deep 6297 * within an unrelated codepath. 6298 * 6299 * ocfs2_extent_block structures are a good example of this - an inode 6300 * btree could have been grown by any number of nodes each allocating 6301 * out of their own suballoc inode. 6302 * 6303 * These structures allow the delay of block de-allocation until a 6304 * later time, when locking of multiple cluster inodes won't cause 6305 * deadlock. 6306 */ 6307 6308 /* 6309 * Describe a single bit freed from a suballocator. For the block 6310 * suballocators, it represents one block. For the global cluster 6311 * allocator, it represents some clusters and free_bit indicates 6312 * clusters number. 6313 */ 6314 struct ocfs2_cached_block_free { 6315 struct ocfs2_cached_block_free *free_next; 6316 u64 free_bg; 6317 u64 free_blk; 6318 unsigned int free_bit; 6319 }; 6320 6321 struct ocfs2_per_slot_free_list { 6322 struct ocfs2_per_slot_free_list *f_next_suballocator; 6323 int f_inode_type; 6324 int f_slot; 6325 struct ocfs2_cached_block_free *f_first; 6326 }; 6327 6328 static int ocfs2_free_cached_blocks(struct ocfs2_super *osb, 6329 int sysfile_type, 6330 int slot, 6331 struct ocfs2_cached_block_free *head) 6332 { 6333 int ret; 6334 u64 bg_blkno; 6335 handle_t *handle; 6336 struct inode *inode; 6337 struct buffer_head *di_bh = NULL; 6338 struct ocfs2_cached_block_free *tmp; 6339 6340 inode = ocfs2_get_system_file_inode(osb, sysfile_type, slot); 6341 if (!inode) { 6342 ret = -EINVAL; 6343 mlog_errno(ret); 6344 goto out; 6345 } 6346 6347 mutex_lock(&inode->i_mutex); 6348 6349 ret = ocfs2_inode_lock(inode, &di_bh, 1); 6350 if (ret) { 6351 mlog_errno(ret); 6352 goto out_mutex; 6353 } 6354 6355 handle = ocfs2_start_trans(osb, OCFS2_SUBALLOC_FREE); 6356 if (IS_ERR(handle)) { 6357 ret = PTR_ERR(handle); 6358 mlog_errno(ret); 6359 goto out_unlock; 6360 } 6361 6362 while (head) { 6363 if (head->free_bg) 6364 bg_blkno = head->free_bg; 6365 else 6366 bg_blkno = ocfs2_which_suballoc_group(head->free_blk, 6367 head->free_bit); 6368 trace_ocfs2_free_cached_blocks( 6369 (unsigned long long)head->free_blk, head->free_bit); 6370 6371 ret = ocfs2_free_suballoc_bits(handle, inode, di_bh, 6372 head->free_bit, bg_blkno, 1); 6373 if (ret) { 6374 mlog_errno(ret); 6375 goto out_journal; 6376 } 6377 6378 ret = ocfs2_extend_trans(handle, OCFS2_SUBALLOC_FREE); 6379 if (ret) { 6380 mlog_errno(ret); 6381 goto out_journal; 6382 } 6383 6384 tmp = head; 6385 head = head->free_next; 6386 kfree(tmp); 6387 } 6388 6389 out_journal: 6390 ocfs2_commit_trans(osb, handle); 6391 6392 out_unlock: 6393 ocfs2_inode_unlock(inode, 1); 6394 brelse(di_bh); 6395 out_mutex: 6396 mutex_unlock(&inode->i_mutex); 6397 iput(inode); 6398 out: 6399 while(head) { 6400 /* Premature exit may have left some dangling items. */ 6401 tmp = head; 6402 head = head->free_next; 6403 kfree(tmp); 6404 } 6405 6406 return ret; 6407 } 6408 6409 int ocfs2_cache_cluster_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt, 6410 u64 blkno, unsigned int bit) 6411 { 6412 int ret = 0; 6413 struct ocfs2_cached_block_free *item; 6414 6415 item = kzalloc(sizeof(*item), GFP_NOFS); 6416 if (item == NULL) { 6417 ret = -ENOMEM; 6418 mlog_errno(ret); 6419 return ret; 6420 } 6421 6422 trace_ocfs2_cache_cluster_dealloc((unsigned long long)blkno, bit); 6423 6424 item->free_blk = blkno; 6425 item->free_bit = bit; 6426 item->free_next = ctxt->c_global_allocator; 6427 6428 ctxt->c_global_allocator = item; 6429 return ret; 6430 } 6431 6432 static int ocfs2_free_cached_clusters(struct ocfs2_super *osb, 6433 struct ocfs2_cached_block_free *head) 6434 { 6435 struct ocfs2_cached_block_free *tmp; 6436 struct inode *tl_inode = osb->osb_tl_inode; 6437 handle_t *handle; 6438 int ret = 0; 6439 6440 mutex_lock(&tl_inode->i_mutex); 6441 6442 while (head) { 6443 if (ocfs2_truncate_log_needs_flush(osb)) { 6444 ret = __ocfs2_flush_truncate_log(osb); 6445 if (ret < 0) { 6446 mlog_errno(ret); 6447 break; 6448 } 6449 } 6450 6451 handle = ocfs2_start_trans(osb, OCFS2_TRUNCATE_LOG_UPDATE); 6452 if (IS_ERR(handle)) { 6453 ret = PTR_ERR(handle); 6454 mlog_errno(ret); 6455 break; 6456 } 6457 6458 ret = ocfs2_truncate_log_append(osb, handle, head->free_blk, 6459 head->free_bit); 6460 6461 ocfs2_commit_trans(osb, handle); 6462 tmp = head; 6463 head = head->free_next; 6464 kfree(tmp); 6465 6466 if (ret < 0) { 6467 mlog_errno(ret); 6468 break; 6469 } 6470 } 6471 6472 mutex_unlock(&tl_inode->i_mutex); 6473 6474 while (head) { 6475 /* Premature exit may have left some dangling items. */ 6476 tmp = head; 6477 head = head->free_next; 6478 kfree(tmp); 6479 } 6480 6481 return ret; 6482 } 6483 6484 int ocfs2_run_deallocs(struct ocfs2_super *osb, 6485 struct ocfs2_cached_dealloc_ctxt *ctxt) 6486 { 6487 int ret = 0, ret2; 6488 struct ocfs2_per_slot_free_list *fl; 6489 6490 if (!ctxt) 6491 return 0; 6492 6493 while (ctxt->c_first_suballocator) { 6494 fl = ctxt->c_first_suballocator; 6495 6496 if (fl->f_first) { 6497 trace_ocfs2_run_deallocs(fl->f_inode_type, 6498 fl->f_slot); 6499 ret2 = ocfs2_free_cached_blocks(osb, 6500 fl->f_inode_type, 6501 fl->f_slot, 6502 fl->f_first); 6503 if (ret2) 6504 mlog_errno(ret2); 6505 if (!ret) 6506 ret = ret2; 6507 } 6508 6509 ctxt->c_first_suballocator = fl->f_next_suballocator; 6510 kfree(fl); 6511 } 6512 6513 if (ctxt->c_global_allocator) { 6514 ret2 = ocfs2_free_cached_clusters(osb, 6515 ctxt->c_global_allocator); 6516 if (ret2) 6517 mlog_errno(ret2); 6518 if (!ret) 6519 ret = ret2; 6520 6521 ctxt->c_global_allocator = NULL; 6522 } 6523 6524 return ret; 6525 } 6526 6527 static struct ocfs2_per_slot_free_list * 6528 ocfs2_find_per_slot_free_list(int type, 6529 int slot, 6530 struct ocfs2_cached_dealloc_ctxt *ctxt) 6531 { 6532 struct ocfs2_per_slot_free_list *fl = ctxt->c_first_suballocator; 6533 6534 while (fl) { 6535 if (fl->f_inode_type == type && fl->f_slot == slot) 6536 return fl; 6537 6538 fl = fl->f_next_suballocator; 6539 } 6540 6541 fl = kmalloc(sizeof(*fl), GFP_NOFS); 6542 if (fl) { 6543 fl->f_inode_type = type; 6544 fl->f_slot = slot; 6545 fl->f_first = NULL; 6546 fl->f_next_suballocator = ctxt->c_first_suballocator; 6547 6548 ctxt->c_first_suballocator = fl; 6549 } 6550 return fl; 6551 } 6552 6553 int ocfs2_cache_block_dealloc(struct ocfs2_cached_dealloc_ctxt *ctxt, 6554 int type, int slot, u64 suballoc, 6555 u64 blkno, unsigned int bit) 6556 { 6557 int ret; 6558 struct ocfs2_per_slot_free_list *fl; 6559 struct ocfs2_cached_block_free *item; 6560 6561 fl = ocfs2_find_per_slot_free_list(type, slot, ctxt); 6562 if (fl == NULL) { 6563 ret = -ENOMEM; 6564 mlog_errno(ret); 6565 goto out; 6566 } 6567 6568 item = kzalloc(sizeof(*item), GFP_NOFS); 6569 if (item == NULL) { 6570 ret = -ENOMEM; 6571 mlog_errno(ret); 6572 goto out; 6573 } 6574 6575 trace_ocfs2_cache_block_dealloc(type, slot, 6576 (unsigned long long)suballoc, 6577 (unsigned long long)blkno, bit); 6578 6579 item->free_bg = suballoc; 6580 item->free_blk = blkno; 6581 item->free_bit = bit; 6582 item->free_next = fl->f_first; 6583 6584 fl->f_first = item; 6585 6586 ret = 0; 6587 out: 6588 return ret; 6589 } 6590 6591 static int ocfs2_cache_extent_block_free(struct ocfs2_cached_dealloc_ctxt *ctxt, 6592 struct ocfs2_extent_block *eb) 6593 { 6594 return ocfs2_cache_block_dealloc(ctxt, EXTENT_ALLOC_SYSTEM_INODE, 6595 le16_to_cpu(eb->h_suballoc_slot), 6596 le64_to_cpu(eb->h_suballoc_loc), 6597 le64_to_cpu(eb->h_blkno), 6598 le16_to_cpu(eb->h_suballoc_bit)); 6599 } 6600 6601 static int ocfs2_zero_func(handle_t *handle, struct buffer_head *bh) 6602 { 6603 set_buffer_uptodate(bh); 6604 mark_buffer_dirty(bh); 6605 return 0; 6606 } 6607 6608 void ocfs2_map_and_dirty_page(struct inode *inode, handle_t *handle, 6609 unsigned int from, unsigned int to, 6610 struct page *page, int zero, u64 *phys) 6611 { 6612 int ret, partial = 0; 6613 6614 ret = ocfs2_map_page_blocks(page, phys, inode, from, to, 0); 6615 if (ret) 6616 mlog_errno(ret); 6617 6618 if (zero) 6619 zero_user_segment(page, from, to); 6620 6621 /* 6622 * Need to set the buffers we zero'd into uptodate 6623 * here if they aren't - ocfs2_map_page_blocks() 6624 * might've skipped some 6625 */ 6626 ret = walk_page_buffers(handle, page_buffers(page), 6627 from, to, &partial, 6628 ocfs2_zero_func); 6629 if (ret < 0) 6630 mlog_errno(ret); 6631 else if (ocfs2_should_order_data(inode)) { 6632 ret = ocfs2_jbd2_file_inode(handle, inode); 6633 if (ret < 0) 6634 mlog_errno(ret); 6635 } 6636 6637 if (!partial) 6638 SetPageUptodate(page); 6639 6640 flush_dcache_page(page); 6641 } 6642 6643 static void ocfs2_zero_cluster_pages(struct inode *inode, loff_t start, 6644 loff_t end, struct page **pages, 6645 int numpages, u64 phys, handle_t *handle) 6646 { 6647 int i; 6648 struct page *page; 6649 unsigned int from, to = PAGE_CACHE_SIZE; 6650 struct super_block *sb = inode->i_sb; 6651 6652 BUG_ON(!ocfs2_sparse_alloc(OCFS2_SB(sb))); 6653 6654 if (numpages == 0) 6655 goto out; 6656 6657 to = PAGE_CACHE_SIZE; 6658 for(i = 0; i < numpages; i++) { 6659 page = pages[i]; 6660 6661 from = start & (PAGE_CACHE_SIZE - 1); 6662 if ((end >> PAGE_CACHE_SHIFT) == page->index) 6663 to = end & (PAGE_CACHE_SIZE - 1); 6664 6665 BUG_ON(from > PAGE_CACHE_SIZE); 6666 BUG_ON(to > PAGE_CACHE_SIZE); 6667 6668 ocfs2_map_and_dirty_page(inode, handle, from, to, page, 1, 6669 &phys); 6670 6671 start = (page->index + 1) << PAGE_CACHE_SHIFT; 6672 } 6673 out: 6674 if (pages) 6675 ocfs2_unlock_and_free_pages(pages, numpages); 6676 } 6677 6678 int ocfs2_grab_pages(struct inode *inode, loff_t start, loff_t end, 6679 struct page **pages, int *num) 6680 { 6681 int numpages, ret = 0; 6682 struct address_space *mapping = inode->i_mapping; 6683 unsigned long index; 6684 loff_t last_page_bytes; 6685 6686 BUG_ON(start > end); 6687 6688 numpages = 0; 6689 last_page_bytes = PAGE_ALIGN(end); 6690 index = start >> PAGE_CACHE_SHIFT; 6691 do { 6692 pages[numpages] = find_or_create_page(mapping, index, GFP_NOFS); 6693 if (!pages[numpages]) { 6694 ret = -ENOMEM; 6695 mlog_errno(ret); 6696 goto out; 6697 } 6698 6699 numpages++; 6700 index++; 6701 } while (index < (last_page_bytes >> PAGE_CACHE_SHIFT)); 6702 6703 out: 6704 if (ret != 0) { 6705 if (pages) 6706 ocfs2_unlock_and_free_pages(pages, numpages); 6707 numpages = 0; 6708 } 6709 6710 *num = numpages; 6711 6712 return ret; 6713 } 6714 6715 static int ocfs2_grab_eof_pages(struct inode *inode, loff_t start, loff_t end, 6716 struct page **pages, int *num) 6717 { 6718 struct super_block *sb = inode->i_sb; 6719 6720 BUG_ON(start >> OCFS2_SB(sb)->s_clustersize_bits != 6721 (end - 1) >> OCFS2_SB(sb)->s_clustersize_bits); 6722 6723 return ocfs2_grab_pages(inode, start, end, pages, num); 6724 } 6725 6726 /* 6727 * Zero the area past i_size but still within an allocated 6728 * cluster. This avoids exposing nonzero data on subsequent file 6729 * extends. 6730 * 6731 * We need to call this before i_size is updated on the inode because 6732 * otherwise block_write_full_page() will skip writeout of pages past 6733 * i_size. The new_i_size parameter is passed for this reason. 6734 */ 6735 int ocfs2_zero_range_for_truncate(struct inode *inode, handle_t *handle, 6736 u64 range_start, u64 range_end) 6737 { 6738 int ret = 0, numpages; 6739 struct page **pages = NULL; 6740 u64 phys; 6741 unsigned int ext_flags; 6742 struct super_block *sb = inode->i_sb; 6743 6744 /* 6745 * File systems which don't support sparse files zero on every 6746 * extend. 6747 */ 6748 if (!ocfs2_sparse_alloc(OCFS2_SB(sb))) 6749 return 0; 6750 6751 pages = kcalloc(ocfs2_pages_per_cluster(sb), 6752 sizeof(struct page *), GFP_NOFS); 6753 if (pages == NULL) { 6754 ret = -ENOMEM; 6755 mlog_errno(ret); 6756 goto out; 6757 } 6758 6759 if (range_start == range_end) 6760 goto out; 6761 6762 ret = ocfs2_extent_map_get_blocks(inode, 6763 range_start >> sb->s_blocksize_bits, 6764 &phys, NULL, &ext_flags); 6765 if (ret) { 6766 mlog_errno(ret); 6767 goto out; 6768 } 6769 6770 /* 6771 * Tail is a hole, or is marked unwritten. In either case, we 6772 * can count on read and write to return/push zero's. 6773 */ 6774 if (phys == 0 || ext_flags & OCFS2_EXT_UNWRITTEN) 6775 goto out; 6776 6777 ret = ocfs2_grab_eof_pages(inode, range_start, range_end, pages, 6778 &numpages); 6779 if (ret) { 6780 mlog_errno(ret); 6781 goto out; 6782 } 6783 6784 ocfs2_zero_cluster_pages(inode, range_start, range_end, pages, 6785 numpages, phys, handle); 6786 6787 /* 6788 * Initiate writeout of the pages we zero'd here. We don't 6789 * wait on them - the truncate_inode_pages() call later will 6790 * do that for us. 6791 */ 6792 ret = filemap_fdatawrite_range(inode->i_mapping, range_start, 6793 range_end - 1); 6794 if (ret) 6795 mlog_errno(ret); 6796 6797 out: 6798 kfree(pages); 6799 6800 return ret; 6801 } 6802 6803 static void ocfs2_zero_dinode_id2_with_xattr(struct inode *inode, 6804 struct ocfs2_dinode *di) 6805 { 6806 unsigned int blocksize = 1 << inode->i_sb->s_blocksize_bits; 6807 unsigned int xattrsize = le16_to_cpu(di->i_xattr_inline_size); 6808 6809 if (le16_to_cpu(di->i_dyn_features) & OCFS2_INLINE_XATTR_FL) 6810 memset(&di->id2, 0, blocksize - 6811 offsetof(struct ocfs2_dinode, id2) - 6812 xattrsize); 6813 else 6814 memset(&di->id2, 0, blocksize - 6815 offsetof(struct ocfs2_dinode, id2)); 6816 } 6817 6818 void ocfs2_dinode_new_extent_list(struct inode *inode, 6819 struct ocfs2_dinode *di) 6820 { 6821 ocfs2_zero_dinode_id2_with_xattr(inode, di); 6822 di->id2.i_list.l_tree_depth = 0; 6823 di->id2.i_list.l_next_free_rec = 0; 6824 di->id2.i_list.l_count = cpu_to_le16( 6825 ocfs2_extent_recs_per_inode_with_xattr(inode->i_sb, di)); 6826 } 6827 6828 void ocfs2_set_inode_data_inline(struct inode *inode, struct ocfs2_dinode *di) 6829 { 6830 struct ocfs2_inode_info *oi = OCFS2_I(inode); 6831 struct ocfs2_inline_data *idata = &di->id2.i_data; 6832 6833 spin_lock(&oi->ip_lock); 6834 oi->ip_dyn_features |= OCFS2_INLINE_DATA_FL; 6835 di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features); 6836 spin_unlock(&oi->ip_lock); 6837 6838 /* 6839 * We clear the entire i_data structure here so that all 6840 * fields can be properly initialized. 6841 */ 6842 ocfs2_zero_dinode_id2_with_xattr(inode, di); 6843 6844 idata->id_count = cpu_to_le16( 6845 ocfs2_max_inline_data_with_xattr(inode->i_sb, di)); 6846 } 6847 6848 int ocfs2_convert_inline_data_to_extents(struct inode *inode, 6849 struct buffer_head *di_bh) 6850 { 6851 int ret, i, has_data, num_pages = 0; 6852 int need_free = 0; 6853 u32 bit_off, num; 6854 handle_t *handle; 6855 u64 uninitialized_var(block); 6856 struct ocfs2_inode_info *oi = OCFS2_I(inode); 6857 struct ocfs2_super *osb = OCFS2_SB(inode->i_sb); 6858 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; 6859 struct ocfs2_alloc_context *data_ac = NULL; 6860 struct page **pages = NULL; 6861 loff_t end = osb->s_clustersize; 6862 struct ocfs2_extent_tree et; 6863 int did_quota = 0; 6864 6865 has_data = i_size_read(inode) ? 1 : 0; 6866 6867 if (has_data) { 6868 pages = kcalloc(ocfs2_pages_per_cluster(osb->sb), 6869 sizeof(struct page *), GFP_NOFS); 6870 if (pages == NULL) { 6871 ret = -ENOMEM; 6872 mlog_errno(ret); 6873 return ret; 6874 } 6875 6876 ret = ocfs2_reserve_clusters(osb, 1, &data_ac); 6877 if (ret) { 6878 mlog_errno(ret); 6879 goto free_pages; 6880 } 6881 } 6882 6883 handle = ocfs2_start_trans(osb, 6884 ocfs2_inline_to_extents_credits(osb->sb)); 6885 if (IS_ERR(handle)) { 6886 ret = PTR_ERR(handle); 6887 mlog_errno(ret); 6888 goto out; 6889 } 6890 6891 ret = ocfs2_journal_access_di(handle, INODE_CACHE(inode), di_bh, 6892 OCFS2_JOURNAL_ACCESS_WRITE); 6893 if (ret) { 6894 mlog_errno(ret); 6895 goto out_commit; 6896 } 6897 6898 if (has_data) { 6899 unsigned int page_end; 6900 u64 phys; 6901 6902 ret = dquot_alloc_space_nodirty(inode, 6903 ocfs2_clusters_to_bytes(osb->sb, 1)); 6904 if (ret) 6905 goto out_commit; 6906 did_quota = 1; 6907 6908 data_ac->ac_resv = &OCFS2_I(inode)->ip_la_data_resv; 6909 6910 ret = ocfs2_claim_clusters(handle, data_ac, 1, &bit_off, 6911 &num); 6912 if (ret) { 6913 mlog_errno(ret); 6914 goto out_commit; 6915 } 6916 6917 /* 6918 * Save two copies, one for insert, and one that can 6919 * be changed by ocfs2_map_and_dirty_page() below. 6920 */ 6921 block = phys = ocfs2_clusters_to_blocks(inode->i_sb, bit_off); 6922 6923 /* 6924 * Non sparse file systems zero on extend, so no need 6925 * to do that now. 6926 */ 6927 if (!ocfs2_sparse_alloc(osb) && 6928 PAGE_CACHE_SIZE < osb->s_clustersize) 6929 end = PAGE_CACHE_SIZE; 6930 6931 ret = ocfs2_grab_eof_pages(inode, 0, end, pages, &num_pages); 6932 if (ret) { 6933 mlog_errno(ret); 6934 need_free = 1; 6935 goto out_commit; 6936 } 6937 6938 /* 6939 * This should populate the 1st page for us and mark 6940 * it up to date. 6941 */ 6942 ret = ocfs2_read_inline_data(inode, pages[0], di_bh); 6943 if (ret) { 6944 mlog_errno(ret); 6945 need_free = 1; 6946 goto out_unlock; 6947 } 6948 6949 page_end = PAGE_CACHE_SIZE; 6950 if (PAGE_CACHE_SIZE > osb->s_clustersize) 6951 page_end = osb->s_clustersize; 6952 6953 for (i = 0; i < num_pages; i++) 6954 ocfs2_map_and_dirty_page(inode, handle, 0, page_end, 6955 pages[i], i > 0, &phys); 6956 } 6957 6958 spin_lock(&oi->ip_lock); 6959 oi->ip_dyn_features &= ~OCFS2_INLINE_DATA_FL; 6960 di->i_dyn_features = cpu_to_le16(oi->ip_dyn_features); 6961 spin_unlock(&oi->ip_lock); 6962 6963 ocfs2_update_inode_fsync_trans(handle, inode, 1); 6964 ocfs2_dinode_new_extent_list(inode, di); 6965 6966 ocfs2_journal_dirty(handle, di_bh); 6967 6968 if (has_data) { 6969 /* 6970 * An error at this point should be extremely rare. If 6971 * this proves to be false, we could always re-build 6972 * the in-inode data from our pages. 6973 */ 6974 ocfs2_init_dinode_extent_tree(&et, INODE_CACHE(inode), di_bh); 6975 ret = ocfs2_insert_extent(handle, &et, 0, block, 1, 0, NULL); 6976 if (ret) { 6977 mlog_errno(ret); 6978 need_free = 1; 6979 goto out_unlock; 6980 } 6981 6982 inode->i_blocks = ocfs2_inode_sector_count(inode); 6983 } 6984 6985 out_unlock: 6986 if (pages) 6987 ocfs2_unlock_and_free_pages(pages, num_pages); 6988 6989 out_commit: 6990 if (ret < 0 && did_quota) 6991 dquot_free_space_nodirty(inode, 6992 ocfs2_clusters_to_bytes(osb->sb, 1)); 6993 6994 if (need_free) { 6995 if (data_ac->ac_which == OCFS2_AC_USE_LOCAL) 6996 ocfs2_free_local_alloc_bits(osb, handle, data_ac, 6997 bit_off, num); 6998 else 6999 ocfs2_free_clusters(handle, 7000 data_ac->ac_inode, 7001 data_ac->ac_bh, 7002 ocfs2_clusters_to_blocks(osb->sb, bit_off), 7003 num); 7004 } 7005 7006 ocfs2_commit_trans(osb, handle); 7007 7008 out: 7009 if (data_ac) 7010 ocfs2_free_alloc_context(data_ac); 7011 free_pages: 7012 kfree(pages); 7013 return ret; 7014 } 7015 7016 /* 7017 * It is expected, that by the time you call this function, 7018 * inode->i_size and fe->i_size have been adjusted. 7019 * 7020 * WARNING: This will kfree the truncate context 7021 */ 7022 int ocfs2_commit_truncate(struct ocfs2_super *osb, 7023 struct inode *inode, 7024 struct buffer_head *di_bh) 7025 { 7026 int status = 0, i, flags = 0; 7027 u32 new_highest_cpos, range, trunc_cpos, trunc_len, phys_cpos, coff; 7028 u64 blkno = 0; 7029 struct ocfs2_extent_list *el; 7030 struct ocfs2_extent_rec *rec; 7031 struct ocfs2_path *path = NULL; 7032 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; 7033 struct ocfs2_extent_list *root_el = &(di->id2.i_list); 7034 u64 refcount_loc = le64_to_cpu(di->i_refcount_loc); 7035 struct ocfs2_extent_tree et; 7036 struct ocfs2_cached_dealloc_ctxt dealloc; 7037 struct ocfs2_refcount_tree *ref_tree = NULL; 7038 7039 ocfs2_init_dinode_extent_tree(&et, INODE_CACHE(inode), di_bh); 7040 ocfs2_init_dealloc_ctxt(&dealloc); 7041 7042 new_highest_cpos = ocfs2_clusters_for_bytes(osb->sb, 7043 i_size_read(inode)); 7044 7045 path = ocfs2_new_path(di_bh, &di->id2.i_list, 7046 ocfs2_journal_access_di); 7047 if (!path) { 7048 status = -ENOMEM; 7049 mlog_errno(status); 7050 goto bail; 7051 } 7052 7053 ocfs2_extent_map_trunc(inode, new_highest_cpos); 7054 7055 start: 7056 /* 7057 * Check that we still have allocation to delete. 7058 */ 7059 if (OCFS2_I(inode)->ip_clusters == 0) { 7060 status = 0; 7061 goto bail; 7062 } 7063 7064 /* 7065 * Truncate always works against the rightmost tree branch. 7066 */ 7067 status = ocfs2_find_path(INODE_CACHE(inode), path, UINT_MAX); 7068 if (status) { 7069 mlog_errno(status); 7070 goto bail; 7071 } 7072 7073 trace_ocfs2_commit_truncate( 7074 (unsigned long long)OCFS2_I(inode)->ip_blkno, 7075 new_highest_cpos, 7076 OCFS2_I(inode)->ip_clusters, 7077 path->p_tree_depth); 7078 7079 /* 7080 * By now, el will point to the extent list on the bottom most 7081 * portion of this tree. Only the tail record is considered in 7082 * each pass. 7083 * 7084 * We handle the following cases, in order: 7085 * - empty extent: delete the remaining branch 7086 * - remove the entire record 7087 * - remove a partial record 7088 * - no record needs to be removed (truncate has completed) 7089 */ 7090 el = path_leaf_el(path); 7091 if (le16_to_cpu(el->l_next_free_rec) == 0) { 7092 ocfs2_error(inode->i_sb, 7093 "Inode %llu has empty extent block at %llu\n", 7094 (unsigned long long)OCFS2_I(inode)->ip_blkno, 7095 (unsigned long long)path_leaf_bh(path)->b_blocknr); 7096 status = -EROFS; 7097 goto bail; 7098 } 7099 7100 i = le16_to_cpu(el->l_next_free_rec) - 1; 7101 rec = &el->l_recs[i]; 7102 flags = rec->e_flags; 7103 range = le32_to_cpu(rec->e_cpos) + ocfs2_rec_clusters(el, rec); 7104 7105 if (i == 0 && ocfs2_is_empty_extent(rec)) { 7106 /* 7107 * Lower levels depend on this never happening, but it's best 7108 * to check it up here before changing the tree. 7109 */ 7110 if (root_el->l_tree_depth && rec->e_int_clusters == 0) { 7111 ocfs2_error(inode->i_sb, "Inode %lu has an empty " 7112 "extent record, depth %u\n", inode->i_ino, 7113 le16_to_cpu(root_el->l_tree_depth)); 7114 status = -EROFS; 7115 goto bail; 7116 } 7117 trunc_cpos = le32_to_cpu(rec->e_cpos); 7118 trunc_len = 0; 7119 blkno = 0; 7120 } else if (le32_to_cpu(rec->e_cpos) >= new_highest_cpos) { 7121 /* 7122 * Truncate entire record. 7123 */ 7124 trunc_cpos = le32_to_cpu(rec->e_cpos); 7125 trunc_len = ocfs2_rec_clusters(el, rec); 7126 blkno = le64_to_cpu(rec->e_blkno); 7127 } else if (range > new_highest_cpos) { 7128 /* 7129 * Partial truncate. it also should be 7130 * the last truncate we're doing. 7131 */ 7132 trunc_cpos = new_highest_cpos; 7133 trunc_len = range - new_highest_cpos; 7134 coff = new_highest_cpos - le32_to_cpu(rec->e_cpos); 7135 blkno = le64_to_cpu(rec->e_blkno) + 7136 ocfs2_clusters_to_blocks(inode->i_sb, coff); 7137 } else { 7138 /* 7139 * Truncate completed, leave happily. 7140 */ 7141 status = 0; 7142 goto bail; 7143 } 7144 7145 phys_cpos = ocfs2_blocks_to_clusters(inode->i_sb, blkno); 7146 7147 if ((flags & OCFS2_EXT_REFCOUNTED) && trunc_len && !ref_tree) { 7148 status = ocfs2_lock_refcount_tree(osb, refcount_loc, 1, 7149 &ref_tree, NULL); 7150 if (status) { 7151 mlog_errno(status); 7152 goto bail; 7153 } 7154 } 7155 7156 status = ocfs2_remove_btree_range(inode, &et, trunc_cpos, 7157 phys_cpos, trunc_len, flags, &dealloc, 7158 refcount_loc, true); 7159 if (status < 0) { 7160 mlog_errno(status); 7161 goto bail; 7162 } 7163 7164 ocfs2_reinit_path(path, 1); 7165 7166 /* 7167 * The check above will catch the case where we've truncated 7168 * away all allocation. 7169 */ 7170 goto start; 7171 7172 bail: 7173 if (ref_tree) 7174 ocfs2_unlock_refcount_tree(osb, ref_tree, 1); 7175 7176 ocfs2_schedule_truncate_log_flush(osb, 1); 7177 7178 ocfs2_run_deallocs(osb, &dealloc); 7179 7180 ocfs2_free_path(path); 7181 7182 return status; 7183 } 7184 7185 /* 7186 * 'start' is inclusive, 'end' is not. 7187 */ 7188 int ocfs2_truncate_inline(struct inode *inode, struct buffer_head *di_bh, 7189 unsigned int start, unsigned int end, int trunc) 7190 { 7191 int ret; 7192 unsigned int numbytes; 7193 handle_t *handle; 7194 struct ocfs2_super *osb = OCFS2_SB(inode->i_sb); 7195 struct ocfs2_dinode *di = (struct ocfs2_dinode *)di_bh->b_data; 7196 struct ocfs2_inline_data *idata = &di->id2.i_data; 7197 7198 if (end > i_size_read(inode)) 7199 end = i_size_read(inode); 7200 7201 BUG_ON(start > end); 7202 7203 if (!(OCFS2_I(inode)->ip_dyn_features & OCFS2_INLINE_DATA_FL) || 7204 !(le16_to_cpu(di->i_dyn_features) & OCFS2_INLINE_DATA_FL) || 7205 !ocfs2_supports_inline_data(osb)) { 7206 ocfs2_error(inode->i_sb, 7207 "Inline data flags for inode %llu don't agree! " 7208 "Disk: 0x%x, Memory: 0x%x, Superblock: 0x%x\n", 7209 (unsigned long long)OCFS2_I(inode)->ip_blkno, 7210 le16_to_cpu(di->i_dyn_features), 7211 OCFS2_I(inode)->ip_dyn_features, 7212 osb->s_feature_incompat); 7213 ret = -EROFS; 7214 goto out; 7215 } 7216 7217 handle = ocfs2_start_trans(osb, OCFS2_INODE_UPDATE_CREDITS); 7218 if (IS_ERR(handle)) { 7219 ret = PTR_ERR(handle); 7220 mlog_errno(ret); 7221 goto out; 7222 } 7223 7224 ret = ocfs2_journal_access_di(handle, INODE_CACHE(inode), di_bh, 7225 OCFS2_JOURNAL_ACCESS_WRITE); 7226 if (ret) { 7227 mlog_errno(ret); 7228 goto out_commit; 7229 } 7230 7231 numbytes = end - start; 7232 memset(idata->id_data + start, 0, numbytes); 7233 7234 /* 7235 * No need to worry about the data page here - it's been 7236 * truncated already and inline data doesn't need it for 7237 * pushing zero's to disk, so we'll let readpage pick it up 7238 * later. 7239 */ 7240 if (trunc) { 7241 i_size_write(inode, start); 7242 di->i_size = cpu_to_le64(start); 7243 } 7244 7245 inode->i_blocks = ocfs2_inode_sector_count(inode); 7246 inode->i_ctime = inode->i_mtime = CURRENT_TIME; 7247 7248 di->i_ctime = di->i_mtime = cpu_to_le64(inode->i_ctime.tv_sec); 7249 di->i_ctime_nsec = di->i_mtime_nsec = cpu_to_le32(inode->i_ctime.tv_nsec); 7250 7251 ocfs2_update_inode_fsync_trans(handle, inode, 1); 7252 ocfs2_journal_dirty(handle, di_bh); 7253 7254 out_commit: 7255 ocfs2_commit_trans(osb, handle); 7256 7257 out: 7258 return ret; 7259 } 7260 7261 static int ocfs2_trim_extent(struct super_block *sb, 7262 struct ocfs2_group_desc *gd, 7263 u32 start, u32 count) 7264 { 7265 u64 discard, bcount; 7266 7267 bcount = ocfs2_clusters_to_blocks(sb, count); 7268 discard = le64_to_cpu(gd->bg_blkno) + 7269 ocfs2_clusters_to_blocks(sb, start); 7270 7271 trace_ocfs2_trim_extent(sb, (unsigned long long)discard, bcount); 7272 7273 return sb_issue_discard(sb, discard, bcount, GFP_NOFS, 0); 7274 } 7275 7276 static int ocfs2_trim_group(struct super_block *sb, 7277 struct ocfs2_group_desc *gd, 7278 u32 start, u32 max, u32 minbits) 7279 { 7280 int ret = 0, count = 0, next; 7281 void *bitmap = gd->bg_bitmap; 7282 7283 if (le16_to_cpu(gd->bg_free_bits_count) < minbits) 7284 return 0; 7285 7286 trace_ocfs2_trim_group((unsigned long long)le64_to_cpu(gd->bg_blkno), 7287 start, max, minbits); 7288 7289 while (start < max) { 7290 start = ocfs2_find_next_zero_bit(bitmap, max, start); 7291 if (start >= max) 7292 break; 7293 next = ocfs2_find_next_bit(bitmap, max, start); 7294 7295 if ((next - start) >= minbits) { 7296 ret = ocfs2_trim_extent(sb, gd, 7297 start, next - start); 7298 if (ret < 0) { 7299 mlog_errno(ret); 7300 break; 7301 } 7302 count += next - start; 7303 } 7304 start = next + 1; 7305 7306 if (fatal_signal_pending(current)) { 7307 count = -ERESTARTSYS; 7308 break; 7309 } 7310 7311 if ((le16_to_cpu(gd->bg_free_bits_count) - count) < minbits) 7312 break; 7313 } 7314 7315 if (ret < 0) 7316 count = ret; 7317 7318 return count; 7319 } 7320 7321 int ocfs2_trim_fs(struct super_block *sb, struct fstrim_range *range) 7322 { 7323 struct ocfs2_super *osb = OCFS2_SB(sb); 7324 u64 start, len, trimmed, first_group, last_group, group; 7325 int ret, cnt; 7326 u32 first_bit, last_bit, minlen; 7327 struct buffer_head *main_bm_bh = NULL; 7328 struct inode *main_bm_inode = NULL; 7329 struct buffer_head *gd_bh = NULL; 7330 struct ocfs2_dinode *main_bm; 7331 struct ocfs2_group_desc *gd = NULL; 7332 7333 start = range->start >> osb->s_clustersize_bits; 7334 len = range->len >> osb->s_clustersize_bits; 7335 minlen = range->minlen >> osb->s_clustersize_bits; 7336 7337 if (minlen >= osb->bitmap_cpg || range->len < sb->s_blocksize) 7338 return -EINVAL; 7339 7340 main_bm_inode = ocfs2_get_system_file_inode(osb, 7341 GLOBAL_BITMAP_SYSTEM_INODE, 7342 OCFS2_INVALID_SLOT); 7343 if (!main_bm_inode) { 7344 ret = -EIO; 7345 mlog_errno(ret); 7346 goto out; 7347 } 7348 7349 mutex_lock(&main_bm_inode->i_mutex); 7350 7351 ret = ocfs2_inode_lock(main_bm_inode, &main_bm_bh, 0); 7352 if (ret < 0) { 7353 mlog_errno(ret); 7354 goto out_mutex; 7355 } 7356 main_bm = (struct ocfs2_dinode *)main_bm_bh->b_data; 7357 7358 if (start >= le32_to_cpu(main_bm->i_clusters)) { 7359 ret = -EINVAL; 7360 goto out_unlock; 7361 } 7362 7363 len = range->len >> osb->s_clustersize_bits; 7364 if (start + len > le32_to_cpu(main_bm->i_clusters)) 7365 len = le32_to_cpu(main_bm->i_clusters) - start; 7366 7367 trace_ocfs2_trim_fs(start, len, minlen); 7368 7369 /* Determine first and last group to examine based on start and len */ 7370 first_group = ocfs2_which_cluster_group(main_bm_inode, start); 7371 if (first_group == osb->first_cluster_group_blkno) 7372 first_bit = start; 7373 else 7374 first_bit = start - ocfs2_blocks_to_clusters(sb, first_group); 7375 last_group = ocfs2_which_cluster_group(main_bm_inode, start + len - 1); 7376 last_bit = osb->bitmap_cpg; 7377 7378 trimmed = 0; 7379 for (group = first_group; group <= last_group;) { 7380 if (first_bit + len >= osb->bitmap_cpg) 7381 last_bit = osb->bitmap_cpg; 7382 else 7383 last_bit = first_bit + len; 7384 7385 ret = ocfs2_read_group_descriptor(main_bm_inode, 7386 main_bm, group, 7387 &gd_bh); 7388 if (ret < 0) { 7389 mlog_errno(ret); 7390 break; 7391 } 7392 7393 gd = (struct ocfs2_group_desc *)gd_bh->b_data; 7394 cnt = ocfs2_trim_group(sb, gd, first_bit, last_bit, minlen); 7395 brelse(gd_bh); 7396 gd_bh = NULL; 7397 if (cnt < 0) { 7398 ret = cnt; 7399 mlog_errno(ret); 7400 break; 7401 } 7402 7403 trimmed += cnt; 7404 len -= osb->bitmap_cpg - first_bit; 7405 first_bit = 0; 7406 if (group == osb->first_cluster_group_blkno) 7407 group = ocfs2_clusters_to_blocks(sb, osb->bitmap_cpg); 7408 else 7409 group += ocfs2_clusters_to_blocks(sb, osb->bitmap_cpg); 7410 } 7411 range->len = trimmed * sb->s_blocksize; 7412 out_unlock: 7413 ocfs2_inode_unlock(main_bm_inode, 0); 7414 brelse(main_bm_bh); 7415 out_mutex: 7416 mutex_unlock(&main_bm_inode->i_mutex); 7417 iput(main_bm_inode); 7418 out: 7419 return ret; 7420 } 7421