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