Project 4: File Systems
***********************

In the previous two assignments, you made extensive use of a filesystem without actually worrying about how it was implemented underneath.  For this last assignment, you will fill in the implementation of the filesystem.  You will be working primarily in the filesys directory.

You should build on the code you wrote for the previous assignments. However, if you wish, you may turn off your VM features, as they are not vital to making the filesystem work.  (You will need to edit filesys/Makefile.vars to fully disable VM.)  All of the functionality needed for project 2 (argument passing, syscalls and multiprogramming) must work in your filesys submission.

On the other hand, one of the particular charms of working on operating systems is being able to use what you build, and building full-featured systems.  Therefore, you should strive to make all the parts work together so that you can run VM and your filesystem at the same time.  Plus, keeping VM is a great way to stress-test your filesystem implementation.

FIXME FIXME FIXME The first step is to understand the default filesystem provided by the base code.  The first things you should look at are threads/init.c and filesys/fsutil.c: there are special command line arguments to Pintos which are used to format and manipulate the emulated disk.  Specifically, -f formats the file system disk for use with Pintos, and -cp SRC DST copies SRC on the Unix filesystem to DST on the file system disk.  With this information, you should be able to compile the base code and try out the command: pintos -f -cp ./small small to copy the file small from your working directory into the Pintos file system.

