1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2007,2008 Oracle. All rights reserved. 4 */ 5 6 #include <linux/sched.h> 7 #include <linux/slab.h> 8 #include <linux/rbtree.h> 9 #include <linux/mm.h> 10 #include <linux/error-injection.h> 11 #include "messages.h" 12 #include "ctree.h" 13 #include "disk-io.h" 14 #include "transaction.h" 15 #include "print-tree.h" 16 #include "locking.h" 17 #include "volumes.h" 18 #include "qgroup.h" 19 #include "tree-mod-log.h" 20 #include "tree-checker.h" 21 #include "fs.h" 22 #include "accessors.h" 23 #include "extent-tree.h" 24 #include "relocation.h" 25 #include "file-item.h" 26 27 static struct kmem_cache *btrfs_path_cachep; 28 29 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 30 *root, struct btrfs_path *path, int level); 31 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root, 32 const struct btrfs_key *ins_key, struct btrfs_path *path, 33 int data_size, int extend); 34 static int push_node_left(struct btrfs_trans_handle *trans, 35 struct extent_buffer *dst, 36 struct extent_buffer *src, int empty); 37 static int balance_node_right(struct btrfs_trans_handle *trans, 38 struct extent_buffer *dst_buf, 39 struct extent_buffer *src_buf); 40 41 static const struct btrfs_csums { 42 u16 size; 43 const char name[10]; 44 const char driver[12]; 45 } btrfs_csums[] = { 46 [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" }, 47 [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" }, 48 [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" }, 49 [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b", 50 .driver = "blake2b-256" }, 51 }; 52 53 /* 54 * The leaf data grows from end-to-front in the node. this returns the address 55 * of the start of the last item, which is the stop of the leaf data stack. 56 */ 57 static unsigned int leaf_data_end(const struct extent_buffer *leaf) 58 { 59 u32 nr = btrfs_header_nritems(leaf); 60 61 if (nr == 0) 62 return BTRFS_LEAF_DATA_SIZE(leaf->fs_info); 63 return btrfs_item_offset(leaf, nr - 1); 64 } 65 66 /* 67 * Move data in a @leaf (using memmove, safe for overlapping ranges). 68 * 69 * @leaf: leaf that we're doing a memmove on 70 * @dst_offset: item data offset we're moving to 71 * @src_offset: item data offset were' moving from 72 * @len: length of the data we're moving 73 * 74 * Wrapper around memmove_extent_buffer() that takes into account the header on 75 * the leaf. The btrfs_item offset's start directly after the header, so we 76 * have to adjust any offsets to account for the header in the leaf. This 77 * handles that math to simplify the callers. 78 */ 79 static inline void memmove_leaf_data(const struct extent_buffer *leaf, 80 unsigned long dst_offset, 81 unsigned long src_offset, 82 unsigned long len) 83 { 84 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, 0) + dst_offset, 85 btrfs_item_nr_offset(leaf, 0) + src_offset, len); 86 } 87 88 /* 89 * Copy item data from @src into @dst at the given @offset. 90 * 91 * @dst: destination leaf that we're copying into 92 * @src: source leaf that we're copying from 93 * @dst_offset: item data offset we're copying to 94 * @src_offset: item data offset were' copying from 95 * @len: length of the data we're copying 96 * 97 * Wrapper around copy_extent_buffer() that takes into account the header on 98 * the leaf. The btrfs_item offset's start directly after the header, so we 99 * have to adjust any offsets to account for the header in the leaf. This 100 * handles that math to simplify the callers. 101 */ 102 static inline void copy_leaf_data(const struct extent_buffer *dst, 103 const struct extent_buffer *src, 104 unsigned long dst_offset, 105 unsigned long src_offset, unsigned long len) 106 { 107 copy_extent_buffer(dst, src, btrfs_item_nr_offset(dst, 0) + dst_offset, 108 btrfs_item_nr_offset(src, 0) + src_offset, len); 109 } 110 111 /* 112 * Move items in a @leaf (using memmove). 113 * 114 * @dst: destination leaf for the items 115 * @dst_item: the item nr we're copying into 116 * @src_item: the item nr we're copying from 117 * @nr_items: the number of items to copy 118 * 119 * Wrapper around memmove_extent_buffer() that does the math to get the 120 * appropriate offsets into the leaf from the item numbers. 121 */ 122 static inline void memmove_leaf_items(const struct extent_buffer *leaf, 123 int dst_item, int src_item, int nr_items) 124 { 125 memmove_extent_buffer(leaf, btrfs_item_nr_offset(leaf, dst_item), 126 btrfs_item_nr_offset(leaf, src_item), 127 nr_items * sizeof(struct btrfs_item)); 128 } 129 130 /* 131 * Copy items from @src into @dst at the given @offset. 132 * 133 * @dst: destination leaf for the items 134 * @src: source leaf for the items 135 * @dst_item: the item nr we're copying into 136 * @src_item: the item nr we're copying from 137 * @nr_items: the number of items to copy 138 * 139 * Wrapper around copy_extent_buffer() that does the math to get the 140 * appropriate offsets into the leaf from the item numbers. 141 */ 142 static inline void copy_leaf_items(const struct extent_buffer *dst, 143 const struct extent_buffer *src, 144 int dst_item, int src_item, int nr_items) 145 { 146 copy_extent_buffer(dst, src, btrfs_item_nr_offset(dst, dst_item), 147 btrfs_item_nr_offset(src, src_item), 148 nr_items * sizeof(struct btrfs_item)); 149 } 150 151 /* This exists for btrfs-progs usages. */ 152 u16 btrfs_csum_type_size(u16 type) 153 { 154 return btrfs_csums[type].size; 155 } 156 157 int btrfs_super_csum_size(const struct btrfs_super_block *s) 158 { 159 u16 t = btrfs_super_csum_type(s); 160 /* 161 * csum type is validated at mount time 162 */ 163 return btrfs_csum_type_size(t); 164 } 165 166 const char *btrfs_super_csum_name(u16 csum_type) 167 { 168 /* csum type is validated at mount time */ 169 return btrfs_csums[csum_type].name; 170 } 171 172 /* 173 * Return driver name if defined, otherwise the name that's also a valid driver 174 * name 175 */ 176 const char *btrfs_super_csum_driver(u16 csum_type) 177 { 178 /* csum type is validated at mount time */ 179 return btrfs_csums[csum_type].driver[0] ? 180 btrfs_csums[csum_type].driver : 181 btrfs_csums[csum_type].name; 182 } 183 184 size_t __attribute_const__ btrfs_get_num_csums(void) 185 { 186 return ARRAY_SIZE(btrfs_csums); 187 } 188 189 struct btrfs_path *btrfs_alloc_path(void) 190 { 191 might_sleep(); 192 193 return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 194 } 195 196 /* this also releases the path */ 197 void btrfs_free_path(struct btrfs_path *p) 198 { 199 if (!p) 200 return; 201 btrfs_release_path(p); 202 kmem_cache_free(btrfs_path_cachep, p); 203 } 204 205 /* 206 * path release drops references on the extent buffers in the path 207 * and it drops any locks held by this path 208 * 209 * It is safe to call this on paths that no locks or extent buffers held. 210 */ 211 noinline void btrfs_release_path(struct btrfs_path *p) 212 { 213 int i; 214 215 for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 216 p->slots[i] = 0; 217 if (!p->nodes[i]) 218 continue; 219 if (p->locks[i]) { 220 btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]); 221 p->locks[i] = 0; 222 } 223 free_extent_buffer(p->nodes[i]); 224 p->nodes[i] = NULL; 225 } 226 } 227 228 /* 229 * We want the transaction abort to print stack trace only for errors where the 230 * cause could be a bug, eg. due to ENOSPC, and not for common errors that are 231 * caused by external factors. 232 */ 233 bool __cold abort_should_print_stack(int errno) 234 { 235 switch (errno) { 236 case -EIO: 237 case -EROFS: 238 case -ENOMEM: 239 return false; 240 } 241 return true; 242 } 243 244 /* 245 * safely gets a reference on the root node of a tree. A lock 246 * is not taken, so a concurrent writer may put a different node 247 * at the root of the tree. See btrfs_lock_root_node for the 248 * looping required. 249 * 250 * The extent buffer returned by this has a reference taken, so 251 * it won't disappear. It may stop being the root of the tree 252 * at any time because there are no locks held. 253 */ 254 struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 255 { 256 struct extent_buffer *eb; 257 258 while (1) { 259 rcu_read_lock(); 260 eb = rcu_dereference(root->node); 261 262 /* 263 * RCU really hurts here, we could free up the root node because 264 * it was COWed but we may not get the new root node yet so do 265 * the inc_not_zero dance and if it doesn't work then 266 * synchronize_rcu and try again. 267 */ 268 if (atomic_inc_not_zero(&eb->refs)) { 269 rcu_read_unlock(); 270 break; 271 } 272 rcu_read_unlock(); 273 synchronize_rcu(); 274 } 275 return eb; 276 } 277 278 /* 279 * Cowonly root (not-shareable trees, everything not subvolume or reloc roots), 280 * just get put onto a simple dirty list. Transaction walks this list to make 281 * sure they get properly updated on disk. 282 */ 283 static void add_root_to_dirty_list(struct btrfs_root *root) 284 { 285 struct btrfs_fs_info *fs_info = root->fs_info; 286 287 if (test_bit(BTRFS_ROOT_DIRTY, &root->state) || 288 !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state)) 289 return; 290 291 spin_lock(&fs_info->trans_lock); 292 if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) { 293 /* Want the extent tree to be the last on the list */ 294 if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID) 295 list_move_tail(&root->dirty_list, 296 &fs_info->dirty_cowonly_roots); 297 else 298 list_move(&root->dirty_list, 299 &fs_info->dirty_cowonly_roots); 300 } 301 spin_unlock(&fs_info->trans_lock); 302 } 303 304 /* 305 * used by snapshot creation to make a copy of a root for a tree with 306 * a given objectid. The buffer with the new root node is returned in 307 * cow_ret, and this func returns zero on success or a negative error code. 308 */ 309 int btrfs_copy_root(struct btrfs_trans_handle *trans, 310 struct btrfs_root *root, 311 struct extent_buffer *buf, 312 struct extent_buffer **cow_ret, u64 new_root_objectid) 313 { 314 struct btrfs_fs_info *fs_info = root->fs_info; 315 struct extent_buffer *cow; 316 int ret = 0; 317 int level; 318 struct btrfs_disk_key disk_key; 319 320 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 321 trans->transid != fs_info->running_transaction->transid); 322 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 323 trans->transid != root->last_trans); 324 325 level = btrfs_header_level(buf); 326 if (level == 0) 327 btrfs_item_key(buf, &disk_key, 0); 328 else 329 btrfs_node_key(buf, &disk_key, 0); 330 331 cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid, 332 &disk_key, level, buf->start, 0, 333 BTRFS_NESTING_NEW_ROOT); 334 if (IS_ERR(cow)) 335 return PTR_ERR(cow); 336 337 copy_extent_buffer_full(cow, buf); 338 btrfs_set_header_bytenr(cow, cow->start); 339 btrfs_set_header_generation(cow, trans->transid); 340 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 341 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 342 BTRFS_HEADER_FLAG_RELOC); 343 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 344 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 345 else 346 btrfs_set_header_owner(cow, new_root_objectid); 347 348 write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid); 349 350 WARN_ON(btrfs_header_generation(buf) > trans->transid); 351 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 352 ret = btrfs_inc_ref(trans, root, cow, 1); 353 else 354 ret = btrfs_inc_ref(trans, root, cow, 0); 355 if (ret) { 356 btrfs_tree_unlock(cow); 357 free_extent_buffer(cow); 358 btrfs_abort_transaction(trans, ret); 359 return ret; 360 } 361 362 btrfs_mark_buffer_dirty(cow); 363 *cow_ret = cow; 364 return 0; 365 } 366 367 /* 368 * check if the tree block can be shared by multiple trees 369 */ 370 int btrfs_block_can_be_shared(struct btrfs_root *root, 371 struct extent_buffer *buf) 372 { 373 /* 374 * Tree blocks not in shareable trees and tree roots are never shared. 375 * If a block was allocated after the last snapshot and the block was 376 * not allocated by tree relocation, we know the block is not shared. 377 */ 378 if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 379 buf != root->node && buf != root->commit_root && 380 (btrfs_header_generation(buf) <= 381 btrfs_root_last_snapshot(&root->root_item) || 382 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 383 return 1; 384 385 return 0; 386 } 387 388 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans, 389 struct btrfs_root *root, 390 struct extent_buffer *buf, 391 struct extent_buffer *cow, 392 int *last_ref) 393 { 394 struct btrfs_fs_info *fs_info = root->fs_info; 395 u64 refs; 396 u64 owner; 397 u64 flags; 398 u64 new_flags = 0; 399 int ret; 400 401 /* 402 * Backrefs update rules: 403 * 404 * Always use full backrefs for extent pointers in tree block 405 * allocated by tree relocation. 406 * 407 * If a shared tree block is no longer referenced by its owner 408 * tree (btrfs_header_owner(buf) == root->root_key.objectid), 409 * use full backrefs for extent pointers in tree block. 410 * 411 * If a tree block is been relocating 412 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID), 413 * use full backrefs for extent pointers in tree block. 414 * The reason for this is some operations (such as drop tree) 415 * are only allowed for blocks use full backrefs. 416 */ 417 418 if (btrfs_block_can_be_shared(root, buf)) { 419 ret = btrfs_lookup_extent_info(trans, fs_info, buf->start, 420 btrfs_header_level(buf), 1, 421 &refs, &flags); 422 if (ret) 423 return ret; 424 if (refs == 0) { 425 ret = -EROFS; 426 btrfs_handle_fs_error(fs_info, ret, NULL); 427 return ret; 428 } 429 } else { 430 refs = 1; 431 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 432 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 433 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF; 434 else 435 flags = 0; 436 } 437 438 owner = btrfs_header_owner(buf); 439 BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID && 440 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)); 441 442 if (refs > 1) { 443 if ((owner == root->root_key.objectid || 444 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && 445 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 446 ret = btrfs_inc_ref(trans, root, buf, 1); 447 if (ret) 448 return ret; 449 450 if (root->root_key.objectid == 451 BTRFS_TREE_RELOC_OBJECTID) { 452 ret = btrfs_dec_ref(trans, root, buf, 0); 453 if (ret) 454 return ret; 455 ret = btrfs_inc_ref(trans, root, cow, 1); 456 if (ret) 457 return ret; 458 } 459 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; 460 } else { 461 462 if (root->root_key.objectid == 463 BTRFS_TREE_RELOC_OBJECTID) 464 ret = btrfs_inc_ref(trans, root, cow, 1); 465 else 466 ret = btrfs_inc_ref(trans, root, cow, 0); 467 if (ret) 468 return ret; 469 } 470 if (new_flags != 0) { 471 ret = btrfs_set_disk_extent_flags(trans, buf, new_flags); 472 if (ret) 473 return ret; 474 } 475 } else { 476 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { 477 if (root->root_key.objectid == 478 BTRFS_TREE_RELOC_OBJECTID) 479 ret = btrfs_inc_ref(trans, root, cow, 1); 480 else 481 ret = btrfs_inc_ref(trans, root, cow, 0); 482 if (ret) 483 return ret; 484 ret = btrfs_dec_ref(trans, root, buf, 1); 485 if (ret) 486 return ret; 487 } 488 btrfs_clear_buffer_dirty(trans, buf); 489 *last_ref = 1; 490 } 491 return 0; 492 } 493 494 /* 495 * does the dirty work in cow of a single block. The parent block (if 496 * supplied) is updated to point to the new cow copy. The new buffer is marked 497 * dirty and returned locked. If you modify the block it needs to be marked 498 * dirty again. 499 * 500 * search_start -- an allocation hint for the new block 501 * 502 * empty_size -- a hint that you plan on doing more cow. This is the size in 503 * bytes the allocator should try to find free next to the block it returns. 504 * This is just a hint and may be ignored by the allocator. 505 */ 506 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 507 struct btrfs_root *root, 508 struct extent_buffer *buf, 509 struct extent_buffer *parent, int parent_slot, 510 struct extent_buffer **cow_ret, 511 u64 search_start, u64 empty_size, 512 enum btrfs_lock_nesting nest) 513 { 514 struct btrfs_fs_info *fs_info = root->fs_info; 515 struct btrfs_disk_key disk_key; 516 struct extent_buffer *cow; 517 int level, ret; 518 int last_ref = 0; 519 int unlock_orig = 0; 520 u64 parent_start = 0; 521 522 if (*cow_ret == buf) 523 unlock_orig = 1; 524 525 btrfs_assert_tree_write_locked(buf); 526 527 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 528 trans->transid != fs_info->running_transaction->transid); 529 WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 530 trans->transid != root->last_trans); 531 532 level = btrfs_header_level(buf); 533 534 if (level == 0) 535 btrfs_item_key(buf, &disk_key, 0); 536 else 537 btrfs_node_key(buf, &disk_key, 0); 538 539 if ((root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && parent) 540 parent_start = parent->start; 541 542 cow = btrfs_alloc_tree_block(trans, root, parent_start, 543 root->root_key.objectid, &disk_key, level, 544 search_start, empty_size, nest); 545 if (IS_ERR(cow)) 546 return PTR_ERR(cow); 547 548 /* cow is set to blocking by btrfs_init_new_buffer */ 549 550 copy_extent_buffer_full(cow, buf); 551 btrfs_set_header_bytenr(cow, cow->start); 552 btrfs_set_header_generation(cow, trans->transid); 553 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 554 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 555 BTRFS_HEADER_FLAG_RELOC); 556 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 557 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 558 else 559 btrfs_set_header_owner(cow, root->root_key.objectid); 560 561 write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid); 562 563 ret = update_ref_for_cow(trans, root, buf, cow, &last_ref); 564 if (ret) { 565 btrfs_tree_unlock(cow); 566 free_extent_buffer(cow); 567 btrfs_abort_transaction(trans, ret); 568 return ret; 569 } 570 571 if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) { 572 ret = btrfs_reloc_cow_block(trans, root, buf, cow); 573 if (ret) { 574 btrfs_tree_unlock(cow); 575 free_extent_buffer(cow); 576 btrfs_abort_transaction(trans, ret); 577 return ret; 578 } 579 } 580 581 if (buf == root->node) { 582 WARN_ON(parent && parent != buf); 583 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 584 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 585 parent_start = buf->start; 586 587 atomic_inc(&cow->refs); 588 ret = btrfs_tree_mod_log_insert_root(root->node, cow, true); 589 BUG_ON(ret < 0); 590 rcu_assign_pointer(root->node, cow); 591 592 btrfs_free_tree_block(trans, btrfs_root_id(root), buf, 593 parent_start, last_ref); 594 free_extent_buffer(buf); 595 add_root_to_dirty_list(root); 596 } else { 597 WARN_ON(trans->transid != btrfs_header_generation(parent)); 598 btrfs_tree_mod_log_insert_key(parent, parent_slot, 599 BTRFS_MOD_LOG_KEY_REPLACE); 600 btrfs_set_node_blockptr(parent, parent_slot, 601 cow->start); 602 btrfs_set_node_ptr_generation(parent, parent_slot, 603 trans->transid); 604 btrfs_mark_buffer_dirty(parent); 605 if (last_ref) { 606 ret = btrfs_tree_mod_log_free_eb(buf); 607 if (ret) { 608 btrfs_tree_unlock(cow); 609 free_extent_buffer(cow); 610 btrfs_abort_transaction(trans, ret); 611 return ret; 612 } 613 } 614 btrfs_free_tree_block(trans, btrfs_root_id(root), buf, 615 parent_start, last_ref); 616 } 617 if (unlock_orig) 618 btrfs_tree_unlock(buf); 619 free_extent_buffer_stale(buf); 620 btrfs_mark_buffer_dirty(cow); 621 *cow_ret = cow; 622 return 0; 623 } 624 625 static inline int should_cow_block(struct btrfs_trans_handle *trans, 626 struct btrfs_root *root, 627 struct extent_buffer *buf) 628 { 629 if (btrfs_is_testing(root->fs_info)) 630 return 0; 631 632 /* Ensure we can see the FORCE_COW bit */ 633 smp_mb__before_atomic(); 634 635 /* 636 * We do not need to cow a block if 637 * 1) this block is not created or changed in this transaction; 638 * 2) this block does not belong to TREE_RELOC tree; 639 * 3) the root is not forced COW. 640 * 641 * What is forced COW: 642 * when we create snapshot during committing the transaction, 643 * after we've finished copying src root, we must COW the shared 644 * block to ensure the metadata consistency. 645 */ 646 if (btrfs_header_generation(buf) == trans->transid && 647 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) && 648 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID && 649 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) && 650 !test_bit(BTRFS_ROOT_FORCE_COW, &root->state)) 651 return 0; 652 return 1; 653 } 654 655 /* 656 * cows a single block, see __btrfs_cow_block for the real work. 657 * This version of it has extra checks so that a block isn't COWed more than 658 * once per transaction, as long as it hasn't been written yet 659 */ 660 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 661 struct btrfs_root *root, struct extent_buffer *buf, 662 struct extent_buffer *parent, int parent_slot, 663 struct extent_buffer **cow_ret, 664 enum btrfs_lock_nesting nest) 665 { 666 struct btrfs_fs_info *fs_info = root->fs_info; 667 u64 search_start; 668 int ret; 669 670 if (test_bit(BTRFS_ROOT_DELETING, &root->state)) 671 btrfs_err(fs_info, 672 "COW'ing blocks on a fs root that's being dropped"); 673 674 if (trans->transaction != fs_info->running_transaction) 675 WARN(1, KERN_CRIT "trans %llu running %llu\n", 676 trans->transid, 677 fs_info->running_transaction->transid); 678 679 if (trans->transid != fs_info->generation) 680 WARN(1, KERN_CRIT "trans %llu running %llu\n", 681 trans->transid, fs_info->generation); 682 683 if (!should_cow_block(trans, root, buf)) { 684 *cow_ret = buf; 685 return 0; 686 } 687 688 search_start = buf->start & ~((u64)SZ_1G - 1); 689 690 /* 691 * Before CoWing this block for later modification, check if it's 692 * the subtree root and do the delayed subtree trace if needed. 693 * 694 * Also We don't care about the error, as it's handled internally. 695 */ 696 btrfs_qgroup_trace_subtree_after_cow(trans, root, buf); 697 ret = __btrfs_cow_block(trans, root, buf, parent, 698 parent_slot, cow_ret, search_start, 0, nest); 699 700 trace_btrfs_cow_block(root, buf, *cow_ret); 701 702 return ret; 703 } 704 ALLOW_ERROR_INJECTION(btrfs_cow_block, ERRNO); 705 706 /* 707 * helper function for defrag to decide if two blocks pointed to by a 708 * node are actually close by 709 */ 710 static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 711 { 712 if (blocknr < other && other - (blocknr + blocksize) < 32768) 713 return 1; 714 if (blocknr > other && blocknr - (other + blocksize) < 32768) 715 return 1; 716 return 0; 717 } 718 719 #ifdef __LITTLE_ENDIAN 720 721 /* 722 * Compare two keys, on little-endian the disk order is same as CPU order and 723 * we can avoid the conversion. 724 */ 725 static int comp_keys(const struct btrfs_disk_key *disk_key, 726 const struct btrfs_key *k2) 727 { 728 const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key; 729 730 return btrfs_comp_cpu_keys(k1, k2); 731 } 732 733 #else 734 735 /* 736 * compare two keys in a memcmp fashion 737 */ 738 static int comp_keys(const struct btrfs_disk_key *disk, 739 const struct btrfs_key *k2) 740 { 741 struct btrfs_key k1; 742 743 btrfs_disk_key_to_cpu(&k1, disk); 744 745 return btrfs_comp_cpu_keys(&k1, k2); 746 } 747 #endif 748 749 /* 750 * same as comp_keys only with two btrfs_key's 751 */ 752 int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2) 753 { 754 if (k1->objectid > k2->objectid) 755 return 1; 756 if (k1->objectid < k2->objectid) 757 return -1; 758 if (k1->type > k2->type) 759 return 1; 760 if (k1->type < k2->type) 761 return -1; 762 if (k1->offset > k2->offset) 763 return 1; 764 if (k1->offset < k2->offset) 765 return -1; 766 return 0; 767 } 768 769 /* 770 * this is used by the defrag code to go through all the 771 * leaves pointed to by a node and reallocate them so that 772 * disk order is close to key order 773 */ 774 int btrfs_realloc_node(struct btrfs_trans_handle *trans, 775 struct btrfs_root *root, struct extent_buffer *parent, 776 int start_slot, u64 *last_ret, 777 struct btrfs_key *progress) 778 { 779 struct btrfs_fs_info *fs_info = root->fs_info; 780 struct extent_buffer *cur; 781 u64 blocknr; 782 u64 search_start = *last_ret; 783 u64 last_block = 0; 784 u64 other; 785 u32 parent_nritems; 786 int end_slot; 787 int i; 788 int err = 0; 789 u32 blocksize; 790 int progress_passed = 0; 791 struct btrfs_disk_key disk_key; 792 793 WARN_ON(trans->transaction != fs_info->running_transaction); 794 WARN_ON(trans->transid != fs_info->generation); 795 796 parent_nritems = btrfs_header_nritems(parent); 797 blocksize = fs_info->nodesize; 798 end_slot = parent_nritems - 1; 799 800 if (parent_nritems <= 1) 801 return 0; 802 803 for (i = start_slot; i <= end_slot; i++) { 804 int close = 1; 805 806 btrfs_node_key(parent, &disk_key, i); 807 if (!progress_passed && comp_keys(&disk_key, progress) < 0) 808 continue; 809 810 progress_passed = 1; 811 blocknr = btrfs_node_blockptr(parent, i); 812 if (last_block == 0) 813 last_block = blocknr; 814 815 if (i > 0) { 816 other = btrfs_node_blockptr(parent, i - 1); 817 close = close_blocks(blocknr, other, blocksize); 818 } 819 if (!close && i < end_slot) { 820 other = btrfs_node_blockptr(parent, i + 1); 821 close = close_blocks(blocknr, other, blocksize); 822 } 823 if (close) { 824 last_block = blocknr; 825 continue; 826 } 827 828 cur = btrfs_read_node_slot(parent, i); 829 if (IS_ERR(cur)) 830 return PTR_ERR(cur); 831 if (search_start == 0) 832 search_start = last_block; 833 834 btrfs_tree_lock(cur); 835 err = __btrfs_cow_block(trans, root, cur, parent, i, 836 &cur, search_start, 837 min(16 * blocksize, 838 (end_slot - i) * blocksize), 839 BTRFS_NESTING_COW); 840 if (err) { 841 btrfs_tree_unlock(cur); 842 free_extent_buffer(cur); 843 break; 844 } 845 search_start = cur->start; 846 last_block = cur->start; 847 *last_ret = search_start; 848 btrfs_tree_unlock(cur); 849 free_extent_buffer(cur); 850 } 851 return err; 852 } 853 854 /* 855 * Search for a key in the given extent_buffer. 856 * 857 * The lower boundary for the search is specified by the slot number @first_slot. 858 * Use a value of 0 to search over the whole extent buffer. Works for both 859 * leaves and nodes. 860 * 861 * The slot in the extent buffer is returned via @slot. If the key exists in the 862 * extent buffer, then @slot will point to the slot where the key is, otherwise 863 * it points to the slot where you would insert the key. 864 * 865 * Slot may point to the total number of items (i.e. one position beyond the last 866 * key) if the key is bigger than the last key in the extent buffer. 867 */ 868 int btrfs_bin_search(struct extent_buffer *eb, int first_slot, 869 const struct btrfs_key *key, int *slot) 870 { 871 unsigned long p; 872 int item_size; 873 /* 874 * Use unsigned types for the low and high slots, so that we get a more 875 * efficient division in the search loop below. 876 */ 877 u32 low = first_slot; 878 u32 high = btrfs_header_nritems(eb); 879 int ret; 880 const int key_size = sizeof(struct btrfs_disk_key); 881 882 if (unlikely(low > high)) { 883 btrfs_err(eb->fs_info, 884 "%s: low (%u) > high (%u) eb %llu owner %llu level %d", 885 __func__, low, high, eb->start, 886 btrfs_header_owner(eb), btrfs_header_level(eb)); 887 return -EINVAL; 888 } 889 890 if (btrfs_header_level(eb) == 0) { 891 p = offsetof(struct btrfs_leaf, items); 892 item_size = sizeof(struct btrfs_item); 893 } else { 894 p = offsetof(struct btrfs_node, ptrs); 895 item_size = sizeof(struct btrfs_key_ptr); 896 } 897 898 while (low < high) { 899 unsigned long oip; 900 unsigned long offset; 901 struct btrfs_disk_key *tmp; 902 struct btrfs_disk_key unaligned; 903 int mid; 904 905 mid = (low + high) / 2; 906 offset = p + mid * item_size; 907 oip = offset_in_page(offset); 908 909 if (oip + key_size <= PAGE_SIZE) { 910 const unsigned long idx = get_eb_page_index(offset); 911 char *kaddr = page_address(eb->pages[idx]); 912 913 oip = get_eb_offset_in_page(eb, offset); 914 tmp = (struct btrfs_disk_key *)(kaddr + oip); 915 } else { 916 read_extent_buffer(eb, &unaligned, offset, key_size); 917 tmp = &unaligned; 918 } 919 920 ret = comp_keys(tmp, key); 921 922 if (ret < 0) 923 low = mid + 1; 924 else if (ret > 0) 925 high = mid; 926 else { 927 *slot = mid; 928 return 0; 929 } 930 } 931 *slot = low; 932 return 1; 933 } 934 935 static void root_add_used(struct btrfs_root *root, u32 size) 936 { 937 spin_lock(&root->accounting_lock); 938 btrfs_set_root_used(&root->root_item, 939 btrfs_root_used(&root->root_item) + size); 940 spin_unlock(&root->accounting_lock); 941 } 942 943 static void root_sub_used(struct btrfs_root *root, u32 size) 944 { 945 spin_lock(&root->accounting_lock); 946 btrfs_set_root_used(&root->root_item, 947 btrfs_root_used(&root->root_item) - size); 948 spin_unlock(&root->accounting_lock); 949 } 950 951 /* given a node and slot number, this reads the blocks it points to. The 952 * extent buffer is returned with a reference taken (but unlocked). 953 */ 954 struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent, 955 int slot) 956 { 957 int level = btrfs_header_level(parent); 958 struct btrfs_tree_parent_check check = { 0 }; 959 struct extent_buffer *eb; 960 961 if (slot < 0 || slot >= btrfs_header_nritems(parent)) 962 return ERR_PTR(-ENOENT); 963 964 ASSERT(level); 965 966 check.level = level - 1; 967 check.transid = btrfs_node_ptr_generation(parent, slot); 968 check.owner_root = btrfs_header_owner(parent); 969 check.has_first_key = true; 970 btrfs_node_key_to_cpu(parent, &check.first_key, slot); 971 972 eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot), 973 &check); 974 if (IS_ERR(eb)) 975 return eb; 976 if (!extent_buffer_uptodate(eb)) { 977 free_extent_buffer(eb); 978 return ERR_PTR(-EIO); 979 } 980 981 return eb; 982 } 983 984 /* 985 * node level balancing, used to make sure nodes are in proper order for 986 * item deletion. We balance from the top down, so we have to make sure 987 * that a deletion won't leave an node completely empty later on. 988 */ 989 static noinline int balance_level(struct btrfs_trans_handle *trans, 990 struct btrfs_root *root, 991 struct btrfs_path *path, int level) 992 { 993 struct btrfs_fs_info *fs_info = root->fs_info; 994 struct extent_buffer *right = NULL; 995 struct extent_buffer *mid; 996 struct extent_buffer *left = NULL; 997 struct extent_buffer *parent = NULL; 998 int ret = 0; 999 int wret; 1000 int pslot; 1001 int orig_slot = path->slots[level]; 1002 u64 orig_ptr; 1003 1004 ASSERT(level > 0); 1005 1006 mid = path->nodes[level]; 1007 1008 WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK); 1009 WARN_ON(btrfs_header_generation(mid) != trans->transid); 1010 1011 orig_ptr = btrfs_node_blockptr(mid, orig_slot); 1012 1013 if (level < BTRFS_MAX_LEVEL - 1) { 1014 parent = path->nodes[level + 1]; 1015 pslot = path->slots[level + 1]; 1016 } 1017 1018 /* 1019 * deal with the case where there is only one pointer in the root 1020 * by promoting the node below to a root 1021 */ 1022 if (!parent) { 1023 struct extent_buffer *child; 1024 1025 if (btrfs_header_nritems(mid) != 1) 1026 return 0; 1027 1028 /* promote the child to a root */ 1029 child = btrfs_read_node_slot(mid, 0); 1030 if (IS_ERR(child)) { 1031 ret = PTR_ERR(child); 1032 btrfs_handle_fs_error(fs_info, ret, NULL); 1033 goto enospc; 1034 } 1035 1036 btrfs_tree_lock(child); 1037 ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 1038 BTRFS_NESTING_COW); 1039 if (ret) { 1040 btrfs_tree_unlock(child); 1041 free_extent_buffer(child); 1042 goto enospc; 1043 } 1044 1045 ret = btrfs_tree_mod_log_insert_root(root->node, child, true); 1046 BUG_ON(ret < 0); 1047 rcu_assign_pointer(root->node, child); 1048 1049 add_root_to_dirty_list(root); 1050 btrfs_tree_unlock(child); 1051 1052 path->locks[level] = 0; 1053 path->nodes[level] = NULL; 1054 btrfs_clear_buffer_dirty(trans, mid); 1055 btrfs_tree_unlock(mid); 1056 /* once for the path */ 1057 free_extent_buffer(mid); 1058 1059 root_sub_used(root, mid->len); 1060 btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1); 1061 /* once for the root ptr */ 1062 free_extent_buffer_stale(mid); 1063 return 0; 1064 } 1065 if (btrfs_header_nritems(mid) > 1066 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4) 1067 return 0; 1068 1069 if (pslot) { 1070 left = btrfs_read_node_slot(parent, pslot - 1); 1071 if (IS_ERR(left)) { 1072 ret = PTR_ERR(left); 1073 left = NULL; 1074 goto enospc; 1075 } 1076 1077 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 1078 wret = btrfs_cow_block(trans, root, left, 1079 parent, pslot - 1, &left, 1080 BTRFS_NESTING_LEFT_COW); 1081 if (wret) { 1082 ret = wret; 1083 goto enospc; 1084 } 1085 } 1086 1087 if (pslot + 1 < btrfs_header_nritems(parent)) { 1088 right = btrfs_read_node_slot(parent, pslot + 1); 1089 if (IS_ERR(right)) { 1090 ret = PTR_ERR(right); 1091 right = NULL; 1092 goto enospc; 1093 } 1094 1095 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 1096 wret = btrfs_cow_block(trans, root, right, 1097 parent, pslot + 1, &right, 1098 BTRFS_NESTING_RIGHT_COW); 1099 if (wret) { 1100 ret = wret; 1101 goto enospc; 1102 } 1103 } 1104 1105 /* first, try to make some room in the middle buffer */ 1106 if (left) { 1107 orig_slot += btrfs_header_nritems(left); 1108 wret = push_node_left(trans, left, mid, 1); 1109 if (wret < 0) 1110 ret = wret; 1111 } 1112 1113 /* 1114 * then try to empty the right most buffer into the middle 1115 */ 1116 if (right) { 1117 wret = push_node_left(trans, mid, right, 1); 1118 if (wret < 0 && wret != -ENOSPC) 1119 ret = wret; 1120 if (btrfs_header_nritems(right) == 0) { 1121 btrfs_clear_buffer_dirty(trans, right); 1122 btrfs_tree_unlock(right); 1123 btrfs_del_ptr(root, path, level + 1, pslot + 1); 1124 root_sub_used(root, right->len); 1125 btrfs_free_tree_block(trans, btrfs_root_id(root), right, 1126 0, 1); 1127 free_extent_buffer_stale(right); 1128 right = NULL; 1129 } else { 1130 struct btrfs_disk_key right_key; 1131 btrfs_node_key(right, &right_key, 0); 1132 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1, 1133 BTRFS_MOD_LOG_KEY_REPLACE); 1134 BUG_ON(ret < 0); 1135 btrfs_set_node_key(parent, &right_key, pslot + 1); 1136 btrfs_mark_buffer_dirty(parent); 1137 } 1138 } 1139 if (btrfs_header_nritems(mid) == 1) { 1140 /* 1141 * we're not allowed to leave a node with one item in the 1142 * tree during a delete. A deletion from lower in the tree 1143 * could try to delete the only pointer in this node. 1144 * So, pull some keys from the left. 1145 * There has to be a left pointer at this point because 1146 * otherwise we would have pulled some pointers from the 1147 * right 1148 */ 1149 if (!left) { 1150 ret = -EROFS; 1151 btrfs_handle_fs_error(fs_info, ret, NULL); 1152 goto enospc; 1153 } 1154 wret = balance_node_right(trans, mid, left); 1155 if (wret < 0) { 1156 ret = wret; 1157 goto enospc; 1158 } 1159 if (wret == 1) { 1160 wret = push_node_left(trans, left, mid, 1); 1161 if (wret < 0) 1162 ret = wret; 1163 } 1164 BUG_ON(wret == 1); 1165 } 1166 if (btrfs_header_nritems(mid) == 0) { 1167 btrfs_clear_buffer_dirty(trans, mid); 1168 btrfs_tree_unlock(mid); 1169 btrfs_del_ptr(root, path, level + 1, pslot); 1170 root_sub_used(root, mid->len); 1171 btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1); 1172 free_extent_buffer_stale(mid); 1173 mid = NULL; 1174 } else { 1175 /* update the parent key to reflect our changes */ 1176 struct btrfs_disk_key mid_key; 1177 btrfs_node_key(mid, &mid_key, 0); 1178 ret = btrfs_tree_mod_log_insert_key(parent, pslot, 1179 BTRFS_MOD_LOG_KEY_REPLACE); 1180 BUG_ON(ret < 0); 1181 btrfs_set_node_key(parent, &mid_key, pslot); 1182 btrfs_mark_buffer_dirty(parent); 1183 } 1184 1185 /* update the path */ 1186 if (left) { 1187 if (btrfs_header_nritems(left) > orig_slot) { 1188 atomic_inc(&left->refs); 1189 /* left was locked after cow */ 1190 path->nodes[level] = left; 1191 path->slots[level + 1] -= 1; 1192 path->slots[level] = orig_slot; 1193 if (mid) { 1194 btrfs_tree_unlock(mid); 1195 free_extent_buffer(mid); 1196 } 1197 } else { 1198 orig_slot -= btrfs_header_nritems(left); 1199 path->slots[level] = orig_slot; 1200 } 1201 } 1202 /* double check we haven't messed things up */ 1203 if (orig_ptr != 1204 btrfs_node_blockptr(path->nodes[level], path->slots[level])) 1205 BUG(); 1206 enospc: 1207 if (right) { 1208 btrfs_tree_unlock(right); 1209 free_extent_buffer(right); 1210 } 1211 if (left) { 1212 if (path->nodes[level] != left) 1213 btrfs_tree_unlock(left); 1214 free_extent_buffer(left); 1215 } 1216 return ret; 1217 } 1218 1219 /* Node balancing for insertion. Here we only split or push nodes around 1220 * when they are completely full. This is also done top down, so we 1221 * have to be pessimistic. 1222 */ 1223 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1224 struct btrfs_root *root, 1225 struct btrfs_path *path, int level) 1226 { 1227 struct btrfs_fs_info *fs_info = root->fs_info; 1228 struct extent_buffer *right = NULL; 1229 struct extent_buffer *mid; 1230 struct extent_buffer *left = NULL; 1231 struct extent_buffer *parent = NULL; 1232 int ret = 0; 1233 int wret; 1234 int pslot; 1235 int orig_slot = path->slots[level]; 1236 1237 if (level == 0) 1238 return 1; 1239 1240 mid = path->nodes[level]; 1241 WARN_ON(btrfs_header_generation(mid) != trans->transid); 1242 1243 if (level < BTRFS_MAX_LEVEL - 1) { 1244 parent = path->nodes[level + 1]; 1245 pslot = path->slots[level + 1]; 1246 } 1247 1248 if (!parent) 1249 return 1; 1250 1251 /* first, try to make some room in the middle buffer */ 1252 if (pslot) { 1253 u32 left_nr; 1254 1255 left = btrfs_read_node_slot(parent, pslot - 1); 1256 if (IS_ERR(left)) 1257 return PTR_ERR(left); 1258 1259 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 1260 1261 left_nr = btrfs_header_nritems(left); 1262 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { 1263 wret = 1; 1264 } else { 1265 ret = btrfs_cow_block(trans, root, left, parent, 1266 pslot - 1, &left, 1267 BTRFS_NESTING_LEFT_COW); 1268 if (ret) 1269 wret = 1; 1270 else { 1271 wret = push_node_left(trans, left, mid, 0); 1272 } 1273 } 1274 if (wret < 0) 1275 ret = wret; 1276 if (wret == 0) { 1277 struct btrfs_disk_key disk_key; 1278 orig_slot += left_nr; 1279 btrfs_node_key(mid, &disk_key, 0); 1280 ret = btrfs_tree_mod_log_insert_key(parent, pslot, 1281 BTRFS_MOD_LOG_KEY_REPLACE); 1282 BUG_ON(ret < 0); 1283 btrfs_set_node_key(parent, &disk_key, pslot); 1284 btrfs_mark_buffer_dirty(parent); 1285 if (btrfs_header_nritems(left) > orig_slot) { 1286 path->nodes[level] = left; 1287 path->slots[level + 1] -= 1; 1288 path->slots[level] = orig_slot; 1289 btrfs_tree_unlock(mid); 1290 free_extent_buffer(mid); 1291 } else { 1292 orig_slot -= 1293 btrfs_header_nritems(left); 1294 path->slots[level] = orig_slot; 1295 btrfs_tree_unlock(left); 1296 free_extent_buffer(left); 1297 } 1298 return 0; 1299 } 1300 btrfs_tree_unlock(left); 1301 free_extent_buffer(left); 1302 } 1303 1304 /* 1305 * then try to empty the right most buffer into the middle 1306 */ 1307 if (pslot + 1 < btrfs_header_nritems(parent)) { 1308 u32 right_nr; 1309 1310 right = btrfs_read_node_slot(parent, pslot + 1); 1311 if (IS_ERR(right)) 1312 return PTR_ERR(right); 1313 1314 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 1315 1316 right_nr = btrfs_header_nritems(right); 1317 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { 1318 wret = 1; 1319 } else { 1320 ret = btrfs_cow_block(trans, root, right, 1321 parent, pslot + 1, 1322 &right, BTRFS_NESTING_RIGHT_COW); 1323 if (ret) 1324 wret = 1; 1325 else { 1326 wret = balance_node_right(trans, right, mid); 1327 } 1328 } 1329 if (wret < 0) 1330 ret = wret; 1331 if (wret == 0) { 1332 struct btrfs_disk_key disk_key; 1333 1334 btrfs_node_key(right, &disk_key, 0); 1335 ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1, 1336 BTRFS_MOD_LOG_KEY_REPLACE); 1337 BUG_ON(ret < 0); 1338 btrfs_set_node_key(parent, &disk_key, pslot + 1); 1339 btrfs_mark_buffer_dirty(parent); 1340 1341 if (btrfs_header_nritems(mid) <= orig_slot) { 1342 path->nodes[level] = right; 1343 path->slots[level + 1] += 1; 1344 path->slots[level] = orig_slot - 1345 btrfs_header_nritems(mid); 1346 btrfs_tree_unlock(mid); 1347 free_extent_buffer(mid); 1348 } else { 1349 btrfs_tree_unlock(right); 1350 free_extent_buffer(right); 1351 } 1352 return 0; 1353 } 1354 btrfs_tree_unlock(right); 1355 free_extent_buffer(right); 1356 } 1357 return 1; 1358 } 1359 1360 /* 1361 * readahead one full node of leaves, finding things that are close 1362 * to the block in 'slot', and triggering ra on them. 1363 */ 1364 static void reada_for_search(struct btrfs_fs_info *fs_info, 1365 struct btrfs_path *path, 1366 int level, int slot, u64 objectid) 1367 { 1368 struct extent_buffer *node; 1369 struct btrfs_disk_key disk_key; 1370 u32 nritems; 1371 u64 search; 1372 u64 target; 1373 u64 nread = 0; 1374 u64 nread_max; 1375 u32 nr; 1376 u32 blocksize; 1377 u32 nscan = 0; 1378 1379 if (level != 1 && path->reada != READA_FORWARD_ALWAYS) 1380 return; 1381 1382 if (!path->nodes[level]) 1383 return; 1384 1385 node = path->nodes[level]; 1386 1387 /* 1388 * Since the time between visiting leaves is much shorter than the time 1389 * between visiting nodes, limit read ahead of nodes to 1, to avoid too 1390 * much IO at once (possibly random). 1391 */ 1392 if (path->reada == READA_FORWARD_ALWAYS) { 1393 if (level > 1) 1394 nread_max = node->fs_info->nodesize; 1395 else 1396 nread_max = SZ_128K; 1397 } else { 1398 nread_max = SZ_64K; 1399 } 1400 1401 search = btrfs_node_blockptr(node, slot); 1402 blocksize = fs_info->nodesize; 1403 if (path->reada != READA_FORWARD_ALWAYS) { 1404 struct extent_buffer *eb; 1405 1406 eb = find_extent_buffer(fs_info, search); 1407 if (eb) { 1408 free_extent_buffer(eb); 1409 return; 1410 } 1411 } 1412 1413 target = search; 1414 1415 nritems = btrfs_header_nritems(node); 1416 nr = slot; 1417 1418 while (1) { 1419 if (path->reada == READA_BACK) { 1420 if (nr == 0) 1421 break; 1422 nr--; 1423 } else if (path->reada == READA_FORWARD || 1424 path->reada == READA_FORWARD_ALWAYS) { 1425 nr++; 1426 if (nr >= nritems) 1427 break; 1428 } 1429 if (path->reada == READA_BACK && objectid) { 1430 btrfs_node_key(node, &disk_key, nr); 1431 if (btrfs_disk_key_objectid(&disk_key) != objectid) 1432 break; 1433 } 1434 search = btrfs_node_blockptr(node, nr); 1435 if (path->reada == READA_FORWARD_ALWAYS || 1436 (search <= target && target - search <= 65536) || 1437 (search > target && search - target <= 65536)) { 1438 btrfs_readahead_node_child(node, nr); 1439 nread += blocksize; 1440 } 1441 nscan++; 1442 if (nread > nread_max || nscan > 32) 1443 break; 1444 } 1445 } 1446 1447 static noinline void reada_for_balance(struct btrfs_path *path, int level) 1448 { 1449 struct extent_buffer *parent; 1450 int slot; 1451 int nritems; 1452 1453 parent = path->nodes[level + 1]; 1454 if (!parent) 1455 return; 1456 1457 nritems = btrfs_header_nritems(parent); 1458 slot = path->slots[level + 1]; 1459 1460 if (slot > 0) 1461 btrfs_readahead_node_child(parent, slot - 1); 1462 if (slot + 1 < nritems) 1463 btrfs_readahead_node_child(parent, slot + 1); 1464 } 1465 1466 1467 /* 1468 * when we walk down the tree, it is usually safe to unlock the higher layers 1469 * in the tree. The exceptions are when our path goes through slot 0, because 1470 * operations on the tree might require changing key pointers higher up in the 1471 * tree. 1472 * 1473 * callers might also have set path->keep_locks, which tells this code to keep 1474 * the lock if the path points to the last slot in the block. This is part of 1475 * walking through the tree, and selecting the next slot in the higher block. 1476 * 1477 * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1478 * if lowest_unlock is 1, level 0 won't be unlocked 1479 */ 1480 static noinline void unlock_up(struct btrfs_path *path, int level, 1481 int lowest_unlock, int min_write_lock_level, 1482 int *write_lock_level) 1483 { 1484 int i; 1485 int skip_level = level; 1486 bool check_skip = true; 1487 1488 for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1489 if (!path->nodes[i]) 1490 break; 1491 if (!path->locks[i]) 1492 break; 1493 1494 if (check_skip) { 1495 if (path->slots[i] == 0) { 1496 skip_level = i + 1; 1497 continue; 1498 } 1499 1500 if (path->keep_locks) { 1501 u32 nritems; 1502 1503 nritems = btrfs_header_nritems(path->nodes[i]); 1504 if (nritems < 1 || path->slots[i] >= nritems - 1) { 1505 skip_level = i + 1; 1506 continue; 1507 } 1508 } 1509 } 1510 1511 if (i >= lowest_unlock && i > skip_level) { 1512 check_skip = false; 1513 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]); 1514 path->locks[i] = 0; 1515 if (write_lock_level && 1516 i > min_write_lock_level && 1517 i <= *write_lock_level) { 1518 *write_lock_level = i - 1; 1519 } 1520 } 1521 } 1522 } 1523 1524 /* 1525 * Helper function for btrfs_search_slot() and other functions that do a search 1526 * on a btree. The goal is to find a tree block in the cache (the radix tree at 1527 * fs_info->buffer_radix), but if we can't find it, or it's not up to date, read 1528 * its pages from disk. 1529 * 1530 * Returns -EAGAIN, with the path unlocked, if the caller needs to repeat the 1531 * whole btree search, starting again from the current root node. 1532 */ 1533 static int 1534 read_block_for_search(struct btrfs_root *root, struct btrfs_path *p, 1535 struct extent_buffer **eb_ret, int level, int slot, 1536 const struct btrfs_key *key) 1537 { 1538 struct btrfs_fs_info *fs_info = root->fs_info; 1539 struct btrfs_tree_parent_check check = { 0 }; 1540 u64 blocknr; 1541 u64 gen; 1542 struct extent_buffer *tmp; 1543 int ret; 1544 int parent_level; 1545 bool unlock_up; 1546 1547 unlock_up = ((level + 1 < BTRFS_MAX_LEVEL) && p->locks[level + 1]); 1548 blocknr = btrfs_node_blockptr(*eb_ret, slot); 1549 gen = btrfs_node_ptr_generation(*eb_ret, slot); 1550 parent_level = btrfs_header_level(*eb_ret); 1551 btrfs_node_key_to_cpu(*eb_ret, &check.first_key, slot); 1552 check.has_first_key = true; 1553 check.level = parent_level - 1; 1554 check.transid = gen; 1555 check.owner_root = root->root_key.objectid; 1556 1557 /* 1558 * If we need to read an extent buffer from disk and we are holding locks 1559 * on upper level nodes, we unlock all the upper nodes before reading the 1560 * extent buffer, and then return -EAGAIN to the caller as it needs to 1561 * restart the search. We don't release the lock on the current level 1562 * because we need to walk this node to figure out which blocks to read. 1563 */ 1564 tmp = find_extent_buffer(fs_info, blocknr); 1565 if (tmp) { 1566 if (p->reada == READA_FORWARD_ALWAYS) 1567 reada_for_search(fs_info, p, level, slot, key->objectid); 1568 1569 /* first we do an atomic uptodate check */ 1570 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) { 1571 /* 1572 * Do extra check for first_key, eb can be stale due to 1573 * being cached, read from scrub, or have multiple 1574 * parents (shared tree blocks). 1575 */ 1576 if (btrfs_verify_level_key(tmp, 1577 parent_level - 1, &check.first_key, gen)) { 1578 free_extent_buffer(tmp); 1579 return -EUCLEAN; 1580 } 1581 *eb_ret = tmp; 1582 return 0; 1583 } 1584 1585 if (p->nowait) { 1586 free_extent_buffer(tmp); 1587 return -EAGAIN; 1588 } 1589 1590 if (unlock_up) 1591 btrfs_unlock_up_safe(p, level + 1); 1592 1593 /* now we're allowed to do a blocking uptodate check */ 1594 ret = btrfs_read_extent_buffer(tmp, &check); 1595 if (ret) { 1596 free_extent_buffer(tmp); 1597 btrfs_release_path(p); 1598 return -EIO; 1599 } 1600 if (btrfs_check_eb_owner(tmp, root->root_key.objectid)) { 1601 free_extent_buffer(tmp); 1602 btrfs_release_path(p); 1603 return -EUCLEAN; 1604 } 1605 1606 if (unlock_up) 1607 ret = -EAGAIN; 1608 1609 goto out; 1610 } else if (p->nowait) { 1611 return -EAGAIN; 1612 } 1613 1614 if (unlock_up) { 1615 btrfs_unlock_up_safe(p, level + 1); 1616 ret = -EAGAIN; 1617 } else { 1618 ret = 0; 1619 } 1620 1621 if (p->reada != READA_NONE) 1622 reada_for_search(fs_info, p, level, slot, key->objectid); 1623 1624 tmp = read_tree_block(fs_info, blocknr, &check); 1625 if (IS_ERR(tmp)) { 1626 btrfs_release_path(p); 1627 return PTR_ERR(tmp); 1628 } 1629 /* 1630 * If the read above didn't mark this buffer up to date, 1631 * it will never end up being up to date. Set ret to EIO now 1632 * and give up so that our caller doesn't loop forever 1633 * on our EAGAINs. 1634 */ 1635 if (!extent_buffer_uptodate(tmp)) 1636 ret = -EIO; 1637 1638 out: 1639 if (ret == 0) { 1640 *eb_ret = tmp; 1641 } else { 1642 free_extent_buffer(tmp); 1643 btrfs_release_path(p); 1644 } 1645 1646 return ret; 1647 } 1648 1649 /* 1650 * helper function for btrfs_search_slot. This does all of the checks 1651 * for node-level blocks and does any balancing required based on 1652 * the ins_len. 1653 * 1654 * If no extra work was required, zero is returned. If we had to 1655 * drop the path, -EAGAIN is returned and btrfs_search_slot must 1656 * start over 1657 */ 1658 static int 1659 setup_nodes_for_search(struct btrfs_trans_handle *trans, 1660 struct btrfs_root *root, struct btrfs_path *p, 1661 struct extent_buffer *b, int level, int ins_len, 1662 int *write_lock_level) 1663 { 1664 struct btrfs_fs_info *fs_info = root->fs_info; 1665 int ret = 0; 1666 1667 if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= 1668 BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) { 1669 1670 if (*write_lock_level < level + 1) { 1671 *write_lock_level = level + 1; 1672 btrfs_release_path(p); 1673 return -EAGAIN; 1674 } 1675 1676 reada_for_balance(p, level); 1677 ret = split_node(trans, root, p, level); 1678 1679 b = p->nodes[level]; 1680 } else if (ins_len < 0 && btrfs_header_nritems(b) < 1681 BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) { 1682 1683 if (*write_lock_level < level + 1) { 1684 *write_lock_level = level + 1; 1685 btrfs_release_path(p); 1686 return -EAGAIN; 1687 } 1688 1689 reada_for_balance(p, level); 1690 ret = balance_level(trans, root, p, level); 1691 if (ret) 1692 return ret; 1693 1694 b = p->nodes[level]; 1695 if (!b) { 1696 btrfs_release_path(p); 1697 return -EAGAIN; 1698 } 1699 BUG_ON(btrfs_header_nritems(b) == 1); 1700 } 1701 return ret; 1702 } 1703 1704 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path, 1705 u64 iobjectid, u64 ioff, u8 key_type, 1706 struct btrfs_key *found_key) 1707 { 1708 int ret; 1709 struct btrfs_key key; 1710 struct extent_buffer *eb; 1711 1712 ASSERT(path); 1713 ASSERT(found_key); 1714 1715 key.type = key_type; 1716 key.objectid = iobjectid; 1717 key.offset = ioff; 1718 1719 ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); 1720 if (ret < 0) 1721 return ret; 1722 1723 eb = path->nodes[0]; 1724 if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { 1725 ret = btrfs_next_leaf(fs_root, path); 1726 if (ret) 1727 return ret; 1728 eb = path->nodes[0]; 1729 } 1730 1731 btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); 1732 if (found_key->type != key.type || 1733 found_key->objectid != key.objectid) 1734 return 1; 1735 1736 return 0; 1737 } 1738 1739 static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root, 1740 struct btrfs_path *p, 1741 int write_lock_level) 1742 { 1743 struct extent_buffer *b; 1744 int root_lock = 0; 1745 int level = 0; 1746 1747 if (p->search_commit_root) { 1748 b = root->commit_root; 1749 atomic_inc(&b->refs); 1750 level = btrfs_header_level(b); 1751 /* 1752 * Ensure that all callers have set skip_locking when 1753 * p->search_commit_root = 1. 1754 */ 1755 ASSERT(p->skip_locking == 1); 1756 1757 goto out; 1758 } 1759 1760 if (p->skip_locking) { 1761 b = btrfs_root_node(root); 1762 level = btrfs_header_level(b); 1763 goto out; 1764 } 1765 1766 /* We try very hard to do read locks on the root */ 1767 root_lock = BTRFS_READ_LOCK; 1768 1769 /* 1770 * If the level is set to maximum, we can skip trying to get the read 1771 * lock. 1772 */ 1773 if (write_lock_level < BTRFS_MAX_LEVEL) { 1774 /* 1775 * We don't know the level of the root node until we actually 1776 * have it read locked 1777 */ 1778 if (p->nowait) { 1779 b = btrfs_try_read_lock_root_node(root); 1780 if (IS_ERR(b)) 1781 return b; 1782 } else { 1783 b = btrfs_read_lock_root_node(root); 1784 } 1785 level = btrfs_header_level(b); 1786 if (level > write_lock_level) 1787 goto out; 1788 1789 /* Whoops, must trade for write lock */ 1790 btrfs_tree_read_unlock(b); 1791 free_extent_buffer(b); 1792 } 1793 1794 b = btrfs_lock_root_node(root); 1795 root_lock = BTRFS_WRITE_LOCK; 1796 1797 /* The level might have changed, check again */ 1798 level = btrfs_header_level(b); 1799 1800 out: 1801 /* 1802 * The root may have failed to write out at some point, and thus is no 1803 * longer valid, return an error in this case. 1804 */ 1805 if (!extent_buffer_uptodate(b)) { 1806 if (root_lock) 1807 btrfs_tree_unlock_rw(b, root_lock); 1808 free_extent_buffer(b); 1809 return ERR_PTR(-EIO); 1810 } 1811 1812 p->nodes[level] = b; 1813 if (!p->skip_locking) 1814 p->locks[level] = root_lock; 1815 /* 1816 * Callers are responsible for dropping b's references. 1817 */ 1818 return b; 1819 } 1820 1821 /* 1822 * Replace the extent buffer at the lowest level of the path with a cloned 1823 * version. The purpose is to be able to use it safely, after releasing the 1824 * commit root semaphore, even if relocation is happening in parallel, the 1825 * transaction used for relocation is committed and the extent buffer is 1826 * reallocated in the next transaction. 1827 * 1828 * This is used in a context where the caller does not prevent transaction 1829 * commits from happening, either by holding a transaction handle or holding 1830 * some lock, while it's doing searches through a commit root. 1831 * At the moment it's only used for send operations. 1832 */ 1833 static int finish_need_commit_sem_search(struct btrfs_path *path) 1834 { 1835 const int i = path->lowest_level; 1836 const int slot = path->slots[i]; 1837 struct extent_buffer *lowest = path->nodes[i]; 1838 struct extent_buffer *clone; 1839 1840 ASSERT(path->need_commit_sem); 1841 1842 if (!lowest) 1843 return 0; 1844 1845 lockdep_assert_held_read(&lowest->fs_info->commit_root_sem); 1846 1847 clone = btrfs_clone_extent_buffer(lowest); 1848 if (!clone) 1849 return -ENOMEM; 1850 1851 btrfs_release_path(path); 1852 path->nodes[i] = clone; 1853 path->slots[i] = slot; 1854 1855 return 0; 1856 } 1857 1858 static inline int search_for_key_slot(struct extent_buffer *eb, 1859 int search_low_slot, 1860 const struct btrfs_key *key, 1861 int prev_cmp, 1862 int *slot) 1863 { 1864 /* 1865 * If a previous call to btrfs_bin_search() on a parent node returned an 1866 * exact match (prev_cmp == 0), we can safely assume the target key will 1867 * always be at slot 0 on lower levels, since each key pointer 1868 * (struct btrfs_key_ptr) refers to the lowest key accessible from the 1869 * subtree it points to. Thus we can skip searching lower levels. 1870 */ 1871 if (prev_cmp == 0) { 1872 *slot = 0; 1873 return 0; 1874 } 1875 1876 return btrfs_bin_search(eb, search_low_slot, key, slot); 1877 } 1878 1879 static int search_leaf(struct btrfs_trans_handle *trans, 1880 struct btrfs_root *root, 1881 const struct btrfs_key *key, 1882 struct btrfs_path *path, 1883 int ins_len, 1884 int prev_cmp) 1885 { 1886 struct extent_buffer *leaf = path->nodes[0]; 1887 int leaf_free_space = -1; 1888 int search_low_slot = 0; 1889 int ret; 1890 bool do_bin_search = true; 1891 1892 /* 1893 * If we are doing an insertion, the leaf has enough free space and the 1894 * destination slot for the key is not slot 0, then we can unlock our 1895 * write lock on the parent, and any other upper nodes, before doing the 1896 * binary search on the leaf (with search_for_key_slot()), allowing other 1897 * tasks to lock the parent and any other upper nodes. 1898 */ 1899 if (ins_len > 0) { 1900 /* 1901 * Cache the leaf free space, since we will need it later and it 1902 * will not change until then. 1903 */ 1904 leaf_free_space = btrfs_leaf_free_space(leaf); 1905 1906 /* 1907 * !path->locks[1] means we have a single node tree, the leaf is 1908 * the root of the tree. 1909 */ 1910 if (path->locks[1] && leaf_free_space >= ins_len) { 1911 struct btrfs_disk_key first_key; 1912 1913 ASSERT(btrfs_header_nritems(leaf) > 0); 1914 btrfs_item_key(leaf, &first_key, 0); 1915 1916 /* 1917 * Doing the extra comparison with the first key is cheap, 1918 * taking into account that the first key is very likely 1919 * already in a cache line because it immediately follows 1920 * the extent buffer's header and we have recently accessed 1921 * the header's level field. 1922 */ 1923 ret = comp_keys(&first_key, key); 1924 if (ret < 0) { 1925 /* 1926 * The first key is smaller than the key we want 1927 * to insert, so we are safe to unlock all upper 1928 * nodes and we have to do the binary search. 1929 * 1930 * We do use btrfs_unlock_up_safe() and not 1931 * unlock_up() because the later does not unlock 1932 * nodes with a slot of 0 - we can safely unlock 1933 * any node even if its slot is 0 since in this 1934 * case the key does not end up at slot 0 of the 1935 * leaf and there's no need to split the leaf. 1936 */ 1937 btrfs_unlock_up_safe(path, 1); 1938 search_low_slot = 1; 1939 } else { 1940 /* 1941 * The first key is >= then the key we want to 1942 * insert, so we can skip the binary search as 1943 * the target key will be at slot 0. 1944 * 1945 * We can not unlock upper nodes when the key is 1946 * less than the first key, because we will need 1947 * to update the key at slot 0 of the parent node 1948 * and possibly of other upper nodes too. 1949 * If the key matches the first key, then we can 1950 * unlock all the upper nodes, using 1951 * btrfs_unlock_up_safe() instead of unlock_up() 1952 * as stated above. 1953 */ 1954 if (ret == 0) 1955 btrfs_unlock_up_safe(path, 1); 1956 /* 1957 * ret is already 0 or 1, matching the result of 1958 * a btrfs_bin_search() call, so there is no need 1959 * to adjust it. 1960 */ 1961 do_bin_search = false; 1962 path->slots[0] = 0; 1963 } 1964 } 1965 } 1966 1967 if (do_bin_search) { 1968 ret = search_for_key_slot(leaf, search_low_slot, key, 1969 prev_cmp, &path->slots[0]); 1970 if (ret < 0) 1971 return ret; 1972 } 1973 1974 if (ins_len > 0) { 1975 /* 1976 * Item key already exists. In this case, if we are allowed to 1977 * insert the item (for example, in dir_item case, item key 1978 * collision is allowed), it will be merged with the original 1979 * item. Only the item size grows, no new btrfs item will be 1980 * added. If search_for_extension is not set, ins_len already 1981 * accounts the size btrfs_item, deduct it here so leaf space 1982 * check will be correct. 1983 */ 1984 if (ret == 0 && !path->search_for_extension) { 1985 ASSERT(ins_len >= sizeof(struct btrfs_item)); 1986 ins_len -= sizeof(struct btrfs_item); 1987 } 1988 1989 ASSERT(leaf_free_space >= 0); 1990 1991 if (leaf_free_space < ins_len) { 1992 int err; 1993 1994 err = split_leaf(trans, root, key, path, ins_len, 1995 (ret == 0)); 1996 ASSERT(err <= 0); 1997 if (WARN_ON(err > 0)) 1998 err = -EUCLEAN; 1999 if (err) 2000 ret = err; 2001 } 2002 } 2003 2004 return ret; 2005 } 2006 2007 /* 2008 * btrfs_search_slot - look for a key in a tree and perform necessary 2009 * modifications to preserve tree invariants. 2010 * 2011 * @trans: Handle of transaction, used when modifying the tree 2012 * @p: Holds all btree nodes along the search path 2013 * @root: The root node of the tree 2014 * @key: The key we are looking for 2015 * @ins_len: Indicates purpose of search: 2016 * >0 for inserts it's size of item inserted (*) 2017 * <0 for deletions 2018 * 0 for plain searches, not modifying the tree 2019 * 2020 * (*) If size of item inserted doesn't include 2021 * sizeof(struct btrfs_item), then p->search_for_extension must 2022 * be set. 2023 * @cow: boolean should CoW operations be performed. Must always be 1 2024 * when modifying the tree. 2025 * 2026 * If @ins_len > 0, nodes and leaves will be split as we walk down the tree. 2027 * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible) 2028 * 2029 * If @key is found, 0 is returned and you can find the item in the leaf level 2030 * of the path (level 0) 2031 * 2032 * If @key isn't found, 1 is returned and the leaf level of the path (level 0) 2033 * points to the slot where it should be inserted 2034 * 2035 * If an error is encountered while searching the tree a negative error number 2036 * is returned 2037 */ 2038 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2039 const struct btrfs_key *key, struct btrfs_path *p, 2040 int ins_len, int cow) 2041 { 2042 struct btrfs_fs_info *fs_info = root->fs_info; 2043 struct extent_buffer *b; 2044 int slot; 2045 int ret; 2046 int err; 2047 int level; 2048 int lowest_unlock = 1; 2049 /* everything at write_lock_level or lower must be write locked */ 2050 int write_lock_level = 0; 2051 u8 lowest_level = 0; 2052 int min_write_lock_level; 2053 int prev_cmp; 2054 2055 might_sleep(); 2056 2057 lowest_level = p->lowest_level; 2058 WARN_ON(lowest_level && ins_len > 0); 2059 WARN_ON(p->nodes[0] != NULL); 2060 BUG_ON(!cow && ins_len); 2061 2062 /* 2063 * For now only allow nowait for read only operations. There's no 2064 * strict reason why we can't, we just only need it for reads so it's 2065 * only implemented for reads. 2066 */ 2067 ASSERT(!p->nowait || !cow); 2068 2069 if (ins_len < 0) { 2070 lowest_unlock = 2; 2071 2072 /* when we are removing items, we might have to go up to level 2073 * two as we update tree pointers Make sure we keep write 2074 * for those levels as well 2075 */ 2076 write_lock_level = 2; 2077 } else if (ins_len > 0) { 2078 /* 2079 * for inserting items, make sure we have a write lock on 2080 * level 1 so we can update keys 2081 */ 2082 write_lock_level = 1; 2083 } 2084 2085 if (!cow) 2086 write_lock_level = -1; 2087 2088 if (cow && (p->keep_locks || p->lowest_level)) 2089 write_lock_level = BTRFS_MAX_LEVEL; 2090 2091 min_write_lock_level = write_lock_level; 2092 2093 if (p->need_commit_sem) { 2094 ASSERT(p->search_commit_root); 2095 if (p->nowait) { 2096 if (!down_read_trylock(&fs_info->commit_root_sem)) 2097 return -EAGAIN; 2098 } else { 2099 down_read(&fs_info->commit_root_sem); 2100 } 2101 } 2102 2103 again: 2104 prev_cmp = -1; 2105 b = btrfs_search_slot_get_root(root, p, write_lock_level); 2106 if (IS_ERR(b)) { 2107 ret = PTR_ERR(b); 2108 goto done; 2109 } 2110 2111 while (b) { 2112 int dec = 0; 2113 2114 level = btrfs_header_level(b); 2115 2116 if (cow) { 2117 bool last_level = (level == (BTRFS_MAX_LEVEL - 1)); 2118 2119 /* 2120 * if we don't really need to cow this block 2121 * then we don't want to set the path blocking, 2122 * so we test it here 2123 */ 2124 if (!should_cow_block(trans, root, b)) 2125 goto cow_done; 2126 2127 /* 2128 * must have write locks on this node and the 2129 * parent 2130 */ 2131 if (level > write_lock_level || 2132 (level + 1 > write_lock_level && 2133 level + 1 < BTRFS_MAX_LEVEL && 2134 p->nodes[level + 1])) { 2135 write_lock_level = level + 1; 2136 btrfs_release_path(p); 2137 goto again; 2138 } 2139 2140 if (last_level) 2141 err = btrfs_cow_block(trans, root, b, NULL, 0, 2142 &b, 2143 BTRFS_NESTING_COW); 2144 else 2145 err = btrfs_cow_block(trans, root, b, 2146 p->nodes[level + 1], 2147 p->slots[level + 1], &b, 2148 BTRFS_NESTING_COW); 2149 if (err) { 2150 ret = err; 2151 goto done; 2152 } 2153 } 2154 cow_done: 2155 p->nodes[level] = b; 2156 2157 /* 2158 * we have a lock on b and as long as we aren't changing 2159 * the tree, there is no way to for the items in b to change. 2160 * It is safe to drop the lock on our parent before we 2161 * go through the expensive btree search on b. 2162 * 2163 * If we're inserting or deleting (ins_len != 0), then we might 2164 * be changing slot zero, which may require changing the parent. 2165 * So, we can't drop the lock until after we know which slot 2166 * we're operating on. 2167 */ 2168 if (!ins_len && !p->keep_locks) { 2169 int u = level + 1; 2170 2171 if (u < BTRFS_MAX_LEVEL && p->locks[u]) { 2172 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]); 2173 p->locks[u] = 0; 2174 } 2175 } 2176 2177 if (level == 0) { 2178 if (ins_len > 0) 2179 ASSERT(write_lock_level >= 1); 2180 2181 ret = search_leaf(trans, root, key, p, ins_len, prev_cmp); 2182 if (!p->search_for_split) 2183 unlock_up(p, level, lowest_unlock, 2184 min_write_lock_level, NULL); 2185 goto done; 2186 } 2187 2188 ret = search_for_key_slot(b, 0, key, prev_cmp, &slot); 2189 if (ret < 0) 2190 goto done; 2191 prev_cmp = ret; 2192 2193 if (ret && slot > 0) { 2194 dec = 1; 2195 slot--; 2196 } 2197 p->slots[level] = slot; 2198 err = setup_nodes_for_search(trans, root, p, b, level, ins_len, 2199 &write_lock_level); 2200 if (err == -EAGAIN) 2201 goto again; 2202 if (err) { 2203 ret = err; 2204 goto done; 2205 } 2206 b = p->nodes[level]; 2207 slot = p->slots[level]; 2208 2209 /* 2210 * Slot 0 is special, if we change the key we have to update 2211 * the parent pointer which means we must have a write lock on 2212 * the parent 2213 */ 2214 if (slot == 0 && ins_len && write_lock_level < level + 1) { 2215 write_lock_level = level + 1; 2216 btrfs_release_path(p); 2217 goto again; 2218 } 2219 2220 unlock_up(p, level, lowest_unlock, min_write_lock_level, 2221 &write_lock_level); 2222 2223 if (level == lowest_level) { 2224 if (dec) 2225 p->slots[level]++; 2226 goto done; 2227 } 2228 2229 err = read_block_for_search(root, p, &b, level, slot, key); 2230 if (err == -EAGAIN) 2231 goto again; 2232 if (err) { 2233 ret = err; 2234 goto done; 2235 } 2236 2237 if (!p->skip_locking) { 2238 level = btrfs_header_level(b); 2239 2240 btrfs_maybe_reset_lockdep_class(root, b); 2241 2242 if (level <= write_lock_level) { 2243 btrfs_tree_lock(b); 2244 p->locks[level] = BTRFS_WRITE_LOCK; 2245 } else { 2246 if (p->nowait) { 2247 if (!btrfs_try_tree_read_lock(b)) { 2248 free_extent_buffer(b); 2249 ret = -EAGAIN; 2250 goto done; 2251 } 2252 } else { 2253 btrfs_tree_read_lock(b); 2254 } 2255 p->locks[level] = BTRFS_READ_LOCK; 2256 } 2257 p->nodes[level] = b; 2258 } 2259 } 2260 ret = 1; 2261 done: 2262 if (ret < 0 && !p->skip_release_on_error) 2263 btrfs_release_path(p); 2264 2265 if (p->need_commit_sem) { 2266 int ret2; 2267 2268 ret2 = finish_need_commit_sem_search(p); 2269 up_read(&fs_info->commit_root_sem); 2270 if (ret2) 2271 ret = ret2; 2272 } 2273 2274 return ret; 2275 } 2276 ALLOW_ERROR_INJECTION(btrfs_search_slot, ERRNO); 2277 2278 /* 2279 * Like btrfs_search_slot, this looks for a key in the given tree. It uses the 2280 * current state of the tree together with the operations recorded in the tree 2281 * modification log to search for the key in a previous version of this tree, as 2282 * denoted by the time_seq parameter. 2283 * 2284 * Naturally, there is no support for insert, delete or cow operations. 2285 * 2286 * The resulting path and return value will be set up as if we called 2287 * btrfs_search_slot at that point in time with ins_len and cow both set to 0. 2288 */ 2289 int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key, 2290 struct btrfs_path *p, u64 time_seq) 2291 { 2292 struct btrfs_fs_info *fs_info = root->fs_info; 2293 struct extent_buffer *b; 2294 int slot; 2295 int ret; 2296 int err; 2297 int level; 2298 int lowest_unlock = 1; 2299 u8 lowest_level = 0; 2300 2301 lowest_level = p->lowest_level; 2302 WARN_ON(p->nodes[0] != NULL); 2303 ASSERT(!p->nowait); 2304 2305 if (p->search_commit_root) { 2306 BUG_ON(time_seq); 2307 return btrfs_search_slot(NULL, root, key, p, 0, 0); 2308 } 2309 2310 again: 2311 b = btrfs_get_old_root(root, time_seq); 2312 if (!b) { 2313 ret = -EIO; 2314 goto done; 2315 } 2316 level = btrfs_header_level(b); 2317 p->locks[level] = BTRFS_READ_LOCK; 2318 2319 while (b) { 2320 int dec = 0; 2321 2322 level = btrfs_header_level(b); 2323 p->nodes[level] = b; 2324 2325 /* 2326 * we have a lock on b and as long as we aren't changing 2327 * the tree, there is no way to for the items in b to change. 2328 * It is safe to drop the lock on our parent before we 2329 * go through the expensive btree search on b. 2330 */ 2331 btrfs_unlock_up_safe(p, level + 1); 2332 2333 ret = btrfs_bin_search(b, 0, key, &slot); 2334 if (ret < 0) 2335 goto done; 2336 2337 if (level == 0) { 2338 p->slots[level] = slot; 2339 unlock_up(p, level, lowest_unlock, 0, NULL); 2340 goto done; 2341 } 2342 2343 if (ret && slot > 0) { 2344 dec = 1; 2345 slot--; 2346 } 2347 p->slots[level] = slot; 2348 unlock_up(p, level, lowest_unlock, 0, NULL); 2349 2350 if (level == lowest_level) { 2351 if (dec) 2352 p->slots[level]++; 2353 goto done; 2354 } 2355 2356 err = read_block_for_search(root, p, &b, level, slot, key); 2357 if (err == -EAGAIN) 2358 goto again; 2359 if (err) { 2360 ret = err; 2361 goto done; 2362 } 2363 2364 level = btrfs_header_level(b); 2365 btrfs_tree_read_lock(b); 2366 b = btrfs_tree_mod_log_rewind(fs_info, p, b, time_seq); 2367 if (!b) { 2368 ret = -ENOMEM; 2369 goto done; 2370 } 2371 p->locks[level] = BTRFS_READ_LOCK; 2372 p->nodes[level] = b; 2373 } 2374 ret = 1; 2375 done: 2376 if (ret < 0) 2377 btrfs_release_path(p); 2378 2379 return ret; 2380 } 2381 2382 /* 2383 * Search the tree again to find a leaf with smaller keys. 2384 * Returns 0 if it found something. 2385 * Returns 1 if there are no smaller keys. 2386 * Returns < 0 on error. 2387 * 2388 * This may release the path, and so you may lose any locks held at the 2389 * time you call it. 2390 */ 2391 static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 2392 { 2393 struct btrfs_key key; 2394 struct btrfs_key orig_key; 2395 struct btrfs_disk_key found_key; 2396 int ret; 2397 2398 btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 2399 orig_key = key; 2400 2401 if (key.offset > 0) { 2402 key.offset--; 2403 } else if (key.type > 0) { 2404 key.type--; 2405 key.offset = (u64)-1; 2406 } else if (key.objectid > 0) { 2407 key.objectid--; 2408 key.type = (u8)-1; 2409 key.offset = (u64)-1; 2410 } else { 2411 return 1; 2412 } 2413 2414 btrfs_release_path(path); 2415 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 2416 if (ret <= 0) 2417 return ret; 2418 2419 /* 2420 * Previous key not found. Even if we were at slot 0 of the leaf we had 2421 * before releasing the path and calling btrfs_search_slot(), we now may 2422 * be in a slot pointing to the same original key - this can happen if 2423 * after we released the path, one of more items were moved from a 2424 * sibling leaf into the front of the leaf we had due to an insertion 2425 * (see push_leaf_right()). 2426 * If we hit this case and our slot is > 0 and just decrement the slot 2427 * so that the caller does not process the same key again, which may or 2428 * may not break the caller, depending on its logic. 2429 */ 2430 if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) { 2431 btrfs_item_key(path->nodes[0], &found_key, path->slots[0]); 2432 ret = comp_keys(&found_key, &orig_key); 2433 if (ret == 0) { 2434 if (path->slots[0] > 0) { 2435 path->slots[0]--; 2436 return 0; 2437 } 2438 /* 2439 * At slot 0, same key as before, it means orig_key is 2440 * the lowest, leftmost, key in the tree. We're done. 2441 */ 2442 return 1; 2443 } 2444 } 2445 2446 btrfs_item_key(path->nodes[0], &found_key, 0); 2447 ret = comp_keys(&found_key, &key); 2448 /* 2449 * We might have had an item with the previous key in the tree right 2450 * before we released our path. And after we released our path, that 2451 * item might have been pushed to the first slot (0) of the leaf we 2452 * were holding due to a tree balance. Alternatively, an item with the 2453 * previous key can exist as the only element of a leaf (big fat item). 2454 * Therefore account for these 2 cases, so that our callers (like 2455 * btrfs_previous_item) don't miss an existing item with a key matching 2456 * the previous key we computed above. 2457 */ 2458 if (ret <= 0) 2459 return 0; 2460 return 1; 2461 } 2462 2463 /* 2464 * helper to use instead of search slot if no exact match is needed but 2465 * instead the next or previous item should be returned. 2466 * When find_higher is true, the next higher item is returned, the next lower 2467 * otherwise. 2468 * When return_any and find_higher are both true, and no higher item is found, 2469 * return the next lower instead. 2470 * When return_any is true and find_higher is false, and no lower item is found, 2471 * return the next higher instead. 2472 * It returns 0 if any item is found, 1 if none is found (tree empty), and 2473 * < 0 on error 2474 */ 2475 int btrfs_search_slot_for_read(struct btrfs_root *root, 2476 const struct btrfs_key *key, 2477 struct btrfs_path *p, int find_higher, 2478 int return_any) 2479 { 2480 int ret; 2481 struct extent_buffer *leaf; 2482 2483 again: 2484 ret = btrfs_search_slot(NULL, root, key, p, 0, 0); 2485 if (ret <= 0) 2486 return ret; 2487 /* 2488 * a return value of 1 means the path is at the position where the 2489 * item should be inserted. Normally this is the next bigger item, 2490 * but in case the previous item is the last in a leaf, path points 2491 * to the first free slot in the previous leaf, i.e. at an invalid 2492 * item. 2493 */ 2494 leaf = p->nodes[0]; 2495 2496 if (find_higher) { 2497 if (p->slots[0] >= btrfs_header_nritems(leaf)) { 2498 ret = btrfs_next_leaf(root, p); 2499 if (ret <= 0) 2500 return ret; 2501 if (!return_any) 2502 return 1; 2503 /* 2504 * no higher item found, return the next 2505 * lower instead 2506 */ 2507 return_any = 0; 2508 find_higher = 0; 2509 btrfs_release_path(p); 2510 goto again; 2511 } 2512 } else { 2513 if (p->slots[0] == 0) { 2514 ret = btrfs_prev_leaf(root, p); 2515 if (ret < 0) 2516 return ret; 2517 if (!ret) { 2518 leaf = p->nodes[0]; 2519 if (p->slots[0] == btrfs_header_nritems(leaf)) 2520 p->slots[0]--; 2521 return 0; 2522 } 2523 if (!return_any) 2524 return 1; 2525 /* 2526 * no lower item found, return the next 2527 * higher instead 2528 */ 2529 return_any = 0; 2530 find_higher = 1; 2531 btrfs_release_path(p); 2532 goto again; 2533 } else { 2534 --p->slots[0]; 2535 } 2536 } 2537 return 0; 2538 } 2539 2540 /* 2541 * Execute search and call btrfs_previous_item to traverse backwards if the item 2542 * was not found. 2543 * 2544 * Return 0 if found, 1 if not found and < 0 if error. 2545 */ 2546 int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key, 2547 struct btrfs_path *path) 2548 { 2549 int ret; 2550 2551 ret = btrfs_search_slot(NULL, root, key, path, 0, 0); 2552 if (ret > 0) 2553 ret = btrfs_previous_item(root, path, key->objectid, key->type); 2554 2555 if (ret == 0) 2556 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]); 2557 2558 return ret; 2559 } 2560 2561 /* 2562 * Search for a valid slot for the given path. 2563 * 2564 * @root: The root node of the tree. 2565 * @key: Will contain a valid item if found. 2566 * @path: The starting point to validate the slot. 2567 * 2568 * Return: 0 if the item is valid 2569 * 1 if not found 2570 * <0 if error. 2571 */ 2572 int btrfs_get_next_valid_item(struct btrfs_root *root, struct btrfs_key *key, 2573 struct btrfs_path *path) 2574 { 2575 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { 2576 int ret; 2577 2578 ret = btrfs_next_leaf(root, path); 2579 if (ret) 2580 return ret; 2581 } 2582 2583 btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]); 2584 return 0; 2585 } 2586 2587 /* 2588 * adjust the pointers going up the tree, starting at level 2589 * making sure the right key of each node is points to 'key'. 2590 * This is used after shifting pointers to the left, so it stops 2591 * fixing up pointers when a given leaf/node is not in slot 0 of the 2592 * higher levels 2593 * 2594 */ 2595 static void fixup_low_keys(struct btrfs_path *path, 2596 struct btrfs_disk_key *key, int level) 2597 { 2598 int i; 2599 struct extent_buffer *t; 2600 int ret; 2601 2602 for (i = level; i < BTRFS_MAX_LEVEL; i++) { 2603 int tslot = path->slots[i]; 2604 2605 if (!path->nodes[i]) 2606 break; 2607 t = path->nodes[i]; 2608 ret = btrfs_tree_mod_log_insert_key(t, tslot, 2609 BTRFS_MOD_LOG_KEY_REPLACE); 2610 BUG_ON(ret < 0); 2611 btrfs_set_node_key(t, key, tslot); 2612 btrfs_mark_buffer_dirty(path->nodes[i]); 2613 if (tslot != 0) 2614 break; 2615 } 2616 } 2617 2618 /* 2619 * update item key. 2620 * 2621 * This function isn't completely safe. It's the caller's responsibility 2622 * that the new key won't break the order 2623 */ 2624 void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info, 2625 struct btrfs_path *path, 2626 const struct btrfs_key *new_key) 2627 { 2628 struct btrfs_disk_key disk_key; 2629 struct extent_buffer *eb; 2630 int slot; 2631 2632 eb = path->nodes[0]; 2633 slot = path->slots[0]; 2634 if (slot > 0) { 2635 btrfs_item_key(eb, &disk_key, slot - 1); 2636 if (unlikely(comp_keys(&disk_key, new_key) >= 0)) { 2637 btrfs_print_leaf(eb); 2638 btrfs_crit(fs_info, 2639 "slot %u key (%llu %u %llu) new key (%llu %u %llu)", 2640 slot, btrfs_disk_key_objectid(&disk_key), 2641 btrfs_disk_key_type(&disk_key), 2642 btrfs_disk_key_offset(&disk_key), 2643 new_key->objectid, new_key->type, 2644 new_key->offset); 2645 BUG(); 2646 } 2647 } 2648 if (slot < btrfs_header_nritems(eb) - 1) { 2649 btrfs_item_key(eb, &disk_key, slot + 1); 2650 if (unlikely(comp_keys(&disk_key, new_key) <= 0)) { 2651 btrfs_print_leaf(eb); 2652 btrfs_crit(fs_info, 2653 "slot %u key (%llu %u %llu) new key (%llu %u %llu)", 2654 slot, btrfs_disk_key_objectid(&disk_key), 2655 btrfs_disk_key_type(&disk_key), 2656 btrfs_disk_key_offset(&disk_key), 2657 new_key->objectid, new_key->type, 2658 new_key->offset); 2659 BUG(); 2660 } 2661 } 2662 2663 btrfs_cpu_key_to_disk(&disk_key, new_key); 2664 btrfs_set_item_key(eb, &disk_key, slot); 2665 btrfs_mark_buffer_dirty(eb); 2666 if (slot == 0) 2667 fixup_low_keys(path, &disk_key, 1); 2668 } 2669 2670 /* 2671 * Check key order of two sibling extent buffers. 2672 * 2673 * Return true if something is wrong. 2674 * Return false if everything is fine. 2675 * 2676 * Tree-checker only works inside one tree block, thus the following 2677 * corruption can not be detected by tree-checker: 2678 * 2679 * Leaf @left | Leaf @right 2680 * -------------------------------------------------------------- 2681 * | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 | 2682 * 2683 * Key f6 in leaf @left itself is valid, but not valid when the next 2684 * key in leaf @right is 7. 2685 * This can only be checked at tree block merge time. 2686 * And since tree checker has ensured all key order in each tree block 2687 * is correct, we only need to bother the last key of @left and the first 2688 * key of @right. 2689 */ 2690 static bool check_sibling_keys(struct extent_buffer *left, 2691 struct extent_buffer *right) 2692 { 2693 struct btrfs_key left_last; 2694 struct btrfs_key right_first; 2695 int level = btrfs_header_level(left); 2696 int nr_left = btrfs_header_nritems(left); 2697 int nr_right = btrfs_header_nritems(right); 2698 2699 /* No key to check in one of the tree blocks */ 2700 if (!nr_left || !nr_right) 2701 return false; 2702 2703 if (level) { 2704 btrfs_node_key_to_cpu(left, &left_last, nr_left - 1); 2705 btrfs_node_key_to_cpu(right, &right_first, 0); 2706 } else { 2707 btrfs_item_key_to_cpu(left, &left_last, nr_left - 1); 2708 btrfs_item_key_to_cpu(right, &right_first, 0); 2709 } 2710 2711 if (unlikely(btrfs_comp_cpu_keys(&left_last, &right_first) >= 0)) { 2712 btrfs_crit(left->fs_info, "left extent buffer:"); 2713 btrfs_print_tree(left, false); 2714 btrfs_crit(left->fs_info, "right extent buffer:"); 2715 btrfs_print_tree(right, false); 2716 btrfs_crit(left->fs_info, 2717 "bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)", 2718 left_last.objectid, left_last.type, 2719 left_last.offset, right_first.objectid, 2720 right_first.type, right_first.offset); 2721 return true; 2722 } 2723 return false; 2724 } 2725 2726 /* 2727 * try to push data from one node into the next node left in the 2728 * tree. 2729 * 2730 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 2731 * error, and > 0 if there was no room in the left hand block. 2732 */ 2733 static int push_node_left(struct btrfs_trans_handle *trans, 2734 struct extent_buffer *dst, 2735 struct extent_buffer *src, int empty) 2736 { 2737 struct btrfs_fs_info *fs_info = trans->fs_info; 2738 int push_items = 0; 2739 int src_nritems; 2740 int dst_nritems; 2741 int ret = 0; 2742 2743 src_nritems = btrfs_header_nritems(src); 2744 dst_nritems = btrfs_header_nritems(dst); 2745 push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems; 2746 WARN_ON(btrfs_header_generation(src) != trans->transid); 2747 WARN_ON(btrfs_header_generation(dst) != trans->transid); 2748 2749 if (!empty && src_nritems <= 8) 2750 return 1; 2751 2752 if (push_items <= 0) 2753 return 1; 2754 2755 if (empty) { 2756 push_items = min(src_nritems, push_items); 2757 if (push_items < src_nritems) { 2758 /* leave at least 8 pointers in the node if 2759 * we aren't going to empty it 2760 */ 2761 if (src_nritems - push_items < 8) { 2762 if (push_items <= 8) 2763 return 1; 2764 push_items -= 8; 2765 } 2766 } 2767 } else 2768 push_items = min(src_nritems - 8, push_items); 2769 2770 /* dst is the left eb, src is the middle eb */ 2771 if (check_sibling_keys(dst, src)) { 2772 ret = -EUCLEAN; 2773 btrfs_abort_transaction(trans, ret); 2774 return ret; 2775 } 2776 ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items); 2777 if (ret) { 2778 btrfs_abort_transaction(trans, ret); 2779 return ret; 2780 } 2781 copy_extent_buffer(dst, src, 2782 btrfs_node_key_ptr_offset(dst, dst_nritems), 2783 btrfs_node_key_ptr_offset(src, 0), 2784 push_items * sizeof(struct btrfs_key_ptr)); 2785 2786 if (push_items < src_nritems) { 2787 /* 2788 * Don't call btrfs_tree_mod_log_insert_move() here, key removal 2789 * was already fully logged by btrfs_tree_mod_log_eb_copy() above. 2790 */ 2791 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(src, 0), 2792 btrfs_node_key_ptr_offset(src, push_items), 2793 (src_nritems - push_items) * 2794 sizeof(struct btrfs_key_ptr)); 2795 } 2796 btrfs_set_header_nritems(src, src_nritems - push_items); 2797 btrfs_set_header_nritems(dst, dst_nritems + push_items); 2798 btrfs_mark_buffer_dirty(src); 2799 btrfs_mark_buffer_dirty(dst); 2800 2801 return ret; 2802 } 2803 2804 /* 2805 * try to push data from one node into the next node right in the 2806 * tree. 2807 * 2808 * returns 0 if some ptrs were pushed, < 0 if there was some horrible 2809 * error, and > 0 if there was no room in the right hand block. 2810 * 2811 * this will only push up to 1/2 the contents of the left node over 2812 */ 2813 static int balance_node_right(struct btrfs_trans_handle *trans, 2814 struct extent_buffer *dst, 2815 struct extent_buffer *src) 2816 { 2817 struct btrfs_fs_info *fs_info = trans->fs_info; 2818 int push_items = 0; 2819 int max_push; 2820 int src_nritems; 2821 int dst_nritems; 2822 int ret = 0; 2823 2824 WARN_ON(btrfs_header_generation(src) != trans->transid); 2825 WARN_ON(btrfs_header_generation(dst) != trans->transid); 2826 2827 src_nritems = btrfs_header_nritems(src); 2828 dst_nritems = btrfs_header_nritems(dst); 2829 push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems; 2830 if (push_items <= 0) 2831 return 1; 2832 2833 if (src_nritems < 4) 2834 return 1; 2835 2836 max_push = src_nritems / 2 + 1; 2837 /* don't try to empty the node */ 2838 if (max_push >= src_nritems) 2839 return 1; 2840 2841 if (max_push < push_items) 2842 push_items = max_push; 2843 2844 /* dst is the right eb, src is the middle eb */ 2845 if (check_sibling_keys(src, dst)) { 2846 ret = -EUCLEAN; 2847 btrfs_abort_transaction(trans, ret); 2848 return ret; 2849 } 2850 ret = btrfs_tree_mod_log_insert_move(dst, push_items, 0, dst_nritems); 2851 BUG_ON(ret < 0); 2852 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(dst, push_items), 2853 btrfs_node_key_ptr_offset(dst, 0), 2854 (dst_nritems) * 2855 sizeof(struct btrfs_key_ptr)); 2856 2857 ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items, 2858 push_items); 2859 if (ret) { 2860 btrfs_abort_transaction(trans, ret); 2861 return ret; 2862 } 2863 copy_extent_buffer(dst, src, 2864 btrfs_node_key_ptr_offset(dst, 0), 2865 btrfs_node_key_ptr_offset(src, src_nritems - push_items), 2866 push_items * sizeof(struct btrfs_key_ptr)); 2867 2868 btrfs_set_header_nritems(src, src_nritems - push_items); 2869 btrfs_set_header_nritems(dst, dst_nritems + push_items); 2870 2871 btrfs_mark_buffer_dirty(src); 2872 btrfs_mark_buffer_dirty(dst); 2873 2874 return ret; 2875 } 2876 2877 /* 2878 * helper function to insert a new root level in the tree. 2879 * A new node is allocated, and a single item is inserted to 2880 * point to the existing root 2881 * 2882 * returns zero on success or < 0 on failure. 2883 */ 2884 static noinline int insert_new_root(struct btrfs_trans_handle *trans, 2885 struct btrfs_root *root, 2886 struct btrfs_path *path, int level) 2887 { 2888 struct btrfs_fs_info *fs_info = root->fs_info; 2889 u64 lower_gen; 2890 struct extent_buffer *lower; 2891 struct extent_buffer *c; 2892 struct extent_buffer *old; 2893 struct btrfs_disk_key lower_key; 2894 int ret; 2895 2896 BUG_ON(path->nodes[level]); 2897 BUG_ON(path->nodes[level-1] != root->node); 2898 2899 lower = path->nodes[level-1]; 2900 if (level == 1) 2901 btrfs_item_key(lower, &lower_key, 0); 2902 else 2903 btrfs_node_key(lower, &lower_key, 0); 2904 2905 c = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 2906 &lower_key, level, root->node->start, 0, 2907 BTRFS_NESTING_NEW_ROOT); 2908 if (IS_ERR(c)) 2909 return PTR_ERR(c); 2910 2911 root_add_used(root, fs_info->nodesize); 2912 2913 btrfs_set_header_nritems(c, 1); 2914 btrfs_set_node_key(c, &lower_key, 0); 2915 btrfs_set_node_blockptr(c, 0, lower->start); 2916 lower_gen = btrfs_header_generation(lower); 2917 WARN_ON(lower_gen != trans->transid); 2918 2919 btrfs_set_node_ptr_generation(c, 0, lower_gen); 2920 2921 btrfs_mark_buffer_dirty(c); 2922 2923 old = root->node; 2924 ret = btrfs_tree_mod_log_insert_root(root->node, c, false); 2925 BUG_ON(ret < 0); 2926 rcu_assign_pointer(root->node, c); 2927 2928 /* the super has an extra ref to root->node */ 2929 free_extent_buffer(old); 2930 2931 add_root_to_dirty_list(root); 2932 atomic_inc(&c->refs); 2933 path->nodes[level] = c; 2934 path->locks[level] = BTRFS_WRITE_LOCK; 2935 path->slots[level] = 0; 2936 return 0; 2937 } 2938 2939 /* 2940 * worker function to insert a single pointer in a node. 2941 * the node should have enough room for the pointer already 2942 * 2943 * slot and level indicate where you want the key to go, and 2944 * blocknr is the block the key points to. 2945 */ 2946 static void insert_ptr(struct btrfs_trans_handle *trans, 2947 struct btrfs_path *path, 2948 struct btrfs_disk_key *key, u64 bytenr, 2949 int slot, int level) 2950 { 2951 struct extent_buffer *lower; 2952 int nritems; 2953 int ret; 2954 2955 BUG_ON(!path->nodes[level]); 2956 btrfs_assert_tree_write_locked(path->nodes[level]); 2957 lower = path->nodes[level]; 2958 nritems = btrfs_header_nritems(lower); 2959 BUG_ON(slot > nritems); 2960 BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info)); 2961 if (slot != nritems) { 2962 if (level) { 2963 ret = btrfs_tree_mod_log_insert_move(lower, slot + 1, 2964 slot, nritems - slot); 2965 BUG_ON(ret < 0); 2966 } 2967 memmove_extent_buffer(lower, 2968 btrfs_node_key_ptr_offset(lower, slot + 1), 2969 btrfs_node_key_ptr_offset(lower, slot), 2970 (nritems - slot) * sizeof(struct btrfs_key_ptr)); 2971 } 2972 if (level) { 2973 ret = btrfs_tree_mod_log_insert_key(lower, slot, 2974 BTRFS_MOD_LOG_KEY_ADD); 2975 BUG_ON(ret < 0); 2976 } 2977 btrfs_set_node_key(lower, key, slot); 2978 btrfs_set_node_blockptr(lower, slot, bytenr); 2979 WARN_ON(trans->transid == 0); 2980 btrfs_set_node_ptr_generation(lower, slot, trans->transid); 2981 btrfs_set_header_nritems(lower, nritems + 1); 2982 btrfs_mark_buffer_dirty(lower); 2983 } 2984 2985 /* 2986 * split the node at the specified level in path in two. 2987 * The path is corrected to point to the appropriate node after the split 2988 * 2989 * Before splitting this tries to make some room in the node by pushing 2990 * left and right, if either one works, it returns right away. 2991 * 2992 * returns 0 on success and < 0 on failure 2993 */ 2994 static noinline int split_node(struct btrfs_trans_handle *trans, 2995 struct btrfs_root *root, 2996 struct btrfs_path *path, int level) 2997 { 2998 struct btrfs_fs_info *fs_info = root->fs_info; 2999 struct extent_buffer *c; 3000 struct extent_buffer *split; 3001 struct btrfs_disk_key disk_key; 3002 int mid; 3003 int ret; 3004 u32 c_nritems; 3005 3006 c = path->nodes[level]; 3007 WARN_ON(btrfs_header_generation(c) != trans->transid); 3008 if (c == root->node) { 3009 /* 3010 * trying to split the root, lets make a new one 3011 * 3012 * tree mod log: We don't log_removal old root in 3013 * insert_new_root, because that root buffer will be kept as a 3014 * normal node. We are going to log removal of half of the 3015 * elements below with btrfs_tree_mod_log_eb_copy(). We're 3016 * holding a tree lock on the buffer, which is why we cannot 3017 * race with other tree_mod_log users. 3018 */ 3019 ret = insert_new_root(trans, root, path, level + 1); 3020 if (ret) 3021 return ret; 3022 } else { 3023 ret = push_nodes_for_insert(trans, root, path, level); 3024 c = path->nodes[level]; 3025 if (!ret && btrfs_header_nritems(c) < 3026 BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) 3027 return 0; 3028 if (ret < 0) 3029 return ret; 3030 } 3031 3032 c_nritems = btrfs_header_nritems(c); 3033 mid = (c_nritems + 1) / 2; 3034 btrfs_node_key(c, &disk_key, mid); 3035 3036 split = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 3037 &disk_key, level, c->start, 0, 3038 BTRFS_NESTING_SPLIT); 3039 if (IS_ERR(split)) 3040 return PTR_ERR(split); 3041 3042 root_add_used(root, fs_info->nodesize); 3043 ASSERT(btrfs_header_level(c) == level); 3044 3045 ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid); 3046 if (ret) { 3047 btrfs_abort_transaction(trans, ret); 3048 return ret; 3049 } 3050 copy_extent_buffer(split, c, 3051 btrfs_node_key_ptr_offset(split, 0), 3052 btrfs_node_key_ptr_offset(c, mid), 3053 (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 3054 btrfs_set_header_nritems(split, c_nritems - mid); 3055 btrfs_set_header_nritems(c, mid); 3056 3057 btrfs_mark_buffer_dirty(c); 3058 btrfs_mark_buffer_dirty(split); 3059 3060 insert_ptr(trans, path, &disk_key, split->start, 3061 path->slots[level + 1] + 1, level + 1); 3062 3063 if (path->slots[level] >= mid) { 3064 path->slots[level] -= mid; 3065 btrfs_tree_unlock(c); 3066 free_extent_buffer(c); 3067 path->nodes[level] = split; 3068 path->slots[level + 1] += 1; 3069 } else { 3070 btrfs_tree_unlock(split); 3071 free_extent_buffer(split); 3072 } 3073 return 0; 3074 } 3075 3076 /* 3077 * how many bytes are required to store the items in a leaf. start 3078 * and nr indicate which items in the leaf to check. This totals up the 3079 * space used both by the item structs and the item data 3080 */ 3081 static int leaf_space_used(const struct extent_buffer *l, int start, int nr) 3082 { 3083 int data_len; 3084 int nritems = btrfs_header_nritems(l); 3085 int end = min(nritems, start + nr) - 1; 3086 3087 if (!nr) 3088 return 0; 3089 data_len = btrfs_item_offset(l, start) + btrfs_item_size(l, start); 3090 data_len = data_len - btrfs_item_offset(l, end); 3091 data_len += sizeof(struct btrfs_item) * nr; 3092 WARN_ON(data_len < 0); 3093 return data_len; 3094 } 3095 3096 /* 3097 * The space between the end of the leaf items and 3098 * the start of the leaf data. IOW, how much room 3099 * the leaf has left for both items and data 3100 */ 3101 int btrfs_leaf_free_space(const struct extent_buffer *leaf) 3102 { 3103 struct btrfs_fs_info *fs_info = leaf->fs_info; 3104 int nritems = btrfs_header_nritems(leaf); 3105 int ret; 3106 3107 ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); 3108 if (ret < 0) { 3109 btrfs_crit(fs_info, 3110 "leaf free space ret %d, leaf data size %lu, used %d nritems %d", 3111 ret, 3112 (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info), 3113 leaf_space_used(leaf, 0, nritems), nritems); 3114 } 3115 return ret; 3116 } 3117 3118 /* 3119 * min slot controls the lowest index we're willing to push to the 3120 * right. We'll push up to and including min_slot, but no lower 3121 */ 3122 static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, 3123 struct btrfs_path *path, 3124 int data_size, int empty, 3125 struct extent_buffer *right, 3126 int free_space, u32 left_nritems, 3127 u32 min_slot) 3128 { 3129 struct btrfs_fs_info *fs_info = right->fs_info; 3130 struct extent_buffer *left = path->nodes[0]; 3131 struct extent_buffer *upper = path->nodes[1]; 3132 struct btrfs_map_token token; 3133 struct btrfs_disk_key disk_key; 3134 int slot; 3135 u32 i; 3136 int push_space = 0; 3137 int push_items = 0; 3138 u32 nr; 3139 u32 right_nritems; 3140 u32 data_end; 3141 u32 this_item_size; 3142 3143 if (empty) 3144 nr = 0; 3145 else 3146 nr = max_t(u32, 1, min_slot); 3147 3148 if (path->slots[0] >= left_nritems) 3149 push_space += data_size; 3150 3151 slot = path->slots[1]; 3152 i = left_nritems - 1; 3153 while (i >= nr) { 3154 if (!empty && push_items > 0) { 3155 if (path->slots[0] > i) 3156 break; 3157 if (path->slots[0] == i) { 3158 int space = btrfs_leaf_free_space(left); 3159 3160 if (space + push_space * 2 > free_space) 3161 break; 3162 } 3163 } 3164 3165 if (path->slots[0] == i) 3166 push_space += data_size; 3167 3168 this_item_size = btrfs_item_size(left, i); 3169 if (this_item_size + sizeof(struct btrfs_item) + 3170 push_space > free_space) 3171 break; 3172 3173 push_items++; 3174 push_space += this_item_size + sizeof(struct btrfs_item); 3175 if (i == 0) 3176 break; 3177 i--; 3178 } 3179 3180 if (push_items == 0) 3181 goto out_unlock; 3182 3183 WARN_ON(!empty && push_items == left_nritems); 3184 3185 /* push left to right */ 3186 right_nritems = btrfs_header_nritems(right); 3187 3188 push_space = btrfs_item_data_end(left, left_nritems - push_items); 3189 push_space -= leaf_data_end(left); 3190 3191 /* make room in the right data area */ 3192 data_end = leaf_data_end(right); 3193 memmove_leaf_data(right, data_end - push_space, data_end, 3194 BTRFS_LEAF_DATA_SIZE(fs_info) - data_end); 3195 3196 /* copy from the left data area */ 3197 copy_leaf_data(right, left, BTRFS_LEAF_DATA_SIZE(fs_info) - push_space, 3198 leaf_data_end(left), push_space); 3199 3200 memmove_leaf_items(right, push_items, 0, right_nritems); 3201 3202 /* copy the items from left to right */ 3203 copy_leaf_items(right, left, 0, left_nritems - push_items, push_items); 3204 3205 /* update the item pointers */ 3206 btrfs_init_map_token(&token, right); 3207 right_nritems += push_items; 3208 btrfs_set_header_nritems(right, right_nritems); 3209 push_space = BTRFS_LEAF_DATA_SIZE(fs_info); 3210 for (i = 0; i < right_nritems; i++) { 3211 push_space -= btrfs_token_item_size(&token, i); 3212 btrfs_set_token_item_offset(&token, i, push_space); 3213 } 3214 3215 left_nritems -= push_items; 3216 btrfs_set_header_nritems(left, left_nritems); 3217 3218 if (left_nritems) 3219 btrfs_mark_buffer_dirty(left); 3220 else 3221 btrfs_clear_buffer_dirty(trans, left); 3222 3223 btrfs_mark_buffer_dirty(right); 3224 3225 btrfs_item_key(right, &disk_key, 0); 3226 btrfs_set_node_key(upper, &disk_key, slot + 1); 3227 btrfs_mark_buffer_dirty(upper); 3228 3229 /* then fixup the leaf pointer in the path */ 3230 if (path->slots[0] >= left_nritems) { 3231 path->slots[0] -= left_nritems; 3232 if (btrfs_header_nritems(path->nodes[0]) == 0) 3233 btrfs_clear_buffer_dirty(trans, path->nodes[0]); 3234 btrfs_tree_unlock(path->nodes[0]); 3235 free_extent_buffer(path->nodes[0]); 3236 path->nodes[0] = right; 3237 path->slots[1] += 1; 3238 } else { 3239 btrfs_tree_unlock(right); 3240 free_extent_buffer(right); 3241 } 3242 return 0; 3243 3244 out_unlock: 3245 btrfs_tree_unlock(right); 3246 free_extent_buffer(right); 3247 return 1; 3248 } 3249 3250 /* 3251 * push some data in the path leaf to the right, trying to free up at 3252 * least data_size bytes. returns zero if the push worked, nonzero otherwise 3253 * 3254 * returns 1 if the push failed because the other node didn't have enough 3255 * room, 0 if everything worked out and < 0 if there were major errors. 3256 * 3257 * this will push starting from min_slot to the end of the leaf. It won't 3258 * push any slot lower than min_slot 3259 */ 3260 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 3261 *root, struct btrfs_path *path, 3262 int min_data_size, int data_size, 3263 int empty, u32 min_slot) 3264 { 3265 struct extent_buffer *left = path->nodes[0]; 3266 struct extent_buffer *right; 3267 struct extent_buffer *upper; 3268 int slot; 3269 int free_space; 3270 u32 left_nritems; 3271 int ret; 3272 3273 if (!path->nodes[1]) 3274 return 1; 3275 3276 slot = path->slots[1]; 3277 upper = path->nodes[1]; 3278 if (slot >= btrfs_header_nritems(upper) - 1) 3279 return 1; 3280 3281 btrfs_assert_tree_write_locked(path->nodes[1]); 3282 3283 right = btrfs_read_node_slot(upper, slot + 1); 3284 if (IS_ERR(right)) 3285 return PTR_ERR(right); 3286 3287 __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 3288 3289 free_space = btrfs_leaf_free_space(right); 3290 if (free_space < data_size) 3291 goto out_unlock; 3292 3293 ret = btrfs_cow_block(trans, root, right, upper, 3294 slot + 1, &right, BTRFS_NESTING_RIGHT_COW); 3295 if (ret) 3296 goto out_unlock; 3297 3298 left_nritems = btrfs_header_nritems(left); 3299 if (left_nritems == 0) 3300 goto out_unlock; 3301 3302 if (check_sibling_keys(left, right)) { 3303 ret = -EUCLEAN; 3304 btrfs_abort_transaction(trans, ret); 3305 btrfs_tree_unlock(right); 3306 free_extent_buffer(right); 3307 return ret; 3308 } 3309 if (path->slots[0] == left_nritems && !empty) { 3310 /* Key greater than all keys in the leaf, right neighbor has 3311 * enough room for it and we're not emptying our leaf to delete 3312 * it, therefore use right neighbor to insert the new item and 3313 * no need to touch/dirty our left leaf. */ 3314 btrfs_tree_unlock(left); 3315 free_extent_buffer(left); 3316 path->nodes[0] = right; 3317 path->slots[0] = 0; 3318 path->slots[1]++; 3319 return 0; 3320 } 3321 3322 return __push_leaf_right(trans, path, min_data_size, empty, right, 3323 free_space, left_nritems, min_slot); 3324 out_unlock: 3325 btrfs_tree_unlock(right); 3326 free_extent_buffer(right); 3327 return 1; 3328 } 3329 3330 /* 3331 * push some data in the path leaf to the left, trying to free up at 3332 * least data_size bytes. returns zero if the push worked, nonzero otherwise 3333 * 3334 * max_slot can put a limit on how far into the leaf we'll push items. The 3335 * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the 3336 * items 3337 */ 3338 static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, 3339 struct btrfs_path *path, int data_size, 3340 int empty, struct extent_buffer *left, 3341 int free_space, u32 right_nritems, 3342 u32 max_slot) 3343 { 3344 struct btrfs_fs_info *fs_info = left->fs_info; 3345 struct btrfs_disk_key disk_key; 3346 struct extent_buffer *right = path->nodes[0]; 3347 int i; 3348 int push_space = 0; 3349 int push_items = 0; 3350 u32 old_left_nritems; 3351 u32 nr; 3352 int ret = 0; 3353 u32 this_item_size; 3354 u32 old_left_item_size; 3355 struct btrfs_map_token token; 3356 3357 if (empty) 3358 nr = min(right_nritems, max_slot); 3359 else 3360 nr = min(right_nritems - 1, max_slot); 3361 3362 for (i = 0; i < nr; i++) { 3363 if (!empty && push_items > 0) { 3364 if (path->slots[0] < i) 3365 break; 3366 if (path->slots[0] == i) { 3367 int space = btrfs_leaf_free_space(right); 3368 3369 if (space + push_space * 2 > free_space) 3370 break; 3371 } 3372 } 3373 3374 if (path->slots[0] == i) 3375 push_space += data_size; 3376 3377 this_item_size = btrfs_item_size(right, i); 3378 if (this_item_size + sizeof(struct btrfs_item) + push_space > 3379 free_space) 3380 break; 3381 3382 push_items++; 3383 push_space += this_item_size + sizeof(struct btrfs_item); 3384 } 3385 3386 if (push_items == 0) { 3387 ret = 1; 3388 goto out; 3389 } 3390 WARN_ON(!empty && push_items == btrfs_header_nritems(right)); 3391 3392 /* push data from right to left */ 3393 copy_leaf_items(left, right, btrfs_header_nritems(left), 0, push_items); 3394 3395 push_space = BTRFS_LEAF_DATA_SIZE(fs_info) - 3396 btrfs_item_offset(right, push_items - 1); 3397 3398 copy_leaf_data(left, right, leaf_data_end(left) - push_space, 3399 btrfs_item_offset(right, push_items - 1), push_space); 3400 old_left_nritems = btrfs_header_nritems(left); 3401 BUG_ON(old_left_nritems <= 0); 3402 3403 btrfs_init_map_token(&token, left); 3404 old_left_item_size = btrfs_item_offset(left, old_left_nritems - 1); 3405 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 3406 u32 ioff; 3407 3408 ioff = btrfs_token_item_offset(&token, i); 3409 btrfs_set_token_item_offset(&token, i, 3410 ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size)); 3411 } 3412 btrfs_set_header_nritems(left, old_left_nritems + push_items); 3413 3414 /* fixup right node */ 3415 if (push_items > right_nritems) 3416 WARN(1, KERN_CRIT "push items %d nr %u\n", push_items, 3417 right_nritems); 3418 3419 if (push_items < right_nritems) { 3420 push_space = btrfs_item_offset(right, push_items - 1) - 3421 leaf_data_end(right); 3422 memmove_leaf_data(right, 3423 BTRFS_LEAF_DATA_SIZE(fs_info) - push_space, 3424 leaf_data_end(right), push_space); 3425 3426 memmove_leaf_items(right, 0, push_items, 3427 btrfs_header_nritems(right) - push_items); 3428 } 3429 3430 btrfs_init_map_token(&token, right); 3431 right_nritems -= push_items; 3432 btrfs_set_header_nritems(right, right_nritems); 3433 push_space = BTRFS_LEAF_DATA_SIZE(fs_info); 3434 for (i = 0; i < right_nritems; i++) { 3435 push_space = push_space - btrfs_token_item_size(&token, i); 3436 btrfs_set_token_item_offset(&token, i, push_space); 3437 } 3438 3439 btrfs_mark_buffer_dirty(left); 3440 if (right_nritems) 3441 btrfs_mark_buffer_dirty(right); 3442 else 3443 btrfs_clear_buffer_dirty(trans, right); 3444 3445 btrfs_item_key(right, &disk_key, 0); 3446 fixup_low_keys(path, &disk_key, 1); 3447 3448 /* then fixup the leaf pointer in the path */ 3449 if (path->slots[0] < push_items) { 3450 path->slots[0] += old_left_nritems; 3451 btrfs_tree_unlock(path->nodes[0]); 3452 free_extent_buffer(path->nodes[0]); 3453 path->nodes[0] = left; 3454 path->slots[1] -= 1; 3455 } else { 3456 btrfs_tree_unlock(left); 3457 free_extent_buffer(left); 3458 path->slots[0] -= push_items; 3459 } 3460 BUG_ON(path->slots[0] < 0); 3461 return ret; 3462 out: 3463 btrfs_tree_unlock(left); 3464 free_extent_buffer(left); 3465 return ret; 3466 } 3467 3468 /* 3469 * push some data in the path leaf to the left, trying to free up at 3470 * least data_size bytes. returns zero if the push worked, nonzero otherwise 3471 * 3472 * max_slot can put a limit on how far into the leaf we'll push items. The 3473 * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the 3474 * items 3475 */ 3476 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 3477 *root, struct btrfs_path *path, int min_data_size, 3478 int data_size, int empty, u32 max_slot) 3479 { 3480 struct extent_buffer *right = path->nodes[0]; 3481 struct extent_buffer *left; 3482 int slot; 3483 int free_space; 3484 u32 right_nritems; 3485 int ret = 0; 3486 3487 slot = path->slots[1]; 3488 if (slot == 0) 3489 return 1; 3490 if (!path->nodes[1]) 3491 return 1; 3492 3493 right_nritems = btrfs_header_nritems(right); 3494 if (right_nritems == 0) 3495 return 1; 3496 3497 btrfs_assert_tree_write_locked(path->nodes[1]); 3498 3499 left = btrfs_read_node_slot(path->nodes[1], slot - 1); 3500 if (IS_ERR(left)) 3501 return PTR_ERR(left); 3502 3503 __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 3504 3505 free_space = btrfs_leaf_free_space(left); 3506 if (free_space < data_size) { 3507 ret = 1; 3508 goto out; 3509 } 3510 3511 ret = btrfs_cow_block(trans, root, left, 3512 path->nodes[1], slot - 1, &left, 3513 BTRFS_NESTING_LEFT_COW); 3514 if (ret) { 3515 /* we hit -ENOSPC, but it isn't fatal here */ 3516 if (ret == -ENOSPC) 3517 ret = 1; 3518 goto out; 3519 } 3520 3521 if (check_sibling_keys(left, right)) { 3522 ret = -EUCLEAN; 3523 btrfs_abort_transaction(trans, ret); 3524 goto out; 3525 } 3526 return __push_leaf_left(trans, path, min_data_size, empty, left, 3527 free_space, right_nritems, max_slot); 3528 out: 3529 btrfs_tree_unlock(left); 3530 free_extent_buffer(left); 3531 return ret; 3532 } 3533 3534 /* 3535 * split the path's leaf in two, making sure there is at least data_size 3536 * available for the resulting leaf level of the path. 3537 */ 3538 static noinline void copy_for_split(struct btrfs_trans_handle *trans, 3539 struct btrfs_path *path, 3540 struct extent_buffer *l, 3541 struct extent_buffer *right, 3542 int slot, int mid, int nritems) 3543 { 3544 struct btrfs_fs_info *fs_info = trans->fs_info; 3545 int data_copy_size; 3546 int rt_data_off; 3547 int i; 3548 struct btrfs_disk_key disk_key; 3549 struct btrfs_map_token token; 3550 3551 nritems = nritems - mid; 3552 btrfs_set_header_nritems(right, nritems); 3553 data_copy_size = btrfs_item_data_end(l, mid) - leaf_data_end(l); 3554 3555 copy_leaf_items(right, l, 0, mid, nritems); 3556 3557 copy_leaf_data(right, l, BTRFS_LEAF_DATA_SIZE(fs_info) - data_copy_size, 3558 leaf_data_end(l), data_copy_size); 3559 3560 rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_data_end(l, mid); 3561 3562 btrfs_init_map_token(&token, right); 3563 for (i = 0; i < nritems; i++) { 3564 u32 ioff; 3565 3566 ioff = btrfs_token_item_offset(&token, i); 3567 btrfs_set_token_item_offset(&token, i, ioff + rt_data_off); 3568 } 3569 3570 btrfs_set_header_nritems(l, mid); 3571 btrfs_item_key(right, &disk_key, 0); 3572 insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1); 3573 3574 btrfs_mark_buffer_dirty(right); 3575 btrfs_mark_buffer_dirty(l); 3576 BUG_ON(path->slots[0] != slot); 3577 3578 if (mid <= slot) { 3579 btrfs_tree_unlock(path->nodes[0]); 3580 free_extent_buffer(path->nodes[0]); 3581 path->nodes[0] = right; 3582 path->slots[0] -= mid; 3583 path->slots[1] += 1; 3584 } else { 3585 btrfs_tree_unlock(right); 3586 free_extent_buffer(right); 3587 } 3588 3589 BUG_ON(path->slots[0] < 0); 3590 } 3591 3592 /* 3593 * double splits happen when we need to insert a big item in the middle 3594 * of a leaf. A double split can leave us with 3 mostly empty leaves: 3595 * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ] 3596 * A B C 3597 * 3598 * We avoid this by trying to push the items on either side of our target 3599 * into the adjacent leaves. If all goes well we can avoid the double split 3600 * completely. 3601 */ 3602 static noinline int push_for_double_split(struct btrfs_trans_handle *trans, 3603 struct btrfs_root *root, 3604 struct btrfs_path *path, 3605 int data_size) 3606 { 3607 int ret; 3608 int progress = 0; 3609 int slot; 3610 u32 nritems; 3611 int space_needed = data_size; 3612 3613 slot = path->slots[0]; 3614 if (slot < btrfs_header_nritems(path->nodes[0])) 3615 space_needed -= btrfs_leaf_free_space(path->nodes[0]); 3616 3617 /* 3618 * try to push all the items after our slot into the 3619 * right leaf 3620 */ 3621 ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot); 3622 if (ret < 0) 3623 return ret; 3624 3625 if (ret == 0) 3626 progress++; 3627 3628 nritems = btrfs_header_nritems(path->nodes[0]); 3629 /* 3630 * our goal is to get our slot at the start or end of a leaf. If 3631 * we've done so we're done 3632 */ 3633 if (path->slots[0] == 0 || path->slots[0] == nritems) 3634 return 0; 3635 3636 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) 3637 return 0; 3638 3639 /* try to push all the items before our slot into the next leaf */ 3640 slot = path->slots[0]; 3641 space_needed = data_size; 3642 if (slot > 0) 3643 space_needed -= btrfs_leaf_free_space(path->nodes[0]); 3644 ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot); 3645 if (ret < 0) 3646 return ret; 3647 3648 if (ret == 0) 3649 progress++; 3650 3651 if (progress) 3652 return 0; 3653 return 1; 3654 } 3655 3656 /* 3657 * split the path's leaf in two, making sure there is at least data_size 3658 * available for the resulting leaf level of the path. 3659 * 3660 * returns 0 if all went well and < 0 on failure. 3661 */ 3662 static noinline int split_leaf(struct btrfs_trans_handle *trans, 3663 struct btrfs_root *root, 3664 const struct btrfs_key *ins_key, 3665 struct btrfs_path *path, int data_size, 3666 int extend) 3667 { 3668 struct btrfs_disk_key disk_key; 3669 struct extent_buffer *l; 3670 u32 nritems; 3671 int mid; 3672 int slot; 3673 struct extent_buffer *right; 3674 struct btrfs_fs_info *fs_info = root->fs_info; 3675 int ret = 0; 3676 int wret; 3677 int split; 3678 int num_doubles = 0; 3679 int tried_avoid_double = 0; 3680 3681 l = path->nodes[0]; 3682 slot = path->slots[0]; 3683 if (extend && data_size + btrfs_item_size(l, slot) + 3684 sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info)) 3685 return -EOVERFLOW; 3686 3687 /* first try to make some room by pushing left and right */ 3688 if (data_size && path->nodes[1]) { 3689 int space_needed = data_size; 3690 3691 if (slot < btrfs_header_nritems(l)) 3692 space_needed -= btrfs_leaf_free_space(l); 3693 3694 wret = push_leaf_right(trans, root, path, space_needed, 3695 space_needed, 0, 0); 3696 if (wret < 0) 3697 return wret; 3698 if (wret) { 3699 space_needed = data_size; 3700 if (slot > 0) 3701 space_needed -= btrfs_leaf_free_space(l); 3702 wret = push_leaf_left(trans, root, path, space_needed, 3703 space_needed, 0, (u32)-1); 3704 if (wret < 0) 3705 return wret; 3706 } 3707 l = path->nodes[0]; 3708 3709 /* did the pushes work? */ 3710 if (btrfs_leaf_free_space(l) >= data_size) 3711 return 0; 3712 } 3713 3714 if (!path->nodes[1]) { 3715 ret = insert_new_root(trans, root, path, 1); 3716 if (ret) 3717 return ret; 3718 } 3719 again: 3720 split = 1; 3721 l = path->nodes[0]; 3722 slot = path->slots[0]; 3723 nritems = btrfs_header_nritems(l); 3724 mid = (nritems + 1) / 2; 3725 3726 if (mid <= slot) { 3727 if (nritems == 1 || 3728 leaf_space_used(l, mid, nritems - mid) + data_size > 3729 BTRFS_LEAF_DATA_SIZE(fs_info)) { 3730 if (slot >= nritems) { 3731 split = 0; 3732 } else { 3733 mid = slot; 3734 if (mid != nritems && 3735 leaf_space_used(l, mid, nritems - mid) + 3736 data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) { 3737 if (data_size && !tried_avoid_double) 3738 goto push_for_double; 3739 split = 2; 3740 } 3741 } 3742 } 3743 } else { 3744 if (leaf_space_used(l, 0, mid) + data_size > 3745 BTRFS_LEAF_DATA_SIZE(fs_info)) { 3746 if (!extend && data_size && slot == 0) { 3747 split = 0; 3748 } else if ((extend || !data_size) && slot == 0) { 3749 mid = 1; 3750 } else { 3751 mid = slot; 3752 if (mid != nritems && 3753 leaf_space_used(l, mid, nritems - mid) + 3754 data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) { 3755 if (data_size && !tried_avoid_double) 3756 goto push_for_double; 3757 split = 2; 3758 } 3759 } 3760 } 3761 } 3762 3763 if (split == 0) 3764 btrfs_cpu_key_to_disk(&disk_key, ins_key); 3765 else 3766 btrfs_item_key(l, &disk_key, mid); 3767 3768 /* 3769 * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double 3770 * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES 3771 * subclasses, which is 8 at the time of this patch, and we've maxed it 3772 * out. In the future we could add a 3773 * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just 3774 * use BTRFS_NESTING_NEW_ROOT. 3775 */ 3776 right = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 3777 &disk_key, 0, l->start, 0, 3778 num_doubles ? BTRFS_NESTING_NEW_ROOT : 3779 BTRFS_NESTING_SPLIT); 3780 if (IS_ERR(right)) 3781 return PTR_ERR(right); 3782 3783 root_add_used(root, fs_info->nodesize); 3784 3785 if (split == 0) { 3786 if (mid <= slot) { 3787 btrfs_set_header_nritems(right, 0); 3788 insert_ptr(trans, path, &disk_key, 3789 right->start, path->slots[1] + 1, 1); 3790 btrfs_tree_unlock(path->nodes[0]); 3791 free_extent_buffer(path->nodes[0]); 3792 path->nodes[0] = right; 3793 path->slots[0] = 0; 3794 path->slots[1] += 1; 3795 } else { 3796 btrfs_set_header_nritems(right, 0); 3797 insert_ptr(trans, path, &disk_key, 3798 right->start, path->slots[1], 1); 3799 btrfs_tree_unlock(path->nodes[0]); 3800 free_extent_buffer(path->nodes[0]); 3801 path->nodes[0] = right; 3802 path->slots[0] = 0; 3803 if (path->slots[1] == 0) 3804 fixup_low_keys(path, &disk_key, 1); 3805 } 3806 /* 3807 * We create a new leaf 'right' for the required ins_len and 3808 * we'll do btrfs_mark_buffer_dirty() on this leaf after copying 3809 * the content of ins_len to 'right'. 3810 */ 3811 return ret; 3812 } 3813 3814 copy_for_split(trans, path, l, right, slot, mid, nritems); 3815 3816 if (split == 2) { 3817 BUG_ON(num_doubles != 0); 3818 num_doubles++; 3819 goto again; 3820 } 3821 3822 return 0; 3823 3824 push_for_double: 3825 push_for_double_split(trans, root, path, data_size); 3826 tried_avoid_double = 1; 3827 if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) 3828 return 0; 3829 goto again; 3830 } 3831 3832 static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3833 struct btrfs_root *root, 3834 struct btrfs_path *path, int ins_len) 3835 { 3836 struct btrfs_key key; 3837 struct extent_buffer *leaf; 3838 struct btrfs_file_extent_item *fi; 3839 u64 extent_len = 0; 3840 u32 item_size; 3841 int ret; 3842 3843 leaf = path->nodes[0]; 3844 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 3845 3846 BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY && 3847 key.type != BTRFS_EXTENT_CSUM_KEY); 3848 3849 if (btrfs_leaf_free_space(leaf) >= ins_len) 3850 return 0; 3851 3852 item_size = btrfs_item_size(leaf, path->slots[0]); 3853 if (key.type == BTRFS_EXTENT_DATA_KEY) { 3854 fi = btrfs_item_ptr(leaf, path->slots[0], 3855 struct btrfs_file_extent_item); 3856 extent_len = btrfs_file_extent_num_bytes(leaf, fi); 3857 } 3858 btrfs_release_path(path); 3859 3860 path->keep_locks = 1; 3861 path->search_for_split = 1; 3862 ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 3863 path->search_for_split = 0; 3864 if (ret > 0) 3865 ret = -EAGAIN; 3866 if (ret < 0) 3867 goto err; 3868 3869 ret = -EAGAIN; 3870 leaf = path->nodes[0]; 3871 /* if our item isn't there, return now */ 3872 if (item_size != btrfs_item_size(leaf, path->slots[0])) 3873 goto err; 3874 3875 /* the leaf has changed, it now has room. return now */ 3876 if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len) 3877 goto err; 3878 3879 if (key.type == BTRFS_EXTENT_DATA_KEY) { 3880 fi = btrfs_item_ptr(leaf, path->slots[0], 3881 struct btrfs_file_extent_item); 3882 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) 3883 goto err; 3884 } 3885 3886 ret = split_leaf(trans, root, &key, path, ins_len, 1); 3887 if (ret) 3888 goto err; 3889 3890 path->keep_locks = 0; 3891 btrfs_unlock_up_safe(path, 1); 3892 return 0; 3893 err: 3894 path->keep_locks = 0; 3895 return ret; 3896 } 3897 3898 static noinline int split_item(struct btrfs_path *path, 3899 const struct btrfs_key *new_key, 3900 unsigned long split_offset) 3901 { 3902 struct extent_buffer *leaf; 3903 int orig_slot, slot; 3904 char *buf; 3905 u32 nritems; 3906 u32 item_size; 3907 u32 orig_offset; 3908 struct btrfs_disk_key disk_key; 3909 3910 leaf = path->nodes[0]; 3911 BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)); 3912 3913 orig_slot = path->slots[0]; 3914 orig_offset = btrfs_item_offset(leaf, path->slots[0]); 3915 item_size = btrfs_item_size(leaf, path->slots[0]); 3916 3917 buf = kmalloc(item_size, GFP_NOFS); 3918 if (!buf) 3919 return -ENOMEM; 3920 3921 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3922 path->slots[0]), item_size); 3923 3924 slot = path->slots[0] + 1; 3925 nritems = btrfs_header_nritems(leaf); 3926 if (slot != nritems) { 3927 /* shift the items */ 3928 memmove_leaf_items(leaf, slot + 1, slot, nritems - slot); 3929 } 3930 3931 btrfs_cpu_key_to_disk(&disk_key, new_key); 3932 btrfs_set_item_key(leaf, &disk_key, slot); 3933 3934 btrfs_set_item_offset(leaf, slot, orig_offset); 3935 btrfs_set_item_size(leaf, slot, item_size - split_offset); 3936 3937 btrfs_set_item_offset(leaf, orig_slot, 3938 orig_offset + item_size - split_offset); 3939 btrfs_set_item_size(leaf, orig_slot, split_offset); 3940 3941 btrfs_set_header_nritems(leaf, nritems + 1); 3942 3943 /* write the data for the start of the original item */ 3944 write_extent_buffer(leaf, buf, 3945 btrfs_item_ptr_offset(leaf, path->slots[0]), 3946 split_offset); 3947 3948 /* write the data for the new item */ 3949 write_extent_buffer(leaf, buf + split_offset, 3950 btrfs_item_ptr_offset(leaf, slot), 3951 item_size - split_offset); 3952 btrfs_mark_buffer_dirty(leaf); 3953 3954 BUG_ON(btrfs_leaf_free_space(leaf) < 0); 3955 kfree(buf); 3956 return 0; 3957 } 3958 3959 /* 3960 * This function splits a single item into two items, 3961 * giving 'new_key' to the new item and splitting the 3962 * old one at split_offset (from the start of the item). 3963 * 3964 * The path may be released by this operation. After 3965 * the split, the path is pointing to the old item. The 3966 * new item is going to be in the same node as the old one. 3967 * 3968 * Note, the item being split must be smaller enough to live alone on 3969 * a tree block with room for one extra struct btrfs_item 3970 * 3971 * This allows us to split the item in place, keeping a lock on the 3972 * leaf the entire time. 3973 */ 3974 int btrfs_split_item(struct btrfs_trans_handle *trans, 3975 struct btrfs_root *root, 3976 struct btrfs_path *path, 3977 const struct btrfs_key *new_key, 3978 unsigned long split_offset) 3979 { 3980 int ret; 3981 ret = setup_leaf_for_split(trans, root, path, 3982 sizeof(struct btrfs_item)); 3983 if (ret) 3984 return ret; 3985 3986 ret = split_item(path, new_key, split_offset); 3987 return ret; 3988 } 3989 3990 /* 3991 * make the item pointed to by the path smaller. new_size indicates 3992 * how small to make it, and from_end tells us if we just chop bytes 3993 * off the end of the item or if we shift the item to chop bytes off 3994 * the front. 3995 */ 3996 void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end) 3997 { 3998 int slot; 3999 struct extent_buffer *leaf; 4000 u32 nritems; 4001 unsigned int data_end; 4002 unsigned int old_data_start; 4003 unsigned int old_size; 4004 unsigned int size_diff; 4005 int i; 4006 struct btrfs_map_token token; 4007 4008 leaf = path->nodes[0]; 4009 slot = path->slots[0]; 4010 4011 old_size = btrfs_item_size(leaf, slot); 4012 if (old_size == new_size) 4013 return; 4014 4015 nritems = btrfs_header_nritems(leaf); 4016 data_end = leaf_data_end(leaf); 4017 4018 old_data_start = btrfs_item_offset(leaf, slot); 4019 4020 size_diff = old_size - new_size; 4021 4022 BUG_ON(slot < 0); 4023 BUG_ON(slot >= nritems); 4024 4025 /* 4026 * item0..itemN ... dataN.offset..dataN.size .. data0.size 4027 */ 4028 /* first correct the data pointers */ 4029 btrfs_init_map_token(&token, leaf); 4030 for (i = slot; i < nritems; i++) { 4031 u32 ioff; 4032 4033 ioff = btrfs_token_item_offset(&token, i); 4034 btrfs_set_token_item_offset(&token, i, ioff + size_diff); 4035 } 4036 4037 /* shift the data */ 4038 if (from_end) { 4039 memmove_leaf_data(leaf, data_end + size_diff, data_end, 4040 old_data_start + new_size - data_end); 4041 } else { 4042 struct btrfs_disk_key disk_key; 4043 u64 offset; 4044 4045 btrfs_item_key(leaf, &disk_key, slot); 4046 4047 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 4048 unsigned long ptr; 4049 struct btrfs_file_extent_item *fi; 4050 4051 fi = btrfs_item_ptr(leaf, slot, 4052 struct btrfs_file_extent_item); 4053 fi = (struct btrfs_file_extent_item *)( 4054 (unsigned long)fi - size_diff); 4055 4056 if (btrfs_file_extent_type(leaf, fi) == 4057 BTRFS_FILE_EXTENT_INLINE) { 4058 ptr = btrfs_item_ptr_offset(leaf, slot); 4059 memmove_extent_buffer(leaf, ptr, 4060 (unsigned long)fi, 4061 BTRFS_FILE_EXTENT_INLINE_DATA_START); 4062 } 4063 } 4064 4065 memmove_leaf_data(leaf, data_end + size_diff, data_end, 4066 old_data_start - data_end); 4067 4068 offset = btrfs_disk_key_offset(&disk_key); 4069 btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 4070 btrfs_set_item_key(leaf, &disk_key, slot); 4071 if (slot == 0) 4072 fixup_low_keys(path, &disk_key, 1); 4073 } 4074 4075 btrfs_set_item_size(leaf, slot, new_size); 4076 btrfs_mark_buffer_dirty(leaf); 4077 4078 if (btrfs_leaf_free_space(leaf) < 0) { 4079 btrfs_print_leaf(leaf); 4080 BUG(); 4081 } 4082 } 4083 4084 /* 4085 * make the item pointed to by the path bigger, data_size is the added size. 4086 */ 4087 void btrfs_extend_item(struct btrfs_path *path, u32 data_size) 4088 { 4089 int slot; 4090 struct extent_buffer *leaf; 4091 u32 nritems; 4092 unsigned int data_end; 4093 unsigned int old_data; 4094 unsigned int old_size; 4095 int i; 4096 struct btrfs_map_token token; 4097 4098 leaf = path->nodes[0]; 4099 4100 nritems = btrfs_header_nritems(leaf); 4101 data_end = leaf_data_end(leaf); 4102 4103 if (btrfs_leaf_free_space(leaf) < data_size) { 4104 btrfs_print_leaf(leaf); 4105 BUG(); 4106 } 4107 slot = path->slots[0]; 4108 old_data = btrfs_item_data_end(leaf, slot); 4109 4110 BUG_ON(slot < 0); 4111 if (slot >= nritems) { 4112 btrfs_print_leaf(leaf); 4113 btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", 4114 slot, nritems); 4115 BUG(); 4116 } 4117 4118 /* 4119 * item0..itemN ... dataN.offset..dataN.size .. data0.size 4120 */ 4121 /* first correct the data pointers */ 4122 btrfs_init_map_token(&token, leaf); 4123 for (i = slot; i < nritems; i++) { 4124 u32 ioff; 4125 4126 ioff = btrfs_token_item_offset(&token, i); 4127 btrfs_set_token_item_offset(&token, i, ioff - data_size); 4128 } 4129 4130 /* shift the data */ 4131 memmove_leaf_data(leaf, data_end - data_size, data_end, 4132 old_data - data_end); 4133 4134 data_end = old_data; 4135 old_size = btrfs_item_size(leaf, slot); 4136 btrfs_set_item_size(leaf, slot, old_size + data_size); 4137 btrfs_mark_buffer_dirty(leaf); 4138 4139 if (btrfs_leaf_free_space(leaf) < 0) { 4140 btrfs_print_leaf(leaf); 4141 BUG(); 4142 } 4143 } 4144 4145 /* 4146 * Make space in the node before inserting one or more items. 4147 * 4148 * @root: root we are inserting items to 4149 * @path: points to the leaf/slot where we are going to insert new items 4150 * @batch: information about the batch of items to insert 4151 * 4152 * Main purpose is to save stack depth by doing the bulk of the work in a 4153 * function that doesn't call btrfs_search_slot 4154 */ 4155 static void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path, 4156 const struct btrfs_item_batch *batch) 4157 { 4158 struct btrfs_fs_info *fs_info = root->fs_info; 4159 int i; 4160 u32 nritems; 4161 unsigned int data_end; 4162 struct btrfs_disk_key disk_key; 4163 struct extent_buffer *leaf; 4164 int slot; 4165 struct btrfs_map_token token; 4166 u32 total_size; 4167 4168 /* 4169 * Before anything else, update keys in the parent and other ancestors 4170 * if needed, then release the write locks on them, so that other tasks 4171 * can use them while we modify the leaf. 4172 */ 4173 if (path->slots[0] == 0) { 4174 btrfs_cpu_key_to_disk(&disk_key, &batch->keys[0]); 4175 fixup_low_keys(path, &disk_key, 1); 4176 } 4177 btrfs_unlock_up_safe(path, 1); 4178 4179 leaf = path->nodes[0]; 4180 slot = path->slots[0]; 4181 4182 nritems = btrfs_header_nritems(leaf); 4183 data_end = leaf_data_end(leaf); 4184 total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item)); 4185 4186 if (btrfs_leaf_free_space(leaf) < total_size) { 4187 btrfs_print_leaf(leaf); 4188 btrfs_crit(fs_info, "not enough freespace need %u have %d", 4189 total_size, btrfs_leaf_free_space(leaf)); 4190 BUG(); 4191 } 4192 4193 btrfs_init_map_token(&token, leaf); 4194 if (slot != nritems) { 4195 unsigned int old_data = btrfs_item_data_end(leaf, slot); 4196 4197 if (old_data < data_end) { 4198 btrfs_print_leaf(leaf); 4199 btrfs_crit(fs_info, 4200 "item at slot %d with data offset %u beyond data end of leaf %u", 4201 slot, old_data, data_end); 4202 BUG(); 4203 } 4204 /* 4205 * item0..itemN ... dataN.offset..dataN.size .. data0.size 4206 */ 4207 /* first correct the data pointers */ 4208 for (i = slot; i < nritems; i++) { 4209 u32 ioff; 4210 4211 ioff = btrfs_token_item_offset(&token, i); 4212 btrfs_set_token_item_offset(&token, i, 4213 ioff - batch->total_data_size); 4214 } 4215 /* shift the items */ 4216 memmove_leaf_items(leaf, slot + batch->nr, slot, nritems - slot); 4217 4218 /* shift the data */ 4219 memmove_leaf_data(leaf, data_end - batch->total_data_size, 4220 data_end, old_data - data_end); 4221 data_end = old_data; 4222 } 4223 4224 /* setup the item for the new data */ 4225 for (i = 0; i < batch->nr; i++) { 4226 btrfs_cpu_key_to_disk(&disk_key, &batch->keys[i]); 4227 btrfs_set_item_key(leaf, &disk_key, slot + i); 4228 data_end -= batch->data_sizes[i]; 4229 btrfs_set_token_item_offset(&token, slot + i, data_end); 4230 btrfs_set_token_item_size(&token, slot + i, batch->data_sizes[i]); 4231 } 4232 4233 btrfs_set_header_nritems(leaf, nritems + batch->nr); 4234 btrfs_mark_buffer_dirty(leaf); 4235 4236 if (btrfs_leaf_free_space(leaf) < 0) { 4237 btrfs_print_leaf(leaf); 4238 BUG(); 4239 } 4240 } 4241 4242 /* 4243 * Insert a new item into a leaf. 4244 * 4245 * @root: The root of the btree. 4246 * @path: A path pointing to the target leaf and slot. 4247 * @key: The key of the new item. 4248 * @data_size: The size of the data associated with the new key. 4249 */ 4250 void btrfs_setup_item_for_insert(struct btrfs_root *root, 4251 struct btrfs_path *path, 4252 const struct btrfs_key *key, 4253 u32 data_size) 4254 { 4255 struct btrfs_item_batch batch; 4256 4257 batch.keys = key; 4258 batch.data_sizes = &data_size; 4259 batch.total_data_size = data_size; 4260 batch.nr = 1; 4261 4262 setup_items_for_insert(root, path, &batch); 4263 } 4264 4265 /* 4266 * Given a key and some data, insert items into the tree. 4267 * This does all the path init required, making room in the tree if needed. 4268 */ 4269 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 4270 struct btrfs_root *root, 4271 struct btrfs_path *path, 4272 const struct btrfs_item_batch *batch) 4273 { 4274 int ret = 0; 4275 int slot; 4276 u32 total_size; 4277 4278 total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item)); 4279 ret = btrfs_search_slot(trans, root, &batch->keys[0], path, total_size, 1); 4280 if (ret == 0) 4281 return -EEXIST; 4282 if (ret < 0) 4283 return ret; 4284 4285 slot = path->slots[0]; 4286 BUG_ON(slot < 0); 4287 4288 setup_items_for_insert(root, path, batch); 4289 return 0; 4290 } 4291 4292 /* 4293 * Given a key and some data, insert an item into the tree. 4294 * This does all the path init required, making room in the tree if needed. 4295 */ 4296 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 4297 const struct btrfs_key *cpu_key, void *data, 4298 u32 data_size) 4299 { 4300 int ret = 0; 4301 struct btrfs_path *path; 4302 struct extent_buffer *leaf; 4303 unsigned long ptr; 4304 4305 path = btrfs_alloc_path(); 4306 if (!path) 4307 return -ENOMEM; 4308 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 4309 if (!ret) { 4310 leaf = path->nodes[0]; 4311 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 4312 write_extent_buffer(leaf, data, ptr, data_size); 4313 btrfs_mark_buffer_dirty(leaf); 4314 } 4315 btrfs_free_path(path); 4316 return ret; 4317 } 4318 4319 /* 4320 * This function duplicates an item, giving 'new_key' to the new item. 4321 * It guarantees both items live in the same tree leaf and the new item is 4322 * contiguous with the original item. 4323 * 4324 * This allows us to split a file extent in place, keeping a lock on the leaf 4325 * the entire time. 4326 */ 4327 int btrfs_duplicate_item(struct btrfs_trans_handle *trans, 4328 struct btrfs_root *root, 4329 struct btrfs_path *path, 4330 const struct btrfs_key *new_key) 4331 { 4332 struct extent_buffer *leaf; 4333 int ret; 4334 u32 item_size; 4335 4336 leaf = path->nodes[0]; 4337 item_size = btrfs_item_size(leaf, path->slots[0]); 4338 ret = setup_leaf_for_split(trans, root, path, 4339 item_size + sizeof(struct btrfs_item)); 4340 if (ret) 4341 return ret; 4342 4343 path->slots[0]++; 4344 btrfs_setup_item_for_insert(root, path, new_key, item_size); 4345 leaf = path->nodes[0]; 4346 memcpy_extent_buffer(leaf, 4347 btrfs_item_ptr_offset(leaf, path->slots[0]), 4348 btrfs_item_ptr_offset(leaf, path->slots[0] - 1), 4349 item_size); 4350 return 0; 4351 } 4352 4353 /* 4354 * delete the pointer from a given node. 4355 * 4356 * the tree should have been previously balanced so the deletion does not 4357 * empty a node. 4358 * 4359 * This is exported for use inside btrfs-progs, don't un-export it. 4360 */ 4361 void btrfs_del_ptr(struct btrfs_root *root, struct btrfs_path *path, int level, 4362 int slot) 4363 { 4364 struct extent_buffer *parent = path->nodes[level]; 4365 u32 nritems; 4366 int ret; 4367 4368 nritems = btrfs_header_nritems(parent); 4369 if (slot != nritems - 1) { 4370 if (level) { 4371 ret = btrfs_tree_mod_log_insert_move(parent, slot, 4372 slot + 1, nritems - slot - 1); 4373 BUG_ON(ret < 0); 4374 } 4375 memmove_extent_buffer(parent, 4376 btrfs_node_key_ptr_offset(parent, slot), 4377 btrfs_node_key_ptr_offset(parent, slot + 1), 4378 sizeof(struct btrfs_key_ptr) * 4379 (nritems - slot - 1)); 4380 } else if (level) { 4381 ret = btrfs_tree_mod_log_insert_key(parent, slot, 4382 BTRFS_MOD_LOG_KEY_REMOVE); 4383 BUG_ON(ret < 0); 4384 } 4385 4386 nritems--; 4387 btrfs_set_header_nritems(parent, nritems); 4388 if (nritems == 0 && parent == root->node) { 4389 BUG_ON(btrfs_header_level(root->node) != 1); 4390 /* just turn the root into a leaf and break */ 4391 btrfs_set_header_level(root->node, 0); 4392 } else if (slot == 0) { 4393 struct btrfs_disk_key disk_key; 4394 4395 btrfs_node_key(parent, &disk_key, 0); 4396 fixup_low_keys(path, &disk_key, level + 1); 4397 } 4398 btrfs_mark_buffer_dirty(parent); 4399 } 4400 4401 /* 4402 * a helper function to delete the leaf pointed to by path->slots[1] and 4403 * path->nodes[1]. 4404 * 4405 * This deletes the pointer in path->nodes[1] and frees the leaf 4406 * block extent. zero is returned if it all worked out, < 0 otherwise. 4407 * 4408 * The path must have already been setup for deleting the leaf, including 4409 * all the proper balancing. path->nodes[1] must be locked. 4410 */ 4411 static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans, 4412 struct btrfs_root *root, 4413 struct btrfs_path *path, 4414 struct extent_buffer *leaf) 4415 { 4416 WARN_ON(btrfs_header_generation(leaf) != trans->transid); 4417 btrfs_del_ptr(root, path, 1, path->slots[1]); 4418 4419 /* 4420 * btrfs_free_extent is expensive, we want to make sure we 4421 * aren't holding any locks when we call it 4422 */ 4423 btrfs_unlock_up_safe(path, 0); 4424 4425 root_sub_used(root, leaf->len); 4426 4427 atomic_inc(&leaf->refs); 4428 btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1); 4429 free_extent_buffer_stale(leaf); 4430 } 4431 /* 4432 * delete the item at the leaf level in path. If that empties 4433 * the leaf, remove it from the tree 4434 */ 4435 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 4436 struct btrfs_path *path, int slot, int nr) 4437 { 4438 struct btrfs_fs_info *fs_info = root->fs_info; 4439 struct extent_buffer *leaf; 4440 int ret = 0; 4441 int wret; 4442 u32 nritems; 4443 4444 leaf = path->nodes[0]; 4445 nritems = btrfs_header_nritems(leaf); 4446 4447 if (slot + nr != nritems) { 4448 const u32 last_off = btrfs_item_offset(leaf, slot + nr - 1); 4449 const int data_end = leaf_data_end(leaf); 4450 struct btrfs_map_token token; 4451 u32 dsize = 0; 4452 int i; 4453 4454 for (i = 0; i < nr; i++) 4455 dsize += btrfs_item_size(leaf, slot + i); 4456 4457 memmove_leaf_data(leaf, data_end + dsize, data_end, 4458 last_off - data_end); 4459 4460 btrfs_init_map_token(&token, leaf); 4461 for (i = slot + nr; i < nritems; i++) { 4462 u32 ioff; 4463 4464 ioff = btrfs_token_item_offset(&token, i); 4465 btrfs_set_token_item_offset(&token, i, ioff + dsize); 4466 } 4467 4468 memmove_leaf_items(leaf, slot, slot + nr, nritems - slot - nr); 4469 } 4470 btrfs_set_header_nritems(leaf, nritems - nr); 4471 nritems -= nr; 4472 4473 /* delete the leaf if we've emptied it */ 4474 if (nritems == 0) { 4475 if (leaf == root->node) { 4476 btrfs_set_header_level(leaf, 0); 4477 } else { 4478 btrfs_clear_buffer_dirty(trans, leaf); 4479 btrfs_del_leaf(trans, root, path, leaf); 4480 } 4481 } else { 4482 int used = leaf_space_used(leaf, 0, nritems); 4483 if (slot == 0) { 4484 struct btrfs_disk_key disk_key; 4485 4486 btrfs_item_key(leaf, &disk_key, 0); 4487 fixup_low_keys(path, &disk_key, 1); 4488 } 4489 4490 /* 4491 * Try to delete the leaf if it is mostly empty. We do this by 4492 * trying to move all its items into its left and right neighbours. 4493 * If we can't move all the items, then we don't delete it - it's 4494 * not ideal, but future insertions might fill the leaf with more 4495 * items, or items from other leaves might be moved later into our 4496 * leaf due to deletions on those leaves. 4497 */ 4498 if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) { 4499 u32 min_push_space; 4500 4501 /* push_leaf_left fixes the path. 4502 * make sure the path still points to our leaf 4503 * for possible call to btrfs_del_ptr below 4504 */ 4505 slot = path->slots[1]; 4506 atomic_inc(&leaf->refs); 4507 /* 4508 * We want to be able to at least push one item to the 4509 * left neighbour leaf, and that's the first item. 4510 */ 4511 min_push_space = sizeof(struct btrfs_item) + 4512 btrfs_item_size(leaf, 0); 4513 wret = push_leaf_left(trans, root, path, 0, 4514 min_push_space, 1, (u32)-1); 4515 if (wret < 0 && wret != -ENOSPC) 4516 ret = wret; 4517 4518 if (path->nodes[0] == leaf && 4519 btrfs_header_nritems(leaf)) { 4520 /* 4521 * If we were not able to push all items from our 4522 * leaf to its left neighbour, then attempt to 4523 * either push all the remaining items to the 4524 * right neighbour or none. There's no advantage 4525 * in pushing only some items, instead of all, as 4526 * it's pointless to end up with a leaf having 4527 * too few items while the neighbours can be full 4528 * or nearly full. 4529 */ 4530 nritems = btrfs_header_nritems(leaf); 4531 min_push_space = leaf_space_used(leaf, 0, nritems); 4532 wret = push_leaf_right(trans, root, path, 0, 4533 min_push_space, 1, 0); 4534 if (wret < 0 && wret != -ENOSPC) 4535 ret = wret; 4536 } 4537 4538 if (btrfs_header_nritems(leaf) == 0) { 4539 path->slots[1] = slot; 4540 btrfs_del_leaf(trans, root, path, leaf); 4541 free_extent_buffer(leaf); 4542 ret = 0; 4543 } else { 4544 /* if we're still in the path, make sure 4545 * we're dirty. Otherwise, one of the 4546 * push_leaf functions must have already 4547 * dirtied this buffer 4548 */ 4549 if (path->nodes[0] == leaf) 4550 btrfs_mark_buffer_dirty(leaf); 4551 free_extent_buffer(leaf); 4552 } 4553 } else { 4554 btrfs_mark_buffer_dirty(leaf); 4555 } 4556 } 4557 return ret; 4558 } 4559 4560 /* 4561 * A helper function to walk down the tree starting at min_key, and looking 4562 * for nodes or leaves that are have a minimum transaction id. 4563 * This is used by the btree defrag code, and tree logging 4564 * 4565 * This does not cow, but it does stuff the starting key it finds back 4566 * into min_key, so you can call btrfs_search_slot with cow=1 on the 4567 * key and get a writable path. 4568 * 4569 * This honors path->lowest_level to prevent descent past a given level 4570 * of the tree. 4571 * 4572 * min_trans indicates the oldest transaction that you are interested 4573 * in walking through. Any nodes or leaves older than min_trans are 4574 * skipped over (without reading them). 4575 * 4576 * returns zero if something useful was found, < 0 on error and 1 if there 4577 * was nothing in the tree that matched the search criteria. 4578 */ 4579 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 4580 struct btrfs_path *path, 4581 u64 min_trans) 4582 { 4583 struct extent_buffer *cur; 4584 struct btrfs_key found_key; 4585 int slot; 4586 int sret; 4587 u32 nritems; 4588 int level; 4589 int ret = 1; 4590 int keep_locks = path->keep_locks; 4591 4592 ASSERT(!path->nowait); 4593 path->keep_locks = 1; 4594 again: 4595 cur = btrfs_read_lock_root_node(root); 4596 level = btrfs_header_level(cur); 4597 WARN_ON(path->nodes[level]); 4598 path->nodes[level] = cur; 4599 path->locks[level] = BTRFS_READ_LOCK; 4600 4601 if (btrfs_header_generation(cur) < min_trans) { 4602 ret = 1; 4603 goto out; 4604 } 4605 while (1) { 4606 nritems = btrfs_header_nritems(cur); 4607 level = btrfs_header_level(cur); 4608 sret = btrfs_bin_search(cur, 0, min_key, &slot); 4609 if (sret < 0) { 4610 ret = sret; 4611 goto out; 4612 } 4613 4614 /* at the lowest level, we're done, setup the path and exit */ 4615 if (level == path->lowest_level) { 4616 if (slot >= nritems) 4617 goto find_next_key; 4618 ret = 0; 4619 path->slots[level] = slot; 4620 btrfs_item_key_to_cpu(cur, &found_key, slot); 4621 goto out; 4622 } 4623 if (sret && slot > 0) 4624 slot--; 4625 /* 4626 * check this node pointer against the min_trans parameters. 4627 * If it is too old, skip to the next one. 4628 */ 4629 while (slot < nritems) { 4630 u64 gen; 4631 4632 gen = btrfs_node_ptr_generation(cur, slot); 4633 if (gen < min_trans) { 4634 slot++; 4635 continue; 4636 } 4637 break; 4638 } 4639 find_next_key: 4640 /* 4641 * we didn't find a candidate key in this node, walk forward 4642 * and find another one 4643 */ 4644 if (slot >= nritems) { 4645 path->slots[level] = slot; 4646 sret = btrfs_find_next_key(root, path, min_key, level, 4647 min_trans); 4648 if (sret == 0) { 4649 btrfs_release_path(path); 4650 goto again; 4651 } else { 4652 goto out; 4653 } 4654 } 4655 /* save our key for returning back */ 4656 btrfs_node_key_to_cpu(cur, &found_key, slot); 4657 path->slots[level] = slot; 4658 if (level == path->lowest_level) { 4659 ret = 0; 4660 goto out; 4661 } 4662 cur = btrfs_read_node_slot(cur, slot); 4663 if (IS_ERR(cur)) { 4664 ret = PTR_ERR(cur); 4665 goto out; 4666 } 4667 4668 btrfs_tree_read_lock(cur); 4669 4670 path->locks[level - 1] = BTRFS_READ_LOCK; 4671 path->nodes[level - 1] = cur; 4672 unlock_up(path, level, 1, 0, NULL); 4673 } 4674 out: 4675 path->keep_locks = keep_locks; 4676 if (ret == 0) { 4677 btrfs_unlock_up_safe(path, path->lowest_level + 1); 4678 memcpy(min_key, &found_key, sizeof(found_key)); 4679 } 4680 return ret; 4681 } 4682 4683 /* 4684 * this is similar to btrfs_next_leaf, but does not try to preserve 4685 * and fixup the path. It looks for and returns the next key in the 4686 * tree based on the current path and the min_trans parameters. 4687 * 4688 * 0 is returned if another key is found, < 0 if there are any errors 4689 * and 1 is returned if there are no higher keys in the tree 4690 * 4691 * path->keep_locks should be set to 1 on the search made before 4692 * calling this function. 4693 */ 4694 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 4695 struct btrfs_key *key, int level, u64 min_trans) 4696 { 4697 int slot; 4698 struct extent_buffer *c; 4699 4700 WARN_ON(!path->keep_locks && !path->skip_locking); 4701 while (level < BTRFS_MAX_LEVEL) { 4702 if (!path->nodes[level]) 4703 return 1; 4704 4705 slot = path->slots[level] + 1; 4706 c = path->nodes[level]; 4707 next: 4708 if (slot >= btrfs_header_nritems(c)) { 4709 int ret; 4710 int orig_lowest; 4711 struct btrfs_key cur_key; 4712 if (level + 1 >= BTRFS_MAX_LEVEL || 4713 !path->nodes[level + 1]) 4714 return 1; 4715 4716 if (path->locks[level + 1] || path->skip_locking) { 4717 level++; 4718 continue; 4719 } 4720 4721 slot = btrfs_header_nritems(c) - 1; 4722 if (level == 0) 4723 btrfs_item_key_to_cpu(c, &cur_key, slot); 4724 else 4725 btrfs_node_key_to_cpu(c, &cur_key, slot); 4726 4727 orig_lowest = path->lowest_level; 4728 btrfs_release_path(path); 4729 path->lowest_level = level; 4730 ret = btrfs_search_slot(NULL, root, &cur_key, path, 4731 0, 0); 4732 path->lowest_level = orig_lowest; 4733 if (ret < 0) 4734 return ret; 4735 4736 c = path->nodes[level]; 4737 slot = path->slots[level]; 4738 if (ret == 0) 4739 slot++; 4740 goto next; 4741 } 4742 4743 if (level == 0) 4744 btrfs_item_key_to_cpu(c, key, slot); 4745 else { 4746 u64 gen = btrfs_node_ptr_generation(c, slot); 4747 4748 if (gen < min_trans) { 4749 slot++; 4750 goto next; 4751 } 4752 btrfs_node_key_to_cpu(c, key, slot); 4753 } 4754 return 0; 4755 } 4756 return 1; 4757 } 4758 4759 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path, 4760 u64 time_seq) 4761 { 4762 int slot; 4763 int level; 4764 struct extent_buffer *c; 4765 struct extent_buffer *next; 4766 struct btrfs_fs_info *fs_info = root->fs_info; 4767 struct btrfs_key key; 4768 bool need_commit_sem = false; 4769 u32 nritems; 4770 int ret; 4771 int i; 4772 4773 /* 4774 * The nowait semantics are used only for write paths, where we don't 4775 * use the tree mod log and sequence numbers. 4776 */ 4777 if (time_seq) 4778 ASSERT(!path->nowait); 4779 4780 nritems = btrfs_header_nritems(path->nodes[0]); 4781 if (nritems == 0) 4782 return 1; 4783 4784 btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 4785 again: 4786 level = 1; 4787 next = NULL; 4788 btrfs_release_path(path); 4789 4790 path->keep_locks = 1; 4791 4792 if (time_seq) { 4793 ret = btrfs_search_old_slot(root, &key, path, time_seq); 4794 } else { 4795 if (path->need_commit_sem) { 4796 path->need_commit_sem = 0; 4797 need_commit_sem = true; 4798 if (path->nowait) { 4799 if (!down_read_trylock(&fs_info->commit_root_sem)) { 4800 ret = -EAGAIN; 4801 goto done; 4802 } 4803 } else { 4804 down_read(&fs_info->commit_root_sem); 4805 } 4806 } 4807 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4808 } 4809 path->keep_locks = 0; 4810 4811 if (ret < 0) 4812 goto done; 4813 4814 nritems = btrfs_header_nritems(path->nodes[0]); 4815 /* 4816 * by releasing the path above we dropped all our locks. A balance 4817 * could have added more items next to the key that used to be 4818 * at the very end of the block. So, check again here and 4819 * advance the path if there are now more items available. 4820 */ 4821 if (nritems > 0 && path->slots[0] < nritems - 1) { 4822 if (ret == 0) 4823 path->slots[0]++; 4824 ret = 0; 4825 goto done; 4826 } 4827 /* 4828 * So the above check misses one case: 4829 * - after releasing the path above, someone has removed the item that 4830 * used to be at the very end of the block, and balance between leafs 4831 * gets another one with bigger key.offset to replace it. 4832 * 4833 * This one should be returned as well, or we can get leaf corruption 4834 * later(esp. in __btrfs_drop_extents()). 4835 * 4836 * And a bit more explanation about this check, 4837 * with ret > 0, the key isn't found, the path points to the slot 4838 * where it should be inserted, so the path->slots[0] item must be the 4839 * bigger one. 4840 */ 4841 if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) { 4842 ret = 0; 4843 goto done; 4844 } 4845 4846 while (level < BTRFS_MAX_LEVEL) { 4847 if (!path->nodes[level]) { 4848 ret = 1; 4849 goto done; 4850 } 4851 4852 slot = path->slots[level] + 1; 4853 c = path->nodes[level]; 4854 if (slot >= btrfs_header_nritems(c)) { 4855 level++; 4856 if (level == BTRFS_MAX_LEVEL) { 4857 ret = 1; 4858 goto done; 4859 } 4860 continue; 4861 } 4862 4863 4864 /* 4865 * Our current level is where we're going to start from, and to 4866 * make sure lockdep doesn't complain we need to drop our locks 4867 * and nodes from 0 to our current level. 4868 */ 4869 for (i = 0; i < level; i++) { 4870 if (path->locks[level]) { 4871 btrfs_tree_read_unlock(path->nodes[i]); 4872 path->locks[i] = 0; 4873 } 4874 free_extent_buffer(path->nodes[i]); 4875 path->nodes[i] = NULL; 4876 } 4877 4878 next = c; 4879 ret = read_block_for_search(root, path, &next, level, 4880 slot, &key); 4881 if (ret == -EAGAIN && !path->nowait) 4882 goto again; 4883 4884 if (ret < 0) { 4885 btrfs_release_path(path); 4886 goto done; 4887 } 4888 4889 if (!path->skip_locking) { 4890 ret = btrfs_try_tree_read_lock(next); 4891 if (!ret && path->nowait) { 4892 ret = -EAGAIN; 4893 goto done; 4894 } 4895 if (!ret && time_seq) { 4896 /* 4897 * If we don't get the lock, we may be racing 4898 * with push_leaf_left, holding that lock while 4899 * itself waiting for the leaf we've currently 4900 * locked. To solve this situation, we give up 4901 * on our lock and cycle. 4902 */ 4903 free_extent_buffer(next); 4904 btrfs_release_path(path); 4905 cond_resched(); 4906 goto again; 4907 } 4908 if (!ret) 4909 btrfs_tree_read_lock(next); 4910 } 4911 break; 4912 } 4913 path->slots[level] = slot; 4914 while (1) { 4915 level--; 4916 path->nodes[level] = next; 4917 path->slots[level] = 0; 4918 if (!path->skip_locking) 4919 path->locks[level] = BTRFS_READ_LOCK; 4920 if (!level) 4921 break; 4922 4923 ret = read_block_for_search(root, path, &next, level, 4924 0, &key); 4925 if (ret == -EAGAIN && !path->nowait) 4926 goto again; 4927 4928 if (ret < 0) { 4929 btrfs_release_path(path); 4930 goto done; 4931 } 4932 4933 if (!path->skip_locking) { 4934 if (path->nowait) { 4935 if (!btrfs_try_tree_read_lock(next)) { 4936 ret = -EAGAIN; 4937 goto done; 4938 } 4939 } else { 4940 btrfs_tree_read_lock(next); 4941 } 4942 } 4943 } 4944 ret = 0; 4945 done: 4946 unlock_up(path, 0, 1, 0, NULL); 4947 if (need_commit_sem) { 4948 int ret2; 4949 4950 path->need_commit_sem = 1; 4951 ret2 = finish_need_commit_sem_search(path); 4952 up_read(&fs_info->commit_root_sem); 4953 if (ret2) 4954 ret = ret2; 4955 } 4956 4957 return ret; 4958 } 4959 4960 int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq) 4961 { 4962 path->slots[0]++; 4963 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) 4964 return btrfs_next_old_leaf(root, path, time_seq); 4965 return 0; 4966 } 4967 4968 /* 4969 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 4970 * searching until it gets past min_objectid or finds an item of 'type' 4971 * 4972 * returns 0 if something is found, 1 if nothing was found and < 0 on error 4973 */ 4974 int btrfs_previous_item(struct btrfs_root *root, 4975 struct btrfs_path *path, u64 min_objectid, 4976 int type) 4977 { 4978 struct btrfs_key found_key; 4979 struct extent_buffer *leaf; 4980 u32 nritems; 4981 int ret; 4982 4983 while (1) { 4984 if (path->slots[0] == 0) { 4985 ret = btrfs_prev_leaf(root, path); 4986 if (ret != 0) 4987 return ret; 4988 } else { 4989 path->slots[0]--; 4990 } 4991 leaf = path->nodes[0]; 4992 nritems = btrfs_header_nritems(leaf); 4993 if (nritems == 0) 4994 return 1; 4995 if (path->slots[0] == nritems) 4996 path->slots[0]--; 4997 4998 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4999 if (found_key.objectid < min_objectid) 5000 break; 5001 if (found_key.type == type) 5002 return 0; 5003 if (found_key.objectid == min_objectid && 5004 found_key.type < type) 5005 break; 5006 } 5007 return 1; 5008 } 5009 5010 /* 5011 * search in extent tree to find a previous Metadata/Data extent item with 5012 * min objecitd. 5013 * 5014 * returns 0 if something is found, 1 if nothing was found and < 0 on error 5015 */ 5016 int btrfs_previous_extent_item(struct btrfs_root *root, 5017 struct btrfs_path *path, u64 min_objectid) 5018 { 5019 struct btrfs_key found_key; 5020 struct extent_buffer *leaf; 5021 u32 nritems; 5022 int ret; 5023 5024 while (1) { 5025 if (path->slots[0] == 0) { 5026 ret = btrfs_prev_leaf(root, path); 5027 if (ret != 0) 5028 return ret; 5029 } else { 5030 path->slots[0]--; 5031 } 5032 leaf = path->nodes[0]; 5033 nritems = btrfs_header_nritems(leaf); 5034 if (nritems == 0) 5035 return 1; 5036 if (path->slots[0] == nritems) 5037 path->slots[0]--; 5038 5039 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 5040 if (found_key.objectid < min_objectid) 5041 break; 5042 if (found_key.type == BTRFS_EXTENT_ITEM_KEY || 5043 found_key.type == BTRFS_METADATA_ITEM_KEY) 5044 return 0; 5045 if (found_key.objectid == min_objectid && 5046 found_key.type < BTRFS_EXTENT_ITEM_KEY) 5047 break; 5048 } 5049 return 1; 5050 } 5051 5052 int __init btrfs_ctree_init(void) 5053 { 5054 btrfs_path_cachep = kmem_cache_create("btrfs_path", 5055 sizeof(struct btrfs_path), 0, 5056 SLAB_MEM_SPREAD, NULL); 5057 if (!btrfs_path_cachep) 5058 return -ENOMEM; 5059 return 0; 5060 } 5061 5062 void __cold btrfs_ctree_exit(void) 5063 { 5064 kmem_cache_destroy(btrfs_path_cachep); 5065 } 5066