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 9aa5d6bedSChris Mason static int split_node(struct ctree_root *root, struct ctree_path *path, 10aa5d6bedSChris Mason int level); 11aa5d6bedSChris Mason static int split_leaf(struct ctree_root *root, struct ctree_path *path, 12aa5d6bedSChris Mason int data_size); 13bb803951SChris Mason static int push_node_left(struct ctree_root *root, struct tree_buffer *dst, 14bb803951SChris Mason struct tree_buffer *src); 1579f95c82SChris Mason static int balance_node_right(struct ctree_root *root, 1679f95c82SChris Mason struct tree_buffer *dst_buf, 1779f95c82SChris Mason struct tree_buffer *src_buf); 18bb803951SChris Mason static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, 19bb803951SChris Mason int slot); 20d97e63b6SChris Mason 215de08d7dSChris Mason inline void init_path(struct ctree_path *p) 22be0e5c09SChris Mason { 23be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 24be0e5c09SChris Mason } 25be0e5c09SChris Mason 265de08d7dSChris Mason void release_path(struct ctree_root *root, struct ctree_path *p) 27eb60ceacSChris Mason { 28eb60ceacSChris Mason int i; 29eb60ceacSChris Mason for (i = 0; i < MAX_LEVEL; i++) { 30eb60ceacSChris Mason if (!p->nodes[i]) 31eb60ceacSChris Mason break; 32eb60ceacSChris Mason tree_block_release(root, p->nodes[i]); 33eb60ceacSChris Mason } 34aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 35eb60ceacSChris Mason } 36eb60ceacSChris Mason 3702217ed2SChris Mason int btrfs_cow_block(struct ctree_root *root, 3802217ed2SChris Mason struct tree_buffer *buf, 3902217ed2SChris Mason struct tree_buffer *parent, 4002217ed2SChris Mason int parent_slot, 4102217ed2SChris Mason struct tree_buffer **cow_ret) 4202217ed2SChris Mason { 4302217ed2SChris Mason struct tree_buffer *cow; 4402217ed2SChris Mason 4502217ed2SChris Mason if (!list_empty(&buf->dirty)) { 4602217ed2SChris Mason *cow_ret = buf; 4702217ed2SChris Mason return 0; 4802217ed2SChris Mason } 4902217ed2SChris Mason cow = alloc_free_block(root); 5002217ed2SChris Mason memcpy(&cow->node, &buf->node, sizeof(buf->node)); 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) 58a28ec197SChris Mason free_extent(root, buf->blocknr, 1); 5902217ed2SChris Mason tree_block_release(root, buf); 6002217ed2SChris Mason } else { 6102217ed2SChris Mason parent->node.blockptrs[parent_slot] = cow->blocknr; 6202217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 63a28ec197SChris Mason free_extent(root, buf->blocknr, 1); 6402217ed2SChris Mason } 6502217ed2SChris Mason tree_block_release(root, buf); 6602217ed2SChris Mason return 0; 6702217ed2SChris Mason } 6802217ed2SChris Mason 6974123bd7SChris Mason /* 7074123bd7SChris Mason * The leaf data grows from end-to-front in the node. 7174123bd7SChris Mason * this returns the address of the start of the last item, 7274123bd7SChris Mason * which is the stop of the leaf data stack 7374123bd7SChris Mason */ 74be0e5c09SChris Mason static inline unsigned int leaf_data_end(struct leaf *leaf) 75be0e5c09SChris Mason { 767518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 77be0e5c09SChris Mason if (nr == 0) 78d97e63b6SChris Mason return sizeof(leaf->data); 790783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 80be0e5c09SChris Mason } 81be0e5c09SChris Mason 8274123bd7SChris Mason /* 8374123bd7SChris Mason * The space between the end of the leaf items and 8474123bd7SChris Mason * the start of the leaf data. IOW, how much room 8574123bd7SChris Mason * the leaf has left for both items and data 8674123bd7SChris Mason */ 875de08d7dSChris Mason int leaf_free_space(struct leaf *leaf) 88be0e5c09SChris Mason { 89be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 907518a238SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 91be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 92be0e5c09SChris Mason return (char *)(leaf->data + data_end) - (char *)items_end; 93be0e5c09SChris Mason } 94be0e5c09SChris Mason 9574123bd7SChris Mason /* 9674123bd7SChris Mason * compare two keys in a memcmp fashion 9774123bd7SChris Mason */ 98e2fa7227SChris Mason int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 99be0e5c09SChris Mason { 100e2fa7227SChris Mason struct btrfs_key k1; 101e2fa7227SChris Mason 102e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 103e2fa7227SChris Mason 104e2fa7227SChris Mason if (k1.objectid > k2->objectid) 105be0e5c09SChris Mason return 1; 106e2fa7227SChris Mason if (k1.objectid < k2->objectid) 107be0e5c09SChris Mason return -1; 108e2fa7227SChris Mason if (k1.flags > k2->flags) 109be0e5c09SChris Mason return 1; 110e2fa7227SChris Mason if (k1.flags < k2->flags) 111be0e5c09SChris Mason return -1; 112e2fa7227SChris Mason if (k1.offset > k2->offset) 113be0e5c09SChris Mason return 1; 114e2fa7227SChris Mason if (k1.offset < k2->offset) 115be0e5c09SChris Mason return -1; 116be0e5c09SChris Mason return 0; 117be0e5c09SChris Mason } 11874123bd7SChris Mason 119aa5d6bedSChris Mason int check_node(struct ctree_path *path, int level) 120aa5d6bedSChris Mason { 121aa5d6bedSChris Mason int i; 122aa5d6bedSChris Mason struct node *parent = NULL; 123aa5d6bedSChris Mason struct node *node = &path->nodes[level]->node; 124aa5d6bedSChris Mason int parent_slot; 1257518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 126aa5d6bedSChris Mason 127aa5d6bedSChris Mason if (path->nodes[level + 1]) 128aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 129aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1307518a238SChris Mason BUG_ON(nritems == 0); 1317518a238SChris Mason if (parent) { 132e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 133aa5d6bedSChris Mason parent_key = &parent->keys[parent_slot]; 134e2fa7227SChris Mason BUG_ON(memcmp(parent_key, node->keys, 135e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1367518a238SChris Mason BUG_ON(parent->blockptrs[parent_slot] != 1377518a238SChris Mason btrfs_header_blocknr(&node->header)); 138aa5d6bedSChris Mason } 1397518a238SChris Mason BUG_ON(nritems > NODEPTRS_PER_BLOCK); 1407518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 141e2fa7227SChris Mason struct btrfs_key cpukey; 142e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->keys[i + 1]); 143e2fa7227SChris Mason BUG_ON(comp_keys(&node->keys[i], &cpukey) >= 0); 144aa5d6bedSChris Mason } 145aa5d6bedSChris Mason return 0; 146aa5d6bedSChris Mason } 147aa5d6bedSChris Mason 148aa5d6bedSChris Mason int check_leaf(struct ctree_path *path, int level) 149aa5d6bedSChris Mason { 150aa5d6bedSChris Mason int i; 151aa5d6bedSChris Mason struct leaf *leaf = &path->nodes[level]->leaf; 152aa5d6bedSChris Mason struct node *parent = NULL; 153aa5d6bedSChris Mason int parent_slot; 1547518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 155aa5d6bedSChris Mason 156aa5d6bedSChris Mason if (path->nodes[level + 1]) 157aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 158aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1597518a238SChris Mason BUG_ON(leaf_free_space(leaf) < 0); 1607518a238SChris Mason 1617518a238SChris Mason if (nritems == 0) 1627518a238SChris Mason return 0; 1637518a238SChris Mason 1647518a238SChris Mason if (parent) { 165e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 166aa5d6bedSChris Mason parent_key = &parent->keys[parent_slot]; 167aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 168e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1697518a238SChris Mason BUG_ON(parent->blockptrs[parent_slot] != 1707518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 171aa5d6bedSChris Mason } 1727518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 173e2fa7227SChris Mason struct btrfs_key cpukey; 174e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); 175aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 176e2fa7227SChris Mason &cpukey) >= 0); 1770783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) != 1780783fcfcSChris Mason btrfs_item_end(leaf->items + i + 1)); 179aa5d6bedSChris Mason if (i == 0) { 1800783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) + 1810783fcfcSChris Mason btrfs_item_size(leaf->items + i) != 182aa5d6bedSChris Mason LEAF_DATA_SIZE); 183aa5d6bedSChris Mason } 184aa5d6bedSChris Mason } 185aa5d6bedSChris Mason return 0; 186aa5d6bedSChris Mason } 187aa5d6bedSChris Mason 188aa5d6bedSChris Mason int check_block(struct ctree_path *path, int level) 189aa5d6bedSChris Mason { 190aa5d6bedSChris Mason if (level == 0) 191aa5d6bedSChris Mason return check_leaf(path, level); 192aa5d6bedSChris Mason return check_node(path, level); 193aa5d6bedSChris Mason } 194aa5d6bedSChris Mason 19574123bd7SChris Mason /* 19674123bd7SChris Mason * search for key in the array p. items p are item_size apart 19774123bd7SChris Mason * and there are 'max' items in p 19874123bd7SChris Mason * the slot in the array is returned via slot, and it points to 19974123bd7SChris Mason * the place where you would insert key if it is not found in 20074123bd7SChris Mason * the array. 20174123bd7SChris Mason * 20274123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 20374123bd7SChris Mason */ 204e2fa7227SChris Mason int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 205be0e5c09SChris Mason int max, int *slot) 206be0e5c09SChris Mason { 207be0e5c09SChris Mason int low = 0; 208be0e5c09SChris Mason int high = max; 209be0e5c09SChris Mason int mid; 210be0e5c09SChris Mason int ret; 211e2fa7227SChris Mason struct btrfs_disk_key *tmp; 212be0e5c09SChris Mason 213be0e5c09SChris Mason while(low < high) { 214be0e5c09SChris Mason mid = (low + high) / 2; 215e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 216be0e5c09SChris Mason ret = comp_keys(tmp, key); 217be0e5c09SChris Mason 218be0e5c09SChris Mason if (ret < 0) 219be0e5c09SChris Mason low = mid + 1; 220be0e5c09SChris Mason else if (ret > 0) 221be0e5c09SChris Mason high = mid; 222be0e5c09SChris Mason else { 223be0e5c09SChris Mason *slot = mid; 224be0e5c09SChris Mason return 0; 225be0e5c09SChris Mason } 226be0e5c09SChris Mason } 227be0e5c09SChris Mason *slot = low; 228be0e5c09SChris Mason return 1; 229be0e5c09SChris Mason } 230be0e5c09SChris Mason 23197571fd0SChris Mason /* 23297571fd0SChris Mason * simple bin_search frontend that does the right thing for 23397571fd0SChris Mason * leaves vs nodes 23497571fd0SChris Mason */ 235e2fa7227SChris Mason int bin_search(struct node *c, struct btrfs_key *key, int *slot) 236be0e5c09SChris Mason { 2377518a238SChris Mason if (btrfs_is_leaf(c)) { 238be0e5c09SChris Mason struct leaf *l = (struct leaf *)c; 2390783fcfcSChris Mason return generic_bin_search((void *)l->items, 2400783fcfcSChris Mason sizeof(struct btrfs_item), 2417518a238SChris Mason key, btrfs_header_nritems(&c->header), 2427518a238SChris Mason slot); 243be0e5c09SChris Mason } else { 244e2fa7227SChris Mason return generic_bin_search((void *)c->keys, 245e2fa7227SChris Mason sizeof(struct btrfs_disk_key), 2467518a238SChris Mason key, btrfs_header_nritems(&c->header), 2477518a238SChris Mason slot); 248be0e5c09SChris Mason } 249be0e5c09SChris Mason return -1; 250be0e5c09SChris Mason } 251be0e5c09SChris Mason 252bb803951SChris Mason struct tree_buffer *read_node_slot(struct ctree_root *root, 253bb803951SChris Mason struct tree_buffer *parent_buf, 254bb803951SChris Mason int slot) 255bb803951SChris Mason { 256bb803951SChris Mason struct node *node = &parent_buf->node; 257bb803951SChris Mason if (slot < 0) 258bb803951SChris Mason return NULL; 2597518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 260bb803951SChris Mason return NULL; 261bb803951SChris Mason return read_tree_block(root, node->blockptrs[slot]); 262bb803951SChris Mason } 263bb803951SChris Mason 264bb803951SChris Mason static int balance_level(struct ctree_root *root, struct ctree_path *path, 265bb803951SChris Mason int level) 266bb803951SChris Mason { 267bb803951SChris Mason struct tree_buffer *right_buf; 268bb803951SChris Mason struct tree_buffer *mid_buf; 269bb803951SChris Mason struct tree_buffer *left_buf; 270bb803951SChris Mason struct tree_buffer *parent_buf = NULL; 271bb803951SChris Mason struct node *right = NULL; 272bb803951SChris Mason struct node *mid; 273bb803951SChris Mason struct node *left = NULL; 274bb803951SChris Mason struct node *parent = NULL; 275bb803951SChris Mason int ret = 0; 276bb803951SChris Mason int wret; 277bb803951SChris Mason int pslot; 278bb803951SChris Mason int orig_slot = path->slots[level]; 27979f95c82SChris Mason u64 orig_ptr; 280bb803951SChris Mason 281bb803951SChris Mason if (level == 0) 282bb803951SChris Mason return 0; 283bb803951SChris Mason 284bb803951SChris Mason mid_buf = path->nodes[level]; 285bb803951SChris Mason mid = &mid_buf->node; 28679f95c82SChris Mason orig_ptr = mid->blockptrs[orig_slot]; 28779f95c82SChris Mason 288bb803951SChris Mason if (level < MAX_LEVEL - 1) 289bb803951SChris Mason parent_buf = path->nodes[level + 1]; 290bb803951SChris Mason pslot = path->slots[level + 1]; 291bb803951SChris Mason 292bb803951SChris Mason if (!parent_buf) { 293bb803951SChris Mason struct tree_buffer *child; 294bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 295bb803951SChris Mason 2967518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 297bb803951SChris Mason return 0; 298bb803951SChris Mason 299bb803951SChris Mason /* promote the child to a root */ 300bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 301bb803951SChris Mason BUG_ON(!child); 302bb803951SChris Mason root->node = child; 303bb803951SChris Mason path->nodes[level] = NULL; 304bb803951SChris Mason /* once for the path */ 305bb803951SChris Mason tree_block_release(root, mid_buf); 306bb803951SChris Mason /* once for the root ptr */ 307bb803951SChris Mason tree_block_release(root, mid_buf); 308ed2ff2cbSChris Mason clean_tree_block(root, mid_buf); 309bb803951SChris Mason return free_extent(root, blocknr, 1); 310bb803951SChris Mason } 311bb803951SChris Mason parent = &parent_buf->node; 312bb803951SChris Mason 3137518a238SChris Mason if (btrfs_header_nritems(&mid->header) > NODEPTRS_PER_BLOCK / 4) 314bb803951SChris Mason return 0; 315bb803951SChris Mason 316bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 317bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 31879f95c82SChris Mason 31979f95c82SChris Mason /* first, try to make some room in the middle buffer */ 320bb803951SChris Mason if (left_buf) { 32102217ed2SChris Mason btrfs_cow_block(root, left_buf, parent_buf, 32202217ed2SChris Mason pslot - 1, &left_buf); 323bb803951SChris Mason left = &left_buf->node; 3247518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 32579f95c82SChris Mason wret = push_node_left(root, left_buf, mid_buf); 32679f95c82SChris Mason if (wret < 0) 32779f95c82SChris Mason ret = wret; 328bb803951SChris Mason } 32979f95c82SChris Mason 33079f95c82SChris Mason /* 33179f95c82SChris Mason * then try to empty the right most buffer into the middle 33279f95c82SChris Mason */ 333bb803951SChris Mason if (right_buf) { 33402217ed2SChris Mason btrfs_cow_block(root, right_buf, parent_buf, 33502217ed2SChris Mason pslot + 1, &right_buf); 33679f95c82SChris Mason right = &right_buf->node; 33779f95c82SChris Mason wret = push_node_left(root, mid_buf, right_buf); 33879f95c82SChris Mason if (wret < 0) 33979f95c82SChris Mason ret = wret; 3407518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 341bb803951SChris Mason u64 blocknr = right_buf->blocknr; 342bb803951SChris Mason tree_block_release(root, right_buf); 343ed2ff2cbSChris Mason clean_tree_block(root, right_buf); 344bb803951SChris Mason right_buf = NULL; 345bb803951SChris Mason right = NULL; 346bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot + 1); 347bb803951SChris Mason if (wret) 348bb803951SChris Mason ret = wret; 349bb803951SChris Mason wret = free_extent(root, blocknr, 1); 350bb803951SChris Mason if (wret) 351bb803951SChris Mason ret = wret; 352bb803951SChris Mason } else { 353bb803951SChris Mason memcpy(parent->keys + pslot + 1, right->keys, 354e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 35502217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 356bb803951SChris Mason } 357bb803951SChris Mason } 3587518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 35979f95c82SChris Mason /* 36079f95c82SChris Mason * we're not allowed to leave a node with one item in the 36179f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 36279f95c82SChris Mason * could try to delete the only pointer in this node. 36379f95c82SChris Mason * So, pull some keys from the left. 36479f95c82SChris Mason * There has to be a left pointer at this point because 36579f95c82SChris Mason * otherwise we would have pulled some pointers from the 36679f95c82SChris Mason * right 36779f95c82SChris Mason */ 36879f95c82SChris Mason BUG_ON(!left_buf); 36979f95c82SChris Mason wret = balance_node_right(root, mid_buf, left_buf); 37079f95c82SChris Mason if (wret < 0) 37179f95c82SChris Mason ret = wret; 37279f95c82SChris Mason BUG_ON(wret == 1); 37379f95c82SChris Mason } 3747518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 37579f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 376bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 377bb803951SChris Mason tree_block_release(root, mid_buf); 378ed2ff2cbSChris Mason clean_tree_block(root, mid_buf); 379bb803951SChris Mason mid_buf = NULL; 380bb803951SChris Mason mid = NULL; 381bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot); 382bb803951SChris Mason if (wret) 383bb803951SChris Mason ret = wret; 384bb803951SChris Mason wret = free_extent(root, blocknr, 1); 385bb803951SChris Mason if (wret) 386bb803951SChris Mason ret = wret; 38779f95c82SChris Mason } else { 38879f95c82SChris Mason /* update the parent key to reflect our changes */ 389e2fa7227SChris Mason memcpy(parent->keys + pslot, mid->keys, 390e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 39102217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 39279f95c82SChris Mason } 393bb803951SChris Mason 39479f95c82SChris Mason /* update the path */ 395bb803951SChris Mason if (left_buf) { 3967518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 397bb803951SChris Mason left_buf->count++; // released below 398bb803951SChris Mason path->nodes[level] = left_buf; 399bb803951SChris Mason path->slots[level + 1] -= 1; 400bb803951SChris Mason path->slots[level] = orig_slot; 401bb803951SChris Mason if (mid_buf) 402bb803951SChris Mason tree_block_release(root, mid_buf); 403bb803951SChris Mason } else { 4047518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 405bb803951SChris Mason path->slots[level] = orig_slot; 406bb803951SChris Mason } 407bb803951SChris Mason } 40879f95c82SChris Mason /* double check we haven't messed things up */ 40979f95c82SChris Mason check_block(path, level); 41079f95c82SChris Mason if (orig_ptr != path->nodes[level]->node.blockptrs[path->slots[level]]) 41179f95c82SChris Mason BUG(); 412bb803951SChris Mason 413bb803951SChris Mason if (right_buf) 414bb803951SChris Mason tree_block_release(root, right_buf); 415bb803951SChris Mason if (left_buf) 416bb803951SChris Mason tree_block_release(root, left_buf); 417bb803951SChris Mason return ret; 418bb803951SChris Mason } 419bb803951SChris Mason 42074123bd7SChris Mason /* 42174123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 42274123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 42374123bd7SChris Mason * level of the path (level 0) 42474123bd7SChris Mason * 42574123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 426aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 427aa5d6bedSChris Mason * search a negative error number is returned. 42897571fd0SChris Mason * 42997571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 43097571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 43197571fd0SChris Mason * possible) 43274123bd7SChris Mason */ 433e2fa7227SChris Mason int search_slot(struct ctree_root *root, struct btrfs_key *key, 43402217ed2SChris Mason struct ctree_path *p, int ins_len, int cow) 435be0e5c09SChris Mason { 436bb803951SChris Mason struct tree_buffer *b; 43702217ed2SChris Mason struct tree_buffer *cow_buf; 438eb60ceacSChris Mason struct node *c; 439be0e5c09SChris Mason int slot; 440be0e5c09SChris Mason int ret; 441be0e5c09SChris Mason int level; 4425c680ed6SChris Mason 443bb803951SChris Mason again: 444bb803951SChris Mason b = root->node; 445eb60ceacSChris Mason b->count++; 446eb60ceacSChris Mason while (b) { 4477518a238SChris Mason level = btrfs_header_level(&b->node.header); 44802217ed2SChris Mason if (cow) { 44902217ed2SChris Mason int wret; 45002217ed2SChris Mason wret = btrfs_cow_block(root, b, p->nodes[level + 1], 45102217ed2SChris Mason p->slots[level + 1], &cow_buf); 45202217ed2SChris Mason b = cow_buf; 45302217ed2SChris Mason } 45402217ed2SChris Mason BUG_ON(!cow && ins_len); 455eb60ceacSChris Mason c = &b->node; 456eb60ceacSChris Mason p->nodes[level] = b; 457aa5d6bedSChris Mason ret = check_block(p, level); 458aa5d6bedSChris Mason if (ret) 459aa5d6bedSChris Mason return -1; 460be0e5c09SChris Mason ret = bin_search(c, key, &slot); 4617518a238SChris Mason if (!btrfs_is_leaf(c)) { 462be0e5c09SChris Mason if (ret && slot > 0) 463be0e5c09SChris Mason slot -= 1; 464be0e5c09SChris Mason p->slots[level] = slot; 4657518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 4667518a238SChris Mason NODEPTRS_PER_BLOCK) { 4675c680ed6SChris Mason int sret = split_node(root, p, level); 4685c680ed6SChris Mason BUG_ON(sret > 0); 4695c680ed6SChris Mason if (sret) 4705c680ed6SChris Mason return sret; 4715c680ed6SChris Mason b = p->nodes[level]; 4725c680ed6SChris Mason c = &b->node; 4735c680ed6SChris Mason slot = p->slots[level]; 474bb803951SChris Mason } else if (ins_len < 0) { 475bb803951SChris Mason int sret = balance_level(root, p, level); 476bb803951SChris Mason if (sret) 477bb803951SChris Mason return sret; 478bb803951SChris Mason b = p->nodes[level]; 479bb803951SChris Mason if (!b) 480bb803951SChris Mason goto again; 481bb803951SChris Mason c = &b->node; 482bb803951SChris Mason slot = p->slots[level]; 4837518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 4845c680ed6SChris Mason } 485eb60ceacSChris Mason b = read_tree_block(root, c->blockptrs[slot]); 486be0e5c09SChris Mason } else { 4875c680ed6SChris Mason struct leaf *l = (struct leaf *)c; 488be0e5c09SChris Mason p->slots[level] = slot; 4895de08d7dSChris Mason if (ins_len > 0 && leaf_free_space(l) < 4900783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 4915c680ed6SChris Mason int sret = split_leaf(root, p, ins_len); 4925c680ed6SChris Mason BUG_ON(sret > 0); 4935c680ed6SChris Mason if (sret) 4945c680ed6SChris Mason return sret; 4955c680ed6SChris Mason } 496bb803951SChris Mason BUG_ON(root->node->count == 1); 497be0e5c09SChris Mason return ret; 498be0e5c09SChris Mason } 499be0e5c09SChris Mason } 500bb803951SChris Mason BUG_ON(root->node->count == 1); 501aa5d6bedSChris Mason return 1; 502be0e5c09SChris Mason } 503be0e5c09SChris Mason 50474123bd7SChris Mason /* 50574123bd7SChris Mason * adjust the pointers going up the tree, starting at level 50674123bd7SChris Mason * making sure the right key of each node is points to 'key'. 50774123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 50874123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 50974123bd7SChris Mason * higher levels 510aa5d6bedSChris Mason * 511aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 512aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 51374123bd7SChris Mason */ 514aa5d6bedSChris Mason static int fixup_low_keys(struct ctree_root *root, 515e2fa7227SChris Mason struct ctree_path *path, struct btrfs_disk_key *key, 516be0e5c09SChris Mason int level) 517be0e5c09SChris Mason { 518be0e5c09SChris Mason int i; 519aa5d6bedSChris Mason int ret = 0; 520be0e5c09SChris Mason for (i = level; i < MAX_LEVEL; i++) { 521eb60ceacSChris Mason struct node *t; 522be0e5c09SChris Mason int tslot = path->slots[i]; 523eb60ceacSChris Mason if (!path->nodes[i]) 524be0e5c09SChris Mason break; 525eb60ceacSChris Mason t = &path->nodes[i]->node; 526be0e5c09SChris Mason memcpy(t->keys + tslot, key, sizeof(*key)); 52702217ed2SChris Mason BUG_ON(list_empty(&path->nodes[i]->dirty)); 528be0e5c09SChris Mason if (tslot != 0) 529be0e5c09SChris Mason break; 530be0e5c09SChris Mason } 531aa5d6bedSChris Mason return ret; 532be0e5c09SChris Mason } 533be0e5c09SChris Mason 53474123bd7SChris Mason /* 53574123bd7SChris Mason * try to push data from one node into the next node left in the 53679f95c82SChris Mason * tree. 537aa5d6bedSChris Mason * 538aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 539aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 54074123bd7SChris Mason */ 541bb803951SChris Mason static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, 542bb803951SChris Mason struct tree_buffer *src_buf) 543be0e5c09SChris Mason { 544bb803951SChris Mason struct node *src = &src_buf->node; 545bb803951SChris Mason struct node *dst = &dst_buf->node; 546be0e5c09SChris Mason int push_items = 0; 547bb803951SChris Mason int src_nritems; 548bb803951SChris Mason int dst_nritems; 549aa5d6bedSChris Mason int ret = 0; 550be0e5c09SChris Mason 5517518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5527518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 553bb803951SChris Mason push_items = NODEPTRS_PER_BLOCK - dst_nritems; 554eb60ceacSChris Mason if (push_items <= 0) { 555be0e5c09SChris Mason return 1; 556eb60ceacSChris Mason } 557be0e5c09SChris Mason 558be0e5c09SChris Mason if (src_nritems < push_items) 559be0e5c09SChris Mason push_items = src_nritems; 56079f95c82SChris Mason 561bb803951SChris Mason memcpy(dst->keys + dst_nritems, src->keys, 562e2fa7227SChris Mason push_items * sizeof(struct btrfs_disk_key)); 563bb803951SChris Mason memcpy(dst->blockptrs + dst_nritems, src->blockptrs, 564be0e5c09SChris Mason push_items * sizeof(u64)); 565bb803951SChris Mason if (push_items < src_nritems) { 566bb803951SChris Mason memmove(src->keys, src->keys + push_items, 567e2fa7227SChris Mason (src_nritems - push_items) * 568e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 569bb803951SChris Mason memmove(src->blockptrs, src->blockptrs + push_items, 570bb803951SChris Mason (src_nritems - push_items) * sizeof(u64)); 571bb803951SChris Mason } 5727518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 5737518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 57402217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 57502217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 576bb803951SChris Mason return ret; 577be0e5c09SChris Mason } 578be0e5c09SChris Mason 57997571fd0SChris Mason /* 58079f95c82SChris Mason * try to push data from one node into the next node right in the 58179f95c82SChris Mason * tree. 58279f95c82SChris Mason * 58379f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 58479f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 58579f95c82SChris Mason * 58679f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 58779f95c82SChris Mason */ 58879f95c82SChris Mason static int balance_node_right(struct ctree_root *root, 58979f95c82SChris Mason struct tree_buffer *dst_buf, 59079f95c82SChris Mason struct tree_buffer *src_buf) 59179f95c82SChris Mason { 59279f95c82SChris Mason struct node *src = &src_buf->node; 59379f95c82SChris Mason struct node *dst = &dst_buf->node; 59479f95c82SChris Mason int push_items = 0; 59579f95c82SChris Mason int max_push; 59679f95c82SChris Mason int src_nritems; 59779f95c82SChris Mason int dst_nritems; 59879f95c82SChris Mason int ret = 0; 59979f95c82SChris Mason 6007518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6017518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 60279f95c82SChris Mason push_items = NODEPTRS_PER_BLOCK - dst_nritems; 60379f95c82SChris Mason if (push_items <= 0) { 60479f95c82SChris Mason return 1; 60579f95c82SChris Mason } 60679f95c82SChris Mason 60779f95c82SChris Mason max_push = src_nritems / 2 + 1; 60879f95c82SChris Mason /* don't try to empty the node */ 60979f95c82SChris Mason if (max_push > src_nritems) 61079f95c82SChris Mason return 1; 61179f95c82SChris Mason if (max_push < push_items) 61279f95c82SChris Mason push_items = max_push; 61379f95c82SChris Mason 61479f95c82SChris Mason memmove(dst->keys + push_items, dst->keys, 615e2fa7227SChris Mason dst_nritems * sizeof(struct btrfs_disk_key)); 61679f95c82SChris Mason memmove(dst->blockptrs + push_items, dst->blockptrs, 61779f95c82SChris Mason dst_nritems * sizeof(u64)); 61879f95c82SChris Mason memcpy(dst->keys, src->keys + src_nritems - push_items, 619e2fa7227SChris Mason push_items * sizeof(struct btrfs_disk_key)); 62079f95c82SChris Mason memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, 62179f95c82SChris Mason push_items * sizeof(u64)); 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 */ 6385de08d7dSChris Mason static int insert_new_root(struct ctree_root *root, 6395de08d7dSChris Mason struct ctree_path *path, int level) 64074123bd7SChris Mason { 64174123bd7SChris Mason struct tree_buffer *t; 6425c680ed6SChris Mason struct node *lower; 6435c680ed6SChris Mason struct 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 64974123bd7SChris Mason t = alloc_free_block(root); 65074123bd7SChris Mason c = &t->node; 65174123bd7SChris Mason memset(c, 0, sizeof(c)); 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)) 65974123bd7SChris Mason lower_key = &((struct leaf *)lower)->items[0].key; 66074123bd7SChris Mason else 66174123bd7SChris Mason lower_key = lower->keys; 662e2fa7227SChris Mason memcpy(c->keys, lower_key, sizeof(struct btrfs_disk_key)); 66374123bd7SChris Mason c->blockptrs[0] = path->nodes[level-1]->blocknr; 664cfaa7295SChris Mason /* the super has an extra ref to root->node */ 66574123bd7SChris Mason tree_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 */ 682aa5d6bedSChris Mason static int insert_ptr(struct ctree_root *root, 683e2fa7227SChris Mason struct ctree_path *path, struct btrfs_disk_key *key, 6845c680ed6SChris Mason u64 blocknr, int slot, int level) 6855c680ed6SChris Mason { 6865c680ed6SChris Mason struct 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(); 69474123bd7SChris Mason if (nritems == NODEPTRS_PER_BLOCK) 69574123bd7SChris Mason BUG(); 69674123bd7SChris Mason if (slot != nritems) { 69774123bd7SChris Mason memmove(lower->keys + slot + 1, lower->keys + slot, 698e2fa7227SChris Mason (nritems - slot) * sizeof(struct btrfs_disk_key)); 69974123bd7SChris Mason memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, 70074123bd7SChris Mason (nritems - slot) * sizeof(u64)); 70174123bd7SChris Mason } 702e2fa7227SChris Mason memcpy(lower->keys + slot, key, sizeof(struct btrfs_disk_key)); 70374123bd7SChris Mason lower->blockptrs[slot] = blocknr; 7047518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 70574123bd7SChris Mason if (lower->keys[1].objectid == 0) 70674123bd7SChris Mason BUG(); 70702217ed2SChris Mason BUG_ON(list_empty(&path->nodes[level]->dirty)); 70874123bd7SChris Mason return 0; 70974123bd7SChris Mason } 71074123bd7SChris Mason 71197571fd0SChris Mason /* 71297571fd0SChris Mason * split the node at the specified level in path in two. 71397571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 71497571fd0SChris Mason * 71597571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 71697571fd0SChris Mason * left and right, if either one works, it returns right away. 717aa5d6bedSChris Mason * 718aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 71997571fd0SChris Mason */ 720aa5d6bedSChris Mason static int split_node(struct ctree_root *root, struct ctree_path *path, 721aa5d6bedSChris Mason int level) 722be0e5c09SChris Mason { 7235c680ed6SChris Mason struct tree_buffer *t; 7245c680ed6SChris Mason struct node *c; 7255c680ed6SChris Mason struct tree_buffer *split_buffer; 7265c680ed6SChris Mason struct node *split; 727be0e5c09SChris Mason int mid; 7285c680ed6SChris Mason int ret; 729aa5d6bedSChris Mason int wret; 7307518a238SChris Mason u32 c_nritems; 731be0e5c09SChris Mason 7325c680ed6SChris Mason t = path->nodes[level]; 733eb60ceacSChris Mason c = &t->node; 7345c680ed6SChris Mason if (t == root->node) { 7355c680ed6SChris Mason /* trying to split the root, lets make a new one */ 7365c680ed6SChris Mason ret = insert_new_root(root, path, level + 1); 7375c680ed6SChris Mason if (ret) 7385c680ed6SChris Mason return ret; 7395c680ed6SChris Mason } 7407518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 7415c680ed6SChris Mason split_buffer = alloc_free_block(root); 7425c680ed6SChris Mason split = &split_buffer->node; 7437518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 7447518a238SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->blocknr); 7457518a238SChris Mason btrfs_set_header_parentid(&split->header, 7467518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 7477518a238SChris Mason mid = (c_nritems + 1) / 2; 7485c680ed6SChris Mason memcpy(split->keys, c->keys + mid, 749e2fa7227SChris Mason (c_nritems - mid) * sizeof(struct btrfs_disk_key)); 7505c680ed6SChris Mason memcpy(split->blockptrs, c->blockptrs + mid, 7517518a238SChris Mason (c_nritems - mid) * sizeof(u64)); 7527518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7537518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 754aa5d6bedSChris Mason ret = 0; 755aa5d6bedSChris Mason 75602217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 757aa5d6bedSChris Mason wret = insert_ptr(root, path, split->keys, split_buffer->blocknr, 7585c680ed6SChris Mason path->slots[level + 1] + 1, 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; 7645c680ed6SChris Mason tree_block_release(root, t); 7655c680ed6SChris Mason path->nodes[level] = split_buffer; 7665c680ed6SChris Mason path->slots[level + 1] += 1; 767eb60ceacSChris Mason } else { 7685c680ed6SChris Mason tree_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 */ 778aa5d6bedSChris Mason static int leaf_space_used(struct 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 */ 798aa5d6bedSChris Mason static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, 79900ec4c51SChris Mason int data_size) 80000ec4c51SChris Mason { 80100ec4c51SChris Mason struct tree_buffer *left_buf = path->nodes[0]; 80200ec4c51SChris Mason struct leaf *left = &left_buf->leaf; 80300ec4c51SChris Mason struct leaf *right; 80400ec4c51SChris Mason struct tree_buffer *right_buf; 80500ec4c51SChris Mason struct tree_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 } 82300ec4c51SChris Mason right_buf = read_tree_block(root, upper->node.blockptrs[slot + 1]); 82400ec4c51SChris Mason right = &right_buf->leaf; 82500ec4c51SChris Mason free_space = leaf_free_space(right); 8260783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 82700ec4c51SChris Mason tree_block_release(root, right_buf); 82800ec4c51SChris Mason return 1; 82900ec4c51SChris Mason } 83002217ed2SChris Mason /* cow and double check */ 83102217ed2SChris Mason btrfs_cow_block(root, right_buf, upper, slot + 1, &right_buf); 83202217ed2SChris Mason right = &right_buf->leaf; 83302217ed2SChris Mason free_space = leaf_free_space(right); 8340783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 83502217ed2SChris Mason tree_block_release(root, right_buf); 83602217ed2SChris Mason return 1; 83702217ed2SChris Mason } 83802217ed2SChris Mason 8397518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8407518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 84100ec4c51SChris Mason item = left->items + i; 84200ec4c51SChris Mason if (path->slots[0] == i) 84300ec4c51SChris Mason push_space += data_size + sizeof(*item); 8440783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8450783fcfcSChris Mason free_space) 84600ec4c51SChris Mason break; 84700ec4c51SChris Mason push_items++; 8480783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 84900ec4c51SChris Mason } 85000ec4c51SChris Mason if (push_items == 0) { 85100ec4c51SChris Mason tree_block_release(root, right_buf); 85200ec4c51SChris Mason return 1; 85300ec4c51SChris Mason } 8547518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 85500ec4c51SChris Mason /* push left to right */ 8560783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 85700ec4c51SChris Mason push_space -= leaf_data_end(left); 85800ec4c51SChris Mason /* make room in the right data area */ 85900ec4c51SChris Mason memmove(right->data + leaf_data_end(right) - push_space, 86000ec4c51SChris Mason right->data + leaf_data_end(right), 86100ec4c51SChris Mason LEAF_DATA_SIZE - leaf_data_end(right)); 86200ec4c51SChris Mason /* copy from the left data area */ 86300ec4c51SChris Mason memcpy(right->data + LEAF_DATA_SIZE - push_space, 86400ec4c51SChris Mason left->data + leaf_data_end(left), 86500ec4c51SChris Mason 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); 87500ec4c51SChris Mason push_space = LEAF_DATA_SIZE; 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)); 88600ec4c51SChris Mason memcpy(upper->node.keys + slot + 1, 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; 89300ec4c51SChris Mason tree_block_release(root, path->nodes[0]); 89400ec4c51SChris Mason path->nodes[0] = right_buf; 89500ec4c51SChris Mason path->slots[1] += 1; 89600ec4c51SChris Mason } else { 89700ec4c51SChris Mason tree_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 */ 905aa5d6bedSChris Mason static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, 906be0e5c09SChris Mason int data_size) 907be0e5c09SChris Mason { 908eb60ceacSChris Mason struct tree_buffer *right_buf = path->nodes[0]; 909eb60ceacSChris Mason struct leaf *right = &right_buf->leaf; 910eb60ceacSChris Mason struct tree_buffer *t; 911be0e5c09SChris Mason struct 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 } 929eb60ceacSChris Mason t = read_tree_block(root, path->nodes[1]->node.blockptrs[slot - 1]); 930eb60ceacSChris Mason left = &t->leaf; 931be0e5c09SChris Mason free_space = leaf_free_space(left); 9320783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 933eb60ceacSChris Mason tree_block_release(root, t); 934be0e5c09SChris Mason return 1; 935be0e5c09SChris Mason } 93602217ed2SChris Mason 93702217ed2SChris Mason /* cow and double check */ 93802217ed2SChris Mason btrfs_cow_block(root, t, path->nodes[1], slot - 1, &t); 93902217ed2SChris Mason left = &t->leaf; 94002217ed2SChris Mason free_space = leaf_free_space(left); 9410783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 94202217ed2SChris Mason tree_block_release(root, t); 94302217ed2SChris Mason return 1; 94402217ed2SChris Mason } 94502217ed2SChris Mason 9467518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 947be0e5c09SChris Mason item = right->items + i; 948be0e5c09SChris Mason if (path->slots[0] == i) 949be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9500783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 9510783fcfcSChris Mason free_space) 952be0e5c09SChris Mason break; 953be0e5c09SChris Mason push_items++; 9540783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 955be0e5c09SChris Mason } 956be0e5c09SChris Mason if (push_items == 0) { 957eb60ceacSChris Mason tree_block_release(root, t); 958be0e5c09SChris Mason return 1; 959be0e5c09SChris Mason } 960be0e5c09SChris Mason /* push data from right to left */ 9617518a238SChris Mason memcpy(left->items + btrfs_header_nritems(&left->header), 9620783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 9630783fcfcSChris Mason push_space = LEAF_DATA_SIZE - 9640783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 965be0e5c09SChris Mason memcpy(left->data + leaf_data_end(left) - push_space, 9660783fcfcSChris Mason right->data + btrfs_item_offset(right->items + push_items - 1), 967be0e5c09SChris Mason push_space); 9687518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 969eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 970eb60ceacSChris Mason 971be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 9720783fcfcSChris Mason u16 ioff = btrfs_item_offset(left->items + i); 9730783fcfcSChris Mason btrfs_set_item_offset(left->items + i, ioff - (LEAF_DATA_SIZE - 9740783fcfcSChris Mason btrfs_item_offset(left->items + 9750783fcfcSChris Mason old_left_nritems - 1))); 976be0e5c09SChris Mason } 9777518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 978be0e5c09SChris Mason 979be0e5c09SChris Mason /* fixup right node */ 9800783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 9810783fcfcSChris Mason leaf_data_end(right); 982be0e5c09SChris Mason memmove(right->data + LEAF_DATA_SIZE - push_space, right->data + 983be0e5c09SChris Mason leaf_data_end(right), push_space); 984be0e5c09SChris Mason memmove(right->items, right->items + push_items, 9857518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 9860783fcfcSChris Mason sizeof(struct btrfs_item)); 9877518a238SChris Mason btrfs_set_header_nritems(&right->header, 9887518a238SChris Mason btrfs_header_nritems(&right->header) - 9897518a238SChris Mason push_items); 990be0e5c09SChris Mason push_space = LEAF_DATA_SIZE; 991eb60ceacSChris Mason 9927518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 9930783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 9940783fcfcSChris Mason btrfs_item_size(right->items + i)); 9950783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 996be0e5c09SChris Mason } 997eb60ceacSChris Mason 99802217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 99902217ed2SChris Mason BUG_ON(list_empty(&right_buf->dirty)); 1000eb60ceacSChris Mason 1001aa5d6bedSChris Mason wret = fixup_low_keys(root, path, &right->items[0].key, 1); 1002aa5d6bedSChris Mason if (wret) 1003aa5d6bedSChris Mason ret = wret; 1004be0e5c09SChris Mason 1005be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1006be0e5c09SChris Mason if (path->slots[0] < push_items) { 1007be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1008eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 1009eb60ceacSChris Mason path->nodes[0] = t; 1010be0e5c09SChris Mason path->slots[1] -= 1; 1011be0e5c09SChris Mason } else { 1012eb60ceacSChris Mason tree_block_release(root, t); 1013be0e5c09SChris Mason path->slots[0] -= push_items; 1014be0e5c09SChris Mason } 1015eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1016aa5d6bedSChris Mason return ret; 1017be0e5c09SChris Mason } 1018be0e5c09SChris Mason 101974123bd7SChris Mason /* 102074123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 102174123bd7SChris Mason * available for the resulting leaf level of the path. 1022aa5d6bedSChris Mason * 1023aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 102474123bd7SChris Mason */ 1025aa5d6bedSChris Mason static int split_leaf(struct ctree_root *root, struct ctree_path *path, 1026aa5d6bedSChris Mason int data_size) 1027be0e5c09SChris Mason { 1028aa5d6bedSChris Mason struct tree_buffer *l_buf; 1029aa5d6bedSChris Mason struct leaf *l; 10307518a238SChris Mason u32 nritems; 1031eb60ceacSChris Mason int mid; 1032eb60ceacSChris Mason int slot; 1033be0e5c09SChris Mason struct leaf *right; 1034eb60ceacSChris Mason struct tree_buffer *right_buffer; 10350783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1036be0e5c09SChris Mason int data_copy_size; 1037be0e5c09SChris Mason int rt_data_off; 1038be0e5c09SChris Mason int i; 1039be0e5c09SChris Mason int ret; 1040aa5d6bedSChris Mason int wret; 1041be0e5c09SChris Mason 1042eb60ceacSChris Mason l_buf = path->nodes[0]; 1043eb60ceacSChris Mason l = &l_buf->leaf; 1044aa5d6bedSChris Mason 1045aa5d6bedSChris Mason /* did the pushes work? */ 10460783fcfcSChris Mason if (leaf_free_space(l) >= sizeof(struct btrfs_item) + data_size) 1047be0e5c09SChris Mason return 0; 1048aa5d6bedSChris Mason 10495c680ed6SChris Mason if (!path->nodes[1]) { 10505c680ed6SChris Mason ret = insert_new_root(root, path, 1); 10515c680ed6SChris Mason if (ret) 10525c680ed6SChris Mason return ret; 10535c680ed6SChris Mason } 1054eb60ceacSChris Mason slot = path->slots[0]; 10557518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1056eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1057eb60ceacSChris Mason right_buffer = alloc_free_block(root); 1058eb60ceacSChris Mason BUG_ON(!right_buffer); 1059eb60ceacSChris Mason BUG_ON(mid == nritems); 1060eb60ceacSChris Mason right = &right_buffer->leaf; 1061be0e5c09SChris Mason memset(right, 0, sizeof(*right)); 1062be0e5c09SChris Mason if (mid <= slot) { 106397571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1064be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1065be0e5c09SChris Mason LEAF_DATA_SIZE) 1066be0e5c09SChris Mason BUG(); 1067be0e5c09SChris Mason } else { 106897571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1069be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1070be0e5c09SChris Mason LEAF_DATA_SIZE) 1071be0e5c09SChris Mason BUG(); 1072be0e5c09SChris Mason } 10737518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 10747518a238SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->blocknr); 10757518a238SChris Mason btrfs_set_header_level(&right->header, 0); 10767518a238SChris Mason btrfs_set_header_parentid(&right->header, 10777518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 10780783fcfcSChris Mason data_copy_size = btrfs_item_end(l->items + mid) - leaf_data_end(l); 1079be0e5c09SChris Mason memcpy(right->items, l->items + mid, 10800783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1081be0e5c09SChris Mason memcpy(right->data + LEAF_DATA_SIZE - data_copy_size, 1082be0e5c09SChris Mason l->data + leaf_data_end(l), data_copy_size); 10830783fcfcSChris Mason rt_data_off = LEAF_DATA_SIZE - btrfs_item_end(l->items + mid); 108474123bd7SChris Mason 10850783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 10860783fcfcSChris Mason u16 ioff = btrfs_item_offset(right->items + i); 10870783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 10880783fcfcSChris Mason } 108974123bd7SChris Mason 10907518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1091aa5d6bedSChris Mason ret = 0; 1092aa5d6bedSChris Mason wret = insert_ptr(root, path, &right->items[0].key, 10935c680ed6SChris Mason right_buffer->blocknr, path->slots[1] + 1, 1); 1094aa5d6bedSChris Mason if (wret) 1095aa5d6bedSChris Mason ret = wret; 109602217ed2SChris Mason BUG_ON(list_empty(&right_buffer->dirty)); 109702217ed2SChris Mason BUG_ON(list_empty(&l_buf->dirty)); 1098eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1099be0e5c09SChris Mason if (mid <= slot) { 1100eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 1101eb60ceacSChris Mason path->nodes[0] = right_buffer; 1102be0e5c09SChris Mason path->slots[0] -= mid; 1103be0e5c09SChris Mason path->slots[1] += 1; 1104eb60ceacSChris Mason } else 1105eb60ceacSChris Mason tree_block_release(root, right_buffer); 1106eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1107be0e5c09SChris Mason return ret; 1108be0e5c09SChris Mason } 1109be0e5c09SChris Mason 111074123bd7SChris Mason /* 111174123bd7SChris Mason * Given a key and some data, insert an item into the tree. 111274123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 111374123bd7SChris Mason */ 1114e2fa7227SChris Mason int insert_item(struct ctree_root *root, struct btrfs_key *cpu_key, 1115be0e5c09SChris Mason void *data, int data_size) 1116be0e5c09SChris Mason { 1117aa5d6bedSChris Mason int ret = 0; 1118be0e5c09SChris Mason int slot; 1119eb60ceacSChris Mason int slot_orig; 1120be0e5c09SChris Mason struct leaf *leaf; 1121eb60ceacSChris Mason struct tree_buffer *leaf_buf; 11227518a238SChris Mason u32 nritems; 1123be0e5c09SChris Mason unsigned int data_end; 1124be0e5c09SChris Mason struct ctree_path path; 1125e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1126e2fa7227SChris Mason 1127e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1128be0e5c09SChris Mason 112974123bd7SChris Mason /* create a root if there isn't one */ 11305c680ed6SChris Mason if (!root->node) 1131cfaa7295SChris Mason BUG(); 1132be0e5c09SChris Mason init_path(&path); 1133e2fa7227SChris Mason ret = search_slot(root, cpu_key, &path, data_size, 1); 1134eb60ceacSChris Mason if (ret == 0) { 1135eb60ceacSChris Mason release_path(root, &path); 1136f0930a37SChris Mason return -EEXIST; 1137aa5d6bedSChris Mason } 1138ed2ff2cbSChris Mason if (ret < 0) 1139ed2ff2cbSChris Mason goto out; 1140be0e5c09SChris Mason 1141eb60ceacSChris Mason slot_orig = path.slots[0]; 1142eb60ceacSChris Mason leaf_buf = path.nodes[0]; 1143eb60ceacSChris Mason leaf = &leaf_buf->leaf; 114474123bd7SChris Mason 11457518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1146be0e5c09SChris Mason data_end = leaf_data_end(leaf); 1147eb60ceacSChris Mason 11480783fcfcSChris Mason if (leaf_free_space(leaf) < sizeof(struct btrfs_item) + data_size) 1149be0e5c09SChris Mason BUG(); 1150be0e5c09SChris Mason 1151be0e5c09SChris Mason slot = path.slots[0]; 1152eb60ceacSChris Mason BUG_ON(slot < 0); 1153be0e5c09SChris Mason if (slot != nritems) { 1154be0e5c09SChris Mason int i; 11550783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1156be0e5c09SChris Mason 1157be0e5c09SChris Mason /* 1158be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1159be0e5c09SChris Mason */ 1160be0e5c09SChris Mason /* first correct the data pointers */ 11610783fcfcSChris Mason for (i = slot; i < nritems; i++) { 11620783fcfcSChris Mason u16 ioff = btrfs_item_offset(leaf->items + i); 11630783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 11640783fcfcSChris Mason ioff - data_size); 11650783fcfcSChris Mason } 1166be0e5c09SChris Mason 1167be0e5c09SChris Mason /* shift the items */ 1168be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 11690783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1170be0e5c09SChris Mason 1171be0e5c09SChris Mason /* shift the data */ 1172be0e5c09SChris Mason memmove(leaf->data + data_end - data_size, leaf->data + 1173be0e5c09SChris Mason data_end, old_data - data_end); 1174be0e5c09SChris Mason data_end = old_data; 1175be0e5c09SChris Mason } 117674123bd7SChris Mason /* copy the new data in */ 1177e2fa7227SChris Mason memcpy(&leaf->items[slot].key, &disk_key, 1178e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 11790783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 11800783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 1181be0e5c09SChris Mason memcpy(leaf->data + data_end - data_size, data, data_size); 11827518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1183aa5d6bedSChris Mason 1184aa5d6bedSChris Mason ret = 0; 11858e19f2cdSChris Mason if (slot == 0) 1186e2fa7227SChris Mason ret = fixup_low_keys(root, &path, &disk_key, 1); 1187aa5d6bedSChris Mason 118802217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1189be0e5c09SChris Mason if (leaf_free_space(leaf) < 0) 1190be0e5c09SChris Mason BUG(); 1191bb803951SChris Mason check_leaf(&path, 0); 1192ed2ff2cbSChris Mason out: 1193eb60ceacSChris Mason release_path(root, &path); 1194aa5d6bedSChris Mason return ret; 1195be0e5c09SChris Mason } 1196be0e5c09SChris Mason 119774123bd7SChris Mason /* 11985de08d7dSChris Mason * delete the pointer from a given node. 119974123bd7SChris Mason * 120074123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 120174123bd7SChris Mason * continuing all the way the root if required. The root is converted into 120274123bd7SChris Mason * a leaf if all the nodes are emptied. 120374123bd7SChris Mason */ 1204bb803951SChris Mason static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, 1205bb803951SChris Mason int slot) 1206be0e5c09SChris Mason { 1207be0e5c09SChris Mason struct node *node; 1208bb803951SChris Mason struct tree_buffer *parent = path->nodes[level]; 12097518a238SChris Mason u32 nritems; 1210aa5d6bedSChris Mason int ret = 0; 1211bb803951SChris Mason int wret; 1212be0e5c09SChris Mason 1213bb803951SChris Mason node = &parent->node; 12147518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1215be0e5c09SChris Mason if (slot != nritems -1) { 1216be0e5c09SChris Mason memmove(node->keys + slot, node->keys + slot + 1, 1217e2fa7227SChris Mason sizeof(struct btrfs_disk_key) * (nritems - slot - 1)); 1218be0e5c09SChris Mason memmove(node->blockptrs + slot, 1219be0e5c09SChris Mason node->blockptrs + slot + 1, 1220be0e5c09SChris Mason sizeof(u64) * (nritems - slot - 1)); 1221be0e5c09SChris Mason } 12227518a238SChris Mason nritems--; 12237518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 12247518a238SChris Mason if (nritems == 0 && parent == root->node) { 12257518a238SChris Mason BUG_ON(btrfs_header_level(&root->node->node.header) != 1); 1226eb60ceacSChris Mason /* just turn the root into a leaf and break */ 12277518a238SChris Mason btrfs_set_header_level(&root->node->node.header, 0); 1228bb803951SChris Mason } else if (slot == 0) { 1229bb803951SChris Mason wret = fixup_low_keys(root, path, node->keys, level + 1); 12300f70abe2SChris Mason if (wret) 12310f70abe2SChris Mason ret = wret; 1232be0e5c09SChris Mason } 123302217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 1234aa5d6bedSChris Mason return ret; 1235be0e5c09SChris Mason } 1236be0e5c09SChris Mason 123774123bd7SChris Mason /* 123874123bd7SChris Mason * delete the item at the leaf level in path. If that empties 123974123bd7SChris Mason * the leaf, remove it from the tree 124074123bd7SChris Mason */ 12414920c9acSChris Mason int del_item(struct ctree_root *root, struct ctree_path *path) 1242be0e5c09SChris Mason { 1243be0e5c09SChris Mason int slot; 1244be0e5c09SChris Mason struct leaf *leaf; 1245eb60ceacSChris Mason struct tree_buffer *leaf_buf; 1246be0e5c09SChris Mason int doff; 1247be0e5c09SChris Mason int dsize; 1248aa5d6bedSChris Mason int ret = 0; 1249aa5d6bedSChris Mason int wret; 12507518a238SChris Mason u32 nritems; 1251be0e5c09SChris Mason 1252eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1253eb60ceacSChris Mason leaf = &leaf_buf->leaf; 12544920c9acSChris Mason slot = path->slots[0]; 12550783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 12560783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 12577518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1258be0e5c09SChris Mason 12597518a238SChris Mason if (slot != nritems - 1) { 1260be0e5c09SChris Mason int i; 1261be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 1262be0e5c09SChris Mason memmove(leaf->data + data_end + dsize, 1263be0e5c09SChris Mason leaf->data + data_end, 1264be0e5c09SChris Mason doff - data_end); 12650783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 12660783fcfcSChris Mason u16 ioff = btrfs_item_offset(leaf->items + i); 12670783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 12680783fcfcSChris Mason } 1269be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 12700783fcfcSChris Mason sizeof(struct btrfs_item) * 12717518a238SChris Mason (nritems - slot - 1)); 1272be0e5c09SChris Mason } 12737518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 12747518a238SChris Mason nritems--; 127574123bd7SChris Mason /* delete the leaf if we've emptied it */ 12767518a238SChris Mason if (nritems == 0) { 1277eb60ceacSChris Mason if (leaf_buf == root->node) { 12787518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 127902217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 12809a8dd150SChris Mason } else { 1281ed2ff2cbSChris Mason clean_tree_block(root, leaf_buf); 1282bb803951SChris Mason wret = del_ptr(root, path, 1, path->slots[1]); 1283aa5d6bedSChris Mason if (wret) 1284aa5d6bedSChris Mason ret = wret; 12850f70abe2SChris Mason wret = free_extent(root, leaf_buf->blocknr, 1); 12860f70abe2SChris Mason if (wret) 12870f70abe2SChris Mason ret = wret; 12889a8dd150SChris Mason } 1289be0e5c09SChris Mason } else { 12907518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1291aa5d6bedSChris Mason if (slot == 0) { 1292aa5d6bedSChris Mason wret = fixup_low_keys(root, path, 1293aa5d6bedSChris Mason &leaf->items[0].key, 1); 1294aa5d6bedSChris Mason if (wret) 1295aa5d6bedSChris Mason ret = wret; 1296aa5d6bedSChris Mason } 129702217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1298aa5d6bedSChris Mason 129974123bd7SChris Mason /* delete the leaf if it is mostly empty */ 13005de08d7dSChris Mason if (used < LEAF_DATA_SIZE / 3) { 1301be0e5c09SChris Mason /* push_leaf_left fixes the path. 1302be0e5c09SChris Mason * make sure the path still points to our leaf 1303be0e5c09SChris Mason * for possible call to del_ptr below 1304be0e5c09SChris Mason */ 13054920c9acSChris Mason slot = path->slots[1]; 1306eb60ceacSChris Mason leaf_buf->count++; 1307aa5d6bedSChris Mason wret = push_leaf_left(root, path, 1); 1308aa5d6bedSChris Mason if (wret < 0) 1309aa5d6bedSChris Mason ret = wret; 1310f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 13117518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1312aa5d6bedSChris Mason wret = push_leaf_right(root, path, 1); 1313aa5d6bedSChris Mason if (wret < 0) 1314aa5d6bedSChris Mason ret = wret; 1315aa5d6bedSChris Mason } 13167518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 13175de08d7dSChris Mason u64 blocknr = leaf_buf->blocknr; 1318ed2ff2cbSChris Mason clean_tree_block(root, leaf_buf); 1319bb803951SChris Mason wret = del_ptr(root, path, 1, slot); 1320aa5d6bedSChris Mason if (wret) 1321aa5d6bedSChris Mason ret = wret; 13225de08d7dSChris Mason tree_block_release(root, leaf_buf); 13230f70abe2SChris Mason wret = free_extent(root, blocknr, 1); 13240f70abe2SChris Mason if (wret) 13250f70abe2SChris Mason ret = wret; 13265de08d7dSChris Mason } else { 1327eb60ceacSChris Mason tree_block_release(root, leaf_buf); 1328be0e5c09SChris Mason } 1329be0e5c09SChris Mason } 13309a8dd150SChris Mason } 1331aa5d6bedSChris Mason return ret; 13329a8dd150SChris Mason } 13339a8dd150SChris Mason 133497571fd0SChris Mason /* 133597571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 13360f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 13370f70abe2SChris Mason * returns < 0 on io errors. 133897571fd0SChris Mason */ 1339d97e63b6SChris Mason int next_leaf(struct ctree_root *root, struct ctree_path *path) 1340d97e63b6SChris Mason { 1341d97e63b6SChris Mason int slot; 1342d97e63b6SChris Mason int level = 1; 1343d97e63b6SChris Mason u64 blocknr; 1344d97e63b6SChris Mason struct tree_buffer *c; 1345cfaa7295SChris Mason struct tree_buffer *next = NULL; 1346d97e63b6SChris Mason 1347d97e63b6SChris Mason while(level < MAX_LEVEL) { 1348d97e63b6SChris Mason if (!path->nodes[level]) 13490f70abe2SChris Mason return 1; 1350d97e63b6SChris Mason slot = path->slots[level] + 1; 1351d97e63b6SChris Mason c = path->nodes[level]; 13527518a238SChris Mason if (slot >= btrfs_header_nritems(&c->node.header)) { 1353d97e63b6SChris Mason level++; 1354d97e63b6SChris Mason continue; 1355d97e63b6SChris Mason } 1356d97e63b6SChris Mason blocknr = c->node.blockptrs[slot]; 1357cfaa7295SChris Mason if (next) 1358cfaa7295SChris Mason tree_block_release(root, next); 1359d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1360d97e63b6SChris Mason break; 1361d97e63b6SChris Mason } 1362d97e63b6SChris Mason path->slots[level] = slot; 1363d97e63b6SChris Mason while(1) { 1364d97e63b6SChris Mason level--; 1365d97e63b6SChris Mason c = path->nodes[level]; 1366d97e63b6SChris Mason tree_block_release(root, c); 1367d97e63b6SChris Mason path->nodes[level] = next; 1368d97e63b6SChris Mason path->slots[level] = 0; 1369d97e63b6SChris Mason if (!level) 1370d97e63b6SChris Mason break; 1371d97e63b6SChris Mason next = read_tree_block(root, next->node.blockptrs[0]); 1372d97e63b6SChris Mason } 1373d97e63b6SChris Mason return 0; 1374d97e63b6SChris Mason } 1375d97e63b6SChris Mason 137602217ed2SChris Mason 1377