In the previous two assignments, you made extensive use of a
file system without actually worrying about how it was implemented
-underneath. For this last assignment, you will fill in the
+underneath. For this last assignment, you will improve the
implementation of the file system. You will be working primarily in
the @file{filesys} directory.
@menu
* Project 4 Background::
+* Project 4 Suggested Order of Implementation::
* Project 4 Requirements::
-* Project 4 FAQ::
+* Project 4 FAQ::
@end menu
@node Project 4 Background
@menu
* File System New Code::
+* Testing File System Persistence::
@end menu
@node File System New Code
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.
+file system translates these calls into disk operations.
All the basic functionality is there in the code above, so that the
file system is usable from the start, as you've seen
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).
+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
+
+To make your job easier, we suggest implementing the parts of this
+project in the following order:
+
+@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
@subsection Indexed and Extensible Files
The basic file system allocates files as a single extent, making it
-vulnerable to external fragmentation. Eliminate this problem by
+vulnerable to external fragmentation, that is, it is possible that an
+@var{n}-block file cannot be allocated even though @var{n} blocks are
+free. Eliminate this problem by
modifying the on-disk 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
+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.)
+not suffer from external fragmentation (as does the extent-based file
+system we provide).
-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
+You can assume that the file system partition will not be larger than
+8 MB. You must
+support files as large as the partition (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.
An extent-based file can only grow if it is followed by empty space, but
-with indexed inodes file growth is possible whenever free space is
+indexed inodes make file growth possible whenever free space is
available. Implement file growth. In the basic file system, the file
-size is specified when the file is created. In UNIX and most other file
+size is specified when the file is created. In most modern 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. Your file system
must allow this.
There should be no predetermined limit on the size of a file, except
-that a file cannot exceed the size of the disk (minus metadata). This
+that a file cannot exceed the size of the file system (minus metadata). This
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
it, at your option. You must allow full path names to be
much longer than 14 characters.
-The current directory is maintained separately for each process. At
-startup, the initial process's current directory is the root directory.
+Maintain a separate current directory for each process. At
+startup, set the root as the initial process's 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.
+(This is why, under Unix, the @command{cd} command is a shell built-in,
+not an external program.)
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. In Unix,
-these are programs rather than built-in shell commands, but
-@command{cd} is a shell command.
+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
+The @code{pintos} @option{extract} and @option{append} 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
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
+is made to read or write a block, check to see if it is in the
+cache, and if so, use the cached data without going to
+disk. Otherwise, fetch the block from disk into the 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.
+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.
of these bounce buffers. Instead, copy data into and out of sectors in
the buffer cache directly.
-Your implementation should also include the following features:
-
-@table @b
-@item write-behind:
-Keep dirty blocks in the cache, instead of immediately writing modified
+Your cache should be @dfn{write-behind}, that is,
+keep dirty blocks in the cache, instead of immediately writing modified
data to disk. Write dirty blocks to disk whenever they are evicted.
Because write-behind makes your file system more fragile in the face of
crashes, in addition you should periodically write all dirty, cached
blocks back to disk. The cache should also be written back to disk in
@func{filesys_done}, so that halting Pintos flushes the cache.
-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}).
+If you have @func{timer_sleep} from the first project working, write-behind is
+an excellent application. Otherwise, you may implement a less general
+facility, but make sure that it does not exhibit busy-waiting.
-@item read-ahead:
-Your buffer cache should automatically fetch the next block of a file
+You should also implement @dfn{read-ahead}, that is,
+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.
-
Read-ahead is only really useful when done asynchronously. That means,
if a process requests disk block 1 from the file, it should block until disk
block 1 is read in, but once that read is complete, control should
return to the process immediately. The read-ahead request for disk
block 2 should be handled asynchronously, in the background.
-@end table
@strong{We recommend integrating the cache into your design early.} In
the past, many groups have tried to tack the cache onto a design late in
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?
+@item Can @code{BLOCk_SECTOR_SIZE} change?
-No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
-of IDE disk hardware.
-
-@item What's the directory separator character?
-
-Forward slash (@samp{/}).
+No, @code{BLOCK_SECTOR_SIZE} is fixed at 512. For IDE disks, this
+value is a fixed property of the hardware. Other disks do not
+necessarily have a 512-byte sector, but for simplicity Pintos only
+supports those that do.
@end table
@menu
@table @b
@item 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.
+The file system partition we create will be 8 MB or smaller. However,
+individual files will have to be smaller than the partition to
+accommodate the metadata. You'll need to consider this when deciding
+your inode organization.
@end table
@node Subdirectories FAQ
@subsection Subdirectories FAQ
@table @b
-@item Why is @command{cd} a shell command?
+@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?
-The current directory of each process is independent. A @command{cd}
-program could change its own current directory, but that would have no
-effect on the shell. In fact, Unix-like systems don't provide any way
-for one process to change another process's current working directory.
+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
copies of inodes would subvert the 64-block limitation that we place
on your cache.
-You can store a pointer to inode data in @struct{inode}, if you want,
-and you can store other information to help you find the inode when you
+You can store a pointer to inode data in @struct{inode}, but if you do
+so you should carefully make sure that this does not limit your OS to 64
+simultaneously open files.
+You can also store other information to help you find the inode when you
need it. Similarly, you may store some metadata along each of your 64
cache entries.
@func{byte_to_sector} in @file{filesys/inode.c} uses the
@struct{inode_disk} directly, without first reading 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.
+You will need to change @func{inode_byte_to_sector} to obtain the
+@struct{inode_disk} from the cache before using it.
@end table
projects / pintos-anon / blobdiff