Switch the base file system from direct-indexed inodes to extents.

[pintos-anon] / doc / filesys.texi

@node Project 4--File Systems, References, Project 3--Virtual Memory, Top
@chapter 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 @file{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
@file{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 @code{THREAD_JOIN_IMPLEMENTED} in
@file{constants.h} (@pxref{Conditional Compilation}).

@menu
* File System New Code::        
* File System Synchronization::  
* Problem 4-1 Indexed Files::     
* Problem 4-2 File Growth::     
* Problem 4-3 Subdirectories::  
* Problem 4-4 Buffer Cache::    
* File System Design Document Requirements::  
* File System FAQ::             
@end menu

@node File System New Code
@section New Code

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

@table @file
@item fsutil.c
Simple utilities for the filesystem that are accessible from the
kernel command line.

@item filesys.h
@itemx filesys.c
Top-level interface to the file system.  Please read the long comment
near the top of @file{filesys.c}, which introduces some details of the
file system code as provided.

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

@item inode.h
@itemx inode.c
Manages the data structure representing the layout of a
file's data on disk.

@item file.h
@itemx file.c
Translates file reads and writes to disk sector reads
and writes.

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

Our file system has a Unix-like interface, so you may also wish to
read the Unix man pages for @code{creat}, @code{open}, @code{close},
@code{read}, @code{write}, @code{lseek}, and @code{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 @file{filesys}, you should be
prepared for interactions with all previous parts (as usual).

@node File System Synchronization
@section 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:

@itemize @bullet
@item
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.

@item
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.

@item
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.
@end itemize

@node Problem 4-1 Indexed Files
@section 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.

@node Problem 4-2 File Growth
@section 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.

@node Problem 4-3 Subdirectories
@section 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 @code{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:

@table @code
@item SYS_chdir
@itemx bool chdir (const char *@var{dir})
Attempts to change the current working directory of the process to
@var{dir}, which may be either relative or absolute.  Returns true if
successful, false on failure.

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

@item SYS_lsdir
@itemx void lsdir (void)
Prints a list of files in the current directory to @code{stdout}, one
per line.
@end table

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

@node Problem 4-4 Buffer Cache
@section 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 @struct{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.@footnote{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:

@table @b
@item 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.

@item 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.
@end table

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
@func{timer_sleep} from the first project working, this is an
excellent application for it.  (If you're still using the base
implementation of @func{timer_sleep}, be aware that it busy-waits, which
is not an acceptable solution.) If @func{timer_sleep}'s delays seem too
short or too long, reread the explanation of the @option{-r} option to
@command{pintos} (@pxref{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.

@node File System Design Document Requirements
@section Design Document Requirements

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

@itemize @bullet
@item
How did you choose to synchronize file system operations?

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

@item
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?

@item
How and when did you flush the cache?
@end itemize

@node File System FAQ
@section FAQ

@enumerate 1
@item
@b{What extra credit opportunities are available for this assignment?}

@itemize @bullet
@item
We'll give out extra credit to groups that implement Unix-style
support for @file{.} and @file{..} in relative paths in their projects.

@item
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
@file{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 @file{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.

@item
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.
@end itemize

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

@item
@b{What exec modes for running Pintos do I absolutely need to
support?}

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

@example
pintos -f
pintos -ci shell 12345
pintos -ex "shell"
@end example

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

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

@item
@b{Will you test our file system with a different @code{DISK_SECTOR_SIZE}?}

No, @code{DISK_SECTOR_SIZE} is fixed at 512.  This is a fixed property
of IDE disk hardware.

@item
@b{Will the @struct{inode} take up space on the disk too?}

Yes.  Anything stored in @struct{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.

@item
@b{What's the directory separator character?}

Forward slash (@samp{/}).
@end enumerate

@menu
* Problem 4-2 File Growth FAQ::  
* Problem 4-3 Subdirectory FAQ::  
* Problem 4-4 Buffer Cache FAQ::  
@end menu

@node Problem 4-2 File Growth FAQ
@subsection Problem 4-2: File Growth FAQ

@enumerate 1
@item
@b{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{inode}
organization.
@end enumerate

@node Problem 4-3 Subdirectory FAQ
@subsection Problem 4-3: Subdirectory FAQ

@enumerate 1
@item
@b{What's the answer to the question in the spec about why
@command{ls} and @command{mkdir} are user programs, while @command{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
@command{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.

@item
@b{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.

@item
@b{When should the @code{lsdir} system call return?}

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

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

This code should create the following output:

@example
Start of directory
...  directory contents ...
End of directory
@end example

@item
@b{Do we have to implement both absolute and relative pathnames?}

Yes.  Implementing @file{.} and @file{..} is extra credit, though.

@item
@b{Should @func{remove} also be able to remove directories?}

Yes.  The @code{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.
@end enumerate

@node Problem 4-4 Buffer Cache FAQ
@subsection Problem 4-4: Buffer Cache FAQ

@enumerate 1
@item
@b{We're limited to a 64-block cache, but can we also keep an
@struct{inode_disk} inside @struct{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 @struct{inode_disk}
without the @code{length} or @code{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 @struct{inode_disk} in @struct{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 @struct{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 @func{inode_byte_to_sector}, it uses the
@struct{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 @func{inode_byte_to_sector} so that it
reads the @struct{inode_disk} from the storage hierarchy before using
it.
@end enumerate