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 19234b63a0SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 20be0e5c09SChris Mason { 21be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 22be0e5c09SChris Mason } 23be0e5c09SChris Mason 24234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 25eb60ceacSChris Mason { 26eb60ceacSChris Mason int i; 27234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 28eb60ceacSChris Mason if (!p->nodes[i]) 29eb60ceacSChris Mason break; 30234b63a0SChris Mason btrfs_block_release(root, p->nodes[i]); 31eb60ceacSChris Mason } 32aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 33eb60ceacSChris Mason } 34eb60ceacSChris Mason 35e089f05cSChris Mason static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 36e20d96d6SChris Mason *root, struct buffer_head *buf, struct buffer_head 37e20d96d6SChris Mason *parent, int parent_slot, struct buffer_head 38e089f05cSChris Mason **cow_ret) 3902217ed2SChris Mason { 40e20d96d6SChris Mason struct buffer_head *cow; 41e20d96d6SChris Mason struct btrfs_node *cow_node; 4202217ed2SChris Mason 437f5c1516SChris Mason if (btrfs_header_generation(btrfs_buffer_header(buf)) == 447f5c1516SChris Mason trans->transid) { 4502217ed2SChris Mason *cow_ret = buf; 4602217ed2SChris Mason return 0; 4702217ed2SChris Mason } 48e089f05cSChris Mason cow = btrfs_alloc_free_block(trans, root); 49e20d96d6SChris Mason cow_node = btrfs_buffer_node(cow); 50e20d96d6SChris Mason memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize); 51e20d96d6SChris Mason btrfs_set_header_blocknr(&cow_node->header, cow->b_blocknr); 527f5c1516SChris Mason btrfs_set_header_generation(&cow_node->header, trans->transid); 5302217ed2SChris Mason *cow_ret = cow; 54d5719762SChris Mason mark_buffer_dirty(cow); 55e089f05cSChris Mason btrfs_inc_ref(trans, root, buf); 5602217ed2SChris Mason if (buf == root->node) { 5702217ed2SChris Mason root->node = cow; 58e20d96d6SChris Mason get_bh(cow); 59a28ec197SChris Mason if (buf != root->commit_root) 60e20d96d6SChris Mason btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1); 61234b63a0SChris Mason btrfs_block_release(root, buf); 6202217ed2SChris Mason } else { 63e20d96d6SChris Mason btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot, 64e20d96d6SChris Mason cow->b_blocknr); 65d5719762SChris Mason mark_buffer_dirty(parent); 66e20d96d6SChris Mason btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1); 6702217ed2SChris Mason } 68234b63a0SChris Mason btrfs_block_release(root, buf); 6902217ed2SChris Mason return 0; 7002217ed2SChris Mason } 7102217ed2SChris Mason 7274123bd7SChris Mason /* 7374123bd7SChris Mason * The leaf data grows from end-to-front in the node. 7474123bd7SChris Mason * this returns the address of the start of the last item, 7574123bd7SChris Mason * which is the stop of the leaf data stack 7674123bd7SChris Mason */ 77123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 78123abc88SChris Mason struct btrfs_leaf *leaf) 79be0e5c09SChris Mason { 807518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 81be0e5c09SChris Mason if (nr == 0) 82123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 830783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 84be0e5c09SChris Mason } 85be0e5c09SChris Mason 8674123bd7SChris Mason /* 8774123bd7SChris Mason * The space between the end of the leaf items and 8874123bd7SChris Mason * the start of the leaf data. IOW, how much room 8974123bd7SChris Mason * the leaf has left for both items and data 9074123bd7SChris Mason */ 91123abc88SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) 92be0e5c09SChris Mason { 93123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 947518a238SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 95be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 96123abc88SChris Mason return (char *)(btrfs_leaf_data(leaf) + data_end) - (char *)items_end; 97be0e5c09SChris Mason } 98be0e5c09SChris Mason 9974123bd7SChris Mason /* 10074123bd7SChris Mason * compare two keys in a memcmp fashion 10174123bd7SChris Mason */ 1029aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 103be0e5c09SChris Mason { 104e2fa7227SChris Mason struct btrfs_key k1; 105e2fa7227SChris Mason 106e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 107e2fa7227SChris Mason 108e2fa7227SChris Mason if (k1.objectid > k2->objectid) 109be0e5c09SChris Mason return 1; 110e2fa7227SChris Mason if (k1.objectid < k2->objectid) 111be0e5c09SChris Mason return -1; 11262e2749eSChris Mason if (k1.flags > k2->flags) 11362e2749eSChris Mason return 1; 11462e2749eSChris Mason if (k1.flags < k2->flags) 11562e2749eSChris Mason return -1; 116a8a2ee0cSChris Mason if (k1.offset > k2->offset) 117a8a2ee0cSChris Mason return 1; 118a8a2ee0cSChris Mason if (k1.offset < k2->offset) 119a8a2ee0cSChris Mason return -1; 120be0e5c09SChris Mason return 0; 121be0e5c09SChris Mason } 12274123bd7SChris Mason 123123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 124123abc88SChris Mason int level) 125aa5d6bedSChris Mason { 126aa5d6bedSChris Mason int i; 127234b63a0SChris Mason struct btrfs_node *parent = NULL; 128e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 129aa5d6bedSChris Mason int parent_slot; 1307518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 131aa5d6bedSChris Mason 132aa5d6bedSChris Mason if (path->nodes[level + 1]) 133e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 134aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1357518a238SChris Mason BUG_ON(nritems == 0); 1367518a238SChris Mason if (parent) { 137e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 138123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 139123abc88SChris Mason BUG_ON(memcmp(parent_key, &node->ptrs[0].key, 140e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1411d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1427518a238SChris Mason btrfs_header_blocknr(&node->header)); 143aa5d6bedSChris Mason } 144123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 1457518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 146e2fa7227SChris Mason struct btrfs_key cpukey; 147123abc88SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key); 148123abc88SChris Mason BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0); 149aa5d6bedSChris Mason } 150aa5d6bedSChris Mason return 0; 151aa5d6bedSChris Mason } 152aa5d6bedSChris Mason 153123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 154123abc88SChris Mason int level) 155aa5d6bedSChris Mason { 156aa5d6bedSChris Mason int i; 157e20d96d6SChris Mason struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]); 158234b63a0SChris Mason struct btrfs_node *parent = NULL; 159aa5d6bedSChris Mason int parent_slot; 1607518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 161aa5d6bedSChris Mason 162aa5d6bedSChris Mason if (path->nodes[level + 1]) 163e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 164aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 165123abc88SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 1667518a238SChris Mason 1677518a238SChris Mason if (nritems == 0) 1687518a238SChris Mason return 0; 1697518a238SChris Mason 1707518a238SChris Mason if (parent) { 171e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 172123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 173aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 174e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1751d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1767518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 177aa5d6bedSChris Mason } 1787518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 179e2fa7227SChris Mason struct btrfs_key cpukey; 180e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); 181aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 182e2fa7227SChris Mason &cpukey) >= 0); 1830783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) != 1840783fcfcSChris Mason btrfs_item_end(leaf->items + i + 1)); 185aa5d6bedSChris Mason if (i == 0) { 1860783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) + 1870783fcfcSChris Mason btrfs_item_size(leaf->items + i) != 188123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)); 189aa5d6bedSChris Mason } 190aa5d6bedSChris Mason } 191aa5d6bedSChris Mason return 0; 192aa5d6bedSChris Mason } 193aa5d6bedSChris Mason 194123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 195123abc88SChris Mason int level) 196aa5d6bedSChris Mason { 197aa5d6bedSChris Mason if (level == 0) 198123abc88SChris Mason return check_leaf(root, path, level); 199123abc88SChris Mason return check_node(root, path, level); 200aa5d6bedSChris Mason } 201aa5d6bedSChris Mason 20274123bd7SChris Mason /* 20374123bd7SChris Mason * search for key in the array p. items p are item_size apart 20474123bd7SChris Mason * and there are 'max' items in p 20574123bd7SChris Mason * the slot in the array is returned via slot, and it points to 20674123bd7SChris Mason * the place where you would insert key if it is not found in 20774123bd7SChris Mason * the array. 20874123bd7SChris Mason * 20974123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 21074123bd7SChris Mason */ 2119aca1d51SChris Mason static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 212be0e5c09SChris Mason int max, int *slot) 213be0e5c09SChris Mason { 214be0e5c09SChris Mason int low = 0; 215be0e5c09SChris Mason int high = max; 216be0e5c09SChris Mason int mid; 217be0e5c09SChris Mason int ret; 218e2fa7227SChris Mason struct btrfs_disk_key *tmp; 219be0e5c09SChris Mason 220be0e5c09SChris Mason while(low < high) { 221be0e5c09SChris Mason mid = (low + high) / 2; 222e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 223be0e5c09SChris Mason ret = comp_keys(tmp, key); 224be0e5c09SChris Mason 225be0e5c09SChris Mason if (ret < 0) 226be0e5c09SChris Mason low = mid + 1; 227be0e5c09SChris Mason else if (ret > 0) 228be0e5c09SChris Mason high = mid; 229be0e5c09SChris Mason else { 230be0e5c09SChris Mason *slot = mid; 231be0e5c09SChris Mason return 0; 232be0e5c09SChris Mason } 233be0e5c09SChris Mason } 234be0e5c09SChris Mason *slot = low; 235be0e5c09SChris Mason return 1; 236be0e5c09SChris Mason } 237be0e5c09SChris Mason 23897571fd0SChris Mason /* 23997571fd0SChris Mason * simple bin_search frontend that does the right thing for 24097571fd0SChris Mason * leaves vs nodes 24197571fd0SChris Mason */ 2429aca1d51SChris Mason static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) 243be0e5c09SChris Mason { 2447518a238SChris Mason if (btrfs_is_leaf(c)) { 245234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 2460783fcfcSChris Mason return generic_bin_search((void *)l->items, 2470783fcfcSChris Mason sizeof(struct btrfs_item), 2487518a238SChris Mason key, btrfs_header_nritems(&c->header), 2497518a238SChris Mason slot); 250be0e5c09SChris Mason } else { 251123abc88SChris Mason return generic_bin_search((void *)c->ptrs, 252123abc88SChris Mason sizeof(struct btrfs_key_ptr), 2537518a238SChris Mason key, btrfs_header_nritems(&c->header), 2547518a238SChris Mason slot); 255be0e5c09SChris Mason } 256be0e5c09SChris Mason return -1; 257be0e5c09SChris Mason } 258be0e5c09SChris Mason 259e20d96d6SChris Mason static struct buffer_head *read_node_slot(struct btrfs_root *root, 260e20d96d6SChris Mason struct buffer_head *parent_buf, 261bb803951SChris Mason int slot) 262bb803951SChris Mason { 263e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(parent_buf); 264bb803951SChris Mason if (slot < 0) 265bb803951SChris Mason return NULL; 2667518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 267bb803951SChris Mason return NULL; 2681d4f8a0cSChris Mason return read_tree_block(root, btrfs_node_blockptr(node, slot)); 269bb803951SChris Mason } 270bb803951SChris Mason 271e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 272e089f05cSChris Mason *root, struct btrfs_path *path, int level) 273bb803951SChris Mason { 274e20d96d6SChris Mason struct buffer_head *right_buf; 275e20d96d6SChris Mason struct buffer_head *mid_buf; 276e20d96d6SChris Mason struct buffer_head *left_buf; 277e20d96d6SChris Mason struct buffer_head *parent_buf = NULL; 278234b63a0SChris Mason struct btrfs_node *right = NULL; 279234b63a0SChris Mason struct btrfs_node *mid; 280234b63a0SChris Mason struct btrfs_node *left = NULL; 281234b63a0SChris Mason struct btrfs_node *parent = NULL; 282bb803951SChris Mason int ret = 0; 283bb803951SChris Mason int wret; 284bb803951SChris Mason int pslot; 285bb803951SChris Mason int orig_slot = path->slots[level]; 28679f95c82SChris Mason u64 orig_ptr; 287bb803951SChris Mason 288bb803951SChris Mason if (level == 0) 289bb803951SChris Mason return 0; 290bb803951SChris Mason 291bb803951SChris Mason mid_buf = path->nodes[level]; 292e20d96d6SChris Mason mid = btrfs_buffer_node(mid_buf); 2931d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 29479f95c82SChris Mason 295234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 296bb803951SChris Mason parent_buf = path->nodes[level + 1]; 297bb803951SChris Mason pslot = path->slots[level + 1]; 298bb803951SChris Mason 29940689478SChris Mason /* 30040689478SChris Mason * deal with the case where there is only one pointer in the root 30140689478SChris Mason * by promoting the node below to a root 30240689478SChris Mason */ 303bb803951SChris Mason if (!parent_buf) { 304e20d96d6SChris Mason struct buffer_head *child; 305e20d96d6SChris Mason u64 blocknr = mid_buf->b_blocknr; 306bb803951SChris Mason 3077518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 308bb803951SChris Mason return 0; 309bb803951SChris Mason 310bb803951SChris Mason /* promote the child to a root */ 311bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 312bb803951SChris Mason BUG_ON(!child); 313bb803951SChris Mason root->node = child; 314bb803951SChris Mason path->nodes[level] = NULL; 315bb803951SChris Mason /* once for the path */ 316234b63a0SChris Mason btrfs_block_release(root, mid_buf); 317bb803951SChris Mason /* once for the root ptr */ 318234b63a0SChris Mason btrfs_block_release(root, mid_buf); 319e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 320e089f05cSChris Mason return btrfs_free_extent(trans, root, blocknr, 1, 1); 321bb803951SChris Mason } 322e20d96d6SChris Mason parent = btrfs_buffer_node(parent_buf); 323bb803951SChris Mason 324123abc88SChris Mason if (btrfs_header_nritems(&mid->header) > 325123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 326bb803951SChris Mason return 0; 327bb803951SChris Mason 328bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 329bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 33079f95c82SChris Mason 33179f95c82SChris Mason /* first, try to make some room in the middle buffer */ 332bb803951SChris Mason if (left_buf) { 333e089f05cSChris Mason btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1, 334e089f05cSChris Mason &left_buf); 335e20d96d6SChris Mason left = btrfs_buffer_node(left_buf); 3367518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 337e089f05cSChris Mason wret = push_node_left(trans, root, left_buf, mid_buf); 33879f95c82SChris Mason if (wret < 0) 33979f95c82SChris Mason ret = wret; 340bb803951SChris Mason } 34179f95c82SChris Mason 34279f95c82SChris Mason /* 34379f95c82SChris Mason * then try to empty the right most buffer into the middle 34479f95c82SChris Mason */ 345bb803951SChris Mason if (right_buf) { 346e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1, 347e089f05cSChris Mason &right_buf); 348e20d96d6SChris Mason right = btrfs_buffer_node(right_buf); 349e089f05cSChris Mason wret = push_node_left(trans, root, mid_buf, right_buf); 35079f95c82SChris Mason if (wret < 0) 35179f95c82SChris Mason ret = wret; 3527518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 353e20d96d6SChris Mason u64 blocknr = right_buf->b_blocknr; 354234b63a0SChris Mason btrfs_block_release(root, right_buf); 355e089f05cSChris Mason clean_tree_block(trans, root, right_buf); 356bb803951SChris Mason right_buf = NULL; 357bb803951SChris Mason right = NULL; 358e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 359e089f05cSChris Mason 1); 360bb803951SChris Mason if (wret) 361bb803951SChris Mason ret = wret; 362e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 363bb803951SChris Mason if (wret) 364bb803951SChris Mason ret = wret; 365bb803951SChris Mason } else { 366123abc88SChris Mason memcpy(&parent->ptrs[pslot + 1].key, 367123abc88SChris Mason &right->ptrs[0].key, 368e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 369d5719762SChris Mason mark_buffer_dirty(parent_buf); 370bb803951SChris Mason } 371bb803951SChris Mason } 3727518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 37379f95c82SChris Mason /* 37479f95c82SChris Mason * we're not allowed to leave a node with one item in the 37579f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 37679f95c82SChris Mason * could try to delete the only pointer in this node. 37779f95c82SChris Mason * So, pull some keys from the left. 37879f95c82SChris Mason * There has to be a left pointer at this point because 37979f95c82SChris Mason * otherwise we would have pulled some pointers from the 38079f95c82SChris Mason * right 38179f95c82SChris Mason */ 38279f95c82SChris Mason BUG_ON(!left_buf); 383e089f05cSChris Mason wret = balance_node_right(trans, root, mid_buf, left_buf); 38479f95c82SChris Mason if (wret < 0) 38579f95c82SChris Mason ret = wret; 38679f95c82SChris Mason BUG_ON(wret == 1); 38779f95c82SChris Mason } 3887518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 38979f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 390e20d96d6SChris Mason u64 blocknr = mid_buf->b_blocknr; 391234b63a0SChris Mason btrfs_block_release(root, mid_buf); 392e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 393bb803951SChris Mason mid_buf = NULL; 394bb803951SChris Mason mid = NULL; 395e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 396bb803951SChris Mason if (wret) 397bb803951SChris Mason ret = wret; 398e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 399bb803951SChris Mason if (wret) 400bb803951SChris Mason ret = wret; 40179f95c82SChris Mason } else { 40279f95c82SChris Mason /* update the parent key to reflect our changes */ 403123abc88SChris Mason memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key, 404e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 405d5719762SChris Mason mark_buffer_dirty(parent_buf); 40679f95c82SChris Mason } 407bb803951SChris Mason 40879f95c82SChris Mason /* update the path */ 409bb803951SChris Mason if (left_buf) { 4107518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 411e20d96d6SChris Mason get_bh(left_buf); 412bb803951SChris Mason path->nodes[level] = left_buf; 413bb803951SChris Mason path->slots[level + 1] -= 1; 414bb803951SChris Mason path->slots[level] = orig_slot; 415bb803951SChris Mason if (mid_buf) 416234b63a0SChris Mason btrfs_block_release(root, mid_buf); 417bb803951SChris Mason } else { 4187518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 419bb803951SChris Mason path->slots[level] = orig_slot; 420bb803951SChris Mason } 421bb803951SChris Mason } 42279f95c82SChris Mason /* double check we haven't messed things up */ 423123abc88SChris Mason check_block(root, path, level); 424e20d96d6SChris Mason if (orig_ptr != 425e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]), 4261d4f8a0cSChris Mason path->slots[level])) 42779f95c82SChris Mason BUG(); 428bb803951SChris Mason 429bb803951SChris Mason if (right_buf) 430234b63a0SChris Mason btrfs_block_release(root, right_buf); 431bb803951SChris Mason if (left_buf) 432234b63a0SChris Mason btrfs_block_release(root, left_buf); 433bb803951SChris Mason return ret; 434bb803951SChris Mason } 435bb803951SChris Mason 43674123bd7SChris Mason /* 43774123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 43874123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 43974123bd7SChris Mason * level of the path (level 0) 44074123bd7SChris Mason * 44174123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 442aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 443aa5d6bedSChris Mason * search a negative error number is returned. 44497571fd0SChris Mason * 44597571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 44697571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 44797571fd0SChris Mason * possible) 44874123bd7SChris Mason */ 449e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 450e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 451e089f05cSChris Mason ins_len, int cow) 452be0e5c09SChris Mason { 453e20d96d6SChris Mason struct buffer_head *b; 454e20d96d6SChris Mason struct buffer_head *cow_buf; 455234b63a0SChris Mason struct btrfs_node *c; 456be0e5c09SChris Mason int slot; 457be0e5c09SChris Mason int ret; 458be0e5c09SChris Mason int level; 4595c680ed6SChris Mason 460bb803951SChris Mason again: 461bb803951SChris Mason b = root->node; 462e20d96d6SChris Mason get_bh(b); 463eb60ceacSChris Mason while (b) { 464e20d96d6SChris Mason c = btrfs_buffer_node(b); 465e20d96d6SChris Mason level = btrfs_header_level(&c->header); 46602217ed2SChris Mason if (cow) { 46702217ed2SChris Mason int wret; 468e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 469e20d96d6SChris Mason p->nodes[level + 1], 470e20d96d6SChris Mason p->slots[level + 1], 471e089f05cSChris Mason &cow_buf); 47202217ed2SChris Mason b = cow_buf; 47302217ed2SChris Mason } 47402217ed2SChris Mason BUG_ON(!cow && ins_len); 475e20d96d6SChris Mason c = btrfs_buffer_node(b); 476eb60ceacSChris Mason p->nodes[level] = b; 477123abc88SChris Mason ret = check_block(root, p, level); 478aa5d6bedSChris Mason if (ret) 479aa5d6bedSChris Mason return -1; 480be0e5c09SChris Mason ret = bin_search(c, key, &slot); 4817518a238SChris Mason if (!btrfs_is_leaf(c)) { 482be0e5c09SChris Mason if (ret && slot > 0) 483be0e5c09SChris Mason slot -= 1; 484be0e5c09SChris Mason p->slots[level] = slot; 4857518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 486123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root)) { 487e089f05cSChris Mason int sret = split_node(trans, root, p, level); 4885c680ed6SChris Mason BUG_ON(sret > 0); 4895c680ed6SChris Mason if (sret) 4905c680ed6SChris Mason return sret; 4915c680ed6SChris Mason b = p->nodes[level]; 492e20d96d6SChris Mason c = btrfs_buffer_node(b); 4935c680ed6SChris Mason slot = p->slots[level]; 494bb803951SChris Mason } else if (ins_len < 0) { 495e089f05cSChris Mason int sret = balance_level(trans, root, p, 496e089f05cSChris Mason level); 497bb803951SChris Mason if (sret) 498bb803951SChris Mason return sret; 499bb803951SChris Mason b = p->nodes[level]; 500bb803951SChris Mason if (!b) 501bb803951SChris Mason goto again; 502e20d96d6SChris Mason c = btrfs_buffer_node(b); 503bb803951SChris Mason slot = p->slots[level]; 5047518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 5055c680ed6SChris Mason } 5061d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 507be0e5c09SChris Mason } else { 508234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 509be0e5c09SChris Mason p->slots[level] = slot; 510123abc88SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 5110783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 512e089f05cSChris Mason int sret = split_leaf(trans, root, p, ins_len); 5135c680ed6SChris Mason BUG_ON(sret > 0); 5145c680ed6SChris Mason if (sret) 5155c680ed6SChris Mason return sret; 5165c680ed6SChris Mason } 517be0e5c09SChris Mason return ret; 518be0e5c09SChris Mason } 519be0e5c09SChris Mason } 520aa5d6bedSChris Mason return 1; 521be0e5c09SChris Mason } 522be0e5c09SChris Mason 52374123bd7SChris Mason /* 52474123bd7SChris Mason * adjust the pointers going up the tree, starting at level 52574123bd7SChris Mason * making sure the right key of each node is points to 'key'. 52674123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 52774123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 52874123bd7SChris Mason * higher levels 529aa5d6bedSChris Mason * 530aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 531aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 53274123bd7SChris Mason */ 533e089f05cSChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root 534e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 535e089f05cSChris Mason *key, int level) 536be0e5c09SChris Mason { 537be0e5c09SChris Mason int i; 538aa5d6bedSChris Mason int ret = 0; 539234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 540234b63a0SChris Mason struct btrfs_node *t; 541be0e5c09SChris Mason int tslot = path->slots[i]; 542eb60ceacSChris Mason if (!path->nodes[i]) 543be0e5c09SChris Mason break; 544e20d96d6SChris Mason t = btrfs_buffer_node(path->nodes[i]); 545123abc88SChris Mason memcpy(&t->ptrs[tslot].key, key, sizeof(*key)); 546d5719762SChris Mason mark_buffer_dirty(path->nodes[i]); 547be0e5c09SChris Mason if (tslot != 0) 548be0e5c09SChris Mason break; 549be0e5c09SChris Mason } 550aa5d6bedSChris Mason return ret; 551be0e5c09SChris Mason } 552be0e5c09SChris Mason 55374123bd7SChris Mason /* 55474123bd7SChris Mason * try to push data from one node into the next node left in the 55579f95c82SChris Mason * tree. 556aa5d6bedSChris Mason * 557aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 558aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 55974123bd7SChris Mason */ 560e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 561e20d96d6SChris Mason *root, struct buffer_head *dst_buf, struct 562e20d96d6SChris Mason buffer_head *src_buf) 563be0e5c09SChris Mason { 564e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 565e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 566be0e5c09SChris Mason int push_items = 0; 567bb803951SChris Mason int src_nritems; 568bb803951SChris Mason int dst_nritems; 569aa5d6bedSChris Mason int ret = 0; 570be0e5c09SChris Mason 5717518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5727518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 573123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 574eb60ceacSChris Mason if (push_items <= 0) { 575be0e5c09SChris Mason return 1; 576eb60ceacSChris Mason } 577be0e5c09SChris Mason 578be0e5c09SChris Mason if (src_nritems < push_items) 579be0e5c09SChris Mason push_items = src_nritems; 58079f95c82SChris Mason 581123abc88SChris Mason memcpy(dst->ptrs + dst_nritems, src->ptrs, 582123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 583bb803951SChris Mason if (push_items < src_nritems) { 584123abc88SChris Mason memmove(src->ptrs, src->ptrs + push_items, 585e2fa7227SChris Mason (src_nritems - push_items) * 586123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 587bb803951SChris Mason } 5887518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 5897518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 590d5719762SChris Mason mark_buffer_dirty(src_buf); 591d5719762SChris Mason mark_buffer_dirty(dst_buf); 592bb803951SChris Mason return ret; 593be0e5c09SChris Mason } 594be0e5c09SChris Mason 59597571fd0SChris Mason /* 59679f95c82SChris Mason * try to push data from one node into the next node right in the 59779f95c82SChris Mason * tree. 59879f95c82SChris Mason * 59979f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 60079f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 60179f95c82SChris Mason * 60279f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 60379f95c82SChris Mason */ 604e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 605e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 606e20d96d6SChris Mason struct buffer_head *src_buf) 60779f95c82SChris Mason { 608e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 609e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 61079f95c82SChris Mason int push_items = 0; 61179f95c82SChris Mason int max_push; 61279f95c82SChris Mason int src_nritems; 61379f95c82SChris Mason int dst_nritems; 61479f95c82SChris Mason int ret = 0; 61579f95c82SChris Mason 6167518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6177518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 618123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 61979f95c82SChris Mason if (push_items <= 0) { 62079f95c82SChris Mason return 1; 62179f95c82SChris Mason } 62279f95c82SChris Mason 62379f95c82SChris Mason max_push = src_nritems / 2 + 1; 62479f95c82SChris Mason /* don't try to empty the node */ 62579f95c82SChris Mason if (max_push > src_nritems) 62679f95c82SChris Mason return 1; 62779f95c82SChris Mason if (max_push < push_items) 62879f95c82SChris Mason push_items = max_push; 62979f95c82SChris Mason 630123abc88SChris Mason memmove(dst->ptrs + push_items, dst->ptrs, 631123abc88SChris Mason dst_nritems * sizeof(struct btrfs_key_ptr)); 632123abc88SChris Mason memcpy(dst->ptrs, src->ptrs + src_nritems - push_items, 633123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 63479f95c82SChris Mason 6357518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6367518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 63779f95c82SChris Mason 638d5719762SChris Mason mark_buffer_dirty(src_buf); 639d5719762SChris Mason mark_buffer_dirty(dst_buf); 64079f95c82SChris Mason return ret; 64179f95c82SChris Mason } 64279f95c82SChris Mason 64379f95c82SChris Mason /* 64497571fd0SChris Mason * helper function to insert a new root level in the tree. 64597571fd0SChris Mason * A new node is allocated, and a single item is inserted to 64697571fd0SChris Mason * point to the existing root 647aa5d6bedSChris Mason * 648aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 64997571fd0SChris Mason */ 650e089f05cSChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root 651e089f05cSChris Mason *root, struct btrfs_path *path, int level) 65274123bd7SChris Mason { 653e20d96d6SChris Mason struct buffer_head *t; 654234b63a0SChris Mason struct btrfs_node *lower; 655234b63a0SChris Mason struct btrfs_node *c; 656e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 6575c680ed6SChris Mason 6585c680ed6SChris Mason BUG_ON(path->nodes[level]); 6595c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 6605c680ed6SChris Mason 661e089f05cSChris Mason t = btrfs_alloc_free_block(trans, root); 662e20d96d6SChris Mason c = btrfs_buffer_node(t); 663123abc88SChris Mason memset(c, 0, root->blocksize); 6647518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 6657518a238SChris Mason btrfs_set_header_level(&c->header, level); 666e20d96d6SChris Mason btrfs_set_header_blocknr(&c->header, t->b_blocknr); 6677f5c1516SChris Mason btrfs_set_header_generation(&c->header, trans->transid); 6687518a238SChris Mason btrfs_set_header_parentid(&c->header, 669e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 670e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level-1]); 6717518a238SChris Mason if (btrfs_is_leaf(lower)) 672234b63a0SChris Mason lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 67374123bd7SChris Mason else 674123abc88SChris Mason lower_key = &lower->ptrs[0].key; 675123abc88SChris Mason memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key)); 676e20d96d6SChris Mason btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->b_blocknr); 677d5719762SChris Mason 678d5719762SChris Mason mark_buffer_dirty(t); 679d5719762SChris Mason 680cfaa7295SChris Mason /* the super has an extra ref to root->node */ 681234b63a0SChris Mason btrfs_block_release(root, root->node); 68274123bd7SChris Mason root->node = t; 683e20d96d6SChris Mason get_bh(t); 68474123bd7SChris Mason path->nodes[level] = t; 68574123bd7SChris Mason path->slots[level] = 0; 68674123bd7SChris Mason return 0; 68774123bd7SChris Mason } 6885c680ed6SChris Mason 6895c680ed6SChris Mason /* 6905c680ed6SChris Mason * worker function to insert a single pointer in a node. 6915c680ed6SChris Mason * the node should have enough room for the pointer already 69297571fd0SChris Mason * 6935c680ed6SChris Mason * slot and level indicate where you want the key to go, and 6945c680ed6SChris Mason * blocknr is the block the key points to. 695aa5d6bedSChris Mason * 696aa5d6bedSChris Mason * returns zero on success and < 0 on any error 6975c680ed6SChris Mason */ 698e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 699e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 700e089f05cSChris Mason *key, u64 blocknr, int slot, int level) 7015c680ed6SChris Mason { 702234b63a0SChris Mason struct btrfs_node *lower; 7035c680ed6SChris Mason int nritems; 7045c680ed6SChris Mason 7055c680ed6SChris Mason BUG_ON(!path->nodes[level]); 706e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level]); 7077518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 70874123bd7SChris Mason if (slot > nritems) 70974123bd7SChris Mason BUG(); 710123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 71174123bd7SChris Mason BUG(); 71274123bd7SChris Mason if (slot != nritems) { 713123abc88SChris Mason memmove(lower->ptrs + slot + 1, lower->ptrs + slot, 714123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 71574123bd7SChris Mason } 716123abc88SChris Mason memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key)); 7171d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 7187518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 719d5719762SChris Mason mark_buffer_dirty(path->nodes[level]); 72074123bd7SChris Mason return 0; 72174123bd7SChris Mason } 72274123bd7SChris Mason 72397571fd0SChris Mason /* 72497571fd0SChris Mason * split the node at the specified level in path in two. 72597571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 72697571fd0SChris Mason * 72797571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 72897571fd0SChris Mason * left and right, if either one works, it returns right away. 729aa5d6bedSChris Mason * 730aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 73197571fd0SChris Mason */ 732e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 733e089f05cSChris Mason *root, struct btrfs_path *path, int level) 734be0e5c09SChris Mason { 735e20d96d6SChris Mason struct buffer_head *t; 736234b63a0SChris Mason struct btrfs_node *c; 737e20d96d6SChris Mason struct buffer_head *split_buffer; 738234b63a0SChris Mason struct btrfs_node *split; 739be0e5c09SChris Mason int mid; 7405c680ed6SChris Mason int ret; 741aa5d6bedSChris Mason int wret; 7427518a238SChris Mason u32 c_nritems; 743be0e5c09SChris Mason 7445c680ed6SChris Mason t = path->nodes[level]; 745e20d96d6SChris Mason c = btrfs_buffer_node(t); 7465c680ed6SChris Mason if (t == root->node) { 7475c680ed6SChris Mason /* trying to split the root, lets make a new one */ 748e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 7495c680ed6SChris Mason if (ret) 7505c680ed6SChris Mason return ret; 7515c680ed6SChris Mason } 7527518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 753e089f05cSChris Mason split_buffer = btrfs_alloc_free_block(trans, root); 754e20d96d6SChris Mason split = btrfs_buffer_node(split_buffer); 7557518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 756e20d96d6SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->b_blocknr); 7577f5c1516SChris Mason btrfs_set_header_generation(&split->header, trans->transid); 7587518a238SChris Mason btrfs_set_header_parentid(&split->header, 759e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 7607518a238SChris Mason mid = (c_nritems + 1) / 2; 761123abc88SChris Mason memcpy(split->ptrs, c->ptrs + mid, 762123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 7637518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7647518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 765aa5d6bedSChris Mason ret = 0; 766aa5d6bedSChris Mason 767d5719762SChris Mason mark_buffer_dirty(t); 768d5719762SChris Mason mark_buffer_dirty(split_buffer); 769e089f05cSChris Mason wret = insert_ptr(trans, root, path, &split->ptrs[0].key, 770e20d96d6SChris Mason split_buffer->b_blocknr, path->slots[level + 1] + 1, 771123abc88SChris Mason level + 1); 772aa5d6bedSChris Mason if (wret) 773aa5d6bedSChris Mason ret = wret; 774aa5d6bedSChris Mason 7755de08d7dSChris Mason if (path->slots[level] >= mid) { 7765c680ed6SChris Mason path->slots[level] -= mid; 777234b63a0SChris Mason btrfs_block_release(root, t); 7785c680ed6SChris Mason path->nodes[level] = split_buffer; 7795c680ed6SChris Mason path->slots[level + 1] += 1; 780eb60ceacSChris Mason } else { 781234b63a0SChris Mason btrfs_block_release(root, split_buffer); 782be0e5c09SChris Mason } 783aa5d6bedSChris Mason return ret; 784be0e5c09SChris Mason } 785be0e5c09SChris Mason 78674123bd7SChris Mason /* 78774123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 78874123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 78974123bd7SChris Mason * space used both by the item structs and the item data 79074123bd7SChris Mason */ 791234b63a0SChris Mason static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 792be0e5c09SChris Mason { 793be0e5c09SChris Mason int data_len; 794be0e5c09SChris Mason int end = start + nr - 1; 795be0e5c09SChris Mason 796be0e5c09SChris Mason if (!nr) 797be0e5c09SChris Mason return 0; 7980783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 7990783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 8000783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 801be0e5c09SChris Mason return data_len; 802be0e5c09SChris Mason } 803be0e5c09SChris Mason 80474123bd7SChris Mason /* 80500ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 80600ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 807aa5d6bedSChris Mason * 808aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 809aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 81000ec4c51SChris Mason */ 811e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 812e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 81300ec4c51SChris Mason { 814e20d96d6SChris Mason struct buffer_head *left_buf = path->nodes[0]; 815e20d96d6SChris Mason struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf); 816234b63a0SChris Mason struct btrfs_leaf *right; 817e20d96d6SChris Mason struct buffer_head *right_buf; 818e20d96d6SChris Mason struct buffer_head *upper; 819e20d96d6SChris Mason struct btrfs_node *upper_node; 82000ec4c51SChris Mason int slot; 82100ec4c51SChris Mason int i; 82200ec4c51SChris Mason int free_space; 82300ec4c51SChris Mason int push_space = 0; 82400ec4c51SChris Mason int push_items = 0; 8250783fcfcSChris Mason struct btrfs_item *item; 8267518a238SChris Mason u32 left_nritems; 8277518a238SChris Mason u32 right_nritems; 82800ec4c51SChris Mason 82900ec4c51SChris Mason slot = path->slots[1]; 83000ec4c51SChris Mason if (!path->nodes[1]) { 83100ec4c51SChris Mason return 1; 83200ec4c51SChris Mason } 83300ec4c51SChris Mason upper = path->nodes[1]; 834e20d96d6SChris Mason upper_node = btrfs_buffer_node(upper); 835e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&upper_node->header) - 1) { 83600ec4c51SChris Mason return 1; 83700ec4c51SChris Mason } 838e20d96d6SChris Mason right_buf = read_tree_block(root, 839e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1)); 840e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 841123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8420783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 843234b63a0SChris Mason btrfs_block_release(root, right_buf); 84400ec4c51SChris Mason return 1; 84500ec4c51SChris Mason } 84602217ed2SChris Mason /* cow and double check */ 847e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf); 848e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 849123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8500783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 851234b63a0SChris Mason btrfs_block_release(root, right_buf); 85202217ed2SChris Mason return 1; 85302217ed2SChris Mason } 85402217ed2SChris Mason 8557518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8567518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 85700ec4c51SChris Mason item = left->items + i; 85800ec4c51SChris Mason if (path->slots[0] == i) 85900ec4c51SChris Mason push_space += data_size + sizeof(*item); 8600783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8610783fcfcSChris Mason free_space) 86200ec4c51SChris Mason break; 86300ec4c51SChris Mason push_items++; 8640783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 86500ec4c51SChris Mason } 86600ec4c51SChris Mason if (push_items == 0) { 867234b63a0SChris Mason btrfs_block_release(root, right_buf); 86800ec4c51SChris Mason return 1; 86900ec4c51SChris Mason } 8707518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 87100ec4c51SChris Mason /* push left to right */ 8720783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 873123abc88SChris Mason push_space -= leaf_data_end(root, left); 87400ec4c51SChris Mason /* make room in the right data area */ 875123abc88SChris Mason memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) - 876123abc88SChris Mason push_space, btrfs_leaf_data(right) + leaf_data_end(root, right), 877123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right)); 87800ec4c51SChris Mason /* copy from the left data area */ 879123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space, 880123abc88SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), push_space); 88100ec4c51SChris Mason memmove(right->items + push_items, right->items, 8820783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 88300ec4c51SChris Mason /* copy the items from left to right */ 8847518a238SChris Mason memcpy(right->items, left->items + left_nritems - push_items, 8850783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 88600ec4c51SChris Mason 88700ec4c51SChris Mason /* update the item pointers */ 8887518a238SChris Mason right_nritems += push_items; 8897518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 890123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 8917518a238SChris Mason for (i = 0; i < right_nritems; i++) { 8920783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 8930783fcfcSChris Mason btrfs_item_size(right->items + i)); 8940783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 89500ec4c51SChris Mason } 8967518a238SChris Mason left_nritems -= push_items; 8977518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 89800ec4c51SChris Mason 899d5719762SChris Mason mark_buffer_dirty(left_buf); 900d5719762SChris Mason mark_buffer_dirty(right_buf); 901e20d96d6SChris Mason memcpy(&upper_node->ptrs[slot + 1].key, 902e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 903d5719762SChris Mason mark_buffer_dirty(upper); 90402217ed2SChris Mason 90500ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 9067518a238SChris Mason if (path->slots[0] >= left_nritems) { 9077518a238SChris Mason path->slots[0] -= left_nritems; 908234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 90900ec4c51SChris Mason path->nodes[0] = right_buf; 91000ec4c51SChris Mason path->slots[1] += 1; 91100ec4c51SChris Mason } else { 912234b63a0SChris Mason btrfs_block_release(root, right_buf); 91300ec4c51SChris Mason } 91400ec4c51SChris Mason return 0; 91500ec4c51SChris Mason } 91600ec4c51SChris Mason /* 91774123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 91874123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 91974123bd7SChris Mason */ 920e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 921e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 922be0e5c09SChris Mason { 923e20d96d6SChris Mason struct buffer_head *right_buf = path->nodes[0]; 924e20d96d6SChris Mason struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf); 925e20d96d6SChris Mason struct buffer_head *t; 926234b63a0SChris Mason struct btrfs_leaf *left; 927be0e5c09SChris Mason int slot; 928be0e5c09SChris Mason int i; 929be0e5c09SChris Mason int free_space; 930be0e5c09SChris Mason int push_space = 0; 931be0e5c09SChris Mason int push_items = 0; 9320783fcfcSChris Mason struct btrfs_item *item; 9337518a238SChris Mason u32 old_left_nritems; 934aa5d6bedSChris Mason int ret = 0; 935aa5d6bedSChris Mason int wret; 936be0e5c09SChris Mason 937be0e5c09SChris Mason slot = path->slots[1]; 938be0e5c09SChris Mason if (slot == 0) { 939be0e5c09SChris Mason return 1; 940be0e5c09SChris Mason } 941be0e5c09SChris Mason if (!path->nodes[1]) { 942be0e5c09SChris Mason return 1; 943be0e5c09SChris Mason } 944e20d96d6SChris Mason t = read_tree_block(root, 945e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1)); 946e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 947123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9480783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 949234b63a0SChris Mason btrfs_block_release(root, t); 950be0e5c09SChris Mason return 1; 951be0e5c09SChris Mason } 95202217ed2SChris Mason 95302217ed2SChris Mason /* cow and double check */ 954e089f05cSChris Mason btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); 955e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 956123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9570783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 958234b63a0SChris Mason btrfs_block_release(root, t); 95902217ed2SChris Mason return 1; 96002217ed2SChris Mason } 96102217ed2SChris Mason 9627518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 963be0e5c09SChris Mason item = right->items + i; 964be0e5c09SChris Mason if (path->slots[0] == i) 965be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9660783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 9670783fcfcSChris Mason free_space) 968be0e5c09SChris Mason break; 969be0e5c09SChris Mason push_items++; 9700783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 971be0e5c09SChris Mason } 972be0e5c09SChris Mason if (push_items == 0) { 973234b63a0SChris Mason btrfs_block_release(root, t); 974be0e5c09SChris Mason return 1; 975be0e5c09SChris Mason } 976be0e5c09SChris Mason /* push data from right to left */ 9777518a238SChris Mason memcpy(left->items + btrfs_header_nritems(&left->header), 9780783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 979123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 9800783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 981123abc88SChris Mason memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space, 982123abc88SChris Mason btrfs_leaf_data(right) + 983123abc88SChris Mason btrfs_item_offset(right->items + push_items - 1), 984be0e5c09SChris Mason push_space); 9857518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 986eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 987eb60ceacSChris Mason 988be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 989123abc88SChris Mason u32 ioff = btrfs_item_offset(left->items + i); 990123abc88SChris Mason btrfs_set_item_offset(left->items + i, ioff - 991123abc88SChris Mason (BTRFS_LEAF_DATA_SIZE(root) - 9920783fcfcSChris Mason btrfs_item_offset(left->items + 9930783fcfcSChris Mason old_left_nritems - 1))); 994be0e5c09SChris Mason } 9957518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 996be0e5c09SChris Mason 997be0e5c09SChris Mason /* fixup right node */ 9980783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 999123abc88SChris Mason leaf_data_end(root, right); 1000123abc88SChris Mason memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1001123abc88SChris Mason push_space, btrfs_leaf_data(right) + 1002123abc88SChris Mason leaf_data_end(root, right), push_space); 1003be0e5c09SChris Mason memmove(right->items, right->items + push_items, 10047518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 10050783fcfcSChris Mason sizeof(struct btrfs_item)); 10067518a238SChris Mason btrfs_set_header_nritems(&right->header, 10077518a238SChris Mason btrfs_header_nritems(&right->header) - 10087518a238SChris Mason push_items); 1009123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1010eb60ceacSChris Mason 10117518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 10120783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 10130783fcfcSChris Mason btrfs_item_size(right->items + i)); 10140783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 1015be0e5c09SChris Mason } 1016eb60ceacSChris Mason 1017d5719762SChris Mason mark_buffer_dirty(t); 1018d5719762SChris Mason mark_buffer_dirty(right_buf); 1019eb60ceacSChris Mason 1020e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); 1021aa5d6bedSChris Mason if (wret) 1022aa5d6bedSChris Mason ret = wret; 1023be0e5c09SChris Mason 1024be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1025be0e5c09SChris Mason if (path->slots[0] < push_items) { 1026be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1027234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1028eb60ceacSChris Mason path->nodes[0] = t; 1029be0e5c09SChris Mason path->slots[1] -= 1; 1030be0e5c09SChris Mason } else { 1031234b63a0SChris Mason btrfs_block_release(root, t); 1032be0e5c09SChris Mason path->slots[0] -= push_items; 1033be0e5c09SChris Mason } 1034eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1035aa5d6bedSChris Mason return ret; 1036be0e5c09SChris Mason } 1037be0e5c09SChris Mason 103874123bd7SChris Mason /* 103974123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 104074123bd7SChris Mason * available for the resulting leaf level of the path. 1041aa5d6bedSChris Mason * 1042aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 104374123bd7SChris Mason */ 1044e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1045e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1046be0e5c09SChris Mason { 1047e20d96d6SChris Mason struct buffer_head *l_buf; 1048234b63a0SChris Mason struct btrfs_leaf *l; 10497518a238SChris Mason u32 nritems; 1050eb60ceacSChris Mason int mid; 1051eb60ceacSChris Mason int slot; 1052234b63a0SChris Mason struct btrfs_leaf *right; 1053e20d96d6SChris Mason struct buffer_head *right_buffer; 10540783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1055be0e5c09SChris Mason int data_copy_size; 1056be0e5c09SChris Mason int rt_data_off; 1057be0e5c09SChris Mason int i; 1058be0e5c09SChris Mason int ret; 1059aa5d6bedSChris Mason int wret; 1060be0e5c09SChris Mason 106140689478SChris Mason /* first try to make some room by pushing left and right */ 1062e089f05cSChris Mason wret = push_leaf_left(trans, root, path, data_size); 1063eaee50e8SChris Mason if (wret < 0) 1064eaee50e8SChris Mason return wret; 1065eaee50e8SChris Mason if (wret) { 1066e089f05cSChris Mason wret = push_leaf_right(trans, root, path, data_size); 1067eaee50e8SChris Mason if (wret < 0) 1068eaee50e8SChris Mason return wret; 1069eaee50e8SChris Mason } 1070eb60ceacSChris Mason l_buf = path->nodes[0]; 1071e20d96d6SChris Mason l = btrfs_buffer_leaf(l_buf); 1072aa5d6bedSChris Mason 1073aa5d6bedSChris Mason /* did the pushes work? */ 1074123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1075123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1076be0e5c09SChris Mason return 0; 1077aa5d6bedSChris Mason 10785c680ed6SChris Mason if (!path->nodes[1]) { 1079e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 10805c680ed6SChris Mason if (ret) 10815c680ed6SChris Mason return ret; 10825c680ed6SChris Mason } 1083eb60ceacSChris Mason slot = path->slots[0]; 10847518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1085eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1086e089f05cSChris Mason right_buffer = btrfs_alloc_free_block(trans, root); 1087eb60ceacSChris Mason BUG_ON(!right_buffer); 1088eb60ceacSChris Mason BUG_ON(mid == nritems); 1089e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buffer); 1090123abc88SChris Mason memset(&right->header, 0, sizeof(right->header)); 1091be0e5c09SChris Mason if (mid <= slot) { 109297571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1093be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1094123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1095be0e5c09SChris Mason BUG(); 1096be0e5c09SChris Mason } else { 109797571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1098be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1099123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1100be0e5c09SChris Mason BUG(); 1101be0e5c09SChris Mason } 11027518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 1103e20d96d6SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr); 11047f5c1516SChris Mason btrfs_set_header_generation(&right->header, trans->transid); 11057518a238SChris Mason btrfs_set_header_level(&right->header, 0); 11067518a238SChris Mason btrfs_set_header_parentid(&right->header, 1107e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 1108123abc88SChris Mason data_copy_size = btrfs_item_end(l->items + mid) - 1109123abc88SChris Mason leaf_data_end(root, l); 1110be0e5c09SChris Mason memcpy(right->items, l->items + mid, 11110783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1112123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1113123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1114123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 1115123abc88SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1116123abc88SChris Mason btrfs_item_end(l->items + mid); 111774123bd7SChris Mason 11180783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1119123abc88SChris Mason u32 ioff = btrfs_item_offset(right->items + i); 11200783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 11210783fcfcSChris Mason } 112274123bd7SChris Mason 11237518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1124aa5d6bedSChris Mason ret = 0; 1125e089f05cSChris Mason wret = insert_ptr(trans, root, path, &right->items[0].key, 1126e20d96d6SChris Mason right_buffer->b_blocknr, path->slots[1] + 1, 1); 1127aa5d6bedSChris Mason if (wret) 1128aa5d6bedSChris Mason ret = wret; 1129d5719762SChris Mason mark_buffer_dirty(right_buffer); 1130d5719762SChris Mason mark_buffer_dirty(l_buf); 1131eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1132be0e5c09SChris Mason if (mid <= slot) { 1133234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1134eb60ceacSChris Mason path->nodes[0] = right_buffer; 1135be0e5c09SChris Mason path->slots[0] -= mid; 1136be0e5c09SChris Mason path->slots[1] += 1; 1137eb60ceacSChris Mason } else 1138234b63a0SChris Mason btrfs_block_release(root, right_buffer); 1139eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1140be0e5c09SChris Mason return ret; 1141be0e5c09SChris Mason } 1142be0e5c09SChris Mason 114374123bd7SChris Mason /* 114474123bd7SChris Mason * Given a key and some data, insert an item into the tree. 114574123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 114674123bd7SChris Mason */ 1147e089f05cSChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1148e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_key 1149e089f05cSChris Mason *cpu_key, u32 data_size) 1150be0e5c09SChris Mason { 1151aa5d6bedSChris Mason int ret = 0; 1152be0e5c09SChris Mason int slot; 1153eb60ceacSChris Mason int slot_orig; 1154234b63a0SChris Mason struct btrfs_leaf *leaf; 1155e20d96d6SChris Mason struct buffer_head *leaf_buf; 11567518a238SChris Mason u32 nritems; 1157be0e5c09SChris Mason unsigned int data_end; 1158e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1159e2fa7227SChris Mason 1160e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1161be0e5c09SChris Mason 116274123bd7SChris Mason /* create a root if there isn't one */ 11635c680ed6SChris Mason if (!root->node) 1164cfaa7295SChris Mason BUG(); 1165e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 1166eb60ceacSChris Mason if (ret == 0) { 116762e2749eSChris Mason btrfs_release_path(root, path); 1168f0930a37SChris Mason return -EEXIST; 1169aa5d6bedSChris Mason } 1170ed2ff2cbSChris Mason if (ret < 0) 1171ed2ff2cbSChris Mason goto out; 1172be0e5c09SChris Mason 117362e2749eSChris Mason slot_orig = path->slots[0]; 117462e2749eSChris Mason leaf_buf = path->nodes[0]; 1175e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 117674123bd7SChris Mason 11777518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1178123abc88SChris Mason data_end = leaf_data_end(root, leaf); 1179eb60ceacSChris Mason 1180123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 1181234b63a0SChris Mason sizeof(struct btrfs_item) + data_size) 1182be0e5c09SChris Mason BUG(); 1183be0e5c09SChris Mason 118462e2749eSChris Mason slot = path->slots[0]; 1185eb60ceacSChris Mason BUG_ON(slot < 0); 1186be0e5c09SChris Mason if (slot != nritems) { 1187be0e5c09SChris Mason int i; 11880783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1189be0e5c09SChris Mason 1190be0e5c09SChris Mason /* 1191be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1192be0e5c09SChris Mason */ 1193be0e5c09SChris Mason /* first correct the data pointers */ 11940783fcfcSChris Mason for (i = slot; i < nritems; i++) { 1195123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 11960783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 11970783fcfcSChris Mason ioff - data_size); 11980783fcfcSChris Mason } 1199be0e5c09SChris Mason 1200be0e5c09SChris Mason /* shift the items */ 1201be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 12020783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1203be0e5c09SChris Mason 1204be0e5c09SChris Mason /* shift the data */ 1205123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end - data_size, 1206123abc88SChris Mason btrfs_leaf_data(leaf) + 1207be0e5c09SChris Mason data_end, old_data - data_end); 1208be0e5c09SChris Mason data_end = old_data; 1209be0e5c09SChris Mason } 121062e2749eSChris Mason /* setup the item for the new data */ 1211e2fa7227SChris Mason memcpy(&leaf->items[slot].key, &disk_key, 1212e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 12130783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 12140783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 12157518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1216d5719762SChris Mason mark_buffer_dirty(leaf_buf); 1217aa5d6bedSChris Mason 1218aa5d6bedSChris Mason ret = 0; 12198e19f2cdSChris Mason if (slot == 0) 1220e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 1221aa5d6bedSChris Mason 1222123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1223be0e5c09SChris Mason BUG(); 122462e2749eSChris Mason check_leaf(root, path, 0); 1225ed2ff2cbSChris Mason out: 122662e2749eSChris Mason return ret; 122762e2749eSChris Mason } 122862e2749eSChris Mason 122962e2749eSChris Mason /* 123062e2749eSChris Mason * Given a key and some data, insert an item into the tree. 123162e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 123262e2749eSChris Mason */ 1233e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 1234e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 1235e089f05cSChris Mason data_size) 123662e2749eSChris Mason { 123762e2749eSChris Mason int ret = 0; 123862e2749eSChris Mason struct btrfs_path path; 123962e2749eSChris Mason u8 *ptr; 124062e2749eSChris Mason 124162e2749eSChris Mason btrfs_init_path(&path); 1242e089f05cSChris Mason ret = btrfs_insert_empty_item(trans, root, &path, cpu_key, data_size); 124362e2749eSChris Mason if (!ret) { 1244e20d96d6SChris Mason ptr = btrfs_item_ptr(btrfs_buffer_leaf(path.nodes[0]), 1245e20d96d6SChris Mason path.slots[0], u8); 124662e2749eSChris Mason memcpy(ptr, data, data_size); 1247d5719762SChris Mason mark_buffer_dirty(path.nodes[0]); 124862e2749eSChris Mason } 1249234b63a0SChris Mason btrfs_release_path(root, &path); 1250aa5d6bedSChris Mason return ret; 1251be0e5c09SChris Mason } 1252be0e5c09SChris Mason 125374123bd7SChris Mason /* 12545de08d7dSChris Mason * delete the pointer from a given node. 125574123bd7SChris Mason * 125674123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 125774123bd7SChris Mason * continuing all the way the root if required. The root is converted into 125874123bd7SChris Mason * a leaf if all the nodes are emptied. 125974123bd7SChris Mason */ 1260e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1261e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 1262be0e5c09SChris Mason { 1263234b63a0SChris Mason struct btrfs_node *node; 1264e20d96d6SChris Mason struct buffer_head *parent = path->nodes[level]; 12657518a238SChris Mason u32 nritems; 1266aa5d6bedSChris Mason int ret = 0; 1267bb803951SChris Mason int wret; 1268be0e5c09SChris Mason 1269e20d96d6SChris Mason node = btrfs_buffer_node(parent); 12707518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1271be0e5c09SChris Mason if (slot != nritems -1) { 1272123abc88SChris Mason memmove(node->ptrs + slot, node->ptrs + slot + 1, 1273123abc88SChris Mason sizeof(struct btrfs_key_ptr) * (nritems - slot - 1)); 1274be0e5c09SChris Mason } 12757518a238SChris Mason nritems--; 12767518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 12777518a238SChris Mason if (nritems == 0 && parent == root->node) { 1278e20d96d6SChris Mason struct btrfs_header *header = btrfs_buffer_header(root->node); 1279e20d96d6SChris Mason BUG_ON(btrfs_header_level(header) != 1); 1280eb60ceacSChris Mason /* just turn the root into a leaf and break */ 1281e20d96d6SChris Mason btrfs_set_header_level(header, 0); 1282bb803951SChris Mason } else if (slot == 0) { 1283e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, 1284123abc88SChris Mason level + 1); 12850f70abe2SChris Mason if (wret) 12860f70abe2SChris Mason ret = wret; 1287be0e5c09SChris Mason } 1288d5719762SChris Mason mark_buffer_dirty(parent); 1289aa5d6bedSChris Mason return ret; 1290be0e5c09SChris Mason } 1291be0e5c09SChris Mason 129274123bd7SChris Mason /* 129374123bd7SChris Mason * delete the item at the leaf level in path. If that empties 129474123bd7SChris Mason * the leaf, remove it from the tree 129574123bd7SChris Mason */ 1296e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1297e089f05cSChris Mason struct btrfs_path *path) 1298be0e5c09SChris Mason { 1299be0e5c09SChris Mason int slot; 1300234b63a0SChris Mason struct btrfs_leaf *leaf; 1301e20d96d6SChris Mason struct buffer_head *leaf_buf; 1302be0e5c09SChris Mason int doff; 1303be0e5c09SChris Mason int dsize; 1304aa5d6bedSChris Mason int ret = 0; 1305aa5d6bedSChris Mason int wret; 13067518a238SChris Mason u32 nritems; 1307be0e5c09SChris Mason 1308eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1309e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 13104920c9acSChris Mason slot = path->slots[0]; 13110783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 13120783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 13137518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1314be0e5c09SChris Mason 13157518a238SChris Mason if (slot != nritems - 1) { 1316be0e5c09SChris Mason int i; 1317123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 1318123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end + dsize, 1319123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 1320be0e5c09SChris Mason doff - data_end); 13210783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 1322123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 13230783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 13240783fcfcSChris Mason } 1325be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 13260783fcfcSChris Mason sizeof(struct btrfs_item) * 13277518a238SChris Mason (nritems - slot - 1)); 1328be0e5c09SChris Mason } 13297518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 13307518a238SChris Mason nritems--; 133174123bd7SChris Mason /* delete the leaf if we've emptied it */ 13327518a238SChris Mason if (nritems == 0) { 1333eb60ceacSChris Mason if (leaf_buf == root->node) { 13347518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 13359a8dd150SChris Mason } else { 1336e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1337e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 1338aa5d6bedSChris Mason if (wret) 1339aa5d6bedSChris Mason ret = wret; 1340e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 1341e20d96d6SChris Mason leaf_buf->b_blocknr, 1, 1); 13420f70abe2SChris Mason if (wret) 13430f70abe2SChris Mason ret = wret; 13449a8dd150SChris Mason } 1345be0e5c09SChris Mason } else { 13467518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1347aa5d6bedSChris Mason if (slot == 0) { 1348e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 1349aa5d6bedSChris Mason &leaf->items[0].key, 1); 1350aa5d6bedSChris Mason if (wret) 1351aa5d6bedSChris Mason ret = wret; 1352aa5d6bedSChris Mason } 1353aa5d6bedSChris Mason 135474123bd7SChris Mason /* delete the leaf if it is mostly empty */ 1355123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 1356be0e5c09SChris Mason /* push_leaf_left fixes the path. 1357be0e5c09SChris Mason * make sure the path still points to our leaf 1358be0e5c09SChris Mason * for possible call to del_ptr below 1359be0e5c09SChris Mason */ 13604920c9acSChris Mason slot = path->slots[1]; 1361e20d96d6SChris Mason get_bh(leaf_buf); 1362e089f05cSChris Mason wret = push_leaf_left(trans, root, path, 1); 1363aa5d6bedSChris Mason if (wret < 0) 1364aa5d6bedSChris Mason ret = wret; 1365f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 13667518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1367e089f05cSChris Mason wret = push_leaf_right(trans, root, path, 1); 1368aa5d6bedSChris Mason if (wret < 0) 1369aa5d6bedSChris Mason ret = wret; 1370aa5d6bedSChris Mason } 13717518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 1372e20d96d6SChris Mason u64 blocknr = leaf_buf->b_blocknr; 1373e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1374e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 1375aa5d6bedSChris Mason if (wret) 1376aa5d6bedSChris Mason ret = wret; 1377234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1378e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1379e089f05cSChris Mason 1, 1); 13800f70abe2SChris Mason if (wret) 13810f70abe2SChris Mason ret = wret; 13825de08d7dSChris Mason } else { 1383d5719762SChris Mason mark_buffer_dirty(leaf_buf); 1384234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1385be0e5c09SChris Mason } 1386d5719762SChris Mason } else { 1387d5719762SChris Mason mark_buffer_dirty(leaf_buf); 1388be0e5c09SChris Mason } 13899a8dd150SChris Mason } 1390aa5d6bedSChris Mason return ret; 13919a8dd150SChris Mason } 13929a8dd150SChris Mason 139397571fd0SChris Mason /* 139497571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 13950f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 13960f70abe2SChris Mason * returns < 0 on io errors. 139797571fd0SChris Mason */ 1398234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 1399d97e63b6SChris Mason { 1400d97e63b6SChris Mason int slot; 1401d97e63b6SChris Mason int level = 1; 1402d97e63b6SChris Mason u64 blocknr; 1403e20d96d6SChris Mason struct buffer_head *c; 1404e20d96d6SChris Mason struct btrfs_node *c_node; 1405e20d96d6SChris Mason struct buffer_head *next = NULL; 1406d97e63b6SChris Mason 1407234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 1408d97e63b6SChris Mason if (!path->nodes[level]) 14090f70abe2SChris Mason return 1; 1410d97e63b6SChris Mason slot = path->slots[level] + 1; 1411d97e63b6SChris Mason c = path->nodes[level]; 1412e20d96d6SChris Mason c_node = btrfs_buffer_node(c); 1413e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&c_node->header)) { 1414d97e63b6SChris Mason level++; 1415d97e63b6SChris Mason continue; 1416d97e63b6SChris Mason } 1417e20d96d6SChris Mason blocknr = btrfs_node_blockptr(c_node, slot); 1418cfaa7295SChris Mason if (next) 1419234b63a0SChris Mason btrfs_block_release(root, next); 1420d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1421d97e63b6SChris Mason break; 1422d97e63b6SChris Mason } 1423d97e63b6SChris Mason path->slots[level] = slot; 1424d97e63b6SChris Mason while(1) { 1425d97e63b6SChris Mason level--; 1426d97e63b6SChris Mason c = path->nodes[level]; 1427234b63a0SChris Mason btrfs_block_release(root, c); 1428d97e63b6SChris Mason path->nodes[level] = next; 1429d97e63b6SChris Mason path->slots[level] = 0; 1430d97e63b6SChris Mason if (!level) 1431d97e63b6SChris Mason break; 14321d4f8a0cSChris Mason next = read_tree_block(root, 1433e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(next), 0)); 1434d97e63b6SChris Mason } 1435d97e63b6SChris Mason return 0; 1436d97e63b6SChris Mason } 1437