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