12e635a27SChris Mason #include <linux/module.h> 2eb60ceacSChris Mason #include "ctree.h" 3eb60ceacSChris Mason #include "disk-io.h" 47f5c1516SChris Mason #include "transaction.h" 59a8dd150SChris Mason 6e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 7e089f05cSChris Mason *root, struct btrfs_path *path, int level); 8e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 9e089f05cSChris Mason *root, struct btrfs_path *path, int data_size); 10e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 11e20d96d6SChris Mason *root, struct buffer_head *dst, struct buffer_head 12e089f05cSChris Mason *src); 13e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 14e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 15e20d96d6SChris Mason struct buffer_head *src_buf); 16e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 17e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 18d97e63b6SChris Mason 192c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void) 202c90e5d6SChris Mason { 212c90e5d6SChris Mason return kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS); 222c90e5d6SChris Mason } 232c90e5d6SChris Mason 242c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p) 252c90e5d6SChris Mason { 262c90e5d6SChris Mason kmem_cache_free(btrfs_path_cachep, p); 272c90e5d6SChris Mason } 282c90e5d6SChris Mason 29234b63a0SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 30be0e5c09SChris Mason { 31be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 32be0e5c09SChris Mason } 33be0e5c09SChris Mason 34234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 35eb60ceacSChris Mason { 36eb60ceacSChris Mason int i; 37234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 38eb60ceacSChris Mason if (!p->nodes[i]) 39eb60ceacSChris Mason break; 40234b63a0SChris Mason btrfs_block_release(root, p->nodes[i]); 41eb60ceacSChris Mason } 42aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 43eb60ceacSChris Mason } 44eb60ceacSChris Mason 45e089f05cSChris Mason static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 46e20d96d6SChris Mason *root, struct buffer_head *buf, struct buffer_head 47e20d96d6SChris Mason *parent, int parent_slot, struct buffer_head 48e089f05cSChris Mason **cow_ret) 4902217ed2SChris Mason { 50e20d96d6SChris Mason struct buffer_head *cow; 51e20d96d6SChris Mason struct btrfs_node *cow_node; 5202217ed2SChris Mason 537f5c1516SChris Mason if (btrfs_header_generation(btrfs_buffer_header(buf)) == 547f5c1516SChris Mason trans->transid) { 5502217ed2SChris Mason *cow_ret = buf; 5602217ed2SChris Mason return 0; 5702217ed2SChris Mason } 58e089f05cSChris Mason cow = btrfs_alloc_free_block(trans, root); 59e20d96d6SChris Mason cow_node = btrfs_buffer_node(cow); 602c90e5d6SChris Mason if (buf->b_size != root->blocksize || cow->b_size != root->blocksize) 612c90e5d6SChris Mason WARN_ON(1); 62e20d96d6SChris Mason memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize); 63e20d96d6SChris Mason btrfs_set_header_blocknr(&cow_node->header, cow->b_blocknr); 647f5c1516SChris Mason btrfs_set_header_generation(&cow_node->header, trans->transid); 65e089f05cSChris Mason btrfs_inc_ref(trans, root, buf); 6602217ed2SChris Mason if (buf == root->node) { 6702217ed2SChris Mason root->node = cow; 68e20d96d6SChris Mason get_bh(cow); 692c90e5d6SChris Mason if (buf != root->commit_root) { 70e20d96d6SChris Mason btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1); 712c90e5d6SChris Mason } 72234b63a0SChris Mason btrfs_block_release(root, buf); 7302217ed2SChris Mason } else { 74e20d96d6SChris Mason btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot, 75e20d96d6SChris Mason cow->b_blocknr); 76d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 77e20d96d6SChris Mason btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1); 7802217ed2SChris Mason } 79234b63a0SChris Mason btrfs_block_release(root, buf); 802c90e5d6SChris Mason *cow_ret = cow; 8102217ed2SChris Mason return 0; 8202217ed2SChris Mason } 8302217ed2SChris Mason 8474123bd7SChris Mason /* 8574123bd7SChris Mason * The leaf data grows from end-to-front in the node. 8674123bd7SChris Mason * this returns the address of the start of the last item, 8774123bd7SChris Mason * which is the stop of the leaf data stack 8874123bd7SChris Mason */ 89123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 90123abc88SChris Mason struct btrfs_leaf *leaf) 91be0e5c09SChris Mason { 927518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 93be0e5c09SChris Mason if (nr == 0) 94123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 950783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 96be0e5c09SChris Mason } 97be0e5c09SChris Mason 9874123bd7SChris Mason /* 9974123bd7SChris Mason * The space between the end of the leaf items and 10074123bd7SChris Mason * the start of the leaf data. IOW, how much room 10174123bd7SChris Mason * the leaf has left for both items and data 10274123bd7SChris Mason */ 103123abc88SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) 104be0e5c09SChris Mason { 105123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 1067518a238SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 107be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 108123abc88SChris Mason return (char *)(btrfs_leaf_data(leaf) + data_end) - (char *)items_end; 109be0e5c09SChris Mason } 110be0e5c09SChris Mason 11174123bd7SChris Mason /* 11274123bd7SChris Mason * compare two keys in a memcmp fashion 11374123bd7SChris Mason */ 1149aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 115be0e5c09SChris Mason { 116e2fa7227SChris Mason struct btrfs_key k1; 117e2fa7227SChris Mason 118e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 119e2fa7227SChris Mason 120e2fa7227SChris Mason if (k1.objectid > k2->objectid) 121be0e5c09SChris Mason return 1; 122e2fa7227SChris Mason if (k1.objectid < k2->objectid) 123be0e5c09SChris Mason return -1; 124a8a2ee0cSChris Mason if (k1.offset > k2->offset) 125a8a2ee0cSChris Mason return 1; 126a8a2ee0cSChris Mason if (k1.offset < k2->offset) 127a8a2ee0cSChris Mason return -1; 128f254e52cSChris Mason if (k1.flags > k2->flags) 129f254e52cSChris Mason return 1; 130f254e52cSChris Mason if (k1.flags < k2->flags) 131f254e52cSChris Mason return -1; 132be0e5c09SChris Mason return 0; 133be0e5c09SChris Mason } 13474123bd7SChris Mason 135123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 136123abc88SChris Mason int level) 137aa5d6bedSChris Mason { 138aa5d6bedSChris Mason int i; 139234b63a0SChris Mason struct btrfs_node *parent = NULL; 140e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 141aa5d6bedSChris Mason int parent_slot; 1427518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 143aa5d6bedSChris Mason 144aa5d6bedSChris Mason if (path->nodes[level + 1]) 145e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 146aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1477518a238SChris Mason BUG_ON(nritems == 0); 1487518a238SChris Mason if (parent) { 149e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 150123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 151123abc88SChris Mason BUG_ON(memcmp(parent_key, &node->ptrs[0].key, 152e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1531d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1547518a238SChris Mason btrfs_header_blocknr(&node->header)); 155aa5d6bedSChris Mason } 156123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 1577518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 158e2fa7227SChris Mason struct btrfs_key cpukey; 159123abc88SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key); 160123abc88SChris Mason BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0); 161aa5d6bedSChris Mason } 162aa5d6bedSChris Mason return 0; 163aa5d6bedSChris Mason } 164aa5d6bedSChris Mason 165123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 166123abc88SChris Mason int level) 167aa5d6bedSChris Mason { 168aa5d6bedSChris Mason int i; 169e20d96d6SChris Mason struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]); 170234b63a0SChris Mason struct btrfs_node *parent = NULL; 171aa5d6bedSChris Mason int parent_slot; 1727518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 173aa5d6bedSChris Mason 174aa5d6bedSChris Mason if (path->nodes[level + 1]) 175e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 176aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 177123abc88SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 1787518a238SChris Mason 1797518a238SChris Mason if (nritems == 0) 1807518a238SChris Mason return 0; 1817518a238SChris Mason 1827518a238SChris Mason if (parent) { 183e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 184123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 185aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 186e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1871d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1887518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 189aa5d6bedSChris Mason } 1907518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 191e2fa7227SChris Mason struct btrfs_key cpukey; 192e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); 193aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 194e2fa7227SChris Mason &cpukey) >= 0); 1950783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) != 1960783fcfcSChris Mason btrfs_item_end(leaf->items + i + 1)); 197aa5d6bedSChris Mason if (i == 0) { 1980783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) + 1990783fcfcSChris Mason btrfs_item_size(leaf->items + i) != 200123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)); 201aa5d6bedSChris Mason } 202aa5d6bedSChris Mason } 203aa5d6bedSChris Mason return 0; 204aa5d6bedSChris Mason } 205aa5d6bedSChris Mason 206123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 207123abc88SChris Mason int level) 208aa5d6bedSChris Mason { 209aa5d6bedSChris Mason if (level == 0) 210123abc88SChris Mason return check_leaf(root, path, level); 211123abc88SChris Mason return check_node(root, path, level); 212aa5d6bedSChris Mason } 213aa5d6bedSChris Mason 21474123bd7SChris Mason /* 21574123bd7SChris Mason * search for key in the array p. items p are item_size apart 21674123bd7SChris Mason * and there are 'max' items in p 21774123bd7SChris Mason * the slot in the array is returned via slot, and it points to 21874123bd7SChris Mason * the place where you would insert key if it is not found in 21974123bd7SChris Mason * the array. 22074123bd7SChris Mason * 22174123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 22274123bd7SChris Mason */ 2239aca1d51SChris Mason static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 224be0e5c09SChris Mason int max, int *slot) 225be0e5c09SChris Mason { 226be0e5c09SChris Mason int low = 0; 227be0e5c09SChris Mason int high = max; 228be0e5c09SChris Mason int mid; 229be0e5c09SChris Mason int ret; 230e2fa7227SChris Mason struct btrfs_disk_key *tmp; 231be0e5c09SChris Mason 232be0e5c09SChris Mason while(low < high) { 233be0e5c09SChris Mason mid = (low + high) / 2; 234e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 235be0e5c09SChris Mason ret = comp_keys(tmp, key); 236be0e5c09SChris Mason 237be0e5c09SChris Mason if (ret < 0) 238be0e5c09SChris Mason low = mid + 1; 239be0e5c09SChris Mason else if (ret > 0) 240be0e5c09SChris Mason high = mid; 241be0e5c09SChris Mason else { 242be0e5c09SChris Mason *slot = mid; 243be0e5c09SChris Mason return 0; 244be0e5c09SChris Mason } 245be0e5c09SChris Mason } 246be0e5c09SChris Mason *slot = low; 247be0e5c09SChris Mason return 1; 248be0e5c09SChris Mason } 249be0e5c09SChris Mason 25097571fd0SChris Mason /* 25197571fd0SChris Mason * simple bin_search frontend that does the right thing for 25297571fd0SChris Mason * leaves vs nodes 25397571fd0SChris Mason */ 2549aca1d51SChris Mason static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) 255be0e5c09SChris Mason { 2567518a238SChris Mason if (btrfs_is_leaf(c)) { 257234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 2580783fcfcSChris Mason return generic_bin_search((void *)l->items, 2590783fcfcSChris Mason sizeof(struct btrfs_item), 2607518a238SChris Mason key, btrfs_header_nritems(&c->header), 2617518a238SChris Mason slot); 262be0e5c09SChris Mason } else { 263123abc88SChris Mason return generic_bin_search((void *)c->ptrs, 264123abc88SChris Mason sizeof(struct btrfs_key_ptr), 2657518a238SChris Mason key, btrfs_header_nritems(&c->header), 2667518a238SChris Mason slot); 267be0e5c09SChris Mason } 268be0e5c09SChris Mason return -1; 269be0e5c09SChris Mason } 270be0e5c09SChris Mason 271e20d96d6SChris Mason static struct buffer_head *read_node_slot(struct btrfs_root *root, 272e20d96d6SChris Mason struct buffer_head *parent_buf, 273bb803951SChris Mason int slot) 274bb803951SChris Mason { 275e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(parent_buf); 276bb803951SChris Mason if (slot < 0) 277bb803951SChris Mason return NULL; 2787518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 279bb803951SChris Mason return NULL; 2801d4f8a0cSChris Mason return read_tree_block(root, btrfs_node_blockptr(node, slot)); 281bb803951SChris Mason } 282bb803951SChris Mason 283e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 284e089f05cSChris Mason *root, struct btrfs_path *path, int level) 285bb803951SChris Mason { 286e20d96d6SChris Mason struct buffer_head *right_buf; 287e20d96d6SChris Mason struct buffer_head *mid_buf; 288e20d96d6SChris Mason struct buffer_head *left_buf; 289e20d96d6SChris Mason struct buffer_head *parent_buf = NULL; 290234b63a0SChris Mason struct btrfs_node *right = NULL; 291234b63a0SChris Mason struct btrfs_node *mid; 292234b63a0SChris Mason struct btrfs_node *left = NULL; 293234b63a0SChris Mason struct btrfs_node *parent = NULL; 294bb803951SChris Mason int ret = 0; 295bb803951SChris Mason int wret; 296bb803951SChris Mason int pslot; 297bb803951SChris Mason int orig_slot = path->slots[level]; 29879f95c82SChris Mason u64 orig_ptr; 299bb803951SChris Mason 300bb803951SChris Mason if (level == 0) 301bb803951SChris Mason return 0; 302bb803951SChris Mason 303bb803951SChris Mason mid_buf = path->nodes[level]; 304e20d96d6SChris Mason mid = btrfs_buffer_node(mid_buf); 3051d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 30679f95c82SChris Mason 307234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 308bb803951SChris Mason parent_buf = path->nodes[level + 1]; 309bb803951SChris Mason pslot = path->slots[level + 1]; 310bb803951SChris Mason 31140689478SChris Mason /* 31240689478SChris Mason * deal with the case where there is only one pointer in the root 31340689478SChris Mason * by promoting the node below to a root 31440689478SChris Mason */ 315bb803951SChris Mason if (!parent_buf) { 316e20d96d6SChris Mason struct buffer_head *child; 317e20d96d6SChris Mason u64 blocknr = mid_buf->b_blocknr; 318bb803951SChris Mason 3197518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 320bb803951SChris Mason return 0; 321bb803951SChris Mason 322bb803951SChris Mason /* promote the child to a root */ 323bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 324bb803951SChris Mason BUG_ON(!child); 325bb803951SChris Mason root->node = child; 326bb803951SChris Mason path->nodes[level] = NULL; 327d6025579SChris Mason clean_tree_block(trans, root, mid_buf); 328d6025579SChris Mason wait_on_buffer(mid_buf); 329bb803951SChris Mason /* once for the path */ 330234b63a0SChris Mason btrfs_block_release(root, mid_buf); 331bb803951SChris Mason /* once for the root ptr */ 332234b63a0SChris Mason btrfs_block_release(root, mid_buf); 333e089f05cSChris Mason return btrfs_free_extent(trans, root, blocknr, 1, 1); 334bb803951SChris Mason } 335e20d96d6SChris Mason parent = btrfs_buffer_node(parent_buf); 336bb803951SChris Mason 337123abc88SChris Mason if (btrfs_header_nritems(&mid->header) > 338123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 339bb803951SChris Mason return 0; 340bb803951SChris Mason 341bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 342bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 34379f95c82SChris Mason 34479f95c82SChris Mason /* first, try to make some room in the middle buffer */ 345bb803951SChris Mason if (left_buf) { 346e089f05cSChris Mason btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1, 347e089f05cSChris Mason &left_buf); 348e20d96d6SChris Mason left = btrfs_buffer_node(left_buf); 3497518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 350e089f05cSChris Mason wret = push_node_left(trans, root, left_buf, mid_buf); 35179f95c82SChris Mason if (wret < 0) 35279f95c82SChris Mason ret = wret; 353bb803951SChris Mason } 35479f95c82SChris Mason 35579f95c82SChris Mason /* 35679f95c82SChris Mason * then try to empty the right most buffer into the middle 35779f95c82SChris Mason */ 358bb803951SChris Mason if (right_buf) { 359e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1, 360e089f05cSChris Mason &right_buf); 361e20d96d6SChris Mason right = btrfs_buffer_node(right_buf); 362e089f05cSChris Mason wret = push_node_left(trans, root, mid_buf, right_buf); 36379f95c82SChris Mason if (wret < 0) 36479f95c82SChris Mason ret = wret; 3657518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 366e20d96d6SChris Mason u64 blocknr = right_buf->b_blocknr; 367e089f05cSChris Mason clean_tree_block(trans, root, right_buf); 368d6025579SChris Mason wait_on_buffer(right_buf); 369d6025579SChris Mason btrfs_block_release(root, right_buf); 370bb803951SChris Mason right_buf = NULL; 371bb803951SChris Mason right = NULL; 372e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 373e089f05cSChris Mason 1); 374bb803951SChris Mason if (wret) 375bb803951SChris Mason ret = wret; 376e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 377bb803951SChris Mason if (wret) 378bb803951SChris Mason ret = wret; 379bb803951SChris Mason } else { 380d6025579SChris Mason btrfs_memcpy(root, parent, 381d6025579SChris Mason &parent->ptrs[pslot + 1].key, 382123abc88SChris Mason &right->ptrs[0].key, 383e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 384d6025579SChris Mason btrfs_mark_buffer_dirty(parent_buf); 385bb803951SChris Mason } 386bb803951SChris Mason } 3877518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 38879f95c82SChris Mason /* 38979f95c82SChris Mason * we're not allowed to leave a node with one item in the 39079f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 39179f95c82SChris Mason * could try to delete the only pointer in this node. 39279f95c82SChris Mason * So, pull some keys from the left. 39379f95c82SChris Mason * There has to be a left pointer at this point because 39479f95c82SChris Mason * otherwise we would have pulled some pointers from the 39579f95c82SChris Mason * right 39679f95c82SChris Mason */ 39779f95c82SChris Mason BUG_ON(!left_buf); 398e089f05cSChris Mason wret = balance_node_right(trans, root, mid_buf, left_buf); 39979f95c82SChris Mason if (wret < 0) 40079f95c82SChris Mason ret = wret; 40179f95c82SChris Mason BUG_ON(wret == 1); 40279f95c82SChris Mason } 4037518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 40479f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 405e20d96d6SChris Mason u64 blocknr = mid_buf->b_blocknr; 406e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 407d6025579SChris Mason wait_on_buffer(mid_buf); 408d6025579SChris Mason btrfs_block_release(root, mid_buf); 409bb803951SChris Mason mid_buf = NULL; 410bb803951SChris Mason mid = NULL; 411e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 412bb803951SChris Mason if (wret) 413bb803951SChris Mason ret = wret; 414e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 415bb803951SChris Mason if (wret) 416bb803951SChris Mason ret = wret; 41779f95c82SChris Mason } else { 41879f95c82SChris Mason /* update the parent key to reflect our changes */ 419d6025579SChris Mason btrfs_memcpy(root, parent, 420d6025579SChris Mason &parent->ptrs[pslot].key, &mid->ptrs[0].key, 421e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 422d6025579SChris Mason btrfs_mark_buffer_dirty(parent_buf); 42379f95c82SChris Mason } 424bb803951SChris Mason 42579f95c82SChris Mason /* update the path */ 426bb803951SChris Mason if (left_buf) { 4277518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 428e20d96d6SChris Mason get_bh(left_buf); 429bb803951SChris Mason path->nodes[level] = left_buf; 430bb803951SChris Mason path->slots[level + 1] -= 1; 431bb803951SChris Mason path->slots[level] = orig_slot; 432bb803951SChris Mason if (mid_buf) 433234b63a0SChris Mason btrfs_block_release(root, mid_buf); 434bb803951SChris Mason } else { 4357518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 436bb803951SChris Mason path->slots[level] = orig_slot; 437bb803951SChris Mason } 438bb803951SChris Mason } 43979f95c82SChris Mason /* double check we haven't messed things up */ 440123abc88SChris Mason check_block(root, path, level); 441e20d96d6SChris Mason if (orig_ptr != 442e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]), 4431d4f8a0cSChris Mason path->slots[level])) 44479f95c82SChris Mason BUG(); 445bb803951SChris Mason 446bb803951SChris Mason if (right_buf) 447234b63a0SChris Mason btrfs_block_release(root, right_buf); 448bb803951SChris Mason if (left_buf) 449234b63a0SChris Mason btrfs_block_release(root, left_buf); 450bb803951SChris Mason return ret; 451bb803951SChris Mason } 452bb803951SChris Mason 45374123bd7SChris Mason /* 45474123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 45574123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 45674123bd7SChris Mason * level of the path (level 0) 45774123bd7SChris Mason * 45874123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 459aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 460aa5d6bedSChris Mason * search a negative error number is returned. 46197571fd0SChris Mason * 46297571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 46397571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 46497571fd0SChris Mason * possible) 46574123bd7SChris Mason */ 466e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 467e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 468e089f05cSChris Mason ins_len, int cow) 469be0e5c09SChris Mason { 470e20d96d6SChris Mason struct buffer_head *b; 471e20d96d6SChris Mason struct buffer_head *cow_buf; 472234b63a0SChris Mason struct btrfs_node *c; 473be0e5c09SChris Mason int slot; 474be0e5c09SChris Mason int ret; 475be0e5c09SChris Mason int level; 4765c680ed6SChris Mason 47722b0ebdaSChris Mason WARN_ON(p->nodes[0] != NULL); 47822b0ebdaSChris Mason WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex)); 479bb803951SChris Mason again: 480bb803951SChris Mason b = root->node; 481e20d96d6SChris Mason get_bh(b); 482eb60ceacSChris Mason while (b) { 483e20d96d6SChris Mason c = btrfs_buffer_node(b); 484e20d96d6SChris Mason level = btrfs_header_level(&c->header); 48502217ed2SChris Mason if (cow) { 48602217ed2SChris Mason int wret; 487e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 488e20d96d6SChris Mason p->nodes[level + 1], 489e20d96d6SChris Mason p->slots[level + 1], 490e089f05cSChris Mason &cow_buf); 49102217ed2SChris Mason b = cow_buf; 4922c90e5d6SChris Mason c = btrfs_buffer_node(b); 49302217ed2SChris Mason } 49402217ed2SChris Mason BUG_ON(!cow && ins_len); 4952c90e5d6SChris Mason if (level != btrfs_header_level(&c->header)) 4962c90e5d6SChris Mason WARN_ON(1); 4972c90e5d6SChris Mason level = btrfs_header_level(&c->header); 498eb60ceacSChris Mason p->nodes[level] = b; 499123abc88SChris Mason ret = check_block(root, p, level); 500aa5d6bedSChris Mason if (ret) 501aa5d6bedSChris Mason return -1; 502be0e5c09SChris Mason ret = bin_search(c, key, &slot); 5037518a238SChris Mason if (!btrfs_is_leaf(c)) { 504be0e5c09SChris Mason if (ret && slot > 0) 505be0e5c09SChris Mason slot -= 1; 506be0e5c09SChris Mason p->slots[level] = slot; 5077518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 508123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root)) { 509e089f05cSChris Mason int sret = split_node(trans, root, p, level); 5105c680ed6SChris Mason BUG_ON(sret > 0); 5115c680ed6SChris Mason if (sret) 5125c680ed6SChris Mason return sret; 5135c680ed6SChris Mason b = p->nodes[level]; 514e20d96d6SChris Mason c = btrfs_buffer_node(b); 5155c680ed6SChris Mason slot = p->slots[level]; 516bb803951SChris Mason } else if (ins_len < 0) { 517e089f05cSChris Mason int sret = balance_level(trans, root, p, 518e089f05cSChris Mason level); 519bb803951SChris Mason if (sret) 520bb803951SChris Mason return sret; 521bb803951SChris Mason b = p->nodes[level]; 522bb803951SChris Mason if (!b) 523bb803951SChris Mason goto again; 524e20d96d6SChris Mason c = btrfs_buffer_node(b); 525bb803951SChris Mason slot = p->slots[level]; 5267518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 5275c680ed6SChris Mason } 5281d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 529be0e5c09SChris Mason } else { 530234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 531be0e5c09SChris Mason p->slots[level] = slot; 532123abc88SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 5330783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 534e089f05cSChris Mason int sret = split_leaf(trans, root, p, ins_len); 5355c680ed6SChris Mason BUG_ON(sret > 0); 5365c680ed6SChris Mason if (sret) 5375c680ed6SChris Mason return sret; 5385c680ed6SChris Mason } 539be0e5c09SChris Mason return ret; 540be0e5c09SChris Mason } 541be0e5c09SChris Mason } 542aa5d6bedSChris Mason return 1; 543be0e5c09SChris Mason } 544be0e5c09SChris Mason 54574123bd7SChris Mason /* 54674123bd7SChris Mason * adjust the pointers going up the tree, starting at level 54774123bd7SChris Mason * making sure the right key of each node is points to 'key'. 54874123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 54974123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 55074123bd7SChris Mason * higher levels 551aa5d6bedSChris Mason * 552aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 553aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 55474123bd7SChris Mason */ 555e089f05cSChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root 556e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 557e089f05cSChris Mason *key, int level) 558be0e5c09SChris Mason { 559be0e5c09SChris Mason int i; 560aa5d6bedSChris Mason int ret = 0; 561234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 562234b63a0SChris Mason struct btrfs_node *t; 563be0e5c09SChris Mason int tslot = path->slots[i]; 564eb60ceacSChris Mason if (!path->nodes[i]) 565be0e5c09SChris Mason break; 566e20d96d6SChris Mason t = btrfs_buffer_node(path->nodes[i]); 567d6025579SChris Mason btrfs_memcpy(root, t, &t->ptrs[tslot].key, key, sizeof(*key)); 568d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[i]); 569be0e5c09SChris Mason if (tslot != 0) 570be0e5c09SChris Mason break; 571be0e5c09SChris Mason } 572aa5d6bedSChris Mason return ret; 573be0e5c09SChris Mason } 574be0e5c09SChris Mason 57574123bd7SChris Mason /* 57674123bd7SChris Mason * try to push data from one node into the next node left in the 57779f95c82SChris Mason * tree. 578aa5d6bedSChris Mason * 579aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 580aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 58174123bd7SChris Mason */ 582e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 583e20d96d6SChris Mason *root, struct buffer_head *dst_buf, struct 584e20d96d6SChris Mason buffer_head *src_buf) 585be0e5c09SChris Mason { 586e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 587e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 588be0e5c09SChris Mason int push_items = 0; 589bb803951SChris Mason int src_nritems; 590bb803951SChris Mason int dst_nritems; 591aa5d6bedSChris Mason int ret = 0; 592be0e5c09SChris Mason 5937518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5947518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 595123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 596eb60ceacSChris Mason if (push_items <= 0) { 597be0e5c09SChris Mason return 1; 598eb60ceacSChris Mason } 599be0e5c09SChris Mason 600be0e5c09SChris Mason if (src_nritems < push_items) 601be0e5c09SChris Mason push_items = src_nritems; 60279f95c82SChris Mason 603d6025579SChris Mason btrfs_memcpy(root, dst, dst->ptrs + dst_nritems, src->ptrs, 604123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 605bb803951SChris Mason if (push_items < src_nritems) { 606d6025579SChris Mason btrfs_memmove(root, src, src->ptrs, src->ptrs + push_items, 607e2fa7227SChris Mason (src_nritems - push_items) * 608123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 609bb803951SChris Mason } 6107518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6117518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 612d6025579SChris Mason btrfs_mark_buffer_dirty(src_buf); 613d6025579SChris Mason btrfs_mark_buffer_dirty(dst_buf); 614bb803951SChris Mason return ret; 615be0e5c09SChris Mason } 616be0e5c09SChris Mason 61797571fd0SChris Mason /* 61879f95c82SChris Mason * try to push data from one node into the next node right in the 61979f95c82SChris Mason * tree. 62079f95c82SChris Mason * 62179f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 62279f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 62379f95c82SChris Mason * 62479f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 62579f95c82SChris Mason */ 626e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 627e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 628e20d96d6SChris Mason struct buffer_head *src_buf) 62979f95c82SChris Mason { 630e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 631e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 63279f95c82SChris Mason int push_items = 0; 63379f95c82SChris Mason int max_push; 63479f95c82SChris Mason int src_nritems; 63579f95c82SChris Mason int dst_nritems; 63679f95c82SChris Mason int ret = 0; 63779f95c82SChris Mason 6387518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6397518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 640123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 64179f95c82SChris Mason if (push_items <= 0) { 64279f95c82SChris Mason return 1; 64379f95c82SChris Mason } 64479f95c82SChris Mason 64579f95c82SChris Mason max_push = src_nritems / 2 + 1; 64679f95c82SChris Mason /* don't try to empty the node */ 64779f95c82SChris Mason if (max_push > src_nritems) 64879f95c82SChris Mason return 1; 64979f95c82SChris Mason if (max_push < push_items) 65079f95c82SChris Mason push_items = max_push; 65179f95c82SChris Mason 652d6025579SChris Mason btrfs_memmove(root, dst, dst->ptrs + push_items, dst->ptrs, 653123abc88SChris Mason dst_nritems * sizeof(struct btrfs_key_ptr)); 654d6025579SChris Mason 655d6025579SChris Mason btrfs_memcpy(root, dst, dst->ptrs, 656d6025579SChris Mason src->ptrs + src_nritems - push_items, 657123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 65879f95c82SChris Mason 6597518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6607518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 66179f95c82SChris Mason 662d6025579SChris Mason btrfs_mark_buffer_dirty(src_buf); 663d6025579SChris Mason btrfs_mark_buffer_dirty(dst_buf); 66479f95c82SChris Mason return ret; 66579f95c82SChris Mason } 66679f95c82SChris Mason 66779f95c82SChris Mason /* 66897571fd0SChris Mason * helper function to insert a new root level in the tree. 66997571fd0SChris Mason * A new node is allocated, and a single item is inserted to 67097571fd0SChris Mason * point to the existing root 671aa5d6bedSChris Mason * 672aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 67397571fd0SChris Mason */ 674e089f05cSChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root 675e089f05cSChris Mason *root, struct btrfs_path *path, int level) 67674123bd7SChris Mason { 677e20d96d6SChris Mason struct buffer_head *t; 678234b63a0SChris Mason struct btrfs_node *lower; 679234b63a0SChris Mason struct btrfs_node *c; 680e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 6815c680ed6SChris Mason 6825c680ed6SChris Mason BUG_ON(path->nodes[level]); 6835c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 6845c680ed6SChris Mason 685e089f05cSChris Mason t = btrfs_alloc_free_block(trans, root); 686e20d96d6SChris Mason c = btrfs_buffer_node(t); 687123abc88SChris Mason memset(c, 0, root->blocksize); 6887518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 6897518a238SChris Mason btrfs_set_header_level(&c->header, level); 690e20d96d6SChris Mason btrfs_set_header_blocknr(&c->header, t->b_blocknr); 6917f5c1516SChris Mason btrfs_set_header_generation(&c->header, trans->transid); 6927518a238SChris Mason btrfs_set_header_parentid(&c->header, 693e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 694e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level-1]); 6957518a238SChris Mason if (btrfs_is_leaf(lower)) 696234b63a0SChris Mason lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 69774123bd7SChris Mason else 698123abc88SChris Mason lower_key = &lower->ptrs[0].key; 699d6025579SChris Mason btrfs_memcpy(root, c, &c->ptrs[0].key, lower_key, 700d6025579SChris Mason sizeof(struct btrfs_disk_key)); 701e20d96d6SChris Mason btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->b_blocknr); 702d5719762SChris Mason 703d6025579SChris Mason btrfs_mark_buffer_dirty(t); 704d5719762SChris Mason 705cfaa7295SChris Mason /* the super has an extra ref to root->node */ 706234b63a0SChris Mason btrfs_block_release(root, root->node); 70774123bd7SChris Mason root->node = t; 708e20d96d6SChris Mason get_bh(t); 70974123bd7SChris Mason path->nodes[level] = t; 71074123bd7SChris Mason path->slots[level] = 0; 71174123bd7SChris Mason return 0; 71274123bd7SChris Mason } 7135c680ed6SChris Mason 7145c680ed6SChris Mason /* 7155c680ed6SChris Mason * worker function to insert a single pointer in a node. 7165c680ed6SChris Mason * the node should have enough room for the pointer already 71797571fd0SChris Mason * 7185c680ed6SChris Mason * slot and level indicate where you want the key to go, and 7195c680ed6SChris Mason * blocknr is the block the key points to. 720aa5d6bedSChris Mason * 721aa5d6bedSChris Mason * returns zero on success and < 0 on any error 7225c680ed6SChris Mason */ 723e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 724e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 725e089f05cSChris Mason *key, u64 blocknr, int slot, int level) 7265c680ed6SChris Mason { 727234b63a0SChris Mason struct btrfs_node *lower; 7285c680ed6SChris Mason int nritems; 7295c680ed6SChris Mason 7305c680ed6SChris Mason BUG_ON(!path->nodes[level]); 731e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level]); 7327518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 73374123bd7SChris Mason if (slot > nritems) 73474123bd7SChris Mason BUG(); 735123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 73674123bd7SChris Mason BUG(); 73774123bd7SChris Mason if (slot != nritems) { 738d6025579SChris Mason btrfs_memmove(root, lower, lower->ptrs + slot + 1, 739d6025579SChris Mason lower->ptrs + slot, 740123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 74174123bd7SChris Mason } 742d6025579SChris Mason btrfs_memcpy(root, lower, &lower->ptrs[slot].key, 743d6025579SChris Mason key, sizeof(struct btrfs_disk_key)); 7441d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 7457518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 746d6025579SChris Mason btrfs_mark_buffer_dirty(path->nodes[level]); 74774123bd7SChris Mason return 0; 74874123bd7SChris Mason } 74974123bd7SChris Mason 75097571fd0SChris Mason /* 75197571fd0SChris Mason * split the node at the specified level in path in two. 75297571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 75397571fd0SChris Mason * 75497571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 75597571fd0SChris Mason * left and right, if either one works, it returns right away. 756aa5d6bedSChris Mason * 757aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 75897571fd0SChris Mason */ 759e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 760e089f05cSChris Mason *root, struct btrfs_path *path, int level) 761be0e5c09SChris Mason { 762e20d96d6SChris Mason struct buffer_head *t; 763234b63a0SChris Mason struct btrfs_node *c; 764e20d96d6SChris Mason struct buffer_head *split_buffer; 765234b63a0SChris Mason struct btrfs_node *split; 766be0e5c09SChris Mason int mid; 7675c680ed6SChris Mason int ret; 768aa5d6bedSChris Mason int wret; 7697518a238SChris Mason u32 c_nritems; 770be0e5c09SChris Mason 7715c680ed6SChris Mason t = path->nodes[level]; 772e20d96d6SChris Mason c = btrfs_buffer_node(t); 7735c680ed6SChris Mason if (t == root->node) { 7745c680ed6SChris Mason /* trying to split the root, lets make a new one */ 775e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 7765c680ed6SChris Mason if (ret) 7775c680ed6SChris Mason return ret; 7785c680ed6SChris Mason } 7797518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 780e089f05cSChris Mason split_buffer = btrfs_alloc_free_block(trans, root); 781e20d96d6SChris Mason split = btrfs_buffer_node(split_buffer); 7827518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 7839a6f11edSChris Mason btrfs_set_header_level(&split->header, btrfs_header_level(&c->header)); 784e20d96d6SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->b_blocknr); 7857f5c1516SChris Mason btrfs_set_header_generation(&split->header, trans->transid); 7867518a238SChris Mason btrfs_set_header_parentid(&split->header, 787e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 7887518a238SChris Mason mid = (c_nritems + 1) / 2; 789d6025579SChris Mason btrfs_memcpy(root, split, split->ptrs, c->ptrs + mid, 790123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 7917518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7927518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 793aa5d6bedSChris Mason ret = 0; 794aa5d6bedSChris Mason 795d6025579SChris Mason btrfs_mark_buffer_dirty(t); 796d6025579SChris Mason btrfs_mark_buffer_dirty(split_buffer); 797e089f05cSChris Mason wret = insert_ptr(trans, root, path, &split->ptrs[0].key, 798e20d96d6SChris Mason split_buffer->b_blocknr, path->slots[level + 1] + 1, 799123abc88SChris Mason level + 1); 800aa5d6bedSChris Mason if (wret) 801aa5d6bedSChris Mason ret = wret; 802aa5d6bedSChris Mason 8035de08d7dSChris Mason if (path->slots[level] >= mid) { 8045c680ed6SChris Mason path->slots[level] -= mid; 805234b63a0SChris Mason btrfs_block_release(root, t); 8065c680ed6SChris Mason path->nodes[level] = split_buffer; 8075c680ed6SChris Mason path->slots[level + 1] += 1; 808eb60ceacSChris Mason } else { 809234b63a0SChris Mason btrfs_block_release(root, split_buffer); 810be0e5c09SChris Mason } 811aa5d6bedSChris Mason return ret; 812be0e5c09SChris Mason } 813be0e5c09SChris Mason 81474123bd7SChris Mason /* 81574123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 81674123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 81774123bd7SChris Mason * space used both by the item structs and the item data 81874123bd7SChris Mason */ 819234b63a0SChris Mason static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 820be0e5c09SChris Mason { 821be0e5c09SChris Mason int data_len; 822be0e5c09SChris Mason int end = start + nr - 1; 823be0e5c09SChris Mason 824be0e5c09SChris Mason if (!nr) 825be0e5c09SChris Mason return 0; 8260783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 8270783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 8280783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 829be0e5c09SChris Mason return data_len; 830be0e5c09SChris Mason } 831be0e5c09SChris Mason 83274123bd7SChris Mason /* 83300ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 83400ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 835aa5d6bedSChris Mason * 836aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 837aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 83800ec4c51SChris Mason */ 839e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 840e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 84100ec4c51SChris Mason { 842e20d96d6SChris Mason struct buffer_head *left_buf = path->nodes[0]; 843e20d96d6SChris Mason struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf); 844234b63a0SChris Mason struct btrfs_leaf *right; 845e20d96d6SChris Mason struct buffer_head *right_buf; 846e20d96d6SChris Mason struct buffer_head *upper; 847e20d96d6SChris Mason struct btrfs_node *upper_node; 84800ec4c51SChris Mason int slot; 84900ec4c51SChris Mason int i; 85000ec4c51SChris Mason int free_space; 85100ec4c51SChris Mason int push_space = 0; 85200ec4c51SChris Mason int push_items = 0; 8530783fcfcSChris Mason struct btrfs_item *item; 8547518a238SChris Mason u32 left_nritems; 8557518a238SChris Mason u32 right_nritems; 85600ec4c51SChris Mason 85700ec4c51SChris Mason slot = path->slots[1]; 85800ec4c51SChris Mason if (!path->nodes[1]) { 85900ec4c51SChris Mason return 1; 86000ec4c51SChris Mason } 86100ec4c51SChris Mason upper = path->nodes[1]; 862e20d96d6SChris Mason upper_node = btrfs_buffer_node(upper); 863e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&upper_node->header) - 1) { 86400ec4c51SChris Mason return 1; 86500ec4c51SChris Mason } 866e20d96d6SChris Mason right_buf = read_tree_block(root, 867e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1)); 868e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 869123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8700783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 871234b63a0SChris Mason btrfs_block_release(root, right_buf); 87200ec4c51SChris Mason return 1; 87300ec4c51SChris Mason } 87402217ed2SChris Mason /* cow and double check */ 875e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf); 876e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 877123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8780783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 879234b63a0SChris Mason btrfs_block_release(root, right_buf); 88002217ed2SChris Mason return 1; 88102217ed2SChris Mason } 88202217ed2SChris Mason 8837518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8847518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 88500ec4c51SChris Mason item = left->items + i; 88600ec4c51SChris Mason if (path->slots[0] == i) 88700ec4c51SChris Mason push_space += data_size + sizeof(*item); 8880783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8890783fcfcSChris Mason free_space) 89000ec4c51SChris Mason break; 89100ec4c51SChris Mason push_items++; 8920783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 89300ec4c51SChris Mason } 89400ec4c51SChris Mason if (push_items == 0) { 895234b63a0SChris Mason btrfs_block_release(root, right_buf); 89600ec4c51SChris Mason return 1; 89700ec4c51SChris Mason } 8987518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 89900ec4c51SChris Mason /* push left to right */ 9000783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 901123abc88SChris Mason push_space -= leaf_data_end(root, left); 90200ec4c51SChris Mason /* make room in the right data area */ 903d6025579SChris Mason btrfs_memmove(root, right, btrfs_leaf_data(right) + 904d6025579SChris Mason leaf_data_end(root, right) - push_space, 905d6025579SChris Mason btrfs_leaf_data(right) + 906d6025579SChris Mason leaf_data_end(root, right), BTRFS_LEAF_DATA_SIZE(root) - 907d6025579SChris Mason leaf_data_end(root, right)); 90800ec4c51SChris Mason /* copy from the left data area */ 909d6025579SChris Mason btrfs_memcpy(root, right, btrfs_leaf_data(right) + 910d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 911d6025579SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), 912d6025579SChris Mason push_space); 913d6025579SChris Mason btrfs_memmove(root, right, right->items + push_items, right->items, 9140783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 91500ec4c51SChris Mason /* copy the items from left to right */ 916d6025579SChris Mason btrfs_memcpy(root, right, right->items, left->items + 917d6025579SChris Mason left_nritems - push_items, 9180783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 91900ec4c51SChris Mason 92000ec4c51SChris Mason /* update the item pointers */ 9217518a238SChris Mason right_nritems += push_items; 9227518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 923123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 9247518a238SChris Mason for (i = 0; i < right_nritems; i++) { 9250783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 9260783fcfcSChris Mason btrfs_item_size(right->items + i)); 9270783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 92800ec4c51SChris Mason } 9297518a238SChris Mason left_nritems -= push_items; 9307518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 93100ec4c51SChris Mason 932d6025579SChris Mason btrfs_mark_buffer_dirty(left_buf); 933d6025579SChris Mason btrfs_mark_buffer_dirty(right_buf); 934d6025579SChris Mason btrfs_memcpy(root, upper_node, &upper_node->ptrs[slot + 1].key, 935e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 936d6025579SChris Mason btrfs_mark_buffer_dirty(upper); 93702217ed2SChris Mason 93800ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 9397518a238SChris Mason if (path->slots[0] >= left_nritems) { 9407518a238SChris Mason path->slots[0] -= left_nritems; 941234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 94200ec4c51SChris Mason path->nodes[0] = right_buf; 94300ec4c51SChris Mason path->slots[1] += 1; 94400ec4c51SChris Mason } else { 945234b63a0SChris Mason btrfs_block_release(root, right_buf); 94600ec4c51SChris Mason } 94700ec4c51SChris Mason return 0; 94800ec4c51SChris Mason } 94900ec4c51SChris Mason /* 95074123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 95174123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 95274123bd7SChris Mason */ 953e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 954e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 955be0e5c09SChris Mason { 956e20d96d6SChris Mason struct buffer_head *right_buf = path->nodes[0]; 957e20d96d6SChris Mason struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf); 958e20d96d6SChris Mason struct buffer_head *t; 959234b63a0SChris Mason struct btrfs_leaf *left; 960be0e5c09SChris Mason int slot; 961be0e5c09SChris Mason int i; 962be0e5c09SChris Mason int free_space; 963be0e5c09SChris Mason int push_space = 0; 964be0e5c09SChris Mason int push_items = 0; 9650783fcfcSChris Mason struct btrfs_item *item; 9667518a238SChris Mason u32 old_left_nritems; 967aa5d6bedSChris Mason int ret = 0; 968aa5d6bedSChris Mason int wret; 969be0e5c09SChris Mason 970be0e5c09SChris Mason slot = path->slots[1]; 971be0e5c09SChris Mason if (slot == 0) { 972be0e5c09SChris Mason return 1; 973be0e5c09SChris Mason } 974be0e5c09SChris Mason if (!path->nodes[1]) { 975be0e5c09SChris Mason return 1; 976be0e5c09SChris Mason } 977e20d96d6SChris Mason t = read_tree_block(root, 978e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1)); 979e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 980123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9810783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 982234b63a0SChris Mason btrfs_block_release(root, t); 983be0e5c09SChris Mason return 1; 984be0e5c09SChris Mason } 98502217ed2SChris Mason 98602217ed2SChris Mason /* cow and double check */ 987e089f05cSChris Mason btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); 988e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 989123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9900783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 991234b63a0SChris Mason btrfs_block_release(root, t); 99202217ed2SChris Mason return 1; 99302217ed2SChris Mason } 99402217ed2SChris Mason 9957518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 996be0e5c09SChris Mason item = right->items + i; 997be0e5c09SChris Mason if (path->slots[0] == i) 998be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9990783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 10000783fcfcSChris Mason free_space) 1001be0e5c09SChris Mason break; 1002be0e5c09SChris Mason push_items++; 10030783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 1004be0e5c09SChris Mason } 1005be0e5c09SChris Mason if (push_items == 0) { 1006234b63a0SChris Mason btrfs_block_release(root, t); 1007be0e5c09SChris Mason return 1; 1008be0e5c09SChris Mason } 1009be0e5c09SChris Mason /* push data from right to left */ 1010d6025579SChris Mason btrfs_memcpy(root, left, left->items + 1011d6025579SChris Mason btrfs_header_nritems(&left->header), 10120783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 1013123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 10140783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 1015d6025579SChris Mason btrfs_memcpy(root, left, btrfs_leaf_data(left) + 1016d6025579SChris Mason leaf_data_end(root, left) - push_space, 1017123abc88SChris Mason btrfs_leaf_data(right) + 1018123abc88SChris Mason btrfs_item_offset(right->items + push_items - 1), 1019be0e5c09SChris Mason push_space); 10207518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 1021eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 1022eb60ceacSChris Mason 1023be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 1024123abc88SChris Mason u32 ioff = btrfs_item_offset(left->items + i); 1025123abc88SChris Mason btrfs_set_item_offset(left->items + i, ioff - 1026123abc88SChris Mason (BTRFS_LEAF_DATA_SIZE(root) - 10270783fcfcSChris Mason btrfs_item_offset(left->items + 10280783fcfcSChris Mason old_left_nritems - 1))); 1029be0e5c09SChris Mason } 10307518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 1031be0e5c09SChris Mason 1032be0e5c09SChris Mason /* fixup right node */ 10330783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 1034123abc88SChris Mason leaf_data_end(root, right); 1035d6025579SChris Mason btrfs_memmove(root, right, btrfs_leaf_data(right) + 1036d6025579SChris Mason BTRFS_LEAF_DATA_SIZE(root) - push_space, 1037d6025579SChris Mason btrfs_leaf_data(right) + 1038123abc88SChris Mason leaf_data_end(root, right), push_space); 1039d6025579SChris Mason btrfs_memmove(root, right, right->items, right->items + push_items, 10407518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 10410783fcfcSChris Mason sizeof(struct btrfs_item)); 10427518a238SChris Mason btrfs_set_header_nritems(&right->header, 10437518a238SChris Mason btrfs_header_nritems(&right->header) - 10447518a238SChris Mason push_items); 1045123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1046eb60ceacSChris Mason 10477518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 10480783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 10490783fcfcSChris Mason btrfs_item_size(right->items + i)); 10500783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 1051be0e5c09SChris Mason } 1052eb60ceacSChris Mason 1053d6025579SChris Mason btrfs_mark_buffer_dirty(t); 1054d6025579SChris Mason btrfs_mark_buffer_dirty(right_buf); 1055eb60ceacSChris Mason 1056e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); 1057aa5d6bedSChris Mason if (wret) 1058aa5d6bedSChris Mason ret = wret; 1059be0e5c09SChris Mason 1060be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1061be0e5c09SChris Mason if (path->slots[0] < push_items) { 1062be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1063234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1064eb60ceacSChris Mason path->nodes[0] = t; 1065be0e5c09SChris Mason path->slots[1] -= 1; 1066be0e5c09SChris Mason } else { 1067234b63a0SChris Mason btrfs_block_release(root, t); 1068be0e5c09SChris Mason path->slots[0] -= push_items; 1069be0e5c09SChris Mason } 1070eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1071aa5d6bedSChris Mason return ret; 1072be0e5c09SChris Mason } 1073be0e5c09SChris Mason 107474123bd7SChris Mason /* 107574123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 107674123bd7SChris Mason * available for the resulting leaf level of the path. 1077aa5d6bedSChris Mason * 1078aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 107974123bd7SChris Mason */ 1080e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1081e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1082be0e5c09SChris Mason { 1083e20d96d6SChris Mason struct buffer_head *l_buf; 1084234b63a0SChris Mason struct btrfs_leaf *l; 10857518a238SChris Mason u32 nritems; 1086eb60ceacSChris Mason int mid; 1087eb60ceacSChris Mason int slot; 1088234b63a0SChris Mason struct btrfs_leaf *right; 1089e20d96d6SChris Mason struct buffer_head *right_buffer; 10900783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1091be0e5c09SChris Mason int data_copy_size; 1092be0e5c09SChris Mason int rt_data_off; 1093be0e5c09SChris Mason int i; 1094be0e5c09SChris Mason int ret; 1095aa5d6bedSChris Mason int wret; 1096be0e5c09SChris Mason 109740689478SChris Mason /* first try to make some room by pushing left and right */ 1098e089f05cSChris Mason wret = push_leaf_left(trans, root, path, data_size); 1099eaee50e8SChris Mason if (wret < 0) 1100eaee50e8SChris Mason return wret; 1101eaee50e8SChris Mason if (wret) { 1102e089f05cSChris Mason wret = push_leaf_right(trans, root, path, data_size); 1103eaee50e8SChris Mason if (wret < 0) 1104eaee50e8SChris Mason return wret; 1105eaee50e8SChris Mason } 1106eb60ceacSChris Mason l_buf = path->nodes[0]; 1107e20d96d6SChris Mason l = btrfs_buffer_leaf(l_buf); 1108aa5d6bedSChris Mason 1109aa5d6bedSChris Mason /* did the pushes work? */ 1110123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1111123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1112be0e5c09SChris Mason return 0; 1113aa5d6bedSChris Mason 11145c680ed6SChris Mason if (!path->nodes[1]) { 1115e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 11165c680ed6SChris Mason if (ret) 11175c680ed6SChris Mason return ret; 11185c680ed6SChris Mason } 1119eb60ceacSChris Mason slot = path->slots[0]; 11207518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1121eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1122e089f05cSChris Mason right_buffer = btrfs_alloc_free_block(trans, root); 1123eb60ceacSChris Mason BUG_ON(!right_buffer); 1124eb60ceacSChris Mason BUG_ON(mid == nritems); 1125e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buffer); 1126123abc88SChris Mason memset(&right->header, 0, sizeof(right->header)); 1127be0e5c09SChris Mason if (mid <= slot) { 112897571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1129be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1130123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1131be0e5c09SChris Mason BUG(); 1132be0e5c09SChris Mason } else { 113397571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1134be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1135123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1136be0e5c09SChris Mason BUG(); 1137be0e5c09SChris Mason } 11387518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 1139e20d96d6SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr); 11407f5c1516SChris Mason btrfs_set_header_generation(&right->header, trans->transid); 11417518a238SChris Mason btrfs_set_header_level(&right->header, 0); 11427518a238SChris Mason btrfs_set_header_parentid(&right->header, 1143e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 1144123abc88SChris Mason data_copy_size = btrfs_item_end(l->items + mid) - 1145123abc88SChris Mason leaf_data_end(root, l); 1146d6025579SChris Mason btrfs_memcpy(root, right, right->items, l->items + mid, 11470783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1148d6025579SChris Mason btrfs_memcpy(root, right, 1149d6025579SChris Mason btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1150123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1151123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 1152123abc88SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1153123abc88SChris Mason btrfs_item_end(l->items + mid); 115474123bd7SChris Mason 11550783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1156123abc88SChris Mason u32 ioff = btrfs_item_offset(right->items + i); 11570783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 11580783fcfcSChris Mason } 115974123bd7SChris Mason 11607518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1161aa5d6bedSChris Mason ret = 0; 1162e089f05cSChris Mason wret = insert_ptr(trans, root, path, &right->items[0].key, 1163e20d96d6SChris Mason right_buffer->b_blocknr, path->slots[1] + 1, 1); 1164aa5d6bedSChris Mason if (wret) 1165aa5d6bedSChris Mason ret = wret; 1166d6025579SChris Mason btrfs_mark_buffer_dirty(right_buffer); 1167d6025579SChris Mason btrfs_mark_buffer_dirty(l_buf); 1168eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1169be0e5c09SChris Mason if (mid <= slot) { 1170234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1171eb60ceacSChris Mason path->nodes[0] = right_buffer; 1172be0e5c09SChris Mason path->slots[0] -= mid; 1173be0e5c09SChris Mason path->slots[1] += 1; 1174eb60ceacSChris Mason } else 1175234b63a0SChris Mason btrfs_block_release(root, right_buffer); 1176eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1177be0e5c09SChris Mason return ret; 1178be0e5c09SChris Mason } 1179be0e5c09SChris Mason 118074123bd7SChris Mason /* 118174123bd7SChris Mason * Given a key and some data, insert an item into the tree. 118274123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 118374123bd7SChris Mason */ 1184e089f05cSChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1185e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_key 1186e089f05cSChris Mason *cpu_key, u32 data_size) 1187be0e5c09SChris Mason { 1188aa5d6bedSChris Mason int ret = 0; 1189be0e5c09SChris Mason int slot; 1190eb60ceacSChris Mason int slot_orig; 1191234b63a0SChris Mason struct btrfs_leaf *leaf; 1192e20d96d6SChris Mason struct buffer_head *leaf_buf; 11937518a238SChris Mason u32 nritems; 1194be0e5c09SChris Mason unsigned int data_end; 1195e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1196e2fa7227SChris Mason 1197e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1198be0e5c09SChris Mason 119974123bd7SChris Mason /* create a root if there isn't one */ 12005c680ed6SChris Mason if (!root->node) 1201cfaa7295SChris Mason BUG(); 1202e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 1203eb60ceacSChris Mason if (ret == 0) { 1204f0930a37SChris Mason return -EEXIST; 1205aa5d6bedSChris Mason } 1206ed2ff2cbSChris Mason if (ret < 0) 1207ed2ff2cbSChris Mason goto out; 1208be0e5c09SChris Mason 120962e2749eSChris Mason slot_orig = path->slots[0]; 121062e2749eSChris Mason leaf_buf = path->nodes[0]; 1211e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 121274123bd7SChris Mason 12137518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1214123abc88SChris Mason data_end = leaf_data_end(root, leaf); 1215eb60ceacSChris Mason 1216123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 1217234b63a0SChris Mason sizeof(struct btrfs_item) + data_size) 1218be0e5c09SChris Mason BUG(); 1219be0e5c09SChris Mason 122062e2749eSChris Mason slot = path->slots[0]; 1221eb60ceacSChris Mason BUG_ON(slot < 0); 1222be0e5c09SChris Mason if (slot != nritems) { 1223be0e5c09SChris Mason int i; 12240783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1225be0e5c09SChris Mason 1226be0e5c09SChris Mason /* 1227be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1228be0e5c09SChris Mason */ 1229be0e5c09SChris Mason /* first correct the data pointers */ 12300783fcfcSChris Mason for (i = slot; i < nritems; i++) { 1231123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 12320783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 12330783fcfcSChris Mason ioff - data_size); 12340783fcfcSChris Mason } 1235be0e5c09SChris Mason 1236be0e5c09SChris Mason /* shift the items */ 1237d6025579SChris Mason btrfs_memmove(root, leaf, leaf->items + slot + 1, 1238d6025579SChris Mason leaf->items + slot, 12390783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1240be0e5c09SChris Mason 1241be0e5c09SChris Mason /* shift the data */ 1242d6025579SChris Mason btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 1243d6025579SChris Mason data_end - data_size, btrfs_leaf_data(leaf) + 1244be0e5c09SChris Mason data_end, old_data - data_end); 1245be0e5c09SChris Mason data_end = old_data; 1246be0e5c09SChris Mason } 124762e2749eSChris Mason /* setup the item for the new data */ 1248d6025579SChris Mason btrfs_memcpy(root, leaf, &leaf->items[slot].key, &disk_key, 1249e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 12500783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 12510783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 12527518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1253d6025579SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 1254aa5d6bedSChris Mason 1255aa5d6bedSChris Mason ret = 0; 12568e19f2cdSChris Mason if (slot == 0) 1257e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 1258aa5d6bedSChris Mason 1259123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1260be0e5c09SChris Mason BUG(); 126162e2749eSChris Mason check_leaf(root, path, 0); 1262ed2ff2cbSChris Mason out: 126362e2749eSChris Mason return ret; 126462e2749eSChris Mason } 126562e2749eSChris Mason 126662e2749eSChris Mason /* 126762e2749eSChris Mason * Given a key and some data, insert an item into the tree. 126862e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 126962e2749eSChris Mason */ 1270e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 1271e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 1272e089f05cSChris Mason data_size) 127362e2749eSChris Mason { 127462e2749eSChris Mason int ret = 0; 12752c90e5d6SChris Mason struct btrfs_path *path; 127662e2749eSChris Mason u8 *ptr; 127762e2749eSChris Mason 12782c90e5d6SChris Mason path = btrfs_alloc_path(); 12792c90e5d6SChris Mason BUG_ON(!path); 12802c90e5d6SChris Mason btrfs_init_path(path); 12812c90e5d6SChris Mason ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size); 128262e2749eSChris Mason if (!ret) { 12832c90e5d6SChris Mason ptr = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), 12842c90e5d6SChris Mason path->slots[0], u8); 12852c90e5d6SChris Mason btrfs_memcpy(root, path->nodes[0]->b_data, 1286d6025579SChris Mason ptr, data, data_size); 12872c90e5d6SChris Mason btrfs_mark_buffer_dirty(path->nodes[0]); 128862e2749eSChris Mason } 12892c90e5d6SChris Mason btrfs_release_path(root, path); 12902c90e5d6SChris Mason btrfs_free_path(path); 1291aa5d6bedSChris Mason return ret; 1292be0e5c09SChris Mason } 1293be0e5c09SChris Mason 129474123bd7SChris Mason /* 12955de08d7dSChris Mason * delete the pointer from a given node. 129674123bd7SChris Mason * 129774123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 129874123bd7SChris Mason * continuing all the way the root if required. The root is converted into 129974123bd7SChris Mason * a leaf if all the nodes are emptied. 130074123bd7SChris Mason */ 1301e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1302e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 1303be0e5c09SChris Mason { 1304234b63a0SChris Mason struct btrfs_node *node; 1305e20d96d6SChris Mason struct buffer_head *parent = path->nodes[level]; 13067518a238SChris Mason u32 nritems; 1307aa5d6bedSChris Mason int ret = 0; 1308bb803951SChris Mason int wret; 1309be0e5c09SChris Mason 1310e20d96d6SChris Mason node = btrfs_buffer_node(parent); 13117518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1312be0e5c09SChris Mason if (slot != nritems -1) { 1313d6025579SChris Mason btrfs_memmove(root, node, node->ptrs + slot, 1314d6025579SChris Mason node->ptrs + slot + 1, 1315d6025579SChris Mason sizeof(struct btrfs_key_ptr) * 1316d6025579SChris Mason (nritems - slot - 1)); 1317be0e5c09SChris Mason } 13187518a238SChris Mason nritems--; 13197518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 13207518a238SChris Mason if (nritems == 0 && parent == root->node) { 1321e20d96d6SChris Mason struct btrfs_header *header = btrfs_buffer_header(root->node); 1322e20d96d6SChris Mason BUG_ON(btrfs_header_level(header) != 1); 1323eb60ceacSChris Mason /* just turn the root into a leaf and break */ 1324e20d96d6SChris Mason btrfs_set_header_level(header, 0); 1325bb803951SChris Mason } else if (slot == 0) { 1326e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, 1327123abc88SChris Mason level + 1); 13280f70abe2SChris Mason if (wret) 13290f70abe2SChris Mason ret = wret; 1330be0e5c09SChris Mason } 1331d6025579SChris Mason btrfs_mark_buffer_dirty(parent); 1332aa5d6bedSChris Mason return ret; 1333be0e5c09SChris Mason } 1334be0e5c09SChris Mason 133574123bd7SChris Mason /* 133674123bd7SChris Mason * delete the item at the leaf level in path. If that empties 133774123bd7SChris Mason * the leaf, remove it from the tree 133874123bd7SChris Mason */ 1339e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1340e089f05cSChris Mason struct btrfs_path *path) 1341be0e5c09SChris Mason { 1342be0e5c09SChris Mason int slot; 1343234b63a0SChris Mason struct btrfs_leaf *leaf; 1344e20d96d6SChris Mason struct buffer_head *leaf_buf; 1345be0e5c09SChris Mason int doff; 1346be0e5c09SChris Mason int dsize; 1347aa5d6bedSChris Mason int ret = 0; 1348aa5d6bedSChris Mason int wret; 13497518a238SChris Mason u32 nritems; 1350be0e5c09SChris Mason 1351eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1352e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 13534920c9acSChris Mason slot = path->slots[0]; 13540783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 13550783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 13567518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1357be0e5c09SChris Mason 13587518a238SChris Mason if (slot != nritems - 1) { 1359be0e5c09SChris Mason int i; 1360123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 1361d6025579SChris Mason btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) + 1362d6025579SChris Mason data_end + dsize, 1363123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 1364be0e5c09SChris Mason doff - data_end); 13650783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 1366123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 13670783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 13680783fcfcSChris Mason } 1369d6025579SChris Mason btrfs_memmove(root, leaf, leaf->items + slot, 1370d6025579SChris Mason leaf->items + slot + 1, 13710783fcfcSChris Mason sizeof(struct btrfs_item) * 13727518a238SChris Mason (nritems - slot - 1)); 1373be0e5c09SChris Mason } 13747518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 13757518a238SChris Mason nritems--; 137674123bd7SChris Mason /* delete the leaf if we've emptied it */ 13777518a238SChris Mason if (nritems == 0) { 1378eb60ceacSChris Mason if (leaf_buf == root->node) { 13797518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 13809a8dd150SChris Mason } else { 1381e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1382d6025579SChris Mason wait_on_buffer(leaf_buf); 1383e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 1384aa5d6bedSChris Mason if (wret) 1385aa5d6bedSChris Mason ret = wret; 1386e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 1387e20d96d6SChris Mason leaf_buf->b_blocknr, 1, 1); 13880f70abe2SChris Mason if (wret) 13890f70abe2SChris Mason ret = wret; 13909a8dd150SChris Mason } 1391be0e5c09SChris Mason } else { 13927518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1393aa5d6bedSChris Mason if (slot == 0) { 1394e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 1395aa5d6bedSChris Mason &leaf->items[0].key, 1); 1396aa5d6bedSChris Mason if (wret) 1397aa5d6bedSChris Mason ret = wret; 1398aa5d6bedSChris Mason } 1399aa5d6bedSChris Mason 140074123bd7SChris Mason /* delete the leaf if it is mostly empty */ 1401123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 1402be0e5c09SChris Mason /* push_leaf_left fixes the path. 1403be0e5c09SChris Mason * make sure the path still points to our leaf 1404be0e5c09SChris Mason * for possible call to del_ptr below 1405be0e5c09SChris Mason */ 14064920c9acSChris Mason slot = path->slots[1]; 1407e20d96d6SChris Mason get_bh(leaf_buf); 1408e089f05cSChris Mason wret = push_leaf_left(trans, root, path, 1); 1409aa5d6bedSChris Mason if (wret < 0) 1410aa5d6bedSChris Mason ret = wret; 1411f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 14127518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1413e089f05cSChris Mason wret = push_leaf_right(trans, root, path, 1); 1414aa5d6bedSChris Mason if (wret < 0) 1415aa5d6bedSChris Mason ret = wret; 1416aa5d6bedSChris Mason } 14177518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 1418e20d96d6SChris Mason u64 blocknr = leaf_buf->b_blocknr; 1419e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1420d6025579SChris Mason wait_on_buffer(leaf_buf); 1421e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 1422aa5d6bedSChris Mason if (wret) 1423aa5d6bedSChris Mason ret = wret; 1424234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1425e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1426e089f05cSChris Mason 1, 1); 14270f70abe2SChris Mason if (wret) 14280f70abe2SChris Mason ret = wret; 14295de08d7dSChris Mason } else { 1430d6025579SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 1431234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1432be0e5c09SChris Mason } 1433d5719762SChris Mason } else { 1434d6025579SChris Mason btrfs_mark_buffer_dirty(leaf_buf); 1435be0e5c09SChris Mason } 14369a8dd150SChris Mason } 1437aa5d6bedSChris Mason return ret; 14389a8dd150SChris Mason } 14399a8dd150SChris Mason 144097571fd0SChris Mason /* 144197571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 14420f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 14430f70abe2SChris Mason * returns < 0 on io errors. 144497571fd0SChris Mason */ 1445234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 1446d97e63b6SChris Mason { 1447d97e63b6SChris Mason int slot; 1448d97e63b6SChris Mason int level = 1; 1449d97e63b6SChris Mason u64 blocknr; 1450e20d96d6SChris Mason struct buffer_head *c; 1451e20d96d6SChris Mason struct btrfs_node *c_node; 1452e20d96d6SChris Mason struct buffer_head *next = NULL; 1453d97e63b6SChris Mason 1454234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 1455d97e63b6SChris Mason if (!path->nodes[level]) 14560f70abe2SChris Mason return 1; 1457d97e63b6SChris Mason slot = path->slots[level] + 1; 1458d97e63b6SChris Mason c = path->nodes[level]; 1459e20d96d6SChris Mason c_node = btrfs_buffer_node(c); 1460e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&c_node->header)) { 1461d97e63b6SChris Mason level++; 1462d97e63b6SChris Mason continue; 1463d97e63b6SChris Mason } 1464e20d96d6SChris Mason blocknr = btrfs_node_blockptr(c_node, slot); 1465cfaa7295SChris Mason if (next) 1466234b63a0SChris Mason btrfs_block_release(root, next); 1467d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1468d97e63b6SChris Mason break; 1469d97e63b6SChris Mason } 1470d97e63b6SChris Mason path->slots[level] = slot; 1471d97e63b6SChris Mason while(1) { 1472d97e63b6SChris Mason level--; 1473d97e63b6SChris Mason c = path->nodes[level]; 1474234b63a0SChris Mason btrfs_block_release(root, c); 1475d97e63b6SChris Mason path->nodes[level] = next; 1476d97e63b6SChris Mason path->slots[level] = 0; 1477d97e63b6SChris Mason if (!level) 1478d97e63b6SChris Mason break; 14791d4f8a0cSChris Mason next = read_tree_block(root, 1480e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(next), 0)); 1481d97e63b6SChris Mason } 1482d97e63b6SChris Mason return 0; 1483d97e63b6SChris Mason } 1484