-@node Project 4--File Systems, Multilevel Feedback Scheduling, Project 3--Virtual Memory, Top
+@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
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).
-
@menu
* File System New Code::
-* Problem 4-1 Large Files::
+* 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 FAQs::
+* File System FAQ::
@end menu
@node File System New Code
@item filesys.h
@itemx filesys.c
-Top-level interface to the file system.
+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 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
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
+@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
-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.
+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 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.
+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
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:
+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
@end table
Also write the @command{ls} and @command{mkdir} user programs. This
-is straightforward once the above syscalls are implemented. If Unix,
+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?)
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,
+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 algoritm in your design document.
+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:
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
+of crashes. Therefore, you should
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.
+@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
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.
+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 :
+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?
How and when did you flush the cache?
@end itemize
-@node File System FAQs
+@node File System FAQ
@section FAQ
@enumerate 1
@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:
+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:
-FIXME
@example
pintos -f
-pintos -cp shell shell
+pintos -ci shell 12345
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.
+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} will not change.
+No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
+of IDE disk hardware.
@item
-@b{Will the @code{struct filehdr} take up space on the disk too?}
+@b{Will the @struct{inode} take up space on the disk too?}
-Yes. Anything stored in @code{struct filehdr} takes up space on disk,
+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
-File Growth FAQs
+@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
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.
+You'll need to consider this when deciding your @struct{inode}
+organization.
@end enumerate
-@item
-Subdirectory FAQs
+@node Problem 4-3 Subdirectory FAQ
+@subsection Problem 4-3: Subdirectory FAQ
@enumerate 1
@item
Yes. Implementing @file{.} and @file{..} is extra credit, though.
@item
-@b{Should @code{remove()} also be able to remove directories?}
+@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
-@item
-Buffer Cache FAQs
+@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 a copy of
-each @code{struct filehdr} for an open file inside @code{struct file},
-the way the stub code does?}
-
-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.
-
-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.
-
-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.
-
-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.
-
-@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
+@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
projects / pintos-anon / blobdiff