git.oblomov.eu Git - linux-2.6/blob - fs/btrfs/ctree.c

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