fsck and the Ordering of Repairs

A filesystem’s allocation accounting has no redundancy. The block bitmap says which blocks are free, the inode table says which blocks each file owns, and the directory entries say which inodes are named. Nothing checks these three statements against each other during normal operation, and nothing can, because a check would cost as much as the operation. After a crash, or after a bug, they can disagree, and the tool that reconciles them is the consistency checker.

Why the passes have a dependency order

The passes cannot run in arbitrary order because each one produces a fact the next needs. The inode scan produces the set of blocks that are claimed; the bitmap reconciliation compares that set against the bitmap. Running the reconciliation first would produce a set of “free” blocks that the inode scan later contradicts, and the repair would have to be redone. Running the directory pass first would risk following an inode number that the inode scan has not yet validated.

The dependency order that follows is:

1. Superblock and geometry. Verify the fields agree and that the volume’s declared size matches the device.
2. Bitmap structure. Verify each group’s bitmap is structurally valid, that its set bits correspond to blocks within the group, and that the descriptors’ counts agree with the bits.
3. Inode scan. Walk every inode record in every group, validate its mode and link count, and follow its block map to build the set of claimed blocks.
4. Block reconciliation. Compare the claimed set against the bitmap. Blocks claimed but marked free are a contradiction; blocks marked used but claimed by nobody are leaked space.
5. Directory structure. Verify each directory’s entries are well formed, that each names an inode of a plausible type, and that no inode appears twice as a hard link in a way the link count does not explain.
6. Link counts. Walk the directory tree and count how many entries name each inode, then compare with the stored link count.
7. Orphan handling. Any inode that is allocated but unreachable from any directory is either attached to a recovery directory or freed.
8. Free counts. Recompute the free block and inode counts from the bitmaps and write them into the descriptors and the superblock.

The order is not arbitrary in the other direction either. Directory structure must be checked after the inode scan, because an entry naming an inode number outside the table, or one whose block map the scan has rejected, cannot be classified at all. It must be checked before link counting, because an entry whose record length is impossible makes the rest of its block unparseable, so a walk over that tree would miss references that are present and compute a count that is too low. Counting follows once the tree can be walked reliably.

The inode scan and the claimed-block set

The scan is the expensive pass. It reads every inode record on the volume, which for a volume with millions of inodes is millions of reads, and for each one it must follow the block map. A file with an extent tree requires reading the tree’s nodes; a file with indirect blocks requires reading each level. The cost follows the number of inodes and the size of their maps rather than the number of data blocks, which is why a volume holding a few large files checks faster than one holding millions of small ones.

What the pass produces is a bitmap of its own: a block is set in the in-memory map when some inode claims it. A block claimed twice is a collision, and a collision is the most serious finding the tool can make, because there is no correct repair. Two files cannot own the same bytes. The tool must choose which inode keeps the block and truncate the other, and truncating a file to remove a collision loses data that no other copy exists for.

The scan must also validate the map’s internal consistency, as described in Extent Trees and the Replacement of Indirect Block Maps: sorted logical numbers, no overlaps, physical ranges within the volume, and the sum of extents consistent with the size field. A map that fails these checks cannot be trusted to produce a correct claimed set, so the tool rebuilds it by truncating the file at the first inconsistency.

Comparing the two bitmaps

The reconciliation is a set difference in both directions. A block set in the claimed map but clear in the on-disk bitmap is allocated to a file and marked free; the repair sets the bit, because the file’s claim is the one backed by data. A block clear in the claimed map but set in the bitmap is allocated and unowned; the repair clears the bit, reclaiming the space.

The asymmetry in the repairs reflects the asymmetry in the risk. Clearing a bit that a file actually owns would allow a future allocation to overwrite file data, so the tool never clears a bit that any inode claims. Setting a bit costs a block of space, which is recoverable; clearing one costs data, which is not. When the tool is unsure whether a claim is real, it prefers to believe the claim.

The counters follow. Each group descriptor’s free-block count must equal the number of clear bits in that group’s bitmap. The tool recomputes the count rather than trusting it, because a wrong count is the failure mode described in Block Groups and the Cost of Metadata Locality: the allocator reads the counter, believes there is space, and allocates a block the bitmap says is in use.

/* The reconciliation, in one direction only: never clear a claimed bit. */
for (uint64_t b = sb->first_data_block; b < sb->blocks_count; b++) {
        uint64_t bit = b % sb->blocks_per_group;   /* offset within the bitmap */
        unsigned char *bm = group_bitmap(sb, b);
        int claimed = bitmap_test(claimed_map, b);
        int marked  = bitmap_test(bm, bit);
        if (claimed && !marked) {
                bitmap_set(bm, bit);
                desc[group_of(sb, b)].free_blocks--;
        } else if (!claimed && marked) {
                bitmap_clear(bm, bit);
                desc[group_of(sb, b)].free_blocks++;
        }
}

Link counts and the two ways to be wrong

A link count that is too high is harmless in the short term and leaks an inode in the long term: the file is deleted, the count decrements to a nonzero value, and the inode is never freed. A link count that is too low is dangerous: the file is deleted, the count reaches zero while a directory entry still names the inode, and the inode is freed and reused while a name still points at it. The next access through that name reads a different file.

The tool resolves both by recomputing. It walks the directory tree from the root, counting references to each inode. A count lower than the stored value means the inode has entries the tool did not see, which usually means a directory is corrupt or a subtree is unreachable; a count higher means entries are missing. In both cases the tool writes the computed count, because the directory tree is the authority on what is reachable, and reachability is what the count is supposed to represent.

The exception is an inode with a count of zero that the scan found allocated. Nothing names it, so by the count’s own definition it should be free, but it holds blocks and possibly data. The tool cannot know whether it is a file that was being written when the system crashed or a file whose directory entry was lost. Deleting it reclaims the space; keeping it preserves data that may be the only copy. The compromise is the orphan directory: the inode is linked into a directory at the root with a fixed name, given a plausible name derived from its number, and left for a human to inspect.

Directories and the limits of repair

Directory repair has fewer options than inode repair because a directory’s contents are its meaning. An entry whose rec_len is impossible makes the rest of the block unparseable, and the usual repair is to overwrite that field with the distance to the end of the block, converting the entry into one that spans the remainder and is skipped. Entries after the damaged one in that block are lost either way, because their offsets can no longer be reached. An entry naming an inode that is not allocated must be removed, because following it would read a free inode’s stale bytes. An entry naming an inode of the wrong type, such as a directory entry pointing at a regular file used as a directory, must also be removed.

The htree index described in Directory Hash Trees: Indexing Names Without Breaking Enumeration adds a second consistency requirement: the index must cover every leaf and the leaves must be sorted by hash. A tool can rebuild the index from the leaves, which costs a full scan of the directory but preserves the entries. A tool cannot rebuild the leaves from the index, because the index stores no names.

The final pass writes the recomputed counters and clears the state field that marked the volume as needing a check. A tool run in a mode that reports without repairing leaves that field set, and a mount of a volume in that state is at best forced and at worst refused, depending on the driver and the options given. Leaving the mark is the conservative outcome: the inconsistencies the check found are exactly the ones that turn into corruption under load, and the mark is what tells the next mount not to proceed as if nothing happened.

What the checker cannot see

The checker verifies that the metadata is self-consistent. It does not verify that file contents are correct. A block that was written with the wrong data, or a file whose blocks were reassigned by a bug that left the bitmap consistent, passes every pass. Detecting that requires checksums over data blocks, which is a separate mechanism, and the distinction between metadata consistency and data integrity is why a repaired filesystem can still return wrong bytes.

It also cannot distinguish a deliberate state from a damaged one. A sparse file’s hole and a lost extent look identical to the inode scan: both are ranges with no blocks. The size field and the extent map together describe the file as the filesystem believes it to be, and the tool has no independent record to compare against. Repair restores consistency with the recorded state, not with what the program intended, and that gap is the reason the orphan directory exists at all.