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 { 611d4f8a0cSChris Mason btrfs_set_node_blockptr(&parent->node, parent_slot, 621d4f8a0cSChris Mason cow->blocknr); 6302217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 64a28ec197SChris Mason free_extent(root, buf->blocknr, 1); 6502217ed2SChris Mason } 6602217ed2SChris Mason tree_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 */ 75be0e5c09SChris Mason static inline unsigned int leaf_data_end(struct leaf *leaf) 76be0e5c09SChris Mason { 777518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 78be0e5c09SChris Mason if (nr == 0) 79d97e63b6SChris Mason return sizeof(leaf->data); 800783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 81be0e5c09SChris Mason } 82be0e5c09SChris Mason 8374123bd7SChris Mason /* 8474123bd7SChris Mason * The space between the end of the leaf items and 8574123bd7SChris Mason * the start of the leaf data. IOW, how much room 8674123bd7SChris Mason * the leaf has left for both items and data 8774123bd7SChris Mason */ 885de08d7dSChris Mason int leaf_free_space(struct leaf *leaf) 89be0e5c09SChris Mason { 90be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 917518a238SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 92be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 93be0e5c09SChris Mason return (char *)(leaf->data + data_end) - (char *)items_end; 94be0e5c09SChris Mason } 95be0e5c09SChris Mason 9674123bd7SChris Mason /* 9774123bd7SChris Mason * compare two keys in a memcmp fashion 9874123bd7SChris Mason */ 99e2fa7227SChris Mason int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 100be0e5c09SChris Mason { 101e2fa7227SChris Mason struct btrfs_key k1; 102e2fa7227SChris Mason 103e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 104e2fa7227SChris Mason 105e2fa7227SChris Mason if (k1.objectid > k2->objectid) 106be0e5c09SChris Mason return 1; 107e2fa7227SChris Mason if (k1.objectid < k2->objectid) 108be0e5c09SChris Mason return -1; 109e2fa7227SChris Mason if (k1.flags > k2->flags) 110be0e5c09SChris Mason return 1; 111e2fa7227SChris Mason if (k1.flags < k2->flags) 112be0e5c09SChris Mason return -1; 113e2fa7227SChris Mason if (k1.offset > k2->offset) 114be0e5c09SChris Mason return 1; 115e2fa7227SChris Mason if (k1.offset < k2->offset) 116be0e5c09SChris Mason return -1; 117be0e5c09SChris Mason return 0; 118be0e5c09SChris Mason } 11974123bd7SChris Mason 120aa5d6bedSChris Mason int check_node(struct ctree_path *path, int level) 121aa5d6bedSChris Mason { 122aa5d6bedSChris Mason int i; 123aa5d6bedSChris Mason struct node *parent = NULL; 124aa5d6bedSChris Mason struct node *node = &path->nodes[level]->node; 125aa5d6bedSChris Mason int parent_slot; 1267518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 127aa5d6bedSChris Mason 128aa5d6bedSChris Mason if (path->nodes[level + 1]) 129aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 130aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1317518a238SChris Mason BUG_ON(nritems == 0); 1327518a238SChris Mason if (parent) { 133e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 134aa5d6bedSChris Mason parent_key = &parent->keys[parent_slot]; 135e2fa7227SChris Mason BUG_ON(memcmp(parent_key, node->keys, 136e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1371d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1387518a238SChris Mason btrfs_header_blocknr(&node->header)); 139aa5d6bedSChris Mason } 1407518a238SChris Mason BUG_ON(nritems > NODEPTRS_PER_BLOCK); 1417518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 142e2fa7227SChris Mason struct btrfs_key cpukey; 143e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->keys[i + 1]); 144e2fa7227SChris Mason BUG_ON(comp_keys(&node->keys[i], &cpukey) >= 0); 145aa5d6bedSChris Mason } 146aa5d6bedSChris Mason return 0; 147aa5d6bedSChris Mason } 148aa5d6bedSChris Mason 149aa5d6bedSChris Mason int check_leaf(struct ctree_path *path, int level) 150aa5d6bedSChris Mason { 151aa5d6bedSChris Mason int i; 152aa5d6bedSChris Mason struct leaf *leaf = &path->nodes[level]->leaf; 153aa5d6bedSChris Mason struct node *parent = NULL; 154aa5d6bedSChris Mason int parent_slot; 1557518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 156aa5d6bedSChris Mason 157aa5d6bedSChris Mason if (path->nodes[level + 1]) 158aa5d6bedSChris Mason parent = &path->nodes[level + 1]->node; 159aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1607518a238SChris Mason BUG_ON(leaf_free_space(leaf) < 0); 1617518a238SChris Mason 1627518a238SChris Mason if (nritems == 0) 1637518a238SChris Mason return 0; 1647518a238SChris Mason 1657518a238SChris Mason if (parent) { 166e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 167aa5d6bedSChris Mason parent_key = &parent->keys[parent_slot]; 168aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 169e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1701d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1717518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 172aa5d6bedSChris Mason } 1737518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 174e2fa7227SChris Mason struct btrfs_key cpukey; 175e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); 176aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 177e2fa7227SChris Mason &cpukey) >= 0); 1780783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) != 1790783fcfcSChris Mason btrfs_item_end(leaf->items + i + 1)); 180aa5d6bedSChris Mason if (i == 0) { 1810783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) + 1820783fcfcSChris Mason btrfs_item_size(leaf->items + i) != 183aa5d6bedSChris Mason LEAF_DATA_SIZE); 184aa5d6bedSChris Mason } 185aa5d6bedSChris Mason } 186aa5d6bedSChris Mason return 0; 187aa5d6bedSChris Mason } 188aa5d6bedSChris Mason 189aa5d6bedSChris Mason int check_block(struct ctree_path *path, int level) 190aa5d6bedSChris Mason { 191aa5d6bedSChris Mason if (level == 0) 192aa5d6bedSChris Mason return check_leaf(path, level); 193aa5d6bedSChris Mason return check_node(path, level); 194aa5d6bedSChris Mason } 195aa5d6bedSChris Mason 19674123bd7SChris Mason /* 19774123bd7SChris Mason * search for key in the array p. items p are item_size apart 19874123bd7SChris Mason * and there are 'max' items in p 19974123bd7SChris Mason * the slot in the array is returned via slot, and it points to 20074123bd7SChris Mason * the place where you would insert key if it is not found in 20174123bd7SChris Mason * the array. 20274123bd7SChris Mason * 20374123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 20474123bd7SChris Mason */ 205e2fa7227SChris Mason int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 206be0e5c09SChris Mason int max, int *slot) 207be0e5c09SChris Mason { 208be0e5c09SChris Mason int low = 0; 209be0e5c09SChris Mason int high = max; 210be0e5c09SChris Mason int mid; 211be0e5c09SChris Mason int ret; 212e2fa7227SChris Mason struct btrfs_disk_key *tmp; 213be0e5c09SChris Mason 214be0e5c09SChris Mason while(low < high) { 215be0e5c09SChris Mason mid = (low + high) / 2; 216e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 217be0e5c09SChris Mason ret = comp_keys(tmp, key); 218be0e5c09SChris Mason 219be0e5c09SChris Mason if (ret < 0) 220be0e5c09SChris Mason low = mid + 1; 221be0e5c09SChris Mason else if (ret > 0) 222be0e5c09SChris Mason high = mid; 223be0e5c09SChris Mason else { 224be0e5c09SChris Mason *slot = mid; 225be0e5c09SChris Mason return 0; 226be0e5c09SChris Mason } 227be0e5c09SChris Mason } 228be0e5c09SChris Mason *slot = low; 229be0e5c09SChris Mason return 1; 230be0e5c09SChris Mason } 231be0e5c09SChris Mason 23297571fd0SChris Mason /* 23397571fd0SChris Mason * simple bin_search frontend that does the right thing for 23497571fd0SChris Mason * leaves vs nodes 23597571fd0SChris Mason */ 236e2fa7227SChris Mason int bin_search(struct node *c, struct btrfs_key *key, int *slot) 237be0e5c09SChris Mason { 2387518a238SChris Mason if (btrfs_is_leaf(c)) { 239be0e5c09SChris Mason struct leaf *l = (struct leaf *)c; 2400783fcfcSChris Mason return generic_bin_search((void *)l->items, 2410783fcfcSChris Mason sizeof(struct btrfs_item), 2427518a238SChris Mason key, btrfs_header_nritems(&c->header), 2437518a238SChris Mason slot); 244be0e5c09SChris Mason } else { 245e2fa7227SChris Mason return generic_bin_search((void *)c->keys, 246e2fa7227SChris Mason sizeof(struct btrfs_disk_key), 2477518a238SChris Mason key, btrfs_header_nritems(&c->header), 2487518a238SChris Mason slot); 249be0e5c09SChris Mason } 250be0e5c09SChris Mason return -1; 251be0e5c09SChris Mason } 252be0e5c09SChris Mason 253bb803951SChris Mason struct tree_buffer *read_node_slot(struct ctree_root *root, 254bb803951SChris Mason struct tree_buffer *parent_buf, 255bb803951SChris Mason int slot) 256bb803951SChris Mason { 257bb803951SChris Mason struct node *node = &parent_buf->node; 258bb803951SChris Mason if (slot < 0) 259bb803951SChris Mason return NULL; 2607518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 261bb803951SChris Mason return NULL; 2621d4f8a0cSChris Mason return read_tree_block(root, btrfs_node_blockptr(node, slot)); 263bb803951SChris Mason } 264bb803951SChris Mason 265bb803951SChris Mason static int balance_level(struct ctree_root *root, struct ctree_path *path, 266bb803951SChris Mason int level) 267bb803951SChris Mason { 268bb803951SChris Mason struct tree_buffer *right_buf; 269bb803951SChris Mason struct tree_buffer *mid_buf; 270bb803951SChris Mason struct tree_buffer *left_buf; 271bb803951SChris Mason struct tree_buffer *parent_buf = NULL; 272bb803951SChris Mason struct node *right = NULL; 273bb803951SChris Mason struct node *mid; 274bb803951SChris Mason struct node *left = NULL; 275bb803951SChris Mason struct node *parent = NULL; 276bb803951SChris Mason int ret = 0; 277bb803951SChris Mason int wret; 278bb803951SChris Mason int pslot; 279bb803951SChris Mason int orig_slot = path->slots[level]; 28079f95c82SChris Mason u64 orig_ptr; 281bb803951SChris Mason 282bb803951SChris Mason if (level == 0) 283bb803951SChris Mason return 0; 284bb803951SChris Mason 285bb803951SChris Mason mid_buf = path->nodes[level]; 286bb803951SChris Mason mid = &mid_buf->node; 2871d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 28879f95c82SChris Mason 289bb803951SChris Mason if (level < MAX_LEVEL - 1) 290bb803951SChris Mason parent_buf = path->nodes[level + 1]; 291bb803951SChris Mason pslot = path->slots[level + 1]; 292bb803951SChris Mason 293bb803951SChris Mason if (!parent_buf) { 294bb803951SChris Mason struct tree_buffer *child; 295bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 296bb803951SChris Mason 2977518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 298bb803951SChris Mason return 0; 299bb803951SChris Mason 300bb803951SChris Mason /* promote the child to a root */ 301bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 302bb803951SChris Mason BUG_ON(!child); 303bb803951SChris Mason root->node = child; 304bb803951SChris Mason path->nodes[level] = NULL; 305bb803951SChris Mason /* once for the path */ 306bb803951SChris Mason tree_block_release(root, mid_buf); 307bb803951SChris Mason /* once for the root ptr */ 308bb803951SChris Mason tree_block_release(root, mid_buf); 309ed2ff2cbSChris Mason clean_tree_block(root, mid_buf); 310bb803951SChris Mason return free_extent(root, blocknr, 1); 311bb803951SChris Mason } 312bb803951SChris Mason parent = &parent_buf->node; 313bb803951SChris Mason 3147518a238SChris Mason if (btrfs_header_nritems(&mid->header) > NODEPTRS_PER_BLOCK / 4) 315bb803951SChris Mason return 0; 316bb803951SChris Mason 317bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 318bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 31979f95c82SChris Mason 32079f95c82SChris Mason /* first, try to make some room in the middle buffer */ 321bb803951SChris Mason if (left_buf) { 32202217ed2SChris Mason btrfs_cow_block(root, left_buf, parent_buf, 32302217ed2SChris Mason pslot - 1, &left_buf); 324bb803951SChris Mason left = &left_buf->node; 3257518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 32679f95c82SChris Mason wret = push_node_left(root, left_buf, mid_buf); 32779f95c82SChris Mason if (wret < 0) 32879f95c82SChris Mason ret = wret; 329bb803951SChris Mason } 33079f95c82SChris Mason 33179f95c82SChris Mason /* 33279f95c82SChris Mason * then try to empty the right most buffer into the middle 33379f95c82SChris Mason */ 334bb803951SChris Mason if (right_buf) { 33502217ed2SChris Mason btrfs_cow_block(root, right_buf, parent_buf, 33602217ed2SChris Mason pslot + 1, &right_buf); 33779f95c82SChris Mason right = &right_buf->node; 33879f95c82SChris Mason wret = push_node_left(root, mid_buf, right_buf); 33979f95c82SChris Mason if (wret < 0) 34079f95c82SChris Mason ret = wret; 3417518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 342bb803951SChris Mason u64 blocknr = right_buf->blocknr; 343bb803951SChris Mason tree_block_release(root, right_buf); 344ed2ff2cbSChris Mason clean_tree_block(root, right_buf); 345bb803951SChris Mason right_buf = NULL; 346bb803951SChris Mason right = NULL; 347bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot + 1); 348bb803951SChris Mason if (wret) 349bb803951SChris Mason ret = wret; 350bb803951SChris Mason wret = free_extent(root, blocknr, 1); 351bb803951SChris Mason if (wret) 352bb803951SChris Mason ret = wret; 353bb803951SChris Mason } else { 354bb803951SChris Mason memcpy(parent->keys + pslot + 1, right->keys, 355e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 35602217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 357bb803951SChris Mason } 358bb803951SChris Mason } 3597518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 36079f95c82SChris Mason /* 36179f95c82SChris Mason * we're not allowed to leave a node with one item in the 36279f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 36379f95c82SChris Mason * could try to delete the only pointer in this node. 36479f95c82SChris Mason * So, pull some keys from the left. 36579f95c82SChris Mason * There has to be a left pointer at this point because 36679f95c82SChris Mason * otherwise we would have pulled some pointers from the 36779f95c82SChris Mason * right 36879f95c82SChris Mason */ 36979f95c82SChris Mason BUG_ON(!left_buf); 37079f95c82SChris Mason wret = balance_node_right(root, mid_buf, left_buf); 37179f95c82SChris Mason if (wret < 0) 37279f95c82SChris Mason ret = wret; 37379f95c82SChris Mason BUG_ON(wret == 1); 37479f95c82SChris Mason } 3757518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 37679f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 377bb803951SChris Mason u64 blocknr = mid_buf->blocknr; 378bb803951SChris Mason tree_block_release(root, mid_buf); 379ed2ff2cbSChris Mason clean_tree_block(root, mid_buf); 380bb803951SChris Mason mid_buf = NULL; 381bb803951SChris Mason mid = NULL; 382bb803951SChris Mason wret = del_ptr(root, path, level + 1, pslot); 383bb803951SChris Mason if (wret) 384bb803951SChris Mason ret = wret; 385bb803951SChris Mason wret = free_extent(root, blocknr, 1); 386bb803951SChris Mason if (wret) 387bb803951SChris Mason ret = wret; 38879f95c82SChris Mason } else { 38979f95c82SChris Mason /* update the parent key to reflect our changes */ 390e2fa7227SChris Mason memcpy(parent->keys + pslot, mid->keys, 391e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 39202217ed2SChris Mason BUG_ON(list_empty(&parent_buf->dirty)); 39379f95c82SChris Mason } 394bb803951SChris Mason 39579f95c82SChris Mason /* update the path */ 396bb803951SChris Mason if (left_buf) { 3977518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 398bb803951SChris Mason left_buf->count++; // released below 399bb803951SChris Mason path->nodes[level] = left_buf; 400bb803951SChris Mason path->slots[level + 1] -= 1; 401bb803951SChris Mason path->slots[level] = orig_slot; 402bb803951SChris Mason if (mid_buf) 403bb803951SChris Mason tree_block_release(root, mid_buf); 404bb803951SChris Mason } else { 4057518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 406bb803951SChris Mason path->slots[level] = orig_slot; 407bb803951SChris Mason } 408bb803951SChris Mason } 40979f95c82SChris Mason /* double check we haven't messed things up */ 41079f95c82SChris Mason check_block(path, level); 4111d4f8a0cSChris Mason if (orig_ptr != btrfs_node_blockptr(&path->nodes[level]->node, 4121d4f8a0cSChris Mason path->slots[level])) 41379f95c82SChris Mason BUG(); 414bb803951SChris Mason 415bb803951SChris Mason if (right_buf) 416bb803951SChris Mason tree_block_release(root, right_buf); 417bb803951SChris Mason if (left_buf) 418bb803951SChris Mason tree_block_release(root, left_buf); 419bb803951SChris Mason return ret; 420bb803951SChris Mason } 421bb803951SChris Mason 42274123bd7SChris Mason /* 42374123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 42474123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 42574123bd7SChris Mason * level of the path (level 0) 42674123bd7SChris Mason * 42774123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 428aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 429aa5d6bedSChris Mason * search a negative error number is returned. 43097571fd0SChris Mason * 43197571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 43297571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 43397571fd0SChris Mason * possible) 43474123bd7SChris Mason */ 435e2fa7227SChris Mason int search_slot(struct ctree_root *root, struct btrfs_key *key, 43602217ed2SChris Mason struct ctree_path *p, int ins_len, int cow) 437be0e5c09SChris Mason { 438bb803951SChris Mason struct tree_buffer *b; 43902217ed2SChris Mason struct tree_buffer *cow_buf; 440eb60ceacSChris Mason struct node *c; 441be0e5c09SChris Mason int slot; 442be0e5c09SChris Mason int ret; 443be0e5c09SChris Mason int level; 4445c680ed6SChris Mason 445bb803951SChris Mason again: 446bb803951SChris Mason b = root->node; 447eb60ceacSChris Mason b->count++; 448eb60ceacSChris Mason while (b) { 4497518a238SChris Mason level = btrfs_header_level(&b->node.header); 45002217ed2SChris Mason if (cow) { 45102217ed2SChris Mason int wret; 45202217ed2SChris Mason wret = btrfs_cow_block(root, b, p->nodes[level + 1], 45302217ed2SChris Mason p->slots[level + 1], &cow_buf); 45402217ed2SChris Mason b = cow_buf; 45502217ed2SChris Mason } 45602217ed2SChris Mason BUG_ON(!cow && ins_len); 457eb60ceacSChris Mason c = &b->node; 458eb60ceacSChris Mason p->nodes[level] = b; 459aa5d6bedSChris Mason ret = check_block(p, level); 460aa5d6bedSChris Mason if (ret) 461aa5d6bedSChris Mason return -1; 462be0e5c09SChris Mason ret = bin_search(c, key, &slot); 4637518a238SChris Mason if (!btrfs_is_leaf(c)) { 464be0e5c09SChris Mason if (ret && slot > 0) 465be0e5c09SChris Mason slot -= 1; 466be0e5c09SChris Mason p->slots[level] = slot; 4677518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 4687518a238SChris Mason NODEPTRS_PER_BLOCK) { 4695c680ed6SChris Mason int sret = split_node(root, p, level); 4705c680ed6SChris Mason BUG_ON(sret > 0); 4715c680ed6SChris Mason if (sret) 4725c680ed6SChris Mason return sret; 4735c680ed6SChris Mason b = p->nodes[level]; 4745c680ed6SChris Mason c = &b->node; 4755c680ed6SChris Mason slot = p->slots[level]; 476bb803951SChris Mason } else if (ins_len < 0) { 477bb803951SChris Mason int sret = balance_level(root, p, level); 478bb803951SChris Mason if (sret) 479bb803951SChris Mason return sret; 480bb803951SChris Mason b = p->nodes[level]; 481bb803951SChris Mason if (!b) 482bb803951SChris Mason goto again; 483bb803951SChris Mason c = &b->node; 484bb803951SChris Mason slot = p->slots[level]; 4857518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 4865c680ed6SChris Mason } 4871d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 488be0e5c09SChris Mason } else { 4895c680ed6SChris Mason struct leaf *l = (struct leaf *)c; 490be0e5c09SChris Mason p->slots[level] = slot; 4915de08d7dSChris Mason if (ins_len > 0 && leaf_free_space(l) < 4920783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 4935c680ed6SChris Mason int sret = split_leaf(root, p, ins_len); 4945c680ed6SChris Mason BUG_ON(sret > 0); 4955c680ed6SChris Mason if (sret) 4965c680ed6SChris Mason return sret; 4975c680ed6SChris Mason } 498bb803951SChris Mason BUG_ON(root->node->count == 1); 499be0e5c09SChris Mason return ret; 500be0e5c09SChris Mason } 501be0e5c09SChris Mason } 502bb803951SChris Mason BUG_ON(root->node->count == 1); 503aa5d6bedSChris Mason return 1; 504be0e5c09SChris Mason } 505be0e5c09SChris Mason 50674123bd7SChris Mason /* 50774123bd7SChris Mason * adjust the pointers going up the tree, starting at level 50874123bd7SChris Mason * making sure the right key of each node is points to 'key'. 50974123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 51074123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 51174123bd7SChris Mason * higher levels 512aa5d6bedSChris Mason * 513aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 514aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 51574123bd7SChris Mason */ 516aa5d6bedSChris Mason static int fixup_low_keys(struct ctree_root *root, 517e2fa7227SChris Mason struct ctree_path *path, struct btrfs_disk_key *key, 518be0e5c09SChris Mason int level) 519be0e5c09SChris Mason { 520be0e5c09SChris Mason int i; 521aa5d6bedSChris Mason int ret = 0; 522be0e5c09SChris Mason for (i = level; i < MAX_LEVEL; i++) { 523eb60ceacSChris Mason struct node *t; 524be0e5c09SChris Mason int tslot = path->slots[i]; 525eb60ceacSChris Mason if (!path->nodes[i]) 526be0e5c09SChris Mason break; 527eb60ceacSChris Mason t = &path->nodes[i]->node; 528be0e5c09SChris Mason memcpy(t->keys + tslot, key, sizeof(*key)); 52902217ed2SChris Mason BUG_ON(list_empty(&path->nodes[i]->dirty)); 530be0e5c09SChris Mason if (tslot != 0) 531be0e5c09SChris Mason break; 532be0e5c09SChris Mason } 533aa5d6bedSChris Mason return ret; 534be0e5c09SChris Mason } 535be0e5c09SChris Mason 53674123bd7SChris Mason /* 53774123bd7SChris Mason * try to push data from one node into the next node left in the 53879f95c82SChris Mason * tree. 539aa5d6bedSChris Mason * 540aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 541aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 54274123bd7SChris Mason */ 543bb803951SChris Mason static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf, 544bb803951SChris Mason struct tree_buffer *src_buf) 545be0e5c09SChris Mason { 546bb803951SChris Mason struct node *src = &src_buf->node; 547bb803951SChris Mason struct node *dst = &dst_buf->node; 548be0e5c09SChris Mason int push_items = 0; 549bb803951SChris Mason int src_nritems; 550bb803951SChris Mason int dst_nritems; 551aa5d6bedSChris Mason int ret = 0; 552be0e5c09SChris Mason 5537518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5547518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 555bb803951SChris Mason push_items = NODEPTRS_PER_BLOCK - dst_nritems; 556eb60ceacSChris Mason if (push_items <= 0) { 557be0e5c09SChris Mason return 1; 558eb60ceacSChris Mason } 559be0e5c09SChris Mason 560be0e5c09SChris Mason if (src_nritems < push_items) 561be0e5c09SChris Mason push_items = src_nritems; 56279f95c82SChris Mason 563bb803951SChris Mason memcpy(dst->keys + dst_nritems, src->keys, 564e2fa7227SChris Mason push_items * sizeof(struct btrfs_disk_key)); 565bb803951SChris Mason memcpy(dst->blockptrs + dst_nritems, src->blockptrs, 566be0e5c09SChris Mason push_items * sizeof(u64)); 567bb803951SChris Mason if (push_items < src_nritems) { 568bb803951SChris Mason memmove(src->keys, src->keys + push_items, 569e2fa7227SChris Mason (src_nritems - push_items) * 570e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 571bb803951SChris Mason memmove(src->blockptrs, src->blockptrs + push_items, 572bb803951SChris Mason (src_nritems - push_items) * sizeof(u64)); 573bb803951SChris Mason } 5747518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 5757518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 57602217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 57702217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 578bb803951SChris Mason return ret; 579be0e5c09SChris Mason } 580be0e5c09SChris Mason 58197571fd0SChris Mason /* 58279f95c82SChris Mason * try to push data from one node into the next node right in the 58379f95c82SChris Mason * tree. 58479f95c82SChris Mason * 58579f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 58679f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 58779f95c82SChris Mason * 58879f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 58979f95c82SChris Mason */ 59079f95c82SChris Mason static int balance_node_right(struct ctree_root *root, 59179f95c82SChris Mason struct tree_buffer *dst_buf, 59279f95c82SChris Mason struct tree_buffer *src_buf) 59379f95c82SChris Mason { 59479f95c82SChris Mason struct node *src = &src_buf->node; 59579f95c82SChris Mason struct node *dst = &dst_buf->node; 59679f95c82SChris Mason int push_items = 0; 59779f95c82SChris Mason int max_push; 59879f95c82SChris Mason int src_nritems; 59979f95c82SChris Mason int dst_nritems; 60079f95c82SChris Mason int ret = 0; 60179f95c82SChris Mason 6027518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6037518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 60479f95c82SChris Mason push_items = NODEPTRS_PER_BLOCK - dst_nritems; 60579f95c82SChris Mason if (push_items <= 0) { 60679f95c82SChris Mason return 1; 60779f95c82SChris Mason } 60879f95c82SChris Mason 60979f95c82SChris Mason max_push = src_nritems / 2 + 1; 61079f95c82SChris Mason /* don't try to empty the node */ 61179f95c82SChris Mason if (max_push > src_nritems) 61279f95c82SChris Mason return 1; 61379f95c82SChris Mason if (max_push < push_items) 61479f95c82SChris Mason push_items = max_push; 61579f95c82SChris Mason 61679f95c82SChris Mason memmove(dst->keys + push_items, dst->keys, 617e2fa7227SChris Mason dst_nritems * sizeof(struct btrfs_disk_key)); 61879f95c82SChris Mason memmove(dst->blockptrs + push_items, dst->blockptrs, 61979f95c82SChris Mason dst_nritems * sizeof(u64)); 62079f95c82SChris Mason memcpy(dst->keys, src->keys + src_nritems - push_items, 621e2fa7227SChris Mason push_items * sizeof(struct btrfs_disk_key)); 62279f95c82SChris Mason memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, 62379f95c82SChris Mason push_items * sizeof(u64)); 62479f95c82SChris Mason 6257518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6267518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 62779f95c82SChris Mason 62802217ed2SChris Mason BUG_ON(list_empty(&src_buf->dirty)); 62902217ed2SChris Mason BUG_ON(list_empty(&dst_buf->dirty)); 63079f95c82SChris Mason return ret; 63179f95c82SChris Mason } 63279f95c82SChris Mason 63379f95c82SChris Mason /* 63497571fd0SChris Mason * helper function to insert a new root level in the tree. 63597571fd0SChris Mason * A new node is allocated, and a single item is inserted to 63697571fd0SChris Mason * point to the existing root 637aa5d6bedSChris Mason * 638aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 63997571fd0SChris Mason */ 6405de08d7dSChris Mason static int insert_new_root(struct ctree_root *root, 6415de08d7dSChris Mason struct ctree_path *path, int level) 64274123bd7SChris Mason { 64374123bd7SChris Mason struct tree_buffer *t; 6445c680ed6SChris Mason struct node *lower; 6455c680ed6SChris Mason struct node *c; 646e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 6475c680ed6SChris Mason 6485c680ed6SChris Mason BUG_ON(path->nodes[level]); 6495c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 6505c680ed6SChris Mason 65174123bd7SChris Mason t = alloc_free_block(root); 65274123bd7SChris Mason c = &t->node; 65374123bd7SChris Mason memset(c, 0, sizeof(c)); 6547518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 6557518a238SChris Mason btrfs_set_header_level(&c->header, level); 6567518a238SChris Mason btrfs_set_header_blocknr(&c->header, t->blocknr); 6577518a238SChris Mason btrfs_set_header_parentid(&c->header, 6587518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 65974123bd7SChris Mason lower = &path->nodes[level-1]->node; 6607518a238SChris Mason if (btrfs_is_leaf(lower)) 66174123bd7SChris Mason lower_key = &((struct leaf *)lower)->items[0].key; 66274123bd7SChris Mason else 66374123bd7SChris Mason lower_key = lower->keys; 664e2fa7227SChris Mason memcpy(c->keys, lower_key, sizeof(struct btrfs_disk_key)); 6651d4f8a0cSChris Mason btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->blocknr); 666cfaa7295SChris Mason /* the super has an extra ref to root->node */ 66774123bd7SChris Mason tree_block_release(root, root->node); 66874123bd7SChris Mason root->node = t; 66974123bd7SChris Mason t->count++; 67074123bd7SChris Mason path->nodes[level] = t; 67174123bd7SChris Mason path->slots[level] = 0; 67274123bd7SChris Mason return 0; 67374123bd7SChris Mason } 6745c680ed6SChris Mason 6755c680ed6SChris Mason /* 6765c680ed6SChris Mason * worker function to insert a single pointer in a node. 6775c680ed6SChris Mason * the node should have enough room for the pointer already 67897571fd0SChris Mason * 6795c680ed6SChris Mason * slot and level indicate where you want the key to go, and 6805c680ed6SChris Mason * blocknr is the block the key points to. 681aa5d6bedSChris Mason * 682aa5d6bedSChris Mason * returns zero on success and < 0 on any error 6835c680ed6SChris Mason */ 684aa5d6bedSChris Mason static int insert_ptr(struct ctree_root *root, 685e2fa7227SChris Mason struct ctree_path *path, struct btrfs_disk_key *key, 6865c680ed6SChris Mason u64 blocknr, int slot, int level) 6875c680ed6SChris Mason { 6885c680ed6SChris Mason struct node *lower; 6895c680ed6SChris Mason int nritems; 6905c680ed6SChris Mason 6915c680ed6SChris Mason BUG_ON(!path->nodes[level]); 69274123bd7SChris Mason lower = &path->nodes[level]->node; 6937518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 69474123bd7SChris Mason if (slot > nritems) 69574123bd7SChris Mason BUG(); 69674123bd7SChris Mason if (nritems == NODEPTRS_PER_BLOCK) 69774123bd7SChris Mason BUG(); 69874123bd7SChris Mason if (slot != nritems) { 69974123bd7SChris Mason memmove(lower->keys + slot + 1, lower->keys + slot, 700e2fa7227SChris Mason (nritems - slot) * sizeof(struct btrfs_disk_key)); 70174123bd7SChris Mason memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, 70274123bd7SChris Mason (nritems - slot) * sizeof(u64)); 70374123bd7SChris Mason } 704e2fa7227SChris Mason memcpy(lower->keys + slot, key, sizeof(struct btrfs_disk_key)); 7051d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 7067518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 70774123bd7SChris Mason if (lower->keys[1].objectid == 0) 70874123bd7SChris Mason BUG(); 70902217ed2SChris Mason BUG_ON(list_empty(&path->nodes[level]->dirty)); 71074123bd7SChris Mason return 0; 71174123bd7SChris Mason } 71274123bd7SChris Mason 71397571fd0SChris Mason /* 71497571fd0SChris Mason * split the node at the specified level in path in two. 71597571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 71697571fd0SChris Mason * 71797571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 71897571fd0SChris Mason * left and right, if either one works, it returns right away. 719aa5d6bedSChris Mason * 720aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 72197571fd0SChris Mason */ 722aa5d6bedSChris Mason static int split_node(struct ctree_root *root, struct ctree_path *path, 723aa5d6bedSChris Mason int level) 724be0e5c09SChris Mason { 7255c680ed6SChris Mason struct tree_buffer *t; 7265c680ed6SChris Mason struct node *c; 7275c680ed6SChris Mason struct tree_buffer *split_buffer; 7285c680ed6SChris Mason struct node *split; 729be0e5c09SChris Mason int mid; 7305c680ed6SChris Mason int ret; 731aa5d6bedSChris Mason int wret; 7327518a238SChris Mason u32 c_nritems; 733be0e5c09SChris Mason 7345c680ed6SChris Mason t = path->nodes[level]; 735eb60ceacSChris Mason c = &t->node; 7365c680ed6SChris Mason if (t == root->node) { 7375c680ed6SChris Mason /* trying to split the root, lets make a new one */ 7385c680ed6SChris Mason ret = insert_new_root(root, path, level + 1); 7395c680ed6SChris Mason if (ret) 7405c680ed6SChris Mason return ret; 7415c680ed6SChris Mason } 7427518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 7435c680ed6SChris Mason split_buffer = alloc_free_block(root); 7445c680ed6SChris Mason split = &split_buffer->node; 7457518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 7467518a238SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->blocknr); 7477518a238SChris Mason btrfs_set_header_parentid(&split->header, 7487518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 7497518a238SChris Mason mid = (c_nritems + 1) / 2; 7505c680ed6SChris Mason memcpy(split->keys, c->keys + mid, 751e2fa7227SChris Mason (c_nritems - mid) * sizeof(struct btrfs_disk_key)); 7525c680ed6SChris Mason memcpy(split->blockptrs, c->blockptrs + mid, 7537518a238SChris Mason (c_nritems - mid) * sizeof(u64)); 7547518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7557518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 756aa5d6bedSChris Mason ret = 0; 757aa5d6bedSChris Mason 75802217ed2SChris Mason BUG_ON(list_empty(&t->dirty)); 759aa5d6bedSChris Mason wret = insert_ptr(root, path, split->keys, split_buffer->blocknr, 7605c680ed6SChris Mason path->slots[level + 1] + 1, level + 1); 761aa5d6bedSChris Mason if (wret) 762aa5d6bedSChris Mason ret = wret; 763aa5d6bedSChris Mason 7645de08d7dSChris Mason if (path->slots[level] >= mid) { 7655c680ed6SChris Mason path->slots[level] -= mid; 7665c680ed6SChris Mason tree_block_release(root, t); 7675c680ed6SChris Mason path->nodes[level] = split_buffer; 7685c680ed6SChris Mason path->slots[level + 1] += 1; 769eb60ceacSChris Mason } else { 7705c680ed6SChris Mason tree_block_release(root, split_buffer); 771be0e5c09SChris Mason } 772aa5d6bedSChris Mason return ret; 773be0e5c09SChris Mason } 774be0e5c09SChris Mason 77574123bd7SChris Mason /* 77674123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 77774123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 77874123bd7SChris Mason * space used both by the item structs and the item data 77974123bd7SChris Mason */ 780aa5d6bedSChris Mason static int leaf_space_used(struct leaf *l, int start, int nr) 781be0e5c09SChris Mason { 782be0e5c09SChris Mason int data_len; 783be0e5c09SChris Mason int end = start + nr - 1; 784be0e5c09SChris Mason 785be0e5c09SChris Mason if (!nr) 786be0e5c09SChris Mason return 0; 7870783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 7880783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 7890783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 790be0e5c09SChris Mason return data_len; 791be0e5c09SChris Mason } 792be0e5c09SChris Mason 79374123bd7SChris Mason /* 79400ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 79500ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 796aa5d6bedSChris Mason * 797aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 798aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 79900ec4c51SChris Mason */ 800aa5d6bedSChris Mason static int push_leaf_right(struct ctree_root *root, struct ctree_path *path, 80100ec4c51SChris Mason int data_size) 80200ec4c51SChris Mason { 80300ec4c51SChris Mason struct tree_buffer *left_buf = path->nodes[0]; 80400ec4c51SChris Mason struct leaf *left = &left_buf->leaf; 80500ec4c51SChris Mason struct leaf *right; 80600ec4c51SChris Mason struct tree_buffer *right_buf; 80700ec4c51SChris Mason struct tree_buffer *upper; 80800ec4c51SChris Mason int slot; 80900ec4c51SChris Mason int i; 81000ec4c51SChris Mason int free_space; 81100ec4c51SChris Mason int push_space = 0; 81200ec4c51SChris Mason int push_items = 0; 8130783fcfcSChris Mason struct btrfs_item *item; 8147518a238SChris Mason u32 left_nritems; 8157518a238SChris Mason u32 right_nritems; 81600ec4c51SChris Mason 81700ec4c51SChris Mason slot = path->slots[1]; 81800ec4c51SChris Mason if (!path->nodes[1]) { 81900ec4c51SChris Mason return 1; 82000ec4c51SChris Mason } 82100ec4c51SChris Mason upper = path->nodes[1]; 8227518a238SChris Mason if (slot >= btrfs_header_nritems(&upper->node.header) - 1) { 82300ec4c51SChris Mason return 1; 82400ec4c51SChris Mason } 8251d4f8a0cSChris Mason right_buf = read_tree_block(root, btrfs_node_blockptr(&upper->node, 8261d4f8a0cSChris Mason slot + 1)); 82700ec4c51SChris Mason right = &right_buf->leaf; 82800ec4c51SChris Mason free_space = leaf_free_space(right); 8290783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 83000ec4c51SChris Mason tree_block_release(root, right_buf); 83100ec4c51SChris Mason return 1; 83200ec4c51SChris Mason } 83302217ed2SChris Mason /* cow and double check */ 83402217ed2SChris Mason btrfs_cow_block(root, right_buf, upper, slot + 1, &right_buf); 83502217ed2SChris Mason right = &right_buf->leaf; 83602217ed2SChris Mason free_space = leaf_free_space(right); 8370783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 83802217ed2SChris Mason tree_block_release(root, right_buf); 83902217ed2SChris Mason return 1; 84002217ed2SChris Mason } 84102217ed2SChris Mason 8427518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8437518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 84400ec4c51SChris Mason item = left->items + i; 84500ec4c51SChris Mason if (path->slots[0] == i) 84600ec4c51SChris Mason push_space += data_size + sizeof(*item); 8470783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8480783fcfcSChris Mason free_space) 84900ec4c51SChris Mason break; 85000ec4c51SChris Mason push_items++; 8510783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 85200ec4c51SChris Mason } 85300ec4c51SChris Mason if (push_items == 0) { 85400ec4c51SChris Mason tree_block_release(root, right_buf); 85500ec4c51SChris Mason return 1; 85600ec4c51SChris Mason } 8577518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 85800ec4c51SChris Mason /* push left to right */ 8590783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 86000ec4c51SChris Mason push_space -= leaf_data_end(left); 86100ec4c51SChris Mason /* make room in the right data area */ 86200ec4c51SChris Mason memmove(right->data + leaf_data_end(right) - push_space, 86300ec4c51SChris Mason right->data + leaf_data_end(right), 86400ec4c51SChris Mason LEAF_DATA_SIZE - leaf_data_end(right)); 86500ec4c51SChris Mason /* copy from the left data area */ 86600ec4c51SChris Mason memcpy(right->data + LEAF_DATA_SIZE - push_space, 86700ec4c51SChris Mason left->data + leaf_data_end(left), 86800ec4c51SChris Mason push_space); 86900ec4c51SChris Mason memmove(right->items + push_items, right->items, 8700783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 87100ec4c51SChris Mason /* copy the items from left to right */ 8727518a238SChris Mason memcpy(right->items, left->items + left_nritems - push_items, 8730783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 87400ec4c51SChris Mason 87500ec4c51SChris Mason /* update the item pointers */ 8767518a238SChris Mason right_nritems += push_items; 8777518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 87800ec4c51SChris Mason push_space = LEAF_DATA_SIZE; 8797518a238SChris Mason for (i = 0; i < right_nritems; i++) { 8800783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 8810783fcfcSChris Mason btrfs_item_size(right->items + i)); 8820783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 88300ec4c51SChris Mason } 8847518a238SChris Mason left_nritems -= push_items; 8857518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 88600ec4c51SChris Mason 88702217ed2SChris Mason BUG_ON(list_empty(&left_buf->dirty)); 88802217ed2SChris Mason BUG_ON(list_empty(&right_buf->dirty)); 88900ec4c51SChris Mason memcpy(upper->node.keys + slot + 1, 890e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 89102217ed2SChris Mason BUG_ON(list_empty(&upper->dirty)); 89202217ed2SChris Mason 89300ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 8947518a238SChris Mason if (path->slots[0] >= left_nritems) { 8957518a238SChris Mason path->slots[0] -= left_nritems; 89600ec4c51SChris Mason tree_block_release(root, path->nodes[0]); 89700ec4c51SChris Mason path->nodes[0] = right_buf; 89800ec4c51SChris Mason path->slots[1] += 1; 89900ec4c51SChris Mason } else { 90000ec4c51SChris Mason tree_block_release(root, right_buf); 90100ec4c51SChris Mason } 90200ec4c51SChris Mason return 0; 90300ec4c51SChris Mason } 90400ec4c51SChris Mason /* 90574123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 90674123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 90774123bd7SChris Mason */ 908aa5d6bedSChris Mason static int push_leaf_left(struct ctree_root *root, struct ctree_path *path, 909be0e5c09SChris Mason int data_size) 910be0e5c09SChris Mason { 911eb60ceacSChris Mason struct tree_buffer *right_buf = path->nodes[0]; 912eb60ceacSChris Mason struct leaf *right = &right_buf->leaf; 913eb60ceacSChris Mason struct tree_buffer *t; 914be0e5c09SChris Mason struct leaf *left; 915be0e5c09SChris Mason int slot; 916be0e5c09SChris Mason int i; 917be0e5c09SChris Mason int free_space; 918be0e5c09SChris Mason int push_space = 0; 919be0e5c09SChris Mason int push_items = 0; 9200783fcfcSChris Mason struct btrfs_item *item; 9217518a238SChris Mason u32 old_left_nritems; 922aa5d6bedSChris Mason int ret = 0; 923aa5d6bedSChris Mason int wret; 924be0e5c09SChris Mason 925be0e5c09SChris Mason slot = path->slots[1]; 926be0e5c09SChris Mason if (slot == 0) { 927be0e5c09SChris Mason return 1; 928be0e5c09SChris Mason } 929be0e5c09SChris Mason if (!path->nodes[1]) { 930be0e5c09SChris Mason return 1; 931be0e5c09SChris Mason } 9321d4f8a0cSChris Mason t = read_tree_block(root, btrfs_node_blockptr(&path->nodes[1]->node, 9331d4f8a0cSChris Mason slot - 1)); 934eb60ceacSChris Mason left = &t->leaf; 935be0e5c09SChris Mason free_space = leaf_free_space(left); 9360783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 937eb60ceacSChris Mason tree_block_release(root, t); 938be0e5c09SChris Mason return 1; 939be0e5c09SChris Mason } 94002217ed2SChris Mason 94102217ed2SChris Mason /* cow and double check */ 94202217ed2SChris Mason btrfs_cow_block(root, t, path->nodes[1], slot - 1, &t); 94302217ed2SChris Mason left = &t->leaf; 94402217ed2SChris Mason free_space = leaf_free_space(left); 9450783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 94602217ed2SChris Mason tree_block_release(root, t); 94702217ed2SChris Mason return 1; 94802217ed2SChris Mason } 94902217ed2SChris Mason 9507518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 951be0e5c09SChris Mason item = right->items + i; 952be0e5c09SChris Mason if (path->slots[0] == i) 953be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9540783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 9550783fcfcSChris Mason free_space) 956be0e5c09SChris Mason break; 957be0e5c09SChris Mason push_items++; 9580783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 959be0e5c09SChris Mason } 960be0e5c09SChris Mason if (push_items == 0) { 961eb60ceacSChris Mason tree_block_release(root, t); 962be0e5c09SChris Mason return 1; 963be0e5c09SChris Mason } 964be0e5c09SChris Mason /* push data from right to left */ 9657518a238SChris Mason memcpy(left->items + btrfs_header_nritems(&left->header), 9660783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 9670783fcfcSChris Mason push_space = LEAF_DATA_SIZE - 9680783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 969be0e5c09SChris Mason memcpy(left->data + leaf_data_end(left) - push_space, 9700783fcfcSChris Mason right->data + btrfs_item_offset(right->items + push_items - 1), 971be0e5c09SChris Mason push_space); 9727518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 973eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 974eb60ceacSChris Mason 975be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 9760783fcfcSChris Mason u16 ioff = btrfs_item_offset(left->items + i); 9770783fcfcSChris Mason btrfs_set_item_offset(left->items + i, ioff - (LEAF_DATA_SIZE - 9780783fcfcSChris Mason btrfs_item_offset(left->items + 9790783fcfcSChris Mason old_left_nritems - 1))); 980be0e5c09SChris Mason } 9817518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 982be0e5c09SChris Mason 983be0e5c09SChris Mason /* fixup right node */ 9840783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 9850783fcfcSChris Mason leaf_data_end(right); 986be0e5c09SChris Mason memmove(right->data + LEAF_DATA_SIZE - push_space, right->data + 987be0e5c09SChris Mason leaf_data_end(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); 994be0e5c09SChris Mason push_space = LEAF_DATA_SIZE; 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 1005aa5d6bedSChris Mason wret = fixup_low_keys(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; 1012eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 1013eb60ceacSChris Mason path->nodes[0] = t; 1014be0e5c09SChris Mason path->slots[1] -= 1; 1015be0e5c09SChris Mason } else { 1016eb60ceacSChris Mason tree_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 */ 1029aa5d6bedSChris Mason static int split_leaf(struct ctree_root *root, struct ctree_path *path, 1030aa5d6bedSChris Mason int data_size) 1031be0e5c09SChris Mason { 1032aa5d6bedSChris Mason struct tree_buffer *l_buf; 1033aa5d6bedSChris Mason struct leaf *l; 10347518a238SChris Mason u32 nritems; 1035eb60ceacSChris Mason int mid; 1036eb60ceacSChris Mason int slot; 1037be0e5c09SChris Mason struct leaf *right; 1038eb60ceacSChris Mason struct tree_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 1046eb60ceacSChris Mason l_buf = path->nodes[0]; 1047eb60ceacSChris Mason l = &l_buf->leaf; 1048aa5d6bedSChris Mason 1049aa5d6bedSChris Mason /* did the pushes work? */ 10500783fcfcSChris Mason if (leaf_free_space(l) >= sizeof(struct btrfs_item) + data_size) 1051be0e5c09SChris Mason return 0; 1052aa5d6bedSChris Mason 10535c680ed6SChris Mason if (!path->nodes[1]) { 10545c680ed6SChris Mason ret = insert_new_root(root, path, 1); 10555c680ed6SChris Mason if (ret) 10565c680ed6SChris Mason return ret; 10575c680ed6SChris Mason } 1058eb60ceacSChris Mason slot = path->slots[0]; 10597518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1060eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1061eb60ceacSChris Mason right_buffer = alloc_free_block(root); 1062eb60ceacSChris Mason BUG_ON(!right_buffer); 1063eb60ceacSChris Mason BUG_ON(mid == nritems); 1064eb60ceacSChris Mason right = &right_buffer->leaf; 1065be0e5c09SChris Mason memset(right, 0, sizeof(*right)); 1066be0e5c09SChris Mason if (mid <= slot) { 106797571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1068be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1069be0e5c09SChris Mason LEAF_DATA_SIZE) 1070be0e5c09SChris Mason BUG(); 1071be0e5c09SChris Mason } else { 107297571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1073be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1074be0e5c09SChris Mason LEAF_DATA_SIZE) 1075be0e5c09SChris Mason BUG(); 1076be0e5c09SChris Mason } 10777518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 10787518a238SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->blocknr); 10797518a238SChris Mason btrfs_set_header_level(&right->header, 0); 10807518a238SChris Mason btrfs_set_header_parentid(&right->header, 10817518a238SChris Mason btrfs_header_parentid(&root->node->node.header)); 10820783fcfcSChris Mason data_copy_size = btrfs_item_end(l->items + mid) - leaf_data_end(l); 1083be0e5c09SChris Mason memcpy(right->items, l->items + mid, 10840783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1085be0e5c09SChris Mason memcpy(right->data + LEAF_DATA_SIZE - data_copy_size, 1086be0e5c09SChris Mason l->data + leaf_data_end(l), data_copy_size); 10870783fcfcSChris Mason rt_data_off = LEAF_DATA_SIZE - btrfs_item_end(l->items + mid); 108874123bd7SChris Mason 10890783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 10900783fcfcSChris Mason u16 ioff = btrfs_item_offset(right->items + i); 10910783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 10920783fcfcSChris Mason } 109374123bd7SChris Mason 10947518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1095aa5d6bedSChris Mason ret = 0; 1096aa5d6bedSChris Mason wret = insert_ptr(root, path, &right->items[0].key, 10975c680ed6SChris Mason right_buffer->blocknr, path->slots[1] + 1, 1); 1098aa5d6bedSChris Mason if (wret) 1099aa5d6bedSChris Mason ret = wret; 110002217ed2SChris Mason BUG_ON(list_empty(&right_buffer->dirty)); 110102217ed2SChris Mason BUG_ON(list_empty(&l_buf->dirty)); 1102eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1103be0e5c09SChris Mason if (mid <= slot) { 1104eb60ceacSChris Mason tree_block_release(root, path->nodes[0]); 1105eb60ceacSChris Mason path->nodes[0] = right_buffer; 1106be0e5c09SChris Mason path->slots[0] -= mid; 1107be0e5c09SChris Mason path->slots[1] += 1; 1108eb60ceacSChris Mason } else 1109eb60ceacSChris Mason tree_block_release(root, right_buffer); 1110eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1111be0e5c09SChris Mason return ret; 1112be0e5c09SChris Mason } 1113be0e5c09SChris Mason 111474123bd7SChris Mason /* 111574123bd7SChris Mason * Given a key and some data, insert an item into the tree. 111674123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 111774123bd7SChris Mason */ 1118e2fa7227SChris Mason int insert_item(struct ctree_root *root, struct btrfs_key *cpu_key, 1119be0e5c09SChris Mason void *data, int data_size) 1120be0e5c09SChris Mason { 1121aa5d6bedSChris Mason int ret = 0; 1122be0e5c09SChris Mason int slot; 1123eb60ceacSChris Mason int slot_orig; 1124be0e5c09SChris Mason struct leaf *leaf; 1125eb60ceacSChris Mason struct tree_buffer *leaf_buf; 11267518a238SChris Mason u32 nritems; 1127be0e5c09SChris Mason unsigned int data_end; 1128be0e5c09SChris Mason struct ctree_path path; 1129e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1130e2fa7227SChris Mason 1131e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1132be0e5c09SChris Mason 113374123bd7SChris Mason /* create a root if there isn't one */ 11345c680ed6SChris Mason if (!root->node) 1135cfaa7295SChris Mason BUG(); 1136be0e5c09SChris Mason init_path(&path); 1137e2fa7227SChris Mason ret = search_slot(root, cpu_key, &path, data_size, 1); 1138eb60ceacSChris Mason if (ret == 0) { 1139eb60ceacSChris Mason release_path(root, &path); 1140f0930a37SChris Mason return -EEXIST; 1141aa5d6bedSChris Mason } 1142ed2ff2cbSChris Mason if (ret < 0) 1143ed2ff2cbSChris Mason goto out; 1144be0e5c09SChris Mason 1145eb60ceacSChris Mason slot_orig = path.slots[0]; 1146eb60ceacSChris Mason leaf_buf = path.nodes[0]; 1147eb60ceacSChris Mason leaf = &leaf_buf->leaf; 114874123bd7SChris Mason 11497518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1150be0e5c09SChris Mason data_end = leaf_data_end(leaf); 1151eb60ceacSChris Mason 11520783fcfcSChris Mason if (leaf_free_space(leaf) < sizeof(struct btrfs_item) + data_size) 1153be0e5c09SChris Mason BUG(); 1154be0e5c09SChris Mason 1155be0e5c09SChris Mason slot = path.slots[0]; 1156eb60ceacSChris Mason BUG_ON(slot < 0); 1157be0e5c09SChris Mason if (slot != nritems) { 1158be0e5c09SChris Mason int i; 11590783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1160be0e5c09SChris Mason 1161be0e5c09SChris Mason /* 1162be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1163be0e5c09SChris Mason */ 1164be0e5c09SChris Mason /* first correct the data pointers */ 11650783fcfcSChris Mason for (i = slot; i < nritems; i++) { 11660783fcfcSChris Mason u16 ioff = btrfs_item_offset(leaf->items + i); 11670783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 11680783fcfcSChris Mason ioff - data_size); 11690783fcfcSChris Mason } 1170be0e5c09SChris Mason 1171be0e5c09SChris Mason /* shift the items */ 1172be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 11730783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1174be0e5c09SChris Mason 1175be0e5c09SChris Mason /* shift the data */ 1176be0e5c09SChris Mason memmove(leaf->data + data_end - data_size, leaf->data + 1177be0e5c09SChris Mason data_end, old_data - data_end); 1178be0e5c09SChris Mason data_end = old_data; 1179be0e5c09SChris Mason } 118074123bd7SChris Mason /* copy the new data in */ 1181e2fa7227SChris Mason memcpy(&leaf->items[slot].key, &disk_key, 1182e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 11830783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 11840783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 1185be0e5c09SChris Mason memcpy(leaf->data + data_end - data_size, data, data_size); 11867518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1187aa5d6bedSChris Mason 1188aa5d6bedSChris Mason ret = 0; 11898e19f2cdSChris Mason if (slot == 0) 1190e2fa7227SChris Mason ret = fixup_low_keys(root, &path, &disk_key, 1); 1191aa5d6bedSChris Mason 119202217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1193be0e5c09SChris Mason if (leaf_free_space(leaf) < 0) 1194be0e5c09SChris Mason BUG(); 1195bb803951SChris Mason check_leaf(&path, 0); 1196ed2ff2cbSChris Mason out: 1197eb60ceacSChris Mason release_path(root, &path); 1198aa5d6bedSChris Mason return ret; 1199be0e5c09SChris Mason } 1200be0e5c09SChris Mason 120174123bd7SChris Mason /* 12025de08d7dSChris Mason * delete the pointer from a given node. 120374123bd7SChris Mason * 120474123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 120574123bd7SChris Mason * continuing all the way the root if required. The root is converted into 120674123bd7SChris Mason * a leaf if all the nodes are emptied. 120774123bd7SChris Mason */ 1208bb803951SChris Mason static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level, 1209bb803951SChris Mason int slot) 1210be0e5c09SChris Mason { 1211be0e5c09SChris Mason struct node *node; 1212bb803951SChris Mason struct tree_buffer *parent = path->nodes[level]; 12137518a238SChris Mason u32 nritems; 1214aa5d6bedSChris Mason int ret = 0; 1215bb803951SChris Mason int wret; 1216be0e5c09SChris Mason 1217bb803951SChris Mason node = &parent->node; 12187518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1219be0e5c09SChris Mason if (slot != nritems -1) { 1220be0e5c09SChris Mason memmove(node->keys + slot, node->keys + slot + 1, 1221e2fa7227SChris Mason sizeof(struct btrfs_disk_key) * (nritems - slot - 1)); 1222be0e5c09SChris Mason memmove(node->blockptrs + slot, 1223be0e5c09SChris Mason node->blockptrs + slot + 1, 1224be0e5c09SChris Mason sizeof(u64) * (nritems - slot - 1)); 1225be0e5c09SChris Mason } 12267518a238SChris Mason nritems--; 12277518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 12287518a238SChris Mason if (nritems == 0 && parent == root->node) { 12297518a238SChris Mason BUG_ON(btrfs_header_level(&root->node->node.header) != 1); 1230eb60ceacSChris Mason /* just turn the root into a leaf and break */ 12317518a238SChris Mason btrfs_set_header_level(&root->node->node.header, 0); 1232bb803951SChris Mason } else if (slot == 0) { 1233bb803951SChris Mason wret = fixup_low_keys(root, path, node->keys, level + 1); 12340f70abe2SChris Mason if (wret) 12350f70abe2SChris Mason ret = wret; 1236be0e5c09SChris Mason } 123702217ed2SChris Mason BUG_ON(list_empty(&parent->dirty)); 1238aa5d6bedSChris Mason return ret; 1239be0e5c09SChris Mason } 1240be0e5c09SChris Mason 124174123bd7SChris Mason /* 124274123bd7SChris Mason * delete the item at the leaf level in path. If that empties 124374123bd7SChris Mason * the leaf, remove it from the tree 124474123bd7SChris Mason */ 12454920c9acSChris Mason int del_item(struct ctree_root *root, struct ctree_path *path) 1246be0e5c09SChris Mason { 1247be0e5c09SChris Mason int slot; 1248be0e5c09SChris Mason struct leaf *leaf; 1249eb60ceacSChris Mason struct tree_buffer *leaf_buf; 1250be0e5c09SChris Mason int doff; 1251be0e5c09SChris Mason int dsize; 1252aa5d6bedSChris Mason int ret = 0; 1253aa5d6bedSChris Mason int wret; 12547518a238SChris Mason u32 nritems; 1255be0e5c09SChris Mason 1256eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1257eb60ceacSChris Mason leaf = &leaf_buf->leaf; 12584920c9acSChris Mason slot = path->slots[0]; 12590783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 12600783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 12617518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1262be0e5c09SChris Mason 12637518a238SChris Mason if (slot != nritems - 1) { 1264be0e5c09SChris Mason int i; 1265be0e5c09SChris Mason int data_end = leaf_data_end(leaf); 1266be0e5c09SChris Mason memmove(leaf->data + data_end + dsize, 1267be0e5c09SChris Mason leaf->data + data_end, 1268be0e5c09SChris Mason doff - data_end); 12690783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 12700783fcfcSChris Mason u16 ioff = btrfs_item_offset(leaf->items + i); 12710783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 12720783fcfcSChris Mason } 1273be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 12740783fcfcSChris Mason sizeof(struct btrfs_item) * 12757518a238SChris Mason (nritems - slot - 1)); 1276be0e5c09SChris Mason } 12777518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 12787518a238SChris Mason nritems--; 127974123bd7SChris Mason /* delete the leaf if we've emptied it */ 12807518a238SChris Mason if (nritems == 0) { 1281eb60ceacSChris Mason if (leaf_buf == root->node) { 12827518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 128302217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 12849a8dd150SChris Mason } else { 1285ed2ff2cbSChris Mason clean_tree_block(root, leaf_buf); 1286bb803951SChris Mason wret = del_ptr(root, path, 1, path->slots[1]); 1287aa5d6bedSChris Mason if (wret) 1288aa5d6bedSChris Mason ret = wret; 12890f70abe2SChris Mason wret = free_extent(root, leaf_buf->blocknr, 1); 12900f70abe2SChris Mason if (wret) 12910f70abe2SChris Mason ret = wret; 12929a8dd150SChris Mason } 1293be0e5c09SChris Mason } else { 12947518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1295aa5d6bedSChris Mason if (slot == 0) { 1296aa5d6bedSChris Mason wret = fixup_low_keys(root, path, 1297aa5d6bedSChris Mason &leaf->items[0].key, 1); 1298aa5d6bedSChris Mason if (wret) 1299aa5d6bedSChris Mason ret = wret; 1300aa5d6bedSChris Mason } 130102217ed2SChris Mason BUG_ON(list_empty(&leaf_buf->dirty)); 1302aa5d6bedSChris Mason 130374123bd7SChris Mason /* delete the leaf if it is mostly empty */ 13045de08d7dSChris Mason if (used < LEAF_DATA_SIZE / 3) { 1305be0e5c09SChris Mason /* push_leaf_left fixes the path. 1306be0e5c09SChris Mason * make sure the path still points to our leaf 1307be0e5c09SChris Mason * for possible call to del_ptr below 1308be0e5c09SChris Mason */ 13094920c9acSChris Mason slot = path->slots[1]; 1310eb60ceacSChris Mason leaf_buf->count++; 1311aa5d6bedSChris Mason wret = push_leaf_left(root, path, 1); 1312aa5d6bedSChris Mason if (wret < 0) 1313aa5d6bedSChris Mason ret = wret; 1314f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 13157518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1316aa5d6bedSChris Mason wret = push_leaf_right(root, path, 1); 1317aa5d6bedSChris Mason if (wret < 0) 1318aa5d6bedSChris Mason ret = wret; 1319aa5d6bedSChris Mason } 13207518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 13215de08d7dSChris Mason u64 blocknr = leaf_buf->blocknr; 1322ed2ff2cbSChris Mason clean_tree_block(root, leaf_buf); 1323bb803951SChris Mason wret = del_ptr(root, path, 1, slot); 1324aa5d6bedSChris Mason if (wret) 1325aa5d6bedSChris Mason ret = wret; 13265de08d7dSChris Mason tree_block_release(root, leaf_buf); 13270f70abe2SChris Mason wret = free_extent(root, blocknr, 1); 13280f70abe2SChris Mason if (wret) 13290f70abe2SChris Mason ret = wret; 13305de08d7dSChris Mason } else { 1331eb60ceacSChris Mason tree_block_release(root, leaf_buf); 1332be0e5c09SChris Mason } 1333be0e5c09SChris Mason } 13349a8dd150SChris Mason } 1335aa5d6bedSChris Mason return ret; 13369a8dd150SChris Mason } 13379a8dd150SChris Mason 133897571fd0SChris Mason /* 133997571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 13400f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 13410f70abe2SChris Mason * returns < 0 on io errors. 134297571fd0SChris Mason */ 1343d97e63b6SChris Mason int next_leaf(struct ctree_root *root, struct ctree_path *path) 1344d97e63b6SChris Mason { 1345d97e63b6SChris Mason int slot; 1346d97e63b6SChris Mason int level = 1; 1347d97e63b6SChris Mason u64 blocknr; 1348d97e63b6SChris Mason struct tree_buffer *c; 1349cfaa7295SChris Mason struct tree_buffer *next = NULL; 1350d97e63b6SChris Mason 1351d97e63b6SChris Mason while(level < MAX_LEVEL) { 1352d97e63b6SChris Mason if (!path->nodes[level]) 13530f70abe2SChris Mason return 1; 1354d97e63b6SChris Mason slot = path->slots[level] + 1; 1355d97e63b6SChris Mason c = path->nodes[level]; 13567518a238SChris Mason if (slot >= btrfs_header_nritems(&c->node.header)) { 1357d97e63b6SChris Mason level++; 1358d97e63b6SChris Mason continue; 1359d97e63b6SChris Mason } 13601d4f8a0cSChris Mason blocknr = btrfs_node_blockptr(&c->node, slot); 1361cfaa7295SChris Mason if (next) 1362cfaa7295SChris Mason tree_block_release(root, next); 1363d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1364d97e63b6SChris Mason break; 1365d97e63b6SChris Mason } 1366d97e63b6SChris Mason path->slots[level] = slot; 1367d97e63b6SChris Mason while(1) { 1368d97e63b6SChris Mason level--; 1369d97e63b6SChris Mason c = path->nodes[level]; 1370d97e63b6SChris Mason tree_block_release(root, c); 1371d97e63b6SChris Mason path->nodes[level] = next; 1372d97e63b6SChris Mason path->slots[level] = 0; 1373d97e63b6SChris Mason if (!level) 1374d97e63b6SChris Mason break; 13751d4f8a0cSChris Mason next = read_tree_block(root, 13761d4f8a0cSChris Mason btrfs_node_blockptr(&next->node, 0)); 1377d97e63b6SChris Mason } 1378d97e63b6SChris Mason return 0; 1379d97e63b6SChris Mason } 1380d97e63b6SChris Mason 138102217ed2SChris Mason 1382