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, 0, &error);
1580                 if (parent == NULL)
1581                         goto done;
1582                 hammer_lock_ex(&parent->lock);
1583                 hammer_modify_node_noundo(cursor->trans, parent);
1584                 ondisk = parent->ondisk;
1585                 ondisk->count = 1;
1586                 ondisk->parent = 0;
1587                 ondisk->mirror_tid = node->ondisk->mirror_tid;
1588                 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1589                 ondisk->elms[0].base = hmp->root_btree_beg;
1590                 ondisk->elms[0].base.btype = node->ondisk->type;
1591                 ondisk->elms[0].internal.subtree_offset = node->node_offset;
1592                 ondisk->elms[1].base = hmp->root_btree_end;
1593                 hammer_modify_node_done(parent);
1594                 /* ondisk->elms[1].base.btype - not used */
1595                 made_root = 1;
1596                 parent_index = 0;       /* index of current node in parent */
1597         } else {
1598                 made_root = 0;
1599                 parent = cursor->parent;
1600                 parent_index = cursor->parent_index;
1601         }
1602
1603         /*
1604          * Calculate a hint for the allocation of the new B-Tree node.
1605          * The most likely expansion is coming from the insertion point
1606          * at cursor->index, so try to localize the allocation of our
1607          * new node to accomodate that sub-tree.
1608          *
1609          * Use the right-most sub-tree when expandinging on the right edge.
1610          * This is a very common case when copying a directory tree.
1611          */
1612         if (cursor->index == ondisk->count)
1613                 hint = ondisk->elms[cursor->index - 1].internal.subtree_offset;
1614         else
1615                 hint = ondisk->elms[cursor->index].internal.subtree_offset;
1616
1617         /*
1618          * Split node into new_node at the split point.
1619          *
1620          *  B O O O P N N B     <-- P = node->elms[split] (index 4)
1621          *   0 1 2 3 4 5 6      <-- subtree indices
1622          *
1623          *       x x P x x
1624          *        s S S s
1625          *         /   \
1626          *  B O O O B    B N N B        <--- inner boundary points are 'P'
1627          *   0 1 2 3      4 5 6
1628          */
1629         new_node = hammer_alloc_btree(cursor->trans, 0, &error);
1630         if (new_node == NULL) {
1631                 if (made_root) {
1632                         hammer_unlock(&parent->lock);
1633                         hammer_delete_node(cursor->trans, parent);
1634                         hammer_rel_node(parent);
1635                 }
1636                 goto done;
1637         }
1638         hammer_lock_ex(&new_node->lock);
1639
1640         /*
1641          * Create the new node.  P becomes the left-hand boundary in the
1642          * new node.  Copy the right-hand boundary as well.
1643          *
1644          * elm is the new separator.
1645          */
1646         hammer_modify_node_noundo(cursor->trans, new_node);
1647         hammer_modify_node_all(cursor->trans, node);
1648         ondisk = node->ondisk;
1649         elm = &ondisk->elms[split];
1650         bcopy(elm, &new_node->ondisk->elms[0],
1651               (ondisk->count - split + 1) * esize);
1652         new_node->ondisk->count = ondisk->count - split;
1653         new_node->ondisk->parent = parent->node_offset;
1654         new_node->ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1655         new_node->ondisk->mirror_tid = ondisk->mirror_tid;
1656         KKASSERT(ondisk->type == new_node->ondisk->type);
1657         hammer_cursor_split_node(node, new_node, split);
1658
1659         /*
1660          * Cleanup the original node.  Elm (P) becomes the new boundary,
1661          * its subtree_offset was moved to the new node.  If we had created
1662          * a new root its parent pointer may have changed.
1663          */
1664         elm->internal.subtree_offset = 0;
1665         ondisk->count = split;
1666
1667         /*
1668          * Insert the separator into the parent, fixup the parent's
1669          * reference to the original node, and reference the new node.
1670          * The separator is P.
1671          *
1672          * Remember that base.count does not include the right-hand boundary.
1673          */
1674         hammer_modify_node_all(cursor->trans, parent);
1675         ondisk = parent->ondisk;
1676         KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
1677         parent_elm = &ondisk->elms[parent_index+1];
1678         bcopy(parent_elm, parent_elm + 1,
1679               (ondisk->count - parent_index) * esize);
1680         parent_elm->internal.base = elm->base;  /* separator P */
1681         parent_elm->internal.base.btype = new_node->ondisk->type;
1682         parent_elm->internal.subtree_offset = new_node->node_offset;
1683         parent_elm->internal.mirror_tid = new_node->ondisk->mirror_tid;
1684         ++ondisk->count;
1685         hammer_modify_node_done(parent);
1686         hammer_cursor_inserted_element(parent, parent_index + 1);
1687
1688         /*
1689          * The children of new_node need their parent pointer set to new_node.
1690          * The children have already been locked by
1691          * hammer_btree_lock_children().
1692          */
1693         for (i = 0; i < new_node->ondisk->count; ++i) {
1694                 elm = &new_node->ondisk->elms[i];
1695                 error = btree_set_parent(cursor->trans, new_node, elm);
1696                 if (error) {
1697                         panic("btree_split_internal: btree-fixup problem");
1698                 }
1699         }
1700         hammer_modify_node_done(new_node);
1701
1702         /*
1703          * The filesystem's root B-Tree pointer may have to be updated.
1704          */
1705         if (made_root) {
1706                 hammer_volume_t volume;
1707
1708                 volume = hammer_get_root_volume(hmp, &error);
1709                 KKASSERT(error == 0);
1710
1711                 hammer_modify_volume_field(cursor->trans, volume,
1712                                            vol0_btree_root);
1713                 volume->ondisk->vol0_btree_root = parent->node_offset;
1714                 hammer_modify_volume_done(volume);
1715                 node->ondisk->parent = parent->node_offset;
1716                 if (cursor->parent) {
1717                         hammer_unlock(&cursor->parent->lock);
1718                         hammer_rel_node(cursor->parent);
1719                 }
1720                 cursor->parent = parent;        /* lock'd and ref'd */
1721                 hammer_rel_volume(volume, 0);
1722         }
1723         hammer_modify_node_done(node);
1724
1725         /*
1726          * Ok, now adjust the cursor depending on which element the original
1727          * index was pointing at.  If we are >= the split point the push node
1728          * is now in the new node.
1729          *
1730          * NOTE: If we are at the split point itself we cannot stay with the
1731          * original node because the push index will point at the right-hand
1732          * boundary, which is illegal.
1733          *
1734          * NOTE: The cursor's parent or parent_index must be adjusted for
1735          * the case where a new parent (new root) was created, and the case
1736          * where the cursor is now pointing at the split node.
1737          */
1738         if (cursor->index >= split) {
1739                 cursor->parent_index = parent_index + 1;
1740                 cursor->index -= split;
1741                 hammer_unlock(&cursor->node->lock);
1742                 hammer_rel_node(cursor->node);
1743                 cursor->node = new_node;        /* locked and ref'd */
1744         } else {
1745                 cursor->parent_index = parent_index;
1746                 hammer_unlock(&new_node->lock);
1747                 hammer_rel_node(new_node);
1748         }
1749
1750         /*
1751          * Fixup left and right bounds
1752          */
1753         parent_elm = &parent->ondisk->elms[cursor->parent_index];
1754         cursor->left_bound = &parent_elm[0].internal.base;
1755         cursor->right_bound = &parent_elm[1].internal.base;
1756         KKASSERT(hammer_btree_cmp(cursor->left_bound,
1757                  &cursor->node->ondisk->elms[0].internal.base) <= 0);
1758         KKASSERT(hammer_btree_cmp(cursor->right_bound,
1759                  &cursor->node->ondisk->elms[cursor->node->ondisk->count].internal.base) >= 0);
1760
1761 done:
1762         hammer_btree_unlock_children(cursor->trans->hmp, &lockroot, NULL);
1763         hammer_cursor_downgrade(cursor);
1764         return (error);
1765 }
1766
1767 /*
1768  * Same as the above, but splits a full leaf node.
1769  *
1770  * This function
1771  */
1772 static
1773 int
1774 btree_split_leaf(hammer_cursor_t cursor)
1775 {
1776         hammer_node_ondisk_t ondisk;
1777         hammer_node_t parent;
1778         hammer_node_t leaf;
1779         hammer_mount_t hmp;
1780         hammer_node_t new_leaf;
1781         hammer_btree_elm_t elm;
1782         hammer_btree_elm_t parent_elm;
1783         hammer_base_elm_t mid_boundary;
1784         hammer_off_t hint;
1785         int parent_index;
1786         int made_root;
1787         int split;
1788         int error;
1789         const size_t esize = sizeof(*elm);
1790
1791         if ((error = hammer_cursor_upgrade(cursor)) != 0)
1792                 return(error);
1793         ++hammer_stats_btree_splits;
1794
1795         KKASSERT(hammer_btree_cmp(cursor->left_bound,
1796                  &cursor->node->ondisk->elms[0].leaf.base) <= 0);
1797         KKASSERT(hammer_btree_cmp(cursor->right_bound,
1798                  &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
1799
1800         /*
1801          * Calculate the split point.  If the insertion point is at the
1802          * end of the leaf we adjust the split point significantly to the
1803          * right to try to optimize node fill and flag it.  If we hit
1804          * that same leaf again our heuristic failed and we don't try
1805          * to optimize node fill (it could lead to a degenerate case).
1806          *
1807          * Spikes are made up of two leaf elements which cannot be
1808          * safely split.
1809          */
1810         leaf = cursor->node;
1811         ondisk = leaf->ondisk;
1812         KKASSERT(ondisk->count > 4);
1813         if (cursor->index == ondisk->count &&
1814             (leaf->flags & HAMMER_NODE_NONLINEAR) == 0) {
1815                 split = (ondisk->count + 1) * 3 / 4;
1816                 leaf->flags |= HAMMER_NODE_NONLINEAR;
1817         } else {
1818                 split = (ondisk->count + 1) / 2;
1819         }
1820
1821 #if 0
1822         /*
1823          * If the insertion point is at the split point shift the
1824          * split point left so we don't have to worry about
1825          */
1826         if (cursor->index == split)
1827                 --split;
1828 #endif
1829         KKASSERT(split > 0 && split < ondisk->count);
1830
1831         error = 0;
1832         hmp = leaf->hmp;
1833
1834         elm = &ondisk->elms[split];
1835
1836         KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm[-1].leaf.base) <= 0);
1837         KKASSERT(hammer_btree_cmp(cursor->left_bound, &elm->leaf.base) <= 0);
1838         KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm->leaf.base) > 0);
1839         KKASSERT(hammer_btree_cmp(cursor->right_bound, &elm[1].leaf.base) > 0);
1840
1841         /*
1842          * If we are at the root of the tree, create a new root node with
1843          * 1 element and split normally.  Avoid making major modifications
1844          * until we know the whole operation will work.
1845          */
1846         if (ondisk->parent == 0) {
1847                 parent = hammer_alloc_btree(cursor->trans, 0, &error);
1848                 if (parent == NULL)
1849                         goto done;
1850                 hammer_lock_ex(&parent->lock);
1851                 hammer_modify_node_noundo(cursor->trans, parent);
1852                 ondisk = parent->ondisk;
1853                 ondisk->count = 1;
1854                 ondisk->parent = 0;
1855                 ondisk->mirror_tid = leaf->ondisk->mirror_tid;
1856                 ondisk->type = HAMMER_BTREE_TYPE_INTERNAL;
1857                 ondisk->elms[0].base = hmp->root_btree_beg;
1858                 ondisk->elms[0].base.btype = leaf->ondisk->type;
1859                 ondisk->elms[0].internal.subtree_offset = leaf->node_offset;
1860                 ondisk->elms[1].base = hmp->root_btree_end;
1861                 /* ondisk->elms[1].base.btype = not used */
1862                 hammer_modify_node_done(parent);
1863                 made_root = 1;
1864                 parent_index = 0;       /* insertion point in parent */
1865         } else {
1866                 made_root = 0;
1867                 parent = cursor->parent;
1868                 parent_index = cursor->parent_index;
1869         }
1870
1871         /*
1872          * Calculate a hint for the allocation of the new B-Tree leaf node.
1873          * For now just try to localize it within the same bigblock as
1874          * the current leaf.
1875          *
1876          * If the insertion point is at the end of the leaf we recognize a
1877          * likely append sequence of some sort (data, meta-data, inodes,
1878          * whatever).  Set the hint to zero to allocate out of linear space
1879          * instead of trying to completely fill previously hinted space.
1880          *
1881          * This also sets the stage for recursive splits to localize using
1882          * the new space.
1883          */
1884         ondisk = leaf->ondisk;
1885         if (cursor->index == ondisk->count)
1886                 hint = 0;
1887         else
1888                 hint = leaf->node_offset;
1889
1890         /*
1891          * Split leaf into new_leaf at the split point.  Select a separator
1892          * value in-between the two leafs but with a bent towards the right
1893          * leaf since comparisons use an 'elm >= separator' inequality.
1894          *
1895          *  L L L L L L L L
1896          *
1897          *       x x P x x
1898          *        s S S s
1899          *         /   \
1900          *  L L L L     L L L L
1901          */
1902         new_leaf = hammer_alloc_btree(cursor->trans, 0, &error);
1903         if (new_leaf == NULL) {
1904                 if (made_root) {
1905                         hammer_unlock(&parent->lock);
1906                         hammer_delete_node(cursor->trans, parent);
1907                         hammer_rel_node(parent);
1908                 }
1909                 goto done;
1910         }
1911         hammer_lock_ex(&new_leaf->lock);
1912
1913         /*
1914          * Create the new node and copy the leaf elements from the split
1915          * point on to the new node.
1916          */
1917         hammer_modify_node_all(cursor->trans, leaf);
1918         hammer_modify_node_noundo(cursor->trans, new_leaf);
1919         ondisk = leaf->ondisk;
1920         elm = &ondisk->elms[split];
1921         bcopy(elm, &new_leaf->ondisk->elms[0], (ondisk->count - split) * esize);
1922         new_leaf->ondisk->count = ondisk->count - split;
1923         new_leaf->ondisk->parent = parent->node_offset;
1924         new_leaf->ondisk->type = HAMMER_BTREE_TYPE_LEAF;
1925         new_leaf->ondisk->mirror_tid = ondisk->mirror_tid;
1926         KKASSERT(ondisk->type == new_leaf->ondisk->type);
1927         hammer_modify_node_done(new_leaf);
1928         hammer_cursor_split_node(leaf, new_leaf, split);
1929
1930         /*
1931          * Cleanup the original node.  Because this is a leaf node and
1932          * leaf nodes do not have a right-hand boundary, there
1933          * aren't any special edge cases to clean up.  We just fixup the
1934          * count.
1935          */
1936         ondisk->count = split;
1937
1938         /*
1939          * Insert the separator into the parent, fixup the parent's
1940          * reference to the original node, and reference the new node.
1941          * The separator is P.
1942          *
1943          * Remember that base.count does not include the right-hand boundary.
1944          * We are copying parent_index+1 to parent_index+2, not +0 to +1.
1945          */
1946         hammer_modify_node_all(cursor->trans, parent);
1947         ondisk = parent->ondisk;
1948         KKASSERT(split != 0);
1949         KKASSERT(ondisk->count != HAMMER_BTREE_INT_ELMS);
1950         parent_elm = &ondisk->elms[parent_index+1];
1951         bcopy(parent_elm, parent_elm + 1,
1952               (ondisk->count - parent_index) * esize);
1953
1954         hammer_make_separator(&elm[-1].base, &elm[0].base, &parent_elm->base);
1955         parent_elm->internal.base.btype = new_leaf->ondisk->type;
1956         parent_elm->internal.subtree_offset = new_leaf->node_offset;
1957         parent_elm->internal.mirror_tid = new_leaf->ondisk->mirror_tid;
1958         mid_boundary = &parent_elm->base;
1959         ++ondisk->count;
1960         hammer_modify_node_done(parent);
1961         hammer_cursor_inserted_element(parent, parent_index + 1);
1962
1963         /*
1964          * The filesystem's root B-Tree pointer may have to be updated.
1965          */
1966         if (made_root) {
1967                 hammer_volume_t volume;
1968
1969                 volume = hammer_get_root_volume(hmp, &error);
1970                 KKASSERT(error == 0);
1971
1972                 hammer_modify_volume_field(cursor->trans, volume,
1973                                            vol0_btree_root);
1974                 volume->ondisk->vol0_btree_root = parent->node_offset;
1975                 hammer_modify_volume_done(volume);
1976                 leaf->ondisk->parent = parent->node_offset;
1977                 if (cursor->parent) {
1978                         hammer_unlock(&cursor->parent->lock);
1979                         hammer_rel_node(cursor->parent);
1980                 }
1981                 cursor->parent = parent;        /* lock'd and ref'd */
1982                 hammer_rel_volume(volume, 0);
1983         }
1984         hammer_modify_node_done(leaf);
1985
1986         /*
1987          * Ok, now adjust the cursor depending on which element the original
1988          * index was pointing at.  If we are >= the split point the push node
1989          * is now in the new node.
1990          *
1991          * NOTE: If we are at the split point itself we need to select the
1992          * old or new node based on where key_beg's insertion point will be.
1993          * If we pick the wrong side the inserted element will wind up in
1994          * the wrong leaf node and outside that node's bounds.
1995          */
1996         if (cursor->index > split ||
1997             (cursor->index == split &&
1998              hammer_btree_cmp(&cursor->key_beg, mid_boundary) >= 0)) {
1999                 cursor->parent_index = parent_index + 1;
2000                 cursor->index -= split;
2001                 hammer_unlock(&cursor->node->lock);
2002                 hammer_rel_node(cursor->node);
2003                 cursor->node = new_leaf;
2004         } else {
2005                 cursor->parent_index = parent_index;
2006                 hammer_unlock(&new_leaf->lock);
2007                 hammer_rel_node(new_leaf);
2008         }
2009
2010         /*
2011          * Fixup left and right bounds
2012          */
2013         parent_elm = &parent->ondisk->elms[cursor->parent_index];
2014         cursor->left_bound = &parent_elm[0].internal.base;
2015         cursor->right_bound = &parent_elm[1].internal.base;
2016
2017         /*
2018          * Assert that the bounds are correct.
2019          */
2020         KKASSERT(hammer_btree_cmp(cursor->left_bound,
2021                  &cursor->node->ondisk->elms[0].leaf.base) <= 0);
2022         KKASSERT(hammer_btree_cmp(cursor->right_bound,
2023                  &cursor->node->ondisk->elms[cursor->node->ondisk->count-1].leaf.base) > 0);
2024         KKASSERT(hammer_btree_cmp(cursor->left_bound, &cursor->key_beg) <= 0);
2025         KKASSERT(hammer_btree_cmp(cursor->right_bound, &cursor->key_beg) > 0);
2026
2027 done:
2028         hammer_cursor_downgrade(cursor);
2029         return (error);
2030 }
2031
2032 #if 0
2033
2034 /*
2035  * Recursively correct the right-hand boundary's create_tid to (tid) as
2036  * long as the rest of the key matches.  We have to recurse upward in
2037  * the tree as well as down the left side of each parent's right node.
2038  *
2039  * Return EDEADLK if we were only partially successful, forcing the caller
2040  * to try again.  The original cursor is not modified.  This routine can
2041  * also fail with EDEADLK if it is forced to throw away a portion of its
2042  * record history.
2043  *
2044  * The caller must pass a downgraded cursor to us (otherwise we can't dup it).
2045  */
2046 struct hammer_rhb {
2047         TAILQ_ENTRY(hammer_rhb) entry;
2048         hammer_node_t   node;
2049         int             index;
2050 };
2051
2052 TAILQ_HEAD(hammer_rhb_list, hammer_rhb);
2053
2054 int
2055 hammer_btree_correct_rhb(hammer_cursor_t cursor, hammer_tid_t tid)
2056 {
2057         struct hammer_mount *hmp;
2058         struct hammer_rhb_list rhb_list;
2059         hammer_base_elm_t elm;
2060         hammer_node_t orig_node;
2061         struct hammer_rhb *rhb;
2062         int orig_index;
2063         int error;
2064
2065         TAILQ_INIT(&rhb_list);
2066         hmp = cursor->trans->hmp;
2067
2068         /*
2069          * Save our position so we can restore it on return.  This also
2070          * gives us a stable 'elm'.
2071          */
2072         orig_node = cursor->node;
2073         hammer_ref_node(orig_node);
2074         hammer_lock_sh(&orig_node->lock);
2075         orig_index = cursor->index;
2076         elm = &orig_node->ondisk->elms[orig_index].base;
2077
2078         /*
2079          * Now build a list of parents going up, allocating a rhb
2080          * structure for each one.
2081          */
2082         while (cursor->parent) {
2083                 /*
2084                  * Stop if we no longer have any right-bounds to fix up
2085                  */
2086                 if (elm->obj_id != cursor->right_bound->obj_id ||
2087                     elm->rec_type != cursor->right_bound->rec_type ||
2088                     elm->key != cursor->right_bound->key) {
2089                         break;
2090                 }
2091
2092                 /*
2093                  * Stop if the right-hand bound's create_tid does not
2094                  * need to be corrected.
2095                  */
2096                 if (cursor->right_bound->create_tid >= tid)
2097                         break;
2098
2099                 rhb = kmalloc(sizeof(*rhb), hmp->m_misc, M_WAITOK|M_ZERO);
2100                 rhb->node = cursor->parent;
2101                 rhb->index = cursor->parent_index;
2102                 hammer_ref_node(rhb->node);
2103                 hammer_lock_sh(&rhb->node->lock);
2104                 TAILQ_INSERT_HEAD(&rhb_list, rhb, entry);
2105
2106                 hammer_cursor_up(cursor);
2107         }
2108
2109         /*
2110          * now safely adjust the right hand bound for each rhb.  This may
2111          * also require taking the right side of the tree and iterating down
2112          * ITS left side.
2113          */
2114         error = 0;
2115         while (error == 0 && (rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2116                 error = hammer_cursor_seek(cursor, rhb->node, rhb->index);
2117                 if (error)
2118                         break;
2119                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2120                 hammer_unlock(&rhb->node->lock);
2121                 hammer_rel_node(rhb->node);
2122                 kfree(rhb, hmp->m_misc);
2123
2124                 switch (cursor->node->ondisk->type) {
2125                 case HAMMER_BTREE_TYPE_INTERNAL:
2126                         /*
2127                          * Right-boundary for parent at internal node
2128                          * is one element to the right of the element whos
2129                          * right boundary needs adjusting.  We must then
2130                          * traverse down the left side correcting any left
2131                          * bounds (which may now be too far to the left).
2132                          */
2133                         ++cursor->index;
2134                         error = hammer_btree_correct_lhb(cursor, tid);
2135                         break;
2136                 default:
2137                         panic("hammer_btree_correct_rhb(): Bad node type");
2138                         error = EINVAL;
2139                         break;
2140                 }
2141         }
2142
2143         /*
2144          * Cleanup
2145          */
2146         while ((rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2147                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2148                 hammer_unlock(&rhb->node->lock);
2149                 hammer_rel_node(rhb->node);
2150                 kfree(rhb, hmp->m_misc);
2151         }
2152         error = hammer_cursor_seek(cursor, orig_node, orig_index);
2153         hammer_unlock(&orig_node->lock);
2154         hammer_rel_node(orig_node);
2155         return (error);
2156 }
2157
2158 /*
2159  * Similar to rhb (in fact, rhb calls lhb), but corrects the left hand
2160  * bound going downward starting at the current cursor position.
2161  *
2162  * This function does not restore the cursor after use.
2163  */
2164 int
2165 hammer_btree_correct_lhb(hammer_cursor_t cursor, hammer_tid_t tid)
2166 {
2167         struct hammer_rhb_list rhb_list;
2168         hammer_base_elm_t elm;
2169         hammer_base_elm_t cmp;
2170         struct hammer_rhb *rhb;
2171         struct hammer_mount *hmp;
2172         int error;
2173
2174         TAILQ_INIT(&rhb_list);
2175         hmp = cursor->trans->hmp;
2176
2177         cmp = &cursor->node->ondisk->elms[cursor->index].base;
2178
2179         /*
2180          * Record the node and traverse down the left-hand side for all
2181          * matching records needing a boundary correction.
2182          */
2183         error = 0;
2184         for (;;) {
2185                 rhb = kmalloc(sizeof(*rhb), hmp->m_misc, M_WAITOK|M_ZERO);
2186                 rhb->node = cursor->node;
2187                 rhb->index = cursor->index;
2188                 hammer_ref_node(rhb->node);
2189                 hammer_lock_sh(&rhb->node->lock);
2190                 TAILQ_INSERT_HEAD(&rhb_list, rhb, entry);
2191
2192                 if (cursor->node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
2193                         /*
2194                          * Nothing to traverse down if we are at the right
2195                          * boundary of an internal node.
2196                          */
2197                         if (cursor->index == cursor->node->ondisk->count)
2198                                 break;
2199                 } else {
2200                         elm = &cursor->node->ondisk->elms[cursor->index].base;
2201                         if (elm->btype == HAMMER_BTREE_TYPE_RECORD)
2202                                 break;
2203                         panic("Illegal leaf record type %02x", elm->btype);
2204                 }
2205                 error = hammer_cursor_down(cursor);
2206                 if (error)
2207                         break;
2208
2209                 elm = &cursor->node->ondisk->elms[cursor->index].base;
2210                 if (elm->obj_id != cmp->obj_id ||
2211                     elm->rec_type != cmp->rec_type ||
2212                     elm->key != cmp->key) {
2213                         break;
2214                 }
2215                 if (elm->create_tid >= tid)
2216                         break;
2217
2218         }
2219
2220         /*
2221          * Now we can safely adjust the left-hand boundary from the bottom-up.
2222          * The last element we remove from the list is the caller's right hand
2223          * boundary, which must also be adjusted.
2224          */
2225         while (error == 0 && (rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2226                 error = hammer_cursor_seek(cursor, rhb->node, rhb->index);
2227                 if (error)
2228                         break;
2229                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2230                 hammer_unlock(&rhb->node->lock);
2231                 hammer_rel_node(rhb->node);
2232                 kfree(rhb, hmp->m_misc);
2233
2234                 elm = &cursor->node->ondisk->elms[cursor->index].base;
2235                 if (cursor->node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
2236                         hammer_modify_node(cursor->trans, cursor->node,
2237                                            &elm->create_tid,
2238                                            sizeof(elm->create_tid));
2239                         elm->create_tid = tid;
2240                         hammer_modify_node_done(cursor->node);
2241                 } else {
2242                         panic("hammer_btree_correct_lhb(): Bad element type");
2243                 }
2244         }
2245
2246         /*
2247          * Cleanup
2248          */
2249         while ((rhb = TAILQ_FIRST(&rhb_list)) != NULL) {
2250                 TAILQ_REMOVE(&rhb_list, rhb, entry);
2251                 hammer_unlock(&rhb->node->lock);
2252                 hammer_rel_node(rhb->node);
2253                 kfree(rhb, hmp->m_misc);
2254         }
2255         return (error);
2256 }
2257
2258 #endif
2259
2260 /*
2261  * Attempt to remove the locked, empty or want-to-be-empty B-Tree node at
2262  * (cursor->node).  Returns 0 on success, EDEADLK if we could not complete
2263  * the operation due to a deadlock, or some other error.
2264  *
2265  * This routine is initially called with an empty leaf and may be
2266  * recursively called with single-element internal nodes.
2267  *
2268  * It should also be noted that when removing empty leaves we must be sure
2269  * to test and update mirror_tid because another thread may have deadlocked
2270  * against us (or someone) trying to propagate it up and cannot retry once
2271  * the node has been deleted.
2272  *
2273  * On return the cursor may end up pointing to an internal node, suitable
2274  * for further iteration but not for an immediate insertion or deletion.
2275  */
2276 static int
2277 btree_remove(hammer_cursor_t cursor)
2278 {
2279         hammer_node_ondisk_t ondisk;
2280         hammer_btree_elm_t elm;
2281         hammer_node_t node;
2282         hammer_node_t parent;
2283         const int esize = sizeof(*elm);
2284         int error;
2285
2286         node = cursor->node;
2287
2288         /*
2289          * When deleting the root of the filesystem convert it to
2290          * an empty leaf node.  Internal nodes cannot be empty.
2291          */
2292         ondisk = node->ondisk;
2293         if (ondisk->parent == 0) {
2294                 KKASSERT(cursor->parent == NULL);
2295                 hammer_modify_node_all(cursor->trans, node);
2296                 KKASSERT(ondisk == node->ondisk);
2297                 ondisk->type = HAMMER_BTREE_TYPE_LEAF;
2298                 ondisk->count = 0;
2299                 hammer_modify_node_done(node);
2300                 cursor->index = 0;
2301                 return(0);
2302         }
2303
2304         parent = cursor->parent;
2305
2306         /*
2307          * Attempt to remove the parent's reference to the child.  If the
2308          * parent would become empty we have to recurse.  If we fail we
2309          * leave the parent pointing to an empty leaf node.
2310          *
2311          * We have to recurse successfully before we can delete the internal
2312          * node as it is illegal to have empty internal nodes.  Even though
2313          * the operation may be aborted we must still fixup any unlocked
2314          * cursors as if we had deleted the element prior to recursing
2315          * (by calling hammer_cursor_deleted_element()) so those cursors
2316          * are properly forced up the chain by the recursion.
2317          */
2318         if (parent->ondisk->count == 1) {
2319                 /*
2320                  * This special cursor_up_locked() call leaves the original
2321                  * node exclusively locked and referenced, leaves the
2322                  * original parent locked (as the new node), and locks the
2323                  * new parent.  It can return EDEADLK.
2324                  *
2325                  * We cannot call hammer_cursor_removed_node() until we are
2326                  * actually able to remove the node.  If we did then tracked
2327                  * cursors in the middle of iterations could be repointed
2328                  * to a parent node.  If this occurs they could end up
2329                  * scanning newly inserted records into the node (that could
2330                  * not be deleted) when they push down again.
2331                  *
2332                  * Due to the way the recursion works the final parent is left
2333                  * in cursor->parent after the recursion returns.  Each
2334                  * layer on the way back up is thus able to call
2335                  * hammer_cursor_removed_node() and 'jump' the node up to
2336                  * the (same) final parent.
2337                  *
2338                  * NOTE!  The local variable 'parent' is invalid after we
2339                  *        call hammer_cursor_up_locked().
2340                  */
2341                 error = hammer_cursor_up_locked(cursor);
2342                 parent = NULL;
2343
2344                 if (error == 0) {
2345                         hammer_cursor_deleted_element(cursor->node, 0);
2346                         error = btree_remove(cursor);
2347                         if (error == 0) {
2348                                 KKASSERT(node != cursor->node);
2349                                 hammer_cursor_removed_node(
2350                                         node, cursor->node,
2351                                         cursor->index);
2352                                 hammer_modify_node_all(cursor->trans, node);
2353                                 ondisk = node->ondisk;
2354                                 ondisk->type = HAMMER_BTREE_TYPE_DELETED;
2355                                 ondisk->count = 0;
2356                                 hammer_modify_node_done(node);
2357                                 hammer_flush_node(node, 0);
2358                                 hammer_delete_node(cursor->trans, node);
2359                         } else {
2360                                 /*
2361                                  * Defer parent removal because we could not
2362                                  * get the lock, just let the leaf remain
2363                                  * empty.
2364                                  */
2365                                 /**/
2366                         }
2367                         hammer_unlock(&node->lock);
2368                         hammer_rel_node(node);
2369                 } else {
2370                         /*
2371                          * Defer parent removal because we could not
2372                          * get the lock, just let the leaf remain
2373                          * empty.
2374                          */
2375                         /**/
2376                 }
2377         } else {
2378                 KKASSERT(parent->ondisk->count > 1);
2379
2380                 hammer_modify_node_all(cursor->trans, parent);
2381                 ondisk = parent->ondisk;
2382                 KKASSERT(ondisk->type == HAMMER_BTREE_TYPE_INTERNAL);
2383
2384                 elm = &ondisk->elms[cursor->parent_index];
2385                 KKASSERT(elm->internal.subtree_offset == node->node_offset);
2386                 KKASSERT(ondisk->count > 0);
2387
2388                 /*
2389                  * We must retain the highest mirror_tid.  The deleted
2390                  * range is now encompassed by the element to the left.
2391                  * If we are already at the left edge the new left edge
2392                  * inherits mirror_tid.
2393                  *
2394                  * Note that bounds of the parent to our parent may create
2395                  * a gap to the left of our left-most node or to the right
2396                  * of our right-most node.  The gap is silently included
2397                  * in the mirror_tid's area of effect from the point of view
2398                  * of the scan.
2399                  */
2400                 if (cursor->parent_index) {
2401                         if (elm[-1].internal.mirror_tid <
2402                             elm[0].internal.mirror_tid) {
2403                                 elm[-1].internal.mirror_tid =
2404                                     elm[0].internal.mirror_tid;
2405                         }
2406                 } else {
2407                         if (elm[1].internal.mirror_tid <
2408                             elm[0].internal.mirror_tid) {
2409                                 elm[1].internal.mirror_tid =
2410                                     elm[0].internal.mirror_tid;
2411                         }
2412                 }
2413
2414                 /*
2415                  * Delete the subtree reference in the parent.  Include
2416                  * boundary element at end.
2417                  */
2418                 bcopy(&elm[1], &elm[0],
2419                       (ondisk->count - cursor->parent_index) * esize);
2420                 --ondisk->count;
2421                 hammer_modify_node_done(parent);
2422                 hammer_cursor_removed_node(node, parent, cursor->parent_index);
2423                 hammer_cursor_deleted_element(parent, cursor->parent_index);
2424                 hammer_flush_node(node, 0);
2425                 hammer_delete_node(cursor->trans, node);
2426
2427                 /*
2428                  * cursor->node is invalid, cursor up to make the cursor
2429                  * valid again.  We have to flag the condition in case
2430                  * another thread wiggles an insertion in during an
2431                  * iteration.
2432                  */
2433                 cursor->flags |= HAMMER_CURSOR_ITERATE_CHECK;
2434                 error = hammer_cursor_up(cursor);
2435         }
2436         return (error);
2437 }
2438
2439 /*
2440  * Propagate cursor->trans->tid up the B-Tree starting at the current
2441  * cursor position using pseudofs info gleaned from the passed inode.
2442  *
2443  * The passed inode has no relationship to the cursor position other
2444  * then being in the same pseudofs as the insertion or deletion we
2445  * are propagating the mirror_tid for.
2446  *
2447  * WARNING!  Because we push and pop the passed cursor, it may be
2448  *           modified by other B-Tree operations while it is unlocked
2449  *           and things like the node & leaf pointers, and indexes might
2450  *           change.
2451  */
2452 void
2453 hammer_btree_do_propagation(hammer_cursor_t cursor,
2454                             hammer_pseudofs_inmem_t pfsm,
2455                             hammer_btree_leaf_elm_t leaf)
2456 {
2457         hammer_cursor_t ncursor;
2458         hammer_tid_t mirror_tid;
2459         int error;
2460
2461         /*
2462          * We do not propagate a mirror_tid if the filesystem was mounted
2463          * in no-mirror mode.
2464          */
2465         if (cursor->trans->hmp->master_id < 0)
2466                 return;
2467
2468         /*
2469          * This is a bit of a hack because we cannot deadlock or return
2470          * EDEADLK here.  The related operation has already completed and
2471          * we must propagate the mirror_tid now regardless.
2472          *
2473          * Generate a new cursor which inherits the original's locks and
2474          * unlock the original.  Use the new cursor to propagate the
2475          * mirror_tid.  Then clean up the new cursor and reacquire locks
2476          * on the original.
2477          *
2478          * hammer_dup_cursor() cannot dup locks.  The dup inherits the
2479          * original's locks and the original is tracked and must be
2480          * re-locked.
2481          */
2482         mirror_tid = cursor->node->ondisk->mirror_tid;
2483         KKASSERT(mirror_tid != 0);
2484         ncursor = hammer_push_cursor(cursor);
2485         error = hammer_btree_mirror_propagate(ncursor, mirror_tid);
2486         KKASSERT(error == 0);
2487         hammer_pop_cursor(cursor, ncursor);
2488         /* WARNING: cursor's leaf pointer may change after pop */
2489 }
2490
2491
2492 /*
2493  * Propagate a mirror TID update upwards through the B-Tree to the root.
2494  *
2495  * A locked internal node must be passed in.  The node will remain locked
2496  * on return.
2497  *
2498  * This function syncs mirror_tid at the specified internal node's element,
2499  * adjusts the node's aggregation mirror_tid, and then recurses upwards.
2500  */
2501 static int
2502 hammer_btree_mirror_propagate(hammer_cursor_t cursor, hammer_tid_t mirror_tid)
2503 {
2504         hammer_btree_internal_elm_t elm;
2505         hammer_node_t node;
2506         int error;
2507
2508         for (;;) {
2509                 error = hammer_cursor_up(cursor);
2510                 if (error == 0)
2511                         error = hammer_cursor_upgrade(cursor);
2512
2513                 /*
2514                  * We can ignore HAMMER_CURSOR_ITERATE_CHECK, the
2515                  * cursor will still be properly positioned for
2516                  * mirror propagation, just not for iterations.
2517                  */
2518                 while (error == EDEADLK) {
2519                         hammer_recover_cursor(cursor);
2520                         error = hammer_cursor_upgrade(cursor);
2521                 }
2522                 if (error)
2523                         break;
2524
2525                 /*
2526                  * If the cursor deadlocked it could end up at a leaf
2527                  * after we lost the lock.
2528                  */
2529                 node = cursor->node;
2530                 if (node->ondisk->type != HAMMER_BTREE_TYPE_INTERNAL)
2531                         continue;
2532
2533                 /*
2534                  * Adjust the node's element
2535                  */
2536                 elm = &node->ondisk->elms[cursor->index].internal;
2537                 if (elm->mirror_tid >= mirror_tid)
2538                         break;
2539                 hammer_modify_node(cursor->trans, node, &elm->mirror_tid,
2540                                    sizeof(elm->mirror_tid));
2541                 elm->mirror_tid = mirror_tid;
2542                 hammer_modify_node_done(node);
2543                 if (hammer_debug_general & 0x0002) {
2544                         kprintf("mirror_propagate: propagate "
2545                                 "%016llx @%016llx:%d\n",
2546                                 (long long)mirror_tid,
2547                                 (long long)node->node_offset,
2548                                 cursor->index);
2549                 }
2550
2551
2552                 /*
2553                  * Adjust the node's mirror_tid aggregator
2554                  */
2555                 if (node->ondisk->mirror_tid >= mirror_tid)
2556                         return(0);
2557                 hammer_modify_node_field(cursor->trans, node, mirror_tid);
2558                 node->ondisk->mirror_tid = mirror_tid;
2559                 hammer_modify_node_done(node);
2560                 if (hammer_debug_general & 0x0002) {
2561                         kprintf("mirror_propagate: propagate "
2562                                 "%016llx @%016llx\n",
2563                                 (long long)mirror_tid,
2564                                 (long long)node->node_offset);
2565                 }
2566         }
2567         if (error == ENOENT)
2568                 error = 0;
2569         return(error);
2570 }
2571
2572 hammer_node_t
2573 hammer_btree_get_parent(hammer_transaction_t trans, hammer_node_t node,
2574                         int *parent_indexp, int *errorp, int try_exclusive)
2575 {
2576         hammer_node_t parent;
2577         hammer_btree_elm_t elm;
2578         int i;
2579
2580         /*
2581          * Get the node
2582          */
2583         parent = hammer_get_node(trans, node->ondisk->parent, 0, errorp);
2584         if (*errorp) {
2585                 KKASSERT(parent == NULL);
2586                 return(NULL);
2587         }
2588         KKASSERT ((parent->flags & HAMMER_NODE_DELETED) == 0);
2589
2590         /*
2591          * Lock the node
2592          */
2593         if (try_exclusive) {
2594                 if (hammer_lock_ex_try(&parent->lock)) {
2595                         hammer_rel_node(parent);
2596                         *errorp = EDEADLK;
2597                         return(NULL);
2598                 }
2599         } else {
2600                 hammer_lock_sh(&parent->lock);
2601         }
2602
2603         /*
2604          * Figure out which element in the parent is pointing to the
2605          * child.
2606          */
2607         if (node->ondisk->count) {
2608                 i = hammer_btree_search_node(&node->ondisk->elms[0].base,
2609                                              parent->ondisk);
2610         } else {
2611                 i = 0;
2612         }
2613         while (i < parent->ondisk->count) {
2614                 elm = &parent->ondisk->elms[i];
2615                 if (elm->internal.subtree_offset == node->node_offset)
2616                         break;
2617                 ++i;
2618         }
2619         if (i == parent->ondisk->count) {
2620                 hammer_unlock(&parent->lock);
2621                 panic("Bad B-Tree link: parent %p node %p\n", parent, node);
2622         }
2623         *parent_indexp = i;
2624         KKASSERT(*errorp == 0);
2625         return(parent);
2626 }
2627
2628 /*
2629  * The element (elm) has been moved to a new internal node (node).
2630  *
2631  * If the element represents a pointer to an internal node that node's
2632  * parent must be adjusted to the element's new location.
2633  *
2634  * XXX deadlock potential here with our exclusive locks
2635  */
2636 int
2637 btree_set_parent(hammer_transaction_t trans, hammer_node_t node,
2638                  hammer_btree_elm_t elm)
2639 {
2640         hammer_node_t child;
2641         int error;
2642
2643         error = 0;
2644
2645         switch(elm->base.btype) {
2646         case HAMMER_BTREE_TYPE_INTERNAL:
2647         case HAMMER_BTREE_TYPE_LEAF:
2648                 child = hammer_get_node(trans, elm->internal.subtree_offset,
2649                                         0, &error);
2650                 if (error == 0) {
2651                         hammer_modify_node_field(trans, child, parent);
2652                         child->ondisk->parent = node->node_offset;
2653                         hammer_modify_node_done(child);
2654                         hammer_rel_node(child);
2655                 }
2656                 break;
2657         default:
2658                 break;
2659         }
2660         return(error);
2661 }
2662
2663 /*
2664  * Initialize the root of a recursive B-Tree node lock list structure.
2665  */
2666 void
2667 hammer_node_lock_init(hammer_node_lock_t parent, hammer_node_t node)
2668 {
2669         TAILQ_INIT(&parent->list);
2670         parent->parent = NULL;
2671         parent->node = node;
2672         parent->index = -1;
2673         parent->count = node->ondisk->count;
2674         parent->copy = NULL;
2675         parent->flags = 0;
2676 }
2677
2678 /*
2679  * Initialize a cache of hammer_node_lock's including space allocated
2680  * for node copies.
2681  *
2682  * This is used by the rebalancing code to preallocate the copy space
2683  * for ~4096 B-Tree nodes (16MB of data) prior to acquiring any HAMMER
2684  * locks, otherwise we can blow out the pageout daemon's emergency
2685  * reserve and deadlock it.
2686  *
2687  * NOTE: HAMMER_NODE_LOCK_LCACHE is not set on items cached in the lcache.
2688  *       The flag is set when the item is pulled off the cache for use.
2689  */
2690 void
2691 hammer_btree_lcache_init(hammer_mount_t hmp, hammer_node_lock_t lcache,
2692                          int depth)
2693 {
2694         hammer_node_lock_t item;
2695         int count;
2696
2697         for (count = 1; depth; --depth)
2698                 count *= HAMMER_BTREE_LEAF_ELMS;
2699         bzero(lcache, sizeof(*lcache));
2700         TAILQ_INIT(&lcache->list);
2701         while (count) {
2702                 item = kmalloc(sizeof(*item), hmp->m_misc, M_WAITOK|M_ZERO);
2703                 item->copy = kmalloc(sizeof(*item->copy),
2704                                      hmp->m_misc, M_WAITOK);
2705                 TAILQ_INIT(&item->list);
2706                 TAILQ_INSERT_TAIL(&lcache->list, item, entry);
2707                 --count;
2708         }
2709 }
2710
2711 void
2712 hammer_btree_lcache_free(hammer_mount_t hmp, hammer_node_lock_t lcache)
2713 {
2714         hammer_node_lock_t item;
2715
2716         while ((item = TAILQ_FIRST(&lcache->list)) != NULL) {
2717                 TAILQ_REMOVE(&lcache->list, item, entry);
2718                 KKASSERT(item->copy);
2719                 KKASSERT(TAILQ_EMPTY(&item->list));
2720                 kfree(item->copy, hmp->m_misc);
2721                 kfree(item, hmp->m_misc);
2722         }
2723         KKASSERT(lcache->copy == NULL);
2724 }
2725
2726 /*
2727  * Exclusively lock all the children of node.  This is used by the split
2728  * code to prevent anyone from accessing the children of a cursor node
2729  * while we fix-up its parent offset.
2730  *
2731  * If we don't lock the children we can really mess up cursors which block
2732  * trying to cursor-up into our node.
2733  *
2734  * On failure EDEADLK (or some other error) is returned.  If a deadlock
2735  * error is returned the cursor is adjusted to block on termination.
2736  *
2737  * The caller is responsible for managing parent->node, the root's node
2738  * is usually aliased from a cursor.
2739  */
2740 int
2741 hammer_btree_lock_children(hammer_cursor_t cursor, int depth,
2742                            hammer_node_lock_t parent,
2743                            hammer_node_lock_t lcache)
2744 {
2745         hammer_node_t node;
2746         hammer_node_lock_t item;
2747         hammer_node_ondisk_t ondisk;
2748         hammer_btree_elm_t elm;
2749         hammer_node_t child;
2750         struct hammer_mount *hmp;
2751         int error;
2752         int i;
2753
2754         node = parent->node;
2755         ondisk = node->ondisk;
2756         error = 0;
2757         hmp = cursor->trans->hmp;
2758
2759         /*
2760          * We really do not want to block on I/O with exclusive locks held,
2761          * pre-get the children before trying to lock the mess.  This is
2762          * only done one-level deep for now.
2763          */
2764         for (i = 0; i < ondisk->count; ++i) {
2765                 ++hammer_stats_btree_elements;
2766                 elm = &ondisk->elms[i];
2767                 if (elm->base.btype != HAMMER_BTREE_TYPE_LEAF &&
2768                     elm->base.btype != HAMMER_BTREE_TYPE_INTERNAL) {
2769                         continue;
2770                 }
2771                 child = hammer_get_node(cursor->trans,
2772                                         elm->internal.subtree_offset,
2773                                         0, &error);
2774                 if (child)
2775                         hammer_rel_node(child);
2776         }
2777
2778         /*
2779          * Do it for real
2780          */
2781         for (i = 0; error == 0 && i < ondisk->count; ++i) {
2782                 ++hammer_stats_btree_elements;
2783                 elm = &ondisk->elms[i];
2784
2785                 switch(elm->base.btype) {
2786                 case HAMMER_BTREE_TYPE_INTERNAL:
2787                 case HAMMER_BTREE_TYPE_LEAF:
2788                         KKASSERT(elm->internal.subtree_offset != 0);
2789                         child = hammer_get_node(cursor->trans,
2790                                                 elm->internal.subtree_offset,
2791                                                 0, &error);
2792                         break;
2793                 default:
2794                         child = NULL;
2795                         break;
2796                 }
2797                 if (child) {
2798                         if (hammer_lock_ex_try(&child->lock) != 0) {
2799                                 if (cursor->deadlk_node == NULL) {
2800                                         cursor->deadlk_node = child;
2801                                         hammer_ref_node(cursor->deadlk_node);
2802                                 }
2803                                 error = EDEADLK;
2804                                 hammer_rel_node(child);
2805                         } else {
2806                                 if (lcache) {
2807                                         item = TAILQ_FIRST(&lcache->list);
2808                                         KKASSERT(item != NULL);
2809                                         item->flags |= HAMMER_NODE_LOCK_LCACHE;
2810                                         TAILQ_REMOVE(&lcache->list,
2811                                                      item, entry);
2812                                 } else {
2813                                         item = kmalloc(sizeof(*item),
2814                                                        hmp->m_misc,
2815                                                        M_WAITOK|M_ZERO);
2816                                         TAILQ_INIT(&item->list);
2817                                 }
2818
2819                                 TAILQ_INSERT_TAIL(&parent->list, item, entry);
2820                                 item->parent = parent;
2821                                 item->node = child;
2822                                 item->index = i;
2823                                 item->count = child->ondisk->count;
2824
2825                                 /*
2826                                  * Recurse (used by the rebalancing code)
2827                                  */
2828                                 if (depth > 1 && elm->base.btype == HAMMER_BTREE_TYPE_INTERNAL) {
2829                                         error = hammer_btree_lock_children(
2830                                                         cursor,
2831                                                         depth - 1,
2832                                                         item,
2833                                                         lcache);
2834                                 }
2835                         }
2836                 }
2837         }
2838         if (error)
2839                 hammer_btree_unlock_children(hmp, parent, lcache);
2840         return(error);
2841 }
2842
2843 /*
2844  * Create an in-memory copy of all B-Tree nodes listed, recursively,
2845  * including the parent.
2846  */
2847 void
2848 hammer_btree_lock_copy(hammer_cursor_t cursor, hammer_node_lock_t parent)
2849 {
2850         hammer_mount_t hmp = cursor->trans->hmp;
2851         hammer_node_lock_t item;
2852
2853         if (parent->copy == NULL) {
2854                 KKASSERT((parent->flags & HAMMER_NODE_LOCK_LCACHE) == 0);
2855                 parent->copy = kmalloc(sizeof(*parent->copy),
2856                                        hmp->m_misc, M_WAITOK);
2857         }
2858         KKASSERT((parent->flags & HAMMER_NODE_LOCK_UPDATED) == 0);
2859         *parent->copy = *parent->node->ondisk;
2860         TAILQ_FOREACH(item, &parent->list, entry) {
2861                 hammer_btree_lock_copy(cursor, item);
2862         }
2863 }
2864
2865 /*
2866  * Recursively sync modified copies to the media.
2867  */
2868 int
2869 hammer_btree_sync_copy(hammer_cursor_t cursor, hammer_node_lock_t parent)
2870 {
2871         hammer_node_lock_t item;
2872         int count = 0;
2873
2874         if (parent->flags & HAMMER_NODE_LOCK_UPDATED) {
2875                 ++count;
2876                 hammer_modify_node_all(cursor->trans, parent->node);
2877                 *parent->node->ondisk = *parent->copy;
2878                 hammer_modify_node_done(parent->node);
2879                 if (parent->copy->type == HAMMER_BTREE_TYPE_DELETED) {
2880                         hammer_flush_node(parent->node, 0);
2881                         hammer_delete_node(cursor->trans, parent->node);
2882                 }
2883         }
2884         TAILQ_FOREACH(item, &parent->list, entry) {
2885                 count += hammer_btree_sync_copy(cursor, item);
2886         }
2887         return(count);
2888 }
2889
2890 /*
2891  * Release previously obtained node locks.  The caller is responsible for
2892  * cleaning up parent->node itself (its usually just aliased from a cursor),
2893  * but this function will take care of the copies.
2894  *
2895  * NOTE: The root node is not placed in the lcache and node->copy is not
2896  *       deallocated when lcache != NULL.
2897  */
2898 void
2899 hammer_btree_unlock_children(hammer_mount_t hmp, hammer_node_lock_t parent,
2900                              hammer_node_lock_t lcache)
2901 {
2902         hammer_node_lock_t item;
2903         hammer_node_ondisk_t copy;
2904
2905         while ((item = TAILQ_FIRST(&parent->list)) != NULL) {
2906                 TAILQ_REMOVE(&parent->list, item, entry);
2907                 hammer_btree_unlock_children(hmp, item, lcache);
2908                 hammer_unlock(&item->node->lock);
2909                 hammer_rel_node(item->node);
2910                 if (lcache) {
2911                         /*
2912                          * NOTE: When placing the item back in the lcache
2913                          *       the flag is cleared by the bzero().
2914                          *       Remaining fields are cleared as a safety
2915                          *       measure.
2916                          */
2917                         KKASSERT(item->flags & HAMMER_NODE_LOCK_LCACHE);
2918                         KKASSERT(TAILQ_EMPTY(&item->list));
2919                         copy = item->copy;
2920                         bzero(item, sizeof(*item));
2921                         TAILQ_INIT(&item->list);
2922                         item->copy = copy;
2923                         if (copy)
2924                                 bzero(copy, sizeof(*copy));
2925                         TAILQ_INSERT_TAIL(&lcache->list, item, entry);
2926                 } else {
2927                         kfree(item, hmp->m_misc);
2928                 }
2929         }
2930         if (parent->copy && (parent->flags & HAMMER_NODE_LOCK_LCACHE) == 0) {
2931                 kfree(parent->copy, hmp->m_misc);
2932                 parent->copy = NULL;    /* safety */
2933         }
2934 }
2935
2936 /************************************************************************
2937  *                         MISCELLANIOUS SUPPORT                        *
2938  ************************************************************************/
2939
2940 /*
2941  * Compare two B-Tree elements, return -N, 0, or +N (e.g. similar to strcmp).
2942  *
2943  * Note that for this particular function a return value of -1, 0, or +1
2944  * can denote a match if create_tid is otherwise discounted.  A create_tid
2945  * of zero is considered to be 'infinity' in comparisons.
2946  *
2947  * See also hammer_rec_rb_compare() and hammer_rec_cmp() in hammer_object.c.
2948  */
2949 int
2950 hammer_btree_cmp(hammer_base_elm_t key1, hammer_base_elm_t key2)
2951 {
2952         if (key1->localization < key2->localization)
2953                 return(-5);
2954         if (key1->localization > key2->localization)
2955                 return(5);
2956
2957         if (key1->obj_id < key2->obj_id)
2958                 return(-4);
2959         if (key1->obj_id > key2->obj_id)
2960                 return(4);
2961
2962         if (key1->rec_type < key2->rec_type)
2963                 return(-3);
2964         if (key1->rec_type > key2->rec_type)
2965                 return(3);
2966
2967         if (key1->key < key2->key)
2968                 return(-2);
2969         if (key1->key > key2->key)
2970                 return(2);
2971
2972         /*
2973          * A create_tid of zero indicates a record which is undeletable
2974          * and must be considered to have a value of positive infinity.
2975          */
2976         if (key1->create_tid == 0) {
2977                 if (key2->create_tid == 0)
2978                         return(0);
2979                 return(1);
2980         }
2981         if (key2->create_tid == 0)
2982                 return(-1);
2983         if (key1->create_tid < key2->create_tid)
2984                 return(-1);
2985         if (key1->create_tid > key2->create_tid)
2986                 return(1);
2987         return(0);
2988 }
2989
2990 /*
2991  * Test a timestamp against an element to determine whether the
2992  * element is visible.  A timestamp of 0 means 'infinity'.
2993  */
2994 int
2995 hammer_btree_chkts(hammer_tid_t asof, hammer_base_elm_t base)
2996 {
2997         if (asof == 0) {
2998                 if (base->delete_tid)
2999                         return(1);
3000                 return(0);
3001         }
3002         if (asof < base->create_tid)
3003                 return(-1);
3004         if (base->delete_tid && asof >= base->delete_tid)
3005                 return(1);
3006         return(0);
3007 }
3008
3009 /*
3010  * Create a separator half way inbetween key1 and key2.  For fields just
3011  * one unit apart, the separator will match key2.  key1 is on the left-hand
3012  * side and key2 is on the right-hand side.
3013  *
3014  * key2 must be >= the separator.  It is ok for the separator to match key2.
3015  *
3016  * NOTE: Even if key1 does not match key2, the separator may wind up matching
3017  * key2.
3018  *
3019  * NOTE: It might be beneficial to just scrap this whole mess and just
3020  * set the separator to key2.
3021  */
3022 #define MAKE_SEPARATOR(key1, key2, dest, field) \
3023         dest->field = key1->field + ((key2->field - key1->field + 1) >> 1);
3024
3025 static void
3026 hammer_make_separator(hammer_base_elm_t key1, hammer_base_elm_t key2,
3027                       hammer_base_elm_t dest)
3028 {
3029         bzero(dest, sizeof(*dest));
3030
3031         dest->rec_type = key2->rec_type;
3032         dest->key = key2->key;
3033         dest->obj_id = key2->obj_id;
3034         dest->create_tid = key2->create_tid;
3035
3036         MAKE_SEPARATOR(key1, key2, dest, localization);
3037         if (key1->localization == key2->localization) {
3038                 MAKE_SEPARATOR(key1, key2, dest, obj_id);
3039                 if (key1->obj_id == key2->obj_id) {
3040                         MAKE_SEPARATOR(key1, key2, dest, rec_type);
3041                         if (key1->rec_type == key2->rec_type) {
3042                                 MAKE_SEPARATOR(key1, key2, dest, key);
3043                                 /*
3044                                  * Don't bother creating a separator for
3045                                  * create_tid, which also conveniently avoids
3046                                  * having to handle the create_tid == 0
3047                                  * (infinity) case.  Just leave create_tid
3048                                  * set to key2.
3049                                  *
3050                                  * Worst case, dest matches key2 exactly,
3051                                  * which is acceptable.
3052                                  */
3053                         }
3054                 }
3055         }
3056 }
3057
3058 #undef MAKE_SEPARATOR
3059
3060 /*
3061  * Return whether a generic internal or leaf node is full
3062  */
3063 static int
3064 btree_node_is_full(hammer_node_ondisk_t node)
3065 {
3066         switch(node->type) {
3067         case HAMMER_BTREE_TYPE_INTERNAL:
3068                 if (node->count == HAMMER_BTREE_INT_ELMS)
3069                         return(1);
3070                 break;
3071         case HAMMER_BTREE_TYPE_LEAF:
3072                 if (node->count == HAMMER_BTREE_LEAF_ELMS)
3073                         return(1);
3074                 break;
3075         default:
3076                 panic("illegal btree subtype");
3077         }
3078         return(0);
3079 }
3080
3081 #if 0
3082 static int
3083 btree_max_elements(u_int8_t type)
3084 {
3085         if (type == HAMMER_BTREE_TYPE_LEAF)
3086                 return(HAMMER_BTREE_LEAF_ELMS);
3087         if (type == HAMMER_BTREE_TYPE_INTERNAL)
3088                 return(HAMMER_BTREE_INT_ELMS);
3089         panic("btree_max_elements: bad type %d\n", type);
3090 }
3091 #endif
3092
3093 void
3094 hammer_print_btree_node(hammer_node_ondisk_t ondisk)
3095 {
3096         hammer_btree_elm_t elm;
3097         int i;
3098
3099         kprintf("node %p count=%d parent=%016llx type=%c\n",
3100                 ondisk, ondisk->count,
3101                 (long long)ondisk->parent, ondisk->type);
3102
3103         /*
3104          * Dump both boundary elements if an internal node
3105          */
3106         if (ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
3107                 for (i = 0; i <= ondisk->count; ++i) {
3108                         elm = &ondisk->elms[i];
3109                         hammer_print_btree_elm(elm, ondisk->type, i);
3110                 }
3111         } else {
3112                 for (i = 0; i < ondisk->count; ++i) {
3113                         elm = &ondisk->elms[i];
3114                         hammer_print_btree_elm(elm, ondisk->type, i);
3115                 }
3116         }
3117 }
3118
3119 void
3120 hammer_print_btree_elm(hammer_btree_elm_t elm, u_int8_t type, int i)
3121 {
3122         kprintf("  %2d", i);
3123         kprintf("\tobj_id       = %016llx\n", (long long)elm->base.obj_id);
3124         kprintf("\tkey          = %016llx\n", (long long)elm->base.key);
3125         kprintf("\tcreate_tid   = %016llx\n", (long long)elm->base.create_tid);
3126         kprintf("\tdelete_tid   = %016llx\n", (long long)elm->base.delete_tid);
3127         kprintf("\trec_type     = %04x\n", elm->base.rec_type);
3128         kprintf("\tobj_type     = %02x\n", elm->base.obj_type);
3129         kprintf("\tbtype        = %02x (%c)\n",
3130                 elm->base.btype,
3131                 (elm->base.btype ? elm->base.btype : '?'));
3132         kprintf("\tlocalization = %02x\n", elm->base.localization);
3133
3134         switch(type) {
3135         case HAMMER_BTREE_TYPE_INTERNAL:
3136                 kprintf("\tsubtree_off  = %016llx\n",
3137                         (long long)elm->internal.subtree_offset);
3138                 break;
3139         case HAMMER_BTREE_TYPE_RECORD:
3140                 kprintf("\tdata_offset  = %016llx\n",
3141                         (long long)elm->leaf.data_offset);
3142                 kprintf("\tdata_len     = %08x\n", elm->leaf.data_len);
3143                 kprintf("\tdata_crc     = %08x\n", elm->leaf.data_crc);
3144                 break;
3145         }
3146 }