ctree.c

   1 /*
   2  * Copyright (C) 2007 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 #include "ctree.h"
  19 #include "disk-io.h"
  20 #include "transaction.h"
  21 #include "print-tree.h"
  22 #include "repair.h"
  23
  24 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  25                       *root, struct btrfs_path *path, int level);
  26 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
  27                       *root, struct btrfs_key *ins_key,
  28                       struct btrfs_path *path, int data_size, int extend);
  29 static int push_node_left(struct btrfs_trans_handle *trans,
  30                           struct btrfs_root *root, struct extent_buffer *dst,
  31                           struct extent_buffer *src, int empty);
  32 static int balance_node_right(struct btrfs_trans_handle *trans,
  33                               struct btrfs_root *root,
  34                               struct extent_buffer *dst_buf,
  35                               struct extent_buffer *src_buf);
  36
  37 inline void btrfs_init_path(struct btrfs_path *p)
  38 {
  39         memset(p, 0, sizeof(*p));
  40 }
  41
  42 struct btrfs_path *btrfs_alloc_path(void)
  43 {
  44         struct btrfs_path *path;
  45         path = kzalloc(sizeof(struct btrfs_path), GFP_NOFS);
  46         return path;
  47 }
  48
  49 void btrfs_free_path(struct btrfs_path *p)
  50 {
  51         if (!p)
  52                 return;
  53         btrfs_release_path(p);
  54         kfree(p);
  55 }
  56
  57 void btrfs_release_path(struct btrfs_path *p)
  58 {
  59         int i;
  60         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  61                 if (!p->nodes[i])
  62                         continue;
  63                 free_extent_buffer(p->nodes[i]);
  64         }
  65         memset(p, 0, sizeof(*p));
  66 }
  67
  68 void add_root_to_dirty_list(struct btrfs_root *root)
  69 {
  70         if (root->track_dirty && list_empty(&root->dirty_list)) {
  71                 list_add(&root->dirty_list,
  72                          &root->fs_info->dirty_cowonly_roots);
  73         }
  74 }
  75
  76 int btrfs_copy_root(struct btrfs_trans_handle *trans,
  77                       struct btrfs_root *root,
  78                       struct extent_buffer *buf,
  79                       struct extent_buffer **cow_ret, u64 new_root_objectid)
  80 {
  81         struct extent_buffer *cow;
  82         int ret = 0;
  83         int level;
  84         struct btrfs_root *new_root;
  85         struct btrfs_disk_key disk_key;
  86
  87         new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
  88         if (!new_root)
  89                 return -ENOMEM;
  90
  91         memcpy(new_root, root, sizeof(*new_root));
  92         new_root->root_key.objectid = new_root_objectid;
  93
  94         WARN_ON(root->ref_cows && trans->transid !=
  95                 root->fs_info->running_transaction->transid);
  96         WARN_ON(root->ref_cows && trans->transid != root->last_trans);
  97
  98         level = btrfs_header_level(buf);
  99         if (level == 0)
 100                 btrfs_item_key(buf, &disk_key, 0);
 101         else
 102                 btrfs_node_key(buf, &disk_key, 0);
 103         cow = btrfs_alloc_free_block(trans, new_root, buf->len,
 104                                      new_root_objectid, &disk_key,
 105                                      level, buf->start, 0);
 106         if (IS_ERR(cow)) {
 107                 kfree(new_root);
 108                 return PTR_ERR(cow);
 109         }
 110
 111         copy_extent_buffer(cow, buf, 0, 0, cow->len);
 112         btrfs_set_header_bytenr(cow, cow->start);
 113         btrfs_set_header_generation(cow, trans->transid);
 114         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
 115         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
 116                                      BTRFS_HEADER_FLAG_RELOC);
 117         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 118                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
 119         else
 120                 btrfs_set_header_owner(cow, new_root_objectid);
 121
 122         write_extent_buffer(cow, root->fs_info->fsid,
 123                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
 124
 125         WARN_ON(btrfs_header_generation(buf) > trans->transid);
 126         ret = btrfs_inc_ref(trans, new_root, cow, 0);
 127         kfree(new_root);
 128
 129         if (ret)
 130                 return ret;
 131
 132         btrfs_mark_buffer_dirty(cow);
 133         *cow_ret = cow;
 134         return 0;
 135 }
 136
 137 /*
 138  * check if the tree block can be shared by multiple trees
 139  */
 140 static int btrfs_block_can_be_shared(struct btrfs_root *root,
 141                                      struct extent_buffer *buf)
 142 {
 143         /*
 144          * Tree blocks not in refernece counted trees and tree roots
 145          * are never shared. If a block was allocated after the last
 146          * snapshot and the block was not allocated by tree relocation,
 147          * we know the block is not shared.
 148          */
 149         if (root->ref_cows &&
 150             buf != root->node && buf != root->commit_root &&
 151             (btrfs_header_generation(buf) <=
 152              btrfs_root_last_snapshot(&root->root_item) ||
 153              btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
 154                 return 1;
 155 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 156         if (root->ref_cows &&
 157             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
 158                 return 1;
 159 #endif
 160         return 0;
 161 }
 162
 163 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
 164                                        struct btrfs_root *root,
 165                                        struct extent_buffer *buf,
 166                                        struct extent_buffer *cow)
 167 {
 168         u64 refs;
 169         u64 owner;
 170         u64 flags;
 171         u64 new_flags = 0;
 172         int ret;
 173
 174         /*
 175          * Backrefs update rules:
 176          *
 177          * Always use full backrefs for extent pointers in tree block
 178          * allocated by tree relocation.
 179          *
 180          * If a shared tree block is no longer referenced by its owner
 181          * tree (btrfs_header_owner(buf) == root->root_key.objectid),
 182          * use full backrefs for extent pointers in tree block.
 183          *
 184          * If a tree block is been relocating
 185          * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
 186          * use full backrefs for extent pointers in tree block.
 187          * The reason for this is some operations (such as drop tree)
 188          * are only allowed for blocks use full backrefs.
 189          */
 190
 191         if (btrfs_block_can_be_shared(root, buf)) {
 192                 ret = btrfs_lookup_extent_info(trans, root, buf->start,
 193                                                btrfs_header_level(buf), 1,
 194                                                &refs, &flags);
 195                 BUG_ON(ret);
 196                 BUG_ON(refs == 0);
 197         } else {
 198                 refs = 1;
 199                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
 200                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
 201                         flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
 202                 else
 203                         flags = 0;
 204         }
 205
 206         owner = btrfs_header_owner(buf);
 207         BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
 208                owner == BTRFS_TREE_RELOC_OBJECTID);
 209
 210         if (refs > 1) {
 211                 if ((owner == root->root_key.objectid ||
 212                      root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
 213                     !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
 214                         ret = btrfs_inc_ref(trans, root, buf, 1);
 215                         BUG_ON(ret);
 216
 217                         if (root->root_key.objectid ==
 218                             BTRFS_TREE_RELOC_OBJECTID) {
 219                                 ret = btrfs_dec_ref(trans, root, buf, 0);
 220                                 BUG_ON(ret);
 221                                 ret = btrfs_inc_ref(trans, root, cow, 1);
 222                                 BUG_ON(ret);
 223                         }
 224                         new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
 225                 } else {
 226
 227                         if (root->root_key.objectid ==
 228                             BTRFS_TREE_RELOC_OBJECTID)
 229                                 ret = btrfs_inc_ref(trans, root, cow, 1);
 230                         else
 231                                 ret = btrfs_inc_ref(trans, root, cow, 0);
 232                         BUG_ON(ret);
 233                 }
 234                 if (new_flags != 0) {
 235                         ret = btrfs_set_block_flags(trans, root, buf->start,
 236                                                     btrfs_header_level(buf),
 237                                                     new_flags);
 238                         BUG_ON(ret);
 239                 }
 240         } else {
 241                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
 242                         if (root->root_key.objectid ==
 243                             BTRFS_TREE_RELOC_OBJECTID)
 244                                 ret = btrfs_inc_ref(trans, root, cow, 1);
 245                         else
 246                                 ret = btrfs_inc_ref(trans, root, cow, 0);
 247                         BUG_ON(ret);
 248                         ret = btrfs_dec_ref(trans, root, buf, 1);
 249                         BUG_ON(ret);
 250                 }
 251                 clean_tree_block(trans, root, buf);
 252         }
 253         return 0;
 254 }
 255
 256 int __btrfs_cow_block(struct btrfs_trans_handle *trans,
 257                              struct btrfs_root *root,
 258                              struct extent_buffer *buf,
 259                              struct extent_buffer *parent, int parent_slot,
 260                              struct extent_buffer **cow_ret,
 261                              u64 search_start, u64 empty_size)
 262 {
 263         struct extent_buffer *cow;
 264         struct btrfs_disk_key disk_key;
 265         int level;
 266
 267         WARN_ON(root->ref_cows && trans->transid !=
 268                 root->fs_info->running_transaction->transid);
 269         WARN_ON(root->ref_cows && trans->transid != root->last_trans);
 270
 271         level = btrfs_header_level(buf);
 272
 273         if (level == 0)
 274                 btrfs_item_key(buf, &disk_key, 0);
 275         else
 276                 btrfs_node_key(buf, &disk_key, 0);
 277
 278         cow = btrfs_alloc_free_block(trans, root, buf->len,
 279                                      root->root_key.objectid, &disk_key,
 280                                      level, search_start, empty_size);
 281         if (IS_ERR(cow))
 282                 return PTR_ERR(cow);
 283
 284         copy_extent_buffer(cow, buf, 0, 0, cow->len);
 285         btrfs_set_header_bytenr(cow, cow->start);
 286         btrfs_set_header_generation(cow, trans->transid);
 287         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
 288         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
 289                                      BTRFS_HEADER_FLAG_RELOC);
 290         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
 291                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
 292         else
 293                 btrfs_set_header_owner(cow, root->root_key.objectid);
 294
 295         write_extent_buffer(cow, root->fs_info->fsid,
 296                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
 297
 298         WARN_ON(!(buf->flags & EXTENT_BAD_TRANSID) &&
 299                 btrfs_header_generation(buf) > trans->transid);
 300
 301         update_ref_for_cow(trans, root, buf, cow);
 302
 303         if (buf == root->node) {
 304                 root->node = cow;
 305                 extent_buffer_get(cow);
 306
 307                 btrfs_free_extent(trans, root, buf->start, buf->len,
 308                                   0, root->root_key.objectid, level, 0);
 309                 free_extent_buffer(buf);
 310                 add_root_to_dirty_list(root);
 311         } else {
 312                 btrfs_set_node_blockptr(parent, parent_slot,
 313                                         cow->start);
 314                 WARN_ON(trans->transid == 0);
 315                 btrfs_set_node_ptr_generation(parent, parent_slot,
 316                                               trans->transid);
 317                 btrfs_mark_buffer_dirty(parent);
 318                 WARN_ON(btrfs_header_generation(parent) != trans->transid);
 319
 320                 btrfs_free_extent(trans, root, buf->start, buf->len,
 321                                   0, root->root_key.objectid, level, 1);
 322         }
 323         if (!list_empty(&buf->recow)) {
 324                 list_del_init(&buf->recow);
 325                 free_extent_buffer(buf);
 326         }
 327         free_extent_buffer(buf);
 328         btrfs_mark_buffer_dirty(cow);
 329         *cow_ret = cow;
 330         return 0;
 331 }
 332
 333 static inline int should_cow_block(struct btrfs_trans_handle *trans,
 334                                    struct btrfs_root *root,
 335                                    struct extent_buffer *buf)
 336 {
 337         if (btrfs_header_generation(buf) == trans->transid &&
 338             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
 339             !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
 340               btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
 341                 return 0;
 342         return 1;
 343 }
 344
 345 int btrfs_cow_block(struct btrfs_trans_handle *trans,
 346                     struct btrfs_root *root, struct extent_buffer *buf,
 347                     struct extent_buffer *parent, int parent_slot,
 348                     struct extent_buffer **cow_ret)
 349 {
 350         u64 search_start;
 351         int ret;
 352         /*
 353         if (trans->transaction != root->fs_info->running_transaction) {
 354                 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
 355                        root->fs_info->running_transaction->transid);
 356                 WARN_ON(1);
 357         }
 358         */
 359         if (trans->transid != root->fs_info->generation) {
 360                 printk(KERN_CRIT "trans %llu running %llu\n",
 361                         (unsigned long long)trans->transid,
 362                         (unsigned long long)root->fs_info->generation);
 363                 WARN_ON(1);
 364         }
 365         if (!should_cow_block(trans, root, buf)) {
 366                 *cow_ret = buf;
 367                 return 0;
 368         }
 369
 370         search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
 371         ret = __btrfs_cow_block(trans, root, buf, parent,
 372                                  parent_slot, cow_ret, search_start, 0);
 373         return ret;
 374 }
 375
 376 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
 377 {
 378         if (k1->objectid > k2->objectid)
 379                 return 1;
 380         if (k1->objectid < k2->objectid)
 381                 return -1;
 382         if (k1->type > k2->type)
 383                 return 1;
 384         if (k1->type < k2->type)
 385                 return -1;
 386         if (k1->offset > k2->offset)
 387                 return 1;
 388         if (k1->offset < k2->offset)
 389                 return -1;
 390         return 0;
 391 }
 392
 393 /*
 394  * compare two keys in a memcmp fashion
 395  */
 396 static int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
 397 {
 398         struct btrfs_key k1;
 399
 400         btrfs_disk_key_to_cpu(&k1, disk);
 401         return btrfs_comp_cpu_keys(&k1, k2);
 402 }
 403
 404 /*
 405  * The leaf data grows from end-to-front in the node.
 406  * this returns the address of the start of the last item,
 407  * which is the stop of the leaf data stack
 408  */
 409 static inline unsigned int leaf_data_end(struct btrfs_root *root,
 410                                          struct extent_buffer *leaf)
 411 {
 412         u32 nr = btrfs_header_nritems(leaf);
 413         if (nr == 0)
 414                 return BTRFS_LEAF_DATA_SIZE(root);
 415         return btrfs_item_offset_nr(leaf, nr - 1);
 416 }
 417
 418 enum btrfs_tree_block_status
 419 btrfs_check_node(struct btrfs_root *root, struct btrfs_disk_key *parent_key,
 420                  struct extent_buffer *buf)
 421 {
 422         int i;
 423         struct btrfs_key cpukey;
 424         struct btrfs_disk_key key;
 425         u32 nritems = btrfs_header_nritems(buf);
 426         enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS;
 427
 428         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
 429                 goto fail;
 430
 431         ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY;
 432         if (parent_key && parent_key->type) {
 433                 btrfs_node_key(buf, &key, 0);
 434                 if (memcmp(parent_key, &key, sizeof(key)))
 435                         goto fail;
 436         }
 437         ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
 438         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 439                 btrfs_node_key(buf, &key, i);
 440                 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
 441                 if (btrfs_comp_keys(&key, &cpukey) >= 0)
 442                         goto fail;
 443         }
 444         return BTRFS_TREE_BLOCK_CLEAN;
 445 fail:
 446         if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) {
 447                 if (parent_key)
 448                         btrfs_disk_key_to_cpu(&cpukey, parent_key);
 449                 else
 450                         btrfs_node_key_to_cpu(buf, &cpukey, 0);
 451                 btrfs_add_corrupt_extent_record(root->fs_info, &cpukey,
 452                                                 buf->start, buf->len,
 453                                                 btrfs_header_level(buf));
 454         }
 455         return ret;
 456 }
 457
 458 enum btrfs_tree_block_status
 459 btrfs_check_leaf(struct btrfs_root *root, struct btrfs_disk_key *parent_key,
 460                  struct extent_buffer *buf)
 461 {
 462         int i;
 463         struct btrfs_key cpukey;
 464         struct btrfs_disk_key key;
 465         u32 nritems = btrfs_header_nritems(buf);
 466         enum btrfs_tree_block_status ret = BTRFS_TREE_BLOCK_INVALID_NRITEMS;
 467
 468         if (nritems * sizeof(struct btrfs_item) > buf->len)  {
 469                 fprintf(stderr, "invalid number of items %llu\n",
 470                         (unsigned long long)buf->start);
 471                 goto fail;
 472         }
 473
 474         if (btrfs_header_level(buf) != 0) {
 475                 ret = BTRFS_TREE_BLOCK_INVALID_LEVEL;
 476                 fprintf(stderr, "leaf is not a leaf %llu\n",
 477                        (unsigned long long)btrfs_header_bytenr(buf));
 478                 goto fail;
 479         }
 480         if (btrfs_leaf_free_space(root, buf) < 0) {
 481                 ret = BTRFS_TREE_BLOCK_INVALID_FREE_SPACE;
 482                 fprintf(stderr, "leaf free space incorrect %llu %d\n",
 483                         (unsigned long long)btrfs_header_bytenr(buf),
 484                         btrfs_leaf_free_space(root, buf));
 485                 goto fail;
 486         }
 487
 488         if (nritems == 0)
 489                 return BTRFS_TREE_BLOCK_CLEAN;
 490
 491         btrfs_item_key(buf, &key, 0);
 492         if (parent_key && parent_key->type &&
 493             memcmp(parent_key, &key, sizeof(key))) {
 494                 ret = BTRFS_TREE_BLOCK_INVALID_PARENT_KEY;
 495                 fprintf(stderr, "leaf parent key incorrect %llu\n",
 496                        (unsigned long long)btrfs_header_bytenr(buf));
 497                 goto fail;
 498         }
 499         for (i = 0; nritems > 1 && i < nritems - 1; i++) {
 500                 btrfs_item_key(buf, &key, i);
 501                 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
 502                 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
 503                         ret = BTRFS_TREE_BLOCK_BAD_KEY_ORDER;
 504                         fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
 505                         goto fail;
 506                 }
 507                 if (btrfs_item_offset_nr(buf, i) !=
 508                         btrfs_item_end_nr(buf, i + 1)) {
 509                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 510                         fprintf(stderr, "incorrect offsets %u %u\n",
 511                                 btrfs_item_offset_nr(buf, i),
 512                                 btrfs_item_end_nr(buf, i + 1));
 513                         goto fail;
 514                 }
 515                 if (i == 0 && btrfs_item_end_nr(buf, i) !=
 516                     BTRFS_LEAF_DATA_SIZE(root)) {
 517                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 518                         fprintf(stderr, "bad item end %u wanted %u\n",
 519                                 btrfs_item_end_nr(buf, i),
 520                                 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
 521                         goto fail;
 522                 }
 523         }
 524
 525         for (i = 0; i < nritems; i++) {
 526                 if (btrfs_item_end_nr(buf, i) > BTRFS_LEAF_DATA_SIZE(root)) {
 527                         btrfs_item_key(buf, &key, 0);
 528                         btrfs_print_key(&key);
 529                         fflush(stdout);
 530                         ret = BTRFS_TREE_BLOCK_INVALID_OFFSETS;
 531                         fprintf(stderr, "slot end outside of leaf %llu > %llu\n",
 532                                 (unsigned long long)btrfs_item_end_nr(buf, i),
 533                                 (unsigned long long)BTRFS_LEAF_DATA_SIZE(root));
 534                         goto fail;
 535                 }
 536         }
 537
 538         return BTRFS_TREE_BLOCK_CLEAN;
 539 fail:
 540         if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) {
 541                 if (parent_key)
 542                         btrfs_disk_key_to_cpu(&cpukey, parent_key);
 543                 else
 544                         btrfs_item_key_to_cpu(buf, &cpukey, 0);
 545
 546                 btrfs_add_corrupt_extent_record(root->fs_info, &cpukey,
 547                                                 buf->start, buf->len, 0);
 548         }
 549         return ret;
 550 }
 551
 552 static int noinline check_block(struct btrfs_root *root,
 553                                 struct btrfs_path *path, int level)
 554 {
 555         struct btrfs_disk_key key;
 556         struct btrfs_disk_key *key_ptr = NULL;
 557         struct extent_buffer *parent;
 558         enum btrfs_tree_block_status ret;
 559
 560         if (path->skip_check_block)
 561                 return 0;
 562         if (path->nodes[level + 1]) {
 563                 parent = path->nodes[level + 1];
 564                 btrfs_node_key(parent, &key, path->slots[level + 1]);
 565                 key_ptr = &key;
 566         }
 567         if (level == 0)
 568                 ret =  btrfs_check_leaf(root, key_ptr, path->nodes[0]);
 569         else
 570                 ret = btrfs_check_node(root, key_ptr, path->nodes[level]);
 571         if (ret == BTRFS_TREE_BLOCK_CLEAN)
 572                 return 0;
 573         return -EIO;
 574 }
 575
 576 /*
 577  * search for key in the extent_buffer.  The items start at offset p,
 578  * and they are item_size apart.  There are 'max' items in p.
 579  *
 580  * the slot in the array is returned via slot, and it points to
 581  * the place where you would insert key if it is not found in
 582  * the array.
 583  *
 584  * slot may point to max if the key is bigger than all of the keys
 585  */
 586 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
 587                               int item_size, struct btrfs_key *key,
 588                               int max, int *slot)
 589 {
 590         int low = 0;
 591         int high = max;
 592         int mid;
 593         int ret;
 594         unsigned long offset;
 595         struct btrfs_disk_key *tmp;
 596
 597         while(low < high) {
 598                 mid = (low + high) / 2;
 599                 offset = p + mid * item_size;
 600
 601                 tmp = (struct btrfs_disk_key *)(eb->data + offset);
 602                 ret = btrfs_comp_keys(tmp, key);
 603
 604                 if (ret < 0)
 605                         low = mid + 1;
 606                 else if (ret > 0)
 607                         high = mid;
 608                 else {
 609                         *slot = mid;
 610                         return 0;
 611                 }
 612         }
 613         *slot = low;
 614         return 1;
 615 }
 616
 617 /*
 618  * simple bin_search frontend that does the right thing for
 619  * leaves vs nodes
 620  */
 621 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
 622                       int level, int *slot)
 623 {
 624         if (level == 0)
 625                 return generic_bin_search(eb,
 626                                           offsetof(struct btrfs_leaf, items),
 627                                           sizeof(struct btrfs_item),
 628                                           key, btrfs_header_nritems(eb),
 629                                           slot);
 630         else
 631                 return generic_bin_search(eb,
 632                                           offsetof(struct btrfs_node, ptrs),
 633                                           sizeof(struct btrfs_key_ptr),
 634                                           key, btrfs_header_nritems(eb),
 635                                           slot);
 636 }
 637
 638 struct extent_buffer *read_node_slot(struct btrfs_root *root,
 639                                    struct extent_buffer *parent, int slot)
 640 {
 641         int level = btrfs_header_level(parent);
 642         if (slot < 0)
 643                 return NULL;
 644         if (slot >= btrfs_header_nritems(parent))
 645                 return NULL;
 646
 647         if (level == 0)
 648                 return NULL;
 649
 650         return read_tree_block(root, btrfs_node_blockptr(parent, slot),
 651                        btrfs_level_size(root, level - 1),
 652                        btrfs_node_ptr_generation(parent, slot));
 653 }
 654
 655 static int balance_level(struct btrfs_trans_handle *trans,
 656                          struct btrfs_root *root,
 657                          struct btrfs_path *path, int level)
 658 {
 659         struct extent_buffer *right = NULL;
 660         struct extent_buffer *mid;
 661         struct extent_buffer *left = NULL;
 662         struct extent_buffer *parent = NULL;
 663         int ret = 0;
 664         int wret;
 665         int pslot;
 666         int orig_slot = path->slots[level];
 667         u64 orig_ptr;
 668
 669         if (level == 0)
 670                 return 0;
 671
 672         mid = path->nodes[level];
 673         WARN_ON(btrfs_header_generation(mid) != trans->transid);
 674
 675         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
 676
 677         if (level < BTRFS_MAX_LEVEL - 1) {
 678                 parent = path->nodes[level + 1];
 679                 pslot = path->slots[level + 1];
 680         }
 681
 682         /*
 683          * deal with the case where there is only one pointer in the root
 684          * by promoting the node below to a root
 685          */
 686         if (!parent) {
 687                 struct extent_buffer *child;
 688
 689                 if (btrfs_header_nritems(mid) != 1)
 690                         return 0;
 691
 692                 /* promote the child to a root */
 693                 child = read_node_slot(root, mid, 0);
 694                 BUG_ON(!extent_buffer_uptodate(child));
 695                 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
 696                 BUG_ON(ret);
 697
 698                 root->node = child;
 699                 add_root_to_dirty_list(root);
 700                 path->nodes[level] = NULL;
 701                 clean_tree_block(trans, root, mid);
 702                 wait_on_tree_block_writeback(root, mid);
 703                 /* once for the path */
 704                 free_extent_buffer(mid);
 705
 706                 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
 707                                         0, root->root_key.objectid,
 708                                         level, 1);
 709                 /* once for the root ptr */
 710                 free_extent_buffer(mid);
 711                 return ret;
 712         }
 713         if (btrfs_header_nritems(mid) >
 714             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
 715                 return 0;
 716
 717         left = read_node_slot(root, parent, pslot - 1);
 718         if (extent_buffer_uptodate(left)) {
 719                 wret = btrfs_cow_block(trans, root, left,
 720                                        parent, pslot - 1, &left);
 721                 if (wret) {
 722                         ret = wret;
 723                         goto enospc;
 724                 }
 725         }
 726         right = read_node_slot(root, parent, pslot + 1);
 727         if (extent_buffer_uptodate(right)) {
 728                 wret = btrfs_cow_block(trans, root, right,
 729                                        parent, pslot + 1, &right);
 730                 if (wret) {
 731                         ret = wret;
 732                         goto enospc;
 733                 }
 734         }
 735
 736         /* first, try to make some room in the middle buffer */
 737         if (left) {
 738                 orig_slot += btrfs_header_nritems(left);
 739                 wret = push_node_left(trans, root, left, mid, 1);
 740                 if (wret < 0)
 741                         ret = wret;
 742         }
 743
 744         /*
 745          * then try to empty the right most buffer into the middle
 746          */
 747         if (right) {
 748                 wret = push_node_left(trans, root, mid, right, 1);
 749                 if (wret < 0 && wret != -ENOSPC)
 750                         ret = wret;
 751                 if (btrfs_header_nritems(right) == 0) {
 752                         u64 bytenr = right->start;
 753                         u32 blocksize = right->len;
 754
 755                         clean_tree_block(trans, root, right);
 756                         wait_on_tree_block_writeback(root, right);
 757                         free_extent_buffer(right);
 758                         right = NULL;
 759                         wret = btrfs_del_ptr(trans, root, path,
 760                                              level + 1, pslot + 1);
 761                         if (wret)
 762                                 ret = wret;
 763                         wret = btrfs_free_extent(trans, root, bytenr,
 764                                                  blocksize, 0,
 765                                                  root->root_key.objectid,
 766                                                  level, 0);
 767                         if (wret)
 768                                 ret = wret;
 769                 } else {
 770                         struct btrfs_disk_key right_key;
 771                         btrfs_node_key(right, &right_key, 0);
 772                         btrfs_set_node_key(parent, &right_key, pslot + 1);
 773                         btrfs_mark_buffer_dirty(parent);
 774                 }
 775         }
 776         if (btrfs_header_nritems(mid) == 1) {
 777                 /*
 778                  * we're not allowed to leave a node with one item in the
 779                  * tree during a delete.  A deletion from lower in the tree
 780                  * could try to delete the only pointer in this node.
 781                  * So, pull some keys from the left.
 782                  * There has to be a left pointer at this point because
 783                  * otherwise we would have pulled some pointers from the
 784                  * right
 785                  */
 786                 BUG_ON(!left);
 787                 wret = balance_node_right(trans, root, mid, left);
 788                 if (wret < 0) {
 789                         ret = wret;
 790                         goto enospc;
 791                 }
 792                 if (wret == 1) {
 793                         wret = push_node_left(trans, root, left, mid, 1);
 794                         if (wret < 0)
 795                                 ret = wret;
 796                 }
 797                 BUG_ON(wret == 1);
 798         }
 799         if (btrfs_header_nritems(mid) == 0) {
 800                 /* we've managed to empty the middle node, drop it */
 801                 u64 bytenr = mid->start;
 802                 u32 blocksize = mid->len;
 803                 clean_tree_block(trans, root, mid);
 804                 wait_on_tree_block_writeback(root, mid);
 805                 free_extent_buffer(mid);
 806                 mid = NULL;
 807                 wret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
 808                 if (wret)
 809                         ret = wret;
 810                 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
 811                                          0, root->root_key.objectid,
 812                                          level, 0);
 813                 if (wret)
 814                         ret = wret;
 815         } else {
 816                 /* update the parent key to reflect our changes */
 817                 struct btrfs_disk_key mid_key;
 818                 btrfs_node_key(mid, &mid_key, 0);
 819                 btrfs_set_node_key(parent, &mid_key, pslot);
 820                 btrfs_mark_buffer_dirty(parent);
 821         }
 822
 823         /* update the path */
 824         if (left) {
 825                 if (btrfs_header_nritems(left) > orig_slot) {
 826                         extent_buffer_get(left);
 827                         path->nodes[level] = left;
 828                         path->slots[level + 1] -= 1;
 829                         path->slots[level] = orig_slot;
 830                         if (mid)
 831                                 free_extent_buffer(mid);
 832                 } else {
 833                         orig_slot -= btrfs_header_nritems(left);
 834                         path->slots[level] = orig_slot;
 835                 }
 836         }
 837         /* double check we haven't messed things up */
 838         check_block(root, path, level);
 839         if (orig_ptr !=
 840             btrfs_node_blockptr(path->nodes[level], path->slots[level]))
 841                 BUG();
 842 enospc:
 843         if (right)
 844                 free_extent_buffer(right);
 845         if (left)
 846                 free_extent_buffer(left);
 847         return ret;
 848 }
 849
 850 /* returns zero if the push worked, non-zero otherwise */
 851 static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
 852                                           struct btrfs_root *root,
 853                                           struct btrfs_path *path, int level)
 854 {
 855         struct extent_buffer *right = NULL;
 856         struct extent_buffer *mid;
 857         struct extent_buffer *left = NULL;
 858         struct extent_buffer *parent = NULL;
 859         int ret = 0;
 860         int wret;
 861         int pslot;
 862         int orig_slot = path->slots[level];
 863
 864         if (level == 0)
 865                 return 1;
 866
 867         mid = path->nodes[level];
 868         WARN_ON(btrfs_header_generation(mid) != trans->transid);
 869
 870         if (level < BTRFS_MAX_LEVEL - 1) {
 871                 parent = path->nodes[level + 1];
 872                 pslot = path->slots[level + 1];
 873         }
 874
 875         if (!parent)
 876                 return 1;
 877
 878         left = read_node_slot(root, parent, pslot - 1);
 879
 880         /* first, try to make some room in the middle buffer */
 881         if (extent_buffer_uptodate(left)) {
 882                 u32 left_nr;
 883                 left_nr = btrfs_header_nritems(left);
 884                 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
 885                         wret = 1;
 886                 } else {
 887                         ret = btrfs_cow_block(trans, root, left, parent,
 888                                               pslot - 1, &left);
 889                         if (ret)
 890                                 wret = 1;
 891                         else {
 892                                 wret = push_node_left(trans, root,
 893                                                       left, mid, 0);
 894                         }
 895                 }
 896                 if (wret < 0)
 897                         ret = wret;
 898                 if (wret == 0) {
 899                         struct btrfs_disk_key disk_key;
 900                         orig_slot += left_nr;
 901                         btrfs_node_key(mid, &disk_key, 0);
 902                         btrfs_set_node_key(parent, &disk_key, pslot);
 903                         btrfs_mark_buffer_dirty(parent);
 904                         if (btrfs_header_nritems(left) > orig_slot) {
 905                                 path->nodes[level] = left;
 906                                 path->slots[level + 1] -= 1;
 907                                 path->slots[level] = orig_slot;
 908                                 free_extent_buffer(mid);
 909                         } else {
 910                                 orig_slot -=
 911                                         btrfs_header_nritems(left);
 912                                 path->slots[level] = orig_slot;
 913                                 free_extent_buffer(left);
 914                         }
 915                         return 0;
 916                 }
 917                 free_extent_buffer(left);
 918         }
 919         right= read_node_slot(root, parent, pslot + 1);
 920
 921         /*
 922          * then try to empty the right most buffer into the middle
 923          */
 924         if (extent_buffer_uptodate(right)) {
 925                 u32 right_nr;
 926                 right_nr = btrfs_header_nritems(right);
 927                 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
 928                         wret = 1;
 929                 } else {
 930                         ret = btrfs_cow_block(trans, root, right,
 931                                               parent, pslot + 1,
 932                                               &right);
 933                         if (ret)
 934                                 wret = 1;
 935                         else {
 936                                 wret = balance_node_right(trans, root,
 937                                                           right, mid);
 938                         }
 939                 }
 940                 if (wret < 0)
 941                         ret = wret;
 942                 if (wret == 0) {
 943                         struct btrfs_disk_key disk_key;
 944
 945                         btrfs_node_key(right, &disk_key, 0);
 946                         btrfs_set_node_key(parent, &disk_key, pslot + 1);
 947                         btrfs_mark_buffer_dirty(parent);
 948
 949                         if (btrfs_header_nritems(mid) <= orig_slot) {
 950                                 path->nodes[level] = right;
 951                                 path->slots[level + 1] += 1;
 952                                 path->slots[level] = orig_slot -
 953                                         btrfs_header_nritems(mid);
 954                                 free_extent_buffer(mid);
 955                         } else {
 956                                 free_extent_buffer(right);
 957                         }
 958                         return 0;
 959                 }
 960                 free_extent_buffer(right);
 961         }
 962         return 1;
 963 }
 964
 965 /*
 966  * readahead one full node of leaves
 967  */
 968 void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
 969                              int level, int slot, u64 objectid)
 970 {
 971         struct extent_buffer *node;
 972         struct btrfs_disk_key disk_key;
 973         u32 nritems;
 974         u64 search;
 975         u64 lowest_read;
 976         u64 highest_read;
 977         u64 nread = 0;
 978         int direction = path->reada;
 979         struct extent_buffer *eb;
 980         u32 nr;
 981         u32 blocksize;
 982         u32 nscan = 0;
 983
 984         if (level != 1)
 985                 return;
 986
 987         if (!path->nodes[level])
 988                 return;
 989
 990         node = path->nodes[level];
 991         search = btrfs_node_blockptr(node, slot);
 992         blocksize = btrfs_level_size(root, level - 1);
 993         eb = btrfs_find_tree_block(root, search, blocksize);
 994         if (eb) {
 995                 free_extent_buffer(eb);
 996                 return;
 997         }
 998
 999         highest_read = search;
1000         lowest_read = search;
1001
1002         nritems = btrfs_header_nritems(node);
1003         nr = slot;
1004         while(1) {
1005                 if (direction < 0) {
1006                         if (nr == 0)
1007                                 break;
1008                         nr--;
1009                 } else if (direction > 0) {
1010                         nr++;
1011                         if (nr >= nritems)
1012                                 break;
1013                 }
1014                 if (path->reada < 0 && objectid) {
1015                         btrfs_node_key(node, &disk_key, nr);
1016                         if (btrfs_disk_key_objectid(&disk_key) != objectid)
1017                                 break;
1018                 }
1019                 search = btrfs_node_blockptr(node, nr);
1020                 if ((search >= lowest_read && search <= highest_read) ||
1021                     (search < lowest_read && lowest_read - search <= 32768) ||
1022                     (search > highest_read && search - highest_read <= 32768)) {
1023                         readahead_tree_block(root, search, blocksize,
1024                                      btrfs_node_ptr_generation(node, nr));
1025                         nread += blocksize;
1026                 }
1027                 nscan++;
1028                 if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
1029                         break;
1030                 if(nread > (1024 * 1024) || nscan > 128)
1031                         break;
1032
1033                 if (search < lowest_read)
1034                         lowest_read = search;
1035                 if (search > highest_read)
1036                         highest_read = search;
1037         }
1038 }
1039
1040 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *found_path,
1041                 u64 iobjectid, u64 ioff, u8 key_type,
1042                 struct btrfs_key *found_key)
1043 {
1044         int ret;
1045         struct btrfs_key key;
1046         struct extent_buffer *eb;
1047         struct btrfs_path *path;
1048
1049         key.type = key_type;
1050         key.objectid = iobjectid;
1051         key.offset = ioff;
1052
1053         if (found_path == NULL) {
1054                 path = btrfs_alloc_path();
1055                 if (!path)
1056                         return -ENOMEM;
1057         } else
1058                 path = found_path;
1059
1060         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
1061         if ((ret < 0) || (found_key == NULL)) {
1062                 if (path != found_path)
1063                         btrfs_free_path(path);
1064                 return ret;
1065         }
1066
1067         eb = path->nodes[0];
1068         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
1069                 ret = btrfs_next_leaf(fs_root, path);
1070                 if (ret)
1071                         return ret;
1072                 eb = path->nodes[0];
1073         }
1074
1075         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
1076         if (found_key->type != key.type ||
1077                         found_key->objectid != key.objectid)
1078                 return 1;
1079
1080         return 0;
1081 }
1082
1083 /*
1084  * look for key in the tree.  path is filled in with nodes along the way
1085  * if key is found, we return zero and you can find the item in the leaf
1086  * level of the path (level 0)
1087  *
1088  * If the key isn't found, the path points to the slot where it should
1089  * be inserted, and 1 is returned.  If there are other errors during the
1090  * search a negative error number is returned.
1091  *
1092  * if ins_len > 0, nodes and leaves will be split as we walk down the
1093  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
1094  * possible)
1095  */
1096 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1097                       *root, struct btrfs_key *key, struct btrfs_path *p, int
1098                       ins_len, int cow)
1099 {
1100         struct extent_buffer *b;
1101         int slot;
1102         int ret;
1103         int level;
1104         int should_reada = p->reada;
1105         u8 lowest_level = 0;
1106
1107         lowest_level = p->lowest_level;
1108         WARN_ON(lowest_level && ins_len > 0);
1109         WARN_ON(p->nodes[0] != NULL);
1110         /*
1111         WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1112         */
1113 again:
1114         b = root->node;
1115         extent_buffer_get(b);
1116         while (b) {
1117                 level = btrfs_header_level(b);
1118                 if (cow) {
1119                         int wret;
1120                         wret = btrfs_cow_block(trans, root, b,
1121                                                p->nodes[level + 1],
1122                                                p->slots[level + 1],
1123                                                &b);
1124                         if (wret) {
1125                                 free_extent_buffer(b);
1126                                 return wret;
1127                         }
1128                 }
1129                 BUG_ON(!cow && ins_len);
1130                 if (level != btrfs_header_level(b))
1131                         WARN_ON(1);
1132                 level = btrfs_header_level(b);
1133                 p->nodes[level] = b;
1134                 ret = check_block(root, p, level);
1135                 if (ret)
1136                         return -1;
1137                 ret = bin_search(b, key, level, &slot);
1138                 if (level != 0) {
1139                         if (ret && slot > 0)
1140                                 slot -= 1;
1141                         p->slots[level] = slot;
1142                         if ((p->search_for_split || ins_len > 0) &&
1143                             btrfs_header_nritems(b) >=
1144                             BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1145                                 int sret = split_node(trans, root, p, level);
1146                                 BUG_ON(sret > 0);
1147                                 if (sret)
1148                                         return sret;
1149                                 b = p->nodes[level];
1150                                 slot = p->slots[level];
1151                         } else if (ins_len < 0) {
1152                                 int sret = balance_level(trans, root, p,
1153                                                          level);
1154                                 if (sret)
1155                                         return sret;
1156                                 b = p->nodes[level];
1157                                 if (!b) {
1158                                         btrfs_release_path(p);
1159                                         goto again;
1160                                 }
1161                                 slot = p->slots[level];
1162                                 BUG_ON(btrfs_header_nritems(b) == 1);
1163                         }
1164                         /* this is only true while dropping a snapshot */
1165                         if (level == lowest_level)
1166                                 break;
1167
1168                         if (should_reada)
1169                                 reada_for_search(root, p, level, slot,
1170                                                  key->objectid);
1171
1172                         b = read_node_slot(root, b, slot);
1173                         if (!extent_buffer_uptodate(b))
1174                                 return -EIO;
1175                 } else {
1176                         p->slots[level] = slot;
1177                         if (ins_len > 0 &&
1178                             ins_len > btrfs_leaf_free_space(root, b)) {
1179                                 int sret = split_leaf(trans, root, key,
1180                                                       p, ins_len, ret == 0);
1181                                 BUG_ON(sret > 0);
1182                                 if (sret)
1183                                         return sret;
1184                         }
1185                         return ret;
1186                 }
1187         }
1188         return 1;
1189 }
1190
1191 /*
1192  * adjust the pointers going up the tree, starting at level
1193  * making sure the right key of each node is points to 'key'.
1194  * This is used after shifting pointers to the left, so it stops
1195  * fixing up pointers when a given leaf/node is not in slot 0 of the
1196  * higher levels
1197  */
1198 void btrfs_fixup_low_keys(struct btrfs_root *root, struct btrfs_path *path,
1199                           struct btrfs_disk_key *key, int level)
1200 {
1201         int i;
1202         struct extent_buffer *t;
1203
1204         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1205                 int tslot = path->slots[i];
1206                 if (!path->nodes[i])
1207                         break;
1208                 t = path->nodes[i];
1209                 btrfs_set_node_key(t, key, tslot);
1210                 btrfs_mark_buffer_dirty(path->nodes[i]);
1211                 if (tslot != 0)
1212                         break;
1213         }
1214 }
1215
1216 /*
1217  * update item key.
1218  *
1219  * This function isn't completely safe. It's the caller's responsibility
1220  * that the new key won't break the order
1221  */
1222 int btrfs_set_item_key_safe(struct btrfs_root *root, struct btrfs_path *path,
1223                             struct btrfs_key *new_key)
1224 {
1225         struct btrfs_disk_key disk_key;
1226         struct extent_buffer *eb;
1227         int slot;
1228
1229         eb = path->nodes[0];
1230         slot = path->slots[0];
1231         if (slot > 0) {
1232                 btrfs_item_key(eb, &disk_key, slot - 1);
1233                 if (btrfs_comp_keys(&disk_key, new_key) >= 0)
1234                         return -1;
1235         }
1236         if (slot < btrfs_header_nritems(eb) - 1) {
1237                 btrfs_item_key(eb, &disk_key, slot + 1);
1238                 if (btrfs_comp_keys(&disk_key, new_key) <= 0)
1239                         return -1;
1240         }
1241
1242         btrfs_cpu_key_to_disk(&disk_key, new_key);
1243         btrfs_set_item_key(eb, &disk_key, slot);
1244         btrfs_mark_buffer_dirty(eb);
1245         if (slot == 0)
1246                 btrfs_fixup_low_keys(root, path, &disk_key, 1);
1247         return 0;
1248 }
1249
1250 /*
1251  * update an item key without the safety checks.  This is meant to be called by
1252  * fsck only.
1253  */
1254 void btrfs_set_item_key_unsafe(struct btrfs_root *root,
1255                                struct btrfs_path *path,
1256                                struct btrfs_key *new_key)
1257 {
1258         struct btrfs_disk_key disk_key;
1259         struct extent_buffer *eb;
1260         int slot;
1261
1262         eb = path->nodes[0];
1263         slot = path->slots[0];
1264
1265         btrfs_cpu_key_to_disk(&disk_key, new_key);
1266         btrfs_set_item_key(eb, &disk_key, slot);
1267         btrfs_mark_buffer_dirty(eb);
1268         if (slot == 0)
1269                 btrfs_fixup_low_keys(root, path, &disk_key, 1);
1270 }
1271
1272 /*
1273  * try to push data from one node into the next node left in the
1274  * tree.
1275  *
1276  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1277  * error, and > 0 if there was no room in the left hand block.
1278  */
1279 static int push_node_left(struct btrfs_trans_handle *trans,
1280                           struct btrfs_root *root, struct extent_buffer *dst,
1281                           struct extent_buffer *src, int empty)
1282 {
1283         int push_items = 0;
1284         int src_nritems;
1285         int dst_nritems;
1286         int ret = 0;
1287
1288         src_nritems = btrfs_header_nritems(src);
1289         dst_nritems = btrfs_header_nritems(dst);
1290         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1291         WARN_ON(btrfs_header_generation(src) != trans->transid);
1292         WARN_ON(btrfs_header_generation(dst) != trans->transid);
1293
1294         if (!empty && src_nritems <= 8)
1295                 return 1;
1296
1297         if (push_items <= 0) {
1298                 return 1;
1299         }
1300
1301         if (empty) {
1302                 push_items = min(src_nritems, push_items);
1303                 if (push_items < src_nritems) {
1304                         /* leave at least 8 pointers in the node if
1305                          * we aren't going to empty it
1306                          */
1307                         if (src_nritems - push_items < 8) {
1308                                 if (push_items <= 8)
1309                                         return 1;
1310                                 push_items -= 8;
1311                         }
1312                 }
1313         } else
1314                 push_items = min(src_nritems - 8, push_items);
1315
1316         copy_extent_buffer(dst, src,
1317                            btrfs_node_key_ptr_offset(dst_nritems),
1318                            btrfs_node_key_ptr_offset(0),
1319                            push_items * sizeof(struct btrfs_key_ptr));
1320
1321         if (push_items < src_nritems) {
1322                 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1323                                       btrfs_node_key_ptr_offset(push_items),
1324                                       (src_nritems - push_items) *
1325                                       sizeof(struct btrfs_key_ptr));
1326         }
1327         btrfs_set_header_nritems(src, src_nritems - push_items);
1328         btrfs_set_header_nritems(dst, dst_nritems + push_items);
1329         btrfs_mark_buffer_dirty(src);
1330         btrfs_mark_buffer_dirty(dst);
1331
1332         return ret;
1333 }
1334
1335 /*
1336  * try to push data from one node into the next node right in the
1337  * tree.
1338  *
1339  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1340  * error, and > 0 if there was no room in the right hand block.
1341  *
1342  * this will  only push up to 1/2 the contents of the left node over
1343  */
1344 static int balance_node_right(struct btrfs_trans_handle *trans,
1345                               struct btrfs_root *root,
1346                               struct extent_buffer *dst,
1347                               struct extent_buffer *src)
1348 {
1349         int push_items = 0;
1350         int max_push;
1351         int src_nritems;
1352         int dst_nritems;
1353         int ret = 0;
1354
1355         WARN_ON(btrfs_header_generation(src) != trans->transid);
1356         WARN_ON(btrfs_header_generation(dst) != trans->transid);
1357
1358         src_nritems = btrfs_header_nritems(src);
1359         dst_nritems = btrfs_header_nritems(dst);
1360         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1361         if (push_items <= 0) {
1362                 return 1;
1363         }
1364
1365         if (src_nritems < 4) {
1366                 return 1;
1367         }
1368
1369         max_push = src_nritems / 2 + 1;
1370         /* don't try to empty the node */
1371         if (max_push >= src_nritems) {
1372                 return 1;
1373         }
1374
1375         if (max_push < push_items)
1376                 push_items = max_push;
1377
1378         memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1379                                       btrfs_node_key_ptr_offset(0),
1380                                       (dst_nritems) *
1381                                       sizeof(struct btrfs_key_ptr));
1382
1383         copy_extent_buffer(dst, src,
1384                            btrfs_node_key_ptr_offset(0),
1385                            btrfs_node_key_ptr_offset(src_nritems - push_items),
1386                            push_items * sizeof(struct btrfs_key_ptr));
1387
1388         btrfs_set_header_nritems(src, src_nritems - push_items);
1389         btrfs_set_header_nritems(dst, dst_nritems + push_items);
1390
1391         btrfs_mark_buffer_dirty(src);
1392         btrfs_mark_buffer_dirty(dst);
1393
1394         return ret;
1395 }
1396
1397 /*
1398  * helper function to insert a new root level in the tree.
1399  * A new node is allocated, and a single item is inserted to
1400  * point to the existing root
1401  *
1402  * returns zero on success or < 0 on failure.
1403  */
1404 static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1405                            struct btrfs_root *root,
1406                            struct btrfs_path *path, int level)
1407 {
1408         u64 lower_gen;
1409         struct extent_buffer *lower;
1410         struct extent_buffer *c;
1411         struct extent_buffer *old;
1412         struct btrfs_disk_key lower_key;
1413
1414         BUG_ON(path->nodes[level]);
1415         BUG_ON(path->nodes[level-1] != root->node);
1416
1417         lower = path->nodes[level-1];
1418         if (level == 1)
1419                 btrfs_item_key(lower, &lower_key, 0);
1420         else
1421                 btrfs_node_key(lower, &lower_key, 0);
1422
1423         c = btrfs_alloc_free_block(trans, root, root->nodesize,
1424                                    root->root_key.objectid, &lower_key,
1425                                    level, root->node->start, 0);
1426
1427         if (IS_ERR(c))
1428                 return PTR_ERR(c);
1429
1430         memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
1431         btrfs_set_header_nritems(c, 1);
1432         btrfs_set_header_level(c, level);
1433         btrfs_set_header_bytenr(c, c->start);
1434         btrfs_set_header_generation(c, trans->transid);
1435         btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
1436         btrfs_set_header_owner(c, root->root_key.objectid);
1437
1438         write_extent_buffer(c, root->fs_info->fsid,
1439                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
1440
1441         write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
1442                             btrfs_header_chunk_tree_uuid(c),
1443                             BTRFS_UUID_SIZE);
1444
1445         btrfs_set_node_key(c, &lower_key, 0);
1446         btrfs_set_node_blockptr(c, 0, lower->start);
1447         lower_gen = btrfs_header_generation(lower);
1448         WARN_ON(lower_gen != trans->transid);
1449
1450         btrfs_set_node_ptr_generation(c, 0, lower_gen);
1451
1452         btrfs_mark_buffer_dirty(c);
1453
1454         old = root->node;
1455         root->node = c;
1456
1457         /* the super has an extra ref to root->node */
1458         free_extent_buffer(old);
1459
1460         add_root_to_dirty_list(root);
1461         extent_buffer_get(c);
1462         path->nodes[level] = c;
1463         path->slots[level] = 0;
1464         return 0;
1465 }
1466
1467 /*
1468  * worker function to insert a single pointer in a node.
1469  * the node should have enough room for the pointer already
1470  *
1471  * slot and level indicate where you want the key to go, and
1472  * blocknr is the block the key points to.
1473  *
1474  * returns zero on success and < 0 on any error
1475  */
1476 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1477                       *root, struct btrfs_path *path, struct btrfs_disk_key
1478                       *key, u64 bytenr, int slot, int level)
1479 {
1480         struct extent_buffer *lower;
1481         int nritems;
1482
1483         BUG_ON(!path->nodes[level]);
1484         lower = path->nodes[level];
1485         nritems = btrfs_header_nritems(lower);
1486         if (slot > nritems)
1487                 BUG();
1488         if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1489                 BUG();
1490         if (slot != nritems) {
1491                 memmove_extent_buffer(lower,
1492                               btrfs_node_key_ptr_offset(slot + 1),
1493                               btrfs_node_key_ptr_offset(slot),
1494                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
1495         }
1496         btrfs_set_node_key(lower, key, slot);
1497         btrfs_set_node_blockptr(lower, slot, bytenr);
1498         WARN_ON(trans->transid == 0);
1499         btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1500         btrfs_set_header_nritems(lower, nritems + 1);
1501         btrfs_mark_buffer_dirty(lower);
1502         return 0;
1503 }
1504
1505 /*
1506  * split the node at the specified level in path in two.
1507  * The path is corrected to point to the appropriate node after the split
1508  *
1509  * Before splitting this tries to make some room in the node by pushing
1510  * left and right, if either one works, it returns right away.
1511  *
1512  * returns 0 on success and < 0 on failure
1513  */
1514 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1515                       *root, struct btrfs_path *path, int level)
1516 {
1517         struct extent_buffer *c;
1518         struct extent_buffer *split;
1519         struct btrfs_disk_key disk_key;
1520         int mid;
1521         int ret;
1522         int wret;
1523         u32 c_nritems;
1524
1525         c = path->nodes[level];
1526         WARN_ON(btrfs_header_generation(c) != trans->transid);
1527         if (c == root->node) {
1528                 /* trying to split the root, lets make a new one */
1529                 ret = insert_new_root(trans, root, path, level + 1);
1530                 if (ret)
1531                         return ret;
1532         } else {
1533                 ret = push_nodes_for_insert(trans, root, path, level);
1534                 c = path->nodes[level];
1535                 if (!ret && btrfs_header_nritems(c) <
1536                     BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
1537                         return 0;
1538                 if (ret < 0)
1539                         return ret;
1540         }
1541
1542         c_nritems = btrfs_header_nritems(c);
1543         mid = (c_nritems + 1) / 2;
1544         btrfs_node_key(c, &disk_key, mid);
1545
1546         split = btrfs_alloc_free_block(trans, root, root->nodesize,
1547                                         root->root_key.objectid,
1548                                         &disk_key, level, c->start, 0);
1549         if (IS_ERR(split))
1550                 return PTR_ERR(split);
1551
1552         memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
1553         btrfs_set_header_level(split, btrfs_header_level(c));
1554         btrfs_set_header_bytenr(split, split->start);
1555         btrfs_set_header_generation(split, trans->transid);
1556         btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
1557         btrfs_set_header_owner(split, root->root_key.objectid);
1558         write_extent_buffer(split, root->fs_info->fsid,
1559                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
1560         write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
1561                             btrfs_header_chunk_tree_uuid(split),
1562                             BTRFS_UUID_SIZE);
1563
1564
1565         copy_extent_buffer(split, c,
1566                            btrfs_node_key_ptr_offset(0),
1567                            btrfs_node_key_ptr_offset(mid),
1568                            (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1569         btrfs_set_header_nritems(split, c_nritems - mid);
1570         btrfs_set_header_nritems(c, mid);
1571         ret = 0;
1572
1573         btrfs_mark_buffer_dirty(c);
1574         btrfs_mark_buffer_dirty(split);
1575
1576         wret = insert_ptr(trans, root, path, &disk_key, split->start,
1577                           path->slots[level + 1] + 1,
1578                           level + 1);
1579         if (wret)
1580                 ret = wret;
1581
1582         if (path->slots[level] >= mid) {
1583                 path->slots[level] -= mid;
1584                 free_extent_buffer(c);
1585                 path->nodes[level] = split;
1586                 path->slots[level + 1] += 1;
1587         } else {
1588                 free_extent_buffer(split);
1589         }
1590         return ret;
1591 }
1592
1593 /*
1594  * how many bytes are required to store the items in a leaf.  start
1595  * and nr indicate which items in the leaf to check.  This totals up the
1596  * space used both by the item structs and the item data
1597  */
1598 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1599 {
1600         int data_len;
1601         int nritems = btrfs_header_nritems(l);
1602         int end = min(nritems, start + nr) - 1;
1603
1604         if (!nr)
1605                 return 0;
1606         data_len = btrfs_item_end_nr(l, start);
1607         data_len = data_len - btrfs_item_offset_nr(l, end);
1608         data_len += sizeof(struct btrfs_item) * nr;
1609         WARN_ON(data_len < 0);
1610         return data_len;
1611 }
1612
1613 /*
1614  * The space between the end of the leaf items and
1615  * the start of the leaf data.  IOW, how much room
1616  * the leaf has left for both items and data
1617  */
1618 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1619 {
1620         int nritems = btrfs_header_nritems(leaf);
1621         int ret;
1622         ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1623         if (ret < 0) {
1624                 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1625                        ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1626                        leaf_space_used(leaf, 0, nritems), nritems);
1627         }
1628         return ret;
1629 }
1630
1631 /*
1632  * push some data in the path leaf to the right, trying to free up at
1633  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
1634  *
1635  * returns 1 if the push failed because the other node didn't have enough
1636  * room, 0 if everything worked out and < 0 if there were major errors.
1637  */
1638 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1639                            *root, struct btrfs_path *path, int data_size,
1640                            int empty)
1641 {
1642         struct extent_buffer *left = path->nodes[0];
1643         struct extent_buffer *right;
1644         struct extent_buffer *upper;
1645         struct btrfs_disk_key disk_key;
1646         int slot;
1647         u32 i;
1648         int free_space;
1649         int push_space = 0;
1650         int push_items = 0;
1651         struct btrfs_item *item;
1652         u32 left_nritems;
1653         u32 nr;
1654         u32 right_nritems;
1655         u32 data_end;
1656         u32 this_item_size;
1657         int ret;
1658
1659         slot = path->slots[1];
1660         if (!path->nodes[1]) {
1661                 return 1;
1662         }
1663         upper = path->nodes[1];
1664         if (slot >= btrfs_header_nritems(upper) - 1)
1665                 return 1;
1666
1667         right = read_node_slot(root, upper, slot + 1);
1668         if (!extent_buffer_uptodate(right)) {
1669                 if (IS_ERR(right))
1670                         return PTR_ERR(right);
1671                 return -EIO;
1672         }
1673         free_space = btrfs_leaf_free_space(root, right);
1674         if (free_space < data_size) {
1675                 free_extent_buffer(right);
1676                 return 1;
1677         }
1678
1679         /* cow and double check */
1680         ret = btrfs_cow_block(trans, root, right, upper,
1681                               slot + 1, &right);
1682         if (ret) {
1683                 free_extent_buffer(right);
1684                 return 1;
1685         }
1686         free_space = btrfs_leaf_free_space(root, right);
1687         if (free_space < data_size) {
1688                 free_extent_buffer(right);
1689                 return 1;
1690         }
1691
1692         left_nritems = btrfs_header_nritems(left);
1693         if (left_nritems == 0) {
1694                 free_extent_buffer(right);
1695                 return 1;
1696         }
1697
1698         if (empty)
1699                 nr = 0;
1700         else
1701                 nr = 1;
1702
1703         i = left_nritems - 1;
1704         while (i >= nr) {
1705                 item = btrfs_item_nr(i);
1706
1707                 if (path->slots[0] == i)
1708                         push_space += data_size + sizeof(*item);
1709
1710                 this_item_size = btrfs_item_size(left, item);
1711                 if (this_item_size + sizeof(*item) + push_space > free_space)
1712                         break;
1713                 push_items++;
1714                 push_space += this_item_size + sizeof(*item);
1715                 if (i == 0)
1716                         break;
1717                 i--;
1718         }
1719
1720         if (push_items == 0) {
1721                 free_extent_buffer(right);
1722                 return 1;
1723         }
1724
1725         if (!empty && push_items == left_nritems)
1726                 WARN_ON(1);
1727
1728         /* push left to right */
1729         right_nritems = btrfs_header_nritems(right);
1730
1731         push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1732         push_space -= leaf_data_end(root, left);
1733
1734         /* make room in the right data area */
1735         data_end = leaf_data_end(root, right);
1736         memmove_extent_buffer(right,
1737                               btrfs_leaf_data(right) + data_end - push_space,
1738                               btrfs_leaf_data(right) + data_end,
1739                               BTRFS_LEAF_DATA_SIZE(root) - data_end);
1740
1741         /* copy from the left data area */
1742         copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1743                      BTRFS_LEAF_DATA_SIZE(root) - push_space,
1744                      btrfs_leaf_data(left) + leaf_data_end(root, left),
1745                      push_space);
1746
1747         memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1748                               btrfs_item_nr_offset(0),
1749                               right_nritems * sizeof(struct btrfs_item));
1750
1751         /* copy the items from left to right */
1752         copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1753                    btrfs_item_nr_offset(left_nritems - push_items),
1754                    push_items * sizeof(struct btrfs_item));
1755
1756         /* update the item pointers */
1757         right_nritems += push_items;
1758         btrfs_set_header_nritems(right, right_nritems);
1759         push_space = BTRFS_LEAF_DATA_SIZE(root);
1760         for (i = 0; i < right_nritems; i++) {
1761                 item = btrfs_item_nr(i);
1762                 push_space -= btrfs_item_size(right, item);
1763                 btrfs_set_item_offset(right, item, push_space);
1764         }
1765
1766         left_nritems -= push_items;
1767         btrfs_set_header_nritems(left, left_nritems);
1768
1769         if (left_nritems)
1770                 btrfs_mark_buffer_dirty(left);
1771         btrfs_mark_buffer_dirty(right);
1772
1773         btrfs_item_key(right, &disk_key, 0);
1774         btrfs_set_node_key(upper, &disk_key, slot + 1);
1775         btrfs_mark_buffer_dirty(upper);
1776
1777         /* then fixup the leaf pointer in the path */
1778         if (path->slots[0] >= left_nritems) {
1779                 path->slots[0] -= left_nritems;
1780                 free_extent_buffer(path->nodes[0]);
1781                 path->nodes[0] = right;
1782                 path->slots[1] += 1;
1783         } else {
1784                 free_extent_buffer(right);
1785         }
1786         return 0;
1787 }
1788 /*
1789  * push some data in the path leaf to the left, trying to free up at
1790  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
1791  */
1792 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1793                           *root, struct btrfs_path *path, int data_size,
1794                           int empty)
1795 {
1796         struct btrfs_disk_key disk_key;
1797         struct extent_buffer *right = path->nodes[0];
1798         struct extent_buffer *left;
1799         int slot;
1800         int i;
1801         int free_space;
1802         int push_space = 0;
1803         int push_items = 0;
1804         struct btrfs_item *item;
1805         u32 old_left_nritems;
1806         u32 right_nritems;
1807         u32 nr;
1808         int ret = 0;
1809         u32 this_item_size;
1810         u32 old_left_item_size;
1811
1812         slot = path->slots[1];
1813         if (slot == 0)
1814                 return 1;
1815         if (!path->nodes[1])
1816                 return 1;
1817
1818         right_nritems = btrfs_header_nritems(right);
1819         if (right_nritems == 0) {
1820                 return 1;
1821         }
1822
1823         left = read_node_slot(root, path->nodes[1], slot - 1);
1824         free_space = btrfs_leaf_free_space(root, left);
1825         if (free_space < data_size) {
1826                 free_extent_buffer(left);
1827                 return 1;
1828         }
1829
1830         /* cow and double check */
1831         ret = btrfs_cow_block(trans, root, left,
1832                               path->nodes[1], slot - 1, &left);
1833         if (ret) {
1834                 /* we hit -ENOSPC, but it isn't fatal here */
1835                 free_extent_buffer(left);
1836                 return 1;
1837         }
1838
1839         free_space = btrfs_leaf_free_space(root, left);
1840         if (free_space < data_size) {
1841                 free_extent_buffer(left);
1842                 return 1;
1843         }
1844
1845         if (empty)
1846                 nr = right_nritems;
1847         else
1848                 nr = right_nritems - 1;
1849
1850         for (i = 0; i < nr; i++) {
1851                 item = btrfs_item_nr(i);
1852
1853                 if (path->slots[0] == i)
1854                         push_space += data_size + sizeof(*item);
1855
1856                 this_item_size = btrfs_item_size(right, item);
1857                 if (this_item_size + sizeof(*item) + push_space > free_space)
1858                         break;
1859
1860                 push_items++;
1861                 push_space += this_item_size + sizeof(*item);
1862         }
1863
1864         if (push_items == 0) {
1865                 free_extent_buffer(left);
1866                 return 1;
1867         }
1868         if (!empty && push_items == btrfs_header_nritems(right))
1869                 WARN_ON(1);
1870
1871         /* push data from right to left */
1872         copy_extent_buffer(left, right,
1873                            btrfs_item_nr_offset(btrfs_header_nritems(left)),
1874                            btrfs_item_nr_offset(0),
1875                            push_items * sizeof(struct btrfs_item));
1876
1877         push_space = BTRFS_LEAF_DATA_SIZE(root) -
1878                      btrfs_item_offset_nr(right, push_items -1);
1879
1880         copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1881                      leaf_data_end(root, left) - push_space,
1882                      btrfs_leaf_data(right) +
1883                      btrfs_item_offset_nr(right, push_items - 1),
1884                      push_space);
1885         old_left_nritems = btrfs_header_nritems(left);
1886         BUG_ON(old_left_nritems == 0);
1887
1888         old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1889         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1890                 u32 ioff;
1891
1892                 item = btrfs_item_nr(i);
1893                 ioff = btrfs_item_offset(left, item);
1894                 btrfs_set_item_offset(left, item,
1895                       ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1896         }
1897         btrfs_set_header_nritems(left, old_left_nritems + push_items);
1898
1899         /* fixup right node */
1900         if (push_items > right_nritems) {
1901                 printk("push items %d nr %u\n", push_items, right_nritems);
1902                 WARN_ON(1);
1903         }
1904
1905         if (push_items < right_nritems) {
1906                 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1907                                                   leaf_data_end(root, right);
1908                 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1909                                       BTRFS_LEAF_DATA_SIZE(root) - push_space,
1910                                       btrfs_leaf_data(right) +
1911                                       leaf_data_end(root, right), push_space);
1912
1913                 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1914                               btrfs_item_nr_offset(push_items),
1915                              (btrfs_header_nritems(right) - push_items) *
1916                              sizeof(struct btrfs_item));
1917         }
1918         right_nritems -= push_items;
1919         btrfs_set_header_nritems(right, right_nritems);
1920         push_space = BTRFS_LEAF_DATA_SIZE(root);
1921         for (i = 0; i < right_nritems; i++) {
1922                 item = btrfs_item_nr(i);
1923                 push_space = push_space - btrfs_item_size(right, item);
1924                 btrfs_set_item_offset(right, item, push_space);
1925         }
1926
1927         btrfs_mark_buffer_dirty(left);
1928         if (right_nritems)
1929                 btrfs_mark_buffer_dirty(right);
1930
1931         btrfs_item_key(right, &disk_key, 0);
1932         btrfs_fixup_low_keys(root, path, &disk_key, 1);
1933
1934         /* then fixup the leaf pointer in the path */
1935         if (path->slots[0] < push_items) {
1936                 path->slots[0] += old_left_nritems;
1937                 free_extent_buffer(path->nodes[0]);
1938                 path->nodes[0] = left;
1939                 path->slots[1] -= 1;
1940         } else {
1941                 free_extent_buffer(left);
1942                 path->slots[0] -= push_items;
1943         }
1944         BUG_ON(path->slots[0] < 0);
1945         return ret;
1946 }
1947
1948 /*
1949  * split the path's leaf in two, making sure there is at least data_size
1950  * available for the resulting leaf level of the path.
1951  *
1952  * returns 0 if all went well and < 0 on failure.
1953  */
1954 static noinline int copy_for_split(struct btrfs_trans_handle *trans,
1955                                struct btrfs_root *root,
1956                                struct btrfs_path *path,
1957                                struct extent_buffer *l,
1958                                struct extent_buffer *right,
1959                                int slot, int mid, int nritems)
1960 {
1961         int data_copy_size;
1962         int rt_data_off;
1963         int i;
1964         int ret = 0;
1965         int wret;
1966         struct btrfs_disk_key disk_key;
1967
1968         nritems = nritems - mid;
1969         btrfs_set_header_nritems(right, nritems);
1970         data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
1971
1972         copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
1973                            btrfs_item_nr_offset(mid),
1974                            nritems * sizeof(struct btrfs_item));
1975
1976         copy_extent_buffer(right, l,
1977                      btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1978                      data_copy_size, btrfs_leaf_data(l) +
1979                      leaf_data_end(root, l), data_copy_size);
1980
1981         rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1982                       btrfs_item_end_nr(l, mid);
1983
1984         for (i = 0; i < nritems; i++) {
1985                 struct btrfs_item *item = btrfs_item_nr(i);
1986                 u32 ioff = btrfs_item_offset(right, item);
1987                 btrfs_set_item_offset(right, item, ioff + rt_data_off);
1988         }
1989
1990         btrfs_set_header_nritems(l, mid);
1991         ret = 0;
1992         btrfs_item_key(right, &disk_key, 0);
1993         wret = insert_ptr(trans, root, path, &disk_key, right->start,
1994                           path->slots[1] + 1, 1);
1995         if (wret)
1996                 ret = wret;
1997
1998         btrfs_mark_buffer_dirty(right);
1999         btrfs_mark_buffer_dirty(l);
2000         BUG_ON(path->slots[0] != slot);
2001
2002         if (mid <= slot) {
2003                 free_extent_buffer(path->nodes[0]);
2004                 path->nodes[0] = right;
2005                 path->slots[0] -= mid;
2006                 path->slots[1] += 1;
2007         } else {
2008                 free_extent_buffer(right);
2009         }
2010
2011         BUG_ON(path->slots[0] < 0);
2012
2013         return ret;
2014 }
2015
2016 /*
2017  * split the path's leaf in two, making sure there is at least data_size
2018  * available for the resulting leaf level of the path.
2019  *
2020  * returns 0 if all went well and < 0 on failure.
2021  */
2022 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2023                                struct btrfs_root *root,
2024                                struct btrfs_key *ins_key,
2025                                struct btrfs_path *path, int data_size,
2026                                int extend)
2027 {
2028         struct btrfs_disk_key disk_key;
2029         struct extent_buffer *l;
2030         u32 nritems;
2031         int mid;
2032         int slot;
2033         struct extent_buffer *right;
2034         int ret = 0;
2035         int wret;
2036         int split;
2037         int num_doubles = 0;
2038
2039         l = path->nodes[0];
2040         slot = path->slots[0];
2041         if (extend && data_size + btrfs_item_size_nr(l, slot) +
2042             sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
2043                 return -EOVERFLOW;
2044
2045         /* first try to make some room by pushing left and right */
2046         if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2047                 wret = push_leaf_right(trans, root, path, data_size, 0);
2048                 if (wret < 0)
2049                         return wret;
2050                 if (wret) {
2051                         wret = push_leaf_left(trans, root, path, data_size, 0);
2052                         if (wret < 0)
2053                                 return wret;
2054                 }
2055                 l = path->nodes[0];
2056
2057                 /* did the pushes work? */
2058                 if (btrfs_leaf_free_space(root, l) >= data_size)
2059                         return 0;
2060         }
2061
2062         if (!path->nodes[1]) {
2063                 ret = insert_new_root(trans, root, path, 1);
2064                 if (ret)
2065                         return ret;
2066         }
2067 again:
2068         split = 1;
2069         l = path->nodes[0];
2070         slot = path->slots[0];
2071         nritems = btrfs_header_nritems(l);
2072         mid = (nritems + 1) / 2;
2073
2074         if (mid <= slot) {
2075                 if (nritems == 1 ||
2076                     leaf_space_used(l, mid, nritems - mid) + data_size >
2077                         BTRFS_LEAF_DATA_SIZE(root)) {
2078                         if (slot >= nritems) {
2079                                 split = 0;
2080                         } else {
2081                                 mid = slot;
2082                                 if (mid != nritems &&
2083                                     leaf_space_used(l, mid, nritems - mid) +
2084                                     data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2085                                         split = 2;
2086                                 }
2087                         }
2088                 }
2089         } else {
2090                 if (leaf_space_used(l, 0, mid) + data_size >
2091                         BTRFS_LEAF_DATA_SIZE(root)) {
2092                         if (!extend && data_size && slot == 0) {
2093                                 split = 0;
2094                         } else if ((extend || !data_size) && slot == 0) {
2095                                 mid = 1;
2096                         } else {
2097                                 mid = slot;
2098                                 if (mid != nritems &&
2099                                     leaf_space_used(l, mid, nritems - mid) +
2100                                     data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2101                                         split = 2 ;
2102                                 }
2103                         }
2104                 }
2105         }
2106
2107         if (split == 0)
2108                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2109         else
2110                 btrfs_item_key(l, &disk_key, mid);
2111
2112         right = btrfs_alloc_free_block(trans, root, root->leafsize,
2113                                         root->root_key.objectid,
2114                                         &disk_key, 0, l->start, 0);
2115         if (IS_ERR(right)) {
2116                 BUG_ON(1);
2117                 return PTR_ERR(right);
2118         }
2119
2120         memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2121         btrfs_set_header_bytenr(right, right->start);
2122         btrfs_set_header_generation(right, trans->transid);
2123         btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
2124         btrfs_set_header_owner(right, root->root_key.objectid);
2125         btrfs_set_header_level(right, 0);
2126         write_extent_buffer(right, root->fs_info->fsid,
2127                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
2128
2129         write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2130                             btrfs_header_chunk_tree_uuid(right),
2131                             BTRFS_UUID_SIZE);
2132
2133         if (split == 0) {
2134                 if (mid <= slot) {
2135                         btrfs_set_header_nritems(right, 0);
2136                         wret = insert_ptr(trans, root, path,
2137                                           &disk_key, right->start,
2138                                           path->slots[1] + 1, 1);
2139                         if (wret)
2140                                 ret = wret;
2141
2142                         free_extent_buffer(path->nodes[0]);
2143                         path->nodes[0] = right;
2144                         path->slots[0] = 0;
2145                         path->slots[1] += 1;
2146                 } else {
2147                         btrfs_set_header_nritems(right, 0);
2148                         wret = insert_ptr(trans, root, path,
2149                                           &disk_key,
2150                                           right->start,
2151                                           path->slots[1], 1);
2152                         if (wret)
2153                                 ret = wret;
2154                         free_extent_buffer(path->nodes[0]);
2155                         path->nodes[0] = right;
2156                         path->slots[0] = 0;
2157                         if (path->slots[1] == 0) {
2158                                 btrfs_fixup_low_keys(root, path,
2159                                                      &disk_key, 1);
2160                         }
2161                 }
2162                 btrfs_mark_buffer_dirty(right);
2163                 return ret;
2164         }
2165
2166         ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2167         BUG_ON(ret);
2168
2169         if (split == 2) {
2170                 BUG_ON(num_doubles != 0);
2171                 num_doubles++;
2172                 goto again;
2173         }
2174
2175         return ret;
2176 }
2177
2178 /*
2179  * This function splits a single item into two items,
2180  * giving 'new_key' to the new item and splitting the
2181  * old one at split_offset (from the start of the item).
2182  *
2183  * The path may be released by this operation.  After
2184  * the split, the path is pointing to the old item.  The
2185  * new item is going to be in the same node as the old one.
2186  *
2187  * Note, the item being split must be smaller enough to live alone on
2188  * a tree block with room for one extra struct btrfs_item
2189  *
2190  * This allows us to split the item in place, keeping a lock on the
2191  * leaf the entire time.
2192  */
2193 int btrfs_split_item(struct btrfs_trans_handle *trans,
2194                      struct btrfs_root *root,
2195                      struct btrfs_path *path,
2196                      struct btrfs_key *new_key,
2197                      unsigned long split_offset)
2198 {
2199         u32 item_size;
2200         struct extent_buffer *leaf;
2201         struct btrfs_key orig_key;
2202         struct btrfs_item *item;
2203         struct btrfs_item *new_item;
2204         int ret = 0;
2205         int slot;
2206         u32 nritems;
2207         u32 orig_offset;
2208         struct btrfs_disk_key disk_key;
2209         char *buf;
2210
2211         leaf = path->nodes[0];
2212         btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
2213         if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
2214                 goto split;
2215
2216         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2217         btrfs_release_path(path);
2218
2219         path->search_for_split = 1;
2220
2221         ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
2222         path->search_for_split = 0;
2223
2224         /* if our item isn't there or got smaller, return now */
2225         if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
2226                                                         path->slots[0])) {
2227                 return -EAGAIN;
2228         }
2229
2230         ret = split_leaf(trans, root, &orig_key, path, 0, 0);
2231         BUG_ON(ret);
2232
2233         BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
2234         leaf = path->nodes[0];
2235
2236 split:
2237         item = btrfs_item_nr(path->slots[0]);
2238         orig_offset = btrfs_item_offset(leaf, item);
2239         item_size = btrfs_item_size(leaf, item);
2240
2241
2242         buf = kmalloc(item_size, GFP_NOFS);
2243         read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
2244                             path->slots[0]), item_size);
2245         slot = path->slots[0] + 1;
2246         leaf = path->nodes[0];
2247
2248         nritems = btrfs_header_nritems(leaf);
2249
2250         if (slot != nritems) {
2251                 /* shift the items */
2252                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2253                               btrfs_item_nr_offset(slot),
2254                               (nritems - slot) * sizeof(struct btrfs_item));
2255
2256         }
2257
2258         btrfs_cpu_key_to_disk(&disk_key, new_key);
2259         btrfs_set_item_key(leaf, &disk_key, slot);
2260
2261         new_item = btrfs_item_nr(slot);
2262
2263         btrfs_set_item_offset(leaf, new_item, orig_offset);
2264         btrfs_set_item_size(leaf, new_item, item_size - split_offset);
2265
2266         btrfs_set_item_offset(leaf, item,
2267                               orig_offset + item_size - split_offset);
2268         btrfs_set_item_size(leaf, item, split_offset);
2269
2270         btrfs_set_header_nritems(leaf, nritems + 1);
2271
2272         /* write the data for the start of the original item */
2273         write_extent_buffer(leaf, buf,
2274                             btrfs_item_ptr_offset(leaf, path->slots[0]),
2275                             split_offset);
2276
2277         /* write the data for the new item */
2278         write_extent_buffer(leaf, buf + split_offset,
2279                             btrfs_item_ptr_offset(leaf, slot),
2280                             item_size - split_offset);
2281         btrfs_mark_buffer_dirty(leaf);
2282
2283         ret = 0;
2284         if (btrfs_leaf_free_space(root, leaf) < 0) {
2285                 btrfs_print_leaf(root, leaf);
2286                 BUG();
2287         }
2288         kfree(buf);
2289         return ret;
2290 }
2291
2292 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
2293                         struct btrfs_root *root,
2294                         struct btrfs_path *path,
2295                         u32 new_size, int from_end)
2296 {
2297         int ret = 0;
2298         int slot;
2299         struct extent_buffer *leaf;
2300         struct btrfs_item *item;
2301         u32 nritems;
2302         unsigned int data_end;
2303         unsigned int old_data_start;
2304         unsigned int old_size;
2305         unsigned int size_diff;
2306         int i;
2307
2308         leaf = path->nodes[0];
2309         slot = path->slots[0];
2310
2311         old_size = btrfs_item_size_nr(leaf, slot);
2312         if (old_size == new_size)
2313                 return 0;
2314
2315         nritems = btrfs_header_nritems(leaf);
2316         data_end = leaf_data_end(root, leaf);
2317
2318         old_data_start = btrfs_item_offset_nr(leaf, slot);
2319
2320         size_diff = old_size - new_size;
2321
2322         BUG_ON(slot < 0);
2323         BUG_ON(slot >= nritems);
2324
2325         /*
2326          * item0..itemN ... dataN.offset..dataN.size .. data0.size
2327          */
2328         /* first correct the data pointers */
2329         for (i = slot; i < nritems; i++) {
2330                 u32 ioff;
2331                 item = btrfs_item_nr(i);
2332                 ioff = btrfs_item_offset(leaf, item);
2333                 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2334         }
2335
2336         /* shift the data */
2337         if (from_end) {
2338                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2339                               data_end + size_diff, btrfs_leaf_data(leaf) +
2340                               data_end, old_data_start + new_size - data_end);
2341         } else {
2342                 struct btrfs_disk_key disk_key;
2343                 u64 offset;
2344
2345                 btrfs_item_key(leaf, &disk_key, slot);
2346
2347                 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
2348                         unsigned long ptr;
2349                         struct btrfs_file_extent_item *fi;
2350
2351                         fi = btrfs_item_ptr(leaf, slot,
2352                                             struct btrfs_file_extent_item);
2353                         fi = (struct btrfs_file_extent_item *)(
2354                              (unsigned long)fi - size_diff);
2355
2356                         if (btrfs_file_extent_type(leaf, fi) ==
2357                             BTRFS_FILE_EXTENT_INLINE) {
2358                                 ptr = btrfs_item_ptr_offset(leaf, slot);
2359                                 memmove_extent_buffer(leaf, ptr,
2360                                         (unsigned long)fi,
2361                                         offsetof(struct btrfs_file_extent_item,
2362                                                  disk_bytenr));
2363                         }
2364                 }
2365
2366                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2367                               data_end + size_diff, btrfs_leaf_data(leaf) +
2368                               data_end, old_data_start - data_end);
2369
2370                 offset = btrfs_disk_key_offset(&disk_key);
2371                 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
2372                 btrfs_set_item_key(leaf, &disk_key, slot);
2373                 if (slot == 0)
2374                         btrfs_fixup_low_keys(root, path, &disk_key, 1);
2375         }
2376
2377         item = btrfs_item_nr(slot);
2378         btrfs_set_item_size(leaf, item, new_size);
2379         btrfs_mark_buffer_dirty(leaf);
2380
2381         ret = 0;
2382         if (btrfs_leaf_free_space(root, leaf) < 0) {
2383                 btrfs_print_leaf(root, leaf);
2384                 BUG();
2385         }
2386         return ret;
2387 }
2388
2389 int btrfs_extend_item(struct btrfs_trans_handle *trans,
2390                       struct btrfs_root *root, struct btrfs_path *path,
2391                       u32 data_size)
2392 {
2393         int ret = 0;
2394         int slot;
2395         struct extent_buffer *leaf;
2396         struct btrfs_item *item;
2397         u32 nritems;
2398         unsigned int data_end;
2399         unsigned int old_data;
2400         unsigned int old_size;
2401         int i;
2402
2403         leaf = path->nodes[0];
2404
2405         nritems = btrfs_header_nritems(leaf);
2406         data_end = leaf_data_end(root, leaf);
2407
2408         if (btrfs_leaf_free_space(root, leaf) < data_size) {
2409                 btrfs_print_leaf(root, leaf);
2410                 BUG();
2411         }
2412         slot = path->slots[0];
2413         old_data = btrfs_item_end_nr(leaf, slot);
2414
2415         BUG_ON(slot < 0);
2416         if (slot >= nritems) {
2417                 btrfs_print_leaf(root, leaf);
2418                 printk("slot %d too large, nritems %d\n", slot, nritems);
2419                 BUG_ON(1);
2420         }
2421
2422         /*
2423          * item0..itemN ... dataN.offset..dataN.size .. data0.size
2424          */
2425         /* first correct the data pointers */
2426         for (i = slot; i < nritems; i++) {
2427                 u32 ioff;
2428                 item = btrfs_item_nr(i);
2429                 ioff = btrfs_item_offset(leaf, item);
2430                 btrfs_set_item_offset(leaf, item, ioff - data_size);
2431         }
2432
2433         /* shift the data */
2434         memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2435                       data_end - data_size, btrfs_leaf_data(leaf) +
2436                       data_end, old_data - data_end);
2437
2438         data_end = old_data;
2439         old_size = btrfs_item_size_nr(leaf, slot);
2440         item = btrfs_item_nr(slot);
2441         btrfs_set_item_size(leaf, item, old_size + data_size);
2442         btrfs_mark_buffer_dirty(leaf);
2443
2444         ret = 0;
2445         if (btrfs_leaf_free_space(root, leaf) < 0) {
2446                 btrfs_print_leaf(root, leaf);
2447                 BUG();
2448         }
2449         return ret;
2450 }
2451
2452 /*
2453  * Given a key and some data, insert an item into the tree.
2454  * This does all the path init required, making room in the tree if needed.
2455  */
2456 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2457                             struct btrfs_root *root,
2458                             struct btrfs_path *path,
2459                             struct btrfs_key *cpu_key, u32 *data_size,
2460                             int nr)
2461 {
2462         struct extent_buffer *leaf;
2463         struct btrfs_item *item;
2464         int ret = 0;
2465         int slot;
2466         int i;
2467         u32 nritems;
2468         u32 total_size = 0;
2469         u32 total_data = 0;
2470         unsigned int data_end;
2471         struct btrfs_disk_key disk_key;
2472
2473         for (i = 0; i < nr; i++) {
2474                 total_data += data_size[i];
2475         }
2476
2477         /* create a root if there isn't one */
2478         if (!root->node)
2479                 BUG();
2480
2481         total_size = total_data + nr * sizeof(struct btrfs_item);
2482         ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2483         if (ret == 0) {
2484                 return -EEXIST;
2485         }
2486         if (ret < 0)
2487                 goto out;
2488
2489         leaf = path->nodes[0];
2490
2491         nritems = btrfs_header_nritems(leaf);
2492         data_end = leaf_data_end(root, leaf);
2493
2494         if (btrfs_leaf_free_space(root, leaf) < total_size) {
2495                 btrfs_print_leaf(root, leaf);
2496                 printk("not enough freespace need %u have %d\n",
2497                        total_size, btrfs_leaf_free_space(root, leaf));
2498                 BUG();
2499         }
2500
2501         slot = path->slots[0];
2502         BUG_ON(slot < 0);
2503
2504         if (slot != nritems) {
2505                 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2506
2507                 if (old_data < data_end) {
2508                         btrfs_print_leaf(root, leaf);
2509                         printk("slot %d old_data %d data_end %d\n",
2510                                slot, old_data, data_end);
2511                         BUG_ON(1);
2512                 }
2513                 /*
2514                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
2515                  */
2516                 /* first correct the data pointers */
2517                 for (i = slot; i < nritems; i++) {
2518                         u32 ioff;
2519
2520                         item = btrfs_item_nr(i);
2521                         ioff = btrfs_item_offset(leaf, item);
2522                         btrfs_set_item_offset(leaf, item, ioff - total_data);
2523                 }
2524
2525                 /* shift the items */
2526                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
2527                               btrfs_item_nr_offset(slot),
2528                               (nritems - slot) * sizeof(struct btrfs_item));
2529
2530                 /* shift the data */
2531                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2532                               data_end - total_data, btrfs_leaf_data(leaf) +
2533                               data_end, old_data - data_end);
2534                 data_end = old_data;
2535         }
2536
2537         /* setup the item for the new data */
2538         for (i = 0; i < nr; i++) {
2539                 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
2540                 btrfs_set_item_key(leaf, &disk_key, slot + i);
2541                 item = btrfs_item_nr(slot + i);
2542                 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
2543                 data_end -= data_size[i];
2544                 btrfs_set_item_size(leaf, item, data_size[i]);
2545         }
2546         btrfs_set_header_nritems(leaf, nritems + nr);
2547         btrfs_mark_buffer_dirty(leaf);
2548
2549         ret = 0;
2550         if (slot == 0) {
2551                 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2552                 btrfs_fixup_low_keys(root, path, &disk_key, 1);
2553         }
2554
2555         if (btrfs_leaf_free_space(root, leaf) < 0) {
2556                 btrfs_print_leaf(root, leaf);
2557                 BUG();
2558         }
2559
2560 out:
2561         return ret;
2562 }
2563
2564 /*
2565  * Given a key and some data, insert an item into the tree.
2566  * This does all the path init required, making room in the tree if needed.
2567  */
2568 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2569                       *root, struct btrfs_key *cpu_key, void *data, u32
2570                       data_size)
2571 {
2572         int ret = 0;
2573         struct btrfs_path *path;
2574         struct extent_buffer *leaf;
2575         unsigned long ptr;
2576
2577         path = btrfs_alloc_path();
2578         BUG_ON(!path);
2579         ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2580         if (!ret) {
2581                 leaf = path->nodes[0];
2582                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2583                 write_extent_buffer(leaf, data, ptr, data_size);
2584                 btrfs_mark_buffer_dirty(leaf);
2585         }
2586         btrfs_free_path(path);
2587         return ret;
2588 }
2589
2590 /*
2591  * delete the pointer from a given node.
2592  *
2593  * If the delete empties a node, the node is removed from the tree,
2594  * continuing all the way the root if required.  The root is converted into
2595  * a leaf if all the nodes are emptied.
2596  */
2597 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2598                    struct btrfs_path *path, int level, int slot)
2599 {
2600         struct extent_buffer *parent = path->nodes[level];
2601         u32 nritems;
2602         int ret = 0;
2603
2604         nritems = btrfs_header_nritems(parent);
2605         if (slot != nritems -1) {
2606                 memmove_extent_buffer(parent,
2607                               btrfs_node_key_ptr_offset(slot),
2608                               btrfs_node_key_ptr_offset(slot + 1),
2609                               sizeof(struct btrfs_key_ptr) *
2610                               (nritems - slot - 1));
2611         }
2612         nritems--;
2613         btrfs_set_header_nritems(parent, nritems);
2614         if (nritems == 0 && parent == root->node) {
2615                 BUG_ON(btrfs_header_level(root->node) != 1);
2616                 /* just turn the root into a leaf and break */
2617                 btrfs_set_header_level(root->node, 0);
2618         } else if (slot == 0) {
2619                 struct btrfs_disk_key disk_key;
2620
2621                 btrfs_node_key(parent, &disk_key, 0);
2622                 btrfs_fixup_low_keys(root, path, &disk_key, level + 1);
2623         }
2624         btrfs_mark_buffer_dirty(parent);
2625         return ret;
2626 }
2627
2628 /*
2629  * a helper function to delete the leaf pointed to by path->slots[1] and
2630  * path->nodes[1].
2631  *
2632  * This deletes the pointer in path->nodes[1] and frees the leaf
2633  * block extent.  zero is returned if it all worked out, < 0 otherwise.
2634  *
2635  * The path must have already been setup for deleting the leaf, including
2636  * all the proper balancing.  path->nodes[1] must be locked.
2637  */
2638 static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
2639                                    struct btrfs_root *root,
2640                                    struct btrfs_path *path,
2641                                    struct extent_buffer *leaf)
2642 {
2643         int ret;
2644
2645         WARN_ON(btrfs_header_generation(leaf) != trans->transid);
2646         ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]);
2647         if (ret)
2648                 return ret;
2649
2650         ret = btrfs_free_extent(trans, root, leaf->start, leaf->len,
2651                                 0, root->root_key.objectid, 0, 0);
2652         return ret;
2653 }
2654
2655 /*
2656  * delete the item at the leaf level in path.  If that empties
2657  * the leaf, remove it from the tree
2658  */
2659 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2660                     struct btrfs_path *path, int slot, int nr)
2661 {
2662         struct extent_buffer *leaf;
2663         struct btrfs_item *item;
2664         int last_off;
2665         int dsize = 0;
2666         int ret = 0;
2667         int wret;
2668         int i;
2669         u32 nritems;
2670
2671         leaf = path->nodes[0];
2672         last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
2673
2674         for (i = 0; i < nr; i++)
2675                 dsize += btrfs_item_size_nr(leaf, slot + i);
2676
2677         nritems = btrfs_header_nritems(leaf);
2678
2679         if (slot + nr != nritems) {
2680                 int data_end = leaf_data_end(root, leaf);
2681
2682                 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2683                               data_end + dsize,
2684                               btrfs_leaf_data(leaf) + data_end,
2685                               last_off - data_end);
2686
2687                 for (i = slot + nr; i < nritems; i++) {
2688                         u32 ioff;
2689
2690                         item = btrfs_item_nr(i);
2691                         ioff = btrfs_item_offset(leaf, item);
2692                         btrfs_set_item_offset(leaf, item, ioff + dsize);
2693                 }
2694
2695                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2696                               btrfs_item_nr_offset(slot + nr),
2697                               sizeof(struct btrfs_item) *
2698                               (nritems - slot - nr));
2699         }
2700         btrfs_set_header_nritems(leaf, nritems - nr);
2701         nritems -= nr;
2702
2703         /* delete the leaf if we've emptied it */
2704         if (nritems == 0) {
2705                 if (leaf == root->node) {
2706                         btrfs_set_header_level(leaf, 0);
2707                 } else {
2708                         clean_tree_block(trans, root, leaf);
2709                         wait_on_tree_block_writeback(root, leaf);
2710
2711                         wret = btrfs_del_leaf(trans, root, path, leaf);
2712                         BUG_ON(ret);
2713                         if (wret)
2714                                 ret = wret;
2715                 }
2716         } else {
2717                 int used = leaf_space_used(leaf, 0, nritems);
2718                 if (slot == 0) {
2719                         struct btrfs_disk_key disk_key;
2720
2721                         btrfs_item_key(leaf, &disk_key, 0);
2722                         btrfs_fixup_low_keys(root, path, &disk_key, 1);
2723                 }
2724
2725                 /* delete the leaf if it is mostly empty */
2726                 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2727                         /* push_leaf_left fixes the path.
2728                          * make sure the path still points to our leaf
2729                          * for possible call to del_ptr below
2730                          */
2731                         slot = path->slots[1];
2732                         extent_buffer_get(leaf);
2733
2734                         wret = push_leaf_left(trans, root, path, 1, 1);
2735                         if (wret < 0 && wret != -ENOSPC)
2736                                 ret = wret;
2737
2738                         if (path->nodes[0] == leaf &&
2739                             btrfs_header_nritems(leaf)) {
2740                                 wret = push_leaf_right(trans, root, path, 1, 1);
2741                                 if (wret < 0 && wret != -ENOSPC)
2742                                         ret = wret;
2743                         }
2744
2745                         if (btrfs_header_nritems(leaf) == 0) {
2746                                 clean_tree_block(trans, root, leaf);
2747                                 wait_on_tree_block_writeback(root, leaf);
2748
2749                                 path->slots[1] = slot;
2750                                 ret = btrfs_del_leaf(trans, root, path, leaf);
2751                                 BUG_ON(ret);
2752                                 free_extent_buffer(leaf);
2753
2754                         } else {
2755                                 btrfs_mark_buffer_dirty(leaf);
2756                                 free_extent_buffer(leaf);
2757                         }
2758                 } else {
2759                         btrfs_mark_buffer_dirty(leaf);
2760                 }
2761         }
2762         return ret;
2763 }
2764
2765 /*
2766  * walk up the tree as far as required to find the previous leaf.
2767  * returns 0 if it found something or 1 if there are no lesser leaves.
2768  * returns < 0 on io errors.
2769  */
2770 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2771 {
2772         int slot;
2773         int level = 1;
2774         struct extent_buffer *c;
2775         struct extent_buffer *next = NULL;
2776
2777         while(level < BTRFS_MAX_LEVEL) {
2778                 if (!path->nodes[level])
2779                         return 1;
2780
2781                 slot = path->slots[level];
2782                 c = path->nodes[level];
2783                 if (slot == 0) {
2784                         level++;
2785                         if (level == BTRFS_MAX_LEVEL)
2786                                 return 1;
2787                         continue;
2788                 }
2789                 slot--;
2790
2791                 next = read_node_slot(root, c, slot);
2792                 if (!extent_buffer_uptodate(next)) {
2793                         if (IS_ERR(next))
2794                                 return PTR_ERR(next);
2795                         return -EIO;
2796                 }
2797                 break;
2798         }
2799         path->slots[level] = slot;
2800         while(1) {
2801                 level--;
2802                 c = path->nodes[level];
2803                 free_extent_buffer(c);
2804                 slot = btrfs_header_nritems(next);
2805                 if (slot != 0)
2806                         slot--;
2807                 path->nodes[level] = next;
2808                 path->slots[level] = slot;
2809                 if (!level)
2810                         break;
2811                 next = read_node_slot(root, next, slot);
2812                 if (!extent_buffer_uptodate(next)) {
2813                         if (IS_ERR(next))
2814                                 return PTR_ERR(next);
2815                         return -EIO;
2816                 }
2817         }
2818         return 0;
2819 }
2820
2821 /*
2822  * walk up the tree as far as required to find the next leaf.
2823  * returns 0 if it found something or 1 if there are no greater leaves.
2824  * returns < 0 on io errors.
2825  */
2826 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2827 {
2828         int slot;
2829         int level = 1;
2830         struct extent_buffer *c;
2831         struct extent_buffer *next = NULL;
2832
2833         while(level < BTRFS_MAX_LEVEL) {
2834                 if (!path->nodes[level])
2835                         return 1;
2836
2837                 slot = path->slots[level] + 1;
2838                 c = path->nodes[level];
2839                 if (slot >= btrfs_header_nritems(c)) {
2840                         level++;
2841                         if (level == BTRFS_MAX_LEVEL)
2842                                 return 1;
2843                         continue;
2844                 }
2845
2846                 if (path->reada)
2847                         reada_for_search(root, path, level, slot, 0);
2848
2849                 next = read_node_slot(root, c, slot);
2850                 if (!extent_buffer_uptodate(next))
2851                         return -EIO;
2852                 break;
2853         }
2854         path->slots[level] = slot;
2855         while(1) {
2856                 level--;
2857                 c = path->nodes[level];
2858                 free_extent_buffer(c);
2859                 path->nodes[level] = next;
2860                 path->slots[level] = 0;
2861                 if (!level)
2862                         break;
2863                 if (path->reada)
2864                         reada_for_search(root, path, level, 0, 0);
2865                 next = read_node_slot(root, next, 0);
2866                 if (!extent_buffer_uptodate(next))
2867                         return -EIO;
2868         }
2869         return 0;
2870 }
2871
2872 int btrfs_previous_item(struct btrfs_root *root,
2873                         struct btrfs_path *path, u64 min_objectid,
2874                         int type)
2875 {
2876         struct btrfs_key found_key;
2877         struct extent_buffer *leaf;
2878         int ret;
2879
2880         while(1) {
2881                 if (path->slots[0] == 0) {
2882                         ret = btrfs_prev_leaf(root, path);
2883                         if (ret != 0)
2884                                 return ret;
2885                 } else {
2886                         path->slots[0]--;
2887                 }
2888                 leaf = path->nodes[0];
2889                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2890                 if (found_key.type == type)
2891                         return 0;
2892         }
2893         return 1;
2894 }
2895
2896 /*
2897  * search in extent tree to find a previous Metadata/Data extent item with
2898  * min objecitd.
2899  *
2900  * returns 0 if something is found, 1 if nothing was found and < 0 on error
2901  */
2902 int btrfs_previous_extent_item(struct btrfs_root *root,
2903                         struct btrfs_path *path, u64 min_objectid)
2904 {
2905         struct btrfs_key found_key;
2906         struct extent_buffer *leaf;
2907         u32 nritems;
2908         int ret;
2909
2910         while (1) {
2911                 if (path->slots[0] == 0) {
2912                         ret = btrfs_prev_leaf(root, path);
2913                         if (ret != 0)
2914                                 return ret;
2915                 } else {
2916                         path->slots[0]--;
2917                 }
2918                 leaf = path->nodes[0];
2919                 nritems = btrfs_header_nritems(leaf);
2920                 if (nritems == 0)
2921                         return 1;
2922                 if (path->slots[0] == nritems)
2923                         path->slots[0]--;
2924
2925                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2926                 if (found_key.objectid < min_objectid)
2927                         break;
2928                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
2929                     found_key.type == BTRFS_METADATA_ITEM_KEY)
2930                         return 0;
2931                 if (found_key.objectid == min_objectid &&
2932                     found_key.type < BTRFS_EXTENT_ITEM_KEY)
2933                         break;
2934         }
2935         return 1;
2936 }