16cbd5570SChris Mason /* 26cbd5570SChris Mason * Copyright (C) 2007 Oracle. All rights reserved. 36cbd5570SChris Mason * 46cbd5570SChris Mason * This program is free software; you can redistribute it and/or 56cbd5570SChris Mason * modify it under the terms of the GNU General Public 66cbd5570SChris Mason * License v2 as published by the Free Software Foundation. 76cbd5570SChris Mason * 86cbd5570SChris Mason * This program is distributed in the hope that it will be useful, 96cbd5570SChris Mason * but WITHOUT ANY WARRANTY; without even the implied warranty of 106cbd5570SChris Mason * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 116cbd5570SChris Mason * General Public License for more details. 126cbd5570SChris Mason * 136cbd5570SChris Mason * You should have received a copy of the GNU General Public 146cbd5570SChris Mason * License along with this program; if not, write to the 156cbd5570SChris Mason * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 166cbd5570SChris Mason * Boston, MA 021110-1307, USA. 176cbd5570SChris Mason */ 186cbd5570SChris Mason 19eb60ceacSChris Mason #include "ctree.h" 20eb60ceacSChris Mason #include "disk-io.h" 217f5c1516SChris Mason #include "transaction.h" 229a8dd150SChris Mason 23e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 24e089f05cSChris Mason *root, struct btrfs_path *path, int level); 25e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 26d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 27d4dbff95SChris Mason struct btrfs_path *path, int data_size); 28e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 29e20d96d6SChris Mason *root, struct buffer_head *dst, struct buffer_head 30e089f05cSChris Mason *src); 31e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 32e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 33e20d96d6SChris Mason struct buffer_head *src_buf); 34e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 35e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 36d97e63b6SChris Mason 37df24a2b9SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 38df24a2b9SChris Mason { 39df24a2b9SChris Mason memset(p, 0, sizeof(*p)); 40df24a2b9SChris Mason } 41df24a2b9SChris Mason 422c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 432c90e5d6SChris Mason { 44df24a2b9SChris Mason struct btrfs_path *path; 45df24a2b9SChris Mason path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS); 462cc58cf2SChris Mason if (path) { 47df24a2b9SChris Mason btrfs_init_path(path); 482cc58cf2SChris Mason path->reada = 1; 492cc58cf2SChris Mason } 50df24a2b9SChris Mason return path; 512c90e5d6SChris Mason } 522c90e5d6SChris Mason 532c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 542c90e5d6SChris Mason { 55df24a2b9SChris Mason btrfs_release_path(NULL, p); 562c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 572c90e5d6SChris Mason } 582c90e5d6SChris Mason 59234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 60eb60ceacSChris Mason { 61eb60ceacSChris Mason int i; 62234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 63eb60ceacSChris Mason if (!p->nodes[i]) 64eb60ceacSChris Mason break; 65234b63a0SChris Mason btrfs_block_release(root, p->nodes[i]); 66eb60ceacSChris Mason } 67aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 68eb60ceacSChris Mason } 69eb60ceacSChris Mason 706702ed49SChris Mason static int __btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 716702ed49SChris Mason *root, struct buffer_head *buf, struct buffer_head 726702ed49SChris Mason *parent, int parent_slot, struct buffer_head 736702ed49SChris Mason **cow_ret, u64 search_start, u64 empty_size) 746702ed49SChris Mason { 756702ed49SChris Mason struct buffer_head *cow; 766702ed49SChris Mason struct btrfs_node *cow_node; 776702ed49SChris Mason int ret = 0; 786702ed49SChris Mason int different_trans = 0; 796702ed49SChris Mason 806702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 816702ed49SChris Mason WARN_ON(!buffer_uptodate(buf)); 826702ed49SChris Mason cow = btrfs_alloc_free_block(trans, root, search_start, empty_size); 836702ed49SChris Mason if (IS_ERR(cow)) 846702ed49SChris Mason return PTR_ERR(cow); 856702ed49SChris Mason 866702ed49SChris Mason cow_node = btrfs_buffer_node(cow); 876702ed49SChris Mason if (buf->b_size != root->blocksize || cow->b_size != root->blocksize) 886702ed49SChris Mason WARN_ON(1); 896702ed49SChris Mason 906702ed49SChris Mason memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize); 916702ed49SChris Mason btrfs_set_header_blocknr(&cow_node->header, bh_blocknr(cow)); 926702ed49SChris Mason btrfs_set_header_generation(&cow_node->header, trans->transid); 936702ed49SChris Mason btrfs_set_header_owner(&cow_node->header, root->root_key.objectid); 946702ed49SChris Mason 956702ed49SChris Mason WARN_ON(btrfs_header_generation(btrfs_buffer_header(buf)) > 966702ed49SChris Mason trans->transid); 976702ed49SChris Mason if (btrfs_header_generation(btrfs_buffer_header(buf)) != 986702ed49SChris Mason trans->transid) { 996702ed49SChris Mason different_trans = 1; 1006702ed49SChris Mason ret = btrfs_inc_ref(trans, root, buf); 1016702ed49SChris Mason if (ret) 1026702ed49SChris Mason return ret; 1036702ed49SChris Mason } else { 1046702ed49SChris Mason clean_tree_block(trans, root, buf); 1056702ed49SChris Mason } 1066702ed49SChris Mason 1076702ed49SChris Mason if (buf == root->node) { 1086702ed49SChris Mason root->node = cow; 1096702ed49SChris Mason get_bh(cow); 1106702ed49SChris Mason if (buf != root->commit_root) { 1116702ed49SChris Mason btrfs_free_extent(trans, root, bh_blocknr(buf), 1, 1); 1126702ed49SChris Mason } 1136702ed49SChris Mason btrfs_block_release(root, buf); 1146702ed49SChris Mason } else { 1156702ed49SChris Mason btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot, 1166702ed49SChris Mason bh_blocknr(cow)); 1176702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 1186702ed49SChris Mason WARN_ON(btrfs_header_generation(btrfs_buffer_header(parent)) != 1196702ed49SChris Mason trans->transid); 1206702ed49SChris Mason btrfs_free_extent(trans, root, bh_blocknr(buf), 1, 1); 1216702ed49SChris Mason } 1226702ed49SChris Mason btrfs_block_release(root, buf); 1236702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 1246702ed49SChris Mason *cow_ret = cow; 1256702ed49SChris Mason return 0; 1266702ed49SChris Mason } 1276702ed49SChris Mason 1286702ed49SChris Mason int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 129e20d96d6SChris Mason *root, struct buffer_head *buf, struct buffer_head 130e20d96d6SChris Mason *parent, int parent_slot, struct buffer_head 131e089f05cSChris Mason **cow_ret) 13202217ed2SChris Mason { 1336702ed49SChris Mason u64 search_start; 134ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 135ccd467d6SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 136ccd467d6SChris Mason root->fs_info->running_transaction->transid); 137ccd467d6SChris Mason WARN_ON(1); 138ccd467d6SChris Mason } 139ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 140ccd467d6SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 141ccd467d6SChris Mason root->fs_info->generation); 142ccd467d6SChris Mason WARN_ON(1); 143ccd467d6SChris Mason } 1447f5c1516SChris Mason if (btrfs_header_generation(btrfs_buffer_header(buf)) == 1457f5c1516SChris Mason trans->transid) { 14602217ed2SChris Mason *cow_ret = buf; 14702217ed2SChris Mason return 0; 14802217ed2SChris Mason } 1496702ed49SChris Mason 1506702ed49SChris Mason search_start = bh_blocknr(buf) & ~((u64)65535); 1516702ed49SChris Mason return __btrfs_cow_block(trans, root, buf, parent, 1526702ed49SChris Mason parent_slot, cow_ret, search_start, 0); 1532c90e5d6SChris Mason } 1546702ed49SChris Mason 1556702ed49SChris Mason static int close_blocks(u64 blocknr, u64 other) 1566702ed49SChris Mason { 1576702ed49SChris Mason if (blocknr < other && other - blocknr < 8) 1586702ed49SChris Mason return 1; 1596702ed49SChris Mason if (blocknr > other && blocknr - other < 8) 1606702ed49SChris Mason return 1; 16102217ed2SChris Mason return 0; 16202217ed2SChris Mason } 16302217ed2SChris Mason 1642cc58cf2SChris Mason static int should_defrag_leaf(struct buffer_head *bh) 1652cc58cf2SChris Mason { 1662cc58cf2SChris Mason struct btrfs_leaf *leaf = btrfs_buffer_leaf(bh); 1672cc58cf2SChris Mason struct btrfs_disk_key *key; 1682cc58cf2SChris Mason u32 nritems; 1692cc58cf2SChris Mason 1702cc58cf2SChris Mason if (buffer_defrag(bh)) 1712cc58cf2SChris Mason return 1; 1722cc58cf2SChris Mason 1732cc58cf2SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1742cc58cf2SChris Mason if (nritems == 0) 1752cc58cf2SChris Mason return 0; 1762cc58cf2SChris Mason 1772cc58cf2SChris Mason key = &leaf->items[0].key; 1782cc58cf2SChris Mason if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY) 1792cc58cf2SChris Mason return 1; 1802cc58cf2SChris Mason 1812cc58cf2SChris Mason key = &leaf->items[nritems-1].key; 1822cc58cf2SChris Mason if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY) 1832cc58cf2SChris Mason return 1; 1842cc58cf2SChris Mason if (nritems > 4) { 1852cc58cf2SChris Mason key = &leaf->items[nritems/2].key; 1862cc58cf2SChris Mason if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY) 1872cc58cf2SChris Mason return 1; 1882cc58cf2SChris Mason } 1892cc58cf2SChris Mason return 0; 1902cc58cf2SChris Mason } 1912cc58cf2SChris Mason 1926702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 1936702ed49SChris Mason struct btrfs_root *root, struct buffer_head *parent, 194e9d0b13bSChris Mason int cache_only, u64 *last_ret) 1956702ed49SChris Mason { 1966702ed49SChris Mason struct btrfs_node *parent_node; 1976702ed49SChris Mason struct buffer_head *cur_bh; 1986702ed49SChris Mason struct buffer_head *tmp_bh; 1996702ed49SChris Mason u64 blocknr; 200e9d0b13bSChris Mason u64 search_start = *last_ret; 201e9d0b13bSChris Mason u64 last_block = 0; 2026702ed49SChris Mason u64 other; 2036702ed49SChris Mason u32 parent_nritems; 2046702ed49SChris Mason int start_slot; 2056702ed49SChris Mason int end_slot; 2066702ed49SChris Mason int i; 2076702ed49SChris Mason int err = 0; 208f2183bdeSChris Mason int parent_level; 2096702ed49SChris Mason 2106702ed49SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 2116702ed49SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 2126702ed49SChris Mason root->fs_info->running_transaction->transid); 2136702ed49SChris Mason WARN_ON(1); 2146702ed49SChris Mason } 2156702ed49SChris Mason if (trans->transid != root->fs_info->generation) { 2166702ed49SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 2176702ed49SChris Mason root->fs_info->generation); 2186702ed49SChris Mason WARN_ON(1); 2196702ed49SChris Mason } 2206702ed49SChris Mason parent_node = btrfs_buffer_node(parent); 2216702ed49SChris Mason parent_nritems = btrfs_header_nritems(&parent_node->header); 222f2183bdeSChris Mason parent_level = btrfs_header_level(&parent_node->header); 2236702ed49SChris Mason 2246702ed49SChris Mason start_slot = 0; 2256702ed49SChris Mason end_slot = parent_nritems; 2266702ed49SChris Mason 2276702ed49SChris Mason if (parent_nritems == 1) 2286702ed49SChris Mason return 0; 2296702ed49SChris Mason 2306702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 2316702ed49SChris Mason int close = 1; 2326702ed49SChris Mason blocknr = btrfs_node_blockptr(parent_node, i); 233e9d0b13bSChris Mason if (last_block == 0) 234e9d0b13bSChris Mason last_block = blocknr; 2356702ed49SChris Mason if (i > 0) { 2366702ed49SChris Mason other = btrfs_node_blockptr(parent_node, i - 1); 2376702ed49SChris Mason close = close_blocks(blocknr, other); 2386702ed49SChris Mason } 2396702ed49SChris Mason if (close && i < end_slot - 1) { 2406702ed49SChris Mason other = btrfs_node_blockptr(parent_node, i + 1); 2416702ed49SChris Mason close = close_blocks(blocknr, other); 2426702ed49SChris Mason } 243e9d0b13bSChris Mason if (close) { 244e9d0b13bSChris Mason last_block = blocknr; 2456702ed49SChris Mason continue; 246e9d0b13bSChris Mason } 2476702ed49SChris Mason 2486702ed49SChris Mason cur_bh = btrfs_find_tree_block(root, blocknr); 2496702ed49SChris Mason if (!cur_bh || !buffer_uptodate(cur_bh) || 2502cc58cf2SChris Mason buffer_locked(cur_bh) || 2512cc58cf2SChris Mason (parent_level != 1 && !buffer_defrag(cur_bh)) || 2522cc58cf2SChris Mason (parent_level == 1 && !should_defrag_leaf(cur_bh))) { 2536702ed49SChris Mason if (cache_only) { 2546702ed49SChris Mason brelse(cur_bh); 2556702ed49SChris Mason continue; 2566702ed49SChris Mason } 257f2183bdeSChris Mason if (!cur_bh || !buffer_uptodate(cur_bh) || 258f2183bdeSChris Mason buffer_locked(cur_bh)) { 2596702ed49SChris Mason brelse(cur_bh); 2606702ed49SChris Mason cur_bh = read_tree_block(root, blocknr); 2616702ed49SChris Mason } 262f2183bdeSChris Mason } 263e9d0b13bSChris Mason if (search_start == 0) 264e9d0b13bSChris Mason search_start = last_block & ~((u64)65535); 265e9d0b13bSChris Mason 2666702ed49SChris Mason err = __btrfs_cow_block(trans, root, cur_bh, parent, i, 2676702ed49SChris Mason &tmp_bh, search_start, 2686702ed49SChris Mason min(8, end_slot - i)); 269252c38f0SYan if (err) { 270252c38f0SYan brelse(cur_bh); 2716702ed49SChris Mason break; 272252c38f0SYan } 2736702ed49SChris Mason search_start = bh_blocknr(tmp_bh); 274f2183bdeSChris Mason *last_ret = search_start; 275f2183bdeSChris Mason if (parent_level == 1) 276f2183bdeSChris Mason clear_buffer_defrag(tmp_bh); 2776702ed49SChris Mason brelse(tmp_bh); 2786702ed49SChris Mason } 2796702ed49SChris Mason return err; 2806702ed49SChris Mason } 2816702ed49SChris Mason 28274123bd7SChris Mason /* 28374123bd7SChris Mason * The leaf data grows from end-to-front in the node. 28474123bd7SChris Mason * this returns the address of the start of the last item, 28574123bd7SChris Mason * which is the stop of the leaf data stack 28674123bd7SChris Mason */ 287123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 288123abc88SChris Mason struct btrfs_leaf *leaf) 289be0e5c09SChris Mason { 2907518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 291be0e5c09SChris Mason if (nr == 0) 292123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 2930783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 294be0e5c09SChris Mason } 295be0e5c09SChris Mason 29674123bd7SChris Mason /* 29774123bd7SChris Mason * compare two keys in a memcmp fashion 29874123bd7SChris Mason */ 2999aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 300be0e5c09SChris Mason { 301e2fa7227SChris Mason struct btrfs_key k1; 302e2fa7227SChris Mason 303e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 304e2fa7227SChris Mason 305e2fa7227SChris Mason if (k1.objectid > k2->objectid) 306be0e5c09SChris Mason return 1; 307e2fa7227SChris Mason if (k1.objectid < k2->objectid) 308be0e5c09SChris Mason return -1; 309f254e52cSChris Mason if (k1.flags > k2->flags) 310f254e52cSChris Mason return 1; 311f254e52cSChris Mason if (k1.flags < k2->flags) 312f254e52cSChris Mason return -1; 31370b2befdSChris Mason if (k1.offset > k2->offset) 31470b2befdSChris Mason return 1; 31570b2befdSChris Mason if (k1.offset < k2->offset) 31670b2befdSChris Mason return -1; 317be0e5c09SChris Mason return 0; 318be0e5c09SChris Mason } 31974123bd7SChris Mason 320123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 321123abc88SChris Mason int level) 322aa5d6bedSChris Mason { 323234b63a0SChris Mason struct btrfs_node *parent = NULL; 324e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 325aa5d6bedSChris Mason int parent_slot; 3268d7be552SChris Mason int slot; 3278d7be552SChris Mason struct btrfs_key cpukey; 3287518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 329aa5d6bedSChris Mason 330aa5d6bedSChris Mason if (path->nodes[level + 1]) 331e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 332a1f39630SAneesh 3338d7be552SChris Mason slot = path->slots[level]; 3342cc58cf2SChris Mason BUG_ON(!buffer_uptodate(path->nodes[level])); 3357518a238SChris Mason BUG_ON(nritems == 0); 3367518a238SChris Mason if (parent) { 337e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 338a1f39630SAneesh 339a1f39630SAneesh parent_slot = path->slots[level + 1]; 340123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 341123abc88SChris Mason BUG_ON(memcmp(parent_key, &node->ptrs[0].key, 342e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 3431d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 3447518a238SChris Mason btrfs_header_blocknr(&node->header)); 345aa5d6bedSChris Mason } 346123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 3478d7be552SChris Mason if (slot != 0) { 3488d7be552SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[slot - 1].key); 3498d7be552SChris Mason BUG_ON(comp_keys(&node->ptrs[slot].key, &cpukey) <= 0); 3508d7be552SChris Mason } 3518d7be552SChris Mason if (slot < nritems - 1) { 3528d7be552SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[slot + 1].key); 3538d7be552SChris Mason BUG_ON(comp_keys(&node->ptrs[slot].key, &cpukey) >= 0); 354aa5d6bedSChris Mason } 355aa5d6bedSChris Mason return 0; 356aa5d6bedSChris Mason } 357aa5d6bedSChris Mason 358123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 359123abc88SChris Mason int level) 360aa5d6bedSChris Mason { 361e20d96d6SChris Mason struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]); 362234b63a0SChris Mason struct btrfs_node *parent = NULL; 363aa5d6bedSChris Mason int parent_slot; 3648d7be552SChris Mason int slot = path->slots[0]; 3658d7be552SChris Mason struct btrfs_key cpukey; 3668d7be552SChris Mason 3677518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 368aa5d6bedSChris Mason 369aa5d6bedSChris Mason if (path->nodes[level + 1]) 370e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 371a1f39630SAneesh 372123abc88SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 3737518a238SChris Mason 3747518a238SChris Mason if (nritems == 0) 3757518a238SChris Mason return 0; 3767518a238SChris Mason 3777518a238SChris Mason if (parent) { 378e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 379a1f39630SAneesh 380a1f39630SAneesh parent_slot = path->slots[level + 1]; 381123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 3826702ed49SChris Mason 383aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 384e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 3851d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 3867518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 387aa5d6bedSChris Mason } 3888d7be552SChris Mason if (slot != 0) { 3898d7be552SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[slot - 1].key); 3908d7be552SChris Mason BUG_ON(comp_keys(&leaf->items[slot].key, &cpukey) <= 0); 3918d7be552SChris Mason BUG_ON(btrfs_item_offset(leaf->items + slot - 1) != 3928d7be552SChris Mason btrfs_item_end(leaf->items + slot)); 393aa5d6bedSChris Mason } 3948d7be552SChris Mason if (slot < nritems - 1) { 3958d7be552SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[slot + 1].key); 3968d7be552SChris Mason BUG_ON(comp_keys(&leaf->items[slot].key, &cpukey) >= 0); 3978d7be552SChris Mason BUG_ON(btrfs_item_offset(leaf->items + slot) != 3988d7be552SChris Mason btrfs_item_end(leaf->items + slot + 1)); 399aa5d6bedSChris Mason } 4008d7be552SChris Mason BUG_ON(btrfs_item_offset(leaf->items) + 4018d7be552SChris Mason btrfs_item_size(leaf->items) != BTRFS_LEAF_DATA_SIZE(root)); 402aa5d6bedSChris Mason return 0; 403aa5d6bedSChris Mason } 404aa5d6bedSChris Mason 405123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 406123abc88SChris Mason int level) 407aa5d6bedSChris Mason { 4083eb0314dSChris Mason struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 4093eb0314dSChris Mason if (memcmp(node->header.fsid, root->fs_info->disk_super->fsid, 4103eb0314dSChris Mason sizeof(node->header.fsid))) 4113eb0314dSChris Mason BUG(); 412aa5d6bedSChris Mason if (level == 0) 413123abc88SChris Mason return check_leaf(root, path, level); 414123abc88SChris Mason return check_node(root, path, level); 415aa5d6bedSChris Mason } 416aa5d6bedSChris Mason 41774123bd7SChris Mason /* 41874123bd7SChris Mason * search for key in the array p. items p are item_size apart 41974123bd7SChris Mason * and there are 'max' items in p 42074123bd7SChris Mason * the slot in the array is returned via slot, and it points to 42174123bd7SChris Mason * the place where you would insert key if it is not found in 42274123bd7SChris Mason * the array. 42374123bd7SChris Mason * 42474123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 42574123bd7SChris Mason */ 4269aca1d51SChris Mason static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 427be0e5c09SChris Mason int max, int *slot) 428be0e5c09SChris Mason { 429be0e5c09SChris Mason int low = 0; 430be0e5c09SChris Mason int high = max; 431be0e5c09SChris Mason int mid; 432be0e5c09SChris Mason int ret; 433e2fa7227SChris Mason struct btrfs_disk_key *tmp; 434be0e5c09SChris Mason 435be0e5c09SChris Mason while(low < high) { 436be0e5c09SChris Mason mid = (low + high) / 2; 437e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 438be0e5c09SChris Mason ret = comp_keys(tmp, key); 439be0e5c09SChris Mason 440be0e5c09SChris Mason if (ret < 0) 441be0e5c09SChris Mason low = mid + 1; 442be0e5c09SChris Mason else if (ret > 0) 443be0e5c09SChris Mason high = mid; 444be0e5c09SChris Mason else { 445be0e5c09SChris Mason *slot = mid; 446be0e5c09SChris Mason return 0; 447be0e5c09SChris Mason } 448be0e5c09SChris Mason } 449be0e5c09SChris Mason *slot = low; 450be0e5c09SChris Mason return 1; 451be0e5c09SChris Mason } 452be0e5c09SChris Mason 45397571fd0SChris Mason /* 45497571fd0SChris Mason * simple bin_search frontend that does the right thing for 45597571fd0SChris Mason * leaves vs nodes 45697571fd0SChris Mason */ 4579aca1d51SChris Mason static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) 458be0e5c09SChris Mason { 4597518a238SChris Mason if (btrfs_is_leaf(c)) { 460234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 4610783fcfcSChris Mason return generic_bin_search((void *)l->items, 4620783fcfcSChris Mason sizeof(struct btrfs_item), 4637518a238SChris Mason key, btrfs_header_nritems(&c->header), 4647518a238SChris Mason slot); 465be0e5c09SChris Mason } else { 466123abc88SChris Mason return generic_bin_search((void *)c->ptrs, 467123abc88SChris Mason sizeof(struct btrfs_key_ptr), 4687518a238SChris Mason key, btrfs_header_nritems(&c->header), 4697518a238SChris Mason slot); 470be0e5c09SChris Mason } 471be0e5c09SChris Mason return -1; 472be0e5c09SChris Mason } 473be0e5c09SChris Mason 474e20d96d6SChris Mason static struct buffer_head *read_node_slot(struct btrfs_root *root, 475e20d96d6SChris Mason struct buffer_head *parent_buf, 476bb803951SChris Mason int slot) 477bb803951SChris Mason { 478e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(parent_buf); 479bb803951SChris Mason if (slot < 0) 480bb803951SChris Mason return NULL; 4817518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 482bb803951SChris Mason return NULL; 4831d4f8a0cSChris Mason return read_tree_block(root, btrfs_node_blockptr(node, slot)); 484bb803951SChris Mason } 485bb803951SChris Mason 486e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 487e089f05cSChris Mason *root, struct btrfs_path *path, int level) 488bb803951SChris Mason { 489e20d96d6SChris Mason struct buffer_head *right_buf; 490e20d96d6SChris Mason struct buffer_head *mid_buf; 491e20d96d6SChris Mason struct buffer_head *left_buf; 492e20d96d6SChris Mason struct buffer_head *parent_buf = NULL; 493234b63a0SChris Mason struct btrfs_node *right = NULL; 494234b63a0SChris Mason struct btrfs_node *mid; 495234b63a0SChris Mason struct btrfs_node *left = NULL; 496234b63a0SChris Mason struct btrfs_node *parent = NULL; 497bb803951SChris Mason int ret = 0; 498bb803951SChris Mason int wret; 499bb803951SChris Mason int pslot; 500bb803951SChris Mason int orig_slot = path->slots[level]; 50154aa1f4dSChris Mason int err_on_enospc = 0; 50279f95c82SChris Mason u64 orig_ptr; 503bb803951SChris Mason 504bb803951SChris Mason if (level == 0) 505bb803951SChris Mason return 0; 506bb803951SChris Mason 507bb803951SChris Mason mid_buf = path->nodes[level]; 508e20d96d6SChris Mason mid = btrfs_buffer_node(mid_buf); 5091d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 51079f95c82SChris Mason 511234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 512bb803951SChris Mason parent_buf = path->nodes[level + 1]; 513bb803951SChris Mason pslot = path->slots[level + 1]; 514bb803951SChris Mason 51540689478SChris Mason /* 51640689478SChris Mason * deal with the case where there is only one pointer in the root 51740689478SChris Mason * by promoting the node below to a root 51840689478SChris Mason */ 519bb803951SChris Mason if (!parent_buf) { 520e20d96d6SChris Mason struct buffer_head *child; 5217eccb903SChris Mason u64 blocknr = bh_blocknr(mid_buf); 522bb803951SChris Mason 5237518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 524bb803951SChris Mason return 0; 525bb803951SChris Mason 526bb803951SChris Mason /* promote the child to a root */ 527bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 528bb803951SChris Mason BUG_ON(!child); 529bb803951SChris Mason root->node = child; 530bb803951SChris Mason path->nodes[level] = NULL; 531d6025579SChris Mason clean_tree_block(trans, root, mid_buf); 532d6025579SChris Mason wait_on_buffer(mid_buf); 533bb803951SChris Mason /* once for the path */ 534234b63a0SChris Mason btrfs_block_release(root, mid_buf); 535bb803951SChris Mason /* once for the root ptr */ 536234b63a0SChris Mason btrfs_block_release(root, mid_buf); 537e089f05cSChris Mason return btrfs_free_extent(trans, root, blocknr, 1, 1); 538bb803951SChris Mason } 539e20d96d6SChris Mason parent = btrfs_buffer_node(parent_buf); 540bb803951SChris Mason 541123abc88SChris Mason if (btrfs_header_nritems(&mid->header) > 542123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 543bb803951SChris Mason return 0; 544bb803951SChris Mason 54554aa1f4dSChris Mason if (btrfs_header_nritems(&mid->header) < 2) 54654aa1f4dSChris Mason err_on_enospc = 1; 54754aa1f4dSChris Mason 548bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 549bb803951SChris Mason if (left_buf) { 55054aa1f4dSChris Mason wret = btrfs_cow_block(trans, root, left_buf, 55154aa1f4dSChris Mason parent_buf, pslot - 1, &left_buf); 55254aa1f4dSChris Mason if (wret) { 55354aa1f4dSChris Mason ret = wret; 55454aa1f4dSChris Mason goto enospc; 55554aa1f4dSChris Mason } 5562cc58cf2SChris Mason } 5572cc58cf2SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 5582cc58cf2SChris Mason if (right_buf) { 5592cc58cf2SChris Mason wret = btrfs_cow_block(trans, root, right_buf, 5602cc58cf2SChris Mason parent_buf, pslot + 1, &right_buf); 5612cc58cf2SChris Mason if (wret) { 5622cc58cf2SChris Mason ret = wret; 5632cc58cf2SChris Mason goto enospc; 5642cc58cf2SChris Mason } 5652cc58cf2SChris Mason } 5662cc58cf2SChris Mason 5672cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 5682cc58cf2SChris Mason if (left_buf) { 569e20d96d6SChris Mason left = btrfs_buffer_node(left_buf); 5707518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 571e089f05cSChris Mason wret = push_node_left(trans, root, left_buf, mid_buf); 57279f95c82SChris Mason if (wret < 0) 57379f95c82SChris Mason ret = wret; 57454aa1f4dSChris Mason if (btrfs_header_nritems(&mid->header) < 2) 57554aa1f4dSChris Mason err_on_enospc = 1; 576bb803951SChris Mason } 57779f95c82SChris Mason 57879f95c82SChris Mason /* 57979f95c82SChris Mason * then try to empty the right most buffer into the middle 58079f95c82SChris Mason */ 581bb803951SChris Mason if (right_buf) { 582e20d96d6SChris Mason right = btrfs_buffer_node(right_buf); 583e089f05cSChris Mason wret = push_node_left(trans, root, mid_buf, right_buf); 58454aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 58579f95c82SChris Mason ret = wret; 5867518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 5877eccb903SChris Mason u64 blocknr = bh_blocknr(right_buf); 588e089f05cSChris Mason clean_tree_block(trans, root, right_buf); 589d6025579SChris Mason wait_on_buffer(right_buf); 590d6025579SChris Mason btrfs_block_release(root, right_buf); 591bb803951SChris Mason right_buf = NULL; 592bb803951SChris Mason right = NULL; 593e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 594e089f05cSChris Mason 1); 595bb803951SChris Mason if (wret) 596bb803951SChris Mason ret = wret; 597e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 598bb803951SChris Mason if (wret) 599bb803951SChris Mason ret = wret; 600bb803951SChris Mason } else { 601d6025579SChris Mason btrfs_memcpy(root, parent, 602d6025579SChris Mason &parent->ptrs[pslot + 1].key, 603123abc88SChris Mason &right->ptrs[0].key, 604e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 605d6025579SChris Mason btrfs_mark_buffer_dirty(parent_buf); 606bb803951SChris Mason } 607bb803951SChris Mason } 6087518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 60979f95c82SChris Mason /* 61079f95c82SChris Mason * we're not allowed to leave a node with one item in the 61179f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 61279f95c82SChris Mason * could try to delete the only pointer in this node. 61379f95c82SChris Mason * So, pull some keys from the left. 61479f95c82SChris Mason * There has to be a left pointer at this point because 61579f95c82SChris Mason * otherwise we would have pulled some pointers from the 61679f95c82SChris Mason * right 61779f95c82SChris Mason */ 61879f95c82SChris Mason BUG_ON(!left_buf); 619e089f05cSChris Mason wret = balance_node_right(trans, root, mid_buf, left_buf); 62054aa1f4dSChris Mason if (wret < 0) { 62179f95c82SChris Mason ret = wret; 62254aa1f4dSChris Mason goto enospc; 62354aa1f4dSChris Mason } 62479f95c82SChris Mason BUG_ON(wret == 1); 62579f95c82SChris Mason } 6267518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 62779f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 6287eccb903SChris Mason u64 blocknr = bh_blocknr(mid_buf); 629e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 630d6025579SChris Mason wait_on_buffer(mid_buf); 631d6025579SChris Mason btrfs_block_release(root, mid_buf); 632bb803951SChris Mason mid_buf = NULL; 633bb803951SChris Mason mid = NULL; 634e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 635bb803951SChris Mason if (wret) 636bb803951SChris Mason ret = wret; 637e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 638bb803951SChris Mason if (wret) 639bb803951SChris Mason ret = wret; 64079f95c82SChris Mason } else { 64179f95c82SChris Mason /* update the parent key to reflect our changes */ 642d6025579SChris Mason btrfs_memcpy(root, parent, 643d6025579SChris Mason &parent->ptrs[pslot].key, &mid->ptrs[0].key, 644e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 645d6025579SChris Mason btrfs_mark_buffer_dirty(parent_buf); 64679f95c82SChris Mason } 647bb803951SChris Mason 64879f95c82SChris Mason /* update the path */ 649bb803951SChris Mason if (left_buf) { 6507518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 651e20d96d6SChris Mason get_bh(left_buf); 652bb803951SChris Mason path->nodes[level] = left_buf; 653bb803951SChris Mason path->slots[level + 1] -= 1; 654bb803951SChris Mason path->slots[level] = orig_slot; 655bb803951SChris Mason if (mid_buf) 656234b63a0SChris Mason btrfs_block_release(root, mid_buf); 657bb803951SChris Mason } else { 6587518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 659bb803951SChris Mason path->slots[level] = orig_slot; 660bb803951SChris Mason } 661bb803951SChris Mason } 66279f95c82SChris Mason /* double check we haven't messed things up */ 663123abc88SChris Mason check_block(root, path, level); 664e20d96d6SChris Mason if (orig_ptr != 665e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]), 6661d4f8a0cSChris Mason path->slots[level])) 66779f95c82SChris Mason BUG(); 66854aa1f4dSChris Mason enospc: 669bb803951SChris Mason if (right_buf) 670234b63a0SChris Mason btrfs_block_release(root, right_buf); 671bb803951SChris Mason if (left_buf) 672234b63a0SChris Mason btrfs_block_release(root, left_buf); 673bb803951SChris Mason return ret; 674bb803951SChris Mason } 675bb803951SChris Mason 676e66f709bSChris Mason /* returns zero if the push worked, non-zero otherwise */ 677e66f709bSChris Mason static int push_nodes_for_insert(struct btrfs_trans_handle *trans, 678e66f709bSChris Mason struct btrfs_root *root, 679e66f709bSChris Mason struct btrfs_path *path, int level) 680e66f709bSChris Mason { 681e66f709bSChris Mason struct buffer_head *right_buf; 682e66f709bSChris Mason struct buffer_head *mid_buf; 683e66f709bSChris Mason struct buffer_head *left_buf; 684e66f709bSChris Mason struct buffer_head *parent_buf = NULL; 685e66f709bSChris Mason struct btrfs_node *right = NULL; 686e66f709bSChris Mason struct btrfs_node *mid; 687e66f709bSChris Mason struct btrfs_node *left = NULL; 688e66f709bSChris Mason struct btrfs_node *parent = NULL; 689e66f709bSChris Mason int ret = 0; 690e66f709bSChris Mason int wret; 691e66f709bSChris Mason int pslot; 692e66f709bSChris Mason int orig_slot = path->slots[level]; 693e66f709bSChris Mason u64 orig_ptr; 694e66f709bSChris Mason 695e66f709bSChris Mason if (level == 0) 696e66f709bSChris Mason return 1; 697e66f709bSChris Mason 698e66f709bSChris Mason mid_buf = path->nodes[level]; 699e66f709bSChris Mason mid = btrfs_buffer_node(mid_buf); 700e66f709bSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 701e66f709bSChris Mason 702e66f709bSChris Mason if (level < BTRFS_MAX_LEVEL - 1) 703e66f709bSChris Mason parent_buf = path->nodes[level + 1]; 704e66f709bSChris Mason pslot = path->slots[level + 1]; 705e66f709bSChris Mason 706e66f709bSChris Mason if (!parent_buf) 707e66f709bSChris Mason return 1; 708e66f709bSChris Mason parent = btrfs_buffer_node(parent_buf); 709e66f709bSChris Mason 710e66f709bSChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 711e66f709bSChris Mason 712e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 713e66f709bSChris Mason if (left_buf) { 714e66f709bSChris Mason u32 left_nr; 715e66f709bSChris Mason left = btrfs_buffer_node(left_buf); 716e66f709bSChris Mason left_nr = btrfs_header_nritems(&left->header); 71733ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 71833ade1f8SChris Mason wret = 1; 71933ade1f8SChris Mason } else { 72054aa1f4dSChris Mason ret = btrfs_cow_block(trans, root, left_buf, parent_buf, 72133ade1f8SChris Mason pslot - 1, &left_buf); 72254aa1f4dSChris Mason if (ret) 72354aa1f4dSChris Mason wret = 1; 72454aa1f4dSChris Mason else { 72533ade1f8SChris Mason left = btrfs_buffer_node(left_buf); 72654aa1f4dSChris Mason wret = push_node_left(trans, root, 72754aa1f4dSChris Mason left_buf, mid_buf); 72854aa1f4dSChris Mason } 72933ade1f8SChris Mason } 730e66f709bSChris Mason if (wret < 0) 731e66f709bSChris Mason ret = wret; 732e66f709bSChris Mason if (wret == 0) { 733e66f709bSChris Mason orig_slot += left_nr; 734e66f709bSChris Mason btrfs_memcpy(root, parent, 735e66f709bSChris Mason &parent->ptrs[pslot].key, 736e66f709bSChris Mason &mid->ptrs[0].key, 737e66f709bSChris Mason sizeof(struct btrfs_disk_key)); 738e66f709bSChris Mason btrfs_mark_buffer_dirty(parent_buf); 739e66f709bSChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 740e66f709bSChris Mason path->nodes[level] = left_buf; 741e66f709bSChris Mason path->slots[level + 1] -= 1; 742e66f709bSChris Mason path->slots[level] = orig_slot; 743e66f709bSChris Mason btrfs_block_release(root, mid_buf); 744e66f709bSChris Mason } else { 745e66f709bSChris Mason orig_slot -= 746e66f709bSChris Mason btrfs_header_nritems(&left->header); 747e66f709bSChris Mason path->slots[level] = orig_slot; 748e66f709bSChris Mason btrfs_block_release(root, left_buf); 749e66f709bSChris Mason } 750e66f709bSChris Mason check_node(root, path, level); 751e66f709bSChris Mason return 0; 752e66f709bSChris Mason } 753e66f709bSChris Mason btrfs_block_release(root, left_buf); 754e66f709bSChris Mason } 755e66f709bSChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 756e66f709bSChris Mason 757e66f709bSChris Mason /* 758e66f709bSChris Mason * then try to empty the right most buffer into the middle 759e66f709bSChris Mason */ 760e66f709bSChris Mason if (right_buf) { 76133ade1f8SChris Mason u32 right_nr; 762e66f709bSChris Mason right = btrfs_buffer_node(right_buf); 76333ade1f8SChris Mason right_nr = btrfs_header_nritems(&right->header); 76433ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 76533ade1f8SChris Mason wret = 1; 76633ade1f8SChris Mason } else { 76754aa1f4dSChris Mason ret = btrfs_cow_block(trans, root, right_buf, 76854aa1f4dSChris Mason parent_buf, pslot + 1, 76954aa1f4dSChris Mason &right_buf); 77054aa1f4dSChris Mason if (ret) 77154aa1f4dSChris Mason wret = 1; 77254aa1f4dSChris Mason else { 77333ade1f8SChris Mason right = btrfs_buffer_node(right_buf); 77433ade1f8SChris Mason wret = balance_node_right(trans, root, 77533ade1f8SChris Mason right_buf, mid_buf); 77633ade1f8SChris Mason } 77754aa1f4dSChris Mason } 778e66f709bSChris Mason if (wret < 0) 779e66f709bSChris Mason ret = wret; 780e66f709bSChris Mason if (wret == 0) { 781e66f709bSChris Mason btrfs_memcpy(root, parent, 782e66f709bSChris Mason &parent->ptrs[pslot + 1].key, 783e66f709bSChris Mason &right->ptrs[0].key, 784e66f709bSChris Mason sizeof(struct btrfs_disk_key)); 785e66f709bSChris Mason btrfs_mark_buffer_dirty(parent_buf); 786e66f709bSChris Mason if (btrfs_header_nritems(&mid->header) <= orig_slot) { 787e66f709bSChris Mason path->nodes[level] = right_buf; 788e66f709bSChris Mason path->slots[level + 1] += 1; 789e66f709bSChris Mason path->slots[level] = orig_slot - 790e66f709bSChris Mason btrfs_header_nritems(&mid->header); 791e66f709bSChris Mason btrfs_block_release(root, mid_buf); 792e66f709bSChris Mason } else { 793e66f709bSChris Mason btrfs_block_release(root, right_buf); 794e66f709bSChris Mason } 795e66f709bSChris Mason check_node(root, path, level); 796e66f709bSChris Mason return 0; 797e66f709bSChris Mason } 798e66f709bSChris Mason btrfs_block_release(root, right_buf); 799e66f709bSChris Mason } 800e66f709bSChris Mason check_node(root, path, level); 801e66f709bSChris Mason return 1; 802e66f709bSChris Mason } 803e66f709bSChris Mason 80474123bd7SChris Mason /* 8053c69faecSChris Mason * readahead one full node of leaves 8063c69faecSChris Mason */ 8073c69faecSChris Mason static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, 8086702ed49SChris Mason int level, int slot) 8093c69faecSChris Mason { 8103c69faecSChris Mason struct btrfs_node *node; 8113c69faecSChris Mason int i; 8123c69faecSChris Mason u32 nritems; 8133c69faecSChris Mason u64 item_objectid; 8143c69faecSChris Mason u64 blocknr; 8153c69faecSChris Mason u64 search; 8163c69faecSChris Mason u64 cluster_start; 8173c69faecSChris Mason int ret; 8183c69faecSChris Mason int nread = 0; 8193c69faecSChris Mason int direction = path->reada; 8203c69faecSChris Mason struct radix_tree_root found; 8213c69faecSChris Mason unsigned long gang[8]; 8223c69faecSChris Mason struct buffer_head *bh; 8233c69faecSChris Mason 8246702ed49SChris Mason if (level == 0) 8253c69faecSChris Mason return; 8263c69faecSChris Mason 8276702ed49SChris Mason if (!path->nodes[level]) 8286702ed49SChris Mason return; 8296702ed49SChris Mason 8306702ed49SChris Mason node = btrfs_buffer_node(path->nodes[level]); 8313c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 8323c69faecSChris Mason bh = btrfs_find_tree_block(root, search); 8333c69faecSChris Mason if (bh) { 8343c69faecSChris Mason brelse(bh); 8353c69faecSChris Mason return; 8363c69faecSChris Mason } 8373c69faecSChris Mason 8383c69faecSChris Mason init_bit_radix(&found); 8393c69faecSChris Mason nritems = btrfs_header_nritems(&node->header); 8403c69faecSChris Mason for (i = slot; i < nritems; i++) { 8413c69faecSChris Mason item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key); 8423c69faecSChris Mason blocknr = btrfs_node_blockptr(node, i); 8433c69faecSChris Mason set_radix_bit(&found, blocknr); 8443c69faecSChris Mason } 8453c69faecSChris Mason if (direction > 0) { 8463c69faecSChris Mason cluster_start = search - 4; 8473c69faecSChris Mason if (cluster_start > search) 8483c69faecSChris Mason cluster_start = 0; 8493c69faecSChris Mason } else 8503c69faecSChris Mason cluster_start = search + 4; 8513c69faecSChris Mason while(1) { 8523c69faecSChris Mason ret = find_first_radix_bit(&found, gang, 0, ARRAY_SIZE(gang)); 8533c69faecSChris Mason if (!ret) 8543c69faecSChris Mason break; 8553c69faecSChris Mason for (i = 0; i < ret; i++) { 8563c69faecSChris Mason blocknr = gang[i]; 8573c69faecSChris Mason clear_radix_bit(&found, blocknr); 8582cc58cf2SChris Mason if (path->reada == 1 && nread > 16) 8593c69faecSChris Mason continue; 860f2183bdeSChris Mason if (close_blocks(cluster_start, blocknr)) { 8613c69faecSChris Mason readahead_tree_block(root, blocknr); 8623c69faecSChris Mason nread++; 8633c69faecSChris Mason cluster_start = blocknr; 8643c69faecSChris Mason } 8653c69faecSChris Mason } 8663c69faecSChris Mason } 8673c69faecSChris Mason } 8683c69faecSChris Mason /* 86974123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 87074123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 87174123bd7SChris Mason * level of the path (level 0) 87274123bd7SChris Mason * 87374123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 874aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 875aa5d6bedSChris Mason * search a negative error number is returned. 87697571fd0SChris Mason * 87797571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 87897571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 87997571fd0SChris Mason * possible) 88074123bd7SChris Mason */ 881e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 882e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 883e089f05cSChris Mason ins_len, int cow) 884be0e5c09SChris Mason { 885e20d96d6SChris Mason struct buffer_head *b; 886234b63a0SChris Mason struct btrfs_node *c; 8873c69faecSChris Mason u64 blocknr; 888be0e5c09SChris Mason int slot; 889be0e5c09SChris Mason int ret; 890be0e5c09SChris Mason int level; 8913c69faecSChris Mason int should_reada = p->reada; 8929f3a7427SChris Mason u8 lowest_level = 0; 8939f3a7427SChris Mason 8946702ed49SChris Mason lowest_level = p->lowest_level; 8956702ed49SChris Mason WARN_ON(lowest_level && ins_len); 89622b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 89722b0ebdaSChris Mason WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex)); 898bb803951SChris Mason again: 899bb803951SChris Mason b = root->node; 900e20d96d6SChris Mason get_bh(b); 901eb60ceacSChris Mason while (b) { 902e20d96d6SChris Mason c = btrfs_buffer_node(b); 903e20d96d6SChris Mason level = btrfs_header_level(&c->header); 90402217ed2SChris Mason if (cow) { 90502217ed2SChris Mason int wret; 906e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 907e20d96d6SChris Mason p->nodes[level + 1], 908e20d96d6SChris Mason p->slots[level + 1], 909252c38f0SYan &b); 91054aa1f4dSChris Mason if (wret) { 911252c38f0SYan btrfs_block_release(root, b); 91254aa1f4dSChris Mason return wret; 91354aa1f4dSChris Mason } 9142c90e5d6SChris Mason c = btrfs_buffer_node(b); 91502217ed2SChris Mason } 91602217ed2SChris Mason BUG_ON(!cow && ins_len); 9172c90e5d6SChris Mason if (level != btrfs_header_level(&c->header)) 9182c90e5d6SChris Mason WARN_ON(1); 9192c90e5d6SChris Mason level = btrfs_header_level(&c->header); 920eb60ceacSChris Mason p->nodes[level] = b; 921123abc88SChris Mason ret = check_block(root, p, level); 922aa5d6bedSChris Mason if (ret) 923aa5d6bedSChris Mason return -1; 924be0e5c09SChris Mason ret = bin_search(c, key, &slot); 9257518a238SChris Mason if (!btrfs_is_leaf(c)) { 926be0e5c09SChris Mason if (ret && slot > 0) 927be0e5c09SChris Mason slot -= 1; 928be0e5c09SChris Mason p->slots[level] = slot; 929d4dbff95SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) >= 930d4dbff95SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 931e089f05cSChris Mason int sret = split_node(trans, root, p, level); 9325c680ed6SChris Mason BUG_ON(sret > 0); 9335c680ed6SChris Mason if (sret) 9345c680ed6SChris Mason return sret; 9355c680ed6SChris Mason b = p->nodes[level]; 936e20d96d6SChris Mason c = btrfs_buffer_node(b); 9375c680ed6SChris Mason slot = p->slots[level]; 938bb803951SChris Mason } else if (ins_len < 0) { 939e089f05cSChris Mason int sret = balance_level(trans, root, p, 940e089f05cSChris Mason level); 941bb803951SChris Mason if (sret) 942bb803951SChris Mason return sret; 943bb803951SChris Mason b = p->nodes[level]; 944bb803951SChris Mason if (!b) 945bb803951SChris Mason goto again; 946e20d96d6SChris Mason c = btrfs_buffer_node(b); 947bb803951SChris Mason slot = p->slots[level]; 9487518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 9495c680ed6SChris Mason } 9509f3a7427SChris Mason /* this is only true while dropping a snapshot */ 9519f3a7427SChris Mason if (level == lowest_level) 9529f3a7427SChris Mason break; 9533c69faecSChris Mason blocknr = btrfs_node_blockptr(c, slot); 9546702ed49SChris Mason if (should_reada) 9556702ed49SChris Mason reada_for_search(root, p, level, slot); 9561d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 9573c69faecSChris Mason 958be0e5c09SChris Mason } else { 959234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 960be0e5c09SChris Mason p->slots[level] = slot; 961123abc88SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 9620783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 963d4dbff95SChris Mason int sret = split_leaf(trans, root, key, 964d4dbff95SChris Mason p, ins_len); 9655c680ed6SChris Mason BUG_ON(sret > 0); 9665c680ed6SChris Mason if (sret) 9675c680ed6SChris Mason return sret; 9685c680ed6SChris Mason } 969be0e5c09SChris Mason return ret; 970be0e5c09SChris Mason } 971be0e5c09SChris Mason } 972aa5d6bedSChris Mason return 1; 973be0e5c09SChris Mason } 974be0e5c09SChris Mason 97574123bd7SChris Mason /* 97674123bd7SChris Mason * adjust the pointers going up the tree, starting at level 97774123bd7SChris Mason * making sure the right key of each node is points to 'key'. 97874123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 97974123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 98074123bd7SChris Mason * higher levels 981aa5d6bedSChris Mason * 982aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 983aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 98474123bd7SChris Mason */ 985e089f05cSChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root 986e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 987e089f05cSChris Mason *key, int level) 988be0e5c09SChris Mason { 989be0e5c09SChris Mason int i; 990aa5d6bedSChris Mason int ret = 0; 991234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 992234b63a0SChris Mason struct btrfs_node *t; 993be0e5c09SChris Mason int tslot = path->slots[i]; 994eb60ceacSChris Mason if (!path->nodes[i]) 995be0e5c09SChris Mason break; 996e20d96d6SChris Mason t = btrfs_buffer_node(path->nodes[i]); 997d6025579SChris Mason btrfs_memcpy(root, t, &t->ptrs[tslot].key, key, sizeof(*key)); 998d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 999be0e5c09SChris Mason if (tslot != 0) 1000be0e5c09SChris Mason break; 1001be0e5c09SChris Mason } 1002aa5d6bedSChris Mason return ret; 1003be0e5c09SChris Mason } 1004be0e5c09SChris Mason 100574123bd7SChris Mason /* 100674123bd7SChris Mason * try to push data from one node into the next node left in the 100779f95c82SChris Mason * tree. 1008aa5d6bedSChris Mason * 1009aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1010aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 101174123bd7SChris Mason */ 1012e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 1013e20d96d6SChris Mason *root, struct buffer_head *dst_buf, struct 1014e20d96d6SChris Mason buffer_head *src_buf) 1015be0e5c09SChris Mason { 1016e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 1017e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 1018be0e5c09SChris Mason int push_items = 0; 1019bb803951SChris Mason int src_nritems; 1020bb803951SChris Mason int dst_nritems; 1021aa5d6bedSChris Mason int ret = 0; 1022be0e5c09SChris Mason 10237518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 10247518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 1025123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 102654aa1f4dSChris Mason 1027eb60ceacSChris Mason if (push_items <= 0) { 1028be0e5c09SChris Mason return 1; 1029eb60ceacSChris Mason } 1030be0e5c09SChris Mason 1031be0e5c09SChris Mason if (src_nritems < push_items) 1032be0e5c09SChris Mason push_items = src_nritems; 103379f95c82SChris Mason 1034d6025579SChris Mason btrfs_memcpy(root, dst, dst->ptrs + dst_nritems, src->ptrs, 1035123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 1036bb803951SChris Mason if (push_items < src_nritems) { 1037d6025579SChris Mason btrfs_memmove(root, src, src->ptrs, src->ptrs + push_items, 1038e2fa7227SChris Mason (src_nritems - push_items) * 1039123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1040bb803951SChris Mason } 10417518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 10427518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 1043d6025579SChris Mason btrfs_mark_buffer_dirty(src_buf); 1044d6025579SChris Mason btrfs_mark_buffer_dirty(dst_buf); 1045bb803951SChris Mason return ret; 1046be0e5c09SChris Mason } 1047be0e5c09SChris Mason 104897571fd0SChris Mason /* 104979f95c82SChris Mason * try to push data from one node into the next node right in the 105079f95c82SChris Mason * tree. 105179f95c82SChris Mason * 105279f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 105379f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 105479f95c82SChris Mason * 105579f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 105679f95c82SChris Mason */ 1057e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 1058e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 1059e20d96d6SChris Mason struct buffer_head *src_buf) 106079f95c82SChris Mason { 1061e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 1062e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 106379f95c82SChris Mason int push_items = 0; 106479f95c82SChris Mason int max_push; 106579f95c82SChris Mason int src_nritems; 106679f95c82SChris Mason int dst_nritems; 106779f95c82SChris Mason int ret = 0; 106879f95c82SChris Mason 10697518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 10707518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 1071123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 107279f95c82SChris Mason if (push_items <= 0) { 107379f95c82SChris Mason return 1; 107479f95c82SChris Mason } 107579f95c82SChris Mason 107679f95c82SChris Mason max_push = src_nritems / 2 + 1; 107779f95c82SChris Mason /* don't try to empty the node */ 1078252c38f0SYan if (max_push >= src_nritems) 107979f95c82SChris Mason return 1; 1080252c38f0SYan 108179f95c82SChris Mason if (max_push < push_items) 108279f95c82SChris Mason push_items = max_push; 108379f95c82SChris Mason 1084d6025579SChris Mason btrfs_memmove(root, dst, dst->ptrs + push_items, dst->ptrs, 1085123abc88SChris Mason dst_nritems * sizeof(struct btrfs_key_ptr)); 1086d6025579SChris Mason 1087d6025579SChris Mason btrfs_memcpy(root, dst, dst->ptrs, 1088d6025579SChris Mason src->ptrs + src_nritems - push_items, 1089123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 109079f95c82SChris Mason 10917518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 10927518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 109379f95c82SChris Mason 1094d6025579SChris Mason btrfs_mark_buffer_dirty(src_buf); 1095d6025579SChris Mason btrfs_mark_buffer_dirty(dst_buf); 109679f95c82SChris Mason return ret; 109779f95c82SChris Mason } 109879f95c82SChris Mason 109979f95c82SChris Mason /* 110097571fd0SChris Mason * helper function to insert a new root level in the tree. 110197571fd0SChris Mason * A new node is allocated, and a single item is inserted to 110297571fd0SChris Mason * point to the existing root 1103aa5d6bedSChris Mason * 1104aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 110597571fd0SChris Mason */ 1106e089f05cSChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root 1107e089f05cSChris Mason *root, struct btrfs_path *path, int level) 110874123bd7SChris Mason { 1109e20d96d6SChris Mason struct buffer_head *t; 1110234b63a0SChris Mason struct btrfs_node *lower; 1111234b63a0SChris Mason struct btrfs_node *c; 1112e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 11135c680ed6SChris Mason 11145c680ed6SChris Mason BUG_ON(path->nodes[level]); 11155c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 11165c680ed6SChris Mason 11176702ed49SChris Mason t = btrfs_alloc_free_block(trans, root, root->node->b_blocknr, 0); 111854aa1f4dSChris Mason if (IS_ERR(t)) 111954aa1f4dSChris Mason return PTR_ERR(t); 1120e20d96d6SChris Mason c = btrfs_buffer_node(t); 1121123abc88SChris Mason memset(c, 0, root->blocksize); 11227518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 11237518a238SChris Mason btrfs_set_header_level(&c->header, level); 11247eccb903SChris Mason btrfs_set_header_blocknr(&c->header, bh_blocknr(t)); 11257f5c1516SChris Mason btrfs_set_header_generation(&c->header, trans->transid); 11264d775673SChris Mason btrfs_set_header_owner(&c->header, root->root_key.objectid); 1127e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level-1]); 11283eb0314dSChris Mason memcpy(c->header.fsid, root->fs_info->disk_super->fsid, 11293eb0314dSChris Mason sizeof(c->header.fsid)); 11307518a238SChris Mason if (btrfs_is_leaf(lower)) 1131234b63a0SChris Mason lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 113274123bd7SChris Mason else 1133123abc88SChris Mason lower_key = &lower->ptrs[0].key; 1134d6025579SChris Mason btrfs_memcpy(root, c, &c->ptrs[0].key, lower_key, 1135d6025579SChris Mason sizeof(struct btrfs_disk_key)); 11367eccb903SChris Mason btrfs_set_node_blockptr(c, 0, bh_blocknr(path->nodes[level - 1])); 1137d5719762SChris Mason 1138d6025579SChris Mason btrfs_mark_buffer_dirty(t); 1139d5719762SChris Mason 1140cfaa7295SChris Mason /* the super has an extra ref to root->node */ 1141234b63a0SChris Mason btrfs_block_release(root, root->node); 114274123bd7SChris Mason root->node = t; 1143e20d96d6SChris Mason get_bh(t); 114474123bd7SChris Mason path->nodes[level] = t; 114574123bd7SChris Mason path->slots[level] = 0; 114674123bd7SChris Mason return 0; 114774123bd7SChris Mason } 11485c680ed6SChris Mason 11495c680ed6SChris Mason /* 11505c680ed6SChris Mason * worker function to insert a single pointer in a node. 11515c680ed6SChris Mason * the node should have enough room for the pointer already 115297571fd0SChris Mason * 11535c680ed6SChris Mason * slot and level indicate where you want the key to go, and 11545c680ed6SChris Mason * blocknr is the block the key points to. 1155aa5d6bedSChris Mason * 1156aa5d6bedSChris Mason * returns zero on success and < 0 on any error 11575c680ed6SChris Mason */ 1158e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 1159e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 1160e089f05cSChris Mason *key, u64 blocknr, int slot, int level) 11615c680ed6SChris Mason { 1162234b63a0SChris Mason struct btrfs_node *lower; 11635c680ed6SChris Mason int nritems; 11645c680ed6SChris Mason 11655c680ed6SChris Mason BUG_ON(!path->nodes[level]); 1166e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level]); 11677518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 116874123bd7SChris Mason if (slot > nritems) 116974123bd7SChris Mason BUG(); 1170123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 117174123bd7SChris Mason BUG(); 117274123bd7SChris Mason if (slot != nritems) { 1173d6025579SChris Mason btrfs_memmove(root, lower, lower->ptrs + slot + 1, 1174d6025579SChris Mason lower->ptrs + slot, 1175123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 117674123bd7SChris Mason } 1177d6025579SChris Mason btrfs_memcpy(root, lower, &lower->ptrs[slot].key, 1178d6025579SChris Mason key, sizeof(struct btrfs_disk_key)); 11791d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 11807518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 1181d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[level]); 1182098f59c2SChris Mason check_node(root, path, level); 118374123bd7SChris Mason return 0; 118474123bd7SChris Mason } 118574123bd7SChris Mason 118697571fd0SChris Mason /* 118797571fd0SChris Mason * split the node at the specified level in path in two. 118897571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 118997571fd0SChris Mason * 119097571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 119197571fd0SChris Mason * left and right, if either one works, it returns right away. 1192aa5d6bedSChris Mason * 1193aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 119497571fd0SChris Mason */ 1195e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 1196e089f05cSChris Mason *root, struct btrfs_path *path, int level) 1197be0e5c09SChris Mason { 1198e20d96d6SChris Mason struct buffer_head *t; 1199234b63a0SChris Mason struct btrfs_node *c; 1200e20d96d6SChris Mason struct buffer_head *split_buffer; 1201234b63a0SChris Mason struct btrfs_node *split; 1202be0e5c09SChris Mason int mid; 12035c680ed6SChris Mason int ret; 1204aa5d6bedSChris Mason int wret; 12057518a238SChris Mason u32 c_nritems; 1206be0e5c09SChris Mason 12075c680ed6SChris Mason t = path->nodes[level]; 1208e20d96d6SChris Mason c = btrfs_buffer_node(t); 12095c680ed6SChris Mason if (t == root->node) { 12105c680ed6SChris Mason /* trying to split the root, lets make a new one */ 1211e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 12125c680ed6SChris Mason if (ret) 12135c680ed6SChris Mason return ret; 1214e66f709bSChris Mason } else { 1215e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 1216e66f709bSChris Mason t = path->nodes[level]; 1217e66f709bSChris Mason c = btrfs_buffer_node(t); 1218e66f709bSChris Mason if (!ret && 1219e66f709bSChris Mason btrfs_header_nritems(&c->header) < 1220e66f709bSChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 1) 1221e66f709bSChris Mason return 0; 122254aa1f4dSChris Mason if (ret < 0) 122354aa1f4dSChris Mason return ret; 12245c680ed6SChris Mason } 1225e66f709bSChris Mason 12267518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 12276702ed49SChris Mason split_buffer = btrfs_alloc_free_block(trans, root, t->b_blocknr, 0); 122854aa1f4dSChris Mason if (IS_ERR(split_buffer)) 122954aa1f4dSChris Mason return PTR_ERR(split_buffer); 123054aa1f4dSChris Mason 1231e20d96d6SChris Mason split = btrfs_buffer_node(split_buffer); 12327518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 12339a6f11edSChris Mason btrfs_set_header_level(&split->header, btrfs_header_level(&c->header)); 12347eccb903SChris Mason btrfs_set_header_blocknr(&split->header, bh_blocknr(split_buffer)); 12357f5c1516SChris Mason btrfs_set_header_generation(&split->header, trans->transid); 12364d775673SChris Mason btrfs_set_header_owner(&split->header, root->root_key.objectid); 12373eb0314dSChris Mason memcpy(split->header.fsid, root->fs_info->disk_super->fsid, 12383eb0314dSChris Mason sizeof(split->header.fsid)); 12397518a238SChris Mason mid = (c_nritems + 1) / 2; 1240d6025579SChris Mason btrfs_memcpy(root, split, split->ptrs, c->ptrs + mid, 1241123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 12427518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 12437518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 1244aa5d6bedSChris Mason ret = 0; 1245aa5d6bedSChris Mason 1246d6025579SChris Mason btrfs_mark_buffer_dirty(t); 1247d6025579SChris Mason btrfs_mark_buffer_dirty(split_buffer); 1248e089f05cSChris Mason wret = insert_ptr(trans, root, path, &split->ptrs[0].key, 12497eccb903SChris Mason bh_blocknr(split_buffer), path->slots[level + 1] + 1, 1250123abc88SChris Mason level + 1); 1251aa5d6bedSChris Mason if (wret) 1252aa5d6bedSChris Mason ret = wret; 1253aa5d6bedSChris Mason 12545de08d7dSChris Mason if (path->slots[level] >= mid) { 12555c680ed6SChris Mason path->slots[level] -= mid; 1256234b63a0SChris Mason btrfs_block_release(root, t); 12575c680ed6SChris Mason path->nodes[level] = split_buffer; 12585c680ed6SChris Mason path->slots[level + 1] += 1; 1259eb60ceacSChris Mason } else { 1260234b63a0SChris Mason btrfs_block_release(root, split_buffer); 1261be0e5c09SChris Mason } 1262aa5d6bedSChris Mason return ret; 1263be0e5c09SChris Mason } 1264be0e5c09SChris Mason 126574123bd7SChris Mason /* 126674123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 126774123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 126874123bd7SChris Mason * space used both by the item structs and the item data 126974123bd7SChris Mason */ 1270234b63a0SChris Mason static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 1271be0e5c09SChris Mason { 1272be0e5c09SChris Mason int data_len; 1273d4dbff95SChris Mason int nritems = btrfs_header_nritems(&l->header); 1274d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 1275be0e5c09SChris Mason 1276be0e5c09SChris Mason if (!nr) 1277be0e5c09SChris Mason return 0; 12780783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 12790783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 12800783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 1281d4dbff95SChris Mason WARN_ON(data_len < 0); 1282be0e5c09SChris Mason return data_len; 1283be0e5c09SChris Mason } 1284be0e5c09SChris Mason 128574123bd7SChris Mason /* 1286d4dbff95SChris Mason * The space between the end of the leaf items and 1287d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 1288d4dbff95SChris Mason * the leaf has left for both items and data 1289d4dbff95SChris Mason */ 1290d4dbff95SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) 1291d4dbff95SChris Mason { 1292d4dbff95SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 1293d4dbff95SChris Mason return BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 1294d4dbff95SChris Mason } 1295d4dbff95SChris Mason 1296d4dbff95SChris Mason /* 129700ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 129800ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 1299aa5d6bedSChris Mason * 1300aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 1301aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 130200ec4c51SChris Mason */ 1303e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 1304e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 130500ec4c51SChris Mason { 1306e20d96d6SChris Mason struct buffer_head *left_buf = path->nodes[0]; 1307e20d96d6SChris Mason struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf); 1308234b63a0SChris Mason struct btrfs_leaf *right; 1309e20d96d6SChris Mason struct buffer_head *right_buf; 1310e20d96d6SChris Mason struct buffer_head *upper; 1311e20d96d6SChris Mason struct btrfs_node *upper_node; 131200ec4c51SChris Mason int slot; 131300ec4c51SChris Mason int i; 131400ec4c51SChris Mason int free_space; 131500ec4c51SChris Mason int push_space = 0; 131600ec4c51SChris Mason int push_items = 0; 13170783fcfcSChris Mason struct btrfs_item *item; 13187518a238SChris Mason u32 left_nritems; 13197518a238SChris Mason u32 right_nritems; 132054aa1f4dSChris Mason int ret; 132100ec4c51SChris Mason 132200ec4c51SChris Mason slot = path->slots[1]; 132300ec4c51SChris Mason if (!path->nodes[1]) { 132400ec4c51SChris Mason return 1; 132500ec4c51SChris Mason } 132600ec4c51SChris Mason upper = path->nodes[1]; 1327e20d96d6SChris Mason upper_node = btrfs_buffer_node(upper); 1328e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&upper_node->header) - 1) { 132900ec4c51SChris Mason return 1; 133000ec4c51SChris Mason } 1331e20d96d6SChris Mason right_buf = read_tree_block(root, 1332e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1)); 1333e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 1334123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 13350783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 1336234b63a0SChris Mason btrfs_block_release(root, right_buf); 133700ec4c51SChris Mason return 1; 133800ec4c51SChris Mason } 133902217ed2SChris Mason /* cow and double check */ 134054aa1f4dSChris Mason ret = btrfs_cow_block(trans, root, right_buf, upper, 134154aa1f4dSChris Mason slot + 1, &right_buf); 134254aa1f4dSChris Mason if (ret) { 134354aa1f4dSChris Mason btrfs_block_release(root, right_buf); 134454aa1f4dSChris Mason return 1; 134554aa1f4dSChris Mason } 1346e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 1347123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 13480783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 1349234b63a0SChris Mason btrfs_block_release(root, right_buf); 135002217ed2SChris Mason return 1; 135102217ed2SChris Mason } 135202217ed2SChris Mason 13537518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 1354a429e513SChris Mason if (left_nritems == 0) { 1355a429e513SChris Mason btrfs_block_release(root, right_buf); 1356a429e513SChris Mason return 1; 1357a429e513SChris Mason } 1358a429e513SChris Mason for (i = left_nritems - 1; i >= 1; i--) { 135900ec4c51SChris Mason item = left->items + i; 136000ec4c51SChris Mason if (path->slots[0] == i) 136100ec4c51SChris Mason push_space += data_size + sizeof(*item); 13620783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 13630783fcfcSChris Mason free_space) 136400ec4c51SChris Mason break; 136500ec4c51SChris Mason push_items++; 13660783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 136700ec4c51SChris Mason } 136800ec4c51SChris Mason if (push_items == 0) { 1369234b63a0SChris Mason btrfs_block_release(root, right_buf); 137000ec4c51SChris Mason return 1; 137100ec4c51SChris Mason } 1372a429e513SChris Mason if (push_items == left_nritems) 1373a429e513SChris Mason WARN_ON(1); 13747518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 137500ec4c51SChris Mason /* push left to right */ 13760783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 1377123abc88SChris Mason push_space -= leaf_data_end(root, left); 137800ec4c51SChris Mason /* make room in the right data area */ 1379d6025579SChris Mason btrfs_memmove(root, right, btrfs_leaf_data(right) + 1380d6025579SChris Mason leaf_data_end(root, right) - push_space, 1381d6025579SChris Mason btrfs_leaf_data(right) + 1382d6025579SChris Mason leaf_data_end(root, right), BTRFS_LEAF_DATA_SIZE(root) - 1383d6025579SChris Mason leaf_data_end(root, right)); 138400ec4c51SChris Mason /* copy from the left data area */ 1385d6025579SChris Mason btrfs_memcpy(root, right, btrfs_leaf_data(right) + 1386d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1387d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 1388d6025579SChris Mason push_space); 1389d6025579SChris Mason btrfs_memmove(root, right, right->items + push_items, right->items, 13900783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 139100ec4c51SChris Mason /* copy the items from left to right */ 1392d6025579SChris Mason btrfs_memcpy(root, right, right->items, left->items + 1393d6025579SChris Mason left_nritems - push_items, 13940783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 139500ec4c51SChris Mason 139600ec4c51SChris Mason /* update the item pointers */ 13977518a238SChris Mason right_nritems += push_items; 13987518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 1399123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 14007518a238SChris Mason for (i = 0; i < right_nritems; i++) { 14010783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 14020783fcfcSChris Mason btrfs_item_size(right->items + i)); 14030783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 140400ec4c51SChris Mason } 14057518a238SChris Mason left_nritems -= push_items; 14067518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 140700ec4c51SChris Mason 1408d6025579SChris Mason btrfs_mark_buffer_dirty(left_buf); 1409d6025579SChris Mason btrfs_mark_buffer_dirty(right_buf); 1410a429e513SChris Mason 1411d6025579SChris Mason btrfs_memcpy(root, upper_node, &upper_node->ptrs[slot + 1].key, 1412e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 1413d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 141402217ed2SChris Mason 141500ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 14167518a238SChris Mason if (path->slots[0] >= left_nritems) { 14177518a238SChris Mason path->slots[0] -= left_nritems; 1418234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 141900ec4c51SChris Mason path->nodes[0] = right_buf; 142000ec4c51SChris Mason path->slots[1] += 1; 142100ec4c51SChris Mason } else { 1422234b63a0SChris Mason btrfs_block_release(root, right_buf); 142300ec4c51SChris Mason } 1424098f59c2SChris Mason if (path->nodes[1]) 1425098f59c2SChris Mason check_node(root, path, 1); 142600ec4c51SChris Mason return 0; 142700ec4c51SChris Mason } 142800ec4c51SChris Mason /* 142974123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 143074123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 143174123bd7SChris Mason */ 1432e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 1433e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1434be0e5c09SChris Mason { 1435e20d96d6SChris Mason struct buffer_head *right_buf = path->nodes[0]; 1436e20d96d6SChris Mason struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf); 1437e20d96d6SChris Mason struct buffer_head *t; 1438234b63a0SChris Mason struct btrfs_leaf *left; 1439be0e5c09SChris Mason int slot; 1440be0e5c09SChris Mason int i; 1441be0e5c09SChris Mason int free_space; 1442be0e5c09SChris Mason int push_space = 0; 1443be0e5c09SChris Mason int push_items = 0; 14440783fcfcSChris Mason struct btrfs_item *item; 14457518a238SChris Mason u32 old_left_nritems; 1446aa5d6bedSChris Mason int ret = 0; 1447aa5d6bedSChris Mason int wret; 1448be0e5c09SChris Mason 1449be0e5c09SChris Mason slot = path->slots[1]; 1450be0e5c09SChris Mason if (slot == 0) { 1451be0e5c09SChris Mason return 1; 1452be0e5c09SChris Mason } 1453be0e5c09SChris Mason if (!path->nodes[1]) { 1454be0e5c09SChris Mason return 1; 1455be0e5c09SChris Mason } 1456e20d96d6SChris Mason t = read_tree_block(root, 1457e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1)); 1458e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 1459123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 14600783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 1461234b63a0SChris Mason btrfs_block_release(root, t); 1462be0e5c09SChris Mason return 1; 1463be0e5c09SChris Mason } 146402217ed2SChris Mason 146502217ed2SChris Mason /* cow and double check */ 146654aa1f4dSChris Mason ret = btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); 146754aa1f4dSChris Mason if (ret) { 146854aa1f4dSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 1469252c38f0SYan btrfs_block_release(root, t); 147054aa1f4dSChris Mason return 1; 147154aa1f4dSChris Mason } 1472e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 1473123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 14740783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 1475234b63a0SChris Mason btrfs_block_release(root, t); 147602217ed2SChris Mason return 1; 147702217ed2SChris Mason } 147802217ed2SChris Mason 1479a429e513SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 1480a429e513SChris Mason btrfs_block_release(root, t); 1481a429e513SChris Mason return 1; 1482a429e513SChris Mason } 1483a429e513SChris Mason 1484a429e513SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header) - 1; i++) { 1485be0e5c09SChris Mason item = right->items + i; 1486be0e5c09SChris Mason if (path->slots[0] == i) 1487be0e5c09SChris Mason push_space += data_size + sizeof(*item); 14880783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 14890783fcfcSChris Mason free_space) 1490be0e5c09SChris Mason break; 1491be0e5c09SChris Mason push_items++; 14920783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 1493be0e5c09SChris Mason } 1494be0e5c09SChris Mason if (push_items == 0) { 1495234b63a0SChris Mason btrfs_block_release(root, t); 1496be0e5c09SChris Mason return 1; 1497be0e5c09SChris Mason } 1498a429e513SChris Mason if (push_items == btrfs_header_nritems(&right->header)) 1499a429e513SChris Mason WARN_ON(1); 1500be0e5c09SChris Mason /* push data from right to left */ 1501d6025579SChris Mason btrfs_memcpy(root, left, left->items + 1502d6025579SChris Mason btrfs_header_nritems(&left->header), 15030783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 1504123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 15050783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 1506d6025579SChris Mason btrfs_memcpy(root, left, btrfs_leaf_data(left) + 1507d6025579SChris Mason leaf_data_end(root, left) - push_space, 1508123abc88SChris Mason btrfs_leaf_data(right) + 1509123abc88SChris Mason btrfs_item_offset(right->items + push_items - 1), 1510be0e5c09SChris Mason push_space); 15117518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 1512eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 1513eb60ceacSChris Mason 1514be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 1515123abc88SChris Mason u32 ioff = btrfs_item_offset(left->items + i); 1516123abc88SChris Mason btrfs_set_item_offset(left->items + i, ioff - 1517123abc88SChris Mason (BTRFS_LEAF_DATA_SIZE(root) - 15180783fcfcSChris Mason btrfs_item_offset(left->items + 15190783fcfcSChris Mason old_left_nritems - 1))); 1520be0e5c09SChris Mason } 15217518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 1522be0e5c09SChris Mason 1523be0e5c09SChris Mason /* fixup right node */ 15240783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 1525123abc88SChris Mason leaf_data_end(root, right); 1526d6025579SChris Mason btrfs_memmove(root, right, btrfs_leaf_data(right) + 1527d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1528d6025579SChris Mason btrfs_leaf_data(right) + 1529123abc88SChris Mason leaf_data_end(root, right), push_space); 1530d6025579SChris Mason btrfs_memmove(root, right, right->items, right->items + push_items, 15317518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 15320783fcfcSChris Mason sizeof(struct btrfs_item)); 15337518a238SChris Mason btrfs_set_header_nritems(&right->header, 15347518a238SChris Mason btrfs_header_nritems(&right->header) - 15357518a238SChris Mason push_items); 1536123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1537eb60ceacSChris Mason 15387518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 15390783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 15400783fcfcSChris Mason btrfs_item_size(right->items + i)); 15410783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 1542be0e5c09SChris Mason } 1543eb60ceacSChris Mason 1544d6025579SChris Mason btrfs_mark_buffer_dirty(t); 1545d6025579SChris Mason btrfs_mark_buffer_dirty(right_buf); 1546098f59c2SChris Mason 1547e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); 1548aa5d6bedSChris Mason if (wret) 1549aa5d6bedSChris Mason ret = wret; 1550be0e5c09SChris Mason 1551be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1552be0e5c09SChris Mason if (path->slots[0] < push_items) { 1553be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1554234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1555eb60ceacSChris Mason path->nodes[0] = t; 1556be0e5c09SChris Mason path->slots[1] -= 1; 1557be0e5c09SChris Mason } else { 1558234b63a0SChris Mason btrfs_block_release(root, t); 1559be0e5c09SChris Mason path->slots[0] -= push_items; 1560be0e5c09SChris Mason } 1561eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1562098f59c2SChris Mason if (path->nodes[1]) 1563098f59c2SChris Mason check_node(root, path, 1); 1564aa5d6bedSChris Mason return ret; 1565be0e5c09SChris Mason } 1566be0e5c09SChris Mason 156774123bd7SChris Mason /* 156874123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 156974123bd7SChris Mason * available for the resulting leaf level of the path. 1570aa5d6bedSChris Mason * 1571aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 157274123bd7SChris Mason */ 1573e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1574d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 1575d4dbff95SChris Mason struct btrfs_path *path, int data_size) 1576be0e5c09SChris Mason { 1577e20d96d6SChris Mason struct buffer_head *l_buf; 1578234b63a0SChris Mason struct btrfs_leaf *l; 15797518a238SChris Mason u32 nritems; 1580eb60ceacSChris Mason int mid; 1581eb60ceacSChris Mason int slot; 1582234b63a0SChris Mason struct btrfs_leaf *right; 1583e20d96d6SChris Mason struct buffer_head *right_buffer; 15840783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1585be0e5c09SChris Mason int data_copy_size; 1586be0e5c09SChris Mason int rt_data_off; 1587be0e5c09SChris Mason int i; 1588d4dbff95SChris Mason int ret = 0; 1589aa5d6bedSChris Mason int wret; 1590d4dbff95SChris Mason int double_split = 0; 1591d4dbff95SChris Mason struct btrfs_disk_key disk_key; 1592be0e5c09SChris Mason 159340689478SChris Mason /* first try to make some room by pushing left and right */ 1594e089f05cSChris Mason wret = push_leaf_left(trans, root, path, data_size); 1595eaee50e8SChris Mason if (wret < 0) 1596eaee50e8SChris Mason return wret; 1597eaee50e8SChris Mason if (wret) { 1598e089f05cSChris Mason wret = push_leaf_right(trans, root, path, data_size); 1599eaee50e8SChris Mason if (wret < 0) 1600eaee50e8SChris Mason return wret; 1601eaee50e8SChris Mason } 1602eb60ceacSChris Mason l_buf = path->nodes[0]; 1603e20d96d6SChris Mason l = btrfs_buffer_leaf(l_buf); 1604aa5d6bedSChris Mason 1605aa5d6bedSChris Mason /* did the pushes work? */ 1606123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1607123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1608be0e5c09SChris Mason return 0; 1609aa5d6bedSChris Mason 16105c680ed6SChris Mason if (!path->nodes[1]) { 1611e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 16125c680ed6SChris Mason if (ret) 16135c680ed6SChris Mason return ret; 16145c680ed6SChris Mason } 1615eb60ceacSChris Mason slot = path->slots[0]; 16167518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1617eb60ceacSChris Mason mid = (nritems + 1)/ 2; 161854aa1f4dSChris Mason 16196702ed49SChris Mason right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr, 0); 162054aa1f4dSChris Mason if (IS_ERR(right_buffer)) 162154aa1f4dSChris Mason return PTR_ERR(right_buffer); 162254aa1f4dSChris Mason 1623e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buffer); 1624123abc88SChris Mason memset(&right->header, 0, sizeof(right->header)); 16257eccb903SChris Mason btrfs_set_header_blocknr(&right->header, bh_blocknr(right_buffer)); 16267f5c1516SChris Mason btrfs_set_header_generation(&right->header, trans->transid); 16274d775673SChris Mason btrfs_set_header_owner(&right->header, root->root_key.objectid); 16287518a238SChris Mason btrfs_set_header_level(&right->header, 0); 16293eb0314dSChris Mason memcpy(right->header.fsid, root->fs_info->disk_super->fsid, 16303eb0314dSChris Mason sizeof(right->header.fsid)); 1631d4dbff95SChris Mason if (mid <= slot) { 1632d4dbff95SChris Mason if (nritems == 1 || 1633d4dbff95SChris Mason leaf_space_used(l, mid, nritems - mid) + space_needed > 1634d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 1635d4dbff95SChris Mason if (slot >= nritems) { 1636d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 1637d4dbff95SChris Mason btrfs_set_header_nritems(&right->header, 0); 1638d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1639d4dbff95SChris Mason &disk_key, 16407eccb903SChris Mason bh_blocknr(right_buffer), 1641d4dbff95SChris Mason path->slots[1] + 1, 1); 1642d4dbff95SChris Mason if (wret) 1643d4dbff95SChris Mason ret = wret; 1644d4dbff95SChris Mason btrfs_block_release(root, path->nodes[0]); 1645d4dbff95SChris Mason path->nodes[0] = right_buffer; 1646d4dbff95SChris Mason path->slots[0] = 0; 1647d4dbff95SChris Mason path->slots[1] += 1; 1648d4dbff95SChris Mason return ret; 1649d4dbff95SChris Mason } 1650d4dbff95SChris Mason mid = slot; 1651d4dbff95SChris Mason double_split = 1; 1652d4dbff95SChris Mason } 1653d4dbff95SChris Mason } else { 1654d4dbff95SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1655d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 1656d4dbff95SChris Mason if (slot == 0) { 1657d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 1658d4dbff95SChris Mason btrfs_set_header_nritems(&right->header, 0); 1659d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1660d4dbff95SChris Mason &disk_key, 16617eccb903SChris Mason bh_blocknr(right_buffer), 1662098f59c2SChris Mason path->slots[1], 1); 1663d4dbff95SChris Mason if (wret) 1664d4dbff95SChris Mason ret = wret; 1665d4dbff95SChris Mason btrfs_block_release(root, path->nodes[0]); 1666d4dbff95SChris Mason path->nodes[0] = right_buffer; 1667d4dbff95SChris Mason path->slots[0] = 0; 1668a429e513SChris Mason if (path->slots[1] == 0) { 1669a429e513SChris Mason wret = fixup_low_keys(trans, root, 1670a429e513SChris Mason path, &disk_key, 1); 1671a429e513SChris Mason if (wret) 1672a429e513SChris Mason ret = wret; 1673a429e513SChris Mason } 1674d4dbff95SChris Mason return ret; 1675d4dbff95SChris Mason } 1676d4dbff95SChris Mason mid = slot; 1677d4dbff95SChris Mason double_split = 1; 1678d4dbff95SChris Mason } 1679d4dbff95SChris Mason } 1680d4dbff95SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 1681123abc88SChris Mason data_copy_size = btrfs_item_end(l->items + mid) - 1682123abc88SChris Mason leaf_data_end(root, l); 1683d6025579SChris Mason btrfs_memcpy(root, right, right->items, l->items + mid, 16840783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1685d6025579SChris Mason btrfs_memcpy(root, right, 1686d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1687123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1688123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 1689123abc88SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1690123abc88SChris Mason btrfs_item_end(l->items + mid); 169174123bd7SChris Mason 16920783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1693123abc88SChris Mason u32 ioff = btrfs_item_offset(right->items + i); 16940783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 16950783fcfcSChris Mason } 169674123bd7SChris Mason 16977518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1698aa5d6bedSChris Mason ret = 0; 1699e089f05cSChris Mason wret = insert_ptr(trans, root, path, &right->items[0].key, 17007eccb903SChris Mason bh_blocknr(right_buffer), path->slots[1] + 1, 1); 1701aa5d6bedSChris Mason if (wret) 1702aa5d6bedSChris Mason ret = wret; 1703d6025579SChris Mason btrfs_mark_buffer_dirty(right_buffer); 1704d6025579SChris Mason btrfs_mark_buffer_dirty(l_buf); 1705eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1706be0e5c09SChris Mason if (mid <= slot) { 1707234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1708eb60ceacSChris Mason path->nodes[0] = right_buffer; 1709be0e5c09SChris Mason path->slots[0] -= mid; 1710be0e5c09SChris Mason path->slots[1] += 1; 1711eb60ceacSChris Mason } else 1712234b63a0SChris Mason btrfs_block_release(root, right_buffer); 1713eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1714098f59c2SChris Mason check_node(root, path, 1); 1715d4dbff95SChris Mason 1716d4dbff95SChris Mason if (!double_split) 1717d4dbff95SChris Mason return ret; 17186702ed49SChris Mason right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr, 0); 171954aa1f4dSChris Mason if (IS_ERR(right_buffer)) 172054aa1f4dSChris Mason return PTR_ERR(right_buffer); 172154aa1f4dSChris Mason 1722d4dbff95SChris Mason right = btrfs_buffer_leaf(right_buffer); 1723d4dbff95SChris Mason memset(&right->header, 0, sizeof(right->header)); 17247eccb903SChris Mason btrfs_set_header_blocknr(&right->header, bh_blocknr(right_buffer)); 1725d4dbff95SChris Mason btrfs_set_header_generation(&right->header, trans->transid); 17264d775673SChris Mason btrfs_set_header_owner(&right->header, root->root_key.objectid); 1727d4dbff95SChris Mason btrfs_set_header_level(&right->header, 0); 17283eb0314dSChris Mason memcpy(right->header.fsid, root->fs_info->disk_super->fsid, 17293eb0314dSChris Mason sizeof(right->header.fsid)); 1730d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 1731d4dbff95SChris Mason btrfs_set_header_nritems(&right->header, 0); 1732d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1733d4dbff95SChris Mason &disk_key, 17347eccb903SChris Mason bh_blocknr(right_buffer), 1735d4dbff95SChris Mason path->slots[1], 1); 1736d4dbff95SChris Mason if (wret) 1737d4dbff95SChris Mason ret = wret; 1738a429e513SChris Mason if (path->slots[1] == 0) { 1739a429e513SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 1740a429e513SChris Mason if (wret) 1741a429e513SChris Mason ret = wret; 1742a429e513SChris Mason } 1743d4dbff95SChris Mason btrfs_block_release(root, path->nodes[0]); 1744d4dbff95SChris Mason path->nodes[0] = right_buffer; 1745d4dbff95SChris Mason path->slots[0] = 0; 1746d4dbff95SChris Mason check_node(root, path, 1); 1747d4dbff95SChris Mason check_leaf(root, path, 0); 1748be0e5c09SChris Mason return ret; 1749be0e5c09SChris Mason } 1750be0e5c09SChris Mason 1751b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans, 1752b18c6685SChris Mason struct btrfs_root *root, 1753b18c6685SChris Mason struct btrfs_path *path, 1754b18c6685SChris Mason u32 new_size) 1755b18c6685SChris Mason { 1756b18c6685SChris Mason int ret = 0; 1757b18c6685SChris Mason int slot; 1758b18c6685SChris Mason int slot_orig; 1759b18c6685SChris Mason struct btrfs_leaf *leaf; 1760b18c6685SChris Mason struct buffer_head *leaf_buf; 1761b18c6685SChris Mason u32 nritems; 1762b18c6685SChris Mason unsigned int data_end; 1763b18c6685SChris Mason unsigned int old_data_start; 1764b18c6685SChris Mason unsigned int old_size; 1765b18c6685SChris Mason unsigned int size_diff; 1766b18c6685SChris Mason int i; 1767b18c6685SChris Mason 1768b18c6685SChris Mason slot_orig = path->slots[0]; 1769b18c6685SChris Mason leaf_buf = path->nodes[0]; 1770b18c6685SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 1771b18c6685SChris Mason 1772b18c6685SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1773b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 1774b18c6685SChris Mason 1775b18c6685SChris Mason slot = path->slots[0]; 1776b18c6685SChris Mason old_data_start = btrfs_item_offset(leaf->items + slot); 1777b18c6685SChris Mason old_size = btrfs_item_size(leaf->items + slot); 1778b18c6685SChris Mason BUG_ON(old_size <= new_size); 1779b18c6685SChris Mason size_diff = old_size - new_size; 1780b18c6685SChris Mason 1781b18c6685SChris Mason BUG_ON(slot < 0); 1782b18c6685SChris Mason BUG_ON(slot >= nritems); 1783b18c6685SChris Mason 1784b18c6685SChris Mason /* 1785b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1786b18c6685SChris Mason */ 1787b18c6685SChris Mason /* first correct the data pointers */ 1788b18c6685SChris Mason for (i = slot; i < nritems; i++) { 1789b18c6685SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 1790b18c6685SChris Mason btrfs_set_item_offset(leaf->items + i, 1791b18c6685SChris Mason ioff + size_diff); 1792b18c6685SChris Mason } 1793b18c6685SChris Mason /* shift the data */ 1794b18c6685SChris Mason btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 1795b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 1796b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 1797b18c6685SChris Mason btrfs_set_item_size(leaf->items + slot, new_size); 1798b18c6685SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 1799b18c6685SChris Mason 1800b18c6685SChris Mason ret = 0; 1801b18c6685SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1802b18c6685SChris Mason BUG(); 1803b18c6685SChris Mason check_leaf(root, path, 0); 1804b18c6685SChris Mason return ret; 1805b18c6685SChris Mason } 1806b18c6685SChris Mason 18076567e837SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root 18086567e837SChris Mason *root, struct btrfs_path *path, u32 data_size) 18096567e837SChris Mason { 18106567e837SChris Mason int ret = 0; 18116567e837SChris Mason int slot; 18126567e837SChris Mason int slot_orig; 18136567e837SChris Mason struct btrfs_leaf *leaf; 18146567e837SChris Mason struct buffer_head *leaf_buf; 18156567e837SChris Mason u32 nritems; 18166567e837SChris Mason unsigned int data_end; 18176567e837SChris Mason unsigned int old_data; 18186567e837SChris Mason unsigned int old_size; 18196567e837SChris Mason int i; 18206567e837SChris Mason 18216567e837SChris Mason slot_orig = path->slots[0]; 18226567e837SChris Mason leaf_buf = path->nodes[0]; 18236567e837SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 18246567e837SChris Mason 18256567e837SChris Mason nritems = btrfs_header_nritems(&leaf->header); 18266567e837SChris Mason data_end = leaf_data_end(root, leaf); 18276567e837SChris Mason 18286567e837SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) 18296567e837SChris Mason BUG(); 18306567e837SChris Mason slot = path->slots[0]; 18316567e837SChris Mason old_data = btrfs_item_end(leaf->items + slot); 18326567e837SChris Mason 18336567e837SChris Mason BUG_ON(slot < 0); 18346567e837SChris Mason BUG_ON(slot >= nritems); 18356567e837SChris Mason 18366567e837SChris Mason /* 18376567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 18386567e837SChris Mason */ 18396567e837SChris Mason /* first correct the data pointers */ 18406567e837SChris Mason for (i = slot; i < nritems; i++) { 18416567e837SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 18426567e837SChris Mason btrfs_set_item_offset(leaf->items + i, 18436567e837SChris Mason ioff - data_size); 18446567e837SChris Mason } 18456567e837SChris Mason /* shift the data */ 18466567e837SChris Mason btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 18476567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 18486567e837SChris Mason data_end, old_data - data_end); 18496567e837SChris Mason data_end = old_data; 18506567e837SChris Mason old_size = btrfs_item_size(leaf->items + slot); 18516567e837SChris Mason btrfs_set_item_size(leaf->items + slot, old_size + data_size); 18526567e837SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 18536567e837SChris Mason 18546567e837SChris Mason ret = 0; 18556567e837SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 18566567e837SChris Mason BUG(); 18576567e837SChris Mason check_leaf(root, path, 0); 18586567e837SChris Mason return ret; 18596567e837SChris Mason } 18606567e837SChris Mason 186174123bd7SChris Mason /* 186274123bd7SChris Mason * Given a key and some data, insert an item into the tree. 186374123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 186474123bd7SChris Mason */ 1865e089f05cSChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1866e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_key 1867e089f05cSChris Mason *cpu_key, u32 data_size) 1868be0e5c09SChris Mason { 1869aa5d6bedSChris Mason int ret = 0; 1870be0e5c09SChris Mason int slot; 1871eb60ceacSChris Mason int slot_orig; 1872234b63a0SChris Mason struct btrfs_leaf *leaf; 1873e20d96d6SChris Mason struct buffer_head *leaf_buf; 18747518a238SChris Mason u32 nritems; 1875be0e5c09SChris Mason unsigned int data_end; 1876e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1877e2fa7227SChris Mason 1878e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1879be0e5c09SChris Mason 188074123bd7SChris Mason /* create a root if there isn't one */ 18815c680ed6SChris Mason if (!root->node) 1882cfaa7295SChris Mason BUG(); 1883e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 1884eb60ceacSChris Mason if (ret == 0) { 1885f0930a37SChris Mason return -EEXIST; 1886aa5d6bedSChris Mason } 1887ed2ff2cbSChris Mason if (ret < 0) 1888ed2ff2cbSChris Mason goto out; 1889be0e5c09SChris Mason 189062e2749eSChris Mason slot_orig = path->slots[0]; 189162e2749eSChris Mason leaf_buf = path->nodes[0]; 1892e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 189374123bd7SChris Mason 18947518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1895123abc88SChris Mason data_end = leaf_data_end(root, leaf); 1896eb60ceacSChris Mason 1897123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 1898d4dbff95SChris Mason sizeof(struct btrfs_item) + data_size) { 1899be0e5c09SChris Mason BUG(); 1900d4dbff95SChris Mason } 190162e2749eSChris Mason slot = path->slots[0]; 1902eb60ceacSChris Mason BUG_ON(slot < 0); 1903be0e5c09SChris Mason if (slot != nritems) { 1904be0e5c09SChris Mason int i; 19050783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1906be0e5c09SChris Mason 1907be0e5c09SChris Mason /* 1908be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1909be0e5c09SChris Mason */ 1910be0e5c09SChris Mason /* first correct the data pointers */ 19110783fcfcSChris Mason for (i = slot; i < nritems; i++) { 1912123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 19130783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 19140783fcfcSChris Mason ioff - data_size); 19150783fcfcSChris Mason } 1916be0e5c09SChris Mason 1917be0e5c09SChris Mason /* shift the items */ 1918d6025579SChris Mason btrfs_memmove(root, leaf, leaf->items + slot + 1, 1919d6025579SChris Mason leaf->items + slot, 19200783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1921be0e5c09SChris Mason 1922be0e5c09SChris Mason /* shift the data */ 1923d6025579SChris Mason btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 1924d6025579SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 1925be0e5c09SChris Mason data_end, old_data - data_end); 1926be0e5c09SChris Mason data_end = old_data; 1927be0e5c09SChris Mason } 192862e2749eSChris Mason /* setup the item for the new data */ 1929d6025579SChris Mason btrfs_memcpy(root, leaf, &leaf->items[slot].key, &disk_key, 1930e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 19310783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 19320783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 19337518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1934d6025579SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 1935aa5d6bedSChris Mason 1936aa5d6bedSChris Mason ret = 0; 19378e19f2cdSChris Mason if (slot == 0) 1938e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 1939aa5d6bedSChris Mason 1940123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1941be0e5c09SChris Mason BUG(); 194262e2749eSChris Mason check_leaf(root, path, 0); 1943ed2ff2cbSChris Mason out: 194462e2749eSChris Mason return ret; 194562e2749eSChris Mason } 194662e2749eSChris Mason 194762e2749eSChris Mason /* 194862e2749eSChris Mason * Given a key and some data, insert an item into the tree. 194962e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 195062e2749eSChris Mason */ 1951e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 1952e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 1953e089f05cSChris Mason data_size) 195462e2749eSChris Mason { 195562e2749eSChris Mason int ret = 0; 19562c90e5d6SChris Mason struct btrfs_path *path; 195762e2749eSChris Mason u8 *ptr; 195862e2749eSChris Mason 19592c90e5d6SChris Mason path = btrfs_alloc_path(); 19602c90e5d6SChris Mason BUG_ON(!path); 19612c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 196262e2749eSChris Mason if (!ret) { 19632c90e5d6SChris Mason ptr = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), 19642c90e5d6SChris Mason path->slots[0], u8); 19652c90e5d6SChris Mason btrfs_memcpy(root, path->nodes[0]->b_data, 1966d6025579SChris Mason ptr, data, data_size); 19672c90e5d6SChris Mason btrfs_mark_buffer_dirty(path->nodes[0]); 196862e2749eSChris Mason } 19692c90e5d6SChris Mason btrfs_free_path(path); 1970aa5d6bedSChris Mason return ret; 1971be0e5c09SChris Mason } 1972be0e5c09SChris Mason 197374123bd7SChris Mason /* 19745de08d7dSChris Mason * delete the pointer from a given node. 197574123bd7SChris Mason * 197674123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 197774123bd7SChris Mason * continuing all the way the root if required. The root is converted into 197874123bd7SChris Mason * a leaf if all the nodes are emptied. 197974123bd7SChris Mason */ 1980e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1981e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 1982be0e5c09SChris Mason { 1983234b63a0SChris Mason struct btrfs_node *node; 1984e20d96d6SChris Mason struct buffer_head *parent = path->nodes[level]; 19857518a238SChris Mason u32 nritems; 1986aa5d6bedSChris Mason int ret = 0; 1987bb803951SChris Mason int wret; 1988be0e5c09SChris Mason 1989e20d96d6SChris Mason node = btrfs_buffer_node(parent); 19907518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1991be0e5c09SChris Mason if (slot != nritems -1) { 1992d6025579SChris Mason btrfs_memmove(root, node, node->ptrs + slot, 1993d6025579SChris Mason node->ptrs + slot + 1, 1994d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 1995d6025579SChris Mason (nritems - slot - 1)); 1996be0e5c09SChris Mason } 19977518a238SChris Mason nritems--; 19987518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 19997518a238SChris Mason if (nritems == 0 && parent == root->node) { 2000e20d96d6SChris Mason struct btrfs_header *header = btrfs_buffer_header(root->node); 2001e20d96d6SChris Mason BUG_ON(btrfs_header_level(header) != 1); 2002eb60ceacSChris Mason /* just turn the root into a leaf and break */ 2003e20d96d6SChris Mason btrfs_set_header_level(header, 0); 2004bb803951SChris Mason } else if (slot == 0) { 2005e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, 2006123abc88SChris Mason level + 1); 20070f70abe2SChris Mason if (wret) 20080f70abe2SChris Mason ret = wret; 2009be0e5c09SChris Mason } 2010d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 2011aa5d6bedSChris Mason return ret; 2012be0e5c09SChris Mason } 2013be0e5c09SChris Mason 201474123bd7SChris Mason /* 201574123bd7SChris Mason * delete the item at the leaf level in path. If that empties 201674123bd7SChris Mason * the leaf, remove it from the tree 201774123bd7SChris Mason */ 2018e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2019e089f05cSChris Mason struct btrfs_path *path) 2020be0e5c09SChris Mason { 2021be0e5c09SChris Mason int slot; 2022234b63a0SChris Mason struct btrfs_leaf *leaf; 2023e20d96d6SChris Mason struct buffer_head *leaf_buf; 2024be0e5c09SChris Mason int doff; 2025be0e5c09SChris Mason int dsize; 2026aa5d6bedSChris Mason int ret = 0; 2027aa5d6bedSChris Mason int wret; 20287518a238SChris Mason u32 nritems; 2029be0e5c09SChris Mason 2030eb60ceacSChris Mason leaf_buf = path->nodes[0]; 2031e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 20324920c9acSChris Mason slot = path->slots[0]; 20330783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 20340783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 20357518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 2036be0e5c09SChris Mason 20377518a238SChris Mason if (slot != nritems - 1) { 2038be0e5c09SChris Mason int i; 2039123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 2040d6025579SChris Mason btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 2041d6025579SChris Mason data_end + dsize, 2042123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 2043be0e5c09SChris Mason doff - data_end); 20440783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 2045123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 20460783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 20470783fcfcSChris Mason } 2048d6025579SChris Mason btrfs_memmove(root, leaf, leaf->items + slot, 2049d6025579SChris Mason leaf->items + slot + 1, 20500783fcfcSChris Mason sizeof(struct btrfs_item) * 20517518a238SChris Mason (nritems - slot - 1)); 2052be0e5c09SChris Mason } 20537518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 20547518a238SChris Mason nritems--; 205574123bd7SChris Mason /* delete the leaf if we've emptied it */ 20567518a238SChris Mason if (nritems == 0) { 2057eb60ceacSChris Mason if (leaf_buf == root->node) { 20587518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 20599a8dd150SChris Mason } else { 2060e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 2061d6025579SChris Mason wait_on_buffer(leaf_buf); 2062e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 2063aa5d6bedSChris Mason if (wret) 2064aa5d6bedSChris Mason ret = wret; 2065e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 20667eccb903SChris Mason bh_blocknr(leaf_buf), 1, 1); 20670f70abe2SChris Mason if (wret) 20680f70abe2SChris Mason ret = wret; 20699a8dd150SChris Mason } 2070be0e5c09SChris Mason } else { 20717518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 2072aa5d6bedSChris Mason if (slot == 0) { 2073e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 2074aa5d6bedSChris Mason &leaf->items[0].key, 1); 2075aa5d6bedSChris Mason if (wret) 2076aa5d6bedSChris Mason ret = wret; 2077aa5d6bedSChris Mason } 2078aa5d6bedSChris Mason 207974123bd7SChris Mason /* delete the leaf if it is mostly empty */ 2080123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 2081be0e5c09SChris Mason /* push_leaf_left fixes the path. 2082be0e5c09SChris Mason * make sure the path still points to our leaf 2083be0e5c09SChris Mason * for possible call to del_ptr below 2084be0e5c09SChris Mason */ 20854920c9acSChris Mason slot = path->slots[1]; 2086e20d96d6SChris Mason get_bh(leaf_buf); 2087e089f05cSChris Mason wret = push_leaf_left(trans, root, path, 1); 208854aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 2089aa5d6bedSChris Mason ret = wret; 2090f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 20917518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 2092e089f05cSChris Mason wret = push_leaf_right(trans, root, path, 1); 209354aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 2094aa5d6bedSChris Mason ret = wret; 2095aa5d6bedSChris Mason } 20967518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 20977eccb903SChris Mason u64 blocknr = bh_blocknr(leaf_buf); 2098e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 2099d6025579SChris Mason wait_on_buffer(leaf_buf); 2100e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 2101aa5d6bedSChris Mason if (wret) 2102aa5d6bedSChris Mason ret = wret; 2103234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 2104e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 2105e089f05cSChris Mason 1, 1); 21060f70abe2SChris Mason if (wret) 21070f70abe2SChris Mason ret = wret; 21085de08d7dSChris Mason } else { 2109d6025579SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 2110234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 2111be0e5c09SChris Mason } 2112d5719762SChris Mason } else { 2113d6025579SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 2114be0e5c09SChris Mason } 21159a8dd150SChris Mason } 2116aa5d6bedSChris Mason return ret; 21179a8dd150SChris Mason } 21189a8dd150SChris Mason 211997571fd0SChris Mason /* 212097571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 21210f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 21220f70abe2SChris Mason * returns < 0 on io errors. 212397571fd0SChris Mason */ 2124234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 2125d97e63b6SChris Mason { 2126d97e63b6SChris Mason int slot; 2127d97e63b6SChris Mason int level = 1; 2128d97e63b6SChris Mason u64 blocknr; 2129e20d96d6SChris Mason struct buffer_head *c; 2130e20d96d6SChris Mason struct btrfs_node *c_node; 2131e20d96d6SChris Mason struct buffer_head *next = NULL; 2132d97e63b6SChris Mason 2133234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 2134d97e63b6SChris Mason if (!path->nodes[level]) 21350f70abe2SChris Mason return 1; 2136d97e63b6SChris Mason slot = path->slots[level] + 1; 2137d97e63b6SChris Mason c = path->nodes[level]; 2138e20d96d6SChris Mason c_node = btrfs_buffer_node(c); 2139e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&c_node->header)) { 2140d97e63b6SChris Mason level++; 2141d97e63b6SChris Mason continue; 2142d97e63b6SChris Mason } 2143e20d96d6SChris Mason blocknr = btrfs_node_blockptr(c_node, slot); 2144cfaa7295SChris Mason if (next) 2145234b63a0SChris Mason btrfs_block_release(root, next); 21466702ed49SChris Mason if (path->reada) 21476702ed49SChris Mason reada_for_search(root, path, level, slot); 2148d97e63b6SChris Mason next = read_tree_block(root, blocknr); 2149d97e63b6SChris Mason break; 2150d97e63b6SChris Mason } 2151d97e63b6SChris Mason path->slots[level] = slot; 2152d97e63b6SChris Mason while(1) { 2153d97e63b6SChris Mason level--; 2154d97e63b6SChris Mason c = path->nodes[level]; 2155234b63a0SChris Mason btrfs_block_release(root, c); 2156d97e63b6SChris Mason path->nodes[level] = next; 2157d97e63b6SChris Mason path->slots[level] = 0; 2158d97e63b6SChris Mason if (!level) 2159d97e63b6SChris Mason break; 21606702ed49SChris Mason if (path->reada) 216132020611SYan reada_for_search(root, path, level, 0); 21621d4f8a0cSChris Mason next = read_tree_block(root, 2163e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(next), 0)); 2164d97e63b6SChris Mason } 2165d97e63b6SChris Mason return 0; 2166d97e63b6SChris Mason } 2167