sys/vfs/hammer/hammer_rebalance.c

   1 /*
   2  * Copyright (c) 2009 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
  35 #include "hammer.h"
  36
  37 static int rebalance_node(struct hammer_ioc_rebalance *rebal,
  38                         hammer_cursor_t cursor);
  39 static void rebalance_closeout(hammer_node_lock_t base_item, int base_count,
  40                         hammer_btree_elm_t elm);
  41 static void rebalance_parent_ptrs(hammer_node_lock_t base_item, int index,
  42                         hammer_node_lock_t item, hammer_node_lock_t chld_item);
  43
  44 /*
  45  * Iterate through the specified range of object ids and rebalance B-Tree
  46  * leaf and internal nodes we encounter.  A forwards iteration is used.
  47  *
  48  * All leafs are at the same depth.  We use the b-tree scan code loosely
  49  * to position ourselves and create degenerate cases to skip indices
  50  * that we have rebalanced in bulk.
  51  */
  52
  53 int
  54 hammer_ioc_rebalance(hammer_transaction_t trans, hammer_inode_t ip,
  55                  struct hammer_ioc_rebalance *rebal)
  56 {
  57         struct hammer_cursor cursor;
  58         hammer_btree_leaf_elm_t elm;
  59         int error;
  60         int seq;
  61
  62         if ((rebal->key_beg.localization | rebal->key_end.localization) &
  63             HAMMER_LOCALIZE_PSEUDOFS_MASK) {
  64                 return(EINVAL);
  65         }
  66         if (rebal->key_beg.localization > rebal->key_end.localization)
  67                 return(EINVAL);
  68         if (rebal->key_beg.localization == rebal->key_end.localization) {
  69                 if (rebal->key_beg.obj_id > rebal->key_end.obj_id)
  70                         return(EINVAL);
  71                 /* key-space limitations - no check needed */
  72         }
  73         if (rebal->saturation < HAMMER_BTREE_INT_ELMS / 2)
  74                 rebal->saturation = HAMMER_BTREE_INT_ELMS / 2;
  75         if (rebal->saturation > HAMMER_BTREE_INT_ELMS)
  76                 rebal->saturation = HAMMER_BTREE_INT_ELMS;
  77
  78         rebal->key_cur = rebal->key_beg;
  79         rebal->key_cur.localization &= HAMMER_LOCALIZE_MASK;
  80         rebal->key_cur.localization += ip->obj_localization;
  81
  82         seq = trans->hmp->flusher.act;
  83
  84         /*
  85          * Scan forwards.  Retries typically occur if a deadlock is detected.
  86          */
  87 retry:
  88         error = hammer_init_cursor(trans, &cursor, NULL, NULL);
  89         if (error) {
  90                 hammer_done_cursor(&cursor);
  91                 goto failed;
  92         }
  93         cursor.key_beg = rebal->key_cur;
  94         cursor.key_end = rebal->key_end;
  95         cursor.key_end.localization &= HAMMER_LOCALIZE_MASK;
  96         cursor.key_end.localization += ip->obj_localization;
  97         cursor.flags |= HAMMER_CURSOR_END_INCLUSIVE;
  98         cursor.flags |= HAMMER_CURSOR_BACKEND;
  99
 100         /*
 101          * Cause internal nodes to be returned on the way up.  Internal nodes
 102          * are not returned on the way down so we can create a degenerate
 103          * case to handle internal nodes as a trailing function of their
 104          * sub-trees.
 105          *
 106          * Note that by not setting INSERTING or PRUNING no boundary
 107          * corrections will be made and a sync lock is not needed for the
 108          * B-Tree scan itself.
 109          */
 110         cursor.flags |= HAMMER_CURSOR_REBLOCKING;
 111
 112         error = hammer_btree_first(&cursor);
 113
 114         while (error == 0) {
 115                 /*
 116                  * Rebalancing can be hard on the memory allocator, make
 117                  * sure there is enough free memory before doing it.
 118                  */
 119                 vm_wait_nominal();
 120
 121                 /*
 122                  * We only care about internal nodes visited for the last
 123                  * time on the way up... that is, a trailing scan of the
 124                  * internal node after all of its children have been recursed
 125                  * through.
 126                  */
 127                 if (cursor.node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
 128                         /*
 129                          * Leave cursor.index alone, we want to recurse
 130                          * through all children of the internal node before
 131                          * visiting it.
 132                          *
 133                          * Process the internal node on the way up after
 134                          * the last child's sub-tree has been balanced.
 135                          */
 136                         if (cursor.index == cursor.node->ondisk->count - 1) {
 137                                 hammer_sync_lock_sh(trans);
 138                                 error = rebalance_node(rebal, &cursor);
 139                                 hammer_sync_unlock(trans);
 140                         }
 141                 } else {
 142                         /*
 143                          * We don't need to iterate through all the leaf
 144                          * elements, we only care about the parent (internal)
 145                          * node.
 146                          */
 147                         cursor.index = cursor.node->ondisk->count - 1;
 148                 }
 149                 if (error)
 150                         break;
 151
 152                 /*
 153                  * Update returned scan position and do a flush if
 154                  * necessary.
 155                  *
 156                  * WARNING: We extract the base using the leaf element
 157                  *          type but this could be an internal node.  The
 158                  *          base is the same either way.
 159                  *
 160                  *          However, due to the rebalancing operation the
 161                  *          cursor position may have exceeded the right-hand
 162                  *          boundary.
 163                  *
 164                  * WARNING: See warnings in hammer_unlock_cursor()
 165                  *          function.
 166                  */
 167                 elm = &cursor.node->ondisk->elms[cursor.index].leaf;
 168                 rebal->key_cur = elm->base;
 169                 ++rebal->stat_ncount;
 170
 171                 while (hammer_flusher_meta_halflimit(trans->hmp) ||
 172                        hammer_flusher_undo_exhausted(trans, 2)) {
 173                         hammer_unlock_cursor(&cursor);
 174                         hammer_flusher_wait(trans->hmp, seq);
 175                         hammer_lock_cursor(&cursor);
 176                         seq = hammer_flusher_async_one(trans->hmp);
 177                 }
 178
 179                 /*
 180                  * Before iterating check if the rebalance operation caused
 181                  * the cursor to index past the right-hand boundary and make
 182                  * sure to stop if it does.  Otherwise the iteration may
 183                  * panic e.g. due to the key maxing out its fields and no
 184                  * longer being within the strict bounds of the root node.
 185                  */
 186                 if (hammer_btree_cmp(&rebal->key_cur, &cursor.key_end) > 0) {
 187                         rebal->key_cur = cursor.key_end;
 188                         break;
 189                 }
 190
 191                 /*
 192                  * Iterate, stop if a signal was received.
 193                  */
 194                 if ((error = hammer_signal_check(trans->hmp)) != 0)
 195                         break;
 196                 error = hammer_btree_iterate(&cursor);
 197         }
 198         if (error == ENOENT)
 199                 error = 0;
 200         hammer_done_cursor(&cursor);
 201         if (error == EDEADLK) {
 202                 ++rebal->stat_collisions;
 203                 goto retry;
 204         }
 205         if (error == EINTR) {
 206                 rebal->head.flags |= HAMMER_IOC_HEAD_INTR;
 207                 error = 0;
 208         }
 209 failed:
 210         rebal->key_cur.localization &= HAMMER_LOCALIZE_MASK;
 211         return(error);
 212 }
 213
 214 /*
 215  * Rebalance an internal node, called via a trailing upward recursion.
 216  * All the children have already been individually rebalanced.
 217  *
 218  * To rebalance we scan the elements in the children and pack them,
 219  * so we actually need to lock the children and the children's children.
 220  *
 221  *      INTERNAL_NODE
 222  *      / / | | | \ \
 223  *     C C  C C C  C C  children (first level) (internal or leaf nodes)
 224  *                      children's elements (second level)
 225  *
 226  *      <<<----------   pack children's elements, possibly remove excess
 227  *                      children after packing.
 228  *
 229  * NOTE: The mirror_tids, parent pointers, and child pointers must be updated.
 230  *       Any live tracked B-Tree nodes must be updated (we worm out of that
 231  *       by not allowing any).  And boundary elements must be preserved.
 232  *
 233  * NOTE: If the children are leaf nodes we may have a degenerate case
 234  *       case where there are no elements in the leafs.
 235  *
 236  * XXX live-tracked
 237  */
 238 static int
 239 rebalance_node(struct hammer_ioc_rebalance *rebal, hammer_cursor_t cursor)
 240 {
 241         struct hammer_node_lock lockroot;
 242         hammer_node_lock_t base_item;
 243         hammer_node_lock_t chld_item;
 244         hammer_node_lock_t item;
 245         hammer_btree_elm_t elm;
 246         hammer_node_t node;
 247         hammer_tid_t tid;
 248         u_int8_t type1;
 249         int base_count;
 250         int root_count;
 251         int avg_elms;
 252         int count;
 253         int error;
 254         int i;
 255         int n;
 256
 257         /*
 258          * Lock the parent node via the cursor, collect and lock our
 259          * children and children's children.
 260          *
 261          * By the way, this is a LOT of locks.
 262          */
 263         hammer_node_lock_init(&lockroot, cursor->node);
 264         error = hammer_cursor_upgrade(cursor);
 265         if (error)
 266                 goto done;
 267         error = hammer_btree_lock_children(cursor, 2, &lockroot);
 268         if (error)
 269                 goto done;
 270
 271         /*
 272          * Make a copy of all the locked on-disk data to simplify the element
 273          * shifting we are going to have to do.  We will modify the copy
 274          * first.
 275          */
 276         hammer_btree_lock_copy(cursor, &lockroot);
 277
 278         /*
 279          * Look at the first child node.
 280          */
 281         if (TAILQ_FIRST(&lockroot.list) == NULL)
 282                 goto done;
 283         type1 = TAILQ_FIRST(&lockroot.list)->node->ondisk->type;
 284
 285         /*
 286          * Figure out the total number of children's children and
 287          * calculate the average number of elements per child.
 288          *
 289          * The minimum avg_elms is 1 when count > 0.  avg_elms * root_elms
 290          * is always greater or equal to count.
 291          *
 292          * If count == 0 we hit a degenerate case which will cause
 293          * avg_elms to also calculate as 0.
 294          */
 295         if (hammer_debug_general & 0x1000)
 296                 kprintf("lockroot %p count %d\n", &lockroot, lockroot.count);
 297         count = 0;
 298         TAILQ_FOREACH(item, &lockroot.list, entry) {
 299                 if (hammer_debug_general & 0x1000)
 300                         kprintf("add count %d\n", item->count);
 301                 count += item->count;
 302                 KKASSERT(item->node->ondisk->type == type1);
 303         }
 304         avg_elms = (count + (lockroot.count - 1)) / lockroot.count;
 305         KKASSERT(avg_elms >= 0);
 306
 307         /*
 308          * If the average number of elements per child is too low then
 309          * calculate the desired number of children (n) such that the
 310          * average number of elements is reasonable.
 311          *
 312          * If the desired number of children is 1 then avg_elms will
 313          * wind up being count, which may still be smaller then saturation
 314          * but that is ok.
 315          */
 316         if (count && avg_elms < rebal->saturation) {
 317                 n = (count + (rebal->saturation - 1)) / rebal->saturation;
 318                 avg_elms = (count + (n - 1)) / n;
 319         }
 320
 321         /*
 322          * Pack the elements in the children.  Elements for each item is
 323          * packed into base_item until avg_elms is reached, then base_item
 324          * iterates.
 325          *
 326          * hammer_cursor_moved_element() is called for each element moved
 327          * to update tracked cursors, including the index beyond the last
 328          * element (at count).
 329          *
 330          * Any cursors tracking the internal node itself must also be
 331          * updated, potentially repointing them at a leaf and clearing
 332          * ATEDISK.
 333          */
 334         base_item = TAILQ_FIRST(&lockroot.list);
 335         base_count = 0;
 336         root_count = 0;
 337
 338         TAILQ_FOREACH(item, &lockroot.list, entry) {
 339                 node = item->node;
 340                 KKASSERT(item->count == node->ondisk->count);
 341                 chld_item = TAILQ_FIRST(&item->list);
 342                 for (i = 0; i < item->count; ++i) {
 343                         /*
 344                          * Closeout.  If the next element is at index 0
 345                          * just use the existing separator in the parent.
 346                          */
 347                         if (base_count == avg_elms) {
 348                                 if (i == 0) {
 349                                         elm = &lockroot.node->ondisk->elms[
 350                                                 item->index];
 351                                 } else {
 352                                         elm = &node->ondisk->elms[i];
 353                                 }
 354                                 rebalance_closeout(base_item, base_count, elm);
 355                                 base_item = TAILQ_NEXT(base_item, entry);
 356                                 KKASSERT(base_item);
 357                                 base_count = 0;
 358                                 ++root_count;
 359                         }
 360
 361                         /*
 362                          * Check degenerate no-work case.  Otherwise pack
 363                          * the element.
 364                          *
 365                          * All changes are made to the copy.
 366                          */
 367                         if (item == base_item && i == base_count) {
 368                                 ++base_count;
 369                                 if (chld_item)
 370                                         chld_item = TAILQ_NEXT(chld_item, entry);
 371                                 continue;
 372                         }
 373
 374                         /*
 375                          * Pack element.
 376                          */
 377                         elm = &base_item->copy->elms[base_count];
 378                         *elm = node->ondisk->elms[i];
 379                         base_item->flags |= HAMMER_NODE_LOCK_UPDATED;
 380
 381                         /*
 382                          * Adjust the mirror_tid of the target and the
 383                          * internal element linkage.
 384                          *
 385                          * The parent node (lockroot.node) should already
 386                          * have an aggregate mirror_tid so we do not have
 387                          * to update that.  However, it is possible for us
 388                          * to catch a hammer_btree_mirror_propagate() with
 389                          * its pants down.  Update the parent if necessary.
 390                          */
 391                         tid = node->ondisk->mirror_tid;
 392
 393                         if (base_item->copy->mirror_tid < tid) {
 394                                 base_item->copy->mirror_tid = tid;
 395                                 if (lockroot.copy->mirror_tid < tid) {
 396                                         lockroot.copy->mirror_tid = tid;
 397                                         lockroot.flags |=
 398                                                 HAMMER_NODE_LOCK_UPDATED;
 399                                 }
 400                                 if (lockroot.copy->elms[root_count].
 401                                     internal.mirror_tid < tid) {
 402                                         lockroot.copy->elms[root_count].
 403                                                 internal.mirror_tid = tid;
 404                                         lockroot.flags |=
 405                                                 HAMMER_NODE_LOCK_UPDATED;
 406                                 }
 407                                 base_item->flags |= HAMMER_NODE_LOCK_UPDATED;
 408                         }
 409
 410                         /*
 411                          * We moved elm.  The parent pointers for any
 412                          * children of elm must be repointed.
 413                          */
 414                         if (item != base_item &&
 415                             node->ondisk->type == HAMMER_BTREE_TYPE_INTERNAL) {
 416                                 KKASSERT(chld_item);
 417                                 rebalance_parent_ptrs(base_item, base_count,
 418                                                       item, chld_item);
 419                         }
 420                         hammer_cursor_moved_element(item->parent->node,
 421                                                     item->index,
 422                                                     node, i,
 423                                                     base_item->node,
 424                                                     base_count);
 425                         ++base_count;
 426                         if (chld_item)
 427                                 chld_item = TAILQ_NEXT(chld_item, entry);
 428                 }
 429
 430                 /*
 431                  * Always call at the end (i == number of elements) in
 432                  * case a cursor is sitting indexed there.
 433                  */
 434                 hammer_cursor_moved_element(item->parent->node, item->index,
 435                                             node, i,
 436                                             base_item->node, base_count);
 437         }
 438
 439         /*
 440          * Packing complete, close-out base_item using the right-hand
 441          * boundary of the original parent.
 442          *
 443          * If we will be deleting nodes from the root shift the old
 444          * right-hand-boundary to the new ending index.
 445          */
 446         elm = &lockroot.node->ondisk->elms[lockroot.node->ondisk->count];
 447         rebalance_closeout(base_item, base_count, elm);
 448         ++root_count;
 449         if (lockroot.copy->count != root_count) {
 450                 lockroot.copy->count = root_count;
 451                 lockroot.copy->elms[root_count] = *elm;
 452                 lockroot.flags |= HAMMER_NODE_LOCK_UPDATED;
 453         }
 454
 455         /*
 456          * Any extra items beyond base_item are now completely empty and
 457          * can be destroyed.  Queue the destruction up in the copy.  Note
 458          * that none of the destroyed nodes are part of our cursor.
 459          *
 460          * The cursor is locked so it isn't on the tracking list.  It
 461          * should have been pointing at the boundary element (at root_count).
 462          * When deleting elements from the root (which is cursor.node), we
 463          * have to update the cursor.index manually to keep it in bounds.
 464          */
 465         while ((base_item = TAILQ_NEXT(base_item, entry)) != NULL) {
 466                 hammer_cursor_removed_node(base_item->node, lockroot.node,
 467                                            base_count);
 468                 hammer_cursor_deleted_element(lockroot.node, base_count);
 469                 base_item->copy->type = HAMMER_BTREE_TYPE_DELETED;
 470                 base_item->copy->count = 0;
 471                 base_item->flags |= HAMMER_NODE_LOCK_UPDATED;
 472                 if (cursor->index > lockroot.copy->count)
 473                         --cursor->index;
 474                 ++rebal->stat_deletions;
 475         }
 476
 477         /*
 478          * All done, sync the locked child tree to disk.  This will also
 479          * flush and delete deleted nodes.
 480          */
 481         rebal->stat_nrebal += hammer_btree_sync_copy(cursor, &lockroot);
 482 done:
 483         hammer_btree_unlock_children(cursor, &lockroot);
 484         hammer_cursor_downgrade(cursor);
 485         return (error);
 486 }
 487
 488 /*
 489  * Close-out the child base_item.  This node contains base_count
 490  * elements.
 491  *
 492  * If the node is an internal node the right-hand boundary must be
 493  * set to elm.
 494  */
 495 static
 496 void
 497 rebalance_closeout(hammer_node_lock_t base_item, int base_count,
 498                    hammer_btree_elm_t elm)
 499 {
 500         hammer_node_lock_t parent;
 501         hammer_btree_elm_t base_elm;
 502         hammer_btree_elm_t rbound_elm;
 503         u_int8_t save;
 504
 505         /*
 506          * Update the count.  NOTE:  base_count can be 0 for the
 507          * degenerate leaf case.
 508          */
 509         if (hammer_debug_general & 0x1000) {
 510                 kprintf("rebalance_closeout %016llx:",
 511                         (long long)base_item->node->node_offset);
 512         }
 513         if (base_item->copy->count != base_count) {
 514                 base_item->flags |= HAMMER_NODE_LOCK_UPDATED;
 515                 base_item->copy->count = base_count;
 516                 if (hammer_debug_general & 0x1000)
 517                         kprintf(" (count update)");
 518         }
 519
 520         /*
 521          * If we are closing out an internal node we must assign
 522          * a right-hand boundary.  Use the element contents as the
 523          * right-hand boundary.
 524          *
 525          * Internal nodes are required to have at least one child,
 526          * otherwise the left and right boundary would end up being
 527          * the same element.  Only leaf nodes can be empty.
 528          *
 529          * Rebalancing may cut-off an internal node such that the
 530          * new right hand boundary is the next element anyway, but
 531          * we still have to make sure that subtree_offset, btype,
 532          * and mirror_tid are all 0.
 533          */
 534         if (base_item->copy->type == HAMMER_BTREE_TYPE_INTERNAL) {
 535                 KKASSERT(base_count != 0);
 536                 base_elm = &base_item->copy->elms[base_count];
 537
 538                 if (bcmp(base_elm, elm, sizeof(*elm)) != 0 ||
 539                     elm->internal.subtree_offset ||
 540                     elm->internal.mirror_tid ||
 541                     elm->base.btype) {
 542                         *base_elm = *elm;
 543                         base_elm->internal.subtree_offset = 0;
 544                         base_elm->internal.mirror_tid = 0;
 545                         base_elm->base.btype = 0;
 546                         base_item->flags |= HAMMER_NODE_LOCK_UPDATED;
 547                         if (hammer_debug_general & 0x1000)
 548                                 kprintf(" (rhs update)");
 549                 } else {
 550                         if (hammer_debug_general & 0x1000)
 551                                 kprintf(" (rhs same)");
 552                 }
 553         }
 554
 555         /*
 556          * The parent's boundary must be updated.  Be careful to retain
 557          * the btype and non-base internal fields as that information is
 558          * unrelated.
 559          */
 560         parent = base_item->parent;
 561         rbound_elm = &parent->copy->elms[base_item->index + 1];
 562         if (bcmp(&rbound_elm->base, &elm->base, sizeof(elm->base)) != 0) {
 563                 save = rbound_elm->base.btype;
 564                 rbound_elm->base = elm->base;
 565                 rbound_elm->base.btype = save;
 566                 parent->flags |= HAMMER_NODE_LOCK_UPDATED;
 567                 if (hammer_debug_general & 0x1000) {
 568                         kprintf(" (parent bound update %d)",
 569                                 base_item->index + 1);
 570                 }
 571         }
 572         if (hammer_debug_general & 0x1000)
 573                 kprintf("\n");
 574 }
 575
 576 /*
 577  * An element in item has moved to base_item.  We must update the parent
 578  * pointer of the node the element points to (which is chld_item).
 579  */
 580 static
 581 void
 582 rebalance_parent_ptrs(hammer_node_lock_t base_item, int index,
 583                       hammer_node_lock_t item, hammer_node_lock_t chld_item)
 584 {
 585         KKASSERT(chld_item->node->ondisk->parent == item->node->node_offset);
 586         chld_item->copy->parent = base_item->node->node_offset;
 587         chld_item->flags |= HAMMER_NODE_LOCK_UPDATED;
 588         hammer_cursor_parent_changed(chld_item->node,
 589                                      item->node, base_item->node, index);
 590 }