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