1 @node Project 4--File Systems
2 @chapter Project 4: File Systems
4 In the previous two assignments, you made extensive use of a
5 file system without actually worrying about how it was implemented
6 underneath. For this last assignment, you will improve the
7 implementation of the file system. You will be working primarily in
8 the @file{filesys} directory.
10 You may build project 4 on top of project 2 or project 3. In either
11 case, all of the functionality needed for project 2 must work in your
12 filesys submission. If you build on project 3, then all of the project
13 3 functionality must work also, and you will need to edit
14 @file{filesys/Make.vars} to enable VM functionality. You can receive up
15 to 5% extra credit if you do enable VM.
17 The tests for project 4 will probably run faster if
18 you use the qemu emulator, e.g.@: via @code{make check
22 * Project 4 Background::
23 * Project 4 Requirements::
27 @node Project 4 Background
31 * File System New Code::
34 @node File System New Code
37 Here are some files that are probably new to you. These are in the
38 @file{filesys} directory except where indicated:
42 Simple utilities for the file system that are accessible from the
47 Top-level interface to the file system. @xref{Using the File System},
52 Translates file names to inodes. The directory data structure is
57 Manages the data structure representing the layout of a
62 Translates file reads and writes to disk sector reads
65 @item lib/kernel/bitmap.h
66 @itemx lib/kernel/bitmap.c
67 A bitmap data structure along with routines for reading and writing
68 the bitmap to disk files.
71 Our file system has a Unix-like interface, so you may also wish to
72 read the Unix man pages for @code{creat}, @code{open}, @code{close},
73 @code{read}, @code{write}, @code{lseek}, and @code{unlink}. Our file
74 system has calls that are similar, but not identical, to these. The
75 file system translates these calls into disk operations.
77 All the basic functionality is there in the code above, so that the
78 file system is usable from the start, as you've seen
79 in the previous two projects. However, it has severe limitations
80 which you will remove.
82 While most of your work will be in @file{filesys}, you should be
83 prepared for interactions with all previous parts.
85 @node Project 4 Requirements
89 * Project 4 Design Document::
90 * Indexed and Extensible Files::
93 * File System Synchronization::
96 @node Project 4 Design Document
97 @subsection Design Document
99 Before you turn in your project, you must copy @uref{filesys.tmpl, , the
100 project 4 design document template} into your source tree under the name
101 @file{pintos/src/filesys/DESIGNDOC} and fill it in. We recommend that
102 you read the design document template before you start working on the
103 project. @xref{Project Documentation}, for a sample design document
104 that goes along with a fictitious project.
106 @node Indexed and Extensible Files
107 @subsection Indexed and Extensible Files
109 The basic file system allocates files as a single extent, making it
110 vulnerable to external fragmentation, that is, it is possible that an
111 @var{n}-block file cannot be allocated even though @var{n} blocks are
112 free. Eliminate this problem by
113 modifying the on-disk inode structure. In practice, this probably means using
114 an index structure with direct, indirect, and doubly indirect blocks.
115 You are welcome to choose a different scheme as long as you explain the
116 rationale for it in your design documentation, and as long as it does
117 not suffer from external fragmentation (as does the extent-based file
120 You can assume that the disk will not be larger than 8 MB. You must
121 support files as large as the disk (minus metadata). Each inode is
122 stored in one disk sector, limiting the number of block pointers that it
123 can contain. Supporting 8 MB files will require you to implement
124 doubly-indirect blocks.
126 An extent-based file can only grow if it is followed by empty space, but
127 indexed inodes make file growth possible whenever free space is
128 available. Implement file growth. In the basic file system, the file
129 size is specified when the file is created. In most modern file
130 systems, a file is initially created with size 0 and is then expanded
131 every time a write is made off the end of the file. Your file system
134 There should be no predetermined limit on the size of a file, except
135 that a file cannot exceed the size of the disk (minus metadata). This
136 also applies to the root directory file, which should now be allowed
137 to expand beyond its initial limit of 16 files.
139 The user is allowed to seek beyond the current end-of-file (EOF). The
140 seek itself does not extend the file. Writing at a position past EOF
141 extends the file to the position being written, and any gap between the
142 previous EOF and the start of the write must be filled with zeros. A
143 read starting from a position past EOF returns no bytes.
145 Writing far beyond EOF can cause many blocks to be entirely zero. Some
146 file systems allocate and write real data blocks for these implicitly
147 zeroed blocks. Other file systems do not allocate these blocks at all
148 until they are explicitly written. The latter file systems are said to
149 support ``sparse files.'' You may adopt either allocation strategy in
153 @subsection Subdirectories
155 Implement a hierarchical name space. In the basic file system, all
156 files live in a single directory. Modify this to allow directory
157 entries to point to files or to other directories.
159 Make sure that directories can expand beyond their original size just
160 as any other file can.
162 The basic file system has a 14-character limit on file names. You may
163 retain this limit for individual file name components, or may extend
164 it, at your option. You must allow full path names to be
165 much longer than 14 characters.
167 Maintain a separate current directory for each process. At
168 startup, set the root as the initial process's current directory.
169 When one process starts another with the @code{exec} system call, the
170 child process inherits its parent's current directory. After that, the
171 two processes' current directories are independent, so that either
172 changing its own current directory has no effect on the other.
173 (This is why, under Unix, the @command{cd} command is a shell built-in,
174 not an external program.)
176 Update the existing system calls so that, anywhere a file name is
177 provided by the caller, an absolute or relative path name may used.
178 The directory separator character is forward slash (@samp{/}).
180 Update the @code{remove} system call so that it can delete empty
181 directories in addition to regular files. Directories can only be
182 deleted if they do not contain any files or subdirectories.
184 Implement the following new system calls:
186 @deftypefn {System Call} bool chdir (const char *@var{dir})
187 Changes the current working directory of the process to
188 @var{dir}, which may be relative or absolute. Returns true if
189 successful, false on failure.
192 @deftypefn {System Call} bool mkdir (const char *@var{dir})
193 Creates the directory named @var{dir}, which may be
194 relative or absolute. Returns true if successful, false on failure.
195 Fails if @var{dir} already exists or if any directory name in
196 @var{dir}, besides the last, does not already exist. That is,
197 @code{mkdir("/a/b/c")} succeeds only if @file{/a/b} already exists and
198 @file{/a/b/c} does not.
201 @deftypefn {System Call} void lsdir (void)
202 Prints a list of files in the current directory to @code{stdout}, one
203 per line, in no particular order.
206 We have provided @command{ls} and @command{mkdir} user programs, which
207 are straightforward once the above syscalls are implemented.
209 The @code{pintos} @option{put} and @option{get} commands should now
210 accept full path names, assuming that the directories used in the
211 paths have already been created. This should not require any extra
214 You may support @file{.} and @file{..} for a small amount of extra
218 @subsection Buffer Cache
220 Modify the file system to keep a cache of file blocks. When a request
221 is made to read or write a block, check to see if it is in the
222 cache, and if so, use the cached data without going to
223 disk. Otherwise, fetch the block from disk into cache, evicting an
224 older entry if necessary. You are limited to a cache no greater than 64
227 Be sure to choose an intelligent cache replacement algorithm.
228 Experiment to see what combination of accessed, dirty, and other
229 information results in the best performance, as measured by the number
230 of disk accesses. For example, metadata is generally more valuable to
233 You can keep a cached copy of the free map permanently in memory if you
234 like. It doesn't have to count against the cache size.
236 The provided inode code uses a ``bounce buffer'' allocated with
237 @func{malloc} to translate the disk's sector-by-sector interface into
238 the system call interface's byte-by-byte interface. You should get rid
239 of these bounce buffers. Instead, copy data into and out of sectors in
240 the buffer cache directly.
242 Your cache should be @dfn{write-behind}, that is,
243 keep dirty blocks in the cache, instead of immediately writing modified
244 data to disk. Write dirty blocks to disk whenever they are evicted.
245 Because write-behind makes your file system more fragile in the face of
246 crashes, in addition you should periodically write all dirty, cached
247 blocks back to disk. The cache should also be written back to disk in
248 @func{filesys_done}, so that halting Pintos flushes the cache.
250 If you have @func{timer_sleep} from the first project working, write-behind is
251 an excellent application. If you're still using the base
252 implementation of @func{timer_sleep}, be aware that it busy-waits, which
253 is not acceptable here (or elsewhere). If @func{timer_sleep}'s delays seem too
254 short or too long, reread the explanation of the @option{-r} option to
255 @command{pintos} (@pxref{Debugging versus Testing}).
257 You should also implement @dfn{read-ahead}, that is,
258 automatically fetch the next block of a file
259 into the cache when one block of a file is read, in case that block is
261 Read-ahead is only really useful when done asynchronously. That means,
262 if a process requests disk block 1 from the file, it should block until disk
263 block 1 is read in, but once that read is complete, control should
264 return to the process immediately. The read-ahead request for disk
265 block 2 should be handled asynchronously, in the background.
267 @strong{We recommend integrating the cache into your design early.} In
268 the past, many groups have tried to tack the cache onto a design late in
269 the design process. This is very difficult. These groups have often
270 turned in projects that failed most or all of the tests.
272 @node File System Synchronization
273 @subsection Synchronization
275 The provided file system requires external synchronization, that is,
276 callers must ensure that only one thread can be running in the file
277 system code at once. Your submission must adopt a finer-grained
278 synchronization strategy that does not require external synchronization.
279 To the extent possible, operations on independent entities should be
280 independent, so that they do not need to wait on each other.
282 Operations on different cache blocks must be independent. In
283 particular, when I/O is required on a particular block, operations on
284 other blocks that do not require I/O should proceed without having to
285 wait for the I/O to complete.
287 Multiple processes must be able to access a single file at once.
288 Multiple reads of a single file must be able to complete without
289 waiting for one another. When writing to a file does not extend the
290 file, multiple processes should also be able to write a single file at
291 once. A read of a file by one process when the file is being written by
292 another process is allowed to show that none, all, or part of the write
293 has completed. (However, after the @code{write} system call returns to
294 its caller, all subsequent readers must see the change.) Similarly,
295 when two processes simultaneously write to the same part of a file,
296 their data may be interleaved.
298 On the other hand, extending a file and writing data into the new
299 section must be atomic. Suppose processes A and B both have a given
300 file open and both are positioned at end-of-file. If A reads and B
301 writes the file at the same time, A may read all, part, or none of what
302 B writes. However, A may not read data other than what B writes, e.g.@:
303 if B's data is all nonzero bytes, A is not allowed to see any zeros.
305 Operations on different directories should take place concurrently.
306 Operations on the same directory may wait for one another.
312 @item How much code will I need to write?
314 Here's a summary of our reference solution, produced by the
315 @command{diffstat} program. The final row gives total lines inserted
316 and deleted; a changed line counts as both an insertion and a deletion.
318 This summary is relative to the Pintos base code, but the reference
319 solution for project 4 is based on the reference solution to project 3.
320 Thus, the reference solution runs with virtual memory enabled.
321 @xref{Project 3 FAQ}, for the summary of project 3.
323 The reference solution represents just one possible solution. Many
324 other solutions are also possible and many of those differ greatly from
325 the reference solution. Some excellent solutions may not modify all the
326 files modified by the reference solution, and some may modify files not
327 modified by the reference solution.
331 devices/timer.c | 42 ++
332 filesys/Make.vars | 6
333 filesys/cache.c | 473 +++++++++++++++++++++++++
334 filesys/cache.h | 23 +
335 filesys/directory.c | 99 ++++-
336 filesys/directory.h | 3
338 filesys/filesys.c | 194 +++++++++-
339 filesys/filesys.h | 5
340 filesys/free-map.c | 45 +-
341 filesys/free-map.h | 4
343 filesys/inode.c | 444 ++++++++++++++++++-----
346 threads/interrupt.c | 2
347 threads/thread.c | 32 +
348 threads/thread.h | 38 +-
349 userprog/exception.c | 12
350 userprog/pagedir.c | 10
351 userprog/process.c | 332 +++++++++++++----
352 userprog/syscall.c | 582 ++++++++++++++++++++++++++++++-
353 userprog/syscall.h | 1
354 vm/frame.c | 161 ++++++++
356 vm/page.c | 297 +++++++++++++++
360 30 files changed, 2721 insertions(+), 286 deletions(-)
363 @item What extra credit opportunities are available?
365 You may implement Unix-style support for @file{.} and @file{..} in
366 relative paths in their projects.
368 You may submit with VM enabled.
370 @item Can @code{DISK_SECTOR_SIZE} change?
372 No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
373 of IDE disk hardware.
377 * Indexed Files FAQ::
381 @node Indexed Files FAQ
382 @subsection Indexed Files FAQ
385 @item What is the largest file size that we are supposed to support?
387 The disk we create will be 8 MB or smaller. However, individual files
388 will have to be smaller than the disk to accommodate the metadata.
389 You'll need to consider this when deciding your inode organization.
392 @node Buffer Cache FAQ
393 @subsection Buffer Cache FAQ
396 @item Can we keep a @struct{inode_disk} inside @struct{inode}?
398 The goal of the 64-block limit is to bound the amount of cached file
399 system data. If you keep a block of disk data---whether file data or
400 metadata---anywhere in kernel memory then you have to count it against
401 the 64-block limit. The same rule applies to anything that's
402 ``similar'' to a block of disk data, such as a @struct{inode_disk}
403 without the @code{length} or @code{sector_cnt} members.
405 That means you'll have to change the way the inode implementation
406 accesses its corresponding on-disk inode right now, since it currently
407 just embeds a @struct{inode_disk} in @struct{inode} and reads the
408 corresponding sector from disk when it's created. Keeping extra
409 copies of inodes would subvert the 64-block limitation that we place
412 You can store a pointer to inode data in @struct{inode}, but it you do
413 so you should carefully make sure that this does not limit your OS to 64
414 simultaneously open files.
415 You can also store other information to help you find the inode when you
416 need it. Similarly, you may store some metadata along each of your 64
419 You can keep a cached copy of the free map permanently in memory if you
420 like. It doesn't have to count against the cache size.
422 @func{byte_to_sector} in @file{filesys/inode.c} uses the
423 @struct{inode_disk} directly, without first reading that sector from
424 wherever it was in the storage hierarchy. This will no longer work.
425 You will need to change @func{inode_byte_to_sector} to obtain the
426 @struct{inode_disk} from the cache before using it.