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 412c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 422c90e5d6SChris Mason { 43df24a2b9SChris Mason struct btrfs_path *path; 44e00f7308SJeff Mahoney path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 45e00f7308SJeff Mahoney if (path) 462cc58cf2SChris Mason path->reada = 1; 47df24a2b9SChris Mason return path; 482c90e5d6SChris Mason } 492c90e5d6SChris Mason 50b4ce94deSChris Mason /* 51b4ce94deSChris Mason * set all locked nodes in the path to blocking locks. This should 52b4ce94deSChris Mason * be done before scheduling 53b4ce94deSChris Mason */ 54b4ce94deSChris Mason noinline void btrfs_set_path_blocking(struct btrfs_path *p) 55b4ce94deSChris Mason { 56b4ce94deSChris Mason int i; 57b4ce94deSChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 58b4ce94deSChris Mason if (p->nodes[i] && p->locks[i]) 59b4ce94deSChris Mason btrfs_set_lock_blocking(p->nodes[i]); 60b4ce94deSChris Mason } 61b4ce94deSChris Mason } 62b4ce94deSChris Mason 63b4ce94deSChris Mason /* 64b4ce94deSChris Mason * reset all the locked nodes in the patch to spinning locks. 654008c04aSChris Mason * 664008c04aSChris Mason * held is used to keep lockdep happy, when lockdep is enabled 674008c04aSChris Mason * we set held to a blocking lock before we go around and 684008c04aSChris Mason * retake all the spinlocks in the path. You can safely use NULL 694008c04aSChris Mason * for held 70b4ce94deSChris Mason */ 714008c04aSChris Mason noinline void btrfs_clear_path_blocking(struct btrfs_path *p, 724008c04aSChris Mason struct extent_buffer *held) 73b4ce94deSChris Mason { 74b4ce94deSChris Mason int i; 754008c04aSChris Mason 764008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 774008c04aSChris Mason /* lockdep really cares that we take all of these spinlocks 784008c04aSChris Mason * in the right order. If any of the locks in the path are not 794008c04aSChris Mason * currently blocking, it is going to complain. So, make really 804008c04aSChris Mason * really sure by forcing the path to blocking before we clear 814008c04aSChris Mason * the path blocking. 824008c04aSChris Mason */ 834008c04aSChris Mason if (held) 844008c04aSChris Mason btrfs_set_lock_blocking(held); 854008c04aSChris Mason btrfs_set_path_blocking(p); 864008c04aSChris Mason #endif 874008c04aSChris Mason 884008c04aSChris Mason for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) { 89b4ce94deSChris Mason if (p->nodes[i] && p->locks[i]) 90b4ce94deSChris Mason btrfs_clear_lock_blocking(p->nodes[i]); 91b4ce94deSChris Mason } 924008c04aSChris Mason 934008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 944008c04aSChris Mason if (held) 954008c04aSChris Mason btrfs_clear_lock_blocking(held); 964008c04aSChris Mason #endif 97b4ce94deSChris Mason } 98b4ce94deSChris Mason 99d352ac68SChris Mason /* this also releases the path */ 1002c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 1012c90e5d6SChris Mason { 102df24a2b9SChris Mason btrfs_release_path(NULL, p); 1032c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 1042c90e5d6SChris Mason } 1052c90e5d6SChris Mason 106d352ac68SChris Mason /* 107d352ac68SChris Mason * path release drops references on the extent buffers in the path 108d352ac68SChris Mason * and it drops any locks held by this path 109d352ac68SChris Mason * 110d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 111d352ac68SChris Mason */ 112d397712bSChris Mason noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 113eb60ceacSChris Mason { 114eb60ceacSChris Mason int i; 115a2135011SChris Mason 116234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 1173f157a2fSChris Mason p->slots[i] = 0; 118eb60ceacSChris Mason if (!p->nodes[i]) 119925baeddSChris Mason continue; 120925baeddSChris Mason if (p->locks[i]) { 121925baeddSChris Mason btrfs_tree_unlock(p->nodes[i]); 122925baeddSChris Mason p->locks[i] = 0; 123925baeddSChris Mason } 1245f39d397SChris Mason free_extent_buffer(p->nodes[i]); 1253f157a2fSChris Mason p->nodes[i] = NULL; 126eb60ceacSChris Mason } 127eb60ceacSChris Mason } 128eb60ceacSChris Mason 129d352ac68SChris Mason /* 130d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 131d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 132d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 133d352ac68SChris Mason * looping required. 134d352ac68SChris Mason * 135d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 136d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 137d352ac68SChris Mason * at any time because there are no locks held. 138d352ac68SChris Mason */ 139925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 140925baeddSChris Mason { 141925baeddSChris Mason struct extent_buffer *eb; 142925baeddSChris Mason spin_lock(&root->node_lock); 143925baeddSChris Mason eb = root->node; 144925baeddSChris Mason extent_buffer_get(eb); 145925baeddSChris Mason spin_unlock(&root->node_lock); 146925baeddSChris Mason return eb; 147925baeddSChris Mason } 148925baeddSChris Mason 149d352ac68SChris Mason /* loop around taking references on and locking the root node of the 150d352ac68SChris Mason * tree until you end up with a lock on the root. A locked buffer 151d352ac68SChris Mason * is returned, with a reference held. 152d352ac68SChris Mason */ 153925baeddSChris Mason struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root) 154925baeddSChris Mason { 155925baeddSChris Mason struct extent_buffer *eb; 156925baeddSChris Mason 157925baeddSChris Mason while (1) { 158925baeddSChris Mason eb = btrfs_root_node(root); 159925baeddSChris Mason btrfs_tree_lock(eb); 160925baeddSChris Mason 161925baeddSChris Mason spin_lock(&root->node_lock); 162925baeddSChris Mason if (eb == root->node) { 163925baeddSChris Mason spin_unlock(&root->node_lock); 164925baeddSChris Mason break; 165925baeddSChris Mason } 166925baeddSChris Mason spin_unlock(&root->node_lock); 167925baeddSChris Mason 168925baeddSChris Mason btrfs_tree_unlock(eb); 169925baeddSChris Mason free_extent_buffer(eb); 170925baeddSChris Mason } 171925baeddSChris Mason return eb; 172925baeddSChris Mason } 173925baeddSChris Mason 174d352ac68SChris Mason /* cowonly root (everything not a reference counted cow subvolume), just get 175d352ac68SChris Mason * put onto a simple dirty list. transaction.c walks this to make sure they 176d352ac68SChris Mason * get properly updated on disk. 177d352ac68SChris Mason */ 1780b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 1790b86a832SChris Mason { 1800b86a832SChris Mason if (root->track_dirty && list_empty(&root->dirty_list)) { 1810b86a832SChris Mason list_add(&root->dirty_list, 1820b86a832SChris Mason &root->fs_info->dirty_cowonly_roots); 1830b86a832SChris Mason } 1840b86a832SChris Mason } 1850b86a832SChris Mason 186d352ac68SChris Mason /* 187d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 188d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 189d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 190d352ac68SChris Mason */ 191be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 192be20aa9dSChris Mason struct btrfs_root *root, 193be20aa9dSChris Mason struct extent_buffer *buf, 194be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 195be20aa9dSChris Mason { 196be20aa9dSChris Mason struct extent_buffer *cow; 197be20aa9dSChris Mason u32 nritems; 198be20aa9dSChris Mason int ret = 0; 199be20aa9dSChris Mason int level; 2004aec2b52SChris Mason struct btrfs_root *new_root; 201be20aa9dSChris Mason 2024aec2b52SChris Mason new_root = kmalloc(sizeof(*new_root), GFP_NOFS); 2034aec2b52SChris Mason if (!new_root) 2044aec2b52SChris Mason return -ENOMEM; 2054aec2b52SChris Mason 2064aec2b52SChris Mason memcpy(new_root, root, sizeof(*new_root)); 2074aec2b52SChris Mason new_root->root_key.objectid = new_root_objectid; 208be20aa9dSChris Mason 209be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != 210be20aa9dSChris Mason root->fs_info->running_transaction->transid); 211be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 212be20aa9dSChris Mason 213be20aa9dSChris Mason level = btrfs_header_level(buf); 214be20aa9dSChris Mason nritems = btrfs_header_nritems(buf); 21531840ae1SZheng Yan 21631840ae1SZheng Yan cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0, 21731840ae1SZheng Yan new_root_objectid, trans->transid, 218be20aa9dSChris Mason level, buf->start, 0); 2194aec2b52SChris Mason if (IS_ERR(cow)) { 2204aec2b52SChris Mason kfree(new_root); 221be20aa9dSChris Mason return PTR_ERR(cow); 2224aec2b52SChris Mason } 223be20aa9dSChris Mason 224be20aa9dSChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 225be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 226be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 227be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 22863b10fc4SChris Mason btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); 229be20aa9dSChris Mason 2302b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 2312b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 2322b82032cSYan Zheng BTRFS_FSID_SIZE); 2332b82032cSYan Zheng 234be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 23531840ae1SZheng Yan ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL); 2364aec2b52SChris Mason kfree(new_root); 2374aec2b52SChris Mason 238be20aa9dSChris Mason if (ret) 239be20aa9dSChris Mason return ret; 240be20aa9dSChris Mason 241be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 242be20aa9dSChris Mason *cow_ret = cow; 243be20aa9dSChris Mason return 0; 244be20aa9dSChris Mason } 245be20aa9dSChris Mason 246d352ac68SChris Mason /* 247d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 248d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 249d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 250d397712bSChris Mason * dirty again. 251d352ac68SChris Mason * 252d352ac68SChris Mason * search_start -- an allocation hint for the new block 253d352ac68SChris Mason * 254d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 255d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 256d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 257d352ac68SChris Mason */ 258d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 2595f39d397SChris Mason struct btrfs_root *root, 2605f39d397SChris Mason struct extent_buffer *buf, 2615f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 2625f39d397SChris Mason struct extent_buffer **cow_ret, 2639fa8cfe7SChris Mason u64 search_start, u64 empty_size) 2646702ed49SChris Mason { 26531840ae1SZheng Yan u64 parent_start; 2665f39d397SChris Mason struct extent_buffer *cow; 2677bb86316SChris Mason u32 nritems; 2686702ed49SChris Mason int ret = 0; 2697bb86316SChris Mason int level; 270925baeddSChris Mason int unlock_orig = 0; 2716702ed49SChris Mason 272925baeddSChris Mason if (*cow_ret == buf) 273925baeddSChris Mason unlock_orig = 1; 274925baeddSChris Mason 275b9447ef8SChris Mason btrfs_assert_tree_locked(buf); 276925baeddSChris Mason 27731840ae1SZheng Yan if (parent) 27831840ae1SZheng Yan parent_start = parent->start; 27931840ae1SZheng Yan else 28031840ae1SZheng Yan parent_start = 0; 28131840ae1SZheng Yan 2827bb86316SChris Mason WARN_ON(root->ref_cows && trans->transid != 2837bb86316SChris Mason root->fs_info->running_transaction->transid); 2846702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 2855f39d397SChris Mason 2867bb86316SChris Mason level = btrfs_header_level(buf); 2877bb86316SChris Mason nritems = btrfs_header_nritems(buf); 28831840ae1SZheng Yan 289925baeddSChris Mason cow = btrfs_alloc_free_block(trans, root, buf->len, 2909fa8cfe7SChris Mason parent_start, root->root_key.objectid, 29131840ae1SZheng Yan trans->transid, level, 29231840ae1SZheng Yan search_start, empty_size); 2936702ed49SChris Mason if (IS_ERR(cow)) 2946702ed49SChris Mason return PTR_ERR(cow); 2956702ed49SChris Mason 296b4ce94deSChris Mason /* cow is set to blocking by btrfs_init_new_buffer */ 297b4ce94deSChris Mason 2985f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 299db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 3005f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 3015f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 30263b10fc4SChris Mason btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN); 3036702ed49SChris Mason 3042b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 3052b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 3062b82032cSYan Zheng BTRFS_FSID_SIZE); 3072b82032cSYan Zheng 3085f39d397SChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 3095f39d397SChris Mason if (btrfs_header_generation(buf) != trans->transid) { 31031840ae1SZheng Yan u32 nr_extents; 31131840ae1SZheng Yan ret = btrfs_inc_ref(trans, root, buf, cow, &nr_extents); 3126702ed49SChris Mason if (ret) 3136702ed49SChris Mason return ret; 31431840ae1SZheng Yan 31531840ae1SZheng Yan ret = btrfs_cache_ref(trans, root, buf, nr_extents); 31631840ae1SZheng Yan WARN_ON(ret); 3171a40e23bSZheng Yan } else if (btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID) { 3181a40e23bSZheng Yan /* 3191a40e23bSZheng Yan * There are only two places that can drop reference to 3201a40e23bSZheng Yan * tree blocks owned by living reloc trees, one is here, 321f82d02d9SYan Zheng * the other place is btrfs_drop_subtree. In both places, 3221a40e23bSZheng Yan * we check reference count while tree block is locked. 3231a40e23bSZheng Yan * Furthermore, if reference count is one, it won't get 3241a40e23bSZheng Yan * increased by someone else. 3251a40e23bSZheng Yan */ 3261a40e23bSZheng Yan u32 refs; 3271a40e23bSZheng Yan ret = btrfs_lookup_extent_ref(trans, root, buf->start, 3281a40e23bSZheng Yan buf->len, &refs); 3291a40e23bSZheng Yan BUG_ON(ret); 3301a40e23bSZheng Yan if (refs == 1) { 3311a40e23bSZheng Yan ret = btrfs_update_ref(trans, root, buf, cow, 3321a40e23bSZheng Yan 0, nritems); 3331a40e23bSZheng Yan clean_tree_block(trans, root, buf); 3341a40e23bSZheng Yan } else { 3351a40e23bSZheng Yan ret = btrfs_inc_ref(trans, root, buf, cow, NULL); 3361a40e23bSZheng Yan } 3371a40e23bSZheng Yan BUG_ON(ret); 3386702ed49SChris Mason } else { 33931840ae1SZheng Yan ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems); 34031840ae1SZheng Yan if (ret) 34131840ae1SZheng Yan return ret; 3426702ed49SChris Mason clean_tree_block(trans, root, buf); 3436702ed49SChris Mason } 3446702ed49SChris Mason 3451a40e23bSZheng Yan if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) { 3461a40e23bSZheng Yan ret = btrfs_reloc_tree_cache_ref(trans, root, cow, buf->start); 3471a40e23bSZheng Yan WARN_ON(ret); 3481a40e23bSZheng Yan } 3491a40e23bSZheng Yan 3506702ed49SChris Mason if (buf == root->node) { 351925baeddSChris Mason WARN_ON(parent && parent != buf); 352925baeddSChris Mason 353925baeddSChris Mason spin_lock(&root->node_lock); 3546702ed49SChris Mason root->node = cow; 3555f39d397SChris Mason extent_buffer_get(cow); 356925baeddSChris Mason spin_unlock(&root->node_lock); 357925baeddSChris Mason 3586702ed49SChris Mason if (buf != root->commit_root) { 359db94535dSChris Mason btrfs_free_extent(trans, root, buf->start, 36031840ae1SZheng Yan buf->len, buf->start, 36131840ae1SZheng Yan root->root_key.objectid, 36231840ae1SZheng Yan btrfs_header_generation(buf), 3633bb1a1bcSYan Zheng level, 1); 3646702ed49SChris Mason } 3655f39d397SChris Mason free_extent_buffer(buf); 3660b86a832SChris Mason add_root_to_dirty_list(root); 3676702ed49SChris Mason } else { 3685f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 369db94535dSChris Mason cow->start); 37074493f7aSChris Mason WARN_ON(trans->transid == 0); 37174493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 37274493f7aSChris Mason trans->transid); 3736702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 3745f39d397SChris Mason WARN_ON(btrfs_header_generation(parent) != trans->transid); 3757bb86316SChris Mason btrfs_free_extent(trans, root, buf->start, buf->len, 37631840ae1SZheng Yan parent_start, btrfs_header_owner(parent), 3773bb1a1bcSYan Zheng btrfs_header_generation(parent), level, 1); 3786702ed49SChris Mason } 379925baeddSChris Mason if (unlock_orig) 380925baeddSChris Mason btrfs_tree_unlock(buf); 3815f39d397SChris Mason free_extent_buffer(buf); 3826702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 3836702ed49SChris Mason *cow_ret = cow; 3846702ed49SChris Mason return 0; 3856702ed49SChris Mason } 3866702ed49SChris Mason 387d352ac68SChris Mason /* 388d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 389d352ac68SChris Mason * This version of it has extra checks so that a block isn't cow'd more than 390d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 391d352ac68SChris Mason */ 392d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 3935f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 3945f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 3959fa8cfe7SChris Mason struct extent_buffer **cow_ret) 39602217ed2SChris Mason { 3976702ed49SChris Mason u64 search_start; 398f510cfecSChris Mason int ret; 399dc17ff8fSChris Mason 400ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 401d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 402d397712bSChris Mason (unsigned long long)trans->transid, 403d397712bSChris Mason (unsigned long long) 404ccd467d6SChris Mason root->fs_info->running_transaction->transid); 405ccd467d6SChris Mason WARN_ON(1); 406ccd467d6SChris Mason } 407ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 408d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 409d397712bSChris Mason (unsigned long long)trans->transid, 410d397712bSChris Mason (unsigned long long)root->fs_info->generation); 411ccd467d6SChris Mason WARN_ON(1); 412ccd467d6SChris Mason } 413dc17ff8fSChris Mason 4145b21f2edSZheng Yan if (btrfs_header_generation(buf) == trans->transid && 4155b21f2edSZheng Yan btrfs_header_owner(buf) == root->root_key.objectid && 41663b10fc4SChris Mason !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) { 41702217ed2SChris Mason *cow_ret = buf; 41802217ed2SChris Mason return 0; 41902217ed2SChris Mason } 420c487685dSChris Mason 4210b86a832SChris Mason search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); 422b4ce94deSChris Mason 423b4ce94deSChris Mason if (parent) 424b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 425b4ce94deSChris Mason btrfs_set_lock_blocking(buf); 426b4ce94deSChris Mason 427f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 4289fa8cfe7SChris Mason parent_slot, cow_ret, search_start, 0); 429f510cfecSChris Mason return ret; 4302c90e5d6SChris Mason } 4316702ed49SChris Mason 432d352ac68SChris Mason /* 433d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 434d352ac68SChris Mason * node are actually close by 435d352ac68SChris Mason */ 4366b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 4376702ed49SChris Mason { 4386b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 4396702ed49SChris Mason return 1; 4406b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 4416702ed49SChris Mason return 1; 44202217ed2SChris Mason return 0; 44302217ed2SChris Mason } 44402217ed2SChris Mason 445081e9573SChris Mason /* 446081e9573SChris Mason * compare two keys in a memcmp fashion 447081e9573SChris Mason */ 448081e9573SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 449081e9573SChris Mason { 450081e9573SChris Mason struct btrfs_key k1; 451081e9573SChris Mason 452081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 453081e9573SChris Mason 454081e9573SChris Mason if (k1.objectid > k2->objectid) 455081e9573SChris Mason return 1; 456081e9573SChris Mason if (k1.objectid < k2->objectid) 457081e9573SChris Mason return -1; 458081e9573SChris Mason if (k1.type > k2->type) 459081e9573SChris Mason return 1; 460081e9573SChris Mason if (k1.type < k2->type) 461081e9573SChris Mason return -1; 462081e9573SChris Mason if (k1.offset > k2->offset) 463081e9573SChris Mason return 1; 464081e9573SChris Mason if (k1.offset < k2->offset) 465081e9573SChris Mason return -1; 466081e9573SChris Mason return 0; 467081e9573SChris Mason } 468081e9573SChris Mason 469f3465ca4SJosef Bacik /* 470f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 471f3465ca4SJosef Bacik */ 472f3465ca4SJosef Bacik static int comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2) 473f3465ca4SJosef Bacik { 474f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 475f3465ca4SJosef Bacik return 1; 476f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 477f3465ca4SJosef Bacik return -1; 478f3465ca4SJosef Bacik if (k1->type > k2->type) 479f3465ca4SJosef Bacik return 1; 480f3465ca4SJosef Bacik if (k1->type < k2->type) 481f3465ca4SJosef Bacik return -1; 482f3465ca4SJosef Bacik if (k1->offset > k2->offset) 483f3465ca4SJosef Bacik return 1; 484f3465ca4SJosef Bacik if (k1->offset < k2->offset) 485f3465ca4SJosef Bacik return -1; 486f3465ca4SJosef Bacik return 0; 487f3465ca4SJosef Bacik } 488081e9573SChris Mason 489d352ac68SChris Mason /* 490d352ac68SChris Mason * this is used by the defrag code to go through all the 491d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 492d352ac68SChris Mason * disk order is close to key order 493d352ac68SChris Mason */ 4946702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 4955f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 496a6b6e75eSChris Mason int start_slot, int cache_only, u64 *last_ret, 497a6b6e75eSChris Mason struct btrfs_key *progress) 4986702ed49SChris Mason { 4996b80053dSChris Mason struct extent_buffer *cur; 5006702ed49SChris Mason u64 blocknr; 501ca7a79adSChris Mason u64 gen; 502e9d0b13bSChris Mason u64 search_start = *last_ret; 503e9d0b13bSChris Mason u64 last_block = 0; 5046702ed49SChris Mason u64 other; 5056702ed49SChris Mason u32 parent_nritems; 5066702ed49SChris Mason int end_slot; 5076702ed49SChris Mason int i; 5086702ed49SChris Mason int err = 0; 509f2183bdeSChris Mason int parent_level; 5106b80053dSChris Mason int uptodate; 5116b80053dSChris Mason u32 blocksize; 512081e9573SChris Mason int progress_passed = 0; 513081e9573SChris Mason struct btrfs_disk_key disk_key; 5146702ed49SChris Mason 5155708b959SChris Mason parent_level = btrfs_header_level(parent); 5165708b959SChris Mason if (cache_only && parent_level != 1) 5175708b959SChris Mason return 0; 5185708b959SChris Mason 519d397712bSChris Mason if (trans->transaction != root->fs_info->running_transaction) 5206702ed49SChris Mason WARN_ON(1); 521d397712bSChris Mason if (trans->transid != root->fs_info->generation) 5226702ed49SChris Mason WARN_ON(1); 52386479a04SChris Mason 5246b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 5256b80053dSChris Mason blocksize = btrfs_level_size(root, parent_level - 1); 5266702ed49SChris Mason end_slot = parent_nritems; 5276702ed49SChris Mason 5286702ed49SChris Mason if (parent_nritems == 1) 5296702ed49SChris Mason return 0; 5306702ed49SChris Mason 531b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 532b4ce94deSChris Mason 5336702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 5346702ed49SChris Mason int close = 1; 535a6b6e75eSChris Mason 5365708b959SChris Mason if (!parent->map_token) { 5375708b959SChris Mason map_extent_buffer(parent, 5385708b959SChris Mason btrfs_node_key_ptr_offset(i), 5395708b959SChris Mason sizeof(struct btrfs_key_ptr), 5405708b959SChris Mason &parent->map_token, &parent->kaddr, 5415708b959SChris Mason &parent->map_start, &parent->map_len, 5425708b959SChris Mason KM_USER1); 5435708b959SChris Mason } 544081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 545081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 546081e9573SChris Mason continue; 547081e9573SChris Mason 548081e9573SChris Mason progress_passed = 1; 5496b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 550ca7a79adSChris Mason gen = btrfs_node_ptr_generation(parent, i); 551e9d0b13bSChris Mason if (last_block == 0) 552e9d0b13bSChris Mason last_block = blocknr; 5535708b959SChris Mason 5546702ed49SChris Mason if (i > 0) { 5556b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 5566b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 5576702ed49SChris Mason } 5580ef3e66bSChris Mason if (!close && i < end_slot - 2) { 5596b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 5606b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 5616702ed49SChris Mason } 562e9d0b13bSChris Mason if (close) { 563e9d0b13bSChris Mason last_block = blocknr; 5646702ed49SChris Mason continue; 565e9d0b13bSChris Mason } 5665708b959SChris Mason if (parent->map_token) { 5675708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 5685708b959SChris Mason KM_USER1); 5695708b959SChris Mason parent->map_token = NULL; 5705708b959SChris Mason } 5716702ed49SChris Mason 5726b80053dSChris Mason cur = btrfs_find_tree_block(root, blocknr, blocksize); 5736b80053dSChris Mason if (cur) 5741259ab75SChris Mason uptodate = btrfs_buffer_uptodate(cur, gen); 5756b80053dSChris Mason else 5766b80053dSChris Mason uptodate = 0; 5775708b959SChris Mason if (!cur || !uptodate) { 5786702ed49SChris Mason if (cache_only) { 5796b80053dSChris Mason free_extent_buffer(cur); 5806702ed49SChris Mason continue; 5816702ed49SChris Mason } 5826b80053dSChris Mason if (!cur) { 5836b80053dSChris Mason cur = read_tree_block(root, blocknr, 584ca7a79adSChris Mason blocksize, gen); 5856b80053dSChris Mason } else if (!uptodate) { 586ca7a79adSChris Mason btrfs_read_buffer(cur, gen); 5876702ed49SChris Mason } 588f2183bdeSChris Mason } 589e9d0b13bSChris Mason if (search_start == 0) 5906b80053dSChris Mason search_start = last_block; 591e9d0b13bSChris Mason 592e7a84565SChris Mason btrfs_tree_lock(cur); 593b4ce94deSChris Mason btrfs_set_lock_blocking(cur); 5946b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 595e7a84565SChris Mason &cur, search_start, 5966b80053dSChris Mason min(16 * blocksize, 5979fa8cfe7SChris Mason (end_slot - i) * blocksize)); 598252c38f0SYan if (err) { 599e7a84565SChris Mason btrfs_tree_unlock(cur); 6006b80053dSChris Mason free_extent_buffer(cur); 6016702ed49SChris Mason break; 602252c38f0SYan } 603e7a84565SChris Mason search_start = cur->start; 604e7a84565SChris Mason last_block = cur->start; 605f2183bdeSChris Mason *last_ret = search_start; 606e7a84565SChris Mason btrfs_tree_unlock(cur); 607e7a84565SChris Mason free_extent_buffer(cur); 6086702ed49SChris Mason } 6095708b959SChris Mason if (parent->map_token) { 6105708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 6115708b959SChris Mason KM_USER1); 6125708b959SChris Mason parent->map_token = NULL; 6135708b959SChris Mason } 6146702ed49SChris Mason return err; 6156702ed49SChris Mason } 6166702ed49SChris Mason 61774123bd7SChris Mason /* 61874123bd7SChris Mason * The leaf data grows from end-to-front in the node. 61974123bd7SChris Mason * this returns the address of the start of the last item, 62074123bd7SChris Mason * which is the stop of the leaf data stack 62174123bd7SChris Mason */ 622123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 6235f39d397SChris Mason struct extent_buffer *leaf) 624be0e5c09SChris Mason { 6255f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 626be0e5c09SChris Mason if (nr == 0) 627123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 6285f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 629be0e5c09SChris Mason } 630be0e5c09SChris Mason 631d352ac68SChris Mason /* 632d352ac68SChris Mason * extra debugging checks to make sure all the items in a key are 633d352ac68SChris Mason * well formed and in the proper order 634d352ac68SChris Mason */ 635123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 636123abc88SChris Mason int level) 637aa5d6bedSChris Mason { 6385f39d397SChris Mason struct extent_buffer *parent = NULL; 6395f39d397SChris Mason struct extent_buffer *node = path->nodes[level]; 6405f39d397SChris Mason struct btrfs_disk_key parent_key; 6415f39d397SChris Mason struct btrfs_disk_key node_key; 642aa5d6bedSChris Mason int parent_slot; 6438d7be552SChris Mason int slot; 6448d7be552SChris Mason struct btrfs_key cpukey; 6455f39d397SChris Mason u32 nritems = btrfs_header_nritems(node); 646aa5d6bedSChris Mason 647aa5d6bedSChris Mason if (path->nodes[level + 1]) 6485f39d397SChris Mason parent = path->nodes[level + 1]; 649a1f39630SAneesh 6508d7be552SChris Mason slot = path->slots[level]; 6517518a238SChris Mason BUG_ON(nritems == 0); 6527518a238SChris Mason if (parent) { 653a1f39630SAneesh parent_slot = path->slots[level + 1]; 6545f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 6555f39d397SChris Mason btrfs_node_key(node, &node_key, 0); 6565f39d397SChris Mason BUG_ON(memcmp(&parent_key, &node_key, 657e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 6581d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 659db94535dSChris Mason btrfs_header_bytenr(node)); 660aa5d6bedSChris Mason } 661123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 6628d7be552SChris Mason if (slot != 0) { 6635f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot - 1); 6645f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 6655f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) <= 0); 6668d7be552SChris Mason } 6678d7be552SChris Mason if (slot < nritems - 1) { 6685f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot + 1); 6695f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 6705f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) >= 0); 671aa5d6bedSChris Mason } 672aa5d6bedSChris Mason return 0; 673aa5d6bedSChris Mason } 674aa5d6bedSChris Mason 675d352ac68SChris Mason /* 676d352ac68SChris Mason * extra checking to make sure all the items in a leaf are 677d352ac68SChris Mason * well formed and in the proper order 678d352ac68SChris Mason */ 679123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 680123abc88SChris Mason int level) 681aa5d6bedSChris Mason { 6825f39d397SChris Mason struct extent_buffer *leaf = path->nodes[level]; 6835f39d397SChris Mason struct extent_buffer *parent = NULL; 684aa5d6bedSChris Mason int parent_slot; 6858d7be552SChris Mason struct btrfs_key cpukey; 6865f39d397SChris Mason struct btrfs_disk_key parent_key; 6875f39d397SChris Mason struct btrfs_disk_key leaf_key; 6885f39d397SChris Mason int slot = path->slots[0]; 6898d7be552SChris Mason 6905f39d397SChris Mason u32 nritems = btrfs_header_nritems(leaf); 691aa5d6bedSChris Mason 692aa5d6bedSChris Mason if (path->nodes[level + 1]) 6935f39d397SChris Mason parent = path->nodes[level + 1]; 6947518a238SChris Mason 6957518a238SChris Mason if (nritems == 0) 6967518a238SChris Mason return 0; 6977518a238SChris Mason 6987518a238SChris Mason if (parent) { 699a1f39630SAneesh parent_slot = path->slots[level + 1]; 7005f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 7015f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, 0); 7026702ed49SChris Mason 7035f39d397SChris Mason BUG_ON(memcmp(&parent_key, &leaf_key, 704e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 7051d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 706db94535dSChris Mason btrfs_header_bytenr(leaf)); 707aa5d6bedSChris Mason } 7085f39d397SChris Mason if (slot != 0 && slot < nritems - 1) { 7095f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 7105f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1); 7115f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) <= 0) { 7125f39d397SChris Mason btrfs_print_leaf(root, leaf); 713d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad key\n", slot); 7145f39d397SChris Mason BUG_ON(1); 7155f39d397SChris Mason } 7165f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot - 1) != 7175f39d397SChris Mason btrfs_item_end_nr(leaf, slot)) { 7185f39d397SChris Mason btrfs_print_leaf(root, leaf); 719d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad\n", slot); 7205f39d397SChris Mason BUG_ON(1); 7215f39d397SChris Mason } 722aa5d6bedSChris Mason } 7238d7be552SChris Mason if (slot < nritems - 1) { 7245f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 7255f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1); 7265f39d397SChris Mason BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0); 7275f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot) != 7285f39d397SChris Mason btrfs_item_end_nr(leaf, slot + 1)) { 7295f39d397SChris Mason btrfs_print_leaf(root, leaf); 730d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad\n", slot); 7315f39d397SChris Mason BUG_ON(1); 732aa5d6bedSChris Mason } 7335f39d397SChris Mason } 7345f39d397SChris Mason BUG_ON(btrfs_item_offset_nr(leaf, 0) + 7355f39d397SChris Mason btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root)); 736aa5d6bedSChris Mason return 0; 737aa5d6bedSChris Mason } 738aa5d6bedSChris Mason 739d397712bSChris Mason static noinline int check_block(struct btrfs_root *root, 74098ed5174SChris Mason struct btrfs_path *path, int level) 741aa5d6bedSChris Mason { 74285d824c4SChris Mason return 0; 743aa5d6bedSChris Mason if (level == 0) 744123abc88SChris Mason return check_leaf(root, path, level); 745123abc88SChris Mason return check_node(root, path, level); 746aa5d6bedSChris Mason } 747aa5d6bedSChris Mason 74874123bd7SChris Mason /* 7495f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 7505f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 7515f39d397SChris Mason * 75274123bd7SChris Mason * the slot in the array is returned via slot, and it points to 75374123bd7SChris Mason * the place where you would insert key if it is not found in 75474123bd7SChris Mason * the array. 75574123bd7SChris Mason * 75674123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 75774123bd7SChris Mason */ 758e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 759e02119d5SChris Mason unsigned long p, 7605f39d397SChris Mason int item_size, struct btrfs_key *key, 761be0e5c09SChris Mason int max, int *slot) 762be0e5c09SChris Mason { 763be0e5c09SChris Mason int low = 0; 764be0e5c09SChris Mason int high = max; 765be0e5c09SChris Mason int mid; 766be0e5c09SChris Mason int ret; 767479965d6SChris Mason struct btrfs_disk_key *tmp = NULL; 7685f39d397SChris Mason struct btrfs_disk_key unaligned; 7695f39d397SChris Mason unsigned long offset; 7705f39d397SChris Mason char *map_token = NULL; 7715f39d397SChris Mason char *kaddr = NULL; 7725f39d397SChris Mason unsigned long map_start = 0; 7735f39d397SChris Mason unsigned long map_len = 0; 774479965d6SChris Mason int err; 775be0e5c09SChris Mason 776be0e5c09SChris Mason while (low < high) { 777be0e5c09SChris Mason mid = (low + high) / 2; 7785f39d397SChris Mason offset = p + mid * item_size; 7795f39d397SChris Mason 7805f39d397SChris Mason if (!map_token || offset < map_start || 7815f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 7825f39d397SChris Mason map_start + map_len) { 783479965d6SChris Mason if (map_token) { 7845f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 785479965d6SChris Mason map_token = NULL; 786479965d6SChris Mason } 787934d375bSChris Mason 788934d375bSChris Mason err = map_private_extent_buffer(eb, offset, 789479965d6SChris Mason sizeof(struct btrfs_disk_key), 790479965d6SChris Mason &map_token, &kaddr, 7915f39d397SChris Mason &map_start, &map_len, KM_USER0); 7925f39d397SChris Mason 793479965d6SChris Mason if (!err) { 794479965d6SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 795479965d6SChris Mason map_start); 796479965d6SChris Mason } else { 7975f39d397SChris Mason read_extent_buffer(eb, &unaligned, 7985f39d397SChris Mason offset, sizeof(unaligned)); 7995f39d397SChris Mason tmp = &unaligned; 800479965d6SChris Mason } 801479965d6SChris Mason 8025f39d397SChris Mason } else { 8035f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 8045f39d397SChris Mason map_start); 8055f39d397SChris Mason } 806be0e5c09SChris Mason ret = comp_keys(tmp, key); 807be0e5c09SChris Mason 808be0e5c09SChris Mason if (ret < 0) 809be0e5c09SChris Mason low = mid + 1; 810be0e5c09SChris Mason else if (ret > 0) 811be0e5c09SChris Mason high = mid; 812be0e5c09SChris Mason else { 813be0e5c09SChris Mason *slot = mid; 814479965d6SChris Mason if (map_token) 8155f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 816be0e5c09SChris Mason return 0; 817be0e5c09SChris Mason } 818be0e5c09SChris Mason } 819be0e5c09SChris Mason *slot = low; 8205f39d397SChris Mason if (map_token) 8215f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 822be0e5c09SChris Mason return 1; 823be0e5c09SChris Mason } 824be0e5c09SChris Mason 82597571fd0SChris Mason /* 82697571fd0SChris Mason * simple bin_search frontend that does the right thing for 82797571fd0SChris Mason * leaves vs nodes 82897571fd0SChris Mason */ 8295f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 8305f39d397SChris Mason int level, int *slot) 831be0e5c09SChris Mason { 8325f39d397SChris Mason if (level == 0) { 8335f39d397SChris Mason return generic_bin_search(eb, 8345f39d397SChris Mason offsetof(struct btrfs_leaf, items), 8350783fcfcSChris Mason sizeof(struct btrfs_item), 8365f39d397SChris Mason key, btrfs_header_nritems(eb), 8377518a238SChris Mason slot); 838be0e5c09SChris Mason } else { 8395f39d397SChris Mason return generic_bin_search(eb, 8405f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 841123abc88SChris Mason sizeof(struct btrfs_key_ptr), 8425f39d397SChris Mason key, btrfs_header_nritems(eb), 8437518a238SChris Mason slot); 844be0e5c09SChris Mason } 845be0e5c09SChris Mason return -1; 846be0e5c09SChris Mason } 847be0e5c09SChris Mason 848d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 849d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 850d352ac68SChris Mason * NULL is returned on error. 851d352ac68SChris Mason */ 852e02119d5SChris Mason static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root, 8535f39d397SChris Mason struct extent_buffer *parent, int slot) 854bb803951SChris Mason { 855ca7a79adSChris Mason int level = btrfs_header_level(parent); 856bb803951SChris Mason if (slot < 0) 857bb803951SChris Mason return NULL; 8585f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 859bb803951SChris Mason return NULL; 860ca7a79adSChris Mason 861ca7a79adSChris Mason BUG_ON(level == 0); 862ca7a79adSChris Mason 863db94535dSChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot), 864ca7a79adSChris Mason btrfs_level_size(root, level - 1), 865ca7a79adSChris Mason btrfs_node_ptr_generation(parent, slot)); 866bb803951SChris Mason } 867bb803951SChris Mason 868d352ac68SChris Mason /* 869d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 870d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 871d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 872d352ac68SChris Mason */ 873e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 87498ed5174SChris Mason struct btrfs_root *root, 87598ed5174SChris Mason struct btrfs_path *path, int level) 876bb803951SChris Mason { 8775f39d397SChris Mason struct extent_buffer *right = NULL; 8785f39d397SChris Mason struct extent_buffer *mid; 8795f39d397SChris Mason struct extent_buffer *left = NULL; 8805f39d397SChris Mason struct extent_buffer *parent = NULL; 881bb803951SChris Mason int ret = 0; 882bb803951SChris Mason int wret; 883bb803951SChris Mason int pslot; 884bb803951SChris Mason int orig_slot = path->slots[level]; 88554aa1f4dSChris Mason int err_on_enospc = 0; 88679f95c82SChris Mason u64 orig_ptr; 887bb803951SChris Mason 888bb803951SChris Mason if (level == 0) 889bb803951SChris Mason return 0; 890bb803951SChris Mason 8915f39d397SChris Mason mid = path->nodes[level]; 892b4ce94deSChris Mason 893925baeddSChris Mason WARN_ON(!path->locks[level]); 8947bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 8957bb86316SChris Mason 8961d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 89779f95c82SChris Mason 898234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 8995f39d397SChris Mason parent = path->nodes[level + 1]; 900bb803951SChris Mason pslot = path->slots[level + 1]; 901bb803951SChris Mason 90240689478SChris Mason /* 90340689478SChris Mason * deal with the case where there is only one pointer in the root 90440689478SChris Mason * by promoting the node below to a root 90540689478SChris Mason */ 9065f39d397SChris Mason if (!parent) { 9075f39d397SChris Mason struct extent_buffer *child; 908bb803951SChris Mason 9095f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 910bb803951SChris Mason return 0; 911bb803951SChris Mason 912bb803951SChris Mason /* promote the child to a root */ 9135f39d397SChris Mason child = read_node_slot(root, mid, 0); 9147951f3ceSJeff Mahoney BUG_ON(!child); 915925baeddSChris Mason btrfs_tree_lock(child); 916b4ce94deSChris Mason btrfs_set_lock_blocking(child); 9179fa8cfe7SChris Mason ret = btrfs_cow_block(trans, root, child, mid, 0, &child); 9182f375ab9SYan BUG_ON(ret); 9192f375ab9SYan 920925baeddSChris Mason spin_lock(&root->node_lock); 921bb803951SChris Mason root->node = child; 922925baeddSChris Mason spin_unlock(&root->node_lock); 923925baeddSChris Mason 92431840ae1SZheng Yan ret = btrfs_update_extent_ref(trans, root, child->start, 92556bec294SChris Mason child->len, 92631840ae1SZheng Yan mid->start, child->start, 92731840ae1SZheng Yan root->root_key.objectid, 9283bb1a1bcSYan Zheng trans->transid, level - 1); 92931840ae1SZheng Yan BUG_ON(ret); 93031840ae1SZheng Yan 9310b86a832SChris Mason add_root_to_dirty_list(root); 932925baeddSChris Mason btrfs_tree_unlock(child); 933b4ce94deSChris Mason 934925baeddSChris Mason path->locks[level] = 0; 935bb803951SChris Mason path->nodes[level] = NULL; 9365f39d397SChris Mason clean_tree_block(trans, root, mid); 937925baeddSChris Mason btrfs_tree_unlock(mid); 938bb803951SChris Mason /* once for the path */ 9395f39d397SChris Mason free_extent_buffer(mid); 9407bb86316SChris Mason ret = btrfs_free_extent(trans, root, mid->start, mid->len, 94131840ae1SZheng Yan mid->start, root->root_key.objectid, 9423bb1a1bcSYan Zheng btrfs_header_generation(mid), 9433bb1a1bcSYan Zheng level, 1); 944bb803951SChris Mason /* once for the root ptr */ 9455f39d397SChris Mason free_extent_buffer(mid); 946db94535dSChris Mason return ret; 947bb803951SChris Mason } 9485f39d397SChris Mason if (btrfs_header_nritems(mid) > 949123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 950bb803951SChris Mason return 0; 951bb803951SChris Mason 9525f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 95354aa1f4dSChris Mason err_on_enospc = 1; 95454aa1f4dSChris Mason 9555f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 9565f39d397SChris Mason if (left) { 957925baeddSChris Mason btrfs_tree_lock(left); 958b4ce94deSChris Mason btrfs_set_lock_blocking(left); 9595f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 9609fa8cfe7SChris Mason parent, pslot - 1, &left); 96154aa1f4dSChris Mason if (wret) { 96254aa1f4dSChris Mason ret = wret; 96354aa1f4dSChris Mason goto enospc; 96454aa1f4dSChris Mason } 9652cc58cf2SChris Mason } 9665f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 9675f39d397SChris Mason if (right) { 968925baeddSChris Mason btrfs_tree_lock(right); 969b4ce94deSChris Mason btrfs_set_lock_blocking(right); 9705f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 9719fa8cfe7SChris Mason parent, pslot + 1, &right); 9722cc58cf2SChris Mason if (wret) { 9732cc58cf2SChris Mason ret = wret; 9742cc58cf2SChris Mason goto enospc; 9752cc58cf2SChris Mason } 9762cc58cf2SChris Mason } 9772cc58cf2SChris Mason 9782cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 9795f39d397SChris Mason if (left) { 9805f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 981bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 98279f95c82SChris Mason if (wret < 0) 98379f95c82SChris Mason ret = wret; 9845f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 98554aa1f4dSChris Mason err_on_enospc = 1; 986bb803951SChris Mason } 98779f95c82SChris Mason 98879f95c82SChris Mason /* 98979f95c82SChris Mason * then try to empty the right most buffer into the middle 99079f95c82SChris Mason */ 9915f39d397SChris Mason if (right) { 992971a1f66SChris Mason wret = push_node_left(trans, root, mid, right, 1); 99354aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 99479f95c82SChris Mason ret = wret; 9955f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 996db94535dSChris Mason u64 bytenr = right->start; 9977bb86316SChris Mason u64 generation = btrfs_header_generation(parent); 998db94535dSChris Mason u32 blocksize = right->len; 999db94535dSChris Mason 10005f39d397SChris Mason clean_tree_block(trans, root, right); 1001925baeddSChris Mason btrfs_tree_unlock(right); 10025f39d397SChris Mason free_extent_buffer(right); 1003bb803951SChris Mason right = NULL; 1004e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 1005e089f05cSChris Mason 1); 1006bb803951SChris Mason if (wret) 1007bb803951SChris Mason ret = wret; 1008db94535dSChris Mason wret = btrfs_free_extent(trans, root, bytenr, 100931840ae1SZheng Yan blocksize, parent->start, 10107bb86316SChris Mason btrfs_header_owner(parent), 10113bb1a1bcSYan Zheng generation, level, 1); 1012bb803951SChris Mason if (wret) 1013bb803951SChris Mason ret = wret; 1014bb803951SChris Mason } else { 10155f39d397SChris Mason struct btrfs_disk_key right_key; 10165f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 10175f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 10185f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 1019bb803951SChris Mason } 1020bb803951SChris Mason } 10215f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 102279f95c82SChris Mason /* 102379f95c82SChris Mason * we're not allowed to leave a node with one item in the 102479f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 102579f95c82SChris Mason * could try to delete the only pointer in this node. 102679f95c82SChris Mason * So, pull some keys from the left. 102779f95c82SChris Mason * There has to be a left pointer at this point because 102879f95c82SChris Mason * otherwise we would have pulled some pointers from the 102979f95c82SChris Mason * right 103079f95c82SChris Mason */ 10315f39d397SChris Mason BUG_ON(!left); 10325f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 103354aa1f4dSChris Mason if (wret < 0) { 103479f95c82SChris Mason ret = wret; 103554aa1f4dSChris Mason goto enospc; 103654aa1f4dSChris Mason } 1037bce4eae9SChris Mason if (wret == 1) { 1038bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 1039bce4eae9SChris Mason if (wret < 0) 1040bce4eae9SChris Mason ret = wret; 1041bce4eae9SChris Mason } 104279f95c82SChris Mason BUG_ON(wret == 1); 104379f95c82SChris Mason } 10445f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 104579f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 10467bb86316SChris Mason u64 root_gen = btrfs_header_generation(parent); 1047db94535dSChris Mason u64 bytenr = mid->start; 1048db94535dSChris Mason u32 blocksize = mid->len; 1049925baeddSChris Mason 10505f39d397SChris Mason clean_tree_block(trans, root, mid); 1051925baeddSChris Mason btrfs_tree_unlock(mid); 10525f39d397SChris Mason free_extent_buffer(mid); 1053bb803951SChris Mason mid = NULL; 1054e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 1055bb803951SChris Mason if (wret) 1056bb803951SChris Mason ret = wret; 10577bb86316SChris Mason wret = btrfs_free_extent(trans, root, bytenr, blocksize, 105831840ae1SZheng Yan parent->start, 10597bb86316SChris Mason btrfs_header_owner(parent), 10603bb1a1bcSYan Zheng root_gen, level, 1); 1061bb803951SChris Mason if (wret) 1062bb803951SChris Mason ret = wret; 106379f95c82SChris Mason } else { 106479f95c82SChris Mason /* update the parent key to reflect our changes */ 10655f39d397SChris Mason struct btrfs_disk_key mid_key; 10665f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 10675f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 10685f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 106979f95c82SChris Mason } 1070bb803951SChris Mason 107179f95c82SChris Mason /* update the path */ 10725f39d397SChris Mason if (left) { 10735f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 10745f39d397SChris Mason extent_buffer_get(left); 1075925baeddSChris Mason /* left was locked after cow */ 10765f39d397SChris Mason path->nodes[level] = left; 1077bb803951SChris Mason path->slots[level + 1] -= 1; 1078bb803951SChris Mason path->slots[level] = orig_slot; 1079925baeddSChris Mason if (mid) { 1080925baeddSChris Mason btrfs_tree_unlock(mid); 10815f39d397SChris Mason free_extent_buffer(mid); 1082925baeddSChris Mason } 1083bb803951SChris Mason } else { 10845f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1085bb803951SChris Mason path->slots[level] = orig_slot; 1086bb803951SChris Mason } 1087bb803951SChris Mason } 108879f95c82SChris Mason /* double check we haven't messed things up */ 1089123abc88SChris Mason check_block(root, path, level); 1090e20d96d6SChris Mason if (orig_ptr != 10915f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 109279f95c82SChris Mason BUG(); 109354aa1f4dSChris Mason enospc: 1094925baeddSChris Mason if (right) { 1095925baeddSChris Mason btrfs_tree_unlock(right); 10965f39d397SChris Mason free_extent_buffer(right); 1097925baeddSChris Mason } 1098925baeddSChris Mason if (left) { 1099925baeddSChris Mason if (path->nodes[level] != left) 1100925baeddSChris Mason btrfs_tree_unlock(left); 11015f39d397SChris Mason free_extent_buffer(left); 1102925baeddSChris Mason } 1103bb803951SChris Mason return ret; 1104bb803951SChris Mason } 1105bb803951SChris Mason 1106d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1107d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1108d352ac68SChris Mason * have to be pessimistic. 1109d352ac68SChris Mason */ 1110d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1111e66f709bSChris Mason struct btrfs_root *root, 1112e66f709bSChris Mason struct btrfs_path *path, int level) 1113e66f709bSChris Mason { 11145f39d397SChris Mason struct extent_buffer *right = NULL; 11155f39d397SChris Mason struct extent_buffer *mid; 11165f39d397SChris Mason struct extent_buffer *left = NULL; 11175f39d397SChris Mason struct extent_buffer *parent = NULL; 1118e66f709bSChris Mason int ret = 0; 1119e66f709bSChris Mason int wret; 1120e66f709bSChris Mason int pslot; 1121e66f709bSChris Mason int orig_slot = path->slots[level]; 1122e66f709bSChris Mason u64 orig_ptr; 1123e66f709bSChris Mason 1124e66f709bSChris Mason if (level == 0) 1125e66f709bSChris Mason return 1; 1126e66f709bSChris Mason 11275f39d397SChris Mason mid = path->nodes[level]; 11287bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1129e66f709bSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 1130e66f709bSChris Mason 1131e66f709bSChris Mason if (level < BTRFS_MAX_LEVEL - 1) 11325f39d397SChris Mason parent = path->nodes[level + 1]; 1133e66f709bSChris Mason pslot = path->slots[level + 1]; 1134e66f709bSChris Mason 11355f39d397SChris Mason if (!parent) 1136e66f709bSChris Mason return 1; 1137e66f709bSChris Mason 11385f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 1139e66f709bSChris Mason 1140e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 11415f39d397SChris Mason if (left) { 1142e66f709bSChris Mason u32 left_nr; 1143925baeddSChris Mason 1144925baeddSChris Mason btrfs_tree_lock(left); 1145b4ce94deSChris Mason btrfs_set_lock_blocking(left); 1146b4ce94deSChris Mason 11475f39d397SChris Mason left_nr = btrfs_header_nritems(left); 114833ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 114933ade1f8SChris Mason wret = 1; 115033ade1f8SChris Mason } else { 11515f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 11529fa8cfe7SChris Mason pslot - 1, &left); 115354aa1f4dSChris Mason if (ret) 115454aa1f4dSChris Mason wret = 1; 115554aa1f4dSChris Mason else { 115654aa1f4dSChris Mason wret = push_node_left(trans, root, 1157971a1f66SChris Mason left, mid, 0); 115854aa1f4dSChris Mason } 115933ade1f8SChris Mason } 1160e66f709bSChris Mason if (wret < 0) 1161e66f709bSChris Mason ret = wret; 1162e66f709bSChris Mason if (wret == 0) { 11635f39d397SChris Mason struct btrfs_disk_key disk_key; 1164e66f709bSChris Mason orig_slot += left_nr; 11655f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 11665f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 11675f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 11685f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 11695f39d397SChris Mason path->nodes[level] = left; 1170e66f709bSChris Mason path->slots[level + 1] -= 1; 1171e66f709bSChris Mason path->slots[level] = orig_slot; 1172925baeddSChris Mason btrfs_tree_unlock(mid); 11735f39d397SChris Mason free_extent_buffer(mid); 1174e66f709bSChris Mason } else { 1175e66f709bSChris Mason orig_slot -= 11765f39d397SChris Mason btrfs_header_nritems(left); 1177e66f709bSChris Mason path->slots[level] = orig_slot; 1178925baeddSChris Mason btrfs_tree_unlock(left); 11795f39d397SChris Mason free_extent_buffer(left); 1180e66f709bSChris Mason } 1181e66f709bSChris Mason return 0; 1182e66f709bSChris Mason } 1183925baeddSChris Mason btrfs_tree_unlock(left); 11845f39d397SChris Mason free_extent_buffer(left); 1185e66f709bSChris Mason } 11865f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 1187e66f709bSChris Mason 1188e66f709bSChris Mason /* 1189e66f709bSChris Mason * then try to empty the right most buffer into the middle 1190e66f709bSChris Mason */ 11915f39d397SChris Mason if (right) { 119233ade1f8SChris Mason u32 right_nr; 1193b4ce94deSChris Mason 1194925baeddSChris Mason btrfs_tree_lock(right); 1195b4ce94deSChris Mason btrfs_set_lock_blocking(right); 1196b4ce94deSChris Mason 11975f39d397SChris Mason right_nr = btrfs_header_nritems(right); 119833ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 119933ade1f8SChris Mason wret = 1; 120033ade1f8SChris Mason } else { 12015f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 12025f39d397SChris Mason parent, pslot + 1, 12039fa8cfe7SChris Mason &right); 120454aa1f4dSChris Mason if (ret) 120554aa1f4dSChris Mason wret = 1; 120654aa1f4dSChris Mason else { 120733ade1f8SChris Mason wret = balance_node_right(trans, root, 12085f39d397SChris Mason right, mid); 120933ade1f8SChris Mason } 121054aa1f4dSChris Mason } 1211e66f709bSChris Mason if (wret < 0) 1212e66f709bSChris Mason ret = wret; 1213e66f709bSChris Mason if (wret == 0) { 12145f39d397SChris Mason struct btrfs_disk_key disk_key; 12155f39d397SChris Mason 12165f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 12175f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 12185f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 12195f39d397SChris Mason 12205f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 12215f39d397SChris Mason path->nodes[level] = right; 1222e66f709bSChris Mason path->slots[level + 1] += 1; 1223e66f709bSChris Mason path->slots[level] = orig_slot - 12245f39d397SChris Mason btrfs_header_nritems(mid); 1225925baeddSChris Mason btrfs_tree_unlock(mid); 12265f39d397SChris Mason free_extent_buffer(mid); 1227e66f709bSChris Mason } else { 1228925baeddSChris Mason btrfs_tree_unlock(right); 12295f39d397SChris Mason free_extent_buffer(right); 1230e66f709bSChris Mason } 1231e66f709bSChris Mason return 0; 1232e66f709bSChris Mason } 1233925baeddSChris Mason btrfs_tree_unlock(right); 12345f39d397SChris Mason free_extent_buffer(right); 1235e66f709bSChris Mason } 1236e66f709bSChris Mason return 1; 1237e66f709bSChris Mason } 1238e66f709bSChris Mason 123974123bd7SChris Mason /* 1240d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1241d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 12423c69faecSChris Mason */ 1243e02119d5SChris Mason static noinline void reada_for_search(struct btrfs_root *root, 1244e02119d5SChris Mason struct btrfs_path *path, 124501f46658SChris Mason int level, int slot, u64 objectid) 12463c69faecSChris Mason { 12475f39d397SChris Mason struct extent_buffer *node; 124801f46658SChris Mason struct btrfs_disk_key disk_key; 12493c69faecSChris Mason u32 nritems; 12503c69faecSChris Mason u64 search; 1251a7175319SChris Mason u64 target; 12526b80053dSChris Mason u64 nread = 0; 12533c69faecSChris Mason int direction = path->reada; 12545f39d397SChris Mason struct extent_buffer *eb; 12556b80053dSChris Mason u32 nr; 12566b80053dSChris Mason u32 blocksize; 12576b80053dSChris Mason u32 nscan = 0; 1258db94535dSChris Mason 1259a6b6e75eSChris Mason if (level != 1) 12603c69faecSChris Mason return; 12613c69faecSChris Mason 12626702ed49SChris Mason if (!path->nodes[level]) 12636702ed49SChris Mason return; 12646702ed49SChris Mason 12655f39d397SChris Mason node = path->nodes[level]; 1266925baeddSChris Mason 12673c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 12686b80053dSChris Mason blocksize = btrfs_level_size(root, level - 1); 12696b80053dSChris Mason eb = btrfs_find_tree_block(root, search, blocksize); 12705f39d397SChris Mason if (eb) { 12715f39d397SChris Mason free_extent_buffer(eb); 12723c69faecSChris Mason return; 12733c69faecSChris Mason } 12743c69faecSChris Mason 1275a7175319SChris Mason target = search; 12766b80053dSChris Mason 12775f39d397SChris Mason nritems = btrfs_header_nritems(node); 12786b80053dSChris Mason nr = slot; 12793c69faecSChris Mason while (1) { 12806b80053dSChris Mason if (direction < 0) { 12816b80053dSChris Mason if (nr == 0) 12823c69faecSChris Mason break; 12836b80053dSChris Mason nr--; 12846b80053dSChris Mason } else if (direction > 0) { 12856b80053dSChris Mason nr++; 12866b80053dSChris Mason if (nr >= nritems) 12876b80053dSChris Mason break; 12883c69faecSChris Mason } 128901f46658SChris Mason if (path->reada < 0 && objectid) { 129001f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 129101f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 129201f46658SChris Mason break; 129301f46658SChris Mason } 12946b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1295a7175319SChris Mason if ((search <= target && target - search <= 65536) || 1296a7175319SChris Mason (search > target && search - target <= 65536)) { 1297ca7a79adSChris Mason readahead_tree_block(root, search, blocksize, 1298ca7a79adSChris Mason btrfs_node_ptr_generation(node, nr)); 12996b80053dSChris Mason nread += blocksize; 13003c69faecSChris Mason } 13016b80053dSChris Mason nscan++; 1302a7175319SChris Mason if ((nread > 65536 || nscan > 32)) 13036b80053dSChris Mason break; 13043c69faecSChris Mason } 13053c69faecSChris Mason } 1306925baeddSChris Mason 1307d352ac68SChris Mason /* 1308b4ce94deSChris Mason * returns -EAGAIN if it had to drop the path, or zero if everything was in 1309b4ce94deSChris Mason * cache 1310b4ce94deSChris Mason */ 1311b4ce94deSChris Mason static noinline int reada_for_balance(struct btrfs_root *root, 1312b4ce94deSChris Mason struct btrfs_path *path, int level) 1313b4ce94deSChris Mason { 1314b4ce94deSChris Mason int slot; 1315b4ce94deSChris Mason int nritems; 1316b4ce94deSChris Mason struct extent_buffer *parent; 1317b4ce94deSChris Mason struct extent_buffer *eb; 1318b4ce94deSChris Mason u64 gen; 1319b4ce94deSChris Mason u64 block1 = 0; 1320b4ce94deSChris Mason u64 block2 = 0; 1321b4ce94deSChris Mason int ret = 0; 1322b4ce94deSChris Mason int blocksize; 1323b4ce94deSChris Mason 1324b4ce94deSChris Mason parent = path->nodes[level - 1]; 1325b4ce94deSChris Mason if (!parent) 1326b4ce94deSChris Mason return 0; 1327b4ce94deSChris Mason 1328b4ce94deSChris Mason nritems = btrfs_header_nritems(parent); 1329b4ce94deSChris Mason slot = path->slots[level]; 1330b4ce94deSChris Mason blocksize = btrfs_level_size(root, level); 1331b4ce94deSChris Mason 1332b4ce94deSChris Mason if (slot > 0) { 1333b4ce94deSChris Mason block1 = btrfs_node_blockptr(parent, slot - 1); 1334b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot - 1); 1335b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block1, blocksize); 1336b4ce94deSChris Mason if (eb && btrfs_buffer_uptodate(eb, gen)) 1337b4ce94deSChris Mason block1 = 0; 1338b4ce94deSChris Mason free_extent_buffer(eb); 1339b4ce94deSChris Mason } 1340b4ce94deSChris Mason if (slot < nritems) { 1341b4ce94deSChris Mason block2 = btrfs_node_blockptr(parent, slot + 1); 1342b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot + 1); 1343b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block2, blocksize); 1344b4ce94deSChris Mason if (eb && btrfs_buffer_uptodate(eb, gen)) 1345b4ce94deSChris Mason block2 = 0; 1346b4ce94deSChris Mason free_extent_buffer(eb); 1347b4ce94deSChris Mason } 1348b4ce94deSChris Mason if (block1 || block2) { 1349b4ce94deSChris Mason ret = -EAGAIN; 1350b4ce94deSChris Mason btrfs_release_path(root, path); 1351b4ce94deSChris Mason if (block1) 1352b4ce94deSChris Mason readahead_tree_block(root, block1, blocksize, 0); 1353b4ce94deSChris Mason if (block2) 1354b4ce94deSChris Mason readahead_tree_block(root, block2, blocksize, 0); 1355b4ce94deSChris Mason 1356b4ce94deSChris Mason if (block1) { 1357b4ce94deSChris Mason eb = read_tree_block(root, block1, blocksize, 0); 1358b4ce94deSChris Mason free_extent_buffer(eb); 1359b4ce94deSChris Mason } 1360b4ce94deSChris Mason if (block1) { 1361b4ce94deSChris Mason eb = read_tree_block(root, block2, blocksize, 0); 1362b4ce94deSChris Mason free_extent_buffer(eb); 1363b4ce94deSChris Mason } 1364b4ce94deSChris Mason } 1365b4ce94deSChris Mason return ret; 1366b4ce94deSChris Mason } 1367b4ce94deSChris Mason 1368b4ce94deSChris Mason 1369b4ce94deSChris Mason /* 1370d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1371d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1372d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1373d397712bSChris Mason * tree. 1374d352ac68SChris Mason * 1375d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1376d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1377d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1378d352ac68SChris Mason * 1379d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1380d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1381d352ac68SChris Mason */ 1382e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1383e02119d5SChris Mason int lowest_unlock) 1384925baeddSChris Mason { 1385925baeddSChris Mason int i; 1386925baeddSChris Mason int skip_level = level; 1387051e1b9fSChris Mason int no_skips = 0; 1388925baeddSChris Mason struct extent_buffer *t; 1389925baeddSChris Mason 1390925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1391925baeddSChris Mason if (!path->nodes[i]) 1392925baeddSChris Mason break; 1393925baeddSChris Mason if (!path->locks[i]) 1394925baeddSChris Mason break; 1395051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1396925baeddSChris Mason skip_level = i + 1; 1397925baeddSChris Mason continue; 1398925baeddSChris Mason } 1399051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1400925baeddSChris Mason u32 nritems; 1401925baeddSChris Mason t = path->nodes[i]; 1402925baeddSChris Mason nritems = btrfs_header_nritems(t); 1403051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1404925baeddSChris Mason skip_level = i + 1; 1405925baeddSChris Mason continue; 1406925baeddSChris Mason } 1407925baeddSChris Mason } 1408051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1409051e1b9fSChris Mason no_skips = 1; 1410051e1b9fSChris Mason 1411925baeddSChris Mason t = path->nodes[i]; 1412925baeddSChris Mason if (i >= lowest_unlock && i > skip_level && path->locks[i]) { 1413925baeddSChris Mason btrfs_tree_unlock(t); 1414925baeddSChris Mason path->locks[i] = 0; 1415925baeddSChris Mason } 1416925baeddSChris Mason } 1417925baeddSChris Mason } 1418925baeddSChris Mason 14193c69faecSChris Mason /* 1420b4ce94deSChris Mason * This releases any locks held in the path starting at level and 1421b4ce94deSChris Mason * going all the way up to the root. 1422b4ce94deSChris Mason * 1423b4ce94deSChris Mason * btrfs_search_slot will keep the lock held on higher nodes in a few 1424b4ce94deSChris Mason * corner cases, such as COW of the block at slot zero in the node. This 1425b4ce94deSChris Mason * ignores those rules, and it should only be called when there are no 1426b4ce94deSChris Mason * more updates to be done higher up in the tree. 1427b4ce94deSChris Mason */ 1428b4ce94deSChris Mason noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level) 1429b4ce94deSChris Mason { 1430b4ce94deSChris Mason int i; 1431b4ce94deSChris Mason 1432b4ce94deSChris Mason if (path->keep_locks || path->lowest_level) 1433b4ce94deSChris Mason return; 1434b4ce94deSChris Mason 1435b4ce94deSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1436b4ce94deSChris Mason if (!path->nodes[i]) 143712f4daccSChris Mason continue; 1438b4ce94deSChris Mason if (!path->locks[i]) 143912f4daccSChris Mason continue; 1440b4ce94deSChris Mason btrfs_tree_unlock(path->nodes[i]); 1441b4ce94deSChris Mason path->locks[i] = 0; 1442b4ce94deSChris Mason } 1443b4ce94deSChris Mason } 1444b4ce94deSChris Mason 1445b4ce94deSChris Mason /* 144674123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 144774123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 144874123bd7SChris Mason * level of the path (level 0) 144974123bd7SChris Mason * 145074123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 1451aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 1452aa5d6bedSChris Mason * search a negative error number is returned. 145397571fd0SChris Mason * 145497571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 145597571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 145697571fd0SChris Mason * possible) 145774123bd7SChris Mason */ 1458e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 1459e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 1460e089f05cSChris Mason ins_len, int cow) 1461be0e5c09SChris Mason { 14625f39d397SChris Mason struct extent_buffer *b; 1463051e1b9fSChris Mason struct extent_buffer *tmp; 1464be0e5c09SChris Mason int slot; 1465be0e5c09SChris Mason int ret; 1466be0e5c09SChris Mason int level; 14673c69faecSChris Mason int should_reada = p->reada; 1468925baeddSChris Mason int lowest_unlock = 1; 1469594a24ebSChris Mason int blocksize; 14709f3a7427SChris Mason u8 lowest_level = 0; 1471594a24ebSChris Mason u64 blocknr; 1472594a24ebSChris Mason u64 gen; 14739f3a7427SChris Mason 14746702ed49SChris Mason lowest_level = p->lowest_level; 1475323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 147622b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 147725179201SJosef Bacik 1478925baeddSChris Mason if (ins_len < 0) 1479925baeddSChris Mason lowest_unlock = 2; 148065b51a00SChris Mason 1481bb803951SChris Mason again: 14825cd57b2cSChris Mason if (p->skip_locking) 14835cd57b2cSChris Mason b = btrfs_root_node(root); 14845cd57b2cSChris Mason else 1485925baeddSChris Mason b = btrfs_lock_root_node(root); 1486925baeddSChris Mason 1487eb60ceacSChris Mason while (b) { 14885f39d397SChris Mason level = btrfs_header_level(b); 148965b51a00SChris Mason 149065b51a00SChris Mason /* 149165b51a00SChris Mason * setup the path here so we can release it under lock 149265b51a00SChris Mason * contention with the cow code 149365b51a00SChris Mason */ 149465b51a00SChris Mason p->nodes[level] = b; 149565b51a00SChris Mason if (!p->skip_locking) 149665b51a00SChris Mason p->locks[level] = 1; 149765b51a00SChris Mason 149802217ed2SChris Mason if (cow) { 149902217ed2SChris Mason int wret; 150065b51a00SChris Mason 150165b51a00SChris Mason /* is a cow on this block not required */ 150265b51a00SChris Mason if (btrfs_header_generation(b) == trans->transid && 15035b21f2edSZheng Yan btrfs_header_owner(b) == root->root_key.objectid && 150465b51a00SChris Mason !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) { 150565b51a00SChris Mason goto cow_done; 150665b51a00SChris Mason } 1507b4ce94deSChris Mason btrfs_set_path_blocking(p); 1508b4ce94deSChris Mason 1509e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 1510e20d96d6SChris Mason p->nodes[level + 1], 15119fa8cfe7SChris Mason p->slots[level + 1], &b); 151254aa1f4dSChris Mason if (wret) { 15135f39d397SChris Mason free_extent_buffer(b); 151465b51a00SChris Mason ret = wret; 151565b51a00SChris Mason goto done; 151654aa1f4dSChris Mason } 151702217ed2SChris Mason } 151865b51a00SChris Mason cow_done: 151902217ed2SChris Mason BUG_ON(!cow && ins_len); 15205f39d397SChris Mason if (level != btrfs_header_level(b)) 15212c90e5d6SChris Mason WARN_ON(1); 15225f39d397SChris Mason level = btrfs_header_level(b); 152365b51a00SChris Mason 1524eb60ceacSChris Mason p->nodes[level] = b; 15255cd57b2cSChris Mason if (!p->skip_locking) 1526925baeddSChris Mason p->locks[level] = 1; 152765b51a00SChris Mason 15284008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1529b4ce94deSChris Mason 1530b4ce94deSChris Mason /* 1531b4ce94deSChris Mason * we have a lock on b and as long as we aren't changing 1532b4ce94deSChris Mason * the tree, there is no way to for the items in b to change. 1533b4ce94deSChris Mason * It is safe to drop the lock on our parent before we 1534b4ce94deSChris Mason * go through the expensive btree search on b. 1535b4ce94deSChris Mason * 1536b4ce94deSChris Mason * If cow is true, then we might be changing slot zero, 1537b4ce94deSChris Mason * which may require changing the parent. So, we can't 1538b4ce94deSChris Mason * drop the lock until after we know which slot we're 1539b4ce94deSChris Mason * operating on. 1540b4ce94deSChris Mason */ 1541b4ce94deSChris Mason if (!cow) 1542b4ce94deSChris Mason btrfs_unlock_up_safe(p, level + 1); 1543b4ce94deSChris Mason 1544123abc88SChris Mason ret = check_block(root, p, level); 154565b51a00SChris Mason if (ret) { 154665b51a00SChris Mason ret = -1; 154765b51a00SChris Mason goto done; 154865b51a00SChris Mason } 1549925baeddSChris Mason 15505f39d397SChris Mason ret = bin_search(b, key, level, &slot); 1551b4ce94deSChris Mason 15525f39d397SChris Mason if (level != 0) { 1553be0e5c09SChris Mason if (ret && slot > 0) 1554be0e5c09SChris Mason slot -= 1; 1555be0e5c09SChris Mason p->slots[level] = slot; 1556459931ecSChris Mason if ((p->search_for_split || ins_len > 0) && 1557459931ecSChris Mason btrfs_header_nritems(b) >= 15581514794eSChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { 1559b4ce94deSChris Mason int sret; 1560b4ce94deSChris Mason 1561b4ce94deSChris Mason sret = reada_for_balance(root, p, level); 1562b4ce94deSChris Mason if (sret) 1563b4ce94deSChris Mason goto again; 1564b4ce94deSChris Mason 1565b4ce94deSChris Mason btrfs_set_path_blocking(p); 1566b4ce94deSChris Mason sret = split_node(trans, root, p, level); 15674008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1568b4ce94deSChris Mason 15695c680ed6SChris Mason BUG_ON(sret > 0); 157065b51a00SChris Mason if (sret) { 157165b51a00SChris Mason ret = sret; 157265b51a00SChris Mason goto done; 157365b51a00SChris Mason } 15745c680ed6SChris Mason b = p->nodes[level]; 15755c680ed6SChris Mason slot = p->slots[level]; 15767b78c170SChris Mason } else if (ins_len < 0 && 15777b78c170SChris Mason btrfs_header_nritems(b) < 15787b78c170SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) { 1579b4ce94deSChris Mason int sret; 1580b4ce94deSChris Mason 1581b4ce94deSChris Mason sret = reada_for_balance(root, p, level); 1582b4ce94deSChris Mason if (sret) 1583b4ce94deSChris Mason goto again; 1584b4ce94deSChris Mason 1585b4ce94deSChris Mason btrfs_set_path_blocking(p); 1586b4ce94deSChris Mason sret = balance_level(trans, root, p, level); 15874008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1588b4ce94deSChris Mason 158965b51a00SChris Mason if (sret) { 159065b51a00SChris Mason ret = sret; 159165b51a00SChris Mason goto done; 159265b51a00SChris Mason } 1593bb803951SChris Mason b = p->nodes[level]; 1594f510cfecSChris Mason if (!b) { 1595f510cfecSChris Mason btrfs_release_path(NULL, p); 1596bb803951SChris Mason goto again; 1597f510cfecSChris Mason } 1598bb803951SChris Mason slot = p->slots[level]; 15995f39d397SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 16005c680ed6SChris Mason } 1601f9efa9c7SChris Mason unlock_up(p, level, lowest_unlock); 1602f9efa9c7SChris Mason 16039f3a7427SChris Mason /* this is only true while dropping a snapshot */ 1604925baeddSChris Mason if (level == lowest_level) { 16055b21f2edSZheng Yan ret = 0; 16065b21f2edSZheng Yan goto done; 1607925baeddSChris Mason } 1608ca7a79adSChris Mason 1609594a24ebSChris Mason blocknr = btrfs_node_blockptr(b, slot); 1610594a24ebSChris Mason gen = btrfs_node_ptr_generation(b, slot); 1611594a24ebSChris Mason blocksize = btrfs_level_size(root, level - 1); 1612594a24ebSChris Mason 1613594a24ebSChris Mason tmp = btrfs_find_tree_block(root, blocknr, blocksize); 1614594a24ebSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 1615051e1b9fSChris Mason b = tmp; 1616051e1b9fSChris Mason } else { 1617051e1b9fSChris Mason /* 1618051e1b9fSChris Mason * reduce lock contention at high levels 1619051e1b9fSChris Mason * of the btree by dropping locks before 1620051e1b9fSChris Mason * we read. 1621051e1b9fSChris Mason */ 1622b4ce94deSChris Mason if (level > 0) { 1623051e1b9fSChris Mason btrfs_release_path(NULL, p); 1624051e1b9fSChris Mason if (tmp) 1625051e1b9fSChris Mason free_extent_buffer(tmp); 1626f9efa9c7SChris Mason if (should_reada) 1627f9efa9c7SChris Mason reada_for_search(root, p, 1628f9efa9c7SChris Mason level, slot, 1629f9efa9c7SChris Mason key->objectid); 1630f9efa9c7SChris Mason 1631594a24ebSChris Mason tmp = read_tree_block(root, blocknr, 1632594a24ebSChris Mason blocksize, gen); 1633594a24ebSChris Mason if (tmp) 1634594a24ebSChris Mason free_extent_buffer(tmp); 1635051e1b9fSChris Mason goto again; 1636051e1b9fSChris Mason } else { 1637b4ce94deSChris Mason btrfs_set_path_blocking(p); 1638a74a4b97SChris Mason if (tmp) 1639a74a4b97SChris Mason free_extent_buffer(tmp); 1640f9efa9c7SChris Mason if (should_reada) 1641f9efa9c7SChris Mason reada_for_search(root, p, 1642f9efa9c7SChris Mason level, slot, 1643f9efa9c7SChris Mason key->objectid); 1644ca7a79adSChris Mason b = read_node_slot(root, b, slot); 1645051e1b9fSChris Mason } 1646051e1b9fSChris Mason } 1647b4ce94deSChris Mason if (!p->skip_locking) { 1648b4ce94deSChris Mason int lret; 1649b4ce94deSChris Mason 16504008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1651b4ce94deSChris Mason lret = btrfs_try_spin_lock(b); 1652b4ce94deSChris Mason 1653b4ce94deSChris Mason if (!lret) { 1654b4ce94deSChris Mason btrfs_set_path_blocking(p); 1655925baeddSChris Mason btrfs_tree_lock(b); 16564008c04aSChris Mason btrfs_clear_path_blocking(p, b); 1657b4ce94deSChris Mason } 1658b4ce94deSChris Mason } 1659be0e5c09SChris Mason } else { 1660be0e5c09SChris Mason p->slots[level] = slot; 166187b29b20SYan Zheng if (ins_len > 0 && 166287b29b20SYan Zheng btrfs_leaf_free_space(root, b) < ins_len) { 1663b4ce94deSChris Mason int sret; 1664b4ce94deSChris Mason 1665b4ce94deSChris Mason btrfs_set_path_blocking(p); 1666b4ce94deSChris Mason sret = split_leaf(trans, root, key, 1667cc0c5538SChris Mason p, ins_len, ret == 0); 16684008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1669b4ce94deSChris Mason 16705c680ed6SChris Mason BUG_ON(sret > 0); 167165b51a00SChris Mason if (sret) { 167265b51a00SChris Mason ret = sret; 167365b51a00SChris Mason goto done; 167465b51a00SChris Mason } 16755c680ed6SChris Mason } 1676459931ecSChris Mason if (!p->search_for_split) 1677925baeddSChris Mason unlock_up(p, level, lowest_unlock); 167865b51a00SChris Mason goto done; 167965b51a00SChris Mason } 168065b51a00SChris Mason } 168165b51a00SChris Mason ret = 1; 168265b51a00SChris Mason done: 1683b4ce94deSChris Mason /* 1684b4ce94deSChris Mason * we don't really know what they plan on doing with the path 1685b4ce94deSChris Mason * from here on, so for now just mark it as blocking 1686b4ce94deSChris Mason */ 1687b9473439SChris Mason if (!p->leave_spinning) 1688b4ce94deSChris Mason btrfs_set_path_blocking(p); 1689be0e5c09SChris Mason return ret; 1690be0e5c09SChris Mason } 1691be0e5c09SChris Mason 16921a40e23bSZheng Yan int btrfs_merge_path(struct btrfs_trans_handle *trans, 16931a40e23bSZheng Yan struct btrfs_root *root, 16941a40e23bSZheng Yan struct btrfs_key *node_keys, 16951a40e23bSZheng Yan u64 *nodes, int lowest_level) 16961a40e23bSZheng Yan { 16971a40e23bSZheng Yan struct extent_buffer *eb; 16981a40e23bSZheng Yan struct extent_buffer *parent; 16991a40e23bSZheng Yan struct btrfs_key key; 17001a40e23bSZheng Yan u64 bytenr; 17011a40e23bSZheng Yan u64 generation; 17021a40e23bSZheng Yan u32 blocksize; 17031a40e23bSZheng Yan int level; 17041a40e23bSZheng Yan int slot; 17051a40e23bSZheng Yan int key_match; 17061a40e23bSZheng Yan int ret; 17071a40e23bSZheng Yan 17081a40e23bSZheng Yan eb = btrfs_lock_root_node(root); 17099fa8cfe7SChris Mason ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb); 17101a40e23bSZheng Yan BUG_ON(ret); 17111a40e23bSZheng Yan 1712b4ce94deSChris Mason btrfs_set_lock_blocking(eb); 1713b4ce94deSChris Mason 17141a40e23bSZheng Yan parent = eb; 17151a40e23bSZheng Yan while (1) { 17161a40e23bSZheng Yan level = btrfs_header_level(parent); 17171a40e23bSZheng Yan if (level == 0 || level <= lowest_level) 17181a40e23bSZheng Yan break; 17191a40e23bSZheng Yan 17201a40e23bSZheng Yan ret = bin_search(parent, &node_keys[lowest_level], level, 17211a40e23bSZheng Yan &slot); 17221a40e23bSZheng Yan if (ret && slot > 0) 17231a40e23bSZheng Yan slot--; 17241a40e23bSZheng Yan 17251a40e23bSZheng Yan bytenr = btrfs_node_blockptr(parent, slot); 17261a40e23bSZheng Yan if (nodes[level - 1] == bytenr) 17271a40e23bSZheng Yan break; 17281a40e23bSZheng Yan 17291a40e23bSZheng Yan blocksize = btrfs_level_size(root, level - 1); 17301a40e23bSZheng Yan generation = btrfs_node_ptr_generation(parent, slot); 17311a40e23bSZheng Yan btrfs_node_key_to_cpu(eb, &key, slot); 17321a40e23bSZheng Yan key_match = !memcmp(&key, &node_keys[level - 1], sizeof(key)); 17331a40e23bSZheng Yan 1734f82d02d9SYan Zheng if (generation == trans->transid) { 17351a40e23bSZheng Yan eb = read_tree_block(root, bytenr, blocksize, 17361a40e23bSZheng Yan generation); 17371a40e23bSZheng Yan btrfs_tree_lock(eb); 1738b4ce94deSChris Mason btrfs_set_lock_blocking(eb); 1739f82d02d9SYan Zheng } 1740f82d02d9SYan Zheng 1741f82d02d9SYan Zheng /* 1742f82d02d9SYan Zheng * if node keys match and node pointer hasn't been modified 1743f82d02d9SYan Zheng * in the running transaction, we can merge the path. for 1744f82d02d9SYan Zheng * blocks owened by reloc trees, the node pointer check is 1745f82d02d9SYan Zheng * skipped, this is because these blocks are fully controlled 1746f82d02d9SYan Zheng * by the space balance code, no one else can modify them. 1747f82d02d9SYan Zheng */ 1748f82d02d9SYan Zheng if (!nodes[level - 1] || !key_match || 1749f82d02d9SYan Zheng (generation == trans->transid && 1750f82d02d9SYan Zheng btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID)) { 1751f82d02d9SYan Zheng if (level == 1 || level == lowest_level + 1) { 1752f82d02d9SYan Zheng if (generation == trans->transid) { 1753f82d02d9SYan Zheng btrfs_tree_unlock(eb); 1754f82d02d9SYan Zheng free_extent_buffer(eb); 1755f82d02d9SYan Zheng } 1756f82d02d9SYan Zheng break; 1757f82d02d9SYan Zheng } 1758f82d02d9SYan Zheng 1759f82d02d9SYan Zheng if (generation != trans->transid) { 1760f82d02d9SYan Zheng eb = read_tree_block(root, bytenr, blocksize, 1761f82d02d9SYan Zheng generation); 1762f82d02d9SYan Zheng btrfs_tree_lock(eb); 1763b4ce94deSChris Mason btrfs_set_lock_blocking(eb); 1764f82d02d9SYan Zheng } 17651a40e23bSZheng Yan 17661a40e23bSZheng Yan ret = btrfs_cow_block(trans, root, eb, parent, slot, 17679fa8cfe7SChris Mason &eb); 17681a40e23bSZheng Yan BUG_ON(ret); 17691a40e23bSZheng Yan 1770f82d02d9SYan Zheng if (root->root_key.objectid == 1771f82d02d9SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 1772f82d02d9SYan Zheng if (!nodes[level - 1]) { 1773f82d02d9SYan Zheng nodes[level - 1] = eb->start; 1774f82d02d9SYan Zheng memcpy(&node_keys[level - 1], &key, 1775f82d02d9SYan Zheng sizeof(node_keys[0])); 1776f82d02d9SYan Zheng } else { 1777f82d02d9SYan Zheng WARN_ON(1); 1778f82d02d9SYan Zheng } 1779f82d02d9SYan Zheng } 1780f82d02d9SYan Zheng 17811a40e23bSZheng Yan btrfs_tree_unlock(parent); 17821a40e23bSZheng Yan free_extent_buffer(parent); 17831a40e23bSZheng Yan parent = eb; 17841a40e23bSZheng Yan continue; 17851a40e23bSZheng Yan } 17861a40e23bSZheng Yan 17871a40e23bSZheng Yan btrfs_set_node_blockptr(parent, slot, nodes[level - 1]); 17881a40e23bSZheng Yan btrfs_set_node_ptr_generation(parent, slot, trans->transid); 17891a40e23bSZheng Yan btrfs_mark_buffer_dirty(parent); 17901a40e23bSZheng Yan 17911a40e23bSZheng Yan ret = btrfs_inc_extent_ref(trans, root, 17921a40e23bSZheng Yan nodes[level - 1], 17931a40e23bSZheng Yan blocksize, parent->start, 17941a40e23bSZheng Yan btrfs_header_owner(parent), 17951a40e23bSZheng Yan btrfs_header_generation(parent), 17963bb1a1bcSYan Zheng level - 1); 17971a40e23bSZheng Yan BUG_ON(ret); 1798f82d02d9SYan Zheng 1799f82d02d9SYan Zheng /* 1800f82d02d9SYan Zheng * If the block was created in the running transaction, 1801f82d02d9SYan Zheng * it's possible this is the last reference to it, so we 1802f82d02d9SYan Zheng * should drop the subtree. 1803f82d02d9SYan Zheng */ 1804f82d02d9SYan Zheng if (generation == trans->transid) { 1805f82d02d9SYan Zheng ret = btrfs_drop_subtree(trans, root, eb, parent); 1806f82d02d9SYan Zheng BUG_ON(ret); 1807f82d02d9SYan Zheng btrfs_tree_unlock(eb); 1808f82d02d9SYan Zheng free_extent_buffer(eb); 1809f82d02d9SYan Zheng } else { 18101a40e23bSZheng Yan ret = btrfs_free_extent(trans, root, bytenr, 18111a40e23bSZheng Yan blocksize, parent->start, 18121a40e23bSZheng Yan btrfs_header_owner(parent), 18131a40e23bSZheng Yan btrfs_header_generation(parent), 18143bb1a1bcSYan Zheng level - 1, 1); 18151a40e23bSZheng Yan BUG_ON(ret); 18161a40e23bSZheng Yan } 18171a40e23bSZheng Yan break; 18181a40e23bSZheng Yan } 18191a40e23bSZheng Yan btrfs_tree_unlock(parent); 18201a40e23bSZheng Yan free_extent_buffer(parent); 18211a40e23bSZheng Yan return 0; 18221a40e23bSZheng Yan } 18231a40e23bSZheng Yan 182474123bd7SChris Mason /* 182574123bd7SChris Mason * adjust the pointers going up the tree, starting at level 182674123bd7SChris Mason * making sure the right key of each node is points to 'key'. 182774123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 182874123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 182974123bd7SChris Mason * higher levels 1830aa5d6bedSChris Mason * 1831aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 1832aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 183374123bd7SChris Mason */ 18345f39d397SChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, 18355f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 18365f39d397SChris Mason struct btrfs_disk_key *key, int level) 1837be0e5c09SChris Mason { 1838be0e5c09SChris Mason int i; 1839aa5d6bedSChris Mason int ret = 0; 18405f39d397SChris Mason struct extent_buffer *t; 18415f39d397SChris Mason 1842234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1843be0e5c09SChris Mason int tslot = path->slots[i]; 1844eb60ceacSChris Mason if (!path->nodes[i]) 1845be0e5c09SChris Mason break; 18465f39d397SChris Mason t = path->nodes[i]; 18475f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 1848d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 1849be0e5c09SChris Mason if (tslot != 0) 1850be0e5c09SChris Mason break; 1851be0e5c09SChris Mason } 1852aa5d6bedSChris Mason return ret; 1853be0e5c09SChris Mason } 1854be0e5c09SChris Mason 185574123bd7SChris Mason /* 185631840ae1SZheng Yan * update item key. 185731840ae1SZheng Yan * 185831840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 185931840ae1SZheng Yan * that the new key won't break the order 186031840ae1SZheng Yan */ 186131840ae1SZheng Yan int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, 186231840ae1SZheng Yan struct btrfs_root *root, struct btrfs_path *path, 186331840ae1SZheng Yan struct btrfs_key *new_key) 186431840ae1SZheng Yan { 186531840ae1SZheng Yan struct btrfs_disk_key disk_key; 186631840ae1SZheng Yan struct extent_buffer *eb; 186731840ae1SZheng Yan int slot; 186831840ae1SZheng Yan 186931840ae1SZheng Yan eb = path->nodes[0]; 187031840ae1SZheng Yan slot = path->slots[0]; 187131840ae1SZheng Yan if (slot > 0) { 187231840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 187331840ae1SZheng Yan if (comp_keys(&disk_key, new_key) >= 0) 187431840ae1SZheng Yan return -1; 187531840ae1SZheng Yan } 187631840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 187731840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 187831840ae1SZheng Yan if (comp_keys(&disk_key, new_key) <= 0) 187931840ae1SZheng Yan return -1; 188031840ae1SZheng Yan } 188131840ae1SZheng Yan 188231840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 188331840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 188431840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 188531840ae1SZheng Yan if (slot == 0) 188631840ae1SZheng Yan fixup_low_keys(trans, root, path, &disk_key, 1); 188731840ae1SZheng Yan return 0; 188831840ae1SZheng Yan } 188931840ae1SZheng Yan 189031840ae1SZheng Yan /* 189174123bd7SChris Mason * try to push data from one node into the next node left in the 189279f95c82SChris Mason * tree. 1893aa5d6bedSChris Mason * 1894aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1895aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 189674123bd7SChris Mason */ 189798ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 189898ed5174SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 1899971a1f66SChris Mason struct extent_buffer *src, int empty) 1900be0e5c09SChris Mason { 1901be0e5c09SChris Mason int push_items = 0; 1902bb803951SChris Mason int src_nritems; 1903bb803951SChris Mason int dst_nritems; 1904aa5d6bedSChris Mason int ret = 0; 1905be0e5c09SChris Mason 19065f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 19075f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1908123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 19097bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 19107bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 191154aa1f4dSChris Mason 1912bce4eae9SChris Mason if (!empty && src_nritems <= 8) 1913971a1f66SChris Mason return 1; 1914971a1f66SChris Mason 1915d397712bSChris Mason if (push_items <= 0) 1916be0e5c09SChris Mason return 1; 1917be0e5c09SChris Mason 1918bce4eae9SChris Mason if (empty) { 1919971a1f66SChris Mason push_items = min(src_nritems, push_items); 1920bce4eae9SChris Mason if (push_items < src_nritems) { 1921bce4eae9SChris Mason /* leave at least 8 pointers in the node if 1922bce4eae9SChris Mason * we aren't going to empty it 1923bce4eae9SChris Mason */ 1924bce4eae9SChris Mason if (src_nritems - push_items < 8) { 1925bce4eae9SChris Mason if (push_items <= 8) 1926bce4eae9SChris Mason return 1; 1927bce4eae9SChris Mason push_items -= 8; 1928bce4eae9SChris Mason } 1929bce4eae9SChris Mason } 1930bce4eae9SChris Mason } else 1931bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 193279f95c82SChris Mason 19335f39d397SChris Mason copy_extent_buffer(dst, src, 19345f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 19355f39d397SChris Mason btrfs_node_key_ptr_offset(0), 1936123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 19375f39d397SChris Mason 1938bb803951SChris Mason if (push_items < src_nritems) { 19395f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 19405f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 1941e2fa7227SChris Mason (src_nritems - push_items) * 1942123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1943bb803951SChris Mason } 19445f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 19455f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 19465f39d397SChris Mason btrfs_mark_buffer_dirty(src); 19475f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 194831840ae1SZheng Yan 194931840ae1SZheng Yan ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items); 195031840ae1SZheng Yan BUG_ON(ret); 195131840ae1SZheng Yan 1952bb803951SChris Mason return ret; 1953be0e5c09SChris Mason } 1954be0e5c09SChris Mason 195597571fd0SChris Mason /* 195679f95c82SChris Mason * try to push data from one node into the next node right in the 195779f95c82SChris Mason * tree. 195879f95c82SChris Mason * 195979f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 196079f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 196179f95c82SChris Mason * 196279f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 196379f95c82SChris Mason */ 19645f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 19655f39d397SChris Mason struct btrfs_root *root, 19665f39d397SChris Mason struct extent_buffer *dst, 19675f39d397SChris Mason struct extent_buffer *src) 196879f95c82SChris Mason { 196979f95c82SChris Mason int push_items = 0; 197079f95c82SChris Mason int max_push; 197179f95c82SChris Mason int src_nritems; 197279f95c82SChris Mason int dst_nritems; 197379f95c82SChris Mason int ret = 0; 197479f95c82SChris Mason 19757bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 19767bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 19777bb86316SChris Mason 19785f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 19795f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1980123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 1981d397712bSChris Mason if (push_items <= 0) 198279f95c82SChris Mason return 1; 1983bce4eae9SChris Mason 1984d397712bSChris Mason if (src_nritems < 4) 1985bce4eae9SChris Mason return 1; 198679f95c82SChris Mason 198779f95c82SChris Mason max_push = src_nritems / 2 + 1; 198879f95c82SChris Mason /* don't try to empty the node */ 1989d397712bSChris Mason if (max_push >= src_nritems) 199079f95c82SChris Mason return 1; 1991252c38f0SYan 199279f95c82SChris Mason if (max_push < push_items) 199379f95c82SChris Mason push_items = max_push; 199479f95c82SChris Mason 19955f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 19965f39d397SChris Mason btrfs_node_key_ptr_offset(0), 19975f39d397SChris Mason (dst_nritems) * 19985f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 1999d6025579SChris Mason 20005f39d397SChris Mason copy_extent_buffer(dst, src, 20015f39d397SChris Mason btrfs_node_key_ptr_offset(0), 20025f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 2003123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 200479f95c82SChris Mason 20055f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 20065f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 200779f95c82SChris Mason 20085f39d397SChris Mason btrfs_mark_buffer_dirty(src); 20095f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 201031840ae1SZheng Yan 201131840ae1SZheng Yan ret = btrfs_update_ref(trans, root, src, dst, 0, push_items); 201231840ae1SZheng Yan BUG_ON(ret); 201331840ae1SZheng Yan 201479f95c82SChris Mason return ret; 201579f95c82SChris Mason } 201679f95c82SChris Mason 201779f95c82SChris Mason /* 201897571fd0SChris Mason * helper function to insert a new root level in the tree. 201997571fd0SChris Mason * A new node is allocated, and a single item is inserted to 202097571fd0SChris Mason * point to the existing root 2021aa5d6bedSChris Mason * 2022aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 202397571fd0SChris Mason */ 2024d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 20255f39d397SChris Mason struct btrfs_root *root, 20265f39d397SChris Mason struct btrfs_path *path, int level) 202774123bd7SChris Mason { 20287bb86316SChris Mason u64 lower_gen; 20295f39d397SChris Mason struct extent_buffer *lower; 20305f39d397SChris Mason struct extent_buffer *c; 2031925baeddSChris Mason struct extent_buffer *old; 20325f39d397SChris Mason struct btrfs_disk_key lower_key; 203331840ae1SZheng Yan int ret; 20345c680ed6SChris Mason 20355c680ed6SChris Mason BUG_ON(path->nodes[level]); 20365c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 20375c680ed6SChris Mason 20387bb86316SChris Mason lower = path->nodes[level-1]; 20397bb86316SChris Mason if (level == 1) 20407bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 20417bb86316SChris Mason else 20427bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 20437bb86316SChris Mason 204431840ae1SZheng Yan c = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 204531840ae1SZheng Yan root->root_key.objectid, trans->transid, 2046ad3d81baSChristoph Hellwig level, root->node->start, 0); 20475f39d397SChris Mason if (IS_ERR(c)) 20485f39d397SChris Mason return PTR_ERR(c); 2049925baeddSChris Mason 20505f39d397SChris Mason memset_extent_buffer(c, 0, 0, root->nodesize); 20515f39d397SChris Mason btrfs_set_header_nritems(c, 1); 20525f39d397SChris Mason btrfs_set_header_level(c, level); 2053db94535dSChris Mason btrfs_set_header_bytenr(c, c->start); 20545f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 20555f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 2056d5719762SChris Mason 20575f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 20585f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 20595f39d397SChris Mason BTRFS_FSID_SIZE); 2060e17cade2SChris Mason 2061e17cade2SChris Mason write_extent_buffer(c, root->fs_info->chunk_tree_uuid, 2062e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(c), 2063e17cade2SChris Mason BTRFS_UUID_SIZE); 2064e17cade2SChris Mason 20655f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 2066db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 20677bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 206831840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 20697bb86316SChris Mason 20707bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 20715f39d397SChris Mason 20725f39d397SChris Mason btrfs_mark_buffer_dirty(c); 2073d5719762SChris Mason 2074925baeddSChris Mason spin_lock(&root->node_lock); 2075925baeddSChris Mason old = root->node; 20765f39d397SChris Mason root->node = c; 2077925baeddSChris Mason spin_unlock(&root->node_lock); 2078925baeddSChris Mason 207931840ae1SZheng Yan ret = btrfs_update_extent_ref(trans, root, lower->start, 208056bec294SChris Mason lower->len, lower->start, c->start, 208131840ae1SZheng Yan root->root_key.objectid, 20823bb1a1bcSYan Zheng trans->transid, level - 1); 208331840ae1SZheng Yan BUG_ON(ret); 208431840ae1SZheng Yan 2085925baeddSChris Mason /* the super has an extra ref to root->node */ 2086925baeddSChris Mason free_extent_buffer(old); 2087925baeddSChris Mason 20880b86a832SChris Mason add_root_to_dirty_list(root); 20895f39d397SChris Mason extent_buffer_get(c); 20905f39d397SChris Mason path->nodes[level] = c; 2091925baeddSChris Mason path->locks[level] = 1; 209274123bd7SChris Mason path->slots[level] = 0; 209374123bd7SChris Mason return 0; 209474123bd7SChris Mason } 20955c680ed6SChris Mason 20965c680ed6SChris Mason /* 20975c680ed6SChris Mason * worker function to insert a single pointer in a node. 20985c680ed6SChris Mason * the node should have enough room for the pointer already 209997571fd0SChris Mason * 21005c680ed6SChris Mason * slot and level indicate where you want the key to go, and 21015c680ed6SChris Mason * blocknr is the block the key points to. 2102aa5d6bedSChris Mason * 2103aa5d6bedSChris Mason * returns zero on success and < 0 on any error 21045c680ed6SChris Mason */ 2105e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 2106e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 2107db94535dSChris Mason *key, u64 bytenr, int slot, int level) 21085c680ed6SChris Mason { 21095f39d397SChris Mason struct extent_buffer *lower; 21105c680ed6SChris Mason int nritems; 21115c680ed6SChris Mason 21125c680ed6SChris Mason BUG_ON(!path->nodes[level]); 21135f39d397SChris Mason lower = path->nodes[level]; 21145f39d397SChris Mason nritems = btrfs_header_nritems(lower); 211574123bd7SChris Mason if (slot > nritems) 211674123bd7SChris Mason BUG(); 2117123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 211874123bd7SChris Mason BUG(); 211974123bd7SChris Mason if (slot != nritems) { 21205f39d397SChris Mason memmove_extent_buffer(lower, 21215f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 21225f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 2123123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 212474123bd7SChris Mason } 21255f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 2126db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 212774493f7aSChris Mason WARN_ON(trans->transid == 0); 212874493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 21295f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 21305f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 213174123bd7SChris Mason return 0; 213274123bd7SChris Mason } 213374123bd7SChris Mason 213497571fd0SChris Mason /* 213597571fd0SChris Mason * split the node at the specified level in path in two. 213697571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 213797571fd0SChris Mason * 213897571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 213997571fd0SChris Mason * left and right, if either one works, it returns right away. 2140aa5d6bedSChris Mason * 2141aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 214297571fd0SChris Mason */ 2143e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 2144e02119d5SChris Mason struct btrfs_root *root, 2145e02119d5SChris Mason struct btrfs_path *path, int level) 2146be0e5c09SChris Mason { 21475f39d397SChris Mason struct extent_buffer *c; 21485f39d397SChris Mason struct extent_buffer *split; 21495f39d397SChris Mason struct btrfs_disk_key disk_key; 2150be0e5c09SChris Mason int mid; 21515c680ed6SChris Mason int ret; 2152aa5d6bedSChris Mason int wret; 21537518a238SChris Mason u32 c_nritems; 2154be0e5c09SChris Mason 21555f39d397SChris Mason c = path->nodes[level]; 21567bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 21575f39d397SChris Mason if (c == root->node) { 21585c680ed6SChris Mason /* trying to split the root, lets make a new one */ 2159e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 21605c680ed6SChris Mason if (ret) 21615c680ed6SChris Mason return ret; 2162e66f709bSChris Mason } else { 2163e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 21645f39d397SChris Mason c = path->nodes[level]; 21655f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 2166c448acf0SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) 2167e66f709bSChris Mason return 0; 216854aa1f4dSChris Mason if (ret < 0) 216954aa1f4dSChris Mason return ret; 21705c680ed6SChris Mason } 2171e66f709bSChris Mason 21725f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 21737bb86316SChris Mason 2174925baeddSChris Mason split = btrfs_alloc_free_block(trans, root, root->nodesize, 217531840ae1SZheng Yan path->nodes[level + 1]->start, 21767bb86316SChris Mason root->root_key.objectid, 217731840ae1SZheng Yan trans->transid, level, c->start, 0); 21785f39d397SChris Mason if (IS_ERR(split)) 21795f39d397SChris Mason return PTR_ERR(split); 218054aa1f4dSChris Mason 21815f39d397SChris Mason btrfs_set_header_flags(split, btrfs_header_flags(c)); 21825f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 2183db94535dSChris Mason btrfs_set_header_bytenr(split, split->start); 21845f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 21855f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 218663b10fc4SChris Mason btrfs_set_header_flags(split, 0); 21875f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 21885f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 21895f39d397SChris Mason BTRFS_FSID_SIZE); 2190e17cade2SChris Mason write_extent_buffer(split, root->fs_info->chunk_tree_uuid, 2191e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(split), 2192e17cade2SChris Mason BTRFS_UUID_SIZE); 21935f39d397SChris Mason 21947518a238SChris Mason mid = (c_nritems + 1) / 2; 21955f39d397SChris Mason 21965f39d397SChris Mason copy_extent_buffer(split, c, 21975f39d397SChris Mason btrfs_node_key_ptr_offset(0), 21985f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2199123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 22005f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 22015f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2202aa5d6bedSChris Mason ret = 0; 2203aa5d6bedSChris Mason 22045f39d397SChris Mason btrfs_mark_buffer_dirty(c); 22055f39d397SChris Mason btrfs_mark_buffer_dirty(split); 22065f39d397SChris Mason 22075f39d397SChris Mason btrfs_node_key(split, &disk_key, 0); 2208db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, split->start, 22095f39d397SChris Mason path->slots[level + 1] + 1, 2210123abc88SChris Mason level + 1); 2211aa5d6bedSChris Mason if (wret) 2212aa5d6bedSChris Mason ret = wret; 2213aa5d6bedSChris Mason 221431840ae1SZheng Yan ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid); 221531840ae1SZheng Yan BUG_ON(ret); 221631840ae1SZheng Yan 22175de08d7dSChris Mason if (path->slots[level] >= mid) { 22185c680ed6SChris Mason path->slots[level] -= mid; 2219925baeddSChris Mason btrfs_tree_unlock(c); 22205f39d397SChris Mason free_extent_buffer(c); 22215f39d397SChris Mason path->nodes[level] = split; 22225c680ed6SChris Mason path->slots[level + 1] += 1; 2223eb60ceacSChris Mason } else { 2224925baeddSChris Mason btrfs_tree_unlock(split); 22255f39d397SChris Mason free_extent_buffer(split); 2226be0e5c09SChris Mason } 2227aa5d6bedSChris Mason return ret; 2228be0e5c09SChris Mason } 2229be0e5c09SChris Mason 223074123bd7SChris Mason /* 223174123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 223274123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 223374123bd7SChris Mason * space used both by the item structs and the item data 223474123bd7SChris Mason */ 22355f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2236be0e5c09SChris Mason { 2237be0e5c09SChris Mason int data_len; 22385f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2239d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2240be0e5c09SChris Mason 2241be0e5c09SChris Mason if (!nr) 2242be0e5c09SChris Mason return 0; 22435f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 22445f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 22450783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2246d4dbff95SChris Mason WARN_ON(data_len < 0); 2247be0e5c09SChris Mason return data_len; 2248be0e5c09SChris Mason } 2249be0e5c09SChris Mason 225074123bd7SChris Mason /* 2251d4dbff95SChris Mason * The space between the end of the leaf items and 2252d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2253d4dbff95SChris Mason * the leaf has left for both items and data 2254d4dbff95SChris Mason */ 2255d397712bSChris Mason noinline int btrfs_leaf_free_space(struct btrfs_root *root, 2256e02119d5SChris Mason struct extent_buffer *leaf) 2257d4dbff95SChris Mason { 22585f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 22595f39d397SChris Mason int ret; 22605f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 22615f39d397SChris Mason if (ret < 0) { 2262d397712bSChris Mason printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, " 2263d397712bSChris Mason "used %d nritems %d\n", 2264ae2f5411SJens Axboe ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), 22655f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 22665f39d397SChris Mason } 22675f39d397SChris Mason return ret; 2268d4dbff95SChris Mason } 2269d4dbff95SChris Mason 227044871b1bSChris Mason static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, 227144871b1bSChris Mason struct btrfs_root *root, 227244871b1bSChris Mason struct btrfs_path *path, 227344871b1bSChris Mason int data_size, int empty, 227444871b1bSChris Mason struct extent_buffer *right, 227544871b1bSChris Mason int free_space, u32 left_nritems) 227600ec4c51SChris Mason { 22775f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 227844871b1bSChris Mason struct extent_buffer *upper = path->nodes[1]; 22795f39d397SChris Mason struct btrfs_disk_key disk_key; 228000ec4c51SChris Mason int slot; 228134a38218SChris Mason u32 i; 228200ec4c51SChris Mason int push_space = 0; 228300ec4c51SChris Mason int push_items = 0; 22840783fcfcSChris Mason struct btrfs_item *item; 228534a38218SChris Mason u32 nr; 22867518a238SChris Mason u32 right_nritems; 22875f39d397SChris Mason u32 data_end; 2288db94535dSChris Mason u32 this_item_size; 228954aa1f4dSChris Mason int ret; 229000ec4c51SChris Mason 229134a38218SChris Mason if (empty) 229234a38218SChris Mason nr = 0; 229334a38218SChris Mason else 229434a38218SChris Mason nr = 1; 229534a38218SChris Mason 229631840ae1SZheng Yan if (path->slots[0] >= left_nritems) 229787b29b20SYan Zheng push_space += data_size; 229831840ae1SZheng Yan 229944871b1bSChris Mason slot = path->slots[1]; 230034a38218SChris Mason i = left_nritems - 1; 230134a38218SChris Mason while (i >= nr) { 23025f39d397SChris Mason item = btrfs_item_nr(left, i); 2303db94535dSChris Mason 230431840ae1SZheng Yan if (!empty && push_items > 0) { 230531840ae1SZheng Yan if (path->slots[0] > i) 230631840ae1SZheng Yan break; 230731840ae1SZheng Yan if (path->slots[0] == i) { 230831840ae1SZheng Yan int space = btrfs_leaf_free_space(root, left); 230931840ae1SZheng Yan if (space + push_space * 2 > free_space) 231031840ae1SZheng Yan break; 231131840ae1SZheng Yan } 231231840ae1SZheng Yan } 231331840ae1SZheng Yan 231400ec4c51SChris Mason if (path->slots[0] == i) 231587b29b20SYan Zheng push_space += data_size; 2316db94535dSChris Mason 2317db94535dSChris Mason if (!left->map_token) { 2318db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 2319db94535dSChris Mason sizeof(struct btrfs_item), 2320db94535dSChris Mason &left->map_token, &left->kaddr, 2321db94535dSChris Mason &left->map_start, &left->map_len, 2322db94535dSChris Mason KM_USER1); 2323db94535dSChris Mason } 2324db94535dSChris Mason 2325db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 2326db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 232700ec4c51SChris Mason break; 232831840ae1SZheng Yan 232900ec4c51SChris Mason push_items++; 2330db94535dSChris Mason push_space += this_item_size + sizeof(*item); 233134a38218SChris Mason if (i == 0) 233234a38218SChris Mason break; 233334a38218SChris Mason i--; 2334db94535dSChris Mason } 2335db94535dSChris Mason if (left->map_token) { 2336db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 2337db94535dSChris Mason left->map_token = NULL; 233800ec4c51SChris Mason } 23395f39d397SChris Mason 2340925baeddSChris Mason if (push_items == 0) 2341925baeddSChris Mason goto out_unlock; 23425f39d397SChris Mason 234334a38218SChris Mason if (!empty && push_items == left_nritems) 2344a429e513SChris Mason WARN_ON(1); 23455f39d397SChris Mason 234600ec4c51SChris Mason /* push left to right */ 23475f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 234834a38218SChris Mason 23495f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 2350123abc88SChris Mason push_space -= leaf_data_end(root, left); 23515f39d397SChris Mason 235200ec4c51SChris Mason /* make room in the right data area */ 23535f39d397SChris Mason data_end = leaf_data_end(root, right); 23545f39d397SChris Mason memmove_extent_buffer(right, 23555f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 23565f39d397SChris Mason btrfs_leaf_data(right) + data_end, 23575f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 23585f39d397SChris Mason 235900ec4c51SChris Mason /* copy from the left data area */ 23605f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 2361d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2362d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 2363d6025579SChris Mason push_space); 23645f39d397SChris Mason 23655f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 23665f39d397SChris Mason btrfs_item_nr_offset(0), 23670783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 23685f39d397SChris Mason 236900ec4c51SChris Mason /* copy the items from left to right */ 23705f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 23715f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 23720783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 237300ec4c51SChris Mason 237400ec4c51SChris Mason /* update the item pointers */ 23757518a238SChris Mason right_nritems += push_items; 23765f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 2377123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 23787518a238SChris Mason for (i = 0; i < right_nritems; i++) { 23795f39d397SChris Mason item = btrfs_item_nr(right, i); 2380db94535dSChris Mason if (!right->map_token) { 2381db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2382db94535dSChris Mason sizeof(struct btrfs_item), 2383db94535dSChris Mason &right->map_token, &right->kaddr, 2384db94535dSChris Mason &right->map_start, &right->map_len, 2385db94535dSChris Mason KM_USER1); 2386db94535dSChris Mason } 2387db94535dSChris Mason push_space -= btrfs_item_size(right, item); 2388db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2389db94535dSChris Mason } 2390db94535dSChris Mason 2391db94535dSChris Mason if (right->map_token) { 2392db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2393db94535dSChris Mason right->map_token = NULL; 239400ec4c51SChris Mason } 23957518a238SChris Mason left_nritems -= push_items; 23965f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 239700ec4c51SChris Mason 239834a38218SChris Mason if (left_nritems) 23995f39d397SChris Mason btrfs_mark_buffer_dirty(left); 24005f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2401a429e513SChris Mason 240231840ae1SZheng Yan ret = btrfs_update_ref(trans, root, left, right, 0, push_items); 240331840ae1SZheng Yan BUG_ON(ret); 240431840ae1SZheng Yan 24055f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 24065f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2407d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 240802217ed2SChris Mason 240900ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 24107518a238SChris Mason if (path->slots[0] >= left_nritems) { 24117518a238SChris Mason path->slots[0] -= left_nritems; 2412925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2413925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2414925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 24155f39d397SChris Mason free_extent_buffer(path->nodes[0]); 24165f39d397SChris Mason path->nodes[0] = right; 241700ec4c51SChris Mason path->slots[1] += 1; 241800ec4c51SChris Mason } else { 2419925baeddSChris Mason btrfs_tree_unlock(right); 24205f39d397SChris Mason free_extent_buffer(right); 242100ec4c51SChris Mason } 242200ec4c51SChris Mason return 0; 2423925baeddSChris Mason 2424925baeddSChris Mason out_unlock: 2425925baeddSChris Mason btrfs_tree_unlock(right); 2426925baeddSChris Mason free_extent_buffer(right); 2427925baeddSChris Mason return 1; 242800ec4c51SChris Mason } 2429925baeddSChris Mason 243000ec4c51SChris Mason /* 243144871b1bSChris Mason * push some data in the path leaf to the right, trying to free up at 243274123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 243344871b1bSChris Mason * 243444871b1bSChris Mason * returns 1 if the push failed because the other node didn't have enough 243544871b1bSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 243674123bd7SChris Mason */ 243744871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 243834a38218SChris Mason *root, struct btrfs_path *path, int data_size, 243934a38218SChris Mason int empty) 2440be0e5c09SChris Mason { 244144871b1bSChris Mason struct extent_buffer *left = path->nodes[0]; 244244871b1bSChris Mason struct extent_buffer *right; 244344871b1bSChris Mason struct extent_buffer *upper; 244444871b1bSChris Mason int slot; 244544871b1bSChris Mason int free_space; 244644871b1bSChris Mason u32 left_nritems; 244744871b1bSChris Mason int ret; 244844871b1bSChris Mason 244944871b1bSChris Mason if (!path->nodes[1]) 245044871b1bSChris Mason return 1; 245144871b1bSChris Mason 245244871b1bSChris Mason slot = path->slots[1]; 245344871b1bSChris Mason upper = path->nodes[1]; 245444871b1bSChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 245544871b1bSChris Mason return 1; 245644871b1bSChris Mason 245744871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 245844871b1bSChris Mason 245944871b1bSChris Mason right = read_node_slot(root, upper, slot + 1); 246044871b1bSChris Mason btrfs_tree_lock(right); 246144871b1bSChris Mason btrfs_set_lock_blocking(right); 246244871b1bSChris Mason 246344871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 246444871b1bSChris Mason if (free_space < data_size) 246544871b1bSChris Mason goto out_unlock; 246644871b1bSChris Mason 246744871b1bSChris Mason /* cow and double check */ 246844871b1bSChris Mason ret = btrfs_cow_block(trans, root, right, upper, 246944871b1bSChris Mason slot + 1, &right); 247044871b1bSChris Mason if (ret) 247144871b1bSChris Mason goto out_unlock; 247244871b1bSChris Mason 247344871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 247444871b1bSChris Mason if (free_space < data_size) 247544871b1bSChris Mason goto out_unlock; 247644871b1bSChris Mason 247744871b1bSChris Mason left_nritems = btrfs_header_nritems(left); 247844871b1bSChris Mason if (left_nritems == 0) 247944871b1bSChris Mason goto out_unlock; 248044871b1bSChris Mason 248144871b1bSChris Mason return __push_leaf_right(trans, root, path, data_size, empty, 248244871b1bSChris Mason right, free_space, left_nritems); 248344871b1bSChris Mason out_unlock: 248444871b1bSChris Mason btrfs_tree_unlock(right); 248544871b1bSChris Mason free_extent_buffer(right); 248644871b1bSChris Mason return 1; 248744871b1bSChris Mason } 248844871b1bSChris Mason 248944871b1bSChris Mason /* 249044871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 249144871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 249244871b1bSChris Mason */ 249344871b1bSChris Mason static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, 249444871b1bSChris Mason struct btrfs_root *root, 249544871b1bSChris Mason struct btrfs_path *path, int data_size, 249644871b1bSChris Mason int empty, struct extent_buffer *left, 249744871b1bSChris Mason int free_space, int right_nritems) 249844871b1bSChris Mason { 24995f39d397SChris Mason struct btrfs_disk_key disk_key; 25005f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 2501be0e5c09SChris Mason int slot; 2502be0e5c09SChris Mason int i; 2503be0e5c09SChris Mason int push_space = 0; 2504be0e5c09SChris Mason int push_items = 0; 25050783fcfcSChris Mason struct btrfs_item *item; 25067518a238SChris Mason u32 old_left_nritems; 250734a38218SChris Mason u32 nr; 2508aa5d6bedSChris Mason int ret = 0; 2509aa5d6bedSChris Mason int wret; 2510db94535dSChris Mason u32 this_item_size; 2511db94535dSChris Mason u32 old_left_item_size; 2512be0e5c09SChris Mason 2513be0e5c09SChris Mason slot = path->slots[1]; 251402217ed2SChris Mason 251534a38218SChris Mason if (empty) 251634a38218SChris Mason nr = right_nritems; 251734a38218SChris Mason else 251834a38218SChris Mason nr = right_nritems - 1; 251934a38218SChris Mason 252034a38218SChris Mason for (i = 0; i < nr; i++) { 25215f39d397SChris Mason item = btrfs_item_nr(right, i); 2522db94535dSChris Mason if (!right->map_token) { 2523db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2524db94535dSChris Mason sizeof(struct btrfs_item), 2525db94535dSChris Mason &right->map_token, &right->kaddr, 2526db94535dSChris Mason &right->map_start, &right->map_len, 2527db94535dSChris Mason KM_USER1); 2528db94535dSChris Mason } 2529db94535dSChris Mason 253031840ae1SZheng Yan if (!empty && push_items > 0) { 253131840ae1SZheng Yan if (path->slots[0] < i) 253231840ae1SZheng Yan break; 253331840ae1SZheng Yan if (path->slots[0] == i) { 253431840ae1SZheng Yan int space = btrfs_leaf_free_space(root, right); 253531840ae1SZheng Yan if (space + push_space * 2 > free_space) 253631840ae1SZheng Yan break; 253731840ae1SZheng Yan } 253831840ae1SZheng Yan } 253931840ae1SZheng Yan 2540be0e5c09SChris Mason if (path->slots[0] == i) 254187b29b20SYan Zheng push_space += data_size; 2542db94535dSChris Mason 2543db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 2544db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 2545be0e5c09SChris Mason break; 2546db94535dSChris Mason 2547be0e5c09SChris Mason push_items++; 2548db94535dSChris Mason push_space += this_item_size + sizeof(*item); 2549be0e5c09SChris Mason } 2550db94535dSChris Mason 2551db94535dSChris Mason if (right->map_token) { 2552db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2553db94535dSChris Mason right->map_token = NULL; 2554db94535dSChris Mason } 2555db94535dSChris Mason 2556be0e5c09SChris Mason if (push_items == 0) { 2557925baeddSChris Mason ret = 1; 2558925baeddSChris Mason goto out; 2559be0e5c09SChris Mason } 256034a38218SChris Mason if (!empty && push_items == btrfs_header_nritems(right)) 2561a429e513SChris Mason WARN_ON(1); 25625f39d397SChris Mason 2563be0e5c09SChris Mason /* push data from right to left */ 25645f39d397SChris Mason copy_extent_buffer(left, right, 25655f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 25665f39d397SChris Mason btrfs_item_nr_offset(0), 25675f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 25685f39d397SChris Mason 2569123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 25705f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1); 25715f39d397SChris Mason 25725f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 2573d6025579SChris Mason leaf_data_end(root, left) - push_space, 2574123abc88SChris Mason btrfs_leaf_data(right) + 25755f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 2576be0e5c09SChris Mason push_space); 25775f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 257887b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 2579eb60ceacSChris Mason 2580db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 2581be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 25825f39d397SChris Mason u32 ioff; 2583db94535dSChris Mason 25845f39d397SChris Mason item = btrfs_item_nr(left, i); 2585db94535dSChris Mason if (!left->map_token) { 2586db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 2587db94535dSChris Mason sizeof(struct btrfs_item), 2588db94535dSChris Mason &left->map_token, &left->kaddr, 2589db94535dSChris Mason &left->map_start, &left->map_len, 2590db94535dSChris Mason KM_USER1); 2591db94535dSChris Mason } 2592db94535dSChris Mason 25935f39d397SChris Mason ioff = btrfs_item_offset(left, item); 25945f39d397SChris Mason btrfs_set_item_offset(left, item, 2595db94535dSChris Mason ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size)); 2596be0e5c09SChris Mason } 25975f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 2598db94535dSChris Mason if (left->map_token) { 2599db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 2600db94535dSChris Mason left->map_token = NULL; 2601db94535dSChris Mason } 2602be0e5c09SChris Mason 2603be0e5c09SChris Mason /* fixup right node */ 260434a38218SChris Mason if (push_items > right_nritems) { 2605d397712bSChris Mason printk(KERN_CRIT "push items %d nr %u\n", push_items, 2606d397712bSChris Mason right_nritems); 260734a38218SChris Mason WARN_ON(1); 260834a38218SChris Mason } 260934a38218SChris Mason 261034a38218SChris Mason if (push_items < right_nritems) { 26115f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 2612123abc88SChris Mason leaf_data_end(root, right); 26135f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 2614d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2615d6025579SChris Mason btrfs_leaf_data(right) + 2616123abc88SChris Mason leaf_data_end(root, right), push_space); 26175f39d397SChris Mason 26185f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 26195f39d397SChris Mason btrfs_item_nr_offset(push_items), 26205f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 26210783fcfcSChris Mason sizeof(struct btrfs_item)); 262234a38218SChris Mason } 2623eef1c494SYan right_nritems -= push_items; 2624eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 2625123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 26265f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 26275f39d397SChris Mason item = btrfs_item_nr(right, i); 2628db94535dSChris Mason 2629db94535dSChris Mason if (!right->map_token) { 2630db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2631db94535dSChris Mason sizeof(struct btrfs_item), 2632db94535dSChris Mason &right->map_token, &right->kaddr, 2633db94535dSChris Mason &right->map_start, &right->map_len, 2634db94535dSChris Mason KM_USER1); 2635db94535dSChris Mason } 2636db94535dSChris Mason 2637db94535dSChris Mason push_space = push_space - btrfs_item_size(right, item); 2638db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2639db94535dSChris Mason } 2640db94535dSChris Mason if (right->map_token) { 2641db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2642db94535dSChris Mason right->map_token = NULL; 2643be0e5c09SChris Mason } 2644eb60ceacSChris Mason 26455f39d397SChris Mason btrfs_mark_buffer_dirty(left); 264634a38218SChris Mason if (right_nritems) 26475f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2648098f59c2SChris Mason 264931840ae1SZheng Yan ret = btrfs_update_ref(trans, root, right, left, 265031840ae1SZheng Yan old_left_nritems, push_items); 265131840ae1SZheng Yan BUG_ON(ret); 265231840ae1SZheng Yan 26535f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 26545f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 2655aa5d6bedSChris Mason if (wret) 2656aa5d6bedSChris Mason ret = wret; 2657be0e5c09SChris Mason 2658be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 2659be0e5c09SChris Mason if (path->slots[0] < push_items) { 2660be0e5c09SChris Mason path->slots[0] += old_left_nritems; 2661925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2662925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2663925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 26645f39d397SChris Mason free_extent_buffer(path->nodes[0]); 26655f39d397SChris Mason path->nodes[0] = left; 2666be0e5c09SChris Mason path->slots[1] -= 1; 2667be0e5c09SChris Mason } else { 2668925baeddSChris Mason btrfs_tree_unlock(left); 26695f39d397SChris Mason free_extent_buffer(left); 2670be0e5c09SChris Mason path->slots[0] -= push_items; 2671be0e5c09SChris Mason } 2672eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2673aa5d6bedSChris Mason return ret; 2674925baeddSChris Mason out: 2675925baeddSChris Mason btrfs_tree_unlock(left); 2676925baeddSChris Mason free_extent_buffer(left); 2677925baeddSChris Mason return ret; 2678be0e5c09SChris Mason } 2679be0e5c09SChris Mason 268074123bd7SChris Mason /* 268144871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 268244871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 268344871b1bSChris Mason */ 268444871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 268544871b1bSChris Mason *root, struct btrfs_path *path, int data_size, 268644871b1bSChris Mason int empty) 268744871b1bSChris Mason { 268844871b1bSChris Mason struct extent_buffer *right = path->nodes[0]; 268944871b1bSChris Mason struct extent_buffer *left; 269044871b1bSChris Mason int slot; 269144871b1bSChris Mason int free_space; 269244871b1bSChris Mason u32 right_nritems; 269344871b1bSChris Mason int ret = 0; 269444871b1bSChris Mason 269544871b1bSChris Mason slot = path->slots[1]; 269644871b1bSChris Mason if (slot == 0) 269744871b1bSChris Mason return 1; 269844871b1bSChris Mason if (!path->nodes[1]) 269944871b1bSChris Mason return 1; 270044871b1bSChris Mason 270144871b1bSChris Mason right_nritems = btrfs_header_nritems(right); 270244871b1bSChris Mason if (right_nritems == 0) 270344871b1bSChris Mason return 1; 270444871b1bSChris Mason 270544871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 270644871b1bSChris Mason 270744871b1bSChris Mason left = read_node_slot(root, path->nodes[1], slot - 1); 270844871b1bSChris Mason btrfs_tree_lock(left); 270944871b1bSChris Mason btrfs_set_lock_blocking(left); 271044871b1bSChris Mason 271144871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 271244871b1bSChris Mason if (free_space < data_size) { 271344871b1bSChris Mason ret = 1; 271444871b1bSChris Mason goto out; 271544871b1bSChris Mason } 271644871b1bSChris Mason 271744871b1bSChris Mason /* cow and double check */ 271844871b1bSChris Mason ret = btrfs_cow_block(trans, root, left, 271944871b1bSChris Mason path->nodes[1], slot - 1, &left); 272044871b1bSChris Mason if (ret) { 272144871b1bSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 272244871b1bSChris Mason ret = 1; 272344871b1bSChris Mason goto out; 272444871b1bSChris Mason } 272544871b1bSChris Mason 272644871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 272744871b1bSChris Mason if (free_space < data_size) { 272844871b1bSChris Mason ret = 1; 272944871b1bSChris Mason goto out; 273044871b1bSChris Mason } 273144871b1bSChris Mason 273244871b1bSChris Mason return __push_leaf_left(trans, root, path, data_size, 273344871b1bSChris Mason empty, left, free_space, right_nritems); 273444871b1bSChris Mason out: 273544871b1bSChris Mason btrfs_tree_unlock(left); 273644871b1bSChris Mason free_extent_buffer(left); 273744871b1bSChris Mason return ret; 273844871b1bSChris Mason } 273944871b1bSChris Mason 274044871b1bSChris Mason /* 274174123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 274274123bd7SChris Mason * available for the resulting leaf level of the path. 2743aa5d6bedSChris Mason * 2744aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 274574123bd7SChris Mason */ 274644871b1bSChris Mason static noinline int copy_for_split(struct btrfs_trans_handle *trans, 2747e02119d5SChris Mason struct btrfs_root *root, 274844871b1bSChris Mason struct btrfs_path *path, 274944871b1bSChris Mason struct extent_buffer *l, 275044871b1bSChris Mason struct extent_buffer *right, 275144871b1bSChris Mason int slot, int mid, int nritems) 2752be0e5c09SChris Mason { 2753be0e5c09SChris Mason int data_copy_size; 2754be0e5c09SChris Mason int rt_data_off; 2755be0e5c09SChris Mason int i; 2756d4dbff95SChris Mason int ret = 0; 2757aa5d6bedSChris Mason int wret; 2758d4dbff95SChris Mason struct btrfs_disk_key disk_key; 2759be0e5c09SChris Mason 27605f39d397SChris Mason nritems = nritems - mid; 27615f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 27625f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 27635f39d397SChris Mason 27645f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 27655f39d397SChris Mason btrfs_item_nr_offset(mid), 27665f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 27675f39d397SChris Mason 27685f39d397SChris Mason copy_extent_buffer(right, l, 2769d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 2770123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 2771123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 277274123bd7SChris Mason 27735f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 27745f39d397SChris Mason btrfs_item_end_nr(l, mid); 27755f39d397SChris Mason 27765f39d397SChris Mason for (i = 0; i < nritems; i++) { 27775f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 2778db94535dSChris Mason u32 ioff; 2779db94535dSChris Mason 2780db94535dSChris Mason if (!right->map_token) { 2781db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2782db94535dSChris Mason sizeof(struct btrfs_item), 2783db94535dSChris Mason &right->map_token, &right->kaddr, 2784db94535dSChris Mason &right->map_start, &right->map_len, 2785db94535dSChris Mason KM_USER1); 2786db94535dSChris Mason } 2787db94535dSChris Mason 2788db94535dSChris Mason ioff = btrfs_item_offset(right, item); 27895f39d397SChris Mason btrfs_set_item_offset(right, item, ioff + rt_data_off); 27900783fcfcSChris Mason } 279174123bd7SChris Mason 2792db94535dSChris Mason if (right->map_token) { 2793db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2794db94535dSChris Mason right->map_token = NULL; 2795db94535dSChris Mason } 2796db94535dSChris Mason 27975f39d397SChris Mason btrfs_set_header_nritems(l, mid); 2798aa5d6bedSChris Mason ret = 0; 27995f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 2800db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, right->start, 2801db94535dSChris Mason path->slots[1] + 1, 1); 2802aa5d6bedSChris Mason if (wret) 2803aa5d6bedSChris Mason ret = wret; 28045f39d397SChris Mason 28055f39d397SChris Mason btrfs_mark_buffer_dirty(right); 28065f39d397SChris Mason btrfs_mark_buffer_dirty(l); 2807eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 28085f39d397SChris Mason 280931840ae1SZheng Yan ret = btrfs_update_ref(trans, root, l, right, 0, nritems); 281031840ae1SZheng Yan BUG_ON(ret); 281131840ae1SZheng Yan 2812be0e5c09SChris Mason if (mid <= slot) { 2813925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 28145f39d397SChris Mason free_extent_buffer(path->nodes[0]); 28155f39d397SChris Mason path->nodes[0] = right; 2816be0e5c09SChris Mason path->slots[0] -= mid; 2817be0e5c09SChris Mason path->slots[1] += 1; 2818925baeddSChris Mason } else { 2819925baeddSChris Mason btrfs_tree_unlock(right); 28205f39d397SChris Mason free_extent_buffer(right); 2821925baeddSChris Mason } 28225f39d397SChris Mason 2823eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2824d4dbff95SChris Mason 282544871b1bSChris Mason return ret; 282644871b1bSChris Mason } 282744871b1bSChris Mason 282844871b1bSChris Mason /* 282944871b1bSChris Mason * split the path's leaf in two, making sure there is at least data_size 283044871b1bSChris Mason * available for the resulting leaf level of the path. 283144871b1bSChris Mason * 283244871b1bSChris Mason * returns 0 if all went well and < 0 on failure. 283344871b1bSChris Mason */ 283444871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 283544871b1bSChris Mason struct btrfs_root *root, 283644871b1bSChris Mason struct btrfs_key *ins_key, 283744871b1bSChris Mason struct btrfs_path *path, int data_size, 283844871b1bSChris Mason int extend) 283944871b1bSChris Mason { 284044871b1bSChris Mason struct extent_buffer *l; 284144871b1bSChris Mason u32 nritems; 284244871b1bSChris Mason int mid; 284344871b1bSChris Mason int slot; 284444871b1bSChris Mason struct extent_buffer *right; 284544871b1bSChris Mason int ret = 0; 284644871b1bSChris Mason int wret; 284744871b1bSChris Mason int double_split; 284844871b1bSChris Mason int num_doubles = 0; 284944871b1bSChris Mason 285044871b1bSChris Mason /* first try to make some room by pushing left and right */ 285144871b1bSChris Mason if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) { 285244871b1bSChris Mason wret = push_leaf_right(trans, root, path, data_size, 0); 285344871b1bSChris Mason if (wret < 0) 285444871b1bSChris Mason return wret; 285544871b1bSChris Mason if (wret) { 285644871b1bSChris Mason wret = push_leaf_left(trans, root, path, data_size, 0); 285744871b1bSChris Mason if (wret < 0) 285844871b1bSChris Mason return wret; 285944871b1bSChris Mason } 286044871b1bSChris Mason l = path->nodes[0]; 286144871b1bSChris Mason 286244871b1bSChris Mason /* did the pushes work? */ 286344871b1bSChris Mason if (btrfs_leaf_free_space(root, l) >= data_size) 286444871b1bSChris Mason return 0; 286544871b1bSChris Mason } 286644871b1bSChris Mason 286744871b1bSChris Mason if (!path->nodes[1]) { 286844871b1bSChris Mason ret = insert_new_root(trans, root, path, 1); 286944871b1bSChris Mason if (ret) 287044871b1bSChris Mason return ret; 287144871b1bSChris Mason } 287244871b1bSChris Mason again: 287344871b1bSChris Mason double_split = 0; 287444871b1bSChris Mason l = path->nodes[0]; 287544871b1bSChris Mason slot = path->slots[0]; 287644871b1bSChris Mason nritems = btrfs_header_nritems(l); 287744871b1bSChris Mason mid = (nritems + 1) / 2; 287844871b1bSChris Mason 287944871b1bSChris Mason right = btrfs_alloc_free_block(trans, root, root->leafsize, 288044871b1bSChris Mason path->nodes[1]->start, 288144871b1bSChris Mason root->root_key.objectid, 288244871b1bSChris Mason trans->transid, 0, l->start, 0); 288344871b1bSChris Mason if (IS_ERR(right)) { 288444871b1bSChris Mason BUG_ON(1); 288544871b1bSChris Mason return PTR_ERR(right); 288644871b1bSChris Mason } 288744871b1bSChris Mason 288844871b1bSChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 288944871b1bSChris Mason btrfs_set_header_bytenr(right, right->start); 289044871b1bSChris Mason btrfs_set_header_generation(right, trans->transid); 289144871b1bSChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 289244871b1bSChris Mason btrfs_set_header_level(right, 0); 289344871b1bSChris Mason write_extent_buffer(right, root->fs_info->fsid, 289444871b1bSChris Mason (unsigned long)btrfs_header_fsid(right), 289544871b1bSChris Mason BTRFS_FSID_SIZE); 289644871b1bSChris Mason 289744871b1bSChris Mason write_extent_buffer(right, root->fs_info->chunk_tree_uuid, 289844871b1bSChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(right), 289944871b1bSChris Mason BTRFS_UUID_SIZE); 290044871b1bSChris Mason 290144871b1bSChris Mason if (mid <= slot) { 290244871b1bSChris Mason if (nritems == 1 || 290344871b1bSChris Mason leaf_space_used(l, mid, nritems - mid) + data_size > 290444871b1bSChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 290544871b1bSChris Mason if (slot >= nritems) { 290644871b1bSChris Mason struct btrfs_disk_key disk_key; 290744871b1bSChris Mason 290844871b1bSChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 290944871b1bSChris Mason btrfs_set_header_nritems(right, 0); 291044871b1bSChris Mason wret = insert_ptr(trans, root, path, 291144871b1bSChris Mason &disk_key, right->start, 291244871b1bSChris Mason path->slots[1] + 1, 1); 291344871b1bSChris Mason if (wret) 291444871b1bSChris Mason ret = wret; 291544871b1bSChris Mason 291644871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 291744871b1bSChris Mason free_extent_buffer(path->nodes[0]); 291844871b1bSChris Mason path->nodes[0] = right; 291944871b1bSChris Mason path->slots[0] = 0; 292044871b1bSChris Mason path->slots[1] += 1; 292144871b1bSChris Mason btrfs_mark_buffer_dirty(right); 292244871b1bSChris Mason return ret; 292344871b1bSChris Mason } 292444871b1bSChris Mason mid = slot; 292544871b1bSChris Mason if (mid != nritems && 292644871b1bSChris Mason leaf_space_used(l, mid, nritems - mid) + 292744871b1bSChris Mason data_size > BTRFS_LEAF_DATA_SIZE(root)) { 292844871b1bSChris Mason double_split = 1; 292944871b1bSChris Mason } 293044871b1bSChris Mason } 293144871b1bSChris Mason } else { 293244871b1bSChris Mason if (leaf_space_used(l, 0, mid) + data_size > 293344871b1bSChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 293444871b1bSChris Mason if (!extend && data_size && slot == 0) { 293544871b1bSChris Mason struct btrfs_disk_key disk_key; 293644871b1bSChris Mason 293744871b1bSChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 293844871b1bSChris Mason btrfs_set_header_nritems(right, 0); 293944871b1bSChris Mason wret = insert_ptr(trans, root, path, 294044871b1bSChris Mason &disk_key, 294144871b1bSChris Mason right->start, 294244871b1bSChris Mason path->slots[1], 1); 294344871b1bSChris Mason if (wret) 294444871b1bSChris Mason ret = wret; 294544871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 294644871b1bSChris Mason free_extent_buffer(path->nodes[0]); 294744871b1bSChris Mason path->nodes[0] = right; 294844871b1bSChris Mason path->slots[0] = 0; 294944871b1bSChris Mason if (path->slots[1] == 0) { 295044871b1bSChris Mason wret = fixup_low_keys(trans, root, 295144871b1bSChris Mason path, &disk_key, 1); 295244871b1bSChris Mason if (wret) 295344871b1bSChris Mason ret = wret; 295444871b1bSChris Mason } 295544871b1bSChris Mason btrfs_mark_buffer_dirty(right); 295644871b1bSChris Mason return ret; 295744871b1bSChris Mason } else if ((extend || !data_size) && slot == 0) { 295844871b1bSChris Mason mid = 1; 295944871b1bSChris Mason } else { 296044871b1bSChris Mason mid = slot; 296144871b1bSChris Mason if (mid != nritems && 296244871b1bSChris Mason leaf_space_used(l, mid, nritems - mid) + 296344871b1bSChris Mason data_size > BTRFS_LEAF_DATA_SIZE(root)) { 296444871b1bSChris Mason double_split = 1; 296544871b1bSChris Mason } 296644871b1bSChris Mason } 296744871b1bSChris Mason } 296844871b1bSChris Mason } 296944871b1bSChris Mason 297044871b1bSChris Mason ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems); 297144871b1bSChris Mason BUG_ON(ret); 297244871b1bSChris Mason 2973cc0c5538SChris Mason if (double_split) { 2974cc0c5538SChris Mason BUG_ON(num_doubles != 0); 2975cc0c5538SChris Mason num_doubles++; 2976cc0c5538SChris Mason goto again; 29773326d1b0SChris Mason } 297844871b1bSChris Mason 2979be0e5c09SChris Mason return ret; 2980be0e5c09SChris Mason } 2981be0e5c09SChris Mason 2982d352ac68SChris Mason /* 2983459931ecSChris Mason * This function splits a single item into two items, 2984459931ecSChris Mason * giving 'new_key' to the new item and splitting the 2985459931ecSChris Mason * old one at split_offset (from the start of the item). 2986459931ecSChris Mason * 2987459931ecSChris Mason * The path may be released by this operation. After 2988459931ecSChris Mason * the split, the path is pointing to the old item. The 2989459931ecSChris Mason * new item is going to be in the same node as the old one. 2990459931ecSChris Mason * 2991459931ecSChris Mason * Note, the item being split must be smaller enough to live alone on 2992459931ecSChris Mason * a tree block with room for one extra struct btrfs_item 2993459931ecSChris Mason * 2994459931ecSChris Mason * This allows us to split the item in place, keeping a lock on the 2995459931ecSChris Mason * leaf the entire time. 2996459931ecSChris Mason */ 2997459931ecSChris Mason int btrfs_split_item(struct btrfs_trans_handle *trans, 2998459931ecSChris Mason struct btrfs_root *root, 2999459931ecSChris Mason struct btrfs_path *path, 3000459931ecSChris Mason struct btrfs_key *new_key, 3001459931ecSChris Mason unsigned long split_offset) 3002459931ecSChris Mason { 3003459931ecSChris Mason u32 item_size; 3004459931ecSChris Mason struct extent_buffer *leaf; 3005459931ecSChris Mason struct btrfs_key orig_key; 3006459931ecSChris Mason struct btrfs_item *item; 3007459931ecSChris Mason struct btrfs_item *new_item; 3008459931ecSChris Mason int ret = 0; 3009459931ecSChris Mason int slot; 3010459931ecSChris Mason u32 nritems; 3011459931ecSChris Mason u32 orig_offset; 3012459931ecSChris Mason struct btrfs_disk_key disk_key; 3013459931ecSChris Mason char *buf; 3014459931ecSChris Mason 3015459931ecSChris Mason leaf = path->nodes[0]; 3016459931ecSChris Mason btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]); 3017459931ecSChris Mason if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item)) 3018459931ecSChris Mason goto split; 3019459931ecSChris Mason 3020459931ecSChris Mason item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3021459931ecSChris Mason btrfs_release_path(root, path); 3022459931ecSChris Mason 3023459931ecSChris Mason path->search_for_split = 1; 3024459931ecSChris Mason path->keep_locks = 1; 3025459931ecSChris Mason 3026459931ecSChris Mason ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1); 3027459931ecSChris Mason path->search_for_split = 0; 3028459931ecSChris Mason 3029459931ecSChris Mason /* if our item isn't there or got smaller, return now */ 3030459931ecSChris Mason if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0], 3031459931ecSChris Mason path->slots[0])) { 3032459931ecSChris Mason path->keep_locks = 0; 3033459931ecSChris Mason return -EAGAIN; 3034459931ecSChris Mason } 3035459931ecSChris Mason 3036b9473439SChris Mason btrfs_set_path_blocking(path); 303787b29b20SYan Zheng ret = split_leaf(trans, root, &orig_key, path, 303887b29b20SYan Zheng sizeof(struct btrfs_item), 1); 3039459931ecSChris Mason path->keep_locks = 0; 3040459931ecSChris Mason BUG_ON(ret); 3041459931ecSChris Mason 3042b9473439SChris Mason btrfs_unlock_up_safe(path, 1); 3043b9473439SChris Mason leaf = path->nodes[0]; 3044b9473439SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item)); 3045b9473439SChris Mason 3046b9473439SChris Mason split: 3047b4ce94deSChris Mason /* 3048b4ce94deSChris Mason * make sure any changes to the path from split_leaf leave it 3049b4ce94deSChris Mason * in a blocking state 3050b4ce94deSChris Mason */ 3051b4ce94deSChris Mason btrfs_set_path_blocking(path); 3052b4ce94deSChris Mason 3053459931ecSChris Mason item = btrfs_item_nr(leaf, path->slots[0]); 3054459931ecSChris Mason orig_offset = btrfs_item_offset(leaf, item); 3055459931ecSChris Mason item_size = btrfs_item_size(leaf, item); 3056459931ecSChris Mason 3057459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 3058459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3059459931ecSChris Mason path->slots[0]), item_size); 3060459931ecSChris Mason slot = path->slots[0] + 1; 3061459931ecSChris Mason leaf = path->nodes[0]; 3062459931ecSChris Mason 3063459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 3064459931ecSChris Mason 3065459931ecSChris Mason if (slot != nritems) { 3066459931ecSChris Mason /* shift the items */ 3067459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 3068459931ecSChris Mason btrfs_item_nr_offset(slot), 3069459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3070459931ecSChris Mason 3071459931ecSChris Mason } 3072459931ecSChris Mason 3073459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 3074459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3075459931ecSChris Mason 3076459931ecSChris Mason new_item = btrfs_item_nr(leaf, slot); 3077459931ecSChris Mason 3078459931ecSChris Mason btrfs_set_item_offset(leaf, new_item, orig_offset); 3079459931ecSChris Mason btrfs_set_item_size(leaf, new_item, item_size - split_offset); 3080459931ecSChris Mason 3081459931ecSChris Mason btrfs_set_item_offset(leaf, item, 3082459931ecSChris Mason orig_offset + item_size - split_offset); 3083459931ecSChris Mason btrfs_set_item_size(leaf, item, split_offset); 3084459931ecSChris Mason 3085459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 3086459931ecSChris Mason 3087459931ecSChris Mason /* write the data for the start of the original item */ 3088459931ecSChris Mason write_extent_buffer(leaf, buf, 3089459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 3090459931ecSChris Mason split_offset); 3091459931ecSChris Mason 3092459931ecSChris Mason /* write the data for the new item */ 3093459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 3094459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 3095459931ecSChris Mason item_size - split_offset); 3096459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 3097459931ecSChris Mason 3098459931ecSChris Mason ret = 0; 3099459931ecSChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 3100459931ecSChris Mason btrfs_print_leaf(root, leaf); 3101459931ecSChris Mason BUG(); 3102459931ecSChris Mason } 3103459931ecSChris Mason kfree(buf); 3104459931ecSChris Mason return ret; 3105459931ecSChris Mason } 3106459931ecSChris Mason 3107459931ecSChris Mason /* 3108d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 3109d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 3110d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 3111d352ac68SChris Mason * the front. 3112d352ac68SChris Mason */ 3113b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans, 3114b18c6685SChris Mason struct btrfs_root *root, 3115b18c6685SChris Mason struct btrfs_path *path, 3116179e29e4SChris Mason u32 new_size, int from_end) 3117b18c6685SChris Mason { 3118b18c6685SChris Mason int ret = 0; 3119b18c6685SChris Mason int slot; 3120b18c6685SChris Mason int slot_orig; 31215f39d397SChris Mason struct extent_buffer *leaf; 31225f39d397SChris Mason struct btrfs_item *item; 3123b18c6685SChris Mason u32 nritems; 3124b18c6685SChris Mason unsigned int data_end; 3125b18c6685SChris Mason unsigned int old_data_start; 3126b18c6685SChris Mason unsigned int old_size; 3127b18c6685SChris Mason unsigned int size_diff; 3128b18c6685SChris Mason int i; 3129b18c6685SChris Mason 3130b18c6685SChris Mason slot_orig = path->slots[0]; 31315f39d397SChris Mason leaf = path->nodes[0]; 3132179e29e4SChris Mason slot = path->slots[0]; 3133179e29e4SChris Mason 3134179e29e4SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 3135179e29e4SChris Mason if (old_size == new_size) 3136179e29e4SChris Mason return 0; 3137b18c6685SChris Mason 31385f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3139b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 3140b18c6685SChris Mason 31415f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 3142179e29e4SChris Mason 3143b18c6685SChris Mason size_diff = old_size - new_size; 3144b18c6685SChris Mason 3145b18c6685SChris Mason BUG_ON(slot < 0); 3146b18c6685SChris Mason BUG_ON(slot >= nritems); 3147b18c6685SChris Mason 3148b18c6685SChris Mason /* 3149b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3150b18c6685SChris Mason */ 3151b18c6685SChris Mason /* first correct the data pointers */ 3152b18c6685SChris Mason for (i = slot; i < nritems; i++) { 31535f39d397SChris Mason u32 ioff; 31545f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3155db94535dSChris Mason 3156db94535dSChris Mason if (!leaf->map_token) { 3157db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3158db94535dSChris Mason sizeof(struct btrfs_item), 3159db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3160db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3161db94535dSChris Mason KM_USER1); 3162db94535dSChris Mason } 3163db94535dSChris Mason 31645f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 31655f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + size_diff); 3166b18c6685SChris Mason } 3167db94535dSChris Mason 3168db94535dSChris Mason if (leaf->map_token) { 3169db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3170db94535dSChris Mason leaf->map_token = NULL; 3171db94535dSChris Mason } 3172db94535dSChris Mason 3173b18c6685SChris Mason /* shift the data */ 3174179e29e4SChris Mason if (from_end) { 31755f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3176b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 3177b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 3178179e29e4SChris Mason } else { 3179179e29e4SChris Mason struct btrfs_disk_key disk_key; 3180179e29e4SChris Mason u64 offset; 3181179e29e4SChris Mason 3182179e29e4SChris Mason btrfs_item_key(leaf, &disk_key, slot); 3183179e29e4SChris Mason 3184179e29e4SChris Mason if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 3185179e29e4SChris Mason unsigned long ptr; 3186179e29e4SChris Mason struct btrfs_file_extent_item *fi; 3187179e29e4SChris Mason 3188179e29e4SChris Mason fi = btrfs_item_ptr(leaf, slot, 3189179e29e4SChris Mason struct btrfs_file_extent_item); 3190179e29e4SChris Mason fi = (struct btrfs_file_extent_item *)( 3191179e29e4SChris Mason (unsigned long)fi - size_diff); 3192179e29e4SChris Mason 3193179e29e4SChris Mason if (btrfs_file_extent_type(leaf, fi) == 3194179e29e4SChris Mason BTRFS_FILE_EXTENT_INLINE) { 3195179e29e4SChris Mason ptr = btrfs_item_ptr_offset(leaf, slot); 3196179e29e4SChris Mason memmove_extent_buffer(leaf, ptr, 3197179e29e4SChris Mason (unsigned long)fi, 3198179e29e4SChris Mason offsetof(struct btrfs_file_extent_item, 3199179e29e4SChris Mason disk_bytenr)); 3200179e29e4SChris Mason } 3201179e29e4SChris Mason } 3202179e29e4SChris Mason 3203179e29e4SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3204179e29e4SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 3205179e29e4SChris Mason data_end, old_data_start - data_end); 3206179e29e4SChris Mason 3207179e29e4SChris Mason offset = btrfs_disk_key_offset(&disk_key); 3208179e29e4SChris Mason btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 3209179e29e4SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3210179e29e4SChris Mason if (slot == 0) 3211179e29e4SChris Mason fixup_low_keys(trans, root, path, &disk_key, 1); 3212179e29e4SChris Mason } 32135f39d397SChris Mason 32145f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 32155f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 32165f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3217b18c6685SChris Mason 3218b18c6685SChris Mason ret = 0; 32195f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 32205f39d397SChris Mason btrfs_print_leaf(root, leaf); 3221b18c6685SChris Mason BUG(); 32225f39d397SChris Mason } 3223b18c6685SChris Mason return ret; 3224b18c6685SChris Mason } 3225b18c6685SChris Mason 3226d352ac68SChris Mason /* 3227d352ac68SChris Mason * make the item pointed to by the path bigger, data_size is the new size. 3228d352ac68SChris Mason */ 32295f39d397SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans, 32305f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 32315f39d397SChris Mason u32 data_size) 32326567e837SChris Mason { 32336567e837SChris Mason int ret = 0; 32346567e837SChris Mason int slot; 32356567e837SChris Mason int slot_orig; 32365f39d397SChris Mason struct extent_buffer *leaf; 32375f39d397SChris Mason struct btrfs_item *item; 32386567e837SChris Mason u32 nritems; 32396567e837SChris Mason unsigned int data_end; 32406567e837SChris Mason unsigned int old_data; 32416567e837SChris Mason unsigned int old_size; 32426567e837SChris Mason int i; 32436567e837SChris Mason 32446567e837SChris Mason slot_orig = path->slots[0]; 32455f39d397SChris Mason leaf = path->nodes[0]; 32466567e837SChris Mason 32475f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 32486567e837SChris Mason data_end = leaf_data_end(root, leaf); 32496567e837SChris Mason 32505f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 32515f39d397SChris Mason btrfs_print_leaf(root, leaf); 32526567e837SChris Mason BUG(); 32535f39d397SChris Mason } 32546567e837SChris Mason slot = path->slots[0]; 32555f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 32566567e837SChris Mason 32576567e837SChris Mason BUG_ON(slot < 0); 32583326d1b0SChris Mason if (slot >= nritems) { 32593326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3260d397712bSChris Mason printk(KERN_CRIT "slot %d too large, nritems %d\n", 3261d397712bSChris Mason slot, nritems); 32623326d1b0SChris Mason BUG_ON(1); 32633326d1b0SChris Mason } 32646567e837SChris Mason 32656567e837SChris Mason /* 32666567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 32676567e837SChris Mason */ 32686567e837SChris Mason /* first correct the data pointers */ 32696567e837SChris Mason for (i = slot; i < nritems; i++) { 32705f39d397SChris Mason u32 ioff; 32715f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3272db94535dSChris Mason 3273db94535dSChris Mason if (!leaf->map_token) { 3274db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3275db94535dSChris Mason sizeof(struct btrfs_item), 3276db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3277db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3278db94535dSChris Mason KM_USER1); 3279db94535dSChris Mason } 32805f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 32815f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 32826567e837SChris Mason } 32835f39d397SChris Mason 3284db94535dSChris Mason if (leaf->map_token) { 3285db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3286db94535dSChris Mason leaf->map_token = NULL; 3287db94535dSChris Mason } 3288db94535dSChris Mason 32896567e837SChris Mason /* shift the data */ 32905f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 32916567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 32926567e837SChris Mason data_end, old_data - data_end); 32935f39d397SChris Mason 32946567e837SChris Mason data_end = old_data; 32955f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 32965f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 32975f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 32985f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 32996567e837SChris Mason 33006567e837SChris Mason ret = 0; 33015f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 33025f39d397SChris Mason btrfs_print_leaf(root, leaf); 33036567e837SChris Mason BUG(); 33045f39d397SChris Mason } 33056567e837SChris Mason return ret; 33066567e837SChris Mason } 33076567e837SChris Mason 330874123bd7SChris Mason /* 3309d352ac68SChris Mason * Given a key and some data, insert items into the tree. 331074123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 3311f3465ca4SJosef Bacik * Returns the number of keys that were inserted. 3312f3465ca4SJosef Bacik */ 3313f3465ca4SJosef Bacik int btrfs_insert_some_items(struct btrfs_trans_handle *trans, 3314f3465ca4SJosef Bacik struct btrfs_root *root, 3315f3465ca4SJosef Bacik struct btrfs_path *path, 3316f3465ca4SJosef Bacik struct btrfs_key *cpu_key, u32 *data_size, 3317f3465ca4SJosef Bacik int nr) 3318f3465ca4SJosef Bacik { 3319f3465ca4SJosef Bacik struct extent_buffer *leaf; 3320f3465ca4SJosef Bacik struct btrfs_item *item; 3321f3465ca4SJosef Bacik int ret = 0; 3322f3465ca4SJosef Bacik int slot; 3323f3465ca4SJosef Bacik int i; 3324f3465ca4SJosef Bacik u32 nritems; 3325f3465ca4SJosef Bacik u32 total_data = 0; 3326f3465ca4SJosef Bacik u32 total_size = 0; 3327f3465ca4SJosef Bacik unsigned int data_end; 3328f3465ca4SJosef Bacik struct btrfs_disk_key disk_key; 3329f3465ca4SJosef Bacik struct btrfs_key found_key; 3330f3465ca4SJosef Bacik 333187b29b20SYan Zheng for (i = 0; i < nr; i++) { 333287b29b20SYan Zheng if (total_size + data_size[i] + sizeof(struct btrfs_item) > 333387b29b20SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 333487b29b20SYan Zheng break; 333587b29b20SYan Zheng nr = i; 333687b29b20SYan Zheng } 3337f3465ca4SJosef Bacik total_data += data_size[i]; 333887b29b20SYan Zheng total_size += data_size[i] + sizeof(struct btrfs_item); 333987b29b20SYan Zheng } 334087b29b20SYan Zheng BUG_ON(nr == 0); 3341f3465ca4SJosef Bacik 3342f3465ca4SJosef Bacik ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 3343f3465ca4SJosef Bacik if (ret == 0) 3344f3465ca4SJosef Bacik return -EEXIST; 3345f3465ca4SJosef Bacik if (ret < 0) 3346f3465ca4SJosef Bacik goto out; 3347f3465ca4SJosef Bacik 3348f3465ca4SJosef Bacik leaf = path->nodes[0]; 3349f3465ca4SJosef Bacik 3350f3465ca4SJosef Bacik nritems = btrfs_header_nritems(leaf); 3351f3465ca4SJosef Bacik data_end = leaf_data_end(root, leaf); 3352f3465ca4SJosef Bacik 3353f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < total_size) { 3354f3465ca4SJosef Bacik for (i = nr; i >= 0; i--) { 3355f3465ca4SJosef Bacik total_data -= data_size[i]; 3356f3465ca4SJosef Bacik total_size -= data_size[i] + sizeof(struct btrfs_item); 3357f3465ca4SJosef Bacik if (total_size < btrfs_leaf_free_space(root, leaf)) 3358f3465ca4SJosef Bacik break; 3359f3465ca4SJosef Bacik } 3360f3465ca4SJosef Bacik nr = i; 3361f3465ca4SJosef Bacik } 3362f3465ca4SJosef Bacik 3363f3465ca4SJosef Bacik slot = path->slots[0]; 3364f3465ca4SJosef Bacik BUG_ON(slot < 0); 3365f3465ca4SJosef Bacik 3366f3465ca4SJosef Bacik if (slot != nritems) { 3367f3465ca4SJosef Bacik unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3368f3465ca4SJosef Bacik 3369f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot); 3370f3465ca4SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, slot); 3371f3465ca4SJosef Bacik 3372f3465ca4SJosef Bacik /* figure out how many keys we can insert in here */ 3373f3465ca4SJosef Bacik total_data = data_size[0]; 3374f3465ca4SJosef Bacik for (i = 1; i < nr; i++) { 3375f3465ca4SJosef Bacik if (comp_cpu_keys(&found_key, cpu_key + i) <= 0) 3376f3465ca4SJosef Bacik break; 3377f3465ca4SJosef Bacik total_data += data_size[i]; 3378f3465ca4SJosef Bacik } 3379f3465ca4SJosef Bacik nr = i; 3380f3465ca4SJosef Bacik 3381f3465ca4SJosef Bacik if (old_data < data_end) { 3382f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3383d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 3384f3465ca4SJosef Bacik slot, old_data, data_end); 3385f3465ca4SJosef Bacik BUG_ON(1); 3386f3465ca4SJosef Bacik } 3387f3465ca4SJosef Bacik /* 3388f3465ca4SJosef Bacik * item0..itemN ... dataN.offset..dataN.size .. data0.size 3389f3465ca4SJosef Bacik */ 3390f3465ca4SJosef Bacik /* first correct the data pointers */ 3391f3465ca4SJosef Bacik WARN_ON(leaf->map_token); 3392f3465ca4SJosef Bacik for (i = slot; i < nritems; i++) { 3393f3465ca4SJosef Bacik u32 ioff; 3394f3465ca4SJosef Bacik 3395f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, i); 3396f3465ca4SJosef Bacik if (!leaf->map_token) { 3397f3465ca4SJosef Bacik map_extent_buffer(leaf, (unsigned long)item, 3398f3465ca4SJosef Bacik sizeof(struct btrfs_item), 3399f3465ca4SJosef Bacik &leaf->map_token, &leaf->kaddr, 3400f3465ca4SJosef Bacik &leaf->map_start, &leaf->map_len, 3401f3465ca4SJosef Bacik KM_USER1); 3402f3465ca4SJosef Bacik } 3403f3465ca4SJosef Bacik 3404f3465ca4SJosef Bacik ioff = btrfs_item_offset(leaf, item); 3405f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, ioff - total_data); 3406f3465ca4SJosef Bacik } 3407f3465ca4SJosef Bacik if (leaf->map_token) { 3408f3465ca4SJosef Bacik unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3409f3465ca4SJosef Bacik leaf->map_token = NULL; 3410f3465ca4SJosef Bacik } 3411f3465ca4SJosef Bacik 3412f3465ca4SJosef Bacik /* shift the items */ 3413f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 3414f3465ca4SJosef Bacik btrfs_item_nr_offset(slot), 3415f3465ca4SJosef Bacik (nritems - slot) * sizeof(struct btrfs_item)); 3416f3465ca4SJosef Bacik 3417f3465ca4SJosef Bacik /* shift the data */ 3418f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3419f3465ca4SJosef Bacik data_end - total_data, btrfs_leaf_data(leaf) + 3420f3465ca4SJosef Bacik data_end, old_data - data_end); 3421f3465ca4SJosef Bacik data_end = old_data; 3422f3465ca4SJosef Bacik } else { 3423f3465ca4SJosef Bacik /* 3424f3465ca4SJosef Bacik * this sucks but it has to be done, if we are inserting at 3425f3465ca4SJosef Bacik * the end of the leaf only insert 1 of the items, since we 3426f3465ca4SJosef Bacik * have no way of knowing whats on the next leaf and we'd have 3427f3465ca4SJosef Bacik * to drop our current locks to figure it out 3428f3465ca4SJosef Bacik */ 3429f3465ca4SJosef Bacik nr = 1; 3430f3465ca4SJosef Bacik } 3431f3465ca4SJosef Bacik 3432f3465ca4SJosef Bacik /* setup the item for the new data */ 3433f3465ca4SJosef Bacik for (i = 0; i < nr; i++) { 3434f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 3435f3465ca4SJosef Bacik btrfs_set_item_key(leaf, &disk_key, slot + i); 3436f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot + i); 3437f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 3438f3465ca4SJosef Bacik data_end -= data_size[i]; 3439f3465ca4SJosef Bacik btrfs_set_item_size(leaf, item, data_size[i]); 3440f3465ca4SJosef Bacik } 3441f3465ca4SJosef Bacik btrfs_set_header_nritems(leaf, nritems + nr); 3442f3465ca4SJosef Bacik btrfs_mark_buffer_dirty(leaf); 3443f3465ca4SJosef Bacik 3444f3465ca4SJosef Bacik ret = 0; 3445f3465ca4SJosef Bacik if (slot == 0) { 3446f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3447f3465ca4SJosef Bacik ret = fixup_low_keys(trans, root, path, &disk_key, 1); 3448f3465ca4SJosef Bacik } 3449f3465ca4SJosef Bacik 3450f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < 0) { 3451f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3452f3465ca4SJosef Bacik BUG(); 3453f3465ca4SJosef Bacik } 3454f3465ca4SJosef Bacik out: 3455f3465ca4SJosef Bacik if (!ret) 3456f3465ca4SJosef Bacik ret = nr; 3457f3465ca4SJosef Bacik return ret; 3458f3465ca4SJosef Bacik } 3459f3465ca4SJosef Bacik 3460f3465ca4SJosef Bacik /* 346144871b1bSChris Mason * this is a helper for btrfs_insert_empty_items, the main goal here is 346244871b1bSChris Mason * to save stack depth by doing the bulk of the work in a function 346344871b1bSChris Mason * that doesn't call btrfs_search_slot 346474123bd7SChris Mason */ 346544871b1bSChris Mason static noinline_for_stack int 346644871b1bSChris Mason setup_items_for_insert(struct btrfs_trans_handle *trans, 346744871b1bSChris Mason struct btrfs_root *root, struct btrfs_path *path, 34689c58309dSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 346944871b1bSChris Mason u32 total_data, u32 total_size, int nr) 3470be0e5c09SChris Mason { 34715f39d397SChris Mason struct btrfs_item *item; 34729c58309dSChris Mason int i; 34737518a238SChris Mason u32 nritems; 3474be0e5c09SChris Mason unsigned int data_end; 3475e2fa7227SChris Mason struct btrfs_disk_key disk_key; 347644871b1bSChris Mason int ret; 347744871b1bSChris Mason struct extent_buffer *leaf; 347844871b1bSChris Mason int slot; 3479e2fa7227SChris Mason 34805f39d397SChris Mason leaf = path->nodes[0]; 348144871b1bSChris Mason slot = path->slots[0]; 348274123bd7SChris Mason 34835f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3484123abc88SChris Mason data_end = leaf_data_end(root, leaf); 3485eb60ceacSChris Mason 3486f25956ccSChris Mason if (btrfs_leaf_free_space(root, leaf) < total_size) { 34873326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3488d397712bSChris Mason printk(KERN_CRIT "not enough freespace need %u have %d\n", 34899c58309dSChris Mason total_size, btrfs_leaf_free_space(root, leaf)); 3490be0e5c09SChris Mason BUG(); 3491d4dbff95SChris Mason } 34925f39d397SChris Mason 3493be0e5c09SChris Mason if (slot != nritems) { 34945f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3495be0e5c09SChris Mason 34965f39d397SChris Mason if (old_data < data_end) { 34975f39d397SChris Mason btrfs_print_leaf(root, leaf); 3498d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 34995f39d397SChris Mason slot, old_data, data_end); 35005f39d397SChris Mason BUG_ON(1); 35015f39d397SChris Mason } 3502be0e5c09SChris Mason /* 3503be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3504be0e5c09SChris Mason */ 3505be0e5c09SChris Mason /* first correct the data pointers */ 3506db94535dSChris Mason WARN_ON(leaf->map_token); 35070783fcfcSChris Mason for (i = slot; i < nritems; i++) { 35085f39d397SChris Mason u32 ioff; 3509db94535dSChris Mason 35105f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3511db94535dSChris Mason if (!leaf->map_token) { 3512db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3513db94535dSChris Mason sizeof(struct btrfs_item), 3514db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3515db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3516db94535dSChris Mason KM_USER1); 3517db94535dSChris Mason } 3518db94535dSChris Mason 35195f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 35209c58309dSChris Mason btrfs_set_item_offset(leaf, item, ioff - total_data); 35210783fcfcSChris Mason } 3522db94535dSChris Mason if (leaf->map_token) { 3523db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3524db94535dSChris Mason leaf->map_token = NULL; 3525db94535dSChris Mason } 3526be0e5c09SChris Mason 3527be0e5c09SChris Mason /* shift the items */ 35289c58309dSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 35295f39d397SChris Mason btrfs_item_nr_offset(slot), 35300783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3531be0e5c09SChris Mason 3532be0e5c09SChris Mason /* shift the data */ 35335f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 35349c58309dSChris Mason data_end - total_data, btrfs_leaf_data(leaf) + 3535be0e5c09SChris Mason data_end, old_data - data_end); 3536be0e5c09SChris Mason data_end = old_data; 3537be0e5c09SChris Mason } 35385f39d397SChris Mason 353962e2749eSChris Mason /* setup the item for the new data */ 35409c58309dSChris Mason for (i = 0; i < nr; i++) { 35419c58309dSChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 35429c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 35439c58309dSChris Mason item = btrfs_item_nr(leaf, slot + i); 35449c58309dSChris Mason btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 35459c58309dSChris Mason data_end -= data_size[i]; 35469c58309dSChris Mason btrfs_set_item_size(leaf, item, data_size[i]); 35479c58309dSChris Mason } 354844871b1bSChris Mason 35499c58309dSChris Mason btrfs_set_header_nritems(leaf, nritems + nr); 3550aa5d6bedSChris Mason 3551aa5d6bedSChris Mason ret = 0; 35525a01a2e3SChris Mason if (slot == 0) { 355344871b1bSChris Mason struct btrfs_disk_key disk_key; 35545a01a2e3SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3555e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 35565a01a2e3SChris Mason } 3557b9473439SChris Mason btrfs_unlock_up_safe(path, 1); 3558b9473439SChris Mason btrfs_mark_buffer_dirty(leaf); 3559aa5d6bedSChris Mason 35605f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 35615f39d397SChris Mason btrfs_print_leaf(root, leaf); 3562be0e5c09SChris Mason BUG(); 35635f39d397SChris Mason } 356444871b1bSChris Mason return ret; 356544871b1bSChris Mason } 356644871b1bSChris Mason 356744871b1bSChris Mason /* 356844871b1bSChris Mason * Given a key and some data, insert items into the tree. 356944871b1bSChris Mason * This does all the path init required, making room in the tree if needed. 357044871b1bSChris Mason */ 357144871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 357244871b1bSChris Mason struct btrfs_root *root, 357344871b1bSChris Mason struct btrfs_path *path, 357444871b1bSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 357544871b1bSChris Mason int nr) 357644871b1bSChris Mason { 357744871b1bSChris Mason struct extent_buffer *leaf; 357844871b1bSChris Mason int ret = 0; 357944871b1bSChris Mason int slot; 358044871b1bSChris Mason int i; 358144871b1bSChris Mason u32 total_size = 0; 358244871b1bSChris Mason u32 total_data = 0; 358344871b1bSChris Mason 358444871b1bSChris Mason for (i = 0; i < nr; i++) 358544871b1bSChris Mason total_data += data_size[i]; 358644871b1bSChris Mason 358744871b1bSChris Mason total_size = total_data + (nr * sizeof(struct btrfs_item)); 358844871b1bSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 358944871b1bSChris Mason if (ret == 0) 359044871b1bSChris Mason return -EEXIST; 359144871b1bSChris Mason if (ret < 0) 359244871b1bSChris Mason goto out; 359344871b1bSChris Mason 359444871b1bSChris Mason leaf = path->nodes[0]; 359544871b1bSChris Mason slot = path->slots[0]; 359644871b1bSChris Mason BUG_ON(slot < 0); 359744871b1bSChris Mason 359844871b1bSChris Mason ret = setup_items_for_insert(trans, root, path, cpu_key, data_size, 359944871b1bSChris Mason total_data, total_size, nr); 360044871b1bSChris Mason 3601ed2ff2cbSChris Mason out: 360262e2749eSChris Mason return ret; 360362e2749eSChris Mason } 360462e2749eSChris Mason 360562e2749eSChris Mason /* 360662e2749eSChris Mason * Given a key and some data, insert an item into the tree. 360762e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 360862e2749eSChris Mason */ 3609e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 3610e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 3611e089f05cSChris Mason data_size) 361262e2749eSChris Mason { 361362e2749eSChris Mason int ret = 0; 36142c90e5d6SChris Mason struct btrfs_path *path; 36155f39d397SChris Mason struct extent_buffer *leaf; 36165f39d397SChris Mason unsigned long ptr; 361762e2749eSChris Mason 36182c90e5d6SChris Mason path = btrfs_alloc_path(); 36192c90e5d6SChris Mason BUG_ON(!path); 36202c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 362162e2749eSChris Mason if (!ret) { 36225f39d397SChris Mason leaf = path->nodes[0]; 36235f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 36245f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 36255f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 362662e2749eSChris Mason } 36272c90e5d6SChris Mason btrfs_free_path(path); 3628aa5d6bedSChris Mason return ret; 3629be0e5c09SChris Mason } 3630be0e5c09SChris Mason 363174123bd7SChris Mason /* 36325de08d7dSChris Mason * delete the pointer from a given node. 363374123bd7SChris Mason * 3634d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 3635d352ac68SChris Mason * empty a node. 363674123bd7SChris Mason */ 3637e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 3638e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 3639be0e5c09SChris Mason { 36405f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 36417518a238SChris Mason u32 nritems; 3642aa5d6bedSChris Mason int ret = 0; 3643bb803951SChris Mason int wret; 3644be0e5c09SChris Mason 36455f39d397SChris Mason nritems = btrfs_header_nritems(parent); 3646be0e5c09SChris Mason if (slot != nritems - 1) { 36475f39d397SChris Mason memmove_extent_buffer(parent, 36485f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 36495f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 3650d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 3651d6025579SChris Mason (nritems - slot - 1)); 3652be0e5c09SChris Mason } 36537518a238SChris Mason nritems--; 36545f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 36557518a238SChris Mason if (nritems == 0 && parent == root->node) { 36565f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 3657eb60ceacSChris Mason /* just turn the root into a leaf and break */ 36585f39d397SChris Mason btrfs_set_header_level(root->node, 0); 3659bb803951SChris Mason } else if (slot == 0) { 36605f39d397SChris Mason struct btrfs_disk_key disk_key; 36615f39d397SChris Mason 36625f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 36635f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); 36640f70abe2SChris Mason if (wret) 36650f70abe2SChris Mason ret = wret; 3666be0e5c09SChris Mason } 3667d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 3668aa5d6bedSChris Mason return ret; 3669be0e5c09SChris Mason } 3670be0e5c09SChris Mason 367174123bd7SChris Mason /* 3672323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 3673323ac95bSChris Mason * path->nodes[1]. bytenr is the node block pointer, but since the callers 3674323ac95bSChris Mason * already know it, it is faster to have them pass it down than to 3675323ac95bSChris Mason * read it out of the node again. 3676323ac95bSChris Mason * 3677323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 3678323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 3679323ac95bSChris Mason * 3680323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 3681323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 3682323ac95bSChris Mason */ 3683323ac95bSChris Mason noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans, 3684323ac95bSChris Mason struct btrfs_root *root, 3685323ac95bSChris Mason struct btrfs_path *path, u64 bytenr) 3686323ac95bSChris Mason { 3687323ac95bSChris Mason int ret; 3688323ac95bSChris Mason u64 root_gen = btrfs_header_generation(path->nodes[1]); 36894d081c41SChris Mason u64 parent_start = path->nodes[1]->start; 36904d081c41SChris Mason u64 parent_owner = btrfs_header_owner(path->nodes[1]); 3691323ac95bSChris Mason 3692323ac95bSChris Mason ret = del_ptr(trans, root, path, 1, path->slots[1]); 3693323ac95bSChris Mason if (ret) 3694323ac95bSChris Mason return ret; 3695323ac95bSChris Mason 36964d081c41SChris Mason /* 36974d081c41SChris Mason * btrfs_free_extent is expensive, we want to make sure we 36984d081c41SChris Mason * aren't holding any locks when we call it 36994d081c41SChris Mason */ 37004d081c41SChris Mason btrfs_unlock_up_safe(path, 0); 37014d081c41SChris Mason 3702323ac95bSChris Mason ret = btrfs_free_extent(trans, root, bytenr, 3703323ac95bSChris Mason btrfs_level_size(root, 0), 37044d081c41SChris Mason parent_start, parent_owner, 37053bb1a1bcSYan Zheng root_gen, 0, 1); 3706323ac95bSChris Mason return ret; 3707323ac95bSChris Mason } 3708323ac95bSChris Mason /* 370974123bd7SChris Mason * delete the item at the leaf level in path. If that empties 371074123bd7SChris Mason * the leaf, remove it from the tree 371174123bd7SChris Mason */ 371285e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 371385e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 3714be0e5c09SChris Mason { 37155f39d397SChris Mason struct extent_buffer *leaf; 37165f39d397SChris Mason struct btrfs_item *item; 371785e21bacSChris Mason int last_off; 371885e21bacSChris Mason int dsize = 0; 3719aa5d6bedSChris Mason int ret = 0; 3720aa5d6bedSChris Mason int wret; 372185e21bacSChris Mason int i; 37227518a238SChris Mason u32 nritems; 3723be0e5c09SChris Mason 37245f39d397SChris Mason leaf = path->nodes[0]; 372585e21bacSChris Mason last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); 372685e21bacSChris Mason 372785e21bacSChris Mason for (i = 0; i < nr; i++) 372885e21bacSChris Mason dsize += btrfs_item_size_nr(leaf, slot + i); 372985e21bacSChris Mason 37305f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3731be0e5c09SChris Mason 373285e21bacSChris Mason if (slot + nr != nritems) { 3733123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 37345f39d397SChris Mason 37355f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3736d6025579SChris Mason data_end + dsize, 3737123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 373885e21bacSChris Mason last_off - data_end); 37395f39d397SChris Mason 374085e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 37415f39d397SChris Mason u32 ioff; 3742db94535dSChris Mason 37435f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3744db94535dSChris Mason if (!leaf->map_token) { 3745db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3746db94535dSChris Mason sizeof(struct btrfs_item), 3747db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3748db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3749db94535dSChris Mason KM_USER1); 3750db94535dSChris Mason } 37515f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 37525f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + dsize); 37530783fcfcSChris Mason } 3754db94535dSChris Mason 3755db94535dSChris Mason if (leaf->map_token) { 3756db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3757db94535dSChris Mason leaf->map_token = NULL; 3758db94535dSChris Mason } 3759db94535dSChris Mason 37605f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 376185e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 37620783fcfcSChris Mason sizeof(struct btrfs_item) * 376385e21bacSChris Mason (nritems - slot - nr)); 3764be0e5c09SChris Mason } 376585e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 376685e21bacSChris Mason nritems -= nr; 37675f39d397SChris Mason 376874123bd7SChris Mason /* delete the leaf if we've emptied it */ 37697518a238SChris Mason if (nritems == 0) { 37705f39d397SChris Mason if (leaf == root->node) { 37715f39d397SChris Mason btrfs_set_header_level(leaf, 0); 37729a8dd150SChris Mason } else { 3773323ac95bSChris Mason ret = btrfs_del_leaf(trans, root, path, leaf->start); 3774323ac95bSChris Mason BUG_ON(ret); 37759a8dd150SChris Mason } 3776be0e5c09SChris Mason } else { 37777518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 3778aa5d6bedSChris Mason if (slot == 0) { 37795f39d397SChris Mason struct btrfs_disk_key disk_key; 37805f39d397SChris Mason 37815f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 3782e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 37835f39d397SChris Mason &disk_key, 1); 3784aa5d6bedSChris Mason if (wret) 3785aa5d6bedSChris Mason ret = wret; 3786aa5d6bedSChris Mason } 3787aa5d6bedSChris Mason 378874123bd7SChris Mason /* delete the leaf if it is mostly empty */ 378985e21bacSChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) { 3790be0e5c09SChris Mason /* push_leaf_left fixes the path. 3791be0e5c09SChris Mason * make sure the path still points to our leaf 3792be0e5c09SChris Mason * for possible call to del_ptr below 3793be0e5c09SChris Mason */ 37944920c9acSChris Mason slot = path->slots[1]; 37955f39d397SChris Mason extent_buffer_get(leaf); 37965f39d397SChris Mason 3797b9473439SChris Mason btrfs_set_path_blocking(path); 379885e21bacSChris Mason wret = push_leaf_left(trans, root, path, 1, 1); 379954aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3800aa5d6bedSChris Mason ret = wret; 38015f39d397SChris Mason 38025f39d397SChris Mason if (path->nodes[0] == leaf && 38035f39d397SChris Mason btrfs_header_nritems(leaf)) { 380485e21bacSChris Mason wret = push_leaf_right(trans, root, path, 1, 1); 380554aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3806aa5d6bedSChris Mason ret = wret; 3807aa5d6bedSChris Mason } 38085f39d397SChris Mason 38095f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 3810323ac95bSChris Mason path->slots[1] = slot; 3811d397712bSChris Mason ret = btrfs_del_leaf(trans, root, path, 3812d397712bSChris Mason leaf->start); 3813323ac95bSChris Mason BUG_ON(ret); 38145f39d397SChris Mason free_extent_buffer(leaf); 38155de08d7dSChris Mason } else { 3816925baeddSChris Mason /* if we're still in the path, make sure 3817925baeddSChris Mason * we're dirty. Otherwise, one of the 3818925baeddSChris Mason * push_leaf functions must have already 3819925baeddSChris Mason * dirtied this buffer 3820925baeddSChris Mason */ 3821925baeddSChris Mason if (path->nodes[0] == leaf) 38225f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 38235f39d397SChris Mason free_extent_buffer(leaf); 3824be0e5c09SChris Mason } 3825d5719762SChris Mason } else { 38265f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3827be0e5c09SChris Mason } 38289a8dd150SChris Mason } 3829aa5d6bedSChris Mason return ret; 38309a8dd150SChris Mason } 38319a8dd150SChris Mason 383297571fd0SChris Mason /* 3833925baeddSChris Mason * search the tree again to find a leaf with lesser keys 38347bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 38357bb86316SChris Mason * returns < 0 on io errors. 3836d352ac68SChris Mason * 3837d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 3838d352ac68SChris Mason * time you call it. 38397bb86316SChris Mason */ 38407bb86316SChris Mason int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 38417bb86316SChris Mason { 3842925baeddSChris Mason struct btrfs_key key; 3843925baeddSChris Mason struct btrfs_disk_key found_key; 3844925baeddSChris Mason int ret; 38457bb86316SChris Mason 3846925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 3847925baeddSChris Mason 3848925baeddSChris Mason if (key.offset > 0) 3849925baeddSChris Mason key.offset--; 3850925baeddSChris Mason else if (key.type > 0) 3851925baeddSChris Mason key.type--; 3852925baeddSChris Mason else if (key.objectid > 0) 3853925baeddSChris Mason key.objectid--; 3854925baeddSChris Mason else 38557bb86316SChris Mason return 1; 38567bb86316SChris Mason 3857925baeddSChris Mason btrfs_release_path(root, path); 3858925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 3859925baeddSChris Mason if (ret < 0) 3860925baeddSChris Mason return ret; 3861925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 3862925baeddSChris Mason ret = comp_keys(&found_key, &key); 3863925baeddSChris Mason if (ret < 0) 38647bb86316SChris Mason return 0; 3865925baeddSChris Mason return 1; 38667bb86316SChris Mason } 38677bb86316SChris Mason 38683f157a2fSChris Mason /* 38693f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 38703f157a2fSChris Mason * for nodes or leaves that are either in cache or have a minimum 3871d352ac68SChris Mason * transaction id. This is used by the btree defrag code, and tree logging 38723f157a2fSChris Mason * 38733f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 38743f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 38753f157a2fSChris Mason * key and get a writable path. 38763f157a2fSChris Mason * 38773f157a2fSChris Mason * This does lock as it descends, and path->keep_locks should be set 38783f157a2fSChris Mason * to 1 by the caller. 38793f157a2fSChris Mason * 38803f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 38813f157a2fSChris Mason * of the tree. 38823f157a2fSChris Mason * 3883d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 3884d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 3885d352ac68SChris Mason * skipped over (without reading them). 3886d352ac68SChris Mason * 38873f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 38883f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 38893f157a2fSChris Mason */ 38903f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 3891e02119d5SChris Mason struct btrfs_key *max_key, 38923f157a2fSChris Mason struct btrfs_path *path, int cache_only, 38933f157a2fSChris Mason u64 min_trans) 38943f157a2fSChris Mason { 38953f157a2fSChris Mason struct extent_buffer *cur; 38963f157a2fSChris Mason struct btrfs_key found_key; 38973f157a2fSChris Mason int slot; 38989652480bSYan int sret; 38993f157a2fSChris Mason u32 nritems; 39003f157a2fSChris Mason int level; 39013f157a2fSChris Mason int ret = 1; 39023f157a2fSChris Mason 3903934d375bSChris Mason WARN_ON(!path->keep_locks); 39043f157a2fSChris Mason again: 39053f157a2fSChris Mason cur = btrfs_lock_root_node(root); 39063f157a2fSChris Mason level = btrfs_header_level(cur); 3907e02119d5SChris Mason WARN_ON(path->nodes[level]); 39083f157a2fSChris Mason path->nodes[level] = cur; 39093f157a2fSChris Mason path->locks[level] = 1; 39103f157a2fSChris Mason 39113f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 39123f157a2fSChris Mason ret = 1; 39133f157a2fSChris Mason goto out; 39143f157a2fSChris Mason } 39153f157a2fSChris Mason while (1) { 39163f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 39173f157a2fSChris Mason level = btrfs_header_level(cur); 39189652480bSYan sret = bin_search(cur, min_key, level, &slot); 39193f157a2fSChris Mason 3920323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 3921323ac95bSChris Mason if (level == path->lowest_level) { 3922e02119d5SChris Mason if (slot >= nritems) 3923e02119d5SChris Mason goto find_next_key; 39243f157a2fSChris Mason ret = 0; 39253f157a2fSChris Mason path->slots[level] = slot; 39263f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 39273f157a2fSChris Mason goto out; 39283f157a2fSChris Mason } 39299652480bSYan if (sret && slot > 0) 39309652480bSYan slot--; 39313f157a2fSChris Mason /* 39323f157a2fSChris Mason * check this node pointer against the cache_only and 39333f157a2fSChris Mason * min_trans parameters. If it isn't in cache or is too 39343f157a2fSChris Mason * old, skip to the next one. 39353f157a2fSChris Mason */ 39363f157a2fSChris Mason while (slot < nritems) { 39373f157a2fSChris Mason u64 blockptr; 39383f157a2fSChris Mason u64 gen; 39393f157a2fSChris Mason struct extent_buffer *tmp; 3940e02119d5SChris Mason struct btrfs_disk_key disk_key; 3941e02119d5SChris Mason 39423f157a2fSChris Mason blockptr = btrfs_node_blockptr(cur, slot); 39433f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 39443f157a2fSChris Mason if (gen < min_trans) { 39453f157a2fSChris Mason slot++; 39463f157a2fSChris Mason continue; 39473f157a2fSChris Mason } 39483f157a2fSChris Mason if (!cache_only) 39493f157a2fSChris Mason break; 39503f157a2fSChris Mason 3951e02119d5SChris Mason if (max_key) { 3952e02119d5SChris Mason btrfs_node_key(cur, &disk_key, slot); 3953e02119d5SChris Mason if (comp_keys(&disk_key, max_key) >= 0) { 3954e02119d5SChris Mason ret = 1; 3955e02119d5SChris Mason goto out; 3956e02119d5SChris Mason } 3957e02119d5SChris Mason } 3958e02119d5SChris Mason 39593f157a2fSChris Mason tmp = btrfs_find_tree_block(root, blockptr, 39603f157a2fSChris Mason btrfs_level_size(root, level - 1)); 39613f157a2fSChris Mason 39623f157a2fSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 39633f157a2fSChris Mason free_extent_buffer(tmp); 39643f157a2fSChris Mason break; 39653f157a2fSChris Mason } 39663f157a2fSChris Mason if (tmp) 39673f157a2fSChris Mason free_extent_buffer(tmp); 39683f157a2fSChris Mason slot++; 39693f157a2fSChris Mason } 3970e02119d5SChris Mason find_next_key: 39713f157a2fSChris Mason /* 39723f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 39733f157a2fSChris Mason * and find another one 39743f157a2fSChris Mason */ 39753f157a2fSChris Mason if (slot >= nritems) { 3976e02119d5SChris Mason path->slots[level] = slot; 3977b4ce94deSChris Mason btrfs_set_path_blocking(path); 3978e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 39793f157a2fSChris Mason cache_only, min_trans); 3980e02119d5SChris Mason if (sret == 0) { 39813f157a2fSChris Mason btrfs_release_path(root, path); 39823f157a2fSChris Mason goto again; 39833f157a2fSChris Mason } else { 39843f157a2fSChris Mason goto out; 39853f157a2fSChris Mason } 39863f157a2fSChris Mason } 39873f157a2fSChris Mason /* save our key for returning back */ 39883f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 39893f157a2fSChris Mason path->slots[level] = slot; 39903f157a2fSChris Mason if (level == path->lowest_level) { 39913f157a2fSChris Mason ret = 0; 39923f157a2fSChris Mason unlock_up(path, level, 1); 39933f157a2fSChris Mason goto out; 39943f157a2fSChris Mason } 3995b4ce94deSChris Mason btrfs_set_path_blocking(path); 39963f157a2fSChris Mason cur = read_node_slot(root, cur, slot); 39973f157a2fSChris Mason 39983f157a2fSChris Mason btrfs_tree_lock(cur); 3999b4ce94deSChris Mason 40003f157a2fSChris Mason path->locks[level - 1] = 1; 40013f157a2fSChris Mason path->nodes[level - 1] = cur; 40023f157a2fSChris Mason unlock_up(path, level, 1); 40034008c04aSChris Mason btrfs_clear_path_blocking(path, NULL); 40043f157a2fSChris Mason } 40053f157a2fSChris Mason out: 40063f157a2fSChris Mason if (ret == 0) 40073f157a2fSChris Mason memcpy(min_key, &found_key, sizeof(found_key)); 4008b4ce94deSChris Mason btrfs_set_path_blocking(path); 40093f157a2fSChris Mason return ret; 40103f157a2fSChris Mason } 40113f157a2fSChris Mason 40123f157a2fSChris Mason /* 40133f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 40143f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 40153f157a2fSChris Mason * tree based on the current path and the cache_only and min_trans 40163f157a2fSChris Mason * parameters. 40173f157a2fSChris Mason * 40183f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 40193f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 40203f157a2fSChris Mason * 40213f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 40223f157a2fSChris Mason * calling this function. 40233f157a2fSChris Mason */ 4024e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 40253f157a2fSChris Mason struct btrfs_key *key, int lowest_level, 40263f157a2fSChris Mason int cache_only, u64 min_trans) 4027e7a84565SChris Mason { 4028e7a84565SChris Mason int level = lowest_level; 4029e7a84565SChris Mason int slot; 4030e7a84565SChris Mason struct extent_buffer *c; 4031e7a84565SChris Mason 4032934d375bSChris Mason WARN_ON(!path->keep_locks); 4033e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 4034e7a84565SChris Mason if (!path->nodes[level]) 4035e7a84565SChris Mason return 1; 4036e7a84565SChris Mason 4037e7a84565SChris Mason slot = path->slots[level] + 1; 4038e7a84565SChris Mason c = path->nodes[level]; 40393f157a2fSChris Mason next: 4040e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 4041e7a84565SChris Mason level++; 4042d397712bSChris Mason if (level == BTRFS_MAX_LEVEL) 4043e7a84565SChris Mason return 1; 4044e7a84565SChris Mason continue; 4045e7a84565SChris Mason } 4046e7a84565SChris Mason if (level == 0) 4047e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 40483f157a2fSChris Mason else { 40493f157a2fSChris Mason u64 blockptr = btrfs_node_blockptr(c, slot); 40503f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 40513f157a2fSChris Mason 40523f157a2fSChris Mason if (cache_only) { 40533f157a2fSChris Mason struct extent_buffer *cur; 40543f157a2fSChris Mason cur = btrfs_find_tree_block(root, blockptr, 40553f157a2fSChris Mason btrfs_level_size(root, level - 1)); 40563f157a2fSChris Mason if (!cur || !btrfs_buffer_uptodate(cur, gen)) { 40573f157a2fSChris Mason slot++; 40583f157a2fSChris Mason if (cur) 40593f157a2fSChris Mason free_extent_buffer(cur); 40603f157a2fSChris Mason goto next; 40613f157a2fSChris Mason } 40623f157a2fSChris Mason free_extent_buffer(cur); 40633f157a2fSChris Mason } 40643f157a2fSChris Mason if (gen < min_trans) { 40653f157a2fSChris Mason slot++; 40663f157a2fSChris Mason goto next; 40673f157a2fSChris Mason } 4068e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 40693f157a2fSChris Mason } 4070e7a84565SChris Mason return 0; 4071e7a84565SChris Mason } 4072e7a84565SChris Mason return 1; 4073e7a84565SChris Mason } 4074e7a84565SChris Mason 40757bb86316SChris Mason /* 4076925baeddSChris Mason * search the tree again to find a leaf with greater keys 40770f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 40780f70abe2SChris Mason * returns < 0 on io errors. 407997571fd0SChris Mason */ 4080234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 4081d97e63b6SChris Mason { 4082d97e63b6SChris Mason int slot; 4083d97e63b6SChris Mason int level = 1; 40845f39d397SChris Mason struct extent_buffer *c; 40855f39d397SChris Mason struct extent_buffer *next = NULL; 4086925baeddSChris Mason struct btrfs_key key; 4087925baeddSChris Mason u32 nritems; 4088925baeddSChris Mason int ret; 4089925baeddSChris Mason 4090925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4091d397712bSChris Mason if (nritems == 0) 4092925baeddSChris Mason return 1; 4093925baeddSChris Mason 4094925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 4095925baeddSChris Mason 4096925baeddSChris Mason btrfs_release_path(root, path); 4097a2135011SChris Mason path->keep_locks = 1; 4098925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4099925baeddSChris Mason path->keep_locks = 0; 4100925baeddSChris Mason 4101925baeddSChris Mason if (ret < 0) 4102925baeddSChris Mason return ret; 4103925baeddSChris Mason 4104b4ce94deSChris Mason btrfs_set_path_blocking(path); 4105a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4106168fd7d2SChris Mason /* 4107168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 4108168fd7d2SChris Mason * could have added more items next to the key that used to be 4109168fd7d2SChris Mason * at the very end of the block. So, check again here and 4110168fd7d2SChris Mason * advance the path if there are now more items available. 4111168fd7d2SChris Mason */ 4112a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 4113168fd7d2SChris Mason path->slots[0]++; 4114925baeddSChris Mason goto done; 4115925baeddSChris Mason } 4116d97e63b6SChris Mason 4117234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 4118d97e63b6SChris Mason if (!path->nodes[level]) 41190f70abe2SChris Mason return 1; 41205f39d397SChris Mason 4121d97e63b6SChris Mason slot = path->slots[level] + 1; 4122d97e63b6SChris Mason c = path->nodes[level]; 41235f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 4124d97e63b6SChris Mason level++; 4125d397712bSChris Mason if (level == BTRFS_MAX_LEVEL) 41267bb86316SChris Mason return 1; 4127d97e63b6SChris Mason continue; 4128d97e63b6SChris Mason } 41295f39d397SChris Mason 4130925baeddSChris Mason if (next) { 4131925baeddSChris Mason btrfs_tree_unlock(next); 41325f39d397SChris Mason free_extent_buffer(next); 4133925baeddSChris Mason } 41345f39d397SChris Mason 4135b4ce94deSChris Mason /* the path was set to blocking above */ 41360bd40a71SChris Mason if (level == 1 && (path->locks[1] || path->skip_locking) && 41370bd40a71SChris Mason path->reada) 413801f46658SChris Mason reada_for_search(root, path, level, slot, 0); 41395f39d397SChris Mason 4140ca7a79adSChris Mason next = read_node_slot(root, c, slot); 41415cd57b2cSChris Mason if (!path->skip_locking) { 4142b9447ef8SChris Mason btrfs_assert_tree_locked(c); 4143925baeddSChris Mason btrfs_tree_lock(next); 4144b4ce94deSChris Mason btrfs_set_lock_blocking(next); 41455cd57b2cSChris Mason } 4146d97e63b6SChris Mason break; 4147d97e63b6SChris Mason } 4148d97e63b6SChris Mason path->slots[level] = slot; 4149d97e63b6SChris Mason while (1) { 4150d97e63b6SChris Mason level--; 4151d97e63b6SChris Mason c = path->nodes[level]; 4152925baeddSChris Mason if (path->locks[level]) 4153925baeddSChris Mason btrfs_tree_unlock(c); 41545f39d397SChris Mason free_extent_buffer(c); 4155d97e63b6SChris Mason path->nodes[level] = next; 4156d97e63b6SChris Mason path->slots[level] = 0; 4157a74a4b97SChris Mason if (!path->skip_locking) 4158925baeddSChris Mason path->locks[level] = 1; 4159d97e63b6SChris Mason if (!level) 4160d97e63b6SChris Mason break; 4161b4ce94deSChris Mason 4162b4ce94deSChris Mason btrfs_set_path_blocking(path); 4163925baeddSChris Mason if (level == 1 && path->locks[1] && path->reada) 4164925baeddSChris Mason reada_for_search(root, path, level, slot, 0); 4165ca7a79adSChris Mason next = read_node_slot(root, next, 0); 41665cd57b2cSChris Mason if (!path->skip_locking) { 4167b9447ef8SChris Mason btrfs_assert_tree_locked(path->nodes[level]); 4168925baeddSChris Mason btrfs_tree_lock(next); 4169b4ce94deSChris Mason btrfs_set_lock_blocking(next); 4170d97e63b6SChris Mason } 41715cd57b2cSChris Mason } 4172925baeddSChris Mason done: 4173925baeddSChris Mason unlock_up(path, 0, 1); 4174d97e63b6SChris Mason return 0; 4175d97e63b6SChris Mason } 41760b86a832SChris Mason 41773f157a2fSChris Mason /* 41783f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 41793f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 41803f157a2fSChris Mason * 41813f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 41823f157a2fSChris Mason */ 41830b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 41840b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 41850b86a832SChris Mason int type) 41860b86a832SChris Mason { 41870b86a832SChris Mason struct btrfs_key found_key; 41880b86a832SChris Mason struct extent_buffer *leaf; 4189e02119d5SChris Mason u32 nritems; 41900b86a832SChris Mason int ret; 41910b86a832SChris Mason 41920b86a832SChris Mason while (1) { 41930b86a832SChris Mason if (path->slots[0] == 0) { 4194b4ce94deSChris Mason btrfs_set_path_blocking(path); 41950b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 41960b86a832SChris Mason if (ret != 0) 41970b86a832SChris Mason return ret; 41980b86a832SChris Mason } else { 41990b86a832SChris Mason path->slots[0]--; 42000b86a832SChris Mason } 42010b86a832SChris Mason leaf = path->nodes[0]; 4202e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 4203e02119d5SChris Mason if (nritems == 0) 4204e02119d5SChris Mason return 1; 4205e02119d5SChris Mason if (path->slots[0] == nritems) 4206e02119d5SChris Mason path->slots[0]--; 4207e02119d5SChris Mason 42080b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 42090b86a832SChris Mason if (found_key.type == type) 42100b86a832SChris Mason return 0; 4211e02119d5SChris Mason if (found_key.objectid < min_objectid) 4212e02119d5SChris Mason break; 4213e02119d5SChris Mason if (found_key.objectid == min_objectid && 4214e02119d5SChris Mason found_key.type < type) 4215e02119d5SChris Mason break; 42160b86a832SChris Mason } 42170b86a832SChris Mason return 1; 42180b86a832SChris Mason } 4219