ctree.c

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