sys/vfs/hammer2/hammer2_flush.c

   1 /*
   2  * Copyright (c) 2011-2013 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             pass;
  60         int             cache_index;
  61         int             domodify;
  62         struct h2_flush_deferral_list flush_list;
  63         hammer2_tid_t   sync_tid;       /* flush synchronization point */
  64 };
  65
  66 typedef struct hammer2_flush_info hammer2_flush_info_t;
  67
  68 static void hammer2_chain_flush_core(hammer2_flush_info_t *info,
  69                                 hammer2_chain_t **chainp);
  70 static int hammer2_chain_flush_scan1(hammer2_chain_t *child, void *data);
  71 static int hammer2_chain_flush_scan2(hammer2_chain_t *child, void *data);
  72 static void hammer2_flush_core_update(hammer2_chain_core_t *core,
  73                           hammer2_flush_info_t *info);
  74 static void hammer2_rollup_stats(hammer2_chain_t *parent,
  75                                 hammer2_chain_t *child, int how);
  76
  77 /*
  78  * Can we ignore a chain for the purposes of flushing modifications
  79  * to the media?
  80  *
  81  * This code is no degenerate.  We used to have to distinguish between
  82  * deleted chains and deleted chains associated with inodes that were
  83  * still open.  This mechanic has been fixed so the function is now
  84  * a simple test.
  85  */
  86 static __inline
  87 int
  88 h2ignore_deleted(hammer2_flush_info_t *info, hammer2_chain_t *chain)
  89 {
  90         return (chain->delete_tid <= info->sync_tid);
  91 }
  92
  93 #if 0
  94 static __inline
  95 void
  96 hammer2_updatestats(hammer2_flush_info_t *info, hammer2_blockref_t *bref,
  97                     int how)
  98 {
  99         hammer2_key_t bytes;
 100
 101         if (bref->type != 0) {
 102                 bytes = 1 << (bref->data_off & HAMMER2_OFF_MASK_RADIX);
 103                 if (bref->type == HAMMER2_BREF_TYPE_INODE)
 104                         info->inode_count += how;
 105                 if (how < 0)
 106                         info->data_count -= bytes;
 107                 else
 108                         info->data_count += bytes;
 109         }
 110 }
 111 #endif
 112
 113 /*
 114  * Transaction support functions for writing to the filesystem.
 115  *
 116  * Initializing a new transaction allocates a transaction ID.  Typically
 117  * passed a pmp (hmp passed as NULL), indicating a cluster transaction.  Can
 118  * be passed a NULL pmp and non-NULL hmp to indicate a transaction on a single
 119  * media target.  The latter mode is used by the recovery code.
 120  *
 121  * TWO TRANSACTION IDs can run concurrently, where one is a flush and the
 122  * other is a set of any number of concurrent filesystem operations.  We
 123  * can either have <running_fs_ops> + <waiting_flush> + <blocked_fs_ops>
 124  * or we can have <running_flush> + <concurrent_fs_ops>.
 125  *
 126  * During a flush, new fs_ops are only blocked until the fs_ops prior to
 127  * the flush complete.  The new fs_ops can then run concurrent with the flush.
 128  *
 129  * Buffer-cache transactions operate as fs_ops but never block.  A
 130  * buffer-cache flush will run either before or after the current pending
 131  * flush depending on its state.
 132  *
 133  * sync_tid vs real_tid.  For flush transactions ONLY, the flush operation
 134  * actually uses two transaction ids, one for the flush operation itself,
 135  * and <N+1> for any freemap allocations made as a side-effect.  real_tid
 136  * is fixed at <N>, sync_tid is adjusted dynamically as-needed.
 137  *
 138  * NOTE: The sync_tid for a flush's freemap allocation will match the
 139  *       sync_tid of the following <concurrent_fs_ops> transaction(s).
 140  *       The freemap topology will be out-of-step by one transaction id
 141  *       in order to give the flusher a stable freemap topology to flush
 142  *       out.  This is fixed up at mount-time using a quick incremental
 143  *       scan.
 144  */
 145 void
 146 hammer2_trans_init(hammer2_trans_t *trans, hammer2_pfsmount_t *pmp,
 147                    hammer2_mount_t *hmp, int flags)
 148 {
 149         hammer2_trans_t *head;
 150
 151         bzero(trans, sizeof(*trans));
 152         if (pmp) {
 153                 trans->pmp = pmp;
 154                 KKASSERT(hmp == NULL);
 155                 hmp = pmp->cluster.chains[0]->hmp;      /* XXX */
 156         } else {
 157                 trans->hmp_single = hmp;
 158                 KKASSERT(hmp);
 159         }
 160
 161         hammer2_voldata_lock(hmp);
 162         trans->flags = flags;
 163         trans->td = curthread;
 164         /*trans->delete_gen = 0;*/      /* multiple deletions within trans */
 165
 166         if (flags & HAMMER2_TRANS_ISFLUSH) {
 167                 /*
 168                  * If multiple flushes are trying to run we have to
 169                  * wait until it is our turn.  All flushes are serialized.
 170                  *
 171                  * We queue ourselves and then wait to become the head
 172                  * of the queue, allowing all prior flushes to complete.
 173                  *
 174                  * A unique transaction id is required to avoid confusion
 175                  * when updating the block tables.
 176                  */
 177                 ++hmp->flushcnt;
 178                 ++hmp->voldata.alloc_tid;
 179                 trans->sync_tid = hmp->voldata.alloc_tid;
 180                 trans->real_tid = trans->sync_tid;
 181                 ++hmp->voldata.alloc_tid;
 182                 TAILQ_INSERT_TAIL(&hmp->transq, trans, entry);
 183                 if (TAILQ_FIRST(&hmp->transq) != trans) {
 184                         trans->blocked = 1;
 185                         while (trans->blocked) {
 186                                 lksleep(&trans->sync_tid, &hmp->voldatalk,
 187                                         0, "h2multf", hz);
 188                         }
 189                 }
 190         } else if (hmp->flushcnt == 0) {
 191                 /*
 192                  * No flushes are pending, we can go.
 193                  */
 194                 TAILQ_INSERT_TAIL(&hmp->transq, trans, entry);
 195                 trans->sync_tid = hmp->voldata.alloc_tid;
 196                 trans->real_tid = trans->sync_tid;
 197
 198                 /* XXX improve/optimize inode allocation */
 199         } else {
 200                 /*
 201                  * One or more flushes are pending.  We insert after
 202                  * the current flush and may block.  We have priority
 203                  * over any flushes that are not the current flush.
 204                  *
 205                  * TRANS_BUFCACHE transactions cannot block.
 206                  */
 207                 TAILQ_FOREACH(head, &hmp->transq, entry) {
 208                         if (head->flags & HAMMER2_TRANS_ISFLUSH)
 209                                 break;
 210                 }
 211                 KKASSERT(head);
 212                 TAILQ_INSERT_AFTER(&hmp->transq, head, trans, entry);
 213                 trans->sync_tid = head->real_tid + 1;
 214                 trans->real_tid = trans->sync_tid;
 215
 216                 if ((trans->flags & HAMMER2_TRANS_BUFCACHE) == 0) {
 217                         if (TAILQ_FIRST(&hmp->transq) != head) {
 218                                 trans->blocked = 1;
 219                                 while (trans->blocked) {
 220                                         lksleep(&trans->sync_tid,
 221                                                 &hmp->voldatalk, 0,
 222                                                 "h2multf", hz);
 223                                 }
 224                         }
 225                 }
 226         }
 227         if (flags & HAMMER2_TRANS_NEWINODE) {
 228                 if (hmp->voldata.inode_tid < HAMMER2_INODE_START)
 229                         hmp->voldata.inode_tid = HAMMER2_INODE_START;
 230                 trans->inode_tid = hmp->voldata.inode_tid++;
 231         }
 232         hammer2_voldata_unlock(hmp, 0);
 233 }
 234
 235 void
 236 hammer2_trans_done(hammer2_trans_t *trans)
 237 {
 238         hammer2_mount_t *hmp;
 239         hammer2_trans_t *head;
 240         hammer2_trans_t *scan;
 241
 242         if (trans->pmp)
 243                 hmp = trans->pmp->cluster.chains[0]->hmp;
 244         else
 245                 hmp = trans->hmp_single;
 246
 247         /*
 248          * Remove and adjust flushcnt
 249          */
 250         hammer2_voldata_lock(hmp);
 251         TAILQ_REMOVE(&hmp->transq, trans, entry);
 252         if (trans->flags & HAMMER2_TRANS_ISFLUSH)
 253                 --hmp->flushcnt;
 254
 255         /*
 256          * Unblock the head of the queue and any additional transactions
 257          * up to the next flush.
 258          */
 259         head = TAILQ_FIRST(&hmp->transq);
 260         if (head && head->blocked) {
 261                 head->blocked = 0;
 262                 wakeup(&head->sync_tid);
 263
 264                 scan = TAILQ_NEXT(head, entry);
 265                 while (scan && (scan->flags & HAMMER2_TRANS_ISFLUSH) == 0) {
 266                         if (scan->blocked) {
 267                                 scan->blocked = 0;
 268                                 wakeup(&scan->sync_tid);
 269                         }
 270                         scan = TAILQ_NEXT(scan, entry);
 271                 }
 272         }
 273         hammer2_voldata_unlock(hmp, 0);
 274 }
 275
 276 /*
 277  * Flush the chain and all modified sub-chains through the specified
 278  * synchronization point (sync_tid), propagating parent chain modifications
 279  * and mirror_tid updates back up as needed.  Since we are recursing downward
 280  * we do not have to deal with the complexities of multi-homed chains (chains
 281  * with multiple parents).
 282  *
 283  * Caller must have interlocked against any non-flush-related modifying
 284  * operations in progress whos modify_tid values are less than or equal
 285  * to the passed sync_tid.
 286  *
 287  * Caller must have already vetted synchronization points to ensure they
 288  * are properly flushed.  Only snapshots and cluster flushes can create
 289  * these sorts of synchronization points.
 290  *
 291  * This routine can be called from several places but the most important
 292  * is from the hammer2_vop_reclaim() function.  We want to try to completely
 293  * clean out the inode structure to prevent disconnected inodes from
 294  * building up and blowing out the kmalloc pool.  However, it is not actually
 295  * necessary to flush reclaimed inodes to maintain HAMMER2's crash recovery
 296  * capability.
 297  *
 298  * chain is locked on call and will remain locked on return.  If a flush
 299  * occured, the chain's MOVED bit will be set indicating that its parent
 300  * (which is not part of the flush) should be updated.  The chain may be
 301  * replaced by the call.
 302  */
 303 void
 304 hammer2_chain_flush(hammer2_trans_t *trans, hammer2_chain_t **chainp)
 305 {
 306         hammer2_chain_t *chain = *chainp;
 307         hammer2_chain_t *scan;
 308         hammer2_chain_core_t *core;
 309         hammer2_flush_info_t info;
 310         int loops;
 311
 312         /*
 313          * Execute the recursive flush and handle deferrals.
 314          *
 315          * Chains can be ridiculously long (thousands deep), so to
 316          * avoid blowing out the kernel stack the recursive flush has a
 317          * depth limit.  Elements at the limit are placed on a list
 318          * for re-execution after the stack has been popped.
 319          */
 320         bzero(&info, sizeof(info));
 321         TAILQ_INIT(&info.flush_list);
 322         info.trans = trans;
 323         info.sync_tid = trans->sync_tid;
 324         info.cache_index = -1;
 325
 326         core = chain->core;
 327 #if FLUSH_DEBUG
 328         kprintf("CHAIN FLUSH trans %p.%016jx chain %p.%d mod %016jx upd %016jx\n", trans, trans->sync_tid, chain, chain->bref.type, chain->modify_tid, core->update_lo);
 329 #endif
 330
 331         /*
 332          * Extra ref needed because flush_core expects it when replacing
 333          * chain.
 334          */
 335         hammer2_chain_ref(chain);
 336         loops = 0;
 337
 338         for (;;) {
 339                 /*
 340                  * Unwind deep recursions which had been deferred.  This
 341                  * can leave MOVED set for these chains, which will be
 342                  * handled when we [re]flush chain after the unwind.
 343                  */
 344                 while ((scan = TAILQ_FIRST(&info.flush_list)) != NULL) {
 345                         KKASSERT(scan->flags & HAMMER2_CHAIN_DEFERRED);
 346                         TAILQ_REMOVE(&info.flush_list, scan, flush_node);
 347                         atomic_clear_int(&scan->flags, HAMMER2_CHAIN_DEFERRED);
 348
 349                         /*
 350                          * Now that we've popped back up we can do a secondary
 351                          * recursion on the deferred elements.
 352                          *
 353                          * NOTE: hammer2_chain_flush() may replace scan.
 354                          */
 355                         if (hammer2_debug & 0x0040)
 356                                 kprintf("deferred flush %p\n", scan);
 357                         hammer2_chain_lock(scan, HAMMER2_RESOLVE_MAYBE);
 358                         hammer2_chain_drop(scan);       /* ref from deferral */
 359                         hammer2_chain_flush(trans, &scan);
 360                         hammer2_chain_unlock(scan);
 361                 }
 362
 363                 /*
 364                  * [re]flush chain.
 365                  */
 366                 info.diddeferral = 0;
 367                 hammer2_chain_flush_core(&info, &chain);
 368 #if FLUSH_DEBUG
 369                 kprintf("flush_core_done parent=<base> chain=%p.%d %08x\n",
 370                         chain, chain->bref.type, chain->flags);
 371 #endif
 372
 373                 /*
 374                  * Only loop if deep recursions have been deferred.
 375                  */
 376                 if (TAILQ_EMPTY(&info.flush_list))
 377                         break;
 378
 379                 if (++loops % 1000 == 0) {
 380                         kprintf("hammer2_chain_flush: excessive loops on %p\n",
 381                                 chain);
 382                         if (hammer2_debug & 0x100000)
 383                                 Debugger("hell4");
 384                 }
 385         }
 386         hammer2_chain_drop(chain);
 387         *chainp = chain;
 388 }
 389
 390 /*
 391  * This is the core of the chain flushing code.  The chain is locked by the
 392  * caller and must also have an extra ref on it by the caller, and remains
 393  * locked and will have an extra ref on return.
 394  *
 395  * If the flush accomplished any work chain will be flagged MOVED
 396  * indicating a copy-on-write propagation back up is required.
 397  * Deep sub-nodes may also have been entered onto the deferral list.
 398  * MOVED is never set on the volume root.
 399  *
 400  * NOTE: modify_tid is different from MODIFIED.  modify_tid is updated
 401  *       only when a chain is specifically modified, and not updated
 402  *       for copy-on-write propagations.  MODIFIED is set on any modification
 403  *       including copy-on-write propagations.
 404  *
 405  * NOTE: We are responsible for updating chain->bref.mirror_tid and
 406  *       core->update_lo  The caller is responsible for processing us into
 407  *       our parent (if any).
 408  *
 409  *       We are also responsible for updating chain->core->update_lo to
 410  *       prevent repeated recursions due to deferrals.
 411  *
 412  * WARNING! bref.mirror_tid may only be updated if either the MODIFIED bit
 413  *          is already zero or if we clear it.
 414  *
 415  */
 416 static void
 417 hammer2_chain_flush_core(hammer2_flush_info_t *info, hammer2_chain_t **chainp)
 418 {
 419         hammer2_chain_t *chain = *chainp;
 420         hammer2_chain_t *saved_parent;
 421         hammer2_mount_t *hmp;
 422         hammer2_blockref_t *bref;
 423         hammer2_chain_core_t *core;
 424         char *bdata;
 425         hammer2_io_t *dio;
 426         int error;
 427         int diddeferral;
 428
 429         hmp = chain->hmp;
 430         core = chain->core;
 431         diddeferral = info->diddeferral;
 432
 433         /*
 434          * Check if we even have any work to do.
 435          *
 436          * We do not update core->update_lo because there might be other
 437          * paths to the core and we haven't actually checked it.
 438          *
 439          * This bit of code is capable of short-cutting entire sub-trees
 440          * if they have not been touched.
 441          */
 442         if ((chain->flags & HAMMER2_CHAIN_MODIFIED) == 0 &&
 443             (core->update_lo >= info->sync_tid ||
 444              chain->bref.mirror_tid >= info->sync_tid ||
 445              chain->bref.mirror_tid >= core->update_hi)) {
 446                 KKASSERT(chain->modify_tid <= info->sync_tid);
 447                 /* don't update update_lo, there may be other paths to core */
 448                 /* don't update bref.mirror_tid, scan2 is not called */
 449                 return;
 450         }
 451
 452         /*
 453          * Ignore chains which have already been flushed through the current
 454          * synchronization point.
 455          */
 456         KKASSERT (chain->bref.mirror_tid <= info->sync_tid);
 457         if (chain->bref.mirror_tid == info->sync_tid) {
 458                 /* do not update core->update_lo, there may be another path */
 459                 return;
 460         }
 461
 462         /*
 463          * Ignore chains modified beyond the current flush point.  These
 464          * will be treated as if they did not exist.  Subchains with lower
 465          * modify_tid's will still be accessible via other parents.
 466          *
 467          * Do not update bref.mirror_tid here, it will interfere with
 468          * synchronization.  e.g. inode flush tid 1, concurrent D-D tid 2,
 469          * then later on inode flush tid 2.  If we were to set mirror_tid
 470          * to 1 during inode flush tid 1 the blockrefs would only be partially
 471          * updated (and likely panic).
 472          *
 473          * Do not update core->update_lo here, there might be other paths
 474          * to the core and we haven't actually flushed it.
 475          *
 476          * (vchain and fchain are exceptions since they cannot be duplicated)
 477          */
 478         if (chain->modify_tid > info->sync_tid &&
 479             chain != &hmp->fchain && chain != &hmp->vchain) {
 480                 /* do not update bref.mirror_tid, scan2 ignores chain */
 481                 /* do not update core->update_lo, there may be another path */
 482                 return;
 483         }
 484
 485         saved_parent = info->parent;
 486         info->parent = chain;
 487 retry:
 488
 489         /*
 490          * Chains deleted as-of the flush synchronization point require some
 491          * special early handling to avoid double flushing because multiple
 492          * deletions are sometimes forced within the same transaction.
 493          * Allowing the flush to proceed through more than one path can wind
 494          * up updating the chain's block table twice and cause an assertion.
 495          *
 496          * We don't check the 'same transaction' part but simply punt in this
 497          * situation.  We must still check for multiple deletions, since any
 498          * terminal (non-stale) deletion still requires processing to at
 499          * least clean up the children, and also (for inodes) there might
 500          * still be an open descriptor.
 501          *
 502          * Clear MODIFIED but set MOVED to ensure that the parent still
 503          * deals with it.
 504          */
 505         if (chain->delete_tid <= info->sync_tid &&
 506             (chain->flags & HAMMER2_CHAIN_DUPLICATED)) {
 507                 if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
 508 #if 0
 509                         /*
 510                          * XXX should be able to invalidate the buffer here.
 511                          * XXX problem if reused, snapshotted, or reactivated.
 512                          */
 513                         if (chain->dio) {
 514                                 hammer2_io_setinval(chain->dio, chain->bytes);
 515                         }
 516 #endif
 517                         if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
 518                                 hammer2_chain_ref(chain);
 519                                 atomic_set_int(&chain->flags,
 520                                                HAMMER2_CHAIN_MOVED);
 521                         }
 522                         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
 523                         hammer2_chain_memory_wakeup(chain->pmp);
 524                         hammer2_chain_drop(chain);
 525                 }
 526
 527                 /*
 528                  * Update mirror_tid, indicating that chain is synchronized
 529                  * on its modification and block table.  This probably isn't
 530                  * needed since scan2 should ignore deleted chains anyway.
 531                  *
 532                  * NOTE: bref.mirror_tid cannot be updated
 533                  *       unless MODIFIED is cleared or already
 534                  *       clear.
 535                  */
 536                 if (chain->bref.mirror_tid < info->sync_tid)
 537                         chain->bref.mirror_tid = info->sync_tid;
 538                 /* do not update core->update_lo, there may be another path */
 539                 info->parent = saved_parent;
 540                 return;
 541         }
 542
 543         /*
 544          * Recurse if we are not up-to-date.  Once we are done we will
 545          * update update_lo if there were no deferrals.  update_lo can become
 546          * higher than update_hi and is used to prevent re-recursions during
 547          * the same flush cycle.
 548          *
 549          * update_hi was already checked and prevents initial recursions on
 550          * subtrees which have not been modified.
 551          *
 552          * NOTE: We must recurse whether chain is flagged DELETED or not.
 553          *       However, if it is flagged DELETED we limit sync_tid to
 554          *       delete_tid to ensure that the chain's bref.mirror_tid is
 555          *       not fully updated and causes it to miss the non-DELETED
 556          *       path.
 557          *
 558          * NOTE: If a deferral occurs hammer2_chain_flush() will flush the
 559          *       deferred chain independently which will update it's
 560          *       bref.mirror_tid and prevent it from deferred again.
 561          */
 562         if (chain->bref.mirror_tid < info->sync_tid &&
 563             chain->bref.mirror_tid < core->update_hi) {
 564                 hammer2_chain_layer_t *layer;
 565                 int saved_domodify;
 566                 int save_gen;
 567
 568                 /*
 569                  * Races will bump update_hi above trans->sync_tid and should
 570                  * not affect this test.
 571                  *
 572                  * We don't want to set our chain to MODIFIED gratuitously.
 573                  *
 574                  * We need an extra ref on chain because we are going to
 575                  * release its lock temporarily in our child loop.
 576                  */
 577
 578                 /*
 579                  * Run two passes.  The first pass handles MODIFIED and
 580                  * update_lo recursions while the second pass handles
 581                  * MOVED chains on the way back up.
 582                  *
 583                  * If the stack gets too deep we defer the chain.   Since
 584                  * hammer2_chain_core's can be shared at multiple levels
 585                  * in the tree, we may encounter a chain that we had already
 586                  * deferred.  We could undefer it but it will probably just
 587                  * defer again so it is best to leave it deferred.
 588                  *
 589                  * Scan1 is recursive.
 590                  *
 591                  * NOTE: The act of handling a modified/submodified chain can
 592                  *       cause the MOVED Flag to be set.  It can also be set
 593                  *       via hammer2_chain_delete() and in other situations.
 594                  *
 595                  * NOTE: RB_SCAN() must be used instead of RB_FOREACH()
 596                  *       because children can be physically removed during
 597                  *       the scan.
 598                  *
 599                  * NOTE: We would normally not care about insertions except
 600                  *       that some insertions might occur from the flush
 601                  *       itself, so loop on generation number changes.
 602                  */
 603                 saved_domodify = info->domodify;
 604                 info->domodify = 0;
 605
 606                 if (chain->flags & HAMMER2_CHAIN_DEFERRED) {
 607                         ++info->diddeferral;
 608                 } else if (info->depth == HAMMER2_FLUSH_DEPTH_LIMIT) {
 609                         if ((chain->flags & HAMMER2_CHAIN_DEFERRED) == 0) {
 610                                 hammer2_chain_ref(chain);
 611                                 TAILQ_INSERT_TAIL(&info->flush_list,
 612                                                   chain, flush_node);
 613                                 atomic_set_int(&chain->flags,
 614                                                HAMMER2_CHAIN_DEFERRED);
 615                         }
 616                         ++info->diddeferral;
 617                 } else {
 618                         spin_lock(&core->cst.spin);
 619                         KKASSERT(core->good == 0x1234 && core->sharecnt > 0);
 620                         do {
 621                                 save_gen = core->generation;
 622                                 TAILQ_FOREACH_REVERSE(layer, &core->layerq,
 623                                                       h2_layer_list, entry) {
 624                                         ++layer->refs;
 625                                         KKASSERT(layer->good == 0xABCD);
 626                                         RB_SCAN(hammer2_chain_tree,
 627                                                 &layer->rbtree,
 628                                                 NULL, hammer2_chain_flush_scan1,
 629                                                 info);
 630                                         --layer->refs;
 631                                 }
 632                         } while (core->generation != save_gen);
 633                         spin_unlock(&core->cst.spin);
 634                 }
 635
 636                 if (info->parent != chain) {
 637                         kprintf("ZZZ\n");
 638                         hammer2_chain_drop(chain);
 639                         hammer2_chain_ref(info->parent);
 640                 }
 641                 chain = info->parent;
 642
 643                 /*
 644                  * chain was unlocked during the scan1 recursion and may
 645                  * have been deleted, destroyed, or even synchronously
 646                  * flushed due to aliasing.
 647                  *
 648                  * The flush continues normally in the first two places as
 649                  * the deletion or destruction does NOT affect the flush
 650                  * as-of the flush synchronization point.
 651                  *
 652                  * We must detect the last case and avoid flushing chain twice.
 653                  */
 654 #if 0
 655                 if (chain->delete_tid <= info->sync_tid &&
 656                     (chain->flags & HAMMER2_CHAIN_DUPLICATED)) {
 657                         kprintf("xxx\n");
 658                         goto retry;
 659                 }
 660 #endif
 661                 if (chain->bref.mirror_tid >= info->sync_tid ||
 662                     chain->bref.mirror_tid >= core->update_hi) {
 663                         kprintf("yyy\n");
 664                         goto retry;
 665                 }
 666
 667                 /*
 668                  * If any deferral occurred we must set domodify to 0 to avoid
 669                  * potentially modifying the parent twice (now and when we run
 670                  * the deferral list), as doing so could cause the blockref
 671                  * update to run on a block array which has already been
 672                  * updated.
 673                  */
 674                 if (info->domodify && diddeferral != info->diddeferral)
 675                         info->domodify = 0;
 676
 677                 /*
 678                  * THIS IS THE ONLY POINT IN THE FLUSH WHERE A PARENT IN THE
 679                  * NOMINAL TOPOLOGY, OTHER THAN FREEMAP ALLOCATIONS, IS
 680                  * MODIFIED.  FREEMAP ALLOCATIONS WILL MODIFY THE FREEMAP
 681                  * TOPOLOGY WITH SYNC_TID+1 AND DO NOT AFFECT THE CURRENT
 682                  * FLUSH.
 683                  *
 684                  * Modifying the parent can create issues if the current
 685                  * parent is already in a modified state with an earlier
 686                  * transaction id.  We want to avoid an endless flush loop
 687                  * on the original parent so we must clear its modified bit
 688                  * after creating the new parent, if they wind up being
 689                  * different.  Care must also be taken to avoid flushing the
 690                  * same parent twice.
 691                  *
 692                  * We are responsible for setting the parent into a modified
 693                  * state before we scan the children to update the parent's
 694                  * block table.  This must essentially be done as an atomic
 695                  * operation (the parent must remain locked throughout the
 696                  * operation), otherwise other transactions can squeeze a
 697                  * delete-duplicate in and create block table havoc.
 698                  *
 699                  * NOTE: Blockrefs are only updated on live chains.
 700                  *
 701                  * NOTE: Modifying the parent generally causes a
 702                  *       delete-duplicate to occur from within the flush
 703                  *       itself, with an allocation from the freemap occuring
 704                  *       as an additional side-effect.
 705                  *
 706                  * NOTE: If the parent was deleted our modified chain will
 707                  *       also be marked deleted, but since it inherits the
 708                  *       parent's delete_tid it will still appear to be
 709                  *       'live' for the purposes of the flush.
 710                  */
 711                 if (info->domodify && !h2ignore_deleted(info, chain)) {
 712                         KKASSERT(chain->modify_tid < info->sync_tid);
 713
 714                         /*
 715                          * The scan1 loop and/or flush_core is reentrant,
 716                          * particularly when core->generation changes.  To
 717                          * avoid havoc we have to prevent repetitive
 718                          * delete-duplicates of the same chain.
 719                          *
 720                          * After executing the modify set the original chain's
 721                          * bref.mirror_tid to prevent any reentrancy during
 722                          * the current flush cycle.
 723                          */
 724                         hammer2_chain_modify(info->trans, &info->parent,
 725                                              HAMMER2_MODIFY_NO_MODIFY_TID);
 726                         if (info->parent != chain) {
 727                                 /*
 728                                  * NOTE: bref.mirror_tid cannot be updated
 729                                  *       unless MODIFIED is cleared or already
 730                                  *       clear.
 731                                  */
 732                                 if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
 733                                         atomic_clear_int(&chain->flags,
 734                                                         HAMMER2_CHAIN_MODIFIED);
 735                                         hammer2_chain_memory_wakeup(chain->pmp);
 736                                         hammer2_chain_drop(chain);
 737                                 }
 738                                 if (chain->bref.mirror_tid < info->sync_tid)
 739                                         chain->bref.mirror_tid = info->sync_tid;
 740                                 hammer2_chain_drop(chain);
 741                                 hammer2_chain_ref(info->parent);
 742                         }
 743                         chain = info->parent;
 744                 }
 745
 746                 KKASSERT(chain == info->parent);
 747
 748                 /*
 749                  * Handle successfully flushed children who are in the MOVED
 750                  * state on the way back up the recursion.  This can have
 751                  * the side-effect of clearing MOVED.
 752                  *
 753                  * Scan2 may replace info->parent.  If it does it will also
 754                  * replace the extra ref we made.
 755                  *
 756                  * Scan2 is non-recursive.
 757                  */
 758                 if (diddeferral != info->diddeferral) {
 759                         spin_lock(&core->cst.spin);
 760                 } else {
 761                         KKASSERT(chain == info->parent);
 762                         KKASSERT(info->domodify == 0 ||
 763                                  (chain->flags & HAMMER2_CHAIN_FLUSHED) == 0);
 764                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_FLUSHED);
 765                         spin_lock(&core->cst.spin);
 766                         KKASSERT(core->good == 0x1234 && core->sharecnt > 0);
 767                         KKASSERT(info->parent->core == core);
 768                         TAILQ_FOREACH_REVERSE(layer, &core->layerq,
 769                                               h2_layer_list, entry) {
 770                                 info->pass = 1;
 771                                 ++layer->refs;
 772                                 KKASSERT(layer->good == 0xABCD);
 773                                 RB_SCAN(hammer2_chain_tree, &layer->rbtree,
 774                                         NULL, hammer2_chain_flush_scan2, info);
 775                                 info->pass = 2;
 776                                 RB_SCAN(hammer2_chain_tree, &layer->rbtree,
 777                                         NULL, hammer2_chain_flush_scan2, info);
 778                                 --layer->refs;
 779                         }
 780                 }
 781
 782                 /*
 783                  * info->parent must not have been replaced again
 784                  */
 785                 KKASSERT(info->parent == chain);
 786
 787                 *chainp = chain;
 788
 789                 hammer2_chain_layer_check_locked(chain->hmp, core);
 790                 spin_unlock(&core->cst.spin);
 791
 792                 /*
 793                  * Update the core only if no deferrals occurred.  Otherwise
 794                  * we could end up clearing the MOVED bit in the children
 795                  * prematurely.
 796                  */
 797                 if (diddeferral == info->diddeferral)
 798                         hammer2_flush_core_update(core, info);
 799
 800                 info->domodify = saved_domodify;
 801                 KKASSERT(chain->refs > 1);
 802         } else {
 803                 /*
 804                  * Update the core, no deferrals occurred in this path.
 805                  */
 806                 hammer2_flush_core_update(core, info);
 807         }
 808         info->parent = saved_parent;
 809
 810 #if FLUSH_DEBUG
 811         kprintf("POP    %p.%d defer=%d\n", chain, chain->bref.type, diddeferral);
 812 #endif
 813
 814         /*
 815          * Do not flush the chain if there were any deferrals.  It will be
 816          * retried later after the deferrals are independently handled.
 817          * Do not update update_lo or bref.mirror_tid.
 818          */
 819         if (diddeferral != info->diddeferral) {
 820                 if (hammer2_debug & 0x0008) {
 821                         kprintf("%*.*s} %p/%d %04x (deferred)",
 822                                 info->depth, info->depth, "",
 823                                 chain, chain->refs, chain->flags);
 824                 }
 825                 /* do not update core->update_lo */
 826                 /* do not update bref.mirror_tid */
 827                 return;
 828         }
 829
 830         KKASSERT(chain->bref.mirror_tid < info->sync_tid);
 831
 832         /*
 833          * Non-deferral path, chain is now deterministically being flushed.
 834          * We've finished running the recursion and the blockref update.
 835          *
 836          * update bref.mirror_tid.  update_lo has already been updated.
 837          *
 838          * After this point we MUST dipose of the MODIFIED bit on chain.
 839          */
 840         if (chain->bref.mirror_tid < info->sync_tid)
 841                 chain->bref.mirror_tid = info->sync_tid;
 842
 843         /*
 844          * Deal with deleted and destroyed chains on the way back up.
 845          *
 846          * Otherwise a deleted chain can be optimized by clearing MODIFIED
 847          * without bothering to write it out.
 848          *
 849          * NOTE: We optimize this by noting that only 'inode' chains require
 850          *       this treatment.  When a file with an open descriptor is
 851          *       deleted only its inode is marked deleted.  Other deletions,
 852          *       such as indirect block deletions, will no longer be visible
 853          *       to the live filesystem and do not need to be updated.
 854          */
 855         if (h2ignore_deleted(info, chain)) {
 856                 /*
 857                  * At the moment we unconditionally set the MOVED bit because
 858                  * there are situations where it might not have been set due
 859                  * to similar delete-destroyed optimizations, and the parent
 860                  * of the parent still may need to be notified of the deletion.
 861                  */
 862                 if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
 863                         hammer2_chain_ref(chain);
 864                         atomic_set_int(&chain->flags,
 865                                        HAMMER2_CHAIN_MOVED);
 866                 }
 867                 if (chain->flags & HAMMER2_CHAIN_MODIFIED) {
 868 #if 0
 869                         /*
 870                          * XXX should be able to invalidate the buffer here.
 871                          * XXX problem if reused, snapshotted, or reactivated.
 872                          */
 873                         if (chain->dio) {
 874                                 hammer2_io_setinval(chain->dio, chain->bytes);
 875                         }
 876 #endif
 877                         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
 878                         hammer2_chain_memory_wakeup(chain->pmp);
 879                         hammer2_chain_drop(chain);
 880                 }
 881                 return;
 882         }
 883
 884         /*
 885          * A degenerate flush might not have flushed anything and thus not
 886          * processed modified blocks on the way back up.  Detect the case.
 887          *
 888          * This case can occur when a create, modify, and rename (to a
 889          * different part of the topology) occurs in the same flush,
 890          * resulting in a parent which effectively needs no modification.
 891          */
 892         if ((chain->flags & HAMMER2_CHAIN_MODIFIED) == 0) {
 893 #if 0
 894                 kprintf("chain %p.%d %08x recursed but wasn't "
 895                         "modified mirr=%016jx "
 896                         "update_lo=%016jx synctid=%016jx\n",
 897                         chain, chain->bref.type, chain->flags,
 898                         chain->bref.mirror_tid,
 899                         core->update_lo, info->sync_tid);
 900 #endif
 901 #if 0
 902                 if ((chain->flags & HAMMER2_CHAIN_MOVED) == 0) {
 903                         hammer2_chain_ref(chain);
 904                         atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
 905                 }
 906 #endif
 907                 return;
 908         }
 909
 910         /*
 911          * Issue flush.
 912          *
 913          * A DELETED node that reaches this point must be flushed for
 914          * synchronization point consistency.
 915          *
 916          * Update bref.mirror_tid, clear MODIFIED, and set MOVED.
 917          *
 918          * The caller will update the parent's reference to this chain
 919          * by testing MOVED as long as the modification was in-bounds.
 920          *
 921          * MOVED is never set on the volume root as there is no parent
 922          * to adjust.
 923          */
 924         if (hammer2_debug & 0x1000) {
 925                 kprintf("Flush %p.%d %016jx/%d sync_tid=%016jx data=%016jx\n",
 926                         chain, chain->bref.type,
 927                         chain->bref.key, chain->bref.keybits,
 928                         info->sync_tid, chain->bref.data_off);
 929         }
 930         if (hammer2_debug & 0x2000) {
 931                 Debugger("Flush hell");
 932         }
 933
 934         atomic_clear_int(&chain->flags, HAMMER2_CHAIN_MODIFIED);
 935         hammer2_chain_memory_wakeup(chain->pmp);
 936
 937         if ((chain->flags & HAMMER2_CHAIN_MOVED) ||
 938             chain == &hmp->vchain ||
 939             chain == &hmp->fchain) {
 940                 /*
 941                  * Drop the ref from the MODIFIED bit we cleared,
 942                  * net -1 ref.
 943                  */
 944                 hammer2_chain_drop(chain);
 945         } else {
 946                 /*
 947                  * Drop the ref from the MODIFIED bit we cleared and
 948                  * set a ref for the MOVED bit we are setting.  Net 0 refs.
 949                  */
 950                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_MOVED);
 951         }
 952
 953         /*
 954          * If this is part of a recursive flush we can go ahead and write
 955          * out the buffer cache buffer and pass a new bref back up the chain
 956          * via the MOVED bit.
 957          *
 958          * Volume headers are NOT flushed here as they require special
 959          * processing.
 960          */
 961         switch(chain->bref.type) {
 962         case HAMMER2_BREF_TYPE_FREEMAP:
 963                 hammer2_modify_volume(hmp);
 964                 hmp->voldata.freemap_tid = hmp->fchain.bref.mirror_tid;
 965                 break;
 966         case HAMMER2_BREF_TYPE_VOLUME:
 967                 /*
 968                  * The free block table is flushed by hammer2_vfs_sync()
 969                  * before it flushes vchain.  We must still hold fchain
 970                  * locked while copying voldata to volsync, however.
 971                  */
 972                 hammer2_chain_lock(&hmp->fchain, HAMMER2_RESOLVE_ALWAYS);
 973 #if 0
 974                 if ((hmp->fchain.flags & HAMMER2_CHAIN_MODIFIED) ||
 975                     hmp->voldata.freemap_tid < info->trans->sync_tid) {
 976                         /* this will modify vchain as a side effect */
 977                         hammer2_chain_t *tmp = &hmp->fchain;
 978                         hammer2_chain_flush(info->trans, &tmp);
 979                         KKASSERT(tmp == &hmp->fchain);
 980                 }
 981 #endif
 982
 983                 /*
 984                  * There is no parent to our root vchain and fchain to
 985                  * synchronize the bref to, their updated mirror_tid's
 986                  * must be synchronized to the volume header.
 987                  */
 988                 hmp->voldata.mirror_tid = chain->bref.mirror_tid;
 989                 /*hmp->voldata.freemap_tid = hmp->fchain.bref.mirror_tid;*/
 990
 991                 /*
 992                  * The volume header is flushed manually by the syncer, not
 993                  * here.  All we do here is adjust the crc's.
 994                  */
 995                 KKASSERT(chain->data != NULL);
 996                 KKASSERT(chain->dio == NULL);
 997
 998                 hmp->voldata.icrc_sects[HAMMER2_VOL_ICRC_SECT1]=
 999                         hammer2_icrc32(
1000                                 (char *)&hmp->voldata +
1001                                  HAMMER2_VOLUME_ICRC1_OFF,
1002                                 HAMMER2_VOLUME_ICRC1_SIZE);
1003                 hmp->voldata.icrc_sects[HAMMER2_VOL_ICRC_SECT0]=
1004                         hammer2_icrc32(
1005                                 (char *)&hmp->voldata +
1006                                  HAMMER2_VOLUME_ICRC0_OFF,
1007                                 HAMMER2_VOLUME_ICRC0_SIZE);
1008                 hmp->voldata.icrc_volheader =
1009                         hammer2_icrc32(
1010                                 (char *)&hmp->voldata +
1011                                  HAMMER2_VOLUME_ICRCVH_OFF,
1012                                 HAMMER2_VOLUME_ICRCVH_SIZE);
1013                 hmp->volsync = hmp->voldata;
1014                 atomic_set_int(&chain->flags, HAMMER2_CHAIN_VOLUMESYNC);
1015                 hammer2_chain_unlock(&hmp->fchain);
1016                 break;
1017         case HAMMER2_BREF_TYPE_DATA:
1018                 /*
1019                  * Data elements have already been flushed via the logical
1020                  * file buffer cache.  Their hash was set in the bref by
1021                  * the vop_write code.
1022                  *
1023                  * Make sure any device buffer(s) have been flushed out here.
1024                  * (there aren't usually any to flush).
1025                  */
1026 #if 0
1027                 /* XXX */
1028                 /* chain and chain->bref, NOWAIT operation */
1029 #endif
1030                 break;
1031 #if 0
1032         case HAMMER2_BREF_TYPE_INDIRECT:
1033                 /*
1034                  * Indirect blocks may be in an INITIAL state.  Use the
1035                  * chain_lock() call to ensure that the buffer has been
1036                  * instantiated (even though it is already locked the buffer
1037                  * might not have been instantiated).
1038                  *
1039                  * Only write the buffer out if it is dirty, it is possible
1040                  * the operating system had already written out the buffer.
1041                  */
1042                 hammer2_chain_lock(chain, HAMMER2_RESOLVE_ALWAYS);
1043                 KKASSERT(chain->dio != NULL);
1044
1045                 chain->data = NULL;
1046                 hammer2_io_bqrelse(&chain->dio);
1047                 hammer2_chain_unlock(chain);
1048                 break;
1049 #endif
1050         case HAMMER2_BREF_TYPE_INDIRECT:
1051         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1052                 /*
1053                  * Device-backed.  Buffer will be flushed by the sync
1054                  * code XXX.
1055                  */
1056                 KKASSERT((chain->flags & HAMMER2_CHAIN_EMBEDDED) == 0);
1057                 break;
1058         case HAMMER2_BREF_TYPE_FREEMAP_LEAF:
1059         default:
1060                 /*
1061                  * Embedded elements have to be flushed out.
1062                  * (Basically just BREF_TYPE_INODE).
1063                  */
1064                 KKASSERT(chain->flags & HAMMER2_CHAIN_EMBEDDED);
1065                 KKASSERT(chain->data != NULL);
1066                 KKASSERT(chain->dio == NULL);
1067                 bref = &chain->bref;
1068
1069                 KKASSERT((bref->data_off & HAMMER2_OFF_MASK) != 0);
1070                 KKASSERT(HAMMER2_DEC_CHECK(chain->bref.methods) ==
1071                          HAMMER2_CHECK_ISCSI32 ||
1072                          HAMMER2_DEC_CHECK(chain->bref.methods) ==
1073                          HAMMER2_CHECK_FREEMAP);
1074
1075                 /*
1076                  * The data is embedded, we have to acquire the
1077                  * buffer cache buffer and copy the data into it.
1078                  */
1079                 error = hammer2_io_bread(hmp, bref->data_off, chain->bytes,
1080                                          &dio);
1081                 KKASSERT(error == 0);
1082                 bdata = hammer2_io_data(dio, bref->data_off);
1083
1084                 /*
1085                  * Copy the data to the buffer, mark the buffer
1086                  * dirty, and convert the chain to unmodified.
1087                  */
1088                 bcopy(chain->data, bdata, chain->bytes);
1089                 hammer2_io_bdwrite(&dio);
1090
1091                 switch(HAMMER2_DEC_CHECK(chain->bref.methods)) {
1092                 case HAMMER2_CHECK_FREEMAP:
1093                         chain->bref.check.freemap.icrc32 =
1094                                 hammer2_icrc32(chain->data, chain->bytes);
1095                         break;
1096                 case HAMMER2_CHECK_ISCSI32:
1097                         chain->bref.check.iscsi32.value =
1098                                 hammer2_icrc32(chain->data, chain->bytes);
1099                         break;
1100                 default:
1101                         panic("hammer2_flush_core: bad crc type");
1102                         break; /* NOT REACHED */
1103                 }
1104                 if (chain->bref.type == HAMMER2_BREF_TYPE_INODE)
1105                         ++hammer2_iod_meta_write;
1106                 else
1107                         ++hammer2_iod_indr_write;
1108         }
1109 }
1110
1111 /*
1112  * Flush helper scan1 (recursive)
1113  *
1114  * Flushes the children of the caller's chain (parent) and updates
1115  * the blockref, restricted by sync_tid.
1116  *
1117  * Ripouts during the loop should not cause any problems.  Because we are
1118  * flushing to a synchronization point, modification races will occur after
1119  * sync_tid and do not have to be flushed anyway.
1120  *
1121  * It is also ok if the parent is chain_duplicate()'d while unlocked because
1122  * the delete/duplication will install a delete_tid that is still larger than
1123  * our current sync_tid.
1124  *
1125  * WARNING! If we do not call chain_flush_core we must update bref.mirror_tid
1126  *          ourselves.
1127  */
1128 static int
1129 hammer2_chain_flush_scan1(hammer2_chain_t *child, void *data)
1130 {
1131         hammer2_flush_info_t *info = data;
1132         hammer2_trans_t *trans = info->trans;
1133         hammer2_chain_t *parent = info->parent;
1134         int     diddeferral;
1135
1136         if (hammer2_debug & 0x80000)
1137                 Debugger("hell3");
1138         diddeferral = info->diddeferral;
1139
1140         /*
1141          * Child is beyond the flush synchronization zone, don't persue.
1142          * Remember that modifications generally delete-duplicate so if the
1143          * sub-tree is dirty another child will get us there.  But not this
1144          * one.
1145          *
1146          * Or MODIFIED is not set and child is already fully synchronized
1147          * with its sub-tree.  Don't persue.
1148          *
1149          * (child can never be fchain or vchain so a special check isn't
1150          *  needed).
1151          */
1152         if (child->modify_tid > trans->sync_tid) {
1153                 KKASSERT(child->delete_tid >= child->modify_tid);
1154                 /* do not update child->core->update_lo, core not flushed */
1155                 /* do not update core->update_lo, there may be another path */
1156                 /* do not update mirror_tid, scan2 will ignore chain */
1157                 return (0);
1158         }
1159
1160         /*
1161          * We must ref the child before unlocking the spinlock.
1162          *
1163          * The caller has added a ref to the parent so we can temporarily
1164          * unlock it in order to lock the child.
1165          */
1166         hammer2_chain_ref(child);
1167         spin_unlock(&parent->core->cst.spin);
1168
1169         hammer2_chain_unlock(parent);
1170         hammer2_chain_lock(child, HAMMER2_RESOLVE_MAYBE);
1171
1172         /*
1173          * No recursion needed if neither the child or anything under it
1174          * was messed with.
1175          */
1176         if ((child->flags & HAMMER2_CHAIN_MODIFIED) == 0 &&
1177             child->core->update_lo >= info->sync_tid) {
1178                 KKASSERT((child->flags & HAMMER2_CHAIN_MODIFIED) == 0);
1179                 if (child->bref.mirror_tid < info->sync_tid)
1180                         child->bref.mirror_tid = info->sync_tid;
1181                 goto skip;
1182         }
1183
1184         /*
1185          * XXX delete child if parent is deleted.  Propagate deletion
1186          *     downward.  TODO
1187          */
1188
1189
1190         /*
1191          * Re-check original pre-lock conditions after locking.
1192          */
1193         if (child->modify_tid > trans->sync_tid) {
1194                 hammer2_chain_unlock(child);
1195                 hammer2_chain_drop(child);
1196                 hammer2_chain_lock(parent, HAMMER2_RESOLVE_MAYBE);
1197                 spin_lock(&parent->core->cst.spin);
1198                 return (0);
1199         }
1200
1201         if ((child->flags & HAMMER2_CHAIN_MODIFIED) == 0 &&
1202             child->core->update_lo >= info->sync_tid) {
1203                 KKASSERT((child->flags & HAMMER2_CHAIN_MODIFIED) == 0);
1204                 if (child->bref.mirror_tid < info->sync_tid)
1205                         child->bref.mirror_tid = info->sync_tid;
1206                 goto skip;
1207         }
1208
1209         /*
1210          * Recurse and collect deferral data.
1211          */
1212         ++info->depth;
1213         hammer2_chain_flush_core(info, &child);
1214         --info->depth;
1215
1216 skip:
1217         /*
1218          * Check the conditions that could cause SCAN2 to modify the parent.
1219          * Modify the parent here instead of in SCAN2, which would cause
1220          * rollup chicken-and-egg races.
1221          *
1222          * Scan2 is expected to update bref.mirror_tid in the domodify case,
1223          * but will skip the child otherwise giving us the responsibility to
1224          * update bref.mirror_tid.
1225          *
1226          * WARNING!  Do NOT update the child's bref.mirror_tid right here,
1227          *           even if there was no deferral.  Doing so would cause
1228          *           confusion with the child's block array state in a
1229          *           future flush.
1230          */
1231         if (h2ignore_deleted(info, parent)) {
1232                 /*
1233                  * Special optimization matching similar tests done in
1234                  * flush_core, scan1, and scan2.  Avoid updating the block
1235                  * table in the parent if the parent is no longer visible.
1236                  */
1237                 ;
1238         } else if (child->delete_tid <= trans->sync_tid &&
1239                    child->delete_tid > parent->bref.mirror_tid &&
1240                    child->modify_tid <= parent->bref.mirror_tid) {
1241                 info->domodify = 1;
1242         } else if (child->delete_tid > trans->sync_tid &&
1243                    child->modify_tid > parent->bref.mirror_tid) {
1244                 info->domodify = 1;             /* base insertion */
1245         }
1246
1247         /*
1248          * Relock to continue the loop
1249          */
1250         hammer2_chain_unlock(child);
1251         hammer2_chain_lock(parent, HAMMER2_RESOLVE_MAYBE);
1252         hammer2_chain_drop(child);
1253         KKASSERT(info->parent == parent);
1254
1255         spin_lock(&parent->core->cst.spin);
1256         return (0);
1257 }
1258
1259 /*
1260  * Flush helper scan2 (non-recursive)
1261  *
1262  * This pass on a chain's children propagates any MOVED or DELETED
1263  * elements back up the chain towards the root after those elements have
1264  * been fully flushed.  Unlike scan1, this function is NOT recursive and
1265  * the parent remains locked across the entire scan.
1266  *
1267  * SCAN2 is called twice, once with pass set to 1 and once with it set to 2.
1268  * We have to do this so base[] elements can be deleted in pass 1 to make
1269  * room for adding new elements in pass 2.
1270  *
1271  * This function also rolls up storage statistics.
1272  *
1273  * NOTE!  A deletion is a visbility issue, there can still be references to
1274  *        deleted elements (for example, to an unlinked file which is still
1275  *        open), and there can also be multiple chains pointing to the same
1276  *        bref where some are deleted and some are not (for example due to
1277  *        a rename).   So a chain marked for deletion is basically considered
1278  *        to be live until it is explicitly destroyed or until its ref-count
1279  *        reaches zero (also implying that MOVED and MODIFIED are clear).
1280  *
1281  * NOTE!  Info->parent will be locked but will only be instantiated/modified
1282  *        if it is either MODIFIED or if scan1 determined that block table
1283  *        updates will occur.
1284  *
1285  * NOTE!  SCAN2 is responsible for updating child->bref.mirror_tid only in
1286  *        the case where it modifies the parent (does a base insertion
1287  *        or deletion).  SCAN1 handled all other cases.
1288  */
1289 static int
1290 hammer2_chain_flush_scan2(hammer2_chain_t *child, void *data)
1291 {
1292         hammer2_flush_info_t *info = data;
1293         hammer2_chain_t *parent = info->parent;
1294         hammer2_chain_core_t *above = child->above;
1295         hammer2_mount_t *hmp = child->hmp;
1296         hammer2_trans_t *trans = info->trans;
1297         hammer2_blockref_t *base;
1298         int count;
1299         int ok;
1300
1301 #if FLUSH_DEBUG
1302         kprintf("SCAN2 %p.%d %08x mod=%016jx del=%016jx trans=%016jx\n", child, child->bref.type, child->flags, child->modify_tid, child->delete_tid, info->trans->sync_tid);
1303 #endif
1304         /*
1305          * Ignore children created after our flush point, treating them as
1306          * if they did not exist).  These children will not cause the parent
1307          * to be updated.
1308          *
1309          * Children deleted after our flush point are treated as having been
1310          * created for the purposes of the flush.  The parent's update_hi
1311          * will already be higher than our trans->sync_tid so the path for
1312          * the next flush is left intact.
1313          *
1314          * When we encounter such children and the parent chain has not been
1315          * deleted, delete/duplicated, or delete/duplicated-for-move, then
1316          * the parent may be used to funnel through several flush points.
1317          * These chains will still be visible to later flushes due to having
1318          * a higher update_hi than we can set in the current flush.
1319          */
1320         if (child->modify_tid > trans->sync_tid) {
1321                 KKASSERT(child->delete_tid >= child->modify_tid);
1322                 goto finalize;
1323         }
1324
1325 #if 0
1326         /*
1327          * Ignore children which have not changed.  The parent's block table
1328          * is already correct.
1329          *
1330          * XXX The MOVED bit is only cleared when all multi-homed parents
1331          *     have flushed, creating a situation where a re-flush can occur
1332          *     via a parent which has already flushed.  The hammer2_base_*()
1333          *     functions currently have a hack to deal with this case but
1334          *     we need something better.
1335          */
1336         if ((child->flags & HAMMER2_CHAIN_MOVED) == 0) {
1337                 KKASSERT((child->flags & HAMMER2_CHAIN_MODIFIED) == 0);
1338                 goto finalize;
1339         }
1340 #endif
1341
1342         /*
1343          * Make sure child is referenced before we unlock.
1344          */
1345         hammer2_chain_ref(child);
1346         spin_unlock(&above->cst.spin);
1347
1348         /*
1349          * Parent reflushed after the child has passed them by should skip
1350          * due to the modify_tid test. XXX
1351          */
1352         hammer2_chain_lock(child, HAMMER2_RESOLVE_NEVER);
1353         KKASSERT(child->above == above);
1354         KKASSERT(parent->core == above);
1355
1356         /*
1357          * The parent's blockref to the child must be deleted or updated.
1358          *
1359          * This point is not reached on successful DELETED optimizations
1360          * but can be reached on recursive deletions and restricted flushes.
1361          *
1362          * The chain_modify here may delete-duplicate the block.  This can
1363          * cause a multitude of issues if the block was already modified
1364          * by a later (post-flush) transaction.  Primarily blockrefs in
1365          * the later block can be out-of-date, so if the situation occurs
1366          * we can't throw away the MOVED bit on the current blocks until
1367          * the later blocks are flushed (so as to be able to regenerate all
1368          * the changes that were made).
1369          *
1370          * Because flushes are ordered we do not have to make a
1371          * modify/duplicate of indirect blocks.  That is, the flush
1372          * code does not have to kmalloc or duplicate anything.  We
1373          * can adjust the indirect block table in-place and reuse the
1374          * chain.  It IS possible that the chain has already been duplicated
1375          * or may wind up being duplicated on-the-fly by modifying code
1376          * on the frontend.  We simply use the original and ignore such
1377          * chains.  However, it does mean we can't clear the MOVED bit.
1378          *
1379          * XXX recursive deletions not optimized.
1380          */
1381
1382         switch(parent->bref.type) {
1383         case HAMMER2_BREF_TYPE_INODE:
1384                 /*
1385                  * Access the inode's block array.  However, there is no
1386                  * block array if the inode is flagged DIRECTDATA.  The
1387                  * DIRECTDATA case typicaly only occurs when a hardlink has
1388                  * been shifted up the tree and the original inode gets
1389                  * replaced with an OBJTYPE_HARDLINK placeholding inode.
1390                  */
1391                 if (parent->data &&
1392                     (parent->data->ipdata.op_flags &
1393                      HAMMER2_OPFLAG_DIRECTDATA) == 0) {
1394                         base = &parent->data->ipdata.u.blockset.blockref[0];
1395                 } else {
1396                         base = NULL;
1397                 }
1398                 count = HAMMER2_SET_COUNT;
1399                 break;
1400         case HAMMER2_BREF_TYPE_INDIRECT:
1401         case HAMMER2_BREF_TYPE_FREEMAP_NODE:
1402                 if (parent->data)
1403                         base = &parent->data->npdata[0];
1404                 else
1405                         base = NULL;
1406                 count = parent->bytes / sizeof(hammer2_blockref_t);
1407                 break;
1408         case HAMMER2_BREF_TYPE_VOLUME:
1409                 base = &hmp->voldata.sroot_blockset.blockref[0];
1410                 count = HAMMER2_SET_COUNT;
1411                 break;
1412         case HAMMER2_BREF_TYPE_FREEMAP:
1413                 base = &parent->data->npdata[0];
1414                 count = HAMMER2_SET_COUNT;
1415                 break;
1416         default:
1417                 base = NULL;
1418                 count = 0;
1419                 panic("hammer2_chain_flush_scan2: "
1420                       "unrecognized blockref type: %d",
1421                       parent->bref.type);
1422         }
1423
1424         /*
1425          * Don't bother updating a deleted parent's blockrefs.
1426          *
1427          * Otherwise, we need to be COUNTEDBREFS synchronized for the
1428          * hammer2_base_*() functions.
1429          *
1430          * This test must match the similar one in flush_core.
1431          */
1432 #if FLUSH_DEBUG
1433         kprintf("SCAN2 base=%p pass=%d PARENT %p.%d DTID=%016jx SYNC=%016jx\n",
1434                 base,
1435                 info->pass, parent, parent->bref.type, parent->delete_tid, trans->sync_tid);
1436 #endif
1437         if (h2ignore_deleted(info, parent))
1438                 base = NULL;
1439
1440         /*
1441          * Update the parent's blockref table and propagate mirror_tid.
1442          *
1443          * NOTE! Children with modify_tid's beyond our flush point are
1444          *       considered to not exist for the purposes of updating the
1445          *       parent's blockref array.
1446          *
1447          * NOTE! SCAN1 has already put the parent in a modified state
1448          *       so if it isn't we panic.
1449          *
1450          * NOTE! chain->modify_tid vs chain->bref.modify_tid.  The chain's
1451          *       internal modify_tid is always updated based on creation
1452          *       or delete-duplicate.  However, the bref.modify_tid is NOT
1453          *       updated due to simple blockref updates.
1454          */
1455 #if FLUSH_DEBUG
1456         kprintf("chain %p->%p pass %d trans %016jx sync %p.%d %016jx/%d C=%016jx D=%016jx PMIRROR %016jx\n",
1457                 parent, child,
1458                 info->pass, trans->sync_tid,
1459                 child, child->bref.type,
1460                 child->bref.key, child->bref.keybits,
1461                 child->modify_tid, child->delete_tid, parent->bref.mirror_tid);
1462 #endif
1463
1464         if (info->pass == 1 && child->delete_tid <= trans->sync_tid) {
1465                 /*
1466                  * Deleting.  The block array is expected to contain the
1467                  * child's entry if:
1468                  *
1469                  * (1) The deletion occurred after the parent's block table
1470                  *     was last synchronized (delete_tid), and
1471                  *
1472                  * (2) The creation occurred before or during the parent's
1473                  *     last block table synchronization.
1474                  */
1475 #if FLUSH_DEBUG
1476                 kprintf("S2A %p.%d b=%p d/b=%016jx/%016jx m/b=%016jx/%016jx\n",
1477                         child, child->bref.type,
1478                         base, child->delete_tid, parent->bref.mirror_tid,
1479                         child->modify_tid, parent->bref.mirror_tid);
1480 #endif
1481                 if (base &&
1482                     child->delete_tid > parent->bref.mirror_tid &&
1483                     child->modify_tid <= parent->bref.mirror_tid) {
1484                         KKASSERT(child->flags & HAMMER2_CHAIN_MOVED);
1485                         KKASSERT(parent->modify_tid == trans->sync_tid ||
1486                                  (parent == &hmp->vchain ||
1487                                   parent == &hmp->fchain));
1488                         hammer2_rollup_stats(parent, child, -1);
1489                         spin_lock(&above->cst.spin);
1490 #if FLUSH_DEBUG
1491                         kprintf("trans %jx parent %p.%d child %p.%d m/d %016jx/%016jx "
1492                                 "flg=%08x %016jx/%d delete\n",
1493                                 trans->sync_tid,
1494                                 parent, parent->bref.type,
1495                                 child, child->bref.type,
1496                                 child->modify_tid, child->delete_tid,
1497                                 child->flags,
1498                                 child->bref.key, child->bref.keybits);
1499 #endif
1500                         hammer2_base_delete(trans, parent, base, count,
1501                                             &info->cache_index, child);
1502                         spin_unlock(&above->cst.spin);
1503                 }
1504         } else if (info->pass == 2 && child->delete_tid > trans->sync_tid) {
1505                 /*
1506                  * Inserting.  The block array is expected to NOT contain
1507                  * the child's entry if:
1508                  *
1509                  * (1) The creation occurred after the parent's block table
1510                  *     was last synchronized (modify_tid), and
1511                  *
1512                  * (2) The child is not being deleted in the same
1513                  *     transaction.
1514                  */
1515 #if FLUSH_DEBUG
1516                 kprintf("S2B %p.%d b=%p d/b=%016jx/%016jx m/b=%016jx/%016jx\n",
1517                         child, child->bref.type,
1518                         base, child->delete_tid, parent->bref.mirror_tid,
1519                         child->modify_tid, parent->bref.mirror_tid);
1520 #endif
1521                 if (base &&
1522                     child->modify_tid > parent->bref.mirror_tid) {
1523                         KKASSERT(child->flags & HAMMER2_CHAIN_MOVED);
1524                         KKASSERT(parent->modify_tid == trans->sync_tid ||
1525                                  (parent == &hmp->vchain ||
1526                                   parent == &hmp->fchain));
1527                         hammer2_rollup_stats(parent, child, 1);
1528                         spin_lock(&above->cst.spin);
1529 #if FLUSH_DEBUG
1530                         kprintf("trans %jx parent %p.%d child %p.%d m/d %016jx/%016jx "
1531                                 "flg=%08x %016jx/%d insert\n",
1532                                 trans->sync_tid,
1533                                 parent, parent->bref.type,
1534                                 child, child->bref.type,
1535                                 child->modify_tid, child->delete_tid,
1536                                 child->flags,
1537                                 child->bref.key, child->bref.keybits);
1538 #endif
1539                         hammer2_base_insert(trans, parent, base, count,
1540                                             &info->cache_index, child);
1541                         spin_unlock(&above->cst.spin);
1542                 }
1543         } else if (info->pass == 3 &&
1544                    (child->delete_tid == HAMMER2_MAX_TID ||
1545                     child->delete_tid <= trans->sync_tid) &&
1546                    (child->flags & HAMMER2_CHAIN_MOVED)) {
1547                 /*
1548                  * We can't clear the MOVED bit on children whos modify_tid
1549                  * is beyond our current trans (was tested at top of scan2),
1550                  * or on deleted children which have not yet been flushed
1551                  * (handled above).
1552                  *
1553                  * Scan all parents of this child and determine if any of
1554                  * them still need the child's MOVED bit.
1555                  */
1556                 hammer2_chain_t *scan;
1557
1558                 if (hammer2_debug & 0x4000)
1559                         kprintf("CHECKMOVED %p (parent=%p)", child, parent);
1560
1561                 ok = 1;
1562                 spin_lock(&above->cst.spin);
1563                 TAILQ_FOREACH(scan, &above->ownerq, core_entry) {
1564                         /*
1565                          * Can't clear child's MOVED until all parent's have
1566                          * synchronized with it.
1567                          *
1568                          * Ignore deleted parents as-of this flush TID.
1569                          * Ignore the current parent being flushed.
1570                          */
1571                         if (h2ignore_deleted(info, scan))
1572                                 continue;
1573                         if (scan == parent)
1574                                 continue;
1575
1576                         /*
1577                          * For parents not already synchronized check to see
1578                          * if the flush has gotten past them yet or not.
1579                          *
1580                          * This must roughly mimic the tests that
1581                          * hammer2_chain_flush_core() runs or we could leave
1582                          * children hanging around with MOVED set and cause
1583                          * a memory leak.
1584                          */
1585                         if (scan->bref.mirror_tid >= trans->sync_tid)
1586                                 continue;
1587                         if (scan->bref.mirror_tid >= above->update_hi)
1588                                 continue;
1589
1590                         if (hammer2_debug & 0x4000) {
1591                                 kprintf("(fail scan %p %016jx/%016jx)",
1592                                         scan, scan->bref.mirror_tid,
1593                                         child->modify_tid);
1594                         }
1595                         ok = 0;
1596                         break;
1597                 }
1598                 if (hammer2_debug & 0x4000)
1599                         kprintf("\n");
1600                 spin_unlock(&above->cst.spin);
1601
1602                 /*
1603                  * Can we finally clear MOVED?
1604                  */
1605                 if (ok) {
1606                         if (hammer2_debug & 0x4000)
1607                                 kprintf("clear moved %p.%d %016jx/%d\n",
1608                                         child, child->bref.type,
1609                                         child->bref.key, child->bref.keybits);
1610                         atomic_clear_int(&child->flags, HAMMER2_CHAIN_MOVED);
1611                         if (child->flags & HAMMER2_CHAIN_MODIFIED) {
1612                                 kprintf("modified child %p all parents updated\n",
1613                                         child);
1614                                 atomic_clear_int(&child->flags,
1615                                                  HAMMER2_CHAIN_MODIFIED);
1616                                 hammer2_chain_memory_wakeup(child->pmp);
1617                                 hammer2_chain_drop(child);/* cleared MODIFIED */
1618                         }
1619                         hammer2_chain_drop(child);      /* cleared MOVED */
1620                 } else {
1621                         if (hammer2_debug & 0x4000)
1622                                 kprintf("keep  moved %p.%d %016jx/%d\n",
1623                                         child, child->bref.type,
1624                                         child->bref.key, child->bref.keybits);
1625                 }
1626         }
1627
1628         /*
1629          * Unlock the child.  This can wind up dropping the child's
1630          * last ref, removing it from the parent's RB tree, and deallocating
1631          * the structure.  The RB_SCAN() our caller is doing handles the
1632          * situation.
1633          */
1634         hammer2_chain_unlock(child);
1635         hammer2_chain_drop(child);
1636         spin_lock(&above->cst.spin);
1637
1638         /*
1639          * The parent may have been delete-duplicated.
1640          */
1641         info->parent = parent;
1642 finalize:
1643         return (0);
1644 }
1645
1646 /*
1647  * Update core->update_lo and attempt to clear the MOVED bit
1648  * for its children.
1649  *
1650  * This routine is only called after a sub-tree has been fully flushed
1651  * up to the current flush synchronization point.  Calling it under any
1652  * other condition will blow up flush tracking.
1653  */
1654 static
1655 void
1656 hammer2_flush_core_update(hammer2_chain_core_t *core,
1657                           hammer2_flush_info_t *info)
1658 {
1659         hammer2_chain_layer_t *layer;
1660
1661         spin_lock(&core->cst.spin);
1662         if (core->update_lo < info->sync_tid)
1663                 core->update_lo = info->sync_tid;
1664         TAILQ_FOREACH_REVERSE(layer, &core->layerq,
1665                               h2_layer_list, entry) {
1666                 info->pass = 3;
1667                 ++layer->refs;
1668                 KKASSERT(layer->good == 0xABCD);
1669                 RB_SCAN(hammer2_chain_tree, &layer->rbtree,
1670                         NULL, hammer2_chain_flush_scan2, info);
1671                 --layer->refs;
1672                 KKASSERT(info->parent->core == core);
1673         }
1674         spin_unlock(&core->cst.spin);
1675 }
1676
1677 static
1678 void
1679 hammer2_rollup_stats(hammer2_chain_t *parent, hammer2_chain_t *child, int how)
1680 {
1681 #if 0
1682         hammer2_chain_t *grandp;
1683 #endif
1684
1685         parent->data_count += child->data_count;
1686         parent->inode_count += child->inode_count;
1687         child->data_count = 0;
1688         child->inode_count = 0;
1689         if (how < 0) {
1690                 parent->data_count -= child->bytes;
1691                 if (child->bref.type == HAMMER2_BREF_TYPE_INODE) {
1692                         parent->inode_count -= 1;
1693 #if 0
1694                         /* XXX child->data may be NULL atm */
1695                         parent->data_count -= child->data->ipdata.data_count;
1696                         parent->inode_count -= child->data->ipdata.inode_count;
1697 #endif
1698                 }
1699         } else if (how > 0) {
1700                 parent->data_count += child->bytes;
1701                 if (child->bref.type == HAMMER2_BREF_TYPE_INODE) {
1702                         parent->inode_count += 1;
1703 #if 0
1704                         /* XXX child->data may be NULL atm */
1705                         parent->data_count += child->data->ipdata.data_count;
1706                         parent->inode_count += child->data->ipdata.inode_count;
1707 #endif
1708                 }
1709         }
1710         if (parent->bref.type == HAMMER2_BREF_TYPE_INODE) {
1711                 parent->data->ipdata.data_count += parent->data_count;
1712                 parent->data->ipdata.inode_count += parent->inode_count;
1713 #if 0
1714                 for (grandp = parent->above->first_parent;
1715                      grandp;
1716                      grandp = grandp->next_parent) {
1717                         grandp->data_count += parent->data_count;
1718                         grandp->inode_count += parent->inode_count;
1719                 }
1720 #endif
1721                 parent->data_count = 0;
1722                 parent->inode_count = 0;
1723         }
1724 }