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); 39e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 40e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 41ad48fd75SYan, Zheng static int setup_items_for_insert(struct btrfs_trans_handle *trans, 42ad48fd75SYan, Zheng struct btrfs_root *root, struct btrfs_path *path, 43ad48fd75SYan, Zheng struct btrfs_key *cpu_key, u32 *data_size, 44ad48fd75SYan, Zheng u32 total_data, u32 total_size, int nr); 45ad48fd75SYan, Zheng 46d97e63b6SChris Mason 472c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 482c90e5d6SChris Mason { 49df24a2b9SChris Mason struct btrfs_path *path; 50e00f7308SJeff Mahoney path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 51e00f7308SJeff Mahoney if (path) 522cc58cf2SChris Mason path->reada = 1; 53df24a2b9SChris Mason return path; 542c90e5d6SChris Mason } 552c90e5d6SChris Mason 56b4ce94deSChris Mason /* 57b4ce94deSChris Mason * set all locked nodes in the path to blocking locks. This should 58b4ce94deSChris Mason * be done before scheduling 59b4ce94deSChris Mason */ 60b4ce94deSChris Mason noinline void btrfs_set_path_blocking(struct btrfs_path *p) 61b4ce94deSChris Mason { 62b4ce94deSChris Mason int i; 63b4ce94deSChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 64b4ce94deSChris Mason if (p->nodes[i] && p->locks[i]) 65b4ce94deSChris Mason btrfs_set_lock_blocking(p->nodes[i]); 66b4ce94deSChris Mason } 67b4ce94deSChris Mason } 68b4ce94deSChris Mason 69b4ce94deSChris Mason /* 70b4ce94deSChris Mason * reset all the locked nodes in the patch to spinning locks. 714008c04aSChris Mason * 724008c04aSChris Mason * held is used to keep lockdep happy, when lockdep is enabled 734008c04aSChris Mason * we set held to a blocking lock before we go around and 744008c04aSChris Mason * retake all the spinlocks in the path. You can safely use NULL 754008c04aSChris Mason * for held 76b4ce94deSChris Mason */ 774008c04aSChris Mason noinline void btrfs_clear_path_blocking(struct btrfs_path *p, 784008c04aSChris Mason struct extent_buffer *held) 79b4ce94deSChris Mason { 80b4ce94deSChris Mason int i; 814008c04aSChris Mason 824008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 834008c04aSChris Mason /* lockdep really cares that we take all of these spinlocks 844008c04aSChris Mason * in the right order. If any of the locks in the path are not 854008c04aSChris Mason * currently blocking, it is going to complain. So, make really 864008c04aSChris Mason * really sure by forcing the path to blocking before we clear 874008c04aSChris Mason * the path blocking. 884008c04aSChris Mason */ 894008c04aSChris Mason if (held) 904008c04aSChris Mason btrfs_set_lock_blocking(held); 914008c04aSChris Mason btrfs_set_path_blocking(p); 924008c04aSChris Mason #endif 934008c04aSChris Mason 944008c04aSChris Mason for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) { 95b4ce94deSChris Mason if (p->nodes[i] && p->locks[i]) 96b4ce94deSChris Mason btrfs_clear_lock_blocking(p->nodes[i]); 97b4ce94deSChris Mason } 984008c04aSChris Mason 994008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 1004008c04aSChris Mason if (held) 1014008c04aSChris Mason btrfs_clear_lock_blocking(held); 1024008c04aSChris Mason #endif 103b4ce94deSChris Mason } 104b4ce94deSChris Mason 105d352ac68SChris Mason /* this also releases the path */ 1062c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 1072c90e5d6SChris Mason { 108df24a2b9SChris Mason btrfs_release_path(NULL, p); 1092c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 1102c90e5d6SChris Mason } 1112c90e5d6SChris Mason 112d352ac68SChris Mason /* 113d352ac68SChris Mason * path release drops references on the extent buffers in the path 114d352ac68SChris Mason * and it drops any locks held by this path 115d352ac68SChris Mason * 116d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 117d352ac68SChris Mason */ 118d397712bSChris Mason noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 119eb60ceacSChris Mason { 120eb60ceacSChris Mason int i; 121a2135011SChris Mason 122234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 1233f157a2fSChris Mason p->slots[i] = 0; 124eb60ceacSChris Mason if (!p->nodes[i]) 125925baeddSChris Mason continue; 126925baeddSChris Mason if (p->locks[i]) { 127925baeddSChris Mason btrfs_tree_unlock(p->nodes[i]); 128925baeddSChris Mason p->locks[i] = 0; 129925baeddSChris Mason } 1305f39d397SChris Mason free_extent_buffer(p->nodes[i]); 1313f157a2fSChris Mason p->nodes[i] = NULL; 132eb60ceacSChris Mason } 133eb60ceacSChris Mason } 134eb60ceacSChris Mason 135d352ac68SChris Mason /* 136d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 137d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 138d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 139d352ac68SChris Mason * looping required. 140d352ac68SChris Mason * 141d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 142d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 143d352ac68SChris Mason * at any time because there are no locks held. 144d352ac68SChris Mason */ 145925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 146925baeddSChris Mason { 147925baeddSChris Mason struct extent_buffer *eb; 148925baeddSChris Mason spin_lock(&root->node_lock); 149925baeddSChris Mason eb = root->node; 150925baeddSChris Mason extent_buffer_get(eb); 151925baeddSChris Mason spin_unlock(&root->node_lock); 152925baeddSChris Mason return eb; 153925baeddSChris Mason } 154925baeddSChris Mason 155d352ac68SChris Mason /* loop around taking references on and locking the root node of the 156d352ac68SChris Mason * tree until you end up with a lock on the root. A locked buffer 157d352ac68SChris Mason * is returned, with a reference held. 158d352ac68SChris Mason */ 159925baeddSChris Mason struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root) 160925baeddSChris Mason { 161925baeddSChris Mason struct extent_buffer *eb; 162925baeddSChris Mason 163925baeddSChris Mason while (1) { 164925baeddSChris Mason eb = btrfs_root_node(root); 165925baeddSChris Mason btrfs_tree_lock(eb); 166925baeddSChris Mason 167925baeddSChris Mason spin_lock(&root->node_lock); 168925baeddSChris Mason if (eb == root->node) { 169925baeddSChris Mason spin_unlock(&root->node_lock); 170925baeddSChris Mason break; 171925baeddSChris Mason } 172925baeddSChris Mason spin_unlock(&root->node_lock); 173925baeddSChris Mason 174925baeddSChris Mason btrfs_tree_unlock(eb); 175925baeddSChris Mason free_extent_buffer(eb); 176925baeddSChris Mason } 177925baeddSChris Mason return eb; 178925baeddSChris Mason } 179925baeddSChris Mason 180d352ac68SChris Mason /* cowonly root (everything not a reference counted cow subvolume), just get 181d352ac68SChris Mason * put onto a simple dirty list. transaction.c walks this to make sure they 182d352ac68SChris Mason * get properly updated on disk. 183d352ac68SChris Mason */ 1840b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 1850b86a832SChris Mason { 1860b86a832SChris Mason if (root->track_dirty && list_empty(&root->dirty_list)) { 1870b86a832SChris Mason list_add(&root->dirty_list, 1880b86a832SChris Mason &root->fs_info->dirty_cowonly_roots); 1890b86a832SChris Mason } 1900b86a832SChris Mason } 1910b86a832SChris Mason 192d352ac68SChris Mason /* 193d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 194d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 195d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 196d352ac68SChris Mason */ 197be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 198be20aa9dSChris Mason struct btrfs_root *root, 199be20aa9dSChris Mason struct extent_buffer *buf, 200be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 201be20aa9dSChris Mason { 202be20aa9dSChris Mason struct extent_buffer *cow; 203be20aa9dSChris Mason u32 nritems; 204be20aa9dSChris Mason int ret = 0; 205be20aa9dSChris Mason int level; 2065d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 207be20aa9dSChris Mason 208be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != 209be20aa9dSChris Mason root->fs_info->running_transaction->transid); 210be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 211be20aa9dSChris Mason 212be20aa9dSChris Mason level = btrfs_header_level(buf); 213be20aa9dSChris Mason nritems = btrfs_header_nritems(buf); 2145d4f98a2SYan Zheng if (level == 0) 2155d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 2165d4f98a2SYan Zheng else 2175d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 21831840ae1SZheng Yan 2195d4f98a2SYan Zheng cow = btrfs_alloc_free_block(trans, root, buf->len, 0, 2205d4f98a2SYan Zheng new_root_objectid, &disk_key, level, 2215d4f98a2SYan Zheng buf->start, 0); 2225d4f98a2SYan Zheng if (IS_ERR(cow)) 223be20aa9dSChris Mason return PTR_ERR(cow); 224be20aa9dSChris Mason 225be20aa9dSChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 226be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 227be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 2285d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 2295d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 2305d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 2315d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 2325d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 2335d4f98a2SYan Zheng else 234be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 235be20aa9dSChris Mason 2362b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 2372b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 2382b82032cSYan Zheng BTRFS_FSID_SIZE); 2392b82032cSYan Zheng 240be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 2415d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 2425d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 1); 2435d4f98a2SYan Zheng else 2445d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 0); 2454aec2b52SChris Mason 246be20aa9dSChris Mason if (ret) 247be20aa9dSChris Mason return ret; 248be20aa9dSChris Mason 249be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 250be20aa9dSChris Mason *cow_ret = cow; 251be20aa9dSChris Mason return 0; 252be20aa9dSChris Mason } 253be20aa9dSChris Mason 254d352ac68SChris Mason /* 2555d4f98a2SYan Zheng * check if the tree block can be shared by multiple trees 2565d4f98a2SYan Zheng */ 2575d4f98a2SYan Zheng int btrfs_block_can_be_shared(struct btrfs_root *root, 2585d4f98a2SYan Zheng struct extent_buffer *buf) 2595d4f98a2SYan Zheng { 2605d4f98a2SYan Zheng /* 2615d4f98a2SYan Zheng * Tree blocks not in refernece counted trees and tree roots 2625d4f98a2SYan Zheng * are never shared. If a block was allocated after the last 2635d4f98a2SYan Zheng * snapshot and the block was not allocated by tree relocation, 2645d4f98a2SYan Zheng * we know the block is not shared. 2655d4f98a2SYan Zheng */ 2665d4f98a2SYan Zheng if (root->ref_cows && 2675d4f98a2SYan Zheng buf != root->node && buf != root->commit_root && 2685d4f98a2SYan Zheng (btrfs_header_generation(buf) <= 2695d4f98a2SYan Zheng btrfs_root_last_snapshot(&root->root_item) || 2705d4f98a2SYan Zheng btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 2715d4f98a2SYan Zheng return 1; 2725d4f98a2SYan Zheng #ifdef BTRFS_COMPAT_EXTENT_TREE_V0 2735d4f98a2SYan Zheng if (root->ref_cows && 2745d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 2755d4f98a2SYan Zheng return 1; 2765d4f98a2SYan Zheng #endif 2775d4f98a2SYan Zheng return 0; 2785d4f98a2SYan Zheng } 2795d4f98a2SYan Zheng 2805d4f98a2SYan Zheng static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans, 2815d4f98a2SYan Zheng struct btrfs_root *root, 2825d4f98a2SYan Zheng struct extent_buffer *buf, 2835d4f98a2SYan Zheng struct extent_buffer *cow) 2845d4f98a2SYan Zheng { 2855d4f98a2SYan Zheng u64 refs; 2865d4f98a2SYan Zheng u64 owner; 2875d4f98a2SYan Zheng u64 flags; 2885d4f98a2SYan Zheng u64 new_flags = 0; 2895d4f98a2SYan Zheng int ret; 2905d4f98a2SYan Zheng 2915d4f98a2SYan Zheng /* 2925d4f98a2SYan Zheng * Backrefs update rules: 2935d4f98a2SYan Zheng * 2945d4f98a2SYan Zheng * Always use full backrefs for extent pointers in tree block 2955d4f98a2SYan Zheng * allocated by tree relocation. 2965d4f98a2SYan Zheng * 2975d4f98a2SYan Zheng * If a shared tree block is no longer referenced by its owner 2985d4f98a2SYan Zheng * tree (btrfs_header_owner(buf) == root->root_key.objectid), 2995d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 3005d4f98a2SYan Zheng * 3015d4f98a2SYan Zheng * If a tree block is been relocating 3025d4f98a2SYan Zheng * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID), 3035d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 3045d4f98a2SYan Zheng * The reason for this is some operations (such as drop tree) 3055d4f98a2SYan Zheng * are only allowed for blocks use full backrefs. 3065d4f98a2SYan Zheng */ 3075d4f98a2SYan Zheng 3085d4f98a2SYan Zheng if (btrfs_block_can_be_shared(root, buf)) { 3095d4f98a2SYan Zheng ret = btrfs_lookup_extent_info(trans, root, buf->start, 3105d4f98a2SYan Zheng buf->len, &refs, &flags); 3115d4f98a2SYan Zheng BUG_ON(ret); 3125d4f98a2SYan Zheng BUG_ON(refs == 0); 3135d4f98a2SYan Zheng } else { 3145d4f98a2SYan Zheng refs = 1; 3155d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 3165d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 3175d4f98a2SYan Zheng flags = BTRFS_BLOCK_FLAG_FULL_BACKREF; 3185d4f98a2SYan Zheng else 3195d4f98a2SYan Zheng flags = 0; 3205d4f98a2SYan Zheng } 3215d4f98a2SYan Zheng 3225d4f98a2SYan Zheng owner = btrfs_header_owner(buf); 3235d4f98a2SYan Zheng BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID && 3245d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)); 3255d4f98a2SYan Zheng 3265d4f98a2SYan Zheng if (refs > 1) { 3275d4f98a2SYan Zheng if ((owner == root->root_key.objectid || 3285d4f98a2SYan Zheng root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && 3295d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 3305d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, buf, 1); 3315d4f98a2SYan Zheng BUG_ON(ret); 3325d4f98a2SYan Zheng 3335d4f98a2SYan Zheng if (root->root_key.objectid == 3345d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 3355d4f98a2SYan Zheng ret = btrfs_dec_ref(trans, root, buf, 0); 3365d4f98a2SYan Zheng BUG_ON(ret); 3375d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 1); 3385d4f98a2SYan Zheng BUG_ON(ret); 3395d4f98a2SYan Zheng } 3405d4f98a2SYan Zheng new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; 3415d4f98a2SYan Zheng } else { 3425d4f98a2SYan Zheng 3435d4f98a2SYan Zheng if (root->root_key.objectid == 3445d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 3455d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 1); 3465d4f98a2SYan Zheng else 3475d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 0); 3485d4f98a2SYan Zheng BUG_ON(ret); 3495d4f98a2SYan Zheng } 3505d4f98a2SYan Zheng if (new_flags != 0) { 3515d4f98a2SYan Zheng ret = btrfs_set_disk_extent_flags(trans, root, 3525d4f98a2SYan Zheng buf->start, 3535d4f98a2SYan Zheng buf->len, 3545d4f98a2SYan Zheng new_flags, 0); 3555d4f98a2SYan Zheng BUG_ON(ret); 3565d4f98a2SYan Zheng } 3575d4f98a2SYan Zheng } else { 3585d4f98a2SYan Zheng if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { 3595d4f98a2SYan Zheng if (root->root_key.objectid == 3605d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 3615d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 1); 3625d4f98a2SYan Zheng else 3635d4f98a2SYan Zheng ret = btrfs_inc_ref(trans, root, cow, 0); 3645d4f98a2SYan Zheng BUG_ON(ret); 3655d4f98a2SYan Zheng ret = btrfs_dec_ref(trans, root, buf, 1); 3665d4f98a2SYan Zheng BUG_ON(ret); 3675d4f98a2SYan Zheng } 3685d4f98a2SYan Zheng clean_tree_block(trans, root, buf); 3695d4f98a2SYan Zheng } 3705d4f98a2SYan Zheng return 0; 3715d4f98a2SYan Zheng } 3725d4f98a2SYan Zheng 3735d4f98a2SYan Zheng /* 374d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 375d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 376d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 377d397712bSChris Mason * dirty again. 378d352ac68SChris Mason * 379d352ac68SChris Mason * search_start -- an allocation hint for the new block 380d352ac68SChris Mason * 381d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 382d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 383d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 384d352ac68SChris Mason */ 385d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 3865f39d397SChris Mason struct btrfs_root *root, 3875f39d397SChris Mason struct extent_buffer *buf, 3885f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 3895f39d397SChris Mason struct extent_buffer **cow_ret, 3909fa8cfe7SChris Mason u64 search_start, u64 empty_size) 3916702ed49SChris Mason { 3925d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 3935f39d397SChris Mason struct extent_buffer *cow; 3947bb86316SChris Mason int level; 395925baeddSChris Mason int unlock_orig = 0; 3965d4f98a2SYan Zheng u64 parent_start; 3976702ed49SChris Mason 398925baeddSChris Mason if (*cow_ret == buf) 399925baeddSChris Mason unlock_orig = 1; 400925baeddSChris Mason 401b9447ef8SChris Mason btrfs_assert_tree_locked(buf); 402925baeddSChris Mason 4037bb86316SChris Mason WARN_ON(root->ref_cows && trans->transid != 4047bb86316SChris Mason root->fs_info->running_transaction->transid); 4056702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 4065f39d397SChris Mason 4077bb86316SChris Mason level = btrfs_header_level(buf); 40831840ae1SZheng Yan 4095d4f98a2SYan Zheng if (level == 0) 4105d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 4115d4f98a2SYan Zheng else 4125d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 4135d4f98a2SYan Zheng 4145d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) { 4155d4f98a2SYan Zheng if (parent) 4165d4f98a2SYan Zheng parent_start = parent->start; 4175d4f98a2SYan Zheng else 4185d4f98a2SYan Zheng parent_start = 0; 4195d4f98a2SYan Zheng } else 4205d4f98a2SYan Zheng parent_start = 0; 4215d4f98a2SYan Zheng 4225d4f98a2SYan Zheng cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start, 4235d4f98a2SYan Zheng root->root_key.objectid, &disk_key, 4245d4f98a2SYan Zheng level, search_start, empty_size); 4256702ed49SChris Mason if (IS_ERR(cow)) 4266702ed49SChris Mason return PTR_ERR(cow); 4276702ed49SChris Mason 428b4ce94deSChris Mason /* cow is set to blocking by btrfs_init_new_buffer */ 429b4ce94deSChris Mason 4305f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 431db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 4325f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 4335d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 4345d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 4355d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 4365d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 4375d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 4385d4f98a2SYan Zheng else 4395f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 4406702ed49SChris Mason 4412b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 4422b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 4432b82032cSYan Zheng BTRFS_FSID_SIZE); 4442b82032cSYan Zheng 4455d4f98a2SYan Zheng update_ref_for_cow(trans, root, buf, cow); 4461a40e23bSZheng Yan 4476702ed49SChris Mason if (buf == root->node) { 448925baeddSChris Mason WARN_ON(parent && parent != buf); 4495d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 4505d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 4515d4f98a2SYan Zheng parent_start = buf->start; 4525d4f98a2SYan Zheng else 4535d4f98a2SYan Zheng parent_start = 0; 454925baeddSChris Mason 455925baeddSChris Mason spin_lock(&root->node_lock); 4566702ed49SChris Mason root->node = cow; 4575f39d397SChris Mason extent_buffer_get(cow); 458925baeddSChris Mason spin_unlock(&root->node_lock); 459925baeddSChris Mason 46086b9f2ecSYan, Zheng btrfs_free_tree_block(trans, root, buf->start, buf->len, 46186b9f2ecSYan, Zheng parent_start, root->root_key.objectid, level); 4625f39d397SChris Mason free_extent_buffer(buf); 4630b86a832SChris Mason add_root_to_dirty_list(root); 4646702ed49SChris Mason } else { 4655d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 4665d4f98a2SYan Zheng parent_start = parent->start; 4675d4f98a2SYan Zheng else 4685d4f98a2SYan Zheng parent_start = 0; 4695d4f98a2SYan Zheng 4705d4f98a2SYan Zheng WARN_ON(trans->transid != btrfs_header_generation(parent)); 4715f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 472db94535dSChris Mason cow->start); 47374493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 47474493f7aSChris Mason trans->transid); 4756702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 47686b9f2ecSYan, Zheng btrfs_free_tree_block(trans, root, buf->start, buf->len, 47786b9f2ecSYan, Zheng parent_start, root->root_key.objectid, level); 4786702ed49SChris Mason } 479925baeddSChris Mason if (unlock_orig) 480925baeddSChris Mason btrfs_tree_unlock(buf); 4815f39d397SChris Mason free_extent_buffer(buf); 4826702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 4836702ed49SChris Mason *cow_ret = cow; 4846702ed49SChris Mason return 0; 4856702ed49SChris Mason } 4866702ed49SChris Mason 4875d4f98a2SYan Zheng static inline int should_cow_block(struct btrfs_trans_handle *trans, 4885d4f98a2SYan Zheng struct btrfs_root *root, 4895d4f98a2SYan Zheng struct extent_buffer *buf) 4905d4f98a2SYan Zheng { 4915d4f98a2SYan Zheng if (btrfs_header_generation(buf) == trans->transid && 4925d4f98a2SYan Zheng !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) && 4935d4f98a2SYan Zheng !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID && 4945d4f98a2SYan Zheng btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 4955d4f98a2SYan Zheng return 0; 4965d4f98a2SYan Zheng return 1; 4975d4f98a2SYan Zheng } 4985d4f98a2SYan Zheng 499d352ac68SChris Mason /* 500d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 501d352ac68SChris Mason * This version of it has extra checks so that a block isn't cow'd more than 502d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 503d352ac68SChris Mason */ 504d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 5055f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 5065f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 5079fa8cfe7SChris Mason struct extent_buffer **cow_ret) 50802217ed2SChris Mason { 5096702ed49SChris Mason u64 search_start; 510f510cfecSChris Mason int ret; 511dc17ff8fSChris Mason 512ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 513d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 514d397712bSChris Mason (unsigned long long)trans->transid, 515d397712bSChris Mason (unsigned long long) 516ccd467d6SChris Mason root->fs_info->running_transaction->transid); 517ccd467d6SChris Mason WARN_ON(1); 518ccd467d6SChris Mason } 519ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 520d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 521d397712bSChris Mason (unsigned long long)trans->transid, 522d397712bSChris Mason (unsigned long long)root->fs_info->generation); 523ccd467d6SChris Mason WARN_ON(1); 524ccd467d6SChris Mason } 525dc17ff8fSChris Mason 5265d4f98a2SYan Zheng if (!should_cow_block(trans, root, buf)) { 52702217ed2SChris Mason *cow_ret = buf; 52802217ed2SChris Mason return 0; 52902217ed2SChris Mason } 530c487685dSChris Mason 5310b86a832SChris Mason search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); 532b4ce94deSChris Mason 533b4ce94deSChris Mason if (parent) 534b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 535b4ce94deSChris Mason btrfs_set_lock_blocking(buf); 536b4ce94deSChris Mason 537f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 5389fa8cfe7SChris Mason parent_slot, cow_ret, search_start, 0); 539f510cfecSChris Mason return ret; 5402c90e5d6SChris Mason } 5416702ed49SChris Mason 542d352ac68SChris Mason /* 543d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 544d352ac68SChris Mason * node are actually close by 545d352ac68SChris Mason */ 5466b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 5476702ed49SChris Mason { 5486b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 5496702ed49SChris Mason return 1; 5506b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 5516702ed49SChris Mason return 1; 55202217ed2SChris Mason return 0; 55302217ed2SChris Mason } 55402217ed2SChris Mason 555081e9573SChris Mason /* 556081e9573SChris Mason * compare two keys in a memcmp fashion 557081e9573SChris Mason */ 558081e9573SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 559081e9573SChris Mason { 560081e9573SChris Mason struct btrfs_key k1; 561081e9573SChris Mason 562081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 563081e9573SChris Mason 56420736abaSDiego Calleja return btrfs_comp_cpu_keys(&k1, k2); 565081e9573SChris Mason } 566081e9573SChris Mason 567f3465ca4SJosef Bacik /* 568f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 569f3465ca4SJosef Bacik */ 5705d4f98a2SYan Zheng int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2) 571f3465ca4SJosef Bacik { 572f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 573f3465ca4SJosef Bacik return 1; 574f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 575f3465ca4SJosef Bacik return -1; 576f3465ca4SJosef Bacik if (k1->type > k2->type) 577f3465ca4SJosef Bacik return 1; 578f3465ca4SJosef Bacik if (k1->type < k2->type) 579f3465ca4SJosef Bacik return -1; 580f3465ca4SJosef Bacik if (k1->offset > k2->offset) 581f3465ca4SJosef Bacik return 1; 582f3465ca4SJosef Bacik if (k1->offset < k2->offset) 583f3465ca4SJosef Bacik return -1; 584f3465ca4SJosef Bacik return 0; 585f3465ca4SJosef Bacik } 586081e9573SChris Mason 587d352ac68SChris Mason /* 588d352ac68SChris Mason * this is used by the defrag code to go through all the 589d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 590d352ac68SChris Mason * disk order is close to key order 591d352ac68SChris Mason */ 5926702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 5935f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 594a6b6e75eSChris Mason int start_slot, int cache_only, u64 *last_ret, 595a6b6e75eSChris Mason struct btrfs_key *progress) 5966702ed49SChris Mason { 5976b80053dSChris Mason struct extent_buffer *cur; 5986702ed49SChris Mason u64 blocknr; 599ca7a79adSChris Mason u64 gen; 600e9d0b13bSChris Mason u64 search_start = *last_ret; 601e9d0b13bSChris Mason u64 last_block = 0; 6026702ed49SChris Mason u64 other; 6036702ed49SChris Mason u32 parent_nritems; 6046702ed49SChris Mason int end_slot; 6056702ed49SChris Mason int i; 6066702ed49SChris Mason int err = 0; 607f2183bdeSChris Mason int parent_level; 6086b80053dSChris Mason int uptodate; 6096b80053dSChris Mason u32 blocksize; 610081e9573SChris Mason int progress_passed = 0; 611081e9573SChris Mason struct btrfs_disk_key disk_key; 6126702ed49SChris Mason 6135708b959SChris Mason parent_level = btrfs_header_level(parent); 6145708b959SChris Mason if (cache_only && parent_level != 1) 6155708b959SChris Mason return 0; 6165708b959SChris Mason 617d397712bSChris Mason if (trans->transaction != root->fs_info->running_transaction) 6186702ed49SChris Mason WARN_ON(1); 619d397712bSChris Mason if (trans->transid != root->fs_info->generation) 6206702ed49SChris Mason WARN_ON(1); 62186479a04SChris Mason 6226b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 6236b80053dSChris Mason blocksize = btrfs_level_size(root, parent_level - 1); 6246702ed49SChris Mason end_slot = parent_nritems; 6256702ed49SChris Mason 6266702ed49SChris Mason if (parent_nritems == 1) 6276702ed49SChris Mason return 0; 6286702ed49SChris Mason 629b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 630b4ce94deSChris Mason 6316702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 6326702ed49SChris Mason int close = 1; 633a6b6e75eSChris Mason 6345708b959SChris Mason if (!parent->map_token) { 6355708b959SChris Mason map_extent_buffer(parent, 6365708b959SChris Mason btrfs_node_key_ptr_offset(i), 6375708b959SChris Mason sizeof(struct btrfs_key_ptr), 6385708b959SChris Mason &parent->map_token, &parent->kaddr, 6395708b959SChris Mason &parent->map_start, &parent->map_len, 6405708b959SChris Mason KM_USER1); 6415708b959SChris Mason } 642081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 643081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 644081e9573SChris Mason continue; 645081e9573SChris Mason 646081e9573SChris Mason progress_passed = 1; 6476b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 648ca7a79adSChris Mason gen = btrfs_node_ptr_generation(parent, i); 649e9d0b13bSChris Mason if (last_block == 0) 650e9d0b13bSChris Mason last_block = blocknr; 6515708b959SChris Mason 6526702ed49SChris Mason if (i > 0) { 6536b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 6546b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 6556702ed49SChris Mason } 6560ef3e66bSChris Mason if (!close && i < end_slot - 2) { 6576b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 6586b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 6596702ed49SChris Mason } 660e9d0b13bSChris Mason if (close) { 661e9d0b13bSChris Mason last_block = blocknr; 6626702ed49SChris Mason continue; 663e9d0b13bSChris Mason } 6645708b959SChris Mason if (parent->map_token) { 6655708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 6665708b959SChris Mason KM_USER1); 6675708b959SChris Mason parent->map_token = NULL; 6685708b959SChris Mason } 6696702ed49SChris Mason 6706b80053dSChris Mason cur = btrfs_find_tree_block(root, blocknr, blocksize); 6716b80053dSChris Mason if (cur) 6721259ab75SChris Mason uptodate = btrfs_buffer_uptodate(cur, gen); 6736b80053dSChris Mason else 6746b80053dSChris Mason uptodate = 0; 6755708b959SChris Mason if (!cur || !uptodate) { 6766702ed49SChris Mason if (cache_only) { 6776b80053dSChris Mason free_extent_buffer(cur); 6786702ed49SChris Mason continue; 6796702ed49SChris Mason } 6806b80053dSChris Mason if (!cur) { 6816b80053dSChris Mason cur = read_tree_block(root, blocknr, 682ca7a79adSChris Mason blocksize, gen); 6836b80053dSChris Mason } else if (!uptodate) { 684ca7a79adSChris Mason btrfs_read_buffer(cur, gen); 6856702ed49SChris Mason } 686f2183bdeSChris Mason } 687e9d0b13bSChris Mason if (search_start == 0) 6886b80053dSChris Mason search_start = last_block; 689e9d0b13bSChris Mason 690e7a84565SChris Mason btrfs_tree_lock(cur); 691b4ce94deSChris Mason btrfs_set_lock_blocking(cur); 6926b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 693e7a84565SChris Mason &cur, search_start, 6946b80053dSChris Mason min(16 * blocksize, 6959fa8cfe7SChris Mason (end_slot - i) * blocksize)); 696252c38f0SYan if (err) { 697e7a84565SChris Mason btrfs_tree_unlock(cur); 6986b80053dSChris Mason free_extent_buffer(cur); 6996702ed49SChris Mason break; 700252c38f0SYan } 701e7a84565SChris Mason search_start = cur->start; 702e7a84565SChris Mason last_block = cur->start; 703f2183bdeSChris Mason *last_ret = search_start; 704e7a84565SChris Mason btrfs_tree_unlock(cur); 705e7a84565SChris Mason free_extent_buffer(cur); 7066702ed49SChris Mason } 7075708b959SChris Mason if (parent->map_token) { 7085708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 7095708b959SChris Mason KM_USER1); 7105708b959SChris Mason parent->map_token = NULL; 7115708b959SChris Mason } 7126702ed49SChris Mason return err; 7136702ed49SChris Mason } 7146702ed49SChris Mason 71574123bd7SChris Mason /* 71674123bd7SChris Mason * The leaf data grows from end-to-front in the node. 71774123bd7SChris Mason * this returns the address of the start of the last item, 71874123bd7SChris Mason * which is the stop of the leaf data stack 71974123bd7SChris Mason */ 720123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 7215f39d397SChris Mason struct extent_buffer *leaf) 722be0e5c09SChris Mason { 7235f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 724be0e5c09SChris Mason if (nr == 0) 725123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 7265f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 727be0e5c09SChris Mason } 728be0e5c09SChris Mason 729d352ac68SChris Mason /* 730d352ac68SChris Mason * extra debugging checks to make sure all the items in a key are 731d352ac68SChris Mason * well formed and in the proper order 732d352ac68SChris Mason */ 733123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 734123abc88SChris Mason int level) 735aa5d6bedSChris Mason { 7365f39d397SChris Mason struct extent_buffer *parent = NULL; 7375f39d397SChris Mason struct extent_buffer *node = path->nodes[level]; 7385f39d397SChris Mason struct btrfs_disk_key parent_key; 7395f39d397SChris Mason struct btrfs_disk_key node_key; 740aa5d6bedSChris Mason int parent_slot; 7418d7be552SChris Mason int slot; 7428d7be552SChris Mason struct btrfs_key cpukey; 7435f39d397SChris Mason u32 nritems = btrfs_header_nritems(node); 744aa5d6bedSChris Mason 745aa5d6bedSChris Mason if (path->nodes[level + 1]) 7465f39d397SChris Mason parent = path->nodes[level + 1]; 747a1f39630SAneesh 7488d7be552SChris Mason slot = path->slots[level]; 7497518a238SChris Mason BUG_ON(nritems == 0); 7507518a238SChris Mason if (parent) { 751a1f39630SAneesh parent_slot = path->slots[level + 1]; 7525f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 7535f39d397SChris Mason btrfs_node_key(node, &node_key, 0); 7545f39d397SChris Mason BUG_ON(memcmp(&parent_key, &node_key, 755e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 7561d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 757db94535dSChris Mason btrfs_header_bytenr(node)); 758aa5d6bedSChris Mason } 759123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 7608d7be552SChris Mason if (slot != 0) { 7615f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot - 1); 7625f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 7635f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) <= 0); 7648d7be552SChris Mason } 7658d7be552SChris Mason if (slot < nritems - 1) { 7665f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot + 1); 7675f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 7685f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) >= 0); 769aa5d6bedSChris Mason } 770aa5d6bedSChris Mason return 0; 771aa5d6bedSChris Mason } 772aa5d6bedSChris Mason 773d352ac68SChris Mason /* 774d352ac68SChris Mason * extra checking to make sure all the items in a leaf are 775d352ac68SChris Mason * well formed and in the proper order 776d352ac68SChris Mason */ 777123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 778123abc88SChris Mason int level) 779aa5d6bedSChris Mason { 7805f39d397SChris Mason struct extent_buffer *leaf = path->nodes[level]; 7815f39d397SChris Mason struct extent_buffer *parent = NULL; 782aa5d6bedSChris Mason int parent_slot; 7838d7be552SChris Mason struct btrfs_key cpukey; 7845f39d397SChris Mason struct btrfs_disk_key parent_key; 7855f39d397SChris Mason struct btrfs_disk_key leaf_key; 7865f39d397SChris Mason int slot = path->slots[0]; 7878d7be552SChris Mason 7885f39d397SChris Mason u32 nritems = btrfs_header_nritems(leaf); 789aa5d6bedSChris Mason 790aa5d6bedSChris Mason if (path->nodes[level + 1]) 7915f39d397SChris Mason parent = path->nodes[level + 1]; 7927518a238SChris Mason 7937518a238SChris Mason if (nritems == 0) 7947518a238SChris Mason return 0; 7957518a238SChris Mason 7967518a238SChris Mason if (parent) { 797a1f39630SAneesh parent_slot = path->slots[level + 1]; 7985f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 7995f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, 0); 8006702ed49SChris Mason 8015f39d397SChris Mason BUG_ON(memcmp(&parent_key, &leaf_key, 802e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 8031d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 804db94535dSChris Mason btrfs_header_bytenr(leaf)); 805aa5d6bedSChris Mason } 8065f39d397SChris Mason if (slot != 0 && slot < nritems - 1) { 8075f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 8085f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1); 8095f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) <= 0) { 8105f39d397SChris Mason btrfs_print_leaf(root, leaf); 811d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad key\n", slot); 8125f39d397SChris Mason BUG_ON(1); 8135f39d397SChris Mason } 8145f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot - 1) != 8155f39d397SChris Mason btrfs_item_end_nr(leaf, slot)) { 8165f39d397SChris Mason btrfs_print_leaf(root, leaf); 817d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad\n", slot); 8185f39d397SChris Mason BUG_ON(1); 8195f39d397SChris Mason } 820aa5d6bedSChris Mason } 8218d7be552SChris Mason if (slot < nritems - 1) { 8225f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 8235f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1); 8245f39d397SChris Mason BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0); 8255f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot) != 8265f39d397SChris Mason btrfs_item_end_nr(leaf, slot + 1)) { 8275f39d397SChris Mason btrfs_print_leaf(root, leaf); 828d397712bSChris Mason printk(KERN_CRIT "slot %d offset bad\n", slot); 8295f39d397SChris Mason BUG_ON(1); 830aa5d6bedSChris Mason } 8315f39d397SChris Mason } 8325f39d397SChris Mason BUG_ON(btrfs_item_offset_nr(leaf, 0) + 8335f39d397SChris Mason btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root)); 834aa5d6bedSChris Mason return 0; 835aa5d6bedSChris Mason } 836aa5d6bedSChris Mason 837d397712bSChris Mason static noinline int check_block(struct btrfs_root *root, 83898ed5174SChris Mason struct btrfs_path *path, int level) 839aa5d6bedSChris Mason { 84085d824c4SChris Mason return 0; 841aa5d6bedSChris Mason if (level == 0) 842123abc88SChris Mason return check_leaf(root, path, level); 843123abc88SChris Mason return check_node(root, path, level); 844aa5d6bedSChris Mason } 845aa5d6bedSChris Mason 84674123bd7SChris Mason /* 8475f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 8485f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 8495f39d397SChris Mason * 85074123bd7SChris Mason * the slot in the array is returned via slot, and it points to 85174123bd7SChris Mason * the place where you would insert key if it is not found in 85274123bd7SChris Mason * the array. 85374123bd7SChris Mason * 85474123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 85574123bd7SChris Mason */ 856e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 857e02119d5SChris Mason unsigned long p, 8585f39d397SChris Mason int item_size, struct btrfs_key *key, 859be0e5c09SChris Mason int max, int *slot) 860be0e5c09SChris Mason { 861be0e5c09SChris Mason int low = 0; 862be0e5c09SChris Mason int high = max; 863be0e5c09SChris Mason int mid; 864be0e5c09SChris Mason int ret; 865479965d6SChris Mason struct btrfs_disk_key *tmp = NULL; 8665f39d397SChris Mason struct btrfs_disk_key unaligned; 8675f39d397SChris Mason unsigned long offset; 8685f39d397SChris Mason char *map_token = NULL; 8695f39d397SChris Mason char *kaddr = NULL; 8705f39d397SChris Mason unsigned long map_start = 0; 8715f39d397SChris Mason unsigned long map_len = 0; 872479965d6SChris Mason int err; 873be0e5c09SChris Mason 874be0e5c09SChris Mason while (low < high) { 875be0e5c09SChris Mason mid = (low + high) / 2; 8765f39d397SChris Mason offset = p + mid * item_size; 8775f39d397SChris Mason 8785f39d397SChris Mason if (!map_token || offset < map_start || 8795f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 8805f39d397SChris Mason map_start + map_len) { 881479965d6SChris Mason if (map_token) { 8825f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 883479965d6SChris Mason map_token = NULL; 884479965d6SChris Mason } 885934d375bSChris Mason 886934d375bSChris Mason err = map_private_extent_buffer(eb, offset, 887479965d6SChris Mason sizeof(struct btrfs_disk_key), 888479965d6SChris Mason &map_token, &kaddr, 8895f39d397SChris Mason &map_start, &map_len, KM_USER0); 8905f39d397SChris Mason 891479965d6SChris Mason if (!err) { 892479965d6SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 893479965d6SChris Mason map_start); 894479965d6SChris Mason } else { 8955f39d397SChris Mason read_extent_buffer(eb, &unaligned, 8965f39d397SChris Mason offset, sizeof(unaligned)); 8975f39d397SChris Mason tmp = &unaligned; 898479965d6SChris Mason } 899479965d6SChris Mason 9005f39d397SChris Mason } else { 9015f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 9025f39d397SChris Mason map_start); 9035f39d397SChris Mason } 904be0e5c09SChris Mason ret = comp_keys(tmp, key); 905be0e5c09SChris Mason 906be0e5c09SChris Mason if (ret < 0) 907be0e5c09SChris Mason low = mid + 1; 908be0e5c09SChris Mason else if (ret > 0) 909be0e5c09SChris Mason high = mid; 910be0e5c09SChris Mason else { 911be0e5c09SChris Mason *slot = mid; 912479965d6SChris Mason if (map_token) 9135f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 914be0e5c09SChris Mason return 0; 915be0e5c09SChris Mason } 916be0e5c09SChris Mason } 917be0e5c09SChris Mason *slot = low; 9185f39d397SChris Mason if (map_token) 9195f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 920be0e5c09SChris Mason return 1; 921be0e5c09SChris Mason } 922be0e5c09SChris Mason 92397571fd0SChris Mason /* 92497571fd0SChris Mason * simple bin_search frontend that does the right thing for 92597571fd0SChris Mason * leaves vs nodes 92697571fd0SChris Mason */ 9275f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 9285f39d397SChris Mason int level, int *slot) 929be0e5c09SChris Mason { 9305f39d397SChris Mason if (level == 0) { 9315f39d397SChris Mason return generic_bin_search(eb, 9325f39d397SChris Mason offsetof(struct btrfs_leaf, items), 9330783fcfcSChris Mason sizeof(struct btrfs_item), 9345f39d397SChris Mason key, btrfs_header_nritems(eb), 9357518a238SChris Mason slot); 936be0e5c09SChris Mason } else { 9375f39d397SChris Mason return generic_bin_search(eb, 9385f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 939123abc88SChris Mason sizeof(struct btrfs_key_ptr), 9405f39d397SChris Mason key, btrfs_header_nritems(eb), 9417518a238SChris Mason slot); 942be0e5c09SChris Mason } 943be0e5c09SChris Mason return -1; 944be0e5c09SChris Mason } 945be0e5c09SChris Mason 9465d4f98a2SYan Zheng int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key, 9475d4f98a2SYan Zheng int level, int *slot) 9485d4f98a2SYan Zheng { 9495d4f98a2SYan Zheng return bin_search(eb, key, level, slot); 9505d4f98a2SYan Zheng } 9515d4f98a2SYan Zheng 952d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 953d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 954d352ac68SChris Mason * NULL is returned on error. 955d352ac68SChris Mason */ 956e02119d5SChris Mason static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root, 9575f39d397SChris Mason struct extent_buffer *parent, int slot) 958bb803951SChris Mason { 959ca7a79adSChris Mason int level = btrfs_header_level(parent); 960bb803951SChris Mason if (slot < 0) 961bb803951SChris Mason return NULL; 9625f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 963bb803951SChris Mason return NULL; 964ca7a79adSChris Mason 965ca7a79adSChris Mason BUG_ON(level == 0); 966ca7a79adSChris Mason 967db94535dSChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot), 968ca7a79adSChris Mason btrfs_level_size(root, level - 1), 969ca7a79adSChris Mason btrfs_node_ptr_generation(parent, slot)); 970bb803951SChris Mason } 971bb803951SChris Mason 972d352ac68SChris Mason /* 973d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 974d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 975d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 976d352ac68SChris Mason */ 977e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 97898ed5174SChris Mason struct btrfs_root *root, 97998ed5174SChris Mason struct btrfs_path *path, int level) 980bb803951SChris Mason { 9815f39d397SChris Mason struct extent_buffer *right = NULL; 9825f39d397SChris Mason struct extent_buffer *mid; 9835f39d397SChris Mason struct extent_buffer *left = NULL; 9845f39d397SChris Mason struct extent_buffer *parent = NULL; 985bb803951SChris Mason int ret = 0; 986bb803951SChris Mason int wret; 987bb803951SChris Mason int pslot; 988bb803951SChris Mason int orig_slot = path->slots[level]; 98954aa1f4dSChris Mason int err_on_enospc = 0; 99079f95c82SChris Mason u64 orig_ptr; 991bb803951SChris Mason 992bb803951SChris Mason if (level == 0) 993bb803951SChris Mason return 0; 994bb803951SChris Mason 9955f39d397SChris Mason mid = path->nodes[level]; 996b4ce94deSChris Mason 997925baeddSChris Mason WARN_ON(!path->locks[level]); 9987bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 9997bb86316SChris Mason 10001d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 100179f95c82SChris Mason 1002234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 10035f39d397SChris Mason parent = path->nodes[level + 1]; 1004bb803951SChris Mason pslot = path->slots[level + 1]; 1005bb803951SChris Mason 100640689478SChris Mason /* 100740689478SChris Mason * deal with the case where there is only one pointer in the root 100840689478SChris Mason * by promoting the node below to a root 100940689478SChris Mason */ 10105f39d397SChris Mason if (!parent) { 10115f39d397SChris Mason struct extent_buffer *child; 1012bb803951SChris Mason 10135f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 1014bb803951SChris Mason return 0; 1015bb803951SChris Mason 1016bb803951SChris Mason /* promote the child to a root */ 10175f39d397SChris Mason child = read_node_slot(root, mid, 0); 10187951f3ceSJeff Mahoney BUG_ON(!child); 1019925baeddSChris Mason btrfs_tree_lock(child); 1020b4ce94deSChris Mason btrfs_set_lock_blocking(child); 10219fa8cfe7SChris Mason ret = btrfs_cow_block(trans, root, child, mid, 0, &child); 10222f375ab9SYan BUG_ON(ret); 10232f375ab9SYan 1024925baeddSChris Mason spin_lock(&root->node_lock); 1025bb803951SChris Mason root->node = child; 1026925baeddSChris Mason spin_unlock(&root->node_lock); 1027925baeddSChris Mason 10280b86a832SChris Mason add_root_to_dirty_list(root); 1029925baeddSChris Mason btrfs_tree_unlock(child); 1030b4ce94deSChris Mason 1031925baeddSChris Mason path->locks[level] = 0; 1032bb803951SChris Mason path->nodes[level] = NULL; 10335f39d397SChris Mason clean_tree_block(trans, root, mid); 1034925baeddSChris Mason btrfs_tree_unlock(mid); 1035bb803951SChris Mason /* once for the path */ 10365f39d397SChris Mason free_extent_buffer(mid); 103786b9f2ecSYan, Zheng ret = btrfs_free_tree_block(trans, root, mid->start, mid->len, 103886b9f2ecSYan, Zheng 0, root->root_key.objectid, level); 1039bb803951SChris Mason /* once for the root ptr */ 10405f39d397SChris Mason free_extent_buffer(mid); 1041db94535dSChris Mason return ret; 1042bb803951SChris Mason } 10435f39d397SChris Mason if (btrfs_header_nritems(mid) > 1044123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 1045bb803951SChris Mason return 0; 1046bb803951SChris Mason 10475f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 104854aa1f4dSChris Mason err_on_enospc = 1; 104954aa1f4dSChris Mason 10505f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 10515f39d397SChris Mason if (left) { 1052925baeddSChris Mason btrfs_tree_lock(left); 1053b4ce94deSChris Mason btrfs_set_lock_blocking(left); 10545f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 10559fa8cfe7SChris Mason parent, pslot - 1, &left); 105654aa1f4dSChris Mason if (wret) { 105754aa1f4dSChris Mason ret = wret; 105854aa1f4dSChris Mason goto enospc; 105954aa1f4dSChris Mason } 10602cc58cf2SChris Mason } 10615f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 10625f39d397SChris Mason if (right) { 1063925baeddSChris Mason btrfs_tree_lock(right); 1064b4ce94deSChris Mason btrfs_set_lock_blocking(right); 10655f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 10669fa8cfe7SChris Mason parent, pslot + 1, &right); 10672cc58cf2SChris Mason if (wret) { 10682cc58cf2SChris Mason ret = wret; 10692cc58cf2SChris Mason goto enospc; 10702cc58cf2SChris Mason } 10712cc58cf2SChris Mason } 10722cc58cf2SChris Mason 10732cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 10745f39d397SChris Mason if (left) { 10755f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 1076bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 107779f95c82SChris Mason if (wret < 0) 107879f95c82SChris Mason ret = wret; 10795f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 108054aa1f4dSChris Mason err_on_enospc = 1; 1081bb803951SChris Mason } 108279f95c82SChris Mason 108379f95c82SChris Mason /* 108479f95c82SChris Mason * then try to empty the right most buffer into the middle 108579f95c82SChris Mason */ 10865f39d397SChris Mason if (right) { 1087971a1f66SChris Mason wret = push_node_left(trans, root, mid, right, 1); 108854aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 108979f95c82SChris Mason ret = wret; 10905f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 1091db94535dSChris Mason u64 bytenr = right->start; 1092db94535dSChris Mason u32 blocksize = right->len; 1093db94535dSChris Mason 10945f39d397SChris Mason clean_tree_block(trans, root, right); 1095925baeddSChris Mason btrfs_tree_unlock(right); 10965f39d397SChris Mason free_extent_buffer(right); 1097bb803951SChris Mason right = NULL; 1098e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 1099e089f05cSChris Mason 1); 1100bb803951SChris Mason if (wret) 1101bb803951SChris Mason ret = wret; 110286b9f2ecSYan, Zheng wret = btrfs_free_tree_block(trans, root, 110386b9f2ecSYan, Zheng bytenr, blocksize, 0, 11045d4f98a2SYan Zheng root->root_key.objectid, 110586b9f2ecSYan, Zheng level); 1106bb803951SChris Mason if (wret) 1107bb803951SChris Mason ret = wret; 1108bb803951SChris Mason } else { 11095f39d397SChris Mason struct btrfs_disk_key right_key; 11105f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 11115f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 11125f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 1113bb803951SChris Mason } 1114bb803951SChris Mason } 11155f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 111679f95c82SChris Mason /* 111779f95c82SChris Mason * we're not allowed to leave a node with one item in the 111879f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 111979f95c82SChris Mason * could try to delete the only pointer in this node. 112079f95c82SChris Mason * So, pull some keys from the left. 112179f95c82SChris Mason * There has to be a left pointer at this point because 112279f95c82SChris Mason * otherwise we would have pulled some pointers from the 112379f95c82SChris Mason * right 112479f95c82SChris Mason */ 11255f39d397SChris Mason BUG_ON(!left); 11265f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 112754aa1f4dSChris Mason if (wret < 0) { 112879f95c82SChris Mason ret = wret; 112954aa1f4dSChris Mason goto enospc; 113054aa1f4dSChris Mason } 1131bce4eae9SChris Mason if (wret == 1) { 1132bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 1133bce4eae9SChris Mason if (wret < 0) 1134bce4eae9SChris Mason ret = wret; 1135bce4eae9SChris Mason } 113679f95c82SChris Mason BUG_ON(wret == 1); 113779f95c82SChris Mason } 11385f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 113979f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 1140db94535dSChris Mason u64 bytenr = mid->start; 1141db94535dSChris Mason u32 blocksize = mid->len; 1142925baeddSChris Mason 11435f39d397SChris Mason clean_tree_block(trans, root, mid); 1144925baeddSChris Mason btrfs_tree_unlock(mid); 11455f39d397SChris Mason free_extent_buffer(mid); 1146bb803951SChris Mason mid = NULL; 1147e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 1148bb803951SChris Mason if (wret) 1149bb803951SChris Mason ret = wret; 115086b9f2ecSYan, Zheng wret = btrfs_free_tree_block(trans, root, bytenr, blocksize, 115186b9f2ecSYan, Zheng 0, root->root_key.objectid, level); 1152bb803951SChris Mason if (wret) 1153bb803951SChris Mason ret = wret; 115479f95c82SChris Mason } else { 115579f95c82SChris Mason /* update the parent key to reflect our changes */ 11565f39d397SChris Mason struct btrfs_disk_key mid_key; 11575f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 11585f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 11595f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 116079f95c82SChris Mason } 1161bb803951SChris Mason 116279f95c82SChris Mason /* update the path */ 11635f39d397SChris Mason if (left) { 11645f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 11655f39d397SChris Mason extent_buffer_get(left); 1166925baeddSChris Mason /* left was locked after cow */ 11675f39d397SChris Mason path->nodes[level] = left; 1168bb803951SChris Mason path->slots[level + 1] -= 1; 1169bb803951SChris Mason path->slots[level] = orig_slot; 1170925baeddSChris Mason if (mid) { 1171925baeddSChris Mason btrfs_tree_unlock(mid); 11725f39d397SChris Mason free_extent_buffer(mid); 1173925baeddSChris Mason } 1174bb803951SChris Mason } else { 11755f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1176bb803951SChris Mason path->slots[level] = orig_slot; 1177bb803951SChris Mason } 1178bb803951SChris Mason } 117979f95c82SChris Mason /* double check we haven't messed things up */ 1180123abc88SChris Mason check_block(root, path, level); 1181e20d96d6SChris Mason if (orig_ptr != 11825f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 118379f95c82SChris Mason BUG(); 118454aa1f4dSChris Mason enospc: 1185925baeddSChris Mason if (right) { 1186925baeddSChris Mason btrfs_tree_unlock(right); 11875f39d397SChris Mason free_extent_buffer(right); 1188925baeddSChris Mason } 1189925baeddSChris Mason if (left) { 1190925baeddSChris Mason if (path->nodes[level] != left) 1191925baeddSChris Mason btrfs_tree_unlock(left); 11925f39d397SChris Mason free_extent_buffer(left); 1193925baeddSChris Mason } 1194bb803951SChris Mason return ret; 1195bb803951SChris Mason } 1196bb803951SChris Mason 1197d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1198d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1199d352ac68SChris Mason * have to be pessimistic. 1200d352ac68SChris Mason */ 1201d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1202e66f709bSChris Mason struct btrfs_root *root, 1203e66f709bSChris Mason struct btrfs_path *path, int level) 1204e66f709bSChris Mason { 12055f39d397SChris Mason struct extent_buffer *right = NULL; 12065f39d397SChris Mason struct extent_buffer *mid; 12075f39d397SChris Mason struct extent_buffer *left = NULL; 12085f39d397SChris Mason struct extent_buffer *parent = NULL; 1209e66f709bSChris Mason int ret = 0; 1210e66f709bSChris Mason int wret; 1211e66f709bSChris Mason int pslot; 1212e66f709bSChris Mason int orig_slot = path->slots[level]; 1213e66f709bSChris Mason u64 orig_ptr; 1214e66f709bSChris Mason 1215e66f709bSChris Mason if (level == 0) 1216e66f709bSChris Mason return 1; 1217e66f709bSChris Mason 12185f39d397SChris Mason mid = path->nodes[level]; 12197bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1220e66f709bSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 1221e66f709bSChris Mason 1222e66f709bSChris Mason if (level < BTRFS_MAX_LEVEL - 1) 12235f39d397SChris Mason parent = path->nodes[level + 1]; 1224e66f709bSChris Mason pslot = path->slots[level + 1]; 1225e66f709bSChris Mason 12265f39d397SChris Mason if (!parent) 1227e66f709bSChris Mason return 1; 1228e66f709bSChris Mason 12295f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 1230e66f709bSChris Mason 1231e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 12325f39d397SChris Mason if (left) { 1233e66f709bSChris Mason u32 left_nr; 1234925baeddSChris Mason 1235925baeddSChris Mason btrfs_tree_lock(left); 1236b4ce94deSChris Mason btrfs_set_lock_blocking(left); 1237b4ce94deSChris Mason 12385f39d397SChris Mason left_nr = btrfs_header_nritems(left); 123933ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 124033ade1f8SChris Mason wret = 1; 124133ade1f8SChris Mason } else { 12425f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 12439fa8cfe7SChris Mason pslot - 1, &left); 124454aa1f4dSChris Mason if (ret) 124554aa1f4dSChris Mason wret = 1; 124654aa1f4dSChris Mason else { 124754aa1f4dSChris Mason wret = push_node_left(trans, root, 1248971a1f66SChris Mason left, mid, 0); 124954aa1f4dSChris Mason } 125033ade1f8SChris Mason } 1251e66f709bSChris Mason if (wret < 0) 1252e66f709bSChris Mason ret = wret; 1253e66f709bSChris Mason if (wret == 0) { 12545f39d397SChris Mason struct btrfs_disk_key disk_key; 1255e66f709bSChris Mason orig_slot += left_nr; 12565f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 12575f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 12585f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 12595f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 12605f39d397SChris Mason path->nodes[level] = left; 1261e66f709bSChris Mason path->slots[level + 1] -= 1; 1262e66f709bSChris Mason path->slots[level] = orig_slot; 1263925baeddSChris Mason btrfs_tree_unlock(mid); 12645f39d397SChris Mason free_extent_buffer(mid); 1265e66f709bSChris Mason } else { 1266e66f709bSChris Mason orig_slot -= 12675f39d397SChris Mason btrfs_header_nritems(left); 1268e66f709bSChris Mason path->slots[level] = orig_slot; 1269925baeddSChris Mason btrfs_tree_unlock(left); 12705f39d397SChris Mason free_extent_buffer(left); 1271e66f709bSChris Mason } 1272e66f709bSChris Mason return 0; 1273e66f709bSChris Mason } 1274925baeddSChris Mason btrfs_tree_unlock(left); 12755f39d397SChris Mason free_extent_buffer(left); 1276e66f709bSChris Mason } 12775f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 1278e66f709bSChris Mason 1279e66f709bSChris Mason /* 1280e66f709bSChris Mason * then try to empty the right most buffer into the middle 1281e66f709bSChris Mason */ 12825f39d397SChris Mason if (right) { 128333ade1f8SChris Mason u32 right_nr; 1284b4ce94deSChris Mason 1285925baeddSChris Mason btrfs_tree_lock(right); 1286b4ce94deSChris Mason btrfs_set_lock_blocking(right); 1287b4ce94deSChris Mason 12885f39d397SChris Mason right_nr = btrfs_header_nritems(right); 128933ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 129033ade1f8SChris Mason wret = 1; 129133ade1f8SChris Mason } else { 12925f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 12935f39d397SChris Mason parent, pslot + 1, 12949fa8cfe7SChris Mason &right); 129554aa1f4dSChris Mason if (ret) 129654aa1f4dSChris Mason wret = 1; 129754aa1f4dSChris Mason else { 129833ade1f8SChris Mason wret = balance_node_right(trans, root, 12995f39d397SChris Mason right, mid); 130033ade1f8SChris Mason } 130154aa1f4dSChris Mason } 1302e66f709bSChris Mason if (wret < 0) 1303e66f709bSChris Mason ret = wret; 1304e66f709bSChris Mason if (wret == 0) { 13055f39d397SChris Mason struct btrfs_disk_key disk_key; 13065f39d397SChris Mason 13075f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 13085f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 13095f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 13105f39d397SChris Mason 13115f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 13125f39d397SChris Mason path->nodes[level] = right; 1313e66f709bSChris Mason path->slots[level + 1] += 1; 1314e66f709bSChris Mason path->slots[level] = orig_slot - 13155f39d397SChris Mason btrfs_header_nritems(mid); 1316925baeddSChris Mason btrfs_tree_unlock(mid); 13175f39d397SChris Mason free_extent_buffer(mid); 1318e66f709bSChris Mason } else { 1319925baeddSChris Mason btrfs_tree_unlock(right); 13205f39d397SChris Mason free_extent_buffer(right); 1321e66f709bSChris Mason } 1322e66f709bSChris Mason return 0; 1323e66f709bSChris Mason } 1324925baeddSChris Mason btrfs_tree_unlock(right); 13255f39d397SChris Mason free_extent_buffer(right); 1326e66f709bSChris Mason } 1327e66f709bSChris Mason return 1; 1328e66f709bSChris Mason } 1329e66f709bSChris Mason 133074123bd7SChris Mason /* 1331d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1332d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 13333c69faecSChris Mason */ 1334c8c42864SChris Mason static void reada_for_search(struct btrfs_root *root, 1335e02119d5SChris Mason struct btrfs_path *path, 133601f46658SChris Mason int level, int slot, u64 objectid) 13373c69faecSChris Mason { 13385f39d397SChris Mason struct extent_buffer *node; 133901f46658SChris Mason struct btrfs_disk_key disk_key; 13403c69faecSChris Mason u32 nritems; 13413c69faecSChris Mason u64 search; 1342a7175319SChris Mason u64 target; 13436b80053dSChris Mason u64 nread = 0; 13443c69faecSChris Mason int direction = path->reada; 13455f39d397SChris Mason struct extent_buffer *eb; 13466b80053dSChris Mason u32 nr; 13476b80053dSChris Mason u32 blocksize; 13486b80053dSChris Mason u32 nscan = 0; 1349db94535dSChris Mason 1350a6b6e75eSChris Mason if (level != 1) 13513c69faecSChris Mason return; 13523c69faecSChris Mason 13536702ed49SChris Mason if (!path->nodes[level]) 13546702ed49SChris Mason return; 13556702ed49SChris Mason 13565f39d397SChris Mason node = path->nodes[level]; 1357925baeddSChris Mason 13583c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 13596b80053dSChris Mason blocksize = btrfs_level_size(root, level - 1); 13606b80053dSChris Mason eb = btrfs_find_tree_block(root, search, blocksize); 13615f39d397SChris Mason if (eb) { 13625f39d397SChris Mason free_extent_buffer(eb); 13633c69faecSChris Mason return; 13643c69faecSChris Mason } 13653c69faecSChris Mason 1366a7175319SChris Mason target = search; 13676b80053dSChris Mason 13685f39d397SChris Mason nritems = btrfs_header_nritems(node); 13696b80053dSChris Mason nr = slot; 13703c69faecSChris Mason while (1) { 13716b80053dSChris Mason if (direction < 0) { 13726b80053dSChris Mason if (nr == 0) 13733c69faecSChris Mason break; 13746b80053dSChris Mason nr--; 13756b80053dSChris Mason } else if (direction > 0) { 13766b80053dSChris Mason nr++; 13776b80053dSChris Mason if (nr >= nritems) 13786b80053dSChris Mason break; 13793c69faecSChris Mason } 138001f46658SChris Mason if (path->reada < 0 && objectid) { 138101f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 138201f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 138301f46658SChris Mason break; 138401f46658SChris Mason } 13856b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1386a7175319SChris Mason if ((search <= target && target - search <= 65536) || 1387a7175319SChris Mason (search > target && search - target <= 65536)) { 1388ca7a79adSChris Mason readahead_tree_block(root, search, blocksize, 1389ca7a79adSChris Mason btrfs_node_ptr_generation(node, nr)); 13906b80053dSChris Mason nread += blocksize; 13913c69faecSChris Mason } 13926b80053dSChris Mason nscan++; 1393a7175319SChris Mason if ((nread > 65536 || nscan > 32)) 13946b80053dSChris Mason break; 13953c69faecSChris Mason } 13963c69faecSChris Mason } 1397925baeddSChris Mason 1398d352ac68SChris Mason /* 1399b4ce94deSChris Mason * returns -EAGAIN if it had to drop the path, or zero if everything was in 1400b4ce94deSChris Mason * cache 1401b4ce94deSChris Mason */ 1402b4ce94deSChris Mason static noinline int reada_for_balance(struct btrfs_root *root, 1403b4ce94deSChris Mason struct btrfs_path *path, int level) 1404b4ce94deSChris Mason { 1405b4ce94deSChris Mason int slot; 1406b4ce94deSChris Mason int nritems; 1407b4ce94deSChris Mason struct extent_buffer *parent; 1408b4ce94deSChris Mason struct extent_buffer *eb; 1409b4ce94deSChris Mason u64 gen; 1410b4ce94deSChris Mason u64 block1 = 0; 1411b4ce94deSChris Mason u64 block2 = 0; 1412b4ce94deSChris Mason int ret = 0; 1413b4ce94deSChris Mason int blocksize; 1414b4ce94deSChris Mason 14158c594ea8SChris Mason parent = path->nodes[level + 1]; 1416b4ce94deSChris Mason if (!parent) 1417b4ce94deSChris Mason return 0; 1418b4ce94deSChris Mason 1419b4ce94deSChris Mason nritems = btrfs_header_nritems(parent); 14208c594ea8SChris Mason slot = path->slots[level + 1]; 1421b4ce94deSChris Mason blocksize = btrfs_level_size(root, level); 1422b4ce94deSChris Mason 1423b4ce94deSChris Mason if (slot > 0) { 1424b4ce94deSChris Mason block1 = btrfs_node_blockptr(parent, slot - 1); 1425b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot - 1); 1426b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block1, blocksize); 1427b4ce94deSChris Mason if (eb && btrfs_buffer_uptodate(eb, gen)) 1428b4ce94deSChris Mason block1 = 0; 1429b4ce94deSChris Mason free_extent_buffer(eb); 1430b4ce94deSChris Mason } 14318c594ea8SChris Mason if (slot + 1 < nritems) { 1432b4ce94deSChris Mason block2 = btrfs_node_blockptr(parent, slot + 1); 1433b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot + 1); 1434b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block2, blocksize); 1435b4ce94deSChris Mason if (eb && btrfs_buffer_uptodate(eb, gen)) 1436b4ce94deSChris Mason block2 = 0; 1437b4ce94deSChris Mason free_extent_buffer(eb); 1438b4ce94deSChris Mason } 1439b4ce94deSChris Mason if (block1 || block2) { 1440b4ce94deSChris Mason ret = -EAGAIN; 14418c594ea8SChris Mason 14428c594ea8SChris Mason /* release the whole path */ 1443b4ce94deSChris Mason btrfs_release_path(root, path); 14448c594ea8SChris Mason 14458c594ea8SChris Mason /* read the blocks */ 1446b4ce94deSChris Mason if (block1) 1447b4ce94deSChris Mason readahead_tree_block(root, block1, blocksize, 0); 1448b4ce94deSChris Mason if (block2) 1449b4ce94deSChris Mason readahead_tree_block(root, block2, blocksize, 0); 1450b4ce94deSChris Mason 1451b4ce94deSChris Mason if (block1) { 1452b4ce94deSChris Mason eb = read_tree_block(root, block1, blocksize, 0); 1453b4ce94deSChris Mason free_extent_buffer(eb); 1454b4ce94deSChris Mason } 14558c594ea8SChris Mason if (block2) { 1456b4ce94deSChris Mason eb = read_tree_block(root, block2, blocksize, 0); 1457b4ce94deSChris Mason free_extent_buffer(eb); 1458b4ce94deSChris Mason } 1459b4ce94deSChris Mason } 1460b4ce94deSChris Mason return ret; 1461b4ce94deSChris Mason } 1462b4ce94deSChris Mason 1463b4ce94deSChris Mason 1464b4ce94deSChris Mason /* 1465d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1466d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1467d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1468d397712bSChris Mason * tree. 1469d352ac68SChris Mason * 1470d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1471d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1472d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1473d352ac68SChris Mason * 1474d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1475d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1476d352ac68SChris Mason */ 1477e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1478e02119d5SChris Mason int lowest_unlock) 1479925baeddSChris Mason { 1480925baeddSChris Mason int i; 1481925baeddSChris Mason int skip_level = level; 1482051e1b9fSChris Mason int no_skips = 0; 1483925baeddSChris Mason struct extent_buffer *t; 1484925baeddSChris Mason 1485925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1486925baeddSChris Mason if (!path->nodes[i]) 1487925baeddSChris Mason break; 1488925baeddSChris Mason if (!path->locks[i]) 1489925baeddSChris Mason break; 1490051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1491925baeddSChris Mason skip_level = i + 1; 1492925baeddSChris Mason continue; 1493925baeddSChris Mason } 1494051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1495925baeddSChris Mason u32 nritems; 1496925baeddSChris Mason t = path->nodes[i]; 1497925baeddSChris Mason nritems = btrfs_header_nritems(t); 1498051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1499925baeddSChris Mason skip_level = i + 1; 1500925baeddSChris Mason continue; 1501925baeddSChris Mason } 1502925baeddSChris Mason } 1503051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1504051e1b9fSChris Mason no_skips = 1; 1505051e1b9fSChris Mason 1506925baeddSChris Mason t = path->nodes[i]; 1507925baeddSChris Mason if (i >= lowest_unlock && i > skip_level && path->locks[i]) { 1508925baeddSChris Mason btrfs_tree_unlock(t); 1509925baeddSChris Mason path->locks[i] = 0; 1510925baeddSChris Mason } 1511925baeddSChris Mason } 1512925baeddSChris Mason } 1513925baeddSChris Mason 15143c69faecSChris Mason /* 1515b4ce94deSChris Mason * This releases any locks held in the path starting at level and 1516b4ce94deSChris Mason * going all the way up to the root. 1517b4ce94deSChris Mason * 1518b4ce94deSChris Mason * btrfs_search_slot will keep the lock held on higher nodes in a few 1519b4ce94deSChris Mason * corner cases, such as COW of the block at slot zero in the node. This 1520b4ce94deSChris Mason * ignores those rules, and it should only be called when there are no 1521b4ce94deSChris Mason * more updates to be done higher up in the tree. 1522b4ce94deSChris Mason */ 1523b4ce94deSChris Mason noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level) 1524b4ce94deSChris Mason { 1525b4ce94deSChris Mason int i; 1526b4ce94deSChris Mason 15275d4f98a2SYan Zheng if (path->keep_locks) 1528b4ce94deSChris Mason return; 1529b4ce94deSChris Mason 1530b4ce94deSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1531b4ce94deSChris Mason if (!path->nodes[i]) 153212f4daccSChris Mason continue; 1533b4ce94deSChris Mason if (!path->locks[i]) 153412f4daccSChris Mason continue; 1535b4ce94deSChris Mason btrfs_tree_unlock(path->nodes[i]); 1536b4ce94deSChris Mason path->locks[i] = 0; 1537b4ce94deSChris Mason } 1538b4ce94deSChris Mason } 1539b4ce94deSChris Mason 1540b4ce94deSChris Mason /* 1541c8c42864SChris Mason * helper function for btrfs_search_slot. The goal is to find a block 1542c8c42864SChris Mason * in cache without setting the path to blocking. If we find the block 1543c8c42864SChris Mason * we return zero and the path is unchanged. 1544c8c42864SChris Mason * 1545c8c42864SChris Mason * If we can't find the block, we set the path blocking and do some 1546c8c42864SChris Mason * reada. -EAGAIN is returned and the search must be repeated. 1547c8c42864SChris Mason */ 1548c8c42864SChris Mason static int 1549c8c42864SChris Mason read_block_for_search(struct btrfs_trans_handle *trans, 1550c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1551c8c42864SChris Mason struct extent_buffer **eb_ret, int level, int slot, 1552c8c42864SChris Mason struct btrfs_key *key) 1553c8c42864SChris Mason { 1554c8c42864SChris Mason u64 blocknr; 1555c8c42864SChris Mason u64 gen; 1556c8c42864SChris Mason u32 blocksize; 1557c8c42864SChris Mason struct extent_buffer *b = *eb_ret; 1558c8c42864SChris Mason struct extent_buffer *tmp; 155976a05b35SChris Mason int ret; 1560c8c42864SChris Mason 1561c8c42864SChris Mason blocknr = btrfs_node_blockptr(b, slot); 1562c8c42864SChris Mason gen = btrfs_node_ptr_generation(b, slot); 1563c8c42864SChris Mason blocksize = btrfs_level_size(root, level - 1); 1564c8c42864SChris Mason 1565c8c42864SChris Mason tmp = btrfs_find_tree_block(root, blocknr, blocksize); 1566c8c42864SChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 156776a05b35SChris Mason /* 156876a05b35SChris Mason * we found an up to date block without sleeping, return 156976a05b35SChris Mason * right away 157076a05b35SChris Mason */ 1571c8c42864SChris Mason *eb_ret = tmp; 1572c8c42864SChris Mason return 0; 1573c8c42864SChris Mason } 1574c8c42864SChris Mason 1575c8c42864SChris Mason /* 1576c8c42864SChris Mason * reduce lock contention at high levels 1577c8c42864SChris Mason * of the btree by dropping locks before 157876a05b35SChris Mason * we read. Don't release the lock on the current 157976a05b35SChris Mason * level because we need to walk this node to figure 158076a05b35SChris Mason * out which blocks to read. 1581c8c42864SChris Mason */ 15828c594ea8SChris Mason btrfs_unlock_up_safe(p, level + 1); 15838c594ea8SChris Mason btrfs_set_path_blocking(p); 15848c594ea8SChris Mason 1585c8c42864SChris Mason if (tmp) 1586c8c42864SChris Mason free_extent_buffer(tmp); 1587c8c42864SChris Mason if (p->reada) 1588c8c42864SChris Mason reada_for_search(root, p, level, slot, key->objectid); 1589c8c42864SChris Mason 15908c594ea8SChris Mason btrfs_release_path(NULL, p); 159176a05b35SChris Mason 159276a05b35SChris Mason ret = -EAGAIN; 1593c8c42864SChris Mason tmp = read_tree_block(root, blocknr, blocksize, gen); 159476a05b35SChris Mason if (tmp) { 159576a05b35SChris Mason /* 159676a05b35SChris Mason * If the read above didn't mark this buffer up to date, 159776a05b35SChris Mason * it will never end up being up to date. Set ret to EIO now 159876a05b35SChris Mason * and give up so that our caller doesn't loop forever 159976a05b35SChris Mason * on our EAGAINs. 160076a05b35SChris Mason */ 160176a05b35SChris Mason if (!btrfs_buffer_uptodate(tmp, 0)) 160276a05b35SChris Mason ret = -EIO; 1603c8c42864SChris Mason free_extent_buffer(tmp); 160476a05b35SChris Mason } 160576a05b35SChris Mason return ret; 1606c8c42864SChris Mason } 1607c8c42864SChris Mason 1608c8c42864SChris Mason /* 1609c8c42864SChris Mason * helper function for btrfs_search_slot. This does all of the checks 1610c8c42864SChris Mason * for node-level blocks and does any balancing required based on 1611c8c42864SChris Mason * the ins_len. 1612c8c42864SChris Mason * 1613c8c42864SChris Mason * If no extra work was required, zero is returned. If we had to 1614c8c42864SChris Mason * drop the path, -EAGAIN is returned and btrfs_search_slot must 1615c8c42864SChris Mason * start over 1616c8c42864SChris Mason */ 1617c8c42864SChris Mason static int 1618c8c42864SChris Mason setup_nodes_for_search(struct btrfs_trans_handle *trans, 1619c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1620c8c42864SChris Mason struct extent_buffer *b, int level, int ins_len) 1621c8c42864SChris Mason { 1622c8c42864SChris Mason int ret; 1623c8c42864SChris Mason if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= 1624c8c42864SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { 1625c8c42864SChris Mason int sret; 1626c8c42864SChris Mason 1627c8c42864SChris Mason sret = reada_for_balance(root, p, level); 1628c8c42864SChris Mason if (sret) 1629c8c42864SChris Mason goto again; 1630c8c42864SChris Mason 1631c8c42864SChris Mason btrfs_set_path_blocking(p); 1632c8c42864SChris Mason sret = split_node(trans, root, p, level); 1633c8c42864SChris Mason btrfs_clear_path_blocking(p, NULL); 1634c8c42864SChris Mason 1635c8c42864SChris Mason BUG_ON(sret > 0); 1636c8c42864SChris Mason if (sret) { 1637c8c42864SChris Mason ret = sret; 1638c8c42864SChris Mason goto done; 1639c8c42864SChris Mason } 1640c8c42864SChris Mason b = p->nodes[level]; 1641c8c42864SChris Mason } else if (ins_len < 0 && btrfs_header_nritems(b) < 1642cfbb9308SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 2) { 1643c8c42864SChris Mason int sret; 1644c8c42864SChris Mason 1645c8c42864SChris Mason sret = reada_for_balance(root, p, level); 1646c8c42864SChris Mason if (sret) 1647c8c42864SChris Mason goto again; 1648c8c42864SChris Mason 1649c8c42864SChris Mason btrfs_set_path_blocking(p); 1650c8c42864SChris Mason sret = balance_level(trans, root, p, level); 1651c8c42864SChris Mason btrfs_clear_path_blocking(p, NULL); 1652c8c42864SChris Mason 1653c8c42864SChris Mason if (sret) { 1654c8c42864SChris Mason ret = sret; 1655c8c42864SChris Mason goto done; 1656c8c42864SChris Mason } 1657c8c42864SChris Mason b = p->nodes[level]; 1658c8c42864SChris Mason if (!b) { 1659c8c42864SChris Mason btrfs_release_path(NULL, p); 1660c8c42864SChris Mason goto again; 1661c8c42864SChris Mason } 1662c8c42864SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 1663c8c42864SChris Mason } 1664c8c42864SChris Mason return 0; 1665c8c42864SChris Mason 1666c8c42864SChris Mason again: 1667c8c42864SChris Mason ret = -EAGAIN; 1668c8c42864SChris Mason done: 1669c8c42864SChris Mason return ret; 1670c8c42864SChris Mason } 1671c8c42864SChris Mason 1672c8c42864SChris Mason /* 167374123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 167474123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 167574123bd7SChris Mason * level of the path (level 0) 167674123bd7SChris Mason * 167774123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 1678aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 1679aa5d6bedSChris Mason * search a negative error number is returned. 168097571fd0SChris Mason * 168197571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 168297571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 168397571fd0SChris Mason * possible) 168474123bd7SChris Mason */ 1685e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 1686e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 1687e089f05cSChris Mason ins_len, int cow) 1688be0e5c09SChris Mason { 16895f39d397SChris Mason struct extent_buffer *b; 1690be0e5c09SChris Mason int slot; 1691be0e5c09SChris Mason int ret; 169233c66f43SYan Zheng int err; 1693be0e5c09SChris Mason int level; 1694925baeddSChris Mason int lowest_unlock = 1; 16959f3a7427SChris Mason u8 lowest_level = 0; 16969f3a7427SChris Mason 16976702ed49SChris Mason lowest_level = p->lowest_level; 1698323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 169922b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 170025179201SJosef Bacik 1701925baeddSChris Mason if (ins_len < 0) 1702925baeddSChris Mason lowest_unlock = 2; 170365b51a00SChris Mason 1704bb803951SChris Mason again: 17055d4f98a2SYan Zheng if (p->search_commit_root) { 17065d4f98a2SYan Zheng b = root->commit_root; 17075d4f98a2SYan Zheng extent_buffer_get(b); 17085d4f98a2SYan Zheng if (!p->skip_locking) 17095d4f98a2SYan Zheng btrfs_tree_lock(b); 17105d4f98a2SYan Zheng } else { 17115cd57b2cSChris Mason if (p->skip_locking) 17125cd57b2cSChris Mason b = btrfs_root_node(root); 17135cd57b2cSChris Mason else 1714925baeddSChris Mason b = btrfs_lock_root_node(root); 17155d4f98a2SYan Zheng } 1716925baeddSChris Mason 1717eb60ceacSChris Mason while (b) { 17185f39d397SChris Mason level = btrfs_header_level(b); 171965b51a00SChris Mason 172065b51a00SChris Mason /* 172165b51a00SChris Mason * setup the path here so we can release it under lock 172265b51a00SChris Mason * contention with the cow code 172365b51a00SChris Mason */ 172465b51a00SChris Mason p->nodes[level] = b; 172565b51a00SChris Mason if (!p->skip_locking) 172665b51a00SChris Mason p->locks[level] = 1; 172765b51a00SChris Mason 172802217ed2SChris Mason if (cow) { 1729c8c42864SChris Mason /* 1730c8c42864SChris Mason * if we don't really need to cow this block 1731c8c42864SChris Mason * then we don't want to set the path blocking, 1732c8c42864SChris Mason * so we test it here 1733c8c42864SChris Mason */ 17345d4f98a2SYan Zheng if (!should_cow_block(trans, root, b)) 173565b51a00SChris Mason goto cow_done; 17365d4f98a2SYan Zheng 1737b4ce94deSChris Mason btrfs_set_path_blocking(p); 1738b4ce94deSChris Mason 173933c66f43SYan Zheng err = btrfs_cow_block(trans, root, b, 1740e20d96d6SChris Mason p->nodes[level + 1], 17419fa8cfe7SChris Mason p->slots[level + 1], &b); 174233c66f43SYan Zheng if (err) { 17435f39d397SChris Mason free_extent_buffer(b); 174433c66f43SYan Zheng ret = err; 174565b51a00SChris Mason goto done; 174654aa1f4dSChris Mason } 174702217ed2SChris Mason } 174865b51a00SChris Mason cow_done: 174902217ed2SChris Mason BUG_ON(!cow && ins_len); 17505f39d397SChris Mason if (level != btrfs_header_level(b)) 17512c90e5d6SChris Mason WARN_ON(1); 17525f39d397SChris Mason level = btrfs_header_level(b); 175365b51a00SChris Mason 1754eb60ceacSChris Mason p->nodes[level] = b; 17555cd57b2cSChris Mason if (!p->skip_locking) 1756925baeddSChris Mason p->locks[level] = 1; 175765b51a00SChris Mason 17584008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1759b4ce94deSChris Mason 1760b4ce94deSChris Mason /* 1761b4ce94deSChris Mason * we have a lock on b and as long as we aren't changing 1762b4ce94deSChris Mason * the tree, there is no way to for the items in b to change. 1763b4ce94deSChris Mason * It is safe to drop the lock on our parent before we 1764b4ce94deSChris Mason * go through the expensive btree search on b. 1765b4ce94deSChris Mason * 1766b4ce94deSChris Mason * If cow is true, then we might be changing slot zero, 1767b4ce94deSChris Mason * which may require changing the parent. So, we can't 1768b4ce94deSChris Mason * drop the lock until after we know which slot we're 1769b4ce94deSChris Mason * operating on. 1770b4ce94deSChris Mason */ 1771b4ce94deSChris Mason if (!cow) 1772b4ce94deSChris Mason btrfs_unlock_up_safe(p, level + 1); 1773b4ce94deSChris Mason 1774123abc88SChris Mason ret = check_block(root, p, level); 177565b51a00SChris Mason if (ret) { 177665b51a00SChris Mason ret = -1; 177765b51a00SChris Mason goto done; 177865b51a00SChris Mason } 1779925baeddSChris Mason 17805f39d397SChris Mason ret = bin_search(b, key, level, &slot); 1781b4ce94deSChris Mason 17825f39d397SChris Mason if (level != 0) { 178333c66f43SYan Zheng int dec = 0; 178433c66f43SYan Zheng if (ret && slot > 0) { 178533c66f43SYan Zheng dec = 1; 1786be0e5c09SChris Mason slot -= 1; 178733c66f43SYan Zheng } 1788be0e5c09SChris Mason p->slots[level] = slot; 178933c66f43SYan Zheng err = setup_nodes_for_search(trans, root, p, b, level, 1790c8c42864SChris Mason ins_len); 179133c66f43SYan Zheng if (err == -EAGAIN) 1792b4ce94deSChris Mason goto again; 179333c66f43SYan Zheng if (err) { 179433c66f43SYan Zheng ret = err; 179565b51a00SChris Mason goto done; 179633c66f43SYan Zheng } 17975c680ed6SChris Mason b = p->nodes[level]; 17985c680ed6SChris Mason slot = p->slots[level]; 1799b4ce94deSChris Mason 1800f9efa9c7SChris Mason unlock_up(p, level, lowest_unlock); 1801f9efa9c7SChris Mason 1802925baeddSChris Mason if (level == lowest_level) { 180333c66f43SYan Zheng if (dec) 180433c66f43SYan Zheng p->slots[level]++; 18055b21f2edSZheng Yan goto done; 1806925baeddSChris Mason } 1807ca7a79adSChris Mason 180833c66f43SYan Zheng err = read_block_for_search(trans, root, p, 1809c8c42864SChris Mason &b, level, slot, key); 181033c66f43SYan Zheng if (err == -EAGAIN) 1811051e1b9fSChris Mason goto again; 181233c66f43SYan Zheng if (err) { 181333c66f43SYan Zheng ret = err; 181476a05b35SChris Mason goto done; 181533c66f43SYan Zheng } 181676a05b35SChris Mason 1817b4ce94deSChris Mason if (!p->skip_locking) { 18184008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 181933c66f43SYan Zheng err = btrfs_try_spin_lock(b); 1820b4ce94deSChris Mason 182133c66f43SYan Zheng if (!err) { 1822b4ce94deSChris Mason btrfs_set_path_blocking(p); 1823925baeddSChris Mason btrfs_tree_lock(b); 18244008c04aSChris Mason btrfs_clear_path_blocking(p, b); 1825b4ce94deSChris Mason } 1826b4ce94deSChris Mason } 1827be0e5c09SChris Mason } else { 1828be0e5c09SChris Mason p->slots[level] = slot; 182987b29b20SYan Zheng if (ins_len > 0 && 183087b29b20SYan Zheng btrfs_leaf_free_space(root, b) < ins_len) { 1831b4ce94deSChris Mason btrfs_set_path_blocking(p); 183233c66f43SYan Zheng err = split_leaf(trans, root, key, 1833cc0c5538SChris Mason p, ins_len, ret == 0); 18344008c04aSChris Mason btrfs_clear_path_blocking(p, NULL); 1835b4ce94deSChris Mason 183633c66f43SYan Zheng BUG_ON(err > 0); 183733c66f43SYan Zheng if (err) { 183833c66f43SYan Zheng ret = err; 183965b51a00SChris Mason goto done; 184065b51a00SChris Mason } 18415c680ed6SChris Mason } 1842459931ecSChris Mason if (!p->search_for_split) 1843925baeddSChris Mason unlock_up(p, level, lowest_unlock); 184465b51a00SChris Mason goto done; 184565b51a00SChris Mason } 184665b51a00SChris Mason } 184765b51a00SChris Mason ret = 1; 184865b51a00SChris Mason done: 1849b4ce94deSChris Mason /* 1850b4ce94deSChris Mason * we don't really know what they plan on doing with the path 1851b4ce94deSChris Mason * from here on, so for now just mark it as blocking 1852b4ce94deSChris Mason */ 1853b9473439SChris Mason if (!p->leave_spinning) 1854b4ce94deSChris Mason btrfs_set_path_blocking(p); 185576a05b35SChris Mason if (ret < 0) 185676a05b35SChris Mason btrfs_release_path(root, p); 1857be0e5c09SChris Mason return ret; 1858be0e5c09SChris Mason } 1859be0e5c09SChris Mason 186074123bd7SChris Mason /* 186174123bd7SChris Mason * adjust the pointers going up the tree, starting at level 186274123bd7SChris Mason * making sure the right key of each node is points to 'key'. 186374123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 186474123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 186574123bd7SChris Mason * higher levels 1866aa5d6bedSChris Mason * 1867aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 1868aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 186974123bd7SChris Mason */ 18705f39d397SChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, 18715f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 18725f39d397SChris Mason struct btrfs_disk_key *key, int level) 1873be0e5c09SChris Mason { 1874be0e5c09SChris Mason int i; 1875aa5d6bedSChris Mason int ret = 0; 18765f39d397SChris Mason struct extent_buffer *t; 18775f39d397SChris Mason 1878234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1879be0e5c09SChris Mason int tslot = path->slots[i]; 1880eb60ceacSChris Mason if (!path->nodes[i]) 1881be0e5c09SChris Mason break; 18825f39d397SChris Mason t = path->nodes[i]; 18835f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 1884d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 1885be0e5c09SChris Mason if (tslot != 0) 1886be0e5c09SChris Mason break; 1887be0e5c09SChris Mason } 1888aa5d6bedSChris Mason return ret; 1889be0e5c09SChris Mason } 1890be0e5c09SChris Mason 189174123bd7SChris Mason /* 189231840ae1SZheng Yan * update item key. 189331840ae1SZheng Yan * 189431840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 189531840ae1SZheng Yan * that the new key won't break the order 189631840ae1SZheng Yan */ 189731840ae1SZheng Yan int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, 189831840ae1SZheng Yan struct btrfs_root *root, struct btrfs_path *path, 189931840ae1SZheng Yan struct btrfs_key *new_key) 190031840ae1SZheng Yan { 190131840ae1SZheng Yan struct btrfs_disk_key disk_key; 190231840ae1SZheng Yan struct extent_buffer *eb; 190331840ae1SZheng Yan int slot; 190431840ae1SZheng Yan 190531840ae1SZheng Yan eb = path->nodes[0]; 190631840ae1SZheng Yan slot = path->slots[0]; 190731840ae1SZheng Yan if (slot > 0) { 190831840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 190931840ae1SZheng Yan if (comp_keys(&disk_key, new_key) >= 0) 191031840ae1SZheng Yan return -1; 191131840ae1SZheng Yan } 191231840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 191331840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 191431840ae1SZheng Yan if (comp_keys(&disk_key, new_key) <= 0) 191531840ae1SZheng Yan return -1; 191631840ae1SZheng Yan } 191731840ae1SZheng Yan 191831840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 191931840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 192031840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 192131840ae1SZheng Yan if (slot == 0) 192231840ae1SZheng Yan fixup_low_keys(trans, root, path, &disk_key, 1); 192331840ae1SZheng Yan return 0; 192431840ae1SZheng Yan } 192531840ae1SZheng Yan 192631840ae1SZheng Yan /* 192774123bd7SChris Mason * try to push data from one node into the next node left in the 192879f95c82SChris Mason * tree. 1929aa5d6bedSChris Mason * 1930aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1931aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 193274123bd7SChris Mason */ 193398ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 193498ed5174SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 1935971a1f66SChris Mason struct extent_buffer *src, int empty) 1936be0e5c09SChris Mason { 1937be0e5c09SChris Mason int push_items = 0; 1938bb803951SChris Mason int src_nritems; 1939bb803951SChris Mason int dst_nritems; 1940aa5d6bedSChris Mason int ret = 0; 1941be0e5c09SChris Mason 19425f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 19435f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1944123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 19457bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 19467bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 194754aa1f4dSChris Mason 1948bce4eae9SChris Mason if (!empty && src_nritems <= 8) 1949971a1f66SChris Mason return 1; 1950971a1f66SChris Mason 1951d397712bSChris Mason if (push_items <= 0) 1952be0e5c09SChris Mason return 1; 1953be0e5c09SChris Mason 1954bce4eae9SChris Mason if (empty) { 1955971a1f66SChris Mason push_items = min(src_nritems, push_items); 1956bce4eae9SChris Mason if (push_items < src_nritems) { 1957bce4eae9SChris Mason /* leave at least 8 pointers in the node if 1958bce4eae9SChris Mason * we aren't going to empty it 1959bce4eae9SChris Mason */ 1960bce4eae9SChris Mason if (src_nritems - push_items < 8) { 1961bce4eae9SChris Mason if (push_items <= 8) 1962bce4eae9SChris Mason return 1; 1963bce4eae9SChris Mason push_items -= 8; 1964bce4eae9SChris Mason } 1965bce4eae9SChris Mason } 1966bce4eae9SChris Mason } else 1967bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 196879f95c82SChris Mason 19695f39d397SChris Mason copy_extent_buffer(dst, src, 19705f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 19715f39d397SChris Mason btrfs_node_key_ptr_offset(0), 1972123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 19735f39d397SChris Mason 1974bb803951SChris Mason if (push_items < src_nritems) { 19755f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 19765f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 1977e2fa7227SChris Mason (src_nritems - push_items) * 1978123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1979bb803951SChris Mason } 19805f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 19815f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 19825f39d397SChris Mason btrfs_mark_buffer_dirty(src); 19835f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 198431840ae1SZheng Yan 1985bb803951SChris Mason return ret; 1986be0e5c09SChris Mason } 1987be0e5c09SChris Mason 198897571fd0SChris Mason /* 198979f95c82SChris Mason * try to push data from one node into the next node right in the 199079f95c82SChris Mason * tree. 199179f95c82SChris Mason * 199279f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 199379f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 199479f95c82SChris Mason * 199579f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 199679f95c82SChris Mason */ 19975f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 19985f39d397SChris Mason struct btrfs_root *root, 19995f39d397SChris Mason struct extent_buffer *dst, 20005f39d397SChris Mason struct extent_buffer *src) 200179f95c82SChris Mason { 200279f95c82SChris Mason int push_items = 0; 200379f95c82SChris Mason int max_push; 200479f95c82SChris Mason int src_nritems; 200579f95c82SChris Mason int dst_nritems; 200679f95c82SChris Mason int ret = 0; 200779f95c82SChris Mason 20087bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 20097bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 20107bb86316SChris Mason 20115f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 20125f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 2013123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 2014d397712bSChris Mason if (push_items <= 0) 201579f95c82SChris Mason return 1; 2016bce4eae9SChris Mason 2017d397712bSChris Mason if (src_nritems < 4) 2018bce4eae9SChris Mason return 1; 201979f95c82SChris Mason 202079f95c82SChris Mason max_push = src_nritems / 2 + 1; 202179f95c82SChris Mason /* don't try to empty the node */ 2022d397712bSChris Mason if (max_push >= src_nritems) 202379f95c82SChris Mason return 1; 2024252c38f0SYan 202579f95c82SChris Mason if (max_push < push_items) 202679f95c82SChris Mason push_items = max_push; 202779f95c82SChris Mason 20285f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 20295f39d397SChris Mason btrfs_node_key_ptr_offset(0), 20305f39d397SChris Mason (dst_nritems) * 20315f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 2032d6025579SChris Mason 20335f39d397SChris Mason copy_extent_buffer(dst, src, 20345f39d397SChris Mason btrfs_node_key_ptr_offset(0), 20355f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 2036123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 203779f95c82SChris Mason 20385f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 20395f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 204079f95c82SChris Mason 20415f39d397SChris Mason btrfs_mark_buffer_dirty(src); 20425f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 204331840ae1SZheng Yan 204479f95c82SChris Mason return ret; 204579f95c82SChris Mason } 204679f95c82SChris Mason 204779f95c82SChris Mason /* 204897571fd0SChris Mason * helper function to insert a new root level in the tree. 204997571fd0SChris Mason * A new node is allocated, and a single item is inserted to 205097571fd0SChris Mason * point to the existing root 2051aa5d6bedSChris Mason * 2052aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 205397571fd0SChris Mason */ 2054d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 20555f39d397SChris Mason struct btrfs_root *root, 20565f39d397SChris Mason struct btrfs_path *path, int level) 205774123bd7SChris Mason { 20587bb86316SChris Mason u64 lower_gen; 20595f39d397SChris Mason struct extent_buffer *lower; 20605f39d397SChris Mason struct extent_buffer *c; 2061925baeddSChris Mason struct extent_buffer *old; 20625f39d397SChris Mason struct btrfs_disk_key lower_key; 20635c680ed6SChris Mason 20645c680ed6SChris Mason BUG_ON(path->nodes[level]); 20655c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 20665c680ed6SChris Mason 20677bb86316SChris Mason lower = path->nodes[level-1]; 20687bb86316SChris Mason if (level == 1) 20697bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 20707bb86316SChris Mason else 20717bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 20727bb86316SChris Mason 207331840ae1SZheng Yan c = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 20745d4f98a2SYan Zheng root->root_key.objectid, &lower_key, 2075ad3d81baSChristoph Hellwig level, root->node->start, 0); 20765f39d397SChris Mason if (IS_ERR(c)) 20775f39d397SChris Mason return PTR_ERR(c); 2078925baeddSChris Mason 20795d4f98a2SYan Zheng memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header)); 20805f39d397SChris Mason btrfs_set_header_nritems(c, 1); 20815f39d397SChris Mason btrfs_set_header_level(c, level); 2082db94535dSChris Mason btrfs_set_header_bytenr(c, c->start); 20835f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 20845d4f98a2SYan Zheng btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV); 20855f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 2086d5719762SChris Mason 20875f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 20885f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 20895f39d397SChris Mason BTRFS_FSID_SIZE); 2090e17cade2SChris Mason 2091e17cade2SChris Mason write_extent_buffer(c, root->fs_info->chunk_tree_uuid, 2092e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(c), 2093e17cade2SChris Mason BTRFS_UUID_SIZE); 2094e17cade2SChris Mason 20955f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 2096db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 20977bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 209831840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 20997bb86316SChris Mason 21007bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 21015f39d397SChris Mason 21025f39d397SChris Mason btrfs_mark_buffer_dirty(c); 2103d5719762SChris Mason 2104925baeddSChris Mason spin_lock(&root->node_lock); 2105925baeddSChris Mason old = root->node; 21065f39d397SChris Mason root->node = c; 2107925baeddSChris Mason spin_unlock(&root->node_lock); 2108925baeddSChris Mason 2109925baeddSChris Mason /* the super has an extra ref to root->node */ 2110925baeddSChris Mason free_extent_buffer(old); 2111925baeddSChris Mason 21120b86a832SChris Mason add_root_to_dirty_list(root); 21135f39d397SChris Mason extent_buffer_get(c); 21145f39d397SChris Mason path->nodes[level] = c; 2115925baeddSChris Mason path->locks[level] = 1; 211674123bd7SChris Mason path->slots[level] = 0; 211774123bd7SChris Mason return 0; 211874123bd7SChris Mason } 21195c680ed6SChris Mason 21205c680ed6SChris Mason /* 21215c680ed6SChris Mason * worker function to insert a single pointer in a node. 21225c680ed6SChris Mason * the node should have enough room for the pointer already 212397571fd0SChris Mason * 21245c680ed6SChris Mason * slot and level indicate where you want the key to go, and 21255c680ed6SChris Mason * blocknr is the block the key points to. 2126aa5d6bedSChris Mason * 2127aa5d6bedSChris Mason * returns zero on success and < 0 on any error 21285c680ed6SChris Mason */ 2129e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 2130e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 2131db94535dSChris Mason *key, u64 bytenr, int slot, int level) 21325c680ed6SChris Mason { 21335f39d397SChris Mason struct extent_buffer *lower; 21345c680ed6SChris Mason int nritems; 21355c680ed6SChris Mason 21365c680ed6SChris Mason BUG_ON(!path->nodes[level]); 21375f39d397SChris Mason lower = path->nodes[level]; 21385f39d397SChris Mason nritems = btrfs_header_nritems(lower); 2139c293498bSStoyan Gaydarov BUG_ON(slot > nritems); 2140123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 214174123bd7SChris Mason BUG(); 214274123bd7SChris Mason if (slot != nritems) { 21435f39d397SChris Mason memmove_extent_buffer(lower, 21445f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 21455f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 2146123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 214774123bd7SChris Mason } 21485f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 2149db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 215074493f7aSChris Mason WARN_ON(trans->transid == 0); 215174493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 21525f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 21535f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 215474123bd7SChris Mason return 0; 215574123bd7SChris Mason } 215674123bd7SChris Mason 215797571fd0SChris Mason /* 215897571fd0SChris Mason * split the node at the specified level in path in two. 215997571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 216097571fd0SChris Mason * 216197571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 216297571fd0SChris Mason * left and right, if either one works, it returns right away. 2163aa5d6bedSChris Mason * 2164aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 216597571fd0SChris Mason */ 2166e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 2167e02119d5SChris Mason struct btrfs_root *root, 2168e02119d5SChris Mason struct btrfs_path *path, int level) 2169be0e5c09SChris Mason { 21705f39d397SChris Mason struct extent_buffer *c; 21715f39d397SChris Mason struct extent_buffer *split; 21725f39d397SChris Mason struct btrfs_disk_key disk_key; 2173be0e5c09SChris Mason int mid; 21745c680ed6SChris Mason int ret; 2175aa5d6bedSChris Mason int wret; 21767518a238SChris Mason u32 c_nritems; 2177be0e5c09SChris Mason 21785f39d397SChris Mason c = path->nodes[level]; 21797bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 21805f39d397SChris Mason if (c == root->node) { 21815c680ed6SChris Mason /* trying to split the root, lets make a new one */ 2182e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 21835c680ed6SChris Mason if (ret) 21845c680ed6SChris Mason return ret; 2185b3612421SChris Mason } else { 2186e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 21875f39d397SChris Mason c = path->nodes[level]; 21885f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 2189c448acf0SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) 2190e66f709bSChris Mason return 0; 219154aa1f4dSChris Mason if (ret < 0) 219254aa1f4dSChris Mason return ret; 21935c680ed6SChris Mason } 2194e66f709bSChris Mason 21955f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 21965d4f98a2SYan Zheng mid = (c_nritems + 1) / 2; 21975d4f98a2SYan Zheng btrfs_node_key(c, &disk_key, mid); 21987bb86316SChris Mason 21995d4f98a2SYan Zheng split = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 22007bb86316SChris Mason root->root_key.objectid, 22015d4f98a2SYan Zheng &disk_key, level, c->start, 0); 22025f39d397SChris Mason if (IS_ERR(split)) 22035f39d397SChris Mason return PTR_ERR(split); 220454aa1f4dSChris Mason 22055d4f98a2SYan Zheng memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header)); 22065f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 2207db94535dSChris Mason btrfs_set_header_bytenr(split, split->start); 22085f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 22095d4f98a2SYan Zheng btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV); 22105f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 22115f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 22125f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 22135f39d397SChris Mason BTRFS_FSID_SIZE); 2214e17cade2SChris Mason write_extent_buffer(split, root->fs_info->chunk_tree_uuid, 2215e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(split), 2216e17cade2SChris Mason BTRFS_UUID_SIZE); 22175f39d397SChris Mason 22185f39d397SChris Mason 22195f39d397SChris Mason copy_extent_buffer(split, c, 22205f39d397SChris Mason btrfs_node_key_ptr_offset(0), 22215f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2222123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 22235f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 22245f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2225aa5d6bedSChris Mason ret = 0; 2226aa5d6bedSChris Mason 22275f39d397SChris Mason btrfs_mark_buffer_dirty(c); 22285f39d397SChris Mason btrfs_mark_buffer_dirty(split); 22295f39d397SChris Mason 2230db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, split->start, 22315f39d397SChris Mason path->slots[level + 1] + 1, 2232123abc88SChris Mason level + 1); 2233aa5d6bedSChris Mason if (wret) 2234aa5d6bedSChris Mason ret = wret; 2235aa5d6bedSChris Mason 22365de08d7dSChris Mason if (path->slots[level] >= mid) { 22375c680ed6SChris Mason path->slots[level] -= mid; 2238925baeddSChris Mason btrfs_tree_unlock(c); 22395f39d397SChris Mason free_extent_buffer(c); 22405f39d397SChris Mason path->nodes[level] = split; 22415c680ed6SChris Mason path->slots[level + 1] += 1; 2242eb60ceacSChris Mason } else { 2243925baeddSChris Mason btrfs_tree_unlock(split); 22445f39d397SChris Mason free_extent_buffer(split); 2245be0e5c09SChris Mason } 2246aa5d6bedSChris Mason return ret; 2247be0e5c09SChris Mason } 2248be0e5c09SChris Mason 224974123bd7SChris Mason /* 225074123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 225174123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 225274123bd7SChris Mason * space used both by the item structs and the item data 225374123bd7SChris Mason */ 22545f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2255be0e5c09SChris Mason { 2256be0e5c09SChris Mason int data_len; 22575f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2258d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2259be0e5c09SChris Mason 2260be0e5c09SChris Mason if (!nr) 2261be0e5c09SChris Mason return 0; 22625f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 22635f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 22640783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2265d4dbff95SChris Mason WARN_ON(data_len < 0); 2266be0e5c09SChris Mason return data_len; 2267be0e5c09SChris Mason } 2268be0e5c09SChris Mason 226974123bd7SChris Mason /* 2270d4dbff95SChris Mason * The space between the end of the leaf items and 2271d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2272d4dbff95SChris Mason * the leaf has left for both items and data 2273d4dbff95SChris Mason */ 2274d397712bSChris Mason noinline int btrfs_leaf_free_space(struct btrfs_root *root, 2275e02119d5SChris Mason struct extent_buffer *leaf) 2276d4dbff95SChris Mason { 22775f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 22785f39d397SChris Mason int ret; 22795f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 22805f39d397SChris Mason if (ret < 0) { 2281d397712bSChris Mason printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, " 2282d397712bSChris Mason "used %d nritems %d\n", 2283ae2f5411SJens Axboe ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), 22845f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 22855f39d397SChris Mason } 22865f39d397SChris Mason return ret; 2287d4dbff95SChris Mason } 2288d4dbff95SChris Mason 228944871b1bSChris Mason static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, 229044871b1bSChris Mason struct btrfs_root *root, 229144871b1bSChris Mason struct btrfs_path *path, 229244871b1bSChris Mason int data_size, int empty, 229344871b1bSChris Mason struct extent_buffer *right, 229444871b1bSChris Mason int free_space, u32 left_nritems) 229500ec4c51SChris Mason { 22965f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 229744871b1bSChris Mason struct extent_buffer *upper = path->nodes[1]; 22985f39d397SChris Mason struct btrfs_disk_key disk_key; 229900ec4c51SChris Mason int slot; 230034a38218SChris Mason u32 i; 230100ec4c51SChris Mason int push_space = 0; 230200ec4c51SChris Mason int push_items = 0; 23030783fcfcSChris Mason struct btrfs_item *item; 230434a38218SChris Mason u32 nr; 23057518a238SChris Mason u32 right_nritems; 23065f39d397SChris Mason u32 data_end; 2307db94535dSChris Mason u32 this_item_size; 230800ec4c51SChris Mason 230934a38218SChris Mason if (empty) 231034a38218SChris Mason nr = 0; 231134a38218SChris Mason else 231234a38218SChris Mason nr = 1; 231334a38218SChris Mason 231431840ae1SZheng Yan if (path->slots[0] >= left_nritems) 231587b29b20SYan Zheng push_space += data_size; 231631840ae1SZheng Yan 231744871b1bSChris Mason slot = path->slots[1]; 231834a38218SChris Mason i = left_nritems - 1; 231934a38218SChris Mason while (i >= nr) { 23205f39d397SChris Mason item = btrfs_item_nr(left, i); 2321db94535dSChris Mason 232231840ae1SZheng Yan if (!empty && push_items > 0) { 232331840ae1SZheng Yan if (path->slots[0] > i) 232431840ae1SZheng Yan break; 232531840ae1SZheng Yan if (path->slots[0] == i) { 232631840ae1SZheng Yan int space = btrfs_leaf_free_space(root, left); 232731840ae1SZheng Yan if (space + push_space * 2 > free_space) 232831840ae1SZheng Yan break; 232931840ae1SZheng Yan } 233031840ae1SZheng Yan } 233131840ae1SZheng Yan 233200ec4c51SChris Mason if (path->slots[0] == i) 233387b29b20SYan Zheng push_space += data_size; 2334db94535dSChris Mason 2335db94535dSChris Mason if (!left->map_token) { 2336db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 2337db94535dSChris Mason sizeof(struct btrfs_item), 2338db94535dSChris Mason &left->map_token, &left->kaddr, 2339db94535dSChris Mason &left->map_start, &left->map_len, 2340db94535dSChris Mason KM_USER1); 2341db94535dSChris Mason } 2342db94535dSChris Mason 2343db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 2344db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 234500ec4c51SChris Mason break; 234631840ae1SZheng Yan 234700ec4c51SChris Mason push_items++; 2348db94535dSChris Mason push_space += this_item_size + sizeof(*item); 234934a38218SChris Mason if (i == 0) 235034a38218SChris Mason break; 235134a38218SChris Mason i--; 2352db94535dSChris Mason } 2353db94535dSChris Mason if (left->map_token) { 2354db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 2355db94535dSChris Mason left->map_token = NULL; 235600ec4c51SChris Mason } 23575f39d397SChris Mason 2358925baeddSChris Mason if (push_items == 0) 2359925baeddSChris Mason goto out_unlock; 23605f39d397SChris Mason 236134a38218SChris Mason if (!empty && push_items == left_nritems) 2362a429e513SChris Mason WARN_ON(1); 23635f39d397SChris Mason 236400ec4c51SChris Mason /* push left to right */ 23655f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 236634a38218SChris Mason 23675f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 2368123abc88SChris Mason push_space -= leaf_data_end(root, left); 23695f39d397SChris Mason 237000ec4c51SChris Mason /* make room in the right data area */ 23715f39d397SChris Mason data_end = leaf_data_end(root, right); 23725f39d397SChris Mason memmove_extent_buffer(right, 23735f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 23745f39d397SChris Mason btrfs_leaf_data(right) + data_end, 23755f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 23765f39d397SChris Mason 237700ec4c51SChris Mason /* copy from the left data area */ 23785f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 2379d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2380d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 2381d6025579SChris Mason push_space); 23825f39d397SChris Mason 23835f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 23845f39d397SChris Mason btrfs_item_nr_offset(0), 23850783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 23865f39d397SChris Mason 238700ec4c51SChris Mason /* copy the items from left to right */ 23885f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 23895f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 23900783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 239100ec4c51SChris Mason 239200ec4c51SChris Mason /* update the item pointers */ 23937518a238SChris Mason right_nritems += push_items; 23945f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 2395123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 23967518a238SChris Mason for (i = 0; i < right_nritems; i++) { 23975f39d397SChris Mason item = btrfs_item_nr(right, i); 2398db94535dSChris Mason if (!right->map_token) { 2399db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2400db94535dSChris Mason sizeof(struct btrfs_item), 2401db94535dSChris Mason &right->map_token, &right->kaddr, 2402db94535dSChris Mason &right->map_start, &right->map_len, 2403db94535dSChris Mason KM_USER1); 2404db94535dSChris Mason } 2405db94535dSChris Mason push_space -= btrfs_item_size(right, item); 2406db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2407db94535dSChris Mason } 2408db94535dSChris Mason 2409db94535dSChris Mason if (right->map_token) { 2410db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2411db94535dSChris Mason right->map_token = NULL; 241200ec4c51SChris Mason } 24137518a238SChris Mason left_nritems -= push_items; 24145f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 241500ec4c51SChris Mason 241634a38218SChris Mason if (left_nritems) 24175f39d397SChris Mason btrfs_mark_buffer_dirty(left); 24185f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2419a429e513SChris Mason 24205f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 24215f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2422d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 242302217ed2SChris Mason 242400ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 24257518a238SChris Mason if (path->slots[0] >= left_nritems) { 24267518a238SChris Mason path->slots[0] -= left_nritems; 2427925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2428925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2429925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 24305f39d397SChris Mason free_extent_buffer(path->nodes[0]); 24315f39d397SChris Mason path->nodes[0] = right; 243200ec4c51SChris Mason path->slots[1] += 1; 243300ec4c51SChris Mason } else { 2434925baeddSChris Mason btrfs_tree_unlock(right); 24355f39d397SChris Mason free_extent_buffer(right); 243600ec4c51SChris Mason } 243700ec4c51SChris Mason return 0; 2438925baeddSChris Mason 2439925baeddSChris Mason out_unlock: 2440925baeddSChris Mason btrfs_tree_unlock(right); 2441925baeddSChris Mason free_extent_buffer(right); 2442925baeddSChris Mason return 1; 244300ec4c51SChris Mason } 2444925baeddSChris Mason 244500ec4c51SChris Mason /* 244644871b1bSChris Mason * push some data in the path leaf to the right, trying to free up at 244774123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 244844871b1bSChris Mason * 244944871b1bSChris Mason * returns 1 if the push failed because the other node didn't have enough 245044871b1bSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 245174123bd7SChris Mason */ 245244871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 245334a38218SChris Mason *root, struct btrfs_path *path, int data_size, 245434a38218SChris Mason int empty) 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); 247544871b1bSChris Mason btrfs_tree_lock(right); 247644871b1bSChris Mason btrfs_set_lock_blocking(right); 247744871b1bSChris Mason 247844871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 247944871b1bSChris Mason if (free_space < data_size) 248044871b1bSChris Mason goto out_unlock; 248144871b1bSChris Mason 248244871b1bSChris Mason /* cow and double check */ 248344871b1bSChris Mason ret = btrfs_cow_block(trans, root, right, upper, 248444871b1bSChris Mason slot + 1, &right); 248544871b1bSChris Mason if (ret) 248644871b1bSChris Mason goto out_unlock; 248744871b1bSChris Mason 248844871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 248944871b1bSChris Mason if (free_space < data_size) 249044871b1bSChris Mason goto out_unlock; 249144871b1bSChris Mason 249244871b1bSChris Mason left_nritems = btrfs_header_nritems(left); 249344871b1bSChris Mason if (left_nritems == 0) 249444871b1bSChris Mason goto out_unlock; 249544871b1bSChris Mason 249644871b1bSChris Mason return __push_leaf_right(trans, root, path, data_size, empty, 249744871b1bSChris Mason right, free_space, left_nritems); 249844871b1bSChris Mason out_unlock: 249944871b1bSChris Mason btrfs_tree_unlock(right); 250044871b1bSChris Mason free_extent_buffer(right); 250144871b1bSChris Mason return 1; 250244871b1bSChris Mason } 250344871b1bSChris Mason 250444871b1bSChris Mason /* 250544871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 250644871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 250744871b1bSChris Mason */ 250844871b1bSChris Mason static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, 250944871b1bSChris Mason struct btrfs_root *root, 251044871b1bSChris Mason struct btrfs_path *path, int data_size, 251144871b1bSChris Mason int empty, struct extent_buffer *left, 251244871b1bSChris Mason int free_space, int right_nritems) 251344871b1bSChris Mason { 25145f39d397SChris Mason struct btrfs_disk_key disk_key; 25155f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 2516be0e5c09SChris Mason int slot; 2517be0e5c09SChris Mason int i; 2518be0e5c09SChris Mason int push_space = 0; 2519be0e5c09SChris Mason int push_items = 0; 25200783fcfcSChris Mason struct btrfs_item *item; 25217518a238SChris Mason u32 old_left_nritems; 252234a38218SChris Mason u32 nr; 2523aa5d6bedSChris Mason int ret = 0; 2524aa5d6bedSChris Mason int wret; 2525db94535dSChris Mason u32 this_item_size; 2526db94535dSChris Mason u32 old_left_item_size; 2527be0e5c09SChris Mason 2528be0e5c09SChris Mason slot = path->slots[1]; 252902217ed2SChris Mason 253034a38218SChris Mason if (empty) 253134a38218SChris Mason nr = right_nritems; 253234a38218SChris Mason else 253334a38218SChris Mason nr = right_nritems - 1; 253434a38218SChris Mason 253534a38218SChris Mason for (i = 0; i < nr; i++) { 25365f39d397SChris Mason item = btrfs_item_nr(right, i); 2537db94535dSChris Mason if (!right->map_token) { 2538db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2539db94535dSChris Mason sizeof(struct btrfs_item), 2540db94535dSChris Mason &right->map_token, &right->kaddr, 2541db94535dSChris Mason &right->map_start, &right->map_len, 2542db94535dSChris Mason KM_USER1); 2543db94535dSChris Mason } 2544db94535dSChris Mason 254531840ae1SZheng Yan if (!empty && push_items > 0) { 254631840ae1SZheng Yan if (path->slots[0] < i) 254731840ae1SZheng Yan break; 254831840ae1SZheng Yan if (path->slots[0] == i) { 254931840ae1SZheng Yan int space = btrfs_leaf_free_space(root, right); 255031840ae1SZheng Yan if (space + push_space * 2 > free_space) 255131840ae1SZheng Yan break; 255231840ae1SZheng Yan } 255331840ae1SZheng Yan } 255431840ae1SZheng Yan 2555be0e5c09SChris Mason if (path->slots[0] == i) 255687b29b20SYan Zheng push_space += data_size; 2557db94535dSChris Mason 2558db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 2559db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 2560be0e5c09SChris Mason break; 2561db94535dSChris Mason 2562be0e5c09SChris Mason push_items++; 2563db94535dSChris Mason push_space += this_item_size + sizeof(*item); 2564be0e5c09SChris Mason } 2565db94535dSChris Mason 2566db94535dSChris Mason if (right->map_token) { 2567db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2568db94535dSChris Mason right->map_token = NULL; 2569db94535dSChris Mason } 2570db94535dSChris Mason 2571be0e5c09SChris Mason if (push_items == 0) { 2572925baeddSChris Mason ret = 1; 2573925baeddSChris Mason goto out; 2574be0e5c09SChris Mason } 257534a38218SChris Mason if (!empty && push_items == btrfs_header_nritems(right)) 2576a429e513SChris Mason WARN_ON(1); 25775f39d397SChris Mason 2578be0e5c09SChris Mason /* push data from right to left */ 25795f39d397SChris Mason copy_extent_buffer(left, right, 25805f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 25815f39d397SChris Mason btrfs_item_nr_offset(0), 25825f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 25835f39d397SChris Mason 2584123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 25855f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1); 25865f39d397SChris Mason 25875f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 2588d6025579SChris Mason leaf_data_end(root, left) - push_space, 2589123abc88SChris Mason btrfs_leaf_data(right) + 25905f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 2591be0e5c09SChris Mason push_space); 25925f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 259387b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 2594eb60ceacSChris Mason 2595db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 2596be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 25975f39d397SChris Mason u32 ioff; 2598db94535dSChris Mason 25995f39d397SChris Mason item = btrfs_item_nr(left, i); 2600db94535dSChris Mason if (!left->map_token) { 2601db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 2602db94535dSChris Mason sizeof(struct btrfs_item), 2603db94535dSChris Mason &left->map_token, &left->kaddr, 2604db94535dSChris Mason &left->map_start, &left->map_len, 2605db94535dSChris Mason KM_USER1); 2606db94535dSChris Mason } 2607db94535dSChris Mason 26085f39d397SChris Mason ioff = btrfs_item_offset(left, item); 26095f39d397SChris Mason btrfs_set_item_offset(left, item, 2610db94535dSChris Mason ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size)); 2611be0e5c09SChris Mason } 26125f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 2613db94535dSChris Mason if (left->map_token) { 2614db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 2615db94535dSChris Mason left->map_token = NULL; 2616db94535dSChris Mason } 2617be0e5c09SChris Mason 2618be0e5c09SChris Mason /* fixup right node */ 261934a38218SChris Mason if (push_items > right_nritems) { 2620d397712bSChris Mason printk(KERN_CRIT "push items %d nr %u\n", push_items, 2621d397712bSChris Mason right_nritems); 262234a38218SChris Mason WARN_ON(1); 262334a38218SChris Mason } 262434a38218SChris Mason 262534a38218SChris Mason if (push_items < right_nritems) { 26265f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 2627123abc88SChris Mason leaf_data_end(root, right); 26285f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 2629d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2630d6025579SChris Mason btrfs_leaf_data(right) + 2631123abc88SChris Mason leaf_data_end(root, right), push_space); 26325f39d397SChris Mason 26335f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 26345f39d397SChris Mason btrfs_item_nr_offset(push_items), 26355f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 26360783fcfcSChris Mason sizeof(struct btrfs_item)); 263734a38218SChris Mason } 2638eef1c494SYan right_nritems -= push_items; 2639eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 2640123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 26415f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 26425f39d397SChris Mason item = btrfs_item_nr(right, i); 2643db94535dSChris Mason 2644db94535dSChris Mason if (!right->map_token) { 2645db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2646db94535dSChris Mason sizeof(struct btrfs_item), 2647db94535dSChris Mason &right->map_token, &right->kaddr, 2648db94535dSChris Mason &right->map_start, &right->map_len, 2649db94535dSChris Mason KM_USER1); 2650db94535dSChris Mason } 2651db94535dSChris Mason 2652db94535dSChris Mason push_space = push_space - btrfs_item_size(right, item); 2653db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 2654db94535dSChris Mason } 2655db94535dSChris Mason if (right->map_token) { 2656db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2657db94535dSChris Mason right->map_token = NULL; 2658be0e5c09SChris Mason } 2659eb60ceacSChris Mason 26605f39d397SChris Mason btrfs_mark_buffer_dirty(left); 266134a38218SChris Mason if (right_nritems) 26625f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2663098f59c2SChris Mason 26645f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 26655f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 2666aa5d6bedSChris Mason if (wret) 2667aa5d6bedSChris Mason ret = wret; 2668be0e5c09SChris Mason 2669be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 2670be0e5c09SChris Mason if (path->slots[0] < push_items) { 2671be0e5c09SChris Mason path->slots[0] += old_left_nritems; 2672925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2673925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2674925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 26755f39d397SChris Mason free_extent_buffer(path->nodes[0]); 26765f39d397SChris Mason path->nodes[0] = left; 2677be0e5c09SChris Mason path->slots[1] -= 1; 2678be0e5c09SChris Mason } else { 2679925baeddSChris Mason btrfs_tree_unlock(left); 26805f39d397SChris Mason free_extent_buffer(left); 2681be0e5c09SChris Mason path->slots[0] -= push_items; 2682be0e5c09SChris Mason } 2683eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2684aa5d6bedSChris Mason return ret; 2685925baeddSChris Mason out: 2686925baeddSChris Mason btrfs_tree_unlock(left); 2687925baeddSChris Mason free_extent_buffer(left); 2688925baeddSChris Mason return ret; 2689be0e5c09SChris Mason } 2690be0e5c09SChris Mason 269174123bd7SChris Mason /* 269244871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 269344871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 269444871b1bSChris Mason */ 269544871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 269644871b1bSChris Mason *root, struct btrfs_path *path, int data_size, 269744871b1bSChris Mason int empty) 269844871b1bSChris Mason { 269944871b1bSChris Mason struct extent_buffer *right = path->nodes[0]; 270044871b1bSChris Mason struct extent_buffer *left; 270144871b1bSChris Mason int slot; 270244871b1bSChris Mason int free_space; 270344871b1bSChris Mason u32 right_nritems; 270444871b1bSChris Mason int ret = 0; 270544871b1bSChris Mason 270644871b1bSChris Mason slot = path->slots[1]; 270744871b1bSChris Mason if (slot == 0) 270844871b1bSChris Mason return 1; 270944871b1bSChris Mason if (!path->nodes[1]) 271044871b1bSChris Mason return 1; 271144871b1bSChris Mason 271244871b1bSChris Mason right_nritems = btrfs_header_nritems(right); 271344871b1bSChris Mason if (right_nritems == 0) 271444871b1bSChris Mason return 1; 271544871b1bSChris Mason 271644871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 271744871b1bSChris Mason 271844871b1bSChris Mason left = read_node_slot(root, path->nodes[1], slot - 1); 271944871b1bSChris Mason btrfs_tree_lock(left); 272044871b1bSChris Mason btrfs_set_lock_blocking(left); 272144871b1bSChris Mason 272244871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 272344871b1bSChris Mason if (free_space < data_size) { 272444871b1bSChris Mason ret = 1; 272544871b1bSChris Mason goto out; 272644871b1bSChris Mason } 272744871b1bSChris Mason 272844871b1bSChris Mason /* cow and double check */ 272944871b1bSChris Mason ret = btrfs_cow_block(trans, root, left, 273044871b1bSChris Mason path->nodes[1], slot - 1, &left); 273144871b1bSChris Mason if (ret) { 273244871b1bSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 273344871b1bSChris Mason ret = 1; 273444871b1bSChris Mason goto out; 273544871b1bSChris Mason } 273644871b1bSChris Mason 273744871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 273844871b1bSChris Mason if (free_space < data_size) { 273944871b1bSChris Mason ret = 1; 274044871b1bSChris Mason goto out; 274144871b1bSChris Mason } 274244871b1bSChris Mason 274344871b1bSChris Mason return __push_leaf_left(trans, root, path, data_size, 274444871b1bSChris Mason empty, left, free_space, right_nritems); 274544871b1bSChris Mason out: 274644871b1bSChris Mason btrfs_tree_unlock(left); 274744871b1bSChris Mason free_extent_buffer(left); 274844871b1bSChris Mason return ret; 274944871b1bSChris Mason } 275044871b1bSChris Mason 275144871b1bSChris Mason /* 275274123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 275374123bd7SChris Mason * available for the resulting leaf level of the path. 2754aa5d6bedSChris Mason * 2755aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 275674123bd7SChris Mason */ 275744871b1bSChris Mason static noinline int copy_for_split(struct btrfs_trans_handle *trans, 2758e02119d5SChris Mason struct btrfs_root *root, 275944871b1bSChris Mason struct btrfs_path *path, 276044871b1bSChris Mason struct extent_buffer *l, 276144871b1bSChris Mason struct extent_buffer *right, 276244871b1bSChris Mason int slot, int mid, int nritems) 2763be0e5c09SChris Mason { 2764be0e5c09SChris Mason int data_copy_size; 2765be0e5c09SChris Mason int rt_data_off; 2766be0e5c09SChris Mason int i; 2767d4dbff95SChris Mason int ret = 0; 2768aa5d6bedSChris Mason int wret; 2769d4dbff95SChris Mason struct btrfs_disk_key disk_key; 2770be0e5c09SChris Mason 27715f39d397SChris Mason nritems = nritems - mid; 27725f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 27735f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 27745f39d397SChris Mason 27755f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 27765f39d397SChris Mason btrfs_item_nr_offset(mid), 27775f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 27785f39d397SChris Mason 27795f39d397SChris Mason copy_extent_buffer(right, l, 2780d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 2781123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 2782123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 278374123bd7SChris Mason 27845f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 27855f39d397SChris Mason btrfs_item_end_nr(l, mid); 27865f39d397SChris Mason 27875f39d397SChris Mason for (i = 0; i < nritems; i++) { 27885f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 2789db94535dSChris Mason u32 ioff; 2790db94535dSChris Mason 2791db94535dSChris Mason if (!right->map_token) { 2792db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 2793db94535dSChris Mason sizeof(struct btrfs_item), 2794db94535dSChris Mason &right->map_token, &right->kaddr, 2795db94535dSChris Mason &right->map_start, &right->map_len, 2796db94535dSChris Mason KM_USER1); 2797db94535dSChris Mason } 2798db94535dSChris Mason 2799db94535dSChris Mason ioff = btrfs_item_offset(right, item); 28005f39d397SChris Mason btrfs_set_item_offset(right, item, ioff + rt_data_off); 28010783fcfcSChris Mason } 280274123bd7SChris Mason 2803db94535dSChris Mason if (right->map_token) { 2804db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 2805db94535dSChris Mason right->map_token = NULL; 2806db94535dSChris Mason } 2807db94535dSChris Mason 28085f39d397SChris Mason btrfs_set_header_nritems(l, mid); 2809aa5d6bedSChris Mason ret = 0; 28105f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 2811db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, right->start, 2812db94535dSChris Mason path->slots[1] + 1, 1); 2813aa5d6bedSChris Mason if (wret) 2814aa5d6bedSChris Mason ret = wret; 28155f39d397SChris Mason 28165f39d397SChris Mason btrfs_mark_buffer_dirty(right); 28175f39d397SChris Mason btrfs_mark_buffer_dirty(l); 2818eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 28195f39d397SChris Mason 2820be0e5c09SChris Mason if (mid <= slot) { 2821925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 28225f39d397SChris Mason free_extent_buffer(path->nodes[0]); 28235f39d397SChris Mason path->nodes[0] = right; 2824be0e5c09SChris Mason path->slots[0] -= mid; 2825be0e5c09SChris Mason path->slots[1] += 1; 2826925baeddSChris Mason } else { 2827925baeddSChris Mason btrfs_tree_unlock(right); 28285f39d397SChris Mason free_extent_buffer(right); 2829925baeddSChris Mason } 28305f39d397SChris Mason 2831eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 2832d4dbff95SChris Mason 283344871b1bSChris Mason return ret; 283444871b1bSChris Mason } 283544871b1bSChris Mason 283644871b1bSChris Mason /* 283744871b1bSChris Mason * split the path's leaf in two, making sure there is at least data_size 283844871b1bSChris Mason * available for the resulting leaf level of the path. 283944871b1bSChris Mason * 284044871b1bSChris Mason * returns 0 if all went well and < 0 on failure. 284144871b1bSChris Mason */ 284244871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 284344871b1bSChris Mason struct btrfs_root *root, 284444871b1bSChris Mason struct btrfs_key *ins_key, 284544871b1bSChris Mason struct btrfs_path *path, int data_size, 284644871b1bSChris Mason int extend) 284744871b1bSChris Mason { 28485d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 284944871b1bSChris Mason struct extent_buffer *l; 285044871b1bSChris Mason u32 nritems; 285144871b1bSChris Mason int mid; 285244871b1bSChris Mason int slot; 285344871b1bSChris Mason struct extent_buffer *right; 285444871b1bSChris Mason int ret = 0; 285544871b1bSChris Mason int wret; 28565d4f98a2SYan Zheng int split; 285744871b1bSChris Mason int num_doubles = 0; 285844871b1bSChris Mason 2859a5719521SYan, Zheng l = path->nodes[0]; 2860a5719521SYan, Zheng slot = path->slots[0]; 2861a5719521SYan, Zheng if (extend && data_size + btrfs_item_size_nr(l, slot) + 2862a5719521SYan, Zheng sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root)) 2863a5719521SYan, Zheng return -EOVERFLOW; 2864a5719521SYan, Zheng 286544871b1bSChris Mason /* first try to make some room by pushing left and right */ 2866b3612421SChris Mason if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) { 286744871b1bSChris Mason wret = push_leaf_right(trans, root, path, data_size, 0); 286844871b1bSChris Mason if (wret < 0) 286944871b1bSChris Mason return wret; 287044871b1bSChris Mason if (wret) { 287144871b1bSChris Mason wret = push_leaf_left(trans, root, path, data_size, 0); 287244871b1bSChris Mason if (wret < 0) 287344871b1bSChris Mason return wret; 287444871b1bSChris Mason } 287544871b1bSChris Mason l = path->nodes[0]; 287644871b1bSChris Mason 287744871b1bSChris Mason /* did the pushes work? */ 287844871b1bSChris Mason if (btrfs_leaf_free_space(root, l) >= data_size) 287944871b1bSChris Mason return 0; 288044871b1bSChris Mason } 288144871b1bSChris Mason 288244871b1bSChris Mason if (!path->nodes[1]) { 288344871b1bSChris Mason ret = insert_new_root(trans, root, path, 1); 288444871b1bSChris Mason if (ret) 288544871b1bSChris Mason return ret; 288644871b1bSChris Mason } 288744871b1bSChris Mason again: 28885d4f98a2SYan Zheng split = 1; 288944871b1bSChris Mason l = path->nodes[0]; 289044871b1bSChris Mason slot = path->slots[0]; 289144871b1bSChris Mason nritems = btrfs_header_nritems(l); 289244871b1bSChris Mason mid = (nritems + 1) / 2; 289344871b1bSChris Mason 28945d4f98a2SYan Zheng if (mid <= slot) { 28955d4f98a2SYan Zheng if (nritems == 1 || 28965d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + data_size > 28975d4f98a2SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 28985d4f98a2SYan Zheng if (slot >= nritems) { 28995d4f98a2SYan Zheng split = 0; 29005d4f98a2SYan Zheng } else { 29015d4f98a2SYan Zheng mid = slot; 29025d4f98a2SYan Zheng if (mid != nritems && 29035d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 29045d4f98a2SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 29055d4f98a2SYan Zheng split = 2; 29065d4f98a2SYan Zheng } 29075d4f98a2SYan Zheng } 29085d4f98a2SYan Zheng } 29095d4f98a2SYan Zheng } else { 29105d4f98a2SYan Zheng if (leaf_space_used(l, 0, mid) + data_size > 29115d4f98a2SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 29125d4f98a2SYan Zheng if (!extend && data_size && slot == 0) { 29135d4f98a2SYan Zheng split = 0; 29145d4f98a2SYan Zheng } else if ((extend || !data_size) && slot == 0) { 29155d4f98a2SYan Zheng mid = 1; 29165d4f98a2SYan Zheng } else { 29175d4f98a2SYan Zheng mid = slot; 29185d4f98a2SYan Zheng if (mid != nritems && 29195d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 29205d4f98a2SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 29215d4f98a2SYan Zheng split = 2 ; 29225d4f98a2SYan Zheng } 29235d4f98a2SYan Zheng } 29245d4f98a2SYan Zheng } 29255d4f98a2SYan Zheng } 29265d4f98a2SYan Zheng 29275d4f98a2SYan Zheng if (split == 0) 29285d4f98a2SYan Zheng btrfs_cpu_key_to_disk(&disk_key, ins_key); 29295d4f98a2SYan Zheng else 29305d4f98a2SYan Zheng btrfs_item_key(l, &disk_key, mid); 29315d4f98a2SYan Zheng 29325d4f98a2SYan Zheng right = btrfs_alloc_free_block(trans, root, root->leafsize, 0, 293344871b1bSChris Mason root->root_key.objectid, 29345d4f98a2SYan Zheng &disk_key, 0, l->start, 0); 293544871b1bSChris Mason if (IS_ERR(right)) { 293644871b1bSChris Mason BUG_ON(1); 293744871b1bSChris Mason return PTR_ERR(right); 293844871b1bSChris Mason } 293944871b1bSChris Mason 294044871b1bSChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 294144871b1bSChris Mason btrfs_set_header_bytenr(right, right->start); 294244871b1bSChris Mason btrfs_set_header_generation(right, trans->transid); 29435d4f98a2SYan Zheng btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV); 294444871b1bSChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 294544871b1bSChris Mason btrfs_set_header_level(right, 0); 294644871b1bSChris Mason write_extent_buffer(right, root->fs_info->fsid, 294744871b1bSChris Mason (unsigned long)btrfs_header_fsid(right), 294844871b1bSChris Mason BTRFS_FSID_SIZE); 294944871b1bSChris Mason 295044871b1bSChris Mason write_extent_buffer(right, root->fs_info->chunk_tree_uuid, 295144871b1bSChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(right), 295244871b1bSChris Mason BTRFS_UUID_SIZE); 295344871b1bSChris Mason 29545d4f98a2SYan Zheng if (split == 0) { 295544871b1bSChris Mason if (mid <= slot) { 295644871b1bSChris Mason btrfs_set_header_nritems(right, 0); 295744871b1bSChris Mason wret = insert_ptr(trans, root, path, 295844871b1bSChris Mason &disk_key, right->start, 295944871b1bSChris Mason path->slots[1] + 1, 1); 296044871b1bSChris Mason if (wret) 296144871b1bSChris Mason ret = wret; 296244871b1bSChris Mason 296344871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 296444871b1bSChris Mason free_extent_buffer(path->nodes[0]); 296544871b1bSChris Mason path->nodes[0] = right; 296644871b1bSChris Mason path->slots[0] = 0; 296744871b1bSChris Mason path->slots[1] += 1; 296844871b1bSChris Mason } else { 296944871b1bSChris Mason btrfs_set_header_nritems(right, 0); 297044871b1bSChris Mason wret = insert_ptr(trans, root, path, 297144871b1bSChris Mason &disk_key, 297244871b1bSChris Mason right->start, 297344871b1bSChris Mason path->slots[1], 1); 297444871b1bSChris Mason if (wret) 297544871b1bSChris Mason ret = wret; 297644871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 297744871b1bSChris Mason free_extent_buffer(path->nodes[0]); 297844871b1bSChris Mason path->nodes[0] = right; 297944871b1bSChris Mason path->slots[0] = 0; 298044871b1bSChris Mason if (path->slots[1] == 0) { 298144871b1bSChris Mason wret = fixup_low_keys(trans, root, 298244871b1bSChris Mason path, &disk_key, 1); 298344871b1bSChris Mason if (wret) 298444871b1bSChris Mason ret = wret; 298544871b1bSChris Mason } 29865d4f98a2SYan Zheng } 298744871b1bSChris Mason btrfs_mark_buffer_dirty(right); 298844871b1bSChris Mason return ret; 298944871b1bSChris Mason } 299044871b1bSChris Mason 299144871b1bSChris Mason ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems); 299244871b1bSChris Mason BUG_ON(ret); 299344871b1bSChris Mason 29945d4f98a2SYan Zheng if (split == 2) { 2995cc0c5538SChris Mason BUG_ON(num_doubles != 0); 2996cc0c5538SChris Mason num_doubles++; 2997cc0c5538SChris Mason goto again; 29983326d1b0SChris Mason } 299944871b1bSChris Mason 3000be0e5c09SChris Mason return ret; 3001be0e5c09SChris Mason } 3002be0e5c09SChris Mason 3003ad48fd75SYan, Zheng static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3004ad48fd75SYan, Zheng struct btrfs_root *root, 3005ad48fd75SYan, Zheng struct btrfs_path *path, int ins_len) 3006ad48fd75SYan, Zheng { 3007ad48fd75SYan, Zheng struct btrfs_key key; 3008ad48fd75SYan, Zheng struct extent_buffer *leaf; 3009ad48fd75SYan, Zheng struct btrfs_file_extent_item *fi; 3010ad48fd75SYan, Zheng u64 extent_len = 0; 3011ad48fd75SYan, Zheng u32 item_size; 3012ad48fd75SYan, Zheng int ret; 3013ad48fd75SYan, Zheng 3014ad48fd75SYan, Zheng leaf = path->nodes[0]; 3015ad48fd75SYan, Zheng btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 3016ad48fd75SYan, Zheng 3017ad48fd75SYan, Zheng BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY && 3018ad48fd75SYan, Zheng key.type != BTRFS_EXTENT_CSUM_KEY); 3019ad48fd75SYan, Zheng 3020ad48fd75SYan, Zheng if (btrfs_leaf_free_space(root, leaf) >= ins_len) 3021ad48fd75SYan, Zheng return 0; 3022ad48fd75SYan, Zheng 3023ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3024ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3025ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3026ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3027ad48fd75SYan, Zheng extent_len = btrfs_file_extent_num_bytes(leaf, fi); 3028ad48fd75SYan, Zheng } 3029ad48fd75SYan, Zheng btrfs_release_path(root, path); 3030ad48fd75SYan, Zheng 3031ad48fd75SYan, Zheng path->keep_locks = 1; 3032ad48fd75SYan, Zheng path->search_for_split = 1; 3033ad48fd75SYan, Zheng ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 3034ad48fd75SYan, Zheng path->search_for_split = 0; 3035ad48fd75SYan, Zheng if (ret < 0) 3036ad48fd75SYan, Zheng goto err; 3037ad48fd75SYan, Zheng 3038ad48fd75SYan, Zheng ret = -EAGAIN; 3039ad48fd75SYan, Zheng leaf = path->nodes[0]; 3040ad48fd75SYan, Zheng /* if our item isn't there or got smaller, return now */ 3041ad48fd75SYan, Zheng if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0])) 3042ad48fd75SYan, Zheng goto err; 3043ad48fd75SYan, Zheng 3044ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3045ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3046ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3047ad48fd75SYan, Zheng if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) 3048ad48fd75SYan, Zheng goto err; 3049ad48fd75SYan, Zheng } 3050ad48fd75SYan, Zheng 3051ad48fd75SYan, Zheng btrfs_set_path_blocking(path); 3052ad48fd75SYan, Zheng ret = split_leaf(trans, root, &key, path, ins_len, 1); 3053ad48fd75SYan, Zheng BUG_ON(ret); 3054ad48fd75SYan, Zheng 3055ad48fd75SYan, Zheng path->keep_locks = 0; 3056ad48fd75SYan, Zheng btrfs_unlock_up_safe(path, 1); 3057ad48fd75SYan, Zheng return 0; 3058ad48fd75SYan, Zheng err: 3059ad48fd75SYan, Zheng path->keep_locks = 0; 3060ad48fd75SYan, Zheng return ret; 3061ad48fd75SYan, Zheng } 3062ad48fd75SYan, Zheng 3063ad48fd75SYan, Zheng static noinline int split_item(struct btrfs_trans_handle *trans, 3064459931ecSChris Mason struct btrfs_root *root, 3065459931ecSChris Mason struct btrfs_path *path, 3066459931ecSChris Mason struct btrfs_key *new_key, 3067459931ecSChris Mason unsigned long split_offset) 3068459931ecSChris Mason { 3069459931ecSChris Mason struct extent_buffer *leaf; 3070459931ecSChris Mason struct btrfs_item *item; 3071459931ecSChris Mason struct btrfs_item *new_item; 3072459931ecSChris Mason int slot; 3073ad48fd75SYan, Zheng char *buf; 3074459931ecSChris Mason u32 nritems; 3075ad48fd75SYan, Zheng u32 item_size; 3076459931ecSChris Mason u32 orig_offset; 3077459931ecSChris Mason struct btrfs_disk_key disk_key; 3078459931ecSChris Mason 3079459931ecSChris Mason leaf = path->nodes[0]; 3080b9473439SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item)); 3081b9473439SChris Mason 3082b4ce94deSChris Mason btrfs_set_path_blocking(path); 3083b4ce94deSChris Mason 3084459931ecSChris Mason item = btrfs_item_nr(leaf, path->slots[0]); 3085459931ecSChris Mason orig_offset = btrfs_item_offset(leaf, item); 3086459931ecSChris Mason item_size = btrfs_item_size(leaf, item); 3087459931ecSChris Mason 3088459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 3089ad48fd75SYan, Zheng if (!buf) 3090ad48fd75SYan, Zheng return -ENOMEM; 3091ad48fd75SYan, Zheng 3092459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3093459931ecSChris Mason path->slots[0]), item_size); 3094ad48fd75SYan, Zheng 3095459931ecSChris Mason slot = path->slots[0] + 1; 3096459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 3097459931ecSChris Mason if (slot != nritems) { 3098459931ecSChris Mason /* shift the items */ 3099459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 3100459931ecSChris Mason btrfs_item_nr_offset(slot), 3101459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3102459931ecSChris Mason } 3103459931ecSChris Mason 3104459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 3105459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3106459931ecSChris Mason 3107459931ecSChris Mason new_item = btrfs_item_nr(leaf, slot); 3108459931ecSChris Mason 3109459931ecSChris Mason btrfs_set_item_offset(leaf, new_item, orig_offset); 3110459931ecSChris Mason btrfs_set_item_size(leaf, new_item, item_size - split_offset); 3111459931ecSChris Mason 3112459931ecSChris Mason btrfs_set_item_offset(leaf, item, 3113459931ecSChris Mason orig_offset + item_size - split_offset); 3114459931ecSChris Mason btrfs_set_item_size(leaf, item, split_offset); 3115459931ecSChris Mason 3116459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 3117459931ecSChris Mason 3118459931ecSChris Mason /* write the data for the start of the original item */ 3119459931ecSChris Mason write_extent_buffer(leaf, buf, 3120459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 3121459931ecSChris Mason split_offset); 3122459931ecSChris Mason 3123459931ecSChris Mason /* write the data for the new item */ 3124459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 3125459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 3126459931ecSChris Mason item_size - split_offset); 3127459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 3128459931ecSChris Mason 3129ad48fd75SYan, Zheng BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 3130459931ecSChris Mason kfree(buf); 3131ad48fd75SYan, Zheng return 0; 3132ad48fd75SYan, Zheng } 3133ad48fd75SYan, Zheng 3134ad48fd75SYan, Zheng /* 3135ad48fd75SYan, Zheng * This function splits a single item into two items, 3136ad48fd75SYan, Zheng * giving 'new_key' to the new item and splitting the 3137ad48fd75SYan, Zheng * old one at split_offset (from the start of the item). 3138ad48fd75SYan, Zheng * 3139ad48fd75SYan, Zheng * The path may be released by this operation. After 3140ad48fd75SYan, Zheng * the split, the path is pointing to the old item. The 3141ad48fd75SYan, Zheng * new item is going to be in the same node as the old one. 3142ad48fd75SYan, Zheng * 3143ad48fd75SYan, Zheng * Note, the item being split must be smaller enough to live alone on 3144ad48fd75SYan, Zheng * a tree block with room for one extra struct btrfs_item 3145ad48fd75SYan, Zheng * 3146ad48fd75SYan, Zheng * This allows us to split the item in place, keeping a lock on the 3147ad48fd75SYan, Zheng * leaf the entire time. 3148ad48fd75SYan, Zheng */ 3149ad48fd75SYan, Zheng int btrfs_split_item(struct btrfs_trans_handle *trans, 3150ad48fd75SYan, Zheng struct btrfs_root *root, 3151ad48fd75SYan, Zheng struct btrfs_path *path, 3152ad48fd75SYan, Zheng struct btrfs_key *new_key, 3153ad48fd75SYan, Zheng unsigned long split_offset) 3154ad48fd75SYan, Zheng { 3155ad48fd75SYan, Zheng int ret; 3156ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3157ad48fd75SYan, Zheng sizeof(struct btrfs_item)); 3158ad48fd75SYan, Zheng if (ret) 3159459931ecSChris Mason return ret; 3160ad48fd75SYan, Zheng 3161ad48fd75SYan, Zheng ret = split_item(trans, root, path, new_key, split_offset); 3162ad48fd75SYan, Zheng return ret; 3163ad48fd75SYan, Zheng } 3164ad48fd75SYan, Zheng 3165ad48fd75SYan, Zheng /* 3166ad48fd75SYan, Zheng * This function duplicate a item, giving 'new_key' to the new item. 3167ad48fd75SYan, Zheng * It guarantees both items live in the same tree leaf and the new item 3168ad48fd75SYan, Zheng * is contiguous with the original item. 3169ad48fd75SYan, Zheng * 3170ad48fd75SYan, Zheng * This allows us to split file extent in place, keeping a lock on the 3171ad48fd75SYan, Zheng * leaf the entire time. 3172ad48fd75SYan, Zheng */ 3173ad48fd75SYan, Zheng int btrfs_duplicate_item(struct btrfs_trans_handle *trans, 3174ad48fd75SYan, Zheng struct btrfs_root *root, 3175ad48fd75SYan, Zheng struct btrfs_path *path, 3176ad48fd75SYan, Zheng struct btrfs_key *new_key) 3177ad48fd75SYan, Zheng { 3178ad48fd75SYan, Zheng struct extent_buffer *leaf; 3179ad48fd75SYan, Zheng int ret; 3180ad48fd75SYan, Zheng u32 item_size; 3181ad48fd75SYan, Zheng 3182ad48fd75SYan, Zheng leaf = path->nodes[0]; 3183ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3184ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3185ad48fd75SYan, Zheng item_size + sizeof(struct btrfs_item)); 3186ad48fd75SYan, Zheng if (ret) 3187ad48fd75SYan, Zheng return ret; 3188ad48fd75SYan, Zheng 3189ad48fd75SYan, Zheng path->slots[0]++; 3190ad48fd75SYan, Zheng ret = setup_items_for_insert(trans, root, path, new_key, &item_size, 3191ad48fd75SYan, Zheng item_size, item_size + 3192ad48fd75SYan, Zheng sizeof(struct btrfs_item), 1); 3193ad48fd75SYan, Zheng BUG_ON(ret); 3194ad48fd75SYan, Zheng 3195ad48fd75SYan, Zheng leaf = path->nodes[0]; 3196ad48fd75SYan, Zheng memcpy_extent_buffer(leaf, 3197ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0]), 3198ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0] - 1), 3199ad48fd75SYan, Zheng item_size); 3200ad48fd75SYan, Zheng return 0; 3201459931ecSChris Mason } 3202459931ecSChris Mason 3203459931ecSChris Mason /* 3204d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 3205d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 3206d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 3207d352ac68SChris Mason * the front. 3208d352ac68SChris Mason */ 3209b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans, 3210b18c6685SChris Mason struct btrfs_root *root, 3211b18c6685SChris Mason struct btrfs_path *path, 3212179e29e4SChris Mason u32 new_size, int from_end) 3213b18c6685SChris Mason { 3214b18c6685SChris Mason int ret = 0; 3215b18c6685SChris Mason int slot; 3216b18c6685SChris Mason int slot_orig; 32175f39d397SChris Mason struct extent_buffer *leaf; 32185f39d397SChris Mason struct btrfs_item *item; 3219b18c6685SChris Mason u32 nritems; 3220b18c6685SChris Mason unsigned int data_end; 3221b18c6685SChris Mason unsigned int old_data_start; 3222b18c6685SChris Mason unsigned int old_size; 3223b18c6685SChris Mason unsigned int size_diff; 3224b18c6685SChris Mason int i; 3225b18c6685SChris Mason 3226b18c6685SChris Mason slot_orig = path->slots[0]; 32275f39d397SChris Mason leaf = path->nodes[0]; 3228179e29e4SChris Mason slot = path->slots[0]; 3229179e29e4SChris Mason 3230179e29e4SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 3231179e29e4SChris Mason if (old_size == new_size) 3232179e29e4SChris Mason return 0; 3233b18c6685SChris Mason 32345f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3235b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 3236b18c6685SChris Mason 32375f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 3238179e29e4SChris Mason 3239b18c6685SChris Mason size_diff = old_size - new_size; 3240b18c6685SChris Mason 3241b18c6685SChris Mason BUG_ON(slot < 0); 3242b18c6685SChris Mason BUG_ON(slot >= nritems); 3243b18c6685SChris Mason 3244b18c6685SChris Mason /* 3245b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3246b18c6685SChris Mason */ 3247b18c6685SChris Mason /* first correct the data pointers */ 3248b18c6685SChris Mason for (i = slot; i < nritems; i++) { 32495f39d397SChris Mason u32 ioff; 32505f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3251db94535dSChris Mason 3252db94535dSChris Mason if (!leaf->map_token) { 3253db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3254db94535dSChris Mason sizeof(struct btrfs_item), 3255db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3256db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3257db94535dSChris Mason KM_USER1); 3258db94535dSChris Mason } 3259db94535dSChris Mason 32605f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 32615f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + size_diff); 3262b18c6685SChris Mason } 3263db94535dSChris Mason 3264db94535dSChris Mason if (leaf->map_token) { 3265db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3266db94535dSChris Mason leaf->map_token = NULL; 3267db94535dSChris 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 3314b18c6685SChris Mason ret = 0; 33155f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 33165f39d397SChris Mason btrfs_print_leaf(root, leaf); 3317b18c6685SChris Mason BUG(); 33185f39d397SChris Mason } 3319b18c6685SChris Mason return ret; 3320b18c6685SChris Mason } 3321b18c6685SChris Mason 3322d352ac68SChris Mason /* 3323d352ac68SChris Mason * make the item pointed to by the path bigger, data_size is the new size. 3324d352ac68SChris Mason */ 33255f39d397SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans, 33265f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 33275f39d397SChris Mason u32 data_size) 33286567e837SChris Mason { 33296567e837SChris Mason int ret = 0; 33306567e837SChris Mason int slot; 33316567e837SChris Mason int slot_orig; 33325f39d397SChris Mason struct extent_buffer *leaf; 33335f39d397SChris Mason struct btrfs_item *item; 33346567e837SChris Mason u32 nritems; 33356567e837SChris Mason unsigned int data_end; 33366567e837SChris Mason unsigned int old_data; 33376567e837SChris Mason unsigned int old_size; 33386567e837SChris Mason int i; 33396567e837SChris Mason 33406567e837SChris Mason slot_orig = path->slots[0]; 33415f39d397SChris Mason leaf = path->nodes[0]; 33426567e837SChris Mason 33435f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 33446567e837SChris Mason data_end = leaf_data_end(root, leaf); 33456567e837SChris Mason 33465f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 33475f39d397SChris Mason btrfs_print_leaf(root, leaf); 33486567e837SChris Mason BUG(); 33495f39d397SChris Mason } 33506567e837SChris Mason slot = path->slots[0]; 33515f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 33526567e837SChris Mason 33536567e837SChris Mason BUG_ON(slot < 0); 33543326d1b0SChris Mason if (slot >= nritems) { 33553326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3356d397712bSChris Mason printk(KERN_CRIT "slot %d too large, nritems %d\n", 3357d397712bSChris Mason slot, nritems); 33583326d1b0SChris Mason BUG_ON(1); 33593326d1b0SChris Mason } 33606567e837SChris Mason 33616567e837SChris Mason /* 33626567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 33636567e837SChris Mason */ 33646567e837SChris Mason /* first correct the data pointers */ 33656567e837SChris Mason for (i = slot; i < nritems; i++) { 33665f39d397SChris Mason u32 ioff; 33675f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3368db94535dSChris Mason 3369db94535dSChris Mason if (!leaf->map_token) { 3370db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3371db94535dSChris Mason sizeof(struct btrfs_item), 3372db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3373db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3374db94535dSChris Mason KM_USER1); 3375db94535dSChris Mason } 33765f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 33775f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 33786567e837SChris Mason } 33795f39d397SChris Mason 3380db94535dSChris Mason if (leaf->map_token) { 3381db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3382db94535dSChris Mason leaf->map_token = NULL; 3383db94535dSChris Mason } 3384db94535dSChris Mason 33856567e837SChris Mason /* shift the data */ 33865f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 33876567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 33886567e837SChris Mason data_end, old_data - data_end); 33895f39d397SChris Mason 33906567e837SChris Mason data_end = old_data; 33915f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 33925f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 33935f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 33945f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 33956567e837SChris Mason 33966567e837SChris Mason ret = 0; 33975f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 33985f39d397SChris Mason btrfs_print_leaf(root, leaf); 33996567e837SChris Mason BUG(); 34005f39d397SChris Mason } 34016567e837SChris Mason return ret; 34026567e837SChris Mason } 34036567e837SChris Mason 340474123bd7SChris Mason /* 3405d352ac68SChris Mason * Given a key and some data, insert items into the tree. 340674123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 3407f3465ca4SJosef Bacik * Returns the number of keys that were inserted. 3408f3465ca4SJosef Bacik */ 3409f3465ca4SJosef Bacik int btrfs_insert_some_items(struct btrfs_trans_handle *trans, 3410f3465ca4SJosef Bacik struct btrfs_root *root, 3411f3465ca4SJosef Bacik struct btrfs_path *path, 3412f3465ca4SJosef Bacik struct btrfs_key *cpu_key, u32 *data_size, 3413f3465ca4SJosef Bacik int nr) 3414f3465ca4SJosef Bacik { 3415f3465ca4SJosef Bacik struct extent_buffer *leaf; 3416f3465ca4SJosef Bacik struct btrfs_item *item; 3417f3465ca4SJosef Bacik int ret = 0; 3418f3465ca4SJosef Bacik int slot; 3419f3465ca4SJosef Bacik int i; 3420f3465ca4SJosef Bacik u32 nritems; 3421f3465ca4SJosef Bacik u32 total_data = 0; 3422f3465ca4SJosef Bacik u32 total_size = 0; 3423f3465ca4SJosef Bacik unsigned int data_end; 3424f3465ca4SJosef Bacik struct btrfs_disk_key disk_key; 3425f3465ca4SJosef Bacik struct btrfs_key found_key; 3426f3465ca4SJosef Bacik 342787b29b20SYan Zheng for (i = 0; i < nr; i++) { 342887b29b20SYan Zheng if (total_size + data_size[i] + sizeof(struct btrfs_item) > 342987b29b20SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 343087b29b20SYan Zheng break; 343187b29b20SYan Zheng nr = i; 343287b29b20SYan Zheng } 3433f3465ca4SJosef Bacik total_data += data_size[i]; 343487b29b20SYan Zheng total_size += data_size[i] + sizeof(struct btrfs_item); 343587b29b20SYan Zheng } 343687b29b20SYan Zheng BUG_ON(nr == 0); 3437f3465ca4SJosef Bacik 3438f3465ca4SJosef Bacik ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 3439f3465ca4SJosef Bacik if (ret == 0) 3440f3465ca4SJosef Bacik return -EEXIST; 3441f3465ca4SJosef Bacik if (ret < 0) 3442f3465ca4SJosef Bacik goto out; 3443f3465ca4SJosef Bacik 3444f3465ca4SJosef Bacik leaf = path->nodes[0]; 3445f3465ca4SJosef Bacik 3446f3465ca4SJosef Bacik nritems = btrfs_header_nritems(leaf); 3447f3465ca4SJosef Bacik data_end = leaf_data_end(root, leaf); 3448f3465ca4SJosef Bacik 3449f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < total_size) { 3450f3465ca4SJosef Bacik for (i = nr; i >= 0; i--) { 3451f3465ca4SJosef Bacik total_data -= data_size[i]; 3452f3465ca4SJosef Bacik total_size -= data_size[i] + sizeof(struct btrfs_item); 3453f3465ca4SJosef Bacik if (total_size < btrfs_leaf_free_space(root, leaf)) 3454f3465ca4SJosef Bacik break; 3455f3465ca4SJosef Bacik } 3456f3465ca4SJosef Bacik nr = i; 3457f3465ca4SJosef Bacik } 3458f3465ca4SJosef Bacik 3459f3465ca4SJosef Bacik slot = path->slots[0]; 3460f3465ca4SJosef Bacik BUG_ON(slot < 0); 3461f3465ca4SJosef Bacik 3462f3465ca4SJosef Bacik if (slot != nritems) { 3463f3465ca4SJosef Bacik unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3464f3465ca4SJosef Bacik 3465f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot); 3466f3465ca4SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, slot); 3467f3465ca4SJosef Bacik 3468f3465ca4SJosef Bacik /* figure out how many keys we can insert in here */ 3469f3465ca4SJosef Bacik total_data = data_size[0]; 3470f3465ca4SJosef Bacik for (i = 1; i < nr; i++) { 34715d4f98a2SYan Zheng if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0) 3472f3465ca4SJosef Bacik break; 3473f3465ca4SJosef Bacik total_data += data_size[i]; 3474f3465ca4SJosef Bacik } 3475f3465ca4SJosef Bacik nr = i; 3476f3465ca4SJosef Bacik 3477f3465ca4SJosef Bacik if (old_data < data_end) { 3478f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3479d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 3480f3465ca4SJosef Bacik slot, old_data, data_end); 3481f3465ca4SJosef Bacik BUG_ON(1); 3482f3465ca4SJosef Bacik } 3483f3465ca4SJosef Bacik /* 3484f3465ca4SJosef Bacik * item0..itemN ... dataN.offset..dataN.size .. data0.size 3485f3465ca4SJosef Bacik */ 3486f3465ca4SJosef Bacik /* first correct the data pointers */ 3487f3465ca4SJosef Bacik WARN_ON(leaf->map_token); 3488f3465ca4SJosef Bacik for (i = slot; i < nritems; i++) { 3489f3465ca4SJosef Bacik u32 ioff; 3490f3465ca4SJosef Bacik 3491f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, i); 3492f3465ca4SJosef Bacik if (!leaf->map_token) { 3493f3465ca4SJosef Bacik map_extent_buffer(leaf, (unsigned long)item, 3494f3465ca4SJosef Bacik sizeof(struct btrfs_item), 3495f3465ca4SJosef Bacik &leaf->map_token, &leaf->kaddr, 3496f3465ca4SJosef Bacik &leaf->map_start, &leaf->map_len, 3497f3465ca4SJosef Bacik KM_USER1); 3498f3465ca4SJosef Bacik } 3499f3465ca4SJosef Bacik 3500f3465ca4SJosef Bacik ioff = btrfs_item_offset(leaf, item); 3501f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, ioff - total_data); 3502f3465ca4SJosef Bacik } 3503f3465ca4SJosef Bacik if (leaf->map_token) { 3504f3465ca4SJosef Bacik unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3505f3465ca4SJosef Bacik leaf->map_token = NULL; 3506f3465ca4SJosef Bacik } 3507f3465ca4SJosef Bacik 3508f3465ca4SJosef Bacik /* shift the items */ 3509f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 3510f3465ca4SJosef Bacik btrfs_item_nr_offset(slot), 3511f3465ca4SJosef Bacik (nritems - slot) * sizeof(struct btrfs_item)); 3512f3465ca4SJosef Bacik 3513f3465ca4SJosef Bacik /* shift the data */ 3514f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3515f3465ca4SJosef Bacik data_end - total_data, btrfs_leaf_data(leaf) + 3516f3465ca4SJosef Bacik data_end, old_data - data_end); 3517f3465ca4SJosef Bacik data_end = old_data; 3518f3465ca4SJosef Bacik } else { 3519f3465ca4SJosef Bacik /* 3520f3465ca4SJosef Bacik * this sucks but it has to be done, if we are inserting at 3521f3465ca4SJosef Bacik * the end of the leaf only insert 1 of the items, since we 3522f3465ca4SJosef Bacik * have no way of knowing whats on the next leaf and we'd have 3523f3465ca4SJosef Bacik * to drop our current locks to figure it out 3524f3465ca4SJosef Bacik */ 3525f3465ca4SJosef Bacik nr = 1; 3526f3465ca4SJosef Bacik } 3527f3465ca4SJosef Bacik 3528f3465ca4SJosef Bacik /* setup the item for the new data */ 3529f3465ca4SJosef Bacik for (i = 0; i < nr; i++) { 3530f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 3531f3465ca4SJosef Bacik btrfs_set_item_key(leaf, &disk_key, slot + i); 3532f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot + i); 3533f3465ca4SJosef Bacik btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 3534f3465ca4SJosef Bacik data_end -= data_size[i]; 3535f3465ca4SJosef Bacik btrfs_set_item_size(leaf, item, data_size[i]); 3536f3465ca4SJosef Bacik } 3537f3465ca4SJosef Bacik btrfs_set_header_nritems(leaf, nritems + nr); 3538f3465ca4SJosef Bacik btrfs_mark_buffer_dirty(leaf); 3539f3465ca4SJosef Bacik 3540f3465ca4SJosef Bacik ret = 0; 3541f3465ca4SJosef Bacik if (slot == 0) { 3542f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3543f3465ca4SJosef Bacik ret = fixup_low_keys(trans, root, path, &disk_key, 1); 3544f3465ca4SJosef Bacik } 3545f3465ca4SJosef Bacik 3546f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < 0) { 3547f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3548f3465ca4SJosef Bacik BUG(); 3549f3465ca4SJosef Bacik } 3550f3465ca4SJosef Bacik out: 3551f3465ca4SJosef Bacik if (!ret) 3552f3465ca4SJosef Bacik ret = nr; 3553f3465ca4SJosef Bacik return ret; 3554f3465ca4SJosef Bacik } 3555f3465ca4SJosef Bacik 3556f3465ca4SJosef Bacik /* 355744871b1bSChris Mason * this is a helper for btrfs_insert_empty_items, the main goal here is 355844871b1bSChris Mason * to save stack depth by doing the bulk of the work in a function 355944871b1bSChris Mason * that doesn't call btrfs_search_slot 356074123bd7SChris Mason */ 356144871b1bSChris Mason static noinline_for_stack int 356244871b1bSChris Mason setup_items_for_insert(struct btrfs_trans_handle *trans, 356344871b1bSChris Mason struct btrfs_root *root, struct btrfs_path *path, 35649c58309dSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 356544871b1bSChris Mason u32 total_data, u32 total_size, int nr) 3566be0e5c09SChris Mason { 35675f39d397SChris Mason struct btrfs_item *item; 35689c58309dSChris Mason int i; 35697518a238SChris Mason u32 nritems; 3570be0e5c09SChris Mason unsigned int data_end; 3571e2fa7227SChris Mason struct btrfs_disk_key disk_key; 357244871b1bSChris Mason int ret; 357344871b1bSChris Mason struct extent_buffer *leaf; 357444871b1bSChris Mason int slot; 3575e2fa7227SChris Mason 35765f39d397SChris Mason leaf = path->nodes[0]; 357744871b1bSChris Mason slot = path->slots[0]; 357874123bd7SChris Mason 35795f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3580123abc88SChris Mason data_end = leaf_data_end(root, leaf); 3581eb60ceacSChris Mason 3582f25956ccSChris Mason if (btrfs_leaf_free_space(root, leaf) < total_size) { 35833326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3584d397712bSChris Mason printk(KERN_CRIT "not enough freespace need %u have %d\n", 35859c58309dSChris Mason total_size, btrfs_leaf_free_space(root, leaf)); 3586be0e5c09SChris Mason BUG(); 3587d4dbff95SChris Mason } 35885f39d397SChris Mason 3589be0e5c09SChris Mason if (slot != nritems) { 35905f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3591be0e5c09SChris Mason 35925f39d397SChris Mason if (old_data < data_end) { 35935f39d397SChris Mason btrfs_print_leaf(root, leaf); 3594d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 35955f39d397SChris Mason slot, old_data, data_end); 35965f39d397SChris Mason BUG_ON(1); 35975f39d397SChris Mason } 3598be0e5c09SChris Mason /* 3599be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3600be0e5c09SChris Mason */ 3601be0e5c09SChris Mason /* first correct the data pointers */ 3602db94535dSChris Mason WARN_ON(leaf->map_token); 36030783fcfcSChris Mason for (i = slot; i < nritems; i++) { 36045f39d397SChris Mason u32 ioff; 3605db94535dSChris Mason 36065f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3607db94535dSChris Mason if (!leaf->map_token) { 3608db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3609db94535dSChris Mason sizeof(struct btrfs_item), 3610db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3611db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3612db94535dSChris Mason KM_USER1); 3613db94535dSChris Mason } 3614db94535dSChris Mason 36155f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 36169c58309dSChris Mason btrfs_set_item_offset(leaf, item, ioff - total_data); 36170783fcfcSChris Mason } 3618db94535dSChris Mason if (leaf->map_token) { 3619db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3620db94535dSChris Mason leaf->map_token = NULL; 3621db94535dSChris Mason } 3622be0e5c09SChris Mason 3623be0e5c09SChris Mason /* shift the items */ 36249c58309dSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 36255f39d397SChris Mason btrfs_item_nr_offset(slot), 36260783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3627be0e5c09SChris Mason 3628be0e5c09SChris Mason /* shift the data */ 36295f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 36309c58309dSChris Mason data_end - total_data, btrfs_leaf_data(leaf) + 3631be0e5c09SChris Mason data_end, old_data - data_end); 3632be0e5c09SChris Mason data_end = old_data; 3633be0e5c09SChris Mason } 36345f39d397SChris Mason 363562e2749eSChris Mason /* setup the item for the new data */ 36369c58309dSChris Mason for (i = 0; i < nr; i++) { 36379c58309dSChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 36389c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 36399c58309dSChris Mason item = btrfs_item_nr(leaf, slot + i); 36409c58309dSChris Mason btrfs_set_item_offset(leaf, item, data_end - data_size[i]); 36419c58309dSChris Mason data_end -= data_size[i]; 36429c58309dSChris Mason btrfs_set_item_size(leaf, item, data_size[i]); 36439c58309dSChris Mason } 364444871b1bSChris Mason 36459c58309dSChris Mason btrfs_set_header_nritems(leaf, nritems + nr); 3646aa5d6bedSChris Mason 3647aa5d6bedSChris Mason ret = 0; 36485a01a2e3SChris Mason if (slot == 0) { 364944871b1bSChris Mason struct btrfs_disk_key disk_key; 36505a01a2e3SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3651e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 36525a01a2e3SChris Mason } 3653b9473439SChris Mason btrfs_unlock_up_safe(path, 1); 3654b9473439SChris Mason btrfs_mark_buffer_dirty(leaf); 3655aa5d6bedSChris Mason 36565f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 36575f39d397SChris Mason btrfs_print_leaf(root, leaf); 3658be0e5c09SChris Mason BUG(); 36595f39d397SChris Mason } 366044871b1bSChris Mason return ret; 366144871b1bSChris Mason } 366244871b1bSChris Mason 366344871b1bSChris Mason /* 366444871b1bSChris Mason * Given a key and some data, insert items into the tree. 366544871b1bSChris Mason * This does all the path init required, making room in the tree if needed. 366644871b1bSChris Mason */ 366744871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 366844871b1bSChris Mason struct btrfs_root *root, 366944871b1bSChris Mason struct btrfs_path *path, 367044871b1bSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 367144871b1bSChris Mason int nr) 367244871b1bSChris Mason { 367344871b1bSChris Mason struct extent_buffer *leaf; 367444871b1bSChris Mason int ret = 0; 367544871b1bSChris Mason int slot; 367644871b1bSChris Mason int i; 367744871b1bSChris Mason u32 total_size = 0; 367844871b1bSChris Mason u32 total_data = 0; 367944871b1bSChris Mason 368044871b1bSChris Mason for (i = 0; i < nr; i++) 368144871b1bSChris Mason total_data += data_size[i]; 368244871b1bSChris Mason 368344871b1bSChris Mason total_size = total_data + (nr * sizeof(struct btrfs_item)); 368444871b1bSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 368544871b1bSChris Mason if (ret == 0) 368644871b1bSChris Mason return -EEXIST; 368744871b1bSChris Mason if (ret < 0) 368844871b1bSChris Mason goto out; 368944871b1bSChris Mason 369044871b1bSChris Mason leaf = path->nodes[0]; 369144871b1bSChris Mason slot = path->slots[0]; 369244871b1bSChris Mason BUG_ON(slot < 0); 369344871b1bSChris Mason 369444871b1bSChris Mason ret = setup_items_for_insert(trans, root, path, cpu_key, data_size, 369544871b1bSChris Mason total_data, total_size, nr); 369644871b1bSChris Mason 3697ed2ff2cbSChris Mason out: 369862e2749eSChris Mason return ret; 369962e2749eSChris Mason } 370062e2749eSChris Mason 370162e2749eSChris Mason /* 370262e2749eSChris Mason * Given a key and some data, insert an item into the tree. 370362e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 370462e2749eSChris Mason */ 3705e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 3706e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 3707e089f05cSChris Mason data_size) 370862e2749eSChris Mason { 370962e2749eSChris Mason int ret = 0; 37102c90e5d6SChris Mason struct btrfs_path *path; 37115f39d397SChris Mason struct extent_buffer *leaf; 37125f39d397SChris Mason unsigned long ptr; 371362e2749eSChris Mason 37142c90e5d6SChris Mason path = btrfs_alloc_path(); 37152c90e5d6SChris Mason BUG_ON(!path); 37162c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 371762e2749eSChris Mason if (!ret) { 37185f39d397SChris Mason leaf = path->nodes[0]; 37195f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 37205f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 37215f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 372262e2749eSChris Mason } 37232c90e5d6SChris Mason btrfs_free_path(path); 3724aa5d6bedSChris Mason return ret; 3725be0e5c09SChris Mason } 3726be0e5c09SChris Mason 372774123bd7SChris Mason /* 37285de08d7dSChris Mason * delete the pointer from a given node. 372974123bd7SChris Mason * 3730d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 3731d352ac68SChris Mason * empty a node. 373274123bd7SChris Mason */ 3733e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 3734e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 3735be0e5c09SChris Mason { 37365f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 37377518a238SChris Mason u32 nritems; 3738aa5d6bedSChris Mason int ret = 0; 3739bb803951SChris Mason int wret; 3740be0e5c09SChris Mason 37415f39d397SChris Mason nritems = btrfs_header_nritems(parent); 3742be0e5c09SChris Mason if (slot != nritems - 1) { 37435f39d397SChris Mason memmove_extent_buffer(parent, 37445f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 37455f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 3746d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 3747d6025579SChris Mason (nritems - slot - 1)); 3748be0e5c09SChris Mason } 37497518a238SChris Mason nritems--; 37505f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 37517518a238SChris Mason if (nritems == 0 && parent == root->node) { 37525f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 3753eb60ceacSChris Mason /* just turn the root into a leaf and break */ 37545f39d397SChris Mason btrfs_set_header_level(root->node, 0); 3755bb803951SChris Mason } else if (slot == 0) { 37565f39d397SChris Mason struct btrfs_disk_key disk_key; 37575f39d397SChris Mason 37585f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 37595f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); 37600f70abe2SChris Mason if (wret) 37610f70abe2SChris Mason ret = wret; 3762be0e5c09SChris Mason } 3763d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 3764aa5d6bedSChris Mason return ret; 3765be0e5c09SChris Mason } 3766be0e5c09SChris Mason 376774123bd7SChris Mason /* 3768323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 37695d4f98a2SYan Zheng * path->nodes[1]. 3770323ac95bSChris Mason * 3771323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 3772323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 3773323ac95bSChris Mason * 3774323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 3775323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 3776323ac95bSChris Mason */ 37775d4f98a2SYan Zheng static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans, 3778323ac95bSChris Mason struct btrfs_root *root, 37795d4f98a2SYan Zheng struct btrfs_path *path, 37805d4f98a2SYan Zheng struct extent_buffer *leaf) 3781323ac95bSChris Mason { 3782323ac95bSChris Mason int ret; 3783323ac95bSChris Mason 37845d4f98a2SYan Zheng WARN_ON(btrfs_header_generation(leaf) != trans->transid); 3785323ac95bSChris Mason ret = del_ptr(trans, root, path, 1, path->slots[1]); 3786323ac95bSChris Mason if (ret) 3787323ac95bSChris Mason return ret; 3788323ac95bSChris Mason 37894d081c41SChris Mason /* 37904d081c41SChris Mason * btrfs_free_extent is expensive, we want to make sure we 37914d081c41SChris Mason * aren't holding any locks when we call it 37924d081c41SChris Mason */ 37934d081c41SChris Mason btrfs_unlock_up_safe(path, 0); 37944d081c41SChris Mason 379586b9f2ecSYan, Zheng ret = btrfs_free_tree_block(trans, root, leaf->start, leaf->len, 379686b9f2ecSYan, Zheng 0, root->root_key.objectid, 0); 3797323ac95bSChris Mason return ret; 3798323ac95bSChris Mason } 3799323ac95bSChris Mason /* 380074123bd7SChris Mason * delete the item at the leaf level in path. If that empties 380174123bd7SChris Mason * the leaf, remove it from the tree 380274123bd7SChris Mason */ 380385e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 380485e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 3805be0e5c09SChris Mason { 38065f39d397SChris Mason struct extent_buffer *leaf; 38075f39d397SChris Mason struct btrfs_item *item; 380885e21bacSChris Mason int last_off; 380985e21bacSChris Mason int dsize = 0; 3810aa5d6bedSChris Mason int ret = 0; 3811aa5d6bedSChris Mason int wret; 381285e21bacSChris Mason int i; 38137518a238SChris Mason u32 nritems; 3814be0e5c09SChris Mason 38155f39d397SChris Mason leaf = path->nodes[0]; 381685e21bacSChris Mason last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); 381785e21bacSChris Mason 381885e21bacSChris Mason for (i = 0; i < nr; i++) 381985e21bacSChris Mason dsize += btrfs_item_size_nr(leaf, slot + i); 382085e21bacSChris Mason 38215f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3822be0e5c09SChris Mason 382385e21bacSChris Mason if (slot + nr != nritems) { 3824123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 38255f39d397SChris Mason 38265f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3827d6025579SChris Mason data_end + dsize, 3828123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 382985e21bacSChris Mason last_off - data_end); 38305f39d397SChris Mason 383185e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 38325f39d397SChris Mason u32 ioff; 3833db94535dSChris Mason 38345f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3835db94535dSChris Mason if (!leaf->map_token) { 3836db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 3837db94535dSChris Mason sizeof(struct btrfs_item), 3838db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 3839db94535dSChris Mason &leaf->map_start, &leaf->map_len, 3840db94535dSChris Mason KM_USER1); 3841db94535dSChris Mason } 38425f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 38435f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + dsize); 38440783fcfcSChris Mason } 3845db94535dSChris Mason 3846db94535dSChris Mason if (leaf->map_token) { 3847db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 3848db94535dSChris Mason leaf->map_token = NULL; 3849db94535dSChris Mason } 3850db94535dSChris Mason 38515f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 385285e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 38530783fcfcSChris Mason sizeof(struct btrfs_item) * 385485e21bacSChris Mason (nritems - slot - nr)); 3855be0e5c09SChris Mason } 385685e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 385785e21bacSChris Mason nritems -= nr; 38585f39d397SChris Mason 385974123bd7SChris Mason /* delete the leaf if we've emptied it */ 38607518a238SChris Mason if (nritems == 0) { 38615f39d397SChris Mason if (leaf == root->node) { 38625f39d397SChris Mason btrfs_set_header_level(leaf, 0); 38639a8dd150SChris Mason } else { 38645d4f98a2SYan Zheng ret = btrfs_del_leaf(trans, root, path, leaf); 3865323ac95bSChris Mason BUG_ON(ret); 38669a8dd150SChris Mason } 3867be0e5c09SChris Mason } else { 38687518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 3869aa5d6bedSChris Mason if (slot == 0) { 38705f39d397SChris Mason struct btrfs_disk_key disk_key; 38715f39d397SChris Mason 38725f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 3873e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 38745f39d397SChris Mason &disk_key, 1); 3875aa5d6bedSChris Mason if (wret) 3876aa5d6bedSChris Mason ret = wret; 3877aa5d6bedSChris Mason } 3878aa5d6bedSChris Mason 387974123bd7SChris Mason /* delete the leaf if it is mostly empty */ 3880d717aa1dSYan Zheng if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 3881be0e5c09SChris Mason /* push_leaf_left fixes the path. 3882be0e5c09SChris Mason * make sure the path still points to our leaf 3883be0e5c09SChris Mason * for possible call to del_ptr below 3884be0e5c09SChris Mason */ 38854920c9acSChris Mason slot = path->slots[1]; 38865f39d397SChris Mason extent_buffer_get(leaf); 38875f39d397SChris Mason 3888b9473439SChris Mason btrfs_set_path_blocking(path); 388985e21bacSChris Mason wret = push_leaf_left(trans, root, path, 1, 1); 389054aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3891aa5d6bedSChris Mason ret = wret; 38925f39d397SChris Mason 38935f39d397SChris Mason if (path->nodes[0] == leaf && 38945f39d397SChris Mason btrfs_header_nritems(leaf)) { 389585e21bacSChris Mason wret = push_leaf_right(trans, root, path, 1, 1); 389654aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 3897aa5d6bedSChris Mason ret = wret; 3898aa5d6bedSChris Mason } 38995f39d397SChris Mason 39005f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 3901323ac95bSChris Mason path->slots[1] = slot; 39025d4f98a2SYan Zheng ret = btrfs_del_leaf(trans, root, path, leaf); 3903323ac95bSChris Mason BUG_ON(ret); 39045f39d397SChris Mason free_extent_buffer(leaf); 39055de08d7dSChris Mason } else { 3906925baeddSChris Mason /* if we're still in the path, make sure 3907925baeddSChris Mason * we're dirty. Otherwise, one of the 3908925baeddSChris Mason * push_leaf functions must have already 3909925baeddSChris Mason * dirtied this buffer 3910925baeddSChris Mason */ 3911925baeddSChris Mason if (path->nodes[0] == leaf) 39125f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 39135f39d397SChris Mason free_extent_buffer(leaf); 3914be0e5c09SChris Mason } 3915d5719762SChris Mason } else { 39165f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3917be0e5c09SChris Mason } 39189a8dd150SChris Mason } 3919aa5d6bedSChris Mason return ret; 39209a8dd150SChris Mason } 39219a8dd150SChris Mason 392297571fd0SChris Mason /* 3923925baeddSChris Mason * search the tree again to find a leaf with lesser keys 39247bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 39257bb86316SChris Mason * returns < 0 on io errors. 3926d352ac68SChris Mason * 3927d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 3928d352ac68SChris Mason * time you call it. 39297bb86316SChris Mason */ 39307bb86316SChris Mason int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 39317bb86316SChris Mason { 3932925baeddSChris Mason struct btrfs_key key; 3933925baeddSChris Mason struct btrfs_disk_key found_key; 3934925baeddSChris Mason int ret; 39357bb86316SChris Mason 3936925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 3937925baeddSChris Mason 3938925baeddSChris Mason if (key.offset > 0) 3939925baeddSChris Mason key.offset--; 3940925baeddSChris Mason else if (key.type > 0) 3941925baeddSChris Mason key.type--; 3942925baeddSChris Mason else if (key.objectid > 0) 3943925baeddSChris Mason key.objectid--; 3944925baeddSChris Mason else 39457bb86316SChris Mason return 1; 39467bb86316SChris Mason 3947925baeddSChris Mason btrfs_release_path(root, path); 3948925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 3949925baeddSChris Mason if (ret < 0) 3950925baeddSChris Mason return ret; 3951925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 3952925baeddSChris Mason ret = comp_keys(&found_key, &key); 3953925baeddSChris Mason if (ret < 0) 39547bb86316SChris Mason return 0; 3955925baeddSChris Mason return 1; 39567bb86316SChris Mason } 39577bb86316SChris Mason 39583f157a2fSChris Mason /* 39593f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 39603f157a2fSChris Mason * for nodes or leaves that are either in cache or have a minimum 3961d352ac68SChris Mason * transaction id. This is used by the btree defrag code, and tree logging 39623f157a2fSChris Mason * 39633f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 39643f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 39653f157a2fSChris Mason * key and get a writable path. 39663f157a2fSChris Mason * 39673f157a2fSChris Mason * This does lock as it descends, and path->keep_locks should be set 39683f157a2fSChris Mason * to 1 by the caller. 39693f157a2fSChris Mason * 39703f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 39713f157a2fSChris Mason * of the tree. 39723f157a2fSChris Mason * 3973d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 3974d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 3975d352ac68SChris Mason * skipped over (without reading them). 3976d352ac68SChris Mason * 39773f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 39783f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 39793f157a2fSChris Mason */ 39803f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 3981e02119d5SChris Mason struct btrfs_key *max_key, 39823f157a2fSChris Mason struct btrfs_path *path, int cache_only, 39833f157a2fSChris Mason u64 min_trans) 39843f157a2fSChris Mason { 39853f157a2fSChris Mason struct extent_buffer *cur; 39863f157a2fSChris Mason struct btrfs_key found_key; 39873f157a2fSChris Mason int slot; 39889652480bSYan int sret; 39893f157a2fSChris Mason u32 nritems; 39903f157a2fSChris Mason int level; 39913f157a2fSChris Mason int ret = 1; 39923f157a2fSChris Mason 3993934d375bSChris Mason WARN_ON(!path->keep_locks); 39943f157a2fSChris Mason again: 39953f157a2fSChris Mason cur = btrfs_lock_root_node(root); 39963f157a2fSChris Mason level = btrfs_header_level(cur); 3997e02119d5SChris Mason WARN_ON(path->nodes[level]); 39983f157a2fSChris Mason path->nodes[level] = cur; 39993f157a2fSChris Mason path->locks[level] = 1; 40003f157a2fSChris Mason 40013f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 40023f157a2fSChris Mason ret = 1; 40033f157a2fSChris Mason goto out; 40043f157a2fSChris Mason } 40053f157a2fSChris Mason while (1) { 40063f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 40073f157a2fSChris Mason level = btrfs_header_level(cur); 40089652480bSYan sret = bin_search(cur, min_key, level, &slot); 40093f157a2fSChris Mason 4010323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 4011323ac95bSChris Mason if (level == path->lowest_level) { 4012e02119d5SChris Mason if (slot >= nritems) 4013e02119d5SChris Mason goto find_next_key; 40143f157a2fSChris Mason ret = 0; 40153f157a2fSChris Mason path->slots[level] = slot; 40163f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 40173f157a2fSChris Mason goto out; 40183f157a2fSChris Mason } 40199652480bSYan if (sret && slot > 0) 40209652480bSYan slot--; 40213f157a2fSChris Mason /* 40223f157a2fSChris Mason * check this node pointer against the cache_only and 40233f157a2fSChris Mason * min_trans parameters. If it isn't in cache or is too 40243f157a2fSChris Mason * old, skip to the next one. 40253f157a2fSChris Mason */ 40263f157a2fSChris Mason while (slot < nritems) { 40273f157a2fSChris Mason u64 blockptr; 40283f157a2fSChris Mason u64 gen; 40293f157a2fSChris Mason struct extent_buffer *tmp; 4030e02119d5SChris Mason struct btrfs_disk_key disk_key; 4031e02119d5SChris Mason 40323f157a2fSChris Mason blockptr = btrfs_node_blockptr(cur, slot); 40333f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 40343f157a2fSChris Mason if (gen < min_trans) { 40353f157a2fSChris Mason slot++; 40363f157a2fSChris Mason continue; 40373f157a2fSChris Mason } 40383f157a2fSChris Mason if (!cache_only) 40393f157a2fSChris Mason break; 40403f157a2fSChris Mason 4041e02119d5SChris Mason if (max_key) { 4042e02119d5SChris Mason btrfs_node_key(cur, &disk_key, slot); 4043e02119d5SChris Mason if (comp_keys(&disk_key, max_key) >= 0) { 4044e02119d5SChris Mason ret = 1; 4045e02119d5SChris Mason goto out; 4046e02119d5SChris Mason } 4047e02119d5SChris Mason } 4048e02119d5SChris Mason 40493f157a2fSChris Mason tmp = btrfs_find_tree_block(root, blockptr, 40503f157a2fSChris Mason btrfs_level_size(root, level - 1)); 40513f157a2fSChris Mason 40523f157a2fSChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen)) { 40533f157a2fSChris Mason free_extent_buffer(tmp); 40543f157a2fSChris Mason break; 40553f157a2fSChris Mason } 40563f157a2fSChris Mason if (tmp) 40573f157a2fSChris Mason free_extent_buffer(tmp); 40583f157a2fSChris Mason slot++; 40593f157a2fSChris Mason } 4060e02119d5SChris Mason find_next_key: 40613f157a2fSChris Mason /* 40623f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 40633f157a2fSChris Mason * and find another one 40643f157a2fSChris Mason */ 40653f157a2fSChris Mason if (slot >= nritems) { 4066e02119d5SChris Mason path->slots[level] = slot; 4067b4ce94deSChris Mason btrfs_set_path_blocking(path); 4068e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 40693f157a2fSChris Mason cache_only, min_trans); 4070e02119d5SChris Mason if (sret == 0) { 40713f157a2fSChris Mason btrfs_release_path(root, path); 40723f157a2fSChris Mason goto again; 40733f157a2fSChris Mason } else { 40743f157a2fSChris Mason goto out; 40753f157a2fSChris Mason } 40763f157a2fSChris Mason } 40773f157a2fSChris Mason /* save our key for returning back */ 40783f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 40793f157a2fSChris Mason path->slots[level] = slot; 40803f157a2fSChris Mason if (level == path->lowest_level) { 40813f157a2fSChris Mason ret = 0; 40823f157a2fSChris Mason unlock_up(path, level, 1); 40833f157a2fSChris Mason goto out; 40843f157a2fSChris Mason } 4085b4ce94deSChris Mason btrfs_set_path_blocking(path); 40863f157a2fSChris Mason cur = read_node_slot(root, cur, slot); 40873f157a2fSChris Mason 40883f157a2fSChris Mason btrfs_tree_lock(cur); 4089b4ce94deSChris Mason 40903f157a2fSChris Mason path->locks[level - 1] = 1; 40913f157a2fSChris Mason path->nodes[level - 1] = cur; 40923f157a2fSChris Mason unlock_up(path, level, 1); 40934008c04aSChris Mason btrfs_clear_path_blocking(path, NULL); 40943f157a2fSChris Mason } 40953f157a2fSChris Mason out: 40963f157a2fSChris Mason if (ret == 0) 40973f157a2fSChris Mason memcpy(min_key, &found_key, sizeof(found_key)); 4098b4ce94deSChris Mason btrfs_set_path_blocking(path); 40993f157a2fSChris Mason return ret; 41003f157a2fSChris Mason } 41013f157a2fSChris Mason 41023f157a2fSChris Mason /* 41033f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 41043f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 41053f157a2fSChris Mason * tree based on the current path and the cache_only and min_trans 41063f157a2fSChris Mason * parameters. 41073f157a2fSChris Mason * 41083f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 41093f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 41103f157a2fSChris Mason * 41113f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 41123f157a2fSChris Mason * calling this function. 41133f157a2fSChris Mason */ 4114e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 411533c66f43SYan Zheng struct btrfs_key *key, int level, 41163f157a2fSChris Mason int cache_only, u64 min_trans) 4117e7a84565SChris Mason { 4118e7a84565SChris Mason int slot; 4119e7a84565SChris Mason struct extent_buffer *c; 4120e7a84565SChris Mason 4121934d375bSChris Mason WARN_ON(!path->keep_locks); 4122e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 4123e7a84565SChris Mason if (!path->nodes[level]) 4124e7a84565SChris Mason return 1; 4125e7a84565SChris Mason 4126e7a84565SChris Mason slot = path->slots[level] + 1; 4127e7a84565SChris Mason c = path->nodes[level]; 41283f157a2fSChris Mason next: 4129e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 413033c66f43SYan Zheng int ret; 413133c66f43SYan Zheng int orig_lowest; 413233c66f43SYan Zheng struct btrfs_key cur_key; 413333c66f43SYan Zheng if (level + 1 >= BTRFS_MAX_LEVEL || 413433c66f43SYan Zheng !path->nodes[level + 1]) 4135e7a84565SChris Mason return 1; 413633c66f43SYan Zheng 413733c66f43SYan Zheng if (path->locks[level + 1]) { 413833c66f43SYan Zheng level++; 4139e7a84565SChris Mason continue; 4140e7a84565SChris Mason } 414133c66f43SYan Zheng 414233c66f43SYan Zheng slot = btrfs_header_nritems(c) - 1; 414333c66f43SYan Zheng if (level == 0) 414433c66f43SYan Zheng btrfs_item_key_to_cpu(c, &cur_key, slot); 414533c66f43SYan Zheng else 414633c66f43SYan Zheng btrfs_node_key_to_cpu(c, &cur_key, slot); 414733c66f43SYan Zheng 414833c66f43SYan Zheng orig_lowest = path->lowest_level; 414933c66f43SYan Zheng btrfs_release_path(root, path); 415033c66f43SYan Zheng path->lowest_level = level; 415133c66f43SYan Zheng ret = btrfs_search_slot(NULL, root, &cur_key, path, 415233c66f43SYan Zheng 0, 0); 415333c66f43SYan Zheng path->lowest_level = orig_lowest; 415433c66f43SYan Zheng if (ret < 0) 415533c66f43SYan Zheng return ret; 415633c66f43SYan Zheng 415733c66f43SYan Zheng c = path->nodes[level]; 415833c66f43SYan Zheng slot = path->slots[level]; 415933c66f43SYan Zheng if (ret == 0) 416033c66f43SYan Zheng slot++; 416133c66f43SYan Zheng goto next; 416233c66f43SYan Zheng } 416333c66f43SYan Zheng 4164e7a84565SChris Mason if (level == 0) 4165e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 41663f157a2fSChris Mason else { 41673f157a2fSChris Mason u64 blockptr = btrfs_node_blockptr(c, slot); 41683f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 41693f157a2fSChris Mason 41703f157a2fSChris Mason if (cache_only) { 41713f157a2fSChris Mason struct extent_buffer *cur; 41723f157a2fSChris Mason cur = btrfs_find_tree_block(root, blockptr, 41733f157a2fSChris Mason btrfs_level_size(root, level - 1)); 41743f157a2fSChris Mason if (!cur || !btrfs_buffer_uptodate(cur, gen)) { 41753f157a2fSChris Mason slot++; 41763f157a2fSChris Mason if (cur) 41773f157a2fSChris Mason free_extent_buffer(cur); 41783f157a2fSChris Mason goto next; 41793f157a2fSChris Mason } 41803f157a2fSChris Mason free_extent_buffer(cur); 41813f157a2fSChris Mason } 41823f157a2fSChris Mason if (gen < min_trans) { 41833f157a2fSChris Mason slot++; 41843f157a2fSChris Mason goto next; 41853f157a2fSChris Mason } 4186e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 41873f157a2fSChris Mason } 4188e7a84565SChris Mason return 0; 4189e7a84565SChris Mason } 4190e7a84565SChris Mason return 1; 4191e7a84565SChris Mason } 4192e7a84565SChris Mason 41937bb86316SChris Mason /* 4194925baeddSChris Mason * search the tree again to find a leaf with greater keys 41950f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 41960f70abe2SChris Mason * returns < 0 on io errors. 419797571fd0SChris Mason */ 4198234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 4199d97e63b6SChris Mason { 4200d97e63b6SChris Mason int slot; 42018e73f275SChris Mason int level; 42025f39d397SChris Mason struct extent_buffer *c; 42038e73f275SChris Mason struct extent_buffer *next; 4204925baeddSChris Mason struct btrfs_key key; 4205925baeddSChris Mason u32 nritems; 4206925baeddSChris Mason int ret; 42078e73f275SChris Mason int old_spinning = path->leave_spinning; 42088e73f275SChris Mason int force_blocking = 0; 4209925baeddSChris Mason 4210925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4211d397712bSChris Mason if (nritems == 0) 4212925baeddSChris Mason return 1; 4213925baeddSChris Mason 42148e73f275SChris Mason /* 42158e73f275SChris Mason * we take the blocks in an order that upsets lockdep. Using 42168e73f275SChris Mason * blocking mode is the only way around it. 42178e73f275SChris Mason */ 42188e73f275SChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 42198e73f275SChris Mason force_blocking = 1; 42208e73f275SChris Mason #endif 4221925baeddSChris Mason 42228e73f275SChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 42238e73f275SChris Mason again: 42248e73f275SChris Mason level = 1; 42258e73f275SChris Mason next = NULL; 4226925baeddSChris Mason btrfs_release_path(root, path); 42278e73f275SChris Mason 4228a2135011SChris Mason path->keep_locks = 1; 42298e73f275SChris Mason 42308e73f275SChris Mason if (!force_blocking) 42318e73f275SChris Mason path->leave_spinning = 1; 42328e73f275SChris Mason 4233925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4234925baeddSChris Mason path->keep_locks = 0; 4235925baeddSChris Mason 4236925baeddSChris Mason if (ret < 0) 4237925baeddSChris Mason return ret; 4238925baeddSChris Mason 4239a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4240168fd7d2SChris Mason /* 4241168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 4242168fd7d2SChris Mason * could have added more items next to the key that used to be 4243168fd7d2SChris Mason * at the very end of the block. So, check again here and 4244168fd7d2SChris Mason * advance the path if there are now more items available. 4245168fd7d2SChris Mason */ 4246a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 4247e457afecSYan Zheng if (ret == 0) 4248168fd7d2SChris Mason path->slots[0]++; 42498e73f275SChris Mason ret = 0; 4250925baeddSChris Mason goto done; 4251925baeddSChris Mason } 4252d97e63b6SChris Mason 4253234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 42548e73f275SChris Mason if (!path->nodes[level]) { 42558e73f275SChris Mason ret = 1; 42568e73f275SChris Mason goto done; 42578e73f275SChris Mason } 42585f39d397SChris Mason 4259d97e63b6SChris Mason slot = path->slots[level] + 1; 4260d97e63b6SChris Mason c = path->nodes[level]; 42615f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 4262d97e63b6SChris Mason level++; 42638e73f275SChris Mason if (level == BTRFS_MAX_LEVEL) { 42648e73f275SChris Mason ret = 1; 42658e73f275SChris Mason goto done; 42668e73f275SChris Mason } 4267d97e63b6SChris Mason continue; 4268d97e63b6SChris Mason } 42695f39d397SChris Mason 4270925baeddSChris Mason if (next) { 4271925baeddSChris Mason btrfs_tree_unlock(next); 42725f39d397SChris Mason free_extent_buffer(next); 4273925baeddSChris Mason } 42745f39d397SChris Mason 42758e73f275SChris Mason next = c; 42768e73f275SChris Mason ret = read_block_for_search(NULL, root, path, &next, level, 42778e73f275SChris Mason slot, &key); 42788e73f275SChris Mason if (ret == -EAGAIN) 42798e73f275SChris Mason goto again; 42805f39d397SChris Mason 428176a05b35SChris Mason if (ret < 0) { 428276a05b35SChris Mason btrfs_release_path(root, path); 428376a05b35SChris Mason goto done; 428476a05b35SChris Mason } 428576a05b35SChris Mason 42865cd57b2cSChris Mason if (!path->skip_locking) { 42878e73f275SChris Mason ret = btrfs_try_spin_lock(next); 42888e73f275SChris Mason if (!ret) { 42898e73f275SChris Mason btrfs_set_path_blocking(path); 4290925baeddSChris Mason btrfs_tree_lock(next); 42918e73f275SChris Mason if (!force_blocking) 42928e73f275SChris Mason btrfs_clear_path_blocking(path, next); 42938e73f275SChris Mason } 42948e73f275SChris Mason if (force_blocking) 4295b4ce94deSChris Mason btrfs_set_lock_blocking(next); 42965cd57b2cSChris Mason } 4297d97e63b6SChris Mason break; 4298d97e63b6SChris Mason } 4299d97e63b6SChris Mason path->slots[level] = slot; 4300d97e63b6SChris Mason while (1) { 4301d97e63b6SChris Mason level--; 4302d97e63b6SChris Mason c = path->nodes[level]; 4303925baeddSChris Mason if (path->locks[level]) 4304925baeddSChris Mason btrfs_tree_unlock(c); 43058e73f275SChris Mason 43065f39d397SChris Mason free_extent_buffer(c); 4307d97e63b6SChris Mason path->nodes[level] = next; 4308d97e63b6SChris Mason path->slots[level] = 0; 4309a74a4b97SChris Mason if (!path->skip_locking) 4310925baeddSChris Mason path->locks[level] = 1; 43118e73f275SChris Mason 4312d97e63b6SChris Mason if (!level) 4313d97e63b6SChris Mason break; 4314b4ce94deSChris Mason 43158e73f275SChris Mason ret = read_block_for_search(NULL, root, path, &next, level, 43168e73f275SChris Mason 0, &key); 43178e73f275SChris Mason if (ret == -EAGAIN) 43188e73f275SChris Mason goto again; 43198e73f275SChris Mason 432076a05b35SChris Mason if (ret < 0) { 432176a05b35SChris Mason btrfs_release_path(root, path); 432276a05b35SChris Mason goto done; 432376a05b35SChris Mason } 432476a05b35SChris Mason 43255cd57b2cSChris Mason if (!path->skip_locking) { 4326b9447ef8SChris Mason btrfs_assert_tree_locked(path->nodes[level]); 43278e73f275SChris Mason ret = btrfs_try_spin_lock(next); 43288e73f275SChris Mason if (!ret) { 43298e73f275SChris Mason btrfs_set_path_blocking(path); 4330925baeddSChris Mason btrfs_tree_lock(next); 43318e73f275SChris Mason if (!force_blocking) 43328e73f275SChris Mason btrfs_clear_path_blocking(path, next); 43338e73f275SChris Mason } 43348e73f275SChris Mason if (force_blocking) 4335b4ce94deSChris Mason btrfs_set_lock_blocking(next); 4336d97e63b6SChris Mason } 43375cd57b2cSChris Mason } 43388e73f275SChris Mason ret = 0; 4339925baeddSChris Mason done: 4340925baeddSChris Mason unlock_up(path, 0, 1); 43418e73f275SChris Mason path->leave_spinning = old_spinning; 43428e73f275SChris Mason if (!old_spinning) 43438e73f275SChris Mason btrfs_set_path_blocking(path); 43448e73f275SChris Mason 43458e73f275SChris Mason return ret; 4346d97e63b6SChris Mason } 43470b86a832SChris Mason 43483f157a2fSChris Mason /* 43493f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 43503f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 43513f157a2fSChris Mason * 43523f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 43533f157a2fSChris Mason */ 43540b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 43550b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 43560b86a832SChris Mason int type) 43570b86a832SChris Mason { 43580b86a832SChris Mason struct btrfs_key found_key; 43590b86a832SChris Mason struct extent_buffer *leaf; 4360e02119d5SChris Mason u32 nritems; 43610b86a832SChris Mason int ret; 43620b86a832SChris Mason 43630b86a832SChris Mason while (1) { 43640b86a832SChris Mason if (path->slots[0] == 0) { 4365b4ce94deSChris Mason btrfs_set_path_blocking(path); 43660b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 43670b86a832SChris Mason if (ret != 0) 43680b86a832SChris Mason return ret; 43690b86a832SChris Mason } else { 43700b86a832SChris Mason path->slots[0]--; 43710b86a832SChris Mason } 43720b86a832SChris Mason leaf = path->nodes[0]; 4373e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 4374e02119d5SChris Mason if (nritems == 0) 4375e02119d5SChris Mason return 1; 4376e02119d5SChris Mason if (path->slots[0] == nritems) 4377e02119d5SChris Mason path->slots[0]--; 4378e02119d5SChris Mason 43790b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4380e02119d5SChris Mason if (found_key.objectid < min_objectid) 4381e02119d5SChris Mason break; 43820a4eefbbSYan Zheng if (found_key.type == type) 43830a4eefbbSYan Zheng return 0; 4384e02119d5SChris Mason if (found_key.objectid == min_objectid && 4385e02119d5SChris Mason found_key.type < type) 4386e02119d5SChris Mason break; 43870b86a832SChris Mason } 43880b86a832SChris Mason return 1; 43890b86a832SChris Mason } 4390