A New Problem: Garbage Collection

Let's discuss how LFS employs garbage collection to remove the outdated file structures on the disk, thus making room for subsequent writes.

We'll cover the following

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.


For example, let’s imagine the case where we have an existing file referred to by inode number kk, which points to a single data block D0D0. We now update that block, generating both a new inode and a new data block. The resulting on-disk layout of LFS would look something like this (note we omit the imap and other structures for simplicity; a new chunk of imap would also have to be written to disk to point to the new inode):

Get hands-on with 1200+ tech skills courses.