sys/vfs/hammer2/hammer2_flush.c

   1 /*
   2  * Copyright (c) 2011-2014 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Matthew Dillon <dillon@dragonflybsd.org>
   6  * by Venkatesh Srinivas <vsrinivas@dragonflybsd.org>
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in
  16  *    the documentation and/or other materials provided with the
  17  *    distribution.
  18  * 3. Neither the name of The DragonFly Project nor the names of its
  19  *    contributors may be used to endorse or promote products derived
  20  *    from this software without specific, prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  23  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  26  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  27  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  30  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  31  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  32  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  33  * SUCH DAMAGE.
  34  */
  35
  36 #include <sys/cdefs.h>
  37 #include <sys/param.h>
  38 #include <sys/systm.h>
  39 #include <sys/types.h>
  40 #include <sys/lock.h>
  41 #include <sys/uuid.h>
  42
  43 #include "hammer2.h"
  44
  45 #define FLUSH_DEBUG 0
  46
  47 /*
  48  * Recursively flush the specified chain.  The chain is locked and
  49  * referenced by the caller and will remain so on return.  The chain
  50  * will remain referenced throughout but can temporarily lose its
  51  * lock during the recursion to avoid unnecessarily stalling user
  52  * processes.
  53  */
  54 struct hammer2_flush_info {
  55         hammer2_chain_t *parent;
  56         hammer2_trans_t *trans;
  57         int             depth;
  58         int             diddeferral;
  59         int             cache_index;
  60         int             domodify;
  61         struct h2_flush_deferral_list flush_list;
  62         hammer2_tid_t   sync_tid;       /* flush synchronization point */
  63 };
  64
  65 typedef struct hammer2_flush_info hammer2_flush_info_t;
  66
  67 static void hammer2_flush_core(hammer2_flush_info_t *info,
  68                                 hammer2_chain_t **chainp, int deleting);
  69 static int hammer2_flush_pass1(hammer2_chain_t *child, void *data);
  70 static int hammer2_flush_pass2(hammer2_chain_t *child, void *data);
  71 static int hammer2_flush_pass3(hammer2_chain_t *child, void *data);
  72 static int hammer2_flush_pass4(hammer2_chain_t *child, void *data);
  73 static int hammer2_flush_pass5(hammer2_chain_t *child, void *data);
  74 static void hammer2_rollup_stats(hammer2_chain_t *parent,
  75                                 hammer2_chain_t *child, int how);
  76
  77
  78 /*
  79  * Can we ignore a chain for the purposes of flushing modifications
  80  * to the media?
  81  *
  82  * This code is now degenerate.  We used to have to distinguish between
  83  * deleted chains and deleted chains associated with inodes that were
  84  * still open.  This mechanic has been fixed so the function is now
  85  * a simple test.
  86  */
  87 static __inline
  88 int
  89 h2ignore_deleted(hammer2_flush_info_t *info, hammer2_chain_t *chain)
  90 {
  91         return (chain->delete_tid <= info->sync_tid);
  92 }
  93
  94 #if 0
  95 static __inline
  96 void
  97 hammer2_updatestats(hammer2_flush_info_t *info, hammer2_blockref_t *bref,
  98                     int how)
  99 {
 100         hammer2_key_t bytes;
 101
 102         if (bref->type != 0) {
 103                 bytes = 1 << (bref->data_off & HAMMER2_OFF_MASK_RADIX);
 104                 if (bref->type == HAMMER2_BREF_TYPE_INODE)
 105                         info->inode_count += how;
 106                 if (how < 0)
 107                         info->data_count -= bytes;
 108                 else
 109                         info->data_count += bytes;
 110         }
 111 }
 112 #endif
 113
 114 /*
 115  * Transaction support functions for writing to the filesystem.
 116  *
 117  * Initializing a new transaction allocates a transaction ID.  Typically
 118  * passed a pmp (hmp passed as NULL), indicating a cluster transaction.  Can
 119  * be passed a NULL pmp and non-NULL hmp to indicate a transaction on a single
 120  * media target.  The latter mode is used by the recovery code.
 121  *
 122  * TWO TRANSACTION IDs can run concurrently, where one is a flush and the
 123  * other is a set of any number of concurrent filesystem operations.  We
 124  * can either have <running_fs_ops> + <waiting_flush> + <blocked_fs_ops>
 125  * or we can have <running_flush> + <concurrent_fs_ops>.
 126  *
 127  * During a flush, new fs_ops are only blocked until the fs_ops prior to
 128  * the flush complete.  The new fs_ops can then run concurrent with the flush.
 129  *
 130  * Buffer-cache transactions operate as fs_ops but never block.  A
 131  * buffer-cache flush will run either before or after the current pending
 132  * flush depending on its state.
 133  *
 134  * NOTE: The sync_tid for a flush's freemap allocation will match the
 135  *       sync_tid of the following <concurrent_fs_ops> transaction(s).
 136  *       The freemap topology will be out-of-step by one transaction id
 137  *       in order to give the flusher a stable freemap topology to flush
 138  *       out.  This is fixed up at mount-time using a quick incremental
 139  *       scan.
 140  */
 141 void
 142 hammer2_trans_init(hammer2_trans_t *trans, hammer2_pfsmount_t *pmp,
 143                    hammer2_mount_t *hmp, int flags)
 144 {
 145         hammer2_trans_t *head;
 146
 147         bzero(trans, sizeof(*trans));
 148         if (pmp) {
 149                 trans->pmp = pmp;
 150                 KKASSERT(hmp == NULL);
 151                 hmp = pmp->cluster.chains[0]->hmp;      /* XXX */
 152         } else {
 153                 trans->hmp_single = hmp;
 154                 KKASSERT(hmp);
 155         }
 156
 157         hammer2_voldata_lock(hmp);
 158         trans->flags = flags;
 159         trans->td = curthread;
 160         /*trans->delete_gen = 0;*/      /* multiple deletions within trans */
 161
 162         if (flags & HAMMER2_TRANS_ISFLUSH) {
 163                 /*
 164                  * If multiple flushes are trying to run we have to
 165                  * wait until it is our turn.  All flushes are serialized.
 166                  *
 167                  * We queue ourselves and then wait to become the head
 168                  * of the queue, allowing all prior flushes to complete.
 169                  *
 170                  * Multiple normal transactions can share the current
 171                  * transaction id but a flush transaction needs its own
 172                  * unique TID for proper block table update accounting.
 173                  */
 174                 ++hmp->flushcnt;
 175                 ++hmp->voldata.alloc_tid;
 176                 trans->sync_tid = hmp->voldata.alloc_tid;
 177                 trans->orig_tid = trans->sync_tid;
 178                 ++hmp->voldata.alloc_tid;
 179                 TAILQ_INSERT_TAIL(&hmp->transq, trans, entry);
 180                 if (TAILQ_FIRST(&hmp->transq) != trans) {
 181                         trans->blocked = 1;
 182                         while (trans->blocked) {
 183                                 lksleep(&trans->sync_tid, &hmp->voldatalk,
 184                                         0, "h2multf", hz);
 185                         }
 186                 }
 187         } else if (hmp->flushcnt == 0) {
 188                 /*
 189                  * No flushes are pending, we can go.
 190                  */
 191                 TAILQ_INSERT_TAIL(&hmp->transq, trans, entry);
 192                 trans->sync_tid = hmp->voldata.alloc_tid;
 193                 trans->orig_tid = trans->sync_tid;
 194
 195                 /* XXX improve/optimize inode allocation */
 196         } else if (trans->flags & HAMMER2_TRANS_BUFCACHE) {
 197                 /*
 198                  * A buffer cache transaction is requested while a flush
 199                  * is in progress.  The flush's PREFLUSH flag must be set
 200                  * in this situation.
 201                  *
 202                  * The buffer cache flush takes on the main flush's
 203                  * transaction id.
 204                  */
 205                 TAILQ_FOREACH(head, &hmp->transq, entry) {
 206                         if (head->flags & HAMMER2_TRANS_ISFLUSH)
 207                                 break;
 208                 }
 209                 KKASSERT(head);
 210                 KKASSERT(head->flags & HAMMER2_TRANS_PREFLUSH);
 211                 trans->flags |= HAMMER2_TRANS_PREFLUSH;
 212                 TAILQ_INSERT_AFTER(&hmp->transq, head, trans, entry);
 213                 trans->sync_tid = head->orig_tid;
 214                 trans->orig_tid = trans->sync_tid;
 215                 trans->flags |= HAMMER2_TRANS_CONCURRENT;
 216                 /* not allowed to block */
 217         } else {
 218                 /*
 219                  * A normal transaction is requested while a flush is in
 220                  * progress.  We insert after the current flush and may
 221                  * block.  Assign sync_tid = flush's tid + 1.
 222                  */
 223                 TAILQ_FOREACH(head, &hmp->transq, entry) {
 224                         if (head->flags & HAMMER2_TRANS_ISFLUSH)
 225                                 break;
 226                 }
 227                 KKASSERT(head);
 228                 TAILQ_INSERT_AFTER(&hmp->transq, head, trans, entry);
 229                 trans->sync_tid = head->orig_tid + 1;
 230                 trans->orig_tid = trans->sync_tid;
 231                 trans->flags |= HAMMER2_TRANS_CONCURRENT;
 232
 233                 /*
 234                  * XXX for now we must block new transactions, synchronous
 235                  * flush mode is on by default.
 236                  *
 237                  * If synchronous flush mode is enabled concurrent
 238                  * frontend transactions during the flush are not
 239                  * allowed (except we don't have a choice for buffer
 240                  * cache ops).
 241                  */
 242                 if (hammer2_synchronous_flush > 0 ||
 243                     TAILQ_FIRST(&hmp->transq) != head) {
 244                         trans->blocked = 1;
 245                         while (trans->blocked) {
 246                                 lksleep(&trans->sync_tid,
 247                                         &hmp->voldatalk, 0,
 248                                         "h2multf", hz);
 249                         }
 250                 }
 251         }
 252         if (flags & HAMMER2_TRANS_NEWINODE) {
 253                 if (hmp->voldata.inode_tid < HAMMER2_INODE_START)
 254                         hmp->voldata.inode_tid = HAMMER2_INODE_START;
 255                 trans->inode_tid = hmp->voldata.inode_tid++;
 256         }
 257         hammer2_voldata_unlock(hmp, 0);
 258 }
 259
 260 void
 261 hammer2_trans_done(hammer2_trans_t *trans)
 262 {
 263         hammer2_mount_t *hmp;
 264         hammer2_trans_t *head;
 265         hammer2_trans_t *scan;
 266
 267         if (trans->pmp)
 268                 hmp = trans->pmp->cluster.chains[0]->hmp;
 269         else
 270                 hmp = trans->hmp_single;
 271
 272         /*
 273          * Remove.
 274          */
 275         hammer2_voldata_lock(hmp);
 276         TAILQ_REMOVE(&hmp->transq, trans, entry);
 277         head = TAILQ_FIRST(&hmp->transq);
 278
 279         /*
 280          * Adjust flushcnt if this was a flush, clear TRANS_CONCURRENT
 281          * up through the next flush.  (If the head is a flush then we
 282          * stop there, unlike the unblock code following this section).
 283          */
 284         if (trans->flags & HAMMER2_TRANS_ISFLUSH) {
 285                 --hmp->flushcnt;
 286                 scan = head;
 287                 while (scan && (scan->flags & HAMMER2_TRANS_ISFLUSH) == 0) {
 288                         atomic_clear_int(&scan->flags,
 289                                          HAMMER2_TRANS_CONCURRENT);
 290                         scan = TAILQ_NEXT(scan, entry);
 291                 }
 292         }
 293
 294         /*
 295          * Unblock the head of the queue and any additional transactions
 296          * up to the next flush.  The head can be a flush and it will be
 297          * unblocked along with the non-flush transactions following it
 298          * (which are allowed to run concurrently with it).
 299          *
 300          * In synchronous flush mode we stop if the head transaction is
 301          * a flush.
 302          */
 303         if (head && head->blocked) {
 304                 head->blocked = 0;
 305                 wakeup(&head->sync_tid);
 306
 307                 if (hammer2_synchronous_flush > 0)
 308                         scan = head;
 309                 else
 310                         scan = TAILQ_NEXT(head, entry);
 311                 while (scan && (scan->flags & HAMMER2_TRANS_ISFLUSH) == 0) {
 312                         if (scan->blocked) {
 313                                 scan->blocked = 0;
 314                                 wakeup(&scan->sync_tid);
 315                         }
 316                         scan = TAILQ_NEXT(scan, entry);
 317                 }
 318         }
 319         hammer2_voldata_unlock(hmp, 0);
 320 }
 321
 322 /*
 323  * Flush the chain and all modified sub-chains through the specified
 324  * synchronization point (sync_tid), propagating parent chain modifications
 325  * and mirror_tid updates back up as needed.  Since we are recursing downward
 326  * we do not have to deal with the complexities of multi-homed chains (chains
 327  * with multiple parents).
 328  *
 329  * Caller must have interlocked against any non-flush-related modifying
 330  * operations in progress whos modify_tid values are less than or equal
 331  * to the passed sync_tid.
 332  *
 333  * Caller must have already vetted synchronization points to ensure they
 334  * are properly flushed.  Only snapshots and cluster flushes can create
 335  * these sorts of synchronization points.
 336  *
 337  * This routine can be called from several places but the most important
 338  * is from VFS_SYNC.
 339  *
 340  * chain is locked on call and will remain locked on return.  If a flush
 341  * occured, the chain's FLUSH_CREATE and/or FLUSH_DELETE bit will be set
 342  * indicating that its parent (which is not part of the flush) should be
 343  * updated.  The chain may be replaced by the call if it was modified.
 344  */
 345 void
 346 hammer2_flush(hammer2_trans_t *trans, hammer2_chain_t **chainp)
 347 {
 348         hammer2_chain_t *chain = *chainp;
 349         hammer2_chain_t *scan;
 350         hammer2_chain_core_t *core;
 351         hammer2_flush_info_t info;
 352         int loops;
 353
 354         /*
 355          * Execute the recursive flush and handle deferrals.
 356          *
 357          * Chains can be ridiculously long (thousands deep), so to
 358          * avoid blowing out the kernel stack the recursive flush has a
 359          * depth limit.  Elements at the limit are placed on a list
 360          * for re-execution after the stack has been popped.
 361          */
 362         bzero(&info, sizeof(info));
 363         TAILQ_INIT(&info.flush_list);
 364         info.trans = trans;
 365         info.sync_tid = trans->sync_tid;
 366         info.cache_index = -1;
 367
 368         core = chain->core;
 369
 370         /*
 371          * Extra ref needed because flush_core expects it when replacing
 372          * chain.
 373          */
 374         hammer2_chain_ref(chain);
 375         loops = 0;
 376
 377         for (;;) {
 378                 /*
 379                  * Unwind deep recursions which had been deferred.  This
 380                  * can leave the FLUSH_* bits set for these chains, which
 381                  * will be handled when we [re]flush chain after the unwind.
 382                  */
 383                 while ((scan = TAILQ_FIRST(&info.flush_list)) != NULL) {
 384                         KKASSERT(scan->flags & HAMMER2_CHAIN_DEFERRED);
 385                         TAILQ_REMOVE(&info.flush_list, scan, flush_node);
 386                         atomic_clear_int(&scan->flags, HAMMER2_CHAIN_DEFERRED);
 387
 388                         /*
 389                          * Now that we've popped back up we can do a secondary
 390                          * recursion on the deferred elements.
 391                          *
 392                          * NOTE: hammer2_flush() may replace scan.
 393                          */
 394                         if (hammer2_debug & 0x0040)
 395                                 kprintf("deferred flush %p\n", scan);
 396                         hammer2_chain_lock(scan, HAMMER2_RESOLVE_MAYBE);
 397                         hammer2_chain_drop(scan);       /* ref from deferral */
 398                         hammer2_flush(trans, &scan);
 399                         hammer2_chain_unlock(scan);
 400                 }
 401
 402                 /*
 403                  * [re]flush chain.
 404                  */
 405                 info.diddeferral = 0;
 406                 hammer2_flush_core(&info, &chain, 0);
 407
 408                 /*
 409                  * Only loop if deep recursions have been deferred.
 410                  */
 411                 if (TAILQ_EMPTY(&info.flush_list))
 412                         break;
 413
 414                 if (++loops % 1000 == 0) {
 415                         kprintf("hammer2_flush: excessive loops on %p\n",
 416                                 chain);
 417                         if (hammer2_debug & 0x100000)
 418                                 Debugger("hell4");
 419                 }
 420         }
 421         hammer2_chain_drop(chain);
 422         *chainp = chain;
 423 }
 424
 425 /*
 426  * This is the core of the chain flushing code.  The chain is locked by the
 427  * caller and must also have an extra ref on it by the caller, and remains
 428  * locked and will have an extra ref on return.  Upon return, the caller can
 429  * test the FLUSH_CREATE and FLUSH_DELETE bits to determine what action must
 430  * be taken on the parent.
 431  *
 432  * (1) Determine if this node is a candidate for the flush, return if it is
 433  *     not.  fchain and vchain are always candidates for the flush.
 434  *
 435  * (2) If we recurse too deep the chain is entered onto the deferral list and
 436  *     the current flush stack is aborted until after the deferral list is
 437  *     run.
 438  *
 439  * (3) Recursively flush live children (rbtree).  This can create deferrals.
 440  *     A successful flush clears the MODIFIED bit in the children.
 441  *
 442  * (4) Recursively flush deleted children (dbtree).  Deletions may be
 443  *     considered 'live' if the delete_tid is beyond the flush_tid.  If
 444  *     considered 'dead' the recursion is still needed in order to clean
 445  *     up the chain.  This can create deferrals.
 446  *
 447  *     A successful flush clears the MODIFIED bit in the children.
 448  *
 449  * (5) Calculate block table updates on chain based on the children scans
 450  *     in (3) and (4) by testing the FLUSH_CREATE and FLUSH_DELETE bits,
 451  *     modifying chain if necessary to perform the block table updates.
 452  *     Deletions must be removed from dbtree when removed from the
 453  *     chain's block table.
 454  *
 455  *     If 'chain' itself is marked DELETED but treated as live, the block
 456  *     table update(s) must be propagated to all contemporary chains.  In
 457  *     fact, all contemporary chains must be locked and updated uninterrupted
 458  *     to avoid lookup races.  Once MODIFIED and FLUSH_CREATE is cleared,
 459  *     a chain can be unloaded from memory with the expectation that it can
 460  *     be reloaded later via the block table at any time.
 461  *
 462  * NOTE: chain->bref.modify_tid is different from chain->modify_tid.  COW
 463  *       propagations for block updates do not update chain->bref.modify_tid,
 464  *       only chain->bref.mirror_tid.  The MODIFIED bit is set on any
 465  *       modified chain, including COW propagations, but the flusher normally
 466  *       just keys off of the FLUSH_* bits.  FLUSH_CREATE will also be set
 467  *       in this situation.
 468  *
 469  * NOTE: We are responsible for updating chain->bref.mirror_tid and
 470  *       chain->update_lo.  The caller is responsible for processing us into
 471  *       our parent (if any).
 472  */
 473 static void
 474 hammer2_flush_core(hammer2_flush_info_t *info, hammer2_chain_t **chainp,
 475                    int deleting)
 476 {
 477         hammer2_chain_t *chain = *chainp;
 478         hammer2_chain_t *saved_parent;
 479         hammer2_mount_t *hmp;
 480         hammer2_chain_core_t *core;
 481         int diddeferral;
 482         int saved_domodify;
 483
 484         hmp = chain->hmp;
 485         core = chain->core;
 486         diddeferral = info->diddeferral;
 487
 488         /*
 489          * (1) Check if we even have any work to do.
 490          *
 491          * This bit of code is capable of short-cutting entire sub-trees
 492          * if they have not been touched or if they have already been
 493          * flushed.
 494          */
 495         if (/*(chain->flags & HAMMER2_CHAIN_MODIFIED) == 0 &&*/
 496             (chain->update_lo >= info->sync_tid ||      /* already synced */
 497              chain->update_lo >= chain->update_hi)) {   /* old/unchanged */
 498                 /* update_lo/_hi already filters chain out, do not update */
 499                 /* don't update bref.mirror_tid, pass2 is not called */
 500                 return;
 501         }
 502
 503         /*
 504          * mirror_tid should not be forward-indexed
 505          */
 506         KKASSERT(chain->bref.mirror_tid <= info->sync_tid);
 507
 508         /*
 509          * Ignore chains modified beyond the current flush point.  These
 510          * will be treated as if they did not exist.  Subchains with lower
 511          * modify_tid's will still be accessible via other parents.
 512          *
 513          * Do not update bref.mirror_tid here, it will interfere with
 514          * synchronization.  e.g. inode flush tid 1, concurrent D-D tid 2,
 515          * then later on inode flush tid 2.  If we were to set mirror_tid
 516          * to 1 during inode flush tid 1 the blockrefs would only be partially
 517          * updated (and likely panic).
 518          *
 519          * We must update chain->update_lo here to prevent re-entry in this
 520          * flush transaction.
 521          *
 522          * (vchain and fchain are exceptions since they cannot be duplicated)
 523          */
 524         if (chain->modify_tid > info->sync_tid &&
 525             chain != &hmp->fchain && chain != &hmp->vchain) {
 526                 /* do not update bref.mirror_tid, pass2 ignores chain */
 527                 /* chain->update_lo = info->sync_tid; */
 528                 return;
 529         }
 530
 531         /*
 532          * (2) Recurse downward and check recursion depth.
 533          * (3) Flush live children
 534          * (4) Flush deleted children
 535          *
 536          * We adjust update_lo if not deferring chain to prevent re-entry
 537          * in this flush cycle, but it must be set AFTER the flush in case
 538          * a deeper flush hits the chain.  Otherwise the deeper flush cannot
 539          * complete.  We re-check the condition after finishing the flushes.
 540          *
 541          * update_hi was already checked and prevents initial recursions on
 542          * subtrees which have not been modified.
 543          */
 544         saved_parent = info->parent;
 545         saved_domodify = info->domodify;
 546         info->parent = chain;
 547         info->domodify = 0;
 548
 549         if (chain->flags & HAMMER2_CHAIN_DEFERRED) {
 550                 ++info->diddeferral;
 551         } else if (info->depth == HAMMER2_FLUSH_DEPTH_LIMIT) {
 552                 if ((chain->flags & HAMMER2_CHAIN_DEFERRED) == 0) {
 553                         hammer2_chain_ref(chain);
 554                         TAILQ_INSERT_TAIL(&info->flush_list,
 555                                           chain, flush_node);
 556                         atomic_set_int(&chain->flags,
 557                                        HAMMER2_CHAIN_DEFERRED);
 558                 }
 559                 ++info->diddeferral;
 560         } else {
 561                 hammer2_chain_t *scan;
 562
 563                 /*
 564                  * The flush is queue-agnostic when running pass1, but order
 565                  * is important to catch any races where an existing
 566                  * flush-visible child is moved from rbtree->dbtree/dbq.
 567                  *
 568                  * New children added by concurrent operations are not visible
 569                  * to the flush anyway so we don't care about those races.
 570                  * However, the flush itself can move a child from dbq to
 571                  * dbtree (rare in pass1 but it is possible).
 572                  *
 573                  * pass1 can handle re-execution of a child.
 574                  */
 575                 spin_lock(&core->cst.spin);
 576                 KKASSERT(core->good == 0x1234 && core->sharecnt > 0);
 577                 RB_SCAN(hammer2_chain_tree, &core->rbtree,
 578                         NULL, hammer2_flush_pass1, info);
 579                 RB_SCAN(hammer2_chain_tree, &core->dbtree,
 580                         NULL, hammer2_flush_pass1, info);
 581                 scan = TAILQ_FIRST(&core->dbq);
 582                 while (scan) {
 583                         KKASSERT(scan->flags & HAMMER2_CHAIN_ONDBQ);
 584                         hammer2_flush_pass1(scan, info);
 585                         if (scan->flags & HAMMER2_CHAIN_ONDBQ)
 586                                 scan = TAILQ_NEXT(scan, db_entry);
 587                         else
 588                                 scan = TAILQ_FIRST(&core->dbq);
 589                 }
 590                 spin_unlock(&core->cst.spin);
 591         }
 592
 593         /*
 594          * Stop if deferred, do not update update_lo.
 595          */
 596         if (info->diddeferral)
 597                 goto done;
 598
 599         /*
 600          * If a block table update is needed place the parent in a modified
 601          * state, which might delete-duplicate it.
 602          *
 603          * - To prevent loops and other confusion, we synchronize update_lo
 604          *   for the original chain.
 605          *
 606          * - The original parent will not be used by the flush so we can
 607          *   clear its MODIFIED bit.
 608          */
 609         if (info->domodify) {
 610                 hammer2_chain_modify(info->trans, &info->parent,
 611                                      HAMMER2_MODIFY_NO_MODIFY_TID);
 612                 if (info->parent != chain) {
 613                         /*
 614                          * chain        - old
 615                          * info->parent - new
 616                          *
 617                          * NOTE: bref.mirror_tid cannot be updated
 618                          *       unless MODIFIED is cleared or already
 619                          *       clear.
 620                          */
 621                         chain->inode_reason += 0x10000000;
 622                         info->parent->inode_reason += 0x100;
 623                         KKASSERT(info->parent->core == chain->core);
 624                         if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
 625                                 atomic_clear_int(&chain->flags,
 626                                                 HAMMER2_CHAIN_MODIFIED);
 627                                 hammer2_chain_memory_wakeup(chain->pmp);
 628                                 hammer2_chain_drop(chain);
 629                         }
 630 #if 0
 631                         if (chain->flags & HAMMER2_CHAIN_FLUSH_CREATE) {
 632                                 atomic_clear_int(&chain->flags,
 633                                                 HAMMER2_CHAIN_FLUSH_CREATE);
 634                                 hammer2_chain_drop(chain);
 635                         }
 636                         if (info->parent->flags & HAMMER2_CHAIN_FLUSH_DELETE) {
 637                                 atomic_clear_int(&info->parent->flags,
 638                                                 HAMMER2_CHAIN_FLUSH_DELETE);
 639                                 hammer2_chain_drop(info->parent);
 640                         }
 641 #endif
 642 #if 0
 643                         if (chain->bref.mirror_tid < info->sync_tid)
 644                                 chain->bref.mirror_tid = info->sync_tid;
 645 #endif
 646                         if (chain->update_lo < info->sync_tid)
 647                                 chain->update_lo = info->sync_tid;
 648                         KKASSERT(info->parent->update_lo < info->sync_tid);
 649                         hammer2_chain_drop(chain);
 650                         hammer2_chain_ref(info->parent);
 651                 }
 652                 chain = info->parent;
 653         }
 654
 655         /*
 656          * If a blocktable update is needed determine if this is the last
 657          * parent requiring modification (check all parents using the core).
 658          *
 659          * Set bit 1 (0x02) of domodify if this is the last parent,
 660          * which will cause scan2 to clear FLUSH_CREATE and FLUSH_DELETE.
 661          */
 662         if (1) {
 663                 hammer2_chain_t *scan;
 664
 665                 spin_lock(&core->cst.spin);
 666                 TAILQ_FOREACH(scan, &core->ownerq, core_entry) {
 667                         /*
 668                          * Ignore chains which have already been updated
 669                          * Ignore unmodified chains
 670                          */
 671                         if ((scan->flags & HAMMER2_CHAIN_MODIFIED) == 0 &&
 672                             (scan->update_lo >= info->sync_tid ||
 673                              scan->update_lo >= scan->update_hi)) {
 674                                 continue;
 675                         }
 676
 677                         /*
 678                          * Ignore the current parent being processed (we do
 679                          * not adjust update_lo until after the fixup).
 680                          */
 681                         if (scan == chain)
 682                                 continue;
 683
 684                         /*
 685                          * Cannot exhaust all parents if one is not visible
 686                          * to the flush.  The root chains are special-cased
 687                          * because they cannot really be delete-duplicated.
 688                          */
 689                         if (scan != &scan->hmp->fchain &&
 690                             scan != &scan->hmp->vchain &&
 691                             scan->modify_tid > info->sync_tid) {
 692                                 break;
 693                         }
 694
 695                         /*
 696                          * Fail if update_lo has not been synchronized to
 697                          * at least our sync_tid on any modified parent chain.
 698                          */
 699                         if (scan->update_lo < info->sync_tid)
 700                                 break;
 701                 }
 702                 spin_unlock(&core->cst.spin);
 703                 if (scan == NULL)
 704                         info->domodify |= 2;
 705         }
 706
 707         /*
 708          * (5) Calculate block table updates or child cleanups.
 709          *     (this whole operation has to be atomic)
 710          *
 711          * domodify 0x01 - block table updates
 712          *          0x02 - child cleanups
 713          *
 714          *      pass2 - Process deletions from dbtree and dbq.
 715          *      pass3 - Process insertions from rbtree, dbtree, and dbq.
 716          *      pass4 - Cleanup child flags on the last parent and
 717          *              Adjust queues on the live parent (deletions).
 718          *      pass5 - Cleanup child flags on the last parent and
 719          *              Adjust queues on the live parent (insertions).
 720          *
 721          *      Queue adjustments had to be separated into deletions and
 722          *      insertions because both can occur on dbtree.
 723          */
 724         if (info->domodify) {
 725                 hammer2_chain_t *scan;
 726
 727                 spin_lock(&core->cst.spin);
 728
 729                 while ((info->domodify & 1) && info->parent) {
 730                         /* PASS2 - Deletions */
 731                         RB_SCAN(hammer2_chain_tree, &core->rbtree,
 732                                 NULL, hammer2_flush_pass2, info);
 733                         RB_SCAN(hammer2_chain_tree, &core->dbtree,
 734                                 NULL, hammer2_flush_pass2, info);
 735                         scan = TAILQ_FIRST(&core->dbq);
 736                         TAILQ_FOREACH(scan, &core->dbq, db_entry) {
 737                                 KKASSERT(scan->flags & HAMMER2_CHAIN_ONDBQ);
 738                                 hammer2_flush_pass2(scan, info);
 739                         }
 740
 741                         /* PASS3 - Insertions */
 742                         RB_SCAN(hammer2_chain_tree, &core->rbtree,
 743                                 NULL, hammer2_flush_pass3, info);
 744                         RB_SCAN(hammer2_chain_tree, &core->dbtree,
 745                                 NULL, hammer2_flush_pass3, info);
 746                         TAILQ_FOREACH(scan, &core->dbq, db_entry) {
 747                                 KKASSERT(scan->flags & HAMMER2_CHAIN_ONDBQ);
 748                                 hammer2_flush_pass3(scan, info);
 749                         }
 750                         info->parent = TAILQ_NEXT(info->parent, core_entry);
 751                         if (info->parent)
 752                                 kprintf("FLUSH SPECIAL UPDATE (%p) %p.%d %08x\n",
 753                                         chain, info->parent,
 754                                         info->parent->bref.type,
 755                                         info->parent->flags);
 756                 }
 757                 info->parent = chain;
 758
 759                 /* PASS4 - Cleanup */
 760                 RB_SCAN(hammer2_chain_tree, &core->rbtree,
 761                         NULL, hammer2_flush_pass4, info);
 762                 scan = TAILQ_FIRST(&core->dbq);
 763                 while (scan) {
 764                         KKASSERT(scan->flags & HAMMER2_CHAIN_ONDBQ);
 765                         hammer2_flush_pass4(scan, info);
 766                         if (scan->flags & HAMMER2_CHAIN_ONDBQ)
 767                                 scan = TAILQ_NEXT(scan, db_entry);
 768                         else
 769                                 scan = TAILQ_FIRST(&core->dbq);
 770                 }
 771                 RB_SCAN(hammer2_chain_tree, &core->dbtree,
 772                         NULL, hammer2_flush_pass4, info);
 773
 774                 /* PASS5 - Cleanup */
 775                 RB_SCAN(hammer2_chain_tree, &core->rbtree,
 776                         NULL, hammer2_flush_pass5, info);
 777                 scan = TAILQ_FIRST(&core->dbq);
 778                 while (scan) {
 779                         KKASSERT(scan->flags & HAMMER2_CHAIN_ONDBQ);
 780                         hammer2_flush_pass5(scan, info);
 781                         if (scan->flags & HAMMER2_CHAIN_ONDBQ)
 782                                 scan = TAILQ_NEXT(scan, db_entry);
 783                         else
 784                                 scan = TAILQ_FIRST(&core->dbq);
 785                 }
 786                 RB_SCAN(hammer2_chain_tree, &core->dbtree,
 787                         NULL, hammer2_flush_pass5, info);
 788
 789                 spin_unlock(&core->cst.spin);
 790         }
 791
 792         /*
 793          * Synchronize update_lo to prevent reentrant block updates of this
 794          * parent.
 795          */
 796         chain->update_lo = info->sync_tid;
 797
 798         /*
 799          * Skip the flush if the chain was not placed in a modified state
 800          * or was not already in a modified state.
 801          */
 802         if ((chain->flags & HAMMER2_CHAIN_MODIFIED) == 0)
 803                 goto done;
 804
 805         /*
 806          * FLUSH THE CHAIN (on the way back up the recursion)
 807          *
 808          * Chain is now deterministically being flushed and not being deferred.
 809          * We've finished running the recursion and the blockref update.
 810          *
 811          * update bref.mirror_tid.  update_lo has already been updated.
 812          */
 813         if (chain->bref.mirror_tid < info->sync_tid)
 814                 chain->bref.mirror_tid = info->sync_tid;
 815
 816         /*
 817          * Dispose of the modified bit.  FLUSH_CREATE should already be
 818          * set.
 819          */
 820         KKASSERT(chain->flags & HAMMER2_CHAIN_FLUSH_CREATE);
 821         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
 822         hammer2_chain_memory_wakeup(chain->pmp);
 823
 824         if ((chain->flags & HAMMER2_CHAIN_FLUSH_CREATE) ||
 825             chain == &hmp->vchain ||
 826             chain == &hmp->fchain) {
 827                 /*
 828                  * Drop the ref from the MODIFIED bit we cleared,
 829                  * net -1 ref.
 830                  */
 831                 hammer2_chain_drop(chain);
 832         } else {
 833                 /*
 834                  * Drop the ref from the MODIFIED bit we cleared and
 835                  * set a ref for the FLUSH_CREATE bit we are setting.
 836                  * Net 0 refs.
 837                  */
 838                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_FLUSH_CREATE);
 839         }
 840
 841         /*
 842          * Skip the actual flush operation if the chain has been deleted
 843          * in our flus hview.  There will be no block table entry that
 844          * references it.
 845          */
 846         if (h2ignore_deleted(info, chain))
 847                 goto done;
 848
 849         /*
 850          * Issue flush.
 851          *
 852          * A DELETED node that reaches this point must be flushed for
 853          * synchronization point consistency.
 854          *
 855          * Update bref.mirror_tid, clear MODIFIED, and set MOVED.
 856          *
 857          * The caller will update the parent's reference to this chain
 858          * by testing MOVED as long as the modification was in-bounds.
 859          *
 860          * MOVED is never set on the volume root as there is no parent
 861          * to adjust.
 862          */
 863         if (hammer2_debug & 0x1000) {
 864                 kprintf("Flush %p.%d %016jx/%d sync_tid=%016jx data=%016jx\n",
 865                         chain, chain->bref.type,
 866                         chain->bref.key, chain->bref.keybits,
 867                         info->sync_tid, chain->bref.data_off);
 868         }
 869         if (hammer2_debug & 0x2000) {
 870                 Debugger("Flush hell");
 871         }
 872
 873         /*
 874          * If this is part of a recursive flush we can go ahead and write
 875          * out the buffer cache buffer and pass a new bref back up the chain
 876          * via the MOVED bit.
 877          *
 878          * Volume headers are NOT flushed here as they require special
 879          * processing.
 880          */
 881         switch(chain->bref.type) {
 882         case HAMMER2_BREF_TYPE_FREEMAP:
 883                 hammer2_modify_volume(hmp);
 884                 hmp->voldata.freemap_tid = hmp->fchain.bref.mirror_tid;
 885                 break;
 886         case HAMMER2_BREF_TYPE_VOLUME:
 887                 /*
 888                  * The free block table is flushed by hammer2_vfs_sync()
 889                  * before it flushes vchain.  We must still hold fchain
 890                  * locked while copying voldata to volsync, however.
 891                  */
 892                 hammer2_chain_lock(&hmp->fchain, HAMMER2_RESOLVE_ALWAYS);
 893 #if 0
 894                 if ((hmp->fchain.flags & HAMMER2_CHAIN_MODIFIED) ||
 895                     hmp->voldata.freemap_tid < info->trans->sync_tid) {
 896                         /* this will modify vchain as a side effect */
 897                         hammer2_chain_t *tmp = &hmp->fchain;
 898                         hammer2_chain_flush(info->trans, &tmp);
 899                         KKASSERT(tmp == &hmp->fchain);
 900                 }
 901 #endif
 902
 903                 /*
 904                  * There is no parent to our root vchain and fchain to
 905                  * synchronize the bref to, their updated mirror_tid's
 906                  * must be synchronized to the volume header.
 907                  */
 908                 hmp->voldata.mirror_tid = chain->bref.mirror_tid;
 909                 /*hmp->voldata.freemap_tid = hmp->fchain.bref.mirror_tid;*/
 910
 911                 /*
 912                  * The volume header is flushed manually by the syncer, not
 913                  * here.  All we do here is adjust the crc's.
 914                  */
 915                 KKASSERT(chain->data != NULL);
 916                 KKASSERT(chain->dio == NULL);
 917
 918                 hmp->voldata.icrc_sects[HAMMER2_VOL_ICRC_SECT1]=
 919                         hammer2_icrc32(
 920                                 (char *)&hmp->voldata +
 921                                  HAMMER2_VOLUME_ICRC1_OFF,
 922                                 HAMMER2_VOLUME_ICRC1_SIZE);
 923                 hmp->voldata.icrc_sects[HAMMER2_VOL_ICRC_SECT0]=
 924                         hammer2_icrc32(
 925                                 (char *)&hmp->voldata +
 926                                  HAMMER2_VOLUME_ICRC0_OFF,
 927                                 HAMMER2_VOLUME_ICRC0_SIZE);
 928                 hmp->voldata.icrc_volheader =
 929                         hammer2_icrc32(
 930                                 (char *)&hmp->voldata +
 931                                  HAMMER2_VOLUME_ICRCVH_OFF,
 932                                 HAMMER2_VOLUME_ICRCVH_SIZE);
 933                 hmp->volsync = hmp->voldata;
 934                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_VOLUMESYNC);
 935                 hammer2_chain_unlock(&hmp->fchain);
 936                 break;
 937         case HAMMER2_BREF_TYPE_DATA:
 938                 /*
 939                  * Data elements have already been flushed via the logical
 940                  * file buffer cache.  Their hash was set in the bref by
 941                  * the vop_write code.
 942                  *
 943                  * Make sure any device buffer(s) have been flushed out here.
 944                  * (there aren't usually any to flush).
 945                  */
 946                 break;
 947 #if 0
 948         case HAMMER2_BREF_TYPE_INDIRECT:
 949                 /*
 950                  * Indirect blocks may be in an INITIAL state.  Use the
 951                  * chain_lock() call to ensure that the buffer has been
 952                  * instantiated (even though it is already locked the buffer
 953                  * might not have been instantiated).
 954                  *
 955                  * Only write the buffer out if it is dirty, it is possible
 956                  * the operating system had already written out the buffer.
 957                  */
 958                 hammer2_chain_lock(chain, HAMMER2_RESOLVE_ALWAYS);
 959                 KKASSERT(chain->dio != NULL);
 960
 961                 chain->data = NULL;
 962                 hammer2_io_bqrelse(&chain->dio);
 963                 hammer2_chain_unlock(chain);
 964                 break;
 965 #endif
 966         case HAMMER2_BREF_TYPE_INDIRECT:
 967         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
 968         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
 969         case HAMMER2_BREF_TYPE_INODE:
 970                 /*
 971                  * Device-backed.  Buffer will be flushed by the sync
 972                  * code XXX.
 973                  */
 974                 KKASSERT((chain->flags & HAMMER2_CHAIN_EMBEDDED) == 0);
 975                 break;
 976         default:
 977                 KKASSERT(chain->flags & HAMMER2_CHAIN_EMBEDDED);
 978                 panic("hammer2_chain_flush_core: unsupported embedded bref %d",
 979                       chain->bref.type);
 980                 /* NOT REACHED */
 981         }
 982
 983         /*
 984          * Final cleanup after flush
 985          */
 986 done:
 987         KKASSERT(chain->refs > 1);
 988         info->domodify = saved_domodify;
 989         info->parent = saved_parent;
 990         *chainp = chain;
 991
 992         KKASSERT(chain->bref.mirror_tid <= info->sync_tid);
 993 }
 994
 995 /*
 996  * Flush helper pass1 (recursive)
 997  *
 998  * Flushes the children of the caller's chain (info->parent), restricted
 999  * by sync_tid.  Set info->domodify if the child's blockref must propagate
1000  * back up to the parent.
1001  *
1002  * Ripouts can move child from rbtree to dbtree or dbq but the caller's
1003  * flush scan order prevents any chains from being lost.  A child can be
1004  * executes more than once (update_lo is used to prevent infinite recursions).
1005  *
1006  * WARNING! If we do not call hammer2_flush_core() we must update
1007  *          bref.mirror_tid ourselves to indicate that the flush has
1008  *          processed the child.
1009  *
1010  * WARNING! parent->core spinlock is held on entry and return.
1011  */
1012 static int
1013 hammer2_flush_pass1(hammer2_chain_t *child, void *data)
1014 {
1015         hammer2_flush_info_t *info = data;
1016         hammer2_trans_t *trans = info->trans;
1017         hammer2_chain_t *parent = info->parent;
1018
1019         /*
1020          * Child modified in a later transactions, nothing to flush in this
1021          * transaction.
1022          *
1023          * Remember that modifications generally delete-duplicate so if the
1024          * sub-tree is dirty another child will get us there.  But not this
1025          * one.
1026          *
1027          * (child can never be fchain or vchain so a special check isn't
1028          *  needed).
1029          */
1030         if (child->modify_tid > trans->sync_tid) {
1031                 KKASSERT(child->delete_tid >= child->modify_tid);
1032                 /*child->update_lo = info->sync_tid;*/
1033                 /* do not update mirror_tid, pass2 will ignore chain */
1034                 return (0);
1035         }
1036
1037         /*
1038          * We must ref the child before unlocking the spinlock.
1039          *
1040          * The caller has added a ref to the parent so we can temporarily
1041          * unlock it in order to lock the child.
1042          */
1043         hammer2_chain_ref(child);
1044         spin_unlock(&parent->core->cst.spin);
1045
1046         hammer2_chain_unlock(parent);
1047         hammer2_chain_lock(child, HAMMER2_RESOLVE_MAYBE);
1048
1049         /*
1050          * Recurse and collect deferral data.  We only recursively sync
1051          * (basically) if update_lo has not been updated, indicating that
1052          * the child has not already been processed.
1053          */
1054         if ((child->flags & HAMMER2_CHAIN_MODIFIED) ||
1055             (child->update_lo < info->sync_tid &&
1056              child->update_lo < child->update_hi)) {
1057                 ++info->depth;
1058                 hammer2_flush_core(info, &child, 0); /* XXX deleting */
1059                 --info->depth;
1060         }
1061
1062         /*
1063          * Determine if domodify should be set.  Do not otherwise adjust
1064          * the child or pass2 will get confused.
1065          *
1066          * Insertion:
1067          *      - child is flagged as possibly needing block table insertion.
1068          *      - child not deleted or deletion is beyond transaction id
1069          *      - child created beyond parent synchronization point
1070          *      - parent not deleted as-of this transaction
1071          */
1072         if ((child->flags & HAMMER2_CHAIN_FLUSH_CREATE) &&
1073             child->delete_tid > trans->sync_tid &&
1074             child->modify_tid > parent->update_lo &&
1075             parent->delete_tid > trans->sync_tid) {
1076                 info->domodify = 1;
1077         }
1078
1079         /*
1080          * Removal:
1081          *      - child is flagged as possibly needing block table removal.
1082          *      - child deleted before or during this transaction
1083          *      - child created prior or during parent synchronization point
1084          *      - parent not yet synchronized to child deletion
1085          *      - parent not deleted as-of this transaction
1086          */
1087         if ((child->flags & HAMMER2_CHAIN_FLUSH_DELETE) &&
1088             child->delete_tid <= trans->sync_tid &&
1089             child->modify_tid <= parent->update_lo &&
1090             child->delete_tid > parent->update_lo &&
1091             parent->delete_tid > trans->sync_tid) {
1092                 info->domodify = 1;
1093         }
1094
1095         /*
1096          * Relock to continue the loop
1097          */
1098         hammer2_chain_unlock(child);
1099         hammer2_chain_lock(parent, HAMMER2_RESOLVE_MAYBE);
1100         hammer2_chain_drop(child);
1101         KKASSERT(info->parent == parent);
1102
1103         spin_lock(&parent->core->cst.spin);
1104         return (0);
1105 }
1106
1107 /*
1108  * PASS2 - BLOCKTABLE DELETIONS
1109  */
1110 static int
1111 hammer2_flush_pass2(hammer2_chain_t *child, void *data)
1112 {
1113         hammer2_flush_info_t *info = data;
1114         hammer2_chain_t *parent = info->parent;
1115         hammer2_mount_t *hmp = child->hmp;
1116         hammer2_trans_t *trans = info->trans;
1117         hammer2_blockref_t *base;
1118         int count;
1119
1120         /*
1121          * Prefilter - Ignore children not flagged as needing a parent
1122          *             blocktable update.
1123          */
1124         if ((child->flags & HAMMER2_CHAIN_FLUSH_DELETE) == 0)
1125                 return (0);
1126
1127         /*
1128          * Prefilter - Ignore children created after our flush_tid (not
1129          *             visible to our flush).
1130          */
1131         if (child->modify_tid > trans->sync_tid) {
1132                 KKASSERT(child->delete_tid >= child->modify_tid);
1133                 return 0;
1134         }
1135
1136         /*
1137          * Prefilter - Don't bother updating the blockrefs for a deleted
1138          *             parent (from the flush's perspective).  Otherwise,
1139          *             we need to be COUNTEDBREFS synchronized for the
1140          *             hammer2_base_*() functions.
1141          *
1142          * NOTE: This test must match the similar one in flush_core.
1143          */
1144         if (h2ignore_deleted(info, parent))
1145                 return 0;
1146
1147         /*
1148          * Calculate blockmap pointer
1149          */
1150         switch(parent->bref.type) {
1151         case HAMMER2_BREF_TYPE_INODE:
1152                 /*
1153                  * Access the inode's block array.  However, there is no
1154                  * block array if the inode is flagged DIRECTDATA.  The
1155                  * DIRECTDATA case typicaly only occurs when a hardlink has
1156                  * been shifted up the tree and the original inode gets
1157                  * replaced with an OBJTYPE_HARDLINK placeholding inode.
1158                  */
1159                 if (parent->data &&
1160                     (parent->data->ipdata.op_flags &
1161                      HAMMER2_OPFLAG_DIRECTDATA) == 0) {
1162                         base = &parent->data->ipdata.u.blockset.blockref[0];
1163                 } else {
1164                         base = NULL;
1165                 }
1166                 count = HAMMER2_SET_COUNT;
1167                 break;
1168         case HAMMER2_BREF_TYPE_INDIRECT:
1169         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1170                 if (parent->data)
1171                         base = &parent->data->npdata[0];
1172                 else
1173                         base = NULL;
1174                 count = parent->bytes / sizeof(hammer2_blockref_t);
1175                 break;
1176         case HAMMER2_BREF_TYPE_VOLUME:
1177                 base = &hmp->voldata.sroot_blockset.blockref[0];
1178                 count = HAMMER2_SET_COUNT;
1179                 break;
1180         case HAMMER2_BREF_TYPE_FREEMAP:
1181                 base = &parent->data->npdata[0];
1182                 count = HAMMER2_SET_COUNT;
1183                 break;
1184         default:
1185                 base = NULL;
1186                 count = 0;
1187                 panic("hammer2_chain_flush_pass2: "
1188                       "unrecognized blockref type: %d",
1189                       parent->bref.type);
1190         }
1191
1192         /*
1193          * Removal
1194          *      - child is flagged for removal
1195          *      - child deleted before or during this transaction
1196          *      - child created prior or during parent synchronization point
1197          *      - parent not yet synchronized to child's deletion
1198          */
1199         if (child->delete_tid <= trans->sync_tid &&
1200             child->modify_tid <= parent->update_lo &&
1201             child->delete_tid > parent->update_lo) {
1202                 /* can't assert BMAPPED because state adjustment may occur
1203                  * before we are done, and BMAPPED only applies to the live
1204                  * parent.
1205                  *KKASSERT(child->flags & HAMMER2_CHAIN_BMAPPED);*/
1206                 if (base) {
1207                         hammer2_rollup_stats(parent, child, -1);
1208                         hammer2_base_delete(trans, parent, base, count,
1209                                             &info->cache_index, child);
1210                 }
1211         }
1212
1213         return 0;
1214 }
1215
1216 /*
1217  * PASS3 - BLOCKTABLE INSERTIONS
1218  */
1219 static int
1220 hammer2_flush_pass3(hammer2_chain_t *child, void *data)
1221 {
1222         hammer2_flush_info_t *info = data;
1223         hammer2_chain_t *parent = info->parent;
1224         hammer2_mount_t *hmp = child->hmp;
1225         hammer2_trans_t *trans = info->trans;
1226         hammer2_blockref_t *base;
1227         int count;
1228
1229         /*
1230          * Prefilter - Ignore children not flagged as needing a parent
1231          *             blocktable update.
1232          */
1233         if ((child->flags & HAMMER2_CHAIN_FLUSH_CREATE) == 0)
1234                 return (0);
1235
1236         /*
1237          * Prefilter - Ignore children created after our flush_tid (not
1238          *             visible to our flush).
1239          */
1240         if (child->modify_tid > trans->sync_tid) {
1241                 KKASSERT(child->delete_tid >= child->modify_tid);
1242                 return 0;
1243         }
1244
1245         /*
1246          * Prefilter - Don't bother updating the blockrefs for a deleted
1247          *             parent (from the flush's perspective).  Otherwise,
1248          *             we need to be COUNTEDBREFS synchronized for the
1249          *             hammer2_base_*() functions.
1250          *
1251          * NOTE: This test must match the similar one in flush_core.
1252          */
1253         if (h2ignore_deleted(info, parent))
1254                 return 0;
1255
1256         /*
1257          * Calculate blockmap pointer
1258          */
1259         switch(parent->bref.type) {
1260         case HAMMER2_BREF_TYPE_INODE:
1261                 /*
1262                  * Access the inode's block array.  However, there is no
1263                  * block array if the inode is flagged DIRECTDATA.  The
1264                  * DIRECTDATA case typicaly only occurs when a hardlink has
1265                  * been shifted up the tree and the original inode gets
1266                  * replaced with an OBJTYPE_HARDLINK placeholding inode.
1267                  */
1268                 if (parent->data &&
1269                     (parent->data->ipdata.op_flags &
1270                      HAMMER2_OPFLAG_DIRECTDATA) == 0) {
1271                         base = &parent->data->ipdata.u.blockset.blockref[0];
1272                 } else {
1273                         base = NULL;
1274                 }
1275                 count = HAMMER2_SET_COUNT;
1276                 break;
1277         case HAMMER2_BREF_TYPE_INDIRECT:
1278         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1279                 if (parent->data)
1280                         base = &parent->data->npdata[0];
1281                 else
1282                         base = NULL;
1283                 count = parent->bytes / sizeof(hammer2_blockref_t);
1284                 break;
1285         case HAMMER2_BREF_TYPE_VOLUME:
1286                 base = &hmp->voldata.sroot_blockset.blockref[0];
1287                 count = HAMMER2_SET_COUNT;
1288                 break;
1289         case HAMMER2_BREF_TYPE_FREEMAP:
1290                 base = &parent->data->npdata[0];
1291                 count = HAMMER2_SET_COUNT;
1292                 break;
1293         default:
1294                 base = NULL;
1295                 count = 0;
1296                 panic("hammer2_chain_flush_pass2: "
1297                       "unrecognized blockref type: %d",
1298                       parent->bref.type);
1299         }
1300
1301         /*
1302          * Insertion
1303          *      - child is flagged as possibly needing block table insertion.
1304          *      - child not deleted or deletion is beyond transaction id
1305          *      - child created beyond parent synchronization point
1306          */
1307         if (child->delete_tid > trans->sync_tid &&
1308             child->modify_tid > parent->update_lo) {
1309                 if (base) {
1310                         hammer2_rollup_stats(parent, child, 1);
1311                         hammer2_base_insert(trans, parent, base, count,
1312                                             &info->cache_index, child);
1313                 }
1314         }
1315
1316         return 0;
1317 }
1318
1319 /*
1320  * PASS4 - CLEANUP CHILDREN (non-recursive, but CAN be re-entrant)
1321  *
1322  * Adjust queues and set or clear BMAPPED appropriately if processing
1323  * the live parent.  pass4 handles deletions, pass5 handles insertions.
1324  * Separate passes are required because both deletions and insertions can
1325  * occur on dbtree.
1326  *
1327  * Cleanup FLUSH_CREATE/FLUSH_DELETE on the last parent.
1328  */
1329 static int
1330 hammer2_flush_pass4(hammer2_chain_t *child, void *data)
1331 {
1332         hammer2_flush_info_t *info = data;
1333         hammer2_chain_t *parent = info->parent;
1334         hammer2_chain_core_t *above = child->above;
1335         hammer2_trans_t *trans = info->trans;
1336
1337         /*
1338          * Prefilter - Ignore children created after our flush_tid (not
1339          *             visible to our flush).
1340          */
1341         if (child->modify_tid > trans->sync_tid) {
1342                 KKASSERT(child->delete_tid >= child->modify_tid);
1343                 return 0;
1344         }
1345
1346         /*
1347          * Ref and lock child for operation, spinlock must be temporarily
1348          * Make sure child is referenced before we unlock.
1349          */
1350         hammer2_chain_ref(child);
1351         spin_unlock(&above->cst.spin);
1352         hammer2_chain_lock(child, HAMMER2_RESOLVE_NEVER);
1353         KKASSERT(child->above == above);
1354         KKASSERT(parent->core == above);
1355
1356         /*
1357          * Adjust BMAPPED state and rbtree/queue only when we hit the
1358          * actual live parent.
1359          */
1360         if ((parent->flags & HAMMER2_CHAIN_DELETED) == 0) {
1361                 spin_lock(&above->cst.spin);
1362
1363                 /*
1364                  * Deleting from blockmap, move child out of dbtree
1365                  * and clear BMAPPED.  Child should not be on RBTREE.
1366                  */
1367                 if (child->delete_tid <= trans->sync_tid &&
1368                     child->modify_tid <= parent->update_lo &&
1369                     child->delete_tid > parent->update_lo &&
1370                     (child->flags & HAMMER2_CHAIN_BMAPPED)) {
1371                         KKASSERT(child->flags & HAMMER2_CHAIN_ONDBTREE);
1372                         RB_REMOVE(hammer2_chain_tree, &above->dbtree, child);
1373                         atomic_clear_int(&child->flags, HAMMER2_CHAIN_ONDBTREE);
1374                         atomic_clear_int(&child->flags, HAMMER2_CHAIN_BMAPPED);
1375                 }
1376
1377                 /*
1378                  * Not on any list, place child on DBQ
1379                  */
1380                 if ((child->flags & (HAMMER2_CHAIN_ONRBTREE |
1381                                      HAMMER2_CHAIN_ONDBTREE |
1382                                      HAMMER2_CHAIN_ONDBQ)) == 0) {
1383                         KKASSERT((child->flags & HAMMER2_CHAIN_BMAPPED) == 0);
1384                         TAILQ_INSERT_TAIL(&above->dbq, child, db_entry);
1385                         atomic_set_int(&child->flags, HAMMER2_CHAIN_ONDBQ);
1386                 }
1387                 spin_unlock(&above->cst.spin);
1388         }
1389
1390         /*
1391          * Unlock the child.  This can wind up dropping the child's
1392          * last ref, removing it from the parent's RB tree, and deallocating
1393          * the structure.  The RB_SCAN() our caller is doing handles the
1394          * situation.
1395          */
1396         hammer2_chain_unlock(child);
1397         hammer2_chain_drop(child);
1398         spin_lock(&above->cst.spin);
1399
1400         /*
1401          * The parent may have been delete-duplicated.
1402          */
1403         return (0);
1404 }
1405
1406 static int
1407 hammer2_flush_pass5(hammer2_chain_t *child, void *data)
1408 {
1409         hammer2_flush_info_t *info = data;
1410         hammer2_chain_t *parent = info->parent;
1411         hammer2_chain_t *xchain;
1412         hammer2_chain_core_t *above = child->above;
1413         hammer2_trans_t *trans = info->trans;
1414
1415         /*
1416          * Prefilter - Ignore children created after our flush_tid (not
1417          *             visible to our flush).
1418          */
1419         if (child->modify_tid > trans->sync_tid) {
1420                 KKASSERT(child->delete_tid >= child->modify_tid);
1421                 return 0;
1422         }
1423
1424         /*
1425          * Ref and lock child for operation, spinlock must be temporarily
1426          * Make sure child is referenced before we unlock.
1427          */
1428         hammer2_chain_ref(child);
1429         spin_unlock(&above->cst.spin);
1430         hammer2_chain_lock(child, HAMMER2_RESOLVE_NEVER);
1431         KKASSERT(child->above == above);
1432         KKASSERT(parent->core == above);
1433
1434         /*
1435          * Adjust BMAPPED state and rbtree/queue only when we hit the
1436          * actual live parent.
1437          */
1438         if ((parent->flags & HAMMER2_CHAIN_DELETED) == 0) {
1439                 spin_lock(&above->cst.spin);
1440
1441                 /*
1442                  * Inserting into blockmap, place child in rbtree or dbtree.
1443                  */
1444                 if (child->delete_tid > trans->sync_tid &&
1445                     child->modify_tid > parent->update_lo &&
1446                     (child->flags & HAMMER2_CHAIN_BMAPPED) == 0) {
1447                         if (child->flags & HAMMER2_CHAIN_ONDBQ) {
1448                                 TAILQ_REMOVE(&above->dbq, child, db_entry);
1449                                 atomic_clear_int(&child->flags,
1450                                                  HAMMER2_CHAIN_ONDBQ);
1451                         }
1452                         if ((child->flags & HAMMER2_CHAIN_DELETED) == 0 &&
1453                             (child->flags & HAMMER2_CHAIN_ONRBTREE) == 0) {
1454                                 KKASSERT((child->flags &
1455                                           (HAMMER2_CHAIN_ONDBTREE |
1456                                            HAMMER2_CHAIN_ONDBQ)) == 0);
1457                                 xchain = RB_INSERT(hammer2_chain_tree,
1458                                                    &above->rbtree, child);
1459                                 KKASSERT(xchain == NULL);
1460                                 atomic_set_int(&child->flags,
1461                                                HAMMER2_CHAIN_ONRBTREE);
1462                         } else
1463                         if ((child->flags & HAMMER2_CHAIN_DELETED) &&
1464                             (child->flags & HAMMER2_CHAIN_ONDBTREE) == 0) {
1465                                 KKASSERT((child->flags &
1466                                           (HAMMER2_CHAIN_ONRBTREE |
1467                                            HAMMER2_CHAIN_ONDBQ)) == 0);
1468                                 xchain = RB_INSERT(hammer2_chain_tree,
1469                                                    &above->dbtree, child);
1470                                 KKASSERT(xchain == NULL);
1471                                 atomic_set_int(&child->flags,
1472                                                HAMMER2_CHAIN_ONDBTREE);
1473                         }
1474                         atomic_set_int(&child->flags, HAMMER2_CHAIN_BMAPPED);
1475                         KKASSERT(child->flags &
1476                                  (HAMMER2_CHAIN_ONRBTREE |
1477                                   HAMMER2_CHAIN_ONDBTREE |
1478                                   HAMMER2_CHAIN_ONDBQ));
1479                 }
1480
1481                 /*
1482                  * Not on any list, place child on DBQ
1483                  */
1484                 if ((child->flags & (HAMMER2_CHAIN_ONRBTREE |
1485                                      HAMMER2_CHAIN_ONDBTREE |
1486                                      HAMMER2_CHAIN_ONDBQ)) == 0) {
1487                         KKASSERT((child->flags & HAMMER2_CHAIN_BMAPPED) == 0);
1488                         TAILQ_INSERT_TAIL(&above->dbq, child, db_entry);
1489                         atomic_set_int(&child->flags, HAMMER2_CHAIN_ONDBQ);
1490                 }
1491                 spin_unlock(&above->cst.spin);
1492         }
1493
1494         /*
1495          * Cleanup flags on last parent iterated for flush.
1496          */
1497         if (info->domodify & 2) {
1498                 if (child->flags & HAMMER2_CHAIN_FLUSH_CREATE) {
1499                         atomic_clear_int(&child->flags,
1500                                          HAMMER2_CHAIN_FLUSH_CREATE);
1501                         hammer2_chain_drop(child);
1502                 }
1503                 if ((child->flags & HAMMER2_CHAIN_FLUSH_DELETE) &&
1504                     child->delete_tid <= trans->sync_tid) {
1505                         KKASSERT((child->flags & HAMMER2_CHAIN_ONDBTREE) == 0);
1506                         KKASSERT((child->flags & HAMMER2_CHAIN_BMAPPED) == 0);
1507                         atomic_clear_int(&child->flags,
1508                                          HAMMER2_CHAIN_FLUSH_DELETE);
1509                         hammer2_chain_drop(child);
1510                 }
1511         }
1512
1513         /*
1514          * Unlock the child.  This can wind up dropping the child's
1515          * last ref, removing it from the parent's RB tree, and deallocating
1516          * the structure.  The RB_SCAN() our caller is doing handles the
1517          * situation.
1518          */
1519         hammer2_chain_unlock(child);
1520         hammer2_chain_drop(child);
1521         spin_lock(&above->cst.spin);
1522
1523         /*
1524          * The parent may have been delete-duplicated.
1525          */
1526         return (0);
1527 }
1528
1529 void
1530 hammer2_rollup_stats(hammer2_chain_t *parent, hammer2_chain_t *child, int how)
1531 {
1532 #if 0
1533         hammer2_chain_t *grandp;
1534 #endif
1535
1536         parent->data_count += child->data_count;
1537         parent->inode_count += child->inode_count;
1538         child->data_count = 0;
1539         child->inode_count = 0;
1540         if (how < 0) {
1541                 parent->data_count -= child->bytes;
1542                 if (child->bref.type == HAMMER2_BREF_TYPE_INODE) {
1543                         parent->inode_count -= 1;
1544 #if 0
1545                         /* XXX child->data may be NULL atm */
1546                         parent->data_count -= child->data->ipdata.data_count;
1547                         parent->inode_count -= child->data->ipdata.inode_count;
1548 #endif
1549                 }
1550         } else if (how > 0) {
1551                 parent->data_count += child->bytes;
1552                 if (child->bref.type == HAMMER2_BREF_TYPE_INODE) {
1553                         parent->inode_count += 1;
1554 #if 0
1555                         /* XXX child->data may be NULL atm */
1556                         parent->data_count += child->data->ipdata.data_count;
1557                         parent->inode_count += child->data->ipdata.inode_count;
1558 #endif
1559                 }
1560         }
1561         if (parent->bref.type == HAMMER2_BREF_TYPE_INODE) {
1562                 parent->data->ipdata.data_count += parent->data_count;
1563                 parent->data->ipdata.inode_count += parent->inode_count;
1564 #if 0
1565                 for (grandp = parent->above->first_parent;
1566                      grandp;
1567                      grandp = grandp->next_parent) {
1568                         grandp->data_count += parent->data_count;
1569                         grandp->inode_count += parent->inode_count;
1570                 }
1571 #endif
1572                 parent->data_count = 0;
1573                 parent->inode_count = 0;
1574         }
1575 }