fs/btrfs/ctree.c

   1 /*
   2  * Copyright (C) 2007,2008 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <linux/sched.h>
  20 #include "ctree.h"
  21 #include "disk-io.h"
  22 #include "transaction.h"
  23 #include "print-tree.h"
  24 #include "locking.h"
  25
  26 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  27                       *root, struct btrfs_path *path, int level);
  28 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
  29                       *root, struct btrfs_key *ins_key,
  30                       struct btrfs_path *path, int data_size, int extend);
  31 static int push_node_left(struct btrfs_trans_handle *trans,
  32                           struct btrfs_root *root, struct extent_buffer *dst,
  33                           struct extent_buffer *src, int empty);
  34 static int balance_node_right(struct btrfs_trans_handle *trans,
  35                               struct btrfs_root *root,
  36                               struct extent_buffer *dst_buf,
  37                               struct extent_buffer *src_buf);
  38 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  39                    struct btrfs_path *path, int level, int slot);
  40
  41 struct btrfs_path *btrfs_alloc_path(void)
  42 {
  43         struct btrfs_path *path;
  44         path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
  45         if (path)
  46                 path->reada = 1;
  47         return path;
  48 }
  49
  50 /*
  51  * set all locked nodes in the path to blocking locks.  This should
  52  * be done before scheduling
  53  */
  54 noinline void btrfs_set_path_blocking(struct btrfs_path *p)
  55 {
  56         int i;
  57         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  58                 if (p->nodes[i] && p->locks[i])
  59                         btrfs_set_lock_blocking(p->nodes[i]);
  60         }
  61 }
  62
  63 /*
  64  * reset all the locked nodes in the patch to spinning locks.
  65  *
  66  * held is used to keep lockdep happy, when lockdep is enabled
  67  * we set held to a blocking lock before we go around and
  68  * retake all the spinlocks in the path.  You can safely use NULL
  69  * for held
  70  */
  71 noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
  72                                         struct extent_buffer *held)
  73 {
  74         int i;
  75
  76 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  77         /* lockdep really cares that we take all of these spinlocks
  78          * in the right order.  If any of the locks in the path are not
  79          * currently blocking, it is going to complain.  So, make really
  80          * really sure by forcing the path to blocking before we clear
  81          * the path blocking.
  82          */
  83         if (held)
  84                 btrfs_set_lock_blocking(held);
  85         btrfs_set_path_blocking(p);
  86 #endif
  87
  88         for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
  89                 if (p->nodes[i] && p->locks[i])
  90                         btrfs_clear_lock_blocking(p->nodes[i]);
  91         }
  92
  93 #ifdef CONFIG_DEBUG_LOCK_ALLOC
  94         if (held)
  95                 btrfs_clear_lock_blocking(held);
  96 #endif
  97 }
  98
  99 /* this also releases the path */
 100 void btrfs_free_path(struct btrfs_path *p)
 101 {
 102         btrfs_release_path(NULL, p);
 103         kmem_cache_free(btrfs_path_cachep, p);
 104 }
 105
 106 /*
 107  * path release drops references on the extent buffers in the path
 108  * and it drops any locks held by this path
 109  *
 110  * It is safe to call this on paths that no locks or extent buffers held.
 111  */
 112 noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
 113 {
 114         int i;
 115
 116         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
 117                 p->slots[i] = 0;
 118                 if (!p->nodes[i])
 119                         continue;
 120                 if (p->locks[i]) {
 121                         btrfs_tree_unlock(p->nodes[i]);
 122                         p->locks[i] = 0;
 123                 }
 124                 free_extent_buffer(p->nodes[i]);
 125                 p->nodes[i] = NULL;
 126         }
 127 }
 128
 129 /*
 130  * safely gets a reference on the root node of a tree.  A lock
 131  * is not taken, so a concurrent writer may put a different node
 132  * at the root of the tree.  See btrfs_lock_root_node for the
 133  * looping required.
 134  *
 135  * The extent buffer returned by this has a reference taken, so
 136  * it won't disappear.  It may stop being the root of the tree
 137  * at any time because there are no locks held.
 138  */
 139 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
 140 {
 141         struct extent_buffer *eb;
 142         spin_lock(&root->node_lock);
 143         eb = root->node;
 144         extent_buffer_get(eb);
 145         spin_unlock(&root->node_lock);
 146         return eb;
 147 }
 148
 149 /* loop around taking references on and locking the root node of the
 150  * tree until you end up with a lock on the root.  A locked buffer
 151  * is returned, with a reference held.
 152  */
 153 struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
 154 {
 155         struct extent_buffer *eb;
 156
 157         while (1) {
 158                 eb = btrfs_root_node(root);
 159                 btrfs_tree_lock(eb);
 160
 161                 spin_lock(&root->node_lock);
 162                 if (eb == root->node) {
 163                         spin_unlock(&root->node_lock);
 164                         break;
 165                 }
 166                 spin_unlock(&root->node_lock);
 167
 168                 btrfs_tree_unlock(eb);
 169                 free_extent_buffer(eb);
 170         }
 171         return eb;
 172 }
 173
 174 /* cowonly root (everything not a reference counted cow subvolume), just get
 175  * put onto a simple dirty list.  transaction.c walks this to make sure they
 176  * get properly updated on disk.
 177  */
 178 static void add_root_to_dirty_list(struct btrfs_root *root)
 179 {
 180         if (root->track_dirty && list_empty(&root->dirty_list)) {
 181                 list_add(&root->dirty_list,
 182                          &root->fs_info->dirty_cowonly_roots);
 183         }
 184 }
 185
 186 /*
 187  * used by snapshot creation to make a copy of a root for a tree with
 188  * a given objectid.  The buffer with the new root node is returned in
 189  * cow_ret, and this func returns zero on success or a negative error code.
 190  */
 191 int btrfs_copy_root(struct btrfs_trans_handle *trans,
 192                       struct btrfs_root *root,
 193                       struct extent_buffer *buf,
 194                       struct extent_buffer **cow_ret, u64 new_root_objectid)
 195 {
 196         struct extent_buffer *cow;
 197         u32 nritems;
 198         int ret = 0;
 199         int level;
 200         struct btrfs_root *new_root;
 201
 202         new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
 203         if (!new_root)
 204                 return -ENOMEM;
 205
 206         memcpy(new_root, root, sizeof(*new_root));
 207         new_root->root_key.objectid = new_root_objectid;
 208
 209         WARN_ON(root->ref_cows && trans->transid !=
 210                 root->fs_info->running_transaction->transid);
 211         WARN_ON(root->ref_cows && trans->transid != root->last_trans);
 212
 213         level = btrfs_header_level(buf);
 214         nritems = btrfs_header_nritems(buf);
 215
 216         cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0,
 217                                      new_root_objectid, trans->transid,
 218                                      level, buf->start, 0);
 219         if (IS_ERR(cow)) {
 220                 kfree(new_root);
 221                 return PTR_ERR(cow);
 222         }
 223
 224         copy_extent_buffer(cow, buf, 0, 0, cow->len);
 225         btrfs_set_header_bytenr(cow, cow->start);
 226         btrfs_set_header_generation(cow, trans->transid);
 227         btrfs_set_header_owner(cow, new_root_objectid);
 228         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
 229
 230         write_extent_buffer(cow, root->fs_info->fsid,
 231                             (unsigned long)btrfs_header_fsid(cow),
 232                             BTRFS_FSID_SIZE);
 233
 234         WARN_ON(btrfs_header_generation(buf) > trans->transid);
 235         ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL);
 236         kfree(new_root);
 237
 238         if (ret)
 239                 return ret;
 240
 241         btrfs_mark_buffer_dirty(cow);
 242         *cow_ret = cow;
 243         return 0;
 244 }
 245
 246 /*
 247  * does the dirty work in cow of a single block.  The parent block (if
 248  * supplied) is updated to point to the new cow copy.  The new buffer is marked
 249  * dirty and returned locked.  If you modify the block it needs to be marked
 250  * dirty again.
 251  *
 252  * search_start -- an allocation hint for the new block
 253  *
 254  * empty_size -- a hint that you plan on doing more cow.  This is the size in
 255  * bytes the allocator should try to find free next to the block it returns.
 256  * This is just a hint and may be ignored by the allocator.
 257  *
 258  * prealloc_dest -- if you have already reserved a destination for the cow,
 259  * this uses that block instead of allocating a new one.
 260  * btrfs_alloc_reserved_extent is used to finish the allocation.
 261  */
 262 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
 263                              struct btrfs_root *root,
 264                              struct extent_buffer *buf,
 265                              struct extent_buffer *parent, int parent_slot,
 266                              struct extent_buffer **cow_ret,
 267                              u64 search_start, u64 empty_size,
 268                              u64 prealloc_dest)
 269 {
 270         u64 parent_start;
 271         struct extent_buffer *cow;
 272         u32 nritems;
 273         int ret = 0;
 274         int level;
 275         int unlock_orig = 0;
 276
 277         if (*cow_ret == buf)
 278                 unlock_orig = 1;
 279
 280         btrfs_assert_tree_locked(buf);
 281
 282         if (parent)
 283                 parent_start = parent->start;
 284         else
 285                 parent_start = 0;
 286
 287         WARN_ON(root->ref_cows && trans->transid !=
 288                 root->fs_info->running_transaction->transid);
 289         WARN_ON(root->ref_cows && trans->transid != root->last_trans);
 290
 291         level = btrfs_header_level(buf);
 292         nritems = btrfs_header_nritems(buf);
 293
 294         if (prealloc_dest) {
 295                 struct btrfs_key ins;
 296
 297                 ins.objectid = prealloc_dest;
 298                 ins.offset = buf->len;
 299                 ins.type = BTRFS_EXTENT_ITEM_KEY;
 300
 301                 ret = btrfs_alloc_reserved_extent(trans, root, parent_start,
 302                                                   root->root_key.objectid,
 303                                                   trans->transid, level, &ins);
 304                 BUG_ON(ret);
 305                 cow = btrfs_init_new_buffer(trans, root, prealloc_dest,
 306                                             buf->len, level);
 307         } else {
 308                 cow = btrfs_alloc_free_block(trans, root, buf->len,
 309                                              parent_start,
 310                                              root->root_key.objectid,
 311                                              trans->transid, level,
 312                                              search_start, empty_size);
 313         }
 314         if (IS_ERR(cow))
 315                 return PTR_ERR(cow);
 316
 317         /* cow is set to blocking by btrfs_init_new_buffer */
 318
 319         copy_extent_buffer(cow, buf, 0, 0, cow->len);
 320         btrfs_set_header_bytenr(cow, cow->start);
 321         btrfs_set_header_generation(cow, trans->transid);
 322         btrfs_set_header_owner(cow, root->root_key.objectid);
 323         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
 324
 325         write_extent_buffer(cow, root->fs_info->fsid,
 326                             (unsigned long)btrfs_header_fsid(cow),
 327                             BTRFS_FSID_SIZE);
 328
 329         WARN_ON(btrfs_header_generation(buf) > trans->transid);
 330         if (btrfs_header_generation(buf) != trans->transid) {
 331                 u32 nr_extents;
 332                 ret = btrfs_inc_ref(trans, root, buf, cow, &nr_extents);
 333                 if (ret)
 334                         return ret;
 335
 336                 ret = btrfs_cache_ref(trans, root, buf, nr_extents);
 337                 WARN_ON(ret);
 338         } else if (btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID) {
 339                 /*
 340                  * There are only two places that can drop reference to
 341                  * tree blocks owned by living reloc trees, one is here,
 342                  * the other place is btrfs_drop_subtree. In both places,
 343                  * we check reference count while tree block is locked.
 344                  * Furthermore, if reference count is one, it won't get
 345                  * increased by someone else.
 346                  */
 347                 u32 refs;
 348                 ret = btrfs_lookup_extent_ref(trans, root, buf->start,
 349                                               buf->len, &refs);
 350                 BUG_ON(ret);
 351                 if (refs == 1) {
 352                         ret = btrfs_update_ref(trans, root, buf, cow,
 353                                                0, nritems);
 354                         clean_tree_block(trans, root, buf);
 355                 } else {
 356                         ret = btrfs_inc_ref(trans, root, buf, cow, NULL);
 357                 }
 358                 BUG_ON(ret);
 359         } else {
 360                 ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems);
 361                 if (ret)
 362                         return ret;
 363                 clean_tree_block(trans, root, buf);
 364         }
 365
 366         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
 367                 ret = btrfs_reloc_tree_cache_ref(trans, root, cow, buf->start);
 368                 WARN_ON(ret);
 369         }
 370
 371         if (buf == root->node) {
 372                 WARN_ON(parent && parent != buf);
 373
 374                 spin_lock(&root->node_lock);
 375                 root->node = cow;
 376                 extent_buffer_get(cow);
 377                 spin_unlock(&root->node_lock);
 378
 379                 if (buf != root->commit_root) {
 380                         btrfs_free_extent(trans, root, buf->start,
 381                                           buf->len, buf->start,
 382                                           root->root_key.objectid,
 383                                           btrfs_header_generation(buf),
 384                                           level, 1);
 385                 }
 386                 free_extent_buffer(buf);
 387                 add_root_to_dirty_list(root);
 388         } else {
 389                 btrfs_set_node_blockptr(parent, parent_slot,
 390                                         cow->start);
 391                 WARN_ON(trans->transid == 0);
 392                 btrfs_set_node_ptr_generation(parent, parent_slot,
 393                                               trans->transid);
 394                 btrfs_mark_buffer_dirty(parent);
 395                 WARN_ON(btrfs_header_generation(parent) != trans->transid);
 396                 btrfs_free_extent(trans, root, buf->start, buf->len,
 397                                   parent_start, btrfs_header_owner(parent),
 398                                   btrfs_header_generation(parent), level, 1);
 399         }
 400         if (unlock_orig)
 401                 btrfs_tree_unlock(buf);
 402         free_extent_buffer(buf);
 403         btrfs_mark_buffer_dirty(cow);
 404         *cow_ret = cow;
 405         return 0;
 406 }
 407
 408 /*
 409  * cows a single block, see __btrfs_cow_block for the real work.
 410  * This version of it has extra checks so that a block isn't cow'd more than
 411  * once per transaction, as long as it hasn't been written yet
 412  */
 413 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
 414                     struct btrfs_root *root, struct extent_buffer *buf,
 415                     struct extent_buffer *parent, int parent_slot,
 416                     struct extent_buffer **cow_ret, u64 prealloc_dest)
 417 {
 418         u64 search_start;
 419         int ret;
 420
 421         if (trans->transaction != root->fs_info->running_transaction) {
 422                 printk(KERN_CRIT "trans %llu running %llu\n",
 423                        (unsigned long long)trans->transid,
 424                        (unsigned long long)
 425                        root->fs_info->running_transaction->transid);
 426                 WARN_ON(1);
 427         }
 428         if (trans->transid != root->fs_info->generation) {
 429                 printk(KERN_CRIT "trans %llu running %llu\n",
 430                        (unsigned long long)trans->transid,
 431                        (unsigned long long)root->fs_info->generation);
 432                 WARN_ON(1);
 433         }
 434
 435         if (btrfs_header_generation(buf) == trans->transid &&
 436             btrfs_header_owner(buf) == root->root_key.objectid &&
 437             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
 438                 *cow_ret = buf;
 439                 WARN_ON(prealloc_dest);
 440                 return 0;
 441         }
 442
 443         search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
 444
 445         if (parent)
 446                 btrfs_set_lock_blocking(parent);
 447         btrfs_set_lock_blocking(buf);
 448
 449         ret = __btrfs_cow_block(trans, root, buf, parent,
 450                                  parent_slot, cow_ret, search_start, 0,
 451                                  prealloc_dest);
 452         return ret;
 453 }
 454
 455 /*
 456  * helper function for defrag to decide if two blocks pointed to by a
 457  * node are actually close by
 458  */
 459 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
 460 {
 461         if (blocknr < other && other - (blocknr + blocksize) < 32768)
 462                 return 1;
 463         if (blocknr > other && blocknr - (other + blocksize) < 32768)
 464                 return 1;
 465         return 0;
 466 }
 467
 468 /*
 469  * compare two keys in a memcmp fashion
 470  */
 471 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
 472 {
 473         struct btrfs_key k1;
 474
 475         btrfs_disk_key_to_cpu(&k1, disk);
 476
 477         if (k1.objectid > k2->objectid)
 478                 return 1;
 479         if (k1.objectid < k2->objectid)
 480                 return -1;
 481         if (k1.type > k2->type)
 482                 return 1;
 483         if (k1.type < k2->type)
 484                 return -1;
 485         if (k1.offset > k2->offset)
 486                 return 1;
 487         if (k1.offset < k2->offset)
 488                 return -1;
 489         return 0;
 490 }
 491
 492 /*
 493  * same as comp_keys only with two btrfs_key's
 494  */
 495 static int comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
 496 {
 497         if (k1->objectid > k2->objectid)
 498                 return 1;
 499         if (k1->objectid < k2->objectid)
 500                 return -1;
 501         if (k1->type > k2->type)
 502                 return 1;
 503         if (k1->type < k2->type)
 504                 return -1;
 505         if (k1->offset > k2->offset)
 506                 return 1;
 507         if (k1->offset < k2->offset)
 508                 return -1;
 509         return 0;
 510 }
 511
 512 /*
 513  * this is used by the defrag code to go through all the
 514  * leaves pointed to by a node and reallocate them so that
 515  * disk order is close to key order
 516  */
 517 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
 518                        struct btrfs_root *root, struct extent_buffer *parent,
 519                        int start_slot, int cache_only, u64 *last_ret,
 520                        struct btrfs_key *progress)
 521 {
 522         struct extent_buffer *cur;
 523         u64 blocknr;
 524         u64 gen;
 525         u64 search_start = *last_ret;
 526         u64 last_block = 0;
 527         u64 other;
 528         u32 parent_nritems;
 529         int end_slot;
 530         int i;
 531         int err = 0;
 532         int parent_level;
 533         int uptodate;
 534         u32 blocksize;
 535         int progress_passed = 0;
 536         struct btrfs_disk_key disk_key;
 537
 538         parent_level = btrfs_header_level(parent);
 539         if (cache_only && parent_level != 1)
 540                 return 0;
 541
 542         if (trans->transaction != root->fs_info->running_transaction)
 543                 WARN_ON(1);
 544         if (trans->transid != root->fs_info->generation)
 545                 WARN_ON(1);
 546
 547         parent_nritems = btrfs_header_nritems(parent);
 548         blocksize = btrfs_level_size(root, parent_level - 1);
 549         end_slot = parent_nritems;
 550
 551         if (parent_nritems == 1)
 552                 return 0;
 553
 554         btrfs_set_lock_blocking(parent);
 555
 556         for (i = start_slot; i < end_slot; i++) {
 557                 int close = 1;
 558
 559                 if (!parent->map_token) {
 560                         map_extent_buffer(parent,
 561                                         btrfs_node_key_ptr_offset(i),
 562                                         sizeof(struct btrfs_key_ptr),
 563                                         &parent->map_token, &parent->kaddr,
 564                                         &parent->map_start, &parent->map_len,
 565                                         KM_USER1);
 566                 }
 567                 btrfs_node_key(parent, &disk_key, i);
 568                 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
 569                         continue;
 570
 571                 progress_passed = 1;
 572                 blocknr = btrfs_node_blockptr(parent, i);
 573                 gen = btrfs_node_ptr_generation(parent, i);
 574                 if (last_block == 0)
 575                         last_block = blocknr;
 576
 577                 if (i > 0) {
 578                         other = btrfs_node_blockptr(parent, i - 1);
 579                         close = close_blocks(blocknr, other, blocksize);
 580                 }
 581                 if (!close && i < end_slot - 2) {
 582                         other = btrfs_node_blockptr(parent, i + 1);
 583                         close = close_blocks(blocknr, other, blocksize);
 584                 }
 585                 if (close) {
 586                         last_block = blocknr;
 587                         continue;
 588                 }
 589                 if (parent->map_token) {
 590                         unmap_extent_buffer(parent, parent->map_token,
 591                                             KM_USER1);
 592                         parent->map_token = NULL;
 593                 }
 594
 595                 cur = btrfs_find_tree_block(root, blocknr, blocksize);
 596                 if (cur)
 597                         uptodate = btrfs_buffer_uptodate(cur, gen);
 598                 else
 599                         uptodate = 0;
 600                 if (!cur || !uptodate) {
 601                         if (cache_only) {
 602                                 free_extent_buffer(cur);
 603                                 continue;
 604                         }
 605                         if (!cur) {
 606                                 cur = read_tree_block(root, blocknr,
 607                                                          blocksize, gen);
 608                         } else if (!uptodate) {
 609                                 btrfs_read_buffer(cur, gen);
 610                         }
 611                 }
 612                 if (search_start == 0)
 613                         search_start = last_block;
 614
 615                 btrfs_tree_lock(cur);
 616                 btrfs_set_lock_blocking(cur);
 617                 err = __btrfs_cow_block(trans, root, cur, parent, i,
 618                                         &cur, search_start,
 619                                         min(16 * blocksize,
 620                                             (end_slot - i) * blocksize), 0);
 621                 if (err) {
 622                         btrfs_tree_unlock(cur);
 623                         free_extent_buffer(cur);
 624                         break;
 625                 }
 626                 search_start = cur->start;
 627                 last_block = cur->start;
 628                 *last_ret = search_start;
 629                 btrfs_tree_unlock(cur);
 630                 free_extent_buffer(cur);
 631         }
 632         if (parent->map_token) {
 633                 unmap_extent_buffer(parent, parent->map_token,
 634                                     KM_USER1);
 635                 parent->map_token = NULL;
 636         }
 637         return err;
 638 }
 639
 640 /*
 641  * The leaf data grows from end-to-front in the node.
 642  * this returns the address of the start of the last item,
 643  * which is the stop of the leaf data stack
 644  */
 645 static inline unsigned int leaf_data_end(struct btrfs_root *root,
 646                                          struct extent_buffer *leaf)
 647 {
 648         u32 nr = btrfs_header_nritems(leaf);
 649         if (nr == 0)
 650                 return BTRFS_LEAF_DATA_SIZE(root);
 651         return btrfs_item_offset_nr(leaf, nr - 1);
 652 }
 653
 654 /*
 655  * extra debugging checks to make sure all the items in a key are
 656  * well formed and in the proper order
 657  */
 658 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
 659                       int level)
 660 {
 661         struct extent_buffer *parent = NULL;
 662         struct extent_buffer *node = path->nodes[level];
 663         struct btrfs_disk_key parent_key;
 664         struct btrfs_disk_key node_key;
 665         int parent_slot;
 666         int slot;
 667         struct btrfs_key cpukey;
 668         u32 nritems = btrfs_header_nritems(node);
 669
 670         if (path->nodes[level + 1])
 671                 parent = path->nodes[level + 1];
 672
 673         slot = path->slots[level];
 674         BUG_ON(nritems == 0);
 675         if (parent) {
 676                 parent_slot = path->slots[level + 1];
 677                 btrfs_node_key(parent, &parent_key, parent_slot);
 678                 btrfs_node_key(node, &node_key, 0);
 679                 BUG_ON(memcmp(&parent_key, &node_key,
 680                               sizeof(struct btrfs_disk_key)));
 681                 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
 682                        btrfs_header_bytenr(node));
 683         }
 684         BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
 685         if (slot != 0) {
 686                 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
 687                 btrfs_node_key(node, &node_key, slot);
 688                 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
 689         }
 690         if (slot < nritems - 1) {
 691                 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
 692                 btrfs_node_key(node, &node_key, slot);
 693                 BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
 694         }
 695         return 0;
 696 }
 697
 698 /*
 699  * extra checking to make sure all the items in a leaf are
 700  * well formed and in the proper order
 701  */
 702 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
 703                       int level)
 704 {
 705         struct extent_buffer *leaf = path->nodes[level];
 706         struct extent_buffer *parent = NULL;
 707         int parent_slot;
 708         struct btrfs_key cpukey;
 709         struct btrfs_disk_key parent_key;
 710         struct btrfs_disk_key leaf_key;
 711         int slot = path->slots[0];
 712
 713         u32 nritems = btrfs_header_nritems(leaf);
 714
 715         if (path->nodes[level + 1])
 716                 parent = path->nodes[level + 1];
 717
 718         if (nritems == 0)
 719                 return 0;
 720
 721         if (parent) {
 722                 parent_slot = path->slots[level + 1];
 723                 btrfs_node_key(parent, &parent_key, parent_slot);
 724                 btrfs_item_key(leaf, &leaf_key, 0);
 725
 726                 BUG_ON(memcmp(&parent_key, &leaf_key,
 727                        sizeof(struct btrfs_disk_key)));
 728                 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
 729                        btrfs_header_bytenr(leaf));
 730         }
 731         if (slot != 0 && slot < nritems - 1) {
 732                 btrfs_item_key(leaf, &leaf_key, slot);
 733                 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
 734                 if (comp_keys(&leaf_key, &cpukey) <= 0) {
 735                         btrfs_print_leaf(root, leaf);
 736                         printk(KERN_CRIT "slot %d offset bad key\n", slot);
 737                         BUG_ON(1);
 738                 }
 739                 if (btrfs_item_offset_nr(leaf, slot - 1) !=
 740                        btrfs_item_end_nr(leaf, slot)) {
 741                         btrfs_print_leaf(root, leaf);
 742                         printk(KERN_CRIT "slot %d offset bad\n", slot);
 743                         BUG_ON(1);
 744                 }
 745         }
 746         if (slot < nritems - 1) {
 747                 btrfs_item_key(leaf, &leaf_key, slot);
 748                 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
 749                 BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
 750                 if (btrfs_item_offset_nr(leaf, slot) !=
 751                         btrfs_item_end_nr(leaf, slot + 1)) {
 752                         btrfs_print_leaf(root, leaf);
 753                         printk(KERN_CRIT "slot %d offset bad\n", slot);
 754                         BUG_ON(1);
 755                 }
 756         }
 757         BUG_ON(btrfs_item_offset_nr(leaf, 0) +
 758                btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
 759         return 0;
 760 }
 761
 762 static noinline int check_block(struct btrfs_root *root,
 763                                 struct btrfs_path *path, int level)
 764 {
 765         return 0;
 766         if (level == 0)
 767                 return check_leaf(root, path, level);
 768         return check_node(root, path, level);
 769 }
 770
 771 /*
 772  * search for key in the extent_buffer.  The items start at offset p,
 773  * and they are item_size apart.  There are 'max' items in p.
 774  *
 775  * the slot in the array is returned via slot, and it points to
 776  * the place where you would insert key if it is not found in
 777  * the array.
 778  *
 779  * slot may point to max if the key is bigger than all of the keys
 780  */
 781 static noinline int generic_bin_search(struct extent_buffer *eb,
 782                                        unsigned long p,
 783                                        int item_size, struct btrfs_key *key,
 784                                        int max, int *slot)
 785 {
 786         int low = 0;
 787         int high = max;
 788         int mid;
 789         int ret;
 790         struct btrfs_disk_key *tmp = NULL;
 791         struct btrfs_disk_key unaligned;
 792         unsigned long offset;
 793         char *map_token = NULL;
 794         char *kaddr = NULL;
 795         unsigned long map_start = 0;
 796         unsigned long map_len = 0;
 797         int err;
 798
 799         while (low < high) {
 800                 mid = (low + high) / 2;
 801                 offset = p + mid * item_size;
 802
 803                 if (!map_token || offset < map_start ||
 804                     (offset + sizeof(struct btrfs_disk_key)) >
 805                     map_start + map_len) {
 806                         if (map_token) {
 807                                 unmap_extent_buffer(eb, map_token, KM_USER0);
 808                                 map_token = NULL;
 809                         }
 810
 811                         err = map_private_extent_buffer(eb, offset,
 812                                                 sizeof(struct btrfs_disk_key),
 813                                                 &map_token, &kaddr,
 814                                                 &map_start, &map_len, KM_USER0);
 815
 816                         if (!err) {
 817                                 tmp = (struct btrfs_disk_key *)(kaddr + offset -
 818                                                         map_start);
 819                         } else {
 820                                 read_extent_buffer(eb, &unaligned,
 821                                                    offset, sizeof(unaligned));
 822                                 tmp = &unaligned;
 823                         }
 824
 825                 } else {
 826                         tmp = (struct btrfs_disk_key *)(kaddr + offset -
 827                                                         map_start);
 828                 }
 829                 ret = comp_keys(tmp, key);
 830
 831                 if (ret < 0)
 832                         low = mid + 1;
 833                 else if (ret > 0)
 834                         high = mid;
 835                 else {
 836                         *slot = mid;
 837                         if (map_token)
 838                                 unmap_extent_buffer(eb, map_token, KM_USER0);
 839                         return 0;
 840                 }
 841         }
 842         *slot = low;
 843         if (map_token)
 844                 unmap_extent_buffer(eb, map_token, KM_USER0);
 845         return 1;
 846 }
 847
 848 /*
 849  * simple bin_search frontend that does the right thing for
 850  * leaves vs nodes
 851  */
 852 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
 853                       int level, int *slot)
 854 {
 855         if (level == 0) {
 856                 return generic_bin_search(eb,
 857                                           offsetof(struct btrfs_leaf, items),
 858                                           sizeof(struct btrfs_item),
 859                                           key, btrfs_header_nritems(eb),
 860                                           slot);
 861         } else {
 862                 return generic_bin_search(eb,
 863                                           offsetof(struct btrfs_node, ptrs),
 864                                           sizeof(struct btrfs_key_ptr),
 865                                           key, btrfs_header_nritems(eb),
 866                                           slot);
 867         }
 868         return -1;
 869 }
 870
 871 /* given a node and slot number, this reads the blocks it points to.  The
 872  * extent buffer is returned with a reference taken (but unlocked).
 873  * NULL is returned on error.
 874  */
 875 static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
 876                                    struct extent_buffer *parent, int slot)
 877 {
 878         int level = btrfs_header_level(parent);
 879         if (slot < 0)
 880                 return NULL;
 881         if (slot >= btrfs_header_nritems(parent))
 882                 return NULL;
 883
 884         BUG_ON(level == 0);
 885
 886         return read_tree_block(root, btrfs_node_blockptr(parent, slot),
 887                        btrfs_level_size(root, level - 1),
 888                        btrfs_node_ptr_generation(parent, slot));
 889 }
 890
 891 /*
 892  * node level balancing, used to make sure nodes are in proper order for
 893  * item deletion.  We balance from the top down, so we have to make sure
 894  * that a deletion won't leave an node completely empty later on.
 895  */
 896 static noinline int balance_level(struct btrfs_trans_handle *trans,
 897                          struct btrfs_root *root,
 898                          struct btrfs_path *path, int level)
 899 {
 900         struct extent_buffer *right = NULL;
 901         struct extent_buffer *mid;
 902         struct extent_buffer *left = NULL;
 903         struct extent_buffer *parent = NULL;
 904         int ret = 0;
 905         int wret;
 906         int pslot;
 907         int orig_slot = path->slots[level];
 908         int err_on_enospc = 0;
 909         u64 orig_ptr;
 910
 911         if (level == 0)
 912                 return 0;
 913
 914         mid = path->nodes[level];
 915
 916         WARN_ON(!path->locks[level]);
 917         WARN_ON(btrfs_header_generation(mid) != trans->transid);
 918
 919         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
 920
 921         if (level < BTRFS_MAX_LEVEL - 1)
 922                 parent = path->nodes[level + 1];
 923         pslot = path->slots[level + 1];
 924
 925         /*
 926          * deal with the case where there is only one pointer in the root
 927          * by promoting the node below to a root
 928          */
 929         if (!parent) {
 930                 struct extent_buffer *child;
 931
 932                 if (btrfs_header_nritems(mid) != 1)
 933                         return 0;
 934
 935                 /* promote the child to a root */
 936                 child = read_node_slot(root, mid, 0);
 937                 BUG_ON(!child);
 938                 btrfs_tree_lock(child);
 939                 btrfs_set_lock_blocking(child);
 940                 ret = btrfs_cow_block(trans, root, child, mid, 0, &child, 0);
 941                 BUG_ON(ret);
 942
 943                 spin_lock(&root->node_lock);
 944                 root->node = child;
 945                 spin_unlock(&root->node_lock);
 946
 947                 ret = btrfs_update_extent_ref(trans, root, child->start,
 948                                               mid->start, child->start,
 949                                               root->root_key.objectid,
 950                                               trans->transid, level - 1);
 951                 BUG_ON(ret);
 952
 953                 add_root_to_dirty_list(root);
 954                 btrfs_tree_unlock(child);
 955
 956                 path->locks[level] = 0;
 957                 path->nodes[level] = NULL;
 958                 clean_tree_block(trans, root, mid);
 959                 btrfs_tree_unlock(mid);
 960                 /* once for the path */
 961                 free_extent_buffer(mid);
 962                 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
 963                                         mid->start, root->root_key.objectid,
 964                                         btrfs_header_generation(mid),
 965                                         level, 1);
 966                 /* once for the root ptr */
 967                 free_extent_buffer(mid);
 968                 return ret;
 969         }
 970         if (btrfs_header_nritems(mid) >
 971             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
 972                 return 0;
 973
 974         if (btrfs_header_nritems(mid) < 2)
 975                 err_on_enospc = 1;
 976
 977         left = read_node_slot(root, parent, pslot - 1);
 978         if (left) {
 979                 btrfs_tree_lock(left);
 980                 btrfs_set_lock_blocking(left);
 981                 wret = btrfs_cow_block(trans, root, left,
 982                                        parent, pslot - 1, &left, 0);
 983                 if (wret) {
 984                         ret = wret;
 985                         goto enospc;
 986                 }
 987         }
 988         right = read_node_slot(root, parent, pslot + 1);
 989         if (right) {
 990                 btrfs_tree_lock(right);
 991                 btrfs_set_lock_blocking(right);
 992                 wret = btrfs_cow_block(trans, root, right,
 993                                        parent, pslot + 1, &right, 0);
 994                 if (wret) {
 995                         ret = wret;
 996                         goto enospc;
 997                 }
 998         }
 999
1000         /* first, try to make some room in the middle buffer */
1001         if (left) {
1002                 orig_slot += btrfs_header_nritems(left);
1003                 wret = push_node_left(trans, root, left, mid, 1);
1004                 if (wret < 0)
1005                         ret = wret;
1006                 if (btrfs_header_nritems(mid) < 2)
1007                         err_on_enospc = 1;
1008         }
1009
1010         /*
1011          * then try to empty the right most buffer into the middle
1012          */
1013         if (right) {
1014                 wret = push_node_left(trans, root, mid, right, 1);
1015                 if (wret < 0 && wret != -ENOSPC)
1016                         ret = wret;
1017                 if (btrfs_header_nritems(right) == 0) {
1018                         u64 bytenr = right->start;
1019                         u64 generation = btrfs_header_generation(parent);
1020                         u32 blocksize = right->len;
1021
1022                         clean_tree_block(trans, root, right);
1023                         btrfs_tree_unlock(right);
1024                         free_extent_buffer(right);
1025                         right = NULL;
1026                         wret = del_ptr(trans, root, path, level + 1, pslot +
1027                                        1);
1028                         if (wret)
1029                                 ret = wret;
1030                         wret = btrfs_free_extent(trans, root, bytenr,
1031                                                  blocksize, parent->start,
1032                                                  btrfs_header_owner(parent),
1033                                                  generation, level, 1);
1034                         if (wret)
1035                                 ret = wret;
1036                 } else {
1037                         struct btrfs_disk_key right_key;
1038                         btrfs_node_key(right, &right_key, 0);
1039                         btrfs_set_node_key(parent, &right_key, pslot + 1);
1040                         btrfs_mark_buffer_dirty(parent);
1041                 }
1042         }
1043         if (btrfs_header_nritems(mid) == 1) {
1044                 /*
1045                  * we're not allowed to leave a node with one item in the
1046                  * tree during a delete.  A deletion from lower in the tree
1047                  * could try to delete the only pointer in this node.
1048                  * So, pull some keys from the left.
1049                  * There has to be a left pointer at this point because
1050                  * otherwise we would have pulled some pointers from the
1051                  * right
1052                  */
1053                 BUG_ON(!left);
1054                 wret = balance_node_right(trans, root, mid, left);
1055                 if (wret < 0) {
1056                         ret = wret;
1057                         goto enospc;
1058                 }
1059                 if (wret == 1) {
1060                         wret = push_node_left(trans, root, left, mid, 1);
1061                         if (wret < 0)
1062                                 ret = wret;
1063                 }
1064                 BUG_ON(wret == 1);
1065         }
1066         if (btrfs_header_nritems(mid) == 0) {
1067                 /* we've managed to empty the middle node, drop it */
1068                 u64 root_gen = btrfs_header_generation(parent);
1069                 u64 bytenr = mid->start;
1070                 u32 blocksize = mid->len;
1071
1072                 clean_tree_block(trans, root, mid);
1073                 btrfs_tree_unlock(mid);
1074                 free_extent_buffer(mid);
1075                 mid = NULL;
1076                 wret = del_ptr(trans, root, path, level + 1, pslot);
1077                 if (wret)
1078                         ret = wret;
1079                 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
1080                                          parent->start,
1081                                          btrfs_header_owner(parent),
1082                                          root_gen, level, 1);
1083                 if (wret)
1084                         ret = wret;
1085         } else {
1086                 /* update the parent key to reflect our changes */
1087                 struct btrfs_disk_key mid_key;
1088                 btrfs_node_key(mid, &mid_key, 0);
1089                 btrfs_set_node_key(parent, &mid_key, pslot);
1090                 btrfs_mark_buffer_dirty(parent);
1091         }
1092
1093         /* update the path */
1094         if (left) {
1095                 if (btrfs_header_nritems(left) > orig_slot) {
1096                         extent_buffer_get(left);
1097                         /* left was locked after cow */
1098                         path->nodes[level] = left;
1099                         path->slots[level + 1] -= 1;
1100                         path->slots[level] = orig_slot;
1101                         if (mid) {
1102                                 btrfs_tree_unlock(mid);
1103                                 free_extent_buffer(mid);
1104                         }
1105                 } else {
1106                         orig_slot -= btrfs_header_nritems(left);
1107                         path->slots[level] = orig_slot;
1108                 }
1109         }
1110         /* double check we haven't messed things up */
1111         check_block(root, path, level);
1112         if (orig_ptr !=
1113             btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1114                 BUG();
1115 enospc:
1116         if (right) {
1117                 btrfs_tree_unlock(right);
1118                 free_extent_buffer(right);
1119         }
1120         if (left) {
1121                 if (path->nodes[level] != left)
1122                         btrfs_tree_unlock(left);
1123                 free_extent_buffer(left);
1124         }
1125         return ret;
1126 }
1127
1128 /* Node balancing for insertion.  Here we only split or push nodes around
1129  * when they are completely full.  This is also done top down, so we
1130  * have to be pessimistic.
1131  */
1132 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1133                                           struct btrfs_root *root,
1134                                           struct btrfs_path *path, int level)
1135 {
1136         struct extent_buffer *right = NULL;
1137         struct extent_buffer *mid;
1138         struct extent_buffer *left = NULL;
1139         struct extent_buffer *parent = NULL;
1140         int ret = 0;
1141         int wret;
1142         int pslot;
1143         int orig_slot = path->slots[level];
1144         u64 orig_ptr;
1145
1146         if (level == 0)
1147                 return 1;
1148
1149         mid = path->nodes[level];
1150         WARN_ON(btrfs_header_generation(mid) != trans->transid);
1151         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1152
1153         if (level < BTRFS_MAX_LEVEL - 1)
1154                 parent = path->nodes[level + 1];
1155         pslot = path->slots[level + 1];
1156
1157         if (!parent)
1158                 return 1;
1159
1160         left = read_node_slot(root, parent, pslot - 1);
1161
1162         /* first, try to make some room in the middle buffer */
1163         if (left) {
1164                 u32 left_nr;
1165
1166                 btrfs_tree_lock(left);
1167                 btrfs_set_lock_blocking(left);
1168
1169                 left_nr = btrfs_header_nritems(left);
1170                 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1171                         wret = 1;
1172                 } else {
1173                         ret = btrfs_cow_block(trans, root, left, parent,
1174                                               pslot - 1, &left, 0);
1175                         if (ret)
1176                                 wret = 1;
1177                         else {
1178                                 wret = push_node_left(trans, root,
1179                                                       left, mid, 0);
1180                         }
1181                 }
1182                 if (wret < 0)
1183                         ret = wret;
1184                 if (wret == 0) {
1185                         struct btrfs_disk_key disk_key;
1186                         orig_slot += left_nr;
1187                         btrfs_node_key(mid, &disk_key, 0);
1188                         btrfs_set_node_key(parent, &disk_key, pslot);
1189                         btrfs_mark_buffer_dirty(parent);
1190                         if (btrfs_header_nritems(left) > orig_slot) {
1191                                 path->nodes[level] = left;
1192                                 path->slots[level + 1] -= 1;
1193                                 path->slots[level] = orig_slot;
1194                                 btrfs_tree_unlock(mid);
1195                                 free_extent_buffer(mid);
1196                         } else {
1197                                 orig_slot -=
1198                                         btrfs_header_nritems(left);
1199                                 path->slots[level] = orig_slot;
1200                                 btrfs_tree_unlock(left);
1201                                 free_extent_buffer(left);
1202                         }
1203                         return 0;
1204                 }
1205                 btrfs_tree_unlock(left);
1206                 free_extent_buffer(left);
1207         }
1208         right = read_node_slot(root, parent, pslot + 1);
1209
1210         /*
1211          * then try to empty the right most buffer into the middle
1212          */
1213         if (right) {
1214                 u32 right_nr;
1215
1216                 btrfs_tree_lock(right);
1217                 btrfs_set_lock_blocking(right);
1218
1219                 right_nr = btrfs_header_nritems(right);
1220                 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1221                         wret = 1;
1222                 } else {
1223                         ret = btrfs_cow_block(trans, root, right,
1224                                               parent, pslot + 1,
1225                                               &right, 0);
1226                         if (ret)
1227                                 wret = 1;
1228                         else {
1229                                 wret = balance_node_right(trans, root,
1230                                                           right, mid);
1231                         }
1232                 }
1233                 if (wret < 0)
1234                         ret = wret;
1235                 if (wret == 0) {
1236                         struct btrfs_disk_key disk_key;
1237
1238                         btrfs_node_key(right, &disk_key, 0);
1239                         btrfs_set_node_key(parent, &disk_key, pslot + 1);
1240                         btrfs_mark_buffer_dirty(parent);
1241
1242                         if (btrfs_header_nritems(mid) <= orig_slot) {
1243                                 path->nodes[level] = right;
1244                                 path->slots[level + 1] += 1;
1245                                 path->slots[level] = orig_slot -
1246                                         btrfs_header_nritems(mid);
1247                                 btrfs_tree_unlock(mid);
1248                                 free_extent_buffer(mid);
1249                         } else {
1250                                 btrfs_tree_unlock(right);
1251                                 free_extent_buffer(right);
1252                         }
1253                         return 0;
1254                 }
1255                 btrfs_tree_unlock(right);
1256                 free_extent_buffer(right);
1257         }
1258         return 1;
1259 }
1260
1261 /*
1262  * readahead one full node of leaves, finding things that are close
1263  * to the block in 'slot', and triggering ra on them.
1264  */
1265 static noinline void reada_for_search(struct btrfs_root *root,
1266                                       struct btrfs_path *path,
1267                                       int level, int slot, u64 objectid)
1268 {
1269         struct extent_buffer *node;
1270         struct btrfs_disk_key disk_key;
1271         u32 nritems;
1272         u64 search;
1273         u64 target;
1274         u64 nread = 0;
1275         int direction = path->reada;
1276         struct extent_buffer *eb;
1277         u32 nr;
1278         u32 blocksize;
1279         u32 nscan = 0;
1280
1281         if (level != 1)
1282                 return;
1283
1284         if (!path->nodes[level])
1285                 return;
1286
1287         node = path->nodes[level];
1288
1289         search = btrfs_node_blockptr(node, slot);
1290         blocksize = btrfs_level_size(root, level - 1);
1291         eb = btrfs_find_tree_block(root, search, blocksize);
1292         if (eb) {
1293                 free_extent_buffer(eb);
1294                 return;
1295         }
1296
1297         target = search;
1298
1299         nritems = btrfs_header_nritems(node);
1300         nr = slot;
1301         while (1) {
1302                 if (direction < 0) {
1303                         if (nr == 0)
1304                                 break;
1305                         nr--;
1306                 } else if (direction > 0) {
1307                         nr++;
1308                         if (nr >= nritems)
1309                                 break;
1310                 }
1311                 if (path->reada < 0 && objectid) {
1312                         btrfs_node_key(node, &disk_key, nr);
1313                         if (btrfs_disk_key_objectid(&disk_key) != objectid)
1314                                 break;
1315                 }
1316                 search = btrfs_node_blockptr(node, nr);
1317                 if ((search <= target && target - search <= 65536) ||
1318                     (search > target && search - target <= 65536)) {
1319                         readahead_tree_block(root, search, blocksize,
1320                                      btrfs_node_ptr_generation(node, nr));
1321                         nread += blocksize;
1322                 }
1323                 nscan++;
1324                 if ((nread > 65536 || nscan > 32))
1325                         break;
1326         }
1327 }
1328
1329 /*
1330  * returns -EAGAIN if it had to drop the path, or zero if everything was in
1331  * cache
1332  */
1333 static noinline int reada_for_balance(struct btrfs_root *root,
1334                                       struct btrfs_path *path, int level)
1335 {
1336         int slot;
1337         int nritems;
1338         struct extent_buffer *parent;
1339         struct extent_buffer *eb;
1340         u64 gen;
1341         u64 block1 = 0;
1342         u64 block2 = 0;
1343         int ret = 0;
1344         int blocksize;
1345
1346         parent = path->nodes[level - 1];
1347         if (!parent)
1348                 return 0;
1349
1350         nritems = btrfs_header_nritems(parent);
1351         slot = path->slots[level];
1352         blocksize = btrfs_level_size(root, level);
1353
1354         if (slot > 0) {
1355                 block1 = btrfs_node_blockptr(parent, slot - 1);
1356                 gen = btrfs_node_ptr_generation(parent, slot - 1);
1357                 eb = btrfs_find_tree_block(root, block1, blocksize);
1358                 if (eb && btrfs_buffer_uptodate(eb, gen))
1359                         block1 = 0;
1360                 free_extent_buffer(eb);
1361         }
1362         if (slot < nritems) {
1363                 block2 = btrfs_node_blockptr(parent, slot + 1);
1364                 gen = btrfs_node_ptr_generation(parent, slot + 1);
1365                 eb = btrfs_find_tree_block(root, block2, blocksize);
1366                 if (eb && btrfs_buffer_uptodate(eb, gen))
1367                         block2 = 0;
1368                 free_extent_buffer(eb);
1369         }
1370         if (block1 || block2) {
1371                 ret = -EAGAIN;
1372                 btrfs_release_path(root, path);
1373                 if (block1)
1374                         readahead_tree_block(root, block1, blocksize, 0);
1375                 if (block2)
1376                         readahead_tree_block(root, block2, blocksize, 0);
1377
1378                 if (block1) {
1379                         eb = read_tree_block(root, block1, blocksize, 0);
1380                         free_extent_buffer(eb);
1381                 }
1382                 if (block1) {
1383                         eb = read_tree_block(root, block2, blocksize, 0);
1384                         free_extent_buffer(eb);
1385                 }
1386         }
1387         return ret;
1388 }
1389
1390
1391 /*
1392  * when we walk down the tree, it is usually safe to unlock the higher layers
1393  * in the tree.  The exceptions are when our path goes through slot 0, because
1394  * operations on the tree might require changing key pointers higher up in the
1395  * tree.
1396  *
1397  * callers might also have set path->keep_locks, which tells this code to keep
1398  * the lock if the path points to the last slot in the block.  This is part of
1399  * walking through the tree, and selecting the next slot in the higher block.
1400  *
1401  * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
1402  * if lowest_unlock is 1, level 0 won't be unlocked
1403  */
1404 static noinline void unlock_up(struct btrfs_path *path, int level,
1405                                int lowest_unlock)
1406 {
1407         int i;
1408         int skip_level = level;
1409         int no_skips = 0;
1410         struct extent_buffer *t;
1411
1412         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1413                 if (!path->nodes[i])
1414                         break;
1415                 if (!path->locks[i])
1416                         break;
1417                 if (!no_skips && path->slots[i] == 0) {
1418                         skip_level = i + 1;
1419                         continue;
1420                 }
1421                 if (!no_skips && path->keep_locks) {
1422                         u32 nritems;
1423                         t = path->nodes[i];
1424                         nritems = btrfs_header_nritems(t);
1425                         if (nritems < 1 || path->slots[i] >= nritems - 1) {
1426                                 skip_level = i + 1;
1427                                 continue;
1428                         }
1429                 }
1430                 if (skip_level < i && i >= lowest_unlock)
1431                         no_skips = 1;
1432
1433                 t = path->nodes[i];
1434                 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1435                         btrfs_tree_unlock(t);
1436                         path->locks[i] = 0;
1437                 }
1438         }
1439 }
1440
1441 /*
1442  * This releases any locks held in the path starting at level and
1443  * going all the way up to the root.
1444  *
1445  * btrfs_search_slot will keep the lock held on higher nodes in a few
1446  * corner cases, such as COW of the block at slot zero in the node.  This
1447  * ignores those rules, and it should only be called when there are no
1448  * more updates to be done higher up in the tree.
1449  */
1450 noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1451 {
1452         int i;
1453
1454         if (path->keep_locks || path->lowest_level)
1455                 return;
1456
1457         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1458                 if (!path->nodes[i])
1459                         continue;
1460                 if (!path->locks[i])
1461                         continue;
1462                 btrfs_tree_unlock(path->nodes[i]);
1463                 path->locks[i] = 0;
1464         }
1465 }
1466
1467 /*
1468  * look for key in the tree.  path is filled in with nodes along the way
1469  * if key is found, we return zero and you can find the item in the leaf
1470  * level of the path (level 0)
1471  *
1472  * If the key isn't found, the path points to the slot where it should
1473  * be inserted, and 1 is returned.  If there are other errors during the
1474  * search a negative error number is returned.
1475  *
1476  * if ins_len > 0, nodes and leaves will be split as we walk down the
1477  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
1478  * possible)
1479  */
1480 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1481                       *root, struct btrfs_key *key, struct btrfs_path *p, int
1482                       ins_len, int cow)
1483 {
1484         struct extent_buffer *b;
1485         struct extent_buffer *tmp;
1486         int slot;
1487         int ret;
1488         int level;
1489         int should_reada = p->reada;
1490         int lowest_unlock = 1;
1491         int blocksize;
1492         u8 lowest_level = 0;
1493         u64 blocknr;
1494         u64 gen;
1495         struct btrfs_key prealloc_block;
1496
1497         lowest_level = p->lowest_level;
1498         WARN_ON(lowest_level && ins_len > 0);
1499         WARN_ON(p->nodes[0] != NULL);
1500
1501         if (ins_len < 0)
1502                 lowest_unlock = 2;
1503
1504         prealloc_block.objectid = 0;
1505
1506 again:
1507         if (p->skip_locking)
1508                 b = btrfs_root_node(root);
1509         else
1510                 b = btrfs_lock_root_node(root);
1511
1512         while (b) {
1513                 level = btrfs_header_level(b);
1514
1515                 /*
1516                  * setup the path here so we can release it under lock
1517                  * contention with the cow code
1518                  */
1519                 p->nodes[level] = b;
1520                 if (!p->skip_locking)
1521                         p->locks[level] = 1;
1522
1523                 if (cow) {
1524                         int wret;
1525
1526                         /* is a cow on this block not required */
1527                         if (btrfs_header_generation(b) == trans->transid &&
1528                             btrfs_header_owner(b) == root->root_key.objectid &&
1529                             !btrfs_header_flag(b, BTRFS_HEADER_FLAG_WRITTEN)) {
1530                                 goto cow_done;
1531                         }
1532
1533                         /* ok, we have to cow, is our old prealloc the right
1534                          * size?
1535                          */
1536                         if (prealloc_block.objectid &&
1537                             prealloc_block.offset != b->len) {
1538                                 btrfs_release_path(root, p);
1539                                 btrfs_free_reserved_extent(root,
1540                                            prealloc_block.objectid,
1541                                            prealloc_block.offset);
1542                                 prealloc_block.objectid = 0;
1543                                 goto again;
1544                         }
1545
1546                         /*
1547                          * for higher level blocks, try not to allocate blocks
1548                          * with the block and the parent locks held.
1549                          */
1550                         if (level > 0 && !prealloc_block.objectid) {
1551                                 u32 size = b->len;
1552                                 u64 hint = b->start;
1553
1554                                 btrfs_release_path(root, p);
1555                                 ret = btrfs_reserve_extent(trans, root,
1556                                                            size, size, 0,
1557                                                            hint, (u64)-1,
1558                                                            &prealloc_block, 0);
1559                                 BUG_ON(ret);
1560                                 goto again;
1561                         }
1562
1563                         btrfs_set_path_blocking(p);
1564
1565                         wret = btrfs_cow_block(trans, root, b,
1566                                                p->nodes[level + 1],
1567                                                p->slots[level + 1],
1568                                                &b, prealloc_block.objectid);
1569                         prealloc_block.objectid = 0;
1570                         if (wret) {
1571                                 free_extent_buffer(b);
1572                                 ret = wret;
1573                                 goto done;
1574                         }
1575                 }
1576 cow_done:
1577                 BUG_ON(!cow && ins_len);
1578                 if (level != btrfs_header_level(b))
1579                         WARN_ON(1);
1580                 level = btrfs_header_level(b);
1581
1582                 p->nodes[level] = b;
1583                 if (!p->skip_locking)
1584                         p->locks[level] = 1;
1585
1586                 btrfs_clear_path_blocking(p, NULL);
1587
1588                 /*
1589                  * we have a lock on b and as long as we aren't changing
1590                  * the tree, there is no way to for the items in b to change.
1591                  * It is safe to drop the lock on our parent before we
1592                  * go through the expensive btree search on b.
1593                  *
1594                  * If cow is true, then we might be changing slot zero,
1595                  * which may require changing the parent.  So, we can't
1596                  * drop the lock until after we know which slot we're
1597                  * operating on.
1598                  */
1599                 if (!cow)
1600                         btrfs_unlock_up_safe(p, level + 1);
1601
1602                 ret = check_block(root, p, level);
1603                 if (ret) {
1604                         ret = -1;
1605                         goto done;
1606                 }
1607
1608                 ret = bin_search(b, key, level, &slot);
1609
1610                 if (level != 0) {
1611                         if (ret && slot > 0)
1612                                 slot -= 1;
1613                         p->slots[level] = slot;
1614                         if ((p->search_for_split || ins_len > 0) &&
1615                             btrfs_header_nritems(b) >=
1616                             BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1617                                 int sret;
1618
1619                                 sret = reada_for_balance(root, p, level);
1620                                 if (sret)
1621                                         goto again;
1622
1623                                 btrfs_set_path_blocking(p);
1624                                 sret = split_node(trans, root, p, level);
1625                                 btrfs_clear_path_blocking(p, NULL);
1626
1627                                 BUG_ON(sret > 0);
1628                                 if (sret) {
1629                                         ret = sret;
1630                                         goto done;
1631                                 }
1632                                 b = p->nodes[level];
1633                                 slot = p->slots[level];
1634                         } else if (ins_len < 0 &&
1635                                    btrfs_header_nritems(b) <
1636                                    BTRFS_NODEPTRS_PER_BLOCK(root) / 4) {
1637                                 int sret;
1638
1639                                 sret = reada_for_balance(root, p, level);
1640                                 if (sret)
1641                                         goto again;
1642
1643                                 btrfs_set_path_blocking(p);
1644                                 sret = balance_level(trans, root, p, level);
1645                                 btrfs_clear_path_blocking(p, NULL);
1646
1647                                 if (sret) {
1648                                         ret = sret;
1649                                         goto done;
1650                                 }
1651                                 b = p->nodes[level];
1652                                 if (!b) {
1653                                         btrfs_release_path(NULL, p);
1654                                         goto again;
1655                                 }
1656                                 slot = p->slots[level];
1657                                 BUG_ON(btrfs_header_nritems(b) == 1);
1658                         }
1659                         unlock_up(p, level, lowest_unlock);
1660
1661                         /* this is only true while dropping a snapshot */
1662                         if (level == lowest_level) {
1663                                 ret = 0;
1664                                 goto done;
1665                         }
1666
1667                         blocknr = btrfs_node_blockptr(b, slot);
1668                         gen = btrfs_node_ptr_generation(b, slot);
1669                         blocksize = btrfs_level_size(root, level - 1);
1670
1671                         tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1672                         if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1673                                 b = tmp;
1674                         } else {
1675                                 /*
1676                                  * reduce lock contention at high levels
1677                                  * of the btree by dropping locks before
1678                                  * we read.
1679                                  */
1680                                 if (level > 0) {
1681                                         btrfs_release_path(NULL, p);
1682                                         if (tmp)
1683                                                 free_extent_buffer(tmp);
1684                                         if (should_reada)
1685                                                 reada_for_search(root, p,
1686                                                                  level, slot,
1687                                                                  key->objectid);
1688
1689                                         tmp = read_tree_block(root, blocknr,
1690                                                          blocksize, gen);
1691                                         if (tmp)
1692                                                 free_extent_buffer(tmp);
1693                                         goto again;
1694                                 } else {
1695                                         btrfs_set_path_blocking(p);
1696                                         if (tmp)
1697                                                 free_extent_buffer(tmp);
1698                                         if (should_reada)
1699                                                 reada_for_search(root, p,
1700                                                                  level, slot,
1701                                                                  key->objectid);
1702                                         b = read_node_slot(root, b, slot);
1703                                 }
1704                         }
1705                         if (!p->skip_locking) {
1706                                 int lret;
1707
1708                                 btrfs_clear_path_blocking(p, NULL);
1709                                 lret = btrfs_try_spin_lock(b);
1710
1711                                 if (!lret) {
1712                                         btrfs_set_path_blocking(p);
1713                                         btrfs_tree_lock(b);
1714                                         btrfs_clear_path_blocking(p, b);
1715                                 }
1716                         }
1717                 } else {
1718                         p->slots[level] = slot;
1719                         if (ins_len > 0 &&
1720                             btrfs_leaf_free_space(root, b) < ins_len) {
1721                                 int sret;
1722
1723                                 btrfs_set_path_blocking(p);
1724                                 sret = split_leaf(trans, root, key,
1725                                                       p, ins_len, ret == 0);
1726                                 btrfs_clear_path_blocking(p, NULL);
1727
1728                                 BUG_ON(sret > 0);
1729                                 if (sret) {
1730                                         ret = sret;
1731                                         goto done;
1732                                 }
1733                         }
1734                         if (!p->search_for_split)
1735                                 unlock_up(p, level, lowest_unlock);
1736                         goto done;
1737                 }
1738         }
1739         ret = 1;
1740 done:
1741         /*
1742          * we don't really know what they plan on doing with the path
1743          * from here on, so for now just mark it as blocking
1744          */
1745         btrfs_set_path_blocking(p);
1746         if (prealloc_block.objectid) {
1747                 btrfs_free_reserved_extent(root,
1748                            prealloc_block.objectid,
1749                            prealloc_block.offset);
1750         }
1751         return ret;
1752 }
1753
1754 int btrfs_merge_path(struct btrfs_trans_handle *trans,
1755                      struct btrfs_root *root,
1756                      struct btrfs_key *node_keys,
1757                      u64 *nodes, int lowest_level)
1758 {
1759         struct extent_buffer *eb;
1760         struct extent_buffer *parent;
1761         struct btrfs_key key;
1762         u64 bytenr;
1763         u64 generation;
1764         u32 blocksize;
1765         int level;
1766         int slot;
1767         int key_match;
1768         int ret;
1769
1770         eb = btrfs_lock_root_node(root);
1771         ret = btrfs_cow_block(trans, root, eb, NULL, 0, &eb, 0);
1772         BUG_ON(ret);
1773
1774         btrfs_set_lock_blocking(eb);
1775
1776         parent = eb;
1777         while (1) {
1778                 level = btrfs_header_level(parent);
1779                 if (level == 0 || level <= lowest_level)
1780                         break;
1781
1782                 ret = bin_search(parent, &node_keys[lowest_level], level,
1783                                  &slot);
1784                 if (ret && slot > 0)
1785                         slot--;
1786
1787                 bytenr = btrfs_node_blockptr(parent, slot);
1788                 if (nodes[level - 1] == bytenr)
1789                         break;
1790
1791                 blocksize = btrfs_level_size(root, level - 1);
1792                 generation = btrfs_node_ptr_generation(parent, slot);
1793                 btrfs_node_key_to_cpu(eb, &key, slot);
1794                 key_match = !memcmp(&key, &node_keys[level - 1], sizeof(key));
1795
1796                 if (generation == trans->transid) {
1797                         eb = read_tree_block(root, bytenr, blocksize,
1798                                              generation);
1799                         btrfs_tree_lock(eb);
1800                         btrfs_set_lock_blocking(eb);
1801                 }
1802
1803                 /*
1804                  * if node keys match and node pointer hasn't been modified
1805                  * in the running transaction, we can merge the path. for
1806                  * blocks owened by reloc trees, the node pointer check is
1807                  * skipped, this is because these blocks are fully controlled
1808                  * by the space balance code, no one else can modify them.
1809                  */
1810                 if (!nodes[level - 1] || !key_match ||
1811                     (generation == trans->transid &&
1812                      btrfs_header_owner(eb) != BTRFS_TREE_RELOC_OBJECTID)) {
1813                         if (level == 1 || level == lowest_level + 1) {
1814                                 if (generation == trans->transid) {
1815                                         btrfs_tree_unlock(eb);
1816                                         free_extent_buffer(eb);
1817                                 }
1818                                 break;
1819                         }
1820
1821                         if (generation != trans->transid) {
1822                                 eb = read_tree_block(root, bytenr, blocksize,
1823                                                 generation);
1824                                 btrfs_tree_lock(eb);
1825                                 btrfs_set_lock_blocking(eb);
1826                         }
1827
1828                         ret = btrfs_cow_block(trans, root, eb, parent, slot,
1829                                               &eb, 0);
1830                         BUG_ON(ret);
1831
1832                         if (root->root_key.objectid ==
1833                             BTRFS_TREE_RELOC_OBJECTID) {
1834                                 if (!nodes[level - 1]) {
1835                                         nodes[level - 1] = eb->start;
1836                                         memcpy(&node_keys[level - 1], &key,
1837                                                sizeof(node_keys[0]));
1838                                 } else {
1839                                         WARN_ON(1);
1840                                 }
1841                         }
1842
1843                         btrfs_tree_unlock(parent);
1844                         free_extent_buffer(parent);
1845                         parent = eb;
1846                         continue;
1847                 }
1848
1849                 btrfs_set_node_blockptr(parent, slot, nodes[level - 1]);
1850                 btrfs_set_node_ptr_generation(parent, slot, trans->transid);
1851                 btrfs_mark_buffer_dirty(parent);
1852
1853                 ret = btrfs_inc_extent_ref(trans, root,
1854                                         nodes[level - 1],
1855                                         blocksize, parent->start,
1856                                         btrfs_header_owner(parent),
1857                                         btrfs_header_generation(parent),
1858                                         level - 1);
1859                 BUG_ON(ret);
1860
1861                 /*
1862                  * If the block was created in the running transaction,
1863                  * it's possible this is the last reference to it, so we
1864                  * should drop the subtree.
1865                  */
1866                 if (generation == trans->transid) {
1867                         ret = btrfs_drop_subtree(trans, root, eb, parent);
1868                         BUG_ON(ret);
1869                         btrfs_tree_unlock(eb);
1870                         free_extent_buffer(eb);
1871                 } else {
1872                         ret = btrfs_free_extent(trans, root, bytenr,
1873                                         blocksize, parent->start,
1874                                         btrfs_header_owner(parent),
1875                                         btrfs_header_generation(parent),
1876                                         level - 1, 1);
1877                         BUG_ON(ret);
1878                 }
1879                 break;
1880         }
1881         btrfs_tree_unlock(parent);
1882         free_extent_buffer(parent);
1883         return 0;
1884 }
1885
1886 /*
1887  * adjust the pointers going up the tree, starting at level
1888  * making sure the right key of each node is points to 'key'.
1889  * This is used after shifting pointers to the left, so it stops
1890  * fixing up pointers when a given leaf/node is not in slot 0 of the
1891  * higher levels
1892  *
1893  * If this fails to write a tree block, it returns -1, but continues
1894  * fixing up the blocks in ram so the tree is consistent.
1895  */
1896 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1897                           struct btrfs_root *root, struct btrfs_path *path,
1898                           struct btrfs_disk_key *key, int level)
1899 {
1900         int i;
1901         int ret = 0;
1902         struct extent_buffer *t;
1903
1904         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1905                 int tslot = path->slots[i];
1906                 if (!path->nodes[i])
1907                         break;
1908                 t = path->nodes[i];
1909                 btrfs_set_node_key(t, key, tslot);
1910                 btrfs_mark_buffer_dirty(path->nodes[i]);
1911                 if (tslot != 0)
1912                         break;
1913         }
1914         return ret;
1915 }
1916
1917 /*
1918  * update item key.
1919  *
1920  * This function isn't completely safe. It's the caller's responsibility
1921  * that the new key won't break the order
1922  */
1923 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1924                             struct btrfs_root *root, struct btrfs_path *path,
1925                             struct btrfs_key *new_key)
1926 {
1927         struct btrfs_disk_key disk_key;
1928         struct extent_buffer *eb;
1929         int slot;
1930
1931         eb = path->nodes[0];
1932         slot = path->slots[0];
1933         if (slot > 0) {
1934                 btrfs_item_key(eb, &disk_key, slot - 1);
1935                 if (comp_keys(&disk_key, new_key) >= 0)
1936                         return -1;
1937         }
1938         if (slot < btrfs_header_nritems(eb) - 1) {
1939                 btrfs_item_key(eb, &disk_key, slot + 1);
1940                 if (comp_keys(&disk_key, new_key) <= 0)
1941                         return -1;
1942         }
1943
1944         btrfs_cpu_key_to_disk(&disk_key, new_key);
1945         btrfs_set_item_key(eb, &disk_key, slot);
1946         btrfs_mark_buffer_dirty(eb);
1947         if (slot == 0)
1948                 fixup_low_keys(trans, root, path, &disk_key, 1);
1949         return 0;
1950 }
1951
1952 /*
1953  * try to push data from one node into the next node left in the
1954  * tree.
1955  *
1956  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1957  * error, and > 0 if there was no room in the left hand block.
1958  */
1959 static int push_node_left(struct btrfs_trans_handle *trans,
1960                           struct btrfs_root *root, struct extent_buffer *dst,
1961                           struct extent_buffer *src, int empty)
1962 {
1963         int push_items = 0;
1964         int src_nritems;
1965         int dst_nritems;
1966         int ret = 0;
1967
1968         src_nritems = btrfs_header_nritems(src);
1969         dst_nritems = btrfs_header_nritems(dst);
1970         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1971         WARN_ON(btrfs_header_generation(src) != trans->transid);
1972         WARN_ON(btrfs_header_generation(dst) != trans->transid);
1973
1974         if (!empty && src_nritems <= 8)
1975                 return 1;
1976
1977         if (push_items <= 0)
1978                 return 1;
1979
1980         if (empty) {
1981                 push_items = min(src_nritems, push_items);
1982                 if (push_items < src_nritems) {
1983                         /* leave at least 8 pointers in the node if
1984                          * we aren't going to empty it
1985                          */
1986                         if (src_nritems - push_items < 8) {
1987                                 if (push_items <= 8)
1988                                         return 1;
1989                                 push_items -= 8;
1990                         }
1991                 }
1992         } else
1993                 push_items = min(src_nritems - 8, push_items);
1994
1995         copy_extent_buffer(dst, src,
1996                            btrfs_node_key_ptr_offset(dst_nritems),
1997                            btrfs_node_key_ptr_offset(0),
1998                            push_items * sizeof(struct btrfs_key_ptr));
1999
2000         if (push_items < src_nritems) {
2001                 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
2002                                       btrfs_node_key_ptr_offset(push_items),
2003                                       (src_nritems - push_items) *
2004                                       sizeof(struct btrfs_key_ptr));
2005         }
2006         btrfs_set_header_nritems(src, src_nritems - push_items);
2007         btrfs_set_header_nritems(dst, dst_nritems + push_items);
2008         btrfs_mark_buffer_dirty(src);
2009         btrfs_mark_buffer_dirty(dst);
2010
2011         ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items);
2012         BUG_ON(ret);
2013
2014         return ret;
2015 }
2016
2017 /*
2018  * try to push data from one node into the next node right in the
2019  * tree.
2020  *
2021  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
2022  * error, and > 0 if there was no room in the right hand block.
2023  *
2024  * this will  only push up to 1/2 the contents of the left node over
2025  */
2026 static int balance_node_right(struct btrfs_trans_handle *trans,
2027                               struct btrfs_root *root,
2028                               struct extent_buffer *dst,
2029                               struct extent_buffer *src)
2030 {
2031         int push_items = 0;
2032         int max_push;
2033         int src_nritems;
2034         int dst_nritems;
2035         int ret = 0;
2036
2037         WARN_ON(btrfs_header_generation(src) != trans->transid);
2038         WARN_ON(btrfs_header_generation(dst) != trans->transid);
2039
2040         src_nritems = btrfs_header_nritems(src);
2041         dst_nritems = btrfs_header_nritems(dst);
2042         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
2043         if (push_items <= 0)
2044                 return 1;
2045
2046         if (src_nritems < 4)
2047                 return 1;
2048
2049         max_push = src_nritems / 2 + 1;
2050         /* don't try to empty the node */
2051         if (max_push >= src_nritems)
2052                 return 1;
2053
2054         if (max_push < push_items)
2055                 push_items = max_push;
2056
2057         memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
2058                                       btrfs_node_key_ptr_offset(0),
2059                                       (dst_nritems) *
2060                                       sizeof(struct btrfs_key_ptr));
2061
2062         copy_extent_buffer(dst, src,
2063                            btrfs_node_key_ptr_offset(0),
2064                            btrfs_node_key_ptr_offset(src_nritems - push_items),
2065                            push_items * sizeof(struct btrfs_key_ptr));
2066
2067         btrfs_set_header_nritems(src, src_nritems - push_items);
2068         btrfs_set_header_nritems(dst, dst_nritems + push_items);
2069
2070         btrfs_mark_buffer_dirty(src);
2071         btrfs_mark_buffer_dirty(dst);
2072
2073         ret = btrfs_update_ref(trans, root, src, dst, 0, push_items);
2074         BUG_ON(ret);
2075
2076         return ret;
2077 }
2078
2079 /*
2080  * helper function to insert a new root level in the tree.
2081  * A new node is allocated, and a single item is inserted to
2082  * point to the existing root
2083  *
2084  * returns zero on success or < 0 on failure.
2085  */
2086 static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2087                            struct btrfs_root *root,
2088                            struct btrfs_path *path, int level)
2089 {
2090         u64 lower_gen;
2091         struct extent_buffer *lower;
2092         struct extent_buffer *c;
2093         struct extent_buffer *old;
2094         struct btrfs_disk_key lower_key;
2095         int ret;
2096
2097         BUG_ON(path->nodes[level]);
2098         BUG_ON(path->nodes[level-1] != root->node);
2099
2100         lower = path->nodes[level-1];
2101         if (level == 1)
2102                 btrfs_item_key(lower, &lower_key, 0);
2103         else
2104                 btrfs_node_key(lower, &lower_key, 0);
2105
2106         c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
2107                                    root->root_key.objectid, trans->transid,
2108                                    level, root->node->start, 0);
2109         if (IS_ERR(c))
2110                 return PTR_ERR(c);
2111
2112         memset_extent_buffer(c, 0, 0, root->nodesize);
2113         btrfs_set_header_nritems(c, 1);
2114         btrfs_set_header_level(c, level);
2115         btrfs_set_header_bytenr(c, c->start);
2116         btrfs_set_header_generation(c, trans->transid);
2117         btrfs_set_header_owner(c, root->root_key.objectid);
2118
2119         write_extent_buffer(c, root->fs_info->fsid,
2120                             (unsigned long)btrfs_header_fsid(c),
2121                             BTRFS_FSID_SIZE);
2122
2123         write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
2124                             (unsigned long)btrfs_header_chunk_tree_uuid(c),
2125                             BTRFS_UUID_SIZE);
2126
2127         btrfs_set_node_key(c, &lower_key, 0);
2128         btrfs_set_node_blockptr(c, 0, lower->start);
2129         lower_gen = btrfs_header_generation(lower);
2130         WARN_ON(lower_gen != trans->transid);
2131
2132         btrfs_set_node_ptr_generation(c, 0, lower_gen);
2133
2134         btrfs_mark_buffer_dirty(c);
2135
2136         spin_lock(&root->node_lock);
2137         old = root->node;
2138         root->node = c;
2139         spin_unlock(&root->node_lock);
2140
2141         ret = btrfs_update_extent_ref(trans, root, lower->start,
2142                                       lower->start, c->start,
2143                                       root->root_key.objectid,
2144                                       trans->transid, level - 1);
2145         BUG_ON(ret);
2146
2147         /* the super has an extra ref to root->node */
2148         free_extent_buffer(old);
2149
2150         add_root_to_dirty_list(root);
2151         extent_buffer_get(c);
2152         path->nodes[level] = c;
2153         path->locks[level] = 1;
2154         path->slots[level] = 0;
2155         return 0;
2156 }
2157
2158 /*
2159  * worker function to insert a single pointer in a node.
2160  * the node should have enough room for the pointer already
2161  *
2162  * slot and level indicate where you want the key to go, and
2163  * blocknr is the block the key points to.
2164  *
2165  * returns zero on success and < 0 on any error
2166  */
2167 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2168                       *root, struct btrfs_path *path, struct btrfs_disk_key
2169                       *key, u64 bytenr, int slot, int level)
2170 {
2171         struct extent_buffer *lower;
2172         int nritems;
2173
2174         BUG_ON(!path->nodes[level]);
2175         lower = path->nodes[level];
2176         nritems = btrfs_header_nritems(lower);
2177         if (slot > nritems)
2178                 BUG();
2179         if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
2180                 BUG();
2181         if (slot != nritems) {
2182                 memmove_extent_buffer(lower,
2183                               btrfs_node_key_ptr_offset(slot + 1),
2184                               btrfs_node_key_ptr_offset(slot),
2185                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
2186         }
2187         btrfs_set_node_key(lower, key, slot);
2188         btrfs_set_node_blockptr(lower, slot, bytenr);
2189         WARN_ON(trans->transid == 0);
2190         btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2191         btrfs_set_header_nritems(lower, nritems + 1);
2192         btrfs_mark_buffer_dirty(lower);
2193         return 0;
2194 }
2195
2196 /*
2197  * split the node at the specified level in path in two.
2198  * The path is corrected to point to the appropriate node after the split
2199  *
2200  * Before splitting this tries to make some room in the node by pushing
2201  * left and right, if either one works, it returns right away.
2202  *
2203  * returns 0 on success and < 0 on failure
2204  */
2205 static noinline int split_node(struct btrfs_trans_handle *trans,
2206                                struct btrfs_root *root,
2207                                struct btrfs_path *path, int level)
2208 {
2209         struct extent_buffer *c;
2210         struct extent_buffer *split;
2211         struct btrfs_disk_key disk_key;
2212         int mid;
2213         int ret;
2214         int wret;
2215         u32 c_nritems;
2216
2217         c = path->nodes[level];
2218         WARN_ON(btrfs_header_generation(c) != trans->transid);
2219         if (c == root->node) {
2220                 /* trying to split the root, lets make a new one */
2221                 ret = insert_new_root(trans, root, path, level + 1);
2222                 if (ret)
2223                         return ret;
2224         } else {
2225                 ret = push_nodes_for_insert(trans, root, path, level);
2226                 c = path->nodes[level];
2227                 if (!ret && btrfs_header_nritems(c) <
2228                     BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
2229                         return 0;
2230                 if (ret < 0)
2231                         return ret;
2232         }
2233
2234         c_nritems = btrfs_header_nritems(c);
2235
2236         split = btrfs_alloc_free_block(trans, root, root->nodesize,
2237                                         path->nodes[level + 1]->start,
2238                                         root->root_key.objectid,
2239                                         trans->transid, level, c->start, 0);
2240         if (IS_ERR(split))
2241                 return PTR_ERR(split);
2242
2243         btrfs_set_header_flags(split, btrfs_header_flags(c));
2244         btrfs_set_header_level(split, btrfs_header_level(c));
2245         btrfs_set_header_bytenr(split, split->start);
2246         btrfs_set_header_generation(split, trans->transid);
2247         btrfs_set_header_owner(split, root->root_key.objectid);
2248         btrfs_set_header_flags(split, 0);
2249         write_extent_buffer(split, root->fs_info->fsid,
2250                             (unsigned long)btrfs_header_fsid(split),
2251                             BTRFS_FSID_SIZE);
2252         write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
2253                             (unsigned long)btrfs_header_chunk_tree_uuid(split),
2254                             BTRFS_UUID_SIZE);
2255
2256         mid = (c_nritems + 1) / 2;
2257
2258         copy_extent_buffer(split, c,
2259                            btrfs_node_key_ptr_offset(0),
2260                            btrfs_node_key_ptr_offset(mid),
2261                            (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2262         btrfs_set_header_nritems(split, c_nritems - mid);
2263         btrfs_set_header_nritems(c, mid);
2264         ret = 0;
2265
2266         btrfs_mark_buffer_dirty(c);
2267         btrfs_mark_buffer_dirty(split);
2268
2269         btrfs_node_key(split, &disk_key, 0);
2270         wret = insert_ptr(trans, root, path, &disk_key, split->start,
2271                           path->slots[level + 1] + 1,
2272                           level + 1);
2273         if (wret)
2274                 ret = wret;
2275
2276         ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid);
2277         BUG_ON(ret);
2278
2279         if (path->slots[level] >= mid) {
2280                 path->slots[level] -= mid;
2281                 btrfs_tree_unlock(c);
2282                 free_extent_buffer(c);
2283                 path->nodes[level] = split;
2284                 path->slots[level + 1] += 1;
2285         } else {
2286                 btrfs_tree_unlock(split);
2287                 free_extent_buffer(split);
2288         }
2289         return ret;
2290 }
2291
2292 /*
2293  * how many bytes are required to store the items in a leaf.  start
2294  * and nr indicate which items in the leaf to check.  This totals up the
2295  * space used both by the item structs and the item data
2296  */
2297 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
2298 {
2299         int data_len;
2300         int nritems = btrfs_header_nritems(l);
2301         int end = min(nritems, start + nr) - 1;
2302
2303         if (!nr)
2304                 return 0;
2305         data_len = btrfs_item_end_nr(l, start);
2306         data_len = data_len - btrfs_item_offset_nr(l, end);
2307         data_len += sizeof(struct btrfs_item) * nr;
2308         WARN_ON(data_len < 0);
2309         return data_len;
2310 }
2311
2312 /*
2313  * The space between the end of the leaf items and
2314  * the start of the leaf data.  IOW, how much room
2315  * the leaf has left for both items and data
2316  */
2317 noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2318                                    struct extent_buffer *leaf)
2319 {
2320         int nritems = btrfs_header_nritems(leaf);
2321         int ret;
2322         ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
2323         if (ret < 0) {
2324                 printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
2325                        "used %d nritems %d\n",
2326                        ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
2327                        leaf_space_used(leaf, 0, nritems), nritems);
2328         }
2329         return ret;
2330 }
2331
2332 /*
2333  * push some data in the path leaf to the right, trying to free up at
2334  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
2335  *
2336  * returns 1 if the push failed because the other node didn't have enough
2337  * room, 0 if everything worked out and < 0 if there were major errors.
2338  */
2339 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2340                            *root, struct btrfs_path *path, int data_size,
2341                            int empty)
2342 {
2343         struct extent_buffer *left = path->nodes[0];
2344         struct extent_buffer *right;
2345         struct extent_buffer *upper;
2346         struct btrfs_disk_key disk_key;
2347         int slot;
2348         u32 i;
2349         int free_space;
2350         int push_space = 0;
2351         int push_items = 0;
2352         struct btrfs_item *item;
2353         u32 left_nritems;
2354         u32 nr;
2355         u32 right_nritems;
2356         u32 data_end;
2357         u32 this_item_size;
2358         int ret;
2359
2360         slot = path->slots[1];
2361         if (!path->nodes[1])
2362                 return 1;
2363
2364         upper = path->nodes[1];
2365         if (slot >= btrfs_header_nritems(upper) - 1)
2366                 return 1;
2367
2368         btrfs_assert_tree_locked(path->nodes[1]);
2369
2370         right = read_node_slot(root, upper, slot + 1);
2371         btrfs_tree_lock(right);
2372         btrfs_set_lock_blocking(right);
2373
2374         free_space = btrfs_leaf_free_space(root, right);
2375         if (free_space < data_size)
2376                 goto out_unlock;
2377
2378         /* cow and double check */
2379         ret = btrfs_cow_block(trans, root, right, upper,
2380                               slot + 1, &right, 0);
2381         if (ret)
2382                 goto out_unlock;
2383
2384         free_space = btrfs_leaf_free_space(root, right);
2385         if (free_space < data_size)
2386                 goto out_unlock;
2387
2388         left_nritems = btrfs_header_nritems(left);
2389         if (left_nritems == 0)
2390                 goto out_unlock;
2391
2392         if (empty)
2393                 nr = 0;
2394         else
2395                 nr = 1;
2396
2397         if (path->slots[0] >= left_nritems)
2398                 push_space += data_size;
2399
2400         i = left_nritems - 1;
2401         while (i >= nr) {
2402                 item = btrfs_item_nr(left, i);
2403
2404                 if (!empty && push_items > 0) {
2405                         if (path->slots[0] > i)
2406                                 break;
2407                         if (path->slots[0] == i) {
2408                                 int space = btrfs_leaf_free_space(root, left);
2409                                 if (space + push_space * 2 > free_space)
2410                                         break;
2411                         }
2412                 }
2413
2414                 if (path->slots[0] == i)
2415                         push_space += data_size;
2416
2417                 if (!left->map_token) {
2418                         map_extent_buffer(left, (unsigned long)item,
2419                                         sizeof(struct btrfs_item),
2420                                         &left->map_token, &left->kaddr,
2421                                         &left->map_start, &left->map_len,
2422                                         KM_USER1);
2423                 }
2424
2425                 this_item_size = btrfs_item_size(left, item);
2426                 if (this_item_size + sizeof(*item) + push_space > free_space)
2427                         break;
2428
2429                 push_items++;
2430                 push_space += this_item_size + sizeof(*item);
2431                 if (i == 0)
2432                         break;
2433                 i--;
2434         }
2435         if (left->map_token) {
2436                 unmap_extent_buffer(left, left->map_token, KM_USER1);
2437                 left->map_token = NULL;
2438         }
2439
2440         if (push_items == 0)
2441                 goto out_unlock;
2442
2443         if (!empty && push_items == left_nritems)
2444                 WARN_ON(1);
2445
2446         /* push left to right */
2447         right_nritems = btrfs_header_nritems(right);
2448
2449         push_space = btrfs_item_end_nr(left, left_nritems - push_items);
2450         push_space -= leaf_data_end(root, left);
2451
2452         /* make room in the right data area */
2453         data_end = leaf_data_end(root, right);
2454         memmove_extent_buffer(right,
2455                               btrfs_leaf_data(right) + data_end - push_space,
2456                               btrfs_leaf_data(right) + data_end,
2457                               BTRFS_LEAF_DATA_SIZE(root) - data_end);
2458
2459         /* copy from the left data area */
2460         copy_extent_buffer(right, left, btrfs_leaf_data(right) +
2461                      BTRFS_LEAF_DATA_SIZE(root) - push_space,
2462                      btrfs_leaf_data(left) + leaf_data_end(root, left),
2463                      push_space);
2464
2465         memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
2466                               btrfs_item_nr_offset(0),
2467                               right_nritems * sizeof(struct btrfs_item));
2468
2469         /* copy the items from left to right */
2470         copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
2471                    btrfs_item_nr_offset(left_nritems - push_items),
2472                    push_items * sizeof(struct btrfs_item));
2473
2474         /* update the item pointers */
2475         right_nritems += push_items;
2476         btrfs_set_header_nritems(right, right_nritems);
2477         push_space = BTRFS_LEAF_DATA_SIZE(root);
2478         for (i = 0; i < right_nritems; i++) {
2479                 item = btrfs_item_nr(right, i);
2480                 if (!right->map_token) {
2481                         map_extent_buffer(right, (unsigned long)item,
2482                                         sizeof(struct btrfs_item),
2483                                         &right->map_token, &right->kaddr,
2484                                         &right->map_start, &right->map_len,
2485                                         KM_USER1);
2486                 }
2487                 push_space -= btrfs_item_size(right, item);
2488                 btrfs_set_item_offset(right, item, push_space);
2489         }
2490
2491         if (right->map_token) {
2492                 unmap_extent_buffer(right, right->map_token, KM_USER1);
2493                 right->map_token = NULL;
2494         }
2495         left_nritems -= push_items;
2496         btrfs_set_header_nritems(left, left_nritems);
2497
2498         if (left_nritems)
2499                 btrfs_mark_buffer_dirty(left);
2500         btrfs_mark_buffer_dirty(right);
2501
2502         ret = btrfs_update_ref(trans, root, left, right, 0, push_items);
2503         BUG_ON(ret);
2504
2505         btrfs_item_key(right, &disk_key, 0);
2506         btrfs_set_node_key(upper, &disk_key, slot + 1);
2507         btrfs_mark_buffer_dirty(upper);
2508
2509         /* then fixup the leaf pointer in the path */
2510         if (path->slots[0] >= left_nritems) {
2511                 path->slots[0] -= left_nritems;
2512                 if (btrfs_header_nritems(path->nodes[0]) == 0)
2513                         clean_tree_block(trans, root, path->nodes[0]);
2514                 btrfs_tree_unlock(path->nodes[0]);
2515                 free_extent_buffer(path->nodes[0]);
2516                 path->nodes[0] = right;
2517                 path->slots[1] += 1;
2518         } else {
2519                 btrfs_tree_unlock(right);
2520                 free_extent_buffer(right);
2521         }
2522         return 0;
2523
2524 out_unlock:
2525         btrfs_tree_unlock(right);
2526         free_extent_buffer(right);
2527         return 1;
2528 }
2529
2530 /*
2531  * push some data in the path leaf to the left, trying to free up at
2532  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
2533  */
2534 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2535                           *root, struct btrfs_path *path, int data_size,
2536                           int empty)
2537 {
2538         struct btrfs_disk_key disk_key;
2539         struct extent_buffer *right = path->nodes[0];
2540         struct extent_buffer *left;
2541         int slot;
2542         int i;
2543         int free_space;
2544         int push_space = 0;
2545         int push_items = 0;
2546         struct btrfs_item *item;
2547         u32 old_left_nritems;
2548         u32 right_nritems;
2549         u32 nr;
2550         int ret = 0;
2551         int wret;
2552         u32 this_item_size;
2553         u32 old_left_item_size;
2554
2555         slot = path->slots[1];
2556         if (slot == 0)
2557                 return 1;
2558         if (!path->nodes[1])
2559                 return 1;
2560
2561         right_nritems = btrfs_header_nritems(right);
2562         if (right_nritems == 0)
2563                 return 1;
2564
2565         btrfs_assert_tree_locked(path->nodes[1]);
2566
2567         left = read_node_slot(root, path->nodes[1], slot - 1);
2568         btrfs_tree_lock(left);
2569         btrfs_set_lock_blocking(left);
2570
2571         free_space = btrfs_leaf_free_space(root, left);
2572         if (free_space < data_size) {
2573                 ret = 1;
2574                 goto out;
2575         }
2576
2577         /* cow and double check */
2578         ret = btrfs_cow_block(trans, root, left,
2579                               path->nodes[1], slot - 1, &left, 0);
2580         if (ret) {
2581                 /* we hit -ENOSPC, but it isn't fatal here */
2582                 ret = 1;
2583                 goto out;
2584         }
2585
2586         free_space = btrfs_leaf_free_space(root, left);
2587         if (free_space < data_size) {
2588                 ret = 1;
2589                 goto out;
2590         }
2591
2592         if (empty)
2593                 nr = right_nritems;
2594         else
2595                 nr = right_nritems - 1;
2596
2597         for (i = 0; i < nr; i++) {
2598                 item = btrfs_item_nr(right, i);
2599                 if (!right->map_token) {
2600                         map_extent_buffer(right, (unsigned long)item,
2601                                         sizeof(struct btrfs_item),
2602                                         &right->map_token, &right->kaddr,
2603                                         &right->map_start, &right->map_len,
2604                                         KM_USER1);
2605                 }
2606
2607                 if (!empty && push_items > 0) {
2608                         if (path->slots[0] < i)
2609                                 break;
2610                         if (path->slots[0] == i) {
2611                                 int space = btrfs_leaf_free_space(root, right);
2612                                 if (space + push_space * 2 > free_space)
2613                                         break;
2614                         }
2615                 }
2616
2617                 if (path->slots[0] == i)
2618                         push_space += data_size;
2619
2620                 this_item_size = btrfs_item_size(right, item);
2621                 if (this_item_size + sizeof(*item) + push_space > free_space)
2622                         break;
2623
2624                 push_items++;
2625                 push_space += this_item_size + sizeof(*item);
2626         }
2627
2628         if (right->map_token) {
2629                 unmap_extent_buffer(right, right->map_token, KM_USER1);
2630                 right->map_token = NULL;
2631         }
2632
2633         if (push_items == 0) {
2634                 ret = 1;
2635                 goto out;
2636         }
2637         if (!empty && push_items == btrfs_header_nritems(right))
2638                 WARN_ON(1);
2639
2640         /* push data from right to left */
2641         copy_extent_buffer(left, right,
2642                            btrfs_item_nr_offset(btrfs_header_nritems(left)),
2643                            btrfs_item_nr_offset(0),
2644                            push_items * sizeof(struct btrfs_item));
2645
2646         push_space = BTRFS_LEAF_DATA_SIZE(root) -
2647                      btrfs_item_offset_nr(right, push_items - 1);
2648
2649         copy_extent_buffer(left, right, btrfs_leaf_data(left) +
2650                      leaf_data_end(root, left) - push_space,
2651                      btrfs_leaf_data(right) +
2652                      btrfs_item_offset_nr(right, push_items - 1),
2653                      push_space);
2654         old_left_nritems = btrfs_header_nritems(left);
2655         BUG_ON(old_left_nritems <= 0);
2656
2657         old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
2658         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
2659                 u32 ioff;
2660
2661                 item = btrfs_item_nr(left, i);
2662                 if (!left->map_token) {
2663                         map_extent_buffer(left, (unsigned long)item,
2664                                         sizeof(struct btrfs_item),
2665                                         &left->map_token, &left->kaddr,
2666                                         &left->map_start, &left->map_len,
2667                                         KM_USER1);
2668                 }
2669
2670                 ioff = btrfs_item_offset(left, item);
2671                 btrfs_set_item_offset(left, item,
2672                       ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
2673         }
2674         btrfs_set_header_nritems(left, old_left_nritems + push_items);
2675         if (left->map_token) {
2676                 unmap_extent_buffer(left, left->map_token, KM_USER1);
2677                 left->map_token = NULL;
2678         }
2679
2680         /* fixup right node */
2681         if (push_items > right_nritems) {
2682                 printk(KERN_CRIT "push items %d nr %u\n", push_items,
2683                        right_nritems);
2684                 WARN_ON(1);
2685         }
2686
2687         if (push_items < right_nritems) {
2688                 push_space = btrfs_item_offset_nr(right, push_items - 1) -
2689                                                   leaf_data_end(root, right);
2690                 memmove_extent_buffer(right, btrfs_leaf_data(right) +
2691                                       BTRFS_LEAF_DATA_SIZE(root) - push_space,
2692                                       btrfs_leaf_data(right) +
2693                                       leaf_data_end(root, right), push_space);
2694
2695                 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
2696                               btrfs_item_nr_offset(push_items),
2697                              (btrfs_header_nritems(right) - push_items) *
2698                              sizeof(struct btrfs_item));
2699         }
2700         right_nritems -= push_items;
2701         btrfs_set_header_nritems(right, right_nritems);
2702         push_space = BTRFS_LEAF_DATA_SIZE(root);
2703         for (i = 0; i < right_nritems; i++) {
2704                 item = btrfs_item_nr(right, i);
2705
2706                 if (!right->map_token) {
2707                         map_extent_buffer(right, (unsigned long)item,
2708                                         sizeof(struct btrfs_item),
2709                                         &right->map_token, &right->kaddr,
2710                                         &right->map_start, &right->map_len,
2711                                         KM_USER1);
2712                 }
2713
2714                 push_space = push_space - btrfs_item_size(right, item);
2715                 btrfs_set_item_offset(right, item, push_space);
2716         }
2717         if (right->map_token) {
2718                 unmap_extent_buffer(right, right->map_token, KM_USER1);
2719                 right->map_token = NULL;
2720         }
2721
2722         btrfs_mark_buffer_dirty(left);
2723         if (right_nritems)
2724                 btrfs_mark_buffer_dirty(right);
2725
2726         ret = btrfs_update_ref(trans, root, right, left,
2727                                old_left_nritems, push_items);
2728         BUG_ON(ret);
2729
2730         btrfs_item_key(right, &disk_key, 0);
2731         wret = fixup_low_keys(trans, root, path, &disk_key, 1);
2732         if (wret)
2733                 ret = wret;
2734
2735         /* then fixup the leaf pointer in the path */
2736         if (path->slots[0] < push_items) {
2737                 path->slots[0] += old_left_nritems;
2738                 if (btrfs_header_nritems(path->nodes[0]) == 0)
2739                         clean_tree_block(trans, root, path->nodes[0]);
2740                 btrfs_tree_unlock(path->nodes[0]);
2741                 free_extent_buffer(path->nodes[0]);
2742                 path->nodes[0] = left;
2743                 path->slots[1] -= 1;
2744         } else {
2745                 btrfs_tree_unlock(left);
2746                 free_extent_buffer(left);
2747                 path->slots[0] -= push_items;
2748         }
2749         BUG_ON(path->slots[0] < 0);
2750         return ret;
2751 out:
2752         btrfs_tree_unlock(left);
2753         free_extent_buffer(left);
2754         return ret;
2755 }
2756
2757 /*
2758  * split the path's leaf in two, making sure there is at least data_size
2759  * available for the resulting leaf level of the path.
2760  *
2761  * returns 0 if all went well and < 0 on failure.
2762  */
2763 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2764                                struct btrfs_root *root,
2765                                struct btrfs_key *ins_key,
2766                                struct btrfs_path *path, int data_size,
2767                                int extend)
2768 {
2769         struct extent_buffer *l;
2770         u32 nritems;
2771         int mid;
2772         int slot;
2773         struct extent_buffer *right;
2774         int data_copy_size;
2775         int rt_data_off;
2776         int i;
2777         int ret = 0;
2778         int wret;
2779         int double_split;
2780         int num_doubles = 0;
2781         struct btrfs_disk_key disk_key;
2782
2783         /* first try to make some room by pushing left and right */
2784         if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2785                 wret = push_leaf_right(trans, root, path, data_size, 0);
2786                 if (wret < 0)
2787                         return wret;
2788                 if (wret) {
2789                         wret = push_leaf_left(trans, root, path, data_size, 0);
2790                         if (wret < 0)
2791                                 return wret;
2792                 }
2793                 l = path->nodes[0];
2794
2795                 /* did the pushes work? */
2796                 if (btrfs_leaf_free_space(root, l) >= data_size)
2797                         return 0;
2798         }
2799
2800         if (!path->nodes[1]) {
2801                 ret = insert_new_root(trans, root, path, 1);
2802                 if (ret)
2803                         return ret;
2804         }
2805 again:
2806         double_split = 0;
2807         l = path->nodes[0];
2808         slot = path->slots[0];
2809         nritems = btrfs_header_nritems(l);
2810         mid = (nritems + 1) / 2;
2811
2812         right = btrfs_alloc_free_block(trans, root, root->leafsize,
2813                                         path->nodes[1]->start,
2814                                         root->root_key.objectid,
2815                                         trans->transid, 0, l->start, 0);
2816         if (IS_ERR(right)) {
2817                 BUG_ON(1);
2818                 return PTR_ERR(right);
2819         }
2820
2821         memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2822         btrfs_set_header_bytenr(right, right->start);
2823         btrfs_set_header_generation(right, trans->transid);
2824         btrfs_set_header_owner(right, root->root_key.objectid);
2825         btrfs_set_header_level(right, 0);
2826         write_extent_buffer(right, root->fs_info->fsid,
2827                             (unsigned long)btrfs_header_fsid(right),
2828                             BTRFS_FSID_SIZE);
2829
2830         write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2831                             (unsigned long)btrfs_header_chunk_tree_uuid(right),
2832                             BTRFS_UUID_SIZE);
2833         if (mid <= slot) {
2834                 if (nritems == 1 ||
2835                     leaf_space_used(l, mid, nritems - mid) + data_size >
2836                         BTRFS_LEAF_DATA_SIZE(root)) {
2837                         if (slot >= nritems) {
2838                                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2839                                 btrfs_set_header_nritems(right, 0);
2840                                 wret = insert_ptr(trans, root, path,
2841                                                   &disk_key, right->start,
2842                                                   path->slots[1] + 1, 1);
2843                                 if (wret)
2844                                         ret = wret;
2845
2846                                 btrfs_tree_unlock(path->nodes[0]);
2847                                 free_extent_buffer(path->nodes[0]);
2848                                 path->nodes[0] = right;
2849                                 path->slots[0] = 0;
2850                                 path->slots[1] += 1;
2851                                 btrfs_mark_buffer_dirty(right);
2852                                 return ret;
2853                         }
2854                         mid = slot;
2855                         if (mid != nritems &&
2856                             leaf_space_used(l, mid, nritems - mid) +
2857                             data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2858                                 double_split = 1;
2859                         }
2860                 }
2861         } else {
2862                 if (leaf_space_used(l, 0, mid) + data_size >
2863                         BTRFS_LEAF_DATA_SIZE(root)) {
2864                         if (!extend && data_size && slot == 0) {
2865                                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2866                                 btrfs_set_header_nritems(right, 0);
2867                                 wret = insert_ptr(trans, root, path,
2868                                                   &disk_key,
2869                                                   right->start,
2870                                                   path->slots[1], 1);
2871                                 if (wret)
2872                                         ret = wret;
2873                                 btrfs_tree_unlock(path->nodes[0]);
2874                                 free_extent_buffer(path->nodes[0]);
2875                                 path->nodes[0] = right;
2876                                 path->slots[0] = 0;
2877                                 if (path->slots[1] == 0) {
2878                                         wret = fixup_low_keys(trans, root,
2879                                                       path, &disk_key, 1);
2880                                         if (wret)
2881                                                 ret = wret;
2882                                 }
2883                                 btrfs_mark_buffer_dirty(right);
2884                                 return ret;
2885                         } else if ((extend || !data_size) && slot == 0) {
2886                                 mid = 1;
2887                         } else {
2888                                 mid = slot;
2889                                 if (mid != nritems &&
2890                                     leaf_space_used(l, mid, nritems - mid) +
2891                                     data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2892                                         double_split = 1;
2893                                 }
2894                         }
2895                 }
2896         }
2897         nritems = nritems - mid;
2898         btrfs_set_header_nritems(right, nritems);
2899         data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2900
2901         copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2902                            btrfs_item_nr_offset(mid),
2903                            nritems * sizeof(struct btrfs_item));
2904
2905         copy_extent_buffer(right, l,
2906                      btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2907                      data_copy_size, btrfs_leaf_data(l) +
2908                      leaf_data_end(root, l), data_copy_size);
2909
2910         rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2911                       btrfs_item_end_nr(l, mid);
2912
2913         for (i = 0; i < nritems; i++) {
2914                 struct btrfs_item *item = btrfs_item_nr(right, i);
2915                 u32 ioff;
2916
2917                 if (!right->map_token) {
2918                         map_extent_buffer(right, (unsigned long)item,
2919                                         sizeof(struct btrfs_item),
2920                                         &right->map_token, &right->kaddr,
2921                                         &right->map_start, &right->map_len,
2922                                         KM_USER1);
2923                 }
2924
2925                 ioff = btrfs_item_offset(right, item);
2926                 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2927         }
2928
2929         if (right->map_token) {
2930                 unmap_extent_buffer(right, right->map_token, KM_USER1);
2931                 right->map_token = NULL;
2932         }
2933
2934         btrfs_set_header_nritems(l, mid);
2935         ret = 0;
2936         btrfs_item_key(right, &disk_key, 0);
2937         wret = insert_ptr(trans, root, path, &disk_key, right->start,
2938                           path->slots[1] + 1, 1);
2939         if (wret)
2940                 ret = wret;
2941
2942         btrfs_mark_buffer_dirty(right);
2943         btrfs_mark_buffer_dirty(l);
2944         BUG_ON(path->slots[0] != slot);
2945
2946         ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
2947         BUG_ON(ret);
2948
2949         if (mid <= slot) {
2950                 btrfs_tree_unlock(path->nodes[0]);
2951                 free_extent_buffer(path->nodes[0]);
2952                 path->nodes[0] = right;
2953                 path->slots[0] -= mid;
2954                 path->slots[1] += 1;
2955         } else {
2956                 btrfs_tree_unlock(right);
2957                 free_extent_buffer(right);
2958         }
2959
2960         BUG_ON(path->slots[0] < 0);
2961
2962         if (double_split) {
2963                 BUG_ON(num_doubles != 0);
2964                 num_doubles++;
2965                 goto again;
2966         }
2967         return ret;
2968 }
2969
2970 /*
2971  * This function splits a single item into two items,
2972  * giving 'new_key' to the new item and splitting the
2973  * old one at split_offset (from the start of the item).
2974  *
2975  * The path may be released by this operation.  After
2976  * the split, the path is pointing to the old item.  The
2977  * new item is going to be in the same node as the old one.
2978  *
2979  * Note, the item being split must be smaller enough to live alone on
2980  * a tree block with room for one extra struct btrfs_item
2981  *
2982  * This allows us to split the item in place, keeping a lock on the
2983  * leaf the entire time.
2984  */
2985 int btrfs_split_item(struct btrfs_trans_handle *trans,
2986                      struct btrfs_root *root,
2987                      struct btrfs_path *path,
2988                      struct btrfs_key *new_key,
2989                      unsigned long split_offset)
2990 {
2991         u32 item_size;
2992         struct extent_buffer *leaf;
2993         struct btrfs_key orig_key;
2994         struct btrfs_item *item;
2995         struct btrfs_item *new_item;
2996         int ret = 0;
2997         int slot;
2998         u32 nritems;
2999         u32 orig_offset;
3000         struct btrfs_disk_key disk_key;
3001         char *buf;
3002
3003         leaf = path->nodes[0];
3004         btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
3005         if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
3006                 goto split;
3007
3008         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3009         btrfs_release_path(root, path);
3010
3011         path->search_for_split = 1;
3012         path->keep_locks = 1;
3013
3014         ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
3015         path->search_for_split = 0;
3016
3017         /* if our item isn't there or got smaller, return now */
3018         if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
3019                                                         path->slots[0])) {
3020                 path->keep_locks = 0;
3021                 return -EAGAIN;
3022         }
3023
3024         ret = split_leaf(trans, root, &orig_key, path,
3025                          sizeof(struct btrfs_item), 1);
3026         path->keep_locks = 0;
3027         BUG_ON(ret);
3028
3029         /*
3030          * make sure any changes to the path from split_leaf leave it
3031          * in a blocking state
3032          */
3033         btrfs_set_path_blocking(path);
3034
3035         leaf = path->nodes[0];
3036         BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3037
3038 split:
3039         item = btrfs_item_nr(leaf, path->slots[0]);
3040         orig_offset = btrfs_item_offset(leaf, item);
3041         item_size = btrfs_item_size(leaf, item);
3042
3043
3044         buf = kmalloc(item_size, GFP_NOFS);
3045         read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3046                             path->slots[0]), item_size);
3047         slot = path->slots[0] + 1;
3048         leaf = path->nodes[0];
3049
3050         nritems = btrfs_header_nritems(leaf);
3051
3052         if (slot != nritems) {
3053                 /* shift the items */
3054                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
3055                               btrfs_item_nr_offset(slot),
3056                               (nritems - slot) * sizeof(struct btrfs_item));
3057
3058         }
3059
3060         btrfs_cpu_key_to_disk(&disk_key, new_key);
3061         btrfs_set_item_key(leaf, &disk_key, slot);
3062
3063         new_item = btrfs_item_nr(leaf, slot);
3064
3065         btrfs_set_item_offset(leaf, new_item, orig_offset);
3066         btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3067
3068         btrfs_set_item_offset(leaf, item,
3069                               orig_offset + item_size - split_offset);
3070         btrfs_set_item_size(leaf, item, split_offset);
3071
3072         btrfs_set_header_nritems(leaf, nritems + 1);
3073
3074         /* write the data for the start of the original item */
3075         write_extent_buffer(leaf, buf,
3076                             btrfs_item_ptr_offset(leaf, path->slots[0]),
3077                             split_offset);
3078
3079         /* write the data for the new item */
3080         write_extent_buffer(leaf, buf + split_offset,
3081                             btrfs_item_ptr_offset(leaf, slot),
3082                             item_size - split_offset);
3083         btrfs_mark_buffer_dirty(leaf);
3084
3085         ret = 0;
3086         if (btrfs_leaf_free_space(root, leaf) < 0) {
3087                 btrfs_print_leaf(root, leaf);
3088                 BUG();
3089         }
3090         kfree(buf);
3091         return ret;
3092 }
3093
3094 /*
3095  * make the item pointed to by the path smaller.  new_size indicates
3096  * how small to make it, and from_end tells us if we just chop bytes
3097  * off the end of the item or if we shift the item to chop bytes off
3098  * the front.
3099  */
3100 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
3101                         struct btrfs_root *root,
3102                         struct btrfs_path *path,
3103                         u32 new_size, int from_end)
3104 {
3105         int ret = 0;
3106         int slot;
3107         int slot_orig;
3108         struct extent_buffer *leaf;
3109         struct btrfs_item *item;
3110         u32 nritems;
3111         unsigned int data_end;
3112         unsigned int old_data_start;
3113         unsigned int old_size;
3114         unsigned int size_diff;
3115         int i;
3116
3117         slot_orig = path->slots[0];
3118         leaf = path->nodes[0];
3119         slot = path->slots[0];
3120
3121         old_size = btrfs_item_size_nr(leaf, slot);
3122         if (old_size == new_size)
3123                 return 0;
3124
3125         nritems = btrfs_header_nritems(leaf);
3126         data_end = leaf_data_end(root, leaf);
3127
3128         old_data_start = btrfs_item_offset_nr(leaf, slot);
3129
3130         size_diff = old_size - new_size;
3131
3132         BUG_ON(slot < 0);
3133         BUG_ON(slot >= nritems);
3134
3135         /*
3136          * item0..itemN ... dataN.offset..dataN.size .. data0.size
3137          */
3138         /* first correct the data pointers */
3139         for (i = slot; i < nritems; i++) {
3140                 u32 ioff;
3141                 item = btrfs_item_nr(leaf, i);
3142
3143                 if (!leaf->map_token) {
3144                         map_extent_buffer(leaf, (unsigned long)item,
3145                                         sizeof(struct btrfs_item),
3146                                         &leaf->map_token, &leaf->kaddr,
3147                                         &leaf->map_start, &leaf->map_len,
3148                                         KM_USER1);
3149                 }
3150
3151                 ioff = btrfs_item_offset(leaf, item);
3152                 btrfs_set_item_offset(leaf, item, ioff + size_diff);
3153         }
3154
3155         if (leaf->map_token) {
3156                 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3157                 leaf->map_token = NULL;
3158         }
3159
3160         /* shift the data */
3161         if (from_end) {
3162                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3163                               data_end + size_diff, btrfs_leaf_data(leaf) +
3164                               data_end, old_data_start + new_size - data_end);
3165         } else {
3166                 struct btrfs_disk_key disk_key;
3167                 u64 offset;
3168
3169                 btrfs_item_key(leaf, &disk_key, slot);
3170
3171                 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3172                         unsigned long ptr;
3173                         struct btrfs_file_extent_item *fi;
3174
3175                         fi = btrfs_item_ptr(leaf, slot,
3176                                             struct btrfs_file_extent_item);
3177                         fi = (struct btrfs_file_extent_item *)(
3178                              (unsigned long)fi - size_diff);
3179
3180                         if (btrfs_file_extent_type(leaf, fi) ==
3181                             BTRFS_FILE_EXTENT_INLINE) {
3182                                 ptr = btrfs_item_ptr_offset(leaf, slot);
3183                                 memmove_extent_buffer(leaf, ptr,
3184                                       (unsigned long)fi,
3185                                       offsetof(struct btrfs_file_extent_item,
3186                                                  disk_bytenr));
3187                         }
3188                 }
3189
3190                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3191                               data_end + size_diff, btrfs_leaf_data(leaf) +
3192                               data_end, old_data_start - data_end);
3193
3194                 offset = btrfs_disk_key_offset(&disk_key);
3195                 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3196                 btrfs_set_item_key(leaf, &disk_key, slot);
3197                 if (slot == 0)
3198                         fixup_low_keys(trans, root, path, &disk_key, 1);
3199         }
3200
3201         item = btrfs_item_nr(leaf, slot);
3202         btrfs_set_item_size(leaf, item, new_size);
3203         btrfs_mark_buffer_dirty(leaf);
3204
3205         ret = 0;
3206         if (btrfs_leaf_free_space(root, leaf) < 0) {
3207                 btrfs_print_leaf(root, leaf);
3208                 BUG();
3209         }
3210         return ret;
3211 }
3212
3213 /*
3214  * make the item pointed to by the path bigger, data_size is the new size.
3215  */
3216 int btrfs_extend_item(struct btrfs_trans_handle *trans,
3217                       struct btrfs_root *root, struct btrfs_path *path,
3218                       u32 data_size)
3219 {
3220         int ret = 0;
3221         int slot;
3222         int slot_orig;
3223         struct extent_buffer *leaf;
3224         struct btrfs_item *item;
3225         u32 nritems;
3226         unsigned int data_end;
3227         unsigned int old_data;
3228         unsigned int old_size;
3229         int i;
3230
3231         slot_orig = path->slots[0];
3232         leaf = path->nodes[0];
3233
3234         nritems = btrfs_header_nritems(leaf);
3235         data_end = leaf_data_end(root, leaf);
3236
3237         if (btrfs_leaf_free_space(root, leaf) < data_size) {
3238                 btrfs_print_leaf(root, leaf);
3239                 BUG();
3240         }
3241         slot = path->slots[0];
3242         old_data = btrfs_item_end_nr(leaf, slot);
3243
3244         BUG_ON(slot < 0);
3245         if (slot >= nritems) {
3246                 btrfs_print_leaf(root, leaf);
3247                 printk(KERN_CRIT "slot %d too large, nritems %d\n",
3248                        slot, nritems);
3249                 BUG_ON(1);
3250         }
3251
3252         /*
3253          * item0..itemN ... dataN.offset..dataN.size .. data0.size
3254          */
3255         /* first correct the data pointers */
3256         for (i = slot; i < nritems; i++) {
3257                 u32 ioff;
3258                 item = btrfs_item_nr(leaf, i);
3259
3260                 if (!leaf->map_token) {
3261                         map_extent_buffer(leaf, (unsigned long)item,
3262                                         sizeof(struct btrfs_item),
3263                                         &leaf->map_token, &leaf->kaddr,
3264                                         &leaf->map_start, &leaf->map_len,
3265                                         KM_USER1);
3266                 }
3267                 ioff = btrfs_item_offset(leaf, item);
3268                 btrfs_set_item_offset(leaf, item, ioff - data_size);
3269         }
3270
3271         if (leaf->map_token) {
3272                 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3273                 leaf->map_token = NULL;
3274         }
3275
3276         /* shift the data */
3277         memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3278                       data_end - data_size, btrfs_leaf_data(leaf) +
3279                       data_end, old_data - data_end);
3280
3281         data_end = old_data;
3282         old_size = btrfs_item_size_nr(leaf, slot);
3283         item = btrfs_item_nr(leaf, slot);
3284         btrfs_set_item_size(leaf, item, old_size + data_size);
3285         btrfs_mark_buffer_dirty(leaf);
3286
3287         ret = 0;
3288         if (btrfs_leaf_free_space(root, leaf) < 0) {
3289                 btrfs_print_leaf(root, leaf);
3290                 BUG();
3291         }
3292         return ret;
3293 }
3294
3295 /*
3296  * Given a key and some data, insert items into the tree.
3297  * This does all the path init required, making room in the tree if needed.
3298  * Returns the number of keys that were inserted.
3299  */
3300 int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
3301                             struct btrfs_root *root,
3302                             struct btrfs_path *path,
3303                             struct btrfs_key *cpu_key, u32 *data_size,
3304                             int nr)
3305 {
3306         struct extent_buffer *leaf;
3307         struct btrfs_item *item;
3308         int ret = 0;
3309         int slot;
3310         int i;
3311         u32 nritems;
3312         u32 total_data = 0;
3313         u32 total_size = 0;
3314         unsigned int data_end;
3315         struct btrfs_disk_key disk_key;
3316         struct btrfs_key found_key;
3317
3318         for (i = 0; i < nr; i++) {
3319                 if (total_size + data_size[i] + sizeof(struct btrfs_item) >
3320                     BTRFS_LEAF_DATA_SIZE(root)) {
3321                         break;
3322                         nr = i;
3323                 }
3324                 total_data += data_size[i];
3325                 total_size += data_size[i] + sizeof(struct btrfs_item);
3326         }
3327         BUG_ON(nr == 0);
3328
3329         ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3330         if (ret == 0)
3331                 return -EEXIST;
3332         if (ret < 0)
3333                 goto out;
3334
3335         leaf = path->nodes[0];
3336
3337         nritems = btrfs_header_nritems(leaf);
3338         data_end = leaf_data_end(root, leaf);
3339
3340         if (btrfs_leaf_free_space(root, leaf) < total_size) {
3341                 for (i = nr; i >= 0; i--) {
3342                         total_data -= data_size[i];
3343                         total_size -= data_size[i] + sizeof(struct btrfs_item);
3344                         if (total_size < btrfs_leaf_free_space(root, leaf))
3345                                 break;
3346                 }
3347                 nr = i;
3348         }
3349
3350         slot = path->slots[0];
3351         BUG_ON(slot < 0);
3352
3353         if (slot != nritems) {
3354                 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3355
3356                 item = btrfs_item_nr(leaf, slot);
3357                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3358
3359                 /* figure out how many keys we can insert in here */
3360                 total_data = data_size[0];
3361                 for (i = 1; i < nr; i++) {
3362                         if (comp_cpu_keys(&found_key, cpu_key + i) <= 0)
3363                                 break;
3364                         total_data += data_size[i];
3365                 }
3366                 nr = i;
3367
3368                 if (old_data < data_end) {
3369                         btrfs_print_leaf(root, leaf);
3370                         printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3371                                slot, old_data, data_end);
3372                         BUG_ON(1);
3373                 }
3374                 /*
3375                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
3376                  */
3377                 /* first correct the data pointers */
3378                 WARN_ON(leaf->map_token);
3379                 for (i = slot; i < nritems; i++) {
3380                         u32 ioff;
3381
3382                         item = btrfs_item_nr(leaf, i);
3383                         if (!leaf->map_token) {
3384                                 map_extent_buffer(leaf, (unsigned long)item,
3385                                         sizeof(struct btrfs_item),
3386                                         &leaf->map_token, &leaf->kaddr,
3387                                         &leaf->map_start, &leaf->map_len,
3388                                         KM_USER1);
3389                         }
3390
3391                         ioff = btrfs_item_offset(leaf, item);
3392                         btrfs_set_item_offset(leaf, item, ioff - total_data);
3393                 }
3394                 if (leaf->map_token) {
3395                         unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3396                         leaf->map_token = NULL;
3397                 }
3398
3399                 /* shift the items */
3400                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3401                               btrfs_item_nr_offset(slot),
3402                               (nritems - slot) * sizeof(struct btrfs_item));
3403
3404                 /* shift the data */
3405                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3406                               data_end - total_data, btrfs_leaf_data(leaf) +
3407                               data_end, old_data - data_end);
3408                 data_end = old_data;
3409         } else {
3410                 /*
3411                  * this sucks but it has to be done, if we are inserting at
3412                  * the end of the leaf only insert 1 of the items, since we
3413                  * have no way of knowing whats on the next leaf and we'd have
3414                  * to drop our current locks to figure it out
3415                  */
3416                 nr = 1;
3417         }
3418
3419         /* setup the item for the new data */
3420         for (i = 0; i < nr; i++) {
3421                 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3422                 btrfs_set_item_key(leaf, &disk_key, slot + i);
3423                 item = btrfs_item_nr(leaf, slot + i);
3424                 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3425                 data_end -= data_size[i];
3426                 btrfs_set_item_size(leaf, item, data_size[i]);
3427         }
3428         btrfs_set_header_nritems(leaf, nritems + nr);
3429         btrfs_mark_buffer_dirty(leaf);
3430
3431         ret = 0;
3432         if (slot == 0) {
3433                 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3434                 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3435         }
3436
3437         if (btrfs_leaf_free_space(root, leaf) < 0) {
3438                 btrfs_print_leaf(root, leaf);
3439                 BUG();
3440         }
3441 out:
3442         if (!ret)
3443                 ret = nr;
3444         return ret;
3445 }
3446
3447 /*
3448  * Given a key and some data, insert items into the tree.
3449  * This does all the path init required, making room in the tree if needed.
3450  */
3451 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3452                             struct btrfs_root *root,
3453                             struct btrfs_path *path,
3454                             struct btrfs_key *cpu_key, u32 *data_size,
3455                             int nr)
3456 {
3457         struct extent_buffer *leaf;
3458         struct btrfs_item *item;
3459         int ret = 0;
3460         int slot;
3461         int slot_orig;
3462         int i;
3463         u32 nritems;
3464         u32 total_size = 0;
3465         u32 total_data = 0;
3466         unsigned int data_end;
3467         struct btrfs_disk_key disk_key;
3468
3469         for (i = 0; i < nr; i++)
3470                 total_data += data_size[i];
3471
3472         total_size = total_data + (nr * sizeof(struct btrfs_item));
3473         ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3474         if (ret == 0)
3475                 return -EEXIST;
3476         if (ret < 0)
3477                 goto out;
3478
3479         slot_orig = path->slots[0];
3480         leaf = path->nodes[0];
3481
3482         nritems = btrfs_header_nritems(leaf);
3483         data_end = leaf_data_end(root, leaf);
3484
3485         if (btrfs_leaf_free_space(root, leaf) < total_size) {
3486                 btrfs_print_leaf(root, leaf);
3487                 printk(KERN_CRIT "not enough freespace need %u have %d\n",
3488                        total_size, btrfs_leaf_free_space(root, leaf));
3489                 BUG();
3490         }
3491
3492         slot = path->slots[0];
3493         BUG_ON(slot < 0);
3494
3495         if (slot != nritems) {
3496                 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3497
3498                 if (old_data < data_end) {
3499                         btrfs_print_leaf(root, leaf);
3500                         printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3501                                slot, old_data, data_end);
3502                         BUG_ON(1);
3503                 }
3504                 /*
3505                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
3506                  */
3507                 /* first correct the data pointers */
3508                 WARN_ON(leaf->map_token);
3509                 for (i = slot; i < nritems; i++) {
3510                         u32 ioff;
3511
3512                         item = btrfs_item_nr(leaf, i);
3513                         if (!leaf->map_token) {
3514                                 map_extent_buffer(leaf, (unsigned long)item,
3515                                         sizeof(struct btrfs_item),
3516                                         &leaf->map_token, &leaf->kaddr,
3517                                         &leaf->map_start, &leaf->map_len,
3518                                         KM_USER1);
3519                         }
3520
3521                         ioff = btrfs_item_offset(leaf, item);
3522                         btrfs_set_item_offset(leaf, item, ioff - total_data);
3523                 }
3524                 if (leaf->map_token) {
3525                         unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3526                         leaf->map_token = NULL;
3527                 }
3528
3529                 /* shift the items */
3530                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3531                               btrfs_item_nr_offset(slot),
3532                               (nritems - slot) * sizeof(struct btrfs_item));
3533
3534                 /* shift the data */
3535                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3536                               data_end - total_data, btrfs_leaf_data(leaf) +
3537                               data_end, old_data - data_end);
3538                 data_end = old_data;
3539         }
3540
3541         /* setup the item for the new data */
3542         for (i = 0; i < nr; i++) {
3543                 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3544                 btrfs_set_item_key(leaf, &disk_key, slot + i);
3545                 item = btrfs_item_nr(leaf, slot + i);
3546                 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3547                 data_end -= data_size[i];
3548                 btrfs_set_item_size(leaf, item, data_size[i]);
3549         }
3550         btrfs_set_header_nritems(leaf, nritems + nr);
3551         btrfs_mark_buffer_dirty(leaf);
3552
3553         ret = 0;
3554         if (slot == 0) {
3555                 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3556                 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3557         }
3558
3559         if (btrfs_leaf_free_space(root, leaf) < 0) {
3560                 btrfs_print_leaf(root, leaf);
3561                 BUG();
3562         }
3563 out:
3564         btrfs_unlock_up_safe(path, 1);
3565         return ret;
3566 }
3567
3568 /*
3569  * Given a key and some data, insert an item into the tree.
3570  * This does all the path init required, making room in the tree if needed.
3571  */
3572 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
3573                       *root, struct btrfs_key *cpu_key, void *data, u32
3574                       data_size)
3575 {
3576         int ret = 0;
3577         struct btrfs_path *path;
3578         struct extent_buffer *leaf;
3579         unsigned long ptr;
3580
3581         path = btrfs_alloc_path();
3582         BUG_ON(!path);
3583         ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
3584         if (!ret) {
3585                 leaf = path->nodes[0];
3586                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
3587                 write_extent_buffer(leaf, data, ptr, data_size);
3588                 btrfs_mark_buffer_dirty(leaf);
3589         }
3590         btrfs_free_path(path);
3591         return ret;
3592 }
3593
3594 /*
3595  * delete the pointer from a given node.
3596  *
3597  * the tree should have been previously balanced so the deletion does not
3598  * empty a node.
3599  */
3600 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3601                    struct btrfs_path *path, int level, int slot)
3602 {
3603         struct extent_buffer *parent = path->nodes[level];
3604         u32 nritems;
3605         int ret = 0;
3606         int wret;
3607
3608         nritems = btrfs_header_nritems(parent);
3609         if (slot != nritems - 1) {
3610                 memmove_extent_buffer(parent,
3611                               btrfs_node_key_ptr_offset(slot),
3612                               btrfs_node_key_ptr_offset(slot + 1),
3613                               sizeof(struct btrfs_key_ptr) *
3614                               (nritems - slot - 1));
3615         }
3616         nritems--;
3617         btrfs_set_header_nritems(parent, nritems);
3618         if (nritems == 0 && parent == root->node) {
3619                 BUG_ON(btrfs_header_level(root->node) != 1);
3620                 /* just turn the root into a leaf and break */
3621                 btrfs_set_header_level(root->node, 0);
3622         } else if (slot == 0) {
3623                 struct btrfs_disk_key disk_key;
3624
3625                 btrfs_node_key(parent, &disk_key, 0);
3626                 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
3627                 if (wret)
3628                         ret = wret;
3629         }
3630         btrfs_mark_buffer_dirty(parent);
3631         return ret;
3632 }
3633
3634 /*
3635  * a helper function to delete the leaf pointed to by path->slots[1] and
3636  * path->nodes[1].  bytenr is the node block pointer, but since the callers
3637  * already know it, it is faster to have them pass it down than to
3638  * read it out of the node again.
3639  *
3640  * This deletes the pointer in path->nodes[1] and frees the leaf
3641  * block extent.  zero is returned if it all worked out, < 0 otherwise.
3642  *
3643  * The path must have already been setup for deleting the leaf, including
3644  * all the proper balancing.  path->nodes[1] must be locked.
3645  */
3646 noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
3647                             struct btrfs_root *root,
3648                             struct btrfs_path *path, u64 bytenr)
3649 {
3650         int ret;
3651         u64 root_gen = btrfs_header_generation(path->nodes[1]);
3652         u64 parent_start = path->nodes[1]->start;
3653         u64 parent_owner = btrfs_header_owner(path->nodes[1]);
3654
3655         ret = del_ptr(trans, root, path, 1, path->slots[1]);
3656         if (ret)
3657                 return ret;
3658
3659         /*
3660          * btrfs_free_extent is expensive, we want to make sure we
3661          * aren't holding any locks when we call it
3662          */
3663         btrfs_unlock_up_safe(path, 0);
3664
3665         ret = btrfs_free_extent(trans, root, bytenr,
3666                                 btrfs_level_size(root, 0),
3667                                 parent_start, parent_owner,
3668                                 root_gen, 0, 1);
3669         return ret;
3670 }
3671 /*
3672  * delete the item at the leaf level in path.  If that empties
3673  * the leaf, remove it from the tree
3674  */
3675 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3676                     struct btrfs_path *path, int slot, int nr)
3677 {
3678         struct extent_buffer *leaf;
3679         struct btrfs_item *item;
3680         int last_off;
3681         int dsize = 0;
3682         int ret = 0;
3683         int wret;
3684         int i;
3685         u32 nritems;
3686
3687         leaf = path->nodes[0];
3688         last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
3689
3690         for (i = 0; i < nr; i++)
3691                 dsize += btrfs_item_size_nr(leaf, slot + i);
3692
3693         nritems = btrfs_header_nritems(leaf);
3694
3695         if (slot + nr != nritems) {
3696                 int data_end = leaf_data_end(root, leaf);
3697
3698                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3699                               data_end + dsize,
3700                               btrfs_leaf_data(leaf) + data_end,
3701                               last_off - data_end);
3702
3703                 for (i = slot + nr; i < nritems; i++) {
3704                         u32 ioff;
3705
3706                         item = btrfs_item_nr(leaf, i);
3707                         if (!leaf->map_token) {
3708                                 map_extent_buffer(leaf, (unsigned long)item,
3709                                         sizeof(struct btrfs_item),
3710                                         &leaf->map_token, &leaf->kaddr,
3711                                         &leaf->map_start, &leaf->map_len,
3712                                         KM_USER1);
3713                         }
3714                         ioff = btrfs_item_offset(leaf, item);
3715                         btrfs_set_item_offset(leaf, item, ioff + dsize);
3716                 }
3717
3718                 if (leaf->map_token) {
3719                         unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3720                         leaf->map_token = NULL;
3721                 }
3722
3723                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
3724                               btrfs_item_nr_offset(slot + nr),
3725                               sizeof(struct btrfs_item) *
3726                               (nritems - slot - nr));
3727         }
3728         btrfs_set_header_nritems(leaf, nritems - nr);
3729         nritems -= nr;
3730
3731         /* delete the leaf if we've emptied it */
3732         if (nritems == 0) {
3733                 if (leaf == root->node) {
3734                         btrfs_set_header_level(leaf, 0);
3735                 } else {
3736                         ret = btrfs_del_leaf(trans, root, path, leaf->start);
3737                         BUG_ON(ret);
3738                 }
3739         } else {
3740                 int used = leaf_space_used(leaf, 0, nritems);
3741                 if (slot == 0) {
3742                         struct btrfs_disk_key disk_key;
3743
3744                         btrfs_item_key(leaf, &disk_key, 0);
3745                         wret = fixup_low_keys(trans, root, path,
3746                                               &disk_key, 1);
3747                         if (wret)
3748                                 ret = wret;
3749                 }
3750
3751                 /* delete the leaf if it is mostly empty */
3752                 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
3753                         /* push_leaf_left fixes the path.
3754                          * make sure the path still points to our leaf
3755                          * for possible call to del_ptr below
3756                          */
3757                         slot = path->slots[1];
3758                         extent_buffer_get(leaf);
3759
3760                         wret = push_leaf_left(trans, root, path, 1, 1);
3761                         if (wret < 0 && wret != -ENOSPC)
3762                                 ret = wret;
3763
3764                         if (path->nodes[0] == leaf &&
3765                             btrfs_header_nritems(leaf)) {
3766                                 wret = push_leaf_right(trans, root, path, 1, 1);
3767                                 if (wret < 0 && wret != -ENOSPC)
3768                                         ret = wret;
3769                         }
3770
3771                         if (btrfs_header_nritems(leaf) == 0) {
3772                                 path->slots[1] = slot;
3773                                 ret = btrfs_del_leaf(trans, root, path,
3774                                                      leaf->start);
3775                                 BUG_ON(ret);
3776                                 free_extent_buffer(leaf);
3777                         } else {
3778                                 /* if we're still in the path, make sure
3779                                  * we're dirty.  Otherwise, one of the
3780                                  * push_leaf functions must have already
3781                                  * dirtied this buffer
3782                                  */
3783                                 if (path->nodes[0] == leaf)
3784                                         btrfs_mark_buffer_dirty(leaf);
3785                                 free_extent_buffer(leaf);
3786                         }
3787                 } else {
3788                         btrfs_mark_buffer_dirty(leaf);
3789                 }
3790         }
3791         return ret;
3792 }
3793
3794 /*
3795  * search the tree again to find a leaf with lesser keys
3796  * returns 0 if it found something or 1 if there are no lesser leaves.
3797  * returns < 0 on io errors.
3798  *
3799  * This may release the path, and so you may lose any locks held at the
3800  * time you call it.
3801  */
3802 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
3803 {
3804         struct btrfs_key key;
3805         struct btrfs_disk_key found_key;
3806         int ret;
3807
3808         btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
3809
3810         if (key.offset > 0)
3811                 key.offset--;
3812         else if (key.type > 0)
3813                 key.type--;
3814         else if (key.objectid > 0)
3815                 key.objectid--;
3816         else
3817                 return 1;
3818
3819         btrfs_release_path(root, path);
3820         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3821         if (ret < 0)
3822                 return ret;
3823         btrfs_item_key(path->nodes[0], &found_key, 0);
3824         ret = comp_keys(&found_key, &key);
3825         if (ret < 0)
3826                 return 0;
3827         return 1;
3828 }
3829
3830 /*
3831  * A helper function to walk down the tree starting at min_key, and looking
3832  * for nodes or leaves that are either in cache or have a minimum
3833  * transaction id.  This is used by the btree defrag code, and tree logging
3834  *
3835  * This does not cow, but it does stuff the starting key it finds back
3836  * into min_key, so you can call btrfs_search_slot with cow=1 on the
3837  * key and get a writable path.
3838  *
3839  * This does lock as it descends, and path->keep_locks should be set
3840  * to 1 by the caller.
3841  *
3842  * This honors path->lowest_level to prevent descent past a given level
3843  * of the tree.
3844  *
3845  * min_trans indicates the oldest transaction that you are interested
3846  * in walking through.  Any nodes or leaves older than min_trans are
3847  * skipped over (without reading them).
3848  *
3849  * returns zero if something useful was found, < 0 on error and 1 if there
3850  * was nothing in the tree that matched the search criteria.
3851  */
3852 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
3853                          struct btrfs_key *max_key,
3854                          struct btrfs_path *path, int cache_only,
3855                          u64 min_trans)
3856 {
3857         struct extent_buffer *cur;
3858         struct btrfs_key found_key;
3859         int slot;
3860         int sret;
3861         u32 nritems;
3862         int level;
3863         int ret = 1;
3864
3865         WARN_ON(!path->keep_locks);
3866 again:
3867         cur = btrfs_lock_root_node(root);
3868         level = btrfs_header_level(cur);
3869         WARN_ON(path->nodes[level]);
3870         path->nodes[level] = cur;
3871         path->locks[level] = 1;
3872
3873         if (btrfs_header_generation(cur) < min_trans) {
3874                 ret = 1;
3875                 goto out;
3876         }
3877         while (1) {
3878                 nritems = btrfs_header_nritems(cur);
3879                 level = btrfs_header_level(cur);
3880                 sret = bin_search(cur, min_key, level, &slot);
3881
3882                 /* at the lowest level, we're done, setup the path and exit */
3883                 if (level == path->lowest_level) {
3884                         if (slot >= nritems)
3885                                 goto find_next_key;
3886                         ret = 0;
3887                         path->slots[level] = slot;
3888                         btrfs_item_key_to_cpu(cur, &found_key, slot);
3889                         goto out;
3890                 }
3891                 if (sret && slot > 0)
3892                         slot--;
3893                 /*
3894                  * check this node pointer against the cache_only and
3895                  * min_trans parameters.  If it isn't in cache or is too
3896                  * old, skip to the next one.
3897                  */
3898                 while (slot < nritems) {
3899                         u64 blockptr;
3900                         u64 gen;
3901                         struct extent_buffer *tmp;
3902                         struct btrfs_disk_key disk_key;
3903
3904                         blockptr = btrfs_node_blockptr(cur, slot);
3905                         gen = btrfs_node_ptr_generation(cur, slot);
3906                         if (gen < min_trans) {
3907                                 slot++;
3908                                 continue;
3909                         }
3910                         if (!cache_only)
3911                                 break;
3912
3913                         if (max_key) {
3914                                 btrfs_node_key(cur, &disk_key, slot);
3915                                 if (comp_keys(&disk_key, max_key) >= 0) {
3916                                         ret = 1;
3917                                         goto out;
3918                                 }
3919                         }
3920
3921                         tmp = btrfs_find_tree_block(root, blockptr,
3922                                             btrfs_level_size(root, level - 1));
3923
3924                         if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
3925                                 free_extent_buffer(tmp);
3926                                 break;
3927                         }
3928                         if (tmp)
3929                                 free_extent_buffer(tmp);
3930                         slot++;
3931                 }
3932 find_next_key:
3933                 /*
3934                  * we didn't find a candidate key in this node, walk forward
3935                  * and find another one
3936                  */
3937                 if (slot >= nritems) {
3938                         path->slots[level] = slot;
3939                         btrfs_set_path_blocking(path);
3940                         sret = btrfs_find_next_key(root, path, min_key, level,
3941                                                   cache_only, min_trans);
3942                         if (sret == 0) {
3943                                 btrfs_release_path(root, path);
3944                                 goto again;
3945                         } else {
3946                                 goto out;
3947                         }
3948                 }
3949                 /* save our key for returning back */
3950                 btrfs_node_key_to_cpu(cur, &found_key, slot);
3951                 path->slots[level] = slot;
3952                 if (level == path->lowest_level) {
3953                         ret = 0;
3954                         unlock_up(path, level, 1);
3955                         goto out;
3956                 }
3957                 btrfs_set_path_blocking(path);
3958                 cur = read_node_slot(root, cur, slot);
3959
3960                 btrfs_tree_lock(cur);
3961
3962                 path->locks[level - 1] = 1;
3963                 path->nodes[level - 1] = cur;
3964                 unlock_up(path, level, 1);
3965                 btrfs_clear_path_blocking(path, NULL);
3966         }
3967 out:
3968         if (ret == 0)
3969                 memcpy(min_key, &found_key, sizeof(found_key));
3970         btrfs_set_path_blocking(path);
3971         return ret;
3972 }
3973
3974 /*
3975  * this is similar to btrfs_next_leaf, but does not try to preserve
3976  * and fixup the path.  It looks for and returns the next key in the
3977  * tree based on the current path and the cache_only and min_trans
3978  * parameters.
3979  *
3980  * 0 is returned if another key is found, < 0 if there are any errors
3981  * and 1 is returned if there are no higher keys in the tree
3982  *
3983  * path->keep_locks should be set to 1 on the search made before
3984  * calling this function.
3985  */
3986 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
3987                         struct btrfs_key *key, int lowest_level,
3988                         int cache_only, u64 min_trans)
3989 {
3990         int level = lowest_level;
3991         int slot;
3992         struct extent_buffer *c;
3993
3994         WARN_ON(!path->keep_locks);
3995         while (level < BTRFS_MAX_LEVEL) {
3996                 if (!path->nodes[level])
3997                         return 1;
3998
3999                 slot = path->slots[level] + 1;
4000                 c = path->nodes[level];
4001 next:
4002                 if (slot >= btrfs_header_nritems(c)) {
4003                         level++;
4004                         if (level == BTRFS_MAX_LEVEL)
4005                                 return 1;
4006                         continue;
4007                 }
4008                 if (level == 0)
4009                         btrfs_item_key_to_cpu(c, key, slot);
4010                 else {
4011                         u64 blockptr = btrfs_node_blockptr(c, slot);
4012                         u64 gen = btrfs_node_ptr_generation(c, slot);
4013
4014                         if (cache_only) {
4015                                 struct extent_buffer *cur;
4016                                 cur = btrfs_find_tree_block(root, blockptr,
4017                                             btrfs_level_size(root, level - 1));
4018                                 if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
4019                                         slot++;
4020                                         if (cur)
4021                                                 free_extent_buffer(cur);
4022                                         goto next;
4023                                 }
4024                                 free_extent_buffer(cur);
4025                         }
4026                         if (gen < min_trans) {
4027                                 slot++;
4028                                 goto next;
4029                         }
4030                         btrfs_node_key_to_cpu(c, key, slot);
4031                 }
4032                 return 0;
4033         }
4034         return 1;
4035 }
4036
4037 /*
4038  * search the tree again to find a leaf with greater keys
4039  * returns 0 if it found something or 1 if there are no greater leaves.
4040  * returns < 0 on io errors.
4041  */
4042 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4043 {
4044         int slot;
4045         int level = 1;
4046         struct extent_buffer *c;
4047         struct extent_buffer *next = NULL;
4048         struct btrfs_key key;
4049         u32 nritems;
4050         int ret;
4051
4052         nritems = btrfs_header_nritems(path->nodes[0]);
4053         if (nritems == 0)
4054                 return 1;
4055
4056         btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4057
4058         btrfs_release_path(root, path);
4059         path->keep_locks = 1;
4060         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4061         path->keep_locks = 0;
4062
4063         if (ret < 0)
4064                 return ret;
4065
4066         btrfs_set_path_blocking(path);
4067         nritems = btrfs_header_nritems(path->nodes[0]);
4068         /*
4069          * by releasing the path above we dropped all our locks.  A balance
4070          * could have added more items next to the key that used to be
4071          * at the very end of the block.  So, check again here and
4072          * advance the path if there are now more items available.
4073          */
4074         if (nritems > 0 && path->slots[0] < nritems - 1) {
4075                 path->slots[0]++;
4076                 goto done;
4077         }
4078
4079         while (level < BTRFS_MAX_LEVEL) {
4080                 if (!path->nodes[level])
4081                         return 1;
4082
4083                 slot = path->slots[level] + 1;
4084                 c = path->nodes[level];
4085                 if (slot >= btrfs_header_nritems(c)) {
4086                         level++;
4087                         if (level == BTRFS_MAX_LEVEL)
4088                                 return 1;
4089                         continue;
4090                 }
4091
4092                 if (next) {
4093                         btrfs_tree_unlock(next);
4094                         free_extent_buffer(next);
4095                 }
4096
4097                 /* the path was set to blocking above */
4098                 if (level == 1 && (path->locks[1] || path->skip_locking) &&
4099                     path->reada)
4100                         reada_for_search(root, path, level, slot, 0);
4101
4102                 next = read_node_slot(root, c, slot);
4103                 if (!path->skip_locking) {
4104                         btrfs_assert_tree_locked(c);
4105                         btrfs_tree_lock(next);
4106                         btrfs_set_lock_blocking(next);
4107                 }
4108                 break;
4109         }
4110         path->slots[level] = slot;
4111         while (1) {
4112                 level--;
4113                 c = path->nodes[level];
4114                 if (path->locks[level])
4115                         btrfs_tree_unlock(c);
4116                 free_extent_buffer(c);
4117                 path->nodes[level] = next;
4118                 path->slots[level] = 0;
4119                 if (!path->skip_locking)
4120                         path->locks[level] = 1;
4121                 if (!level)
4122                         break;
4123
4124                 btrfs_set_path_blocking(path);
4125                 if (level == 1 && path->locks[1] && path->reada)
4126                         reada_for_search(root, path, level, slot, 0);
4127                 next = read_node_slot(root, next, 0);
4128                 if (!path->skip_locking) {
4129                         btrfs_assert_tree_locked(path->nodes[level]);
4130                         btrfs_tree_lock(next);
4131                         btrfs_set_lock_blocking(next);
4132                 }
4133         }
4134 done:
4135         unlock_up(path, 0, 1);
4136         return 0;
4137 }
4138
4139 /*
4140  * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4141  * searching until it gets past min_objectid or finds an item of 'type'
4142  *
4143  * returns 0 if something is found, 1 if nothing was found and < 0 on error
4144  */
4145 int btrfs_previous_item(struct btrfs_root *root,
4146                         struct btrfs_path *path, u64 min_objectid,
4147                         int type)
4148 {
4149         struct btrfs_key found_key;
4150         struct extent_buffer *leaf;
4151         u32 nritems;
4152         int ret;
4153
4154         while (1) {
4155                 if (path->slots[0] == 0) {
4156                         btrfs_set_path_blocking(path);
4157                         ret = btrfs_prev_leaf(root, path);
4158                         if (ret != 0)
4159                                 return ret;
4160                 } else {
4161                         path->slots[0]--;
4162                 }
4163                 leaf = path->nodes[0];
4164                 nritems = btrfs_header_nritems(leaf);
4165                 if (nritems == 0)
4166                         return 1;
4167                 if (path->slots[0] == nritems)
4168                         path->slots[0]--;
4169
4170                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4171                 if (found_key.type == type)
4172                         return 0;
4173                 if (found_key.objectid < min_objectid)
4174                         break;
4175                 if (found_key.objectid == min_objectid &&
4176                     found_key.type < type)
4177                         break;
4178         }
4179         return 1;
4180 }