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 9e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 10e089f05cSChris Mason *root, struct btrfs_path *path, int level); 11e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 12e089f05cSChris Mason *root, struct btrfs_path *path, int data_size); 13e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 14e089f05cSChris Mason *root, struct btrfs_buffer *dst, struct btrfs_buffer 15e089f05cSChris Mason *src); 16e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 17e089f05cSChris Mason btrfs_root *root, struct btrfs_buffer *dst_buf, 18234b63a0SChris Mason struct btrfs_buffer *src_buf); 19e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 20e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 21d97e63b6SChris Mason 22234b63a0SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 23be0e5c09SChris Mason { 24be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 25be0e5c09SChris Mason } 26be0e5c09SChris Mason 27234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 28eb60ceacSChris Mason { 29eb60ceacSChris Mason int i; 30234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 31eb60ceacSChris Mason if (!p->nodes[i]) 32eb60ceacSChris Mason break; 33234b63a0SChris Mason btrfs_block_release(root, p->nodes[i]); 34eb60ceacSChris Mason } 35aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 36eb60ceacSChris Mason } 37eb60ceacSChris Mason 38e089f05cSChris Mason static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 39e089f05cSChris Mason *root, struct btrfs_buffer *buf, struct btrfs_buffer 40e089f05cSChris Mason *parent, int parent_slot, struct btrfs_buffer 41e089f05cSChris Mason **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 } 49e089f05cSChris Mason cow = btrfs_alloc_free_block(trans, 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; 53e089f05cSChris Mason btrfs_inc_ref(trans, root, buf); 5402217ed2SChris Mason if (buf == root->node) { 5502217ed2SChris Mason root->node = cow; 5602217ed2SChris Mason cow->count++; 57a28ec197SChris Mason if (buf != root->commit_root) 58e089f05cSChris Mason btrfs_free_extent(trans, root, buf->blocknr, 1, 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)); 64e089f05cSChris Mason btrfs_free_extent(trans, root, buf->blocknr, 1, 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; 11062e2749eSChris Mason if (k1.flags > k2->flags) 11162e2749eSChris Mason return 1; 11262e2749eSChris Mason if (k1.flags < k2->flags) 11362e2749eSChris Mason return -1; 114a8a2ee0cSChris Mason if (k1.offset > k2->offset) 115a8a2ee0cSChris Mason return 1; 116a8a2ee0cSChris Mason if (k1.offset < k2->offset) 117a8a2ee0cSChris 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 269e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 270e089f05cSChris Mason *root, struct btrfs_path *path, 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); 313e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 314e089f05cSChris Mason return btrfs_free_extent(trans, root, blocknr, 1, 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) { 327e089f05cSChris Mason btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1, 328e089f05cSChris Mason &left_buf); 329bb803951SChris Mason left = &left_buf->node; 3307518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 331e089f05cSChris Mason wret = push_node_left(trans, 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) { 340e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1, 341e089f05cSChris Mason &right_buf); 34279f95c82SChris Mason right = &right_buf->node; 343e089f05cSChris Mason wret = push_node_left(trans, 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); 349e089f05cSChris Mason clean_tree_block(trans, root, right_buf); 350bb803951SChris Mason right_buf = NULL; 351bb803951SChris Mason right = NULL; 352e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 353e089f05cSChris Mason 1); 354bb803951SChris Mason if (wret) 355bb803951SChris Mason ret = wret; 356e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 357bb803951SChris Mason if (wret) 358bb803951SChris Mason ret = wret; 359bb803951SChris Mason } else { 360123abc88SChris Mason memcpy(&parent->ptrs[pslot + 1].key, 361123abc88SChris Mason &right->ptrs[0].key, 362e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 36302217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 364bb803951SChris Mason } 365bb803951SChris Mason } 3667518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 36779f95c82SChris Mason /* 36879f95c82SChris Mason * we're not allowed to leave a node with one item in the 36979f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 37079f95c82SChris Mason * could try to delete the only pointer in this node. 37179f95c82SChris Mason * So, pull some keys from the left. 37279f95c82SChris Mason * There has to be a left pointer at this point because 37379f95c82SChris Mason * otherwise we would have pulled some pointers from the 37479f95c82SChris Mason * right 37579f95c82SChris Mason */ 37679f95c82SChris Mason BUG_ON(!left_buf); 377e089f05cSChris Mason wret = balance_node_right(trans, root, mid_buf, left_buf); 37879f95c82SChris Mason if (wret < 0) 37979f95c82SChris Mason ret = wret; 38079f95c82SChris Mason BUG_ON(wret == 1); 38179f95c82SChris Mason } 3827518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 38379f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 384bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 385234b63a0SChris Mason btrfs_block_release(root, mid_buf); 386e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 387bb803951SChris Mason mid_buf = NULL; 388bb803951SChris Mason mid = NULL; 389e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 390bb803951SChris Mason if (wret) 391bb803951SChris Mason ret = wret; 392e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 393bb803951SChris Mason if (wret) 394bb803951SChris Mason ret = wret; 39579f95c82SChris Mason } else { 39679f95c82SChris Mason /* update the parent key to reflect our changes */ 397123abc88SChris Mason memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key, 398e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 39902217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 40079f95c82SChris Mason } 401bb803951SChris Mason 40279f95c82SChris Mason /* update the path */ 403bb803951SChris Mason if (left_buf) { 4047518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 405bb803951SChris Mason left_buf->count++; // released below 406bb803951SChris Mason path->nodes[level] = left_buf; 407bb803951SChris Mason path->slots[level + 1] -= 1; 408bb803951SChris Mason path->slots[level] = orig_slot; 409bb803951SChris Mason if (mid_buf) 410234b63a0SChris Mason btrfs_block_release(root, mid_buf); 411bb803951SChris Mason } else { 4127518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 413bb803951SChris Mason path->slots[level] = orig_slot; 414bb803951SChris Mason } 415bb803951SChris Mason } 41679f95c82SChris Mason /* double check we haven't messed things up */ 417123abc88SChris Mason check_block(root, path, level); 4181d4f8a0cSChris Mason if (orig_ptr != btrfs_node_blockptr(&path->nodes[level]->node, 4191d4f8a0cSChris Mason path->slots[level])) 42079f95c82SChris Mason BUG(); 421bb803951SChris Mason 422bb803951SChris Mason if (right_buf) 423234b63a0SChris Mason btrfs_block_release(root, right_buf); 424bb803951SChris Mason if (left_buf) 425234b63a0SChris Mason btrfs_block_release(root, left_buf); 426bb803951SChris Mason return ret; 427bb803951SChris Mason } 428bb803951SChris Mason 42974123bd7SChris Mason /* 43074123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 43174123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 43274123bd7SChris Mason * level of the path (level 0) 43374123bd7SChris Mason * 43474123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 435aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 436aa5d6bedSChris Mason * search a negative error number is returned. 43797571fd0SChris Mason * 43897571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 43997571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 44097571fd0SChris Mason * possible) 44174123bd7SChris Mason */ 442e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 443e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 444e089f05cSChris Mason ins_len, int cow) 445be0e5c09SChris Mason { 446234b63a0SChris Mason struct btrfs_buffer *b; 447234b63a0SChris Mason struct btrfs_buffer *cow_buf; 448234b63a0SChris Mason struct btrfs_node *c; 449be0e5c09SChris Mason int slot; 450be0e5c09SChris Mason int ret; 451be0e5c09SChris Mason int level; 4525c680ed6SChris Mason 453bb803951SChris Mason again: 454bb803951SChris Mason b = root->node; 455eb60ceacSChris Mason b->count++; 456eb60ceacSChris Mason while (b) { 4577518a238SChris Mason level = btrfs_header_level(&b->node.header); 45802217ed2SChris Mason if (cow) { 45902217ed2SChris Mason int wret; 460e089f05cSChris Mason wret = btrfs_cow_block(trans, root, b, p->nodes[level + 461e089f05cSChris Mason 1], p->slots[level + 1], 462e089f05cSChris Mason &cow_buf); 46302217ed2SChris Mason b = cow_buf; 46402217ed2SChris Mason } 46502217ed2SChris Mason BUG_ON(!cow && ins_len); 466eb60ceacSChris Mason c = &b->node; 467eb60ceacSChris Mason p->nodes[level] = b; 468123abc88SChris Mason ret = check_block(root, p, level); 469aa5d6bedSChris Mason if (ret) 470aa5d6bedSChris Mason return -1; 471be0e5c09SChris Mason ret = bin_search(c, key, &slot); 4727518a238SChris Mason if (!btrfs_is_leaf(c)) { 473be0e5c09SChris Mason if (ret && slot > 0) 474be0e5c09SChris Mason slot -= 1; 475be0e5c09SChris Mason p->slots[level] = slot; 4767518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 477123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root)) { 478e089f05cSChris Mason int sret = split_node(trans, root, p, level); 4795c680ed6SChris Mason BUG_ON(sret > 0); 4805c680ed6SChris Mason if (sret) 4815c680ed6SChris Mason return sret; 4825c680ed6SChris Mason b = p->nodes[level]; 4835c680ed6SChris Mason c = &b->node; 4845c680ed6SChris Mason slot = p->slots[level]; 485bb803951SChris Mason } else if (ins_len < 0) { 486e089f05cSChris Mason int sret = balance_level(trans, root, p, 487e089f05cSChris Mason level); 488bb803951SChris Mason if (sret) 489bb803951SChris Mason return sret; 490bb803951SChris Mason b = p->nodes[level]; 491bb803951SChris Mason if (!b) 492bb803951SChris Mason goto again; 493bb803951SChris Mason c = &b->node; 494bb803951SChris Mason slot = p->slots[level]; 4957518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 4965c680ed6SChris Mason } 4971d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 498be0e5c09SChris Mason } else { 499234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 500be0e5c09SChris Mason p->slots[level] = slot; 501123abc88SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 5020783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 503e089f05cSChris Mason int sret = split_leaf(trans, root, p, ins_len); 5045c680ed6SChris Mason BUG_ON(sret > 0); 5055c680ed6SChris Mason if (sret) 5065c680ed6SChris Mason return sret; 5075c680ed6SChris Mason } 508bb803951SChris Mason BUG_ON(root->node->count == 1); 509be0e5c09SChris Mason return ret; 510be0e5c09SChris Mason } 511be0e5c09SChris Mason } 512bb803951SChris Mason BUG_ON(root->node->count == 1); 513aa5d6bedSChris Mason return 1; 514be0e5c09SChris Mason } 515be0e5c09SChris Mason 51674123bd7SChris Mason /* 51774123bd7SChris Mason * adjust the pointers going up the tree, starting at level 51874123bd7SChris Mason * making sure the right key of each node is points to 'key'. 51974123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 52074123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 52174123bd7SChris Mason * higher levels 522aa5d6bedSChris Mason * 523aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 524aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 52574123bd7SChris Mason */ 526e089f05cSChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root 527e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 528e089f05cSChris Mason *key, int level) 529be0e5c09SChris Mason { 530be0e5c09SChris Mason int i; 531aa5d6bedSChris Mason int ret = 0; 532234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 533234b63a0SChris Mason struct btrfs_node *t; 534be0e5c09SChris Mason int tslot = path->slots[i]; 535eb60ceacSChris Mason if (!path->nodes[i]) 536be0e5c09SChris Mason break; 537eb60ceacSChris Mason t = &path->nodes[i]->node; 538123abc88SChris Mason memcpy(&t->ptrs[tslot].key, key, sizeof(*key)); 53902217ed2SChris Mason BUG_ON(list_empty(&path->nodes[i]->dirty)); 540be0e5c09SChris Mason if (tslot != 0) 541be0e5c09SChris Mason break; 542be0e5c09SChris Mason } 543aa5d6bedSChris Mason return ret; 544be0e5c09SChris Mason } 545be0e5c09SChris Mason 54674123bd7SChris Mason /* 54774123bd7SChris Mason * try to push data from one node into the next node left in the 54879f95c82SChris Mason * tree. 549aa5d6bedSChris Mason * 550aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 551aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 55274123bd7SChris Mason */ 553e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 554e089f05cSChris Mason *root, struct btrfs_buffer *dst_buf, struct 555e089f05cSChris Mason btrfs_buffer *src_buf) 556be0e5c09SChris Mason { 557234b63a0SChris Mason struct btrfs_node *src = &src_buf->node; 558234b63a0SChris Mason struct btrfs_node *dst = &dst_buf->node; 559be0e5c09SChris Mason int push_items = 0; 560bb803951SChris Mason int src_nritems; 561bb803951SChris Mason int dst_nritems; 562aa5d6bedSChris Mason int ret = 0; 563be0e5c09SChris Mason 5647518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5657518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 566123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 567eb60ceacSChris Mason if (push_items <= 0) { 568be0e5c09SChris Mason return 1; 569eb60ceacSChris Mason } 570be0e5c09SChris Mason 571be0e5c09SChris Mason if (src_nritems < push_items) 572be0e5c09SChris Mason push_items = src_nritems; 57379f95c82SChris Mason 574123abc88SChris Mason memcpy(dst->ptrs + dst_nritems, src->ptrs, 575123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 576bb803951SChris Mason if (push_items < src_nritems) { 577123abc88SChris Mason memmove(src->ptrs, src->ptrs + push_items, 578e2fa7227SChris Mason (src_nritems - push_items) * 579123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 580bb803951SChris Mason } 5817518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 5827518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 58302217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 58402217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 585bb803951SChris Mason return ret; 586be0e5c09SChris Mason } 587be0e5c09SChris Mason 58897571fd0SChris Mason /* 58979f95c82SChris Mason * try to push data from one node into the next node right in the 59079f95c82SChris Mason * tree. 59179f95c82SChris Mason * 59279f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 59379f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 59479f95c82SChris Mason * 59579f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 59679f95c82SChris Mason */ 597e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 598e089f05cSChris Mason btrfs_root *root, struct btrfs_buffer *dst_buf, 599234b63a0SChris Mason struct btrfs_buffer *src_buf) 60079f95c82SChris Mason { 601234b63a0SChris Mason struct btrfs_node *src = &src_buf->node; 602234b63a0SChris Mason struct btrfs_node *dst = &dst_buf->node; 60379f95c82SChris Mason int push_items = 0; 60479f95c82SChris Mason int max_push; 60579f95c82SChris Mason int src_nritems; 60679f95c82SChris Mason int dst_nritems; 60779f95c82SChris Mason int ret = 0; 60879f95c82SChris Mason 6097518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6107518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 611123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 61279f95c82SChris Mason if (push_items <= 0) { 61379f95c82SChris Mason return 1; 61479f95c82SChris Mason } 61579f95c82SChris Mason 61679f95c82SChris Mason max_push = src_nritems / 2 + 1; 61779f95c82SChris Mason /* don't try to empty the node */ 61879f95c82SChris Mason if (max_push > src_nritems) 61979f95c82SChris Mason return 1; 62079f95c82SChris Mason if (max_push < push_items) 62179f95c82SChris Mason push_items = max_push; 62279f95c82SChris Mason 623123abc88SChris Mason memmove(dst->ptrs + push_items, dst->ptrs, 624123abc88SChris Mason dst_nritems * sizeof(struct btrfs_key_ptr)); 625123abc88SChris Mason memcpy(dst->ptrs, src->ptrs + src_nritems - push_items, 626123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 62779f95c82SChris Mason 6287518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6297518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 63079f95c82SChris Mason 63102217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 63202217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 63379f95c82SChris Mason return ret; 63479f95c82SChris Mason } 63579f95c82SChris Mason 63679f95c82SChris Mason /* 63797571fd0SChris Mason * helper function to insert a new root level in the tree. 63897571fd0SChris Mason * A new node is allocated, and a single item is inserted to 63997571fd0SChris Mason * point to the existing root 640aa5d6bedSChris Mason * 641aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 64297571fd0SChris Mason */ 643e089f05cSChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root 644e089f05cSChris Mason *root, struct btrfs_path *path, int level) 64574123bd7SChris Mason { 646234b63a0SChris Mason struct btrfs_buffer *t; 647234b63a0SChris Mason struct btrfs_node *lower; 648234b63a0SChris Mason struct btrfs_node *c; 649e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 6505c680ed6SChris Mason 6515c680ed6SChris Mason BUG_ON(path->nodes[level]); 6525c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 6535c680ed6SChris Mason 654e089f05cSChris Mason t = btrfs_alloc_free_block(trans, root); 65574123bd7SChris Mason c = &t->node; 656123abc88SChris Mason memset(c, 0, root->blocksize); 6577518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 6587518a238SChris Mason btrfs_set_header_level(&c->header, level); 6597518a238SChris Mason btrfs_set_header_blocknr(&c->header, t->blocknr); 6607518a238SChris Mason btrfs_set_header_parentid(&c->header, 6617518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 66274123bd7SChris Mason lower = &path->nodes[level-1]->node; 6637518a238SChris Mason if (btrfs_is_leaf(lower)) 664234b63a0SChris Mason lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 66574123bd7SChris Mason else 666123abc88SChris Mason lower_key = &lower->ptrs[0].key; 667123abc88SChris Mason memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key)); 6681d4f8a0cSChris Mason btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->blocknr); 669cfaa7295SChris Mason /* the super has an extra ref to root->node */ 670234b63a0SChris Mason btrfs_block_release(root, root->node); 67174123bd7SChris Mason root->node = t; 67274123bd7SChris Mason t->count++; 67374123bd7SChris Mason path->nodes[level] = t; 67474123bd7SChris Mason path->slots[level] = 0; 67574123bd7SChris Mason return 0; 67674123bd7SChris Mason } 6775c680ed6SChris Mason 6785c680ed6SChris Mason /* 6795c680ed6SChris Mason * worker function to insert a single pointer in a node. 6805c680ed6SChris Mason * the node should have enough room for the pointer already 68197571fd0SChris Mason * 6825c680ed6SChris Mason * slot and level indicate where you want the key to go, and 6835c680ed6SChris Mason * blocknr is the block the key points to. 684aa5d6bedSChris Mason * 685aa5d6bedSChris Mason * returns zero on success and < 0 on any error 6865c680ed6SChris Mason */ 687e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 688e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 689e089f05cSChris Mason *key, u64 blocknr, int slot, int level) 6905c680ed6SChris Mason { 691234b63a0SChris Mason struct btrfs_node *lower; 6925c680ed6SChris Mason int nritems; 6935c680ed6SChris Mason 6945c680ed6SChris Mason BUG_ON(!path->nodes[level]); 69574123bd7SChris Mason lower = &path->nodes[level]->node; 6967518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 69774123bd7SChris Mason if (slot > nritems) 69874123bd7SChris Mason BUG(); 699123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 70074123bd7SChris Mason BUG(); 70174123bd7SChris Mason if (slot != nritems) { 702123abc88SChris Mason memmove(lower->ptrs + slot + 1, lower->ptrs + slot, 703123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 70474123bd7SChris Mason } 705123abc88SChris Mason memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key)); 7061d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 7077518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 70802217ed2SChris Mason BUG_ON(list_empty(&path->nodes[level]->dirty)); 70974123bd7SChris Mason return 0; 71074123bd7SChris Mason } 71174123bd7SChris Mason 71297571fd0SChris Mason /* 71397571fd0SChris Mason * split the node at the specified level in path in two. 71497571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 71597571fd0SChris Mason * 71697571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 71797571fd0SChris Mason * left and right, if either one works, it returns right away. 718aa5d6bedSChris Mason * 719aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 72097571fd0SChris Mason */ 721e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 722e089f05cSChris Mason *root, struct btrfs_path *path, int level) 723be0e5c09SChris Mason { 724234b63a0SChris Mason struct btrfs_buffer *t; 725234b63a0SChris Mason struct btrfs_node *c; 726234b63a0SChris Mason struct btrfs_buffer *split_buffer; 727234b63a0SChris Mason struct btrfs_node *split; 728be0e5c09SChris Mason int mid; 7295c680ed6SChris Mason int ret; 730aa5d6bedSChris Mason int wret; 7317518a238SChris Mason u32 c_nritems; 732be0e5c09SChris Mason 7335c680ed6SChris Mason t = path->nodes[level]; 734eb60ceacSChris Mason c = &t->node; 7355c680ed6SChris Mason if (t == root->node) { 7365c680ed6SChris Mason /* trying to split the root, lets make a new one */ 737e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 7385c680ed6SChris Mason if (ret) 7395c680ed6SChris Mason return ret; 7405c680ed6SChris Mason } 7417518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 742e089f05cSChris Mason split_buffer = btrfs_alloc_free_block(trans, root); 7435c680ed6SChris Mason split = &split_buffer->node; 7447518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 7457518a238SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->blocknr); 7467518a238SChris Mason btrfs_set_header_parentid(&split->header, 7477518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 7487518a238SChris Mason mid = (c_nritems + 1) / 2; 749123abc88SChris Mason memcpy(split->ptrs, c->ptrs + mid, 750123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 7517518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7527518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 753aa5d6bedSChris Mason ret = 0; 754aa5d6bedSChris Mason 75502217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 756e089f05cSChris Mason wret = insert_ptr(trans, root, path, &split->ptrs[0].key, 757123abc88SChris Mason split_buffer->blocknr, path->slots[level + 1] + 1, 758123abc88SChris Mason level + 1); 759aa5d6bedSChris Mason if (wret) 760aa5d6bedSChris Mason ret = wret; 761aa5d6bedSChris Mason 7625de08d7dSChris Mason if (path->slots[level] >= mid) { 7635c680ed6SChris Mason path->slots[level] -= mid; 764234b63a0SChris Mason btrfs_block_release(root, t); 7655c680ed6SChris Mason path->nodes[level] = split_buffer; 7665c680ed6SChris Mason path->slots[level + 1] += 1; 767eb60ceacSChris Mason } else { 768234b63a0SChris Mason btrfs_block_release(root, split_buffer); 769be0e5c09SChris Mason } 770aa5d6bedSChris Mason return ret; 771be0e5c09SChris Mason } 772be0e5c09SChris Mason 77374123bd7SChris Mason /* 77474123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 77574123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 77674123bd7SChris Mason * space used both by the item structs and the item data 77774123bd7SChris Mason */ 778234b63a0SChris Mason static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 779be0e5c09SChris Mason { 780be0e5c09SChris Mason int data_len; 781be0e5c09SChris Mason int end = start + nr - 1; 782be0e5c09SChris Mason 783be0e5c09SChris Mason if (!nr) 784be0e5c09SChris Mason return 0; 7850783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 7860783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 7870783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 788be0e5c09SChris Mason return data_len; 789be0e5c09SChris Mason } 790be0e5c09SChris Mason 79174123bd7SChris Mason /* 79200ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 79300ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 794aa5d6bedSChris Mason * 795aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 796aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 79700ec4c51SChris Mason */ 798e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 799e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 80000ec4c51SChris Mason { 801234b63a0SChris Mason struct btrfs_buffer *left_buf = path->nodes[0]; 802234b63a0SChris Mason struct btrfs_leaf *left = &left_buf->leaf; 803234b63a0SChris Mason struct btrfs_leaf *right; 804234b63a0SChris Mason struct btrfs_buffer *right_buf; 805234b63a0SChris Mason struct btrfs_buffer *upper; 80600ec4c51SChris Mason int slot; 80700ec4c51SChris Mason int i; 80800ec4c51SChris Mason int free_space; 80900ec4c51SChris Mason int push_space = 0; 81000ec4c51SChris Mason int push_items = 0; 8110783fcfcSChris Mason struct btrfs_item *item; 8127518a238SChris Mason u32 left_nritems; 8137518a238SChris Mason u32 right_nritems; 81400ec4c51SChris Mason 81500ec4c51SChris Mason slot = path->slots[1]; 81600ec4c51SChris Mason if (!path->nodes[1]) { 81700ec4c51SChris Mason return 1; 81800ec4c51SChris Mason } 81900ec4c51SChris Mason upper = path->nodes[1]; 8207518a238SChris Mason if (slot >= btrfs_header_nritems(&upper->node.header) - 1) { 82100ec4c51SChris Mason return 1; 82200ec4c51SChris Mason } 8231d4f8a0cSChris Mason right_buf = read_tree_block(root, btrfs_node_blockptr(&upper->node, 8241d4f8a0cSChris Mason slot + 1)); 82500ec4c51SChris Mason right = &right_buf->leaf; 826123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8270783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 828234b63a0SChris Mason btrfs_block_release(root, right_buf); 82900ec4c51SChris Mason return 1; 83000ec4c51SChris Mason } 83102217ed2SChris Mason /* cow and double check */ 832e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf); 83302217ed2SChris Mason right = &right_buf->leaf; 834123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8350783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 836234b63a0SChris Mason btrfs_block_release(root, right_buf); 83702217ed2SChris Mason return 1; 83802217ed2SChris Mason } 83902217ed2SChris Mason 8407518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8417518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 84200ec4c51SChris Mason item = left->items + i; 84300ec4c51SChris Mason if (path->slots[0] == i) 84400ec4c51SChris Mason push_space += data_size + sizeof(*item); 8450783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8460783fcfcSChris Mason free_space) 84700ec4c51SChris Mason break; 84800ec4c51SChris Mason push_items++; 8490783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 85000ec4c51SChris Mason } 85100ec4c51SChris Mason if (push_items == 0) { 852234b63a0SChris Mason btrfs_block_release(root, right_buf); 85300ec4c51SChris Mason return 1; 85400ec4c51SChris Mason } 8557518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 85600ec4c51SChris Mason /* push left to right */ 8570783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 858123abc88SChris Mason push_space -= leaf_data_end(root, left); 85900ec4c51SChris Mason /* make room in the right data area */ 860123abc88SChris Mason memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) - 861123abc88SChris Mason push_space, btrfs_leaf_data(right) + leaf_data_end(root, right), 862123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right)); 86300ec4c51SChris Mason /* copy from the left data area */ 864123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space, 865123abc88SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), push_space); 86600ec4c51SChris Mason memmove(right->items + push_items, right->items, 8670783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 86800ec4c51SChris Mason /* copy the items from left to right */ 8697518a238SChris Mason memcpy(right->items, left->items + left_nritems - push_items, 8700783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 87100ec4c51SChris Mason 87200ec4c51SChris Mason /* update the item pointers */ 8737518a238SChris Mason right_nritems += push_items; 8747518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 875123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 8767518a238SChris Mason for (i = 0; i < right_nritems; i++) { 8770783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 8780783fcfcSChris Mason btrfs_item_size(right->items + i)); 8790783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 88000ec4c51SChris Mason } 8817518a238SChris Mason left_nritems -= push_items; 8827518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 88300ec4c51SChris Mason 88402217ed2SChris Mason BUG_ON(list_empty(&left_buf->dirty)); 88502217ed2SChris Mason BUG_ON(list_empty(&right_buf->dirty)); 886123abc88SChris Mason memcpy(&upper->node.ptrs[slot + 1].key, 887e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 88802217ed2SChris Mason BUG_ON(list_empty(&upper->dirty)); 88902217ed2SChris Mason 89000ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 8917518a238SChris Mason if (path->slots[0] >= left_nritems) { 8927518a238SChris Mason path->slots[0] -= left_nritems; 893234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 89400ec4c51SChris Mason path->nodes[0] = right_buf; 89500ec4c51SChris Mason path->slots[1] += 1; 89600ec4c51SChris Mason } else { 897234b63a0SChris Mason btrfs_block_release(root, right_buf); 89800ec4c51SChris Mason } 89900ec4c51SChris Mason return 0; 90000ec4c51SChris Mason } 90100ec4c51SChris Mason /* 90274123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 90374123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 90474123bd7SChris Mason */ 905e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 906e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 907be0e5c09SChris Mason { 908234b63a0SChris Mason struct btrfs_buffer *right_buf = path->nodes[0]; 909234b63a0SChris Mason struct btrfs_leaf *right = &right_buf->leaf; 910234b63a0SChris Mason struct btrfs_buffer *t; 911234b63a0SChris Mason struct btrfs_leaf *left; 912be0e5c09SChris Mason int slot; 913be0e5c09SChris Mason int i; 914be0e5c09SChris Mason int free_space; 915be0e5c09SChris Mason int push_space = 0; 916be0e5c09SChris Mason int push_items = 0; 9170783fcfcSChris Mason struct btrfs_item *item; 9187518a238SChris Mason u32 old_left_nritems; 919aa5d6bedSChris Mason int ret = 0; 920aa5d6bedSChris Mason int wret; 921be0e5c09SChris Mason 922be0e5c09SChris Mason slot = path->slots[1]; 923be0e5c09SChris Mason if (slot == 0) { 924be0e5c09SChris Mason return 1; 925be0e5c09SChris Mason } 926be0e5c09SChris Mason if (!path->nodes[1]) { 927be0e5c09SChris Mason return 1; 928be0e5c09SChris Mason } 9291d4f8a0cSChris Mason t = read_tree_block(root, btrfs_node_blockptr(&path->nodes[1]->node, 9301d4f8a0cSChris Mason slot - 1)); 931eb60ceacSChris Mason left = &t->leaf; 932123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9330783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 934234b63a0SChris Mason btrfs_block_release(root, t); 935be0e5c09SChris Mason return 1; 936be0e5c09SChris Mason } 93702217ed2SChris Mason 93802217ed2SChris Mason /* cow and double check */ 939e089f05cSChris Mason btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); 94002217ed2SChris Mason left = &t->leaf; 941123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9420783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 943234b63a0SChris Mason btrfs_block_release(root, t); 94402217ed2SChris Mason return 1; 94502217ed2SChris Mason } 94602217ed2SChris Mason 9477518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 948be0e5c09SChris Mason item = right->items + i; 949be0e5c09SChris Mason if (path->slots[0] == i) 950be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9510783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 9520783fcfcSChris Mason free_space) 953be0e5c09SChris Mason break; 954be0e5c09SChris Mason push_items++; 9550783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 956be0e5c09SChris Mason } 957be0e5c09SChris Mason if (push_items == 0) { 958234b63a0SChris Mason btrfs_block_release(root, t); 959be0e5c09SChris Mason return 1; 960be0e5c09SChris Mason } 961be0e5c09SChris Mason /* push data from right to left */ 9627518a238SChris Mason memcpy(left->items + btrfs_header_nritems(&left->header), 9630783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 964123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 9650783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 966123abc88SChris Mason memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space, 967123abc88SChris Mason btrfs_leaf_data(right) + 968123abc88SChris Mason btrfs_item_offset(right->items + push_items - 1), 969be0e5c09SChris Mason push_space); 9707518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 971eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 972eb60ceacSChris Mason 973be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 974123abc88SChris Mason u32 ioff = btrfs_item_offset(left->items + i); 975123abc88SChris Mason btrfs_set_item_offset(left->items + i, ioff - 976123abc88SChris Mason (BTRFS_LEAF_DATA_SIZE(root) - 9770783fcfcSChris Mason btrfs_item_offset(left->items + 9780783fcfcSChris Mason old_left_nritems - 1))); 979be0e5c09SChris Mason } 9807518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 981be0e5c09SChris Mason 982be0e5c09SChris Mason /* fixup right node */ 9830783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 984123abc88SChris Mason leaf_data_end(root, right); 985123abc88SChris Mason memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 986123abc88SChris Mason push_space, btrfs_leaf_data(right) + 987123abc88SChris Mason leaf_data_end(root, right), push_space); 988be0e5c09SChris Mason memmove(right->items, right->items + push_items, 9897518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 9900783fcfcSChris Mason sizeof(struct btrfs_item)); 9917518a238SChris Mason btrfs_set_header_nritems(&right->header, 9927518a238SChris Mason btrfs_header_nritems(&right->header) - 9937518a238SChris Mason push_items); 994123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 995eb60ceacSChris Mason 9967518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 9970783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 9980783fcfcSChris Mason btrfs_item_size(right->items + i)); 9990783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 1000be0e5c09SChris Mason } 1001eb60ceacSChris Mason 100202217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 100302217ed2SChris Mason BUG_ON(list_empty(&right_buf->dirty)); 1004eb60ceacSChris Mason 1005e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); 1006aa5d6bedSChris Mason if (wret) 1007aa5d6bedSChris Mason ret = wret; 1008be0e5c09SChris Mason 1009be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1010be0e5c09SChris Mason if (path->slots[0] < push_items) { 1011be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1012234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1013eb60ceacSChris Mason path->nodes[0] = t; 1014be0e5c09SChris Mason path->slots[1] -= 1; 1015be0e5c09SChris Mason } else { 1016234b63a0SChris Mason btrfs_block_release(root, t); 1017be0e5c09SChris Mason path->slots[0] -= push_items; 1018be0e5c09SChris Mason } 1019eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1020aa5d6bedSChris Mason return ret; 1021be0e5c09SChris Mason } 1022be0e5c09SChris Mason 102374123bd7SChris Mason /* 102474123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 102574123bd7SChris Mason * available for the resulting leaf level of the path. 1026aa5d6bedSChris Mason * 1027aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 102874123bd7SChris Mason */ 1029e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1030e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1031be0e5c09SChris Mason { 1032234b63a0SChris Mason struct btrfs_buffer *l_buf; 1033234b63a0SChris Mason struct btrfs_leaf *l; 10347518a238SChris Mason u32 nritems; 1035eb60ceacSChris Mason int mid; 1036eb60ceacSChris Mason int slot; 1037234b63a0SChris Mason struct btrfs_leaf *right; 1038234b63a0SChris Mason struct btrfs_buffer *right_buffer; 10390783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1040be0e5c09SChris Mason int data_copy_size; 1041be0e5c09SChris Mason int rt_data_off; 1042be0e5c09SChris Mason int i; 1043be0e5c09SChris Mason int ret; 1044aa5d6bedSChris Mason int wret; 1045be0e5c09SChris Mason 1046e089f05cSChris Mason wret = push_leaf_left(trans, root, path, data_size); 1047eaee50e8SChris Mason if (wret < 0) 1048eaee50e8SChris Mason return wret; 1049eaee50e8SChris Mason if (wret) { 1050e089f05cSChris Mason wret = push_leaf_right(trans, root, path, data_size); 1051eaee50e8SChris Mason if (wret < 0) 1052eaee50e8SChris Mason return wret; 1053eaee50e8SChris Mason } 1054eb60ceacSChris Mason l_buf = path->nodes[0]; 1055eb60ceacSChris Mason l = &l_buf->leaf; 1056aa5d6bedSChris Mason 1057aa5d6bedSChris Mason /* did the pushes work? */ 1058123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1059123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1060be0e5c09SChris Mason return 0; 1061aa5d6bedSChris Mason 10625c680ed6SChris Mason if (!path->nodes[1]) { 1063e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 10645c680ed6SChris Mason if (ret) 10655c680ed6SChris Mason return ret; 10665c680ed6SChris Mason } 1067eb60ceacSChris Mason slot = path->slots[0]; 10687518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1069eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1070e089f05cSChris Mason right_buffer = btrfs_alloc_free_block(trans, root); 1071eb60ceacSChris Mason BUG_ON(!right_buffer); 1072eb60ceacSChris Mason BUG_ON(mid == nritems); 1073eb60ceacSChris Mason right = &right_buffer->leaf; 1074123abc88SChris Mason memset(&right->header, 0, sizeof(right->header)); 1075be0e5c09SChris Mason if (mid <= slot) { 107697571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1077be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1078123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1079be0e5c09SChris Mason BUG(); 1080be0e5c09SChris Mason } else { 108197571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1082be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1083123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1084be0e5c09SChris Mason BUG(); 1085be0e5c09SChris Mason } 10867518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 10877518a238SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->blocknr); 10887518a238SChris Mason btrfs_set_header_level(&right->header, 0); 10897518a238SChris Mason btrfs_set_header_parentid(&right->header, 10907518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 1091123abc88SChris Mason data_copy_size = btrfs_item_end(l->items + mid) - 1092123abc88SChris Mason leaf_data_end(root, l); 1093be0e5c09SChris Mason memcpy(right->items, l->items + mid, 10940783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1095123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1096123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1097123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 1098123abc88SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1099123abc88SChris Mason btrfs_item_end(l->items + mid); 110074123bd7SChris Mason 11010783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1102123abc88SChris Mason u32 ioff = btrfs_item_offset(right->items + i); 11030783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 11040783fcfcSChris Mason } 110574123bd7SChris Mason 11067518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1107aa5d6bedSChris Mason ret = 0; 1108e089f05cSChris Mason wret = insert_ptr(trans, root, path, &right->items[0].key, 11095c680ed6SChris Mason right_buffer->blocknr, path->slots[1] + 1, 1); 1110aa5d6bedSChris Mason if (wret) 1111aa5d6bedSChris Mason ret = wret; 111202217ed2SChris Mason BUG_ON(list_empty(&right_buffer->dirty)); 111302217ed2SChris Mason BUG_ON(list_empty(&l_buf->dirty)); 1114eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1115be0e5c09SChris Mason if (mid <= slot) { 1116234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1117eb60ceacSChris Mason path->nodes[0] = right_buffer; 1118be0e5c09SChris Mason path->slots[0] -= mid; 1119be0e5c09SChris Mason path->slots[1] += 1; 1120eb60ceacSChris Mason } else 1121234b63a0SChris Mason btrfs_block_release(root, right_buffer); 1122eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1123be0e5c09SChris Mason return ret; 1124be0e5c09SChris Mason } 1125be0e5c09SChris Mason 112674123bd7SChris Mason /* 112774123bd7SChris Mason * Given a key and some data, insert an item into the tree. 112874123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 112974123bd7SChris Mason */ 1130e089f05cSChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1131e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_key 1132e089f05cSChris Mason *cpu_key, u32 data_size) 1133be0e5c09SChris Mason { 1134aa5d6bedSChris Mason int ret = 0; 1135be0e5c09SChris Mason int slot; 1136eb60ceacSChris Mason int slot_orig; 1137234b63a0SChris Mason struct btrfs_leaf *leaf; 1138234b63a0SChris Mason struct btrfs_buffer *leaf_buf; 11397518a238SChris Mason u32 nritems; 1140be0e5c09SChris Mason unsigned int data_end; 1141e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1142e2fa7227SChris Mason 1143e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1144be0e5c09SChris Mason 114574123bd7SChris Mason /* create a root if there isn't one */ 11465c680ed6SChris Mason if (!root->node) 1147cfaa7295SChris Mason BUG(); 1148e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 1149eb60ceacSChris Mason if (ret == 0) { 115062e2749eSChris Mason btrfs_release_path(root, path); 1151f0930a37SChris Mason return -EEXIST; 1152aa5d6bedSChris Mason } 1153ed2ff2cbSChris Mason if (ret < 0) 1154ed2ff2cbSChris Mason goto out; 1155be0e5c09SChris Mason 115662e2749eSChris Mason slot_orig = path->slots[0]; 115762e2749eSChris Mason leaf_buf = path->nodes[0]; 1158eb60ceacSChris Mason leaf = &leaf_buf->leaf; 115974123bd7SChris Mason 11607518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1161123abc88SChris Mason data_end = leaf_data_end(root, leaf); 1162eb60ceacSChris Mason 1163123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 1164234b63a0SChris Mason sizeof(struct btrfs_item) + data_size) 1165be0e5c09SChris Mason BUG(); 1166be0e5c09SChris Mason 116762e2749eSChris Mason slot = path->slots[0]; 1168eb60ceacSChris Mason BUG_ON(slot < 0); 1169be0e5c09SChris Mason if (slot != nritems) { 1170be0e5c09SChris Mason int i; 11710783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1172be0e5c09SChris Mason 1173be0e5c09SChris Mason /* 1174be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1175be0e5c09SChris Mason */ 1176be0e5c09SChris Mason /* first correct the data pointers */ 11770783fcfcSChris Mason for (i = slot; i < nritems; i++) { 1178123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 11790783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 11800783fcfcSChris Mason ioff - data_size); 11810783fcfcSChris Mason } 1182be0e5c09SChris Mason 1183be0e5c09SChris Mason /* shift the items */ 1184be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 11850783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1186be0e5c09SChris Mason 1187be0e5c09SChris Mason /* shift the data */ 1188123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end - data_size, 1189123abc88SChris Mason btrfs_leaf_data(leaf) + 1190be0e5c09SChris Mason data_end, old_data - data_end); 1191be0e5c09SChris Mason data_end = old_data; 1192be0e5c09SChris Mason } 119362e2749eSChris Mason /* setup the item for the new data */ 1194e2fa7227SChris Mason memcpy(&leaf->items[slot].key, &disk_key, 1195e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 11960783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 11970783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 11987518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1199aa5d6bedSChris Mason 1200aa5d6bedSChris Mason ret = 0; 12018e19f2cdSChris Mason if (slot == 0) 1202e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 1203aa5d6bedSChris Mason 120402217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1205123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1206be0e5c09SChris Mason BUG(); 120762e2749eSChris Mason check_leaf(root, path, 0); 1208ed2ff2cbSChris Mason out: 120962e2749eSChris Mason return ret; 121062e2749eSChris Mason } 121162e2749eSChris Mason 121262e2749eSChris Mason /* 121362e2749eSChris Mason * Given a key and some data, insert an item into the tree. 121462e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 121562e2749eSChris Mason */ 1216e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 1217e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 1218e089f05cSChris Mason data_size) 121962e2749eSChris Mason { 122062e2749eSChris Mason int ret = 0; 122162e2749eSChris Mason struct btrfs_path path; 122262e2749eSChris Mason u8 *ptr; 122362e2749eSChris Mason 122462e2749eSChris Mason btrfs_init_path(&path); 1225e089f05cSChris Mason ret = btrfs_insert_empty_item(trans, root, &path, cpu_key, data_size); 122662e2749eSChris Mason if (!ret) { 122762e2749eSChris Mason ptr = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], u8); 122862e2749eSChris Mason memcpy(ptr, data, data_size); 122962e2749eSChris Mason } 1230234b63a0SChris Mason btrfs_release_path(root, &path); 1231aa5d6bedSChris Mason return ret; 1232be0e5c09SChris Mason } 1233be0e5c09SChris Mason 123474123bd7SChris Mason /* 12355de08d7dSChris Mason * delete the pointer from a given node. 123674123bd7SChris Mason * 123774123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 123874123bd7SChris Mason * continuing all the way the root if required. The root is converted into 123974123bd7SChris Mason * a leaf if all the nodes are emptied. 124074123bd7SChris Mason */ 1241e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1242e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 1243be0e5c09SChris Mason { 1244234b63a0SChris Mason struct btrfs_node *node; 1245234b63a0SChris Mason struct btrfs_buffer *parent = path->nodes[level]; 12467518a238SChris Mason u32 nritems; 1247aa5d6bedSChris Mason int ret = 0; 1248bb803951SChris Mason int wret; 1249be0e5c09SChris Mason 1250bb803951SChris Mason node = &parent->node; 12517518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1252be0e5c09SChris Mason if (slot != nritems -1) { 1253123abc88SChris Mason memmove(node->ptrs + slot, node->ptrs + slot + 1, 1254123abc88SChris Mason sizeof(struct btrfs_key_ptr) * (nritems - slot - 1)); 1255be0e5c09SChris Mason } 12567518a238SChris Mason nritems--; 12577518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 12587518a238SChris Mason if (nritems == 0 && parent == root->node) { 12597518a238SChris Mason BUG_ON(btrfs_header_level(&root->node->node.header) != 1); 1260eb60ceacSChris Mason /* just turn the root into a leaf and break */ 12617518a238SChris Mason btrfs_set_header_level(&root->node->node.header, 0); 1262bb803951SChris Mason } else if (slot == 0) { 1263e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, 1264123abc88SChris Mason level + 1); 12650f70abe2SChris Mason if (wret) 12660f70abe2SChris Mason ret = wret; 1267be0e5c09SChris Mason } 126802217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 1269aa5d6bedSChris Mason return ret; 1270be0e5c09SChris Mason } 1271be0e5c09SChris Mason 127274123bd7SChris Mason /* 127374123bd7SChris Mason * delete the item at the leaf level in path. If that empties 127474123bd7SChris Mason * the leaf, remove it from the tree 127574123bd7SChris Mason */ 1276e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1277e089f05cSChris Mason struct btrfs_path *path) 1278be0e5c09SChris Mason { 1279be0e5c09SChris Mason int slot; 1280234b63a0SChris Mason struct btrfs_leaf *leaf; 1281234b63a0SChris Mason struct btrfs_buffer *leaf_buf; 1282be0e5c09SChris Mason int doff; 1283be0e5c09SChris Mason int dsize; 1284aa5d6bedSChris Mason int ret = 0; 1285aa5d6bedSChris Mason int wret; 12867518a238SChris Mason u32 nritems; 1287be0e5c09SChris Mason 1288eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1289eb60ceacSChris Mason leaf = &leaf_buf->leaf; 12904920c9acSChris Mason slot = path->slots[0]; 12910783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 12920783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 12937518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1294be0e5c09SChris Mason 12957518a238SChris Mason if (slot != nritems - 1) { 1296be0e5c09SChris Mason int i; 1297123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 1298123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end + dsize, 1299123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 1300be0e5c09SChris Mason doff - data_end); 13010783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 1302123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 13030783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 13040783fcfcSChris Mason } 1305be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 13060783fcfcSChris Mason sizeof(struct btrfs_item) * 13077518a238SChris Mason (nritems - slot - 1)); 1308be0e5c09SChris Mason } 13097518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 13107518a238SChris Mason nritems--; 131174123bd7SChris Mason /* delete the leaf if we've emptied it */ 13127518a238SChris Mason if (nritems == 0) { 1313eb60ceacSChris Mason if (leaf_buf == root->node) { 13147518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 131502217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 13169a8dd150SChris Mason } else { 1317e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1318e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 1319aa5d6bedSChris Mason if (wret) 1320aa5d6bedSChris Mason ret = wret; 1321e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 1322e089f05cSChris Mason leaf_buf->blocknr, 1, 1); 13230f70abe2SChris Mason if (wret) 13240f70abe2SChris Mason ret = wret; 13259a8dd150SChris Mason } 1326be0e5c09SChris Mason } else { 13277518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1328aa5d6bedSChris Mason if (slot == 0) { 1329e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 1330aa5d6bedSChris Mason &leaf->items[0].key, 1); 1331aa5d6bedSChris Mason if (wret) 1332aa5d6bedSChris Mason ret = wret; 1333aa5d6bedSChris Mason } 133402217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1335aa5d6bedSChris Mason 133674123bd7SChris Mason /* delete the leaf if it is mostly empty */ 1337123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 1338be0e5c09SChris Mason /* push_leaf_left fixes the path. 1339be0e5c09SChris Mason * make sure the path still points to our leaf 1340be0e5c09SChris Mason * for possible call to del_ptr below 1341be0e5c09SChris Mason */ 13424920c9acSChris Mason slot = path->slots[1]; 1343eb60ceacSChris Mason leaf_buf->count++; 1344e089f05cSChris Mason wret = push_leaf_left(trans, root, path, 1); 1345aa5d6bedSChris Mason if (wret < 0) 1346aa5d6bedSChris Mason ret = wret; 1347f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 13487518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1349e089f05cSChris Mason wret = push_leaf_right(trans, root, path, 1); 1350aa5d6bedSChris Mason if (wret < 0) 1351aa5d6bedSChris Mason ret = wret; 1352aa5d6bedSChris Mason } 13537518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 13545de08d7dSChris Mason u64 blocknr = leaf_buf->blocknr; 1355e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1356e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 1357aa5d6bedSChris Mason if (wret) 1358aa5d6bedSChris Mason ret = wret; 1359234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1360e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1361e089f05cSChris Mason 1, 1); 13620f70abe2SChris Mason if (wret) 13630f70abe2SChris Mason ret = wret; 13645de08d7dSChris Mason } else { 1365234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1366be0e5c09SChris Mason } 1367be0e5c09SChris Mason } 13689a8dd150SChris Mason } 1369aa5d6bedSChris Mason return ret; 13709a8dd150SChris Mason } 13719a8dd150SChris Mason 137297571fd0SChris Mason /* 137397571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 13740f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 13750f70abe2SChris Mason * returns < 0 on io errors. 137697571fd0SChris Mason */ 1377234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 1378d97e63b6SChris Mason { 1379d97e63b6SChris Mason int slot; 1380d97e63b6SChris Mason int level = 1; 1381d97e63b6SChris Mason u64 blocknr; 1382234b63a0SChris Mason struct btrfs_buffer *c; 1383234b63a0SChris Mason struct btrfs_buffer *next = NULL; 1384d97e63b6SChris Mason 1385234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 1386d97e63b6SChris Mason if (!path->nodes[level]) 13870f70abe2SChris Mason return 1; 1388d97e63b6SChris Mason slot = path->slots[level] + 1; 1389d97e63b6SChris Mason c = path->nodes[level]; 13907518a238SChris Mason if (slot >= btrfs_header_nritems(&c->node.header)) { 1391d97e63b6SChris Mason level++; 1392d97e63b6SChris Mason continue; 1393d97e63b6SChris Mason } 13941d4f8a0cSChris Mason blocknr = btrfs_node_blockptr(&c->node, slot); 1395cfaa7295SChris Mason if (next) 1396234b63a0SChris Mason btrfs_block_release(root, next); 1397d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1398d97e63b6SChris Mason break; 1399d97e63b6SChris Mason } 1400d97e63b6SChris Mason path->slots[level] = slot; 1401d97e63b6SChris Mason while(1) { 1402d97e63b6SChris Mason level--; 1403d97e63b6SChris Mason c = path->nodes[level]; 1404234b63a0SChris Mason btrfs_block_release(root, c); 1405d97e63b6SChris Mason path->nodes[level] = next; 1406d97e63b6SChris Mason path->slots[level] = 0; 1407d97e63b6SChris Mason if (!level) 1408d97e63b6SChris Mason break; 14091d4f8a0cSChris Mason next = read_tree_block(root, 14101d4f8a0cSChris Mason btrfs_node_blockptr(&next->node, 0)); 1411d97e63b6SChris Mason } 1412d97e63b6SChris Mason return 0; 1413d97e63b6SChris Mason } 1414