Simulator

This exercise involves a simulator of the log-structured file system, LFS. The simulator simplifies what we have covered in this chapter a bit but hopefully leaves enough in place in order to illustrate some of the important properties of such a file system.

To get started, run the following in the terminal above:

prompt> ./lfs.py -n 1 -o

What you will see is as follows:

INITIAL file system contents:
[   0 ] live checkpoint: 3 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
[   1 ] live [.,0] [..,0] -- -- -- -- -- --
[   2 ] live type:dir size:1 refs:2 ptrs: 1 -- -- -- -- -- -- --
[   3 ] live chunk(imap): 2 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

create file /ku3

FINAL file system contents:
[   0 ]  ?   checkpoint: 7 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
[   1 ]  ?   [.,0] [..,0] -- -- -- -- -- --
[   2 ]  ?   type:dir size:1 refs:2 ptrs: 1 -- -- -- -- -- -- --
[   3 ]  ?   chunk(imap): 2 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
[   4 ]  ?   [.,0] [..,0] [ku3,1] -- -- -- -- --
[   5 ]  ?   type:dir size:1 refs:2 ptrs: 4 -- -- -- -- -- -- --
[   6 ]  ?   type:reg size:0 refs:1 ptrs: -- -- -- -- -- -- -- --
[   7 ]  ?   chunk(imap): 5 6 -- -- -- -- -- -- -- -- -- -- -- -- -- --

The output shows the initial file system state of an empty LFS, with a few different blocks initialized. The first block (block 0) is the “checkpoint region” of this LFS. For simplicity, this LFS only has one checkpoint region, and it is always located at block address=0 and is always just the size of a single block.

The contents of the checkpoint region are just disk addresses: locations of chunks of the inode map. In this case, the checkpoint region has the following contents:

checkpoint: 3 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

Let’s call the leftmost entry (marked with a 3 here) the 0th entry, the next one the 1st, and the last one (because there ...