On Fri, 2022-12-30 at 14:10 -0800, Darrick J. Wong wrote: > From: Darrick J. Wong <djwong@xxxxxxxxxx> > > Writes to an XFS filesystem employ an eventual consistency update > model > to break up complex multistep metadata updates into small chained > transactions. This is generally good for performance and scalability > because XFS doesn't need to prepare for enormous transactions, but it > also means that online fsck must be careful not to attempt a fsck > action > unless it can be shown that there are no other threads processing a > transaction chain. This part of the design documentation covers the > thinking behind the consistency model and how scrub deals with it. > > Signed-off-by: Darrick J. Wong <djwong@xxxxxxxxxx> > --- > .../filesystems/xfs-online-fsck-design.rst | 303 > ++++++++++++++++++++ > 1 file changed, 303 insertions(+) > > > diff --git a/Documentation/filesystems/xfs-online-fsck-design.rst > b/Documentation/filesystems/xfs-online-fsck-design.rst > index f45bf97fa9c4..419eb54ee200 100644 > --- a/Documentation/filesystems/xfs-online-fsck-design.rst > +++ b/Documentation/filesystems/xfs-online-fsck-design.rst > @@ -1443,3 +1443,306 @@ This step is critical for enabling system > administrator to monitor the status > of the filesystem and the progress of any repairs. > For developers, it is a useful means to judge the efficacy of error > detection > and correction in the online and offline checking tools. > + > +Eventual Consistency vs. Online Fsck > +------------------------------------ > + > +Midway through the development of online scrubbing, the fsstress > tests > +uncovered a misinteraction between online fsck and compound > transaction chains > +created by other writer threads that resulted in false reports of > metadata > +inconsistency. > +The root cause of these reports is the eventual consistency model > introduced by > +the expansion of deferred work items and compound transaction chains > when > +reverse mapping and reflink were introduced. > + > +Originally, transaction chains were added to XFS to avoid deadlocks > when > +unmapping space from files. > +Deadlock avoidance rules require that AGs only be locked in > increasing order, > +which makes it impossible (say) to use a single transaction to free > a space > +extent in AG 7 and then try to free a now superfluous block mapping > btree block > +in AG 3. > +To avoid these kinds of deadlocks, XFS creates Extent Freeing Intent > (EFI) log > +items to commit to freeing some space in one transaction while > deferring the > +actual metadata updates to a fresh transaction. > +The transaction sequence looks like this: > + > +1. The first transaction contains a physical update to the file's > block mapping > + structures to remove the mapping from the btree blocks. > + It then attaches to the in-memory transaction an action item to > schedule > + deferred freeing of space. > + Concretely, each transaction maintains a list of ``struct > + xfs_defer_pending`` objects, each of which maintains a list of > ``struct > + xfs_extent_free_item`` objects. > + Returning to the example above, the action item tracks the > freeing of both > + the unmapped space from AG 7 and the block mapping btree (BMBT) > block from > + AG 3. > + Deferred frees recorded in this manner are committed in the log > by creating > + an EFI log item from the ``struct xfs_extent_free_item`` object > and > + attaching the log item to the transaction. > + When the log is persisted to disk, the EFI item is written into > the ondisk > + transaction record. > + EFIs can list up to 16 extents to free, all sorted in AG order. > + > +2. The second transaction contains a physical update to the free > space btrees > + of AG 3 to release the former BMBT block and a second physical > update to the > + free space btrees of AG 7 to release the unmapped file space. > + Observe that the the physical updates are resequenced in the > correct order > + when possible. > + Attached to the transaction is a an extent free done (EFD) log > item. > + The EFD contains a pointer to the EFI logged in transaction #1 so > that log > + recovery can tell if the EFI needs to be replayed. > + > +If the system goes down after transaction #1 is written back to the > filesystem > +but before #2 is committed, a scan of the filesystem metadata would > show > +inconsistent filesystem metadata because there would not appear to > be any owner > +of the unmapped space. > +Happily, log recovery corrects this inconsistency for us -- when > recovery finds > +an intent log item but does not find a corresponding intent done > item, it will > +reconstruct the incore state of the intent item and finish it. > +In the example above, the log must replay both frees described in > the recovered > +EFI to complete the recovery phase. > + > +There are two subtleties to XFS' transaction chaining strategy to > consider. > +The first is that log items must be added to a transaction in the > correct order > +to prevent conflicts with principal objects that are not held by the > +transaction. > +In other words, all per-AG metadata updates for an unmapped block > must be > +completed before the last update to free the extent, and extents > should not > +be reallocated until that last update commits to the log. > +The second subtlety comes from the fact that AG header buffers are > (usually) > +released between each transaction in a chain. > +This means that other threads can observe an AG in an intermediate > state, > +but as long as the first subtlety is handled, this should not affect > the > +correctness of filesystem operations. > +Unmounting the filesystem flushes all pending work to disk, which > means that > +offline fsck never sees the temporary inconsistencies caused by > deferred work > +item processing. > +In this manner, XFS employs a form of eventual consistency to avoid > deadlocks > +and increase parallelism. > + > +During the design phase of the reverse mapping and reflink features, > it was > +decided that it was impractical to cram all the reverse mapping > updates for a > +single filesystem change into a single transaction because a single > file > +mapping operation can explode into many small updates: > + > +* The block mapping update itself > +* A reverse mapping update for the block mapping update > +* Fixing the freelist > +* A reverse mapping update for the freelist fix > + > +* A shape change to the block mapping btree > +* A reverse mapping update for the btree update > +* Fixing the freelist (again) > +* A reverse mapping update for the freelist fix > + > +* An update to the reference counting information > +* A reverse mapping update for the refcount update > +* Fixing the freelist (a third time) > +* A reverse mapping update for the freelist fix > + > +* Freeing any space that was unmapped and not owned by any other > file > +* Fixing the freelist (a fourth time) > +* A reverse mapping update for the freelist fix > + > +* Freeing the space used by the block mapping btree > +* Fixing the freelist (a fifth time) > +* A reverse mapping update for the freelist fix > + > +Free list fixups are not usually needed more than once per AG per > transaction > +chain, but it is theoretically possible if space is very tight. > +For copy-on-write updates this is even worse, because this must be > done once to > +remove the space from a staging area and again to map it into the > file! > + > +To deal with this explosion in a calm manner, XFS expands its use of > deferred > +work items to cover most reverse mapping updates and all refcount > updates. > +This reduces the worst case size of transaction reservations by > breaking the > +work into a long chain of small updates, which increases the degree > of eventual > +consistency in the system. > +Again, this generally isn't a problem because XFS orders its > deferred work > +items carefully to avoid resource reuse conflicts between > unsuspecting threads. > + > +However, online fsck changes the rules -- remember that although > physical > +updates to per-AG structures are coordinated by locking the buffers > for AG > +headers, buffer locks are dropped between transactions. > +Once scrub acquires resources and takes locks for a data structure, > it must do > +all the validation work without releasing the lock. > +If the main lock for a space btree is an AG header buffer lock, > scrub may have > +interrupted another thread that is midway through finishing a chain. > +For example, if a thread performing a copy-on-write has completed a > reverse > +mapping update but not the corresponding refcount update, the two AG > btrees > +will appear inconsistent to scrub and an observation of corruption > will be > +recorded. This observation will not be correct. > +If a repair is attempted in this state, the results will be > catastrophic! > + > +Several solutions to this problem were evaluated upon discovery of > this flaw: Hmm, so while having a really in depth efi example is insightful, I wonder if it would be more oranized to put it in a separate document somewhere and just reference it. As far as ofsck is concerned, I think a lighter sumary would do: "Complex operations that modify multiple AGs are performed through a series of transactions which are logged to a journal that an offline fsck can either replay or discard. Online fsck however, must be able to deal with these operations while they are still in progress. This presents a unique challenge for ofsck since a partially completed transaction chain may present the appearance of inconsistencies, even though the operations are functioning as intended. (For a more detailed example, see <cite document here...>) The challenge then becomes how to avoid incorrectly repairing these non-issues as doing so would cause more harm than help." > + > +1. Add a higher level lock to allocation groups and require writer > threads to > + acquire the higher level lock in AG order before making any > changes. > + This would be very difficult to implement in practice because it > is > + difficult to determine which locks need to be obtained, and in > what order, > + without simulating the entire operation. > + Performing a dry run of a file operation to discover necessary > locks would > + make the filesystem very slow. > + > +2. Make the deferred work coordinator code aware of consecutive > intent items > + targeting the same AG and have it hold the AG header buffers > locked across > + the transaction roll between updates. > + This would introduce a lot of complexity into the coordinator > since it is > + only loosely coupled with the actual deferred work items. > + It would also fail to solve the problem because deferred work > items can > + generate new deferred subtasks, but all subtasks must be complete > before > + work can start on a new sibling task. Hmm, that one doesnt seem like it's really an option then :-( > + > +3. Teach online fsck to walk all transactions waiting for whichever > lock(s) > + protect the data structure being scrubbed to look for pending > operations. > + The checking and repair operations must factor these pending > operations into > + the evaluations being performed. > + This solution is a nonstarter because it is *extremely* invasive > to the main > + filesystem. > + > +4. Recognize that only online fsck has this requirement of total > consistency > + of AG metadata, and that online fsck should be relatively rare as > compared > + to filesystem change operations. > + For each AG, maintain a count of intent items targetting that AG. > + When online fsck wants to examine an AG, it should lock the AG > header > + buffers to quiesce all transaction chains that want to modify > that AG, and > + only proceed with the scrub if the count is zero. > + In other words, scrub only proceeds if it can lock the AG header > buffers and > + there can't possibly be any intents in progress. > + This may lead to fairness and starvation issues, but regular > filesystem > + updates take precedence over online fsck activity. So basically it sounds like 4 is the only reasonable option? If the discussion concerning the other options have died down, I would clean them out. They're great for brain storming and invitations for collaboration, but ideally the goal of any of that should be to narrow down an agreed upon plan of action. And the goal of your document should make clear what that plan is. So if no one has any objections by now, maybe just tie it right into the last line: "The challenge then becomes how to avoid incorrectly repairing these non-issues as doing so would cause more harm than help. Fortunately only online fsck has this requirement of total consistency..." > + > +Intent Drains > +````````````` > + > +The fourth solution is implemented in the current iteration of This solution is implemented... > online fsck, > +with atomic_t providing the active intent counter. > + > +There are two key properties to the drain mechanism. > +First, the counter is incremented when a deferred work item is > *queued* to a > +transaction, and it is decremented after the associated intent done > log item is > +*committed* to another transaction. > +The second property is that deferred work can be added to a > transaction without > +holding an AG header lock, but per-AG work items cannot be marked > done without > +locking that AG header buffer to log the physical updates and the > intent done > +log item. > +The first property enables scrub to yield to running transaction > chains, which > +is an explicit deprioritization of online fsck to benefit file > operations. > +The second property of the drain is key to the correct coordination > of scrub, > +since scrub will always be able to decide if a conflict is possible. > + > +For regular filesystem code, the drain works as follows: > + > +1. Call the appropriate subsystem function to add a deferred work > item to a > + transaction. > + > +2. The function calls ``xfs_drain_bump`` to increase the counter. > + > +3. When the deferred item manager wants to finish the deferred work > item, it > + calls ``->finish_item`` to complete it. > + > +4. The ``->finish_item`` implementation logs some changes and calls > + ``xfs_drain_drop`` to decrease the sloppy counter and wake up any > threads > + waiting on the drain. > + > +5. The subtransaction commits, which unlocks the resource associated > with the > + intent item. > + > +For scrub, the drain works as follows: > + > +1. Lock the resource(s) associated with the metadata being scrubbed. > + For example, a scan of the refcount btree would lock the AGI and > AGF header > + buffers. > + > +2. If the counter is zero (``xfs_drain_busy`` returns false), there > are no > + chains in progress and the operation may proceed. > + > +3. Otherwise, release the resources grabbed in step 1. > + > +4. Wait for the intent counter to reach zero > (``xfs_drain_intents``), then go > + back to step 1 unless a signal has been caught. > + > +To avoid polling in step 4, the drain provides a waitqueue for scrub > threads to > +be woken up whenever the intent count drops to zero. I think all that makes sense > + > +The proposed patchset is the > +`scrub intent drain series > +< > https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/ > log/?h=scrub-drain-intents>`_. > + > +.. _jump_labels: > + > +Static Keys (aka Jump Label Patching) > +````````````````````````````````````` > + > +Online fsck for XFS separates the regular filesystem from the > checking and > +repair code as much as possible. > +However, there are a few parts of online fsck (such as the intent > drains, and > +later, live update hooks) where it is useful for the online fsck > code to know > +what's going on in the rest of the filesystem. > +Since it is not expected that online fsck will be constantly running > in the > +background, it is very important to minimize the runtime overhead > imposed by > +these hooks when online fsck is compiled into the kernel but not > actively > +running on behalf of userspace. > +Taking locks in the hot path of a writer thread to access a data > structure only > +to find that no further action is necessary is expensive -- on the > author's > +computer, this have an overhead of 40-50ns per access. > +Fortunately, the kernel supports dynamic code patching, which > enables XFS to > +replace a static branch to hook code with ``nop`` sleds when online > fsck isn't > +running. > +This sled has an overhead of however long it takes the instruction > decoder to > +skip past the sled, which seems to be on the order of less than 1ns > and > +does not access memory outside of instruction fetching. > + > +When online fsck enables the static key, the sled is replaced with > an > +unconditional branch to call the hook code. > +The switchover is quite expensive (~22000ns) but is paid entirely by > the > +program that invoked online fsck, and can be amortized if multiple > threads > +enter online fsck at the same time, or if multiple filesystems are > being > +checked at the same time. > +Changing the branch direction requires taking the CPU hotplug lock, > and since > +CPU initialization requires memory allocation, online fsck must be > careful not > +to change a static key while holding any locks or resources that > could be > +accessed in the memory reclaim paths. > +To minimize contention on the CPU hotplug lock, care should be taken > not to > +enable or disable static keys unnecessarily. > + > +Because static keys are intended to minimize hook overhead for > regular > +filesystem operations when xfs_scrub is not running, the intended > usage > +patterns are as follows: > + > +- The hooked part of XFS should declare a static-scoped static key > that > + defaults to false. > + The ``DEFINE_STATIC_KEY_FALSE`` macro takes care of this. > + The static key itself should be declared as a ``static`` variable. > + > +- When deciding to invoke code that's only used by scrub, the > regular > + filesystem should call the ``static_branch_unlikely`` predicate to > avoid the > + scrub-only hook code if the static key is not enabled. > + > +- The regular filesystem should export helper functions that call > + ``static_branch_inc`` to enable and ``static_branch_dec`` to > disable the > + static key. > + Wrapper functions make it easy to compile out the relevant code if > the kernel > + distributor turns off online fsck at build time. > + > +- Scrub functions wanting to turn on scrub-only XFS functionality > should call > + the ``xchk_fshooks_enable`` from the setup function to enable a > specific > + hook. > + This must be done before obtaining any resources that are used by > memory > + reclaim. > + Callers had better be sure they really need the functionality > gated by the > + static key; the ``TRY_HARDER`` flag is useful here. > + > +Online scrub has resource acquisition helpers (e.g. > ``xchk_perag_lock``) to > +handle locking AGI and AGF buffers for all scrubber functions. > +If it detects a conflict between scrub and the running transactions, > it will > +try to wait for intents to complete. > +If the caller of the helper has not enabled the static key, the > helper will > +return -EDEADLOCK, which should result in the scrub being restarted > with the > +``TRY_HARDER`` flag set. > +The scrub setup function should detect that flag, enable the static > key, and > +try the scrub again. > +Scrub teardown disables all static keys obtained by > ``xchk_fshooks_enable``. Ok, this part here seems pretty well documented. Organizing nits aside I think it looks good. Allison > + > +For more information, please see the kernel documentation of > +Documentation/staging/static-keys.rst. >
