ctree.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "kerncompat.h"
   4 #include "radix-tree.h"
   5 #include "ctree.h"
   6 #include "disk-io.h"
   7 #include "print-tree.h"
   8
   9 static int split_node(struct ctree_root *root, struct ctree_path *path,
  10                       int level);
  11 static int split_leaf(struct ctree_root *root, struct ctree_path *path,
  12                       int data_size);
  13 static int push_node_left(struct ctree_root *root, struct tree_buffer *dst,
  14                           struct tree_buffer *src);
  15 static int balance_node_right(struct ctree_root *root,
  16                               struct tree_buffer *dst_buf,
  17                               struct tree_buffer *src_buf);
  18 static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level,
  19                    int slot);
  20
  21 inline void init_path(struct ctree_path *p)
  22 {
  23         memset(p, 0, sizeof(*p));
  24 }
  25
  26 void release_path(struct ctree_root *root, struct ctree_path *p)
  27 {
  28         int i;
  29         for (i = 0; i < MAX_LEVEL; i++) {
  30                 if (!p->nodes[i])
  31                         break;
  32                 tree_block_release(root, p->nodes[i]);
  33         }
  34         memset(p, 0, sizeof(*p));
  35 }
  36
  37 int btrfs_cow_block(struct ctree_root *root,
  38                     struct tree_buffer *buf,
  39                     struct tree_buffer *parent,
  40                     int parent_slot,
  41                     struct tree_buffer **cow_ret)
  42 {
  43         struct tree_buffer *cow;
  44
  45         if (!list_empty(&buf->dirty)) {
  46                 *cow_ret = buf;
  47                 return 0;
  48         }
  49         cow = alloc_free_block(root);
  50         memcpy(&cow->node, &buf->node, sizeof(buf->node));
  51         btrfs_set_header_blocknr(&cow->node.header, cow->blocknr);
  52         *cow_ret = cow;
  53         btrfs_inc_ref(root, buf);
  54         if (buf == root->node) {
  55                 root->node = cow;
  56                 cow->count++;
  57                 if (buf != root->commit_root)
  58                         free_extent(root, buf->blocknr, 1);
  59                 tree_block_release(root, buf);
  60         } else {
  61                 parent->node.blockptrs[parent_slot] = cow->blocknr;
  62                 BUG_ON(list_empty(&parent->dirty));
  63                 free_extent(root, buf->blocknr, 1);
  64         }
  65         tree_block_release(root, buf);
  66         return 0;
  67 }
  68
  69 /*
  70  * The leaf data grows from end-to-front in the node.
  71  * this returns the address of the start of the last item,
  72  * which is the stop of the leaf data stack
  73  */
  74 static inline unsigned int leaf_data_end(struct leaf *leaf)
  75 {
  76         u32 nr = btrfs_header_nritems(&leaf->header);
  77         if (nr == 0)
  78                 return sizeof(leaf->data);
  79         return leaf->items[nr-1].offset;
  80 }
  81
  82 /*
  83  * The space between the end of the leaf items and
  84  * the start of the leaf data.  IOW, how much room
  85  * the leaf has left for both items and data
  86  */
  87 int leaf_free_space(struct leaf *leaf)
  88 {
  89         int data_end = leaf_data_end(leaf);
  90         int nritems = btrfs_header_nritems(&leaf->header);
  91         char *items_end = (char *)(leaf->items + nritems + 1);
  92         return (char *)(leaf->data + data_end) - (char *)items_end;
  93 }
  94
  95 /*
  96  * compare two keys in a memcmp fashion
  97  */
  98 int comp_keys(struct key *k1, struct key *k2)
  99 {
 100         if (k1->objectid > k2->objectid)
 101                 return 1;
 102         if (k1->objectid < k2->objectid)
 103                 return -1;
 104         if (k1->flags > k2->flags)
 105                 return 1;
 106         if (k1->flags < k2->flags)
 107                 return -1;
 108         if (k1->offset > k2->offset)
 109                 return 1;
 110         if (k1->offset < k2->offset)
 111                 return -1;
 112         return 0;
 113 }
 114
 115 int check_node(struct ctree_path *path, int level)
 116 {
 117         int i;
 118         struct node *parent = NULL;
 119         struct node *node = &path->nodes[level]->node;
 120         int parent_slot;
 121         u32 nritems = btrfs_header_nritems(&node->header);
 122
 123         if (path->nodes[level + 1])
 124                 parent = &path->nodes[level + 1]->node;
 125         parent_slot = path->slots[level + 1];
 126         BUG_ON(nritems == 0);
 127         if (parent) {
 128                 struct key *parent_key;
 129                 parent_key = &parent->keys[parent_slot];
 130                 BUG_ON(memcmp(parent_key, node->keys, sizeof(struct key)));
 131                 BUG_ON(parent->blockptrs[parent_slot] !=
 132                        btrfs_header_blocknr(&node->header));
 133         }
 134         BUG_ON(nritems > NODEPTRS_PER_BLOCK);
 135         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 136                 BUG_ON(comp_keys(&node->keys[i], &node->keys[i+1]) >= 0);
 137         }
 138         return 0;
 139 }
 140
 141 int check_leaf(struct ctree_path *path, int level)
 142 {
 143         int i;
 144         struct leaf *leaf = &path->nodes[level]->leaf;
 145         struct node *parent = NULL;
 146         int parent_slot;
 147         u32 nritems = btrfs_header_nritems(&leaf->header);
 148
 149         if (path->nodes[level + 1])
 150                 parent = &path->nodes[level + 1]->node;
 151         parent_slot = path->slots[level + 1];
 152         BUG_ON(leaf_free_space(leaf) < 0);
 153
 154         if (nritems == 0)
 155                 return 0;
 156
 157         if (parent) {
 158                 struct key *parent_key;
 159                 parent_key = &parent->keys[parent_slot];
 160                 BUG_ON(memcmp(parent_key, &leaf->items[0].key,
 161                        sizeof(struct key)));
 162                 BUG_ON(parent->blockptrs[parent_slot] !=
 163                        btrfs_header_blocknr(&leaf->header));
 164         }
 165         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 166                 BUG_ON(comp_keys(&leaf->items[i].key,
 167                                  &leaf->items[i+1].key) >= 0);
 168                 BUG_ON(leaf->items[i].offset != leaf->items[i + 1].offset +
 169                     leaf->items[i + 1].size);
 170                 if (i == 0) {
 171                         BUG_ON(leaf->items[i].offset + leaf->items[i].size !=
 172                                 LEAF_DATA_SIZE);
 173                 }
 174         }
 175         return 0;
 176 }
 177
 178 int check_block(struct ctree_path *path, int level)
 179 {
 180         if (level == 0)
 181                 return check_leaf(path, level);
 182         return check_node(path, level);
 183 }
 184
 185 /*
 186  * search for key in the array p.  items p are item_size apart
 187  * and there are 'max' items in p
 188  * the slot in the array is returned via slot, and it points to
 189  * the place where you would insert key if it is not found in
 190  * the array.
 191  *
 192  * slot may point to max if the key is bigger than all of the keys
 193  */
 194 int generic_bin_search(char *p, int item_size, struct key *key,
 195                        int max, int *slot)
 196 {
 197         int low = 0;
 198         int high = max;
 199         int mid;
 200         int ret;
 201         struct key *tmp;
 202
 203         while(low < high) {
 204                 mid = (low + high) / 2;
 205                 tmp = (struct key *)(p + mid * item_size);
 206                 ret = comp_keys(tmp, key);
 207
 208                 if (ret < 0)
 209                         low = mid + 1;
 210                 else if (ret > 0)
 211                         high = mid;
 212                 else {
 213                         *slot = mid;
 214                         return 0;
 215                 }
 216         }
 217         *slot = low;
 218         return 1;
 219 }
 220
 221 /*
 222  * simple bin_search frontend that does the right thing for
 223  * leaves vs nodes
 224  */
 225 int bin_search(struct node *c, struct key *key, int *slot)
 226 {
 227         if (btrfs_is_leaf(c)) {
 228                 struct leaf *l = (struct leaf *)c;
 229                 return generic_bin_search((void *)l->items, sizeof(struct item),
 230                                           key, btrfs_header_nritems(&c->header),
 231                                           slot);
 232         } else {
 233                 return generic_bin_search((void *)c->keys, sizeof(struct key),
 234                                           key, btrfs_header_nritems(&c->header),
 235                                           slot);
 236         }
 237         return -1;
 238 }
 239
 240 struct tree_buffer *read_node_slot(struct ctree_root *root,
 241                                    struct tree_buffer *parent_buf,
 242                                    int slot)
 243 {
 244         struct node *node = &parent_buf->node;
 245         if (slot < 0)
 246                 return NULL;
 247         if (slot >= btrfs_header_nritems(&node->header))
 248                 return NULL;
 249         return read_tree_block(root, node->blockptrs[slot]);
 250 }
 251
 252 static int balance_level(struct ctree_root *root, struct ctree_path *path,
 253                         int level)
 254 {
 255         struct tree_buffer *right_buf;
 256         struct tree_buffer *mid_buf;
 257         struct tree_buffer *left_buf;
 258         struct tree_buffer *parent_buf = NULL;
 259         struct node *right = NULL;
 260         struct node *mid;
 261         struct node *left = NULL;
 262         struct node *parent = NULL;
 263         int ret = 0;
 264         int wret;
 265         int pslot;
 266         int orig_slot = path->slots[level];
 267         u64 orig_ptr;
 268
 269         if (level == 0)
 270                 return 0;
 271
 272         mid_buf = path->nodes[level];
 273         mid = &mid_buf->node;
 274         orig_ptr = mid->blockptrs[orig_slot];
 275
 276         if (level < MAX_LEVEL - 1)
 277                 parent_buf = path->nodes[level + 1];
 278         pslot = path->slots[level + 1];
 279
 280         if (!parent_buf) {
 281                 struct tree_buffer *child;
 282                 u64 blocknr = mid_buf->blocknr;
 283
 284                 if (btrfs_header_nritems(&mid->header) != 1)
 285                         return 0;
 286
 287                 /* promote the child to a root */
 288                 child = read_node_slot(root, mid_buf, 0);
 289                 BUG_ON(!child);
 290                 root->node = child;
 291                 path->nodes[level] = NULL;
 292                 /* once for the path */
 293                 tree_block_release(root, mid_buf);
 294                 /* once for the root ptr */
 295                 tree_block_release(root, mid_buf);
 296                 clean_tree_block(root, mid_buf);
 297                 return free_extent(root, blocknr, 1);
 298         }
 299         parent = &parent_buf->node;
 300
 301         if (btrfs_header_nritems(&mid->header) > NODEPTRS_PER_BLOCK / 4)
 302                 return 0;
 303
 304         left_buf = read_node_slot(root, parent_buf, pslot - 1);
 305         right_buf = read_node_slot(root, parent_buf, pslot + 1);
 306
 307         /* first, try to make some room in the middle buffer */
 308         if (left_buf) {
 309                 btrfs_cow_block(root, left_buf, parent_buf,
 310                                 pslot - 1, &left_buf);
 311                 left = &left_buf->node;
 312                 orig_slot += btrfs_header_nritems(&left->header);
 313                 wret = push_node_left(root, left_buf, mid_buf);
 314                 if (wret < 0)
 315                         ret = wret;
 316         }
 317
 318         /*
 319          * then try to empty the right most buffer into the middle
 320          */
 321         if (right_buf) {
 322                 btrfs_cow_block(root, right_buf, parent_buf,
 323                                 pslot + 1, &right_buf);
 324                 right = &right_buf->node;
 325                 wret = push_node_left(root, mid_buf, right_buf);
 326                 if (wret < 0)
 327                         ret = wret;
 328                 if (btrfs_header_nritems(&right->header) == 0) {
 329                         u64 blocknr = right_buf->blocknr;
 330                         tree_block_release(root, right_buf);
 331                         clean_tree_block(root, right_buf);
 332                         right_buf = NULL;
 333                         right = NULL;
 334                         wret = del_ptr(root, path, level + 1, pslot + 1);
 335                         if (wret)
 336                                 ret = wret;
 337                         wret = free_extent(root, blocknr, 1);
 338                         if (wret)
 339                                 ret = wret;
 340                 } else {
 341                         memcpy(parent->keys + pslot + 1, right->keys,
 342                                 sizeof(struct key));
 343                         BUG_ON(list_empty(&parent_buf->dirty));
 344                 }
 345         }
 346         if (btrfs_header_nritems(&mid->header) == 1) {
 347                 /*
 348                  * we're not allowed to leave a node with one item in the
 349                  * tree during a delete.  A deletion from lower in the tree
 350                  * could try to delete the only pointer in this node.
 351                  * So, pull some keys from the left.
 352                  * There has to be a left pointer at this point because
 353                  * otherwise we would have pulled some pointers from the
 354                  * right
 355                  */
 356                 BUG_ON(!left_buf);
 357                 wret = balance_node_right(root, mid_buf, left_buf);
 358                 if (wret < 0)
 359                         ret = wret;
 360                 BUG_ON(wret == 1);
 361         }
 362         if (btrfs_header_nritems(&mid->header) == 0) {
 363                 /* we've managed to empty the middle node, drop it */
 364                 u64 blocknr = mid_buf->blocknr;
 365                 tree_block_release(root, mid_buf);
 366                 clean_tree_block(root, mid_buf);
 367                 mid_buf = NULL;
 368                 mid = NULL;
 369                 wret = del_ptr(root, path, level + 1, pslot);
 370                 if (wret)
 371                         ret = wret;
 372                 wret = free_extent(root, blocknr, 1);
 373                 if (wret)
 374                         ret = wret;
 375         } else {
 376                 /* update the parent key to reflect our changes */
 377                 memcpy(parent->keys + pslot, mid->keys, sizeof(struct key));
 378                 BUG_ON(list_empty(&parent_buf->dirty));
 379         }
 380
 381         /* update the path */
 382         if (left_buf) {
 383                 if (btrfs_header_nritems(&left->header) > orig_slot) {
 384                         left_buf->count++; // released below
 385                         path->nodes[level] = left_buf;
 386                         path->slots[level + 1] -= 1;
 387                         path->slots[level] = orig_slot;
 388                         if (mid_buf)
 389                                 tree_block_release(root, mid_buf);
 390                 } else {
 391                         orig_slot -= btrfs_header_nritems(&left->header);
 392                         path->slots[level] = orig_slot;
 393                 }
 394         }
 395         /* double check we haven't messed things up */
 396         check_block(path, level);
 397         if (orig_ptr != path->nodes[level]->node.blockptrs[path->slots[level]])
 398                 BUG();
 399
 400         if (right_buf)
 401                 tree_block_release(root, right_buf);
 402         if (left_buf)
 403                 tree_block_release(root, left_buf);
 404         return ret;
 405 }
 406
 407 /*
 408  * look for key in the tree.  path is filled in with nodes along the way
 409  * if key is found, we return zero and you can find the item in the leaf
 410  * level of the path (level 0)
 411  *
 412  * If the key isn't found, the path points to the slot where it should
 413  * be inserted, and 1 is returned.  If there are other errors during the
 414  * search a negative error number is returned.
 415  *
 416  * if ins_len > 0, nodes and leaves will be split as we walk down the
 417  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
 418  * possible)
 419  */
 420 int search_slot(struct ctree_root *root, struct key *key,
 421                 struct ctree_path *p, int ins_len, int cow)
 422 {
 423         struct tree_buffer *b;
 424         struct tree_buffer *cow_buf;
 425         struct node *c;
 426         int slot;
 427         int ret;
 428         int level;
 429
 430 again:
 431         b = root->node;
 432         b->count++;
 433         while (b) {
 434                 level = btrfs_header_level(&b->node.header);
 435                 if (cow) {
 436                         int wret;
 437                         wret = btrfs_cow_block(root, b, p->nodes[level + 1],
 438                                                p->slots[level + 1], &cow_buf);
 439                         b = cow_buf;
 440                 }
 441                 BUG_ON(!cow && ins_len);
 442                 c = &b->node;
 443                 p->nodes[level] = b;
 444                 ret = check_block(p, level);
 445                 if (ret)
 446                         return -1;
 447                 ret = bin_search(c, key, &slot);
 448                 if (!btrfs_is_leaf(c)) {
 449                         if (ret && slot > 0)
 450                                 slot -= 1;
 451                         p->slots[level] = slot;
 452                         if (ins_len > 0 && btrfs_header_nritems(&c->header) ==
 453                             NODEPTRS_PER_BLOCK) {
 454                                 int sret = split_node(root, p, level);
 455                                 BUG_ON(sret > 0);
 456                                 if (sret)
 457                                         return sret;
 458                                 b = p->nodes[level];
 459                                 c = &b->node;
 460                                 slot = p->slots[level];
 461                         } else if (ins_len < 0) {
 462                                 int sret = balance_level(root, p, level);
 463                                 if (sret)
 464                                         return sret;
 465                                 b = p->nodes[level];
 466                                 if (!b)
 467                                         goto again;
 468                                 c = &b->node;
 469                                 slot = p->slots[level];
 470                                 BUG_ON(btrfs_header_nritems(&c->header) == 1);
 471                         }
 472                         b = read_tree_block(root, c->blockptrs[slot]);
 473                 } else {
 474                         struct leaf *l = (struct leaf *)c;
 475                         p->slots[level] = slot;
 476                         if (ins_len > 0 && leaf_free_space(l) <
 477                             sizeof(struct item) + ins_len) {
 478                                 int sret = split_leaf(root, p, ins_len);
 479                                 BUG_ON(sret > 0);
 480                                 if (sret)
 481                                         return sret;
 482                         }
 483                         BUG_ON(root->node->count == 1);
 484                         return ret;
 485                 }
 486         }
 487         BUG_ON(root->node->count == 1);
 488         return 1;
 489 }
 490
 491 /*
 492  * adjust the pointers going up the tree, starting at level
 493  * making sure the right key of each node is points to 'key'.
 494  * This is used after shifting pointers to the left, so it stops
 495  * fixing up pointers when a given leaf/node is not in slot 0 of the
 496  * higher levels
 497  *
 498  * If this fails to write a tree block, it returns -1, but continues
 499  * fixing up the blocks in ram so the tree is consistent.
 500  */
 501 static int fixup_low_keys(struct ctree_root *root,
 502                            struct ctree_path *path, struct key *key,
 503                            int level)
 504 {
 505         int i;
 506         int ret = 0;
 507         for (i = level; i < MAX_LEVEL; i++) {
 508                 struct node *t;
 509                 int tslot = path->slots[i];
 510                 if (!path->nodes[i])
 511                         break;
 512                 t = &path->nodes[i]->node;
 513                 memcpy(t->keys + tslot, key, sizeof(*key));
 514                 BUG_ON(list_empty(&path->nodes[i]->dirty));
 515                 if (tslot != 0)
 516                         break;
 517         }
 518         return ret;
 519 }
 520
 521 /*
 522  * try to push data from one node into the next node left in the
 523  * tree.
 524  *
 525  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
 526  * error, and > 0 if there was no room in the left hand block.
 527  */
 528 static int push_node_left(struct ctree_root *root, struct tree_buffer *dst_buf,
 529                           struct tree_buffer *src_buf)
 530 {
 531         struct node *src = &src_buf->node;
 532         struct node *dst = &dst_buf->node;
 533         int push_items = 0;
 534         int src_nritems;
 535         int dst_nritems;
 536         int ret = 0;
 537
 538         src_nritems = btrfs_header_nritems(&src->header);
 539         dst_nritems = btrfs_header_nritems(&dst->header);
 540         push_items = NODEPTRS_PER_BLOCK - dst_nritems;
 541         if (push_items <= 0) {
 542                 return 1;
 543         }
 544
 545         if (src_nritems < push_items)
 546                 push_items = src_nritems;
 547
 548         memcpy(dst->keys + dst_nritems, src->keys,
 549                 push_items * sizeof(struct key));
 550         memcpy(dst->blockptrs + dst_nritems, src->blockptrs,
 551                 push_items * sizeof(u64));
 552         if (push_items < src_nritems) {
 553                 memmove(src->keys, src->keys + push_items,
 554                         (src_nritems - push_items) * sizeof(struct key));
 555                 memmove(src->blockptrs, src->blockptrs + push_items,
 556                         (src_nritems - push_items) * sizeof(u64));
 557         }
 558         btrfs_set_header_nritems(&src->header, src_nritems - push_items);
 559         btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
 560         BUG_ON(list_empty(&src_buf->dirty));
 561         BUG_ON(list_empty(&dst_buf->dirty));
 562         return ret;
 563 }
 564
 565 /*
 566  * try to push data from one node into the next node right in the
 567  * tree.
 568  *
 569  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
 570  * error, and > 0 if there was no room in the right hand block.
 571  *
 572  * this will  only push up to 1/2 the contents of the left node over
 573  */
 574 static int balance_node_right(struct ctree_root *root,
 575                               struct tree_buffer *dst_buf,
 576                               struct tree_buffer *src_buf)
 577 {
 578         struct node *src = &src_buf->node;
 579         struct node *dst = &dst_buf->node;
 580         int push_items = 0;
 581         int max_push;
 582         int src_nritems;
 583         int dst_nritems;
 584         int ret = 0;
 585
 586         src_nritems = btrfs_header_nritems(&src->header);
 587         dst_nritems = btrfs_header_nritems(&dst->header);
 588         push_items = NODEPTRS_PER_BLOCK - dst_nritems;
 589         if (push_items <= 0) {
 590                 return 1;
 591         }
 592
 593         max_push = src_nritems / 2 + 1;
 594         /* don't try to empty the node */
 595         if (max_push > src_nritems)
 596                 return 1;
 597         if (max_push < push_items)
 598                 push_items = max_push;
 599
 600         memmove(dst->keys + push_items, dst->keys,
 601                 dst_nritems * sizeof(struct key));
 602         memmove(dst->blockptrs + push_items, dst->blockptrs,
 603                 dst_nritems * sizeof(u64));
 604         memcpy(dst->keys, src->keys + src_nritems - push_items,
 605                 push_items * sizeof(struct key));
 606         memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items,
 607                 push_items * sizeof(u64));
 608
 609         btrfs_set_header_nritems(&src->header, src_nritems - push_items);
 610         btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
 611
 612         BUG_ON(list_empty(&src_buf->dirty));
 613         BUG_ON(list_empty(&dst_buf->dirty));
 614         return ret;
 615 }
 616
 617 /*
 618  * helper function to insert a new root level in the tree.
 619  * A new node is allocated, and a single item is inserted to
 620  * point to the existing root
 621  *
 622  * returns zero on success or < 0 on failure.
 623  */
 624 static int insert_new_root(struct ctree_root *root,
 625                            struct ctree_path *path, int level)
 626 {
 627         struct tree_buffer *t;
 628         struct node *lower;
 629         struct node *c;
 630         struct key *lower_key;
 631
 632         BUG_ON(path->nodes[level]);
 633         BUG_ON(path->nodes[level-1] != root->node);
 634
 635         t = alloc_free_block(root);
 636         c = &t->node;
 637         memset(c, 0, sizeof(c));
 638         btrfs_set_header_nritems(&c->header, 1);
 639         btrfs_set_header_level(&c->header, level);
 640         btrfs_set_header_blocknr(&c->header, t->blocknr);
 641         btrfs_set_header_parentid(&c->header,
 642                                btrfs_header_parentid(&root->node->node.header));
 643         lower = &path->nodes[level-1]->node;
 644         if (btrfs_is_leaf(lower))
 645                 lower_key = &((struct leaf *)lower)->items[0].key;
 646         else
 647                 lower_key = lower->keys;
 648         memcpy(c->keys, lower_key, sizeof(struct key));
 649         c->blockptrs[0] = path->nodes[level-1]->blocknr;
 650         /* the super has an extra ref to root->node */
 651         tree_block_release(root, root->node);
 652         root->node = t;
 653         t->count++;
 654         path->nodes[level] = t;
 655         path->slots[level] = 0;
 656         return 0;
 657 }
 658
 659 /*
 660  * worker function to insert a single pointer in a node.
 661  * the node should have enough room for the pointer already
 662  *
 663  * slot and level indicate where you want the key to go, and
 664  * blocknr is the block the key points to.
 665  *
 666  * returns zero on success and < 0 on any error
 667  */
 668 static int insert_ptr(struct ctree_root *root,
 669                 struct ctree_path *path, struct key *key,
 670                 u64 blocknr, int slot, int level)
 671 {
 672         struct node *lower;
 673         int nritems;
 674
 675         BUG_ON(!path->nodes[level]);
 676         lower = &path->nodes[level]->node;
 677         nritems = btrfs_header_nritems(&lower->header);
 678         if (slot > nritems)
 679                 BUG();
 680         if (nritems == NODEPTRS_PER_BLOCK)
 681                 BUG();
 682         if (slot != nritems) {
 683                 memmove(lower->keys + slot + 1, lower->keys + slot,
 684                         (nritems - slot) * sizeof(struct key));
 685                 memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot,
 686                         (nritems - slot) * sizeof(u64));
 687         }
 688         memcpy(lower->keys + slot, key, sizeof(struct key));
 689         lower->blockptrs[slot] = blocknr;
 690         btrfs_set_header_nritems(&lower->header, nritems + 1);
 691         if (lower->keys[1].objectid == 0)
 692                         BUG();
 693         BUG_ON(list_empty(&path->nodes[level]->dirty));
 694         return 0;
 695 }
 696
 697 /*
 698  * split the node at the specified level in path in two.
 699  * The path is corrected to point to the appropriate node after the split
 700  *
 701  * Before splitting this tries to make some room in the node by pushing
 702  * left and right, if either one works, it returns right away.
 703  *
 704  * returns 0 on success and < 0 on failure
 705  */
 706 static int split_node(struct ctree_root *root, struct ctree_path *path,
 707                       int level)
 708 {
 709         struct tree_buffer *t;
 710         struct node *c;
 711         struct tree_buffer *split_buffer;
 712         struct node *split;
 713         int mid;
 714         int ret;
 715         int wret;
 716         u32 c_nritems;
 717
 718         t = path->nodes[level];
 719         c = &t->node;
 720         if (t == root->node) {
 721                 /* trying to split the root, lets make a new one */
 722                 ret = insert_new_root(root, path, level + 1);
 723                 if (ret)
 724                         return ret;
 725         }
 726         c_nritems = btrfs_header_nritems(&c->header);
 727         split_buffer = alloc_free_block(root);
 728         split = &split_buffer->node;
 729         btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
 730         btrfs_set_header_blocknr(&split->header, split_buffer->blocknr);
 731         btrfs_set_header_parentid(&split->header,
 732                                btrfs_header_parentid(&root->node->node.header));
 733         mid = (c_nritems + 1) / 2;
 734         memcpy(split->keys, c->keys + mid,
 735                 (c_nritems - mid) * sizeof(struct key));
 736         memcpy(split->blockptrs, c->blockptrs + mid,
 737                 (c_nritems - mid) * sizeof(u64));
 738         btrfs_set_header_nritems(&split->header, c_nritems - mid);
 739         btrfs_set_header_nritems(&c->header, mid);
 740         ret = 0;
 741
 742         BUG_ON(list_empty(&t->dirty));
 743         wret = insert_ptr(root, path, split->keys, split_buffer->blocknr,
 744                           path->slots[level + 1] + 1, level + 1);
 745         if (wret)
 746                 ret = wret;
 747
 748         if (path->slots[level] >= mid) {
 749                 path->slots[level] -= mid;
 750                 tree_block_release(root, t);
 751                 path->nodes[level] = split_buffer;
 752                 path->slots[level + 1] += 1;
 753         } else {
 754                 tree_block_release(root, split_buffer);
 755         }
 756         return ret;
 757 }
 758
 759 /*
 760  * how many bytes are required to store the items in a leaf.  start
 761  * and nr indicate which items in the leaf to check.  This totals up the
 762  * space used both by the item structs and the item data
 763  */
 764 static int leaf_space_used(struct leaf *l, int start, int nr)
 765 {
 766         int data_len;
 767         int end = start + nr - 1;
 768
 769         if (!nr)
 770                 return 0;
 771         data_len = l->items[start].offset + l->items[start].size;
 772         data_len = data_len - l->items[end].offset;
 773         data_len += sizeof(struct item) * nr;
 774         return data_len;
 775 }
 776
 777 /*
 778  * push some data in the path leaf to the right, trying to free up at
 779  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 780  *
 781  * returns 1 if the push failed because the other node didn't have enough
 782  * room, 0 if everything worked out and < 0 if there were major errors.
 783  */
 784 static int push_leaf_right(struct ctree_root *root, struct ctree_path *path,
 785                            int data_size)
 786 {
 787         struct tree_buffer *left_buf = path->nodes[0];
 788         struct leaf *left = &left_buf->leaf;
 789         struct leaf *right;
 790         struct tree_buffer *right_buf;
 791         struct tree_buffer *upper;
 792         int slot;
 793         int i;
 794         int free_space;
 795         int push_space = 0;
 796         int push_items = 0;
 797         struct item *item;
 798         u32 left_nritems;
 799         u32 right_nritems;
 800
 801         slot = path->slots[1];
 802         if (!path->nodes[1]) {
 803                 return 1;
 804         }
 805         upper = path->nodes[1];
 806         if (slot >= btrfs_header_nritems(&upper->node.header) - 1) {
 807                 return 1;
 808         }
 809         right_buf = read_tree_block(root, upper->node.blockptrs[slot + 1]);
 810         right = &right_buf->leaf;
 811         free_space = leaf_free_space(right);
 812         if (free_space < data_size + sizeof(struct item)) {
 813                 tree_block_release(root, right_buf);
 814                 return 1;
 815         }
 816         /* cow and double check */
 817         btrfs_cow_block(root, right_buf, upper, slot + 1, &right_buf);
 818         right = &right_buf->leaf;
 819         free_space = leaf_free_space(right);
 820         if (free_space < data_size + sizeof(struct item)) {
 821                 tree_block_release(root, right_buf);
 822                 return 1;
 823         }
 824
 825         left_nritems = btrfs_header_nritems(&left->header);
 826         for (i = left_nritems - 1; i >= 0; i--) {
 827                 item = left->items + i;
 828                 if (path->slots[0] == i)
 829                         push_space += data_size + sizeof(*item);
 830                 if (item->size + sizeof(*item) + push_space > free_space)
 831                         break;
 832                 push_items++;
 833                 push_space += item->size + sizeof(*item);
 834         }
 835         if (push_items == 0) {
 836                 tree_block_release(root, right_buf);
 837                 return 1;
 838         }
 839         right_nritems = btrfs_header_nritems(&right->header);
 840         /* push left to right */
 841         push_space = left->items[left_nritems - push_items].offset +
 842                      left->items[left_nritems - push_items].size;
 843         push_space -= leaf_data_end(left);
 844         /* make room in the right data area */
 845         memmove(right->data + leaf_data_end(right) - push_space,
 846                 right->data + leaf_data_end(right),
 847                 LEAF_DATA_SIZE - leaf_data_end(right));
 848         /* copy from the left data area */
 849         memcpy(right->data + LEAF_DATA_SIZE - push_space,
 850                 left->data + leaf_data_end(left),
 851                 push_space);
 852         memmove(right->items + push_items, right->items,
 853                 right_nritems * sizeof(struct item));
 854         /* copy the items from left to right */
 855         memcpy(right->items, left->items + left_nritems - push_items,
 856                 push_items * sizeof(struct item));
 857
 858         /* update the item pointers */
 859         right_nritems += push_items;
 860         btrfs_set_header_nritems(&right->header, right_nritems);
 861         push_space = LEAF_DATA_SIZE;
 862         for (i = 0; i < right_nritems; i++) {
 863                 right->items[i].offset = push_space - right->items[i].size;
 864                 push_space = right->items[i].offset;
 865         }
 866         left_nritems -= push_items;
 867         btrfs_set_header_nritems(&left->header, left_nritems);
 868
 869         BUG_ON(list_empty(&left_buf->dirty));
 870         BUG_ON(list_empty(&right_buf->dirty));
 871         memcpy(upper->node.keys + slot + 1,
 872                 &right->items[0].key, sizeof(struct key));
 873         BUG_ON(list_empty(&upper->dirty));
 874
 875         /* then fixup the leaf pointer in the path */
 876         if (path->slots[0] >= left_nritems) {
 877                 path->slots[0] -= left_nritems;
 878                 tree_block_release(root, path->nodes[0]);
 879                 path->nodes[0] = right_buf;
 880                 path->slots[1] += 1;
 881         } else {
 882                 tree_block_release(root, right_buf);
 883         }
 884         return 0;
 885 }
 886 /*
 887  * push some data in the path leaf to the left, trying to free up at
 888  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 889  */
 890 static int push_leaf_left(struct ctree_root *root, struct ctree_path *path,
 891                           int data_size)
 892 {
 893         struct tree_buffer *right_buf = path->nodes[0];
 894         struct leaf *right = &right_buf->leaf;
 895         struct tree_buffer *t;
 896         struct leaf *left;
 897         int slot;
 898         int i;
 899         int free_space;
 900         int push_space = 0;
 901         int push_items = 0;
 902         struct item *item;
 903         u32 old_left_nritems;
 904         int ret = 0;
 905         int wret;
 906
 907         slot = path->slots[1];
 908         if (slot == 0) {
 909                 return 1;
 910         }
 911         if (!path->nodes[1]) {
 912                 return 1;
 913         }
 914         t = read_tree_block(root, path->nodes[1]->node.blockptrs[slot - 1]);
 915         left = &t->leaf;
 916         free_space = leaf_free_space(left);
 917         if (free_space < data_size + sizeof(struct item)) {
 918                 tree_block_release(root, t);
 919                 return 1;
 920         }
 921
 922         /* cow and double check */
 923         btrfs_cow_block(root, t, path->nodes[1], slot - 1, &t);
 924         left = &t->leaf;
 925         free_space = leaf_free_space(left);
 926         if (free_space < data_size + sizeof(struct item)) {
 927                 tree_block_release(root, t);
 928                 return 1;
 929         }
 930
 931         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
 932                 item = right->items + i;
 933                 if (path->slots[0] == i)
 934                         push_space += data_size + sizeof(*item);
 935                 if (item->size + sizeof(*item) + push_space > free_space)
 936                         break;
 937                 push_items++;
 938                 push_space += item->size + sizeof(*item);
 939         }
 940         if (push_items == 0) {
 941                 tree_block_release(root, t);
 942                 return 1;
 943         }
 944         /* push data from right to left */
 945         memcpy(left->items + btrfs_header_nritems(&left->header),
 946                 right->items, push_items * sizeof(struct item));
 947         push_space = LEAF_DATA_SIZE - right->items[push_items -1].offset;
 948         memcpy(left->data + leaf_data_end(left) - push_space,
 949                 right->data + right->items[push_items - 1].offset,
 950                 push_space);
 951         old_left_nritems = btrfs_header_nritems(&left->header);
 952         BUG_ON(old_left_nritems < 0);
 953
 954         for(i = old_left_nritems; i < old_left_nritems + push_items; i++) {
 955                 left->items[i].offset -= LEAF_DATA_SIZE -
 956                         left->items[old_left_nritems -1].offset;
 957         }
 958         btrfs_set_header_nritems(&left->header, old_left_nritems + push_items);
 959
 960         /* fixup right node */
 961         push_space = right->items[push_items-1].offset - leaf_data_end(right);
 962         memmove(right->data + LEAF_DATA_SIZE - push_space, right->data +
 963                 leaf_data_end(right), push_space);
 964         memmove(right->items, right->items + push_items,
 965                 (btrfs_header_nritems(&right->header) - push_items) *
 966                 sizeof(struct item));
 967         btrfs_set_header_nritems(&right->header,
 968                                  btrfs_header_nritems(&right->header) -
 969                                  push_items);
 970         push_space = LEAF_DATA_SIZE;
 971
 972         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
 973                 right->items[i].offset = push_space - right->items[i].size;
 974                 push_space = right->items[i].offset;
 975         }
 976
 977         BUG_ON(list_empty(&t->dirty));
 978         BUG_ON(list_empty(&right_buf->dirty));
 979
 980         wret = fixup_low_keys(root, path, &right->items[0].key, 1);
 981         if (wret)
 982                 ret = wret;
 983
 984         /* then fixup the leaf pointer in the path */
 985         if (path->slots[0] < push_items) {
 986                 path->slots[0] += old_left_nritems;
 987                 tree_block_release(root, path->nodes[0]);
 988                 path->nodes[0] = t;
 989                 path->slots[1] -= 1;
 990         } else {
 991                 tree_block_release(root, t);
 992                 path->slots[0] -= push_items;
 993         }
 994         BUG_ON(path->slots[0] < 0);
 995         return ret;
 996 }
 997
 998 /*
 999  * split the path's leaf in two, making sure there is at least data_size
1000  * available for the resulting leaf level of the path.
1001  *
1002  * returns 0 if all went well and < 0 on failure.
1003  */
1004 static int split_leaf(struct ctree_root *root, struct ctree_path *path,
1005                       int data_size)
1006 {
1007         struct tree_buffer *l_buf;
1008         struct leaf *l;
1009         u32 nritems;
1010         int mid;
1011         int slot;
1012         struct leaf *right;
1013         struct tree_buffer *right_buffer;
1014         int space_needed = data_size + sizeof(struct item);
1015         int data_copy_size;
1016         int rt_data_off;
1017         int i;
1018         int ret;
1019         int wret;
1020
1021         l_buf = path->nodes[0];
1022         l = &l_buf->leaf;
1023
1024         /* did the pushes work? */
1025         if (leaf_free_space(l) >= sizeof(struct item) + data_size)
1026                 return 0;
1027
1028         if (!path->nodes[1]) {
1029                 ret = insert_new_root(root, path, 1);
1030                 if (ret)
1031                         return ret;
1032         }
1033         slot = path->slots[0];
1034         nritems = btrfs_header_nritems(&l->header);
1035         mid = (nritems + 1)/ 2;
1036         right_buffer = alloc_free_block(root);
1037         BUG_ON(!right_buffer);
1038         BUG_ON(mid == nritems);
1039         right = &right_buffer->leaf;
1040         memset(right, 0, sizeof(*right));
1041         if (mid <= slot) {
1042                 /* FIXME, just alloc a new leaf here */
1043                 if (leaf_space_used(l, mid, nritems - mid) + space_needed >
1044                         LEAF_DATA_SIZE)
1045                         BUG();
1046         } else {
1047                 /* FIXME, just alloc a new leaf here */
1048                 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1049                         LEAF_DATA_SIZE)
1050                         BUG();
1051         }
1052         btrfs_set_header_nritems(&right->header, nritems - mid);
1053         btrfs_set_header_blocknr(&right->header, right_buffer->blocknr);
1054         btrfs_set_header_level(&right->header, 0);
1055         btrfs_set_header_parentid(&right->header,
1056                                btrfs_header_parentid(&root->node->node.header));
1057         data_copy_size = l->items[mid].offset + l->items[mid].size -
1058                          leaf_data_end(l);
1059         memcpy(right->items, l->items + mid,
1060                (nritems - mid) * sizeof(struct item));
1061         memcpy(right->data + LEAF_DATA_SIZE - data_copy_size,
1062                l->data + leaf_data_end(l), data_copy_size);
1063         rt_data_off = LEAF_DATA_SIZE -
1064                      (l->items[mid].offset + l->items[mid].size);
1065
1066         for (i = 0; i < btrfs_header_nritems(&right->header); i++)
1067                 right->items[i].offset += rt_data_off;
1068
1069         btrfs_set_header_nritems(&l->header, mid);
1070         ret = 0;
1071         wret = insert_ptr(root, path, &right->items[0].key,
1072                           right_buffer->blocknr, path->slots[1] + 1, 1);
1073         if (wret)
1074                 ret = wret;
1075         BUG_ON(list_empty(&right_buffer->dirty));
1076         BUG_ON(list_empty(&l_buf->dirty));
1077         BUG_ON(path->slots[0] != slot);
1078         if (mid <= slot) {
1079                 tree_block_release(root, path->nodes[0]);
1080                 path->nodes[0] = right_buffer;
1081                 path->slots[0] -= mid;
1082                 path->slots[1] += 1;
1083         } else
1084                 tree_block_release(root, right_buffer);
1085         BUG_ON(path->slots[0] < 0);
1086         return ret;
1087 }
1088
1089 /*
1090  * Given a key and some data, insert an item into the tree.
1091  * This does all the path init required, making room in the tree if needed.
1092  */
1093 int insert_item(struct ctree_root *root, struct key *key,
1094                           void *data, int data_size)
1095 {
1096         int ret = 0;
1097         int slot;
1098         int slot_orig;
1099         struct leaf *leaf;
1100         struct tree_buffer *leaf_buf;
1101         u32 nritems;
1102         unsigned int data_end;
1103         struct ctree_path path;
1104
1105         /* create a root if there isn't one */
1106         if (!root->node)
1107                 BUG();
1108         init_path(&path);
1109         ret = search_slot(root, key, &path, data_size, 1);
1110         if (ret == 0) {
1111                 release_path(root, &path);
1112                 return -EEXIST;
1113         }
1114         if (ret < 0)
1115                 goto out;
1116
1117         slot_orig = path.slots[0];
1118         leaf_buf = path.nodes[0];
1119         leaf = &leaf_buf->leaf;
1120
1121         nritems = btrfs_header_nritems(&leaf->header);
1122         data_end = leaf_data_end(leaf);
1123
1124         if (leaf_free_space(leaf) <  sizeof(struct item) + data_size)
1125                 BUG();
1126
1127         slot = path.slots[0];
1128         BUG_ON(slot < 0);
1129         if (slot != nritems) {
1130                 int i;
1131                 unsigned int old_data = leaf->items[slot].offset +
1132                                         leaf->items[slot].size;
1133
1134                 /*
1135                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
1136                  */
1137                 /* first correct the data pointers */
1138                 for (i = slot; i < nritems; i++)
1139                         leaf->items[i].offset -= data_size;
1140
1141                 /* shift the items */
1142                 memmove(leaf->items + slot + 1, leaf->items + slot,
1143                         (nritems - slot) * sizeof(struct item));
1144
1145                 /* shift the data */
1146                 memmove(leaf->data + data_end - data_size, leaf->data +
1147                         data_end, old_data - data_end);
1148                 data_end = old_data;
1149         }
1150         /* copy the new data in */
1151         memcpy(&leaf->items[slot].key, key, sizeof(struct key));
1152         leaf->items[slot].offset = data_end - data_size;
1153         leaf->items[slot].size = data_size;
1154         memcpy(leaf->data + data_end - data_size, data, data_size);
1155         btrfs_set_header_nritems(&leaf->header, nritems + 1);
1156
1157         ret = 0;
1158         if (slot == 0)
1159                 ret = fixup_low_keys(root, &path, key, 1);
1160
1161         BUG_ON(list_empty(&leaf_buf->dirty));
1162         if (leaf_free_space(leaf) < 0)
1163                 BUG();
1164         check_leaf(&path, 0);
1165 out:
1166         release_path(root, &path);
1167         return ret;
1168 }
1169
1170 /*
1171  * delete the pointer from a given node.
1172  *
1173  * If the delete empties a node, the node is removed from the tree,
1174  * continuing all the way the root if required.  The root is converted into
1175  * a leaf if all the nodes are emptied.
1176  */
1177 static int del_ptr(struct ctree_root *root, struct ctree_path *path, int level,
1178                    int slot)
1179 {
1180         struct node *node;
1181         struct tree_buffer *parent = path->nodes[level];
1182         u32 nritems;
1183         int ret = 0;
1184         int wret;
1185
1186         node = &parent->node;
1187         nritems = btrfs_header_nritems(&node->header);
1188         if (slot != nritems -1) {
1189                 memmove(node->keys + slot, node->keys + slot + 1,
1190                         sizeof(struct key) * (nritems - slot - 1));
1191                 memmove(node->blockptrs + slot,
1192                         node->blockptrs + slot + 1,
1193                         sizeof(u64) * (nritems - slot - 1));
1194         }
1195         nritems--;
1196         btrfs_set_header_nritems(&node->header, nritems);
1197         if (nritems == 0 && parent == root->node) {
1198                 BUG_ON(btrfs_header_level(&root->node->node.header) != 1);
1199                 /* just turn the root into a leaf and break */
1200                 btrfs_set_header_level(&root->node->node.header, 0);
1201         } else if (slot == 0) {
1202                 wret = fixup_low_keys(root, path, node->keys, level + 1);
1203                 if (wret)
1204                         ret = wret;
1205         }
1206         BUG_ON(list_empty(&parent->dirty));
1207         return ret;
1208 }
1209
1210 /*
1211  * delete the item at the leaf level in path.  If that empties
1212  * the leaf, remove it from the tree
1213  */
1214 int del_item(struct ctree_root *root, struct ctree_path *path)
1215 {
1216         int slot;
1217         struct leaf *leaf;
1218         struct tree_buffer *leaf_buf;
1219         int doff;
1220         int dsize;
1221         int ret = 0;
1222         int wret;
1223         u32 nritems;
1224
1225         leaf_buf = path->nodes[0];
1226         leaf = &leaf_buf->leaf;
1227         slot = path->slots[0];
1228         doff = leaf->items[slot].offset;
1229         dsize = leaf->items[slot].size;
1230         nritems = btrfs_header_nritems(&leaf->header);
1231
1232         if (slot != nritems - 1) {
1233                 int i;
1234                 int data_end = leaf_data_end(leaf);
1235                 memmove(leaf->data + data_end + dsize,
1236                         leaf->data + data_end,
1237                         doff - data_end);
1238                 for (i = slot + 1; i < nritems; i++)
1239                         leaf->items[i].offset += dsize;
1240                 memmove(leaf->items + slot, leaf->items + slot + 1,
1241                         sizeof(struct item) *
1242                         (nritems - slot - 1));
1243         }
1244         btrfs_set_header_nritems(&leaf->header, nritems - 1);
1245         nritems--;
1246         /* delete the leaf if we've emptied it */
1247         if (nritems == 0) {
1248                 if (leaf_buf == root->node) {
1249                         btrfs_set_header_level(&leaf->header, 0);
1250                         BUG_ON(list_empty(&leaf_buf->dirty));
1251                 } else {
1252                         clean_tree_block(root, leaf_buf);
1253                         wret = del_ptr(root, path, 1, path->slots[1]);
1254                         if (wret)
1255                                 ret = wret;
1256                         wret = free_extent(root, leaf_buf->blocknr, 1);
1257                         if (wret)
1258                                 ret = wret;
1259                 }
1260         } else {
1261                 int used = leaf_space_used(leaf, 0, nritems);
1262                 if (slot == 0) {
1263                         wret = fixup_low_keys(root, path,
1264                                                    &leaf->items[0].key, 1);
1265                         if (wret)
1266                                 ret = wret;
1267                 }
1268                 BUG_ON(list_empty(&leaf_buf->dirty));
1269
1270                 /* delete the leaf if it is mostly empty */
1271                 if (used < LEAF_DATA_SIZE / 3) {
1272                         /* push_leaf_left fixes the path.
1273                          * make sure the path still points to our leaf
1274                          * for possible call to del_ptr below
1275                          */
1276                         slot = path->slots[1];
1277                         leaf_buf->count++;
1278                         wret = push_leaf_left(root, path, 1);
1279                         if (wret < 0)
1280                                 ret = wret;
1281                         if (path->nodes[0] == leaf_buf &&
1282                             btrfs_header_nritems(&leaf->header)) {
1283                                 wret = push_leaf_right(root, path, 1);
1284                                 if (wret < 0)
1285                                         ret = wret;
1286                         }
1287                         if (btrfs_header_nritems(&leaf->header) == 0) {
1288                                 u64 blocknr = leaf_buf->blocknr;
1289                                 clean_tree_block(root, leaf_buf);
1290                                 wret = del_ptr(root, path, 1, slot);
1291                                 if (wret)
1292                                         ret = wret;
1293                                 tree_block_release(root, leaf_buf);
1294                                 wret = free_extent(root, blocknr, 1);
1295                                 if (wret)
1296                                         ret = wret;
1297                         } else {
1298                                 tree_block_release(root, leaf_buf);
1299                         }
1300                 }
1301         }
1302         return ret;
1303 }
1304
1305 /*
1306  * walk up the tree as far as required to find the next leaf.
1307  * returns 0 if it found something or 1 if there are no greater leaves.
1308  * returns < 0 on io errors.
1309  */
1310 int next_leaf(struct ctree_root *root, struct ctree_path *path)
1311 {
1312         int slot;
1313         int level = 1;
1314         u64 blocknr;
1315         struct tree_buffer *c;
1316         struct tree_buffer *next = NULL;
1317
1318         while(level < MAX_LEVEL) {
1319                 if (!path->nodes[level])
1320                         return 1;
1321                 slot = path->slots[level] + 1;
1322                 c = path->nodes[level];
1323                 if (slot >= btrfs_header_nritems(&c->node.header)) {
1324                         level++;
1325                         continue;
1326                 }
1327                 blocknr = c->node.blockptrs[slot];
1328                 if (next)
1329                         tree_block_release(root, next);
1330                 next = read_tree_block(root, blocknr);
1331                 break;
1332         }
1333         path->slots[level] = slot;
1334         while(1) {
1335                 level--;
1336                 c = path->nodes[level];
1337                 tree_block_release(root, c);
1338                 path->nodes[level] = next;
1339                 path->slots[level] = 0;
1340                 if (!level)
1341                         break;
1342                 next = read_tree_block(root, next->node.blockptrs[0]);
1343         }
1344         return 0;
1345 }
1346
1347