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> 21bd989ba3SJan Schmidt #include <linux/rbtree.h> 22eb60ceacSChris Mason #include "ctree.h" 23eb60ceacSChris Mason #include "disk-io.h" 247f5c1516SChris Mason #include "transaction.h" 255f39d397SChris Mason #include "print-tree.h" 26925baeddSChris Mason #include "locking.h" 279a8dd150SChris Mason 28e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 29e089f05cSChris Mason *root, struct btrfs_path *path, int level); 30e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 31d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 32cc0c5538SChris Mason struct btrfs_path *path, int data_size, int extend); 335f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 345f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 35971a1f66SChris Mason struct extent_buffer *src, int empty); 365f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 375f39d397SChris Mason struct btrfs_root *root, 385f39d397SChris Mason struct extent_buffer *dst_buf, 395f39d397SChris Mason struct extent_buffer *src_buf); 40143bede5SJeff Mahoney static void del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 41f3ea38daSJan Schmidt struct btrfs_path *path, int level, int slot, 42f3ea38daSJan Schmidt int tree_mod_log); 43f230475eSJan Schmidt static void tree_mod_log_free_eb(struct btrfs_fs_info *fs_info, 44f230475eSJan Schmidt struct extent_buffer *eb); 45f230475eSJan Schmidt struct extent_buffer *read_old_tree_block(struct btrfs_root *root, u64 bytenr, 46f230475eSJan Schmidt u32 blocksize, u64 parent_transid, 47f230475eSJan Schmidt u64 time_seq); 48f230475eSJan Schmidt struct extent_buffer *btrfs_find_old_tree_block(struct btrfs_root *root, 49f230475eSJan Schmidt u64 bytenr, u32 blocksize, 50f230475eSJan Schmidt u64 time_seq); 51d97e63b6SChris Mason 522c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 532c90e5d6SChris Mason { 54df24a2b9SChris Mason struct btrfs_path *path; 55e00f7308SJeff Mahoney path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 56df24a2b9SChris Mason return path; 572c90e5d6SChris Mason } 582c90e5d6SChris Mason 59b4ce94deSChris Mason /* 60b4ce94deSChris Mason * set all locked nodes in the path to blocking locks. This should 61b4ce94deSChris Mason * be done before scheduling 62b4ce94deSChris Mason */ 63b4ce94deSChris Mason noinline void btrfs_set_path_blocking(struct btrfs_path *p) 64b4ce94deSChris Mason { 65b4ce94deSChris Mason int i; 66b4ce94deSChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 67bd681513SChris Mason if (!p->nodes[i] || !p->locks[i]) 68bd681513SChris Mason continue; 69bd681513SChris Mason btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]); 70bd681513SChris Mason if (p->locks[i] == BTRFS_READ_LOCK) 71bd681513SChris Mason p->locks[i] = BTRFS_READ_LOCK_BLOCKING; 72bd681513SChris Mason else if (p->locks[i] == BTRFS_WRITE_LOCK) 73bd681513SChris Mason p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING; 74b4ce94deSChris Mason } 75b4ce94deSChris Mason } 76b4ce94deSChris Mason 77b4ce94deSChris Mason /* 78b4ce94deSChris Mason * reset all the locked nodes in the patch to spinning locks. 794008c04aSChris Mason * 804008c04aSChris Mason * held is used to keep lockdep happy, when lockdep is enabled 814008c04aSChris Mason * we set held to a blocking lock before we go around and 824008c04aSChris Mason * retake all the spinlocks in the path. You can safely use NULL 834008c04aSChris Mason * for held 84b4ce94deSChris Mason */ 854008c04aSChris Mason noinline void btrfs_clear_path_blocking(struct btrfs_path *p, 86bd681513SChris Mason struct extent_buffer *held, int held_rw) 87b4ce94deSChris Mason { 88b4ce94deSChris Mason int i; 894008c04aSChris Mason 904008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 914008c04aSChris Mason /* lockdep really cares that we take all of these spinlocks 924008c04aSChris Mason * in the right order. If any of the locks in the path are not 934008c04aSChris Mason * currently blocking, it is going to complain. So, make really 944008c04aSChris Mason * really sure by forcing the path to blocking before we clear 954008c04aSChris Mason * the path blocking. 964008c04aSChris Mason */ 97bd681513SChris Mason if (held) { 98bd681513SChris Mason btrfs_set_lock_blocking_rw(held, held_rw); 99bd681513SChris Mason if (held_rw == BTRFS_WRITE_LOCK) 100bd681513SChris Mason held_rw = BTRFS_WRITE_LOCK_BLOCKING; 101bd681513SChris Mason else if (held_rw == BTRFS_READ_LOCK) 102bd681513SChris Mason held_rw = BTRFS_READ_LOCK_BLOCKING; 103bd681513SChris Mason } 1044008c04aSChris Mason btrfs_set_path_blocking(p); 1054008c04aSChris Mason #endif 1064008c04aSChris Mason 1074008c04aSChris Mason for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) { 108bd681513SChris Mason if (p->nodes[i] && p->locks[i]) { 109bd681513SChris Mason btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]); 110bd681513SChris Mason if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING) 111bd681513SChris Mason p->locks[i] = BTRFS_WRITE_LOCK; 112bd681513SChris Mason else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING) 113bd681513SChris Mason p->locks[i] = BTRFS_READ_LOCK; 114bd681513SChris Mason } 115b4ce94deSChris Mason } 1164008c04aSChris Mason 1174008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC 1184008c04aSChris Mason if (held) 119bd681513SChris Mason btrfs_clear_lock_blocking_rw(held, held_rw); 1204008c04aSChris Mason #endif 121b4ce94deSChris Mason } 122b4ce94deSChris Mason 123d352ac68SChris Mason /* this also releases the path */ 1242c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 1252c90e5d6SChris Mason { 126ff175d57SJesper Juhl if (!p) 127ff175d57SJesper Juhl return; 128b3b4aa74SDavid Sterba btrfs_release_path(p); 1292c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 1302c90e5d6SChris Mason } 1312c90e5d6SChris Mason 132d352ac68SChris Mason /* 133d352ac68SChris Mason * path release drops references on the extent buffers in the path 134d352ac68SChris Mason * and it drops any locks held by this path 135d352ac68SChris Mason * 136d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 137d352ac68SChris Mason */ 138b3b4aa74SDavid Sterba noinline void btrfs_release_path(struct btrfs_path *p) 139eb60ceacSChris Mason { 140eb60ceacSChris Mason int i; 141a2135011SChris Mason 142234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 1433f157a2fSChris Mason p->slots[i] = 0; 144eb60ceacSChris Mason if (!p->nodes[i]) 145925baeddSChris Mason continue; 146925baeddSChris Mason if (p->locks[i]) { 147bd681513SChris Mason btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]); 148925baeddSChris Mason p->locks[i] = 0; 149925baeddSChris Mason } 1505f39d397SChris Mason free_extent_buffer(p->nodes[i]); 1513f157a2fSChris Mason p->nodes[i] = NULL; 152eb60ceacSChris Mason } 153eb60ceacSChris Mason } 154eb60ceacSChris Mason 155d352ac68SChris Mason /* 156d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 157d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 158d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 159d352ac68SChris Mason * looping required. 160d352ac68SChris Mason * 161d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 162d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 163d352ac68SChris Mason * at any time because there are no locks held. 164d352ac68SChris Mason */ 165925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 166925baeddSChris Mason { 167925baeddSChris Mason struct extent_buffer *eb; 168240f62c8SChris Mason 1693083ee2eSJosef Bacik while (1) { 170240f62c8SChris Mason rcu_read_lock(); 171240f62c8SChris Mason eb = rcu_dereference(root->node); 1723083ee2eSJosef Bacik 1733083ee2eSJosef Bacik /* 1743083ee2eSJosef Bacik * RCU really hurts here, we could free up the root node because 1753083ee2eSJosef Bacik * it was cow'ed but we may not get the new root node yet so do 1763083ee2eSJosef Bacik * the inc_not_zero dance and if it doesn't work then 1773083ee2eSJosef Bacik * synchronize_rcu and try again. 1783083ee2eSJosef Bacik */ 1793083ee2eSJosef Bacik if (atomic_inc_not_zero(&eb->refs)) { 180240f62c8SChris Mason rcu_read_unlock(); 1813083ee2eSJosef Bacik break; 1823083ee2eSJosef Bacik } 1833083ee2eSJosef Bacik rcu_read_unlock(); 1843083ee2eSJosef Bacik synchronize_rcu(); 1853083ee2eSJosef Bacik } 186925baeddSChris Mason return eb; 187925baeddSChris Mason } 188925baeddSChris Mason 189d352ac68SChris Mason /* loop around taking references on and locking the root node of the 190d352ac68SChris Mason * tree until you end up with a lock on the root. A locked buffer 191d352ac68SChris Mason * is returned, with a reference held. 192d352ac68SChris Mason */ 193925baeddSChris Mason struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root) 194925baeddSChris Mason { 195925baeddSChris Mason struct extent_buffer *eb; 196925baeddSChris Mason 197925baeddSChris Mason while (1) { 198925baeddSChris Mason eb = btrfs_root_node(root); 199925baeddSChris Mason btrfs_tree_lock(eb); 200240f62c8SChris Mason if (eb == root->node) 201925baeddSChris Mason break; 202925baeddSChris Mason btrfs_tree_unlock(eb); 203925baeddSChris Mason free_extent_buffer(eb); 204925baeddSChris Mason } 205925baeddSChris Mason return eb; 206925baeddSChris Mason } 207925baeddSChris Mason 208bd681513SChris Mason /* loop around taking references on and locking the root node of the 209bd681513SChris Mason * tree until you end up with a lock on the root. A locked buffer 210bd681513SChris Mason * is returned, with a reference held. 211bd681513SChris Mason */ 212bd681513SChris Mason struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root) 213bd681513SChris Mason { 214bd681513SChris Mason struct extent_buffer *eb; 215bd681513SChris Mason 216bd681513SChris Mason while (1) { 217bd681513SChris Mason eb = btrfs_root_node(root); 218bd681513SChris Mason btrfs_tree_read_lock(eb); 219bd681513SChris Mason if (eb == root->node) 220bd681513SChris Mason break; 221bd681513SChris Mason btrfs_tree_read_unlock(eb); 222bd681513SChris Mason free_extent_buffer(eb); 223bd681513SChris Mason } 224bd681513SChris Mason return eb; 225bd681513SChris Mason } 226bd681513SChris Mason 227d352ac68SChris Mason /* cowonly root (everything not a reference counted cow subvolume), just get 228d352ac68SChris Mason * put onto a simple dirty list. transaction.c walks this to make sure they 229d352ac68SChris Mason * get properly updated on disk. 230d352ac68SChris Mason */ 2310b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 2320b86a832SChris Mason { 233e5846fc6SChris Mason spin_lock(&root->fs_info->trans_lock); 2340b86a832SChris Mason if (root->track_dirty && list_empty(&root->dirty_list)) { 2350b86a832SChris Mason list_add(&root->dirty_list, 2360b86a832SChris Mason &root->fs_info->dirty_cowonly_roots); 2370b86a832SChris Mason } 238e5846fc6SChris Mason spin_unlock(&root->fs_info->trans_lock); 2390b86a832SChris Mason } 2400b86a832SChris Mason 241d352ac68SChris Mason /* 242d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 243d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 244d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 245d352ac68SChris Mason */ 246be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 247be20aa9dSChris Mason struct btrfs_root *root, 248be20aa9dSChris Mason struct extent_buffer *buf, 249be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 250be20aa9dSChris Mason { 251be20aa9dSChris Mason struct extent_buffer *cow; 252be20aa9dSChris Mason int ret = 0; 253be20aa9dSChris Mason int level; 2545d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 255be20aa9dSChris Mason 256be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != 257be20aa9dSChris Mason root->fs_info->running_transaction->transid); 258be20aa9dSChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 259be20aa9dSChris Mason 260be20aa9dSChris Mason level = btrfs_header_level(buf); 2615d4f98a2SYan Zheng if (level == 0) 2625d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 2635d4f98a2SYan Zheng else 2645d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 26531840ae1SZheng Yan 2665d4f98a2SYan Zheng cow = btrfs_alloc_free_block(trans, root, buf->len, 0, 2675d4f98a2SYan Zheng new_root_objectid, &disk_key, level, 2685581a51aSJan Schmidt buf->start, 0); 2695d4f98a2SYan Zheng if (IS_ERR(cow)) 270be20aa9dSChris Mason return PTR_ERR(cow); 271be20aa9dSChris Mason 272be20aa9dSChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 273be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 274be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 2755d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 2765d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 2775d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 2785d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 2795d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 2805d4f98a2SYan Zheng else 281be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 282be20aa9dSChris Mason 2832b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 2842b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 2852b82032cSYan Zheng BTRFS_FSID_SIZE); 2862b82032cSYan Zheng 287be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 2885d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 28966d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 2905d4f98a2SYan Zheng else 29166d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 0, 1); 2924aec2b52SChris Mason 293be20aa9dSChris Mason if (ret) 294be20aa9dSChris Mason return ret; 295be20aa9dSChris Mason 296be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 297be20aa9dSChris Mason *cow_ret = cow; 298be20aa9dSChris Mason return 0; 299be20aa9dSChris Mason } 300be20aa9dSChris Mason 301bd989ba3SJan Schmidt enum mod_log_op { 302bd989ba3SJan Schmidt MOD_LOG_KEY_REPLACE, 303bd989ba3SJan Schmidt MOD_LOG_KEY_ADD, 304bd989ba3SJan Schmidt MOD_LOG_KEY_REMOVE, 305bd989ba3SJan Schmidt MOD_LOG_KEY_REMOVE_WHILE_FREEING, 306bd989ba3SJan Schmidt MOD_LOG_KEY_REMOVE_WHILE_MOVING, 307bd989ba3SJan Schmidt MOD_LOG_MOVE_KEYS, 308bd989ba3SJan Schmidt MOD_LOG_ROOT_REPLACE, 309bd989ba3SJan Schmidt }; 310bd989ba3SJan Schmidt 311bd989ba3SJan Schmidt struct tree_mod_move { 312bd989ba3SJan Schmidt int dst_slot; 313bd989ba3SJan Schmidt int nr_items; 314bd989ba3SJan Schmidt }; 315bd989ba3SJan Schmidt 316bd989ba3SJan Schmidt struct tree_mod_root { 317bd989ba3SJan Schmidt u64 logical; 318bd989ba3SJan Schmidt u8 level; 319bd989ba3SJan Schmidt }; 320bd989ba3SJan Schmidt 321bd989ba3SJan Schmidt struct tree_mod_elem { 322bd989ba3SJan Schmidt struct rb_node node; 323bd989ba3SJan Schmidt u64 index; /* shifted logical */ 324bd989ba3SJan Schmidt struct seq_list elem; 325bd989ba3SJan Schmidt enum mod_log_op op; 326bd989ba3SJan Schmidt 327bd989ba3SJan Schmidt /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */ 328bd989ba3SJan Schmidt int slot; 329bd989ba3SJan Schmidt 330bd989ba3SJan Schmidt /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */ 331bd989ba3SJan Schmidt u64 generation; 332bd989ba3SJan Schmidt 333bd989ba3SJan Schmidt /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */ 334bd989ba3SJan Schmidt struct btrfs_disk_key key; 335bd989ba3SJan Schmidt u64 blockptr; 336bd989ba3SJan Schmidt 337bd989ba3SJan Schmidt /* this is used for op == MOD_LOG_MOVE_KEYS */ 338bd989ba3SJan Schmidt struct tree_mod_move move; 339bd989ba3SJan Schmidt 340bd989ba3SJan Schmidt /* this is used for op == MOD_LOG_ROOT_REPLACE */ 341bd989ba3SJan Schmidt struct tree_mod_root old_root; 342bd989ba3SJan Schmidt }; 343bd989ba3SJan Schmidt 344bd989ba3SJan Schmidt static inline void 345bd989ba3SJan Schmidt __get_tree_mod_seq(struct btrfs_fs_info *fs_info, struct seq_list *elem) 346bd989ba3SJan Schmidt { 347bd989ba3SJan Schmidt elem->seq = atomic_inc_return(&fs_info->tree_mod_seq); 348bd989ba3SJan Schmidt list_add_tail(&elem->list, &fs_info->tree_mod_seq_list); 349bd989ba3SJan Schmidt } 350bd989ba3SJan Schmidt 351bd989ba3SJan Schmidt void btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info, 352bd989ba3SJan Schmidt struct seq_list *elem) 353bd989ba3SJan Schmidt { 354bd989ba3SJan Schmidt elem->flags = 1; 355bd989ba3SJan Schmidt spin_lock(&fs_info->tree_mod_seq_lock); 356bd989ba3SJan Schmidt __get_tree_mod_seq(fs_info, elem); 357bd989ba3SJan Schmidt spin_unlock(&fs_info->tree_mod_seq_lock); 358bd989ba3SJan Schmidt } 359bd989ba3SJan Schmidt 360bd989ba3SJan Schmidt void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info, 361bd989ba3SJan Schmidt struct seq_list *elem) 362bd989ba3SJan Schmidt { 363bd989ba3SJan Schmidt struct rb_root *tm_root; 364bd989ba3SJan Schmidt struct rb_node *node; 365bd989ba3SJan Schmidt struct rb_node *next; 366bd989ba3SJan Schmidt struct seq_list *cur_elem; 367bd989ba3SJan Schmidt struct tree_mod_elem *tm; 368bd989ba3SJan Schmidt u64 min_seq = (u64)-1; 369bd989ba3SJan Schmidt u64 seq_putting = elem->seq; 370bd989ba3SJan Schmidt 371bd989ba3SJan Schmidt if (!seq_putting) 372bd989ba3SJan Schmidt return; 373bd989ba3SJan Schmidt 374bd989ba3SJan Schmidt BUG_ON(!(elem->flags & 1)); 375bd989ba3SJan Schmidt spin_lock(&fs_info->tree_mod_seq_lock); 376bd989ba3SJan Schmidt list_del(&elem->list); 377bd989ba3SJan Schmidt 378bd989ba3SJan Schmidt list_for_each_entry(cur_elem, &fs_info->tree_mod_seq_list, list) { 379bd989ba3SJan Schmidt if ((cur_elem->flags & 1) && cur_elem->seq < min_seq) { 380bd989ba3SJan Schmidt if (seq_putting > cur_elem->seq) { 381bd989ba3SJan Schmidt /* 382bd989ba3SJan Schmidt * blocker with lower sequence number exists, we 383bd989ba3SJan Schmidt * cannot remove anything from the log 384bd989ba3SJan Schmidt */ 385bd989ba3SJan Schmidt goto out; 386bd989ba3SJan Schmidt } 387bd989ba3SJan Schmidt min_seq = cur_elem->seq; 388bd989ba3SJan Schmidt } 389bd989ba3SJan Schmidt } 390bd989ba3SJan Schmidt 391bd989ba3SJan Schmidt /* 392bd989ba3SJan Schmidt * anything that's lower than the lowest existing (read: blocked) 393bd989ba3SJan Schmidt * sequence number can be removed from the tree. 394bd989ba3SJan Schmidt */ 395bd989ba3SJan Schmidt write_lock(&fs_info->tree_mod_log_lock); 396bd989ba3SJan Schmidt tm_root = &fs_info->tree_mod_log; 397bd989ba3SJan Schmidt for (node = rb_first(tm_root); node; node = next) { 398bd989ba3SJan Schmidt next = rb_next(node); 399bd989ba3SJan Schmidt tm = container_of(node, struct tree_mod_elem, node); 400bd989ba3SJan Schmidt if (tm->elem.seq > min_seq) 401bd989ba3SJan Schmidt continue; 402bd989ba3SJan Schmidt rb_erase(node, tm_root); 403bd989ba3SJan Schmidt list_del(&tm->elem.list); 404bd989ba3SJan Schmidt kfree(tm); 405bd989ba3SJan Schmidt } 406bd989ba3SJan Schmidt write_unlock(&fs_info->tree_mod_log_lock); 407bd989ba3SJan Schmidt out: 408bd989ba3SJan Schmidt spin_unlock(&fs_info->tree_mod_seq_lock); 409bd989ba3SJan Schmidt } 410bd989ba3SJan Schmidt 411bd989ba3SJan Schmidt /* 412bd989ba3SJan Schmidt * key order of the log: 413bd989ba3SJan Schmidt * index -> sequence 414bd989ba3SJan Schmidt * 415bd989ba3SJan Schmidt * the index is the shifted logical of the *new* root node for root replace 416bd989ba3SJan Schmidt * operations, or the shifted logical of the affected block for all other 417bd989ba3SJan Schmidt * operations. 418bd989ba3SJan Schmidt */ 419bd989ba3SJan Schmidt static noinline int 420bd989ba3SJan Schmidt __tree_mod_log_insert(struct btrfs_fs_info *fs_info, struct tree_mod_elem *tm) 421bd989ba3SJan Schmidt { 422bd989ba3SJan Schmidt struct rb_root *tm_root; 423bd989ba3SJan Schmidt struct rb_node **new; 424bd989ba3SJan Schmidt struct rb_node *parent = NULL; 425bd989ba3SJan Schmidt struct tree_mod_elem *cur; 426bd989ba3SJan Schmidt int ret = 0; 427bd989ba3SJan Schmidt 428bd989ba3SJan Schmidt BUG_ON(!tm || !tm->elem.seq); 429bd989ba3SJan Schmidt 430bd989ba3SJan Schmidt write_lock(&fs_info->tree_mod_log_lock); 431bd989ba3SJan Schmidt tm_root = &fs_info->tree_mod_log; 432bd989ba3SJan Schmidt new = &tm_root->rb_node; 433bd989ba3SJan Schmidt while (*new) { 434bd989ba3SJan Schmidt cur = container_of(*new, struct tree_mod_elem, node); 435bd989ba3SJan Schmidt parent = *new; 436bd989ba3SJan Schmidt if (cur->index < tm->index) 437bd989ba3SJan Schmidt new = &((*new)->rb_left); 438bd989ba3SJan Schmidt else if (cur->index > tm->index) 439bd989ba3SJan Schmidt new = &((*new)->rb_right); 440bd989ba3SJan Schmidt else if (cur->elem.seq < tm->elem.seq) 441bd989ba3SJan Schmidt new = &((*new)->rb_left); 442bd989ba3SJan Schmidt else if (cur->elem.seq > tm->elem.seq) 443bd989ba3SJan Schmidt new = &((*new)->rb_right); 444bd989ba3SJan Schmidt else { 445bd989ba3SJan Schmidt kfree(tm); 446bd989ba3SJan Schmidt ret = -EEXIST; 447bd989ba3SJan Schmidt goto unlock; 448bd989ba3SJan Schmidt } 449bd989ba3SJan Schmidt } 450bd989ba3SJan Schmidt 451bd989ba3SJan Schmidt rb_link_node(&tm->node, parent, new); 452bd989ba3SJan Schmidt rb_insert_color(&tm->node, tm_root); 453bd989ba3SJan Schmidt unlock: 454bd989ba3SJan Schmidt write_unlock(&fs_info->tree_mod_log_lock); 455bd989ba3SJan Schmidt return ret; 456bd989ba3SJan Schmidt } 457bd989ba3SJan Schmidt 458bd989ba3SJan Schmidt int tree_mod_alloc(struct btrfs_fs_info *fs_info, gfp_t flags, 459bd989ba3SJan Schmidt struct tree_mod_elem **tm_ret) 460bd989ba3SJan Schmidt { 461bd989ba3SJan Schmidt struct tree_mod_elem *tm; 462bd989ba3SJan Schmidt u64 seq = 0; 463bd989ba3SJan Schmidt 464bd989ba3SJan Schmidt smp_mb(); 465bd989ba3SJan Schmidt if (list_empty(&fs_info->tree_mod_seq_list)) 466bd989ba3SJan Schmidt return 0; 467bd989ba3SJan Schmidt 468bd989ba3SJan Schmidt tm = *tm_ret = kzalloc(sizeof(*tm), flags); 469bd989ba3SJan Schmidt if (!tm) 470bd989ba3SJan Schmidt return -ENOMEM; 471bd989ba3SJan Schmidt 472bd989ba3SJan Schmidt __get_tree_mod_seq(fs_info, &tm->elem); 473bd989ba3SJan Schmidt seq = tm->elem.seq; 474bd989ba3SJan Schmidt tm->elem.flags = 0; 475bd989ba3SJan Schmidt 476bd989ba3SJan Schmidt return seq; 477bd989ba3SJan Schmidt } 478bd989ba3SJan Schmidt 479bd989ba3SJan Schmidt static noinline int 480bd989ba3SJan Schmidt tree_mod_log_insert_key_mask(struct btrfs_fs_info *fs_info, 481bd989ba3SJan Schmidt struct extent_buffer *eb, int slot, 482bd989ba3SJan Schmidt enum mod_log_op op, gfp_t flags) 483bd989ba3SJan Schmidt { 484bd989ba3SJan Schmidt struct tree_mod_elem *tm; 485bd989ba3SJan Schmidt int ret; 486bd989ba3SJan Schmidt 487bd989ba3SJan Schmidt ret = tree_mod_alloc(fs_info, flags, &tm); 488bd989ba3SJan Schmidt if (ret <= 0) 489bd989ba3SJan Schmidt return ret; 490bd989ba3SJan Schmidt 491bd989ba3SJan Schmidt tm->index = eb->start >> PAGE_CACHE_SHIFT; 492bd989ba3SJan Schmidt if (op != MOD_LOG_KEY_ADD) { 493bd989ba3SJan Schmidt btrfs_node_key(eb, &tm->key, slot); 494bd989ba3SJan Schmidt tm->blockptr = btrfs_node_blockptr(eb, slot); 495bd989ba3SJan Schmidt } 496bd989ba3SJan Schmidt tm->op = op; 497bd989ba3SJan Schmidt tm->slot = slot; 498bd989ba3SJan Schmidt tm->generation = btrfs_node_ptr_generation(eb, slot); 499bd989ba3SJan Schmidt 500bd989ba3SJan Schmidt return __tree_mod_log_insert(fs_info, tm); 501bd989ba3SJan Schmidt } 502bd989ba3SJan Schmidt 503bd989ba3SJan Schmidt static noinline int 504bd989ba3SJan Schmidt tree_mod_log_insert_key(struct btrfs_fs_info *fs_info, struct extent_buffer *eb, 505bd989ba3SJan Schmidt int slot, enum mod_log_op op) 506bd989ba3SJan Schmidt { 507bd989ba3SJan Schmidt return tree_mod_log_insert_key_mask(fs_info, eb, slot, op, GFP_NOFS); 508bd989ba3SJan Schmidt } 509bd989ba3SJan Schmidt 510bd989ba3SJan Schmidt static noinline int 511bd989ba3SJan Schmidt tree_mod_log_insert_move(struct btrfs_fs_info *fs_info, 512bd989ba3SJan Schmidt struct extent_buffer *eb, int dst_slot, int src_slot, 513bd989ba3SJan Schmidt int nr_items, gfp_t flags) 514bd989ba3SJan Schmidt { 515bd989ba3SJan Schmidt struct tree_mod_elem *tm; 516bd989ba3SJan Schmidt int ret; 517bd989ba3SJan Schmidt int i; 518bd989ba3SJan Schmidt 519bd989ba3SJan Schmidt ret = tree_mod_alloc(fs_info, flags, &tm); 520bd989ba3SJan Schmidt if (ret <= 0) 521bd989ba3SJan Schmidt return ret; 522bd989ba3SJan Schmidt 523bd989ba3SJan Schmidt for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) { 524bd989ba3SJan Schmidt ret = tree_mod_log_insert_key(fs_info, eb, i + dst_slot, 525bd989ba3SJan Schmidt MOD_LOG_KEY_REMOVE_WHILE_MOVING); 526bd989ba3SJan Schmidt BUG_ON(ret < 0); 527bd989ba3SJan Schmidt } 528bd989ba3SJan Schmidt 529bd989ba3SJan Schmidt tm->index = eb->start >> PAGE_CACHE_SHIFT; 530bd989ba3SJan Schmidt tm->slot = src_slot; 531bd989ba3SJan Schmidt tm->move.dst_slot = dst_slot; 532bd989ba3SJan Schmidt tm->move.nr_items = nr_items; 533bd989ba3SJan Schmidt tm->op = MOD_LOG_MOVE_KEYS; 534bd989ba3SJan Schmidt 535bd989ba3SJan Schmidt return __tree_mod_log_insert(fs_info, tm); 536bd989ba3SJan Schmidt } 537bd989ba3SJan Schmidt 538bd989ba3SJan Schmidt static noinline int 539bd989ba3SJan Schmidt tree_mod_log_insert_root(struct btrfs_fs_info *fs_info, 540bd989ba3SJan Schmidt struct extent_buffer *old_root, 541bd989ba3SJan Schmidt struct extent_buffer *new_root, gfp_t flags) 542bd989ba3SJan Schmidt { 543bd989ba3SJan Schmidt struct tree_mod_elem *tm; 544bd989ba3SJan Schmidt int ret; 545bd989ba3SJan Schmidt 546bd989ba3SJan Schmidt ret = tree_mod_alloc(fs_info, flags, &tm); 547bd989ba3SJan Schmidt if (ret <= 0) 548bd989ba3SJan Schmidt return ret; 549bd989ba3SJan Schmidt 550bd989ba3SJan Schmidt tm->index = new_root->start >> PAGE_CACHE_SHIFT; 551bd989ba3SJan Schmidt tm->old_root.logical = old_root->start; 552bd989ba3SJan Schmidt tm->old_root.level = btrfs_header_level(old_root); 553bd989ba3SJan Schmidt tm->generation = btrfs_header_generation(old_root); 554bd989ba3SJan Schmidt tm->op = MOD_LOG_ROOT_REPLACE; 555bd989ba3SJan Schmidt 556bd989ba3SJan Schmidt return __tree_mod_log_insert(fs_info, tm); 557bd989ba3SJan Schmidt } 558bd989ba3SJan Schmidt 559bd989ba3SJan Schmidt static struct tree_mod_elem * 560bd989ba3SJan Schmidt __tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq, 561bd989ba3SJan Schmidt int smallest) 562bd989ba3SJan Schmidt { 563bd989ba3SJan Schmidt struct rb_root *tm_root; 564bd989ba3SJan Schmidt struct rb_node *node; 565bd989ba3SJan Schmidt struct tree_mod_elem *cur = NULL; 566bd989ba3SJan Schmidt struct tree_mod_elem *found = NULL; 567bd989ba3SJan Schmidt u64 index = start >> PAGE_CACHE_SHIFT; 568bd989ba3SJan Schmidt 569bd989ba3SJan Schmidt read_lock(&fs_info->tree_mod_log_lock); 570bd989ba3SJan Schmidt tm_root = &fs_info->tree_mod_log; 571bd989ba3SJan Schmidt node = tm_root->rb_node; 572bd989ba3SJan Schmidt while (node) { 573bd989ba3SJan Schmidt cur = container_of(node, struct tree_mod_elem, node); 574bd989ba3SJan Schmidt if (cur->index < index) { 575bd989ba3SJan Schmidt node = node->rb_left; 576bd989ba3SJan Schmidt } else if (cur->index > index) { 577bd989ba3SJan Schmidt node = node->rb_right; 578bd989ba3SJan Schmidt } else if (cur->elem.seq < min_seq) { 579bd989ba3SJan Schmidt node = node->rb_left; 580bd989ba3SJan Schmidt } else if (!smallest) { 581bd989ba3SJan Schmidt /* we want the node with the highest seq */ 582bd989ba3SJan Schmidt if (found) 583bd989ba3SJan Schmidt BUG_ON(found->elem.seq > cur->elem.seq); 584bd989ba3SJan Schmidt found = cur; 585bd989ba3SJan Schmidt node = node->rb_left; 586bd989ba3SJan Schmidt } else if (cur->elem.seq > min_seq) { 587bd989ba3SJan Schmidt /* we want the node with the smallest seq */ 588bd989ba3SJan Schmidt if (found) 589bd989ba3SJan Schmidt BUG_ON(found->elem.seq < cur->elem.seq); 590bd989ba3SJan Schmidt found = cur; 591bd989ba3SJan Schmidt node = node->rb_right; 592bd989ba3SJan Schmidt } else { 593bd989ba3SJan Schmidt found = cur; 594bd989ba3SJan Schmidt break; 595bd989ba3SJan Schmidt } 596bd989ba3SJan Schmidt } 597bd989ba3SJan Schmidt read_unlock(&fs_info->tree_mod_log_lock); 598bd989ba3SJan Schmidt 599bd989ba3SJan Schmidt return found; 600bd989ba3SJan Schmidt } 601bd989ba3SJan Schmidt 602bd989ba3SJan Schmidt /* 603bd989ba3SJan Schmidt * this returns the element from the log with the smallest time sequence 604bd989ba3SJan Schmidt * value that's in the log (the oldest log item). any element with a time 605bd989ba3SJan Schmidt * sequence lower than min_seq will be ignored. 606bd989ba3SJan Schmidt */ 607bd989ba3SJan Schmidt static struct tree_mod_elem * 608bd989ba3SJan Schmidt tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, u64 start, 609bd989ba3SJan Schmidt u64 min_seq) 610bd989ba3SJan Schmidt { 611bd989ba3SJan Schmidt return __tree_mod_log_search(fs_info, start, min_seq, 1); 612bd989ba3SJan Schmidt } 613bd989ba3SJan Schmidt 614bd989ba3SJan Schmidt /* 615bd989ba3SJan Schmidt * this returns the element from the log with the largest time sequence 616bd989ba3SJan Schmidt * value that's in the log (the most recent log item). any element with 617bd989ba3SJan Schmidt * a time sequence lower than min_seq will be ignored. 618bd989ba3SJan Schmidt */ 619bd989ba3SJan Schmidt static struct tree_mod_elem * 620bd989ba3SJan Schmidt tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq) 621bd989ba3SJan Schmidt { 622bd989ba3SJan Schmidt return __tree_mod_log_search(fs_info, start, min_seq, 0); 623bd989ba3SJan Schmidt } 624bd989ba3SJan Schmidt 625bd989ba3SJan Schmidt static inline void 626bd989ba3SJan Schmidt tree_mod_log_eb_copy(struct btrfs_fs_info *fs_info, struct extent_buffer *dst, 627bd989ba3SJan Schmidt struct extent_buffer *src, unsigned long dst_offset, 628bd989ba3SJan Schmidt unsigned long src_offset, int nr_items) 629bd989ba3SJan Schmidt { 630bd989ba3SJan Schmidt int ret; 631bd989ba3SJan Schmidt int i; 632bd989ba3SJan Schmidt 633bd989ba3SJan Schmidt smp_mb(); 634bd989ba3SJan Schmidt if (list_empty(&fs_info->tree_mod_seq_list)) 635bd989ba3SJan Schmidt return; 636bd989ba3SJan Schmidt 637bd989ba3SJan Schmidt if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0) 638bd989ba3SJan Schmidt return; 639bd989ba3SJan Schmidt 640bd989ba3SJan Schmidt /* speed this up by single seq for all operations? */ 641bd989ba3SJan Schmidt for (i = 0; i < nr_items; i++) { 642bd989ba3SJan Schmidt ret = tree_mod_log_insert_key(fs_info, src, i + src_offset, 643bd989ba3SJan Schmidt MOD_LOG_KEY_REMOVE); 644bd989ba3SJan Schmidt BUG_ON(ret < 0); 645bd989ba3SJan Schmidt ret = tree_mod_log_insert_key(fs_info, dst, i + dst_offset, 646bd989ba3SJan Schmidt MOD_LOG_KEY_ADD); 647bd989ba3SJan Schmidt BUG_ON(ret < 0); 648bd989ba3SJan Schmidt } 649bd989ba3SJan Schmidt } 650bd989ba3SJan Schmidt 651bd989ba3SJan Schmidt static inline void 652bd989ba3SJan Schmidt tree_mod_log_eb_move(struct btrfs_fs_info *fs_info, struct extent_buffer *dst, 653bd989ba3SJan Schmidt int dst_offset, int src_offset, int nr_items) 654bd989ba3SJan Schmidt { 655bd989ba3SJan Schmidt int ret; 656bd989ba3SJan Schmidt ret = tree_mod_log_insert_move(fs_info, dst, dst_offset, src_offset, 657bd989ba3SJan Schmidt nr_items, GFP_NOFS); 658bd989ba3SJan Schmidt BUG_ON(ret < 0); 659bd989ba3SJan Schmidt } 660bd989ba3SJan Schmidt 661bd989ba3SJan Schmidt static inline void 662bd989ba3SJan Schmidt tree_mod_log_set_node_key(struct btrfs_fs_info *fs_info, 663bd989ba3SJan Schmidt struct extent_buffer *eb, 664bd989ba3SJan Schmidt struct btrfs_disk_key *disk_key, int slot, int atomic) 665bd989ba3SJan Schmidt { 666bd989ba3SJan Schmidt int ret; 667bd989ba3SJan Schmidt 668bd989ba3SJan Schmidt ret = tree_mod_log_insert_key_mask(fs_info, eb, slot, 669bd989ba3SJan Schmidt MOD_LOG_KEY_REPLACE, 670bd989ba3SJan Schmidt atomic ? GFP_ATOMIC : GFP_NOFS); 671bd989ba3SJan Schmidt BUG_ON(ret < 0); 672bd989ba3SJan Schmidt } 673bd989ba3SJan Schmidt 674bd989ba3SJan Schmidt static void tree_mod_log_free_eb(struct btrfs_fs_info *fs_info, 675bd989ba3SJan Schmidt struct extent_buffer *eb) 676bd989ba3SJan Schmidt { 677bd989ba3SJan Schmidt int i; 678bd989ba3SJan Schmidt int ret; 679bd989ba3SJan Schmidt u32 nritems; 680bd989ba3SJan Schmidt 681bd989ba3SJan Schmidt smp_mb(); 682bd989ba3SJan Schmidt if (list_empty(&fs_info->tree_mod_seq_list)) 683bd989ba3SJan Schmidt return; 684bd989ba3SJan Schmidt 685bd989ba3SJan Schmidt if (btrfs_header_level(eb) == 0) 686bd989ba3SJan Schmidt return; 687bd989ba3SJan Schmidt 688bd989ba3SJan Schmidt nritems = btrfs_header_nritems(eb); 689bd989ba3SJan Schmidt for (i = nritems - 1; i >= 0; i--) { 690bd989ba3SJan Schmidt ret = tree_mod_log_insert_key(fs_info, eb, i, 691bd989ba3SJan Schmidt MOD_LOG_KEY_REMOVE_WHILE_FREEING); 692bd989ba3SJan Schmidt BUG_ON(ret < 0); 693bd989ba3SJan Schmidt } 694bd989ba3SJan Schmidt } 695bd989ba3SJan Schmidt 696bd989ba3SJan Schmidt static inline void 697bd989ba3SJan Schmidt tree_mod_log_set_root_pointer(struct btrfs_root *root, 698bd989ba3SJan Schmidt struct extent_buffer *new_root_node) 699bd989ba3SJan Schmidt { 700bd989ba3SJan Schmidt int ret; 701bd989ba3SJan Schmidt tree_mod_log_free_eb(root->fs_info, root->node); 702bd989ba3SJan Schmidt ret = tree_mod_log_insert_root(root->fs_info, root->node, 703bd989ba3SJan Schmidt new_root_node, GFP_NOFS); 704bd989ba3SJan Schmidt BUG_ON(ret < 0); 705bd989ba3SJan Schmidt } 706bd989ba3SJan Schmidt 707d352ac68SChris Mason /* 7085d4f98a2SYan Zheng * check if the tree block can be shared by multiple trees 7095d4f98a2SYan Zheng */ 7105d4f98a2SYan Zheng int btrfs_block_can_be_shared(struct btrfs_root *root, 7115d4f98a2SYan Zheng struct extent_buffer *buf) 7125d4f98a2SYan Zheng { 7135d4f98a2SYan Zheng /* 7145d4f98a2SYan Zheng * Tree blocks not in refernece counted trees and tree roots 7155d4f98a2SYan Zheng * are never shared. If a block was allocated after the last 7165d4f98a2SYan Zheng * snapshot and the block was not allocated by tree relocation, 7175d4f98a2SYan Zheng * we know the block is not shared. 7185d4f98a2SYan Zheng */ 7195d4f98a2SYan Zheng if (root->ref_cows && 7205d4f98a2SYan Zheng buf != root->node && buf != root->commit_root && 7215d4f98a2SYan Zheng (btrfs_header_generation(buf) <= 7225d4f98a2SYan Zheng btrfs_root_last_snapshot(&root->root_item) || 7235d4f98a2SYan Zheng btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 7245d4f98a2SYan Zheng return 1; 7255d4f98a2SYan Zheng #ifdef BTRFS_COMPAT_EXTENT_TREE_V0 7265d4f98a2SYan Zheng if (root->ref_cows && 7275d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 7285d4f98a2SYan Zheng return 1; 7295d4f98a2SYan Zheng #endif 7305d4f98a2SYan Zheng return 0; 7315d4f98a2SYan Zheng } 7325d4f98a2SYan Zheng 7335d4f98a2SYan Zheng static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans, 7345d4f98a2SYan Zheng struct btrfs_root *root, 7355d4f98a2SYan Zheng struct extent_buffer *buf, 736f0486c68SYan, Zheng struct extent_buffer *cow, 737f0486c68SYan, Zheng int *last_ref) 7385d4f98a2SYan Zheng { 7395d4f98a2SYan Zheng u64 refs; 7405d4f98a2SYan Zheng u64 owner; 7415d4f98a2SYan Zheng u64 flags; 7425d4f98a2SYan Zheng u64 new_flags = 0; 7435d4f98a2SYan Zheng int ret; 7445d4f98a2SYan Zheng 7455d4f98a2SYan Zheng /* 7465d4f98a2SYan Zheng * Backrefs update rules: 7475d4f98a2SYan Zheng * 7485d4f98a2SYan Zheng * Always use full backrefs for extent pointers in tree block 7495d4f98a2SYan Zheng * allocated by tree relocation. 7505d4f98a2SYan Zheng * 7515d4f98a2SYan Zheng * If a shared tree block is no longer referenced by its owner 7525d4f98a2SYan Zheng * tree (btrfs_header_owner(buf) == root->root_key.objectid), 7535d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 7545d4f98a2SYan Zheng * 7555d4f98a2SYan Zheng * If a tree block is been relocating 7565d4f98a2SYan Zheng * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID), 7575d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 7585d4f98a2SYan Zheng * The reason for this is some operations (such as drop tree) 7595d4f98a2SYan Zheng * are only allowed for blocks use full backrefs. 7605d4f98a2SYan Zheng */ 7615d4f98a2SYan Zheng 7625d4f98a2SYan Zheng if (btrfs_block_can_be_shared(root, buf)) { 7635d4f98a2SYan Zheng ret = btrfs_lookup_extent_info(trans, root, buf->start, 7645d4f98a2SYan Zheng buf->len, &refs, &flags); 765be1a5564SMark Fasheh if (ret) 766be1a5564SMark Fasheh return ret; 767e5df9573SMark Fasheh if (refs == 0) { 768e5df9573SMark Fasheh ret = -EROFS; 769e5df9573SMark Fasheh btrfs_std_error(root->fs_info, ret); 770e5df9573SMark Fasheh return ret; 771e5df9573SMark Fasheh } 7725d4f98a2SYan Zheng } else { 7735d4f98a2SYan Zheng refs = 1; 7745d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 7755d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 7765d4f98a2SYan Zheng flags = BTRFS_BLOCK_FLAG_FULL_BACKREF; 7775d4f98a2SYan Zheng else 7785d4f98a2SYan Zheng flags = 0; 7795d4f98a2SYan Zheng } 7805d4f98a2SYan Zheng 7815d4f98a2SYan Zheng owner = btrfs_header_owner(buf); 7825d4f98a2SYan Zheng BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID && 7835d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)); 7845d4f98a2SYan Zheng 7855d4f98a2SYan Zheng if (refs > 1) { 7865d4f98a2SYan Zheng if ((owner == root->root_key.objectid || 7875d4f98a2SYan Zheng root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && 7885d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 78966d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, buf, 1, 1); 79079787eaaSJeff Mahoney BUG_ON(ret); /* -ENOMEM */ 7915d4f98a2SYan Zheng 7925d4f98a2SYan Zheng if (root->root_key.objectid == 7935d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 79466d7e7f0SArne Jansen ret = btrfs_dec_ref(trans, root, buf, 0, 1); 79579787eaaSJeff Mahoney BUG_ON(ret); /* -ENOMEM */ 79666d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 79779787eaaSJeff Mahoney BUG_ON(ret); /* -ENOMEM */ 7985d4f98a2SYan Zheng } 7995d4f98a2SYan Zheng new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; 8005d4f98a2SYan Zheng } else { 8015d4f98a2SYan Zheng 8025d4f98a2SYan Zheng if (root->root_key.objectid == 8035d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 80466d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 8055d4f98a2SYan Zheng else 80666d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 0, 1); 80779787eaaSJeff Mahoney BUG_ON(ret); /* -ENOMEM */ 8085d4f98a2SYan Zheng } 8095d4f98a2SYan Zheng if (new_flags != 0) { 8105d4f98a2SYan Zheng ret = btrfs_set_disk_extent_flags(trans, root, 8115d4f98a2SYan Zheng buf->start, 8125d4f98a2SYan Zheng buf->len, 8135d4f98a2SYan Zheng new_flags, 0); 814be1a5564SMark Fasheh if (ret) 815be1a5564SMark Fasheh return ret; 8165d4f98a2SYan Zheng } 8175d4f98a2SYan Zheng } else { 8185d4f98a2SYan Zheng if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { 8195d4f98a2SYan Zheng if (root->root_key.objectid == 8205d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 82166d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 1, 1); 8225d4f98a2SYan Zheng else 82366d7e7f0SArne Jansen ret = btrfs_inc_ref(trans, root, cow, 0, 1); 82479787eaaSJeff Mahoney BUG_ON(ret); /* -ENOMEM */ 82566d7e7f0SArne Jansen ret = btrfs_dec_ref(trans, root, buf, 1, 1); 82679787eaaSJeff Mahoney BUG_ON(ret); /* -ENOMEM */ 8275d4f98a2SYan Zheng } 828f230475eSJan Schmidt /* 829f230475eSJan Schmidt * don't log freeing in case we're freeing the root node, this 830f230475eSJan Schmidt * is done by tree_mod_log_set_root_pointer later 831f230475eSJan Schmidt */ 832f230475eSJan Schmidt if (buf != root->node && btrfs_header_level(buf) != 0) 833f230475eSJan Schmidt tree_mod_log_free_eb(root->fs_info, buf); 8345d4f98a2SYan Zheng clean_tree_block(trans, root, buf); 835f0486c68SYan, Zheng *last_ref = 1; 8365d4f98a2SYan Zheng } 8375d4f98a2SYan Zheng return 0; 8385d4f98a2SYan Zheng } 8395d4f98a2SYan Zheng 8405d4f98a2SYan Zheng /* 841d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 842d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 843d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 844d397712bSChris Mason * dirty again. 845d352ac68SChris Mason * 846d352ac68SChris Mason * search_start -- an allocation hint for the new block 847d352ac68SChris Mason * 848d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 849d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 850d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 851d352ac68SChris Mason */ 852d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 8535f39d397SChris Mason struct btrfs_root *root, 8545f39d397SChris Mason struct extent_buffer *buf, 8555f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 8565f39d397SChris Mason struct extent_buffer **cow_ret, 8579fa8cfe7SChris Mason u64 search_start, u64 empty_size) 8586702ed49SChris Mason { 8595d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 8605f39d397SChris Mason struct extent_buffer *cow; 861be1a5564SMark Fasheh int level, ret; 862f0486c68SYan, Zheng int last_ref = 0; 863925baeddSChris Mason int unlock_orig = 0; 8645d4f98a2SYan Zheng u64 parent_start; 8656702ed49SChris Mason 866925baeddSChris Mason if (*cow_ret == buf) 867925baeddSChris Mason unlock_orig = 1; 868925baeddSChris Mason 869b9447ef8SChris Mason btrfs_assert_tree_locked(buf); 870925baeddSChris Mason 8717bb86316SChris Mason WARN_ON(root->ref_cows && trans->transid != 8727bb86316SChris Mason root->fs_info->running_transaction->transid); 8736702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 8745f39d397SChris Mason 8757bb86316SChris Mason level = btrfs_header_level(buf); 87631840ae1SZheng Yan 8775d4f98a2SYan Zheng if (level == 0) 8785d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 8795d4f98a2SYan Zheng else 8805d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 8815d4f98a2SYan Zheng 8825d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) { 8835d4f98a2SYan Zheng if (parent) 8845d4f98a2SYan Zheng parent_start = parent->start; 8855d4f98a2SYan Zheng else 8865d4f98a2SYan Zheng parent_start = 0; 8875d4f98a2SYan Zheng } else 8885d4f98a2SYan Zheng parent_start = 0; 8895d4f98a2SYan Zheng 8905d4f98a2SYan Zheng cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start, 8915d4f98a2SYan Zheng root->root_key.objectid, &disk_key, 8925581a51aSJan Schmidt level, search_start, empty_size); 8936702ed49SChris Mason if (IS_ERR(cow)) 8946702ed49SChris Mason return PTR_ERR(cow); 8956702ed49SChris Mason 896b4ce94deSChris Mason /* cow is set to blocking by btrfs_init_new_buffer */ 897b4ce94deSChris Mason 8985f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 899db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 9005f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 9015d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 9025d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 9035d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 9045d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 9055d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 9065d4f98a2SYan Zheng else 9075f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 9086702ed49SChris Mason 9092b82032cSYan Zheng write_extent_buffer(cow, root->fs_info->fsid, 9102b82032cSYan Zheng (unsigned long)btrfs_header_fsid(cow), 9112b82032cSYan Zheng BTRFS_FSID_SIZE); 9122b82032cSYan Zheng 913be1a5564SMark Fasheh ret = update_ref_for_cow(trans, root, buf, cow, &last_ref); 914b68dc2a9SMark Fasheh if (ret) { 91579787eaaSJeff Mahoney btrfs_abort_transaction(trans, root, ret); 916b68dc2a9SMark Fasheh return ret; 917b68dc2a9SMark Fasheh } 9181a40e23bSZheng Yan 9193fd0a558SYan, Zheng if (root->ref_cows) 9203fd0a558SYan, Zheng btrfs_reloc_cow_block(trans, root, buf, cow); 9213fd0a558SYan, Zheng 9226702ed49SChris Mason if (buf == root->node) { 923925baeddSChris Mason WARN_ON(parent && parent != buf); 9245d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 9255d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 9265d4f98a2SYan Zheng parent_start = buf->start; 9275d4f98a2SYan Zheng else 9285d4f98a2SYan Zheng parent_start = 0; 929925baeddSChris Mason 9305f39d397SChris Mason extent_buffer_get(cow); 931f230475eSJan Schmidt tree_mod_log_set_root_pointer(root, cow); 932240f62c8SChris Mason rcu_assign_pointer(root->node, cow); 933925baeddSChris Mason 934f0486c68SYan, Zheng btrfs_free_tree_block(trans, root, buf, parent_start, 9355581a51aSJan Schmidt last_ref); 9365f39d397SChris Mason free_extent_buffer(buf); 9370b86a832SChris Mason add_root_to_dirty_list(root); 9386702ed49SChris Mason } else { 9395d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 9405d4f98a2SYan Zheng parent_start = parent->start; 9415d4f98a2SYan Zheng else 9425d4f98a2SYan Zheng parent_start = 0; 9435d4f98a2SYan Zheng 9445d4f98a2SYan Zheng WARN_ON(trans->transid != btrfs_header_generation(parent)); 945f230475eSJan Schmidt tree_mod_log_insert_key(root->fs_info, parent, parent_slot, 946f230475eSJan Schmidt MOD_LOG_KEY_REPLACE); 9475f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 948db94535dSChris Mason cow->start); 94974493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 95074493f7aSChris Mason trans->transid); 9516702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 952f0486c68SYan, Zheng btrfs_free_tree_block(trans, root, buf, parent_start, 9535581a51aSJan Schmidt last_ref); 9546702ed49SChris Mason } 955925baeddSChris Mason if (unlock_orig) 956925baeddSChris Mason btrfs_tree_unlock(buf); 9573083ee2eSJosef Bacik free_extent_buffer_stale(buf); 9586702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 9596702ed49SChris Mason *cow_ret = cow; 9606702ed49SChris Mason return 0; 9616702ed49SChris Mason } 9626702ed49SChris Mason 9635d4f98a2SYan Zheng static inline int should_cow_block(struct btrfs_trans_handle *trans, 9645d4f98a2SYan Zheng struct btrfs_root *root, 9655d4f98a2SYan Zheng struct extent_buffer *buf) 9665d4f98a2SYan Zheng { 967f1ebcc74SLiu Bo /* ensure we can see the force_cow */ 968f1ebcc74SLiu Bo smp_rmb(); 969f1ebcc74SLiu Bo 970f1ebcc74SLiu Bo /* 971f1ebcc74SLiu Bo * We do not need to cow a block if 972f1ebcc74SLiu Bo * 1) this block is not created or changed in this transaction; 973f1ebcc74SLiu Bo * 2) this block does not belong to TREE_RELOC tree; 974f1ebcc74SLiu Bo * 3) the root is not forced COW. 975f1ebcc74SLiu Bo * 976f1ebcc74SLiu Bo * What is forced COW: 977f1ebcc74SLiu Bo * when we create snapshot during commiting the transaction, 978f1ebcc74SLiu Bo * after we've finished coping src root, we must COW the shared 979f1ebcc74SLiu Bo * block to ensure the metadata consistency. 980f1ebcc74SLiu Bo */ 9815d4f98a2SYan Zheng if (btrfs_header_generation(buf) == trans->transid && 9825d4f98a2SYan Zheng !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) && 9835d4f98a2SYan Zheng !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID && 984f1ebcc74SLiu Bo btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) && 985f1ebcc74SLiu Bo !root->force_cow) 9865d4f98a2SYan Zheng return 0; 9875d4f98a2SYan Zheng return 1; 9885d4f98a2SYan Zheng } 9895d4f98a2SYan Zheng 990d352ac68SChris Mason /* 991d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 992d352ac68SChris Mason * This version of it has extra checks so that a block isn't cow'd more than 993d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 994d352ac68SChris Mason */ 995d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 9965f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 9975f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 9989fa8cfe7SChris Mason struct extent_buffer **cow_ret) 99902217ed2SChris Mason { 10006702ed49SChris Mason u64 search_start; 1001f510cfecSChris Mason int ret; 1002dc17ff8fSChris Mason 1003ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 1004d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 1005d397712bSChris Mason (unsigned long long)trans->transid, 1006d397712bSChris Mason (unsigned long long) 1007ccd467d6SChris Mason root->fs_info->running_transaction->transid); 1008ccd467d6SChris Mason WARN_ON(1); 1009ccd467d6SChris Mason } 1010ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 1011d397712bSChris Mason printk(KERN_CRIT "trans %llu running %llu\n", 1012d397712bSChris Mason (unsigned long long)trans->transid, 1013d397712bSChris Mason (unsigned long long)root->fs_info->generation); 1014ccd467d6SChris Mason WARN_ON(1); 1015ccd467d6SChris Mason } 1016dc17ff8fSChris Mason 10175d4f98a2SYan Zheng if (!should_cow_block(trans, root, buf)) { 101802217ed2SChris Mason *cow_ret = buf; 101902217ed2SChris Mason return 0; 102002217ed2SChris Mason } 1021c487685dSChris Mason 10220b86a832SChris Mason search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1); 1023b4ce94deSChris Mason 1024b4ce94deSChris Mason if (parent) 1025b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 1026b4ce94deSChris Mason btrfs_set_lock_blocking(buf); 1027b4ce94deSChris Mason 1028f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 10299fa8cfe7SChris Mason parent_slot, cow_ret, search_start, 0); 10301abe9b8aSliubo 10311abe9b8aSliubo trace_btrfs_cow_block(root, buf, *cow_ret); 10321abe9b8aSliubo 1033f510cfecSChris Mason return ret; 10342c90e5d6SChris Mason } 10356702ed49SChris Mason 1036d352ac68SChris Mason /* 1037d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 1038d352ac68SChris Mason * node are actually close by 1039d352ac68SChris Mason */ 10406b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 10416702ed49SChris Mason { 10426b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 10436702ed49SChris Mason return 1; 10446b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 10456702ed49SChris Mason return 1; 104602217ed2SChris Mason return 0; 104702217ed2SChris Mason } 104802217ed2SChris Mason 1049081e9573SChris Mason /* 1050081e9573SChris Mason * compare two keys in a memcmp fashion 1051081e9573SChris Mason */ 1052081e9573SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 1053081e9573SChris Mason { 1054081e9573SChris Mason struct btrfs_key k1; 1055081e9573SChris Mason 1056081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 1057081e9573SChris Mason 105820736abaSDiego Calleja return btrfs_comp_cpu_keys(&k1, k2); 1059081e9573SChris Mason } 1060081e9573SChris Mason 1061f3465ca4SJosef Bacik /* 1062f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 1063f3465ca4SJosef Bacik */ 10645d4f98a2SYan Zheng int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2) 1065f3465ca4SJosef Bacik { 1066f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 1067f3465ca4SJosef Bacik return 1; 1068f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 1069f3465ca4SJosef Bacik return -1; 1070f3465ca4SJosef Bacik if (k1->type > k2->type) 1071f3465ca4SJosef Bacik return 1; 1072f3465ca4SJosef Bacik if (k1->type < k2->type) 1073f3465ca4SJosef Bacik return -1; 1074f3465ca4SJosef Bacik if (k1->offset > k2->offset) 1075f3465ca4SJosef Bacik return 1; 1076f3465ca4SJosef Bacik if (k1->offset < k2->offset) 1077f3465ca4SJosef Bacik return -1; 1078f3465ca4SJosef Bacik return 0; 1079f3465ca4SJosef Bacik } 1080081e9573SChris Mason 1081d352ac68SChris Mason /* 1082d352ac68SChris Mason * this is used by the defrag code to go through all the 1083d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 1084d352ac68SChris Mason * disk order is close to key order 1085d352ac68SChris Mason */ 10866702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 10875f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 1088a6b6e75eSChris Mason int start_slot, int cache_only, u64 *last_ret, 1089a6b6e75eSChris Mason struct btrfs_key *progress) 10906702ed49SChris Mason { 10916b80053dSChris Mason struct extent_buffer *cur; 10926702ed49SChris Mason u64 blocknr; 1093ca7a79adSChris Mason u64 gen; 1094e9d0b13bSChris Mason u64 search_start = *last_ret; 1095e9d0b13bSChris Mason u64 last_block = 0; 10966702ed49SChris Mason u64 other; 10976702ed49SChris Mason u32 parent_nritems; 10986702ed49SChris Mason int end_slot; 10996702ed49SChris Mason int i; 11006702ed49SChris Mason int err = 0; 1101f2183bdeSChris Mason int parent_level; 11026b80053dSChris Mason int uptodate; 11036b80053dSChris Mason u32 blocksize; 1104081e9573SChris Mason int progress_passed = 0; 1105081e9573SChris Mason struct btrfs_disk_key disk_key; 11066702ed49SChris Mason 11075708b959SChris Mason parent_level = btrfs_header_level(parent); 11085708b959SChris Mason if (cache_only && parent_level != 1) 11095708b959SChris Mason return 0; 11105708b959SChris Mason 1111d397712bSChris Mason if (trans->transaction != root->fs_info->running_transaction) 11126702ed49SChris Mason WARN_ON(1); 1113d397712bSChris Mason if (trans->transid != root->fs_info->generation) 11146702ed49SChris Mason WARN_ON(1); 111586479a04SChris Mason 11166b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 11176b80053dSChris Mason blocksize = btrfs_level_size(root, parent_level - 1); 11186702ed49SChris Mason end_slot = parent_nritems; 11196702ed49SChris Mason 11206702ed49SChris Mason if (parent_nritems == 1) 11216702ed49SChris Mason return 0; 11226702ed49SChris Mason 1123b4ce94deSChris Mason btrfs_set_lock_blocking(parent); 1124b4ce94deSChris Mason 11256702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 11266702ed49SChris Mason int close = 1; 1127a6b6e75eSChris Mason 1128081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 1129081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 1130081e9573SChris Mason continue; 1131081e9573SChris Mason 1132081e9573SChris Mason progress_passed = 1; 11336b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 1134ca7a79adSChris Mason gen = btrfs_node_ptr_generation(parent, i); 1135e9d0b13bSChris Mason if (last_block == 0) 1136e9d0b13bSChris Mason last_block = blocknr; 11375708b959SChris Mason 11386702ed49SChris Mason if (i > 0) { 11396b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 11406b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 11416702ed49SChris Mason } 11420ef3e66bSChris Mason if (!close && i < end_slot - 2) { 11436b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 11446b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 11456702ed49SChris Mason } 1146e9d0b13bSChris Mason if (close) { 1147e9d0b13bSChris Mason last_block = blocknr; 11486702ed49SChris Mason continue; 1149e9d0b13bSChris Mason } 11506702ed49SChris Mason 11516b80053dSChris Mason cur = btrfs_find_tree_block(root, blocknr, blocksize); 11526b80053dSChris Mason if (cur) 1153b9fab919SChris Mason uptodate = btrfs_buffer_uptodate(cur, gen, 0); 11546b80053dSChris Mason else 11556b80053dSChris Mason uptodate = 0; 11565708b959SChris Mason if (!cur || !uptodate) { 11576702ed49SChris Mason if (cache_only) { 11586b80053dSChris Mason free_extent_buffer(cur); 11596702ed49SChris Mason continue; 11606702ed49SChris Mason } 11616b80053dSChris Mason if (!cur) { 11626b80053dSChris Mason cur = read_tree_block(root, blocknr, 1163ca7a79adSChris Mason blocksize, gen); 116497d9a8a4STsutomu Itoh if (!cur) 116597d9a8a4STsutomu Itoh return -EIO; 11666b80053dSChris Mason } else if (!uptodate) { 1167ca7a79adSChris Mason btrfs_read_buffer(cur, gen); 11686702ed49SChris Mason } 1169f2183bdeSChris Mason } 1170e9d0b13bSChris Mason if (search_start == 0) 11716b80053dSChris Mason search_start = last_block; 1172e9d0b13bSChris Mason 1173e7a84565SChris Mason btrfs_tree_lock(cur); 1174b4ce94deSChris Mason btrfs_set_lock_blocking(cur); 11756b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 1176e7a84565SChris Mason &cur, search_start, 11776b80053dSChris Mason min(16 * blocksize, 11789fa8cfe7SChris Mason (end_slot - i) * blocksize)); 1179252c38f0SYan if (err) { 1180e7a84565SChris Mason btrfs_tree_unlock(cur); 11816b80053dSChris Mason free_extent_buffer(cur); 11826702ed49SChris Mason break; 1183252c38f0SYan } 1184e7a84565SChris Mason search_start = cur->start; 1185e7a84565SChris Mason last_block = cur->start; 1186f2183bdeSChris Mason *last_ret = search_start; 1187e7a84565SChris Mason btrfs_tree_unlock(cur); 1188e7a84565SChris Mason free_extent_buffer(cur); 11896702ed49SChris Mason } 11906702ed49SChris Mason return err; 11916702ed49SChris Mason } 11926702ed49SChris Mason 119374123bd7SChris Mason /* 119474123bd7SChris Mason * The leaf data grows from end-to-front in the node. 119574123bd7SChris Mason * this returns the address of the start of the last item, 119674123bd7SChris Mason * which is the stop of the leaf data stack 119774123bd7SChris Mason */ 1198123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 11995f39d397SChris Mason struct extent_buffer *leaf) 1200be0e5c09SChris Mason { 12015f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 1202be0e5c09SChris Mason if (nr == 0) 1203123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 12045f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 1205be0e5c09SChris Mason } 1206be0e5c09SChris Mason 1207aa5d6bedSChris Mason 120874123bd7SChris Mason /* 12095f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 12105f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 12115f39d397SChris Mason * 121274123bd7SChris Mason * the slot in the array is returned via slot, and it points to 121374123bd7SChris Mason * the place where you would insert key if it is not found in 121474123bd7SChris Mason * the array. 121574123bd7SChris Mason * 121674123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 121774123bd7SChris Mason */ 1218e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 1219e02119d5SChris Mason unsigned long p, 12205f39d397SChris Mason int item_size, struct btrfs_key *key, 1221be0e5c09SChris Mason int max, int *slot) 1222be0e5c09SChris Mason { 1223be0e5c09SChris Mason int low = 0; 1224be0e5c09SChris Mason int high = max; 1225be0e5c09SChris Mason int mid; 1226be0e5c09SChris Mason int ret; 1227479965d6SChris Mason struct btrfs_disk_key *tmp = NULL; 12285f39d397SChris Mason struct btrfs_disk_key unaligned; 12295f39d397SChris Mason unsigned long offset; 12305f39d397SChris Mason char *kaddr = NULL; 12315f39d397SChris Mason unsigned long map_start = 0; 12325f39d397SChris Mason unsigned long map_len = 0; 1233479965d6SChris Mason int err; 1234be0e5c09SChris Mason 1235be0e5c09SChris Mason while (low < high) { 1236be0e5c09SChris Mason mid = (low + high) / 2; 12375f39d397SChris Mason offset = p + mid * item_size; 12385f39d397SChris Mason 1239a6591715SChris Mason if (!kaddr || offset < map_start || 12405f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 12415f39d397SChris Mason map_start + map_len) { 1242934d375bSChris Mason 1243934d375bSChris Mason err = map_private_extent_buffer(eb, offset, 1244479965d6SChris Mason sizeof(struct btrfs_disk_key), 1245a6591715SChris Mason &kaddr, &map_start, &map_len); 12465f39d397SChris Mason 1247479965d6SChris Mason if (!err) { 1248479965d6SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 1249479965d6SChris Mason map_start); 1250479965d6SChris Mason } else { 12515f39d397SChris Mason read_extent_buffer(eb, &unaligned, 12525f39d397SChris Mason offset, sizeof(unaligned)); 12535f39d397SChris Mason tmp = &unaligned; 1254479965d6SChris Mason } 1255479965d6SChris Mason 12565f39d397SChris Mason } else { 12575f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 12585f39d397SChris Mason map_start); 12595f39d397SChris Mason } 1260be0e5c09SChris Mason ret = comp_keys(tmp, key); 1261be0e5c09SChris Mason 1262be0e5c09SChris Mason if (ret < 0) 1263be0e5c09SChris Mason low = mid + 1; 1264be0e5c09SChris Mason else if (ret > 0) 1265be0e5c09SChris Mason high = mid; 1266be0e5c09SChris Mason else { 1267be0e5c09SChris Mason *slot = mid; 1268be0e5c09SChris Mason return 0; 1269be0e5c09SChris Mason } 1270be0e5c09SChris Mason } 1271be0e5c09SChris Mason *slot = low; 1272be0e5c09SChris Mason return 1; 1273be0e5c09SChris Mason } 1274be0e5c09SChris Mason 127597571fd0SChris Mason /* 127697571fd0SChris Mason * simple bin_search frontend that does the right thing for 127797571fd0SChris Mason * leaves vs nodes 127897571fd0SChris Mason */ 12795f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 12805f39d397SChris Mason int level, int *slot) 1281be0e5c09SChris Mason { 12825f39d397SChris Mason if (level == 0) { 12835f39d397SChris Mason return generic_bin_search(eb, 12845f39d397SChris Mason offsetof(struct btrfs_leaf, items), 12850783fcfcSChris Mason sizeof(struct btrfs_item), 12865f39d397SChris Mason key, btrfs_header_nritems(eb), 12877518a238SChris Mason slot); 1288be0e5c09SChris Mason } else { 12895f39d397SChris Mason return generic_bin_search(eb, 12905f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 1291123abc88SChris Mason sizeof(struct btrfs_key_ptr), 12925f39d397SChris Mason key, btrfs_header_nritems(eb), 12937518a238SChris Mason slot); 1294be0e5c09SChris Mason } 1295be0e5c09SChris Mason return -1; 1296be0e5c09SChris Mason } 1297be0e5c09SChris Mason 12985d4f98a2SYan Zheng int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key, 12995d4f98a2SYan Zheng int level, int *slot) 13005d4f98a2SYan Zheng { 13015d4f98a2SYan Zheng return bin_search(eb, key, level, slot); 13025d4f98a2SYan Zheng } 13035d4f98a2SYan Zheng 1304f0486c68SYan, Zheng static void root_add_used(struct btrfs_root *root, u32 size) 1305f0486c68SYan, Zheng { 1306f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 1307f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 1308f0486c68SYan, Zheng btrfs_root_used(&root->root_item) + size); 1309f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 1310f0486c68SYan, Zheng } 1311f0486c68SYan, Zheng 1312f0486c68SYan, Zheng static void root_sub_used(struct btrfs_root *root, u32 size) 1313f0486c68SYan, Zheng { 1314f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 1315f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 1316f0486c68SYan, Zheng btrfs_root_used(&root->root_item) - size); 1317f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 1318f0486c68SYan, Zheng } 1319f0486c68SYan, Zheng 1320d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 1321d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 1322d352ac68SChris Mason * NULL is returned on error. 1323d352ac68SChris Mason */ 1324e02119d5SChris Mason static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root, 13255f39d397SChris Mason struct extent_buffer *parent, int slot) 1326bb803951SChris Mason { 1327ca7a79adSChris Mason int level = btrfs_header_level(parent); 1328bb803951SChris Mason if (slot < 0) 1329bb803951SChris Mason return NULL; 13305f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 1331bb803951SChris Mason return NULL; 1332ca7a79adSChris Mason 1333ca7a79adSChris Mason BUG_ON(level == 0); 1334ca7a79adSChris Mason 1335db94535dSChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot), 1336ca7a79adSChris Mason btrfs_level_size(root, level - 1), 1337ca7a79adSChris Mason btrfs_node_ptr_generation(parent, slot)); 1338bb803951SChris Mason } 1339bb803951SChris Mason 1340d352ac68SChris Mason /* 1341d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 1342d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 1343d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 1344d352ac68SChris Mason */ 1345e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 134698ed5174SChris Mason struct btrfs_root *root, 134798ed5174SChris Mason struct btrfs_path *path, int level) 1348bb803951SChris Mason { 13495f39d397SChris Mason struct extent_buffer *right = NULL; 13505f39d397SChris Mason struct extent_buffer *mid; 13515f39d397SChris Mason struct extent_buffer *left = NULL; 13525f39d397SChris Mason struct extent_buffer *parent = NULL; 1353bb803951SChris Mason int ret = 0; 1354bb803951SChris Mason int wret; 1355bb803951SChris Mason int pslot; 1356bb803951SChris Mason int orig_slot = path->slots[level]; 135779f95c82SChris Mason u64 orig_ptr; 1358bb803951SChris Mason 1359bb803951SChris Mason if (level == 0) 1360bb803951SChris Mason return 0; 1361bb803951SChris Mason 13625f39d397SChris Mason mid = path->nodes[level]; 1363b4ce94deSChris Mason 1364bd681513SChris Mason WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK && 1365bd681513SChris Mason path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING); 13667bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 13677bb86316SChris Mason 13681d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 136979f95c82SChris Mason 1370a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 13715f39d397SChris Mason parent = path->nodes[level + 1]; 1372bb803951SChris Mason pslot = path->slots[level + 1]; 1373a05a9bb1SLi Zefan } 1374bb803951SChris Mason 137540689478SChris Mason /* 137640689478SChris Mason * deal with the case where there is only one pointer in the root 137740689478SChris Mason * by promoting the node below to a root 137840689478SChris Mason */ 13795f39d397SChris Mason if (!parent) { 13805f39d397SChris Mason struct extent_buffer *child; 1381bb803951SChris Mason 13825f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 1383bb803951SChris Mason return 0; 1384bb803951SChris Mason 1385bb803951SChris Mason /* promote the child to a root */ 13865f39d397SChris Mason child = read_node_slot(root, mid, 0); 1387305a26afSMark Fasheh if (!child) { 1388305a26afSMark Fasheh ret = -EROFS; 1389305a26afSMark Fasheh btrfs_std_error(root->fs_info, ret); 1390305a26afSMark Fasheh goto enospc; 1391305a26afSMark Fasheh } 1392305a26afSMark Fasheh 1393925baeddSChris Mason btrfs_tree_lock(child); 1394b4ce94deSChris Mason btrfs_set_lock_blocking(child); 13959fa8cfe7SChris Mason ret = btrfs_cow_block(trans, root, child, mid, 0, &child); 1396f0486c68SYan, Zheng if (ret) { 1397f0486c68SYan, Zheng btrfs_tree_unlock(child); 1398f0486c68SYan, Zheng free_extent_buffer(child); 1399f0486c68SYan, Zheng goto enospc; 1400f0486c68SYan, Zheng } 14012f375ab9SYan 1402f230475eSJan Schmidt tree_mod_log_set_root_pointer(root, child); 1403240f62c8SChris Mason rcu_assign_pointer(root->node, child); 1404925baeddSChris Mason 14050b86a832SChris Mason add_root_to_dirty_list(root); 1406925baeddSChris Mason btrfs_tree_unlock(child); 1407b4ce94deSChris Mason 1408925baeddSChris Mason path->locks[level] = 0; 1409bb803951SChris Mason path->nodes[level] = NULL; 14105f39d397SChris Mason clean_tree_block(trans, root, mid); 1411925baeddSChris Mason btrfs_tree_unlock(mid); 1412bb803951SChris Mason /* once for the path */ 14135f39d397SChris Mason free_extent_buffer(mid); 1414f0486c68SYan, Zheng 1415f0486c68SYan, Zheng root_sub_used(root, mid->len); 14165581a51aSJan Schmidt btrfs_free_tree_block(trans, root, mid, 0, 1); 1417bb803951SChris Mason /* once for the root ptr */ 14183083ee2eSJosef Bacik free_extent_buffer_stale(mid); 1419f0486c68SYan, Zheng return 0; 1420bb803951SChris Mason } 14215f39d397SChris Mason if (btrfs_header_nritems(mid) > 1422123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 1423bb803951SChris Mason return 0; 1424bb803951SChris Mason 1425559af821SAndi Kleen btrfs_header_nritems(mid); 142654aa1f4dSChris Mason 14275f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 14285f39d397SChris Mason if (left) { 1429925baeddSChris Mason btrfs_tree_lock(left); 1430b4ce94deSChris Mason btrfs_set_lock_blocking(left); 14315f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 14329fa8cfe7SChris Mason parent, pslot - 1, &left); 143354aa1f4dSChris Mason if (wret) { 143454aa1f4dSChris Mason ret = wret; 143554aa1f4dSChris Mason goto enospc; 143654aa1f4dSChris Mason } 14372cc58cf2SChris Mason } 14385f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 14395f39d397SChris Mason if (right) { 1440925baeddSChris Mason btrfs_tree_lock(right); 1441b4ce94deSChris Mason btrfs_set_lock_blocking(right); 14425f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 14439fa8cfe7SChris Mason parent, pslot + 1, &right); 14442cc58cf2SChris Mason if (wret) { 14452cc58cf2SChris Mason ret = wret; 14462cc58cf2SChris Mason goto enospc; 14472cc58cf2SChris Mason } 14482cc58cf2SChris Mason } 14492cc58cf2SChris Mason 14502cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 14515f39d397SChris Mason if (left) { 14525f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 1453bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 145479f95c82SChris Mason if (wret < 0) 145579f95c82SChris Mason ret = wret; 1456559af821SAndi Kleen btrfs_header_nritems(mid); 1457bb803951SChris Mason } 145879f95c82SChris Mason 145979f95c82SChris Mason /* 146079f95c82SChris Mason * then try to empty the right most buffer into the middle 146179f95c82SChris Mason */ 14625f39d397SChris Mason if (right) { 1463971a1f66SChris Mason wret = push_node_left(trans, root, mid, right, 1); 146454aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 146579f95c82SChris Mason ret = wret; 14665f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 14675f39d397SChris Mason clean_tree_block(trans, root, right); 1468925baeddSChris Mason btrfs_tree_unlock(right); 1469f3ea38daSJan Schmidt del_ptr(trans, root, path, level + 1, pslot + 1, 1); 1470f0486c68SYan, Zheng root_sub_used(root, right->len); 14715581a51aSJan Schmidt btrfs_free_tree_block(trans, root, right, 0, 1); 14723083ee2eSJosef Bacik free_extent_buffer_stale(right); 1473f0486c68SYan, Zheng right = NULL; 1474bb803951SChris Mason } else { 14755f39d397SChris Mason struct btrfs_disk_key right_key; 14765f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 1477f230475eSJan Schmidt tree_mod_log_set_node_key(root->fs_info, parent, 1478f230475eSJan Schmidt &right_key, pslot + 1, 0); 14795f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 14805f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 1481bb803951SChris Mason } 1482bb803951SChris Mason } 14835f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 148479f95c82SChris Mason /* 148579f95c82SChris Mason * we're not allowed to leave a node with one item in the 148679f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 148779f95c82SChris Mason * could try to delete the only pointer in this node. 148879f95c82SChris Mason * So, pull some keys from the left. 148979f95c82SChris Mason * There has to be a left pointer at this point because 149079f95c82SChris Mason * otherwise we would have pulled some pointers from the 149179f95c82SChris Mason * right 149279f95c82SChris Mason */ 1493305a26afSMark Fasheh if (!left) { 1494305a26afSMark Fasheh ret = -EROFS; 1495305a26afSMark Fasheh btrfs_std_error(root->fs_info, ret); 1496305a26afSMark Fasheh goto enospc; 1497305a26afSMark Fasheh } 14985f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 149954aa1f4dSChris Mason if (wret < 0) { 150079f95c82SChris Mason ret = wret; 150154aa1f4dSChris Mason goto enospc; 150254aa1f4dSChris Mason } 1503bce4eae9SChris Mason if (wret == 1) { 1504bce4eae9SChris Mason wret = push_node_left(trans, root, left, mid, 1); 1505bce4eae9SChris Mason if (wret < 0) 1506bce4eae9SChris Mason ret = wret; 1507bce4eae9SChris Mason } 150879f95c82SChris Mason BUG_ON(wret == 1); 150979f95c82SChris Mason } 15105f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 15115f39d397SChris Mason clean_tree_block(trans, root, mid); 1512925baeddSChris Mason btrfs_tree_unlock(mid); 1513f3ea38daSJan Schmidt del_ptr(trans, root, path, level + 1, pslot, 1); 1514f0486c68SYan, Zheng root_sub_used(root, mid->len); 15155581a51aSJan Schmidt btrfs_free_tree_block(trans, root, mid, 0, 1); 15163083ee2eSJosef Bacik free_extent_buffer_stale(mid); 1517f0486c68SYan, Zheng mid = NULL; 151879f95c82SChris Mason } else { 151979f95c82SChris Mason /* update the parent key to reflect our changes */ 15205f39d397SChris Mason struct btrfs_disk_key mid_key; 15215f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 1522f230475eSJan Schmidt tree_mod_log_set_node_key(root->fs_info, parent, &mid_key, 1523f230475eSJan Schmidt pslot, 0); 15245f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 15255f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 152679f95c82SChris Mason } 1527bb803951SChris Mason 152879f95c82SChris Mason /* update the path */ 15295f39d397SChris Mason if (left) { 15305f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 15315f39d397SChris Mason extent_buffer_get(left); 1532925baeddSChris Mason /* left was locked after cow */ 15335f39d397SChris Mason path->nodes[level] = left; 1534bb803951SChris Mason path->slots[level + 1] -= 1; 1535bb803951SChris Mason path->slots[level] = orig_slot; 1536925baeddSChris Mason if (mid) { 1537925baeddSChris Mason btrfs_tree_unlock(mid); 15385f39d397SChris Mason free_extent_buffer(mid); 1539925baeddSChris Mason } 1540bb803951SChris Mason } else { 15415f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1542bb803951SChris Mason path->slots[level] = orig_slot; 1543bb803951SChris Mason } 1544bb803951SChris Mason } 154579f95c82SChris Mason /* double check we haven't messed things up */ 1546e20d96d6SChris Mason if (orig_ptr != 15475f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 154879f95c82SChris Mason BUG(); 154954aa1f4dSChris Mason enospc: 1550925baeddSChris Mason if (right) { 1551925baeddSChris Mason btrfs_tree_unlock(right); 15525f39d397SChris Mason free_extent_buffer(right); 1553925baeddSChris Mason } 1554925baeddSChris Mason if (left) { 1555925baeddSChris Mason if (path->nodes[level] != left) 1556925baeddSChris Mason btrfs_tree_unlock(left); 15575f39d397SChris Mason free_extent_buffer(left); 1558925baeddSChris Mason } 1559bb803951SChris Mason return ret; 1560bb803951SChris Mason } 1561bb803951SChris Mason 1562d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1563d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1564d352ac68SChris Mason * have to be pessimistic. 1565d352ac68SChris Mason */ 1566d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1567e66f709bSChris Mason struct btrfs_root *root, 1568e66f709bSChris Mason struct btrfs_path *path, int level) 1569e66f709bSChris Mason { 15705f39d397SChris Mason struct extent_buffer *right = NULL; 15715f39d397SChris Mason struct extent_buffer *mid; 15725f39d397SChris Mason struct extent_buffer *left = NULL; 15735f39d397SChris Mason struct extent_buffer *parent = NULL; 1574e66f709bSChris Mason int ret = 0; 1575e66f709bSChris Mason int wret; 1576e66f709bSChris Mason int pslot; 1577e66f709bSChris Mason int orig_slot = path->slots[level]; 1578e66f709bSChris Mason 1579e66f709bSChris Mason if (level == 0) 1580e66f709bSChris Mason return 1; 1581e66f709bSChris Mason 15825f39d397SChris Mason mid = path->nodes[level]; 15837bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1584e66f709bSChris Mason 1585a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 15865f39d397SChris Mason parent = path->nodes[level + 1]; 1587e66f709bSChris Mason pslot = path->slots[level + 1]; 1588a05a9bb1SLi Zefan } 1589e66f709bSChris Mason 15905f39d397SChris Mason if (!parent) 1591e66f709bSChris Mason return 1; 1592e66f709bSChris Mason 15935f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 1594e66f709bSChris Mason 1595e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 15965f39d397SChris Mason if (left) { 1597e66f709bSChris Mason u32 left_nr; 1598925baeddSChris Mason 1599925baeddSChris Mason btrfs_tree_lock(left); 1600b4ce94deSChris Mason btrfs_set_lock_blocking(left); 1601b4ce94deSChris Mason 16025f39d397SChris Mason left_nr = btrfs_header_nritems(left); 160333ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 160433ade1f8SChris Mason wret = 1; 160533ade1f8SChris Mason } else { 16065f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 16079fa8cfe7SChris Mason pslot - 1, &left); 160854aa1f4dSChris Mason if (ret) 160954aa1f4dSChris Mason wret = 1; 161054aa1f4dSChris Mason else { 161154aa1f4dSChris Mason wret = push_node_left(trans, root, 1612971a1f66SChris Mason left, mid, 0); 161354aa1f4dSChris Mason } 161433ade1f8SChris Mason } 1615e66f709bSChris Mason if (wret < 0) 1616e66f709bSChris Mason ret = wret; 1617e66f709bSChris Mason if (wret == 0) { 16185f39d397SChris Mason struct btrfs_disk_key disk_key; 1619e66f709bSChris Mason orig_slot += left_nr; 16205f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 1621f230475eSJan Schmidt tree_mod_log_set_node_key(root->fs_info, parent, 1622f230475eSJan Schmidt &disk_key, pslot, 0); 16235f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 16245f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 16255f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 16265f39d397SChris Mason path->nodes[level] = left; 1627e66f709bSChris Mason path->slots[level + 1] -= 1; 1628e66f709bSChris Mason path->slots[level] = orig_slot; 1629925baeddSChris Mason btrfs_tree_unlock(mid); 16305f39d397SChris Mason free_extent_buffer(mid); 1631e66f709bSChris Mason } else { 1632e66f709bSChris Mason orig_slot -= 16335f39d397SChris Mason btrfs_header_nritems(left); 1634e66f709bSChris Mason path->slots[level] = orig_slot; 1635925baeddSChris Mason btrfs_tree_unlock(left); 16365f39d397SChris Mason free_extent_buffer(left); 1637e66f709bSChris Mason } 1638e66f709bSChris Mason return 0; 1639e66f709bSChris Mason } 1640925baeddSChris Mason btrfs_tree_unlock(left); 16415f39d397SChris Mason free_extent_buffer(left); 1642e66f709bSChris Mason } 16435f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 1644e66f709bSChris Mason 1645e66f709bSChris Mason /* 1646e66f709bSChris Mason * then try to empty the right most buffer into the middle 1647e66f709bSChris Mason */ 16485f39d397SChris Mason if (right) { 164933ade1f8SChris Mason u32 right_nr; 1650b4ce94deSChris Mason 1651925baeddSChris Mason btrfs_tree_lock(right); 1652b4ce94deSChris Mason btrfs_set_lock_blocking(right); 1653b4ce94deSChris Mason 16545f39d397SChris Mason right_nr = btrfs_header_nritems(right); 165533ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 165633ade1f8SChris Mason wret = 1; 165733ade1f8SChris Mason } else { 16585f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 16595f39d397SChris Mason parent, pslot + 1, 16609fa8cfe7SChris Mason &right); 166154aa1f4dSChris Mason if (ret) 166254aa1f4dSChris Mason wret = 1; 166354aa1f4dSChris Mason else { 166433ade1f8SChris Mason wret = balance_node_right(trans, root, 16655f39d397SChris Mason right, mid); 166633ade1f8SChris Mason } 166754aa1f4dSChris Mason } 1668e66f709bSChris Mason if (wret < 0) 1669e66f709bSChris Mason ret = wret; 1670e66f709bSChris Mason if (wret == 0) { 16715f39d397SChris Mason struct btrfs_disk_key disk_key; 16725f39d397SChris Mason 16735f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 1674f230475eSJan Schmidt tree_mod_log_set_node_key(root->fs_info, parent, 1675f230475eSJan Schmidt &disk_key, pslot + 1, 0); 16765f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 16775f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 16785f39d397SChris Mason 16795f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 16805f39d397SChris Mason path->nodes[level] = right; 1681e66f709bSChris Mason path->slots[level + 1] += 1; 1682e66f709bSChris Mason path->slots[level] = orig_slot - 16835f39d397SChris Mason btrfs_header_nritems(mid); 1684925baeddSChris Mason btrfs_tree_unlock(mid); 16855f39d397SChris Mason free_extent_buffer(mid); 1686e66f709bSChris Mason } else { 1687925baeddSChris Mason btrfs_tree_unlock(right); 16885f39d397SChris Mason free_extent_buffer(right); 1689e66f709bSChris Mason } 1690e66f709bSChris Mason return 0; 1691e66f709bSChris Mason } 1692925baeddSChris Mason btrfs_tree_unlock(right); 16935f39d397SChris Mason free_extent_buffer(right); 1694e66f709bSChris Mason } 1695e66f709bSChris Mason return 1; 1696e66f709bSChris Mason } 1697e66f709bSChris Mason 169874123bd7SChris Mason /* 1699d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1700d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 17013c69faecSChris Mason */ 1702c8c42864SChris Mason static void reada_for_search(struct btrfs_root *root, 1703e02119d5SChris Mason struct btrfs_path *path, 170401f46658SChris Mason int level, int slot, u64 objectid) 17053c69faecSChris Mason { 17065f39d397SChris Mason struct extent_buffer *node; 170701f46658SChris Mason struct btrfs_disk_key disk_key; 17083c69faecSChris Mason u32 nritems; 17093c69faecSChris Mason u64 search; 1710a7175319SChris Mason u64 target; 17116b80053dSChris Mason u64 nread = 0; 1712cb25c2eaSJosef Bacik u64 gen; 17133c69faecSChris Mason int direction = path->reada; 17145f39d397SChris Mason struct extent_buffer *eb; 17156b80053dSChris Mason u32 nr; 17166b80053dSChris Mason u32 blocksize; 17176b80053dSChris Mason u32 nscan = 0; 1718db94535dSChris Mason 1719a6b6e75eSChris Mason if (level != 1) 17203c69faecSChris Mason return; 17213c69faecSChris Mason 17226702ed49SChris Mason if (!path->nodes[level]) 17236702ed49SChris Mason return; 17246702ed49SChris Mason 17255f39d397SChris Mason node = path->nodes[level]; 1726925baeddSChris Mason 17273c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 17286b80053dSChris Mason blocksize = btrfs_level_size(root, level - 1); 17296b80053dSChris Mason eb = btrfs_find_tree_block(root, search, blocksize); 17305f39d397SChris Mason if (eb) { 17315f39d397SChris Mason free_extent_buffer(eb); 17323c69faecSChris Mason return; 17333c69faecSChris Mason } 17343c69faecSChris Mason 1735a7175319SChris Mason target = search; 17366b80053dSChris Mason 17375f39d397SChris Mason nritems = btrfs_header_nritems(node); 17386b80053dSChris Mason nr = slot; 173925b8b936SJosef Bacik 17403c69faecSChris Mason while (1) { 17416b80053dSChris Mason if (direction < 0) { 17426b80053dSChris Mason if (nr == 0) 17433c69faecSChris Mason break; 17446b80053dSChris Mason nr--; 17456b80053dSChris Mason } else if (direction > 0) { 17466b80053dSChris Mason nr++; 17476b80053dSChris Mason if (nr >= nritems) 17486b80053dSChris Mason break; 17493c69faecSChris Mason } 175001f46658SChris Mason if (path->reada < 0 && objectid) { 175101f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 175201f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 175301f46658SChris Mason break; 175401f46658SChris Mason } 17556b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1756a7175319SChris Mason if ((search <= target && target - search <= 65536) || 1757a7175319SChris Mason (search > target && search - target <= 65536)) { 1758cb25c2eaSJosef Bacik gen = btrfs_node_ptr_generation(node, nr); 1759cb25c2eaSJosef Bacik readahead_tree_block(root, search, blocksize, gen); 17606b80053dSChris Mason nread += blocksize; 17613c69faecSChris Mason } 17626b80053dSChris Mason nscan++; 1763a7175319SChris Mason if ((nread > 65536 || nscan > 32)) 17646b80053dSChris Mason break; 17653c69faecSChris Mason } 17663c69faecSChris Mason } 1767925baeddSChris Mason 1768d352ac68SChris Mason /* 1769b4ce94deSChris Mason * returns -EAGAIN if it had to drop the path, or zero if everything was in 1770b4ce94deSChris Mason * cache 1771b4ce94deSChris Mason */ 1772b4ce94deSChris Mason static noinline int reada_for_balance(struct btrfs_root *root, 1773b4ce94deSChris Mason struct btrfs_path *path, int level) 1774b4ce94deSChris Mason { 1775b4ce94deSChris Mason int slot; 1776b4ce94deSChris Mason int nritems; 1777b4ce94deSChris Mason struct extent_buffer *parent; 1778b4ce94deSChris Mason struct extent_buffer *eb; 1779b4ce94deSChris Mason u64 gen; 1780b4ce94deSChris Mason u64 block1 = 0; 1781b4ce94deSChris Mason u64 block2 = 0; 1782b4ce94deSChris Mason int ret = 0; 1783b4ce94deSChris Mason int blocksize; 1784b4ce94deSChris Mason 17858c594ea8SChris Mason parent = path->nodes[level + 1]; 1786b4ce94deSChris Mason if (!parent) 1787b4ce94deSChris Mason return 0; 1788b4ce94deSChris Mason 1789b4ce94deSChris Mason nritems = btrfs_header_nritems(parent); 17908c594ea8SChris Mason slot = path->slots[level + 1]; 1791b4ce94deSChris Mason blocksize = btrfs_level_size(root, level); 1792b4ce94deSChris Mason 1793b4ce94deSChris Mason if (slot > 0) { 1794b4ce94deSChris Mason block1 = btrfs_node_blockptr(parent, slot - 1); 1795b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot - 1); 1796b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block1, blocksize); 1797b9fab919SChris Mason /* 1798b9fab919SChris Mason * if we get -eagain from btrfs_buffer_uptodate, we 1799b9fab919SChris Mason * don't want to return eagain here. That will loop 1800b9fab919SChris Mason * forever 1801b9fab919SChris Mason */ 1802b9fab919SChris Mason if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0) 1803b4ce94deSChris Mason block1 = 0; 1804b4ce94deSChris Mason free_extent_buffer(eb); 1805b4ce94deSChris Mason } 18068c594ea8SChris Mason if (slot + 1 < nritems) { 1807b4ce94deSChris Mason block2 = btrfs_node_blockptr(parent, slot + 1); 1808b4ce94deSChris Mason gen = btrfs_node_ptr_generation(parent, slot + 1); 1809b4ce94deSChris Mason eb = btrfs_find_tree_block(root, block2, blocksize); 1810b9fab919SChris Mason if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0) 1811b4ce94deSChris Mason block2 = 0; 1812b4ce94deSChris Mason free_extent_buffer(eb); 1813b4ce94deSChris Mason } 1814b4ce94deSChris Mason if (block1 || block2) { 1815b4ce94deSChris Mason ret = -EAGAIN; 18168c594ea8SChris Mason 18178c594ea8SChris Mason /* release the whole path */ 1818b3b4aa74SDavid Sterba btrfs_release_path(path); 18198c594ea8SChris Mason 18208c594ea8SChris Mason /* read the blocks */ 1821b4ce94deSChris Mason if (block1) 1822b4ce94deSChris Mason readahead_tree_block(root, block1, blocksize, 0); 1823b4ce94deSChris Mason if (block2) 1824b4ce94deSChris Mason readahead_tree_block(root, block2, blocksize, 0); 1825b4ce94deSChris Mason 1826b4ce94deSChris Mason if (block1) { 1827b4ce94deSChris Mason eb = read_tree_block(root, block1, blocksize, 0); 1828b4ce94deSChris Mason free_extent_buffer(eb); 1829b4ce94deSChris Mason } 18308c594ea8SChris Mason if (block2) { 1831b4ce94deSChris Mason eb = read_tree_block(root, block2, blocksize, 0); 1832b4ce94deSChris Mason free_extent_buffer(eb); 1833b4ce94deSChris Mason } 1834b4ce94deSChris Mason } 1835b4ce94deSChris Mason return ret; 1836b4ce94deSChris Mason } 1837b4ce94deSChris Mason 1838b4ce94deSChris Mason 1839b4ce94deSChris Mason /* 1840d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1841d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1842d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1843d397712bSChris Mason * tree. 1844d352ac68SChris Mason * 1845d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1846d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1847d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1848d352ac68SChris Mason * 1849d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1850d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1851d352ac68SChris Mason */ 1852e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1853f7c79f30SChris Mason int lowest_unlock, int min_write_lock_level, 1854f7c79f30SChris Mason int *write_lock_level) 1855925baeddSChris Mason { 1856925baeddSChris Mason int i; 1857925baeddSChris Mason int skip_level = level; 1858051e1b9fSChris Mason int no_skips = 0; 1859925baeddSChris Mason struct extent_buffer *t; 1860925baeddSChris Mason 1861925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1862925baeddSChris Mason if (!path->nodes[i]) 1863925baeddSChris Mason break; 1864925baeddSChris Mason if (!path->locks[i]) 1865925baeddSChris Mason break; 1866051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1867925baeddSChris Mason skip_level = i + 1; 1868925baeddSChris Mason continue; 1869925baeddSChris Mason } 1870051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1871925baeddSChris Mason u32 nritems; 1872925baeddSChris Mason t = path->nodes[i]; 1873925baeddSChris Mason nritems = btrfs_header_nritems(t); 1874051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1875925baeddSChris Mason skip_level = i + 1; 1876925baeddSChris Mason continue; 1877925baeddSChris Mason } 1878925baeddSChris Mason } 1879051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1880051e1b9fSChris Mason no_skips = 1; 1881051e1b9fSChris Mason 1882925baeddSChris Mason t = path->nodes[i]; 1883925baeddSChris Mason if (i >= lowest_unlock && i > skip_level && path->locks[i]) { 1884bd681513SChris Mason btrfs_tree_unlock_rw(t, path->locks[i]); 1885925baeddSChris Mason path->locks[i] = 0; 1886f7c79f30SChris Mason if (write_lock_level && 1887f7c79f30SChris Mason i > min_write_lock_level && 1888f7c79f30SChris Mason i <= *write_lock_level) { 1889f7c79f30SChris Mason *write_lock_level = i - 1; 1890f7c79f30SChris Mason } 1891925baeddSChris Mason } 1892925baeddSChris Mason } 1893925baeddSChris Mason } 1894925baeddSChris Mason 18953c69faecSChris Mason /* 1896b4ce94deSChris Mason * This releases any locks held in the path starting at level and 1897b4ce94deSChris Mason * going all the way up to the root. 1898b4ce94deSChris Mason * 1899b4ce94deSChris Mason * btrfs_search_slot will keep the lock held on higher nodes in a few 1900b4ce94deSChris Mason * corner cases, such as COW of the block at slot zero in the node. This 1901b4ce94deSChris Mason * ignores those rules, and it should only be called when there are no 1902b4ce94deSChris Mason * more updates to be done higher up in the tree. 1903b4ce94deSChris Mason */ 1904b4ce94deSChris Mason noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level) 1905b4ce94deSChris Mason { 1906b4ce94deSChris Mason int i; 1907b4ce94deSChris Mason 19085d4f98a2SYan Zheng if (path->keep_locks) 1909b4ce94deSChris Mason return; 1910b4ce94deSChris Mason 1911b4ce94deSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1912b4ce94deSChris Mason if (!path->nodes[i]) 191312f4daccSChris Mason continue; 1914b4ce94deSChris Mason if (!path->locks[i]) 191512f4daccSChris Mason continue; 1916bd681513SChris Mason btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]); 1917b4ce94deSChris Mason path->locks[i] = 0; 1918b4ce94deSChris Mason } 1919b4ce94deSChris Mason } 1920b4ce94deSChris Mason 1921b4ce94deSChris Mason /* 1922c8c42864SChris Mason * helper function for btrfs_search_slot. The goal is to find a block 1923c8c42864SChris Mason * in cache without setting the path to blocking. If we find the block 1924c8c42864SChris Mason * we return zero and the path is unchanged. 1925c8c42864SChris Mason * 1926c8c42864SChris Mason * If we can't find the block, we set the path blocking and do some 1927c8c42864SChris Mason * reada. -EAGAIN is returned and the search must be repeated. 1928c8c42864SChris Mason */ 1929c8c42864SChris Mason static int 1930c8c42864SChris Mason read_block_for_search(struct btrfs_trans_handle *trans, 1931c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1932c8c42864SChris Mason struct extent_buffer **eb_ret, int level, int slot, 1933c8c42864SChris Mason struct btrfs_key *key) 1934c8c42864SChris Mason { 1935c8c42864SChris Mason u64 blocknr; 1936c8c42864SChris Mason u64 gen; 1937c8c42864SChris Mason u32 blocksize; 1938c8c42864SChris Mason struct extent_buffer *b = *eb_ret; 1939c8c42864SChris Mason struct extent_buffer *tmp; 194076a05b35SChris Mason int ret; 1941c8c42864SChris Mason 1942c8c42864SChris Mason blocknr = btrfs_node_blockptr(b, slot); 1943c8c42864SChris Mason gen = btrfs_node_ptr_generation(b, slot); 1944c8c42864SChris Mason blocksize = btrfs_level_size(root, level - 1); 1945c8c42864SChris Mason 1946c8c42864SChris Mason tmp = btrfs_find_tree_block(root, blocknr, blocksize); 1947cb44921aSChris Mason if (tmp) { 1948b9fab919SChris Mason /* first we do an atomic uptodate check */ 1949b9fab919SChris Mason if (btrfs_buffer_uptodate(tmp, 0, 1) > 0) { 1950b9fab919SChris Mason if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) { 195176a05b35SChris Mason /* 1952cb44921aSChris Mason * we found an up to date block without 1953cb44921aSChris Mason * sleeping, return 195476a05b35SChris Mason * right away 195576a05b35SChris Mason */ 1956c8c42864SChris Mason *eb_ret = tmp; 1957c8c42864SChris Mason return 0; 1958c8c42864SChris Mason } 1959cb44921aSChris Mason /* the pages were up to date, but we failed 1960cb44921aSChris Mason * the generation number check. Do a full 1961cb44921aSChris Mason * read for the generation number that is correct. 1962cb44921aSChris Mason * We must do this without dropping locks so 1963cb44921aSChris Mason * we can trust our generation number 1964cb44921aSChris Mason */ 1965cb44921aSChris Mason free_extent_buffer(tmp); 1966bd681513SChris Mason btrfs_set_path_blocking(p); 1967bd681513SChris Mason 1968b9fab919SChris Mason /* now we're allowed to do a blocking uptodate check */ 1969cb44921aSChris Mason tmp = read_tree_block(root, blocknr, blocksize, gen); 1970b9fab919SChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen, 0) > 0) { 1971cb44921aSChris Mason *eb_ret = tmp; 1972cb44921aSChris Mason return 0; 1973cb44921aSChris Mason } 1974cb44921aSChris Mason free_extent_buffer(tmp); 1975b3b4aa74SDavid Sterba btrfs_release_path(p); 1976cb44921aSChris Mason return -EIO; 1977cb44921aSChris Mason } 1978cb44921aSChris Mason } 1979c8c42864SChris Mason 1980c8c42864SChris Mason /* 1981c8c42864SChris Mason * reduce lock contention at high levels 1982c8c42864SChris Mason * of the btree by dropping locks before 198376a05b35SChris Mason * we read. Don't release the lock on the current 198476a05b35SChris Mason * level because we need to walk this node to figure 198576a05b35SChris Mason * out which blocks to read. 1986c8c42864SChris Mason */ 19878c594ea8SChris Mason btrfs_unlock_up_safe(p, level + 1); 19888c594ea8SChris Mason btrfs_set_path_blocking(p); 19898c594ea8SChris Mason 1990c8c42864SChris Mason free_extent_buffer(tmp); 1991c8c42864SChris Mason if (p->reada) 1992c8c42864SChris Mason reada_for_search(root, p, level, slot, key->objectid); 1993c8c42864SChris Mason 1994b3b4aa74SDavid Sterba btrfs_release_path(p); 199576a05b35SChris Mason 199676a05b35SChris Mason ret = -EAGAIN; 19975bdd3536SYan, Zheng tmp = read_tree_block(root, blocknr, blocksize, 0); 199876a05b35SChris Mason if (tmp) { 199976a05b35SChris Mason /* 200076a05b35SChris Mason * If the read above didn't mark this buffer up to date, 200176a05b35SChris Mason * it will never end up being up to date. Set ret to EIO now 200276a05b35SChris Mason * and give up so that our caller doesn't loop forever 200376a05b35SChris Mason * on our EAGAINs. 200476a05b35SChris Mason */ 2005b9fab919SChris Mason if (!btrfs_buffer_uptodate(tmp, 0, 0)) 200676a05b35SChris Mason ret = -EIO; 2007c8c42864SChris Mason free_extent_buffer(tmp); 200876a05b35SChris Mason } 200976a05b35SChris Mason return ret; 2010c8c42864SChris Mason } 2011c8c42864SChris Mason 2012c8c42864SChris Mason /* 2013c8c42864SChris Mason * helper function for btrfs_search_slot. This does all of the checks 2014c8c42864SChris Mason * for node-level blocks and does any balancing required based on 2015c8c42864SChris Mason * the ins_len. 2016c8c42864SChris Mason * 2017c8c42864SChris Mason * If no extra work was required, zero is returned. If we had to 2018c8c42864SChris Mason * drop the path, -EAGAIN is returned and btrfs_search_slot must 2019c8c42864SChris Mason * start over 2020c8c42864SChris Mason */ 2021c8c42864SChris Mason static int 2022c8c42864SChris Mason setup_nodes_for_search(struct btrfs_trans_handle *trans, 2023c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 2024bd681513SChris Mason struct extent_buffer *b, int level, int ins_len, 2025bd681513SChris Mason int *write_lock_level) 2026c8c42864SChris Mason { 2027c8c42864SChris Mason int ret; 2028c8c42864SChris Mason if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= 2029c8c42864SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) { 2030c8c42864SChris Mason int sret; 2031c8c42864SChris Mason 2032bd681513SChris Mason if (*write_lock_level < level + 1) { 2033bd681513SChris Mason *write_lock_level = level + 1; 2034bd681513SChris Mason btrfs_release_path(p); 2035bd681513SChris Mason goto again; 2036bd681513SChris Mason } 2037bd681513SChris Mason 2038c8c42864SChris Mason sret = reada_for_balance(root, p, level); 2039c8c42864SChris Mason if (sret) 2040c8c42864SChris Mason goto again; 2041c8c42864SChris Mason 2042c8c42864SChris Mason btrfs_set_path_blocking(p); 2043c8c42864SChris Mason sret = split_node(trans, root, p, level); 2044bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 2045c8c42864SChris Mason 2046c8c42864SChris Mason BUG_ON(sret > 0); 2047c8c42864SChris Mason if (sret) { 2048c8c42864SChris Mason ret = sret; 2049c8c42864SChris Mason goto done; 2050c8c42864SChris Mason } 2051c8c42864SChris Mason b = p->nodes[level]; 2052c8c42864SChris Mason } else if (ins_len < 0 && btrfs_header_nritems(b) < 2053cfbb9308SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 2) { 2054c8c42864SChris Mason int sret; 2055c8c42864SChris Mason 2056bd681513SChris Mason if (*write_lock_level < level + 1) { 2057bd681513SChris Mason *write_lock_level = level + 1; 2058bd681513SChris Mason btrfs_release_path(p); 2059bd681513SChris Mason goto again; 2060bd681513SChris Mason } 2061bd681513SChris Mason 2062c8c42864SChris Mason sret = reada_for_balance(root, p, level); 2063c8c42864SChris Mason if (sret) 2064c8c42864SChris Mason goto again; 2065c8c42864SChris Mason 2066c8c42864SChris Mason btrfs_set_path_blocking(p); 2067c8c42864SChris Mason sret = balance_level(trans, root, p, level); 2068bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 2069c8c42864SChris Mason 2070c8c42864SChris Mason if (sret) { 2071c8c42864SChris Mason ret = sret; 2072c8c42864SChris Mason goto done; 2073c8c42864SChris Mason } 2074c8c42864SChris Mason b = p->nodes[level]; 2075c8c42864SChris Mason if (!b) { 2076b3b4aa74SDavid Sterba btrfs_release_path(p); 2077c8c42864SChris Mason goto again; 2078c8c42864SChris Mason } 2079c8c42864SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 2080c8c42864SChris Mason } 2081c8c42864SChris Mason return 0; 2082c8c42864SChris Mason 2083c8c42864SChris Mason again: 2084c8c42864SChris Mason ret = -EAGAIN; 2085c8c42864SChris Mason done: 2086c8c42864SChris Mason return ret; 2087c8c42864SChris Mason } 2088c8c42864SChris Mason 2089c8c42864SChris Mason /* 209074123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 209174123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 209274123bd7SChris Mason * level of the path (level 0) 209374123bd7SChris Mason * 209474123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 2095aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 2096aa5d6bedSChris Mason * search a negative error number is returned. 209797571fd0SChris Mason * 209897571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 209997571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 210097571fd0SChris Mason * possible) 210174123bd7SChris Mason */ 2102e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 2103e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 2104e089f05cSChris Mason ins_len, int cow) 2105be0e5c09SChris Mason { 21065f39d397SChris Mason struct extent_buffer *b; 2107be0e5c09SChris Mason int slot; 2108be0e5c09SChris Mason int ret; 210933c66f43SYan Zheng int err; 2110be0e5c09SChris Mason int level; 2111925baeddSChris Mason int lowest_unlock = 1; 2112bd681513SChris Mason int root_lock; 2113bd681513SChris Mason /* everything at write_lock_level or lower must be write locked */ 2114bd681513SChris Mason int write_lock_level = 0; 21159f3a7427SChris Mason u8 lowest_level = 0; 2116f7c79f30SChris Mason int min_write_lock_level; 21179f3a7427SChris Mason 21186702ed49SChris Mason lowest_level = p->lowest_level; 2119323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 212022b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 212125179201SJosef Bacik 2122bd681513SChris Mason if (ins_len < 0) { 2123925baeddSChris Mason lowest_unlock = 2; 212465b51a00SChris Mason 2125bd681513SChris Mason /* when we are removing items, we might have to go up to level 2126bd681513SChris Mason * two as we update tree pointers Make sure we keep write 2127bd681513SChris Mason * for those levels as well 2128bd681513SChris Mason */ 2129bd681513SChris Mason write_lock_level = 2; 2130bd681513SChris Mason } else if (ins_len > 0) { 2131bd681513SChris Mason /* 2132bd681513SChris Mason * for inserting items, make sure we have a write lock on 2133bd681513SChris Mason * level 1 so we can update keys 2134bd681513SChris Mason */ 2135bd681513SChris Mason write_lock_level = 1; 2136bd681513SChris Mason } 2137bd681513SChris Mason 2138bd681513SChris Mason if (!cow) 2139bd681513SChris Mason write_lock_level = -1; 2140bd681513SChris Mason 2141bd681513SChris Mason if (cow && (p->keep_locks || p->lowest_level)) 2142bd681513SChris Mason write_lock_level = BTRFS_MAX_LEVEL; 2143bd681513SChris Mason 2144f7c79f30SChris Mason min_write_lock_level = write_lock_level; 2145f7c79f30SChris Mason 2146bb803951SChris Mason again: 2147bd681513SChris Mason /* 2148bd681513SChris Mason * we try very hard to do read locks on the root 2149bd681513SChris Mason */ 2150bd681513SChris Mason root_lock = BTRFS_READ_LOCK; 2151bd681513SChris Mason level = 0; 21525d4f98a2SYan Zheng if (p->search_commit_root) { 2153bd681513SChris Mason /* 2154bd681513SChris Mason * the commit roots are read only 2155bd681513SChris Mason * so we always do read locks 2156bd681513SChris Mason */ 21575d4f98a2SYan Zheng b = root->commit_root; 21585d4f98a2SYan Zheng extent_buffer_get(b); 2159bd681513SChris Mason level = btrfs_header_level(b); 21605d4f98a2SYan Zheng if (!p->skip_locking) 2161bd681513SChris Mason btrfs_tree_read_lock(b); 21625d4f98a2SYan Zheng } else { 2163bd681513SChris Mason if (p->skip_locking) { 21645cd57b2cSChris Mason b = btrfs_root_node(root); 2165bd681513SChris Mason level = btrfs_header_level(b); 2166bd681513SChris Mason } else { 2167bd681513SChris Mason /* we don't know the level of the root node 2168bd681513SChris Mason * until we actually have it read locked 2169bd681513SChris Mason */ 2170bd681513SChris Mason b = btrfs_read_lock_root_node(root); 2171bd681513SChris Mason level = btrfs_header_level(b); 2172bd681513SChris Mason if (level <= write_lock_level) { 2173bd681513SChris Mason /* whoops, must trade for write lock */ 2174bd681513SChris Mason btrfs_tree_read_unlock(b); 2175bd681513SChris Mason free_extent_buffer(b); 2176925baeddSChris Mason b = btrfs_lock_root_node(root); 2177bd681513SChris Mason root_lock = BTRFS_WRITE_LOCK; 2178bd681513SChris Mason 2179bd681513SChris Mason /* the level might have changed, check again */ 2180bd681513SChris Mason level = btrfs_header_level(b); 21815d4f98a2SYan Zheng } 2182bd681513SChris Mason } 2183bd681513SChris Mason } 2184bd681513SChris Mason p->nodes[level] = b; 2185bd681513SChris Mason if (!p->skip_locking) 2186bd681513SChris Mason p->locks[level] = root_lock; 2187925baeddSChris Mason 2188eb60ceacSChris Mason while (b) { 21895f39d397SChris Mason level = btrfs_header_level(b); 219065b51a00SChris Mason 219165b51a00SChris Mason /* 219265b51a00SChris Mason * setup the path here so we can release it under lock 219365b51a00SChris Mason * contention with the cow code 219465b51a00SChris Mason */ 219502217ed2SChris Mason if (cow) { 2196c8c42864SChris Mason /* 2197c8c42864SChris Mason * if we don't really need to cow this block 2198c8c42864SChris Mason * then we don't want to set the path blocking, 2199c8c42864SChris Mason * so we test it here 2200c8c42864SChris Mason */ 22015d4f98a2SYan Zheng if (!should_cow_block(trans, root, b)) 220265b51a00SChris Mason goto cow_done; 22035d4f98a2SYan Zheng 2204b4ce94deSChris Mason btrfs_set_path_blocking(p); 2205b4ce94deSChris Mason 2206bd681513SChris Mason /* 2207bd681513SChris Mason * must have write locks on this node and the 2208bd681513SChris Mason * parent 2209bd681513SChris Mason */ 2210bd681513SChris Mason if (level + 1 > write_lock_level) { 2211bd681513SChris Mason write_lock_level = level + 1; 2212bd681513SChris Mason btrfs_release_path(p); 2213bd681513SChris Mason goto again; 2214bd681513SChris Mason } 2215bd681513SChris Mason 221633c66f43SYan Zheng err = btrfs_cow_block(trans, root, b, 2217e20d96d6SChris Mason p->nodes[level + 1], 22189fa8cfe7SChris Mason p->slots[level + 1], &b); 221933c66f43SYan Zheng if (err) { 222033c66f43SYan Zheng ret = err; 222165b51a00SChris Mason goto done; 222254aa1f4dSChris Mason } 222302217ed2SChris Mason } 222465b51a00SChris Mason cow_done: 222502217ed2SChris Mason BUG_ON(!cow && ins_len); 222665b51a00SChris Mason 2227eb60ceacSChris Mason p->nodes[level] = b; 2228bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 2229b4ce94deSChris Mason 2230b4ce94deSChris Mason /* 2231b4ce94deSChris Mason * we have a lock on b and as long as we aren't changing 2232b4ce94deSChris Mason * the tree, there is no way to for the items in b to change. 2233b4ce94deSChris Mason * It is safe to drop the lock on our parent before we 2234b4ce94deSChris Mason * go through the expensive btree search on b. 2235b4ce94deSChris Mason * 2236b4ce94deSChris Mason * If cow is true, then we might be changing slot zero, 2237b4ce94deSChris Mason * which may require changing the parent. So, we can't 2238b4ce94deSChris Mason * drop the lock until after we know which slot we're 2239b4ce94deSChris Mason * operating on. 2240b4ce94deSChris Mason */ 2241b4ce94deSChris Mason if (!cow) 2242b4ce94deSChris Mason btrfs_unlock_up_safe(p, level + 1); 2243b4ce94deSChris Mason 22445f39d397SChris Mason ret = bin_search(b, key, level, &slot); 2245b4ce94deSChris Mason 22465f39d397SChris Mason if (level != 0) { 224733c66f43SYan Zheng int dec = 0; 224833c66f43SYan Zheng if (ret && slot > 0) { 224933c66f43SYan Zheng dec = 1; 2250be0e5c09SChris Mason slot -= 1; 225133c66f43SYan Zheng } 2252be0e5c09SChris Mason p->slots[level] = slot; 225333c66f43SYan Zheng err = setup_nodes_for_search(trans, root, p, b, level, 2254bd681513SChris Mason ins_len, &write_lock_level); 225533c66f43SYan Zheng if (err == -EAGAIN) 2256b4ce94deSChris Mason goto again; 225733c66f43SYan Zheng if (err) { 225833c66f43SYan Zheng ret = err; 225965b51a00SChris Mason goto done; 226033c66f43SYan Zheng } 22615c680ed6SChris Mason b = p->nodes[level]; 22625c680ed6SChris Mason slot = p->slots[level]; 2263b4ce94deSChris Mason 2264bd681513SChris Mason /* 2265bd681513SChris Mason * slot 0 is special, if we change the key 2266bd681513SChris Mason * we have to update the parent pointer 2267bd681513SChris Mason * which means we must have a write lock 2268bd681513SChris Mason * on the parent 2269bd681513SChris Mason */ 2270bd681513SChris Mason if (slot == 0 && cow && 2271bd681513SChris Mason write_lock_level < level + 1) { 2272bd681513SChris Mason write_lock_level = level + 1; 2273bd681513SChris Mason btrfs_release_path(p); 2274bd681513SChris Mason goto again; 2275bd681513SChris Mason } 2276bd681513SChris Mason 2277f7c79f30SChris Mason unlock_up(p, level, lowest_unlock, 2278f7c79f30SChris Mason min_write_lock_level, &write_lock_level); 2279f9efa9c7SChris Mason 2280925baeddSChris Mason if (level == lowest_level) { 228133c66f43SYan Zheng if (dec) 228233c66f43SYan Zheng p->slots[level]++; 22835b21f2edSZheng Yan goto done; 2284925baeddSChris Mason } 2285ca7a79adSChris Mason 228633c66f43SYan Zheng err = read_block_for_search(trans, root, p, 2287c8c42864SChris Mason &b, level, slot, key); 228833c66f43SYan Zheng if (err == -EAGAIN) 2289051e1b9fSChris Mason goto again; 229033c66f43SYan Zheng if (err) { 229133c66f43SYan Zheng ret = err; 229276a05b35SChris Mason goto done; 229333c66f43SYan Zheng } 229476a05b35SChris Mason 2295b4ce94deSChris Mason if (!p->skip_locking) { 2296bd681513SChris Mason level = btrfs_header_level(b); 2297bd681513SChris Mason if (level <= write_lock_level) { 2298bd681513SChris Mason err = btrfs_try_tree_write_lock(b); 229933c66f43SYan Zheng if (!err) { 2300b4ce94deSChris Mason btrfs_set_path_blocking(p); 2301925baeddSChris Mason btrfs_tree_lock(b); 2302bd681513SChris Mason btrfs_clear_path_blocking(p, b, 2303bd681513SChris Mason BTRFS_WRITE_LOCK); 2304b4ce94deSChris Mason } 2305bd681513SChris Mason p->locks[level] = BTRFS_WRITE_LOCK; 2306bd681513SChris Mason } else { 2307bd681513SChris Mason err = btrfs_try_tree_read_lock(b); 2308bd681513SChris Mason if (!err) { 2309bd681513SChris Mason btrfs_set_path_blocking(p); 2310bd681513SChris Mason btrfs_tree_read_lock(b); 2311bd681513SChris Mason btrfs_clear_path_blocking(p, b, 2312bd681513SChris Mason BTRFS_READ_LOCK); 2313bd681513SChris Mason } 2314bd681513SChris Mason p->locks[level] = BTRFS_READ_LOCK; 2315bd681513SChris Mason } 2316bd681513SChris Mason p->nodes[level] = b; 2317b4ce94deSChris Mason } 2318be0e5c09SChris Mason } else { 2319be0e5c09SChris Mason p->slots[level] = slot; 232087b29b20SYan Zheng if (ins_len > 0 && 232187b29b20SYan Zheng btrfs_leaf_free_space(root, b) < ins_len) { 2322bd681513SChris Mason if (write_lock_level < 1) { 2323bd681513SChris Mason write_lock_level = 1; 2324bd681513SChris Mason btrfs_release_path(p); 2325bd681513SChris Mason goto again; 2326bd681513SChris Mason } 2327bd681513SChris Mason 2328b4ce94deSChris Mason btrfs_set_path_blocking(p); 232933c66f43SYan Zheng err = split_leaf(trans, root, key, 2330cc0c5538SChris Mason p, ins_len, ret == 0); 2331bd681513SChris Mason btrfs_clear_path_blocking(p, NULL, 0); 2332b4ce94deSChris Mason 233333c66f43SYan Zheng BUG_ON(err > 0); 233433c66f43SYan Zheng if (err) { 233533c66f43SYan Zheng ret = err; 233665b51a00SChris Mason goto done; 233765b51a00SChris Mason } 23385c680ed6SChris Mason } 2339459931ecSChris Mason if (!p->search_for_split) 2340f7c79f30SChris Mason unlock_up(p, level, lowest_unlock, 2341f7c79f30SChris Mason min_write_lock_level, &write_lock_level); 234265b51a00SChris Mason goto done; 234365b51a00SChris Mason } 234465b51a00SChris Mason } 234565b51a00SChris Mason ret = 1; 234665b51a00SChris Mason done: 2347b4ce94deSChris Mason /* 2348b4ce94deSChris Mason * we don't really know what they plan on doing with the path 2349b4ce94deSChris Mason * from here on, so for now just mark it as blocking 2350b4ce94deSChris Mason */ 2351b9473439SChris Mason if (!p->leave_spinning) 2352b4ce94deSChris Mason btrfs_set_path_blocking(p); 235376a05b35SChris Mason if (ret < 0) 2354b3b4aa74SDavid Sterba btrfs_release_path(p); 2355be0e5c09SChris Mason return ret; 2356be0e5c09SChris Mason } 2357be0e5c09SChris Mason 235874123bd7SChris Mason /* 235974123bd7SChris Mason * adjust the pointers going up the tree, starting at level 236074123bd7SChris Mason * making sure the right key of each node is points to 'key'. 236174123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 236274123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 236374123bd7SChris Mason * higher levels 2364aa5d6bedSChris Mason * 236574123bd7SChris Mason */ 2366143bede5SJeff Mahoney static void fixup_low_keys(struct btrfs_trans_handle *trans, 23675f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 23685f39d397SChris Mason struct btrfs_disk_key *key, int level) 2369be0e5c09SChris Mason { 2370be0e5c09SChris Mason int i; 23715f39d397SChris Mason struct extent_buffer *t; 23725f39d397SChris Mason 2373234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 2374be0e5c09SChris Mason int tslot = path->slots[i]; 2375eb60ceacSChris Mason if (!path->nodes[i]) 2376be0e5c09SChris Mason break; 23775f39d397SChris Mason t = path->nodes[i]; 2378f230475eSJan Schmidt tree_mod_log_set_node_key(root->fs_info, t, key, tslot, 1); 23795f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 2380d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 2381be0e5c09SChris Mason if (tslot != 0) 2382be0e5c09SChris Mason break; 2383be0e5c09SChris Mason } 2384be0e5c09SChris Mason } 2385be0e5c09SChris Mason 238674123bd7SChris Mason /* 238731840ae1SZheng Yan * update item key. 238831840ae1SZheng Yan * 238931840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 239031840ae1SZheng Yan * that the new key won't break the order 239131840ae1SZheng Yan */ 2392143bede5SJeff Mahoney void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans, 239331840ae1SZheng Yan struct btrfs_root *root, struct btrfs_path *path, 239431840ae1SZheng Yan struct btrfs_key *new_key) 239531840ae1SZheng Yan { 239631840ae1SZheng Yan struct btrfs_disk_key disk_key; 239731840ae1SZheng Yan struct extent_buffer *eb; 239831840ae1SZheng Yan int slot; 239931840ae1SZheng Yan 240031840ae1SZheng Yan eb = path->nodes[0]; 240131840ae1SZheng Yan slot = path->slots[0]; 240231840ae1SZheng Yan if (slot > 0) { 240331840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 2404143bede5SJeff Mahoney BUG_ON(comp_keys(&disk_key, new_key) >= 0); 240531840ae1SZheng Yan } 240631840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 240731840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 2408143bede5SJeff Mahoney BUG_ON(comp_keys(&disk_key, new_key) <= 0); 240931840ae1SZheng Yan } 241031840ae1SZheng Yan 241131840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 241231840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 241331840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 241431840ae1SZheng Yan if (slot == 0) 241531840ae1SZheng Yan fixup_low_keys(trans, root, path, &disk_key, 1); 241631840ae1SZheng Yan } 241731840ae1SZheng Yan 241831840ae1SZheng Yan /* 241974123bd7SChris Mason * try to push data from one node into the next node left in the 242079f95c82SChris Mason * tree. 2421aa5d6bedSChris Mason * 2422aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 2423aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 242474123bd7SChris Mason */ 242598ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 242698ed5174SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 2427971a1f66SChris Mason struct extent_buffer *src, int empty) 2428be0e5c09SChris Mason { 2429be0e5c09SChris Mason int push_items = 0; 2430bb803951SChris Mason int src_nritems; 2431bb803951SChris Mason int dst_nritems; 2432aa5d6bedSChris Mason int ret = 0; 2433be0e5c09SChris Mason 24345f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 24355f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 2436123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 24377bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 24387bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 243954aa1f4dSChris Mason 2440bce4eae9SChris Mason if (!empty && src_nritems <= 8) 2441971a1f66SChris Mason return 1; 2442971a1f66SChris Mason 2443d397712bSChris Mason if (push_items <= 0) 2444be0e5c09SChris Mason return 1; 2445be0e5c09SChris Mason 2446bce4eae9SChris Mason if (empty) { 2447971a1f66SChris Mason push_items = min(src_nritems, push_items); 2448bce4eae9SChris Mason if (push_items < src_nritems) { 2449bce4eae9SChris Mason /* leave at least 8 pointers in the node if 2450bce4eae9SChris Mason * we aren't going to empty it 2451bce4eae9SChris Mason */ 2452bce4eae9SChris Mason if (src_nritems - push_items < 8) { 2453bce4eae9SChris Mason if (push_items <= 8) 2454bce4eae9SChris Mason return 1; 2455bce4eae9SChris Mason push_items -= 8; 2456bce4eae9SChris Mason } 2457bce4eae9SChris Mason } 2458bce4eae9SChris Mason } else 2459bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 246079f95c82SChris Mason 2461f230475eSJan Schmidt tree_mod_log_eb_copy(root->fs_info, dst, src, dst_nritems, 0, 2462f230475eSJan Schmidt push_items); 24635f39d397SChris Mason copy_extent_buffer(dst, src, 24645f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 24655f39d397SChris Mason btrfs_node_key_ptr_offset(0), 2466123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 24675f39d397SChris Mason 2468bb803951SChris Mason if (push_items < src_nritems) { 2469f230475eSJan Schmidt tree_mod_log_eb_move(root->fs_info, src, 0, push_items, 2470f230475eSJan Schmidt src_nritems - push_items); 24715f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 24725f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 2473e2fa7227SChris Mason (src_nritems - push_items) * 2474123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 2475bb803951SChris Mason } 24765f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 24775f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 24785f39d397SChris Mason btrfs_mark_buffer_dirty(src); 24795f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 248031840ae1SZheng Yan 2481bb803951SChris Mason return ret; 2482be0e5c09SChris Mason } 2483be0e5c09SChris Mason 248497571fd0SChris Mason /* 248579f95c82SChris Mason * try to push data from one node into the next node right in the 248679f95c82SChris Mason * tree. 248779f95c82SChris Mason * 248879f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 248979f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 249079f95c82SChris Mason * 249179f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 249279f95c82SChris Mason */ 24935f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 24945f39d397SChris Mason struct btrfs_root *root, 24955f39d397SChris Mason struct extent_buffer *dst, 24965f39d397SChris Mason struct extent_buffer *src) 249779f95c82SChris Mason { 249879f95c82SChris Mason int push_items = 0; 249979f95c82SChris Mason int max_push; 250079f95c82SChris Mason int src_nritems; 250179f95c82SChris Mason int dst_nritems; 250279f95c82SChris Mason int ret = 0; 250379f95c82SChris Mason 25047bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 25057bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 25067bb86316SChris Mason 25075f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 25085f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 2509123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 2510d397712bSChris Mason if (push_items <= 0) 251179f95c82SChris Mason return 1; 2512bce4eae9SChris Mason 2513d397712bSChris Mason if (src_nritems < 4) 2514bce4eae9SChris Mason return 1; 251579f95c82SChris Mason 251679f95c82SChris Mason max_push = src_nritems / 2 + 1; 251779f95c82SChris Mason /* don't try to empty the node */ 2518d397712bSChris Mason if (max_push >= src_nritems) 251979f95c82SChris Mason return 1; 2520252c38f0SYan 252179f95c82SChris Mason if (max_push < push_items) 252279f95c82SChris Mason push_items = max_push; 252379f95c82SChris Mason 2524f230475eSJan Schmidt tree_mod_log_eb_move(root->fs_info, dst, push_items, 0, dst_nritems); 25255f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 25265f39d397SChris Mason btrfs_node_key_ptr_offset(0), 25275f39d397SChris Mason (dst_nritems) * 25285f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 2529d6025579SChris Mason 2530f230475eSJan Schmidt tree_mod_log_eb_copy(root->fs_info, dst, src, 0, 2531f230475eSJan Schmidt src_nritems - push_items, push_items); 25325f39d397SChris Mason copy_extent_buffer(dst, src, 25335f39d397SChris Mason btrfs_node_key_ptr_offset(0), 25345f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 2535123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 253679f95c82SChris Mason 25375f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 25385f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 253979f95c82SChris Mason 25405f39d397SChris Mason btrfs_mark_buffer_dirty(src); 25415f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 254231840ae1SZheng Yan 254379f95c82SChris Mason return ret; 254479f95c82SChris Mason } 254579f95c82SChris Mason 254679f95c82SChris Mason /* 254797571fd0SChris Mason * helper function to insert a new root level in the tree. 254897571fd0SChris Mason * A new node is allocated, and a single item is inserted to 254997571fd0SChris Mason * point to the existing root 2550aa5d6bedSChris Mason * 2551aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 255297571fd0SChris Mason */ 2553d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 25545f39d397SChris Mason struct btrfs_root *root, 25555f39d397SChris Mason struct btrfs_path *path, int level) 255674123bd7SChris Mason { 25577bb86316SChris Mason u64 lower_gen; 25585f39d397SChris Mason struct extent_buffer *lower; 25595f39d397SChris Mason struct extent_buffer *c; 2560925baeddSChris Mason struct extent_buffer *old; 25615f39d397SChris Mason struct btrfs_disk_key lower_key; 25625c680ed6SChris Mason 25635c680ed6SChris Mason BUG_ON(path->nodes[level]); 25645c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 25655c680ed6SChris Mason 25667bb86316SChris Mason lower = path->nodes[level-1]; 25677bb86316SChris Mason if (level == 1) 25687bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 25697bb86316SChris Mason else 25707bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 25717bb86316SChris Mason 257231840ae1SZheng Yan c = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 25735d4f98a2SYan Zheng root->root_key.objectid, &lower_key, 25745581a51aSJan Schmidt level, root->node->start, 0); 25755f39d397SChris Mason if (IS_ERR(c)) 25765f39d397SChris Mason return PTR_ERR(c); 2577925baeddSChris Mason 2578f0486c68SYan, Zheng root_add_used(root, root->nodesize); 2579f0486c68SYan, Zheng 25805d4f98a2SYan Zheng memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header)); 25815f39d397SChris Mason btrfs_set_header_nritems(c, 1); 25825f39d397SChris Mason btrfs_set_header_level(c, level); 2583db94535dSChris Mason btrfs_set_header_bytenr(c, c->start); 25845f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 25855d4f98a2SYan Zheng btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV); 25865f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 2587d5719762SChris Mason 25885f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 25895f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 25905f39d397SChris Mason BTRFS_FSID_SIZE); 2591e17cade2SChris Mason 2592e17cade2SChris Mason write_extent_buffer(c, root->fs_info->chunk_tree_uuid, 2593e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(c), 2594e17cade2SChris Mason BTRFS_UUID_SIZE); 2595e17cade2SChris Mason 25965f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 2597db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 25987bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 259931840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 26007bb86316SChris Mason 26017bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 26025f39d397SChris Mason 26035f39d397SChris Mason btrfs_mark_buffer_dirty(c); 2604d5719762SChris Mason 2605925baeddSChris Mason old = root->node; 2606f230475eSJan Schmidt tree_mod_log_set_root_pointer(root, c); 2607240f62c8SChris Mason rcu_assign_pointer(root->node, c); 2608925baeddSChris Mason 2609925baeddSChris Mason /* the super has an extra ref to root->node */ 2610925baeddSChris Mason free_extent_buffer(old); 2611925baeddSChris Mason 26120b86a832SChris Mason add_root_to_dirty_list(root); 26135f39d397SChris Mason extent_buffer_get(c); 26145f39d397SChris Mason path->nodes[level] = c; 2615bd681513SChris Mason path->locks[level] = BTRFS_WRITE_LOCK; 261674123bd7SChris Mason path->slots[level] = 0; 261774123bd7SChris Mason return 0; 261874123bd7SChris Mason } 26195c680ed6SChris Mason 26205c680ed6SChris Mason /* 26215c680ed6SChris Mason * worker function to insert a single pointer in a node. 26225c680ed6SChris Mason * the node should have enough room for the pointer already 262397571fd0SChris Mason * 26245c680ed6SChris Mason * slot and level indicate where you want the key to go, and 26255c680ed6SChris Mason * blocknr is the block the key points to. 26265c680ed6SChris Mason */ 2627143bede5SJeff Mahoney static void insert_ptr(struct btrfs_trans_handle *trans, 2628143bede5SJeff Mahoney struct btrfs_root *root, struct btrfs_path *path, 2629143bede5SJeff Mahoney struct btrfs_disk_key *key, u64 bytenr, 2630f3ea38daSJan Schmidt int slot, int level, int tree_mod_log) 26315c680ed6SChris Mason { 26325f39d397SChris Mason struct extent_buffer *lower; 26335c680ed6SChris Mason int nritems; 2634f3ea38daSJan Schmidt int ret; 26355c680ed6SChris Mason 26365c680ed6SChris Mason BUG_ON(!path->nodes[level]); 2637f0486c68SYan, Zheng btrfs_assert_tree_locked(path->nodes[level]); 26385f39d397SChris Mason lower = path->nodes[level]; 26395f39d397SChris Mason nritems = btrfs_header_nritems(lower); 2640c293498bSStoyan Gaydarov BUG_ON(slot > nritems); 2641143bede5SJeff Mahoney BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(root)); 264274123bd7SChris Mason if (slot != nritems) { 2643f3ea38daSJan Schmidt if (tree_mod_log && level) 2644f3ea38daSJan Schmidt tree_mod_log_eb_move(root->fs_info, lower, slot + 1, 2645f3ea38daSJan Schmidt slot, nritems - slot); 26465f39d397SChris Mason memmove_extent_buffer(lower, 26475f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 26485f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 2649123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 265074123bd7SChris Mason } 2651f3ea38daSJan Schmidt if (tree_mod_log && level) { 2652f3ea38daSJan Schmidt ret = tree_mod_log_insert_key(root->fs_info, lower, slot, 2653f3ea38daSJan Schmidt MOD_LOG_KEY_ADD); 2654f3ea38daSJan Schmidt BUG_ON(ret < 0); 2655f3ea38daSJan Schmidt } 26565f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 2657db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 265874493f7aSChris Mason WARN_ON(trans->transid == 0); 265974493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 26605f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 26615f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 266274123bd7SChris Mason } 266374123bd7SChris Mason 266497571fd0SChris Mason /* 266597571fd0SChris Mason * split the node at the specified level in path in two. 266697571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 266797571fd0SChris Mason * 266897571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 266997571fd0SChris Mason * left and right, if either one works, it returns right away. 2670aa5d6bedSChris Mason * 2671aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 267297571fd0SChris Mason */ 2673e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 2674e02119d5SChris Mason struct btrfs_root *root, 2675e02119d5SChris Mason struct btrfs_path *path, int level) 2676be0e5c09SChris Mason { 26775f39d397SChris Mason struct extent_buffer *c; 26785f39d397SChris Mason struct extent_buffer *split; 26795f39d397SChris Mason struct btrfs_disk_key disk_key; 2680be0e5c09SChris Mason int mid; 26815c680ed6SChris Mason int ret; 26827518a238SChris Mason u32 c_nritems; 2683be0e5c09SChris Mason 26845f39d397SChris Mason c = path->nodes[level]; 26857bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 26865f39d397SChris Mason if (c == root->node) { 26875c680ed6SChris Mason /* trying to split the root, lets make a new one */ 2688e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 26895c680ed6SChris Mason if (ret) 26905c680ed6SChris Mason return ret; 2691b3612421SChris Mason } else { 2692e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 26935f39d397SChris Mason c = path->nodes[level]; 26945f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 2695c448acf0SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 3) 2696e66f709bSChris Mason return 0; 269754aa1f4dSChris Mason if (ret < 0) 269854aa1f4dSChris Mason return ret; 26995c680ed6SChris Mason } 2700e66f709bSChris Mason 27015f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 27025d4f98a2SYan Zheng mid = (c_nritems + 1) / 2; 27035d4f98a2SYan Zheng btrfs_node_key(c, &disk_key, mid); 27047bb86316SChris Mason 27055d4f98a2SYan Zheng split = btrfs_alloc_free_block(trans, root, root->nodesize, 0, 27067bb86316SChris Mason root->root_key.objectid, 27075581a51aSJan Schmidt &disk_key, level, c->start, 0); 27085f39d397SChris Mason if (IS_ERR(split)) 27095f39d397SChris Mason return PTR_ERR(split); 271054aa1f4dSChris Mason 2711f0486c68SYan, Zheng root_add_used(root, root->nodesize); 2712f0486c68SYan, Zheng 27135d4f98a2SYan Zheng memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header)); 27145f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 2715db94535dSChris Mason btrfs_set_header_bytenr(split, split->start); 27165f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 27175d4f98a2SYan Zheng btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV); 27185f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 27195f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 27205f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 27215f39d397SChris Mason BTRFS_FSID_SIZE); 2722e17cade2SChris Mason write_extent_buffer(split, root->fs_info->chunk_tree_uuid, 2723e17cade2SChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(split), 2724e17cade2SChris Mason BTRFS_UUID_SIZE); 27255f39d397SChris Mason 2726f230475eSJan Schmidt tree_mod_log_eb_copy(root->fs_info, split, c, 0, mid, c_nritems - mid); 27275f39d397SChris Mason copy_extent_buffer(split, c, 27285f39d397SChris Mason btrfs_node_key_ptr_offset(0), 27295f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2730123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 27315f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 27325f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2733aa5d6bedSChris Mason ret = 0; 2734aa5d6bedSChris Mason 27355f39d397SChris Mason btrfs_mark_buffer_dirty(c); 27365f39d397SChris Mason btrfs_mark_buffer_dirty(split); 27375f39d397SChris Mason 2738143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, split->start, 2739f3ea38daSJan Schmidt path->slots[level + 1] + 1, level + 1, 1); 2740aa5d6bedSChris Mason 27415de08d7dSChris Mason if (path->slots[level] >= mid) { 27425c680ed6SChris Mason path->slots[level] -= mid; 2743925baeddSChris Mason btrfs_tree_unlock(c); 27445f39d397SChris Mason free_extent_buffer(c); 27455f39d397SChris Mason path->nodes[level] = split; 27465c680ed6SChris Mason path->slots[level + 1] += 1; 2747eb60ceacSChris Mason } else { 2748925baeddSChris Mason btrfs_tree_unlock(split); 27495f39d397SChris Mason free_extent_buffer(split); 2750be0e5c09SChris Mason } 2751aa5d6bedSChris Mason return ret; 2752be0e5c09SChris Mason } 2753be0e5c09SChris Mason 275474123bd7SChris Mason /* 275574123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 275674123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 275774123bd7SChris Mason * space used both by the item structs and the item data 275874123bd7SChris Mason */ 27595f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2760be0e5c09SChris Mason { 2761be0e5c09SChris Mason int data_len; 27625f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2763d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2764be0e5c09SChris Mason 2765be0e5c09SChris Mason if (!nr) 2766be0e5c09SChris Mason return 0; 27675f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 27685f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 27690783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2770d4dbff95SChris Mason WARN_ON(data_len < 0); 2771be0e5c09SChris Mason return data_len; 2772be0e5c09SChris Mason } 2773be0e5c09SChris Mason 277474123bd7SChris Mason /* 2775d4dbff95SChris Mason * The space between the end of the leaf items and 2776d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2777d4dbff95SChris Mason * the leaf has left for both items and data 2778d4dbff95SChris Mason */ 2779d397712bSChris Mason noinline int btrfs_leaf_free_space(struct btrfs_root *root, 2780e02119d5SChris Mason struct extent_buffer *leaf) 2781d4dbff95SChris Mason { 27825f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 27835f39d397SChris Mason int ret; 27845f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 27855f39d397SChris Mason if (ret < 0) { 2786d397712bSChris Mason printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, " 2787d397712bSChris Mason "used %d nritems %d\n", 2788ae2f5411SJens Axboe ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), 27895f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 27905f39d397SChris Mason } 27915f39d397SChris Mason return ret; 2792d4dbff95SChris Mason } 2793d4dbff95SChris Mason 279499d8f83cSChris Mason /* 279599d8f83cSChris Mason * min slot controls the lowest index we're willing to push to the 279699d8f83cSChris Mason * right. We'll push up to and including min_slot, but no lower 279799d8f83cSChris Mason */ 279844871b1bSChris Mason static noinline int __push_leaf_right(struct btrfs_trans_handle *trans, 279944871b1bSChris Mason struct btrfs_root *root, 280044871b1bSChris Mason struct btrfs_path *path, 280144871b1bSChris Mason int data_size, int empty, 280244871b1bSChris Mason struct extent_buffer *right, 280399d8f83cSChris Mason int free_space, u32 left_nritems, 280499d8f83cSChris Mason u32 min_slot) 280500ec4c51SChris Mason { 28065f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 280744871b1bSChris Mason struct extent_buffer *upper = path->nodes[1]; 2808cfed81a0SChris Mason struct btrfs_map_token token; 28095f39d397SChris Mason struct btrfs_disk_key disk_key; 281000ec4c51SChris Mason int slot; 281134a38218SChris Mason u32 i; 281200ec4c51SChris Mason int push_space = 0; 281300ec4c51SChris Mason int push_items = 0; 28140783fcfcSChris Mason struct btrfs_item *item; 281534a38218SChris Mason u32 nr; 28167518a238SChris Mason u32 right_nritems; 28175f39d397SChris Mason u32 data_end; 2818db94535dSChris Mason u32 this_item_size; 281900ec4c51SChris Mason 2820cfed81a0SChris Mason btrfs_init_map_token(&token); 2821cfed81a0SChris Mason 282234a38218SChris Mason if (empty) 282334a38218SChris Mason nr = 0; 282434a38218SChris Mason else 282599d8f83cSChris Mason nr = max_t(u32, 1, min_slot); 282634a38218SChris Mason 282731840ae1SZheng Yan if (path->slots[0] >= left_nritems) 282887b29b20SYan Zheng push_space += data_size; 282931840ae1SZheng Yan 283044871b1bSChris Mason slot = path->slots[1]; 283134a38218SChris Mason i = left_nritems - 1; 283234a38218SChris Mason while (i >= nr) { 28335f39d397SChris Mason item = btrfs_item_nr(left, i); 2834db94535dSChris Mason 283531840ae1SZheng Yan if (!empty && push_items > 0) { 283631840ae1SZheng Yan if (path->slots[0] > i) 283731840ae1SZheng Yan break; 283831840ae1SZheng Yan if (path->slots[0] == i) { 283931840ae1SZheng Yan int space = btrfs_leaf_free_space(root, left); 284031840ae1SZheng Yan if (space + push_space * 2 > free_space) 284131840ae1SZheng Yan break; 284231840ae1SZheng Yan } 284331840ae1SZheng Yan } 284431840ae1SZheng Yan 284500ec4c51SChris Mason if (path->slots[0] == i) 284687b29b20SYan Zheng push_space += data_size; 2847db94535dSChris Mason 2848db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 2849db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 285000ec4c51SChris Mason break; 285131840ae1SZheng Yan 285200ec4c51SChris Mason push_items++; 2853db94535dSChris Mason push_space += this_item_size + sizeof(*item); 285434a38218SChris Mason if (i == 0) 285534a38218SChris Mason break; 285634a38218SChris Mason i--; 2857db94535dSChris Mason } 28585f39d397SChris Mason 2859925baeddSChris Mason if (push_items == 0) 2860925baeddSChris Mason goto out_unlock; 28615f39d397SChris Mason 286234a38218SChris Mason if (!empty && push_items == left_nritems) 2863a429e513SChris Mason WARN_ON(1); 28645f39d397SChris Mason 286500ec4c51SChris Mason /* push left to right */ 28665f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 286734a38218SChris Mason 28685f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 2869123abc88SChris Mason push_space -= leaf_data_end(root, left); 28705f39d397SChris Mason 287100ec4c51SChris Mason /* make room in the right data area */ 28725f39d397SChris Mason data_end = leaf_data_end(root, right); 28735f39d397SChris Mason memmove_extent_buffer(right, 28745f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 28755f39d397SChris Mason btrfs_leaf_data(right) + data_end, 28765f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 28775f39d397SChris Mason 287800ec4c51SChris Mason /* copy from the left data area */ 28795f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 2880d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 2881d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 2882d6025579SChris Mason push_space); 28835f39d397SChris Mason 28845f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 28855f39d397SChris Mason btrfs_item_nr_offset(0), 28860783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 28875f39d397SChris Mason 288800ec4c51SChris Mason /* copy the items from left to right */ 28895f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 28905f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 28910783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 289200ec4c51SChris Mason 289300ec4c51SChris Mason /* update the item pointers */ 28947518a238SChris Mason right_nritems += push_items; 28955f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 2896123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 28977518a238SChris Mason for (i = 0; i < right_nritems; i++) { 28985f39d397SChris Mason item = btrfs_item_nr(right, i); 2899cfed81a0SChris Mason push_space -= btrfs_token_item_size(right, item, &token); 2900cfed81a0SChris Mason btrfs_set_token_item_offset(right, item, push_space, &token); 2901db94535dSChris Mason } 2902db94535dSChris Mason 29037518a238SChris Mason left_nritems -= push_items; 29045f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 290500ec4c51SChris Mason 290634a38218SChris Mason if (left_nritems) 29075f39d397SChris Mason btrfs_mark_buffer_dirty(left); 2908f0486c68SYan, Zheng else 2909f0486c68SYan, Zheng clean_tree_block(trans, root, left); 2910f0486c68SYan, Zheng 29115f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2912a429e513SChris Mason 29135f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 29145f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2915d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 291602217ed2SChris Mason 291700ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 29187518a238SChris Mason if (path->slots[0] >= left_nritems) { 29197518a238SChris Mason path->slots[0] -= left_nritems; 2920925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 2921925baeddSChris Mason clean_tree_block(trans, root, path->nodes[0]); 2922925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 29235f39d397SChris Mason free_extent_buffer(path->nodes[0]); 29245f39d397SChris Mason path->nodes[0] = right; 292500ec4c51SChris Mason path->slots[1] += 1; 292600ec4c51SChris Mason } else { 2927925baeddSChris Mason btrfs_tree_unlock(right); 29285f39d397SChris Mason free_extent_buffer(right); 292900ec4c51SChris Mason } 293000ec4c51SChris Mason return 0; 2931925baeddSChris Mason 2932925baeddSChris Mason out_unlock: 2933925baeddSChris Mason btrfs_tree_unlock(right); 2934925baeddSChris Mason free_extent_buffer(right); 2935925baeddSChris Mason return 1; 293600ec4c51SChris Mason } 2937925baeddSChris Mason 293800ec4c51SChris Mason /* 293944871b1bSChris Mason * push some data in the path leaf to the right, trying to free up at 294074123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 294144871b1bSChris Mason * 294244871b1bSChris Mason * returns 1 if the push failed because the other node didn't have enough 294344871b1bSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 294499d8f83cSChris Mason * 294599d8f83cSChris Mason * this will push starting from min_slot to the end of the leaf. It won't 294699d8f83cSChris Mason * push any slot lower than min_slot 294774123bd7SChris Mason */ 294844871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 294999d8f83cSChris Mason *root, struct btrfs_path *path, 295099d8f83cSChris Mason int min_data_size, int data_size, 295199d8f83cSChris Mason int empty, u32 min_slot) 2952be0e5c09SChris Mason { 295344871b1bSChris Mason struct extent_buffer *left = path->nodes[0]; 295444871b1bSChris Mason struct extent_buffer *right; 295544871b1bSChris Mason struct extent_buffer *upper; 295644871b1bSChris Mason int slot; 295744871b1bSChris Mason int free_space; 295844871b1bSChris Mason u32 left_nritems; 295944871b1bSChris Mason int ret; 296044871b1bSChris Mason 296144871b1bSChris Mason if (!path->nodes[1]) 296244871b1bSChris Mason return 1; 296344871b1bSChris Mason 296444871b1bSChris Mason slot = path->slots[1]; 296544871b1bSChris Mason upper = path->nodes[1]; 296644871b1bSChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 296744871b1bSChris Mason return 1; 296844871b1bSChris Mason 296944871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 297044871b1bSChris Mason 297144871b1bSChris Mason right = read_node_slot(root, upper, slot + 1); 297291ca338dSTsutomu Itoh if (right == NULL) 297391ca338dSTsutomu Itoh return 1; 297491ca338dSTsutomu Itoh 297544871b1bSChris Mason btrfs_tree_lock(right); 297644871b1bSChris Mason btrfs_set_lock_blocking(right); 297744871b1bSChris Mason 297844871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 297944871b1bSChris Mason if (free_space < data_size) 298044871b1bSChris Mason goto out_unlock; 298144871b1bSChris Mason 298244871b1bSChris Mason /* cow and double check */ 298344871b1bSChris Mason ret = btrfs_cow_block(trans, root, right, upper, 298444871b1bSChris Mason slot + 1, &right); 298544871b1bSChris Mason if (ret) 298644871b1bSChris Mason goto out_unlock; 298744871b1bSChris Mason 298844871b1bSChris Mason free_space = btrfs_leaf_free_space(root, right); 298944871b1bSChris Mason if (free_space < data_size) 299044871b1bSChris Mason goto out_unlock; 299144871b1bSChris Mason 299244871b1bSChris Mason left_nritems = btrfs_header_nritems(left); 299344871b1bSChris Mason if (left_nritems == 0) 299444871b1bSChris Mason goto out_unlock; 299544871b1bSChris Mason 299699d8f83cSChris Mason return __push_leaf_right(trans, root, path, min_data_size, empty, 299799d8f83cSChris Mason right, free_space, left_nritems, min_slot); 299844871b1bSChris Mason out_unlock: 299944871b1bSChris Mason btrfs_tree_unlock(right); 300044871b1bSChris Mason free_extent_buffer(right); 300144871b1bSChris Mason return 1; 300244871b1bSChris Mason } 300344871b1bSChris Mason 300444871b1bSChris Mason /* 300544871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 300644871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 300799d8f83cSChris Mason * 300899d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 300999d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the 301099d8f83cSChris Mason * items 301144871b1bSChris Mason */ 301244871b1bSChris Mason static noinline int __push_leaf_left(struct btrfs_trans_handle *trans, 301344871b1bSChris Mason struct btrfs_root *root, 301444871b1bSChris Mason struct btrfs_path *path, int data_size, 301544871b1bSChris Mason int empty, struct extent_buffer *left, 301699d8f83cSChris Mason int free_space, u32 right_nritems, 301799d8f83cSChris Mason u32 max_slot) 301844871b1bSChris Mason { 30195f39d397SChris Mason struct btrfs_disk_key disk_key; 30205f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 3021be0e5c09SChris Mason int i; 3022be0e5c09SChris Mason int push_space = 0; 3023be0e5c09SChris Mason int push_items = 0; 30240783fcfcSChris Mason struct btrfs_item *item; 30257518a238SChris Mason u32 old_left_nritems; 302634a38218SChris Mason u32 nr; 3027aa5d6bedSChris Mason int ret = 0; 3028db94535dSChris Mason u32 this_item_size; 3029db94535dSChris Mason u32 old_left_item_size; 3030cfed81a0SChris Mason struct btrfs_map_token token; 3031cfed81a0SChris Mason 3032cfed81a0SChris Mason btrfs_init_map_token(&token); 3033be0e5c09SChris Mason 303434a38218SChris Mason if (empty) 303599d8f83cSChris Mason nr = min(right_nritems, max_slot); 303634a38218SChris Mason else 303799d8f83cSChris Mason nr = min(right_nritems - 1, max_slot); 303834a38218SChris Mason 303934a38218SChris Mason for (i = 0; i < nr; i++) { 30405f39d397SChris Mason item = btrfs_item_nr(right, i); 3041db94535dSChris Mason 304231840ae1SZheng Yan if (!empty && push_items > 0) { 304331840ae1SZheng Yan if (path->slots[0] < i) 304431840ae1SZheng Yan break; 304531840ae1SZheng Yan if (path->slots[0] == i) { 304631840ae1SZheng Yan int space = btrfs_leaf_free_space(root, right); 304731840ae1SZheng Yan if (space + push_space * 2 > free_space) 304831840ae1SZheng Yan break; 304931840ae1SZheng Yan } 305031840ae1SZheng Yan } 305131840ae1SZheng Yan 3052be0e5c09SChris Mason if (path->slots[0] == i) 305387b29b20SYan Zheng push_space += data_size; 3054db94535dSChris Mason 3055db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 3056db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 3057be0e5c09SChris Mason break; 3058db94535dSChris Mason 3059be0e5c09SChris Mason push_items++; 3060db94535dSChris Mason push_space += this_item_size + sizeof(*item); 3061be0e5c09SChris Mason } 3062db94535dSChris Mason 3063be0e5c09SChris Mason if (push_items == 0) { 3064925baeddSChris Mason ret = 1; 3065925baeddSChris Mason goto out; 3066be0e5c09SChris Mason } 306734a38218SChris Mason if (!empty && push_items == btrfs_header_nritems(right)) 3068a429e513SChris Mason WARN_ON(1); 30695f39d397SChris Mason 3070be0e5c09SChris Mason /* push data from right to left */ 30715f39d397SChris Mason copy_extent_buffer(left, right, 30725f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 30735f39d397SChris Mason btrfs_item_nr_offset(0), 30745f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 30755f39d397SChris Mason 3076123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 30775f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1); 30785f39d397SChris Mason 30795f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 3080d6025579SChris Mason leaf_data_end(root, left) - push_space, 3081123abc88SChris Mason btrfs_leaf_data(right) + 30825f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 3083be0e5c09SChris Mason push_space); 30845f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 308587b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 3086eb60ceacSChris Mason 3087db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 3088be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 30895f39d397SChris Mason u32 ioff; 3090db94535dSChris Mason 30915f39d397SChris Mason item = btrfs_item_nr(left, i); 3092db94535dSChris Mason 3093cfed81a0SChris Mason ioff = btrfs_token_item_offset(left, item, &token); 3094cfed81a0SChris Mason btrfs_set_token_item_offset(left, item, 3095cfed81a0SChris Mason ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size), 3096cfed81a0SChris Mason &token); 3097be0e5c09SChris Mason } 30985f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 3099be0e5c09SChris Mason 3100be0e5c09SChris Mason /* fixup right node */ 310134a38218SChris Mason if (push_items > right_nritems) { 3102d397712bSChris Mason printk(KERN_CRIT "push items %d nr %u\n", push_items, 3103d397712bSChris Mason right_nritems); 310434a38218SChris Mason WARN_ON(1); 310534a38218SChris Mason } 310634a38218SChris Mason 310734a38218SChris Mason if (push_items < right_nritems) { 31085f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 3109123abc88SChris Mason leaf_data_end(root, right); 31105f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 3111d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 3112d6025579SChris Mason btrfs_leaf_data(right) + 3113123abc88SChris Mason leaf_data_end(root, right), push_space); 31145f39d397SChris Mason 31155f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 31165f39d397SChris Mason btrfs_item_nr_offset(push_items), 31175f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 31180783fcfcSChris Mason sizeof(struct btrfs_item)); 311934a38218SChris Mason } 3120eef1c494SYan right_nritems -= push_items; 3121eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 3122123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 31235f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 31245f39d397SChris Mason item = btrfs_item_nr(right, i); 3125db94535dSChris Mason 3126cfed81a0SChris Mason push_space = push_space - btrfs_token_item_size(right, 3127cfed81a0SChris Mason item, &token); 3128cfed81a0SChris Mason btrfs_set_token_item_offset(right, item, push_space, &token); 3129db94535dSChris Mason } 3130eb60ceacSChris Mason 31315f39d397SChris Mason btrfs_mark_buffer_dirty(left); 313234a38218SChris Mason if (right_nritems) 31335f39d397SChris Mason btrfs_mark_buffer_dirty(right); 3134f0486c68SYan, Zheng else 3135f0486c68SYan, Zheng clean_tree_block(trans, root, right); 3136098f59c2SChris Mason 31375f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 3138143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 3139be0e5c09SChris Mason 3140be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 3141be0e5c09SChris Mason if (path->slots[0] < push_items) { 3142be0e5c09SChris Mason path->slots[0] += old_left_nritems; 3143925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 31445f39d397SChris Mason free_extent_buffer(path->nodes[0]); 31455f39d397SChris Mason path->nodes[0] = left; 3146be0e5c09SChris Mason path->slots[1] -= 1; 3147be0e5c09SChris Mason } else { 3148925baeddSChris Mason btrfs_tree_unlock(left); 31495f39d397SChris Mason free_extent_buffer(left); 3150be0e5c09SChris Mason path->slots[0] -= push_items; 3151be0e5c09SChris Mason } 3152eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 3153aa5d6bedSChris Mason return ret; 3154925baeddSChris Mason out: 3155925baeddSChris Mason btrfs_tree_unlock(left); 3156925baeddSChris Mason free_extent_buffer(left); 3157925baeddSChris Mason return ret; 3158be0e5c09SChris Mason } 3159be0e5c09SChris Mason 316074123bd7SChris Mason /* 316144871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 316244871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 316399d8f83cSChris Mason * 316499d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 316599d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the 316699d8f83cSChris Mason * items 316744871b1bSChris Mason */ 316844871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 316999d8f83cSChris Mason *root, struct btrfs_path *path, int min_data_size, 317099d8f83cSChris Mason int data_size, int empty, u32 max_slot) 317144871b1bSChris Mason { 317244871b1bSChris Mason struct extent_buffer *right = path->nodes[0]; 317344871b1bSChris Mason struct extent_buffer *left; 317444871b1bSChris Mason int slot; 317544871b1bSChris Mason int free_space; 317644871b1bSChris Mason u32 right_nritems; 317744871b1bSChris Mason int ret = 0; 317844871b1bSChris Mason 317944871b1bSChris Mason slot = path->slots[1]; 318044871b1bSChris Mason if (slot == 0) 318144871b1bSChris Mason return 1; 318244871b1bSChris Mason if (!path->nodes[1]) 318344871b1bSChris Mason return 1; 318444871b1bSChris Mason 318544871b1bSChris Mason right_nritems = btrfs_header_nritems(right); 318644871b1bSChris Mason if (right_nritems == 0) 318744871b1bSChris Mason return 1; 318844871b1bSChris Mason 318944871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 319044871b1bSChris Mason 319144871b1bSChris Mason left = read_node_slot(root, path->nodes[1], slot - 1); 319291ca338dSTsutomu Itoh if (left == NULL) 319391ca338dSTsutomu Itoh return 1; 319491ca338dSTsutomu Itoh 319544871b1bSChris Mason btrfs_tree_lock(left); 319644871b1bSChris Mason btrfs_set_lock_blocking(left); 319744871b1bSChris Mason 319844871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 319944871b1bSChris Mason if (free_space < data_size) { 320044871b1bSChris Mason ret = 1; 320144871b1bSChris Mason goto out; 320244871b1bSChris Mason } 320344871b1bSChris Mason 320444871b1bSChris Mason /* cow and double check */ 320544871b1bSChris Mason ret = btrfs_cow_block(trans, root, left, 320644871b1bSChris Mason path->nodes[1], slot - 1, &left); 320744871b1bSChris Mason if (ret) { 320844871b1bSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 320979787eaaSJeff Mahoney if (ret == -ENOSPC) 321044871b1bSChris Mason ret = 1; 321144871b1bSChris Mason goto out; 321244871b1bSChris Mason } 321344871b1bSChris Mason 321444871b1bSChris Mason free_space = btrfs_leaf_free_space(root, left); 321544871b1bSChris Mason if (free_space < data_size) { 321644871b1bSChris Mason ret = 1; 321744871b1bSChris Mason goto out; 321844871b1bSChris Mason } 321944871b1bSChris Mason 322099d8f83cSChris Mason return __push_leaf_left(trans, root, path, min_data_size, 322199d8f83cSChris Mason empty, left, free_space, right_nritems, 322299d8f83cSChris Mason max_slot); 322344871b1bSChris Mason out: 322444871b1bSChris Mason btrfs_tree_unlock(left); 322544871b1bSChris Mason free_extent_buffer(left); 322644871b1bSChris Mason return ret; 322744871b1bSChris Mason } 322844871b1bSChris Mason 322944871b1bSChris Mason /* 323074123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 323174123bd7SChris Mason * available for the resulting leaf level of the path. 323274123bd7SChris Mason */ 3233143bede5SJeff Mahoney static noinline void copy_for_split(struct btrfs_trans_handle *trans, 3234e02119d5SChris Mason struct btrfs_root *root, 323544871b1bSChris Mason struct btrfs_path *path, 323644871b1bSChris Mason struct extent_buffer *l, 323744871b1bSChris Mason struct extent_buffer *right, 323844871b1bSChris Mason int slot, int mid, int nritems) 3239be0e5c09SChris Mason { 3240be0e5c09SChris Mason int data_copy_size; 3241be0e5c09SChris Mason int rt_data_off; 3242be0e5c09SChris Mason int i; 3243d4dbff95SChris Mason struct btrfs_disk_key disk_key; 3244cfed81a0SChris Mason struct btrfs_map_token token; 3245cfed81a0SChris Mason 3246cfed81a0SChris Mason btrfs_init_map_token(&token); 3247be0e5c09SChris Mason 32485f39d397SChris Mason nritems = nritems - mid; 32495f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 32505f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 32515f39d397SChris Mason 32525f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 32535f39d397SChris Mason btrfs_item_nr_offset(mid), 32545f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 32555f39d397SChris Mason 32565f39d397SChris Mason copy_extent_buffer(right, l, 3257d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 3258123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 3259123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 326074123bd7SChris Mason 32615f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 32625f39d397SChris Mason btrfs_item_end_nr(l, mid); 32635f39d397SChris Mason 32645f39d397SChris Mason for (i = 0; i < nritems; i++) { 32655f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 3266db94535dSChris Mason u32 ioff; 3267db94535dSChris Mason 3268cfed81a0SChris Mason ioff = btrfs_token_item_offset(right, item, &token); 3269cfed81a0SChris Mason btrfs_set_token_item_offset(right, item, 3270cfed81a0SChris Mason ioff + rt_data_off, &token); 32710783fcfcSChris Mason } 327274123bd7SChris Mason 32735f39d397SChris Mason btrfs_set_header_nritems(l, mid); 32745f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 3275143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, right->start, 3276f3ea38daSJan Schmidt path->slots[1] + 1, 1, 0); 32775f39d397SChris Mason 32785f39d397SChris Mason btrfs_mark_buffer_dirty(right); 32795f39d397SChris Mason btrfs_mark_buffer_dirty(l); 3280eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 32815f39d397SChris Mason 3282be0e5c09SChris Mason if (mid <= slot) { 3283925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 32845f39d397SChris Mason free_extent_buffer(path->nodes[0]); 32855f39d397SChris Mason path->nodes[0] = right; 3286be0e5c09SChris Mason path->slots[0] -= mid; 3287be0e5c09SChris Mason path->slots[1] += 1; 3288925baeddSChris Mason } else { 3289925baeddSChris Mason btrfs_tree_unlock(right); 32905f39d397SChris Mason free_extent_buffer(right); 3291925baeddSChris Mason } 32925f39d397SChris Mason 3293eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 329444871b1bSChris Mason } 329544871b1bSChris Mason 329644871b1bSChris Mason /* 329799d8f83cSChris Mason * double splits happen when we need to insert a big item in the middle 329899d8f83cSChris Mason * of a leaf. A double split can leave us with 3 mostly empty leaves: 329999d8f83cSChris Mason * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ] 330099d8f83cSChris Mason * A B C 330199d8f83cSChris Mason * 330299d8f83cSChris Mason * We avoid this by trying to push the items on either side of our target 330399d8f83cSChris Mason * into the adjacent leaves. If all goes well we can avoid the double split 330499d8f83cSChris Mason * completely. 330599d8f83cSChris Mason */ 330699d8f83cSChris Mason static noinline int push_for_double_split(struct btrfs_trans_handle *trans, 330799d8f83cSChris Mason struct btrfs_root *root, 330899d8f83cSChris Mason struct btrfs_path *path, 330999d8f83cSChris Mason int data_size) 331099d8f83cSChris Mason { 331199d8f83cSChris Mason int ret; 331299d8f83cSChris Mason int progress = 0; 331399d8f83cSChris Mason int slot; 331499d8f83cSChris Mason u32 nritems; 331599d8f83cSChris Mason 331699d8f83cSChris Mason slot = path->slots[0]; 331799d8f83cSChris Mason 331899d8f83cSChris Mason /* 331999d8f83cSChris Mason * try to push all the items after our slot into the 332099d8f83cSChris Mason * right leaf 332199d8f83cSChris Mason */ 332299d8f83cSChris Mason ret = push_leaf_right(trans, root, path, 1, data_size, 0, slot); 332399d8f83cSChris Mason if (ret < 0) 332499d8f83cSChris Mason return ret; 332599d8f83cSChris Mason 332699d8f83cSChris Mason if (ret == 0) 332799d8f83cSChris Mason progress++; 332899d8f83cSChris Mason 332999d8f83cSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 333099d8f83cSChris Mason /* 333199d8f83cSChris Mason * our goal is to get our slot at the start or end of a leaf. If 333299d8f83cSChris Mason * we've done so we're done 333399d8f83cSChris Mason */ 333499d8f83cSChris Mason if (path->slots[0] == 0 || path->slots[0] == nritems) 333599d8f83cSChris Mason return 0; 333699d8f83cSChris Mason 333799d8f83cSChris Mason if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size) 333899d8f83cSChris Mason return 0; 333999d8f83cSChris Mason 334099d8f83cSChris Mason /* try to push all the items before our slot into the next leaf */ 334199d8f83cSChris Mason slot = path->slots[0]; 334299d8f83cSChris Mason ret = push_leaf_left(trans, root, path, 1, data_size, 0, slot); 334399d8f83cSChris Mason if (ret < 0) 334499d8f83cSChris Mason return ret; 334599d8f83cSChris Mason 334699d8f83cSChris Mason if (ret == 0) 334799d8f83cSChris Mason progress++; 334899d8f83cSChris Mason 334999d8f83cSChris Mason if (progress) 335099d8f83cSChris Mason return 0; 335199d8f83cSChris Mason return 1; 335299d8f83cSChris Mason } 335399d8f83cSChris Mason 335499d8f83cSChris Mason /* 335544871b1bSChris Mason * split the path's leaf in two, making sure there is at least data_size 335644871b1bSChris Mason * available for the resulting leaf level of the path. 335744871b1bSChris Mason * 335844871b1bSChris Mason * returns 0 if all went well and < 0 on failure. 335944871b1bSChris Mason */ 336044871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 336144871b1bSChris Mason struct btrfs_root *root, 336244871b1bSChris Mason struct btrfs_key *ins_key, 336344871b1bSChris Mason struct btrfs_path *path, int data_size, 336444871b1bSChris Mason int extend) 336544871b1bSChris Mason { 33665d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 336744871b1bSChris Mason struct extent_buffer *l; 336844871b1bSChris Mason u32 nritems; 336944871b1bSChris Mason int mid; 337044871b1bSChris Mason int slot; 337144871b1bSChris Mason struct extent_buffer *right; 337244871b1bSChris Mason int ret = 0; 337344871b1bSChris Mason int wret; 33745d4f98a2SYan Zheng int split; 337544871b1bSChris Mason int num_doubles = 0; 337699d8f83cSChris Mason int tried_avoid_double = 0; 337744871b1bSChris Mason 3378a5719521SYan, Zheng l = path->nodes[0]; 3379a5719521SYan, Zheng slot = path->slots[0]; 3380a5719521SYan, Zheng if (extend && data_size + btrfs_item_size_nr(l, slot) + 3381a5719521SYan, Zheng sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root)) 3382a5719521SYan, Zheng return -EOVERFLOW; 3383a5719521SYan, Zheng 338444871b1bSChris Mason /* first try to make some room by pushing left and right */ 338599d8f83cSChris Mason if (data_size) { 338699d8f83cSChris Mason wret = push_leaf_right(trans, root, path, data_size, 338799d8f83cSChris Mason data_size, 0, 0); 338844871b1bSChris Mason if (wret < 0) 338944871b1bSChris Mason return wret; 339044871b1bSChris Mason if (wret) { 339199d8f83cSChris Mason wret = push_leaf_left(trans, root, path, data_size, 339299d8f83cSChris Mason data_size, 0, (u32)-1); 339344871b1bSChris Mason if (wret < 0) 339444871b1bSChris Mason return wret; 339544871b1bSChris Mason } 339644871b1bSChris Mason l = path->nodes[0]; 339744871b1bSChris Mason 339844871b1bSChris Mason /* did the pushes work? */ 339944871b1bSChris Mason if (btrfs_leaf_free_space(root, l) >= data_size) 340044871b1bSChris Mason return 0; 340144871b1bSChris Mason } 340244871b1bSChris Mason 340344871b1bSChris Mason if (!path->nodes[1]) { 340444871b1bSChris Mason ret = insert_new_root(trans, root, path, 1); 340544871b1bSChris Mason if (ret) 340644871b1bSChris Mason return ret; 340744871b1bSChris Mason } 340844871b1bSChris Mason again: 34095d4f98a2SYan Zheng split = 1; 341044871b1bSChris Mason l = path->nodes[0]; 341144871b1bSChris Mason slot = path->slots[0]; 341244871b1bSChris Mason nritems = btrfs_header_nritems(l); 341344871b1bSChris Mason mid = (nritems + 1) / 2; 341444871b1bSChris Mason 34155d4f98a2SYan Zheng if (mid <= slot) { 34165d4f98a2SYan Zheng if (nritems == 1 || 34175d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + data_size > 34185d4f98a2SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 34195d4f98a2SYan Zheng if (slot >= nritems) { 34205d4f98a2SYan Zheng split = 0; 34215d4f98a2SYan Zheng } else { 34225d4f98a2SYan Zheng mid = slot; 34235d4f98a2SYan Zheng if (mid != nritems && 34245d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 34255d4f98a2SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 342699d8f83cSChris Mason if (data_size && !tried_avoid_double) 342799d8f83cSChris Mason goto push_for_double; 34285d4f98a2SYan Zheng split = 2; 34295d4f98a2SYan Zheng } 34305d4f98a2SYan Zheng } 34315d4f98a2SYan Zheng } 34325d4f98a2SYan Zheng } else { 34335d4f98a2SYan Zheng if (leaf_space_used(l, 0, mid) + data_size > 34345d4f98a2SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 34355d4f98a2SYan Zheng if (!extend && data_size && slot == 0) { 34365d4f98a2SYan Zheng split = 0; 34375d4f98a2SYan Zheng } else if ((extend || !data_size) && slot == 0) { 34385d4f98a2SYan Zheng mid = 1; 34395d4f98a2SYan Zheng } else { 34405d4f98a2SYan Zheng mid = slot; 34415d4f98a2SYan Zheng if (mid != nritems && 34425d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 34435d4f98a2SYan Zheng data_size > BTRFS_LEAF_DATA_SIZE(root)) { 344499d8f83cSChris Mason if (data_size && !tried_avoid_double) 344599d8f83cSChris Mason goto push_for_double; 34465d4f98a2SYan Zheng split = 2 ; 34475d4f98a2SYan Zheng } 34485d4f98a2SYan Zheng } 34495d4f98a2SYan Zheng } 34505d4f98a2SYan Zheng } 34515d4f98a2SYan Zheng 34525d4f98a2SYan Zheng if (split == 0) 34535d4f98a2SYan Zheng btrfs_cpu_key_to_disk(&disk_key, ins_key); 34545d4f98a2SYan Zheng else 34555d4f98a2SYan Zheng btrfs_item_key(l, &disk_key, mid); 34565d4f98a2SYan Zheng 34575d4f98a2SYan Zheng right = btrfs_alloc_free_block(trans, root, root->leafsize, 0, 345844871b1bSChris Mason root->root_key.objectid, 34595581a51aSJan Schmidt &disk_key, 0, l->start, 0); 3460f0486c68SYan, Zheng if (IS_ERR(right)) 346144871b1bSChris Mason return PTR_ERR(right); 3462f0486c68SYan, Zheng 3463f0486c68SYan, Zheng root_add_used(root, root->leafsize); 346444871b1bSChris Mason 346544871b1bSChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 346644871b1bSChris Mason btrfs_set_header_bytenr(right, right->start); 346744871b1bSChris Mason btrfs_set_header_generation(right, trans->transid); 34685d4f98a2SYan Zheng btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV); 346944871b1bSChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 347044871b1bSChris Mason btrfs_set_header_level(right, 0); 347144871b1bSChris Mason write_extent_buffer(right, root->fs_info->fsid, 347244871b1bSChris Mason (unsigned long)btrfs_header_fsid(right), 347344871b1bSChris Mason BTRFS_FSID_SIZE); 347444871b1bSChris Mason 347544871b1bSChris Mason write_extent_buffer(right, root->fs_info->chunk_tree_uuid, 347644871b1bSChris Mason (unsigned long)btrfs_header_chunk_tree_uuid(right), 347744871b1bSChris Mason BTRFS_UUID_SIZE); 347844871b1bSChris Mason 34795d4f98a2SYan Zheng if (split == 0) { 348044871b1bSChris Mason if (mid <= slot) { 348144871b1bSChris Mason btrfs_set_header_nritems(right, 0); 3482143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, right->start, 3483f3ea38daSJan Schmidt path->slots[1] + 1, 1, 0); 348444871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 348544871b1bSChris Mason free_extent_buffer(path->nodes[0]); 348644871b1bSChris Mason path->nodes[0] = right; 348744871b1bSChris Mason path->slots[0] = 0; 348844871b1bSChris Mason path->slots[1] += 1; 348944871b1bSChris Mason } else { 349044871b1bSChris Mason btrfs_set_header_nritems(right, 0); 3491143bede5SJeff Mahoney insert_ptr(trans, root, path, &disk_key, right->start, 3492f3ea38daSJan Schmidt path->slots[1], 1, 0); 349344871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 349444871b1bSChris Mason free_extent_buffer(path->nodes[0]); 349544871b1bSChris Mason path->nodes[0] = right; 349644871b1bSChris Mason path->slots[0] = 0; 3497143bede5SJeff Mahoney if (path->slots[1] == 0) 3498143bede5SJeff Mahoney fixup_low_keys(trans, root, path, 3499143bede5SJeff Mahoney &disk_key, 1); 35005d4f98a2SYan Zheng } 350144871b1bSChris Mason btrfs_mark_buffer_dirty(right); 350244871b1bSChris Mason return ret; 350344871b1bSChris Mason } 350444871b1bSChris Mason 3505143bede5SJeff Mahoney copy_for_split(trans, root, path, l, right, slot, mid, nritems); 350644871b1bSChris Mason 35075d4f98a2SYan Zheng if (split == 2) { 3508cc0c5538SChris Mason BUG_ON(num_doubles != 0); 3509cc0c5538SChris Mason num_doubles++; 3510cc0c5538SChris Mason goto again; 35113326d1b0SChris Mason } 351244871b1bSChris Mason 3513143bede5SJeff Mahoney return 0; 351499d8f83cSChris Mason 351599d8f83cSChris Mason push_for_double: 351699d8f83cSChris Mason push_for_double_split(trans, root, path, data_size); 351799d8f83cSChris Mason tried_avoid_double = 1; 351899d8f83cSChris Mason if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size) 351999d8f83cSChris Mason return 0; 352099d8f83cSChris Mason goto again; 3521be0e5c09SChris Mason } 3522be0e5c09SChris Mason 3523ad48fd75SYan, Zheng static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3524ad48fd75SYan, Zheng struct btrfs_root *root, 3525ad48fd75SYan, Zheng struct btrfs_path *path, int ins_len) 3526ad48fd75SYan, Zheng { 3527ad48fd75SYan, Zheng struct btrfs_key key; 3528ad48fd75SYan, Zheng struct extent_buffer *leaf; 3529ad48fd75SYan, Zheng struct btrfs_file_extent_item *fi; 3530ad48fd75SYan, Zheng u64 extent_len = 0; 3531ad48fd75SYan, Zheng u32 item_size; 3532ad48fd75SYan, Zheng int ret; 3533ad48fd75SYan, Zheng 3534ad48fd75SYan, Zheng leaf = path->nodes[0]; 3535ad48fd75SYan, Zheng btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 3536ad48fd75SYan, Zheng 3537ad48fd75SYan, Zheng BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY && 3538ad48fd75SYan, Zheng key.type != BTRFS_EXTENT_CSUM_KEY); 3539ad48fd75SYan, Zheng 3540ad48fd75SYan, Zheng if (btrfs_leaf_free_space(root, leaf) >= ins_len) 3541ad48fd75SYan, Zheng return 0; 3542ad48fd75SYan, Zheng 3543ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3544ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3545ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3546ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3547ad48fd75SYan, Zheng extent_len = btrfs_file_extent_num_bytes(leaf, fi); 3548ad48fd75SYan, Zheng } 3549b3b4aa74SDavid Sterba btrfs_release_path(path); 3550ad48fd75SYan, Zheng 3551ad48fd75SYan, Zheng path->keep_locks = 1; 3552ad48fd75SYan, Zheng path->search_for_split = 1; 3553ad48fd75SYan, Zheng ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 3554ad48fd75SYan, Zheng path->search_for_split = 0; 3555ad48fd75SYan, Zheng if (ret < 0) 3556ad48fd75SYan, Zheng goto err; 3557ad48fd75SYan, Zheng 3558ad48fd75SYan, Zheng ret = -EAGAIN; 3559ad48fd75SYan, Zheng leaf = path->nodes[0]; 3560ad48fd75SYan, Zheng /* if our item isn't there or got smaller, return now */ 3561ad48fd75SYan, Zheng if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0])) 3562ad48fd75SYan, Zheng goto err; 3563ad48fd75SYan, Zheng 3564109f6aefSChris Mason /* the leaf has changed, it now has room. return now */ 3565109f6aefSChris Mason if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len) 3566109f6aefSChris Mason goto err; 3567109f6aefSChris Mason 3568ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3569ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3570ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3571ad48fd75SYan, Zheng if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) 3572ad48fd75SYan, Zheng goto err; 3573ad48fd75SYan, Zheng } 3574ad48fd75SYan, Zheng 3575ad48fd75SYan, Zheng btrfs_set_path_blocking(path); 3576ad48fd75SYan, Zheng ret = split_leaf(trans, root, &key, path, ins_len, 1); 3577f0486c68SYan, Zheng if (ret) 3578f0486c68SYan, Zheng goto err; 3579ad48fd75SYan, Zheng 3580ad48fd75SYan, Zheng path->keep_locks = 0; 3581ad48fd75SYan, Zheng btrfs_unlock_up_safe(path, 1); 3582ad48fd75SYan, Zheng return 0; 3583ad48fd75SYan, Zheng err: 3584ad48fd75SYan, Zheng path->keep_locks = 0; 3585ad48fd75SYan, Zheng return ret; 3586ad48fd75SYan, Zheng } 3587ad48fd75SYan, Zheng 3588ad48fd75SYan, Zheng static noinline int split_item(struct btrfs_trans_handle *trans, 3589459931ecSChris Mason struct btrfs_root *root, 3590459931ecSChris Mason struct btrfs_path *path, 3591459931ecSChris Mason struct btrfs_key *new_key, 3592459931ecSChris Mason unsigned long split_offset) 3593459931ecSChris Mason { 3594459931ecSChris Mason struct extent_buffer *leaf; 3595459931ecSChris Mason struct btrfs_item *item; 3596459931ecSChris Mason struct btrfs_item *new_item; 3597459931ecSChris Mason int slot; 3598ad48fd75SYan, Zheng char *buf; 3599459931ecSChris Mason u32 nritems; 3600ad48fd75SYan, Zheng u32 item_size; 3601459931ecSChris Mason u32 orig_offset; 3602459931ecSChris Mason struct btrfs_disk_key disk_key; 3603459931ecSChris Mason 3604459931ecSChris Mason leaf = path->nodes[0]; 3605b9473439SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item)); 3606b9473439SChris Mason 3607b4ce94deSChris Mason btrfs_set_path_blocking(path); 3608b4ce94deSChris Mason 3609459931ecSChris Mason item = btrfs_item_nr(leaf, path->slots[0]); 3610459931ecSChris Mason orig_offset = btrfs_item_offset(leaf, item); 3611459931ecSChris Mason item_size = btrfs_item_size(leaf, item); 3612459931ecSChris Mason 3613459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 3614ad48fd75SYan, Zheng if (!buf) 3615ad48fd75SYan, Zheng return -ENOMEM; 3616ad48fd75SYan, Zheng 3617459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3618459931ecSChris Mason path->slots[0]), item_size); 3619ad48fd75SYan, Zheng 3620459931ecSChris Mason slot = path->slots[0] + 1; 3621459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 3622459931ecSChris Mason if (slot != nritems) { 3623459931ecSChris Mason /* shift the items */ 3624459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 3625459931ecSChris Mason btrfs_item_nr_offset(slot), 3626459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3627459931ecSChris Mason } 3628459931ecSChris Mason 3629459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 3630459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3631459931ecSChris Mason 3632459931ecSChris Mason new_item = btrfs_item_nr(leaf, slot); 3633459931ecSChris Mason 3634459931ecSChris Mason btrfs_set_item_offset(leaf, new_item, orig_offset); 3635459931ecSChris Mason btrfs_set_item_size(leaf, new_item, item_size - split_offset); 3636459931ecSChris Mason 3637459931ecSChris Mason btrfs_set_item_offset(leaf, item, 3638459931ecSChris Mason orig_offset + item_size - split_offset); 3639459931ecSChris Mason btrfs_set_item_size(leaf, item, split_offset); 3640459931ecSChris Mason 3641459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 3642459931ecSChris Mason 3643459931ecSChris Mason /* write the data for the start of the original item */ 3644459931ecSChris Mason write_extent_buffer(leaf, buf, 3645459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 3646459931ecSChris Mason split_offset); 3647459931ecSChris Mason 3648459931ecSChris Mason /* write the data for the new item */ 3649459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 3650459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 3651459931ecSChris Mason item_size - split_offset); 3652459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 3653459931ecSChris Mason 3654ad48fd75SYan, Zheng BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 3655459931ecSChris Mason kfree(buf); 3656ad48fd75SYan, Zheng return 0; 3657ad48fd75SYan, Zheng } 3658ad48fd75SYan, Zheng 3659ad48fd75SYan, Zheng /* 3660ad48fd75SYan, Zheng * This function splits a single item into two items, 3661ad48fd75SYan, Zheng * giving 'new_key' to the new item and splitting the 3662ad48fd75SYan, Zheng * old one at split_offset (from the start of the item). 3663ad48fd75SYan, Zheng * 3664ad48fd75SYan, Zheng * The path may be released by this operation. After 3665ad48fd75SYan, Zheng * the split, the path is pointing to the old item. The 3666ad48fd75SYan, Zheng * new item is going to be in the same node as the old one. 3667ad48fd75SYan, Zheng * 3668ad48fd75SYan, Zheng * Note, the item being split must be smaller enough to live alone on 3669ad48fd75SYan, Zheng * a tree block with room for one extra struct btrfs_item 3670ad48fd75SYan, Zheng * 3671ad48fd75SYan, Zheng * This allows us to split the item in place, keeping a lock on the 3672ad48fd75SYan, Zheng * leaf the entire time. 3673ad48fd75SYan, Zheng */ 3674ad48fd75SYan, Zheng int btrfs_split_item(struct btrfs_trans_handle *trans, 3675ad48fd75SYan, Zheng struct btrfs_root *root, 3676ad48fd75SYan, Zheng struct btrfs_path *path, 3677ad48fd75SYan, Zheng struct btrfs_key *new_key, 3678ad48fd75SYan, Zheng unsigned long split_offset) 3679ad48fd75SYan, Zheng { 3680ad48fd75SYan, Zheng int ret; 3681ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3682ad48fd75SYan, Zheng sizeof(struct btrfs_item)); 3683ad48fd75SYan, Zheng if (ret) 3684459931ecSChris Mason return ret; 3685ad48fd75SYan, Zheng 3686ad48fd75SYan, Zheng ret = split_item(trans, root, path, new_key, split_offset); 3687ad48fd75SYan, Zheng return ret; 3688ad48fd75SYan, Zheng } 3689ad48fd75SYan, Zheng 3690ad48fd75SYan, Zheng /* 3691ad48fd75SYan, Zheng * This function duplicate a item, giving 'new_key' to the new item. 3692ad48fd75SYan, Zheng * It guarantees both items live in the same tree leaf and the new item 3693ad48fd75SYan, Zheng * is contiguous with the original item. 3694ad48fd75SYan, Zheng * 3695ad48fd75SYan, Zheng * This allows us to split file extent in place, keeping a lock on the 3696ad48fd75SYan, Zheng * leaf the entire time. 3697ad48fd75SYan, Zheng */ 3698ad48fd75SYan, Zheng int btrfs_duplicate_item(struct btrfs_trans_handle *trans, 3699ad48fd75SYan, Zheng struct btrfs_root *root, 3700ad48fd75SYan, Zheng struct btrfs_path *path, 3701ad48fd75SYan, Zheng struct btrfs_key *new_key) 3702ad48fd75SYan, Zheng { 3703ad48fd75SYan, Zheng struct extent_buffer *leaf; 3704ad48fd75SYan, Zheng int ret; 3705ad48fd75SYan, Zheng u32 item_size; 3706ad48fd75SYan, Zheng 3707ad48fd75SYan, Zheng leaf = path->nodes[0]; 3708ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3709ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3710ad48fd75SYan, Zheng item_size + sizeof(struct btrfs_item)); 3711ad48fd75SYan, Zheng if (ret) 3712ad48fd75SYan, Zheng return ret; 3713ad48fd75SYan, Zheng 3714ad48fd75SYan, Zheng path->slots[0]++; 3715143bede5SJeff Mahoney setup_items_for_insert(trans, root, path, new_key, &item_size, 3716ad48fd75SYan, Zheng item_size, item_size + 3717ad48fd75SYan, Zheng sizeof(struct btrfs_item), 1); 3718ad48fd75SYan, Zheng leaf = path->nodes[0]; 3719ad48fd75SYan, Zheng memcpy_extent_buffer(leaf, 3720ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0]), 3721ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0] - 1), 3722ad48fd75SYan, Zheng item_size); 3723ad48fd75SYan, Zheng return 0; 3724459931ecSChris Mason } 3725459931ecSChris Mason 3726459931ecSChris Mason /* 3727d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 3728d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 3729d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 3730d352ac68SChris Mason * the front. 3731d352ac68SChris Mason */ 3732143bede5SJeff Mahoney void btrfs_truncate_item(struct btrfs_trans_handle *trans, 3733b18c6685SChris Mason struct btrfs_root *root, 3734b18c6685SChris Mason struct btrfs_path *path, 3735179e29e4SChris Mason u32 new_size, int from_end) 3736b18c6685SChris Mason { 3737b18c6685SChris Mason int slot; 37385f39d397SChris Mason struct extent_buffer *leaf; 37395f39d397SChris Mason struct btrfs_item *item; 3740b18c6685SChris Mason u32 nritems; 3741b18c6685SChris Mason unsigned int data_end; 3742b18c6685SChris Mason unsigned int old_data_start; 3743b18c6685SChris Mason unsigned int old_size; 3744b18c6685SChris Mason unsigned int size_diff; 3745b18c6685SChris Mason int i; 3746cfed81a0SChris Mason struct btrfs_map_token token; 3747cfed81a0SChris Mason 3748cfed81a0SChris Mason btrfs_init_map_token(&token); 3749b18c6685SChris Mason 37505f39d397SChris Mason leaf = path->nodes[0]; 3751179e29e4SChris Mason slot = path->slots[0]; 3752179e29e4SChris Mason 3753179e29e4SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 3754179e29e4SChris Mason if (old_size == new_size) 3755143bede5SJeff Mahoney return; 3756b18c6685SChris Mason 37575f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 3758b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 3759b18c6685SChris Mason 37605f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 3761179e29e4SChris Mason 3762b18c6685SChris Mason size_diff = old_size - new_size; 3763b18c6685SChris Mason 3764b18c6685SChris Mason BUG_ON(slot < 0); 3765b18c6685SChris Mason BUG_ON(slot >= nritems); 3766b18c6685SChris Mason 3767b18c6685SChris Mason /* 3768b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3769b18c6685SChris Mason */ 3770b18c6685SChris Mason /* first correct the data pointers */ 3771b18c6685SChris Mason for (i = slot; i < nritems; i++) { 37725f39d397SChris Mason u32 ioff; 37735f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3774db94535dSChris Mason 3775cfed81a0SChris Mason ioff = btrfs_token_item_offset(leaf, item, &token); 3776cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 3777cfed81a0SChris Mason ioff + size_diff, &token); 3778b18c6685SChris Mason } 3779db94535dSChris Mason 3780b18c6685SChris Mason /* shift the data */ 3781179e29e4SChris Mason if (from_end) { 37825f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3783b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 3784b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 3785179e29e4SChris Mason } else { 3786179e29e4SChris Mason struct btrfs_disk_key disk_key; 3787179e29e4SChris Mason u64 offset; 3788179e29e4SChris Mason 3789179e29e4SChris Mason btrfs_item_key(leaf, &disk_key, slot); 3790179e29e4SChris Mason 3791179e29e4SChris Mason if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 3792179e29e4SChris Mason unsigned long ptr; 3793179e29e4SChris Mason struct btrfs_file_extent_item *fi; 3794179e29e4SChris Mason 3795179e29e4SChris Mason fi = btrfs_item_ptr(leaf, slot, 3796179e29e4SChris Mason struct btrfs_file_extent_item); 3797179e29e4SChris Mason fi = (struct btrfs_file_extent_item *)( 3798179e29e4SChris Mason (unsigned long)fi - size_diff); 3799179e29e4SChris Mason 3800179e29e4SChris Mason if (btrfs_file_extent_type(leaf, fi) == 3801179e29e4SChris Mason BTRFS_FILE_EXTENT_INLINE) { 3802179e29e4SChris Mason ptr = btrfs_item_ptr_offset(leaf, slot); 3803179e29e4SChris Mason memmove_extent_buffer(leaf, ptr, 3804179e29e4SChris Mason (unsigned long)fi, 3805179e29e4SChris Mason offsetof(struct btrfs_file_extent_item, 3806179e29e4SChris Mason disk_bytenr)); 3807179e29e4SChris Mason } 3808179e29e4SChris Mason } 3809179e29e4SChris Mason 3810179e29e4SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 3811179e29e4SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 3812179e29e4SChris Mason data_end, old_data_start - data_end); 3813179e29e4SChris Mason 3814179e29e4SChris Mason offset = btrfs_disk_key_offset(&disk_key); 3815179e29e4SChris Mason btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 3816179e29e4SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3817179e29e4SChris Mason if (slot == 0) 3818179e29e4SChris Mason fixup_low_keys(trans, root, path, &disk_key, 1); 3819179e29e4SChris Mason } 38205f39d397SChris Mason 38215f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 38225f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 38235f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3824b18c6685SChris Mason 38255f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 38265f39d397SChris Mason btrfs_print_leaf(root, leaf); 3827b18c6685SChris Mason BUG(); 38285f39d397SChris Mason } 3829b18c6685SChris Mason } 3830b18c6685SChris Mason 3831d352ac68SChris Mason /* 3832d352ac68SChris Mason * make the item pointed to by the path bigger, data_size is the new size. 3833d352ac68SChris Mason */ 3834143bede5SJeff Mahoney void btrfs_extend_item(struct btrfs_trans_handle *trans, 38355f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 38365f39d397SChris Mason u32 data_size) 38376567e837SChris Mason { 38386567e837SChris Mason int slot; 38395f39d397SChris Mason struct extent_buffer *leaf; 38405f39d397SChris Mason struct btrfs_item *item; 38416567e837SChris Mason u32 nritems; 38426567e837SChris Mason unsigned int data_end; 38436567e837SChris Mason unsigned int old_data; 38446567e837SChris Mason unsigned int old_size; 38456567e837SChris Mason int i; 3846cfed81a0SChris Mason struct btrfs_map_token token; 3847cfed81a0SChris Mason 3848cfed81a0SChris Mason btrfs_init_map_token(&token); 38496567e837SChris Mason 38505f39d397SChris Mason leaf = path->nodes[0]; 38516567e837SChris Mason 38525f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 38536567e837SChris Mason data_end = leaf_data_end(root, leaf); 38546567e837SChris Mason 38555f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 38565f39d397SChris Mason btrfs_print_leaf(root, leaf); 38576567e837SChris Mason BUG(); 38585f39d397SChris Mason } 38596567e837SChris Mason slot = path->slots[0]; 38605f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 38616567e837SChris Mason 38626567e837SChris Mason BUG_ON(slot < 0); 38633326d1b0SChris Mason if (slot >= nritems) { 38643326d1b0SChris Mason btrfs_print_leaf(root, leaf); 3865d397712bSChris Mason printk(KERN_CRIT "slot %d too large, nritems %d\n", 3866d397712bSChris Mason slot, nritems); 38673326d1b0SChris Mason BUG_ON(1); 38683326d1b0SChris Mason } 38696567e837SChris Mason 38706567e837SChris Mason /* 38716567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 38726567e837SChris Mason */ 38736567e837SChris Mason /* first correct the data pointers */ 38746567e837SChris Mason for (i = slot; i < nritems; i++) { 38755f39d397SChris Mason u32 ioff; 38765f39d397SChris Mason item = btrfs_item_nr(leaf, i); 3877db94535dSChris Mason 3878cfed81a0SChris Mason ioff = btrfs_token_item_offset(leaf, item, &token); 3879cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 3880cfed81a0SChris Mason ioff - data_size, &token); 38816567e837SChris Mason } 38825f39d397SChris Mason 38836567e837SChris Mason /* shift the data */ 38845f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 38856567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 38866567e837SChris Mason data_end, old_data - data_end); 38875f39d397SChris Mason 38886567e837SChris Mason data_end = old_data; 38895f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 38905f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 38915f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 38925f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 38936567e837SChris Mason 38945f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 38955f39d397SChris Mason btrfs_print_leaf(root, leaf); 38966567e837SChris Mason BUG(); 38975f39d397SChris Mason } 38986567e837SChris Mason } 38996567e837SChris Mason 390074123bd7SChris Mason /* 3901d352ac68SChris Mason * Given a key and some data, insert items into the tree. 390274123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 3903f3465ca4SJosef Bacik * Returns the number of keys that were inserted. 3904f3465ca4SJosef Bacik */ 3905f3465ca4SJosef Bacik int btrfs_insert_some_items(struct btrfs_trans_handle *trans, 3906f3465ca4SJosef Bacik struct btrfs_root *root, 3907f3465ca4SJosef Bacik struct btrfs_path *path, 3908f3465ca4SJosef Bacik struct btrfs_key *cpu_key, u32 *data_size, 3909f3465ca4SJosef Bacik int nr) 3910f3465ca4SJosef Bacik { 3911f3465ca4SJosef Bacik struct extent_buffer *leaf; 3912f3465ca4SJosef Bacik struct btrfs_item *item; 3913f3465ca4SJosef Bacik int ret = 0; 3914f3465ca4SJosef Bacik int slot; 3915f3465ca4SJosef Bacik int i; 3916f3465ca4SJosef Bacik u32 nritems; 3917f3465ca4SJosef Bacik u32 total_data = 0; 3918f3465ca4SJosef Bacik u32 total_size = 0; 3919f3465ca4SJosef Bacik unsigned int data_end; 3920f3465ca4SJosef Bacik struct btrfs_disk_key disk_key; 3921f3465ca4SJosef Bacik struct btrfs_key found_key; 3922cfed81a0SChris Mason struct btrfs_map_token token; 3923cfed81a0SChris Mason 3924cfed81a0SChris Mason btrfs_init_map_token(&token); 3925f3465ca4SJosef Bacik 392687b29b20SYan Zheng for (i = 0; i < nr; i++) { 392787b29b20SYan Zheng if (total_size + data_size[i] + sizeof(struct btrfs_item) > 392887b29b20SYan Zheng BTRFS_LEAF_DATA_SIZE(root)) { 392987b29b20SYan Zheng break; 393087b29b20SYan Zheng nr = i; 393187b29b20SYan Zheng } 3932f3465ca4SJosef Bacik total_data += data_size[i]; 393387b29b20SYan Zheng total_size += data_size[i] + sizeof(struct btrfs_item); 393487b29b20SYan Zheng } 393587b29b20SYan Zheng BUG_ON(nr == 0); 3936f3465ca4SJosef Bacik 3937f3465ca4SJosef Bacik ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 3938f3465ca4SJosef Bacik if (ret == 0) 3939f3465ca4SJosef Bacik return -EEXIST; 3940f3465ca4SJosef Bacik if (ret < 0) 3941f3465ca4SJosef Bacik goto out; 3942f3465ca4SJosef Bacik 3943f3465ca4SJosef Bacik leaf = path->nodes[0]; 3944f3465ca4SJosef Bacik 3945f3465ca4SJosef Bacik nritems = btrfs_header_nritems(leaf); 3946f3465ca4SJosef Bacik data_end = leaf_data_end(root, leaf); 3947f3465ca4SJosef Bacik 3948f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < total_size) { 3949f3465ca4SJosef Bacik for (i = nr; i >= 0; i--) { 3950f3465ca4SJosef Bacik total_data -= data_size[i]; 3951f3465ca4SJosef Bacik total_size -= data_size[i] + sizeof(struct btrfs_item); 3952f3465ca4SJosef Bacik if (total_size < btrfs_leaf_free_space(root, leaf)) 3953f3465ca4SJosef Bacik break; 3954f3465ca4SJosef Bacik } 3955f3465ca4SJosef Bacik nr = i; 3956f3465ca4SJosef Bacik } 3957f3465ca4SJosef Bacik 3958f3465ca4SJosef Bacik slot = path->slots[0]; 3959f3465ca4SJosef Bacik BUG_ON(slot < 0); 3960f3465ca4SJosef Bacik 3961f3465ca4SJosef Bacik if (slot != nritems) { 3962f3465ca4SJosef Bacik unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3963f3465ca4SJosef Bacik 3964f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot); 3965f3465ca4SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, slot); 3966f3465ca4SJosef Bacik 3967f3465ca4SJosef Bacik /* figure out how many keys we can insert in here */ 3968f3465ca4SJosef Bacik total_data = data_size[0]; 3969f3465ca4SJosef Bacik for (i = 1; i < nr; i++) { 39705d4f98a2SYan Zheng if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0) 3971f3465ca4SJosef Bacik break; 3972f3465ca4SJosef Bacik total_data += data_size[i]; 3973f3465ca4SJosef Bacik } 3974f3465ca4SJosef Bacik nr = i; 3975f3465ca4SJosef Bacik 3976f3465ca4SJosef Bacik if (old_data < data_end) { 3977f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 3978d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 3979f3465ca4SJosef Bacik slot, old_data, data_end); 3980f3465ca4SJosef Bacik BUG_ON(1); 3981f3465ca4SJosef Bacik } 3982f3465ca4SJosef Bacik /* 3983f3465ca4SJosef Bacik * item0..itemN ... dataN.offset..dataN.size .. data0.size 3984f3465ca4SJosef Bacik */ 3985f3465ca4SJosef Bacik /* first correct the data pointers */ 3986f3465ca4SJosef Bacik for (i = slot; i < nritems; i++) { 3987f3465ca4SJosef Bacik u32 ioff; 3988f3465ca4SJosef Bacik 3989f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, i); 3990cfed81a0SChris Mason ioff = btrfs_token_item_offset(leaf, item, &token); 3991cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 3992cfed81a0SChris Mason ioff - total_data, &token); 3993f3465ca4SJosef Bacik } 3994f3465ca4SJosef Bacik /* shift the items */ 3995f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 3996f3465ca4SJosef Bacik btrfs_item_nr_offset(slot), 3997f3465ca4SJosef Bacik (nritems - slot) * sizeof(struct btrfs_item)); 3998f3465ca4SJosef Bacik 3999f3465ca4SJosef Bacik /* shift the data */ 4000f3465ca4SJosef Bacik memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 4001f3465ca4SJosef Bacik data_end - total_data, btrfs_leaf_data(leaf) + 4002f3465ca4SJosef Bacik data_end, old_data - data_end); 4003f3465ca4SJosef Bacik data_end = old_data; 4004f3465ca4SJosef Bacik } else { 4005f3465ca4SJosef Bacik /* 4006f3465ca4SJosef Bacik * this sucks but it has to be done, if we are inserting at 4007f3465ca4SJosef Bacik * the end of the leaf only insert 1 of the items, since we 4008f3465ca4SJosef Bacik * have no way of knowing whats on the next leaf and we'd have 4009f3465ca4SJosef Bacik * to drop our current locks to figure it out 4010f3465ca4SJosef Bacik */ 4011f3465ca4SJosef Bacik nr = 1; 4012f3465ca4SJosef Bacik } 4013f3465ca4SJosef Bacik 4014f3465ca4SJosef Bacik /* setup the item for the new data */ 4015f3465ca4SJosef Bacik for (i = 0; i < nr; i++) { 4016f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 4017f3465ca4SJosef Bacik btrfs_set_item_key(leaf, &disk_key, slot + i); 4018f3465ca4SJosef Bacik item = btrfs_item_nr(leaf, slot + i); 4019cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 4020cfed81a0SChris Mason data_end - data_size[i], &token); 4021f3465ca4SJosef Bacik data_end -= data_size[i]; 4022cfed81a0SChris Mason btrfs_set_token_item_size(leaf, item, data_size[i], &token); 4023f3465ca4SJosef Bacik } 4024f3465ca4SJosef Bacik btrfs_set_header_nritems(leaf, nritems + nr); 4025f3465ca4SJosef Bacik btrfs_mark_buffer_dirty(leaf); 4026f3465ca4SJosef Bacik 4027f3465ca4SJosef Bacik ret = 0; 4028f3465ca4SJosef Bacik if (slot == 0) { 4029f3465ca4SJosef Bacik btrfs_cpu_key_to_disk(&disk_key, cpu_key); 4030143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 4031f3465ca4SJosef Bacik } 4032f3465ca4SJosef Bacik 4033f3465ca4SJosef Bacik if (btrfs_leaf_free_space(root, leaf) < 0) { 4034f3465ca4SJosef Bacik btrfs_print_leaf(root, leaf); 4035f3465ca4SJosef Bacik BUG(); 4036f3465ca4SJosef Bacik } 4037f3465ca4SJosef Bacik out: 4038f3465ca4SJosef Bacik if (!ret) 4039f3465ca4SJosef Bacik ret = nr; 4040f3465ca4SJosef Bacik return ret; 4041f3465ca4SJosef Bacik } 4042f3465ca4SJosef Bacik 4043f3465ca4SJosef Bacik /* 404444871b1bSChris Mason * this is a helper for btrfs_insert_empty_items, the main goal here is 404544871b1bSChris Mason * to save stack depth by doing the bulk of the work in a function 404644871b1bSChris Mason * that doesn't call btrfs_search_slot 404774123bd7SChris Mason */ 4048143bede5SJeff Mahoney void setup_items_for_insert(struct btrfs_trans_handle *trans, 404944871b1bSChris Mason struct btrfs_root *root, struct btrfs_path *path, 40509c58309dSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 405144871b1bSChris Mason u32 total_data, u32 total_size, int nr) 4052be0e5c09SChris Mason { 40535f39d397SChris Mason struct btrfs_item *item; 40549c58309dSChris Mason int i; 40557518a238SChris Mason u32 nritems; 4056be0e5c09SChris Mason unsigned int data_end; 4057e2fa7227SChris Mason struct btrfs_disk_key disk_key; 405844871b1bSChris Mason struct extent_buffer *leaf; 405944871b1bSChris Mason int slot; 4060cfed81a0SChris Mason struct btrfs_map_token token; 4061cfed81a0SChris Mason 4062cfed81a0SChris Mason btrfs_init_map_token(&token); 4063e2fa7227SChris Mason 40645f39d397SChris Mason leaf = path->nodes[0]; 406544871b1bSChris Mason slot = path->slots[0]; 406674123bd7SChris Mason 40675f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 4068123abc88SChris Mason data_end = leaf_data_end(root, leaf); 4069eb60ceacSChris Mason 4070f25956ccSChris Mason if (btrfs_leaf_free_space(root, leaf) < total_size) { 40713326d1b0SChris Mason btrfs_print_leaf(root, leaf); 4072d397712bSChris Mason printk(KERN_CRIT "not enough freespace need %u have %d\n", 40739c58309dSChris Mason total_size, btrfs_leaf_free_space(root, leaf)); 4074be0e5c09SChris Mason BUG(); 4075d4dbff95SChris Mason } 40765f39d397SChris Mason 4077be0e5c09SChris Mason if (slot != nritems) { 40785f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 4079be0e5c09SChris Mason 40805f39d397SChris Mason if (old_data < data_end) { 40815f39d397SChris Mason btrfs_print_leaf(root, leaf); 4082d397712bSChris Mason printk(KERN_CRIT "slot %d old_data %d data_end %d\n", 40835f39d397SChris Mason slot, old_data, data_end); 40845f39d397SChris Mason BUG_ON(1); 40855f39d397SChris Mason } 4086be0e5c09SChris Mason /* 4087be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 4088be0e5c09SChris Mason */ 4089be0e5c09SChris Mason /* first correct the data pointers */ 40900783fcfcSChris Mason for (i = slot; i < nritems; i++) { 40915f39d397SChris Mason u32 ioff; 4092db94535dSChris Mason 40935f39d397SChris Mason item = btrfs_item_nr(leaf, i); 4094cfed81a0SChris Mason ioff = btrfs_token_item_offset(leaf, item, &token); 4095cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 4096cfed81a0SChris Mason ioff - total_data, &token); 40970783fcfcSChris Mason } 4098be0e5c09SChris Mason /* shift the items */ 40999c58309dSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 41005f39d397SChris Mason btrfs_item_nr_offset(slot), 41010783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 4102be0e5c09SChris Mason 4103be0e5c09SChris Mason /* shift the data */ 41045f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 41059c58309dSChris Mason data_end - total_data, btrfs_leaf_data(leaf) + 4106be0e5c09SChris Mason data_end, old_data - data_end); 4107be0e5c09SChris Mason data_end = old_data; 4108be0e5c09SChris Mason } 41095f39d397SChris Mason 411062e2749eSChris Mason /* setup the item for the new data */ 41119c58309dSChris Mason for (i = 0; i < nr; i++) { 41129c58309dSChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 41139c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 41149c58309dSChris Mason item = btrfs_item_nr(leaf, slot + i); 4115cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 4116cfed81a0SChris Mason data_end - data_size[i], &token); 41179c58309dSChris Mason data_end -= data_size[i]; 4118cfed81a0SChris Mason btrfs_set_token_item_size(leaf, item, data_size[i], &token); 41199c58309dSChris Mason } 412044871b1bSChris Mason 41219c58309dSChris Mason btrfs_set_header_nritems(leaf, nritems + nr); 4122aa5d6bedSChris Mason 41235a01a2e3SChris Mason if (slot == 0) { 41245a01a2e3SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 4125143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 41265a01a2e3SChris Mason } 4127b9473439SChris Mason btrfs_unlock_up_safe(path, 1); 4128b9473439SChris Mason btrfs_mark_buffer_dirty(leaf); 4129aa5d6bedSChris Mason 41305f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 41315f39d397SChris Mason btrfs_print_leaf(root, leaf); 4132be0e5c09SChris Mason BUG(); 41335f39d397SChris Mason } 413444871b1bSChris Mason } 413544871b1bSChris Mason 413644871b1bSChris Mason /* 413744871b1bSChris Mason * Given a key and some data, insert items into the tree. 413844871b1bSChris Mason * This does all the path init required, making room in the tree if needed. 413944871b1bSChris Mason */ 414044871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 414144871b1bSChris Mason struct btrfs_root *root, 414244871b1bSChris Mason struct btrfs_path *path, 414344871b1bSChris Mason struct btrfs_key *cpu_key, u32 *data_size, 414444871b1bSChris Mason int nr) 414544871b1bSChris Mason { 414644871b1bSChris Mason int ret = 0; 414744871b1bSChris Mason int slot; 414844871b1bSChris Mason int i; 414944871b1bSChris Mason u32 total_size = 0; 415044871b1bSChris Mason u32 total_data = 0; 415144871b1bSChris Mason 415244871b1bSChris Mason for (i = 0; i < nr; i++) 415344871b1bSChris Mason total_data += data_size[i]; 415444871b1bSChris Mason 415544871b1bSChris Mason total_size = total_data + (nr * sizeof(struct btrfs_item)); 415644871b1bSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 415744871b1bSChris Mason if (ret == 0) 415844871b1bSChris Mason return -EEXIST; 415944871b1bSChris Mason if (ret < 0) 4160143bede5SJeff Mahoney return ret; 416144871b1bSChris Mason 416244871b1bSChris Mason slot = path->slots[0]; 416344871b1bSChris Mason BUG_ON(slot < 0); 416444871b1bSChris Mason 4165143bede5SJeff Mahoney setup_items_for_insert(trans, root, path, cpu_key, data_size, 416644871b1bSChris Mason total_data, total_size, nr); 4167143bede5SJeff Mahoney return 0; 416862e2749eSChris Mason } 416962e2749eSChris Mason 417062e2749eSChris Mason /* 417162e2749eSChris Mason * Given a key and some data, insert an item into the tree. 417262e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 417362e2749eSChris Mason */ 4174e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 4175e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 4176e089f05cSChris Mason data_size) 417762e2749eSChris Mason { 417862e2749eSChris Mason int ret = 0; 41792c90e5d6SChris Mason struct btrfs_path *path; 41805f39d397SChris Mason struct extent_buffer *leaf; 41815f39d397SChris Mason unsigned long ptr; 418262e2749eSChris Mason 41832c90e5d6SChris Mason path = btrfs_alloc_path(); 4184db5b493aSTsutomu Itoh if (!path) 4185db5b493aSTsutomu Itoh return -ENOMEM; 41862c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 418762e2749eSChris Mason if (!ret) { 41885f39d397SChris Mason leaf = path->nodes[0]; 41895f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 41905f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 41915f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 419262e2749eSChris Mason } 41932c90e5d6SChris Mason btrfs_free_path(path); 4194aa5d6bedSChris Mason return ret; 4195be0e5c09SChris Mason } 4196be0e5c09SChris Mason 419774123bd7SChris Mason /* 41985de08d7dSChris Mason * delete the pointer from a given node. 419974123bd7SChris Mason * 4200d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 4201d352ac68SChris Mason * empty a node. 420274123bd7SChris Mason */ 4203143bede5SJeff Mahoney static void del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 4204f3ea38daSJan Schmidt struct btrfs_path *path, int level, int slot, 4205f3ea38daSJan Schmidt int tree_mod_log) 4206be0e5c09SChris Mason { 42075f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 42087518a238SChris Mason u32 nritems; 4209f3ea38daSJan Schmidt int ret; 4210be0e5c09SChris Mason 42115f39d397SChris Mason nritems = btrfs_header_nritems(parent); 4212be0e5c09SChris Mason if (slot != nritems - 1) { 4213f3ea38daSJan Schmidt if (tree_mod_log && level) 4214f3ea38daSJan Schmidt tree_mod_log_eb_move(root->fs_info, parent, slot, 4215f3ea38daSJan Schmidt slot + 1, nritems - slot - 1); 42165f39d397SChris Mason memmove_extent_buffer(parent, 42175f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 42185f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 4219d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 4220d6025579SChris Mason (nritems - slot - 1)); 4221be0e5c09SChris Mason } 4222f3ea38daSJan Schmidt 4223f3ea38daSJan Schmidt if (tree_mod_log && level) { 4224f3ea38daSJan Schmidt ret = tree_mod_log_insert_key(root->fs_info, parent, slot, 4225f3ea38daSJan Schmidt MOD_LOG_KEY_REMOVE); 4226f3ea38daSJan Schmidt BUG_ON(ret < 0); 4227f3ea38daSJan Schmidt } 4228f3ea38daSJan Schmidt 42297518a238SChris Mason nritems--; 42305f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 42317518a238SChris Mason if (nritems == 0 && parent == root->node) { 42325f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 4233eb60ceacSChris Mason /* just turn the root into a leaf and break */ 42345f39d397SChris Mason btrfs_set_header_level(root->node, 0); 4235bb803951SChris Mason } else if (slot == 0) { 42365f39d397SChris Mason struct btrfs_disk_key disk_key; 42375f39d397SChris Mason 42385f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 4239143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, level + 1); 4240be0e5c09SChris Mason } 4241d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 4242be0e5c09SChris Mason } 4243be0e5c09SChris Mason 424474123bd7SChris Mason /* 4245323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 42465d4f98a2SYan Zheng * path->nodes[1]. 4247323ac95bSChris Mason * 4248323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 4249323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 4250323ac95bSChris Mason * 4251323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 4252323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 4253323ac95bSChris Mason */ 4254143bede5SJeff Mahoney static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans, 4255323ac95bSChris Mason struct btrfs_root *root, 42565d4f98a2SYan Zheng struct btrfs_path *path, 42575d4f98a2SYan Zheng struct extent_buffer *leaf) 4258323ac95bSChris Mason { 42595d4f98a2SYan Zheng WARN_ON(btrfs_header_generation(leaf) != trans->transid); 4260f3ea38daSJan Schmidt del_ptr(trans, root, path, 1, path->slots[1], 1); 4261323ac95bSChris Mason 42624d081c41SChris Mason /* 42634d081c41SChris Mason * btrfs_free_extent is expensive, we want to make sure we 42644d081c41SChris Mason * aren't holding any locks when we call it 42654d081c41SChris Mason */ 42664d081c41SChris Mason btrfs_unlock_up_safe(path, 0); 42674d081c41SChris Mason 4268f0486c68SYan, Zheng root_sub_used(root, leaf->len); 4269f0486c68SYan, Zheng 42703083ee2eSJosef Bacik extent_buffer_get(leaf); 42715581a51aSJan Schmidt btrfs_free_tree_block(trans, root, leaf, 0, 1); 42723083ee2eSJosef Bacik free_extent_buffer_stale(leaf); 4273323ac95bSChris Mason } 4274323ac95bSChris Mason /* 427574123bd7SChris Mason * delete the item at the leaf level in path. If that empties 427674123bd7SChris Mason * the leaf, remove it from the tree 427774123bd7SChris Mason */ 427885e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 427985e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 4280be0e5c09SChris Mason { 42815f39d397SChris Mason struct extent_buffer *leaf; 42825f39d397SChris Mason struct btrfs_item *item; 428385e21bacSChris Mason int last_off; 428485e21bacSChris Mason int dsize = 0; 4285aa5d6bedSChris Mason int ret = 0; 4286aa5d6bedSChris Mason int wret; 428785e21bacSChris Mason int i; 42887518a238SChris Mason u32 nritems; 4289cfed81a0SChris Mason struct btrfs_map_token token; 4290cfed81a0SChris Mason 4291cfed81a0SChris Mason btrfs_init_map_token(&token); 4292be0e5c09SChris Mason 42935f39d397SChris Mason leaf = path->nodes[0]; 429485e21bacSChris Mason last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); 429585e21bacSChris Mason 429685e21bacSChris Mason for (i = 0; i < nr; i++) 429785e21bacSChris Mason dsize += btrfs_item_size_nr(leaf, slot + i); 429885e21bacSChris Mason 42995f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 4300be0e5c09SChris Mason 430185e21bacSChris Mason if (slot + nr != nritems) { 4302123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 43035f39d397SChris Mason 43045f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 4305d6025579SChris Mason data_end + dsize, 4306123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 430785e21bacSChris Mason last_off - data_end); 43085f39d397SChris Mason 430985e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 43105f39d397SChris Mason u32 ioff; 4311db94535dSChris Mason 43125f39d397SChris Mason item = btrfs_item_nr(leaf, i); 4313cfed81a0SChris Mason ioff = btrfs_token_item_offset(leaf, item, &token); 4314cfed81a0SChris Mason btrfs_set_token_item_offset(leaf, item, 4315cfed81a0SChris Mason ioff + dsize, &token); 43160783fcfcSChris Mason } 4317db94535dSChris Mason 43185f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 431985e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 43200783fcfcSChris Mason sizeof(struct btrfs_item) * 432185e21bacSChris Mason (nritems - slot - nr)); 4322be0e5c09SChris Mason } 432385e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 432485e21bacSChris Mason nritems -= nr; 43255f39d397SChris Mason 432674123bd7SChris Mason /* delete the leaf if we've emptied it */ 43277518a238SChris Mason if (nritems == 0) { 43285f39d397SChris Mason if (leaf == root->node) { 43295f39d397SChris Mason btrfs_set_header_level(leaf, 0); 43309a8dd150SChris Mason } else { 4331f0486c68SYan, Zheng btrfs_set_path_blocking(path); 4332f0486c68SYan, Zheng clean_tree_block(trans, root, leaf); 4333143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 43349a8dd150SChris Mason } 4335be0e5c09SChris Mason } else { 43367518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 4337aa5d6bedSChris Mason if (slot == 0) { 43385f39d397SChris Mason struct btrfs_disk_key disk_key; 43395f39d397SChris Mason 43405f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 4341143bede5SJeff Mahoney fixup_low_keys(trans, root, path, &disk_key, 1); 4342aa5d6bedSChris Mason } 4343aa5d6bedSChris Mason 434474123bd7SChris Mason /* delete the leaf if it is mostly empty */ 4345d717aa1dSYan Zheng if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 4346be0e5c09SChris Mason /* push_leaf_left fixes the path. 4347be0e5c09SChris Mason * make sure the path still points to our leaf 4348be0e5c09SChris Mason * for possible call to del_ptr below 4349be0e5c09SChris Mason */ 43504920c9acSChris Mason slot = path->slots[1]; 43515f39d397SChris Mason extent_buffer_get(leaf); 43525f39d397SChris Mason 4353b9473439SChris Mason btrfs_set_path_blocking(path); 435499d8f83cSChris Mason wret = push_leaf_left(trans, root, path, 1, 1, 435599d8f83cSChris Mason 1, (u32)-1); 435654aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 4357aa5d6bedSChris Mason ret = wret; 43585f39d397SChris Mason 43595f39d397SChris Mason if (path->nodes[0] == leaf && 43605f39d397SChris Mason btrfs_header_nritems(leaf)) { 436199d8f83cSChris Mason wret = push_leaf_right(trans, root, path, 1, 436299d8f83cSChris Mason 1, 1, 0); 436354aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 4364aa5d6bedSChris Mason ret = wret; 4365aa5d6bedSChris Mason } 43665f39d397SChris Mason 43675f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 4368323ac95bSChris Mason path->slots[1] = slot; 4369143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 43705f39d397SChris Mason free_extent_buffer(leaf); 4371143bede5SJeff Mahoney ret = 0; 43725de08d7dSChris Mason } else { 4373925baeddSChris Mason /* if we're still in the path, make sure 4374925baeddSChris Mason * we're dirty. Otherwise, one of the 4375925baeddSChris Mason * push_leaf functions must have already 4376925baeddSChris Mason * dirtied this buffer 4377925baeddSChris Mason */ 4378925baeddSChris Mason if (path->nodes[0] == leaf) 43795f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 43805f39d397SChris Mason free_extent_buffer(leaf); 4381be0e5c09SChris Mason } 4382d5719762SChris Mason } else { 43835f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 4384be0e5c09SChris Mason } 43859a8dd150SChris Mason } 4386aa5d6bedSChris Mason return ret; 43879a8dd150SChris Mason } 43889a8dd150SChris Mason 438997571fd0SChris Mason /* 4390925baeddSChris Mason * search the tree again to find a leaf with lesser keys 43917bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 43927bb86316SChris Mason * returns < 0 on io errors. 4393d352ac68SChris Mason * 4394d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 4395d352ac68SChris Mason * time you call it. 43967bb86316SChris Mason */ 43977bb86316SChris Mason int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 43987bb86316SChris Mason { 4399925baeddSChris Mason struct btrfs_key key; 4400925baeddSChris Mason struct btrfs_disk_key found_key; 4401925baeddSChris Mason int ret; 44027bb86316SChris Mason 4403925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 4404925baeddSChris Mason 4405925baeddSChris Mason if (key.offset > 0) 4406925baeddSChris Mason key.offset--; 4407925baeddSChris Mason else if (key.type > 0) 4408925baeddSChris Mason key.type--; 4409925baeddSChris Mason else if (key.objectid > 0) 4410925baeddSChris Mason key.objectid--; 4411925baeddSChris Mason else 44127bb86316SChris Mason return 1; 44137bb86316SChris Mason 4414b3b4aa74SDavid Sterba btrfs_release_path(path); 4415925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4416925baeddSChris Mason if (ret < 0) 4417925baeddSChris Mason return ret; 4418925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 4419925baeddSChris Mason ret = comp_keys(&found_key, &key); 4420925baeddSChris Mason if (ret < 0) 44217bb86316SChris Mason return 0; 4422925baeddSChris Mason return 1; 44237bb86316SChris Mason } 44247bb86316SChris Mason 44253f157a2fSChris Mason /* 44263f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 44273f157a2fSChris Mason * for nodes or leaves that are either in cache or have a minimum 4428d352ac68SChris Mason * transaction id. This is used by the btree defrag code, and tree logging 44293f157a2fSChris Mason * 44303f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 44313f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 44323f157a2fSChris Mason * key and get a writable path. 44333f157a2fSChris Mason * 44343f157a2fSChris Mason * This does lock as it descends, and path->keep_locks should be set 44353f157a2fSChris Mason * to 1 by the caller. 44363f157a2fSChris Mason * 44373f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 44383f157a2fSChris Mason * of the tree. 44393f157a2fSChris Mason * 4440d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 4441d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 4442d352ac68SChris Mason * skipped over (without reading them). 4443d352ac68SChris Mason * 44443f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 44453f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 44463f157a2fSChris Mason */ 44473f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 4448e02119d5SChris Mason struct btrfs_key *max_key, 44493f157a2fSChris Mason struct btrfs_path *path, int cache_only, 44503f157a2fSChris Mason u64 min_trans) 44513f157a2fSChris Mason { 44523f157a2fSChris Mason struct extent_buffer *cur; 44533f157a2fSChris Mason struct btrfs_key found_key; 44543f157a2fSChris Mason int slot; 44559652480bSYan int sret; 44563f157a2fSChris Mason u32 nritems; 44573f157a2fSChris Mason int level; 44583f157a2fSChris Mason int ret = 1; 44593f157a2fSChris Mason 4460934d375bSChris Mason WARN_ON(!path->keep_locks); 44613f157a2fSChris Mason again: 4462bd681513SChris Mason cur = btrfs_read_lock_root_node(root); 44633f157a2fSChris Mason level = btrfs_header_level(cur); 4464e02119d5SChris Mason WARN_ON(path->nodes[level]); 44653f157a2fSChris Mason path->nodes[level] = cur; 4466bd681513SChris Mason path->locks[level] = BTRFS_READ_LOCK; 44673f157a2fSChris Mason 44683f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 44693f157a2fSChris Mason ret = 1; 44703f157a2fSChris Mason goto out; 44713f157a2fSChris Mason } 44723f157a2fSChris Mason while (1) { 44733f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 44743f157a2fSChris Mason level = btrfs_header_level(cur); 44759652480bSYan sret = bin_search(cur, min_key, level, &slot); 44763f157a2fSChris Mason 4477323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 4478323ac95bSChris Mason if (level == path->lowest_level) { 4479e02119d5SChris Mason if (slot >= nritems) 4480e02119d5SChris Mason goto find_next_key; 44813f157a2fSChris Mason ret = 0; 44823f157a2fSChris Mason path->slots[level] = slot; 44833f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 44843f157a2fSChris Mason goto out; 44853f157a2fSChris Mason } 44869652480bSYan if (sret && slot > 0) 44879652480bSYan slot--; 44883f157a2fSChris Mason /* 44893f157a2fSChris Mason * check this node pointer against the cache_only and 44903f157a2fSChris Mason * min_trans parameters. If it isn't in cache or is too 44913f157a2fSChris Mason * old, skip to the next one. 44923f157a2fSChris Mason */ 44933f157a2fSChris Mason while (slot < nritems) { 44943f157a2fSChris Mason u64 blockptr; 44953f157a2fSChris Mason u64 gen; 44963f157a2fSChris Mason struct extent_buffer *tmp; 4497e02119d5SChris Mason struct btrfs_disk_key disk_key; 4498e02119d5SChris Mason 44993f157a2fSChris Mason blockptr = btrfs_node_blockptr(cur, slot); 45003f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 45013f157a2fSChris Mason if (gen < min_trans) { 45023f157a2fSChris Mason slot++; 45033f157a2fSChris Mason continue; 45043f157a2fSChris Mason } 45053f157a2fSChris Mason if (!cache_only) 45063f157a2fSChris Mason break; 45073f157a2fSChris Mason 4508e02119d5SChris Mason if (max_key) { 4509e02119d5SChris Mason btrfs_node_key(cur, &disk_key, slot); 4510e02119d5SChris Mason if (comp_keys(&disk_key, max_key) >= 0) { 4511e02119d5SChris Mason ret = 1; 4512e02119d5SChris Mason goto out; 4513e02119d5SChris Mason } 4514e02119d5SChris Mason } 4515e02119d5SChris Mason 45163f157a2fSChris Mason tmp = btrfs_find_tree_block(root, blockptr, 45173f157a2fSChris Mason btrfs_level_size(root, level - 1)); 45183f157a2fSChris Mason 4519b9fab919SChris Mason if (tmp && btrfs_buffer_uptodate(tmp, gen, 1) > 0) { 45203f157a2fSChris Mason free_extent_buffer(tmp); 45213f157a2fSChris Mason break; 45223f157a2fSChris Mason } 45233f157a2fSChris Mason if (tmp) 45243f157a2fSChris Mason free_extent_buffer(tmp); 45253f157a2fSChris Mason slot++; 45263f157a2fSChris Mason } 4527e02119d5SChris Mason find_next_key: 45283f157a2fSChris Mason /* 45293f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 45303f157a2fSChris Mason * and find another one 45313f157a2fSChris Mason */ 45323f157a2fSChris Mason if (slot >= nritems) { 4533e02119d5SChris Mason path->slots[level] = slot; 4534b4ce94deSChris Mason btrfs_set_path_blocking(path); 4535e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 45363f157a2fSChris Mason cache_only, min_trans); 4537e02119d5SChris Mason if (sret == 0) { 4538b3b4aa74SDavid Sterba btrfs_release_path(path); 45393f157a2fSChris Mason goto again; 45403f157a2fSChris Mason } else { 45413f157a2fSChris Mason goto out; 45423f157a2fSChris Mason } 45433f157a2fSChris Mason } 45443f157a2fSChris Mason /* save our key for returning back */ 45453f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 45463f157a2fSChris Mason path->slots[level] = slot; 45473f157a2fSChris Mason if (level == path->lowest_level) { 45483f157a2fSChris Mason ret = 0; 4549f7c79f30SChris Mason unlock_up(path, level, 1, 0, NULL); 45503f157a2fSChris Mason goto out; 45513f157a2fSChris Mason } 4552b4ce94deSChris Mason btrfs_set_path_blocking(path); 45533f157a2fSChris Mason cur = read_node_slot(root, cur, slot); 455479787eaaSJeff Mahoney BUG_ON(!cur); /* -ENOMEM */ 45553f157a2fSChris Mason 4556bd681513SChris Mason btrfs_tree_read_lock(cur); 4557b4ce94deSChris Mason 4558bd681513SChris Mason path->locks[level - 1] = BTRFS_READ_LOCK; 45593f157a2fSChris Mason path->nodes[level - 1] = cur; 4560f7c79f30SChris Mason unlock_up(path, level, 1, 0, NULL); 4561bd681513SChris Mason btrfs_clear_path_blocking(path, NULL, 0); 45623f157a2fSChris Mason } 45633f157a2fSChris Mason out: 45643f157a2fSChris Mason if (ret == 0) 45653f157a2fSChris Mason memcpy(min_key, &found_key, sizeof(found_key)); 4566b4ce94deSChris Mason btrfs_set_path_blocking(path); 45673f157a2fSChris Mason return ret; 45683f157a2fSChris Mason } 45693f157a2fSChris Mason 45703f157a2fSChris Mason /* 45713f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 45723f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 45733f157a2fSChris Mason * tree based on the current path and the cache_only and min_trans 45743f157a2fSChris Mason * parameters. 45753f157a2fSChris Mason * 45763f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 45773f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 45783f157a2fSChris Mason * 45793f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 45803f157a2fSChris Mason * calling this function. 45813f157a2fSChris Mason */ 4582e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 458333c66f43SYan Zheng struct btrfs_key *key, int level, 45843f157a2fSChris Mason int cache_only, u64 min_trans) 4585e7a84565SChris Mason { 4586e7a84565SChris Mason int slot; 4587e7a84565SChris Mason struct extent_buffer *c; 4588e7a84565SChris Mason 4589934d375bSChris Mason WARN_ON(!path->keep_locks); 4590e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 4591e7a84565SChris Mason if (!path->nodes[level]) 4592e7a84565SChris Mason return 1; 4593e7a84565SChris Mason 4594e7a84565SChris Mason slot = path->slots[level] + 1; 4595e7a84565SChris Mason c = path->nodes[level]; 45963f157a2fSChris Mason next: 4597e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 459833c66f43SYan Zheng int ret; 459933c66f43SYan Zheng int orig_lowest; 460033c66f43SYan Zheng struct btrfs_key cur_key; 460133c66f43SYan Zheng if (level + 1 >= BTRFS_MAX_LEVEL || 460233c66f43SYan Zheng !path->nodes[level + 1]) 4603e7a84565SChris Mason return 1; 460433c66f43SYan Zheng 460533c66f43SYan Zheng if (path->locks[level + 1]) { 460633c66f43SYan Zheng level++; 4607e7a84565SChris Mason continue; 4608e7a84565SChris Mason } 460933c66f43SYan Zheng 461033c66f43SYan Zheng slot = btrfs_header_nritems(c) - 1; 461133c66f43SYan Zheng if (level == 0) 461233c66f43SYan Zheng btrfs_item_key_to_cpu(c, &cur_key, slot); 461333c66f43SYan Zheng else 461433c66f43SYan Zheng btrfs_node_key_to_cpu(c, &cur_key, slot); 461533c66f43SYan Zheng 461633c66f43SYan Zheng orig_lowest = path->lowest_level; 4617b3b4aa74SDavid Sterba btrfs_release_path(path); 461833c66f43SYan Zheng path->lowest_level = level; 461933c66f43SYan Zheng ret = btrfs_search_slot(NULL, root, &cur_key, path, 462033c66f43SYan Zheng 0, 0); 462133c66f43SYan Zheng path->lowest_level = orig_lowest; 462233c66f43SYan Zheng if (ret < 0) 462333c66f43SYan Zheng return ret; 462433c66f43SYan Zheng 462533c66f43SYan Zheng c = path->nodes[level]; 462633c66f43SYan Zheng slot = path->slots[level]; 462733c66f43SYan Zheng if (ret == 0) 462833c66f43SYan Zheng slot++; 462933c66f43SYan Zheng goto next; 463033c66f43SYan Zheng } 463133c66f43SYan Zheng 4632e7a84565SChris Mason if (level == 0) 4633e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 46343f157a2fSChris Mason else { 46353f157a2fSChris Mason u64 blockptr = btrfs_node_blockptr(c, slot); 46363f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 46373f157a2fSChris Mason 46383f157a2fSChris Mason if (cache_only) { 46393f157a2fSChris Mason struct extent_buffer *cur; 46403f157a2fSChris Mason cur = btrfs_find_tree_block(root, blockptr, 46413f157a2fSChris Mason btrfs_level_size(root, level - 1)); 4642b9fab919SChris Mason if (!cur || 4643b9fab919SChris Mason btrfs_buffer_uptodate(cur, gen, 1) <= 0) { 46443f157a2fSChris Mason slot++; 46453f157a2fSChris Mason if (cur) 46463f157a2fSChris Mason free_extent_buffer(cur); 46473f157a2fSChris Mason goto next; 46483f157a2fSChris Mason } 46493f157a2fSChris Mason free_extent_buffer(cur); 46503f157a2fSChris Mason } 46513f157a2fSChris Mason if (gen < min_trans) { 46523f157a2fSChris Mason slot++; 46533f157a2fSChris Mason goto next; 46543f157a2fSChris Mason } 4655e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 46563f157a2fSChris Mason } 4657e7a84565SChris Mason return 0; 4658e7a84565SChris Mason } 4659e7a84565SChris Mason return 1; 4660e7a84565SChris Mason } 4661e7a84565SChris Mason 46627bb86316SChris Mason /* 4663925baeddSChris Mason * search the tree again to find a leaf with greater keys 46640f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 46650f70abe2SChris Mason * returns < 0 on io errors. 466697571fd0SChris Mason */ 4667234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 4668d97e63b6SChris Mason { 4669d97e63b6SChris Mason int slot; 46708e73f275SChris Mason int level; 46715f39d397SChris Mason struct extent_buffer *c; 46728e73f275SChris Mason struct extent_buffer *next; 4673925baeddSChris Mason struct btrfs_key key; 4674925baeddSChris Mason u32 nritems; 4675925baeddSChris Mason int ret; 46768e73f275SChris Mason int old_spinning = path->leave_spinning; 4677bd681513SChris Mason int next_rw_lock = 0; 4678925baeddSChris Mason 4679925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4680d397712bSChris Mason if (nritems == 0) 4681925baeddSChris Mason return 1; 4682925baeddSChris Mason 46838e73f275SChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 46848e73f275SChris Mason again: 46858e73f275SChris Mason level = 1; 46868e73f275SChris Mason next = NULL; 4687bd681513SChris Mason next_rw_lock = 0; 4688b3b4aa74SDavid Sterba btrfs_release_path(path); 46898e73f275SChris Mason 4690a2135011SChris Mason path->keep_locks = 1; 46918e73f275SChris Mason path->leave_spinning = 1; 46928e73f275SChris Mason 4693925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4694925baeddSChris Mason path->keep_locks = 0; 4695925baeddSChris Mason 4696925baeddSChris Mason if (ret < 0) 4697925baeddSChris Mason return ret; 4698925baeddSChris Mason 4699a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4700168fd7d2SChris Mason /* 4701168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 4702168fd7d2SChris Mason * could have added more items next to the key that used to be 4703168fd7d2SChris Mason * at the very end of the block. So, check again here and 4704168fd7d2SChris Mason * advance the path if there are now more items available. 4705168fd7d2SChris Mason */ 4706a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 4707e457afecSYan Zheng if (ret == 0) 4708168fd7d2SChris Mason path->slots[0]++; 47098e73f275SChris Mason ret = 0; 4710925baeddSChris Mason goto done; 4711925baeddSChris Mason } 4712d97e63b6SChris Mason 4713234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 47148e73f275SChris Mason if (!path->nodes[level]) { 47158e73f275SChris Mason ret = 1; 47168e73f275SChris Mason goto done; 47178e73f275SChris Mason } 47185f39d397SChris Mason 4719d97e63b6SChris Mason slot = path->slots[level] + 1; 4720d97e63b6SChris Mason c = path->nodes[level]; 47215f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 4722d97e63b6SChris Mason level++; 47238e73f275SChris Mason if (level == BTRFS_MAX_LEVEL) { 47248e73f275SChris Mason ret = 1; 47258e73f275SChris Mason goto done; 47268e73f275SChris Mason } 4727d97e63b6SChris Mason continue; 4728d97e63b6SChris Mason } 47295f39d397SChris Mason 4730925baeddSChris Mason if (next) { 4731bd681513SChris Mason btrfs_tree_unlock_rw(next, next_rw_lock); 47325f39d397SChris Mason free_extent_buffer(next); 4733925baeddSChris Mason } 47345f39d397SChris Mason 47358e73f275SChris Mason next = c; 4736bd681513SChris Mason next_rw_lock = path->locks[level]; 47378e73f275SChris Mason ret = read_block_for_search(NULL, root, path, &next, level, 47388e73f275SChris Mason slot, &key); 47398e73f275SChris Mason if (ret == -EAGAIN) 47408e73f275SChris Mason goto again; 47415f39d397SChris Mason 474276a05b35SChris Mason if (ret < 0) { 4743b3b4aa74SDavid Sterba btrfs_release_path(path); 474476a05b35SChris Mason goto done; 474576a05b35SChris Mason } 474676a05b35SChris Mason 47475cd57b2cSChris Mason if (!path->skip_locking) { 4748bd681513SChris Mason ret = btrfs_try_tree_read_lock(next); 47498e73f275SChris Mason if (!ret) { 47508e73f275SChris Mason btrfs_set_path_blocking(path); 4751bd681513SChris Mason btrfs_tree_read_lock(next); 4752bd681513SChris Mason btrfs_clear_path_blocking(path, next, 4753bd681513SChris Mason BTRFS_READ_LOCK); 47548e73f275SChris Mason } 4755bd681513SChris Mason next_rw_lock = BTRFS_READ_LOCK; 4756bd681513SChris Mason } 4757d97e63b6SChris Mason break; 4758d97e63b6SChris Mason } 4759d97e63b6SChris Mason path->slots[level] = slot; 4760d97e63b6SChris Mason while (1) { 4761d97e63b6SChris Mason level--; 4762d97e63b6SChris Mason c = path->nodes[level]; 4763925baeddSChris Mason if (path->locks[level]) 4764bd681513SChris Mason btrfs_tree_unlock_rw(c, path->locks[level]); 47658e73f275SChris Mason 47665f39d397SChris Mason free_extent_buffer(c); 4767d97e63b6SChris Mason path->nodes[level] = next; 4768d97e63b6SChris Mason path->slots[level] = 0; 4769a74a4b97SChris Mason if (!path->skip_locking) 4770bd681513SChris Mason path->locks[level] = next_rw_lock; 4771d97e63b6SChris Mason if (!level) 4772d97e63b6SChris Mason break; 4773b4ce94deSChris Mason 47748e73f275SChris Mason ret = read_block_for_search(NULL, root, path, &next, level, 47758e73f275SChris Mason 0, &key); 47768e73f275SChris Mason if (ret == -EAGAIN) 47778e73f275SChris Mason goto again; 47788e73f275SChris Mason 477976a05b35SChris Mason if (ret < 0) { 4780b3b4aa74SDavid Sterba btrfs_release_path(path); 478176a05b35SChris Mason goto done; 478276a05b35SChris Mason } 478376a05b35SChris Mason 47845cd57b2cSChris Mason if (!path->skip_locking) { 4785bd681513SChris Mason ret = btrfs_try_tree_read_lock(next); 47868e73f275SChris Mason if (!ret) { 47878e73f275SChris Mason btrfs_set_path_blocking(path); 4788bd681513SChris Mason btrfs_tree_read_lock(next); 4789bd681513SChris Mason btrfs_clear_path_blocking(path, next, 4790bd681513SChris Mason BTRFS_READ_LOCK); 47918e73f275SChris Mason } 4792bd681513SChris Mason next_rw_lock = BTRFS_READ_LOCK; 4793bd681513SChris Mason } 4794d97e63b6SChris Mason } 47958e73f275SChris Mason ret = 0; 4796925baeddSChris Mason done: 4797f7c79f30SChris Mason unlock_up(path, 0, 1, 0, NULL); 47988e73f275SChris Mason path->leave_spinning = old_spinning; 47998e73f275SChris Mason if (!old_spinning) 48008e73f275SChris Mason btrfs_set_path_blocking(path); 48018e73f275SChris Mason 48028e73f275SChris Mason return ret; 4803d97e63b6SChris Mason } 48040b86a832SChris Mason 48053f157a2fSChris Mason /* 48063f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 48073f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 48083f157a2fSChris Mason * 48093f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 48103f157a2fSChris Mason */ 48110b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 48120b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 48130b86a832SChris Mason int type) 48140b86a832SChris Mason { 48150b86a832SChris Mason struct btrfs_key found_key; 48160b86a832SChris Mason struct extent_buffer *leaf; 4817e02119d5SChris Mason u32 nritems; 48180b86a832SChris Mason int ret; 48190b86a832SChris Mason 48200b86a832SChris Mason while (1) { 48210b86a832SChris Mason if (path->slots[0] == 0) { 4822b4ce94deSChris Mason btrfs_set_path_blocking(path); 48230b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 48240b86a832SChris Mason if (ret != 0) 48250b86a832SChris Mason return ret; 48260b86a832SChris Mason } else { 48270b86a832SChris Mason path->slots[0]--; 48280b86a832SChris Mason } 48290b86a832SChris Mason leaf = path->nodes[0]; 4830e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 4831e02119d5SChris Mason if (nritems == 0) 4832e02119d5SChris Mason return 1; 4833e02119d5SChris Mason if (path->slots[0] == nritems) 4834e02119d5SChris Mason path->slots[0]--; 4835e02119d5SChris Mason 48360b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4837e02119d5SChris Mason if (found_key.objectid < min_objectid) 4838e02119d5SChris Mason break; 48390a4eefbbSYan Zheng if (found_key.type == type) 48400a4eefbbSYan Zheng return 0; 4841e02119d5SChris Mason if (found_key.objectid == min_objectid && 4842e02119d5SChris Mason found_key.type < type) 4843e02119d5SChris Mason break; 48440b86a832SChris Mason } 48450b86a832SChris Mason return 1; 48460b86a832SChris Mason } 4847