fs/btrfs/ctree.c

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