12e635a27SChris Mason #include <linux/module.h> 2eb60ceacSChris Mason #include "ctree.h" 3eb60ceacSChris Mason #include "disk-io.h" 49a8dd150SChris Mason 5e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 6e089f05cSChris Mason *root, struct btrfs_path *path, int level); 7e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 8e089f05cSChris Mason *root, struct btrfs_path *path, int data_size); 9e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 10e20d96d6SChris Mason *root, struct buffer_head *dst, struct buffer_head 11e089f05cSChris Mason *src); 12e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 13e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 14e20d96d6SChris Mason struct buffer_head *src_buf); 15e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 16e089f05cSChris Mason struct btrfs_path *path, int level, int slot); 17d97e63b6SChris Mason 18234b63a0SChris Mason inline void btrfs_init_path(struct btrfs_path *p) 19be0e5c09SChris Mason { 20be0e5c09SChris Mason memset(p, 0, sizeof(*p)); 21be0e5c09SChris Mason } 22be0e5c09SChris Mason 23234b63a0SChris Mason void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p) 24eb60ceacSChris Mason { 25eb60ceacSChris Mason int i; 26234b63a0SChris Mason for (i = 0; i < BTRFS_MAX_LEVEL; i++) { 27eb60ceacSChris Mason if (!p->nodes[i]) 28eb60ceacSChris Mason break; 29234b63a0SChris Mason btrfs_block_release(root, p->nodes[i]); 30eb60ceacSChris Mason } 31aa5d6bedSChris Mason memset(p, 0, sizeof(*p)); 32eb60ceacSChris Mason } 33eb60ceacSChris Mason 34e089f05cSChris Mason static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root 35e20d96d6SChris Mason *root, struct buffer_head *buf, struct buffer_head 36e20d96d6SChris Mason *parent, int parent_slot, struct buffer_head 37e089f05cSChris Mason **cow_ret) 3802217ed2SChris Mason { 39e20d96d6SChris Mason struct buffer_head *cow; 40e20d96d6SChris Mason struct btrfs_node *cow_node; 4102217ed2SChris Mason 42d5719762SChris Mason if (buffer_dirty(buf)) { 4302217ed2SChris Mason *cow_ret = buf; 4402217ed2SChris Mason return 0; 4502217ed2SChris Mason } 46e089f05cSChris Mason cow = btrfs_alloc_free_block(trans, root); 47e20d96d6SChris Mason cow_node = btrfs_buffer_node(cow); 48e20d96d6SChris Mason memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize); 49e20d96d6SChris Mason btrfs_set_header_blocknr(&cow_node->header, cow->b_blocknr); 5002217ed2SChris Mason *cow_ret = cow; 51d5719762SChris Mason mark_buffer_dirty(cow); 52e089f05cSChris Mason btrfs_inc_ref(trans, root, buf); 5302217ed2SChris Mason if (buf == root->node) { 5402217ed2SChris Mason root->node = cow; 55e20d96d6SChris Mason get_bh(cow); 56a28ec197SChris Mason if (buf != root->commit_root) 57e20d96d6SChris Mason btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1); 58234b63a0SChris Mason btrfs_block_release(root, buf); 5902217ed2SChris Mason } else { 60e20d96d6SChris Mason btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot, 61e20d96d6SChris Mason cow->b_blocknr); 62d5719762SChris Mason mark_buffer_dirty(parent); 63e20d96d6SChris Mason btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1); 6402217ed2SChris Mason } 65234b63a0SChris Mason btrfs_block_release(root, buf); 6602217ed2SChris Mason return 0; 6702217ed2SChris Mason } 6802217ed2SChris Mason 6974123bd7SChris Mason /* 7074123bd7SChris Mason * The leaf data grows from end-to-front in the node. 7174123bd7SChris Mason * this returns the address of the start of the last item, 7274123bd7SChris Mason * which is the stop of the leaf data stack 7374123bd7SChris Mason */ 74123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root, 75123abc88SChris Mason struct btrfs_leaf *leaf) 76be0e5c09SChris Mason { 777518a238SChris Mason u32 nr = btrfs_header_nritems(&leaf->header); 78be0e5c09SChris Mason if (nr == 0) 79123abc88SChris Mason return BTRFS_LEAF_DATA_SIZE(root); 800783fcfcSChris Mason return btrfs_item_offset(leaf->items + nr - 1); 81be0e5c09SChris Mason } 82be0e5c09SChris Mason 8374123bd7SChris Mason /* 8474123bd7SChris Mason * The space between the end of the leaf items and 8574123bd7SChris Mason * the start of the leaf data. IOW, how much room 8674123bd7SChris Mason * the leaf has left for both items and data 8774123bd7SChris Mason */ 88123abc88SChris Mason int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf) 89be0e5c09SChris Mason { 90123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 917518a238SChris Mason int nritems = btrfs_header_nritems(&leaf->header); 92be0e5c09SChris Mason char *items_end = (char *)(leaf->items + nritems + 1); 93123abc88SChris Mason return (char *)(btrfs_leaf_data(leaf) + data_end) - (char *)items_end; 94be0e5c09SChris Mason } 95be0e5c09SChris Mason 9674123bd7SChris Mason /* 9774123bd7SChris Mason * compare two keys in a memcmp fashion 9874123bd7SChris Mason */ 999aca1d51SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2) 100be0e5c09SChris Mason { 101e2fa7227SChris Mason struct btrfs_key k1; 102e2fa7227SChris Mason 103e2fa7227SChris Mason btrfs_disk_key_to_cpu(&k1, disk); 104e2fa7227SChris Mason 105e2fa7227SChris Mason if (k1.objectid > k2->objectid) 106be0e5c09SChris Mason return 1; 107e2fa7227SChris Mason if (k1.objectid < k2->objectid) 108be0e5c09SChris Mason return -1; 10962e2749eSChris Mason if (k1.flags > k2->flags) 11062e2749eSChris Mason return 1; 11162e2749eSChris Mason if (k1.flags < k2->flags) 11262e2749eSChris Mason return -1; 113a8a2ee0cSChris Mason if (k1.offset > k2->offset) 114a8a2ee0cSChris Mason return 1; 115a8a2ee0cSChris Mason if (k1.offset < k2->offset) 116a8a2ee0cSChris Mason return -1; 117be0e5c09SChris Mason return 0; 118be0e5c09SChris Mason } 11974123bd7SChris Mason 120123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path, 121123abc88SChris Mason int level) 122aa5d6bedSChris Mason { 123aa5d6bedSChris Mason int i; 124234b63a0SChris Mason struct btrfs_node *parent = NULL; 125e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]); 126aa5d6bedSChris Mason int parent_slot; 1277518a238SChris Mason u32 nritems = btrfs_header_nritems(&node->header); 128aa5d6bedSChris Mason 129aa5d6bedSChris Mason if (path->nodes[level + 1]) 130e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 131aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 1327518a238SChris Mason BUG_ON(nritems == 0); 1337518a238SChris Mason if (parent) { 134e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 135123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 136123abc88SChris Mason BUG_ON(memcmp(parent_key, &node->ptrs[0].key, 137e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1381d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1397518a238SChris Mason btrfs_header_blocknr(&node->header)); 140aa5d6bedSChris Mason } 141123abc88SChris Mason BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root)); 1427518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 143e2fa7227SChris Mason struct btrfs_key cpukey; 144123abc88SChris Mason btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key); 145123abc88SChris Mason BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0); 146aa5d6bedSChris Mason } 147aa5d6bedSChris Mason return 0; 148aa5d6bedSChris Mason } 149aa5d6bedSChris Mason 150123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path, 151123abc88SChris Mason int level) 152aa5d6bedSChris Mason { 153aa5d6bedSChris Mason int i; 154e20d96d6SChris Mason struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]); 155234b63a0SChris Mason struct btrfs_node *parent = NULL; 156aa5d6bedSChris Mason int parent_slot; 1577518a238SChris Mason u32 nritems = btrfs_header_nritems(&leaf->header); 158aa5d6bedSChris Mason 159aa5d6bedSChris Mason if (path->nodes[level + 1]) 160e20d96d6SChris Mason parent = btrfs_buffer_node(path->nodes[level + 1]); 161aa5d6bedSChris Mason parent_slot = path->slots[level + 1]; 162123abc88SChris Mason BUG_ON(btrfs_leaf_free_space(root, leaf) < 0); 1637518a238SChris Mason 1647518a238SChris Mason if (nritems == 0) 1657518a238SChris Mason return 0; 1667518a238SChris Mason 1677518a238SChris Mason if (parent) { 168e2fa7227SChris Mason struct btrfs_disk_key *parent_key; 169123abc88SChris Mason parent_key = &parent->ptrs[parent_slot].key; 170aa5d6bedSChris Mason BUG_ON(memcmp(parent_key, &leaf->items[0].key, 171e2fa7227SChris Mason sizeof(struct btrfs_disk_key))); 1721d4f8a0cSChris Mason BUG_ON(btrfs_node_blockptr(parent, parent_slot) != 1737518a238SChris Mason btrfs_header_blocknr(&leaf->header)); 174aa5d6bedSChris Mason } 1757518a238SChris Mason for (i = 0; nritems > 1 && i < nritems - 2; i++) { 176e2fa7227SChris Mason struct btrfs_key cpukey; 177e2fa7227SChris Mason btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key); 178aa5d6bedSChris Mason BUG_ON(comp_keys(&leaf->items[i].key, 179e2fa7227SChris Mason &cpukey) >= 0); 1800783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) != 1810783fcfcSChris Mason btrfs_item_end(leaf->items + i + 1)); 182aa5d6bedSChris Mason if (i == 0) { 1830783fcfcSChris Mason BUG_ON(btrfs_item_offset(leaf->items + i) + 1840783fcfcSChris Mason btrfs_item_size(leaf->items + i) != 185123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)); 186aa5d6bedSChris Mason } 187aa5d6bedSChris Mason } 188aa5d6bedSChris Mason return 0; 189aa5d6bedSChris Mason } 190aa5d6bedSChris Mason 191123abc88SChris Mason static int check_block(struct btrfs_root *root, struct btrfs_path *path, 192123abc88SChris Mason int level) 193aa5d6bedSChris Mason { 194aa5d6bedSChris Mason if (level == 0) 195123abc88SChris Mason return check_leaf(root, path, level); 196123abc88SChris Mason return check_node(root, path, level); 197aa5d6bedSChris Mason } 198aa5d6bedSChris Mason 19974123bd7SChris Mason /* 20074123bd7SChris Mason * search for key in the array p. items p are item_size apart 20174123bd7SChris Mason * and there are 'max' items in p 20274123bd7SChris Mason * the slot in the array is returned via slot, and it points to 20374123bd7SChris Mason * the place where you would insert key if it is not found in 20474123bd7SChris Mason * the array. 20574123bd7SChris Mason * 20674123bd7SChris Mason * slot may point to max if the key is bigger than all of the keys 20774123bd7SChris Mason */ 2089aca1d51SChris Mason static int generic_bin_search(char *p, int item_size, struct btrfs_key *key, 209be0e5c09SChris Mason int max, int *slot) 210be0e5c09SChris Mason { 211be0e5c09SChris Mason int low = 0; 212be0e5c09SChris Mason int high = max; 213be0e5c09SChris Mason int mid; 214be0e5c09SChris Mason int ret; 215e2fa7227SChris Mason struct btrfs_disk_key *tmp; 216be0e5c09SChris Mason 217be0e5c09SChris Mason while(low < high) { 218be0e5c09SChris Mason mid = (low + high) / 2; 219e2fa7227SChris Mason tmp = (struct btrfs_disk_key *)(p + mid * item_size); 220be0e5c09SChris Mason ret = comp_keys(tmp, key); 221be0e5c09SChris Mason 222be0e5c09SChris Mason if (ret < 0) 223be0e5c09SChris Mason low = mid + 1; 224be0e5c09SChris Mason else if (ret > 0) 225be0e5c09SChris Mason high = mid; 226be0e5c09SChris Mason else { 227be0e5c09SChris Mason *slot = mid; 228be0e5c09SChris Mason return 0; 229be0e5c09SChris Mason } 230be0e5c09SChris Mason } 231be0e5c09SChris Mason *slot = low; 232be0e5c09SChris Mason return 1; 233be0e5c09SChris Mason } 234be0e5c09SChris Mason 23597571fd0SChris Mason /* 23697571fd0SChris Mason * simple bin_search frontend that does the right thing for 23797571fd0SChris Mason * leaves vs nodes 23897571fd0SChris Mason */ 2399aca1d51SChris Mason static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot) 240be0e5c09SChris Mason { 2417518a238SChris Mason if (btrfs_is_leaf(c)) { 242234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 2430783fcfcSChris Mason return generic_bin_search((void *)l->items, 2440783fcfcSChris Mason sizeof(struct btrfs_item), 2457518a238SChris Mason key, btrfs_header_nritems(&c->header), 2467518a238SChris Mason slot); 247be0e5c09SChris Mason } else { 248123abc88SChris Mason return generic_bin_search((void *)c->ptrs, 249123abc88SChris Mason sizeof(struct btrfs_key_ptr), 2507518a238SChris Mason key, btrfs_header_nritems(&c->header), 2517518a238SChris Mason slot); 252be0e5c09SChris Mason } 253be0e5c09SChris Mason return -1; 254be0e5c09SChris Mason } 255be0e5c09SChris Mason 256e20d96d6SChris Mason static struct buffer_head *read_node_slot(struct btrfs_root *root, 257e20d96d6SChris Mason struct buffer_head *parent_buf, 258bb803951SChris Mason int slot) 259bb803951SChris Mason { 260e20d96d6SChris Mason struct btrfs_node *node = btrfs_buffer_node(parent_buf); 261bb803951SChris Mason if (slot < 0) 262bb803951SChris Mason return NULL; 2637518a238SChris Mason if (slot >= btrfs_header_nritems(&node->header)) 264bb803951SChris Mason return NULL; 2651d4f8a0cSChris Mason return read_tree_block(root, btrfs_node_blockptr(node, slot)); 266bb803951SChris Mason } 267bb803951SChris Mason 268e089f05cSChris Mason static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root 269e089f05cSChris Mason *root, struct btrfs_path *path, int level) 270bb803951SChris Mason { 271e20d96d6SChris Mason struct buffer_head *right_buf; 272e20d96d6SChris Mason struct buffer_head *mid_buf; 273e20d96d6SChris Mason struct buffer_head *left_buf; 274e20d96d6SChris Mason struct buffer_head *parent_buf = NULL; 275234b63a0SChris Mason struct btrfs_node *right = NULL; 276234b63a0SChris Mason struct btrfs_node *mid; 277234b63a0SChris Mason struct btrfs_node *left = NULL; 278234b63a0SChris Mason struct btrfs_node *parent = NULL; 279bb803951SChris Mason int ret = 0; 280bb803951SChris Mason int wret; 281bb803951SChris Mason int pslot; 282bb803951SChris Mason int orig_slot = path->slots[level]; 28379f95c82SChris Mason u64 orig_ptr; 284bb803951SChris Mason 285bb803951SChris Mason if (level == 0) 286bb803951SChris Mason return 0; 287bb803951SChris Mason 288bb803951SChris Mason mid_buf = path->nodes[level]; 289e20d96d6SChris Mason mid = btrfs_buffer_node(mid_buf); 2901d4f8a0cSChris Mason orig_ptr = btrfs_node_blockptr(mid, orig_slot); 29179f95c82SChris Mason 292234b63a0SChris Mason if (level < BTRFS_MAX_LEVEL - 1) 293bb803951SChris Mason parent_buf = path->nodes[level + 1]; 294bb803951SChris Mason pslot = path->slots[level + 1]; 295bb803951SChris Mason 29640689478SChris Mason /* 29740689478SChris Mason * deal with the case where there is only one pointer in the root 29840689478SChris Mason * by promoting the node below to a root 29940689478SChris Mason */ 300bb803951SChris Mason if (!parent_buf) { 301e20d96d6SChris Mason struct buffer_head *child; 302e20d96d6SChris Mason u64 blocknr = mid_buf->b_blocknr; 303bb803951SChris Mason 3047518a238SChris Mason if (btrfs_header_nritems(&mid->header) != 1) 305bb803951SChris Mason return 0; 306bb803951SChris Mason 307bb803951SChris Mason /* promote the child to a root */ 308bb803951SChris Mason child = read_node_slot(root, mid_buf, 0); 309bb803951SChris Mason BUG_ON(!child); 310bb803951SChris Mason root->node = child; 311bb803951SChris Mason path->nodes[level] = NULL; 312bb803951SChris Mason /* once for the path */ 313234b63a0SChris Mason btrfs_block_release(root, mid_buf); 314bb803951SChris Mason /* once for the root ptr */ 315234b63a0SChris Mason btrfs_block_release(root, mid_buf); 316e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 317e089f05cSChris Mason return btrfs_free_extent(trans, root, blocknr, 1, 1); 318bb803951SChris Mason } 319e20d96d6SChris Mason parent = btrfs_buffer_node(parent_buf); 320bb803951SChris Mason 321123abc88SChris Mason if (btrfs_header_nritems(&mid->header) > 322123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root) / 4) 323bb803951SChris Mason return 0; 324bb803951SChris Mason 325bb803951SChris Mason left_buf = read_node_slot(root, parent_buf, pslot - 1); 326bb803951SChris Mason right_buf = read_node_slot(root, parent_buf, pslot + 1); 32779f95c82SChris Mason 32879f95c82SChris Mason /* first, try to make some room in the middle buffer */ 329bb803951SChris Mason if (left_buf) { 330e089f05cSChris Mason btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1, 331e089f05cSChris Mason &left_buf); 332e20d96d6SChris Mason left = btrfs_buffer_node(left_buf); 3337518a238SChris Mason orig_slot += btrfs_header_nritems(&left->header); 334e089f05cSChris Mason wret = push_node_left(trans, root, left_buf, mid_buf); 33579f95c82SChris Mason if (wret < 0) 33679f95c82SChris Mason ret = wret; 337bb803951SChris Mason } 33879f95c82SChris Mason 33979f95c82SChris Mason /* 34079f95c82SChris Mason * then try to empty the right most buffer into the middle 34179f95c82SChris Mason */ 342bb803951SChris Mason if (right_buf) { 343e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1, 344e089f05cSChris Mason &right_buf); 345e20d96d6SChris Mason right = btrfs_buffer_node(right_buf); 346e089f05cSChris Mason wret = push_node_left(trans, root, mid_buf, right_buf); 34779f95c82SChris Mason if (wret < 0) 34879f95c82SChris Mason ret = wret; 3497518a238SChris Mason if (btrfs_header_nritems(&right->header) == 0) { 350e20d96d6SChris Mason u64 blocknr = right_buf->b_blocknr; 351234b63a0SChris Mason btrfs_block_release(root, right_buf); 352e089f05cSChris Mason clean_tree_block(trans, root, right_buf); 353bb803951SChris Mason right_buf = NULL; 354bb803951SChris Mason right = NULL; 355e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot + 356e089f05cSChris Mason 1); 357bb803951SChris Mason if (wret) 358bb803951SChris Mason ret = wret; 359e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 360bb803951SChris Mason if (wret) 361bb803951SChris Mason ret = wret; 362bb803951SChris Mason } else { 363123abc88SChris Mason memcpy(&parent->ptrs[pslot + 1].key, 364123abc88SChris Mason &right->ptrs[0].key, 365e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 366d5719762SChris Mason mark_buffer_dirty(parent_buf); 367bb803951SChris Mason } 368bb803951SChris Mason } 3697518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 1) { 37079f95c82SChris Mason /* 37179f95c82SChris Mason * we're not allowed to leave a node with one item in the 37279f95c82SChris Mason * tree during a delete. A deletion from lower in the tree 37379f95c82SChris Mason * could try to delete the only pointer in this node. 37479f95c82SChris Mason * So, pull some keys from the left. 37579f95c82SChris Mason * There has to be a left pointer at this point because 37679f95c82SChris Mason * otherwise we would have pulled some pointers from the 37779f95c82SChris Mason * right 37879f95c82SChris Mason */ 37979f95c82SChris Mason BUG_ON(!left_buf); 380e089f05cSChris Mason wret = balance_node_right(trans, root, mid_buf, left_buf); 38179f95c82SChris Mason if (wret < 0) 38279f95c82SChris Mason ret = wret; 38379f95c82SChris Mason BUG_ON(wret == 1); 38479f95c82SChris Mason } 3857518a238SChris Mason if (btrfs_header_nritems(&mid->header) == 0) { 38679f95c82SChris Mason /* we've managed to empty the middle node, drop it */ 387e20d96d6SChris Mason u64 blocknr = mid_buf->b_blocknr; 388234b63a0SChris Mason btrfs_block_release(root, mid_buf); 389e089f05cSChris Mason clean_tree_block(trans, root, mid_buf); 390bb803951SChris Mason mid_buf = NULL; 391bb803951SChris Mason mid = NULL; 392e089f05cSChris Mason wret = del_ptr(trans, root, path, level + 1, pslot); 393bb803951SChris Mason if (wret) 394bb803951SChris Mason ret = wret; 395e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1, 1); 396bb803951SChris Mason if (wret) 397bb803951SChris Mason ret = wret; 39879f95c82SChris Mason } else { 39979f95c82SChris Mason /* update the parent key to reflect our changes */ 400123abc88SChris Mason memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key, 401e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 402d5719762SChris Mason mark_buffer_dirty(parent_buf); 40379f95c82SChris Mason } 404bb803951SChris Mason 40579f95c82SChris Mason /* update the path */ 406bb803951SChris Mason if (left_buf) { 4077518a238SChris Mason if (btrfs_header_nritems(&left->header) > orig_slot) { 408e20d96d6SChris Mason get_bh(left_buf); 409bb803951SChris Mason path->nodes[level] = left_buf; 410bb803951SChris Mason path->slots[level + 1] -= 1; 411bb803951SChris Mason path->slots[level] = orig_slot; 412bb803951SChris Mason if (mid_buf) 413234b63a0SChris Mason btrfs_block_release(root, mid_buf); 414bb803951SChris Mason } else { 4157518a238SChris Mason orig_slot -= btrfs_header_nritems(&left->header); 416bb803951SChris Mason path->slots[level] = orig_slot; 417bb803951SChris Mason } 418bb803951SChris Mason } 41979f95c82SChris Mason /* double check we haven't messed things up */ 420123abc88SChris Mason check_block(root, path, level); 421e20d96d6SChris Mason if (orig_ptr != 422e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]), 4231d4f8a0cSChris Mason path->slots[level])) 42479f95c82SChris Mason BUG(); 425bb803951SChris Mason 426bb803951SChris Mason if (right_buf) 427234b63a0SChris Mason btrfs_block_release(root, right_buf); 428bb803951SChris Mason if (left_buf) 429234b63a0SChris Mason btrfs_block_release(root, left_buf); 430bb803951SChris Mason return ret; 431bb803951SChris Mason } 432bb803951SChris Mason 43374123bd7SChris Mason /* 43474123bd7SChris Mason * look for key in the tree. path is filled in with nodes along the way 43574123bd7SChris Mason * if key is found, we return zero and you can find the item in the leaf 43674123bd7SChris Mason * level of the path (level 0) 43774123bd7SChris Mason * 43874123bd7SChris Mason * If the key isn't found, the path points to the slot where it should 439aa5d6bedSChris Mason * be inserted, and 1 is returned. If there are other errors during the 440aa5d6bedSChris Mason * search a negative error number is returned. 44197571fd0SChris Mason * 44297571fd0SChris Mason * if ins_len > 0, nodes and leaves will be split as we walk down the 44397571fd0SChris Mason * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if 44497571fd0SChris Mason * possible) 44574123bd7SChris Mason */ 446e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root 447e089f05cSChris Mason *root, struct btrfs_key *key, struct btrfs_path *p, int 448e089f05cSChris Mason ins_len, int cow) 449be0e5c09SChris Mason { 450e20d96d6SChris Mason struct buffer_head *b; 451e20d96d6SChris Mason struct buffer_head *cow_buf; 452234b63a0SChris Mason struct btrfs_node *c; 453be0e5c09SChris Mason int slot; 454be0e5c09SChris Mason int ret; 455be0e5c09SChris Mason int level; 4565c680ed6SChris Mason 457bb803951SChris Mason again: 458bb803951SChris Mason b = root->node; 459e20d96d6SChris Mason get_bh(b); 460eb60ceacSChris Mason while (b) { 461e20d96d6SChris Mason c = btrfs_buffer_node(b); 462e20d96d6SChris Mason level = btrfs_header_level(&c->header); 46302217ed2SChris Mason if (cow) { 46402217ed2SChris Mason int wret; 465e20d96d6SChris Mason wret = btrfs_cow_block(trans, root, b, 466e20d96d6SChris Mason p->nodes[level + 1], 467e20d96d6SChris Mason p->slots[level + 1], 468e089f05cSChris Mason &cow_buf); 46902217ed2SChris Mason b = cow_buf; 47002217ed2SChris Mason } 47102217ed2SChris Mason BUG_ON(!cow && ins_len); 472e20d96d6SChris Mason c = btrfs_buffer_node(b); 473eb60ceacSChris Mason p->nodes[level] = b; 474123abc88SChris Mason ret = check_block(root, p, level); 475aa5d6bedSChris Mason if (ret) 476aa5d6bedSChris Mason return -1; 477be0e5c09SChris Mason ret = bin_search(c, key, &slot); 4787518a238SChris Mason if (!btrfs_is_leaf(c)) { 479be0e5c09SChris Mason if (ret && slot > 0) 480be0e5c09SChris Mason slot -= 1; 481be0e5c09SChris Mason p->slots[level] = slot; 4827518a238SChris Mason if (ins_len > 0 && btrfs_header_nritems(&c->header) == 483123abc88SChris Mason BTRFS_NODEPTRS_PER_BLOCK(root)) { 484e089f05cSChris Mason int sret = split_node(trans, root, p, level); 4855c680ed6SChris Mason BUG_ON(sret > 0); 4865c680ed6SChris Mason if (sret) 4875c680ed6SChris Mason return sret; 4885c680ed6SChris Mason b = p->nodes[level]; 489e20d96d6SChris Mason c = btrfs_buffer_node(b); 4905c680ed6SChris Mason slot = p->slots[level]; 491bb803951SChris Mason } else if (ins_len < 0) { 492e089f05cSChris Mason int sret = balance_level(trans, root, p, 493e089f05cSChris Mason level); 494bb803951SChris Mason if (sret) 495bb803951SChris Mason return sret; 496bb803951SChris Mason b = p->nodes[level]; 497bb803951SChris Mason if (!b) 498bb803951SChris Mason goto again; 499e20d96d6SChris Mason c = btrfs_buffer_node(b); 500bb803951SChris Mason slot = p->slots[level]; 5017518a238SChris Mason BUG_ON(btrfs_header_nritems(&c->header) == 1); 5025c680ed6SChris Mason } 5031d4f8a0cSChris Mason b = read_tree_block(root, btrfs_node_blockptr(c, slot)); 504be0e5c09SChris Mason } else { 505234b63a0SChris Mason struct btrfs_leaf *l = (struct btrfs_leaf *)c; 506be0e5c09SChris Mason p->slots[level] = slot; 507123abc88SChris Mason if (ins_len > 0 && btrfs_leaf_free_space(root, l) < 5080783fcfcSChris Mason sizeof(struct btrfs_item) + ins_len) { 509e089f05cSChris Mason int sret = split_leaf(trans, root, p, ins_len); 5105c680ed6SChris Mason BUG_ON(sret > 0); 5115c680ed6SChris Mason if (sret) 5125c680ed6SChris Mason return sret; 5135c680ed6SChris Mason } 514be0e5c09SChris Mason return ret; 515be0e5c09SChris Mason } 516be0e5c09SChris Mason } 517aa5d6bedSChris Mason return 1; 518be0e5c09SChris Mason } 519be0e5c09SChris Mason 52074123bd7SChris Mason /* 52174123bd7SChris Mason * adjust the pointers going up the tree, starting at level 52274123bd7SChris Mason * making sure the right key of each node is points to 'key'. 52374123bd7SChris Mason * This is used after shifting pointers to the left, so it stops 52474123bd7SChris Mason * fixing up pointers when a given leaf/node is not in slot 0 of the 52574123bd7SChris Mason * higher levels 526aa5d6bedSChris Mason * 527aa5d6bedSChris Mason * If this fails to write a tree block, it returns -1, but continues 528aa5d6bedSChris Mason * fixing up the blocks in ram so the tree is consistent. 52974123bd7SChris Mason */ 530e089f05cSChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root 531e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 532e089f05cSChris Mason *key, int level) 533be0e5c09SChris Mason { 534be0e5c09SChris Mason int i; 535aa5d6bedSChris Mason int ret = 0; 536234b63a0SChris Mason for (i = level; i < BTRFS_MAX_LEVEL; i++) { 537234b63a0SChris Mason struct btrfs_node *t; 538be0e5c09SChris Mason int tslot = path->slots[i]; 539eb60ceacSChris Mason if (!path->nodes[i]) 540be0e5c09SChris Mason break; 541e20d96d6SChris Mason t = btrfs_buffer_node(path->nodes[i]); 542123abc88SChris Mason memcpy(&t->ptrs[tslot].key, key, sizeof(*key)); 543d5719762SChris Mason mark_buffer_dirty(path->nodes[i]); 544be0e5c09SChris Mason if (tslot != 0) 545be0e5c09SChris Mason break; 546be0e5c09SChris Mason } 547aa5d6bedSChris Mason return ret; 548be0e5c09SChris Mason } 549be0e5c09SChris Mason 55074123bd7SChris Mason /* 55174123bd7SChris Mason * try to push data from one node into the next node left in the 55279f95c82SChris Mason * tree. 553aa5d6bedSChris Mason * 554aa5d6bedSChris Mason * returns 0 if some ptrs were pushed left, < 0 if there was some horrible 555aa5d6bedSChris Mason * error, and > 0 if there was no room in the left hand block. 55674123bd7SChris Mason */ 557e089f05cSChris Mason static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root 558e20d96d6SChris Mason *root, struct buffer_head *dst_buf, struct 559e20d96d6SChris Mason buffer_head *src_buf) 560be0e5c09SChris Mason { 561e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 562e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 563be0e5c09SChris Mason int push_items = 0; 564bb803951SChris Mason int src_nritems; 565bb803951SChris Mason int dst_nritems; 566aa5d6bedSChris Mason int ret = 0; 567be0e5c09SChris Mason 5687518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 5697518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 570123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 571eb60ceacSChris Mason if (push_items <= 0) { 572be0e5c09SChris Mason return 1; 573eb60ceacSChris Mason } 574be0e5c09SChris Mason 575be0e5c09SChris Mason if (src_nritems < push_items) 576be0e5c09SChris Mason push_items = src_nritems; 57779f95c82SChris Mason 578123abc88SChris Mason memcpy(dst->ptrs + dst_nritems, src->ptrs, 579123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 580bb803951SChris Mason if (push_items < src_nritems) { 581123abc88SChris Mason memmove(src->ptrs, src->ptrs + push_items, 582e2fa7227SChris Mason (src_nritems - push_items) * 583123abc88SChris Mason sizeof(struct btrfs_key_ptr)); 584bb803951SChris Mason } 5857518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 5867518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 587d5719762SChris Mason mark_buffer_dirty(src_buf); 588d5719762SChris Mason mark_buffer_dirty(dst_buf); 589bb803951SChris Mason return ret; 590be0e5c09SChris Mason } 591be0e5c09SChris Mason 59297571fd0SChris Mason /* 59379f95c82SChris Mason * try to push data from one node into the next node right in the 59479f95c82SChris Mason * tree. 59579f95c82SChris Mason * 59679f95c82SChris Mason * returns 0 if some ptrs were pushed, < 0 if there was some horrible 59779f95c82SChris Mason * error, and > 0 if there was no room in the right hand block. 59879f95c82SChris Mason * 59979f95c82SChris Mason * this will only push up to 1/2 the contents of the left node over 60079f95c82SChris Mason */ 601e089f05cSChris Mason static int balance_node_right(struct btrfs_trans_handle *trans, struct 602e20d96d6SChris Mason btrfs_root *root, struct buffer_head *dst_buf, 603e20d96d6SChris Mason struct buffer_head *src_buf) 60479f95c82SChris Mason { 605e20d96d6SChris Mason struct btrfs_node *src = btrfs_buffer_node(src_buf); 606e20d96d6SChris Mason struct btrfs_node *dst = btrfs_buffer_node(dst_buf); 60779f95c82SChris Mason int push_items = 0; 60879f95c82SChris Mason int max_push; 60979f95c82SChris Mason int src_nritems; 61079f95c82SChris Mason int dst_nritems; 61179f95c82SChris Mason int ret = 0; 61279f95c82SChris Mason 6137518a238SChris Mason src_nritems = btrfs_header_nritems(&src->header); 6147518a238SChris Mason dst_nritems = btrfs_header_nritems(&dst->header); 615123abc88SChris Mason push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems; 61679f95c82SChris Mason if (push_items <= 0) { 61779f95c82SChris Mason return 1; 61879f95c82SChris Mason } 61979f95c82SChris Mason 62079f95c82SChris Mason max_push = src_nritems / 2 + 1; 62179f95c82SChris Mason /* don't try to empty the node */ 62279f95c82SChris Mason if (max_push > src_nritems) 62379f95c82SChris Mason return 1; 62479f95c82SChris Mason if (max_push < push_items) 62579f95c82SChris Mason push_items = max_push; 62679f95c82SChris Mason 627123abc88SChris Mason memmove(dst->ptrs + push_items, dst->ptrs, 628123abc88SChris Mason dst_nritems * sizeof(struct btrfs_key_ptr)); 629123abc88SChris Mason memcpy(dst->ptrs, src->ptrs + src_nritems - push_items, 630123abc88SChris Mason push_items * sizeof(struct btrfs_key_ptr)); 63179f95c82SChris Mason 6327518a238SChris Mason btrfs_set_header_nritems(&src->header, src_nritems - push_items); 6337518a238SChris Mason btrfs_set_header_nritems(&dst->header, dst_nritems + push_items); 63479f95c82SChris Mason 635d5719762SChris Mason mark_buffer_dirty(src_buf); 636d5719762SChris Mason mark_buffer_dirty(dst_buf); 63779f95c82SChris Mason return ret; 63879f95c82SChris Mason } 63979f95c82SChris Mason 64079f95c82SChris Mason /* 64197571fd0SChris Mason * helper function to insert a new root level in the tree. 64297571fd0SChris Mason * A new node is allocated, and a single item is inserted to 64397571fd0SChris Mason * point to the existing root 644aa5d6bedSChris Mason * 645aa5d6bedSChris Mason * returns zero on success or < 0 on failure. 64697571fd0SChris Mason */ 647e089f05cSChris Mason static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root 648e089f05cSChris Mason *root, struct btrfs_path *path, int level) 64974123bd7SChris Mason { 650e20d96d6SChris Mason struct buffer_head *t; 651234b63a0SChris Mason struct btrfs_node *lower; 652234b63a0SChris Mason struct btrfs_node *c; 653e2fa7227SChris Mason struct btrfs_disk_key *lower_key; 6545c680ed6SChris Mason 6555c680ed6SChris Mason BUG_ON(path->nodes[level]); 6565c680ed6SChris Mason BUG_ON(path->nodes[level-1] != root->node); 6575c680ed6SChris Mason 658e089f05cSChris Mason t = btrfs_alloc_free_block(trans, root); 659e20d96d6SChris Mason c = btrfs_buffer_node(t); 660123abc88SChris Mason memset(c, 0, root->blocksize); 6617518a238SChris Mason btrfs_set_header_nritems(&c->header, 1); 6627518a238SChris Mason btrfs_set_header_level(&c->header, level); 663e20d96d6SChris Mason btrfs_set_header_blocknr(&c->header, t->b_blocknr); 6647518a238SChris Mason btrfs_set_header_parentid(&c->header, 665e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 666e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level-1]); 6677518a238SChris Mason if (btrfs_is_leaf(lower)) 668234b63a0SChris Mason lower_key = &((struct btrfs_leaf *)lower)->items[0].key; 66974123bd7SChris Mason else 670123abc88SChris Mason lower_key = &lower->ptrs[0].key; 671123abc88SChris Mason memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key)); 672e20d96d6SChris Mason btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->b_blocknr); 673d5719762SChris Mason 674d5719762SChris Mason mark_buffer_dirty(t); 675d5719762SChris Mason 676cfaa7295SChris Mason /* the super has an extra ref to root->node */ 677234b63a0SChris Mason btrfs_block_release(root, root->node); 67874123bd7SChris Mason root->node = t; 679e20d96d6SChris Mason get_bh(t); 68074123bd7SChris Mason path->nodes[level] = t; 68174123bd7SChris Mason path->slots[level] = 0; 68274123bd7SChris Mason return 0; 68374123bd7SChris Mason } 6845c680ed6SChris Mason 6855c680ed6SChris Mason /* 6865c680ed6SChris Mason * worker function to insert a single pointer in a node. 6875c680ed6SChris Mason * the node should have enough room for the pointer already 68897571fd0SChris Mason * 6895c680ed6SChris Mason * slot and level indicate where you want the key to go, and 6905c680ed6SChris Mason * blocknr is the block the key points to. 691aa5d6bedSChris Mason * 692aa5d6bedSChris Mason * returns zero on success and < 0 on any error 6935c680ed6SChris Mason */ 694e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root 695e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_disk_key 696e089f05cSChris Mason *key, u64 blocknr, int slot, int level) 6975c680ed6SChris Mason { 698234b63a0SChris Mason struct btrfs_node *lower; 6995c680ed6SChris Mason int nritems; 7005c680ed6SChris Mason 7015c680ed6SChris Mason BUG_ON(!path->nodes[level]); 702e20d96d6SChris Mason lower = btrfs_buffer_node(path->nodes[level]); 7037518a238SChris Mason nritems = btrfs_header_nritems(&lower->header); 70474123bd7SChris Mason if (slot > nritems) 70574123bd7SChris Mason BUG(); 706123abc88SChris Mason if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root)) 70774123bd7SChris Mason BUG(); 70874123bd7SChris Mason if (slot != nritems) { 709123abc88SChris Mason memmove(lower->ptrs + slot + 1, lower->ptrs + slot, 710123abc88SChris Mason (nritems - slot) * sizeof(struct btrfs_key_ptr)); 71174123bd7SChris Mason } 712123abc88SChris Mason memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key)); 7131d4f8a0cSChris Mason btrfs_set_node_blockptr(lower, slot, blocknr); 7147518a238SChris Mason btrfs_set_header_nritems(&lower->header, nritems + 1); 715d5719762SChris Mason mark_buffer_dirty(path->nodes[level]); 71674123bd7SChris Mason return 0; 71774123bd7SChris Mason } 71874123bd7SChris Mason 71997571fd0SChris Mason /* 72097571fd0SChris Mason * split the node at the specified level in path in two. 72197571fd0SChris Mason * The path is corrected to point to the appropriate node after the split 72297571fd0SChris Mason * 72397571fd0SChris Mason * Before splitting this tries to make some room in the node by pushing 72497571fd0SChris Mason * left and right, if either one works, it returns right away. 725aa5d6bedSChris Mason * 726aa5d6bedSChris Mason * returns 0 on success and < 0 on failure 72797571fd0SChris Mason */ 728e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root 729e089f05cSChris Mason *root, struct btrfs_path *path, int level) 730be0e5c09SChris Mason { 731e20d96d6SChris Mason struct buffer_head *t; 732234b63a0SChris Mason struct btrfs_node *c; 733e20d96d6SChris Mason struct buffer_head *split_buffer; 734234b63a0SChris Mason struct btrfs_node *split; 735be0e5c09SChris Mason int mid; 7365c680ed6SChris Mason int ret; 737aa5d6bedSChris Mason int wret; 7387518a238SChris Mason u32 c_nritems; 739be0e5c09SChris Mason 7405c680ed6SChris Mason t = path->nodes[level]; 741e20d96d6SChris Mason c = btrfs_buffer_node(t); 7425c680ed6SChris Mason if (t == root->node) { 7435c680ed6SChris Mason /* trying to split the root, lets make a new one */ 744e089f05cSChris Mason ret = insert_new_root(trans, root, path, level + 1); 7455c680ed6SChris Mason if (ret) 7465c680ed6SChris Mason return ret; 7475c680ed6SChris Mason } 7487518a238SChris Mason c_nritems = btrfs_header_nritems(&c->header); 749e089f05cSChris Mason split_buffer = btrfs_alloc_free_block(trans, root); 750e20d96d6SChris Mason split = btrfs_buffer_node(split_buffer); 7517518a238SChris Mason btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); 752e20d96d6SChris Mason btrfs_set_header_blocknr(&split->header, split_buffer->b_blocknr); 7537518a238SChris Mason btrfs_set_header_parentid(&split->header, 754e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 7557518a238SChris Mason mid = (c_nritems + 1) / 2; 756123abc88SChris Mason memcpy(split->ptrs, c->ptrs + mid, 757123abc88SChris Mason (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); 7587518a238SChris Mason btrfs_set_header_nritems(&split->header, c_nritems - mid); 7597518a238SChris Mason btrfs_set_header_nritems(&c->header, mid); 760aa5d6bedSChris Mason ret = 0; 761aa5d6bedSChris Mason 762d5719762SChris Mason mark_buffer_dirty(t); 763d5719762SChris Mason mark_buffer_dirty(split_buffer); 764e089f05cSChris Mason wret = insert_ptr(trans, root, path, &split->ptrs[0].key, 765e20d96d6SChris Mason split_buffer->b_blocknr, path->slots[level + 1] + 1, 766123abc88SChris Mason level + 1); 767aa5d6bedSChris Mason if (wret) 768aa5d6bedSChris Mason ret = wret; 769aa5d6bedSChris Mason 7705de08d7dSChris Mason if (path->slots[level] >= mid) { 7715c680ed6SChris Mason path->slots[level] -= mid; 772234b63a0SChris Mason btrfs_block_release(root, t); 7735c680ed6SChris Mason path->nodes[level] = split_buffer; 7745c680ed6SChris Mason path->slots[level + 1] += 1; 775eb60ceacSChris Mason } else { 776234b63a0SChris Mason btrfs_block_release(root, split_buffer); 777be0e5c09SChris Mason } 778aa5d6bedSChris Mason return ret; 779be0e5c09SChris Mason } 780be0e5c09SChris Mason 78174123bd7SChris Mason /* 78274123bd7SChris Mason * how many bytes are required to store the items in a leaf. start 78374123bd7SChris Mason * and nr indicate which items in the leaf to check. This totals up the 78474123bd7SChris Mason * space used both by the item structs and the item data 78574123bd7SChris Mason */ 786234b63a0SChris Mason static int leaf_space_used(struct btrfs_leaf *l, int start, int nr) 787be0e5c09SChris Mason { 788be0e5c09SChris Mason int data_len; 789be0e5c09SChris Mason int end = start + nr - 1; 790be0e5c09SChris Mason 791be0e5c09SChris Mason if (!nr) 792be0e5c09SChris Mason return 0; 7930783fcfcSChris Mason data_len = btrfs_item_end(l->items + start); 7940783fcfcSChris Mason data_len = data_len - btrfs_item_offset(l->items + end); 7950783fcfcSChris Mason data_len += sizeof(struct btrfs_item) * nr; 796be0e5c09SChris Mason return data_len; 797be0e5c09SChris Mason } 798be0e5c09SChris Mason 79974123bd7SChris Mason /* 80000ec4c51SChris Mason * push some data in the path leaf to the right, trying to free up at 80100ec4c51SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 802aa5d6bedSChris Mason * 803aa5d6bedSChris Mason * returns 1 if the push failed because the other node didn't have enough 804aa5d6bedSChris Mason * room, 0 if everything worked out and < 0 if there were major errors. 80500ec4c51SChris Mason */ 806e089f05cSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root 807e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 80800ec4c51SChris Mason { 809e20d96d6SChris Mason struct buffer_head *left_buf = path->nodes[0]; 810e20d96d6SChris Mason struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf); 811234b63a0SChris Mason struct btrfs_leaf *right; 812e20d96d6SChris Mason struct buffer_head *right_buf; 813e20d96d6SChris Mason struct buffer_head *upper; 814e20d96d6SChris Mason struct btrfs_node *upper_node; 81500ec4c51SChris Mason int slot; 81600ec4c51SChris Mason int i; 81700ec4c51SChris Mason int free_space; 81800ec4c51SChris Mason int push_space = 0; 81900ec4c51SChris Mason int push_items = 0; 8200783fcfcSChris Mason struct btrfs_item *item; 8217518a238SChris Mason u32 left_nritems; 8227518a238SChris Mason u32 right_nritems; 82300ec4c51SChris Mason 82400ec4c51SChris Mason slot = path->slots[1]; 82500ec4c51SChris Mason if (!path->nodes[1]) { 82600ec4c51SChris Mason return 1; 82700ec4c51SChris Mason } 82800ec4c51SChris Mason upper = path->nodes[1]; 829e20d96d6SChris Mason upper_node = btrfs_buffer_node(upper); 830e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&upper_node->header) - 1) { 83100ec4c51SChris Mason return 1; 83200ec4c51SChris Mason } 833e20d96d6SChris Mason right_buf = read_tree_block(root, 834e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1)); 835e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 836123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8370783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 838234b63a0SChris Mason btrfs_block_release(root, right_buf); 83900ec4c51SChris Mason return 1; 84000ec4c51SChris Mason } 84102217ed2SChris Mason /* cow and double check */ 842e089f05cSChris Mason btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf); 843e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buf); 844123abc88SChris Mason free_space = btrfs_leaf_free_space(root, right); 8450783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 846234b63a0SChris Mason btrfs_block_release(root, right_buf); 84702217ed2SChris Mason return 1; 84802217ed2SChris Mason } 84902217ed2SChris Mason 8507518a238SChris Mason left_nritems = btrfs_header_nritems(&left->header); 8517518a238SChris Mason for (i = left_nritems - 1; i >= 0; i--) { 85200ec4c51SChris Mason item = left->items + i; 85300ec4c51SChris Mason if (path->slots[0] == i) 85400ec4c51SChris Mason push_space += data_size + sizeof(*item); 8550783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 8560783fcfcSChris Mason free_space) 85700ec4c51SChris Mason break; 85800ec4c51SChris Mason push_items++; 8590783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 86000ec4c51SChris Mason } 86100ec4c51SChris Mason if (push_items == 0) { 862234b63a0SChris Mason btrfs_block_release(root, right_buf); 86300ec4c51SChris Mason return 1; 86400ec4c51SChris Mason } 8657518a238SChris Mason right_nritems = btrfs_header_nritems(&right->header); 86600ec4c51SChris Mason /* push left to right */ 8670783fcfcSChris Mason push_space = btrfs_item_end(left->items + left_nritems - push_items); 868123abc88SChris Mason push_space -= leaf_data_end(root, left); 86900ec4c51SChris Mason /* make room in the right data area */ 870123abc88SChris Mason memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) - 871123abc88SChris Mason push_space, btrfs_leaf_data(right) + leaf_data_end(root, right), 872123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right)); 87300ec4c51SChris Mason /* copy from the left data area */ 874123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space, 875123abc88SChris Mason btrfs_leaf_data(left) + leaf_data_end(root, left), push_space); 87600ec4c51SChris Mason memmove(right->items + push_items, right->items, 8770783fcfcSChris Mason right_nritems * sizeof(struct btrfs_item)); 87800ec4c51SChris Mason /* copy the items from left to right */ 8797518a238SChris Mason memcpy(right->items, left->items + left_nritems - push_items, 8800783fcfcSChris Mason push_items * sizeof(struct btrfs_item)); 88100ec4c51SChris Mason 88200ec4c51SChris Mason /* update the item pointers */ 8837518a238SChris Mason right_nritems += push_items; 8847518a238SChris Mason btrfs_set_header_nritems(&right->header, right_nritems); 885123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 8867518a238SChris Mason for (i = 0; i < right_nritems; i++) { 8870783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 8880783fcfcSChris Mason btrfs_item_size(right->items + i)); 8890783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 89000ec4c51SChris Mason } 8917518a238SChris Mason left_nritems -= push_items; 8927518a238SChris Mason btrfs_set_header_nritems(&left->header, left_nritems); 89300ec4c51SChris Mason 894d5719762SChris Mason mark_buffer_dirty(left_buf); 895d5719762SChris Mason mark_buffer_dirty(right_buf); 896e20d96d6SChris Mason memcpy(&upper_node->ptrs[slot + 1].key, 897e2fa7227SChris Mason &right->items[0].key, sizeof(struct btrfs_disk_key)); 898d5719762SChris Mason mark_buffer_dirty(upper); 89902217ed2SChris Mason 90000ec4c51SChris Mason /* then fixup the leaf pointer in the path */ 9017518a238SChris Mason if (path->slots[0] >= left_nritems) { 9027518a238SChris Mason path->slots[0] -= left_nritems; 903234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 90400ec4c51SChris Mason path->nodes[0] = right_buf; 90500ec4c51SChris Mason path->slots[1] += 1; 90600ec4c51SChris Mason } else { 907234b63a0SChris Mason btrfs_block_release(root, right_buf); 90800ec4c51SChris Mason } 90900ec4c51SChris Mason return 0; 91000ec4c51SChris Mason } 91100ec4c51SChris Mason /* 91274123bd7SChris Mason * push some data in the path leaf to the left, trying to free up at 91374123bd7SChris Mason * least data_size bytes. returns zero if the push worked, nonzero otherwise 91474123bd7SChris Mason */ 915e089f05cSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root 916e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 917be0e5c09SChris Mason { 918e20d96d6SChris Mason struct buffer_head *right_buf = path->nodes[0]; 919e20d96d6SChris Mason struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf); 920e20d96d6SChris Mason struct buffer_head *t; 921234b63a0SChris Mason struct btrfs_leaf *left; 922be0e5c09SChris Mason int slot; 923be0e5c09SChris Mason int i; 924be0e5c09SChris Mason int free_space; 925be0e5c09SChris Mason int push_space = 0; 926be0e5c09SChris Mason int push_items = 0; 9270783fcfcSChris Mason struct btrfs_item *item; 9287518a238SChris Mason u32 old_left_nritems; 929aa5d6bedSChris Mason int ret = 0; 930aa5d6bedSChris Mason int wret; 931be0e5c09SChris Mason 932be0e5c09SChris Mason slot = path->slots[1]; 933be0e5c09SChris Mason if (slot == 0) { 934be0e5c09SChris Mason return 1; 935be0e5c09SChris Mason } 936be0e5c09SChris Mason if (!path->nodes[1]) { 937be0e5c09SChris Mason return 1; 938be0e5c09SChris Mason } 939e20d96d6SChris Mason t = read_tree_block(root, 940e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1)); 941e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 942123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9430783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 944234b63a0SChris Mason btrfs_block_release(root, t); 945be0e5c09SChris Mason return 1; 946be0e5c09SChris Mason } 94702217ed2SChris Mason 94802217ed2SChris Mason /* cow and double check */ 949e089f05cSChris Mason btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t); 950e20d96d6SChris Mason left = btrfs_buffer_leaf(t); 951123abc88SChris Mason free_space = btrfs_leaf_free_space(root, left); 9520783fcfcSChris Mason if (free_space < data_size + sizeof(struct btrfs_item)) { 953234b63a0SChris Mason btrfs_block_release(root, t); 95402217ed2SChris Mason return 1; 95502217ed2SChris Mason } 95602217ed2SChris Mason 9577518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 958be0e5c09SChris Mason item = right->items + i; 959be0e5c09SChris Mason if (path->slots[0] == i) 960be0e5c09SChris Mason push_space += data_size + sizeof(*item); 9610783fcfcSChris Mason if (btrfs_item_size(item) + sizeof(*item) + push_space > 9620783fcfcSChris Mason free_space) 963be0e5c09SChris Mason break; 964be0e5c09SChris Mason push_items++; 9650783fcfcSChris Mason push_space += btrfs_item_size(item) + sizeof(*item); 966be0e5c09SChris Mason } 967be0e5c09SChris Mason if (push_items == 0) { 968234b63a0SChris Mason btrfs_block_release(root, t); 969be0e5c09SChris Mason return 1; 970be0e5c09SChris Mason } 971be0e5c09SChris Mason /* push data from right to left */ 9727518a238SChris Mason memcpy(left->items + btrfs_header_nritems(&left->header), 9730783fcfcSChris Mason right->items, push_items * sizeof(struct btrfs_item)); 974123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root) - 9750783fcfcSChris Mason btrfs_item_offset(right->items + push_items -1); 976123abc88SChris Mason memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space, 977123abc88SChris Mason btrfs_leaf_data(right) + 978123abc88SChris Mason btrfs_item_offset(right->items + push_items - 1), 979be0e5c09SChris Mason push_space); 9807518a238SChris Mason old_left_nritems = btrfs_header_nritems(&left->header); 981eb60ceacSChris Mason BUG_ON(old_left_nritems < 0); 982eb60ceacSChris Mason 983be0e5c09SChris Mason for (i = old_left_nritems; i < old_left_nritems + push_items; i++) { 984123abc88SChris Mason u32 ioff = btrfs_item_offset(left->items + i); 985123abc88SChris Mason btrfs_set_item_offset(left->items + i, ioff - 986123abc88SChris Mason (BTRFS_LEAF_DATA_SIZE(root) - 9870783fcfcSChris Mason btrfs_item_offset(left->items + 9880783fcfcSChris Mason old_left_nritems - 1))); 989be0e5c09SChris Mason } 9907518a238SChris Mason btrfs_set_header_nritems(&left->header, old_left_nritems + push_items); 991be0e5c09SChris Mason 992be0e5c09SChris Mason /* fixup right node */ 9930783fcfcSChris Mason push_space = btrfs_item_offset(right->items + push_items - 1) - 994123abc88SChris Mason leaf_data_end(root, right); 995123abc88SChris Mason memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 996123abc88SChris Mason push_space, btrfs_leaf_data(right) + 997123abc88SChris Mason leaf_data_end(root, right), push_space); 998be0e5c09SChris Mason memmove(right->items, right->items + push_items, 9997518a238SChris Mason (btrfs_header_nritems(&right->header) - push_items) * 10000783fcfcSChris Mason sizeof(struct btrfs_item)); 10017518a238SChris Mason btrfs_set_header_nritems(&right->header, 10027518a238SChris Mason btrfs_header_nritems(&right->header) - 10037518a238SChris Mason push_items); 1004123abc88SChris Mason push_space = BTRFS_LEAF_DATA_SIZE(root); 1005eb60ceacSChris Mason 10067518a238SChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 10070783fcfcSChris Mason btrfs_set_item_offset(right->items + i, push_space - 10080783fcfcSChris Mason btrfs_item_size(right->items + i)); 10090783fcfcSChris Mason push_space = btrfs_item_offset(right->items + i); 1010be0e5c09SChris Mason } 1011eb60ceacSChris Mason 1012d5719762SChris Mason mark_buffer_dirty(t); 1013d5719762SChris Mason mark_buffer_dirty(right_buf); 1014eb60ceacSChris Mason 1015e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1); 1016aa5d6bedSChris Mason if (wret) 1017aa5d6bedSChris Mason ret = wret; 1018be0e5c09SChris Mason 1019be0e5c09SChris Mason /* then fixup the leaf pointer in the path */ 1020be0e5c09SChris Mason if (path->slots[0] < push_items) { 1021be0e5c09SChris Mason path->slots[0] += old_left_nritems; 1022234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1023eb60ceacSChris Mason path->nodes[0] = t; 1024be0e5c09SChris Mason path->slots[1] -= 1; 1025be0e5c09SChris Mason } else { 1026234b63a0SChris Mason btrfs_block_release(root, t); 1027be0e5c09SChris Mason path->slots[0] -= push_items; 1028be0e5c09SChris Mason } 1029eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1030aa5d6bedSChris Mason return ret; 1031be0e5c09SChris Mason } 1032be0e5c09SChris Mason 103374123bd7SChris Mason /* 103474123bd7SChris Mason * split the path's leaf in two, making sure there is at least data_size 103574123bd7SChris Mason * available for the resulting leaf level of the path. 1036aa5d6bedSChris Mason * 1037aa5d6bedSChris Mason * returns 0 if all went well and < 0 on failure. 103874123bd7SChris Mason */ 1039e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root 1040e089f05cSChris Mason *root, struct btrfs_path *path, int data_size) 1041be0e5c09SChris Mason { 1042e20d96d6SChris Mason struct buffer_head *l_buf; 1043234b63a0SChris Mason struct btrfs_leaf *l; 10447518a238SChris Mason u32 nritems; 1045eb60ceacSChris Mason int mid; 1046eb60ceacSChris Mason int slot; 1047234b63a0SChris Mason struct btrfs_leaf *right; 1048e20d96d6SChris Mason struct buffer_head *right_buffer; 10490783fcfcSChris Mason int space_needed = data_size + sizeof(struct btrfs_item); 1050be0e5c09SChris Mason int data_copy_size; 1051be0e5c09SChris Mason int rt_data_off; 1052be0e5c09SChris Mason int i; 1053be0e5c09SChris Mason int ret; 1054aa5d6bedSChris Mason int wret; 1055be0e5c09SChris Mason 105640689478SChris Mason /* first try to make some room by pushing left and right */ 1057e089f05cSChris Mason wret = push_leaf_left(trans, root, path, data_size); 1058eaee50e8SChris Mason if (wret < 0) 1059eaee50e8SChris Mason return wret; 1060eaee50e8SChris Mason if (wret) { 1061e089f05cSChris Mason wret = push_leaf_right(trans, root, path, data_size); 1062eaee50e8SChris Mason if (wret < 0) 1063eaee50e8SChris Mason return wret; 1064eaee50e8SChris Mason } 1065eb60ceacSChris Mason l_buf = path->nodes[0]; 1066e20d96d6SChris Mason l = btrfs_buffer_leaf(l_buf); 1067aa5d6bedSChris Mason 1068aa5d6bedSChris Mason /* did the pushes work? */ 1069123abc88SChris Mason if (btrfs_leaf_free_space(root, l) >= 1070123abc88SChris Mason sizeof(struct btrfs_item) + data_size) 1071be0e5c09SChris Mason return 0; 1072aa5d6bedSChris Mason 10735c680ed6SChris Mason if (!path->nodes[1]) { 1074e089f05cSChris Mason ret = insert_new_root(trans, root, path, 1); 10755c680ed6SChris Mason if (ret) 10765c680ed6SChris Mason return ret; 10775c680ed6SChris Mason } 1078eb60ceacSChris Mason slot = path->slots[0]; 10797518a238SChris Mason nritems = btrfs_header_nritems(&l->header); 1080eb60ceacSChris Mason mid = (nritems + 1)/ 2; 1081e089f05cSChris Mason right_buffer = btrfs_alloc_free_block(trans, root); 1082eb60ceacSChris Mason BUG_ON(!right_buffer); 1083eb60ceacSChris Mason BUG_ON(mid == nritems); 1084e20d96d6SChris Mason right = btrfs_buffer_leaf(right_buffer); 1085123abc88SChris Mason memset(&right->header, 0, sizeof(right->header)); 1086be0e5c09SChris Mason if (mid <= slot) { 108797571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1088be0e5c09SChris Mason if (leaf_space_used(l, mid, nritems - mid) + space_needed > 1089123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1090be0e5c09SChris Mason BUG(); 1091be0e5c09SChris Mason } else { 109297571fd0SChris Mason /* FIXME, just alloc a new leaf here */ 1093be0e5c09SChris Mason if (leaf_space_used(l, 0, mid + 1) + space_needed > 1094123abc88SChris Mason BTRFS_LEAF_DATA_SIZE(root)) 1095be0e5c09SChris Mason BUG(); 1096be0e5c09SChris Mason } 10977518a238SChris Mason btrfs_set_header_nritems(&right->header, nritems - mid); 1098e20d96d6SChris Mason btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr); 10997518a238SChris Mason btrfs_set_header_level(&right->header, 0); 11007518a238SChris Mason btrfs_set_header_parentid(&right->header, 1101e20d96d6SChris Mason btrfs_header_parentid(btrfs_buffer_header(root->node))); 1102123abc88SChris Mason data_copy_size = btrfs_item_end(l->items + mid) - 1103123abc88SChris Mason leaf_data_end(root, l); 1104be0e5c09SChris Mason memcpy(right->items, l->items + mid, 11050783fcfcSChris Mason (nritems - mid) * sizeof(struct btrfs_item)); 1106123abc88SChris Mason memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - 1107123abc88SChris Mason data_copy_size, btrfs_leaf_data(l) + 1108123abc88SChris Mason leaf_data_end(root, l), data_copy_size); 1109123abc88SChris Mason rt_data_off = BTRFS_LEAF_DATA_SIZE(root) - 1110123abc88SChris Mason btrfs_item_end(l->items + mid); 111174123bd7SChris Mason 11120783fcfcSChris Mason for (i = 0; i < btrfs_header_nritems(&right->header); i++) { 1113123abc88SChris Mason u32 ioff = btrfs_item_offset(right->items + i); 11140783fcfcSChris Mason btrfs_set_item_offset(right->items + i, ioff + rt_data_off); 11150783fcfcSChris Mason } 111674123bd7SChris Mason 11177518a238SChris Mason btrfs_set_header_nritems(&l->header, mid); 1118aa5d6bedSChris Mason ret = 0; 1119e089f05cSChris Mason wret = insert_ptr(trans, root, path, &right->items[0].key, 1120e20d96d6SChris Mason right_buffer->b_blocknr, path->slots[1] + 1, 1); 1121aa5d6bedSChris Mason if (wret) 1122aa5d6bedSChris Mason ret = wret; 1123d5719762SChris Mason mark_buffer_dirty(right_buffer); 1124d5719762SChris Mason mark_buffer_dirty(l_buf); 1125eb60ceacSChris Mason BUG_ON(path->slots[0] != slot); 1126be0e5c09SChris Mason if (mid <= slot) { 1127234b63a0SChris Mason btrfs_block_release(root, path->nodes[0]); 1128eb60ceacSChris Mason path->nodes[0] = right_buffer; 1129be0e5c09SChris Mason path->slots[0] -= mid; 1130be0e5c09SChris Mason path->slots[1] += 1; 1131eb60ceacSChris Mason } else 1132234b63a0SChris Mason btrfs_block_release(root, right_buffer); 1133eb60ceacSChris Mason BUG_ON(path->slots[0] < 0); 1134be0e5c09SChris Mason return ret; 1135be0e5c09SChris Mason } 1136be0e5c09SChris Mason 113774123bd7SChris Mason /* 113874123bd7SChris Mason * Given a key and some data, insert an item into the tree. 113974123bd7SChris Mason * This does all the path init required, making room in the tree if needed. 114074123bd7SChris Mason */ 1141e089f05cSChris Mason int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root 1142e089f05cSChris Mason *root, struct btrfs_path *path, struct btrfs_key 1143e089f05cSChris Mason *cpu_key, u32 data_size) 1144be0e5c09SChris Mason { 1145aa5d6bedSChris Mason int ret = 0; 1146be0e5c09SChris Mason int slot; 1147eb60ceacSChris Mason int slot_orig; 1148234b63a0SChris Mason struct btrfs_leaf *leaf; 1149e20d96d6SChris Mason struct buffer_head *leaf_buf; 11507518a238SChris Mason u32 nritems; 1151be0e5c09SChris Mason unsigned int data_end; 1152e2fa7227SChris Mason struct btrfs_disk_key disk_key; 1153e2fa7227SChris Mason 1154e2fa7227SChris Mason btrfs_cpu_key_to_disk(&disk_key, cpu_key); 1155be0e5c09SChris Mason 115674123bd7SChris Mason /* create a root if there isn't one */ 11575c680ed6SChris Mason if (!root->node) 1158cfaa7295SChris Mason BUG(); 1159e089f05cSChris Mason ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1); 1160eb60ceacSChris Mason if (ret == 0) { 116162e2749eSChris Mason btrfs_release_path(root, path); 1162f0930a37SChris Mason return -EEXIST; 1163aa5d6bedSChris Mason } 1164ed2ff2cbSChris Mason if (ret < 0) 1165ed2ff2cbSChris Mason goto out; 1166be0e5c09SChris Mason 116762e2749eSChris Mason slot_orig = path->slots[0]; 116862e2749eSChris Mason leaf_buf = path->nodes[0]; 1169e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 117074123bd7SChris Mason 11717518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1172123abc88SChris Mason data_end = leaf_data_end(root, leaf); 1173eb60ceacSChris Mason 1174123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 1175234b63a0SChris Mason sizeof(struct btrfs_item) + data_size) 1176be0e5c09SChris Mason BUG(); 1177be0e5c09SChris Mason 117862e2749eSChris Mason slot = path->slots[0]; 1179eb60ceacSChris Mason BUG_ON(slot < 0); 1180be0e5c09SChris Mason if (slot != nritems) { 1181be0e5c09SChris Mason int i; 11820783fcfcSChris Mason unsigned int old_data = btrfs_item_end(leaf->items + slot); 1183be0e5c09SChris Mason 1184be0e5c09SChris Mason /* 1185be0e5c09SChris Mason * item0..itemN ... dataN.offset..dataN.size .. data0.size 1186be0e5c09SChris Mason */ 1187be0e5c09SChris Mason /* first correct the data pointers */ 11880783fcfcSChris Mason for (i = slot; i < nritems; i++) { 1189123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 11900783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, 11910783fcfcSChris Mason ioff - data_size); 11920783fcfcSChris Mason } 1193be0e5c09SChris Mason 1194be0e5c09SChris Mason /* shift the items */ 1195be0e5c09SChris Mason memmove(leaf->items + slot + 1, leaf->items + slot, 11960783fcfcSChris Mason (nritems - slot) * sizeof(struct btrfs_item)); 1197be0e5c09SChris Mason 1198be0e5c09SChris Mason /* shift the data */ 1199123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end - data_size, 1200123abc88SChris Mason btrfs_leaf_data(leaf) + 1201be0e5c09SChris Mason data_end, old_data - data_end); 1202be0e5c09SChris Mason data_end = old_data; 1203be0e5c09SChris Mason } 120462e2749eSChris Mason /* setup the item for the new data */ 1205e2fa7227SChris Mason memcpy(&leaf->items[slot].key, &disk_key, 1206e2fa7227SChris Mason sizeof(struct btrfs_disk_key)); 12070783fcfcSChris Mason btrfs_set_item_offset(leaf->items + slot, data_end - data_size); 12080783fcfcSChris Mason btrfs_set_item_size(leaf->items + slot, data_size); 12097518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems + 1); 1210d5719762SChris Mason mark_buffer_dirty(leaf_buf); 1211aa5d6bedSChris Mason 1212aa5d6bedSChris Mason ret = 0; 12138e19f2cdSChris Mason if (slot == 0) 1214e089f05cSChris Mason ret = fixup_low_keys(trans, root, path, &disk_key, 1); 1215aa5d6bedSChris Mason 1216123abc88SChris Mason if (btrfs_leaf_free_space(root, leaf) < 0) 1217be0e5c09SChris Mason BUG(); 121862e2749eSChris Mason check_leaf(root, path, 0); 1219ed2ff2cbSChris Mason out: 122062e2749eSChris Mason return ret; 122162e2749eSChris Mason } 122262e2749eSChris Mason 122362e2749eSChris Mason /* 122462e2749eSChris Mason * Given a key and some data, insert an item into the tree. 122562e2749eSChris Mason * This does all the path init required, making room in the tree if needed. 122662e2749eSChris Mason */ 1227e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root 1228e089f05cSChris Mason *root, struct btrfs_key *cpu_key, void *data, u32 1229e089f05cSChris Mason data_size) 123062e2749eSChris Mason { 123162e2749eSChris Mason int ret = 0; 123262e2749eSChris Mason struct btrfs_path path; 123362e2749eSChris Mason u8 *ptr; 123462e2749eSChris Mason 123562e2749eSChris Mason btrfs_init_path(&path); 1236e089f05cSChris Mason ret = btrfs_insert_empty_item(trans, root, &path, cpu_key, data_size); 123762e2749eSChris Mason if (!ret) { 1238e20d96d6SChris Mason ptr = btrfs_item_ptr(btrfs_buffer_leaf(path.nodes[0]), 1239e20d96d6SChris Mason path.slots[0], u8); 124062e2749eSChris Mason memcpy(ptr, data, data_size); 1241d5719762SChris Mason mark_buffer_dirty(path.nodes[0]); 124262e2749eSChris Mason } 1243234b63a0SChris Mason btrfs_release_path(root, &path); 1244aa5d6bedSChris Mason return ret; 1245be0e5c09SChris Mason } 1246be0e5c09SChris Mason 124774123bd7SChris Mason /* 12485de08d7dSChris Mason * delete the pointer from a given node. 124974123bd7SChris Mason * 125074123bd7SChris Mason * If the delete empties a node, the node is removed from the tree, 125174123bd7SChris Mason * continuing all the way the root if required. The root is converted into 125274123bd7SChris Mason * a leaf if all the nodes are emptied. 125374123bd7SChris Mason */ 1254e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1255e089f05cSChris Mason struct btrfs_path *path, int level, int slot) 1256be0e5c09SChris Mason { 1257234b63a0SChris Mason struct btrfs_node *node; 1258e20d96d6SChris Mason struct buffer_head *parent = path->nodes[level]; 12597518a238SChris Mason u32 nritems; 1260aa5d6bedSChris Mason int ret = 0; 1261bb803951SChris Mason int wret; 1262be0e5c09SChris Mason 1263e20d96d6SChris Mason node = btrfs_buffer_node(parent); 12647518a238SChris Mason nritems = btrfs_header_nritems(&node->header); 1265be0e5c09SChris Mason if (slot != nritems -1) { 1266123abc88SChris Mason memmove(node->ptrs + slot, node->ptrs + slot + 1, 1267123abc88SChris Mason sizeof(struct btrfs_key_ptr) * (nritems - slot - 1)); 1268be0e5c09SChris Mason } 12697518a238SChris Mason nritems--; 12707518a238SChris Mason btrfs_set_header_nritems(&node->header, nritems); 12717518a238SChris Mason if (nritems == 0 && parent == root->node) { 1272e20d96d6SChris Mason struct btrfs_header *header = btrfs_buffer_header(root->node); 1273e20d96d6SChris Mason BUG_ON(btrfs_header_level(header) != 1); 1274eb60ceacSChris Mason /* just turn the root into a leaf and break */ 1275e20d96d6SChris Mason btrfs_set_header_level(header, 0); 1276bb803951SChris Mason } else if (slot == 0) { 1277e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key, 1278123abc88SChris Mason level + 1); 12790f70abe2SChris Mason if (wret) 12800f70abe2SChris Mason ret = wret; 1281be0e5c09SChris Mason } 1282d5719762SChris Mason mark_buffer_dirty(parent); 1283aa5d6bedSChris Mason return ret; 1284be0e5c09SChris Mason } 1285be0e5c09SChris Mason 128674123bd7SChris Mason /* 128774123bd7SChris Mason * delete the item at the leaf level in path. If that empties 128874123bd7SChris Mason * the leaf, remove it from the tree 128974123bd7SChris Mason */ 1290e089f05cSChris Mason int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root, 1291e089f05cSChris Mason struct btrfs_path *path) 1292be0e5c09SChris Mason { 1293be0e5c09SChris Mason int slot; 1294234b63a0SChris Mason struct btrfs_leaf *leaf; 1295e20d96d6SChris Mason struct buffer_head *leaf_buf; 1296be0e5c09SChris Mason int doff; 1297be0e5c09SChris Mason int dsize; 1298aa5d6bedSChris Mason int ret = 0; 1299aa5d6bedSChris Mason int wret; 13007518a238SChris Mason u32 nritems; 1301be0e5c09SChris Mason 1302eb60ceacSChris Mason leaf_buf = path->nodes[0]; 1303e20d96d6SChris Mason leaf = btrfs_buffer_leaf(leaf_buf); 13044920c9acSChris Mason slot = path->slots[0]; 13050783fcfcSChris Mason doff = btrfs_item_offset(leaf->items + slot); 13060783fcfcSChris Mason dsize = btrfs_item_size(leaf->items + slot); 13077518a238SChris Mason nritems = btrfs_header_nritems(&leaf->header); 1308be0e5c09SChris Mason 13097518a238SChris Mason if (slot != nritems - 1) { 1310be0e5c09SChris Mason int i; 1311123abc88SChris Mason int data_end = leaf_data_end(root, leaf); 1312123abc88SChris Mason memmove(btrfs_leaf_data(leaf) + data_end + dsize, 1313123abc88SChris Mason btrfs_leaf_data(leaf) + data_end, 1314be0e5c09SChris Mason doff - data_end); 13150783fcfcSChris Mason for (i = slot + 1; i < nritems; i++) { 1316123abc88SChris Mason u32 ioff = btrfs_item_offset(leaf->items + i); 13170783fcfcSChris Mason btrfs_set_item_offset(leaf->items + i, ioff + dsize); 13180783fcfcSChris Mason } 1319be0e5c09SChris Mason memmove(leaf->items + slot, leaf->items + slot + 1, 13200783fcfcSChris Mason sizeof(struct btrfs_item) * 13217518a238SChris Mason (nritems - slot - 1)); 1322be0e5c09SChris Mason } 13237518a238SChris Mason btrfs_set_header_nritems(&leaf->header, nritems - 1); 13247518a238SChris Mason nritems--; 132574123bd7SChris Mason /* delete the leaf if we've emptied it */ 13267518a238SChris Mason if (nritems == 0) { 1327eb60ceacSChris Mason if (leaf_buf == root->node) { 13287518a238SChris Mason btrfs_set_header_level(&leaf->header, 0); 13299a8dd150SChris Mason } else { 1330e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1331e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, path->slots[1]); 1332aa5d6bedSChris Mason if (wret) 1333aa5d6bedSChris Mason ret = wret; 1334e089f05cSChris Mason wret = btrfs_free_extent(trans, root, 1335e20d96d6SChris Mason leaf_buf->b_blocknr, 1, 1); 13360f70abe2SChris Mason if (wret) 13370f70abe2SChris Mason ret = wret; 13389a8dd150SChris Mason } 1339be0e5c09SChris Mason } else { 13407518a238SChris Mason int used = leaf_space_used(leaf, 0, nritems); 1341aa5d6bedSChris Mason if (slot == 0) { 1342e089f05cSChris Mason wret = fixup_low_keys(trans, root, path, 1343aa5d6bedSChris Mason &leaf->items[0].key, 1); 1344aa5d6bedSChris Mason if (wret) 1345aa5d6bedSChris Mason ret = wret; 1346aa5d6bedSChris Mason } 1347aa5d6bedSChris Mason 134874123bd7SChris Mason /* delete the leaf if it is mostly empty */ 1349123abc88SChris Mason if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) { 1350be0e5c09SChris Mason /* push_leaf_left fixes the path. 1351be0e5c09SChris Mason * make sure the path still points to our leaf 1352be0e5c09SChris Mason * for possible call to del_ptr below 1353be0e5c09SChris Mason */ 13544920c9acSChris Mason slot = path->slots[1]; 1355e20d96d6SChris Mason get_bh(leaf_buf); 1356e089f05cSChris Mason wret = push_leaf_left(trans, root, path, 1); 1357aa5d6bedSChris Mason if (wret < 0) 1358aa5d6bedSChris Mason ret = wret; 1359f0930a37SChris Mason if (path->nodes[0] == leaf_buf && 13607518a238SChris Mason btrfs_header_nritems(&leaf->header)) { 1361e089f05cSChris Mason wret = push_leaf_right(trans, root, path, 1); 1362aa5d6bedSChris Mason if (wret < 0) 1363aa5d6bedSChris Mason ret = wret; 1364aa5d6bedSChris Mason } 13657518a238SChris Mason if (btrfs_header_nritems(&leaf->header) == 0) { 1366e20d96d6SChris Mason u64 blocknr = leaf_buf->b_blocknr; 1367e089f05cSChris Mason clean_tree_block(trans, root, leaf_buf); 1368e089f05cSChris Mason wret = del_ptr(trans, root, path, 1, slot); 1369aa5d6bedSChris Mason if (wret) 1370aa5d6bedSChris Mason ret = wret; 1371234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1372e089f05cSChris Mason wret = btrfs_free_extent(trans, root, blocknr, 1373e089f05cSChris Mason 1, 1); 13740f70abe2SChris Mason if (wret) 13750f70abe2SChris Mason ret = wret; 13765de08d7dSChris Mason } else { 1377d5719762SChris Mason mark_buffer_dirty(leaf_buf); 1378234b63a0SChris Mason btrfs_block_release(root, leaf_buf); 1379be0e5c09SChris Mason } 1380d5719762SChris Mason } else { 1381d5719762SChris Mason mark_buffer_dirty(leaf_buf); 1382be0e5c09SChris Mason } 13839a8dd150SChris Mason } 1384aa5d6bedSChris Mason return ret; 13859a8dd150SChris Mason } 13869a8dd150SChris Mason 138797571fd0SChris Mason /* 138897571fd0SChris Mason * walk up the tree as far as required to find the next leaf. 13890f70abe2SChris Mason * returns 0 if it found something or 1 if there are no greater leaves. 13900f70abe2SChris Mason * returns < 0 on io errors. 139197571fd0SChris Mason */ 1392234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path) 1393d97e63b6SChris Mason { 1394d97e63b6SChris Mason int slot; 1395d97e63b6SChris Mason int level = 1; 1396d97e63b6SChris Mason u64 blocknr; 1397e20d96d6SChris Mason struct buffer_head *c; 1398e20d96d6SChris Mason struct btrfs_node *c_node; 1399e20d96d6SChris Mason struct buffer_head *next = NULL; 1400d97e63b6SChris Mason 1401234b63a0SChris Mason while(level < BTRFS_MAX_LEVEL) { 1402d97e63b6SChris Mason if (!path->nodes[level]) 14030f70abe2SChris Mason return 1; 1404d97e63b6SChris Mason slot = path->slots[level] + 1; 1405d97e63b6SChris Mason c = path->nodes[level]; 1406e20d96d6SChris Mason c_node = btrfs_buffer_node(c); 1407e20d96d6SChris Mason if (slot >= btrfs_header_nritems(&c_node->header)) { 1408d97e63b6SChris Mason level++; 1409d97e63b6SChris Mason continue; 1410d97e63b6SChris Mason } 1411e20d96d6SChris Mason blocknr = btrfs_node_blockptr(c_node, slot); 1412cfaa7295SChris Mason if (next) 1413234b63a0SChris Mason btrfs_block_release(root, next); 1414d97e63b6SChris Mason next = read_tree_block(root, blocknr); 1415d97e63b6SChris Mason break; 1416d97e63b6SChris Mason } 1417d97e63b6SChris Mason path->slots[level] = slot; 1418d97e63b6SChris Mason while(1) { 1419d97e63b6SChris Mason level--; 1420d97e63b6SChris Mason c = path->nodes[level]; 1421234b63a0SChris Mason btrfs_block_release(root, c); 1422d97e63b6SChris Mason path->nodes[level] = next; 1423d97e63b6SChris Mason path->slots[level] = 0; 1424d97e63b6SChris Mason if (!level) 1425d97e63b6SChris Mason break; 14261d4f8a0cSChris Mason next = read_tree_block(root, 1427e20d96d6SChris Mason btrfs_node_blockptr(btrfs_buffer_node(next), 0)); 1428d97e63b6SChris Mason } 1429d97e63b6SChris Mason return 0; 1430d97e63b6SChris Mason } 1431