ctree.c

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