fs/btrfs/ctree.c

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