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