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> 205a0e3ad6STejun Heo #include <linux/slab.h> 21eb60ceacSChris Mason #include "ctree.h" 22eb60ceacSChris Mason #include "disk-io.h" 237f5c1516SChris Mason #include "transaction.h" 245f39d397SChris Mason #include "print-tree.h" 25925baeddSChris Mason #include "locking.h" 269a8dd150SChris Mason 27e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 28e089f05cSChris Mason *root, struct btrfs_path *path, int level); 29e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 30d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 31cc0c5538SChris Mason struct btrfs_path *path, int data_size, int extend); 325f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 335f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 34971a1f66SChris Mason struct extent_buffer *src, int empty); 355f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 365f39d397SChris Mason struct btrfs_root *root, 375f39d397SChris Mason struct extent_buffer *dst_buf, 385f39d397SChris Mason struct extent_buffer *src_buf); 39143bede5SJeff Mahoney static void del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 40e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 41d97e63b6SChris Mason 422c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 432c90e5d6SChris Mason { 44df24a2b9SChris Mason struct btrfs_path *path; 45e00f7308SJeff Mahoney path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 46df24a2b9SChris Mason return path; 472c90e5d6SChris Mason } 482c90e5d6SChris Mason 49b4ce94deSChris Mason /* 50b4ce94deSChris Mason * set all locked nodes in the path to blocking locks. This should 51b4ce94deSChris Mason * be done before scheduling 52b4ce94deSChris Mason */ 53b4ce94deSChris Mason noinline void btrfs_set_path_blocking(struct btrfs_path *p) 54b4ce94deSChris Mason { 55b4ce94deSChris Mason int i; 56b4ce94deSChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 57bd681513SChris Mason if (!p->nodes[i] || !p->locks[i]) 58bd681513SChris Mason continue; 59bd681513SChris Mason btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]); 60bd681513SChris Mason if (p->locks[i] == BTRFS_READ_LOCK) 61bd681513SChris Mason p->locks[i] = BTRFS_READ_LOCK_BLOCKING; 62bd681513SChris Mason else if (p->locks[i] == BTRFS_WRITE_LOCK) 63bd681513SChris Mason p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING; 64b4ce94deSChris Mason } 65b4ce94deSChris Mason } 66b4ce94deSChris Mason 67b4ce94deSChris Mason /* 68b4ce94deSChris Mason * reset all the locked nodes in the patch to spinning locks. 694008c04aSChris Mason * 704008c04aSChris Mason * held is used to keep lockdep happy, when lockdep is enabled 714008c04aSChris Mason * we set held to a blocking lock before we go around and 724008c04aSChris Mason * retake all the spinlocks in the path. You can safely use NULL 734008c04aSChris Mason * for held 74b4ce94deSChris Mason */ 754008c04aSChris Mason noinline void btrfs_clear_path_blocking(struct btrfs_path *p, 76bd681513SChris Mason struct extent_buffer *held, int held_rw) 77b4ce94deSChris Mason { 78b4ce94deSChris Mason int i; 794008c04aSChris Mason 804008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 814008c04aSChris Mason /* lockdep really cares that we take all of these spinlocks 824008c04aSChris Mason * in the right order. If any of the locks in the path are not 834008c04aSChris Mason * currently blocking, it is going to complain. So, make really 844008c04aSChris Mason * really sure by forcing the path to blocking before we clear 854008c04aSChris Mason * the path blocking. 864008c04aSChris Mason */ 87bd681513SChris Mason if (held) { 88bd681513SChris Mason btrfs_set_lock_blocking_rw(held, held_rw); 89bd681513SChris Mason if (held_rw == BTRFS_WRITE_LOCK) 90bd681513SChris Mason held_rw = BTRFS_WRITE_LOCK_BLOCKING; 91bd681513SChris Mason else if (held_rw == BTRFS_READ_LOCK) 92bd681513SChris Mason held_rw = BTRFS_READ_LOCK_BLOCKING; 93bd681513SChris Mason } 944008c04aSChris Mason btrfs_set_path_blocking(p); 954008c04aSChris Mason #endif 964008c04aSChris Mason 974008c04aSChris Mason for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) { 98bd681513SChris Mason if (p->nodes[i] && p->locks[i]) { 99bd681513SChris Mason btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]); 100bd681513SChris Mason if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING) 101bd681513SChris Mason p->locks[i] = BTRFS_WRITE_LOCK; 102bd681513SChris Mason else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING) 103bd681513SChris Mason p->locks[i] = BTRFS_READ_LOCK; 104bd681513SChris Mason } 105b4ce94deSChris Mason } 1064008c04aSChris Mason 1074008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 1084008c04aSChris Mason if (held) 109bd681513SChris Mason btrfs_clear_lock_blocking_rw(held, held_rw); 1104008c04aSChris Mason #endif 111b4ce94deSChris Mason } 112b4ce94deSChris Mason 113d352ac68SChris Mason /* this also releases the path */ 1142c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 1152c90e5d6SChris Mason { 116ff175d57SJesper Juhl if (!p) 117ff175d57SJesper Juhl return; 118b3b4aa74SDavid Sterba btrfs_release_path(p); 1192c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 1202c90e5d6SChris Mason } 1212c90e5d6SChris Mason 122d352ac68SChris Mason /* 123d352ac68SChris Mason * path release drops references on the extent buffers in the path 124d352ac68SChris Mason * and it drops any locks held by this path 125d352ac68SChris Mason * 126d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 127d352ac68SChris Mason */ 128b3b4aa74SDavid Sterba noinline void btrfs_release_path(struct btrfs_path *p) 129eb60ceacSChris Mason { 130eb60ceacSChris Mason int i; 131a2135011SChris Mason 132234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 1333f157a2fSChris Mason p->slots[i] = 0; 134eb60ceacSChris Mason if (!p->nodes[i]) 135925baeddSChris Mason continue; 136925baeddSChris Mason if (p->locks[i]) { 137bd681513SChris Mason btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]); 138925baeddSChris Mason p->locks[i] = 0; 139925baeddSChris Mason } 1405f39d397SChris Mason free_extent_buffer(p->nodes[i]); 1413f157a2fSChris Mason p->nodes[i] = NULL; 142eb60ceacSChris Mason } 143eb60ceacSChris Mason } 144eb60ceacSChris Mason 145d352ac68SChris Mason /* 146d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 147d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 148d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 149d352ac68SChris Mason * looping required. 150d352ac68SChris Mason * 151d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 152d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 153d352ac68SChris Mason * at any time because there are no locks held. 154d352ac68SChris Mason */ 155925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 156925baeddSChris Mason { 157925baeddSChris Mason struct extent_buffer *eb; 158240f62c8SChris Mason 159240f62c8SChris Mason rcu_read_lock(); 160240f62c8SChris Mason eb = rcu_dereference(root->node); 161925baeddSChris Mason extent_buffer_get(eb); 162240f62c8SChris Mason rcu_read_unlock(); 163925baeddSChris Mason return eb; 164925baeddSChris Mason } 165925baeddSChris Mason 166d352ac68SChris Mason /* loop around taking references on and locking the root node of the 167d352ac68SChris Mason * tree until you end up with a lock on the root. A locked buffer 168d352ac68SChris Mason * is returned, with a reference held. 169d352ac68SChris Mason */ 170925baeddSChris Mason struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root) 171925baeddSChris Mason { 172925baeddSChris Mason struct extent_buffer *eb; 173925baeddSChris Mason 174925baeddSChris Mason while (1) { 175925baeddSChris Mason eb = btrfs_root_node(root); 176925baeddSChris Mason btrfs_tree_lock(eb); 177240f62c8SChris Mason if (eb == root->node) 178925baeddSChris Mason break; 179925baeddSChris Mason btrfs_tree_unlock(eb); 180925baeddSChris Mason free_extent_buffer(eb); 181925baeddSChris Mason } 182925baeddSChris Mason return eb; 183925baeddSChris Mason } 184925baeddSChris Mason 185bd681513SChris Mason /* loop around taking references on and locking the root node of the 186bd681513SChris Mason * tree until you end up with a lock on the root. A locked buffer 187bd681513SChris Mason * is returned, with a reference held. 188bd681513SChris Mason */ 189bd681513SChris Mason struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root) 190bd681513SChris Mason { 191bd681513SChris Mason struct extent_buffer *eb; 192bd681513SChris Mason 193bd681513SChris Mason while (1) { 194bd681513SChris Mason eb = btrfs_root_node(root); 195bd681513SChris Mason btrfs_tree_read_lock(eb); 196bd681513SChris Mason if (eb == root->node) 197bd681513SChris Mason break; 198bd681513SChris Mason btrfs_tree_read_unlock(eb); 199bd681513SChris Mason free_extent_buffer(eb); 200bd681513SChris Mason } 201bd681513SChris Mason return eb; 202bd681513SChris Mason } 203bd681513SChris Mason 204d352ac68SChris Mason /* cowonly root (everything not a reference counted cow subvolume), just get 205d352ac68SChris Mason * put onto a simple dirty list. transaction.c walks this to make sure they 206d352ac68SChris Mason * get properly updated on disk. 207d352ac68SChris Mason */ 2080b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 2090b86a832SChris Mason { 2100b86a832SChris Mason if (root->track_dirty && list_empty(&root->dirty_list)) { 2110b86a832SChris Mason list_add(&root->dirty_list, 2120b86a832SChris Mason &root->fs_info->dirty_cowonly_roots); 2130b86a832SChris Mason } 2140b86a832SChris Mason } 2150b86a832SChris Mason 216d352ac68SChris Mason /* 217d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 218d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 219d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 220d352ac68SChris Mason */ 221be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 222be20aa9dSChris Mason struct btrfs_root *root, 223be20aa9dSChris Mason struct extent_buffer *buf, 224be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 225be20aa9dSChris Mason { 226be20aa9dSChris Mason struct extent_buffer *cow; 227be20aa9dSChris Mason int ret = 0; 228be20aa9dSChris Mason int level; 2295d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 230be20aa9dSChris Mason 231be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != 232be20aa9dSChris Mason root->fs_info->running_transaction->transid); 233be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 234be20aa9dSChris Mason 235be20aa9dSChris Mason level = btrfs_header_level(buf); 2365d4f98a2SYan Zheng if (level == 0) 2375d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 2385d4f98a2SYan Zheng else 2395d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 24031840ae1SZheng Yan 2415d4f98a2SYan Zheng cow = btrfs_alloc_free_block(trans, root, buf->len, 0, 2425d4f98a2SYan Zheng new_root_objectid, &disk_key, level, 24366d7e7f0SArne Jansen buf->start, 0, 1); 2445d4f98a2SYan Zheng if (IS_ERR(cow)) 245be20aa9dSChris Mason return PTR_ERR(cow); 246be20aa9dSChris Mason 247be20aa9dSChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 248be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 249be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 2505d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 2515d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 2525d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 2535d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 2545d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 2555d4f98a2SYan Zheng else 256be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 257be20aa9dSChris Mason 2582b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 2592b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 2602b82032cSYan Zheng BTRFS_FSID_SIZE); 2612b82032cSYan Zheng 262be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 2635d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 26466d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 2655d4f98a2SYan Zheng else 26666d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 0, 1); 2674aec2b52SChris Mason 268be20aa9dSChris Mason if (ret) 269be20aa9dSChris Mason return ret; 270be20aa9dSChris Mason 271be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 272be20aa9dSChris Mason *cow_ret = cow; 273be20aa9dSChris Mason return 0; 274be20aa9dSChris Mason } 275be20aa9dSChris Mason 276d352ac68SChris Mason /* 2775d4f98a2SYan Zheng * check if the tree block can be shared by multiple trees 2785d4f98a2SYan Zheng */ 2795d4f98a2SYan Zheng int btrfs_block_can_be_shared(struct btrfs_root *root, 2805d4f98a2SYan Zheng struct extent_buffer *buf) 2815d4f98a2SYan Zheng { 2825d4f98a2SYan Zheng /* 2835d4f98a2SYan Zheng * Tree blocks not in refernece counted trees and tree roots 2845d4f98a2SYan Zheng * are never shared. If a block was allocated after the last 2855d4f98a2SYan Zheng * snapshot and the block was not allocated by tree relocation, 2865d4f98a2SYan Zheng * we know the block is not shared. 2875d4f98a2SYan Zheng */ 2885d4f98a2SYan Zheng if (root->ref_cows && 2895d4f98a2SYan Zheng buf != root->node && buf != root->commit_root && 2905d4f98a2SYan Zheng (btrfs_header_generation(buf) <= 2915d4f98a2SYan Zheng btrfs_root_last_snapshot(&root->root_item) || 2925d4f98a2SYan Zheng btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 2935d4f98a2SYan Zheng return 1; 2945d4f98a2SYan Zheng #ifdef BTRFS_COMPAT_EXTENT_TREE_V0 2955d4f98a2SYan Zheng if (root->ref_cows && 2965d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 2975d4f98a2SYan Zheng return 1; 2985d4f98a2SYan Zheng #endif 2995d4f98a2SYan Zheng return 0; 3005d4f98a2SYan Zheng } 3015d4f98a2SYan Zheng 3025d4f98a2SYan Zheng static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans, 3035d4f98a2SYan Zheng struct btrfs_root *root, 3045d4f98a2SYan Zheng struct extent_buffer *buf, 305f0486c68SYan, Zheng struct extent_buffer *cow, 306f0486c68SYan, Zheng int *last_ref) 3075d4f98a2SYan Zheng { 3085d4f98a2SYan Zheng u64 refs; 3095d4f98a2SYan Zheng u64 owner; 3105d4f98a2SYan Zheng u64 flags; 3115d4f98a2SYan Zheng u64 new_flags = 0; 3125d4f98a2SYan Zheng int ret; 3135d4f98a2SYan Zheng 3145d4f98a2SYan Zheng /* 3155d4f98a2SYan Zheng * Backrefs update rules: 3165d4f98a2SYan Zheng * 3175d4f98a2SYan Zheng * Always use full backrefs for extent pointers in tree block 3185d4f98a2SYan Zheng * allocated by tree relocation. 3195d4f98a2SYan Zheng * 3205d4f98a2SYan Zheng * If a shared tree block is no longer referenced by its owner 3215d4f98a2SYan Zheng * tree (btrfs_header_owner(buf) == root->root_key.objectid), 3225d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 3235d4f98a2SYan Zheng * 3245d4f98a2SYan Zheng * If a tree block is been relocating 3255d4f98a2SYan Zheng * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID), 3265d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 3275d4f98a2SYan Zheng * The reason for this is some operations (such as drop tree) 3285d4f98a2SYan Zheng * are only allowed for blocks use full backrefs. 3295d4f98a2SYan Zheng */ 3305d4f98a2SYan Zheng 3315d4f98a2SYan Zheng if (btrfs_block_can_be_shared(root, buf)) { 3325d4f98a2SYan Zheng ret = btrfs_lookup_extent_info(trans, root, buf->start, 3335d4f98a2SYan Zheng buf->len, &refs, &flags); 334be1a5564SMark Fasheh if (ret) 335be1a5564SMark Fasheh return ret; 336e5df9573SMark Fasheh if (refs == 0) { 337e5df9573SMark Fasheh ret = -EROFS; 338e5df9573SMark Fasheh btrfs_std_error(root->fs_info, ret); 339e5df9573SMark Fasheh return ret; 340e5df9573SMark Fasheh } 3415d4f98a2SYan Zheng } else { 3425d4f98a2SYan Zheng refs = 1; 3435d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 3445d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 3455d4f98a2SYan Zheng flags = BTRFS_BLOCK_FLAG_FULL_BACKREF; 3465d4f98a2SYan Zheng else 3475d4f98a2SYan Zheng flags = 0; 3485d4f98a2SYan Zheng } 3495d4f98a2SYan Zheng 3505d4f98a2SYan Zheng owner = btrfs_header_owner(buf); 3515d4f98a2SYan Zheng BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID && 3525d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)); 3535d4f98a2SYan Zheng 3545d4f98a2SYan Zheng if (refs > 1) { 3555d4f98a2SYan Zheng if ((owner == root->root_key.objectid || 3565d4f98a2SYan Zheng root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && 3575d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 35866d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, buf, 1, 1); 3595d4f98a2SYan Zheng BUG_ON(ret); 3605d4f98a2SYan Zheng 3615d4f98a2SYan Zheng if (root->root_key.objectid == 3625d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 36366d7e7f0SArne Jansen ret = btrfs_dec_ref(trans, root, buf, 0, 1); 3645d4f98a2SYan Zheng BUG_ON(ret); 36566d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 3665d4f98a2SYan Zheng BUG_ON(ret); 3675d4f98a2SYan Zheng } 3685d4f98a2SYan Zheng new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; 3695d4f98a2SYan Zheng } else { 3705d4f98a2SYan Zheng 3715d4f98a2SYan Zheng if (root->root_key.objectid == 3725d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 37366d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 3745d4f98a2SYan Zheng else 37566d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 0, 1); 3765d4f98a2SYan Zheng BUG_ON(ret); 3775d4f98a2SYan Zheng } 3785d4f98a2SYan Zheng if (new_flags != 0) { 3795d4f98a2SYan Zheng ret = btrfs_set_disk_extent_flags(trans, root, 3805d4f98a2SYan Zheng buf->start, 3815d4f98a2SYan Zheng buf->len, 3825d4f98a2SYan Zheng new_flags, 0); 383be1a5564SMark Fasheh if (ret) 384be1a5564SMark Fasheh return ret; 3855d4f98a2SYan Zheng } 3865d4f98a2SYan Zheng } else { 3875d4f98a2SYan Zheng if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { 3885d4f98a2SYan Zheng if (root->root_key.objectid == 3895d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 39066d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 3915d4f98a2SYan Zheng else 39266d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 0, 1); 3935d4f98a2SYan Zheng BUG_ON(ret); 39466d7e7f0SArne Jansen ret = btrfs_dec_ref(trans, root, buf, 1, 1); 3955d4f98a2SYan Zheng BUG_ON(ret); 3965d4f98a2SYan Zheng } 3975d4f98a2SYan Zheng clean_tree_block(trans, root, buf); 398f0486c68SYan, Zheng *last_ref = 1; 3995d4f98a2SYan Zheng } 4005d4f98a2SYan Zheng return 0; 4015d4f98a2SYan Zheng } 4025d4f98a2SYan Zheng 4035d4f98a2SYan Zheng /* 404d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 405d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 406d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 407d397712bSChris Mason * dirty again. 408d352ac68SChris Mason * 409d352ac68SChris Mason * search_start -- an allocation hint for the new block 410d352ac68SChris Mason * 411d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 412d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 413d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 414d352ac68SChris Mason */ 415d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 4165f39d397SChris Mason struct btrfs_root *root, 4175f39d397SChris Mason struct extent_buffer *buf, 4185f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 4195f39d397SChris Mason struct extent_buffer **cow_ret, 4209fa8cfe7SChris Mason u64 search_start, u64 empty_size) 4216702ed49SChris Mason { 4225d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 4235f39d397SChris Mason struct extent_buffer *cow; 424be1a5564SMark Fasheh int level, ret; 425f0486c68SYan, Zheng int last_ref = 0; 426925baeddSChris Mason int unlock_orig = 0; 4275d4f98a2SYan Zheng u64 parent_start; 4286702ed49SChris Mason 429925baeddSChris Mason if (*cow_ret == buf) 430925baeddSChris Mason unlock_orig = 1; 431925baeddSChris Mason 432b9447ef8SChris Mason btrfs_assert_tree_locked(buf); 433925baeddSChris Mason 4347bb86316SChris Mason WARN_ON(root->ref_cows && trans->transid != 4357bb86316SChris Mason root->fs_info->running_transaction->transid); 4366702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 4375f39d397SChris Mason 4387bb86316SChris Mason level = btrfs_header_level(buf); 43931840ae1SZheng Yan 4405d4f98a2SYan Zheng if (level == 0) 4415d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 4425d4f98a2SYan Zheng else 4435d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 4445d4f98a2SYan Zheng 4455d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) { 4465d4f98a2SYan Zheng if (parent) 4475d4f98a2SYan Zheng parent_start = parent->start; 4485d4f98a2SYan Zheng else 4495d4f98a2SYan Zheng parent_start = 0; 4505d4f98a2SYan Zheng } else 4515d4f98a2SYan Zheng parent_start = 0; 4525d4f98a2SYan Zheng 4535d4f98a2SYan Zheng cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start, 4545d4f98a2SYan Zheng root->root_key.objectid, &disk_key, 45566d7e7f0SArne Jansen level, search_start, empty_size, 1); 4566702ed49SChris Mason if (IS_ERR(cow)) 4576702ed49SChris Mason return PTR_ERR(cow); 4586702ed49SChris Mason 459b4ce94deSChris Mason /* cow is set to blocking by btrfs_init_new_buffer */ 460b4ce94deSChris Mason 4615f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 462db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 4635f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 4645d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 4655d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 4665d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 4675d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 4685d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 4695d4f98a2SYan Zheng else 4705f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 4716702ed49SChris Mason 4722b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 4732b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 4742b82032cSYan Zheng BTRFS_FSID_SIZE); 4752b82032cSYan Zheng 476be1a5564SMark Fasheh ret = update_ref_for_cow(trans, root, buf, cow, &last_ref); 477b68dc2a9SMark Fasheh if (ret) { 478b68dc2a9SMark Fasheh btrfs_std_error(root->fs_info, ret); 479b68dc2a9SMark Fasheh return ret; 480b68dc2a9SMark Fasheh } 4811a40e23bSZheng Yan 4823fd0a558SYan, Zheng if (root->ref_cows) 4833fd0a558SYan, Zheng btrfs_reloc_cow_block(trans, root, buf, cow); 4843fd0a558SYan, Zheng 4856702ed49SChris Mason if (buf == root->node) { 486925baeddSChris Mason WARN_ON(parent && parent != buf); 4875d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 4885d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 4895d4f98a2SYan Zheng parent_start = buf->start; 4905d4f98a2SYan Zheng else 4915d4f98a2SYan Zheng parent_start = 0; 492925baeddSChris Mason 4935f39d397SChris Mason extent_buffer_get(cow); 494240f62c8SChris Mason rcu_assign_pointer(root->node, cow); 495925baeddSChris Mason 496f0486c68SYan, Zheng btrfs_free_tree_block(trans, root, buf, parent_start, 49766d7e7f0SArne Jansen last_ref, 1); 4985f39d397SChris Mason free_extent_buffer(buf); 4990b86a832SChris Mason add_root_to_dirty_list(root); 5006702ed49SChris Mason } else { 5015d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 5025d4f98a2SYan Zheng parent_start = parent->start; 5035d4f98a2SYan Zheng else 5045d4f98a2SYan Zheng parent_start = 0; 5055d4f98a2SYan Zheng 5065d4f98a2SYan Zheng WARN_ON(trans->transid != btrfs_header_generation(parent)); 5075f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 508db94535dSChris Mason cow->start); 50974493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 51074493f7aSChris Mason trans->transid); 5116702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 512f0486c68SYan, Zheng btrfs_free_tree_block(trans, root, buf, parent_start, 51366d7e7f0SArne Jansen last_ref, 1); 5146702ed49SChris Mason } 515925baeddSChris Mason if (unlock_orig) 516925baeddSChris Mason btrfs_tree_unlock(buf); 5175f39d397SChris Mason free_extent_buffer(buf); 5186702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 5196702ed49SChris Mason *cow_ret = cow; 5206702ed49SChris Mason return 0; 5216702ed49SChris Mason } 5226702ed49SChris Mason 5235d4f98a2SYan Zheng static inline int should_cow_block(struct btrfs_trans_handle *trans, 5245d4f98a2SYan Zheng struct btrfs_root *root, 5255d4f98a2SYan Zheng struct extent_buffer *buf) 5265d4f98a2SYan Zheng { 527f1ebcc74SLiu Bo /* ensure we can see the force_cow */ 528f1ebcc74SLiu Bo smp_rmb(); 529f1ebcc74SLiu Bo 530f1ebcc74SLiu Bo /* 531f1ebcc74SLiu Bo * We do not need to cow a block if 532f1ebcc74SLiu Bo * 1) this block is not created or changed in this transaction; 533f1ebcc74SLiu Bo * 2) this block does not belong to TREE_RELOC tree; 534f1ebcc74SLiu Bo * 3) the root is not forced COW. 535f1ebcc74SLiu Bo * 536f1ebcc74SLiu Bo * What is forced COW: 537f1ebcc74SLiu Bo * when we create snapshot during commiting the transaction, 538f1ebcc74SLiu Bo * after we've finished coping src root, we must COW the shared 539f1ebcc74SLiu Bo * block to ensure the metadata consistency. 540f1ebcc74SLiu Bo */ 5415d4f98a2SYan Zheng if (btrfs_header_generation(buf) == trans->transid && 5425d4f98a2SYan Zheng !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) && 5435d4f98a2SYan Zheng !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID && 544f1ebcc74SLiu Bo btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) && 545f1ebcc74SLiu Bo !root->force_cow) 5465d4f98a2SYan Zheng return 0; 5475d4f98a2SYan Zheng return 1; 5485d4f98a2SYan Zheng } 5495d4f98a2SYan Zheng 550d352ac68SChris Mason /* 551d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 552d352ac68SChris Mason * This version of it has extra checks so that a block isn't cow'd more than 553d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 554d352ac68SChris Mason */ 555d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 5565f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 5575f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 5589fa8cfe7SChris Mason struct extent_buffer **cow_ret) 55902217ed2SChris Mason { 5606702ed49SChris Mason u64 search_start; 561f510cfecSChris Mason int ret; 562dc17ff8fSChris Mason 563ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 564d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 565d397712bSChris Mason (unsigned long long)trans->transid, 566d397712bSChris Mason (unsigned long long) 567ccd467d6SChris Mason root->fs_info->running_transaction->transid); 568ccd467d6SChris Mason WARN_ON(1); 569ccd467d6SChris Mason } 570ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 571d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 572d397712bSChris Mason (unsigned long long)trans->transid, 573d397712bSChris Mason (unsigned long long)root->fs_info->generation); 574ccd467d6SChris Mason WARN_ON(1); 575ccd467d6SChris Mason } 576dc17ff8fSChris Mason 5775d4f98a2SYan Zheng if (!should_cow_block(trans, root, buf)) { 57802217ed2SChris Mason *cow_ret = buf; 57902217ed2SChris Mason return 0; 58002217ed2SChris Mason } 581c487685dSChris Mason 5820b86a832SChris Mason search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); 583b4ce94deSChris Mason 584b4ce94deSChris Mason if (parent) 585b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 586b4ce94deSChris Mason btrfs_set_lock_blocking(buf); 587b4ce94deSChris Mason 588f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 5899fa8cfe7SChris Mason parent_slot, cow_ret, search_start, 0); 5901abe9b8aSliubo 5911abe9b8aSliubo trace_btrfs_cow_block(root, buf, *cow_ret); 5921abe9b8aSliubo 593f510cfecSChris Mason return ret; 5942c90e5d6SChris Mason } 5956702ed49SChris Mason 596d352ac68SChris Mason /* 597d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 598d352ac68SChris Mason * node are actually close by 599d352ac68SChris Mason */ 6006b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 6016702ed49SChris Mason { 6026b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 6036702ed49SChris Mason return 1; 6046b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 6056702ed49SChris Mason return 1; 60602217ed2SChris Mason return 0; 60702217ed2SChris Mason } 60802217ed2SChris Mason 609081e9573SChris Mason /* 610081e9573SChris Mason * compare two keys in a memcmp fashion 611081e9573SChris Mason */ 612081e9573SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 613081e9573SChris Mason { 614081e9573SChris Mason struct btrfs_key k1; 615081e9573SChris Mason 616081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 617081e9573SChris Mason 61820736abaSDiego Calleja return btrfs_comp_cpu_keys(&k1, k2); 619081e9573SChris Mason } 620081e9573SChris Mason 621f3465ca4SJosef Bacik /* 622f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 623f3465ca4SJosef Bacik */ 6245d4f98a2SYan Zheng int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2) 625f3465ca4SJosef Bacik { 626f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 627f3465ca4SJosef Bacik return 1; 628f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 629f3465ca4SJosef Bacik return -1; 630f3465ca4SJosef Bacik if (k1->type > k2->type) 631f3465ca4SJosef Bacik return 1; 632f3465ca4SJosef Bacik if (k1->type < k2->type) 633f3465ca4SJosef Bacik return -1; 634f3465ca4SJosef Bacik if (k1->offset > k2->offset) 635f3465ca4SJosef Bacik return 1; 636f3465ca4SJosef Bacik if (k1->offset < k2->offset) 637f3465ca4SJosef Bacik return -1; 638f3465ca4SJosef Bacik return 0; 639f3465ca4SJosef Bacik } 640081e9573SChris Mason 641d352ac68SChris Mason /* 642d352ac68SChris Mason * this is used by the defrag code to go through all the 643d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 644d352ac68SChris Mason * disk order is close to key order 645d352ac68SChris Mason */ 6466702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 6475f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 648a6b6e75eSChris Mason int start_slot, int cache_only, u64 *last_ret, 649a6b6e75eSChris Mason struct btrfs_key *progress) 6506702ed49SChris Mason { 6516b80053dSChris Mason struct extent_buffer *cur; 6526702ed49SChris Mason u64 blocknr; 653ca7a79adSChris Mason u64 gen; 654e9d0b13bSChris Mason u64 search_start = *last_ret; 655e9d0b13bSChris Mason u64 last_block = 0; 6566702ed49SChris Mason u64 other; 6576702ed49SChris Mason u32 parent_nritems; 6586702ed49SChris Mason int end_slot; 6596702ed49SChris Mason int i; 6606702ed49SChris Mason int err = 0; 661f2183bdeSChris Mason int parent_level; 6626b80053dSChris Mason int uptodate; 6636b80053dSChris Mason u32 blocksize; 664081e9573SChris Mason int progress_passed = 0; 665081e9573SChris Mason struct btrfs_disk_key disk_key; 6666702ed49SChris Mason 6675708b959SChris Mason parent_level = btrfs_header_level(parent); 6685708b959SChris Mason if (cache_only && parent_level != 1) 6695708b959SChris Mason return 0; 6705708b959SChris Mason 671d397712bSChris Mason if (trans->transaction != root->fs_info->running_transaction) 6726702ed49SChris Mason WARN_ON(1); 673d397712bSChris Mason if (trans->transid != root->fs_info->generation) 6746702ed49SChris Mason WARN_ON(1); 67586479a04SChris Mason 6766b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 6776b80053dSChris Mason blocksize = btrfs_level_size(root, parent_level - 1); 6786702ed49SChris Mason end_slot = parent_nritems; 6796702ed49SChris Mason 6806702ed49SChris Mason if (parent_nritems == 1) 6816702ed49SChris Mason return 0; 6826702ed49SChris Mason 683b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 684b4ce94deSChris Mason 6856702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 6866702ed49SChris Mason int close = 1; 687a6b6e75eSChris Mason 688081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 689081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 690081e9573SChris Mason continue; 691081e9573SChris Mason 692081e9573SChris Mason progress_passed = 1; 6936b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 694ca7a79adSChris Mason gen = btrfs_node_ptr_generation(parent, i); 695e9d0b13bSChris Mason if (last_block == 0) 696e9d0b13bSChris Mason last_block = blocknr; 6975708b959SChris Mason 6986702ed49SChris Mason if (i > 0) { 6996b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 7006b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 7016702ed49SChris Mason } 7020ef3e66bSChris Mason if (!close && i < end_slot - 2) { 7036b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 7046b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 7056702ed49SChris Mason } 706e9d0b13bSChris Mason if (close) { 707e9d0b13bSChris Mason last_block = blocknr; 7086702ed49SChris Mason continue; 709e9d0b13bSChris Mason } 7106702ed49SChris Mason 7116b80053dSChris Mason cur = btrfs_find_tree_block(root, blocknr, blocksize); 7126b80053dSChris Mason if (cur) 7131259ab75SChris Mason uptodate = btrfs_buffer_uptodate(cur, gen); 7146b80053dSChris Mason else 7156b80053dSChris Mason uptodate = 0; 7165708b959SChris Mason if (!cur || !uptodate) { 7176702ed49SChris Mason if (cache_only) { 7186b80053dSChris Mason free_extent_buffer(cur); 7196702ed49SChris Mason continue; 7206702ed49SChris Mason } 7216b80053dSChris Mason if (!cur) { 7226b80053dSChris Mason cur = read_tree_block(root, blocknr, 723ca7a79adSChris Mason blocksize, gen); 72497d9a8a4STsutomu Itoh if (!cur) 72597d9a8a4STsutomu Itoh return -EIO; 7266b80053dSChris Mason } else if (!uptodate) { 727ca7a79adSChris Mason btrfs_read_buffer(cur, gen); 7286702ed49SChris Mason } 729f2183bdeSChris Mason } 730e9d0b13bSChris Mason if (search_start == 0) 7316b80053dSChris Mason search_start = last_block; 732e9d0b13bSChris Mason 733e7a84565SChris Mason btrfs_tree_lock(cur); 734b4ce94deSChris Mason btrfs_set_lock_blocking(cur); 7356b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 736e7a84565SChris Mason &cur, search_start, 7376b80053dSChris Mason min(16 * blocksize, 7389fa8cfe7SChris Mason (end_slot - i) * blocksize)); 739252c38f0SYan if (err) { 740e7a84565SChris Mason btrfs_tree_unlock(cur); 7416b80053dSChris Mason free_extent_buffer(cur); 7426702ed49SChris Mason break; 743252c38f0SYan } 744e7a84565SChris Mason search_start = cur->start; 745e7a84565SChris Mason last_block = cur->start; 746f2183bdeSChris Mason *last_ret = search_start; 747e7a84565SChris Mason btrfs_tree_unlock(cur); 748e7a84565SChris Mason free_extent_buffer(cur); 7496702ed49SChris Mason } 7506702ed49SChris Mason return err; 7516702ed49SChris Mason } 7526702ed49SChris Mason 75374123bd7SChris Mason /* 75474123bd7SChris Mason * The leaf data grows from end-to-front in the node. 75574123bd7SChris Mason * this returns the address of the start of the last item, 75674123bd7SChris Mason * which is the stop of the leaf data stack 75774123bd7SChris Mason */ 758123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 7595f39d397SChris Mason struct extent_buffer *leaf) 760be0e5c09SChris Mason { 7615f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 762be0e5c09SChris Mason if (nr == 0) 763123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 7645f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 765be0e5c09SChris Mason } 766be0e5c09SChris Mason 767aa5d6bedSChris Mason 76874123bd7SChris Mason /* 7695f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 7705f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 7715f39d397SChris Mason * 77274123bd7SChris Mason * the slot in the array is returned via slot, and it points to 77374123bd7SChris Mason * the place where you would insert key if it is not found in 77474123bd7SChris Mason * the array. 77574123bd7SChris Mason * 77674123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 77774123bd7SChris Mason */ 778e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 779e02119d5SChris Mason unsigned long p, 7805f39d397SChris Mason int item_size, struct btrfs_key *key, 781be0e5c09SChris Mason int max, int *slot) 782be0e5c09SChris Mason { 783be0e5c09SChris Mason int low = 0; 784be0e5c09SChris Mason int high = max; 785be0e5c09SChris Mason int mid; 786be0e5c09SChris Mason int ret; 787479965d6SChris Mason struct btrfs_disk_key *tmp = NULL; 7885f39d397SChris Mason struct btrfs_disk_key unaligned; 7895f39d397SChris Mason unsigned long offset; 7905f39d397SChris Mason char *kaddr = NULL; 7915f39d397SChris Mason unsigned long map_start = 0; 7925f39d397SChris Mason unsigned long map_len = 0; 793479965d6SChris Mason int err; 794be0e5c09SChris Mason 795be0e5c09SChris Mason while (low < high) { 796be0e5c09SChris Mason mid = (low + high) / 2; 7975f39d397SChris Mason offset = p + mid * item_size; 7985f39d397SChris Mason 799a6591715SChris Mason if (!kaddr || offset < map_start || 8005f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 8015f39d397SChris Mason map_start + map_len) { 802934d375bSChris Mason 803934d375bSChris Mason err = map_private_extent_buffer(eb, offset, 804479965d6SChris Mason sizeof(struct btrfs_disk_key), 805a6591715SChris Mason &kaddr, &map_start, &map_len); 8065f39d397SChris Mason 807479965d6SChris Mason if (!err) { 808479965d6SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 809479965d6SChris Mason map_start); 810479965d6SChris Mason } else { 8115f39d397SChris Mason read_extent_buffer(eb, &unaligned, 8125f39d397SChris Mason offset, sizeof(unaligned)); 8135f39d397SChris Mason tmp = &unaligned; 814479965d6SChris Mason } 815479965d6SChris Mason 8165f39d397SChris Mason } else { 8175f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 8185f39d397SChris Mason map_start); 8195f39d397SChris Mason } 820be0e5c09SChris Mason ret = comp_keys(tmp, key); 821be0e5c09SChris Mason 822be0e5c09SChris Mason if (ret < 0) 823be0e5c09SChris Mason low = mid + 1; 824be0e5c09SChris Mason else if (ret > 0) 825be0e5c09SChris Mason high = mid; 826be0e5c09SChris Mason else { 827be0e5c09SChris Mason *slot = mid; 828be0e5c09SChris Mason return 0; 829be0e5c09SChris Mason } 830be0e5c09SChris Mason } 831be0e5c09SChris Mason *slot = low; 832be0e5c09SChris Mason return 1; 833be0e5c09SChris Mason } 834be0e5c09SChris Mason 83597571fd0SChris Mason /* 83697571fd0SChris Mason * simple bin_search frontend that does the right thing for 83797571fd0SChris Mason * leaves vs nodes 83897571fd0SChris Mason */ 8395f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 8405f39d397SChris Mason int level, int *slot) 841be0e5c09SChris Mason { 8425f39d397SChris Mason if (level == 0) { 8435f39d397SChris Mason return generic_bin_search(eb, 8445f39d397SChris Mason offsetof(struct btrfs_leaf, items), 8450783fcfcSChris Mason sizeof(struct btrfs_item), 8465f39d397SChris Mason key, btrfs_header_nritems(eb), 8477518a238SChris Mason slot); 848be0e5c09SChris Mason } else { 8495f39d397SChris Mason return generic_bin_search(eb, 8505f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 851123abc88SChris Mason sizeof(struct btrfs_key_ptr), 8525f39d397SChris Mason key, btrfs_header_nritems(eb), 8537518a238SChris Mason slot); 854be0e5c09SChris Mason } 855be0e5c09SChris Mason return -1; 856be0e5c09SChris Mason } 857be0e5c09SChris Mason 8585d4f98a2SYan Zheng int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key, 8595d4f98a2SYan Zheng int level, int *slot) 8605d4f98a2SYan Zheng { 8615d4f98a2SYan Zheng return bin_search(eb, key, level, slot); 8625d4f98a2SYan Zheng } 8635d4f98a2SYan Zheng 864f0486c68SYan, Zheng static void root_add_used(struct btrfs_root *root, u32 size) 865f0486c68SYan, Zheng { 866f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 867f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 868f0486c68SYan, Zheng btrfs_root_used(&root->root_item) + size); 869f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 870f0486c68SYan, Zheng } 871f0486c68SYan, Zheng 872f0486c68SYan, Zheng static void root_sub_used(struct btrfs_root *root, u32 size) 873f0486c68SYan, Zheng { 874f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 875f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 876f0486c68SYan, Zheng btrfs_root_used(&root->root_item) - size); 877f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 878f0486c68SYan, Zheng } 879f0486c68SYan, Zheng 880d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 881d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 882d352ac68SChris Mason * NULL is returned on error. 883d352ac68SChris Mason */ 884e02119d5SChris Mason static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root, 8855f39d397SChris Mason struct extent_buffer *parent, int slot) 886bb803951SChris Mason { 887ca7a79adSChris Mason int level = btrfs_header_level(parent); 888bb803951SChris Mason if (slot < 0) 889bb803951SChris Mason return NULL; 8905f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 891bb803951SChris Mason return NULL; 892ca7a79adSChris Mason 893ca7a79adSChris Mason BUG_ON(level == 0); 894ca7a79adSChris Mason 895db94535dSChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot), 896ca7a79adSChris Mason btrfs_level_size(root, level - 1), 897ca7a79adSChris Mason btrfs_node_ptr_generation(parent, slot)); 898bb803951SChris Mason } 899bb803951SChris Mason 900d352ac68SChris Mason /* 901d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 902d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 903d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 904d352ac68SChris Mason */ 905e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 90698ed5174SChris Mason struct btrfs_root *root, 90798ed5174SChris Mason struct btrfs_path *path, int level) 908bb803951SChris Mason { 9095f39d397SChris Mason struct extent_buffer *right = NULL; 9105f39d397SChris Mason struct extent_buffer *mid; 9115f39d397SChris Mason struct extent_buffer *left = NULL; 9125f39d397SChris Mason struct extent_buffer *parent = NULL; 913bb803951SChris Mason int ret = 0; 914bb803951SChris Mason int wret; 915bb803951SChris Mason int pslot; 916bb803951SChris Mason int orig_slot = path->slots[level]; 91779f95c82SChris Mason u64 orig_ptr; 918bb803951SChris Mason 919bb803951SChris Mason if (level == 0) 920bb803951SChris Mason return 0; 921bb803951SChris Mason 9225f39d397SChris Mason mid = path->nodes[level]; 923b4ce94deSChris Mason 924bd681513SChris Mason WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK && 925bd681513SChris Mason path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING); 9267bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 9277bb86316SChris Mason 9281d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 92979f95c82SChris Mason 930a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 9315f39d397SChris Mason parent = path->nodes[level + 1]; 932bb803951SChris Mason pslot = path->slots[level + 1]; 933a05a9bb1SLi Zefan } 934bb803951SChris Mason 93540689478SChris Mason /* 93640689478SChris Mason * deal with the case where there is only one pointer in the root 93740689478SChris Mason * by promoting the node below to a root 93840689478SChris Mason */ 9395f39d397SChris Mason if (!parent) { 9405f39d397SChris Mason struct extent_buffer *child; 941bb803951SChris Mason 9425f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 943bb803951SChris Mason return 0; 944bb803951SChris Mason 945bb803951SChris Mason /* promote the child to a root */ 9465f39d397SChris Mason child = read_node_slot(root, mid, 0); 9477951f3ceSJeff Mahoney BUG_ON(!child); 948925baeddSChris Mason btrfs_tree_lock(child); 949b4ce94deSChris Mason btrfs_set_lock_blocking(child); 9509fa8cfe7SChris Mason ret = btrfs_cow_block(trans, root, child, mid, 0, &child); 951f0486c68SYan, Zheng if (ret) { 952f0486c68SYan, Zheng btrfs_tree_unlock(child); 953f0486c68SYan, Zheng free_extent_buffer(child); 954f0486c68SYan, Zheng goto enospc; 955f0486c68SYan, Zheng } 9562f375ab9SYan 957240f62c8SChris Mason rcu_assign_pointer(root->node, child); 958925baeddSChris Mason 9590b86a832SChris Mason add_root_to_dirty_list(root); 960925baeddSChris Mason btrfs_tree_unlock(child); 961b4ce94deSChris Mason 962925baeddSChris Mason path->locks[level] = 0; 963bb803951SChris Mason path->nodes[level] = NULL; 9645f39d397SChris Mason clean_tree_block(trans, root, mid); 965925baeddSChris Mason btrfs_tree_unlock(mid); 966bb803951SChris Mason /* once for the path */ 9675f39d397SChris Mason free_extent_buffer(mid); 968f0486c68SYan, Zheng 969f0486c68SYan, Zheng root_sub_used(root, mid->len); 97066d7e7f0SArne Jansen btrfs_free_tree_block(trans, root, mid, 0, 1, 0); 971bb803951SChris Mason /* once for the root ptr */ 9725f39d397SChris Mason free_extent_buffer(mid); 973f0486c68SYan, Zheng return 0; 974bb803951SChris Mason } 9755f39d397SChris Mason if (btrfs_header_nritems(mid) > 976123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 977bb803951SChris Mason return 0; 978bb803951SChris Mason 979559af821SAndi Kleen btrfs_header_nritems(mid); 98054aa1f4dSChris Mason 9815f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 9825f39d397SChris Mason if (left) { 983925baeddSChris Mason btrfs_tree_lock(left); 984b4ce94deSChris Mason btrfs_set_lock_blocking(left); 9855f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 9869fa8cfe7SChris Mason parent, pslot - 1, &left); 98754aa1f4dSChris Mason if (wret) { 98854aa1f4dSChris Mason ret = wret; 98954aa1f4dSChris Mason goto enospc; 99054aa1f4dSChris Mason } 9912cc58cf2SChris Mason } 9925f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 9935f39d397SChris Mason if (right) { 994925baeddSChris Mason btrfs_tree_lock(right); 995b4ce94deSChris Mason btrfs_set_lock_blocking(right); 9965f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 9979fa8cfe7SChris Mason parent, pslot + 1, &right); 9982cc58cf2SChris Mason if (wret) { 9992cc58cf2SChris Mason ret = wret; 10002cc58cf2SChris Mason goto enospc; 10012cc58cf2SChris Mason } 10022cc58cf2SChris Mason } 10032cc58cf2SChris Mason 10042cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 10055f39d397SChris Mason if (left) { 10065f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 1007bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 100879f95c82SChris Mason if (wret < 0) 100979f95c82SChris Mason ret = wret; 1010559af821SAndi Kleen btrfs_header_nritems(mid); 1011bb803951SChris Mason } 101279f95c82SChris Mason 101379f95c82SChris Mason /* 101479f95c82SChris Mason * then try to empty the right most buffer into the middle 101579f95c82SChris Mason */ 10165f39d397SChris Mason if (right) { 1017971a1f66SChris Mason wret = push_node_left(trans, root, mid, right, 1); 101854aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 101979f95c82SChris Mason ret = wret; 10205f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 10215f39d397SChris Mason clean_tree_block(trans, root, right); 1022925baeddSChris Mason btrfs_tree_unlock(right); 1023143bede5SJeff Mahoney del_ptr(trans, root, path, level + 1, pslot + 1); 1024f0486c68SYan, Zheng root_sub_used(root, right->len); 102566d7e7f0SArne Jansen btrfs_free_tree_block(trans, root, right, 0, 1, 0); 1026f0486c68SYan, Zheng free_extent_buffer(right); 1027f0486c68SYan, Zheng right = NULL; 1028bb803951SChris Mason } else { 10295f39d397SChris Mason struct btrfs_disk_key right_key; 10305f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 10315f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 10325f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 1033bb803951SChris Mason } 1034bb803951SChris Mason } 10355f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 103679f95c82SChris Mason /* 103779f95c82SChris Mason * we're not allowed to leave a node with one item in the 103879f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 103979f95c82SChris Mason * could try to delete the only pointer in this node. 104079f95c82SChris Mason * So, pull some keys from the left. 104179f95c82SChris Mason * There has to be a left pointer at this point because 104279f95c82SChris Mason * otherwise we would have pulled some pointers from the 104379f95c82SChris Mason * right 104479f95c82SChris Mason */ 10455f39d397SChris Mason BUG_ON(!left); 10465f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 104754aa1f4dSChris Mason if (wret < 0) { 104879f95c82SChris Mason ret = wret; 104954aa1f4dSChris Mason goto enospc; 105054aa1f4dSChris Mason } 1051bce4eae9SChris Mason if (wret == 1) { 1052bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 1053bce4eae9SChris Mason if (wret < 0) 1054bce4eae9SChris Mason ret = wret; 1055bce4eae9SChris Mason } 105679f95c82SChris Mason BUG_ON(wret == 1); 105779f95c82SChris Mason } 10585f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 10595f39d397SChris Mason clean_tree_block(trans, root, mid); 1060925baeddSChris Mason btrfs_tree_unlock(mid); 1061143bede5SJeff Mahoney del_ptr(trans, root, path, level + 1, pslot); 1062f0486c68SYan, Zheng root_sub_used(root, mid->len); 106366d7e7f0SArne Jansen btrfs_free_tree_block(trans, root, mid, 0, 1, 0); 1064f0486c68SYan, Zheng free_extent_buffer(mid); 1065f0486c68SYan, Zheng mid = NULL; 106679f95c82SChris Mason } else { 106779f95c82SChris Mason /* update the parent key to reflect our changes */ 10685f39d397SChris Mason struct btrfs_disk_key mid_key; 10695f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 10705f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 10715f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 107279f95c82SChris Mason } 1073bb803951SChris Mason 107479f95c82SChris Mason /* update the path */ 10755f39d397SChris Mason if (left) { 10765f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 10775f39d397SChris Mason extent_buffer_get(left); 1078925baeddSChris Mason /* left was locked after cow */ 10795f39d397SChris Mason path->nodes[level] = left; 1080bb803951SChris Mason path->slots[level + 1] -= 1; 1081bb803951SChris Mason path->slots[level] = orig_slot; 1082925baeddSChris Mason if (mid) { 1083925baeddSChris Mason btrfs_tree_unlock(mid); 10845f39d397SChris Mason free_extent_buffer(mid); 1085925baeddSChris Mason } 1086bb803951SChris Mason } else { 10875f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1088bb803951SChris Mason path->slots[level] = orig_slot; 1089bb803951SChris Mason } 1090bb803951SChris Mason } 109179f95c82SChris Mason /* double check we haven't messed things up */ 1092e20d96d6SChris Mason if (orig_ptr != 10935f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 109479f95c82SChris Mason BUG(); 109554aa1f4dSChris Mason enospc: 1096925baeddSChris Mason if (right) { 1097925baeddSChris Mason btrfs_tree_unlock(right); 10985f39d397SChris Mason free_extent_buffer(right); 1099925baeddSChris Mason } 1100925baeddSChris Mason if (left) { 1101925baeddSChris Mason if (path->nodes[level] != left) 1102925baeddSChris Mason btrfs_tree_unlock(left); 11035f39d397SChris Mason free_extent_buffer(left); 1104925baeddSChris Mason } 1105bb803951SChris Mason return ret; 1106bb803951SChris Mason } 1107bb803951SChris Mason 1108d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1109d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1110d352ac68SChris Mason * have to be pessimistic. 1111d352ac68SChris Mason */ 1112d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1113e66f709bSChris Mason struct btrfs_root *root, 1114e66f709bSChris Mason struct btrfs_path *path, int level) 1115e66f709bSChris Mason { 11165f39d397SChris Mason struct extent_buffer *right = NULL; 11175f39d397SChris Mason struct extent_buffer *mid; 11185f39d397SChris Mason struct extent_buffer *left = NULL; 11195f39d397SChris Mason struct extent_buffer *parent = NULL; 1120e66f709bSChris Mason int ret = 0; 1121e66f709bSChris Mason int wret; 1122e66f709bSChris Mason int pslot; 1123e66f709bSChris Mason int orig_slot = path->slots[level]; 1124e66f709bSChris Mason 1125e66f709bSChris Mason if (level == 0) 1126e66f709bSChris Mason return 1; 1127e66f709bSChris Mason 11285f39d397SChris Mason mid = path->nodes[level]; 11297bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1130e66f709bSChris Mason 1131a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 11325f39d397SChris Mason parent = path->nodes[level + 1]; 1133e66f709bSChris Mason pslot = path->slots[level + 1]; 1134a05a9bb1SLi Zefan } 1135e66f709bSChris Mason 11365f39d397SChris Mason if (!parent) 1137e66f709bSChris Mason return 1; 1138e66f709bSChris Mason 11395f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 1140e66f709bSChris Mason 1141e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 11425f39d397SChris Mason if (left) { 1143e66f709bSChris Mason u32 left_nr; 1144925baeddSChris Mason 1145925baeddSChris Mason btrfs_tree_lock(left); 1146b4ce94deSChris Mason btrfs_set_lock_blocking(left); 1147b4ce94deSChris Mason 11485f39d397SChris Mason left_nr = btrfs_header_nritems(left); 114933ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 115033ade1f8SChris Mason wret = 1; 115133ade1f8SChris Mason } else { 11525f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 11539fa8cfe7SChris Mason pslot - 1, &left); 115454aa1f4dSChris Mason if (ret) 115554aa1f4dSChris Mason wret = 1; 115654aa1f4dSChris Mason else { 115754aa1f4dSChris Mason wret = push_node_left(trans, root, 1158971a1f66SChris Mason left, mid, 0); 115954aa1f4dSChris Mason } 116033ade1f8SChris Mason } 1161e66f709bSChris Mason if (wret < 0) 1162e66f709bSChris Mason ret = wret; 1163e66f709bSChris Mason if (wret == 0) { 11645f39d397SChris Mason struct btrfs_disk_key disk_key; 1165e66f709bSChris Mason orig_slot += left_nr; 11665f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 11675f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 11685f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 11695f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 11705f39d397SChris Mason path->nodes[level] = left; 1171e66f709bSChris Mason path->slots[level + 1] -= 1; 1172e66f709bSChris Mason path->slots[level] = orig_slot; 1173925baeddSChris Mason btrfs_tree_unlock(mid); 11745f39d397SChris Mason free_extent_buffer(mid); 1175e66f709bSChris Mason } else { 1176e66f709bSChris Mason orig_slot -= 11775f39d397SChris Mason btrfs_header_nritems(left); 1178e66f709bSChris Mason path->slots[level] = orig_slot; 1179925baeddSChris Mason btrfs_tree_unlock(left); 11805f39d397SChris Mason free_extent_buffer(left); 1181e66f709bSChris Mason } 1182e66f709bSChris Mason return 0; 1183e66f709bSChris Mason } 1184925baeddSChris Mason btrfs_tree_unlock(left); 11855f39d397SChris Mason free_extent_buffer(left); 1186e66f709bSChris Mason } 11875f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 1188e66f709bSChris Mason 1189e66f709bSChris Mason /* 1190e66f709bSChris Mason * then try to empty the right most buffer into the middle 1191e66f709bSChris Mason */ 11925f39d397SChris Mason if (right) { 119333ade1f8SChris Mason u32 right_nr; 1194b4ce94deSChris Mason 1195925baeddSChris Mason btrfs_tree_lock(right); 1196b4ce94deSChris Mason btrfs_set_lock_blocking(right); 1197b4ce94deSChris Mason 11985f39d397SChris Mason right_nr = btrfs_header_nritems(right); 119933ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 120033ade1f8SChris Mason wret = 1; 120133ade1f8SChris Mason } else { 12025f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 12035f39d397SChris Mason parent, pslot + 1, 12049fa8cfe7SChris Mason &right); 120554aa1f4dSChris Mason if (ret) 120654aa1f4dSChris Mason wret = 1; 120754aa1f4dSChris Mason else { 120833ade1f8SChris Mason wret = balance_node_right(trans, root, 12095f39d397SChris Mason right, mid); 121033ade1f8SChris Mason } 121154aa1f4dSChris Mason } 1212e66f709bSChris Mason if (wret < 0) 1213e66f709bSChris Mason ret = wret; 1214e66f709bSChris Mason if (wret == 0) { 12155f39d397SChris Mason struct btrfs_disk_key disk_key; 12165f39d397SChris Mason 12175f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 12185f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 12195f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 12205f39d397SChris Mason 12215f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 12225f39d397SChris Mason path->nodes[level] = right; 1223e66f709bSChris Mason path->slots[level + 1] += 1; 1224e66f709bSChris Mason path->slots[level] = orig_slot - 12255f39d397SChris Mason btrfs_header_nritems(mid); 1226925baeddSChris Mason btrfs_tree_unlock(mid); 12275f39d397SChris Mason free_extent_buffer(mid); 1228e66f709bSChris Mason } else { 1229925baeddSChris Mason btrfs_tree_unlock(right); 12305f39d397SChris Mason free_extent_buffer(right); 1231e66f709bSChris Mason } 1232e66f709bSChris Mason return 0; 1233e66f709bSChris Mason } 1234925baeddSChris Mason btrfs_tree_unlock(right); 12355f39d397SChris Mason free_extent_buffer(right); 1236e66f709bSChris Mason } 1237e66f709bSChris Mason return 1; 1238e66f709bSChris Mason } 1239e66f709bSChris Mason 124074123bd7SChris Mason /* 1241d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1242d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 12433c69faecSChris Mason */ 1244c8c42864SChris Mason static void reada_for_search(struct btrfs_root *root, 1245e02119d5SChris Mason struct btrfs_path *path, 124601f46658SChris Mason int level, int slot, u64 objectid) 12473c69faecSChris Mason { 12485f39d397SChris Mason struct extent_buffer *node; 124901f46658SChris Mason struct btrfs_disk_key disk_key; 12503c69faecSChris Mason u32 nritems; 12513c69faecSChris Mason u64 search; 1252a7175319SChris Mason u64 target; 12536b80053dSChris Mason u64 nread = 0; 1254cb25c2eaSJosef Bacik u64 gen; 12553c69faecSChris Mason int direction = path->reada; 12565f39d397SChris Mason struct extent_buffer *eb; 12576b80053dSChris Mason u32 nr; 12586b80053dSChris Mason u32 blocksize; 12596b80053dSChris Mason u32 nscan = 0; 1260db94535dSChris Mason 1261a6b6e75eSChris Mason if (level != 1) 12623c69faecSChris Mason return; 12633c69faecSChris Mason 12646702ed49SChris Mason if (!path->nodes[level]) 12656702ed49SChris Mason return; 12666702ed49SChris Mason 12675f39d397SChris Mason node = path->nodes[level]; 1268925baeddSChris Mason 12693c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 12706b80053dSChris Mason blocksize = btrfs_level_size(root, level - 1); 12716b80053dSChris Mason eb = btrfs_find_tree_block(root, search, blocksize); 12725f39d397SChris Mason if (eb) { 12735f39d397SChris Mason free_extent_buffer(eb); 12743c69faecSChris Mason return; 12753c69faecSChris Mason } 12763c69faecSChris Mason 1277a7175319SChris Mason target = search; 12786b80053dSChris Mason 12795f39d397SChris Mason nritems = btrfs_header_nritems(node); 12806b80053dSChris Mason nr = slot; 128125b8b936SJosef Bacik 12823c69faecSChris Mason while (1) { 12836b80053dSChris Mason if (direction < 0) { 12846b80053dSChris Mason if (nr == 0) 12853c69faecSChris Mason break; 12866b80053dSChris Mason nr--; 12876b80053dSChris Mason } else if (direction > 0) { 12886b80053dSChris Mason nr++; 12896b80053dSChris Mason if (nr >= nritems) 12906b80053dSChris Mason break; 12913c69faecSChris Mason } 129201f46658SChris Mason if (path->reada < 0 && objectid) { 129301f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 129401f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 129501f46658SChris Mason break; 129601f46658SChris Mason } 12976b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1298a7175319SChris Mason if ((search <= target && target - search <= 65536) || 1299a7175319SChris Mason (search > target && search - target <= 65536)) { 1300cb25c2eaSJosef Bacik gen = btrfs_node_ptr_generation(node, nr); 1301cb25c2eaSJosef Bacik readahead_tree_block(root, search, blocksize, gen); 13026b80053dSChris Mason nread += blocksize; 13033c69faecSChris Mason } 13046b80053dSChris Mason nscan++; 1305a7175319SChris Mason if ((nread > 65536 || nscan > 32)) 13066b80053dSChris Mason break; 13073c69faecSChris Mason } 13083c69faecSChris Mason } 1309925baeddSChris Mason 1310d352ac68SChris Mason /* 1311b4ce94deSChris Mason * returns -EAGAIN if it had to drop the path, or zero if everything was in 1312b4ce94deSChris Mason * cache 1313b4ce94deSChris Mason */ 1314b4ce94deSChris Mason static noinline int reada_for_balance(struct btrfs_root *root, 1315b4ce94deSChris Mason struct btrfs_path *path, int level) 1316b4ce94deSChris Mason { 1317b4ce94deSChris Mason int slot; 1318b4ce94deSChris Mason int nritems; 1319b4ce94deSChris Mason struct extent_buffer *parent; 1320b4ce94deSChris Mason struct extent_buffer *eb; 1321b4ce94deSChris Mason u64 gen; 1322b4ce94deSChris Mason u64 block1 = 0; 1323b4ce94deSChris Mason u64 block2 = 0; 1324b4ce94deSChris Mason int ret = 0; 1325b4ce94deSChris Mason int blocksize; 1326b4ce94deSChris Mason 13278c594ea8SChris Mason parent = path->nodes[level + 1]; 1328b4ce94deSChris Mason if (!parent) 1329b4ce94deSChris Mason return 0; 1330b4ce94deSChris Mason 1331b4ce94deSChris Mason nritems = btrfs_header_nritems(parent); 13328c594ea8SChris Mason slot = path->slots[level + 1]; 1333b4ce94deSChris Mason blocksize = btrfs_level_size(root, level); 1334b4ce94deSChris Mason 1335b4ce94deSChris Mason if (slot > 0) { 1336b4ce94deSChris Mason block1 = btrfs_node_blockptr(parent, slot - 1); 1337b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot - 1); 1338b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block1, blocksize); 1339b4ce94deSChris Mason if (eb && btrfs_buffer_uptodate(eb, gen)) 1340b4ce94deSChris Mason block1 = 0; 1341b4ce94deSChris Mason free_extent_buffer(eb); 1342b4ce94deSChris Mason } 13438c594ea8SChris Mason if (slot + 1 < nritems) { 1344b4ce94deSChris Mason block2 = btrfs_node_blockptr(parent, slot + 1); 1345b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot + 1); 1346b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block2, blocksize); 1347b4ce94deSChris Mason if (eb && btrfs_buffer_uptodate(eb, gen)) 1348b4ce94deSChris Mason block2 = 0; 1349b4ce94deSChris Mason free_extent_buffer(eb); 1350b4ce94deSChris Mason } 1351b4ce94deSChris Mason if (block1 || block2) { 1352b4ce94deSChris Mason ret = -EAGAIN; 13538c594ea8SChris Mason 13548c594ea8SChris Mason /* release the whole path */ 1355b3b4aa74SDavid Sterba btrfs_release_path(path); 13568c594ea8SChris Mason 13578c594ea8SChris Mason /* read the blocks */ 1358b4ce94deSChris Mason if (block1) 1359b4ce94deSChris Mason readahead_tree_block(root, block1, blocksize, 0); 1360b4ce94deSChris Mason if (block2) 1361b4ce94deSChris Mason readahead_tree_block(root, block2, blocksize, 0); 1362b4ce94deSChris Mason 1363b4ce94deSChris Mason if (block1) { 1364b4ce94deSChris Mason eb = read_tree_block(root, block1, blocksize, 0); 1365b4ce94deSChris Mason free_extent_buffer(eb); 1366b4ce94deSChris Mason } 13678c594ea8SChris Mason if (block2) { 1368b4ce94deSChris Mason eb = read_tree_block(root, block2, blocksize, 0); 1369b4ce94deSChris Mason free_extent_buffer(eb); 1370b4ce94deSChris Mason } 1371b4ce94deSChris Mason } 1372b4ce94deSChris Mason return ret; 1373b4ce94deSChris Mason } 1374b4ce94deSChris Mason 1375b4ce94deSChris Mason 1376b4ce94deSChris Mason /* 1377d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1378d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1379d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1380d397712bSChris Mason * tree. 1381d352ac68SChris Mason * 1382d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1383d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1384d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1385d352ac68SChris Mason * 1386d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1387d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1388d352ac68SChris Mason */ 1389e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1390e02119d5SChris Mason int lowest_unlock) 1391925baeddSChris Mason { 1392925baeddSChris Mason int i; 1393925baeddSChris Mason int skip_level = level; 1394051e1b9fSChris Mason int no_skips = 0; 1395925baeddSChris Mason struct extent_buffer *t; 1396925baeddSChris Mason 1397925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1398925baeddSChris Mason if (!path->nodes[i]) 1399925baeddSChris Mason break; 1400925baeddSChris Mason if (!path->locks[i]) 1401925baeddSChris Mason break; 1402051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1403925baeddSChris Mason skip_level = i + 1; 1404925baeddSChris Mason continue; 1405925baeddSChris Mason } 1406051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1407925baeddSChris Mason u32 nritems; 1408925baeddSChris Mason t = path->nodes[i]; 1409925baeddSChris Mason nritems = btrfs_header_nritems(t); 1410051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1411925baeddSChris Mason skip_level = i + 1; 1412925baeddSChris Mason continue; 1413925baeddSChris Mason } 1414925baeddSChris Mason } 1415051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1416051e1b9fSChris Mason no_skips = 1; 1417051e1b9fSChris Mason 1418925baeddSChris Mason t = path->nodes[i]; 1419925baeddSChris Mason if (i >= lowest_unlock && i > skip_level && path->locks[i]) { 1420bd681513SChris Mason btrfs_tree_unlock_rw(t, path->locks[i]); 1421925baeddSChris Mason path->locks[i] = 0; 1422925baeddSChris Mason } 1423925baeddSChris Mason } 1424925baeddSChris Mason } 1425925baeddSChris Mason 14263c69faecSChris Mason /* 1427b4ce94deSChris Mason * This releases any locks held in the path starting at level and 1428b4ce94deSChris Mason * going all the way up to the root. 1429b4ce94deSChris Mason * 1430b4ce94deSChris Mason * btrfs_search_slot will keep the lock held on higher nodes in a few 1431b4ce94deSChris Mason * corner cases, such as COW of the block at slot zero in the node. This 1432b4ce94deSChris Mason * ignores those rules, and it should only be called when there are no 1433b4ce94deSChris Mason * more updates to be done higher up in the tree. 1434b4ce94deSChris Mason */ 1435b4ce94deSChris Mason noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level) 1436b4ce94deSChris Mason { 1437b4ce94deSChris Mason int i; 1438b4ce94deSChris Mason 14395d4f98a2SYan Zheng if (path->keep_locks) 1440b4ce94deSChris Mason return; 1441b4ce94deSChris Mason 1442b4ce94deSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1443b4ce94deSChris Mason if (!path->nodes[i]) 144412f4daccSChris Mason continue; 1445b4ce94deSChris Mason if (!path->locks[i]) 144612f4daccSChris Mason continue; 1447bd681513SChris Mason btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]); 1448b4ce94deSChris Mason path->locks[i] = 0; 1449b4ce94deSChris Mason } 1450b4ce94deSChris Mason } 1451b4ce94deSChris Mason 1452b4ce94deSChris Mason /* 1453c8c42864SChris Mason * helper function for btrfs_search_slot. The goal is to find a block 1454c8c42864SChris Mason * in cache without setting the path to blocking. If we find the block 1455c8c42864SChris Mason * we return zero and the path is unchanged. 1456c8c42864SChris Mason * 1457c8c42864SChris Mason * If we can't find the block, we set the path blocking and do some 1458c8c42864SChris Mason * reada. -EAGAIN is returned and the search must be repeated. 1459c8c42864SChris Mason */ 1460c8c42864SChris Mason static int 1461c8c42864SChris Mason read_block_for_search(struct btrfs_trans_handle *trans, 1462c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1463c8c42864SChris Mason struct extent_buffer **eb_ret, int level, int slot, 1464c8c42864SChris Mason struct btrfs_key *key) 1465c8c42864SChris Mason { 1466c8c42864SChris Mason u64 blocknr; 1467c8c42864SChris Mason u64 gen; 1468c8c42864SChris Mason u32 blocksize; 1469c8c42864SChris Mason struct extent_buffer *b = *eb_ret; 1470c8c42864SChris Mason struct extent_buffer *tmp; 147176a05b35SChris Mason int ret; 1472c8c42864SChris Mason 1473c8c42864SChris Mason blocknr = btrfs_node_blockptr(b, slot); 1474c8c42864SChris Mason gen = btrfs_node_ptr_generation(b, slot); 1475c8c42864SChris Mason blocksize = btrfs_level_size(root, level - 1); 1476c8c42864SChris Mason 1477c8c42864SChris Mason tmp = btrfs_find_tree_block(root, blocknr, blocksize); 1478cb44921aSChris Mason if (tmp) { 1479cb44921aSChris Mason if (btrfs_buffer_uptodate(tmp, 0)) { 1480cb44921aSChris Mason if (btrfs_buffer_uptodate(tmp, gen)) { 148176a05b35SChris Mason /* 1482cb44921aSChris Mason * we found an up to date block without 1483cb44921aSChris Mason * sleeping, return 148476a05b35SChris Mason * right away 148576a05b35SChris Mason */ 1486c8c42864SChris Mason *eb_ret = tmp; 1487c8c42864SChris Mason return 0; 1488c8c42864SChris Mason } 1489cb44921aSChris Mason /* the pages were up to date, but we failed 1490cb44921aSChris Mason * the generation number check. Do a full 1491cb44921aSChris Mason * read for the generation number that is correct. 1492cb44921aSChris Mason * We must do this without dropping locks so 1493cb44921aSChris Mason * we can trust our generation number 1494cb44921aSChris Mason */ 1495cb44921aSChris Mason free_extent_buffer(tmp); 1496bd681513SChris Mason btrfs_set_path_blocking(p); 1497bd681513SChris Mason 1498cb44921aSChris Mason tmp = read_tree_block(root, blocknr, blocksize, gen); 1499cb44921aSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 1500cb44921aSChris Mason *eb_ret = tmp; 1501cb44921aSChris Mason return 0; 1502cb44921aSChris Mason } 1503cb44921aSChris Mason free_extent_buffer(tmp); 1504b3b4aa74SDavid Sterba btrfs_release_path(p); 1505cb44921aSChris Mason return -EIO; 1506cb44921aSChris Mason } 1507cb44921aSChris Mason } 1508c8c42864SChris Mason 1509c8c42864SChris Mason /* 1510c8c42864SChris Mason * reduce lock contention at high levels 1511c8c42864SChris Mason * of the btree by dropping locks before 151276a05b35SChris Mason * we read. Don't release the lock on the current 151376a05b35SChris Mason * level because we need to walk this node to figure 151476a05b35SChris Mason * out which blocks to read. 1515c8c42864SChris Mason */ 15168c594ea8SChris Mason btrfs_unlock_up_safe(p, level + 1); 15178c594ea8SChris Mason btrfs_set_path_blocking(p); 15188c594ea8SChris Mason 1519c8c42864SChris Mason free_extent_buffer(tmp); 1520c8c42864SChris Mason if (p->reada) 1521c8c42864SChris Mason reada_for_search(root, p, level, slot, key->objectid); 1522c8c42864SChris Mason 1523b3b4aa74SDavid Sterba btrfs_release_path(p); 152476a05b35SChris Mason 152576a05b35SChris Mason ret = -EAGAIN; 15265bdd3536SYan, Zheng tmp = read_tree_block(root, blocknr, blocksize, 0); 152776a05b35SChris Mason if (tmp) { 152876a05b35SChris Mason /* 152976a05b35SChris Mason * If the read above didn't mark this buffer up to date, 153076a05b35SChris Mason * it will never end up being up to date. Set ret to EIO now 153176a05b35SChris Mason * and give up so that our caller doesn't loop forever 153276a05b35SChris Mason * on our EAGAINs. 153376a05b35SChris Mason */ 153476a05b35SChris Mason if (!btrfs_buffer_uptodate(tmp, 0)) 153576a05b35SChris Mason ret = -EIO; 1536c8c42864SChris Mason free_extent_buffer(tmp); 153776a05b35SChris Mason } 153876a05b35SChris Mason return ret; 1539c8c42864SChris Mason } 1540c8c42864SChris Mason 1541c8c42864SChris Mason /* 1542c8c42864SChris Mason * helper function for btrfs_search_slot. This does all of the checks 1543c8c42864SChris Mason * for node-level blocks and does any balancing required based on 1544c8c42864SChris Mason * the ins_len. 1545c8c42864SChris Mason * 1546c8c42864SChris Mason * If no extra work was required, zero is returned. If we had to 1547c8c42864SChris Mason * drop the path, -EAGAIN is returned and btrfs_search_slot must 1548c8c42864SChris Mason * start over 1549c8c42864SChris Mason */ 1550c8c42864SChris Mason static int 1551c8c42864SChris Mason setup_nodes_for_search(struct btrfs_trans_handle *trans, 1552c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1553bd681513SChris Mason struct extent_buffer *b, int level, int ins_len, 1554bd681513SChris Mason int *write_lock_level) 1555c8c42864SChris Mason { 1556c8c42864SChris Mason int ret; 1557c8c42864SChris Mason if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= 1558c8c42864SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { 1559c8c42864SChris Mason int sret; 1560c8c42864SChris Mason 1561bd681513SChris Mason if (*write_lock_level < level + 1) { 1562bd681513SChris Mason *write_lock_level = level + 1; 1563bd681513SChris Mason btrfs_release_path(p); 1564bd681513SChris Mason goto again; 1565bd681513SChris Mason } 1566bd681513SChris Mason 1567c8c42864SChris Mason sret = reada_for_balance(root, p, level); 1568c8c42864SChris Mason if (sret) 1569c8c42864SChris Mason goto again; 1570c8c42864SChris Mason 1571c8c42864SChris Mason btrfs_set_path_blocking(p); 1572c8c42864SChris Mason sret = split_node(trans, root, p, level); 1573bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 1574c8c42864SChris Mason 1575c8c42864SChris Mason BUG_ON(sret > 0); 1576c8c42864SChris Mason if (sret) { 1577c8c42864SChris Mason ret = sret; 1578c8c42864SChris Mason goto done; 1579c8c42864SChris Mason } 1580c8c42864SChris Mason b = p->nodes[level]; 1581c8c42864SChris Mason } else if (ins_len < 0 && btrfs_header_nritems(b) < 1582cfbb9308SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 2) { 1583c8c42864SChris Mason int sret; 1584c8c42864SChris Mason 1585bd681513SChris Mason if (*write_lock_level < level + 1) { 1586bd681513SChris Mason *write_lock_level = level + 1; 1587bd681513SChris Mason btrfs_release_path(p); 1588bd681513SChris Mason goto again; 1589bd681513SChris Mason } 1590bd681513SChris Mason 1591c8c42864SChris Mason sret = reada_for_balance(root, p, level); 1592c8c42864SChris Mason if (sret) 1593c8c42864SChris Mason goto again; 1594c8c42864SChris Mason 1595c8c42864SChris Mason btrfs_set_path_blocking(p); 1596c8c42864SChris Mason sret = balance_level(trans, root, p, level); 1597bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 1598c8c42864SChris Mason 1599c8c42864SChris Mason if (sret) { 1600c8c42864SChris Mason ret = sret; 1601c8c42864SChris Mason goto done; 1602c8c42864SChris Mason } 1603c8c42864SChris Mason b = p->nodes[level]; 1604c8c42864SChris Mason if (!b) { 1605b3b4aa74SDavid Sterba btrfs_release_path(p); 1606c8c42864SChris Mason goto again; 1607c8c42864SChris Mason } 1608c8c42864SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 1609c8c42864SChris Mason } 1610c8c42864SChris Mason return 0; 1611c8c42864SChris Mason 1612c8c42864SChris Mason again: 1613c8c42864SChris Mason ret = -EAGAIN; 1614c8c42864SChris Mason done: 1615c8c42864SChris Mason return ret; 1616c8c42864SChris Mason } 1617c8c42864SChris Mason 1618c8c42864SChris Mason /* 161974123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 162074123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 162174123bd7SChris Mason * level of the path (level 0) 162274123bd7SChris Mason * 162374123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 1624aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 1625aa5d6bedSChris Mason * search a negative error number is returned. 162697571fd0SChris Mason * 162797571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 162897571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 162997571fd0SChris Mason * possible) 163074123bd7SChris Mason */ 1631e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 1632e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 1633e089f05cSChris Mason ins_len, int cow) 1634be0e5c09SChris Mason { 16355f39d397SChris Mason struct extent_buffer *b; 1636be0e5c09SChris Mason int slot; 1637be0e5c09SChris Mason int ret; 163833c66f43SYan Zheng int err; 1639be0e5c09SChris Mason int level; 1640925baeddSChris Mason int lowest_unlock = 1; 1641bd681513SChris Mason int root_lock; 1642bd681513SChris Mason /* everything at write_lock_level or lower must be write locked */ 1643bd681513SChris Mason int write_lock_level = 0; 16449f3a7427SChris Mason u8 lowest_level = 0; 16459f3a7427SChris Mason 16466702ed49SChris Mason lowest_level = p->lowest_level; 1647323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 164822b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 164925179201SJosef Bacik 1650bd681513SChris Mason if (ins_len < 0) { 1651925baeddSChris Mason lowest_unlock = 2; 165265b51a00SChris Mason 1653bd681513SChris Mason /* when we are removing items, we might have to go up to level 1654bd681513SChris Mason * two as we update tree pointers Make sure we keep write 1655bd681513SChris Mason * for those levels as well 1656bd681513SChris Mason */ 1657bd681513SChris Mason write_lock_level = 2; 1658bd681513SChris Mason } else if (ins_len > 0) { 1659bd681513SChris Mason /* 1660bd681513SChris Mason * for inserting items, make sure we have a write lock on 1661bd681513SChris Mason * level 1 so we can update keys 1662bd681513SChris Mason */ 1663bd681513SChris Mason write_lock_level = 1; 1664bd681513SChris Mason } 1665bd681513SChris Mason 1666bd681513SChris Mason if (!cow) 1667bd681513SChris Mason write_lock_level = -1; 1668bd681513SChris Mason 1669bd681513SChris Mason if (cow && (p->keep_locks || p->lowest_level)) 1670bd681513SChris Mason write_lock_level = BTRFS_MAX_LEVEL; 1671bd681513SChris Mason 1672bb803951SChris Mason again: 1673bd681513SChris Mason /* 1674bd681513SChris Mason * we try very hard to do read locks on the root 1675bd681513SChris Mason */ 1676bd681513SChris Mason root_lock = BTRFS_READ_LOCK; 1677bd681513SChris Mason level = 0; 16785d4f98a2SYan Zheng if (p->search_commit_root) { 1679bd681513SChris Mason /* 1680bd681513SChris Mason * the commit roots are read only 1681bd681513SChris Mason * so we always do read locks 1682bd681513SChris Mason */ 16835d4f98a2SYan Zheng b = root->commit_root; 16845d4f98a2SYan Zheng extent_buffer_get(b); 1685bd681513SChris Mason level = btrfs_header_level(b); 16865d4f98a2SYan Zheng if (!p->skip_locking) 1687bd681513SChris Mason btrfs_tree_read_lock(b); 16885d4f98a2SYan Zheng } else { 1689bd681513SChris Mason if (p->skip_locking) { 16905cd57b2cSChris Mason b = btrfs_root_node(root); 1691bd681513SChris Mason level = btrfs_header_level(b); 1692bd681513SChris Mason } else { 1693bd681513SChris Mason /* we don't know the level of the root node 1694bd681513SChris Mason * until we actually have it read locked 1695bd681513SChris Mason */ 1696bd681513SChris Mason b = btrfs_read_lock_root_node(root); 1697bd681513SChris Mason level = btrfs_header_level(b); 1698bd681513SChris Mason if (level <= write_lock_level) { 1699bd681513SChris Mason /* whoops, must trade for write lock */ 1700bd681513SChris Mason btrfs_tree_read_unlock(b); 1701bd681513SChris Mason free_extent_buffer(b); 1702925baeddSChris Mason b = btrfs_lock_root_node(root); 1703bd681513SChris Mason root_lock = BTRFS_WRITE_LOCK; 1704bd681513SChris Mason 1705bd681513SChris Mason /* the level might have changed, check again */ 1706bd681513SChris Mason level = btrfs_header_level(b); 17075d4f98a2SYan Zheng } 1708bd681513SChris Mason } 1709bd681513SChris Mason } 1710bd681513SChris Mason p->nodes[level] = b; 1711bd681513SChris Mason if (!p->skip_locking) 1712bd681513SChris Mason p->locks[level] = root_lock; 1713925baeddSChris Mason 1714eb60ceacSChris Mason while (b) { 17155f39d397SChris Mason level = btrfs_header_level(b); 171665b51a00SChris Mason 171765b51a00SChris Mason /* 171865b51a00SChris Mason * setup the path here so we can release it under lock 171965b51a00SChris Mason * contention with the cow code 172065b51a00SChris Mason */ 172102217ed2SChris Mason if (cow) { 1722c8c42864SChris Mason /* 1723c8c42864SChris Mason * if we don't really need to cow this block 1724c8c42864SChris Mason * then we don't want to set the path blocking, 1725c8c42864SChris Mason * so we test it here 1726c8c42864SChris Mason */ 17275d4f98a2SYan Zheng if (!should_cow_block(trans, root, b)) 172865b51a00SChris Mason goto cow_done; 17295d4f98a2SYan Zheng 1730b4ce94deSChris Mason btrfs_set_path_blocking(p); 1731b4ce94deSChris Mason 1732bd681513SChris Mason /* 1733bd681513SChris Mason * must have write locks on this node and the 1734bd681513SChris Mason * parent 1735bd681513SChris Mason */ 1736bd681513SChris Mason if (level + 1 > write_lock_level) { 1737bd681513SChris Mason write_lock_level = level + 1; 1738bd681513SChris Mason btrfs_release_path(p); 1739bd681513SChris Mason goto again; 1740bd681513SChris Mason } 1741bd681513SChris Mason 174233c66f43SYan Zheng err = btrfs_cow_block(trans, root, b, 1743e20d96d6SChris Mason p->nodes[level + 1], 17449fa8cfe7SChris Mason p->slots[level + 1], &b); 174533c66f43SYan Zheng if (err) { 174633c66f43SYan Zheng ret = err; 174765b51a00SChris Mason goto done; 174854aa1f4dSChris Mason } 174902217ed2SChris Mason } 175065b51a00SChris Mason cow_done: 175102217ed2SChris Mason BUG_ON(!cow && ins_len); 175265b51a00SChris Mason 1753eb60ceacSChris Mason p->nodes[level] = b; 1754bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 1755b4ce94deSChris Mason 1756b4ce94deSChris Mason /* 1757b4ce94deSChris Mason * we have a lock on b and as long as we aren't changing 1758b4ce94deSChris Mason * the tree, there is no way to for the items in b to change. 1759b4ce94deSChris Mason * It is safe to drop the lock on our parent before we 1760b4ce94deSChris Mason * go through the expensive btree search on b. 1761b4ce94deSChris Mason * 1762b4ce94deSChris Mason * If cow is true, then we might be changing slot zero, 1763b4ce94deSChris Mason * which may require changing the parent. So, we can't 1764b4ce94deSChris Mason * drop the lock until after we know which slot we're 1765b4ce94deSChris Mason * operating on. 1766b4ce94deSChris Mason */ 1767b4ce94deSChris Mason if (!cow) 1768b4ce94deSChris Mason btrfs_unlock_up_safe(p, level + 1); 1769b4ce94deSChris Mason 17705f39d397SChris Mason ret = bin_search(b, key, level, &slot); 1771b4ce94deSChris Mason 17725f39d397SChris Mason if (level != 0) { 177333c66f43SYan Zheng int dec = 0; 177433c66f43SYan Zheng if (ret && slot > 0) { 177533c66f43SYan Zheng dec = 1; 1776be0e5c09SChris Mason slot -= 1; 177733c66f43SYan Zheng } 1778be0e5c09SChris Mason p->slots[level] = slot; 177933c66f43SYan Zheng err = setup_nodes_for_search(trans, root, p, b, level, 1780bd681513SChris Mason ins_len, &write_lock_level); 178133c66f43SYan Zheng if (err == -EAGAIN) 1782b4ce94deSChris Mason goto again; 178333c66f43SYan Zheng if (err) { 178433c66f43SYan Zheng ret = err; 178565b51a00SChris Mason goto done; 178633c66f43SYan Zheng } 17875c680ed6SChris Mason b = p->nodes[level]; 17885c680ed6SChris Mason slot = p->slots[level]; 1789b4ce94deSChris Mason 1790bd681513SChris Mason /* 1791bd681513SChris Mason * slot 0 is special, if we change the key 1792bd681513SChris Mason * we have to update the parent pointer 1793bd681513SChris Mason * which means we must have a write lock 1794bd681513SChris Mason * on the parent 1795bd681513SChris Mason */ 1796bd681513SChris Mason if (slot == 0 && cow && 1797bd681513SChris Mason write_lock_level < level + 1) { 1798bd681513SChris Mason write_lock_level = level + 1; 1799bd681513SChris Mason btrfs_release_path(p); 1800bd681513SChris Mason goto again; 1801bd681513SChris Mason } 1802bd681513SChris Mason 1803f9efa9c7SChris Mason unlock_up(p, level, lowest_unlock); 1804f9efa9c7SChris Mason 1805925baeddSChris Mason if (level == lowest_level) { 180633c66f43SYan Zheng if (dec) 180733c66f43SYan Zheng p->slots[level]++; 18085b21f2edSZheng Yan goto done; 1809925baeddSChris Mason } 1810ca7a79adSChris Mason 181133c66f43SYan Zheng err = read_block_for_search(trans, root, p, 1812c8c42864SChris Mason &b, level, slot, key); 181333c66f43SYan Zheng if (err == -EAGAIN) 1814051e1b9fSChris Mason goto again; 181533c66f43SYan Zheng if (err) { 181633c66f43SYan Zheng ret = err; 181776a05b35SChris Mason goto done; 181833c66f43SYan Zheng } 181976a05b35SChris Mason 1820b4ce94deSChris Mason if (!p->skip_locking) { 1821bd681513SChris Mason level = btrfs_header_level(b); 1822bd681513SChris Mason if (level <= write_lock_level) { 1823bd681513SChris Mason err = btrfs_try_tree_write_lock(b); 182433c66f43SYan Zheng if (!err) { 1825b4ce94deSChris Mason btrfs_set_path_blocking(p); 1826925baeddSChris Mason btrfs_tree_lock(b); 1827bd681513SChris Mason btrfs_clear_path_blocking(p, b, 1828bd681513SChris Mason BTRFS_WRITE_LOCK); 1829b4ce94deSChris Mason } 1830bd681513SChris Mason p->locks[level] = BTRFS_WRITE_LOCK; 1831bd681513SChris Mason } else { 1832bd681513SChris Mason err = btrfs_try_tree_read_lock(b); 1833bd681513SChris Mason if (!err) { 1834bd681513SChris Mason btrfs_set_path_blocking(p); 1835bd681513SChris Mason btrfs_tree_read_lock(b); 1836bd681513SChris Mason btrfs_clear_path_blocking(p, b, 1837bd681513SChris Mason BTRFS_READ_LOCK); 1838bd681513SChris Mason } 1839bd681513SChris Mason p->locks[level] = BTRFS_READ_LOCK; 1840bd681513SChris Mason } 1841bd681513SChris Mason p->nodes[level] = b; 1842b4ce94deSChris Mason } 1843be0e5c09SChris Mason } else { 1844be0e5c09SChris Mason p->slots[level] = slot; 184587b29b20SYan Zheng if (ins_len > 0 && 184687b29b20SYan Zheng btrfs_leaf_free_space(root, b) < ins_len) { 1847bd681513SChris Mason if (write_lock_level < 1) { 1848bd681513SChris Mason write_lock_level = 1; 1849bd681513SChris Mason btrfs_release_path(p); 1850bd681513SChris Mason goto again; 1851bd681513SChris Mason } 1852bd681513SChris Mason 1853b4ce94deSChris Mason btrfs_set_path_blocking(p); 185433c66f43SYan Zheng err = split_leaf(trans, root, key, 1855cc0c5538SChris Mason p, ins_len, ret == 0); 1856bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 1857b4ce94deSChris Mason 185833c66f43SYan Zheng BUG_ON(err > 0); 185933c66f43SYan Zheng if (err) { 186033c66f43SYan Zheng ret = err; 186165b51a00SChris Mason goto done; 186265b51a00SChris Mason } 18635c680ed6SChris Mason } 1864459931ecSChris Mason if (!p->search_for_split) 1865925baeddSChris Mason unlock_up(p, level, lowest_unlock); 186665b51a00SChris Mason goto done; 186765b51a00SChris Mason } 186865b51a00SChris Mason } 186965b51a00SChris Mason ret = 1; 187065b51a00SChris Mason done: 1871b4ce94deSChris Mason /* 1872b4ce94deSChris Mason * we don't really know what they plan on doing with the path 1873b4ce94deSChris Mason * from here on, so for now just mark it as blocking 1874b4ce94deSChris Mason */ 1875b9473439SChris Mason if (!p->leave_spinning) 1876b4ce94deSChris Mason btrfs_set_path_blocking(p); 187776a05b35SChris Mason if (ret < 0) 1878b3b4aa74SDavid Sterba btrfs_release_path(p); 1879be0e5c09SChris Mason return ret; 1880be0e5c09SChris Mason } 1881be0e5c09SChris Mason 188274123bd7SChris Mason /* 188374123bd7SChris Mason * adjust the pointers going up the tree, starting at level 188474123bd7SChris Mason * making sure the right key of each node is points to 'key'. 188574123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 188674123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 188774123bd7SChris Mason * higher levels 1888aa5d6bedSChris Mason * 188974123bd7SChris Mason */ 1890143bede5SJeff Mahoney static void fixup_low_keys(struct btrfs_trans_handle *trans, 18915f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 18925f39d397SChris Mason struct btrfs_disk_key *key, int level) 1893be0e5c09SChris Mason { 1894be0e5c09SChris Mason int i; 18955f39d397SChris Mason struct extent_buffer *t; 18965f39d397SChris Mason 1897234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1898be0e5c09SChris Mason int tslot = path->slots[i]; 1899eb60ceacSChris Mason if (!path->nodes[i]) 1900be0e5c09SChris Mason break; 19015f39d397SChris Mason t = path->nodes[i]; 19025f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 1903d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 1904be0e5c09SChris Mason if (tslot != 0) 1905be0e5c09SChris Mason break; 1906be0e5c09SChris Mason } 1907be0e5c09SChris Mason } 1908be0e5c09SChris Mason 190974123bd7SChris Mason /* 191031840ae1SZheng Yan * update item key. 191131840ae1SZheng Yan * 191231840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 191331840ae1SZheng Yan * that the new key won't break the order 191431840ae1SZheng Yan */ 1915143bede5SJeff Mahoney void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, 191631840ae1SZheng Yan struct btrfs_root *root, struct btrfs_path *path, 191731840ae1SZheng Yan struct btrfs_key *new_key) 191831840ae1SZheng Yan { 191931840ae1SZheng Yan struct btrfs_disk_key disk_key; 192031840ae1SZheng Yan struct extent_buffer *eb; 192131840ae1SZheng Yan int slot; 192231840ae1SZheng Yan 192331840ae1SZheng Yan eb = path->nodes[0]; 192431840ae1SZheng Yan slot = path->slots[0]; 192531840ae1SZheng Yan if (slot > 0) { 192631840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 1927143bede5SJeff Mahoney BUG_ON(comp_keys(&disk_key, new_key) >= 0); 192831840ae1SZheng Yan } 192931840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 193031840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 1931143bede5SJeff Mahoney BUG_ON(comp_keys(&disk_key, new_key) <= 0); 193231840ae1SZheng Yan } 193331840ae1SZheng Yan 193431840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 193531840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 193631840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 193731840ae1SZheng Yan if (slot == 0) 193831840ae1SZheng Yan fixup_low_keys(trans, root, path, &disk_key, 1); 193931840ae1SZheng Yan } 194031840ae1SZheng Yan 194131840ae1SZheng Yan /* 194274123bd7SChris Mason * try to push data from one node into the next node left in the 194379f95c82SChris Mason * tree. 1944aa5d6bedSChris Mason * 1945aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1946aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 194774123bd7SChris Mason */ 194898ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 194998ed5174SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 1950971a1f66SChris Mason struct extent_buffer *src, int empty) 1951be0e5c09SChris Mason { 1952be0e5c09SChris Mason int push_items = 0; 1953bb803951SChris Mason int src_nritems; 1954bb803951SChris Mason int dst_nritems; 1955aa5d6bedSChris Mason int ret = 0; 1956be0e5c09SChris Mason 19575f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 19585f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1959123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 19607bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 19617bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 196254aa1f4dSChris Mason 1963bce4eae9SChris Mason if (!empty && src_nritems <= 8) 1964971a1f66SChris Mason return 1; 1965971a1f66SChris Mason 1966d397712bSChris Mason if (push_items <= 0) 1967be0e5c09SChris Mason return 1; 1968be0e5c09SChris Mason 1969bce4eae9SChris Mason if (empty) { 1970971a1f66SChris Mason push_items = min(src_nritems, push_items); 1971bce4eae9SChris Mason if (push_items < src_nritems) { 1972bce4eae9SChris Mason /* leave at least 8 pointers in the node if 1973bce4eae9SChris Mason * we aren't going to empty it 1974bce4eae9SChris Mason */ 1975bce4eae9SChris Mason if (src_nritems - push_items < 8) { 1976bce4eae9SChris Mason if (push_items <= 8) 1977bce4eae9SChris Mason return 1; 1978bce4eae9SChris Mason push_items -= 8; 1979bce4eae9SChris Mason } 1980bce4eae9SChris Mason } 1981bce4eae9SChris Mason } else 1982bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 198379f95c82SChris Mason 19845f39d397SChris Mason copy_extent_buffer(dst, src, 19855f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 19865f39d397SChris Mason btrfs_node_key_ptr_offset(0), 1987123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 19885f39d397SChris Mason 1989bb803951SChris Mason if (push_items < src_nritems) { 19905f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 19915f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 1992e2fa7227SChris Mason (src_nritems - push_items) * 1993123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1994bb803951SChris Mason } 19955f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 19965f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 19975f39d397SChris Mason btrfs_mark_buffer_dirty(src); 19985f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 199931840ae1SZheng Yan 2000bb803951SChris Mason return ret; 2001be0e5c09SChris Mason } 2002be0e5c09SChris Mason 200397571fd0SChris Mason /* 200479f95c82SChris Mason * try to push data from one node into the next node right in the 200579f95c82SChris Mason * tree. 200679f95c82SChris Mason * 200779f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 200879f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 200979f95c82SChris Mason * 201079f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 201179f95c82SChris Mason */ 20125f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 20135f39d397SChris Mason struct btrfs_root *root, 20145f39d397SChris Mason struct extent_buffer *dst, 20155f39d397SChris Mason struct extent_buffer *src) 201679f95c82SChris Mason { 201779f95c82SChris Mason int push_items = 0; 201879f95c82SChris Mason int max_push; 201979f95c82SChris Mason int src_nritems; 202079f95c82SChris Mason int dst_nritems; 202179f95c82SChris Mason int ret = 0; 202279f95c82SChris Mason 20237bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 20247bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 20257bb86316SChris Mason 20265f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 20275f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 2028123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 2029d397712bSChris Mason if (push_items <= 0) 203079f95c82SChris Mason return 1; 2031bce4eae9SChris Mason 2032d397712bSChris Mason if (src_nritems < 4) 2033bce4eae9SChris Mason return 1; 203479f95c82SChris Mason 203579f95c82SChris Mason max_push = src_nritems / 2 + 1; 203679f95c82SChris Mason /* don't try to empty the node */ 2037d397712bSChris Mason if (max_push >= src_nritems) 203879f95c82SChris Mason return 1; 2039252c38f0SYan 204079f95c82SChris Mason if (max_push < push_items) 204179f95c82SChris Mason push_items = max_push; 204279f95c82SChris Mason 20435f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 20445f39d397SChris Mason btrfs_node_key_ptr_offset(0), 20455f39d397SChris Mason (dst_nritems) * 20465f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 2047d6025579SChris Mason 20485f39d397SChris Mason copy_extent_buffer(dst, src, 20495f39d397SChris Mason btrfs_node_key_ptr_offset(0), 20505f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 2051123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 205279f95c82SChris Mason 20535f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 20545f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 205579f95c82SChris Mason 20565f39d397SChris Mason btrfs_mark_buffer_dirty(src); 20575f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 205831840ae1SZheng Yan 205979f95c82SChris Mason return ret; 206079f95c82SChris Mason } 206179f95c82SChris Mason 206279f95c82SChris Mason /* 206397571fd0SChris Mason * helper function to insert a new root level in the tree. 206497571fd0SChris Mason * A new node is allocated, and a single item is inserted to 206597571fd0SChris Mason * point to the existing root 2066aa5d6bedSChris Mason * 2067aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 206897571fd0SChris Mason */ 2069d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 20705f39d397SChris Mason struct btrfs_root *root, 20715f39d397SChris Mason struct btrfs_path *path, int level) 207274123bd7SChris Mason { 20737bb86316SChris Mason u64 lower_gen; 20745f39d397SChris Mason struct extent_buffer *lower; 20755f39d397SChris Mason struct extent_buffer *c; 2076925baeddSChris Mason struct extent_buffer *old; 20775f39d397SChris Mason struct btrfs_disk_key lower_key; 20785c680ed6SChris Mason 20795c680ed6SChris Mason BUG_ON(path->nodes[level]); 20805c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 20815c680ed6SChris Mason 20827bb86316SChris Mason lower = path->nodes[level-1]; 20837bb86316SChris Mason if (level == 1) 20847bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 20857bb86316SChris Mason else 20867bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 20877bb86316SChris Mason 208831840ae1SZheng Yan c = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 20895d4f98a2SYan Zheng root->root_key.objectid, &lower_key, 209066d7e7f0SArne Jansen level, root->node->start, 0, 0); 20915f39d397SChris Mason if (IS_ERR(c)) 20925f39d397SChris Mason return PTR_ERR(c); 2093925baeddSChris Mason 2094f0486c68SYan, Zheng root_add_used(root, root->nodesize); 2095f0486c68SYan, Zheng 20965d4f98a2SYan Zheng memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header)); 20975f39d397SChris Mason btrfs_set_header_nritems(c, 1); 20985f39d397SChris Mason btrfs_set_header_level(c, level); 2099db94535dSChris Mason btrfs_set_header_bytenr(c, c->start); 21005f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 21015d4f98a2SYan Zheng btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV); 21025f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 2103d5719762SChris Mason 21045f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 21055f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 21065f39d397SChris Mason BTRFS_FSID_SIZE); 2107e17cade2SChris Mason 2108e17cade2SChris Mason write_extent_buffer(c, root->fs_info->chunk_tree_uuid, 2109e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(c), 2110e17cade2SChris Mason BTRFS_UUID_SIZE); 2111e17cade2SChris Mason 21125f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 2113db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 21147bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 211531840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 21167bb86316SChris Mason 21177bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 21185f39d397SChris Mason 21195f39d397SChris Mason btrfs_mark_buffer_dirty(c); 2120d5719762SChris Mason 2121925baeddSChris Mason old = root->node; 2122240f62c8SChris Mason rcu_assign_pointer(root->node, c); 2123925baeddSChris Mason 2124925baeddSChris Mason /* the super has an extra ref to root->node */ 2125925baeddSChris Mason free_extent_buffer(old); 2126925baeddSChris Mason 21270b86a832SChris Mason add_root_to_dirty_list(root); 21285f39d397SChris Mason extent_buffer_get(c); 21295f39d397SChris Mason path->nodes[level] = c; 2130bd681513SChris Mason path->locks[level] = BTRFS_WRITE_LOCK; 213174123bd7SChris Mason path->slots[level] = 0; 213274123bd7SChris Mason return 0; 213374123bd7SChris Mason } 21345c680ed6SChris Mason 21355c680ed6SChris Mason /* 21365c680ed6SChris Mason * worker function to insert a single pointer in a node. 21375c680ed6SChris Mason * the node should have enough room for the pointer already 213897571fd0SChris Mason * 21395c680ed6SChris Mason * slot and level indicate where you want the key to go, and 21405c680ed6SChris Mason * blocknr is the block the key points to. 21415c680ed6SChris Mason */ 2142143bede5SJeff Mahoney static void insert_ptr(struct btrfs_trans_handle *trans, 2143143bede5SJeff Mahoney struct btrfs_root *root, struct btrfs_path *path, 2144143bede5SJeff Mahoney struct btrfs_disk_key *key, u64 bytenr, 2145143bede5SJeff Mahoney int slot, int level) 21465c680ed6SChris Mason { 21475f39d397SChris Mason struct extent_buffer *lower; 21485c680ed6SChris Mason int nritems; 21495c680ed6SChris Mason 21505c680ed6SChris Mason BUG_ON(!path->nodes[level]); 2151f0486c68SYan, Zheng btrfs_assert_tree_locked(path->nodes[level]); 21525f39d397SChris Mason lower = path->nodes[level]; 21535f39d397SChris Mason nritems = btrfs_header_nritems(lower); 2154c293498bSStoyan Gaydarov BUG_ON(slot > nritems); 2155143bede5SJeff Mahoney BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(root)); 215674123bd7SChris Mason if (slot != nritems) { 21575f39d397SChris Mason memmove_extent_buffer(lower, 21585f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 21595f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 2160123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 216174123bd7SChris Mason } 21625f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 2163db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 216474493f7aSChris Mason WARN_ON(trans->transid == 0); 216574493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 21665f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 21675f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 216874123bd7SChris Mason } 216974123bd7SChris Mason 217097571fd0SChris Mason /* 217197571fd0SChris Mason * split the node at the specified level in path in two. 217297571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 217397571fd0SChris Mason * 217497571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 217597571fd0SChris Mason * left and right, if either one works, it returns right away. 2176aa5d6bedSChris Mason * 2177aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 217897571fd0SChris Mason */ 2179e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 2180e02119d5SChris Mason struct btrfs_root *root, 2181e02119d5SChris Mason struct btrfs_path *path, int level) 2182be0e5c09SChris Mason { 21835f39d397SChris Mason struct extent_buffer *c; 21845f39d397SChris Mason struct extent_buffer *split; 21855f39d397SChris Mason struct btrfs_disk_key disk_key; 2186be0e5c09SChris Mason int mid; 21875c680ed6SChris Mason int ret; 21887518a238SChris Mason u32 c_nritems; 2189be0e5c09SChris Mason 21905f39d397SChris Mason c = path->nodes[level]; 21917bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 21925f39d397SChris Mason if (c == root->node) { 21935c680ed6SChris Mason /* trying to split the root, lets make a new one */ 2194e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 21955c680ed6SChris Mason if (ret) 21965c680ed6SChris Mason return ret; 2197b3612421SChris Mason } else { 2198e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 21995f39d397SChris Mason c = path->nodes[level]; 22005f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 2201c448acf0SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) 2202e66f709bSChris Mason return 0; 220354aa1f4dSChris Mason if (ret < 0) 220454aa1f4dSChris Mason return ret; 22055c680ed6SChris Mason } 2206e66f709bSChris Mason 22075f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 22085d4f98a2SYan Zheng mid = (c_nritems + 1) / 2; 22095d4f98a2SYan Zheng btrfs_node_key(c, &disk_key, mid); 22107bb86316SChris Mason 22115d4f98a2SYan Zheng split = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 22127bb86316SChris Mason root->root_key.objectid, 221366d7e7f0SArne Jansen &disk_key, level, c->start, 0, 0); 22145f39d397SChris Mason if (IS_ERR(split)) 22155f39d397SChris Mason return PTR_ERR(split); 221654aa1f4dSChris Mason 2217f0486c68SYan, Zheng root_add_used(root, root->nodesize); 2218f0486c68SYan, Zheng 22195d4f98a2SYan Zheng memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header)); 22205f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 2221db94535dSChris Mason btrfs_set_header_bytenr(split, split->start); 22225f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 22235d4f98a2SYan Zheng btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV); 22245f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 22255f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 22265f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 22275f39d397SChris Mason BTRFS_FSID_SIZE); 2228e17cade2SChris Mason write_extent_buffer(split, root->fs_info->chunk_tree_uuid, 2229e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(split), 2230e17cade2SChris Mason BTRFS_UUID_SIZE); 22315f39d397SChris Mason 22325f39d397SChris Mason 22335f39d397SChris Mason copy_extent_buffer(split, c, 22345f39d397SChris Mason btrfs_node_key_ptr_offset(0), 22355f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2236123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 22375f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 22385f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2239aa5d6bedSChris Mason ret = 0; 2240aa5d6bedSChris Mason 22415f39d397SChris Mason btrfs_mark_buffer_dirty(c); 22425f39d397SChris Mason btrfs_mark_buffer_dirty(split); 22435f39d397SChris Mason 2244143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, split->start, 2245143bede5SJeff Mahoney path->slots[level + 1] + 1, level + 1); 2246aa5d6bedSChris Mason 22475de08d7dSChris Mason if (path->slots[level] >= mid) { 22485c680ed6SChris Mason path->slots[level] -= mid; 2249925baeddSChris Mason btrfs_tree_unlock(c); 22505f39d397SChris Mason free_extent_buffer(c); 22515f39d397SChris Mason path->nodes[level] = split; 22525c680ed6SChris Mason path->slots[level + 1] += 1; 2253eb60ceacSChris Mason } else { 2254925baeddSChris Mason btrfs_tree_unlock(split); 22555f39d397SChris Mason free_extent_buffer(split); 2256be0e5c09SChris Mason } 2257aa5d6bedSChris Mason return ret; 2258be0e5c09SChris Mason } 2259be0e5c09SChris Mason 226074123bd7SChris Mason /* 226174123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 226274123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 226374123bd7SChris Mason * space used both by the item structs and the item data 226474123bd7SChris Mason */ 22655f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2266be0e5c09SChris Mason { 2267be0e5c09SChris Mason int data_len; 22685f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2269d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2270be0e5c09SChris Mason 2271be0e5c09SChris Mason if (!nr) 2272be0e5c09SChris Mason return 0; 22735f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 22745f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 22750783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2276d4dbff95SChris Mason WARN_ON(data_len < 0); 2277be0e5c09SChris Mason return data_len; 2278be0e5c09SChris Mason } 2279be0e5c09SChris Mason 228074123bd7SChris Mason /* 2281d4dbff95SChris Mason * The space between the end of the leaf items and 2282d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2283d4dbff95SChris Mason * the leaf has left for both items and data 2284d4dbff95SChris Mason */ 2285d397712bSChris Mason noinline int btrfs_leaf_free_space(struct btrfs_root *root, 2286e02119d5SChris Mason struct extent_buffer *leaf) 2287d4dbff95SChris Mason { 22885f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 22895f39d397SChris Mason int ret; 22905f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 22915f39d397SChris Mason if (ret < 0) { 2292d397712bSChris Mason printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, " 2293d397712bSChris Mason "used %d nritems %d\n", 2294ae2f5411SJens Axboe ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), 22955f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 22965f39d397SChris Mason } 22975f39d397SChris Mason return ret; 2298d4dbff95SChris Mason } 2299d4dbff95SChris Mason 230099d8f83cSChris Mason /* 230199d8f83cSChris Mason * min slot controls the lowest index we're willing to push to the 230299d8f83cSChris Mason * right. We'll push up to and including min_slot, but no lower 230399d8f83cSChris Mason */ 230444871b1bSChris Mason static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, 230544871b1bSChris Mason struct btrfs_root *root, 230644871b1bSChris Mason struct btrfs_path *path, 230744871b1bSChris Mason int data_size, int empty, 230844871b1bSChris Mason struct extent_buffer *right, 230999d8f83cSChris Mason int free_space, u32 left_nritems, 231099d8f83cSChris Mason u32 min_slot) 231100ec4c51SChris Mason { 23125f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 231344871b1bSChris Mason struct extent_buffer *upper = path->nodes[1]; 23145f39d397SChris Mason struct btrfs_disk_key disk_key; 231500ec4c51SChris Mason int slot; 231634a38218SChris Mason u32 i; 231700ec4c51SChris Mason int push_space = 0; 231800ec4c51SChris Mason int push_items = 0; 23190783fcfcSChris Mason struct btrfs_item *item; 232034a38218SChris Mason u32 nr; 23217518a238SChris Mason u32 right_nritems; 23225f39d397SChris Mason u32 data_end; 2323db94535dSChris Mason u32 this_item_size; 232400ec4c51SChris Mason 232534a38218SChris Mason if (empty) 232634a38218SChris Mason nr = 0; 232734a38218SChris Mason else 232899d8f83cSChris Mason nr = max_t(u32, 1, min_slot); 232934a38218SChris Mason 233031840ae1SZheng Yan if (path->slots[0] >= left_nritems) 233187b29b20SYan Zheng push_space += data_size; 233231840ae1SZheng Yan 233344871b1bSChris Mason slot = path->slots[1]; 233434a38218SChris Mason i = left_nritems - 1; 233534a38218SChris Mason while (i >= nr) { 23365f39d397SChris Mason item = btrfs_item_nr(left, i); 2337db94535dSChris Mason 233831840ae1SZheng Yan if (!empty && push_items > 0) { 233931840ae1SZheng Yan if (path->slots[0] > i) 234031840ae1SZheng Yan break; 234131840ae1SZheng Yan if (path->slots[0] == i) { 234231840ae1SZheng Yan int space = btrfs_leaf_free_space(root, left); 234331840ae1SZheng Yan if (space + push_space * 2 > free_space) 234431840ae1SZheng Yan break; 234531840ae1SZheng Yan } 234631840ae1SZheng Yan } 234731840ae1SZheng Yan 234800ec4c51SChris Mason if (path->slots[0] == i) 234987b29b20SYan Zheng push_space += data_size; 2350db94535dSChris Mason 2351db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 2352db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 235300ec4c51SChris Mason break; 235431840ae1SZheng Yan 235500ec4c51SChris Mason push_items++; 2356db94535dSChris Mason push_space += this_item_size + sizeof(*item); 235734a38218SChris Mason if (i == 0) 235834a38218SChris Mason break; 235934a38218SChris Mason i--; 2360db94535dSChris Mason } 23615f39d397SChris Mason 2362925baeddSChris Mason if (push_items == 0) 2363925baeddSChris Mason goto out_unlock; 23645f39d397SChris Mason 236534a38218SChris Mason if (!empty && push_items == left_nritems) 2366a429e513SChris Mason WARN_ON(1); 23675f39d397SChris Mason 236800ec4c51SChris Mason /* push left to right */ 23695f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 237034a38218SChris Mason 23715f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 2372123abc88SChris Mason push_space -= leaf_data_end(root, left); 23735f39d397SChris Mason 237400ec4c51SChris Mason /* make room in the right data area */ 23755f39d397SChris Mason data_end = leaf_data_end(root, right); 23765f39d397SChris Mason memmove_extent_buffer(right, 23775f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 23785f39d397SChris Mason btrfs_leaf_data(right) + data_end, 23795f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 23805f39d397SChris Mason 238100ec4c51SChris Mason /* copy from the left data area */ 23825f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 2383d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2384d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 2385d6025579SChris Mason push_space); 23865f39d397SChris Mason 23875f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 23885f39d397SChris Mason btrfs_item_nr_offset(0), 23890783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 23905f39d397SChris Mason 239100ec4c51SChris Mason /* copy the items from left to right */ 23925f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 23935f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 23940783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 239500ec4c51SChris Mason 239600ec4c51SChris Mason /* update the item pointers */ 23977518a238SChris Mason right_nritems += push_items; 23985f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 2399123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 24007518a238SChris Mason for (i = 0; i < right_nritems; i++) { 24015f39d397SChris Mason item = btrfs_item_nr(right, i); 2402db94535dSChris Mason push_space -= btrfs_item_size(right, item); 2403db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2404db94535dSChris Mason } 2405db94535dSChris Mason 24067518a238SChris Mason left_nritems -= push_items; 24075f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 240800ec4c51SChris Mason 240934a38218SChris Mason if (left_nritems) 24105f39d397SChris Mason btrfs_mark_buffer_dirty(left); 2411f0486c68SYan, Zheng else 2412f0486c68SYan, Zheng clean_tree_block(trans, root, left); 2413f0486c68SYan, Zheng 24145f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2415a429e513SChris Mason 24165f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 24175f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2418d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 241902217ed2SChris Mason 242000ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 24217518a238SChris Mason if (path->slots[0] >= left_nritems) { 24227518a238SChris Mason path->slots[0] -= left_nritems; 2423925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2424925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2425925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 24265f39d397SChris Mason free_extent_buffer(path->nodes[0]); 24275f39d397SChris Mason path->nodes[0] = right; 242800ec4c51SChris Mason path->slots[1] += 1; 242900ec4c51SChris Mason } else { 2430925baeddSChris Mason btrfs_tree_unlock(right); 24315f39d397SChris Mason free_extent_buffer(right); 243200ec4c51SChris Mason } 243300ec4c51SChris Mason return 0; 2434925baeddSChris Mason 2435925baeddSChris Mason out_unlock: 2436925baeddSChris Mason btrfs_tree_unlock(right); 2437925baeddSChris Mason free_extent_buffer(right); 2438925baeddSChris Mason return 1; 243900ec4c51SChris Mason } 2440925baeddSChris Mason 244100ec4c51SChris Mason /* 244244871b1bSChris Mason * push some data in the path leaf to the right, trying to free up at 244374123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 244444871b1bSChris Mason * 244544871b1bSChris Mason * returns 1 if the push failed because the other node didn't have enough 244644871b1bSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 244799d8f83cSChris Mason * 244899d8f83cSChris Mason * this will push starting from min_slot to the end of the leaf. It won't 244999d8f83cSChris Mason * push any slot lower than min_slot 245074123bd7SChris Mason */ 245144871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 245299d8f83cSChris Mason *root, struct btrfs_path *path, 245399d8f83cSChris Mason int min_data_size, int data_size, 245499d8f83cSChris Mason int empty, u32 min_slot) 2455be0e5c09SChris Mason { 245644871b1bSChris Mason struct extent_buffer *left = path->nodes[0]; 245744871b1bSChris Mason struct extent_buffer *right; 245844871b1bSChris Mason struct extent_buffer *upper; 245944871b1bSChris Mason int slot; 246044871b1bSChris Mason int free_space; 246144871b1bSChris Mason u32 left_nritems; 246244871b1bSChris Mason int ret; 246344871b1bSChris Mason 246444871b1bSChris Mason if (!path->nodes[1]) 246544871b1bSChris Mason return 1; 246644871b1bSChris Mason 246744871b1bSChris Mason slot = path->slots[1]; 246844871b1bSChris Mason upper = path->nodes[1]; 246944871b1bSChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 247044871b1bSChris Mason return 1; 247144871b1bSChris Mason 247244871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 247344871b1bSChris Mason 247444871b1bSChris Mason right = read_node_slot(root, upper, slot + 1); 247591ca338dSTsutomu Itoh if (right == NULL) 247691ca338dSTsutomu Itoh return 1; 247791ca338dSTsutomu Itoh 247844871b1bSChris Mason btrfs_tree_lock(right); 247944871b1bSChris Mason btrfs_set_lock_blocking(right); 248044871b1bSChris Mason 248144871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 248244871b1bSChris Mason if (free_space < data_size) 248344871b1bSChris Mason goto out_unlock; 248444871b1bSChris Mason 248544871b1bSChris Mason /* cow and double check */ 248644871b1bSChris Mason ret = btrfs_cow_block(trans, root, right, upper, 248744871b1bSChris Mason slot + 1, &right); 248844871b1bSChris Mason if (ret) 248944871b1bSChris Mason goto out_unlock; 249044871b1bSChris Mason 249144871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 249244871b1bSChris Mason if (free_space < data_size) 249344871b1bSChris Mason goto out_unlock; 249444871b1bSChris Mason 249544871b1bSChris Mason left_nritems = btrfs_header_nritems(left); 249644871b1bSChris Mason if (left_nritems == 0) 249744871b1bSChris Mason goto out_unlock; 249844871b1bSChris Mason 249999d8f83cSChris Mason return __push_leaf_right(trans, root, path, min_data_size, empty, 250099d8f83cSChris Mason right, free_space, left_nritems, min_slot); 250144871b1bSChris Mason out_unlock: 250244871b1bSChris Mason btrfs_tree_unlock(right); 250344871b1bSChris Mason free_extent_buffer(right); 250444871b1bSChris Mason return 1; 250544871b1bSChris Mason } 250644871b1bSChris Mason 250744871b1bSChris Mason /* 250844871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 250944871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 251099d8f83cSChris Mason * 251199d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 251299d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the 251399d8f83cSChris Mason * items 251444871b1bSChris Mason */ 251544871b1bSChris Mason static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, 251644871b1bSChris Mason struct btrfs_root *root, 251744871b1bSChris Mason struct btrfs_path *path, int data_size, 251844871b1bSChris Mason int empty, struct extent_buffer *left, 251999d8f83cSChris Mason int free_space, u32 right_nritems, 252099d8f83cSChris Mason u32 max_slot) 252144871b1bSChris Mason { 25225f39d397SChris Mason struct btrfs_disk_key disk_key; 25235f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 2524be0e5c09SChris Mason int i; 2525be0e5c09SChris Mason int push_space = 0; 2526be0e5c09SChris Mason int push_items = 0; 25270783fcfcSChris Mason struct btrfs_item *item; 25287518a238SChris Mason u32 old_left_nritems; 252934a38218SChris Mason u32 nr; 2530aa5d6bedSChris Mason int ret = 0; 2531db94535dSChris Mason u32 this_item_size; 2532db94535dSChris Mason u32 old_left_item_size; 2533be0e5c09SChris Mason 253434a38218SChris Mason if (empty) 253599d8f83cSChris Mason nr = min(right_nritems, max_slot); 253634a38218SChris Mason else 253799d8f83cSChris Mason nr = min(right_nritems - 1, max_slot); 253834a38218SChris Mason 253934a38218SChris Mason for (i = 0; i < nr; i++) { 25405f39d397SChris Mason item = btrfs_item_nr(right, i); 2541db94535dSChris Mason 254231840ae1SZheng Yan if (!empty && push_items > 0) { 254331840ae1SZheng Yan if (path->slots[0] < i) 254431840ae1SZheng Yan break; 254531840ae1SZheng Yan if (path->slots[0] == i) { 254631840ae1SZheng Yan int space = btrfs_leaf_free_space(root, right); 254731840ae1SZheng Yan if (space + push_space * 2 > free_space) 254831840ae1SZheng Yan break; 254931840ae1SZheng Yan } 255031840ae1SZheng Yan } 255131840ae1SZheng Yan 2552be0e5c09SChris Mason if (path->slots[0] == i) 255387b29b20SYan Zheng push_space += data_size; 2554db94535dSChris Mason 2555db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 2556db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 2557be0e5c09SChris Mason break; 2558db94535dSChris Mason 2559be0e5c09SChris Mason push_items++; 2560db94535dSChris Mason push_space += this_item_size + sizeof(*item); 2561be0e5c09SChris Mason } 2562db94535dSChris Mason 2563be0e5c09SChris Mason if (push_items == 0) { 2564925baeddSChris Mason ret = 1; 2565925baeddSChris Mason goto out; 2566be0e5c09SChris Mason } 256734a38218SChris Mason if (!empty && push_items == btrfs_header_nritems(right)) 2568a429e513SChris Mason WARN_ON(1); 25695f39d397SChris Mason 2570be0e5c09SChris Mason /* push data from right to left */ 25715f39d397SChris Mason copy_extent_buffer(left, right, 25725f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 25735f39d397SChris Mason btrfs_item_nr_offset(0), 25745f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 25755f39d397SChris Mason 2576123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 25775f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1); 25785f39d397SChris Mason 25795f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 2580d6025579SChris Mason leaf_data_end(root, left) - push_space, 2581123abc88SChris Mason btrfs_leaf_data(right) + 25825f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 2583be0e5c09SChris Mason push_space); 25845f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 258587b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 2586eb60ceacSChris Mason 2587db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 2588be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 25895f39d397SChris Mason u32 ioff; 2590db94535dSChris Mason 25915f39d397SChris Mason item = btrfs_item_nr(left, i); 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); 2598be0e5c09SChris Mason 2599be0e5c09SChris Mason /* fixup right node */ 260034a38218SChris Mason if (push_items > right_nritems) { 2601d397712bSChris Mason printk(KERN_CRIT "push items %d nr %u\n", push_items, 2602d397712bSChris Mason right_nritems); 260334a38218SChris Mason WARN_ON(1); 260434a38218SChris Mason } 260534a38218SChris Mason 260634a38218SChris Mason if (push_items < right_nritems) { 26075f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 2608123abc88SChris Mason leaf_data_end(root, right); 26095f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 2610d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2611d6025579SChris Mason btrfs_leaf_data(right) + 2612123abc88SChris Mason leaf_data_end(root, right), push_space); 26135f39d397SChris Mason 26145f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 26155f39d397SChris Mason btrfs_item_nr_offset(push_items), 26165f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 26170783fcfcSChris Mason sizeof(struct btrfs_item)); 261834a38218SChris Mason } 2619eef1c494SYan right_nritems -= push_items; 2620eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 2621123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 26225f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 26235f39d397SChris Mason item = btrfs_item_nr(right, i); 2624db94535dSChris Mason 2625db94535dSChris Mason push_space = push_space - btrfs_item_size(right, item); 2626db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2627db94535dSChris Mason } 2628eb60ceacSChris Mason 26295f39d397SChris Mason btrfs_mark_buffer_dirty(left); 263034a38218SChris Mason if (right_nritems) 26315f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2632f0486c68SYan, Zheng else 2633f0486c68SYan, Zheng clean_tree_block(trans, root, right); 2634098f59c2SChris Mason 26355f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 2636143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 2637be0e5c09SChris Mason 2638be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 2639be0e5c09SChris Mason if (path->slots[0] < push_items) { 2640be0e5c09SChris Mason path->slots[0] += old_left_nritems; 2641925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 26425f39d397SChris Mason free_extent_buffer(path->nodes[0]); 26435f39d397SChris Mason path->nodes[0] = left; 2644be0e5c09SChris Mason path->slots[1] -= 1; 2645be0e5c09SChris Mason } else { 2646925baeddSChris Mason btrfs_tree_unlock(left); 26475f39d397SChris Mason free_extent_buffer(left); 2648be0e5c09SChris Mason path->slots[0] -= push_items; 2649be0e5c09SChris Mason } 2650eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2651aa5d6bedSChris Mason return ret; 2652925baeddSChris Mason out: 2653925baeddSChris Mason btrfs_tree_unlock(left); 2654925baeddSChris Mason free_extent_buffer(left); 2655925baeddSChris Mason return ret; 2656be0e5c09SChris Mason } 2657be0e5c09SChris Mason 265874123bd7SChris Mason /* 265944871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 266044871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 266199d8f83cSChris Mason * 266299d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 266399d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the 266499d8f83cSChris Mason * items 266544871b1bSChris Mason */ 266644871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 266799d8f83cSChris Mason *root, struct btrfs_path *path, int min_data_size, 266899d8f83cSChris Mason int data_size, int empty, u32 max_slot) 266944871b1bSChris Mason { 267044871b1bSChris Mason struct extent_buffer *right = path->nodes[0]; 267144871b1bSChris Mason struct extent_buffer *left; 267244871b1bSChris Mason int slot; 267344871b1bSChris Mason int free_space; 267444871b1bSChris Mason u32 right_nritems; 267544871b1bSChris Mason int ret = 0; 267644871b1bSChris Mason 267744871b1bSChris Mason slot = path->slots[1]; 267844871b1bSChris Mason if (slot == 0) 267944871b1bSChris Mason return 1; 268044871b1bSChris Mason if (!path->nodes[1]) 268144871b1bSChris Mason return 1; 268244871b1bSChris Mason 268344871b1bSChris Mason right_nritems = btrfs_header_nritems(right); 268444871b1bSChris Mason if (right_nritems == 0) 268544871b1bSChris Mason return 1; 268644871b1bSChris Mason 268744871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 268844871b1bSChris Mason 268944871b1bSChris Mason left = read_node_slot(root, path->nodes[1], slot - 1); 269091ca338dSTsutomu Itoh if (left == NULL) 269191ca338dSTsutomu Itoh return 1; 269291ca338dSTsutomu Itoh 269344871b1bSChris Mason btrfs_tree_lock(left); 269444871b1bSChris Mason btrfs_set_lock_blocking(left); 269544871b1bSChris Mason 269644871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 269744871b1bSChris Mason if (free_space < data_size) { 269844871b1bSChris Mason ret = 1; 269944871b1bSChris Mason goto out; 270044871b1bSChris Mason } 270144871b1bSChris Mason 270244871b1bSChris Mason /* cow and double check */ 270344871b1bSChris Mason ret = btrfs_cow_block(trans, root, left, 270444871b1bSChris Mason path->nodes[1], slot - 1, &left); 270544871b1bSChris Mason if (ret) { 270644871b1bSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 270744871b1bSChris Mason ret = 1; 270844871b1bSChris Mason goto out; 270944871b1bSChris Mason } 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 271799d8f83cSChris Mason return __push_leaf_left(trans, root, path, min_data_size, 271899d8f83cSChris Mason empty, left, free_space, right_nritems, 271999d8f83cSChris Mason max_slot); 272044871b1bSChris Mason out: 272144871b1bSChris Mason btrfs_tree_unlock(left); 272244871b1bSChris Mason free_extent_buffer(left); 272344871b1bSChris Mason return ret; 272444871b1bSChris Mason } 272544871b1bSChris Mason 272644871b1bSChris Mason /* 272774123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 272874123bd7SChris Mason * available for the resulting leaf level of the path. 272974123bd7SChris Mason */ 2730143bede5SJeff Mahoney static noinline void copy_for_split(struct btrfs_trans_handle *trans, 2731e02119d5SChris Mason struct btrfs_root *root, 273244871b1bSChris Mason struct btrfs_path *path, 273344871b1bSChris Mason struct extent_buffer *l, 273444871b1bSChris Mason struct extent_buffer *right, 273544871b1bSChris Mason int slot, int mid, int nritems) 2736be0e5c09SChris Mason { 2737be0e5c09SChris Mason int data_copy_size; 2738be0e5c09SChris Mason int rt_data_off; 2739be0e5c09SChris Mason int i; 2740d4dbff95SChris Mason struct btrfs_disk_key disk_key; 2741be0e5c09SChris Mason 27425f39d397SChris Mason nritems = nritems - mid; 27435f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 27445f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 27455f39d397SChris Mason 27465f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 27475f39d397SChris Mason btrfs_item_nr_offset(mid), 27485f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 27495f39d397SChris Mason 27505f39d397SChris Mason copy_extent_buffer(right, l, 2751d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 2752123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 2753123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 275474123bd7SChris Mason 27555f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 27565f39d397SChris Mason btrfs_item_end_nr(l, mid); 27575f39d397SChris Mason 27585f39d397SChris Mason for (i = 0; i < nritems; i++) { 27595f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 2760db94535dSChris Mason u32 ioff; 2761db94535dSChris Mason 2762db94535dSChris Mason ioff = btrfs_item_offset(right, item); 27635f39d397SChris Mason btrfs_set_item_offset(right, item, ioff + rt_data_off); 27640783fcfcSChris Mason } 276574123bd7SChris Mason 27665f39d397SChris Mason btrfs_set_header_nritems(l, mid); 27675f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 2768143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, right->start, 2769db94535dSChris Mason path->slots[1] + 1, 1); 27705f39d397SChris Mason 27715f39d397SChris Mason btrfs_mark_buffer_dirty(right); 27725f39d397SChris Mason btrfs_mark_buffer_dirty(l); 2773eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 27745f39d397SChris Mason 2775be0e5c09SChris Mason if (mid <= slot) { 2776925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 27775f39d397SChris Mason free_extent_buffer(path->nodes[0]); 27785f39d397SChris Mason path->nodes[0] = right; 2779be0e5c09SChris Mason path->slots[0] -= mid; 2780be0e5c09SChris Mason path->slots[1] += 1; 2781925baeddSChris Mason } else { 2782925baeddSChris Mason btrfs_tree_unlock(right); 27835f39d397SChris Mason free_extent_buffer(right); 2784925baeddSChris Mason } 27855f39d397SChris Mason 2786eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 278744871b1bSChris Mason } 278844871b1bSChris Mason 278944871b1bSChris Mason /* 279099d8f83cSChris Mason * double splits happen when we need to insert a big item in the middle 279199d8f83cSChris Mason * of a leaf. A double split can leave us with 3 mostly empty leaves: 279299d8f83cSChris Mason * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ] 279399d8f83cSChris Mason * A B C 279499d8f83cSChris Mason * 279599d8f83cSChris Mason * We avoid this by trying to push the items on either side of our target 279699d8f83cSChris Mason * into the adjacent leaves. If all goes well we can avoid the double split 279799d8f83cSChris Mason * completely. 279899d8f83cSChris Mason */ 279999d8f83cSChris Mason static noinline int push_for_double_split(struct btrfs_trans_handle *trans, 280099d8f83cSChris Mason struct btrfs_root *root, 280199d8f83cSChris Mason struct btrfs_path *path, 280299d8f83cSChris Mason int data_size) 280399d8f83cSChris Mason { 280499d8f83cSChris Mason int ret; 280599d8f83cSChris Mason int progress = 0; 280699d8f83cSChris Mason int slot; 280799d8f83cSChris Mason u32 nritems; 280899d8f83cSChris Mason 280999d8f83cSChris Mason slot = path->slots[0]; 281099d8f83cSChris Mason 281199d8f83cSChris Mason /* 281299d8f83cSChris Mason * try to push all the items after our slot into the 281399d8f83cSChris Mason * right leaf 281499d8f83cSChris Mason */ 281599d8f83cSChris Mason ret = push_leaf_right(trans, root, path, 1, data_size, 0, slot); 281699d8f83cSChris Mason if (ret < 0) 281799d8f83cSChris Mason return ret; 281899d8f83cSChris Mason 281999d8f83cSChris Mason if (ret == 0) 282099d8f83cSChris Mason progress++; 282199d8f83cSChris Mason 282299d8f83cSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 282399d8f83cSChris Mason /* 282499d8f83cSChris Mason * our goal is to get our slot at the start or end of a leaf. If 282599d8f83cSChris Mason * we've done so we're done 282699d8f83cSChris Mason */ 282799d8f83cSChris Mason if (path->slots[0] == 0 || path->slots[0] == nritems) 282899d8f83cSChris Mason return 0; 282999d8f83cSChris Mason 283099d8f83cSChris Mason if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size) 283199d8f83cSChris Mason return 0; 283299d8f83cSChris Mason 283399d8f83cSChris Mason /* try to push all the items before our slot into the next leaf */ 283499d8f83cSChris Mason slot = path->slots[0]; 283599d8f83cSChris Mason ret = push_leaf_left(trans, root, path, 1, data_size, 0, slot); 283699d8f83cSChris Mason if (ret < 0) 283799d8f83cSChris Mason return ret; 283899d8f83cSChris Mason 283999d8f83cSChris Mason if (ret == 0) 284099d8f83cSChris Mason progress++; 284199d8f83cSChris Mason 284299d8f83cSChris Mason if (progress) 284399d8f83cSChris Mason return 0; 284499d8f83cSChris Mason return 1; 284599d8f83cSChris Mason } 284699d8f83cSChris Mason 284799d8f83cSChris Mason /* 284844871b1bSChris Mason * split the path's leaf in two, making sure there is at least data_size 284944871b1bSChris Mason * available for the resulting leaf level of the path. 285044871b1bSChris Mason * 285144871b1bSChris Mason * returns 0 if all went well and < 0 on failure. 285244871b1bSChris Mason */ 285344871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 285444871b1bSChris Mason struct btrfs_root *root, 285544871b1bSChris Mason struct btrfs_key *ins_key, 285644871b1bSChris Mason struct btrfs_path *path, int data_size, 285744871b1bSChris Mason int extend) 285844871b1bSChris Mason { 28595d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 286044871b1bSChris Mason struct extent_buffer *l; 286144871b1bSChris Mason u32 nritems; 286244871b1bSChris Mason int mid; 286344871b1bSChris Mason int slot; 286444871b1bSChris Mason struct extent_buffer *right; 286544871b1bSChris Mason int ret = 0; 286644871b1bSChris Mason int wret; 28675d4f98a2SYan Zheng int split; 286844871b1bSChris Mason int num_doubles = 0; 286999d8f83cSChris Mason int tried_avoid_double = 0; 287044871b1bSChris Mason 2871a5719521SYan, Zheng l = path->nodes[0]; 2872a5719521SYan, Zheng slot = path->slots[0]; 2873a5719521SYan, Zheng if (extend && data_size + btrfs_item_size_nr(l, slot) + 2874a5719521SYan, Zheng sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root)) 2875a5719521SYan, Zheng return -EOVERFLOW; 2876a5719521SYan, Zheng 287744871b1bSChris Mason /* first try to make some room by pushing left and right */ 287899d8f83cSChris Mason if (data_size) { 287999d8f83cSChris Mason wret = push_leaf_right(trans, root, path, data_size, 288099d8f83cSChris Mason data_size, 0, 0); 288144871b1bSChris Mason if (wret < 0) 288244871b1bSChris Mason return wret; 288344871b1bSChris Mason if (wret) { 288499d8f83cSChris Mason wret = push_leaf_left(trans, root, path, data_size, 288599d8f83cSChris Mason data_size, 0, (u32)-1); 288644871b1bSChris Mason if (wret < 0) 288744871b1bSChris Mason return wret; 288844871b1bSChris Mason } 288944871b1bSChris Mason l = path->nodes[0]; 289044871b1bSChris Mason 289144871b1bSChris Mason /* did the pushes work? */ 289244871b1bSChris Mason if (btrfs_leaf_free_space(root, l) >= data_size) 289344871b1bSChris Mason return 0; 289444871b1bSChris Mason } 289544871b1bSChris Mason 289644871b1bSChris Mason if (!path->nodes[1]) { 289744871b1bSChris Mason ret = insert_new_root(trans, root, path, 1); 289844871b1bSChris Mason if (ret) 289944871b1bSChris Mason return ret; 290044871b1bSChris Mason } 290144871b1bSChris Mason again: 29025d4f98a2SYan Zheng split = 1; 290344871b1bSChris Mason l = path->nodes[0]; 290444871b1bSChris Mason slot = path->slots[0]; 290544871b1bSChris Mason nritems = btrfs_header_nritems(l); 290644871b1bSChris Mason mid = (nritems + 1) / 2; 290744871b1bSChris Mason 29085d4f98a2SYan Zheng if (mid <= slot) { 29095d4f98a2SYan Zheng if (nritems == 1 || 29105d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + data_size > 29115d4f98a2SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 29125d4f98a2SYan Zheng if (slot >= nritems) { 29135d4f98a2SYan Zheng split = 0; 29145d4f98a2SYan Zheng } else { 29155d4f98a2SYan Zheng mid = slot; 29165d4f98a2SYan Zheng if (mid != nritems && 29175d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 29185d4f98a2SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 291999d8f83cSChris Mason if (data_size && !tried_avoid_double) 292099d8f83cSChris Mason goto push_for_double; 29215d4f98a2SYan Zheng split = 2; 29225d4f98a2SYan Zheng } 29235d4f98a2SYan Zheng } 29245d4f98a2SYan Zheng } 29255d4f98a2SYan Zheng } else { 29265d4f98a2SYan Zheng if (leaf_space_used(l, 0, mid) + data_size > 29275d4f98a2SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 29285d4f98a2SYan Zheng if (!extend && data_size && slot == 0) { 29295d4f98a2SYan Zheng split = 0; 29305d4f98a2SYan Zheng } else if ((extend || !data_size) && slot == 0) { 29315d4f98a2SYan Zheng mid = 1; 29325d4f98a2SYan Zheng } else { 29335d4f98a2SYan Zheng mid = slot; 29345d4f98a2SYan Zheng if (mid != nritems && 29355d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 29365d4f98a2SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 293799d8f83cSChris Mason if (data_size && !tried_avoid_double) 293899d8f83cSChris Mason goto push_for_double; 29395d4f98a2SYan Zheng split = 2 ; 29405d4f98a2SYan Zheng } 29415d4f98a2SYan Zheng } 29425d4f98a2SYan Zheng } 29435d4f98a2SYan Zheng } 29445d4f98a2SYan Zheng 29455d4f98a2SYan Zheng if (split == 0) 29465d4f98a2SYan Zheng btrfs_cpu_key_to_disk(&disk_key, ins_key); 29475d4f98a2SYan Zheng else 29485d4f98a2SYan Zheng btrfs_item_key(l, &disk_key, mid); 29495d4f98a2SYan Zheng 29505d4f98a2SYan Zheng right = btrfs_alloc_free_block(trans, root, root->leafsize, 0, 295144871b1bSChris Mason root->root_key.objectid, 295266d7e7f0SArne Jansen &disk_key, 0, l->start, 0, 0); 2953f0486c68SYan, Zheng if (IS_ERR(right)) 295444871b1bSChris Mason return PTR_ERR(right); 2955f0486c68SYan, Zheng 2956f0486c68SYan, Zheng root_add_used(root, root->leafsize); 295744871b1bSChris Mason 295844871b1bSChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 295944871b1bSChris Mason btrfs_set_header_bytenr(right, right->start); 296044871b1bSChris Mason btrfs_set_header_generation(right, trans->transid); 29615d4f98a2SYan Zheng btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV); 296244871b1bSChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 296344871b1bSChris Mason btrfs_set_header_level(right, 0); 296444871b1bSChris Mason write_extent_buffer(right, root->fs_info->fsid, 296544871b1bSChris Mason (unsigned long)btrfs_header_fsid(right), 296644871b1bSChris Mason BTRFS_FSID_SIZE); 296744871b1bSChris Mason 296844871b1bSChris Mason write_extent_buffer(right, root->fs_info->chunk_tree_uuid, 296944871b1bSChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(right), 297044871b1bSChris Mason BTRFS_UUID_SIZE); 297144871b1bSChris Mason 29725d4f98a2SYan Zheng if (split == 0) { 297344871b1bSChris Mason if (mid <= slot) { 297444871b1bSChris Mason btrfs_set_header_nritems(right, 0); 2975143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, right->start, 297644871b1bSChris Mason path->slots[1] + 1, 1); 297744871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 297844871b1bSChris Mason free_extent_buffer(path->nodes[0]); 297944871b1bSChris Mason path->nodes[0] = right; 298044871b1bSChris Mason path->slots[0] = 0; 298144871b1bSChris Mason path->slots[1] += 1; 298244871b1bSChris Mason } else { 298344871b1bSChris Mason btrfs_set_header_nritems(right, 0); 2984143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, right->start, 298544871b1bSChris Mason path->slots[1], 1); 298644871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 298744871b1bSChris Mason free_extent_buffer(path->nodes[0]); 298844871b1bSChris Mason path->nodes[0] = right; 298944871b1bSChris Mason path->slots[0] = 0; 2990143bede5SJeff Mahoney if (path->slots[1] == 0) 2991143bede5SJeff Mahoney fixup_low_keys(trans, root, path, 2992143bede5SJeff Mahoney &disk_key, 1); 29935d4f98a2SYan Zheng } 299444871b1bSChris Mason btrfs_mark_buffer_dirty(right); 299544871b1bSChris Mason return ret; 299644871b1bSChris Mason } 299744871b1bSChris Mason 2998143bede5SJeff Mahoney copy_for_split(trans, root, path, l, right, slot, mid, nritems); 299944871b1bSChris Mason 30005d4f98a2SYan Zheng if (split == 2) { 3001cc0c5538SChris Mason BUG_ON(num_doubles != 0); 3002cc0c5538SChris Mason num_doubles++; 3003cc0c5538SChris Mason goto again; 30043326d1b0SChris Mason } 300544871b1bSChris Mason 3006143bede5SJeff Mahoney return 0; 300799d8f83cSChris Mason 300899d8f83cSChris Mason push_for_double: 300999d8f83cSChris Mason push_for_double_split(trans, root, path, data_size); 301099d8f83cSChris Mason tried_avoid_double = 1; 301199d8f83cSChris Mason if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size) 301299d8f83cSChris Mason return 0; 301399d8f83cSChris Mason goto again; 3014be0e5c09SChris Mason } 3015be0e5c09SChris Mason 3016ad48fd75SYan, Zheng static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3017ad48fd75SYan, Zheng struct btrfs_root *root, 3018ad48fd75SYan, Zheng struct btrfs_path *path, int ins_len) 3019ad48fd75SYan, Zheng { 3020ad48fd75SYan, Zheng struct btrfs_key key; 3021ad48fd75SYan, Zheng struct extent_buffer *leaf; 3022ad48fd75SYan, Zheng struct btrfs_file_extent_item *fi; 3023ad48fd75SYan, Zheng u64 extent_len = 0; 3024ad48fd75SYan, Zheng u32 item_size; 3025ad48fd75SYan, Zheng int ret; 3026ad48fd75SYan, Zheng 3027ad48fd75SYan, Zheng leaf = path->nodes[0]; 3028ad48fd75SYan, Zheng btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 3029ad48fd75SYan, Zheng 3030ad48fd75SYan, Zheng BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY && 3031ad48fd75SYan, Zheng key.type != BTRFS_EXTENT_CSUM_KEY); 3032ad48fd75SYan, Zheng 3033ad48fd75SYan, Zheng if (btrfs_leaf_free_space(root, leaf) >= ins_len) 3034ad48fd75SYan, Zheng return 0; 3035ad48fd75SYan, Zheng 3036ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3037ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3038ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3039ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3040ad48fd75SYan, Zheng extent_len = btrfs_file_extent_num_bytes(leaf, fi); 3041ad48fd75SYan, Zheng } 3042b3b4aa74SDavid Sterba btrfs_release_path(path); 3043ad48fd75SYan, Zheng 3044ad48fd75SYan, Zheng path->keep_locks = 1; 3045ad48fd75SYan, Zheng path->search_for_split = 1; 3046ad48fd75SYan, Zheng ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 3047ad48fd75SYan, Zheng path->search_for_split = 0; 3048ad48fd75SYan, Zheng if (ret < 0) 3049ad48fd75SYan, Zheng goto err; 3050ad48fd75SYan, Zheng 3051ad48fd75SYan, Zheng ret = -EAGAIN; 3052ad48fd75SYan, Zheng leaf = path->nodes[0]; 3053ad48fd75SYan, Zheng /* if our item isn't there or got smaller, return now */ 3054ad48fd75SYan, Zheng if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0])) 3055ad48fd75SYan, Zheng goto err; 3056ad48fd75SYan, Zheng 3057109f6aefSChris Mason /* the leaf has changed, it now has room. return now */ 3058109f6aefSChris Mason if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len) 3059109f6aefSChris Mason goto err; 3060109f6aefSChris Mason 3061ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3062ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3063ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3064ad48fd75SYan, Zheng if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) 3065ad48fd75SYan, Zheng goto err; 3066ad48fd75SYan, Zheng } 3067ad48fd75SYan, Zheng 3068ad48fd75SYan, Zheng btrfs_set_path_blocking(path); 3069ad48fd75SYan, Zheng ret = split_leaf(trans, root, &key, path, ins_len, 1); 3070f0486c68SYan, Zheng if (ret) 3071f0486c68SYan, Zheng goto err; 3072ad48fd75SYan, Zheng 3073ad48fd75SYan, Zheng path->keep_locks = 0; 3074ad48fd75SYan, Zheng btrfs_unlock_up_safe(path, 1); 3075ad48fd75SYan, Zheng return 0; 3076ad48fd75SYan, Zheng err: 3077ad48fd75SYan, Zheng path->keep_locks = 0; 3078ad48fd75SYan, Zheng return ret; 3079ad48fd75SYan, Zheng } 3080ad48fd75SYan, Zheng 3081ad48fd75SYan, Zheng static noinline int split_item(struct btrfs_trans_handle *trans, 3082459931ecSChris Mason struct btrfs_root *root, 3083459931ecSChris Mason struct btrfs_path *path, 3084459931ecSChris Mason struct btrfs_key *new_key, 3085459931ecSChris Mason unsigned long split_offset) 3086459931ecSChris Mason { 3087459931ecSChris Mason struct extent_buffer *leaf; 3088459931ecSChris Mason struct btrfs_item *item; 3089459931ecSChris Mason struct btrfs_item *new_item; 3090459931ecSChris Mason int slot; 3091ad48fd75SYan, Zheng char *buf; 3092459931ecSChris Mason u32 nritems; 3093ad48fd75SYan, Zheng u32 item_size; 3094459931ecSChris Mason u32 orig_offset; 3095459931ecSChris Mason struct btrfs_disk_key disk_key; 3096459931ecSChris Mason 3097459931ecSChris Mason leaf = path->nodes[0]; 3098b9473439SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item)); 3099b9473439SChris Mason 3100b4ce94deSChris Mason btrfs_set_path_blocking(path); 3101b4ce94deSChris Mason 3102459931ecSChris Mason item = btrfs_item_nr(leaf, path->slots[0]); 3103459931ecSChris Mason orig_offset = btrfs_item_offset(leaf, item); 3104459931ecSChris Mason item_size = btrfs_item_size(leaf, item); 3105459931ecSChris Mason 3106459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 3107ad48fd75SYan, Zheng if (!buf) 3108ad48fd75SYan, Zheng return -ENOMEM; 3109ad48fd75SYan, Zheng 3110459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3111459931ecSChris Mason path->slots[0]), item_size); 3112ad48fd75SYan, Zheng 3113459931ecSChris Mason slot = path->slots[0] + 1; 3114459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 3115459931ecSChris Mason if (slot != nritems) { 3116459931ecSChris Mason /* shift the items */ 3117459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 3118459931ecSChris Mason btrfs_item_nr_offset(slot), 3119459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3120459931ecSChris Mason } 3121459931ecSChris Mason 3122459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 3123459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3124459931ecSChris Mason 3125459931ecSChris Mason new_item = btrfs_item_nr(leaf, slot); 3126459931ecSChris Mason 3127459931ecSChris Mason btrfs_set_item_offset(leaf, new_item, orig_offset); 3128459931ecSChris Mason btrfs_set_item_size(leaf, new_item, item_size - split_offset); 3129459931ecSChris Mason 3130459931ecSChris Mason btrfs_set_item_offset(leaf, item, 3131459931ecSChris Mason orig_offset + item_size - split_offset); 3132459931ecSChris Mason btrfs_set_item_size(leaf, item, split_offset); 3133459931ecSChris Mason 3134459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 3135459931ecSChris Mason 3136459931ecSChris Mason /* write the data for the start of the original item */ 3137459931ecSChris Mason write_extent_buffer(leaf, buf, 3138459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 3139459931ecSChris Mason split_offset); 3140459931ecSChris Mason 3141459931ecSChris Mason /* write the data for the new item */ 3142459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 3143459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 3144459931ecSChris Mason item_size - split_offset); 3145459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 3146459931ecSChris Mason 3147ad48fd75SYan, Zheng BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 3148459931ecSChris Mason kfree(buf); 3149ad48fd75SYan, Zheng return 0; 3150ad48fd75SYan, Zheng } 3151ad48fd75SYan, Zheng 3152ad48fd75SYan, Zheng /* 3153ad48fd75SYan, Zheng * This function splits a single item into two items, 3154ad48fd75SYan, Zheng * giving 'new_key' to the new item and splitting the 3155ad48fd75SYan, Zheng * old one at split_offset (from the start of the item). 3156ad48fd75SYan, Zheng * 3157ad48fd75SYan, Zheng * The path may be released by this operation. After 3158ad48fd75SYan, Zheng * the split, the path is pointing to the old item. The 3159ad48fd75SYan, Zheng * new item is going to be in the same node as the old one. 3160ad48fd75SYan, Zheng * 3161ad48fd75SYan, Zheng * Note, the item being split must be smaller enough to live alone on 3162ad48fd75SYan, Zheng * a tree block with room for one extra struct btrfs_item 3163ad48fd75SYan, Zheng * 3164ad48fd75SYan, Zheng * This allows us to split the item in place, keeping a lock on the 3165ad48fd75SYan, Zheng * leaf the entire time. 3166ad48fd75SYan, Zheng */ 3167ad48fd75SYan, Zheng int btrfs_split_item(struct btrfs_trans_handle *trans, 3168ad48fd75SYan, Zheng struct btrfs_root *root, 3169ad48fd75SYan, Zheng struct btrfs_path *path, 3170ad48fd75SYan, Zheng struct btrfs_key *new_key, 3171ad48fd75SYan, Zheng unsigned long split_offset) 3172ad48fd75SYan, Zheng { 3173ad48fd75SYan, Zheng int ret; 3174ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3175ad48fd75SYan, Zheng sizeof(struct btrfs_item)); 3176ad48fd75SYan, Zheng if (ret) 3177459931ecSChris Mason return ret; 3178ad48fd75SYan, Zheng 3179ad48fd75SYan, Zheng ret = split_item(trans, root, path, new_key, split_offset); 3180ad48fd75SYan, Zheng return ret; 3181ad48fd75SYan, Zheng } 3182ad48fd75SYan, Zheng 3183ad48fd75SYan, Zheng /* 3184ad48fd75SYan, Zheng * This function duplicate a item, giving 'new_key' to the new item. 3185ad48fd75SYan, Zheng * It guarantees both items live in the same tree leaf and the new item 3186ad48fd75SYan, Zheng * is contiguous with the original item. 3187ad48fd75SYan, Zheng * 3188ad48fd75SYan, Zheng * This allows us to split file extent in place, keeping a lock on the 3189ad48fd75SYan, Zheng * leaf the entire time. 3190ad48fd75SYan, Zheng */ 3191ad48fd75SYan, Zheng int btrfs_duplicate_item(struct btrfs_trans_handle *trans, 3192ad48fd75SYan, Zheng struct btrfs_root *root, 3193ad48fd75SYan, Zheng struct btrfs_path *path, 3194ad48fd75SYan, Zheng struct btrfs_key *new_key) 3195ad48fd75SYan, Zheng { 3196ad48fd75SYan, Zheng struct extent_buffer *leaf; 3197ad48fd75SYan, Zheng int ret; 3198ad48fd75SYan, Zheng u32 item_size; 3199ad48fd75SYan, Zheng 3200ad48fd75SYan, Zheng leaf = path->nodes[0]; 3201ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3202ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3203ad48fd75SYan, Zheng item_size + sizeof(struct btrfs_item)); 3204ad48fd75SYan, Zheng if (ret) 3205ad48fd75SYan, Zheng return ret; 3206ad48fd75SYan, Zheng 3207ad48fd75SYan, Zheng path->slots[0]++; 3208143bede5SJeff Mahoney setup_items_for_insert(trans, root, path, new_key, &item_size, 3209ad48fd75SYan, Zheng item_size, item_size + 3210ad48fd75SYan, Zheng sizeof(struct btrfs_item), 1); 3211ad48fd75SYan, Zheng leaf = path->nodes[0]; 3212ad48fd75SYan, Zheng memcpy_extent_buffer(leaf, 3213ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0]), 3214ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0] - 1), 3215ad48fd75SYan, Zheng item_size); 3216ad48fd75SYan, Zheng return 0; 3217459931ecSChris Mason } 3218459931ecSChris Mason 3219459931ecSChris Mason /* 3220d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 3221d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 3222d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 3223d352ac68SChris Mason * the front. 3224d352ac68SChris Mason */ 3225143bede5SJeff Mahoney void btrfs_truncate_item(struct btrfs_trans_handle *trans, 3226b18c6685SChris Mason struct btrfs_root *root, 3227b18c6685SChris Mason struct btrfs_path *path, 3228179e29e4SChris Mason u32 new_size, int from_end) 3229b18c6685SChris Mason { 3230b18c6685SChris Mason int slot; 32315f39d397SChris Mason struct extent_buffer *leaf; 32325f39d397SChris Mason struct btrfs_item *item; 3233b18c6685SChris Mason u32 nritems; 3234b18c6685SChris Mason unsigned int data_end; 3235b18c6685SChris Mason unsigned int old_data_start; 3236b18c6685SChris Mason unsigned int old_size; 3237b18c6685SChris Mason unsigned int size_diff; 3238b18c6685SChris Mason int i; 3239b18c6685SChris Mason 32405f39d397SChris Mason leaf = path->nodes[0]; 3241179e29e4SChris Mason slot = path->slots[0]; 3242179e29e4SChris Mason 3243179e29e4SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 3244179e29e4SChris Mason if (old_size == new_size) 3245143bede5SJeff Mahoney return; 3246b18c6685SChris Mason 32475f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3248b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 3249b18c6685SChris Mason 32505f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 3251179e29e4SChris Mason 3252b18c6685SChris Mason size_diff = old_size - new_size; 3253b18c6685SChris Mason 3254b18c6685SChris Mason BUG_ON(slot < 0); 3255b18c6685SChris Mason BUG_ON(slot >= nritems); 3256b18c6685SChris Mason 3257b18c6685SChris Mason /* 3258b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3259b18c6685SChris Mason */ 3260b18c6685SChris Mason /* first correct the data pointers */ 3261b18c6685SChris Mason for (i = slot; i < nritems; i++) { 32625f39d397SChris Mason u32 ioff; 32635f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3264db94535dSChris Mason 32655f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 32665f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + size_diff); 3267b18c6685SChris Mason } 3268db94535dSChris Mason 3269b18c6685SChris Mason /* shift the data */ 3270179e29e4SChris Mason if (from_end) { 32715f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3272b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 3273b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 3274179e29e4SChris Mason } else { 3275179e29e4SChris Mason struct btrfs_disk_key disk_key; 3276179e29e4SChris Mason u64 offset; 3277179e29e4SChris Mason 3278179e29e4SChris Mason btrfs_item_key(leaf, &disk_key, slot); 3279179e29e4SChris Mason 3280179e29e4SChris Mason if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 3281179e29e4SChris Mason unsigned long ptr; 3282179e29e4SChris Mason struct btrfs_file_extent_item *fi; 3283179e29e4SChris Mason 3284179e29e4SChris Mason fi = btrfs_item_ptr(leaf, slot, 3285179e29e4SChris Mason struct btrfs_file_extent_item); 3286179e29e4SChris Mason fi = (struct btrfs_file_extent_item *)( 3287179e29e4SChris Mason (unsigned long)fi - size_diff); 3288179e29e4SChris Mason 3289179e29e4SChris Mason if (btrfs_file_extent_type(leaf, fi) == 3290179e29e4SChris Mason BTRFS_FILE_EXTENT_INLINE) { 3291179e29e4SChris Mason ptr = btrfs_item_ptr_offset(leaf, slot); 3292179e29e4SChris Mason memmove_extent_buffer(leaf, ptr, 3293179e29e4SChris Mason (unsigned long)fi, 3294179e29e4SChris Mason offsetof(struct btrfs_file_extent_item, 3295179e29e4SChris Mason disk_bytenr)); 3296179e29e4SChris Mason } 3297179e29e4SChris Mason } 3298179e29e4SChris Mason 3299179e29e4SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3300179e29e4SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 3301179e29e4SChris Mason data_end, old_data_start - data_end); 3302179e29e4SChris Mason 3303179e29e4SChris Mason offset = btrfs_disk_key_offset(&disk_key); 3304179e29e4SChris Mason btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 3305179e29e4SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3306179e29e4SChris Mason if (slot == 0) 3307179e29e4SChris Mason fixup_low_keys(trans, root, path, &disk_key, 1); 3308179e29e4SChris Mason } 33095f39d397SChris Mason 33105f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 33115f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 33125f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3313b18c6685SChris Mason 33145f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 33155f39d397SChris Mason btrfs_print_leaf(root, leaf); 3316b18c6685SChris Mason BUG(); 33175f39d397SChris Mason } 3318b18c6685SChris Mason } 3319b18c6685SChris Mason 3320d352ac68SChris Mason /* 3321d352ac68SChris Mason * make the item pointed to by the path bigger, data_size is the new size. 3322d352ac68SChris Mason */ 3323143bede5SJeff Mahoney void btrfs_extend_item(struct btrfs_trans_handle *trans, 33245f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 33255f39d397SChris Mason u32 data_size) 33266567e837SChris Mason { 33276567e837SChris Mason int slot; 33285f39d397SChris Mason struct extent_buffer *leaf; 33295f39d397SChris Mason struct btrfs_item *item; 33306567e837SChris Mason u32 nritems; 33316567e837SChris Mason unsigned int data_end; 33326567e837SChris Mason unsigned int old_data; 33336567e837SChris Mason unsigned int old_size; 33346567e837SChris Mason int i; 33356567e837SChris Mason 33365f39d397SChris Mason leaf = path->nodes[0]; 33376567e837SChris Mason 33385f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 33396567e837SChris Mason data_end = leaf_data_end(root, leaf); 33406567e837SChris Mason 33415f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 33425f39d397SChris Mason btrfs_print_leaf(root, leaf); 33436567e837SChris Mason BUG(); 33445f39d397SChris Mason } 33456567e837SChris Mason slot = path->slots[0]; 33465f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 33476567e837SChris Mason 33486567e837SChris Mason BUG_ON(slot < 0); 33493326d1b0SChris Mason if (slot >= nritems) { 33503326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3351d397712bSChris Mason printk(KERN_CRIT "slot %d too large, nritems %d\n", 3352d397712bSChris Mason slot, nritems); 33533326d1b0SChris Mason BUG_ON(1); 33543326d1b0SChris Mason } 33556567e837SChris Mason 33566567e837SChris Mason /* 33576567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 33586567e837SChris Mason */ 33596567e837SChris Mason /* first correct the data pointers */ 33606567e837SChris Mason for (i = slot; i < nritems; i++) { 33615f39d397SChris Mason u32 ioff; 33625f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3363db94535dSChris Mason 33645f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 33655f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 33666567e837SChris Mason } 33675f39d397SChris Mason 33686567e837SChris Mason /* shift the data */ 33695f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 33706567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 33716567e837SChris Mason data_end, old_data - data_end); 33725f39d397SChris Mason 33736567e837SChris Mason data_end = old_data; 33745f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 33755f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 33765f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 33775f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 33786567e837SChris Mason 33795f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 33805f39d397SChris Mason btrfs_print_leaf(root, leaf); 33816567e837SChris Mason BUG(); 33825f39d397SChris Mason } 33836567e837SChris Mason } 33846567e837SChris Mason 338574123bd7SChris Mason /* 3386d352ac68SChris Mason * Given a key and some data, insert items into the tree. 338774123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 3388f3465ca4SJosef Bacik * Returns the number of keys that were inserted. 3389f3465ca4SJosef Bacik */ 3390f3465ca4SJosef Bacik int btrfs_insert_some_items(struct btrfs_trans_handle *trans, 3391f3465ca4SJosef Bacik struct btrfs_root *root, 3392f3465ca4SJosef Bacik struct btrfs_path *path, 3393f3465ca4SJosef Bacik struct btrfs_key *cpu_key, u32 *data_size, 3394f3465ca4SJosef Bacik int nr) 3395f3465ca4SJosef Bacik { 3396f3465ca4SJosef Bacik struct extent_buffer *leaf; 3397f3465ca4SJosef Bacik struct btrfs_item *item; 3398f3465ca4SJosef Bacik int ret = 0; 3399f3465ca4SJosef Bacik int slot; 3400f3465ca4SJosef Bacik int i; 3401f3465ca4SJosef Bacik u32 nritems; 3402f3465ca4SJosef Bacik u32 total_data = 0; 3403f3465ca4SJosef Bacik u32 total_size = 0; 3404f3465ca4SJosef Bacik unsigned int data_end; 3405f3465ca4SJosef Bacik struct btrfs_disk_key disk_key; 3406f3465ca4SJosef Bacik struct btrfs_key found_key; 3407f3465ca4SJosef Bacik 340887b29b20SYan Zheng for (i = 0; i < nr; i++) { 340987b29b20SYan Zheng if (total_size + data_size[i] + sizeof(struct btrfs_item) > 341087b29b20SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 341187b29b20SYan Zheng break; 341287b29b20SYan Zheng nr = i; 341387b29b20SYan Zheng } 3414f3465ca4SJosef Bacik total_data += data_size[i]; 341587b29b20SYan Zheng total_size += data_size[i] + sizeof(struct btrfs_item); 341687b29b20SYan Zheng } 341787b29b20SYan Zheng BUG_ON(nr == 0); 3418f3465ca4SJosef Bacik 3419f3465ca4SJosef Bacik ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 3420f3465ca4SJosef Bacik if (ret == 0) 3421f3465ca4SJosef Bacik return -EEXIST; 3422f3465ca4SJosef Bacik if (ret < 0) 3423f3465ca4SJosef Bacik goto out; 3424f3465ca4SJosef Bacik 3425f3465ca4SJosef Bacik leaf = path->nodes[0]; 3426f3465ca4SJosef Bacik 3427f3465ca4SJosef Bacik nritems = btrfs_header_nritems(leaf); 3428f3465ca4SJosef Bacik data_end = leaf_data_end(root, leaf); 3429f3465ca4SJosef Bacik 3430f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < total_size) { 3431f3465ca4SJosef Bacik for (i = nr; i >= 0; i--) { 3432f3465ca4SJosef Bacik total_data -= data_size[i]; 3433f3465ca4SJosef Bacik total_size -= data_size[i] + sizeof(struct btrfs_item); 3434f3465ca4SJosef Bacik if (total_size < btrfs_leaf_free_space(root, leaf)) 3435f3465ca4SJosef Bacik break; 3436f3465ca4SJosef Bacik } 3437f3465ca4SJosef Bacik nr = i; 3438f3465ca4SJosef Bacik } 3439f3465ca4SJosef Bacik 3440f3465ca4SJosef Bacik slot = path->slots[0]; 3441f3465ca4SJosef Bacik BUG_ON(slot < 0); 3442f3465ca4SJosef Bacik 3443f3465ca4SJosef Bacik if (slot != nritems) { 3444f3465ca4SJosef Bacik unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3445f3465ca4SJosef Bacik 3446f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot); 3447f3465ca4SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, slot); 3448f3465ca4SJosef Bacik 3449f3465ca4SJosef Bacik /* figure out how many keys we can insert in here */ 3450f3465ca4SJosef Bacik total_data = data_size[0]; 3451f3465ca4SJosef Bacik for (i = 1; i < nr; i++) { 34525d4f98a2SYan Zheng if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0) 3453f3465ca4SJosef Bacik break; 3454f3465ca4SJosef Bacik total_data += data_size[i]; 3455f3465ca4SJosef Bacik } 3456f3465ca4SJosef Bacik nr = i; 3457f3465ca4SJosef Bacik 3458f3465ca4SJosef Bacik if (old_data < data_end) { 3459f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3460d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 3461f3465ca4SJosef Bacik slot, old_data, data_end); 3462f3465ca4SJosef Bacik BUG_ON(1); 3463f3465ca4SJosef Bacik } 3464f3465ca4SJosef Bacik /* 3465f3465ca4SJosef Bacik * item0..itemN ... dataN.offset..dataN.size .. data0.size 3466f3465ca4SJosef Bacik */ 3467f3465ca4SJosef Bacik /* first correct the data pointers */ 3468f3465ca4SJosef Bacik for (i = slot; i < nritems; i++) { 3469f3465ca4SJosef Bacik u32 ioff; 3470f3465ca4SJosef Bacik 3471f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, i); 3472f3465ca4SJosef Bacik ioff = btrfs_item_offset(leaf, item); 3473f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, ioff - total_data); 3474f3465ca4SJosef Bacik } 3475f3465ca4SJosef Bacik /* shift the items */ 3476f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 3477f3465ca4SJosef Bacik btrfs_item_nr_offset(slot), 3478f3465ca4SJosef Bacik (nritems - slot) * sizeof(struct btrfs_item)); 3479f3465ca4SJosef Bacik 3480f3465ca4SJosef Bacik /* shift the data */ 3481f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3482f3465ca4SJosef Bacik data_end - total_data, btrfs_leaf_data(leaf) + 3483f3465ca4SJosef Bacik data_end, old_data - data_end); 3484f3465ca4SJosef Bacik data_end = old_data; 3485f3465ca4SJosef Bacik } else { 3486f3465ca4SJosef Bacik /* 3487f3465ca4SJosef Bacik * this sucks but it has to be done, if we are inserting at 3488f3465ca4SJosef Bacik * the end of the leaf only insert 1 of the items, since we 3489f3465ca4SJosef Bacik * have no way of knowing whats on the next leaf and we'd have 3490f3465ca4SJosef Bacik * to drop our current locks to figure it out 3491f3465ca4SJosef Bacik */ 3492f3465ca4SJosef Bacik nr = 1; 3493f3465ca4SJosef Bacik } 3494f3465ca4SJosef Bacik 3495f3465ca4SJosef Bacik /* setup the item for the new data */ 3496f3465ca4SJosef Bacik for (i = 0; i < nr; i++) { 3497f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 3498f3465ca4SJosef Bacik btrfs_set_item_key(leaf, &disk_key, slot + i); 3499f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot + i); 3500f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 3501f3465ca4SJosef Bacik data_end -= data_size[i]; 3502f3465ca4SJosef Bacik btrfs_set_item_size(leaf, item, data_size[i]); 3503f3465ca4SJosef Bacik } 3504f3465ca4SJosef Bacik btrfs_set_header_nritems(leaf, nritems + nr); 3505f3465ca4SJosef Bacik btrfs_mark_buffer_dirty(leaf); 3506f3465ca4SJosef Bacik 3507f3465ca4SJosef Bacik ret = 0; 3508f3465ca4SJosef Bacik if (slot == 0) { 3509f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3510143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 3511f3465ca4SJosef Bacik } 3512f3465ca4SJosef Bacik 3513f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < 0) { 3514f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3515f3465ca4SJosef Bacik BUG(); 3516f3465ca4SJosef Bacik } 3517f3465ca4SJosef Bacik out: 3518f3465ca4SJosef Bacik if (!ret) 3519f3465ca4SJosef Bacik ret = nr; 3520f3465ca4SJosef Bacik return ret; 3521f3465ca4SJosef Bacik } 3522f3465ca4SJosef Bacik 3523f3465ca4SJosef Bacik /* 352444871b1bSChris Mason * this is a helper for btrfs_insert_empty_items, the main goal here is 352544871b1bSChris Mason * to save stack depth by doing the bulk of the work in a function 352644871b1bSChris Mason * that doesn't call btrfs_search_slot 352774123bd7SChris Mason */ 3528143bede5SJeff Mahoney void setup_items_for_insert(struct btrfs_trans_handle *trans, 352944871b1bSChris Mason struct btrfs_root *root, struct btrfs_path *path, 35309c58309dSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 353144871b1bSChris Mason u32 total_data, u32 total_size, int nr) 3532be0e5c09SChris Mason { 35335f39d397SChris Mason struct btrfs_item *item; 35349c58309dSChris Mason int i; 35357518a238SChris Mason u32 nritems; 3536be0e5c09SChris Mason unsigned int data_end; 3537e2fa7227SChris Mason struct btrfs_disk_key disk_key; 353844871b1bSChris Mason struct extent_buffer *leaf; 353944871b1bSChris Mason int slot; 3540e2fa7227SChris Mason 35415f39d397SChris Mason leaf = path->nodes[0]; 354244871b1bSChris Mason slot = path->slots[0]; 354374123bd7SChris Mason 35445f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3545123abc88SChris Mason data_end = leaf_data_end(root, leaf); 3546eb60ceacSChris Mason 3547f25956ccSChris Mason if (btrfs_leaf_free_space(root, leaf) < total_size) { 35483326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3549d397712bSChris Mason printk(KERN_CRIT "not enough freespace need %u have %d\n", 35509c58309dSChris Mason total_size, btrfs_leaf_free_space(root, leaf)); 3551be0e5c09SChris Mason BUG(); 3552d4dbff95SChris Mason } 35535f39d397SChris Mason 3554be0e5c09SChris Mason if (slot != nritems) { 35555f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3556be0e5c09SChris Mason 35575f39d397SChris Mason if (old_data < data_end) { 35585f39d397SChris Mason btrfs_print_leaf(root, leaf); 3559d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 35605f39d397SChris Mason slot, old_data, data_end); 35615f39d397SChris Mason BUG_ON(1); 35625f39d397SChris Mason } 3563be0e5c09SChris Mason /* 3564be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3565be0e5c09SChris Mason */ 3566be0e5c09SChris Mason /* first correct the data pointers */ 35670783fcfcSChris Mason for (i = slot; i < nritems; i++) { 35685f39d397SChris Mason u32 ioff; 3569db94535dSChris Mason 35705f39d397SChris Mason item = btrfs_item_nr(leaf, i); 35715f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 35729c58309dSChris Mason btrfs_set_item_offset(leaf, item, ioff - total_data); 35730783fcfcSChris Mason } 3574be0e5c09SChris Mason /* shift the items */ 35759c58309dSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 35765f39d397SChris Mason btrfs_item_nr_offset(slot), 35770783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3578be0e5c09SChris Mason 3579be0e5c09SChris Mason /* shift the data */ 35805f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 35819c58309dSChris Mason data_end - total_data, btrfs_leaf_data(leaf) + 3582be0e5c09SChris Mason data_end, old_data - data_end); 3583be0e5c09SChris Mason data_end = old_data; 3584be0e5c09SChris Mason } 35855f39d397SChris Mason 358662e2749eSChris Mason /* setup the item for the new data */ 35879c58309dSChris Mason for (i = 0; i < nr; i++) { 35889c58309dSChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 35899c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 35909c58309dSChris Mason item = btrfs_item_nr(leaf, slot + i); 35919c58309dSChris Mason btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 35929c58309dSChris Mason data_end -= data_size[i]; 35939c58309dSChris Mason btrfs_set_item_size(leaf, item, data_size[i]); 35949c58309dSChris Mason } 359544871b1bSChris Mason 35969c58309dSChris Mason btrfs_set_header_nritems(leaf, nritems + nr); 3597aa5d6bedSChris Mason 35985a01a2e3SChris Mason if (slot == 0) { 35995a01a2e3SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3600143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 36015a01a2e3SChris Mason } 3602b9473439SChris Mason btrfs_unlock_up_safe(path, 1); 3603b9473439SChris Mason btrfs_mark_buffer_dirty(leaf); 3604aa5d6bedSChris Mason 36055f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 36065f39d397SChris Mason btrfs_print_leaf(root, leaf); 3607be0e5c09SChris Mason BUG(); 36085f39d397SChris Mason } 360944871b1bSChris Mason } 361044871b1bSChris Mason 361144871b1bSChris Mason /* 361244871b1bSChris Mason * Given a key and some data, insert items into the tree. 361344871b1bSChris Mason * This does all the path init required, making room in the tree if needed. 361444871b1bSChris Mason */ 361544871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 361644871b1bSChris Mason struct btrfs_root *root, 361744871b1bSChris Mason struct btrfs_path *path, 361844871b1bSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 361944871b1bSChris Mason int nr) 362044871b1bSChris Mason { 362144871b1bSChris Mason int ret = 0; 362244871b1bSChris Mason int slot; 362344871b1bSChris Mason int i; 362444871b1bSChris Mason u32 total_size = 0; 362544871b1bSChris Mason u32 total_data = 0; 362644871b1bSChris Mason 362744871b1bSChris Mason for (i = 0; i < nr; i++) 362844871b1bSChris Mason total_data += data_size[i]; 362944871b1bSChris Mason 363044871b1bSChris Mason total_size = total_data + (nr * sizeof(struct btrfs_item)); 363144871b1bSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 363244871b1bSChris Mason if (ret == 0) 363344871b1bSChris Mason return -EEXIST; 363444871b1bSChris Mason if (ret < 0) 3635143bede5SJeff Mahoney return ret; 363644871b1bSChris Mason 363744871b1bSChris Mason slot = path->slots[0]; 363844871b1bSChris Mason BUG_ON(slot < 0); 363944871b1bSChris Mason 3640143bede5SJeff Mahoney setup_items_for_insert(trans, root, path, cpu_key, data_size, 364144871b1bSChris Mason total_data, total_size, nr); 3642143bede5SJeff Mahoney return 0; 364362e2749eSChris Mason } 364462e2749eSChris Mason 364562e2749eSChris Mason /* 364662e2749eSChris Mason * Given a key and some data, insert an item into the tree. 364762e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 364862e2749eSChris Mason */ 3649e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 3650e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 3651e089f05cSChris Mason data_size) 365262e2749eSChris Mason { 365362e2749eSChris Mason int ret = 0; 36542c90e5d6SChris Mason struct btrfs_path *path; 36555f39d397SChris Mason struct extent_buffer *leaf; 36565f39d397SChris Mason unsigned long ptr; 365762e2749eSChris Mason 36582c90e5d6SChris Mason path = btrfs_alloc_path(); 3659db5b493aSTsutomu Itoh if (!path) 3660db5b493aSTsutomu Itoh return -ENOMEM; 36612c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 366262e2749eSChris Mason if (!ret) { 36635f39d397SChris Mason leaf = path->nodes[0]; 36645f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 36655f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 36665f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 366762e2749eSChris Mason } 36682c90e5d6SChris Mason btrfs_free_path(path); 3669aa5d6bedSChris Mason return ret; 3670be0e5c09SChris Mason } 3671be0e5c09SChris Mason 367274123bd7SChris Mason /* 36735de08d7dSChris Mason * delete the pointer from a given node. 367474123bd7SChris Mason * 3675d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 3676d352ac68SChris Mason * empty a node. 367774123bd7SChris Mason */ 3678143bede5SJeff Mahoney static void del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 3679e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 3680be0e5c09SChris Mason { 36815f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 36827518a238SChris Mason u32 nritems; 3683be0e5c09SChris Mason 36845f39d397SChris Mason nritems = btrfs_header_nritems(parent); 3685be0e5c09SChris Mason if (slot != nritems - 1) { 36865f39d397SChris Mason memmove_extent_buffer(parent, 36875f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 36885f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 3689d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 3690d6025579SChris Mason (nritems - slot - 1)); 3691be0e5c09SChris Mason } 36927518a238SChris Mason nritems--; 36935f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 36947518a238SChris Mason if (nritems == 0 && parent == root->node) { 36955f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 3696eb60ceacSChris Mason /* just turn the root into a leaf and break */ 36975f39d397SChris Mason btrfs_set_header_level(root->node, 0); 3698bb803951SChris Mason } else if (slot == 0) { 36995f39d397SChris Mason struct btrfs_disk_key disk_key; 37005f39d397SChris Mason 37015f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 3702143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, level + 1); 3703be0e5c09SChris Mason } 3704d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 3705be0e5c09SChris Mason } 3706be0e5c09SChris Mason 370774123bd7SChris Mason /* 3708323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 37095d4f98a2SYan Zheng * path->nodes[1]. 3710323ac95bSChris Mason * 3711323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 3712323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 3713323ac95bSChris Mason * 3714323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 3715323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 3716323ac95bSChris Mason */ 3717143bede5SJeff Mahoney static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans, 3718323ac95bSChris Mason struct btrfs_root *root, 37195d4f98a2SYan Zheng struct btrfs_path *path, 37205d4f98a2SYan Zheng struct extent_buffer *leaf) 3721323ac95bSChris Mason { 37225d4f98a2SYan Zheng WARN_ON(btrfs_header_generation(leaf) != trans->transid); 3723143bede5SJeff Mahoney del_ptr(trans, root, path, 1, path->slots[1]); 3724323ac95bSChris Mason 37254d081c41SChris Mason /* 37264d081c41SChris Mason * btrfs_free_extent is expensive, we want to make sure we 37274d081c41SChris Mason * aren't holding any locks when we call it 37284d081c41SChris Mason */ 37294d081c41SChris Mason btrfs_unlock_up_safe(path, 0); 37304d081c41SChris Mason 3731f0486c68SYan, Zheng root_sub_used(root, leaf->len); 3732f0486c68SYan, Zheng 373366d7e7f0SArne Jansen btrfs_free_tree_block(trans, root, leaf, 0, 1, 0); 3734323ac95bSChris Mason } 3735323ac95bSChris Mason /* 373674123bd7SChris Mason * delete the item at the leaf level in path. If that empties 373774123bd7SChris Mason * the leaf, remove it from the tree 373874123bd7SChris Mason */ 373985e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 374085e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 3741be0e5c09SChris Mason { 37425f39d397SChris Mason struct extent_buffer *leaf; 37435f39d397SChris Mason struct btrfs_item *item; 374485e21bacSChris Mason int last_off; 374585e21bacSChris Mason int dsize = 0; 3746aa5d6bedSChris Mason int ret = 0; 3747aa5d6bedSChris Mason int wret; 374885e21bacSChris Mason int i; 37497518a238SChris Mason u32 nritems; 3750be0e5c09SChris Mason 37515f39d397SChris Mason leaf = path->nodes[0]; 375285e21bacSChris Mason last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); 375385e21bacSChris Mason 375485e21bacSChris Mason for (i = 0; i < nr; i++) 375585e21bacSChris Mason dsize += btrfs_item_size_nr(leaf, slot + i); 375685e21bacSChris Mason 37575f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3758be0e5c09SChris Mason 375985e21bacSChris Mason if (slot + nr != nritems) { 3760123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 37615f39d397SChris Mason 37625f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3763d6025579SChris Mason data_end + dsize, 3764123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 376585e21bacSChris Mason last_off - data_end); 37665f39d397SChris Mason 376785e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 37685f39d397SChris Mason u32 ioff; 3769db94535dSChris Mason 37705f39d397SChris Mason item = btrfs_item_nr(leaf, i); 37715f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 37725f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + dsize); 37730783fcfcSChris Mason } 3774db94535dSChris Mason 37755f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 377685e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 37770783fcfcSChris Mason sizeof(struct btrfs_item) * 377885e21bacSChris Mason (nritems - slot - nr)); 3779be0e5c09SChris Mason } 378085e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 378185e21bacSChris Mason nritems -= nr; 37825f39d397SChris Mason 378374123bd7SChris Mason /* delete the leaf if we've emptied it */ 37847518a238SChris Mason if (nritems == 0) { 37855f39d397SChris Mason if (leaf == root->node) { 37865f39d397SChris Mason btrfs_set_header_level(leaf, 0); 37879a8dd150SChris Mason } else { 3788f0486c68SYan, Zheng btrfs_set_path_blocking(path); 3789f0486c68SYan, Zheng clean_tree_block(trans, root, leaf); 3790143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 37919a8dd150SChris Mason } 3792be0e5c09SChris Mason } else { 37937518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 3794aa5d6bedSChris Mason if (slot == 0) { 37955f39d397SChris Mason struct btrfs_disk_key disk_key; 37965f39d397SChris Mason 37975f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 3798143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 3799aa5d6bedSChris Mason } 3800aa5d6bedSChris Mason 380174123bd7SChris Mason /* delete the leaf if it is mostly empty */ 3802d717aa1dSYan Zheng if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 3803be0e5c09SChris Mason /* push_leaf_left fixes the path. 3804be0e5c09SChris Mason * make sure the path still points to our leaf 3805be0e5c09SChris Mason * for possible call to del_ptr below 3806be0e5c09SChris Mason */ 38074920c9acSChris Mason slot = path->slots[1]; 38085f39d397SChris Mason extent_buffer_get(leaf); 38095f39d397SChris Mason 3810b9473439SChris Mason btrfs_set_path_blocking(path); 381199d8f83cSChris Mason wret = push_leaf_left(trans, root, path, 1, 1, 381299d8f83cSChris Mason 1, (u32)-1); 381354aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3814aa5d6bedSChris Mason ret = wret; 38155f39d397SChris Mason 38165f39d397SChris Mason if (path->nodes[0] == leaf && 38175f39d397SChris Mason btrfs_header_nritems(leaf)) { 381899d8f83cSChris Mason wret = push_leaf_right(trans, root, path, 1, 381999d8f83cSChris Mason 1, 1, 0); 382054aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3821aa5d6bedSChris Mason ret = wret; 3822aa5d6bedSChris Mason } 38235f39d397SChris Mason 38245f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 3825323ac95bSChris Mason path->slots[1] = slot; 3826143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 38275f39d397SChris Mason free_extent_buffer(leaf); 3828143bede5SJeff Mahoney ret = 0; 38295de08d7dSChris Mason } else { 3830925baeddSChris Mason /* if we're still in the path, make sure 3831925baeddSChris Mason * we're dirty. Otherwise, one of the 3832925baeddSChris Mason * push_leaf functions must have already 3833925baeddSChris Mason * dirtied this buffer 3834925baeddSChris Mason */ 3835925baeddSChris Mason if (path->nodes[0] == leaf) 38365f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 38375f39d397SChris Mason free_extent_buffer(leaf); 3838be0e5c09SChris Mason } 3839d5719762SChris Mason } else { 38405f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3841be0e5c09SChris Mason } 38429a8dd150SChris Mason } 3843aa5d6bedSChris Mason return ret; 38449a8dd150SChris Mason } 38459a8dd150SChris Mason 384697571fd0SChris Mason /* 3847925baeddSChris Mason * search the tree again to find a leaf with lesser keys 38487bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 38497bb86316SChris Mason * returns < 0 on io errors. 3850d352ac68SChris Mason * 3851d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 3852d352ac68SChris Mason * time you call it. 38537bb86316SChris Mason */ 38547bb86316SChris Mason int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 38557bb86316SChris Mason { 3856925baeddSChris Mason struct btrfs_key key; 3857925baeddSChris Mason struct btrfs_disk_key found_key; 3858925baeddSChris Mason int ret; 38597bb86316SChris Mason 3860925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 3861925baeddSChris Mason 3862925baeddSChris Mason if (key.offset > 0) 3863925baeddSChris Mason key.offset--; 3864925baeddSChris Mason else if (key.type > 0) 3865925baeddSChris Mason key.type--; 3866925baeddSChris Mason else if (key.objectid > 0) 3867925baeddSChris Mason key.objectid--; 3868925baeddSChris Mason else 38697bb86316SChris Mason return 1; 38707bb86316SChris Mason 3871b3b4aa74SDavid Sterba btrfs_release_path(path); 3872925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 3873925baeddSChris Mason if (ret < 0) 3874925baeddSChris Mason return ret; 3875925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 3876925baeddSChris Mason ret = comp_keys(&found_key, &key); 3877925baeddSChris Mason if (ret < 0) 38787bb86316SChris Mason return 0; 3879925baeddSChris Mason return 1; 38807bb86316SChris Mason } 38817bb86316SChris Mason 38823f157a2fSChris Mason /* 38833f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 38843f157a2fSChris Mason * for nodes or leaves that are either in cache or have a minimum 3885d352ac68SChris Mason * transaction id. This is used by the btree defrag code, and tree logging 38863f157a2fSChris Mason * 38873f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 38883f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 38893f157a2fSChris Mason * key and get a writable path. 38903f157a2fSChris Mason * 38913f157a2fSChris Mason * This does lock as it descends, and path->keep_locks should be set 38923f157a2fSChris Mason * to 1 by the caller. 38933f157a2fSChris Mason * 38943f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 38953f157a2fSChris Mason * of the tree. 38963f157a2fSChris Mason * 3897d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 3898d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 3899d352ac68SChris Mason * skipped over (without reading them). 3900d352ac68SChris Mason * 39013f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 39023f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 39033f157a2fSChris Mason */ 39043f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 3905e02119d5SChris Mason struct btrfs_key *max_key, 39063f157a2fSChris Mason struct btrfs_path *path, int cache_only, 39073f157a2fSChris Mason u64 min_trans) 39083f157a2fSChris Mason { 39093f157a2fSChris Mason struct extent_buffer *cur; 39103f157a2fSChris Mason struct btrfs_key found_key; 39113f157a2fSChris Mason int slot; 39129652480bSYan int sret; 39133f157a2fSChris Mason u32 nritems; 39143f157a2fSChris Mason int level; 39153f157a2fSChris Mason int ret = 1; 39163f157a2fSChris Mason 3917934d375bSChris Mason WARN_ON(!path->keep_locks); 39183f157a2fSChris Mason again: 3919bd681513SChris Mason cur = btrfs_read_lock_root_node(root); 39203f157a2fSChris Mason level = btrfs_header_level(cur); 3921e02119d5SChris Mason WARN_ON(path->nodes[level]); 39223f157a2fSChris Mason path->nodes[level] = cur; 3923bd681513SChris Mason path->locks[level] = BTRFS_READ_LOCK; 39243f157a2fSChris Mason 39253f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 39263f157a2fSChris Mason ret = 1; 39273f157a2fSChris Mason goto out; 39283f157a2fSChris Mason } 39293f157a2fSChris Mason while (1) { 39303f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 39313f157a2fSChris Mason level = btrfs_header_level(cur); 39329652480bSYan sret = bin_search(cur, min_key, level, &slot); 39333f157a2fSChris Mason 3934323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 3935323ac95bSChris Mason if (level == path->lowest_level) { 3936e02119d5SChris Mason if (slot >= nritems) 3937e02119d5SChris Mason goto find_next_key; 39383f157a2fSChris Mason ret = 0; 39393f157a2fSChris Mason path->slots[level] = slot; 39403f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 39413f157a2fSChris Mason goto out; 39423f157a2fSChris Mason } 39439652480bSYan if (sret && slot > 0) 39449652480bSYan slot--; 39453f157a2fSChris Mason /* 39463f157a2fSChris Mason * check this node pointer against the cache_only and 39473f157a2fSChris Mason * min_trans parameters. If it isn't in cache or is too 39483f157a2fSChris Mason * old, skip to the next one. 39493f157a2fSChris Mason */ 39503f157a2fSChris Mason while (slot < nritems) { 39513f157a2fSChris Mason u64 blockptr; 39523f157a2fSChris Mason u64 gen; 39533f157a2fSChris Mason struct extent_buffer *tmp; 3954e02119d5SChris Mason struct btrfs_disk_key disk_key; 3955e02119d5SChris Mason 39563f157a2fSChris Mason blockptr = btrfs_node_blockptr(cur, slot); 39573f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 39583f157a2fSChris Mason if (gen < min_trans) { 39593f157a2fSChris Mason slot++; 39603f157a2fSChris Mason continue; 39613f157a2fSChris Mason } 39623f157a2fSChris Mason if (!cache_only) 39633f157a2fSChris Mason break; 39643f157a2fSChris Mason 3965e02119d5SChris Mason if (max_key) { 3966e02119d5SChris Mason btrfs_node_key(cur, &disk_key, slot); 3967e02119d5SChris Mason if (comp_keys(&disk_key, max_key) >= 0) { 3968e02119d5SChris Mason ret = 1; 3969e02119d5SChris Mason goto out; 3970e02119d5SChris Mason } 3971e02119d5SChris Mason } 3972e02119d5SChris Mason 39733f157a2fSChris Mason tmp = btrfs_find_tree_block(root, blockptr, 39743f157a2fSChris Mason btrfs_level_size(root, level - 1)); 39753f157a2fSChris Mason 39763f157a2fSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 39773f157a2fSChris Mason free_extent_buffer(tmp); 39783f157a2fSChris Mason break; 39793f157a2fSChris Mason } 39803f157a2fSChris Mason if (tmp) 39813f157a2fSChris Mason free_extent_buffer(tmp); 39823f157a2fSChris Mason slot++; 39833f157a2fSChris Mason } 3984e02119d5SChris Mason find_next_key: 39853f157a2fSChris Mason /* 39863f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 39873f157a2fSChris Mason * and find another one 39883f157a2fSChris Mason */ 39893f157a2fSChris Mason if (slot >= nritems) { 3990e02119d5SChris Mason path->slots[level] = slot; 3991b4ce94deSChris Mason btrfs_set_path_blocking(path); 3992e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 39933f157a2fSChris Mason cache_only, min_trans); 3994e02119d5SChris Mason if (sret == 0) { 3995b3b4aa74SDavid Sterba btrfs_release_path(path); 39963f157a2fSChris Mason goto again; 39973f157a2fSChris Mason } else { 39983f157a2fSChris Mason goto out; 39993f157a2fSChris Mason } 40003f157a2fSChris Mason } 40013f157a2fSChris Mason /* save our key for returning back */ 40023f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 40033f157a2fSChris Mason path->slots[level] = slot; 40043f157a2fSChris Mason if (level == path->lowest_level) { 40053f157a2fSChris Mason ret = 0; 40063f157a2fSChris Mason unlock_up(path, level, 1); 40073f157a2fSChris Mason goto out; 40083f157a2fSChris Mason } 4009b4ce94deSChris Mason btrfs_set_path_blocking(path); 40103f157a2fSChris Mason cur = read_node_slot(root, cur, slot); 401197d9a8a4STsutomu Itoh BUG_ON(!cur); 40123f157a2fSChris Mason 4013bd681513SChris Mason btrfs_tree_read_lock(cur); 4014b4ce94deSChris Mason 4015bd681513SChris Mason path->locks[level - 1] = BTRFS_READ_LOCK; 40163f157a2fSChris Mason path->nodes[level - 1] = cur; 40173f157a2fSChris Mason unlock_up(path, level, 1); 4018bd681513SChris Mason btrfs_clear_path_blocking(path, NULL, 0); 40193f157a2fSChris Mason } 40203f157a2fSChris Mason out: 40213f157a2fSChris Mason if (ret == 0) 40223f157a2fSChris Mason memcpy(min_key, &found_key, sizeof(found_key)); 4023b4ce94deSChris Mason btrfs_set_path_blocking(path); 40243f157a2fSChris Mason return ret; 40253f157a2fSChris Mason } 40263f157a2fSChris Mason 40273f157a2fSChris Mason /* 40283f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 40293f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 40303f157a2fSChris Mason * tree based on the current path and the cache_only and min_trans 40313f157a2fSChris Mason * parameters. 40323f157a2fSChris Mason * 40333f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 40343f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 40353f157a2fSChris Mason * 40363f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 40373f157a2fSChris Mason * calling this function. 40383f157a2fSChris Mason */ 4039e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 404033c66f43SYan Zheng struct btrfs_key *key, int level, 40413f157a2fSChris Mason int cache_only, u64 min_trans) 4042e7a84565SChris Mason { 4043e7a84565SChris Mason int slot; 4044e7a84565SChris Mason struct extent_buffer *c; 4045e7a84565SChris Mason 4046934d375bSChris Mason WARN_ON(!path->keep_locks); 4047e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 4048e7a84565SChris Mason if (!path->nodes[level]) 4049e7a84565SChris Mason return 1; 4050e7a84565SChris Mason 4051e7a84565SChris Mason slot = path->slots[level] + 1; 4052e7a84565SChris Mason c = path->nodes[level]; 40533f157a2fSChris Mason next: 4054e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 405533c66f43SYan Zheng int ret; 405633c66f43SYan Zheng int orig_lowest; 405733c66f43SYan Zheng struct btrfs_key cur_key; 405833c66f43SYan Zheng if (level + 1 >= BTRFS_MAX_LEVEL || 405933c66f43SYan Zheng !path->nodes[level + 1]) 4060e7a84565SChris Mason return 1; 406133c66f43SYan Zheng 406233c66f43SYan Zheng if (path->locks[level + 1]) { 406333c66f43SYan Zheng level++; 4064e7a84565SChris Mason continue; 4065e7a84565SChris Mason } 406633c66f43SYan Zheng 406733c66f43SYan Zheng slot = btrfs_header_nritems(c) - 1; 406833c66f43SYan Zheng if (level == 0) 406933c66f43SYan Zheng btrfs_item_key_to_cpu(c, &cur_key, slot); 407033c66f43SYan Zheng else 407133c66f43SYan Zheng btrfs_node_key_to_cpu(c, &cur_key, slot); 407233c66f43SYan Zheng 407333c66f43SYan Zheng orig_lowest = path->lowest_level; 4074b3b4aa74SDavid Sterba btrfs_release_path(path); 407533c66f43SYan Zheng path->lowest_level = level; 407633c66f43SYan Zheng ret = btrfs_search_slot(NULL, root, &cur_key, path, 407733c66f43SYan Zheng 0, 0); 407833c66f43SYan Zheng path->lowest_level = orig_lowest; 407933c66f43SYan Zheng if (ret < 0) 408033c66f43SYan Zheng return ret; 408133c66f43SYan Zheng 408233c66f43SYan Zheng c = path->nodes[level]; 408333c66f43SYan Zheng slot = path->slots[level]; 408433c66f43SYan Zheng if (ret == 0) 408533c66f43SYan Zheng slot++; 408633c66f43SYan Zheng goto next; 408733c66f43SYan Zheng } 408833c66f43SYan Zheng 4089e7a84565SChris Mason if (level == 0) 4090e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 40913f157a2fSChris Mason else { 40923f157a2fSChris Mason u64 blockptr = btrfs_node_blockptr(c, slot); 40933f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 40943f157a2fSChris Mason 40953f157a2fSChris Mason if (cache_only) { 40963f157a2fSChris Mason struct extent_buffer *cur; 40973f157a2fSChris Mason cur = btrfs_find_tree_block(root, blockptr, 40983f157a2fSChris Mason btrfs_level_size(root, level - 1)); 40993f157a2fSChris Mason if (!cur || !btrfs_buffer_uptodate(cur, gen)) { 41003f157a2fSChris Mason slot++; 41013f157a2fSChris Mason if (cur) 41023f157a2fSChris Mason free_extent_buffer(cur); 41033f157a2fSChris Mason goto next; 41043f157a2fSChris Mason } 41053f157a2fSChris Mason free_extent_buffer(cur); 41063f157a2fSChris Mason } 41073f157a2fSChris Mason if (gen < min_trans) { 41083f157a2fSChris Mason slot++; 41093f157a2fSChris Mason goto next; 41103f157a2fSChris Mason } 4111e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 41123f157a2fSChris Mason } 4113e7a84565SChris Mason return 0; 4114e7a84565SChris Mason } 4115e7a84565SChris Mason return 1; 4116e7a84565SChris Mason } 4117e7a84565SChris Mason 41187bb86316SChris Mason /* 4119925baeddSChris Mason * search the tree again to find a leaf with greater keys 41200f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 41210f70abe2SChris Mason * returns < 0 on io errors. 412297571fd0SChris Mason */ 4123234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 4124d97e63b6SChris Mason { 4125d97e63b6SChris Mason int slot; 41268e73f275SChris Mason int level; 41275f39d397SChris Mason struct extent_buffer *c; 41288e73f275SChris Mason struct extent_buffer *next; 4129925baeddSChris Mason struct btrfs_key key; 4130925baeddSChris Mason u32 nritems; 4131925baeddSChris Mason int ret; 41328e73f275SChris Mason int old_spinning = path->leave_spinning; 4133bd681513SChris Mason int next_rw_lock = 0; 4134925baeddSChris Mason 4135925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4136d397712bSChris Mason if (nritems == 0) 4137925baeddSChris Mason return 1; 4138925baeddSChris Mason 41398e73f275SChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 41408e73f275SChris Mason again: 41418e73f275SChris Mason level = 1; 41428e73f275SChris Mason next = NULL; 4143bd681513SChris Mason next_rw_lock = 0; 4144b3b4aa74SDavid Sterba btrfs_release_path(path); 41458e73f275SChris Mason 4146a2135011SChris Mason path->keep_locks = 1; 41478e73f275SChris Mason path->leave_spinning = 1; 41488e73f275SChris Mason 4149925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4150925baeddSChris Mason path->keep_locks = 0; 4151925baeddSChris Mason 4152925baeddSChris Mason if (ret < 0) 4153925baeddSChris Mason return ret; 4154925baeddSChris Mason 4155a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4156168fd7d2SChris Mason /* 4157168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 4158168fd7d2SChris Mason * could have added more items next to the key that used to be 4159168fd7d2SChris Mason * at the very end of the block. So, check again here and 4160168fd7d2SChris Mason * advance the path if there are now more items available. 4161168fd7d2SChris Mason */ 4162a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 4163e457afecSYan Zheng if (ret == 0) 4164168fd7d2SChris Mason path->slots[0]++; 41658e73f275SChris Mason ret = 0; 4166925baeddSChris Mason goto done; 4167925baeddSChris Mason } 4168d97e63b6SChris Mason 4169234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 41708e73f275SChris Mason if (!path->nodes[level]) { 41718e73f275SChris Mason ret = 1; 41728e73f275SChris Mason goto done; 41738e73f275SChris Mason } 41745f39d397SChris Mason 4175d97e63b6SChris Mason slot = path->slots[level] + 1; 4176d97e63b6SChris Mason c = path->nodes[level]; 41775f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 4178d97e63b6SChris Mason level++; 41798e73f275SChris Mason if (level == BTRFS_MAX_LEVEL) { 41808e73f275SChris Mason ret = 1; 41818e73f275SChris Mason goto done; 41828e73f275SChris Mason } 4183d97e63b6SChris Mason continue; 4184d97e63b6SChris Mason } 41855f39d397SChris Mason 4186925baeddSChris Mason if (next) { 4187bd681513SChris Mason btrfs_tree_unlock_rw(next, next_rw_lock); 41885f39d397SChris Mason free_extent_buffer(next); 4189925baeddSChris Mason } 41905f39d397SChris Mason 41918e73f275SChris Mason next = c; 4192bd681513SChris Mason next_rw_lock = path->locks[level]; 41938e73f275SChris Mason ret = read_block_for_search(NULL, root, path, &next, level, 41948e73f275SChris Mason slot, &key); 41958e73f275SChris Mason if (ret == -EAGAIN) 41968e73f275SChris Mason goto again; 41975f39d397SChris Mason 419876a05b35SChris Mason if (ret < 0) { 4199b3b4aa74SDavid Sterba btrfs_release_path(path); 420076a05b35SChris Mason goto done; 420176a05b35SChris Mason } 420276a05b35SChris Mason 42035cd57b2cSChris Mason if (!path->skip_locking) { 4204bd681513SChris Mason ret = btrfs_try_tree_read_lock(next); 42058e73f275SChris Mason if (!ret) { 42068e73f275SChris Mason btrfs_set_path_blocking(path); 4207bd681513SChris Mason btrfs_tree_read_lock(next); 4208bd681513SChris Mason btrfs_clear_path_blocking(path, next, 4209bd681513SChris Mason BTRFS_READ_LOCK); 42108e73f275SChris Mason } 4211bd681513SChris Mason next_rw_lock = BTRFS_READ_LOCK; 4212bd681513SChris Mason } 4213d97e63b6SChris Mason break; 4214d97e63b6SChris Mason } 4215d97e63b6SChris Mason path->slots[level] = slot; 4216d97e63b6SChris Mason while (1) { 4217d97e63b6SChris Mason level--; 4218d97e63b6SChris Mason c = path->nodes[level]; 4219925baeddSChris Mason if (path->locks[level]) 4220bd681513SChris Mason btrfs_tree_unlock_rw(c, path->locks[level]); 42218e73f275SChris Mason 42225f39d397SChris Mason free_extent_buffer(c); 4223d97e63b6SChris Mason path->nodes[level] = next; 4224d97e63b6SChris Mason path->slots[level] = 0; 4225a74a4b97SChris Mason if (!path->skip_locking) 4226bd681513SChris Mason path->locks[level] = next_rw_lock; 4227d97e63b6SChris Mason if (!level) 4228d97e63b6SChris Mason break; 4229b4ce94deSChris Mason 42308e73f275SChris Mason ret = read_block_for_search(NULL, root, path, &next, level, 42318e73f275SChris Mason 0, &key); 42328e73f275SChris Mason if (ret == -EAGAIN) 42338e73f275SChris Mason goto again; 42348e73f275SChris Mason 423576a05b35SChris Mason if (ret < 0) { 4236b3b4aa74SDavid Sterba btrfs_release_path(path); 423776a05b35SChris Mason goto done; 423876a05b35SChris Mason } 423976a05b35SChris Mason 42405cd57b2cSChris Mason if (!path->skip_locking) { 4241bd681513SChris Mason ret = btrfs_try_tree_read_lock(next); 42428e73f275SChris Mason if (!ret) { 42438e73f275SChris Mason btrfs_set_path_blocking(path); 4244bd681513SChris Mason btrfs_tree_read_lock(next); 4245bd681513SChris Mason btrfs_clear_path_blocking(path, next, 4246bd681513SChris Mason BTRFS_READ_LOCK); 42478e73f275SChris Mason } 4248bd681513SChris Mason next_rw_lock = BTRFS_READ_LOCK; 4249bd681513SChris Mason } 4250d97e63b6SChris Mason } 42518e73f275SChris Mason ret = 0; 4252925baeddSChris Mason done: 4253925baeddSChris Mason unlock_up(path, 0, 1); 42548e73f275SChris Mason path->leave_spinning = old_spinning; 42558e73f275SChris Mason if (!old_spinning) 42568e73f275SChris Mason btrfs_set_path_blocking(path); 42578e73f275SChris Mason 42588e73f275SChris Mason return ret; 4259d97e63b6SChris Mason } 42600b86a832SChris Mason 42613f157a2fSChris Mason /* 42623f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 42633f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 42643f157a2fSChris Mason * 42653f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 42663f157a2fSChris Mason */ 42670b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 42680b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 42690b86a832SChris Mason int type) 42700b86a832SChris Mason { 42710b86a832SChris Mason struct btrfs_key found_key; 42720b86a832SChris Mason struct extent_buffer *leaf; 4273e02119d5SChris Mason u32 nritems; 42740b86a832SChris Mason int ret; 42750b86a832SChris Mason 42760b86a832SChris Mason while (1) { 42770b86a832SChris Mason if (path->slots[0] == 0) { 4278b4ce94deSChris Mason btrfs_set_path_blocking(path); 42790b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 42800b86a832SChris Mason if (ret != 0) 42810b86a832SChris Mason return ret; 42820b86a832SChris Mason } else { 42830b86a832SChris Mason path->slots[0]--; 42840b86a832SChris Mason } 42850b86a832SChris Mason leaf = path->nodes[0]; 4286e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 4287e02119d5SChris Mason if (nritems == 0) 4288e02119d5SChris Mason return 1; 4289e02119d5SChris Mason if (path->slots[0] == nritems) 4290e02119d5SChris Mason path->slots[0]--; 4291e02119d5SChris Mason 42920b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4293e02119d5SChris Mason if (found_key.objectid < min_objectid) 4294e02119d5SChris Mason break; 42950a4eefbbSYan Zheng if (found_key.type == type) 42960a4eefbbSYan Zheng return 0; 4297e02119d5SChris Mason if (found_key.objectid == min_objectid && 4298e02119d5SChris Mason found_key.type < type) 4299e02119d5SChris Mason break; 43000b86a832SChris Mason } 43010b86a832SChris Mason return 1; 43020b86a832SChris Mason } 4303