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