Page MenuHomeFreeBSD
Files F174170482

D60139.diff
No OneTemporary
Actions

D60139.diff
View Options

diff --git a/etc/mtree/BSD.tests.dist b/etc/mtree/BSD.tests.dist
--- a/etc/mtree/BSD.tests.dist
+++ b/etc/mtree/BSD.tests.dist
@@ -491,6 +491,8 @@
..
dhclient
..
+ fsck_ffs
+ ..
fsck_msdosfs
..
growfs
diff --git a/sbin/fsck_ffs/Makefile b/sbin/fsck_ffs/Makefile
--- a/sbin/fsck_ffs/Makefile
+++ b/sbin/fsck_ffs/Makefile
@@ -1,3 +1,5 @@
+.include <src.opts.mk>
+
PACKAGE=ufs
PROG= fsck_ffs
LINKS+= ${BINDIR}/fsck_ffs ${BINDIR}/fsck_ufs
@@ -13,4 +15,7 @@
.PATH: ${SRCTOP}/sys/ufs/ffs
+HAS_TESTS=
+SUBDIR.${MK_TESTS}+= tests
+
.include <bsd.prog.mk>
diff --git a/sbin/fsck_ffs/dir.c b/sbin/fsck_ffs/dir.c
--- a/sbin/fsck_ffs/dir.c
+++ b/sbin/fsck_ffs/dir.c
@@ -60,6 +60,17 @@
static int lftempname(char *bufp, ino_t ino);
static int mkentry(struct inodesc *);
+/*
+ * Where makeentry() last added an entry to lost+found. Reconnecting
+ * orphans appends to it over and over, and scanning it from the start
+ * for every entry makes that quadratic, so the next entry is looked for
+ * starting at that block. See makeentry().
+ */
+static ino_t mkentry_dir;
+static uint64_t mkentry_gen;
+static ufs_lbn_t mkentry_lbn;
+static ufs_lbn_t mkentry_startlbn;
+
/*
* Propagate connected state through the tree.
*/
@@ -208,6 +219,11 @@
idesc->id_filesize -= blksiz;
return (SKIP);
}
+ /* Skip, without reading them, the blocks makeentry() is not after. */
+ if (idesc->id_func == mkentry && idesc->id_lbn < mkentry_startlbn) {
+ idesc->id_filesize -= blksiz;
+ return (idesc->id_filesize > 0 ? KEEPON : STOP);
+ }
idesc->id_loc = 0;
for (dp = fsck_readdir(idesc); dp != NULL; dp = fsck_readdir(idesc)) {
dsize = dp->d_reclen;
@@ -753,18 +769,35 @@
DIP_SET(dp, di_size, roundup(DIP(dp, di_size), DIRBLKSIZ));
inodirty(&ip);
}
- if ((ckinode(dp, &idesc) & ALTERED) != 0) {
- irelse(&ip);
- free(idesc.id_name);
- return (1);
+ /*
+ * When adding to lost+found again, start looking for room in the
+ * block that got the previous entry, as long as the directory still
+ * has that block. Room freed in earlier blocks is not reused then,
+ * which only costs space.
+ */
+ mkentry_startlbn = 0;
+ if (parent == lfdir && parent == mkentry_dir &&
+ DIP(dp, di_gen) == mkentry_gen &&
+ mkentry_lbn < howmany(DIP(dp, di_size), sblock.fs_bsize))
+ mkentry_startlbn = mkentry_lbn;
+ retval = ckinode(dp, &idesc) & ALTERED;
+ if (retval == 0) {
+ getpathname(pathbuf, parent, parent);
+ if (expanddir(&ip, pathbuf) != 0) {
+ retval = ckinode(dp, &idesc) & ALTERED;
+ /* Not expected, but fall back to a full scan. */
+ if (retval == 0 && mkentry_startlbn != 0) {
+ mkentry_startlbn = 0;
+ retval = ckinode(dp, &idesc) & ALTERED;
+ }
+ }
}
- getpathname(pathbuf, parent, parent);
- if (expanddir(&ip, pathbuf) == 0) {
- irelse(&ip);
- free(idesc.id_name);
- return (0);
+ if (retval != 0 && parent == lfdir) {
+ mkentry_dir = parent;
+ mkentry_gen = DIP(dp, di_gen);
+ mkentry_lbn = idesc.id_lbn;
}
- retval = ckinode(dp, &idesc) & ALTERED;
+ mkentry_startlbn = 0;
irelse(&ip);
free(idesc.id_name);
return (retval);
diff --git a/sbin/fsck_ffs/tests/Makefile b/sbin/fsck_ffs/tests/Makefile
new file mode 100644
--- /dev/null
+++ b/sbin/fsck_ffs/tests/Makefile
@@ -0,0 +1,5 @@
+PACKAGE= tests
+
+ATF_TESTS_SH= lost_found_test
+
+.include <bsd.test.mk>
diff --git a/sbin/fsck_ffs/tests/lost_found_test.sh b/sbin/fsck_ffs/tests/lost_found_test.sh
new file mode 100644
--- /dev/null
+++ b/sbin/fsck_ffs/tests/lost_found_test.sh
@@ -0,0 +1,93 @@
+#
+# SPDX-License-Identifier: BSD-2-Clause
+#
+# Copyright (c) 2026 Maksym Sobolyev <sobomax@sippysoft.com>
+#
+
+# Tests for fsck_ffs(8) reconnecting orphaned inodes into lost+found.
+#
+# The orphans are made by building a file system image with makefs(8) that
+# holds a directory full of entries and clearing that directory's inode with
+# clri(8). None of this needs root: fsck_ffs(8) checks the image file
+# directly.
+
+IMG=ffs.img
+
+# Build $IMG with directory "d" holding $1 empty files and $2 directories,
+# each of those with one file in it, and clear the inode of "d". Small
+# blocks make lost+found span many blocks with few entries.
+make_orphans()
+{
+ local ino
+
+ rm -rf root ${IMG}
+ mkdir -p root/d
+ (cd root/d && jot "$1" | xargs touch)
+ if [ "$2" -gt 0 ]; then
+ (cd root/d && jot "$2" | sed 's/^/dir/' | xargs mkdir)
+ (cd root/d && jot "$2" | sed 's|^\(.*\)$|dir\1/f|' | xargs touch)
+ fi
+ atf_check -o ignore makefs -t ffs -o version=2,bsize=4096,fsize=512 \
+ -s 64m ${IMG} root
+ ino=$(printf 'ls\n' | fsdb -r ${IMG} 2>/dev/null |
+ awk '/directory, `d'"'"'$/ { print $6 }')
+ atf_check test -n "${ino}"
+ atf_check -o ignore -e ignore clri ${IMG} ${ino}
+}
+
+# Repair $IMG, check that $1 inodes were reconnected and that the file
+# system is clean afterwards, and set LOOKUPS to the number of block
+# lookups fsck_ffs(8) made, taken from its debug statistics.
+repair()
+{
+ atf_check -o save:fsck.out -e ignore fsck_ffs -d -fy ${IMG}
+ atf_check -o inline:"$1\n" grep -c 'RECONNECT? yes' fsck.out
+ atf_check -o not-match:'UNREF' -e ignore fsck_ffs -fn ${IMG}
+ LOOKUPS=$(sed -n 's/^cache with .* missed [0-9]* of \([0-9]*\) .*/\1/p' \
+ fsck.out)
+ atf_check test -n "${LOOKUPS}"
+}
+
+atf_test_case reconnect_files
+reconnect_files_head()
+{
+ atf_set "descr" "Reconnecting orphans must not rescan lost+found " \
+ "for every inode"
+ atf_set "require.progs" "makefs fsdb clri fsck_ffs jot"
+}
+reconnect_files_body()
+{
+ local l1 l2
+
+ make_orphans 1000 0
+ repair 1000
+ l1=${LOOKUPS}
+ make_orphans 2000 0
+ repair 2000
+ l2=${LOOKUPS}
+ # Rescanning lost+found for every orphan makes the number of lookups
+ # grow with the square of the number of orphans: doubling them about
+ # quadruples it. Without rescans it about doubles.
+ if [ $((l2 * 10)) -ge $((l1 * 30)) ]; then
+ atf_fail "lookups went from ${l1} for 1000 orphans to" \
+ "${l2} for 2000"
+ fi
+}
+
+atf_test_case reconnect_dirs
+reconnect_dirs_head()
+{
+ atf_set "descr" "Orphaned files and directories are all reconnected"
+ atf_set "require.progs" "makefs fsdb clri fsck_ffs jot"
+}
+reconnect_dirs_body()
+{
+ make_orphans 2000 200
+ repair 2200
+}
+
+atf_init_test_cases()
+{
+ atf_add_test_case reconnect_files
+ atf_add_test_case reconnect_dirs
+}

File Metadata

Mime Type
text/plain
Expires
Fri, Oct 2, 3:03 AM (17 h, 55 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
39988380
Default Alt Text
D60139.diff (6 KB)

Event Timeline