fs/btrfs/ctree.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * BTRFS filesystem implementation for U-Boot
   4  *
   5  * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
   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_keys(struct btrfs_key *a, struct btrfs_key *b)
  74 {
  75         if (a->objectid > b->objectid)
  76                 return 1;
  77         if (a->objectid < b->objectid)
  78                 return -1;
  79         if (a->type > b->type)
  80                 return 1;
  81         if (a->type < b->type)
  82                 return -1;
  83         if (a->offset > b->offset)
  84                 return 1;
  85         if (a->offset < b->offset)
  86                 return -1;
  87         return 0;
  88 }
  89
  90 int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b)
  91 {
  92         if (a->objectid > b->objectid)
  93                 return 1;
  94         if (a->objectid < b->objectid)
  95                 return -1;
  96         if (a->type > b->type)
  97                 return 1;
  98         if (a->type < b->type)
  99                 return -1;
 100         return 0;
 101 }
 102
 103 /*
 104  * search for key in the extent_buffer.  The items start at offset p,
 105  * and they are item_size apart.  There are 'max' items in p.
 106  *
 107  * the slot in the array is returned via slot, and it points to
 108  * the place where you would insert key if it is not found in
 109  * the array.
 110  *
 111  * slot may point to max if the key is bigger than all of the keys
 112  */
 113 static int __generic_bin_search(void *addr, int item_size, struct btrfs_key *key,
 114                               int max, int *slot)
 115 {
 116         int low = 0, high = max, mid, ret;
 117         struct btrfs_key *tmp;
 118
 119         while (low < high) {
 120                 mid = (low + high) / 2;
 121
 122                 tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size);
 123                 ret = __btrfs_comp_keys(tmp, key);
 124
 125                 if (ret < 0) {
 126                         low = mid + 1;
 127                 } else if (ret > 0) {
 128                         high = mid;
 129                 } else {
 130                         *slot = mid;
 131                         return 0;
 132                 }
 133         }
 134
 135         *slot = low;
 136         return 1;
 137 }
 138
 139 int __btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key,
 140                        int *slot)
 141 {
 142         void *addr;
 143         unsigned long size;
 144
 145         if (p->header.level) {
 146                 addr = p->node.ptrs;
 147                 size = sizeof(struct btrfs_key_ptr);
 148         } else {
 149                 addr = p->leaf.items;
 150                 size = sizeof(struct btrfs_item);
 151         }
 152
 153         return __generic_bin_search(addr, size, key, p->header.nritems, slot);
 154 }
 155
 156 static void clear_path(struct __btrfs_path *p)
 157 {
 158         int i;
 159
 160         for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
 161                 p->nodes[i] = NULL;
 162                 p->slots[i] = 0;
 163         }
 164 }
 165
 166 void __btrfs_free_path(struct __btrfs_path *p)
 167 {
 168         int i;
 169
 170         for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
 171                 if (p->nodes[i])
 172                         free(p->nodes[i]);
 173         }
 174
 175         clear_path(p);
 176 }
 177
 178 static int read_tree_node(u64 physical, union btrfs_tree_node **buf)
 179 {
 180         ALLOC_CACHE_ALIGN_BUFFER(struct btrfs_header, hdr,
 181                                  sizeof(struct btrfs_header));
 182         unsigned long size, offset = sizeof(*hdr);
 183         union btrfs_tree_node *res;
 184         u32 i;
 185
 186         if (!btrfs_devread(physical, sizeof(*hdr), hdr))
 187                 return -1;
 188
 189         btrfs_header_to_cpu(hdr);
 190
 191         if (hdr->level)
 192                 size = sizeof(struct btrfs_node)
 193                        + hdr->nritems * sizeof(struct btrfs_key_ptr);
 194         else
 195                 size = btrfs_info.sb.nodesize;
 196
 197         res = malloc_cache_aligned(size);
 198         if (!res) {
 199                 debug("%s: malloc failed\n", __func__);
 200                 return -1;
 201         }
 202
 203         if (!btrfs_devread(physical + offset, size - offset,
 204                            ((u8 *) res) + offset)) {
 205                 free(res);
 206                 return -1;
 207         }
 208
 209         memcpy(&res->header, hdr, sizeof(*hdr));
 210         if (hdr->level)
 211                 for (i = 0; i < hdr->nritems; ++i)
 212                         btrfs_key_ptr_to_cpu(&res->node.ptrs[i]);
 213         else
 214                 for (i = 0; i < hdr->nritems; ++i)
 215                         btrfs_item_to_cpu(&res->leaf.items[i]);
 216
 217         *buf = res;
 218
 219         return 0;
 220 }
 221
 222 int btrfs_search_tree(const struct __btrfs_root *root, struct btrfs_key *key,
 223                       struct __btrfs_path *p)
 224 {
 225         u8 lvl, prev_lvl;
 226         int i, slot, ret;
 227         u64 logical, physical;
 228         union btrfs_tree_node *buf;
 229
 230         clear_path(p);
 231
 232         logical = root->bytenr;
 233
 234         for (i = 0; i < BTRFS_MAX_LEVEL; ++i) {
 235                 physical = btrfs_map_logical_to_physical(logical);
 236                 if (physical == -1ULL)
 237                         goto err;
 238
 239                 if (read_tree_node(physical, &buf))
 240                         goto err;
 241
 242                 lvl = buf->header.level;
 243                 if (i && prev_lvl != lvl + 1) {
 244                         printf("%s: invalid level in header at %llu\n",
 245                                __func__, logical);
 246                         goto err;
 247                 }
 248                 prev_lvl = lvl;
 249
 250                 ret = __btrfs_bin_search(buf, key, &slot);
 251                 if (ret < 0)
 252                         goto err;
 253                 if (ret && slot > 0 && lvl)
 254                         slot -= 1;
 255
 256                 p->slots[lvl] = slot;
 257                 p->nodes[lvl] = buf;
 258
 259                 if (lvl) {
 260                         logical = buf->node.ptrs[slot].blockptr;
 261                 } else {
 262                         /*
 263                          * The path might be invalid if:
 264                          *   cur leaf max < searched value < next leaf min
 265                          *
 266                          * Jump to the next valid element if it exists.
 267                          */
 268                         if (slot >= buf->header.nritems)
 269                                 if (btrfs_next_slot(p) < 0)
 270                                         goto err;
 271                         break;
 272                 }
 273         }
 274
 275         return 0;
 276 err:
 277         __btrfs_free_path(p);
 278         return -1;
 279 }
 280
 281 static int jump_leaf(struct __btrfs_path *path, int dir)
 282 {
 283         struct __btrfs_path p;
 284         u32 slot;
 285         int level = 1, from_level, i;
 286
 287         dir = dir >= 0 ? 1 : -1;
 288
 289         p = *path;
 290
 291         while (level < BTRFS_MAX_LEVEL) {
 292                 if (!p.nodes[level])
 293                         return 1;
 294
 295                 slot = p.slots[level];
 296                 if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems)
 297                     || (dir < 0 && !slot))
 298                         level++;
 299                 else
 300                         break;
 301         }
 302
 303         if (level == BTRFS_MAX_LEVEL)
 304                 return 1;
 305
 306         p.slots[level] = slot + dir;
 307         level--;
 308         from_level = level;
 309
 310         while (level >= 0) {
 311                 u64 logical, physical;
 312
 313                 slot = p.slots[level + 1];
 314                 logical = p.nodes[level + 1]->node.ptrs[slot].blockptr;
 315                 physical = btrfs_map_logical_to_physical(logical);
 316                 if (physical == -1ULL)
 317                         goto err;
 318
 319                 if (read_tree_node(physical, &p.nodes[level]))
 320                         goto err;
 321
 322                 if (dir > 0)
 323                         p.slots[level] = 0;
 324                 else
 325                         p.slots[level] = p.nodes[level]->header.nritems - 1;
 326                 level--;
 327         }
 328
 329         /* Free rewritten nodes in path */
 330         for (i = 0; i <= from_level; ++i)
 331                 free(path->nodes[i]);
 332
 333         *path = p;
 334         return 0;
 335
 336 err:
 337         /* Free rewritten nodes in p */
 338         for (i = level + 1; i <= from_level; ++i)
 339                 free(p.nodes[i]);
 340         return -1;
 341 }
 342
 343 int btrfs_prev_slot(struct __btrfs_path *p)
 344 {
 345         if (!p->slots[0])
 346                 return jump_leaf(p, -1);
 347
 348         p->slots[0]--;
 349         return 0;
 350 }
 351
 352 int btrfs_next_slot(struct __btrfs_path *p)
 353 {
 354         struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
 355
 356         if (p->slots[0] + 1 >= leaf->header.nritems)
 357                 return jump_leaf(p, 1);
 358
 359         p->slots[0]++;
 360         return 0;
 361 }
 362
 363 int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
 364 {
 365         if (k1->objectid > k2->objectid)
 366                 return 1;
 367         if (k1->objectid < k2->objectid)
 368                 return -1;
 369         if (k1->type > k2->type)
 370                 return 1;
 371         if (k1->type < k2->type)
 372                 return -1;
 373         if (k1->offset > k2->offset)
 374                 return 1;
 375         if (k1->offset < k2->offset)
 376                 return -1;
 377         return 0;
 378 }
 379
 380 static int btrfs_comp_keys(struct btrfs_disk_key *disk,
 381                              const struct btrfs_key *k2)
 382 {
 383         struct btrfs_key k1;
 384
 385         btrfs_disk_key_to_cpu(&k1, disk);
 386         return btrfs_comp_cpu_keys(&k1, k2);
 387 }
 388
 389 enum btrfs_tree_block_status
 390 btrfs_check_node(struct btrfs_fs_info *fs_info,
 391                  struct btrfs_disk_key *parent_key, struct extent_buffer *buf)
 392 {
 393         int i;
 394         struct btrfs_key cpukey;
 395         struct btrfs_disk_key key;
 396         u32 nritems = btrfs_header_nritems(buf);
 397         enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS;
 398
 399         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(fs_info))
 400                 goto fail;
 401
 402         ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY;
 403         if (parent_key && parent_key->type) {
 404                 btrfs_node_key(buf, &key, 0);
 405                 if (memcmp(parent_key, &key, sizeof(key)))
 406                         goto fail;
 407         }
 408         ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
 409         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 410                 btrfs_node_key(buf, &key, i);
 411                 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
 412                 if (btrfs_comp_keys(&key, &cpukey) >= 0)
 413                         goto fail;
 414         }
 415         return BTRFS_TREE_BLOCK_CLEAN;
 416 fail:
 417         return ret;
 418 }
 419
 420 enum btrfs_tree_block_status
 421 btrfs_check_leaf(struct btrfs_fs_info *fs_info,
 422                  struct btrfs_disk_key *parent_key, struct extent_buffer *buf)
 423 {
 424         int i;
 425         struct btrfs_key cpukey;
 426         struct btrfs_disk_key key;
 427         u32 nritems = btrfs_header_nritems(buf);
 428         enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS;
 429
 430         if (nritems * sizeof(struct btrfs_item) > buf->len)  {
 431                 fprintf(stderr, "invalid number of items %llu\n",
 432                         (unsigned long long)buf->start);
 433                 goto fail;
 434         }
 435
 436         if (btrfs_header_level(buf) != 0) {
 437                 ret = BTRFS_TREE_BLOCK_INVALID_LEVEL;
 438                 fprintf(stderr, "leaf is not a leaf %llu\n",
 439                        (unsigned long long)btrfs_header_bytenr(buf));
 440                 goto fail;
 441         }
 442         if (btrfs_leaf_free_space(buf) < 0) {
 443                 ret = BTRFS_TREE_BLOCK_INVALID_FREE_SPACE;
 444                 fprintf(stderr, "leaf free space incorrect %llu %d\n",
 445                         (unsigned long long)btrfs_header_bytenr(buf),
 446                         btrfs_leaf_free_space(buf));
 447                 goto fail;
 448         }
 449
 450         if (nritems == 0)
 451                 return BTRFS_TREE_BLOCK_CLEAN;
 452
 453         btrfs_item_key(buf, &key, 0);
 454         if (parent_key && parent_key->type &&
 455             memcmp(parent_key, &key, sizeof(key))) {
 456                 ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY;
 457                 fprintf(stderr, "leaf parent key incorrect %llu\n",
 458                        (unsigned long long)btrfs_header_bytenr(buf));
 459                 goto fail;
 460         }
 461         for (i = 0; nritems > 1 && i < nritems - 1; i++) {
 462                 btrfs_item_key(buf, &key, i);
 463                 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
 464                 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
 465                         ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
 466                         fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
 467                         goto fail;
 468                 }
 469                 if (btrfs_item_offset_nr(buf, i) !=
 470                         btrfs_item_end_nr(buf, i + 1)) {
 471                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 472                         fprintf(stderr, "incorrect offsets %u %u\n",
 473                                 btrfs_item_offset_nr(buf, i),
 474                                 btrfs_item_end_nr(buf, i + 1));
 475                         goto fail;
 476                 }
 477                 if (i == 0 && btrfs_item_end_nr(buf, i) !=
 478                     BTRFS_LEAF_DATA_SIZE(fs_info)) {
 479                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 480                         fprintf(stderr, "bad item end %u wanted %u\n",
 481                                 btrfs_item_end_nr(buf, i),
 482                                 (unsigned)BTRFS_LEAF_DATA_SIZE(fs_info));
 483                         goto fail;
 484                 }
 485         }
 486
 487         for (i = 0; i < nritems; i++) {
 488                 if (btrfs_item_end_nr(buf, i) >
 489                                 BTRFS_LEAF_DATA_SIZE(fs_info)) {
 490                         btrfs_item_key(buf, &key, 0);
 491                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 492                         fprintf(stderr, "slot end outside of leaf %llu > %llu\n",
 493                                 (unsigned long long)btrfs_item_end_nr(buf, i),
 494                                 (unsigned long long)BTRFS_LEAF_DATA_SIZE(
 495                                         fs_info));
 496                         goto fail;
 497                 }
 498         }
 499
 500         return BTRFS_TREE_BLOCK_CLEAN;
 501 fail:
 502         return ret;
 503 }
 504
 505 static int noinline check_block(struct btrfs_fs_info *fs_info,
 506                                 struct btrfs_path *path, int level)
 507 {
 508         struct btrfs_disk_key key;
 509         struct btrfs_disk_key *key_ptr = NULL;
 510         struct extent_buffer *parent;
 511         enum btrfs_tree_block_status ret;
 512
 513         if (path->nodes[level + 1]) {
 514                 parent = path->nodes[level + 1];
 515                 btrfs_node_key(parent, &key, path->slots[level + 1]);
 516                 key_ptr = &key;
 517         }
 518         if (level == 0)
 519                 ret = btrfs_check_leaf(fs_info, key_ptr, path->nodes[0]);
 520         else
 521                 ret = btrfs_check_node(fs_info, key_ptr, path->nodes[level]);
 522         if (ret == BTRFS_TREE_BLOCK_CLEAN)
 523                 return 0;
 524         return -EIO;
 525 }
 526
 527 /*
 528  * search for key in the extent_buffer.  The items start at offset p,
 529  * and they are item_size apart.  There are 'max' items in p.
 530  *
 531  * the slot in the array is returned via slot, and it points to
 532  * the place where you would insert key if it is not found in
 533  * the array.
 534  *
 535  * slot may point to max if the key is bigger than all of the keys
 536  */
 537 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
 538                               int item_size, const struct btrfs_key *key,
 539                               int max, int *slot)
 540 {
 541         int low = 0;
 542         int high = max;
 543         int mid;
 544         int ret;
 545         unsigned long offset;
 546         struct btrfs_disk_key *tmp;
 547
 548         while(low < high) {
 549                 mid = (low + high) / 2;
 550                 offset = p + mid * item_size;
 551
 552                 tmp = (struct btrfs_disk_key *)(eb->data + offset);
 553                 ret = btrfs_comp_keys(tmp, key);
 554
 555                 if (ret < 0)
 556                         low = mid + 1;
 557                 else if (ret > 0)
 558                         high = mid;
 559                 else {
 560                         *slot = mid;
 561                         return 0;
 562                 }
 563         }
 564         *slot = low;
 565         return 1;
 566 }
 567
 568 /*
 569  * simple bin_search frontend that does the right thing for
 570  * leaves vs nodes
 571  */
 572 int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key,
 573                      int *slot)
 574 {
 575         if (btrfs_header_level(eb) == 0)
 576                 return generic_bin_search(eb,
 577                                           offsetof(struct btrfs_leaf, items),
 578                                           sizeof(struct btrfs_item),
 579                                           key, btrfs_header_nritems(eb),
 580                                           slot);
 581         else
 582                 return generic_bin_search(eb,
 583                                           offsetof(struct btrfs_node, ptrs),
 584                                           sizeof(struct btrfs_key_ptr),
 585                                           key, btrfs_header_nritems(eb),
 586                                           slot);
 587 }
 588
 589 struct extent_buffer *read_node_slot(struct btrfs_fs_info *fs_info,
 590                                    struct extent_buffer *parent, int slot)
 591 {
 592         struct extent_buffer *ret;
 593         int level = btrfs_header_level(parent);
 594
 595         if (slot < 0)
 596                 return NULL;
 597         if (slot >= btrfs_header_nritems(parent))
 598                 return NULL;
 599
 600         if (level == 0)
 601                 return NULL;
 602
 603         ret = read_tree_block(fs_info, btrfs_node_blockptr(parent, slot),
 604                        btrfs_node_ptr_generation(parent, slot));
 605         if (!extent_buffer_uptodate(ret))
 606                 return ERR_PTR(-EIO);
 607
 608         if (btrfs_header_level(ret) != level - 1) {
 609                 error("child eb corrupted: parent bytenr=%llu item=%d parent level=%d child level=%d",
 610                       btrfs_header_bytenr(parent), slot,
 611                       btrfs_header_level(parent), btrfs_header_level(ret));
 612                 free_extent_buffer(ret);
 613                 return ERR_PTR(-EIO);
 614         }
 615         return ret;
 616 }
 617
 618 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path,
 619                 u64 iobjectid, u64 ioff, u8 key_type,
 620                 struct btrfs_key *found_key)
 621 {
 622         int ret;
 623         struct btrfs_key key;
 624         struct extent_buffer *eb;
 625         struct btrfs_path *path;
 626
 627         key.type = key_type;
 628         key.objectid = iobjectid;
 629         key.offset = ioff;
 630
 631         if (found_path == NULL) {
 632                 path = btrfs_alloc_path();
 633                 if (!path)
 634                         return -ENOMEM;
 635         } else
 636                 path = found_path;
 637
 638         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
 639         if ((ret < 0) || (found_key == NULL))
 640                 goto out;
 641
 642         eb = path->nodes[0];
 643         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
 644                 ret = btrfs_next_leaf(fs_root, path);
 645                 if (ret)
 646                         goto out;
 647                 eb = path->nodes[0];
 648         }
 649
 650         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
 651         if (found_key->type != key.type ||
 652                         found_key->objectid != key.objectid) {
 653                 ret = 1;
 654                 goto out;
 655         }
 656
 657 out:
 658         if (path != found_path)
 659                 btrfs_free_path(path);
 660         return ret;
 661 }
 662
 663 /*
 664  * look for key in the tree.  path is filled in with nodes along the way
 665  * if key is found, we return zero and you can find the item in the leaf
 666  * level of the path (level 0)
 667  *
 668  * If the key isn't found, the path points to the slot where it should
 669  * be inserted, and 1 is returned.  If there are other errors during the
 670  * search a negative error number is returned.
 671  *
 672  * if ins_len > 0, nodes and leaves will be split as we walk down the
 673  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
 674  * possible)
 675  *
 676  * NOTE: This version has no COW ability, thus we expect trans == NULL,
 677  * ins_len == 0 and cow == 0.
 678  */
 679 int btrfs_search_slot(struct btrfs_trans_handle *trans,
 680                 struct btrfs_root *root, const struct btrfs_key *key,
 681                 struct btrfs_path *p, int ins_len, int cow)
 682 {
 683         struct extent_buffer *b;
 684         int slot;
 685         int ret;
 686         int level;
 687         struct btrfs_fs_info *fs_info = root->fs_info;
 688         u8 lowest_level = 0;
 689
 690         assert(trans == NULL && ins_len == 0 && cow == 0);
 691         lowest_level = p->lowest_level;
 692         WARN_ON(lowest_level && ins_len > 0);
 693         WARN_ON(p->nodes[0] != NULL);
 694
 695         b = root->node;
 696         extent_buffer_get(b);
 697         while (b) {
 698                 level = btrfs_header_level(b);
 699                 /*
 700                 if (cow) {
 701                         int wret;
 702                         wret = btrfs_cow_block(trans, root, b,
 703                                                p->nodes[level + 1],
 704                                                p->slots[level + 1],
 705                                                &b);
 706                         if (wret) {
 707                                 free_extent_buffer(b);
 708                                 return wret;
 709                         }
 710                 }
 711                 */
 712                 BUG_ON(!cow && ins_len);
 713                 if (level != btrfs_header_level(b))
 714                         WARN_ON(1);
 715                 level = btrfs_header_level(b);
 716                 p->nodes[level] = b;
 717                 ret = check_block(fs_info, p, level);
 718                 if (ret)
 719                         return -1;
 720                 ret = btrfs_bin_search(b, key, &slot);
 721                 if (level != 0) {
 722                         if (ret && slot > 0)
 723                                 slot -= 1;
 724                         p->slots[level] = slot;
 725                         /*
 726                         if ((p->search_for_split || ins_len > 0) &&
 727                             btrfs_header_nritems(b) >=
 728                             BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) {
 729                                 int sret = split_node(trans, root, p, level);
 730                                 BUG_ON(sret > 0);
 731                                 if (sret)
 732                                         return sret;
 733                                 b = p->nodes[level];
 734                                 slot = p->slots[level];
 735                         } else if (ins_len < 0) {
 736                                 int sret = balance_level(trans, root, p,
 737                                                          level);
 738                                 if (sret)
 739                                         return sret;
 740                                 b = p->nodes[level];
 741                                 if (!b) {
 742                                         btrfs_release_path(p);
 743                                         goto again;
 744                                 }
 745                                 slot = p->slots[level];
 746                                 BUG_ON(btrfs_header_nritems(b) == 1);
 747                         }
 748                         */
 749                         /* this is only true while dropping a snapshot */
 750                         if (level == lowest_level)
 751                                 break;
 752
 753                         b = read_node_slot(fs_info, b, slot);
 754                         if (!extent_buffer_uptodate(b))
 755                                 return -EIO;
 756                 } else {
 757                         p->slots[level] = slot;
 758                         /*
 759                         if (ins_len > 0 &&
 760                             ins_len > btrfs_leaf_free_space(b)) {
 761                                 int sret = split_leaf(trans, root, key,
 762                                                       p, ins_len, ret == 0);
 763                                 BUG_ON(sret > 0);
 764                                 if (sret)
 765                                         return sret;
 766                         }
 767                         */
 768                         return ret;
 769                 }
 770         }
 771         return 1;
 772 }
 773
 774 /*
 775  * Helper to use instead of search slot if no exact match is needed but
 776  * instead the next or previous item should be returned.
 777  * When find_higher is true, the next higher item is returned, the next lower
 778  * otherwise.
 779  * When return_any and find_higher are both true, and no higher item is found,
 780  * return the next lower instead.
 781  * When return_any is true and find_higher is false, and no lower item is found,
 782  * return the next higher instead.
 783  * It returns 0 if any item is found, 1 if none is found (tree empty), and
 784  * < 0 on error
 785  */
 786 int btrfs_search_slot_for_read(struct btrfs_root *root,
 787                                const struct btrfs_key *key,
 788                                struct btrfs_path *p, int find_higher,
 789                                int return_any)
 790 {
 791         int ret;
 792         struct extent_buffer *leaf;
 793
 794 again:
 795         ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
 796         if (ret <= 0)
 797                  return ret;
 798         /*
 799          * A return value of 1 means the path is at the position where the item
 800          * should be inserted. Normally this is the next bigger item, but in
 801          * case the previous item is the last in a leaf, path points to the
 802          * first free slot in the previous leaf, i.e. at an invalid item.
 803          */
 804         leaf = p->nodes[0];
 805
 806         if (find_higher) {
 807                 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
 808                         ret = btrfs_next_leaf(root, p);
 809                         if (ret <= 0)
 810                                 return ret;
 811                         if (!return_any)
 812                                 return 1;
 813                         /*
 814                          * No higher item found, return the next lower instead
 815                          */
 816                         return_any = 0;
 817                         find_higher = 0;
 818                         btrfs_release_path(p);
 819                         goto again;
 820                 }
 821         } else {
 822                 if (p->slots[0] == 0) {
 823                         ret = btrfs_prev_leaf(root, p);
 824                         if (ret < 0)
 825                                 return ret;
 826                         if (!ret) {
 827                                 leaf = p->nodes[0];
 828                                 if (p->slots[0] == btrfs_header_nritems(leaf))
 829                                         p->slots[0]--;
 830                                 return 0;
 831                         }
 832                         if (!return_any)
 833                                 return 1;
 834                         /*
 835                          * No lower item found, return the next higher instead
 836                          */
 837                         return_any = 0;
 838                         find_higher = 1;
 839                         btrfs_release_path(p);
 840                         goto again;
 841                 } else {
 842                         --p->slots[0];
 843                 }
 844         }
 845         return 0;
 846 }
 847
 848 /*
 849  * how many bytes are required to store the items in a leaf.  start
 850  * and nr indicate which items in the leaf to check.  This totals up the
 851  * space used both by the item structs and the item data
 852  */
 853 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
 854 {
 855         int data_len;
 856         int nritems = btrfs_header_nritems(l);
 857         int end = min(nritems, start + nr) - 1;
 858
 859         if (!nr)
 860                 return 0;
 861         data_len = btrfs_item_end_nr(l, start);
 862         data_len = data_len - btrfs_item_offset_nr(l, end);
 863         data_len += sizeof(struct btrfs_item) * nr;
 864         WARN_ON(data_len < 0);
 865         return data_len;
 866 }
 867
 868 /*
 869  * The space between the end of the leaf items and
 870  * the start of the leaf data.  IOW, how much room
 871  * the leaf has left for both items and data
 872  */
 873 int btrfs_leaf_free_space(struct extent_buffer *leaf)
 874 {
 875         int nritems = btrfs_header_nritems(leaf);
 876         u32 leaf_data_size;
 877         int ret;
 878
 879         BUG_ON(leaf->fs_info && leaf->fs_info->nodesize != leaf->len);
 880         leaf_data_size = __BTRFS_LEAF_DATA_SIZE(leaf->len);
 881         ret = leaf_data_size - leaf_space_used(leaf, 0 ,nritems);
 882         if (ret < 0) {
 883                 printk("leaf free space ret %d, leaf data size %u, used %d nritems %d\n",
 884                        ret, leaf_data_size, leaf_space_used(leaf, 0, nritems),
 885                        nritems);
 886         }
 887         return ret;
 888 }
 889
 890 /*
 891  * walk up the tree as far as required to find the previous leaf.
 892  * returns 0 if it found something or 1 if there are no lesser leaves.
 893  * returns < 0 on io errors.
 894  */
 895 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
 896 {
 897         int slot;
 898         int level = 1;
 899         struct extent_buffer *c;
 900         struct extent_buffer *next = NULL;
 901         struct btrfs_fs_info *fs_info = root->fs_info;
 902
 903         while(level < BTRFS_MAX_LEVEL) {
 904                 if (!path->nodes[level])
 905                         return 1;
 906
 907                 slot = path->slots[level];
 908                 c = path->nodes[level];
 909                 if (slot == 0) {
 910                         level++;
 911                         if (level == BTRFS_MAX_LEVEL)
 912                                 return 1;
 913                         continue;
 914                 }
 915                 slot--;
 916
 917                 next = read_node_slot(fs_info, c, slot);
 918                 if (!extent_buffer_uptodate(next)) {
 919                         if (IS_ERR(next))
 920                                 return PTR_ERR(next);
 921                         return -EIO;
 922                 }
 923                 break;
 924         }
 925         path->slots[level] = slot;
 926         while(1) {
 927                 level--;
 928                 c = path->nodes[level];
 929                 free_extent_buffer(c);
 930                 slot = btrfs_header_nritems(next);
 931                 if (slot != 0)
 932                         slot--;
 933                 path->nodes[level] = next;
 934                 path->slots[level] = slot;
 935                 if (!level)
 936                         break;
 937                 next = read_node_slot(fs_info, next, slot);
 938                 if (!extent_buffer_uptodate(next)) {
 939                         if (IS_ERR(next))
 940                                 return PTR_ERR(next);
 941                         return -EIO;
 942                 }
 943         }
 944         return 0;
 945 }
 946
 947 /*
 948  * Walk up the tree as far as necessary to find the next sibling tree block.
 949  * More generic version of btrfs_next_leaf(), as it could find sibling nodes
 950  * if @path->lowest_level is not 0.
 951  *
 952  * returns 0 if it found something or 1 if there are no greater leaves.
 953  * returns < 0 on io errors.
 954  */
 955 int btrfs_next_sibling_tree_block(struct btrfs_fs_info *fs_info,
 956                                   struct btrfs_path *path)
 957 {
 958         int slot;
 959         int level = path->lowest_level + 1;
 960         struct extent_buffer *c;
 961         struct extent_buffer *next = NULL;
 962
 963         BUG_ON(path->lowest_level + 1 >= BTRFS_MAX_LEVEL);
 964         do {
 965                 if (!path->nodes[level])
 966                         return 1;
 967
 968                 slot = path->slots[level] + 1;
 969                 c = path->nodes[level];
 970                 if (slot >= btrfs_header_nritems(c)) {
 971                         level++;
 972                         if (level == BTRFS_MAX_LEVEL)
 973                                 return 1;
 974                         continue;
 975                 }
 976
 977                 next = read_node_slot(fs_info, c, slot);
 978                 if (!extent_buffer_uptodate(next))
 979                         return -EIO;
 980                 break;
 981         } while (level < BTRFS_MAX_LEVEL);
 982         path->slots[level] = slot;
 983         while(1) {
 984                 level--;
 985                 c = path->nodes[level];
 986                 free_extent_buffer(c);
 987                 path->nodes[level] = next;
 988                 path->slots[level] = 0;
 989                 if (level == path->lowest_level)
 990                         break;
 991                 next = read_node_slot(fs_info, next, 0);
 992                 if (!extent_buffer_uptodate(next))
 993                         return -EIO;
 994         }
 995         return 0;
 996 }
 997
 998 int btrfs_previous_item(struct btrfs_root *root,
 999                         struct btrfs_path *path, u64 min_objectid,
1000                         int type)
1001 {
1002         struct btrfs_key found_key;
1003         struct extent_buffer *leaf;
1004         u32 nritems;
1005         int ret;
1006
1007         while(1) {
1008                 if (path->slots[0] == 0) {
1009                         ret = btrfs_prev_leaf(root, path);
1010                         if (ret != 0)
1011                                 return ret;
1012                 } else {
1013                         path->slots[0]--;
1014                 }
1015                 leaf = path->nodes[0];
1016                 nritems = btrfs_header_nritems(leaf);
1017                 if (nritems == 0)
1018                         return 1;
1019                 if (path->slots[0] == nritems)
1020                         path->slots[0]--;
1021
1022                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1023                 if (found_key.objectid < min_objectid)
1024                         break;
1025                 if (found_key.type == type)
1026                         return 0;
1027                 if (found_key.objectid == min_objectid &&
1028                     found_key.type < type)
1029                         break;
1030         }
1031         return 1;
1032 }