X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=doc%2Ffilesys.texi;h=f245daa48ea1e6d592a86146ddddf9947ca9cffe;hb=c9667cc796f96017951f8ac90978846918c184d7;hp=8e4dc4f964b4f352f7ffc30c6b672f2bda8573c5;hpb=a4613d70fb56b93216299f6253698ab0e4bbd46d;p=pintos-anon diff --git a/doc/filesys.texi b/doc/filesys.texi index 8e4dc4f..f245daa 100644 --- a/doc/filesys.texi +++ b/doc/filesys.texi @@ -14,12 +14,9 @@ filesys submission. If you build on project 3, then all of the project @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 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 @@ -29,6 +26,7 @@ PINTOSOPTS='--qemu'}. @menu * File System New Code:: +* Testing File System Persistence:: @end menu @node File System New Code @@ -82,6 +80,62 @@ which you will remove. 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 should think about synchronization throughout. + @node Project 4 Requirements @section Requirements @@ -176,18 +230,21 @@ 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 may support @file{.} and @file{..} for a small amount of extra -credit. - -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. +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. -Passing @file{.} as the argument to @code{open} must open the current -directory, regardless of whether @file{.} and @file{..} are fully -implemented. Of the existing system calls, only @code{close} needs to -accept a file descriptor for a directory. +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 (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: @@ -213,8 +270,7 @@ 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}, -regardless of whether they are implemented. +@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. @@ -230,14 +286,24 @@ 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. The -@command{shell} program implements @command{cd} internally. +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. +paths have already been created. This should not require any significant +extra effort on your part. @node Buffer Cache @subsection Buffer Cache @@ -249,11 +315,12 @@ 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. +You must implement a cache replacement algorithm that is at least as +good as the ``clock'' algorithm. Your algorithm must also 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. @@ -273,11 +340,8 @@ 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, 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 @@ -330,6 +394,10 @@ if B's data is all nonzero bytes, A is not allowed to see any zeros. 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 @@ -385,13 +453,6 @@ modified by the reference solution. 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 @@ -419,16 +480,20 @@ You'll need to consider this when deciding your inode organization. @subsection Subdirectories FAQ @table @b -@item How should a file name like @samp{//a//b} be interpreted? +@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}. +file name is the same as @samp{a/b}. @item How about a file name like @samp{/../x}? -If you don't implement @file{.} and @file{..}, then this is not a -special case. If you do, then it is equivalent to @samp{/x}. That is, -the root directory is its own parent. +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