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

   1 #include <linux/module.h>
   2 #include "ctree.h"
   3 #include "disk-io.h"
   4 #include "transaction.h"
   5
   6 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
   7                       *root, struct btrfs_path *path, int level);
   8 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
   9                       *root, struct btrfs_key *ins_key,
  10                       struct btrfs_path *path, int data_size);
  11 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
  12                           *root, struct buffer_head *dst, struct buffer_head
  13                           *src);
  14 static int balance_node_right(struct btrfs_trans_handle *trans, struct
  15                               btrfs_root *root, struct buffer_head *dst_buf,
  16                               struct buffer_head *src_buf);
  17 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  18                    struct btrfs_path *path, int level, int slot);
  19
  20 inline void btrfs_init_path(struct btrfs_path *p)
  21 {
  22         memset(p, 0, sizeof(*p));
  23 }
  24
  25 struct btrfs_path *btrfs_alloc_path(void)
  26 {
  27         struct btrfs_path *path;
  28         path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
  29         if (path)
  30                 btrfs_init_path(path);
  31         return path;
  32 }
  33
  34 void btrfs_free_path(struct btrfs_path *p)
  35 {
  36         btrfs_release_path(NULL, p);
  37         kmem_cache_free(btrfs_path_cachep, p);
  38 }
  39
  40 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
  41 {
  42         int i;
  43         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  44                 if (!p->nodes[i])
  45                         break;
  46                 btrfs_block_release(root, p->nodes[i]);
  47         }
  48         memset(p, 0, sizeof(*p));
  49 }
  50
  51 static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root
  52                            *root, struct buffer_head *buf, struct buffer_head
  53                            *parent, int parent_slot, struct buffer_head
  54                            **cow_ret)
  55 {
  56         struct buffer_head *cow;
  57         struct btrfs_node *cow_node;
  58
  59         if (btrfs_header_generation(btrfs_buffer_header(buf)) ==
  60                                     trans->transid) {
  61                 *cow_ret = buf;
  62                 return 0;
  63         }
  64         cow = btrfs_alloc_free_block(trans, root);
  65         cow_node = btrfs_buffer_node(cow);
  66         if (buf->b_size != root->blocksize || cow->b_size != root->blocksize)
  67                 WARN_ON(1);
  68         memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize);
  69         btrfs_set_header_blocknr(&cow_node->header, cow->b_blocknr);
  70         btrfs_set_header_generation(&cow_node->header, trans->transid);
  71         btrfs_inc_ref(trans, root, buf);
  72         if (buf == root->node) {
  73                 root->node = cow;
  74                 get_bh(cow);
  75                 if (buf != root->commit_root) {
  76                         btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1);
  77                 }
  78                 btrfs_block_release(root, buf);
  79         } else {
  80                 btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot,
  81                                         cow->b_blocknr);
  82                 btrfs_mark_buffer_dirty(parent);
  83                 btrfs_free_extent(trans, root, buf->b_blocknr, 1, 1);
  84         }
  85         btrfs_block_release(root, buf);
  86         mark_buffer_dirty(cow);
  87         *cow_ret = cow;
  88         return 0;
  89 }
  90
  91 /*
  92  * The leaf data grows from end-to-front in the node.
  93  * this returns the address of the start of the last item,
  94  * which is the stop of the leaf data stack
  95  */
  96 static inline unsigned int leaf_data_end(struct btrfs_root *root,
  97                                          struct btrfs_leaf *leaf)
  98 {
  99         u32 nr = btrfs_header_nritems(&leaf->header);
 100         if (nr == 0)
 101                 return BTRFS_LEAF_DATA_SIZE(root);
 102         return btrfs_item_offset(leaf->items + nr - 1);
 103 }
 104
 105 /*
 106  * compare two keys in a memcmp fashion
 107  */
 108 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
 109 {
 110         struct btrfs_key k1;
 111
 112         btrfs_disk_key_to_cpu(&k1, disk);
 113
 114         if (k1.objectid > k2->objectid)
 115                 return 1;
 116         if (k1.objectid < k2->objectid)
 117                 return -1;
 118         if (k1.offset > k2->offset)
 119                 return 1;
 120         if (k1.offset < k2->offset)
 121                 return -1;
 122         if (k1.flags > k2->flags)
 123                 return 1;
 124         if (k1.flags < k2->flags)
 125                 return -1;
 126         return 0;
 127 }
 128
 129 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
 130                       int level)
 131 {
 132         int i;
 133         struct btrfs_node *parent = NULL;
 134         struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]);
 135         int parent_slot;
 136         u32 nritems = btrfs_header_nritems(&node->header);
 137
 138         if (path->nodes[level + 1])
 139                 parent = btrfs_buffer_node(path->nodes[level + 1]);
 140         parent_slot = path->slots[level + 1];
 141         BUG_ON(nritems == 0);
 142         if (parent) {
 143                 struct btrfs_disk_key *parent_key;
 144                 parent_key = &parent->ptrs[parent_slot].key;
 145                 BUG_ON(memcmp(parent_key, &node->ptrs[0].key,
 146                               sizeof(struct btrfs_disk_key)));
 147                 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
 148                        btrfs_header_blocknr(&node->header));
 149         }
 150         BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
 151         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 152                 struct btrfs_key cpukey;
 153                 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
 154                 BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0);
 155         }
 156         return 0;
 157 }
 158
 159 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
 160                       int level)
 161 {
 162         int i;
 163         struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]);
 164         struct btrfs_node *parent = NULL;
 165         int parent_slot;
 166         u32 nritems = btrfs_header_nritems(&leaf->header);
 167
 168         if (path->nodes[level + 1])
 169                 parent = btrfs_buffer_node(path->nodes[level + 1]);
 170         parent_slot = path->slots[level + 1];
 171         BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
 172
 173         if (nritems == 0)
 174                 return 0;
 175
 176         if (parent) {
 177                 struct btrfs_disk_key *parent_key;
 178                 parent_key = &parent->ptrs[parent_slot].key;
 179                 BUG_ON(memcmp(parent_key, &leaf->items[0].key,
 180                        sizeof(struct btrfs_disk_key)));
 181                 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
 182                        btrfs_header_blocknr(&leaf->header));
 183         }
 184         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 185                 struct btrfs_key cpukey;
 186                 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
 187                 BUG_ON(comp_keys(&leaf->items[i].key,
 188                                  &cpukey) >= 0);
 189                 BUG_ON(btrfs_item_offset(leaf->items + i) !=
 190                         btrfs_item_end(leaf->items + i + 1));
 191                 if (i == 0) {
 192                         BUG_ON(btrfs_item_offset(leaf->items + i) +
 193                                btrfs_item_size(leaf->items + i) !=
 194                                BTRFS_LEAF_DATA_SIZE(root));
 195                 }
 196         }
 197         return 0;
 198 }
 199
 200 static int check_block(struct btrfs_root *root, struct btrfs_path *path,
 201                         int level)
 202 {
 203         if (level == 0)
 204                 return check_leaf(root, path, level);
 205         return check_node(root, path, level);
 206 }
 207
 208 /*
 209  * search for key in the array p.  items p are item_size apart
 210  * and there are 'max' items in p
 211  * the slot in the array is returned via slot, and it points to
 212  * the place where you would insert key if it is not found in
 213  * the array.
 214  *
 215  * slot may point to max if the key is bigger than all of the keys
 216  */
 217 static int generic_bin_search(char *p, int item_size, struct btrfs_key *key,
 218                        int max, int *slot)
 219 {
 220         int low = 0;
 221         int high = max;
 222         int mid;
 223         int ret;
 224         struct btrfs_disk_key *tmp;
 225
 226         while(low < high) {
 227                 mid = (low + high) / 2;
 228                 tmp = (struct btrfs_disk_key *)(p + mid * item_size);
 229                 ret = comp_keys(tmp, key);
 230
 231                 if (ret < 0)
 232                         low = mid + 1;
 233                 else if (ret > 0)
 234                         high = mid;
 235                 else {
 236                         *slot = mid;
 237                         return 0;
 238                 }
 239         }
 240         *slot = low;
 241         return 1;
 242 }
 243
 244 /*
 245  * simple bin_search frontend that does the right thing for
 246  * leaves vs nodes
 247  */
 248 static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot)
 249 {
 250         if (btrfs_is_leaf(c)) {
 251                 struct btrfs_leaf *l = (struct btrfs_leaf *)c;
 252                 return generic_bin_search((void *)l->items,
 253                                           sizeof(struct btrfs_item),
 254                                           key, btrfs_header_nritems(&c->header),
 255                                           slot);
 256         } else {
 257                 return generic_bin_search((void *)c->ptrs,
 258                                           sizeof(struct btrfs_key_ptr),
 259                                           key, btrfs_header_nritems(&c->header),
 260                                           slot);
 261         }
 262         return -1;
 263 }
 264
 265 static struct buffer_head *read_node_slot(struct btrfs_root *root,
 266                                    struct buffer_head *parent_buf,
 267                                    int slot)
 268 {
 269         struct btrfs_node *node = btrfs_buffer_node(parent_buf);
 270         if (slot < 0)
 271                 return NULL;
 272         if (slot >= btrfs_header_nritems(&node->header))
 273                 return NULL;
 274         return read_tree_block(root, btrfs_node_blockptr(node, slot));
 275 }
 276
 277 static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 278                          *root, struct btrfs_path *path, int level)
 279 {
 280         struct buffer_head *right_buf;
 281         struct buffer_head *mid_buf;
 282         struct buffer_head *left_buf;
 283         struct buffer_head *parent_buf = NULL;
 284         struct btrfs_node *right = NULL;
 285         struct btrfs_node *mid;
 286         struct btrfs_node *left = NULL;
 287         struct btrfs_node *parent = NULL;
 288         int ret = 0;
 289         int wret;
 290         int pslot;
 291         int orig_slot = path->slots[level];
 292         u64 orig_ptr;
 293
 294         if (level == 0)
 295                 return 0;
 296
 297         mid_buf = path->nodes[level];
 298         mid = btrfs_buffer_node(mid_buf);
 299         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
 300
 301         if (level < BTRFS_MAX_LEVEL - 1)
 302                 parent_buf = path->nodes[level + 1];
 303         pslot = path->slots[level + 1];
 304
 305         /*
 306          * deal with the case where there is only one pointer in the root
 307          * by promoting the node below to a root
 308          */
 309         if (!parent_buf) {
 310                 struct buffer_head *child;
 311                 u64 blocknr = mid_buf->b_blocknr;
 312
 313                 if (btrfs_header_nritems(&mid->header) != 1)
 314                         return 0;
 315
 316                 /* promote the child to a root */
 317                 child = read_node_slot(root, mid_buf, 0);
 318                 BUG_ON(!child);
 319                 root->node = child;
 320                 path->nodes[level] = NULL;
 321                 clean_tree_block(trans, root, mid_buf);
 322                 wait_on_buffer(mid_buf);
 323                 /* once for the path */
 324                 btrfs_block_release(root, mid_buf);
 325                 /* once for the root ptr */
 326                 btrfs_block_release(root, mid_buf);
 327                 return btrfs_free_extent(trans, root, blocknr, 1, 1);
 328         }
 329         parent = btrfs_buffer_node(parent_buf);
 330
 331         if (btrfs_header_nritems(&mid->header) >
 332             BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
 333                 return 0;
 334
 335         left_buf = read_node_slot(root, parent_buf, pslot - 1);
 336         right_buf = read_node_slot(root, parent_buf, pslot + 1);
 337
 338         /* first, try to make some room in the middle buffer */
 339         if (left_buf) {
 340                 btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1,
 341                                 &left_buf);
 342                 left = btrfs_buffer_node(left_buf);
 343                 orig_slot += btrfs_header_nritems(&left->header);
 344                 wret = push_node_left(trans, root, left_buf, mid_buf);
 345                 if (wret < 0)
 346                         ret = wret;
 347         }
 348
 349         /*
 350          * then try to empty the right most buffer into the middle
 351          */
 352         if (right_buf) {
 353                 btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1,
 354                                 &right_buf);
 355                 right = btrfs_buffer_node(right_buf);
 356                 wret = push_node_left(trans, root, mid_buf, right_buf);
 357                 if (wret < 0)
 358                         ret = wret;
 359                 if (btrfs_header_nritems(&right->header) == 0) {
 360                         u64 blocknr = right_buf->b_blocknr;
 361                         clean_tree_block(trans, root, right_buf);
 362                         wait_on_buffer(right_buf);
 363                         btrfs_block_release(root, right_buf);
 364                         right_buf = NULL;
 365                         right = NULL;
 366                         wret = del_ptr(trans, root, path, level + 1, pslot +
 367                                        1);
 368                         if (wret)
 369                                 ret = wret;
 370                         wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 371                         if (wret)
 372                                 ret = wret;
 373                 } else {
 374                         btrfs_memcpy(root, parent,
 375                                      &parent->ptrs[pslot + 1].key,
 376                                      &right->ptrs[0].key,
 377                                      sizeof(struct btrfs_disk_key));
 378                         btrfs_mark_buffer_dirty(parent_buf);
 379                 }
 380         }
 381         if (btrfs_header_nritems(&mid->header) == 1) {
 382                 /*
 383                  * we're not allowed to leave a node with one item in the
 384                  * tree during a delete.  A deletion from lower in the tree
 385                  * could try to delete the only pointer in this node.
 386                  * So, pull some keys from the left.
 387                  * There has to be a left pointer at this point because
 388                  * otherwise we would have pulled some pointers from the
 389                  * right
 390                  */
 391                 BUG_ON(!left_buf);
 392                 wret = balance_node_right(trans, root, mid_buf, left_buf);
 393                 if (wret < 0)
 394                         ret = wret;
 395                 BUG_ON(wret == 1);
 396         }
 397         if (btrfs_header_nritems(&mid->header) == 0) {
 398                 /* we've managed to empty the middle node, drop it */
 399                 u64 blocknr = mid_buf->b_blocknr;
 400                 clean_tree_block(trans, root, mid_buf);
 401                 wait_on_buffer(mid_buf);
 402                 btrfs_block_release(root, mid_buf);
 403                 mid_buf = NULL;
 404                 mid = NULL;
 405                 wret = del_ptr(trans, root, path, level + 1, pslot);
 406                 if (wret)
 407                         ret = wret;
 408                 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
 409                 if (wret)
 410                         ret = wret;
 411         } else {
 412                 /* update the parent key to reflect our changes */
 413                 btrfs_memcpy(root, parent,
 414                              &parent->ptrs[pslot].key, &mid->ptrs[0].key,
 415                              sizeof(struct btrfs_disk_key));
 416                 btrfs_mark_buffer_dirty(parent_buf);
 417         }
 418
 419         /* update the path */
 420         if (left_buf) {
 421                 if (btrfs_header_nritems(&left->header) > orig_slot) {
 422                         get_bh(left_buf);
 423                         path->nodes[level] = left_buf;
 424                         path->slots[level + 1] -= 1;
 425                         path->slots[level] = orig_slot;
 426                         if (mid_buf)
 427                                 btrfs_block_release(root, mid_buf);
 428                 } else {
 429                         orig_slot -= btrfs_header_nritems(&left->header);
 430                         path->slots[level] = orig_slot;
 431                 }
 432         }
 433         /* double check we haven't messed things up */
 434         check_block(root, path, level);
 435         if (orig_ptr !=
 436             btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]),
 437                                 path->slots[level]))
 438                 BUG();
 439
 440         if (right_buf)
 441                 btrfs_block_release(root, right_buf);
 442         if (left_buf)
 443                 btrfs_block_release(root, left_buf);
 444         return ret;
 445 }
 446
 447 /*
 448  * look for key in the tree.  path is filled in with nodes along the way
 449  * if key is found, we return zero and you can find the item in the leaf
 450  * level of the path (level 0)
 451  *
 452  * If the key isn't found, the path points to the slot where it should
 453  * be inserted, and 1 is returned.  If there are other errors during the
 454  * search a negative error number is returned.
 455  *
 456  * if ins_len > 0, nodes and leaves will be split as we walk down the
 457  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
 458  * possible)
 459  */
 460 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
 461                       *root, struct btrfs_key *key, struct btrfs_path *p, int
 462                       ins_len, int cow)
 463 {
 464         struct buffer_head *b;
 465         struct buffer_head *cow_buf;
 466         struct btrfs_node *c;
 467         int slot;
 468         int ret;
 469         int level;
 470
 471         WARN_ON(p->nodes[0] != NULL);
 472         WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
 473 again:
 474         b = root->node;
 475         get_bh(b);
 476         while (b) {
 477                 c = btrfs_buffer_node(b);
 478                 level = btrfs_header_level(&c->header);
 479                 if (cow) {
 480                         int wret;
 481                         wret = btrfs_cow_block(trans, root, b,
 482                                                p->nodes[level + 1],
 483                                                p->slots[level + 1],
 484                                                &cow_buf);
 485                         b = cow_buf;
 486                         c = btrfs_buffer_node(b);
 487                 }
 488                 BUG_ON(!cow && ins_len);
 489                 if (level != btrfs_header_level(&c->header))
 490                         WARN_ON(1);
 491                 level = btrfs_header_level(&c->header);
 492                 p->nodes[level] = b;
 493                 ret = check_block(root, p, level);
 494                 if (ret)
 495                         return -1;
 496                 ret = bin_search(c, key, &slot);
 497                 if (!btrfs_is_leaf(c)) {
 498                         if (ret && slot > 0)
 499                                 slot -= 1;
 500                         p->slots[level] = slot;
 501                         if (ins_len > 0 && btrfs_header_nritems(&c->header) >=
 502                             BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
 503                                 int sret = split_node(trans, root, p, level);
 504                                 BUG_ON(sret > 0);
 505                                 if (sret)
 506                                         return sret;
 507                                 b = p->nodes[level];
 508                                 c = btrfs_buffer_node(b);
 509                                 slot = p->slots[level];
 510                         } else if (ins_len < 0) {
 511                                 int sret = balance_level(trans, root, p,
 512                                                          level);
 513                                 if (sret)
 514                                         return sret;
 515                                 b = p->nodes[level];
 516                                 if (!b)
 517                                         goto again;
 518                                 c = btrfs_buffer_node(b);
 519                                 slot = p->slots[level];
 520                                 BUG_ON(btrfs_header_nritems(&c->header) == 1);
 521                         }
 522                         b = read_tree_block(root, btrfs_node_blockptr(c, slot));
 523                 } else {
 524                         struct btrfs_leaf *l = (struct btrfs_leaf *)c;
 525                         p->slots[level] = slot;
 526                         if (ins_len > 0 && btrfs_leaf_free_space(root, l) <
 527                             sizeof(struct btrfs_item) + ins_len) {
 528                                 int sret = split_leaf(trans, root, key,
 529                                                       p, ins_len);
 530                                 BUG_ON(sret > 0);
 531                                 if (sret)
 532                                         return sret;
 533                         }
 534                         return ret;
 535                 }
 536         }
 537         return 1;
 538 }
 539
 540 /*
 541  * adjust the pointers going up the tree, starting at level
 542  * making sure the right key of each node is points to 'key'.
 543  * This is used after shifting pointers to the left, so it stops
 544  * fixing up pointers when a given leaf/node is not in slot 0 of the
 545  * higher levels
 546  *
 547  * If this fails to write a tree block, it returns -1, but continues
 548  * fixing up the blocks in ram so the tree is consistent.
 549  */
 550 static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root
 551                           *root, struct btrfs_path *path, struct btrfs_disk_key
 552                           *key, int level)
 553 {
 554         int i;
 555         int ret = 0;
 556         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
 557                 struct btrfs_node *t;
 558                 int tslot = path->slots[i];
 559                 if (!path->nodes[i])
 560                         break;
 561                 t = btrfs_buffer_node(path->nodes[i]);
 562                 btrfs_memcpy(root, t, &t->ptrs[tslot].key, key, sizeof(*key));
 563                 btrfs_mark_buffer_dirty(path->nodes[i]);
 564                 if (tslot != 0)
 565                         break;
 566         }
 567         return ret;
 568 }
 569
 570 /*
 571  * try to push data from one node into the next node left in the
 572  * tree.
 573  *
 574  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
 575  * error, and > 0 if there was no room in the left hand block.
 576  */
 577 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
 578                           *root, struct buffer_head *dst_buf, struct
 579                           buffer_head *src_buf)
 580 {
 581         struct btrfs_node *src = btrfs_buffer_node(src_buf);
 582         struct btrfs_node *dst = btrfs_buffer_node(dst_buf);
 583         int push_items = 0;
 584         int src_nritems;
 585         int dst_nritems;
 586         int ret = 0;
 587
 588         src_nritems = btrfs_header_nritems(&src->header);
 589         dst_nritems = btrfs_header_nritems(&dst->header);
 590         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
 591         if (push_items <= 0) {
 592                 return 1;
 593         }
 594
 595         if (src_nritems < push_items)
 596                 push_items = src_nritems;
 597
 598         btrfs_memcpy(root, dst, dst->ptrs + dst_nritems, src->ptrs,
 599                      push_items * sizeof(struct btrfs_key_ptr));
 600         if (push_items < src_nritems) {
 601                 btrfs_memmove(root, src, src->ptrs, src->ptrs + push_items,
 602                         (src_nritems - push_items) *
 603                         sizeof(struct btrfs_key_ptr));
 604         }
 605         btrfs_set_header_nritems(&src->header, src_nritems - push_items);
 606         btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
 607         btrfs_mark_buffer_dirty(src_buf);
 608         btrfs_mark_buffer_dirty(dst_buf);
 609         return ret;
 610 }
 611
 612 /*
 613  * try to push data from one node into the next node right in the
 614  * tree.
 615  *
 616  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
 617  * error, and > 0 if there was no room in the right hand block.
 618  *
 619  * this will  only push up to 1/2 the contents of the left node over
 620  */
 621 static int balance_node_right(struct btrfs_trans_handle *trans, struct
 622                               btrfs_root *root, struct buffer_head *dst_buf,
 623                               struct buffer_head *src_buf)
 624 {
 625         struct btrfs_node *src = btrfs_buffer_node(src_buf);
 626         struct btrfs_node *dst = btrfs_buffer_node(dst_buf);
 627         int push_items = 0;
 628         int max_push;
 629         int src_nritems;
 630         int dst_nritems;
 631         int ret = 0;
 632
 633         src_nritems = btrfs_header_nritems(&src->header);
 634         dst_nritems = btrfs_header_nritems(&dst->header);
 635         push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
 636         if (push_items <= 0) {
 637                 return 1;
 638         }
 639
 640         max_push = src_nritems / 2 + 1;
 641         /* don't try to empty the node */
 642         if (max_push > src_nritems)
 643                 return 1;
 644         if (max_push < push_items)
 645                 push_items = max_push;
 646
 647         btrfs_memmove(root, dst, dst->ptrs + push_items, dst->ptrs,
 648                       dst_nritems * sizeof(struct btrfs_key_ptr));
 649
 650         btrfs_memcpy(root, dst, dst->ptrs,
 651                      src->ptrs + src_nritems - push_items,
 652                      push_items * sizeof(struct btrfs_key_ptr));
 653
 654         btrfs_set_header_nritems(&src->header, src_nritems - push_items);
 655         btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
 656
 657         btrfs_mark_buffer_dirty(src_buf);
 658         btrfs_mark_buffer_dirty(dst_buf);
 659         return ret;
 660 }
 661
 662 /*
 663  * helper function to insert a new root level in the tree.
 664  * A new node is allocated, and a single item is inserted to
 665  * point to the existing root
 666  *
 667  * returns zero on success or < 0 on failure.
 668  */
 669 static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root
 670                            *root, struct btrfs_path *path, int level)
 671 {
 672         struct buffer_head *t;
 673         struct btrfs_node *lower;
 674         struct btrfs_node *c;
 675         struct btrfs_disk_key *lower_key;
 676
 677         BUG_ON(path->nodes[level]);
 678         BUG_ON(path->nodes[level-1] != root->node);
 679
 680         t = btrfs_alloc_free_block(trans, root);
 681         c = btrfs_buffer_node(t);
 682         memset(c, 0, root->blocksize);
 683         btrfs_set_header_nritems(&c->header, 1);
 684         btrfs_set_header_level(&c->header, level);
 685         btrfs_set_header_blocknr(&c->header, t->b_blocknr);
 686         btrfs_set_header_generation(&c->header, trans->transid);
 687         btrfs_set_header_parentid(&c->header,
 688               btrfs_header_parentid(btrfs_buffer_header(root->node)));
 689         lower = btrfs_buffer_node(path->nodes[level-1]);
 690         if (btrfs_is_leaf(lower))
 691                 lower_key = &((struct btrfs_leaf *)lower)->items[0].key;
 692         else
 693                 lower_key = &lower->ptrs[0].key;
 694         btrfs_memcpy(root, c, &c->ptrs[0].key, lower_key,
 695                      sizeof(struct btrfs_disk_key));
 696         btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->b_blocknr);
 697
 698         btrfs_mark_buffer_dirty(t);
 699
 700         /* the super has an extra ref to root->node */
 701         btrfs_block_release(root, root->node);
 702         root->node = t;
 703         get_bh(t);
 704         path->nodes[level] = t;
 705         path->slots[level] = 0;
 706         return 0;
 707 }
 708
 709 /*
 710  * worker function to insert a single pointer in a node.
 711  * the node should have enough room for the pointer already
 712  *
 713  * slot and level indicate where you want the key to go, and
 714  * blocknr is the block the key points to.
 715  *
 716  * returns zero on success and < 0 on any error
 717  */
 718 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
 719                       *root, struct btrfs_path *path, struct btrfs_disk_key
 720                       *key, u64 blocknr, int slot, int level)
 721 {
 722         struct btrfs_node *lower;
 723         int nritems;
 724
 725         BUG_ON(!path->nodes[level]);
 726         lower = btrfs_buffer_node(path->nodes[level]);
 727         nritems = btrfs_header_nritems(&lower->header);
 728         if (slot > nritems)
 729                 BUG();
 730         if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
 731                 BUG();
 732         if (slot != nritems) {
 733                 btrfs_memmove(root, lower, lower->ptrs + slot + 1,
 734                               lower->ptrs + slot,
 735                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
 736         }
 737         btrfs_memcpy(root, lower, &lower->ptrs[slot].key,
 738                      key, sizeof(struct btrfs_disk_key));
 739         btrfs_set_node_blockptr(lower, slot, blocknr);
 740         btrfs_set_header_nritems(&lower->header, nritems + 1);
 741         btrfs_mark_buffer_dirty(path->nodes[level]);
 742         return 0;
 743 }
 744
 745 /*
 746  * split the node at the specified level in path in two.
 747  * The path is corrected to point to the appropriate node after the split
 748  *
 749  * Before splitting this tries to make some room in the node by pushing
 750  * left and right, if either one works, it returns right away.
 751  *
 752  * returns 0 on success and < 0 on failure
 753  */
 754 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 755                       *root, struct btrfs_path *path, int level)
 756 {
 757         struct buffer_head *t;
 758         struct btrfs_node *c;
 759         struct buffer_head *split_buffer;
 760         struct btrfs_node *split;
 761         int mid;
 762         int ret;
 763         int wret;
 764         u32 c_nritems;
 765
 766         t = path->nodes[level];
 767         c = btrfs_buffer_node(t);
 768         if (t == root->node) {
 769                 /* trying to split the root, lets make a new one */
 770                 ret = insert_new_root(trans, root, path, level + 1);
 771                 if (ret)
 772                         return ret;
 773         }
 774         c_nritems = btrfs_header_nritems(&c->header);
 775         split_buffer = btrfs_alloc_free_block(trans, root);
 776         split = btrfs_buffer_node(split_buffer);
 777         btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
 778         btrfs_set_header_level(&split->header, btrfs_header_level(&c->header));
 779         btrfs_set_header_blocknr(&split->header, split_buffer->b_blocknr);
 780         btrfs_set_header_generation(&split->header, trans->transid);
 781         btrfs_set_header_parentid(&split->header,
 782               btrfs_header_parentid(btrfs_buffer_header(root->node)));
 783         mid = (c_nritems + 1) / 2;
 784         btrfs_memcpy(root, split, split->ptrs, c->ptrs + mid,
 785                      (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
 786         btrfs_set_header_nritems(&split->header, c_nritems - mid);
 787         btrfs_set_header_nritems(&c->header, mid);
 788         ret = 0;
 789
 790         btrfs_mark_buffer_dirty(t);
 791         btrfs_mark_buffer_dirty(split_buffer);
 792         wret = insert_ptr(trans, root, path, &split->ptrs[0].key,
 793                           split_buffer->b_blocknr, path->slots[level + 1] + 1,
 794                           level + 1);
 795         if (wret)
 796                 ret = wret;
 797
 798         if (path->slots[level] >= mid) {
 799                 path->slots[level] -= mid;
 800                 btrfs_block_release(root, t);
 801                 path->nodes[level] = split_buffer;
 802                 path->slots[level + 1] += 1;
 803         } else {
 804                 btrfs_block_release(root, split_buffer);
 805         }
 806         return ret;
 807 }
 808
 809 /*
 810  * how many bytes are required to store the items in a leaf.  start
 811  * and nr indicate which items in the leaf to check.  This totals up the
 812  * space used both by the item structs and the item data
 813  */
 814 static int leaf_space_used(struct btrfs_leaf *l, int start, int nr)
 815 {
 816         int data_len;
 817         int nritems = btrfs_header_nritems(&l->header);
 818         int end = min(nritems, start + nr) - 1;
 819
 820         if (!nr)
 821                 return 0;
 822         data_len = btrfs_item_end(l->items + start);
 823         data_len = data_len - btrfs_item_offset(l->items + end);
 824         data_len += sizeof(struct btrfs_item) * nr;
 825         WARN_ON(data_len < 0);
 826         return data_len;
 827 }
 828
 829 /*
 830  * The space between the end of the leaf items and
 831  * the start of the leaf data.  IOW, how much room
 832  * the leaf has left for both items and data
 833  */
 834 int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf)
 835 {
 836         int nritems = btrfs_header_nritems(&leaf->header);
 837         return BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
 838 }
 839
 840 /*
 841  * push some data in the path leaf to the right, trying to free up at
 842  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 843  *
 844  * returns 1 if the push failed because the other node didn't have enough
 845  * room, 0 if everything worked out and < 0 if there were major errors.
 846  */
 847 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
 848                            *root, struct btrfs_path *path, int data_size)
 849 {
 850         struct buffer_head *left_buf = path->nodes[0];
 851         struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf);
 852         struct btrfs_leaf *right;
 853         struct buffer_head *right_buf;
 854         struct buffer_head *upper;
 855         struct btrfs_node *upper_node;
 856         int slot;
 857         int i;
 858         int free_space;
 859         int push_space = 0;
 860         int push_items = 0;
 861         struct btrfs_item *item;
 862         u32 left_nritems;
 863         u32 right_nritems;
 864
 865         slot = path->slots[1];
 866         if (!path->nodes[1]) {
 867                 return 1;
 868         }
 869         upper = path->nodes[1];
 870         upper_node = btrfs_buffer_node(upper);
 871         if (slot >= btrfs_header_nritems(&upper_node->header) - 1) {
 872                 return 1;
 873         }
 874         right_buf = read_tree_block(root,
 875                     btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1));
 876         right = btrfs_buffer_leaf(right_buf);
 877         free_space = btrfs_leaf_free_space(root, right);
 878         if (free_space < data_size + sizeof(struct btrfs_item)) {
 879                 btrfs_block_release(root, right_buf);
 880                 return 1;
 881         }
 882         /* cow and double check */
 883         btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf);
 884         right = btrfs_buffer_leaf(right_buf);
 885         free_space = btrfs_leaf_free_space(root, right);
 886         if (free_space < data_size + sizeof(struct btrfs_item)) {
 887                 btrfs_block_release(root, right_buf);
 888                 return 1;
 889         }
 890
 891         left_nritems = btrfs_header_nritems(&left->header);
 892         for (i = left_nritems - 1; i >= 0; i--) {
 893                 item = left->items + i;
 894                 if (path->slots[0] == i)
 895                         push_space += data_size + sizeof(*item);
 896                 if (btrfs_item_size(item) + sizeof(*item) + push_space >
 897                     free_space)
 898                         break;
 899                 push_items++;
 900                 push_space += btrfs_item_size(item) + sizeof(*item);
 901         }
 902         if (push_items == 0) {
 903                 btrfs_block_release(root, right_buf);
 904                 return 1;
 905         }
 906         right_nritems = btrfs_header_nritems(&right->header);
 907         /* push left to right */
 908         push_space = btrfs_item_end(left->items + left_nritems - push_items);
 909         push_space -= leaf_data_end(root, left);
 910         /* make room in the right data area */
 911         btrfs_memmove(root, right, btrfs_leaf_data(right) +
 912                       leaf_data_end(root, right) - push_space,
 913                       btrfs_leaf_data(right) +
 914                       leaf_data_end(root, right), BTRFS_LEAF_DATA_SIZE(root) -
 915                       leaf_data_end(root, right));
 916         /* copy from the left data area */
 917         btrfs_memcpy(root, right, btrfs_leaf_data(right) +
 918                      BTRFS_LEAF_DATA_SIZE(root) - push_space,
 919                      btrfs_leaf_data(left) + leaf_data_end(root, left),
 920                      push_space);
 921         btrfs_memmove(root, right, right->items + push_items, right->items,
 922                 right_nritems * sizeof(struct btrfs_item));
 923         /* copy the items from left to right */
 924         btrfs_memcpy(root, right, right->items, left->items +
 925                      left_nritems - push_items,
 926                      push_items * sizeof(struct btrfs_item));
 927
 928         /* update the item pointers */
 929         right_nritems += push_items;
 930         btrfs_set_header_nritems(&right->header, right_nritems);
 931         push_space = BTRFS_LEAF_DATA_SIZE(root);
 932         for (i = 0; i < right_nritems; i++) {
 933                 btrfs_set_item_offset(right->items + i, push_space -
 934                                       btrfs_item_size(right->items + i));
 935                 push_space = btrfs_item_offset(right->items + i);
 936         }
 937         left_nritems -= push_items;
 938         btrfs_set_header_nritems(&left->header, left_nritems);
 939
 940         btrfs_mark_buffer_dirty(left_buf);
 941         btrfs_mark_buffer_dirty(right_buf);
 942         btrfs_memcpy(root, upper_node, &upper_node->ptrs[slot + 1].key,
 943                 &right->items[0].key, sizeof(struct btrfs_disk_key));
 944         btrfs_mark_buffer_dirty(upper);
 945
 946         /* then fixup the leaf pointer in the path */
 947         if (path->slots[0] >= left_nritems) {
 948                 path->slots[0] -= left_nritems;
 949                 btrfs_block_release(root, path->nodes[0]);
 950                 path->nodes[0] = right_buf;
 951                 path->slots[1] += 1;
 952         } else {
 953                 btrfs_block_release(root, right_buf);
 954         }
 955         return 0;
 956 }
 957 /*
 958  * push some data in the path leaf to the left, trying to free up at
 959  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 960  */
 961 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 962                           *root, struct btrfs_path *path, int data_size)
 963 {
 964         struct buffer_head *right_buf = path->nodes[0];
 965         struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf);
 966         struct buffer_head *t;
 967         struct btrfs_leaf *left;
 968         int slot;
 969         int i;
 970         int free_space;
 971         int push_space = 0;
 972         int push_items = 0;
 973         struct btrfs_item *item;
 974         u32 old_left_nritems;
 975         int ret = 0;
 976         int wret;
 977
 978         slot = path->slots[1];
 979         if (slot == 0) {
 980                 return 1;
 981         }
 982         if (!path->nodes[1]) {
 983                 return 1;
 984         }
 985         t = read_tree_block(root,
 986             btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1));
 987         left = btrfs_buffer_leaf(t);
 988         free_space = btrfs_leaf_free_space(root, left);
 989         if (free_space < data_size + sizeof(struct btrfs_item)) {
 990                 btrfs_block_release(root, t);
 991                 return 1;
 992         }
 993
 994         /* cow and double check */
 995         btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t);
 996         left = btrfs_buffer_leaf(t);
 997         free_space = btrfs_leaf_free_space(root, left);
 998         if (free_space < data_size + sizeof(struct btrfs_item)) {
 999                 btrfs_block_release(root, t);
1000                 return 1;
1001         }
1002
1003         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1004                 item = right->items + i;
1005                 if (path->slots[0] == i)
1006                         push_space += data_size + sizeof(*item);
1007                 if (btrfs_item_size(item) + sizeof(*item) + push_space >
1008                     free_space)
1009                         break;
1010                 push_items++;
1011                 push_space += btrfs_item_size(item) + sizeof(*item);
1012         }
1013         if (push_items == 0) {
1014                 btrfs_block_release(root, t);
1015                 return 1;
1016         }
1017         /* push data from right to left */
1018         btrfs_memcpy(root, left, left->items +
1019                      btrfs_header_nritems(&left->header),
1020                      right->items, push_items * sizeof(struct btrfs_item));
1021         push_space = BTRFS_LEAF_DATA_SIZE(root) -
1022                      btrfs_item_offset(right->items + push_items -1);
1023         btrfs_memcpy(root, left, btrfs_leaf_data(left) +
1024                      leaf_data_end(root, left) - push_space,
1025                      btrfs_leaf_data(right) +
1026                      btrfs_item_offset(right->items + push_items - 1),
1027                      push_space);
1028         old_left_nritems = btrfs_header_nritems(&left->header);
1029         BUG_ON(old_left_nritems < 0);
1030
1031         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1032                 u32 ioff = btrfs_item_offset(left->items + i);
1033                 btrfs_set_item_offset(left->items + i, ioff -
1034                                      (BTRFS_LEAF_DATA_SIZE(root) -
1035                                       btrfs_item_offset(left->items +
1036                                                         old_left_nritems - 1)));
1037         }
1038         btrfs_set_header_nritems(&left->header, old_left_nritems + push_items);
1039
1040         /* fixup right node */
1041         push_space = btrfs_item_offset(right->items + push_items - 1) -
1042                      leaf_data_end(root, right);
1043         btrfs_memmove(root, right, btrfs_leaf_data(right) +
1044                       BTRFS_LEAF_DATA_SIZE(root) - push_space,
1045                       btrfs_leaf_data(right) +
1046                       leaf_data_end(root, right), push_space);
1047         btrfs_memmove(root, right, right->items, right->items + push_items,
1048                 (btrfs_header_nritems(&right->header) - push_items) *
1049                 sizeof(struct btrfs_item));
1050         btrfs_set_header_nritems(&right->header,
1051                                  btrfs_header_nritems(&right->header) -
1052                                  push_items);
1053         push_space = BTRFS_LEAF_DATA_SIZE(root);
1054
1055         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1056                 btrfs_set_item_offset(right->items + i, push_space -
1057                                       btrfs_item_size(right->items + i));
1058                 push_space = btrfs_item_offset(right->items + i);
1059         }
1060
1061         btrfs_mark_buffer_dirty(t);
1062         btrfs_mark_buffer_dirty(right_buf);
1063
1064         wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1);
1065         if (wret)
1066                 ret = wret;
1067
1068         /* then fixup the leaf pointer in the path */
1069         if (path->slots[0] < push_items) {
1070                 path->slots[0] += old_left_nritems;
1071                 btrfs_block_release(root, path->nodes[0]);
1072                 path->nodes[0] = t;
1073                 path->slots[1] -= 1;
1074         } else {
1075                 btrfs_block_release(root, t);
1076                 path->slots[0] -= push_items;
1077         }
1078         BUG_ON(path->slots[0] < 0);
1079         return ret;
1080 }
1081
1082 /*
1083  * split the path's leaf in two, making sure there is at least data_size
1084  * available for the resulting leaf level of the path.
1085  *
1086  * returns 0 if all went well and < 0 on failure.
1087  */
1088 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1089                       *root, struct btrfs_key *ins_key,
1090                       struct btrfs_path *path, int data_size)
1091 {
1092         struct buffer_head *l_buf;
1093         struct btrfs_leaf *l;
1094         u32 nritems;
1095         int mid;
1096         int slot;
1097         struct btrfs_leaf *right;
1098         struct buffer_head *right_buffer;
1099         int space_needed = data_size + sizeof(struct btrfs_item);
1100         int data_copy_size;
1101         int rt_data_off;
1102         int i;
1103         int ret = 0;
1104         int wret;
1105         int double_split = 0;
1106         struct btrfs_disk_key disk_key;
1107
1108         /* first try to make some room by pushing left and right */
1109         wret = push_leaf_left(trans, root, path, data_size);
1110         if (wret < 0)
1111                 return wret;
1112         if (wret) {
1113                 wret = push_leaf_right(trans, root, path, data_size);
1114                 if (wret < 0)
1115                         return wret;
1116         }
1117         l_buf = path->nodes[0];
1118         l = btrfs_buffer_leaf(l_buf);
1119
1120         /* did the pushes work? */
1121         if (btrfs_leaf_free_space(root, l) >=
1122             sizeof(struct btrfs_item) + data_size)
1123                 return 0;
1124
1125         if (!path->nodes[1]) {
1126                 ret = insert_new_root(trans, root, path, 1);
1127                 if (ret)
1128                         return ret;
1129         }
1130         slot = path->slots[0];
1131         nritems = btrfs_header_nritems(&l->header);
1132         mid = (nritems + 1)/ 2;
1133         right_buffer = btrfs_alloc_free_block(trans, root);
1134         BUG_ON(!right_buffer);
1135         right = btrfs_buffer_leaf(right_buffer);
1136         memset(&right->header, 0, sizeof(right->header));
1137         btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr);
1138         btrfs_set_header_generation(&right->header, trans->transid);
1139         btrfs_set_header_level(&right->header, 0);
1140         btrfs_set_header_parentid(&right->header,
1141               btrfs_header_parentid(btrfs_buffer_header(root->node)));
1142         if (mid <= slot) {
1143                 if (nritems == 1 ||
1144                     leaf_space_used(l, mid, nritems - mid) + space_needed >
1145                         BTRFS_LEAF_DATA_SIZE(root)) {
1146                         if (slot >= nritems) {
1147                                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1148                                 btrfs_set_header_nritems(&right->header, 0);
1149                                 wret = insert_ptr(trans, root, path,
1150                                                   &disk_key,
1151                                                   right_buffer->b_blocknr,
1152                                                   path->slots[1] + 1, 1);
1153                                 if (wret)
1154                                         ret = wret;
1155                                 btrfs_block_release(root, path->nodes[0]);
1156                                 path->nodes[0] = right_buffer;
1157                                 path->slots[0] = 0;
1158                                 path->slots[1] += 1;
1159                                 return ret;
1160                         }
1161                         mid = slot;
1162                         double_split = 1;
1163                 }
1164         } else {
1165                 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1166                         BTRFS_LEAF_DATA_SIZE(root)) {
1167                         if (slot == 0) {
1168                                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1169                                 btrfs_set_header_nritems(&right->header, 0);
1170                                 wret = insert_ptr(trans, root, path,
1171                                                   &disk_key,
1172                                                   right_buffer->b_blocknr,
1173                                                   path->slots[1] - 1, 1);
1174                                 if (wret)
1175                                         ret = wret;
1176                                 btrfs_block_release(root, path->nodes[0]);
1177                                 path->nodes[0] = right_buffer;
1178                                 path->slots[0] = 0;
1179                                 path->slots[1] -= 1;
1180                                 return ret;
1181                         }
1182                         mid = slot;
1183                         double_split = 1;
1184                 }
1185         }
1186         btrfs_set_header_nritems(&right->header, nritems - mid);
1187         data_copy_size = btrfs_item_end(l->items + mid) -
1188                          leaf_data_end(root, l);
1189         btrfs_memcpy(root, right, right->items, l->items + mid,
1190                      (nritems - mid) * sizeof(struct btrfs_item));
1191         btrfs_memcpy(root, right,
1192                      btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1193                      data_copy_size, btrfs_leaf_data(l) +
1194                      leaf_data_end(root, l), data_copy_size);
1195         rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1196                       btrfs_item_end(l->items + mid);
1197
1198         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1199                 u32 ioff = btrfs_item_offset(right->items + i);
1200                 btrfs_set_item_offset(right->items + i, ioff + rt_data_off);
1201         }
1202
1203         btrfs_set_header_nritems(&l->header, mid);
1204         ret = 0;
1205         wret = insert_ptr(trans, root, path, &right->items[0].key,
1206                           right_buffer->b_blocknr, path->slots[1] + 1, 1);
1207         if (wret)
1208                 ret = wret;
1209         btrfs_mark_buffer_dirty(right_buffer);
1210         btrfs_mark_buffer_dirty(l_buf);
1211         BUG_ON(path->slots[0] != slot);
1212         if (mid <= slot) {
1213                 btrfs_block_release(root, path->nodes[0]);
1214                 path->nodes[0] = right_buffer;
1215                 path->slots[0] -= mid;
1216                 path->slots[1] += 1;
1217         } else
1218                 btrfs_block_release(root, right_buffer);
1219         BUG_ON(path->slots[0] < 0);
1220
1221         if (!double_split)
1222                 return ret;
1223         right_buffer = btrfs_alloc_free_block(trans, root);
1224         BUG_ON(!right_buffer);
1225         right = btrfs_buffer_leaf(right_buffer);
1226         memset(&right->header, 0, sizeof(right->header));
1227         btrfs_set_header_blocknr(&right->header, right_buffer->b_blocknr);
1228         btrfs_set_header_generation(&right->header, trans->transid);
1229         btrfs_set_header_level(&right->header, 0);
1230         btrfs_set_header_parentid(&right->header,
1231               btrfs_header_parentid(btrfs_buffer_header(root->node)));
1232         btrfs_cpu_key_to_disk(&disk_key, ins_key);
1233         btrfs_set_header_nritems(&right->header, 0);
1234         wret = insert_ptr(trans, root, path,
1235                           &disk_key,
1236                           right_buffer->b_blocknr,
1237                           path->slots[1], 1);
1238         if (wret)
1239                 ret = wret;
1240         btrfs_block_release(root, path->nodes[0]);
1241         path->nodes[0] = right_buffer;
1242         path->slots[0] = 0;
1243         check_node(root, path, 1);
1244         check_leaf(root, path, 0);
1245         return ret;
1246 }
1247
1248 /*
1249  * Given a key and some data, insert an item into the tree.
1250  * This does all the path init required, making room in the tree if needed.
1251  */
1252 int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
1253                             *root, struct btrfs_path *path, struct btrfs_key
1254                             *cpu_key, u32 data_size)
1255 {
1256         int ret = 0;
1257         int slot;
1258         int slot_orig;
1259         struct btrfs_leaf *leaf;
1260         struct buffer_head *leaf_buf;
1261         u32 nritems;
1262         unsigned int data_end;
1263         struct btrfs_disk_key disk_key;
1264
1265         btrfs_cpu_key_to_disk(&disk_key, cpu_key);
1266
1267         /* create a root if there isn't one */
1268         if (!root->node)
1269                 BUG();
1270         ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1);
1271         if (ret == 0) {
1272                 return -EEXIST;
1273         }
1274         if (ret < 0)
1275                 goto out;
1276
1277         slot_orig = path->slots[0];
1278         leaf_buf = path->nodes[0];
1279         leaf = btrfs_buffer_leaf(leaf_buf);
1280
1281         nritems = btrfs_header_nritems(&leaf->header);
1282         data_end = leaf_data_end(root, leaf);
1283
1284         if (btrfs_leaf_free_space(root, leaf) <
1285             sizeof(struct btrfs_item) + data_size) {
1286                 BUG();
1287         }
1288         slot = path->slots[0];
1289         BUG_ON(slot < 0);
1290         if (slot != nritems) {
1291                 int i;
1292                 unsigned int old_data = btrfs_item_end(leaf->items + slot);
1293
1294                 /*
1295                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
1296                  */
1297                 /* first correct the data pointers */
1298                 for (i = slot; i < nritems; i++) {
1299                         u32 ioff = btrfs_item_offset(leaf->items + i);
1300                         btrfs_set_item_offset(leaf->items + i,
1301                                               ioff - data_size);
1302                 }
1303
1304                 /* shift the items */
1305                 btrfs_memmove(root, leaf, leaf->items + slot + 1,
1306                               leaf->items + slot,
1307                               (nritems - slot) * sizeof(struct btrfs_item));
1308
1309                 /* shift the data */
1310                 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) +
1311                               data_end - data_size, btrfs_leaf_data(leaf) +
1312                               data_end, old_data - data_end);
1313                 data_end = old_data;
1314         }
1315         /* setup the item for the new data */
1316         btrfs_memcpy(root, leaf, &leaf->items[slot].key, &disk_key,
1317                      sizeof(struct btrfs_disk_key));
1318         btrfs_set_item_offset(leaf->items + slot, data_end - data_size);
1319         btrfs_set_item_size(leaf->items + slot, data_size);
1320         btrfs_set_header_nritems(&leaf->header, nritems + 1);
1321         btrfs_mark_buffer_dirty(leaf_buf);
1322
1323         ret = 0;
1324         if (slot == 0)
1325                 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
1326
1327         if (btrfs_leaf_free_space(root, leaf) < 0)
1328                 BUG();
1329         check_leaf(root, path, 0);
1330 out:
1331         return ret;
1332 }
1333
1334 /*
1335  * Given a key and some data, insert an item into the tree.
1336  * This does all the path init required, making room in the tree if needed.
1337  */
1338 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
1339                       *root, struct btrfs_key *cpu_key, void *data, u32
1340                       data_size)
1341 {
1342         int ret = 0;
1343         struct btrfs_path *path;
1344         u8 *ptr;
1345
1346         path = btrfs_alloc_path();
1347         BUG_ON(!path);
1348         btrfs_init_path(path);
1349         ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
1350         if (!ret) {
1351                 ptr = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]),
1352                                      path->slots[0], u8);
1353                 btrfs_memcpy(root, path->nodes[0]->b_data,
1354                              ptr, data, data_size);
1355                 btrfs_mark_buffer_dirty(path->nodes[0]);
1356         }
1357         btrfs_release_path(root, path);
1358         btrfs_free_path(path);
1359         return ret;
1360 }
1361
1362 /*
1363  * delete the pointer from a given node.
1364  *
1365  * If the delete empties a node, the node is removed from the tree,
1366  * continuing all the way the root if required.  The root is converted into
1367  * a leaf if all the nodes are emptied.
1368  */
1369 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1370                    struct btrfs_path *path, int level, int slot)
1371 {
1372         struct btrfs_node *node;
1373         struct buffer_head *parent = path->nodes[level];
1374         u32 nritems;
1375         int ret = 0;
1376         int wret;
1377
1378         node = btrfs_buffer_node(parent);
1379         nritems = btrfs_header_nritems(&node->header);
1380         if (slot != nritems -1) {
1381                 btrfs_memmove(root, node, node->ptrs + slot,
1382                               node->ptrs + slot + 1,
1383                               sizeof(struct btrfs_key_ptr) *
1384                               (nritems - slot - 1));
1385         }
1386         nritems--;
1387         btrfs_set_header_nritems(&node->header, nritems);
1388         if (nritems == 0 && parent == root->node) {
1389                 struct btrfs_header *header = btrfs_buffer_header(root->node);
1390                 BUG_ON(btrfs_header_level(header) != 1);
1391                 /* just turn the root into a leaf and break */
1392                 btrfs_set_header_level(header, 0);
1393         } else if (slot == 0) {
1394                 wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key,
1395                                       level + 1);
1396                 if (wret)
1397                         ret = wret;
1398         }
1399         btrfs_mark_buffer_dirty(parent);
1400         return ret;
1401 }
1402
1403 /*
1404  * delete the item at the leaf level in path.  If that empties
1405  * the leaf, remove it from the tree
1406  */
1407 int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1408                    struct btrfs_path *path)
1409 {
1410         int slot;
1411         struct btrfs_leaf *leaf;
1412         struct buffer_head *leaf_buf;
1413         int doff;
1414         int dsize;
1415         int ret = 0;
1416         int wret;
1417         u32 nritems;
1418
1419         leaf_buf = path->nodes[0];
1420         leaf = btrfs_buffer_leaf(leaf_buf);
1421         slot = path->slots[0];
1422         doff = btrfs_item_offset(leaf->items + slot);
1423         dsize = btrfs_item_size(leaf->items + slot);
1424         nritems = btrfs_header_nritems(&leaf->header);
1425
1426         if (slot != nritems - 1) {
1427                 int i;
1428                 int data_end = leaf_data_end(root, leaf);
1429                 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) +
1430                               data_end + dsize,
1431                               btrfs_leaf_data(leaf) + data_end,
1432                               doff - data_end);
1433                 for (i = slot + 1; i < nritems; i++) {
1434                         u32 ioff = btrfs_item_offset(leaf->items + i);
1435                         btrfs_set_item_offset(leaf->items + i, ioff + dsize);
1436                 }
1437                 btrfs_memmove(root, leaf, leaf->items + slot,
1438                               leaf->items + slot + 1,
1439                               sizeof(struct btrfs_item) *
1440                               (nritems - slot - 1));
1441         }
1442         btrfs_set_header_nritems(&leaf->header, nritems - 1);
1443         nritems--;
1444         /* delete the leaf if we've emptied it */
1445         if (nritems == 0) {
1446                 if (leaf_buf == root->node) {
1447                         btrfs_set_header_level(&leaf->header, 0);
1448                 } else {
1449                         clean_tree_block(trans, root, leaf_buf);
1450                         wait_on_buffer(leaf_buf);
1451                         wret = del_ptr(trans, root, path, 1, path->slots[1]);
1452                         if (wret)
1453                                 ret = wret;
1454                         wret = btrfs_free_extent(trans, root,
1455                                                  leaf_buf->b_blocknr, 1, 1);
1456                         if (wret)
1457                                 ret = wret;
1458                 }
1459         } else {
1460                 int used = leaf_space_used(leaf, 0, nritems);
1461                 if (slot == 0) {
1462                         wret = fixup_low_keys(trans, root, path,
1463                                               &leaf->items[0].key, 1);
1464                         if (wret)
1465                                 ret = wret;
1466                 }
1467
1468                 /* delete the leaf if it is mostly empty */
1469                 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
1470                         /* push_leaf_left fixes the path.
1471                          * make sure the path still points to our leaf
1472                          * for possible call to del_ptr below
1473                          */
1474                         slot = path->slots[1];
1475                         get_bh(leaf_buf);
1476                         wret = push_leaf_left(trans, root, path, 1);
1477                         if (wret < 0)
1478                                 ret = wret;
1479                         if (path->nodes[0] == leaf_buf &&
1480                             btrfs_header_nritems(&leaf->header)) {
1481                                 wret = push_leaf_right(trans, root, path, 1);
1482                                 if (wret < 0)
1483                                         ret = wret;
1484                         }
1485                         if (btrfs_header_nritems(&leaf->header) == 0) {
1486                                 u64 blocknr = leaf_buf->b_blocknr;
1487                                 clean_tree_block(trans, root, leaf_buf);
1488                                 wait_on_buffer(leaf_buf);
1489                                 wret = del_ptr(trans, root, path, 1, slot);
1490                                 if (wret)
1491                                         ret = wret;
1492                                 btrfs_block_release(root, leaf_buf);
1493                                 wret = btrfs_free_extent(trans, root, blocknr,
1494                                                          1, 1);
1495                                 if (wret)
1496                                         ret = wret;
1497                         } else {
1498                                 btrfs_mark_buffer_dirty(leaf_buf);
1499                                 btrfs_block_release(root, leaf_buf);
1500                         }
1501                 } else {
1502                         btrfs_mark_buffer_dirty(leaf_buf);
1503                 }
1504         }
1505         return ret;
1506 }
1507
1508 /*
1509  * walk up the tree as far as required to find the next leaf.
1510  * returns 0 if it found something or 1 if there are no greater leaves.
1511  * returns < 0 on io errors.
1512  */
1513 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
1514 {
1515         int slot;
1516         int level = 1;
1517         u64 blocknr;
1518         struct buffer_head *c;
1519         struct btrfs_node *c_node;
1520         struct buffer_head *next = NULL;
1521
1522         while(level < BTRFS_MAX_LEVEL) {
1523                 if (!path->nodes[level])
1524                         return 1;
1525                 slot = path->slots[level] + 1;
1526                 c = path->nodes[level];
1527                 c_node = btrfs_buffer_node(c);
1528                 if (slot >= btrfs_header_nritems(&c_node->header)) {
1529                         level++;
1530                         continue;
1531                 }
1532                 blocknr = btrfs_node_blockptr(c_node, slot);
1533                 if (next)
1534                         btrfs_block_release(root, next);
1535                 next = read_tree_block(root, blocknr);
1536                 break;
1537         }
1538         path->slots[level] = slot;
1539         while(1) {
1540                 level--;
1541                 c = path->nodes[level];
1542                 btrfs_block_release(root, c);
1543                 path->nodes[level] = next;
1544                 path->slots[level] = 0;
1545                 if (!level)
1546                         break;
1547                 next = read_tree_block(root,
1548                        btrfs_node_blockptr(btrfs_buffer_node(next), 0));
1549         }
1550         return 0;
1551 }