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