@file{filesys/Make.vars} to enable VM functionality. You can receive up
to 5% extra credit if you do enable VM.
-The tests for project 4 (and later projects) will probably run faster if
-you use the qemu emulator, e.g.@: via @code{make check
-PINTOSOPTS='--qemu'}.
-
@menu
* Project 4 Background::
+* Project 4 Suggested Order of Implementation::
* Project 4 Requirements::
* Project 4 FAQ::
@end menu
@menu
* File System New Code::
+* Testing File System Persistence::
@end menu
@node File System New Code
While most of your work will be in @file{filesys}, you should be
prepared for interactions with all previous parts.
+@node Testing File System Persistence
+@subsection Testing File System Persistence
+
+By now, you should be familiar with the basic process of running the
+Pintos tests. @xref{Testing}, for review, if necessary.
+
+Until now, each test invoked Pintos just once. However, an important
+purpose of a file system is to ensure that data remains accessible from
+one boot to another. Thus, the tests that are part of the file system
+project invoke Pintos a second time. The second run combines all the
+files and directories in the file system into a single file, then copies
+that file out of the Pintos file system into the host (Unix) file
+system.
+
+The grading scripts check the file system's correctness based on the
+contents of the file copied out in the second run. This means that your
+project will not pass any of the extended file system tests until the
+file system is implemented well enough to support @command{tar}, the
+Pintos user program that produces the file that is copied out. The
+@command{tar} program is fairly demanding (it requires both extensible
+file and subdirectory support), so this will take some work. Until
+then, you can ignore errors from @command{make check} regarding the
+extracted file system.
+
+Incidentally, as you may have surmised, the file format used for copying
+out the file system contents is the standard Unix ``tar'' format. You
+can use the Unix @command{tar} program to examine them. The tar file
+for test @var{t} is named @file{@var{t}.tar}.
+
+@node Project 4 Suggested Order of Implementation
+@section Suggested Order of Implementation
+
+We suggest implementing the parts of this project in the following
+order to make your job easier:
+
+@enumerate
+@item
+Buffer cache (@pxref{Buffer Cache}). Implement the buffer cache and
+integrate it into the existing file system. At this point all the
+tests from project 2 (and project 3, if you're building on it) should
+still pass.
+
+@item
+Extensible files (@pxref{Indexed and Extensible Files}). After this
+step, your project should pass the file growth tests.
+
+@item
+Subdirectories (@pxref{Subdirectories}). Afterward, your project
+should pass the directory tests.
+
+@item
+Remaining miscellaneous items.
+@end enumerate
+
+You can implement extensible files and subdirectories in parallel if
+you temporarily make the number of entries in new directories fixed.
+
+You should think about synchronization throughout.
+
@node Project 4 Requirements
@section Requirements
also applies to the root directory file, which should now be allowed
to expand beyond its initial limit of 16 files.
-The user is allowed to seek beyond the current end-of-file (EOF). The
+User programs are 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
Update the existing system calls so that, anywhere a file name is
provided by the caller, an absolute or relative path name may used.
The directory separator character is forward slash (@samp{/}).
+You must also support special file names @file{.} and @file{..}, which
+have the same meanings as they do in Unix.
+
+Update the @code{open} system call so that it can also open directories.
+Of the existing system calls, only @code{close} needs to accept a file
+descriptor for a directory.
Update the @code{remove} system call so that it can delete empty
-directories in addition to regular files. Directories can only be
-deleted if they do not contain any files or subdirectories.
+directories (other than the root) in addition to regular files.
+Directories may only be deleted if they do not contain any files or
+subdirectories (other than @file{.} and @file{..}). You may decide
+whether to allow deletion of a directory that is open by a process or in
+use as a process's current working directory. If it is allowed, then
+attempts to open files (including @file{.} and @file{..}) or create new
+files in a deleted directory must be disallowed.
Implement the following new system calls:
@file{/a/b/c} does not.
@end deftypefn
-@deftypefn {System Call} void lsdir (void)
-Prints a list of files in the current directory to @code{stdout}, one
-per line, in no particular order.
+@deftypefn {System Call} bool readdir (int @var{fd}, char *@var{name})
+Reads a directory entry from file descriptor @var{fd}, which must
+represent a directory. If successful, stores the null-terminated file
+name in @var{name}, which must have room for @code{READDIR_MAX_LEN + 1}
+bytes, and returns true. If no entries are left in the directory,
+returns false.
+
+@file{.} and @file{..} should not be returned by @code{readdir}.
+
+If the directory changes while it is open, then it is acceptable for
+some entries not to be read at all or to be read multiple times.
+Otherwise, each directory entry should be read once, in any order.
+
+@code{READDIR_MAX_LEN} is defined in @file{lib/user/syscall.h}. If your
+file system supports longer file names than the basic file system, you
+should increase this value from the default of 14.
+@end deftypefn
+
+@deftypefn {System Call} bool isdir (int @var{fd})
+Returns true if @var{fd} represents a directory,
+false if it represents an ordinary file.
+@end deftypefn
+
+@deftypefn {System Call} int inumber (int @var{fd})
+Returns the @dfn{inode number} of the inode associated with @var{fd},
+which may represent an ordinary file or a directory.
+
+An inode number persistently identifies a file or directory. It is
+unique during the file's existence. In Pintos, the sector number of the
+inode is suitable for use as an inode number.
@end deftypefn
We have provided @command{ls} and @command{mkdir} user programs, which
-are straightforward once the above syscalls are implemented.
+are straightforward once the above syscalls are implemented.
+We have also provided @command{pwd}, which is not so straightforward.
+The @command{shell} program implements @command{cd} internally.
The @code{pintos} @option{put} and @option{get} commands should now
accept full path names, assuming that the directories used in the
-paths have already been created. This should not require any extra
-effort on your part.
-
-You may support @file{.} and @file{..} for a small amount of extra
-credit.
+paths have already been created. This should not require any significant
+extra effort on your part.
@node Buffer Cache
@subsection Buffer Cache
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.
+You must implement a cache replacement algorithm that is at least as
+good as the ``clock'' algorithm. We encourage you to account for
+the generally greater value of metadata compared to data. Experiment
+to see what combination of accessed, dirty, and other information
+results in the best performance, as measured by the number of disk
+accesses.
You can keep a cached copy of the free map permanently in memory if you
like. It doesn't have to count against the cache size.
@func{filesys_done}, so that halting Pintos flushes the cache.
If you have @func{timer_sleep} from the first project working, write-behind is
-an excellent application. If you're still using the base
-implementation of @func{timer_sleep}, be aware that it busy-waits, which
-is not acceptable here (or elsewhere). 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}).
+an excellent application. Otherwise, you may implement a less general
+facility, but make sure that it does not exhibit busy-waiting.
You should also implement @dfn{read-ahead}, that is,
automatically fetch the next block of a file
Operations on different directories should take place concurrently.
Operations on the same directory may wait for one another.
+Keep in mind that only data shared by multiple threads needs to be
+synchronized. In the base file system, @struct{file} and @struct{dir}
+are accessed only by a single thread.
+
@node Project 4 FAQ
@section FAQ
30 files changed, 2721 insertions(+), 286 deletions(-)
@end verbatim
-@item What extra credit opportunities are available?
-
-You may implement Unix-style support for @file{.} and @file{..} in
-relative paths in their projects.
-
-You may submit with VM enabled.
-
@item Can @code{DISK_SECTOR_SIZE} change?
No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
@menu
* Indexed Files FAQ::
+* Subdirectories FAQ::
* Buffer Cache FAQ::
@end menu
You'll need to consider this when deciding your inode organization.
@end table
+@node Subdirectories FAQ
+@subsection Subdirectories FAQ
+
+@table @b
+@item How should a file name like @samp{a//b} be interpreted?
+
+Multiple consecutive slashes are equivalent to a single slash, so this
+file name is the same as @samp{a/b}.
+
+@item How about a file name like @samp{/../x}?
+
+The root directory is its own parent, so it is equivalent to @samp{/x}.
+
+@item How should a file name that ends in @samp{/} be treated?
+
+Most Unix systems allow a slash at the end of the name for a directory,
+and reject other names that end in slashes. We will allow this
+behavior, as well as simply rejecting a name that ends in a slash.
+@end table
+
@node Buffer Cache FAQ
@subsection Buffer Cache FAQ