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.

Your submission should define THREAD_JOIN_IMPLEMENTED in constants.h (see Conditional Compilation).

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.  Please read the long comment near the top of filesys.c, which introduces some details of the file system code as provided.

directory.h
directory.c
     Translates file names to inodes.  The directory data structure is stored as a file.

inode.h
inode.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.

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).

Synchronization
===============

The provided file system requires external synchronization, that is, callers must ensure that only one thread can be running in the file system code at once.  Your submission should use a finer-grained synchronization strategy.  You will need to consider synchronization issues for each type of file system object.  The provided code uses the following strategies:

  * The free map and root directory are read each time they are needed for an operation, and if they are modified, they are written back before the operation completes.  Thus, the free map is always consistent from an external viewpoint.

  * Inodes are immutable in the provided file system, that is, their content never changes between creation and deletion.  Furthermore, only one copy of an inode's data is maintained in memory at once, even if the file is open in multiple contexts.

  * File data doesn't have to be consistent because it's just not part of the model.  In Unix and many other operating systems, a read of a file by one process when the file is being written by another process can show inconsistent results: it can show that none, all, or part of the write has completed.  (However, after the write system call returns to its caller, all subsequent readers must see the change.)  Similarly, when two threads write to the same part of a file at the same time, their data may be interleaved.  External synchronization of the provided file system ensures that reads and writes are fully serialized, but your file system doesn't have to maintain full serialization as long as it follows the rules above.

Problem 4-1: Indexed Files
==========================

The basic file system allocates files as a single extent, making it vulnerable to external fragmentation.  Eliminate this problem by modifying the inode structure.  In practice, this probably means using an index structure with direct, indirect, and doubly indirect blocks. (You are welcome to choose a different scheme as long as you explain the rationale for it in your design documentation, and as long as it does not suffer from external fragmentation.)

You can assume that the disk will not be larger than 8 MB.  You must support files as large as the disk (minus metadata).  Each inode is stored in one disk sector, limiting the number of block pointers that it can contain.  Supporting 8 MB files 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 inode 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 inode remain properly synchronized.

The user is allowed to seek beyond the current end-of-file (EOF).  The seek itself does not extend the file.  Writing at a position past EOF extends the file to the position being written, and any gap between the previous EOF and the start of the write must be filled with zeros.  A read past EOF returns zero bytes.

Writing far beyond EOF can cause many blocks to be entirely zero.  Some file systems allocate and write real data blocks for these implicitly zeroed blocks.  Other file systems do not allocate these blocks at all until they are explicitly written.  The latter file systems are said to support ``sparse files.''  You may adopt either allocation strategy in your file system.

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.

Each process has its own current directory.  When one process starts another with the exec system call, the child process inherits its parent's current directory.  After that, the two processes' current directories are independent, so that either changing its own current directory has no effect on the other.

Update the existing system calls so that, anywhere a file name is provided by the caller, an absolute or relative path name may used. Also, implement the following new system calls:

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.  In 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 accessed, 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 algorithm in your design document.

The provided file system code uses a ``bounce buffer'' in file to translate the disk's sector-by-sector interface into the system call interface's byte-by-byte interface.  It needs per-file buffers because, without them, there's no other good place to put sector data. (The stack is not a good place because large objects should not be allocated on the stack.  A 512-byte sector is pushing the limit there.)  As part of implementing the buffer cache, you should get rid of these bounce buffers.  Instead, copy data into and out of sectors in the buffer cache directly.  You will probably need some synchronization to prevent sectors from being evicted from the cache while you are using them.

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 periodically write all cached blocks to disk.  If you have timer_sleep from the first project working, this is an excellent application for it.  (If you're still using the base implementation of timer_sleep, be aware that it busy-waits, which is not an acceptable solution.) If timer_sleep's delays seem too short or too long, reread the explanation of the -r option to pintos (see Debugging versus Testing).

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.

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 the disk contents will be consistent.

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

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

  * How did you choose to synchronize file system operations?

  * 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?

     You also need to support the -f, -ci, -co, and -ex flags individually, and you need to handle them when they're combined, like this: pintos -f -ci shell 12345 -ex "shell".  Thus, you should be able to treat the above as equivalent to:

          pintos -f
          pintos -ci shell 12345
          pintos -ex "shell"

     If you don't change the filesystem interface, then this should already be implemented properly in threads/init.c and filesys/fsutil.c.

     You must also implement the -q option and make sure that data gets flushed out to disk properly when it is used.

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

     No, DISK_SECTOR_SIZE is fixed at 512.  This is a fixed property of IDE disk hardware.

 4. Will the inode take up space on the disk too?

     Yes.  Anything stored in inode 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. What's the directory separator character?

     Forward slash (/).

Problem 4-2: File Growth FAQ
----------------------------

 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 inode organization.

Problem 4-3: Subdirectory FAQ
-----------------------------

 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.

Problem 4-4: Buffer Cache FAQ
-----------------------------

 1. We're limited to a 64-block cache, but can we also keep an inode_disk inside inode, the way the provided code does?

     The goal of the 64-block limit is to bound the amount of cached file system data.  If you keep a block of disk data---whether file data or metadata---anywhere in kernel memory then you have to count it against the 64-block limit.  The same rule applies to anything that's ``similar'' to a block of disk data, such as a inode_disk without the length or sector_cnt members.

     You can keep a cached copy of the free map in memory permanently if you like.  It doesn't have to count against the cache size.

     That means you'll have to change the way the inode implementation accesses its corresponding on-disk inode right now, since it currently just embeds a inode_disk in inode and reads the corresponding sector in from disk when it's created.  Keeping extra copies of inodes would be cheating the 64-block limitation that we place on your cache.

     You can store pointers to inode data in inode, 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.

     If you look at inode_byte_to_sector, it uses the inode_disk directly without having first read in that sector from wherever it was in the storage hierarchy.  This will no longer work.  You will need to change inode_byte_to_sector so that it reads the inode_disk from the storage hierarchy before using it.