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 --- Commits in this patchset: * common/fuzzy: stress directory tree modifications with the dirtree tester * scrub: test correction of directory tree corruptions --- 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
