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