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