1 @node Project 4--File Systems, References, Project 3--Virtual Memory, Top
2 @chapter Project 4: File Systems
4 In the previous two assignments, you made extensive use of a
5 filesystem without actually worrying about how it was implemented
6 underneath. For this last assignment, you will fill in the
7 implementation of the filesystem. You will be working primarily in
8 the @file{filesys} directory.
10 You should build on the code you wrote for the previous assignments.
11 However, if you wish, you may turn off your VM features, as they are
12 not vital to making the filesystem work. (You will need to edit
13 @file{filesys/Makefile.vars} to fully disable VM.) All of the
14 functionality needed for project 2 (argument passing, syscalls and
15 multiprogramming) must work in your filesys submission.
17 On the other hand, one of the particular charms of working on
18 operating systems is being able to use what you build, and building
19 full-featured systems. Therefore, you should strive to make all the
20 parts work together so that you can run VM and your filesystem at the
21 same time. Plus, keeping VM is a great way to stress-test your
22 filesystem implementation.
24 Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
25 @file{constants.h} (@pxref{Conditional Compilation}).
28 * File System New Code::
29 * Problem 4-1 Large Files::
30 * Problem 4-2 File Growth::
31 * Problem 4-3 Subdirectories::
32 * Problem 4-4 Buffer Cache::
33 * File System Design Document Requirements::
37 @node File System New Code
40 Here are some files that are probably new to you. These are in the
41 @file{filesys} directory except where indicated:
45 Simple utilities for the filesystem that are accessible from the
50 Top-level interface to the file system.
54 Translates file names to inodes. The directory data structure is
59 Manages the data structure representing the layout of a
64 Translates file reads and writes to disk sector reads
67 @item lib/kernel/bitmap.h
68 @itemx lib/kernel/bitmap.c
69 A bitmap data structure along with routines for reading and writing
70 the bitmap to disk files.
73 Our file system has a Unix-like interface, so you may also wish to
74 read the Unix man pages for @code{creat}, @code{open}, @code{close},
75 @code{read}, @code{write}, @code{lseek}, and @code{unlink}. Our file
76 system has calls that are similar, but not identical, to these. The
77 file system translates these calls into physical disk operations.
79 All the basic functionality is there in the code above, so that the
80 filesystem is usable right off the bat. In fact, you've been using it
81 in the previous two projects. However, it has severe limitations
82 which you will remove.
84 While most of your work will be in @file{filesys}, you should be
85 prepared for interactions with all previous parts (as usual).
87 @node Problem 4-1 Large Files
88 @section Problem 4-1: Large Files
90 Modify the file system to allow the maximum size of a file to be as
91 large as the disk. You can assume that the disk will not be larger
92 than 8 MB. In the basic file system, each file is limited to a file
93 size of just under 64 kB. Each file has a header called an index node
94 or @dfn{inode} (represented by @struct{inode}) that is a table of
95 direct pointers to the disk blocks for that file. Since the inode is
96 stored in one disk sector, the maximum size of a file is limited by
97 the number of pointers that will fit in one disk sector. Increasing
98 the limit to 8 MB will require you to implement doubly-indirect
101 @node Problem 4-2 File Growth
102 @section Problem 4-2: File Growth
104 Implement extensible files. In the basic file system, the file size
105 is specified when the file is created. One advantage of this is that
106 the inode data structure, once created, never changes. In UNIX and
107 most other file systems, a file is initially created with size 0 and
108 is then expanded every time a write is made off the end of the file.
109 Modify the file system to allow this. As one test case, allow the
110 root directory file to expand beyond its current limit of ten files.
111 Make sure that concurrent accesses to the inode remain properly
114 The user is allowed to seek beyond the current end-of-file (EOF). The
115 seek itself does not extend the file. Writing at a position past EOF
116 extends the file to the position being written, and any gap between the
117 previous EOF and the start of the write must be filled with zeros. A
118 read past EOF returns zero bytes.
120 Writing far beyond EOF can cause many blocks to be entirely zero. Some
121 file systems allocate and write real data blocks for these implicitly
122 zeroed blocks. Other file systems do not allocate these blocks at all
123 until they are explicitly written. The latter file systems are said to
124 support ``sparse files.'' You may adopt either allocation strategy in
127 @node Problem 4-3 Subdirectories
128 @section Problem 4-3: Subdirectories
130 Implement a hierarchical name space. In the basic file system, all
131 files live in a single directory. Modify this to allow directories to
132 point to either files or other directories. To do this, you will need
133 to implement routines that parse path names into a sequence of
134 directories, as well as routines that change the current working
135 directory and that list the contents of the current directory. For
136 performance, allow concurrent updates to different directories, but
137 use mutual exclusion to ensure that updates to the same directory are
138 performed atomically (for example, to ensure that a file is deleted
141 Make sure that directories can expand beyond their original size just
142 as any other file can.
144 Each process has its own current directory. When one process starts
145 another with the @code{exec} system call, the child process inherits its
146 parent's current directory. After that, the two processes' current
147 directories are independent, so that either changing its own current
148 directory has no effect on the other.
150 Update the existing system calls so that, anywhere a file name is
151 provided by the caller, an absolute or relative path name may used.
152 Also, implement the following new system calls:
156 @itemx bool chdir (const char *@var{dir})
157 Attempts to change the current working directory of the process to
158 @var{dir}, which may be either relative or absolute. Returns true if
159 successful, false on failure.
162 @itemx bool mkdir (const char *dir)
163 Attempts to create the directory named @var{dir}, which may be either
164 relative or absolute. Returns true if successful, false on failure.
167 @itemx void lsdir (void)
168 Prints a list of files in the current directory to @code{stdout}, one
172 Also write the @command{ls} and @command{mkdir} user programs. This
173 is straightforward once the above syscalls are implemented. In Unix,
174 these are programs rather than built-in shell commands, but
175 @command{cd} is a shell command. (Why?)
177 @node Problem 4-4 Buffer Cache
178 @section Problem 4-4: Buffer Cache
180 Modify the file system to keep a cache of file blocks. When a request
181 is made to read or write a block, check to see if it is stored in the
182 cache, and if so, fetch it immediately from the cache without going to
183 disk. (Otherwise, fetch the block from disk into cache, evicting an
184 older entry if necessary.) You are limited to a cache no greater than
185 64 sectors in size. Be sure to choose an intelligent cache
186 replacement algorithm. Experiment to see what combination of accessed,
187 dirty, and other information results in the best performance, as
188 measured by the number of disk accesses. (For example, metadata is
189 generally more valuable to cache than data.) Document your
190 replacement algorithm in your design document.
192 The provided file system code uses a ``bounce buffer'' in @struct{file}
193 to translate the disk's sector-by-sector interface into the system call
194 interface's byte-by-byte interface. It needs per-file buffers because,
195 without them, there's no other good place to put sector
196 data.@footnote{The stack is not a good place because large objects
197 should not be allocated on the stack. A 512-byte sector is pushing the
198 limit there.} As part of implementing the buffer cache, you should get
199 rid of these bounce buffers. Instead, copy data into and out of sectors
200 in the buffer cache directly. You will probably need some
201 synchronization to prevent sectors from being evicted from the cache
202 while you are using them.
204 In addition to the basic file caching scheme, your implementation
205 should also include the following enhancements:
209 Instead of always immediately writing modified data to disk, dirty
210 blocks can be kept in the cache and written out sometime later. Your
211 buffer cache should write behind whenever a block is evicted from the
215 Your buffer cache should automatically fetch the next block of a file
216 into the cache when one block of a file is read, in case that block is
220 For each of these three optimizations, design a file I/O workload that
221 is likely to benefit from the enhancement, explain why you expect it
222 to perform better than on the original file system implementation, and
223 demonstrate the performance improvement.
225 Note that write-behind makes your filesystem more fragile in the face
226 of crashes. Therefore, you should
227 periodically write all cached blocks to disk. If you have
228 @func{timer_sleep} from the first project working, this is an
229 excellent application for it.
231 Likewise, read-ahead is only really useful when done asynchronously.
232 That is, if a process wants disk block 1 from the file, it needs to
233 block until disk block 1 is read in, but once that read is complete,
234 control should return to the process immediately while the read
235 request for disk block 2 is handled asynchronously. In other words,
236 the process will block to wait for disk block 1, but should not block
237 waiting for disk block 2.
239 When you're implementing this, please make sure you have a scheme for
240 making any read-ahead and write-behind threads halt when Pintos is
241 ``done'' (when the user program has completed, etc), so that Pintos
242 will halt normally and the disk contents will be consistent.
244 @node File System Design Document Requirements
245 @section Design Document Requirements
247 As always, submit a design document file summarizing your design. Be
248 sure to cover the following points:
252 How did you structure your inodes? How many blocks did you access
253 directly, via single-indirection, and/or via double-indirection? Why?
256 How did you structure your buffer cache? How did you perform a lookup
257 in the cache? How did you choose elements to evict from the cache?
260 How and when did you flush the cache?
263 @node File System FAQ
268 @b{What extra credit opportunities are available for this assignment?}
272 We'll give out extra credit to groups that implement Unix-style
273 support for @file{.} and @file{..} in relative paths in their projects.
276 We'll give some extra credit if you submit with VM enabled. If you do
277 this, make sure you show us that you can run multiple programs
278 concurrently. A particularly good demonstration is running
279 @file{capitalize} (with a reduced words file that fits comfortably on
280 your disk, of course). So submit a file system disk that contains a
281 VM-heavy program like @file{capitalize}, so we can try it out. And also
282 include the results in your test case file.
284 We feel that you will be much more satisfied with your cs140 ``final
285 product'' if you can get your VM working with your file system. It's
286 also a great stress test for your FS, but obviously you have to be
287 pretty confident with your VM if you're going to submit this extra
288 credit, since you'll still lose points for failing FS-related tests,
289 even if the problem is in your VM code.
292 A point of extra credit can be assigned if a user can recursively
293 remove directories from the shell command prompt. Note that the
294 typical semantic is to just fail if a directory is not empty.
297 Make sure that you discuss any extra credit in your @file{README}
298 file. We're likely to miss it if it gets buried in your design
302 @b{What exec modes for running Pintos do I absolutely need to
305 You also need to support the @option{-f}, @option{-ci}, @option{-co},
306 and @option{-ex} flags individually, and you need to handle them when
307 they're combined, like this: @samp{pintos -f -ci shell 12345 -ex
308 "shell"}. Thus, you should be able to treat the above as equivalent to:
312 pintos -ci shell 12345
316 If you don't change the filesystem interface, then this should already
317 be implemented properly in @file{threads/init.c} and
318 @file{filesys/fsutil.c}.
320 You must also implement the @option{-q} option and make sure that data
321 gets flushed out to disk properly when it is used.
324 @b{Will you test our file system with a different @code{DISK_SECTOR_SIZE}?}
326 No, @code{DISK_SECTOR_SIZE} is fixed at 512. This is a fixed property
327 of IDE disk hardware.
330 @b{Will the @struct{inode} take up space on the disk too?}
332 Yes. Anything stored in @struct{inode} takes up space on disk,
333 so you must include this in your calculation of how many entires will
334 fit in a single disk sector.
337 @b{What's the directory separator character?}
339 Forward slash (@samp{/}).
343 * Problem 4-2 File Growth FAQ::
344 * Problem 4-3 Subdirectory FAQ::
345 * Problem 4-4 Buffer Cache FAQ::
348 @node Problem 4-2 File Growth FAQ
349 @subsection Problem 4-2: File Growth FAQ
353 @b{What is the largest file size that we are supposed to support?}
355 The disk we create will be 8 MB or smaller. However, individual files
356 will have to be smaller than the disk to accommodate the metadata.
357 You'll need to consider this when deciding your @struct{inode}
361 @node Problem 4-3 Subdirectory FAQ
362 @subsection Problem 4-3: Subdirectory FAQ
366 @b{What's the answer to the question in the spec about why
367 @command{ls} and @command{mkdir} are user programs, while @command{cd}
370 Each process maintains its own current working directory, so it's much
371 easier to change the current working directory of the shell process if
372 @command{cd} is implemented as a shell command rather than as another
373 user process. In fact, Unix-like systems don't provide any way for
374 one process to change another process's current working directory.
377 @b{When the spec states that directories should be able to grow beyond
378 ten files, does this mean that there can still be a set maximum number
379 of files per directory that is greater than ten, or should directories
380 now support unlimited growth (bounded by the maximum supported file
383 We're looking for directories that can support arbitrarily large
384 numbers of files. Now that directories can grow, we want you to
385 remove the concept of a preset maximum file limit.
388 @b{When should the @code{lsdir} system call return?}
390 The @code{lsdir} system call should not return until after the
391 directory has been printed. Here's a code fragment, and the desired
395 printf ("Start of directory\n");
397 printf ("End of directory\n");
400 This code should create the following output:
404 ... directory contents ...
409 @b{Do we have to implement both absolute and relative pathnames?}
411 Yes. Implementing @file{.} and @file{..} is extra credit, though.
414 @b{Should @func{remove} also be able to remove directories?}
416 Yes. The @code{remove} system call should handle removal of both
417 regular files and directories. You may assume that directories can
418 only be deleted if they are empty, as in Unix.
421 @node Problem 4-4 Buffer Cache FAQ
422 @subsection Problem 4-4: Buffer Cache FAQ
426 @b{We're limited to a 64-block cache, but can we also keep an
427 @struct{inode_disk} inside @struct{inode}, the way the provided code
430 The goal of the 64-block limit is to bound the amount of cached file
431 system data. If you keep a block of disk data---whether file data or
432 metadata---anywhere in kernel memory then you have to count it against
433 the 64-block limit. The same rule applies to anything that's
434 ``similar'' to a block of disk data, such as a @struct{inode_disk}
435 without the @code{length} or @code{sector_cnt} members.
437 That means you'll have to change the way the inode implementation
438 accesses its corresponding on-disk inode right now, since it currently
439 just embeds a @struct{inode_disk} in @struct{inode} and reads the
440 corresponding sector in from disk when it's created.
442 There are two reasons for not storing inode data in @struct{inode}.
443 First, keeping extra copies of inodes would be cheating the 64-block
444 limitation that we place on your cache. Second, if two processes have
445 the same file open, you will create a huge synchronization headache for
446 yourself if each @struct{inode} has its own copy of the on-disk inode.
448 You can store pointers to inode data in @struct{inode}, if you want, and
449 you can store some other small amount of information to help you find
450 the inode when you need it. Similarly, if you want to store one block
451 of data plus some small amount of metadata for each of your 64 cache
452 entries, that's fine.
454 If you look at @func{inode_byte_to_sector}, it uses the
455 @struct{inode_disk} directly without having first read in that sector
456 from wherever it was in the storage hierarchy. This will no longer
457 work. You will need to change @func{inode_byte_to_sector} so that it
458 reads the @struct{inode_disk} from the storage hierarchy before using