Summary
makeentry() looks for room for a new entry by scanning the directory from its first block. When the directory is full, it expands it and scans it from the first block again.
Reconnecting orphans only ever appends to lost+found. So every reconnect reads the whole, growing directory once or twice, and reconnecting n inodes costs O(n^2) block reads.
A file system with many orphans can keep fsck busy for hours, rereading the same blocks from memory at hundreds of MB/s. A crash under heavy file creation and removal on a soft updates file system checked with -f leaves exactly that. In one stress2 gnop9.sh run on SU+J, a single fsck_ffs -fy pass spent about 30 minutes reconnecting more than 150,000 zero-length orphans.
The fix: remember the block of lost+found that received the last entry, and start the next search there. dirscan() skips the earlier blocks without reading them.
- Scope: the hint is used only for lost+found (lfdir). It is identified by inode number and generation, so it cannot carry over to another directory or to another file system checked by the same process. It is used only while the directory still has that block.
- Orphaned directories: writing their ".." does not disturb the hint, because only inserts into lost+found update it.
- Fallback: should the search still fail after expanding the directory, makeentry() scans it from the start, as before.
- Cost: room freed in lost+found before the hinted block is not reused, which only costs space.
The second commit adds sbin/fsck_ffs/tests/lost_found_test.sh, the first tests for fsck_ffs.
Git branch: https://github.com/sobomax/freebsd/tree/fsck-lfdir-hint
Files: sbin/fsck_ffs/dir.c (+43 -10); sbin/fsck_ffs/tests/ (new), sbin/fsck_ffs/Makefile, etc/mtree/BSD.tests.dist.
Test Plan
New test
lost_found_test needs no root. It builds a UFS2 image with 4 KB blocks with makefs(8), holding a directory of empty files and optionally subdirectories. It clears the directory's inode with clri(8) and runs fsck_ffs on the image file.
- reconnect_files: reconnects 1000 and then 2000 orphans, and checks that every one is reconnected and that fsck_ffs -fn is clean afterwards. It fails if the number of block lookups reported by fsck_ffs -d grows 3 times or more for twice the orphans. That count depends only on what fsck does, not on the speed of the machine.
- reconnect_dirs: 2000 files plus 200 directories, all reconnected, including rewriting each directory's "..", followed by a clean fsck_ffs -fn.
| fsck_ffs | lookups, 1000 orphans | lookups, 2000 orphans | reconnect_files | reconnect_dirs |
|---|---|---|---|---|
| before | 506,116 | 2,016,303 (x3.98) | fails | passes |
| after | 129,796 | 260,143 (x2.00) | passes | passes |
Each case takes about a second.
Timing
The images were made the same way on md(4) devices, with 32 KB blocks, and repaired with fsck_ffs -fy, using the change applied to fsck_ffs:
| orphans | before | after |
|---|---|---|
| 30,000 files | 17 s | 2 s |
| 20,000 files + 2,000 directories | 12 s | 4 s |
| 90,000 files | 168 s | 5 s |
In every case the resulting lost+found was identical between the two versions, including the ".." of each reconnected directory (compared with a sorted listing), and fsck_ffs -n found the file system clean afterwards.
Stress testing
During stress2 runs (gnop7.sh, gnop9.sh and fsck6.sh on soft updates and SU+J), the patched binary was installed as /sbin/fsck_ffs, and as fsck_ffs.exp for the tests that look for it. Every fsck it ran in those tests got the file system marked clean. The gnop9.sh cycles that followed the 30-minute stock pass mentioned above finished within minutes.