A New Problem: Garbage Collection

You may have noticed another problem with LFS; it repeatedly writes the latest version of a file (including its inode and data) to new locations on disk. This process, while keeping writes efficient, implies that LFS leaves old versions of file structures scattered throughout the disk. We (rather unceremoniously) call these old versions garbage.

Examples

For example, let’s imagine the case where we have an existing file referred to by inode number $k$, which points to a single data block $D0$. We now update that block, generating both a new inode and a new data block. The resulting on-disk layout of ...