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