Overview

This homework involves a simulator of the log-structured file system, LFS.
The simulator simplifies the book chapter's LFS a bit, but hopefully leaves
enough in place in order to illustrate some of the important properties of
such a file system.

To get start, run the following:

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 are 16) the
15th entry. Thus, we can think of them as:

checkpoint: 3 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
    entry:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

This means that the first chunk of the inode map resides at disk address=3,
and that the rest of the inode map pieces have yet to be allocated (and
hence are marked "--").

Let's now look at that chunk of the inode map ("imap" from now on). The
imap is just an array that tells you, for each inode number, its current
location on the disk. In the initial state shown above, we see this:

chunk(imap): 2 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

These chunks also have (by default) 16 entries, and again we can think of
them as such:

chunk(imap): 2 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
     entry:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15

Because each chunk of the imap has 16 entries, and because the checkpoint
region (CR) has 16 entries, we now know that the entire LFS has 16x16=256
inode numbers available for files. A small file system(!) but good enough
for our purposes.

We also now know that each chunk of the imap is responsible for a contiguous
group of inodes, and we know which ones depending on which entry in the CR
points to this chunk. Specifically, entry 0 of the CR points to a chunk of
the imap that has information about inode numbers 0…15; entry 1 of the CR
points to an imap chunk for inode numbers 16…31.

In this specific example, we know the 0th entry of the CR points to block=3,
and in there, the 0th entry has a '2' in it. In our simulator, the root inode
is inode number=0, and thus this is the inode of the root directory of the
file system. From the imap, we now know the location of inode number=0's
address is block=2. So let's look at block 2! We see:

type:dir size:1 refs:2 ptrs: 1 -- -- -- -- -- -- --

This file metadata is a simplified inode, with file type (a directory), size
(1 block), reference count (how many directories it refers to, if this is a
directory), and some number of pointers to data blocks (in this case, one,
which points to block address=1).

This finally leads us to the last bit of initial state, which is the contents
of the directory. This directory only has one block in it (at address 1),
which has contents:

[.,0] [..,0] -- -- -- -- -- --

Herein lies an empty directory, with [name,inode number] pairs for itself
(".") and its parent (".."). In this special case (the root), the parent is
just itself, and both are inode number=0. Whew! We have now (hopefully)
understood the entire contents of the initial state of the file system.

What happens next in the default mode of the simulation is that one or more
operations are run against the file system, thus changing its state. In this
case, we know what the command because we had the simulator tell us via the
"-o" flag (which shows each operation as it is run). That operation is:

create file /ku3

This means a file "ku3" was created in the root directory "/". To accomplish
this creation, a number of structures must be updated, which means that the
log was written to. You can see that four writes occur beyond the previous end
of the log (address=3), at blocks 4…7:

[.,0] [..,0] [ku3,1] -- -- -- -- --
type:dir size:1 refs:2 ptrs: 4 -- -- -- -- -- -- --
type:reg size:0 refs:1 ptrs: -- -- -- -- -- -- -- --
chunk(imap): 5 6 -- -- -- -- -- -- -- -- -- -- -- -- -- --

These updates reflect how this version of LFS writes to the disk to create a
file:

• A directory block update to include "ku3" and its inode number (1) in the root directory
• An updated root inode which now refers to block 4 where the latest contents of this directory are found
• A new inode for the newly created file (note the type)
• A new version of the first imap chunk which now tells us where both inode 0 and inode 1 are located

However, this does not (quite) reflect all that must change. Because the inode
map itself has changed, the checkpoint region must also reflect where the
latest chunk of the first piece of the inode map resides. Thus, the CR is also
updated:

checkpoint: 7 -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

You might also have noticed one more thing in the output. In the initial file
system contents, there is a marker between the disk address and the contents
that says "live" for each entry, and in the final output there is a "?"
instead. This "?" is there so you can determine, for yourself, whether each
block is live or not. Start with the checkpoint region and see if you can
determine which group of blocks can be reached (and hence are live); all the
rest are thus dead and could be used again.

To see if you are right, run again with -c:

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

...

As you can now see, every time a structure is updated, garbage is left behind,
one of the main issues a non-update-in-place file system like LFS must deal
with. Fortunately, for you, we won't worry too much about garbage collection
in this simplified version of LFS.

You now have all the information you need to understand this version of LFS.

The other options, which let you play with various aspects of the simulator, include:

prompt> ./lfs.py -h
Usage: lfs.py [options]

Options:
  -h, --help            show this help message and exit
  -s SEED, --seed=SEED  the random seed
  -N, --no_force        Do not force checkpoint writes after updates
  -D, --use_disk_cr     use disk (maybe old) version of checkpoint region
  -c, --compute         compute answers for me
  -o, --show_operations
                        print out operations as they occur
  -i, --show_intermediate
                        print out state changes as they occur
  -e, --show_return_codes
                        show error/return codes
  -n NUM_COMMANDS, --num_commands=NUM_COMMANDS
                        generate N random commands
  -p PERCENTAGES, --percentages=PERCENTAGES
                        percent chance of:
                        createfile,writefile,createdir,rmfile,linkfile,sync
                        (example is c30,w30,d10,r20,l10,s0)
  -a INODE_POLICY, --allocation_policy=INODE_POLICY
                        inode allocation policy: "r" for "random" or "s" for
                        "sequential"
  -L COMMAND_LIST, --command_list=COMMAND_LIST
                        command list in format:
                        "cmd1,arg1,...,argN:cmd2,arg1,...,argN:... where cmds
                        are:c:createfile, d:createdir, r:delete, w:write,
                        l:link, s:syncformat: c,filepath d,dirpath r,filepath
                        w,filepath,offset,numblks l,srcpath,dstpath s