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