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 195f39d397SChris Mason #include <linux/highmem.h> 20eb60ceacSChris Mason #include "ctree.h" 21eb60ceacSChris Mason #include "disk-io.h" 227f5c1516SChris Mason #include "transaction.h" 235f39d397SChris Mason #include "print-tree.h" 249a8dd150SChris Mason 25e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 26e089f05cSChris Mason *root, struct btrfs_path *path, int level); 27e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 28d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 29d4dbff95SChris Mason struct btrfs_path *path, int data_size); 305f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans, 315f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *dst, 325f39d397SChris Mason struct extent_buffer *src); 335f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 345f39d397SChris Mason struct btrfs_root *root, 355f39d397SChris Mason struct extent_buffer *dst_buf, 365f39d397SChris Mason struct extent_buffer *src_buf); 37e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 38e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 39d97e63b6SChris Mason 40df24a2b9SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 41df24a2b9SChris Mason { 42df24a2b9SChris Mason memset(p, 0, sizeof(*p)); 43df24a2b9SChris Mason } 44df24a2b9SChris Mason 452c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 462c90e5d6SChris Mason { 47df24a2b9SChris Mason struct btrfs_path *path; 48df24a2b9SChris Mason path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS); 492cc58cf2SChris Mason if (path) { 50df24a2b9SChris Mason btrfs_init_path(path); 512cc58cf2SChris Mason path->reada = 1; 522cc58cf2SChris Mason } 53df24a2b9SChris Mason return path; 542c90e5d6SChris Mason } 552c90e5d6SChris Mason 562c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 572c90e5d6SChris Mason { 58df24a2b9SChris Mason btrfs_release_path(NULL, p); 592c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 602c90e5d6SChris Mason } 612c90e5d6SChris Mason 62234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 63eb60ceacSChris Mason { 64eb60ceacSChris Mason int i; 65234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 66eb60ceacSChris Mason if (!p->nodes[i]) 67eb60ceacSChris Mason break; 685f39d397SChris Mason free_extent_buffer(p->nodes[i]); 69eb60ceacSChris Mason } 70aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 71eb60ceacSChris Mason } 72eb60ceacSChris Mason 735f39d397SChris Mason static int __btrfs_cow_block(struct btrfs_trans_handle *trans, 745f39d397SChris Mason struct btrfs_root *root, 755f39d397SChris Mason struct extent_buffer *buf, 765f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 775f39d397SChris Mason struct extent_buffer **cow_ret, 785f39d397SChris Mason u64 search_start, u64 empty_size) 796702ed49SChris Mason { 805f39d397SChris Mason struct extent_buffer *cow; 816702ed49SChris Mason int ret = 0; 826702ed49SChris Mason int different_trans = 0; 836702ed49SChris Mason 846702ed49SChris Mason WARN_ON(root->ref_cows && trans->transid != root->last_trans); 855f39d397SChris Mason 866702ed49SChris Mason cow = btrfs_alloc_free_block(trans, root, search_start, empty_size); 876702ed49SChris Mason if (IS_ERR(cow)) 886702ed49SChris Mason return PTR_ERR(cow); 896702ed49SChris Mason 905f39d397SChris Mason if (buf->len != root->sectorsize || cow->len != root->sectorsize) 916702ed49SChris Mason WARN_ON(1); 926702ed49SChris Mason 935f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 945f39d397SChris Mason btrfs_set_header_blocknr(cow, extent_buffer_blocknr(cow)); 955f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 965f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 976702ed49SChris Mason 985f39d397SChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 995f39d397SChris Mason if (btrfs_header_generation(buf) != trans->transid) { 1006702ed49SChris Mason different_trans = 1; 1016702ed49SChris Mason ret = btrfs_inc_ref(trans, root, buf); 1026702ed49SChris Mason if (ret) 1036702ed49SChris Mason return ret; 1046702ed49SChris Mason } else { 1056702ed49SChris Mason clean_tree_block(trans, root, buf); 1066702ed49SChris Mason } 1076702ed49SChris Mason 1086702ed49SChris Mason if (buf == root->node) { 1096702ed49SChris Mason root->node = cow; 1105f39d397SChris Mason extent_buffer_get(cow); 1116702ed49SChris Mason if (buf != root->commit_root) { 1125f39d397SChris Mason btrfs_free_extent(trans, root, 1135f39d397SChris Mason extent_buffer_blocknr(buf), 1, 1); 1146702ed49SChris Mason } 1155f39d397SChris Mason free_extent_buffer(buf); 1166702ed49SChris Mason } else { 1175f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 1185f39d397SChris Mason extent_buffer_blocknr(cow)); 1196702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 1205f39d397SChris Mason WARN_ON(btrfs_header_generation(parent) != trans->transid); 1215f39d397SChris Mason btrfs_free_extent(trans, root, extent_buffer_blocknr(buf),1,1); 1226702ed49SChris Mason } 1235f39d397SChris Mason free_extent_buffer(buf); 1246702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 1256702ed49SChris Mason *cow_ret = cow; 1266702ed49SChris Mason return 0; 1276702ed49SChris Mason } 1286702ed49SChris Mason 1295f39d397SChris Mason int btrfs_cow_block(struct btrfs_trans_handle *trans, 1305f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 1315f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 1325f39d397SChris Mason struct extent_buffer **cow_ret) 13302217ed2SChris Mason { 1346702ed49SChris Mason u64 search_start; 135ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 136ccd467d6SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 137ccd467d6SChris Mason root->fs_info->running_transaction->transid); 138ccd467d6SChris Mason WARN_ON(1); 139ccd467d6SChris Mason } 140ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 141ccd467d6SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 142ccd467d6SChris Mason root->fs_info->generation); 143ccd467d6SChris Mason WARN_ON(1); 144ccd467d6SChris Mason } 1455f39d397SChris Mason if (btrfs_header_generation(buf) == trans->transid) { 14602217ed2SChris Mason *cow_ret = buf; 14702217ed2SChris Mason return 0; 14802217ed2SChris Mason } 1496702ed49SChris Mason 1505f39d397SChris Mason search_start = extent_buffer_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 1645f39d397SChris Mason #if 0 1655f39d397SChris Mason static int should_defrag_leaf(struct extent_buffer *eb) 1662cc58cf2SChris Mason { 1675f39d397SChris Mason return 0; 1685f39d397SChris Mason struct btrfs_leaf *leaf = btrfs_buffer_leaf(eb); 1692cc58cf2SChris Mason struct btrfs_disk_key *key; 1702cc58cf2SChris Mason u32 nritems; 1712cc58cf2SChris Mason 1722cc58cf2SChris Mason if (buffer_defrag(bh)) 1732cc58cf2SChris Mason return 1; 1742cc58cf2SChris Mason 1752cc58cf2SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1762cc58cf2SChris Mason if (nritems == 0) 1772cc58cf2SChris Mason return 0; 1782cc58cf2SChris Mason 1792cc58cf2SChris Mason key = &leaf->items[0].key; 1802cc58cf2SChris Mason if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY) 1812cc58cf2SChris Mason return 1; 1822cc58cf2SChris Mason 1832cc58cf2SChris Mason key = &leaf->items[nritems-1].key; 1842cc58cf2SChris Mason if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY) 1852cc58cf2SChris Mason return 1; 1862cc58cf2SChris Mason if (nritems > 4) { 1872cc58cf2SChris Mason key = &leaf->items[nritems/2].key; 1882cc58cf2SChris Mason if (btrfs_disk_key_type(key) == BTRFS_DIR_ITEM_KEY) 1892cc58cf2SChris Mason return 1; 1902cc58cf2SChris Mason } 1912cc58cf2SChris Mason return 0; 1922cc58cf2SChris Mason } 1935f39d397SChris Mason #endif 1942cc58cf2SChris Mason 1956702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 1965f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 197e9d0b13bSChris Mason int cache_only, u64 *last_ret) 1986702ed49SChris Mason { 1995f39d397SChris Mason return 0; 2005f39d397SChris Mason #if 0 2016702ed49SChris Mason struct btrfs_node *parent_node; 2025f39d397SChris Mason struct extent_buffer *cur_eb; 2035f39d397SChris Mason struct extent_buffer *tmp_eb; 2046702ed49SChris Mason u64 blocknr; 205e9d0b13bSChris Mason u64 search_start = *last_ret; 206e9d0b13bSChris Mason u64 last_block = 0; 2076702ed49SChris Mason u64 other; 2086702ed49SChris Mason u32 parent_nritems; 2096702ed49SChris Mason int start_slot; 2106702ed49SChris Mason int end_slot; 2116702ed49SChris Mason int i; 2126702ed49SChris Mason int err = 0; 213f2183bdeSChris Mason int parent_level; 2146702ed49SChris Mason 2156702ed49SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 2166702ed49SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 2176702ed49SChris Mason root->fs_info->running_transaction->transid); 2186702ed49SChris Mason WARN_ON(1); 2196702ed49SChris Mason } 2206702ed49SChris Mason if (trans->transid != root->fs_info->generation) { 2216702ed49SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 2226702ed49SChris Mason root->fs_info->generation); 2236702ed49SChris Mason WARN_ON(1); 2246702ed49SChris Mason } 22586479a04SChris Mason if (buffer_defrag_done(parent)) 22686479a04SChris Mason return 0; 22786479a04SChris Mason 2286702ed49SChris Mason parent_node = btrfs_buffer_node(parent); 2296702ed49SChris Mason parent_nritems = btrfs_header_nritems(&parent_node->header); 230f2183bdeSChris Mason parent_level = btrfs_header_level(&parent_node->header); 2316702ed49SChris Mason 2326702ed49SChris Mason start_slot = 0; 2336702ed49SChris Mason end_slot = parent_nritems; 2346702ed49SChris Mason 2356702ed49SChris Mason if (parent_nritems == 1) 2366702ed49SChris Mason return 0; 2376702ed49SChris Mason 2386702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 2396702ed49SChris Mason int close = 1; 2406702ed49SChris Mason blocknr = btrfs_node_blockptr(parent_node, i); 241e9d0b13bSChris Mason if (last_block == 0) 242e9d0b13bSChris Mason last_block = blocknr; 2436702ed49SChris Mason if (i > 0) { 2446702ed49SChris Mason other = btrfs_node_blockptr(parent_node, i - 1); 2456702ed49SChris Mason close = close_blocks(blocknr, other); 2466702ed49SChris Mason } 2476702ed49SChris Mason if (close && i < end_slot - 1) { 2486702ed49SChris Mason other = btrfs_node_blockptr(parent_node, i + 1); 2496702ed49SChris Mason close = close_blocks(blocknr, other); 2506702ed49SChris Mason } 251e9d0b13bSChris Mason if (close) { 252e9d0b13bSChris Mason last_block = blocknr; 2536702ed49SChris Mason continue; 254e9d0b13bSChris Mason } 2556702ed49SChris Mason 2566702ed49SChris Mason cur_bh = btrfs_find_tree_block(root, blocknr); 2576702ed49SChris Mason if (!cur_bh || !buffer_uptodate(cur_bh) || 2582cc58cf2SChris Mason buffer_locked(cur_bh) || 2592cc58cf2SChris Mason (parent_level != 1 && !buffer_defrag(cur_bh)) || 2602cc58cf2SChris Mason (parent_level == 1 && !should_defrag_leaf(cur_bh))) { 2616702ed49SChris Mason if (cache_only) { 2626702ed49SChris Mason brelse(cur_bh); 2636702ed49SChris Mason continue; 2646702ed49SChris Mason } 265f2183bdeSChris Mason if (!cur_bh || !buffer_uptodate(cur_bh) || 266f2183bdeSChris Mason buffer_locked(cur_bh)) { 2676702ed49SChris Mason brelse(cur_bh); 2686702ed49SChris Mason cur_bh = read_tree_block(root, blocknr); 2696702ed49SChris Mason } 270f2183bdeSChris Mason } 271e9d0b13bSChris Mason if (search_start == 0) 272e9d0b13bSChris Mason search_start = last_block & ~((u64)65535); 273e9d0b13bSChris Mason 2746702ed49SChris Mason err = __btrfs_cow_block(trans, root, cur_bh, parent, i, 2756702ed49SChris Mason &tmp_bh, search_start, 2766702ed49SChris Mason min(8, end_slot - i)); 277252c38f0SYan if (err) { 278252c38f0SYan brelse(cur_bh); 2796702ed49SChris Mason break; 280252c38f0SYan } 2816702ed49SChris Mason search_start = bh_blocknr(tmp_bh); 282f2183bdeSChris Mason *last_ret = search_start; 283f2183bdeSChris Mason if (parent_level == 1) 284f2183bdeSChris Mason clear_buffer_defrag(tmp_bh); 28586479a04SChris Mason set_buffer_defrag_done(tmp_bh); 2866702ed49SChris Mason brelse(tmp_bh); 2876702ed49SChris Mason } 2886702ed49SChris Mason return err; 2895f39d397SChris Mason #endif 2906702ed49SChris Mason } 2916702ed49SChris Mason 29274123bd7SChris Mason /* 29374123bd7SChris Mason * The leaf data grows from end-to-front in the node. 29474123bd7SChris Mason * this returns the address of the start of the last item, 29574123bd7SChris Mason * which is the stop of the leaf data stack 29674123bd7SChris Mason */ 297123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 2985f39d397SChris Mason struct extent_buffer *leaf) 299be0e5c09SChris Mason { 3005f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 301be0e5c09SChris Mason if (nr == 0) 302123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 3035f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 304be0e5c09SChris Mason } 305be0e5c09SChris Mason 30674123bd7SChris Mason /* 30774123bd7SChris Mason * compare two keys in a memcmp fashion 30874123bd7SChris Mason */ 3099aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 310be0e5c09SChris Mason { 311e2fa7227SChris Mason struct btrfs_key k1; 312e2fa7227SChris Mason 313e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 314e2fa7227SChris Mason 315e2fa7227SChris Mason if (k1.objectid > k2->objectid) 316be0e5c09SChris Mason return 1; 317e2fa7227SChris Mason if (k1.objectid < k2->objectid) 318be0e5c09SChris Mason return -1; 3195f39d397SChris Mason if (k1.type > k2->type) 320f254e52cSChris Mason return 1; 3215f39d397SChris Mason if (k1.type < k2->type) 322f254e52cSChris Mason return -1; 32370b2befdSChris Mason if (k1.offset > k2->offset) 32470b2befdSChris Mason return 1; 32570b2befdSChris Mason if (k1.offset < k2->offset) 32670b2befdSChris Mason return -1; 327be0e5c09SChris Mason return 0; 328be0e5c09SChris Mason } 32974123bd7SChris Mason 330123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 331123abc88SChris Mason int level) 332aa5d6bedSChris Mason { 3335f39d397SChris Mason struct extent_buffer *parent = NULL; 3345f39d397SChris Mason struct extent_buffer *node = path->nodes[level]; 3355f39d397SChris Mason struct btrfs_disk_key parent_key; 3365f39d397SChris Mason struct btrfs_disk_key node_key; 337aa5d6bedSChris Mason int parent_slot; 3388d7be552SChris Mason int slot; 3398d7be552SChris Mason struct btrfs_key cpukey; 3405f39d397SChris Mason u32 nritems = btrfs_header_nritems(node); 341aa5d6bedSChris Mason 342aa5d6bedSChris Mason if (path->nodes[level + 1]) 3435f39d397SChris Mason parent = path->nodes[level + 1]; 344a1f39630SAneesh 3458d7be552SChris Mason slot = path->slots[level]; 3467518a238SChris Mason BUG_ON(nritems == 0); 3477518a238SChris Mason if (parent) { 348a1f39630SAneesh parent_slot = path->slots[level + 1]; 3495f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 3505f39d397SChris Mason btrfs_node_key(node, &node_key, 0); 3515f39d397SChris Mason BUG_ON(memcmp(&parent_key, &node_key, 352e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 3531d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 3545f39d397SChris Mason btrfs_header_blocknr(node)); 355aa5d6bedSChris Mason } 356123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 3578d7be552SChris Mason if (slot != 0) { 3585f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot - 1); 3595f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 3605f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) <= 0); 3618d7be552SChris Mason } 3628d7be552SChris Mason if (slot < nritems - 1) { 3635f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot + 1); 3645f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 3655f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) >= 0); 366aa5d6bedSChris Mason } 367aa5d6bedSChris Mason return 0; 368aa5d6bedSChris Mason } 369aa5d6bedSChris Mason 370123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 371123abc88SChris Mason int level) 372aa5d6bedSChris Mason { 3735f39d397SChris Mason struct extent_buffer *leaf = path->nodes[level]; 3745f39d397SChris Mason struct extent_buffer *parent = NULL; 375aa5d6bedSChris Mason int parent_slot; 3768d7be552SChris Mason struct btrfs_key cpukey; 3775f39d397SChris Mason struct btrfs_disk_key parent_key; 3785f39d397SChris Mason struct btrfs_disk_key leaf_key; 3795f39d397SChris Mason int slot = path->slots[0]; 3808d7be552SChris Mason 3815f39d397SChris Mason u32 nritems = btrfs_header_nritems(leaf); 382aa5d6bedSChris Mason 383aa5d6bedSChris Mason if (path->nodes[level + 1]) 3845f39d397SChris Mason parent = path->nodes[level + 1]; 3857518a238SChris Mason 3867518a238SChris Mason if (nritems == 0) 3877518a238SChris Mason return 0; 3887518a238SChris Mason 3897518a238SChris Mason if (parent) { 390a1f39630SAneesh parent_slot = path->slots[level + 1]; 3915f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 3925f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, 0); 3936702ed49SChris Mason 3945f39d397SChris Mason BUG_ON(memcmp(&parent_key, &leaf_key, 395e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 3961d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 3975f39d397SChris Mason btrfs_header_blocknr(leaf)); 398aa5d6bedSChris Mason } 3995f39d397SChris Mason #if 0 4005f39d397SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 4015f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, i + 1); 4025f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, i); 4035f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) >= 0) { 4045f39d397SChris Mason btrfs_print_leaf(root, leaf); 4055f39d397SChris Mason printk("slot %d offset bad key\n", i); 4065f39d397SChris Mason BUG_ON(1); 4075f39d397SChris Mason } 4085f39d397SChris Mason if (btrfs_item_offset_nr(leaf, i) != 4095f39d397SChris Mason btrfs_item_end_nr(leaf, i + 1)) { 4105f39d397SChris Mason btrfs_print_leaf(root, leaf); 4115f39d397SChris Mason printk("slot %d offset bad\n", i); 4125f39d397SChris Mason BUG_ON(1); 4135f39d397SChris Mason } 4145f39d397SChris Mason if (i == 0) { 4155f39d397SChris Mason if (btrfs_item_offset_nr(leaf, i) + 4165f39d397SChris Mason btrfs_item_size_nr(leaf, i) != 4175f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 4185f39d397SChris Mason btrfs_print_leaf(root, leaf); 4195f39d397SChris Mason printk("slot %d first offset bad\n", i); 4205f39d397SChris Mason BUG_ON(1); 4215f39d397SChris Mason } 4225f39d397SChris Mason } 4235f39d397SChris Mason } 4245f39d397SChris Mason if (nritems > 0) { 4255f39d397SChris Mason if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) { 4265f39d397SChris Mason btrfs_print_leaf(root, leaf); 4275f39d397SChris Mason printk("slot %d bad size \n", nritems - 1); 4285f39d397SChris Mason BUG_ON(1); 4295f39d397SChris Mason } 4305f39d397SChris Mason } 4315f39d397SChris Mason #endif 4325f39d397SChris Mason if (slot != 0 && slot < nritems - 1) { 4335f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 4345f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1); 4355f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) <= 0) { 4365f39d397SChris Mason btrfs_print_leaf(root, leaf); 4375f39d397SChris Mason printk("slot %d offset bad key\n", slot); 4385f39d397SChris Mason BUG_ON(1); 4395f39d397SChris Mason } 4405f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot - 1) != 4415f39d397SChris Mason btrfs_item_end_nr(leaf, slot)) { 4425f39d397SChris Mason btrfs_print_leaf(root, leaf); 4435f39d397SChris Mason printk("slot %d offset bad\n", slot); 4445f39d397SChris Mason BUG_ON(1); 4455f39d397SChris Mason } 446aa5d6bedSChris Mason } 4478d7be552SChris Mason if (slot < nritems - 1) { 4485f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 4495f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1); 4505f39d397SChris Mason BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0); 4515f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot) != 4525f39d397SChris Mason btrfs_item_end_nr(leaf, slot + 1)) { 4535f39d397SChris Mason btrfs_print_leaf(root, leaf); 4545f39d397SChris Mason printk("slot %d offset bad\n", slot); 4555f39d397SChris Mason BUG_ON(1); 456aa5d6bedSChris Mason } 4575f39d397SChris Mason } 4585f39d397SChris Mason BUG_ON(btrfs_item_offset_nr(leaf, 0) + 4595f39d397SChris Mason btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root)); 460aa5d6bedSChris Mason return 0; 461aa5d6bedSChris Mason } 462aa5d6bedSChris Mason 463123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 464123abc88SChris Mason int level) 465aa5d6bedSChris Mason { 4665f39d397SChris Mason struct extent_buffer *buf = path->nodes[level]; 4675f39d397SChris Mason char fsid[BTRFS_FSID_SIZE]; 4685f39d397SChris Mason 4695f39d397SChris Mason read_extent_buffer(buf, fsid, (unsigned long)btrfs_header_fsid(buf), 4705f39d397SChris Mason BTRFS_FSID_SIZE); 4715f39d397SChris Mason 4725f39d397SChris Mason if (memcmp(fsid, root->fs_info->fsid, BTRFS_FSID_SIZE)) { 4735f39d397SChris Mason int i = 0; 4745f39d397SChris Mason printk("warning bad block %Lu\n", buf->start); 4755f39d397SChris Mason if (!btrfs_buffer_uptodate(buf)) { 4765f39d397SChris Mason WARN_ON(1); 4775f39d397SChris Mason } 4785f39d397SChris Mason for (i = 0; i < BTRFS_FSID_SIZE; i++) { 4795f39d397SChris Mason printk("%x:%x ", root->fs_info->fsid[i], fsid[i]); 4805f39d397SChris Mason } 4815f39d397SChris Mason printk("\n"); 4825f39d397SChris Mason // BUG(); 4835f39d397SChris Mason } 484aa5d6bedSChris Mason if (level == 0) 485123abc88SChris Mason return check_leaf(root, path, level); 486123abc88SChris Mason return check_node(root, path, level); 487aa5d6bedSChris Mason } 488aa5d6bedSChris Mason 48974123bd7SChris Mason /* 4905f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 4915f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 4925f39d397SChris Mason * 49374123bd7SChris Mason * the slot in the array is returned via slot, and it points to 49474123bd7SChris Mason * the place where you would insert key if it is not found in 49574123bd7SChris Mason * the array. 49674123bd7SChris Mason * 49774123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 49874123bd7SChris Mason */ 4995f39d397SChris Mason static int generic_bin_search(struct extent_buffer *eb, unsigned long p, 5005f39d397SChris Mason int item_size, struct btrfs_key *key, 501be0e5c09SChris Mason int max, int *slot) 502be0e5c09SChris Mason { 503be0e5c09SChris Mason int low = 0; 504be0e5c09SChris Mason int high = max; 505be0e5c09SChris Mason int mid; 506be0e5c09SChris Mason int ret; 507e2fa7227SChris Mason struct btrfs_disk_key *tmp; 5085f39d397SChris Mason struct btrfs_disk_key unaligned; 5095f39d397SChris Mason unsigned long offset; 5105f39d397SChris Mason char *map_token = NULL; 5115f39d397SChris Mason char *kaddr = NULL; 5125f39d397SChris Mason unsigned long map_start = 0; 5135f39d397SChris Mason unsigned long map_len = 0; 514be0e5c09SChris Mason 515be0e5c09SChris Mason while(low < high) { 516be0e5c09SChris Mason mid = (low + high) / 2; 5175f39d397SChris Mason offset = p + mid * item_size; 5185f39d397SChris Mason 5195f39d397SChris Mason if (!map_token || offset < map_start || 5205f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 5215f39d397SChris Mason map_start + map_len) { 5225f39d397SChris Mason if (map_token) 5235f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 5245f39d397SChris Mason map_extent_buffer(eb, offset, &map_token, &kaddr, 5255f39d397SChris Mason &map_start, &map_len, KM_USER0); 5265f39d397SChris Mason 5275f39d397SChris Mason } 5285f39d397SChris Mason if (offset + sizeof(struct btrfs_disk_key) > 5295f39d397SChris Mason map_start + map_len) { 5305f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 5315f39d397SChris Mason read_extent_buffer(eb, &unaligned, 5325f39d397SChris Mason offset, sizeof(unaligned)); 5335f39d397SChris Mason map_token = NULL; 5345f39d397SChris Mason tmp = &unaligned; 5355f39d397SChris Mason } else { 5365f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 5375f39d397SChris Mason map_start); 5385f39d397SChris Mason } 539be0e5c09SChris Mason ret = comp_keys(tmp, key); 540be0e5c09SChris Mason 541be0e5c09SChris Mason if (ret < 0) 542be0e5c09SChris Mason low = mid + 1; 543be0e5c09SChris Mason else if (ret > 0) 544be0e5c09SChris Mason high = mid; 545be0e5c09SChris Mason else { 546be0e5c09SChris Mason *slot = mid; 5475f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 548be0e5c09SChris Mason return 0; 549be0e5c09SChris Mason } 550be0e5c09SChris Mason } 551be0e5c09SChris Mason *slot = low; 5525f39d397SChris Mason if (map_token) 5535f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 554be0e5c09SChris Mason return 1; 555be0e5c09SChris Mason } 556be0e5c09SChris Mason 55797571fd0SChris Mason /* 55897571fd0SChris Mason * simple bin_search frontend that does the right thing for 55997571fd0SChris Mason * leaves vs nodes 56097571fd0SChris Mason */ 5615f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 5625f39d397SChris Mason int level, int *slot) 563be0e5c09SChris Mason { 5645f39d397SChris Mason if (level == 0) { 5655f39d397SChris Mason return generic_bin_search(eb, 5665f39d397SChris Mason offsetof(struct btrfs_leaf, items), 5670783fcfcSChris Mason sizeof(struct btrfs_item), 5685f39d397SChris Mason key, btrfs_header_nritems(eb), 5697518a238SChris Mason slot); 570be0e5c09SChris Mason } else { 5715f39d397SChris Mason return generic_bin_search(eb, 5725f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 573123abc88SChris Mason sizeof(struct btrfs_key_ptr), 5745f39d397SChris Mason key, btrfs_header_nritems(eb), 5757518a238SChris Mason slot); 576be0e5c09SChris Mason } 577be0e5c09SChris Mason return -1; 578be0e5c09SChris Mason } 579be0e5c09SChris Mason 5805f39d397SChris Mason static struct extent_buffer *read_node_slot(struct btrfs_root *root, 5815f39d397SChris Mason struct extent_buffer *parent, int slot) 582bb803951SChris Mason { 583bb803951SChris Mason if (slot < 0) 584bb803951SChris Mason return NULL; 5855f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 586bb803951SChris Mason return NULL; 5875f39d397SChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot)); 588bb803951SChris Mason } 589bb803951SChris Mason 590e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 591e089f05cSChris Mason *root, struct btrfs_path *path, int level) 592bb803951SChris Mason { 5935f39d397SChris Mason struct extent_buffer *right = NULL; 5945f39d397SChris Mason struct extent_buffer *mid; 5955f39d397SChris Mason struct extent_buffer *left = NULL; 5965f39d397SChris Mason struct extent_buffer *parent = NULL; 597bb803951SChris Mason int ret = 0; 598bb803951SChris Mason int wret; 599bb803951SChris Mason int pslot; 600bb803951SChris Mason int orig_slot = path->slots[level]; 60154aa1f4dSChris Mason int err_on_enospc = 0; 60279f95c82SChris Mason u64 orig_ptr; 603bb803951SChris Mason 604bb803951SChris Mason if (level == 0) 605bb803951SChris Mason return 0; 606bb803951SChris Mason 6075f39d397SChris Mason mid = path->nodes[level]; 6081d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 60979f95c82SChris Mason 610234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 6115f39d397SChris Mason parent = path->nodes[level + 1]; 612bb803951SChris Mason pslot = path->slots[level + 1]; 613bb803951SChris Mason 61440689478SChris Mason /* 61540689478SChris Mason * deal with the case where there is only one pointer in the root 61640689478SChris Mason * by promoting the node below to a root 61740689478SChris Mason */ 6185f39d397SChris Mason if (!parent) { 6195f39d397SChris Mason struct extent_buffer *child; 6205f39d397SChris Mason u64 blocknr = extent_buffer_blocknr(mid); 621bb803951SChris Mason 6225f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 623bb803951SChris Mason return 0; 624bb803951SChris Mason 625bb803951SChris Mason /* promote the child to a root */ 6265f39d397SChris Mason child = read_node_slot(root, mid, 0); 627bb803951SChris Mason BUG_ON(!child); 628bb803951SChris Mason root->node = child; 629bb803951SChris Mason path->nodes[level] = NULL; 6305f39d397SChris Mason clean_tree_block(trans, root, mid); 6315f39d397SChris Mason wait_on_tree_block_writeback(root, mid); 632bb803951SChris Mason /* once for the path */ 6335f39d397SChris Mason free_extent_buffer(mid); 634bb803951SChris Mason /* once for the root ptr */ 6355f39d397SChris Mason free_extent_buffer(mid); 636e089f05cSChris Mason return btrfs_free_extent(trans, root, blocknr, 1, 1); 637bb803951SChris Mason } 6385f39d397SChris Mason if (btrfs_header_nritems(mid) > 639123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 640bb803951SChris Mason return 0; 641bb803951SChris Mason 6425f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 64354aa1f4dSChris Mason err_on_enospc = 1; 64454aa1f4dSChris Mason 6455f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 6465f39d397SChris Mason if (left) { 6475f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 6485f39d397SChris Mason parent, pslot - 1, &left); 64954aa1f4dSChris Mason if (wret) { 65054aa1f4dSChris Mason ret = wret; 65154aa1f4dSChris Mason goto enospc; 65254aa1f4dSChris Mason } 6532cc58cf2SChris Mason } 6545f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 6555f39d397SChris Mason if (right) { 6565f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 6575f39d397SChris Mason parent, pslot + 1, &right); 6582cc58cf2SChris Mason if (wret) { 6592cc58cf2SChris Mason ret = wret; 6602cc58cf2SChris Mason goto enospc; 6612cc58cf2SChris Mason } 6622cc58cf2SChris Mason } 6632cc58cf2SChris Mason 6642cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 6655f39d397SChris Mason if (left) { 6665f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 6675f39d397SChris Mason wret = push_node_left(trans, root, left, mid); 66879f95c82SChris Mason if (wret < 0) 66979f95c82SChris Mason ret = wret; 6705f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 67154aa1f4dSChris Mason err_on_enospc = 1; 672bb803951SChris Mason } 67379f95c82SChris Mason 67479f95c82SChris Mason /* 67579f95c82SChris Mason * then try to empty the right most buffer into the middle 67679f95c82SChris Mason */ 6775f39d397SChris Mason if (right) { 6785f39d397SChris Mason wret = push_node_left(trans, root, mid, right); 67954aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 68079f95c82SChris Mason ret = wret; 6815f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 6825f39d397SChris Mason u64 blocknr = extent_buffer_blocknr(right); 6835f39d397SChris Mason clean_tree_block(trans, root, right); 6845f39d397SChris Mason wait_on_tree_block_writeback(root, right); 6855f39d397SChris Mason free_extent_buffer(right); 686bb803951SChris Mason right = NULL; 687e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 688e089f05cSChris Mason 1); 689bb803951SChris Mason if (wret) 690bb803951SChris Mason ret = wret; 691e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 692bb803951SChris Mason if (wret) 693bb803951SChris Mason ret = wret; 694bb803951SChris Mason } else { 6955f39d397SChris Mason struct btrfs_disk_key right_key; 6965f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 6975f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 6985f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 699bb803951SChris Mason } 700bb803951SChris Mason } 7015f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 70279f95c82SChris Mason /* 70379f95c82SChris Mason * we're not allowed to leave a node with one item in the 70479f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 70579f95c82SChris Mason * could try to delete the only pointer in this node. 70679f95c82SChris Mason * So, pull some keys from the left. 70779f95c82SChris Mason * There has to be a left pointer at this point because 70879f95c82SChris Mason * otherwise we would have pulled some pointers from the 70979f95c82SChris Mason * right 71079f95c82SChris Mason */ 7115f39d397SChris Mason BUG_ON(!left); 7125f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 71354aa1f4dSChris Mason if (wret < 0) { 71479f95c82SChris Mason ret = wret; 71554aa1f4dSChris Mason goto enospc; 71654aa1f4dSChris Mason } 71779f95c82SChris Mason BUG_ON(wret == 1); 71879f95c82SChris Mason } 7195f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 72079f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 7215f39d397SChris Mason u64 blocknr = extent_buffer_blocknr(mid); 7225f39d397SChris Mason clean_tree_block(trans, root, mid); 7235f39d397SChris Mason wait_on_tree_block_writeback(root, mid); 7245f39d397SChris Mason free_extent_buffer(mid); 725bb803951SChris Mason mid = NULL; 726e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 727bb803951SChris Mason if (wret) 728bb803951SChris Mason ret = wret; 729e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 730bb803951SChris Mason if (wret) 731bb803951SChris Mason ret = wret; 73279f95c82SChris Mason } else { 73379f95c82SChris Mason /* update the parent key to reflect our changes */ 7345f39d397SChris Mason struct btrfs_disk_key mid_key; 7355f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 7365f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 7375f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 73879f95c82SChris Mason } 739bb803951SChris Mason 74079f95c82SChris Mason /* update the path */ 7415f39d397SChris Mason if (left) { 7425f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 7435f39d397SChris Mason extent_buffer_get(left); 7445f39d397SChris Mason path->nodes[level] = left; 745bb803951SChris Mason path->slots[level + 1] -= 1; 746bb803951SChris Mason path->slots[level] = orig_slot; 7475f39d397SChris Mason if (mid) 7485f39d397SChris Mason free_extent_buffer(mid); 749bb803951SChris Mason } else { 7505f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 751bb803951SChris Mason path->slots[level] = orig_slot; 752bb803951SChris Mason } 753bb803951SChris Mason } 75479f95c82SChris Mason /* double check we haven't messed things up */ 755123abc88SChris Mason check_block(root, path, level); 756e20d96d6SChris Mason if (orig_ptr != 7575f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 75879f95c82SChris Mason BUG(); 75954aa1f4dSChris Mason enospc: 7605f39d397SChris Mason if (right) 7615f39d397SChris Mason free_extent_buffer(right); 7625f39d397SChris Mason if (left) 7635f39d397SChris Mason free_extent_buffer(left); 764bb803951SChris Mason return ret; 765bb803951SChris Mason } 766bb803951SChris Mason 767e66f709bSChris Mason /* returns zero if the push worked, non-zero otherwise */ 768e66f709bSChris Mason static int push_nodes_for_insert(struct btrfs_trans_handle *trans, 769e66f709bSChris Mason struct btrfs_root *root, 770e66f709bSChris Mason struct btrfs_path *path, int level) 771e66f709bSChris Mason { 7725f39d397SChris Mason struct extent_buffer *right = NULL; 7735f39d397SChris Mason struct extent_buffer *mid; 7745f39d397SChris Mason struct extent_buffer *left = NULL; 7755f39d397SChris Mason struct extent_buffer *parent = NULL; 776e66f709bSChris Mason int ret = 0; 777e66f709bSChris Mason int wret; 778e66f709bSChris Mason int pslot; 779e66f709bSChris Mason int orig_slot = path->slots[level]; 780e66f709bSChris Mason u64 orig_ptr; 781e66f709bSChris Mason 782e66f709bSChris Mason if (level == 0) 783e66f709bSChris Mason return 1; 784e66f709bSChris Mason 7855f39d397SChris Mason mid = path->nodes[level]; 786e66f709bSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 787e66f709bSChris Mason 788e66f709bSChris Mason if (level < BTRFS_MAX_LEVEL - 1) 7895f39d397SChris Mason parent = path->nodes[level + 1]; 790e66f709bSChris Mason pslot = path->slots[level + 1]; 791e66f709bSChris Mason 7925f39d397SChris Mason if (!parent) 793e66f709bSChris Mason return 1; 794e66f709bSChris Mason 7955f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 796e66f709bSChris Mason 797e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 7985f39d397SChris Mason if (left) { 799e66f709bSChris Mason u32 left_nr; 8005f39d397SChris Mason left_nr = btrfs_header_nritems(left); 80133ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 80233ade1f8SChris Mason wret = 1; 80333ade1f8SChris Mason } else { 8045f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 8055f39d397SChris Mason pslot - 1, &left); 80654aa1f4dSChris Mason if (ret) 80754aa1f4dSChris Mason wret = 1; 80854aa1f4dSChris Mason else { 80954aa1f4dSChris Mason wret = push_node_left(trans, root, 8105f39d397SChris Mason left, mid); 81154aa1f4dSChris Mason } 81233ade1f8SChris Mason } 813e66f709bSChris Mason if (wret < 0) 814e66f709bSChris Mason ret = wret; 815e66f709bSChris Mason if (wret == 0) { 8165f39d397SChris Mason struct btrfs_disk_key disk_key; 817e66f709bSChris Mason orig_slot += left_nr; 8185f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 8195f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 8205f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 8215f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 8225f39d397SChris Mason path->nodes[level] = left; 823e66f709bSChris Mason path->slots[level + 1] -= 1; 824e66f709bSChris Mason path->slots[level] = orig_slot; 8255f39d397SChris Mason free_extent_buffer(mid); 826e66f709bSChris Mason } else { 827e66f709bSChris Mason orig_slot -= 8285f39d397SChris Mason btrfs_header_nritems(left); 829e66f709bSChris Mason path->slots[level] = orig_slot; 8305f39d397SChris Mason free_extent_buffer(left); 831e66f709bSChris Mason } 832e66f709bSChris Mason check_node(root, path, level); 833e66f709bSChris Mason return 0; 834e66f709bSChris Mason } 8355f39d397SChris Mason free_extent_buffer(left); 836e66f709bSChris Mason } 8375f39d397SChris Mason right= read_node_slot(root, parent, pslot + 1); 838e66f709bSChris Mason 839e66f709bSChris Mason /* 840e66f709bSChris Mason * then try to empty the right most buffer into the middle 841e66f709bSChris Mason */ 8425f39d397SChris Mason if (right) { 84333ade1f8SChris Mason u32 right_nr; 8445f39d397SChris Mason right_nr = btrfs_header_nritems(right); 84533ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 84633ade1f8SChris Mason wret = 1; 84733ade1f8SChris Mason } else { 8485f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 8495f39d397SChris Mason parent, pslot + 1, 8505f39d397SChris Mason &right); 85154aa1f4dSChris Mason if (ret) 85254aa1f4dSChris Mason wret = 1; 85354aa1f4dSChris Mason else { 85433ade1f8SChris Mason wret = balance_node_right(trans, root, 8555f39d397SChris Mason right, mid); 85633ade1f8SChris Mason } 85754aa1f4dSChris Mason } 858e66f709bSChris Mason if (wret < 0) 859e66f709bSChris Mason ret = wret; 860e66f709bSChris Mason if (wret == 0) { 8615f39d397SChris Mason struct btrfs_disk_key disk_key; 8625f39d397SChris Mason 8635f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 8645f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 8655f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 8665f39d397SChris Mason 8675f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 8685f39d397SChris Mason path->nodes[level] = right; 869e66f709bSChris Mason path->slots[level + 1] += 1; 870e66f709bSChris Mason path->slots[level] = orig_slot - 8715f39d397SChris Mason btrfs_header_nritems(mid); 8725f39d397SChris Mason free_extent_buffer(mid); 873e66f709bSChris Mason } else { 8745f39d397SChris Mason free_extent_buffer(right); 875e66f709bSChris Mason } 876e66f709bSChris Mason check_node(root, path, level); 877e66f709bSChris Mason return 0; 878e66f709bSChris Mason } 8795f39d397SChris Mason free_extent_buffer(right); 880e66f709bSChris Mason } 881e66f709bSChris Mason check_node(root, path, level); 882e66f709bSChris Mason return 1; 883e66f709bSChris Mason } 884e66f709bSChris Mason 88574123bd7SChris Mason /* 8863c69faecSChris Mason * readahead one full node of leaves 8873c69faecSChris Mason */ 8883c69faecSChris Mason static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, 8896702ed49SChris Mason int level, int slot) 8903c69faecSChris Mason { 8915f39d397SChris Mason struct extent_buffer *node; 8923c69faecSChris Mason int i; 8933c69faecSChris Mason u32 nritems; 8943c69faecSChris Mason u64 blocknr; 8953c69faecSChris Mason u64 search; 8963c69faecSChris Mason u64 cluster_start; 8973c69faecSChris Mason int ret; 8983c69faecSChris Mason int nread = 0; 8993c69faecSChris Mason int direction = path->reada; 9003c69faecSChris Mason struct radix_tree_root found; 9013c69faecSChris Mason unsigned long gang[8]; 9025f39d397SChris Mason struct extent_buffer *eb; 9033c69faecSChris Mason 9046702ed49SChris Mason if (level == 0) 9053c69faecSChris Mason return; 9063c69faecSChris Mason 9076702ed49SChris Mason if (!path->nodes[level]) 9086702ed49SChris Mason return; 9096702ed49SChris Mason 9105f39d397SChris Mason node = path->nodes[level]; 9113c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 9125f39d397SChris Mason eb = btrfs_find_tree_block(root, search); 9135f39d397SChris Mason if (eb) { 9145f39d397SChris Mason free_extent_buffer(eb); 9153c69faecSChris Mason return; 9163c69faecSChris Mason } 9173c69faecSChris Mason 9183c69faecSChris Mason init_bit_radix(&found); 9195f39d397SChris Mason nritems = btrfs_header_nritems(node); 9203c69faecSChris Mason for (i = slot; i < nritems; i++) { 9213c69faecSChris Mason blocknr = btrfs_node_blockptr(node, i); 9223c69faecSChris Mason set_radix_bit(&found, blocknr); 9233c69faecSChris Mason } 9243c69faecSChris Mason if (direction > 0) { 9253c69faecSChris Mason cluster_start = search - 4; 9263c69faecSChris Mason if (cluster_start > search) 9273c69faecSChris Mason cluster_start = 0; 9283c69faecSChris Mason } else 9293c69faecSChris Mason cluster_start = search + 4; 9303c69faecSChris Mason while(1) { 9313c69faecSChris Mason ret = find_first_radix_bit(&found, gang, 0, ARRAY_SIZE(gang)); 9323c69faecSChris Mason if (!ret) 9333c69faecSChris Mason break; 9343c69faecSChris Mason for (i = 0; i < ret; i++) { 9353c69faecSChris Mason blocknr = gang[i]; 9363c69faecSChris Mason clear_radix_bit(&found, blocknr); 9372cc58cf2SChris Mason if (path->reada == 1 && nread > 16) 9383c69faecSChris Mason continue; 939f2183bdeSChris Mason if (close_blocks(cluster_start, blocknr)) { 9403c69faecSChris Mason readahead_tree_block(root, blocknr); 9413c69faecSChris Mason nread++; 9423c69faecSChris Mason cluster_start = blocknr; 9433c69faecSChris Mason } 9443c69faecSChris Mason } 9453c69faecSChris Mason } 9463c69faecSChris Mason } 9473c69faecSChris Mason /* 94874123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 94974123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 95074123bd7SChris Mason * level of the path (level 0) 95174123bd7SChris Mason * 95274123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 953aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 954aa5d6bedSChris Mason * search a negative error number is returned. 95597571fd0SChris Mason * 95697571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 95797571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 95897571fd0SChris Mason * possible) 95974123bd7SChris Mason */ 960e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 961e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 962e089f05cSChris Mason ins_len, int cow) 963be0e5c09SChris Mason { 9645f39d397SChris Mason struct extent_buffer *b; 9653c69faecSChris Mason u64 blocknr; 966be0e5c09SChris Mason int slot; 967be0e5c09SChris Mason int ret; 968be0e5c09SChris Mason int level; 9693c69faecSChris Mason int should_reada = p->reada; 9709f3a7427SChris Mason u8 lowest_level = 0; 9719f3a7427SChris Mason 9726702ed49SChris Mason lowest_level = p->lowest_level; 9736702ed49SChris Mason WARN_ON(lowest_level && ins_len); 97422b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 97522b0ebdaSChris Mason WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex)); 976bb803951SChris Mason again: 977bb803951SChris Mason b = root->node; 9785f39d397SChris Mason extent_buffer_get(b); 979eb60ceacSChris Mason while (b) { 9805f39d397SChris Mason level = btrfs_header_level(b); 98102217ed2SChris Mason if (cow) { 98202217ed2SChris Mason int wret; 983e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 984e20d96d6SChris Mason p->nodes[level + 1], 985e20d96d6SChris Mason p->slots[level + 1], 986252c38f0SYan &b); 98754aa1f4dSChris Mason if (wret) { 9885f39d397SChris Mason free_extent_buffer(b); 98954aa1f4dSChris Mason return wret; 99054aa1f4dSChris Mason } 99102217ed2SChris Mason } 99202217ed2SChris Mason BUG_ON(!cow && ins_len); 9935f39d397SChris Mason if (level != btrfs_header_level(b)) 9942c90e5d6SChris Mason WARN_ON(1); 9955f39d397SChris Mason level = btrfs_header_level(b); 996eb60ceacSChris Mason p->nodes[level] = b; 997123abc88SChris Mason ret = check_block(root, p, level); 998aa5d6bedSChris Mason if (ret) 999aa5d6bedSChris Mason return -1; 10005f39d397SChris Mason ret = bin_search(b, key, level, &slot); 10015f39d397SChris Mason if (level != 0) { 1002be0e5c09SChris Mason if (ret && slot > 0) 1003be0e5c09SChris Mason slot -= 1; 1004be0e5c09SChris Mason p->slots[level] = slot; 10055f39d397SChris Mason if (ins_len > 0 && btrfs_header_nritems(b) >= 1006d4dbff95SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 1007e089f05cSChris Mason int sret = split_node(trans, root, p, level); 10085c680ed6SChris Mason BUG_ON(sret > 0); 10095c680ed6SChris Mason if (sret) 10105c680ed6SChris Mason return sret; 10115c680ed6SChris Mason b = p->nodes[level]; 10125c680ed6SChris Mason slot = p->slots[level]; 1013bb803951SChris Mason } else if (ins_len < 0) { 1014e089f05cSChris Mason int sret = balance_level(trans, root, p, 1015e089f05cSChris Mason level); 1016bb803951SChris Mason if (sret) 1017bb803951SChris Mason return sret; 1018bb803951SChris Mason b = p->nodes[level]; 1019bb803951SChris Mason if (!b) 1020bb803951SChris Mason goto again; 1021bb803951SChris Mason slot = p->slots[level]; 10225f39d397SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 10235c680ed6SChris Mason } 10249f3a7427SChris Mason /* this is only true while dropping a snapshot */ 10259f3a7427SChris Mason if (level == lowest_level) 10269f3a7427SChris Mason break; 10275f39d397SChris Mason blocknr = btrfs_node_blockptr(b, slot); 10286702ed49SChris Mason if (should_reada) 10296702ed49SChris Mason reada_for_search(root, p, level, slot); 10305f39d397SChris Mason b = read_tree_block(root, btrfs_node_blockptr(b, slot)); 1031be0e5c09SChris Mason } else { 1032be0e5c09SChris Mason p->slots[level] = slot; 10335f39d397SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, b) < 10340783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 1035d4dbff95SChris Mason int sret = split_leaf(trans, root, key, 1036d4dbff95SChris Mason p, ins_len); 10375c680ed6SChris Mason BUG_ON(sret > 0); 10385c680ed6SChris Mason if (sret) 10395c680ed6SChris Mason return sret; 10405c680ed6SChris Mason } 1041be0e5c09SChris Mason return ret; 1042be0e5c09SChris Mason } 1043be0e5c09SChris Mason } 1044aa5d6bedSChris Mason return 1; 1045be0e5c09SChris Mason } 1046be0e5c09SChris Mason 104774123bd7SChris Mason /* 104874123bd7SChris Mason * adjust the pointers going up the tree, starting at level 104974123bd7SChris Mason * making sure the right key of each node is points to 'key'. 105074123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 105174123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 105274123bd7SChris Mason * higher levels 1053aa5d6bedSChris Mason * 1054aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 1055aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 105674123bd7SChris Mason */ 10575f39d397SChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, 10585f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 10595f39d397SChris Mason struct btrfs_disk_key *key, int level) 1060be0e5c09SChris Mason { 1061be0e5c09SChris Mason int i; 1062aa5d6bedSChris Mason int ret = 0; 10635f39d397SChris Mason struct extent_buffer *t; 10645f39d397SChris Mason 1065234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1066be0e5c09SChris Mason int tslot = path->slots[i]; 1067eb60ceacSChris Mason if (!path->nodes[i]) 1068be0e5c09SChris Mason break; 10695f39d397SChris Mason t = path->nodes[i]; 10705f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 1071d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 1072be0e5c09SChris Mason if (tslot != 0) 1073be0e5c09SChris Mason break; 1074be0e5c09SChris Mason } 1075aa5d6bedSChris Mason return ret; 1076be0e5c09SChris Mason } 1077be0e5c09SChris Mason 107874123bd7SChris Mason /* 107974123bd7SChris Mason * try to push data from one node into the next node left in the 108079f95c82SChris Mason * tree. 1081aa5d6bedSChris Mason * 1082aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1083aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 108474123bd7SChris Mason */ 1085e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 10865f39d397SChris Mason *root, struct extent_buffer *dst, 10875f39d397SChris Mason struct extent_buffer *src) 1088be0e5c09SChris Mason { 1089be0e5c09SChris Mason int push_items = 0; 1090bb803951SChris Mason int src_nritems; 1091bb803951SChris Mason int dst_nritems; 1092aa5d6bedSChris Mason int ret = 0; 1093be0e5c09SChris Mason 10945f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 10955f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1096123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 109754aa1f4dSChris Mason 1098eb60ceacSChris Mason if (push_items <= 0) { 1099be0e5c09SChris Mason return 1; 1100eb60ceacSChris Mason } 1101be0e5c09SChris Mason 1102be0e5c09SChris Mason if (src_nritems < push_items) 1103be0e5c09SChris Mason push_items = src_nritems; 110479f95c82SChris Mason 11055f39d397SChris Mason copy_extent_buffer(dst, src, 11065f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 11075f39d397SChris Mason btrfs_node_key_ptr_offset(0), 1108123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 11095f39d397SChris Mason 1110bb803951SChris Mason if (push_items < src_nritems) { 11115f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 11125f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 1113e2fa7227SChris Mason (src_nritems - push_items) * 1114123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1115bb803951SChris Mason } 11165f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 11175f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 11185f39d397SChris Mason btrfs_mark_buffer_dirty(src); 11195f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 1120bb803951SChris Mason return ret; 1121be0e5c09SChris Mason } 1122be0e5c09SChris Mason 112397571fd0SChris Mason /* 112479f95c82SChris Mason * try to push data from one node into the next node right in the 112579f95c82SChris Mason * tree. 112679f95c82SChris Mason * 112779f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 112879f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 112979f95c82SChris Mason * 113079f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 113179f95c82SChris Mason */ 11325f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 11335f39d397SChris Mason struct btrfs_root *root, 11345f39d397SChris Mason struct extent_buffer *dst, 11355f39d397SChris Mason struct extent_buffer *src) 113679f95c82SChris Mason { 113779f95c82SChris Mason int push_items = 0; 113879f95c82SChris Mason int max_push; 113979f95c82SChris Mason int src_nritems; 114079f95c82SChris Mason int dst_nritems; 114179f95c82SChris Mason int ret = 0; 114279f95c82SChris Mason 11435f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 11445f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1145123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 11465f39d397SChris Mason if (push_items <= 0) 114779f95c82SChris Mason return 1; 114879f95c82SChris Mason 114979f95c82SChris Mason max_push = src_nritems / 2 + 1; 115079f95c82SChris Mason /* don't try to empty the node */ 1151252c38f0SYan if (max_push >= src_nritems) 115279f95c82SChris Mason return 1; 1153252c38f0SYan 115479f95c82SChris Mason if (max_push < push_items) 115579f95c82SChris Mason push_items = max_push; 115679f95c82SChris Mason 11575f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 11585f39d397SChris Mason btrfs_node_key_ptr_offset(0), 11595f39d397SChris Mason (dst_nritems) * 11605f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 1161d6025579SChris Mason 11625f39d397SChris Mason copy_extent_buffer(dst, src, 11635f39d397SChris Mason btrfs_node_key_ptr_offset(0), 11645f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 1165123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 116679f95c82SChris Mason 11675f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 11685f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 116979f95c82SChris Mason 11705f39d397SChris Mason btrfs_mark_buffer_dirty(src); 11715f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 117279f95c82SChris Mason return ret; 117379f95c82SChris Mason } 117479f95c82SChris Mason 117579f95c82SChris Mason /* 117697571fd0SChris Mason * helper function to insert a new root level in the tree. 117797571fd0SChris Mason * A new node is allocated, and a single item is inserted to 117897571fd0SChris Mason * point to the existing root 1179aa5d6bedSChris Mason * 1180aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 118197571fd0SChris Mason */ 11825f39d397SChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, 11835f39d397SChris Mason struct btrfs_root *root, 11845f39d397SChris Mason struct btrfs_path *path, int level) 118574123bd7SChris Mason { 11865f39d397SChris Mason struct extent_buffer *lower; 11875f39d397SChris Mason struct extent_buffer *c; 11885f39d397SChris Mason struct btrfs_disk_key lower_key; 11895c680ed6SChris Mason 11905c680ed6SChris Mason BUG_ON(path->nodes[level]); 11915c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 11925c680ed6SChris Mason 11935f39d397SChris Mason c = btrfs_alloc_free_block(trans, root, 11945f39d397SChris Mason extent_buffer_blocknr(root->node), 0); 11955f39d397SChris Mason if (IS_ERR(c)) 11965f39d397SChris Mason return PTR_ERR(c); 11975f39d397SChris Mason memset_extent_buffer(c, 0, 0, root->nodesize); 11985f39d397SChris Mason btrfs_set_header_nritems(c, 1); 11995f39d397SChris Mason btrfs_set_header_level(c, level); 12005f39d397SChris Mason btrfs_set_header_blocknr(c, extent_buffer_blocknr(c)); 12015f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 12025f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 12035f39d397SChris Mason lower = path->nodes[level-1]; 1204d5719762SChris Mason 12055f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 12065f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 12075f39d397SChris Mason BTRFS_FSID_SIZE); 12085f39d397SChris Mason if (level == 1) 12095f39d397SChris Mason btrfs_item_key(lower, &lower_key, 0); 12105f39d397SChris Mason else 12115f39d397SChris Mason btrfs_node_key(lower, &lower_key, 0); 12125f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 12135f39d397SChris Mason btrfs_set_node_blockptr(c, 0, extent_buffer_blocknr(lower)); 12145f39d397SChris Mason 12155f39d397SChris Mason btrfs_mark_buffer_dirty(c); 1216d5719762SChris Mason 1217cfaa7295SChris Mason /* the super has an extra ref to root->node */ 12185f39d397SChris Mason free_extent_buffer(root->node); 12195f39d397SChris Mason root->node = c; 12205f39d397SChris Mason extent_buffer_get(c); 12215f39d397SChris Mason path->nodes[level] = c; 122274123bd7SChris Mason path->slots[level] = 0; 122374123bd7SChris Mason return 0; 122474123bd7SChris Mason } 12255c680ed6SChris Mason 12265c680ed6SChris Mason /* 12275c680ed6SChris Mason * worker function to insert a single pointer in a node. 12285c680ed6SChris Mason * the node should have enough room for the pointer already 122997571fd0SChris Mason * 12305c680ed6SChris Mason * slot and level indicate where you want the key to go, and 12315c680ed6SChris Mason * blocknr is the block the key points to. 1232aa5d6bedSChris Mason * 1233aa5d6bedSChris Mason * returns zero on success and < 0 on any error 12345c680ed6SChris Mason */ 1235e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 1236e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 1237e089f05cSChris Mason *key, u64 blocknr, int slot, int level) 12385c680ed6SChris Mason { 12395f39d397SChris Mason struct extent_buffer *lower; 12405c680ed6SChris Mason int nritems; 12415c680ed6SChris Mason 12425c680ed6SChris Mason BUG_ON(!path->nodes[level]); 12435f39d397SChris Mason lower = path->nodes[level]; 12445f39d397SChris Mason nritems = btrfs_header_nritems(lower); 124574123bd7SChris Mason if (slot > nritems) 124674123bd7SChris Mason BUG(); 1247123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 124874123bd7SChris Mason BUG(); 124974123bd7SChris Mason if (slot != nritems) { 12505f39d397SChris Mason memmove_extent_buffer(lower, 12515f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 12525f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 1253123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 125474123bd7SChris Mason } 12555f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 12561d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 12575f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 12585f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 1259098f59c2SChris Mason check_node(root, path, level); 126074123bd7SChris Mason return 0; 126174123bd7SChris Mason } 126274123bd7SChris Mason 126397571fd0SChris Mason /* 126497571fd0SChris Mason * split the node at the specified level in path in two. 126597571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 126697571fd0SChris Mason * 126797571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 126897571fd0SChris Mason * left and right, if either one works, it returns right away. 1269aa5d6bedSChris Mason * 1270aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 127197571fd0SChris Mason */ 1272e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 1273e089f05cSChris Mason *root, struct btrfs_path *path, int level) 1274be0e5c09SChris Mason { 12755f39d397SChris Mason struct extent_buffer *c; 12765f39d397SChris Mason struct extent_buffer *split; 12775f39d397SChris Mason struct btrfs_disk_key disk_key; 1278be0e5c09SChris Mason int mid; 12795c680ed6SChris Mason int ret; 1280aa5d6bedSChris Mason int wret; 12817518a238SChris Mason u32 c_nritems; 1282be0e5c09SChris Mason 12835f39d397SChris Mason c = path->nodes[level]; 12845f39d397SChris Mason if (c == root->node) { 12855c680ed6SChris Mason /* trying to split the root, lets make a new one */ 1286e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 12875c680ed6SChris Mason if (ret) 12885c680ed6SChris Mason return ret; 1289e66f709bSChris Mason } else { 1290e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 12915f39d397SChris Mason c = path->nodes[level]; 12925f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 1293e66f709bSChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 1) 1294e66f709bSChris Mason return 0; 129554aa1f4dSChris Mason if (ret < 0) 129654aa1f4dSChris Mason return ret; 12975c680ed6SChris Mason } 1298e66f709bSChris Mason 12995f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 13005f39d397SChris Mason split = btrfs_alloc_free_block(trans, root, 13015f39d397SChris Mason extent_buffer_blocknr(c), 0); 13025f39d397SChris Mason if (IS_ERR(split)) 13035f39d397SChris Mason return PTR_ERR(split); 130454aa1f4dSChris Mason 13055f39d397SChris Mason btrfs_set_header_flags(split, btrfs_header_flags(c)); 13065f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 13075f39d397SChris Mason btrfs_set_header_blocknr(split, extent_buffer_blocknr(split)); 13085f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 13095f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 13105f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 13115f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 13125f39d397SChris Mason BTRFS_FSID_SIZE); 13135f39d397SChris Mason 13147518a238SChris Mason mid = (c_nritems + 1) / 2; 13155f39d397SChris Mason 13165f39d397SChris Mason copy_extent_buffer(split, c, 13175f39d397SChris Mason btrfs_node_key_ptr_offset(0), 13185f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 1319123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 13205f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 13215f39d397SChris Mason btrfs_set_header_nritems(c, mid); 1322aa5d6bedSChris Mason ret = 0; 1323aa5d6bedSChris Mason 13245f39d397SChris Mason btrfs_mark_buffer_dirty(c); 13255f39d397SChris Mason btrfs_mark_buffer_dirty(split); 13265f39d397SChris Mason 13275f39d397SChris Mason btrfs_node_key(split, &disk_key, 0); 13285f39d397SChris Mason wret = insert_ptr(trans, root, path, &disk_key, 13295f39d397SChris Mason extent_buffer_blocknr(split), 13305f39d397SChris Mason path->slots[level + 1] + 1, 1331123abc88SChris Mason level + 1); 1332aa5d6bedSChris Mason if (wret) 1333aa5d6bedSChris Mason ret = wret; 1334aa5d6bedSChris Mason 13355de08d7dSChris Mason if (path->slots[level] >= mid) { 13365c680ed6SChris Mason path->slots[level] -= mid; 13375f39d397SChris Mason free_extent_buffer(c); 13385f39d397SChris Mason path->nodes[level] = split; 13395c680ed6SChris Mason path->slots[level + 1] += 1; 1340eb60ceacSChris Mason } else { 13415f39d397SChris Mason free_extent_buffer(split); 1342be0e5c09SChris Mason } 1343aa5d6bedSChris Mason return ret; 1344be0e5c09SChris Mason } 1345be0e5c09SChris Mason 134674123bd7SChris Mason /* 134774123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 134874123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 134974123bd7SChris Mason * space used both by the item structs and the item data 135074123bd7SChris Mason */ 13515f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 1352be0e5c09SChris Mason { 1353be0e5c09SChris Mason int data_len; 13545f39d397SChris Mason int nritems = btrfs_header_nritems(l); 1355d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 1356be0e5c09SChris Mason 1357be0e5c09SChris Mason if (!nr) 1358be0e5c09SChris Mason return 0; 13595f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 13605f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 13610783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 1362d4dbff95SChris Mason WARN_ON(data_len < 0); 1363be0e5c09SChris Mason return data_len; 1364be0e5c09SChris Mason } 1365be0e5c09SChris Mason 136674123bd7SChris Mason /* 1367d4dbff95SChris Mason * The space between the end of the leaf items and 1368d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 1369d4dbff95SChris Mason * the leaf has left for both items and data 1370d4dbff95SChris Mason */ 13715f39d397SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf) 1372d4dbff95SChris Mason { 13735f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 13745f39d397SChris Mason int ret; 13755f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 13765f39d397SChris Mason if (ret < 0) { 13775f39d397SChris Mason printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n", 13785f39d397SChris Mason ret, BTRFS_LEAF_DATA_SIZE(root), 13795f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 13805f39d397SChris Mason } 13815f39d397SChris Mason return ret; 1382d4dbff95SChris Mason } 1383d4dbff95SChris Mason 1384d4dbff95SChris Mason /* 138500ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 138600ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 1387aa5d6bedSChris Mason * 1388aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 1389aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 139000ec4c51SChris Mason */ 1391e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 1392e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 139300ec4c51SChris Mason { 13945f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 13955f39d397SChris Mason struct extent_buffer *right; 13965f39d397SChris Mason struct extent_buffer *upper; 13975f39d397SChris Mason struct btrfs_disk_key disk_key; 139800ec4c51SChris Mason int slot; 139900ec4c51SChris Mason int i; 140000ec4c51SChris Mason int free_space; 140100ec4c51SChris Mason int push_space = 0; 140200ec4c51SChris Mason int push_items = 0; 14030783fcfcSChris Mason struct btrfs_item *item; 14047518a238SChris Mason u32 left_nritems; 14057518a238SChris Mason u32 right_nritems; 14065f39d397SChris Mason u32 data_end; 140754aa1f4dSChris Mason int ret; 140800ec4c51SChris Mason 140900ec4c51SChris Mason slot = path->slots[1]; 141000ec4c51SChris Mason if (!path->nodes[1]) { 141100ec4c51SChris Mason return 1; 141200ec4c51SChris Mason } 141300ec4c51SChris Mason upper = path->nodes[1]; 14145f39d397SChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 141500ec4c51SChris Mason return 1; 14165f39d397SChris Mason 14175f39d397SChris Mason right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1)); 1418123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 14190783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 14205f39d397SChris Mason free_extent_buffer(right); 142102217ed2SChris Mason return 1; 142202217ed2SChris Mason } 142302217ed2SChris Mason 14245f39d397SChris Mason /* cow and double check */ 14255f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, upper, 14265f39d397SChris Mason slot + 1, &right); 14275f39d397SChris Mason if (ret) { 14285f39d397SChris Mason free_extent_buffer(right); 1429a429e513SChris Mason return 1; 1430a429e513SChris Mason } 14315f39d397SChris Mason free_space = btrfs_leaf_free_space(root, right); 14325f39d397SChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 14335f39d397SChris Mason free_extent_buffer(right); 14345f39d397SChris Mason return 1; 14355f39d397SChris Mason } 14365f39d397SChris Mason 14375f39d397SChris Mason left_nritems = btrfs_header_nritems(left); 14385f39d397SChris Mason if (left_nritems == 0) { 14395f39d397SChris Mason free_extent_buffer(right); 14405f39d397SChris Mason return 1; 14415f39d397SChris Mason } 14425f39d397SChris Mason 1443a429e513SChris Mason for (i = left_nritems - 1; i >= 1; i--) { 14445f39d397SChris Mason item = btrfs_item_nr(left, i); 144500ec4c51SChris Mason if (path->slots[0] == i) 144600ec4c51SChris Mason push_space += data_size + sizeof(*item); 14475f39d397SChris Mason if (btrfs_item_size(left, item) + sizeof(*item) + push_space > 14480783fcfcSChris Mason free_space) 144900ec4c51SChris Mason break; 145000ec4c51SChris Mason push_items++; 14515f39d397SChris Mason push_space += btrfs_item_size(left, item) + sizeof(*item); 145200ec4c51SChris Mason } 14535f39d397SChris Mason 145400ec4c51SChris Mason if (push_items == 0) { 14555f39d397SChris Mason free_extent_buffer(right); 145600ec4c51SChris Mason return 1; 145700ec4c51SChris Mason } 14585f39d397SChris Mason 1459a429e513SChris Mason if (push_items == left_nritems) 1460a429e513SChris Mason WARN_ON(1); 14615f39d397SChris Mason 146200ec4c51SChris Mason /* push left to right */ 14635f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 14645f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 1465123abc88SChris Mason push_space -= leaf_data_end(root, left); 14665f39d397SChris Mason 146700ec4c51SChris Mason /* make room in the right data area */ 14685f39d397SChris Mason data_end = leaf_data_end(root, right); 14695f39d397SChris Mason memmove_extent_buffer(right, 14705f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 14715f39d397SChris Mason btrfs_leaf_data(right) + data_end, 14725f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 14735f39d397SChris Mason 147400ec4c51SChris Mason /* copy from the left data area */ 14755f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 1476d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1477d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 1478d6025579SChris Mason push_space); 14795f39d397SChris Mason 14805f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 14815f39d397SChris Mason btrfs_item_nr_offset(0), 14820783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 14835f39d397SChris Mason 148400ec4c51SChris Mason /* copy the items from left to right */ 14855f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 14865f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 14870783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 148800ec4c51SChris Mason 148900ec4c51SChris Mason /* update the item pointers */ 14907518a238SChris Mason right_nritems += push_items; 14915f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 1492123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 14937518a238SChris Mason for (i = 0; i < right_nritems; i++) { 14945f39d397SChris Mason item = btrfs_item_nr(right, i); 14955f39d397SChris Mason btrfs_set_item_offset(right, item, push_space - 14965f39d397SChris Mason btrfs_item_size(right, item)); 14975f39d397SChris Mason push_space = btrfs_item_offset(right, item); 149800ec4c51SChris Mason } 14997518a238SChris Mason left_nritems -= push_items; 15005f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 150100ec4c51SChris Mason 15025f39d397SChris Mason btrfs_mark_buffer_dirty(left); 15035f39d397SChris Mason btrfs_mark_buffer_dirty(right); 1504a429e513SChris Mason 15055f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 15065f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 1507d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 150802217ed2SChris Mason 150900ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 15107518a238SChris Mason if (path->slots[0] >= left_nritems) { 15117518a238SChris Mason path->slots[0] -= left_nritems; 15125f39d397SChris Mason free_extent_buffer(path->nodes[0]); 15135f39d397SChris Mason path->nodes[0] = right; 151400ec4c51SChris Mason path->slots[1] += 1; 151500ec4c51SChris Mason } else { 15165f39d397SChris Mason free_extent_buffer(right); 151700ec4c51SChris Mason } 1518098f59c2SChris Mason if (path->nodes[1]) 1519098f59c2SChris Mason check_node(root, path, 1); 152000ec4c51SChris Mason return 0; 152100ec4c51SChris Mason } 152200ec4c51SChris Mason /* 152374123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 152474123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 152574123bd7SChris Mason */ 1526e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 1527e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1528be0e5c09SChris Mason { 15295f39d397SChris Mason struct btrfs_disk_key disk_key; 15305f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 15315f39d397SChris Mason struct extent_buffer *left; 1532be0e5c09SChris Mason int slot; 1533be0e5c09SChris Mason int i; 1534be0e5c09SChris Mason int free_space; 1535be0e5c09SChris Mason int push_space = 0; 1536be0e5c09SChris Mason int push_items = 0; 15370783fcfcSChris Mason struct btrfs_item *item; 15387518a238SChris Mason u32 old_left_nritems; 15395f39d397SChris Mason u32 right_nritems; 1540aa5d6bedSChris Mason int ret = 0; 1541aa5d6bedSChris Mason int wret; 1542be0e5c09SChris Mason 1543be0e5c09SChris Mason slot = path->slots[1]; 15445f39d397SChris Mason if (slot == 0) 1545be0e5c09SChris Mason return 1; 15465f39d397SChris Mason if (!path->nodes[1]) 1547be0e5c09SChris Mason return 1; 15485f39d397SChris Mason 15495f39d397SChris Mason left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1], 15505f39d397SChris Mason slot - 1)); 1551123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 15520783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 15535f39d397SChris Mason free_extent_buffer(left); 1554be0e5c09SChris Mason return 1; 1555be0e5c09SChris Mason } 155602217ed2SChris Mason 155702217ed2SChris Mason /* cow and double check */ 15585f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, 15595f39d397SChris Mason path->nodes[1], slot - 1, &left); 156054aa1f4dSChris Mason if (ret) { 156154aa1f4dSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 15625f39d397SChris Mason free_extent_buffer(left); 156354aa1f4dSChris Mason return 1; 156454aa1f4dSChris Mason } 1565123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 15660783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 15675f39d397SChris Mason free_extent_buffer(left); 156802217ed2SChris Mason return 1; 156902217ed2SChris Mason } 157002217ed2SChris Mason 15715f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 15725f39d397SChris Mason if (right_nritems == 0) { 15735f39d397SChris Mason free_extent_buffer(left); 1574a429e513SChris Mason return 1; 1575a429e513SChris Mason } 1576a429e513SChris Mason 15775f39d397SChris Mason for (i = 0; i < right_nritems - 1; i++) { 15785f39d397SChris Mason item = btrfs_item_nr(right, i); 1579be0e5c09SChris Mason if (path->slots[0] == i) 1580be0e5c09SChris Mason push_space += data_size + sizeof(*item); 15815f39d397SChris Mason if (btrfs_item_size(right, item) + sizeof(*item) + push_space > 15820783fcfcSChris Mason free_space) 1583be0e5c09SChris Mason break; 1584be0e5c09SChris Mason push_items++; 15855f39d397SChris Mason push_space += btrfs_item_size(right, item) + sizeof(*item); 1586be0e5c09SChris Mason } 1587be0e5c09SChris Mason if (push_items == 0) { 15885f39d397SChris Mason free_extent_buffer(left); 1589be0e5c09SChris Mason return 1; 1590be0e5c09SChris Mason } 15915f39d397SChris Mason if (push_items == btrfs_header_nritems(right)) 1592a429e513SChris Mason WARN_ON(1); 15935f39d397SChris Mason 1594be0e5c09SChris Mason /* push data from right to left */ 15955f39d397SChris Mason copy_extent_buffer(left, right, 15965f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 15975f39d397SChris Mason btrfs_item_nr_offset(0), 15985f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 15995f39d397SChris Mason 1600123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 16015f39d397SChris Mason btrfs_item_offset_nr(right, push_items -1); 16025f39d397SChris Mason 16035f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 1604d6025579SChris Mason leaf_data_end(root, left) - push_space, 1605123abc88SChris Mason btrfs_leaf_data(right) + 16065f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 1607be0e5c09SChris Mason push_space); 16085f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 1609eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 1610eb60ceacSChris Mason 1611be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 16125f39d397SChris Mason u32 ioff; 16135f39d397SChris Mason item = btrfs_item_nr(left, i); 16145f39d397SChris Mason ioff = btrfs_item_offset(left, item); 16155f39d397SChris Mason btrfs_set_item_offset(left, item, 16165f39d397SChris Mason ioff - (BTRFS_LEAF_DATA_SIZE(root) - 16175f39d397SChris Mason btrfs_item_offset_nr(left, old_left_nritems - 1))); 1618be0e5c09SChris Mason } 16195f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 1620be0e5c09SChris Mason 1621be0e5c09SChris Mason /* fixup right node */ 16225f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 1623123abc88SChris Mason leaf_data_end(root, right); 16245f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 1625d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1626d6025579SChris Mason btrfs_leaf_data(right) + 1627123abc88SChris Mason leaf_data_end(root, right), push_space); 16285f39d397SChris Mason 16295f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 16305f39d397SChris Mason btrfs_item_nr_offset(push_items), 16315f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 16320783fcfcSChris Mason sizeof(struct btrfs_item)); 16335f39d397SChris Mason 16345f39d397SChris Mason right_nritems = btrfs_header_nritems(right) - push_items; 16355f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 1636123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1637eb60ceacSChris Mason 16385f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 16395f39d397SChris Mason item = btrfs_item_nr(right, i); 16405f39d397SChris Mason btrfs_set_item_offset(right, item, push_space - 16415f39d397SChris Mason btrfs_item_size(right, item)); 16425f39d397SChris Mason push_space = btrfs_item_offset(right, item); 1643be0e5c09SChris Mason } 1644eb60ceacSChris Mason 16455f39d397SChris Mason btrfs_mark_buffer_dirty(left); 16465f39d397SChris Mason btrfs_mark_buffer_dirty(right); 1647098f59c2SChris Mason 16485f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 16495f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 1650aa5d6bedSChris Mason if (wret) 1651aa5d6bedSChris Mason ret = wret; 1652be0e5c09SChris Mason 1653be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1654be0e5c09SChris Mason if (path->slots[0] < push_items) { 1655be0e5c09SChris Mason path->slots[0] += old_left_nritems; 16565f39d397SChris Mason free_extent_buffer(path->nodes[0]); 16575f39d397SChris Mason path->nodes[0] = left; 1658be0e5c09SChris Mason path->slots[1] -= 1; 1659be0e5c09SChris Mason } else { 16605f39d397SChris Mason free_extent_buffer(left); 1661be0e5c09SChris Mason path->slots[0] -= push_items; 1662be0e5c09SChris Mason } 1663eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1664098f59c2SChris Mason if (path->nodes[1]) 1665098f59c2SChris Mason check_node(root, path, 1); 1666aa5d6bedSChris Mason return ret; 1667be0e5c09SChris Mason } 1668be0e5c09SChris Mason 166974123bd7SChris Mason /* 167074123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 167174123bd7SChris Mason * available for the resulting leaf level of the path. 1672aa5d6bedSChris Mason * 1673aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 167474123bd7SChris Mason */ 1675e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1676d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 1677d4dbff95SChris Mason struct btrfs_path *path, int data_size) 1678be0e5c09SChris Mason { 16795f39d397SChris Mason struct extent_buffer *l; 16807518a238SChris Mason u32 nritems; 1681eb60ceacSChris Mason int mid; 1682eb60ceacSChris Mason int slot; 16835f39d397SChris Mason struct extent_buffer *right; 16840783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1685be0e5c09SChris Mason int data_copy_size; 1686be0e5c09SChris Mason int rt_data_off; 1687be0e5c09SChris Mason int i; 1688d4dbff95SChris Mason int ret = 0; 1689aa5d6bedSChris Mason int wret; 1690d4dbff95SChris Mason int double_split = 0; 1691d4dbff95SChris Mason struct btrfs_disk_key disk_key; 1692be0e5c09SChris Mason 169340689478SChris Mason /* first try to make some room by pushing left and right */ 1694e089f05cSChris Mason wret = push_leaf_left(trans, root, path, data_size); 1695eaee50e8SChris Mason if (wret < 0) 1696eaee50e8SChris Mason return wret; 1697eaee50e8SChris Mason if (wret) { 1698e089f05cSChris Mason wret = push_leaf_right(trans, root, path, data_size); 1699eaee50e8SChris Mason if (wret < 0) 1700eaee50e8SChris Mason return wret; 1701eaee50e8SChris Mason } 17025f39d397SChris Mason l = path->nodes[0]; 1703aa5d6bedSChris Mason 1704aa5d6bedSChris Mason /* did the pushes work? */ 1705123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1706123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1707be0e5c09SChris Mason return 0; 1708aa5d6bedSChris Mason 17095c680ed6SChris Mason if (!path->nodes[1]) { 1710e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 17115c680ed6SChris Mason if (ret) 17125c680ed6SChris Mason return ret; 17135c680ed6SChris Mason } 1714eb60ceacSChris Mason slot = path->slots[0]; 17155f39d397SChris Mason nritems = btrfs_header_nritems(l); 1716eb60ceacSChris Mason mid = (nritems + 1)/ 2; 171754aa1f4dSChris Mason 17185f39d397SChris Mason right = btrfs_alloc_free_block(trans, root, 17195f39d397SChris Mason extent_buffer_blocknr(l), 0); 17205f39d397SChris Mason if (IS_ERR(right)) 17215f39d397SChris Mason return PTR_ERR(right); 172254aa1f4dSChris Mason 17235f39d397SChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 17245f39d397SChris Mason btrfs_set_header_blocknr(right, extent_buffer_blocknr(right)); 17255f39d397SChris Mason btrfs_set_header_generation(right, trans->transid); 17265f39d397SChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 17275f39d397SChris Mason btrfs_set_header_level(right, 0); 17285f39d397SChris Mason write_extent_buffer(right, root->fs_info->fsid, 17295f39d397SChris Mason (unsigned long)btrfs_header_fsid(right), 17305f39d397SChris Mason BTRFS_FSID_SIZE); 17315f39d397SChris Mason 1732d4dbff95SChris Mason if (mid <= slot) { 1733d4dbff95SChris Mason if (nritems == 1 || 1734d4dbff95SChris Mason leaf_space_used(l, mid, nritems - mid) + space_needed > 1735d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 1736d4dbff95SChris Mason if (slot >= nritems) { 1737d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 17385f39d397SChris Mason btrfs_set_header_nritems(right, 0); 1739d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1740d4dbff95SChris Mason &disk_key, 17415f39d397SChris Mason extent_buffer_blocknr(right), 1742d4dbff95SChris Mason path->slots[1] + 1, 1); 1743d4dbff95SChris Mason if (wret) 1744d4dbff95SChris Mason ret = wret; 17455f39d397SChris Mason free_extent_buffer(path->nodes[0]); 17465f39d397SChris Mason path->nodes[0] = right; 1747d4dbff95SChris Mason path->slots[0] = 0; 1748d4dbff95SChris Mason path->slots[1] += 1; 1749d4dbff95SChris Mason return ret; 1750d4dbff95SChris Mason } 1751d4dbff95SChris Mason mid = slot; 1752d4dbff95SChris Mason double_split = 1; 1753d4dbff95SChris Mason } 1754d4dbff95SChris Mason } else { 1755d4dbff95SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1756d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 1757d4dbff95SChris Mason if (slot == 0) { 1758d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 17595f39d397SChris Mason btrfs_set_header_nritems(right, 0); 1760d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1761d4dbff95SChris Mason &disk_key, 17625f39d397SChris Mason extent_buffer_blocknr(right), 1763098f59c2SChris Mason path->slots[1], 1); 1764d4dbff95SChris Mason if (wret) 1765d4dbff95SChris Mason ret = wret; 17665f39d397SChris Mason free_extent_buffer(path->nodes[0]); 17675f39d397SChris Mason path->nodes[0] = right; 1768d4dbff95SChris Mason path->slots[0] = 0; 1769a429e513SChris Mason if (path->slots[1] == 0) { 1770a429e513SChris Mason wret = fixup_low_keys(trans, root, 1771a429e513SChris Mason path, &disk_key, 1); 1772a429e513SChris Mason if (wret) 1773a429e513SChris Mason ret = wret; 1774a429e513SChris Mason } 1775d4dbff95SChris Mason return ret; 1776d4dbff95SChris Mason } 1777d4dbff95SChris Mason mid = slot; 1778d4dbff95SChris Mason double_split = 1; 1779d4dbff95SChris Mason } 1780d4dbff95SChris Mason } 17815f39d397SChris Mason nritems = nritems - mid; 17825f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 17835f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 17845f39d397SChris Mason 17855f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 17865f39d397SChris Mason btrfs_item_nr_offset(mid), 17875f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 17885f39d397SChris Mason 17895f39d397SChris Mason copy_extent_buffer(right, l, 1790d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1791123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1792123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 179374123bd7SChris Mason 17945f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 17955f39d397SChris Mason btrfs_item_end_nr(l, mid); 17965f39d397SChris Mason 17975f39d397SChris Mason for (i = 0; i < nritems; i++) { 17985f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 17995f39d397SChris Mason u32 ioff = btrfs_item_offset(right, item); 18005f39d397SChris Mason btrfs_set_item_offset(right, item, ioff + rt_data_off); 18010783fcfcSChris Mason } 180274123bd7SChris Mason 18035f39d397SChris Mason btrfs_set_header_nritems(l, mid); 1804aa5d6bedSChris Mason ret = 0; 18055f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 18065f39d397SChris Mason wret = insert_ptr(trans, root, path, &disk_key, 18075f39d397SChris Mason extent_buffer_blocknr(right), path->slots[1] + 1, 1); 1808aa5d6bedSChris Mason if (wret) 1809aa5d6bedSChris Mason ret = wret; 18105f39d397SChris Mason 18115f39d397SChris Mason btrfs_mark_buffer_dirty(right); 18125f39d397SChris Mason btrfs_mark_buffer_dirty(l); 1813eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 18145f39d397SChris Mason 1815be0e5c09SChris Mason if (mid <= slot) { 18165f39d397SChris Mason free_extent_buffer(path->nodes[0]); 18175f39d397SChris Mason path->nodes[0] = right; 1818be0e5c09SChris Mason path->slots[0] -= mid; 1819be0e5c09SChris Mason path->slots[1] += 1; 1820eb60ceacSChris Mason } else 18215f39d397SChris Mason free_extent_buffer(right); 18225f39d397SChris Mason 1823eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1824098f59c2SChris Mason check_node(root, path, 1); 18255f39d397SChris Mason check_leaf(root, path, 0); 1826d4dbff95SChris Mason 1827d4dbff95SChris Mason if (!double_split) 1828d4dbff95SChris Mason return ret; 182954aa1f4dSChris Mason 18305f39d397SChris Mason right = btrfs_alloc_free_block(trans, root, 18315f39d397SChris Mason extent_buffer_blocknr(l), 0); 18325f39d397SChris Mason if (IS_ERR(right)) 18335f39d397SChris Mason return PTR_ERR(right); 18345f39d397SChris Mason 18355f39d397SChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 18365f39d397SChris Mason btrfs_set_header_blocknr(right, extent_buffer_blocknr(right)); 18375f39d397SChris Mason btrfs_set_header_generation(right, trans->transid); 18385f39d397SChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 18395f39d397SChris Mason btrfs_set_header_level(right, 0); 18405f39d397SChris Mason write_extent_buffer(right, root->fs_info->fsid, 18415f39d397SChris Mason (unsigned long)btrfs_header_fsid(right), 18425f39d397SChris Mason BTRFS_FSID_SIZE); 18435f39d397SChris Mason 1844d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 18455f39d397SChris Mason btrfs_set_header_nritems(right, 0); 1846d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1847d4dbff95SChris Mason &disk_key, 18485f39d397SChris Mason extent_buffer_blocknr(right), 1849d4dbff95SChris Mason path->slots[1], 1); 1850d4dbff95SChris Mason if (wret) 1851d4dbff95SChris Mason ret = wret; 1852a429e513SChris Mason if (path->slots[1] == 0) { 1853a429e513SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 1854a429e513SChris Mason if (wret) 1855a429e513SChris Mason ret = wret; 1856a429e513SChris Mason } 18575f39d397SChris Mason free_extent_buffer(path->nodes[0]); 18585f39d397SChris Mason path->nodes[0] = right; 1859d4dbff95SChris Mason path->slots[0] = 0; 1860d4dbff95SChris Mason check_node(root, path, 1); 1861d4dbff95SChris Mason check_leaf(root, path, 0); 1862be0e5c09SChris Mason return ret; 1863be0e5c09SChris Mason } 1864be0e5c09SChris Mason 1865b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans, 1866b18c6685SChris Mason struct btrfs_root *root, 1867b18c6685SChris Mason struct btrfs_path *path, 1868b18c6685SChris Mason u32 new_size) 1869b18c6685SChris Mason { 1870b18c6685SChris Mason int ret = 0; 1871b18c6685SChris Mason int slot; 1872b18c6685SChris Mason int slot_orig; 18735f39d397SChris Mason struct extent_buffer *leaf; 18745f39d397SChris Mason struct btrfs_item *item; 1875b18c6685SChris Mason u32 nritems; 1876b18c6685SChris Mason unsigned int data_end; 1877b18c6685SChris Mason unsigned int old_data_start; 1878b18c6685SChris Mason unsigned int old_size; 1879b18c6685SChris Mason unsigned int size_diff; 1880b18c6685SChris Mason int i; 1881b18c6685SChris Mason 1882b18c6685SChris Mason slot_orig = path->slots[0]; 18835f39d397SChris Mason leaf = path->nodes[0]; 1884b18c6685SChris Mason 18855f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 1886b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 1887b18c6685SChris Mason 1888b18c6685SChris Mason slot = path->slots[0]; 18895f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 18905f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 1891b18c6685SChris Mason BUG_ON(old_size <= new_size); 1892b18c6685SChris Mason size_diff = old_size - new_size; 1893b18c6685SChris Mason 1894b18c6685SChris Mason BUG_ON(slot < 0); 1895b18c6685SChris Mason BUG_ON(slot >= nritems); 1896b18c6685SChris Mason 1897b18c6685SChris Mason /* 1898b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1899b18c6685SChris Mason */ 1900b18c6685SChris Mason /* first correct the data pointers */ 1901b18c6685SChris Mason for (i = slot; i < nritems; i++) { 19025f39d397SChris Mason u32 ioff; 19035f39d397SChris Mason item = btrfs_item_nr(leaf, i); 19045f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 19055f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + size_diff); 1906b18c6685SChris Mason } 1907b18c6685SChris Mason /* shift the data */ 19085f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 1909b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 1910b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 19115f39d397SChris Mason 19125f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 19135f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 19145f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 1915b18c6685SChris Mason 1916b18c6685SChris Mason ret = 0; 19175f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 19185f39d397SChris Mason btrfs_print_leaf(root, leaf); 1919b18c6685SChris Mason BUG(); 19205f39d397SChris Mason } 1921b18c6685SChris Mason check_leaf(root, path, 0); 1922b18c6685SChris Mason return ret; 1923b18c6685SChris Mason } 1924b18c6685SChris Mason 19255f39d397SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans, 19265f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 19275f39d397SChris Mason u32 data_size) 19286567e837SChris Mason { 19296567e837SChris Mason int ret = 0; 19306567e837SChris Mason int slot; 19316567e837SChris Mason int slot_orig; 19325f39d397SChris Mason struct extent_buffer *leaf; 19335f39d397SChris Mason struct btrfs_item *item; 19346567e837SChris Mason u32 nritems; 19356567e837SChris Mason unsigned int data_end; 19366567e837SChris Mason unsigned int old_data; 19376567e837SChris Mason unsigned int old_size; 19386567e837SChris Mason int i; 19396567e837SChris Mason 19406567e837SChris Mason slot_orig = path->slots[0]; 19415f39d397SChris Mason leaf = path->nodes[0]; 19426567e837SChris Mason 19435f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 19446567e837SChris Mason data_end = leaf_data_end(root, leaf); 19456567e837SChris Mason 19465f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 19475f39d397SChris Mason btrfs_print_leaf(root, leaf); 19486567e837SChris Mason BUG(); 19495f39d397SChris Mason } 19506567e837SChris Mason slot = path->slots[0]; 19515f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 19526567e837SChris Mason 19536567e837SChris Mason BUG_ON(slot < 0); 19546567e837SChris Mason BUG_ON(slot >= nritems); 19556567e837SChris Mason 19566567e837SChris Mason /* 19576567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 19586567e837SChris Mason */ 19596567e837SChris Mason /* first correct the data pointers */ 19606567e837SChris Mason for (i = slot; i < nritems; i++) { 19615f39d397SChris Mason u32 ioff; 19625f39d397SChris Mason item = btrfs_item_nr(leaf, i); 19635f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 19645f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 19656567e837SChris Mason } 19665f39d397SChris Mason 19676567e837SChris Mason /* shift the data */ 19685f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 19696567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 19706567e837SChris Mason data_end, old_data - data_end); 19715f39d397SChris Mason 19726567e837SChris Mason data_end = old_data; 19735f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 19745f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 19755f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 19765f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 19776567e837SChris Mason 19786567e837SChris Mason ret = 0; 19795f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 19805f39d397SChris Mason btrfs_print_leaf(root, leaf); 19816567e837SChris Mason BUG(); 19825f39d397SChris Mason } 19836567e837SChris Mason check_leaf(root, path, 0); 19846567e837SChris Mason return ret; 19856567e837SChris Mason } 19866567e837SChris Mason 198774123bd7SChris Mason /* 198874123bd7SChris Mason * Given a key and some data, insert an item into the tree. 198974123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 199074123bd7SChris Mason */ 19915f39d397SChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, 19925f39d397SChris Mason struct btrfs_root *root, 19935f39d397SChris Mason struct btrfs_path *path, 19945f39d397SChris Mason struct btrfs_key *cpu_key, u32 data_size) 1995be0e5c09SChris Mason { 19965f39d397SChris Mason struct extent_buffer *leaf; 19975f39d397SChris Mason struct btrfs_item *item; 1998aa5d6bedSChris Mason int ret = 0; 1999be0e5c09SChris Mason int slot; 2000eb60ceacSChris Mason int slot_orig; 20017518a238SChris Mason u32 nritems; 2002be0e5c09SChris Mason unsigned int data_end; 2003e2fa7227SChris Mason struct btrfs_disk_key disk_key; 2004e2fa7227SChris Mason 2005e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 2006be0e5c09SChris Mason 200774123bd7SChris Mason /* create a root if there isn't one */ 20085c680ed6SChris Mason if (!root->node) 2009cfaa7295SChris Mason BUG(); 20105f39d397SChris Mason 2011e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 2012eb60ceacSChris Mason if (ret == 0) { 2013f0930a37SChris Mason return -EEXIST; 2014aa5d6bedSChris Mason } 2015ed2ff2cbSChris Mason if (ret < 0) 2016ed2ff2cbSChris Mason goto out; 2017be0e5c09SChris Mason 201862e2749eSChris Mason slot_orig = path->slots[0]; 20195f39d397SChris Mason leaf = path->nodes[0]; 202074123bd7SChris Mason 20215f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 2022123abc88SChris Mason data_end = leaf_data_end(root, leaf); 2023eb60ceacSChris Mason 2024123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 2025d4dbff95SChris Mason sizeof(struct btrfs_item) + data_size) { 2026be0e5c09SChris Mason BUG(); 2027d4dbff95SChris Mason } 20285f39d397SChris Mason 202962e2749eSChris Mason slot = path->slots[0]; 2030eb60ceacSChris Mason BUG_ON(slot < 0); 20315f39d397SChris Mason 2032be0e5c09SChris Mason if (slot != nritems) { 2033be0e5c09SChris Mason int i; 20345f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 2035be0e5c09SChris Mason 20365f39d397SChris Mason if (old_data < data_end) { 20375f39d397SChris Mason btrfs_print_leaf(root, leaf); 20385f39d397SChris Mason printk("slot %d old_data %d data_end %d\n", 20395f39d397SChris Mason slot, old_data, data_end); 20405f39d397SChris Mason BUG_ON(1); 20415f39d397SChris Mason } 2042be0e5c09SChris Mason /* 2043be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 2044be0e5c09SChris Mason */ 2045be0e5c09SChris Mason /* first correct the data pointers */ 20460783fcfcSChris Mason for (i = slot; i < nritems; i++) { 20475f39d397SChris Mason u32 ioff; 20485f39d397SChris Mason item = btrfs_item_nr(leaf, i); 20495f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 20505f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 20510783fcfcSChris Mason } 2052be0e5c09SChris Mason 2053be0e5c09SChris Mason /* shift the items */ 20545f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 20555f39d397SChris Mason btrfs_item_nr_offset(slot), 20560783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 2057be0e5c09SChris Mason 2058be0e5c09SChris Mason /* shift the data */ 20595f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 2060d6025579SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 2061be0e5c09SChris Mason data_end, old_data - data_end); 2062be0e5c09SChris Mason data_end = old_data; 2063be0e5c09SChris Mason } 20645f39d397SChris Mason 206562e2749eSChris Mason /* setup the item for the new data */ 20665f39d397SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 20675f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 20685f39d397SChris Mason btrfs_set_item_offset(leaf, item, data_end - data_size); 20695f39d397SChris Mason btrfs_set_item_size(leaf, item, data_size); 20705f39d397SChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 20715f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 2072aa5d6bedSChris Mason 2073aa5d6bedSChris Mason ret = 0; 20748e19f2cdSChris Mason if (slot == 0) 2075e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 2076aa5d6bedSChris Mason 20775f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 20785f39d397SChris Mason btrfs_print_leaf(root, leaf); 2079be0e5c09SChris Mason BUG(); 20805f39d397SChris Mason } 208162e2749eSChris Mason check_leaf(root, path, 0); 2082ed2ff2cbSChris Mason out: 208362e2749eSChris Mason return ret; 208462e2749eSChris Mason } 208562e2749eSChris Mason 208662e2749eSChris Mason /* 208762e2749eSChris Mason * Given a key and some data, insert an item into the tree. 208862e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 208962e2749eSChris Mason */ 2090e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 2091e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 2092e089f05cSChris Mason data_size) 209362e2749eSChris Mason { 209462e2749eSChris Mason int ret = 0; 20952c90e5d6SChris Mason struct btrfs_path *path; 20965f39d397SChris Mason struct extent_buffer *leaf; 20975f39d397SChris Mason unsigned long ptr; 209862e2749eSChris Mason 20992c90e5d6SChris Mason path = btrfs_alloc_path(); 21002c90e5d6SChris Mason BUG_ON(!path); 21012c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 210262e2749eSChris Mason if (!ret) { 21035f39d397SChris Mason leaf = path->nodes[0]; 21045f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 21055f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 21065f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 210762e2749eSChris Mason } 21082c90e5d6SChris Mason btrfs_free_path(path); 2109aa5d6bedSChris Mason return ret; 2110be0e5c09SChris Mason } 2111be0e5c09SChris Mason 211274123bd7SChris Mason /* 21135de08d7dSChris Mason * delete the pointer from a given node. 211474123bd7SChris Mason * 211574123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 211674123bd7SChris Mason * continuing all the way the root if required. The root is converted into 211774123bd7SChris Mason * a leaf if all the nodes are emptied. 211874123bd7SChris Mason */ 2119e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2120e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 2121be0e5c09SChris Mason { 21225f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 21237518a238SChris Mason u32 nritems; 2124aa5d6bedSChris Mason int ret = 0; 2125bb803951SChris Mason int wret; 2126be0e5c09SChris Mason 21275f39d397SChris Mason nritems = btrfs_header_nritems(parent); 2128be0e5c09SChris Mason if (slot != nritems -1) { 21295f39d397SChris Mason memmove_extent_buffer(parent, 21305f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 21315f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 2132d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 2133d6025579SChris Mason (nritems - slot - 1)); 2134be0e5c09SChris Mason } 21357518a238SChris Mason nritems--; 21365f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 21377518a238SChris Mason if (nritems == 0 && parent == root->node) { 21385f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 2139eb60ceacSChris Mason /* just turn the root into a leaf and break */ 21405f39d397SChris Mason btrfs_set_header_level(root->node, 0); 2141bb803951SChris Mason } else if (slot == 0) { 21425f39d397SChris Mason struct btrfs_disk_key disk_key; 21435f39d397SChris Mason 21445f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 21455f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); 21460f70abe2SChris Mason if (wret) 21470f70abe2SChris Mason ret = wret; 2148be0e5c09SChris Mason } 2149d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 2150aa5d6bedSChris Mason return ret; 2151be0e5c09SChris Mason } 2152be0e5c09SChris Mason 215374123bd7SChris Mason /* 215474123bd7SChris Mason * delete the item at the leaf level in path. If that empties 215574123bd7SChris Mason * the leaf, remove it from the tree 215674123bd7SChris Mason */ 2157e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2158e089f05cSChris Mason struct btrfs_path *path) 2159be0e5c09SChris Mason { 2160be0e5c09SChris Mason int slot; 21615f39d397SChris Mason struct extent_buffer *leaf; 21625f39d397SChris Mason struct btrfs_item *item; 2163be0e5c09SChris Mason int doff; 2164be0e5c09SChris Mason int dsize; 2165aa5d6bedSChris Mason int ret = 0; 2166aa5d6bedSChris Mason int wret; 21677518a238SChris Mason u32 nritems; 2168be0e5c09SChris Mason 21695f39d397SChris Mason leaf = path->nodes[0]; 21704920c9acSChris Mason slot = path->slots[0]; 21715f39d397SChris Mason doff = btrfs_item_offset_nr(leaf, slot); 21725f39d397SChris Mason dsize = btrfs_item_size_nr(leaf, slot); 21735f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 2174be0e5c09SChris Mason 21757518a238SChris Mason if (slot != nritems - 1) { 2176be0e5c09SChris Mason int i; 2177123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 21785f39d397SChris Mason 21795f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 2180d6025579SChris Mason data_end + dsize, 2181123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 2182be0e5c09SChris Mason doff - data_end); 21835f39d397SChris Mason 21840783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 21855f39d397SChris Mason u32 ioff; 21865f39d397SChris Mason item = btrfs_item_nr(leaf, i); 21875f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 21885f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + dsize); 21890783fcfcSChris Mason } 21905f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 21915f39d397SChris Mason btrfs_item_nr_offset(slot + 1), 21920783fcfcSChris Mason sizeof(struct btrfs_item) * 21937518a238SChris Mason (nritems - slot - 1)); 2194be0e5c09SChris Mason } 21955f39d397SChris Mason btrfs_set_header_nritems(leaf, nritems - 1); 21967518a238SChris Mason nritems--; 21975f39d397SChris Mason 219874123bd7SChris Mason /* delete the leaf if we've emptied it */ 21997518a238SChris Mason if (nritems == 0) { 22005f39d397SChris Mason if (leaf == root->node) { 22015f39d397SChris Mason btrfs_set_header_level(leaf, 0); 22029a8dd150SChris Mason } else { 22035f39d397SChris Mason clean_tree_block(trans, root, leaf); 22045f39d397SChris Mason wait_on_tree_block_writeback(root, leaf); 2205e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 2206aa5d6bedSChris Mason if (wret) 2207aa5d6bedSChris Mason ret = wret; 2208e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 22095f39d397SChris Mason extent_buffer_blocknr(leaf), 22105f39d397SChris Mason 1, 1); 22110f70abe2SChris Mason if (wret) 22120f70abe2SChris Mason ret = wret; 22139a8dd150SChris Mason } 2214be0e5c09SChris Mason } else { 22157518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 2216aa5d6bedSChris Mason if (slot == 0) { 22175f39d397SChris Mason struct btrfs_disk_key disk_key; 22185f39d397SChris Mason 22195f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 2220e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 22215f39d397SChris Mason &disk_key, 1); 2222aa5d6bedSChris Mason if (wret) 2223aa5d6bedSChris Mason ret = wret; 2224aa5d6bedSChris Mason } 2225aa5d6bedSChris Mason 222674123bd7SChris Mason /* delete the leaf if it is mostly empty */ 2227123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 2228be0e5c09SChris Mason /* push_leaf_left fixes the path. 2229be0e5c09SChris Mason * make sure the path still points to our leaf 2230be0e5c09SChris Mason * for possible call to del_ptr below 2231be0e5c09SChris Mason */ 22324920c9acSChris Mason slot = path->slots[1]; 22335f39d397SChris Mason extent_buffer_get(leaf); 22345f39d397SChris Mason 2235e089f05cSChris Mason wret = push_leaf_left(trans, root, path, 1); 223654aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 2237aa5d6bedSChris Mason ret = wret; 22385f39d397SChris Mason 22395f39d397SChris Mason if (path->nodes[0] == leaf && 22405f39d397SChris Mason btrfs_header_nritems(leaf)) { 2241e089f05cSChris Mason wret = push_leaf_right(trans, root, path, 1); 224254aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 2243aa5d6bedSChris Mason ret = wret; 2244aa5d6bedSChris Mason } 22455f39d397SChris Mason 22465f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 22475f39d397SChris Mason u64 blocknr = extent_buffer_blocknr(leaf); 22485f39d397SChris Mason 22495f39d397SChris Mason clean_tree_block(trans, root, leaf); 22505f39d397SChris Mason wait_on_tree_block_writeback(root, leaf); 22515f39d397SChris Mason 2252e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 2253aa5d6bedSChris Mason if (wret) 2254aa5d6bedSChris Mason ret = wret; 22555f39d397SChris Mason 22565f39d397SChris Mason free_extent_buffer(leaf); 2257e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 2258e089f05cSChris Mason 1, 1); 22590f70abe2SChris Mason if (wret) 22600f70abe2SChris Mason ret = wret; 22615de08d7dSChris Mason } else { 22625f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 22635f39d397SChris Mason free_extent_buffer(leaf); 2264be0e5c09SChris Mason } 2265d5719762SChris Mason } else { 22665f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 2267be0e5c09SChris Mason } 22689a8dd150SChris Mason } 2269aa5d6bedSChris Mason return ret; 22709a8dd150SChris Mason } 22719a8dd150SChris Mason 227297571fd0SChris Mason /* 227397571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 22740f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 22750f70abe2SChris Mason * returns < 0 on io errors. 227697571fd0SChris Mason */ 2277234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 2278d97e63b6SChris Mason { 2279d97e63b6SChris Mason int slot; 2280d97e63b6SChris Mason int level = 1; 2281d97e63b6SChris Mason u64 blocknr; 22825f39d397SChris Mason struct extent_buffer *c; 22835f39d397SChris Mason struct extent_buffer *next = NULL; 2284d97e63b6SChris Mason 2285234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 2286d97e63b6SChris Mason if (!path->nodes[level]) 22870f70abe2SChris Mason return 1; 22885f39d397SChris Mason 2289d97e63b6SChris Mason slot = path->slots[level] + 1; 2290d97e63b6SChris Mason c = path->nodes[level]; 22915f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 2292d97e63b6SChris Mason level++; 2293d97e63b6SChris Mason continue; 2294d97e63b6SChris Mason } 22955f39d397SChris Mason 22965f39d397SChris Mason blocknr = btrfs_node_blockptr(c, slot); 2297cfaa7295SChris Mason if (next) 22985f39d397SChris Mason free_extent_buffer(next); 22995f39d397SChris Mason 23006702ed49SChris Mason if (path->reada) 23016702ed49SChris Mason reada_for_search(root, path, level, slot); 23025f39d397SChris Mason 2303d97e63b6SChris Mason next = read_tree_block(root, blocknr); 2304d97e63b6SChris Mason break; 2305d97e63b6SChris Mason } 2306d97e63b6SChris Mason path->slots[level] = slot; 2307d97e63b6SChris Mason while(1) { 2308d97e63b6SChris Mason level--; 2309d97e63b6SChris Mason c = path->nodes[level]; 23105f39d397SChris Mason free_extent_buffer(c); 2311d97e63b6SChris Mason path->nodes[level] = next; 2312d97e63b6SChris Mason path->slots[level] = 0; 2313d97e63b6SChris Mason if (!level) 2314d97e63b6SChris Mason break; 23156702ed49SChris Mason if (path->reada) 231632020611SYan reada_for_search(root, path, level, 0); 23175f39d397SChris Mason next = read_tree_block(root, btrfs_node_blockptr(next, 0)); 2318d97e63b6SChris Mason } 2319d97e63b6SChris Mason return 0; 2320d97e63b6SChris Mason } 2321