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