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> 10eb60ceacSChris Mason #include "ctree.h" 11eb60ceacSChris Mason #include "disk-io.h" 127f5c1516SChris Mason #include "transaction.h" 135f39d397SChris Mason #include "print-tree.h" 14925baeddSChris Mason #include "locking.h" 15de37aa51SNikolay Borisov #include "volumes.h" 16f616f5cdSQu Wenruo #include "qgroup.h" 17f3a84ccdSFilipe Manana #include "tree-mod-log.h" 189a8dd150SChris Mason 19e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 20e089f05cSChris Mason *root, struct btrfs_path *path, int level); 21310712b2SOmar Sandoval static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root, 22310712b2SOmar Sandoval const struct btrfs_key *ins_key, struct btrfs_path *path, 23310712b2SOmar Sandoval int data_size, int extend); 245f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 252ff7e61eSJeff Mahoney struct extent_buffer *dst, 26971a1f66SChris Mason struct extent_buffer *src, int empty); 275f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 285f39d397SChris Mason struct extent_buffer *dst_buf, 295f39d397SChris Mason struct extent_buffer *src_buf); 30afe5fea7STsutomu Itoh static void del_ptr(struct btrfs_root *root, struct btrfs_path *path, 31afe5fea7STsutomu Itoh int level, int slot); 32d97e63b6SChris Mason 33af024ed2SJohannes Thumshirn static const struct btrfs_csums { 34af024ed2SJohannes Thumshirn u16 size; 3559a0fcdbSDavid Sterba const char name[10]; 3659a0fcdbSDavid Sterba const char driver[12]; 37af024ed2SJohannes Thumshirn } btrfs_csums[] = { 38af024ed2SJohannes Thumshirn [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" }, 393951e7f0SJohannes Thumshirn [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" }, 403831bf00SJohannes Thumshirn [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" }, 41352ae07bSDavid Sterba [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b", 42352ae07bSDavid Sterba .driver = "blake2b-256" }, 43af024ed2SJohannes Thumshirn }; 44af024ed2SJohannes Thumshirn 45af024ed2SJohannes Thumshirn int btrfs_super_csum_size(const struct btrfs_super_block *s) 46af024ed2SJohannes Thumshirn { 47af024ed2SJohannes Thumshirn u16 t = btrfs_super_csum_type(s); 48af024ed2SJohannes Thumshirn /* 49af024ed2SJohannes Thumshirn * csum type is validated at mount time 50af024ed2SJohannes Thumshirn */ 51af024ed2SJohannes Thumshirn return btrfs_csums[t].size; 52af024ed2SJohannes Thumshirn } 53af024ed2SJohannes Thumshirn 54af024ed2SJohannes Thumshirn const char *btrfs_super_csum_name(u16 csum_type) 55af024ed2SJohannes Thumshirn { 56af024ed2SJohannes Thumshirn /* csum type is validated at mount time */ 57af024ed2SJohannes Thumshirn return btrfs_csums[csum_type].name; 58af024ed2SJohannes Thumshirn } 59af024ed2SJohannes Thumshirn 60b4e967beSDavid Sterba /* 61b4e967beSDavid Sterba * Return driver name if defined, otherwise the name that's also a valid driver 62b4e967beSDavid Sterba * name 63b4e967beSDavid Sterba */ 64b4e967beSDavid Sterba const char *btrfs_super_csum_driver(u16 csum_type) 65b4e967beSDavid Sterba { 66b4e967beSDavid Sterba /* csum type is validated at mount time */ 6759a0fcdbSDavid Sterba return btrfs_csums[csum_type].driver[0] ? 6859a0fcdbSDavid Sterba btrfs_csums[csum_type].driver : 69b4e967beSDavid Sterba btrfs_csums[csum_type].name; 70b4e967beSDavid Sterba } 71b4e967beSDavid Sterba 72604997b4SDavid Sterba size_t __attribute_const__ btrfs_get_num_csums(void) 73f7cea56cSDavid Sterba { 74f7cea56cSDavid Sterba return ARRAY_SIZE(btrfs_csums); 75f7cea56cSDavid Sterba } 76f7cea56cSDavid Sterba 772c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 782c90e5d6SChris Mason { 79e2c89907SMasahiro Yamada return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS); 802c90e5d6SChris Mason } 812c90e5d6SChris Mason 82d352ac68SChris Mason /* this also releases the path */ 832c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 842c90e5d6SChris Mason { 85ff175d57SJesper Juhl if (!p) 86ff175d57SJesper Juhl return; 87b3b4aa74SDavid Sterba btrfs_release_path(p); 882c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 892c90e5d6SChris Mason } 902c90e5d6SChris Mason 91d352ac68SChris Mason /* 92d352ac68SChris Mason * path release drops references on the extent buffers in the path 93d352ac68SChris Mason * and it drops any locks held by this path 94d352ac68SChris Mason * 95d352ac68SChris Mason * It is safe to call this on paths that no locks or extent buffers held. 96d352ac68SChris Mason */ 97b3b4aa74SDavid Sterba noinline void btrfs_release_path(struct btrfs_path *p) 98eb60ceacSChris Mason { 99eb60ceacSChris Mason int i; 100a2135011SChris Mason 101234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 1023f157a2fSChris Mason p->slots[i] = 0; 103eb60ceacSChris Mason if (!p->nodes[i]) 104925baeddSChris Mason continue; 105925baeddSChris Mason if (p->locks[i]) { 106bd681513SChris Mason btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]); 107925baeddSChris Mason p->locks[i] = 0; 108925baeddSChris Mason } 1095f39d397SChris Mason free_extent_buffer(p->nodes[i]); 1103f157a2fSChris Mason p->nodes[i] = NULL; 111eb60ceacSChris Mason } 112eb60ceacSChris Mason } 113eb60ceacSChris Mason 114d352ac68SChris Mason /* 115d352ac68SChris Mason * safely gets a reference on the root node of a tree. A lock 116d352ac68SChris Mason * is not taken, so a concurrent writer may put a different node 117d352ac68SChris Mason * at the root of the tree. See btrfs_lock_root_node for the 118d352ac68SChris Mason * looping required. 119d352ac68SChris Mason * 120d352ac68SChris Mason * The extent buffer returned by this has a reference taken, so 121d352ac68SChris Mason * it won't disappear. It may stop being the root of the tree 122d352ac68SChris Mason * at any time because there are no locks held. 123d352ac68SChris Mason */ 124925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root) 125925baeddSChris Mason { 126925baeddSChris Mason struct extent_buffer *eb; 127240f62c8SChris Mason 1283083ee2eSJosef Bacik while (1) { 129240f62c8SChris Mason rcu_read_lock(); 130240f62c8SChris Mason eb = rcu_dereference(root->node); 1313083ee2eSJosef Bacik 1323083ee2eSJosef Bacik /* 1333083ee2eSJosef Bacik * RCU really hurts here, we could free up the root node because 13401327610SNicholas D Steeves * it was COWed but we may not get the new root node yet so do 1353083ee2eSJosef Bacik * the inc_not_zero dance and if it doesn't work then 1363083ee2eSJosef Bacik * synchronize_rcu and try again. 1373083ee2eSJosef Bacik */ 1383083ee2eSJosef Bacik if (atomic_inc_not_zero(&eb->refs)) { 139240f62c8SChris Mason rcu_read_unlock(); 1403083ee2eSJosef Bacik break; 1413083ee2eSJosef Bacik } 1423083ee2eSJosef Bacik rcu_read_unlock(); 1433083ee2eSJosef Bacik synchronize_rcu(); 1443083ee2eSJosef Bacik } 145925baeddSChris Mason return eb; 146925baeddSChris Mason } 147925baeddSChris Mason 14892a7cc42SQu Wenruo /* 14992a7cc42SQu Wenruo * Cowonly root (not-shareable trees, everything not subvolume or reloc roots), 15092a7cc42SQu Wenruo * just get put onto a simple dirty list. Transaction walks this list to make 15192a7cc42SQu Wenruo * sure they get properly updated on disk. 152d352ac68SChris Mason */ 1530b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root) 1540b86a832SChris Mason { 1550b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 1560b246afaSJeff Mahoney 157e7070be1SJosef Bacik if (test_bit(BTRFS_ROOT_DIRTY, &root->state) || 158e7070be1SJosef Bacik !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state)) 159e7070be1SJosef Bacik return; 160e7070be1SJosef Bacik 1610b246afaSJeff Mahoney spin_lock(&fs_info->trans_lock); 162e7070be1SJosef Bacik if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) { 163e7070be1SJosef Bacik /* Want the extent tree to be the last on the list */ 1644fd786e6SMisono Tomohiro if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID) 165e7070be1SJosef Bacik list_move_tail(&root->dirty_list, 1660b246afaSJeff Mahoney &fs_info->dirty_cowonly_roots); 167e7070be1SJosef Bacik else 168e7070be1SJosef Bacik list_move(&root->dirty_list, 1690b246afaSJeff Mahoney &fs_info->dirty_cowonly_roots); 1700b86a832SChris Mason } 1710b246afaSJeff Mahoney spin_unlock(&fs_info->trans_lock); 1720b86a832SChris Mason } 1730b86a832SChris Mason 174d352ac68SChris Mason /* 175d352ac68SChris Mason * used by snapshot creation to make a copy of a root for a tree with 176d352ac68SChris Mason * a given objectid. The buffer with the new root node is returned in 177d352ac68SChris Mason * cow_ret, and this func returns zero on success or a negative error code. 178d352ac68SChris Mason */ 179be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans, 180be20aa9dSChris Mason struct btrfs_root *root, 181be20aa9dSChris Mason struct extent_buffer *buf, 182be20aa9dSChris Mason struct extent_buffer **cow_ret, u64 new_root_objectid) 183be20aa9dSChris Mason { 1840b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 185be20aa9dSChris Mason struct extent_buffer *cow; 186be20aa9dSChris Mason int ret = 0; 187be20aa9dSChris Mason int level; 1885d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 189be20aa9dSChris Mason 19092a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 1910b246afaSJeff Mahoney trans->transid != fs_info->running_transaction->transid); 19292a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 19327cdeb70SMiao Xie trans->transid != root->last_trans); 194be20aa9dSChris Mason 195be20aa9dSChris Mason level = btrfs_header_level(buf); 1965d4f98a2SYan Zheng if (level == 0) 1975d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 1985d4f98a2SYan Zheng else 1995d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 20031840ae1SZheng Yan 2014d75f8a9SDavid Sterba cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid, 202cf6f34aaSJosef Bacik &disk_key, level, buf->start, 0, 203cf6f34aaSJosef Bacik BTRFS_NESTING_NEW_ROOT); 2045d4f98a2SYan Zheng if (IS_ERR(cow)) 205be20aa9dSChris Mason return PTR_ERR(cow); 206be20aa9dSChris Mason 20758e8012cSDavid Sterba copy_extent_buffer_full(cow, buf); 208be20aa9dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 209be20aa9dSChris Mason btrfs_set_header_generation(cow, trans->transid); 2105d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 2115d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 2125d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 2135d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 2145d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 2155d4f98a2SYan Zheng else 216be20aa9dSChris Mason btrfs_set_header_owner(cow, new_root_objectid); 217be20aa9dSChris Mason 218de37aa51SNikolay Borisov write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid); 2192b82032cSYan Zheng 220be20aa9dSChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 2215d4f98a2SYan Zheng if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) 222e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 2235d4f98a2SYan Zheng else 224e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 0); 225867ed321SJosef Bacik if (ret) { 22672c9925fSFilipe Manana btrfs_tree_unlock(cow); 22772c9925fSFilipe Manana free_extent_buffer(cow); 228867ed321SJosef Bacik btrfs_abort_transaction(trans, ret); 229be20aa9dSChris Mason return ret; 230867ed321SJosef Bacik } 231be20aa9dSChris Mason 232be20aa9dSChris Mason btrfs_mark_buffer_dirty(cow); 233be20aa9dSChris Mason *cow_ret = cow; 234be20aa9dSChris Mason return 0; 235be20aa9dSChris Mason } 236be20aa9dSChris Mason 237d352ac68SChris Mason /* 2385d4f98a2SYan Zheng * check if the tree block can be shared by multiple trees 2395d4f98a2SYan Zheng */ 2405d4f98a2SYan Zheng int btrfs_block_can_be_shared(struct btrfs_root *root, 2415d4f98a2SYan Zheng struct extent_buffer *buf) 2425d4f98a2SYan Zheng { 2435d4f98a2SYan Zheng /* 24492a7cc42SQu Wenruo * Tree blocks not in shareable trees and tree roots are never shared. 24592a7cc42SQu Wenruo * If a block was allocated after the last snapshot and the block was 24692a7cc42SQu Wenruo * not allocated by tree relocation, we know the block is not shared. 2475d4f98a2SYan Zheng */ 24892a7cc42SQu Wenruo if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 2495d4f98a2SYan Zheng buf != root->node && buf != root->commit_root && 2505d4f98a2SYan Zheng (btrfs_header_generation(buf) <= 2515d4f98a2SYan Zheng btrfs_root_last_snapshot(&root->root_item) || 2525d4f98a2SYan Zheng btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))) 2535d4f98a2SYan Zheng return 1; 254a79865c6SNikolay Borisov 2555d4f98a2SYan Zheng return 0; 2565d4f98a2SYan Zheng } 2575d4f98a2SYan Zheng 2585d4f98a2SYan Zheng static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans, 2595d4f98a2SYan Zheng struct btrfs_root *root, 2605d4f98a2SYan Zheng struct extent_buffer *buf, 261f0486c68SYan, Zheng struct extent_buffer *cow, 262f0486c68SYan, Zheng int *last_ref) 2635d4f98a2SYan Zheng { 2640b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 2655d4f98a2SYan Zheng u64 refs; 2665d4f98a2SYan Zheng u64 owner; 2675d4f98a2SYan Zheng u64 flags; 2685d4f98a2SYan Zheng u64 new_flags = 0; 2695d4f98a2SYan Zheng int ret; 2705d4f98a2SYan Zheng 2715d4f98a2SYan Zheng /* 2725d4f98a2SYan Zheng * Backrefs update rules: 2735d4f98a2SYan Zheng * 2745d4f98a2SYan Zheng * Always use full backrefs for extent pointers in tree block 2755d4f98a2SYan Zheng * allocated by tree relocation. 2765d4f98a2SYan Zheng * 2775d4f98a2SYan Zheng * If a shared tree block is no longer referenced by its owner 2785d4f98a2SYan Zheng * tree (btrfs_header_owner(buf) == root->root_key.objectid), 2795d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 2805d4f98a2SYan Zheng * 2815d4f98a2SYan Zheng * If a tree block is been relocating 2825d4f98a2SYan Zheng * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID), 2835d4f98a2SYan Zheng * use full backrefs for extent pointers in tree block. 2845d4f98a2SYan Zheng * The reason for this is some operations (such as drop tree) 2855d4f98a2SYan Zheng * are only allowed for blocks use full backrefs. 2865d4f98a2SYan Zheng */ 2875d4f98a2SYan Zheng 2885d4f98a2SYan Zheng if (btrfs_block_can_be_shared(root, buf)) { 2892ff7e61eSJeff Mahoney ret = btrfs_lookup_extent_info(trans, fs_info, buf->start, 2903173a18fSJosef Bacik btrfs_header_level(buf), 1, 2913173a18fSJosef Bacik &refs, &flags); 292be1a5564SMark Fasheh if (ret) 293be1a5564SMark Fasheh return ret; 294e5df9573SMark Fasheh if (refs == 0) { 295e5df9573SMark Fasheh ret = -EROFS; 2960b246afaSJeff Mahoney btrfs_handle_fs_error(fs_info, ret, NULL); 297e5df9573SMark Fasheh return ret; 298e5df9573SMark Fasheh } 2995d4f98a2SYan Zheng } else { 3005d4f98a2SYan Zheng refs = 1; 3015d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 3025d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 3035d4f98a2SYan Zheng flags = BTRFS_BLOCK_FLAG_FULL_BACKREF; 3045d4f98a2SYan Zheng else 3055d4f98a2SYan Zheng flags = 0; 3065d4f98a2SYan Zheng } 3075d4f98a2SYan Zheng 3085d4f98a2SYan Zheng owner = btrfs_header_owner(buf); 3095d4f98a2SYan Zheng BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID && 3105d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)); 3115d4f98a2SYan Zheng 3125d4f98a2SYan Zheng if (refs > 1) { 3135d4f98a2SYan Zheng if ((owner == root->root_key.objectid || 3145d4f98a2SYan Zheng root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && 3155d4f98a2SYan Zheng !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) { 316e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, buf, 1); 317692826b2SJeff Mahoney if (ret) 318692826b2SJeff Mahoney return ret; 3195d4f98a2SYan Zheng 3205d4f98a2SYan Zheng if (root->root_key.objectid == 3215d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) { 322e339a6b0SJosef Bacik ret = btrfs_dec_ref(trans, root, buf, 0); 323692826b2SJeff Mahoney if (ret) 324692826b2SJeff Mahoney return ret; 325e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 326692826b2SJeff Mahoney if (ret) 327692826b2SJeff Mahoney return ret; 3285d4f98a2SYan Zheng } 3295d4f98a2SYan Zheng new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; 3305d4f98a2SYan Zheng } else { 3315d4f98a2SYan Zheng 3325d4f98a2SYan Zheng if (root->root_key.objectid == 3335d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 334e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 3355d4f98a2SYan Zheng else 336e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 0); 337692826b2SJeff Mahoney if (ret) 338692826b2SJeff Mahoney return ret; 3395d4f98a2SYan Zheng } 3405d4f98a2SYan Zheng if (new_flags != 0) { 341b1c79e09SJosef Bacik int level = btrfs_header_level(buf); 342b1c79e09SJosef Bacik 34342c9d0b5SDavid Sterba ret = btrfs_set_disk_extent_flags(trans, buf, 344b1c79e09SJosef Bacik new_flags, level, 0); 345be1a5564SMark Fasheh if (ret) 346be1a5564SMark Fasheh return ret; 3475d4f98a2SYan Zheng } 3485d4f98a2SYan Zheng } else { 3495d4f98a2SYan Zheng if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) { 3505d4f98a2SYan Zheng if (root->root_key.objectid == 3515d4f98a2SYan Zheng BTRFS_TREE_RELOC_OBJECTID) 352e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 1); 3535d4f98a2SYan Zheng else 354e339a6b0SJosef Bacik ret = btrfs_inc_ref(trans, root, cow, 0); 355692826b2SJeff Mahoney if (ret) 356692826b2SJeff Mahoney return ret; 357e339a6b0SJosef Bacik ret = btrfs_dec_ref(trans, root, buf, 1); 358692826b2SJeff Mahoney if (ret) 359692826b2SJeff Mahoney return ret; 3605d4f98a2SYan Zheng } 3616a884d7dSDavid Sterba btrfs_clean_tree_block(buf); 362f0486c68SYan, Zheng *last_ref = 1; 3635d4f98a2SYan Zheng } 3645d4f98a2SYan Zheng return 0; 3655d4f98a2SYan Zheng } 3665d4f98a2SYan Zheng 3675d4f98a2SYan Zheng /* 368d397712bSChris Mason * does the dirty work in cow of a single block. The parent block (if 369d397712bSChris Mason * supplied) is updated to point to the new cow copy. The new buffer is marked 370d397712bSChris Mason * dirty and returned locked. If you modify the block it needs to be marked 371d397712bSChris Mason * dirty again. 372d352ac68SChris Mason * 373d352ac68SChris Mason * search_start -- an allocation hint for the new block 374d352ac68SChris Mason * 375d397712bSChris Mason * empty_size -- a hint that you plan on doing more cow. This is the size in 376d397712bSChris Mason * bytes the allocator should try to find free next to the block it returns. 377d397712bSChris Mason * This is just a hint and may be ignored by the allocator. 378d352ac68SChris Mason */ 379d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans, 3805f39d397SChris Mason struct btrfs_root *root, 3815f39d397SChris Mason struct extent_buffer *buf, 3825f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 3835f39d397SChris Mason struct extent_buffer **cow_ret, 3849631e4ccSJosef Bacik u64 search_start, u64 empty_size, 3859631e4ccSJosef Bacik enum btrfs_lock_nesting nest) 3866702ed49SChris Mason { 3870b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 3885d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 3895f39d397SChris Mason struct extent_buffer *cow; 390be1a5564SMark Fasheh int level, ret; 391f0486c68SYan, Zheng int last_ref = 0; 392925baeddSChris Mason int unlock_orig = 0; 3930f5053ebSGoldwyn Rodrigues u64 parent_start = 0; 3946702ed49SChris Mason 395925baeddSChris Mason if (*cow_ret == buf) 396925baeddSChris Mason unlock_orig = 1; 397925baeddSChris Mason 398b9447ef8SChris Mason btrfs_assert_tree_locked(buf); 399925baeddSChris Mason 40092a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 4010b246afaSJeff Mahoney trans->transid != fs_info->running_transaction->transid); 40292a7cc42SQu Wenruo WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && 40327cdeb70SMiao Xie trans->transid != root->last_trans); 4045f39d397SChris Mason 4057bb86316SChris Mason level = btrfs_header_level(buf); 40631840ae1SZheng Yan 4075d4f98a2SYan Zheng if (level == 0) 4085d4f98a2SYan Zheng btrfs_item_key(buf, &disk_key, 0); 4095d4f98a2SYan Zheng else 4105d4f98a2SYan Zheng btrfs_node_key(buf, &disk_key, 0); 4115d4f98a2SYan Zheng 4120f5053ebSGoldwyn Rodrigues if ((root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && parent) 4135d4f98a2SYan Zheng parent_start = parent->start; 4145d4f98a2SYan Zheng 415*79bd3712SFilipe Manana cow = btrfs_alloc_tree_block(trans, root, parent_start, 416*79bd3712SFilipe Manana root->root_key.objectid, &disk_key, level, 417*79bd3712SFilipe Manana search_start, empty_size, nest); 4186702ed49SChris Mason if (IS_ERR(cow)) 4196702ed49SChris Mason return PTR_ERR(cow); 4206702ed49SChris Mason 421b4ce94deSChris Mason /* cow is set to blocking by btrfs_init_new_buffer */ 422b4ce94deSChris Mason 42358e8012cSDavid Sterba copy_extent_buffer_full(cow, buf); 424db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 4255f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 4265d4f98a2SYan Zheng btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV); 4275d4f98a2SYan Zheng btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN | 4285d4f98a2SYan Zheng BTRFS_HEADER_FLAG_RELOC); 4295d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) 4305d4f98a2SYan Zheng btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC); 4315d4f98a2SYan Zheng else 4325f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 4336702ed49SChris Mason 434de37aa51SNikolay Borisov write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid); 4352b82032cSYan Zheng 436be1a5564SMark Fasheh ret = update_ref_for_cow(trans, root, buf, cow, &last_ref); 437b68dc2a9SMark Fasheh if (ret) { 438572c83acSJosef Bacik btrfs_tree_unlock(cow); 439572c83acSJosef Bacik free_extent_buffer(cow); 44066642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 441b68dc2a9SMark Fasheh return ret; 442b68dc2a9SMark Fasheh } 4431a40e23bSZheng Yan 44492a7cc42SQu Wenruo if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) { 44583d4cfd4SJosef Bacik ret = btrfs_reloc_cow_block(trans, root, buf, cow); 44693314e3bSZhaolei if (ret) { 447572c83acSJosef Bacik btrfs_tree_unlock(cow); 448572c83acSJosef Bacik free_extent_buffer(cow); 44966642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 45083d4cfd4SJosef Bacik return ret; 45183d4cfd4SJosef Bacik } 45293314e3bSZhaolei } 4533fd0a558SYan, Zheng 4546702ed49SChris Mason if (buf == root->node) { 455925baeddSChris Mason WARN_ON(parent && parent != buf); 4565d4f98a2SYan Zheng if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID || 4575d4f98a2SYan Zheng btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV) 4585d4f98a2SYan Zheng parent_start = buf->start; 459925baeddSChris Mason 46067439dadSDavid Sterba atomic_inc(&cow->refs); 461406808abSFilipe Manana ret = btrfs_tree_mod_log_insert_root(root->node, cow, true); 462d9d19a01SDavid Sterba BUG_ON(ret < 0); 463240f62c8SChris Mason rcu_assign_pointer(root->node, cow); 464925baeddSChris Mason 465f0486c68SYan, Zheng btrfs_free_tree_block(trans, root, buf, parent_start, 4665581a51aSJan Schmidt last_ref); 4675f39d397SChris Mason free_extent_buffer(buf); 4680b86a832SChris Mason add_root_to_dirty_list(root); 4696702ed49SChris Mason } else { 4705d4f98a2SYan Zheng WARN_ON(trans->transid != btrfs_header_generation(parent)); 471f3a84ccdSFilipe Manana btrfs_tree_mod_log_insert_key(parent, parent_slot, 472f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 4735f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 474db94535dSChris Mason cow->start); 47574493f7aSChris Mason btrfs_set_node_ptr_generation(parent, parent_slot, 47674493f7aSChris Mason trans->transid); 4776702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 4785de865eeSFilipe David Borba Manana if (last_ref) { 479f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_free_eb(buf); 4805de865eeSFilipe David Borba Manana if (ret) { 481572c83acSJosef Bacik btrfs_tree_unlock(cow); 482572c83acSJosef Bacik free_extent_buffer(cow); 48366642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 4845de865eeSFilipe David Borba Manana return ret; 4855de865eeSFilipe David Borba Manana } 4865de865eeSFilipe David Borba Manana } 487f0486c68SYan, Zheng btrfs_free_tree_block(trans, root, buf, parent_start, 4885581a51aSJan Schmidt last_ref); 4896702ed49SChris Mason } 490925baeddSChris Mason if (unlock_orig) 491925baeddSChris Mason btrfs_tree_unlock(buf); 4923083ee2eSJosef Bacik free_extent_buffer_stale(buf); 4936702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 4946702ed49SChris Mason *cow_ret = cow; 4956702ed49SChris Mason return 0; 4966702ed49SChris Mason } 4976702ed49SChris Mason 4985d4f98a2SYan Zheng static inline int should_cow_block(struct btrfs_trans_handle *trans, 4995d4f98a2SYan Zheng struct btrfs_root *root, 5005d4f98a2SYan Zheng struct extent_buffer *buf) 5015d4f98a2SYan Zheng { 502f5ee5c9aSJeff Mahoney if (btrfs_is_testing(root->fs_info)) 503faa2dbf0SJosef Bacik return 0; 504fccb84c9SDavid Sterba 505d1980131SDavid Sterba /* Ensure we can see the FORCE_COW bit */ 506d1980131SDavid Sterba smp_mb__before_atomic(); 507f1ebcc74SLiu Bo 508f1ebcc74SLiu Bo /* 509f1ebcc74SLiu Bo * We do not need to cow a block if 510f1ebcc74SLiu Bo * 1) this block is not created or changed in this transaction; 511f1ebcc74SLiu Bo * 2) this block does not belong to TREE_RELOC tree; 512f1ebcc74SLiu Bo * 3) the root is not forced COW. 513f1ebcc74SLiu Bo * 514f1ebcc74SLiu Bo * What is forced COW: 51501327610SNicholas D Steeves * when we create snapshot during committing the transaction, 51652042d8eSAndrea Gelmini * after we've finished copying src root, we must COW the shared 517f1ebcc74SLiu Bo * block to ensure the metadata consistency. 518f1ebcc74SLiu Bo */ 5195d4f98a2SYan Zheng if (btrfs_header_generation(buf) == trans->transid && 5205d4f98a2SYan Zheng !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) && 5215d4f98a2SYan Zheng !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID && 522f1ebcc74SLiu Bo btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) && 52327cdeb70SMiao Xie !test_bit(BTRFS_ROOT_FORCE_COW, &root->state)) 5245d4f98a2SYan Zheng return 0; 5255d4f98a2SYan Zheng return 1; 5265d4f98a2SYan Zheng } 5275d4f98a2SYan Zheng 528d352ac68SChris Mason /* 529d352ac68SChris Mason * cows a single block, see __btrfs_cow_block for the real work. 53001327610SNicholas D Steeves * This version of it has extra checks so that a block isn't COWed more than 531d352ac68SChris Mason * once per transaction, as long as it hasn't been written yet 532d352ac68SChris Mason */ 533d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans, 5345f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 5355f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 5369631e4ccSJosef Bacik struct extent_buffer **cow_ret, 5379631e4ccSJosef Bacik enum btrfs_lock_nesting nest) 53802217ed2SChris Mason { 5390b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 5406702ed49SChris Mason u64 search_start; 541f510cfecSChris Mason int ret; 542dc17ff8fSChris Mason 54383354f07SJosef Bacik if (test_bit(BTRFS_ROOT_DELETING, &root->state)) 54483354f07SJosef Bacik btrfs_err(fs_info, 54583354f07SJosef Bacik "COW'ing blocks on a fs root that's being dropped"); 54683354f07SJosef Bacik 5470b246afaSJeff Mahoney if (trans->transaction != fs_info->running_transaction) 54831b1a2bdSJulia Lawall WARN(1, KERN_CRIT "trans %llu running %llu\n", 549c1c9ff7cSGeert Uytterhoeven trans->transid, 5500b246afaSJeff Mahoney fs_info->running_transaction->transid); 55131b1a2bdSJulia Lawall 5520b246afaSJeff Mahoney if (trans->transid != fs_info->generation) 55331b1a2bdSJulia Lawall WARN(1, KERN_CRIT "trans %llu running %llu\n", 5540b246afaSJeff Mahoney trans->transid, fs_info->generation); 555dc17ff8fSChris Mason 5565d4f98a2SYan Zheng if (!should_cow_block(trans, root, buf)) { 55702217ed2SChris Mason *cow_ret = buf; 55802217ed2SChris Mason return 0; 55902217ed2SChris Mason } 560c487685dSChris Mason 561ee22184bSByongho Lee search_start = buf->start & ~((u64)SZ_1G - 1); 562b4ce94deSChris Mason 563f616f5cdSQu Wenruo /* 564f616f5cdSQu Wenruo * Before CoWing this block for later modification, check if it's 565f616f5cdSQu Wenruo * the subtree root and do the delayed subtree trace if needed. 566f616f5cdSQu Wenruo * 567f616f5cdSQu Wenruo * Also We don't care about the error, as it's handled internally. 568f616f5cdSQu Wenruo */ 569f616f5cdSQu Wenruo btrfs_qgroup_trace_subtree_after_cow(trans, root, buf); 570f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 5719631e4ccSJosef Bacik parent_slot, cow_ret, search_start, 0, nest); 5721abe9b8aSliubo 5731abe9b8aSliubo trace_btrfs_cow_block(root, buf, *cow_ret); 5741abe9b8aSliubo 575f510cfecSChris Mason return ret; 5762c90e5d6SChris Mason } 577f75e2b79SJosef Bacik ALLOW_ERROR_INJECTION(btrfs_cow_block, ERRNO); 5786702ed49SChris Mason 579d352ac68SChris Mason /* 580d352ac68SChris Mason * helper function for defrag to decide if two blocks pointed to by a 581d352ac68SChris Mason * node are actually close by 582d352ac68SChris Mason */ 5836b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 5846702ed49SChris Mason { 5856b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 5866702ed49SChris Mason return 1; 5876b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 5886702ed49SChris Mason return 1; 58902217ed2SChris Mason return 0; 59002217ed2SChris Mason } 59102217ed2SChris Mason 592ce6ef5abSDavid Sterba #ifdef __LITTLE_ENDIAN 593ce6ef5abSDavid Sterba 594ce6ef5abSDavid Sterba /* 595ce6ef5abSDavid Sterba * Compare two keys, on little-endian the disk order is same as CPU order and 596ce6ef5abSDavid Sterba * we can avoid the conversion. 597ce6ef5abSDavid Sterba */ 598ce6ef5abSDavid Sterba static int comp_keys(const struct btrfs_disk_key *disk_key, 599ce6ef5abSDavid Sterba const struct btrfs_key *k2) 600ce6ef5abSDavid Sterba { 601ce6ef5abSDavid Sterba const struct btrfs_key *k1 = (const struct btrfs_key *)disk_key; 602ce6ef5abSDavid Sterba 603ce6ef5abSDavid Sterba return btrfs_comp_cpu_keys(k1, k2); 604ce6ef5abSDavid Sterba } 605ce6ef5abSDavid Sterba 606ce6ef5abSDavid Sterba #else 607ce6ef5abSDavid Sterba 608081e9573SChris Mason /* 609081e9573SChris Mason * compare two keys in a memcmp fashion 610081e9573SChris Mason */ 611310712b2SOmar Sandoval static int comp_keys(const struct btrfs_disk_key *disk, 612310712b2SOmar Sandoval const struct btrfs_key *k2) 613081e9573SChris Mason { 614081e9573SChris Mason struct btrfs_key k1; 615081e9573SChris Mason 616081e9573SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 617081e9573SChris Mason 61820736abaSDiego Calleja return btrfs_comp_cpu_keys(&k1, k2); 619081e9573SChris Mason } 620ce6ef5abSDavid Sterba #endif 621081e9573SChris Mason 622f3465ca4SJosef Bacik /* 623f3465ca4SJosef Bacik * same as comp_keys only with two btrfs_key's 624f3465ca4SJosef Bacik */ 625e1f60a65SDavid Sterba int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2) 626f3465ca4SJosef Bacik { 627f3465ca4SJosef Bacik if (k1->objectid > k2->objectid) 628f3465ca4SJosef Bacik return 1; 629f3465ca4SJosef Bacik if (k1->objectid < k2->objectid) 630f3465ca4SJosef Bacik return -1; 631f3465ca4SJosef Bacik if (k1->type > k2->type) 632f3465ca4SJosef Bacik return 1; 633f3465ca4SJosef Bacik if (k1->type < k2->type) 634f3465ca4SJosef Bacik return -1; 635f3465ca4SJosef Bacik if (k1->offset > k2->offset) 636f3465ca4SJosef Bacik return 1; 637f3465ca4SJosef Bacik if (k1->offset < k2->offset) 638f3465ca4SJosef Bacik return -1; 639f3465ca4SJosef Bacik return 0; 640f3465ca4SJosef Bacik } 641081e9573SChris Mason 642d352ac68SChris Mason /* 643d352ac68SChris Mason * this is used by the defrag code to go through all the 644d352ac68SChris Mason * leaves pointed to by a node and reallocate them so that 645d352ac68SChris Mason * disk order is close to key order 646d352ac68SChris Mason */ 6476702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 6485f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 649de78b51aSEric Sandeen int start_slot, u64 *last_ret, 650a6b6e75eSChris Mason struct btrfs_key *progress) 6516702ed49SChris Mason { 6520b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 6536b80053dSChris Mason struct extent_buffer *cur; 6546702ed49SChris Mason u64 blocknr; 655e9d0b13bSChris Mason u64 search_start = *last_ret; 656e9d0b13bSChris Mason u64 last_block = 0; 6576702ed49SChris Mason u64 other; 6586702ed49SChris Mason u32 parent_nritems; 6596702ed49SChris Mason int end_slot; 6606702ed49SChris Mason int i; 6616702ed49SChris Mason int err = 0; 6626b80053dSChris Mason u32 blocksize; 663081e9573SChris Mason int progress_passed = 0; 664081e9573SChris Mason struct btrfs_disk_key disk_key; 6656702ed49SChris Mason 6660b246afaSJeff Mahoney WARN_ON(trans->transaction != fs_info->running_transaction); 6670b246afaSJeff Mahoney WARN_ON(trans->transid != fs_info->generation); 66886479a04SChris Mason 6696b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 6700b246afaSJeff Mahoney blocksize = fs_info->nodesize; 6715dfe2be7SFilipe Manana end_slot = parent_nritems - 1; 6726702ed49SChris Mason 6735dfe2be7SFilipe Manana if (parent_nritems <= 1) 6746702ed49SChris Mason return 0; 6756702ed49SChris Mason 6765dfe2be7SFilipe Manana for (i = start_slot; i <= end_slot; i++) { 6776702ed49SChris Mason int close = 1; 678a6b6e75eSChris Mason 679081e9573SChris Mason btrfs_node_key(parent, &disk_key, i); 680081e9573SChris Mason if (!progress_passed && comp_keys(&disk_key, progress) < 0) 681081e9573SChris Mason continue; 682081e9573SChris Mason 683081e9573SChris Mason progress_passed = 1; 6846b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 685e9d0b13bSChris Mason if (last_block == 0) 686e9d0b13bSChris Mason last_block = blocknr; 6875708b959SChris Mason 6886702ed49SChris Mason if (i > 0) { 6896b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 6906b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 6916702ed49SChris Mason } 6925dfe2be7SFilipe Manana if (!close && i < end_slot) { 6936b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 6946b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 6956702ed49SChris Mason } 696e9d0b13bSChris Mason if (close) { 697e9d0b13bSChris Mason last_block = blocknr; 6986702ed49SChris Mason continue; 699e9d0b13bSChris Mason } 7006702ed49SChris Mason 701206983b7SJosef Bacik cur = btrfs_read_node_slot(parent, i); 702206983b7SJosef Bacik if (IS_ERR(cur)) 70364c043deSLiu Bo return PTR_ERR(cur); 704e9d0b13bSChris Mason if (search_start == 0) 7056b80053dSChris Mason search_start = last_block; 706e9d0b13bSChris Mason 707e7a84565SChris Mason btrfs_tree_lock(cur); 7086b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 709e7a84565SChris Mason &cur, search_start, 7106b80053dSChris Mason min(16 * blocksize, 7119631e4ccSJosef Bacik (end_slot - i) * blocksize), 7129631e4ccSJosef Bacik BTRFS_NESTING_COW); 713252c38f0SYan if (err) { 714e7a84565SChris Mason btrfs_tree_unlock(cur); 7156b80053dSChris Mason free_extent_buffer(cur); 7166702ed49SChris Mason break; 717252c38f0SYan } 718e7a84565SChris Mason search_start = cur->start; 719e7a84565SChris Mason last_block = cur->start; 720f2183bdeSChris Mason *last_ret = search_start; 721e7a84565SChris Mason btrfs_tree_unlock(cur); 722e7a84565SChris Mason free_extent_buffer(cur); 7236702ed49SChris Mason } 7246702ed49SChris Mason return err; 7256702ed49SChris Mason } 7266702ed49SChris Mason 72774123bd7SChris Mason /* 7285f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 7295f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 7305f39d397SChris Mason * 73174123bd7SChris Mason * the slot in the array is returned via slot, and it points to 73274123bd7SChris Mason * the place where you would insert key if it is not found in 73374123bd7SChris Mason * the array. 73474123bd7SChris Mason * 73574123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 73674123bd7SChris Mason */ 737e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb, 738310712b2SOmar Sandoval unsigned long p, int item_size, 739310712b2SOmar Sandoval const struct btrfs_key *key, 740be0e5c09SChris Mason int max, int *slot) 741be0e5c09SChris Mason { 742be0e5c09SChris Mason int low = 0; 743be0e5c09SChris Mason int high = max; 744be0e5c09SChris Mason int ret; 7455cd17f34SDavid Sterba const int key_size = sizeof(struct btrfs_disk_key); 746be0e5c09SChris Mason 7475e24e9afSLiu Bo if (low > high) { 7485e24e9afSLiu Bo btrfs_err(eb->fs_info, 7495e24e9afSLiu Bo "%s: low (%d) > high (%d) eb %llu owner %llu level %d", 7505e24e9afSLiu Bo __func__, low, high, eb->start, 7515e24e9afSLiu Bo btrfs_header_owner(eb), btrfs_header_level(eb)); 7525e24e9afSLiu Bo return -EINVAL; 7535e24e9afSLiu Bo } 7545e24e9afSLiu Bo 755be0e5c09SChris Mason while (low < high) { 7565cd17f34SDavid Sterba unsigned long oip; 7575cd17f34SDavid Sterba unsigned long offset; 7585cd17f34SDavid Sterba struct btrfs_disk_key *tmp; 7595cd17f34SDavid Sterba struct btrfs_disk_key unaligned; 7605cd17f34SDavid Sterba int mid; 7615cd17f34SDavid Sterba 762be0e5c09SChris Mason mid = (low + high) / 2; 7635f39d397SChris Mason offset = p + mid * item_size; 7645cd17f34SDavid Sterba oip = offset_in_page(offset); 7655f39d397SChris Mason 7665cd17f34SDavid Sterba if (oip + key_size <= PAGE_SIZE) { 767884b07d0SQu Wenruo const unsigned long idx = get_eb_page_index(offset); 7685cd17f34SDavid Sterba char *kaddr = page_address(eb->pages[idx]); 769934d375bSChris Mason 770884b07d0SQu Wenruo oip = get_eb_offset_in_page(eb, offset); 7715cd17f34SDavid Sterba tmp = (struct btrfs_disk_key *)(kaddr + oip); 7725cd17f34SDavid Sterba } else { 7735cd17f34SDavid Sterba read_extent_buffer(eb, &unaligned, offset, key_size); 7745f39d397SChris Mason tmp = &unaligned; 775479965d6SChris Mason } 776479965d6SChris Mason 777be0e5c09SChris Mason ret = comp_keys(tmp, key); 778be0e5c09SChris Mason 779be0e5c09SChris Mason if (ret < 0) 780be0e5c09SChris Mason low = mid + 1; 781be0e5c09SChris Mason else if (ret > 0) 782be0e5c09SChris Mason high = mid; 783be0e5c09SChris Mason else { 784be0e5c09SChris Mason *slot = mid; 785be0e5c09SChris Mason return 0; 786be0e5c09SChris Mason } 787be0e5c09SChris Mason } 788be0e5c09SChris Mason *slot = low; 789be0e5c09SChris Mason return 1; 790be0e5c09SChris Mason } 791be0e5c09SChris Mason 79297571fd0SChris Mason /* 79397571fd0SChris Mason * simple bin_search frontend that does the right thing for 79497571fd0SChris Mason * leaves vs nodes 79597571fd0SChris Mason */ 796a74b35ecSNikolay Borisov int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key, 797e3b83361SQu Wenruo int *slot) 798be0e5c09SChris Mason { 799e3b83361SQu Wenruo if (btrfs_header_level(eb) == 0) 8005f39d397SChris Mason return generic_bin_search(eb, 8015f39d397SChris Mason offsetof(struct btrfs_leaf, items), 8020783fcfcSChris Mason sizeof(struct btrfs_item), 8035f39d397SChris Mason key, btrfs_header_nritems(eb), 8047518a238SChris Mason slot); 805f775738fSWang Sheng-Hui else 8065f39d397SChris Mason return generic_bin_search(eb, 8075f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 808123abc88SChris Mason sizeof(struct btrfs_key_ptr), 8095f39d397SChris Mason key, btrfs_header_nritems(eb), 8107518a238SChris Mason slot); 811be0e5c09SChris Mason } 812be0e5c09SChris Mason 813f0486c68SYan, Zheng static void root_add_used(struct btrfs_root *root, u32 size) 814f0486c68SYan, Zheng { 815f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 816f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 817f0486c68SYan, Zheng btrfs_root_used(&root->root_item) + size); 818f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 819f0486c68SYan, Zheng } 820f0486c68SYan, Zheng 821f0486c68SYan, Zheng static void root_sub_used(struct btrfs_root *root, u32 size) 822f0486c68SYan, Zheng { 823f0486c68SYan, Zheng spin_lock(&root->accounting_lock); 824f0486c68SYan, Zheng btrfs_set_root_used(&root->root_item, 825f0486c68SYan, Zheng btrfs_root_used(&root->root_item) - size); 826f0486c68SYan, Zheng spin_unlock(&root->accounting_lock); 827f0486c68SYan, Zheng } 828f0486c68SYan, Zheng 829d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to. The 830d352ac68SChris Mason * extent buffer is returned with a reference taken (but unlocked). 831d352ac68SChris Mason */ 8324b231ae4SDavid Sterba struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent, 8334b231ae4SDavid Sterba int slot) 834bb803951SChris Mason { 835ca7a79adSChris Mason int level = btrfs_header_level(parent); 836416bc658SJosef Bacik struct extent_buffer *eb; 837581c1760SQu Wenruo struct btrfs_key first_key; 838416bc658SJosef Bacik 839fb770ae4SLiu Bo if (slot < 0 || slot >= btrfs_header_nritems(parent)) 840fb770ae4SLiu Bo return ERR_PTR(-ENOENT); 841ca7a79adSChris Mason 842ca7a79adSChris Mason BUG_ON(level == 0); 843ca7a79adSChris Mason 844581c1760SQu Wenruo btrfs_node_key_to_cpu(parent, &first_key, slot); 845d0d20b0fSDavid Sterba eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot), 8461b7ec85eSJosef Bacik btrfs_header_owner(parent), 847581c1760SQu Wenruo btrfs_node_ptr_generation(parent, slot), 848581c1760SQu Wenruo level - 1, &first_key); 849fb770ae4SLiu Bo if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) { 850416bc658SJosef Bacik free_extent_buffer(eb); 851fb770ae4SLiu Bo eb = ERR_PTR(-EIO); 852416bc658SJosef Bacik } 853416bc658SJosef Bacik 854416bc658SJosef Bacik return eb; 855bb803951SChris Mason } 856bb803951SChris Mason 857d352ac68SChris Mason /* 858d352ac68SChris Mason * node level balancing, used to make sure nodes are in proper order for 859d352ac68SChris Mason * item deletion. We balance from the top down, so we have to make sure 860d352ac68SChris Mason * that a deletion won't leave an node completely empty later on. 861d352ac68SChris Mason */ 862e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans, 86398ed5174SChris Mason struct btrfs_root *root, 86498ed5174SChris Mason struct btrfs_path *path, int level) 865bb803951SChris Mason { 8660b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 8675f39d397SChris Mason struct extent_buffer *right = NULL; 8685f39d397SChris Mason struct extent_buffer *mid; 8695f39d397SChris Mason struct extent_buffer *left = NULL; 8705f39d397SChris Mason struct extent_buffer *parent = NULL; 871bb803951SChris Mason int ret = 0; 872bb803951SChris Mason int wret; 873bb803951SChris Mason int pslot; 874bb803951SChris Mason int orig_slot = path->slots[level]; 87579f95c82SChris Mason u64 orig_ptr; 876bb803951SChris Mason 87798e6b1ebSLiu Bo ASSERT(level > 0); 878bb803951SChris Mason 8795f39d397SChris Mason mid = path->nodes[level]; 880b4ce94deSChris Mason 881ac5887c8SJosef Bacik WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK); 8827bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 8837bb86316SChris Mason 8841d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 88579f95c82SChris Mason 886a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 8875f39d397SChris Mason parent = path->nodes[level + 1]; 888bb803951SChris Mason pslot = path->slots[level + 1]; 889a05a9bb1SLi Zefan } 890bb803951SChris Mason 89140689478SChris Mason /* 89240689478SChris Mason * deal with the case where there is only one pointer in the root 89340689478SChris Mason * by promoting the node below to a root 89440689478SChris Mason */ 8955f39d397SChris Mason if (!parent) { 8965f39d397SChris Mason struct extent_buffer *child; 897bb803951SChris Mason 8985f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 899bb803951SChris Mason return 0; 900bb803951SChris Mason 901bb803951SChris Mason /* promote the child to a root */ 9024b231ae4SDavid Sterba child = btrfs_read_node_slot(mid, 0); 903fb770ae4SLiu Bo if (IS_ERR(child)) { 904fb770ae4SLiu Bo ret = PTR_ERR(child); 9050b246afaSJeff Mahoney btrfs_handle_fs_error(fs_info, ret, NULL); 906305a26afSMark Fasheh goto enospc; 907305a26afSMark Fasheh } 908305a26afSMark Fasheh 909925baeddSChris Mason btrfs_tree_lock(child); 9109631e4ccSJosef Bacik ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 9119631e4ccSJosef Bacik BTRFS_NESTING_COW); 912f0486c68SYan, Zheng if (ret) { 913f0486c68SYan, Zheng btrfs_tree_unlock(child); 914f0486c68SYan, Zheng free_extent_buffer(child); 915f0486c68SYan, Zheng goto enospc; 916f0486c68SYan, Zheng } 9172f375ab9SYan 918406808abSFilipe Manana ret = btrfs_tree_mod_log_insert_root(root->node, child, true); 919d9d19a01SDavid Sterba BUG_ON(ret < 0); 920240f62c8SChris Mason rcu_assign_pointer(root->node, child); 921925baeddSChris Mason 9220b86a832SChris Mason add_root_to_dirty_list(root); 923925baeddSChris Mason btrfs_tree_unlock(child); 924b4ce94deSChris Mason 925925baeddSChris Mason path->locks[level] = 0; 926bb803951SChris Mason path->nodes[level] = NULL; 9276a884d7dSDavid Sterba btrfs_clean_tree_block(mid); 928925baeddSChris Mason btrfs_tree_unlock(mid); 929bb803951SChris Mason /* once for the path */ 9305f39d397SChris Mason free_extent_buffer(mid); 931f0486c68SYan, Zheng 932f0486c68SYan, Zheng root_sub_used(root, mid->len); 9335581a51aSJan Schmidt btrfs_free_tree_block(trans, root, mid, 0, 1); 934bb803951SChris Mason /* once for the root ptr */ 9353083ee2eSJosef Bacik free_extent_buffer_stale(mid); 936f0486c68SYan, Zheng return 0; 937bb803951SChris Mason } 9385f39d397SChris Mason if (btrfs_header_nritems(mid) > 9390b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4) 940bb803951SChris Mason return 0; 941bb803951SChris Mason 9424b231ae4SDavid Sterba left = btrfs_read_node_slot(parent, pslot - 1); 943fb770ae4SLiu Bo if (IS_ERR(left)) 944fb770ae4SLiu Bo left = NULL; 945fb770ae4SLiu Bo 9465f39d397SChris Mason if (left) { 947bf77467aSJosef Bacik __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 9485f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 9499631e4ccSJosef Bacik parent, pslot - 1, &left, 950bf59a5a2SJosef Bacik BTRFS_NESTING_LEFT_COW); 95154aa1f4dSChris Mason if (wret) { 95254aa1f4dSChris Mason ret = wret; 95354aa1f4dSChris Mason goto enospc; 95454aa1f4dSChris Mason } 9552cc58cf2SChris Mason } 956fb770ae4SLiu Bo 9574b231ae4SDavid Sterba right = btrfs_read_node_slot(parent, pslot + 1); 958fb770ae4SLiu Bo if (IS_ERR(right)) 959fb770ae4SLiu Bo right = NULL; 960fb770ae4SLiu Bo 9615f39d397SChris Mason if (right) { 962bf77467aSJosef Bacik __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 9635f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 9649631e4ccSJosef Bacik parent, pslot + 1, &right, 965bf59a5a2SJosef Bacik BTRFS_NESTING_RIGHT_COW); 9662cc58cf2SChris Mason if (wret) { 9672cc58cf2SChris Mason ret = wret; 9682cc58cf2SChris Mason goto enospc; 9692cc58cf2SChris Mason } 9702cc58cf2SChris Mason } 9712cc58cf2SChris Mason 9722cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 9735f39d397SChris Mason if (left) { 9745f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 975d30a668fSDavid Sterba wret = push_node_left(trans, left, mid, 1); 97679f95c82SChris Mason if (wret < 0) 97779f95c82SChris Mason ret = wret; 978bb803951SChris Mason } 97979f95c82SChris Mason 98079f95c82SChris Mason /* 98179f95c82SChris Mason * then try to empty the right most buffer into the middle 98279f95c82SChris Mason */ 9835f39d397SChris Mason if (right) { 984d30a668fSDavid Sterba wret = push_node_left(trans, mid, right, 1); 98554aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 98679f95c82SChris Mason ret = wret; 9875f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 9886a884d7dSDavid Sterba btrfs_clean_tree_block(right); 989925baeddSChris Mason btrfs_tree_unlock(right); 990afe5fea7STsutomu Itoh del_ptr(root, path, level + 1, pslot + 1); 991f0486c68SYan, Zheng root_sub_used(root, right->len); 9925581a51aSJan Schmidt btrfs_free_tree_block(trans, root, right, 0, 1); 9933083ee2eSJosef Bacik free_extent_buffer_stale(right); 994f0486c68SYan, Zheng right = NULL; 995bb803951SChris Mason } else { 9965f39d397SChris Mason struct btrfs_disk_key right_key; 9975f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 998f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1, 999f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 10000e82bcfeSDavid Sterba BUG_ON(ret < 0); 10015f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 10025f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 1003bb803951SChris Mason } 1004bb803951SChris Mason } 10055f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 100679f95c82SChris Mason /* 100779f95c82SChris Mason * we're not allowed to leave a node with one item in the 100879f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 100979f95c82SChris Mason * could try to delete the only pointer in this node. 101079f95c82SChris Mason * So, pull some keys from the left. 101179f95c82SChris Mason * There has to be a left pointer at this point because 101279f95c82SChris Mason * otherwise we would have pulled some pointers from the 101379f95c82SChris Mason * right 101479f95c82SChris Mason */ 1015305a26afSMark Fasheh if (!left) { 1016305a26afSMark Fasheh ret = -EROFS; 10170b246afaSJeff Mahoney btrfs_handle_fs_error(fs_info, ret, NULL); 1018305a26afSMark Fasheh goto enospc; 1019305a26afSMark Fasheh } 102055d32ed8SDavid Sterba wret = balance_node_right(trans, mid, left); 102154aa1f4dSChris Mason if (wret < 0) { 102279f95c82SChris Mason ret = wret; 102354aa1f4dSChris Mason goto enospc; 102454aa1f4dSChris Mason } 1025bce4eae9SChris Mason if (wret == 1) { 1026d30a668fSDavid Sterba wret = push_node_left(trans, left, mid, 1); 1027bce4eae9SChris Mason if (wret < 0) 1028bce4eae9SChris Mason ret = wret; 1029bce4eae9SChris Mason } 103079f95c82SChris Mason BUG_ON(wret == 1); 103179f95c82SChris Mason } 10325f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 10336a884d7dSDavid Sterba btrfs_clean_tree_block(mid); 1034925baeddSChris Mason btrfs_tree_unlock(mid); 1035afe5fea7STsutomu Itoh del_ptr(root, path, level + 1, pslot); 1036f0486c68SYan, Zheng root_sub_used(root, mid->len); 10375581a51aSJan Schmidt btrfs_free_tree_block(trans, root, mid, 0, 1); 10383083ee2eSJosef Bacik free_extent_buffer_stale(mid); 1039f0486c68SYan, Zheng mid = NULL; 104079f95c82SChris Mason } else { 104179f95c82SChris Mason /* update the parent key to reflect our changes */ 10425f39d397SChris Mason struct btrfs_disk_key mid_key; 10435f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 1044f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot, 1045f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 10460e82bcfeSDavid Sterba BUG_ON(ret < 0); 10475f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 10485f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 104979f95c82SChris Mason } 1050bb803951SChris Mason 105179f95c82SChris Mason /* update the path */ 10525f39d397SChris Mason if (left) { 10535f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 105467439dadSDavid Sterba atomic_inc(&left->refs); 1055925baeddSChris Mason /* left was locked after cow */ 10565f39d397SChris Mason path->nodes[level] = left; 1057bb803951SChris Mason path->slots[level + 1] -= 1; 1058bb803951SChris Mason path->slots[level] = orig_slot; 1059925baeddSChris Mason if (mid) { 1060925baeddSChris Mason btrfs_tree_unlock(mid); 10615f39d397SChris Mason free_extent_buffer(mid); 1062925baeddSChris Mason } 1063bb803951SChris Mason } else { 10645f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 1065bb803951SChris Mason path->slots[level] = orig_slot; 1066bb803951SChris Mason } 1067bb803951SChris Mason } 106879f95c82SChris Mason /* double check we haven't messed things up */ 1069e20d96d6SChris Mason if (orig_ptr != 10705f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 107179f95c82SChris Mason BUG(); 107254aa1f4dSChris Mason enospc: 1073925baeddSChris Mason if (right) { 1074925baeddSChris Mason btrfs_tree_unlock(right); 10755f39d397SChris Mason free_extent_buffer(right); 1076925baeddSChris Mason } 1077925baeddSChris Mason if (left) { 1078925baeddSChris Mason if (path->nodes[level] != left) 1079925baeddSChris Mason btrfs_tree_unlock(left); 10805f39d397SChris Mason free_extent_buffer(left); 1081925baeddSChris Mason } 1082bb803951SChris Mason return ret; 1083bb803951SChris Mason } 1084bb803951SChris Mason 1085d352ac68SChris Mason /* Node balancing for insertion. Here we only split or push nodes around 1086d352ac68SChris Mason * when they are completely full. This is also done top down, so we 1087d352ac68SChris Mason * have to be pessimistic. 1088d352ac68SChris Mason */ 1089d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans, 1090e66f709bSChris Mason struct btrfs_root *root, 1091e66f709bSChris Mason struct btrfs_path *path, int level) 1092e66f709bSChris Mason { 10930b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 10945f39d397SChris Mason struct extent_buffer *right = NULL; 10955f39d397SChris Mason struct extent_buffer *mid; 10965f39d397SChris Mason struct extent_buffer *left = NULL; 10975f39d397SChris Mason struct extent_buffer *parent = NULL; 1098e66f709bSChris Mason int ret = 0; 1099e66f709bSChris Mason int wret; 1100e66f709bSChris Mason int pslot; 1101e66f709bSChris Mason int orig_slot = path->slots[level]; 1102e66f709bSChris Mason 1103e66f709bSChris Mason if (level == 0) 1104e66f709bSChris Mason return 1; 1105e66f709bSChris Mason 11065f39d397SChris Mason mid = path->nodes[level]; 11077bb86316SChris Mason WARN_ON(btrfs_header_generation(mid) != trans->transid); 1108e66f709bSChris Mason 1109a05a9bb1SLi Zefan if (level < BTRFS_MAX_LEVEL - 1) { 11105f39d397SChris Mason parent = path->nodes[level + 1]; 1111e66f709bSChris Mason pslot = path->slots[level + 1]; 1112a05a9bb1SLi Zefan } 1113e66f709bSChris Mason 11145f39d397SChris Mason if (!parent) 1115e66f709bSChris Mason return 1; 1116e66f709bSChris Mason 11174b231ae4SDavid Sterba left = btrfs_read_node_slot(parent, pslot - 1); 1118fb770ae4SLiu Bo if (IS_ERR(left)) 1119fb770ae4SLiu Bo left = NULL; 1120e66f709bSChris Mason 1121e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 11225f39d397SChris Mason if (left) { 1123e66f709bSChris Mason u32 left_nr; 1124925baeddSChris Mason 1125bf77467aSJosef Bacik __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 1126b4ce94deSChris Mason 11275f39d397SChris Mason left_nr = btrfs_header_nritems(left); 11280b246afaSJeff Mahoney if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { 112933ade1f8SChris Mason wret = 1; 113033ade1f8SChris Mason } else { 11315f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 11329631e4ccSJosef Bacik pslot - 1, &left, 1133bf59a5a2SJosef Bacik BTRFS_NESTING_LEFT_COW); 113454aa1f4dSChris Mason if (ret) 113554aa1f4dSChris Mason wret = 1; 113654aa1f4dSChris Mason else { 1137d30a668fSDavid Sterba wret = push_node_left(trans, left, mid, 0); 113854aa1f4dSChris Mason } 113933ade1f8SChris Mason } 1140e66f709bSChris Mason if (wret < 0) 1141e66f709bSChris Mason ret = wret; 1142e66f709bSChris Mason if (wret == 0) { 11435f39d397SChris Mason struct btrfs_disk_key disk_key; 1144e66f709bSChris Mason orig_slot += left_nr; 11455f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 1146f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot, 1147f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 11480e82bcfeSDavid Sterba BUG_ON(ret < 0); 11495f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 11505f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 11515f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 11525f39d397SChris Mason path->nodes[level] = left; 1153e66f709bSChris Mason path->slots[level + 1] -= 1; 1154e66f709bSChris Mason path->slots[level] = orig_slot; 1155925baeddSChris Mason btrfs_tree_unlock(mid); 11565f39d397SChris Mason free_extent_buffer(mid); 1157e66f709bSChris Mason } else { 1158e66f709bSChris Mason orig_slot -= 11595f39d397SChris Mason btrfs_header_nritems(left); 1160e66f709bSChris Mason path->slots[level] = orig_slot; 1161925baeddSChris Mason btrfs_tree_unlock(left); 11625f39d397SChris Mason free_extent_buffer(left); 1163e66f709bSChris Mason } 1164e66f709bSChris Mason return 0; 1165e66f709bSChris Mason } 1166925baeddSChris Mason btrfs_tree_unlock(left); 11675f39d397SChris Mason free_extent_buffer(left); 1168e66f709bSChris Mason } 11694b231ae4SDavid Sterba right = btrfs_read_node_slot(parent, pslot + 1); 1170fb770ae4SLiu Bo if (IS_ERR(right)) 1171fb770ae4SLiu Bo right = NULL; 1172e66f709bSChris Mason 1173e66f709bSChris Mason /* 1174e66f709bSChris Mason * then try to empty the right most buffer into the middle 1175e66f709bSChris Mason */ 11765f39d397SChris Mason if (right) { 117733ade1f8SChris Mason u32 right_nr; 1178b4ce94deSChris Mason 1179bf77467aSJosef Bacik __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 1180b4ce94deSChris Mason 11815f39d397SChris Mason right_nr = btrfs_header_nritems(right); 11820b246afaSJeff Mahoney if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) { 118333ade1f8SChris Mason wret = 1; 118433ade1f8SChris Mason } else { 11855f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 11865f39d397SChris Mason parent, pslot + 1, 1187bf59a5a2SJosef Bacik &right, BTRFS_NESTING_RIGHT_COW); 118854aa1f4dSChris Mason if (ret) 118954aa1f4dSChris Mason wret = 1; 119054aa1f4dSChris Mason else { 119155d32ed8SDavid Sterba wret = balance_node_right(trans, right, mid); 119233ade1f8SChris Mason } 119354aa1f4dSChris Mason } 1194e66f709bSChris Mason if (wret < 0) 1195e66f709bSChris Mason ret = wret; 1196e66f709bSChris Mason if (wret == 0) { 11975f39d397SChris Mason struct btrfs_disk_key disk_key; 11985f39d397SChris Mason 11995f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 1200f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1, 1201f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_NOFS); 12020e82bcfeSDavid Sterba BUG_ON(ret < 0); 12035f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 12045f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 12055f39d397SChris Mason 12065f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 12075f39d397SChris Mason path->nodes[level] = right; 1208e66f709bSChris Mason path->slots[level + 1] += 1; 1209e66f709bSChris Mason path->slots[level] = orig_slot - 12105f39d397SChris Mason btrfs_header_nritems(mid); 1211925baeddSChris Mason btrfs_tree_unlock(mid); 12125f39d397SChris Mason free_extent_buffer(mid); 1213e66f709bSChris Mason } else { 1214925baeddSChris Mason btrfs_tree_unlock(right); 12155f39d397SChris Mason free_extent_buffer(right); 1216e66f709bSChris Mason } 1217e66f709bSChris Mason return 0; 1218e66f709bSChris Mason } 1219925baeddSChris Mason btrfs_tree_unlock(right); 12205f39d397SChris Mason free_extent_buffer(right); 1221e66f709bSChris Mason } 1222e66f709bSChris Mason return 1; 1223e66f709bSChris Mason } 1224e66f709bSChris Mason 122574123bd7SChris Mason /* 1226d352ac68SChris Mason * readahead one full node of leaves, finding things that are close 1227d352ac68SChris Mason * to the block in 'slot', and triggering ra on them. 12283c69faecSChris Mason */ 12292ff7e61eSJeff Mahoney static void reada_for_search(struct btrfs_fs_info *fs_info, 1230e02119d5SChris Mason struct btrfs_path *path, 123101f46658SChris Mason int level, int slot, u64 objectid) 12323c69faecSChris Mason { 12335f39d397SChris Mason struct extent_buffer *node; 123401f46658SChris Mason struct btrfs_disk_key disk_key; 12353c69faecSChris Mason u32 nritems; 12363c69faecSChris Mason u64 search; 1237a7175319SChris Mason u64 target; 12386b80053dSChris Mason u64 nread = 0; 1239ace75066SFilipe Manana u64 nread_max; 12405f39d397SChris Mason struct extent_buffer *eb; 12416b80053dSChris Mason u32 nr; 12426b80053dSChris Mason u32 blocksize; 12436b80053dSChris Mason u32 nscan = 0; 1244db94535dSChris Mason 1245ace75066SFilipe Manana if (level != 1 && path->reada != READA_FORWARD_ALWAYS) 12463c69faecSChris Mason return; 12473c69faecSChris Mason 12486702ed49SChris Mason if (!path->nodes[level]) 12496702ed49SChris Mason return; 12506702ed49SChris Mason 12515f39d397SChris Mason node = path->nodes[level]; 1252925baeddSChris Mason 1253ace75066SFilipe Manana /* 1254ace75066SFilipe Manana * Since the time between visiting leaves is much shorter than the time 1255ace75066SFilipe Manana * between visiting nodes, limit read ahead of nodes to 1, to avoid too 1256ace75066SFilipe Manana * much IO at once (possibly random). 1257ace75066SFilipe Manana */ 1258ace75066SFilipe Manana if (path->reada == READA_FORWARD_ALWAYS) { 1259ace75066SFilipe Manana if (level > 1) 1260ace75066SFilipe Manana nread_max = node->fs_info->nodesize; 1261ace75066SFilipe Manana else 1262ace75066SFilipe Manana nread_max = SZ_128K; 1263ace75066SFilipe Manana } else { 1264ace75066SFilipe Manana nread_max = SZ_64K; 1265ace75066SFilipe Manana } 1266ace75066SFilipe Manana 12673c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 12680b246afaSJeff Mahoney blocksize = fs_info->nodesize; 12690b246afaSJeff Mahoney eb = find_extent_buffer(fs_info, search); 12705f39d397SChris Mason if (eb) { 12715f39d397SChris Mason free_extent_buffer(eb); 12723c69faecSChris Mason return; 12733c69faecSChris Mason } 12743c69faecSChris Mason 1275a7175319SChris Mason target = search; 12766b80053dSChris Mason 12775f39d397SChris Mason nritems = btrfs_header_nritems(node); 12786b80053dSChris Mason nr = slot; 127925b8b936SJosef Bacik 12803c69faecSChris Mason while (1) { 1281e4058b54SDavid Sterba if (path->reada == READA_BACK) { 12826b80053dSChris Mason if (nr == 0) 12833c69faecSChris Mason break; 12846b80053dSChris Mason nr--; 1285ace75066SFilipe Manana } else if (path->reada == READA_FORWARD || 1286ace75066SFilipe Manana path->reada == READA_FORWARD_ALWAYS) { 12876b80053dSChris Mason nr++; 12886b80053dSChris Mason if (nr >= nritems) 12896b80053dSChris Mason break; 12903c69faecSChris Mason } 1291e4058b54SDavid Sterba if (path->reada == READA_BACK && objectid) { 129201f46658SChris Mason btrfs_node_key(node, &disk_key, nr); 129301f46658SChris Mason if (btrfs_disk_key_objectid(&disk_key) != objectid) 129401f46658SChris Mason break; 129501f46658SChris Mason } 12966b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 1297ace75066SFilipe Manana if (path->reada == READA_FORWARD_ALWAYS || 1298ace75066SFilipe Manana (search <= target && target - search <= 65536) || 1299a7175319SChris Mason (search > target && search - target <= 65536)) { 1300bfb484d9SJosef Bacik btrfs_readahead_node_child(node, nr); 13016b80053dSChris Mason nread += blocksize; 13023c69faecSChris Mason } 13036b80053dSChris Mason nscan++; 1304ace75066SFilipe Manana if (nread > nread_max || nscan > 32) 13056b80053dSChris Mason break; 13063c69faecSChris Mason } 13073c69faecSChris Mason } 1308925baeddSChris Mason 1309bfb484d9SJosef Bacik static noinline void reada_for_balance(struct btrfs_path *path, int level) 1310b4ce94deSChris Mason { 1311bfb484d9SJosef Bacik struct extent_buffer *parent; 1312b4ce94deSChris Mason int slot; 1313b4ce94deSChris Mason int nritems; 1314b4ce94deSChris Mason 13158c594ea8SChris Mason parent = path->nodes[level + 1]; 1316b4ce94deSChris Mason if (!parent) 13170b08851fSJosef Bacik return; 1318b4ce94deSChris Mason 1319b4ce94deSChris Mason nritems = btrfs_header_nritems(parent); 13208c594ea8SChris Mason slot = path->slots[level + 1]; 1321b4ce94deSChris Mason 1322bfb484d9SJosef Bacik if (slot > 0) 1323bfb484d9SJosef Bacik btrfs_readahead_node_child(parent, slot - 1); 1324bfb484d9SJosef Bacik if (slot + 1 < nritems) 1325bfb484d9SJosef Bacik btrfs_readahead_node_child(parent, slot + 1); 1326b4ce94deSChris Mason } 1327b4ce94deSChris Mason 1328b4ce94deSChris Mason 1329b4ce94deSChris Mason /* 1330d397712bSChris Mason * when we walk down the tree, it is usually safe to unlock the higher layers 1331d397712bSChris Mason * in the tree. The exceptions are when our path goes through slot 0, because 1332d397712bSChris Mason * operations on the tree might require changing key pointers higher up in the 1333d397712bSChris Mason * tree. 1334d352ac68SChris Mason * 1335d397712bSChris Mason * callers might also have set path->keep_locks, which tells this code to keep 1336d397712bSChris Mason * the lock if the path points to the last slot in the block. This is part of 1337d397712bSChris Mason * walking through the tree, and selecting the next slot in the higher block. 1338d352ac68SChris Mason * 1339d397712bSChris Mason * lowest_unlock sets the lowest level in the tree we're allowed to unlock. so 1340d397712bSChris Mason * if lowest_unlock is 1, level 0 won't be unlocked 1341d352ac68SChris Mason */ 1342e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level, 1343f7c79f30SChris Mason int lowest_unlock, int min_write_lock_level, 1344f7c79f30SChris Mason int *write_lock_level) 1345925baeddSChris Mason { 1346925baeddSChris Mason int i; 1347925baeddSChris Mason int skip_level = level; 1348051e1b9fSChris Mason int no_skips = 0; 1349925baeddSChris Mason struct extent_buffer *t; 1350925baeddSChris Mason 1351925baeddSChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1352925baeddSChris Mason if (!path->nodes[i]) 1353925baeddSChris Mason break; 1354925baeddSChris Mason if (!path->locks[i]) 1355925baeddSChris Mason break; 1356051e1b9fSChris Mason if (!no_skips && path->slots[i] == 0) { 1357925baeddSChris Mason skip_level = i + 1; 1358925baeddSChris Mason continue; 1359925baeddSChris Mason } 1360051e1b9fSChris Mason if (!no_skips && path->keep_locks) { 1361925baeddSChris Mason u32 nritems; 1362925baeddSChris Mason t = path->nodes[i]; 1363925baeddSChris Mason nritems = btrfs_header_nritems(t); 1364051e1b9fSChris Mason if (nritems < 1 || path->slots[i] >= nritems - 1) { 1365925baeddSChris Mason skip_level = i + 1; 1366925baeddSChris Mason continue; 1367925baeddSChris Mason } 1368925baeddSChris Mason } 1369051e1b9fSChris Mason if (skip_level < i && i >= lowest_unlock) 1370051e1b9fSChris Mason no_skips = 1; 1371051e1b9fSChris Mason 1372925baeddSChris Mason t = path->nodes[i]; 1373d80bb3f9SLiu Bo if (i >= lowest_unlock && i > skip_level) { 1374bd681513SChris Mason btrfs_tree_unlock_rw(t, path->locks[i]); 1375925baeddSChris Mason path->locks[i] = 0; 1376f7c79f30SChris Mason if (write_lock_level && 1377f7c79f30SChris Mason i > min_write_lock_level && 1378f7c79f30SChris Mason i <= *write_lock_level) { 1379f7c79f30SChris Mason *write_lock_level = i - 1; 1380f7c79f30SChris Mason } 1381925baeddSChris Mason } 1382925baeddSChris Mason } 1383925baeddSChris Mason } 1384925baeddSChris Mason 13853c69faecSChris Mason /* 1386c8c42864SChris Mason * helper function for btrfs_search_slot. The goal is to find a block 1387c8c42864SChris Mason * in cache without setting the path to blocking. If we find the block 1388c8c42864SChris Mason * we return zero and the path is unchanged. 1389c8c42864SChris Mason * 1390c8c42864SChris Mason * If we can't find the block, we set the path blocking and do some 1391c8c42864SChris Mason * reada. -EAGAIN is returned and the search must be repeated. 1392c8c42864SChris Mason */ 1393c8c42864SChris Mason static int 1394d07b8528SLiu Bo read_block_for_search(struct btrfs_root *root, struct btrfs_path *p, 1395c8c42864SChris Mason struct extent_buffer **eb_ret, int level, int slot, 1396cda79c54SDavid Sterba const struct btrfs_key *key) 1397c8c42864SChris Mason { 13980b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 1399c8c42864SChris Mason u64 blocknr; 1400c8c42864SChris Mason u64 gen; 1401c8c42864SChris Mason struct extent_buffer *tmp; 1402581c1760SQu Wenruo struct btrfs_key first_key; 140376a05b35SChris Mason int ret; 1404581c1760SQu Wenruo int parent_level; 1405c8c42864SChris Mason 1406213ff4b7SNikolay Borisov blocknr = btrfs_node_blockptr(*eb_ret, slot); 1407213ff4b7SNikolay Borisov gen = btrfs_node_ptr_generation(*eb_ret, slot); 1408213ff4b7SNikolay Borisov parent_level = btrfs_header_level(*eb_ret); 1409213ff4b7SNikolay Borisov btrfs_node_key_to_cpu(*eb_ret, &first_key, slot); 1410c8c42864SChris Mason 14110b246afaSJeff Mahoney tmp = find_extent_buffer(fs_info, blocknr); 1412cb44921aSChris Mason if (tmp) { 1413ace75066SFilipe Manana if (p->reada == READA_FORWARD_ALWAYS) 1414ace75066SFilipe Manana reada_for_search(fs_info, p, level, slot, key->objectid); 1415ace75066SFilipe Manana 1416b9fab919SChris Mason /* first we do an atomic uptodate check */ 1417b9fab919SChris Mason if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) { 1418448de471SQu Wenruo /* 1419448de471SQu Wenruo * Do extra check for first_key, eb can be stale due to 1420448de471SQu Wenruo * being cached, read from scrub, or have multiple 1421448de471SQu Wenruo * parents (shared tree blocks). 1422448de471SQu Wenruo */ 1423e064d5e9SDavid Sterba if (btrfs_verify_level_key(tmp, 1424448de471SQu Wenruo parent_level - 1, &first_key, gen)) { 1425448de471SQu Wenruo free_extent_buffer(tmp); 1426448de471SQu Wenruo return -EUCLEAN; 1427448de471SQu Wenruo } 1428c8c42864SChris Mason *eb_ret = tmp; 1429c8c42864SChris Mason return 0; 1430c8c42864SChris Mason } 1431bdf7c00eSJosef Bacik 1432b9fab919SChris Mason /* now we're allowed to do a blocking uptodate check */ 1433581c1760SQu Wenruo ret = btrfs_read_buffer(tmp, gen, parent_level - 1, &first_key); 1434bdf7c00eSJosef Bacik if (!ret) { 1435cb44921aSChris Mason *eb_ret = tmp; 1436cb44921aSChris Mason return 0; 1437cb44921aSChris Mason } 1438cb44921aSChris Mason free_extent_buffer(tmp); 1439b3b4aa74SDavid Sterba btrfs_release_path(p); 1440cb44921aSChris Mason return -EIO; 1441cb44921aSChris Mason } 1442c8c42864SChris Mason 1443c8c42864SChris Mason /* 1444c8c42864SChris Mason * reduce lock contention at high levels 1445c8c42864SChris Mason * of the btree by dropping locks before 144676a05b35SChris Mason * we read. Don't release the lock on the current 144776a05b35SChris Mason * level because we need to walk this node to figure 144876a05b35SChris Mason * out which blocks to read. 1449c8c42864SChris Mason */ 14508c594ea8SChris Mason btrfs_unlock_up_safe(p, level + 1); 14518c594ea8SChris Mason 1452e4058b54SDavid Sterba if (p->reada != READA_NONE) 14532ff7e61eSJeff Mahoney reada_for_search(fs_info, p, level, slot, key->objectid); 1454c8c42864SChris Mason 145576a05b35SChris Mason ret = -EAGAIN; 14561b7ec85eSJosef Bacik tmp = read_tree_block(fs_info, blocknr, root->root_key.objectid, 14571b7ec85eSJosef Bacik gen, parent_level - 1, &first_key); 145864c043deSLiu Bo if (!IS_ERR(tmp)) { 145976a05b35SChris Mason /* 146076a05b35SChris Mason * If the read above didn't mark this buffer up to date, 146176a05b35SChris Mason * it will never end up being up to date. Set ret to EIO now 146276a05b35SChris Mason * and give up so that our caller doesn't loop forever 146376a05b35SChris Mason * on our EAGAINs. 146476a05b35SChris Mason */ 1465e6a1d6fdSLiu Bo if (!extent_buffer_uptodate(tmp)) 146676a05b35SChris Mason ret = -EIO; 1467c8c42864SChris Mason free_extent_buffer(tmp); 1468c871b0f2SLiu Bo } else { 1469c871b0f2SLiu Bo ret = PTR_ERR(tmp); 147076a05b35SChris Mason } 147102a3307aSLiu Bo 147202a3307aSLiu Bo btrfs_release_path(p); 147376a05b35SChris Mason return ret; 1474c8c42864SChris Mason } 1475c8c42864SChris Mason 1476c8c42864SChris Mason /* 1477c8c42864SChris Mason * helper function for btrfs_search_slot. This does all of the checks 1478c8c42864SChris Mason * for node-level blocks and does any balancing required based on 1479c8c42864SChris Mason * the ins_len. 1480c8c42864SChris Mason * 1481c8c42864SChris Mason * If no extra work was required, zero is returned. If we had to 1482c8c42864SChris Mason * drop the path, -EAGAIN is returned and btrfs_search_slot must 1483c8c42864SChris Mason * start over 1484c8c42864SChris Mason */ 1485c8c42864SChris Mason static int 1486c8c42864SChris Mason setup_nodes_for_search(struct btrfs_trans_handle *trans, 1487c8c42864SChris Mason struct btrfs_root *root, struct btrfs_path *p, 1488bd681513SChris Mason struct extent_buffer *b, int level, int ins_len, 1489bd681513SChris Mason int *write_lock_level) 1490c8c42864SChris Mason { 14910b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 149295b982deSNikolay Borisov int ret = 0; 14930b246afaSJeff Mahoney 1494c8c42864SChris Mason if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >= 14950b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) { 1496c8c42864SChris Mason 1497bd681513SChris Mason if (*write_lock_level < level + 1) { 1498bd681513SChris Mason *write_lock_level = level + 1; 1499bd681513SChris Mason btrfs_release_path(p); 150095b982deSNikolay Borisov return -EAGAIN; 1501bd681513SChris Mason } 1502bd681513SChris Mason 1503bfb484d9SJosef Bacik reada_for_balance(p, level); 150495b982deSNikolay Borisov ret = split_node(trans, root, p, level); 1505c8c42864SChris Mason 1506c8c42864SChris Mason b = p->nodes[level]; 1507c8c42864SChris Mason } else if (ins_len < 0 && btrfs_header_nritems(b) < 15080b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) { 1509c8c42864SChris Mason 1510bd681513SChris Mason if (*write_lock_level < level + 1) { 1511bd681513SChris Mason *write_lock_level = level + 1; 1512bd681513SChris Mason btrfs_release_path(p); 151395b982deSNikolay Borisov return -EAGAIN; 1514bd681513SChris Mason } 1515bd681513SChris Mason 1516bfb484d9SJosef Bacik reada_for_balance(p, level); 151795b982deSNikolay Borisov ret = balance_level(trans, root, p, level); 151895b982deSNikolay Borisov if (ret) 151995b982deSNikolay Borisov return ret; 1520c8c42864SChris Mason 1521c8c42864SChris Mason b = p->nodes[level]; 1522c8c42864SChris Mason if (!b) { 1523b3b4aa74SDavid Sterba btrfs_release_path(p); 152495b982deSNikolay Borisov return -EAGAIN; 1525c8c42864SChris Mason } 1526c8c42864SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 1527c8c42864SChris Mason } 1528c8c42864SChris Mason return ret; 1529c8c42864SChris Mason } 1530c8c42864SChris Mason 1531381cf658SDavid Sterba int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path, 1532e33d5c3dSKelley Nielsen u64 iobjectid, u64 ioff, u8 key_type, 1533e33d5c3dSKelley Nielsen struct btrfs_key *found_key) 1534e33d5c3dSKelley Nielsen { 1535e33d5c3dSKelley Nielsen int ret; 1536e33d5c3dSKelley Nielsen struct btrfs_key key; 1537e33d5c3dSKelley Nielsen struct extent_buffer *eb; 1538381cf658SDavid Sterba 1539381cf658SDavid Sterba ASSERT(path); 15401d4c08e0SDavid Sterba ASSERT(found_key); 1541e33d5c3dSKelley Nielsen 1542e33d5c3dSKelley Nielsen key.type = key_type; 1543e33d5c3dSKelley Nielsen key.objectid = iobjectid; 1544e33d5c3dSKelley Nielsen key.offset = ioff; 1545e33d5c3dSKelley Nielsen 1546e33d5c3dSKelley Nielsen ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0); 15471d4c08e0SDavid Sterba if (ret < 0) 1548e33d5c3dSKelley Nielsen return ret; 1549e33d5c3dSKelley Nielsen 1550e33d5c3dSKelley Nielsen eb = path->nodes[0]; 1551e33d5c3dSKelley Nielsen if (ret && path->slots[0] >= btrfs_header_nritems(eb)) { 1552e33d5c3dSKelley Nielsen ret = btrfs_next_leaf(fs_root, path); 1553e33d5c3dSKelley Nielsen if (ret) 1554e33d5c3dSKelley Nielsen return ret; 1555e33d5c3dSKelley Nielsen eb = path->nodes[0]; 1556e33d5c3dSKelley Nielsen } 1557e33d5c3dSKelley Nielsen 1558e33d5c3dSKelley Nielsen btrfs_item_key_to_cpu(eb, found_key, path->slots[0]); 1559e33d5c3dSKelley Nielsen if (found_key->type != key.type || 1560e33d5c3dSKelley Nielsen found_key->objectid != key.objectid) 1561e33d5c3dSKelley Nielsen return 1; 1562e33d5c3dSKelley Nielsen 1563e33d5c3dSKelley Nielsen return 0; 1564e33d5c3dSKelley Nielsen } 1565e33d5c3dSKelley Nielsen 15661fc28d8eSLiu Bo static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root, 15671fc28d8eSLiu Bo struct btrfs_path *p, 15681fc28d8eSLiu Bo int write_lock_level) 15691fc28d8eSLiu Bo { 15701fc28d8eSLiu Bo struct btrfs_fs_info *fs_info = root->fs_info; 15711fc28d8eSLiu Bo struct extent_buffer *b; 15721fc28d8eSLiu Bo int root_lock; 15731fc28d8eSLiu Bo int level = 0; 15741fc28d8eSLiu Bo 15751fc28d8eSLiu Bo /* We try very hard to do read locks on the root */ 15761fc28d8eSLiu Bo root_lock = BTRFS_READ_LOCK; 15771fc28d8eSLiu Bo 15781fc28d8eSLiu Bo if (p->search_commit_root) { 1579be6821f8SFilipe Manana /* 1580be6821f8SFilipe Manana * The commit roots are read only so we always do read locks, 1581be6821f8SFilipe Manana * and we always must hold the commit_root_sem when doing 1582be6821f8SFilipe Manana * searches on them, the only exception is send where we don't 1583be6821f8SFilipe Manana * want to block transaction commits for a long time, so 1584be6821f8SFilipe Manana * we need to clone the commit root in order to avoid races 1585be6821f8SFilipe Manana * with transaction commits that create a snapshot of one of 1586be6821f8SFilipe Manana * the roots used by a send operation. 1587be6821f8SFilipe Manana */ 1588be6821f8SFilipe Manana if (p->need_commit_sem) { 15891fc28d8eSLiu Bo down_read(&fs_info->commit_root_sem); 1590be6821f8SFilipe Manana b = btrfs_clone_extent_buffer(root->commit_root); 1591be6821f8SFilipe Manana up_read(&fs_info->commit_root_sem); 1592be6821f8SFilipe Manana if (!b) 1593be6821f8SFilipe Manana return ERR_PTR(-ENOMEM); 1594be6821f8SFilipe Manana 1595be6821f8SFilipe Manana } else { 15961fc28d8eSLiu Bo b = root->commit_root; 159767439dadSDavid Sterba atomic_inc(&b->refs); 1598be6821f8SFilipe Manana } 15991fc28d8eSLiu Bo level = btrfs_header_level(b); 1600f9ddfd05SLiu Bo /* 1601f9ddfd05SLiu Bo * Ensure that all callers have set skip_locking when 1602f9ddfd05SLiu Bo * p->search_commit_root = 1. 1603f9ddfd05SLiu Bo */ 1604f9ddfd05SLiu Bo ASSERT(p->skip_locking == 1); 16051fc28d8eSLiu Bo 16061fc28d8eSLiu Bo goto out; 16071fc28d8eSLiu Bo } 16081fc28d8eSLiu Bo 16091fc28d8eSLiu Bo if (p->skip_locking) { 16101fc28d8eSLiu Bo b = btrfs_root_node(root); 16111fc28d8eSLiu Bo level = btrfs_header_level(b); 16121fc28d8eSLiu Bo goto out; 16131fc28d8eSLiu Bo } 16141fc28d8eSLiu Bo 16151fc28d8eSLiu Bo /* 1616662c653bSLiu Bo * If the level is set to maximum, we can skip trying to get the read 1617662c653bSLiu Bo * lock. 1618662c653bSLiu Bo */ 1619662c653bSLiu Bo if (write_lock_level < BTRFS_MAX_LEVEL) { 1620662c653bSLiu Bo /* 1621662c653bSLiu Bo * We don't know the level of the root node until we actually 1622662c653bSLiu Bo * have it read locked 16231fc28d8eSLiu Bo */ 16241bb96598SJosef Bacik b = btrfs_read_lock_root_node(root); 16251fc28d8eSLiu Bo level = btrfs_header_level(b); 16261fc28d8eSLiu Bo if (level > write_lock_level) 16271fc28d8eSLiu Bo goto out; 16281fc28d8eSLiu Bo 1629662c653bSLiu Bo /* Whoops, must trade for write lock */ 16301fc28d8eSLiu Bo btrfs_tree_read_unlock(b); 16311fc28d8eSLiu Bo free_extent_buffer(b); 1632662c653bSLiu Bo } 1633662c653bSLiu Bo 16341fc28d8eSLiu Bo b = btrfs_lock_root_node(root); 16351fc28d8eSLiu Bo root_lock = BTRFS_WRITE_LOCK; 16361fc28d8eSLiu Bo 16371fc28d8eSLiu Bo /* The level might have changed, check again */ 16381fc28d8eSLiu Bo level = btrfs_header_level(b); 16391fc28d8eSLiu Bo 16401fc28d8eSLiu Bo out: 16411fc28d8eSLiu Bo p->nodes[level] = b; 16421fc28d8eSLiu Bo if (!p->skip_locking) 16431fc28d8eSLiu Bo p->locks[level] = root_lock; 16441fc28d8eSLiu Bo /* 16451fc28d8eSLiu Bo * Callers are responsible for dropping b's references. 16461fc28d8eSLiu Bo */ 16471fc28d8eSLiu Bo return b; 16481fc28d8eSLiu Bo } 16491fc28d8eSLiu Bo 16501fc28d8eSLiu Bo 1651c8c42864SChris Mason /* 16524271eceaSNikolay Borisov * btrfs_search_slot - look for a key in a tree and perform necessary 16534271eceaSNikolay Borisov * modifications to preserve tree invariants. 165474123bd7SChris Mason * 16554271eceaSNikolay Borisov * @trans: Handle of transaction, used when modifying the tree 16564271eceaSNikolay Borisov * @p: Holds all btree nodes along the search path 16574271eceaSNikolay Borisov * @root: The root node of the tree 16584271eceaSNikolay Borisov * @key: The key we are looking for 16599a664971Sethanwu * @ins_len: Indicates purpose of search: 16609a664971Sethanwu * >0 for inserts it's size of item inserted (*) 16619a664971Sethanwu * <0 for deletions 16629a664971Sethanwu * 0 for plain searches, not modifying the tree 16639a664971Sethanwu * 16649a664971Sethanwu * (*) If size of item inserted doesn't include 16659a664971Sethanwu * sizeof(struct btrfs_item), then p->search_for_extension must 16669a664971Sethanwu * be set. 16674271eceaSNikolay Borisov * @cow: boolean should CoW operations be performed. Must always be 1 16684271eceaSNikolay Borisov * when modifying the tree. 166997571fd0SChris Mason * 16704271eceaSNikolay Borisov * If @ins_len > 0, nodes and leaves will be split as we walk down the tree. 16714271eceaSNikolay Borisov * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible) 16724271eceaSNikolay Borisov * 16734271eceaSNikolay Borisov * If @key is found, 0 is returned and you can find the item in the leaf level 16744271eceaSNikolay Borisov * of the path (level 0) 16754271eceaSNikolay Borisov * 16764271eceaSNikolay Borisov * If @key isn't found, 1 is returned and the leaf level of the path (level 0) 16774271eceaSNikolay Borisov * points to the slot where it should be inserted 16784271eceaSNikolay Borisov * 16794271eceaSNikolay Borisov * If an error is encountered while searching the tree a negative error number 16804271eceaSNikolay Borisov * is returned 168174123bd7SChris Mason */ 1682310712b2SOmar Sandoval int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1683310712b2SOmar Sandoval const struct btrfs_key *key, struct btrfs_path *p, 1684310712b2SOmar Sandoval int ins_len, int cow) 1685be0e5c09SChris Mason { 16865f39d397SChris Mason struct extent_buffer *b; 1687be0e5c09SChris Mason int slot; 1688be0e5c09SChris Mason int ret; 168933c66f43SYan Zheng int err; 1690be0e5c09SChris Mason int level; 1691925baeddSChris Mason int lowest_unlock = 1; 1692bd681513SChris Mason /* everything at write_lock_level or lower must be write locked */ 1693bd681513SChris Mason int write_lock_level = 0; 16949f3a7427SChris Mason u8 lowest_level = 0; 1695f7c79f30SChris Mason int min_write_lock_level; 1696d7396f07SFilipe David Borba Manana int prev_cmp; 16979f3a7427SChris Mason 16986702ed49SChris Mason lowest_level = p->lowest_level; 1699323ac95bSChris Mason WARN_ON(lowest_level && ins_len > 0); 170022b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 1701eb653de1SFilipe David Borba Manana BUG_ON(!cow && ins_len); 170225179201SJosef Bacik 1703bd681513SChris Mason if (ins_len < 0) { 1704925baeddSChris Mason lowest_unlock = 2; 170565b51a00SChris Mason 1706bd681513SChris Mason /* when we are removing items, we might have to go up to level 1707bd681513SChris Mason * two as we update tree pointers Make sure we keep write 1708bd681513SChris Mason * for those levels as well 1709bd681513SChris Mason */ 1710bd681513SChris Mason write_lock_level = 2; 1711bd681513SChris Mason } else if (ins_len > 0) { 1712bd681513SChris Mason /* 1713bd681513SChris Mason * for inserting items, make sure we have a write lock on 1714bd681513SChris Mason * level 1 so we can update keys 1715bd681513SChris Mason */ 1716bd681513SChris Mason write_lock_level = 1; 1717bd681513SChris Mason } 1718bd681513SChris Mason 1719bd681513SChris Mason if (!cow) 1720bd681513SChris Mason write_lock_level = -1; 1721bd681513SChris Mason 172209a2a8f9SJosef Bacik if (cow && (p->keep_locks || p->lowest_level)) 1723bd681513SChris Mason write_lock_level = BTRFS_MAX_LEVEL; 1724bd681513SChris Mason 1725f7c79f30SChris Mason min_write_lock_level = write_lock_level; 1726f7c79f30SChris Mason 1727bb803951SChris Mason again: 1728d7396f07SFilipe David Borba Manana prev_cmp = -1; 17291fc28d8eSLiu Bo b = btrfs_search_slot_get_root(root, p, write_lock_level); 1730be6821f8SFilipe Manana if (IS_ERR(b)) { 1731be6821f8SFilipe Manana ret = PTR_ERR(b); 1732be6821f8SFilipe Manana goto done; 1733be6821f8SFilipe Manana } 1734925baeddSChris Mason 1735eb60ceacSChris Mason while (b) { 1736f624d976SQu Wenruo int dec = 0; 1737f624d976SQu Wenruo 17385f39d397SChris Mason level = btrfs_header_level(b); 173965b51a00SChris Mason 174002217ed2SChris Mason if (cow) { 17419ea2c7c9SNikolay Borisov bool last_level = (level == (BTRFS_MAX_LEVEL - 1)); 17429ea2c7c9SNikolay Borisov 1743c8c42864SChris Mason /* 1744c8c42864SChris Mason * if we don't really need to cow this block 1745c8c42864SChris Mason * then we don't want to set the path blocking, 1746c8c42864SChris Mason * so we test it here 1747c8c42864SChris Mason */ 17485963ffcaSJosef Bacik if (!should_cow_block(trans, root, b)) 174965b51a00SChris Mason goto cow_done; 17505d4f98a2SYan Zheng 1751bd681513SChris Mason /* 1752bd681513SChris Mason * must have write locks on this node and the 1753bd681513SChris Mason * parent 1754bd681513SChris Mason */ 17555124e00eSJosef Bacik if (level > write_lock_level || 17565124e00eSJosef Bacik (level + 1 > write_lock_level && 17575124e00eSJosef Bacik level + 1 < BTRFS_MAX_LEVEL && 17585124e00eSJosef Bacik p->nodes[level + 1])) { 1759bd681513SChris Mason write_lock_level = level + 1; 1760bd681513SChris Mason btrfs_release_path(p); 1761bd681513SChris Mason goto again; 1762bd681513SChris Mason } 1763bd681513SChris Mason 17649ea2c7c9SNikolay Borisov if (last_level) 17659ea2c7c9SNikolay Borisov err = btrfs_cow_block(trans, root, b, NULL, 0, 17669631e4ccSJosef Bacik &b, 17679631e4ccSJosef Bacik BTRFS_NESTING_COW); 17689ea2c7c9SNikolay Borisov else 176933c66f43SYan Zheng err = btrfs_cow_block(trans, root, b, 1770e20d96d6SChris Mason p->nodes[level + 1], 17719631e4ccSJosef Bacik p->slots[level + 1], &b, 17729631e4ccSJosef Bacik BTRFS_NESTING_COW); 177333c66f43SYan Zheng if (err) { 177433c66f43SYan Zheng ret = err; 177565b51a00SChris Mason goto done; 177654aa1f4dSChris Mason } 177702217ed2SChris Mason } 177865b51a00SChris Mason cow_done: 1779eb60ceacSChris Mason p->nodes[level] = b; 178052398340SLiu Bo /* 178152398340SLiu Bo * Leave path with blocking locks to avoid massive 178252398340SLiu Bo * lock context switch, this is made on purpose. 178352398340SLiu Bo */ 1784b4ce94deSChris Mason 1785b4ce94deSChris Mason /* 1786b4ce94deSChris Mason * we have a lock on b and as long as we aren't changing 1787b4ce94deSChris Mason * the tree, there is no way to for the items in b to change. 1788b4ce94deSChris Mason * It is safe to drop the lock on our parent before we 1789b4ce94deSChris Mason * go through the expensive btree search on b. 1790b4ce94deSChris Mason * 1791eb653de1SFilipe David Borba Manana * If we're inserting or deleting (ins_len != 0), then we might 1792eb653de1SFilipe David Borba Manana * be changing slot zero, which may require changing the parent. 1793eb653de1SFilipe David Borba Manana * So, we can't drop the lock until after we know which slot 1794eb653de1SFilipe David Borba Manana * we're operating on. 1795b4ce94deSChris Mason */ 1796eb653de1SFilipe David Borba Manana if (!ins_len && !p->keep_locks) { 1797eb653de1SFilipe David Borba Manana int u = level + 1; 1798eb653de1SFilipe David Borba Manana 1799eb653de1SFilipe David Borba Manana if (u < BTRFS_MAX_LEVEL && p->locks[u]) { 1800eb653de1SFilipe David Borba Manana btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]); 1801eb653de1SFilipe David Borba Manana p->locks[u] = 0; 1802eb653de1SFilipe David Borba Manana } 1803eb653de1SFilipe David Borba Manana } 1804b4ce94deSChris Mason 1805995e9a16SNikolay Borisov /* 1806995e9a16SNikolay Borisov * If btrfs_bin_search returns an exact match (prev_cmp == 0) 1807995e9a16SNikolay Borisov * we can safely assume the target key will always be in slot 0 1808995e9a16SNikolay Borisov * on lower levels due to the invariants BTRFS' btree provides, 1809995e9a16SNikolay Borisov * namely that a btrfs_key_ptr entry always points to the 1810995e9a16SNikolay Borisov * lowest key in the child node, thus we can skip searching 1811995e9a16SNikolay Borisov * lower levels 1812995e9a16SNikolay Borisov */ 1813995e9a16SNikolay Borisov if (prev_cmp == 0) { 1814995e9a16SNikolay Borisov slot = 0; 1815995e9a16SNikolay Borisov ret = 0; 1816995e9a16SNikolay Borisov } else { 1817995e9a16SNikolay Borisov ret = btrfs_bin_search(b, key, &slot); 1818995e9a16SNikolay Borisov prev_cmp = ret; 1819415b35a5SLiu Bo if (ret < 0) 1820415b35a5SLiu Bo goto done; 1821995e9a16SNikolay Borisov } 1822b4ce94deSChris Mason 1823f624d976SQu Wenruo if (level == 0) { 1824be0e5c09SChris Mason p->slots[level] = slot; 18259a664971Sethanwu /* 18269a664971Sethanwu * Item key already exists. In this case, if we are 18279a664971Sethanwu * allowed to insert the item (for example, in dir_item 18289a664971Sethanwu * case, item key collision is allowed), it will be 18299a664971Sethanwu * merged with the original item. Only the item size 18309a664971Sethanwu * grows, no new btrfs item will be added. If 18319a664971Sethanwu * search_for_extension is not set, ins_len already 18329a664971Sethanwu * accounts the size btrfs_item, deduct it here so leaf 18339a664971Sethanwu * space check will be correct. 18349a664971Sethanwu */ 18359a664971Sethanwu if (ret == 0 && ins_len > 0 && !p->search_for_extension) { 18369a664971Sethanwu ASSERT(ins_len >= sizeof(struct btrfs_item)); 18379a664971Sethanwu ins_len -= sizeof(struct btrfs_item); 18389a664971Sethanwu } 183987b29b20SYan Zheng if (ins_len > 0 && 1840e902baacSDavid Sterba btrfs_leaf_free_space(b) < ins_len) { 1841bd681513SChris Mason if (write_lock_level < 1) { 1842bd681513SChris Mason write_lock_level = 1; 1843bd681513SChris Mason btrfs_release_path(p); 1844bd681513SChris Mason goto again; 1845bd681513SChris Mason } 1846bd681513SChris Mason 184733c66f43SYan Zheng err = split_leaf(trans, root, key, 1848cc0c5538SChris Mason p, ins_len, ret == 0); 1849b4ce94deSChris Mason 185033c66f43SYan Zheng BUG_ON(err > 0); 185133c66f43SYan Zheng if (err) { 185233c66f43SYan Zheng ret = err; 185365b51a00SChris Mason goto done; 185465b51a00SChris Mason } 18555c680ed6SChris Mason } 1856459931ecSChris Mason if (!p->search_for_split) 1857f7c79f30SChris Mason unlock_up(p, level, lowest_unlock, 18584b6f8e96SLiu Bo min_write_lock_level, NULL); 185965b51a00SChris Mason goto done; 186065b51a00SChris Mason } 1861f624d976SQu Wenruo if (ret && slot > 0) { 1862f624d976SQu Wenruo dec = 1; 1863f624d976SQu Wenruo slot--; 1864f624d976SQu Wenruo } 1865f624d976SQu Wenruo p->slots[level] = slot; 1866f624d976SQu Wenruo err = setup_nodes_for_search(trans, root, p, b, level, ins_len, 1867f624d976SQu Wenruo &write_lock_level); 1868f624d976SQu Wenruo if (err == -EAGAIN) 1869f624d976SQu Wenruo goto again; 1870f624d976SQu Wenruo if (err) { 1871f624d976SQu Wenruo ret = err; 1872f624d976SQu Wenruo goto done; 1873f624d976SQu Wenruo } 1874f624d976SQu Wenruo b = p->nodes[level]; 1875f624d976SQu Wenruo slot = p->slots[level]; 1876f624d976SQu Wenruo 1877f624d976SQu Wenruo /* 1878f624d976SQu Wenruo * Slot 0 is special, if we change the key we have to update 1879f624d976SQu Wenruo * the parent pointer which means we must have a write lock on 1880f624d976SQu Wenruo * the parent 1881f624d976SQu Wenruo */ 1882f624d976SQu Wenruo if (slot == 0 && ins_len && write_lock_level < level + 1) { 1883f624d976SQu Wenruo write_lock_level = level + 1; 1884f624d976SQu Wenruo btrfs_release_path(p); 1885f624d976SQu Wenruo goto again; 1886f624d976SQu Wenruo } 1887f624d976SQu Wenruo 1888f624d976SQu Wenruo unlock_up(p, level, lowest_unlock, min_write_lock_level, 1889f624d976SQu Wenruo &write_lock_level); 1890f624d976SQu Wenruo 1891f624d976SQu Wenruo if (level == lowest_level) { 1892f624d976SQu Wenruo if (dec) 1893f624d976SQu Wenruo p->slots[level]++; 1894f624d976SQu Wenruo goto done; 1895f624d976SQu Wenruo } 1896f624d976SQu Wenruo 1897f624d976SQu Wenruo err = read_block_for_search(root, p, &b, level, slot, key); 1898f624d976SQu Wenruo if (err == -EAGAIN) 1899f624d976SQu Wenruo goto again; 1900f624d976SQu Wenruo if (err) { 1901f624d976SQu Wenruo ret = err; 1902f624d976SQu Wenruo goto done; 1903f624d976SQu Wenruo } 1904f624d976SQu Wenruo 1905f624d976SQu Wenruo if (!p->skip_locking) { 1906f624d976SQu Wenruo level = btrfs_header_level(b); 1907f624d976SQu Wenruo if (level <= write_lock_level) { 1908f624d976SQu Wenruo btrfs_tree_lock(b); 1909f624d976SQu Wenruo p->locks[level] = BTRFS_WRITE_LOCK; 1910f624d976SQu Wenruo } else { 1911fe596ca3SJosef Bacik btrfs_tree_read_lock(b); 1912f624d976SQu Wenruo p->locks[level] = BTRFS_READ_LOCK; 1913f624d976SQu Wenruo } 1914f624d976SQu Wenruo p->nodes[level] = b; 1915f624d976SQu Wenruo } 191665b51a00SChris Mason } 191765b51a00SChris Mason ret = 1; 191865b51a00SChris Mason done: 19195f5bc6b1SFilipe Manana if (ret < 0 && !p->skip_release_on_error) 1920b3b4aa74SDavid Sterba btrfs_release_path(p); 1921be0e5c09SChris Mason return ret; 1922be0e5c09SChris Mason } 1923f75e2b79SJosef Bacik ALLOW_ERROR_INJECTION(btrfs_search_slot, ERRNO); 1924be0e5c09SChris Mason 192574123bd7SChris Mason /* 19265d9e75c4SJan Schmidt * Like btrfs_search_slot, this looks for a key in the given tree. It uses the 19275d9e75c4SJan Schmidt * current state of the tree together with the operations recorded in the tree 19285d9e75c4SJan Schmidt * modification log to search for the key in a previous version of this tree, as 19295d9e75c4SJan Schmidt * denoted by the time_seq parameter. 19305d9e75c4SJan Schmidt * 19315d9e75c4SJan Schmidt * Naturally, there is no support for insert, delete or cow operations. 19325d9e75c4SJan Schmidt * 19335d9e75c4SJan Schmidt * The resulting path and return value will be set up as if we called 19345d9e75c4SJan Schmidt * btrfs_search_slot at that point in time with ins_len and cow both set to 0. 19355d9e75c4SJan Schmidt */ 1936310712b2SOmar Sandoval int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key, 19375d9e75c4SJan Schmidt struct btrfs_path *p, u64 time_seq) 19385d9e75c4SJan Schmidt { 19390b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 19405d9e75c4SJan Schmidt struct extent_buffer *b; 19415d9e75c4SJan Schmidt int slot; 19425d9e75c4SJan Schmidt int ret; 19435d9e75c4SJan Schmidt int err; 19445d9e75c4SJan Schmidt int level; 19455d9e75c4SJan Schmidt int lowest_unlock = 1; 19465d9e75c4SJan Schmidt u8 lowest_level = 0; 19475d9e75c4SJan Schmidt 19485d9e75c4SJan Schmidt lowest_level = p->lowest_level; 19495d9e75c4SJan Schmidt WARN_ON(p->nodes[0] != NULL); 19505d9e75c4SJan Schmidt 19515d9e75c4SJan Schmidt if (p->search_commit_root) { 19525d9e75c4SJan Schmidt BUG_ON(time_seq); 19535d9e75c4SJan Schmidt return btrfs_search_slot(NULL, root, key, p, 0, 0); 19545d9e75c4SJan Schmidt } 19555d9e75c4SJan Schmidt 19565d9e75c4SJan Schmidt again: 1957f3a84ccdSFilipe Manana b = btrfs_get_old_root(root, time_seq); 1958315bed43SNikolay Borisov if (!b) { 1959315bed43SNikolay Borisov ret = -EIO; 1960315bed43SNikolay Borisov goto done; 1961315bed43SNikolay Borisov } 19625d9e75c4SJan Schmidt level = btrfs_header_level(b); 19635d9e75c4SJan Schmidt p->locks[level] = BTRFS_READ_LOCK; 19645d9e75c4SJan Schmidt 19655d9e75c4SJan Schmidt while (b) { 1966abe9339dSQu Wenruo int dec = 0; 1967abe9339dSQu Wenruo 19685d9e75c4SJan Schmidt level = btrfs_header_level(b); 19695d9e75c4SJan Schmidt p->nodes[level] = b; 19705d9e75c4SJan Schmidt 19715d9e75c4SJan Schmidt /* 19725d9e75c4SJan Schmidt * we have a lock on b and as long as we aren't changing 19735d9e75c4SJan Schmidt * the tree, there is no way to for the items in b to change. 19745d9e75c4SJan Schmidt * It is safe to drop the lock on our parent before we 19755d9e75c4SJan Schmidt * go through the expensive btree search on b. 19765d9e75c4SJan Schmidt */ 19775d9e75c4SJan Schmidt btrfs_unlock_up_safe(p, level + 1); 19785d9e75c4SJan Schmidt 1979995e9a16SNikolay Borisov ret = btrfs_bin_search(b, key, &slot); 1980cbca7d59SFilipe Manana if (ret < 0) 1981cbca7d59SFilipe Manana goto done; 19825d9e75c4SJan Schmidt 1983abe9339dSQu Wenruo if (level == 0) { 1984abe9339dSQu Wenruo p->slots[level] = slot; 1985abe9339dSQu Wenruo unlock_up(p, level, lowest_unlock, 0, NULL); 1986abe9339dSQu Wenruo goto done; 1987abe9339dSQu Wenruo } 1988abe9339dSQu Wenruo 19895d9e75c4SJan Schmidt if (ret && slot > 0) { 19905d9e75c4SJan Schmidt dec = 1; 1991abe9339dSQu Wenruo slot--; 19925d9e75c4SJan Schmidt } 19935d9e75c4SJan Schmidt p->slots[level] = slot; 19945d9e75c4SJan Schmidt unlock_up(p, level, lowest_unlock, 0, NULL); 19955d9e75c4SJan Schmidt 19965d9e75c4SJan Schmidt if (level == lowest_level) { 19975d9e75c4SJan Schmidt if (dec) 19985d9e75c4SJan Schmidt p->slots[level]++; 19995d9e75c4SJan Schmidt goto done; 20005d9e75c4SJan Schmidt } 20015d9e75c4SJan Schmidt 2002abe9339dSQu Wenruo err = read_block_for_search(root, p, &b, level, slot, key); 20035d9e75c4SJan Schmidt if (err == -EAGAIN) 20045d9e75c4SJan Schmidt goto again; 20055d9e75c4SJan Schmidt if (err) { 20065d9e75c4SJan Schmidt ret = err; 20075d9e75c4SJan Schmidt goto done; 20085d9e75c4SJan Schmidt } 20095d9e75c4SJan Schmidt 20105d9e75c4SJan Schmidt level = btrfs_header_level(b); 20115d9e75c4SJan Schmidt btrfs_tree_read_lock(b); 2012f3a84ccdSFilipe Manana b = btrfs_tree_mod_log_rewind(fs_info, p, b, time_seq); 2013db7f3436SJosef Bacik if (!b) { 2014db7f3436SJosef Bacik ret = -ENOMEM; 2015db7f3436SJosef Bacik goto done; 2016db7f3436SJosef Bacik } 20175d9e75c4SJan Schmidt p->locks[level] = BTRFS_READ_LOCK; 20185d9e75c4SJan Schmidt p->nodes[level] = b; 20195d9e75c4SJan Schmidt } 20205d9e75c4SJan Schmidt ret = 1; 20215d9e75c4SJan Schmidt done: 20225d9e75c4SJan Schmidt if (ret < 0) 20235d9e75c4SJan Schmidt btrfs_release_path(p); 20245d9e75c4SJan Schmidt 20255d9e75c4SJan Schmidt return ret; 20265d9e75c4SJan Schmidt } 20275d9e75c4SJan Schmidt 20285d9e75c4SJan Schmidt /* 20292f38b3e1SArne Jansen * helper to use instead of search slot if no exact match is needed but 20302f38b3e1SArne Jansen * instead the next or previous item should be returned. 20312f38b3e1SArne Jansen * When find_higher is true, the next higher item is returned, the next lower 20322f38b3e1SArne Jansen * otherwise. 20332f38b3e1SArne Jansen * When return_any and find_higher are both true, and no higher item is found, 20342f38b3e1SArne Jansen * return the next lower instead. 20352f38b3e1SArne Jansen * When return_any is true and find_higher is false, and no lower item is found, 20362f38b3e1SArne Jansen * return the next higher instead. 20372f38b3e1SArne Jansen * It returns 0 if any item is found, 1 if none is found (tree empty), and 20382f38b3e1SArne Jansen * < 0 on error 20392f38b3e1SArne Jansen */ 20402f38b3e1SArne Jansen int btrfs_search_slot_for_read(struct btrfs_root *root, 2041310712b2SOmar Sandoval const struct btrfs_key *key, 2042310712b2SOmar Sandoval struct btrfs_path *p, int find_higher, 2043310712b2SOmar Sandoval int return_any) 20442f38b3e1SArne Jansen { 20452f38b3e1SArne Jansen int ret; 20462f38b3e1SArne Jansen struct extent_buffer *leaf; 20472f38b3e1SArne Jansen 20482f38b3e1SArne Jansen again: 20492f38b3e1SArne Jansen ret = btrfs_search_slot(NULL, root, key, p, 0, 0); 20502f38b3e1SArne Jansen if (ret <= 0) 20512f38b3e1SArne Jansen return ret; 20522f38b3e1SArne Jansen /* 20532f38b3e1SArne Jansen * a return value of 1 means the path is at the position where the 20542f38b3e1SArne Jansen * item should be inserted. Normally this is the next bigger item, 20552f38b3e1SArne Jansen * but in case the previous item is the last in a leaf, path points 20562f38b3e1SArne Jansen * to the first free slot in the previous leaf, i.e. at an invalid 20572f38b3e1SArne Jansen * item. 20582f38b3e1SArne Jansen */ 20592f38b3e1SArne Jansen leaf = p->nodes[0]; 20602f38b3e1SArne Jansen 20612f38b3e1SArne Jansen if (find_higher) { 20622f38b3e1SArne Jansen if (p->slots[0] >= btrfs_header_nritems(leaf)) { 20632f38b3e1SArne Jansen ret = btrfs_next_leaf(root, p); 20642f38b3e1SArne Jansen if (ret <= 0) 20652f38b3e1SArne Jansen return ret; 20662f38b3e1SArne Jansen if (!return_any) 20672f38b3e1SArne Jansen return 1; 20682f38b3e1SArne Jansen /* 20692f38b3e1SArne Jansen * no higher item found, return the next 20702f38b3e1SArne Jansen * lower instead 20712f38b3e1SArne Jansen */ 20722f38b3e1SArne Jansen return_any = 0; 20732f38b3e1SArne Jansen find_higher = 0; 20742f38b3e1SArne Jansen btrfs_release_path(p); 20752f38b3e1SArne Jansen goto again; 20762f38b3e1SArne Jansen } 20772f38b3e1SArne Jansen } else { 20782f38b3e1SArne Jansen if (p->slots[0] == 0) { 20792f38b3e1SArne Jansen ret = btrfs_prev_leaf(root, p); 2080e6793769SArne Jansen if (ret < 0) 20812f38b3e1SArne Jansen return ret; 2082e6793769SArne Jansen if (!ret) { 208323c6bf6aSFilipe David Borba Manana leaf = p->nodes[0]; 208423c6bf6aSFilipe David Borba Manana if (p->slots[0] == btrfs_header_nritems(leaf)) 208523c6bf6aSFilipe David Borba Manana p->slots[0]--; 2086e6793769SArne Jansen return 0; 2087e6793769SArne Jansen } 20882f38b3e1SArne Jansen if (!return_any) 20892f38b3e1SArne Jansen return 1; 20902f38b3e1SArne Jansen /* 20912f38b3e1SArne Jansen * no lower item found, return the next 20922f38b3e1SArne Jansen * higher instead 20932f38b3e1SArne Jansen */ 20942f38b3e1SArne Jansen return_any = 0; 20952f38b3e1SArne Jansen find_higher = 1; 20962f38b3e1SArne Jansen btrfs_release_path(p); 20972f38b3e1SArne Jansen goto again; 2098e6793769SArne Jansen } else { 20992f38b3e1SArne Jansen --p->slots[0]; 21002f38b3e1SArne Jansen } 21012f38b3e1SArne Jansen } 21022f38b3e1SArne Jansen return 0; 21032f38b3e1SArne Jansen } 21042f38b3e1SArne Jansen 21052f38b3e1SArne Jansen /* 210674123bd7SChris Mason * adjust the pointers going up the tree, starting at level 210774123bd7SChris Mason * making sure the right key of each node is points to 'key'. 210874123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 210974123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 211074123bd7SChris Mason * higher levels 2111aa5d6bedSChris Mason * 211274123bd7SChris Mason */ 2113b167fa91SNikolay Borisov static void fixup_low_keys(struct btrfs_path *path, 21145f39d397SChris Mason struct btrfs_disk_key *key, int level) 2115be0e5c09SChris Mason { 2116be0e5c09SChris Mason int i; 21175f39d397SChris Mason struct extent_buffer *t; 21180e82bcfeSDavid Sterba int ret; 21195f39d397SChris Mason 2120234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 2121be0e5c09SChris Mason int tslot = path->slots[i]; 21220e82bcfeSDavid Sterba 2123eb60ceacSChris Mason if (!path->nodes[i]) 2124be0e5c09SChris Mason break; 21255f39d397SChris Mason t = path->nodes[i]; 2126f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(t, tslot, 2127f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REPLACE, GFP_ATOMIC); 21280e82bcfeSDavid Sterba BUG_ON(ret < 0); 21295f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 2130d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 2131be0e5c09SChris Mason if (tslot != 0) 2132be0e5c09SChris Mason break; 2133be0e5c09SChris Mason } 2134be0e5c09SChris Mason } 2135be0e5c09SChris Mason 213674123bd7SChris Mason /* 213731840ae1SZheng Yan * update item key. 213831840ae1SZheng Yan * 213931840ae1SZheng Yan * This function isn't completely safe. It's the caller's responsibility 214031840ae1SZheng Yan * that the new key won't break the order 214131840ae1SZheng Yan */ 2142b7a0365eSDaniel Dressler void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info, 2143b7a0365eSDaniel Dressler struct btrfs_path *path, 2144310712b2SOmar Sandoval const struct btrfs_key *new_key) 214531840ae1SZheng Yan { 214631840ae1SZheng Yan struct btrfs_disk_key disk_key; 214731840ae1SZheng Yan struct extent_buffer *eb; 214831840ae1SZheng Yan int slot; 214931840ae1SZheng Yan 215031840ae1SZheng Yan eb = path->nodes[0]; 215131840ae1SZheng Yan slot = path->slots[0]; 215231840ae1SZheng Yan if (slot > 0) { 215331840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot - 1); 21547c15d410SQu Wenruo if (unlikely(comp_keys(&disk_key, new_key) >= 0)) { 21557c15d410SQu Wenruo btrfs_crit(fs_info, 21567c15d410SQu Wenruo "slot %u key (%llu %u %llu) new key (%llu %u %llu)", 21577c15d410SQu Wenruo slot, btrfs_disk_key_objectid(&disk_key), 21587c15d410SQu Wenruo btrfs_disk_key_type(&disk_key), 21597c15d410SQu Wenruo btrfs_disk_key_offset(&disk_key), 21607c15d410SQu Wenruo new_key->objectid, new_key->type, 21617c15d410SQu Wenruo new_key->offset); 21627c15d410SQu Wenruo btrfs_print_leaf(eb); 21637c15d410SQu Wenruo BUG(); 21647c15d410SQu Wenruo } 216531840ae1SZheng Yan } 216631840ae1SZheng Yan if (slot < btrfs_header_nritems(eb) - 1) { 216731840ae1SZheng Yan btrfs_item_key(eb, &disk_key, slot + 1); 21687c15d410SQu Wenruo if (unlikely(comp_keys(&disk_key, new_key) <= 0)) { 21697c15d410SQu Wenruo btrfs_crit(fs_info, 21707c15d410SQu Wenruo "slot %u key (%llu %u %llu) new key (%llu %u %llu)", 21717c15d410SQu Wenruo slot, btrfs_disk_key_objectid(&disk_key), 21727c15d410SQu Wenruo btrfs_disk_key_type(&disk_key), 21737c15d410SQu Wenruo btrfs_disk_key_offset(&disk_key), 21747c15d410SQu Wenruo new_key->objectid, new_key->type, 21757c15d410SQu Wenruo new_key->offset); 21767c15d410SQu Wenruo btrfs_print_leaf(eb); 21777c15d410SQu Wenruo BUG(); 21787c15d410SQu Wenruo } 217931840ae1SZheng Yan } 218031840ae1SZheng Yan 218131840ae1SZheng Yan btrfs_cpu_key_to_disk(&disk_key, new_key); 218231840ae1SZheng Yan btrfs_set_item_key(eb, &disk_key, slot); 218331840ae1SZheng Yan btrfs_mark_buffer_dirty(eb); 218431840ae1SZheng Yan if (slot == 0) 2185b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 218631840ae1SZheng Yan } 218731840ae1SZheng Yan 218831840ae1SZheng Yan /* 2189d16c702fSQu Wenruo * Check key order of two sibling extent buffers. 2190d16c702fSQu Wenruo * 2191d16c702fSQu Wenruo * Return true if something is wrong. 2192d16c702fSQu Wenruo * Return false if everything is fine. 2193d16c702fSQu Wenruo * 2194d16c702fSQu Wenruo * Tree-checker only works inside one tree block, thus the following 2195d16c702fSQu Wenruo * corruption can not be detected by tree-checker: 2196d16c702fSQu Wenruo * 2197d16c702fSQu Wenruo * Leaf @left | Leaf @right 2198d16c702fSQu Wenruo * -------------------------------------------------------------- 2199d16c702fSQu Wenruo * | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 | 2200d16c702fSQu Wenruo * 2201d16c702fSQu Wenruo * Key f6 in leaf @left itself is valid, but not valid when the next 2202d16c702fSQu Wenruo * key in leaf @right is 7. 2203d16c702fSQu Wenruo * This can only be checked at tree block merge time. 2204d16c702fSQu Wenruo * And since tree checker has ensured all key order in each tree block 2205d16c702fSQu Wenruo * is correct, we only need to bother the last key of @left and the first 2206d16c702fSQu Wenruo * key of @right. 2207d16c702fSQu Wenruo */ 2208d16c702fSQu Wenruo static bool check_sibling_keys(struct extent_buffer *left, 2209d16c702fSQu Wenruo struct extent_buffer *right) 2210d16c702fSQu Wenruo { 2211d16c702fSQu Wenruo struct btrfs_key left_last; 2212d16c702fSQu Wenruo struct btrfs_key right_first; 2213d16c702fSQu Wenruo int level = btrfs_header_level(left); 2214d16c702fSQu Wenruo int nr_left = btrfs_header_nritems(left); 2215d16c702fSQu Wenruo int nr_right = btrfs_header_nritems(right); 2216d16c702fSQu Wenruo 2217d16c702fSQu Wenruo /* No key to check in one of the tree blocks */ 2218d16c702fSQu Wenruo if (!nr_left || !nr_right) 2219d16c702fSQu Wenruo return false; 2220d16c702fSQu Wenruo 2221d16c702fSQu Wenruo if (level) { 2222d16c702fSQu Wenruo btrfs_node_key_to_cpu(left, &left_last, nr_left - 1); 2223d16c702fSQu Wenruo btrfs_node_key_to_cpu(right, &right_first, 0); 2224d16c702fSQu Wenruo } else { 2225d16c702fSQu Wenruo btrfs_item_key_to_cpu(left, &left_last, nr_left - 1); 2226d16c702fSQu Wenruo btrfs_item_key_to_cpu(right, &right_first, 0); 2227d16c702fSQu Wenruo } 2228d16c702fSQu Wenruo 2229d16c702fSQu Wenruo if (btrfs_comp_cpu_keys(&left_last, &right_first) >= 0) { 2230d16c702fSQu Wenruo btrfs_crit(left->fs_info, 2231d16c702fSQu Wenruo "bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)", 2232d16c702fSQu Wenruo left_last.objectid, left_last.type, 2233d16c702fSQu Wenruo left_last.offset, right_first.objectid, 2234d16c702fSQu Wenruo right_first.type, right_first.offset); 2235d16c702fSQu Wenruo return true; 2236d16c702fSQu Wenruo } 2237d16c702fSQu Wenruo return false; 2238d16c702fSQu Wenruo } 2239d16c702fSQu Wenruo 2240d16c702fSQu Wenruo /* 224174123bd7SChris Mason * try to push data from one node into the next node left in the 224279f95c82SChris Mason * tree. 2243aa5d6bedSChris Mason * 2244aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 2245aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 224674123bd7SChris Mason */ 224798ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 22482ff7e61eSJeff Mahoney struct extent_buffer *dst, 2249971a1f66SChris Mason struct extent_buffer *src, int empty) 2250be0e5c09SChris Mason { 2251d30a668fSDavid Sterba struct btrfs_fs_info *fs_info = trans->fs_info; 2252be0e5c09SChris Mason int push_items = 0; 2253bb803951SChris Mason int src_nritems; 2254bb803951SChris Mason int dst_nritems; 2255aa5d6bedSChris Mason int ret = 0; 2256be0e5c09SChris Mason 22575f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 22585f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 22590b246afaSJeff Mahoney push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems; 22607bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 22617bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 226254aa1f4dSChris Mason 2263bce4eae9SChris Mason if (!empty && src_nritems <= 8) 2264971a1f66SChris Mason return 1; 2265971a1f66SChris Mason 2266d397712bSChris Mason if (push_items <= 0) 2267be0e5c09SChris Mason return 1; 2268be0e5c09SChris Mason 2269bce4eae9SChris Mason if (empty) { 2270971a1f66SChris Mason push_items = min(src_nritems, push_items); 2271bce4eae9SChris Mason if (push_items < src_nritems) { 2272bce4eae9SChris Mason /* leave at least 8 pointers in the node if 2273bce4eae9SChris Mason * we aren't going to empty it 2274bce4eae9SChris Mason */ 2275bce4eae9SChris Mason if (src_nritems - push_items < 8) { 2276bce4eae9SChris Mason if (push_items <= 8) 2277bce4eae9SChris Mason return 1; 2278bce4eae9SChris Mason push_items -= 8; 2279bce4eae9SChris Mason } 2280bce4eae9SChris Mason } 2281bce4eae9SChris Mason } else 2282bce4eae9SChris Mason push_items = min(src_nritems - 8, push_items); 228379f95c82SChris Mason 2284d16c702fSQu Wenruo /* dst is the left eb, src is the middle eb */ 2285d16c702fSQu Wenruo if (check_sibling_keys(dst, src)) { 2286d16c702fSQu Wenruo ret = -EUCLEAN; 2287d16c702fSQu Wenruo btrfs_abort_transaction(trans, ret); 2288d16c702fSQu Wenruo return ret; 2289d16c702fSQu Wenruo } 2290f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items); 22915de865eeSFilipe David Borba Manana if (ret) { 229266642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 22935de865eeSFilipe David Borba Manana return ret; 22945de865eeSFilipe David Borba Manana } 22955f39d397SChris Mason copy_extent_buffer(dst, src, 22965f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 22975f39d397SChris Mason btrfs_node_key_ptr_offset(0), 2298123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 22995f39d397SChris Mason 2300bb803951SChris Mason if (push_items < src_nritems) { 230157911b8bSJan Schmidt /* 2302f3a84ccdSFilipe Manana * Don't call btrfs_tree_mod_log_insert_move() here, key removal 2303f3a84ccdSFilipe Manana * was already fully logged by btrfs_tree_mod_log_eb_copy() above. 230457911b8bSJan Schmidt */ 23055f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 23065f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 2307e2fa7227SChris Mason (src_nritems - push_items) * 2308123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 2309bb803951SChris Mason } 23105f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 23115f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 23125f39d397SChris Mason btrfs_mark_buffer_dirty(src); 23135f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 231431840ae1SZheng Yan 2315bb803951SChris Mason return ret; 2316be0e5c09SChris Mason } 2317be0e5c09SChris Mason 231897571fd0SChris Mason /* 231979f95c82SChris Mason * try to push data from one node into the next node right in the 232079f95c82SChris Mason * tree. 232179f95c82SChris Mason * 232279f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 232379f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 232479f95c82SChris Mason * 232579f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 232679f95c82SChris Mason */ 23275f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 23285f39d397SChris Mason struct extent_buffer *dst, 23295f39d397SChris Mason struct extent_buffer *src) 233079f95c82SChris Mason { 233155d32ed8SDavid Sterba struct btrfs_fs_info *fs_info = trans->fs_info; 233279f95c82SChris Mason int push_items = 0; 233379f95c82SChris Mason int max_push; 233479f95c82SChris Mason int src_nritems; 233579f95c82SChris Mason int dst_nritems; 233679f95c82SChris Mason int ret = 0; 233779f95c82SChris Mason 23387bb86316SChris Mason WARN_ON(btrfs_header_generation(src) != trans->transid); 23397bb86316SChris Mason WARN_ON(btrfs_header_generation(dst) != trans->transid); 23407bb86316SChris Mason 23415f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 23425f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 23430b246afaSJeff Mahoney push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems; 2344d397712bSChris Mason if (push_items <= 0) 234579f95c82SChris Mason return 1; 2346bce4eae9SChris Mason 2347d397712bSChris Mason if (src_nritems < 4) 2348bce4eae9SChris Mason return 1; 234979f95c82SChris Mason 235079f95c82SChris Mason max_push = src_nritems / 2 + 1; 235179f95c82SChris Mason /* don't try to empty the node */ 2352d397712bSChris Mason if (max_push >= src_nritems) 235379f95c82SChris Mason return 1; 2354252c38f0SYan 235579f95c82SChris Mason if (max_push < push_items) 235679f95c82SChris Mason push_items = max_push; 235779f95c82SChris Mason 2358d16c702fSQu Wenruo /* dst is the right eb, src is the middle eb */ 2359d16c702fSQu Wenruo if (check_sibling_keys(src, dst)) { 2360d16c702fSQu Wenruo ret = -EUCLEAN; 2361d16c702fSQu Wenruo btrfs_abort_transaction(trans, ret); 2362d16c702fSQu Wenruo return ret; 2363d16c702fSQu Wenruo } 2364f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_move(dst, push_items, 0, dst_nritems); 2365bf1d3425SDavid Sterba BUG_ON(ret < 0); 23665f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 23675f39d397SChris Mason btrfs_node_key_ptr_offset(0), 23685f39d397SChris Mason (dst_nritems) * 23695f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 2370d6025579SChris Mason 2371f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items, 2372ed874f0dSDavid Sterba push_items); 23735de865eeSFilipe David Borba Manana if (ret) { 237466642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 23755de865eeSFilipe David Borba Manana return ret; 23765de865eeSFilipe David Borba Manana } 23775f39d397SChris Mason copy_extent_buffer(dst, src, 23785f39d397SChris Mason btrfs_node_key_ptr_offset(0), 23795f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 2380123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 238179f95c82SChris Mason 23825f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 23835f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 238479f95c82SChris Mason 23855f39d397SChris Mason btrfs_mark_buffer_dirty(src); 23865f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 238731840ae1SZheng Yan 238879f95c82SChris Mason return ret; 238979f95c82SChris Mason } 239079f95c82SChris Mason 239179f95c82SChris Mason /* 239297571fd0SChris Mason * helper function to insert a new root level in the tree. 239397571fd0SChris Mason * A new node is allocated, and a single item is inserted to 239497571fd0SChris Mason * point to the existing root 2395aa5d6bedSChris Mason * 2396aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 239797571fd0SChris Mason */ 2398d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans, 23995f39d397SChris Mason struct btrfs_root *root, 2400fdd99c72SLiu Bo struct btrfs_path *path, int level) 240174123bd7SChris Mason { 24020b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 24037bb86316SChris Mason u64 lower_gen; 24045f39d397SChris Mason struct extent_buffer *lower; 24055f39d397SChris Mason struct extent_buffer *c; 2406925baeddSChris Mason struct extent_buffer *old; 24075f39d397SChris Mason struct btrfs_disk_key lower_key; 2408d9d19a01SDavid Sterba int ret; 24095c680ed6SChris Mason 24105c680ed6SChris Mason BUG_ON(path->nodes[level]); 24115c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 24125c680ed6SChris Mason 24137bb86316SChris Mason lower = path->nodes[level-1]; 24147bb86316SChris Mason if (level == 1) 24157bb86316SChris Mason btrfs_item_key(lower, &lower_key, 0); 24167bb86316SChris Mason else 24177bb86316SChris Mason btrfs_node_key(lower, &lower_key, 0); 24187bb86316SChris Mason 2419*79bd3712SFilipe Manana c = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 2420*79bd3712SFilipe Manana &lower_key, level, root->node->start, 0, 2421cf6f34aaSJosef Bacik BTRFS_NESTING_NEW_ROOT); 24225f39d397SChris Mason if (IS_ERR(c)) 24235f39d397SChris Mason return PTR_ERR(c); 2424925baeddSChris Mason 24250b246afaSJeff Mahoney root_add_used(root, fs_info->nodesize); 2426f0486c68SYan, Zheng 24275f39d397SChris Mason btrfs_set_header_nritems(c, 1); 24285f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 2429db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 24307bb86316SChris Mason lower_gen = btrfs_header_generation(lower); 243131840ae1SZheng Yan WARN_ON(lower_gen != trans->transid); 24327bb86316SChris Mason 24337bb86316SChris Mason btrfs_set_node_ptr_generation(c, 0, lower_gen); 24345f39d397SChris Mason 24355f39d397SChris Mason btrfs_mark_buffer_dirty(c); 2436d5719762SChris Mason 2437925baeddSChris Mason old = root->node; 2438406808abSFilipe Manana ret = btrfs_tree_mod_log_insert_root(root->node, c, false); 2439d9d19a01SDavid Sterba BUG_ON(ret < 0); 2440240f62c8SChris Mason rcu_assign_pointer(root->node, c); 2441925baeddSChris Mason 2442925baeddSChris Mason /* the super has an extra ref to root->node */ 2443925baeddSChris Mason free_extent_buffer(old); 2444925baeddSChris Mason 24450b86a832SChris Mason add_root_to_dirty_list(root); 244667439dadSDavid Sterba atomic_inc(&c->refs); 24475f39d397SChris Mason path->nodes[level] = c; 2448ac5887c8SJosef Bacik path->locks[level] = BTRFS_WRITE_LOCK; 244974123bd7SChris Mason path->slots[level] = 0; 245074123bd7SChris Mason return 0; 245174123bd7SChris Mason } 24525c680ed6SChris Mason 24535c680ed6SChris Mason /* 24545c680ed6SChris Mason * worker function to insert a single pointer in a node. 24555c680ed6SChris Mason * the node should have enough room for the pointer already 245697571fd0SChris Mason * 24575c680ed6SChris Mason * slot and level indicate where you want the key to go, and 24585c680ed6SChris Mason * blocknr is the block the key points to. 24595c680ed6SChris Mason */ 2460143bede5SJeff Mahoney static void insert_ptr(struct btrfs_trans_handle *trans, 24616ad3cf6dSDavid Sterba struct btrfs_path *path, 2462143bede5SJeff Mahoney struct btrfs_disk_key *key, u64 bytenr, 2463c3e06965SJan Schmidt int slot, int level) 24645c680ed6SChris Mason { 24655f39d397SChris Mason struct extent_buffer *lower; 24665c680ed6SChris Mason int nritems; 2467f3ea38daSJan Schmidt int ret; 24685c680ed6SChris Mason 24695c680ed6SChris Mason BUG_ON(!path->nodes[level]); 2470f0486c68SYan, Zheng btrfs_assert_tree_locked(path->nodes[level]); 24715f39d397SChris Mason lower = path->nodes[level]; 24725f39d397SChris Mason nritems = btrfs_header_nritems(lower); 2473c293498bSStoyan Gaydarov BUG_ON(slot > nritems); 24746ad3cf6dSDavid Sterba BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info)); 247574123bd7SChris Mason if (slot != nritems) { 2476bf1d3425SDavid Sterba if (level) { 2477f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_move(lower, slot + 1, 2478f3a84ccdSFilipe Manana slot, nritems - slot); 2479bf1d3425SDavid Sterba BUG_ON(ret < 0); 2480bf1d3425SDavid Sterba } 24815f39d397SChris Mason memmove_extent_buffer(lower, 24825f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 24835f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 2484123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 248574123bd7SChris Mason } 2486c3e06965SJan Schmidt if (level) { 2487f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(lower, slot, 2488f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_ADD, GFP_NOFS); 2489f3ea38daSJan Schmidt BUG_ON(ret < 0); 2490f3ea38daSJan Schmidt } 24915f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 2492db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 249374493f7aSChris Mason WARN_ON(trans->transid == 0); 249474493f7aSChris Mason btrfs_set_node_ptr_generation(lower, slot, trans->transid); 24955f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 24965f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 249774123bd7SChris Mason } 249874123bd7SChris Mason 249997571fd0SChris Mason /* 250097571fd0SChris Mason * split the node at the specified level in path in two. 250197571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 250297571fd0SChris Mason * 250397571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 250497571fd0SChris Mason * left and right, if either one works, it returns right away. 2505aa5d6bedSChris Mason * 2506aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 250797571fd0SChris Mason */ 2508e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans, 2509e02119d5SChris Mason struct btrfs_root *root, 2510e02119d5SChris Mason struct btrfs_path *path, int level) 2511be0e5c09SChris Mason { 25120b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 25135f39d397SChris Mason struct extent_buffer *c; 25145f39d397SChris Mason struct extent_buffer *split; 25155f39d397SChris Mason struct btrfs_disk_key disk_key; 2516be0e5c09SChris Mason int mid; 25175c680ed6SChris Mason int ret; 25187518a238SChris Mason u32 c_nritems; 2519be0e5c09SChris Mason 25205f39d397SChris Mason c = path->nodes[level]; 25217bb86316SChris Mason WARN_ON(btrfs_header_generation(c) != trans->transid); 25225f39d397SChris Mason if (c == root->node) { 2523d9abbf1cSJan Schmidt /* 252490f8d62eSJan Schmidt * trying to split the root, lets make a new one 252590f8d62eSJan Schmidt * 2526fdd99c72SLiu Bo * tree mod log: We don't log_removal old root in 252790f8d62eSJan Schmidt * insert_new_root, because that root buffer will be kept as a 252890f8d62eSJan Schmidt * normal node. We are going to log removal of half of the 2529f3a84ccdSFilipe Manana * elements below with btrfs_tree_mod_log_eb_copy(). We're 2530f3a84ccdSFilipe Manana * holding a tree lock on the buffer, which is why we cannot 2531f3a84ccdSFilipe Manana * race with other tree_mod_log users. 2532d9abbf1cSJan Schmidt */ 2533fdd99c72SLiu Bo ret = insert_new_root(trans, root, path, level + 1); 25345c680ed6SChris Mason if (ret) 25355c680ed6SChris Mason return ret; 2536b3612421SChris Mason } else { 2537e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 25385f39d397SChris Mason c = path->nodes[level]; 25395f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 25400b246afaSJeff Mahoney BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) 2541e66f709bSChris Mason return 0; 254254aa1f4dSChris Mason if (ret < 0) 254354aa1f4dSChris Mason return ret; 25445c680ed6SChris Mason } 2545e66f709bSChris Mason 25465f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 25475d4f98a2SYan Zheng mid = (c_nritems + 1) / 2; 25485d4f98a2SYan Zheng btrfs_node_key(c, &disk_key, mid); 25497bb86316SChris Mason 2550*79bd3712SFilipe Manana split = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 2551*79bd3712SFilipe Manana &disk_key, level, c->start, 0, 2552*79bd3712SFilipe Manana BTRFS_NESTING_SPLIT); 25535f39d397SChris Mason if (IS_ERR(split)) 25545f39d397SChris Mason return PTR_ERR(split); 255554aa1f4dSChris Mason 25560b246afaSJeff Mahoney root_add_used(root, fs_info->nodesize); 2557bc877d28SNikolay Borisov ASSERT(btrfs_header_level(c) == level); 25585f39d397SChris Mason 2559f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid); 25605de865eeSFilipe David Borba Manana if (ret) { 256166642832SJeff Mahoney btrfs_abort_transaction(trans, ret); 25625de865eeSFilipe David Borba Manana return ret; 25635de865eeSFilipe David Borba Manana } 25645f39d397SChris Mason copy_extent_buffer(split, c, 25655f39d397SChris Mason btrfs_node_key_ptr_offset(0), 25665f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 2567123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 25685f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 25695f39d397SChris Mason btrfs_set_header_nritems(c, mid); 2570aa5d6bedSChris Mason 25715f39d397SChris Mason btrfs_mark_buffer_dirty(c); 25725f39d397SChris Mason btrfs_mark_buffer_dirty(split); 25735f39d397SChris Mason 25746ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, split->start, 2575c3e06965SJan Schmidt path->slots[level + 1] + 1, level + 1); 2576aa5d6bedSChris Mason 25775de08d7dSChris Mason if (path->slots[level] >= mid) { 25785c680ed6SChris Mason path->slots[level] -= mid; 2579925baeddSChris Mason btrfs_tree_unlock(c); 25805f39d397SChris Mason free_extent_buffer(c); 25815f39d397SChris Mason path->nodes[level] = split; 25825c680ed6SChris Mason path->slots[level + 1] += 1; 2583eb60ceacSChris Mason } else { 2584925baeddSChris Mason btrfs_tree_unlock(split); 25855f39d397SChris Mason free_extent_buffer(split); 2586be0e5c09SChris Mason } 2587d5286a92SNikolay Borisov return 0; 2588be0e5c09SChris Mason } 2589be0e5c09SChris Mason 259074123bd7SChris Mason /* 259174123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 259274123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 259374123bd7SChris Mason * space used both by the item structs and the item data 259474123bd7SChris Mason */ 25955f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 2596be0e5c09SChris Mason { 259741be1f3bSJosef Bacik struct btrfs_item *start_item; 259841be1f3bSJosef Bacik struct btrfs_item *end_item; 2599be0e5c09SChris Mason int data_len; 26005f39d397SChris Mason int nritems = btrfs_header_nritems(l); 2601d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 2602be0e5c09SChris Mason 2603be0e5c09SChris Mason if (!nr) 2604be0e5c09SChris Mason return 0; 2605dd3cc16bSRoss Kirk start_item = btrfs_item_nr(start); 2606dd3cc16bSRoss Kirk end_item = btrfs_item_nr(end); 2607a31356b9SDavid Sterba data_len = btrfs_item_offset(l, start_item) + 2608a31356b9SDavid Sterba btrfs_item_size(l, start_item); 2609a31356b9SDavid Sterba data_len = data_len - btrfs_item_offset(l, end_item); 26100783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 2611d4dbff95SChris Mason WARN_ON(data_len < 0); 2612be0e5c09SChris Mason return data_len; 2613be0e5c09SChris Mason } 2614be0e5c09SChris Mason 261574123bd7SChris Mason /* 2616d4dbff95SChris Mason * The space between the end of the leaf items and 2617d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 2618d4dbff95SChris Mason * the leaf has left for both items and data 2619d4dbff95SChris Mason */ 2620e902baacSDavid Sterba noinline int btrfs_leaf_free_space(struct extent_buffer *leaf) 2621d4dbff95SChris Mason { 2622e902baacSDavid Sterba struct btrfs_fs_info *fs_info = leaf->fs_info; 26235f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 26245f39d397SChris Mason int ret; 26250b246afaSJeff Mahoney 26260b246afaSJeff Mahoney ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems); 26275f39d397SChris Mason if (ret < 0) { 26280b246afaSJeff Mahoney btrfs_crit(fs_info, 2629efe120a0SFrank Holton "leaf free space ret %d, leaf data size %lu, used %d nritems %d", 2630da17066cSJeff Mahoney ret, 26310b246afaSJeff Mahoney (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info), 26325f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 26335f39d397SChris Mason } 26345f39d397SChris Mason return ret; 2635d4dbff95SChris Mason } 2636d4dbff95SChris Mason 263799d8f83cSChris Mason /* 263899d8f83cSChris Mason * min slot controls the lowest index we're willing to push to the 263999d8f83cSChris Mason * right. We'll push up to and including min_slot, but no lower 264099d8f83cSChris Mason */ 2641f72f0010SDavid Sterba static noinline int __push_leaf_right(struct btrfs_path *path, 264244871b1bSChris Mason int data_size, int empty, 264344871b1bSChris Mason struct extent_buffer *right, 264499d8f83cSChris Mason int free_space, u32 left_nritems, 264599d8f83cSChris Mason u32 min_slot) 264600ec4c51SChris Mason { 2647f72f0010SDavid Sterba struct btrfs_fs_info *fs_info = right->fs_info; 26485f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 264944871b1bSChris Mason struct extent_buffer *upper = path->nodes[1]; 2650cfed81a0SChris Mason struct btrfs_map_token token; 26515f39d397SChris Mason struct btrfs_disk_key disk_key; 265200ec4c51SChris Mason int slot; 265334a38218SChris Mason u32 i; 265400ec4c51SChris Mason int push_space = 0; 265500ec4c51SChris Mason int push_items = 0; 26560783fcfcSChris Mason struct btrfs_item *item; 265734a38218SChris Mason u32 nr; 26587518a238SChris Mason u32 right_nritems; 26595f39d397SChris Mason u32 data_end; 2660db94535dSChris Mason u32 this_item_size; 266100ec4c51SChris Mason 266234a38218SChris Mason if (empty) 266334a38218SChris Mason nr = 0; 266434a38218SChris Mason else 266599d8f83cSChris Mason nr = max_t(u32, 1, min_slot); 266634a38218SChris Mason 266731840ae1SZheng Yan if (path->slots[0] >= left_nritems) 266887b29b20SYan Zheng push_space += data_size; 266931840ae1SZheng Yan 267044871b1bSChris Mason slot = path->slots[1]; 267134a38218SChris Mason i = left_nritems - 1; 267234a38218SChris Mason while (i >= nr) { 2673dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 2674db94535dSChris Mason 267531840ae1SZheng Yan if (!empty && push_items > 0) { 267631840ae1SZheng Yan if (path->slots[0] > i) 267731840ae1SZheng Yan break; 267831840ae1SZheng Yan if (path->slots[0] == i) { 2679e902baacSDavid Sterba int space = btrfs_leaf_free_space(left); 2680e902baacSDavid Sterba 268131840ae1SZheng Yan if (space + push_space * 2 > free_space) 268231840ae1SZheng Yan break; 268331840ae1SZheng Yan } 268431840ae1SZheng Yan } 268531840ae1SZheng Yan 268600ec4c51SChris Mason if (path->slots[0] == i) 268787b29b20SYan Zheng push_space += data_size; 2688db94535dSChris Mason 2689db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 2690db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 269100ec4c51SChris Mason break; 269231840ae1SZheng Yan 269300ec4c51SChris Mason push_items++; 2694db94535dSChris Mason push_space += this_item_size + sizeof(*item); 269534a38218SChris Mason if (i == 0) 269634a38218SChris Mason break; 269734a38218SChris Mason i--; 2698db94535dSChris Mason } 26995f39d397SChris Mason 2700925baeddSChris Mason if (push_items == 0) 2701925baeddSChris Mason goto out_unlock; 27025f39d397SChris Mason 27036c1500f2SJulia Lawall WARN_ON(!empty && push_items == left_nritems); 27045f39d397SChris Mason 270500ec4c51SChris Mason /* push left to right */ 27065f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 270734a38218SChris Mason 27085f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 27098f881e8cSDavid Sterba push_space -= leaf_data_end(left); 27105f39d397SChris Mason 271100ec4c51SChris Mason /* make room in the right data area */ 27128f881e8cSDavid Sterba data_end = leaf_data_end(right); 27135f39d397SChris Mason memmove_extent_buffer(right, 27143d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + data_end - push_space, 27153d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + data_end, 27160b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info) - data_end); 27175f39d397SChris Mason 271800ec4c51SChris Mason /* copy from the left data area */ 27193d9ec8c4SNikolay Borisov copy_extent_buffer(right, left, BTRFS_LEAF_DATA_OFFSET + 27200b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info) - push_space, 27218f881e8cSDavid Sterba BTRFS_LEAF_DATA_OFFSET + leaf_data_end(left), 2722d6025579SChris Mason push_space); 27235f39d397SChris Mason 27245f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 27255f39d397SChris Mason btrfs_item_nr_offset(0), 27260783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 27275f39d397SChris Mason 272800ec4c51SChris Mason /* copy the items from left to right */ 27295f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 27305f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 27310783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 273200ec4c51SChris Mason 273300ec4c51SChris Mason /* update the item pointers */ 2734c82f823cSDavid Sterba btrfs_init_map_token(&token, right); 27357518a238SChris Mason right_nritems += push_items; 27365f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 27370b246afaSJeff Mahoney push_space = BTRFS_LEAF_DATA_SIZE(fs_info); 27387518a238SChris Mason for (i = 0; i < right_nritems; i++) { 2739dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 2740cc4c13d5SDavid Sterba push_space -= btrfs_token_item_size(&token, item); 2741cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, push_space); 2742db94535dSChris Mason } 2743db94535dSChris Mason 27447518a238SChris Mason left_nritems -= push_items; 27455f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 274600ec4c51SChris Mason 274734a38218SChris Mason if (left_nritems) 27485f39d397SChris Mason btrfs_mark_buffer_dirty(left); 2749f0486c68SYan, Zheng else 27506a884d7dSDavid Sterba btrfs_clean_tree_block(left); 2751f0486c68SYan, Zheng 27525f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2753a429e513SChris Mason 27545f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 27555f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 2756d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 275702217ed2SChris Mason 275800ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 27597518a238SChris Mason if (path->slots[0] >= left_nritems) { 27607518a238SChris Mason path->slots[0] -= left_nritems; 2761925baeddSChris Mason if (btrfs_header_nritems(path->nodes[0]) == 0) 27626a884d7dSDavid Sterba btrfs_clean_tree_block(path->nodes[0]); 2763925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 27645f39d397SChris Mason free_extent_buffer(path->nodes[0]); 27655f39d397SChris Mason path->nodes[0] = right; 276600ec4c51SChris Mason path->slots[1] += 1; 276700ec4c51SChris Mason } else { 2768925baeddSChris Mason btrfs_tree_unlock(right); 27695f39d397SChris Mason free_extent_buffer(right); 277000ec4c51SChris Mason } 277100ec4c51SChris Mason return 0; 2772925baeddSChris Mason 2773925baeddSChris Mason out_unlock: 2774925baeddSChris Mason btrfs_tree_unlock(right); 2775925baeddSChris Mason free_extent_buffer(right); 2776925baeddSChris Mason return 1; 277700ec4c51SChris Mason } 2778925baeddSChris Mason 277900ec4c51SChris Mason /* 278044871b1bSChris Mason * push some data in the path leaf to the right, trying to free up at 278174123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 278244871b1bSChris Mason * 278344871b1bSChris Mason * returns 1 if the push failed because the other node didn't have enough 278444871b1bSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 278599d8f83cSChris Mason * 278699d8f83cSChris Mason * this will push starting from min_slot to the end of the leaf. It won't 278799d8f83cSChris Mason * push any slot lower than min_slot 278874123bd7SChris Mason */ 278944871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 279099d8f83cSChris Mason *root, struct btrfs_path *path, 279199d8f83cSChris Mason int min_data_size, int data_size, 279299d8f83cSChris Mason int empty, u32 min_slot) 2793be0e5c09SChris Mason { 279444871b1bSChris Mason struct extent_buffer *left = path->nodes[0]; 279544871b1bSChris Mason struct extent_buffer *right; 279644871b1bSChris Mason struct extent_buffer *upper; 279744871b1bSChris Mason int slot; 279844871b1bSChris Mason int free_space; 279944871b1bSChris Mason u32 left_nritems; 280044871b1bSChris Mason int ret; 280144871b1bSChris Mason 280244871b1bSChris Mason if (!path->nodes[1]) 280344871b1bSChris Mason return 1; 280444871b1bSChris Mason 280544871b1bSChris Mason slot = path->slots[1]; 280644871b1bSChris Mason upper = path->nodes[1]; 280744871b1bSChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 280844871b1bSChris Mason return 1; 280944871b1bSChris Mason 281044871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 281144871b1bSChris Mason 28124b231ae4SDavid Sterba right = btrfs_read_node_slot(upper, slot + 1); 2813fb770ae4SLiu Bo /* 2814fb770ae4SLiu Bo * slot + 1 is not valid or we fail to read the right node, 2815fb770ae4SLiu Bo * no big deal, just return. 2816fb770ae4SLiu Bo */ 2817fb770ae4SLiu Bo if (IS_ERR(right)) 281891ca338dSTsutomu Itoh return 1; 281991ca338dSTsutomu Itoh 2820bf77467aSJosef Bacik __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT); 282144871b1bSChris Mason 2822e902baacSDavid Sterba free_space = btrfs_leaf_free_space(right); 282344871b1bSChris Mason if (free_space < data_size) 282444871b1bSChris Mason goto out_unlock; 282544871b1bSChris Mason 282644871b1bSChris Mason /* cow and double check */ 282744871b1bSChris Mason ret = btrfs_cow_block(trans, root, right, upper, 2828bf59a5a2SJosef Bacik slot + 1, &right, BTRFS_NESTING_RIGHT_COW); 282944871b1bSChris Mason if (ret) 283044871b1bSChris Mason goto out_unlock; 283144871b1bSChris Mason 2832e902baacSDavid Sterba free_space = btrfs_leaf_free_space(right); 283344871b1bSChris Mason if (free_space < data_size) 283444871b1bSChris Mason goto out_unlock; 283544871b1bSChris Mason 283644871b1bSChris Mason left_nritems = btrfs_header_nritems(left); 283744871b1bSChris Mason if (left_nritems == 0) 283844871b1bSChris Mason goto out_unlock; 283944871b1bSChris Mason 2840d16c702fSQu Wenruo if (check_sibling_keys(left, right)) { 2841d16c702fSQu Wenruo ret = -EUCLEAN; 2842d16c702fSQu Wenruo btrfs_tree_unlock(right); 2843d16c702fSQu Wenruo free_extent_buffer(right); 2844d16c702fSQu Wenruo return ret; 2845d16c702fSQu Wenruo } 28462ef1fed2SFilipe David Borba Manana if (path->slots[0] == left_nritems && !empty) { 28472ef1fed2SFilipe David Borba Manana /* Key greater than all keys in the leaf, right neighbor has 28482ef1fed2SFilipe David Borba Manana * enough room for it and we're not emptying our leaf to delete 28492ef1fed2SFilipe David Borba Manana * it, therefore use right neighbor to insert the new item and 285052042d8eSAndrea Gelmini * no need to touch/dirty our left leaf. */ 28512ef1fed2SFilipe David Borba Manana btrfs_tree_unlock(left); 28522ef1fed2SFilipe David Borba Manana free_extent_buffer(left); 28532ef1fed2SFilipe David Borba Manana path->nodes[0] = right; 28542ef1fed2SFilipe David Borba Manana path->slots[0] = 0; 28552ef1fed2SFilipe David Borba Manana path->slots[1]++; 28562ef1fed2SFilipe David Borba Manana return 0; 28572ef1fed2SFilipe David Borba Manana } 28582ef1fed2SFilipe David Borba Manana 2859f72f0010SDavid Sterba return __push_leaf_right(path, min_data_size, empty, 286099d8f83cSChris Mason right, free_space, left_nritems, min_slot); 286144871b1bSChris Mason out_unlock: 286244871b1bSChris Mason btrfs_tree_unlock(right); 286344871b1bSChris Mason free_extent_buffer(right); 286444871b1bSChris Mason return 1; 286544871b1bSChris Mason } 286644871b1bSChris Mason 286744871b1bSChris Mason /* 286844871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 286944871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 287099d8f83cSChris Mason * 287199d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 287299d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the 287399d8f83cSChris Mason * items 287444871b1bSChris Mason */ 28758087c193SDavid Sterba static noinline int __push_leaf_left(struct btrfs_path *path, int data_size, 287644871b1bSChris Mason int empty, struct extent_buffer *left, 287799d8f83cSChris Mason int free_space, u32 right_nritems, 287899d8f83cSChris Mason u32 max_slot) 287944871b1bSChris Mason { 28808087c193SDavid Sterba struct btrfs_fs_info *fs_info = left->fs_info; 28815f39d397SChris Mason struct btrfs_disk_key disk_key; 28825f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 2883be0e5c09SChris Mason int i; 2884be0e5c09SChris Mason int push_space = 0; 2885be0e5c09SChris Mason int push_items = 0; 28860783fcfcSChris Mason struct btrfs_item *item; 28877518a238SChris Mason u32 old_left_nritems; 288834a38218SChris Mason u32 nr; 2889aa5d6bedSChris Mason int ret = 0; 2890db94535dSChris Mason u32 this_item_size; 2891db94535dSChris Mason u32 old_left_item_size; 2892cfed81a0SChris Mason struct btrfs_map_token token; 2893cfed81a0SChris Mason 289434a38218SChris Mason if (empty) 289599d8f83cSChris Mason nr = min(right_nritems, max_slot); 289634a38218SChris Mason else 289799d8f83cSChris Mason nr = min(right_nritems - 1, max_slot); 289834a38218SChris Mason 289934a38218SChris Mason for (i = 0; i < nr; i++) { 2900dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 2901db94535dSChris Mason 290231840ae1SZheng Yan if (!empty && push_items > 0) { 290331840ae1SZheng Yan if (path->slots[0] < i) 290431840ae1SZheng Yan break; 290531840ae1SZheng Yan if (path->slots[0] == i) { 2906e902baacSDavid Sterba int space = btrfs_leaf_free_space(right); 2907e902baacSDavid Sterba 290831840ae1SZheng Yan if (space + push_space * 2 > free_space) 290931840ae1SZheng Yan break; 291031840ae1SZheng Yan } 291131840ae1SZheng Yan } 291231840ae1SZheng Yan 2913be0e5c09SChris Mason if (path->slots[0] == i) 291487b29b20SYan Zheng push_space += data_size; 2915db94535dSChris Mason 2916db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 2917db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 2918be0e5c09SChris Mason break; 2919db94535dSChris Mason 2920be0e5c09SChris Mason push_items++; 2921db94535dSChris Mason push_space += this_item_size + sizeof(*item); 2922be0e5c09SChris Mason } 2923db94535dSChris Mason 2924be0e5c09SChris Mason if (push_items == 0) { 2925925baeddSChris Mason ret = 1; 2926925baeddSChris Mason goto out; 2927be0e5c09SChris Mason } 2928fae7f21cSDulshani Gunawardhana WARN_ON(!empty && push_items == btrfs_header_nritems(right)); 29295f39d397SChris Mason 2930be0e5c09SChris Mason /* push data from right to left */ 29315f39d397SChris Mason copy_extent_buffer(left, right, 29325f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 29335f39d397SChris Mason btrfs_item_nr_offset(0), 29345f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 29355f39d397SChris Mason 29360b246afaSJeff Mahoney push_space = BTRFS_LEAF_DATA_SIZE(fs_info) - 29375f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1); 29385f39d397SChris Mason 29393d9ec8c4SNikolay Borisov copy_extent_buffer(left, right, BTRFS_LEAF_DATA_OFFSET + 29408f881e8cSDavid Sterba leaf_data_end(left) - push_space, 29413d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + 29425f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 2943be0e5c09SChris Mason push_space); 29445f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 294587b29b20SYan Zheng BUG_ON(old_left_nritems <= 0); 2946eb60ceacSChris Mason 2947c82f823cSDavid Sterba btrfs_init_map_token(&token, left); 2948db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 2949be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 29505f39d397SChris Mason u32 ioff; 2951db94535dSChris Mason 2952dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 2953db94535dSChris Mason 2954cc4c13d5SDavid Sterba ioff = btrfs_token_item_offset(&token, item); 2955cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, 2956cc4c13d5SDavid Sterba ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size)); 2957be0e5c09SChris Mason } 29585f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 2959be0e5c09SChris Mason 2960be0e5c09SChris Mason /* fixup right node */ 296131b1a2bdSJulia Lawall if (push_items > right_nritems) 296231b1a2bdSJulia Lawall WARN(1, KERN_CRIT "push items %d nr %u\n", push_items, 2963d397712bSChris Mason right_nritems); 296434a38218SChris Mason 296534a38218SChris Mason if (push_items < right_nritems) { 29665f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 29678f881e8cSDavid Sterba leaf_data_end(right); 29683d9ec8c4SNikolay Borisov memmove_extent_buffer(right, BTRFS_LEAF_DATA_OFFSET + 29690b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info) - push_space, 29703d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + 29718f881e8cSDavid Sterba leaf_data_end(right), push_space); 29725f39d397SChris Mason 29735f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 29745f39d397SChris Mason btrfs_item_nr_offset(push_items), 29755f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 29760783fcfcSChris Mason sizeof(struct btrfs_item)); 297734a38218SChris Mason } 2978c82f823cSDavid Sterba 2979c82f823cSDavid Sterba btrfs_init_map_token(&token, right); 2980eef1c494SYan right_nritems -= push_items; 2981eef1c494SYan btrfs_set_header_nritems(right, right_nritems); 29820b246afaSJeff Mahoney push_space = BTRFS_LEAF_DATA_SIZE(fs_info); 29835f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 2984dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 2985db94535dSChris Mason 2986cc4c13d5SDavid Sterba push_space = push_space - btrfs_token_item_size(&token, item); 2987cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, push_space); 2988db94535dSChris Mason } 2989eb60ceacSChris Mason 29905f39d397SChris Mason btrfs_mark_buffer_dirty(left); 299134a38218SChris Mason if (right_nritems) 29925f39d397SChris Mason btrfs_mark_buffer_dirty(right); 2993f0486c68SYan, Zheng else 29946a884d7dSDavid Sterba btrfs_clean_tree_block(right); 2995098f59c2SChris Mason 29965f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 2997b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 2998be0e5c09SChris Mason 2999be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 3000be0e5c09SChris Mason if (path->slots[0] < push_items) { 3001be0e5c09SChris Mason path->slots[0] += old_left_nritems; 3002925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 30035f39d397SChris Mason free_extent_buffer(path->nodes[0]); 30045f39d397SChris Mason path->nodes[0] = left; 3005be0e5c09SChris Mason path->slots[1] -= 1; 3006be0e5c09SChris Mason } else { 3007925baeddSChris Mason btrfs_tree_unlock(left); 30085f39d397SChris Mason free_extent_buffer(left); 3009be0e5c09SChris Mason path->slots[0] -= push_items; 3010be0e5c09SChris Mason } 3011eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 3012aa5d6bedSChris Mason return ret; 3013925baeddSChris Mason out: 3014925baeddSChris Mason btrfs_tree_unlock(left); 3015925baeddSChris Mason free_extent_buffer(left); 3016925baeddSChris Mason return ret; 3017be0e5c09SChris Mason } 3018be0e5c09SChris Mason 301974123bd7SChris Mason /* 302044871b1bSChris Mason * push some data in the path leaf to the left, trying to free up at 302144871b1bSChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 302299d8f83cSChris Mason * 302399d8f83cSChris Mason * max_slot can put a limit on how far into the leaf we'll push items. The 302499d8f83cSChris Mason * item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the 302599d8f83cSChris Mason * items 302644871b1bSChris Mason */ 302744871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 302899d8f83cSChris Mason *root, struct btrfs_path *path, int min_data_size, 302999d8f83cSChris Mason int data_size, int empty, u32 max_slot) 303044871b1bSChris Mason { 303144871b1bSChris Mason struct extent_buffer *right = path->nodes[0]; 303244871b1bSChris Mason struct extent_buffer *left; 303344871b1bSChris Mason int slot; 303444871b1bSChris Mason int free_space; 303544871b1bSChris Mason u32 right_nritems; 303644871b1bSChris Mason int ret = 0; 303744871b1bSChris Mason 303844871b1bSChris Mason slot = path->slots[1]; 303944871b1bSChris Mason if (slot == 0) 304044871b1bSChris Mason return 1; 304144871b1bSChris Mason if (!path->nodes[1]) 304244871b1bSChris Mason return 1; 304344871b1bSChris Mason 304444871b1bSChris Mason right_nritems = btrfs_header_nritems(right); 304544871b1bSChris Mason if (right_nritems == 0) 304644871b1bSChris Mason return 1; 304744871b1bSChris Mason 304844871b1bSChris Mason btrfs_assert_tree_locked(path->nodes[1]); 304944871b1bSChris Mason 30504b231ae4SDavid Sterba left = btrfs_read_node_slot(path->nodes[1], slot - 1); 3051fb770ae4SLiu Bo /* 3052fb770ae4SLiu Bo * slot - 1 is not valid or we fail to read the left node, 3053fb770ae4SLiu Bo * no big deal, just return. 3054fb770ae4SLiu Bo */ 3055fb770ae4SLiu Bo if (IS_ERR(left)) 305691ca338dSTsutomu Itoh return 1; 305791ca338dSTsutomu Itoh 3058bf77467aSJosef Bacik __btrfs_tree_lock(left, BTRFS_NESTING_LEFT); 305944871b1bSChris Mason 3060e902baacSDavid Sterba free_space = btrfs_leaf_free_space(left); 306144871b1bSChris Mason if (free_space < data_size) { 306244871b1bSChris Mason ret = 1; 306344871b1bSChris Mason goto out; 306444871b1bSChris Mason } 306544871b1bSChris Mason 306644871b1bSChris Mason /* cow and double check */ 306744871b1bSChris Mason ret = btrfs_cow_block(trans, root, left, 30689631e4ccSJosef Bacik path->nodes[1], slot - 1, &left, 3069bf59a5a2SJosef Bacik BTRFS_NESTING_LEFT_COW); 307044871b1bSChris Mason if (ret) { 307144871b1bSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 307279787eaaSJeff Mahoney if (ret == -ENOSPC) 307344871b1bSChris Mason ret = 1; 307444871b1bSChris Mason goto out; 307544871b1bSChris Mason } 307644871b1bSChris Mason 3077e902baacSDavid Sterba free_space = btrfs_leaf_free_space(left); 307844871b1bSChris Mason if (free_space < data_size) { 307944871b1bSChris Mason ret = 1; 308044871b1bSChris Mason goto out; 308144871b1bSChris Mason } 308244871b1bSChris Mason 3083d16c702fSQu Wenruo if (check_sibling_keys(left, right)) { 3084d16c702fSQu Wenruo ret = -EUCLEAN; 3085d16c702fSQu Wenruo goto out; 3086d16c702fSQu Wenruo } 30878087c193SDavid Sterba return __push_leaf_left(path, min_data_size, 308899d8f83cSChris Mason empty, left, free_space, right_nritems, 308999d8f83cSChris Mason max_slot); 309044871b1bSChris Mason out: 309144871b1bSChris Mason btrfs_tree_unlock(left); 309244871b1bSChris Mason free_extent_buffer(left); 309344871b1bSChris Mason return ret; 309444871b1bSChris Mason } 309544871b1bSChris Mason 309644871b1bSChris Mason /* 309774123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 309874123bd7SChris Mason * available for the resulting leaf level of the path. 309974123bd7SChris Mason */ 3100143bede5SJeff Mahoney static noinline void copy_for_split(struct btrfs_trans_handle *trans, 310144871b1bSChris Mason struct btrfs_path *path, 310244871b1bSChris Mason struct extent_buffer *l, 310344871b1bSChris Mason struct extent_buffer *right, 310444871b1bSChris Mason int slot, int mid, int nritems) 3105be0e5c09SChris Mason { 310694f94ad9SDavid Sterba struct btrfs_fs_info *fs_info = trans->fs_info; 3107be0e5c09SChris Mason int data_copy_size; 3108be0e5c09SChris Mason int rt_data_off; 3109be0e5c09SChris Mason int i; 3110d4dbff95SChris Mason struct btrfs_disk_key disk_key; 3111cfed81a0SChris Mason struct btrfs_map_token token; 3112cfed81a0SChris Mason 31135f39d397SChris Mason nritems = nritems - mid; 31145f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 31158f881e8cSDavid Sterba data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(l); 31165f39d397SChris Mason 31175f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 31185f39d397SChris Mason btrfs_item_nr_offset(mid), 31195f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 31205f39d397SChris Mason 31215f39d397SChris Mason copy_extent_buffer(right, l, 31223d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + BTRFS_LEAF_DATA_SIZE(fs_info) - 31233d9ec8c4SNikolay Borisov data_copy_size, BTRFS_LEAF_DATA_OFFSET + 31248f881e8cSDavid Sterba leaf_data_end(l), data_copy_size); 312574123bd7SChris Mason 31260b246afaSJeff Mahoney rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_end_nr(l, mid); 31275f39d397SChris Mason 3128c82f823cSDavid Sterba btrfs_init_map_token(&token, right); 31295f39d397SChris Mason for (i = 0; i < nritems; i++) { 3130dd3cc16bSRoss Kirk struct btrfs_item *item = btrfs_item_nr(i); 3131db94535dSChris Mason u32 ioff; 3132db94535dSChris Mason 3133cc4c13d5SDavid Sterba ioff = btrfs_token_item_offset(&token, item); 3134cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, ioff + rt_data_off); 31350783fcfcSChris Mason } 313674123bd7SChris Mason 31375f39d397SChris Mason btrfs_set_header_nritems(l, mid); 31385f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 31396ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1); 31405f39d397SChris Mason 31415f39d397SChris Mason btrfs_mark_buffer_dirty(right); 31425f39d397SChris Mason btrfs_mark_buffer_dirty(l); 3143eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 31445f39d397SChris Mason 3145be0e5c09SChris Mason if (mid <= slot) { 3146925baeddSChris Mason btrfs_tree_unlock(path->nodes[0]); 31475f39d397SChris Mason free_extent_buffer(path->nodes[0]); 31485f39d397SChris Mason path->nodes[0] = right; 3149be0e5c09SChris Mason path->slots[0] -= mid; 3150be0e5c09SChris Mason path->slots[1] += 1; 3151925baeddSChris Mason } else { 3152925baeddSChris Mason btrfs_tree_unlock(right); 31535f39d397SChris Mason free_extent_buffer(right); 3154925baeddSChris Mason } 31555f39d397SChris Mason 3156eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 315744871b1bSChris Mason } 315844871b1bSChris Mason 315944871b1bSChris Mason /* 316099d8f83cSChris Mason * double splits happen when we need to insert a big item in the middle 316199d8f83cSChris Mason * of a leaf. A double split can leave us with 3 mostly empty leaves: 316299d8f83cSChris Mason * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ] 316399d8f83cSChris Mason * A B C 316499d8f83cSChris Mason * 316599d8f83cSChris Mason * We avoid this by trying to push the items on either side of our target 316699d8f83cSChris Mason * into the adjacent leaves. If all goes well we can avoid the double split 316799d8f83cSChris Mason * completely. 316899d8f83cSChris Mason */ 316999d8f83cSChris Mason static noinline int push_for_double_split(struct btrfs_trans_handle *trans, 317099d8f83cSChris Mason struct btrfs_root *root, 317199d8f83cSChris Mason struct btrfs_path *path, 317299d8f83cSChris Mason int data_size) 317399d8f83cSChris Mason { 317499d8f83cSChris Mason int ret; 317599d8f83cSChris Mason int progress = 0; 317699d8f83cSChris Mason int slot; 317799d8f83cSChris Mason u32 nritems; 31785a4267caSFilipe David Borba Manana int space_needed = data_size; 317999d8f83cSChris Mason 318099d8f83cSChris Mason slot = path->slots[0]; 31815a4267caSFilipe David Borba Manana if (slot < btrfs_header_nritems(path->nodes[0])) 3182e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(path->nodes[0]); 318399d8f83cSChris Mason 318499d8f83cSChris Mason /* 318599d8f83cSChris Mason * try to push all the items after our slot into the 318699d8f83cSChris Mason * right leaf 318799d8f83cSChris Mason */ 31885a4267caSFilipe David Borba Manana ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot); 318999d8f83cSChris Mason if (ret < 0) 319099d8f83cSChris Mason return ret; 319199d8f83cSChris Mason 319299d8f83cSChris Mason if (ret == 0) 319399d8f83cSChris Mason progress++; 319499d8f83cSChris Mason 319599d8f83cSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 319699d8f83cSChris Mason /* 319799d8f83cSChris Mason * our goal is to get our slot at the start or end of a leaf. If 319899d8f83cSChris Mason * we've done so we're done 319999d8f83cSChris Mason */ 320099d8f83cSChris Mason if (path->slots[0] == 0 || path->slots[0] == nritems) 320199d8f83cSChris Mason return 0; 320299d8f83cSChris Mason 3203e902baacSDavid Sterba if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) 320499d8f83cSChris Mason return 0; 320599d8f83cSChris Mason 320699d8f83cSChris Mason /* try to push all the items before our slot into the next leaf */ 320799d8f83cSChris Mason slot = path->slots[0]; 3208263d3995SFilipe Manana space_needed = data_size; 3209263d3995SFilipe Manana if (slot > 0) 3210e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(path->nodes[0]); 32115a4267caSFilipe David Borba Manana ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot); 321299d8f83cSChris Mason if (ret < 0) 321399d8f83cSChris Mason return ret; 321499d8f83cSChris Mason 321599d8f83cSChris Mason if (ret == 0) 321699d8f83cSChris Mason progress++; 321799d8f83cSChris Mason 321899d8f83cSChris Mason if (progress) 321999d8f83cSChris Mason return 0; 322099d8f83cSChris Mason return 1; 322199d8f83cSChris Mason } 322299d8f83cSChris Mason 322399d8f83cSChris Mason /* 322444871b1bSChris Mason * split the path's leaf in two, making sure there is at least data_size 322544871b1bSChris Mason * available for the resulting leaf level of the path. 322644871b1bSChris Mason * 322744871b1bSChris Mason * returns 0 if all went well and < 0 on failure. 322844871b1bSChris Mason */ 322944871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans, 323044871b1bSChris Mason struct btrfs_root *root, 3231310712b2SOmar Sandoval const struct btrfs_key *ins_key, 323244871b1bSChris Mason struct btrfs_path *path, int data_size, 323344871b1bSChris Mason int extend) 323444871b1bSChris Mason { 32355d4f98a2SYan Zheng struct btrfs_disk_key disk_key; 323644871b1bSChris Mason struct extent_buffer *l; 323744871b1bSChris Mason u32 nritems; 323844871b1bSChris Mason int mid; 323944871b1bSChris Mason int slot; 324044871b1bSChris Mason struct extent_buffer *right; 3241b7a0365eSDaniel Dressler struct btrfs_fs_info *fs_info = root->fs_info; 324244871b1bSChris Mason int ret = 0; 324344871b1bSChris Mason int wret; 32445d4f98a2SYan Zheng int split; 324544871b1bSChris Mason int num_doubles = 0; 324699d8f83cSChris Mason int tried_avoid_double = 0; 324744871b1bSChris Mason 3248a5719521SYan, Zheng l = path->nodes[0]; 3249a5719521SYan, Zheng slot = path->slots[0]; 3250a5719521SYan, Zheng if (extend && data_size + btrfs_item_size_nr(l, slot) + 32510b246afaSJeff Mahoney sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info)) 3252a5719521SYan, Zheng return -EOVERFLOW; 3253a5719521SYan, Zheng 325444871b1bSChris Mason /* first try to make some room by pushing left and right */ 325533157e05SLiu Bo if (data_size && path->nodes[1]) { 32565a4267caSFilipe David Borba Manana int space_needed = data_size; 32575a4267caSFilipe David Borba Manana 32585a4267caSFilipe David Borba Manana if (slot < btrfs_header_nritems(l)) 3259e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(l); 32605a4267caSFilipe David Borba Manana 32615a4267caSFilipe David Borba Manana wret = push_leaf_right(trans, root, path, space_needed, 32625a4267caSFilipe David Borba Manana space_needed, 0, 0); 326344871b1bSChris Mason if (wret < 0) 326444871b1bSChris Mason return wret; 326544871b1bSChris Mason if (wret) { 3266263d3995SFilipe Manana space_needed = data_size; 3267263d3995SFilipe Manana if (slot > 0) 3268e902baacSDavid Sterba space_needed -= btrfs_leaf_free_space(l); 32695a4267caSFilipe David Borba Manana wret = push_leaf_left(trans, root, path, space_needed, 32705a4267caSFilipe David Borba Manana space_needed, 0, (u32)-1); 327144871b1bSChris Mason if (wret < 0) 327244871b1bSChris Mason return wret; 327344871b1bSChris Mason } 327444871b1bSChris Mason l = path->nodes[0]; 327544871b1bSChris Mason 327644871b1bSChris Mason /* did the pushes work? */ 3277e902baacSDavid Sterba if (btrfs_leaf_free_space(l) >= data_size) 327844871b1bSChris Mason return 0; 327944871b1bSChris Mason } 328044871b1bSChris Mason 328144871b1bSChris Mason if (!path->nodes[1]) { 3282fdd99c72SLiu Bo ret = insert_new_root(trans, root, path, 1); 328344871b1bSChris Mason if (ret) 328444871b1bSChris Mason return ret; 328544871b1bSChris Mason } 328644871b1bSChris Mason again: 32875d4f98a2SYan Zheng split = 1; 328844871b1bSChris Mason l = path->nodes[0]; 328944871b1bSChris Mason slot = path->slots[0]; 329044871b1bSChris Mason nritems = btrfs_header_nritems(l); 329144871b1bSChris Mason mid = (nritems + 1) / 2; 329244871b1bSChris Mason 32935d4f98a2SYan Zheng if (mid <= slot) { 32945d4f98a2SYan Zheng if (nritems == 1 || 32955d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + data_size > 32960b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info)) { 32975d4f98a2SYan Zheng if (slot >= nritems) { 32985d4f98a2SYan Zheng split = 0; 32995d4f98a2SYan Zheng } else { 33005d4f98a2SYan Zheng mid = slot; 33015d4f98a2SYan Zheng if (mid != nritems && 33025d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 33030b246afaSJeff Mahoney data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) { 330499d8f83cSChris Mason if (data_size && !tried_avoid_double) 330599d8f83cSChris Mason goto push_for_double; 33065d4f98a2SYan Zheng split = 2; 33075d4f98a2SYan Zheng } 33085d4f98a2SYan Zheng } 33095d4f98a2SYan Zheng } 33105d4f98a2SYan Zheng } else { 33115d4f98a2SYan Zheng if (leaf_space_used(l, 0, mid) + data_size > 33120b246afaSJeff Mahoney BTRFS_LEAF_DATA_SIZE(fs_info)) { 33135d4f98a2SYan Zheng if (!extend && data_size && slot == 0) { 33145d4f98a2SYan Zheng split = 0; 33155d4f98a2SYan Zheng } else if ((extend || !data_size) && slot == 0) { 33165d4f98a2SYan Zheng mid = 1; 33175d4f98a2SYan Zheng } else { 33185d4f98a2SYan Zheng mid = slot; 33195d4f98a2SYan Zheng if (mid != nritems && 33205d4f98a2SYan Zheng leaf_space_used(l, mid, nritems - mid) + 33210b246afaSJeff Mahoney data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) { 332299d8f83cSChris Mason if (data_size && !tried_avoid_double) 332399d8f83cSChris Mason goto push_for_double; 33245d4f98a2SYan Zheng split = 2; 33255d4f98a2SYan Zheng } 33265d4f98a2SYan Zheng } 33275d4f98a2SYan Zheng } 33285d4f98a2SYan Zheng } 33295d4f98a2SYan Zheng 33305d4f98a2SYan Zheng if (split == 0) 33315d4f98a2SYan Zheng btrfs_cpu_key_to_disk(&disk_key, ins_key); 33325d4f98a2SYan Zheng else 33335d4f98a2SYan Zheng btrfs_item_key(l, &disk_key, mid); 33345d4f98a2SYan Zheng 3335ca9d473aSJosef Bacik /* 3336ca9d473aSJosef Bacik * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double 3337ca9d473aSJosef Bacik * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES 3338ca9d473aSJosef Bacik * subclasses, which is 8 at the time of this patch, and we've maxed it 3339ca9d473aSJosef Bacik * out. In the future we could add a 3340ca9d473aSJosef Bacik * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just 3341ca9d473aSJosef Bacik * use BTRFS_NESTING_NEW_ROOT. 3342ca9d473aSJosef Bacik */ 3343*79bd3712SFilipe Manana right = btrfs_alloc_tree_block(trans, root, 0, root->root_key.objectid, 3344*79bd3712SFilipe Manana &disk_key, 0, l->start, 0, 3345*79bd3712SFilipe Manana num_doubles ? BTRFS_NESTING_NEW_ROOT : 3346ca9d473aSJosef Bacik BTRFS_NESTING_SPLIT); 3347f0486c68SYan, Zheng if (IS_ERR(right)) 334844871b1bSChris Mason return PTR_ERR(right); 3349f0486c68SYan, Zheng 33500b246afaSJeff Mahoney root_add_used(root, fs_info->nodesize); 335144871b1bSChris Mason 33525d4f98a2SYan Zheng if (split == 0) { 335344871b1bSChris Mason if (mid <= slot) { 335444871b1bSChris Mason btrfs_set_header_nritems(right, 0); 33556ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, 33562ff7e61eSJeff Mahoney right->start, path->slots[1] + 1, 1); 335744871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 335844871b1bSChris Mason free_extent_buffer(path->nodes[0]); 335944871b1bSChris Mason path->nodes[0] = right; 336044871b1bSChris Mason path->slots[0] = 0; 336144871b1bSChris Mason path->slots[1] += 1; 336244871b1bSChris Mason } else { 336344871b1bSChris Mason btrfs_set_header_nritems(right, 0); 33646ad3cf6dSDavid Sterba insert_ptr(trans, path, &disk_key, 33652ff7e61eSJeff Mahoney right->start, path->slots[1], 1); 336644871b1bSChris Mason btrfs_tree_unlock(path->nodes[0]); 336744871b1bSChris Mason free_extent_buffer(path->nodes[0]); 336844871b1bSChris Mason path->nodes[0] = right; 336944871b1bSChris Mason path->slots[0] = 0; 3370143bede5SJeff Mahoney if (path->slots[1] == 0) 3371b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 33725d4f98a2SYan Zheng } 3373196e0249SLiu Bo /* 3374196e0249SLiu Bo * We create a new leaf 'right' for the required ins_len and 3375196e0249SLiu Bo * we'll do btrfs_mark_buffer_dirty() on this leaf after copying 3376196e0249SLiu Bo * the content of ins_len to 'right'. 3377196e0249SLiu Bo */ 337844871b1bSChris Mason return ret; 337944871b1bSChris Mason } 338044871b1bSChris Mason 338194f94ad9SDavid Sterba copy_for_split(trans, path, l, right, slot, mid, nritems); 338244871b1bSChris Mason 33835d4f98a2SYan Zheng if (split == 2) { 3384cc0c5538SChris Mason BUG_ON(num_doubles != 0); 3385cc0c5538SChris Mason num_doubles++; 3386cc0c5538SChris Mason goto again; 33873326d1b0SChris Mason } 338844871b1bSChris Mason 3389143bede5SJeff Mahoney return 0; 339099d8f83cSChris Mason 339199d8f83cSChris Mason push_for_double: 339299d8f83cSChris Mason push_for_double_split(trans, root, path, data_size); 339399d8f83cSChris Mason tried_avoid_double = 1; 3394e902baacSDavid Sterba if (btrfs_leaf_free_space(path->nodes[0]) >= data_size) 339599d8f83cSChris Mason return 0; 339699d8f83cSChris Mason goto again; 3397be0e5c09SChris Mason } 3398be0e5c09SChris Mason 3399ad48fd75SYan, Zheng static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans, 3400ad48fd75SYan, Zheng struct btrfs_root *root, 3401ad48fd75SYan, Zheng struct btrfs_path *path, int ins_len) 3402ad48fd75SYan, Zheng { 3403ad48fd75SYan, Zheng struct btrfs_key key; 3404ad48fd75SYan, Zheng struct extent_buffer *leaf; 3405ad48fd75SYan, Zheng struct btrfs_file_extent_item *fi; 3406ad48fd75SYan, Zheng u64 extent_len = 0; 3407ad48fd75SYan, Zheng u32 item_size; 3408ad48fd75SYan, Zheng int ret; 3409ad48fd75SYan, Zheng 3410ad48fd75SYan, Zheng leaf = path->nodes[0]; 3411ad48fd75SYan, Zheng btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 3412ad48fd75SYan, Zheng 3413ad48fd75SYan, Zheng BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY && 3414ad48fd75SYan, Zheng key.type != BTRFS_EXTENT_CSUM_KEY); 3415ad48fd75SYan, Zheng 3416e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) >= ins_len) 3417ad48fd75SYan, Zheng return 0; 3418ad48fd75SYan, Zheng 3419ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3420ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3421ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3422ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3423ad48fd75SYan, Zheng extent_len = btrfs_file_extent_num_bytes(leaf, fi); 3424ad48fd75SYan, Zheng } 3425b3b4aa74SDavid Sterba btrfs_release_path(path); 3426ad48fd75SYan, Zheng 3427ad48fd75SYan, Zheng path->keep_locks = 1; 3428ad48fd75SYan, Zheng path->search_for_split = 1; 3429ad48fd75SYan, Zheng ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 3430ad48fd75SYan, Zheng path->search_for_split = 0; 3431a8df6fe6SFilipe Manana if (ret > 0) 3432a8df6fe6SFilipe Manana ret = -EAGAIN; 3433ad48fd75SYan, Zheng if (ret < 0) 3434ad48fd75SYan, Zheng goto err; 3435ad48fd75SYan, Zheng 3436ad48fd75SYan, Zheng ret = -EAGAIN; 3437ad48fd75SYan, Zheng leaf = path->nodes[0]; 3438a8df6fe6SFilipe Manana /* if our item isn't there, return now */ 3439a8df6fe6SFilipe Manana if (item_size != btrfs_item_size_nr(leaf, path->slots[0])) 3440ad48fd75SYan, Zheng goto err; 3441ad48fd75SYan, Zheng 3442109f6aefSChris Mason /* the leaf has changed, it now has room. return now */ 3443e902baacSDavid Sterba if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len) 3444109f6aefSChris Mason goto err; 3445109f6aefSChris Mason 3446ad48fd75SYan, Zheng if (key.type == BTRFS_EXTENT_DATA_KEY) { 3447ad48fd75SYan, Zheng fi = btrfs_item_ptr(leaf, path->slots[0], 3448ad48fd75SYan, Zheng struct btrfs_file_extent_item); 3449ad48fd75SYan, Zheng if (extent_len != btrfs_file_extent_num_bytes(leaf, fi)) 3450ad48fd75SYan, Zheng goto err; 3451ad48fd75SYan, Zheng } 3452ad48fd75SYan, Zheng 3453ad48fd75SYan, Zheng ret = split_leaf(trans, root, &key, path, ins_len, 1); 3454f0486c68SYan, Zheng if (ret) 3455f0486c68SYan, Zheng goto err; 3456ad48fd75SYan, Zheng 3457ad48fd75SYan, Zheng path->keep_locks = 0; 3458ad48fd75SYan, Zheng btrfs_unlock_up_safe(path, 1); 3459ad48fd75SYan, Zheng return 0; 3460ad48fd75SYan, Zheng err: 3461ad48fd75SYan, Zheng path->keep_locks = 0; 3462ad48fd75SYan, Zheng return ret; 3463ad48fd75SYan, Zheng } 3464ad48fd75SYan, Zheng 346525263cd7SDavid Sterba static noinline int split_item(struct btrfs_path *path, 3466310712b2SOmar Sandoval const struct btrfs_key *new_key, 3467459931ecSChris Mason unsigned long split_offset) 3468459931ecSChris Mason { 3469459931ecSChris Mason struct extent_buffer *leaf; 3470459931ecSChris Mason struct btrfs_item *item; 3471459931ecSChris Mason struct btrfs_item *new_item; 3472459931ecSChris Mason int slot; 3473ad48fd75SYan, Zheng char *buf; 3474459931ecSChris Mason u32 nritems; 3475ad48fd75SYan, Zheng u32 item_size; 3476459931ecSChris Mason u32 orig_offset; 3477459931ecSChris Mason struct btrfs_disk_key disk_key; 3478459931ecSChris Mason 3479459931ecSChris Mason leaf = path->nodes[0]; 3480e902baacSDavid Sterba BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)); 3481b9473439SChris Mason 3482dd3cc16bSRoss Kirk item = btrfs_item_nr(path->slots[0]); 3483459931ecSChris Mason orig_offset = btrfs_item_offset(leaf, item); 3484459931ecSChris Mason item_size = btrfs_item_size(leaf, item); 3485459931ecSChris Mason 3486459931ecSChris Mason buf = kmalloc(item_size, GFP_NOFS); 3487ad48fd75SYan, Zheng if (!buf) 3488ad48fd75SYan, Zheng return -ENOMEM; 3489ad48fd75SYan, Zheng 3490459931ecSChris Mason read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf, 3491459931ecSChris Mason path->slots[0]), item_size); 3492ad48fd75SYan, Zheng 3493459931ecSChris Mason slot = path->slots[0] + 1; 3494459931ecSChris Mason nritems = btrfs_header_nritems(leaf); 3495459931ecSChris Mason if (slot != nritems) { 3496459931ecSChris Mason /* shift the items */ 3497459931ecSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 3498459931ecSChris Mason btrfs_item_nr_offset(slot), 3499459931ecSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3500459931ecSChris Mason } 3501459931ecSChris Mason 3502459931ecSChris Mason btrfs_cpu_key_to_disk(&disk_key, new_key); 3503459931ecSChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3504459931ecSChris Mason 3505dd3cc16bSRoss Kirk new_item = btrfs_item_nr(slot); 3506459931ecSChris Mason 3507459931ecSChris Mason btrfs_set_item_offset(leaf, new_item, orig_offset); 3508459931ecSChris Mason btrfs_set_item_size(leaf, new_item, item_size - split_offset); 3509459931ecSChris Mason 3510459931ecSChris Mason btrfs_set_item_offset(leaf, item, 3511459931ecSChris Mason orig_offset + item_size - split_offset); 3512459931ecSChris Mason btrfs_set_item_size(leaf, item, split_offset); 3513459931ecSChris Mason 3514459931ecSChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 3515459931ecSChris Mason 3516459931ecSChris Mason /* write the data for the start of the original item */ 3517459931ecSChris Mason write_extent_buffer(leaf, buf, 3518459931ecSChris Mason btrfs_item_ptr_offset(leaf, path->slots[0]), 3519459931ecSChris Mason split_offset); 3520459931ecSChris Mason 3521459931ecSChris Mason /* write the data for the new item */ 3522459931ecSChris Mason write_extent_buffer(leaf, buf + split_offset, 3523459931ecSChris Mason btrfs_item_ptr_offset(leaf, slot), 3524459931ecSChris Mason item_size - split_offset); 3525459931ecSChris Mason btrfs_mark_buffer_dirty(leaf); 3526459931ecSChris Mason 3527e902baacSDavid Sterba BUG_ON(btrfs_leaf_free_space(leaf) < 0); 3528459931ecSChris Mason kfree(buf); 3529ad48fd75SYan, Zheng return 0; 3530ad48fd75SYan, Zheng } 3531ad48fd75SYan, Zheng 3532ad48fd75SYan, Zheng /* 3533ad48fd75SYan, Zheng * This function splits a single item into two items, 3534ad48fd75SYan, Zheng * giving 'new_key' to the new item and splitting the 3535ad48fd75SYan, Zheng * old one at split_offset (from the start of the item). 3536ad48fd75SYan, Zheng * 3537ad48fd75SYan, Zheng * The path may be released by this operation. After 3538ad48fd75SYan, Zheng * the split, the path is pointing to the old item. The 3539ad48fd75SYan, Zheng * new item is going to be in the same node as the old one. 3540ad48fd75SYan, Zheng * 3541ad48fd75SYan, Zheng * Note, the item being split must be smaller enough to live alone on 3542ad48fd75SYan, Zheng * a tree block with room for one extra struct btrfs_item 3543ad48fd75SYan, Zheng * 3544ad48fd75SYan, Zheng * This allows us to split the item in place, keeping a lock on the 3545ad48fd75SYan, Zheng * leaf the entire time. 3546ad48fd75SYan, Zheng */ 3547ad48fd75SYan, Zheng int btrfs_split_item(struct btrfs_trans_handle *trans, 3548ad48fd75SYan, Zheng struct btrfs_root *root, 3549ad48fd75SYan, Zheng struct btrfs_path *path, 3550310712b2SOmar Sandoval const struct btrfs_key *new_key, 3551ad48fd75SYan, Zheng unsigned long split_offset) 3552ad48fd75SYan, Zheng { 3553ad48fd75SYan, Zheng int ret; 3554ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3555ad48fd75SYan, Zheng sizeof(struct btrfs_item)); 3556ad48fd75SYan, Zheng if (ret) 3557459931ecSChris Mason return ret; 3558ad48fd75SYan, Zheng 355925263cd7SDavid Sterba ret = split_item(path, new_key, split_offset); 3560ad48fd75SYan, Zheng return ret; 3561ad48fd75SYan, Zheng } 3562ad48fd75SYan, Zheng 3563ad48fd75SYan, Zheng /* 3564ad48fd75SYan, Zheng * This function duplicate a item, giving 'new_key' to the new item. 3565ad48fd75SYan, Zheng * It guarantees both items live in the same tree leaf and the new item 3566ad48fd75SYan, Zheng * is contiguous with the original item. 3567ad48fd75SYan, Zheng * 3568ad48fd75SYan, Zheng * This allows us to split file extent in place, keeping a lock on the 3569ad48fd75SYan, Zheng * leaf the entire time. 3570ad48fd75SYan, Zheng */ 3571ad48fd75SYan, Zheng int btrfs_duplicate_item(struct btrfs_trans_handle *trans, 3572ad48fd75SYan, Zheng struct btrfs_root *root, 3573ad48fd75SYan, Zheng struct btrfs_path *path, 3574310712b2SOmar Sandoval const struct btrfs_key *new_key) 3575ad48fd75SYan, Zheng { 3576ad48fd75SYan, Zheng struct extent_buffer *leaf; 3577ad48fd75SYan, Zheng int ret; 3578ad48fd75SYan, Zheng u32 item_size; 3579ad48fd75SYan, Zheng 3580ad48fd75SYan, Zheng leaf = path->nodes[0]; 3581ad48fd75SYan, Zheng item_size = btrfs_item_size_nr(leaf, path->slots[0]); 3582ad48fd75SYan, Zheng ret = setup_leaf_for_split(trans, root, path, 3583ad48fd75SYan, Zheng item_size + sizeof(struct btrfs_item)); 3584ad48fd75SYan, Zheng if (ret) 3585ad48fd75SYan, Zheng return ret; 3586ad48fd75SYan, Zheng 3587ad48fd75SYan, Zheng path->slots[0]++; 3588fc0d82e1SNikolay Borisov setup_items_for_insert(root, path, new_key, &item_size, 1); 3589ad48fd75SYan, Zheng leaf = path->nodes[0]; 3590ad48fd75SYan, Zheng memcpy_extent_buffer(leaf, 3591ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0]), 3592ad48fd75SYan, Zheng btrfs_item_ptr_offset(leaf, path->slots[0] - 1), 3593ad48fd75SYan, Zheng item_size); 3594ad48fd75SYan, Zheng return 0; 3595459931ecSChris Mason } 3596459931ecSChris Mason 3597459931ecSChris Mason /* 3598d352ac68SChris Mason * make the item pointed to by the path smaller. new_size indicates 3599d352ac68SChris Mason * how small to make it, and from_end tells us if we just chop bytes 3600d352ac68SChris Mason * off the end of the item or if we shift the item to chop bytes off 3601d352ac68SChris Mason * the front. 3602d352ac68SChris Mason */ 360378ac4f9eSDavid Sterba void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end) 3604b18c6685SChris Mason { 3605b18c6685SChris Mason int slot; 36065f39d397SChris Mason struct extent_buffer *leaf; 36075f39d397SChris Mason struct btrfs_item *item; 3608b18c6685SChris Mason u32 nritems; 3609b18c6685SChris Mason unsigned int data_end; 3610b18c6685SChris Mason unsigned int old_data_start; 3611b18c6685SChris Mason unsigned int old_size; 3612b18c6685SChris Mason unsigned int size_diff; 3613b18c6685SChris Mason int i; 3614cfed81a0SChris Mason struct btrfs_map_token token; 3615cfed81a0SChris Mason 36165f39d397SChris Mason leaf = path->nodes[0]; 3617179e29e4SChris Mason slot = path->slots[0]; 3618179e29e4SChris Mason 3619179e29e4SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 3620179e29e4SChris Mason if (old_size == new_size) 3621143bede5SJeff Mahoney return; 3622b18c6685SChris Mason 36235f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 36248f881e8cSDavid Sterba data_end = leaf_data_end(leaf); 3625b18c6685SChris Mason 36265f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 3627179e29e4SChris Mason 3628b18c6685SChris Mason size_diff = old_size - new_size; 3629b18c6685SChris Mason 3630b18c6685SChris Mason BUG_ON(slot < 0); 3631b18c6685SChris Mason BUG_ON(slot >= nritems); 3632b18c6685SChris Mason 3633b18c6685SChris Mason /* 3634b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3635b18c6685SChris Mason */ 3636b18c6685SChris Mason /* first correct the data pointers */ 3637c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 3638b18c6685SChris Mason for (i = slot; i < nritems; i++) { 36395f39d397SChris Mason u32 ioff; 3640dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 3641db94535dSChris Mason 3642cc4c13d5SDavid Sterba ioff = btrfs_token_item_offset(&token, item); 3643cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, ioff + size_diff); 3644b18c6685SChris Mason } 3645db94535dSChris Mason 3646b18c6685SChris Mason /* shift the data */ 3647179e29e4SChris Mason if (from_end) { 36483d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 36493d9ec8c4SNikolay Borisov data_end + size_diff, BTRFS_LEAF_DATA_OFFSET + 3650b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 3651179e29e4SChris Mason } else { 3652179e29e4SChris Mason struct btrfs_disk_key disk_key; 3653179e29e4SChris Mason u64 offset; 3654179e29e4SChris Mason 3655179e29e4SChris Mason btrfs_item_key(leaf, &disk_key, slot); 3656179e29e4SChris Mason 3657179e29e4SChris Mason if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) { 3658179e29e4SChris Mason unsigned long ptr; 3659179e29e4SChris Mason struct btrfs_file_extent_item *fi; 3660179e29e4SChris Mason 3661179e29e4SChris Mason fi = btrfs_item_ptr(leaf, slot, 3662179e29e4SChris Mason struct btrfs_file_extent_item); 3663179e29e4SChris Mason fi = (struct btrfs_file_extent_item *)( 3664179e29e4SChris Mason (unsigned long)fi - size_diff); 3665179e29e4SChris Mason 3666179e29e4SChris Mason if (btrfs_file_extent_type(leaf, fi) == 3667179e29e4SChris Mason BTRFS_FILE_EXTENT_INLINE) { 3668179e29e4SChris Mason ptr = btrfs_item_ptr_offset(leaf, slot); 3669179e29e4SChris Mason memmove_extent_buffer(leaf, ptr, 3670179e29e4SChris Mason (unsigned long)fi, 36717ec20afbSDavid Sterba BTRFS_FILE_EXTENT_INLINE_DATA_START); 3672179e29e4SChris Mason } 3673179e29e4SChris Mason } 3674179e29e4SChris Mason 36753d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 36763d9ec8c4SNikolay Borisov data_end + size_diff, BTRFS_LEAF_DATA_OFFSET + 3677179e29e4SChris Mason data_end, old_data_start - data_end); 3678179e29e4SChris Mason 3679179e29e4SChris Mason offset = btrfs_disk_key_offset(&disk_key); 3680179e29e4SChris Mason btrfs_set_disk_key_offset(&disk_key, offset + size_diff); 3681179e29e4SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 3682179e29e4SChris Mason if (slot == 0) 3683b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 3684179e29e4SChris Mason } 36855f39d397SChris Mason 3686dd3cc16bSRoss Kirk item = btrfs_item_nr(slot); 36875f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 36885f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 3689b18c6685SChris Mason 3690e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < 0) { 3691a4f78750SDavid Sterba btrfs_print_leaf(leaf); 3692b18c6685SChris Mason BUG(); 36935f39d397SChris Mason } 3694b18c6685SChris Mason } 3695b18c6685SChris Mason 3696d352ac68SChris Mason /* 36978f69dbd2SStefan Behrens * make the item pointed to by the path bigger, data_size is the added size. 3698d352ac68SChris Mason */ 3699c71dd880SDavid Sterba void btrfs_extend_item(struct btrfs_path *path, u32 data_size) 37006567e837SChris Mason { 37016567e837SChris Mason int slot; 37025f39d397SChris Mason struct extent_buffer *leaf; 37035f39d397SChris Mason struct btrfs_item *item; 37046567e837SChris Mason u32 nritems; 37056567e837SChris Mason unsigned int data_end; 37066567e837SChris Mason unsigned int old_data; 37076567e837SChris Mason unsigned int old_size; 37086567e837SChris Mason int i; 3709cfed81a0SChris Mason struct btrfs_map_token token; 3710cfed81a0SChris Mason 37115f39d397SChris Mason leaf = path->nodes[0]; 37126567e837SChris Mason 37135f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 37148f881e8cSDavid Sterba data_end = leaf_data_end(leaf); 37156567e837SChris Mason 3716e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < data_size) { 3717a4f78750SDavid Sterba btrfs_print_leaf(leaf); 37186567e837SChris Mason BUG(); 37195f39d397SChris Mason } 37206567e837SChris Mason slot = path->slots[0]; 37215f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 37226567e837SChris Mason 37236567e837SChris Mason BUG_ON(slot < 0); 37243326d1b0SChris Mason if (slot >= nritems) { 3725a4f78750SDavid Sterba btrfs_print_leaf(leaf); 3726c71dd880SDavid Sterba btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d", 3727d397712bSChris Mason slot, nritems); 3728290342f6SArnd Bergmann BUG(); 37293326d1b0SChris Mason } 37306567e837SChris Mason 37316567e837SChris Mason /* 37326567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 37336567e837SChris Mason */ 37346567e837SChris Mason /* first correct the data pointers */ 3735c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 37366567e837SChris Mason for (i = slot; i < nritems; i++) { 37375f39d397SChris Mason u32 ioff; 3738dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 3739db94535dSChris Mason 3740cc4c13d5SDavid Sterba ioff = btrfs_token_item_offset(&token, item); 3741cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, ioff - data_size); 37426567e837SChris Mason } 37435f39d397SChris Mason 37446567e837SChris Mason /* shift the data */ 37453d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 37463d9ec8c4SNikolay Borisov data_end - data_size, BTRFS_LEAF_DATA_OFFSET + 37476567e837SChris Mason data_end, old_data - data_end); 37485f39d397SChris Mason 37496567e837SChris Mason data_end = old_data; 37505f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 3751dd3cc16bSRoss Kirk item = btrfs_item_nr(slot); 37525f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 37535f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 37546567e837SChris Mason 3755e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < 0) { 3756a4f78750SDavid Sterba btrfs_print_leaf(leaf); 37576567e837SChris Mason BUG(); 37585f39d397SChris Mason } 37596567e837SChris Mason } 37606567e837SChris Mason 3761da9ffb24SNikolay Borisov /** 3762da9ffb24SNikolay Borisov * setup_items_for_insert - Helper called before inserting one or more items 3763da9ffb24SNikolay Borisov * to a leaf. Main purpose is to save stack depth by doing the bulk of the work 3764da9ffb24SNikolay Borisov * in a function that doesn't call btrfs_search_slot 3765da9ffb24SNikolay Borisov * 3766da9ffb24SNikolay Borisov * @root: root we are inserting items to 3767da9ffb24SNikolay Borisov * @path: points to the leaf/slot where we are going to insert new items 3768da9ffb24SNikolay Borisov * @cpu_key: array of keys for items to be inserted 3769da9ffb24SNikolay Borisov * @data_size: size of the body of each item we are going to insert 3770da9ffb24SNikolay Borisov * @nr: size of @cpu_key/@data_size arrays 377174123bd7SChris Mason */ 3772afe5fea7STsutomu Itoh void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path, 3773310712b2SOmar Sandoval const struct btrfs_key *cpu_key, u32 *data_size, 3774fc0d82e1SNikolay Borisov int nr) 3775be0e5c09SChris Mason { 37760b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 37775f39d397SChris Mason struct btrfs_item *item; 37789c58309dSChris Mason int i; 37797518a238SChris Mason u32 nritems; 3780be0e5c09SChris Mason unsigned int data_end; 3781e2fa7227SChris Mason struct btrfs_disk_key disk_key; 378244871b1bSChris Mason struct extent_buffer *leaf; 378344871b1bSChris Mason int slot; 3784cfed81a0SChris Mason struct btrfs_map_token token; 3785fc0d82e1SNikolay Borisov u32 total_size; 3786fc0d82e1SNikolay Borisov u32 total_data = 0; 3787fc0d82e1SNikolay Borisov 3788fc0d82e1SNikolay Borisov for (i = 0; i < nr; i++) 3789fc0d82e1SNikolay Borisov total_data += data_size[i]; 3790fc0d82e1SNikolay Borisov total_size = total_data + (nr * sizeof(struct btrfs_item)); 3791cfed81a0SChris Mason 379224cdc847SFilipe Manana if (path->slots[0] == 0) { 379324cdc847SFilipe Manana btrfs_cpu_key_to_disk(&disk_key, cpu_key); 3794b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 379524cdc847SFilipe Manana } 379624cdc847SFilipe Manana btrfs_unlock_up_safe(path, 1); 379724cdc847SFilipe Manana 37985f39d397SChris Mason leaf = path->nodes[0]; 379944871b1bSChris Mason slot = path->slots[0]; 380074123bd7SChris Mason 38015f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 38028f881e8cSDavid Sterba data_end = leaf_data_end(leaf); 3803eb60ceacSChris Mason 3804e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < total_size) { 3805a4f78750SDavid Sterba btrfs_print_leaf(leaf); 38060b246afaSJeff Mahoney btrfs_crit(fs_info, "not enough freespace need %u have %d", 3807e902baacSDavid Sterba total_size, btrfs_leaf_free_space(leaf)); 3808be0e5c09SChris Mason BUG(); 3809d4dbff95SChris Mason } 38105f39d397SChris Mason 3811c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 3812be0e5c09SChris Mason if (slot != nritems) { 38135f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 3814be0e5c09SChris Mason 38155f39d397SChris Mason if (old_data < data_end) { 3816a4f78750SDavid Sterba btrfs_print_leaf(leaf); 38177269ddd2SNikolay Borisov btrfs_crit(fs_info, 38187269ddd2SNikolay Borisov "item at slot %d with data offset %u beyond data end of leaf %u", 38195f39d397SChris Mason slot, old_data, data_end); 3820290342f6SArnd Bergmann BUG(); 38215f39d397SChris Mason } 3822be0e5c09SChris Mason /* 3823be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 3824be0e5c09SChris Mason */ 3825be0e5c09SChris Mason /* first correct the data pointers */ 38260783fcfcSChris Mason for (i = slot; i < nritems; i++) { 38275f39d397SChris Mason u32 ioff; 3828db94535dSChris Mason 3829dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 3830cc4c13d5SDavid Sterba ioff = btrfs_token_item_offset(&token, item); 3831cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, 3832cc4c13d5SDavid Sterba ioff - total_data); 38330783fcfcSChris Mason } 3834be0e5c09SChris Mason /* shift the items */ 38359c58309dSChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr), 38365f39d397SChris Mason btrfs_item_nr_offset(slot), 38370783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 3838be0e5c09SChris Mason 3839be0e5c09SChris Mason /* shift the data */ 38403d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 38413d9ec8c4SNikolay Borisov data_end - total_data, BTRFS_LEAF_DATA_OFFSET + 3842be0e5c09SChris Mason data_end, old_data - data_end); 3843be0e5c09SChris Mason data_end = old_data; 3844be0e5c09SChris Mason } 38455f39d397SChris Mason 384662e2749eSChris Mason /* setup the item for the new data */ 38479c58309dSChris Mason for (i = 0; i < nr; i++) { 38489c58309dSChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key + i); 38499c58309dSChris Mason btrfs_set_item_key(leaf, &disk_key, slot + i); 3850dd3cc16bSRoss Kirk item = btrfs_item_nr(slot + i); 38519c58309dSChris Mason data_end -= data_size[i]; 3852fc0716c2SNikolay Borisov btrfs_set_token_item_offset(&token, item, data_end); 3853cc4c13d5SDavid Sterba btrfs_set_token_item_size(&token, item, data_size[i]); 38549c58309dSChris Mason } 385544871b1bSChris Mason 38569c58309dSChris Mason btrfs_set_header_nritems(leaf, nritems + nr); 3857b9473439SChris Mason btrfs_mark_buffer_dirty(leaf); 3858aa5d6bedSChris Mason 3859e902baacSDavid Sterba if (btrfs_leaf_free_space(leaf) < 0) { 3860a4f78750SDavid Sterba btrfs_print_leaf(leaf); 3861be0e5c09SChris Mason BUG(); 38625f39d397SChris Mason } 386344871b1bSChris Mason } 386444871b1bSChris Mason 386544871b1bSChris Mason /* 386644871b1bSChris Mason * Given a key and some data, insert items into the tree. 386744871b1bSChris Mason * This does all the path init required, making room in the tree if needed. 386844871b1bSChris Mason */ 386944871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans, 387044871b1bSChris Mason struct btrfs_root *root, 387144871b1bSChris Mason struct btrfs_path *path, 3872310712b2SOmar Sandoval const struct btrfs_key *cpu_key, u32 *data_size, 387344871b1bSChris Mason int nr) 387444871b1bSChris Mason { 387544871b1bSChris Mason int ret = 0; 387644871b1bSChris Mason int slot; 387744871b1bSChris Mason int i; 387844871b1bSChris Mason u32 total_size = 0; 387944871b1bSChris Mason u32 total_data = 0; 388044871b1bSChris Mason 388144871b1bSChris Mason for (i = 0; i < nr; i++) 388244871b1bSChris Mason total_data += data_size[i]; 388344871b1bSChris Mason 388444871b1bSChris Mason total_size = total_data + (nr * sizeof(struct btrfs_item)); 388544871b1bSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1); 388644871b1bSChris Mason if (ret == 0) 388744871b1bSChris Mason return -EEXIST; 388844871b1bSChris Mason if (ret < 0) 3889143bede5SJeff Mahoney return ret; 389044871b1bSChris Mason 389144871b1bSChris Mason slot = path->slots[0]; 389244871b1bSChris Mason BUG_ON(slot < 0); 389344871b1bSChris Mason 3894fc0d82e1SNikolay Borisov setup_items_for_insert(root, path, cpu_key, data_size, nr); 3895143bede5SJeff Mahoney return 0; 389662e2749eSChris Mason } 389762e2749eSChris Mason 389862e2749eSChris Mason /* 389962e2749eSChris Mason * Given a key and some data, insert an item into the tree. 390062e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 390162e2749eSChris Mason */ 3902310712b2SOmar Sandoval int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 3903310712b2SOmar Sandoval const struct btrfs_key *cpu_key, void *data, 3904310712b2SOmar Sandoval u32 data_size) 390562e2749eSChris Mason { 390662e2749eSChris Mason int ret = 0; 39072c90e5d6SChris Mason struct btrfs_path *path; 39085f39d397SChris Mason struct extent_buffer *leaf; 39095f39d397SChris Mason unsigned long ptr; 391062e2749eSChris Mason 39112c90e5d6SChris Mason path = btrfs_alloc_path(); 3912db5b493aSTsutomu Itoh if (!path) 3913db5b493aSTsutomu Itoh return -ENOMEM; 39142c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 391562e2749eSChris Mason if (!ret) { 39165f39d397SChris Mason leaf = path->nodes[0]; 39175f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 39185f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 39195f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 392062e2749eSChris Mason } 39212c90e5d6SChris Mason btrfs_free_path(path); 3922aa5d6bedSChris Mason return ret; 3923be0e5c09SChris Mason } 3924be0e5c09SChris Mason 392574123bd7SChris Mason /* 39265de08d7dSChris Mason * delete the pointer from a given node. 392774123bd7SChris Mason * 3928d352ac68SChris Mason * the tree should have been previously balanced so the deletion does not 3929d352ac68SChris Mason * empty a node. 393074123bd7SChris Mason */ 3931afe5fea7STsutomu Itoh static void del_ptr(struct btrfs_root *root, struct btrfs_path *path, 3932afe5fea7STsutomu Itoh int level, int slot) 3933be0e5c09SChris Mason { 39345f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 39357518a238SChris Mason u32 nritems; 3936f3ea38daSJan Schmidt int ret; 3937be0e5c09SChris Mason 39385f39d397SChris Mason nritems = btrfs_header_nritems(parent); 3939be0e5c09SChris Mason if (slot != nritems - 1) { 3940bf1d3425SDavid Sterba if (level) { 3941f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_move(parent, slot, 3942f3a84ccdSFilipe Manana slot + 1, nritems - slot - 1); 3943bf1d3425SDavid Sterba BUG_ON(ret < 0); 3944bf1d3425SDavid Sterba } 39455f39d397SChris Mason memmove_extent_buffer(parent, 39465f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 39475f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 3948d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 3949d6025579SChris Mason (nritems - slot - 1)); 395057ba86c0SChris Mason } else if (level) { 3951f3a84ccdSFilipe Manana ret = btrfs_tree_mod_log_insert_key(parent, slot, 3952f3a84ccdSFilipe Manana BTRFS_MOD_LOG_KEY_REMOVE, GFP_NOFS); 395357ba86c0SChris Mason BUG_ON(ret < 0); 3954be0e5c09SChris Mason } 3955f3ea38daSJan Schmidt 39567518a238SChris Mason nritems--; 39575f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 39587518a238SChris Mason if (nritems == 0 && parent == root->node) { 39595f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 3960eb60ceacSChris Mason /* just turn the root into a leaf and break */ 39615f39d397SChris Mason btrfs_set_header_level(root->node, 0); 3962bb803951SChris Mason } else if (slot == 0) { 39635f39d397SChris Mason struct btrfs_disk_key disk_key; 39645f39d397SChris Mason 39655f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 3966b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, level + 1); 3967be0e5c09SChris Mason } 3968d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 3969be0e5c09SChris Mason } 3970be0e5c09SChris Mason 397174123bd7SChris Mason /* 3972323ac95bSChris Mason * a helper function to delete the leaf pointed to by path->slots[1] and 39735d4f98a2SYan Zheng * path->nodes[1]. 3974323ac95bSChris Mason * 3975323ac95bSChris Mason * This deletes the pointer in path->nodes[1] and frees the leaf 3976323ac95bSChris Mason * block extent. zero is returned if it all worked out, < 0 otherwise. 3977323ac95bSChris Mason * 3978323ac95bSChris Mason * The path must have already been setup for deleting the leaf, including 3979323ac95bSChris Mason * all the proper balancing. path->nodes[1] must be locked. 3980323ac95bSChris Mason */ 3981143bede5SJeff Mahoney static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans, 3982323ac95bSChris Mason struct btrfs_root *root, 39835d4f98a2SYan Zheng struct btrfs_path *path, 39845d4f98a2SYan Zheng struct extent_buffer *leaf) 3985323ac95bSChris Mason { 39865d4f98a2SYan Zheng WARN_ON(btrfs_header_generation(leaf) != trans->transid); 3987afe5fea7STsutomu Itoh del_ptr(root, path, 1, path->slots[1]); 3988323ac95bSChris Mason 39894d081c41SChris Mason /* 39904d081c41SChris Mason * btrfs_free_extent is expensive, we want to make sure we 39914d081c41SChris Mason * aren't holding any locks when we call it 39924d081c41SChris Mason */ 39934d081c41SChris Mason btrfs_unlock_up_safe(path, 0); 39944d081c41SChris Mason 3995f0486c68SYan, Zheng root_sub_used(root, leaf->len); 3996f0486c68SYan, Zheng 399767439dadSDavid Sterba atomic_inc(&leaf->refs); 39985581a51aSJan Schmidt btrfs_free_tree_block(trans, root, leaf, 0, 1); 39993083ee2eSJosef Bacik free_extent_buffer_stale(leaf); 4000323ac95bSChris Mason } 4001323ac95bSChris Mason /* 400274123bd7SChris Mason * delete the item at the leaf level in path. If that empties 400374123bd7SChris Mason * the leaf, remove it from the tree 400474123bd7SChris Mason */ 400585e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, 400685e21bacSChris Mason struct btrfs_path *path, int slot, int nr) 4007be0e5c09SChris Mason { 40080b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 40095f39d397SChris Mason struct extent_buffer *leaf; 40105f39d397SChris Mason struct btrfs_item *item; 4011ce0eac2aSAlexandru Moise u32 last_off; 4012ce0eac2aSAlexandru Moise u32 dsize = 0; 4013aa5d6bedSChris Mason int ret = 0; 4014aa5d6bedSChris Mason int wret; 401585e21bacSChris Mason int i; 40167518a238SChris Mason u32 nritems; 4017be0e5c09SChris Mason 40185f39d397SChris Mason leaf = path->nodes[0]; 401985e21bacSChris Mason last_off = btrfs_item_offset_nr(leaf, slot + nr - 1); 402085e21bacSChris Mason 402185e21bacSChris Mason for (i = 0; i < nr; i++) 402285e21bacSChris Mason dsize += btrfs_item_size_nr(leaf, slot + i); 402385e21bacSChris Mason 40245f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 4025be0e5c09SChris Mason 402685e21bacSChris Mason if (slot + nr != nritems) { 40278f881e8cSDavid Sterba int data_end = leaf_data_end(leaf); 4028c82f823cSDavid Sterba struct btrfs_map_token token; 40295f39d397SChris Mason 40303d9ec8c4SNikolay Borisov memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET + 4031d6025579SChris Mason data_end + dsize, 40323d9ec8c4SNikolay Borisov BTRFS_LEAF_DATA_OFFSET + data_end, 403385e21bacSChris Mason last_off - data_end); 40345f39d397SChris Mason 4035c82f823cSDavid Sterba btrfs_init_map_token(&token, leaf); 403685e21bacSChris Mason for (i = slot + nr; i < nritems; i++) { 40375f39d397SChris Mason u32 ioff; 4038db94535dSChris Mason 4039dd3cc16bSRoss Kirk item = btrfs_item_nr(i); 4040cc4c13d5SDavid Sterba ioff = btrfs_token_item_offset(&token, item); 4041cc4c13d5SDavid Sterba btrfs_set_token_item_offset(&token, item, ioff + dsize); 40420783fcfcSChris Mason } 4043db94535dSChris Mason 40445f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 404585e21bacSChris Mason btrfs_item_nr_offset(slot + nr), 40460783fcfcSChris Mason sizeof(struct btrfs_item) * 404785e21bacSChris Mason (nritems - slot - nr)); 4048be0e5c09SChris Mason } 404985e21bacSChris Mason btrfs_set_header_nritems(leaf, nritems - nr); 405085e21bacSChris Mason nritems -= nr; 40515f39d397SChris Mason 405274123bd7SChris Mason /* delete the leaf if we've emptied it */ 40537518a238SChris Mason if (nritems == 0) { 40545f39d397SChris Mason if (leaf == root->node) { 40555f39d397SChris Mason btrfs_set_header_level(leaf, 0); 40569a8dd150SChris Mason } else { 40576a884d7dSDavid Sterba btrfs_clean_tree_block(leaf); 4058143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 40599a8dd150SChris Mason } 4060be0e5c09SChris Mason } else { 40617518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 4062aa5d6bedSChris Mason if (slot == 0) { 40635f39d397SChris Mason struct btrfs_disk_key disk_key; 40645f39d397SChris Mason 40655f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 4066b167fa91SNikolay Borisov fixup_low_keys(path, &disk_key, 1); 4067aa5d6bedSChris Mason } 4068aa5d6bedSChris Mason 406974123bd7SChris Mason /* delete the leaf if it is mostly empty */ 40700b246afaSJeff Mahoney if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) { 4071be0e5c09SChris Mason /* push_leaf_left fixes the path. 4072be0e5c09SChris Mason * make sure the path still points to our leaf 4073be0e5c09SChris Mason * for possible call to del_ptr below 4074be0e5c09SChris Mason */ 40754920c9acSChris Mason slot = path->slots[1]; 407667439dadSDavid Sterba atomic_inc(&leaf->refs); 40775f39d397SChris Mason 407899d8f83cSChris Mason wret = push_leaf_left(trans, root, path, 1, 1, 407999d8f83cSChris Mason 1, (u32)-1); 408054aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 4081aa5d6bedSChris Mason ret = wret; 40825f39d397SChris Mason 40835f39d397SChris Mason if (path->nodes[0] == leaf && 40845f39d397SChris Mason btrfs_header_nritems(leaf)) { 408599d8f83cSChris Mason wret = push_leaf_right(trans, root, path, 1, 408699d8f83cSChris Mason 1, 1, 0); 408754aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 4088aa5d6bedSChris Mason ret = wret; 4089aa5d6bedSChris Mason } 40905f39d397SChris Mason 40915f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 4092323ac95bSChris Mason path->slots[1] = slot; 4093143bede5SJeff Mahoney btrfs_del_leaf(trans, root, path, leaf); 40945f39d397SChris Mason free_extent_buffer(leaf); 4095143bede5SJeff Mahoney ret = 0; 40965de08d7dSChris Mason } else { 4097925baeddSChris Mason /* if we're still in the path, make sure 4098925baeddSChris Mason * we're dirty. Otherwise, one of the 4099925baeddSChris Mason * push_leaf functions must have already 4100925baeddSChris Mason * dirtied this buffer 4101925baeddSChris Mason */ 4102925baeddSChris Mason if (path->nodes[0] == leaf) 41035f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 41045f39d397SChris Mason free_extent_buffer(leaf); 4105be0e5c09SChris Mason } 4106d5719762SChris Mason } else { 41075f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 4108be0e5c09SChris Mason } 41099a8dd150SChris Mason } 4110aa5d6bedSChris Mason return ret; 41119a8dd150SChris Mason } 41129a8dd150SChris Mason 411397571fd0SChris Mason /* 4114925baeddSChris Mason * search the tree again to find a leaf with lesser keys 41157bb86316SChris Mason * returns 0 if it found something or 1 if there are no lesser leaves. 41167bb86316SChris Mason * returns < 0 on io errors. 4117d352ac68SChris Mason * 4118d352ac68SChris Mason * This may release the path, and so you may lose any locks held at the 4119d352ac68SChris Mason * time you call it. 41207bb86316SChris Mason */ 412116e7549fSJosef Bacik int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path) 41227bb86316SChris Mason { 4123925baeddSChris Mason struct btrfs_key key; 4124925baeddSChris Mason struct btrfs_disk_key found_key; 4125925baeddSChris Mason int ret; 41267bb86316SChris Mason 4127925baeddSChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, 0); 4128925baeddSChris Mason 4129e8b0d724SFilipe David Borba Manana if (key.offset > 0) { 4130925baeddSChris Mason key.offset--; 4131e8b0d724SFilipe David Borba Manana } else if (key.type > 0) { 4132925baeddSChris Mason key.type--; 4133e8b0d724SFilipe David Borba Manana key.offset = (u64)-1; 4134e8b0d724SFilipe David Borba Manana } else if (key.objectid > 0) { 4135925baeddSChris Mason key.objectid--; 4136e8b0d724SFilipe David Borba Manana key.type = (u8)-1; 4137e8b0d724SFilipe David Borba Manana key.offset = (u64)-1; 4138e8b0d724SFilipe David Borba Manana } else { 41397bb86316SChris Mason return 1; 4140e8b0d724SFilipe David Borba Manana } 41417bb86316SChris Mason 4142b3b4aa74SDavid Sterba btrfs_release_path(path); 4143925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4144925baeddSChris Mason if (ret < 0) 4145925baeddSChris Mason return ret; 4146925baeddSChris Mason btrfs_item_key(path->nodes[0], &found_key, 0); 4147925baeddSChris Mason ret = comp_keys(&found_key, &key); 4148337c6f68SFilipe Manana /* 4149337c6f68SFilipe Manana * We might have had an item with the previous key in the tree right 4150337c6f68SFilipe Manana * before we released our path. And after we released our path, that 4151337c6f68SFilipe Manana * item might have been pushed to the first slot (0) of the leaf we 4152337c6f68SFilipe Manana * were holding due to a tree balance. Alternatively, an item with the 4153337c6f68SFilipe Manana * previous key can exist as the only element of a leaf (big fat item). 4154337c6f68SFilipe Manana * Therefore account for these 2 cases, so that our callers (like 4155337c6f68SFilipe Manana * btrfs_previous_item) don't miss an existing item with a key matching 4156337c6f68SFilipe Manana * the previous key we computed above. 4157337c6f68SFilipe Manana */ 4158337c6f68SFilipe Manana if (ret <= 0) 41597bb86316SChris Mason return 0; 4160925baeddSChris Mason return 1; 41617bb86316SChris Mason } 41627bb86316SChris Mason 41633f157a2fSChris Mason /* 41643f157a2fSChris Mason * A helper function to walk down the tree starting at min_key, and looking 4165de78b51aSEric Sandeen * for nodes or leaves that are have a minimum transaction id. 4166de78b51aSEric Sandeen * This is used by the btree defrag code, and tree logging 41673f157a2fSChris Mason * 41683f157a2fSChris Mason * This does not cow, but it does stuff the starting key it finds back 41693f157a2fSChris Mason * into min_key, so you can call btrfs_search_slot with cow=1 on the 41703f157a2fSChris Mason * key and get a writable path. 41713f157a2fSChris Mason * 41723f157a2fSChris Mason * This honors path->lowest_level to prevent descent past a given level 41733f157a2fSChris Mason * of the tree. 41743f157a2fSChris Mason * 4175d352ac68SChris Mason * min_trans indicates the oldest transaction that you are interested 4176d352ac68SChris Mason * in walking through. Any nodes or leaves older than min_trans are 4177d352ac68SChris Mason * skipped over (without reading them). 4178d352ac68SChris Mason * 41793f157a2fSChris Mason * returns zero if something useful was found, < 0 on error and 1 if there 41803f157a2fSChris Mason * was nothing in the tree that matched the search criteria. 41813f157a2fSChris Mason */ 41823f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, 4183de78b51aSEric Sandeen struct btrfs_path *path, 41843f157a2fSChris Mason u64 min_trans) 41853f157a2fSChris Mason { 41863f157a2fSChris Mason struct extent_buffer *cur; 41873f157a2fSChris Mason struct btrfs_key found_key; 41883f157a2fSChris Mason int slot; 41899652480bSYan int sret; 41903f157a2fSChris Mason u32 nritems; 41913f157a2fSChris Mason int level; 41923f157a2fSChris Mason int ret = 1; 4193f98de9b9SFilipe Manana int keep_locks = path->keep_locks; 41943f157a2fSChris Mason 4195f98de9b9SFilipe Manana path->keep_locks = 1; 41963f157a2fSChris Mason again: 4197bd681513SChris Mason cur = btrfs_read_lock_root_node(root); 41983f157a2fSChris Mason level = btrfs_header_level(cur); 4199e02119d5SChris Mason WARN_ON(path->nodes[level]); 42003f157a2fSChris Mason path->nodes[level] = cur; 4201bd681513SChris Mason path->locks[level] = BTRFS_READ_LOCK; 42023f157a2fSChris Mason 42033f157a2fSChris Mason if (btrfs_header_generation(cur) < min_trans) { 42043f157a2fSChris Mason ret = 1; 42053f157a2fSChris Mason goto out; 42063f157a2fSChris Mason } 42073f157a2fSChris Mason while (1) { 42083f157a2fSChris Mason nritems = btrfs_header_nritems(cur); 42093f157a2fSChris Mason level = btrfs_header_level(cur); 4210e3b83361SQu Wenruo sret = btrfs_bin_search(cur, min_key, &slot); 4211cbca7d59SFilipe Manana if (sret < 0) { 4212cbca7d59SFilipe Manana ret = sret; 4213cbca7d59SFilipe Manana goto out; 4214cbca7d59SFilipe Manana } 42153f157a2fSChris Mason 4216323ac95bSChris Mason /* at the lowest level, we're done, setup the path and exit */ 4217323ac95bSChris Mason if (level == path->lowest_level) { 4218e02119d5SChris Mason if (slot >= nritems) 4219e02119d5SChris Mason goto find_next_key; 42203f157a2fSChris Mason ret = 0; 42213f157a2fSChris Mason path->slots[level] = slot; 42223f157a2fSChris Mason btrfs_item_key_to_cpu(cur, &found_key, slot); 42233f157a2fSChris Mason goto out; 42243f157a2fSChris Mason } 42259652480bSYan if (sret && slot > 0) 42269652480bSYan slot--; 42273f157a2fSChris Mason /* 4228de78b51aSEric Sandeen * check this node pointer against the min_trans parameters. 4229260db43cSRandy Dunlap * If it is too old, skip to the next one. 42303f157a2fSChris Mason */ 42313f157a2fSChris Mason while (slot < nritems) { 42323f157a2fSChris Mason u64 gen; 4233e02119d5SChris Mason 42343f157a2fSChris Mason gen = btrfs_node_ptr_generation(cur, slot); 42353f157a2fSChris Mason if (gen < min_trans) { 42363f157a2fSChris Mason slot++; 42373f157a2fSChris Mason continue; 42383f157a2fSChris Mason } 42393f157a2fSChris Mason break; 42403f157a2fSChris Mason } 4241e02119d5SChris Mason find_next_key: 42423f157a2fSChris Mason /* 42433f157a2fSChris Mason * we didn't find a candidate key in this node, walk forward 42443f157a2fSChris Mason * and find another one 42453f157a2fSChris Mason */ 42463f157a2fSChris Mason if (slot >= nritems) { 4247e02119d5SChris Mason path->slots[level] = slot; 4248e02119d5SChris Mason sret = btrfs_find_next_key(root, path, min_key, level, 4249de78b51aSEric Sandeen min_trans); 4250e02119d5SChris Mason if (sret == 0) { 4251b3b4aa74SDavid Sterba btrfs_release_path(path); 42523f157a2fSChris Mason goto again; 42533f157a2fSChris Mason } else { 42543f157a2fSChris Mason goto out; 42553f157a2fSChris Mason } 42563f157a2fSChris Mason } 42573f157a2fSChris Mason /* save our key for returning back */ 42583f157a2fSChris Mason btrfs_node_key_to_cpu(cur, &found_key, slot); 42593f157a2fSChris Mason path->slots[level] = slot; 42603f157a2fSChris Mason if (level == path->lowest_level) { 42613f157a2fSChris Mason ret = 0; 42623f157a2fSChris Mason goto out; 42633f157a2fSChris Mason } 42644b231ae4SDavid Sterba cur = btrfs_read_node_slot(cur, slot); 4265fb770ae4SLiu Bo if (IS_ERR(cur)) { 4266fb770ae4SLiu Bo ret = PTR_ERR(cur); 4267fb770ae4SLiu Bo goto out; 4268fb770ae4SLiu Bo } 42693f157a2fSChris Mason 4270bd681513SChris Mason btrfs_tree_read_lock(cur); 4271b4ce94deSChris Mason 4272bd681513SChris Mason path->locks[level - 1] = BTRFS_READ_LOCK; 42733f157a2fSChris Mason path->nodes[level - 1] = cur; 4274f7c79f30SChris Mason unlock_up(path, level, 1, 0, NULL); 42753f157a2fSChris Mason } 42763f157a2fSChris Mason out: 4277f98de9b9SFilipe Manana path->keep_locks = keep_locks; 4278f98de9b9SFilipe Manana if (ret == 0) { 4279f98de9b9SFilipe Manana btrfs_unlock_up_safe(path, path->lowest_level + 1); 4280f98de9b9SFilipe Manana memcpy(min_key, &found_key, sizeof(found_key)); 4281f98de9b9SFilipe Manana } 42823f157a2fSChris Mason return ret; 42833f157a2fSChris Mason } 42843f157a2fSChris Mason 42853f157a2fSChris Mason /* 42863f157a2fSChris Mason * this is similar to btrfs_next_leaf, but does not try to preserve 42873f157a2fSChris Mason * and fixup the path. It looks for and returns the next key in the 4288de78b51aSEric Sandeen * tree based on the current path and the min_trans parameters. 42893f157a2fSChris Mason * 42903f157a2fSChris Mason * 0 is returned if another key is found, < 0 if there are any errors 42913f157a2fSChris Mason * and 1 is returned if there are no higher keys in the tree 42923f157a2fSChris Mason * 42933f157a2fSChris Mason * path->keep_locks should be set to 1 on the search made before 42943f157a2fSChris Mason * calling this function. 42953f157a2fSChris Mason */ 4296e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path, 4297de78b51aSEric Sandeen struct btrfs_key *key, int level, u64 min_trans) 4298e7a84565SChris Mason { 4299e7a84565SChris Mason int slot; 4300e7a84565SChris Mason struct extent_buffer *c; 4301e7a84565SChris Mason 43026a9fb468SJosef Bacik WARN_ON(!path->keep_locks && !path->skip_locking); 4303e7a84565SChris Mason while (level < BTRFS_MAX_LEVEL) { 4304e7a84565SChris Mason if (!path->nodes[level]) 4305e7a84565SChris Mason return 1; 4306e7a84565SChris Mason 4307e7a84565SChris Mason slot = path->slots[level] + 1; 4308e7a84565SChris Mason c = path->nodes[level]; 43093f157a2fSChris Mason next: 4310e7a84565SChris Mason if (slot >= btrfs_header_nritems(c)) { 431133c66f43SYan Zheng int ret; 431233c66f43SYan Zheng int orig_lowest; 431333c66f43SYan Zheng struct btrfs_key cur_key; 431433c66f43SYan Zheng if (level + 1 >= BTRFS_MAX_LEVEL || 431533c66f43SYan Zheng !path->nodes[level + 1]) 4316e7a84565SChris Mason return 1; 431733c66f43SYan Zheng 43186a9fb468SJosef Bacik if (path->locks[level + 1] || path->skip_locking) { 431933c66f43SYan Zheng level++; 4320e7a84565SChris Mason continue; 4321e7a84565SChris Mason } 432233c66f43SYan Zheng 432333c66f43SYan Zheng slot = btrfs_header_nritems(c) - 1; 432433c66f43SYan Zheng if (level == 0) 432533c66f43SYan Zheng btrfs_item_key_to_cpu(c, &cur_key, slot); 432633c66f43SYan Zheng else 432733c66f43SYan Zheng btrfs_node_key_to_cpu(c, &cur_key, slot); 432833c66f43SYan Zheng 432933c66f43SYan Zheng orig_lowest = path->lowest_level; 4330b3b4aa74SDavid Sterba btrfs_release_path(path); 433133c66f43SYan Zheng path->lowest_level = level; 433233c66f43SYan Zheng ret = btrfs_search_slot(NULL, root, &cur_key, path, 433333c66f43SYan Zheng 0, 0); 433433c66f43SYan Zheng path->lowest_level = orig_lowest; 433533c66f43SYan Zheng if (ret < 0) 433633c66f43SYan Zheng return ret; 433733c66f43SYan Zheng 433833c66f43SYan Zheng c = path->nodes[level]; 433933c66f43SYan Zheng slot = path->slots[level]; 434033c66f43SYan Zheng if (ret == 0) 434133c66f43SYan Zheng slot++; 434233c66f43SYan Zheng goto next; 434333c66f43SYan Zheng } 434433c66f43SYan Zheng 4345e7a84565SChris Mason if (level == 0) 4346e7a84565SChris Mason btrfs_item_key_to_cpu(c, key, slot); 43473f157a2fSChris Mason else { 43483f157a2fSChris Mason u64 gen = btrfs_node_ptr_generation(c, slot); 43493f157a2fSChris Mason 43503f157a2fSChris Mason if (gen < min_trans) { 43513f157a2fSChris Mason slot++; 43523f157a2fSChris Mason goto next; 43533f157a2fSChris Mason } 4354e7a84565SChris Mason btrfs_node_key_to_cpu(c, key, slot); 43553f157a2fSChris Mason } 4356e7a84565SChris Mason return 0; 4357e7a84565SChris Mason } 4358e7a84565SChris Mason return 1; 4359e7a84565SChris Mason } 4360e7a84565SChris Mason 43617bb86316SChris Mason /* 4362925baeddSChris Mason * search the tree again to find a leaf with greater keys 43630f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 43640f70abe2SChris Mason * returns < 0 on io errors. 436597571fd0SChris Mason */ 4366234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 4367d97e63b6SChris Mason { 43683d7806ecSJan Schmidt return btrfs_next_old_leaf(root, path, 0); 43693d7806ecSJan Schmidt } 43703d7806ecSJan Schmidt 43713d7806ecSJan Schmidt int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path, 43723d7806ecSJan Schmidt u64 time_seq) 43733d7806ecSJan Schmidt { 4374d97e63b6SChris Mason int slot; 43758e73f275SChris Mason int level; 43765f39d397SChris Mason struct extent_buffer *c; 43778e73f275SChris Mason struct extent_buffer *next; 4378925baeddSChris Mason struct btrfs_key key; 4379925baeddSChris Mason u32 nritems; 4380925baeddSChris Mason int ret; 43810e46318dSJosef Bacik int i; 4382925baeddSChris Mason 4383925baeddSChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4384d397712bSChris Mason if (nritems == 0) 4385925baeddSChris Mason return 1; 4386925baeddSChris Mason 43878e73f275SChris Mason btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1); 43888e73f275SChris Mason again: 43898e73f275SChris Mason level = 1; 43908e73f275SChris Mason next = NULL; 4391b3b4aa74SDavid Sterba btrfs_release_path(path); 43928e73f275SChris Mason 4393a2135011SChris Mason path->keep_locks = 1; 43948e73f275SChris Mason 43953d7806ecSJan Schmidt if (time_seq) 43963d7806ecSJan Schmidt ret = btrfs_search_old_slot(root, &key, path, time_seq); 43973d7806ecSJan Schmidt else 4398925baeddSChris Mason ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 4399925baeddSChris Mason path->keep_locks = 0; 4400925baeddSChris Mason 4401925baeddSChris Mason if (ret < 0) 4402925baeddSChris Mason return ret; 4403925baeddSChris Mason 4404a2135011SChris Mason nritems = btrfs_header_nritems(path->nodes[0]); 4405168fd7d2SChris Mason /* 4406168fd7d2SChris Mason * by releasing the path above we dropped all our locks. A balance 4407168fd7d2SChris Mason * could have added more items next to the key that used to be 4408168fd7d2SChris Mason * at the very end of the block. So, check again here and 4409168fd7d2SChris Mason * advance the path if there are now more items available. 4410168fd7d2SChris Mason */ 4411a2135011SChris Mason if (nritems > 0 && path->slots[0] < nritems - 1) { 4412e457afecSYan Zheng if (ret == 0) 4413168fd7d2SChris Mason path->slots[0]++; 44148e73f275SChris Mason ret = 0; 4415925baeddSChris Mason goto done; 4416925baeddSChris Mason } 44170b43e04fSLiu Bo /* 44180b43e04fSLiu Bo * So the above check misses one case: 44190b43e04fSLiu Bo * - after releasing the path above, someone has removed the item that 44200b43e04fSLiu Bo * used to be at the very end of the block, and balance between leafs 44210b43e04fSLiu Bo * gets another one with bigger key.offset to replace it. 44220b43e04fSLiu Bo * 44230b43e04fSLiu Bo * This one should be returned as well, or we can get leaf corruption 44240b43e04fSLiu Bo * later(esp. in __btrfs_drop_extents()). 44250b43e04fSLiu Bo * 44260b43e04fSLiu Bo * And a bit more explanation about this check, 44270b43e04fSLiu Bo * with ret > 0, the key isn't found, the path points to the slot 44280b43e04fSLiu Bo * where it should be inserted, so the path->slots[0] item must be the 44290b43e04fSLiu Bo * bigger one. 44300b43e04fSLiu Bo */ 44310b43e04fSLiu Bo if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) { 44320b43e04fSLiu Bo ret = 0; 44330b43e04fSLiu Bo goto done; 44340b43e04fSLiu Bo } 4435d97e63b6SChris Mason 4436234b63a0SChris Mason while (level < BTRFS_MAX_LEVEL) { 44378e73f275SChris Mason if (!path->nodes[level]) { 44388e73f275SChris Mason ret = 1; 44398e73f275SChris Mason goto done; 44408e73f275SChris Mason } 44415f39d397SChris Mason 4442d97e63b6SChris Mason slot = path->slots[level] + 1; 4443d97e63b6SChris Mason c = path->nodes[level]; 44445f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 4445d97e63b6SChris Mason level++; 44468e73f275SChris Mason if (level == BTRFS_MAX_LEVEL) { 44478e73f275SChris Mason ret = 1; 44488e73f275SChris Mason goto done; 44498e73f275SChris Mason } 4450d97e63b6SChris Mason continue; 4451d97e63b6SChris Mason } 44525f39d397SChris Mason 44530e46318dSJosef Bacik 44540e46318dSJosef Bacik /* 44550e46318dSJosef Bacik * Our current level is where we're going to start from, and to 44560e46318dSJosef Bacik * make sure lockdep doesn't complain we need to drop our locks 44570e46318dSJosef Bacik * and nodes from 0 to our current level. 44580e46318dSJosef Bacik */ 44590e46318dSJosef Bacik for (i = 0; i < level; i++) { 44600e46318dSJosef Bacik if (path->locks[level]) { 44610e46318dSJosef Bacik btrfs_tree_read_unlock(path->nodes[i]); 44620e46318dSJosef Bacik path->locks[i] = 0; 44630e46318dSJosef Bacik } 44640e46318dSJosef Bacik free_extent_buffer(path->nodes[i]); 44650e46318dSJosef Bacik path->nodes[i] = NULL; 4466925baeddSChris Mason } 44675f39d397SChris Mason 44688e73f275SChris Mason next = c; 4469d07b8528SLiu Bo ret = read_block_for_search(root, path, &next, level, 4470cda79c54SDavid Sterba slot, &key); 44718e73f275SChris Mason if (ret == -EAGAIN) 44728e73f275SChris Mason goto again; 44735f39d397SChris Mason 447476a05b35SChris Mason if (ret < 0) { 4475b3b4aa74SDavid Sterba btrfs_release_path(path); 447676a05b35SChris Mason goto done; 447776a05b35SChris Mason } 447876a05b35SChris Mason 44795cd57b2cSChris Mason if (!path->skip_locking) { 4480bd681513SChris Mason ret = btrfs_try_tree_read_lock(next); 4481d42244a0SJan Schmidt if (!ret && time_seq) { 4482d42244a0SJan Schmidt /* 4483d42244a0SJan Schmidt * If we don't get the lock, we may be racing 4484d42244a0SJan Schmidt * with push_leaf_left, holding that lock while 4485d42244a0SJan Schmidt * itself waiting for the leaf we've currently 4486d42244a0SJan Schmidt * locked. To solve this situation, we give up 4487d42244a0SJan Schmidt * on our lock and cycle. 4488d42244a0SJan Schmidt */ 4489cf538830SJan Schmidt free_extent_buffer(next); 4490d42244a0SJan Schmidt btrfs_release_path(path); 4491d42244a0SJan Schmidt cond_resched(); 4492d42244a0SJan Schmidt goto again; 4493d42244a0SJan Schmidt } 44940e46318dSJosef Bacik if (!ret) 44950e46318dSJosef Bacik btrfs_tree_read_lock(next); 4496bd681513SChris Mason } 4497d97e63b6SChris Mason break; 4498d97e63b6SChris Mason } 4499d97e63b6SChris Mason path->slots[level] = slot; 4500d97e63b6SChris Mason while (1) { 4501d97e63b6SChris Mason level--; 4502d97e63b6SChris Mason path->nodes[level] = next; 4503d97e63b6SChris Mason path->slots[level] = 0; 4504a74a4b97SChris Mason if (!path->skip_locking) 4505ffeb03cfSJosef Bacik path->locks[level] = BTRFS_READ_LOCK; 4506d97e63b6SChris Mason if (!level) 4507d97e63b6SChris Mason break; 4508b4ce94deSChris Mason 4509d07b8528SLiu Bo ret = read_block_for_search(root, path, &next, level, 4510cda79c54SDavid Sterba 0, &key); 45118e73f275SChris Mason if (ret == -EAGAIN) 45128e73f275SChris Mason goto again; 45138e73f275SChris Mason 451476a05b35SChris Mason if (ret < 0) { 4515b3b4aa74SDavid Sterba btrfs_release_path(path); 451676a05b35SChris Mason goto done; 451776a05b35SChris Mason } 451876a05b35SChris Mason 4519ffeb03cfSJosef Bacik if (!path->skip_locking) 45200e46318dSJosef Bacik btrfs_tree_read_lock(next); 4521d97e63b6SChris Mason } 45228e73f275SChris Mason ret = 0; 4523925baeddSChris Mason done: 4524f7c79f30SChris Mason unlock_up(path, 0, 1, 0, NULL); 45258e73f275SChris Mason 45268e73f275SChris Mason return ret; 4527d97e63b6SChris Mason } 45280b86a832SChris Mason 45293f157a2fSChris Mason /* 45303f157a2fSChris Mason * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps 45313f157a2fSChris Mason * searching until it gets past min_objectid or finds an item of 'type' 45323f157a2fSChris Mason * 45333f157a2fSChris Mason * returns 0 if something is found, 1 if nothing was found and < 0 on error 45343f157a2fSChris Mason */ 45350b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root, 45360b86a832SChris Mason struct btrfs_path *path, u64 min_objectid, 45370b86a832SChris Mason int type) 45380b86a832SChris Mason { 45390b86a832SChris Mason struct btrfs_key found_key; 45400b86a832SChris Mason struct extent_buffer *leaf; 4541e02119d5SChris Mason u32 nritems; 45420b86a832SChris Mason int ret; 45430b86a832SChris Mason 45440b86a832SChris Mason while (1) { 45450b86a832SChris Mason if (path->slots[0] == 0) { 45460b86a832SChris Mason ret = btrfs_prev_leaf(root, path); 45470b86a832SChris Mason if (ret != 0) 45480b86a832SChris Mason return ret; 45490b86a832SChris Mason } else { 45500b86a832SChris Mason path->slots[0]--; 45510b86a832SChris Mason } 45520b86a832SChris Mason leaf = path->nodes[0]; 4553e02119d5SChris Mason nritems = btrfs_header_nritems(leaf); 4554e02119d5SChris Mason if (nritems == 0) 4555e02119d5SChris Mason return 1; 4556e02119d5SChris Mason if (path->slots[0] == nritems) 4557e02119d5SChris Mason path->slots[0]--; 4558e02119d5SChris Mason 45590b86a832SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4560e02119d5SChris Mason if (found_key.objectid < min_objectid) 4561e02119d5SChris Mason break; 45620a4eefbbSYan Zheng if (found_key.type == type) 45630a4eefbbSYan Zheng return 0; 4564e02119d5SChris Mason if (found_key.objectid == min_objectid && 4565e02119d5SChris Mason found_key.type < type) 4566e02119d5SChris Mason break; 45670b86a832SChris Mason } 45680b86a832SChris Mason return 1; 45690b86a832SChris Mason } 4570ade2e0b3SWang Shilong 4571ade2e0b3SWang Shilong /* 4572ade2e0b3SWang Shilong * search in extent tree to find a previous Metadata/Data extent item with 4573ade2e0b3SWang Shilong * min objecitd. 4574ade2e0b3SWang Shilong * 4575ade2e0b3SWang Shilong * returns 0 if something is found, 1 if nothing was found and < 0 on error 4576ade2e0b3SWang Shilong */ 4577ade2e0b3SWang Shilong int btrfs_previous_extent_item(struct btrfs_root *root, 4578ade2e0b3SWang Shilong struct btrfs_path *path, u64 min_objectid) 4579ade2e0b3SWang Shilong { 4580ade2e0b3SWang Shilong struct btrfs_key found_key; 4581ade2e0b3SWang Shilong struct extent_buffer *leaf; 4582ade2e0b3SWang Shilong u32 nritems; 4583ade2e0b3SWang Shilong int ret; 4584ade2e0b3SWang Shilong 4585ade2e0b3SWang Shilong while (1) { 4586ade2e0b3SWang Shilong if (path->slots[0] == 0) { 4587ade2e0b3SWang Shilong ret = btrfs_prev_leaf(root, path); 4588ade2e0b3SWang Shilong if (ret != 0) 4589ade2e0b3SWang Shilong return ret; 4590ade2e0b3SWang Shilong } else { 4591ade2e0b3SWang Shilong path->slots[0]--; 4592ade2e0b3SWang Shilong } 4593ade2e0b3SWang Shilong leaf = path->nodes[0]; 4594ade2e0b3SWang Shilong nritems = btrfs_header_nritems(leaf); 4595ade2e0b3SWang Shilong if (nritems == 0) 4596ade2e0b3SWang Shilong return 1; 4597ade2e0b3SWang Shilong if (path->slots[0] == nritems) 4598ade2e0b3SWang Shilong path->slots[0]--; 4599ade2e0b3SWang Shilong 4600ade2e0b3SWang Shilong btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 4601ade2e0b3SWang Shilong if (found_key.objectid < min_objectid) 4602ade2e0b3SWang Shilong break; 4603ade2e0b3SWang Shilong if (found_key.type == BTRFS_EXTENT_ITEM_KEY || 4604ade2e0b3SWang Shilong found_key.type == BTRFS_METADATA_ITEM_KEY) 4605ade2e0b3SWang Shilong return 0; 4606ade2e0b3SWang Shilong if (found_key.objectid == min_objectid && 4607ade2e0b3SWang Shilong found_key.type < BTRFS_EXTENT_ITEM_KEY) 4608ade2e0b3SWang Shilong break; 4609ade2e0b3SWang Shilong } 4610ade2e0b3SWang Shilong return 1; 4611ade2e0b3SWang Shilong } 4612