sys/vfs/hammer/hammer_btree.c

   1 /*
   2  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@backplane.com>
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  * 3. Neither the name of The DragonFly Project nor the names of its
  18  *    contributors may be used to endorse or promote products derived
  19  *    from this software without specific, prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  25  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  29  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  30  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  31  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  * $DragonFly: src/sys/vfs/hammer/hammer_btree.c,v 1.14 2007/12/31 05:33:12 dillon Exp $
  35  */
  36
  37 /*
  38  * HAMMER B-Tree index
  39  *
  40  * HAMMER implements a modified B+Tree.  In documentation this will
  41  * simply be refered to as the HAMMER B-Tree.  Basically a B-Tree
  42  * looks like a B+Tree (A B-Tree which stores its records only at the leafs
  43  * of the tree), but adds two additional boundary elements which describe
  44  * the left-most and right-most element a node is able to represent.  In
  45  * otherwords, we have boundary elements at the two ends of a B-Tree node
  46  * instead of sub-tree pointers.
  47  *
  48  * A B-Tree internal node looks like this:
  49  *
  50  *      B N N N N N N B   <-- boundary and internal elements
  51  *       S S S S S S S    <-- subtree pointers
  52  *
  53  * A B-Tree leaf node basically looks like this:
  54  *
  55  *      L L L L L L L L   <-- leaf elemenets
  56  *
  57  * The radix for an internal node is 1 less then a leaf but we get a
  58  * number of significant benefits for our troubles.
  59  *
  60  * The big benefit to using a B-Tree containing boundary information
  61  * is that it is possible to cache pointers into the middle of the tree
  62  * and not have to start searches, insertions, OR deletions at the root
  63  * node.   In particular, searches are able to progress in a definitive
  64  * direction from any point in the tree without revisting nodes.  This
  65  * greatly improves the efficiency of many operations, most especially
  66  * record appends.
  67  *
  68  * B-Trees also make the stacking of trees fairly straightforward.
  69  *
  70  * INTER-CLUSTER ELEMENTS:  An element of an internal node may reference
  71  * the root of another cluster rather then a node in the current cluster.
  72  * This is known as an inter-cluster references.  Only B-Tree searches
  73  * will cross cluster boundaries.  The rebalancing and collapse code does
  74  * not attempt to move children between clusters.  A major effect of this
  75  * is that we have to relax minimum element count requirements and allow
  76  * trees to become somewhat unabalanced.
  77  *
  78  * INSERTIONS AND DELETIONS:  When inserting we split full nodes on our
  79  * way down as an optimization.  I originally experimented with rebalancing
  80  * nodes on the way down for deletions but it created a huge mess due to
  81  * the way inter-cluster linkages work.  Instead, now I simply allow
  82  * the tree to become unbalanced and allow leaf nodes to become empty.
  83  * The delete code will try to clean things up from the bottom-up but
  84  * will stop if related elements are not in-core or if it cannot get a node
  85  * lock.
  86  */
  87 #include "hammer.h"
  88 #include <sys/buf.h>
  89 #include <sys/buf2.h>
  90
  91 static int btree_search(hammer_cursor_t cursor, int flags);
  92 static int btree_split_internal(hammer_cursor_t cursor);
  93 static int btree_split_leaf(hammer_cursor_t cursor);
  94 static int btree_remove(hammer_cursor_t cursor);
  95 static int btree_set_parent(hammer_node_t node, hammer_btree_elm_t elm);
  96 #if 0
  97 static int btree_rebalance(hammer_cursor_t cursor);
  98 static int btree_collapse(hammer_cursor_t cursor);
  99 #endif
 100 static int btree_node_is_full(hammer_node_ondisk_t node);
 101 static void hammer_make_separator(hammer_base_elm_t key1,
 102                         hammer_base_elm_t key2, hammer_base_elm_t dest);
 103
 104 /*
 105  * Iterate records after a search.  The cursor is iterated forwards past
 106  * the current record until a record matching the key-range requirements
 107  * is found.  ENOENT is returned if the iteration goes past the ending
 108  * key.
 109  *
 110  * The iteration is inclusive of key_beg and can be inclusive or exclusive
 111  * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
 112  *
 113  * cursor->key_beg may or may not be modified by this function during
 114  * the iteration.  XXX future - in case of an inverted lock we may have
 115  * to reinitiate the lookup and set key_beg to properly pick up where we
 116  * left off.
 117  */
 118 int
 119 hammer_btree_iterate(hammer_cursor_t cursor)
 120 {
 121         hammer_node_ondisk_t node;
 122         hammer_btree_elm_t elm;
 123         int error;
 124         int r;
 125         int s;
 126
 127         /*
 128          * Skip past the current record
 129          */
 130         node = cursor->node->ondisk;
 131         if (node == NULL)
 132                 return(ENOENT);
 133         if (cursor->index < node->count &&
 134             (cursor->flags & HAMMER_CURSOR_ATEDISK)) {
 135                 ++cursor->index;
 136         }
 137
 138         /*
 139          * Loop until an element is found or we are done.
 140          */
 141         for (;;) {
 142                 /*
 143                  * We iterate up the tree and then index over one element
 144                  * while we are at the last element in the current node.
 145                  *
 146                  * NOTE: This can pop us up to another cluster.
 147                  *
 148                  * If we are at the root of the root cluster, cursor_up
 149                  * returns ENOENT.
 150                  *
 151                  * NOTE: hammer_cursor_up() will adjust cursor->key_beg
 152                  * when told to re-search for the cluster tag.
 153                  *
 154                  * XXX this could be optimized by storing the information in
 155                  * the parent reference.
 156                  *
 157                  * XXX we can lose the node lock temporarily, this could mess
 158                  * up our scan.
 159                  */
 160                 if (cursor->index == node->count) {
 161                         error = hammer_cursor_up(cursor, 0);
 162                         if (error)
 163                                 break;
 164                         node = cursor->node->ondisk;
 165                         KKASSERT(cursor->index != node->count);
 166                         ++cursor->index;
 167                         continue;
 168                 }
 169
 170                 /*
 171                  * Check internal or leaf element.  Determine if the record
 172                  * at the cursor has gone beyond the end of our range.
 173                  * Remember that our key range is end-exclusive.
 174                  *
 175                  * Generally we recurse down through internal nodes.  An
 176                  * internal node can only be returned if INCLUSTER is set
 177                  * and the node represents a cluster-push record.  Internal
 178                  * elements do not contain create_tid/delete_tid information.
 179                  */
 180                 if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
 181                         elm = &node->elms[cursor->index];
 182                         r = hammer_btree_cmp(&cursor->key_end, &elm[0].base);
 183                         s = hammer_btree_cmp(&cursor->key_beg, &elm[1].base);
 184                         if (hammer_debug_btree) {
 185                                 kprintf("BRACKETL %p:%d %016llx %02x %016llx %d\n",
 186                                         cursor->node, cursor->index,
 187                                         elm[0].internal.base.obj_id,
 188                                         elm[0].internal.base.rec_type,
 189                                         elm[0].internal.base.key,
 190                                         r
 191                                 );
 192                                 kprintf("BRACKETR %p:%d %016llx %02x %016llx %d\n",
 193                                         cursor->node, cursor->index + 1,
 194                                         elm[1].internal.base.obj_id,
 195                                         elm[1].internal.base.rec_type,
 196                                         elm[1].internal.base.key,
 197                                         s
 198                                 );
 199                         }
 200
 201                         if (r < 0) {
 202                                 error = ENOENT;
 203                                 break;
 204                         }
 205                         if (r == 0 && (cursor->flags & HAMMER_CURSOR_END_INCLUSIVE) == 0) {
 206                                 error = ENOENT;
 207                                 break;
 208                         }
 209                         KKASSERT(s <= 0);
 210                         if ((cursor->flags & HAMMER_CURSOR_INCLUSTER) == 0 ||
 211                             elm->internal.rec_offset == 0) {
 212                                 error = hammer_cursor_down(cursor);
 213                                 if (error)
 214                                         break;
 215                                 KKASSERT(cursor->index == 0);
 216                                 node = cursor->node->ondisk;
 217                                 continue;
 218                         }
 219                 } else {
 220                         elm = &node->elms[cursor->index];
 221                         r = hammer_btree_cmp(&cursor->key_end, &elm->base);
 222                         if (hammer_debug_btree) {
 223                                 kprintf("ELEMENT  %p:%d %016llx %02x %016llx %d\n",
 224                                         cursor->node, cursor->index,
 225                                         elm[0].leaf.base.obj_id,
 226                                         elm[0].leaf.base.rec_type,
 227                                         elm[0].leaf.base.key,
 228                                         r
 229                                 );
 230                         }
 231                         if (r < 0) {
 232                                 error = ENOENT;
 233                                 break;
 234                         }
 235                         if (r == 0 && (cursor->flags & HAMMER_CURSOR_END_INCLUSIVE) == 0) {
 236                                 error = ENOENT;
 237                                 break;
 238                         }
 239                         if ((cursor->flags & HAMMER_CURSOR_ALLHISTORY) == 0 &&
 240                             hammer_btree_chkts(cursor->key_beg.create_tid,
 241                                                &elm->base) != 0) {
 242                                 ++cursor->index;
 243                                 continue;
 244                         }
 245                 }
 246
 247                 /*
 248                  * Return entry
 249                  */
 250                 if (hammer_debug_btree) {
 251                         int i = cursor->index;
 252                         hammer_btree_elm_t elm = &cursor->node->ondisk->elms[i];
 253                         kprintf("ITERATE  %p:%d %016llx %02x %016llx\n",
 254                                 cursor->node, i,
 255                                 elm->internal.base.obj_id,
 256                                 elm->internal.base.rec_type,
 257                                 elm->internal.base.key
 258                         );
 259                 }
 260                 return(0);
 261         }
 262         return(error);
 263 }
 264
 265 /*
 266  * Lookup cursor->key_beg.  0 is returned on success, ENOENT if the entry
 267  * could not be found, and a fatal error otherwise.
 268  *
 269  * The cursor is suitably positioned for a deletion on success, and suitably
 270  * positioned for an insertion on ENOENT.
 271  *
 272  * The cursor may begin anywhere, the search will traverse clusters in
 273  * either direction to locate the requested element.
 274  */
 275 int
 276 hammer_btree_lookup(hammer_cursor_t cursor)
 277 {
 278         int error;
 279
 280         error = btree_search(cursor, 0);
 281         if (error == 0 && cursor->flags)
 282                 error = hammer_btree_extract(cursor, cursor->flags);
 283         return(error);
 284 }
 285
 286 /*
 287  * Execute the logic required to start an iteration.  The first record
 288  * located within the specified range is returned and iteration control
 289  * flags are adjusted for successive hammer_btree_iterate() calls.
 290  */
 291 int
 292 hammer_btree_first(hammer_cursor_t cursor)
 293 {
 294         int error;
 295
 296         error = hammer_btree_lookup(cursor);
 297         if (error == ENOENT) {
 298                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
 299                 error = hammer_btree_iterate(cursor);
 300         }
 301         cursor->flags |= HAMMER_CURSOR_ATEDISK;
 302         return(error);
 303 }
 304
 305 /*
 306  * Extract the record and/or data associated with the cursor's current
 307  * position.  Any prior record or data stored in the cursor is replaced.
 308  * The cursor must be positioned at a leaf node.
 309  *
 310  * NOTE: Most extractions occur at the leaf of the B-Tree.  The only
 311  *       extraction allowed at an internal element is at a cluster-push.
 312  *       Cluster-push elements have records but no data.
 313  */
 314 int
 315 hammer_btree_extract(hammer_cursor_t cursor, int flags)
 316 {
 317         hammer_node_ondisk_t node;
 318         hammer_btree_elm_t elm;
 319         hammer_cluster_t cluster;
 320         u_int64_t buf_type;
 321         int32_t cloff;
 322         int32_t roff;
 323         int error;
 324
 325         /*
 326          * A cluster record type has no data reference, the information
 327          * is stored directly in the record and B-Tree element.
 328          *
 329          * The case where the data reference resolves to the same buffer
 330          * as the record reference must be handled.
 331          */
 332         node = cursor->node->ondisk;
 333         elm = &node->elms[cursor->index];
 334         cluster = cursor->node->cluster;
 335         cursor->flags &= ~HAMMER_CURSOR_DATA_EMBEDDED;
 336         cursor->data = NULL;
 337         error = 0;
 338
 339         /*
 340          * Internal elements can only be cluster pushes.  A cluster push has
 341          * no data reference.
 342          */
 343         if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
 344                 cloff = elm->leaf.rec_offset;
 345                 KKASSERT(cloff != 0);
 346                 cursor->record = hammer_bread(cluster, cloff,
 347                                               HAMMER_FSBUF_RECORDS, &error,
 348                                               &cursor->record_buffer);
 349                 return(error);
 350         }
 351
 352         /*
 353          * Leaf element.
 354          */
 355         if ((flags & HAMMER_CURSOR_GET_RECORD) && error == 0) {
 356                 cloff = elm->leaf.rec_offset;
 357                 cursor->record = hammer_bread(cluster, cloff,
 358                                               HAMMER_FSBUF_RECORDS, &error,
 359                                               &cursor->record_buffer);
 360         } else {
 361                 cloff = 0;
 362         }
 363         if ((flags & HAMMER_CURSOR_GET_DATA) && error == 0) {
 364                 if ((cloff ^ elm->leaf.data_offset) & ~HAMMER_BUFMASK) {
 365                         /*
 366                          * The data is not in the same buffer as the last
 367                          * record we cached, but it could still be embedded
 368                          * in a record.  Note that we may not have loaded the
 369                          * record's buffer above, depending on flags.
 370                          */
 371                         if ((elm->leaf.rec_offset ^ elm->leaf.data_offset) &
 372                             ~HAMMER_BUFMASK) {
 373                                 if (elm->leaf.data_len & HAMMER_BUFMASK)
 374                                         buf_type = HAMMER_FSBUF_DATA;
 375                                 else
 376                                         buf_type = 0;   /* pure data buffer */
 377                         } else {
 378                                 buf_type = HAMMER_FSBUF_RECORDS;
 379                         }
 380                         cursor->data = hammer_bread(cluster,
 381                                                   elm->leaf.data_offset,
 382                                                   buf_type, &error,
 383                                                   &cursor->data_buffer);
 384                 } else {
 385                         /*
 386                          * Data in same buffer as record.  Note that we
 387                          * leave any existing data_buffer intact, even
 388                          * though we don't use it in this case, in case
 389                          * other records extracted during an iteration
 390                          * go back to it.
 391                          *
 392                          * The data must be embedded in the record for this
 393                          * case to be hit.
 394                          *
 395                          * Just assume the buffer type is correct.
 396                          */
 397                         cursor->data = (void *)
 398                                 ((char *)cursor->record_buffer->ondisk +
 399                                  (elm->leaf.data_offset & HAMMER_BUFMASK));
 400                         roff = (char *)cursor->data - (char *)cursor->record;
 401                         KKASSERT (roff >= 0 && roff < HAMMER_RECORD_SIZE);
 402                         cursor->flags |= HAMMER_CURSOR_DATA_EMBEDDED;
 403                 }
 404         }
 405         return(error);
 406 }
 407
 408
 409 /*
 410  * Insert a leaf element into the B-Tree at the current cursor position.
 411  * The cursor is positioned such that the element at and beyond the cursor
 412  * are shifted to make room for the new record.
 413  *
 414  * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
 415  * flag set and that call must return ENOENT before this function can be
 416  * called.
 417  *
 418  * ENOSPC is returned if there is no room to insert a new record.
 419  */
 420 int
 421 hammer_btree_insert(hammer_cursor_t cursor, hammer_btree_elm_t elm)
 422 {
 423         hammer_node_ondisk_t parent;
 424         hammer_node_ondisk_t node;
 425         int i;
 426
 427 #if 0
 428         /* HANDLED BY CALLER */
 429         /*
 430          * Issue a search to get our cursor at the right place.  The search
 431          * will get us to a leaf node.
 432          *
 433          * The search also does some setup for our insert, so there is always
 434          * room in the leaf.
 435          */
 436         error = btree_search(cursor, HAMMER_CURSOR_INSERT);
 437         if (error != ENOENT) {
 438                 if (error == 0)
 439                         error = EEXIST;
 440                 return (error);
 441         }
 442 #endif
 443
 444         /*
 445          * Insert the element at the leaf node and update the count in the
 446          * parent.  It is possible for parent to be NULL, indicating that
 447          * the root of the B-Tree in the cluster is a leaf.  It is also
 448          * possible for the leaf to be empty.
 449          *
 450          * Remember that the right-hand boundary is not included in the
 451          * count.
 452          */
 453         hammer_modify_node(cursor->node);
 454         node = cursor->node->ondisk;
 455         i = cursor->index;
 456         KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
 457         KKASSERT(node->count < HAMMER_BTREE_LEAF_ELMS);
 458         if (i != node->count) {
 459                 bcopy(&node->elms[i], &node->elms[i+1],
 460                       (node->count - i) * sizeof(*elm));
 461         }
 462         node->elms[i] = *elm;
 463         ++node->count;
 464         hammer_modify_node_done(cursor->node);
 465
 466         KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm->leaf.base) <= 0);
 467         KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm->leaf.base) > 0);
 468         if (i)
 469                 KKASSERT(hammer_btree_cmp(&node->elms[i-1].leaf.base, &elm->leaf.base) < 0);
 470         if (i != node->count - 1)
 471                 KKASSERT(hammer_btree_cmp(&node->elms[i+1].leaf.base, &elm->leaf.base) > 0);
 472
 473         /*
 474          * Adjust the sub-tree count in the parent.  note that the parent
 475          * may be in a different cluster.
 476          */
 477         if (cursor->parent) {
 478                 hammer_modify_node(cursor->parent);
 479                 parent = cursor->parent->ondisk;
 480                 i = cursor->parent_index;
 481                 ++parent->elms[i].internal.subtree_count;
 482                 hammer_modify_node_done(cursor->parent);
 483                 KKASSERT(parent->elms[i].internal.subtree_count <= node->count);
 484         }
 485         return(0);
 486 }
 487
 488 /*
 489  * Delete a record from the B-Tree's at the current cursor position.
 490  * The cursor is positioned such that the current element is the one
 491  * to be deleted.
 492  *
 493  * On return the cursor will be positioned after the deleted element and
 494  * MAY point to an internal node.  It will be suitable for the continuation
 495  * of an iteration but not for an insertion or deletion.
 496  *
 497  * Deletions will attempt to partially rebalance the B-Tree in an upward
 498  * direction.  It is possible to end up with empty leafs.  An empty internal
 499  * node is impossible (worst case: it has one element pointing to an empty
 500  * leaf).
 501  */
 502 int
 503 hammer_btree_delete(hammer_cursor_t cursor)
 504 {
 505         hammer_node_ondisk_t ondisk;
 506         hammer_node_t node;
 507         hammer_node_t parent;
 508         hammer_btree_elm_t elm;
 509         int error;
 510         int i;
 511
 512 #if 0
 513         /* HANDLED BY CALLER */
 514         /*
 515          * Locate the leaf element to delete.  The search is also responsible
 516          * for doing some of the rebalancing work on its way down.
 517          */
 518         error = btree_search(cursor, HAMMER_CURSOR_DELETE);
 519         if (error)
 520                 return (error);
 521 #endif
 522
 523         /*
 524          * Delete the element from the leaf node.
 525          *
 526          * Remember that leaf nodes do not have boundaries.
 527          */
 528         node = cursor->node;
 529         ondisk = node->ondisk;
 530         i = cursor->index;
 531
 532         KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_LEAF);
 533         hammer_modify_node(node);
 534         if (i + 1 != ondisk->count) {
 535                 bcopy(&ondisk->elms[i+1], &ondisk->elms[i],
 536                       (ondisk->count - i - 1) * sizeof(ondisk->elms[0]));
 537         }
 538         --ondisk->count;
 539         hammer_modify_node_done(node);
 540         if (cursor->parent != NULL) {
 541                 /*
 542                  * Adjust parent's notion of the leaf's count.  subtree_count
 543                  * is only approximate, it is allowed to be too small but
 544                  * never allowed to be too large.  Make sure we don't drop
 545                  * the count below 0.
 546                  */
 547                 parent = cursor->parent;
 548                 hammer_modify_node(parent);
 549                 elm = &parent->ondisk->elms[cursor->parent_index];
 550                 if (elm->internal.subtree_count)
 551                         --elm->internal.subtree_count;
 552                 hammer_modify_node_done(parent);
 553                 KKASSERT(elm->internal.subtree_count <= ondisk->count);
 554         }
 555
 556         /*
 557          * It is possible, but not desireable, to stop here.  If the element
 558          * count drops to 0 (which is allowed for a leaf), try recursively
 559          * remove the B-Tree node.
 560          *
 561          * XXX rebalancing calls would go here too.
 562          *
 563          * This may reposition the cursor at one of the parent's of the
 564          * current node.
 565          */
 566         KKASSERT(cursor->index <= ondisk->count);
 567         if (ondisk->count == 0) {
 568                 error = btree_remove(cursor);
 569                 if (error == EAGAIN)
 570                         error = 0;
 571         } else {
 572                 error = 0;
 573         }
 574         return(error);
 575 }
 576
 577 /*
 578  * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
 579  *
 580  * Search a cluster's B-Tree for cursor->key_beg, return the matching node.
 581  *
 582  * The search can begin ANYWHERE in the B-Tree.  As a first step the search
 583  * iterates up the tree as necessary to properly position itself prior to
 584  * actually doing the sarch.
 585  *
 586  * INSERTIONS: The search will split full nodes and leaves on its way down
 587  * and guarentee that the leaf it ends up on is not full.  If we run out
 588  * of space the search continues to the leaf (to position the cursor for
 589  * the spike), but ENOSPC is returned.
 590  *
 591  * DELETIONS: The search will rebalance the tree on its way down. XXX
 592  *
 593  * The search is only guarenteed to end up on a leaf if an error code of 0
 594  * is returned, or if inserting and an error code of ENOENT is returned.
 595  * Otherwise it can stop at an internal node.  On success a search returns
 596  * a leaf node unless INCLUSTER is set and the search located a cluster push
 597  * node (which is an internal node).
 598  */
 599 static
 600 int
 601 btree_search(hammer_cursor_t cursor, int flags)
 602 {
 603         hammer_node_ondisk_t node;
 604         hammer_cluster_t cluster;
 605         int error;
 606         int enospc = 0;
 607         int i;
 608         int r;
 609
 610         flags |= cursor->flags;
 611
 612         if (hammer_debug_btree) {
 613                 kprintf("SEARCH   %p:%d %016llx %02x %016llx\n",
 614                         cursor->node, cursor->index,
 615                         cursor->key_beg.obj_id,
 616                         cursor->key_beg.rec_type,
 617                         cursor->key_beg.key
 618                 );
 619         }
 620
 621         /*
 622          * Move our cursor up the tree until we find a node whos range covers
 623          * the key we are trying to locate.  This may move us between
 624          * clusters.
 625          *
 626          * The left bound is inclusive, the right bound is non-inclusive.
 627          * It is ok to cursor up too far so when cursoring across a cluster
 628          * boundary.
 629          *
 630          * First see if we can skip the whole cluster.  hammer_cursor_up()
 631          * handles both cases but this way we don't check the cluster
 632          * bounds when going up the tree within a cluster.
 633          *
 634          * NOTE: If INCLUSTER is set and we are at the root of the cluster,
 635          * hammer_cursor_up() will return ENOENT.
 636          */
 637         cluster = cursor->node->cluster;
 638         while (
 639             hammer_btree_cmp(&cursor->key_beg, &cluster->clu_btree_beg) < 0 ||
 640             hammer_btree_cmp(&cursor->key_beg, &cluster->clu_btree_end) >= 0) {
 641                 error = hammer_cursor_toroot(cursor);
 642                 if (error)
 643                         goto done;
 644                 error = hammer_cursor_up(cursor, 0);
 645                 if (error)
 646                         goto done;
 647                 cluster = cursor->node->cluster;
 648         }
 649
 650         /*
 651          * Deal with normal cursoring within a cluster.  The right bound
 652          * is non-inclusive.  That is, the bounds form a separator.
 653          */
 654         while (hammer_btree_cmp(&cursor->key_beg, cursor->left_bound) < 0 ||
 655                hammer_btree_cmp(&cursor->key_beg, cursor->right_bound) >= 0) {
 656                 error = hammer_cursor_up(cursor, 0);
 657                 if (error)
 658                         goto done;
 659         }
 660
 661         /*
 662          * We better have ended up with a node somewhere, and our second
 663          * while loop had better not have traversed up a cluster.
 664          */
 665         KKASSERT(cursor->node != NULL && cursor->node->cluster == cluster);
 666
 667         /*
 668          * If we are inserting we can't start at a full node if the parent
 669          * is also full (because there is no way to split the node),
 670          * continue running up the tree until we hit the root of the
 671          * root cluster or until the requirement is satisfied.
 672          *
 673          * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
 674          *
 675          * XXX as an optimization it should be possible to unbalance the tree
 676          * and stop at the root of the current cluster.
 677          */
 678         while (flags & HAMMER_CURSOR_INSERT) {
 679                 if (btree_node_is_full(cursor->node->ondisk) == 0)
 680                         break;
 681                 if (cursor->parent == NULL)
 682                         break;
 683                 if (cursor->parent->ondisk->count != HAMMER_BTREE_INT_ELMS)
 684                         break;
 685                 error = hammer_cursor_up(cursor, 0);
 686                 /* cluster and node are now may become stale */
 687                 if (error)
 688                         goto done;
 689         }
 690         /* cluster = cursor->node->cluster; not needed until next cluster = */
 691
 692 #if 0
 693         /*
 694          * If we are deleting we can't start at an internal node with only
 695          * one element unless it is root, because all of our code assumes
 696          * that internal nodes will never be empty.  Just do this generally
 697          * for both leaf and internal nodes to get better balance.
 698          *
 699          * This handles the case where the cursor is sitting at a leaf and
 700          * either the leaf or parent contain an insufficient number of
 701          * elements.
 702          *
 703          * NOTE: These cursor-up's CAN continue to cross cluster boundaries.
 704          *
 705          * XXX NOTE: Iterations may not set this flag anyway.
 706          */
 707         while (flags & HAMMER_CURSOR_DELETE) {
 708                 if (cursor->node->ondisk->count > 1)
 709                         break;
 710                 if (cursor->parent == NULL)
 711                         break;
 712                 KKASSERT(cursor->node->ondisk->count != 0);
 713                 error = hammer_cursor_up(cursor, 0);
 714                 /* cluster and node are now may become stale */
 715                 if (error)
 716                         goto done;
 717         }
 718 #endif
 719
 720 /*new_cluster:*/
 721         /*
 722          * Push down through internal nodes to locate the requested key.
 723          */
 724         cluster = cursor->node->cluster;
 725         node = cursor->node->ondisk;
 726         while (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
 727 #if 0
 728                 /*
 729                  * If we are a the root node and deleting, try to collapse
 730                  * all of the root's children into the root.  This is the
 731                  * only point where tree depth is reduced.
 732                  *
 733                  * XXX NOTE: Iterations may not set this flag anyway.
 734                  */
 735                 if ((flags & HAMMER_CURSOR_DELETE) && cursor->parent == NULL) {
 736                         error = btree_collapse(cursor);
 737                         /* node becomes stale after call */
 738                         /* XXX ENOSPC */
 739                         if (error)
 740                                 goto done;
 741                 }
 742                 node = cursor->node->ondisk;
 743 #endif
 744                 /*
 745                  * Scan the node to find the subtree index to push down into.
 746                  * We go one-past, then back-up.
 747                  */
 748                 for (i = 0; i < node->count; ++i) {
 749                         r = hammer_btree_cmp(&cursor->key_beg,
 750                                              &node->elms[i].base);
 751                         if (r < 0)
 752                                 break;
 753                 }
 754
 755                 /*
 756                  * It is possible for the search to terminate at i == 0,
 757                  * which is to the LEFT of the LEFT boundary but the RIGHT
 758                  * of the parent's boundary on the left of the sub-tree
 759                  * element.  This case can occur due to deletions (see
 760                  * btree_remove()).
 761                  *
 762                  * When this case occurs an ENOENT return is guarenteed but
 763                  * if inserting we must still terminate at a leaf.  The
 764                  * solution is to make the node's left boundary inherit the
 765                  * boundary stored in the parent.
 766                  *
 767                  * When doing this inheritance some fields in 'base' are
 768                  * actually related to the internal element's child
 769                  * specification and not to the key.  These have to be
 770                  * retained.
 771                  *
 772                  * If we terminate at i == count it is still possible to
 773                  * be to the RIGHT of the RIGHT boundary but still to the
 774                  * LEFT of the parent's RIGHT boundary.  The solution is to
 775                  * adjust the RIGHT boundary to match the parent.  This
 776                  * case can occur due to deletions (see btree_remove()).
 777                  */
 778                 if (i == 0) {
 779                         u_int8_t save;
 780
 781                         if ((flags & HAMMER_CURSOR_INSERT) == 0) {
 782                                 cursor->index = 0;
 783                                 return(ENOENT);
 784                         }
 785                         hammer_modify_node(cursor->node);
 786                         save = node->elms[0].subtree_type;
 787                         node->elms[0].base = *cursor->left_bound;
 788                         node->elms[0].subtree_type = save;
 789                         hammer_modify_node_done(cursor->node);
 790                 } else if (i == node->count) {
 791                         /*
 792                          * Terminate early if not inserting and the key is
 793                          * beyond the uncorrected right hand boundary.  The
 794                          * index must be PAST the last element to prevent an
 795                          * iteration from returning elements to the left of
 796                          * key_beg.
 797                          */
 798                         if ((flags & HAMMER_CURSOR_INSERT) == 0 &&
 799                             hammer_btree_cmp(&cursor->key_beg,
 800                                              &node->elms[i].base) >= 0
 801                         ) {
 802                                 cursor->index = i;
 803                                 return(ENOENT);
 804                         }
 805
 806                         /*
 807                          * Correct a right-hand boundary mismatch.  The push
 808                          * index is the last element (i-1).
 809                          */
 810                         if (hammer_btree_cmp(&node->elms[i].base,
 811                                              cursor->right_bound) != 0) {
 812                                 hammer_modify_node(cursor->node);
 813                                 node->elms[i].base = *cursor->right_bound;
 814                                 hammer_modify_node_done(cursor->node);
 815                         }
 816                         --i;
 817                 } else {
 818                         /*
 819                          * The push-down index is now i - 1.
 820                          */
 821                         --i;
 822                 }
 823                 cursor->index = i;
 824
 825                 if (hammer_debug_btree) {
 826                         hammer_btree_elm_t elm = &node->elms[i];
 827                         kprintf("SEARCH-I %p:%d %016llx %02x %016llx\n",
 828                                 cursor->node, i,
 829                                 elm->internal.base.obj_id,
 830                                 elm->internal.base.rec_type,
 831                                 elm->internal.base.key
 832                         );
 833                 }
 834
 835                 /*
 836                  * Handle insertion and deletion requirements.
 837                  *
 838                  * If inserting split full nodes.  The split code will
 839                  * adjust cursor->node and cursor->index if the current
 840                  * index winds up in the new node.
 841                  */
 842                 if (flags & HAMMER_CURSOR_INSERT) {
 843                         if (node->count == HAMMER_BTREE_INT_ELMS) {
 844                                 error = btree_split_internal(cursor);
 845                                 if (error) {
 846                                         if (error != ENOSPC)
 847                                                 goto done;
 848                                         enospc = 1;
 849                                         flags &= ~HAMMER_CURSOR_INSERT;
 850                                 }
 851                                 /*
 852                                  * reload stale pointers
 853                                  */
 854                                 i = cursor->index;
 855                                 node = cursor->node->ondisk;
 856                         }
 857                 }
 858
 859 #if 0
 860                 /*
 861                  * If deleting rebalance - do not allow the child to have
 862                  * just one element or we will not be able to delete it.
 863                  *
 864                  * Neither internal or leaf nodes (except a root-leaf) are
 865                  * allowed to drop to 0 elements.  (XXX - well, leaf nodes
 866                  * can at the moment).
 867                  *
 868                  * Our separators may have been reorganized after rebalancing,
 869                  * so we have to pop back up and rescan.
 870                  *
 871                  * XXX test for subtree_count < maxelms / 2, minus 1 or 2
 872                  * for hysteresis?
 873                  *
 874                  * XXX NOTE: Iterations may not set this flag anyway.
 875                  */
 876                 if (flags & HAMMER_CURSOR_DELETE) {
 877                         if (node->elms[i].internal.subtree_count <= 1) {
 878                                 error = btree_rebalance(cursor);
 879                                 if (error)
 880                                         goto done;
 881                                 /* cursor->index is invalid after call */
 882                                 goto new_cluster;
 883                         }
 884                 }
 885 #endif
 886                 /*
 887                  * Cluster pushes are done with internal elements.  If this
 888                  * is a cluster push (rec_offset != 0), and INCLUSTER is set,
 889                  * we stop here.
 890                  *
 891                  * However, because this is an internal node we have to
 892                  * determine whether key_beg is within its range and return
 893                  * 0 or ENOENT appropriately.
 894                  */
 895                 if ((flags & HAMMER_CURSOR_INCLUSTER) &&
 896                     node->elms[i].internal.rec_offset) {
 897                         r = hammer_btree_cmp(&cursor->key_beg,
 898                                              &node->elms[i+1].base);
 899                         error = (r < 0) ? 0 : (enospc ? ENOSPC : ENOENT);
 900                         goto done;
 901                 }
 902
 903                 /*
 904                  * Push down (push into new node, existing node becomes
 905                  * the parent) and continue the search.
 906                  */
 907                 error = hammer_cursor_down(cursor);
 908                 /* node and cluster become stale */
 909                 if (error)
 910                         goto done;
 911                 node = cursor->node->ondisk;
 912                 cluster = cursor->node->cluster;
 913         }
 914
 915         /*
 916          * We are at a leaf, do a linear search of the key array.
 917          *
 918          * On success the index is set to the matching element and 0
 919          * is returned.
 920          *
 921          * On failure the index is set to the insertion point and ENOENT
 922          * is returned.
 923          *
 924          * Boundaries are not stored in leaf nodes, so the index can wind
 925          * up to the left of element 0 (index == 0) or past the end of
 926          * the array (index == node->count).
 927          */
 928         KKASSERT(node->count <= HAMMER_BTREE_LEAF_ELMS);
 929
 930         for (i = 0; i < node->count; ++i) {
 931                 r = hammer_btree_cmp(&cursor->key_beg, &node->elms[i].base);
 932
 933                 /*
 934                  * Stop if we've flipped past key_beg
 935                  */
 936                 if (r < 0)
 937                         break;
 938
 939                 /*
 940                  * Return an exact match
 941                  */
 942                 if (r == 0) {
 943                         cursor->index = i;
 944                         error = 0;
 945                         if (hammer_debug_btree) {
 946                                 kprintf("SEARCH-L %p:%d (SUCCESS)\n",
 947                                         cursor->node, i);
 948                         }
 949                         goto done;
 950                 }
 951         }
 952
 953         if (hammer_debug_btree) {
 954                 kprintf("SEARCH-L %p:%d (FAILED)\n",
 955                         cursor->node, i);
 956         }
 957
 958         /*
 959          * No exact match was found, i is now at the insertion point.
 960          *
 961          * If inserting split a full leaf before returning.  This
 962          * may have the side effect of adjusting cursor->node and
 963          * cursor->index.
 964          */
 965         cursor->index = i;
 966         if ((flags & HAMMER_CURSOR_INSERT) &&
 967             node->count == HAMMER_BTREE_LEAF_ELMS) {
 968                 error = btree_split_leaf(cursor);
 969                 if (error) {
 970                         if (error != ENOSPC)
 971                                 goto done;
 972                         enospc = 1;
 973                         flags &= ~HAMMER_CURSOR_INSERT;
 974                 }
 975                 /*
 976                  * reload stale pointers
 977                  */
 978                 /* NOT USED
 979                 i = cursor->index;
 980                 node = &cursor->node->internal;
 981                 */
 982         }
 983
 984         /*
 985          * We reached a leaf but did not find the key we were looking for.
 986          * If this is an insert we will be properly positioned for an insert
 987          * (ENOENT) or spike (ENOSPC) operation.
 988          */
 989         error = enospc ? ENOSPC : ENOENT;
 990 done:
 991         return(error);
 992 }
 993
 994
 995 /************************************************************************
 996  *                         SPLITTING AND MERGING                        *
 997  ************************************************************************
 998  *
 999  * These routines do all the dirty work required to split and merge nodes.
1000  */
1001
1002 /*
1003  * Split an internal node into two nodes and move the separator at the split
1004  * point to the parent.  Note that the parent's parent's element pointing
1005  * to our parent will have an incorrect subtree_count (we don't update it).
1006  * It will be low, which is ok.
1007  *
1008  * (cursor->node, cursor->index) indicates the element the caller intends
1009  * to push into.  We will adjust node and index if that element winds
1010  * up in the split node.
1011  *
1012  * If we are at the root of a cluster a new root must be created with two
1013  * elements, one pointing to the original root and one pointing to the
1014  * newly allocated split node.
1015  *
1016  * NOTE! Being at the root of a cluster is different from being at the
1017  * root of the root cluster.  cursor->parent will not be NULL and
1018  * cursor->node->ondisk.parent must be tested against 0.  Theoretically
1019  * we could propogate the algorithm into the parent and deal with multiple
1020  * 'roots' in the cluster header, but it's easier not to.
1021  */
1022 static
1023 int
1024 btree_split_internal(hammer_cursor_t cursor)
1025 {
1026         hammer_node_ondisk_t ondisk;
1027         hammer_node_t node;
1028         hammer_node_t parent;
1029         hammer_node_t new_node;
1030         hammer_btree_elm_t elm;
1031         hammer_btree_elm_t parent_elm;
1032         int parent_index;
1033         int made_root;
1034         int split;
1035         int error;
1036         int i;
1037         const int esize = sizeof(*elm);
1038
1039         /*
1040          * We are splitting but elms[split] will be promoted to the parent,
1041          * leaving the right hand node with one less element.  If the
1042          * insertion point will be on the left-hand side adjust the split
1043          * point to give the right hand side one additional node.
1044          */
1045         node = cursor->node;
1046         ondisk = node->ondisk;
1047         split = (ondisk->count + 1) / 2;
1048         if (cursor->index <= split)
1049                 --split;
1050         error = 0;
1051
1052         /*
1053          * If we are at the root of the cluster, create a new root node with
1054          * 1 element and split normally.  Avoid making major modifications
1055          * until we know the whole operation will work.
1056          *
1057          * The root of the cluster is different from the root of the root
1058          * cluster.  Use the node's on-disk structure's parent offset to
1059          * detect the case.
1060          */
1061         if (ondisk->parent == 0) {
1062                 parent = hammer_alloc_btree(node->cluster, &error);
1063                 if (parent == NULL)
1064                         return(error);
1065                 hammer_lock_ex(&parent->lock);
1066                 hammer_modify_node(parent);
1067                 ondisk = parent->ondisk;
1068                 ondisk->count = 1;
1069                 ondisk->parent = 0;
1070                 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1071                 ondisk->elms[0].base = node->cluster->clu_btree_beg;
1072                 ondisk->elms[0].internal.subtree_type = node->ondisk->type;
1073                 ondisk->elms[0].internal.subtree_offset = node->node_offset;
1074                 ondisk->elms[1].base = node->cluster->clu_btree_end;
1075                 made_root = 1;
1076                 parent_index = 0;       /* index of current node in parent */
1077                 hammer_modify_node_done(parent);
1078         } else {
1079                 made_root = 0;
1080                 parent = cursor->parent;
1081                 parent_index = cursor->parent_index;
1082                 KKASSERT(parent->cluster == node->cluster);
1083         }
1084
1085         /*
1086          * Split node into new_node at the split point.
1087          *
1088          *  B O O O P N N B     <-- P = node->elms[split]
1089          *   0 1 2 3 4 5 6      <-- subtree indices
1090          *
1091          *       x x P x x
1092          *        s S S s
1093          *         /   \
1094          *  B O O O B    B N N B        <--- inner boundary points are 'P'
1095          *   0 1 2 3      4 5 6
1096          *
1097          */
1098         new_node = hammer_alloc_btree(node->cluster, &error);
1099         if (new_node == NULL) {
1100                 if (made_root) {
1101                         hammer_unlock(&parent->lock);
1102                         parent->flags |= HAMMER_NODE_DELETED;
1103                         hammer_rel_node(parent);
1104                 }
1105                 return(error);
1106         }
1107         hammer_lock_ex(&new_node->lock);
1108
1109         /*
1110          * Create the new node.  P becomes the left-hand boundary in the
1111          * new node.  Copy the right-hand boundary as well.
1112          *
1113          * elm is the new separator.
1114          */
1115         hammer_modify_node(new_node);
1116         hammer_modify_node(node);
1117         ondisk = node->ondisk;
1118         elm = &ondisk->elms[split];
1119         bcopy(elm, &new_node->ondisk->elms[0],
1120               (ondisk->count - split + 1) * esize);
1121         new_node->ondisk->count = ondisk->count - split;
1122         new_node->ondisk->parent = parent->node_offset;
1123         new_node->ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1124         KKASSERT(ondisk->type == new_node->ondisk->type);
1125
1126         /*
1127          * Cleanup the original node.  P becomes the new boundary, its
1128          * subtree_offset was moved to the new node.  If we had created
1129          * a new root its parent pointer may have changed.
1130          */
1131         elm->internal.subtree_offset = 0;
1132         elm->internal.rec_offset = 0;
1133         ondisk->count = split;
1134
1135         /*
1136          * Insert the separator into the parent, fixup the parent's
1137          * reference to the original node, and reference the new node.
1138          * The separator is P.
1139          *
1140          * Remember that base.count does not include the right-hand boundary.
1141          */
1142         hammer_modify_node(parent);
1143         ondisk = parent->ondisk;
1144         KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
1145         ondisk->elms[parent_index].internal.subtree_count = split;
1146         parent_elm = &ondisk->elms[parent_index+1];
1147         bcopy(parent_elm, parent_elm + 1,
1148               (ondisk->count - parent_index) * esize);
1149         parent_elm->internal.base = elm->base;  /* separator P */
1150         parent_elm->internal.subtree_offset = new_node->node_offset;
1151         parent_elm->internal.subtree_count = new_node->ondisk->count;
1152         parent_elm->internal.subtree_type = new_node->ondisk->type;
1153         parent_elm->internal.subtree_vol_no = 0;
1154         parent_elm->internal.rec_offset = 0;
1155         ++ondisk->count;
1156         hammer_modify_node_done(parent);
1157
1158         /*
1159          * The children of new_node need their parent pointer set to new_node.
1160          */
1161         for (i = 0; i < new_node->ondisk->count; ++i) {
1162                 elm = &new_node->ondisk->elms[i];
1163                 error = btree_set_parent(new_node, elm);
1164                 if (error) {
1165                         panic("btree_split_internal: btree-fixup problem");
1166                 }
1167         }
1168
1169         /*
1170          * The cluster's root pointer may have to be updated.
1171          */
1172         if (made_root) {
1173                 hammer_modify_cluster(node->cluster);
1174                 node->cluster->ondisk->clu_btree_root = parent->node_offset;
1175                 hammer_modify_cluster_done(node->cluster);
1176                 node->ondisk->parent = parent->node_offset;
1177                 if (cursor->parent) {
1178                         hammer_unlock(&cursor->parent->lock);
1179                         hammer_rel_node(cursor->parent);
1180                 }
1181                 cursor->parent = parent;        /* lock'd and ref'd */
1182         }
1183         hammer_modify_node_done(new_node);
1184         hammer_modify_node_done(node);
1185
1186
1187         /*
1188          * Ok, now adjust the cursor depending on which element the original
1189          * index was pointing at.  If we are >= the split point the push node
1190          * is now in the new node.
1191          *
1192          * NOTE: If we are at the split point itself we cannot stay with the
1193          * original node because the push index will point at the right-hand
1194          * boundary, which is illegal.
1195          *
1196          * NOTE: The cursor's parent or parent_index must be adjusted for
1197          * the case where a new parent (new root) was created, and the case
1198          * where the cursor is now pointing at the split node.
1199          */
1200         if (cursor->index >= split) {
1201                 cursor->parent_index = parent_index + 1;
1202                 cursor->index -= split;
1203                 hammer_unlock(&cursor->node->lock);
1204                 hammer_rel_node(cursor->node);
1205                 cursor->node = new_node;        /* locked and ref'd */
1206         } else {
1207                 cursor->parent_index = parent_index;
1208                 hammer_unlock(&new_node->lock);
1209                 hammer_rel_node(new_node);
1210         }
1211
1212         /*
1213          * Fixup left and right bounds
1214          */
1215         parent_elm = &parent->ondisk->elms[cursor->parent_index];
1216         cursor->left_bound = &parent_elm[0].internal.base;
1217         cursor->right_bound = &parent_elm[1].internal.base;
1218         KKASSERT(hammer_btree_cmp(cursor->left_bound,
1219                  &cursor->node->ondisk->elms[0].internal.base) <= 0);
1220         KKASSERT(hammer_btree_cmp(cursor->right_bound,
1221                  &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].internal.base) > 0);
1222
1223         return (0);
1224 }
1225
1226 /*
1227  * Same as the above, but splits a full leaf node.
1228  */
1229 static
1230 int
1231 btree_split_leaf(hammer_cursor_t cursor)
1232 {
1233         hammer_node_ondisk_t ondisk;
1234         hammer_node_t parent;
1235         hammer_node_t leaf;
1236         hammer_node_t new_leaf;
1237         hammer_btree_elm_t elm;
1238         hammer_btree_elm_t parent_elm;
1239         hammer_base_elm_t mid_boundary;
1240         int parent_index;
1241         int made_root;
1242         int split;
1243         int error;
1244         const size_t esize = sizeof(*elm);
1245
1246         /*
1247          * Calculate the split point.  If the insertion point will be on
1248          * the left-hand side adjust the split point to give the right
1249          * hand side one additional node.
1250          */
1251         leaf = cursor->node;
1252         ondisk = leaf->ondisk;
1253         split = (ondisk->count + 1) / 2;
1254         if (cursor->index <= split)
1255                 --split;
1256         error = 0;
1257
1258         /*
1259          * If we are at the root of the tree, create a new root node with
1260          * 1 element and split normally.  Avoid making major modifications
1261          * until we know the whole operation will work.
1262          */
1263         if (ondisk->parent == 0) {
1264                 parent = hammer_alloc_btree(leaf->cluster, &error);
1265                 if (parent == NULL)
1266                         return(error);
1267                 hammer_lock_ex(&parent->lock);
1268                 hammer_modify_node(parent);
1269                 ondisk = parent->ondisk;
1270                 ondisk->count = 1;
1271                 ondisk->parent = 0;
1272                 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1273                 ondisk->elms[0].base = leaf->cluster->clu_btree_beg;
1274                 ondisk->elms[0].internal.subtree_type = leaf->ondisk->type;
1275                 ondisk->elms[0].internal.subtree_offset = leaf->node_offset;
1276                 ondisk->elms[1].base = leaf->cluster->clu_btree_end;
1277                 hammer_modify_node_done(parent);
1278                 made_root = 1;
1279                 parent_index = 0;       /* insertion point in parent */
1280         } else {
1281                 made_root = 0;
1282                 parent = cursor->parent;
1283                 parent_index = cursor->parent_index;
1284                 KKASSERT(parent->cluster == leaf->cluster);
1285         }
1286
1287         /*
1288          * Split leaf into new_leaf at the split point.  Select a separator
1289          * value in-between the two leafs but with a bent towards the right
1290          * leaf since comparisons use an 'elm >= separator' inequality.
1291          *
1292          *  L L L L L L L L
1293          *
1294          *       x x P x x
1295          *        s S S s
1296          *         /   \
1297          *  L L L L     L L L L
1298          */
1299         new_leaf = hammer_alloc_btree(leaf->cluster, &error);
1300         if (new_leaf == NULL) {
1301                 if (made_root) {
1302                         hammer_unlock(&parent->lock);
1303                         parent->flags |= HAMMER_NODE_DELETED;
1304                         hammer_rel_node(parent);
1305                 }
1306                 return(error);
1307         }
1308         hammer_lock_ex(&new_leaf->lock);
1309
1310         /*
1311          * Create the new node.  P become the left-hand boundary in the
1312          * new node.  Copy the right-hand boundary as well.
1313          */
1314         hammer_modify_node(leaf);
1315         hammer_modify_node(new_leaf);
1316         ondisk = leaf->ondisk;
1317         elm = &ondisk->elms[split];
1318         bcopy(elm, &new_leaf->ondisk->elms[0], (ondisk->count - split) * esize);
1319         new_leaf->ondisk->count = ondisk->count - split;
1320         new_leaf->ondisk->parent = parent->node_offset;
1321         new_leaf->ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1322         KKASSERT(ondisk->type == new_leaf->ondisk->type);
1323
1324         /*
1325          * Cleanup the original node.  Because this is a leaf node and
1326          * leaf nodes do not have a right-hand boundary, there
1327          * aren't any special edge cases to clean up.  We just fixup the
1328          * count.
1329          */
1330         ondisk->count = split;
1331
1332         /*
1333          * Insert the separator into the parent, fixup the parent's
1334          * reference to the original node, and reference the new node.
1335          * The separator is P.
1336          *
1337          * Remember that base.count does not include the right-hand boundary.
1338          * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1339          */
1340         hammer_modify_node(parent);
1341         ondisk = parent->ondisk;
1342         KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
1343         ondisk->elms[parent_index].internal.subtree_count = split;
1344         parent_elm = &ondisk->elms[parent_index+1];
1345         bcopy(parent_elm, parent_elm + 1,
1346               (ondisk->count - parent_index) * esize);
1347         hammer_make_separator(&elm[-1].base, &elm[0].base, &parent_elm->base);
1348         parent_elm->internal.subtree_offset = new_leaf->node_offset;
1349         parent_elm->internal.subtree_count = new_leaf->ondisk->count;
1350         parent_elm->internal.subtree_type = new_leaf->ondisk->type;
1351         parent_elm->internal.subtree_vol_no = 0;
1352         parent_elm->internal.rec_offset = 0;
1353         mid_boundary = &parent_elm->base;
1354         ++ondisk->count;
1355         hammer_modify_node_done(parent);
1356
1357         /*
1358          * The cluster's root pointer may have to be updated.
1359          */
1360         if (made_root) {
1361                 hammer_modify_cluster(leaf->cluster);
1362                 leaf->cluster->ondisk->clu_btree_root = parent->node_offset;
1363                 hammer_modify_cluster_done(leaf->cluster);
1364                 leaf->ondisk->parent = parent->node_offset;
1365                 if (cursor->parent) {
1366                         hammer_unlock(&cursor->parent->lock);
1367                         hammer_rel_node(cursor->parent);
1368                 }
1369                 cursor->parent = parent;        /* lock'd and ref'd */
1370         }
1371         hammer_modify_node_done(leaf);
1372         hammer_modify_node_done(new_leaf);
1373
1374         /*
1375          * Ok, now adjust the cursor depending on which element the original
1376          * index was pointing at.  If we are >= the split point the push node
1377          * is now in the new node.
1378          *
1379          * NOTE: If we are at the split point itself we need to select the
1380          * old or new node based on where key_beg's insertion point will be.
1381          * If we pick the wrong side the inserted element will wind up in
1382          * the wrong leaf node and outside that node's bounds.
1383          */
1384         if (cursor->index > split ||
1385             (cursor->index == split &&
1386              hammer_btree_cmp(&cursor->key_beg, mid_boundary) >= 0)) {
1387                 cursor->parent_index = parent_index + 1;
1388                 cursor->index -= split;
1389                 hammer_unlock(&cursor->node->lock);
1390                 hammer_rel_node(cursor->node);
1391                 cursor->node = new_leaf;
1392         } else {
1393                 cursor->parent_index = parent_index;
1394                 hammer_unlock(&new_leaf->lock);
1395                 hammer_rel_node(new_leaf);
1396         }
1397
1398         /*
1399          * Fixup left and right bounds
1400          */
1401         parent_elm = &parent->ondisk->elms[cursor->parent_index];
1402         cursor->left_bound = &parent_elm[0].internal.base;
1403         cursor->right_bound = &parent_elm[1].internal.base;
1404         KKASSERT(hammer_btree_cmp(cursor->left_bound,
1405                  &cursor->node->ondisk->elms[0].leaf.base) <= 0);
1406         KKASSERT(hammer_btree_cmp(cursor->right_bound,
1407                  &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
1408
1409         return (0);
1410 }
1411
1412 /*
1413  * Attempt to remove the empty B-Tree node at (cursor->node).  Returns 0
1414  * on success, EAGAIN if we could not acquire the necessary locks, or some
1415  * other error.
1416  *
1417  * On return the cursor may end up pointing at an internal node, suitable
1418  * for further iteration but not for an immediate insertion or deletion.
1419  *
1420  * cursor->node may be an internal node or a leaf node.
1421  *
1422  * NOTE: If cursor->node has one element it is the parent trying to delete
1423  * that element, make sure cursor->index is properly adjusted on success.
1424  */
1425 int
1426 btree_remove(hammer_cursor_t cursor)
1427 {
1428         hammer_node_ondisk_t ondisk;
1429         hammer_btree_elm_t elm;
1430         hammer_node_t save;
1431         hammer_node_t node;
1432         hammer_node_t parent;
1433         int error;
1434         int i;
1435
1436         /*
1437          * If we are at the root of the root cluster there is nothing to
1438          * remove, but an internal node at the root of a cluster is not
1439          * allowed to be empty so convert it to a leaf node.
1440          */
1441         if (cursor->parent == NULL) {
1442                 hammer_modify_node(cursor->node);
1443                 ondisk = cursor->node->ondisk;
1444                 KKASSERT(ondisk->parent == 0);
1445                 ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1446                 ondisk->count = 0;
1447                 cursor->index = 0;
1448                 hammer_modify_node_done(cursor->node);
1449                 kprintf("EMPTY ROOT OF ROOT CLUSTER -> LEAF\n");
1450                 return(0);
1451         }
1452
1453         /*
1454          * Retain a reference to cursor->node, ex-lock again (2 locks now)
1455          * so we do not lose the lock when we cursor around.
1456          */
1457         save = cursor->node;
1458         hammer_ref_node(save);
1459         hammer_lock_ex(&save->lock);
1460
1461         /*
1462          * We need to be able to lock the parent of the parent.  Do this
1463          * non-blocking and return EAGAIN if the lock cannot be acquired.
1464          * non-blocking is required in order to avoid a deadlock.
1465          *
1466          * After we cursor up, parent is moved to node and the new parent
1467          * is the parent of the parent.
1468          */
1469         error = hammer_cursor_up(cursor, 1);
1470         if (error) {
1471                 kprintf("BTREE_REMOVE: Cannot lock parent, skipping\n");
1472                 goto failure;
1473         }
1474
1475         /*
1476          * At this point we want to remove the element at (node, index),
1477          * which is now the (original) parent pointing to the saved node.
1478          * Removing the element allows us to then free the node it was
1479          * pointing to.
1480          *
1481          * However, an internal node is not allowed to have 0 elements, so
1482          * if the count would drop to 0 we have to recurse.  It is possible
1483          * for the recursion to fail.
1484          *
1485          * NOTE: The cursor is in an indeterminant position after recursing,
1486          * but will still be suitable for an iteration.
1487          */
1488         node = cursor->node;
1489         KKASSERT(node->ondisk->count > 0);
1490         if (node->ondisk->count == 1) {
1491                 error = btree_remove(cursor);
1492                 if (error == 0) {
1493                         /*kprintf("BTREE_REMOVE: Successful!\n");*/
1494                         goto success;
1495                 } else {
1496                         kprintf("BTREE_REMOVE: Recursion failed %d\n", error);
1497                         goto failure;
1498                 }
1499         }
1500
1501         /*
1502          * Remove the element at (node, index) and adjust the parent's
1503          * subtree_count.
1504          *
1505          * NOTE! If removing element 0 an internal node's left-hand boundary
1506          * will no longer match its parent.  If removing a mid-element the
1507          * boundary will no longer match a child's left hand or right hand
1508          * boundary.
1509          *
1510          *      BxBxBxB         remove a (x[0]): internal node's left-hand
1511          *       | | |                           boundary no longer matches
1512          *       a b c                           parent.
1513          *
1514          *                      remove b (x[1]): a's right hand boundary no
1515          *                                       longer matches parent.
1516          *
1517          *                      remove c (x[2]): b's right hand boundary no
1518          *                                       longer matches parent.
1519          *
1520          * These cases are corrected in btree_search().
1521          */
1522 #if 0
1523         kprintf("BTREE_REMOVE: Removing element %d\n", cursor->index);
1524 #endif
1525         KKASSERT(node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
1526         KKASSERT(cursor->index < node->ondisk->count);
1527         hammer_modify_node(node);
1528         ondisk = node->ondisk;
1529         i = cursor->index;
1530         bcopy(&ondisk->elms[i+1], &ondisk->elms[i],
1531               (ondisk->count - i) * sizeof(ondisk->elms[0]));
1532         --ondisk->count;
1533         hammer_modify_node_done(node);
1534
1535         /*
1536          * Adjust the parent-parent's (now parent) reference to the parent
1537          * (now node).
1538          */
1539         if ((parent = cursor->parent) != NULL) {
1540                 elm = &parent->ondisk->elms[cursor->parent_index];
1541                 if (elm->internal.subtree_count != ondisk->count) {
1542                         hammer_modify_node(parent);
1543                         elm->internal.subtree_count = ondisk->count;
1544                         hammer_modify_node_done(parent);
1545                 }
1546                 if (elm->subtree_type != HAMMER_BTREE_TYPE_CLUSTER &&
1547                     elm->subtree_type != ondisk->type) {
1548                         hammer_modify_node(parent);
1549                         elm->subtree_type = ondisk->type;
1550                         hammer_modify_node_done(parent);
1551                 }
1552         }
1553
1554 success:
1555         /*
1556          * Free the saved node.  If the saved node was the root of a
1557          * cluster, free the entire cluster.
1558          */
1559         hammer_flush_node(save);
1560         save->flags |= HAMMER_NODE_DELETED;
1561
1562         error = 0;
1563 failure:
1564         hammer_unlock(&save->lock);
1565         hammer_rel_node(save);
1566         return(error);
1567 }
1568
1569 /*
1570  * The child represented by the element in internal node node needs
1571  * to have its parent pointer adjusted.
1572  */
1573 static
1574 int
1575 btree_set_parent(hammer_node_t node, hammer_btree_elm_t elm)
1576 {
1577         hammer_volume_t volume;
1578         hammer_cluster_t cluster;
1579         hammer_node_t child;
1580         int error;
1581
1582         error = 0;
1583
1584         switch(elm->internal.subtree_type) {
1585         case HAMMER_BTREE_TYPE_LEAF:
1586         case HAMMER_BTREE_TYPE_INTERNAL:
1587                 child = hammer_get_node(node->cluster,
1588                                         elm->internal.subtree_offset, &error);
1589                 if (error == 0) {
1590                         hammer_modify_node(child);
1591                         hammer_lock_ex(&child->lock);
1592                         child->ondisk->parent = node->node_offset;
1593                         hammer_unlock(&child->lock);
1594                         hammer_modify_node_done(child);
1595                         hammer_rel_node(child);
1596                 }
1597                 break;
1598         case HAMMER_BTREE_TYPE_CLUSTER:
1599                 volume = hammer_get_volume(node->cluster->volume->hmp,
1600                                         elm->internal.subtree_vol_no, &error);
1601                 if (error)
1602                         break;
1603                 cluster = hammer_get_cluster(volume,
1604                                         elm->internal.subtree_clu_no,
1605                                         &error, 0);
1606                 hammer_rel_volume(volume, 0);
1607                 if (error)
1608                         break;
1609                 hammer_modify_cluster(cluster);
1610                 hammer_lock_ex(&cluster->io.lock);
1611                 cluster->ondisk->clu_btree_parent_offset = node->node_offset;
1612                 hammer_unlock(&cluster->io.lock);
1613                 hammer_modify_cluster_done(cluster);
1614                 KKASSERT(cluster->ondisk->clu_btree_parent_clu_no ==
1615                          node->cluster->clu_no);
1616                 KKASSERT(cluster->ondisk->clu_btree_parent_vol_no ==
1617                          node->cluster->volume->vol_no);
1618                 hammer_rel_cluster(cluster, 0);
1619                 break;
1620         default:
1621                 hammer_print_btree_elm(elm, HAMMER_BTREE_TYPE_INTERNAL, -1);
1622                 panic("btree_set_parent: bad subtree_type");
1623                 break; /* NOT REACHED */
1624         }
1625         return(error);
1626 }
1627
1628 #if 0
1629
1630 /*
1631  * This routine is only called if the cursor is at the root node and the
1632  * root node is an internal node.  We attempt to collapse the root node
1633  * by replacing it with all of its children, reducing tree depth by one.
1634  *
1635  * This is the only way to reduce tree depth in a HAMMER filesystem.
1636  * Note that all leaf nodes are at the same depth.
1637  *
1638  * This is a fairly expensive operation because we not only have to load
1639  * the root's children, we also have to scan each child and adjust the
1640  * parent offset for each element in each child.  Nasty all around.
1641  */
1642 static
1643 int
1644 btree_collapse(hammer_cursor_t cursor)
1645 {
1646         hammer_btree_node_ondisk_t root, child;
1647         hammer_btree_node_ondisk_t children[HAMMER_BTREE_INT_ELMS];
1648         struct hammer_buffer *child_buffer[HAMMER_BTREE_INT_ELMS];
1649         int count;
1650         int i, j, n;
1651         int root_modified;
1652         int error;
1653         int32_t root_offset;
1654         u_int8_t subsubtype;
1655
1656         root = cursor->node;
1657         count = root->base.count;
1658         root_offset = hammer_bclu_offset(cursor->node_buffer, root);
1659
1660         /*
1661          * Sum up the number of children each element has.  This value is
1662          * only approximate due to the way the insertion node works.  It
1663          * may be too small but it will never be too large.
1664          *
1665          * Quickly terminate the collapse if the elements have too many
1666          * children.
1667          */
1668         KKASSERT(root->base.parent == 0);       /* must be root node */
1669         KKASSERT(root->base.type == HAMMER_BTREE_TYPE_INTERNAL);
1670         KKASSERT(count <= HAMMER_BTREE_INT_ELMS);
1671
1672         for (i = n = 0; i < count; ++i) {
1673                 n += root->internal.elms[i].subtree_count;
1674         }
1675         if (n > btree_max_elements(root->base.subtype))
1676                 return(0);
1677
1678         /*
1679          * Iterate through the elements again and correct the subtree_count.
1680          * Terminate the collapse if we wind up with too many.
1681          */
1682         error = 0;
1683         root_modified = 0;
1684
1685         for (i = n = 0; i < count; ++i) {
1686                 struct hammer_btree_internal_elm *elm;
1687
1688                 elm = &root->internal.elms[i];
1689                 child_buffer[i] = NULL;
1690                 children[i] = NULL;
1691                 if (elm->subtree_offset == 0)
1692                         continue;
1693                 child = hammer_bread(cursor->cluster, elm->subtree_offset,
1694                                      HAMMER_FSBUF_BTREE, &error,
1695                                      &child_buffer[i], XXX);
1696                 children[i] = child;
1697                 if (child == NULL)
1698                         continue;
1699                 KKASSERT(root->base.subtype == child->base.type);
1700
1701                 /*
1702                  * Accumulate n for a good child, update the root's count
1703                  * if it was wrong.
1704                  */
1705                 if (root->internal.elms[i].subtree_count != child->base.count) {
1706                         root->internal.elms[i].subtree_count = child->base.count;
1707                         root_modified = 1;
1708                 }
1709                 n += root->internal.elms[i].subtree_count;
1710         }
1711         if (error || n > btree_max_elements(root->base.subtype))
1712                 goto done;
1713
1714         /*
1715          * Ok, we can collapse the root.  If the root's children are leafs
1716          * the collapse is really simple.  If they are internal nodes the
1717          * collapse is not so simple because we have to fixup the parent
1718          * pointers for the root's children's children.
1719          *
1720          * When collapsing an internal node the far left and far right
1721          * element's boundaries should match the root's left and right
1722          * boundaries.
1723          */
1724         if (root->base.subtype == HAMMER_BTREE_TYPE_LEAF) {
1725                 for (i = n = 0; i < count; ++i) {
1726                         child = children[i];
1727                         for (j = 0; j < child->base.count; ++j) {
1728                                 root->leaf.elms[n] = child->leaf.elms[j];
1729                                 ++n;
1730                         }
1731                 }
1732                 root->base.type = root->base.subtype;
1733                 root->base.subtype = 0;
1734                 root->base.count = n;
1735                 root->leaf.link_left = 0;
1736                 root->leaf.link_right = 0;
1737         } else {
1738                 struct hammer_btree_internal_elm *elm;
1739                 struct hammer_btree_internal_node *subchild;
1740                 struct hammer_buffer *subchild_buffer = NULL;
1741
1742                 if (count) {
1743                         child = children[0];
1744                         subsubtype = child->base.subtype;
1745                         KKASSERT(child->base.count > 0);
1746                         KKASSERT(root->internal.elms[0].base.key ==
1747                                  child->internal.elms[0].base.key);
1748                         child = children[count-1];
1749                         KKASSERT(child->base.count > 0);
1750                         KKASSERT(root->internal.elms[count].base.key ==
1751                              child->internal.elms[child->base.count].base.key);
1752                 } else {
1753                         subsubtype = 0;
1754                 }
1755                 for (i = n = 0; i < count; ++i) {
1756                         child = children[i];
1757                         KKASSERT(child->base.subtype == subsubtype);
1758                         for (j = 0; j < child->base.count; ++j) {
1759                                 elm = &child->internal.elms[j];
1760
1761                                 root->internal.elms[n] = *elm;
1762                                 subchild = hammer_bread(cursor->cluster,
1763                                                         elm->subtree_offset,
1764                                                         HAMMER_FSBUF_BTREE,
1765                                                         &error,
1766                                                         &subchild_buffer,
1767                                                         XXX);
1768                                 if (subchild) {
1769                                         subchild->base.parent = root_offset;
1770                                         hammer_modify_buffer(subchild_buffer);
1771                                 }
1772                                 ++n;
1773                         }
1774                         /* make sure the right boundary is correct */
1775                         /* (this gets overwritten when the loop continues) */
1776                         /* XXX generate a new separator? */
1777                         root->internal.elms[n] = child->internal.elms[j];
1778                 }
1779                 root->base.type = HAMMER_BTREE_TYPE_INTERNAL;
1780                 root->base.subtype = subsubtype;
1781                 if (subchild_buffer)
1782                         hammer_put_buffer(subchild_buffer, 0);
1783         }
1784         root_modified = 1;
1785
1786         /*
1787          * Cleanup
1788          */
1789 done:
1790         if (root_modified)
1791                 hammer_modify_buffer(cursor->node_buffer);
1792         for (i = 0; i < count; ++i) {
1793                 if (child_buffer[i])
1794                         hammer_put_buffer(child_buffer[i], 0);
1795         }
1796         return(error);
1797 }
1798
1799 #endif
1800
1801 /************************************************************************
1802  *                         MISCELLANIOUS SUPPORT                        *
1803  ************************************************************************/
1804
1805 /*
1806  * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
1807  *
1808  * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
1809  */
1810 int
1811 hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
1812 {
1813         if (key1->obj_id < key2->obj_id)
1814                 return(-4);
1815         if (key1->obj_id > key2->obj_id)
1816                 return(4);
1817
1818         if (key1->rec_type < key2->rec_type)
1819                 return(-3);
1820         if (key1->rec_type > key2->rec_type)
1821                 return(3);
1822
1823         if (key1->key < key2->key)
1824                 return(-2);
1825         if (key1->key > key2->key)
1826                 return(2);
1827         return(0);
1828 }
1829
1830 /*
1831  * Test a non-zero timestamp against an element to determine whether the
1832  * element is visible.
1833  */
1834 int
1835 hammer_btree_chkts(hammer_tid_t create_tid, hammer_base_elm_t base)
1836 {
1837         if (create_tid < base->create_tid)
1838                 return(-1);
1839         if (base->delete_tid && create_tid >= base->delete_tid)
1840                 return(1);
1841         return(0);
1842 }
1843
1844 /*
1845  * Create a separator half way inbetween key1 and key2.  For fields just
1846  * one unit apart, the separator will match key2.
1847  *
1848  * The handling of delete_tid is a little confusing.  It is only possible
1849  * to have one record in the B-Tree where all fields match except delete_tid.
1850  * This means, worse case, two adjacent elements may have a create_tid that
1851  * is one-apart and cause the separator to choose the right-hand element's
1852  * create_tid.  e.g.  (create,delete):  (1,x)(2,x) -> separator is (2,x).
1853  *
1854  * So all we have to do is set delete_tid to the right-hand element to
1855  * guarentee that the separator is properly between the two elements.
1856  */
1857 #define MAKE_SEPARATOR(key1, key2, dest, field) \
1858         dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
1859
1860 static void
1861 hammer_make_separator(hammer_base_elm_t key1, hammer_base_elm_t key2,
1862                       hammer_base_elm_t dest)
1863 {
1864         bzero(dest, sizeof(*dest));
1865         MAKE_SEPARATOR(key1, key2, dest, obj_id);
1866         MAKE_SEPARATOR(key1, key2, dest, rec_type);
1867         MAKE_SEPARATOR(key1, key2, dest, key);
1868         MAKE_SEPARATOR(key1, key2, dest, create_tid);
1869         dest->delete_tid = key2->delete_tid;
1870 }
1871
1872 #undef MAKE_SEPARATOR
1873
1874 /*
1875  * Return whether a generic internal or leaf node is full
1876  */
1877 static int
1878 btree_node_is_full(hammer_node_ondisk_t node)
1879 {
1880         switch(node->type) {
1881         case HAMMER_BTREE_TYPE_INTERNAL:
1882                 if (node->count == HAMMER_BTREE_INT_ELMS)
1883                         return(1);
1884                 break;
1885         case HAMMER_BTREE_TYPE_LEAF:
1886                 if (node->count == HAMMER_BTREE_LEAF_ELMS)
1887                         return(1);
1888                 break;
1889         default:
1890                 panic("illegal btree subtype");
1891         }
1892         return(0);
1893 }
1894
1895 #if 0
1896 static int
1897 btree_max_elements(u_int8_t type)
1898 {
1899         if (type == HAMMER_BTREE_TYPE_LEAF)
1900                 return(HAMMER_BTREE_LEAF_ELMS);
1901         if (type == HAMMER_BTREE_TYPE_INTERNAL)
1902                 return(HAMMER_BTREE_INT_ELMS);
1903         panic("btree_max_elements: bad type %d\n", type);
1904 }
1905 #endif
1906
1907 void
1908 hammer_print_btree_node(hammer_node_ondisk_t ondisk)
1909 {
1910         hammer_btree_elm_t elm;
1911         int i;
1912
1913         kprintf("node %p count=%d parent=%d type=%c\n",
1914                 ondisk, ondisk->count, ondisk->parent, ondisk->type);
1915
1916         /*
1917          * Dump both boundary elements if an internal node
1918          */
1919         if (ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
1920                 for (i = 0; i <= ondisk->count; ++i) {
1921                         elm = &ondisk->elms[i];
1922                         hammer_print_btree_elm(elm, ondisk->type, i);
1923                 }
1924         } else {
1925                 for (i = 0; i < ondisk->count; ++i) {
1926                         elm = &ondisk->elms[i];
1927                         hammer_print_btree_elm(elm, ondisk->type, i);
1928                 }
1929         }
1930 }
1931
1932 void
1933 hammer_print_btree_elm(hammer_btree_elm_t elm, u_int8_t type, int i)
1934 {
1935         kprintf("  %2d", i);
1936         kprintf("\tobjid        = %016llx\n", elm->base.obj_id);
1937         kprintf("\tkey          = %016llx\n", elm->base.key);
1938         kprintf("\tcreate_tid   = %016llx\n", elm->base.create_tid);
1939         kprintf("\tdelete_tid   = %016llx\n", elm->base.delete_tid);
1940         kprintf("\trec_type     = %04x\n", elm->base.rec_type);
1941         kprintf("\tobj_type     = %02x\n", elm->base.obj_type);
1942         kprintf("\tsubtree_type = %02x\n", elm->subtree_type);
1943
1944         if (type == HAMMER_BTREE_TYPE_INTERNAL) {
1945                 if (elm->internal.rec_offset) {
1946                         kprintf("\tcluster_rec  = %08x\n",
1947                                 elm->internal.rec_offset);
1948                         kprintf("\tcluster_id   = %08x\n",
1949                                 elm->internal.subtree_clu_no);
1950                         kprintf("\tvolno        = %08x\n",
1951                                 elm->internal.subtree_vol_no);
1952                 } else {
1953                         kprintf("\tsubtree_off  = %08x\n",
1954                                 elm->internal.subtree_offset);
1955                 }
1956                 kprintf("\tsubtree_count= %d\n", elm->internal.subtree_count);
1957         } else {
1958                 kprintf("\trec_offset   = %08x\n", elm->leaf.rec_offset);
1959                 kprintf("\tdata_offset  = %08x\n", elm->leaf.data_offset);
1960                 kprintf("\tdata_len     = %08x\n", elm->leaf.data_len);
1961                 kprintf("\tdata_crc     = %08x\n", elm->leaf.data_crc);
1962         }
1963 }