16cbd5570SChris Mason /* 2d352ac68SChris Mason * Copyright (C) 2007,2008 Oracle. All rights reserved. 36cbd5570SChris Mason * 46cbd5570SChris Mason * This program is free software; you can redistribute it and/or 56cbd5570SChris Mason * modify it under the terms of the GNU General Public 66cbd5570SChris Mason * License v2 as published by the Free Software Foundation. 76cbd5570SChris Mason * 86cbd5570SChris Mason * This program is distributed in the hope that it will be useful, 96cbd5570SChris Mason * but WITHOUT ANY WARRANTY; without even the implied warranty of 106cbd5570SChris Mason * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 116cbd5570SChris Mason * General Public License for more details. 126cbd5570SChris Mason * 136cbd5570SChris Mason * You should have received a copy of the GNU General Public 146cbd5570SChris Mason * License along with this program; if not, write to the 156cbd5570SChris Mason * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 166cbd5570SChris Mason * Boston, MA 021110-1307, USA. 176cbd5570SChris Mason */ 186cbd5570SChris Mason 19a6b6e75eSChris Mason #include <linux/sched.h> 20eb60ceacSChris Mason #include "ctree.h" 21eb60ceacSChris Mason #include "disk-io.h" 227f5c1516SChris Mason #include "transaction.h" 235f39d397SChris Mason #include "print-tree.h" 24925baeddSChris Mason #include "locking.h" 259a8dd150SChris Mason 26e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 27e089f05cSChris Mason *root, struct btrfs_path *path, int level); 28e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 29d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 30cc0c5538SChris Mason struct btrfs_path *path, int data_size, int extend); 315f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 325f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 33971a1f66SChris Mason struct extent_buffer *src, int empty); 345f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 355f39d397SChris Mason struct btrfs_root *root, 365f39d397SChris Mason struct extent_buffer *dst_buf, 375f39d397SChris Mason struct extent_buffer *src_buf); 38e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 39e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 40d97e63b6SChris Mason 41df24a2b9SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 42df24a2b9SChris Mason { 43df24a2b9SChris Mason memset(p, 0, sizeof(*p)); 44df24a2b9SChris Mason } 45df24a2b9SChris Mason 462c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 472c90e5d6SChris Mason { 48df24a2b9SChris Mason struct btrfs_path *path; 49df24a2b9SChris Mason path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS); 502cc58cf2SChris Mason if (path) { 51df24a2b9SChris Mason btrfs_init_path(path); 522cc58cf2SChris Mason path->reada = 1; 532cc58cf2SChris Mason } 54df24a2b9SChris Mason return path; 552c90e5d6SChris Mason } 562c90e5d6SChris Mason 57d352ac68SChris Mason /* this also releases the path */ 582c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 592c90e5d6SChris Mason { 60df24a2b9SChris Mason btrfs_release_path(NULL, p); 612c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 622c90e5d6SChris Mason } 632c90e5d6SChris Mason 64d352ac68SChris Mason /* 65d352ac68SChris Mason * path release drops references on the extent buffers in the path 66d352ac68SChris Mason * and it drops any locks held by this path 67d352ac68SChris Mason * 68d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 69d352ac68SChris Mason */ 70d397712bSChris Mason noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 71eb60ceacSChris Mason { 72eb60ceacSChris Mason int i; 73a2135011SChris Mason 74234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 753f157a2fSChris Mason p->slots[i] = 0; 76eb60ceacSChris Mason if (!p->nodes[i]) 77925baeddSChris Mason continue; 78925baeddSChris Mason if (p->locks[i]) { 79925baeddSChris Mason btrfs_tree_unlock(p->nodes[i]); 80925baeddSChris Mason p->locks[i] = 0; 81925baeddSChris Mason } 825f39d397SChris Mason free_extent_buffer(p->nodes[i]); 833f157a2fSChris Mason p->nodes[i] = NULL; 84eb60ceacSChris Mason } 85eb60ceacSChris Mason } 86eb60ceacSChris Mason 87d352ac68SChris Mason /* 88d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 89d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 90d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 91d352ac68SChris Mason * looping required. 92d352ac68SChris Mason * 93d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 94d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 95d352ac68SChris Mason * at any time because there are no locks held. 96d352ac68SChris Mason */ 97925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 98925baeddSChris Mason { 99925baeddSChris Mason struct extent_buffer *eb; 100925baeddSChris Mason spin_lock(&root->node_lock); 101925baeddSChris Mason eb = root->node; 102925baeddSChris Mason extent_buffer_get(eb); 103925baeddSChris Mason spin_unlock(&root->node_lock); 104925baeddSChris Mason return eb; 105925baeddSChris Mason } 106925baeddSChris Mason 107d352ac68SChris Mason /* loop around taking references on and locking the root node of the 108d352ac68SChris Mason * tree until you end up with a lock on the root. A locked buffer 109d352ac68SChris Mason * is returned, with a reference held. 110d352ac68SChris Mason */ 111925baeddSChris Mason struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root) 112925baeddSChris Mason { 113925baeddSChris Mason struct extent_buffer *eb; 114925baeddSChris Mason 115925baeddSChris Mason while (1) { 116925baeddSChris Mason eb = btrfs_root_node(root); 117925baeddSChris Mason btrfs_tree_lock(eb); 118925baeddSChris Mason 119925baeddSChris Mason spin_lock(&root->node_lock); 120925baeddSChris Mason if (eb == root->node) { 121925baeddSChris Mason spin_unlock(&root->node_lock); 122925baeddSChris Mason break; 123925baeddSChris Mason } 124925baeddSChris Mason spin_unlock(&root->node_lock); 125925baeddSChris Mason 126925baeddSChris Mason btrfs_tree_unlock(eb); 127925baeddSChris Mason free_extent_buffer(eb); 128925baeddSChris Mason } 129925baeddSChris Mason return eb; 130925baeddSChris Mason } 131925baeddSChris Mason 132d352ac68SChris Mason /* cowonly root (everything not a reference counted cow subvolume), just get 133d352ac68SChris Mason * put onto a simple dirty list. transaction.c walks this to make sure they 134d352ac68SChris Mason * get properly updated on disk. 135d352ac68SChris Mason */ 1360b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 1370b86a832SChris Mason { 1380b86a832SChris Mason if (root->track_dirty && list_empty(&root->dirty_list)) { 1390b86a832SChris Mason list_add(&root->dirty_list, 1400b86a832SChris Mason &root->fs_info->dirty_cowonly_roots); 1410b86a832SChris Mason } 1420b86a832SChris Mason } 1430b86a832SChris Mason 144d352ac68SChris Mason /* 145d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 146d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 147d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 148d352ac68SChris Mason */ 149be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 150be20aa9dSChris Mason struct btrfs_root *root, 151be20aa9dSChris Mason struct extent_buffer *buf, 152be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 153be20aa9dSChris Mason { 154be20aa9dSChris Mason struct extent_buffer *cow; 155be20aa9dSChris Mason u32 nritems; 156be20aa9dSChris Mason int ret = 0; 157be20aa9dSChris Mason int level; 1584aec2b52SChris Mason struct btrfs_root *new_root; 159be20aa9dSChris Mason 1604aec2b52SChris Mason new_root = kmalloc(sizeof(*new_root), GFP_NOFS); 1614aec2b52SChris Mason if (!new_root) 1624aec2b52SChris Mason return -ENOMEM; 1634aec2b52SChris Mason 1644aec2b52SChris Mason memcpy(new_root, root, sizeof(*new_root)); 1654aec2b52SChris Mason new_root->root_key.objectid = new_root_objectid; 166be20aa9dSChris Mason 167be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != 168be20aa9dSChris Mason root->fs_info->running_transaction->transid); 169be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 170be20aa9dSChris Mason 171be20aa9dSChris Mason level = btrfs_header_level(buf); 172be20aa9dSChris Mason nritems = btrfs_header_nritems(buf); 17331840ae1SZheng Yan 17431840ae1SZheng Yan cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0, 17531840ae1SZheng Yan new_root_objectid, trans->transid, 176be20aa9dSChris Mason level, buf->start, 0); 1774aec2b52SChris Mason if (IS_ERR(cow)) { 1784aec2b52SChris Mason kfree(new_root); 179be20aa9dSChris Mason return PTR_ERR(cow); 1804aec2b52SChris Mason } 181be20aa9dSChris Mason 182be20aa9dSChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 183be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 184be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 185be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 18663b10fc4SChris Mason btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); 187be20aa9dSChris Mason 1882b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 1892b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 1902b82032cSYan Zheng BTRFS_FSID_SIZE); 1912b82032cSYan Zheng 192be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 19331840ae1SZheng Yan ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL); 1944aec2b52SChris Mason kfree(new_root); 1954aec2b52SChris Mason 196be20aa9dSChris Mason if (ret) 197be20aa9dSChris Mason return ret; 198be20aa9dSChris Mason 199be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 200be20aa9dSChris Mason *cow_ret = cow; 201be20aa9dSChris Mason return 0; 202be20aa9dSChris Mason } 203be20aa9dSChris Mason 204d352ac68SChris Mason /* 205d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 206d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 207d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 208d397712bSChris Mason * dirty again. 209d352ac68SChris Mason * 210d352ac68SChris Mason * search_start -- an allocation hint for the new block 211d352ac68SChris Mason * 212d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 213d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 214d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 215d352ac68SChris Mason * 216d352ac68SChris Mason * prealloc_dest -- if you have already reserved a destination for the cow, 217d397712bSChris Mason * this uses that block instead of allocating a new one. 218d397712bSChris Mason * btrfs_alloc_reserved_extent is used to finish the allocation. 219d352ac68SChris Mason */ 220d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 2215f39d397SChris Mason struct btrfs_root *root, 2225f39d397SChris Mason struct extent_buffer *buf, 2235f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 2245f39d397SChris Mason struct extent_buffer **cow_ret, 22565b51a00SChris Mason u64 search_start, u64 empty_size, 22665b51a00SChris Mason u64 prealloc_dest) 2276702ed49SChris Mason { 22831840ae1SZheng Yan u64 parent_start; 2295f39d397SChris Mason struct extent_buffer *cow; 2307bb86316SChris Mason u32 nritems; 2316702ed49SChris Mason int ret = 0; 2327bb86316SChris Mason int level; 233925baeddSChris Mason int unlock_orig = 0; 2346702ed49SChris Mason 235925baeddSChris Mason if (*cow_ret == buf) 236925baeddSChris Mason unlock_orig = 1; 237925baeddSChris Mason 238925baeddSChris Mason WARN_ON(!btrfs_tree_locked(buf)); 239925baeddSChris Mason 24031840ae1SZheng Yan if (parent) 24131840ae1SZheng Yan parent_start = parent->start; 24231840ae1SZheng Yan else 24331840ae1SZheng Yan parent_start = 0; 24431840ae1SZheng Yan 2457bb86316SChris Mason WARN_ON(root->ref_cows && trans->transid != 2467bb86316SChris Mason root->fs_info->running_transaction->transid); 2476702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 2485f39d397SChris Mason 2497bb86316SChris Mason level = btrfs_header_level(buf); 2507bb86316SChris Mason nritems = btrfs_header_nritems(buf); 25131840ae1SZheng Yan 25265b51a00SChris Mason if (prealloc_dest) { 25365b51a00SChris Mason struct btrfs_key ins; 25465b51a00SChris Mason 25565b51a00SChris Mason ins.objectid = prealloc_dest; 25665b51a00SChris Mason ins.offset = buf->len; 25765b51a00SChris Mason ins.type = BTRFS_EXTENT_ITEM_KEY; 25865b51a00SChris Mason 25931840ae1SZheng Yan ret = btrfs_alloc_reserved_extent(trans, root, parent_start, 26065b51a00SChris Mason root->root_key.objectid, 2613bb1a1bcSYan Zheng trans->transid, level, &ins); 26265b51a00SChris Mason BUG_ON(ret); 26365b51a00SChris Mason cow = btrfs_init_new_buffer(trans, root, prealloc_dest, 26465b51a00SChris Mason buf->len); 26565b51a00SChris Mason } else { 266925baeddSChris Mason cow = btrfs_alloc_free_block(trans, root, buf->len, 26731840ae1SZheng Yan parent_start, 2687bb86316SChris Mason root->root_key.objectid, 26931840ae1SZheng Yan trans->transid, level, 27031840ae1SZheng Yan search_start, empty_size); 27165b51a00SChris Mason } 2726702ed49SChris Mason if (IS_ERR(cow)) 2736702ed49SChris Mason return PTR_ERR(cow); 2746702ed49SChris Mason 2755f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 276db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 2775f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 2785f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 27963b10fc4SChris Mason btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); 2806702ed49SChris Mason 2812b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 2822b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 2832b82032cSYan Zheng BTRFS_FSID_SIZE); 2842b82032cSYan Zheng 2855f39d397SChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 2865f39d397SChris Mason if (btrfs_header_generation(buf) != trans->transid) { 28731840ae1SZheng Yan u32 nr_extents; 28831840ae1SZheng Yan ret = btrfs_inc_ref(trans, root, buf, cow, &nr_extents); 2896702ed49SChris Mason if (ret) 2906702ed49SChris Mason return ret; 29131840ae1SZheng Yan 29231840ae1SZheng Yan ret = btrfs_cache_ref(trans, root, buf, nr_extents); 29331840ae1SZheng Yan WARN_ON(ret); 2941a40e23bSZheng Yan } else if (btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID) { 2951a40e23bSZheng Yan /* 2961a40e23bSZheng Yan * There are only two places that can drop reference to 2971a40e23bSZheng Yan * tree blocks owned by living reloc trees, one is here, 298f82d02d9SYan Zheng * the other place is btrfs_drop_subtree. In both places, 2991a40e23bSZheng Yan * we check reference count while tree block is locked. 3001a40e23bSZheng Yan * Furthermore, if reference count is one, it won't get 3011a40e23bSZheng Yan * increased by someone else. 3021a40e23bSZheng Yan */ 3031a40e23bSZheng Yan u32 refs; 3041a40e23bSZheng Yan ret = btrfs_lookup_extent_ref(trans, root, buf->start, 3051a40e23bSZheng Yan buf->len, &refs); 3061a40e23bSZheng Yan BUG_ON(ret); 3071a40e23bSZheng Yan if (refs == 1) { 3081a40e23bSZheng Yan ret = btrfs_update_ref(trans, root, buf, cow, 3091a40e23bSZheng Yan 0, nritems); 3101a40e23bSZheng Yan clean_tree_block(trans, root, buf); 3111a40e23bSZheng Yan } else { 3121a40e23bSZheng Yan ret = btrfs_inc_ref(trans, root, buf, cow, NULL); 3131a40e23bSZheng Yan } 3141a40e23bSZheng Yan BUG_ON(ret); 3156702ed49SChris Mason } else { 31631840ae1SZheng Yan ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems); 31731840ae1SZheng Yan if (ret) 31831840ae1SZheng Yan return ret; 3196702ed49SChris Mason clean_tree_block(trans, root, buf); 3206702ed49SChris Mason } 3216702ed49SChris Mason 3221a40e23bSZheng Yan if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) { 3231a40e23bSZheng Yan ret = btrfs_reloc_tree_cache_ref(trans, root, cow, buf->start); 3241a40e23bSZheng Yan WARN_ON(ret); 3251a40e23bSZheng Yan } 3261a40e23bSZheng Yan 3276702ed49SChris Mason if (buf == root->node) { 328925baeddSChris Mason WARN_ON(parent && parent != buf); 329925baeddSChris Mason 330925baeddSChris Mason spin_lock(&root->node_lock); 3316702ed49SChris Mason root->node = cow; 3325f39d397SChris Mason extent_buffer_get(cow); 333925baeddSChris Mason spin_unlock(&root->node_lock); 334925baeddSChris Mason 3356702ed49SChris Mason if (buf != root->commit_root) { 336db94535dSChris Mason btrfs_free_extent(trans, root, buf->start, 33731840ae1SZheng Yan buf->len, buf->start, 33831840ae1SZheng Yan root->root_key.objectid, 33931840ae1SZheng Yan btrfs_header_generation(buf), 3403bb1a1bcSYan Zheng level, 1); 3416702ed49SChris Mason } 3425f39d397SChris Mason free_extent_buffer(buf); 3430b86a832SChris Mason add_root_to_dirty_list(root); 3446702ed49SChris Mason } else { 3455f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 346db94535dSChris Mason cow->start); 34774493f7aSChris Mason WARN_ON(trans->transid == 0); 34874493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 34974493f7aSChris Mason trans->transid); 3506702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 3515f39d397SChris Mason WARN_ON(btrfs_header_generation(parent) != trans->transid); 3527bb86316SChris Mason btrfs_free_extent(trans, root, buf->start, buf->len, 35331840ae1SZheng Yan parent_start, btrfs_header_owner(parent), 3543bb1a1bcSYan Zheng btrfs_header_generation(parent), level, 1); 3556702ed49SChris Mason } 356925baeddSChris Mason if (unlock_orig) 357925baeddSChris Mason btrfs_tree_unlock(buf); 3585f39d397SChris Mason free_extent_buffer(buf); 3596702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 3606702ed49SChris Mason *cow_ret = cow; 3616702ed49SChris Mason return 0; 3626702ed49SChris Mason } 3636702ed49SChris Mason 364d352ac68SChris Mason /* 365d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 366d352ac68SChris Mason * This version of it has extra checks so that a block isn't cow'd more than 367d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 368d352ac68SChris Mason */ 369d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 3705f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 3715f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 37265b51a00SChris Mason struct extent_buffer **cow_ret, u64 prealloc_dest) 37302217ed2SChris Mason { 3746702ed49SChris Mason u64 search_start; 375f510cfecSChris Mason int ret; 376dc17ff8fSChris Mason 377ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 378d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 379d397712bSChris Mason (unsigned long long)trans->transid, 380d397712bSChris Mason (unsigned long long) 381ccd467d6SChris Mason root->fs_info->running_transaction->transid); 382ccd467d6SChris Mason WARN_ON(1); 383ccd467d6SChris Mason } 384ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 385d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 386d397712bSChris Mason (unsigned long long)trans->transid, 387d397712bSChris Mason (unsigned long long)root->fs_info->generation); 388ccd467d6SChris Mason WARN_ON(1); 389ccd467d6SChris Mason } 390dc17ff8fSChris Mason 3915b21f2edSZheng Yan if (btrfs_header_generation(buf) == trans->transid && 3925b21f2edSZheng Yan btrfs_header_owner(buf) == root->root_key.objectid && 39363b10fc4SChris Mason !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) { 39402217ed2SChris Mason *cow_ret = buf; 39565b51a00SChris Mason WARN_ON(prealloc_dest); 39602217ed2SChris Mason return 0; 39702217ed2SChris Mason } 398c487685dSChris Mason 3990b86a832SChris Mason search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); 400f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 40165b51a00SChris Mason parent_slot, cow_ret, search_start, 0, 40265b51a00SChris Mason prealloc_dest); 403f510cfecSChris Mason return ret; 4042c90e5d6SChris Mason } 4056702ed49SChris Mason 406d352ac68SChris Mason /* 407d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 408d352ac68SChris Mason * node are actually close by 409d352ac68SChris Mason */ 4106b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 4116702ed49SChris Mason { 4126b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 4136702ed49SChris Mason return 1; 4146b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 4156702ed49SChris Mason return 1; 41602217ed2SChris Mason return 0; 41702217ed2SChris Mason } 41802217ed2SChris Mason 419081e9573SChris Mason /* 420081e9573SChris Mason * compare two keys in a memcmp fashion 421081e9573SChris Mason */ 422081e9573SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 423081e9573SChris Mason { 424081e9573SChris Mason struct btrfs_key k1; 425081e9573SChris Mason 426081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 427081e9573SChris Mason 428081e9573SChris Mason if (k1.objectid > k2->objectid) 429081e9573SChris Mason return 1; 430081e9573SChris Mason if (k1.objectid < k2->objectid) 431081e9573SChris Mason return -1; 432081e9573SChris Mason if (k1.type > k2->type) 433081e9573SChris Mason return 1; 434081e9573SChris Mason if (k1.type < k2->type) 435081e9573SChris Mason return -1; 436081e9573SChris Mason if (k1.offset > k2->offset) 437081e9573SChris Mason return 1; 438081e9573SChris Mason if (k1.offset < k2->offset) 439081e9573SChris Mason return -1; 440081e9573SChris Mason return 0; 441081e9573SChris Mason } 442081e9573SChris Mason 443f3465ca4SJosef Bacik /* 444f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 445f3465ca4SJosef Bacik */ 446f3465ca4SJosef Bacik static int comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2) 447f3465ca4SJosef Bacik { 448f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 449f3465ca4SJosef Bacik return 1; 450f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 451f3465ca4SJosef Bacik return -1; 452f3465ca4SJosef Bacik if (k1->type > k2->type) 453f3465ca4SJosef Bacik return 1; 454f3465ca4SJosef Bacik if (k1->type < k2->type) 455f3465ca4SJosef Bacik return -1; 456f3465ca4SJosef Bacik if (k1->offset > k2->offset) 457f3465ca4SJosef Bacik return 1; 458f3465ca4SJosef Bacik if (k1->offset < k2->offset) 459f3465ca4SJosef Bacik return -1; 460f3465ca4SJosef Bacik return 0; 461f3465ca4SJosef Bacik } 462081e9573SChris Mason 463d352ac68SChris Mason /* 464d352ac68SChris Mason * this is used by the defrag code to go through all the 465d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 466d352ac68SChris Mason * disk order is close to key order 467d352ac68SChris Mason */ 4686702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 4695f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 470a6b6e75eSChris Mason int start_slot, int cache_only, u64 *last_ret, 471a6b6e75eSChris Mason struct btrfs_key *progress) 4726702ed49SChris Mason { 4736b80053dSChris Mason struct extent_buffer *cur; 4746702ed49SChris Mason u64 blocknr; 475ca7a79adSChris Mason u64 gen; 476e9d0b13bSChris Mason u64 search_start = *last_ret; 477e9d0b13bSChris Mason u64 last_block = 0; 4786702ed49SChris Mason u64 other; 4796702ed49SChris Mason u32 parent_nritems; 4806702ed49SChris Mason int end_slot; 4816702ed49SChris Mason int i; 4826702ed49SChris Mason int err = 0; 483f2183bdeSChris Mason int parent_level; 4846b80053dSChris Mason int uptodate; 4856b80053dSChris Mason u32 blocksize; 486081e9573SChris Mason int progress_passed = 0; 487081e9573SChris Mason struct btrfs_disk_key disk_key; 4886702ed49SChris Mason 4895708b959SChris Mason parent_level = btrfs_header_level(parent); 4905708b959SChris Mason if (cache_only && parent_level != 1) 4915708b959SChris Mason return 0; 4925708b959SChris Mason 493d397712bSChris Mason if (trans->transaction != root->fs_info->running_transaction) 4946702ed49SChris Mason WARN_ON(1); 495d397712bSChris Mason if (trans->transid != root->fs_info->generation) 4966702ed49SChris Mason WARN_ON(1); 49786479a04SChris Mason 4986b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 4996b80053dSChris Mason blocksize = btrfs_level_size(root, parent_level - 1); 5006702ed49SChris Mason end_slot = parent_nritems; 5016702ed49SChris Mason 5026702ed49SChris Mason if (parent_nritems == 1) 5036702ed49SChris Mason return 0; 5046702ed49SChris Mason 5056702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 5066702ed49SChris Mason int close = 1; 507a6b6e75eSChris Mason 5085708b959SChris Mason if (!parent->map_token) { 5095708b959SChris Mason map_extent_buffer(parent, 5105708b959SChris Mason btrfs_node_key_ptr_offset(i), 5115708b959SChris Mason sizeof(struct btrfs_key_ptr), 5125708b959SChris Mason &parent->map_token, &parent->kaddr, 5135708b959SChris Mason &parent->map_start, &parent->map_len, 5145708b959SChris Mason KM_USER1); 5155708b959SChris Mason } 516081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 517081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 518081e9573SChris Mason continue; 519081e9573SChris Mason 520081e9573SChris Mason progress_passed = 1; 5216b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 522ca7a79adSChris Mason gen = btrfs_node_ptr_generation(parent, i); 523e9d0b13bSChris Mason if (last_block == 0) 524e9d0b13bSChris Mason last_block = blocknr; 5255708b959SChris Mason 5266702ed49SChris Mason if (i > 0) { 5276b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 5286b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 5296702ed49SChris Mason } 5300ef3e66bSChris Mason if (!close && i < end_slot - 2) { 5316b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 5326b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 5336702ed49SChris Mason } 534e9d0b13bSChris Mason if (close) { 535e9d0b13bSChris Mason last_block = blocknr; 5366702ed49SChris Mason continue; 537e9d0b13bSChris Mason } 5385708b959SChris Mason if (parent->map_token) { 5395708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 5405708b959SChris Mason KM_USER1); 5415708b959SChris Mason parent->map_token = NULL; 5425708b959SChris Mason } 5436702ed49SChris Mason 5446b80053dSChris Mason cur = btrfs_find_tree_block(root, blocknr, blocksize); 5456b80053dSChris Mason if (cur) 5461259ab75SChris Mason uptodate = btrfs_buffer_uptodate(cur, gen); 5476b80053dSChris Mason else 5486b80053dSChris Mason uptodate = 0; 5495708b959SChris Mason if (!cur || !uptodate) { 5506702ed49SChris Mason if (cache_only) { 5516b80053dSChris Mason free_extent_buffer(cur); 5526702ed49SChris Mason continue; 5536702ed49SChris Mason } 5546b80053dSChris Mason if (!cur) { 5556b80053dSChris Mason cur = read_tree_block(root, blocknr, 556ca7a79adSChris Mason blocksize, gen); 5576b80053dSChris Mason } else if (!uptodate) { 558ca7a79adSChris Mason btrfs_read_buffer(cur, gen); 5596702ed49SChris Mason } 560f2183bdeSChris Mason } 561e9d0b13bSChris Mason if (search_start == 0) 5626b80053dSChris Mason search_start = last_block; 563e9d0b13bSChris Mason 564e7a84565SChris Mason btrfs_tree_lock(cur); 5656b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 566e7a84565SChris Mason &cur, search_start, 5676b80053dSChris Mason min(16 * blocksize, 56865b51a00SChris Mason (end_slot - i) * blocksize), 0); 569252c38f0SYan if (err) { 570e7a84565SChris Mason btrfs_tree_unlock(cur); 5716b80053dSChris Mason free_extent_buffer(cur); 5726702ed49SChris Mason break; 573252c38f0SYan } 574e7a84565SChris Mason search_start = cur->start; 575e7a84565SChris Mason last_block = cur->start; 576f2183bdeSChris Mason *last_ret = search_start; 577e7a84565SChris Mason btrfs_tree_unlock(cur); 578e7a84565SChris Mason free_extent_buffer(cur); 5796702ed49SChris Mason } 5805708b959SChris Mason if (parent->map_token) { 5815708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 5825708b959SChris Mason KM_USER1); 5835708b959SChris Mason parent->map_token = NULL; 5845708b959SChris Mason } 5856702ed49SChris Mason return err; 5866702ed49SChris Mason } 5876702ed49SChris Mason 58874123bd7SChris Mason /* 58974123bd7SChris Mason * The leaf data grows from end-to-front in the node. 59074123bd7SChris Mason * this returns the address of the start of the last item, 59174123bd7SChris Mason * which is the stop of the leaf data stack 59274123bd7SChris Mason */ 593123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 5945f39d397SChris Mason struct extent_buffer *leaf) 595be0e5c09SChris Mason { 5965f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 597be0e5c09SChris Mason if (nr == 0) 598123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 5995f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 600be0e5c09SChris Mason } 601be0e5c09SChris Mason 602d352ac68SChris Mason /* 603d352ac68SChris Mason * extra debugging checks to make sure all the items in a key are 604d352ac68SChris Mason * well formed and in the proper order 605d352ac68SChris Mason */ 606123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 607123abc88SChris Mason int level) 608aa5d6bedSChris Mason { 6095f39d397SChris Mason struct extent_buffer *parent = NULL; 6105f39d397SChris Mason struct extent_buffer *node = path->nodes[level]; 6115f39d397SChris Mason struct btrfs_disk_key parent_key; 6125f39d397SChris Mason struct btrfs_disk_key node_key; 613aa5d6bedSChris Mason int parent_slot; 6148d7be552SChris Mason int slot; 6158d7be552SChris Mason struct btrfs_key cpukey; 6165f39d397SChris Mason u32 nritems = btrfs_header_nritems(node); 617aa5d6bedSChris Mason 618aa5d6bedSChris Mason if (path->nodes[level + 1]) 6195f39d397SChris Mason parent = path->nodes[level + 1]; 620a1f39630SAneesh 6218d7be552SChris Mason slot = path->slots[level]; 6227518a238SChris Mason BUG_ON(nritems == 0); 6237518a238SChris Mason if (parent) { 624a1f39630SAneesh parent_slot = path->slots[level + 1]; 6255f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 6265f39d397SChris Mason btrfs_node_key(node, &node_key, 0); 6275f39d397SChris Mason BUG_ON(memcmp(&parent_key, &node_key, 628e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 6291d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 630db94535dSChris Mason btrfs_header_bytenr(node)); 631aa5d6bedSChris Mason } 632123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 6338d7be552SChris Mason if (slot != 0) { 6345f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot - 1); 6355f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 6365f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) <= 0); 6378d7be552SChris Mason } 6388d7be552SChris Mason if (slot < nritems - 1) { 6395f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot + 1); 6405f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 6415f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) >= 0); 642aa5d6bedSChris Mason } 643aa5d6bedSChris Mason return 0; 644aa5d6bedSChris Mason } 645aa5d6bedSChris Mason 646d352ac68SChris Mason /* 647d352ac68SChris Mason * extra checking to make sure all the items in a leaf are 648d352ac68SChris Mason * well formed and in the proper order 649d352ac68SChris Mason */ 650123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 651123abc88SChris Mason int level) 652aa5d6bedSChris Mason { 6535f39d397SChris Mason struct extent_buffer *leaf = path->nodes[level]; 6545f39d397SChris Mason struct extent_buffer *parent = NULL; 655aa5d6bedSChris Mason int parent_slot; 6568d7be552SChris Mason struct btrfs_key cpukey; 6575f39d397SChris Mason struct btrfs_disk_key parent_key; 6585f39d397SChris Mason struct btrfs_disk_key leaf_key; 6595f39d397SChris Mason int slot = path->slots[0]; 6608d7be552SChris Mason 6615f39d397SChris Mason u32 nritems = btrfs_header_nritems(leaf); 662aa5d6bedSChris Mason 663aa5d6bedSChris Mason if (path->nodes[level + 1]) 6645f39d397SChris Mason parent = path->nodes[level + 1]; 6657518a238SChris Mason 6667518a238SChris Mason if (nritems == 0) 6677518a238SChris Mason return 0; 6687518a238SChris Mason 6697518a238SChris Mason if (parent) { 670a1f39630SAneesh parent_slot = path->slots[level + 1]; 6715f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 6725f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, 0); 6736702ed49SChris Mason 6745f39d397SChris Mason BUG_ON(memcmp(&parent_key, &leaf_key, 675e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 6761d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 677db94535dSChris Mason btrfs_header_bytenr(leaf)); 678aa5d6bedSChris Mason } 6795f39d397SChris Mason if (slot != 0 && slot < nritems - 1) { 6805f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 6815f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1); 6825f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) <= 0) { 6835f39d397SChris Mason btrfs_print_leaf(root, leaf); 684d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad key\n", slot); 6855f39d397SChris Mason BUG_ON(1); 6865f39d397SChris Mason } 6875f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot - 1) != 6885f39d397SChris Mason btrfs_item_end_nr(leaf, slot)) { 6895f39d397SChris Mason btrfs_print_leaf(root, leaf); 690d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad\n", slot); 6915f39d397SChris Mason BUG_ON(1); 6925f39d397SChris Mason } 693aa5d6bedSChris Mason } 6948d7be552SChris Mason if (slot < nritems - 1) { 6955f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 6965f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1); 6975f39d397SChris Mason BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0); 6985f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot) != 6995f39d397SChris Mason btrfs_item_end_nr(leaf, slot + 1)) { 7005f39d397SChris Mason btrfs_print_leaf(root, leaf); 701d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad\n", slot); 7025f39d397SChris Mason BUG_ON(1); 703aa5d6bedSChris Mason } 7045f39d397SChris Mason } 7055f39d397SChris Mason BUG_ON(btrfs_item_offset_nr(leaf, 0) + 7065f39d397SChris Mason btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root)); 707aa5d6bedSChris Mason return 0; 708aa5d6bedSChris Mason } 709aa5d6bedSChris Mason 710d397712bSChris Mason static noinline int check_block(struct btrfs_root *root, 71198ed5174SChris Mason struct btrfs_path *path, int level) 712aa5d6bedSChris Mason { 71385d824c4SChris Mason return 0; 714aa5d6bedSChris Mason if (level == 0) 715123abc88SChris Mason return check_leaf(root, path, level); 716123abc88SChris Mason return check_node(root, path, level); 717aa5d6bedSChris Mason } 718aa5d6bedSChris Mason 71974123bd7SChris Mason /* 7205f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 7215f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 7225f39d397SChris Mason * 72374123bd7SChris Mason * the slot in the array is returned via slot, and it points to 72474123bd7SChris Mason * the place where you would insert key if it is not found in 72574123bd7SChris Mason * the array. 72674123bd7SChris Mason * 72774123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 72874123bd7SChris Mason */ 729e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 730e02119d5SChris Mason unsigned long p, 7315f39d397SChris Mason int item_size, struct btrfs_key *key, 732be0e5c09SChris Mason int max, int *slot) 733be0e5c09SChris Mason { 734be0e5c09SChris Mason int low = 0; 735be0e5c09SChris Mason int high = max; 736be0e5c09SChris Mason int mid; 737be0e5c09SChris Mason int ret; 738479965d6SChris Mason struct btrfs_disk_key *tmp = NULL; 7395f39d397SChris Mason struct btrfs_disk_key unaligned; 7405f39d397SChris Mason unsigned long offset; 7415f39d397SChris Mason char *map_token = NULL; 7425f39d397SChris Mason char *kaddr = NULL; 7435f39d397SChris Mason unsigned long map_start = 0; 7445f39d397SChris Mason unsigned long map_len = 0; 745479965d6SChris Mason int err; 746be0e5c09SChris Mason 747be0e5c09SChris Mason while (low < high) { 748be0e5c09SChris Mason mid = (low + high) / 2; 7495f39d397SChris Mason offset = p + mid * item_size; 7505f39d397SChris Mason 7515f39d397SChris Mason if (!map_token || offset < map_start || 7525f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 7535f39d397SChris Mason map_start + map_len) { 754479965d6SChris Mason if (map_token) { 7555f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 756479965d6SChris Mason map_token = NULL; 757479965d6SChris Mason } 758934d375bSChris Mason 759934d375bSChris Mason err = map_private_extent_buffer(eb, offset, 760479965d6SChris Mason sizeof(struct btrfs_disk_key), 761479965d6SChris Mason &map_token, &kaddr, 7625f39d397SChris Mason &map_start, &map_len, KM_USER0); 7635f39d397SChris Mason 764479965d6SChris Mason if (!err) { 765479965d6SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 766479965d6SChris Mason map_start); 767479965d6SChris Mason } else { 7685f39d397SChris Mason read_extent_buffer(eb, &unaligned, 7695f39d397SChris Mason offset, sizeof(unaligned)); 7705f39d397SChris Mason tmp = &unaligned; 771479965d6SChris Mason } 772479965d6SChris Mason 7735f39d397SChris Mason } else { 7745f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 7755f39d397SChris Mason map_start); 7765f39d397SChris Mason } 777be0e5c09SChris Mason ret = comp_keys(tmp, key); 778be0e5c09SChris Mason 779be0e5c09SChris Mason if (ret < 0) 780be0e5c09SChris Mason low = mid + 1; 781be0e5c09SChris Mason else if (ret > 0) 782be0e5c09SChris Mason high = mid; 783be0e5c09SChris Mason else { 784be0e5c09SChris Mason *slot = mid; 785479965d6SChris Mason if (map_token) 7865f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 787be0e5c09SChris Mason return 0; 788be0e5c09SChris Mason } 789be0e5c09SChris Mason } 790be0e5c09SChris Mason *slot = low; 7915f39d397SChris Mason if (map_token) 7925f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 793be0e5c09SChris Mason return 1; 794be0e5c09SChris Mason } 795be0e5c09SChris Mason 79697571fd0SChris Mason /* 79797571fd0SChris Mason * simple bin_search frontend that does the right thing for 79897571fd0SChris Mason * leaves vs nodes 79997571fd0SChris Mason */ 8005f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 8015f39d397SChris Mason int level, int *slot) 802be0e5c09SChris Mason { 8035f39d397SChris Mason if (level == 0) { 8045f39d397SChris Mason return generic_bin_search(eb, 8055f39d397SChris Mason offsetof(struct btrfs_leaf, items), 8060783fcfcSChris Mason sizeof(struct btrfs_item), 8075f39d397SChris Mason key, btrfs_header_nritems(eb), 8087518a238SChris Mason slot); 809be0e5c09SChris Mason } else { 8105f39d397SChris Mason return generic_bin_search(eb, 8115f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 812123abc88SChris Mason sizeof(struct btrfs_key_ptr), 8135f39d397SChris Mason key, btrfs_header_nritems(eb), 8147518a238SChris Mason slot); 815be0e5c09SChris Mason } 816be0e5c09SChris Mason return -1; 817be0e5c09SChris Mason } 818be0e5c09SChris Mason 819d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 820d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 821d352ac68SChris Mason * NULL is returned on error. 822d352ac68SChris Mason */ 823e02119d5SChris Mason static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root, 8245f39d397SChris Mason struct extent_buffer *parent, int slot) 825bb803951SChris Mason { 826ca7a79adSChris Mason int level = btrfs_header_level(parent); 827bb803951SChris Mason if (slot < 0) 828bb803951SChris Mason return NULL; 8295f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 830bb803951SChris Mason return NULL; 831ca7a79adSChris Mason 832ca7a79adSChris Mason BUG_ON(level == 0); 833ca7a79adSChris Mason 834db94535dSChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot), 835ca7a79adSChris Mason btrfs_level_size(root, level - 1), 836ca7a79adSChris Mason btrfs_node_ptr_generation(parent, slot)); 837bb803951SChris Mason } 838bb803951SChris Mason 839d352ac68SChris Mason /* 840d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 841d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 842d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 843d352ac68SChris Mason */ 844e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 84598ed5174SChris Mason struct btrfs_root *root, 84698ed5174SChris Mason struct btrfs_path *path, int level) 847bb803951SChris Mason { 8485f39d397SChris Mason struct extent_buffer *right = NULL; 8495f39d397SChris Mason struct extent_buffer *mid; 8505f39d397SChris Mason struct extent_buffer *left = NULL; 8515f39d397SChris Mason struct extent_buffer *parent = NULL; 852bb803951SChris Mason int ret = 0; 853bb803951SChris Mason int wret; 854bb803951SChris Mason int pslot; 855bb803951SChris Mason int orig_slot = path->slots[level]; 85654aa1f4dSChris Mason int err_on_enospc = 0; 85779f95c82SChris Mason u64 orig_ptr; 858bb803951SChris Mason 859bb803951SChris Mason if (level == 0) 860bb803951SChris Mason return 0; 861bb803951SChris Mason 8625f39d397SChris Mason mid = path->nodes[level]; 863925baeddSChris Mason WARN_ON(!path->locks[level]); 8647bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 8657bb86316SChris Mason 8661d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 86779f95c82SChris Mason 868234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 8695f39d397SChris Mason parent = path->nodes[level + 1]; 870bb803951SChris Mason pslot = path->slots[level + 1]; 871bb803951SChris Mason 87240689478SChris Mason /* 87340689478SChris Mason * deal with the case where there is only one pointer in the root 87440689478SChris Mason * by promoting the node below to a root 87540689478SChris Mason */ 8765f39d397SChris Mason if (!parent) { 8775f39d397SChris Mason struct extent_buffer *child; 878bb803951SChris Mason 8795f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 880bb803951SChris Mason return 0; 881bb803951SChris Mason 882bb803951SChris Mason /* promote the child to a root */ 8835f39d397SChris Mason child = read_node_slot(root, mid, 0); 884925baeddSChris Mason btrfs_tree_lock(child); 885bb803951SChris Mason BUG_ON(!child); 88665b51a00SChris Mason ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 0); 8872f375ab9SYan BUG_ON(ret); 8882f375ab9SYan 889925baeddSChris Mason spin_lock(&root->node_lock); 890bb803951SChris Mason root->node = child; 891925baeddSChris Mason spin_unlock(&root->node_lock); 892925baeddSChris Mason 89331840ae1SZheng Yan ret = btrfs_update_extent_ref(trans, root, child->start, 89431840ae1SZheng Yan mid->start, child->start, 89531840ae1SZheng Yan root->root_key.objectid, 8963bb1a1bcSYan Zheng trans->transid, level - 1); 89731840ae1SZheng Yan BUG_ON(ret); 89831840ae1SZheng Yan 8990b86a832SChris Mason add_root_to_dirty_list(root); 900925baeddSChris Mason btrfs_tree_unlock(child); 901925baeddSChris Mason path->locks[level] = 0; 902bb803951SChris Mason path->nodes[level] = NULL; 9035f39d397SChris Mason clean_tree_block(trans, root, mid); 904925baeddSChris Mason btrfs_tree_unlock(mid); 905bb803951SChris Mason /* once for the path */ 9065f39d397SChris Mason free_extent_buffer(mid); 9077bb86316SChris Mason ret = btrfs_free_extent(trans, root, mid->start, mid->len, 90831840ae1SZheng Yan mid->start, root->root_key.objectid, 9093bb1a1bcSYan Zheng btrfs_header_generation(mid), 9103bb1a1bcSYan Zheng level, 1); 911bb803951SChris Mason /* once for the root ptr */ 9125f39d397SChris Mason free_extent_buffer(mid); 913db94535dSChris Mason return ret; 914bb803951SChris Mason } 9155f39d397SChris Mason if (btrfs_header_nritems(mid) > 916123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 917bb803951SChris Mason return 0; 918bb803951SChris Mason 9195f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 92054aa1f4dSChris Mason err_on_enospc = 1; 92154aa1f4dSChris Mason 9225f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 9235f39d397SChris Mason if (left) { 924925baeddSChris Mason btrfs_tree_lock(left); 9255f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 92665b51a00SChris Mason parent, pslot - 1, &left, 0); 92754aa1f4dSChris Mason if (wret) { 92854aa1f4dSChris Mason ret = wret; 92954aa1f4dSChris Mason goto enospc; 93054aa1f4dSChris Mason } 9312cc58cf2SChris Mason } 9325f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 9335f39d397SChris Mason if (right) { 934925baeddSChris Mason btrfs_tree_lock(right); 9355f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 93665b51a00SChris Mason parent, pslot + 1, &right, 0); 9372cc58cf2SChris Mason if (wret) { 9382cc58cf2SChris Mason ret = wret; 9392cc58cf2SChris Mason goto enospc; 9402cc58cf2SChris Mason } 9412cc58cf2SChris Mason } 9422cc58cf2SChris Mason 9432cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 9445f39d397SChris Mason if (left) { 9455f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 946bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 94779f95c82SChris Mason if (wret < 0) 94879f95c82SChris Mason ret = wret; 9495f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 95054aa1f4dSChris Mason err_on_enospc = 1; 951bb803951SChris Mason } 95279f95c82SChris Mason 95379f95c82SChris Mason /* 95479f95c82SChris Mason * then try to empty the right most buffer into the middle 95579f95c82SChris Mason */ 9565f39d397SChris Mason if (right) { 957971a1f66SChris Mason wret = push_node_left(trans, root, mid, right, 1); 95854aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 95979f95c82SChris Mason ret = wret; 9605f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 961db94535dSChris Mason u64 bytenr = right->start; 9627bb86316SChris Mason u64 generation = btrfs_header_generation(parent); 963db94535dSChris Mason u32 blocksize = right->len; 964db94535dSChris Mason 9655f39d397SChris Mason clean_tree_block(trans, root, right); 966925baeddSChris Mason btrfs_tree_unlock(right); 9675f39d397SChris Mason free_extent_buffer(right); 968bb803951SChris Mason right = NULL; 969e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 970e089f05cSChris Mason 1); 971bb803951SChris Mason if (wret) 972bb803951SChris Mason ret = wret; 973db94535dSChris Mason wret = btrfs_free_extent(trans, root, bytenr, 97431840ae1SZheng Yan blocksize, parent->start, 9757bb86316SChris Mason btrfs_header_owner(parent), 9763bb1a1bcSYan Zheng generation, level, 1); 977bb803951SChris Mason if (wret) 978bb803951SChris Mason ret = wret; 979bb803951SChris Mason } else { 9805f39d397SChris Mason struct btrfs_disk_key right_key; 9815f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 9825f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 9835f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 984bb803951SChris Mason } 985bb803951SChris Mason } 9865f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 98779f95c82SChris Mason /* 98879f95c82SChris Mason * we're not allowed to leave a node with one item in the 98979f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 99079f95c82SChris Mason * could try to delete the only pointer in this node. 99179f95c82SChris Mason * So, pull some keys from the left. 99279f95c82SChris Mason * There has to be a left pointer at this point because 99379f95c82SChris Mason * otherwise we would have pulled some pointers from the 99479f95c82SChris Mason * right 99579f95c82SChris Mason */ 9965f39d397SChris Mason BUG_ON(!left); 9975f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 99854aa1f4dSChris Mason if (wret < 0) { 99979f95c82SChris Mason ret = wret; 100054aa1f4dSChris Mason goto enospc; 100154aa1f4dSChris Mason } 1002bce4eae9SChris Mason if (wret == 1) { 1003bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 1004bce4eae9SChris Mason if (wret < 0) 1005bce4eae9SChris Mason ret = wret; 1006bce4eae9SChris Mason } 100779f95c82SChris Mason BUG_ON(wret == 1); 100879f95c82SChris Mason } 10095f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 101079f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 10117bb86316SChris Mason u64 root_gen = btrfs_header_generation(parent); 1012db94535dSChris Mason u64 bytenr = mid->start; 1013db94535dSChris Mason u32 blocksize = mid->len; 1014925baeddSChris Mason 10155f39d397SChris Mason clean_tree_block(trans, root, mid); 1016925baeddSChris Mason btrfs_tree_unlock(mid); 10175f39d397SChris Mason free_extent_buffer(mid); 1018bb803951SChris Mason mid = NULL; 1019e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 1020bb803951SChris Mason if (wret) 1021bb803951SChris Mason ret = wret; 10227bb86316SChris Mason wret = btrfs_free_extent(trans, root, bytenr, blocksize, 102331840ae1SZheng Yan parent->start, 10247bb86316SChris Mason btrfs_header_owner(parent), 10253bb1a1bcSYan Zheng root_gen, level, 1); 1026bb803951SChris Mason if (wret) 1027bb803951SChris Mason ret = wret; 102879f95c82SChris Mason } else { 102979f95c82SChris Mason /* update the parent key to reflect our changes */ 10305f39d397SChris Mason struct btrfs_disk_key mid_key; 10315f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 10325f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 10335f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 103479f95c82SChris Mason } 1035bb803951SChris Mason 103679f95c82SChris Mason /* update the path */ 10375f39d397SChris Mason if (left) { 10385f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 10395f39d397SChris Mason extent_buffer_get(left); 1040925baeddSChris Mason /* left was locked after cow */ 10415f39d397SChris Mason path->nodes[level] = left; 1042bb803951SChris Mason path->slots[level + 1] -= 1; 1043bb803951SChris Mason path->slots[level] = orig_slot; 1044925baeddSChris Mason if (mid) { 1045925baeddSChris Mason btrfs_tree_unlock(mid); 10465f39d397SChris Mason free_extent_buffer(mid); 1047925baeddSChris Mason } 1048bb803951SChris Mason } else { 10495f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1050bb803951SChris Mason path->slots[level] = orig_slot; 1051bb803951SChris Mason } 1052bb803951SChris Mason } 105379f95c82SChris Mason /* double check we haven't messed things up */ 1054123abc88SChris Mason check_block(root, path, level); 1055e20d96d6SChris Mason if (orig_ptr != 10565f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 105779f95c82SChris Mason BUG(); 105854aa1f4dSChris Mason enospc: 1059925baeddSChris Mason if (right) { 1060925baeddSChris Mason btrfs_tree_unlock(right); 10615f39d397SChris Mason free_extent_buffer(right); 1062925baeddSChris Mason } 1063925baeddSChris Mason if (left) { 1064925baeddSChris Mason if (path->nodes[level] != left) 1065925baeddSChris Mason btrfs_tree_unlock(left); 10665f39d397SChris Mason free_extent_buffer(left); 1067925baeddSChris Mason } 1068bb803951SChris Mason return ret; 1069bb803951SChris Mason } 1070bb803951SChris Mason 1071d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1072d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1073d352ac68SChris Mason * have to be pessimistic. 1074d352ac68SChris Mason */ 1075d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1076e66f709bSChris Mason struct btrfs_root *root, 1077e66f709bSChris Mason struct btrfs_path *path, int level) 1078e66f709bSChris Mason { 10795f39d397SChris Mason struct extent_buffer *right = NULL; 10805f39d397SChris Mason struct extent_buffer *mid; 10815f39d397SChris Mason struct extent_buffer *left = NULL; 10825f39d397SChris Mason struct extent_buffer *parent = NULL; 1083e66f709bSChris Mason int ret = 0; 1084e66f709bSChris Mason int wret; 1085e66f709bSChris Mason int pslot; 1086e66f709bSChris Mason int orig_slot = path->slots[level]; 1087e66f709bSChris Mason u64 orig_ptr; 1088e66f709bSChris Mason 1089e66f709bSChris Mason if (level == 0) 1090e66f709bSChris Mason return 1; 1091e66f709bSChris Mason 10925f39d397SChris Mason mid = path->nodes[level]; 10937bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1094e66f709bSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 1095e66f709bSChris Mason 1096e66f709bSChris Mason if (level < BTRFS_MAX_LEVEL - 1) 10975f39d397SChris Mason parent = path->nodes[level + 1]; 1098e66f709bSChris Mason pslot = path->slots[level + 1]; 1099e66f709bSChris Mason 11005f39d397SChris Mason if (!parent) 1101e66f709bSChris Mason return 1; 1102e66f709bSChris Mason 11035f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 1104e66f709bSChris Mason 1105e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 11065f39d397SChris Mason if (left) { 1107e66f709bSChris Mason u32 left_nr; 1108925baeddSChris Mason 1109925baeddSChris Mason btrfs_tree_lock(left); 11105f39d397SChris Mason left_nr = btrfs_header_nritems(left); 111133ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 111233ade1f8SChris Mason wret = 1; 111333ade1f8SChris Mason } else { 11145f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 111565b51a00SChris Mason pslot - 1, &left, 0); 111654aa1f4dSChris Mason if (ret) 111754aa1f4dSChris Mason wret = 1; 111854aa1f4dSChris Mason else { 111954aa1f4dSChris Mason wret = push_node_left(trans, root, 1120971a1f66SChris Mason left, mid, 0); 112154aa1f4dSChris Mason } 112233ade1f8SChris Mason } 1123e66f709bSChris Mason if (wret < 0) 1124e66f709bSChris Mason ret = wret; 1125e66f709bSChris Mason if (wret == 0) { 11265f39d397SChris Mason struct btrfs_disk_key disk_key; 1127e66f709bSChris Mason orig_slot += left_nr; 11285f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 11295f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 11305f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 11315f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 11325f39d397SChris Mason path->nodes[level] = left; 1133e66f709bSChris Mason path->slots[level + 1] -= 1; 1134e66f709bSChris Mason path->slots[level] = orig_slot; 1135925baeddSChris Mason btrfs_tree_unlock(mid); 11365f39d397SChris Mason free_extent_buffer(mid); 1137e66f709bSChris Mason } else { 1138e66f709bSChris Mason orig_slot -= 11395f39d397SChris Mason btrfs_header_nritems(left); 1140e66f709bSChris Mason path->slots[level] = orig_slot; 1141925baeddSChris Mason btrfs_tree_unlock(left); 11425f39d397SChris Mason free_extent_buffer(left); 1143e66f709bSChris Mason } 1144e66f709bSChris Mason return 0; 1145e66f709bSChris Mason } 1146925baeddSChris Mason btrfs_tree_unlock(left); 11475f39d397SChris Mason free_extent_buffer(left); 1148e66f709bSChris Mason } 11495f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 1150e66f709bSChris Mason 1151e66f709bSChris Mason /* 1152e66f709bSChris Mason * then try to empty the right most buffer into the middle 1153e66f709bSChris Mason */ 11545f39d397SChris Mason if (right) { 115533ade1f8SChris Mason u32 right_nr; 1156925baeddSChris Mason btrfs_tree_lock(right); 11575f39d397SChris Mason right_nr = btrfs_header_nritems(right); 115833ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 115933ade1f8SChris Mason wret = 1; 116033ade1f8SChris Mason } else { 11615f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 11625f39d397SChris Mason parent, pslot + 1, 116365b51a00SChris Mason &right, 0); 116454aa1f4dSChris Mason if (ret) 116554aa1f4dSChris Mason wret = 1; 116654aa1f4dSChris Mason else { 116733ade1f8SChris Mason wret = balance_node_right(trans, root, 11685f39d397SChris Mason right, mid); 116933ade1f8SChris Mason } 117054aa1f4dSChris Mason } 1171e66f709bSChris Mason if (wret < 0) 1172e66f709bSChris Mason ret = wret; 1173e66f709bSChris Mason if (wret == 0) { 11745f39d397SChris Mason struct btrfs_disk_key disk_key; 11755f39d397SChris Mason 11765f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 11775f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 11785f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 11795f39d397SChris Mason 11805f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 11815f39d397SChris Mason path->nodes[level] = right; 1182e66f709bSChris Mason path->slots[level + 1] += 1; 1183e66f709bSChris Mason path->slots[level] = orig_slot - 11845f39d397SChris Mason btrfs_header_nritems(mid); 1185925baeddSChris Mason btrfs_tree_unlock(mid); 11865f39d397SChris Mason free_extent_buffer(mid); 1187e66f709bSChris Mason } else { 1188925baeddSChris Mason btrfs_tree_unlock(right); 11895f39d397SChris Mason free_extent_buffer(right); 1190e66f709bSChris Mason } 1191e66f709bSChris Mason return 0; 1192e66f709bSChris Mason } 1193925baeddSChris Mason btrfs_tree_unlock(right); 11945f39d397SChris Mason free_extent_buffer(right); 1195e66f709bSChris Mason } 1196e66f709bSChris Mason return 1; 1197e66f709bSChris Mason } 1198e66f709bSChris Mason 119974123bd7SChris Mason /* 1200d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1201d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 12023c69faecSChris Mason */ 1203e02119d5SChris Mason static noinline void reada_for_search(struct btrfs_root *root, 1204e02119d5SChris Mason struct btrfs_path *path, 120501f46658SChris Mason int level, int slot, u64 objectid) 12063c69faecSChris Mason { 12075f39d397SChris Mason struct extent_buffer *node; 120801f46658SChris Mason struct btrfs_disk_key disk_key; 12093c69faecSChris Mason u32 nritems; 12103c69faecSChris Mason u64 search; 1211a7175319SChris Mason u64 target; 12126b80053dSChris Mason u64 nread = 0; 12133c69faecSChris Mason int direction = path->reada; 12145f39d397SChris Mason struct extent_buffer *eb; 12156b80053dSChris Mason u32 nr; 12166b80053dSChris Mason u32 blocksize; 12176b80053dSChris Mason u32 nscan = 0; 1218db94535dSChris Mason 1219a6b6e75eSChris Mason if (level != 1) 12203c69faecSChris Mason return; 12213c69faecSChris Mason 12226702ed49SChris Mason if (!path->nodes[level]) 12236702ed49SChris Mason return; 12246702ed49SChris Mason 12255f39d397SChris Mason node = path->nodes[level]; 1226925baeddSChris Mason 12273c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 12286b80053dSChris Mason blocksize = btrfs_level_size(root, level - 1); 12296b80053dSChris Mason eb = btrfs_find_tree_block(root, search, blocksize); 12305f39d397SChris Mason if (eb) { 12315f39d397SChris Mason free_extent_buffer(eb); 12323c69faecSChris Mason return; 12333c69faecSChris Mason } 12343c69faecSChris Mason 1235a7175319SChris Mason target = search; 12366b80053dSChris Mason 12375f39d397SChris Mason nritems = btrfs_header_nritems(node); 12386b80053dSChris Mason nr = slot; 12393c69faecSChris Mason while (1) { 12406b80053dSChris Mason if (direction < 0) { 12416b80053dSChris Mason if (nr == 0) 12423c69faecSChris Mason break; 12436b80053dSChris Mason nr--; 12446b80053dSChris Mason } else if (direction > 0) { 12456b80053dSChris Mason nr++; 12466b80053dSChris Mason if (nr >= nritems) 12476b80053dSChris Mason break; 12483c69faecSChris Mason } 124901f46658SChris Mason if (path->reada < 0 && objectid) { 125001f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 125101f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 125201f46658SChris Mason break; 125301f46658SChris Mason } 12546b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1255a7175319SChris Mason if ((search <= target && target - search <= 65536) || 1256a7175319SChris Mason (search > target && search - target <= 65536)) { 1257ca7a79adSChris Mason readahead_tree_block(root, search, blocksize, 1258ca7a79adSChris Mason btrfs_node_ptr_generation(node, nr)); 12596b80053dSChris Mason nread += blocksize; 12603c69faecSChris Mason } 12616b80053dSChris Mason nscan++; 1262a7175319SChris Mason if ((nread > 65536 || nscan > 32)) 12636b80053dSChris Mason break; 12643c69faecSChris Mason } 12653c69faecSChris Mason } 1266925baeddSChris Mason 1267d352ac68SChris Mason /* 1268d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1269d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1270d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1271d397712bSChris Mason * tree. 1272d352ac68SChris Mason * 1273d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1274d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1275d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1276d352ac68SChris Mason * 1277d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1278d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1279d352ac68SChris Mason */ 1280e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1281e02119d5SChris Mason int lowest_unlock) 1282925baeddSChris Mason { 1283925baeddSChris Mason int i; 1284925baeddSChris Mason int skip_level = level; 1285051e1b9fSChris Mason int no_skips = 0; 1286925baeddSChris Mason struct extent_buffer *t; 1287925baeddSChris Mason 1288925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1289925baeddSChris Mason if (!path->nodes[i]) 1290925baeddSChris Mason break; 1291925baeddSChris Mason if (!path->locks[i]) 1292925baeddSChris Mason break; 1293051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1294925baeddSChris Mason skip_level = i + 1; 1295925baeddSChris Mason continue; 1296925baeddSChris Mason } 1297051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1298925baeddSChris Mason u32 nritems; 1299925baeddSChris Mason t = path->nodes[i]; 1300925baeddSChris Mason nritems = btrfs_header_nritems(t); 1301051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1302925baeddSChris Mason skip_level = i + 1; 1303925baeddSChris Mason continue; 1304925baeddSChris Mason } 1305925baeddSChris Mason } 1306051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1307051e1b9fSChris Mason no_skips = 1; 1308051e1b9fSChris Mason 1309925baeddSChris Mason t = path->nodes[i]; 1310925baeddSChris Mason if (i >= lowest_unlock && i > skip_level && path->locks[i]) { 1311925baeddSChris Mason btrfs_tree_unlock(t); 1312925baeddSChris Mason path->locks[i] = 0; 1313925baeddSChris Mason } 1314925baeddSChris Mason } 1315925baeddSChris Mason } 1316925baeddSChris Mason 13173c69faecSChris Mason /* 131874123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 131974123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 132074123bd7SChris Mason * level of the path (level 0) 132174123bd7SChris Mason * 132274123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 1323aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 1324aa5d6bedSChris Mason * search a negative error number is returned. 132597571fd0SChris Mason * 132697571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 132797571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 132897571fd0SChris Mason * possible) 132974123bd7SChris Mason */ 1330e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 1331e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 1332e089f05cSChris Mason ins_len, int cow) 1333be0e5c09SChris Mason { 13345f39d397SChris Mason struct extent_buffer *b; 1335051e1b9fSChris Mason struct extent_buffer *tmp; 1336be0e5c09SChris Mason int slot; 1337be0e5c09SChris Mason int ret; 1338be0e5c09SChris Mason int level; 13393c69faecSChris Mason int should_reada = p->reada; 1340925baeddSChris Mason int lowest_unlock = 1; 1341594a24ebSChris Mason int blocksize; 13429f3a7427SChris Mason u8 lowest_level = 0; 1343594a24ebSChris Mason u64 blocknr; 1344594a24ebSChris Mason u64 gen; 134565b51a00SChris Mason struct btrfs_key prealloc_block; 13469f3a7427SChris Mason 13476702ed49SChris Mason lowest_level = p->lowest_level; 1348323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 134922b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 135025179201SJosef Bacik 1351925baeddSChris Mason if (ins_len < 0) 1352925baeddSChris Mason lowest_unlock = 2; 135365b51a00SChris Mason 135465b51a00SChris Mason prealloc_block.objectid = 0; 135565b51a00SChris Mason 1356bb803951SChris Mason again: 13575cd57b2cSChris Mason if (p->skip_locking) 13585cd57b2cSChris Mason b = btrfs_root_node(root); 13595cd57b2cSChris Mason else 1360925baeddSChris Mason b = btrfs_lock_root_node(root); 1361925baeddSChris Mason 1362eb60ceacSChris Mason while (b) { 13635f39d397SChris Mason level = btrfs_header_level(b); 136465b51a00SChris Mason 136565b51a00SChris Mason /* 136665b51a00SChris Mason * setup the path here so we can release it under lock 136765b51a00SChris Mason * contention with the cow code 136865b51a00SChris Mason */ 136965b51a00SChris Mason p->nodes[level] = b; 137065b51a00SChris Mason if (!p->skip_locking) 137165b51a00SChris Mason p->locks[level] = 1; 137265b51a00SChris Mason 137302217ed2SChris Mason if (cow) { 137402217ed2SChris Mason int wret; 137565b51a00SChris Mason 137665b51a00SChris Mason /* is a cow on this block not required */ 137765b51a00SChris Mason if (btrfs_header_generation(b) == trans->transid && 13785b21f2edSZheng Yan btrfs_header_owner(b) == root->root_key.objectid && 137965b51a00SChris Mason !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) { 138065b51a00SChris Mason goto cow_done; 138165b51a00SChris Mason } 138265b51a00SChris Mason 138365b51a00SChris Mason /* ok, we have to cow, is our old prealloc the right 138465b51a00SChris Mason * size? 138565b51a00SChris Mason */ 138665b51a00SChris Mason if (prealloc_block.objectid && 138765b51a00SChris Mason prealloc_block.offset != b->len) { 138865b51a00SChris Mason btrfs_free_reserved_extent(root, 138965b51a00SChris Mason prealloc_block.objectid, 139065b51a00SChris Mason prealloc_block.offset); 139165b51a00SChris Mason prealloc_block.objectid = 0; 139265b51a00SChris Mason } 139365b51a00SChris Mason 139465b51a00SChris Mason /* 139565b51a00SChris Mason * for higher level blocks, try not to allocate blocks 139665b51a00SChris Mason * with the block and the parent locks held. 139765b51a00SChris Mason */ 139865b51a00SChris Mason if (level > 1 && !prealloc_block.objectid && 139965b51a00SChris Mason btrfs_path_lock_waiting(p, level)) { 140065b51a00SChris Mason u32 size = b->len; 140165b51a00SChris Mason u64 hint = b->start; 140265b51a00SChris Mason 140365b51a00SChris Mason btrfs_release_path(root, p); 140465b51a00SChris Mason ret = btrfs_reserve_extent(trans, root, 140565b51a00SChris Mason size, size, 0, 140665b51a00SChris Mason hint, (u64)-1, 140765b51a00SChris Mason &prealloc_block, 0); 140865b51a00SChris Mason BUG_ON(ret); 140965b51a00SChris Mason goto again; 141065b51a00SChris Mason } 141165b51a00SChris Mason 1412e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 1413e20d96d6SChris Mason p->nodes[level + 1], 1414e20d96d6SChris Mason p->slots[level + 1], 141565b51a00SChris Mason &b, prealloc_block.objectid); 141665b51a00SChris Mason prealloc_block.objectid = 0; 141754aa1f4dSChris Mason if (wret) { 14185f39d397SChris Mason free_extent_buffer(b); 141965b51a00SChris Mason ret = wret; 142065b51a00SChris Mason goto done; 142154aa1f4dSChris Mason } 142202217ed2SChris Mason } 142365b51a00SChris Mason cow_done: 142402217ed2SChris Mason BUG_ON(!cow && ins_len); 14255f39d397SChris Mason if (level != btrfs_header_level(b)) 14262c90e5d6SChris Mason WARN_ON(1); 14275f39d397SChris Mason level = btrfs_header_level(b); 142865b51a00SChris Mason 1429eb60ceacSChris Mason p->nodes[level] = b; 14305cd57b2cSChris Mason if (!p->skip_locking) 1431925baeddSChris Mason p->locks[level] = 1; 143265b51a00SChris Mason 1433123abc88SChris Mason ret = check_block(root, p, level); 143465b51a00SChris Mason if (ret) { 143565b51a00SChris Mason ret = -1; 143665b51a00SChris Mason goto done; 143765b51a00SChris Mason } 1438925baeddSChris Mason 14395f39d397SChris Mason ret = bin_search(b, key, level, &slot); 14405f39d397SChris Mason if (level != 0) { 1441be0e5c09SChris Mason if (ret && slot > 0) 1442be0e5c09SChris Mason slot -= 1; 1443be0e5c09SChris Mason p->slots[level] = slot; 1444459931ecSChris Mason if ((p->search_for_split || ins_len > 0) && 1445459931ecSChris Mason btrfs_header_nritems(b) >= 14461514794eSChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { 1447e089f05cSChris Mason int sret = split_node(trans, root, p, level); 14485c680ed6SChris Mason BUG_ON(sret > 0); 144965b51a00SChris Mason if (sret) { 145065b51a00SChris Mason ret = sret; 145165b51a00SChris Mason goto done; 145265b51a00SChris Mason } 14535c680ed6SChris Mason b = p->nodes[level]; 14545c680ed6SChris Mason slot = p->slots[level]; 1455bb803951SChris Mason } else if (ins_len < 0) { 1456e089f05cSChris Mason int sret = balance_level(trans, root, p, 1457e089f05cSChris Mason level); 145865b51a00SChris Mason if (sret) { 145965b51a00SChris Mason ret = sret; 146065b51a00SChris Mason goto done; 146165b51a00SChris Mason } 1462bb803951SChris Mason b = p->nodes[level]; 1463f510cfecSChris Mason if (!b) { 1464f510cfecSChris Mason btrfs_release_path(NULL, p); 1465bb803951SChris Mason goto again; 1466f510cfecSChris Mason } 1467bb803951SChris Mason slot = p->slots[level]; 14685f39d397SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 14695c680ed6SChris Mason } 1470f9efa9c7SChris Mason unlock_up(p, level, lowest_unlock); 1471f9efa9c7SChris Mason 14729f3a7427SChris Mason /* this is only true while dropping a snapshot */ 1473925baeddSChris Mason if (level == lowest_level) { 14745b21f2edSZheng Yan ret = 0; 14755b21f2edSZheng Yan goto done; 1476925baeddSChris Mason } 1477ca7a79adSChris Mason 1478594a24ebSChris Mason blocknr = btrfs_node_blockptr(b, slot); 1479594a24ebSChris Mason gen = btrfs_node_ptr_generation(b, slot); 1480594a24ebSChris Mason blocksize = btrfs_level_size(root, level - 1); 1481594a24ebSChris Mason 1482594a24ebSChris Mason tmp = btrfs_find_tree_block(root, blocknr, blocksize); 1483594a24ebSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 1484051e1b9fSChris Mason b = tmp; 1485051e1b9fSChris Mason } else { 1486051e1b9fSChris Mason /* 1487051e1b9fSChris Mason * reduce lock contention at high levels 1488051e1b9fSChris Mason * of the btree by dropping locks before 1489051e1b9fSChris Mason * we read. 1490051e1b9fSChris Mason */ 1491051e1b9fSChris Mason if (level > 1) { 1492051e1b9fSChris Mason btrfs_release_path(NULL, p); 1493051e1b9fSChris Mason if (tmp) 1494051e1b9fSChris Mason free_extent_buffer(tmp); 1495f9efa9c7SChris Mason if (should_reada) 1496f9efa9c7SChris Mason reada_for_search(root, p, 1497f9efa9c7SChris Mason level, slot, 1498f9efa9c7SChris Mason key->objectid); 1499f9efa9c7SChris Mason 1500594a24ebSChris Mason tmp = read_tree_block(root, blocknr, 1501594a24ebSChris Mason blocksize, gen); 1502594a24ebSChris Mason if (tmp) 1503594a24ebSChris Mason free_extent_buffer(tmp); 1504051e1b9fSChris Mason goto again; 1505051e1b9fSChris Mason } else { 1506a74a4b97SChris Mason if (tmp) 1507a74a4b97SChris Mason free_extent_buffer(tmp); 1508f9efa9c7SChris Mason if (should_reada) 1509f9efa9c7SChris Mason reada_for_search(root, p, 1510f9efa9c7SChris Mason level, slot, 1511f9efa9c7SChris Mason key->objectid); 1512ca7a79adSChris Mason b = read_node_slot(root, b, slot); 1513051e1b9fSChris Mason } 1514051e1b9fSChris Mason } 15155cd57b2cSChris Mason if (!p->skip_locking) 1516925baeddSChris Mason btrfs_tree_lock(b); 1517be0e5c09SChris Mason } else { 1518be0e5c09SChris Mason p->slots[level] = slot; 151987b29b20SYan Zheng if (ins_len > 0 && 152087b29b20SYan Zheng btrfs_leaf_free_space(root, b) < ins_len) { 1521d4dbff95SChris Mason int sret = split_leaf(trans, root, key, 1522cc0c5538SChris Mason p, ins_len, ret == 0); 15235c680ed6SChris Mason BUG_ON(sret > 0); 152465b51a00SChris Mason if (sret) { 152565b51a00SChris Mason ret = sret; 152665b51a00SChris Mason goto done; 152765b51a00SChris Mason } 15285c680ed6SChris Mason } 1529459931ecSChris Mason if (!p->search_for_split) 1530925baeddSChris Mason unlock_up(p, level, lowest_unlock); 153165b51a00SChris Mason goto done; 153265b51a00SChris Mason } 153365b51a00SChris Mason } 153465b51a00SChris Mason ret = 1; 153565b51a00SChris Mason done: 153665b51a00SChris Mason if (prealloc_block.objectid) { 153765b51a00SChris Mason btrfs_free_reserved_extent(root, 153865b51a00SChris Mason prealloc_block.objectid, 153965b51a00SChris Mason prealloc_block.offset); 154065b51a00SChris Mason } 154165b51a00SChris Mason 1542be0e5c09SChris Mason return ret; 1543be0e5c09SChris Mason } 1544be0e5c09SChris Mason 15451a40e23bSZheng Yan int btrfs_merge_path(struct btrfs_trans_handle *trans, 15461a40e23bSZheng Yan struct btrfs_root *root, 15471a40e23bSZheng Yan struct btrfs_key *node_keys, 15481a40e23bSZheng Yan u64 *nodes, int lowest_level) 15491a40e23bSZheng Yan { 15501a40e23bSZheng Yan struct extent_buffer *eb; 15511a40e23bSZheng Yan struct extent_buffer *parent; 15521a40e23bSZheng Yan struct btrfs_key key; 15531a40e23bSZheng Yan u64 bytenr; 15541a40e23bSZheng Yan u64 generation; 15551a40e23bSZheng Yan u32 blocksize; 15561a40e23bSZheng Yan int level; 15571a40e23bSZheng Yan int slot; 15581a40e23bSZheng Yan int key_match; 15591a40e23bSZheng Yan int ret; 15601a40e23bSZheng Yan 15611a40e23bSZheng Yan eb = btrfs_lock_root_node(root); 15621a40e23bSZheng Yan ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb, 0); 15631a40e23bSZheng Yan BUG_ON(ret); 15641a40e23bSZheng Yan 15651a40e23bSZheng Yan parent = eb; 15661a40e23bSZheng Yan while (1) { 15671a40e23bSZheng Yan level = btrfs_header_level(parent); 15681a40e23bSZheng Yan if (level == 0 || level <= lowest_level) 15691a40e23bSZheng Yan break; 15701a40e23bSZheng Yan 15711a40e23bSZheng Yan ret = bin_search(parent, &node_keys[lowest_level], level, 15721a40e23bSZheng Yan &slot); 15731a40e23bSZheng Yan if (ret && slot > 0) 15741a40e23bSZheng Yan slot--; 15751a40e23bSZheng Yan 15761a40e23bSZheng Yan bytenr = btrfs_node_blockptr(parent, slot); 15771a40e23bSZheng Yan if (nodes[level - 1] == bytenr) 15781a40e23bSZheng Yan break; 15791a40e23bSZheng Yan 15801a40e23bSZheng Yan blocksize = btrfs_level_size(root, level - 1); 15811a40e23bSZheng Yan generation = btrfs_node_ptr_generation(parent, slot); 15821a40e23bSZheng Yan btrfs_node_key_to_cpu(eb, &key, slot); 15831a40e23bSZheng Yan key_match = !memcmp(&key, &node_keys[level - 1], sizeof(key)); 15841a40e23bSZheng Yan 1585f82d02d9SYan Zheng if (generation == trans->transid) { 15861a40e23bSZheng Yan eb = read_tree_block(root, bytenr, blocksize, 15871a40e23bSZheng Yan generation); 15881a40e23bSZheng Yan btrfs_tree_lock(eb); 1589f82d02d9SYan Zheng } 1590f82d02d9SYan Zheng 1591f82d02d9SYan Zheng /* 1592f82d02d9SYan Zheng * if node keys match and node pointer hasn't been modified 1593f82d02d9SYan Zheng * in the running transaction, we can merge the path. for 1594f82d02d9SYan Zheng * blocks owened by reloc trees, the node pointer check is 1595f82d02d9SYan Zheng * skipped, this is because these blocks are fully controlled 1596f82d02d9SYan Zheng * by the space balance code, no one else can modify them. 1597f82d02d9SYan Zheng */ 1598f82d02d9SYan Zheng if (!nodes[level - 1] || !key_match || 1599f82d02d9SYan Zheng (generation == trans->transid && 1600f82d02d9SYan Zheng btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID)) { 1601f82d02d9SYan Zheng if (level == 1 || level == lowest_level + 1) { 1602f82d02d9SYan Zheng if (generation == trans->transid) { 1603f82d02d9SYan Zheng btrfs_tree_unlock(eb); 1604f82d02d9SYan Zheng free_extent_buffer(eb); 1605f82d02d9SYan Zheng } 1606f82d02d9SYan Zheng break; 1607f82d02d9SYan Zheng } 1608f82d02d9SYan Zheng 1609f82d02d9SYan Zheng if (generation != trans->transid) { 1610f82d02d9SYan Zheng eb = read_tree_block(root, bytenr, blocksize, 1611f82d02d9SYan Zheng generation); 1612f82d02d9SYan Zheng btrfs_tree_lock(eb); 1613f82d02d9SYan Zheng } 16141a40e23bSZheng Yan 16151a40e23bSZheng Yan ret = btrfs_cow_block(trans, root, eb, parent, slot, 16161a40e23bSZheng Yan &eb, 0); 16171a40e23bSZheng Yan BUG_ON(ret); 16181a40e23bSZheng Yan 1619f82d02d9SYan Zheng if (root->root_key.objectid == 1620f82d02d9SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 1621f82d02d9SYan Zheng if (!nodes[level - 1]) { 1622f82d02d9SYan Zheng nodes[level - 1] = eb->start; 1623f82d02d9SYan Zheng memcpy(&node_keys[level - 1], &key, 1624f82d02d9SYan Zheng sizeof(node_keys[0])); 1625f82d02d9SYan Zheng } else { 1626f82d02d9SYan Zheng WARN_ON(1); 1627f82d02d9SYan Zheng } 1628f82d02d9SYan Zheng } 1629f82d02d9SYan Zheng 16301a40e23bSZheng Yan btrfs_tree_unlock(parent); 16311a40e23bSZheng Yan free_extent_buffer(parent); 16321a40e23bSZheng Yan parent = eb; 16331a40e23bSZheng Yan continue; 16341a40e23bSZheng Yan } 16351a40e23bSZheng Yan 16361a40e23bSZheng Yan btrfs_set_node_blockptr(parent, slot, nodes[level - 1]); 16371a40e23bSZheng Yan btrfs_set_node_ptr_generation(parent, slot, trans->transid); 16381a40e23bSZheng Yan btrfs_mark_buffer_dirty(parent); 16391a40e23bSZheng Yan 16401a40e23bSZheng Yan ret = btrfs_inc_extent_ref(trans, root, 16411a40e23bSZheng Yan nodes[level - 1], 16421a40e23bSZheng Yan blocksize, parent->start, 16431a40e23bSZheng Yan btrfs_header_owner(parent), 16441a40e23bSZheng Yan btrfs_header_generation(parent), 16453bb1a1bcSYan Zheng level - 1); 16461a40e23bSZheng Yan BUG_ON(ret); 1647f82d02d9SYan Zheng 1648f82d02d9SYan Zheng /* 1649f82d02d9SYan Zheng * If the block was created in the running transaction, 1650f82d02d9SYan Zheng * it's possible this is the last reference to it, so we 1651f82d02d9SYan Zheng * should drop the subtree. 1652f82d02d9SYan Zheng */ 1653f82d02d9SYan Zheng if (generation == trans->transid) { 1654f82d02d9SYan Zheng ret = btrfs_drop_subtree(trans, root, eb, parent); 1655f82d02d9SYan Zheng BUG_ON(ret); 1656f82d02d9SYan Zheng btrfs_tree_unlock(eb); 1657f82d02d9SYan Zheng free_extent_buffer(eb); 1658f82d02d9SYan Zheng } else { 16591a40e23bSZheng Yan ret = btrfs_free_extent(trans, root, bytenr, 16601a40e23bSZheng Yan blocksize, parent->start, 16611a40e23bSZheng Yan btrfs_header_owner(parent), 16621a40e23bSZheng Yan btrfs_header_generation(parent), 16633bb1a1bcSYan Zheng level - 1, 1); 16641a40e23bSZheng Yan BUG_ON(ret); 16651a40e23bSZheng Yan } 16661a40e23bSZheng Yan break; 16671a40e23bSZheng Yan } 16681a40e23bSZheng Yan btrfs_tree_unlock(parent); 16691a40e23bSZheng Yan free_extent_buffer(parent); 16701a40e23bSZheng Yan return 0; 16711a40e23bSZheng Yan } 16721a40e23bSZheng Yan 167374123bd7SChris Mason /* 167474123bd7SChris Mason * adjust the pointers going up the tree, starting at level 167574123bd7SChris Mason * making sure the right key of each node is points to 'key'. 167674123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 167774123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 167874123bd7SChris Mason * higher levels 1679aa5d6bedSChris Mason * 1680aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 1681aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 168274123bd7SChris Mason */ 16835f39d397SChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, 16845f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 16855f39d397SChris Mason struct btrfs_disk_key *key, int level) 1686be0e5c09SChris Mason { 1687be0e5c09SChris Mason int i; 1688aa5d6bedSChris Mason int ret = 0; 16895f39d397SChris Mason struct extent_buffer *t; 16905f39d397SChris Mason 1691234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1692be0e5c09SChris Mason int tslot = path->slots[i]; 1693eb60ceacSChris Mason if (!path->nodes[i]) 1694be0e5c09SChris Mason break; 16955f39d397SChris Mason t = path->nodes[i]; 16965f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 1697d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 1698be0e5c09SChris Mason if (tslot != 0) 1699be0e5c09SChris Mason break; 1700be0e5c09SChris Mason } 1701aa5d6bedSChris Mason return ret; 1702be0e5c09SChris Mason } 1703be0e5c09SChris Mason 170474123bd7SChris Mason /* 170531840ae1SZheng Yan * update item key. 170631840ae1SZheng Yan * 170731840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 170831840ae1SZheng Yan * that the new key won't break the order 170931840ae1SZheng Yan */ 171031840ae1SZheng Yan int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, 171131840ae1SZheng Yan struct btrfs_root *root, struct btrfs_path *path, 171231840ae1SZheng Yan struct btrfs_key *new_key) 171331840ae1SZheng Yan { 171431840ae1SZheng Yan struct btrfs_disk_key disk_key; 171531840ae1SZheng Yan struct extent_buffer *eb; 171631840ae1SZheng Yan int slot; 171731840ae1SZheng Yan 171831840ae1SZheng Yan eb = path->nodes[0]; 171931840ae1SZheng Yan slot = path->slots[0]; 172031840ae1SZheng Yan if (slot > 0) { 172131840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 172231840ae1SZheng Yan if (comp_keys(&disk_key, new_key) >= 0) 172331840ae1SZheng Yan return -1; 172431840ae1SZheng Yan } 172531840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 172631840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 172731840ae1SZheng Yan if (comp_keys(&disk_key, new_key) <= 0) 172831840ae1SZheng Yan return -1; 172931840ae1SZheng Yan } 173031840ae1SZheng Yan 173131840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 173231840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 173331840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 173431840ae1SZheng Yan if (slot == 0) 173531840ae1SZheng Yan fixup_low_keys(trans, root, path, &disk_key, 1); 173631840ae1SZheng Yan return 0; 173731840ae1SZheng Yan } 173831840ae1SZheng Yan 173931840ae1SZheng Yan /* 174074123bd7SChris Mason * try to push data from one node into the next node left in the 174179f95c82SChris Mason * tree. 1742aa5d6bedSChris Mason * 1743aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1744aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 174574123bd7SChris Mason */ 174698ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 174798ed5174SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 1748971a1f66SChris Mason struct extent_buffer *src, int empty) 1749be0e5c09SChris Mason { 1750be0e5c09SChris Mason int push_items = 0; 1751bb803951SChris Mason int src_nritems; 1752bb803951SChris Mason int dst_nritems; 1753aa5d6bedSChris Mason int ret = 0; 1754be0e5c09SChris Mason 17555f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 17565f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1757123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 17587bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 17597bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 176054aa1f4dSChris Mason 1761bce4eae9SChris Mason if (!empty && src_nritems <= 8) 1762971a1f66SChris Mason return 1; 1763971a1f66SChris Mason 1764d397712bSChris Mason if (push_items <= 0) 1765be0e5c09SChris Mason return 1; 1766be0e5c09SChris Mason 1767bce4eae9SChris Mason if (empty) { 1768971a1f66SChris Mason push_items = min(src_nritems, push_items); 1769bce4eae9SChris Mason if (push_items < src_nritems) { 1770bce4eae9SChris Mason /* leave at least 8 pointers in the node if 1771bce4eae9SChris Mason * we aren't going to empty it 1772bce4eae9SChris Mason */ 1773bce4eae9SChris Mason if (src_nritems - push_items < 8) { 1774bce4eae9SChris Mason if (push_items <= 8) 1775bce4eae9SChris Mason return 1; 1776bce4eae9SChris Mason push_items -= 8; 1777bce4eae9SChris Mason } 1778bce4eae9SChris Mason } 1779bce4eae9SChris Mason } else 1780bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 178179f95c82SChris Mason 17825f39d397SChris Mason copy_extent_buffer(dst, src, 17835f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 17845f39d397SChris Mason btrfs_node_key_ptr_offset(0), 1785123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 17865f39d397SChris Mason 1787bb803951SChris Mason if (push_items < src_nritems) { 17885f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 17895f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 1790e2fa7227SChris Mason (src_nritems - push_items) * 1791123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1792bb803951SChris Mason } 17935f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 17945f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 17955f39d397SChris Mason btrfs_mark_buffer_dirty(src); 17965f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 179731840ae1SZheng Yan 179831840ae1SZheng Yan ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items); 179931840ae1SZheng Yan BUG_ON(ret); 180031840ae1SZheng Yan 1801bb803951SChris Mason return ret; 1802be0e5c09SChris Mason } 1803be0e5c09SChris Mason 180497571fd0SChris Mason /* 180579f95c82SChris Mason * try to push data from one node into the next node right in the 180679f95c82SChris Mason * tree. 180779f95c82SChris Mason * 180879f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 180979f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 181079f95c82SChris Mason * 181179f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 181279f95c82SChris Mason */ 18135f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 18145f39d397SChris Mason struct btrfs_root *root, 18155f39d397SChris Mason struct extent_buffer *dst, 18165f39d397SChris Mason struct extent_buffer *src) 181779f95c82SChris Mason { 181879f95c82SChris Mason int push_items = 0; 181979f95c82SChris Mason int max_push; 182079f95c82SChris Mason int src_nritems; 182179f95c82SChris Mason int dst_nritems; 182279f95c82SChris Mason int ret = 0; 182379f95c82SChris Mason 18247bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 18257bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 18267bb86316SChris Mason 18275f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 18285f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1829123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 1830d397712bSChris Mason if (push_items <= 0) 183179f95c82SChris Mason return 1; 1832bce4eae9SChris Mason 1833d397712bSChris Mason if (src_nritems < 4) 1834bce4eae9SChris Mason return 1; 183579f95c82SChris Mason 183679f95c82SChris Mason max_push = src_nritems / 2 + 1; 183779f95c82SChris Mason /* don't try to empty the node */ 1838d397712bSChris Mason if (max_push >= src_nritems) 183979f95c82SChris Mason return 1; 1840252c38f0SYan 184179f95c82SChris Mason if (max_push < push_items) 184279f95c82SChris Mason push_items = max_push; 184379f95c82SChris Mason 18445f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 18455f39d397SChris Mason btrfs_node_key_ptr_offset(0), 18465f39d397SChris Mason (dst_nritems) * 18475f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 1848d6025579SChris Mason 18495f39d397SChris Mason copy_extent_buffer(dst, src, 18505f39d397SChris Mason btrfs_node_key_ptr_offset(0), 18515f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 1852123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 185379f95c82SChris Mason 18545f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 18555f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 185679f95c82SChris Mason 18575f39d397SChris Mason btrfs_mark_buffer_dirty(src); 18585f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 185931840ae1SZheng Yan 186031840ae1SZheng Yan ret = btrfs_update_ref(trans, root, src, dst, 0, push_items); 186131840ae1SZheng Yan BUG_ON(ret); 186231840ae1SZheng Yan 186379f95c82SChris Mason return ret; 186479f95c82SChris Mason } 186579f95c82SChris Mason 186679f95c82SChris Mason /* 186797571fd0SChris Mason * helper function to insert a new root level in the tree. 186897571fd0SChris Mason * A new node is allocated, and a single item is inserted to 186997571fd0SChris Mason * point to the existing root 1870aa5d6bedSChris Mason * 1871aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 187297571fd0SChris Mason */ 1873d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 18745f39d397SChris Mason struct btrfs_root *root, 18755f39d397SChris Mason struct btrfs_path *path, int level) 187674123bd7SChris Mason { 18777bb86316SChris Mason u64 lower_gen; 18785f39d397SChris Mason struct extent_buffer *lower; 18795f39d397SChris Mason struct extent_buffer *c; 1880925baeddSChris Mason struct extent_buffer *old; 18815f39d397SChris Mason struct btrfs_disk_key lower_key; 188231840ae1SZheng Yan int ret; 18835c680ed6SChris Mason 18845c680ed6SChris Mason BUG_ON(path->nodes[level]); 18855c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 18865c680ed6SChris Mason 18877bb86316SChris Mason lower = path->nodes[level-1]; 18887bb86316SChris Mason if (level == 1) 18897bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 18907bb86316SChris Mason else 18917bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 18927bb86316SChris Mason 189331840ae1SZheng Yan c = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 189431840ae1SZheng Yan root->root_key.objectid, trans->transid, 1895ad3d81baSChristoph Hellwig level, root->node->start, 0); 18965f39d397SChris Mason if (IS_ERR(c)) 18975f39d397SChris Mason return PTR_ERR(c); 1898925baeddSChris Mason 18995f39d397SChris Mason memset_extent_buffer(c, 0, 0, root->nodesize); 19005f39d397SChris Mason btrfs_set_header_nritems(c, 1); 19015f39d397SChris Mason btrfs_set_header_level(c, level); 1902db94535dSChris Mason btrfs_set_header_bytenr(c, c->start); 19035f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 19045f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 1905d5719762SChris Mason 19065f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 19075f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 19085f39d397SChris Mason BTRFS_FSID_SIZE); 1909e17cade2SChris Mason 1910e17cade2SChris Mason write_extent_buffer(c, root->fs_info->chunk_tree_uuid, 1911e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(c), 1912e17cade2SChris Mason BTRFS_UUID_SIZE); 1913e17cade2SChris Mason 19145f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 1915db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 19167bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 191731840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 19187bb86316SChris Mason 19197bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 19205f39d397SChris Mason 19215f39d397SChris Mason btrfs_mark_buffer_dirty(c); 1922d5719762SChris Mason 1923925baeddSChris Mason spin_lock(&root->node_lock); 1924925baeddSChris Mason old = root->node; 19255f39d397SChris Mason root->node = c; 1926925baeddSChris Mason spin_unlock(&root->node_lock); 1927925baeddSChris Mason 192831840ae1SZheng Yan ret = btrfs_update_extent_ref(trans, root, lower->start, 192931840ae1SZheng Yan lower->start, c->start, 193031840ae1SZheng Yan root->root_key.objectid, 19313bb1a1bcSYan Zheng trans->transid, level - 1); 193231840ae1SZheng Yan BUG_ON(ret); 193331840ae1SZheng Yan 1934925baeddSChris Mason /* the super has an extra ref to root->node */ 1935925baeddSChris Mason free_extent_buffer(old); 1936925baeddSChris Mason 19370b86a832SChris Mason add_root_to_dirty_list(root); 19385f39d397SChris Mason extent_buffer_get(c); 19395f39d397SChris Mason path->nodes[level] = c; 1940925baeddSChris Mason path->locks[level] = 1; 194174123bd7SChris Mason path->slots[level] = 0; 194274123bd7SChris Mason return 0; 194374123bd7SChris Mason } 19445c680ed6SChris Mason 19455c680ed6SChris Mason /* 19465c680ed6SChris Mason * worker function to insert a single pointer in a node. 19475c680ed6SChris Mason * the node should have enough room for the pointer already 194897571fd0SChris Mason * 19495c680ed6SChris Mason * slot and level indicate where you want the key to go, and 19505c680ed6SChris Mason * blocknr is the block the key points to. 1951aa5d6bedSChris Mason * 1952aa5d6bedSChris Mason * returns zero on success and < 0 on any error 19535c680ed6SChris Mason */ 1954e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 1955e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 1956db94535dSChris Mason *key, u64 bytenr, int slot, int level) 19575c680ed6SChris Mason { 19585f39d397SChris Mason struct extent_buffer *lower; 19595c680ed6SChris Mason int nritems; 19605c680ed6SChris Mason 19615c680ed6SChris Mason BUG_ON(!path->nodes[level]); 19625f39d397SChris Mason lower = path->nodes[level]; 19635f39d397SChris Mason nritems = btrfs_header_nritems(lower); 196474123bd7SChris Mason if (slot > nritems) 196574123bd7SChris Mason BUG(); 1966123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 196774123bd7SChris Mason BUG(); 196874123bd7SChris Mason if (slot != nritems) { 19695f39d397SChris Mason memmove_extent_buffer(lower, 19705f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 19715f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 1972123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 197374123bd7SChris Mason } 19745f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 1975db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 197674493f7aSChris Mason WARN_ON(trans->transid == 0); 197774493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 19785f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 19795f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 198074123bd7SChris Mason return 0; 198174123bd7SChris Mason } 198274123bd7SChris Mason 198397571fd0SChris Mason /* 198497571fd0SChris Mason * split the node at the specified level in path in two. 198597571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 198697571fd0SChris Mason * 198797571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 198897571fd0SChris Mason * left and right, if either one works, it returns right away. 1989aa5d6bedSChris Mason * 1990aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 199197571fd0SChris Mason */ 1992e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 1993e02119d5SChris Mason struct btrfs_root *root, 1994e02119d5SChris Mason struct btrfs_path *path, int level) 1995be0e5c09SChris Mason { 19965f39d397SChris Mason struct extent_buffer *c; 19975f39d397SChris Mason struct extent_buffer *split; 19985f39d397SChris Mason struct btrfs_disk_key disk_key; 1999be0e5c09SChris Mason int mid; 20005c680ed6SChris Mason int ret; 2001aa5d6bedSChris Mason int wret; 20027518a238SChris Mason u32 c_nritems; 2003be0e5c09SChris Mason 20045f39d397SChris Mason c = path->nodes[level]; 20057bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 20065f39d397SChris Mason if (c == root->node) { 20075c680ed6SChris Mason /* trying to split the root, lets make a new one */ 2008e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 20095c680ed6SChris Mason if (ret) 20105c680ed6SChris Mason return ret; 2011e66f709bSChris Mason } else { 2012e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 20135f39d397SChris Mason c = path->nodes[level]; 20145f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 2015c448acf0SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) 2016e66f709bSChris Mason return 0; 201754aa1f4dSChris Mason if (ret < 0) 201854aa1f4dSChris Mason return ret; 20195c680ed6SChris Mason } 2020e66f709bSChris Mason 20215f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 20227bb86316SChris Mason 2023925baeddSChris Mason split = btrfs_alloc_free_block(trans, root, root->nodesize, 202431840ae1SZheng Yan path->nodes[level + 1]->start, 20257bb86316SChris Mason root->root_key.objectid, 202631840ae1SZheng Yan trans->transid, level, c->start, 0); 20275f39d397SChris Mason if (IS_ERR(split)) 20285f39d397SChris Mason return PTR_ERR(split); 202954aa1f4dSChris Mason 20305f39d397SChris Mason btrfs_set_header_flags(split, btrfs_header_flags(c)); 20315f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 2032db94535dSChris Mason btrfs_set_header_bytenr(split, split->start); 20335f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 20345f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 203563b10fc4SChris Mason btrfs_set_header_flags(split, 0); 20365f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 20375f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 20385f39d397SChris Mason BTRFS_FSID_SIZE); 2039e17cade2SChris Mason write_extent_buffer(split, root->fs_info->chunk_tree_uuid, 2040e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(split), 2041e17cade2SChris Mason BTRFS_UUID_SIZE); 20425f39d397SChris Mason 20437518a238SChris Mason mid = (c_nritems + 1) / 2; 20445f39d397SChris Mason 20455f39d397SChris Mason copy_extent_buffer(split, c, 20465f39d397SChris Mason btrfs_node_key_ptr_offset(0), 20475f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2048123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 20495f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 20505f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2051aa5d6bedSChris Mason ret = 0; 2052aa5d6bedSChris Mason 20535f39d397SChris Mason btrfs_mark_buffer_dirty(c); 20545f39d397SChris Mason btrfs_mark_buffer_dirty(split); 20555f39d397SChris Mason 20565f39d397SChris Mason btrfs_node_key(split, &disk_key, 0); 2057db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, split->start, 20585f39d397SChris Mason path->slots[level + 1] + 1, 2059123abc88SChris Mason level + 1); 2060aa5d6bedSChris Mason if (wret) 2061aa5d6bedSChris Mason ret = wret; 2062aa5d6bedSChris Mason 206331840ae1SZheng Yan ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid); 206431840ae1SZheng Yan BUG_ON(ret); 206531840ae1SZheng Yan 20665de08d7dSChris Mason if (path->slots[level] >= mid) { 20675c680ed6SChris Mason path->slots[level] -= mid; 2068925baeddSChris Mason btrfs_tree_unlock(c); 20695f39d397SChris Mason free_extent_buffer(c); 20705f39d397SChris Mason path->nodes[level] = split; 20715c680ed6SChris Mason path->slots[level + 1] += 1; 2072eb60ceacSChris Mason } else { 2073925baeddSChris Mason btrfs_tree_unlock(split); 20745f39d397SChris Mason free_extent_buffer(split); 2075be0e5c09SChris Mason } 2076aa5d6bedSChris Mason return ret; 2077be0e5c09SChris Mason } 2078be0e5c09SChris Mason 207974123bd7SChris Mason /* 208074123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 208174123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 208274123bd7SChris Mason * space used both by the item structs and the item data 208374123bd7SChris Mason */ 20845f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2085be0e5c09SChris Mason { 2086be0e5c09SChris Mason int data_len; 20875f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2088d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2089be0e5c09SChris Mason 2090be0e5c09SChris Mason if (!nr) 2091be0e5c09SChris Mason return 0; 20925f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 20935f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 20940783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2095d4dbff95SChris Mason WARN_ON(data_len < 0); 2096be0e5c09SChris Mason return data_len; 2097be0e5c09SChris Mason } 2098be0e5c09SChris Mason 209974123bd7SChris Mason /* 2100d4dbff95SChris Mason * The space between the end of the leaf items and 2101d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2102d4dbff95SChris Mason * the leaf has left for both items and data 2103d4dbff95SChris Mason */ 2104d397712bSChris Mason noinline int btrfs_leaf_free_space(struct btrfs_root *root, 2105e02119d5SChris Mason struct extent_buffer *leaf) 2106d4dbff95SChris Mason { 21075f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 21085f39d397SChris Mason int ret; 21095f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 21105f39d397SChris Mason if (ret < 0) { 2111d397712bSChris Mason printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, " 2112d397712bSChris Mason "used %d nritems %d\n", 2113ae2f5411SJens Axboe ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), 21145f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 21155f39d397SChris Mason } 21165f39d397SChris Mason return ret; 2117d4dbff95SChris Mason } 2118d4dbff95SChris Mason 2119d4dbff95SChris Mason /* 212000ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 212100ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 2122aa5d6bedSChris Mason * 2123aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 2124aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 212500ec4c51SChris Mason */ 2126e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 212734a38218SChris Mason *root, struct btrfs_path *path, int data_size, 212834a38218SChris Mason int empty) 212900ec4c51SChris Mason { 21305f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 21315f39d397SChris Mason struct extent_buffer *right; 21325f39d397SChris Mason struct extent_buffer *upper; 21335f39d397SChris Mason struct btrfs_disk_key disk_key; 213400ec4c51SChris Mason int slot; 213534a38218SChris Mason u32 i; 213600ec4c51SChris Mason int free_space; 213700ec4c51SChris Mason int push_space = 0; 213800ec4c51SChris Mason int push_items = 0; 21390783fcfcSChris Mason struct btrfs_item *item; 21407518a238SChris Mason u32 left_nritems; 214134a38218SChris Mason u32 nr; 21427518a238SChris Mason u32 right_nritems; 21435f39d397SChris Mason u32 data_end; 2144db94535dSChris Mason u32 this_item_size; 214554aa1f4dSChris Mason int ret; 214600ec4c51SChris Mason 214700ec4c51SChris Mason slot = path->slots[1]; 2148d397712bSChris Mason if (!path->nodes[1]) 214900ec4c51SChris Mason return 1; 2150d397712bSChris Mason 215100ec4c51SChris Mason upper = path->nodes[1]; 21525f39d397SChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 215300ec4c51SChris Mason return 1; 21545f39d397SChris Mason 2155a2135011SChris Mason WARN_ON(!btrfs_tree_locked(path->nodes[1])); 2156a2135011SChris Mason 2157ca7a79adSChris Mason right = read_node_slot(root, upper, slot + 1); 2158925baeddSChris Mason btrfs_tree_lock(right); 2159123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 216087b29b20SYan Zheng if (free_space < data_size) 2161925baeddSChris Mason goto out_unlock; 216202217ed2SChris Mason 21635f39d397SChris Mason /* cow and double check */ 21645f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, upper, 216565b51a00SChris Mason slot + 1, &right, 0); 2166925baeddSChris Mason if (ret) 2167925baeddSChris Mason goto out_unlock; 2168925baeddSChris Mason 21695f39d397SChris Mason free_space = btrfs_leaf_free_space(root, right); 217087b29b20SYan Zheng if (free_space < data_size) 2171925baeddSChris Mason goto out_unlock; 21725f39d397SChris Mason 21735f39d397SChris Mason left_nritems = btrfs_header_nritems(left); 2174925baeddSChris Mason if (left_nritems == 0) 2175925baeddSChris Mason goto out_unlock; 21765f39d397SChris Mason 217734a38218SChris Mason if (empty) 217834a38218SChris Mason nr = 0; 217934a38218SChris Mason else 218034a38218SChris Mason nr = 1; 218134a38218SChris Mason 218231840ae1SZheng Yan if (path->slots[0] >= left_nritems) 218387b29b20SYan Zheng push_space += data_size; 218431840ae1SZheng Yan 218534a38218SChris Mason i = left_nritems - 1; 218634a38218SChris Mason while (i >= nr) { 21875f39d397SChris Mason item = btrfs_item_nr(left, i); 2188db94535dSChris Mason 218931840ae1SZheng Yan if (!empty && push_items > 0) { 219031840ae1SZheng Yan if (path->slots[0] > i) 219131840ae1SZheng Yan break; 219231840ae1SZheng Yan if (path->slots[0] == i) { 219331840ae1SZheng Yan int space = btrfs_leaf_free_space(root, left); 219431840ae1SZheng Yan if (space + push_space * 2 > free_space) 219531840ae1SZheng Yan break; 219631840ae1SZheng Yan } 219731840ae1SZheng Yan } 219831840ae1SZheng Yan 219900ec4c51SChris Mason if (path->slots[0] == i) 220087b29b20SYan Zheng push_space += data_size; 2201db94535dSChris Mason 2202db94535dSChris Mason if (!left->map_token) { 2203db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 2204db94535dSChris Mason sizeof(struct btrfs_item), 2205db94535dSChris Mason &left->map_token, &left->kaddr, 2206db94535dSChris Mason &left->map_start, &left->map_len, 2207db94535dSChris Mason KM_USER1); 2208db94535dSChris Mason } 2209db94535dSChris Mason 2210db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 2211db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 221200ec4c51SChris Mason break; 221331840ae1SZheng Yan 221400ec4c51SChris Mason push_items++; 2215db94535dSChris Mason push_space += this_item_size + sizeof(*item); 221634a38218SChris Mason if (i == 0) 221734a38218SChris Mason break; 221834a38218SChris Mason i--; 2219db94535dSChris Mason } 2220db94535dSChris Mason if (left->map_token) { 2221db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 2222db94535dSChris Mason left->map_token = NULL; 222300ec4c51SChris Mason } 22245f39d397SChris Mason 2225925baeddSChris Mason if (push_items == 0) 2226925baeddSChris Mason goto out_unlock; 22275f39d397SChris Mason 222834a38218SChris Mason if (!empty && push_items == left_nritems) 2229a429e513SChris Mason WARN_ON(1); 22305f39d397SChris Mason 223100ec4c51SChris Mason /* push left to right */ 22325f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 223334a38218SChris Mason 22345f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 2235123abc88SChris Mason push_space -= leaf_data_end(root, left); 22365f39d397SChris Mason 223700ec4c51SChris Mason /* make room in the right data area */ 22385f39d397SChris Mason data_end = leaf_data_end(root, right); 22395f39d397SChris Mason memmove_extent_buffer(right, 22405f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 22415f39d397SChris Mason btrfs_leaf_data(right) + data_end, 22425f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 22435f39d397SChris Mason 224400ec4c51SChris Mason /* copy from the left data area */ 22455f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 2246d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2247d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 2248d6025579SChris Mason push_space); 22495f39d397SChris Mason 22505f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 22515f39d397SChris Mason btrfs_item_nr_offset(0), 22520783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 22535f39d397SChris Mason 225400ec4c51SChris Mason /* copy the items from left to right */ 22555f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 22565f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 22570783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 225800ec4c51SChris Mason 225900ec4c51SChris Mason /* update the item pointers */ 22607518a238SChris Mason right_nritems += push_items; 22615f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 2262123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 22637518a238SChris Mason for (i = 0; i < right_nritems; i++) { 22645f39d397SChris Mason item = btrfs_item_nr(right, i); 2265db94535dSChris Mason if (!right->map_token) { 2266db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2267db94535dSChris Mason sizeof(struct btrfs_item), 2268db94535dSChris Mason &right->map_token, &right->kaddr, 2269db94535dSChris Mason &right->map_start, &right->map_len, 2270db94535dSChris Mason KM_USER1); 2271db94535dSChris Mason } 2272db94535dSChris Mason push_space -= btrfs_item_size(right, item); 2273db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2274db94535dSChris Mason } 2275db94535dSChris Mason 2276db94535dSChris Mason if (right->map_token) { 2277db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2278db94535dSChris Mason right->map_token = NULL; 227900ec4c51SChris Mason } 22807518a238SChris Mason left_nritems -= push_items; 22815f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 228200ec4c51SChris Mason 228334a38218SChris Mason if (left_nritems) 22845f39d397SChris Mason btrfs_mark_buffer_dirty(left); 22855f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2286a429e513SChris Mason 228731840ae1SZheng Yan ret = btrfs_update_ref(trans, root, left, right, 0, push_items); 228831840ae1SZheng Yan BUG_ON(ret); 228931840ae1SZheng Yan 22905f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 22915f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2292d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 229302217ed2SChris Mason 229400ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 22957518a238SChris Mason if (path->slots[0] >= left_nritems) { 22967518a238SChris Mason path->slots[0] -= left_nritems; 2297925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2298925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2299925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 23005f39d397SChris Mason free_extent_buffer(path->nodes[0]); 23015f39d397SChris Mason path->nodes[0] = right; 230200ec4c51SChris Mason path->slots[1] += 1; 230300ec4c51SChris Mason } else { 2304925baeddSChris Mason btrfs_tree_unlock(right); 23055f39d397SChris Mason free_extent_buffer(right); 230600ec4c51SChris Mason } 230700ec4c51SChris Mason return 0; 2308925baeddSChris Mason 2309925baeddSChris Mason out_unlock: 2310925baeddSChris Mason btrfs_tree_unlock(right); 2311925baeddSChris Mason free_extent_buffer(right); 2312925baeddSChris Mason return 1; 231300ec4c51SChris Mason } 2314925baeddSChris Mason 231500ec4c51SChris Mason /* 231674123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 231774123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 231874123bd7SChris Mason */ 2319e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 232034a38218SChris Mason *root, struct btrfs_path *path, int data_size, 232134a38218SChris Mason int empty) 2322be0e5c09SChris Mason { 23235f39d397SChris Mason struct btrfs_disk_key disk_key; 23245f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 23255f39d397SChris Mason struct extent_buffer *left; 2326be0e5c09SChris Mason int slot; 2327be0e5c09SChris Mason int i; 2328be0e5c09SChris Mason int free_space; 2329be0e5c09SChris Mason int push_space = 0; 2330be0e5c09SChris Mason int push_items = 0; 23310783fcfcSChris Mason struct btrfs_item *item; 23327518a238SChris Mason u32 old_left_nritems; 23335f39d397SChris Mason u32 right_nritems; 233434a38218SChris Mason u32 nr; 2335aa5d6bedSChris Mason int ret = 0; 2336aa5d6bedSChris Mason int wret; 2337db94535dSChris Mason u32 this_item_size; 2338db94535dSChris Mason u32 old_left_item_size; 2339be0e5c09SChris Mason 2340be0e5c09SChris Mason slot = path->slots[1]; 23415f39d397SChris Mason if (slot == 0) 2342be0e5c09SChris Mason return 1; 23435f39d397SChris Mason if (!path->nodes[1]) 2344be0e5c09SChris Mason return 1; 23455f39d397SChris Mason 23463685f791SChris Mason right_nritems = btrfs_header_nritems(right); 2347d397712bSChris Mason if (right_nritems == 0) 23483685f791SChris Mason return 1; 23493685f791SChris Mason 2350a2135011SChris Mason WARN_ON(!btrfs_tree_locked(path->nodes[1])); 2351a2135011SChris Mason 2352ca7a79adSChris Mason left = read_node_slot(root, path->nodes[1], slot - 1); 2353925baeddSChris Mason btrfs_tree_lock(left); 2354123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 235587b29b20SYan Zheng if (free_space < data_size) { 2356925baeddSChris Mason ret = 1; 2357925baeddSChris Mason goto out; 2358be0e5c09SChris Mason } 235902217ed2SChris Mason 236002217ed2SChris Mason /* cow and double check */ 23615f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, 236265b51a00SChris Mason path->nodes[1], slot - 1, &left, 0); 236354aa1f4dSChris Mason if (ret) { 236454aa1f4dSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 2365925baeddSChris Mason ret = 1; 2366925baeddSChris Mason goto out; 236754aa1f4dSChris Mason } 23683685f791SChris Mason 2369123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 237087b29b20SYan Zheng if (free_space < data_size) { 2371925baeddSChris Mason ret = 1; 2372925baeddSChris Mason goto out; 237302217ed2SChris Mason } 237402217ed2SChris Mason 237534a38218SChris Mason if (empty) 237634a38218SChris Mason nr = right_nritems; 237734a38218SChris Mason else 237834a38218SChris Mason nr = right_nritems - 1; 237934a38218SChris Mason 238034a38218SChris Mason for (i = 0; i < nr; i++) { 23815f39d397SChris Mason item = btrfs_item_nr(right, i); 2382db94535dSChris Mason if (!right->map_token) { 2383db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2384db94535dSChris Mason sizeof(struct btrfs_item), 2385db94535dSChris Mason &right->map_token, &right->kaddr, 2386db94535dSChris Mason &right->map_start, &right->map_len, 2387db94535dSChris Mason KM_USER1); 2388db94535dSChris Mason } 2389db94535dSChris Mason 239031840ae1SZheng Yan if (!empty && push_items > 0) { 239131840ae1SZheng Yan if (path->slots[0] < i) 239231840ae1SZheng Yan break; 239331840ae1SZheng Yan if (path->slots[0] == i) { 239431840ae1SZheng Yan int space = btrfs_leaf_free_space(root, right); 239531840ae1SZheng Yan if (space + push_space * 2 > free_space) 239631840ae1SZheng Yan break; 239731840ae1SZheng Yan } 239831840ae1SZheng Yan } 239931840ae1SZheng Yan 2400be0e5c09SChris Mason if (path->slots[0] == i) 240187b29b20SYan Zheng push_space += data_size; 2402db94535dSChris Mason 2403db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 2404db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 2405be0e5c09SChris Mason break; 2406db94535dSChris Mason 2407be0e5c09SChris Mason push_items++; 2408db94535dSChris Mason push_space += this_item_size + sizeof(*item); 2409be0e5c09SChris Mason } 2410db94535dSChris Mason 2411db94535dSChris Mason if (right->map_token) { 2412db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2413db94535dSChris Mason right->map_token = NULL; 2414db94535dSChris Mason } 2415db94535dSChris Mason 2416be0e5c09SChris Mason if (push_items == 0) { 2417925baeddSChris Mason ret = 1; 2418925baeddSChris Mason goto out; 2419be0e5c09SChris Mason } 242034a38218SChris Mason if (!empty && push_items == btrfs_header_nritems(right)) 2421a429e513SChris Mason WARN_ON(1); 24225f39d397SChris Mason 2423be0e5c09SChris Mason /* push data from right to left */ 24245f39d397SChris Mason copy_extent_buffer(left, right, 24255f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 24265f39d397SChris Mason btrfs_item_nr_offset(0), 24275f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 24285f39d397SChris Mason 2429123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 24305f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1); 24315f39d397SChris Mason 24325f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 2433d6025579SChris Mason leaf_data_end(root, left) - push_space, 2434123abc88SChris Mason btrfs_leaf_data(right) + 24355f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 2436be0e5c09SChris Mason push_space); 24375f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 243887b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 2439eb60ceacSChris Mason 2440db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 2441be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 24425f39d397SChris Mason u32 ioff; 2443db94535dSChris Mason 24445f39d397SChris Mason item = btrfs_item_nr(left, i); 2445db94535dSChris Mason if (!left->map_token) { 2446db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 2447db94535dSChris Mason sizeof(struct btrfs_item), 2448db94535dSChris Mason &left->map_token, &left->kaddr, 2449db94535dSChris Mason &left->map_start, &left->map_len, 2450db94535dSChris Mason KM_USER1); 2451db94535dSChris Mason } 2452db94535dSChris Mason 24535f39d397SChris Mason ioff = btrfs_item_offset(left, item); 24545f39d397SChris Mason btrfs_set_item_offset(left, item, 2455db94535dSChris Mason ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size)); 2456be0e5c09SChris Mason } 24575f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 2458db94535dSChris Mason if (left->map_token) { 2459db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 2460db94535dSChris Mason left->map_token = NULL; 2461db94535dSChris Mason } 2462be0e5c09SChris Mason 2463be0e5c09SChris Mason /* fixup right node */ 246434a38218SChris Mason if (push_items > right_nritems) { 2465d397712bSChris Mason printk(KERN_CRIT "push items %d nr %u\n", push_items, 2466d397712bSChris Mason right_nritems); 246734a38218SChris Mason WARN_ON(1); 246834a38218SChris Mason } 246934a38218SChris Mason 247034a38218SChris Mason if (push_items < right_nritems) { 24715f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 2472123abc88SChris Mason leaf_data_end(root, right); 24735f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 2474d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2475d6025579SChris Mason btrfs_leaf_data(right) + 2476123abc88SChris Mason leaf_data_end(root, right), push_space); 24775f39d397SChris Mason 24785f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 24795f39d397SChris Mason btrfs_item_nr_offset(push_items), 24805f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 24810783fcfcSChris Mason sizeof(struct btrfs_item)); 248234a38218SChris Mason } 2483eef1c494SYan right_nritems -= push_items; 2484eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 2485123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 24865f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 24875f39d397SChris Mason item = btrfs_item_nr(right, i); 2488db94535dSChris Mason 2489db94535dSChris Mason if (!right->map_token) { 2490db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2491db94535dSChris Mason sizeof(struct btrfs_item), 2492db94535dSChris Mason &right->map_token, &right->kaddr, 2493db94535dSChris Mason &right->map_start, &right->map_len, 2494db94535dSChris Mason KM_USER1); 2495db94535dSChris Mason } 2496db94535dSChris Mason 2497db94535dSChris Mason push_space = push_space - btrfs_item_size(right, item); 2498db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2499db94535dSChris Mason } 2500db94535dSChris Mason if (right->map_token) { 2501db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2502db94535dSChris Mason right->map_token = NULL; 2503be0e5c09SChris Mason } 2504eb60ceacSChris Mason 25055f39d397SChris Mason btrfs_mark_buffer_dirty(left); 250634a38218SChris Mason if (right_nritems) 25075f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2508098f59c2SChris Mason 250931840ae1SZheng Yan ret = btrfs_update_ref(trans, root, right, left, 251031840ae1SZheng Yan old_left_nritems, push_items); 251131840ae1SZheng Yan BUG_ON(ret); 251231840ae1SZheng Yan 25135f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 25145f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 2515aa5d6bedSChris Mason if (wret) 2516aa5d6bedSChris Mason ret = wret; 2517be0e5c09SChris Mason 2518be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 2519be0e5c09SChris Mason if (path->slots[0] < push_items) { 2520be0e5c09SChris Mason path->slots[0] += old_left_nritems; 2521925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2522925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2523925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 25245f39d397SChris Mason free_extent_buffer(path->nodes[0]); 25255f39d397SChris Mason path->nodes[0] = left; 2526be0e5c09SChris Mason path->slots[1] -= 1; 2527be0e5c09SChris Mason } else { 2528925baeddSChris Mason btrfs_tree_unlock(left); 25295f39d397SChris Mason free_extent_buffer(left); 2530be0e5c09SChris Mason path->slots[0] -= push_items; 2531be0e5c09SChris Mason } 2532eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2533aa5d6bedSChris Mason return ret; 2534925baeddSChris Mason out: 2535925baeddSChris Mason btrfs_tree_unlock(left); 2536925baeddSChris Mason free_extent_buffer(left); 2537925baeddSChris Mason return ret; 2538be0e5c09SChris Mason } 2539be0e5c09SChris Mason 254074123bd7SChris Mason /* 254174123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 254274123bd7SChris Mason * available for the resulting leaf level of the path. 2543aa5d6bedSChris Mason * 2544aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 254574123bd7SChris Mason */ 2546e02119d5SChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 2547e02119d5SChris Mason struct btrfs_root *root, 2548e02119d5SChris Mason struct btrfs_key *ins_key, 2549e02119d5SChris Mason struct btrfs_path *path, int data_size, 2550e02119d5SChris Mason int extend) 2551be0e5c09SChris Mason { 25525f39d397SChris Mason struct extent_buffer *l; 25537518a238SChris Mason u32 nritems; 2554eb60ceacSChris Mason int mid; 2555eb60ceacSChris Mason int slot; 25565f39d397SChris Mason struct extent_buffer *right; 2557be0e5c09SChris Mason int data_copy_size; 2558be0e5c09SChris Mason int rt_data_off; 2559be0e5c09SChris Mason int i; 2560d4dbff95SChris Mason int ret = 0; 2561aa5d6bedSChris Mason int wret; 2562cc0c5538SChris Mason int double_split; 2563cc0c5538SChris Mason int num_doubles = 0; 2564d4dbff95SChris Mason struct btrfs_disk_key disk_key; 2565be0e5c09SChris Mason 256640689478SChris Mason /* first try to make some room by pushing left and right */ 2567459931ecSChris Mason if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) { 256834a38218SChris Mason wret = push_leaf_right(trans, root, path, data_size, 0); 2569d397712bSChris Mason if (wret < 0) 2570eaee50e8SChris Mason return wret; 2571eaee50e8SChris Mason if (wret) { 257234a38218SChris Mason wret = push_leaf_left(trans, root, path, data_size, 0); 2573eaee50e8SChris Mason if (wret < 0) 2574eaee50e8SChris Mason return wret; 2575eaee50e8SChris Mason } 25765f39d397SChris Mason l = path->nodes[0]; 2577aa5d6bedSChris Mason 2578aa5d6bedSChris Mason /* did the pushes work? */ 257987b29b20SYan Zheng if (btrfs_leaf_free_space(root, l) >= data_size) 2580be0e5c09SChris Mason return 0; 25813326d1b0SChris Mason } 2582aa5d6bedSChris Mason 25835c680ed6SChris Mason if (!path->nodes[1]) { 2584e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 25855c680ed6SChris Mason if (ret) 25865c680ed6SChris Mason return ret; 25875c680ed6SChris Mason } 2588cc0c5538SChris Mason again: 2589cc0c5538SChris Mason double_split = 0; 2590cc0c5538SChris Mason l = path->nodes[0]; 2591eb60ceacSChris Mason slot = path->slots[0]; 25925f39d397SChris Mason nritems = btrfs_header_nritems(l); 2593eb60ceacSChris Mason mid = (nritems + 1) / 2; 259454aa1f4dSChris Mason 2595925baeddSChris Mason right = btrfs_alloc_free_block(trans, root, root->leafsize, 259631840ae1SZheng Yan path->nodes[1]->start, 25977bb86316SChris Mason root->root_key.objectid, 259831840ae1SZheng Yan trans->transid, 0, l->start, 0); 2599cea9e445SChris Mason if (IS_ERR(right)) { 2600cea9e445SChris Mason BUG_ON(1); 26015f39d397SChris Mason return PTR_ERR(right); 2602cea9e445SChris Mason } 260354aa1f4dSChris Mason 26045f39d397SChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 2605db94535dSChris Mason btrfs_set_header_bytenr(right, right->start); 26065f39d397SChris Mason btrfs_set_header_generation(right, trans->transid); 26075f39d397SChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 26085f39d397SChris Mason btrfs_set_header_level(right, 0); 26095f39d397SChris Mason write_extent_buffer(right, root->fs_info->fsid, 26105f39d397SChris Mason (unsigned long)btrfs_header_fsid(right), 26115f39d397SChris Mason BTRFS_FSID_SIZE); 2612e17cade2SChris Mason 2613e17cade2SChris Mason write_extent_buffer(right, root->fs_info->chunk_tree_uuid, 2614e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(right), 2615e17cade2SChris Mason BTRFS_UUID_SIZE); 2616d4dbff95SChris Mason if (mid <= slot) { 2617d4dbff95SChris Mason if (nritems == 1 || 261887b29b20SYan Zheng leaf_space_used(l, mid, nritems - mid) + data_size > 2619d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 2620d4dbff95SChris Mason if (slot >= nritems) { 2621d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 26225f39d397SChris Mason btrfs_set_header_nritems(right, 0); 2623d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 2624db94535dSChris Mason &disk_key, right->start, 2625d4dbff95SChris Mason path->slots[1] + 1, 1); 2626d4dbff95SChris Mason if (wret) 2627d4dbff95SChris Mason ret = wret; 2628925baeddSChris Mason 2629925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 26305f39d397SChris Mason free_extent_buffer(path->nodes[0]); 26315f39d397SChris Mason path->nodes[0] = right; 2632d4dbff95SChris Mason path->slots[0] = 0; 2633d4dbff95SChris Mason path->slots[1] += 1; 26340ef8b242SChris Mason btrfs_mark_buffer_dirty(right); 2635d4dbff95SChris Mason return ret; 2636d4dbff95SChris Mason } 2637d4dbff95SChris Mason mid = slot; 26383326d1b0SChris Mason if (mid != nritems && 26393326d1b0SChris Mason leaf_space_used(l, mid, nritems - mid) + 264087b29b20SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 2641d4dbff95SChris Mason double_split = 1; 2642d4dbff95SChris Mason } 26433326d1b0SChris Mason } 2644d4dbff95SChris Mason } else { 264587b29b20SYan Zheng if (leaf_space_used(l, 0, mid) + data_size > 2646d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 2647459931ecSChris Mason if (!extend && data_size && slot == 0) { 2648d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 26495f39d397SChris Mason btrfs_set_header_nritems(right, 0); 2650d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 2651d4dbff95SChris Mason &disk_key, 2652db94535dSChris Mason right->start, 2653098f59c2SChris Mason path->slots[1], 1); 2654d4dbff95SChris Mason if (wret) 2655d4dbff95SChris Mason ret = wret; 2656925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 26575f39d397SChris Mason free_extent_buffer(path->nodes[0]); 26585f39d397SChris Mason path->nodes[0] = right; 2659d4dbff95SChris Mason path->slots[0] = 0; 2660a429e513SChris Mason if (path->slots[1] == 0) { 2661a429e513SChris Mason wret = fixup_low_keys(trans, root, 2662a429e513SChris Mason path, &disk_key, 1); 2663a429e513SChris Mason if (wret) 2664a429e513SChris Mason ret = wret; 2665a429e513SChris Mason } 26660ef8b242SChris Mason btrfs_mark_buffer_dirty(right); 2667d4dbff95SChris Mason return ret; 2668459931ecSChris Mason } else if ((extend || !data_size) && slot == 0) { 2669cc0c5538SChris Mason mid = 1; 2670cc0c5538SChris Mason } else { 2671d4dbff95SChris Mason mid = slot; 26725ee78ac7SChris Mason if (mid != nritems && 26735ee78ac7SChris Mason leaf_space_used(l, mid, nritems - mid) + 267487b29b20SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 2675d4dbff95SChris Mason double_split = 1; 2676d4dbff95SChris Mason } 2677d4dbff95SChris Mason } 26785ee78ac7SChris Mason } 2679cc0c5538SChris Mason } 26805f39d397SChris Mason nritems = nritems - mid; 26815f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 26825f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 26835f39d397SChris Mason 26845f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 26855f39d397SChris Mason btrfs_item_nr_offset(mid), 26865f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 26875f39d397SChris Mason 26885f39d397SChris Mason copy_extent_buffer(right, l, 2689d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 2690123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 2691123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 269274123bd7SChris Mason 26935f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 26945f39d397SChris Mason btrfs_item_end_nr(l, mid); 26955f39d397SChris Mason 26965f39d397SChris Mason for (i = 0; i < nritems; i++) { 26975f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 2698db94535dSChris Mason u32 ioff; 2699db94535dSChris Mason 2700db94535dSChris Mason if (!right->map_token) { 2701db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2702db94535dSChris Mason sizeof(struct btrfs_item), 2703db94535dSChris Mason &right->map_token, &right->kaddr, 2704db94535dSChris Mason &right->map_start, &right->map_len, 2705db94535dSChris Mason KM_USER1); 2706db94535dSChris Mason } 2707db94535dSChris Mason 2708db94535dSChris Mason ioff = btrfs_item_offset(right, item); 27095f39d397SChris Mason btrfs_set_item_offset(right, item, ioff + rt_data_off); 27100783fcfcSChris Mason } 271174123bd7SChris Mason 2712db94535dSChris Mason if (right->map_token) { 2713db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2714db94535dSChris Mason right->map_token = NULL; 2715db94535dSChris Mason } 2716db94535dSChris Mason 27175f39d397SChris Mason btrfs_set_header_nritems(l, mid); 2718aa5d6bedSChris Mason ret = 0; 27195f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 2720db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, right->start, 2721db94535dSChris Mason path->slots[1] + 1, 1); 2722aa5d6bedSChris Mason if (wret) 2723aa5d6bedSChris Mason ret = wret; 27245f39d397SChris Mason 27255f39d397SChris Mason btrfs_mark_buffer_dirty(right); 27265f39d397SChris Mason btrfs_mark_buffer_dirty(l); 2727eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 27285f39d397SChris Mason 272931840ae1SZheng Yan ret = btrfs_update_ref(trans, root, l, right, 0, nritems); 273031840ae1SZheng Yan BUG_ON(ret); 273131840ae1SZheng Yan 2732be0e5c09SChris Mason if (mid <= slot) { 2733925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 27345f39d397SChris Mason free_extent_buffer(path->nodes[0]); 27355f39d397SChris Mason path->nodes[0] = right; 2736be0e5c09SChris Mason path->slots[0] -= mid; 2737be0e5c09SChris Mason path->slots[1] += 1; 2738925baeddSChris Mason } else { 2739925baeddSChris Mason btrfs_tree_unlock(right); 27405f39d397SChris Mason free_extent_buffer(right); 2741925baeddSChris Mason } 27425f39d397SChris Mason 2743eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2744d4dbff95SChris Mason 2745cc0c5538SChris Mason if (double_split) { 2746cc0c5538SChris Mason BUG_ON(num_doubles != 0); 2747cc0c5538SChris Mason num_doubles++; 2748cc0c5538SChris Mason goto again; 27493326d1b0SChris Mason } 2750be0e5c09SChris Mason return ret; 2751be0e5c09SChris Mason } 2752be0e5c09SChris Mason 2753d352ac68SChris Mason /* 2754459931ecSChris Mason * This function splits a single item into two items, 2755459931ecSChris Mason * giving 'new_key' to the new item and splitting the 2756459931ecSChris Mason * old one at split_offset (from the start of the item). 2757459931ecSChris Mason * 2758459931ecSChris Mason * The path may be released by this operation. After 2759459931ecSChris Mason * the split, the path is pointing to the old item. The 2760459931ecSChris Mason * new item is going to be in the same node as the old one. 2761459931ecSChris Mason * 2762459931ecSChris Mason * Note, the item being split must be smaller enough to live alone on 2763459931ecSChris Mason * a tree block with room for one extra struct btrfs_item 2764459931ecSChris Mason * 2765459931ecSChris Mason * This allows us to split the item in place, keeping a lock on the 2766459931ecSChris Mason * leaf the entire time. 2767459931ecSChris Mason */ 2768459931ecSChris Mason int btrfs_split_item(struct btrfs_trans_handle *trans, 2769459931ecSChris Mason struct btrfs_root *root, 2770459931ecSChris Mason struct btrfs_path *path, 2771459931ecSChris Mason struct btrfs_key *new_key, 2772459931ecSChris Mason unsigned long split_offset) 2773459931ecSChris Mason { 2774459931ecSChris Mason u32 item_size; 2775459931ecSChris Mason struct extent_buffer *leaf; 2776459931ecSChris Mason struct btrfs_key orig_key; 2777459931ecSChris Mason struct btrfs_item *item; 2778459931ecSChris Mason struct btrfs_item *new_item; 2779459931ecSChris Mason int ret = 0; 2780459931ecSChris Mason int slot; 2781459931ecSChris Mason u32 nritems; 2782459931ecSChris Mason u32 orig_offset; 2783459931ecSChris Mason struct btrfs_disk_key disk_key; 2784459931ecSChris Mason char *buf; 2785459931ecSChris Mason 2786459931ecSChris Mason leaf = path->nodes[0]; 2787459931ecSChris Mason btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]); 2788459931ecSChris Mason if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item)) 2789459931ecSChris Mason goto split; 2790459931ecSChris Mason 2791459931ecSChris Mason item_size = btrfs_item_size_nr(leaf, path->slots[0]); 2792459931ecSChris Mason btrfs_release_path(root, path); 2793459931ecSChris Mason 2794459931ecSChris Mason path->search_for_split = 1; 2795459931ecSChris Mason path->keep_locks = 1; 2796459931ecSChris Mason 2797459931ecSChris Mason ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1); 2798459931ecSChris Mason path->search_for_split = 0; 2799459931ecSChris Mason 2800459931ecSChris Mason /* if our item isn't there or got smaller, return now */ 2801459931ecSChris Mason if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0], 2802459931ecSChris Mason path->slots[0])) { 2803459931ecSChris Mason path->keep_locks = 0; 2804459931ecSChris Mason return -EAGAIN; 2805459931ecSChris Mason } 2806459931ecSChris Mason 280787b29b20SYan Zheng ret = split_leaf(trans, root, &orig_key, path, 280887b29b20SYan Zheng sizeof(struct btrfs_item), 1); 2809459931ecSChris Mason path->keep_locks = 0; 2810459931ecSChris Mason BUG_ON(ret); 2811459931ecSChris Mason 2812459931ecSChris Mason leaf = path->nodes[0]; 281342dc7babSChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item)); 2814459931ecSChris Mason 2815459931ecSChris Mason split: 2816459931ecSChris Mason item = btrfs_item_nr(leaf, path->slots[0]); 2817459931ecSChris Mason orig_offset = btrfs_item_offset(leaf, item); 2818459931ecSChris Mason item_size = btrfs_item_size(leaf, item); 2819459931ecSChris Mason 2820459931ecSChris Mason 2821459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 2822459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 2823459931ecSChris Mason path->slots[0]), item_size); 2824459931ecSChris Mason slot = path->slots[0] + 1; 2825459931ecSChris Mason leaf = path->nodes[0]; 2826459931ecSChris Mason 2827459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 2828459931ecSChris Mason 2829459931ecSChris Mason if (slot != nritems) { 2830459931ecSChris Mason /* shift the items */ 2831459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 2832459931ecSChris Mason btrfs_item_nr_offset(slot), 2833459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 2834459931ecSChris Mason 2835459931ecSChris Mason } 2836459931ecSChris Mason 2837459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 2838459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 2839459931ecSChris Mason 2840459931ecSChris Mason new_item = btrfs_item_nr(leaf, slot); 2841459931ecSChris Mason 2842459931ecSChris Mason btrfs_set_item_offset(leaf, new_item, orig_offset); 2843459931ecSChris Mason btrfs_set_item_size(leaf, new_item, item_size - split_offset); 2844459931ecSChris Mason 2845459931ecSChris Mason btrfs_set_item_offset(leaf, item, 2846459931ecSChris Mason orig_offset + item_size - split_offset); 2847459931ecSChris Mason btrfs_set_item_size(leaf, item, split_offset); 2848459931ecSChris Mason 2849459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 2850459931ecSChris Mason 2851459931ecSChris Mason /* write the data for the start of the original item */ 2852459931ecSChris Mason write_extent_buffer(leaf, buf, 2853459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 2854459931ecSChris Mason split_offset); 2855459931ecSChris Mason 2856459931ecSChris Mason /* write the data for the new item */ 2857459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 2858459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 2859459931ecSChris Mason item_size - split_offset); 2860459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 2861459931ecSChris Mason 2862459931ecSChris Mason ret = 0; 2863459931ecSChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 2864459931ecSChris Mason btrfs_print_leaf(root, leaf); 2865459931ecSChris Mason BUG(); 2866459931ecSChris Mason } 2867459931ecSChris Mason kfree(buf); 2868459931ecSChris Mason return ret; 2869459931ecSChris Mason } 2870459931ecSChris Mason 2871459931ecSChris Mason /* 2872d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 2873d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 2874d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 2875d352ac68SChris Mason * the front. 2876d352ac68SChris Mason */ 2877b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans, 2878b18c6685SChris Mason struct btrfs_root *root, 2879b18c6685SChris Mason struct btrfs_path *path, 2880179e29e4SChris Mason u32 new_size, int from_end) 2881b18c6685SChris Mason { 2882b18c6685SChris Mason int ret = 0; 2883b18c6685SChris Mason int slot; 2884b18c6685SChris Mason int slot_orig; 28855f39d397SChris Mason struct extent_buffer *leaf; 28865f39d397SChris Mason struct btrfs_item *item; 2887b18c6685SChris Mason u32 nritems; 2888b18c6685SChris Mason unsigned int data_end; 2889b18c6685SChris Mason unsigned int old_data_start; 2890b18c6685SChris Mason unsigned int old_size; 2891b18c6685SChris Mason unsigned int size_diff; 2892b18c6685SChris Mason int i; 2893b18c6685SChris Mason 2894b18c6685SChris Mason slot_orig = path->slots[0]; 28955f39d397SChris Mason leaf = path->nodes[0]; 2896179e29e4SChris Mason slot = path->slots[0]; 2897179e29e4SChris Mason 2898179e29e4SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 2899179e29e4SChris Mason if (old_size == new_size) 2900179e29e4SChris Mason return 0; 2901b18c6685SChris Mason 29025f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 2903b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 2904b18c6685SChris Mason 29055f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 2906179e29e4SChris Mason 2907b18c6685SChris Mason size_diff = old_size - new_size; 2908b18c6685SChris Mason 2909b18c6685SChris Mason BUG_ON(slot < 0); 2910b18c6685SChris Mason BUG_ON(slot >= nritems); 2911b18c6685SChris Mason 2912b18c6685SChris Mason /* 2913b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 2914b18c6685SChris Mason */ 2915b18c6685SChris Mason /* first correct the data pointers */ 2916b18c6685SChris Mason for (i = slot; i < nritems; i++) { 29175f39d397SChris Mason u32 ioff; 29185f39d397SChris Mason item = btrfs_item_nr(leaf, i); 2919db94535dSChris Mason 2920db94535dSChris Mason if (!leaf->map_token) { 2921db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 2922db94535dSChris Mason sizeof(struct btrfs_item), 2923db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 2924db94535dSChris Mason &leaf->map_start, &leaf->map_len, 2925db94535dSChris Mason KM_USER1); 2926db94535dSChris Mason } 2927db94535dSChris Mason 29285f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 29295f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + size_diff); 2930b18c6685SChris Mason } 2931db94535dSChris Mason 2932db94535dSChris Mason if (leaf->map_token) { 2933db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 2934db94535dSChris Mason leaf->map_token = NULL; 2935db94535dSChris Mason } 2936db94535dSChris Mason 2937b18c6685SChris Mason /* shift the data */ 2938179e29e4SChris Mason if (from_end) { 29395f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 2940b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 2941b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 2942179e29e4SChris Mason } else { 2943179e29e4SChris Mason struct btrfs_disk_key disk_key; 2944179e29e4SChris Mason u64 offset; 2945179e29e4SChris Mason 2946179e29e4SChris Mason btrfs_item_key(leaf, &disk_key, slot); 2947179e29e4SChris Mason 2948179e29e4SChris Mason if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 2949179e29e4SChris Mason unsigned long ptr; 2950179e29e4SChris Mason struct btrfs_file_extent_item *fi; 2951179e29e4SChris Mason 2952179e29e4SChris Mason fi = btrfs_item_ptr(leaf, slot, 2953179e29e4SChris Mason struct btrfs_file_extent_item); 2954179e29e4SChris Mason fi = (struct btrfs_file_extent_item *)( 2955179e29e4SChris Mason (unsigned long)fi - size_diff); 2956179e29e4SChris Mason 2957179e29e4SChris Mason if (btrfs_file_extent_type(leaf, fi) == 2958179e29e4SChris Mason BTRFS_FILE_EXTENT_INLINE) { 2959179e29e4SChris Mason ptr = btrfs_item_ptr_offset(leaf, slot); 2960179e29e4SChris Mason memmove_extent_buffer(leaf, ptr, 2961179e29e4SChris Mason (unsigned long)fi, 2962179e29e4SChris Mason offsetof(struct btrfs_file_extent_item, 2963179e29e4SChris Mason disk_bytenr)); 2964179e29e4SChris Mason } 2965179e29e4SChris Mason } 2966179e29e4SChris Mason 2967179e29e4SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 2968179e29e4SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 2969179e29e4SChris Mason data_end, old_data_start - data_end); 2970179e29e4SChris Mason 2971179e29e4SChris Mason offset = btrfs_disk_key_offset(&disk_key); 2972179e29e4SChris Mason btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 2973179e29e4SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 2974179e29e4SChris Mason if (slot == 0) 2975179e29e4SChris Mason fixup_low_keys(trans, root, path, &disk_key, 1); 2976179e29e4SChris Mason } 29775f39d397SChris Mason 29785f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 29795f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 29805f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 2981b18c6685SChris Mason 2982b18c6685SChris Mason ret = 0; 29835f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 29845f39d397SChris Mason btrfs_print_leaf(root, leaf); 2985b18c6685SChris Mason BUG(); 29865f39d397SChris Mason } 2987b18c6685SChris Mason return ret; 2988b18c6685SChris Mason } 2989b18c6685SChris Mason 2990d352ac68SChris Mason /* 2991d352ac68SChris Mason * make the item pointed to by the path bigger, data_size is the new size. 2992d352ac68SChris Mason */ 29935f39d397SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans, 29945f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 29955f39d397SChris Mason u32 data_size) 29966567e837SChris Mason { 29976567e837SChris Mason int ret = 0; 29986567e837SChris Mason int slot; 29996567e837SChris Mason int slot_orig; 30005f39d397SChris Mason struct extent_buffer *leaf; 30015f39d397SChris Mason struct btrfs_item *item; 30026567e837SChris Mason u32 nritems; 30036567e837SChris Mason unsigned int data_end; 30046567e837SChris Mason unsigned int old_data; 30056567e837SChris Mason unsigned int old_size; 30066567e837SChris Mason int i; 30076567e837SChris Mason 30086567e837SChris Mason slot_orig = path->slots[0]; 30095f39d397SChris Mason leaf = path->nodes[0]; 30106567e837SChris Mason 30115f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 30126567e837SChris Mason data_end = leaf_data_end(root, leaf); 30136567e837SChris Mason 30145f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 30155f39d397SChris Mason btrfs_print_leaf(root, leaf); 30166567e837SChris Mason BUG(); 30175f39d397SChris Mason } 30186567e837SChris Mason slot = path->slots[0]; 30195f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 30206567e837SChris Mason 30216567e837SChris Mason BUG_ON(slot < 0); 30223326d1b0SChris Mason if (slot >= nritems) { 30233326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3024d397712bSChris Mason printk(KERN_CRIT "slot %d too large, nritems %d\n", 3025d397712bSChris Mason slot, nritems); 30263326d1b0SChris Mason BUG_ON(1); 30273326d1b0SChris Mason } 30286567e837SChris Mason 30296567e837SChris Mason /* 30306567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 30316567e837SChris Mason */ 30326567e837SChris Mason /* first correct the data pointers */ 30336567e837SChris Mason for (i = slot; i < nritems; i++) { 30345f39d397SChris Mason u32 ioff; 30355f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3036db94535dSChris Mason 3037db94535dSChris Mason if (!leaf->map_token) { 3038db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3039db94535dSChris Mason sizeof(struct btrfs_item), 3040db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3041db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3042db94535dSChris Mason KM_USER1); 3043db94535dSChris Mason } 30445f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 30455f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 30466567e837SChris Mason } 30475f39d397SChris Mason 3048db94535dSChris Mason if (leaf->map_token) { 3049db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3050db94535dSChris Mason leaf->map_token = NULL; 3051db94535dSChris Mason } 3052db94535dSChris Mason 30536567e837SChris Mason /* shift the data */ 30545f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 30556567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 30566567e837SChris Mason data_end, old_data - data_end); 30575f39d397SChris Mason 30586567e837SChris Mason data_end = old_data; 30595f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 30605f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 30615f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 30625f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 30636567e837SChris Mason 30646567e837SChris Mason ret = 0; 30655f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 30665f39d397SChris Mason btrfs_print_leaf(root, leaf); 30676567e837SChris Mason BUG(); 30685f39d397SChris Mason } 30696567e837SChris Mason return ret; 30706567e837SChris Mason } 30716567e837SChris Mason 307274123bd7SChris Mason /* 3073d352ac68SChris Mason * Given a key and some data, insert items into the tree. 307474123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 3075f3465ca4SJosef Bacik * Returns the number of keys that were inserted. 3076f3465ca4SJosef Bacik */ 3077f3465ca4SJosef Bacik int btrfs_insert_some_items(struct btrfs_trans_handle *trans, 3078f3465ca4SJosef Bacik struct btrfs_root *root, 3079f3465ca4SJosef Bacik struct btrfs_path *path, 3080f3465ca4SJosef Bacik struct btrfs_key *cpu_key, u32 *data_size, 3081f3465ca4SJosef Bacik int nr) 3082f3465ca4SJosef Bacik { 3083f3465ca4SJosef Bacik struct extent_buffer *leaf; 3084f3465ca4SJosef Bacik struct btrfs_item *item; 3085f3465ca4SJosef Bacik int ret = 0; 3086f3465ca4SJosef Bacik int slot; 3087f3465ca4SJosef Bacik int i; 3088f3465ca4SJosef Bacik u32 nritems; 3089f3465ca4SJosef Bacik u32 total_data = 0; 3090f3465ca4SJosef Bacik u32 total_size = 0; 3091f3465ca4SJosef Bacik unsigned int data_end; 3092f3465ca4SJosef Bacik struct btrfs_disk_key disk_key; 3093f3465ca4SJosef Bacik struct btrfs_key found_key; 3094f3465ca4SJosef Bacik 309587b29b20SYan Zheng for (i = 0; i < nr; i++) { 309687b29b20SYan Zheng if (total_size + data_size[i] + sizeof(struct btrfs_item) > 309787b29b20SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 309887b29b20SYan Zheng break; 309987b29b20SYan Zheng nr = i; 310087b29b20SYan Zheng } 3101f3465ca4SJosef Bacik total_data += data_size[i]; 310287b29b20SYan Zheng total_size += data_size[i] + sizeof(struct btrfs_item); 310387b29b20SYan Zheng } 310487b29b20SYan Zheng BUG_ON(nr == 0); 3105f3465ca4SJosef Bacik 3106f3465ca4SJosef Bacik ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 3107f3465ca4SJosef Bacik if (ret == 0) 3108f3465ca4SJosef Bacik return -EEXIST; 3109f3465ca4SJosef Bacik if (ret < 0) 3110f3465ca4SJosef Bacik goto out; 3111f3465ca4SJosef Bacik 3112f3465ca4SJosef Bacik leaf = path->nodes[0]; 3113f3465ca4SJosef Bacik 3114f3465ca4SJosef Bacik nritems = btrfs_header_nritems(leaf); 3115f3465ca4SJosef Bacik data_end = leaf_data_end(root, leaf); 3116f3465ca4SJosef Bacik 3117f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < total_size) { 3118f3465ca4SJosef Bacik for (i = nr; i >= 0; i--) { 3119f3465ca4SJosef Bacik total_data -= data_size[i]; 3120f3465ca4SJosef Bacik total_size -= data_size[i] + sizeof(struct btrfs_item); 3121f3465ca4SJosef Bacik if (total_size < btrfs_leaf_free_space(root, leaf)) 3122f3465ca4SJosef Bacik break; 3123f3465ca4SJosef Bacik } 3124f3465ca4SJosef Bacik nr = i; 3125f3465ca4SJosef Bacik } 3126f3465ca4SJosef Bacik 3127f3465ca4SJosef Bacik slot = path->slots[0]; 3128f3465ca4SJosef Bacik BUG_ON(slot < 0); 3129f3465ca4SJosef Bacik 3130f3465ca4SJosef Bacik if (slot != nritems) { 3131f3465ca4SJosef Bacik unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3132f3465ca4SJosef Bacik 3133f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot); 3134f3465ca4SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, slot); 3135f3465ca4SJosef Bacik 3136f3465ca4SJosef Bacik /* figure out how many keys we can insert in here */ 3137f3465ca4SJosef Bacik total_data = data_size[0]; 3138f3465ca4SJosef Bacik for (i = 1; i < nr; i++) { 3139f3465ca4SJosef Bacik if (comp_cpu_keys(&found_key, cpu_key + i) <= 0) 3140f3465ca4SJosef Bacik break; 3141f3465ca4SJosef Bacik total_data += data_size[i]; 3142f3465ca4SJosef Bacik } 3143f3465ca4SJosef Bacik nr = i; 3144f3465ca4SJosef Bacik 3145f3465ca4SJosef Bacik if (old_data < data_end) { 3146f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3147d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 3148f3465ca4SJosef Bacik slot, old_data, data_end); 3149f3465ca4SJosef Bacik BUG_ON(1); 3150f3465ca4SJosef Bacik } 3151f3465ca4SJosef Bacik /* 3152f3465ca4SJosef Bacik * item0..itemN ... dataN.offset..dataN.size .. data0.size 3153f3465ca4SJosef Bacik */ 3154f3465ca4SJosef Bacik /* first correct the data pointers */ 3155f3465ca4SJosef Bacik WARN_ON(leaf->map_token); 3156f3465ca4SJosef Bacik for (i = slot; i < nritems; i++) { 3157f3465ca4SJosef Bacik u32 ioff; 3158f3465ca4SJosef Bacik 3159f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, i); 3160f3465ca4SJosef Bacik if (!leaf->map_token) { 3161f3465ca4SJosef Bacik map_extent_buffer(leaf, (unsigned long)item, 3162f3465ca4SJosef Bacik sizeof(struct btrfs_item), 3163f3465ca4SJosef Bacik &leaf->map_token, &leaf->kaddr, 3164f3465ca4SJosef Bacik &leaf->map_start, &leaf->map_len, 3165f3465ca4SJosef Bacik KM_USER1); 3166f3465ca4SJosef Bacik } 3167f3465ca4SJosef Bacik 3168f3465ca4SJosef Bacik ioff = btrfs_item_offset(leaf, item); 3169f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, ioff - total_data); 3170f3465ca4SJosef Bacik } 3171f3465ca4SJosef Bacik if (leaf->map_token) { 3172f3465ca4SJosef Bacik unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3173f3465ca4SJosef Bacik leaf->map_token = NULL; 3174f3465ca4SJosef Bacik } 3175f3465ca4SJosef Bacik 3176f3465ca4SJosef Bacik /* shift the items */ 3177f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 3178f3465ca4SJosef Bacik btrfs_item_nr_offset(slot), 3179f3465ca4SJosef Bacik (nritems - slot) * sizeof(struct btrfs_item)); 3180f3465ca4SJosef Bacik 3181f3465ca4SJosef Bacik /* shift the data */ 3182f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3183f3465ca4SJosef Bacik data_end - total_data, btrfs_leaf_data(leaf) + 3184f3465ca4SJosef Bacik data_end, old_data - data_end); 3185f3465ca4SJosef Bacik data_end = old_data; 3186f3465ca4SJosef Bacik } else { 3187f3465ca4SJosef Bacik /* 3188f3465ca4SJosef Bacik * this sucks but it has to be done, if we are inserting at 3189f3465ca4SJosef Bacik * the end of the leaf only insert 1 of the items, since we 3190f3465ca4SJosef Bacik * have no way of knowing whats on the next leaf and we'd have 3191f3465ca4SJosef Bacik * to drop our current locks to figure it out 3192f3465ca4SJosef Bacik */ 3193f3465ca4SJosef Bacik nr = 1; 3194f3465ca4SJosef Bacik } 3195f3465ca4SJosef Bacik 3196f3465ca4SJosef Bacik /* setup the item for the new data */ 3197f3465ca4SJosef Bacik for (i = 0; i < nr; i++) { 3198f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 3199f3465ca4SJosef Bacik btrfs_set_item_key(leaf, &disk_key, slot + i); 3200f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot + i); 3201f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 3202f3465ca4SJosef Bacik data_end -= data_size[i]; 3203f3465ca4SJosef Bacik btrfs_set_item_size(leaf, item, data_size[i]); 3204f3465ca4SJosef Bacik } 3205f3465ca4SJosef Bacik btrfs_set_header_nritems(leaf, nritems + nr); 3206f3465ca4SJosef Bacik btrfs_mark_buffer_dirty(leaf); 3207f3465ca4SJosef Bacik 3208f3465ca4SJosef Bacik ret = 0; 3209f3465ca4SJosef Bacik if (slot == 0) { 3210f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3211f3465ca4SJosef Bacik ret = fixup_low_keys(trans, root, path, &disk_key, 1); 3212f3465ca4SJosef Bacik } 3213f3465ca4SJosef Bacik 3214f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < 0) { 3215f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3216f3465ca4SJosef Bacik BUG(); 3217f3465ca4SJosef Bacik } 3218f3465ca4SJosef Bacik out: 3219f3465ca4SJosef Bacik if (!ret) 3220f3465ca4SJosef Bacik ret = nr; 3221f3465ca4SJosef Bacik return ret; 3222f3465ca4SJosef Bacik } 3223f3465ca4SJosef Bacik 3224f3465ca4SJosef Bacik /* 3225f3465ca4SJosef Bacik * Given a key and some data, insert items into the tree. 3226f3465ca4SJosef Bacik * This does all the path init required, making room in the tree if needed. 322774123bd7SChris Mason */ 32289c58309dSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 32295f39d397SChris Mason struct btrfs_root *root, 32305f39d397SChris Mason struct btrfs_path *path, 32319c58309dSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 32329c58309dSChris Mason int nr) 3233be0e5c09SChris Mason { 32345f39d397SChris Mason struct extent_buffer *leaf; 32355f39d397SChris Mason struct btrfs_item *item; 3236aa5d6bedSChris Mason int ret = 0; 3237be0e5c09SChris Mason int slot; 3238eb60ceacSChris Mason int slot_orig; 32399c58309dSChris Mason int i; 32407518a238SChris Mason u32 nritems; 32419c58309dSChris Mason u32 total_size = 0; 32429c58309dSChris Mason u32 total_data = 0; 3243be0e5c09SChris Mason unsigned int data_end; 3244e2fa7227SChris Mason struct btrfs_disk_key disk_key; 3245e2fa7227SChris Mason 3246d397712bSChris Mason for (i = 0; i < nr; i++) 32479c58309dSChris Mason total_data += data_size[i]; 3248be0e5c09SChris Mason 32497b128766SJosef Bacik total_size = total_data + (nr * sizeof(struct btrfs_item)); 32509c58309dSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 32510f9dd46cSJosef Bacik if (ret == 0) 3252f0930a37SChris Mason return -EEXIST; 3253ed2ff2cbSChris Mason if (ret < 0) 3254ed2ff2cbSChris Mason goto out; 3255be0e5c09SChris Mason 325662e2749eSChris Mason slot_orig = path->slots[0]; 32575f39d397SChris Mason leaf = path->nodes[0]; 325874123bd7SChris Mason 32595f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3260123abc88SChris Mason data_end = leaf_data_end(root, leaf); 3261eb60ceacSChris Mason 3262f25956ccSChris Mason if (btrfs_leaf_free_space(root, leaf) < total_size) { 32633326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3264d397712bSChris Mason printk(KERN_CRIT "not enough freespace need %u have %d\n", 32659c58309dSChris Mason total_size, btrfs_leaf_free_space(root, leaf)); 3266be0e5c09SChris Mason BUG(); 3267d4dbff95SChris Mason } 32685f39d397SChris Mason 326962e2749eSChris Mason slot = path->slots[0]; 3270eb60ceacSChris Mason BUG_ON(slot < 0); 32715f39d397SChris Mason 3272be0e5c09SChris Mason if (slot != nritems) { 32735f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3274be0e5c09SChris Mason 32755f39d397SChris Mason if (old_data < data_end) { 32765f39d397SChris Mason btrfs_print_leaf(root, leaf); 3277d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 32785f39d397SChris Mason slot, old_data, data_end); 32795f39d397SChris Mason BUG_ON(1); 32805f39d397SChris Mason } 3281be0e5c09SChris Mason /* 3282be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3283be0e5c09SChris Mason */ 3284be0e5c09SChris Mason /* first correct the data pointers */ 3285db94535dSChris Mason WARN_ON(leaf->map_token); 32860783fcfcSChris Mason for (i = slot; i < nritems; i++) { 32875f39d397SChris Mason u32 ioff; 3288db94535dSChris Mason 32895f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3290db94535dSChris Mason if (!leaf->map_token) { 3291db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3292db94535dSChris Mason sizeof(struct btrfs_item), 3293db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3294db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3295db94535dSChris Mason KM_USER1); 3296db94535dSChris Mason } 3297db94535dSChris Mason 32985f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 32999c58309dSChris Mason btrfs_set_item_offset(leaf, item, ioff - total_data); 33000783fcfcSChris Mason } 3301db94535dSChris Mason if (leaf->map_token) { 3302db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3303db94535dSChris Mason leaf->map_token = NULL; 3304db94535dSChris Mason } 3305be0e5c09SChris Mason 3306be0e5c09SChris Mason /* shift the items */ 33079c58309dSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 33085f39d397SChris Mason btrfs_item_nr_offset(slot), 33090783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3310be0e5c09SChris Mason 3311be0e5c09SChris Mason /* shift the data */ 33125f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 33139c58309dSChris Mason data_end - total_data, btrfs_leaf_data(leaf) + 3314be0e5c09SChris Mason data_end, old_data - data_end); 3315be0e5c09SChris Mason data_end = old_data; 3316be0e5c09SChris Mason } 33175f39d397SChris Mason 331862e2749eSChris Mason /* setup the item for the new data */ 33199c58309dSChris Mason for (i = 0; i < nr; i++) { 33209c58309dSChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 33219c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 33229c58309dSChris Mason item = btrfs_item_nr(leaf, slot + i); 33239c58309dSChris Mason btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 33249c58309dSChris Mason data_end -= data_size[i]; 33259c58309dSChris Mason btrfs_set_item_size(leaf, item, data_size[i]); 33269c58309dSChris Mason } 33279c58309dSChris Mason btrfs_set_header_nritems(leaf, nritems + nr); 33285f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3329aa5d6bedSChris Mason 3330aa5d6bedSChris Mason ret = 0; 33315a01a2e3SChris Mason if (slot == 0) { 33325a01a2e3SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3333e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 33345a01a2e3SChris Mason } 3335aa5d6bedSChris Mason 33365f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 33375f39d397SChris Mason btrfs_print_leaf(root, leaf); 3338be0e5c09SChris Mason BUG(); 33395f39d397SChris Mason } 3340ed2ff2cbSChris Mason out: 334162e2749eSChris Mason return ret; 334262e2749eSChris Mason } 334362e2749eSChris Mason 334462e2749eSChris Mason /* 334562e2749eSChris Mason * Given a key and some data, insert an item into the tree. 334662e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 334762e2749eSChris Mason */ 3348e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 3349e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 3350e089f05cSChris Mason data_size) 335162e2749eSChris Mason { 335262e2749eSChris Mason int ret = 0; 33532c90e5d6SChris Mason struct btrfs_path *path; 33545f39d397SChris Mason struct extent_buffer *leaf; 33555f39d397SChris Mason unsigned long ptr; 335662e2749eSChris Mason 33572c90e5d6SChris Mason path = btrfs_alloc_path(); 33582c90e5d6SChris Mason BUG_ON(!path); 33592c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 336062e2749eSChris Mason if (!ret) { 33615f39d397SChris Mason leaf = path->nodes[0]; 33625f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 33635f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 33645f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 336562e2749eSChris Mason } 33662c90e5d6SChris Mason btrfs_free_path(path); 3367aa5d6bedSChris Mason return ret; 3368be0e5c09SChris Mason } 3369be0e5c09SChris Mason 337074123bd7SChris Mason /* 33715de08d7dSChris Mason * delete the pointer from a given node. 337274123bd7SChris Mason * 3373d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 3374d352ac68SChris Mason * empty a node. 337574123bd7SChris Mason */ 3376e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 3377e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 3378be0e5c09SChris Mason { 33795f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 33807518a238SChris Mason u32 nritems; 3381aa5d6bedSChris Mason int ret = 0; 3382bb803951SChris Mason int wret; 3383be0e5c09SChris Mason 33845f39d397SChris Mason nritems = btrfs_header_nritems(parent); 3385be0e5c09SChris Mason if (slot != nritems - 1) { 33865f39d397SChris Mason memmove_extent_buffer(parent, 33875f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 33885f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 3389d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 3390d6025579SChris Mason (nritems - slot - 1)); 3391be0e5c09SChris Mason } 33927518a238SChris Mason nritems--; 33935f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 33947518a238SChris Mason if (nritems == 0 && parent == root->node) { 33955f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 3396eb60ceacSChris Mason /* just turn the root into a leaf and break */ 33975f39d397SChris Mason btrfs_set_header_level(root->node, 0); 3398bb803951SChris Mason } else if (slot == 0) { 33995f39d397SChris Mason struct btrfs_disk_key disk_key; 34005f39d397SChris Mason 34015f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 34025f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); 34030f70abe2SChris Mason if (wret) 34040f70abe2SChris Mason ret = wret; 3405be0e5c09SChris Mason } 3406d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 3407aa5d6bedSChris Mason return ret; 3408be0e5c09SChris Mason } 3409be0e5c09SChris Mason 341074123bd7SChris Mason /* 3411323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 3412323ac95bSChris Mason * path->nodes[1]. bytenr is the node block pointer, but since the callers 3413323ac95bSChris Mason * already know it, it is faster to have them pass it down than to 3414323ac95bSChris Mason * read it out of the node again. 3415323ac95bSChris Mason * 3416323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 3417323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 3418323ac95bSChris Mason * 3419323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 3420323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 3421323ac95bSChris Mason */ 3422323ac95bSChris Mason noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans, 3423323ac95bSChris Mason struct btrfs_root *root, 3424323ac95bSChris Mason struct btrfs_path *path, u64 bytenr) 3425323ac95bSChris Mason { 3426323ac95bSChris Mason int ret; 3427323ac95bSChris Mason u64 root_gen = btrfs_header_generation(path->nodes[1]); 3428323ac95bSChris Mason 3429323ac95bSChris Mason ret = del_ptr(trans, root, path, 1, path->slots[1]); 3430323ac95bSChris Mason if (ret) 3431323ac95bSChris Mason return ret; 3432323ac95bSChris Mason 3433323ac95bSChris Mason ret = btrfs_free_extent(trans, root, bytenr, 3434323ac95bSChris Mason btrfs_level_size(root, 0), 3435323ac95bSChris Mason path->nodes[1]->start, 3436323ac95bSChris Mason btrfs_header_owner(path->nodes[1]), 34373bb1a1bcSYan Zheng root_gen, 0, 1); 3438323ac95bSChris Mason return ret; 3439323ac95bSChris Mason } 3440323ac95bSChris Mason /* 344174123bd7SChris Mason * delete the item at the leaf level in path. If that empties 344274123bd7SChris Mason * the leaf, remove it from the tree 344374123bd7SChris Mason */ 344485e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 344585e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 3446be0e5c09SChris Mason { 34475f39d397SChris Mason struct extent_buffer *leaf; 34485f39d397SChris Mason struct btrfs_item *item; 344985e21bacSChris Mason int last_off; 345085e21bacSChris Mason int dsize = 0; 3451aa5d6bedSChris Mason int ret = 0; 3452aa5d6bedSChris Mason int wret; 345385e21bacSChris Mason int i; 34547518a238SChris Mason u32 nritems; 3455be0e5c09SChris Mason 34565f39d397SChris Mason leaf = path->nodes[0]; 345785e21bacSChris Mason last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); 345885e21bacSChris Mason 345985e21bacSChris Mason for (i = 0; i < nr; i++) 346085e21bacSChris Mason dsize += btrfs_item_size_nr(leaf, slot + i); 346185e21bacSChris Mason 34625f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3463be0e5c09SChris Mason 346485e21bacSChris Mason if (slot + nr != nritems) { 3465123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 34665f39d397SChris Mason 34675f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3468d6025579SChris Mason data_end + dsize, 3469123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 347085e21bacSChris Mason last_off - data_end); 34715f39d397SChris Mason 347285e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 34735f39d397SChris Mason u32 ioff; 3474db94535dSChris Mason 34755f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3476db94535dSChris Mason if (!leaf->map_token) { 3477db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3478db94535dSChris Mason sizeof(struct btrfs_item), 3479db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3480db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3481db94535dSChris Mason KM_USER1); 3482db94535dSChris Mason } 34835f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 34845f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + dsize); 34850783fcfcSChris Mason } 3486db94535dSChris Mason 3487db94535dSChris Mason if (leaf->map_token) { 3488db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3489db94535dSChris Mason leaf->map_token = NULL; 3490db94535dSChris Mason } 3491db94535dSChris Mason 34925f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 349385e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 34940783fcfcSChris Mason sizeof(struct btrfs_item) * 349585e21bacSChris Mason (nritems - slot - nr)); 3496be0e5c09SChris Mason } 349785e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 349885e21bacSChris Mason nritems -= nr; 34995f39d397SChris Mason 350074123bd7SChris Mason /* delete the leaf if we've emptied it */ 35017518a238SChris Mason if (nritems == 0) { 35025f39d397SChris Mason if (leaf == root->node) { 35035f39d397SChris Mason btrfs_set_header_level(leaf, 0); 35049a8dd150SChris Mason } else { 3505323ac95bSChris Mason ret = btrfs_del_leaf(trans, root, path, leaf->start); 3506323ac95bSChris Mason BUG_ON(ret); 35079a8dd150SChris Mason } 3508be0e5c09SChris Mason } else { 35097518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 3510aa5d6bedSChris Mason if (slot == 0) { 35115f39d397SChris Mason struct btrfs_disk_key disk_key; 35125f39d397SChris Mason 35135f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 3514e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 35155f39d397SChris Mason &disk_key, 1); 3516aa5d6bedSChris Mason if (wret) 3517aa5d6bedSChris Mason ret = wret; 3518aa5d6bedSChris Mason } 3519aa5d6bedSChris Mason 352074123bd7SChris Mason /* delete the leaf if it is mostly empty */ 352185e21bacSChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) { 3522be0e5c09SChris Mason /* push_leaf_left fixes the path. 3523be0e5c09SChris Mason * make sure the path still points to our leaf 3524be0e5c09SChris Mason * for possible call to del_ptr below 3525be0e5c09SChris Mason */ 35264920c9acSChris Mason slot = path->slots[1]; 35275f39d397SChris Mason extent_buffer_get(leaf); 35285f39d397SChris Mason 352985e21bacSChris Mason wret = push_leaf_left(trans, root, path, 1, 1); 353054aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3531aa5d6bedSChris Mason ret = wret; 35325f39d397SChris Mason 35335f39d397SChris Mason if (path->nodes[0] == leaf && 35345f39d397SChris Mason btrfs_header_nritems(leaf)) { 353585e21bacSChris Mason wret = push_leaf_right(trans, root, path, 1, 1); 353654aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3537aa5d6bedSChris Mason ret = wret; 3538aa5d6bedSChris Mason } 35395f39d397SChris Mason 35405f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 3541323ac95bSChris Mason path->slots[1] = slot; 3542d397712bSChris Mason ret = btrfs_del_leaf(trans, root, path, 3543d397712bSChris Mason leaf->start); 3544323ac95bSChris Mason BUG_ON(ret); 35455f39d397SChris Mason free_extent_buffer(leaf); 35465de08d7dSChris Mason } else { 3547925baeddSChris Mason /* if we're still in the path, make sure 3548925baeddSChris Mason * we're dirty. Otherwise, one of the 3549925baeddSChris Mason * push_leaf functions must have already 3550925baeddSChris Mason * dirtied this buffer 3551925baeddSChris Mason */ 3552925baeddSChris Mason if (path->nodes[0] == leaf) 35535f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 35545f39d397SChris Mason free_extent_buffer(leaf); 3555be0e5c09SChris Mason } 3556d5719762SChris Mason } else { 35575f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3558be0e5c09SChris Mason } 35599a8dd150SChris Mason } 3560aa5d6bedSChris Mason return ret; 35619a8dd150SChris Mason } 35629a8dd150SChris Mason 356397571fd0SChris Mason /* 3564925baeddSChris Mason * search the tree again to find a leaf with lesser keys 35657bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 35667bb86316SChris Mason * returns < 0 on io errors. 3567d352ac68SChris Mason * 3568d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 3569d352ac68SChris Mason * time you call it. 35707bb86316SChris Mason */ 35717bb86316SChris Mason int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 35727bb86316SChris Mason { 3573925baeddSChris Mason struct btrfs_key key; 3574925baeddSChris Mason struct btrfs_disk_key found_key; 3575925baeddSChris Mason int ret; 35767bb86316SChris Mason 3577925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 3578925baeddSChris Mason 3579925baeddSChris Mason if (key.offset > 0) 3580925baeddSChris Mason key.offset--; 3581925baeddSChris Mason else if (key.type > 0) 3582925baeddSChris Mason key.type--; 3583925baeddSChris Mason else if (key.objectid > 0) 3584925baeddSChris Mason key.objectid--; 3585925baeddSChris Mason else 35867bb86316SChris Mason return 1; 35877bb86316SChris Mason 3588925baeddSChris Mason btrfs_release_path(root, path); 3589925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 3590925baeddSChris Mason if (ret < 0) 3591925baeddSChris Mason return ret; 3592925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 3593925baeddSChris Mason ret = comp_keys(&found_key, &key); 3594925baeddSChris Mason if (ret < 0) 35957bb86316SChris Mason return 0; 3596925baeddSChris Mason return 1; 35977bb86316SChris Mason } 35987bb86316SChris Mason 35993f157a2fSChris Mason /* 36003f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 36013f157a2fSChris Mason * for nodes or leaves that are either in cache or have a minimum 3602d352ac68SChris Mason * transaction id. This is used by the btree defrag code, and tree logging 36033f157a2fSChris Mason * 36043f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 36053f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 36063f157a2fSChris Mason * key and get a writable path. 36073f157a2fSChris Mason * 36083f157a2fSChris Mason * This does lock as it descends, and path->keep_locks should be set 36093f157a2fSChris Mason * to 1 by the caller. 36103f157a2fSChris Mason * 36113f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 36123f157a2fSChris Mason * of the tree. 36133f157a2fSChris Mason * 3614d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 3615d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 3616d352ac68SChris Mason * skipped over (without reading them). 3617d352ac68SChris Mason * 36183f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 36193f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 36203f157a2fSChris Mason */ 36213f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 3622e02119d5SChris Mason struct btrfs_key *max_key, 36233f157a2fSChris Mason struct btrfs_path *path, int cache_only, 36243f157a2fSChris Mason u64 min_trans) 36253f157a2fSChris Mason { 36263f157a2fSChris Mason struct extent_buffer *cur; 36273f157a2fSChris Mason struct btrfs_key found_key; 36283f157a2fSChris Mason int slot; 36299652480bSYan int sret; 36303f157a2fSChris Mason u32 nritems; 36313f157a2fSChris Mason int level; 36323f157a2fSChris Mason int ret = 1; 36333f157a2fSChris Mason 3634934d375bSChris Mason WARN_ON(!path->keep_locks); 36353f157a2fSChris Mason again: 36363f157a2fSChris Mason cur = btrfs_lock_root_node(root); 36373f157a2fSChris Mason level = btrfs_header_level(cur); 3638e02119d5SChris Mason WARN_ON(path->nodes[level]); 36393f157a2fSChris Mason path->nodes[level] = cur; 36403f157a2fSChris Mason path->locks[level] = 1; 36413f157a2fSChris Mason 36423f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 36433f157a2fSChris Mason ret = 1; 36443f157a2fSChris Mason goto out; 36453f157a2fSChris Mason } 36463f157a2fSChris Mason while (1) { 36473f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 36483f157a2fSChris Mason level = btrfs_header_level(cur); 36499652480bSYan sret = bin_search(cur, min_key, level, &slot); 36503f157a2fSChris Mason 3651323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 3652323ac95bSChris Mason if (level == path->lowest_level) { 3653e02119d5SChris Mason if (slot >= nritems) 3654e02119d5SChris Mason goto find_next_key; 36553f157a2fSChris Mason ret = 0; 36563f157a2fSChris Mason path->slots[level] = slot; 36573f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 36583f157a2fSChris Mason goto out; 36593f157a2fSChris Mason } 36609652480bSYan if (sret && slot > 0) 36619652480bSYan slot--; 36623f157a2fSChris Mason /* 36633f157a2fSChris Mason * check this node pointer against the cache_only and 36643f157a2fSChris Mason * min_trans parameters. If it isn't in cache or is too 36653f157a2fSChris Mason * old, skip to the next one. 36663f157a2fSChris Mason */ 36673f157a2fSChris Mason while (slot < nritems) { 36683f157a2fSChris Mason u64 blockptr; 36693f157a2fSChris Mason u64 gen; 36703f157a2fSChris Mason struct extent_buffer *tmp; 3671e02119d5SChris Mason struct btrfs_disk_key disk_key; 3672e02119d5SChris Mason 36733f157a2fSChris Mason blockptr = btrfs_node_blockptr(cur, slot); 36743f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 36753f157a2fSChris Mason if (gen < min_trans) { 36763f157a2fSChris Mason slot++; 36773f157a2fSChris Mason continue; 36783f157a2fSChris Mason } 36793f157a2fSChris Mason if (!cache_only) 36803f157a2fSChris Mason break; 36813f157a2fSChris Mason 3682e02119d5SChris Mason if (max_key) { 3683e02119d5SChris Mason btrfs_node_key(cur, &disk_key, slot); 3684e02119d5SChris Mason if (comp_keys(&disk_key, max_key) >= 0) { 3685e02119d5SChris Mason ret = 1; 3686e02119d5SChris Mason goto out; 3687e02119d5SChris Mason } 3688e02119d5SChris Mason } 3689e02119d5SChris Mason 36903f157a2fSChris Mason tmp = btrfs_find_tree_block(root, blockptr, 36913f157a2fSChris Mason btrfs_level_size(root, level - 1)); 36923f157a2fSChris Mason 36933f157a2fSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 36943f157a2fSChris Mason free_extent_buffer(tmp); 36953f157a2fSChris Mason break; 36963f157a2fSChris Mason } 36973f157a2fSChris Mason if (tmp) 36983f157a2fSChris Mason free_extent_buffer(tmp); 36993f157a2fSChris Mason slot++; 37003f157a2fSChris Mason } 3701e02119d5SChris Mason find_next_key: 37023f157a2fSChris Mason /* 37033f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 37043f157a2fSChris Mason * and find another one 37053f157a2fSChris Mason */ 37063f157a2fSChris Mason if (slot >= nritems) { 3707e02119d5SChris Mason path->slots[level] = slot; 3708e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 37093f157a2fSChris Mason cache_only, min_trans); 3710e02119d5SChris Mason if (sret == 0) { 37113f157a2fSChris Mason btrfs_release_path(root, path); 37123f157a2fSChris Mason goto again; 37133f157a2fSChris Mason } else { 37143f157a2fSChris Mason goto out; 37153f157a2fSChris Mason } 37163f157a2fSChris Mason } 37173f157a2fSChris Mason /* save our key for returning back */ 37183f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 37193f157a2fSChris Mason path->slots[level] = slot; 37203f157a2fSChris Mason if (level == path->lowest_level) { 37213f157a2fSChris Mason ret = 0; 37223f157a2fSChris Mason unlock_up(path, level, 1); 37233f157a2fSChris Mason goto out; 37243f157a2fSChris Mason } 37253f157a2fSChris Mason cur = read_node_slot(root, cur, slot); 37263f157a2fSChris Mason 37273f157a2fSChris Mason btrfs_tree_lock(cur); 37283f157a2fSChris Mason path->locks[level - 1] = 1; 37293f157a2fSChris Mason path->nodes[level - 1] = cur; 37303f157a2fSChris Mason unlock_up(path, level, 1); 37313f157a2fSChris Mason } 37323f157a2fSChris Mason out: 37333f157a2fSChris Mason if (ret == 0) 37343f157a2fSChris Mason memcpy(min_key, &found_key, sizeof(found_key)); 37353f157a2fSChris Mason return ret; 37363f157a2fSChris Mason } 37373f157a2fSChris Mason 37383f157a2fSChris Mason /* 37393f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 37403f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 37413f157a2fSChris Mason * tree based on the current path and the cache_only and min_trans 37423f157a2fSChris Mason * parameters. 37433f157a2fSChris Mason * 37443f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 37453f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 37463f157a2fSChris Mason * 37473f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 37483f157a2fSChris Mason * calling this function. 37493f157a2fSChris Mason */ 3750e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 37513f157a2fSChris Mason struct btrfs_key *key, int lowest_level, 37523f157a2fSChris Mason int cache_only, u64 min_trans) 3753e7a84565SChris Mason { 3754e7a84565SChris Mason int level = lowest_level; 3755e7a84565SChris Mason int slot; 3756e7a84565SChris Mason struct extent_buffer *c; 3757e7a84565SChris Mason 3758934d375bSChris Mason WARN_ON(!path->keep_locks); 3759e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 3760e7a84565SChris Mason if (!path->nodes[level]) 3761e7a84565SChris Mason return 1; 3762e7a84565SChris Mason 3763e7a84565SChris Mason slot = path->slots[level] + 1; 3764e7a84565SChris Mason c = path->nodes[level]; 37653f157a2fSChris Mason next: 3766e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 3767e7a84565SChris Mason level++; 3768d397712bSChris Mason if (level == BTRFS_MAX_LEVEL) 3769e7a84565SChris Mason return 1; 3770e7a84565SChris Mason continue; 3771e7a84565SChris Mason } 3772e7a84565SChris Mason if (level == 0) 3773e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 37743f157a2fSChris Mason else { 37753f157a2fSChris Mason u64 blockptr = btrfs_node_blockptr(c, slot); 37763f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 37773f157a2fSChris Mason 37783f157a2fSChris Mason if (cache_only) { 37793f157a2fSChris Mason struct extent_buffer *cur; 37803f157a2fSChris Mason cur = btrfs_find_tree_block(root, blockptr, 37813f157a2fSChris Mason btrfs_level_size(root, level - 1)); 37823f157a2fSChris Mason if (!cur || !btrfs_buffer_uptodate(cur, gen)) { 37833f157a2fSChris Mason slot++; 37843f157a2fSChris Mason if (cur) 37853f157a2fSChris Mason free_extent_buffer(cur); 37863f157a2fSChris Mason goto next; 37873f157a2fSChris Mason } 37883f157a2fSChris Mason free_extent_buffer(cur); 37893f157a2fSChris Mason } 37903f157a2fSChris Mason if (gen < min_trans) { 37913f157a2fSChris Mason slot++; 37923f157a2fSChris Mason goto next; 37933f157a2fSChris Mason } 3794e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 37953f157a2fSChris Mason } 3796e7a84565SChris Mason return 0; 3797e7a84565SChris Mason } 3798e7a84565SChris Mason return 1; 3799e7a84565SChris Mason } 3800e7a84565SChris Mason 38017bb86316SChris Mason /* 3802925baeddSChris Mason * search the tree again to find a leaf with greater keys 38030f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 38040f70abe2SChris Mason * returns < 0 on io errors. 380597571fd0SChris Mason */ 3806234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 3807d97e63b6SChris Mason { 3808d97e63b6SChris Mason int slot; 3809d97e63b6SChris Mason int level = 1; 38105f39d397SChris Mason struct extent_buffer *c; 38115f39d397SChris Mason struct extent_buffer *next = NULL; 3812925baeddSChris Mason struct btrfs_key key; 3813925baeddSChris Mason u32 nritems; 3814925baeddSChris Mason int ret; 3815925baeddSChris Mason 3816925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 3817d397712bSChris Mason if (nritems == 0) 3818925baeddSChris Mason return 1; 3819925baeddSChris Mason 3820925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 3821925baeddSChris Mason 3822925baeddSChris Mason btrfs_release_path(root, path); 3823a2135011SChris Mason path->keep_locks = 1; 3824925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 3825925baeddSChris Mason path->keep_locks = 0; 3826925baeddSChris Mason 3827925baeddSChris Mason if (ret < 0) 3828925baeddSChris Mason return ret; 3829925baeddSChris Mason 3830a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 3831168fd7d2SChris Mason /* 3832168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 3833168fd7d2SChris Mason * could have added more items next to the key that used to be 3834168fd7d2SChris Mason * at the very end of the block. So, check again here and 3835168fd7d2SChris Mason * advance the path if there are now more items available. 3836168fd7d2SChris Mason */ 3837a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 3838168fd7d2SChris Mason path->slots[0]++; 3839925baeddSChris Mason goto done; 3840925baeddSChris Mason } 3841d97e63b6SChris Mason 3842234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 3843d97e63b6SChris Mason if (!path->nodes[level]) 38440f70abe2SChris Mason return 1; 38455f39d397SChris Mason 3846d97e63b6SChris Mason slot = path->slots[level] + 1; 3847d97e63b6SChris Mason c = path->nodes[level]; 38485f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 3849d97e63b6SChris Mason level++; 3850d397712bSChris Mason if (level == BTRFS_MAX_LEVEL) 38517bb86316SChris Mason return 1; 3852d97e63b6SChris Mason continue; 3853d97e63b6SChris Mason } 38545f39d397SChris Mason 3855925baeddSChris Mason if (next) { 3856925baeddSChris Mason btrfs_tree_unlock(next); 38575f39d397SChris Mason free_extent_buffer(next); 3858925baeddSChris Mason } 38595f39d397SChris Mason 38600bd40a71SChris Mason if (level == 1 && (path->locks[1] || path->skip_locking) && 38610bd40a71SChris Mason path->reada) 386201f46658SChris Mason reada_for_search(root, path, level, slot, 0); 38635f39d397SChris Mason 3864ca7a79adSChris Mason next = read_node_slot(root, c, slot); 38655cd57b2cSChris Mason if (!path->skip_locking) { 3866051e1b9fSChris Mason WARN_ON(!btrfs_tree_locked(c)); 3867925baeddSChris Mason btrfs_tree_lock(next); 38685cd57b2cSChris Mason } 3869d97e63b6SChris Mason break; 3870d97e63b6SChris Mason } 3871d97e63b6SChris Mason path->slots[level] = slot; 3872d97e63b6SChris Mason while (1) { 3873d97e63b6SChris Mason level--; 3874d97e63b6SChris Mason c = path->nodes[level]; 3875925baeddSChris Mason if (path->locks[level]) 3876925baeddSChris Mason btrfs_tree_unlock(c); 38775f39d397SChris Mason free_extent_buffer(c); 3878d97e63b6SChris Mason path->nodes[level] = next; 3879d97e63b6SChris Mason path->slots[level] = 0; 3880a74a4b97SChris Mason if (!path->skip_locking) 3881925baeddSChris Mason path->locks[level] = 1; 3882d97e63b6SChris Mason if (!level) 3883d97e63b6SChris Mason break; 3884925baeddSChris Mason if (level == 1 && path->locks[1] && path->reada) 3885925baeddSChris Mason reada_for_search(root, path, level, slot, 0); 3886ca7a79adSChris Mason next = read_node_slot(root, next, 0); 38875cd57b2cSChris Mason if (!path->skip_locking) { 3888a2135011SChris Mason WARN_ON(!btrfs_tree_locked(path->nodes[level])); 3889925baeddSChris Mason btrfs_tree_lock(next); 3890d97e63b6SChris Mason } 38915cd57b2cSChris Mason } 3892925baeddSChris Mason done: 3893925baeddSChris Mason unlock_up(path, 0, 1); 3894d97e63b6SChris Mason return 0; 3895d97e63b6SChris Mason } 38960b86a832SChris Mason 38973f157a2fSChris Mason /* 38983f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 38993f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 39003f157a2fSChris Mason * 39013f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 39023f157a2fSChris Mason */ 39030b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 39040b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 39050b86a832SChris Mason int type) 39060b86a832SChris Mason { 39070b86a832SChris Mason struct btrfs_key found_key; 39080b86a832SChris Mason struct extent_buffer *leaf; 3909e02119d5SChris Mason u32 nritems; 39100b86a832SChris Mason int ret; 39110b86a832SChris Mason 39120b86a832SChris Mason while (1) { 39130b86a832SChris Mason if (path->slots[0] == 0) { 39140b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 39150b86a832SChris Mason if (ret != 0) 39160b86a832SChris Mason return ret; 39170b86a832SChris Mason } else { 39180b86a832SChris Mason path->slots[0]--; 39190b86a832SChris Mason } 39200b86a832SChris Mason leaf = path->nodes[0]; 3921e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 3922e02119d5SChris Mason if (nritems == 0) 3923e02119d5SChris Mason return 1; 3924e02119d5SChris Mason if (path->slots[0] == nritems) 3925e02119d5SChris Mason path->slots[0]--; 3926e02119d5SChris Mason 39270b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 39280b86a832SChris Mason if (found_key.type == type) 39290b86a832SChris Mason return 0; 3930e02119d5SChris Mason if (found_key.objectid < min_objectid) 3931e02119d5SChris Mason break; 3932e02119d5SChris Mason if (found_key.objectid == min_objectid && 3933e02119d5SChris Mason found_key.type < type) 3934e02119d5SChris Mason break; 39350b86a832SChris Mason } 39360b86a832SChris Mason return 1; 39370b86a832SChris Mason } 3938