FIXME FIXME FIXME One thing you should realize immediately is that, until you use the above operation to copy the shell (or whatever your initial program is) to the emulated disk, Pintos will be unable to do very much useful work (it'll try to open the shell and fail, thereby quitting out).  You will also find that you won't be able to do interesting things until you copy a variety of programs to the disk.  A useful technique, once your inode formats are finalized, is to create a clean reference disk and copy that over whenever you trash your disk beyond a useful state (which will probably happen quite often while debugging).

New Code
========

Here are some files that are probably new to you.  These are in the filesys directory except where indicated:

fsutil.c
     Simple utilities for the filesystem that are accessible from the kernel command line.

filesys.h
filesys.c
     Top-level interface to the file system.

directory.h
directory.c
     Translates file names to disk file headers; the directory data structure is stored as a file.

filehdr.h
filehdr.c
     Manages the data structure representing the layout of a file's data on disk.

file.h
file.c
     Translates file reads and writes to disk sector reads and writes.

devices/disk.h
devices/disk.c
     Provides access to the physical disk, abstracting away the rather awful IDE interface.

lib/kernel/bitmap.h
lib/kernel/bitmap.c
     A bitmap data structure along with routines for reading and writing the bitmap to disk files.

Our file system has a Unix-like interface, so you may also wish to read the Unix man pages for creat, open, close, read, write, lseek, and unlink.  Our file system has calls that are similar, but not identical, to these.  The file system translates these calls into physical disk operations.

All the basic functionality is there in the code above, so that the filesystem is usable right off the bat.  In fact, you've been using it in the previous two projects.  However, it has severe limitations which you will remove.

While most of your work will be in filesys, you should be prepared for interactions with all previous parts (as usual).

Problem 4-1: Large Files
========================

Modify the file system to allow the maximum size of a file to be as large as the disk.  You can assume that the disk will not be larger than 8 MB.  In the basic file system, each file is limited to a file size of just under 64 kB.  Each file has a header (struct filehdr) that is a table of direct pointers to the disk blocks for that file.  Since the header is stored in one disk sector, the maximum size of a file is limited by the number of pointers that will fit in one disk sector.  Increasing the limit to 8 MB will require you to implement doubly-indirect blocks.

Problem 4-2: File Growth
========================

Implement extensible files.  In the basic file system, the file size is specified when the file is created.  One advantage of this is that the FileHeader data structure, once created, never changes.  In UNIX and most other file systems, a file is initially created with size 0 and is then expanded every time a write is made off the end of the file.  Modify the file system to allow this.  As one test case, allow the root directory file to expand beyond its current limit of ten files.  Make sure that concurrent accesses to the file header remain properly synchronized.

Problem 4-3: Subdirectories
===========================

Implement a hierarchical name space.  In the basic file system, all files live in a single directory.  Modify this to allow directories to point to either files or other directories.  To do this, you will need to implement routines that parse path names into a sequence of directories, as well as routines that change the current working directory and that list the contents of the current directory.  For performance, allow concurrent updates to different directories, but use mutual exclusion to ensure that updates to the same directory are performed atomically (for example, to ensure that a file is deleted only once).

Make sure that directories can expand beyond their original size just as any other file can.

To take advantage of hierarchical name spaces in user programs, provide the following syscalls:

SYS_chdir
bool chdir (const char *DIR)
     Attempts to change the current working directory of the process to DIR, which may be either relative or absolute.  Returns true if successful, false on failure.

SYS_mkdir
bool mkdir (const char *dir)
     Attempts to create the directory named DIR, which may be either relative or absolute.  Returns true if successful, false on failure.

SYS_lsdir
void lsdir (void)
     Prints a list of files in the current directory to stdout, one per line.

Also write the ls and mkdir user programs.  This is straightforward once the above syscalls are implemented.  If Unix, these are programs rather than built-in shell commands, but cd is a shell command.  (Why?)

Problem 4-4: Buffer Cache
=========================

Modify the file system to keep a cache of file blocks.  When a request is made to read or write a block, check to see if it is stored in the cache, and if so, fetch it immediately from the cache without going to disk.  (Otherwise, fetch the block from disk into cache, evicting an older entry if necessary.)  You are limited to a cache no greater than 64 sectors in size.  Be sure to choose an intelligent cache replacement algorithm.  Experiment to see what combination of use, dirty, and other information results in the best performance, as measured by the number of disk accesses.  (For example, metadata is generally more valuable to cache than data.)  Document your replacement algoritm in your design document.

In addition to the basic file caching scheme, your implementation should also include the following enhancements:

write-behind:
     Instead of always immediately writing modified data to disk, dirty blocks can be kept in the cache and written out sometime later.  Your buffer cache should write behind whenever a block is evicted from the cache.

read-ahead:
     Your buffer cache should automatically fetch the next block of a file into the cache when one block of a file is read, in case that block is about to be read.

For each of these three optimizations, design a file I/O workload that is likely to benefit from the enhancement, explain why you expect it to perform better than on the original file system implementation, and demonstrate the performance improvement.

Note that write-behind makes your filesystem more fragile in the face of crashes.  Therefore, you should implement some manner to periodically write all cached blocks to disk.  If you have timer_msleep() from the first project working, this is an excellent application for it.

Likewise, read-ahead is only really useful when done asynchronously. That is, if a process wants disk block 1 from the file, it needs to block until disk block 1 is read in, but once that read is complete, control should return to the process immediately while the read request for disk block 2 is handled asynchronously.  In other words, the process will block to wait for disk block 1, but should not block waiting for disk block 2.

FIXME When you're implementing this, please make sure you have a scheme for making any read-ahead and write-behind threads halt when Pintos is ``done'' (when the user program has completed, etc), so that Pintos will halt normally and print its various statistics.

Design Document Requirements
============================

As always, submit a design document file summarizing your design.  Be sure to cover the following points :

  * How did you structure your inodes? How many blocks did you access directly, via single-indirection, and/or via double-indirection?  Why?

  * How did you structure your buffer cache? How did you perform a lookup in the cache? How did you choose elements to evict from the cache?

  * How and when did you flush the cache?

FAQ
===

 1. What extra credit opportunities are available for this assignment?

       * We'll give out extra credit to groups that implement Unix-style support for . and .. in relative paths in their projects.

       * We'll give some extra credit if you submit with VM enabled.  If you do this, make sure you show us that you can run multiple programs concurrently.  A particularly good demonstration is running capitalize (with a reduced words file that fits comfortably on your disk, of course).  So submit a file system disk that contains a VM-heavy program like capitalize, so we can try it out.  And also include the results in your test case file.

          We feel that you will be much more satisfied with your cs140 ``final product'' if you can get your VM working with your file system.  It's also a great stress test for your FS, but obviously you have to be pretty confident with your VM if you're going to submit this extra credit, since you'll still lose points for failing FS-related tests, even if the problem is in your VM code.

       * A point of extra credit can be assigned if a user can recursively remove directories from the shell command prompt.  Note that the typical semantic is to just fail if a directory is not empty.

     Make sure that you discuss any extra credit in your README file.  We're likely to miss it if it gets buried in your design document.

 2. What exec modes for running Pintos do I absolutely need to support?

     FIXME FIXME The most standard mode is to run your Pintos with all the command flags on one command line, like this: pintos -f -cp shell shell -ex "shell".  However, you also need to support these flags individually---especially since that's how the grader tests your program.  Thus, you should be able to run the above instead as:

     FIXME

          pintos -f
          pintos -cp shell shell
          pintos -ex "shell"

     Note that this also provides a way for you to validate that your disks are really persistent.  This is a common problem with a write behind cache: if you don't shut down properly it will leave the disk in an inconsistent state.

 3. Will you test our file system with a different DISK_SECTOR_SIZE?

     No, DISK_SECTOR_SIZE will not change.

 4. Will the struct filehdr take up space on the disk too?

     Yes.  Anything stored in struct filehdr takes up space on disk, so you must include this in your calculation of how many entires will fit in a single disk sector.

 5. File Growth FAQs

      1. What is the largest file size that we are supposed to support?

          The disk we create will be 8 MB or smaller.  However, individual files will have to be smaller than the disk to accommodate the metadata. You'll need to consider this when deciding your struct filehdr (inode) organization.

 6. Subdirectory FAQs

      1. What's the answer to the question in the spec about why ls and mkdir are user programs, while cd is a shell command?

          Each process maintains its own current working directory, so it's much easier to change the current working directory of the shell process if cd is implemented as a shell command rather than as another user process.  In fact, Unix-like systems don't provide any way for one process to change another process's current working directory.

      2. When the spec states that directories should be able to grow beyond ten files, does this mean that there can still be a set maximum number of files per directory that is greater than ten, or should directories now support unlimited growth (bounded by the maximum supported file size)?

          We're looking for directories that can support arbitrarily large numbers of files.  Now that directories can grow, we want you to remove the concept of a preset maximum file limit.

      3. When should the lsdir system call return?

          The lsdir system call should not return until after the directory has been printed.  Here's a code fragment, and the desired output:

               printf ("Start of directory\n");
               lsdir ();
               printf ("End of directory\n");

          This code should create the following output:

               Start of directory
               ...  directory contents ...
               End of directory

      4. Do we have to implement both absolute and relative pathnames?

          Yes.  Implementing . and .. is extra credit, though.

      5. Should remove() also be able to remove directories?

          Yes.  The remove system call should handle removal of both regular files and directories.  You may assume that directories can only be deleted if they are empty, as in Unix.

 7. Buffer Cache FAQs

      1. We're limited to a 64-block cache, but can we also keep a copy of each struct filehdr for an open file inside struct file, the way the stub code does?

          No, you shouldn't keep any disk sectors stored anywhere outside the cache.  That means you'll have to change the way the file implementation accesses its corresponding inode right now, since it currently just creates a new struct filehdr in its constructor and reads the corresponding sector in from disk when it's created.

          There are two reasons for not storing inodes in struct file. First, keeping extra copies of inodes would be cheating the 64-block limitation that we place on your cache.  Second, if two processes have the same file open, you will create a huge synchronization headache for yourself if each struct file has its own copy of the inode.

          Note that you can store pointers to inodes in struct file if you want, and you can store some other small amount of information to help you find the inode when you need it.

          Similarly, if you want to store one block of data plus some small amount of metadata for each of your 64 cache entries, that's fine.

      2. But why can't we store copies of inodes in struct file? We don't understand the answer to the previous question.

          The issue regarding storing struct filehdrs has to do with implementation of the buffer cache.  Basically, you can't store a struct filehdr * in struct filehdr.  Each time you need to read a struct filehdr, you'll have to get it either from the buffer cache or from disk.

          If you look at file_read_at(), it uses hdr directly without having first read in that sector from wherever it was in the storage hierarchy.  You are no longer allowed to do this.  You will need to change file_read_at (and similar functions) so that it reads hdr from the storage hierarchy before using it.