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         lower = &path->nodes[level-1]->node;
 689         if (btrfs_is_leaf(lower))
 690                 lower_key = &((struct btrfs_leaf *)lower)->items[0].key;
 691         else
 692                 lower_key = &lower->ptrs[0].key;
 693         memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key));
 694         btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->blocknr);
 695         /* the super has an extra ref to root->node */
 696         btrfs_block_release(root, root->node);
 697         root->node = t;
 698         t->count++;
 699         path->nodes[level] = t;
 700         path->slots[level] = 0;
 701         return 0;
 702 }
 703
 704 /*
 705  * worker function to insert a single pointer in a node.
 706  * the node should have enough room for the pointer already
 707  *
 708  * slot and level indicate where you want the key to go, and
 709  * blocknr is the block the key points to.
 710  *
 711  * returns zero on success and < 0 on any error
 712  */
 713 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
 714                       *root, struct btrfs_path *path, struct btrfs_disk_key
 715                       *key, u64 blocknr, int slot, int level)
 716 {
 717         struct btrfs_node *lower;
 718         int nritems;
 719
 720         BUG_ON(!path->nodes[level]);
 721         lower = &path->nodes[level]->node;
 722         nritems = btrfs_header_nritems(&lower->header);
 723         if (slot > nritems)
 724                 BUG();
 725         if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
 726                 BUG();
 727         if (slot != nritems) {
 728                 memmove(lower->ptrs + slot + 1, lower->ptrs + slot,
 729                         (nritems - slot) * sizeof(struct btrfs_key_ptr));
 730         }
 731         memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key));
 732         btrfs_set_node_blockptr(lower, slot, blocknr);
 733         btrfs_set_header_nritems(&lower->header, nritems + 1);
 734         BUG_ON(list_empty(&path->nodes[level]->dirty));
 735         return 0;
 736 }
 737
 738 /*
 739  * split the node at the specified level in path in two.
 740  * The path is corrected to point to the appropriate node after the split
 741  *
 742  * Before splitting this tries to make some room in the node by pushing
 743  * left and right, if either one works, it returns right away.
 744  *
 745  * returns 0 on success and < 0 on failure
 746  */
 747 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 748                       *root, struct btrfs_path *path, int level)
 749 {
 750         struct btrfs_buffer *t;
 751         struct btrfs_node *c;
 752         struct btrfs_buffer *split_buffer;
 753         struct btrfs_node *split;
 754         int mid;
 755         int ret;
 756         int wret;
 757         u32 c_nritems;
 758
 759         t = path->nodes[level];
 760         c = &t->node;
 761         if (t == root->node) {
 762                 /* trying to split the root, lets make a new one */
 763                 ret = insert_new_root(trans, root, path, level + 1);
 764                 if (ret)
 765                         return ret;
 766         }
 767         c_nritems = btrfs_header_nritems(&c->header);
 768         split_buffer = btrfs_alloc_free_block(trans, root);
 769         split = &split_buffer->node;
 770         btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
 771         btrfs_set_header_level(&split->header, btrfs_header_level(&c->header));
 772         btrfs_set_header_blocknr(&split->header, split_buffer->blocknr);
 773         btrfs_set_header_owner(&split->header, root->root_key.objectid);
 774         mid = (c_nritems + 1) / 2;
 775         memcpy(split->ptrs, c->ptrs + mid,
 776                 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
 777         btrfs_set_header_nritems(&split->header, c_nritems - mid);
 778         btrfs_set_header_nritems(&c->header, mid);
 779         ret = 0;
 780
 781         BUG_ON(list_empty(&t->dirty));
 782         wret = insert_ptr(trans, root, path, &split->ptrs[0].key,
 783                           split_buffer->blocknr, path->slots[level + 1] + 1,
 784                           level + 1);
 785         if (wret)
 786                 ret = wret;
 787
 788         if (path->slots[level] >= mid) {
 789                 path->slots[level] -= mid;
 790                 btrfs_block_release(root, t);
 791                 path->nodes[level] = split_buffer;
 792                 path->slots[level + 1] += 1;
 793         } else {
 794                 btrfs_block_release(root, split_buffer);
 795         }
 796         return ret;
 797 }
 798
 799 /*
 800  * push some data in the path leaf to the right, trying to free up at
 801  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 802  *
 803  * returns 1 if the push failed because the other node didn't have enough
 804  * room, 0 if everything worked out and < 0 if there were major errors.
 805  */
 806 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
 807                            *root, struct btrfs_path *path, int data_size)
 808 {
 809         struct btrfs_buffer *left_buf = path->nodes[0];
 810         struct btrfs_leaf *left = &left_buf->leaf;
 811         struct btrfs_leaf *right;
 812         struct btrfs_buffer *right_buf;
 813         struct btrfs_buffer *upper;
 814         int slot;
 815         int i;
 816         int free_space;
 817         int push_space = 0;
 818         int push_items = 0;
 819         struct btrfs_item *item;
 820         u32 left_nritems;
 821         u32 right_nritems;
 822
 823         slot = path->slots[1];
 824         if (!path->nodes[1]) {
 825                 return 1;
 826         }
 827         upper = path->nodes[1];
 828         if (slot >= btrfs_header_nritems(&upper->node.header) - 1) {
 829                 return 1;
 830         }
 831         right_buf = read_tree_block(root, btrfs_node_blockptr(&upper->node,
 832                                                               slot + 1));
 833         right = &right_buf->leaf;
 834         free_space = btrfs_leaf_free_space(root, right);
 835         if (free_space < data_size + sizeof(struct btrfs_item)) {
 836                 btrfs_block_release(root, right_buf);
 837                 return 1;
 838         }
 839         /* cow and double check */
 840         btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf);
 841         right = &right_buf->leaf;
 842         free_space = btrfs_leaf_free_space(root, right);
 843         if (free_space < data_size + sizeof(struct btrfs_item)) {
 844                 btrfs_block_release(root, right_buf);
 845                 return 1;
 846         }
 847
 848         left_nritems = btrfs_header_nritems(&left->header);
 849         for (i = left_nritems - 1; i >= 0; i--) {
 850                 item = left->items + i;
 851                 if (path->slots[0] == i)
 852                         push_space += data_size + sizeof(*item);
 853                 if (btrfs_item_size(item) + sizeof(*item) + push_space >
 854                     free_space)
 855                         break;
 856                 push_items++;
 857                 push_space += btrfs_item_size(item) + sizeof(*item);
 858         }
 859         if (push_items == 0) {
 860                 btrfs_block_release(root, right_buf);
 861                 return 1;
 862         }
 863         right_nritems = btrfs_header_nritems(&right->header);
 864         /* push left to right */
 865         push_space = btrfs_item_end(left->items + left_nritems - push_items);
 866         push_space -= leaf_data_end(root, left);
 867         /* make room in the right data area */
 868         memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) -
 869                 push_space, btrfs_leaf_data(right) + leaf_data_end(root, right),
 870                 BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right));
 871         /* copy from the left data area */
 872         memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space,
 873                 btrfs_leaf_data(left) + leaf_data_end(root, left), push_space);
 874         memmove(right->items + push_items, right->items,
 875                 right_nritems * sizeof(struct btrfs_item));
 876         /* copy the items from left to right */
 877         memcpy(right->items, left->items + left_nritems - push_items,
 878                 push_items * sizeof(struct btrfs_item));
 879
 880         /* update the item pointers */
 881         right_nritems += push_items;
 882         btrfs_set_header_nritems(&right->header, right_nritems);
 883         push_space = BTRFS_LEAF_DATA_SIZE(root);
 884         for (i = 0; i < right_nritems; i++) {
 885                 btrfs_set_item_offset(right->items + i, push_space -
 886                                       btrfs_item_size(right->items + i));
 887                 push_space = btrfs_item_offset(right->items + i);
 888         }
 889         left_nritems -= push_items;
 890         btrfs_set_header_nritems(&left->header, left_nritems);
 891
 892         BUG_ON(list_empty(&left_buf->dirty));
 893         BUG_ON(list_empty(&right_buf->dirty));
 894         memcpy(&upper->node.ptrs[slot + 1].key,
 895                 &right->items[0].key, sizeof(struct btrfs_disk_key));
 896         BUG_ON(list_empty(&upper->dirty));
 897
 898         /* then fixup the leaf pointer in the path */
 899         if (path->slots[0] >= left_nritems) {
 900                 path->slots[0] -= left_nritems;
 901                 btrfs_block_release(root, path->nodes[0]);
 902                 path->nodes[0] = right_buf;
 903                 path->slots[1] += 1;
 904         } else {
 905                 btrfs_block_release(root, right_buf);
 906         }
 907         return 0;
 908 }
 909 /*
 910  * push some data in the path leaf to the left, trying to free up at
 911  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 912  */
 913 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 914                           *root, struct btrfs_path *path, int data_size)
 915 {
 916         struct btrfs_buffer *right_buf = path->nodes[0];
 917         struct btrfs_leaf *right = &right_buf->leaf;
 918         struct btrfs_buffer *t;
 919         struct btrfs_leaf *left;
 920         int slot;
 921         int i;
 922         int free_space;
 923         int push_space = 0;
 924         int push_items = 0;
 925         struct btrfs_item *item;
 926         u32 old_left_nritems;
 927         int ret = 0;
 928         int wret;
 929
 930         slot = path->slots[1];
 931         if (slot == 0) {
 932                 return 1;
 933         }
 934         if (!path->nodes[1]) {
 935                 return 1;
 936         }
 937         t = read_tree_block(root, btrfs_node_blockptr(&path->nodes[1]->node,
 938                                                       slot - 1));
 939         left = &t->leaf;
 940         free_space = btrfs_leaf_free_space(root, left);
 941         if (free_space < data_size + sizeof(struct btrfs_item)) {
 942                 btrfs_block_release(root, t);
 943                 return 1;
 944         }
 945
 946         /* cow and double check */
 947         btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t);
 948         left = &t->leaf;
 949         free_space = btrfs_leaf_free_space(root, left);
 950         if (free_space < data_size + sizeof(struct btrfs_item)) {
 951                 btrfs_block_release(root, t);
 952                 return 1;
 953         }
 954
 955         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
 956                 item = right->items + i;
 957                 if (path->slots[0] == i)
 958                         push_space += data_size + sizeof(*item);
 959                 if (btrfs_item_size(item) + sizeof(*item) + push_space >
 960                     free_space)
 961                         break;
 962                 push_items++;
 963                 push_space += btrfs_item_size(item) + sizeof(*item);
 964         }
 965         if (push_items == 0) {
 966                 btrfs_block_release(root, t);
 967                 return 1;
 968         }
 969         /* push data from right to left */
 970         memcpy(left->items + btrfs_header_nritems(&left->header),
 971                 right->items, push_items * sizeof(struct btrfs_item));
 972         push_space = BTRFS_LEAF_DATA_SIZE(root) -
 973                      btrfs_item_offset(right->items + push_items -1);
 974         memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space,
 975                 btrfs_leaf_data(right) +
 976                 btrfs_item_offset(right->items + push_items - 1),
 977                 push_space);
 978         old_left_nritems = btrfs_header_nritems(&left->header);
 979         BUG_ON(old_left_nritems < 0);
 980
 981         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
 982                 u32 ioff = btrfs_item_offset(left->items + i);
 983                 btrfs_set_item_offset(left->items + i, ioff -
 984                                      (BTRFS_LEAF_DATA_SIZE(root) -
 985                                       btrfs_item_offset(left->items +
 986                                                         old_left_nritems - 1)));
 987         }
 988         btrfs_set_header_nritems(&left->header, old_left_nritems + push_items);
 989
 990         /* fixup right node */
 991         push_space = btrfs_item_offset(right->items + push_items - 1) -
 992                      leaf_data_end(root, right);
 993         memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
 994                 push_space, btrfs_leaf_data(right) +
 995                 leaf_data_end(root, right), push_space);
 996         memmove(right->items, right->items + push_items,
 997                 (btrfs_header_nritems(&right->header) - push_items) *
 998                 sizeof(struct btrfs_item));
 999         btrfs_set_header_nritems(&right->header,
1000                                  btrfs_header_nritems(&right->header) -
1001                                  push_items);
1002         push_space = BTRFS_LEAF_DATA_SIZE(root);
1003
1004         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1005                 btrfs_set_item_offset(right->items + i, push_space -
1006                                       btrfs_item_size(right->items + i));
1007                 push_space = btrfs_item_offset(right->items + i);
1008         }
1009
1010         BUG_ON(list_empty(&t->dirty));
1011         BUG_ON(list_empty(&right_buf->dirty));
1012
1013         wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1);
1014         if (wret)
1015                 ret = wret;
1016
1017         /* then fixup the leaf pointer in the path */
1018         if (path->slots[0] < push_items) {
1019                 path->slots[0] += old_left_nritems;
1020                 btrfs_block_release(root, path->nodes[0]);
1021                 path->nodes[0] = t;
1022                 path->slots[1] -= 1;
1023         } else {
1024                 btrfs_block_release(root, t);
1025                 path->slots[0] -= push_items;
1026         }
1027         BUG_ON(path->slots[0] < 0);
1028         return ret;
1029 }
1030
1031 /*
1032  * split the path's leaf in two, making sure there is at least data_size
1033  * available for the resulting leaf level of the path.
1034  *
1035  * returns 0 if all went well and < 0 on failure.
1036  */
1037 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1038                       *root, struct btrfs_path *path, int data_size)
1039 {
1040         struct btrfs_buffer *l_buf;
1041         struct btrfs_leaf *l;
1042         u32 nritems;
1043         int mid;
1044         int slot;
1045         struct btrfs_leaf *right;
1046         struct btrfs_buffer *right_buffer;
1047         int space_needed = data_size + sizeof(struct btrfs_item);
1048         int data_copy_size;
1049         int rt_data_off;
1050         int i;
1051         int ret;
1052         int wret;
1053
1054         /* first try to make some room by pushing left and right */
1055         wret = push_leaf_left(trans, root, path, data_size);
1056         if (wret < 0)
1057                 return wret;
1058         if (wret) {
1059                 wret = push_leaf_right(trans, root, path, data_size);
1060                 if (wret < 0)
1061                         return wret;
1062         }
1063         l_buf = path->nodes[0];
1064         l = &l_buf->leaf;
1065
1066         /* did the pushes work? */
1067         if (btrfs_leaf_free_space(root, l) >=
1068             sizeof(struct btrfs_item) + data_size)
1069                 return 0;
1070
1071         if (!path->nodes[1]) {
1072                 ret = insert_new_root(trans, root, path, 1);
1073                 if (ret)
1074                         return ret;
1075         }
1076         slot = path->slots[0];
1077         nritems = btrfs_header_nritems(&l->header);
1078         mid = (nritems + 1)/ 2;
1079         right_buffer = btrfs_alloc_free_block(trans, root);
1080         BUG_ON(!right_buffer);
1081         BUG_ON(mid == nritems);
1082         right = &right_buffer->leaf;
1083         memset(&right->header, 0, sizeof(right->header));
1084         if (mid <= slot) {
1085                 /* FIXME, just alloc a new leaf here */
1086                 if (leaf_space_used(l, mid, nritems - mid) + space_needed >
1087                         BTRFS_LEAF_DATA_SIZE(root))
1088                         BUG();
1089         } else {
1090                 /* FIXME, just alloc a new leaf here */
1091                 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1092                         BTRFS_LEAF_DATA_SIZE(root))
1093                         BUG();
1094         }
1095         btrfs_set_header_nritems(&right->header, nritems - mid);
1096         btrfs_set_header_blocknr(&right->header, right_buffer->blocknr);
1097         btrfs_set_header_level(&right->header, 0);
1098         btrfs_set_header_owner(&right->header, root->root_key.objectid);
1099         data_copy_size = btrfs_item_end(l->items + mid) -
1100                          leaf_data_end(root, l);
1101         memcpy(right->items, l->items + mid,
1102                (nritems - mid) * sizeof(struct btrfs_item));
1103         memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1104                 data_copy_size, btrfs_leaf_data(l) +
1105                 leaf_data_end(root, l), data_copy_size);
1106         rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1107                       btrfs_item_end(l->items + mid);
1108
1109         for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1110                 u32 ioff = btrfs_item_offset(right->items + i);
1111                 btrfs_set_item_offset(right->items + i, ioff + rt_data_off);
1112         }
1113
1114         btrfs_set_header_nritems(&l->header, mid);
1115         ret = 0;
1116         wret = insert_ptr(trans, root, path, &right->items[0].key,
1117                           right_buffer->blocknr, path->slots[1] + 1, 1);
1118         if (wret)
1119                 ret = wret;
1120         BUG_ON(list_empty(&right_buffer->dirty));
1121         BUG_ON(list_empty(&l_buf->dirty));
1122         BUG_ON(path->slots[0] != slot);
1123         if (mid <= slot) {
1124                 btrfs_block_release(root, path->nodes[0]);
1125                 path->nodes[0] = right_buffer;
1126                 path->slots[0] -= mid;
1127                 path->slots[1] += 1;
1128         } else
1129                 btrfs_block_release(root, right_buffer);
1130         BUG_ON(path->slots[0] < 0);
1131         return ret;
1132 }
1133
1134 /*
1135  * Given a key and some data, insert an item into the tree.
1136  * This does all the path init required, making room in the tree if needed.
1137  */
1138 int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
1139                             *root, struct btrfs_path *path, struct btrfs_key
1140                             *cpu_key, u32 data_size)
1141 {
1142         int ret = 0;
1143         int slot;
1144         int slot_orig;
1145         struct btrfs_leaf *leaf;
1146         struct btrfs_buffer *leaf_buf;
1147         u32 nritems;
1148         unsigned int data_end;
1149         struct btrfs_disk_key disk_key;
1150
1151         btrfs_cpu_key_to_disk(&disk_key, cpu_key);
1152
1153         /* create a root if there isn't one */
1154         if (!root->node)
1155                 BUG();
1156         ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1);
1157         if (ret == 0) {
1158                 return -EEXIST;
1159         }
1160         if (ret < 0)
1161                 goto out;
1162
1163         slot_orig = path->slots[0];
1164         leaf_buf = path->nodes[0];
1165         leaf = &leaf_buf->leaf;
1166
1167         nritems = btrfs_header_nritems(&leaf->header);
1168         data_end = leaf_data_end(root, leaf);
1169
1170         if (btrfs_leaf_free_space(root, leaf) <
1171             sizeof(struct btrfs_item) + data_size)
1172                 BUG();
1173
1174         slot = path->slots[0];
1175         BUG_ON(slot < 0);
1176         if (slot != nritems) {
1177                 int i;
1178                 unsigned int old_data = btrfs_item_end(leaf->items + slot);
1179
1180                 /*
1181                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
1182                  */
1183                 /* first correct the data pointers */
1184                 for (i = slot; i < nritems; i++) {
1185                         u32 ioff = btrfs_item_offset(leaf->items + i);
1186                         btrfs_set_item_offset(leaf->items + i,
1187                                               ioff - data_size);
1188                 }
1189
1190                 /* shift the items */
1191                 memmove(leaf->items + slot + 1, leaf->items + slot,
1192                         (nritems - slot) * sizeof(struct btrfs_item));
1193
1194                 /* shift the data */
1195                 memmove(btrfs_leaf_data(leaf) + data_end - data_size,
1196                         btrfs_leaf_data(leaf) +
1197                         data_end, old_data - data_end);
1198                 data_end = old_data;
1199         }
1200         /* setup the item for the new data */
1201         memcpy(&leaf->items[slot].key, &disk_key,
1202                 sizeof(struct btrfs_disk_key));
1203         btrfs_set_item_offset(leaf->items + slot, data_end - data_size);
1204         btrfs_set_item_size(leaf->items + slot, data_size);
1205         btrfs_set_header_nritems(&leaf->header, nritems + 1);
1206
1207         ret = 0;
1208         if (slot == 0)
1209                 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
1210
1211         BUG_ON(list_empty(&leaf_buf->dirty));
1212         if (btrfs_leaf_free_space(root, leaf) < 0)
1213                 BUG();
1214         check_leaf(root, path, 0);
1215 out:
1216         return ret;
1217 }
1218
1219 /*
1220  * Given a key and some data, insert an item into the tree.
1221  * This does all the path init required, making room in the tree if needed.
1222  */
1223 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
1224                       *root, struct btrfs_key *cpu_key, void *data, u32
1225                       data_size)
1226 {
1227         int ret = 0;
1228         struct btrfs_path path;
1229         u8 *ptr;
1230
1231         btrfs_init_path(&path);
1232         ret = btrfs_insert_empty_item(trans, root, &path, cpu_key, data_size);
1233         if (!ret) {
1234                 ptr = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], u8);
1235                 memcpy(ptr, data, data_size);
1236         }
1237         btrfs_release_path(root, &path);
1238         return ret;
1239 }
1240
1241 /*
1242  * delete the pointer from a given node.
1243  *
1244  * If the delete empties a node, the node is removed from the tree,
1245  * continuing all the way the root if required.  The root is converted into
1246  * a leaf if all the nodes are emptied.
1247  */
1248 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1249                    struct btrfs_path *path, int level, int slot)
1250 {
1251         struct btrfs_node *node;
1252         struct btrfs_buffer *parent = path->nodes[level];
1253         u32 nritems;
1254         int ret = 0;
1255         int wret;
1256
1257         node = &parent->node;
1258         nritems = btrfs_header_nritems(&node->header);
1259         if (slot != nritems -1) {
1260                 memmove(node->ptrs + slot, node->ptrs + slot + 1,
1261                         sizeof(struct btrfs_key_ptr) * (nritems - slot - 1));
1262         }
1263         nritems--;
1264         btrfs_set_header_nritems(&node->header, nritems);
1265         if (nritems == 0 && parent == root->node) {
1266                 BUG_ON(btrfs_header_level(&root->node->node.header) != 1);
1267                 /* just turn the root into a leaf and break */
1268                 btrfs_set_header_level(&root->node->node.header, 0);
1269         } else if (slot == 0) {
1270                 wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key,
1271                                       level + 1);
1272                 if (wret)
1273                         ret = wret;
1274         }
1275         BUG_ON(list_empty(&parent->dirty));
1276         return ret;
1277 }
1278
1279 /*
1280  * delete the item at the leaf level in path.  If that empties
1281  * the leaf, remove it from the tree
1282  */
1283 int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1284                    struct btrfs_path *path)
1285 {
1286         int slot;
1287         struct btrfs_leaf *leaf;
1288         struct btrfs_buffer *leaf_buf;
1289         int doff;
1290         int dsize;
1291         int ret = 0;
1292         int wret;
1293         u32 nritems;
1294
1295         leaf_buf = path->nodes[0];
1296         leaf = &leaf_buf->leaf;
1297         slot = path->slots[0];
1298         doff = btrfs_item_offset(leaf->items + slot);
1299         dsize = btrfs_item_size(leaf->items + slot);
1300         nritems = btrfs_header_nritems(&leaf->header);
1301
1302         if (slot != nritems - 1) {
1303                 int i;
1304                 int data_end = leaf_data_end(root, leaf);
1305                 memmove(btrfs_leaf_data(leaf) + data_end + dsize,
1306                         btrfs_leaf_data(leaf) + data_end,
1307                         doff - data_end);
1308                 for (i = slot + 1; i < nritems; i++) {
1309                         u32 ioff = btrfs_item_offset(leaf->items + i);
1310                         btrfs_set_item_offset(leaf->items + i, ioff + dsize);
1311                 }
1312                 memmove(leaf->items + slot, leaf->items + slot + 1,
1313                         sizeof(struct btrfs_item) *
1314                         (nritems - slot - 1));
1315         }
1316         btrfs_set_header_nritems(&leaf->header, nritems - 1);
1317         nritems--;
1318         /* delete the leaf if we've emptied it */
1319         if (nritems == 0) {
1320                 if (leaf_buf == root->node) {
1321                         btrfs_set_header_level(&leaf->header, 0);
1322                         BUG_ON(list_empty(&leaf_buf->dirty));
1323                 } else {
1324                         clean_tree_block(trans, root, leaf_buf);
1325                         wret = del_ptr(trans, root, path, 1, path->slots[1]);
1326                         if (wret)
1327                                 ret = wret;
1328                         wret = btrfs_free_extent(trans, root,
1329                                                  leaf_buf->blocknr, 1, 1);
1330                         if (wret)
1331                                 ret = wret;
1332                 }
1333         } else {
1334                 int used = leaf_space_used(leaf, 0, nritems);
1335                 if (slot == 0) {
1336                         wret = fixup_low_keys(trans, root, path,
1337                                               &leaf->items[0].key, 1);
1338                         if (wret)
1339                                 ret = wret;
1340                 }
1341                 BUG_ON(list_empty(&leaf_buf->dirty));
1342
1343                 /* delete the leaf if it is mostly empty */
1344                 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
1345                         /* push_leaf_left fixes the path.
1346                          * make sure the path still points to our leaf
1347                          * for possible call to del_ptr below
1348                          */
1349                         slot = path->slots[1];
1350                         leaf_buf->count++;
1351                         wret = push_leaf_left(trans, root, path, 1);
1352                         if (wret < 0)
1353                                 ret = wret;
1354                         if (path->nodes[0] == leaf_buf &&
1355                             btrfs_header_nritems(&leaf->header)) {
1356                                 wret = push_leaf_right(trans, root, path, 1);
1357                                 if (wret < 0)
1358                                         ret = wret;
1359                         }
1360                         if (btrfs_header_nritems(&leaf->header) == 0) {
1361                                 u64 blocknr = leaf_buf->blocknr;
1362                                 clean_tree_block(trans, root, leaf_buf);
1363                                 wret = del_ptr(trans, root, path, 1, slot);
1364                                 if (wret)
1365                                         ret = wret;
1366                                 btrfs_block_release(root, leaf_buf);
1367                                 wret = btrfs_free_extent(trans, root, blocknr,
1368                                                          1, 1);
1369                                 if (wret)
1370                                         ret = wret;
1371                         } else {
1372                                 btrfs_block_release(root, leaf_buf);
1373                         }
1374                 }
1375         }
1376         return ret;
1377 }
1378
1379 int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
1380                       *root, struct btrfs_path *path, u32 data_size)
1381 {
1382         int ret = 0;
1383         int slot;
1384         int slot_orig;
1385         struct btrfs_leaf *leaf;
1386         struct btrfs_buffer *leaf_buf;
1387         u32 nritems;
1388         unsigned int data_end;
1389         unsigned int old_data;
1390         unsigned int old_size;
1391         int i;
1392
1393         slot_orig = path->slots[0];
1394         leaf_buf = path->nodes[0];
1395         leaf = &leaf_buf->leaf;
1396
1397         nritems = btrfs_header_nritems(&leaf->header);
1398         data_end = leaf_data_end(root, leaf);
1399
1400         if (btrfs_leaf_free_space(root, leaf) < data_size)
1401                 BUG();
1402         slot = path->slots[0];
1403         old_data = btrfs_item_end(leaf->items + slot);
1404
1405         BUG_ON(slot < 0);
1406         BUG_ON(slot >= nritems);
1407
1408         /*
1409          * item0..itemN ... dataN.offset..dataN.size .. data0.size
1410          */
1411         /* first correct the data pointers */
1412         for (i = slot; i < nritems; i++) {
1413                 u32 ioff = btrfs_item_offset(leaf->items + i);
1414                 btrfs_set_item_offset(leaf->items + i,
1415                                       ioff - data_size);
1416         }
1417         /* shift the data */
1418         memmove(btrfs_leaf_data(leaf) + data_end - data_size,
1419                 btrfs_leaf_data(leaf) + data_end, old_data - data_end);
1420         data_end = old_data;
1421         old_size = btrfs_item_size(leaf->items + slot);
1422         btrfs_set_item_size(leaf->items + slot, old_size + data_size);
1423
1424         ret = 0;
1425         if (btrfs_leaf_free_space(root, leaf) < 0)
1426                 BUG();
1427         check_leaf(root, path, 0);
1428         return ret;
1429 }
1430
1431 /*
1432  * walk up the tree as far as required to find the next leaf.
1433  * returns 0 if it found something or 1 if there are no greater leaves.
1434  * returns < 0 on io errors.
1435  */
1436 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
1437 {
1438         int slot;
1439         int level = 1;
1440         u64 blocknr;
1441         struct btrfs_buffer *c;
1442         struct btrfs_buffer *next = NULL;
1443
1444         while(level < BTRFS_MAX_LEVEL) {
1445                 if (!path->nodes[level])
1446                         return 1;
1447                 slot = path->slots[level] + 1;
1448                 c = path->nodes[level];
1449                 if (slot >= btrfs_header_nritems(&c->node.header)) {
1450                         level++;
1451                         continue;
1452                 }
1453                 blocknr = btrfs_node_blockptr(&c->node, slot);
1454                 if (next)
1455                         btrfs_block_release(root, next);
1456                 next = read_tree_block(root, blocknr);
1457                 break;
1458         }
1459         path->slots[level] = slot;
1460         while(1) {
1461                 level--;
1462                 c = path->nodes[level];
1463                 btrfs_block_release(root, c);
1464                 path->nodes[level] = next;
1465                 path->slots[level] = 0;
1466                 if (!level)
1467                         break;
1468                 next = read_tree_block(root,
1469                                        btrfs_node_blockptr(&next->node, 0));
1470         }
1471         return 0;
1472 }