1be0e5c09SChris Mason #include <stdio.h> 2be0e5c09SChris Mason #include <stdlib.h> 3be0e5c09SChris Mason #include "kerncompat.h" 4eb60ceacSChris Mason #include "radix-tree.h" 5eb60ceacSChris Mason #include "ctree.h" 6eb60ceacSChris Mason #include "disk-io.h" 75de08d7dSChris Mason #include "print-tree.h" 89a8dd150SChris Mason 9234b63a0SChris Mason static int split_node(struct btrfs_root *root, struct btrfs_path *path, 10aa5d6bedSChris Mason int level); 11234b63a0SChris Mason static int split_leaf(struct btrfs_root *root, struct btrfs_path *path, 12aa5d6bedSChris Mason int data_size); 13234b63a0SChris Mason static int push_node_left(struct btrfs_root *root, struct btrfs_buffer *dst, 14234b63a0SChris Mason struct btrfs_buffer *src); 15234b63a0SChris Mason static int balance_node_right(struct btrfs_root *root, 16234b63a0SChris Mason struct btrfs_buffer *dst_buf, 17234b63a0SChris Mason struct btrfs_buffer *src_buf); 18234b63a0SChris Mason static int del_ptr(struct btrfs_root *root, struct btrfs_path *path, int level, 19bb803951SChris Mason int slot); 20d97e63b6SChris Mason 21234b63a0SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 22be0e5c09SChris Mason { 23be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 24be0e5c09SChris Mason } 25be0e5c09SChris Mason 26234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 27eb60ceacSChris Mason { 28eb60ceacSChris Mason int i; 29234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 30eb60ceacSChris Mason if (!p->nodes[i]) 31eb60ceacSChris Mason break; 32234b63a0SChris Mason btrfs_block_release(root, p->nodes[i]); 33eb60ceacSChris Mason } 34aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 35eb60ceacSChris Mason } 36eb60ceacSChris Mason 379aca1d51SChris Mason static int btrfs_cow_block(struct btrfs_root *root, 38234b63a0SChris Mason struct btrfs_buffer *buf, 39234b63a0SChris Mason struct btrfs_buffer *parent, 4002217ed2SChris Mason int parent_slot, 41234b63a0SChris Mason struct btrfs_buffer **cow_ret) 4202217ed2SChris Mason { 43234b63a0SChris Mason struct btrfs_buffer *cow; 4402217ed2SChris Mason 4502217ed2SChris Mason if (!list_empty(&buf->dirty)) { 4602217ed2SChris Mason *cow_ret = buf; 4702217ed2SChris Mason return 0; 4802217ed2SChris Mason } 49234b63a0SChris Mason cow = btrfs_alloc_free_block(root); 50123abc88SChris Mason memcpy(&cow->node, &buf->node, root->blocksize); 517518a238SChris Mason btrfs_set_header_blocknr(&cow->node.header, cow->blocknr); 5202217ed2SChris Mason *cow_ret = cow; 53a28ec197SChris Mason btrfs_inc_ref(root, buf); 5402217ed2SChris Mason if (buf == root->node) { 5502217ed2SChris Mason root->node = cow; 5602217ed2SChris Mason cow->count++; 57a28ec197SChris Mason if (buf != root->commit_root) 58234b63a0SChris Mason btrfs_free_extent(root, buf->blocknr, 1); 59234b63a0SChris Mason btrfs_block_release(root, buf); 6002217ed2SChris Mason } else { 611d4f8a0cSChris Mason btrfs_set_node_blockptr(&parent->node, parent_slot, 621d4f8a0cSChris Mason cow->blocknr); 6302217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 64234b63a0SChris Mason btrfs_free_extent(root, buf->blocknr, 1); 6502217ed2SChris Mason } 66234b63a0SChris Mason btrfs_block_release(root, buf); 6702217ed2SChris Mason return 0; 6802217ed2SChris Mason } 6902217ed2SChris Mason 7074123bd7SChris Mason /* 7174123bd7SChris Mason * The leaf data grows from end-to-front in the node. 7274123bd7SChris Mason * this returns the address of the start of the last item, 7374123bd7SChris Mason * which is the stop of the leaf data stack 7474123bd7SChris Mason */ 75123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 76123abc88SChris Mason struct btrfs_leaf *leaf) 77be0e5c09SChris Mason { 787518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 79be0e5c09SChris Mason if (nr == 0) 80123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 810783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 82be0e5c09SChris Mason } 83be0e5c09SChris Mason 8474123bd7SChris Mason /* 8574123bd7SChris Mason * The space between the end of the leaf items and 8674123bd7SChris Mason * the start of the leaf data. IOW, how much room 8774123bd7SChris Mason * the leaf has left for both items and data 8874123bd7SChris Mason */ 89123abc88SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) 90be0e5c09SChris Mason { 91123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 927518a238SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 93be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 94123abc88SChris Mason return (char *)(btrfs_leaf_data(leaf) + data_end) - (char *)items_end; 95be0e5c09SChris Mason } 96be0e5c09SChris Mason 9774123bd7SChris Mason /* 9874123bd7SChris Mason * compare two keys in a memcmp fashion 9974123bd7SChris Mason */ 1009aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 101be0e5c09SChris Mason { 102e2fa7227SChris Mason struct btrfs_key k1; 103e2fa7227SChris Mason 104e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 105e2fa7227SChris Mason 106e2fa7227SChris Mason if (k1.objectid > k2->objectid) 107be0e5c09SChris Mason return 1; 108e2fa7227SChris Mason if (k1.objectid < k2->objectid) 109be0e5c09SChris Mason return -1; 110e2fa7227SChris Mason if (k1.offset > k2->offset) 111be0e5c09SChris Mason return 1; 112e2fa7227SChris Mason if (k1.offset < k2->offset) 113be0e5c09SChris Mason return -1; 11462e2749eSChris Mason if (k1.flags > k2->flags) 11562e2749eSChris Mason return 1; 11662e2749eSChris Mason if (k1.flags < k2->flags) 11762e2749eSChris Mason return -1; 118be0e5c09SChris Mason return 0; 119be0e5c09SChris Mason } 12074123bd7SChris Mason 121123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 122123abc88SChris Mason int level) 123aa5d6bedSChris Mason { 124aa5d6bedSChris Mason int i; 125234b63a0SChris Mason struct btrfs_node *parent = NULL; 126234b63a0SChris Mason struct btrfs_node *node = &path->nodes[level]->node; 127aa5d6bedSChris Mason int parent_slot; 1287518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 129aa5d6bedSChris Mason 130aa5d6bedSChris Mason if (path->nodes[level + 1]) 131aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 132aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1337518a238SChris Mason BUG_ON(nritems == 0); 1347518a238SChris Mason if (parent) { 135e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 136123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 137123abc88SChris Mason BUG_ON(memcmp(parent_key, &node->ptrs[0].key, 138e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1391d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1407518a238SChris Mason btrfs_header_blocknr(&node->header)); 141aa5d6bedSChris Mason } 142123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 1437518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 144e2fa7227SChris Mason struct btrfs_key cpukey; 145123abc88SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key); 146123abc88SChris Mason BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0); 147aa5d6bedSChris Mason } 148aa5d6bedSChris Mason return 0; 149aa5d6bedSChris Mason } 150aa5d6bedSChris Mason 151123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 152123abc88SChris Mason int level) 153aa5d6bedSChris Mason { 154aa5d6bedSChris Mason int i; 155234b63a0SChris Mason struct btrfs_leaf *leaf = &path->nodes[level]->leaf; 156234b63a0SChris Mason struct btrfs_node *parent = NULL; 157aa5d6bedSChris Mason int parent_slot; 1587518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 159aa5d6bedSChris Mason 160aa5d6bedSChris Mason if (path->nodes[level + 1]) 161aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 162aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 163123abc88SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 1647518a238SChris Mason 1657518a238SChris Mason if (nritems == 0) 1667518a238SChris Mason return 0; 1677518a238SChris Mason 1687518a238SChris Mason if (parent) { 169e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 170123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 171aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 172e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1731d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1747518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 175aa5d6bedSChris Mason } 1767518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 177e2fa7227SChris Mason struct btrfs_key cpukey; 178e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); 179aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 180e2fa7227SChris Mason &cpukey) >= 0); 1810783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) != 1820783fcfcSChris Mason btrfs_item_end(leaf->items + i + 1)); 183aa5d6bedSChris Mason if (i == 0) { 1840783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) + 1850783fcfcSChris Mason btrfs_item_size(leaf->items + i) != 186123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)); 187aa5d6bedSChris Mason } 188aa5d6bedSChris Mason } 189aa5d6bedSChris Mason return 0; 190aa5d6bedSChris Mason } 191aa5d6bedSChris Mason 192123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 193123abc88SChris Mason int level) 194aa5d6bedSChris Mason { 195aa5d6bedSChris Mason if (level == 0) 196123abc88SChris Mason return check_leaf(root, path, level); 197123abc88SChris Mason return check_node(root, path, level); 198aa5d6bedSChris Mason } 199aa5d6bedSChris Mason 20074123bd7SChris Mason /* 20174123bd7SChris Mason * search for key in the array p. items p are item_size apart 20274123bd7SChris Mason * and there are 'max' items in p 20374123bd7SChris Mason * the slot in the array is returned via slot, and it points to 20474123bd7SChris Mason * the place where you would insert key if it is not found in 20574123bd7SChris Mason * the array. 20674123bd7SChris Mason * 20774123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 20874123bd7SChris Mason */ 2099aca1d51SChris Mason static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 210be0e5c09SChris Mason int max, int *slot) 211be0e5c09SChris Mason { 212be0e5c09SChris Mason int low = 0; 213be0e5c09SChris Mason int high = max; 214be0e5c09SChris Mason int mid; 215be0e5c09SChris Mason int ret; 216e2fa7227SChris Mason struct btrfs_disk_key *tmp; 217be0e5c09SChris Mason 218be0e5c09SChris Mason while(low < high) { 219be0e5c09SChris Mason mid = (low + high) / 2; 220e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 221be0e5c09SChris Mason ret = comp_keys(tmp, key); 222be0e5c09SChris Mason 223be0e5c09SChris Mason if (ret < 0) 224be0e5c09SChris Mason low = mid + 1; 225be0e5c09SChris Mason else if (ret > 0) 226be0e5c09SChris Mason high = mid; 227be0e5c09SChris Mason else { 228be0e5c09SChris Mason *slot = mid; 229be0e5c09SChris Mason return 0; 230be0e5c09SChris Mason } 231be0e5c09SChris Mason } 232be0e5c09SChris Mason *slot = low; 233be0e5c09SChris Mason return 1; 234be0e5c09SChris Mason } 235be0e5c09SChris Mason 23697571fd0SChris Mason /* 23797571fd0SChris Mason * simple bin_search frontend that does the right thing for 23897571fd0SChris Mason * leaves vs nodes 23997571fd0SChris Mason */ 2409aca1d51SChris Mason static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) 241be0e5c09SChris Mason { 2427518a238SChris Mason if (btrfs_is_leaf(c)) { 243234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 2440783fcfcSChris Mason return generic_bin_search((void *)l->items, 2450783fcfcSChris Mason sizeof(struct btrfs_item), 2467518a238SChris Mason key, btrfs_header_nritems(&c->header), 2477518a238SChris Mason slot); 248be0e5c09SChris Mason } else { 249123abc88SChris Mason return generic_bin_search((void *)c->ptrs, 250123abc88SChris Mason sizeof(struct btrfs_key_ptr), 2517518a238SChris Mason key, btrfs_header_nritems(&c->header), 2527518a238SChris Mason slot); 253be0e5c09SChris Mason } 254be0e5c09SChris Mason return -1; 255be0e5c09SChris Mason } 256be0e5c09SChris Mason 2579aca1d51SChris Mason static struct btrfs_buffer *read_node_slot(struct btrfs_root *root, 258234b63a0SChris Mason struct btrfs_buffer *parent_buf, 259bb803951SChris Mason int slot) 260bb803951SChris Mason { 261234b63a0SChris Mason struct btrfs_node *node = &parent_buf->node; 262bb803951SChris Mason if (slot < 0) 263bb803951SChris Mason return NULL; 2647518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 265bb803951SChris Mason return NULL; 2661d4f8a0cSChris Mason return read_tree_block(root, btrfs_node_blockptr(node, slot)); 267bb803951SChris Mason } 268bb803951SChris Mason 269234b63a0SChris Mason static int balance_level(struct btrfs_root *root, struct btrfs_path *path, 270bb803951SChris Mason int level) 271bb803951SChris Mason { 272234b63a0SChris Mason struct btrfs_buffer *right_buf; 273234b63a0SChris Mason struct btrfs_buffer *mid_buf; 274234b63a0SChris Mason struct btrfs_buffer *left_buf; 275234b63a0SChris Mason struct btrfs_buffer *parent_buf = NULL; 276234b63a0SChris Mason struct btrfs_node *right = NULL; 277234b63a0SChris Mason struct btrfs_node *mid; 278234b63a0SChris Mason struct btrfs_node *left = NULL; 279234b63a0SChris Mason struct btrfs_node *parent = NULL; 280bb803951SChris Mason int ret = 0; 281bb803951SChris Mason int wret; 282bb803951SChris Mason int pslot; 283bb803951SChris Mason int orig_slot = path->slots[level]; 28479f95c82SChris Mason u64 orig_ptr; 285bb803951SChris Mason 286bb803951SChris Mason if (level == 0) 287bb803951SChris Mason return 0; 288bb803951SChris Mason 289bb803951SChris Mason mid_buf = path->nodes[level]; 290bb803951SChris Mason mid = &mid_buf->node; 2911d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 29279f95c82SChris Mason 293234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 294bb803951SChris Mason parent_buf = path->nodes[level + 1]; 295bb803951SChris Mason pslot = path->slots[level + 1]; 296bb803951SChris Mason 297bb803951SChris Mason if (!parent_buf) { 298234b63a0SChris Mason struct btrfs_buffer *child; 299bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 300bb803951SChris Mason 3017518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 302bb803951SChris Mason return 0; 303bb803951SChris Mason 304bb803951SChris Mason /* promote the child to a root */ 305bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 306bb803951SChris Mason BUG_ON(!child); 307bb803951SChris Mason root->node = child; 308bb803951SChris Mason path->nodes[level] = NULL; 309bb803951SChris Mason /* once for the path */ 310234b63a0SChris Mason btrfs_block_release(root, mid_buf); 311bb803951SChris Mason /* once for the root ptr */ 312234b63a0SChris Mason btrfs_block_release(root, mid_buf); 313ed2ff2cbSChris Mason clean_tree_block(root, mid_buf); 314234b63a0SChris Mason return btrfs_free_extent(root, blocknr, 1); 315bb803951SChris Mason } 316bb803951SChris Mason parent = &parent_buf->node; 317bb803951SChris Mason 318123abc88SChris Mason if (btrfs_header_nritems(&mid->header) > 319123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 320bb803951SChris Mason return 0; 321bb803951SChris Mason 322bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 323bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 32479f95c82SChris Mason 32579f95c82SChris Mason /* first, try to make some room in the middle buffer */ 326bb803951SChris Mason if (left_buf) { 32702217ed2SChris Mason btrfs_cow_block(root, left_buf, parent_buf, 32802217ed2SChris Mason pslot - 1, &left_buf); 329bb803951SChris Mason left = &left_buf->node; 3307518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 33179f95c82SChris Mason wret = push_node_left(root, left_buf, mid_buf); 33279f95c82SChris Mason if (wret < 0) 33379f95c82SChris Mason ret = wret; 334bb803951SChris Mason } 33579f95c82SChris Mason 33679f95c82SChris Mason /* 33779f95c82SChris Mason * then try to empty the right most buffer into the middle 33879f95c82SChris Mason */ 339bb803951SChris Mason if (right_buf) { 34002217ed2SChris Mason btrfs_cow_block(root, right_buf, parent_buf, 34102217ed2SChris Mason pslot + 1, &right_buf); 34279f95c82SChris Mason right = &right_buf->node; 34379f95c82SChris Mason wret = push_node_left(root, mid_buf, right_buf); 34479f95c82SChris Mason if (wret < 0) 34579f95c82SChris Mason ret = wret; 3467518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 347bb803951SChris Mason u64 blocknr = right_buf->blocknr; 348234b63a0SChris Mason btrfs_block_release(root, right_buf); 349ed2ff2cbSChris Mason clean_tree_block(root, right_buf); 350bb803951SChris Mason right_buf = NULL; 351bb803951SChris Mason right = NULL; 352bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot + 1); 353bb803951SChris Mason if (wret) 354bb803951SChris Mason ret = wret; 355234b63a0SChris Mason wret = btrfs_free_extent(root, blocknr, 1); 356bb803951SChris Mason if (wret) 357bb803951SChris Mason ret = wret; 358bb803951SChris Mason } else { 359123abc88SChris Mason memcpy(&parent->ptrs[pslot + 1].key, 360123abc88SChris Mason &right->ptrs[0].key, 361e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 36202217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 363bb803951SChris Mason } 364bb803951SChris Mason } 3657518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 36679f95c82SChris Mason /* 36779f95c82SChris Mason * we're not allowed to leave a node with one item in the 36879f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 36979f95c82SChris Mason * could try to delete the only pointer in this node. 37079f95c82SChris Mason * So, pull some keys from the left. 37179f95c82SChris Mason * There has to be a left pointer at this point because 37279f95c82SChris Mason * otherwise we would have pulled some pointers from the 37379f95c82SChris Mason * right 37479f95c82SChris Mason */ 37579f95c82SChris Mason BUG_ON(!left_buf); 37679f95c82SChris Mason wret = balance_node_right(root, mid_buf, left_buf); 37779f95c82SChris Mason if (wret < 0) 37879f95c82SChris Mason ret = wret; 37979f95c82SChris Mason BUG_ON(wret == 1); 38079f95c82SChris Mason } 3817518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 38279f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 383bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 384234b63a0SChris Mason btrfs_block_release(root, mid_buf); 385ed2ff2cbSChris Mason clean_tree_block(root, mid_buf); 386bb803951SChris Mason mid_buf = NULL; 387bb803951SChris Mason mid = NULL; 388bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot); 389bb803951SChris Mason if (wret) 390bb803951SChris Mason ret = wret; 391234b63a0SChris Mason wret = btrfs_free_extent(root, blocknr, 1); 392bb803951SChris Mason if (wret) 393bb803951SChris Mason ret = wret; 39479f95c82SChris Mason } else { 39579f95c82SChris Mason /* update the parent key to reflect our changes */ 396123abc88SChris Mason memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key, 397e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 39802217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 39979f95c82SChris Mason } 400bb803951SChris Mason 40179f95c82SChris Mason /* update the path */ 402bb803951SChris Mason if (left_buf) { 4037518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 404bb803951SChris Mason left_buf->count++; // released below 405bb803951SChris Mason path->nodes[level] = left_buf; 406bb803951SChris Mason path->slots[level + 1] -= 1; 407bb803951SChris Mason path->slots[level] = orig_slot; 408bb803951SChris Mason if (mid_buf) 409234b63a0SChris Mason btrfs_block_release(root, mid_buf); 410bb803951SChris Mason } else { 4117518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 412bb803951SChris Mason path->slots[level] = orig_slot; 413bb803951SChris Mason } 414bb803951SChris Mason } 41579f95c82SChris Mason /* double check we haven't messed things up */ 416123abc88SChris Mason check_block(root, path, level); 4171d4f8a0cSChris Mason if (orig_ptr != btrfs_node_blockptr(&path->nodes[level]->node, 4181d4f8a0cSChris Mason path->slots[level])) 41979f95c82SChris Mason BUG(); 420bb803951SChris Mason 421bb803951SChris Mason if (right_buf) 422234b63a0SChris Mason btrfs_block_release(root, right_buf); 423bb803951SChris Mason if (left_buf) 424234b63a0SChris Mason btrfs_block_release(root, left_buf); 425bb803951SChris Mason return ret; 426bb803951SChris Mason } 427bb803951SChris Mason 42874123bd7SChris Mason /* 42974123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 43074123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 43174123bd7SChris Mason * level of the path (level 0) 43274123bd7SChris Mason * 43374123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 434aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 435aa5d6bedSChris Mason * search a negative error number is returned. 43697571fd0SChris Mason * 43797571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 43897571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 43997571fd0SChris Mason * possible) 44074123bd7SChris Mason */ 441234b63a0SChris Mason int btrfs_search_slot(struct btrfs_root *root, struct btrfs_key *key, 442234b63a0SChris Mason struct btrfs_path *p, int ins_len, int cow) 443be0e5c09SChris Mason { 444234b63a0SChris Mason struct btrfs_buffer *b; 445234b63a0SChris Mason struct btrfs_buffer *cow_buf; 446234b63a0SChris Mason struct btrfs_node *c; 447be0e5c09SChris Mason int slot; 448be0e5c09SChris Mason int ret; 449be0e5c09SChris Mason int level; 4505c680ed6SChris Mason 451bb803951SChris Mason again: 452bb803951SChris Mason b = root->node; 453eb60ceacSChris Mason b->count++; 454eb60ceacSChris Mason while (b) { 4557518a238SChris Mason level = btrfs_header_level(&b->node.header); 45602217ed2SChris Mason if (cow) { 45702217ed2SChris Mason int wret; 45802217ed2SChris Mason wret = btrfs_cow_block(root, b, p->nodes[level + 1], 45902217ed2SChris Mason p->slots[level + 1], &cow_buf); 46002217ed2SChris Mason b = cow_buf; 46102217ed2SChris Mason } 46202217ed2SChris Mason BUG_ON(!cow && ins_len); 463eb60ceacSChris Mason c = &b->node; 464eb60ceacSChris Mason p->nodes[level] = b; 465123abc88SChris Mason ret = check_block(root, p, level); 466aa5d6bedSChris Mason if (ret) 467aa5d6bedSChris Mason return -1; 468be0e5c09SChris Mason ret = bin_search(c, key, &slot); 4697518a238SChris Mason if (!btrfs_is_leaf(c)) { 470be0e5c09SChris Mason if (ret && slot > 0) 471be0e5c09SChris Mason slot -= 1; 472be0e5c09SChris Mason p->slots[level] = slot; 4737518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 474123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root)) { 4755c680ed6SChris Mason int sret = split_node(root, p, level); 4765c680ed6SChris Mason BUG_ON(sret > 0); 4775c680ed6SChris Mason if (sret) 4785c680ed6SChris Mason return sret; 4795c680ed6SChris Mason b = p->nodes[level]; 4805c680ed6SChris Mason c = &b->node; 4815c680ed6SChris Mason slot = p->slots[level]; 482bb803951SChris Mason } else if (ins_len < 0) { 483bb803951SChris Mason int sret = balance_level(root, p, level); 484bb803951SChris Mason if (sret) 485bb803951SChris Mason return sret; 486bb803951SChris Mason b = p->nodes[level]; 487bb803951SChris Mason if (!b) 488bb803951SChris Mason goto again; 489bb803951SChris Mason c = &b->node; 490bb803951SChris Mason slot = p->slots[level]; 4917518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 4925c680ed6SChris Mason } 4931d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 494be0e5c09SChris Mason } else { 495234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 496be0e5c09SChris Mason p->slots[level] = slot; 497123abc88SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 4980783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 4995c680ed6SChris Mason int sret = split_leaf(root, p, ins_len); 5005c680ed6SChris Mason BUG_ON(sret > 0); 5015c680ed6SChris Mason if (sret) 5025c680ed6SChris Mason return sret; 5035c680ed6SChris Mason } 504bb803951SChris Mason BUG_ON(root->node->count == 1); 505be0e5c09SChris Mason return ret; 506be0e5c09SChris Mason } 507be0e5c09SChris Mason } 508bb803951SChris Mason BUG_ON(root->node->count == 1); 509aa5d6bedSChris Mason return 1; 510be0e5c09SChris Mason } 511be0e5c09SChris Mason 51274123bd7SChris Mason /* 51374123bd7SChris Mason * adjust the pointers going up the tree, starting at level 51474123bd7SChris Mason * making sure the right key of each node is points to 'key'. 51574123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 51674123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 51774123bd7SChris Mason * higher levels 518aa5d6bedSChris Mason * 519aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 520aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 52174123bd7SChris Mason */ 522234b63a0SChris Mason static int fixup_low_keys(struct btrfs_root *root, 523234b63a0SChris Mason struct btrfs_path *path, struct btrfs_disk_key *key, 524be0e5c09SChris Mason int level) 525be0e5c09SChris Mason { 526be0e5c09SChris Mason int i; 527aa5d6bedSChris Mason int ret = 0; 528234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 529234b63a0SChris Mason struct btrfs_node *t; 530be0e5c09SChris Mason int tslot = path->slots[i]; 531eb60ceacSChris Mason if (!path->nodes[i]) 532be0e5c09SChris Mason break; 533eb60ceacSChris Mason t = &path->nodes[i]->node; 534123abc88SChris Mason memcpy(&t->ptrs[tslot].key, key, sizeof(*key)); 53502217ed2SChris Mason BUG_ON(list_empty(&path->nodes[i]->dirty)); 536be0e5c09SChris Mason if (tslot != 0) 537be0e5c09SChris Mason break; 538be0e5c09SChris Mason } 539aa5d6bedSChris Mason return ret; 540be0e5c09SChris Mason } 541be0e5c09SChris Mason 54274123bd7SChris Mason /* 54374123bd7SChris Mason * try to push data from one node into the next node left in the 54479f95c82SChris Mason * tree. 545aa5d6bedSChris Mason * 546aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 547aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 54874123bd7SChris Mason */ 549234b63a0SChris Mason static int push_node_left(struct btrfs_root *root, struct btrfs_buffer *dst_buf, 550234b63a0SChris Mason struct btrfs_buffer *src_buf) 551be0e5c09SChris Mason { 552234b63a0SChris Mason struct btrfs_node *src = &src_buf->node; 553234b63a0SChris Mason struct btrfs_node *dst = &dst_buf->node; 554be0e5c09SChris Mason int push_items = 0; 555bb803951SChris Mason int src_nritems; 556bb803951SChris Mason int dst_nritems; 557aa5d6bedSChris Mason int ret = 0; 558be0e5c09SChris Mason 5597518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5607518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 561123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 562eb60ceacSChris Mason if (push_items <= 0) { 563be0e5c09SChris Mason return 1; 564eb60ceacSChris Mason } 565be0e5c09SChris Mason 566be0e5c09SChris Mason if (src_nritems < push_items) 567be0e5c09SChris Mason push_items = src_nritems; 56879f95c82SChris Mason 569123abc88SChris Mason memcpy(dst->ptrs + dst_nritems, src->ptrs, 570123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 571bb803951SChris Mason if (push_items < src_nritems) { 572123abc88SChris Mason memmove(src->ptrs, src->ptrs + push_items, 573e2fa7227SChris Mason (src_nritems - push_items) * 574123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 575bb803951SChris Mason } 5767518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 5777518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 57802217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 57902217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 580bb803951SChris Mason return ret; 581be0e5c09SChris Mason } 582be0e5c09SChris Mason 58397571fd0SChris Mason /* 58479f95c82SChris Mason * try to push data from one node into the next node right in the 58579f95c82SChris Mason * tree. 58679f95c82SChris Mason * 58779f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 58879f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 58979f95c82SChris Mason * 59079f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 59179f95c82SChris Mason */ 592234b63a0SChris Mason static int balance_node_right(struct btrfs_root *root, 593234b63a0SChris Mason struct btrfs_buffer *dst_buf, 594234b63a0SChris Mason struct btrfs_buffer *src_buf) 59579f95c82SChris Mason { 596234b63a0SChris Mason struct btrfs_node *src = &src_buf->node; 597234b63a0SChris Mason struct btrfs_node *dst = &dst_buf->node; 59879f95c82SChris Mason int push_items = 0; 59979f95c82SChris Mason int max_push; 60079f95c82SChris Mason int src_nritems; 60179f95c82SChris Mason int dst_nritems; 60279f95c82SChris Mason int ret = 0; 60379f95c82SChris Mason 6047518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6057518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 606123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 60779f95c82SChris Mason if (push_items <= 0) { 60879f95c82SChris Mason return 1; 60979f95c82SChris Mason } 61079f95c82SChris Mason 61179f95c82SChris Mason max_push = src_nritems / 2 + 1; 61279f95c82SChris Mason /* don't try to empty the node */ 61379f95c82SChris Mason if (max_push > src_nritems) 61479f95c82SChris Mason return 1; 61579f95c82SChris Mason if (max_push < push_items) 61679f95c82SChris Mason push_items = max_push; 61779f95c82SChris Mason 618123abc88SChris Mason memmove(dst->ptrs + push_items, dst->ptrs, 619123abc88SChris Mason dst_nritems * sizeof(struct btrfs_key_ptr)); 620123abc88SChris Mason memcpy(dst->ptrs, src->ptrs + src_nritems - push_items, 621123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 62279f95c82SChris Mason 6237518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6247518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 62579f95c82SChris Mason 62602217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 62702217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 62879f95c82SChris Mason return ret; 62979f95c82SChris Mason } 63079f95c82SChris Mason 63179f95c82SChris Mason /* 63297571fd0SChris Mason * helper function to insert a new root level in the tree. 63397571fd0SChris Mason * A new node is allocated, and a single item is inserted to 63497571fd0SChris Mason * point to the existing root 635aa5d6bedSChris Mason * 636aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 63797571fd0SChris Mason */ 638234b63a0SChris Mason static int insert_new_root(struct btrfs_root *root, 639234b63a0SChris Mason struct btrfs_path *path, int level) 64074123bd7SChris Mason { 641234b63a0SChris Mason struct btrfs_buffer *t; 642234b63a0SChris Mason struct btrfs_node *lower; 643234b63a0SChris Mason struct btrfs_node *c; 644e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 6455c680ed6SChris Mason 6465c680ed6SChris Mason BUG_ON(path->nodes[level]); 6475c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 6485c680ed6SChris Mason 649234b63a0SChris Mason t = btrfs_alloc_free_block(root); 65074123bd7SChris Mason c = &t->node; 651123abc88SChris Mason memset(c, 0, root->blocksize); 6527518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 6537518a238SChris Mason btrfs_set_header_level(&c->header, level); 6547518a238SChris Mason btrfs_set_header_blocknr(&c->header, t->blocknr); 6557518a238SChris Mason btrfs_set_header_parentid(&c->header, 6567518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 65774123bd7SChris Mason lower = &path->nodes[level-1]->node; 6587518a238SChris Mason if (btrfs_is_leaf(lower)) 659234b63a0SChris Mason lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 66074123bd7SChris Mason else 661123abc88SChris Mason lower_key = &lower->ptrs[0].key; 662123abc88SChris Mason memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key)); 6631d4f8a0cSChris Mason btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->blocknr); 664cfaa7295SChris Mason /* the super has an extra ref to root->node */ 665234b63a0SChris Mason btrfs_block_release(root, root->node); 66674123bd7SChris Mason root->node = t; 66774123bd7SChris Mason t->count++; 66874123bd7SChris Mason path->nodes[level] = t; 66974123bd7SChris Mason path->slots[level] = 0; 67074123bd7SChris Mason return 0; 67174123bd7SChris Mason } 6725c680ed6SChris Mason 6735c680ed6SChris Mason /* 6745c680ed6SChris Mason * worker function to insert a single pointer in a node. 6755c680ed6SChris Mason * the node should have enough room for the pointer already 67697571fd0SChris Mason * 6775c680ed6SChris Mason * slot and level indicate where you want the key to go, and 6785c680ed6SChris Mason * blocknr is the block the key points to. 679aa5d6bedSChris Mason * 680aa5d6bedSChris Mason * returns zero on success and < 0 on any error 6815c680ed6SChris Mason */ 682234b63a0SChris Mason static int insert_ptr(struct btrfs_root *root, 683234b63a0SChris Mason struct btrfs_path *path, struct btrfs_disk_key *key, 6845c680ed6SChris Mason u64 blocknr, int slot, int level) 6855c680ed6SChris Mason { 686234b63a0SChris Mason struct btrfs_node *lower; 6875c680ed6SChris Mason int nritems; 6885c680ed6SChris Mason 6895c680ed6SChris Mason BUG_ON(!path->nodes[level]); 69074123bd7SChris Mason lower = &path->nodes[level]->node; 6917518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 69274123bd7SChris Mason if (slot > nritems) 69374123bd7SChris Mason BUG(); 694123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 69574123bd7SChris Mason BUG(); 69674123bd7SChris Mason if (slot != nritems) { 697123abc88SChris Mason memmove(lower->ptrs + slot + 1, lower->ptrs + slot, 698123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 69974123bd7SChris Mason } 700123abc88SChris Mason memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key)); 7011d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 7027518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 70302217ed2SChris Mason BUG_ON(list_empty(&path->nodes[level]->dirty)); 70474123bd7SChris Mason return 0; 70574123bd7SChris Mason } 70674123bd7SChris Mason 70797571fd0SChris Mason /* 70897571fd0SChris Mason * split the node at the specified level in path in two. 70997571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 71097571fd0SChris Mason * 71197571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 71297571fd0SChris Mason * left and right, if either one works, it returns right away. 713aa5d6bedSChris Mason * 714aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 71597571fd0SChris Mason */ 716234b63a0SChris Mason static int split_node(struct btrfs_root *root, struct btrfs_path *path, 717aa5d6bedSChris Mason int level) 718be0e5c09SChris Mason { 719234b63a0SChris Mason struct btrfs_buffer *t; 720234b63a0SChris Mason struct btrfs_node *c; 721234b63a0SChris Mason struct btrfs_buffer *split_buffer; 722234b63a0SChris Mason struct btrfs_node *split; 723be0e5c09SChris Mason int mid; 7245c680ed6SChris Mason int ret; 725aa5d6bedSChris Mason int wret; 7267518a238SChris Mason u32 c_nritems; 727be0e5c09SChris Mason 7285c680ed6SChris Mason t = path->nodes[level]; 729eb60ceacSChris Mason c = &t->node; 7305c680ed6SChris Mason if (t == root->node) { 7315c680ed6SChris Mason /* trying to split the root, lets make a new one */ 7325c680ed6SChris Mason ret = insert_new_root(root, path, level + 1); 7335c680ed6SChris Mason if (ret) 7345c680ed6SChris Mason return ret; 7355c680ed6SChris Mason } 7367518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 737234b63a0SChris Mason split_buffer = btrfs_alloc_free_block(root); 7385c680ed6SChris Mason split = &split_buffer->node; 7397518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 7407518a238SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->blocknr); 7417518a238SChris Mason btrfs_set_header_parentid(&split->header, 7427518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 7437518a238SChris Mason mid = (c_nritems + 1) / 2; 744123abc88SChris Mason memcpy(split->ptrs, c->ptrs + mid, 745123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 7467518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7477518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 748aa5d6bedSChris Mason ret = 0; 749aa5d6bedSChris Mason 75002217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 751123abc88SChris Mason wret = insert_ptr(root, path, &split->ptrs[0].key, 752123abc88SChris Mason split_buffer->blocknr, path->slots[level + 1] + 1, 753123abc88SChris Mason level + 1); 754aa5d6bedSChris Mason if (wret) 755aa5d6bedSChris Mason ret = wret; 756aa5d6bedSChris Mason 7575de08d7dSChris Mason if (path->slots[level] >= mid) { 7585c680ed6SChris Mason path->slots[level] -= mid; 759234b63a0SChris Mason btrfs_block_release(root, t); 7605c680ed6SChris Mason path->nodes[level] = split_buffer; 7615c680ed6SChris Mason path->slots[level + 1] += 1; 762eb60ceacSChris Mason } else { 763234b63a0SChris Mason btrfs_block_release(root, split_buffer); 764be0e5c09SChris Mason } 765aa5d6bedSChris Mason return ret; 766be0e5c09SChris Mason } 767be0e5c09SChris Mason 76874123bd7SChris Mason /* 76974123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 77074123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 77174123bd7SChris Mason * space used both by the item structs and the item data 77274123bd7SChris Mason */ 773234b63a0SChris Mason static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 774be0e5c09SChris Mason { 775be0e5c09SChris Mason int data_len; 776be0e5c09SChris Mason int end = start + nr - 1; 777be0e5c09SChris Mason 778be0e5c09SChris Mason if (!nr) 779be0e5c09SChris Mason return 0; 7800783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 7810783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 7820783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 783be0e5c09SChris Mason return data_len; 784be0e5c09SChris Mason } 785be0e5c09SChris Mason 78674123bd7SChris Mason /* 78700ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 78800ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 789aa5d6bedSChris Mason * 790aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 791aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 79200ec4c51SChris Mason */ 793234b63a0SChris Mason static int push_leaf_right(struct btrfs_root *root, struct btrfs_path *path, 79400ec4c51SChris Mason int data_size) 79500ec4c51SChris Mason { 796234b63a0SChris Mason struct btrfs_buffer *left_buf = path->nodes[0]; 797234b63a0SChris Mason struct btrfs_leaf *left = &left_buf->leaf; 798234b63a0SChris Mason struct btrfs_leaf *right; 799234b63a0SChris Mason struct btrfs_buffer *right_buf; 800234b63a0SChris Mason struct btrfs_buffer *upper; 80100ec4c51SChris Mason int slot; 80200ec4c51SChris Mason int i; 80300ec4c51SChris Mason int free_space; 80400ec4c51SChris Mason int push_space = 0; 80500ec4c51SChris Mason int push_items = 0; 8060783fcfcSChris Mason struct btrfs_item *item; 8077518a238SChris Mason u32 left_nritems; 8087518a238SChris Mason u32 right_nritems; 80900ec4c51SChris Mason 81000ec4c51SChris Mason slot = path->slots[1]; 81100ec4c51SChris Mason if (!path->nodes[1]) { 81200ec4c51SChris Mason return 1; 81300ec4c51SChris Mason } 81400ec4c51SChris Mason upper = path->nodes[1]; 8157518a238SChris Mason if (slot >= btrfs_header_nritems(&upper->node.header) - 1) { 81600ec4c51SChris Mason return 1; 81700ec4c51SChris Mason } 8181d4f8a0cSChris Mason right_buf = read_tree_block(root, btrfs_node_blockptr(&upper->node, 8191d4f8a0cSChris Mason slot + 1)); 82000ec4c51SChris Mason right = &right_buf->leaf; 821123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8220783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 823234b63a0SChris Mason btrfs_block_release(root, right_buf); 82400ec4c51SChris Mason return 1; 82500ec4c51SChris Mason } 82602217ed2SChris Mason /* cow and double check */ 82702217ed2SChris Mason btrfs_cow_block(root, right_buf, upper, slot + 1, &right_buf); 82802217ed2SChris Mason right = &right_buf->leaf; 829123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8300783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 831234b63a0SChris Mason btrfs_block_release(root, right_buf); 83202217ed2SChris Mason return 1; 83302217ed2SChris Mason } 83402217ed2SChris Mason 8357518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8367518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 83700ec4c51SChris Mason item = left->items + i; 83800ec4c51SChris Mason if (path->slots[0] == i) 83900ec4c51SChris Mason push_space += data_size + sizeof(*item); 8400783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8410783fcfcSChris Mason free_space) 84200ec4c51SChris Mason break; 84300ec4c51SChris Mason push_items++; 8440783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 84500ec4c51SChris Mason } 84600ec4c51SChris Mason if (push_items == 0) { 847234b63a0SChris Mason btrfs_block_release(root, right_buf); 84800ec4c51SChris Mason return 1; 84900ec4c51SChris Mason } 8507518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 85100ec4c51SChris Mason /* push left to right */ 8520783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 853123abc88SChris Mason push_space -= leaf_data_end(root, left); 85400ec4c51SChris Mason /* make room in the right data area */ 855123abc88SChris Mason memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) - 856123abc88SChris Mason push_space, btrfs_leaf_data(right) + leaf_data_end(root, right), 857123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right)); 85800ec4c51SChris Mason /* copy from the left data area */ 859123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space, 860123abc88SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), push_space); 86100ec4c51SChris Mason memmove(right->items + push_items, right->items, 8620783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 86300ec4c51SChris Mason /* copy the items from left to right */ 8647518a238SChris Mason memcpy(right->items, left->items + left_nritems - push_items, 8650783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 86600ec4c51SChris Mason 86700ec4c51SChris Mason /* update the item pointers */ 8687518a238SChris Mason right_nritems += push_items; 8697518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 870123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 8717518a238SChris Mason for (i = 0; i < right_nritems; i++) { 8720783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 8730783fcfcSChris Mason btrfs_item_size(right->items + i)); 8740783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 87500ec4c51SChris Mason } 8767518a238SChris Mason left_nritems -= push_items; 8777518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 87800ec4c51SChris Mason 87902217ed2SChris Mason BUG_ON(list_empty(&left_buf->dirty)); 88002217ed2SChris Mason BUG_ON(list_empty(&right_buf->dirty)); 881123abc88SChris Mason memcpy(&upper->node.ptrs[slot + 1].key, 882e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 88302217ed2SChris Mason BUG_ON(list_empty(&upper->dirty)); 88402217ed2SChris Mason 88500ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 8867518a238SChris Mason if (path->slots[0] >= left_nritems) { 8877518a238SChris Mason path->slots[0] -= left_nritems; 888234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 88900ec4c51SChris Mason path->nodes[0] = right_buf; 89000ec4c51SChris Mason path->slots[1] += 1; 89100ec4c51SChris Mason } else { 892234b63a0SChris Mason btrfs_block_release(root, right_buf); 89300ec4c51SChris Mason } 89400ec4c51SChris Mason return 0; 89500ec4c51SChris Mason } 89600ec4c51SChris Mason /* 89774123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 89874123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 89974123bd7SChris Mason */ 900234b63a0SChris Mason static int push_leaf_left(struct btrfs_root *root, struct btrfs_path *path, 901be0e5c09SChris Mason int data_size) 902be0e5c09SChris Mason { 903234b63a0SChris Mason struct btrfs_buffer *right_buf = path->nodes[0]; 904234b63a0SChris Mason struct btrfs_leaf *right = &right_buf->leaf; 905234b63a0SChris Mason struct btrfs_buffer *t; 906234b63a0SChris Mason struct btrfs_leaf *left; 907be0e5c09SChris Mason int slot; 908be0e5c09SChris Mason int i; 909be0e5c09SChris Mason int free_space; 910be0e5c09SChris Mason int push_space = 0; 911be0e5c09SChris Mason int push_items = 0; 9120783fcfcSChris Mason struct btrfs_item *item; 9137518a238SChris Mason u32 old_left_nritems; 914aa5d6bedSChris Mason int ret = 0; 915aa5d6bedSChris Mason int wret; 916be0e5c09SChris Mason 917be0e5c09SChris Mason slot = path->slots[1]; 918be0e5c09SChris Mason if (slot == 0) { 919be0e5c09SChris Mason return 1; 920be0e5c09SChris Mason } 921be0e5c09SChris Mason if (!path->nodes[1]) { 922be0e5c09SChris Mason return 1; 923be0e5c09SChris Mason } 9241d4f8a0cSChris Mason t = read_tree_block(root, btrfs_node_blockptr(&path->nodes[1]->node, 9251d4f8a0cSChris Mason slot - 1)); 926eb60ceacSChris Mason left = &t->leaf; 927123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9280783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 929234b63a0SChris Mason btrfs_block_release(root, t); 930be0e5c09SChris Mason return 1; 931be0e5c09SChris Mason } 93202217ed2SChris Mason 93302217ed2SChris Mason /* cow and double check */ 93402217ed2SChris Mason btrfs_cow_block(root, t, path->nodes[1], slot - 1, &t); 93502217ed2SChris Mason left = &t->leaf; 936123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9370783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 938234b63a0SChris Mason btrfs_block_release(root, t); 93902217ed2SChris Mason return 1; 94002217ed2SChris Mason } 94102217ed2SChris Mason 9427518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 943be0e5c09SChris Mason item = right->items + i; 944be0e5c09SChris Mason if (path->slots[0] == i) 945be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9460783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 9470783fcfcSChris Mason free_space) 948be0e5c09SChris Mason break; 949be0e5c09SChris Mason push_items++; 9500783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 951be0e5c09SChris Mason } 952be0e5c09SChris Mason if (push_items == 0) { 953234b63a0SChris Mason btrfs_block_release(root, t); 954be0e5c09SChris Mason return 1; 955be0e5c09SChris Mason } 956be0e5c09SChris Mason /* push data from right to left */ 9577518a238SChris Mason memcpy(left->items + btrfs_header_nritems(&left->header), 9580783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 959123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 9600783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 961123abc88SChris Mason memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space, 962123abc88SChris Mason btrfs_leaf_data(right) + 963123abc88SChris Mason btrfs_item_offset(right->items + push_items - 1), 964be0e5c09SChris Mason push_space); 9657518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 966eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 967eb60ceacSChris Mason 968be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 969123abc88SChris Mason u32 ioff = btrfs_item_offset(left->items + i); 970123abc88SChris Mason btrfs_set_item_offset(left->items + i, ioff - 971123abc88SChris Mason (BTRFS_LEAF_DATA_SIZE(root) - 9720783fcfcSChris Mason btrfs_item_offset(left->items + 9730783fcfcSChris Mason old_left_nritems - 1))); 974be0e5c09SChris Mason } 9757518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 976be0e5c09SChris Mason 977be0e5c09SChris Mason /* fixup right node */ 9780783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 979123abc88SChris Mason leaf_data_end(root, right); 980123abc88SChris Mason memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 981123abc88SChris Mason push_space, btrfs_leaf_data(right) + 982123abc88SChris Mason leaf_data_end(root, right), push_space); 983be0e5c09SChris Mason memmove(right->items, right->items + push_items, 9847518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 9850783fcfcSChris Mason sizeof(struct btrfs_item)); 9867518a238SChris Mason btrfs_set_header_nritems(&right->header, 9877518a238SChris Mason btrfs_header_nritems(&right->header) - 9887518a238SChris Mason push_items); 989123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 990eb60ceacSChris Mason 9917518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 9920783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 9930783fcfcSChris Mason btrfs_item_size(right->items + i)); 9940783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 995be0e5c09SChris Mason } 996eb60ceacSChris Mason 99702217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 99802217ed2SChris Mason BUG_ON(list_empty(&right_buf->dirty)); 999eb60ceacSChris Mason 1000aa5d6bedSChris Mason wret = fixup_low_keys(root, path, &right->items[0].key, 1); 1001aa5d6bedSChris Mason if (wret) 1002aa5d6bedSChris Mason ret = wret; 1003be0e5c09SChris Mason 1004be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1005be0e5c09SChris Mason if (path->slots[0] < push_items) { 1006be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1007234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1008eb60ceacSChris Mason path->nodes[0] = t; 1009be0e5c09SChris Mason path->slots[1] -= 1; 1010be0e5c09SChris Mason } else { 1011234b63a0SChris Mason btrfs_block_release(root, t); 1012be0e5c09SChris Mason path->slots[0] -= push_items; 1013be0e5c09SChris Mason } 1014eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1015aa5d6bedSChris Mason return ret; 1016be0e5c09SChris Mason } 1017be0e5c09SChris Mason 101874123bd7SChris Mason /* 101974123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 102074123bd7SChris Mason * available for the resulting leaf level of the path. 1021aa5d6bedSChris Mason * 1022aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 102374123bd7SChris Mason */ 1024234b63a0SChris Mason static int split_leaf(struct btrfs_root *root, struct btrfs_path *path, 1025aa5d6bedSChris Mason int data_size) 1026be0e5c09SChris Mason { 1027234b63a0SChris Mason struct btrfs_buffer *l_buf; 1028234b63a0SChris Mason struct btrfs_leaf *l; 10297518a238SChris Mason u32 nritems; 1030eb60ceacSChris Mason int mid; 1031eb60ceacSChris Mason int slot; 1032234b63a0SChris Mason struct btrfs_leaf *right; 1033234b63a0SChris Mason struct btrfs_buffer *right_buffer; 10340783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1035be0e5c09SChris Mason int data_copy_size; 1036be0e5c09SChris Mason int rt_data_off; 1037be0e5c09SChris Mason int i; 1038be0e5c09SChris Mason int ret; 1039aa5d6bedSChris Mason int wret; 1040be0e5c09SChris Mason 1041eaee50e8SChris Mason wret = push_leaf_left(root, path, data_size); 1042eaee50e8SChris Mason if (wret < 0) 1043eaee50e8SChris Mason return wret; 1044eaee50e8SChris Mason if (wret) { 1045eaee50e8SChris Mason wret = push_leaf_right(root, path, data_size); 1046eaee50e8SChris Mason if (wret < 0) 1047eaee50e8SChris Mason return wret; 1048eaee50e8SChris Mason } 1049eb60ceacSChris Mason l_buf = path->nodes[0]; 1050eb60ceacSChris Mason l = &l_buf->leaf; 1051aa5d6bedSChris Mason 1052aa5d6bedSChris Mason /* did the pushes work? */ 1053123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1054123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1055be0e5c09SChris Mason return 0; 1056aa5d6bedSChris Mason 10575c680ed6SChris Mason if (!path->nodes[1]) { 10585c680ed6SChris Mason ret = insert_new_root(root, path, 1); 10595c680ed6SChris Mason if (ret) 10605c680ed6SChris Mason return ret; 10615c680ed6SChris Mason } 1062eb60ceacSChris Mason slot = path->slots[0]; 10637518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1064eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1065234b63a0SChris Mason right_buffer = btrfs_alloc_free_block(root); 1066eb60ceacSChris Mason BUG_ON(!right_buffer); 1067eb60ceacSChris Mason BUG_ON(mid == nritems); 1068eb60ceacSChris Mason right = &right_buffer->leaf; 1069123abc88SChris Mason memset(&right->header, 0, sizeof(right->header)); 1070be0e5c09SChris Mason if (mid <= slot) { 107197571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1072be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1073123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1074be0e5c09SChris Mason BUG(); 1075be0e5c09SChris Mason } else { 107697571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1077be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1078123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1079be0e5c09SChris Mason BUG(); 1080be0e5c09SChris Mason } 10817518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 10827518a238SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->blocknr); 10837518a238SChris Mason btrfs_set_header_level(&right->header, 0); 10847518a238SChris Mason btrfs_set_header_parentid(&right->header, 10857518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 1086123abc88SChris Mason data_copy_size = btrfs_item_end(l->items + mid) - 1087123abc88SChris Mason leaf_data_end(root, l); 1088be0e5c09SChris Mason memcpy(right->items, l->items + mid, 10890783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1090123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1091123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1092123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 1093123abc88SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1094123abc88SChris Mason btrfs_item_end(l->items + mid); 109574123bd7SChris Mason 10960783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1097123abc88SChris Mason u32 ioff = btrfs_item_offset(right->items + i); 10980783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 10990783fcfcSChris Mason } 110074123bd7SChris Mason 11017518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1102aa5d6bedSChris Mason ret = 0; 1103aa5d6bedSChris Mason wret = insert_ptr(root, path, &right->items[0].key, 11045c680ed6SChris Mason right_buffer->blocknr, path->slots[1] + 1, 1); 1105aa5d6bedSChris Mason if (wret) 1106aa5d6bedSChris Mason ret = wret; 110702217ed2SChris Mason BUG_ON(list_empty(&right_buffer->dirty)); 110802217ed2SChris Mason BUG_ON(list_empty(&l_buf->dirty)); 1109eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1110be0e5c09SChris Mason if (mid <= slot) { 1111234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1112eb60ceacSChris Mason path->nodes[0] = right_buffer; 1113be0e5c09SChris Mason path->slots[0] -= mid; 1114be0e5c09SChris Mason path->slots[1] += 1; 1115eb60ceacSChris Mason } else 1116234b63a0SChris Mason btrfs_block_release(root, right_buffer); 1117eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1118be0e5c09SChris Mason return ret; 1119be0e5c09SChris Mason } 1120be0e5c09SChris Mason 112174123bd7SChris Mason /* 112274123bd7SChris Mason * Given a key and some data, insert an item into the tree. 112374123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 112474123bd7SChris Mason */ 112562e2749eSChris Mason int btrfs_insert_empty_item(struct btrfs_root *root, struct btrfs_path *path, 112662e2749eSChris Mason struct btrfs_key *cpu_key, u32 data_size) 1127be0e5c09SChris Mason { 1128aa5d6bedSChris Mason int ret = 0; 1129be0e5c09SChris Mason int slot; 1130eb60ceacSChris Mason int slot_orig; 1131234b63a0SChris Mason struct btrfs_leaf *leaf; 1132234b63a0SChris Mason struct btrfs_buffer *leaf_buf; 11337518a238SChris Mason u32 nritems; 1134be0e5c09SChris Mason unsigned int data_end; 1135e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1136e2fa7227SChris Mason 1137e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1138be0e5c09SChris Mason 113974123bd7SChris Mason /* create a root if there isn't one */ 11405c680ed6SChris Mason if (!root->node) 1141cfaa7295SChris Mason BUG(); 114262e2749eSChris Mason ret = btrfs_search_slot(root, cpu_key, path, data_size, 1); 1143eb60ceacSChris Mason if (ret == 0) { 114462e2749eSChris Mason btrfs_release_path(root, path); 1145f0930a37SChris Mason return -EEXIST; 1146aa5d6bedSChris Mason } 1147ed2ff2cbSChris Mason if (ret < 0) 1148ed2ff2cbSChris Mason goto out; 1149be0e5c09SChris Mason 115062e2749eSChris Mason slot_orig = path->slots[0]; 115162e2749eSChris Mason leaf_buf = path->nodes[0]; 1152eb60ceacSChris Mason leaf = &leaf_buf->leaf; 115374123bd7SChris Mason 11547518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1155123abc88SChris Mason data_end = leaf_data_end(root, leaf); 1156eb60ceacSChris Mason 1157123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 1158234b63a0SChris Mason sizeof(struct btrfs_item) + data_size) 1159be0e5c09SChris Mason BUG(); 1160be0e5c09SChris Mason 116162e2749eSChris Mason slot = path->slots[0]; 1162eb60ceacSChris Mason BUG_ON(slot < 0); 1163be0e5c09SChris Mason if (slot != nritems) { 1164be0e5c09SChris Mason int i; 11650783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1166be0e5c09SChris Mason 1167be0e5c09SChris Mason /* 1168be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1169be0e5c09SChris Mason */ 1170be0e5c09SChris Mason /* first correct the data pointers */ 11710783fcfcSChris Mason for (i = slot; i < nritems; i++) { 1172123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 11730783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 11740783fcfcSChris Mason ioff - data_size); 11750783fcfcSChris Mason } 1176be0e5c09SChris Mason 1177be0e5c09SChris Mason /* shift the items */ 1178be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 11790783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1180be0e5c09SChris Mason 1181be0e5c09SChris Mason /* shift the data */ 1182123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end - data_size, 1183123abc88SChris Mason btrfs_leaf_data(leaf) + 1184be0e5c09SChris Mason data_end, old_data - data_end); 1185be0e5c09SChris Mason data_end = old_data; 1186be0e5c09SChris Mason } 118762e2749eSChris Mason /* setup the item for the new data */ 1188e2fa7227SChris Mason memcpy(&leaf->items[slot].key, &disk_key, 1189e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 11900783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 11910783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 11927518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1193aa5d6bedSChris Mason 1194aa5d6bedSChris Mason ret = 0; 11958e19f2cdSChris Mason if (slot == 0) 119662e2749eSChris Mason ret = fixup_low_keys(root, path, &disk_key, 1); 1197aa5d6bedSChris Mason 119802217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1199123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1200be0e5c09SChris Mason BUG(); 120162e2749eSChris Mason check_leaf(root, path, 0); 1202ed2ff2cbSChris Mason out: 120362e2749eSChris Mason return ret; 120462e2749eSChris Mason } 120562e2749eSChris Mason 120662e2749eSChris Mason /* 120762e2749eSChris Mason * Given a key and some data, insert an item into the tree. 120862e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 120962e2749eSChris Mason */ 121062e2749eSChris Mason int btrfs_insert_item(struct btrfs_root *root, struct btrfs_key *cpu_key, 121162e2749eSChris Mason void *data, u32 data_size) 121262e2749eSChris Mason { 121362e2749eSChris Mason int ret = 0; 121462e2749eSChris Mason struct btrfs_path path; 121562e2749eSChris Mason u8 *ptr; 121662e2749eSChris Mason 121762e2749eSChris Mason btrfs_init_path(&path); 121862e2749eSChris Mason ret = btrfs_insert_empty_item(root, &path, cpu_key, data_size); 121962e2749eSChris Mason if (!ret) { 122062e2749eSChris Mason ptr = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], u8); 122162e2749eSChris Mason memcpy(ptr, data, data_size); 122262e2749eSChris Mason } 1223234b63a0SChris Mason btrfs_release_path(root, &path); 1224aa5d6bedSChris Mason return ret; 1225be0e5c09SChris Mason } 1226be0e5c09SChris Mason 122774123bd7SChris Mason /* 12285de08d7dSChris Mason * delete the pointer from a given node. 122974123bd7SChris Mason * 123074123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 123174123bd7SChris Mason * continuing all the way the root if required. The root is converted into 123274123bd7SChris Mason * a leaf if all the nodes are emptied. 123374123bd7SChris Mason */ 1234234b63a0SChris Mason static int del_ptr(struct btrfs_root *root, struct btrfs_path *path, int level, 1235bb803951SChris Mason int slot) 1236be0e5c09SChris Mason { 1237234b63a0SChris Mason struct btrfs_node *node; 1238234b63a0SChris Mason struct btrfs_buffer *parent = path->nodes[level]; 12397518a238SChris Mason u32 nritems; 1240aa5d6bedSChris Mason int ret = 0; 1241bb803951SChris Mason int wret; 1242be0e5c09SChris Mason 1243bb803951SChris Mason node = &parent->node; 12447518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1245be0e5c09SChris Mason if (slot != nritems -1) { 1246123abc88SChris Mason memmove(node->ptrs + slot, node->ptrs + slot + 1, 1247123abc88SChris Mason sizeof(struct btrfs_key_ptr) * (nritems - slot - 1)); 1248be0e5c09SChris Mason } 12497518a238SChris Mason nritems--; 12507518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 12517518a238SChris Mason if (nritems == 0 && parent == root->node) { 12527518a238SChris Mason BUG_ON(btrfs_header_level(&root->node->node.header) != 1); 1253eb60ceacSChris Mason /* just turn the root into a leaf and break */ 12547518a238SChris Mason btrfs_set_header_level(&root->node->node.header, 0); 1255bb803951SChris Mason } else if (slot == 0) { 1256123abc88SChris Mason wret = fixup_low_keys(root, path, &node->ptrs[0].key, 1257123abc88SChris Mason level + 1); 12580f70abe2SChris Mason if (wret) 12590f70abe2SChris Mason ret = wret; 1260be0e5c09SChris Mason } 126102217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 1262aa5d6bedSChris Mason return ret; 1263be0e5c09SChris Mason } 1264be0e5c09SChris Mason 126574123bd7SChris Mason /* 126674123bd7SChris Mason * delete the item at the leaf level in path. If that empties 126774123bd7SChris Mason * the leaf, remove it from the tree 126874123bd7SChris Mason */ 1269234b63a0SChris Mason int btrfs_del_item(struct btrfs_root *root, struct btrfs_path *path) 1270be0e5c09SChris Mason { 1271be0e5c09SChris Mason int slot; 1272234b63a0SChris Mason struct btrfs_leaf *leaf; 1273234b63a0SChris Mason struct btrfs_buffer *leaf_buf; 1274be0e5c09SChris Mason int doff; 1275be0e5c09SChris Mason int dsize; 1276aa5d6bedSChris Mason int ret = 0; 1277aa5d6bedSChris Mason int wret; 12787518a238SChris Mason u32 nritems; 1279be0e5c09SChris Mason 1280eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1281eb60ceacSChris Mason leaf = &leaf_buf->leaf; 12824920c9acSChris Mason slot = path->slots[0]; 12830783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 12840783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 12857518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1286be0e5c09SChris Mason 12877518a238SChris Mason if (slot != nritems - 1) { 1288be0e5c09SChris Mason int i; 1289123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 1290123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end + dsize, 1291123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 1292be0e5c09SChris Mason doff - data_end); 12930783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 1294123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 12950783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 12960783fcfcSChris Mason } 1297be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 12980783fcfcSChris Mason sizeof(struct btrfs_item) * 12997518a238SChris Mason (nritems - slot - 1)); 1300be0e5c09SChris Mason } 13017518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 13027518a238SChris Mason nritems--; 130374123bd7SChris Mason /* delete the leaf if we've emptied it */ 13047518a238SChris Mason if (nritems == 0) { 1305eb60ceacSChris Mason if (leaf_buf == root->node) { 13067518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 130702217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 13089a8dd150SChris Mason } else { 1309ed2ff2cbSChris Mason clean_tree_block(root, leaf_buf); 1310bb803951SChris Mason wret = del_ptr(root, path, 1, path->slots[1]); 1311aa5d6bedSChris Mason if (wret) 1312aa5d6bedSChris Mason ret = wret; 1313234b63a0SChris Mason wret = btrfs_free_extent(root, leaf_buf->blocknr, 1); 13140f70abe2SChris Mason if (wret) 13150f70abe2SChris Mason ret = wret; 13169a8dd150SChris Mason } 1317be0e5c09SChris Mason } else { 13187518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1319aa5d6bedSChris Mason if (slot == 0) { 1320aa5d6bedSChris Mason wret = fixup_low_keys(root, path, 1321aa5d6bedSChris Mason &leaf->items[0].key, 1); 1322aa5d6bedSChris Mason if (wret) 1323aa5d6bedSChris Mason ret = wret; 1324aa5d6bedSChris Mason } 132502217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1326aa5d6bedSChris Mason 132774123bd7SChris Mason /* delete the leaf if it is mostly empty */ 1328123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 1329be0e5c09SChris Mason /* push_leaf_left fixes the path. 1330be0e5c09SChris Mason * make sure the path still points to our leaf 1331be0e5c09SChris Mason * for possible call to del_ptr below 1332be0e5c09SChris Mason */ 13334920c9acSChris Mason slot = path->slots[1]; 1334eb60ceacSChris Mason leaf_buf->count++; 1335aa5d6bedSChris Mason wret = push_leaf_left(root, path, 1); 1336aa5d6bedSChris Mason if (wret < 0) 1337aa5d6bedSChris Mason ret = wret; 1338f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 13397518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1340aa5d6bedSChris Mason wret = push_leaf_right(root, path, 1); 1341aa5d6bedSChris Mason if (wret < 0) 1342aa5d6bedSChris Mason ret = wret; 1343aa5d6bedSChris Mason } 13447518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 13455de08d7dSChris Mason u64 blocknr = leaf_buf->blocknr; 1346ed2ff2cbSChris Mason clean_tree_block(root, leaf_buf); 1347bb803951SChris Mason wret = del_ptr(root, path, 1, slot); 1348aa5d6bedSChris Mason if (wret) 1349aa5d6bedSChris Mason ret = wret; 1350234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1351234b63a0SChris Mason wret = btrfs_free_extent(root, blocknr, 1); 13520f70abe2SChris Mason if (wret) 13530f70abe2SChris Mason ret = wret; 13545de08d7dSChris Mason } else { 1355234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1356be0e5c09SChris Mason } 1357be0e5c09SChris Mason } 13589a8dd150SChris Mason } 1359aa5d6bedSChris Mason return ret; 13609a8dd150SChris Mason } 13619a8dd150SChris Mason 136297571fd0SChris Mason /* 136397571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 13640f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 13650f70abe2SChris Mason * returns < 0 on io errors. 136697571fd0SChris Mason */ 1367234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 1368d97e63b6SChris Mason { 1369d97e63b6SChris Mason int slot; 1370d97e63b6SChris Mason int level = 1; 1371d97e63b6SChris Mason u64 blocknr; 1372234b63a0SChris Mason struct btrfs_buffer *c; 1373234b63a0SChris Mason struct btrfs_buffer *next = NULL; 1374d97e63b6SChris Mason 1375234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 1376d97e63b6SChris Mason if (!path->nodes[level]) 13770f70abe2SChris Mason return 1; 1378d97e63b6SChris Mason slot = path->slots[level] + 1; 1379d97e63b6SChris Mason c = path->nodes[level]; 13807518a238SChris Mason if (slot >= btrfs_header_nritems(&c->node.header)) { 1381d97e63b6SChris Mason level++; 1382d97e63b6SChris Mason continue; 1383d97e63b6SChris Mason } 13841d4f8a0cSChris Mason blocknr = btrfs_node_blockptr(&c->node, slot); 1385cfaa7295SChris Mason if (next) 1386234b63a0SChris Mason btrfs_block_release(root, next); 1387d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1388d97e63b6SChris Mason break; 1389d97e63b6SChris Mason } 1390d97e63b6SChris Mason path->slots[level] = slot; 1391d97e63b6SChris Mason while(1) { 1392d97e63b6SChris Mason level--; 1393d97e63b6SChris Mason c = path->nodes[level]; 1394234b63a0SChris Mason btrfs_block_release(root, c); 1395d97e63b6SChris Mason path->nodes[level] = next; 1396d97e63b6SChris Mason path->slots[level] = 0; 1397d97e63b6SChris Mason if (!level) 1398d97e63b6SChris Mason break; 13991d4f8a0cSChris Mason next = read_tree_block(root, 14001d4f8a0cSChris Mason btrfs_node_blockptr(&next->node, 0)); 1401d97e63b6SChris Mason } 1402d97e63b6SChris Mason return 0; 1403d97e63b6SChris Mason } 1404d97e63b6SChris Mason 140502217ed2SChris Mason 1406