-@node Project 4--File Systems, , Project 3--Virtual Memory, Top
+@node Project 4--File Systems
@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
+file system without actually worrying about how it was implemented
+underneath. For this last assignment, you will improve the
+implementation of the file system. 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.
-
-FIXME FIXME FIXME
-The first step is to understand the default filesystem provided by the
-base code. The first things you should look at are
-@file{threads/init.c} and @file{filesys/fsutil.c}: there are special
-command line arguments to Pintos which are used to format and
-manipulate the emulated disk. Specifically, @option{-f} formats the
-file system disk for use with Pintos, and @option{-cp @var{src}
-@var{dst}} copies @var{src} on the Unix filesystem to @var{dst} on the
-file system disk. With this information, you should be able to
-compile the base code and try out the command: @samp{pintos -f -cp
-./small small} to copy the file @file{small} from your working
-directory into the Pintos file system.
-
-FIXME FIXME FIXME
-One thing you should realize immediately is that, until you use the
-above operation to copy the shell (or whatever your initial program
-is) to the emulated disk, Pintos will be unable to do very much useful
-work (it'll try to open the shell and fail, thereby quitting out). You
-will also find that you won't be able to do interesting things until
-you copy a variety of programs to the disk. A useful technique, once
-your inode formats are finalized, is to create a clean reference disk
-and copy that over whenever you trash your disk beyond a useful state
-(which will probably happen quite often while debugging).
+You may build project 4 on top of project 2 or project 3. In either
+case, all of the functionality needed for project 2 must work in your
+filesys submission. If you build on project 3, then all of the project
+3 functionality must work also, and you will need to edit
+@file{filesys/Make.vars} to enable VM functionality. You can receive up
+to 5% extra credit if you do enable VM.
+
+@menu
+* Project 4 Background::
+* Project 4 Suggested Order of Implementation::
+* Project 4 Requirements::
+* Project 4 FAQ::
+@end menu
+
+@node Project 4 Background
+@section Background
@menu
* File System New Code::
-* Problem 4-1 Large Files::
-* Problem 4-2 File Growth::
-* Problem 4-3 Subdirectories::
-* Problem 4-4 Buffer Cache::
-* File System Design Document Requirements::
-* File System FAQs::
+* Testing File System Persistence::
@end menu
@node File System New Code
-@section New Code
+@subsection 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
+Simple utilities for the file system that are accessible from the
kernel command line.
@item filesys.h
@itemx filesys.c
-Top-level interface to the file system.
+Top-level interface to the file system. @xref{Using the File System},
+for an introduction.
@item directory.h
@itemx directory.c
-Translates file names to disk file headers; the
-directory data structure is stored as a file.
+Translates file names to inodes. The directory data structure is
+stored as a file.
-@item filehdr.h
-@itemx filehdr.c
+@item inode.h
+@itemx inode.c
Manages the data structure representing the layout of a
file's data on disk.
Translates file reads and writes to disk sector reads
and writes.
-@item devices/disk.h
-@itemx devices/disk.c
-Provides access to the physical disk, abstracting away the rather
-awful IDE interface.
-
@item lib/kernel/bitmap.h
@itemx lib/kernel/bitmap.c
A bitmap data structure along with routines for reading and writing
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
-filesystem is usable right off the bat. In fact, you've been using it
+file system is usable from the start, as you've seen
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 Problem 4-1 Large Files
-@section Problem 4-1: Large Files
-
-Modify the file system to allow the maximum size of a file to be as
-large as the disk. You can assume that the disk will not be larger
-than 8 MB. In the basic file system, each file is limited to a file
-size of just under 64 kB. Each file has a header (@code{struct
-filehdr}) that is a table of direct pointers to the disk blocks for
-that file. Since the header is stored in one disk sector, the maximum
-size of a file is limited by the number of pointers that will fit in
-one disk sector. Increasing the limit to 8 MB 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 FileHeader 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 file header remain
-properly synchronized.
-
-@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.
-
-To take advantage of hierarchical name spaces in user programs,
-provide the following syscalls:
-
-@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. If 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 use,
-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 algoritm in your design document.
-
-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 implement some manner to
-periodically write all cached blocks to disk. If you have
-@code{timer_sleep()} from the first project working, this is an
-excellent application for it.
-
-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.
-
-FIXME
-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 print its various statistics.
-
-@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 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 FAQs
-@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.
-
+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
-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.
+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
-@b{What exec modes for running Pintos do I absolutely need to
-support?}
-
-FIXME FIXME
-The most standard mode is to run your Pintos with all the command
-flags on one command line, like this: @samp{pintos -f -cp shell
-shell -ex "shell"}. However, you also need to support these flags
-individually---especially since that's how the grader tests your
-program. Thus, you should be able to run the above instead as:
-
-FIXME
-@example
-pintos -f
-pintos -cp shell shell
-pintos -ex "shell"
-@end example
-
-Note that this also provides a way for you to validate that your disks
-are really persistent. This is a common problem with a write behind
-cache: if you don't shut down properly it will leave the disk in an
-inconsistent state.
+Extensible files (@pxref{Indexed and Extensible Files}). After this
+step, your project should pass the file growth tests.
@item
-@b{Will you test our file system with a different @code{DISK_SECTOR_SIZE}?}
-
-No, @code{DISK_SECTOR_SIZE} will not change.
-
-@item
-@b{Will the @code{struct filehdr} take up space on the disk too?}
-
-Yes. Anything stored in @code{struct filehdr} takes up space on disk,
-so you must include this in your calculation of how many entires will
-fit in a single disk sector.
+Subdirectories (@pxref{Subdirectories}). Afterward, your project
+should pass the directory tests.
@item
-File Growth FAQs
+Remaining miscellaneous items.
+@end enumerate
-@enumerate 1
-@item
-@b{What is the largest file size that we are supposed to support?}
+You can implement extensible files and subdirectories in parallel if
+you temporarily make the number of entries in new directories fixed.
-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 @code{struct filehdr}
-(inode) organization.
-@end enumerate
+You should think about synchronization throughout.
-@item
-Subdirectory FAQs
+@node Project 4 Requirements
+@section Requirements
-@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?}
+@menu
+* Project 4 Design Document::
+* Indexed and Extensible Files::
+* Subdirectories::
+* Buffer Cache::
+* File System Synchronization::
+@end menu
-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.
+@node Project 4 Design Document
+@subsection Design Document
+
+Before you turn in your project, you must copy @uref{filesys.tmpl, , the
+project 4 design document template} into your source tree under the name
+@file{pintos/src/filesys/DESIGNDOC} and fill it in. We recommend that
+you read the design document template before you start working on the
+project. @xref{Project Documentation}, for a sample design document
+that goes along with a fictitious project.
+
+@node Indexed and Extensible Files
+@subsection Indexed and Extensible Files
+
+The basic file system allocates files as a single extent, making it
+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
+rationale for it in your design documentation, and as long as it does
+not suffer from external fragmentation (as does the extent-based file
+system we provide).
+
+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
+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 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 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.
+
+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
+read starting from a position past EOF returns no 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 Subdirectories
+@subsection Subdirectories
-@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)?}
+Implement a hierarchical name space. In the basic file system, all
+files live in a single directory. Modify this to allow directory
+entries to point to files or to other directories.
-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.
+Make sure that directories can expand beyond their original size just
+as any other file can.
+
+The basic file system has a 14-character limit on file names. You may
+retain this limit for individual file name components, or may extend
+it, at your option. You must allow full path names to be
+much longer than 14 characters.
+
+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 (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:
+
+@deftypefn {System Call} bool chdir (const char *@var{dir})
+Changes the current working directory of the process to
+@var{dir}, which may be relative or absolute. Returns true if
+successful, false on failure.
+@end deftypefn
-@item
-@b{When should the @code{lsdir} system call return?}
+@deftypefn {System Call} bool mkdir (const char *@var{dir})
+Creates the directory named @var{dir}, which may be
+relative or absolute. Returns true if successful, false on failure.
+Fails if @var{dir} already exists or if any directory name in
+@var{dir}, besides the last, does not already exist. That is,
+@code{mkdir("/a/b/c")} succeeds only if @file{/a/b} already exists and
+@file{/a/b/c} does not.
+@end deftypefn
+
+@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.
+We have also provided @command{pwd}, which is not so straightforward.
+The @command{shell} program implements @command{cd} internally.
+
+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 significant
+extra effort on your part.
+
+@node Buffer Cache
+@subsection Buffer Cache
-The @code{lsdir} system call should not return until after the
-directory has been printed. Here's a code fragment, and the desired
-output:
+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 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.
+
+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.
+
+The provided inode code uses a ``bounce buffer'' allocated with
+@func{malloc} to translate the disk's sector-by-sector interface into
+the system call interface's byte-by-byte interface. You should get rid
+of these bounce buffers. Instead, copy data into and out of sectors in
+the buffer cache directly.
+
+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, write-behind is
+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
+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.
+
+@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
+the design process. This is very difficult. These groups have often
+turned in projects that failed most or all of the tests.
+
+@node File System Synchronization
+@subsection 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 must adopt a finer-grained
+synchronization strategy that does not require external synchronization.
+To the extent possible, operations on independent entities should be
+independent, so that they do not need to wait on each other.
+
+Operations on different cache blocks must be independent. In
+particular, when I/O is required on a particular block, operations on
+other blocks that do not require I/O should proceed without having to
+wait for the I/O to complete.
+
+Multiple processes must be able to access a single file at once.
+Multiple reads of a single file must be able to complete without
+waiting for one another. When writing to a file does not extend the
+file, multiple processes should also be able to write a single file at
+once. A read of a file by one process when the file is being written by
+another process is allowed to show that none, all, or part of the write
+has completed. (However, after the @code{write} system call returns to
+its caller, all subsequent readers must see the change.) Similarly,
+when two processes simultaneously write to the same part of a file,
+their data may be interleaved.
+
+On the other hand, extending a file and writing data into the new
+section must be atomic. Suppose processes A and B both have a given
+file open and both are positioned at end-of-file. If A reads and B
+writes the file at the same time, A may read all, part, or none of what
+B writes. However, A may not read data other than what B writes, e.g.@:
+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
-@example
-printf ("Start of directory\n");
-lsdir ();
-printf ("End of directory\n");
-@end example
+@table @b
+@item How much code will I need to write?
+
+Here's a summary of our reference solution, produced by the
+@command{diffstat} program. The final row gives total lines inserted
+and deleted; a changed line counts as both an insertion and a deletion.
+
+This summary is relative to the Pintos base code, but the reference
+solution for project 4 is based on the reference solution to project 3.
+Thus, the reference solution runs with virtual memory enabled.
+@xref{Project 3 FAQ}, for the summary of project 3.
+
+The reference solution represents just one possible solution. Many
+other solutions are also possible and many of those differ greatly from
+the reference solution. Some excellent solutions may not modify all the
+files modified by the reference solution, and some may modify files not
+modified by the reference solution.
+
+@verbatim
+ Makefile.build | 5
+ devices/timer.c | 42 ++
+ filesys/Make.vars | 6
+ filesys/cache.c | 473 +++++++++++++++++++++++++
+ filesys/cache.h | 23 +
+ filesys/directory.c | 99 ++++-
+ filesys/directory.h | 3
+ filesys/file.c | 4
+ filesys/filesys.c | 194 +++++++++-
+ filesys/filesys.h | 5
+ filesys/free-map.c | 45 +-
+ filesys/free-map.h | 4
+ filesys/fsutil.c | 8
+ filesys/inode.c | 444 ++++++++++++++++++-----
+ filesys/inode.h | 11
+ threads/init.c | 5
+ threads/interrupt.c | 2
+ threads/thread.c | 32 +
+ threads/thread.h | 38 +-
+ userprog/exception.c | 12
+ userprog/pagedir.c | 10
+ userprog/process.c | 332 +++++++++++++----
+ userprog/syscall.c | 582 ++++++++++++++++++++++++++++++-
+ userprog/syscall.h | 1
+ vm/frame.c | 161 ++++++++
+ vm/frame.h | 23 +
+ vm/page.c | 297 +++++++++++++++
+ vm/page.h | 50 ++
+ vm/swap.c | 85 ++++
+ vm/swap.h | 11
+ 30 files changed, 2721 insertions(+), 286 deletions(-)
+@end verbatim
+
+@item Can @code{BLOCk_SECTOR_SIZE} change?
+
+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
-This code should create the following output:
+@menu
+* Indexed Files FAQ::
+* Subdirectories FAQ::
+* Buffer Cache FAQ::
+@end menu
-@example
-Start of directory
-... directory contents ...
-End of directory
-@end example
+@node Indexed Files FAQ
+@subsection Indexed Files FAQ
-@item
-@b{Do we have to implement both absolute and relative pathnames?}
+@table @b
+@item What is the largest file size that we are supposed to support?
-Yes. Implementing @file{.} and @file{..} is extra credit, though.
+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
-@item
-@b{Should @code{remove()} also be able to remove directories?}
+@node Subdirectories FAQ
+@subsection Subdirectories FAQ
-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
+@table @b
+@item How should a file name like @samp{a//b} be interpreted?
-@item
-Buffer Cache FAQs
+Multiple consecutive slashes are equivalent to a single slash, so this
+file name is the same as @samp{a/b}.
-@enumerate 1
-@item
-@b{We're limited to a 64-block cache, but can we also keep a copy of
-each @code{struct filehdr} for an open file inside @code{struct file},
-the way the stub code does?}
+@item How about a file name like @samp{/../x}?
-No, you shouldn't keep any disk sectors stored anywhere outside the
-cache. That means you'll have to change the way the file
-implementation accesses its corresponding inode right now, since it
-currently just creates a new @code{struct filehdr} in its constructor
-and reads the corresponding sector in from disk when it's created.
+The root directory is its own parent, so it is equivalent to @samp{/x}.
-There are two reasons for not storing inodes in @code{struct file}.
-First, keeping extra copies of inodes would be cheating the 64-block
-limitation that we place on your cache. Second, if two processes have
-the same file open, you will create a huge synchronization headache
-for yourself if each @code{struct file} has its own copy of the inode.
+@item How should a file name that ends in @samp{/} be treated?
-Note that you can store pointers to inodes in @code{struct file} if
-you want, and you can store some other small amount of information to
-help you find the inode when you need it.
+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
-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.
+@node Buffer Cache FAQ
+@subsection Buffer Cache FAQ
-@item
-@b{But why can't we store copies of inodes in @code{struct file}? We
-don't understand the answer to the previous question.}
-
-The issue regarding storing @code{struct filehdr}s has to do with
-implementation of the buffer cache. Basically, you can't store a
-@code{struct filehdr *} in @code{struct filehdr}. Each time you need
-to read a @code{struct filehdr}, you'll have to get it either from the
-buffer cache or from disk.
-
-If you look at @code{file_read_at()}, it uses @code{hdr} directly
-without having first read in that sector from wherever it was in the
-storage hierarchy. You are no longer allowed to do this. You will
-need to change @code{file_read_at} (and similar functions) so that it
-reads @code{hdr} from the storage hierarchy before using it.
-@end enumerate
-@end enumerate
+@table @b
+@item Can we keep a @struct{inode_disk} inside @struct{inode}?
+
+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.
+
+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 from disk when it's created. Keeping extra
+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}, 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.
+
+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{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} to obtain the
+@struct{inode_disk} from the cache before using it.
+@end table
projects / pintos-anon / blobdiff