ctree.c

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