What About Directories?

The piece of the inode map contains the information for the location of both the directory file $dir$ as well as the newly-created file $f$. Thus, when accessing file foo (with inode number $k$), you would first look in the inode map (usually cached in memory) to find the location of the inode of directory $dir$ ($A3$). You then read the directory inode, which gives you the location of the directory data ($A2$); reading this data block gives you the name-to-inode-number mapping of (foo, $k$). You then consult the inode map again to find the location of inode number $k$ ($A1$), and finally read the desired data block at address $A0$.

Recursive update problem

There is one other serious problem in LFS that the inode map solves, known as the recursive update problem“De-indirection for Flash-based SSDs with Nameless Writes” by Yiying Zhang, Leo Prasath Arulraj, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau. FAST ’13, San Jose, California, February 2013. Our paper on a new way to build flash-based storage devices, to avoid redundant mappings in the file system and FTL. The idea is for the device to pick the physical location of a write, and return the address to the file system, which stores the mapping.. The problem arises in any file system that never updates in place (such as LFS), but rather moves updates to new locations on the disk.

Specifically, whenever an inode is updated, its location on disk changes. If we hadn’t been careful, this would have also entailed an update to the directory that points to this file, which then would have mandated a change to the parent of that directory, and so on, all the way up the file system tree.

LFS cleverly avoids this problem with the inode map. Even though the location of an inode may change, the change is never reflected in the directory itself. Rather, the imap structure is updated while the directory holds the same name-to-inode-number mapping. Thus, through indirection, LFS avoids the recursive update problem.