1c1d7c514SDavid Sterba // SPDX-License-Identifier: GPL-2.0 26cbd5570SChris Mason /* 3d352ac68SChris Mason * Copyright (C) 2007,2008 Oracle. All rights reserved. 46cbd5570SChris Mason */ 56cbd5570SChris Mason 6a6b6e75eSChris Mason #include <linux/sched.h> 75a0e3ad6STejun Heo #include <linux/slab.h> 8bd989ba3SJan Schmidt #include <linux/rbtree.h> 9adf02123SDavid Sterba #include <linux/mm.h> 10e41d12f5SChristoph Hellwig #include <linux/error-injection.h> 11eb60ceacSChris Mason #include "ctree.h" 12eb60ceacSChris Mason #include "disk-io.h" 137f5c1516SChris Mason #include "transaction.h" 145f39d397SChris Mason #include "print-tree.h" 15925baeddSChris Mason #include "locking.h" 16de37aa51SNikolay Borisov #include "volumes.h" 17f616f5cdSQu Wenruo #include "qgroup.h" 18f3a84ccdSFilipe Manana #include "tree-mod-log.h" 199a8dd150SChris Mason 20e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 21e089f05cSChris Mason *root, struct btrfs_path *path, int level); 22310712b2SOmar Sandoval static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root, 23310712b2SOmar Sandoval const struct btrfs_key *ins_key, struct btrfs_path *path, 24310712b2SOmar Sandoval int data_size, int extend); 255f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 262ff7e61eSJeff Mahoney struct extent_buffer *dst, 27971a1f66SChris Mason struct extent_buffer *src, int empty); 285f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 295f39d397SChris Mason struct extent_buffer *dst_buf, 305f39d397SChris Mason struct extent_buffer *src_buf); 31afe5fea7STsutomu Itoh static void del_ptr(struct btrfs_root *root, struct btrfs_path *path, 32afe5fea7STsutomu Itoh int level, int slot); 33d97e63b6SChris Mason 34af024ed2SJohannes Thumshirn static const struct btrfs_csums { 35af024ed2SJohannes Thumshirn u16 size; 3659a0fcdbSDavid Sterba const char name[10]; 3759a0fcdbSDavid Sterba const char driver[12]; 38af024ed2SJohannes Thumshirn } btrfs_csums[] = { 39af024ed2SJohannes Thumshirn [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" }, 403951e7f0SJohannes Thumshirn [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" }, 413831bf00SJohannes Thumshirn [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" }, 42352ae07bSDavid Sterba [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b", 43352ae07bSDavid Sterba .driver = "blake2b-256" }, 44af024ed2SJohannes Thumshirn }; 45af024ed2SJohannes Thumshirn 46af024ed2SJohannes Thumshirn int btrfs_super_csum_size(const struct btrfs_super_block *s) 47af024ed2SJohannes Thumshirn { 48af024ed2SJohannes Thumshirn u16 t = btrfs_super_csum_type(s); 49af024ed2SJohannes Thumshirn /* 50af024ed2SJohannes Thumshirn * csum type is validated at mount time 51af024ed2SJohannes Thumshirn */ 52af024ed2SJohannes Thumshirn return btrfs_csums[t].size; 53af024ed2SJohannes Thumshirn } 54af024ed2SJohannes Thumshirn 55af024ed2SJohannes Thumshirn const char *btrfs_super_csum_name(u16 csum_type) 56af024ed2SJohannes Thumshirn { 57af024ed2SJohannes Thumshirn /* csum type is validated at mount time */ 58af024ed2SJohannes Thumshirn return btrfs_csums[csum_type].name; 59af024ed2SJohannes Thumshirn } 60af024ed2SJohannes Thumshirn 61b4e967beSDavid Sterba /* 62b4e967beSDavid Sterba * Return driver name if defined, otherwise the name that's also a valid driver 63b4e967beSDavid Sterba * name 64b4e967beSDavid Sterba */ 65b4e967beSDavid Sterba const char *btrfs_super_csum_driver(u16 csum_type) 66b4e967beSDavid Sterba { 67b4e967beSDavid Sterba /* csum type is validated at mount time */ 6859a0fcdbSDavid Sterba return btrfs_csums[csum_type].driver[0] ? 6959a0fcdbSDavid Sterba btrfs_csums[csum_type].driver : 70b4e967beSDavid Sterba btrfs_csums[csum_type].name; 71b4e967beSDavid Sterba } 72b4e967beSDavid Sterba 73604997b4SDavid Sterba size_t __attribute_const__ btrfs_get_num_csums(void) 74f7cea56cSDavid Sterba { 75f7cea56cSDavid Sterba return ARRAY_SIZE(btrfs_csums); 76f7cea56cSDavid Sterba } 77f7cea56cSDavid Sterba 782c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 792c90e5d6SChris Mason { 80e2c89907SMasahiro Yamada return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 812c90e5d6SChris Mason } 822c90e5d6SChris Mason 83d352ac68SChris Mason /* this also releases the path */ 842c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 852c90e5d6SChris Mason { 86ff175d57SJesper Juhl if (!p) 87ff175d57SJesper Juhl return; 88b3b4aa74SDavid Sterba btrfs_release_path(p); 892c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 902c90e5d6SChris Mason } 912c90e5d6SChris Mason 92d352ac68SChris Mason /* 93d352ac68SChris Mason * path release drops references on the extent buffers in the path 94d352ac68SChris Mason * and it drops any locks held by this path 95d352ac68SChris Mason * 96d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 97d352ac68SChris Mason */ 98b3b4aa74SDavid Sterba noinline void btrfs_release_path(struct btrfs_path *p) 99eb60ceacSChris Mason { 100eb60ceacSChris Mason int i; 101a2135011SChris Mason 102234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 1033f157a2fSChris Mason p->slots[i] = 0; 104eb60ceacSChris Mason if (!p->nodes[i]) 105925baeddSChris Mason continue; 106925baeddSChris Mason if (p->locks[i]) { 107bd681513SChris Mason btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]); 108925baeddSChris Mason p->locks[i] = 0; 109925baeddSChris Mason } 1105f39d397SChris Mason free_extent_buffer(p->nodes[i]); 1113f157a2fSChris Mason p->nodes[i] = NULL; 112eb60ceacSChris Mason } 113eb60ceacSChris Mason } 114eb60ceacSChris Mason 115d352ac68SChris Mason /* 116d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 117d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 118d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 119d352ac68SChris Mason * looping required. 120d352ac68SChris Mason * 121d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 122d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 123d352ac68SChris Mason * at any time because there are no locks held. 124d352ac68SChris Mason */ 125925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 126925baeddSChris Mason { 127925baeddSChris Mason struct extent_buffer *eb; 128240f62c8SChris Mason 1293083ee2eSJosef Bacik while (1) { 130240f62c8SChris Mason rcu_read_lock(); 131240f62c8SChris Mason eb = rcu_dereference(root->node); 1323083ee2eSJosef Bacik 1333083ee2eSJosef Bacik /* 1343083ee2eSJosef Bacik * RCU really hurts here, we could free up the root node because 13501327610SNicholas D Steeves * it was COWed but we may not get the new root node yet so do 1363083ee2eSJosef Bacik * the inc_not_zero dance and if it doesn't work then 1373083ee2eSJosef Bacik * synchronize_rcu and try again. 1383083ee2eSJosef Bacik */ 1393083ee2eSJosef Bacik if (atomic_inc_not_zero(&eb->refs)) { 140240f62c8SChris Mason rcu_read_unlock(); 1413083ee2eSJosef Bacik break; 1423083ee2eSJosef Bacik } 1433083ee2eSJosef Bacik rcu_read_unlock(); 1443083ee2eSJosef Bacik synchronize_rcu(); 1453083ee2eSJosef Bacik } 146925baeddSChris Mason return eb; 147925baeddSChris Mason } 148925baeddSChris Mason 14992a7cc42SQu Wenruo /* 15092a7cc42SQu Wenruo * Cowonly root (not-shareable trees, everything not subvolume or reloc roots), 15192a7cc42SQu Wenruo * just get put onto a simple dirty list. Transaction walks this list to make 15292a7cc42SQu Wenruo * sure they get properly updated on disk. 153d352ac68SChris Mason */ 1540b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 1550b86a832SChris Mason { 1560b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 1570b246afaSJeff Mahoney 158e7070be1SJosef Bacik if (test_bit(BTRFS_ROOT_DIRTY, &root->state) || 159e7070be1SJosef Bacik !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state)) 160e7070be1SJosef Bacik return; 161e7070be1SJosef Bacik 1620b246afaSJeff Mahoney spin_lock(&fs_info->trans_lock); 163e7070be1SJosef Bacik if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) { 164e7070be1SJosef Bacik /* Want the extent tree to be the last on the list */ 1654fd786e6SMisono Tomohiro if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID) 166e7070be1SJosef Bacik list_move_tail(&root->dirty_list, 1670b246afaSJeff Mahoney &fs_info->dirty_cowonly_roots); 168e7070be1SJosef Bacik else 169e7070be1SJosef Bacik list_move(&root->dirty_list, 1700b246afaSJeff Mahoney &fs_info->dirty_cowonly_roots); 1710b86a832SChris Mason } 1720b246afaSJeff Mahoney spin_unlock(&fs_info->trans_lock); 1730b86a832SChris Mason } 1740b86a832SChris Mason 175d352ac68SChris Mason /* 176d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 177d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 178d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 179d352ac68SChris Mason */ 180be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 181be20aa9dSChris Mason struct btrfs_root *root, 182be20aa9dSChris Mason struct extent_buffer *buf, 183be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 184be20aa9dSChris Mason { 1850b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 186be20aa9dSChris Mason struct extent_buffer *cow; 187be20aa9dSChris Mason int ret = 0; 188be20aa9dSChris Mason int level; 1895d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 190be20aa9dSChris Mason 19192a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 1920b246afaSJeff Mahoney trans->transid != fs_info->running_transaction->transid); 19392a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 19427cdeb70SMiao Xie trans->transid != root->last_trans); 195be20aa9dSChris Mason 196be20aa9dSChris Mason level = btrfs_header_level(buf); 1975d4f98a2SYan Zheng if (level == 0) 1985d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 1995d4f98a2SYan Zheng else 2005d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 20131840ae1SZheng Yan 2024d75f8a9SDavid Sterba cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid, 203cf6f34aaSJosef Bacik &disk_key, level, buf->start, 0, 204cf6f34aaSJosef Bacik BTRFS_NESTING_NEW_ROOT); 2055d4f98a2SYan Zheng if (IS_ERR(cow)) 206be20aa9dSChris Mason return PTR_ERR(cow); 207be20aa9dSChris Mason 20858e8012cSDavid Sterba copy_extent_buffer_full(cow, buf); 209be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 210be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 2115d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 2125d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 2135d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 2145d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 2155d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 2165d4f98a2SYan Zheng else 217be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 218be20aa9dSChris Mason 219de37aa51SNikolay Borisov write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid); 2202b82032cSYan Zheng 221be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 2225d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 223e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 2245d4f98a2SYan Zheng else 225e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 0); 226867ed321SJosef Bacik if (ret) { 22772c9925fSFilipe Manana btrfs_tree_unlock(cow); 22872c9925fSFilipe Manana free_extent_buffer(cow); 229867ed321SJosef Bacik btrfs_abort_transaction(trans, ret); 230be20aa9dSChris Mason return ret; 231867ed321SJosef Bacik } 232be20aa9dSChris Mason 233be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 234be20aa9dSChris Mason *cow_ret = cow; 235be20aa9dSChris Mason return 0; 236be20aa9dSChris Mason } 237be20aa9dSChris Mason 238d352ac68SChris Mason /* 2395d4f98a2SYan Zheng * check if the tree block can be shared by multiple trees 2405d4f98a2SYan Zheng */ 2415d4f98a2SYan Zheng int btrfs_block_can_be_shared(struct btrfs_root *root, 2425d4f98a2SYan Zheng struct extent_buffer *buf) 2435d4f98a2SYan Zheng { 2445d4f98a2SYan Zheng /* 24592a7cc42SQu Wenruo * Tree blocks not in shareable trees and tree roots are never shared. 24692a7cc42SQu Wenruo * If a block was allocated after the last snapshot and the block was 24792a7cc42SQu Wenruo * not allocated by tree relocation, we know the block is not shared. 2485d4f98a2SYan Zheng */ 24992a7cc42SQu Wenruo if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 2505d4f98a2SYan Zheng buf != root->node && buf != root->commit_root && 2515d4f98a2SYan Zheng (btrfs_header_generation(buf) <= 2525d4f98a2SYan Zheng btrfs_root_last_snapshot(&root->root_item) || 2535d4f98a2SYan Zheng btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 2545d4f98a2SYan Zheng return 1; 255a79865c6SNikolay Borisov 2565d4f98a2SYan Zheng return 0; 2575d4f98a2SYan Zheng } 2585d4f98a2SYan Zheng 2595d4f98a2SYan Zheng static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans, 2605d4f98a2SYan Zheng struct btrfs_root *root, 2615d4f98a2SYan Zheng struct extent_buffer *buf, 262f0486c68SYan, Zheng struct extent_buffer *cow, 263f0486c68SYan, Zheng int *last_ref) 2645d4f98a2SYan Zheng { 2650b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 2665d4f98a2SYan Zheng u64 refs; 2675d4f98a2SYan Zheng u64 owner; 2685d4f98a2SYan Zheng u64 flags; 2695d4f98a2SYan Zheng u64 new_flags = 0; 2705d4f98a2SYan Zheng int ret; 2715d4f98a2SYan Zheng 2725d4f98a2SYan Zheng /* 2735d4f98a2SYan Zheng * Backrefs update rules: 2745d4f98a2SYan Zheng * 2755d4f98a2SYan Zheng * Always use full backrefs for extent pointers in tree block 2765d4f98a2SYan Zheng * allocated by tree relocation. 2775d4f98a2SYan Zheng * 2785d4f98a2SYan Zheng * If a shared tree block is no longer referenced by its owner 2795d4f98a2SYan Zheng * tree (btrfs_header_owner(buf) == root->root_key.objectid), 2805d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 2815d4f98a2SYan Zheng * 2825d4f98a2SYan Zheng * If a tree block is been relocating 2835d4f98a2SYan Zheng * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID), 2845d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 2855d4f98a2SYan Zheng * The reason for this is some operations (such as drop tree) 2865d4f98a2SYan Zheng * are only allowed for blocks use full backrefs. 2875d4f98a2SYan Zheng */ 2885d4f98a2SYan Zheng 2895d4f98a2SYan Zheng if (btrfs_block_can_be_shared(root, buf)) { 2902ff7e61eSJeff Mahoney ret = btrfs_lookup_extent_info(trans, fs_info, buf->start, 2913173a18fSJosef Bacik btrfs_header_level(buf), 1, 2923173a18fSJosef Bacik &refs, &flags); 293be1a5564SMark Fasheh if (ret) 294be1a5564SMark Fasheh return ret; 295e5df9573SMark Fasheh if (refs == 0) { 296e5df9573SMark Fasheh ret = -EROFS; 2970b246afaSJeff Mahoney btrfs_handle_fs_error(fs_info, ret, NULL); 298e5df9573SMark Fasheh return ret; 299e5df9573SMark Fasheh } 3005d4f98a2SYan Zheng } else { 3015d4f98a2SYan Zheng refs = 1; 3025d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 3035d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 3045d4f98a2SYan Zheng flags = BTRFS_BLOCK_FLAG_FULL_BACKREF; 3055d4f98a2SYan Zheng else 3065d4f98a2SYan Zheng flags = 0; 3075d4f98a2SYan Zheng } 3085d4f98a2SYan Zheng 3095d4f98a2SYan Zheng owner = btrfs_header_owner(buf); 3105d4f98a2SYan Zheng BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID && 3115d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)); 3125d4f98a2SYan Zheng 3135d4f98a2SYan Zheng if (refs > 1) { 3145d4f98a2SYan Zheng if ((owner == root->root_key.objectid || 3155d4f98a2SYan Zheng root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && 3165d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 317e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, buf, 1); 318692826b2SJeff Mahoney if (ret) 319692826b2SJeff Mahoney return ret; 3205d4f98a2SYan Zheng 3215d4f98a2SYan Zheng if (root->root_key.objectid == 3225d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 323e339a6b0SJosef Bacik ret = btrfs_dec_ref(trans, root, buf, 0); 324692826b2SJeff Mahoney if (ret) 325692826b2SJeff Mahoney return ret; 326e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 327692826b2SJeff Mahoney if (ret) 328692826b2SJeff Mahoney return ret; 3295d4f98a2SYan Zheng } 3305d4f98a2SYan Zheng new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; 3315d4f98a2SYan Zheng } else { 3325d4f98a2SYan Zheng 3335d4f98a2SYan Zheng if (root->root_key.objectid == 3345d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 335e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 3365d4f98a2SYan Zheng else 337e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 0); 338692826b2SJeff Mahoney if (ret) 339692826b2SJeff Mahoney return ret; 3405d4f98a2SYan Zheng } 3415d4f98a2SYan Zheng if (new_flags != 0) { 342b1c79e09SJosef Bacik int level = btrfs_header_level(buf); 343b1c79e09SJosef Bacik 34442c9d0b5SDavid Sterba ret = btrfs_set_disk_extent_flags(trans, buf, 345b1c79e09SJosef Bacik new_flags, level, 0); 346be1a5564SMark Fasheh if (ret) 347be1a5564SMark Fasheh return ret; 3485d4f98a2SYan Zheng } 3495d4f98a2SYan Zheng } else { 3505d4f98a2SYan Zheng if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { 3515d4f98a2SYan Zheng if (root->root_key.objectid == 3525d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 353e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 3545d4f98a2SYan Zheng else 355e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 0); 356692826b2SJeff Mahoney if (ret) 357692826b2SJeff Mahoney return ret; 358e339a6b0SJosef Bacik ret = btrfs_dec_ref(trans, root, buf, 1); 359692826b2SJeff Mahoney if (ret) 360692826b2SJeff Mahoney return ret; 3615d4f98a2SYan Zheng } 3626a884d7dSDavid Sterba btrfs_clean_tree_block(buf); 363f0486c68SYan, Zheng *last_ref = 1; 3645d4f98a2SYan Zheng } 3655d4f98a2SYan Zheng return 0; 3665d4f98a2SYan Zheng } 3675d4f98a2SYan Zheng 3685d4f98a2SYan Zheng /* 369d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 370d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 371d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 372d397712bSChris Mason * dirty again. 373d352ac68SChris Mason * 374d352ac68SChris Mason * search_start -- an allocation hint for the new block 375d352ac68SChris Mason * 376d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 377d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 378d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 379d352ac68SChris Mason */ 380d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 3815f39d397SChris Mason struct btrfs_root *root, 3825f39d397SChris Mason struct extent_buffer *buf, 3835f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 3845f39d397SChris Mason struct extent_buffer **cow_ret, 3859631e4ccSJosef Bacik u64 search_start, u64 empty_size, 3869631e4ccSJosef Bacik enum btrfs_lock_nesting nest) 3876702ed49SChris Mason { 3880b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 3895d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 3905f39d397SChris Mason struct extent_buffer *cow; 391be1a5564SMark Fasheh int level, ret; 392f0486c68SYan, Zheng int last_ref = 0; 393925baeddSChris Mason int unlock_orig = 0; 3940f5053ebSGoldwyn Rodrigues u64 parent_start = 0; 3956702ed49SChris Mason 396925baeddSChris Mason if (*cow_ret == buf) 397925baeddSChris Mason unlock_orig = 1; 398925baeddSChris Mason 39949d0c642SFilipe Manana btrfs_assert_tree_write_locked(buf); 400925baeddSChris Mason 40192a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 4020b246afaSJeff Mahoney trans->transid != fs_info->running_transaction->transid); 40392a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 40427cdeb70SMiao Xie trans->transid != root->last_trans); 4055f39d397SChris Mason 4067bb86316SChris Mason level = btrfs_header_level(buf); 40731840ae1SZheng Yan 4085d4f98a2SYan Zheng if (level == 0) 4095d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 4105d4f98a2SYan Zheng else 4115d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 4125d4f98a2SYan Zheng 4130f5053ebSGoldwyn Rodrigues if ((root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && parent) 4145d4f98a2SYan Zheng parent_start = parent->start; 4155d4f98a2SYan Zheng 41679bd3712SFilipe Manana cow = btrfs_alloc_tree_block(trans, root, parent_start, 41779bd3712SFilipe Manana root->root_key.objectid, &disk_key, level, 41879bd3712SFilipe Manana search_start, empty_size, nest); 4196702ed49SChris Mason if (IS_ERR(cow)) 4206702ed49SChris Mason return PTR_ERR(cow); 4216702ed49SChris Mason 422b4ce94deSChris Mason /* cow is set to blocking by btrfs_init_new_buffer */ 423b4ce94deSChris Mason 42458e8012cSDavid Sterba copy_extent_buffer_full(cow, buf); 425db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 4265f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 4275d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 4285d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 4295d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 4305d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 4315d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 4325d4f98a2SYan Zheng else 4335f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 4346702ed49SChris Mason 435de37aa51SNikolay Borisov write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid); 4362b82032cSYan Zheng 437be1a5564SMark Fasheh ret = update_ref_for_cow(trans, root, buf, cow, &last_ref); 438b68dc2a9SMark Fasheh if (ret) { 439572c83acSJosef Bacik btrfs_tree_unlock(cow); 440572c83acSJosef Bacik free_extent_buffer(cow); 44166642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 442b68dc2a9SMark Fasheh return ret; 443b68dc2a9SMark Fasheh } 4441a40e23bSZheng Yan 44592a7cc42SQu Wenruo if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) { 44683d4cfd4SJosef Bacik ret = btrfs_reloc_cow_block(trans, root, buf, cow); 44793314e3bSZhaolei if (ret) { 448572c83acSJosef Bacik btrfs_tree_unlock(cow); 449572c83acSJosef Bacik free_extent_buffer(cow); 45066642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 45183d4cfd4SJosef Bacik return ret; 45283d4cfd4SJosef Bacik } 45393314e3bSZhaolei } 4543fd0a558SYan, Zheng 4556702ed49SChris Mason if (buf == root->node) { 456925baeddSChris Mason WARN_ON(parent && parent != buf); 4575d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 4585d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 4595d4f98a2SYan Zheng parent_start = buf->start; 460925baeddSChris Mason 46167439dadSDavid Sterba atomic_inc(&cow->refs); 462406808abSFilipe Manana ret = btrfs_tree_mod_log_insert_root(root->node, cow, true); 463d9d19a01SDavid Sterba BUG_ON(ret < 0); 464240f62c8SChris Mason rcu_assign_pointer(root->node, cow); 465925baeddSChris Mason 4667a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(root), buf, 4677a163608SFilipe Manana parent_start, last_ref); 4685f39d397SChris Mason free_extent_buffer(buf); 4690b86a832SChris Mason add_root_to_dirty_list(root); 4706702ed49SChris Mason } else { 4715d4f98a2SYan Zheng WARN_ON(trans->transid != btrfs_header_generation(parent)); 472f3a84ccdSFilipe Manana btrfs_tree_mod_log_insert_key(parent, parent_slot, 473f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 4745f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 475db94535dSChris Mason cow->start); 47674493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 47774493f7aSChris Mason trans->transid); 4786702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 4795de865eeSFilipe David Borba Manana if (last_ref) { 480f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_free_eb(buf); 4815de865eeSFilipe David Borba Manana if (ret) { 482572c83acSJosef Bacik btrfs_tree_unlock(cow); 483572c83acSJosef Bacik free_extent_buffer(cow); 48466642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 4855de865eeSFilipe David Borba Manana return ret; 4865de865eeSFilipe David Borba Manana } 4875de865eeSFilipe David Borba Manana } 4887a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(root), buf, 4897a163608SFilipe Manana parent_start, last_ref); 4906702ed49SChris Mason } 491925baeddSChris Mason if (unlock_orig) 492925baeddSChris Mason btrfs_tree_unlock(buf); 4933083ee2eSJosef Bacik free_extent_buffer_stale(buf); 4946702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 4956702ed49SChris Mason *cow_ret = cow; 4966702ed49SChris Mason return 0; 4976702ed49SChris Mason } 4986702ed49SChris Mason 4995d4f98a2SYan Zheng static inline int should_cow_block(struct btrfs_trans_handle *trans, 5005d4f98a2SYan Zheng struct btrfs_root *root, 5015d4f98a2SYan Zheng struct extent_buffer *buf) 5025d4f98a2SYan Zheng { 503f5ee5c9aSJeff Mahoney if (btrfs_is_testing(root->fs_info)) 504faa2dbf0SJosef Bacik return 0; 505fccb84c9SDavid Sterba 506d1980131SDavid Sterba /* Ensure we can see the FORCE_COW bit */ 507d1980131SDavid Sterba smp_mb__before_atomic(); 508f1ebcc74SLiu Bo 509f1ebcc74SLiu Bo /* 510f1ebcc74SLiu Bo * We do not need to cow a block if 511f1ebcc74SLiu Bo * 1) this block is not created or changed in this transaction; 512f1ebcc74SLiu Bo * 2) this block does not belong to TREE_RELOC tree; 513f1ebcc74SLiu Bo * 3) the root is not forced COW. 514f1ebcc74SLiu Bo * 515f1ebcc74SLiu Bo * What is forced COW: 51601327610SNicholas D Steeves * when we create snapshot during committing the transaction, 51752042d8eSAndrea Gelmini * after we've finished copying src root, we must COW the shared 518f1ebcc74SLiu Bo * block to ensure the metadata consistency. 519f1ebcc74SLiu Bo */ 5205d4f98a2SYan Zheng if (btrfs_header_generation(buf) == trans->transid && 5215d4f98a2SYan Zheng !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) && 5225d4f98a2SYan Zheng !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID && 523f1ebcc74SLiu Bo btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) && 52427cdeb70SMiao Xie !test_bit(BTRFS_ROOT_FORCE_COW, &root->state)) 5255d4f98a2SYan Zheng return 0; 5265d4f98a2SYan Zheng return 1; 5275d4f98a2SYan Zheng } 5285d4f98a2SYan Zheng 529d352ac68SChris Mason /* 530d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 53101327610SNicholas D Steeves * This version of it has extra checks so that a block isn't COWed more than 532d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 533d352ac68SChris Mason */ 534d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 5355f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 5365f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 5379631e4ccSJosef Bacik struct extent_buffer **cow_ret, 5389631e4ccSJosef Bacik enum btrfs_lock_nesting nest) 53902217ed2SChris Mason { 5400b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 5416702ed49SChris Mason u64 search_start; 542f510cfecSChris Mason int ret; 543dc17ff8fSChris Mason 54483354f07SJosef Bacik if (test_bit(BTRFS_ROOT_DELETING, &root->state)) 54583354f07SJosef Bacik btrfs_err(fs_info, 54683354f07SJosef Bacik "COW'ing blocks on a fs root that's being dropped"); 54783354f07SJosef Bacik 5480b246afaSJeff Mahoney if (trans->transaction != fs_info->running_transaction) 54931b1a2bdSJulia Lawall WARN(1, KERN_CRIT "trans %llu running %llu\n", 550c1c9ff7cSGeert Uytterhoeven trans->transid, 5510b246afaSJeff Mahoney fs_info->running_transaction->transid); 55231b1a2bdSJulia Lawall 5530b246afaSJeff Mahoney if (trans->transid != fs_info->generation) 55431b1a2bdSJulia Lawall WARN(1, KERN_CRIT "trans %llu running %llu\n", 5550b246afaSJeff Mahoney trans->transid, fs_info->generation); 556dc17ff8fSChris Mason 5575d4f98a2SYan Zheng if (!should_cow_block(trans, root, buf)) { 55802217ed2SChris Mason *cow_ret = buf; 55902217ed2SChris Mason return 0; 56002217ed2SChris Mason } 561c487685dSChris Mason 562ee22184bSByongho Lee search_start = buf->start & ~((u64)SZ_1G - 1); 563b4ce94deSChris Mason 564f616f5cdSQu Wenruo /* 565f616f5cdSQu Wenruo * Before CoWing this block for later modification, check if it's 566f616f5cdSQu Wenruo * the subtree root and do the delayed subtree trace if needed. 567f616f5cdSQu Wenruo * 568f616f5cdSQu Wenruo * Also We don't care about the error, as it's handled internally. 569f616f5cdSQu Wenruo */ 570f616f5cdSQu Wenruo btrfs_qgroup_trace_subtree_after_cow(trans, root, buf); 571f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 5729631e4ccSJosef Bacik parent_slot, cow_ret, search_start, 0, nest); 5731abe9b8aSliubo 5741abe9b8aSliubo trace_btrfs_cow_block(root, buf, *cow_ret); 5751abe9b8aSliubo 576f510cfecSChris Mason return ret; 5772c90e5d6SChris Mason } 578f75e2b79SJosef Bacik ALLOW_ERROR_INJECTION(btrfs_cow_block, ERRNO); 5796702ed49SChris Mason 580d352ac68SChris Mason /* 581d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 582d352ac68SChris Mason * node are actually close by 583d352ac68SChris Mason */ 5846b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 5856702ed49SChris Mason { 5866b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 5876702ed49SChris Mason return 1; 5886b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 5896702ed49SChris Mason return 1; 59002217ed2SChris Mason return 0; 59102217ed2SChris Mason } 59202217ed2SChris Mason 593ce6ef5abSDavid Sterba #ifdef __LITTLE_ENDIAN 594ce6ef5abSDavid Sterba 595ce6ef5abSDavid Sterba /* 596ce6ef5abSDavid Sterba * Compare two keys, on little-endian the disk order is same as CPU order and 597ce6ef5abSDavid Sterba * we can avoid the conversion. 598ce6ef5abSDavid Sterba */ 599ce6ef5abSDavid Sterba static int comp_keys(const struct btrfs_disk_key *disk_key, 600ce6ef5abSDavid Sterba const struct btrfs_key *k2) 601ce6ef5abSDavid Sterba { 602ce6ef5abSDavid Sterba const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key; 603ce6ef5abSDavid Sterba 604ce6ef5abSDavid Sterba return btrfs_comp_cpu_keys(k1, k2); 605ce6ef5abSDavid Sterba } 606ce6ef5abSDavid Sterba 607ce6ef5abSDavid Sterba #else 608ce6ef5abSDavid Sterba 609081e9573SChris Mason /* 610081e9573SChris Mason * compare two keys in a memcmp fashion 611081e9573SChris Mason */ 612310712b2SOmar Sandoval static int comp_keys(const struct btrfs_disk_key *disk, 613310712b2SOmar Sandoval const struct btrfs_key *k2) 614081e9573SChris Mason { 615081e9573SChris Mason struct btrfs_key k1; 616081e9573SChris Mason 617081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 618081e9573SChris Mason 61920736abaSDiego Calleja return btrfs_comp_cpu_keys(&k1, k2); 620081e9573SChris Mason } 621ce6ef5abSDavid Sterba #endif 622081e9573SChris Mason 623f3465ca4SJosef Bacik /* 624f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 625f3465ca4SJosef Bacik */ 626e1f60a65SDavid Sterba int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2) 627f3465ca4SJosef Bacik { 628f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 629f3465ca4SJosef Bacik return 1; 630f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 631f3465ca4SJosef Bacik return -1; 632f3465ca4SJosef Bacik if (k1->type > k2->type) 633f3465ca4SJosef Bacik return 1; 634f3465ca4SJosef Bacik if (k1->type < k2->type) 635f3465ca4SJosef Bacik return -1; 636f3465ca4SJosef Bacik if (k1->offset > k2->offset) 637f3465ca4SJosef Bacik return 1; 638f3465ca4SJosef Bacik if (k1->offset < k2->offset) 639f3465ca4SJosef Bacik return -1; 640f3465ca4SJosef Bacik return 0; 641f3465ca4SJosef Bacik } 642081e9573SChris Mason 643d352ac68SChris Mason /* 644d352ac68SChris Mason * this is used by the defrag code to go through all the 645d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 646d352ac68SChris Mason * disk order is close to key order 647d352ac68SChris Mason */ 6486702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 6495f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 650de78b51aSEric Sandeen int start_slot, u64 *last_ret, 651a6b6e75eSChris Mason struct btrfs_key *progress) 6526702ed49SChris Mason { 6530b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 6546b80053dSChris Mason struct extent_buffer *cur; 6556702ed49SChris Mason u64 blocknr; 656e9d0b13bSChris Mason u64 search_start = *last_ret; 657e9d0b13bSChris Mason u64 last_block = 0; 6586702ed49SChris Mason u64 other; 6596702ed49SChris Mason u32 parent_nritems; 6606702ed49SChris Mason int end_slot; 6616702ed49SChris Mason int i; 6626702ed49SChris Mason int err = 0; 6636b80053dSChris Mason u32 blocksize; 664081e9573SChris Mason int progress_passed = 0; 665081e9573SChris Mason struct btrfs_disk_key disk_key; 6666702ed49SChris Mason 6670b246afaSJeff Mahoney WARN_ON(trans->transaction != fs_info->running_transaction); 6680b246afaSJeff Mahoney WARN_ON(trans->transid != fs_info->generation); 66986479a04SChris Mason 6706b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 6710b246afaSJeff Mahoney blocksize = fs_info->nodesize; 6725dfe2be7SFilipe Manana end_slot = parent_nritems - 1; 6736702ed49SChris Mason 6745dfe2be7SFilipe Manana if (parent_nritems <= 1) 6756702ed49SChris Mason return 0; 6766702ed49SChris Mason 6775dfe2be7SFilipe Manana for (i = start_slot; i <= end_slot; i++) { 6786702ed49SChris Mason int close = 1; 679a6b6e75eSChris Mason 680081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 681081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 682081e9573SChris Mason continue; 683081e9573SChris Mason 684081e9573SChris Mason progress_passed = 1; 6856b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 686e9d0b13bSChris Mason if (last_block == 0) 687e9d0b13bSChris Mason last_block = blocknr; 6885708b959SChris Mason 6896702ed49SChris Mason if (i > 0) { 6906b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 6916b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 6926702ed49SChris Mason } 6935dfe2be7SFilipe Manana if (!close && i < end_slot) { 6946b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 6956b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 6966702ed49SChris Mason } 697e9d0b13bSChris Mason if (close) { 698e9d0b13bSChris Mason last_block = blocknr; 6996702ed49SChris Mason continue; 700e9d0b13bSChris Mason } 7016702ed49SChris Mason 702206983b7SJosef Bacik cur = btrfs_read_node_slot(parent, i); 703206983b7SJosef Bacik if (IS_ERR(cur)) 70464c043deSLiu Bo return PTR_ERR(cur); 705e9d0b13bSChris Mason if (search_start == 0) 7066b80053dSChris Mason search_start = last_block; 707e9d0b13bSChris Mason 708e7a84565SChris Mason btrfs_tree_lock(cur); 7096b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 710e7a84565SChris Mason &cur, search_start, 7116b80053dSChris Mason min(16 * blocksize, 7129631e4ccSJosef Bacik (end_slot - i) * blocksize), 7139631e4ccSJosef Bacik BTRFS_NESTING_COW); 714252c38f0SYan if (err) { 715e7a84565SChris Mason btrfs_tree_unlock(cur); 7166b80053dSChris Mason free_extent_buffer(cur); 7176702ed49SChris Mason break; 718252c38f0SYan } 719e7a84565SChris Mason search_start = cur->start; 720e7a84565SChris Mason last_block = cur->start; 721f2183bdeSChris Mason *last_ret = search_start; 722e7a84565SChris Mason btrfs_tree_unlock(cur); 723e7a84565SChris Mason free_extent_buffer(cur); 7246702ed49SChris Mason } 7256702ed49SChris Mason return err; 7266702ed49SChris Mason } 7276702ed49SChris Mason 72874123bd7SChris Mason /* 7295f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 73067d5e289SMarcos Paulo de Souza * and they are item_size apart. 7315f39d397SChris Mason * 73274123bd7SChris Mason * the slot in the array is returned via slot, and it points to 73374123bd7SChris Mason * the place where you would insert key if it is not found in 73474123bd7SChris Mason * the array. 73574123bd7SChris Mason * 73667d5e289SMarcos Paulo de Souza * Slot may point to total number of items if the key is bigger than 73767d5e289SMarcos Paulo de Souza * all of the keys 73874123bd7SChris Mason */ 739e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 740310712b2SOmar Sandoval unsigned long p, int item_size, 74167d5e289SMarcos Paulo de Souza const struct btrfs_key *key, int *slot) 742be0e5c09SChris Mason { 743be0e5c09SChris Mason int low = 0; 74467d5e289SMarcos Paulo de Souza int high = btrfs_header_nritems(eb); 745be0e5c09SChris Mason int ret; 7465cd17f34SDavid Sterba const int key_size = sizeof(struct btrfs_disk_key); 747be0e5c09SChris Mason 7485e24e9afSLiu Bo if (low > high) { 7495e24e9afSLiu Bo btrfs_err(eb->fs_info, 7505e24e9afSLiu Bo "%s: low (%d) > high (%d) eb %llu owner %llu level %d", 7515e24e9afSLiu Bo __func__, low, high, eb->start, 7525e24e9afSLiu Bo btrfs_header_owner(eb), btrfs_header_level(eb)); 7535e24e9afSLiu Bo return -EINVAL; 7545e24e9afSLiu Bo } 7555e24e9afSLiu Bo 756be0e5c09SChris Mason while (low < high) { 7575cd17f34SDavid Sterba unsigned long oip; 7585cd17f34SDavid Sterba unsigned long offset; 7595cd17f34SDavid Sterba struct btrfs_disk_key *tmp; 7605cd17f34SDavid Sterba struct btrfs_disk_key unaligned; 7615cd17f34SDavid Sterba int mid; 7625cd17f34SDavid Sterba 763be0e5c09SChris Mason mid = (low + high) / 2; 7645f39d397SChris Mason offset = p + mid * item_size; 7655cd17f34SDavid Sterba oip = offset_in_page(offset); 7665f39d397SChris Mason 7675cd17f34SDavid Sterba if (oip + key_size <= PAGE_SIZE) { 768884b07d0SQu Wenruo const unsigned long idx = get_eb_page_index(offset); 7695cd17f34SDavid Sterba char *kaddr = page_address(eb->pages[idx]); 770934d375bSChris Mason 771884b07d0SQu Wenruo oip = get_eb_offset_in_page(eb, offset); 7725cd17f34SDavid Sterba tmp = (struct btrfs_disk_key *)(kaddr + oip); 7735cd17f34SDavid Sterba } else { 7745cd17f34SDavid Sterba read_extent_buffer(eb, &unaligned, offset, key_size); 7755f39d397SChris Mason tmp = &unaligned; 776479965d6SChris Mason } 777479965d6SChris Mason 778be0e5c09SChris Mason ret = comp_keys(tmp, key); 779be0e5c09SChris Mason 780be0e5c09SChris Mason if (ret < 0) 781be0e5c09SChris Mason low = mid + 1; 782be0e5c09SChris Mason else if (ret > 0) 783be0e5c09SChris Mason high = mid; 784be0e5c09SChris Mason else { 785be0e5c09SChris Mason *slot = mid; 786be0e5c09SChris Mason return 0; 787be0e5c09SChris Mason } 788be0e5c09SChris Mason } 789be0e5c09SChris Mason *slot = low; 790be0e5c09SChris Mason return 1; 791be0e5c09SChris Mason } 792be0e5c09SChris Mason 79397571fd0SChris Mason /* 79497571fd0SChris Mason * simple bin_search frontend that does the right thing for 79597571fd0SChris Mason * leaves vs nodes 79697571fd0SChris Mason */ 797a74b35ecSNikolay Borisov int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key, 798e3b83361SQu Wenruo int *slot) 799be0e5c09SChris Mason { 800e3b83361SQu Wenruo if (btrfs_header_level(eb) == 0) 8015f39d397SChris Mason return generic_bin_search(eb, 8025f39d397SChris Mason offsetof(struct btrfs_leaf, items), 80367d5e289SMarcos Paulo de Souza sizeof(struct btrfs_item), key, slot); 804f775738fSWang Sheng-Hui else 8055f39d397SChris Mason return generic_bin_search(eb, 8065f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 80767d5e289SMarcos Paulo de Souza sizeof(struct btrfs_key_ptr), key, slot); 808be0e5c09SChris Mason } 809be0e5c09SChris Mason 810f0486c68SYan, Zheng static void root_add_used(struct btrfs_root *root, u32 size) 811f0486c68SYan, Zheng { 812f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 813f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 814f0486c68SYan, Zheng btrfs_root_used(&root->root_item) + size); 815f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 816f0486c68SYan, Zheng } 817f0486c68SYan, Zheng 818f0486c68SYan, Zheng static void root_sub_used(struct btrfs_root *root, u32 size) 819f0486c68SYan, Zheng { 820f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 821f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 822f0486c68SYan, Zheng btrfs_root_used(&root->root_item) - size); 823f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 824f0486c68SYan, Zheng } 825f0486c68SYan, Zheng 826d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 827d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 828d352ac68SChris Mason */ 8294b231ae4SDavid Sterba struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent, 8304b231ae4SDavid Sterba int slot) 831bb803951SChris Mason { 832ca7a79adSChris Mason int level = btrfs_header_level(parent); 833416bc658SJosef Bacik struct extent_buffer *eb; 834581c1760SQu Wenruo struct btrfs_key first_key; 835416bc658SJosef Bacik 836fb770ae4SLiu Bo if (slot < 0 || slot >= btrfs_header_nritems(parent)) 837fb770ae4SLiu Bo return ERR_PTR(-ENOENT); 838ca7a79adSChris Mason 839ca7a79adSChris Mason BUG_ON(level == 0); 840ca7a79adSChris Mason 841581c1760SQu Wenruo btrfs_node_key_to_cpu(parent, &first_key, slot); 842d0d20b0fSDavid Sterba eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot), 8431b7ec85eSJosef Bacik btrfs_header_owner(parent), 844581c1760SQu Wenruo btrfs_node_ptr_generation(parent, slot), 845581c1760SQu Wenruo level - 1, &first_key); 846fb770ae4SLiu Bo if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) { 847416bc658SJosef Bacik free_extent_buffer(eb); 848fb770ae4SLiu Bo eb = ERR_PTR(-EIO); 849416bc658SJosef Bacik } 850416bc658SJosef Bacik 851416bc658SJosef Bacik return eb; 852bb803951SChris Mason } 853bb803951SChris Mason 854d352ac68SChris Mason /* 855d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 856d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 857d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 858d352ac68SChris Mason */ 859e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 86098ed5174SChris Mason struct btrfs_root *root, 86198ed5174SChris Mason struct btrfs_path *path, int level) 862bb803951SChris Mason { 8630b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 8645f39d397SChris Mason struct extent_buffer *right = NULL; 8655f39d397SChris Mason struct extent_buffer *mid; 8665f39d397SChris Mason struct extent_buffer *left = NULL; 8675f39d397SChris Mason struct extent_buffer *parent = NULL; 868bb803951SChris Mason int ret = 0; 869bb803951SChris Mason int wret; 870bb803951SChris Mason int pslot; 871bb803951SChris Mason int orig_slot = path->slots[level]; 87279f95c82SChris Mason u64 orig_ptr; 873bb803951SChris Mason 87498e6b1ebSLiu Bo ASSERT(level > 0); 875bb803951SChris Mason 8765f39d397SChris Mason mid = path->nodes[level]; 877b4ce94deSChris Mason 878ac5887c8SJosef Bacik WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK); 8797bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 8807bb86316SChris Mason 8811d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 88279f95c82SChris Mason 883a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 8845f39d397SChris Mason parent = path->nodes[level + 1]; 885bb803951SChris Mason pslot = path->slots[level + 1]; 886a05a9bb1SLi Zefan } 887bb803951SChris Mason 88840689478SChris Mason /* 88940689478SChris Mason * deal with the case where there is only one pointer in the root 89040689478SChris Mason * by promoting the node below to a root 89140689478SChris Mason */ 8925f39d397SChris Mason if (!parent) { 8935f39d397SChris Mason struct extent_buffer *child; 894bb803951SChris Mason 8955f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 896bb803951SChris Mason return 0; 897bb803951SChris Mason 898bb803951SChris Mason /* promote the child to a root */ 8994b231ae4SDavid Sterba child = btrfs_read_node_slot(mid, 0); 900fb770ae4SLiu Bo if (IS_ERR(child)) { 901fb770ae4SLiu Bo ret = PTR_ERR(child); 9020b246afaSJeff Mahoney btrfs_handle_fs_error(fs_info, ret, NULL); 903305a26afSMark Fasheh goto enospc; 904305a26afSMark Fasheh } 905305a26afSMark Fasheh 906925baeddSChris Mason btrfs_tree_lock(child); 9079631e4ccSJosef Bacik ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 9089631e4ccSJosef Bacik BTRFS_NESTING_COW); 909f0486c68SYan, Zheng if (ret) { 910f0486c68SYan, Zheng btrfs_tree_unlock(child); 911f0486c68SYan, Zheng free_extent_buffer(child); 912f0486c68SYan, Zheng goto enospc; 913f0486c68SYan, Zheng } 9142f375ab9SYan 915406808abSFilipe Manana ret = btrfs_tree_mod_log_insert_root(root->node, child, true); 916d9d19a01SDavid Sterba BUG_ON(ret < 0); 917240f62c8SChris Mason rcu_assign_pointer(root->node, child); 918925baeddSChris Mason 9190b86a832SChris Mason add_root_to_dirty_list(root); 920925baeddSChris Mason btrfs_tree_unlock(child); 921b4ce94deSChris Mason 922925baeddSChris Mason path->locks[level] = 0; 923bb803951SChris Mason path->nodes[level] = NULL; 9246a884d7dSDavid Sterba btrfs_clean_tree_block(mid); 925925baeddSChris Mason btrfs_tree_unlock(mid); 926bb803951SChris Mason /* once for the path */ 9275f39d397SChris Mason free_extent_buffer(mid); 928f0486c68SYan, Zheng 929f0486c68SYan, Zheng root_sub_used(root, mid->len); 9307a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1); 931bb803951SChris Mason /* once for the root ptr */ 9323083ee2eSJosef Bacik free_extent_buffer_stale(mid); 933f0486c68SYan, Zheng return 0; 934bb803951SChris Mason } 9355f39d397SChris Mason if (btrfs_header_nritems(mid) > 9360b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4) 937bb803951SChris Mason return 0; 938bb803951SChris Mason 9394b231ae4SDavid Sterba left = btrfs_read_node_slot(parent, pslot - 1); 940fb770ae4SLiu Bo if (IS_ERR(left)) 941fb770ae4SLiu Bo left = NULL; 942fb770ae4SLiu Bo 9435f39d397SChris Mason if (left) { 944bf77467aSJosef Bacik __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 9455f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 9469631e4ccSJosef Bacik parent, pslot - 1, &left, 947bf59a5a2SJosef Bacik BTRFS_NESTING_LEFT_COW); 94854aa1f4dSChris Mason if (wret) { 94954aa1f4dSChris Mason ret = wret; 95054aa1f4dSChris Mason goto enospc; 95154aa1f4dSChris Mason } 9522cc58cf2SChris Mason } 953fb770ae4SLiu Bo 9544b231ae4SDavid Sterba right = btrfs_read_node_slot(parent, pslot + 1); 955fb770ae4SLiu Bo if (IS_ERR(right)) 956fb770ae4SLiu Bo right = NULL; 957fb770ae4SLiu Bo 9585f39d397SChris Mason if (right) { 959bf77467aSJosef Bacik __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 9605f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 9619631e4ccSJosef Bacik parent, pslot + 1, &right, 962bf59a5a2SJosef Bacik BTRFS_NESTING_RIGHT_COW); 9632cc58cf2SChris Mason if (wret) { 9642cc58cf2SChris Mason ret = wret; 9652cc58cf2SChris Mason goto enospc; 9662cc58cf2SChris Mason } 9672cc58cf2SChris Mason } 9682cc58cf2SChris Mason 9692cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 9705f39d397SChris Mason if (left) { 9715f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 972d30a668fSDavid Sterba wret = push_node_left(trans, left, mid, 1); 97379f95c82SChris Mason if (wret < 0) 97479f95c82SChris Mason ret = wret; 975bb803951SChris Mason } 97679f95c82SChris Mason 97779f95c82SChris Mason /* 97879f95c82SChris Mason * then try to empty the right most buffer into the middle 97979f95c82SChris Mason */ 9805f39d397SChris Mason if (right) { 981d30a668fSDavid Sterba wret = push_node_left(trans, mid, right, 1); 98254aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 98379f95c82SChris Mason ret = wret; 9845f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 9856a884d7dSDavid Sterba btrfs_clean_tree_block(right); 986925baeddSChris Mason btrfs_tree_unlock(right); 987afe5fea7STsutomu Itoh del_ptr(root, path, level + 1, pslot + 1); 988f0486c68SYan, Zheng root_sub_used(root, right->len); 9897a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(root), right, 9907a163608SFilipe Manana 0, 1); 9913083ee2eSJosef Bacik free_extent_buffer_stale(right); 992f0486c68SYan, Zheng right = NULL; 993bb803951SChris Mason } else { 9945f39d397SChris Mason struct btrfs_disk_key right_key; 9955f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 996f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1, 997f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 9980e82bcfeSDavid Sterba BUG_ON(ret < 0); 9995f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 10005f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 1001bb803951SChris Mason } 1002bb803951SChris Mason } 10035f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 100479f95c82SChris Mason /* 100579f95c82SChris Mason * we're not allowed to leave a node with one item in the 100679f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 100779f95c82SChris Mason * could try to delete the only pointer in this node. 100879f95c82SChris Mason * So, pull some keys from the left. 100979f95c82SChris Mason * There has to be a left pointer at this point because 101079f95c82SChris Mason * otherwise we would have pulled some pointers from the 101179f95c82SChris Mason * right 101279f95c82SChris Mason */ 1013305a26afSMark Fasheh if (!left) { 1014305a26afSMark Fasheh ret = -EROFS; 10150b246afaSJeff Mahoney btrfs_handle_fs_error(fs_info, ret, NULL); 1016305a26afSMark Fasheh goto enospc; 1017305a26afSMark Fasheh } 101855d32ed8SDavid Sterba wret = balance_node_right(trans, mid, left); 101954aa1f4dSChris Mason if (wret < 0) { 102079f95c82SChris Mason ret = wret; 102154aa1f4dSChris Mason goto enospc; 102254aa1f4dSChris Mason } 1023bce4eae9SChris Mason if (wret == 1) { 1024d30a668fSDavid Sterba wret = push_node_left(trans, left, mid, 1); 1025bce4eae9SChris Mason if (wret < 0) 1026bce4eae9SChris Mason ret = wret; 1027bce4eae9SChris Mason } 102879f95c82SChris Mason BUG_ON(wret == 1); 102979f95c82SChris Mason } 10305f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 10316a884d7dSDavid Sterba btrfs_clean_tree_block(mid); 1032925baeddSChris Mason btrfs_tree_unlock(mid); 1033afe5fea7STsutomu Itoh del_ptr(root, path, level + 1, pslot); 1034f0486c68SYan, Zheng root_sub_used(root, mid->len); 10357a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1); 10363083ee2eSJosef Bacik free_extent_buffer_stale(mid); 1037f0486c68SYan, Zheng mid = NULL; 103879f95c82SChris Mason } else { 103979f95c82SChris Mason /* update the parent key to reflect our changes */ 10405f39d397SChris Mason struct btrfs_disk_key mid_key; 10415f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 1042f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot, 1043f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 10440e82bcfeSDavid Sterba BUG_ON(ret < 0); 10455f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 10465f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 104779f95c82SChris Mason } 1048bb803951SChris Mason 104979f95c82SChris Mason /* update the path */ 10505f39d397SChris Mason if (left) { 10515f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 105267439dadSDavid Sterba atomic_inc(&left->refs); 1053925baeddSChris Mason /* left was locked after cow */ 10545f39d397SChris Mason path->nodes[level] = left; 1055bb803951SChris Mason path->slots[level + 1] -= 1; 1056bb803951SChris Mason path->slots[level] = orig_slot; 1057925baeddSChris Mason if (mid) { 1058925baeddSChris Mason btrfs_tree_unlock(mid); 10595f39d397SChris Mason free_extent_buffer(mid); 1060925baeddSChris Mason } 1061bb803951SChris Mason } else { 10625f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1063bb803951SChris Mason path->slots[level] = orig_slot; 1064bb803951SChris Mason } 1065bb803951SChris Mason } 106679f95c82SChris Mason /* double check we haven't messed things up */ 1067e20d96d6SChris Mason if (orig_ptr != 10685f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 106979f95c82SChris Mason BUG(); 107054aa1f4dSChris Mason enospc: 1071925baeddSChris Mason if (right) { 1072925baeddSChris Mason btrfs_tree_unlock(right); 10735f39d397SChris Mason free_extent_buffer(right); 1074925baeddSChris Mason } 1075925baeddSChris Mason if (left) { 1076925baeddSChris Mason if (path->nodes[level] != left) 1077925baeddSChris Mason btrfs_tree_unlock(left); 10785f39d397SChris Mason free_extent_buffer(left); 1079925baeddSChris Mason } 1080bb803951SChris Mason return ret; 1081bb803951SChris Mason } 1082bb803951SChris Mason 1083d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1084d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1085d352ac68SChris Mason * have to be pessimistic. 1086d352ac68SChris Mason */ 1087d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1088e66f709bSChris Mason struct btrfs_root *root, 1089e66f709bSChris Mason struct btrfs_path *path, int level) 1090e66f709bSChris Mason { 10910b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 10925f39d397SChris Mason struct extent_buffer *right = NULL; 10935f39d397SChris Mason struct extent_buffer *mid; 10945f39d397SChris Mason struct extent_buffer *left = NULL; 10955f39d397SChris Mason struct extent_buffer *parent = NULL; 1096e66f709bSChris Mason int ret = 0; 1097e66f709bSChris Mason int wret; 1098e66f709bSChris Mason int pslot; 1099e66f709bSChris Mason int orig_slot = path->slots[level]; 1100e66f709bSChris Mason 1101e66f709bSChris Mason if (level == 0) 1102e66f709bSChris Mason return 1; 1103e66f709bSChris Mason 11045f39d397SChris Mason mid = path->nodes[level]; 11057bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1106e66f709bSChris Mason 1107a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 11085f39d397SChris Mason parent = path->nodes[level + 1]; 1109e66f709bSChris Mason pslot = path->slots[level + 1]; 1110a05a9bb1SLi Zefan } 1111e66f709bSChris Mason 11125f39d397SChris Mason if (!parent) 1113e66f709bSChris Mason return 1; 1114e66f709bSChris Mason 11154b231ae4SDavid Sterba left = btrfs_read_node_slot(parent, pslot - 1); 1116fb770ae4SLiu Bo if (IS_ERR(left)) 1117fb770ae4SLiu Bo left = NULL; 1118e66f709bSChris Mason 1119e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 11205f39d397SChris Mason if (left) { 1121e66f709bSChris Mason u32 left_nr; 1122925baeddSChris Mason 1123bf77467aSJosef Bacik __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 1124b4ce94deSChris Mason 11255f39d397SChris Mason left_nr = btrfs_header_nritems(left); 11260b246afaSJeff Mahoney if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { 112733ade1f8SChris Mason wret = 1; 112833ade1f8SChris Mason } else { 11295f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 11309631e4ccSJosef Bacik pslot - 1, &left, 1131bf59a5a2SJosef Bacik BTRFS_NESTING_LEFT_COW); 113254aa1f4dSChris Mason if (ret) 113354aa1f4dSChris Mason wret = 1; 113454aa1f4dSChris Mason else { 1135d30a668fSDavid Sterba wret = push_node_left(trans, left, mid, 0); 113654aa1f4dSChris Mason } 113733ade1f8SChris Mason } 1138e66f709bSChris Mason if (wret < 0) 1139e66f709bSChris Mason ret = wret; 1140e66f709bSChris Mason if (wret == 0) { 11415f39d397SChris Mason struct btrfs_disk_key disk_key; 1142e66f709bSChris Mason orig_slot += left_nr; 11435f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 1144f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot, 1145f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 11460e82bcfeSDavid Sterba BUG_ON(ret < 0); 11475f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 11485f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 11495f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 11505f39d397SChris Mason path->nodes[level] = left; 1151e66f709bSChris Mason path->slots[level + 1] -= 1; 1152e66f709bSChris Mason path->slots[level] = orig_slot; 1153925baeddSChris Mason btrfs_tree_unlock(mid); 11545f39d397SChris Mason free_extent_buffer(mid); 1155e66f709bSChris Mason } else { 1156e66f709bSChris Mason orig_slot -= 11575f39d397SChris Mason btrfs_header_nritems(left); 1158e66f709bSChris Mason path->slots[level] = orig_slot; 1159925baeddSChris Mason btrfs_tree_unlock(left); 11605f39d397SChris Mason free_extent_buffer(left); 1161e66f709bSChris Mason } 1162e66f709bSChris Mason return 0; 1163e66f709bSChris Mason } 1164925baeddSChris Mason btrfs_tree_unlock(left); 11655f39d397SChris Mason free_extent_buffer(left); 1166e66f709bSChris Mason } 11674b231ae4SDavid Sterba right = btrfs_read_node_slot(parent, pslot + 1); 1168fb770ae4SLiu Bo if (IS_ERR(right)) 1169fb770ae4SLiu Bo right = NULL; 1170e66f709bSChris Mason 1171e66f709bSChris Mason /* 1172e66f709bSChris Mason * then try to empty the right most buffer into the middle 1173e66f709bSChris Mason */ 11745f39d397SChris Mason if (right) { 117533ade1f8SChris Mason u32 right_nr; 1176b4ce94deSChris Mason 1177bf77467aSJosef Bacik __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 1178b4ce94deSChris Mason 11795f39d397SChris Mason right_nr = btrfs_header_nritems(right); 11800b246afaSJeff Mahoney if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { 118133ade1f8SChris Mason wret = 1; 118233ade1f8SChris Mason } else { 11835f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 11845f39d397SChris Mason parent, pslot + 1, 1185bf59a5a2SJosef Bacik &right, BTRFS_NESTING_RIGHT_COW); 118654aa1f4dSChris Mason if (ret) 118754aa1f4dSChris Mason wret = 1; 118854aa1f4dSChris Mason else { 118955d32ed8SDavid Sterba wret = balance_node_right(trans, right, mid); 119033ade1f8SChris Mason } 119154aa1f4dSChris Mason } 1192e66f709bSChris Mason if (wret < 0) 1193e66f709bSChris Mason ret = wret; 1194e66f709bSChris Mason if (wret == 0) { 11955f39d397SChris Mason struct btrfs_disk_key disk_key; 11965f39d397SChris Mason 11975f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 1198f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1, 1199f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 12000e82bcfeSDavid Sterba BUG_ON(ret < 0); 12015f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 12025f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 12035f39d397SChris Mason 12045f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 12055f39d397SChris Mason path->nodes[level] = right; 1206e66f709bSChris Mason path->slots[level + 1] += 1; 1207e66f709bSChris Mason path->slots[level] = orig_slot - 12085f39d397SChris Mason btrfs_header_nritems(mid); 1209925baeddSChris Mason btrfs_tree_unlock(mid); 12105f39d397SChris Mason free_extent_buffer(mid); 1211e66f709bSChris Mason } else { 1212925baeddSChris Mason btrfs_tree_unlock(right); 12135f39d397SChris Mason free_extent_buffer(right); 1214e66f709bSChris Mason } 1215e66f709bSChris Mason return 0; 1216e66f709bSChris Mason } 1217925baeddSChris Mason btrfs_tree_unlock(right); 12185f39d397SChris Mason free_extent_buffer(right); 1219e66f709bSChris Mason } 1220e66f709bSChris Mason return 1; 1221e66f709bSChris Mason } 1222e66f709bSChris Mason 122374123bd7SChris Mason /* 1224d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1225d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 12263c69faecSChris Mason */ 12272ff7e61eSJeff Mahoney static void reada_for_search(struct btrfs_fs_info *fs_info, 1228e02119d5SChris Mason struct btrfs_path *path, 122901f46658SChris Mason int level, int slot, u64 objectid) 12303c69faecSChris Mason { 12315f39d397SChris Mason struct extent_buffer *node; 123201f46658SChris Mason struct btrfs_disk_key disk_key; 12333c69faecSChris Mason u32 nritems; 12343c69faecSChris Mason u64 search; 1235a7175319SChris Mason u64 target; 12366b80053dSChris Mason u64 nread = 0; 1237ace75066SFilipe Manana u64 nread_max; 12386b80053dSChris Mason u32 nr; 12396b80053dSChris Mason u32 blocksize; 12406b80053dSChris Mason u32 nscan = 0; 1241db94535dSChris Mason 1242ace75066SFilipe Manana if (level != 1 && path->reada != READA_FORWARD_ALWAYS) 12433c69faecSChris Mason return; 12443c69faecSChris Mason 12456702ed49SChris Mason if (!path->nodes[level]) 12466702ed49SChris Mason return; 12476702ed49SChris Mason 12485f39d397SChris Mason node = path->nodes[level]; 1249925baeddSChris Mason 1250ace75066SFilipe Manana /* 1251ace75066SFilipe Manana * Since the time between visiting leaves is much shorter than the time 1252ace75066SFilipe Manana * between visiting nodes, limit read ahead of nodes to 1, to avoid too 1253ace75066SFilipe Manana * much IO at once (possibly random). 1254ace75066SFilipe Manana */ 1255ace75066SFilipe Manana if (path->reada == READA_FORWARD_ALWAYS) { 1256ace75066SFilipe Manana if (level > 1) 1257ace75066SFilipe Manana nread_max = node->fs_info->nodesize; 1258ace75066SFilipe Manana else 1259ace75066SFilipe Manana nread_max = SZ_128K; 1260ace75066SFilipe Manana } else { 1261ace75066SFilipe Manana nread_max = SZ_64K; 1262ace75066SFilipe Manana } 1263ace75066SFilipe Manana 12643c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 12650b246afaSJeff Mahoney blocksize = fs_info->nodesize; 1266069a2e37SFilipe Manana if (path->reada != READA_FORWARD_ALWAYS) { 1267069a2e37SFilipe Manana struct extent_buffer *eb; 1268069a2e37SFilipe Manana 12690b246afaSJeff Mahoney eb = find_extent_buffer(fs_info, search); 12705f39d397SChris Mason if (eb) { 12715f39d397SChris Mason free_extent_buffer(eb); 12723c69faecSChris Mason return; 12733c69faecSChris Mason } 1274069a2e37SFilipe Manana } 12753c69faecSChris Mason 1276a7175319SChris Mason target = search; 12776b80053dSChris Mason 12785f39d397SChris Mason nritems = btrfs_header_nritems(node); 12796b80053dSChris Mason nr = slot; 128025b8b936SJosef Bacik 12813c69faecSChris Mason while (1) { 1282e4058b54SDavid Sterba if (path->reada == READA_BACK) { 12836b80053dSChris Mason if (nr == 0) 12843c69faecSChris Mason break; 12856b80053dSChris Mason nr--; 1286ace75066SFilipe Manana } else if (path->reada == READA_FORWARD || 1287ace75066SFilipe Manana path->reada == READA_FORWARD_ALWAYS) { 12886b80053dSChris Mason nr++; 12896b80053dSChris Mason if (nr >= nritems) 12906b80053dSChris Mason break; 12913c69faecSChris Mason } 1292e4058b54SDavid Sterba if (path->reada == READA_BACK && objectid) { 129301f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 129401f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 129501f46658SChris Mason break; 129601f46658SChris Mason } 12976b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1298ace75066SFilipe Manana if (path->reada == READA_FORWARD_ALWAYS || 1299ace75066SFilipe Manana (search <= target && target - search <= 65536) || 1300a7175319SChris Mason (search > target && search - target <= 65536)) { 1301bfb484d9SJosef Bacik btrfs_readahead_node_child(node, nr); 13026b80053dSChris Mason nread += blocksize; 13033c69faecSChris Mason } 13046b80053dSChris Mason nscan++; 1305ace75066SFilipe Manana if (nread > nread_max || nscan > 32) 13066b80053dSChris Mason break; 13073c69faecSChris Mason } 13083c69faecSChris Mason } 1309925baeddSChris Mason 1310bfb484d9SJosef Bacik static noinline void reada_for_balance(struct btrfs_path *path, int level) 1311b4ce94deSChris Mason { 1312bfb484d9SJosef Bacik struct extent_buffer *parent; 1313b4ce94deSChris Mason int slot; 1314b4ce94deSChris Mason int nritems; 1315b4ce94deSChris Mason 13168c594ea8SChris Mason parent = path->nodes[level + 1]; 1317b4ce94deSChris Mason if (!parent) 13180b08851fSJosef Bacik return; 1319b4ce94deSChris Mason 1320b4ce94deSChris Mason nritems = btrfs_header_nritems(parent); 13218c594ea8SChris Mason slot = path->slots[level + 1]; 1322b4ce94deSChris Mason 1323bfb484d9SJosef Bacik if (slot > 0) 1324bfb484d9SJosef Bacik btrfs_readahead_node_child(parent, slot - 1); 1325bfb484d9SJosef Bacik if (slot + 1 < nritems) 1326bfb484d9SJosef Bacik btrfs_readahead_node_child(parent, slot + 1); 1327b4ce94deSChris Mason } 1328b4ce94deSChris Mason 1329b4ce94deSChris Mason 1330b4ce94deSChris Mason /* 1331d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1332d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1333d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1334d397712bSChris Mason * tree. 1335d352ac68SChris Mason * 1336d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1337d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1338d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1339d352ac68SChris Mason * 1340d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1341d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1342d352ac68SChris Mason */ 1343e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1344f7c79f30SChris Mason int lowest_unlock, int min_write_lock_level, 1345f7c79f30SChris Mason int *write_lock_level) 1346925baeddSChris Mason { 1347925baeddSChris Mason int i; 1348925baeddSChris Mason int skip_level = level; 1349051e1b9fSChris Mason int no_skips = 0; 1350925baeddSChris Mason struct extent_buffer *t; 1351925baeddSChris Mason 1352925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1353925baeddSChris Mason if (!path->nodes[i]) 1354925baeddSChris Mason break; 1355925baeddSChris Mason if (!path->locks[i]) 1356925baeddSChris Mason break; 1357051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1358925baeddSChris Mason skip_level = i + 1; 1359925baeddSChris Mason continue; 1360925baeddSChris Mason } 1361051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1362925baeddSChris Mason u32 nritems; 1363925baeddSChris Mason t = path->nodes[i]; 1364925baeddSChris Mason nritems = btrfs_header_nritems(t); 1365051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1366925baeddSChris Mason skip_level = i + 1; 1367925baeddSChris Mason continue; 1368925baeddSChris Mason } 1369925baeddSChris Mason } 1370051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1371051e1b9fSChris Mason no_skips = 1; 1372051e1b9fSChris Mason 1373925baeddSChris Mason t = path->nodes[i]; 1374d80bb3f9SLiu Bo if (i >= lowest_unlock && i > skip_level) { 1375bd681513SChris Mason btrfs_tree_unlock_rw(t, path->locks[i]); 1376925baeddSChris Mason path->locks[i] = 0; 1377f7c79f30SChris Mason if (write_lock_level && 1378f7c79f30SChris Mason i > min_write_lock_level && 1379f7c79f30SChris Mason i <= *write_lock_level) { 1380f7c79f30SChris Mason *write_lock_level = i - 1; 1381f7c79f30SChris Mason } 1382925baeddSChris Mason } 1383925baeddSChris Mason } 1384925baeddSChris Mason } 1385925baeddSChris Mason 13863c69faecSChris Mason /* 1387c8c42864SChris Mason * helper function for btrfs_search_slot. The goal is to find a block 1388c8c42864SChris Mason * in cache without setting the path to blocking. If we find the block 1389c8c42864SChris Mason * we return zero and the path is unchanged. 1390c8c42864SChris Mason * 1391c8c42864SChris Mason * If we can't find the block, we set the path blocking and do some 1392c8c42864SChris Mason * reada. -EAGAIN is returned and the search must be repeated. 1393c8c42864SChris Mason */ 1394c8c42864SChris Mason static int 1395d07b8528SLiu Bo read_block_for_search(struct btrfs_root *root, struct btrfs_path *p, 1396c8c42864SChris Mason struct extent_buffer **eb_ret, int level, int slot, 1397cda79c54SDavid Sterba const struct btrfs_key *key) 1398c8c42864SChris Mason { 13990b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 1400c8c42864SChris Mason u64 blocknr; 1401c8c42864SChris Mason u64 gen; 1402c8c42864SChris Mason struct extent_buffer *tmp; 1403581c1760SQu Wenruo struct btrfs_key first_key; 140476a05b35SChris Mason int ret; 1405581c1760SQu Wenruo int parent_level; 1406c8c42864SChris Mason 1407213ff4b7SNikolay Borisov blocknr = btrfs_node_blockptr(*eb_ret, slot); 1408213ff4b7SNikolay Borisov gen = btrfs_node_ptr_generation(*eb_ret, slot); 1409213ff4b7SNikolay Borisov parent_level = btrfs_header_level(*eb_ret); 1410213ff4b7SNikolay Borisov btrfs_node_key_to_cpu(*eb_ret, &first_key, slot); 1411c8c42864SChris Mason 14120b246afaSJeff Mahoney tmp = find_extent_buffer(fs_info, blocknr); 1413cb44921aSChris Mason if (tmp) { 1414ace75066SFilipe Manana if (p->reada == READA_FORWARD_ALWAYS) 1415ace75066SFilipe Manana reada_for_search(fs_info, p, level, slot, key->objectid); 1416ace75066SFilipe Manana 1417b9fab919SChris Mason /* first we do an atomic uptodate check */ 1418b9fab919SChris Mason if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) { 1419448de471SQu Wenruo /* 1420448de471SQu Wenruo * Do extra check for first_key, eb can be stale due to 1421448de471SQu Wenruo * being cached, read from scrub, or have multiple 1422448de471SQu Wenruo * parents (shared tree blocks). 1423448de471SQu Wenruo */ 1424e064d5e9SDavid Sterba if (btrfs_verify_level_key(tmp, 1425448de471SQu Wenruo parent_level - 1, &first_key, gen)) { 1426448de471SQu Wenruo free_extent_buffer(tmp); 1427448de471SQu Wenruo return -EUCLEAN; 1428448de471SQu Wenruo } 1429c8c42864SChris Mason *eb_ret = tmp; 1430c8c42864SChris Mason return 0; 1431c8c42864SChris Mason } 1432bdf7c00eSJosef Bacik 1433b9fab919SChris Mason /* now we're allowed to do a blocking uptodate check */ 1434581c1760SQu Wenruo ret = btrfs_read_buffer(tmp, gen, parent_level - 1, &first_key); 1435bdf7c00eSJosef Bacik if (!ret) { 1436cb44921aSChris Mason *eb_ret = tmp; 1437cb44921aSChris Mason return 0; 1438cb44921aSChris Mason } 1439cb44921aSChris Mason free_extent_buffer(tmp); 1440b3b4aa74SDavid Sterba btrfs_release_path(p); 1441cb44921aSChris Mason return -EIO; 1442cb44921aSChris Mason } 1443c8c42864SChris Mason 1444c8c42864SChris Mason /* 1445c8c42864SChris Mason * reduce lock contention at high levels 1446c8c42864SChris Mason * of the btree by dropping locks before 144776a05b35SChris Mason * we read. Don't release the lock on the current 144876a05b35SChris Mason * level because we need to walk this node to figure 144976a05b35SChris Mason * out which blocks to read. 1450c8c42864SChris Mason */ 14518c594ea8SChris Mason btrfs_unlock_up_safe(p, level + 1); 14528c594ea8SChris Mason 1453e4058b54SDavid Sterba if (p->reada != READA_NONE) 14542ff7e61eSJeff Mahoney reada_for_search(fs_info, p, level, slot, key->objectid); 1455c8c42864SChris Mason 145676a05b35SChris Mason ret = -EAGAIN; 14571b7ec85eSJosef Bacik tmp = read_tree_block(fs_info, blocknr, root->root_key.objectid, 14581b7ec85eSJosef Bacik gen, parent_level - 1, &first_key); 145964c043deSLiu Bo if (!IS_ERR(tmp)) { 146076a05b35SChris Mason /* 146176a05b35SChris Mason * If the read above didn't mark this buffer up to date, 146276a05b35SChris Mason * it will never end up being up to date. Set ret to EIO now 146376a05b35SChris Mason * and give up so that our caller doesn't loop forever 146476a05b35SChris Mason * on our EAGAINs. 146576a05b35SChris Mason */ 1466e6a1d6fdSLiu Bo if (!extent_buffer_uptodate(tmp)) 146776a05b35SChris Mason ret = -EIO; 1468c8c42864SChris Mason free_extent_buffer(tmp); 1469c871b0f2SLiu Bo } else { 1470c871b0f2SLiu Bo ret = PTR_ERR(tmp); 147176a05b35SChris Mason } 147202a3307aSLiu Bo 147302a3307aSLiu Bo btrfs_release_path(p); 147476a05b35SChris Mason return ret; 1475c8c42864SChris Mason } 1476c8c42864SChris Mason 1477c8c42864SChris Mason /* 1478c8c42864SChris Mason * helper function for btrfs_search_slot. This does all of the checks 1479c8c42864SChris Mason * for node-level blocks and does any balancing required based on 1480c8c42864SChris Mason * the ins_len. 1481c8c42864SChris Mason * 1482c8c42864SChris Mason * If no extra work was required, zero is returned. If we had to 1483c8c42864SChris Mason * drop the path, -EAGAIN is returned and btrfs_search_slot must 1484c8c42864SChris Mason * start over 1485c8c42864SChris Mason */ 1486c8c42864SChris Mason static int 1487c8c42864SChris Mason setup_nodes_for_search(struct btrfs_trans_handle *trans, 1488c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1489bd681513SChris Mason struct extent_buffer *b, int level, int ins_len, 1490bd681513SChris Mason int *write_lock_level) 1491c8c42864SChris Mason { 14920b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 149395b982deSNikolay Borisov int ret = 0; 14940b246afaSJeff Mahoney 1495c8c42864SChris Mason if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= 14960b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) { 1497c8c42864SChris Mason 1498bd681513SChris Mason if (*write_lock_level < level + 1) { 1499bd681513SChris Mason *write_lock_level = level + 1; 1500bd681513SChris Mason btrfs_release_path(p); 150195b982deSNikolay Borisov return -EAGAIN; 1502bd681513SChris Mason } 1503bd681513SChris Mason 1504bfb484d9SJosef Bacik reada_for_balance(p, level); 150595b982deSNikolay Borisov ret = split_node(trans, root, p, level); 1506c8c42864SChris Mason 1507c8c42864SChris Mason b = p->nodes[level]; 1508c8c42864SChris Mason } else if (ins_len < 0 && btrfs_header_nritems(b) < 15090b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) { 1510c8c42864SChris Mason 1511bd681513SChris Mason if (*write_lock_level < level + 1) { 1512bd681513SChris Mason *write_lock_level = level + 1; 1513bd681513SChris Mason btrfs_release_path(p); 151495b982deSNikolay Borisov return -EAGAIN; 1515bd681513SChris Mason } 1516bd681513SChris Mason 1517bfb484d9SJosef Bacik reada_for_balance(p, level); 151895b982deSNikolay Borisov ret = balance_level(trans, root, p, level); 151995b982deSNikolay Borisov if (ret) 152095b982deSNikolay Borisov return ret; 1521c8c42864SChris Mason 1522c8c42864SChris Mason b = p->nodes[level]; 1523c8c42864SChris Mason if (!b) { 1524b3b4aa74SDavid Sterba btrfs_release_path(p); 152595b982deSNikolay Borisov return -EAGAIN; 1526c8c42864SChris Mason } 1527c8c42864SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 1528c8c42864SChris Mason } 1529c8c42864SChris Mason return ret; 1530c8c42864SChris Mason } 1531c8c42864SChris Mason 1532381cf658SDavid Sterba int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path, 1533e33d5c3dSKelley Nielsen u64 iobjectid, u64 ioff, u8 key_type, 1534e33d5c3dSKelley Nielsen struct btrfs_key *found_key) 1535e33d5c3dSKelley Nielsen { 1536e33d5c3dSKelley Nielsen int ret; 1537e33d5c3dSKelley Nielsen struct btrfs_key key; 1538e33d5c3dSKelley Nielsen struct extent_buffer *eb; 1539381cf658SDavid Sterba 1540381cf658SDavid Sterba ASSERT(path); 15411d4c08e0SDavid Sterba ASSERT(found_key); 1542e33d5c3dSKelley Nielsen 1543e33d5c3dSKelley Nielsen key.type = key_type; 1544e33d5c3dSKelley Nielsen key.objectid = iobjectid; 1545e33d5c3dSKelley Nielsen key.offset = ioff; 1546e33d5c3dSKelley Nielsen 1547e33d5c3dSKelley Nielsen ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); 15481d4c08e0SDavid Sterba if (ret < 0) 1549e33d5c3dSKelley Nielsen return ret; 1550e33d5c3dSKelley Nielsen 1551e33d5c3dSKelley Nielsen eb = path->nodes[0]; 1552e33d5c3dSKelley Nielsen if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { 1553e33d5c3dSKelley Nielsen ret = btrfs_next_leaf(fs_root, path); 1554e33d5c3dSKelley Nielsen if (ret) 1555e33d5c3dSKelley Nielsen return ret; 1556e33d5c3dSKelley Nielsen eb = path->nodes[0]; 1557e33d5c3dSKelley Nielsen } 1558e33d5c3dSKelley Nielsen 1559e33d5c3dSKelley Nielsen btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); 1560e33d5c3dSKelley Nielsen if (found_key->type != key.type || 1561e33d5c3dSKelley Nielsen found_key->objectid != key.objectid) 1562e33d5c3dSKelley Nielsen return 1; 1563e33d5c3dSKelley Nielsen 1564e33d5c3dSKelley Nielsen return 0; 1565e33d5c3dSKelley Nielsen } 1566e33d5c3dSKelley Nielsen 15671fc28d8eSLiu Bo static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root, 15681fc28d8eSLiu Bo struct btrfs_path *p, 15691fc28d8eSLiu Bo int write_lock_level) 15701fc28d8eSLiu Bo { 15711fc28d8eSLiu Bo struct extent_buffer *b; 1572*120de408SJosef Bacik int root_lock = 0; 15731fc28d8eSLiu Bo int level = 0; 15741fc28d8eSLiu Bo 15751fc28d8eSLiu Bo if (p->search_commit_root) { 15761fc28d8eSLiu Bo b = root->commit_root; 157767439dadSDavid Sterba atomic_inc(&b->refs); 15781fc28d8eSLiu Bo level = btrfs_header_level(b); 1579f9ddfd05SLiu Bo /* 1580f9ddfd05SLiu Bo * Ensure that all callers have set skip_locking when 1581f9ddfd05SLiu Bo * p->search_commit_root = 1. 1582f9ddfd05SLiu Bo */ 1583f9ddfd05SLiu Bo ASSERT(p->skip_locking == 1); 15841fc28d8eSLiu Bo 15851fc28d8eSLiu Bo goto out; 15861fc28d8eSLiu Bo } 15871fc28d8eSLiu Bo 15881fc28d8eSLiu Bo if (p->skip_locking) { 15891fc28d8eSLiu Bo b = btrfs_root_node(root); 15901fc28d8eSLiu Bo level = btrfs_header_level(b); 15911fc28d8eSLiu Bo goto out; 15921fc28d8eSLiu Bo } 15931fc28d8eSLiu Bo 1594*120de408SJosef Bacik /* We try very hard to do read locks on the root */ 1595*120de408SJosef Bacik root_lock = BTRFS_READ_LOCK; 1596*120de408SJosef Bacik 15971fc28d8eSLiu Bo /* 1598662c653bSLiu Bo * If the level is set to maximum, we can skip trying to get the read 1599662c653bSLiu Bo * lock. 1600662c653bSLiu Bo */ 1601662c653bSLiu Bo if (write_lock_level < BTRFS_MAX_LEVEL) { 1602662c653bSLiu Bo /* 1603662c653bSLiu Bo * We don't know the level of the root node until we actually 1604662c653bSLiu Bo * have it read locked 16051fc28d8eSLiu Bo */ 16061bb96598SJosef Bacik b = btrfs_read_lock_root_node(root); 16071fc28d8eSLiu Bo level = btrfs_header_level(b); 16081fc28d8eSLiu Bo if (level > write_lock_level) 16091fc28d8eSLiu Bo goto out; 16101fc28d8eSLiu Bo 1611662c653bSLiu Bo /* Whoops, must trade for write lock */ 16121fc28d8eSLiu Bo btrfs_tree_read_unlock(b); 16131fc28d8eSLiu Bo free_extent_buffer(b); 1614662c653bSLiu Bo } 1615662c653bSLiu Bo 16161fc28d8eSLiu Bo b = btrfs_lock_root_node(root); 16171fc28d8eSLiu Bo root_lock = BTRFS_WRITE_LOCK; 16181fc28d8eSLiu Bo 16191fc28d8eSLiu Bo /* The level might have changed, check again */ 16201fc28d8eSLiu Bo level = btrfs_header_level(b); 16211fc28d8eSLiu Bo 16221fc28d8eSLiu Bo out: 1623*120de408SJosef Bacik /* 1624*120de408SJosef Bacik * The root may have failed to write out at some point, and thus is no 1625*120de408SJosef Bacik * longer valid, return an error in this case. 1626*120de408SJosef Bacik */ 1627*120de408SJosef Bacik if (!extent_buffer_uptodate(b)) { 1628*120de408SJosef Bacik if (root_lock) 1629*120de408SJosef Bacik btrfs_tree_unlock_rw(b, root_lock); 1630*120de408SJosef Bacik free_extent_buffer(b); 1631*120de408SJosef Bacik return ERR_PTR(-EIO); 1632*120de408SJosef Bacik } 1633*120de408SJosef Bacik 16341fc28d8eSLiu Bo p->nodes[level] = b; 16351fc28d8eSLiu Bo if (!p->skip_locking) 16361fc28d8eSLiu Bo p->locks[level] = root_lock; 16371fc28d8eSLiu Bo /* 16381fc28d8eSLiu Bo * Callers are responsible for dropping b's references. 16391fc28d8eSLiu Bo */ 16401fc28d8eSLiu Bo return b; 16411fc28d8eSLiu Bo } 16421fc28d8eSLiu Bo 1643d96b3424SFilipe Manana /* 1644d96b3424SFilipe Manana * Replace the extent buffer at the lowest level of the path with a cloned 1645d96b3424SFilipe Manana * version. The purpose is to be able to use it safely, after releasing the 1646d96b3424SFilipe Manana * commit root semaphore, even if relocation is happening in parallel, the 1647d96b3424SFilipe Manana * transaction used for relocation is committed and the extent buffer is 1648d96b3424SFilipe Manana * reallocated in the next transaction. 1649d96b3424SFilipe Manana * 1650d96b3424SFilipe Manana * This is used in a context where the caller does not prevent transaction 1651d96b3424SFilipe Manana * commits from happening, either by holding a transaction handle or holding 1652d96b3424SFilipe Manana * some lock, while it's doing searches through a commit root. 1653d96b3424SFilipe Manana * At the moment it's only used for send operations. 1654d96b3424SFilipe Manana */ 1655d96b3424SFilipe Manana static int finish_need_commit_sem_search(struct btrfs_path *path) 1656d96b3424SFilipe Manana { 1657d96b3424SFilipe Manana const int i = path->lowest_level; 1658d96b3424SFilipe Manana const int slot = path->slots[i]; 1659d96b3424SFilipe Manana struct extent_buffer *lowest = path->nodes[i]; 1660d96b3424SFilipe Manana struct extent_buffer *clone; 1661d96b3424SFilipe Manana 1662d96b3424SFilipe Manana ASSERT(path->need_commit_sem); 1663d96b3424SFilipe Manana 1664d96b3424SFilipe Manana if (!lowest) 1665d96b3424SFilipe Manana return 0; 1666d96b3424SFilipe Manana 1667d96b3424SFilipe Manana lockdep_assert_held_read(&lowest->fs_info->commit_root_sem); 1668d96b3424SFilipe Manana 1669d96b3424SFilipe Manana clone = btrfs_clone_extent_buffer(lowest); 1670d96b3424SFilipe Manana if (!clone) 1671d96b3424SFilipe Manana return -ENOMEM; 1672d96b3424SFilipe Manana 1673d96b3424SFilipe Manana btrfs_release_path(path); 1674d96b3424SFilipe Manana path->nodes[i] = clone; 1675d96b3424SFilipe Manana path->slots[i] = slot; 1676d96b3424SFilipe Manana 1677d96b3424SFilipe Manana return 0; 1678d96b3424SFilipe Manana } 16791fc28d8eSLiu Bo 1680c8c42864SChris Mason /* 16814271eceaSNikolay Borisov * btrfs_search_slot - look for a key in a tree and perform necessary 16824271eceaSNikolay Borisov * modifications to preserve tree invariants. 168374123bd7SChris Mason * 16844271eceaSNikolay Borisov * @trans: Handle of transaction, used when modifying the tree 16854271eceaSNikolay Borisov * @p: Holds all btree nodes along the search path 16864271eceaSNikolay Borisov * @root: The root node of the tree 16874271eceaSNikolay Borisov * @key: The key we are looking for 16889a664971Sethanwu * @ins_len: Indicates purpose of search: 16899a664971Sethanwu * >0 for inserts it's size of item inserted (*) 16909a664971Sethanwu * <0 for deletions 16919a664971Sethanwu * 0 for plain searches, not modifying the tree 16929a664971Sethanwu * 16939a664971Sethanwu * (*) If size of item inserted doesn't include 16949a664971Sethanwu * sizeof(struct btrfs_item), then p->search_for_extension must 16959a664971Sethanwu * be set. 16964271eceaSNikolay Borisov * @cow: boolean should CoW operations be performed. Must always be 1 16974271eceaSNikolay Borisov * when modifying the tree. 169897571fd0SChris Mason * 16994271eceaSNikolay Borisov * If @ins_len > 0, nodes and leaves will be split as we walk down the tree. 17004271eceaSNikolay Borisov * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible) 17014271eceaSNikolay Borisov * 17024271eceaSNikolay Borisov * If @key is found, 0 is returned and you can find the item in the leaf level 17034271eceaSNikolay Borisov * of the path (level 0) 17044271eceaSNikolay Borisov * 17054271eceaSNikolay Borisov * If @key isn't found, 1 is returned and the leaf level of the path (level 0) 17064271eceaSNikolay Borisov * points to the slot where it should be inserted 17074271eceaSNikolay Borisov * 17084271eceaSNikolay Borisov * If an error is encountered while searching the tree a negative error number 17094271eceaSNikolay Borisov * is returned 171074123bd7SChris Mason */ 1711310712b2SOmar Sandoval int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1712310712b2SOmar Sandoval const struct btrfs_key *key, struct btrfs_path *p, 1713310712b2SOmar Sandoval int ins_len, int cow) 1714be0e5c09SChris Mason { 1715d96b3424SFilipe Manana struct btrfs_fs_info *fs_info = root->fs_info; 17165f39d397SChris Mason struct extent_buffer *b; 1717be0e5c09SChris Mason int slot; 1718be0e5c09SChris Mason int ret; 171933c66f43SYan Zheng int err; 1720be0e5c09SChris Mason int level; 1721925baeddSChris Mason int lowest_unlock = 1; 1722bd681513SChris Mason /* everything at write_lock_level or lower must be write locked */ 1723bd681513SChris Mason int write_lock_level = 0; 17249f3a7427SChris Mason u8 lowest_level = 0; 1725f7c79f30SChris Mason int min_write_lock_level; 1726d7396f07SFilipe David Borba Manana int prev_cmp; 17279f3a7427SChris Mason 17286702ed49SChris Mason lowest_level = p->lowest_level; 1729323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 173022b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 1731eb653de1SFilipe David Borba Manana BUG_ON(!cow && ins_len); 173225179201SJosef Bacik 1733bd681513SChris Mason if (ins_len < 0) { 1734925baeddSChris Mason lowest_unlock = 2; 173565b51a00SChris Mason 1736bd681513SChris Mason /* when we are removing items, we might have to go up to level 1737bd681513SChris Mason * two as we update tree pointers Make sure we keep write 1738bd681513SChris Mason * for those levels as well 1739bd681513SChris Mason */ 1740bd681513SChris Mason write_lock_level = 2; 1741bd681513SChris Mason } else if (ins_len > 0) { 1742bd681513SChris Mason /* 1743bd681513SChris Mason * for inserting items, make sure we have a write lock on 1744bd681513SChris Mason * level 1 so we can update keys 1745bd681513SChris Mason */ 1746bd681513SChris Mason write_lock_level = 1; 1747bd681513SChris Mason } 1748bd681513SChris Mason 1749bd681513SChris Mason if (!cow) 1750bd681513SChris Mason write_lock_level = -1; 1751bd681513SChris Mason 175209a2a8f9SJosef Bacik if (cow && (p->keep_locks || p->lowest_level)) 1753bd681513SChris Mason write_lock_level = BTRFS_MAX_LEVEL; 1754bd681513SChris Mason 1755f7c79f30SChris Mason min_write_lock_level = write_lock_level; 1756f7c79f30SChris Mason 1757d96b3424SFilipe Manana if (p->need_commit_sem) { 1758d96b3424SFilipe Manana ASSERT(p->search_commit_root); 1759d96b3424SFilipe Manana down_read(&fs_info->commit_root_sem); 1760d96b3424SFilipe Manana } 1761d96b3424SFilipe Manana 1762bb803951SChris Mason again: 1763d7396f07SFilipe David Borba Manana prev_cmp = -1; 17641fc28d8eSLiu Bo b = btrfs_search_slot_get_root(root, p, write_lock_level); 1765be6821f8SFilipe Manana if (IS_ERR(b)) { 1766be6821f8SFilipe Manana ret = PTR_ERR(b); 1767be6821f8SFilipe Manana goto done; 1768be6821f8SFilipe Manana } 1769925baeddSChris Mason 1770eb60ceacSChris Mason while (b) { 1771f624d976SQu Wenruo int dec = 0; 1772f624d976SQu Wenruo 17735f39d397SChris Mason level = btrfs_header_level(b); 177465b51a00SChris Mason 177502217ed2SChris Mason if (cow) { 17769ea2c7c9SNikolay Borisov bool last_level = (level == (BTRFS_MAX_LEVEL - 1)); 17779ea2c7c9SNikolay Borisov 1778c8c42864SChris Mason /* 1779c8c42864SChris Mason * if we don't really need to cow this block 1780c8c42864SChris Mason * then we don't want to set the path blocking, 1781c8c42864SChris Mason * so we test it here 1782c8c42864SChris Mason */ 17835963ffcaSJosef Bacik if (!should_cow_block(trans, root, b)) 178465b51a00SChris Mason goto cow_done; 17855d4f98a2SYan Zheng 1786bd681513SChris Mason /* 1787bd681513SChris Mason * must have write locks on this node and the 1788bd681513SChris Mason * parent 1789bd681513SChris Mason */ 17905124e00eSJosef Bacik if (level > write_lock_level || 17915124e00eSJosef Bacik (level + 1 > write_lock_level && 17925124e00eSJosef Bacik level + 1 < BTRFS_MAX_LEVEL && 17935124e00eSJosef Bacik p->nodes[level + 1])) { 1794bd681513SChris Mason write_lock_level = level + 1; 1795bd681513SChris Mason btrfs_release_path(p); 1796bd681513SChris Mason goto again; 1797bd681513SChris Mason } 1798bd681513SChris Mason 17999ea2c7c9SNikolay Borisov if (last_level) 18009ea2c7c9SNikolay Borisov err = btrfs_cow_block(trans, root, b, NULL, 0, 18019631e4ccSJosef Bacik &b, 18029631e4ccSJosef Bacik BTRFS_NESTING_COW); 18039ea2c7c9SNikolay Borisov else 180433c66f43SYan Zheng err = btrfs_cow_block(trans, root, b, 1805e20d96d6SChris Mason p->nodes[level + 1], 18069631e4ccSJosef Bacik p->slots[level + 1], &b, 18079631e4ccSJosef Bacik BTRFS_NESTING_COW); 180833c66f43SYan Zheng if (err) { 180933c66f43SYan Zheng ret = err; 181065b51a00SChris Mason goto done; 181154aa1f4dSChris Mason } 181202217ed2SChris Mason } 181365b51a00SChris Mason cow_done: 1814eb60ceacSChris Mason p->nodes[level] = b; 181552398340SLiu Bo /* 181652398340SLiu Bo * Leave path with blocking locks to avoid massive 181752398340SLiu Bo * lock context switch, this is made on purpose. 181852398340SLiu Bo */ 1819b4ce94deSChris Mason 1820b4ce94deSChris Mason /* 1821b4ce94deSChris Mason * we have a lock on b and as long as we aren't changing 1822b4ce94deSChris Mason * the tree, there is no way to for the items in b to change. 1823b4ce94deSChris Mason * It is safe to drop the lock on our parent before we 1824b4ce94deSChris Mason * go through the expensive btree search on b. 1825b4ce94deSChris Mason * 1826eb653de1SFilipe David Borba Manana * If we're inserting or deleting (ins_len != 0), then we might 1827eb653de1SFilipe David Borba Manana * be changing slot zero, which may require changing the parent. 1828eb653de1SFilipe David Borba Manana * So, we can't drop the lock until after we know which slot 1829eb653de1SFilipe David Borba Manana * we're operating on. 1830b4ce94deSChris Mason */ 1831eb653de1SFilipe David Borba Manana if (!ins_len && !p->keep_locks) { 1832eb653de1SFilipe David Borba Manana int u = level + 1; 1833eb653de1SFilipe David Borba Manana 1834eb653de1SFilipe David Borba Manana if (u < BTRFS_MAX_LEVEL && p->locks[u]) { 1835eb653de1SFilipe David Borba Manana btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]); 1836eb653de1SFilipe David Borba Manana p->locks[u] = 0; 1837eb653de1SFilipe David Borba Manana } 1838eb653de1SFilipe David Borba Manana } 1839b4ce94deSChris Mason 1840995e9a16SNikolay Borisov /* 1841995e9a16SNikolay Borisov * If btrfs_bin_search returns an exact match (prev_cmp == 0) 1842995e9a16SNikolay Borisov * we can safely assume the target key will always be in slot 0 1843995e9a16SNikolay Borisov * on lower levels due to the invariants BTRFS' btree provides, 1844995e9a16SNikolay Borisov * namely that a btrfs_key_ptr entry always points to the 1845995e9a16SNikolay Borisov * lowest key in the child node, thus we can skip searching 1846995e9a16SNikolay Borisov * lower levels 1847995e9a16SNikolay Borisov */ 1848995e9a16SNikolay Borisov if (prev_cmp == 0) { 1849995e9a16SNikolay Borisov slot = 0; 1850995e9a16SNikolay Borisov ret = 0; 1851995e9a16SNikolay Borisov } else { 1852995e9a16SNikolay Borisov ret = btrfs_bin_search(b, key, &slot); 1853995e9a16SNikolay Borisov prev_cmp = ret; 1854415b35a5SLiu Bo if (ret < 0) 1855415b35a5SLiu Bo goto done; 1856995e9a16SNikolay Borisov } 1857b4ce94deSChris Mason 1858f624d976SQu Wenruo if (level == 0) { 1859be0e5c09SChris Mason p->slots[level] = slot; 18609a664971Sethanwu /* 18619a664971Sethanwu * Item key already exists. In this case, if we are 18629a664971Sethanwu * allowed to insert the item (for example, in dir_item 18639a664971Sethanwu * case, item key collision is allowed), it will be 18649a664971Sethanwu * merged with the original item. Only the item size 18659a664971Sethanwu * grows, no new btrfs item will be added. If 18669a664971Sethanwu * search_for_extension is not set, ins_len already 18679a664971Sethanwu * accounts the size btrfs_item, deduct it here so leaf 18689a664971Sethanwu * space check will be correct. 18699a664971Sethanwu */ 18709a664971Sethanwu if (ret == 0 && ins_len > 0 && !p->search_for_extension) { 18719a664971Sethanwu ASSERT(ins_len >= sizeof(struct btrfs_item)); 18729a664971Sethanwu ins_len -= sizeof(struct btrfs_item); 18739a664971Sethanwu } 187487b29b20SYan Zheng if (ins_len > 0 && 1875e902baacSDavid Sterba btrfs_leaf_free_space(b) < ins_len) { 1876bd681513SChris Mason if (write_lock_level < 1) { 1877bd681513SChris Mason write_lock_level = 1; 1878bd681513SChris Mason btrfs_release_path(p); 1879bd681513SChris Mason goto again; 1880bd681513SChris Mason } 1881bd681513SChris Mason 188233c66f43SYan Zheng err = split_leaf(trans, root, key, 1883cc0c5538SChris Mason p, ins_len, ret == 0); 1884b4ce94deSChris Mason 188533c66f43SYan Zheng BUG_ON(err > 0); 188633c66f43SYan Zheng if (err) { 188733c66f43SYan Zheng ret = err; 188865b51a00SChris Mason goto done; 188965b51a00SChris Mason } 18905c680ed6SChris Mason } 1891459931ecSChris Mason if (!p->search_for_split) 1892f7c79f30SChris Mason unlock_up(p, level, lowest_unlock, 18934b6f8e96SLiu Bo min_write_lock_level, NULL); 189465b51a00SChris Mason goto done; 189565b51a00SChris Mason } 1896f624d976SQu Wenruo if (ret && slot > 0) { 1897f624d976SQu Wenruo dec = 1; 1898f624d976SQu Wenruo slot--; 1899f624d976SQu Wenruo } 1900f624d976SQu Wenruo p->slots[level] = slot; 1901f624d976SQu Wenruo err = setup_nodes_for_search(trans, root, p, b, level, ins_len, 1902f624d976SQu Wenruo &write_lock_level); 1903f624d976SQu Wenruo if (err == -EAGAIN) 1904f624d976SQu Wenruo goto again; 1905f624d976SQu Wenruo if (err) { 1906f624d976SQu Wenruo ret = err; 1907f624d976SQu Wenruo goto done; 1908f624d976SQu Wenruo } 1909f624d976SQu Wenruo b = p->nodes[level]; 1910f624d976SQu Wenruo slot = p->slots[level]; 1911f624d976SQu Wenruo 1912f624d976SQu Wenruo /* 1913f624d976SQu Wenruo * Slot 0 is special, if we change the key we have to update 1914f624d976SQu Wenruo * the parent pointer which means we must have a write lock on 1915f624d976SQu Wenruo * the parent 1916f624d976SQu Wenruo */ 1917f624d976SQu Wenruo if (slot == 0 && ins_len && write_lock_level < level + 1) { 1918f624d976SQu Wenruo write_lock_level = level + 1; 1919f624d976SQu Wenruo btrfs_release_path(p); 1920f624d976SQu Wenruo goto again; 1921f624d976SQu Wenruo } 1922f624d976SQu Wenruo 1923f624d976SQu Wenruo unlock_up(p, level, lowest_unlock, min_write_lock_level, 1924f624d976SQu Wenruo &write_lock_level); 1925f624d976SQu Wenruo 1926f624d976SQu Wenruo if (level == lowest_level) { 1927f624d976SQu Wenruo if (dec) 1928f624d976SQu Wenruo p->slots[level]++; 1929f624d976SQu Wenruo goto done; 1930f624d976SQu Wenruo } 1931f624d976SQu Wenruo 1932f624d976SQu Wenruo err = read_block_for_search(root, p, &b, level, slot, key); 1933f624d976SQu Wenruo if (err == -EAGAIN) 1934f624d976SQu Wenruo goto again; 1935f624d976SQu Wenruo if (err) { 1936f624d976SQu Wenruo ret = err; 1937f624d976SQu Wenruo goto done; 1938f624d976SQu Wenruo } 1939f624d976SQu Wenruo 1940f624d976SQu Wenruo if (!p->skip_locking) { 1941f624d976SQu Wenruo level = btrfs_header_level(b); 1942f624d976SQu Wenruo if (level <= write_lock_level) { 1943f624d976SQu Wenruo btrfs_tree_lock(b); 1944f624d976SQu Wenruo p->locks[level] = BTRFS_WRITE_LOCK; 1945f624d976SQu Wenruo } else { 1946fe596ca3SJosef Bacik btrfs_tree_read_lock(b); 1947f624d976SQu Wenruo p->locks[level] = BTRFS_READ_LOCK; 1948f624d976SQu Wenruo } 1949f624d976SQu Wenruo p->nodes[level] = b; 1950f624d976SQu Wenruo } 195165b51a00SChris Mason } 195265b51a00SChris Mason ret = 1; 195365b51a00SChris Mason done: 19545f5bc6b1SFilipe Manana if (ret < 0 && !p->skip_release_on_error) 1955b3b4aa74SDavid Sterba btrfs_release_path(p); 1956d96b3424SFilipe Manana 1957d96b3424SFilipe Manana if (p->need_commit_sem) { 1958d96b3424SFilipe Manana int ret2; 1959d96b3424SFilipe Manana 1960d96b3424SFilipe Manana ret2 = finish_need_commit_sem_search(p); 1961d96b3424SFilipe Manana up_read(&fs_info->commit_root_sem); 1962d96b3424SFilipe Manana if (ret2) 1963d96b3424SFilipe Manana ret = ret2; 1964d96b3424SFilipe Manana } 1965d96b3424SFilipe Manana 1966be0e5c09SChris Mason return ret; 1967be0e5c09SChris Mason } 1968f75e2b79SJosef Bacik ALLOW_ERROR_INJECTION(btrfs_search_slot, ERRNO); 1969be0e5c09SChris Mason 197074123bd7SChris Mason /* 19715d9e75c4SJan Schmidt * Like btrfs_search_slot, this looks for a key in the given tree. It uses the 19725d9e75c4SJan Schmidt * current state of the tree together with the operations recorded in the tree 19735d9e75c4SJan Schmidt * modification log to search for the key in a previous version of this tree, as 19745d9e75c4SJan Schmidt * denoted by the time_seq parameter. 19755d9e75c4SJan Schmidt * 19765d9e75c4SJan Schmidt * Naturally, there is no support for insert, delete or cow operations. 19775d9e75c4SJan Schmidt * 19785d9e75c4SJan Schmidt * The resulting path and return value will be set up as if we called 19795d9e75c4SJan Schmidt * btrfs_search_slot at that point in time with ins_len and cow both set to 0. 19805d9e75c4SJan Schmidt */ 1981310712b2SOmar Sandoval int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key, 19825d9e75c4SJan Schmidt struct btrfs_path *p, u64 time_seq) 19835d9e75c4SJan Schmidt { 19840b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 19855d9e75c4SJan Schmidt struct extent_buffer *b; 19865d9e75c4SJan Schmidt int slot; 19875d9e75c4SJan Schmidt int ret; 19885d9e75c4SJan Schmidt int err; 19895d9e75c4SJan Schmidt int level; 19905d9e75c4SJan Schmidt int lowest_unlock = 1; 19915d9e75c4SJan Schmidt u8 lowest_level = 0; 19925d9e75c4SJan Schmidt 19935d9e75c4SJan Schmidt lowest_level = p->lowest_level; 19945d9e75c4SJan Schmidt WARN_ON(p->nodes[0] != NULL); 19955d9e75c4SJan Schmidt 19965d9e75c4SJan Schmidt if (p->search_commit_root) { 19975d9e75c4SJan Schmidt BUG_ON(time_seq); 19985d9e75c4SJan Schmidt return btrfs_search_slot(NULL, root, key, p, 0, 0); 19995d9e75c4SJan Schmidt } 20005d9e75c4SJan Schmidt 20015d9e75c4SJan Schmidt again: 2002f3a84ccdSFilipe Manana b = btrfs_get_old_root(root, time_seq); 2003315bed43SNikolay Borisov if (!b) { 2004315bed43SNikolay Borisov ret = -EIO; 2005315bed43SNikolay Borisov goto done; 2006315bed43SNikolay Borisov } 20075d9e75c4SJan Schmidt level = btrfs_header_level(b); 20085d9e75c4SJan Schmidt p->locks[level] = BTRFS_READ_LOCK; 20095d9e75c4SJan Schmidt 20105d9e75c4SJan Schmidt while (b) { 2011abe9339dSQu Wenruo int dec = 0; 2012abe9339dSQu Wenruo 20135d9e75c4SJan Schmidt level = btrfs_header_level(b); 20145d9e75c4SJan Schmidt p->nodes[level] = b; 20155d9e75c4SJan Schmidt 20165d9e75c4SJan Schmidt /* 20175d9e75c4SJan Schmidt * we have a lock on b and as long as we aren't changing 20185d9e75c4SJan Schmidt * the tree, there is no way to for the items in b to change. 20195d9e75c4SJan Schmidt * It is safe to drop the lock on our parent before we 20205d9e75c4SJan Schmidt * go through the expensive btree search on b. 20215d9e75c4SJan Schmidt */ 20225d9e75c4SJan Schmidt btrfs_unlock_up_safe(p, level + 1); 20235d9e75c4SJan Schmidt 2024995e9a16SNikolay Borisov ret = btrfs_bin_search(b, key, &slot); 2025cbca7d59SFilipe Manana if (ret < 0) 2026cbca7d59SFilipe Manana goto done; 20275d9e75c4SJan Schmidt 2028abe9339dSQu Wenruo if (level == 0) { 2029abe9339dSQu Wenruo p->slots[level] = slot; 2030abe9339dSQu Wenruo unlock_up(p, level, lowest_unlock, 0, NULL); 2031abe9339dSQu Wenruo goto done; 2032abe9339dSQu Wenruo } 2033abe9339dSQu Wenruo 20345d9e75c4SJan Schmidt if (ret && slot > 0) { 20355d9e75c4SJan Schmidt dec = 1; 2036abe9339dSQu Wenruo slot--; 20375d9e75c4SJan Schmidt } 20385d9e75c4SJan Schmidt p->slots[level] = slot; 20395d9e75c4SJan Schmidt unlock_up(p, level, lowest_unlock, 0, NULL); 20405d9e75c4SJan Schmidt 20415d9e75c4SJan Schmidt if (level == lowest_level) { 20425d9e75c4SJan Schmidt if (dec) 20435d9e75c4SJan Schmidt p->slots[level]++; 20445d9e75c4SJan Schmidt goto done; 20455d9e75c4SJan Schmidt } 20465d9e75c4SJan Schmidt 2047abe9339dSQu Wenruo err = read_block_for_search(root, p, &b, level, slot, key); 20485d9e75c4SJan Schmidt if (err == -EAGAIN) 20495d9e75c4SJan Schmidt goto again; 20505d9e75c4SJan Schmidt if (err) { 20515d9e75c4SJan Schmidt ret = err; 20525d9e75c4SJan Schmidt goto done; 20535d9e75c4SJan Schmidt } 20545d9e75c4SJan Schmidt 20555d9e75c4SJan Schmidt level = btrfs_header_level(b); 20565d9e75c4SJan Schmidt btrfs_tree_read_lock(b); 2057f3a84ccdSFilipe Manana b = btrfs_tree_mod_log_rewind(fs_info, p, b, time_seq); 2058db7f3436SJosef Bacik if (!b) { 2059db7f3436SJosef Bacik ret = -ENOMEM; 2060db7f3436SJosef Bacik goto done; 2061db7f3436SJosef Bacik } 20625d9e75c4SJan Schmidt p->locks[level] = BTRFS_READ_LOCK; 20635d9e75c4SJan Schmidt p->nodes[level] = b; 20645d9e75c4SJan Schmidt } 20655d9e75c4SJan Schmidt ret = 1; 20665d9e75c4SJan Schmidt done: 20675d9e75c4SJan Schmidt if (ret < 0) 20685d9e75c4SJan Schmidt btrfs_release_path(p); 20695d9e75c4SJan Schmidt 20705d9e75c4SJan Schmidt return ret; 20715d9e75c4SJan Schmidt } 20725d9e75c4SJan Schmidt 20735d9e75c4SJan Schmidt /* 20742f38b3e1SArne Jansen * helper to use instead of search slot if no exact match is needed but 20752f38b3e1SArne Jansen * instead the next or previous item should be returned. 20762f38b3e1SArne Jansen * When find_higher is true, the next higher item is returned, the next lower 20772f38b3e1SArne Jansen * otherwise. 20782f38b3e1SArne Jansen * When return_any and find_higher are both true, and no higher item is found, 20792f38b3e1SArne Jansen * return the next lower instead. 20802f38b3e1SArne Jansen * When return_any is true and find_higher is false, and no lower item is found, 20812f38b3e1SArne Jansen * return the next higher instead. 20822f38b3e1SArne Jansen * It returns 0 if any item is found, 1 if none is found (tree empty), and 20832f38b3e1SArne Jansen * < 0 on error 20842f38b3e1SArne Jansen */ 20852f38b3e1SArne Jansen int btrfs_search_slot_for_read(struct btrfs_root *root, 2086310712b2SOmar Sandoval const struct btrfs_key *key, 2087310712b2SOmar Sandoval struct btrfs_path *p, int find_higher, 2088310712b2SOmar Sandoval int return_any) 20892f38b3e1SArne Jansen { 20902f38b3e1SArne Jansen int ret; 20912f38b3e1SArne Jansen struct extent_buffer *leaf; 20922f38b3e1SArne Jansen 20932f38b3e1SArne Jansen again: 20942f38b3e1SArne Jansen ret = btrfs_search_slot(NULL, root, key, p, 0, 0); 20952f38b3e1SArne Jansen if (ret <= 0) 20962f38b3e1SArne Jansen return ret; 20972f38b3e1SArne Jansen /* 20982f38b3e1SArne Jansen * a return value of 1 means the path is at the position where the 20992f38b3e1SArne Jansen * item should be inserted. Normally this is the next bigger item, 21002f38b3e1SArne Jansen * but in case the previous item is the last in a leaf, path points 21012f38b3e1SArne Jansen * to the first free slot in the previous leaf, i.e. at an invalid 21022f38b3e1SArne Jansen * item. 21032f38b3e1SArne Jansen */ 21042f38b3e1SArne Jansen leaf = p->nodes[0]; 21052f38b3e1SArne Jansen 21062f38b3e1SArne Jansen if (find_higher) { 21072f38b3e1SArne Jansen if (p->slots[0] >= btrfs_header_nritems(leaf)) { 21082f38b3e1SArne Jansen ret = btrfs_next_leaf(root, p); 21092f38b3e1SArne Jansen if (ret <= 0) 21102f38b3e1SArne Jansen return ret; 21112f38b3e1SArne Jansen if (!return_any) 21122f38b3e1SArne Jansen return 1; 21132f38b3e1SArne Jansen /* 21142f38b3e1SArne Jansen * no higher item found, return the next 21152f38b3e1SArne Jansen * lower instead 21162f38b3e1SArne Jansen */ 21172f38b3e1SArne Jansen return_any = 0; 21182f38b3e1SArne Jansen find_higher = 0; 21192f38b3e1SArne Jansen btrfs_release_path(p); 21202f38b3e1SArne Jansen goto again; 21212f38b3e1SArne Jansen } 21222f38b3e1SArne Jansen } else { 21232f38b3e1SArne Jansen if (p->slots[0] == 0) { 21242f38b3e1SArne Jansen ret = btrfs_prev_leaf(root, p); 2125e6793769SArne Jansen if (ret < 0) 21262f38b3e1SArne Jansen return ret; 2127e6793769SArne Jansen if (!ret) { 212823c6bf6aSFilipe David Borba Manana leaf = p->nodes[0]; 212923c6bf6aSFilipe David Borba Manana if (p->slots[0] == btrfs_header_nritems(leaf)) 213023c6bf6aSFilipe David Borba Manana p->slots[0]--; 2131e6793769SArne Jansen return 0; 2132e6793769SArne Jansen } 21332f38b3e1SArne Jansen if (!return_any) 21342f38b3e1SArne Jansen return 1; 21352f38b3e1SArne Jansen /* 21362f38b3e1SArne Jansen * no lower item found, return the next 21372f38b3e1SArne Jansen * higher instead 21382f38b3e1SArne Jansen */ 21392f38b3e1SArne Jansen return_any = 0; 21402f38b3e1SArne Jansen find_higher = 1; 21412f38b3e1SArne Jansen btrfs_release_path(p); 21422f38b3e1SArne Jansen goto again; 2143e6793769SArne Jansen } else { 21442f38b3e1SArne Jansen --p->slots[0]; 21452f38b3e1SArne Jansen } 21462f38b3e1SArne Jansen } 21472f38b3e1SArne Jansen return 0; 21482f38b3e1SArne Jansen } 21492f38b3e1SArne Jansen 21502f38b3e1SArne Jansen /* 21510ff40a91SMarcos Paulo de Souza * Execute search and call btrfs_previous_item to traverse backwards if the item 21520ff40a91SMarcos Paulo de Souza * was not found. 21530ff40a91SMarcos Paulo de Souza * 21540ff40a91SMarcos Paulo de Souza * Return 0 if found, 1 if not found and < 0 if error. 21550ff40a91SMarcos Paulo de Souza */ 21560ff40a91SMarcos Paulo de Souza int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key, 21570ff40a91SMarcos Paulo de Souza struct btrfs_path *path) 21580ff40a91SMarcos Paulo de Souza { 21590ff40a91SMarcos Paulo de Souza int ret; 21600ff40a91SMarcos Paulo de Souza 21610ff40a91SMarcos Paulo de Souza ret = btrfs_search_slot(NULL, root, key, path, 0, 0); 21620ff40a91SMarcos Paulo de Souza if (ret > 0) 21630ff40a91SMarcos Paulo de Souza ret = btrfs_previous_item(root, path, key->objectid, key->type); 21640ff40a91SMarcos Paulo de Souza 21650ff40a91SMarcos Paulo de Souza if (ret == 0) 21660ff40a91SMarcos Paulo de Souza btrfs_item_key_to_cpu(path->nodes[0], key, path->slots[0]); 21670ff40a91SMarcos Paulo de Souza 21680ff40a91SMarcos Paulo de Souza return ret; 21690ff40a91SMarcos Paulo de Souza } 21700ff40a91SMarcos Paulo de Souza 21710ff40a91SMarcos Paulo de Souza /* 217274123bd7SChris Mason * adjust the pointers going up the tree, starting at level 217374123bd7SChris Mason * making sure the right key of each node is points to 'key'. 217474123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 217574123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 217674123bd7SChris Mason * higher levels 2177aa5d6bedSChris Mason * 217874123bd7SChris Mason */ 2179b167fa91SNikolay Borisov static void fixup_low_keys(struct btrfs_path *path, 21805f39d397SChris Mason struct btrfs_disk_key *key, int level) 2181be0e5c09SChris Mason { 2182be0e5c09SChris Mason int i; 21835f39d397SChris Mason struct extent_buffer *t; 21840e82bcfeSDavid Sterba int ret; 21855f39d397SChris Mason 2186234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 2187be0e5c09SChris Mason int tslot = path->slots[i]; 21880e82bcfeSDavid Sterba 2189eb60ceacSChris Mason if (!path->nodes[i]) 2190be0e5c09SChris Mason break; 21915f39d397SChris Mason t = path->nodes[i]; 2192f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(t, tslot, 2193f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_ATOMIC); 21940e82bcfeSDavid Sterba BUG_ON(ret < 0); 21955f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 2196d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 2197be0e5c09SChris Mason if (tslot != 0) 2198be0e5c09SChris Mason break; 2199be0e5c09SChris Mason } 2200be0e5c09SChris Mason } 2201be0e5c09SChris Mason 220274123bd7SChris Mason /* 220331840ae1SZheng Yan * update item key. 220431840ae1SZheng Yan * 220531840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 220631840ae1SZheng Yan * that the new key won't break the order 220731840ae1SZheng Yan */ 2208b7a0365eSDaniel Dressler void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info, 2209b7a0365eSDaniel Dressler struct btrfs_path *path, 2210310712b2SOmar Sandoval const struct btrfs_key *new_key) 221131840ae1SZheng Yan { 221231840ae1SZheng Yan struct btrfs_disk_key disk_key; 221331840ae1SZheng Yan struct extent_buffer *eb; 221431840ae1SZheng Yan int slot; 221531840ae1SZheng Yan 221631840ae1SZheng Yan eb = path->nodes[0]; 221731840ae1SZheng Yan slot = path->slots[0]; 221831840ae1SZheng Yan if (slot > 0) { 221931840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 22207c15d410SQu Wenruo if (unlikely(comp_keys(&disk_key, new_key) >= 0)) { 22217c15d410SQu Wenruo btrfs_crit(fs_info, 22227c15d410SQu Wenruo "slot %u key (%llu %u %llu) new key (%llu %u %llu)", 22237c15d410SQu Wenruo slot, btrfs_disk_key_objectid(&disk_key), 22247c15d410SQu Wenruo btrfs_disk_key_type(&disk_key), 22257c15d410SQu Wenruo btrfs_disk_key_offset(&disk_key), 22267c15d410SQu Wenruo new_key->objectid, new_key->type, 22277c15d410SQu Wenruo new_key->offset); 22287c15d410SQu Wenruo btrfs_print_leaf(eb); 22297c15d410SQu Wenruo BUG(); 22307c15d410SQu Wenruo } 223131840ae1SZheng Yan } 223231840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 223331840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 22347c15d410SQu Wenruo if (unlikely(comp_keys(&disk_key, new_key) <= 0)) { 22357c15d410SQu Wenruo btrfs_crit(fs_info, 22367c15d410SQu Wenruo "slot %u key (%llu %u %llu) new key (%llu %u %llu)", 22377c15d410SQu Wenruo slot, btrfs_disk_key_objectid(&disk_key), 22387c15d410SQu Wenruo btrfs_disk_key_type(&disk_key), 22397c15d410SQu Wenruo btrfs_disk_key_offset(&disk_key), 22407c15d410SQu Wenruo new_key->objectid, new_key->type, 22417c15d410SQu Wenruo new_key->offset); 22427c15d410SQu Wenruo btrfs_print_leaf(eb); 22437c15d410SQu Wenruo BUG(); 22447c15d410SQu Wenruo } 224531840ae1SZheng Yan } 224631840ae1SZheng Yan 224731840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 224831840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 224931840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 225031840ae1SZheng Yan if (slot == 0) 2251b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 225231840ae1SZheng Yan } 225331840ae1SZheng Yan 225431840ae1SZheng Yan /* 2255d16c702fSQu Wenruo * Check key order of two sibling extent buffers. 2256d16c702fSQu Wenruo * 2257d16c702fSQu Wenruo * Return true if something is wrong. 2258d16c702fSQu Wenruo * Return false if everything is fine. 2259d16c702fSQu Wenruo * 2260d16c702fSQu Wenruo * Tree-checker only works inside one tree block, thus the following 2261d16c702fSQu Wenruo * corruption can not be detected by tree-checker: 2262d16c702fSQu Wenruo * 2263d16c702fSQu Wenruo * Leaf @left | Leaf @right 2264d16c702fSQu Wenruo * -------------------------------------------------------------- 2265d16c702fSQu Wenruo * | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 | 2266d16c702fSQu Wenruo * 2267d16c702fSQu Wenruo * Key f6 in leaf @left itself is valid, but not valid when the next 2268d16c702fSQu Wenruo * key in leaf @right is 7. 2269d16c702fSQu Wenruo * This can only be checked at tree block merge time. 2270d16c702fSQu Wenruo * And since tree checker has ensured all key order in each tree block 2271d16c702fSQu Wenruo * is correct, we only need to bother the last key of @left and the first 2272d16c702fSQu Wenruo * key of @right. 2273d16c702fSQu Wenruo */ 2274d16c702fSQu Wenruo static bool check_sibling_keys(struct extent_buffer *left, 2275d16c702fSQu Wenruo struct extent_buffer *right) 2276d16c702fSQu Wenruo { 2277d16c702fSQu Wenruo struct btrfs_key left_last; 2278d16c702fSQu Wenruo struct btrfs_key right_first; 2279d16c702fSQu Wenruo int level = btrfs_header_level(left); 2280d16c702fSQu Wenruo int nr_left = btrfs_header_nritems(left); 2281d16c702fSQu Wenruo int nr_right = btrfs_header_nritems(right); 2282d16c702fSQu Wenruo 2283d16c702fSQu Wenruo /* No key to check in one of the tree blocks */ 2284d16c702fSQu Wenruo if (!nr_left || !nr_right) 2285d16c702fSQu Wenruo return false; 2286d16c702fSQu Wenruo 2287d16c702fSQu Wenruo if (level) { 2288d16c702fSQu Wenruo btrfs_node_key_to_cpu(left, &left_last, nr_left - 1); 2289d16c702fSQu Wenruo btrfs_node_key_to_cpu(right, &right_first, 0); 2290d16c702fSQu Wenruo } else { 2291d16c702fSQu Wenruo btrfs_item_key_to_cpu(left, &left_last, nr_left - 1); 2292d16c702fSQu Wenruo btrfs_item_key_to_cpu(right, &right_first, 0); 2293d16c702fSQu Wenruo } 2294d16c702fSQu Wenruo 2295d16c702fSQu Wenruo if (btrfs_comp_cpu_keys(&left_last, &right_first) >= 0) { 2296d16c702fSQu Wenruo btrfs_crit(left->fs_info, 2297d16c702fSQu Wenruo "bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)", 2298d16c702fSQu Wenruo left_last.objectid, left_last.type, 2299d16c702fSQu Wenruo left_last.offset, right_first.objectid, 2300d16c702fSQu Wenruo right_first.type, right_first.offset); 2301d16c702fSQu Wenruo return true; 2302d16c702fSQu Wenruo } 2303d16c702fSQu Wenruo return false; 2304d16c702fSQu Wenruo } 2305d16c702fSQu Wenruo 2306d16c702fSQu Wenruo /* 230774123bd7SChris Mason * try to push data from one node into the next node left in the 230879f95c82SChris Mason * tree. 2309aa5d6bedSChris Mason * 2310aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 2311aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 231274123bd7SChris Mason */ 231398ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 23142ff7e61eSJeff Mahoney struct extent_buffer *dst, 2315971a1f66SChris Mason struct extent_buffer *src, int empty) 2316be0e5c09SChris Mason { 2317d30a668fSDavid Sterba struct btrfs_fs_info *fs_info = trans->fs_info; 2318be0e5c09SChris Mason int push_items = 0; 2319bb803951SChris Mason int src_nritems; 2320bb803951SChris Mason int dst_nritems; 2321aa5d6bedSChris Mason int ret = 0; 2322be0e5c09SChris Mason 23235f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 23245f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 23250b246afaSJeff Mahoney push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems; 23267bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 23277bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 232854aa1f4dSChris Mason 2329bce4eae9SChris Mason if (!empty && src_nritems <= 8) 2330971a1f66SChris Mason return 1; 2331971a1f66SChris Mason 2332d397712bSChris Mason if (push_items <= 0) 2333be0e5c09SChris Mason return 1; 2334be0e5c09SChris Mason 2335bce4eae9SChris Mason if (empty) { 2336971a1f66SChris Mason push_items = min(src_nritems, push_items); 2337bce4eae9SChris Mason if (push_items < src_nritems) { 2338bce4eae9SChris Mason /* leave at least 8 pointers in the node if 2339bce4eae9SChris Mason * we aren't going to empty it 2340bce4eae9SChris Mason */ 2341bce4eae9SChris Mason if (src_nritems - push_items < 8) { 2342bce4eae9SChris Mason if (push_items <= 8) 2343bce4eae9SChris Mason return 1; 2344bce4eae9SChris Mason push_items -= 8; 2345bce4eae9SChris Mason } 2346bce4eae9SChris Mason } 2347bce4eae9SChris Mason } else 2348bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 234979f95c82SChris Mason 2350d16c702fSQu Wenruo /* dst is the left eb, src is the middle eb */ 2351d16c702fSQu Wenruo if (check_sibling_keys(dst, src)) { 2352d16c702fSQu Wenruo ret = -EUCLEAN; 2353d16c702fSQu Wenruo btrfs_abort_transaction(trans, ret); 2354d16c702fSQu Wenruo return ret; 2355d16c702fSQu Wenruo } 2356f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items); 23575de865eeSFilipe David Borba Manana if (ret) { 235866642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 23595de865eeSFilipe David Borba Manana return ret; 23605de865eeSFilipe David Borba Manana } 23615f39d397SChris Mason copy_extent_buffer(dst, src, 23625f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 23635f39d397SChris Mason btrfs_node_key_ptr_offset(0), 2364123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 23655f39d397SChris Mason 2366bb803951SChris Mason if (push_items < src_nritems) { 236757911b8bSJan Schmidt /* 2368f3a84ccdSFilipe Manana * Don't call btrfs_tree_mod_log_insert_move() here, key removal 2369f3a84ccdSFilipe Manana * was already fully logged by btrfs_tree_mod_log_eb_copy() above. 237057911b8bSJan Schmidt */ 23715f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 23725f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 2373e2fa7227SChris Mason (src_nritems - push_items) * 2374123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 2375bb803951SChris Mason } 23765f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 23775f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 23785f39d397SChris Mason btrfs_mark_buffer_dirty(src); 23795f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 238031840ae1SZheng Yan 2381bb803951SChris Mason return ret; 2382be0e5c09SChris Mason } 2383be0e5c09SChris Mason 238497571fd0SChris Mason /* 238579f95c82SChris Mason * try to push data from one node into the next node right in the 238679f95c82SChris Mason * tree. 238779f95c82SChris Mason * 238879f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 238979f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 239079f95c82SChris Mason * 239179f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 239279f95c82SChris Mason */ 23935f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 23945f39d397SChris Mason struct extent_buffer *dst, 23955f39d397SChris Mason struct extent_buffer *src) 239679f95c82SChris Mason { 239755d32ed8SDavid Sterba struct btrfs_fs_info *fs_info = trans->fs_info; 239879f95c82SChris Mason int push_items = 0; 239979f95c82SChris Mason int max_push; 240079f95c82SChris Mason int src_nritems; 240179f95c82SChris Mason int dst_nritems; 240279f95c82SChris Mason int ret = 0; 240379f95c82SChris Mason 24047bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 24057bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 24067bb86316SChris Mason 24075f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 24085f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 24090b246afaSJeff Mahoney push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems; 2410d397712bSChris Mason if (push_items <= 0) 241179f95c82SChris Mason return 1; 2412bce4eae9SChris Mason 2413d397712bSChris Mason if (src_nritems < 4) 2414bce4eae9SChris Mason return 1; 241579f95c82SChris Mason 241679f95c82SChris Mason max_push = src_nritems / 2 + 1; 241779f95c82SChris Mason /* don't try to empty the node */ 2418d397712bSChris Mason if (max_push >= src_nritems) 241979f95c82SChris Mason return 1; 2420252c38f0SYan 242179f95c82SChris Mason if (max_push < push_items) 242279f95c82SChris Mason push_items = max_push; 242379f95c82SChris Mason 2424d16c702fSQu Wenruo /* dst is the right eb, src is the middle eb */ 2425d16c702fSQu Wenruo if (check_sibling_keys(src, dst)) { 2426d16c702fSQu Wenruo ret = -EUCLEAN; 2427d16c702fSQu Wenruo btrfs_abort_transaction(trans, ret); 2428d16c702fSQu Wenruo return ret; 2429d16c702fSQu Wenruo } 2430f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_move(dst, push_items, 0, dst_nritems); 2431bf1d3425SDavid Sterba BUG_ON(ret < 0); 24325f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 24335f39d397SChris Mason btrfs_node_key_ptr_offset(0), 24345f39d397SChris Mason (dst_nritems) * 24355f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 2436d6025579SChris Mason 2437f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items, 2438ed874f0dSDavid Sterba push_items); 24395de865eeSFilipe David Borba Manana if (ret) { 244066642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 24415de865eeSFilipe David Borba Manana return ret; 24425de865eeSFilipe David Borba Manana } 24435f39d397SChris Mason copy_extent_buffer(dst, src, 24445f39d397SChris Mason btrfs_node_key_ptr_offset(0), 24455f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 2446123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 244779f95c82SChris Mason 24485f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 24495f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 245079f95c82SChris Mason 24515f39d397SChris Mason btrfs_mark_buffer_dirty(src); 24525f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 245331840ae1SZheng Yan 245479f95c82SChris Mason return ret; 245579f95c82SChris Mason } 245679f95c82SChris Mason 245779f95c82SChris Mason /* 245897571fd0SChris Mason * helper function to insert a new root level in the tree. 245997571fd0SChris Mason * A new node is allocated, and a single item is inserted to 246097571fd0SChris Mason * point to the existing root 2461aa5d6bedSChris Mason * 2462aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 246397571fd0SChris Mason */ 2464d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 24655f39d397SChris Mason struct btrfs_root *root, 2466fdd99c72SLiu Bo struct btrfs_path *path, int level) 246774123bd7SChris Mason { 24680b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 24697bb86316SChris Mason u64 lower_gen; 24705f39d397SChris Mason struct extent_buffer *lower; 24715f39d397SChris Mason struct extent_buffer *c; 2472925baeddSChris Mason struct extent_buffer *old; 24735f39d397SChris Mason struct btrfs_disk_key lower_key; 2474d9d19a01SDavid Sterba int ret; 24755c680ed6SChris Mason 24765c680ed6SChris Mason BUG_ON(path->nodes[level]); 24775c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 24785c680ed6SChris Mason 24797bb86316SChris Mason lower = path->nodes[level-1]; 24807bb86316SChris Mason if (level == 1) 24817bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 24827bb86316SChris Mason else 24837bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 24847bb86316SChris Mason 248579bd3712SFilipe Manana c = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 248679bd3712SFilipe Manana &lower_key, level, root->node->start, 0, 2487cf6f34aaSJosef Bacik BTRFS_NESTING_NEW_ROOT); 24885f39d397SChris Mason if (IS_ERR(c)) 24895f39d397SChris Mason return PTR_ERR(c); 2490925baeddSChris Mason 24910b246afaSJeff Mahoney root_add_used(root, fs_info->nodesize); 2492f0486c68SYan, Zheng 24935f39d397SChris Mason btrfs_set_header_nritems(c, 1); 24945f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 2495db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 24967bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 249731840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 24987bb86316SChris Mason 24997bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 25005f39d397SChris Mason 25015f39d397SChris Mason btrfs_mark_buffer_dirty(c); 2502d5719762SChris Mason 2503925baeddSChris Mason old = root->node; 2504406808abSFilipe Manana ret = btrfs_tree_mod_log_insert_root(root->node, c, false); 2505d9d19a01SDavid Sterba BUG_ON(ret < 0); 2506240f62c8SChris Mason rcu_assign_pointer(root->node, c); 2507925baeddSChris Mason 2508925baeddSChris Mason /* the super has an extra ref to root->node */ 2509925baeddSChris Mason free_extent_buffer(old); 2510925baeddSChris Mason 25110b86a832SChris Mason add_root_to_dirty_list(root); 251267439dadSDavid Sterba atomic_inc(&c->refs); 25135f39d397SChris Mason path->nodes[level] = c; 2514ac5887c8SJosef Bacik path->locks[level] = BTRFS_WRITE_LOCK; 251574123bd7SChris Mason path->slots[level] = 0; 251674123bd7SChris Mason return 0; 251774123bd7SChris Mason } 25185c680ed6SChris Mason 25195c680ed6SChris Mason /* 25205c680ed6SChris Mason * worker function to insert a single pointer in a node. 25215c680ed6SChris Mason * the node should have enough room for the pointer already 252297571fd0SChris Mason * 25235c680ed6SChris Mason * slot and level indicate where you want the key to go, and 25245c680ed6SChris Mason * blocknr is the block the key points to. 25255c680ed6SChris Mason */ 2526143bede5SJeff Mahoney static void insert_ptr(struct btrfs_trans_handle *trans, 25276ad3cf6dSDavid Sterba struct btrfs_path *path, 2528143bede5SJeff Mahoney struct btrfs_disk_key *key, u64 bytenr, 2529c3e06965SJan Schmidt int slot, int level) 25305c680ed6SChris Mason { 25315f39d397SChris Mason struct extent_buffer *lower; 25325c680ed6SChris Mason int nritems; 2533f3ea38daSJan Schmidt int ret; 25345c680ed6SChris Mason 25355c680ed6SChris Mason BUG_ON(!path->nodes[level]); 253649d0c642SFilipe Manana btrfs_assert_tree_write_locked(path->nodes[level]); 25375f39d397SChris Mason lower = path->nodes[level]; 25385f39d397SChris Mason nritems = btrfs_header_nritems(lower); 2539c293498bSStoyan Gaydarov BUG_ON(slot > nritems); 25406ad3cf6dSDavid Sterba BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info)); 254174123bd7SChris Mason if (slot != nritems) { 2542bf1d3425SDavid Sterba if (level) { 2543f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_move(lower, slot + 1, 2544f3a84ccdSFilipe Manana slot, nritems - slot); 2545bf1d3425SDavid Sterba BUG_ON(ret < 0); 2546bf1d3425SDavid Sterba } 25475f39d397SChris Mason memmove_extent_buffer(lower, 25485f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 25495f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 2550123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 255174123bd7SChris Mason } 2552c3e06965SJan Schmidt if (level) { 2553f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(lower, slot, 2554f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_ADD, GFP_NOFS); 2555f3ea38daSJan Schmidt BUG_ON(ret < 0); 2556f3ea38daSJan Schmidt } 25575f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 2558db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 255974493f7aSChris Mason WARN_ON(trans->transid == 0); 256074493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 25615f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 25625f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 256374123bd7SChris Mason } 256474123bd7SChris Mason 256597571fd0SChris Mason /* 256697571fd0SChris Mason * split the node at the specified level in path in two. 256797571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 256897571fd0SChris Mason * 256997571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 257097571fd0SChris Mason * left and right, if either one works, it returns right away. 2571aa5d6bedSChris Mason * 2572aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 257397571fd0SChris Mason */ 2574e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 2575e02119d5SChris Mason struct btrfs_root *root, 2576e02119d5SChris Mason struct btrfs_path *path, int level) 2577be0e5c09SChris Mason { 25780b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 25795f39d397SChris Mason struct extent_buffer *c; 25805f39d397SChris Mason struct extent_buffer *split; 25815f39d397SChris Mason struct btrfs_disk_key disk_key; 2582be0e5c09SChris Mason int mid; 25835c680ed6SChris Mason int ret; 25847518a238SChris Mason u32 c_nritems; 2585be0e5c09SChris Mason 25865f39d397SChris Mason c = path->nodes[level]; 25877bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 25885f39d397SChris Mason if (c == root->node) { 2589d9abbf1cSJan Schmidt /* 259090f8d62eSJan Schmidt * trying to split the root, lets make a new one 259190f8d62eSJan Schmidt * 2592fdd99c72SLiu Bo * tree mod log: We don't log_removal old root in 259390f8d62eSJan Schmidt * insert_new_root, because that root buffer will be kept as a 259490f8d62eSJan Schmidt * normal node. We are going to log removal of half of the 2595f3a84ccdSFilipe Manana * elements below with btrfs_tree_mod_log_eb_copy(). We're 2596f3a84ccdSFilipe Manana * holding a tree lock on the buffer, which is why we cannot 2597f3a84ccdSFilipe Manana * race with other tree_mod_log users. 2598d9abbf1cSJan Schmidt */ 2599fdd99c72SLiu Bo ret = insert_new_root(trans, root, path, level + 1); 26005c680ed6SChris Mason if (ret) 26015c680ed6SChris Mason return ret; 2602b3612421SChris Mason } else { 2603e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 26045f39d397SChris Mason c = path->nodes[level]; 26055f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 26060b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) 2607e66f709bSChris Mason return 0; 260854aa1f4dSChris Mason if (ret < 0) 260954aa1f4dSChris Mason return ret; 26105c680ed6SChris Mason } 2611e66f709bSChris Mason 26125f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 26135d4f98a2SYan Zheng mid = (c_nritems + 1) / 2; 26145d4f98a2SYan Zheng btrfs_node_key(c, &disk_key, mid); 26157bb86316SChris Mason 261679bd3712SFilipe Manana split = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 261779bd3712SFilipe Manana &disk_key, level, c->start, 0, 261879bd3712SFilipe Manana BTRFS_NESTING_SPLIT); 26195f39d397SChris Mason if (IS_ERR(split)) 26205f39d397SChris Mason return PTR_ERR(split); 262154aa1f4dSChris Mason 26220b246afaSJeff Mahoney root_add_used(root, fs_info->nodesize); 2623bc877d28SNikolay Borisov ASSERT(btrfs_header_level(c) == level); 26245f39d397SChris Mason 2625f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid); 26265de865eeSFilipe David Borba Manana if (ret) { 262766642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 26285de865eeSFilipe David Borba Manana return ret; 26295de865eeSFilipe David Borba Manana } 26305f39d397SChris Mason copy_extent_buffer(split, c, 26315f39d397SChris Mason btrfs_node_key_ptr_offset(0), 26325f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2633123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 26345f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 26355f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2636aa5d6bedSChris Mason 26375f39d397SChris Mason btrfs_mark_buffer_dirty(c); 26385f39d397SChris Mason btrfs_mark_buffer_dirty(split); 26395f39d397SChris Mason 26406ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, split->start, 2641c3e06965SJan Schmidt path->slots[level + 1] + 1, level + 1); 2642aa5d6bedSChris Mason 26435de08d7dSChris Mason if (path->slots[level] >= mid) { 26445c680ed6SChris Mason path->slots[level] -= mid; 2645925baeddSChris Mason btrfs_tree_unlock(c); 26465f39d397SChris Mason free_extent_buffer(c); 26475f39d397SChris Mason path->nodes[level] = split; 26485c680ed6SChris Mason path->slots[level + 1] += 1; 2649eb60ceacSChris Mason } else { 2650925baeddSChris Mason btrfs_tree_unlock(split); 26515f39d397SChris Mason free_extent_buffer(split); 2652be0e5c09SChris Mason } 2653d5286a92SNikolay Borisov return 0; 2654be0e5c09SChris Mason } 2655be0e5c09SChris Mason 265674123bd7SChris Mason /* 265774123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 265874123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 265974123bd7SChris Mason * space used both by the item structs and the item data 266074123bd7SChris Mason */ 26615f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2662be0e5c09SChris Mason { 2663be0e5c09SChris Mason int data_len; 26645f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2665d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2666be0e5c09SChris Mason 2667be0e5c09SChris Mason if (!nr) 2668be0e5c09SChris Mason return 0; 26693212fa14SJosef Bacik data_len = btrfs_item_offset(l, start) + btrfs_item_size(l, start); 26703212fa14SJosef Bacik data_len = data_len - btrfs_item_offset(l, end); 26710783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2672d4dbff95SChris Mason WARN_ON(data_len < 0); 2673be0e5c09SChris Mason return data_len; 2674be0e5c09SChris Mason } 2675be0e5c09SChris Mason 267674123bd7SChris Mason /* 2677d4dbff95SChris Mason * The space between the end of the leaf items and 2678d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2679d4dbff95SChris Mason * the leaf has left for both items and data 2680d4dbff95SChris Mason */ 2681e902baacSDavid Sterba noinline int btrfs_leaf_free_space(struct extent_buffer *leaf) 2682d4dbff95SChris Mason { 2683e902baacSDavid Sterba struct btrfs_fs_info *fs_info = leaf->fs_info; 26845f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 26855f39d397SChris Mason int ret; 26860b246afaSJeff Mahoney 26870b246afaSJeff Mahoney ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); 26885f39d397SChris Mason if (ret < 0) { 26890b246afaSJeff Mahoney btrfs_crit(fs_info, 2690efe120a0SFrank Holton "leaf free space ret %d, leaf data size %lu, used %d nritems %d", 2691da17066cSJeff Mahoney ret, 26920b246afaSJeff Mahoney (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info), 26935f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 26945f39d397SChris Mason } 26955f39d397SChris Mason return ret; 2696d4dbff95SChris Mason } 2697d4dbff95SChris Mason 269899d8f83cSChris Mason /* 269999d8f83cSChris Mason * min slot controls the lowest index we're willing to push to the 270099d8f83cSChris Mason * right. We'll push up to and including min_slot, but no lower 270199d8f83cSChris Mason */ 2702f72f0010SDavid Sterba static noinline int __push_leaf_right(struct btrfs_path *path, 270344871b1bSChris Mason int data_size, int empty, 270444871b1bSChris Mason struct extent_buffer *right, 270599d8f83cSChris Mason int free_space, u32 left_nritems, 270699d8f83cSChris Mason u32 min_slot) 270700ec4c51SChris Mason { 2708f72f0010SDavid Sterba struct btrfs_fs_info *fs_info = right->fs_info; 27095f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 271044871b1bSChris Mason struct extent_buffer *upper = path->nodes[1]; 2711cfed81a0SChris Mason struct btrfs_map_token token; 27125f39d397SChris Mason struct btrfs_disk_key disk_key; 271300ec4c51SChris Mason int slot; 271434a38218SChris Mason u32 i; 271500ec4c51SChris Mason int push_space = 0; 271600ec4c51SChris Mason int push_items = 0; 271734a38218SChris Mason u32 nr; 27187518a238SChris Mason u32 right_nritems; 27195f39d397SChris Mason u32 data_end; 2720db94535dSChris Mason u32 this_item_size; 272100ec4c51SChris Mason 272234a38218SChris Mason if (empty) 272334a38218SChris Mason nr = 0; 272434a38218SChris Mason else 272599d8f83cSChris Mason nr = max_t(u32, 1, min_slot); 272634a38218SChris Mason 272731840ae1SZheng Yan if (path->slots[0] >= left_nritems) 272887b29b20SYan Zheng push_space += data_size; 272931840ae1SZheng Yan 273044871b1bSChris Mason slot = path->slots[1]; 273134a38218SChris Mason i = left_nritems - 1; 273234a38218SChris Mason while (i >= nr) { 273331840ae1SZheng Yan if (!empty && push_items > 0) { 273431840ae1SZheng Yan if (path->slots[0] > i) 273531840ae1SZheng Yan break; 273631840ae1SZheng Yan if (path->slots[0] == i) { 2737e902baacSDavid Sterba int space = btrfs_leaf_free_space(left); 2738e902baacSDavid Sterba 273931840ae1SZheng Yan if (space + push_space * 2 > free_space) 274031840ae1SZheng Yan break; 274131840ae1SZheng Yan } 274231840ae1SZheng Yan } 274331840ae1SZheng Yan 274400ec4c51SChris Mason if (path->slots[0] == i) 274587b29b20SYan Zheng push_space += data_size; 2746db94535dSChris Mason 27473212fa14SJosef Bacik this_item_size = btrfs_item_size(left, i); 274874794207SJosef Bacik if (this_item_size + sizeof(struct btrfs_item) + 274974794207SJosef Bacik push_space > free_space) 275000ec4c51SChris Mason break; 275131840ae1SZheng Yan 275200ec4c51SChris Mason push_items++; 275374794207SJosef Bacik push_space += this_item_size + sizeof(struct btrfs_item); 275434a38218SChris Mason if (i == 0) 275534a38218SChris Mason break; 275634a38218SChris Mason i--; 2757db94535dSChris Mason } 27585f39d397SChris Mason 2759925baeddSChris Mason if (push_items == 0) 2760925baeddSChris Mason goto out_unlock; 27615f39d397SChris Mason 27626c1500f2SJulia Lawall WARN_ON(!empty && push_items == left_nritems); 27635f39d397SChris Mason 276400ec4c51SChris Mason /* push left to right */ 27655f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 276634a38218SChris Mason 2767dc2e724eSJosef Bacik push_space = btrfs_item_data_end(left, left_nritems - push_items); 27688f881e8cSDavid Sterba push_space -= leaf_data_end(left); 27695f39d397SChris Mason 277000ec4c51SChris Mason /* make room in the right data area */ 27718f881e8cSDavid Sterba data_end = leaf_data_end(right); 27725f39d397SChris Mason memmove_extent_buffer(right, 27733d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + data_end - push_space, 27743d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + data_end, 27750b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info) - data_end); 27765f39d397SChris Mason 277700ec4c51SChris Mason /* copy from the left data area */ 27783d9ec8c4SNikolay Borisov copy_extent_buffer(right, left, BTRFS_LEAF_DATA_OFFSET + 27790b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info) - push_space, 27808f881e8cSDavid Sterba BTRFS_LEAF_DATA_OFFSET + leaf_data_end(left), 2781d6025579SChris Mason push_space); 27825f39d397SChris Mason 27835f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 27845f39d397SChris Mason btrfs_item_nr_offset(0), 27850783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 27865f39d397SChris Mason 278700ec4c51SChris Mason /* copy the items from left to right */ 27885f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 27895f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 27900783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 279100ec4c51SChris Mason 279200ec4c51SChris Mason /* update the item pointers */ 2793c82f823cSDavid Sterba btrfs_init_map_token(&token, right); 27947518a238SChris Mason right_nritems += push_items; 27955f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 27960b246afaSJeff Mahoney push_space = BTRFS_LEAF_DATA_SIZE(fs_info); 27977518a238SChris Mason for (i = 0; i < right_nritems; i++) { 27983212fa14SJosef Bacik push_space -= btrfs_token_item_size(&token, i); 27993212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, push_space); 2800db94535dSChris Mason } 2801db94535dSChris Mason 28027518a238SChris Mason left_nritems -= push_items; 28035f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 280400ec4c51SChris Mason 280534a38218SChris Mason if (left_nritems) 28065f39d397SChris Mason btrfs_mark_buffer_dirty(left); 2807f0486c68SYan, Zheng else 28086a884d7dSDavid Sterba btrfs_clean_tree_block(left); 2809f0486c68SYan, Zheng 28105f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2811a429e513SChris Mason 28125f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 28135f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2814d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 281502217ed2SChris Mason 281600ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 28177518a238SChris Mason if (path->slots[0] >= left_nritems) { 28187518a238SChris Mason path->slots[0] -= left_nritems; 2819925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 28206a884d7dSDavid Sterba btrfs_clean_tree_block(path->nodes[0]); 2821925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 28225f39d397SChris Mason free_extent_buffer(path->nodes[0]); 28235f39d397SChris Mason path->nodes[0] = right; 282400ec4c51SChris Mason path->slots[1] += 1; 282500ec4c51SChris Mason } else { 2826925baeddSChris Mason btrfs_tree_unlock(right); 28275f39d397SChris Mason free_extent_buffer(right); 282800ec4c51SChris Mason } 282900ec4c51SChris Mason return 0; 2830925baeddSChris Mason 2831925baeddSChris Mason out_unlock: 2832925baeddSChris Mason btrfs_tree_unlock(right); 2833925baeddSChris Mason free_extent_buffer(right); 2834925baeddSChris Mason return 1; 283500ec4c51SChris Mason } 2836925baeddSChris Mason 283700ec4c51SChris Mason /* 283844871b1bSChris Mason * push some data in the path leaf to the right, trying to free up at 283974123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 284044871b1bSChris Mason * 284144871b1bSChris Mason * returns 1 if the push failed because the other node didn't have enough 284244871b1bSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 284399d8f83cSChris Mason * 284499d8f83cSChris Mason * this will push starting from min_slot to the end of the leaf. It won't 284599d8f83cSChris Mason * push any slot lower than min_slot 284674123bd7SChris Mason */ 284744871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 284899d8f83cSChris Mason *root, struct btrfs_path *path, 284999d8f83cSChris Mason int min_data_size, int data_size, 285099d8f83cSChris Mason int empty, u32 min_slot) 2851be0e5c09SChris Mason { 285244871b1bSChris Mason struct extent_buffer *left = path->nodes[0]; 285344871b1bSChris Mason struct extent_buffer *right; 285444871b1bSChris Mason struct extent_buffer *upper; 285544871b1bSChris Mason int slot; 285644871b1bSChris Mason int free_space; 285744871b1bSChris Mason u32 left_nritems; 285844871b1bSChris Mason int ret; 285944871b1bSChris Mason 286044871b1bSChris Mason if (!path->nodes[1]) 286144871b1bSChris Mason return 1; 286244871b1bSChris Mason 286344871b1bSChris Mason slot = path->slots[1]; 286444871b1bSChris Mason upper = path->nodes[1]; 286544871b1bSChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 286644871b1bSChris Mason return 1; 286744871b1bSChris Mason 286849d0c642SFilipe Manana btrfs_assert_tree_write_locked(path->nodes[1]); 286944871b1bSChris Mason 28704b231ae4SDavid Sterba right = btrfs_read_node_slot(upper, slot + 1); 2871fb770ae4SLiu Bo /* 2872fb770ae4SLiu Bo * slot + 1 is not valid or we fail to read the right node, 2873fb770ae4SLiu Bo * no big deal, just return. 2874fb770ae4SLiu Bo */ 2875fb770ae4SLiu Bo if (IS_ERR(right)) 287691ca338dSTsutomu Itoh return 1; 287791ca338dSTsutomu Itoh 2878bf77467aSJosef Bacik __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 287944871b1bSChris Mason 2880e902baacSDavid Sterba free_space = btrfs_leaf_free_space(right); 288144871b1bSChris Mason if (free_space < data_size) 288244871b1bSChris Mason goto out_unlock; 288344871b1bSChris Mason 288444871b1bSChris Mason /* cow and double check */ 288544871b1bSChris Mason ret = btrfs_cow_block(trans, root, right, upper, 2886bf59a5a2SJosef Bacik slot + 1, &right, BTRFS_NESTING_RIGHT_COW); 288744871b1bSChris Mason if (ret) 288844871b1bSChris Mason goto out_unlock; 288944871b1bSChris Mason 2890e902baacSDavid Sterba free_space = btrfs_leaf_free_space(right); 289144871b1bSChris Mason if (free_space < data_size) 289244871b1bSChris Mason goto out_unlock; 289344871b1bSChris Mason 289444871b1bSChris Mason left_nritems = btrfs_header_nritems(left); 289544871b1bSChris Mason if (left_nritems == 0) 289644871b1bSChris Mason goto out_unlock; 289744871b1bSChris Mason 2898d16c702fSQu Wenruo if (check_sibling_keys(left, right)) { 2899d16c702fSQu Wenruo ret = -EUCLEAN; 2900d16c702fSQu Wenruo btrfs_tree_unlock(right); 2901d16c702fSQu Wenruo free_extent_buffer(right); 2902d16c702fSQu Wenruo return ret; 2903d16c702fSQu Wenruo } 29042ef1fed2SFilipe David Borba Manana if (path->slots[0] == left_nritems && !empty) { 29052ef1fed2SFilipe David Borba Manana /* Key greater than all keys in the leaf, right neighbor has 29062ef1fed2SFilipe David Borba Manana * enough room for it and we're not emptying our leaf to delete 29072ef1fed2SFilipe David Borba Manana * it, therefore use right neighbor to insert the new item and 290852042d8eSAndrea Gelmini * no need to touch/dirty our left leaf. */ 29092ef1fed2SFilipe David Borba Manana btrfs_tree_unlock(left); 29102ef1fed2SFilipe David Borba Manana free_extent_buffer(left); 29112ef1fed2SFilipe David Borba Manana path->nodes[0] = right; 29122ef1fed2SFilipe David Borba Manana path->slots[0] = 0; 29132ef1fed2SFilipe David Borba Manana path->slots[1]++; 29142ef1fed2SFilipe David Borba Manana return 0; 29152ef1fed2SFilipe David Borba Manana } 29162ef1fed2SFilipe David Borba Manana 2917f72f0010SDavid Sterba return __push_leaf_right(path, min_data_size, empty, 291899d8f83cSChris Mason right, free_space, left_nritems, min_slot); 291944871b1bSChris Mason out_unlock: 292044871b1bSChris Mason btrfs_tree_unlock(right); 292144871b1bSChris Mason free_extent_buffer(right); 292244871b1bSChris Mason return 1; 292344871b1bSChris Mason } 292444871b1bSChris Mason 292544871b1bSChris Mason /* 292644871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 292744871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 292899d8f83cSChris Mason * 292999d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 293099d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the 293199d8f83cSChris Mason * items 293244871b1bSChris Mason */ 29338087c193SDavid Sterba static noinline int __push_leaf_left(struct btrfs_path *path, int data_size, 293444871b1bSChris Mason int empty, struct extent_buffer *left, 293599d8f83cSChris Mason int free_space, u32 right_nritems, 293699d8f83cSChris Mason u32 max_slot) 293744871b1bSChris Mason { 29388087c193SDavid Sterba struct btrfs_fs_info *fs_info = left->fs_info; 29395f39d397SChris Mason struct btrfs_disk_key disk_key; 29405f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 2941be0e5c09SChris Mason int i; 2942be0e5c09SChris Mason int push_space = 0; 2943be0e5c09SChris Mason int push_items = 0; 29447518a238SChris Mason u32 old_left_nritems; 294534a38218SChris Mason u32 nr; 2946aa5d6bedSChris Mason int ret = 0; 2947db94535dSChris Mason u32 this_item_size; 2948db94535dSChris Mason u32 old_left_item_size; 2949cfed81a0SChris Mason struct btrfs_map_token token; 2950cfed81a0SChris Mason 295134a38218SChris Mason if (empty) 295299d8f83cSChris Mason nr = min(right_nritems, max_slot); 295334a38218SChris Mason else 295499d8f83cSChris Mason nr = min(right_nritems - 1, max_slot); 295534a38218SChris Mason 295634a38218SChris Mason for (i = 0; i < nr; i++) { 295731840ae1SZheng Yan if (!empty && push_items > 0) { 295831840ae1SZheng Yan if (path->slots[0] < i) 295931840ae1SZheng Yan break; 296031840ae1SZheng Yan if (path->slots[0] == i) { 2961e902baacSDavid Sterba int space = btrfs_leaf_free_space(right); 2962e902baacSDavid Sterba 296331840ae1SZheng Yan if (space + push_space * 2 > free_space) 296431840ae1SZheng Yan break; 296531840ae1SZheng Yan } 296631840ae1SZheng Yan } 296731840ae1SZheng Yan 2968be0e5c09SChris Mason if (path->slots[0] == i) 296987b29b20SYan Zheng push_space += data_size; 2970db94535dSChris Mason 29713212fa14SJosef Bacik this_item_size = btrfs_item_size(right, i); 297274794207SJosef Bacik if (this_item_size + sizeof(struct btrfs_item) + push_space > 297374794207SJosef Bacik free_space) 2974be0e5c09SChris Mason break; 2975db94535dSChris Mason 2976be0e5c09SChris Mason push_items++; 297774794207SJosef Bacik push_space += this_item_size + sizeof(struct btrfs_item); 2978be0e5c09SChris Mason } 2979db94535dSChris Mason 2980be0e5c09SChris Mason if (push_items == 0) { 2981925baeddSChris Mason ret = 1; 2982925baeddSChris Mason goto out; 2983be0e5c09SChris Mason } 2984fae7f21cSDulshani Gunawardhana WARN_ON(!empty && push_items == btrfs_header_nritems(right)); 29855f39d397SChris Mason 2986be0e5c09SChris Mason /* push data from right to left */ 29875f39d397SChris Mason copy_extent_buffer(left, right, 29885f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 29895f39d397SChris Mason btrfs_item_nr_offset(0), 29905f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 29915f39d397SChris Mason 29920b246afaSJeff Mahoney push_space = BTRFS_LEAF_DATA_SIZE(fs_info) - 29933212fa14SJosef Bacik btrfs_item_offset(right, push_items - 1); 29945f39d397SChris Mason 29953d9ec8c4SNikolay Borisov copy_extent_buffer(left, right, BTRFS_LEAF_DATA_OFFSET + 29968f881e8cSDavid Sterba leaf_data_end(left) - push_space, 29973d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + 29983212fa14SJosef Bacik btrfs_item_offset(right, push_items - 1), 2999be0e5c09SChris Mason push_space); 30005f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 300187b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 3002eb60ceacSChris Mason 3003c82f823cSDavid Sterba btrfs_init_map_token(&token, left); 30043212fa14SJosef Bacik old_left_item_size = btrfs_item_offset(left, old_left_nritems - 1); 3005be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 30065f39d397SChris Mason u32 ioff; 3007db94535dSChris Mason 30083212fa14SJosef Bacik ioff = btrfs_token_item_offset(&token, i); 30093212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, 3010cc4c13d5SDavid Sterba ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size)); 3011be0e5c09SChris Mason } 30125f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 3013be0e5c09SChris Mason 3014be0e5c09SChris Mason /* fixup right node */ 301531b1a2bdSJulia Lawall if (push_items > right_nritems) 301631b1a2bdSJulia Lawall WARN(1, KERN_CRIT "push items %d nr %u\n", push_items, 3017d397712bSChris Mason right_nritems); 301834a38218SChris Mason 301934a38218SChris Mason if (push_items < right_nritems) { 30203212fa14SJosef Bacik push_space = btrfs_item_offset(right, push_items - 1) - 30218f881e8cSDavid Sterba leaf_data_end(right); 30223d9ec8c4SNikolay Borisov memmove_extent_buffer(right, BTRFS_LEAF_DATA_OFFSET + 30230b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info) - push_space, 30243d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + 30258f881e8cSDavid Sterba leaf_data_end(right), push_space); 30265f39d397SChris Mason 30275f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 30285f39d397SChris Mason btrfs_item_nr_offset(push_items), 30295f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 30300783fcfcSChris Mason sizeof(struct btrfs_item)); 303134a38218SChris Mason } 3032c82f823cSDavid Sterba 3033c82f823cSDavid Sterba btrfs_init_map_token(&token, right); 3034eef1c494SYan right_nritems -= push_items; 3035eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 30360b246afaSJeff Mahoney push_space = BTRFS_LEAF_DATA_SIZE(fs_info); 30375f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 30383212fa14SJosef Bacik push_space = push_space - btrfs_token_item_size(&token, i); 30393212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, push_space); 3040db94535dSChris Mason } 3041eb60ceacSChris Mason 30425f39d397SChris Mason btrfs_mark_buffer_dirty(left); 304334a38218SChris Mason if (right_nritems) 30445f39d397SChris Mason btrfs_mark_buffer_dirty(right); 3045f0486c68SYan, Zheng else 30466a884d7dSDavid Sterba btrfs_clean_tree_block(right); 3047098f59c2SChris Mason 30485f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 3049b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 3050be0e5c09SChris Mason 3051be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 3052be0e5c09SChris Mason if (path->slots[0] < push_items) { 3053be0e5c09SChris Mason path->slots[0] += old_left_nritems; 3054925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 30555f39d397SChris Mason free_extent_buffer(path->nodes[0]); 30565f39d397SChris Mason path->nodes[0] = left; 3057be0e5c09SChris Mason path->slots[1] -= 1; 3058be0e5c09SChris Mason } else { 3059925baeddSChris Mason btrfs_tree_unlock(left); 30605f39d397SChris Mason free_extent_buffer(left); 3061be0e5c09SChris Mason path->slots[0] -= push_items; 3062be0e5c09SChris Mason } 3063eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 3064aa5d6bedSChris Mason return ret; 3065925baeddSChris Mason out: 3066925baeddSChris Mason btrfs_tree_unlock(left); 3067925baeddSChris Mason free_extent_buffer(left); 3068925baeddSChris Mason return ret; 3069be0e5c09SChris Mason } 3070be0e5c09SChris Mason 307174123bd7SChris Mason /* 307244871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 307344871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 307499d8f83cSChris Mason * 307599d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 307699d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the 307799d8f83cSChris Mason * items 307844871b1bSChris Mason */ 307944871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 308099d8f83cSChris Mason *root, struct btrfs_path *path, int min_data_size, 308199d8f83cSChris Mason int data_size, int empty, u32 max_slot) 308244871b1bSChris Mason { 308344871b1bSChris Mason struct extent_buffer *right = path->nodes[0]; 308444871b1bSChris Mason struct extent_buffer *left; 308544871b1bSChris Mason int slot; 308644871b1bSChris Mason int free_space; 308744871b1bSChris Mason u32 right_nritems; 308844871b1bSChris Mason int ret = 0; 308944871b1bSChris Mason 309044871b1bSChris Mason slot = path->slots[1]; 309144871b1bSChris Mason if (slot == 0) 309244871b1bSChris Mason return 1; 309344871b1bSChris Mason if (!path->nodes[1]) 309444871b1bSChris Mason return 1; 309544871b1bSChris Mason 309644871b1bSChris Mason right_nritems = btrfs_header_nritems(right); 309744871b1bSChris Mason if (right_nritems == 0) 309844871b1bSChris Mason return 1; 309944871b1bSChris Mason 310049d0c642SFilipe Manana btrfs_assert_tree_write_locked(path->nodes[1]); 310144871b1bSChris Mason 31024b231ae4SDavid Sterba left = btrfs_read_node_slot(path->nodes[1], slot - 1); 3103fb770ae4SLiu Bo /* 3104fb770ae4SLiu Bo * slot - 1 is not valid or we fail to read the left node, 3105fb770ae4SLiu Bo * no big deal, just return. 3106fb770ae4SLiu Bo */ 3107fb770ae4SLiu Bo if (IS_ERR(left)) 310891ca338dSTsutomu Itoh return 1; 310991ca338dSTsutomu Itoh 3110bf77467aSJosef Bacik __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 311144871b1bSChris Mason 3112e902baacSDavid Sterba free_space = btrfs_leaf_free_space(left); 311344871b1bSChris Mason if (free_space < data_size) { 311444871b1bSChris Mason ret = 1; 311544871b1bSChris Mason goto out; 311644871b1bSChris Mason } 311744871b1bSChris Mason 311844871b1bSChris Mason /* cow and double check */ 311944871b1bSChris Mason ret = btrfs_cow_block(trans, root, left, 31209631e4ccSJosef Bacik path->nodes[1], slot - 1, &left, 3121bf59a5a2SJosef Bacik BTRFS_NESTING_LEFT_COW); 312244871b1bSChris Mason if (ret) { 312344871b1bSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 312479787eaaSJeff Mahoney if (ret == -ENOSPC) 312544871b1bSChris Mason ret = 1; 312644871b1bSChris Mason goto out; 312744871b1bSChris Mason } 312844871b1bSChris Mason 3129e902baacSDavid Sterba free_space = btrfs_leaf_free_space(left); 313044871b1bSChris Mason if (free_space < data_size) { 313144871b1bSChris Mason ret = 1; 313244871b1bSChris Mason goto out; 313344871b1bSChris Mason } 313444871b1bSChris Mason 3135d16c702fSQu Wenruo if (check_sibling_keys(left, right)) { 3136d16c702fSQu Wenruo ret = -EUCLEAN; 3137d16c702fSQu Wenruo goto out; 3138d16c702fSQu Wenruo } 31398087c193SDavid Sterba return __push_leaf_left(path, min_data_size, 314099d8f83cSChris Mason empty, left, free_space, right_nritems, 314199d8f83cSChris Mason max_slot); 314244871b1bSChris Mason out: 314344871b1bSChris Mason btrfs_tree_unlock(left); 314444871b1bSChris Mason free_extent_buffer(left); 314544871b1bSChris Mason return ret; 314644871b1bSChris Mason } 314744871b1bSChris Mason 314844871b1bSChris Mason /* 314974123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 315074123bd7SChris Mason * available for the resulting leaf level of the path. 315174123bd7SChris Mason */ 3152143bede5SJeff Mahoney static noinline void copy_for_split(struct btrfs_trans_handle *trans, 315344871b1bSChris Mason struct btrfs_path *path, 315444871b1bSChris Mason struct extent_buffer *l, 315544871b1bSChris Mason struct extent_buffer *right, 315644871b1bSChris Mason int slot, int mid, int nritems) 3157be0e5c09SChris Mason { 315894f94ad9SDavid Sterba struct btrfs_fs_info *fs_info = trans->fs_info; 3159be0e5c09SChris Mason int data_copy_size; 3160be0e5c09SChris Mason int rt_data_off; 3161be0e5c09SChris Mason int i; 3162d4dbff95SChris Mason struct btrfs_disk_key disk_key; 3163cfed81a0SChris Mason struct btrfs_map_token token; 3164cfed81a0SChris Mason 31655f39d397SChris Mason nritems = nritems - mid; 31665f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 3167dc2e724eSJosef Bacik data_copy_size = btrfs_item_data_end(l, mid) - leaf_data_end(l); 31685f39d397SChris Mason 31695f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 31705f39d397SChris Mason btrfs_item_nr_offset(mid), 31715f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 31725f39d397SChris Mason 31735f39d397SChris Mason copy_extent_buffer(right, l, 31743d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + BTRFS_LEAF_DATA_SIZE(fs_info) - 31753d9ec8c4SNikolay Borisov data_copy_size, BTRFS_LEAF_DATA_OFFSET + 31768f881e8cSDavid Sterba leaf_data_end(l), data_copy_size); 317774123bd7SChris Mason 3178dc2e724eSJosef Bacik rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_data_end(l, mid); 31795f39d397SChris Mason 3180c82f823cSDavid Sterba btrfs_init_map_token(&token, right); 31815f39d397SChris Mason for (i = 0; i < nritems; i++) { 3182db94535dSChris Mason u32 ioff; 3183db94535dSChris Mason 31843212fa14SJosef Bacik ioff = btrfs_token_item_offset(&token, i); 31853212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, ioff + rt_data_off); 31860783fcfcSChris Mason } 318774123bd7SChris Mason 31885f39d397SChris Mason btrfs_set_header_nritems(l, mid); 31895f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 31906ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1); 31915f39d397SChris Mason 31925f39d397SChris Mason btrfs_mark_buffer_dirty(right); 31935f39d397SChris Mason btrfs_mark_buffer_dirty(l); 3194eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 31955f39d397SChris Mason 3196be0e5c09SChris Mason if (mid <= slot) { 3197925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 31985f39d397SChris Mason free_extent_buffer(path->nodes[0]); 31995f39d397SChris Mason path->nodes[0] = right; 3200be0e5c09SChris Mason path->slots[0] -= mid; 3201be0e5c09SChris Mason path->slots[1] += 1; 3202925baeddSChris Mason } else { 3203925baeddSChris Mason btrfs_tree_unlock(right); 32045f39d397SChris Mason free_extent_buffer(right); 3205925baeddSChris Mason } 32065f39d397SChris Mason 3207eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 320844871b1bSChris Mason } 320944871b1bSChris Mason 321044871b1bSChris Mason /* 321199d8f83cSChris Mason * double splits happen when we need to insert a big item in the middle 321299d8f83cSChris Mason * of a leaf. A double split can leave us with 3 mostly empty leaves: 321399d8f83cSChris Mason * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ] 321499d8f83cSChris Mason * A B C 321599d8f83cSChris Mason * 321699d8f83cSChris Mason * We avoid this by trying to push the items on either side of our target 321799d8f83cSChris Mason * into the adjacent leaves. If all goes well we can avoid the double split 321899d8f83cSChris Mason * completely. 321999d8f83cSChris Mason */ 322099d8f83cSChris Mason static noinline int push_for_double_split(struct btrfs_trans_handle *trans, 322199d8f83cSChris Mason struct btrfs_root *root, 322299d8f83cSChris Mason struct btrfs_path *path, 322399d8f83cSChris Mason int data_size) 322499d8f83cSChris Mason { 322599d8f83cSChris Mason int ret; 322699d8f83cSChris Mason int progress = 0; 322799d8f83cSChris Mason int slot; 322899d8f83cSChris Mason u32 nritems; 32295a4267caSFilipe David Borba Manana int space_needed = data_size; 323099d8f83cSChris Mason 323199d8f83cSChris Mason slot = path->slots[0]; 32325a4267caSFilipe David Borba Manana if (slot < btrfs_header_nritems(path->nodes[0])) 3233e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(path->nodes[0]); 323499d8f83cSChris Mason 323599d8f83cSChris Mason /* 323699d8f83cSChris Mason * try to push all the items after our slot into the 323799d8f83cSChris Mason * right leaf 323899d8f83cSChris Mason */ 32395a4267caSFilipe David Borba Manana ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot); 324099d8f83cSChris Mason if (ret < 0) 324199d8f83cSChris Mason return ret; 324299d8f83cSChris Mason 324399d8f83cSChris Mason if (ret == 0) 324499d8f83cSChris Mason progress++; 324599d8f83cSChris Mason 324699d8f83cSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 324799d8f83cSChris Mason /* 324899d8f83cSChris Mason * our goal is to get our slot at the start or end of a leaf. If 324999d8f83cSChris Mason * we've done so we're done 325099d8f83cSChris Mason */ 325199d8f83cSChris Mason if (path->slots[0] == 0 || path->slots[0] == nritems) 325299d8f83cSChris Mason return 0; 325399d8f83cSChris Mason 3254e902baacSDavid Sterba if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) 325599d8f83cSChris Mason return 0; 325699d8f83cSChris Mason 325799d8f83cSChris Mason /* try to push all the items before our slot into the next leaf */ 325899d8f83cSChris Mason slot = path->slots[0]; 3259263d3995SFilipe Manana space_needed = data_size; 3260263d3995SFilipe Manana if (slot > 0) 3261e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(path->nodes[0]); 32625a4267caSFilipe David Borba Manana ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot); 326399d8f83cSChris Mason if (ret < 0) 326499d8f83cSChris Mason return ret; 326599d8f83cSChris Mason 326699d8f83cSChris Mason if (ret == 0) 326799d8f83cSChris Mason progress++; 326899d8f83cSChris Mason 326999d8f83cSChris Mason if (progress) 327099d8f83cSChris Mason return 0; 327199d8f83cSChris Mason return 1; 327299d8f83cSChris Mason } 327399d8f83cSChris Mason 327499d8f83cSChris Mason /* 327544871b1bSChris Mason * split the path's leaf in two, making sure there is at least data_size 327644871b1bSChris Mason * available for the resulting leaf level of the path. 327744871b1bSChris Mason * 327844871b1bSChris Mason * returns 0 if all went well and < 0 on failure. 327944871b1bSChris Mason */ 328044871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 328144871b1bSChris Mason struct btrfs_root *root, 3282310712b2SOmar Sandoval const struct btrfs_key *ins_key, 328344871b1bSChris Mason struct btrfs_path *path, int data_size, 328444871b1bSChris Mason int extend) 328544871b1bSChris Mason { 32865d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 328744871b1bSChris Mason struct extent_buffer *l; 328844871b1bSChris Mason u32 nritems; 328944871b1bSChris Mason int mid; 329044871b1bSChris Mason int slot; 329144871b1bSChris Mason struct extent_buffer *right; 3292b7a0365eSDaniel Dressler struct btrfs_fs_info *fs_info = root->fs_info; 329344871b1bSChris Mason int ret = 0; 329444871b1bSChris Mason int wret; 32955d4f98a2SYan Zheng int split; 329644871b1bSChris Mason int num_doubles = 0; 329799d8f83cSChris Mason int tried_avoid_double = 0; 329844871b1bSChris Mason 3299a5719521SYan, Zheng l = path->nodes[0]; 3300a5719521SYan, Zheng slot = path->slots[0]; 33013212fa14SJosef Bacik if (extend && data_size + btrfs_item_size(l, slot) + 33020b246afaSJeff Mahoney sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info)) 3303a5719521SYan, Zheng return -EOVERFLOW; 3304a5719521SYan, Zheng 330544871b1bSChris Mason /* first try to make some room by pushing left and right */ 330633157e05SLiu Bo if (data_size && path->nodes[1]) { 33075a4267caSFilipe David Borba Manana int space_needed = data_size; 33085a4267caSFilipe David Borba Manana 33095a4267caSFilipe David Borba Manana if (slot < btrfs_header_nritems(l)) 3310e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(l); 33115a4267caSFilipe David Borba Manana 33125a4267caSFilipe David Borba Manana wret = push_leaf_right(trans, root, path, space_needed, 33135a4267caSFilipe David Borba Manana space_needed, 0, 0); 331444871b1bSChris Mason if (wret < 0) 331544871b1bSChris Mason return wret; 331644871b1bSChris Mason if (wret) { 3317263d3995SFilipe Manana space_needed = data_size; 3318263d3995SFilipe Manana if (slot > 0) 3319e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(l); 33205a4267caSFilipe David Borba Manana wret = push_leaf_left(trans, root, path, space_needed, 33215a4267caSFilipe David Borba Manana space_needed, 0, (u32)-1); 332244871b1bSChris Mason if (wret < 0) 332344871b1bSChris Mason return wret; 332444871b1bSChris Mason } 332544871b1bSChris Mason l = path->nodes[0]; 332644871b1bSChris Mason 332744871b1bSChris Mason /* did the pushes work? */ 3328e902baacSDavid Sterba if (btrfs_leaf_free_space(l) >= data_size) 332944871b1bSChris Mason return 0; 333044871b1bSChris Mason } 333144871b1bSChris Mason 333244871b1bSChris Mason if (!path->nodes[1]) { 3333fdd99c72SLiu Bo ret = insert_new_root(trans, root, path, 1); 333444871b1bSChris Mason if (ret) 333544871b1bSChris Mason return ret; 333644871b1bSChris Mason } 333744871b1bSChris Mason again: 33385d4f98a2SYan Zheng split = 1; 333944871b1bSChris Mason l = path->nodes[0]; 334044871b1bSChris Mason slot = path->slots[0]; 334144871b1bSChris Mason nritems = btrfs_header_nritems(l); 334244871b1bSChris Mason mid = (nritems + 1) / 2; 334344871b1bSChris Mason 33445d4f98a2SYan Zheng if (mid <= slot) { 33455d4f98a2SYan Zheng if (nritems == 1 || 33465d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + data_size > 33470b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info)) { 33485d4f98a2SYan Zheng if (slot >= nritems) { 33495d4f98a2SYan Zheng split = 0; 33505d4f98a2SYan Zheng } else { 33515d4f98a2SYan Zheng mid = slot; 33525d4f98a2SYan Zheng if (mid != nritems && 33535d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 33540b246afaSJeff Mahoney data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) { 335599d8f83cSChris Mason if (data_size && !tried_avoid_double) 335699d8f83cSChris Mason goto push_for_double; 33575d4f98a2SYan Zheng split = 2; 33585d4f98a2SYan Zheng } 33595d4f98a2SYan Zheng } 33605d4f98a2SYan Zheng } 33615d4f98a2SYan Zheng } else { 33625d4f98a2SYan Zheng if (leaf_space_used(l, 0, mid) + data_size > 33630b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info)) { 33645d4f98a2SYan Zheng if (!extend && data_size && slot == 0) { 33655d4f98a2SYan Zheng split = 0; 33665d4f98a2SYan Zheng } else if ((extend || !data_size) && slot == 0) { 33675d4f98a2SYan Zheng mid = 1; 33685d4f98a2SYan Zheng } else { 33695d4f98a2SYan Zheng mid = slot; 33705d4f98a2SYan Zheng if (mid != nritems && 33715d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 33720b246afaSJeff Mahoney data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) { 337399d8f83cSChris Mason if (data_size && !tried_avoid_double) 337499d8f83cSChris Mason goto push_for_double; 33755d4f98a2SYan Zheng split = 2; 33765d4f98a2SYan Zheng } 33775d4f98a2SYan Zheng } 33785d4f98a2SYan Zheng } 33795d4f98a2SYan Zheng } 33805d4f98a2SYan Zheng 33815d4f98a2SYan Zheng if (split == 0) 33825d4f98a2SYan Zheng btrfs_cpu_key_to_disk(&disk_key, ins_key); 33835d4f98a2SYan Zheng else 33845d4f98a2SYan Zheng btrfs_item_key(l, &disk_key, mid); 33855d4f98a2SYan Zheng 3386ca9d473aSJosef Bacik /* 3387ca9d473aSJosef Bacik * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double 3388ca9d473aSJosef Bacik * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES 3389ca9d473aSJosef Bacik * subclasses, which is 8 at the time of this patch, and we've maxed it 3390ca9d473aSJosef Bacik * out. In the future we could add a 3391ca9d473aSJosef Bacik * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just 3392ca9d473aSJosef Bacik * use BTRFS_NESTING_NEW_ROOT. 3393ca9d473aSJosef Bacik */ 339479bd3712SFilipe Manana right = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 339579bd3712SFilipe Manana &disk_key, 0, l->start, 0, 339679bd3712SFilipe Manana num_doubles ? BTRFS_NESTING_NEW_ROOT : 3397ca9d473aSJosef Bacik BTRFS_NESTING_SPLIT); 3398f0486c68SYan, Zheng if (IS_ERR(right)) 339944871b1bSChris Mason return PTR_ERR(right); 3400f0486c68SYan, Zheng 34010b246afaSJeff Mahoney root_add_used(root, fs_info->nodesize); 340244871b1bSChris Mason 34035d4f98a2SYan Zheng if (split == 0) { 340444871b1bSChris Mason if (mid <= slot) { 340544871b1bSChris Mason btrfs_set_header_nritems(right, 0); 34066ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, 34072ff7e61eSJeff Mahoney right->start, path->slots[1] + 1, 1); 340844871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 340944871b1bSChris Mason free_extent_buffer(path->nodes[0]); 341044871b1bSChris Mason path->nodes[0] = right; 341144871b1bSChris Mason path->slots[0] = 0; 341244871b1bSChris Mason path->slots[1] += 1; 341344871b1bSChris Mason } else { 341444871b1bSChris Mason btrfs_set_header_nritems(right, 0); 34156ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, 34162ff7e61eSJeff Mahoney right->start, path->slots[1], 1); 341744871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 341844871b1bSChris Mason free_extent_buffer(path->nodes[0]); 341944871b1bSChris Mason path->nodes[0] = right; 342044871b1bSChris Mason path->slots[0] = 0; 3421143bede5SJeff Mahoney if (path->slots[1] == 0) 3422b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 34235d4f98a2SYan Zheng } 3424196e0249SLiu Bo /* 3425196e0249SLiu Bo * We create a new leaf 'right' for the required ins_len and 3426196e0249SLiu Bo * we'll do btrfs_mark_buffer_dirty() on this leaf after copying 3427196e0249SLiu Bo * the content of ins_len to 'right'. 3428196e0249SLiu Bo */ 342944871b1bSChris Mason return ret; 343044871b1bSChris Mason } 343144871b1bSChris Mason 343294f94ad9SDavid Sterba copy_for_split(trans, path, l, right, slot, mid, nritems); 343344871b1bSChris Mason 34345d4f98a2SYan Zheng if (split == 2) { 3435cc0c5538SChris Mason BUG_ON(num_doubles != 0); 3436cc0c5538SChris Mason num_doubles++; 3437cc0c5538SChris Mason goto again; 34383326d1b0SChris Mason } 343944871b1bSChris Mason 3440143bede5SJeff Mahoney return 0; 344199d8f83cSChris Mason 344299d8f83cSChris Mason push_for_double: 344399d8f83cSChris Mason push_for_double_split(trans, root, path, data_size); 344499d8f83cSChris Mason tried_avoid_double = 1; 3445e902baacSDavid Sterba if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) 344699d8f83cSChris Mason return 0; 344799d8f83cSChris Mason goto again; 3448be0e5c09SChris Mason } 3449be0e5c09SChris Mason 3450ad48fd75SYan, Zheng static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3451ad48fd75SYan, Zheng struct btrfs_root *root, 3452ad48fd75SYan, Zheng struct btrfs_path *path, int ins_len) 3453ad48fd75SYan, Zheng { 3454ad48fd75SYan, Zheng struct btrfs_key key; 3455ad48fd75SYan, Zheng struct extent_buffer *leaf; 3456ad48fd75SYan, Zheng struct btrfs_file_extent_item *fi; 3457ad48fd75SYan, Zheng u64 extent_len = 0; 3458ad48fd75SYan, Zheng u32 item_size; 3459ad48fd75SYan, Zheng int ret; 3460ad48fd75SYan, Zheng 3461ad48fd75SYan, Zheng leaf = path->nodes[0]; 3462ad48fd75SYan, Zheng btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 3463ad48fd75SYan, Zheng 3464ad48fd75SYan, Zheng BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY && 3465ad48fd75SYan, Zheng key.type != BTRFS_EXTENT_CSUM_KEY); 3466ad48fd75SYan, Zheng 3467e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) >= ins_len) 3468ad48fd75SYan, Zheng return 0; 3469ad48fd75SYan, Zheng 34703212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 3471ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3472ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3473ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3474ad48fd75SYan, Zheng extent_len = btrfs_file_extent_num_bytes(leaf, fi); 3475ad48fd75SYan, Zheng } 3476b3b4aa74SDavid Sterba btrfs_release_path(path); 3477ad48fd75SYan, Zheng 3478ad48fd75SYan, Zheng path->keep_locks = 1; 3479ad48fd75SYan, Zheng path->search_for_split = 1; 3480ad48fd75SYan, Zheng ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 3481ad48fd75SYan, Zheng path->search_for_split = 0; 3482a8df6fe6SFilipe Manana if (ret > 0) 3483a8df6fe6SFilipe Manana ret = -EAGAIN; 3484ad48fd75SYan, Zheng if (ret < 0) 3485ad48fd75SYan, Zheng goto err; 3486ad48fd75SYan, Zheng 3487ad48fd75SYan, Zheng ret = -EAGAIN; 3488ad48fd75SYan, Zheng leaf = path->nodes[0]; 3489a8df6fe6SFilipe Manana /* if our item isn't there, return now */ 34903212fa14SJosef Bacik if (item_size != btrfs_item_size(leaf, path->slots[0])) 3491ad48fd75SYan, Zheng goto err; 3492ad48fd75SYan, Zheng 3493109f6aefSChris Mason /* the leaf has changed, it now has room. return now */ 3494e902baacSDavid Sterba if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len) 3495109f6aefSChris Mason goto err; 3496109f6aefSChris Mason 3497ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3498ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3499ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3500ad48fd75SYan, Zheng if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) 3501ad48fd75SYan, Zheng goto err; 3502ad48fd75SYan, Zheng } 3503ad48fd75SYan, Zheng 3504ad48fd75SYan, Zheng ret = split_leaf(trans, root, &key, path, ins_len, 1); 3505f0486c68SYan, Zheng if (ret) 3506f0486c68SYan, Zheng goto err; 3507ad48fd75SYan, Zheng 3508ad48fd75SYan, Zheng path->keep_locks = 0; 3509ad48fd75SYan, Zheng btrfs_unlock_up_safe(path, 1); 3510ad48fd75SYan, Zheng return 0; 3511ad48fd75SYan, Zheng err: 3512ad48fd75SYan, Zheng path->keep_locks = 0; 3513ad48fd75SYan, Zheng return ret; 3514ad48fd75SYan, Zheng } 3515ad48fd75SYan, Zheng 351625263cd7SDavid Sterba static noinline int split_item(struct btrfs_path *path, 3517310712b2SOmar Sandoval const struct btrfs_key *new_key, 3518459931ecSChris Mason unsigned long split_offset) 3519459931ecSChris Mason { 3520459931ecSChris Mason struct extent_buffer *leaf; 3521c91666b1SJosef Bacik int orig_slot, slot; 3522ad48fd75SYan, Zheng char *buf; 3523459931ecSChris Mason u32 nritems; 3524ad48fd75SYan, Zheng u32 item_size; 3525459931ecSChris Mason u32 orig_offset; 3526459931ecSChris Mason struct btrfs_disk_key disk_key; 3527459931ecSChris Mason 3528459931ecSChris Mason leaf = path->nodes[0]; 3529e902baacSDavid Sterba BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)); 3530b9473439SChris Mason 3531c91666b1SJosef Bacik orig_slot = path->slots[0]; 35323212fa14SJosef Bacik orig_offset = btrfs_item_offset(leaf, path->slots[0]); 35333212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 3534459931ecSChris Mason 3535459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 3536ad48fd75SYan, Zheng if (!buf) 3537ad48fd75SYan, Zheng return -ENOMEM; 3538ad48fd75SYan, Zheng 3539459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3540459931ecSChris Mason path->slots[0]), item_size); 3541ad48fd75SYan, Zheng 3542459931ecSChris Mason slot = path->slots[0] + 1; 3543459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 3544459931ecSChris Mason if (slot != nritems) { 3545459931ecSChris Mason /* shift the items */ 3546459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 3547459931ecSChris Mason btrfs_item_nr_offset(slot), 3548459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3549459931ecSChris Mason } 3550459931ecSChris Mason 3551459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 3552459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3553459931ecSChris Mason 35543212fa14SJosef Bacik btrfs_set_item_offset(leaf, slot, orig_offset); 35553212fa14SJosef Bacik btrfs_set_item_size(leaf, slot, item_size - split_offset); 3556459931ecSChris Mason 35573212fa14SJosef Bacik btrfs_set_item_offset(leaf, orig_slot, 3558459931ecSChris Mason orig_offset + item_size - split_offset); 35593212fa14SJosef Bacik btrfs_set_item_size(leaf, orig_slot, split_offset); 3560459931ecSChris Mason 3561459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 3562459931ecSChris Mason 3563459931ecSChris Mason /* write the data for the start of the original item */ 3564459931ecSChris Mason write_extent_buffer(leaf, buf, 3565459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 3566459931ecSChris Mason split_offset); 3567459931ecSChris Mason 3568459931ecSChris Mason /* write the data for the new item */ 3569459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 3570459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 3571459931ecSChris Mason item_size - split_offset); 3572459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 3573459931ecSChris Mason 3574e902baacSDavid Sterba BUG_ON(btrfs_leaf_free_space(leaf) < 0); 3575459931ecSChris Mason kfree(buf); 3576ad48fd75SYan, Zheng return 0; 3577ad48fd75SYan, Zheng } 3578ad48fd75SYan, Zheng 3579ad48fd75SYan, Zheng /* 3580ad48fd75SYan, Zheng * This function splits a single item into two items, 3581ad48fd75SYan, Zheng * giving 'new_key' to the new item and splitting the 3582ad48fd75SYan, Zheng * old one at split_offset (from the start of the item). 3583ad48fd75SYan, Zheng * 3584ad48fd75SYan, Zheng * The path may be released by this operation. After 3585ad48fd75SYan, Zheng * the split, the path is pointing to the old item. The 3586ad48fd75SYan, Zheng * new item is going to be in the same node as the old one. 3587ad48fd75SYan, Zheng * 3588ad48fd75SYan, Zheng * Note, the item being split must be smaller enough to live alone on 3589ad48fd75SYan, Zheng * a tree block with room for one extra struct btrfs_item 3590ad48fd75SYan, Zheng * 3591ad48fd75SYan, Zheng * This allows us to split the item in place, keeping a lock on the 3592ad48fd75SYan, Zheng * leaf the entire time. 3593ad48fd75SYan, Zheng */ 3594ad48fd75SYan, Zheng int btrfs_split_item(struct btrfs_trans_handle *trans, 3595ad48fd75SYan, Zheng struct btrfs_root *root, 3596ad48fd75SYan, Zheng struct btrfs_path *path, 3597310712b2SOmar Sandoval const struct btrfs_key *new_key, 3598ad48fd75SYan, Zheng unsigned long split_offset) 3599ad48fd75SYan, Zheng { 3600ad48fd75SYan, Zheng int ret; 3601ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3602ad48fd75SYan, Zheng sizeof(struct btrfs_item)); 3603ad48fd75SYan, Zheng if (ret) 3604459931ecSChris Mason return ret; 3605ad48fd75SYan, Zheng 360625263cd7SDavid Sterba ret = split_item(path, new_key, split_offset); 3607ad48fd75SYan, Zheng return ret; 3608ad48fd75SYan, Zheng } 3609ad48fd75SYan, Zheng 3610ad48fd75SYan, Zheng /* 3611d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 3612d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 3613d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 3614d352ac68SChris Mason * the front. 3615d352ac68SChris Mason */ 361678ac4f9eSDavid Sterba void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end) 3617b18c6685SChris Mason { 3618b18c6685SChris Mason int slot; 36195f39d397SChris Mason struct extent_buffer *leaf; 3620b18c6685SChris Mason u32 nritems; 3621b18c6685SChris Mason unsigned int data_end; 3622b18c6685SChris Mason unsigned int old_data_start; 3623b18c6685SChris Mason unsigned int old_size; 3624b18c6685SChris Mason unsigned int size_diff; 3625b18c6685SChris Mason int i; 3626cfed81a0SChris Mason struct btrfs_map_token token; 3627cfed81a0SChris Mason 36285f39d397SChris Mason leaf = path->nodes[0]; 3629179e29e4SChris Mason slot = path->slots[0]; 3630179e29e4SChris Mason 36313212fa14SJosef Bacik old_size = btrfs_item_size(leaf, slot); 3632179e29e4SChris Mason if (old_size == new_size) 3633143bede5SJeff Mahoney return; 3634b18c6685SChris Mason 36355f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 36368f881e8cSDavid Sterba data_end = leaf_data_end(leaf); 3637b18c6685SChris Mason 36383212fa14SJosef Bacik old_data_start = btrfs_item_offset(leaf, slot); 3639179e29e4SChris Mason 3640b18c6685SChris Mason size_diff = old_size - new_size; 3641b18c6685SChris Mason 3642b18c6685SChris Mason BUG_ON(slot < 0); 3643b18c6685SChris Mason BUG_ON(slot >= nritems); 3644b18c6685SChris Mason 3645b18c6685SChris Mason /* 3646b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3647b18c6685SChris Mason */ 3648b18c6685SChris Mason /* first correct the data pointers */ 3649c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 3650b18c6685SChris Mason for (i = slot; i < nritems; i++) { 36515f39d397SChris Mason u32 ioff; 3652db94535dSChris Mason 36533212fa14SJosef Bacik ioff = btrfs_token_item_offset(&token, i); 36543212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, ioff + size_diff); 3655b18c6685SChris Mason } 3656db94535dSChris Mason 3657b18c6685SChris Mason /* shift the data */ 3658179e29e4SChris Mason if (from_end) { 36593d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 36603d9ec8c4SNikolay Borisov data_end + size_diff, BTRFS_LEAF_DATA_OFFSET + 3661b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 3662179e29e4SChris Mason } else { 3663179e29e4SChris Mason struct btrfs_disk_key disk_key; 3664179e29e4SChris Mason u64 offset; 3665179e29e4SChris Mason 3666179e29e4SChris Mason btrfs_item_key(leaf, &disk_key, slot); 3667179e29e4SChris Mason 3668179e29e4SChris Mason if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 3669179e29e4SChris Mason unsigned long ptr; 3670179e29e4SChris Mason struct btrfs_file_extent_item *fi; 3671179e29e4SChris Mason 3672179e29e4SChris Mason fi = btrfs_item_ptr(leaf, slot, 3673179e29e4SChris Mason struct btrfs_file_extent_item); 3674179e29e4SChris Mason fi = (struct btrfs_file_extent_item *)( 3675179e29e4SChris Mason (unsigned long)fi - size_diff); 3676179e29e4SChris Mason 3677179e29e4SChris Mason if (btrfs_file_extent_type(leaf, fi) == 3678179e29e4SChris Mason BTRFS_FILE_EXTENT_INLINE) { 3679179e29e4SChris Mason ptr = btrfs_item_ptr_offset(leaf, slot); 3680179e29e4SChris Mason memmove_extent_buffer(leaf, ptr, 3681179e29e4SChris Mason (unsigned long)fi, 36827ec20afbSDavid Sterba BTRFS_FILE_EXTENT_INLINE_DATA_START); 3683179e29e4SChris Mason } 3684179e29e4SChris Mason } 3685179e29e4SChris Mason 36863d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 36873d9ec8c4SNikolay Borisov data_end + size_diff, BTRFS_LEAF_DATA_OFFSET + 3688179e29e4SChris Mason data_end, old_data_start - data_end); 3689179e29e4SChris Mason 3690179e29e4SChris Mason offset = btrfs_disk_key_offset(&disk_key); 3691179e29e4SChris Mason btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 3692179e29e4SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3693179e29e4SChris Mason if (slot == 0) 3694b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 3695179e29e4SChris Mason } 36965f39d397SChris Mason 36973212fa14SJosef Bacik btrfs_set_item_size(leaf, slot, new_size); 36985f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3699b18c6685SChris Mason 3700e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < 0) { 3701a4f78750SDavid Sterba btrfs_print_leaf(leaf); 3702b18c6685SChris Mason BUG(); 37035f39d397SChris Mason } 3704b18c6685SChris Mason } 3705b18c6685SChris Mason 3706d352ac68SChris Mason /* 37078f69dbd2SStefan Behrens * make the item pointed to by the path bigger, data_size is the added size. 3708d352ac68SChris Mason */ 3709c71dd880SDavid Sterba void btrfs_extend_item(struct btrfs_path *path, u32 data_size) 37106567e837SChris Mason { 37116567e837SChris Mason int slot; 37125f39d397SChris Mason struct extent_buffer *leaf; 37136567e837SChris Mason u32 nritems; 37146567e837SChris Mason unsigned int data_end; 37156567e837SChris Mason unsigned int old_data; 37166567e837SChris Mason unsigned int old_size; 37176567e837SChris Mason int i; 3718cfed81a0SChris Mason struct btrfs_map_token token; 3719cfed81a0SChris Mason 37205f39d397SChris Mason leaf = path->nodes[0]; 37216567e837SChris Mason 37225f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 37238f881e8cSDavid Sterba data_end = leaf_data_end(leaf); 37246567e837SChris Mason 3725e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < data_size) { 3726a4f78750SDavid Sterba btrfs_print_leaf(leaf); 37276567e837SChris Mason BUG(); 37285f39d397SChris Mason } 37296567e837SChris Mason slot = path->slots[0]; 3730dc2e724eSJosef Bacik old_data = btrfs_item_data_end(leaf, slot); 37316567e837SChris Mason 37326567e837SChris Mason BUG_ON(slot < 0); 37333326d1b0SChris Mason if (slot >= nritems) { 3734a4f78750SDavid Sterba btrfs_print_leaf(leaf); 3735c71dd880SDavid Sterba btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", 3736d397712bSChris Mason slot, nritems); 3737290342f6SArnd Bergmann BUG(); 37383326d1b0SChris Mason } 37396567e837SChris Mason 37406567e837SChris Mason /* 37416567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 37426567e837SChris Mason */ 37436567e837SChris Mason /* first correct the data pointers */ 3744c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 37456567e837SChris Mason for (i = slot; i < nritems; i++) { 37465f39d397SChris Mason u32 ioff; 3747db94535dSChris Mason 37483212fa14SJosef Bacik ioff = btrfs_token_item_offset(&token, i); 37493212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, ioff - data_size); 37506567e837SChris Mason } 37515f39d397SChris Mason 37526567e837SChris Mason /* shift the data */ 37533d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 37543d9ec8c4SNikolay Borisov data_end - data_size, BTRFS_LEAF_DATA_OFFSET + 37556567e837SChris Mason data_end, old_data - data_end); 37565f39d397SChris Mason 37576567e837SChris Mason data_end = old_data; 37583212fa14SJosef Bacik old_size = btrfs_item_size(leaf, slot); 37593212fa14SJosef Bacik btrfs_set_item_size(leaf, slot, old_size + data_size); 37605f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 37616567e837SChris Mason 3762e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < 0) { 3763a4f78750SDavid Sterba btrfs_print_leaf(leaf); 37646567e837SChris Mason BUG(); 37655f39d397SChris Mason } 37666567e837SChris Mason } 37676567e837SChris Mason 3768da9ffb24SNikolay Borisov /** 3769da9ffb24SNikolay Borisov * setup_items_for_insert - Helper called before inserting one or more items 3770da9ffb24SNikolay Borisov * to a leaf. Main purpose is to save stack depth by doing the bulk of the work 3771da9ffb24SNikolay Borisov * in a function that doesn't call btrfs_search_slot 3772da9ffb24SNikolay Borisov * 3773da9ffb24SNikolay Borisov * @root: root we are inserting items to 3774da9ffb24SNikolay Borisov * @path: points to the leaf/slot where we are going to insert new items 3775b7ef5f3aSFilipe Manana * @batch: information about the batch of items to insert 377674123bd7SChris Mason */ 3777f0641656SFilipe Manana static void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path, 3778b7ef5f3aSFilipe Manana const struct btrfs_item_batch *batch) 3779be0e5c09SChris Mason { 37800b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 37819c58309dSChris Mason int i; 37827518a238SChris Mason u32 nritems; 3783be0e5c09SChris Mason unsigned int data_end; 3784e2fa7227SChris Mason struct btrfs_disk_key disk_key; 378544871b1bSChris Mason struct extent_buffer *leaf; 378644871b1bSChris Mason int slot; 3787cfed81a0SChris Mason struct btrfs_map_token token; 3788fc0d82e1SNikolay Borisov u32 total_size; 3789fc0d82e1SNikolay Borisov 3790b7ef5f3aSFilipe Manana /* 3791b7ef5f3aSFilipe Manana * Before anything else, update keys in the parent and other ancestors 3792b7ef5f3aSFilipe Manana * if needed, then release the write locks on them, so that other tasks 3793b7ef5f3aSFilipe Manana * can use them while we modify the leaf. 3794b7ef5f3aSFilipe Manana */ 379524cdc847SFilipe Manana if (path->slots[0] == 0) { 3796b7ef5f3aSFilipe Manana btrfs_cpu_key_to_disk(&disk_key, &batch->keys[0]); 3797b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 379824cdc847SFilipe Manana } 379924cdc847SFilipe Manana btrfs_unlock_up_safe(path, 1); 380024cdc847SFilipe Manana 38015f39d397SChris Mason leaf = path->nodes[0]; 380244871b1bSChris Mason slot = path->slots[0]; 380374123bd7SChris Mason 38045f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 38058f881e8cSDavid Sterba data_end = leaf_data_end(leaf); 3806b7ef5f3aSFilipe Manana total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item)); 3807eb60ceacSChris Mason 3808e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < total_size) { 3809a4f78750SDavid Sterba btrfs_print_leaf(leaf); 38100b246afaSJeff Mahoney btrfs_crit(fs_info, "not enough freespace need %u have %d", 3811e902baacSDavid Sterba total_size, btrfs_leaf_free_space(leaf)); 3812be0e5c09SChris Mason BUG(); 3813d4dbff95SChris Mason } 38145f39d397SChris Mason 3815c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 3816be0e5c09SChris Mason if (slot != nritems) { 3817dc2e724eSJosef Bacik unsigned int old_data = btrfs_item_data_end(leaf, slot); 3818be0e5c09SChris Mason 38195f39d397SChris Mason if (old_data < data_end) { 3820a4f78750SDavid Sterba btrfs_print_leaf(leaf); 38217269ddd2SNikolay Borisov btrfs_crit(fs_info, 38227269ddd2SNikolay Borisov "item at slot %d with data offset %u beyond data end of leaf %u", 38235f39d397SChris Mason slot, old_data, data_end); 3824290342f6SArnd Bergmann BUG(); 38255f39d397SChris Mason } 3826be0e5c09SChris Mason /* 3827be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3828be0e5c09SChris Mason */ 3829be0e5c09SChris Mason /* first correct the data pointers */ 38300783fcfcSChris Mason for (i = slot; i < nritems; i++) { 38315f39d397SChris Mason u32 ioff; 3832db94535dSChris Mason 38333212fa14SJosef Bacik ioff = btrfs_token_item_offset(&token, i); 38343212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, 3835b7ef5f3aSFilipe Manana ioff - batch->total_data_size); 38360783fcfcSChris Mason } 3837be0e5c09SChris Mason /* shift the items */ 3838b7ef5f3aSFilipe Manana memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + batch->nr), 38395f39d397SChris Mason btrfs_item_nr_offset(slot), 38400783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3841be0e5c09SChris Mason 3842be0e5c09SChris Mason /* shift the data */ 38433d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 3844b7ef5f3aSFilipe Manana data_end - batch->total_data_size, 3845b7ef5f3aSFilipe Manana BTRFS_LEAF_DATA_OFFSET + data_end, 3846b7ef5f3aSFilipe Manana old_data - data_end); 3847be0e5c09SChris Mason data_end = old_data; 3848be0e5c09SChris Mason } 38495f39d397SChris Mason 385062e2749eSChris Mason /* setup the item for the new data */ 3851b7ef5f3aSFilipe Manana for (i = 0; i < batch->nr; i++) { 3852b7ef5f3aSFilipe Manana btrfs_cpu_key_to_disk(&disk_key, &batch->keys[i]); 38539c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 3854b7ef5f3aSFilipe Manana data_end -= batch->data_sizes[i]; 38553212fa14SJosef Bacik btrfs_set_token_item_offset(&token, slot + i, data_end); 38563212fa14SJosef Bacik btrfs_set_token_item_size(&token, slot + i, batch->data_sizes[i]); 38579c58309dSChris Mason } 385844871b1bSChris Mason 3859b7ef5f3aSFilipe Manana btrfs_set_header_nritems(leaf, nritems + batch->nr); 3860b9473439SChris Mason btrfs_mark_buffer_dirty(leaf); 3861aa5d6bedSChris Mason 3862e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < 0) { 3863a4f78750SDavid Sterba btrfs_print_leaf(leaf); 3864be0e5c09SChris Mason BUG(); 38655f39d397SChris Mason } 386644871b1bSChris Mason } 386744871b1bSChris Mason 386844871b1bSChris Mason /* 3869f0641656SFilipe Manana * Insert a new item into a leaf. 3870f0641656SFilipe Manana * 3871f0641656SFilipe Manana * @root: The root of the btree. 3872f0641656SFilipe Manana * @path: A path pointing to the target leaf and slot. 3873f0641656SFilipe Manana * @key: The key of the new item. 3874f0641656SFilipe Manana * @data_size: The size of the data associated with the new key. 3875f0641656SFilipe Manana */ 3876f0641656SFilipe Manana void btrfs_setup_item_for_insert(struct btrfs_root *root, 3877f0641656SFilipe Manana struct btrfs_path *path, 3878f0641656SFilipe Manana const struct btrfs_key *key, 3879f0641656SFilipe Manana u32 data_size) 3880f0641656SFilipe Manana { 3881f0641656SFilipe Manana struct btrfs_item_batch batch; 3882f0641656SFilipe Manana 3883f0641656SFilipe Manana batch.keys = key; 3884f0641656SFilipe Manana batch.data_sizes = &data_size; 3885f0641656SFilipe Manana batch.total_data_size = data_size; 3886f0641656SFilipe Manana batch.nr = 1; 3887f0641656SFilipe Manana 3888f0641656SFilipe Manana setup_items_for_insert(root, path, &batch); 3889f0641656SFilipe Manana } 3890f0641656SFilipe Manana 3891f0641656SFilipe Manana /* 389244871b1bSChris Mason * Given a key and some data, insert items into the tree. 389344871b1bSChris Mason * This does all the path init required, making room in the tree if needed. 389444871b1bSChris Mason */ 389544871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 389644871b1bSChris Mason struct btrfs_root *root, 389744871b1bSChris Mason struct btrfs_path *path, 3898b7ef5f3aSFilipe Manana const struct btrfs_item_batch *batch) 389944871b1bSChris Mason { 390044871b1bSChris Mason int ret = 0; 390144871b1bSChris Mason int slot; 3902b7ef5f3aSFilipe Manana u32 total_size; 390344871b1bSChris Mason 3904b7ef5f3aSFilipe Manana total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item)); 3905b7ef5f3aSFilipe Manana ret = btrfs_search_slot(trans, root, &batch->keys[0], path, total_size, 1); 390644871b1bSChris Mason if (ret == 0) 390744871b1bSChris Mason return -EEXIST; 390844871b1bSChris Mason if (ret < 0) 3909143bede5SJeff Mahoney return ret; 391044871b1bSChris Mason 391144871b1bSChris Mason slot = path->slots[0]; 391244871b1bSChris Mason BUG_ON(slot < 0); 391344871b1bSChris Mason 3914b7ef5f3aSFilipe Manana setup_items_for_insert(root, path, batch); 3915143bede5SJeff Mahoney return 0; 391662e2749eSChris Mason } 391762e2749eSChris Mason 391862e2749eSChris Mason /* 391962e2749eSChris Mason * Given a key and some data, insert an item into the tree. 392062e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 392162e2749eSChris Mason */ 3922310712b2SOmar Sandoval int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 3923310712b2SOmar Sandoval const struct btrfs_key *cpu_key, void *data, 3924310712b2SOmar Sandoval u32 data_size) 392562e2749eSChris Mason { 392662e2749eSChris Mason int ret = 0; 39272c90e5d6SChris Mason struct btrfs_path *path; 39285f39d397SChris Mason struct extent_buffer *leaf; 39295f39d397SChris Mason unsigned long ptr; 393062e2749eSChris Mason 39312c90e5d6SChris Mason path = btrfs_alloc_path(); 3932db5b493aSTsutomu Itoh if (!path) 3933db5b493aSTsutomu Itoh return -ENOMEM; 39342c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 393562e2749eSChris Mason if (!ret) { 39365f39d397SChris Mason leaf = path->nodes[0]; 39375f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 39385f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 39395f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 394062e2749eSChris Mason } 39412c90e5d6SChris Mason btrfs_free_path(path); 3942aa5d6bedSChris Mason return ret; 3943be0e5c09SChris Mason } 3944be0e5c09SChris Mason 394574123bd7SChris Mason /* 3946f0641656SFilipe Manana * This function duplicates an item, giving 'new_key' to the new item. 3947f0641656SFilipe Manana * It guarantees both items live in the same tree leaf and the new item is 3948f0641656SFilipe Manana * contiguous with the original item. 3949f0641656SFilipe Manana * 3950f0641656SFilipe Manana * This allows us to split a file extent in place, keeping a lock on the leaf 3951f0641656SFilipe Manana * the entire time. 3952f0641656SFilipe Manana */ 3953f0641656SFilipe Manana int btrfs_duplicate_item(struct btrfs_trans_handle *trans, 3954f0641656SFilipe Manana struct btrfs_root *root, 3955f0641656SFilipe Manana struct btrfs_path *path, 3956f0641656SFilipe Manana const struct btrfs_key *new_key) 3957f0641656SFilipe Manana { 3958f0641656SFilipe Manana struct extent_buffer *leaf; 3959f0641656SFilipe Manana int ret; 3960f0641656SFilipe Manana u32 item_size; 3961f0641656SFilipe Manana 3962f0641656SFilipe Manana leaf = path->nodes[0]; 39633212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 3964f0641656SFilipe Manana ret = setup_leaf_for_split(trans, root, path, 3965f0641656SFilipe Manana item_size + sizeof(struct btrfs_item)); 3966f0641656SFilipe Manana if (ret) 3967f0641656SFilipe Manana return ret; 3968f0641656SFilipe Manana 3969f0641656SFilipe Manana path->slots[0]++; 3970f0641656SFilipe Manana btrfs_setup_item_for_insert(root, path, new_key, item_size); 3971f0641656SFilipe Manana leaf = path->nodes[0]; 3972f0641656SFilipe Manana memcpy_extent_buffer(leaf, 3973f0641656SFilipe Manana btrfs_item_ptr_offset(leaf, path->slots[0]), 3974f0641656SFilipe Manana btrfs_item_ptr_offset(leaf, path->slots[0] - 1), 3975f0641656SFilipe Manana item_size); 3976f0641656SFilipe Manana return 0; 3977f0641656SFilipe Manana } 3978f0641656SFilipe Manana 3979f0641656SFilipe Manana /* 39805de08d7dSChris Mason * delete the pointer from a given node. 398174123bd7SChris Mason * 3982d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 3983d352ac68SChris Mason * empty a node. 398474123bd7SChris Mason */ 3985afe5fea7STsutomu Itoh static void del_ptr(struct btrfs_root *root, struct btrfs_path *path, 3986afe5fea7STsutomu Itoh int level, int slot) 3987be0e5c09SChris Mason { 39885f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 39897518a238SChris Mason u32 nritems; 3990f3ea38daSJan Schmidt int ret; 3991be0e5c09SChris Mason 39925f39d397SChris Mason nritems = btrfs_header_nritems(parent); 3993be0e5c09SChris Mason if (slot != nritems - 1) { 3994bf1d3425SDavid Sterba if (level) { 3995f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_move(parent, slot, 3996f3a84ccdSFilipe Manana slot + 1, nritems - slot - 1); 3997bf1d3425SDavid Sterba BUG_ON(ret < 0); 3998bf1d3425SDavid Sterba } 39995f39d397SChris Mason memmove_extent_buffer(parent, 40005f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 40015f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 4002d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 4003d6025579SChris Mason (nritems - slot - 1)); 400457ba86c0SChris Mason } else if (level) { 4005f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, slot, 4006f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REMOVE, GFP_NOFS); 400757ba86c0SChris Mason BUG_ON(ret < 0); 4008be0e5c09SChris Mason } 4009f3ea38daSJan Schmidt 40107518a238SChris Mason nritems--; 40115f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 40127518a238SChris Mason if (nritems == 0 && parent == root->node) { 40135f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 4014eb60ceacSChris Mason /* just turn the root into a leaf and break */ 40155f39d397SChris Mason btrfs_set_header_level(root->node, 0); 4016bb803951SChris Mason } else if (slot == 0) { 40175f39d397SChris Mason struct btrfs_disk_key disk_key; 40185f39d397SChris Mason 40195f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 4020b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, level + 1); 4021be0e5c09SChris Mason } 4022d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 4023be0e5c09SChris Mason } 4024be0e5c09SChris Mason 402574123bd7SChris Mason /* 4026323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 40275d4f98a2SYan Zheng * path->nodes[1]. 4028323ac95bSChris Mason * 4029323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 4030323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 4031323ac95bSChris Mason * 4032323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 4033323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 4034323ac95bSChris Mason */ 4035143bede5SJeff Mahoney static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans, 4036323ac95bSChris Mason struct btrfs_root *root, 40375d4f98a2SYan Zheng struct btrfs_path *path, 40385d4f98a2SYan Zheng struct extent_buffer *leaf) 4039323ac95bSChris Mason { 40405d4f98a2SYan Zheng WARN_ON(btrfs_header_generation(leaf) != trans->transid); 4041afe5fea7STsutomu Itoh del_ptr(root, path, 1, path->slots[1]); 4042323ac95bSChris Mason 40434d081c41SChris Mason /* 40444d081c41SChris Mason * btrfs_free_extent is expensive, we want to make sure we 40454d081c41SChris Mason * aren't holding any locks when we call it 40464d081c41SChris Mason */ 40474d081c41SChris Mason btrfs_unlock_up_safe(path, 0); 40484d081c41SChris Mason 4049f0486c68SYan, Zheng root_sub_used(root, leaf->len); 4050f0486c68SYan, Zheng 405167439dadSDavid Sterba atomic_inc(&leaf->refs); 40527a163608SFilipe Manana btrfs_free_tree_block(trans, btrfs_root_id(root), leaf, 0, 1); 40533083ee2eSJosef Bacik free_extent_buffer_stale(leaf); 4054323ac95bSChris Mason } 4055323ac95bSChris Mason /* 405674123bd7SChris Mason * delete the item at the leaf level in path. If that empties 405774123bd7SChris Mason * the leaf, remove it from the tree 405874123bd7SChris Mason */ 405985e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 406085e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 4061be0e5c09SChris Mason { 40620b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 40635f39d397SChris Mason struct extent_buffer *leaf; 4064ce0eac2aSAlexandru Moise u32 last_off; 4065ce0eac2aSAlexandru Moise u32 dsize = 0; 4066aa5d6bedSChris Mason int ret = 0; 4067aa5d6bedSChris Mason int wret; 406885e21bacSChris Mason int i; 40697518a238SChris Mason u32 nritems; 4070be0e5c09SChris Mason 40715f39d397SChris Mason leaf = path->nodes[0]; 40723212fa14SJosef Bacik last_off = btrfs_item_offset(leaf, slot + nr - 1); 407385e21bacSChris Mason 407485e21bacSChris Mason for (i = 0; i < nr; i++) 40753212fa14SJosef Bacik dsize += btrfs_item_size(leaf, slot + i); 407685e21bacSChris Mason 40775f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 4078be0e5c09SChris Mason 407985e21bacSChris Mason if (slot + nr != nritems) { 40808f881e8cSDavid Sterba int data_end = leaf_data_end(leaf); 4081c82f823cSDavid Sterba struct btrfs_map_token token; 40825f39d397SChris Mason 40833d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 4084d6025579SChris Mason data_end + dsize, 40853d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + data_end, 408685e21bacSChris Mason last_off - data_end); 40875f39d397SChris Mason 4088c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 408985e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 40905f39d397SChris Mason u32 ioff; 4091db94535dSChris Mason 40923212fa14SJosef Bacik ioff = btrfs_token_item_offset(&token, i); 40933212fa14SJosef Bacik btrfs_set_token_item_offset(&token, i, ioff + dsize); 40940783fcfcSChris Mason } 4095db94535dSChris Mason 40965f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 409785e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 40980783fcfcSChris Mason sizeof(struct btrfs_item) * 409985e21bacSChris Mason (nritems - slot - nr)); 4100be0e5c09SChris Mason } 410185e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 410285e21bacSChris Mason nritems -= nr; 41035f39d397SChris Mason 410474123bd7SChris Mason /* delete the leaf if we've emptied it */ 41057518a238SChris Mason if (nritems == 0) { 41065f39d397SChris Mason if (leaf == root->node) { 41075f39d397SChris Mason btrfs_set_header_level(leaf, 0); 41089a8dd150SChris Mason } else { 41096a884d7dSDavid Sterba btrfs_clean_tree_block(leaf); 4110143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 41119a8dd150SChris Mason } 4112be0e5c09SChris Mason } else { 41137518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 4114aa5d6bedSChris Mason if (slot == 0) { 41155f39d397SChris Mason struct btrfs_disk_key disk_key; 41165f39d397SChris Mason 41175f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 4118b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 4119aa5d6bedSChris Mason } 4120aa5d6bedSChris Mason 412174123bd7SChris Mason /* delete the leaf if it is mostly empty */ 41220b246afaSJeff Mahoney if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) { 4123be0e5c09SChris Mason /* push_leaf_left fixes the path. 4124be0e5c09SChris Mason * make sure the path still points to our leaf 4125be0e5c09SChris Mason * for possible call to del_ptr below 4126be0e5c09SChris Mason */ 41274920c9acSChris Mason slot = path->slots[1]; 412867439dadSDavid Sterba atomic_inc(&leaf->refs); 41295f39d397SChris Mason 413099d8f83cSChris Mason wret = push_leaf_left(trans, root, path, 1, 1, 413199d8f83cSChris Mason 1, (u32)-1); 413254aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 4133aa5d6bedSChris Mason ret = wret; 41345f39d397SChris Mason 41355f39d397SChris Mason if (path->nodes[0] == leaf && 41365f39d397SChris Mason btrfs_header_nritems(leaf)) { 413799d8f83cSChris Mason wret = push_leaf_right(trans, root, path, 1, 413899d8f83cSChris Mason 1, 1, 0); 413954aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 4140aa5d6bedSChris Mason ret = wret; 4141aa5d6bedSChris Mason } 41425f39d397SChris Mason 41435f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 4144323ac95bSChris Mason path->slots[1] = slot; 4145143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 41465f39d397SChris Mason free_extent_buffer(leaf); 4147143bede5SJeff Mahoney ret = 0; 41485de08d7dSChris Mason } else { 4149925baeddSChris Mason /* if we're still in the path, make sure 4150925baeddSChris Mason * we're dirty. Otherwise, one of the 4151925baeddSChris Mason * push_leaf functions must have already 4152925baeddSChris Mason * dirtied this buffer 4153925baeddSChris Mason */ 4154925baeddSChris Mason if (path->nodes[0] == leaf) 41555f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 41565f39d397SChris Mason free_extent_buffer(leaf); 4157be0e5c09SChris Mason } 4158d5719762SChris Mason } else { 41595f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 4160be0e5c09SChris Mason } 41619a8dd150SChris Mason } 4162aa5d6bedSChris Mason return ret; 41639a8dd150SChris Mason } 41649a8dd150SChris Mason 416597571fd0SChris Mason /* 4166925baeddSChris Mason * search the tree again to find a leaf with lesser keys 41677bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 41687bb86316SChris Mason * returns < 0 on io errors. 4169d352ac68SChris Mason * 4170d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 4171d352ac68SChris Mason * time you call it. 41727bb86316SChris Mason */ 417316e7549fSJosef Bacik int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 41747bb86316SChris Mason { 4175925baeddSChris Mason struct btrfs_key key; 4176925baeddSChris Mason struct btrfs_disk_key found_key; 4177925baeddSChris Mason int ret; 41787bb86316SChris Mason 4179925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 4180925baeddSChris Mason 4181e8b0d724SFilipe David Borba Manana if (key.offset > 0) { 4182925baeddSChris Mason key.offset--; 4183e8b0d724SFilipe David Borba Manana } else if (key.type > 0) { 4184925baeddSChris Mason key.type--; 4185e8b0d724SFilipe David Borba Manana key.offset = (u64)-1; 4186e8b0d724SFilipe David Borba Manana } else if (key.objectid > 0) { 4187925baeddSChris Mason key.objectid--; 4188e8b0d724SFilipe David Borba Manana key.type = (u8)-1; 4189e8b0d724SFilipe David Borba Manana key.offset = (u64)-1; 4190e8b0d724SFilipe David Borba Manana } else { 41917bb86316SChris Mason return 1; 4192e8b0d724SFilipe David Borba Manana } 41937bb86316SChris Mason 4194b3b4aa74SDavid Sterba btrfs_release_path(path); 4195925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4196925baeddSChris Mason if (ret < 0) 4197925baeddSChris Mason return ret; 4198925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 4199925baeddSChris Mason ret = comp_keys(&found_key, &key); 4200337c6f68SFilipe Manana /* 4201337c6f68SFilipe Manana * We might have had an item with the previous key in the tree right 4202337c6f68SFilipe Manana * before we released our path. And after we released our path, that 4203337c6f68SFilipe Manana * item might have been pushed to the first slot (0) of the leaf we 4204337c6f68SFilipe Manana * were holding due to a tree balance. Alternatively, an item with the 4205337c6f68SFilipe Manana * previous key can exist as the only element of a leaf (big fat item). 4206337c6f68SFilipe Manana * Therefore account for these 2 cases, so that our callers (like 4207337c6f68SFilipe Manana * btrfs_previous_item) don't miss an existing item with a key matching 4208337c6f68SFilipe Manana * the previous key we computed above. 4209337c6f68SFilipe Manana */ 4210337c6f68SFilipe Manana if (ret <= 0) 42117bb86316SChris Mason return 0; 4212925baeddSChris Mason return 1; 42137bb86316SChris Mason } 42147bb86316SChris Mason 42153f157a2fSChris Mason /* 42163f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 4217de78b51aSEric Sandeen * for nodes or leaves that are have a minimum transaction id. 4218de78b51aSEric Sandeen * This is used by the btree defrag code, and tree logging 42193f157a2fSChris Mason * 42203f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 42213f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 42223f157a2fSChris Mason * key and get a writable path. 42233f157a2fSChris Mason * 42243f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 42253f157a2fSChris Mason * of the tree. 42263f157a2fSChris Mason * 4227d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 4228d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 4229d352ac68SChris Mason * skipped over (without reading them). 4230d352ac68SChris Mason * 42313f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 42323f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 42333f157a2fSChris Mason */ 42343f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 4235de78b51aSEric Sandeen struct btrfs_path *path, 42363f157a2fSChris Mason u64 min_trans) 42373f157a2fSChris Mason { 42383f157a2fSChris Mason struct extent_buffer *cur; 42393f157a2fSChris Mason struct btrfs_key found_key; 42403f157a2fSChris Mason int slot; 42419652480bSYan int sret; 42423f157a2fSChris Mason u32 nritems; 42433f157a2fSChris Mason int level; 42443f157a2fSChris Mason int ret = 1; 4245f98de9b9SFilipe Manana int keep_locks = path->keep_locks; 42463f157a2fSChris Mason 4247f98de9b9SFilipe Manana path->keep_locks = 1; 42483f157a2fSChris Mason again: 4249bd681513SChris Mason cur = btrfs_read_lock_root_node(root); 42503f157a2fSChris Mason level = btrfs_header_level(cur); 4251e02119d5SChris Mason WARN_ON(path->nodes[level]); 42523f157a2fSChris Mason path->nodes[level] = cur; 4253bd681513SChris Mason path->locks[level] = BTRFS_READ_LOCK; 42543f157a2fSChris Mason 42553f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 42563f157a2fSChris Mason ret = 1; 42573f157a2fSChris Mason goto out; 42583f157a2fSChris Mason } 42593f157a2fSChris Mason while (1) { 42603f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 42613f157a2fSChris Mason level = btrfs_header_level(cur); 4262e3b83361SQu Wenruo sret = btrfs_bin_search(cur, min_key, &slot); 4263cbca7d59SFilipe Manana if (sret < 0) { 4264cbca7d59SFilipe Manana ret = sret; 4265cbca7d59SFilipe Manana goto out; 4266cbca7d59SFilipe Manana } 42673f157a2fSChris Mason 4268323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 4269323ac95bSChris Mason if (level == path->lowest_level) { 4270e02119d5SChris Mason if (slot >= nritems) 4271e02119d5SChris Mason goto find_next_key; 42723f157a2fSChris Mason ret = 0; 42733f157a2fSChris Mason path->slots[level] = slot; 42743f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 42753f157a2fSChris Mason goto out; 42763f157a2fSChris Mason } 42779652480bSYan if (sret && slot > 0) 42789652480bSYan slot--; 42793f157a2fSChris Mason /* 4280de78b51aSEric Sandeen * check this node pointer against the min_trans parameters. 4281260db43cSRandy Dunlap * If it is too old, skip to the next one. 42823f157a2fSChris Mason */ 42833f157a2fSChris Mason while (slot < nritems) { 42843f157a2fSChris Mason u64 gen; 4285e02119d5SChris Mason 42863f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 42873f157a2fSChris Mason if (gen < min_trans) { 42883f157a2fSChris Mason slot++; 42893f157a2fSChris Mason continue; 42903f157a2fSChris Mason } 42913f157a2fSChris Mason break; 42923f157a2fSChris Mason } 4293e02119d5SChris Mason find_next_key: 42943f157a2fSChris Mason /* 42953f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 42963f157a2fSChris Mason * and find another one 42973f157a2fSChris Mason */ 42983f157a2fSChris Mason if (slot >= nritems) { 4299e02119d5SChris Mason path->slots[level] = slot; 4300e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 4301de78b51aSEric Sandeen min_trans); 4302e02119d5SChris Mason if (sret == 0) { 4303b3b4aa74SDavid Sterba btrfs_release_path(path); 43043f157a2fSChris Mason goto again; 43053f157a2fSChris Mason } else { 43063f157a2fSChris Mason goto out; 43073f157a2fSChris Mason } 43083f157a2fSChris Mason } 43093f157a2fSChris Mason /* save our key for returning back */ 43103f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 43113f157a2fSChris Mason path->slots[level] = slot; 43123f157a2fSChris Mason if (level == path->lowest_level) { 43133f157a2fSChris Mason ret = 0; 43143f157a2fSChris Mason goto out; 43153f157a2fSChris Mason } 43164b231ae4SDavid Sterba cur = btrfs_read_node_slot(cur, slot); 4317fb770ae4SLiu Bo if (IS_ERR(cur)) { 4318fb770ae4SLiu Bo ret = PTR_ERR(cur); 4319fb770ae4SLiu Bo goto out; 4320fb770ae4SLiu Bo } 43213f157a2fSChris Mason 4322bd681513SChris Mason btrfs_tree_read_lock(cur); 4323b4ce94deSChris Mason 4324bd681513SChris Mason path->locks[level - 1] = BTRFS_READ_LOCK; 43253f157a2fSChris Mason path->nodes[level - 1] = cur; 4326f7c79f30SChris Mason unlock_up(path, level, 1, 0, NULL); 43273f157a2fSChris Mason } 43283f157a2fSChris Mason out: 4329f98de9b9SFilipe Manana path->keep_locks = keep_locks; 4330f98de9b9SFilipe Manana if (ret == 0) { 4331f98de9b9SFilipe Manana btrfs_unlock_up_safe(path, path->lowest_level + 1); 4332f98de9b9SFilipe Manana memcpy(min_key, &found_key, sizeof(found_key)); 4333f98de9b9SFilipe Manana } 43343f157a2fSChris Mason return ret; 43353f157a2fSChris Mason } 43363f157a2fSChris Mason 43373f157a2fSChris Mason /* 43383f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 43393f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 4340de78b51aSEric Sandeen * tree based on the current path and the min_trans parameters. 43413f157a2fSChris Mason * 43423f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 43433f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 43443f157a2fSChris Mason * 43453f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 43463f157a2fSChris Mason * calling this function. 43473f157a2fSChris Mason */ 4348e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 4349de78b51aSEric Sandeen struct btrfs_key *key, int level, u64 min_trans) 4350e7a84565SChris Mason { 4351e7a84565SChris Mason int slot; 4352e7a84565SChris Mason struct extent_buffer *c; 4353e7a84565SChris Mason 43546a9fb468SJosef Bacik WARN_ON(!path->keep_locks && !path->skip_locking); 4355e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 4356e7a84565SChris Mason if (!path->nodes[level]) 4357e7a84565SChris Mason return 1; 4358e7a84565SChris Mason 4359e7a84565SChris Mason slot = path->slots[level] + 1; 4360e7a84565SChris Mason c = path->nodes[level]; 43613f157a2fSChris Mason next: 4362e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 436333c66f43SYan Zheng int ret; 436433c66f43SYan Zheng int orig_lowest; 436533c66f43SYan Zheng struct btrfs_key cur_key; 436633c66f43SYan Zheng if (level + 1 >= BTRFS_MAX_LEVEL || 436733c66f43SYan Zheng !path->nodes[level + 1]) 4368e7a84565SChris Mason return 1; 436933c66f43SYan Zheng 43706a9fb468SJosef Bacik if (path->locks[level + 1] || path->skip_locking) { 437133c66f43SYan Zheng level++; 4372e7a84565SChris Mason continue; 4373e7a84565SChris Mason } 437433c66f43SYan Zheng 437533c66f43SYan Zheng slot = btrfs_header_nritems(c) - 1; 437633c66f43SYan Zheng if (level == 0) 437733c66f43SYan Zheng btrfs_item_key_to_cpu(c, &cur_key, slot); 437833c66f43SYan Zheng else 437933c66f43SYan Zheng btrfs_node_key_to_cpu(c, &cur_key, slot); 438033c66f43SYan Zheng 438133c66f43SYan Zheng orig_lowest = path->lowest_level; 4382b3b4aa74SDavid Sterba btrfs_release_path(path); 438333c66f43SYan Zheng path->lowest_level = level; 438433c66f43SYan Zheng ret = btrfs_search_slot(NULL, root, &cur_key, path, 438533c66f43SYan Zheng 0, 0); 438633c66f43SYan Zheng path->lowest_level = orig_lowest; 438733c66f43SYan Zheng if (ret < 0) 438833c66f43SYan Zheng return ret; 438933c66f43SYan Zheng 439033c66f43SYan Zheng c = path->nodes[level]; 439133c66f43SYan Zheng slot = path->slots[level]; 439233c66f43SYan Zheng if (ret == 0) 439333c66f43SYan Zheng slot++; 439433c66f43SYan Zheng goto next; 439533c66f43SYan Zheng } 439633c66f43SYan Zheng 4397e7a84565SChris Mason if (level == 0) 4398e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 43993f157a2fSChris Mason else { 44003f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 44013f157a2fSChris Mason 44023f157a2fSChris Mason if (gen < min_trans) { 44033f157a2fSChris Mason slot++; 44043f157a2fSChris Mason goto next; 44053f157a2fSChris Mason } 4406e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 44073f157a2fSChris Mason } 4408e7a84565SChris Mason return 0; 4409e7a84565SChris Mason } 4410e7a84565SChris Mason return 1; 4411e7a84565SChris Mason } 4412e7a84565SChris Mason 44133d7806ecSJan Schmidt int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path, 44143d7806ecSJan Schmidt u64 time_seq) 44153d7806ecSJan Schmidt { 4416d97e63b6SChris Mason int slot; 44178e73f275SChris Mason int level; 44185f39d397SChris Mason struct extent_buffer *c; 44198e73f275SChris Mason struct extent_buffer *next; 4420d96b3424SFilipe Manana struct btrfs_fs_info *fs_info = root->fs_info; 4421925baeddSChris Mason struct btrfs_key key; 4422d96b3424SFilipe Manana bool need_commit_sem = false; 4423925baeddSChris Mason u32 nritems; 4424925baeddSChris Mason int ret; 44250e46318dSJosef Bacik int i; 4426925baeddSChris Mason 4427925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4428d397712bSChris Mason if (nritems == 0) 4429925baeddSChris Mason return 1; 4430925baeddSChris Mason 44318e73f275SChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 44328e73f275SChris Mason again: 44338e73f275SChris Mason level = 1; 44348e73f275SChris Mason next = NULL; 4435b3b4aa74SDavid Sterba btrfs_release_path(path); 44368e73f275SChris Mason 4437a2135011SChris Mason path->keep_locks = 1; 44388e73f275SChris Mason 4439d96b3424SFilipe Manana if (time_seq) { 44403d7806ecSJan Schmidt ret = btrfs_search_old_slot(root, &key, path, time_seq); 4441d96b3424SFilipe Manana } else { 4442d96b3424SFilipe Manana if (path->need_commit_sem) { 4443d96b3424SFilipe Manana path->need_commit_sem = 0; 4444d96b3424SFilipe Manana need_commit_sem = true; 4445d96b3424SFilipe Manana down_read(&fs_info->commit_root_sem); 4446d96b3424SFilipe Manana } 4447925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4448d96b3424SFilipe Manana } 4449925baeddSChris Mason path->keep_locks = 0; 4450925baeddSChris Mason 4451925baeddSChris Mason if (ret < 0) 4452d96b3424SFilipe Manana goto done; 4453925baeddSChris Mason 4454a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4455168fd7d2SChris Mason /* 4456168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 4457168fd7d2SChris Mason * could have added more items next to the key that used to be 4458168fd7d2SChris Mason * at the very end of the block. So, check again here and 4459168fd7d2SChris Mason * advance the path if there are now more items available. 4460168fd7d2SChris Mason */ 4461a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 4462e457afecSYan Zheng if (ret == 0) 4463168fd7d2SChris Mason path->slots[0]++; 44648e73f275SChris Mason ret = 0; 4465925baeddSChris Mason goto done; 4466925baeddSChris Mason } 44670b43e04fSLiu Bo /* 44680b43e04fSLiu Bo * So the above check misses one case: 44690b43e04fSLiu Bo * - after releasing the path above, someone has removed the item that 44700b43e04fSLiu Bo * used to be at the very end of the block, and balance between leafs 44710b43e04fSLiu Bo * gets another one with bigger key.offset to replace it. 44720b43e04fSLiu Bo * 44730b43e04fSLiu Bo * This one should be returned as well, or we can get leaf corruption 44740b43e04fSLiu Bo * later(esp. in __btrfs_drop_extents()). 44750b43e04fSLiu Bo * 44760b43e04fSLiu Bo * And a bit more explanation about this check, 44770b43e04fSLiu Bo * with ret > 0, the key isn't found, the path points to the slot 44780b43e04fSLiu Bo * where it should be inserted, so the path->slots[0] item must be the 44790b43e04fSLiu Bo * bigger one. 44800b43e04fSLiu Bo */ 44810b43e04fSLiu Bo if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) { 44820b43e04fSLiu Bo ret = 0; 44830b43e04fSLiu Bo goto done; 44840b43e04fSLiu Bo } 4485d97e63b6SChris Mason 4486234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 44878e73f275SChris Mason if (!path->nodes[level]) { 44888e73f275SChris Mason ret = 1; 44898e73f275SChris Mason goto done; 44908e73f275SChris Mason } 44915f39d397SChris Mason 4492d97e63b6SChris Mason slot = path->slots[level] + 1; 4493d97e63b6SChris Mason c = path->nodes[level]; 44945f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 4495d97e63b6SChris Mason level++; 44968e73f275SChris Mason if (level == BTRFS_MAX_LEVEL) { 44978e73f275SChris Mason ret = 1; 44988e73f275SChris Mason goto done; 44998e73f275SChris Mason } 4500d97e63b6SChris Mason continue; 4501d97e63b6SChris Mason } 45025f39d397SChris Mason 45030e46318dSJosef Bacik 45040e46318dSJosef Bacik /* 45050e46318dSJosef Bacik * Our current level is where we're going to start from, and to 45060e46318dSJosef Bacik * make sure lockdep doesn't complain we need to drop our locks 45070e46318dSJosef Bacik * and nodes from 0 to our current level. 45080e46318dSJosef Bacik */ 45090e46318dSJosef Bacik for (i = 0; i < level; i++) { 45100e46318dSJosef Bacik if (path->locks[level]) { 45110e46318dSJosef Bacik btrfs_tree_read_unlock(path->nodes[i]); 45120e46318dSJosef Bacik path->locks[i] = 0; 45130e46318dSJosef Bacik } 45140e46318dSJosef Bacik free_extent_buffer(path->nodes[i]); 45150e46318dSJosef Bacik path->nodes[i] = NULL; 4516925baeddSChris Mason } 45175f39d397SChris Mason 45188e73f275SChris Mason next = c; 4519d07b8528SLiu Bo ret = read_block_for_search(root, path, &next, level, 4520cda79c54SDavid Sterba slot, &key); 45218e73f275SChris Mason if (ret == -EAGAIN) 45228e73f275SChris Mason goto again; 45235f39d397SChris Mason 452476a05b35SChris Mason if (ret < 0) { 4525b3b4aa74SDavid Sterba btrfs_release_path(path); 452676a05b35SChris Mason goto done; 452776a05b35SChris Mason } 452876a05b35SChris Mason 45295cd57b2cSChris Mason if (!path->skip_locking) { 4530bd681513SChris Mason ret = btrfs_try_tree_read_lock(next); 4531d42244a0SJan Schmidt if (!ret && time_seq) { 4532d42244a0SJan Schmidt /* 4533d42244a0SJan Schmidt * If we don't get the lock, we may be racing 4534d42244a0SJan Schmidt * with push_leaf_left, holding that lock while 4535d42244a0SJan Schmidt * itself waiting for the leaf we've currently 4536d42244a0SJan Schmidt * locked. To solve this situation, we give up 4537d42244a0SJan Schmidt * on our lock and cycle. 4538d42244a0SJan Schmidt */ 4539cf538830SJan Schmidt free_extent_buffer(next); 4540d42244a0SJan Schmidt btrfs_release_path(path); 4541d42244a0SJan Schmidt cond_resched(); 4542d42244a0SJan Schmidt goto again; 4543d42244a0SJan Schmidt } 45440e46318dSJosef Bacik if (!ret) 45450e46318dSJosef Bacik btrfs_tree_read_lock(next); 4546bd681513SChris Mason } 4547d97e63b6SChris Mason break; 4548d97e63b6SChris Mason } 4549d97e63b6SChris Mason path->slots[level] = slot; 4550d97e63b6SChris Mason while (1) { 4551d97e63b6SChris Mason level--; 4552d97e63b6SChris Mason path->nodes[level] = next; 4553d97e63b6SChris Mason path->slots[level] = 0; 4554a74a4b97SChris Mason if (!path->skip_locking) 4555ffeb03cfSJosef Bacik path->locks[level] = BTRFS_READ_LOCK; 4556d97e63b6SChris Mason if (!level) 4557d97e63b6SChris Mason break; 4558b4ce94deSChris Mason 4559d07b8528SLiu Bo ret = read_block_for_search(root, path, &next, level, 4560cda79c54SDavid Sterba 0, &key); 45618e73f275SChris Mason if (ret == -EAGAIN) 45628e73f275SChris Mason goto again; 45638e73f275SChris Mason 456476a05b35SChris Mason if (ret < 0) { 4565b3b4aa74SDavid Sterba btrfs_release_path(path); 456676a05b35SChris Mason goto done; 456776a05b35SChris Mason } 456876a05b35SChris Mason 4569ffeb03cfSJosef Bacik if (!path->skip_locking) 45700e46318dSJosef Bacik btrfs_tree_read_lock(next); 4571d97e63b6SChris Mason } 45728e73f275SChris Mason ret = 0; 4573925baeddSChris Mason done: 4574f7c79f30SChris Mason unlock_up(path, 0, 1, 0, NULL); 4575d96b3424SFilipe Manana if (need_commit_sem) { 4576d96b3424SFilipe Manana int ret2; 4577d96b3424SFilipe Manana 4578d96b3424SFilipe Manana path->need_commit_sem = 1; 4579d96b3424SFilipe Manana ret2 = finish_need_commit_sem_search(path); 4580d96b3424SFilipe Manana up_read(&fs_info->commit_root_sem); 4581d96b3424SFilipe Manana if (ret2) 4582d96b3424SFilipe Manana ret = ret2; 4583d96b3424SFilipe Manana } 45848e73f275SChris Mason 45858e73f275SChris Mason return ret; 4586d97e63b6SChris Mason } 45870b86a832SChris Mason 45883f157a2fSChris Mason /* 45893f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 45903f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 45913f157a2fSChris Mason * 45923f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 45933f157a2fSChris Mason */ 45940b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 45950b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 45960b86a832SChris Mason int type) 45970b86a832SChris Mason { 45980b86a832SChris Mason struct btrfs_key found_key; 45990b86a832SChris Mason struct extent_buffer *leaf; 4600e02119d5SChris Mason u32 nritems; 46010b86a832SChris Mason int ret; 46020b86a832SChris Mason 46030b86a832SChris Mason while (1) { 46040b86a832SChris Mason if (path->slots[0] == 0) { 46050b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 46060b86a832SChris Mason if (ret != 0) 46070b86a832SChris Mason return ret; 46080b86a832SChris Mason } else { 46090b86a832SChris Mason path->slots[0]--; 46100b86a832SChris Mason } 46110b86a832SChris Mason leaf = path->nodes[0]; 4612e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 4613e02119d5SChris Mason if (nritems == 0) 4614e02119d5SChris Mason return 1; 4615e02119d5SChris Mason if (path->slots[0] == nritems) 4616e02119d5SChris Mason path->slots[0]--; 4617e02119d5SChris Mason 46180b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4619e02119d5SChris Mason if (found_key.objectid < min_objectid) 4620e02119d5SChris Mason break; 46210a4eefbbSYan Zheng if (found_key.type == type) 46220a4eefbbSYan Zheng return 0; 4623e02119d5SChris Mason if (found_key.objectid == min_objectid && 4624e02119d5SChris Mason found_key.type < type) 4625e02119d5SChris Mason break; 46260b86a832SChris Mason } 46270b86a832SChris Mason return 1; 46280b86a832SChris Mason } 4629ade2e0b3SWang Shilong 4630ade2e0b3SWang Shilong /* 4631ade2e0b3SWang Shilong * search in extent tree to find a previous Metadata/Data extent item with 4632ade2e0b3SWang Shilong * min objecitd. 4633ade2e0b3SWang Shilong * 4634ade2e0b3SWang Shilong * returns 0 if something is found, 1 if nothing was found and < 0 on error 4635ade2e0b3SWang Shilong */ 4636ade2e0b3SWang Shilong int btrfs_previous_extent_item(struct btrfs_root *root, 4637ade2e0b3SWang Shilong struct btrfs_path *path, u64 min_objectid) 4638ade2e0b3SWang Shilong { 4639ade2e0b3SWang Shilong struct btrfs_key found_key; 4640ade2e0b3SWang Shilong struct extent_buffer *leaf; 4641ade2e0b3SWang Shilong u32 nritems; 4642ade2e0b3SWang Shilong int ret; 4643ade2e0b3SWang Shilong 4644ade2e0b3SWang Shilong while (1) { 4645ade2e0b3SWang Shilong if (path->slots[0] == 0) { 4646ade2e0b3SWang Shilong ret = btrfs_prev_leaf(root, path); 4647ade2e0b3SWang Shilong if (ret != 0) 4648ade2e0b3SWang Shilong return ret; 4649ade2e0b3SWang Shilong } else { 4650ade2e0b3SWang Shilong path->slots[0]--; 4651ade2e0b3SWang Shilong } 4652ade2e0b3SWang Shilong leaf = path->nodes[0]; 4653ade2e0b3SWang Shilong nritems = btrfs_header_nritems(leaf); 4654ade2e0b3SWang Shilong if (nritems == 0) 4655ade2e0b3SWang Shilong return 1; 4656ade2e0b3SWang Shilong if (path->slots[0] == nritems) 4657ade2e0b3SWang Shilong path->slots[0]--; 4658ade2e0b3SWang Shilong 4659ade2e0b3SWang Shilong btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4660ade2e0b3SWang Shilong if (found_key.objectid < min_objectid) 4661ade2e0b3SWang Shilong break; 4662ade2e0b3SWang Shilong if (found_key.type == BTRFS_EXTENT_ITEM_KEY || 4663ade2e0b3SWang Shilong found_key.type == BTRFS_METADATA_ITEM_KEY) 4664ade2e0b3SWang Shilong return 0; 4665ade2e0b3SWang Shilong if (found_key.objectid == min_objectid && 4666ade2e0b3SWang Shilong found_key.type < BTRFS_EXTENT_ITEM_KEY) 4667ade2e0b3SWang Shilong break; 4668ade2e0b3SWang Shilong } 4669ade2e0b3SWang Shilong return 1; 4670ade2e0b3SWang Shilong } 4671