Determining Block Liveness

Segment summary block

Given a data block $D$ within an on-disk segment $S$, LFS must be able to determine whether $D$ is live. To do so, LFS adds a little extra information to each segment that describes each block. Specifically, LFS includes, for each data block $D$, its inode number (which file it belongs to) and its offset (which block of the file this is). This information is recorded in a structure at the head of the segment known as the segment summary block.

Given this information, it is straightforward to determine whether a block is live or dead. For a block $D$ located on disk at address $A$, look in the segment summary block and find its inode number $N$ and offset $T$. Next, look in the imap to find where $N$ lives and read $N$ from disk (perhaps it is already in memory, which is even better). Finally, using the offset $T$, look in the inode (or some indirect block) to see where the inode thinks the Tth block of this file is on disk. If it points exactly to the disk address $A$, LFS can conclude that the block $D$ is live. If it points anywhere else, LFS can conclude that $D$ is not in use (i.e., it is dead) and thus know that this version is no longer needed.

Here is a pseudocode summary: