sys/vfs/hammer/hammer_btree.c

   1 /*
   2  * Copyright (c) 2007-2008 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.76 2008/08/06 15:38:58 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 HAMMER 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  * INSERTIONS:  A search performed with the intention of doing
  71  * an insert will guarantee that the terminal leaf node is not full by
  72  * splitting full nodes.  Splits occur top-down during the dive down the
  73  * B-Tree.
  74  *
  75  * DELETIONS: A deletion makes no attempt to proactively balance the
  76  * tree and will recursively remove nodes that become empty.  If a
  77  * deadlock occurs a deletion may not be able to remove an empty leaf.
  78  * Deletions never allow internal nodes to become empty (that would blow
  79  * up the boundaries).
  80  */
  81 #include "hammer.h"
  82 #include <sys/buf.h>
  83 #include <sys/buf2.h>
  84
  85 static int btree_search(hammer_cursor_t cursor, int flags);
  86 static int btree_split_internal(hammer_cursor_t cursor);
  87 static int btree_split_leaf(hammer_cursor_t cursor);
  88 static int btree_remove(hammer_cursor_t cursor);
  89 static int btree_node_is_full(hammer_node_ondisk_t node);
  90 static int hammer_btree_mirror_propagate(hammer_cursor_t cursor,
  91                         hammer_tid_t mirror_tid);
  92 static void hammer_make_separator(hammer_base_elm_t key1,
  93                         hammer_base_elm_t key2, hammer_base_elm_t dest);
  94 static void hammer_cursor_mirror_filter(hammer_cursor_t cursor);
  95
  96 /*
  97  * Iterate records after a search.  The cursor is iterated forwards past
  98  * the current record until a record matching the key-range requirements
  99  * is found.  ENOENT is returned if the iteration goes past the ending
 100  * key.
 101  *
 102  * The iteration is inclusive of key_beg and can be inclusive or exclusive
 103  * of key_end depending on whether HAMMER_CURSOR_END_INCLUSIVE is set.
 104  *
 105  * When doing an as-of search (cursor->asof != 0), key_beg.create_tid
 106  * may be modified by B-Tree functions.
 107  *
 108  * cursor->key_beg may or may not be modified by this function during
 109  * the iteration.  XXX future - in case of an inverted lock we may have
 110  * to reinitiate the lookup and set key_beg to properly pick up where we
 111  * left off.
 112  *
 113  * If HAMMER_CURSOR_ITERATE_CHECK is set it is possible that the cursor
 114  * was reverse indexed due to being moved to a parent while unlocked,
 115  * and something else might have inserted an element outside the iteration
 116  * range.  When this case occurs the iterator just keeps iterating until
 117  * it gets back into the iteration range (instead of asserting).
 118  *
 119  * NOTE!  EDEADLK *CANNOT* be returned by this procedure.
 120  */
 121 int
 122 hammer_btree_iterate(hammer_cursor_t cursor)
 123 {
 124         hammer_node_ondisk_t node;
 125         hammer_btree_elm_t elm;
 126         hammer_mount_t hmp;
 127         int error = 0;
 128         int r;
 129         int s;
 130
 131         /*
 132          * Skip past the current record
 133          */
 134         hmp = cursor->trans->hmp;
 135         node = cursor->node->ondisk;
 136         if (node == NULL)
 137                 return(ENOENT);
 138         if (cursor->index < node->count &&
 139             (cursor->flags & HAMMER_CURSOR_ATEDISK)) {
 140                 ++cursor->index;
 141         }
 142
 143         /*
 144          * HAMMER can wind up being cpu-bound.
 145          */
 146         if (++hmp->check_yield > hammer_yield_check) {
 147                 hmp->check_yield = 0;
 148                 lwkt_user_yield();
 149         }
 150
 151
 152         /*
 153          * Loop until an element is found or we are done.
 154          */
 155         for (;;) {
 156                 /*
 157                  * We iterate up the tree and then index over one element
 158                  * while we are at the last element in the current node.
 159                  *
 160                  * If we are at the root of the filesystem, cursor_up
 161                  * returns ENOENT.
 162                  *
 163                  * XXX this could be optimized by storing the information in
 164                  * the parent reference.
 165                  *
 166                  * XXX we can lose the node lock temporarily, this could mess
 167                  * up our scan.
 168                  */
 169                 ++hammer_stats_btree_iterations;
 170                 hammer_flusher_clean_loose_ios(hmp);
 171
 172                 if (cursor->index == node->count) {
 173                         if (hammer_debug_btree) {
 174                                 kprintf("BRACKETU %016llx[%d] -> %016llx[%d] (td=%p)\n",
 175                                         (long long)cursor->node->node_offset,
 176                                         cursor->index,
 177                                         (long long)(cursor->parent ? cursor->parent->node_offset : -1),
 178                                         cursor->parent_index,
 179                                         curthread);
 180                         }
 181                         KKASSERT(cursor->parent == NULL || cursor->parent->ondisk->elms[cursor->parent_index].internal.subtree_offset == cursor->node->node_offset);
 182                         error = hammer_cursor_up(cursor);
 183                         if (error)
 184                                 break;
 185                         /* reload stale pointer */
 186                         node = cursor->node->ondisk;
 187                         KKASSERT(cursor->index != node->count);
 188
 189                         /*
 190                          * If we are reblocking we want to return internal
 191                          * nodes.  Note that the internal node will be
 192                          * returned multiple times, on each upward recursion
 193                          * from its children.  The caller selects which
 194                          * revisit it cares about (usually first or last only).
 195                          */
 196                         if (cursor->flags & HAMMER_CURSOR_REBLOCKING) {
 197                                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
 198                                 return(0);
 199                         }
 200                         ++cursor->index;
 201                         continue;
 202                 }
 203
 204                 /*
 205                  * Check internal or leaf element.  Determine if the record
 206                  * at the cursor has gone beyond the end of our range.
 207                  *
 208                  * We recurse down through internal nodes.
 209                  */
 210                 if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
 211                         elm = &node->elms[cursor->index];
 212
 213                         r = hammer_btree_cmp(&cursor->key_end, &elm[0].base);
 214                         s = hammer_btree_cmp(&cursor->key_beg, &elm[1].base);
 215                         if (hammer_debug_btree) {
 216                                 kprintf("BRACKETL %016llx[%d] %016llx %02x %016llx lo=%02x %d (td=%p)\n",
 217                                         (long long)cursor->node->node_offset,
 218                                         cursor->index,
 219                                         (long long)elm[0].internal.base.obj_id,
 220                                         elm[0].internal.base.rec_type,
 221                                         (long long)elm[0].internal.base.key,
 222                                         elm[0].internal.base.localization,
 223                                         r,
 224                                         curthread
 225                                 );
 226                                 kprintf("BRACKETR %016llx[%d] %016llx %02x %016llx lo=%02x %d\n",
 227                                         (long long)cursor->node->node_offset,
 228                                         cursor->index + 1,
 229                                         (long long)elm[1].internal.base.obj_id,
 230                                         elm[1].internal.base.rec_type,
 231                                         (long long)elm[1].internal.base.key,
 232                                         elm[1].internal.base.localization,
 233                                         s
 234                                 );
 235                         }
 236
 237                         if (r < 0) {
 238                                 error = ENOENT;
 239                                 break;
 240                         }
 241                         if (r == 0 && (cursor->flags &
 242                                        HAMMER_CURSOR_END_INCLUSIVE) == 0) {
 243                                 error = ENOENT;
 244                                 break;
 245                         }
 246
 247                         /*
 248                          * Better not be zero
 249                          */
 250                         KKASSERT(elm->internal.subtree_offset != 0);
 251
 252                         if (s <= 0) {
 253                                 /*
 254                                  * If running the mirror filter see if we
 255                                  * can skip one or more entire sub-trees.
 256                                  * If we can we return the internal node
 257                                  * and the caller processes the skipped
 258                                  * range (see mirror_read).
 259                                  */
 260                                 if (cursor->flags &
 261                                     HAMMER_CURSOR_MIRROR_FILTERED) {
 262                                         if (elm->internal.mirror_tid <
 263                                             cursor->cmirror->mirror_tid) {
 264                                                 hammer_cursor_mirror_filter(cursor);
 265                                                 return(0);
 266                                         }
 267                                 }
 268                         } else {
 269                                 /*
 270                                  * Normally it would be impossible for the
 271                                  * cursor to have gotten back-indexed,
 272                                  * but it can happen if a node is deleted
 273                                  * and the cursor is moved to its parent
 274                                  * internal node.  ITERATE_CHECK will be set.
 275                                  */
 276                                 KKASSERT(cursor->flags &
 277                                          HAMMER_CURSOR_ITERATE_CHECK);
 278                                 kprintf("hammer_btree_iterate: "
 279                                         "DEBUG: Caught parent seek "
 280                                         "in internal iteration\n");
 281                         }
 282
 283                         error = hammer_cursor_down(cursor);
 284                         if (error)
 285                                 break;
 286                         KKASSERT(cursor->index == 0);
 287                         /* reload stale pointer */
 288                         node = cursor->node->ondisk;
 289                         continue;
 290                 } else {
 291                         elm = &node->elms[cursor->index];
 292                         r = hammer_btree_cmp(&cursor->key_end, &elm->base);
 293                         if (hammer_debug_btree) {
 294                                 kprintf("ELEMENT  %016llx:%d %c %016llx %02x %016llx lo=%02x %d\n",
 295                                         (long long)cursor->node->node_offset,
 296                                         cursor->index,
 297                                         (elm[0].leaf.base.btype ?
 298                                          elm[0].leaf.base.btype : '?'),
 299                                         (long long)elm[0].leaf.base.obj_id,
 300                                         elm[0].leaf.base.rec_type,
 301                                         (long long)elm[0].leaf.base.key,
 302                                         elm[0].leaf.base.localization,
 303                                         r
 304                                 );
 305                         }
 306                         if (r < 0) {
 307                                 error = ENOENT;
 308                                 break;
 309                         }
 310
 311                         /*
 312                          * We support both end-inclusive and
 313                          * end-exclusive searches.
 314                          */
 315                         if (r == 0 &&
 316                            (cursor->flags & HAMMER_CURSOR_END_INCLUSIVE) == 0) {
 317                                 error = ENOENT;
 318                                 break;
 319                         }
 320
 321                         /*
 322                          * If ITERATE_CHECK is set an unlocked cursor may
 323                          * have been moved to a parent and the iterate can
 324                          * happen upon elements that are not in the requested
 325                          * range.
 326                          */
 327                         if (cursor->flags & HAMMER_CURSOR_ITERATE_CHECK) {
 328                                 s = hammer_btree_cmp(&cursor->key_beg,
 329                                                      &elm->base);
 330                                 if (s > 0) {
 331                                         kprintf("hammer_btree_iterate: "
 332                                                 "DEBUG: Caught parent seek "
 333                                                 "in leaf iteration\n");
 334                                         ++cursor->index;
 335                                         continue;
 336                                 }
 337                         }
 338                         cursor->flags &= ~HAMMER_CURSOR_ITERATE_CHECK;
 339
 340                         /*
 341                          * Return the element
 342                          */
 343                         switch(elm->leaf.base.btype) {
 344                         case HAMMER_BTREE_TYPE_RECORD:
 345                                 if ((cursor->flags & HAMMER_CURSOR_ASOF) &&
 346                                     hammer_btree_chkts(cursor->asof, &elm->base)) {
 347                                         ++cursor->index;
 348                                         continue;
 349                                 }
 350                                 error = 0;
 351                                 break;
 352                         default:
 353                                 error = EINVAL;
 354                                 break;
 355                         }
 356                         if (error)
 357                                 break;
 358                 }
 359                 /*
 360                  * node pointer invalid after loop
 361                  */
 362
 363                 /*
 364                  * Return entry
 365                  */
 366                 if (hammer_debug_btree) {
 367                         int i = cursor->index;
 368                         hammer_btree_elm_t elm = &cursor->node->ondisk->elms[i];
 369                         kprintf("ITERATE  %p:%d %016llx %02x %016llx lo=%02x\n",
 370                                 cursor->node, i,
 371                                 (long long)elm->internal.base.obj_id,
 372                                 elm->internal.base.rec_type,
 373                                 (long long)elm->internal.base.key,
 374                                 elm->internal.base.localization
 375                         );
 376                 }
 377                 return(0);
 378         }
 379         return(error);
 380 }
 381
 382 /*
 383  * We hit an internal element that we could skip as part of a mirroring
 384  * scan.  Calculate the entire range being skipped.
 385  *
 386  * It is important to include any gaps between the parent's left_bound
 387  * and the node's left_bound, and same goes for the right side.
 388  */
 389 static void
 390 hammer_cursor_mirror_filter(hammer_cursor_t cursor)
 391 {
 392         struct hammer_cmirror *cmirror;
 393         hammer_node_ondisk_t ondisk;
 394         hammer_btree_elm_t elm;
 395
 396         ondisk = cursor->node->ondisk;
 397         cmirror = cursor->cmirror;
 398
 399         /*
 400          * Calculate the skipped range
 401          */
 402         elm = &ondisk->elms[cursor->index];
 403         if (cursor->index == 0)
 404                 cmirror->skip_beg = *cursor->left_bound;
 405         else
 406                 cmirror->skip_beg = elm->internal.base;
 407         while (cursor->index < ondisk->count) {
 408                 if (elm->internal.mirror_tid >= cmirror->mirror_tid)
 409                         break;
 410                 ++cursor->index;
 411                 ++elm;
 412         }
 413         if (cursor->index == ondisk->count)
 414                 cmirror->skip_end = *cursor->right_bound;
 415         else
 416                 cmirror->skip_end = elm->internal.base;
 417
 418         /*
 419          * clip the returned result.
 420          */
 421         if (hammer_btree_cmp(&cmirror->skip_beg, &cursor->key_beg) < 0)
 422                 cmirror->skip_beg = cursor->key_beg;
 423         if (hammer_btree_cmp(&cmirror->skip_end, &cursor->key_end) > 0)
 424                 cmirror->skip_end = cursor->key_end;
 425 }
 426
 427 /*
 428  * Iterate in the reverse direction.  This is used by the pruning code to
 429  * avoid overlapping records.
 430  */
 431 int
 432 hammer_btree_iterate_reverse(hammer_cursor_t cursor)
 433 {
 434         hammer_node_ondisk_t node;
 435         hammer_btree_elm_t elm;
 436         hammer_mount_t hmp;
 437         int error = 0;
 438         int r;
 439         int s;
 440
 441         /* mirror filtering not supported for reverse iteration */
 442         KKASSERT ((cursor->flags & HAMMER_CURSOR_MIRROR_FILTERED) == 0);
 443
 444         /*
 445          * Skip past the current record.  For various reasons the cursor
 446          * may end up set to -1 or set to point at the end of the current
 447          * node.  These cases must be addressed.
 448          */
 449         node = cursor->node->ondisk;
 450         if (node == NULL)
 451                 return(ENOENT);
 452         if (cursor->index != -1 &&
 453             (cursor->flags & HAMMER_CURSOR_ATEDISK)) {
 454                 --cursor->index;
 455         }
 456         if (cursor->index == cursor->node->ondisk->count)
 457                 --cursor->index;
 458
 459         /*
 460          * HAMMER can wind up being cpu-bound.
 461          */
 462         hmp = cursor->trans->hmp;
 463         if (++hmp->check_yield > hammer_yield_check) {
 464                 hmp->check_yield = 0;
 465                 lwkt_user_yield();
 466         }
 467
 468         /*
 469          * Loop until an element is found or we are done.
 470          */
 471         for (;;) {
 472                 ++hammer_stats_btree_iterations;
 473                 hammer_flusher_clean_loose_ios(hmp);
 474
 475                 /*
 476                  * We iterate up the tree and then index over one element
 477                  * while we are at the last element in the current node.
 478                  */
 479                 if (cursor->index == -1) {
 480                         error = hammer_cursor_up(cursor);
 481                         if (error) {
 482                                 cursor->index = 0; /* sanity */
 483                                 break;
 484                         }
 485                         /* reload stale pointer */
 486                         node = cursor->node->ondisk;
 487                         KKASSERT(cursor->index != node->count);
 488                         --cursor->index;
 489                         continue;
 490                 }
 491
 492                 /*
 493                  * Check internal or leaf element.  Determine if the record
 494                  * at the cursor has gone beyond the end of our range.
 495                  *
 496                  * We recurse down through internal nodes.
 497                  */
 498                 KKASSERT(cursor->index != node->count);
 499                 if (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
 500                         elm = &node->elms[cursor->index];
 501                         r = hammer_btree_cmp(&cursor->key_end, &elm[0].base);
 502                         s = hammer_btree_cmp(&cursor->key_beg, &elm[1].base);
 503                         if (hammer_debug_btree) {
 504                                 kprintf("BRACKETL %016llx[%d] %016llx %02x %016llx lo=%02x %d\n",
 505                                         (long long)cursor->node->node_offset,
 506                                         cursor->index,
 507                                         (long long)elm[0].internal.base.obj_id,
 508                                         elm[0].internal.base.rec_type,
 509                                         (long long)elm[0].internal.base.key,
 510                                         elm[0].internal.base.localization,
 511                                         r
 512                                 );
 513                                 kprintf("BRACKETR %016llx[%d] %016llx %02x %016llx lo=%02x %d\n",
 514                                         (long long)cursor->node->node_offset,
 515                                         cursor->index + 1,
 516                                         (long long)elm[1].internal.base.obj_id,
 517                                         elm[1].internal.base.rec_type,
 518                                         (long long)elm[1].internal.base.key,
 519                                         elm[1].internal.base.localization,
 520                                         s
 521                                 );
 522                         }
 523
 524                         if (s >= 0) {
 525                                 error = ENOENT;
 526                                 break;
 527                         }
 528
 529                         /*
 530                          * It shouldn't be possible to be seeked past key_end,
 531                          * even if the cursor got moved to a parent.
 532                          */
 533                         KKASSERT(r >= 0);
 534
 535                         /*
 536                          * Better not be zero
 537                          */
 538                         KKASSERT(elm->internal.subtree_offset != 0);
 539
 540                         error = hammer_cursor_down(cursor);
 541                         if (error)
 542                                 break;
 543                         KKASSERT(cursor->index == 0);
 544                         /* reload stale pointer */
 545                         node = cursor->node->ondisk;
 546
 547                         /* this can assign -1 if the leaf was empty */
 548                         cursor->index = node->count - 1;
 549                         continue;
 550                 } else {
 551                         elm = &node->elms[cursor->index];
 552                         s = hammer_btree_cmp(&cursor->key_beg, &elm->base);
 553                         if (hammer_debug_btree) {
 554                                 kprintf("ELEMENT  %016llx:%d %c %016llx %02x %016llx lo=%02x %d\n",
 555                                         (long long)cursor->node->node_offset,
 556                                         cursor->index,
 557                                         (elm[0].leaf.base.btype ?
 558                                          elm[0].leaf.base.btype : '?'),
 559                                         (long long)elm[0].leaf.base.obj_id,
 560                                         elm[0].leaf.base.rec_type,
 561                                         (long long)elm[0].leaf.base.key,
 562                                         elm[0].leaf.base.localization,
 563                                         s
 564                                 );
 565                         }
 566                         if (s > 0) {
 567                                 error = ENOENT;
 568                                 break;
 569                         }
 570
 571                         /*
 572                          * It shouldn't be possible to be seeked past key_end,
 573                          * even if the cursor got moved to a parent.
 574                          */
 575                         cursor->flags &= ~HAMMER_CURSOR_ITERATE_CHECK;
 576
 577                         /*
 578                          * Return the element
 579                          */
 580                         switch(elm->leaf.base.btype) {
 581                         case HAMMER_BTREE_TYPE_RECORD:
 582                                 if ((cursor->flags & HAMMER_CURSOR_ASOF) &&
 583                                     hammer_btree_chkts(cursor->asof, &elm->base)) {
 584                                         --cursor->index;
 585                                         continue;
 586                                 }
 587                                 error = 0;
 588                                 break;
 589                         default:
 590                                 error = EINVAL;
 591                                 break;
 592                         }
 593                         if (error)
 594                                 break;
 595                 }
 596                 /*
 597                  * node pointer invalid after loop
 598                  */
 599
 600                 /*
 601                  * Return entry
 602                  */
 603                 if (hammer_debug_btree) {
 604                         int i = cursor->index;
 605                         hammer_btree_elm_t elm = &cursor->node->ondisk->elms[i];
 606                         kprintf("ITERATE  %p:%d %016llx %02x %016llx lo=%02x\n",
 607                                 cursor->node, i,
 608                                 (long long)elm->internal.base.obj_id,
 609                                 elm->internal.base.rec_type,
 610                                 (long long)elm->internal.base.key,
 611                                 elm->internal.base.localization
 612                         );
 613                 }
 614                 return(0);
 615         }
 616         return(error);
 617 }
 618
 619 /*
 620  * Lookup cursor->key_beg.  0 is returned on success, ENOENT if the entry
 621  * could not be found, EDEADLK if inserting and a retry is needed, and a
 622  * fatal error otherwise.  When retrying, the caller must terminate the
 623  * cursor and reinitialize it.  EDEADLK cannot be returned if not inserting.
 624  *
 625  * The cursor is suitably positioned for a deletion on success, and suitably
 626  * positioned for an insertion on ENOENT if HAMMER_CURSOR_INSERT was
 627  * specified.
 628  *
 629  * The cursor may begin anywhere, the search will traverse the tree in
 630  * either direction to locate the requested element.
 631  *
 632  * Most of the logic implementing historical searches is handled here.  We
 633  * do an initial lookup with create_tid set to the asof TID.  Due to the
 634  * way records are laid out, a backwards iteration may be required if
 635  * ENOENT is returned to locate the historical record.  Here's the
 636  * problem:
 637  *
 638  * create_tid:    10      15       20
 639  *                   LEAF1   LEAF2
 640  * records:         (11)        (18)
 641  *
 642  * Lets say we want to do a lookup AS-OF timestamp 17.  We will traverse
 643  * LEAF2 but the only record in LEAF2 has a create_tid of 18, which is
 644  * not visible and thus causes ENOENT to be returned.  We really need
 645  * to check record 11 in LEAF1.  If it also fails then the search fails
 646  * (e.g. it might represent the range 11-16 and thus still not match our
 647  * AS-OF timestamp of 17).  Note that LEAF1 could be empty, requiring
 648  * further iterations.
 649  *
 650  * If this case occurs btree_search() will set HAMMER_CURSOR_CREATE_CHECK
 651  * and the cursor->create_check TID if an iteration might be needed.
 652  * In the above example create_check would be set to 14.
 653  */
 654 int
 655 hammer_btree_lookup(hammer_cursor_t cursor)
 656 {
 657         int error;
 658
 659         cursor->flags &= ~HAMMER_CURSOR_ITERATE_CHECK;
 660         KKASSERT ((cursor->flags & HAMMER_CURSOR_INSERT) == 0 ||
 661                   cursor->trans->sync_lock_refs > 0);
 662         ++hammer_stats_btree_lookups;
 663         if (cursor->flags & HAMMER_CURSOR_ASOF) {
 664                 KKASSERT((cursor->flags & HAMMER_CURSOR_INSERT) == 0);
 665                 cursor->key_beg.create_tid = cursor->asof;
 666                 for (;;) {
 667                         cursor->flags &= ~HAMMER_CURSOR_CREATE_CHECK;
 668                         error = btree_search(cursor, 0);
 669                         if (error != ENOENT ||
 670                             (cursor->flags & HAMMER_CURSOR_CREATE_CHECK) == 0) {
 671                                 /*
 672                                  * Stop if no error.
 673                                  * Stop if error other then ENOENT.
 674                                  * Stop if ENOENT and not special case.
 675                                  */
 676                                 break;
 677                         }
 678                         if (hammer_debug_btree) {
 679                                 kprintf("CREATE_CHECK %016llx\n",
 680                                         (long long)cursor->create_check);
 681                         }
 682                         cursor->key_beg.create_tid = cursor->create_check;
 683                         /* loop */
 684                 }
 685         } else {
 686                 error = btree_search(cursor, 0);
 687         }
 688         if (error == 0)
 689                 error = hammer_btree_extract(cursor, cursor->flags);
 690         return(error);
 691 }
 692
 693 /*
 694  * Execute the logic required to start an iteration.  The first record
 695  * located within the specified range is returned and iteration control
 696  * flags are adjusted for successive hammer_btree_iterate() calls.
 697  *
 698  * Set ATEDISK so a low-level caller can call btree_first/btree_iterate
 699  * in a loop without worrying about it.  Higher-level merged searches will
 700  * adjust the flag appropriately.
 701  */
 702 int
 703 hammer_btree_first(hammer_cursor_t cursor)
 704 {
 705         int error;
 706
 707         error = hammer_btree_lookup(cursor);
 708         if (error == ENOENT) {
 709                 cursor->flags &= ~HAMMER_CURSOR_ATEDISK;
 710                 error = hammer_btree_iterate(cursor);
 711         }
 712         cursor->flags |= HAMMER_CURSOR_ATEDISK;
 713         return(error);
 714 }
 715
 716 /*
 717  * Similarly but for an iteration in the reverse direction.
 718  *
 719  * Set ATEDISK when iterating backwards to skip the current entry,
 720  * which after an ENOENT lookup will be pointing beyond our end point.
 721  *
 722  * Set ATEDISK so a low-level caller can call btree_last/btree_iterate_reverse
 723  * in a loop without worrying about it.  Higher-level merged searches will
 724  * adjust the flag appropriately.
 725  */
 726 int
 727 hammer_btree_last(hammer_cursor_t cursor)
 728 {
 729         struct hammer_base_elm save;
 730         int error;
 731
 732         save = cursor->key_beg;
 733         cursor->key_beg = cursor->key_end;
 734         error = hammer_btree_lookup(cursor);
 735         cursor->key_beg = save;
 736         if (error == ENOENT ||
 737             (cursor->flags & HAMMER_CURSOR_END_INCLUSIVE) == 0) {
 738                 cursor->flags |= HAMMER_CURSOR_ATEDISK;
 739                 error = hammer_btree_iterate_reverse(cursor);
 740         }
 741         cursor->flags |= HAMMER_CURSOR_ATEDISK;
 742         return(error);
 743 }
 744
 745 /*
 746  * Extract the record and/or data associated with the cursor's current
 747  * position.  Any prior record or data stored in the cursor is replaced.
 748  * The cursor must be positioned at a leaf node.
 749  *
 750  * NOTE: All extractions occur at the leaf of the B-Tree.
 751  */
 752 int
 753 hammer_btree_extract(hammer_cursor_t cursor, int flags)
 754 {
 755         hammer_node_ondisk_t node;
 756         hammer_btree_elm_t elm;
 757         hammer_off_t data_off;
 758         hammer_mount_t hmp;
 759         int32_t data_len;
 760         int error;
 761
 762         /*
 763          * The case where the data reference resolves to the same buffer
 764          * as the record reference must be handled.
 765          */
 766         node = cursor->node->ondisk;
 767         elm = &node->elms[cursor->index];
 768         cursor->data = NULL;
 769         hmp = cursor->node->hmp;
 770
 771         /*
 772          * There is nothing to extract for an internal element.
 773          */
 774         if (node->type == HAMMER_BTREE_TYPE_INTERNAL)
 775                 return(EINVAL);
 776
 777         /*
 778          * Only record types have data.
 779          */
 780         KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
 781         cursor->leaf = &elm->leaf;
 782
 783         if ((flags & HAMMER_CURSOR_GET_DATA) == 0)
 784                 return(0);
 785         if (elm->leaf.base.btype != HAMMER_BTREE_TYPE_RECORD)
 786                 return(0);
 787         data_off = elm->leaf.data_offset;
 788         data_len = elm->leaf.data_len;
 789         if (data_off == 0)
 790                 return(0);
 791
 792         /*
 793          * Load the data
 794          */
 795         KKASSERT(data_len >= 0 && data_len <= HAMMER_XBUFSIZE);
 796         cursor->data = hammer_bread_ext(hmp, data_off, data_len,
 797                                         &error, &cursor->data_buffer);
 798
 799         /*
 800          * Mark the data buffer as not being meta-data if it isn't
 801          * meta-data (sometimes bulk data is accessed via a volume
 802          * block device).
 803          */
 804         if (error == 0) {
 805                 switch(elm->leaf.base.rec_type) {
 806                 case HAMMER_RECTYPE_DATA:
 807                 case HAMMER_RECTYPE_DB:
 808                         hammer_io_notmeta(cursor->data_buffer);
 809                         break;
 810                 default:
 811                         break;
 812                 }
 813         }
 814
 815         /*
 816          * Deal with CRC errors on the extracted data.
 817          */
 818         if (error == 0 &&
 819             hammer_crc_test_leaf(cursor->data, &elm->leaf) == 0) {
 820                 kprintf("CRC DATA @ %016llx/%d FAILED\n",
 821                         (long long)elm->leaf.data_offset, elm->leaf.data_len);
 822                 if (hammer_debug_critical)
 823                         Debugger("CRC FAILED: DATA");
 824                 if (cursor->trans->flags & HAMMER_TRANSF_CRCDOM)
 825                         error = EDOM;   /* less critical (mirroring) */
 826                 else
 827                         error = EIO;    /* critical */
 828         }
 829         return(error);
 830 }
 831
 832
 833 /*
 834  * Insert a leaf element into the B-Tree at the current cursor position.
 835  * The cursor is positioned such that the element at and beyond the cursor
 836  * are shifted to make room for the new record.
 837  *
 838  * The caller must call hammer_btree_lookup() with the HAMMER_CURSOR_INSERT
 839  * flag set and that call must return ENOENT before this function can be
 840  * called.
 841  *
 842  * The caller may depend on the cursor's exclusive lock after return to
 843  * interlock frontend visibility (see HAMMER_RECF_CONVERT_DELETE).
 844  *
 845  * ENOSPC is returned if there is no room to insert a new record.
 846  */
 847 int
 848 hammer_btree_insert(hammer_cursor_t cursor, hammer_btree_leaf_elm_t elm,
 849                     int *doprop)
 850 {
 851         hammer_node_ondisk_t node;
 852         int i;
 853         int error;
 854
 855         *doprop = 0;
 856         if ((error = hammer_cursor_upgrade_node(cursor)) != 0)
 857                 return(error);
 858         ++hammer_stats_btree_inserts;
 859
 860         /*
 861          * Insert the element at the leaf node and update the count in the
 862          * parent.  It is possible for parent to be NULL, indicating that
 863          * the filesystem's ROOT B-Tree node is a leaf itself, which is
 864          * possible.  The root inode can never be deleted so the leaf should
 865          * never be empty.
 866          *
 867          * Remember that the right-hand boundary is not included in the
 868          * count.
 869          */
 870         hammer_modify_node_all(cursor->trans, cursor->node);
 871         node = cursor->node->ondisk;
 872         i = cursor->index;
 873         KKASSERT(elm->base.btype != 0);
 874         KKASSERT(node->type == HAMMER_BTREE_TYPE_LEAF);
 875         KKASSERT(node->count < HAMMER_BTREE_LEAF_ELMS);
 876         if (i != node->count) {
 877                 bcopy(&node->elms[i], &node->elms[i+1],
 878                       (node->count - i) * sizeof(*elm));
 879         }
 880         node->elms[i].leaf = *elm;
 881         ++node->count;
 882         hammer_cursor_inserted_element(cursor->node, i);
 883
 884         /*
 885          * Update the leaf node's aggregate mirror_tid for mirroring
 886          * support.
 887          */
 888         if (node->mirror_tid < elm->base.delete_tid) {
 889                 node->mirror_tid = elm->base.delete_tid;
 890                 *doprop = 1;
 891         }
 892         if (node->mirror_tid < elm->base.create_tid) {
 893                 node->mirror_tid = elm->base.create_tid;
 894                 *doprop = 1;
 895         }
 896         hammer_modify_node_done(cursor->node);
 897
 898         /*
 899          * Debugging sanity checks.
 900          */
 901         KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm->base) <= 0);
 902         KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm->base) > 0);
 903         if (i) {
 904                 KKASSERT(hammer_btree_cmp(&node->elms[i-1].leaf.base, &elm->base) < 0);
 905         }
 906         if (i != node->count - 1)
 907                 KKASSERT(hammer_btree_cmp(&node->elms[i+1].leaf.base, &elm->base) > 0);
 908
 909         return(0);
 910 }
 911
 912 /*
 913  * Delete a record from the B-Tree at the current cursor position.
 914  * The cursor is positioned such that the current element is the one
 915  * to be deleted.
 916  *
 917  * On return the cursor will be positioned after the deleted element and
 918  * MAY point to an internal node.  It will be suitable for the continuation
 919  * of an iteration but not for an insertion or deletion.
 920  *
 921  * Deletions will attempt to partially rebalance the B-Tree in an upward
 922  * direction, but will terminate rather then deadlock.  Empty internal nodes
 923  * are never allowed by a deletion which deadlocks may end up giving us an
 924  * empty leaf.  The pruner will clean up and rebalance the tree.
 925  *
 926  * This function can return EDEADLK, requiring the caller to retry the
 927  * operation after clearing the deadlock.
 928  */
 929 int
 930 hammer_btree_delete(hammer_cursor_t cursor)
 931 {
 932         hammer_node_ondisk_t ondisk;
 933         hammer_node_t node;
 934         hammer_node_t parent;
 935         int error;
 936         int i;
 937
 938         KKASSERT (cursor->trans->sync_lock_refs > 0);
 939         if ((error = hammer_cursor_upgrade(cursor)) != 0)
 940                 return(error);
 941         ++hammer_stats_btree_deletes;
 942
 943         /*
 944          * Delete the element from the leaf node.
 945          *
 946          * Remember that leaf nodes do not have boundaries.
 947          */
 948         node = cursor->node;
 949         ondisk = node->ondisk;
 950         i = cursor->index;
 951
 952         KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_LEAF);
 953         KKASSERT(i >= 0 && i < ondisk->count);
 954         hammer_modify_node_all(cursor->trans, node);
 955         if (i + 1 != ondisk->count) {
 956                 bcopy(&ondisk->elms[i+1], &ondisk->elms[i],
 957                       (ondisk->count - i - 1) * sizeof(ondisk->elms[0]));
 958         }
 959         --ondisk->count;
 960         hammer_modify_node_done(node);
 961         hammer_cursor_deleted_element(node, i);
 962
 963         /*
 964          * Validate local parent
 965          */
 966         if (ondisk->parent) {
 967                 parent = cursor->parent;
 968
 969                 KKASSERT(parent != NULL);
 970                 KKASSERT(parent->node_offset == ondisk->parent);
 971         }
 972
 973         /*
 974          * If the leaf becomes empty it must be detached from the parent,
 975          * potentially recursing through to the filesystem root.
 976          *
 977          * This may reposition the cursor at one of the parent's of the
 978          * current node.
 979          *
 980          * Ignore deadlock errors, that simply means that btree_remove
 981          * was unable to recurse and had to leave us with an empty leaf.
 982          */
 983         KKASSERT(cursor->index <= ondisk->count);
 984         if (ondisk->count == 0) {
 985                 error = btree_remove(cursor);
 986                 if (error == EDEADLK)
 987                         error = 0;
 988         } else {
 989                 error = 0;
 990         }
 991         KKASSERT(cursor->parent == NULL ||
 992                  cursor->parent_index < cursor->parent->ondisk->count);
 993         return(error);
 994 }
 995
 996 /*
 997  * PRIMAY B-TREE SEARCH SUPPORT PROCEDURE
 998  *
 999  * Search the filesystem B-Tree for cursor->key_beg, return the matching node.
1000  *
1001  * The search can begin ANYWHERE in the B-Tree.  As a first step the search
1002  * iterates up the tree as necessary to properly position itself prior to
1003  * actually doing the sarch.
1004  *
1005  * INSERTIONS: The search will split full nodes and leaves on its way down
1006  * and guarentee that the leaf it ends up on is not full.  If we run out
1007  * of space the search continues to the leaf (to position the cursor for
1008  * the spike), but ENOSPC is returned.
1009  *
1010  * The search is only guarenteed to end up on a leaf if an error code of 0
1011  * is returned, or if inserting and an error code of ENOENT is returned.
1012  * Otherwise it can stop at an internal node.  On success a search returns
1013  * a leaf node.
1014  *
1015  * COMPLEXITY WARNING!  This is the core B-Tree search code for the entire
1016  * filesystem, and it is not simple code.  Please note the following facts:
1017  *
1018  * - Internal node recursions have a boundary on the left AND right.  The
1019  *   right boundary is non-inclusive.  The create_tid is a generic part
1020  *   of the key for internal nodes.
1021  *
1022  * - Leaf nodes contain terminal elements only now.
1023  *
1024  * - Filesystem lookups typically set HAMMER_CURSOR_ASOF, indicating a
1025  *   historical search.  ASOF and INSERT are mutually exclusive.  When
1026  *   doing an as-of lookup btree_search() checks for a right-edge boundary
1027  *   case.  If while recursing down the left-edge differs from the key
1028  *   by ONLY its create_tid, HAMMER_CURSOR_CREATE_CHECK is set along
1029  *   with cursor->create_check.  This is used by btree_lookup() to iterate.
1030  *   The iteration backwards because as-of searches can wind up going
1031  *   down the wrong branch of the B-Tree.
1032  */
1033 static
1034 int
1035 btree_search(hammer_cursor_t cursor, int flags)
1036 {
1037         hammer_node_ondisk_t node;
1038         hammer_btree_elm_t elm;
1039         int error;
1040         int enospc = 0;
1041         int i;
1042         int r;
1043         int s;
1044
1045         flags |= cursor->flags;
1046         ++hammer_stats_btree_searches;
1047
1048         if (hammer_debug_btree) {
1049                 kprintf("SEARCH   %016llx[%d] %016llx %02x key=%016llx cre=%016llx lo=%02x (td = %p)\n",
1050                         (long long)cursor->node->node_offset,
1051                         cursor->index,
1052                         (long long)cursor->key_beg.obj_id,
1053                         cursor->key_beg.rec_type,
1054                         (long long)cursor->key_beg.key,
1055                         (long long)cursor->key_beg.create_tid,
1056                         cursor->key_beg.localization,
1057                         curthread
1058                 );
1059                 if (cursor->parent)
1060                     kprintf("SEARCHP %016llx[%d] (%016llx/%016llx %016llx/%016llx) (%p/%p %p/%p)\n",
1061                         (long long)cursor->parent->node_offset,
1062                         cursor->parent_index,
1063                         (long long)cursor->left_bound->obj_id,
1064                         (long long)cursor->parent->ondisk->elms[cursor->parent_index].internal.base.obj_id,
1065                         (long long)cursor->right_bound->obj_id,
1066                         (long long)cursor->parent->ondisk->elms[cursor->parent_index+1].internal.base.obj_id,
1067                         cursor->left_bound,
1068                         &cursor->parent->ondisk->elms[cursor->parent_index],
1069                         cursor->right_bound,
1070                         &cursor->parent->ondisk->elms[cursor->parent_index+1]
1071                     );
1072         }
1073
1074         /*
1075          * Move our cursor up the tree until we find a node whos range covers
1076          * the key we are trying to locate.
1077          *
1078          * The left bound is inclusive, the right bound is non-inclusive.
1079          * It is ok to cursor up too far.
1080          */
1081         for (;;) {
1082                 r = hammer_btree_cmp(&cursor->key_beg, cursor->left_bound);
1083                 s = hammer_btree_cmp(&cursor->key_beg, cursor->right_bound);
1084                 if (r >= 0 && s < 0)
1085                         break;
1086                 KKASSERT(cursor->parent);
1087                 ++hammer_stats_btree_iterations;
1088                 error = hammer_cursor_up(cursor);
1089                 if (error)
1090                         goto done;
1091         }
1092
1093         /*
1094          * The delete-checks below are based on node, not parent.  Set the
1095          * initial delete-check based on the parent.
1096          */
1097         if (r == 1) {
1098                 KKASSERT(cursor->left_bound->create_tid != 1);
1099                 cursor->create_check = cursor->left_bound->create_tid - 1;
1100                 cursor->flags |= HAMMER_CURSOR_CREATE_CHECK;
1101         }
1102
1103         /*
1104          * We better have ended up with a node somewhere.
1105          */
1106         KKASSERT(cursor->node != NULL);
1107
1108         /*
1109          * If we are inserting we can't start at a full node if the parent
1110          * is also full (because there is no way to split the node),
1111          * continue running up the tree until the requirement is satisfied
1112          * or we hit the root of the filesystem.
1113          *
1114          * (If inserting we aren't doing an as-of search so we don't have
1115          *  to worry about create_check).
1116          */
1117         while ((flags & HAMMER_CURSOR_INSERT) && enospc == 0) {
1118                 if (cursor->node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
1119                         if (btree_node_is_full(cursor->node->ondisk) == 0)
1120                                 break;
1121                 } else {
1122                         if (btree_node_is_full(cursor->node->ondisk) ==0)
1123                                 break;
1124                 }
1125                 if (cursor->node->ondisk->parent == 0 ||
1126                     cursor->parent->ondisk->count != HAMMER_BTREE_INT_ELMS) {
1127                         break;
1128                 }
1129                 ++hammer_stats_btree_iterations;
1130                 error = hammer_cursor_up(cursor);
1131                 /* node may have become stale */
1132                 if (error)
1133                         goto done;
1134         }
1135
1136         /*
1137          * Push down through internal nodes to locate the requested key.
1138          */
1139         node = cursor->node->ondisk;
1140         while (node->type == HAMMER_BTREE_TYPE_INTERNAL) {
1141                 /*
1142                  * Scan the node to find the subtree index to push down into.
1143                  * We go one-past, then back-up.
1144                  *
1145                  * We must proactively remove deleted elements which may
1146                  * have been left over from a deadlocked btree_remove().
1147                  *
1148                  * The left and right boundaries are included in the loop
1149                  * in order to detect edge cases.
1150                  *
1151                  * If the separator only differs by create_tid (r == 1)
1152                  * and we are doing an as-of search, we may end up going
1153                  * down a branch to the left of the one containing the
1154                  * desired key.  This requires numerous special cases.
1155                  */
1156                 ++hammer_stats_btree_iterations;
1157                 if (hammer_debug_btree) {
1158                         kprintf("SEARCH-I %016llx count=%d\n",
1159                                 (long long)cursor->node->node_offset,
1160                                 node->count);
1161                 }
1162
1163                 /*
1164                  * Try to shortcut the search before dropping into the
1165                  * linear loop.  Locate the first node where r <= 1.
1166                  */
1167                 i = hammer_btree_search_node(&cursor->key_beg, node);
1168                 while (i <= node->count) {
1169                         ++hammer_stats_btree_elements;
1170                         elm = &node->elms[i];
1171                         r = hammer_btree_cmp(&cursor->key_beg, &elm->base);
1172                         if (hammer_debug_btree > 2) {
1173                                 kprintf(" IELM %p %d r=%d\n",
1174                                         &node->elms[i], i, r);
1175                         }
1176                         if (r < 0)
1177                                 break;
1178                         if (r == 1) {
1179                                 KKASSERT(elm->base.create_tid != 1);
1180                                 cursor->create_check = elm->base.create_tid - 1;
1181                                 cursor->flags |= HAMMER_CURSOR_CREATE_CHECK;
1182                         }
1183                         ++i;
1184                 }
1185                 if (hammer_debug_btree) {
1186                         kprintf("SEARCH-I preI=%d/%d r=%d\n",
1187                                 i, node->count, r);
1188                 }
1189
1190                 /*
1191                  * These cases occur when the parent's idea of the boundary
1192                  * is wider then the child's idea of the boundary, and
1193                  * require special handling.  If not inserting we can
1194                  * terminate the search early for these cases but the
1195                  * child's boundaries cannot be unconditionally modified.
1196                  */
1197                 if (i == 0) {
1198                         /*
1199                          * If i == 0 the search terminated to the LEFT of the
1200                          * left_boundary but to the RIGHT of the parent's left
1201                          * boundary.
1202                          */
1203                         u_int8_t save;
1204
1205                         elm = &node->elms[0];
1206
1207                         /*
1208                          * If we aren't inserting we can stop here.
1209                          */
1210                         if ((flags & (HAMMER_CURSOR_INSERT |
1211                                       HAMMER_CURSOR_PRUNING)) == 0) {
1212                                 cursor->index = 0;
1213                                 return(ENOENT);
1214                         }
1215
1216                         /*
1217                          * Correct a left-hand boundary mismatch.
1218                          *
1219                          * We can only do this if we can upgrade the lock,
1220                          * and synchronized as a background cursor (i.e.
1221                          * inserting or pruning).
1222                          *
1223                          * WARNING: We can only do this if inserting, i.e.
1224                          * we are running on the backend.
1225                          */
1226                         if ((error = hammer_cursor_upgrade(cursor)) != 0)
1227                                 return(error);
1228                         KKASSERT(cursor->flags & HAMMER_CURSOR_BACKEND);
1229                         hammer_modify_node_field(cursor->trans, cursor->node,
1230                                                  elms[0]);
1231                         save = node->elms[0].base.btype;
1232                         node->elms[0].base = *cursor->left_bound;
1233                         node->elms[0].base.btype = save;
1234                         hammer_modify_node_done(cursor->node);
1235                 } else if (i == node->count + 1) {
1236                         /*
1237                          * If i == node->count + 1 the search terminated to
1238                          * the RIGHT of the right boundary but to the LEFT
1239                          * of the parent's right boundary.  If we aren't
1240                          * inserting we can stop here.
1241                          *
1242                          * Note that the last element in this case is
1243                          * elms[i-2] prior to adjustments to 'i'.
1244                          */
1245                         --i;
1246                         if ((flags & (HAMMER_CURSOR_INSERT |
1247                                       HAMMER_CURSOR_PRUNING)) == 0) {
1248                                 cursor->index = i;
1249                                 return (ENOENT);
1250                         }
1251
1252                         /*
1253                          * Correct a right-hand boundary mismatch.
1254                          * (actual push-down record is i-2 prior to
1255                          * adjustments to i).
1256                          *
1257                          * We can only do this if we can upgrade the lock,
1258                          * and synchronized as a background cursor (i.e.
1259                          * inserting or pruning).
1260                          *
1261                          * WARNING: We can only do this if inserting, i.e.
1262                          * we are running on the backend.
1263                          */
1264                         if ((error = hammer_cursor_upgrade(cursor)) != 0)
1265                                 return(error);
1266                         elm = &node->elms[i];
1267                         KKASSERT(cursor->flags & HAMMER_CURSOR_BACKEND);
1268                         hammer_modify_node(cursor->trans, cursor->node,
1269                                            &elm->base, sizeof(elm->base));
1270                         elm->base = *cursor->right_bound;
1271                         hammer_modify_node_done(cursor->node);
1272                         --i;
1273                 } else {
1274                         /*
1275                          * The push-down index is now i - 1.  If we had
1276                          * terminated on the right boundary this will point
1277                          * us at the last element.
1278                          */
1279                         --i;
1280                 }
1281                 cursor->index = i;
1282                 elm = &node->elms[i];
1283
1284                 if (hammer_debug_btree) {
1285                         kprintf("RESULT-I %016llx[%d] %016llx %02x "
1286                                 "key=%016llx cre=%016llx lo=%02x\n",
1287                                 (long long)cursor->node->node_offset,
1288                                 i,
1289                                 (long long)elm->internal.base.obj_id,
1290                                 elm->internal.base.rec_type,
1291                                 (long long)elm->internal.base.key,
1292                                 (long long)elm->internal.base.create_tid,
1293                                 elm->internal.base.localization
1294                         );
1295                 }
1296
1297                 /*
1298                  * We better have a valid subtree offset.
1299                  */
1300                 KKASSERT(elm->internal.subtree_offset != 0);
1301
1302                 /*
1303                  * Handle insertion and deletion requirements.
1304                  *
1305                  * If inserting split full nodes.  The split code will
1306                  * adjust cursor->node and cursor->index if the current
1307                  * index winds up in the new node.
1308                  *
1309                  * If inserting and a left or right edge case was detected,
1310                  * we cannot correct the left or right boundary and must
1311                  * prepend and append an empty leaf node in order to make
1312                  * the boundary correction.
1313                  *
1314                  * If we run out of space we set enospc and continue on
1315                  * to a leaf to provide the spike code with a good point
1316                  * of entry.
1317                  */
1318                 if ((flags & HAMMER_CURSOR_INSERT) && enospc == 0) {
1319                         if (btree_node_is_full(node)) {
1320                                 error = btree_split_internal(cursor);
1321                                 if (error) {
1322                                         if (error != ENOSPC)
1323                                                 goto done;
1324                                         enospc = 1;
1325                                 }
1326                                 /*
1327                                  * reload stale pointers
1328                                  */
1329                                 i = cursor->index;
1330                                 node = cursor->node->ondisk;
1331                         }
1332                 }
1333
1334                 /*
1335                  * Push down (push into new node, existing node becomes
1336                  * the parent) and continue the search.
1337                  */
1338                 error = hammer_cursor_down(cursor);
1339                 /* node may have become stale */
1340                 if (error)
1341                         goto done;
1342                 node = cursor->node->ondisk;
1343         }
1344
1345         /*
1346          * We are at a leaf, do a linear search of the key array.
1347          *
1348          * On success the index is set to the matching element and 0
1349          * is returned.
1350          *
1351          * On failure the index is set to the insertion point and ENOENT
1352          * is returned.
1353          *
1354          * Boundaries are not stored in leaf nodes, so the index can wind
1355          * up to the left of element 0 (index == 0) or past the end of
1356          * the array (index == node->count).  It is also possible that the
1357          * leaf might be empty.
1358          */
1359         ++hammer_stats_btree_iterations;
1360         KKASSERT (node->type == HAMMER_BTREE_TYPE_LEAF);
1361         KKASSERT(node->count <= HAMMER_BTREE_LEAF_ELMS);
1362         if (hammer_debug_btree) {
1363                 kprintf("SEARCH-L %016llx count=%d\n",
1364                         (long long)cursor->node->node_offset,
1365                         node->count);
1366         }
1367
1368         /*
1369          * Try to shortcut the search before dropping into the
1370          * linear loop.  Locate the first node where r <= 1.
1371          */
1372         i = hammer_btree_search_node(&cursor->key_beg, node);
1373         while (i < node->count) {
1374                 ++hammer_stats_btree_elements;
1375                 elm = &node->elms[i];
1376
1377                 r = hammer_btree_cmp(&cursor->key_beg, &elm->leaf.base);
1378
1379                 if (hammer_debug_btree > 1)
1380                         kprintf("  ELM %p %d r=%d\n", &node->elms[i], i, r);
1381
1382                 /*
1383                  * We are at a record element.  Stop if we've flipped past
1384                  * key_beg, not counting the create_tid test.  Allow the
1385                  * r == 1 case (key_beg > element but differs only by its
1386                  * create_tid) to fall through to the AS-OF check.
1387                  */
1388                 KKASSERT (elm->leaf.base.btype == HAMMER_BTREE_TYPE_RECORD);
1389
1390                 if (r < 0)
1391                         goto failed;
1392                 if (r > 1) {
1393                         ++i;
1394                         continue;
1395                 }
1396
1397                 /*
1398                  * Check our as-of timestamp against the element.
1399                  */
1400                 if (flags & HAMMER_CURSOR_ASOF) {
1401                         if (hammer_btree_chkts(cursor->asof,
1402                                                &node->elms[i].base) != 0) {
1403                                 ++i;
1404                                 continue;
1405                         }
1406                         /* success */
1407                 } else {
1408                         if (r > 0) {    /* can only be +1 */
1409                                 ++i;
1410                                 continue;
1411                         }
1412                         /* success */
1413                 }
1414                 cursor->index = i;
1415                 error = 0;
1416                 if (hammer_debug_btree) {
1417                         kprintf("RESULT-L %016llx[%d] (SUCCESS)\n",
1418                                 (long long)cursor->node->node_offset, i);
1419                 }
1420                 goto done;
1421         }
1422
1423         /*
1424          * The search of the leaf node failed.  i is the insertion point.
1425          */
1426 failed:
1427         if (hammer_debug_btree) {
1428                 kprintf("RESULT-L %016llx[%d] (FAILED)\n",
1429                         (long long)cursor->node->node_offset, i);
1430         }
1431
1432         /*
1433          * No exact match was found, i is now at the insertion point.
1434          *
1435          * If inserting split a full leaf before returning.  This
1436          * may have the side effect of adjusting cursor->node and
1437          * cursor->index.
1438          */
1439         cursor->index = i;
1440         if ((flags & HAMMER_CURSOR_INSERT) && enospc == 0 &&
1441              btree_node_is_full(node)) {
1442                 error = btree_split_leaf(cursor);
1443                 if (error) {
1444                         if (error != ENOSPC)
1445                                 goto done;
1446                         enospc = 1;
1447                 }
1448                 /*
1449                  * reload stale pointers
1450                  */
1451                 /* NOT USED
1452                 i = cursor->index;
1453                 node = &cursor->node->internal;
1454                 */
1455         }
1456
1457         /*
1458          * We reached a leaf but did not find the key we were looking for.
1459          * If this is an insert we will be properly positioned for an insert
1460          * (ENOENT) or spike (ENOSPC) operation.
1461          */
1462         error = enospc ? ENOSPC : ENOENT;
1463 done:
1464         return(error);
1465 }
1466
1467 /*
1468  * Heuristical search for the first element whos comparison is <= 1.  May
1469  * return an index whos compare result is > 1 but may only return an index
1470  * whos compare result is <= 1 if it is the first element with that result.
1471  */
1472 int
1473 hammer_btree_search_node(hammer_base_elm_t elm, hammer_node_ondisk_t node)
1474 {
1475         int b;
1476         int s;
1477         int i;
1478         int r;
1479
1480         /*
1481          * Don't bother if the node does not have very many elements
1482          */
1483         b = 0;
1484         s = node->count;
1485         while (s - b > 4) {
1486                 i = b + (s - b) / 2;
1487                 ++hammer_stats_btree_elements;
1488                 r = hammer_btree_cmp(elm, &node->elms[i].leaf.base);
1489                 if (r <= 1) {
1490                         s = i;
1491                 } else {
1492                         b = i;
1493                 }
1494         }
1495         return(b);
1496 }
1497
1498
1499 /************************************************************************
1500  *                         SPLITTING AND MERGING                        *
1501  ************************************************************************
1502  *
1503  * These routines do all the dirty work required to split and merge nodes.
1504  */
1505
1506 /*
1507  * Split an internal node into two nodes and move the separator at the split
1508  * point to the parent.
1509  *
1510  * (cursor->node, cursor->index) indicates the element the caller intends
1511  * to push into.  We will adjust node and index if that element winds
1512  * up in the split node.
1513  *
1514  * If we are at the root of the filesystem a new root must be created with
1515  * two elements, one pointing to the original root and one pointing to the
1516  * newly allocated split node.
1517  */
1518 static
1519 int
1520 btree_split_internal(hammer_cursor_t cursor)
1521 {
1522         hammer_node_ondisk_t ondisk;
1523         hammer_node_t node;
1524         hammer_node_t parent;
1525         hammer_node_t new_node;
1526         hammer_btree_elm_t elm;
1527         hammer_btree_elm_t parent_elm;
1528         struct hammer_node_lock lockroot;
1529         hammer_mount_t hmp = cursor->trans->hmp;
1530         hammer_off_t hint;
1531         int parent_index;
1532         int made_root;
1533         int split;
1534         int error;
1535         int i;
1536         const int esize = sizeof(*elm);
1537
1538         hammer_node_lock_init(&lockroot, cursor->node);
1539         error = hammer_btree_lock_children(cursor, 1, &lockroot, NULL);
1540         if (error)
1541                 goto done;
1542         if ((error = hammer_cursor_upgrade(cursor)) != 0)
1543                 goto done;
1544         ++hammer_stats_btree_splits;
1545
1546         /*
1547          * Calculate the split point.  If the insertion point is at the
1548          * end of the leaf we adjust the split point significantly to the
1549          * right to try to optimize node fill and flag it.  If we hit
1550          * that same leaf again our heuristic failed and we don't try
1551          * to optimize node fill (it could lead to a degenerate case).
1552          */
1553         node = cursor->node;
1554         ondisk = node->ondisk;
1555         KKASSERT(ondisk->count > 4);
1556         if (cursor->index == ondisk->count &&
1557             (node->flags & HAMMER_NODE_NONLINEAR) == 0) {
1558                 split = (ondisk->count + 1) * 3 / 4;
1559                 node->flags |= HAMMER_NODE_NONLINEAR;
1560         } else {
1561                 /*
1562                  * We are splitting but elms[split] will be promoted to
1563                  * the parent, leaving the right hand node with one less
1564                  * element.  If the insertion point will be on the
1565                  * left-hand side adjust the split point to give the
1566                  * right hand side one additional node.
1567                  */
1568                 split = (ondisk->count + 1) / 2;
1569                 if (cursor->index <= split)
1570                         --split;
1571         }
1572
1573         /*
1574          * If we are at the root of the filesystem, create a new root node
1575          * with 1 element and split normally.  Avoid making major
1576          * modifications until we know the whole operation will work.
1577          */
1578         if (ondisk->parent == 0) {
1579                 parent = hammer_alloc_btree(cursor->trans, node->node_offset,
1580                                             &error);
1581                 if (parent == NULL)
1582                         goto done;
1583                 hammer_lock_ex(&parent->lock);
1584                 hammer_modify_node_noundo(cursor->trans, parent);
1585                 ondisk = parent->ondisk;
1586                 ondisk->count = 1;
1587                 ondisk->parent = 0;
1588                 ondisk->mirror_tid = node->ondisk->mirror_tid;
1589                 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1590                 ondisk->elms[0].base = hmp->root_btree_beg;
1591                 ondisk->elms[0].base.btype = node->ondisk->type;
1592                 ondisk->elms[0].internal.subtree_offset = node->node_offset;
1593                 ondisk->elms[1].base = hmp->root_btree_end;
1594                 hammer_modify_node_done(parent);
1595                 /* ondisk->elms[1].base.btype - not used */
1596                 made_root = 1;
1597                 parent_index = 0;       /* index of current node in parent */
1598         } else {
1599                 made_root = 0;
1600                 parent = cursor->parent;
1601                 parent_index = cursor->parent_index;
1602         }
1603
1604         /*
1605          * Calculate a hint for the allocation of the new B-Tree node.
1606          * The most likely expansion is coming from the insertion point
1607          * at cursor->index, so try to localize the allocation of our
1608          * new node to accomodate that sub-tree.
1609          *
1610          * Use the right-most sub-tree when expandinging on the right edge.
1611          * This is a very common case when copying a directory tree.
1612          */
1613         if (cursor->index == ondisk->count)
1614                 hint = ondisk->elms[cursor->index - 1].internal.subtree_offset;
1615         else
1616                 hint = ondisk->elms[cursor->index].internal.subtree_offset;
1617
1618         /*
1619          * Split node into new_node at the split point.
1620          *
1621          *  B O O O P N N B     <-- P = node->elms[split] (index 4)
1622          *   0 1 2 3 4 5 6      <-- subtree indices
1623          *
1624          *       x x P x x
1625          *        s S S s
1626          *         /   \
1627          *  B O O O B    B N N B        <--- inner boundary points are 'P'
1628          *   0 1 2 3      4 5 6
1629          */
1630         new_node = hammer_alloc_btree(cursor->trans, hint, &error);
1631         if (new_node == NULL) {
1632                 if (made_root) {
1633                         hammer_unlock(&parent->lock);
1634                         hammer_delete_node(cursor->trans, parent);
1635                         hammer_rel_node(parent);
1636                 }
1637                 goto done;
1638         }
1639         hammer_lock_ex(&new_node->lock);
1640
1641         /*
1642          * Create the new node.  P becomes the left-hand boundary in the
1643          * new node.  Copy the right-hand boundary as well.
1644          *
1645          * elm is the new separator.
1646          */
1647         hammer_modify_node_noundo(cursor->trans, new_node);
1648         hammer_modify_node_all(cursor->trans, node);
1649         ondisk = node->ondisk;
1650         elm = &ondisk->elms[split];
1651         bcopy(elm, &new_node->ondisk->elms[0],
1652               (ondisk->count - split + 1) * esize);
1653         new_node->ondisk->count = ondisk->count - split;
1654         new_node->ondisk->parent = parent->node_offset;
1655         new_node->ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1656         new_node->ondisk->mirror_tid = ondisk->mirror_tid;
1657         KKASSERT(ondisk->type == new_node->ondisk->type);
1658         hammer_cursor_split_node(node, new_node, split);
1659
1660         /*
1661          * Cleanup the original node.  Elm (P) becomes the new boundary,
1662          * its subtree_offset was moved to the new node.  If we had created
1663          * a new root its parent pointer may have changed.
1664          */
1665         elm->internal.subtree_offset = 0;
1666         ondisk->count = split;
1667
1668         /*
1669          * Insert the separator into the parent, fixup the parent's
1670          * reference to the original node, and reference the new node.
1671          * The separator is P.
1672          *
1673          * Remember that base.count does not include the right-hand boundary.
1674          */
1675         hammer_modify_node_all(cursor->trans, parent);
1676         ondisk = parent->ondisk;
1677         KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
1678         parent_elm = &ondisk->elms[parent_index+1];
1679         bcopy(parent_elm, parent_elm + 1,
1680               (ondisk->count - parent_index) * esize);
1681         parent_elm->internal.base = elm->base;  /* separator P */
1682         parent_elm->internal.base.btype = new_node->ondisk->type;
1683         parent_elm->internal.subtree_offset = new_node->node_offset;
1684         parent_elm->internal.mirror_tid = new_node->ondisk->mirror_tid;
1685         ++ondisk->count;
1686         hammer_modify_node_done(parent);
1687         hammer_cursor_inserted_element(parent, parent_index + 1);
1688
1689         /*
1690          * The children of new_node need their parent pointer set to new_node.
1691          * The children have already been locked by
1692          * hammer_btree_lock_children().
1693          */
1694         for (i = 0; i < new_node->ondisk->count; ++i) {
1695                 elm = &new_node->ondisk->elms[i];
1696                 error = btree_set_parent(cursor->trans, new_node, elm);
1697                 if (error) {
1698                         panic("btree_split_internal: btree-fixup problem");
1699                 }
1700         }
1701         hammer_modify_node_done(new_node);
1702
1703         /*
1704          * The filesystem's root B-Tree pointer may have to be updated.
1705          */
1706         if (made_root) {
1707                 hammer_volume_t volume;
1708
1709                 volume = hammer_get_root_volume(hmp, &error);
1710                 KKASSERT(error == 0);
1711
1712                 hammer_modify_volume_field(cursor->trans, volume,
1713                                            vol0_btree_root);
1714                 volume->ondisk->vol0_btree_root = parent->node_offset;
1715                 hammer_modify_volume_done(volume);
1716                 node->ondisk->parent = parent->node_offset;
1717                 if (cursor->parent) {
1718                         hammer_unlock(&cursor->parent->lock);
1719                         hammer_rel_node(cursor->parent);
1720                 }
1721                 cursor->parent = parent;        /* lock'd and ref'd */
1722                 hammer_rel_volume(volume, 0);
1723         }
1724         hammer_modify_node_done(node);
1725
1726         /*
1727          * Ok, now adjust the cursor depending on which element the original
1728          * index was pointing at.  If we are >= the split point the push node
1729          * is now in the new node.
1730          *
1731          * NOTE: If we are at the split point itself we cannot stay with the
1732          * original node because the push index will point at the right-hand
1733          * boundary, which is illegal.
1734          *
1735          * NOTE: The cursor's parent or parent_index must be adjusted for
1736          * the case where a new parent (new root) was created, and the case
1737          * where the cursor is now pointing at the split node.
1738          */
1739         if (cursor->index >= split) {
1740                 cursor->parent_index = parent_index + 1;
1741                 cursor->index -= split;
1742                 hammer_unlock(&cursor->node->lock);
1743                 hammer_rel_node(cursor->node);
1744                 cursor->node = new_node;        /* locked and ref'd */
1745         } else {
1746                 cursor->parent_index = parent_index;
1747                 hammer_unlock(&new_node->lock);
1748                 hammer_rel_node(new_node);
1749         }
1750
1751         /*
1752          * Fixup left and right bounds
1753          */
1754         parent_elm = &parent->ondisk->elms[cursor->parent_index];
1755         cursor->left_bound = &parent_elm[0].internal.base;
1756         cursor->right_bound = &parent_elm[1].internal.base;
1757         KKASSERT(hammer_btree_cmp(cursor->left_bound,
1758                  &cursor->node->ondisk->elms[0].internal.base) <= 0);
1759         KKASSERT(hammer_btree_cmp(cursor->right_bound,
1760                  &cursor->node->ondisk->elms[cursor->node->ondisk->count].internal.base) >= 0);
1761
1762 done:
1763         hammer_btree_unlock_children(cursor->trans->hmp, &lockroot, NULL);
1764         hammer_cursor_downgrade(cursor);
1765         return (error);
1766 }
1767
1768 /*
1769  * Same as the above, but splits a full leaf node.
1770  *
1771  * This function
1772  */
1773 static
1774 int
1775 btree_split_leaf(hammer_cursor_t cursor)
1776 {
1777         hammer_node_ondisk_t ondisk;
1778         hammer_node_t parent;
1779         hammer_node_t leaf;
1780         hammer_mount_t hmp;
1781         hammer_node_t new_leaf;
1782         hammer_btree_elm_t elm;
1783         hammer_btree_elm_t parent_elm;
1784         hammer_base_elm_t mid_boundary;
1785         hammer_off_t hint;
1786         int parent_index;
1787         int made_root;
1788         int split;
1789         int error;
1790         const size_t esize = sizeof(*elm);
1791
1792         if ((error = hammer_cursor_upgrade(cursor)) != 0)
1793                 return(error);
1794         ++hammer_stats_btree_splits;
1795
1796         KKASSERT(hammer_btree_cmp(cursor->left_bound,
1797                  &cursor->node->ondisk->elms[0].leaf.base) <= 0);
1798         KKASSERT(hammer_btree_cmp(cursor->right_bound,
1799                  &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
1800
1801         /*
1802          * Calculate the split point.  If the insertion point is at the
1803          * end of the leaf we adjust the split point significantly to the
1804          * right to try to optimize node fill and flag it.  If we hit
1805          * that same leaf again our heuristic failed and we don't try
1806          * to optimize node fill (it could lead to a degenerate case).
1807          *
1808          * Spikes are made up of two leaf elements which cannot be
1809          * safely split.
1810          */
1811         leaf = cursor->node;
1812         ondisk = leaf->ondisk;
1813         KKASSERT(ondisk->count > 4);
1814         if (cursor->index == ondisk->count &&
1815             (leaf->flags & HAMMER_NODE_NONLINEAR) == 0) {
1816                 split = (ondisk->count + 1) * 3 / 4;
1817                 leaf->flags |= HAMMER_NODE_NONLINEAR;
1818         } else {
1819                 split = (ondisk->count + 1) / 2;
1820         }
1821
1822 #if 0
1823         /*
1824          * If the insertion point is at the split point shift the
1825          * split point left so we don't have to worry about
1826          */
1827         if (cursor->index == split)
1828                 --split;
1829 #endif
1830         KKASSERT(split > 0 && split < ondisk->count);
1831
1832         error = 0;
1833         hmp = leaf->hmp;
1834
1835         elm = &ondisk->elms[split];
1836
1837         KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm[-1].leaf.base) <= 0);
1838         KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm->leaf.base) <= 0);
1839         KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm->leaf.base) > 0);
1840         KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm[1].leaf.base) > 0);
1841
1842         /*
1843          * If we are at the root of the tree, create a new root node with
1844          * 1 element and split normally.  Avoid making major modifications
1845          * until we know the whole operation will work.
1846          */
1847         if (ondisk->parent == 0) {
1848                 parent = hammer_alloc_btree(cursor->trans, leaf->node_offset,
1849                                             &error);
1850                 if (parent == NULL)
1851                         goto done;
1852                 hammer_lock_ex(&parent->lock);
1853                 hammer_modify_node_noundo(cursor->trans, parent);
1854                 ondisk = parent->ondisk;
1855                 ondisk->count = 1;
1856                 ondisk->parent = 0;
1857                 ondisk->mirror_tid = leaf->ondisk->mirror_tid;
1858                 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1859                 ondisk->elms[0].base = hmp->root_btree_beg;
1860                 ondisk->elms[0].base.btype = leaf->ondisk->type;
1861                 ondisk->elms[0].internal.subtree_offset = leaf->node_offset;
1862                 ondisk->elms[1].base = hmp->root_btree_end;
1863                 /* ondisk->elms[1].base.btype = not used */
1864                 hammer_modify_node_done(parent);
1865                 made_root = 1;
1866                 parent_index = 0;       /* insertion point in parent */
1867         } else {
1868                 made_root = 0;
1869                 parent = cursor->parent;
1870                 parent_index = cursor->parent_index;
1871         }
1872
1873         /*
1874          * Calculate a hint for the allocation of the new B-Tree leaf node.
1875          * For now just try to localize it within the same bigblock as
1876          * the current leaf.
1877          *
1878          * If the insertion point is at the end of the leaf we recognize a
1879          * likely append sequence of some sort (data, meta-data, inodes,
1880          * whatever).  Set the hint to zero to allocate out of linear space
1881          * instead of trying to completely fill previously hinted space.
1882          *
1883          * This also sets the stage for recursive splits to localize using
1884          * the new space.
1885          */
1886         ondisk = leaf->ondisk;
1887         if (cursor->index == ondisk->count)
1888                 hint = 0;
1889         else
1890                 hint = leaf->node_offset;
1891
1892         /*
1893          * Split leaf into new_leaf at the split point.  Select a separator
1894          * value in-between the two leafs but with a bent towards the right
1895          * leaf since comparisons use an 'elm >= separator' inequality.
1896          *
1897          *  L L L L L L L L
1898          *
1899          *       x x P x x
1900          *        s S S s
1901          *         /   \
1902          *  L L L L     L L L L
1903          */
1904         new_leaf = hammer_alloc_btree(cursor->trans, hint, &error);
1905         if (new_leaf == NULL) {
1906                 if (made_root) {
1907                         hammer_unlock(&parent->lock);
1908                         hammer_delete_node(cursor->trans, parent);
1909                         hammer_rel_node(parent);
1910                 }
1911                 goto done;
1912         }
1913         hammer_lock_ex(&new_leaf->lock);
1914
1915         /*
1916          * Create the new node and copy the leaf elements from the split
1917          * point on to the new node.
1918          */
1919         hammer_modify_node_all(cursor->trans, leaf);
1920         hammer_modify_node_noundo(cursor->trans, new_leaf);
1921         ondisk = leaf->ondisk;
1922         elm = &ondisk->elms[split];
1923         bcopy(elm, &new_leaf->ondisk->elms[0], (ondisk->count - split) * esize);
1924         new_leaf->ondisk->count = ondisk->count - split;
1925         new_leaf->ondisk->parent = parent->node_offset;
1926         new_leaf->ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1927         new_leaf->ondisk->mirror_tid = ondisk->mirror_tid;
1928         KKASSERT(ondisk->type == new_leaf->ondisk->type);
1929         hammer_modify_node_done(new_leaf);
1930         hammer_cursor_split_node(leaf, new_leaf, split);
1931
1932         /*
1933          * Cleanup the original node.  Because this is a leaf node and
1934          * leaf nodes do not have a right-hand boundary, there
1935          * aren't any special edge cases to clean up.  We just fixup the
1936          * count.
1937          */
1938         ondisk->count = split;
1939
1940         /*
1941          * Insert the separator into the parent, fixup the parent's
1942          * reference to the original node, and reference the new node.
1943          * The separator is P.
1944          *
1945          * Remember that base.count does not include the right-hand boundary.
1946          * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1947          */
1948         hammer_modify_node_all(cursor->trans, parent);
1949         ondisk = parent->ondisk;
1950         KKASSERT(split != 0);
1951         KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
1952         parent_elm = &ondisk->elms[parent_index+1];
1953         bcopy(parent_elm, parent_elm + 1,
1954               (ondisk->count - parent_index) * esize);
1955
1956         hammer_make_separator(&elm[-1].base, &elm[0].base, &parent_elm->base);
1957         parent_elm->internal.base.btype = new_leaf->ondisk->type;
1958         parent_elm->internal.subtree_offset = new_leaf->node_offset;
1959         parent_elm->internal.mirror_tid = new_leaf->ondisk->mirror_tid;
1960         mid_boundary = &parent_elm->base;
1961         ++ondisk->count;
1962         hammer_modify_node_done(parent);
1963         hammer_cursor_inserted_element(parent, parent_index + 1);
1964
1965         /*
1966          * The filesystem's root B-Tree pointer may have to be updated.
1967          */
1968         if (made_root) {
1969                 hammer_volume_t volume;
1970
1971                 volume = hammer_get_root_volume(hmp, &error);
1972                 KKASSERT(error == 0);
1973
1974                 hammer_modify_volume_field(cursor->trans, volume,
1975                                            vol0_btree_root);
1976                 volume->ondisk->vol0_btree_root = parent->node_offset;
1977                 hammer_modify_volume_done(volume);
1978                 leaf->ondisk->parent = parent->node_offset;
1979                 if (cursor->parent) {
1980                         hammer_unlock(&cursor->parent->lock);
1981                         hammer_rel_node(cursor->parent);
1982                 }
1983                 cursor->parent = parent;        /* lock'd and ref'd */
1984                 hammer_rel_volume(volume, 0);
1985         }
1986         hammer_modify_node_done(leaf);
1987
1988         /*
1989          * Ok, now adjust the cursor depending on which element the original
1990          * index was pointing at.  If we are >= the split point the push node
1991          * is now in the new node.
1992          *
1993          * NOTE: If we are at the split point itself we need to select the
1994          * old or new node based on where key_beg's insertion point will be.
1995          * If we pick the wrong side the inserted element will wind up in
1996          * the wrong leaf node and outside that node's bounds.
1997          */
1998         if (cursor->index > split ||
1999             (cursor->index == split &&
2000              hammer_btree_cmp(&cursor->key_beg, mid_boundary) >= 0)) {
2001                 cursor->parent_index = parent_index + 1;
2002                 cursor->index -= split;
2003                 hammer_unlock(&cursor->node->lock);
2004                 hammer_rel_node(cursor->node);
2005                 cursor->node = new_leaf;
2006         } else {
2007                 cursor->parent_index = parent_index;
2008                 hammer_unlock(&new_leaf->lock);
2009                 hammer_rel_node(new_leaf);
2010         }
2011
2012         /*
2013          * Fixup left and right bounds
2014          */
2015         parent_elm = &parent->ondisk->elms[cursor->parent_index];
2016         cursor->left_bound = &parent_elm[0].internal.base;
2017         cursor->right_bound = &parent_elm[1].internal.base;
2018
2019         /*
2020          * Assert that the bounds are correct.
2021          */
2022         KKASSERT(hammer_btree_cmp(cursor->left_bound,
2023                  &cursor->node->ondisk->elms[0].leaf.base) <= 0);
2024         KKASSERT(hammer_btree_cmp(cursor->right_bound,
2025                  &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
2026         KKASSERT(hammer_btree_cmp(cursor->left_bound, &cursor->key_beg) <= 0);
2027         KKASSERT(hammer_btree_cmp(cursor->right_bound, &cursor->key_beg) > 0);
2028
2029 done:
2030         hammer_cursor_downgrade(cursor);
2031         return (error);
2032 }
2033
2034 #if 0
2035
2036 /*
2037  * Recursively correct the right-hand boundary's create_tid to (tid) as
2038  * long as the rest of the key matches.  We have to recurse upward in
2039  * the tree as well as down the left side of each parent's right node.
2040  *
2041  * Return EDEADLK if we were only partially successful, forcing the caller
2042  * to try again.  The original cursor is not modified.  This routine can
2043  * also fail with EDEADLK if it is forced to throw away a portion of its
2044  * record history.
2045  *
2046  * The caller must pass a downgraded cursor to us (otherwise we can't dup it).
2047  */
2048 struct hammer_rhb {
2049         TAILQ_ENTRY(hammer_rhb) entry;
2050         hammer_node_t   node;
2051         int             index;
2052 };
2053
2054 TAILQ_HEAD(hammer_rhb_list, hammer_rhb);
2055
2056 int
2057 hammer_btree_correct_rhb(hammer_cursor_t cursor, hammer_tid_t tid)
2058 {
2059         struct hammer_mount *hmp;
2060         struct hammer_rhb_list rhb_list;
2061         hammer_base_elm_t elm;
2062         hammer_node_t orig_node;
2063         struct hammer_rhb *rhb;
2064         int orig_index;
2065         int error;
2066
2067         TAILQ_INIT(&rhb_list);
2068         hmp = cursor->trans->hmp;
2069
2070         /*
2071          * Save our position so we can restore it on return.  This also
2072          * gives us a stable 'elm'.
2073          */
2074         orig_node = cursor->node;
2075         hammer_ref_node(orig_node);
2076         hammer_lock_sh(&orig_node->lock);
2077         orig_index = cursor->index;
2078         elm = &orig_node->ondisk->elms[orig_index].base;
2079
2080         /*
2081          * Now build a list of parents going up, allocating a rhb
2082          * structure for each one.
2083          */
2084         while (cursor->parent) {
2085                 /*
2086                  * Stop if we no longer have any right-bounds to fix up
2087                  */
2088                 if (elm->obj_id != cursor->right_bound->obj_id ||
2089                     elm->rec_type != cursor->right_bound->rec_type ||
2090                     elm->key != cursor->right_bound->key) {
2091                         break;
2092                 }
2093
2094                 /*
2095                  * Stop if the right-hand bound's create_tid does not
2096                  * need to be corrected.
2097                  */
2098                 if (cursor->right_bound->create_tid >= tid)
2099                         break;
2100
2101                 rhb = kmalloc(sizeof(*rhb), hmp->m_misc, M_WAITOK|M_ZERO);
2102                 rhb->node = cursor->parent;
2103                 rhb->index = cursor->parent_index;
2104                 hammer_ref_node(rhb->node);
2105                 hammer_lock_sh(&rhb->node->lock);
2106                 TAILQ_INSERT_HEAD(&rhb_list, rhb, entry);
2107
2108                 hammer_cursor_up(cursor);
2109         }
2110
2111         /*
2112          * now safely adjust the right hand bound for each rhb.  This may
2113          * also require taking the right side of the tree and iterating down
2114          * ITS left side.
2115          */
2116         error = 0;
2117         while (error == 0 && (rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2118                 error = hammer_cursor_seek(cursor, rhb->node, rhb->index);
2119                 if (error)
2120                         break;
2121                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2122                 hammer_unlock(&rhb->node->lock);
2123                 hammer_rel_node(rhb->node);
2124                 kfree(rhb, hmp->m_misc);
2125
2126                 switch (cursor->node->ondisk->type) {
2127                 case HAMMER_BTREE_TYPE_INTERNAL:
2128                         /*
2129                          * Right-boundary for parent at internal node
2130                          * is one element to the right of the element whos
2131                          * right boundary needs adjusting.  We must then
2132                          * traverse down the left side correcting any left
2133                          * bounds (which may now be too far to the left).
2134                          */
2135                         ++cursor->index;
2136                         error = hammer_btree_correct_lhb(cursor, tid);
2137                         break;
2138                 default:
2139                         panic("hammer_btree_correct_rhb(): Bad node type");
2140                         error = EINVAL;
2141                         break;
2142                 }
2143         }
2144
2145         /*
2146          * Cleanup
2147          */
2148         while ((rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2149                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2150                 hammer_unlock(&rhb->node->lock);
2151                 hammer_rel_node(rhb->node);
2152                 kfree(rhb, hmp->m_misc);
2153         }
2154         error = hammer_cursor_seek(cursor, orig_node, orig_index);
2155         hammer_unlock(&orig_node->lock);
2156         hammer_rel_node(orig_node);
2157         return (error);
2158 }
2159
2160 /*
2161  * Similar to rhb (in fact, rhb calls lhb), but corrects the left hand
2162  * bound going downward starting at the current cursor position.
2163  *
2164  * This function does not restore the cursor after use.
2165  */
2166 int
2167 hammer_btree_correct_lhb(hammer_cursor_t cursor, hammer_tid_t tid)
2168 {
2169         struct hammer_rhb_list rhb_list;
2170         hammer_base_elm_t elm;
2171         hammer_base_elm_t cmp;
2172         struct hammer_rhb *rhb;
2173         struct hammer_mount *hmp;
2174         int error;
2175
2176         TAILQ_INIT(&rhb_list);
2177         hmp = cursor->trans->hmp;
2178
2179         cmp = &cursor->node->ondisk->elms[cursor->index].base;
2180
2181         /*
2182          * Record the node and traverse down the left-hand side for all
2183          * matching records needing a boundary correction.
2184          */
2185         error = 0;
2186         for (;;) {
2187                 rhb = kmalloc(sizeof(*rhb), hmp->m_misc, M_WAITOK|M_ZERO);
2188                 rhb->node = cursor->node;
2189                 rhb->index = cursor->index;
2190                 hammer_ref_node(rhb->node);
2191                 hammer_lock_sh(&rhb->node->lock);
2192                 TAILQ_INSERT_HEAD(&rhb_list, rhb, entry);
2193
2194                 if (cursor->node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
2195                         /*
2196                          * Nothing to traverse down if we are at the right
2197                          * boundary of an internal node.
2198                          */
2199                         if (cursor->index == cursor->node->ondisk->count)
2200                                 break;
2201                 } else {
2202                         elm = &cursor->node->ondisk->elms[cursor->index].base;
2203                         if (elm->btype == HAMMER_BTREE_TYPE_RECORD)
2204                                 break;
2205                         panic("Illegal leaf record type %02x", elm->btype);
2206                 }
2207                 error = hammer_cursor_down(cursor);
2208                 if (error)
2209                         break;
2210
2211                 elm = &cursor->node->ondisk->elms[cursor->index].base;
2212                 if (elm->obj_id != cmp->obj_id ||
2213                     elm->rec_type != cmp->rec_type ||
2214                     elm->key != cmp->key) {
2215                         break;
2216                 }
2217                 if (elm->create_tid >= tid)
2218                         break;
2219
2220         }
2221
2222         /*
2223          * Now we can safely adjust the left-hand boundary from the bottom-up.
2224          * The last element we remove from the list is the caller's right hand
2225          * boundary, which must also be adjusted.
2226          */
2227         while (error == 0 && (rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2228                 error = hammer_cursor_seek(cursor, rhb->node, rhb->index);
2229                 if (error)
2230                         break;
2231                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2232                 hammer_unlock(&rhb->node->lock);
2233                 hammer_rel_node(rhb->node);
2234                 kfree(rhb, hmp->m_misc);
2235
2236                 elm = &cursor->node->ondisk->elms[cursor->index].base;
2237                 if (cursor->node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
2238                         hammer_modify_node(cursor->trans, cursor->node,
2239                                            &elm->create_tid,
2240                                            sizeof(elm->create_tid));
2241                         elm->create_tid = tid;
2242                         hammer_modify_node_done(cursor->node);
2243                 } else {
2244                         panic("hammer_btree_correct_lhb(): Bad element type");
2245                 }
2246         }
2247
2248         /*
2249          * Cleanup
2250          */
2251         while ((rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2252                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2253                 hammer_unlock(&rhb->node->lock);
2254                 hammer_rel_node(rhb->node);
2255                 kfree(rhb, hmp->m_misc);
2256         }
2257         return (error);
2258 }
2259
2260 #endif
2261
2262 /*
2263  * Attempt to remove the locked, empty or want-to-be-empty B-Tree node at
2264  * (cursor->node).  Returns 0 on success, EDEADLK if we could not complete
2265  * the operation due to a deadlock, or some other error.
2266  *
2267  * This routine is initially called with an empty leaf and may be
2268  * recursively called with single-element internal nodes.
2269  *
2270  * It should also be noted that when removing empty leaves we must be sure
2271  * to test and update mirror_tid because another thread may have deadlocked
2272  * against us (or someone) trying to propagate it up and cannot retry once
2273  * the node has been deleted.
2274  *
2275  * On return the cursor may end up pointing to an internal node, suitable
2276  * for further iteration but not for an immediate insertion or deletion.
2277  */
2278 static int
2279 btree_remove(hammer_cursor_t cursor)
2280 {
2281         hammer_node_ondisk_t ondisk;
2282         hammer_btree_elm_t elm;
2283         hammer_node_t node;
2284         hammer_node_t parent;
2285         const int esize = sizeof(*elm);
2286         int error;
2287
2288         node = cursor->node;
2289
2290         /*
2291          * When deleting the root of the filesystem convert it to
2292          * an empty leaf node.  Internal nodes cannot be empty.
2293          */
2294         ondisk = node->ondisk;
2295         if (ondisk->parent == 0) {
2296                 KKASSERT(cursor->parent == NULL);
2297                 hammer_modify_node_all(cursor->trans, node);
2298                 KKASSERT(ondisk == node->ondisk);
2299                 ondisk->type = HAMMER_BTREE_TYPE_LEAF;
2300                 ondisk->count = 0;
2301                 hammer_modify_node_done(node);
2302                 cursor->index = 0;
2303                 return(0);
2304         }
2305
2306         parent = cursor->parent;
2307
2308         /*
2309          * Attempt to remove the parent's reference to the child.  If the
2310          * parent would become empty we have to recurse.  If we fail we
2311          * leave the parent pointing to an empty leaf node.
2312          *
2313          * We have to recurse successfully before we can delete the internal
2314          * node as it is illegal to have empty internal nodes.  Even though
2315          * the operation may be aborted we must still fixup any unlocked
2316          * cursors as if we had deleted the element prior to recursing
2317          * (by calling hammer_cursor_deleted_element()) so those cursors
2318          * are properly forced up the chain by the recursion.
2319          */
2320         if (parent->ondisk->count == 1) {
2321                 /*
2322                  * This special cursor_up_locked() call leaves the original
2323                  * node exclusively locked and referenced, leaves the
2324                  * original parent locked (as the new node), and locks the
2325                  * new parent.  It can return EDEADLK.
2326                  *
2327                  * We cannot call hammer_cursor_removed_node() until we are
2328                  * actually able to remove the node.  If we did then tracked
2329                  * cursors in the middle of iterations could be repointed
2330                  * to a parent node.  If this occurs they could end up
2331                  * scanning newly inserted records into the node (that could
2332                  * not be deleted) when they push down again.
2333                  *
2334                  * Due to the way the recursion works the final parent is left
2335                  * in cursor->parent after the recursion returns.  Each
2336                  * layer on the way back up is thus able to call
2337                  * hammer_cursor_removed_node() and 'jump' the node up to
2338                  * the (same) final parent.
2339                  *
2340                  * NOTE!  The local variable 'parent' is invalid after we
2341                  *        call hammer_cursor_up_locked().
2342                  */
2343                 error = hammer_cursor_up_locked(cursor);
2344                 parent = NULL;
2345
2346                 if (error == 0) {
2347                         hammer_cursor_deleted_element(cursor->node, 0);
2348                         error = btree_remove(cursor);
2349                         if (error == 0) {
2350                                 KKASSERT(node != cursor->node);
2351                                 hammer_cursor_removed_node(
2352                                         node, cursor->node,
2353                                         cursor->index);
2354                                 hammer_modify_node_all(cursor->trans, node);
2355                                 ondisk = node->ondisk;
2356                                 ondisk->type = HAMMER_BTREE_TYPE_DELETED;
2357                                 ondisk->count = 0;
2358                                 hammer_modify_node_done(node);
2359                                 hammer_flush_node(node, 0);
2360                                 hammer_delete_node(cursor->trans, node);
2361                         } else {
2362                                 /*
2363                                  * Defer parent removal because we could not
2364                                  * get the lock, just let the leaf remain
2365                                  * empty.
2366                                  */
2367                                 /**/
2368                         }
2369                         hammer_unlock(&node->lock);
2370                         hammer_rel_node(node);
2371                 } else {
2372                         /*
2373                          * Defer parent removal because we could not
2374                          * get the lock, just let the leaf remain
2375                          * empty.
2376                          */
2377                         /**/
2378                 }
2379         } else {
2380                 KKASSERT(parent->ondisk->count > 1);
2381
2382                 hammer_modify_node_all(cursor->trans, parent);
2383                 ondisk = parent->ondisk;
2384                 KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
2385
2386                 elm = &ondisk->elms[cursor->parent_index];
2387                 KKASSERT(elm->internal.subtree_offset == node->node_offset);
2388                 KKASSERT(ondisk->count > 0);
2389
2390                 /*
2391                  * We must retain the highest mirror_tid.  The deleted
2392                  * range is now encompassed by the element to the left.
2393                  * If we are already at the left edge the new left edge
2394                  * inherits mirror_tid.
2395                  *
2396                  * Note that bounds of the parent to our parent may create
2397                  * a gap to the left of our left-most node or to the right
2398                  * of our right-most node.  The gap is silently included
2399                  * in the mirror_tid's area of effect from the point of view
2400                  * of the scan.
2401                  */
2402                 if (cursor->parent_index) {
2403                         if (elm[-1].internal.mirror_tid <
2404                             elm[0].internal.mirror_tid) {
2405                                 elm[-1].internal.mirror_tid =
2406                                     elm[0].internal.mirror_tid;
2407                         }
2408                 } else {
2409                         if (elm[1].internal.mirror_tid <
2410                             elm[0].internal.mirror_tid) {
2411                                 elm[1].internal.mirror_tid =
2412                                     elm[0].internal.mirror_tid;
2413                         }
2414                 }
2415
2416                 /*
2417                  * Delete the subtree reference in the parent.  Include
2418                  * boundary element at end.
2419                  */
2420                 bcopy(&elm[1], &elm[0],
2421                       (ondisk->count - cursor->parent_index) * esize);
2422                 --ondisk->count;
2423                 hammer_modify_node_done(parent);
2424                 hammer_cursor_removed_node(node, parent, cursor->parent_index);
2425                 hammer_cursor_deleted_element(parent, cursor->parent_index);
2426                 hammer_flush_node(node, 0);
2427                 hammer_delete_node(cursor->trans, node);
2428
2429                 /*
2430                  * cursor->node is invalid, cursor up to make the cursor
2431                  * valid again.  We have to flag the condition in case
2432                  * another thread wiggles an insertion in during an
2433                  * iteration.
2434                  */
2435                 cursor->flags |= HAMMER_CURSOR_ITERATE_CHECK;
2436                 error = hammer_cursor_up(cursor);
2437         }
2438         return (error);
2439 }
2440
2441 /*
2442  * Propagate cursor->trans->tid up the B-Tree starting at the current
2443  * cursor position using pseudofs info gleaned from the passed inode.
2444  *
2445  * The passed inode has no relationship to the cursor position other
2446  * then being in the same pseudofs as the insertion or deletion we
2447  * are propagating the mirror_tid for.
2448  *
2449  * WARNING!  Because we push and pop the passed cursor, it may be
2450  *           modified by other B-Tree operations while it is unlocked
2451  *           and things like the node & leaf pointers, and indexes might
2452  *           change.
2453  */
2454 void
2455 hammer_btree_do_propagation(hammer_cursor_t cursor,
2456                             hammer_pseudofs_inmem_t pfsm,
2457                             hammer_btree_leaf_elm_t leaf)
2458 {
2459         hammer_cursor_t ncursor;
2460         hammer_tid_t mirror_tid;
2461         int error;
2462
2463         /*
2464          * We do not propagate a mirror_tid if the filesystem was mounted
2465          * in no-mirror mode.
2466          */
2467         if (cursor->trans->hmp->master_id < 0)
2468                 return;
2469
2470         /*
2471          * This is a bit of a hack because we cannot deadlock or return
2472          * EDEADLK here.  The related operation has already completed and
2473          * we must propagate the mirror_tid now regardless.
2474          *
2475          * Generate a new cursor which inherits the original's locks and
2476          * unlock the original.  Use the new cursor to propagate the
2477          * mirror_tid.  Then clean up the new cursor and reacquire locks
2478          * on the original.
2479          *
2480          * hammer_dup_cursor() cannot dup locks.  The dup inherits the
2481          * original's locks and the original is tracked and must be
2482          * re-locked.
2483          */
2484         mirror_tid = cursor->node->ondisk->mirror_tid;
2485         KKASSERT(mirror_tid != 0);
2486         ncursor = hammer_push_cursor(cursor);
2487         error = hammer_btree_mirror_propagate(ncursor, mirror_tid);
2488         KKASSERT(error == 0);
2489         hammer_pop_cursor(cursor, ncursor);
2490         /* WARNING: cursor's leaf pointer may change after pop */
2491 }
2492
2493
2494 /*
2495  * Propagate a mirror TID update upwards through the B-Tree to the root.
2496  *
2497  * A locked internal node must be passed in.  The node will remain locked
2498  * on return.
2499  *
2500  * This function syncs mirror_tid at the specified internal node's element,
2501  * adjusts the node's aggregation mirror_tid, and then recurses upwards.
2502  */
2503 static int
2504 hammer_btree_mirror_propagate(hammer_cursor_t cursor, hammer_tid_t mirror_tid)
2505 {
2506         hammer_btree_internal_elm_t elm;
2507         hammer_node_t node;
2508         int error;
2509
2510         for (;;) {
2511                 error = hammer_cursor_up(cursor);
2512                 if (error == 0)
2513                         error = hammer_cursor_upgrade(cursor);
2514
2515                 /*
2516                  * We can ignore HAMMER_CURSOR_ITERATE_CHECK, the
2517                  * cursor will still be properly positioned for
2518                  * mirror propagation, just not for iterations.
2519                  */
2520                 while (error == EDEADLK) {
2521                         hammer_recover_cursor(cursor);
2522                         error = hammer_cursor_upgrade(cursor);
2523                 }
2524                 if (error)
2525                         break;
2526
2527                 /*
2528                  * If the cursor deadlocked it could end up at a leaf
2529                  * after we lost the lock.
2530                  */
2531                 node = cursor->node;
2532                 if (node->ondisk->type != HAMMER_BTREE_TYPE_INTERNAL)
2533                         continue;
2534
2535                 /*
2536                  * Adjust the node's element
2537                  */
2538                 elm = &node->ondisk->elms[cursor->index].internal;
2539                 if (elm->mirror_tid >= mirror_tid)
2540                         break;
2541                 hammer_modify_node(cursor->trans, node, &elm->mirror_tid,
2542                                    sizeof(elm->mirror_tid));
2543                 elm->mirror_tid = mirror_tid;
2544                 hammer_modify_node_done(node);
2545                 if (hammer_debug_general & 0x0002) {
2546                         kprintf("mirror_propagate: propagate "
2547                                 "%016llx @%016llx:%d\n",
2548                                 (long long)mirror_tid,
2549                                 (long long)node->node_offset,
2550                                 cursor->index);
2551                 }
2552
2553
2554                 /*
2555                  * Adjust the node's mirror_tid aggregator
2556                  */
2557                 if (node->ondisk->mirror_tid >= mirror_tid)
2558                         return(0);
2559                 hammer_modify_node_field(cursor->trans, node, mirror_tid);
2560                 node->ondisk->mirror_tid = mirror_tid;
2561                 hammer_modify_node_done(node);
2562                 if (hammer_debug_general & 0x0002) {
2563                         kprintf("mirror_propagate: propagate "
2564                                 "%016llx @%016llx\n",
2565                                 (long long)mirror_tid,
2566                                 (long long)node->node_offset);
2567                 }
2568         }
2569         if (error == ENOENT)
2570                 error = 0;
2571         return(error);
2572 }
2573
2574 hammer_node_t
2575 hammer_btree_get_parent(hammer_transaction_t trans, hammer_node_t node,
2576                         int *parent_indexp, int *errorp, int try_exclusive)
2577 {
2578         hammer_node_t parent;
2579         hammer_btree_elm_t elm;
2580         int i;
2581
2582         /*
2583          * Get the node
2584          */
2585         parent = hammer_get_node(trans, node->ondisk->parent, 0, errorp);
2586         if (*errorp) {
2587                 KKASSERT(parent == NULL);
2588                 return(NULL);
2589         }
2590         KKASSERT ((parent->flags & HAMMER_NODE_DELETED) == 0);
2591
2592         /*
2593          * Lock the node
2594          */
2595         if (try_exclusive) {
2596                 if (hammer_lock_ex_try(&parent->lock)) {
2597                         hammer_rel_node(parent);
2598                         *errorp = EDEADLK;
2599                         return(NULL);
2600                 }
2601         } else {
2602                 hammer_lock_sh(&parent->lock);
2603         }
2604
2605         /*
2606          * Figure out which element in the parent is pointing to the
2607          * child.
2608          */
2609         if (node->ondisk->count) {
2610                 i = hammer_btree_search_node(&node->ondisk->elms[0].base,
2611                                              parent->ondisk);
2612         } else {
2613                 i = 0;
2614         }
2615         while (i < parent->ondisk->count) {
2616                 elm = &parent->ondisk->elms[i];
2617                 if (elm->internal.subtree_offset == node->node_offset)
2618                         break;
2619                 ++i;
2620         }
2621         if (i == parent->ondisk->count) {
2622                 hammer_unlock(&parent->lock);
2623                 panic("Bad B-Tree link: parent %p node %p\n", parent, node);
2624         }
2625         *parent_indexp = i;
2626         KKASSERT(*errorp == 0);
2627         return(parent);
2628 }
2629
2630 /*
2631  * The element (elm) has been moved to a new internal node (node).
2632  *
2633  * If the element represents a pointer to an internal node that node's
2634  * parent must be adjusted to the element's new location.
2635  *
2636  * XXX deadlock potential here with our exclusive locks
2637  */
2638 int
2639 btree_set_parent(hammer_transaction_t trans, hammer_node_t node,
2640                  hammer_btree_elm_t elm)
2641 {
2642         hammer_node_t child;
2643         int error;
2644
2645         error = 0;
2646
2647         switch(elm->base.btype) {
2648         case HAMMER_BTREE_TYPE_INTERNAL:
2649         case HAMMER_BTREE_TYPE_LEAF:
2650                 child = hammer_get_node(trans, elm->internal.subtree_offset,
2651                                         0, &error);
2652                 if (error == 0) {
2653                         hammer_modify_node_field(trans, child, parent);
2654                         child->ondisk->parent = node->node_offset;
2655                         hammer_modify_node_done(child);
2656                         hammer_rel_node(child);
2657                 }
2658                 break;
2659         default:
2660                 break;
2661         }
2662         return(error);
2663 }
2664
2665 /*
2666  * Initialize the root of a recursive B-Tree node lock list structure.
2667  */
2668 void
2669 hammer_node_lock_init(hammer_node_lock_t parent, hammer_node_t node)
2670 {
2671         TAILQ_INIT(&parent->list);
2672         parent->parent = NULL;
2673         parent->node = node;
2674         parent->index = -1;
2675         parent->count = node->ondisk->count;
2676         parent->copy = NULL;
2677         parent->flags = 0;
2678 }
2679
2680 /*
2681  * Initialize a cache of hammer_node_lock's including space allocated
2682  * for node copies.
2683  *
2684  * This is used by the rebalancing code to preallocate the copy space
2685  * for ~4096 B-Tree nodes (16MB of data) prior to acquiring any HAMMER
2686  * locks, otherwise we can blow out the pageout daemon's emergency
2687  * reserve and deadlock it.
2688  *
2689  * NOTE: HAMMER_NODE_LOCK_LCACHE is not set on items cached in the lcache.
2690  *       The flag is set when the item is pulled off the cache for use.
2691  */
2692 void
2693 hammer_btree_lcache_init(hammer_mount_t hmp, hammer_node_lock_t lcache,
2694                          int depth)
2695 {
2696         hammer_node_lock_t item;
2697         int count;
2698
2699         for (count = 1; depth; --depth)
2700                 count *= HAMMER_BTREE_LEAF_ELMS;
2701         bzero(lcache, sizeof(*lcache));
2702         TAILQ_INIT(&lcache->list);
2703         while (count) {
2704                 item = kmalloc(sizeof(*item), hmp->m_misc, M_WAITOK|M_ZERO);
2705                 item->copy = kmalloc(sizeof(*item->copy),
2706                                      hmp->m_misc, M_WAITOK);
2707                 TAILQ_INIT(&item->list);
2708                 TAILQ_INSERT_TAIL(&lcache->list, item, entry);
2709                 --count;
2710         }
2711 }
2712
2713 void
2714 hammer_btree_lcache_free(hammer_mount_t hmp, hammer_node_lock_t lcache)
2715 {
2716         hammer_node_lock_t item;
2717
2718         while ((item = TAILQ_FIRST(&lcache->list)) != NULL) {
2719                 TAILQ_REMOVE(&lcache->list, item, entry);
2720                 KKASSERT(item->copy);
2721                 KKASSERT(TAILQ_EMPTY(&item->list));
2722                 kfree(item->copy, hmp->m_misc);
2723                 kfree(item, hmp->m_misc);
2724         }
2725         KKASSERT(lcache->copy == NULL);
2726 }
2727
2728 /*
2729  * Exclusively lock all the children of node.  This is used by the split
2730  * code to prevent anyone from accessing the children of a cursor node
2731  * while we fix-up its parent offset.
2732  *
2733  * If we don't lock the children we can really mess up cursors which block
2734  * trying to cursor-up into our node.
2735  *
2736  * On failure EDEADLK (or some other error) is returned.  If a deadlock
2737  * error is returned the cursor is adjusted to block on termination.
2738  *
2739  * The caller is responsible for managing parent->node, the root's node
2740  * is usually aliased from a cursor.
2741  */
2742 int
2743 hammer_btree_lock_children(hammer_cursor_t cursor, int depth,
2744                            hammer_node_lock_t parent,
2745                            hammer_node_lock_t lcache)
2746 {
2747         hammer_node_t node;
2748         hammer_node_lock_t item;
2749         hammer_node_ondisk_t ondisk;
2750         hammer_btree_elm_t elm;
2751         hammer_node_t child;
2752         struct hammer_mount *hmp;
2753         int error;
2754         int i;
2755
2756         node = parent->node;
2757         ondisk = node->ondisk;
2758         error = 0;
2759         hmp = cursor->trans->hmp;
2760
2761         /*
2762          * We really do not want to block on I/O with exclusive locks held,
2763          * pre-get the children before trying to lock the mess.  This is
2764          * only done one-level deep for now.
2765          */
2766         for (i = 0; i < ondisk->count; ++i) {
2767                 ++hammer_stats_btree_elements;
2768                 elm = &ondisk->elms[i];
2769                 if (elm->base.btype != HAMMER_BTREE_TYPE_LEAF &&
2770                     elm->base.btype != HAMMER_BTREE_TYPE_INTERNAL) {
2771                         continue;
2772                 }
2773                 child = hammer_get_node(cursor->trans,
2774                                         elm->internal.subtree_offset,
2775                                         0, &error);
2776                 if (child)
2777                         hammer_rel_node(child);
2778         }
2779
2780         /*
2781          * Do it for real
2782          */
2783         for (i = 0; error == 0 && i < ondisk->count; ++i) {
2784                 ++hammer_stats_btree_elements;
2785                 elm = &ondisk->elms[i];
2786
2787                 switch(elm->base.btype) {
2788                 case HAMMER_BTREE_TYPE_INTERNAL:
2789                 case HAMMER_BTREE_TYPE_LEAF:
2790                         KKASSERT(elm->internal.subtree_offset != 0);
2791                         child = hammer_get_node(cursor->trans,
2792                                                 elm->internal.subtree_offset,
2793                                                 0, &error);
2794                         break;
2795                 default:
2796                         child = NULL;
2797                         break;
2798                 }
2799                 if (child) {
2800                         if (hammer_lock_ex_try(&child->lock) != 0) {
2801                                 if (cursor->deadlk_node == NULL) {
2802                                         cursor->deadlk_node = child;
2803                                         hammer_ref_node(cursor->deadlk_node);
2804                                 }
2805                                 error = EDEADLK;
2806                                 hammer_rel_node(child);
2807                         } else {
2808                                 if (lcache) {
2809                                         item = TAILQ_FIRST(&lcache->list);
2810                                         KKASSERT(item != NULL);
2811                                         item->flags |= HAMMER_NODE_LOCK_LCACHE;
2812                                         TAILQ_REMOVE(&lcache->list,
2813                                                      item, entry);
2814                                 } else {
2815                                         item = kmalloc(sizeof(*item),
2816                                                        hmp->m_misc,
2817                                                        M_WAITOK|M_ZERO);
2818                                         TAILQ_INIT(&item->list);
2819                                 }
2820
2821                                 TAILQ_INSERT_TAIL(&parent->list, item, entry);
2822                                 item->parent = parent;
2823                                 item->node = child;
2824                                 item->index = i;
2825                                 item->count = child->ondisk->count;
2826
2827                                 /*
2828                                  * Recurse (used by the rebalancing code)
2829                                  */
2830                                 if (depth > 1 && elm->base.btype == HAMMER_BTREE_TYPE_INTERNAL) {
2831                                         error = hammer_btree_lock_children(
2832                                                         cursor,
2833                                                         depth - 1,
2834                                                         item,
2835                                                         lcache);
2836                                 }
2837                         }
2838                 }
2839         }
2840         if (error)
2841                 hammer_btree_unlock_children(hmp, parent, lcache);
2842         return(error);
2843 }
2844
2845 /*
2846  * Create an in-memory copy of all B-Tree nodes listed, recursively,
2847  * including the parent.
2848  */
2849 void
2850 hammer_btree_lock_copy(hammer_cursor_t cursor, hammer_node_lock_t parent)
2851 {
2852         hammer_mount_t hmp = cursor->trans->hmp;
2853         hammer_node_lock_t item;
2854
2855         if (parent->copy == NULL) {
2856                 KKASSERT((parent->flags & HAMMER_NODE_LOCK_LCACHE) == 0);
2857                 parent->copy = kmalloc(sizeof(*parent->copy),
2858                                        hmp->m_misc, M_WAITOK);
2859         }
2860         KKASSERT((parent->flags & HAMMER_NODE_LOCK_UPDATED) == 0);
2861         *parent->copy = *parent->node->ondisk;
2862         TAILQ_FOREACH(item, &parent->list, entry) {
2863                 hammer_btree_lock_copy(cursor, item);
2864         }
2865 }
2866
2867 /*
2868  * Recursively sync modified copies to the media.
2869  */
2870 int
2871 hammer_btree_sync_copy(hammer_cursor_t cursor, hammer_node_lock_t parent)
2872 {
2873         hammer_node_lock_t item;
2874         int count = 0;
2875
2876         if (parent->flags & HAMMER_NODE_LOCK_UPDATED) {
2877                 ++count;
2878                 hammer_modify_node_all(cursor->trans, parent->node);
2879                 *parent->node->ondisk = *parent->copy;
2880                 hammer_modify_node_done(parent->node);
2881                 if (parent->copy->type == HAMMER_BTREE_TYPE_DELETED) {
2882                         hammer_flush_node(parent->node, 0);
2883                         hammer_delete_node(cursor->trans, parent->node);
2884                 }
2885         }
2886         TAILQ_FOREACH(item, &parent->list, entry) {
2887                 count += hammer_btree_sync_copy(cursor, item);
2888         }
2889         return(count);
2890 }
2891
2892 /*
2893  * Release previously obtained node locks.  The caller is responsible for
2894  * cleaning up parent->node itself (its usually just aliased from a cursor),
2895  * but this function will take care of the copies.
2896  *
2897  * NOTE: The root node is not placed in the lcache and node->copy is not
2898  *       deallocated when lcache != NULL.
2899  */
2900 void
2901 hammer_btree_unlock_children(hammer_mount_t hmp, hammer_node_lock_t parent,
2902                              hammer_node_lock_t lcache)
2903 {
2904         hammer_node_lock_t item;
2905         hammer_node_ondisk_t copy;
2906
2907         while ((item = TAILQ_FIRST(&parent->list)) != NULL) {
2908                 TAILQ_REMOVE(&parent->list, item, entry);
2909                 hammer_btree_unlock_children(hmp, item, lcache);
2910                 hammer_unlock(&item->node->lock);
2911                 hammer_rel_node(item->node);
2912                 if (lcache) {
2913                         /*
2914                          * NOTE: When placing the item back in the lcache
2915                          *       the flag is cleared by the bzero().
2916                          *       Remaining fields are cleared as a safety
2917                          *       measure.
2918                          */
2919                         KKASSERT(item->flags & HAMMER_NODE_LOCK_LCACHE);
2920                         KKASSERT(TAILQ_EMPTY(&item->list));
2921                         copy = item->copy;
2922                         bzero(item, sizeof(*item));
2923                         TAILQ_INIT(&item->list);
2924                         item->copy = copy;
2925                         if (copy)
2926                                 bzero(copy, sizeof(*copy));
2927                         TAILQ_INSERT_TAIL(&lcache->list, item, entry);
2928                 } else {
2929                         kfree(item, hmp->m_misc);
2930                 }
2931         }
2932         if (parent->copy && (parent->flags & HAMMER_NODE_LOCK_LCACHE) == 0) {
2933                 kfree(parent->copy, hmp->m_misc);
2934                 parent->copy = NULL;    /* safety */
2935         }
2936 }
2937
2938 /************************************************************************
2939  *                         MISCELLANIOUS SUPPORT                        *
2940  ************************************************************************/
2941
2942 /*
2943  * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
2944  *
2945  * Note that for this particular function a return value of -1, 0, or +1
2946  * can denote a match if create_tid is otherwise discounted.  A create_tid
2947  * of zero is considered to be 'infinity' in comparisons.
2948  *
2949  * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
2950  */
2951 int
2952 hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
2953 {
2954         if (key1->localization < key2->localization)
2955                 return(-5);
2956         if (key1->localization > key2->localization)
2957                 return(5);
2958
2959         if (key1->obj_id < key2->obj_id)
2960                 return(-4);
2961         if (key1->obj_id > key2->obj_id)
2962                 return(4);
2963
2964         if (key1->rec_type < key2->rec_type)
2965                 return(-3);
2966         if (key1->rec_type > key2->rec_type)
2967                 return(3);
2968
2969         if (key1->key < key2->key)
2970                 return(-2);
2971         if (key1->key > key2->key)
2972                 return(2);
2973
2974         /*
2975          * A create_tid of zero indicates a record which is undeletable
2976          * and must be considered to have a value of positive infinity.
2977          */
2978         if (key1->create_tid == 0) {
2979                 if (key2->create_tid == 0)
2980                         return(0);
2981                 return(1);
2982         }
2983         if (key2->create_tid == 0)
2984                 return(-1);
2985         if (key1->create_tid < key2->create_tid)
2986                 return(-1);
2987         if (key1->create_tid > key2->create_tid)
2988                 return(1);
2989         return(0);
2990 }
2991
2992 /*
2993  * Test a timestamp against an element to determine whether the
2994  * element is visible.  A timestamp of 0 means 'infinity'.
2995  */
2996 int
2997 hammer_btree_chkts(hammer_tid_t asof, hammer_base_elm_t base)
2998 {
2999         if (asof == 0) {
3000                 if (base->delete_tid)
3001                         return(1);
3002                 return(0);
3003         }
3004         if (asof < base->create_tid)
3005                 return(-1);
3006         if (base->delete_tid && asof >= base->delete_tid)
3007                 return(1);
3008         return(0);
3009 }
3010
3011 /*
3012  * Create a separator half way inbetween key1 and key2.  For fields just
3013  * one unit apart, the separator will match key2.  key1 is on the left-hand
3014  * side and key2 is on the right-hand side.
3015  *
3016  * key2 must be >= the separator.  It is ok for the separator to match key2.
3017  *
3018  * NOTE: Even if key1 does not match key2, the separator may wind up matching
3019  * key2.
3020  *
3021  * NOTE: It might be beneficial to just scrap this whole mess and just
3022  * set the separator to key2.
3023  */
3024 #define MAKE_SEPARATOR(key1, key2, dest, field) \
3025         dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
3026
3027 static void
3028 hammer_make_separator(hammer_base_elm_t key1, hammer_base_elm_t key2,
3029                       hammer_base_elm_t dest)
3030 {
3031         bzero(dest, sizeof(*dest));
3032
3033         dest->rec_type = key2->rec_type;
3034         dest->key = key2->key;
3035         dest->obj_id = key2->obj_id;
3036         dest->create_tid = key2->create_tid;
3037
3038         MAKE_SEPARATOR(key1, key2, dest, localization);
3039         if (key1->localization == key2->localization) {
3040                 MAKE_SEPARATOR(key1, key2, dest, obj_id);
3041                 if (key1->obj_id == key2->obj_id) {
3042                         MAKE_SEPARATOR(key1, key2, dest, rec_type);
3043                         if (key1->rec_type == key2->rec_type) {
3044                                 MAKE_SEPARATOR(key1, key2, dest, key);
3045                                 /*
3046                                  * Don't bother creating a separator for
3047                                  * create_tid, which also conveniently avoids
3048                                  * having to handle the create_tid == 0
3049                                  * (infinity) case.  Just leave create_tid
3050                                  * set to key2.
3051                                  *
3052                                  * Worst case, dest matches key2 exactly,
3053                                  * which is acceptable.
3054                                  */
3055                         }
3056                 }
3057         }
3058 }
3059
3060 #undef MAKE_SEPARATOR
3061
3062 /*
3063  * Return whether a generic internal or leaf node is full
3064  */
3065 static int
3066 btree_node_is_full(hammer_node_ondisk_t node)
3067 {
3068         switch(node->type) {
3069         case HAMMER_BTREE_TYPE_INTERNAL:
3070                 if (node->count == HAMMER_BTREE_INT_ELMS)
3071                         return(1);
3072                 break;
3073         case HAMMER_BTREE_TYPE_LEAF:
3074                 if (node->count == HAMMER_BTREE_LEAF_ELMS)
3075                         return(1);
3076                 break;
3077         default:
3078                 panic("illegal btree subtype");
3079         }
3080         return(0);
3081 }
3082
3083 #if 0
3084 static int
3085 btree_max_elements(u_int8_t type)
3086 {
3087         if (type == HAMMER_BTREE_TYPE_LEAF)
3088                 return(HAMMER_BTREE_LEAF_ELMS);
3089         if (type == HAMMER_BTREE_TYPE_INTERNAL)
3090                 return(HAMMER_BTREE_INT_ELMS);
3091         panic("btree_max_elements: bad type %d\n", type);
3092 }
3093 #endif
3094
3095 void
3096 hammer_print_btree_node(hammer_node_ondisk_t ondisk)
3097 {
3098         hammer_btree_elm_t elm;
3099         int i;
3100
3101         kprintf("node %p count=%d parent=%016llx type=%c\n",
3102                 ondisk, ondisk->count,
3103                 (long long)ondisk->parent, ondisk->type);
3104
3105         /*
3106          * Dump both boundary elements if an internal node
3107          */
3108         if (ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
3109                 for (i = 0; i <= ondisk->count; ++i) {
3110                         elm = &ondisk->elms[i];
3111                         hammer_print_btree_elm(elm, ondisk->type, i);
3112                 }
3113         } else {
3114                 for (i = 0; i < ondisk->count; ++i) {
3115                         elm = &ondisk->elms[i];
3116                         hammer_print_btree_elm(elm, ondisk->type, i);
3117                 }
3118         }
3119 }
3120
3121 void
3122 hammer_print_btree_elm(hammer_btree_elm_t elm, u_int8_t type, int i)
3123 {
3124         kprintf("  %2d", i);
3125         kprintf("\tobj_id       = %016llx\n", (long long)elm->base.obj_id);
3126         kprintf("\tkey          = %016llx\n", (long long)elm->base.key);
3127         kprintf("\tcreate_tid   = %016llx\n", (long long)elm->base.create_tid);
3128         kprintf("\tdelete_tid   = %016llx\n", (long long)elm->base.delete_tid);
3129         kprintf("\trec_type     = %04x\n", elm->base.rec_type);
3130         kprintf("\tobj_type     = %02x\n", elm->base.obj_type);
3131         kprintf("\tbtype        = %02x (%c)\n",
3132                 elm->base.btype,
3133                 (elm->base.btype ? elm->base.btype : '?'));
3134         kprintf("\tlocalization = %02x\n", elm->base.localization);
3135
3136         switch(type) {
3137         case HAMMER_BTREE_TYPE_INTERNAL:
3138                 kprintf("\tsubtree_off  = %016llx\n",
3139                         (long long)elm->internal.subtree_offset);
3140                 break;
3141         case HAMMER_BTREE_TYPE_RECORD:
3142                 kprintf("\tdata_offset  = %016llx\n",
3143                         (long long)elm->leaf.data_offset);
3144                 kprintf("\tdata_len     = %08x\n", elm->leaf.data_len);
3145                 kprintf("\tdata_crc     = %08x\n", elm->leaf.data_crc);
3146                 break;
3147         }
3148 }