From: "Darrick J. Wong" <djwong@kernel.org>
To: zlang@redhat.com, djwong@kernel.org
Cc: linux-xfs@vger.kernel.org, guan@eryu.me, fstests@vger.kernel.org
Subject: [PATCHSET v13.0 2/3] xfs: detect and correct directory tree structures
Date: Sun, 31 Dec 2023 11:59:29 -0800 [thread overview]
Message-ID: <170405028893.1825187.7753896310306155652.stgit@frogsfrogsfrogs> (raw)
In-Reply-To: <20231231181849.GT361584@frogsfrogsfrogs>
Hi all,
Historically, checking the tree-ness of the directory tree structure has
not been complete. Cycles of subdirectories break the tree properties,
as do subdirectories with multiple parents. It's easy enough for DFS to
detect problems as long as one of the participants is reachable from the
root, but this technique cannot find unconnected cycles.
Directory parent pointers change that, because we can discover all of
these problems from a simple walk from a subdirectory towards the root.
For each child we start with, if the walk terminates without reaching
the root, we know the path is disconnected and ought to be attached to
the lost and found. If we find ourselves, we know this is a cycle and
can delete an incoming edge. If we find multiple paths to the root, we
know to delete an incoming edge.
Even better, once we've finished walking paths, we've identified the
good ones and know which other path(s) to remove.
If you're going to start using this code, I strongly recommend pulling
from my git trees, which are linked below.
This has been running on the djcloud for months with no problems. Enjoy!
Comments and questions are, as always, welcome.
--D
kernel git tree:
https://git.kernel.org/cgit/linux/kernel/git/djwong/xfs-linux.git/log/?h=scrub-directory-tree
xfsprogs git tree:
https://git.kernel.org/cgit/linux/kernel/git/djwong/xfsprogs-dev.git/log/?h=scrub-directory-tree
fstests git tree:
https://git.kernel.org/cgit/linux/kernel/git/djwong/xfstests-dev.git/log/?h=scrub-directory-tree
---
tests/xfs/1864 | 38 +++++++++++++
tests/xfs/1864.out | 2 +
tests/xfs/1865 | 38 +++++++++++++
tests/xfs/1865.out | 2 +
tests/xfs/1866 | 122 ++++++++++++++++++++++++++++++++++++++++
tests/xfs/1866.out | 19 ++++++
tests/xfs/1867 | 133 ++++++++++++++++++++++++++++++++++++++++++++
tests/xfs/1867.out | 25 ++++++++
tests/xfs/1868 | 121 ++++++++++++++++++++++++++++++++++++++++
tests/xfs/1868.out | 21 +++++++
tests/xfs/1869 | 157 ++++++++++++++++++++++++++++++++++++++++++++++++++++
tests/xfs/1869.out | 32 +++++++++++
tests/xfs/1870 | 146 ++++++++++++++++++++++++++++++++++++++++++++++++
tests/xfs/1870.out | 30 ++++++++++
tests/xfs/1871 | 78 ++++++++++++++++++++++++++
tests/xfs/1871.out | 2 +
16 files changed, 966 insertions(+)
create mode 100755 tests/xfs/1864
create mode 100644 tests/xfs/1864.out
create mode 100755 tests/xfs/1865
create mode 100644 tests/xfs/1865.out
create mode 100755 tests/xfs/1866
create mode 100644 tests/xfs/1866.out
create mode 100755 tests/xfs/1867
create mode 100644 tests/xfs/1867.out
create mode 100755 tests/xfs/1868
create mode 100644 tests/xfs/1868.out
create mode 100755 tests/xfs/1869
create mode 100644 tests/xfs/1869.out
create mode 100755 tests/xfs/1870
create mode 100644 tests/xfs/1870.out
create mode 100755 tests/xfs/1871
create mode 100644 tests/xfs/1871.out
next prev parent reply other threads:[~2023-12-31 19:59 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-12-31 18:18 [NYE PATCHRIVER 2/4] xfs: online repair part 2 Darrick J. Wong
2023-12-31 19:59 ` [PATCHSET v13.0 1/3] fstests: adjust tests for xfs parent pointers Darrick J. Wong
2023-12-27 13:46 ` [PATCH 01/11] generic: test recovery of extended attribute updates Darrick J. Wong
2023-12-27 13:46 ` [PATCH 02/11] xfs/206: filter out the parent= status from mkfs Darrick J. Wong
2023-12-27 13:47 ` [PATCH 03/11] xfs/122: update for parent pointers Darrick J. Wong
2023-12-27 13:47 ` [PATCH 04/11] populate: create hardlinks " Darrick J. Wong
2023-12-27 13:47 ` [PATCH 05/11] xfs/021: adapt golden output files " Darrick J. Wong
2023-12-27 13:47 ` [PATCH 06/11] xfs/{018,191,288}: disable parent pointers for this test Darrick J. Wong
2023-12-27 13:48 ` [PATCH 07/11] xfs/306: fix formatting failures with parent pointers Darrick J. Wong
2023-12-27 13:48 ` [PATCH 08/11] common: add helpers for parent pointer tests Darrick J. Wong
2023-12-27 13:48 ` [PATCH 09/11] xfs: add parent pointer test Darrick J. Wong
2023-12-27 13:48 ` [PATCH 10/11] xfs: add multi link " Darrick J. Wong
2023-12-27 13:49 ` [PATCH 11/11] xfs: add parent pointer inject test Darrick J. Wong
2023-12-31 19:59 ` Darrick J. Wong [this message]
2023-12-27 13:49 ` [PATCH 1/2] common/fuzzy: stress directory tree modifications with the dirtree tester Darrick J. Wong
2023-12-27 13:49 ` [PATCH 2/2] scrub: test correction of directory tree corruptions Darrick J. Wong
2023-12-31 19:59 ` [PATCHSET 3/3] xfs_scrub: vectorize kernel calls Darrick J. Wong
2023-12-27 13:49 ` [PATCH 1/1] xfs/122: update for vectored scrub 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=170405028893.1825187.7753896310306155652.stgit@frogsfrogsfrogs \
--to=djwong@kernel.org \
--cc=fstests@vger.kernel.org \
--cc=guan@eryu.me \
--cc=linux-xfs@vger.kernel.org \
--cc=zlang@redhat.com \
/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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox