The earliest file systems took a lazy stance on crash consistency: let inconsistencies happen, then fix them at reboot. The classic tool for this is fsck fsck The file system checker: the old, lazy crash-consistency approach — let inconsistencies happen, then scan the whole disk at reboot and repair the metadata (rebuild bitmaps from inodes, fix link counts, clear bad pointers, move orphaned inodes to lost+found). Correct-ish but O(disk size), so far too slow on large modern volumes. defined in ch. 42 — open in glossary (“file system check”), which scans a disk partition for inconsistencies and repairs them.
42.2 The File System Checker
fsck runs before the file system is mounted, assuming no other file-system
activity is happening. Its goal is modest but important: make the file system’s
metadata internally consistent. (It cannot recover data — recall the
scenario where the inode and bitmap agree but the data block holds garbage;
fsck can’t even tell.) It works in phases:
| phase | what it checks | how it repairs | |
|---|---|---|---|
| Superblock | Superblock | sanity, e.g. the file-system size is ≥ the number of allocated blocks | if it looks corrupt, switch to an alternate superblock copy |
| Free blocks | Free blocks | scan all inodes, indirect blocks, etc. to learn which blocks are truly in use | rebuild the allocation bitmaps; on an inode-vs-bitmap disagreement, TRUST the inodes |
| Inode state | Inode state | each allocated inode has a valid type field (regular / directory / symlink) and no obvious corruption | clear suspect inodes and update the inode bitmap accordingly |
| Inode links | Inode links | recompute each inode's link count by walking the ENTIRE directory tree from the root | fix mismatched counts; an allocated inode no directory references → move to lost+found |
| Duplicates | Duplicates | two different inodes pointing at the same block (duplicate pointers) | clear the obviously-bad inode, or give each inode its own copy of the block |
| Bad blocks | Bad blocks | a pointer to an address outside the valid range (e.g. beyond the partition size) | just remove (clear) that pointer from the inode or indirect block |
| Directories | Directories | "." and ".." are the first entries, every referenced inode is allocated, no directory is linked more than once | repair the directory's integrity (fsck knows the directory format, unlike file contents) |
Building a correct fsck demands intricate knowledge of the file system, and
getting every case right is genuinely hard. But it has a deeper, fatal flaw:
it’s too slow.
The premise is irrational at scale. Our append changed three blocks — yet
fsck scans the entire disk and walks the whole directory tree to
repair it. Recovery is O(disk size), not O(update size), so on a large volume
it can take minutes or hours.
Aside: Searching The Whole House For Keys
It’s like dropping your keys on the floor of your bedroom, and then running a search-the-entire-house recovery algorithm — starting in the basement and working through every room. It works, but it’s absurdly wasteful. As disks (and RAIDs) grew, this cost became prohibitive, and people looked for a smarter approach — one whose work is proportional to the update, not the whole disk.Check yourself: the file system checker (fsck)
1.What is fsck's basic strategy for crash consistency?
2.When must fsck run, and what is its goal?
3.When fsck rebuilds the allocation bitmaps and finds a disagreement with the inodes, which does it trust?
4.During its link-count check, fsck finds an allocated inode that no directory references. What does it do?
5.What is the fundamental problem with fsck on modern systems?
6.The 'searching the whole house for keys' analogy captures which idea?