Ben Bitdiddle has proposed the simple neat and robust file system (SNARFS).* Ben’s system has no on-disk data structures other than the disk blocks themselves, which are self-describing. Each 4-kilobyte disk block starts with the following 24 bytes of information:

■ fid (File-ID): a 64-bit number that uniquely defines a file. A fid of zero implies that the disk block is free.

■ sn (Sequence Number): a 64-bit number that identifies which block of a file this disk block contains.

■ t (Time): The time this block was last updated.

In addition, the first block of a file contains the file name (string), version number, and the fid of its parent directory. The rest of the first block is filled with data. Setting the directory fid to zero marks the entire file free. Directories are just files. Each directory should contain only the fid of its parent directory. However, as a “hint” directories may also include a table giving the mapping from name to fid and the mapping from fid to blocks for some of the files in the directory. To allow fast access, three in-memory (virtual memory) structures are created each time the system is booted:

■ map: an in-memory hash table that associates a (fid, sn) pair with the disk block containing that block of that file

■ free: a free list that represents all of the free blocks on disk in a compact manner

■ recycle: a list of blocks that are available for reuse but have not yet been written with a fid of 0

a. Each read or write of a disk block results in one disk I/O. What is the minimum number of disk I/Os required in SNARFS to create a new file containing 2 kilobytes of data in an existing directory? If the system crashes (i.e., the contents of virtual memory are lost) after these I/Os are completed, the file should be present in the appropriate directory after recovery.

b. Ben argues that the in-memory structures can easily be rebuilt after a crash. Explain what actions are required to rebuild map, free, and recycle at boot time.