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 19a6b6e75eSChris Mason #include <linux/sched.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, 29cc0c5538SChris Mason struct btrfs_path *path, int data_size, int extend); 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 86db94535dSChris Mason cow = btrfs_alloc_free_block(trans, root, buf->len, 87db94535dSChris Mason search_start, empty_size); 886702ed49SChris Mason if (IS_ERR(cow)) 896702ed49SChris Mason return PTR_ERR(cow); 906702ed49SChris Mason 915f39d397SChris Mason copy_extent_buffer(cow, buf, 0, 0, cow->len); 92db94535dSChris Mason btrfs_set_header_bytenr(cow, cow->start); 935f39d397SChris Mason btrfs_set_header_generation(cow, trans->transid); 945f39d397SChris Mason btrfs_set_header_owner(cow, root->root_key.objectid); 956702ed49SChris Mason 965f39d397SChris Mason WARN_ON(btrfs_header_generation(buf) > trans->transid); 975f39d397SChris Mason if (btrfs_header_generation(buf) != trans->transid) { 986702ed49SChris Mason different_trans = 1; 996702ed49SChris Mason ret = btrfs_inc_ref(trans, root, buf); 1006702ed49SChris Mason if (ret) 1016702ed49SChris Mason return ret; 1026702ed49SChris Mason } else { 1036702ed49SChris Mason clean_tree_block(trans, root, buf); 1046702ed49SChris Mason } 1056702ed49SChris Mason 1066702ed49SChris Mason if (buf == root->node) { 1076702ed49SChris Mason root->node = cow; 1085f39d397SChris Mason extent_buffer_get(cow); 1096702ed49SChris Mason if (buf != root->commit_root) { 110db94535dSChris Mason btrfs_free_extent(trans, root, buf->start, 111db94535dSChris Mason buf->len, 1); 1126702ed49SChris Mason } 1135f39d397SChris Mason free_extent_buffer(buf); 1146702ed49SChris Mason } else { 1155f39d397SChris Mason btrfs_set_node_blockptr(parent, parent_slot, 116db94535dSChris Mason cow->start); 1176702ed49SChris Mason btrfs_mark_buffer_dirty(parent); 1185f39d397SChris Mason WARN_ON(btrfs_header_generation(parent) != trans->transid); 119db94535dSChris Mason btrfs_free_extent(trans, root, buf->start, buf->len, 1); 1206702ed49SChris Mason } 1215f39d397SChris Mason free_extent_buffer(buf); 1226702ed49SChris Mason btrfs_mark_buffer_dirty(cow); 1236702ed49SChris Mason *cow_ret = cow; 1246702ed49SChris Mason return 0; 1256702ed49SChris Mason } 1266702ed49SChris Mason 1275f39d397SChris Mason int btrfs_cow_block(struct btrfs_trans_handle *trans, 1285f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *buf, 1295f39d397SChris Mason struct extent_buffer *parent, int parent_slot, 1305f39d397SChris Mason struct extent_buffer **cow_ret) 13102217ed2SChris Mason { 1326702ed49SChris Mason u64 search_start; 133f510cfecSChris Mason int ret; 134ccd467d6SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 135ccd467d6SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 136ccd467d6SChris Mason root->fs_info->running_transaction->transid); 137ccd467d6SChris Mason WARN_ON(1); 138ccd467d6SChris Mason } 139ccd467d6SChris Mason if (trans->transid != root->fs_info->generation) { 140ccd467d6SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 141ccd467d6SChris Mason root->fs_info->generation); 142ccd467d6SChris Mason WARN_ON(1); 143ccd467d6SChris Mason } 1445f39d397SChris Mason if (btrfs_header_generation(buf) == trans->transid) { 14502217ed2SChris Mason *cow_ret = buf; 14602217ed2SChris Mason return 0; 14702217ed2SChris Mason } 1486702ed49SChris Mason 149db94535dSChris Mason search_start = buf->start & ~((u64)BTRFS_BLOCK_GROUP_SIZE - 1); 150f510cfecSChris Mason ret = __btrfs_cow_block(trans, root, buf, parent, 1516702ed49SChris Mason parent_slot, cow_ret, search_start, 0); 152f510cfecSChris Mason return ret; 1532c90e5d6SChris Mason } 1546702ed49SChris Mason 1556b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize) 1566702ed49SChris Mason { 1576b80053dSChris Mason if (blocknr < other && other - (blocknr + blocksize) < 32768) 1586702ed49SChris Mason return 1; 1596b80053dSChris Mason if (blocknr > other && blocknr - (other + blocksize) < 32768) 1606702ed49SChris Mason return 1; 16102217ed2SChris Mason return 0; 16202217ed2SChris Mason } 16302217ed2SChris Mason 1646702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans, 1655f39d397SChris Mason struct btrfs_root *root, struct extent_buffer *parent, 166a6b6e75eSChris Mason int start_slot, int cache_only, u64 *last_ret, 167a6b6e75eSChris Mason struct btrfs_key *progress) 1686702ed49SChris Mason { 1696b80053dSChris Mason struct extent_buffer *cur; 1706b80053dSChris Mason struct extent_buffer *tmp; 1716702ed49SChris Mason u64 blocknr; 172e9d0b13bSChris Mason u64 search_start = *last_ret; 173e9d0b13bSChris Mason u64 last_block = 0; 1746702ed49SChris Mason u64 other; 1756702ed49SChris Mason u32 parent_nritems; 1766702ed49SChris Mason int end_slot; 1776702ed49SChris Mason int i; 1786702ed49SChris Mason int err = 0; 179f2183bdeSChris Mason int parent_level; 1806b80053dSChris Mason int uptodate; 1816b80053dSChris Mason u32 blocksize; 1826702ed49SChris Mason 1835708b959SChris Mason parent_level = btrfs_header_level(parent); 1845708b959SChris Mason if (cache_only && parent_level != 1) 1855708b959SChris Mason return 0; 1865708b959SChris Mason 1876702ed49SChris Mason if (trans->transaction != root->fs_info->running_transaction) { 1886702ed49SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 1896702ed49SChris Mason root->fs_info->running_transaction->transid); 1906702ed49SChris Mason WARN_ON(1); 1916702ed49SChris Mason } 1926702ed49SChris Mason if (trans->transid != root->fs_info->generation) { 1936702ed49SChris Mason printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid, 1946702ed49SChris Mason root->fs_info->generation); 1956702ed49SChris Mason WARN_ON(1); 1966702ed49SChris Mason } 19786479a04SChris Mason 1986b80053dSChris Mason parent_nritems = btrfs_header_nritems(parent); 1996b80053dSChris Mason blocksize = btrfs_level_size(root, parent_level - 1); 2006702ed49SChris Mason end_slot = parent_nritems; 2016702ed49SChris Mason 2026702ed49SChris Mason if (parent_nritems == 1) 2036702ed49SChris Mason return 0; 2046702ed49SChris Mason 2056702ed49SChris Mason for (i = start_slot; i < end_slot; i++) { 2066702ed49SChris Mason int close = 1; 207a6b6e75eSChris Mason 2085708b959SChris Mason if (!parent->map_token) { 2095708b959SChris Mason map_extent_buffer(parent, 2105708b959SChris Mason btrfs_node_key_ptr_offset(i), 2115708b959SChris Mason sizeof(struct btrfs_key_ptr), 2125708b959SChris Mason &parent->map_token, &parent->kaddr, 2135708b959SChris Mason &parent->map_start, &parent->map_len, 2145708b959SChris Mason KM_USER1); 2155708b959SChris Mason } 2166b80053dSChris Mason blocknr = btrfs_node_blockptr(parent, i); 217e9d0b13bSChris Mason if (last_block == 0) 218e9d0b13bSChris Mason last_block = blocknr; 2195708b959SChris Mason 2206702ed49SChris Mason if (i > 0) { 2216b80053dSChris Mason other = btrfs_node_blockptr(parent, i - 1); 2226b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 2236702ed49SChris Mason } 2245708b959SChris Mason if (close && i < end_slot - 2) { 2256b80053dSChris Mason other = btrfs_node_blockptr(parent, i + 1); 2266b80053dSChris Mason close = close_blocks(blocknr, other, blocksize); 2276702ed49SChris Mason } 228e9d0b13bSChris Mason if (close) { 229e9d0b13bSChris Mason last_block = blocknr; 2306702ed49SChris Mason continue; 231e9d0b13bSChris Mason } 2325708b959SChris Mason if (parent->map_token) { 2335708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 2345708b959SChris Mason KM_USER1); 2355708b959SChris Mason parent->map_token = NULL; 2365708b959SChris Mason } 2376702ed49SChris Mason 2386b80053dSChris Mason cur = btrfs_find_tree_block(root, blocknr, blocksize); 2396b80053dSChris Mason if (cur) 2406b80053dSChris Mason uptodate = btrfs_buffer_uptodate(cur); 2416b80053dSChris Mason else 2426b80053dSChris Mason uptodate = 0; 2435708b959SChris Mason if (!cur || !uptodate) { 2446702ed49SChris Mason if (cache_only) { 2456b80053dSChris Mason free_extent_buffer(cur); 2466702ed49SChris Mason continue; 2476702ed49SChris Mason } 2486b80053dSChris Mason if (!cur) { 2496b80053dSChris Mason cur = read_tree_block(root, blocknr, 2506b80053dSChris Mason blocksize); 2516b80053dSChris Mason } else if (!uptodate) { 2526b80053dSChris Mason btrfs_read_buffer(cur); 2536702ed49SChris Mason } 254f2183bdeSChris Mason } 255e9d0b13bSChris Mason if (search_start == 0) 2566b80053dSChris Mason search_start = last_block; 257e9d0b13bSChris Mason 2586b80053dSChris Mason err = __btrfs_cow_block(trans, root, cur, parent, i, 2596b80053dSChris Mason &tmp, search_start, 2606b80053dSChris Mason min(16 * blocksize, 2616b80053dSChris Mason (end_slot - i) * blocksize)); 262252c38f0SYan if (err) { 2636b80053dSChris Mason free_extent_buffer(cur); 2646702ed49SChris Mason break; 265252c38f0SYan } 2666b80053dSChris Mason search_start = tmp->start; 2675708b959SChris Mason last_block = tmp->start; 268f2183bdeSChris Mason *last_ret = search_start; 269f2183bdeSChris Mason if (parent_level == 1) 2706b80053dSChris Mason btrfs_clear_buffer_defrag(tmp); 2716b80053dSChris Mason free_extent_buffer(tmp); 2726702ed49SChris Mason } 2735708b959SChris Mason if (parent->map_token) { 2745708b959SChris Mason unmap_extent_buffer(parent, parent->map_token, 2755708b959SChris Mason KM_USER1); 2765708b959SChris Mason parent->map_token = NULL; 2775708b959SChris Mason } 2786702ed49SChris Mason return err; 2796702ed49SChris Mason } 2806702ed49SChris Mason 28174123bd7SChris Mason /* 28274123bd7SChris Mason * The leaf data grows from end-to-front in the node. 28374123bd7SChris Mason * this returns the address of the start of the last item, 28474123bd7SChris Mason * which is the stop of the leaf data stack 28574123bd7SChris Mason */ 286123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 2875f39d397SChris Mason struct extent_buffer *leaf) 288be0e5c09SChris Mason { 2895f39d397SChris Mason u32 nr = btrfs_header_nritems(leaf); 290be0e5c09SChris Mason if (nr == 0) 291123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 2925f39d397SChris Mason return btrfs_item_offset_nr(leaf, nr - 1); 293be0e5c09SChris Mason } 294be0e5c09SChris Mason 29574123bd7SChris Mason /* 29674123bd7SChris Mason * compare two keys in a memcmp fashion 29774123bd7SChris Mason */ 2989aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 299be0e5c09SChris Mason { 300e2fa7227SChris Mason struct btrfs_key k1; 301e2fa7227SChris Mason 302e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 303e2fa7227SChris Mason 304e2fa7227SChris Mason if (k1.objectid > k2->objectid) 305be0e5c09SChris Mason return 1; 306e2fa7227SChris Mason if (k1.objectid < k2->objectid) 307be0e5c09SChris Mason return -1; 3085f39d397SChris Mason if (k1.type > k2->type) 309f254e52cSChris Mason return 1; 3105f39d397SChris Mason if (k1.type < k2->type) 311f254e52cSChris Mason return -1; 31270b2befdSChris Mason if (k1.offset > k2->offset) 31370b2befdSChris Mason return 1; 31470b2befdSChris Mason if (k1.offset < k2->offset) 31570b2befdSChris Mason return -1; 316be0e5c09SChris Mason return 0; 317be0e5c09SChris Mason } 31874123bd7SChris Mason 319123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 320123abc88SChris Mason int level) 321aa5d6bedSChris Mason { 3225f39d397SChris Mason struct extent_buffer *parent = NULL; 3235f39d397SChris Mason struct extent_buffer *node = path->nodes[level]; 3245f39d397SChris Mason struct btrfs_disk_key parent_key; 3255f39d397SChris Mason struct btrfs_disk_key node_key; 326aa5d6bedSChris Mason int parent_slot; 3278d7be552SChris Mason int slot; 3288d7be552SChris Mason struct btrfs_key cpukey; 3295f39d397SChris Mason u32 nritems = btrfs_header_nritems(node); 330aa5d6bedSChris Mason 331aa5d6bedSChris Mason if (path->nodes[level + 1]) 3325f39d397SChris Mason parent = path->nodes[level + 1]; 333a1f39630SAneesh 3348d7be552SChris Mason slot = path->slots[level]; 3357518a238SChris Mason BUG_ON(nritems == 0); 3367518a238SChris Mason if (parent) { 337a1f39630SAneesh parent_slot = path->slots[level + 1]; 3385f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 3395f39d397SChris Mason btrfs_node_key(node, &node_key, 0); 3405f39d397SChris Mason BUG_ON(memcmp(&parent_key, &node_key, 341e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 3421d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 343db94535dSChris Mason btrfs_header_bytenr(node)); 344aa5d6bedSChris Mason } 345123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 3468d7be552SChris Mason if (slot != 0) { 3475f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot - 1); 3485f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 3495f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) <= 0); 3508d7be552SChris Mason } 3518d7be552SChris Mason if (slot < nritems - 1) { 3525f39d397SChris Mason btrfs_node_key_to_cpu(node, &cpukey, slot + 1); 3535f39d397SChris Mason btrfs_node_key(node, &node_key, slot); 3545f39d397SChris Mason BUG_ON(comp_keys(&node_key, &cpukey) >= 0); 355aa5d6bedSChris Mason } 356aa5d6bedSChris Mason return 0; 357aa5d6bedSChris Mason } 358aa5d6bedSChris Mason 359123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 360123abc88SChris Mason int level) 361aa5d6bedSChris Mason { 3625f39d397SChris Mason struct extent_buffer *leaf = path->nodes[level]; 3635f39d397SChris Mason struct extent_buffer *parent = NULL; 364aa5d6bedSChris Mason int parent_slot; 3658d7be552SChris Mason struct btrfs_key cpukey; 3665f39d397SChris Mason struct btrfs_disk_key parent_key; 3675f39d397SChris Mason struct btrfs_disk_key leaf_key; 3685f39d397SChris Mason int slot = path->slots[0]; 3698d7be552SChris Mason 3705f39d397SChris Mason u32 nritems = btrfs_header_nritems(leaf); 371aa5d6bedSChris Mason 372aa5d6bedSChris Mason if (path->nodes[level + 1]) 3735f39d397SChris Mason parent = path->nodes[level + 1]; 3747518a238SChris Mason 3757518a238SChris Mason if (nritems == 0) 3767518a238SChris Mason return 0; 3777518a238SChris Mason 3787518a238SChris Mason if (parent) { 379a1f39630SAneesh parent_slot = path->slots[level + 1]; 3805f39d397SChris Mason btrfs_node_key(parent, &parent_key, parent_slot); 3815f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, 0); 3826702ed49SChris Mason 3835f39d397SChris Mason BUG_ON(memcmp(&parent_key, &leaf_key, 384e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 3851d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 386db94535dSChris Mason btrfs_header_bytenr(leaf)); 387aa5d6bedSChris Mason } 3885f39d397SChris Mason #if 0 3895f39d397SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 3905f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, i + 1); 3915f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, i); 3925f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) >= 0) { 3935f39d397SChris Mason btrfs_print_leaf(root, leaf); 3945f39d397SChris Mason printk("slot %d offset bad key\n", i); 3955f39d397SChris Mason BUG_ON(1); 3965f39d397SChris Mason } 3975f39d397SChris Mason if (btrfs_item_offset_nr(leaf, i) != 3985f39d397SChris Mason btrfs_item_end_nr(leaf, i + 1)) { 3995f39d397SChris Mason btrfs_print_leaf(root, leaf); 4005f39d397SChris Mason printk("slot %d offset bad\n", i); 4015f39d397SChris Mason BUG_ON(1); 4025f39d397SChris Mason } 4035f39d397SChris Mason if (i == 0) { 4045f39d397SChris Mason if (btrfs_item_offset_nr(leaf, i) + 4055f39d397SChris Mason btrfs_item_size_nr(leaf, i) != 4065f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 4075f39d397SChris Mason btrfs_print_leaf(root, leaf); 4085f39d397SChris Mason printk("slot %d first offset bad\n", i); 4095f39d397SChris Mason BUG_ON(1); 4105f39d397SChris Mason } 4115f39d397SChris Mason } 4125f39d397SChris Mason } 4135f39d397SChris Mason if (nritems > 0) { 4145f39d397SChris Mason if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) { 4155f39d397SChris Mason btrfs_print_leaf(root, leaf); 4165f39d397SChris Mason printk("slot %d bad size \n", nritems - 1); 4175f39d397SChris Mason BUG_ON(1); 4185f39d397SChris Mason } 4195f39d397SChris Mason } 4205f39d397SChris Mason #endif 4215f39d397SChris Mason if (slot != 0 && slot < nritems - 1) { 4225f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 4235f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1); 4245f39d397SChris Mason if (comp_keys(&leaf_key, &cpukey) <= 0) { 4255f39d397SChris Mason btrfs_print_leaf(root, leaf); 4265f39d397SChris Mason printk("slot %d offset bad key\n", slot); 4275f39d397SChris Mason BUG_ON(1); 4285f39d397SChris Mason } 4295f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot - 1) != 4305f39d397SChris Mason btrfs_item_end_nr(leaf, slot)) { 4315f39d397SChris Mason btrfs_print_leaf(root, leaf); 4325f39d397SChris Mason printk("slot %d offset bad\n", slot); 4335f39d397SChris Mason BUG_ON(1); 4345f39d397SChris Mason } 435aa5d6bedSChris Mason } 4368d7be552SChris Mason if (slot < nritems - 1) { 4375f39d397SChris Mason btrfs_item_key(leaf, &leaf_key, slot); 4385f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1); 4395f39d397SChris Mason BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0); 4405f39d397SChris Mason if (btrfs_item_offset_nr(leaf, slot) != 4415f39d397SChris Mason btrfs_item_end_nr(leaf, slot + 1)) { 4425f39d397SChris Mason btrfs_print_leaf(root, leaf); 4435f39d397SChris Mason printk("slot %d offset bad\n", slot); 4445f39d397SChris Mason BUG_ON(1); 445aa5d6bedSChris Mason } 4465f39d397SChris Mason } 4475f39d397SChris Mason BUG_ON(btrfs_item_offset_nr(leaf, 0) + 4485f39d397SChris Mason btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root)); 449aa5d6bedSChris Mason return 0; 450aa5d6bedSChris Mason } 451aa5d6bedSChris Mason 452123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 453123abc88SChris Mason int level) 454aa5d6bedSChris Mason { 455810191ffSChris Mason return 0; 456db94535dSChris Mason #if 0 4575f39d397SChris Mason struct extent_buffer *buf = path->nodes[level]; 4585f39d397SChris Mason 459479965d6SChris Mason if (memcmp_extent_buffer(buf, root->fs_info->fsid, 460479965d6SChris Mason (unsigned long)btrfs_header_fsid(buf), 461479965d6SChris Mason BTRFS_FSID_SIZE)) { 4625f39d397SChris Mason printk("warning bad block %Lu\n", buf->start); 463db94535dSChris Mason return 1; 4645f39d397SChris Mason } 465db94535dSChris Mason #endif 466aa5d6bedSChris Mason if (level == 0) 467123abc88SChris Mason return check_leaf(root, path, level); 468123abc88SChris Mason return check_node(root, path, level); 469aa5d6bedSChris Mason } 470aa5d6bedSChris Mason 47174123bd7SChris Mason /* 4725f39d397SChris Mason * search for key in the extent_buffer. The items start at offset p, 4735f39d397SChris Mason * and they are item_size apart. There are 'max' items in p. 4745f39d397SChris Mason * 47574123bd7SChris Mason * the slot in the array is returned via slot, and it points to 47674123bd7SChris Mason * the place where you would insert key if it is not found in 47774123bd7SChris Mason * the array. 47874123bd7SChris Mason * 47974123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 48074123bd7SChris Mason */ 4815f39d397SChris Mason static int generic_bin_search(struct extent_buffer *eb, unsigned long p, 4825f39d397SChris Mason int item_size, struct btrfs_key *key, 483be0e5c09SChris Mason int max, int *slot) 484be0e5c09SChris Mason { 485be0e5c09SChris Mason int low = 0; 486be0e5c09SChris Mason int high = max; 487be0e5c09SChris Mason int mid; 488be0e5c09SChris Mason int ret; 489479965d6SChris Mason struct btrfs_disk_key *tmp = NULL; 4905f39d397SChris Mason struct btrfs_disk_key unaligned; 4915f39d397SChris Mason unsigned long offset; 4925f39d397SChris Mason char *map_token = NULL; 4935f39d397SChris Mason char *kaddr = NULL; 4945f39d397SChris Mason unsigned long map_start = 0; 4955f39d397SChris Mason unsigned long map_len = 0; 496479965d6SChris Mason int err; 497be0e5c09SChris Mason 498be0e5c09SChris Mason while(low < high) { 499be0e5c09SChris Mason mid = (low + high) / 2; 5005f39d397SChris Mason offset = p + mid * item_size; 5015f39d397SChris Mason 5025f39d397SChris Mason if (!map_token || offset < map_start || 5035f39d397SChris Mason (offset + sizeof(struct btrfs_disk_key)) > 5045f39d397SChris Mason map_start + map_len) { 505479965d6SChris Mason if (map_token) { 5065f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 507479965d6SChris Mason map_token = NULL; 508479965d6SChris Mason } 509479965d6SChris Mason err = map_extent_buffer(eb, offset, 510479965d6SChris Mason sizeof(struct btrfs_disk_key), 511479965d6SChris Mason &map_token, &kaddr, 5125f39d397SChris Mason &map_start, &map_len, KM_USER0); 5135f39d397SChris Mason 514479965d6SChris Mason if (!err) { 515479965d6SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 516479965d6SChris Mason map_start); 517479965d6SChris Mason } else { 5185f39d397SChris Mason read_extent_buffer(eb, &unaligned, 5195f39d397SChris Mason offset, sizeof(unaligned)); 5205f39d397SChris Mason tmp = &unaligned; 521479965d6SChris Mason } 522479965d6SChris Mason 5235f39d397SChris Mason } else { 5245f39d397SChris Mason tmp = (struct btrfs_disk_key *)(kaddr + offset - 5255f39d397SChris Mason map_start); 5265f39d397SChris Mason } 527be0e5c09SChris Mason ret = comp_keys(tmp, key); 528be0e5c09SChris Mason 529be0e5c09SChris Mason if (ret < 0) 530be0e5c09SChris Mason low = mid + 1; 531be0e5c09SChris Mason else if (ret > 0) 532be0e5c09SChris Mason high = mid; 533be0e5c09SChris Mason else { 534be0e5c09SChris Mason *slot = mid; 535479965d6SChris Mason if (map_token) 5365f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 537be0e5c09SChris Mason return 0; 538be0e5c09SChris Mason } 539be0e5c09SChris Mason } 540be0e5c09SChris Mason *slot = low; 5415f39d397SChris Mason if (map_token) 5425f39d397SChris Mason unmap_extent_buffer(eb, map_token, KM_USER0); 543be0e5c09SChris Mason return 1; 544be0e5c09SChris Mason } 545be0e5c09SChris Mason 54697571fd0SChris Mason /* 54797571fd0SChris Mason * simple bin_search frontend that does the right thing for 54897571fd0SChris Mason * leaves vs nodes 54997571fd0SChris Mason */ 5505f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key, 5515f39d397SChris Mason int level, int *slot) 552be0e5c09SChris Mason { 5535f39d397SChris Mason if (level == 0) { 5545f39d397SChris Mason return generic_bin_search(eb, 5555f39d397SChris Mason offsetof(struct btrfs_leaf, items), 5560783fcfcSChris Mason sizeof(struct btrfs_item), 5575f39d397SChris Mason key, btrfs_header_nritems(eb), 5587518a238SChris Mason slot); 559be0e5c09SChris Mason } else { 5605f39d397SChris Mason return generic_bin_search(eb, 5615f39d397SChris Mason offsetof(struct btrfs_node, ptrs), 562123abc88SChris Mason sizeof(struct btrfs_key_ptr), 5635f39d397SChris Mason key, btrfs_header_nritems(eb), 5647518a238SChris Mason slot); 565be0e5c09SChris Mason } 566be0e5c09SChris Mason return -1; 567be0e5c09SChris Mason } 568be0e5c09SChris Mason 5695f39d397SChris Mason static struct extent_buffer *read_node_slot(struct btrfs_root *root, 5705f39d397SChris Mason struct extent_buffer *parent, int slot) 571bb803951SChris Mason { 572bb803951SChris Mason if (slot < 0) 573bb803951SChris Mason return NULL; 5745f39d397SChris Mason if (slot >= btrfs_header_nritems(parent)) 575bb803951SChris Mason return NULL; 576db94535dSChris Mason return read_tree_block(root, btrfs_node_blockptr(parent, slot), 577db94535dSChris Mason btrfs_level_size(root, btrfs_header_level(parent) - 1)); 578bb803951SChris Mason } 579bb803951SChris Mason 580e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 581e089f05cSChris Mason *root, struct btrfs_path *path, int level) 582bb803951SChris Mason { 5835f39d397SChris Mason struct extent_buffer *right = NULL; 5845f39d397SChris Mason struct extent_buffer *mid; 5855f39d397SChris Mason struct extent_buffer *left = NULL; 5865f39d397SChris Mason struct extent_buffer *parent = NULL; 587bb803951SChris Mason int ret = 0; 588bb803951SChris Mason int wret; 589bb803951SChris Mason int pslot; 590bb803951SChris Mason int orig_slot = path->slots[level]; 59154aa1f4dSChris Mason int err_on_enospc = 0; 59279f95c82SChris Mason u64 orig_ptr; 593bb803951SChris Mason 594bb803951SChris Mason if (level == 0) 595bb803951SChris Mason return 0; 596bb803951SChris Mason 5975f39d397SChris Mason mid = path->nodes[level]; 5981d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 59979f95c82SChris Mason 600234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 6015f39d397SChris Mason parent = path->nodes[level + 1]; 602bb803951SChris Mason pslot = path->slots[level + 1]; 603bb803951SChris Mason 60440689478SChris Mason /* 60540689478SChris Mason * deal with the case where there is only one pointer in the root 60640689478SChris Mason * by promoting the node below to a root 60740689478SChris Mason */ 6085f39d397SChris Mason if (!parent) { 6095f39d397SChris Mason struct extent_buffer *child; 610bb803951SChris Mason 6115f39d397SChris Mason if (btrfs_header_nritems(mid) != 1) 612bb803951SChris Mason return 0; 613bb803951SChris Mason 614bb803951SChris Mason /* promote the child to a root */ 6155f39d397SChris Mason child = read_node_slot(root, mid, 0); 616bb803951SChris Mason BUG_ON(!child); 617bb803951SChris Mason root->node = child; 618bb803951SChris Mason path->nodes[level] = NULL; 6195f39d397SChris Mason clean_tree_block(trans, root, mid); 6205f39d397SChris Mason wait_on_tree_block_writeback(root, mid); 621bb803951SChris Mason /* once for the path */ 6225f39d397SChris Mason free_extent_buffer(mid); 623db94535dSChris Mason ret = btrfs_free_extent(trans, root, mid->start, mid->len, 1); 624bb803951SChris Mason /* once for the root ptr */ 6255f39d397SChris Mason free_extent_buffer(mid); 626db94535dSChris Mason return ret; 627bb803951SChris Mason } 6285f39d397SChris Mason if (btrfs_header_nritems(mid) > 629123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 630bb803951SChris Mason return 0; 631bb803951SChris Mason 6325f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 63354aa1f4dSChris Mason err_on_enospc = 1; 63454aa1f4dSChris Mason 6355f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 6365f39d397SChris Mason if (left) { 6375f39d397SChris Mason wret = btrfs_cow_block(trans, root, left, 6385f39d397SChris Mason parent, pslot - 1, &left); 63954aa1f4dSChris Mason if (wret) { 64054aa1f4dSChris Mason ret = wret; 64154aa1f4dSChris Mason goto enospc; 64254aa1f4dSChris Mason } 6432cc58cf2SChris Mason } 6445f39d397SChris Mason right = read_node_slot(root, parent, pslot + 1); 6455f39d397SChris Mason if (right) { 6465f39d397SChris Mason wret = btrfs_cow_block(trans, root, right, 6475f39d397SChris Mason parent, pslot + 1, &right); 6482cc58cf2SChris Mason if (wret) { 6492cc58cf2SChris Mason ret = wret; 6502cc58cf2SChris Mason goto enospc; 6512cc58cf2SChris Mason } 6522cc58cf2SChris Mason } 6532cc58cf2SChris Mason 6542cc58cf2SChris Mason /* first, try to make some room in the middle buffer */ 6555f39d397SChris Mason if (left) { 6565f39d397SChris Mason orig_slot += btrfs_header_nritems(left); 6575f39d397SChris Mason wret = push_node_left(trans, root, left, mid); 65879f95c82SChris Mason if (wret < 0) 65979f95c82SChris Mason ret = wret; 6605f39d397SChris Mason if (btrfs_header_nritems(mid) < 2) 66154aa1f4dSChris Mason err_on_enospc = 1; 662bb803951SChris Mason } 66379f95c82SChris Mason 66479f95c82SChris Mason /* 66579f95c82SChris Mason * then try to empty the right most buffer into the middle 66679f95c82SChris Mason */ 6675f39d397SChris Mason if (right) { 6685f39d397SChris Mason wret = push_node_left(trans, root, mid, right); 66954aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 67079f95c82SChris Mason ret = wret; 6715f39d397SChris Mason if (btrfs_header_nritems(right) == 0) { 672db94535dSChris Mason u64 bytenr = right->start; 673db94535dSChris Mason u32 blocksize = right->len; 674db94535dSChris Mason 6755f39d397SChris Mason clean_tree_block(trans, root, right); 6765f39d397SChris Mason wait_on_tree_block_writeback(root, right); 6775f39d397SChris Mason free_extent_buffer(right); 678bb803951SChris Mason right = NULL; 679e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 680e089f05cSChris Mason 1); 681bb803951SChris Mason if (wret) 682bb803951SChris Mason ret = wret; 683db94535dSChris Mason wret = btrfs_free_extent(trans, root, bytenr, 684db94535dSChris Mason blocksize, 1); 685bb803951SChris Mason if (wret) 686bb803951SChris Mason ret = wret; 687bb803951SChris Mason } else { 6885f39d397SChris Mason struct btrfs_disk_key right_key; 6895f39d397SChris Mason btrfs_node_key(right, &right_key, 0); 6905f39d397SChris Mason btrfs_set_node_key(parent, &right_key, pslot + 1); 6915f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 692bb803951SChris Mason } 693bb803951SChris Mason } 6945f39d397SChris Mason if (btrfs_header_nritems(mid) == 1) { 69579f95c82SChris Mason /* 69679f95c82SChris Mason * we're not allowed to leave a node with one item in the 69779f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 69879f95c82SChris Mason * could try to delete the only pointer in this node. 69979f95c82SChris Mason * So, pull some keys from the left. 70079f95c82SChris Mason * There has to be a left pointer at this point because 70179f95c82SChris Mason * otherwise we would have pulled some pointers from the 70279f95c82SChris Mason * right 70379f95c82SChris Mason */ 7045f39d397SChris Mason BUG_ON(!left); 7055f39d397SChris Mason wret = balance_node_right(trans, root, mid, left); 70654aa1f4dSChris Mason if (wret < 0) { 70779f95c82SChris Mason ret = wret; 70854aa1f4dSChris Mason goto enospc; 70954aa1f4dSChris Mason } 71079f95c82SChris Mason BUG_ON(wret == 1); 71179f95c82SChris Mason } 7125f39d397SChris Mason if (btrfs_header_nritems(mid) == 0) { 71379f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 714db94535dSChris Mason u64 bytenr = mid->start; 715db94535dSChris Mason u32 blocksize = mid->len; 7165f39d397SChris Mason clean_tree_block(trans, root, mid); 7175f39d397SChris Mason wait_on_tree_block_writeback(root, mid); 7185f39d397SChris Mason free_extent_buffer(mid); 719bb803951SChris Mason mid = NULL; 720e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 721bb803951SChris Mason if (wret) 722bb803951SChris Mason ret = wret; 723db94535dSChris Mason wret = btrfs_free_extent(trans, root, bytenr, blocksize, 1); 724bb803951SChris Mason if (wret) 725bb803951SChris Mason ret = wret; 72679f95c82SChris Mason } else { 72779f95c82SChris Mason /* update the parent key to reflect our changes */ 7285f39d397SChris Mason struct btrfs_disk_key mid_key; 7295f39d397SChris Mason btrfs_node_key(mid, &mid_key, 0); 7305f39d397SChris Mason btrfs_set_node_key(parent, &mid_key, pslot); 7315f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 73279f95c82SChris Mason } 733bb803951SChris Mason 73479f95c82SChris Mason /* update the path */ 7355f39d397SChris Mason if (left) { 7365f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 7375f39d397SChris Mason extent_buffer_get(left); 7385f39d397SChris Mason path->nodes[level] = left; 739bb803951SChris Mason path->slots[level + 1] -= 1; 740bb803951SChris Mason path->slots[level] = orig_slot; 7415f39d397SChris Mason if (mid) 7425f39d397SChris Mason free_extent_buffer(mid); 743bb803951SChris Mason } else { 7445f39d397SChris Mason orig_slot -= btrfs_header_nritems(left); 745bb803951SChris Mason path->slots[level] = orig_slot; 746bb803951SChris Mason } 747bb803951SChris Mason } 74879f95c82SChris Mason /* double check we haven't messed things up */ 749123abc88SChris Mason check_block(root, path, level); 750e20d96d6SChris Mason if (orig_ptr != 7515f39d397SChris Mason btrfs_node_blockptr(path->nodes[level], path->slots[level])) 75279f95c82SChris Mason BUG(); 75354aa1f4dSChris Mason enospc: 7545f39d397SChris Mason if (right) 7555f39d397SChris Mason free_extent_buffer(right); 7565f39d397SChris Mason if (left) 7575f39d397SChris Mason free_extent_buffer(left); 758bb803951SChris Mason return ret; 759bb803951SChris Mason } 760bb803951SChris Mason 761e66f709bSChris Mason /* returns zero if the push worked, non-zero otherwise */ 762e66f709bSChris Mason static int push_nodes_for_insert(struct btrfs_trans_handle *trans, 763e66f709bSChris Mason struct btrfs_root *root, 764e66f709bSChris Mason struct btrfs_path *path, int level) 765e66f709bSChris Mason { 7665f39d397SChris Mason struct extent_buffer *right = NULL; 7675f39d397SChris Mason struct extent_buffer *mid; 7685f39d397SChris Mason struct extent_buffer *left = NULL; 7695f39d397SChris Mason struct extent_buffer *parent = NULL; 770e66f709bSChris Mason int ret = 0; 771e66f709bSChris Mason int wret; 772e66f709bSChris Mason int pslot; 773e66f709bSChris Mason int orig_slot = path->slots[level]; 774e66f709bSChris Mason u64 orig_ptr; 775e66f709bSChris Mason 776e66f709bSChris Mason if (level == 0) 777e66f709bSChris Mason return 1; 778e66f709bSChris Mason 7795f39d397SChris Mason mid = path->nodes[level]; 780e66f709bSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 781e66f709bSChris Mason 782e66f709bSChris Mason if (level < BTRFS_MAX_LEVEL - 1) 7835f39d397SChris Mason parent = path->nodes[level + 1]; 784e66f709bSChris Mason pslot = path->slots[level + 1]; 785e66f709bSChris Mason 7865f39d397SChris Mason if (!parent) 787e66f709bSChris Mason return 1; 788e66f709bSChris Mason 7895f39d397SChris Mason left = read_node_slot(root, parent, pslot - 1); 790e66f709bSChris Mason 791e66f709bSChris Mason /* first, try to make some room in the middle buffer */ 7925f39d397SChris Mason if (left) { 793e66f709bSChris Mason u32 left_nr; 7945f39d397SChris Mason left_nr = btrfs_header_nritems(left); 79533ade1f8SChris Mason if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 79633ade1f8SChris Mason wret = 1; 79733ade1f8SChris Mason } else { 7985f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, parent, 7995f39d397SChris Mason pslot - 1, &left); 80054aa1f4dSChris Mason if (ret) 80154aa1f4dSChris Mason wret = 1; 80254aa1f4dSChris Mason else { 80354aa1f4dSChris Mason wret = push_node_left(trans, root, 8045f39d397SChris Mason left, mid); 80554aa1f4dSChris Mason } 80633ade1f8SChris Mason } 807e66f709bSChris Mason if (wret < 0) 808e66f709bSChris Mason ret = wret; 809e66f709bSChris Mason if (wret == 0) { 8105f39d397SChris Mason struct btrfs_disk_key disk_key; 811e66f709bSChris Mason orig_slot += left_nr; 8125f39d397SChris Mason btrfs_node_key(mid, &disk_key, 0); 8135f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot); 8145f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 8155f39d397SChris Mason if (btrfs_header_nritems(left) > orig_slot) { 8165f39d397SChris Mason path->nodes[level] = left; 817e66f709bSChris Mason path->slots[level + 1] -= 1; 818e66f709bSChris Mason path->slots[level] = orig_slot; 8195f39d397SChris Mason free_extent_buffer(mid); 820e66f709bSChris Mason } else { 821e66f709bSChris Mason orig_slot -= 8225f39d397SChris Mason btrfs_header_nritems(left); 823e66f709bSChris Mason path->slots[level] = orig_slot; 8245f39d397SChris Mason free_extent_buffer(left); 825e66f709bSChris Mason } 826e66f709bSChris Mason return 0; 827e66f709bSChris Mason } 8285f39d397SChris Mason free_extent_buffer(left); 829e66f709bSChris Mason } 8305f39d397SChris Mason right= read_node_slot(root, parent, pslot + 1); 831e66f709bSChris Mason 832e66f709bSChris Mason /* 833e66f709bSChris Mason * then try to empty the right most buffer into the middle 834e66f709bSChris Mason */ 8355f39d397SChris Mason if (right) { 83633ade1f8SChris Mason u32 right_nr; 8375f39d397SChris Mason right_nr = btrfs_header_nritems(right); 83833ade1f8SChris Mason if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 83933ade1f8SChris Mason wret = 1; 84033ade1f8SChris Mason } else { 8415f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, 8425f39d397SChris Mason parent, pslot + 1, 8435f39d397SChris Mason &right); 84454aa1f4dSChris Mason if (ret) 84554aa1f4dSChris Mason wret = 1; 84654aa1f4dSChris Mason else { 84733ade1f8SChris Mason wret = balance_node_right(trans, root, 8485f39d397SChris Mason right, mid); 84933ade1f8SChris Mason } 85054aa1f4dSChris Mason } 851e66f709bSChris Mason if (wret < 0) 852e66f709bSChris Mason ret = wret; 853e66f709bSChris Mason if (wret == 0) { 8545f39d397SChris Mason struct btrfs_disk_key disk_key; 8555f39d397SChris Mason 8565f39d397SChris Mason btrfs_node_key(right, &disk_key, 0); 8575f39d397SChris Mason btrfs_set_node_key(parent, &disk_key, pslot + 1); 8585f39d397SChris Mason btrfs_mark_buffer_dirty(parent); 8595f39d397SChris Mason 8605f39d397SChris Mason if (btrfs_header_nritems(mid) <= orig_slot) { 8615f39d397SChris Mason path->nodes[level] = right; 862e66f709bSChris Mason path->slots[level + 1] += 1; 863e66f709bSChris Mason path->slots[level] = orig_slot - 8645f39d397SChris Mason btrfs_header_nritems(mid); 8655f39d397SChris Mason free_extent_buffer(mid); 866e66f709bSChris Mason } else { 8675f39d397SChris Mason free_extent_buffer(right); 868e66f709bSChris Mason } 869e66f709bSChris Mason return 0; 870e66f709bSChris Mason } 8715f39d397SChris Mason free_extent_buffer(right); 872e66f709bSChris Mason } 873e66f709bSChris Mason return 1; 874e66f709bSChris Mason } 875e66f709bSChris Mason 87674123bd7SChris Mason /* 8773c69faecSChris Mason * readahead one full node of leaves 8783c69faecSChris Mason */ 8793c69faecSChris Mason static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path, 8806702ed49SChris Mason int level, int slot) 8813c69faecSChris Mason { 8825f39d397SChris Mason struct extent_buffer *node; 8833c69faecSChris Mason u32 nritems; 8843c69faecSChris Mason u64 search; 8856b80053dSChris Mason u64 lowest_read; 8866b80053dSChris Mason u64 highest_read; 8876b80053dSChris Mason u64 nread = 0; 8883c69faecSChris Mason int direction = path->reada; 8895f39d397SChris Mason struct extent_buffer *eb; 8906b80053dSChris Mason u32 nr; 8916b80053dSChris Mason u32 blocksize; 8926b80053dSChris Mason u32 nscan = 0; 893db94535dSChris Mason 894a6b6e75eSChris Mason if (level != 1) 8953c69faecSChris Mason return; 8963c69faecSChris Mason 8976702ed49SChris Mason if (!path->nodes[level]) 8986702ed49SChris Mason return; 8996702ed49SChris Mason 9005f39d397SChris Mason node = path->nodes[level]; 9013c69faecSChris Mason search = btrfs_node_blockptr(node, slot); 9026b80053dSChris Mason blocksize = btrfs_level_size(root, level - 1); 9036b80053dSChris Mason eb = btrfs_find_tree_block(root, search, blocksize); 9045f39d397SChris Mason if (eb) { 9055f39d397SChris Mason free_extent_buffer(eb); 9063c69faecSChris Mason return; 9073c69faecSChris Mason } 9083c69faecSChris Mason 9096b80053dSChris Mason highest_read = search; 9106b80053dSChris Mason lowest_read = search; 9116b80053dSChris Mason 9125f39d397SChris Mason nritems = btrfs_header_nritems(node); 9136b80053dSChris Mason nr = slot; 9143c69faecSChris Mason while(1) { 9156b80053dSChris Mason if (direction < 0) { 9166b80053dSChris Mason if (nr == 0) 9173c69faecSChris Mason break; 9186b80053dSChris Mason nr--; 9196b80053dSChris Mason } else if (direction > 0) { 9206b80053dSChris Mason nr++; 9216b80053dSChris Mason if (nr >= nritems) 9226b80053dSChris Mason break; 9233c69faecSChris Mason } 9246b80053dSChris Mason search = btrfs_node_blockptr(node, nr); 9256b80053dSChris Mason if ((search >= lowest_read && search <= highest_read) || 9266b80053dSChris Mason (search < lowest_read && lowest_read - search <= 32768) || 9276b80053dSChris Mason (search > highest_read && search - highest_read <= 32768)) { 9286b80053dSChris Mason readahead_tree_block(root, search, blocksize); 9296b80053dSChris Mason nread += blocksize; 9303c69faecSChris Mason } 9316b80053dSChris Mason nscan++; 9326b80053dSChris Mason if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32)) 9336b80053dSChris Mason break; 9346b80053dSChris Mason if(nread > (1024 * 1024) || nscan > 128) 9356b80053dSChris Mason break; 9366b80053dSChris Mason 9376b80053dSChris Mason if (search < lowest_read) 9386b80053dSChris Mason lowest_read = search; 9396b80053dSChris Mason if (search > highest_read) 9406b80053dSChris Mason highest_read = search; 9413c69faecSChris Mason } 9423c69faecSChris Mason } 9433c69faecSChris Mason /* 94474123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 94574123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 94674123bd7SChris Mason * level of the path (level 0) 94774123bd7SChris Mason * 94874123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 949aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 950aa5d6bedSChris Mason * search a negative error number is returned. 95197571fd0SChris Mason * 95297571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 95397571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 95497571fd0SChris Mason * possible) 95574123bd7SChris Mason */ 956e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 957e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 958e089f05cSChris Mason ins_len, int cow) 959be0e5c09SChris Mason { 9605f39d397SChris Mason struct extent_buffer *b; 961db94535dSChris Mason u64 bytenr; 962be0e5c09SChris Mason int slot; 963be0e5c09SChris Mason int ret; 964be0e5c09SChris Mason int level; 9653c69faecSChris Mason int should_reada = p->reada; 9669f3a7427SChris Mason u8 lowest_level = 0; 9679f3a7427SChris Mason 9686702ed49SChris Mason lowest_level = p->lowest_level; 9696702ed49SChris Mason WARN_ON(lowest_level && ins_len); 97022b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 97122b0ebdaSChris Mason WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex)); 972bb803951SChris Mason again: 973bb803951SChris Mason b = root->node; 9745f39d397SChris Mason extent_buffer_get(b); 975eb60ceacSChris Mason while (b) { 9765f39d397SChris Mason level = btrfs_header_level(b); 97702217ed2SChris Mason if (cow) { 97802217ed2SChris Mason int wret; 979e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 980e20d96d6SChris Mason p->nodes[level + 1], 981e20d96d6SChris Mason p->slots[level + 1], 982252c38f0SYan &b); 98354aa1f4dSChris Mason if (wret) { 9845f39d397SChris Mason free_extent_buffer(b); 98554aa1f4dSChris Mason return wret; 98654aa1f4dSChris Mason } 98702217ed2SChris Mason } 98802217ed2SChris Mason BUG_ON(!cow && ins_len); 9895f39d397SChris Mason if (level != btrfs_header_level(b)) 9902c90e5d6SChris Mason WARN_ON(1); 9915f39d397SChris Mason level = btrfs_header_level(b); 992eb60ceacSChris Mason p->nodes[level] = b; 993123abc88SChris Mason ret = check_block(root, p, level); 994aa5d6bedSChris Mason if (ret) 995aa5d6bedSChris Mason return -1; 9965f39d397SChris Mason ret = bin_search(b, key, level, &slot); 9975f39d397SChris Mason if (level != 0) { 998be0e5c09SChris Mason if (ret && slot > 0) 999be0e5c09SChris Mason slot -= 1; 1000be0e5c09SChris Mason p->slots[level] = slot; 10015f39d397SChris Mason if (ins_len > 0 && btrfs_header_nritems(b) >= 1002d4dbff95SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 1) { 1003e089f05cSChris Mason int sret = split_node(trans, root, p, level); 10045c680ed6SChris Mason BUG_ON(sret > 0); 10055c680ed6SChris Mason if (sret) 10065c680ed6SChris Mason return sret; 10075c680ed6SChris Mason b = p->nodes[level]; 10085c680ed6SChris Mason slot = p->slots[level]; 1009bb803951SChris Mason } else if (ins_len < 0) { 1010e089f05cSChris Mason int sret = balance_level(trans, root, p, 1011e089f05cSChris Mason level); 1012bb803951SChris Mason if (sret) 1013bb803951SChris Mason return sret; 1014bb803951SChris Mason b = p->nodes[level]; 1015f510cfecSChris Mason if (!b) { 1016f510cfecSChris Mason btrfs_release_path(NULL, p); 1017bb803951SChris Mason goto again; 1018f510cfecSChris Mason } 1019bb803951SChris Mason slot = p->slots[level]; 10205f39d397SChris Mason BUG_ON(btrfs_header_nritems(b) == 1); 10215c680ed6SChris Mason } 10229f3a7427SChris Mason /* this is only true while dropping a snapshot */ 10239f3a7427SChris Mason if (level == lowest_level) 10249f3a7427SChris Mason break; 1025db94535dSChris Mason bytenr = btrfs_node_blockptr(b, slot); 10266702ed49SChris Mason if (should_reada) 10276702ed49SChris Mason reada_for_search(root, p, level, slot); 1028db94535dSChris Mason b = read_tree_block(root, bytenr, 1029db94535dSChris Mason btrfs_level_size(root, level - 1)); 1030be0e5c09SChris Mason } else { 1031be0e5c09SChris Mason p->slots[level] = slot; 10325f39d397SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, b) < 10330783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 1034d4dbff95SChris Mason int sret = split_leaf(trans, root, key, 1035cc0c5538SChris Mason p, ins_len, ret == 0); 10365c680ed6SChris Mason BUG_ON(sret > 0); 10375c680ed6SChris Mason if (sret) 10385c680ed6SChris Mason return sret; 10395c680ed6SChris Mason } 1040be0e5c09SChris Mason return ret; 1041be0e5c09SChris Mason } 1042be0e5c09SChris Mason } 1043aa5d6bedSChris Mason return 1; 1044be0e5c09SChris Mason } 1045be0e5c09SChris Mason 104674123bd7SChris Mason /* 104774123bd7SChris Mason * adjust the pointers going up the tree, starting at level 104874123bd7SChris Mason * making sure the right key of each node is points to 'key'. 104974123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 105074123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 105174123bd7SChris Mason * higher levels 1052aa5d6bedSChris Mason * 1053aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 1054aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 105574123bd7SChris Mason */ 10565f39d397SChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, 10575f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 10585f39d397SChris Mason struct btrfs_disk_key *key, int level) 1059be0e5c09SChris Mason { 1060be0e5c09SChris Mason int i; 1061aa5d6bedSChris Mason int ret = 0; 10625f39d397SChris Mason struct extent_buffer *t; 10635f39d397SChris Mason 1064234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 1065be0e5c09SChris Mason int tslot = path->slots[i]; 1066eb60ceacSChris Mason if (!path->nodes[i]) 1067be0e5c09SChris Mason break; 10685f39d397SChris Mason t = path->nodes[i]; 10695f39d397SChris Mason btrfs_set_node_key(t, key, tslot); 1070d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 1071be0e5c09SChris Mason if (tslot != 0) 1072be0e5c09SChris Mason break; 1073be0e5c09SChris Mason } 1074aa5d6bedSChris Mason return ret; 1075be0e5c09SChris Mason } 1076be0e5c09SChris Mason 107774123bd7SChris Mason /* 107874123bd7SChris Mason * try to push data from one node into the next node left in the 107979f95c82SChris Mason * tree. 1080aa5d6bedSChris Mason * 1081aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 1082aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 108374123bd7SChris Mason */ 1084e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 10855f39d397SChris Mason *root, struct extent_buffer *dst, 10865f39d397SChris Mason struct extent_buffer *src) 1087be0e5c09SChris Mason { 1088be0e5c09SChris Mason int push_items = 0; 1089bb803951SChris Mason int src_nritems; 1090bb803951SChris Mason int dst_nritems; 1091aa5d6bedSChris Mason int ret = 0; 1092be0e5c09SChris Mason 10935f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 10945f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1095123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 109654aa1f4dSChris Mason 1097eb60ceacSChris Mason if (push_items <= 0) { 1098be0e5c09SChris Mason return 1; 1099eb60ceacSChris Mason } 1100be0e5c09SChris Mason 1101be0e5c09SChris Mason if (src_nritems < push_items) 1102be0e5c09SChris Mason push_items = src_nritems; 110379f95c82SChris Mason 11045f39d397SChris Mason copy_extent_buffer(dst, src, 11055f39d397SChris Mason btrfs_node_key_ptr_offset(dst_nritems), 11065f39d397SChris Mason btrfs_node_key_ptr_offset(0), 1107123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 11085f39d397SChris Mason 1109bb803951SChris Mason if (push_items < src_nritems) { 11105f39d397SChris Mason memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0), 11115f39d397SChris Mason btrfs_node_key_ptr_offset(push_items), 1112e2fa7227SChris Mason (src_nritems - push_items) * 1113123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 1114bb803951SChris Mason } 11155f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 11165f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 11175f39d397SChris Mason btrfs_mark_buffer_dirty(src); 11185f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 1119bb803951SChris Mason return ret; 1120be0e5c09SChris Mason } 1121be0e5c09SChris Mason 112297571fd0SChris Mason /* 112379f95c82SChris Mason * try to push data from one node into the next node right in the 112479f95c82SChris Mason * tree. 112579f95c82SChris Mason * 112679f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 112779f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 112879f95c82SChris Mason * 112979f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 113079f95c82SChris Mason */ 11315f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, 11325f39d397SChris Mason struct btrfs_root *root, 11335f39d397SChris Mason struct extent_buffer *dst, 11345f39d397SChris Mason struct extent_buffer *src) 113579f95c82SChris Mason { 113679f95c82SChris Mason int push_items = 0; 113779f95c82SChris Mason int max_push; 113879f95c82SChris Mason int src_nritems; 113979f95c82SChris Mason int dst_nritems; 114079f95c82SChris Mason int ret = 0; 114179f95c82SChris Mason 11425f39d397SChris Mason src_nritems = btrfs_header_nritems(src); 11435f39d397SChris Mason dst_nritems = btrfs_header_nritems(dst); 1144123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 11455f39d397SChris Mason if (push_items <= 0) 114679f95c82SChris Mason return 1; 114779f95c82SChris Mason 114879f95c82SChris Mason max_push = src_nritems / 2 + 1; 114979f95c82SChris Mason /* don't try to empty the node */ 1150252c38f0SYan if (max_push >= src_nritems) 115179f95c82SChris Mason return 1; 1152252c38f0SYan 115379f95c82SChris Mason if (max_push < push_items) 115479f95c82SChris Mason push_items = max_push; 115579f95c82SChris Mason 11565f39d397SChris Mason memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items), 11575f39d397SChris Mason btrfs_node_key_ptr_offset(0), 11585f39d397SChris Mason (dst_nritems) * 11595f39d397SChris Mason sizeof(struct btrfs_key_ptr)); 1160d6025579SChris Mason 11615f39d397SChris Mason copy_extent_buffer(dst, src, 11625f39d397SChris Mason btrfs_node_key_ptr_offset(0), 11635f39d397SChris Mason btrfs_node_key_ptr_offset(src_nritems - push_items), 1164123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 116579f95c82SChris Mason 11665f39d397SChris Mason btrfs_set_header_nritems(src, src_nritems - push_items); 11675f39d397SChris Mason btrfs_set_header_nritems(dst, dst_nritems + push_items); 116879f95c82SChris Mason 11695f39d397SChris Mason btrfs_mark_buffer_dirty(src); 11705f39d397SChris Mason btrfs_mark_buffer_dirty(dst); 117179f95c82SChris Mason return ret; 117279f95c82SChris Mason } 117379f95c82SChris Mason 117479f95c82SChris Mason /* 117597571fd0SChris Mason * helper function to insert a new root level in the tree. 117697571fd0SChris Mason * A new node is allocated, and a single item is inserted to 117797571fd0SChris Mason * point to the existing root 1178aa5d6bedSChris Mason * 1179aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 118097571fd0SChris Mason */ 11815f39d397SChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, 11825f39d397SChris Mason struct btrfs_root *root, 11835f39d397SChris Mason struct btrfs_path *path, int level) 118474123bd7SChris Mason { 11855f39d397SChris Mason struct extent_buffer *lower; 11865f39d397SChris Mason struct extent_buffer *c; 11875f39d397SChris Mason struct btrfs_disk_key lower_key; 11885c680ed6SChris Mason 11895c680ed6SChris Mason BUG_ON(path->nodes[level]); 11905c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 11915c680ed6SChris Mason 1192db94535dSChris Mason c = btrfs_alloc_free_block(trans, root, root->nodesize, 1193db94535dSChris Mason root->node->start, 0); 11945f39d397SChris Mason if (IS_ERR(c)) 11955f39d397SChris Mason return PTR_ERR(c); 11965f39d397SChris Mason memset_extent_buffer(c, 0, 0, root->nodesize); 11975f39d397SChris Mason btrfs_set_header_nritems(c, 1); 11985f39d397SChris Mason btrfs_set_header_level(c, level); 1199db94535dSChris Mason btrfs_set_header_bytenr(c, c->start); 12005f39d397SChris Mason btrfs_set_header_generation(c, trans->transid); 12015f39d397SChris Mason btrfs_set_header_owner(c, root->root_key.objectid); 12025f39d397SChris Mason lower = path->nodes[level-1]; 1203d5719762SChris Mason 12045f39d397SChris Mason write_extent_buffer(c, root->fs_info->fsid, 12055f39d397SChris Mason (unsigned long)btrfs_header_fsid(c), 12065f39d397SChris Mason BTRFS_FSID_SIZE); 12075f39d397SChris Mason if (level == 1) 12085f39d397SChris Mason btrfs_item_key(lower, &lower_key, 0); 12095f39d397SChris Mason else 12105f39d397SChris Mason btrfs_node_key(lower, &lower_key, 0); 12115f39d397SChris Mason btrfs_set_node_key(c, &lower_key, 0); 1212db94535dSChris Mason btrfs_set_node_blockptr(c, 0, lower->start); 12135f39d397SChris Mason 12145f39d397SChris Mason btrfs_mark_buffer_dirty(c); 1215d5719762SChris Mason 1216cfaa7295SChris Mason /* the super has an extra ref to root->node */ 12175f39d397SChris Mason free_extent_buffer(root->node); 12185f39d397SChris Mason root->node = c; 12195f39d397SChris Mason extent_buffer_get(c); 12205f39d397SChris Mason path->nodes[level] = c; 122174123bd7SChris Mason path->slots[level] = 0; 122274123bd7SChris Mason return 0; 122374123bd7SChris Mason } 12245c680ed6SChris Mason 12255c680ed6SChris Mason /* 12265c680ed6SChris Mason * worker function to insert a single pointer in a node. 12275c680ed6SChris Mason * the node should have enough room for the pointer already 122897571fd0SChris Mason * 12295c680ed6SChris Mason * slot and level indicate where you want the key to go, and 12305c680ed6SChris Mason * blocknr is the block the key points to. 1231aa5d6bedSChris Mason * 1232aa5d6bedSChris Mason * returns zero on success and < 0 on any error 12335c680ed6SChris Mason */ 1234e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 1235e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 1236db94535dSChris Mason *key, u64 bytenr, int slot, int level) 12375c680ed6SChris Mason { 12385f39d397SChris Mason struct extent_buffer *lower; 12395c680ed6SChris Mason int nritems; 12405c680ed6SChris Mason 12415c680ed6SChris Mason BUG_ON(!path->nodes[level]); 12425f39d397SChris Mason lower = path->nodes[level]; 12435f39d397SChris Mason nritems = btrfs_header_nritems(lower); 124474123bd7SChris Mason if (slot > nritems) 124574123bd7SChris Mason BUG(); 1246123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 124774123bd7SChris Mason BUG(); 124874123bd7SChris Mason if (slot != nritems) { 12495f39d397SChris Mason memmove_extent_buffer(lower, 12505f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 12515f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 1252123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 125374123bd7SChris Mason } 12545f39d397SChris Mason btrfs_set_node_key(lower, key, slot); 1255db94535dSChris Mason btrfs_set_node_blockptr(lower, slot, bytenr); 12565f39d397SChris Mason btrfs_set_header_nritems(lower, nritems + 1); 12575f39d397SChris Mason btrfs_mark_buffer_dirty(lower); 125874123bd7SChris Mason return 0; 125974123bd7SChris Mason } 126074123bd7SChris Mason 126197571fd0SChris Mason /* 126297571fd0SChris Mason * split the node at the specified level in path in two. 126397571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 126497571fd0SChris Mason * 126597571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 126697571fd0SChris Mason * left and right, if either one works, it returns right away. 1267aa5d6bedSChris Mason * 1268aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 126997571fd0SChris Mason */ 1270e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 1271e089f05cSChris Mason *root, struct btrfs_path *path, int level) 1272be0e5c09SChris Mason { 12735f39d397SChris Mason struct extent_buffer *c; 12745f39d397SChris Mason struct extent_buffer *split; 12755f39d397SChris Mason struct btrfs_disk_key disk_key; 1276be0e5c09SChris Mason int mid; 12775c680ed6SChris Mason int ret; 1278aa5d6bedSChris Mason int wret; 12797518a238SChris Mason u32 c_nritems; 1280be0e5c09SChris Mason 12815f39d397SChris Mason c = path->nodes[level]; 12825f39d397SChris Mason if (c == root->node) { 12835c680ed6SChris Mason /* trying to split the root, lets make a new one */ 1284e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 12855c680ed6SChris Mason if (ret) 12865c680ed6SChris Mason return ret; 1287e66f709bSChris Mason } else { 1288e66f709bSChris Mason ret = push_nodes_for_insert(trans, root, path, level); 12895f39d397SChris Mason c = path->nodes[level]; 12905f39d397SChris Mason if (!ret && btrfs_header_nritems(c) < 1291e66f709bSChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) - 1) 1292e66f709bSChris Mason return 0; 129354aa1f4dSChris Mason if (ret < 0) 129454aa1f4dSChris Mason return ret; 12955c680ed6SChris Mason } 1296e66f709bSChris Mason 12975f39d397SChris Mason c_nritems = btrfs_header_nritems(c); 1298db94535dSChris Mason split = btrfs_alloc_free_block(trans, root, root->nodesize, 1299db94535dSChris Mason c->start, 0); 13005f39d397SChris Mason if (IS_ERR(split)) 13015f39d397SChris Mason return PTR_ERR(split); 130254aa1f4dSChris Mason 13035f39d397SChris Mason btrfs_set_header_flags(split, btrfs_header_flags(c)); 13045f39d397SChris Mason btrfs_set_header_level(split, btrfs_header_level(c)); 1305db94535dSChris Mason btrfs_set_header_bytenr(split, split->start); 13065f39d397SChris Mason btrfs_set_header_generation(split, trans->transid); 13075f39d397SChris Mason btrfs_set_header_owner(split, root->root_key.objectid); 13085f39d397SChris Mason write_extent_buffer(split, root->fs_info->fsid, 13095f39d397SChris Mason (unsigned long)btrfs_header_fsid(split), 13105f39d397SChris Mason BTRFS_FSID_SIZE); 13115f39d397SChris Mason 13127518a238SChris Mason mid = (c_nritems + 1) / 2; 13135f39d397SChris Mason 13145f39d397SChris Mason copy_extent_buffer(split, c, 13155f39d397SChris Mason btrfs_node_key_ptr_offset(0), 13165f39d397SChris Mason btrfs_node_key_ptr_offset(mid), 1317123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 13185f39d397SChris Mason btrfs_set_header_nritems(split, c_nritems - mid); 13195f39d397SChris Mason btrfs_set_header_nritems(c, mid); 1320aa5d6bedSChris Mason ret = 0; 1321aa5d6bedSChris Mason 13225f39d397SChris Mason btrfs_mark_buffer_dirty(c); 13235f39d397SChris Mason btrfs_mark_buffer_dirty(split); 13245f39d397SChris Mason 13255f39d397SChris Mason btrfs_node_key(split, &disk_key, 0); 1326db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, split->start, 13275f39d397SChris Mason path->slots[level + 1] + 1, 1328123abc88SChris Mason level + 1); 1329aa5d6bedSChris Mason if (wret) 1330aa5d6bedSChris Mason ret = wret; 1331aa5d6bedSChris Mason 13325de08d7dSChris Mason if (path->slots[level] >= mid) { 13335c680ed6SChris Mason path->slots[level] -= mid; 13345f39d397SChris Mason free_extent_buffer(c); 13355f39d397SChris Mason path->nodes[level] = split; 13365c680ed6SChris Mason path->slots[level + 1] += 1; 1337eb60ceacSChris Mason } else { 13385f39d397SChris Mason free_extent_buffer(split); 1339be0e5c09SChris Mason } 1340aa5d6bedSChris Mason return ret; 1341be0e5c09SChris Mason } 1342be0e5c09SChris Mason 134374123bd7SChris Mason /* 134474123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 134574123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 134674123bd7SChris Mason * space used both by the item structs and the item data 134774123bd7SChris Mason */ 13485f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr) 1349be0e5c09SChris Mason { 1350be0e5c09SChris Mason int data_len; 13515f39d397SChris Mason int nritems = btrfs_header_nritems(l); 1352d4dbff95SChris Mason int end = min(nritems, start + nr) - 1; 1353be0e5c09SChris Mason 1354be0e5c09SChris Mason if (!nr) 1355be0e5c09SChris Mason return 0; 13565f39d397SChris Mason data_len = btrfs_item_end_nr(l, start); 13575f39d397SChris Mason data_len = data_len - btrfs_item_offset_nr(l, end); 13580783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 1359d4dbff95SChris Mason WARN_ON(data_len < 0); 1360be0e5c09SChris Mason return data_len; 1361be0e5c09SChris Mason } 1362be0e5c09SChris Mason 136374123bd7SChris Mason /* 1364d4dbff95SChris Mason * The space between the end of the leaf items and 1365d4dbff95SChris Mason * the start of the leaf data. IOW, how much room 1366d4dbff95SChris Mason * the leaf has left for both items and data 1367d4dbff95SChris Mason */ 13685f39d397SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf) 1369d4dbff95SChris Mason { 13705f39d397SChris Mason int nritems = btrfs_header_nritems(leaf); 13715f39d397SChris Mason int ret; 13725f39d397SChris Mason ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems); 13735f39d397SChris Mason if (ret < 0) { 13745f39d397SChris Mason printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n", 1375ae2f5411SJens Axboe ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root), 13765f39d397SChris Mason leaf_space_used(leaf, 0, nritems), nritems); 13775f39d397SChris Mason } 13785f39d397SChris Mason return ret; 1379d4dbff95SChris Mason } 1380d4dbff95SChris Mason 1381d4dbff95SChris Mason /* 138200ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 138300ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 1384aa5d6bedSChris Mason * 1385aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 1386aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 138700ec4c51SChris Mason */ 1388e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 1389e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 139000ec4c51SChris Mason { 13915f39d397SChris Mason struct extent_buffer *left = path->nodes[0]; 13925f39d397SChris Mason struct extent_buffer *right; 13935f39d397SChris Mason struct extent_buffer *upper; 13945f39d397SChris Mason struct btrfs_disk_key disk_key; 139500ec4c51SChris Mason int slot; 139600ec4c51SChris Mason int i; 139700ec4c51SChris Mason int free_space; 139800ec4c51SChris Mason int push_space = 0; 139900ec4c51SChris Mason int push_items = 0; 14000783fcfcSChris Mason struct btrfs_item *item; 14017518a238SChris Mason u32 left_nritems; 14027518a238SChris Mason u32 right_nritems; 14035f39d397SChris Mason u32 data_end; 1404db94535dSChris Mason u32 this_item_size; 140554aa1f4dSChris Mason int ret; 140600ec4c51SChris Mason 140700ec4c51SChris Mason slot = path->slots[1]; 140800ec4c51SChris Mason if (!path->nodes[1]) { 140900ec4c51SChris Mason return 1; 141000ec4c51SChris Mason } 141100ec4c51SChris Mason upper = path->nodes[1]; 14125f39d397SChris Mason if (slot >= btrfs_header_nritems(upper) - 1) 141300ec4c51SChris Mason return 1; 14145f39d397SChris Mason 1415db94535dSChris Mason right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1), 1416db94535dSChris Mason root->leafsize); 1417123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 14180783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 14195f39d397SChris Mason free_extent_buffer(right); 142002217ed2SChris Mason return 1; 142102217ed2SChris Mason } 142202217ed2SChris Mason 14235f39d397SChris Mason /* cow and double check */ 14245f39d397SChris Mason ret = btrfs_cow_block(trans, root, right, upper, 14255f39d397SChris Mason slot + 1, &right); 14265f39d397SChris Mason if (ret) { 14275f39d397SChris Mason free_extent_buffer(right); 1428a429e513SChris Mason return 1; 1429a429e513SChris Mason } 14305f39d397SChris Mason free_space = btrfs_leaf_free_space(root, right); 14315f39d397SChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 14325f39d397SChris Mason free_extent_buffer(right); 14335f39d397SChris Mason return 1; 14345f39d397SChris Mason } 14355f39d397SChris Mason 14365f39d397SChris Mason left_nritems = btrfs_header_nritems(left); 14375f39d397SChris Mason if (left_nritems == 0) { 14385f39d397SChris Mason free_extent_buffer(right); 14395f39d397SChris Mason return 1; 14405f39d397SChris Mason } 14415f39d397SChris Mason 1442a429e513SChris Mason for (i = left_nritems - 1; i >= 1; i--) { 14435f39d397SChris Mason item = btrfs_item_nr(left, i); 1444db94535dSChris Mason 144500ec4c51SChris Mason if (path->slots[0] == i) 144600ec4c51SChris Mason push_space += data_size + sizeof(*item); 1447db94535dSChris Mason 1448db94535dSChris Mason if (!left->map_token) { 1449db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 1450db94535dSChris Mason sizeof(struct btrfs_item), 1451db94535dSChris Mason &left->map_token, &left->kaddr, 1452db94535dSChris Mason &left->map_start, &left->map_len, 1453db94535dSChris Mason KM_USER1); 1454db94535dSChris Mason } 1455db94535dSChris Mason 1456db94535dSChris Mason this_item_size = btrfs_item_size(left, item); 1457db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 145800ec4c51SChris Mason break; 145900ec4c51SChris Mason push_items++; 1460db94535dSChris Mason push_space += this_item_size + sizeof(*item); 1461db94535dSChris Mason } 1462db94535dSChris Mason if (left->map_token) { 1463db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 1464db94535dSChris Mason left->map_token = NULL; 146500ec4c51SChris Mason } 14665f39d397SChris Mason 146700ec4c51SChris Mason if (push_items == 0) { 14685f39d397SChris Mason free_extent_buffer(right); 146900ec4c51SChris Mason return 1; 147000ec4c51SChris Mason } 14715f39d397SChris Mason 1472a429e513SChris Mason if (push_items == left_nritems) 1473a429e513SChris Mason WARN_ON(1); 14745f39d397SChris Mason 147500ec4c51SChris Mason /* push left to right */ 14765f39d397SChris Mason right_nritems = btrfs_header_nritems(right); 14775f39d397SChris Mason push_space = btrfs_item_end_nr(left, left_nritems - push_items); 1478123abc88SChris Mason push_space -= leaf_data_end(root, left); 14795f39d397SChris Mason 148000ec4c51SChris Mason /* make room in the right data area */ 14815f39d397SChris Mason data_end = leaf_data_end(root, right); 14825f39d397SChris Mason memmove_extent_buffer(right, 14835f39d397SChris Mason btrfs_leaf_data(right) + data_end - push_space, 14845f39d397SChris Mason btrfs_leaf_data(right) + data_end, 14855f39d397SChris Mason BTRFS_LEAF_DATA_SIZE(root) - data_end); 14865f39d397SChris Mason 148700ec4c51SChris Mason /* copy from the left data area */ 14885f39d397SChris Mason copy_extent_buffer(right, left, btrfs_leaf_data(right) + 1489d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1490d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 1491d6025579SChris Mason push_space); 14925f39d397SChris Mason 14935f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(push_items), 14945f39d397SChris Mason btrfs_item_nr_offset(0), 14950783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 14965f39d397SChris Mason 149700ec4c51SChris Mason /* copy the items from left to right */ 14985f39d397SChris Mason copy_extent_buffer(right, left, btrfs_item_nr_offset(0), 14995f39d397SChris Mason btrfs_item_nr_offset(left_nritems - push_items), 15000783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 150100ec4c51SChris Mason 150200ec4c51SChris Mason /* update the item pointers */ 15037518a238SChris Mason right_nritems += push_items; 15045f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 1505123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1506db94535dSChris Mason 15077518a238SChris Mason for (i = 0; i < right_nritems; i++) { 15085f39d397SChris Mason item = btrfs_item_nr(right, i); 1509db94535dSChris Mason if (!right->map_token) { 1510db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 1511db94535dSChris Mason sizeof(struct btrfs_item), 1512db94535dSChris Mason &right->map_token, &right->kaddr, 1513db94535dSChris Mason &right->map_start, &right->map_len, 1514db94535dSChris Mason KM_USER1); 1515db94535dSChris Mason } 1516db94535dSChris Mason push_space -= btrfs_item_size(right, item); 1517db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 1518db94535dSChris Mason } 1519db94535dSChris Mason 1520db94535dSChris Mason if (right->map_token) { 1521db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 1522db94535dSChris Mason right->map_token = NULL; 152300ec4c51SChris Mason } 15247518a238SChris Mason left_nritems -= push_items; 15255f39d397SChris Mason btrfs_set_header_nritems(left, left_nritems); 152600ec4c51SChris Mason 15275f39d397SChris Mason btrfs_mark_buffer_dirty(left); 15285f39d397SChris Mason btrfs_mark_buffer_dirty(right); 1529a429e513SChris Mason 15305f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 15315f39d397SChris Mason btrfs_set_node_key(upper, &disk_key, slot + 1); 1532d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 153302217ed2SChris Mason 153400ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 15357518a238SChris Mason if (path->slots[0] >= left_nritems) { 15367518a238SChris Mason path->slots[0] -= left_nritems; 15375f39d397SChris Mason free_extent_buffer(path->nodes[0]); 15385f39d397SChris Mason path->nodes[0] = right; 153900ec4c51SChris Mason path->slots[1] += 1; 154000ec4c51SChris Mason } else { 15415f39d397SChris Mason free_extent_buffer(right); 154200ec4c51SChris Mason } 154300ec4c51SChris Mason return 0; 154400ec4c51SChris Mason } 154500ec4c51SChris Mason /* 154674123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 154774123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 154874123bd7SChris Mason */ 1549e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 1550e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1551be0e5c09SChris Mason { 15525f39d397SChris Mason struct btrfs_disk_key disk_key; 15535f39d397SChris Mason struct extent_buffer *right = path->nodes[0]; 15545f39d397SChris Mason struct extent_buffer *left; 1555be0e5c09SChris Mason int slot; 1556be0e5c09SChris Mason int i; 1557be0e5c09SChris Mason int free_space; 1558be0e5c09SChris Mason int push_space = 0; 1559be0e5c09SChris Mason int push_items = 0; 15600783fcfcSChris Mason struct btrfs_item *item; 15617518a238SChris Mason u32 old_left_nritems; 15625f39d397SChris Mason u32 right_nritems; 1563aa5d6bedSChris Mason int ret = 0; 1564aa5d6bedSChris Mason int wret; 1565db94535dSChris Mason u32 this_item_size; 1566db94535dSChris Mason u32 old_left_item_size; 1567be0e5c09SChris Mason 1568be0e5c09SChris Mason slot = path->slots[1]; 15695f39d397SChris Mason if (slot == 0) 1570be0e5c09SChris Mason return 1; 15715f39d397SChris Mason if (!path->nodes[1]) 1572be0e5c09SChris Mason return 1; 15735f39d397SChris Mason 15743685f791SChris Mason right_nritems = btrfs_header_nritems(right); 15753685f791SChris Mason if (right_nritems == 0) { 15763685f791SChris Mason return 1; 15773685f791SChris Mason } 15783685f791SChris Mason 15795f39d397SChris Mason left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1], 1580db94535dSChris Mason slot - 1), root->leafsize); 1581123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 15820783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 15835f39d397SChris Mason free_extent_buffer(left); 1584be0e5c09SChris Mason return 1; 1585be0e5c09SChris Mason } 158602217ed2SChris Mason 158702217ed2SChris Mason /* cow and double check */ 15885f39d397SChris Mason ret = btrfs_cow_block(trans, root, left, 15895f39d397SChris Mason path->nodes[1], slot - 1, &left); 159054aa1f4dSChris Mason if (ret) { 159154aa1f4dSChris Mason /* we hit -ENOSPC, but it isn't fatal here */ 15925f39d397SChris Mason free_extent_buffer(left); 159354aa1f4dSChris Mason return 1; 159454aa1f4dSChris Mason } 15953685f791SChris Mason 1596123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 15970783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 15985f39d397SChris Mason free_extent_buffer(left); 159902217ed2SChris Mason return 1; 160002217ed2SChris Mason } 160102217ed2SChris Mason 16025f39d397SChris Mason for (i = 0; i < right_nritems - 1; i++) { 16035f39d397SChris Mason item = btrfs_item_nr(right, i); 1604db94535dSChris Mason if (!right->map_token) { 1605db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 1606db94535dSChris Mason sizeof(struct btrfs_item), 1607db94535dSChris Mason &right->map_token, &right->kaddr, 1608db94535dSChris Mason &right->map_start, &right->map_len, 1609db94535dSChris Mason KM_USER1); 1610db94535dSChris Mason } 1611db94535dSChris Mason 1612be0e5c09SChris Mason if (path->slots[0] == i) 1613be0e5c09SChris Mason push_space += data_size + sizeof(*item); 1614db94535dSChris Mason 1615db94535dSChris Mason this_item_size = btrfs_item_size(right, item); 1616db94535dSChris Mason if (this_item_size + sizeof(*item) + push_space > free_space) 1617be0e5c09SChris Mason break; 1618db94535dSChris Mason 1619be0e5c09SChris Mason push_items++; 1620db94535dSChris Mason push_space += this_item_size + sizeof(*item); 1621be0e5c09SChris Mason } 1622db94535dSChris Mason 1623db94535dSChris Mason if (right->map_token) { 1624db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 1625db94535dSChris Mason right->map_token = NULL; 1626db94535dSChris Mason } 1627db94535dSChris Mason 1628be0e5c09SChris Mason if (push_items == 0) { 16295f39d397SChris Mason free_extent_buffer(left); 1630be0e5c09SChris Mason return 1; 1631be0e5c09SChris Mason } 16325f39d397SChris Mason if (push_items == btrfs_header_nritems(right)) 1633a429e513SChris Mason WARN_ON(1); 16345f39d397SChris Mason 1635be0e5c09SChris Mason /* push data from right to left */ 16365f39d397SChris Mason copy_extent_buffer(left, right, 16375f39d397SChris Mason btrfs_item_nr_offset(btrfs_header_nritems(left)), 16385f39d397SChris Mason btrfs_item_nr_offset(0), 16395f39d397SChris Mason push_items * sizeof(struct btrfs_item)); 16405f39d397SChris Mason 1641123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 16425f39d397SChris Mason btrfs_item_offset_nr(right, push_items -1); 16435f39d397SChris Mason 16445f39d397SChris Mason copy_extent_buffer(left, right, btrfs_leaf_data(left) + 1645d6025579SChris Mason leaf_data_end(root, left) - push_space, 1646123abc88SChris Mason btrfs_leaf_data(right) + 16475f39d397SChris Mason btrfs_item_offset_nr(right, push_items - 1), 1648be0e5c09SChris Mason push_space); 16495f39d397SChris Mason old_left_nritems = btrfs_header_nritems(left); 1650eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 1651eb60ceacSChris Mason 1652db94535dSChris Mason old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1); 1653be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 16545f39d397SChris Mason u32 ioff; 1655db94535dSChris Mason 16565f39d397SChris Mason item = btrfs_item_nr(left, i); 1657db94535dSChris Mason if (!left->map_token) { 1658db94535dSChris Mason map_extent_buffer(left, (unsigned long)item, 1659db94535dSChris Mason sizeof(struct btrfs_item), 1660db94535dSChris Mason &left->map_token, &left->kaddr, 1661db94535dSChris Mason &left->map_start, &left->map_len, 1662db94535dSChris Mason KM_USER1); 1663db94535dSChris Mason } 1664db94535dSChris Mason 16655f39d397SChris Mason ioff = btrfs_item_offset(left, item); 16665f39d397SChris Mason btrfs_set_item_offset(left, item, 1667db94535dSChris Mason ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size)); 1668be0e5c09SChris Mason } 16695f39d397SChris Mason btrfs_set_header_nritems(left, old_left_nritems + push_items); 1670db94535dSChris Mason if (left->map_token) { 1671db94535dSChris Mason unmap_extent_buffer(left, left->map_token, KM_USER1); 1672db94535dSChris Mason left->map_token = NULL; 1673db94535dSChris Mason } 1674be0e5c09SChris Mason 1675be0e5c09SChris Mason /* fixup right node */ 16765f39d397SChris Mason push_space = btrfs_item_offset_nr(right, push_items - 1) - 1677123abc88SChris Mason leaf_data_end(root, right); 16785f39d397SChris Mason memmove_extent_buffer(right, btrfs_leaf_data(right) + 1679d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1680d6025579SChris Mason btrfs_leaf_data(right) + 1681123abc88SChris Mason leaf_data_end(root, right), push_space); 16825f39d397SChris Mason 16835f39d397SChris Mason memmove_extent_buffer(right, btrfs_item_nr_offset(0), 16845f39d397SChris Mason btrfs_item_nr_offset(push_items), 16855f39d397SChris Mason (btrfs_header_nritems(right) - push_items) * 16860783fcfcSChris Mason sizeof(struct btrfs_item)); 16875f39d397SChris Mason 16885f39d397SChris Mason right_nritems = btrfs_header_nritems(right) - push_items; 16895f39d397SChris Mason btrfs_set_header_nritems(right, right_nritems); 1690123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1691eb60ceacSChris Mason 16925f39d397SChris Mason for (i = 0; i < right_nritems; i++) { 16935f39d397SChris Mason item = btrfs_item_nr(right, i); 1694db94535dSChris Mason 1695db94535dSChris Mason if (!right->map_token) { 1696db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 1697db94535dSChris Mason sizeof(struct btrfs_item), 1698db94535dSChris Mason &right->map_token, &right->kaddr, 1699db94535dSChris Mason &right->map_start, &right->map_len, 1700db94535dSChris Mason KM_USER1); 1701db94535dSChris Mason } 1702db94535dSChris Mason 1703db94535dSChris Mason push_space = push_space - btrfs_item_size(right, item); 1704db94535dSChris Mason btrfs_set_item_offset(right, item, push_space); 1705db94535dSChris Mason } 1706db94535dSChris Mason if (right->map_token) { 1707db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 1708db94535dSChris Mason right->map_token = NULL; 1709be0e5c09SChris Mason } 1710eb60ceacSChris Mason 17115f39d397SChris Mason btrfs_mark_buffer_dirty(left); 17125f39d397SChris Mason btrfs_mark_buffer_dirty(right); 1713098f59c2SChris Mason 17145f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 17155f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, 1); 1716aa5d6bedSChris Mason if (wret) 1717aa5d6bedSChris Mason ret = wret; 1718be0e5c09SChris Mason 1719be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1720be0e5c09SChris Mason if (path->slots[0] < push_items) { 1721be0e5c09SChris Mason path->slots[0] += old_left_nritems; 17225f39d397SChris Mason free_extent_buffer(path->nodes[0]); 17235f39d397SChris Mason path->nodes[0] = left; 1724be0e5c09SChris Mason path->slots[1] -= 1; 1725be0e5c09SChris Mason } else { 17265f39d397SChris Mason free_extent_buffer(left); 1727be0e5c09SChris Mason path->slots[0] -= push_items; 1728be0e5c09SChris Mason } 1729eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1730aa5d6bedSChris Mason return ret; 1731be0e5c09SChris Mason } 1732be0e5c09SChris Mason 173374123bd7SChris Mason /* 173474123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 173574123bd7SChris Mason * available for the resulting leaf level of the path. 1736aa5d6bedSChris Mason * 1737aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 173874123bd7SChris Mason */ 1739e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1740d4dbff95SChris Mason *root, struct btrfs_key *ins_key, 1741cc0c5538SChris Mason struct btrfs_path *path, int data_size, int extend) 1742be0e5c09SChris Mason { 17435f39d397SChris Mason struct extent_buffer *l; 17447518a238SChris Mason u32 nritems; 1745eb60ceacSChris Mason int mid; 1746eb60ceacSChris Mason int slot; 17475f39d397SChris Mason struct extent_buffer *right; 17480783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1749be0e5c09SChris Mason int data_copy_size; 1750be0e5c09SChris Mason int rt_data_off; 1751be0e5c09SChris Mason int i; 1752d4dbff95SChris Mason int ret = 0; 1753aa5d6bedSChris Mason int wret; 1754cc0c5538SChris Mason int double_split; 1755cc0c5538SChris Mason int num_doubles = 0; 1756d4dbff95SChris Mason struct btrfs_disk_key disk_key; 1757be0e5c09SChris Mason 1758cc0c5538SChris Mason if (extend) 1759cc0c5538SChris Mason space_needed = data_size; 1760cc0c5538SChris Mason 176140689478SChris Mason /* first try to make some room by pushing left and right */ 17623685f791SChris Mason if (ins_key->type != BTRFS_DIR_ITEM_KEY) { 17633685f791SChris Mason wret = push_leaf_right(trans, root, path, data_size); 17643326d1b0SChris Mason if (wret < 0) { 1765eaee50e8SChris Mason return wret; 17663326d1b0SChris Mason } 1767eaee50e8SChris Mason if (wret) { 17683685f791SChris Mason wret = push_leaf_left(trans, root, path, data_size); 1769eaee50e8SChris Mason if (wret < 0) 1770eaee50e8SChris Mason return wret; 1771eaee50e8SChris Mason } 17725f39d397SChris Mason l = path->nodes[0]; 1773aa5d6bedSChris Mason 1774aa5d6bedSChris Mason /* did the pushes work? */ 1775cc0c5538SChris Mason if (btrfs_leaf_free_space(root, l) >= space_needed) 1776be0e5c09SChris Mason return 0; 17773326d1b0SChris Mason } 1778aa5d6bedSChris Mason 17795c680ed6SChris Mason if (!path->nodes[1]) { 1780e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 17815c680ed6SChris Mason if (ret) 17825c680ed6SChris Mason return ret; 17835c680ed6SChris Mason } 1784cc0c5538SChris Mason again: 1785cc0c5538SChris Mason double_split = 0; 1786cc0c5538SChris Mason l = path->nodes[0]; 1787eb60ceacSChris Mason slot = path->slots[0]; 17885f39d397SChris Mason nritems = btrfs_header_nritems(l); 1789eb60ceacSChris Mason mid = (nritems + 1)/ 2; 179054aa1f4dSChris Mason 1791db94535dSChris Mason right = btrfs_alloc_free_block(trans, root, root->leafsize, 1792db94535dSChris Mason l->start, 0); 17935f39d397SChris Mason if (IS_ERR(right)) 17945f39d397SChris Mason return PTR_ERR(right); 179554aa1f4dSChris Mason 17965f39d397SChris Mason memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header)); 1797db94535dSChris Mason btrfs_set_header_bytenr(right, right->start); 17985f39d397SChris Mason btrfs_set_header_generation(right, trans->transid); 17995f39d397SChris Mason btrfs_set_header_owner(right, root->root_key.objectid); 18005f39d397SChris Mason btrfs_set_header_level(right, 0); 18015f39d397SChris Mason write_extent_buffer(right, root->fs_info->fsid, 18025f39d397SChris Mason (unsigned long)btrfs_header_fsid(right), 18035f39d397SChris Mason BTRFS_FSID_SIZE); 1804d4dbff95SChris Mason if (mid <= slot) { 1805d4dbff95SChris Mason if (nritems == 1 || 1806d4dbff95SChris Mason leaf_space_used(l, mid, nritems - mid) + space_needed > 1807d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 1808d4dbff95SChris Mason if (slot >= nritems) { 1809d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 18105f39d397SChris Mason btrfs_set_header_nritems(right, 0); 1811d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1812db94535dSChris Mason &disk_key, right->start, 1813d4dbff95SChris Mason path->slots[1] + 1, 1); 1814d4dbff95SChris Mason if (wret) 1815d4dbff95SChris Mason ret = wret; 18165f39d397SChris Mason free_extent_buffer(path->nodes[0]); 18175f39d397SChris Mason path->nodes[0] = right; 1818d4dbff95SChris Mason path->slots[0] = 0; 1819d4dbff95SChris Mason path->slots[1] += 1; 1820d4dbff95SChris Mason return ret; 1821d4dbff95SChris Mason } 1822d4dbff95SChris Mason mid = slot; 18233326d1b0SChris Mason if (mid != nritems && 18243326d1b0SChris Mason leaf_space_used(l, mid, nritems - mid) + 18253326d1b0SChris Mason space_needed > BTRFS_LEAF_DATA_SIZE(root)) { 1826d4dbff95SChris Mason double_split = 1; 1827d4dbff95SChris Mason } 18283326d1b0SChris Mason } 1829d4dbff95SChris Mason } else { 1830d4dbff95SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1831d4dbff95SChris Mason BTRFS_LEAF_DATA_SIZE(root)) { 1832cc0c5538SChris Mason if (!extend && slot == 0) { 1833d4dbff95SChris Mason btrfs_cpu_key_to_disk(&disk_key, ins_key); 18345f39d397SChris Mason btrfs_set_header_nritems(right, 0); 1835d4dbff95SChris Mason wret = insert_ptr(trans, root, path, 1836d4dbff95SChris Mason &disk_key, 1837db94535dSChris Mason right->start, 1838098f59c2SChris Mason path->slots[1], 1); 1839d4dbff95SChris Mason if (wret) 1840d4dbff95SChris Mason ret = wret; 18415f39d397SChris Mason free_extent_buffer(path->nodes[0]); 18425f39d397SChris Mason path->nodes[0] = right; 1843d4dbff95SChris Mason path->slots[0] = 0; 1844a429e513SChris Mason if (path->slots[1] == 0) { 1845a429e513SChris Mason wret = fixup_low_keys(trans, root, 1846a429e513SChris Mason path, &disk_key, 1); 1847a429e513SChris Mason if (wret) 1848a429e513SChris Mason ret = wret; 1849a429e513SChris Mason } 1850d4dbff95SChris Mason return ret; 1851cc0c5538SChris Mason } else if (extend && slot == 0) { 1852cc0c5538SChris Mason mid = 1; 1853cc0c5538SChris Mason } else { 1854d4dbff95SChris Mason mid = slot; 18555ee78ac7SChris Mason if (mid != nritems && 18565ee78ac7SChris Mason leaf_space_used(l, mid, nritems - mid) + 18575ee78ac7SChris Mason space_needed > BTRFS_LEAF_DATA_SIZE(root)) { 1858d4dbff95SChris Mason double_split = 1; 1859d4dbff95SChris Mason } 1860d4dbff95SChris Mason } 18615ee78ac7SChris Mason } 1862cc0c5538SChris Mason } 18635f39d397SChris Mason nritems = nritems - mid; 18645f39d397SChris Mason btrfs_set_header_nritems(right, nritems); 18655f39d397SChris Mason data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l); 18665f39d397SChris Mason 18675f39d397SChris Mason copy_extent_buffer(right, l, btrfs_item_nr_offset(0), 18685f39d397SChris Mason btrfs_item_nr_offset(mid), 18695f39d397SChris Mason nritems * sizeof(struct btrfs_item)); 18705f39d397SChris Mason 18715f39d397SChris Mason copy_extent_buffer(right, l, 1872d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1873123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1874123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 187574123bd7SChris Mason 18765f39d397SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 18775f39d397SChris Mason btrfs_item_end_nr(l, mid); 18785f39d397SChris Mason 18795f39d397SChris Mason for (i = 0; i < nritems; i++) { 18805f39d397SChris Mason struct btrfs_item *item = btrfs_item_nr(right, i); 1881db94535dSChris Mason u32 ioff; 1882db94535dSChris Mason 1883db94535dSChris Mason if (!right->map_token) { 1884db94535dSChris Mason map_extent_buffer(right, (unsigned long)item, 1885db94535dSChris Mason sizeof(struct btrfs_item), 1886db94535dSChris Mason &right->map_token, &right->kaddr, 1887db94535dSChris Mason &right->map_start, &right->map_len, 1888db94535dSChris Mason KM_USER1); 1889db94535dSChris Mason } 1890db94535dSChris Mason 1891db94535dSChris Mason ioff = btrfs_item_offset(right, item); 18925f39d397SChris Mason btrfs_set_item_offset(right, item, ioff + rt_data_off); 18930783fcfcSChris Mason } 189474123bd7SChris Mason 1895db94535dSChris Mason if (right->map_token) { 1896db94535dSChris Mason unmap_extent_buffer(right, right->map_token, KM_USER1); 1897db94535dSChris Mason right->map_token = NULL; 1898db94535dSChris Mason } 1899db94535dSChris Mason 19005f39d397SChris Mason btrfs_set_header_nritems(l, mid); 1901aa5d6bedSChris Mason ret = 0; 19025f39d397SChris Mason btrfs_item_key(right, &disk_key, 0); 1903db94535dSChris Mason wret = insert_ptr(trans, root, path, &disk_key, right->start, 1904db94535dSChris Mason path->slots[1] + 1, 1); 1905aa5d6bedSChris Mason if (wret) 1906aa5d6bedSChris Mason ret = wret; 19075f39d397SChris Mason 19085f39d397SChris Mason btrfs_mark_buffer_dirty(right); 19095f39d397SChris Mason btrfs_mark_buffer_dirty(l); 1910eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 19115f39d397SChris Mason 1912be0e5c09SChris Mason if (mid <= slot) { 19135f39d397SChris Mason free_extent_buffer(path->nodes[0]); 19145f39d397SChris Mason path->nodes[0] = right; 1915be0e5c09SChris Mason path->slots[0] -= mid; 1916be0e5c09SChris Mason path->slots[1] += 1; 1917eb60ceacSChris Mason } else 19185f39d397SChris Mason free_extent_buffer(right); 19195f39d397SChris Mason 1920eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1921d4dbff95SChris Mason 1922cc0c5538SChris Mason if (double_split) { 1923cc0c5538SChris Mason BUG_ON(num_doubles != 0); 1924cc0c5538SChris Mason num_doubles++; 1925cc0c5538SChris Mason goto again; 19263326d1b0SChris Mason } 1927be0e5c09SChris Mason return ret; 1928be0e5c09SChris Mason } 1929be0e5c09SChris Mason 1930b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans, 1931b18c6685SChris Mason struct btrfs_root *root, 1932b18c6685SChris Mason struct btrfs_path *path, 1933b18c6685SChris Mason u32 new_size) 1934b18c6685SChris Mason { 1935b18c6685SChris Mason int ret = 0; 1936b18c6685SChris Mason int slot; 1937b18c6685SChris Mason int slot_orig; 19385f39d397SChris Mason struct extent_buffer *leaf; 19395f39d397SChris Mason struct btrfs_item *item; 1940b18c6685SChris Mason u32 nritems; 1941b18c6685SChris Mason unsigned int data_end; 1942b18c6685SChris Mason unsigned int old_data_start; 1943b18c6685SChris Mason unsigned int old_size; 1944b18c6685SChris Mason unsigned int size_diff; 1945b18c6685SChris Mason int i; 1946b18c6685SChris Mason 1947b18c6685SChris Mason slot_orig = path->slots[0]; 19485f39d397SChris Mason leaf = path->nodes[0]; 1949b18c6685SChris Mason 19505f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 1951b18c6685SChris Mason data_end = leaf_data_end(root, leaf); 1952b18c6685SChris Mason 1953b18c6685SChris Mason slot = path->slots[0]; 19545f39d397SChris Mason old_data_start = btrfs_item_offset_nr(leaf, slot); 1955cc0c5538SChris Mason old_size = btrfs_item_size_nr(leaf, slot); BUG_ON(old_size <= new_size); 1956b18c6685SChris Mason size_diff = old_size - new_size; 1957b18c6685SChris Mason 1958b18c6685SChris Mason BUG_ON(slot < 0); 1959b18c6685SChris Mason BUG_ON(slot >= nritems); 1960b18c6685SChris Mason 1961b18c6685SChris Mason /* 1962b18c6685SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1963b18c6685SChris Mason */ 1964b18c6685SChris Mason /* first correct the data pointers */ 1965b18c6685SChris Mason for (i = slot; i < nritems; i++) { 19665f39d397SChris Mason u32 ioff; 19675f39d397SChris Mason item = btrfs_item_nr(leaf, i); 1968db94535dSChris Mason 1969db94535dSChris Mason if (!leaf->map_token) { 1970db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 1971db94535dSChris Mason sizeof(struct btrfs_item), 1972db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 1973db94535dSChris Mason &leaf->map_start, &leaf->map_len, 1974db94535dSChris Mason KM_USER1); 1975db94535dSChris Mason } 1976db94535dSChris Mason 19775f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 19785f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + size_diff); 1979b18c6685SChris Mason } 1980db94535dSChris Mason 1981db94535dSChris Mason if (leaf->map_token) { 1982db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 1983db94535dSChris Mason leaf->map_token = NULL; 1984db94535dSChris Mason } 1985db94535dSChris Mason 1986b18c6685SChris Mason /* shift the data */ 19875f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 1988b18c6685SChris Mason data_end + size_diff, btrfs_leaf_data(leaf) + 1989b18c6685SChris Mason data_end, old_data_start + new_size - data_end); 19905f39d397SChris Mason 19915f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 19925f39d397SChris Mason btrfs_set_item_size(leaf, item, new_size); 19935f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 1994b18c6685SChris Mason 1995b18c6685SChris Mason ret = 0; 19965f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 19975f39d397SChris Mason btrfs_print_leaf(root, leaf); 1998b18c6685SChris Mason BUG(); 19995f39d397SChris Mason } 2000b18c6685SChris Mason return ret; 2001b18c6685SChris Mason } 2002b18c6685SChris Mason 20035f39d397SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans, 20045f39d397SChris Mason struct btrfs_root *root, struct btrfs_path *path, 20055f39d397SChris Mason u32 data_size) 20066567e837SChris Mason { 20076567e837SChris Mason int ret = 0; 20086567e837SChris Mason int slot; 20096567e837SChris Mason int slot_orig; 20105f39d397SChris Mason struct extent_buffer *leaf; 20115f39d397SChris Mason struct btrfs_item *item; 20126567e837SChris Mason u32 nritems; 20136567e837SChris Mason unsigned int data_end; 20146567e837SChris Mason unsigned int old_data; 20156567e837SChris Mason unsigned int old_size; 20166567e837SChris Mason int i; 20176567e837SChris Mason 20186567e837SChris Mason slot_orig = path->slots[0]; 20195f39d397SChris Mason leaf = path->nodes[0]; 20206567e837SChris Mason 20215f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 20226567e837SChris Mason data_end = leaf_data_end(root, leaf); 20236567e837SChris Mason 20245f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < data_size) { 20255f39d397SChris Mason btrfs_print_leaf(root, leaf); 20266567e837SChris Mason BUG(); 20275f39d397SChris Mason } 20286567e837SChris Mason slot = path->slots[0]; 20295f39d397SChris Mason old_data = btrfs_item_end_nr(leaf, slot); 20306567e837SChris Mason 20316567e837SChris Mason BUG_ON(slot < 0); 20323326d1b0SChris Mason if (slot >= nritems) { 20333326d1b0SChris Mason btrfs_print_leaf(root, leaf); 20343326d1b0SChris Mason printk("slot %d too large, nritems %d\n", slot, nritems); 20353326d1b0SChris Mason BUG_ON(1); 20363326d1b0SChris Mason } 20376567e837SChris Mason 20386567e837SChris Mason /* 20396567e837SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 20406567e837SChris Mason */ 20416567e837SChris Mason /* first correct the data pointers */ 20426567e837SChris Mason for (i = slot; i < nritems; i++) { 20435f39d397SChris Mason u32 ioff; 20445f39d397SChris Mason item = btrfs_item_nr(leaf, i); 2045db94535dSChris Mason 2046db94535dSChris Mason if (!leaf->map_token) { 2047db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 2048db94535dSChris Mason sizeof(struct btrfs_item), 2049db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 2050db94535dSChris Mason &leaf->map_start, &leaf->map_len, 2051db94535dSChris Mason KM_USER1); 2052db94535dSChris Mason } 20535f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 20545f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 20556567e837SChris Mason } 20565f39d397SChris Mason 2057db94535dSChris Mason if (leaf->map_token) { 2058db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 2059db94535dSChris Mason leaf->map_token = NULL; 2060db94535dSChris Mason } 2061db94535dSChris Mason 20626567e837SChris Mason /* shift the data */ 20635f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 20646567e837SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 20656567e837SChris Mason data_end, old_data - data_end); 20665f39d397SChris Mason 20676567e837SChris Mason data_end = old_data; 20685f39d397SChris Mason old_size = btrfs_item_size_nr(leaf, slot); 20695f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 20705f39d397SChris Mason btrfs_set_item_size(leaf, item, old_size + data_size); 20715f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 20726567e837SChris Mason 20736567e837SChris Mason ret = 0; 20745f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 20755f39d397SChris Mason btrfs_print_leaf(root, leaf); 20766567e837SChris Mason BUG(); 20775f39d397SChris Mason } 20786567e837SChris Mason return ret; 20796567e837SChris Mason } 20806567e837SChris Mason 208174123bd7SChris Mason /* 208274123bd7SChris Mason * Given a key and some data, insert an item into the tree. 208374123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 208474123bd7SChris Mason */ 20855f39d397SChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, 20865f39d397SChris Mason struct btrfs_root *root, 20875f39d397SChris Mason struct btrfs_path *path, 20885f39d397SChris Mason struct btrfs_key *cpu_key, u32 data_size) 2089be0e5c09SChris Mason { 20905f39d397SChris Mason struct extent_buffer *leaf; 20915f39d397SChris Mason struct btrfs_item *item; 2092aa5d6bedSChris Mason int ret = 0; 2093be0e5c09SChris Mason int slot; 2094eb60ceacSChris Mason int slot_orig; 20957518a238SChris Mason u32 nritems; 2096be0e5c09SChris Mason unsigned int data_end; 2097e2fa7227SChris Mason struct btrfs_disk_key disk_key; 2098e2fa7227SChris Mason 2099e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 2100be0e5c09SChris Mason 210174123bd7SChris Mason /* create a root if there isn't one */ 21025c680ed6SChris Mason if (!root->node) 2103cfaa7295SChris Mason BUG(); 21045f39d397SChris Mason 2105e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 2106eb60ceacSChris Mason if (ret == 0) { 2107f0930a37SChris Mason return -EEXIST; 2108aa5d6bedSChris Mason } 2109ed2ff2cbSChris Mason if (ret < 0) 2110ed2ff2cbSChris Mason goto out; 2111be0e5c09SChris Mason 211262e2749eSChris Mason slot_orig = path->slots[0]; 21135f39d397SChris Mason leaf = path->nodes[0]; 211474123bd7SChris Mason 21155f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 2116123abc88SChris Mason data_end = leaf_data_end(root, leaf); 2117eb60ceacSChris Mason 2118123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 2119d4dbff95SChris Mason sizeof(struct btrfs_item) + data_size) { 21203326d1b0SChris Mason btrfs_print_leaf(root, leaf); 21213326d1b0SChris Mason printk("not enough freespace need %u have %d\n", 21223326d1b0SChris Mason data_size, btrfs_leaf_free_space(root, leaf)); 2123be0e5c09SChris Mason BUG(); 2124d4dbff95SChris Mason } 21255f39d397SChris Mason 212662e2749eSChris Mason slot = path->slots[0]; 2127eb60ceacSChris Mason BUG_ON(slot < 0); 21285f39d397SChris Mason 2129be0e5c09SChris Mason if (slot != nritems) { 2130be0e5c09SChris Mason int i; 21315f39d397SChris Mason unsigned int old_data = btrfs_item_end_nr(leaf, slot); 2132be0e5c09SChris Mason 21335f39d397SChris Mason if (old_data < data_end) { 21345f39d397SChris Mason btrfs_print_leaf(root, leaf); 21355f39d397SChris Mason printk("slot %d old_data %d data_end %d\n", 21365f39d397SChris Mason slot, old_data, data_end); 21375f39d397SChris Mason BUG_ON(1); 21385f39d397SChris Mason } 2139be0e5c09SChris Mason /* 2140be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 2141be0e5c09SChris Mason */ 2142be0e5c09SChris Mason /* first correct the data pointers */ 2143db94535dSChris Mason WARN_ON(leaf->map_token); 21440783fcfcSChris Mason for (i = slot; i < nritems; i++) { 21455f39d397SChris Mason u32 ioff; 2146db94535dSChris Mason 21475f39d397SChris Mason item = btrfs_item_nr(leaf, i); 2148db94535dSChris Mason if (!leaf->map_token) { 2149db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 2150db94535dSChris Mason sizeof(struct btrfs_item), 2151db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 2152db94535dSChris Mason &leaf->map_start, &leaf->map_len, 2153db94535dSChris Mason KM_USER1); 2154db94535dSChris Mason } 2155db94535dSChris Mason 21565f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 21575f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff - data_size); 21580783fcfcSChris Mason } 2159db94535dSChris Mason if (leaf->map_token) { 2160db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 2161db94535dSChris Mason leaf->map_token = NULL; 2162db94535dSChris Mason } 2163be0e5c09SChris Mason 2164be0e5c09SChris Mason /* shift the items */ 21655f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1), 21665f39d397SChris Mason btrfs_item_nr_offset(slot), 21670783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 2168be0e5c09SChris Mason 2169be0e5c09SChris Mason /* shift the data */ 21705f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 2171d6025579SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 2172be0e5c09SChris Mason data_end, old_data - data_end); 2173be0e5c09SChris Mason data_end = old_data; 2174be0e5c09SChris Mason } 21755f39d397SChris Mason 217662e2749eSChris Mason /* setup the item for the new data */ 21775f39d397SChris Mason btrfs_set_item_key(leaf, &disk_key, slot); 21785f39d397SChris Mason item = btrfs_item_nr(leaf, slot); 21795f39d397SChris Mason btrfs_set_item_offset(leaf, item, data_end - data_size); 21805f39d397SChris Mason btrfs_set_item_size(leaf, item, data_size); 21815f39d397SChris Mason btrfs_set_header_nritems(leaf, nritems + 1); 21825f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 2183aa5d6bedSChris Mason 2184aa5d6bedSChris Mason ret = 0; 21858e19f2cdSChris Mason if (slot == 0) 2186e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 2187aa5d6bedSChris Mason 21885f39d397SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) { 21895f39d397SChris Mason btrfs_print_leaf(root, leaf); 2190be0e5c09SChris Mason BUG(); 21915f39d397SChris Mason } 2192ed2ff2cbSChris Mason out: 219362e2749eSChris Mason return ret; 219462e2749eSChris Mason } 219562e2749eSChris Mason 219662e2749eSChris Mason /* 219762e2749eSChris Mason * Given a key and some data, insert an item into the tree. 219862e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 219962e2749eSChris Mason */ 2200e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 2201e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 2202e089f05cSChris Mason data_size) 220362e2749eSChris Mason { 220462e2749eSChris Mason int ret = 0; 22052c90e5d6SChris Mason struct btrfs_path *path; 22065f39d397SChris Mason struct extent_buffer *leaf; 22075f39d397SChris Mason unsigned long ptr; 220862e2749eSChris Mason 22092c90e5d6SChris Mason path = btrfs_alloc_path(); 22102c90e5d6SChris Mason BUG_ON(!path); 22112c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 221262e2749eSChris Mason if (!ret) { 22135f39d397SChris Mason leaf = path->nodes[0]; 22145f39d397SChris Mason ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 22155f39d397SChris Mason write_extent_buffer(leaf, data, ptr, data_size); 22165f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 221762e2749eSChris Mason } 22182c90e5d6SChris Mason btrfs_free_path(path); 2219aa5d6bedSChris Mason return ret; 2220be0e5c09SChris Mason } 2221be0e5c09SChris Mason 222274123bd7SChris Mason /* 22235de08d7dSChris Mason * delete the pointer from a given node. 222474123bd7SChris Mason * 222574123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 222674123bd7SChris Mason * continuing all the way the root if required. The root is converted into 222774123bd7SChris Mason * a leaf if all the nodes are emptied. 222874123bd7SChris Mason */ 2229e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2230e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 2231be0e5c09SChris Mason { 22325f39d397SChris Mason struct extent_buffer *parent = path->nodes[level]; 22337518a238SChris Mason u32 nritems; 2234aa5d6bedSChris Mason int ret = 0; 2235bb803951SChris Mason int wret; 2236be0e5c09SChris Mason 22375f39d397SChris Mason nritems = btrfs_header_nritems(parent); 2238be0e5c09SChris Mason if (slot != nritems -1) { 22395f39d397SChris Mason memmove_extent_buffer(parent, 22405f39d397SChris Mason btrfs_node_key_ptr_offset(slot), 22415f39d397SChris Mason btrfs_node_key_ptr_offset(slot + 1), 2242d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 2243d6025579SChris Mason (nritems - slot - 1)); 2244be0e5c09SChris Mason } 22457518a238SChris Mason nritems--; 22465f39d397SChris Mason btrfs_set_header_nritems(parent, nritems); 22477518a238SChris Mason if (nritems == 0 && parent == root->node) { 22485f39d397SChris Mason BUG_ON(btrfs_header_level(root->node) != 1); 2249eb60ceacSChris Mason /* just turn the root into a leaf and break */ 22505f39d397SChris Mason btrfs_set_header_level(root->node, 0); 2251bb803951SChris Mason } else if (slot == 0) { 22525f39d397SChris Mason struct btrfs_disk_key disk_key; 22535f39d397SChris Mason 22545f39d397SChris Mason btrfs_node_key(parent, &disk_key, 0); 22555f39d397SChris Mason wret = fixup_low_keys(trans, root, path, &disk_key, level + 1); 22560f70abe2SChris Mason if (wret) 22570f70abe2SChris Mason ret = wret; 2258be0e5c09SChris Mason } 2259d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 2260aa5d6bedSChris Mason return ret; 2261be0e5c09SChris Mason } 2262be0e5c09SChris Mason 226374123bd7SChris Mason /* 226474123bd7SChris Mason * delete the item at the leaf level in path. If that empties 226574123bd7SChris Mason * the leaf, remove it from the tree 226674123bd7SChris Mason */ 2267e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 2268e089f05cSChris Mason struct btrfs_path *path) 2269be0e5c09SChris Mason { 2270be0e5c09SChris Mason int slot; 22715f39d397SChris Mason struct extent_buffer *leaf; 22725f39d397SChris Mason struct btrfs_item *item; 2273be0e5c09SChris Mason int doff; 2274be0e5c09SChris Mason int dsize; 2275aa5d6bedSChris Mason int ret = 0; 2276aa5d6bedSChris Mason int wret; 22777518a238SChris Mason u32 nritems; 2278be0e5c09SChris Mason 22795f39d397SChris Mason leaf = path->nodes[0]; 22804920c9acSChris Mason slot = path->slots[0]; 22815f39d397SChris Mason doff = btrfs_item_offset_nr(leaf, slot); 22825f39d397SChris Mason dsize = btrfs_item_size_nr(leaf, slot); 22835f39d397SChris Mason nritems = btrfs_header_nritems(leaf); 2284be0e5c09SChris Mason 22857518a238SChris Mason if (slot != nritems - 1) { 2286be0e5c09SChris Mason int i; 2287123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 22885f39d397SChris Mason 22895f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) + 2290d6025579SChris Mason data_end + dsize, 2291123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 2292be0e5c09SChris Mason doff - data_end); 22935f39d397SChris Mason 22940783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 22955f39d397SChris Mason u32 ioff; 2296db94535dSChris Mason 22975f39d397SChris Mason item = btrfs_item_nr(leaf, i); 2298db94535dSChris Mason if (!leaf->map_token) { 2299db94535dSChris Mason map_extent_buffer(leaf, (unsigned long)item, 2300db94535dSChris Mason sizeof(struct btrfs_item), 2301db94535dSChris Mason &leaf->map_token, &leaf->kaddr, 2302db94535dSChris Mason &leaf->map_start, &leaf->map_len, 2303db94535dSChris Mason KM_USER1); 2304db94535dSChris Mason } 23055f39d397SChris Mason ioff = btrfs_item_offset(leaf, item); 23065f39d397SChris Mason btrfs_set_item_offset(leaf, item, ioff + dsize); 23070783fcfcSChris Mason } 2308db94535dSChris Mason 2309db94535dSChris Mason if (leaf->map_token) { 2310db94535dSChris Mason unmap_extent_buffer(leaf, leaf->map_token, KM_USER1); 2311db94535dSChris Mason leaf->map_token = NULL; 2312db94535dSChris Mason } 2313db94535dSChris Mason 23145f39d397SChris Mason memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot), 23155f39d397SChris Mason btrfs_item_nr_offset(slot + 1), 23160783fcfcSChris Mason sizeof(struct btrfs_item) * 23177518a238SChris Mason (nritems - slot - 1)); 2318be0e5c09SChris Mason } 23195f39d397SChris Mason btrfs_set_header_nritems(leaf, nritems - 1); 23207518a238SChris Mason nritems--; 23215f39d397SChris Mason 232274123bd7SChris Mason /* delete the leaf if we've emptied it */ 23237518a238SChris Mason if (nritems == 0) { 23245f39d397SChris Mason if (leaf == root->node) { 23255f39d397SChris Mason btrfs_set_header_level(leaf, 0); 23269a8dd150SChris Mason } else { 23275f39d397SChris Mason clean_tree_block(trans, root, leaf); 23285f39d397SChris Mason wait_on_tree_block_writeback(root, leaf); 2329e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 2330aa5d6bedSChris Mason if (wret) 2331aa5d6bedSChris Mason ret = wret; 2332e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 2333db94535dSChris Mason leaf->start, leaf->len, 1); 23340f70abe2SChris Mason if (wret) 23350f70abe2SChris Mason ret = wret; 23369a8dd150SChris Mason } 2337be0e5c09SChris Mason } else { 23387518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 2339aa5d6bedSChris Mason if (slot == 0) { 23405f39d397SChris Mason struct btrfs_disk_key disk_key; 23415f39d397SChris Mason 23425f39d397SChris Mason btrfs_item_key(leaf, &disk_key, 0); 2343e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 23445f39d397SChris Mason &disk_key, 1); 2345aa5d6bedSChris Mason if (wret) 2346aa5d6bedSChris Mason ret = wret; 2347aa5d6bedSChris Mason } 2348aa5d6bedSChris Mason 234974123bd7SChris Mason /* delete the leaf if it is mostly empty */ 23507936ca38SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 2351be0e5c09SChris Mason /* push_leaf_left fixes the path. 2352be0e5c09SChris Mason * make sure the path still points to our leaf 2353be0e5c09SChris Mason * for possible call to del_ptr below 2354be0e5c09SChris Mason */ 23554920c9acSChris Mason slot = path->slots[1]; 23565f39d397SChris Mason extent_buffer_get(leaf); 23575f39d397SChris Mason 23583685f791SChris Mason wret = push_leaf_right(trans, root, path, 1); 235954aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 2360aa5d6bedSChris Mason ret = wret; 23615f39d397SChris Mason 23625f39d397SChris Mason if (path->nodes[0] == leaf && 23635f39d397SChris Mason btrfs_header_nritems(leaf)) { 23643685f791SChris Mason wret = push_leaf_left(trans, root, path, 1); 236554aa1f4dSChris Mason if (wret < 0 && wret != -ENOSPC) 2366aa5d6bedSChris Mason ret = wret; 2367aa5d6bedSChris Mason } 23685f39d397SChris Mason 23695f39d397SChris Mason if (btrfs_header_nritems(leaf) == 0) { 2370db94535dSChris Mason u64 bytenr = leaf->start; 2371db94535dSChris Mason u32 blocksize = leaf->len; 23725f39d397SChris Mason 23735f39d397SChris Mason clean_tree_block(trans, root, leaf); 23745f39d397SChris Mason wait_on_tree_block_writeback(root, leaf); 23755f39d397SChris Mason 2376e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 2377aa5d6bedSChris Mason if (wret) 2378aa5d6bedSChris Mason ret = wret; 23795f39d397SChris Mason 23805f39d397SChris Mason free_extent_buffer(leaf); 2381db94535dSChris Mason wret = btrfs_free_extent(trans, root, bytenr, 2382db94535dSChris Mason blocksize, 1); 23830f70abe2SChris Mason if (wret) 23840f70abe2SChris Mason ret = wret; 23855de08d7dSChris Mason } else { 23865f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 23875f39d397SChris Mason free_extent_buffer(leaf); 2388be0e5c09SChris Mason } 2389d5719762SChris Mason } else { 23905f39d397SChris Mason btrfs_mark_buffer_dirty(leaf); 2391be0e5c09SChris Mason } 23929a8dd150SChris Mason } 2393aa5d6bedSChris Mason return ret; 23949a8dd150SChris Mason } 23959a8dd150SChris Mason 239697571fd0SChris Mason /* 239797571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 23980f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 23990f70abe2SChris Mason * returns < 0 on io errors. 240097571fd0SChris Mason */ 2401234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 2402d97e63b6SChris Mason { 2403d97e63b6SChris Mason int slot; 2404d97e63b6SChris Mason int level = 1; 2405db94535dSChris Mason u64 bytenr; 24065f39d397SChris Mason struct extent_buffer *c; 24075f39d397SChris Mason struct extent_buffer *next = NULL; 2408d97e63b6SChris Mason 2409234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 2410d97e63b6SChris Mason if (!path->nodes[level]) 24110f70abe2SChris Mason return 1; 24125f39d397SChris Mason 2413d97e63b6SChris Mason slot = path->slots[level] + 1; 2414d97e63b6SChris Mason c = path->nodes[level]; 24155f39d397SChris Mason if (slot >= btrfs_header_nritems(c)) { 2416d97e63b6SChris Mason level++; 2417d97e63b6SChris Mason continue; 2418d97e63b6SChris Mason } 24195f39d397SChris Mason 2420db94535dSChris Mason bytenr = btrfs_node_blockptr(c, slot); 2421cfaa7295SChris Mason if (next) 24225f39d397SChris Mason free_extent_buffer(next); 24235f39d397SChris Mason 24246702ed49SChris Mason if (path->reada) 24256702ed49SChris Mason reada_for_search(root, path, level, slot); 24265f39d397SChris Mason 2427db94535dSChris Mason next = read_tree_block(root, bytenr, 2428db94535dSChris Mason btrfs_level_size(root, level -1)); 2429d97e63b6SChris Mason break; 2430d97e63b6SChris Mason } 2431d97e63b6SChris Mason path->slots[level] = slot; 2432d97e63b6SChris Mason while(1) { 2433d97e63b6SChris Mason level--; 2434d97e63b6SChris Mason c = path->nodes[level]; 24355f39d397SChris Mason free_extent_buffer(c); 2436d97e63b6SChris Mason path->nodes[level] = next; 2437d97e63b6SChris Mason path->slots[level] = 0; 2438d97e63b6SChris Mason if (!level) 2439d97e63b6SChris Mason break; 24406702ed49SChris Mason if (path->reada) 244132020611SYan reada_for_search(root, path, level, 0); 2442db94535dSChris Mason next = read_tree_block(root, btrfs_node_blockptr(next, 0), 2443db94535dSChris Mason btrfs_level_size(root, level - 1)); 2444d97e63b6SChris Mason } 2445d97e63b6SChris Mason return 0; 2446d97e63b6SChris Mason } 2447