fs/btrfs/ctree.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * BTRFS filesystem implementation for U-Boot
   4  *
   5  * 2017 Marek Behún, CZ.NIC, kabel@kernel.org
   6  */
   7
   8 #include <linux/kernel.h>
   9 #include <log.h>
  10 #include <malloc.h>
  11 #include <memalign.h>
  12 #include "btrfs.h"
  13 #include "disk-io.h"
  14
  15 static const struct btrfs_csum {
  16         u16 size;
  17         const char name[14];
  18 } btrfs_csums[] = {
  19         [BTRFS_CSUM_TYPE_CRC32]         = {  4, "crc32c" },
  20         [BTRFS_CSUM_TYPE_XXHASH]        = {  8, "xxhash64" },
  21         [BTRFS_CSUM_TYPE_SHA256]        = { 32, "sha256" },
  22         [BTRFS_CSUM_TYPE_BLAKE2]        = { 32, "blake2" },
  23 };
  24
  25 u16 btrfs_super_csum_size(const struct btrfs_super_block *sb)
  26 {
  27         const u16 csum_type = btrfs_super_csum_type(sb);
  28
  29         return btrfs_csums[csum_type].size;
  30 }
  31
  32 const char *btrfs_super_csum_name(u16 csum_type)
  33 {
  34         return btrfs_csums[csum_type].name;
  35 }
  36
  37 size_t btrfs_super_num_csums(void)
  38 {
  39         return ARRAY_SIZE(btrfs_csums);
  40 }
  41
  42 u16 btrfs_csum_type_size(u16 csum_type)
  43 {
  44         return btrfs_csums[csum_type].size;
  45 }
  46
  47 struct btrfs_path *btrfs_alloc_path(void)
  48 {
  49         struct btrfs_path *path;
  50         path = kzalloc(sizeof(struct btrfs_path), GFP_NOFS);
  51         return path;
  52 }
  53
  54 void btrfs_free_path(struct btrfs_path *p)
  55 {
  56         if (!p)
  57                 return;
  58         btrfs_release_path(p);
  59         kfree(p);
  60 }
  61
  62 void btrfs_release_path(struct btrfs_path *p)
  63 {
  64         int i;
  65         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  66                 if (!p->nodes[i])
  67                         continue;
  68                 free_extent_buffer(p->nodes[i]);
  69         }
  70         memset(p, 0, sizeof(*p));
  71 }
  72
  73 int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
  74 {
  75         if (k1->objectid > k2->objectid)
  76                 return 1;
  77         if (k1->objectid < k2->objectid)
  78                 return -1;
  79         if (k1->type > k2->type)
  80                 return 1;
  81         if (k1->type < k2->type)
  82                 return -1;
  83         if (k1->offset > k2->offset)
  84                 return 1;
  85         if (k1->offset < k2->offset)
  86                 return -1;
  87         return 0;
  88 }
  89
  90 static int btrfs_comp_keys(struct btrfs_disk_key *disk,
  91                              const struct btrfs_key *k2)
  92 {
  93         struct btrfs_key k1;
  94
  95         btrfs_disk_key_to_cpu(&k1, disk);
  96         return btrfs_comp_cpu_keys(&k1, k2);
  97 }
  98
  99 enum btrfs_tree_block_status
 100 btrfs_check_node(struct btrfs_fs_info *fs_info,
 101                  struct btrfs_disk_key *parent_key, struct extent_buffer *buf)
 102 {
 103         int i;
 104         struct btrfs_key cpukey;
 105         struct btrfs_disk_key key;
 106         u32 nritems = btrfs_header_nritems(buf);
 107         enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS;
 108
 109         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(fs_info))
 110                 goto fail;
 111
 112         ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY;
 113         if (parent_key && parent_key->type) {
 114                 btrfs_node_key(buf, &key, 0);
 115                 if (memcmp(parent_key, &key, sizeof(key)))
 116                         goto fail;
 117         }
 118         ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
 119         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 120                 btrfs_node_key(buf, &key, i);
 121                 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
 122                 if (btrfs_comp_keys(&key, &cpukey) >= 0)
 123                         goto fail;
 124         }
 125         return BTRFS_TREE_BLOCK_CLEAN;
 126 fail:
 127         return ret;
 128 }
 129
 130 enum btrfs_tree_block_status
 131 btrfs_check_leaf(struct btrfs_fs_info *fs_info,
 132                  struct btrfs_disk_key *parent_key, struct extent_buffer *buf)
 133 {
 134         int i;
 135         struct btrfs_key cpukey;
 136         struct btrfs_disk_key key;
 137         u32 nritems = btrfs_header_nritems(buf);
 138         enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS;
 139
 140         if (nritems * sizeof(struct btrfs_item) > buf->len)  {
 141                 fprintf(stderr, "invalid number of items %llu\n",
 142                         (unsigned long long)buf->start);
 143                 goto fail;
 144         }
 145
 146         if (btrfs_header_level(buf) != 0) {
 147                 ret = BTRFS_TREE_BLOCK_INVALID_LEVEL;
 148                 fprintf(stderr, "leaf is not a leaf %llu\n",
 149                        (unsigned long long)btrfs_header_bytenr(buf));
 150                 goto fail;
 151         }
 152         if (btrfs_leaf_free_space(buf) < 0) {
 153                 ret = BTRFS_TREE_BLOCK_INVALID_FREE_SPACE;
 154                 fprintf(stderr, "leaf free space incorrect %llu %d\n",
 155                         (unsigned long long)btrfs_header_bytenr(buf),
 156                         btrfs_leaf_free_space(buf));
 157                 goto fail;
 158         }
 159
 160         if (nritems == 0)
 161                 return BTRFS_TREE_BLOCK_CLEAN;
 162
 163         btrfs_item_key(buf, &key, 0);
 164         if (parent_key && parent_key->type &&
 165             memcmp(parent_key, &key, sizeof(key))) {
 166                 ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY;
 167                 fprintf(stderr, "leaf parent key incorrect %llu\n",
 168                        (unsigned long long)btrfs_header_bytenr(buf));
 169                 goto fail;
 170         }
 171         for (i = 0; nritems > 1 && i < nritems - 1; i++) {
 172                 btrfs_item_key(buf, &key, i);
 173                 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
 174                 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
 175                         ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
 176                         fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
 177                         goto fail;
 178                 }
 179                 if (btrfs_item_offset_nr(buf, i) !=
 180                         btrfs_item_end_nr(buf, i + 1)) {
 181                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 182                         fprintf(stderr, "incorrect offsets %u %u\n",
 183                                 btrfs_item_offset_nr(buf, i),
 184                                 btrfs_item_end_nr(buf, i + 1));
 185                         goto fail;
 186                 }
 187                 if (i == 0 && btrfs_item_end_nr(buf, i) !=
 188                     BTRFS_LEAF_DATA_SIZE(fs_info)) {
 189                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 190                         fprintf(stderr, "bad item end %u wanted %u\n",
 191                                 btrfs_item_end_nr(buf, i),
 192                                 (unsigned)BTRFS_LEAF_DATA_SIZE(fs_info));
 193                         goto fail;
 194                 }
 195         }
 196
 197         for (i = 0; i < nritems; i++) {
 198                 if (btrfs_item_end_nr(buf, i) >
 199                                 BTRFS_LEAF_DATA_SIZE(fs_info)) {
 200                         btrfs_item_key(buf, &key, 0);
 201                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 202                         fprintf(stderr, "slot end outside of leaf %llu > %llu\n",
 203                                 (unsigned long long)btrfs_item_end_nr(buf, i),
 204                                 (unsigned long long)BTRFS_LEAF_DATA_SIZE(
 205                                         fs_info));
 206                         goto fail;
 207                 }
 208         }
 209
 210         return BTRFS_TREE_BLOCK_CLEAN;
 211 fail:
 212         return ret;
 213 }
 214
 215 static int noinline check_block(struct btrfs_fs_info *fs_info,
 216                                 struct btrfs_path *path, int level)
 217 {
 218         struct btrfs_disk_key key;
 219         struct btrfs_disk_key *key_ptr = NULL;
 220         struct extent_buffer *parent;
 221         enum btrfs_tree_block_status ret;
 222
 223         if (path->nodes[level + 1]) {
 224                 parent = path->nodes[level + 1];
 225                 btrfs_node_key(parent, &key, path->slots[level + 1]);
 226                 key_ptr = &key;
 227         }
 228         if (level == 0)
 229                 ret = btrfs_check_leaf(fs_info, key_ptr, path->nodes[0]);
 230         else
 231                 ret = btrfs_check_node(fs_info, key_ptr, path->nodes[level]);
 232         if (ret == BTRFS_TREE_BLOCK_CLEAN)
 233                 return 0;
 234         return -EIO;
 235 }
 236
 237 /*
 238  * search for key in the extent_buffer.  The items start at offset p,
 239  * and they are item_size apart.  There are 'max' items in p.
 240  *
 241  * the slot in the array is returned via slot, and it points to
 242  * the place where you would insert key if it is not found in
 243  * the array.
 244  *
 245  * slot may point to max if the key is bigger than all of the keys
 246  */
 247 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
 248                               int item_size, const struct btrfs_key *key,
 249                               int max, int *slot)
 250 {
 251         int low = 0;
 252         int high = max;
 253         int mid;
 254         int ret;
 255         unsigned long offset;
 256         struct btrfs_disk_key *tmp;
 257
 258         while(low < high) {
 259                 mid = (low + high) / 2;
 260                 offset = p + mid * item_size;
 261
 262                 tmp = (struct btrfs_disk_key *)(eb->data + offset);
 263                 ret = btrfs_comp_keys(tmp, key);
 264
 265                 if (ret < 0)
 266                         low = mid + 1;
 267                 else if (ret > 0)
 268                         high = mid;
 269                 else {
 270                         *slot = mid;
 271                         return 0;
 272                 }
 273         }
 274         *slot = low;
 275         return 1;
 276 }
 277
 278 /*
 279  * simple bin_search frontend that does the right thing for
 280  * leaves vs nodes
 281  */
 282 int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key,
 283                      int *slot)
 284 {
 285         if (btrfs_header_level(eb) == 0)
 286                 return generic_bin_search(eb,
 287                                           offsetof(struct btrfs_leaf, items),
 288                                           sizeof(struct btrfs_item),
 289                                           key, btrfs_header_nritems(eb),
 290                                           slot);
 291         else
 292                 return generic_bin_search(eb,
 293                                           offsetof(struct btrfs_node, ptrs),
 294                                           sizeof(struct btrfs_key_ptr),
 295                                           key, btrfs_header_nritems(eb),
 296                                           slot);
 297 }
 298
 299 struct extent_buffer *read_node_slot(struct btrfs_fs_info *fs_info,
 300                                    struct extent_buffer *parent, int slot)
 301 {
 302         struct extent_buffer *ret;
 303         int level = btrfs_header_level(parent);
 304
 305         if (slot < 0)
 306                 return NULL;
 307         if (slot >= btrfs_header_nritems(parent))
 308                 return NULL;
 309
 310         if (level == 0)
 311                 return NULL;
 312
 313         ret = read_tree_block(fs_info, btrfs_node_blockptr(parent, slot),
 314                        btrfs_node_ptr_generation(parent, slot));
 315         if (!extent_buffer_uptodate(ret))
 316                 return ERR_PTR(-EIO);
 317
 318         if (btrfs_header_level(ret) != level - 1) {
 319                 error("child eb corrupted: parent bytenr=%llu item=%d parent level=%d child level=%d",
 320                       btrfs_header_bytenr(parent), slot,
 321                       btrfs_header_level(parent), btrfs_header_level(ret));
 322                 free_extent_buffer(ret);
 323                 return ERR_PTR(-EIO);
 324         }
 325         return ret;
 326 }
 327
 328 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path,
 329                 u64 iobjectid, u64 ioff, u8 key_type,
 330                 struct btrfs_key *found_key)
 331 {
 332         int ret;
 333         struct btrfs_key key;
 334         struct extent_buffer *eb;
 335         struct btrfs_path *path;
 336
 337         key.type = key_type;
 338         key.objectid = iobjectid;
 339         key.offset = ioff;
 340
 341         if (found_path == NULL) {
 342                 path = btrfs_alloc_path();
 343                 if (!path)
 344                         return -ENOMEM;
 345         } else
 346                 path = found_path;
 347
 348         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
 349         if ((ret < 0) || (found_key == NULL))
 350                 goto out;
 351
 352         eb = path->nodes[0];
 353         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
 354                 ret = btrfs_next_leaf(fs_root, path);
 355                 if (ret)
 356                         goto out;
 357                 eb = path->nodes[0];
 358         }
 359
 360         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
 361         if (found_key->type != key.type ||
 362                         found_key->objectid != key.objectid) {
 363                 ret = 1;
 364                 goto out;
 365         }
 366
 367 out:
 368         if (path != found_path)
 369                 btrfs_free_path(path);
 370         return ret;
 371 }
 372
 373 /*
 374  * look for key in the tree.  path is filled in with nodes along the way
 375  * if key is found, we return zero and you can find the item in the leaf
 376  * level of the path (level 0)
 377  *
 378  * If the key isn't found, the path points to the slot where it should
 379  * be inserted, and 1 is returned.  If there are other errors during the
 380  * search a negative error number is returned.
 381  *
 382  * if ins_len > 0, nodes and leaves will be split as we walk down the
 383  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
 384  * possible)
 385  *
 386  * NOTE: This version has no COW ability, thus we expect trans == NULL,
 387  * ins_len == 0 and cow == 0.
 388  */
 389 int btrfs_search_slot(struct btrfs_trans_handle *trans,
 390                 struct btrfs_root *root, const struct btrfs_key *key,
 391                 struct btrfs_path *p, int ins_len, int cow)
 392 {
 393         struct extent_buffer *b;
 394         int slot;
 395         int ret;
 396         int level;
 397         struct btrfs_fs_info *fs_info = root->fs_info;
 398         u8 lowest_level = 0;
 399
 400         assert(trans == NULL && ins_len == 0 && cow == 0);
 401         lowest_level = p->lowest_level;
 402         WARN_ON(lowest_level && ins_len > 0);
 403         WARN_ON(p->nodes[0] != NULL);
 404
 405         b = root->node;
 406         extent_buffer_get(b);
 407         while (b) {
 408                 level = btrfs_header_level(b);
 409                 /*
 410                 if (cow) {
 411                         int wret;
 412                         wret = btrfs_cow_block(trans, root, b,
 413                                                p->nodes[level + 1],
 414                                                p->slots[level + 1],
 415                                                &b);
 416                         if (wret) {
 417                                 free_extent_buffer(b);
 418                                 return wret;
 419                         }
 420                 }
 421                 */
 422                 BUG_ON(!cow && ins_len);
 423                 if (level != btrfs_header_level(b))
 424                         WARN_ON(1);
 425                 level = btrfs_header_level(b);
 426                 p->nodes[level] = b;
 427                 ret = check_block(fs_info, p, level);
 428                 if (ret)
 429                         return -1;
 430                 ret = btrfs_bin_search(b, key, &slot);
 431                 if (level != 0) {
 432                         if (ret && slot > 0)
 433                                 slot -= 1;
 434                         p->slots[level] = slot;
 435                         /*
 436                         if ((p->search_for_split || ins_len > 0) &&
 437                             btrfs_header_nritems(b) >=
 438                             BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) {
 439                                 int sret = split_node(trans, root, p, level);
 440                                 BUG_ON(sret > 0);
 441                                 if (sret)
 442                                         return sret;
 443                                 b = p->nodes[level];
 444                                 slot = p->slots[level];
 445                         } else if (ins_len < 0) {
 446                                 int sret = balance_level(trans, root, p,
 447                                                          level);
 448                                 if (sret)
 449                                         return sret;
 450                                 b = p->nodes[level];
 451                                 if (!b) {
 452                                         btrfs_release_path(p);
 453                                         goto again;
 454                                 }
 455                                 slot = p->slots[level];
 456                                 BUG_ON(btrfs_header_nritems(b) == 1);
 457                         }
 458                         */
 459                         /* this is only true while dropping a snapshot */
 460                         if (level == lowest_level)
 461                                 break;
 462
 463                         b = read_node_slot(fs_info, b, slot);
 464                         if (!extent_buffer_uptodate(b))
 465                                 return -EIO;
 466                 } else {
 467                         p->slots[level] = slot;
 468                         /*
 469                         if (ins_len > 0 &&
 470                             ins_len > btrfs_leaf_free_space(b)) {
 471                                 int sret = split_leaf(trans, root, key,
 472                                                       p, ins_len, ret == 0);
 473                                 BUG_ON(sret > 0);
 474                                 if (sret)
 475                                         return sret;
 476                         }
 477                         */
 478                         return ret;
 479                 }
 480         }
 481         return 1;
 482 }
 483
 484 /*
 485  * Helper to use instead of search slot if no exact match is needed but
 486  * instead the next or previous item should be returned.
 487  * When find_higher is true, the next higher item is returned, the next lower
 488  * otherwise.
 489  * When return_any and find_higher are both true, and no higher item is found,
 490  * return the next lower instead.
 491  * When return_any is true and find_higher is false, and no lower item is found,
 492  * return the next higher instead.
 493  * It returns 0 if any item is found, 1 if none is found (tree empty), and
 494  * < 0 on error
 495  */
 496 int btrfs_search_slot_for_read(struct btrfs_root *root,
 497                                const struct btrfs_key *key,
 498                                struct btrfs_path *p, int find_higher,
 499                                int return_any)
 500 {
 501         int ret;
 502         struct extent_buffer *leaf;
 503
 504 again:
 505         ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
 506         if (ret <= 0)
 507                  return ret;
 508         /*
 509          * A return value of 1 means the path is at the position where the item
 510          * should be inserted. Normally this is the next bigger item, but in
 511          * case the previous item is the last in a leaf, path points to the
 512          * first free slot in the previous leaf, i.e. at an invalid item.
 513          */
 514         leaf = p->nodes[0];
 515
 516         if (find_higher) {
 517                 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
 518                         ret = btrfs_next_leaf(root, p);
 519                         if (ret <= 0)
 520                                 return ret;
 521                         if (!return_any)
 522                                 return 1;
 523                         /*
 524                          * No higher item found, return the next lower instead
 525                          */
 526                         return_any = 0;
 527                         find_higher = 0;
 528                         btrfs_release_path(p);
 529                         goto again;
 530                 }
 531         } else {
 532                 if (p->slots[0] == 0) {
 533                         ret = btrfs_prev_leaf(root, p);
 534                         if (ret < 0)
 535                                 return ret;
 536                         if (!ret) {
 537                                 leaf = p->nodes[0];
 538                                 if (p->slots[0] == btrfs_header_nritems(leaf))
 539                                         p->slots[0]--;
 540                                 return 0;
 541                         }
 542                         if (!return_any)
 543                                 return 1;
 544                         /*
 545                          * No lower item found, return the next higher instead
 546                          */
 547                         return_any = 0;
 548                         find_higher = 1;
 549                         btrfs_release_path(p);
 550                         goto again;
 551                 } else {
 552                         --p->slots[0];
 553                 }
 554         }
 555         return 0;
 556 }
 557
 558 /*
 559  * how many bytes are required to store the items in a leaf.  start
 560  * and nr indicate which items in the leaf to check.  This totals up the
 561  * space used both by the item structs and the item data
 562  */
 563 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
 564 {
 565         int data_len;
 566         int nritems = btrfs_header_nritems(l);
 567         int end = min(nritems, start + nr) - 1;
 568
 569         if (!nr)
 570                 return 0;
 571         data_len = btrfs_item_end_nr(l, start);
 572         data_len = data_len - btrfs_item_offset_nr(l, end);
 573         data_len += sizeof(struct btrfs_item) * nr;
 574         WARN_ON(data_len < 0);
 575         return data_len;
 576 }
 577
 578 /*
 579  * The space between the end of the leaf items and
 580  * the start of the leaf data.  IOW, how much room
 581  * the leaf has left for both items and data
 582  */
 583 int btrfs_leaf_free_space(struct extent_buffer *leaf)
 584 {
 585         int nritems = btrfs_header_nritems(leaf);
 586         u32 leaf_data_size;
 587         int ret;
 588
 589         BUG_ON(leaf->fs_info && leaf->fs_info->nodesize != leaf->len);
 590         leaf_data_size = __BTRFS_LEAF_DATA_SIZE(leaf->len);
 591         ret = leaf_data_size - leaf_space_used(leaf, 0 ,nritems);
 592         if (ret < 0) {
 593                 printk("leaf free space ret %d, leaf data size %u, used %d nritems %d\n",
 594                        ret, leaf_data_size, leaf_space_used(leaf, 0, nritems),
 595                        nritems);
 596         }
 597         return ret;
 598 }
 599
 600 /*
 601  * walk up the tree as far as required to find the previous leaf.
 602  * returns 0 if it found something or 1 if there are no lesser leaves.
 603  * returns < 0 on io errors.
 604  */
 605 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
 606 {
 607         int slot;
 608         int level = 1;
 609         struct extent_buffer *c;
 610         struct extent_buffer *next = NULL;
 611         struct btrfs_fs_info *fs_info = root->fs_info;
 612
 613         while(level < BTRFS_MAX_LEVEL) {
 614                 if (!path->nodes[level])
 615                         return 1;
 616
 617                 slot = path->slots[level];
 618                 c = path->nodes[level];
 619                 if (slot == 0) {
 620                         level++;
 621                         if (level == BTRFS_MAX_LEVEL)
 622                                 return 1;
 623                         continue;
 624                 }
 625                 slot--;
 626
 627                 next = read_node_slot(fs_info, c, slot);
 628                 if (!extent_buffer_uptodate(next)) {
 629                         if (IS_ERR(next))
 630                                 return PTR_ERR(next);
 631                         return -EIO;
 632                 }
 633                 break;
 634         }
 635         path->slots[level] = slot;
 636         while(1) {
 637                 level--;
 638                 c = path->nodes[level];
 639                 free_extent_buffer(c);
 640                 slot = btrfs_header_nritems(next);
 641                 if (slot != 0)
 642                         slot--;
 643                 path->nodes[level] = next;
 644                 path->slots[level] = slot;
 645                 if (!level)
 646                         break;
 647                 next = read_node_slot(fs_info, next, slot);
 648                 if (!extent_buffer_uptodate(next)) {
 649                         if (IS_ERR(next))
 650                                 return PTR_ERR(next);
 651                         return -EIO;
 652                 }
 653         }
 654         return 0;
 655 }
 656
 657 /*
 658  * Walk up the tree as far as necessary to find the next sibling tree block.
 659  * More generic version of btrfs_next_leaf(), as it could find sibling nodes
 660  * if @path->lowest_level is not 0.
 661  *
 662  * returns 0 if it found something or 1 if there are no greater leaves.
 663  * returns < 0 on io errors.
 664  */
 665 int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info,
 666                                   struct btrfs_path *path)
 667 {
 668         int slot;
 669         int level = path->lowest_level + 1;
 670         struct extent_buffer *c;
 671         struct extent_buffer *next = NULL;
 672
 673         BUG_ON(path->lowest_level + 1 >= BTRFS_MAX_LEVEL);
 674         do {
 675                 if (!path->nodes[level])
 676                         return 1;
 677
 678                 slot = path->slots[level] + 1;
 679                 c = path->nodes[level];
 680                 if (slot >= btrfs_header_nritems(c)) {
 681                         level++;
 682                         if (level == BTRFS_MAX_LEVEL)
 683                                 return 1;
 684                         continue;
 685                 }
 686
 687                 next = read_node_slot(fs_info, c, slot);
 688                 if (!extent_buffer_uptodate(next))
 689                         return -EIO;
 690                 break;
 691         } while (level < BTRFS_MAX_LEVEL);
 692         path->slots[level] = slot;
 693         while(1) {
 694                 level--;
 695                 c = path->nodes[level];
 696                 free_extent_buffer(c);
 697                 path->nodes[level] = next;
 698                 path->slots[level] = 0;
 699                 if (level == path->lowest_level)
 700                         break;
 701                 next = read_node_slot(fs_info, next, 0);
 702                 if (!extent_buffer_uptodate(next))
 703                         return -EIO;
 704         }
 705         return 0;
 706 }
 707
 708 int btrfs_previous_item(struct btrfs_root *root,
 709                         struct btrfs_path *path, u64 min_objectid,
 710                         int type)
 711 {
 712         struct btrfs_key found_key;
 713         struct extent_buffer *leaf;
 714         u32 nritems;
 715         int ret;
 716
 717         while(1) {
 718                 if (path->slots[0] == 0) {
 719                         ret = btrfs_prev_leaf(root, path);
 720                         if (ret != 0)
 721                                 return ret;
 722                 } else {
 723                         path->slots[0]--;
 724                 }
 725                 leaf = path->nodes[0];
 726                 nritems = btrfs_header_nritems(leaf);
 727                 if (nritems == 0)
 728                         return 1;
 729                 if (path->slots[0] == nritems)
 730                         path->slots[0]--;
 731
 732                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 733                 if (found_key.objectid < min_objectid)
 734                         break;
 735                 if (found_key.type == type)
 736                         return 0;
 737                 if (found_key.objectid == min_objectid &&
 738                     found_key.type < type)
 739                         break;
 740         }
 741         return 1;
 742 }