From: "Darrick J. Wong" <djwong@kernel.org>
To: chandanbabu@kernel.org, djwong@kernel.org
Cc: Christoph Hellwig <hch@lst.de>, hch@lst.de, linux-xfs@vger.kernel.org
Subject: [PATCH 4/4] docs: describe xfs directory tree online fsck
Date: Mon, 15 Apr 2024 16:57:28 -0700 [thread overview]
Message-ID: <171322386179.91896.3455401757230848909.stgit@frogsfrogsfrogs> (raw)
In-Reply-To: <171322386102.91896.17539357886365049977.stgit@frogsfrogsfrogs>
From: Darrick J. Wong <djwong@kernel.org>
I've added a scrubber that checks the directory tree structure and fixes
them; describe this in the design documentation.
Signed-off-by: Darrick J. Wong <djwong@kernel.org>
Reviewed-by: Christoph Hellwig <hch@lst.de>
---
.../filesystems/xfs/xfs-online-fsck-design.rst | 124 ++++++++++++++++++++
1 file changed, 124 insertions(+)
diff --git a/Documentation/filesystems/xfs/xfs-online-fsck-design.rst b/Documentation/filesystems/xfs/xfs-online-fsck-design.rst
index 70e3e629d8b3..12aa63840830 100644
--- a/Documentation/filesystems/xfs/xfs-online-fsck-design.rst
+++ b/Documentation/filesystems/xfs/xfs-online-fsck-design.rst
@@ -4785,6 +4785,130 @@ This scan would have to be converted into a multi-pass scan:
This code has not yet been constructed.
+.. _dirtree:
+
+Case Study: Directory Tree Structure
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+As mentioned earlier, the filesystem directory tree is supposed to be a
+directed acylic graph structure.
+However, each node in this graph is a separate ``xfs_inode`` object with its
+own locks, which makes validating the tree qualities difficult.
+Fortunately, non-directories are allowed to have multiple parents and cannot
+have children, so only directories need to be scanned.
+Directories typically constitute 5-10% of the files in a filesystem, which
+reduces the amount of work dramatically.
+
+If the directory tree could be frozen, it would be easy to discover cycles and
+disconnected regions by running a depth (or breadth) first search downwards
+from the root directory and marking a bitmap for each directory found.
+At any point in the walk, trying to set an already set bit means there is a
+cycle.
+After the scan completes, XORing the marked inode bitmap with the inode
+allocation bitmap reveals disconnected inodes.
+However, one of online repair's design goals is to avoid locking the entire
+filesystem unless it's absolutely necessary.
+Directory tree updates can move subtrees across the scanner wavefront on a live
+filesystem, so the bitmap algorithm cannot be applied.
+
+Directory parent pointers enable an incremental approach to validation of the
+tree structure.
+Instead of using one thread to scan the entire filesystem, multiple threads can
+walk from individual subdirectories upwards towards the root.
+For this to work, all directory entries and parent pointers must be internally
+consistent, each directory entry must have a parent pointer, and the link
+counts of all directories must be correct.
+Each scanner thread must be able to take the IOLOCK of an alleged parent
+directory while holding the IOLOCK of the child directory to prevent either
+directory from being moved within the tree.
+This is not possible since the VFS does not take the IOLOCK of a child
+subdirectory when moving that subdirectory, so instead the scanner stabilizes
+the parent -> child relationship by taking the ILOCKs and installing a dirent
+update hook to detect changes.
+
+The scanning process uses a dirent hook to detect changes to the directories
+mentioned in the scan data.
+The scan works as follows:
+
+1. For each subdirectory in the filesystem,
+
+ a. For each parent pointer of that subdirectory,
+
+ 1. Create a path object for that parent pointer, and mark the
+ subdirectory inode number in the path object's bitmap.
+
+ 2. Record the parent pointer name and inode number in a path structure.
+
+ 3. If the alleged parent is the subdirectory being scrubbed, the path is
+ a cycle.
+ Mark the path for deletion and repeat step 1a with the next
+ subdirectory parent pointer.
+
+ 4. Try to mark the alleged parent inode number in a bitmap in the path
+ object.
+ If the bit is already set, then there is a cycle in the directory
+ tree.
+ Mark the path as a cycle and repeat step 1a with the next subdirectory
+ parent pointer.
+
+ 5. Load the alleged parent.
+ If the alleged parent is not a linked directory, abort the scan
+ because the parent pointer information is inconsistent.
+
+ 6. For each parent pointer of this alleged ancestor directory,
+
+ a. Record the parent pointer name and inode number in the path object
+ if no parent has been set for that level.
+
+ b. If an ancestor has more than one parent, mark the path as corrupt.
+ Repeat step 1a with the next subdirectory parent pointer.
+
+ c. Repeat steps 1a3-1a6 for the ancestor identified in step 1a6a.
+ This repeats until the directory tree root is reached or no parents
+ are found.
+
+ 7. If the walk terminates at the root directory, mark the path as ok.
+
+ 8. If the walk terminates without reaching the root, mark the path as
+ disconnected.
+
+2. If the directory entry update hook triggers, check all paths already found
+ by the scan.
+ If the entry matches part of a path, mark that path and the scan stale.
+ When the scanner thread sees that the scan has been marked stale, it deletes
+ all scan data and starts over.
+
+Repairing the directory tree works as follows:
+
+1. Walk each path of the target subdirectory.
+
+ a. Corrupt paths and cycle paths are counted as suspect.
+
+ b. Paths already marked for deletion are counted as bad.
+
+ c. Paths that reached the root are counted as good.
+
+2. If the subdirectory is either the root directory or has zero link count,
+ delete all incoming directory entries in the immediate parents.
+ Repairs are complete.
+
+3. If the subdirectory has exactly one path, set the dotdot entry to the
+ parent and exit.
+
+4. If the subdirectory has at least one good path, delete all the other
+ incoming directory entries in the immediate parents.
+
+5. If the subdirectory has no good paths and more than one suspect path, delete
+ all the other incoming directory entries in the immediate parents.
+
+6. If the subdirectory has zero paths, attach it to the lost and found.
+
+The proposed patches are in the
+`directory tree repair
+<https://git.kernel.org/pub/scm/linux/kernel/git/djwong/xfs-linux.git/log/?h=scrub-directory-tree>`_
+series.
+
+
.. _orphanage:
The Orphanage
next prev parent reply other threads:[~2024-04-15 23:57 UTC|newest]
Thread overview: 103+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-15 23:28 [PATCHBOMB v30.3] xfs: online repair, part 1 is done Darrick J. Wong
2024-04-15 23:33 ` [PATCHSET v30.3 01/16] xfs: improve log incompat feature handling Darrick J. Wong
2024-04-15 23:37 ` [PATCH 1/5] xfs: pass xfs_buf lookup flags to xfs_*read_agi Darrick J. Wong
2024-04-15 23:38 ` [PATCH 2/5] xfs: fix an AGI lock acquisition ordering problem in xrep_dinode_findmode Darrick J. Wong
2024-04-15 23:38 ` [PATCH 3/5] xfs: fix potential AGI <-> ILOCK ABBA deadlock in xrep_dinode_findmode_walk_directory Darrick J. Wong
2024-04-15 23:38 ` [PATCH 4/5] xfs: fix error bailout in xrep_abt_build_new_trees Darrick J. Wong
2024-04-15 23:38 ` [PATCH 5/5] xfs: only clear log incompat flags at clean unmount Darrick J. Wong
2024-04-15 23:34 ` [PATCHSET v30.3 02/16] xfs: refactorings for atomic file content exchanges Darrick J. Wong
2024-04-15 23:39 ` [PATCH 1/7] xfs: move inode lease breaking functions to xfs_inode.c Darrick J. Wong
2024-04-15 23:39 ` [PATCH 2/7] xfs: move xfs_iops.c declarations out of xfs_inode.h Darrick J. Wong
2024-04-15 23:39 ` [PATCH 3/7] xfs: declare xfs_file.c symbols in xfs_file.h Darrick J. Wong
2024-04-15 23:40 ` [PATCH 4/7] xfs: create a new helper to return a file's allocation unit Darrick J. Wong
2024-04-15 23:40 ` [PATCH 5/7] xfs: hoist multi-fsb allocation unit detection to a helper Darrick J. Wong
2024-04-15 23:40 ` [PATCH 6/7] xfs: refactor non-power-of-two alignment checks Darrick J. Wong
2024-04-15 23:40 ` [PATCH 7/7] xfs: constify xfs_bmap_is_written_extent Darrick J. Wong
2024-04-15 23:34 ` [PATCHSET v30.3 03/16] xfs: atomic file content exchanges Darrick J. Wong
2024-04-15 23:41 ` [PATCH 01/15] vfs: export remap and write check helpers Darrick J. Wong
2024-04-15 23:41 ` [PATCH 02/15] xfs: introduce new file range exchange ioctl Darrick J. Wong
2024-04-15 23:41 ` [PATCH 03/15] xfs: create a incompat flag for atomic file mapping exchanges Darrick J. Wong
2024-04-15 23:41 ` [PATCH 04/15] xfs: introduce a file mapping exchange log intent item Darrick J. Wong
2024-04-15 23:42 ` [PATCH 05/15] xfs: create deferred log items for file mapping exchanges Darrick J. Wong
2024-04-15 23:42 ` [PATCH 06/15] xfs: bind together the front and back ends of the file range exchange code Darrick J. Wong
2024-04-15 23:42 ` [PATCH 07/15] xfs: add error injection to test file mapping exchange recovery Darrick J. Wong
2024-04-15 23:42 ` [PATCH 08/15] xfs: condense extended attributes after a mapping exchange operation Darrick J. Wong
2024-04-15 23:43 ` [PATCH 09/15] xfs: condense directories " Darrick J. Wong
2024-04-15 23:43 ` [PATCH 10/15] xfs: condense symbolic links " Darrick J. Wong
2024-04-15 23:43 ` [PATCH 11/15] xfs: make file range exchange support realtime files Darrick J. Wong
2024-04-15 23:43 ` [PATCH 12/15] xfs: support non-power-of-two rtextsize with exchange-range Darrick J. Wong
2024-04-15 23:44 ` [PATCH 13/15] xfs: capture inode generation numbers in the ondisk exchmaps log item Darrick J. Wong
2024-04-15 23:44 ` [PATCH 14/15] docs: update swapext -> exchmaps language Darrick J. Wong
2024-04-15 23:44 ` [PATCH 15/15] xfs: enable logged file mapping exchange feature Darrick J. Wong
2024-04-15 23:34 ` [PATCHSET v30.3 04/16] xfs: create temporary files for online repair Darrick J. Wong
2024-04-15 23:44 ` [PATCH 1/4] xfs: hide private inodes from bulkstat and handle functions Darrick J. Wong
2024-04-15 23:45 ` [PATCH 2/4] xfs: create temporary files and directories for online repair Darrick J. Wong
2024-04-15 23:45 ` [PATCH 3/4] xfs: refactor live buffer invalidation for repairs Darrick J. Wong
2024-04-15 23:45 ` [PATCH 4/4] xfs: add the ability to reap entire inode forks Darrick J. Wong
2024-04-15 23:34 ` [PATCHSET v30.3 05/16] xfs: online repair of realtime summaries Darrick J. Wong
2024-04-15 23:46 ` [PATCH 1/3] xfs: support preallocating and copying content into temporary files Darrick J. Wong
2024-04-15 23:46 ` [PATCH 2/3] xfs: teach the tempfile to set up atomic file content exchanges Darrick J. Wong
2024-04-15 23:46 ` [PATCH 3/3] xfs: online repair of realtime summaries Darrick J. Wong
2024-04-15 23:35 ` [PATCHSET v30.3 06/16] xfs: set and validate dir/attr block owners Darrick J. Wong
2024-04-15 23:46 ` [PATCH 01/10] xfs: add an explicit owner field to xfs_da_args Darrick J. Wong
2024-04-15 23:47 ` [PATCH 02/10] xfs: use the xfs_da_args owner field to set new dir/attr block owner Darrick J. Wong
2024-04-15 23:47 ` [PATCH 03/10] xfs: reduce indenting in xfs_attr_node_list Darrick J. Wong
2024-04-15 23:47 ` [PATCH 04/10] xfs: validate attr leaf buffer owners Darrick J. Wong
2024-04-15 23:47 ` [PATCH 05/10] xfs: validate attr remote value " Darrick J. Wong
2024-04-15 23:48 ` [PATCH 06/10] xfs: validate dabtree node " Darrick J. Wong
2024-04-15 23:48 ` [PATCH 07/10] xfs: validate directory leaf " Darrick J. Wong
2024-04-15 23:48 ` [PATCH 08/10] xfs: validate explicit directory data " Darrick J. Wong
2024-04-15 23:48 ` [PATCH 09/10] xfs: validate explicit directory block " Darrick J. Wong
2024-04-15 23:49 ` [PATCH 10/10] xfs: validate explicit directory free block owners Darrick J. Wong
2024-04-15 23:35 ` [PATCHSET v30.3 07/16] xfs: online repair of extended attributes Darrick J. Wong
2024-04-15 23:49 ` [PATCH 1/7] xfs: enable discarding of folios backing an xfile Darrick J. Wong
2024-04-15 23:49 ` [PATCH 2/7] xfs: create a blob array data structure Darrick J. Wong
2024-04-15 23:49 ` [PATCH 3/7] xfs: use atomic extent swapping to fix user file fork data Darrick J. Wong
2024-04-15 23:50 ` [PATCH 4/7] xfs: repair extended attributes Darrick J. Wong
2024-04-15 23:50 ` [PATCH 5/7] xfs: scrub should set preen if attr leaf has holes Darrick J. Wong
2024-04-15 23:50 ` [PATCH 6/7] xfs: flag empty xattr leaf blocks for optimization Darrick J. Wong
2024-04-15 23:50 ` [PATCH 7/7] xfs: create an xattr iteration function for scrub Darrick J. Wong
2024-04-15 23:35 ` [PATCHSET v30.3 08/16] xfs: online repair of inode unlinked state Darrick J. Wong
2024-04-15 23:51 ` [PATCH 1/2] xfs: ensure unlinked list state is consistent with nlink during scrub Darrick J. Wong
2024-04-15 23:51 ` [PATCH 2/2] xfs: update the unlinked list when repairing link counts Darrick J. Wong
2024-04-15 23:35 ` [PATCHSET v30.3 09/16] xfs: online repair of directories Darrick J. Wong
2024-04-15 23:51 ` [PATCH 1/5] xfs: inactivate directory data blocks Darrick J. Wong
2024-04-15 23:52 ` [PATCH 2/5] xfs: online repair of directories Darrick J. Wong
2024-04-15 23:52 ` [PATCH 3/5] xfs: scan the filesystem to repair a directory dotdot entry Darrick J. Wong
2024-04-15 23:52 ` [PATCH 4/5] xfs: online repair of parent pointers Darrick J. Wong
2024-04-15 23:52 ` [PATCH 5/5] xfs: ask the dentry cache if it knows the parent of a directory Darrick J. Wong
2024-04-15 23:36 ` [PATCHSET v30.3 10/16] xfs: move orphan files to lost and found Darrick J. Wong
2024-04-15 23:53 ` [PATCH 1/3] xfs: move orphan files to the orphanage Darrick J. Wong
2024-04-15 23:53 ` [PATCH 2/3] xfs: move files to orphanage instead of letting nlinks drop to zero Darrick J. Wong
2024-04-15 23:53 ` [PATCH 3/3] xfs: ensure dentry consistency when the orphanage adopts a file Darrick J. Wong
2024-04-15 23:36 ` [PATCHSET v30.3 11/16] xfs: online repair of symbolic links Darrick J. Wong
2024-04-15 23:53 ` [PATCH 1/3] xfs: expose xfs_bmap_local_to_extents for online repair Darrick J. Wong
2024-04-15 23:54 ` [PATCH 2/3] xfs: pass the owner to xfs_symlink_write_target Darrick J. Wong
2024-04-15 23:54 ` [PATCH 3/3] xfs: online repair of symbolic links Darrick J. Wong
2024-04-15 23:36 ` [PATCHSET v30.3 12/16] xfs: online fsck of iunlink buckets Darrick J. Wong
2024-04-15 23:54 ` [PATCH 1/3] xfs: check AGI unlinked inode buckets Darrick J. Wong
2024-04-15 23:54 ` [PATCH 2/3] xfs: hoist AGI repair context to a heap object Darrick J. Wong
2024-04-15 23:55 ` [PATCH 3/3] xfs: repair AGI unlinked inode bucket lists Darrick J. Wong
2024-04-15 23:36 ` [PATCHSET v30.3 13/16] xfs: inode-related repair fixes Darrick J. Wong
2024-04-15 23:55 ` [PATCH 1/4] xfs: check unused nlink fields in the ondisk inode Darrick J. Wong
2024-04-15 23:55 ` [PATCH 2/4] xfs: try to avoid allocating from sick inode clusters Darrick J. Wong
2024-04-15 23:55 ` [PATCH 3/4] xfs: pin inodes that would otherwise overflow link count Darrick J. Wong
2024-04-15 23:56 ` [PATCH 4/4] xfs: create subordinate scrub contexts for xchk_metadata_inode_subtype Darrick J. Wong
2024-04-15 23:37 ` [PATCHSET v30.3 14/16] xfs: less heavy locks during fstrim Darrick J. Wong
2024-04-15 23:56 ` [PATCH 1/1] xfs: fix performance problems when fstrimming a subset of a fragmented AG Darrick J. Wong
2024-04-15 23:37 ` [PATCHSET v13.2 15/16] xfs: design documentation for online fsck, part 2 Darrick J. Wong
2024-04-15 23:56 ` [PATCH 1/4] docs: update the parent pointers documentation to the final version Darrick J. Wong
2024-04-15 23:56 ` [PATCH 2/4] docs: update online directory and parent pointer repair sections Darrick J. Wong
2024-04-15 23:57 ` [PATCH 3/4] docs: update offline parent pointer repair strategy Darrick J. Wong
2024-04-15 23:57 ` Darrick J. Wong [this message]
2024-04-15 23:37 ` [PATCHSET v13.2 16/16] xfs: retain ILOCK during directory updates Darrick J. Wong
2024-04-15 23:57 ` [PATCH 1/7] xfs: Increase XFS_DEFER_OPS_NR_INODES to 5 Darrick J. Wong
2024-04-15 23:57 ` [PATCH 2/7] xfs: Increase XFS_QM_TRANS_MAXDQS " Darrick J. Wong
2024-04-15 23:58 ` [PATCH 3/7] xfs: Hold inode locks in xfs_ialloc Darrick J. Wong
2024-04-15 23:58 ` [PATCH 4/7] xfs: Hold inode locks in xfs_trans_alloc_dir Darrick J. Wong
2024-04-15 23:58 ` [PATCH 5/7] xfs: Hold inode locks in xfs_rename Darrick J. Wong
2024-04-15 23:59 ` [PATCH 6/7] xfs: don't pick up IOLOCK during rmapbt repair scan Darrick J. Wong
2024-04-15 23:59 ` [PATCH 7/7] xfs: unlock new repair tempfiles after creation Darrick J. Wong
-- strict thread matches above, loose matches on Subject: below --
2024-04-10 0:44 [PATCHSET v13.1 1/9] xfs: design documentation for online fsck, part 2 Darrick J. Wong
2024-04-10 0:47 ` [PATCH 4/4] docs: describe xfs directory tree online fsck Darrick J. Wong
2024-04-10 4:40 ` Christoph Hellwig
2023-12-31 19:32 [PATCHSET v13.0 1/7] xfs: design documentation for online fsck, part 2 Darrick J. Wong
2023-12-31 20:43 ` [PATCH 4/4] docs: describe xfs directory tree online fsck Darrick J. Wong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=171322386179.91896.3455401757230848909.stgit@frogsfrogsfrogs \
--to=djwong@kernel.org \
--cc=chandanbabu@kernel.org \
--cc=hch@lst.de \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.