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