Determining Block Liveness

Let's explore how LFS determines whether a segment is live or not.

We'll cover the following

Segment summary block

Given a data block DD within an on-disk segment SS, LFS must be able to determine whether DD 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 DD, 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 DD located on disk at address AA, look in the segment summary block and find its inode number NN and offset TT. Next, look in the imap to find where NN lives and read NN from disk (perhaps it is already in memory, which is even better). Finally, using the offset TT, 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 AA, LFS can conclude that the block DD is live. If it points anywhere else, LFS can conclude that DD is not in use (i.e., it is dead) and thus know that this version is no longer needed.

Here is a pseudocode summary:

Get hands-on with 1200+ tech skills courses.