§43.4–43.8Finding Inodes: The Inode Map and Checkpoint Region

LFS writes everything sequentially — which creates a new problem: where did the inodes go?

43.4 The Problem: Finding Inodes

In FFS (or the old UNIX FS), inodes live in a fixed on-disk array, so you find one by simple arithmetic: address = start + inode_number × inode_size. In LFS, that’s impossible — inodes are scattered all over the disk, and since LFS never overwrites in place, an inode’s newest version keeps moving with every update.

43.5 The Inode Map (imap)

The fix is the classic one: a level of indirection. The inode map (imap) inode map The imap: LFS's level of indirection from inode number → the disk address of the most recent version of that inode. Since LFS scatters inodes across the disk and moves them on every write, the imap is how they're found; it's updated (and written) right alongside each segment. It also solves the recursive update problem. defined in ch. 43 — open in glossary maps an inode number to the disk address of that inode’s most recent version — a simple array with a 4-byte pointer per entry, updated whenever an inode is written. To avoid extra seeks, LFS doesn’t keep the imap at a fixed spot; it writes each imap chunk right next to the data and inode it describes, in the same segment.

43.6–43.7 The Checkpoint Region, and Reading

But if imap pieces are also scattered, how do we find them? There has to be one fixed place to start. That’s the checkpoint region (CR) checkpoint region The CR: a fixed, well-known disk location (LFS keeps two) that points to the latest pieces of the inode map — the starting point for finding everything. It's updated only periodically (~every 30 s) so it doesn't hurt performance; on reboot, LFS reads the CR to bootstrap recovery. defined in ch. 43 — open in glossary : a known location holding pointers to the latest imap pieces. Crucially, the CR is updated only periodically (~every 30 s), so it doesn’t add a seek to every write. Reading a file thus walks a chain of indirection:

43.8 What About Directories?

Directories work exactly as before — a directory is just a file whose data is a set of (name → inode number) mappings — and it’s written into the log too. Looking up foo walks the imap twice (once for the directory, once for the file):

The imap also quietly solves the recursive update problem recursive update problem A hazard in any never-overwrite-in-place file system: moving an inode to a new address would force updating the directory that points to it, then that directory's parent, and so on up to the root. LFS avoids it with the inode map — the directory keeps the same name→inode-number mapping, and only the imap entry changes. defined in ch. 43 — open in glossary : in any never-overwrite-in-place FS, moving an inode to a new address would force updating the directory that points to it — then that directory’s parent, and so on up to the root. LFS avoids the whole cascade because the directory stores only the inode number (unchanged); when the inode moves, only its imap entry is updated, not the directory.