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