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