Make more useful.
[pintos-anon] / doc / filesys.texi
1 @node Project 4--File Systems, Multilevel Feedback Scheduling, Project 3--Virtual Memory, Top
2 @chapter Project 4: File Systems
3
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.
9
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.
16
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.
23
24 Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
25 @file{constants.h} (@pxref{Conditional Compilation}).
26
27 FIXME FIXME FIXME
28 The first step is to understand the default filesystem provided by the
29 base code.  
30
31 @menu
32 * File System New Code::        
33 * Problem 4-1 Large Files::     
34 * Problem 4-2 File Growth::     
35 * Problem 4-3 Subdirectories::  
36 * Problem 4-4 Buffer Cache::    
37 * File System Design Document Requirements::  
38 * File System FAQs::            
39 @end menu
40
41 @node File System New Code
42 @section New Code
43
44 Here are some files that are probably new to you.  These are in the
45 @file{filesys} directory except where indicated:
46
47 @table @file
48 @item fsutil.c
49 Simple utilities for the filesystem that are accessible from the
50 kernel command line.
51
52 @item filesys.h
53 @itemx filesys.c
54 Top-level interface to the file system.
55
56 @item directory.h
57 @itemx directory.c
58 Translates file names to disk file headers; the
59 directory data structure is stored as a file.
60
61 @item filehdr.h
62 @itemx filehdr.c
63 Manages the data structure representing the layout of a
64 file's data on disk.
65
66 @item file.h
67 @itemx file.c
68 Translates file reads and writes to disk sector reads
69 and writes.
70
71 @item devices/disk.h
72 @itemx devices/disk.c
73 Provides access to the physical disk, abstracting away the rather
74 awful IDE interface.
75
76 @item lib/kernel/bitmap.h
77 @itemx lib/kernel/bitmap.c
78 A bitmap data structure along with routines for reading and writing
79 the bitmap to disk files.
80 @end table
81
82 Our file system has a Unix-like interface, so you may also wish to
83 read the Unix man pages for @code{creat}, @code{open}, @code{close},
84 @code{read}, @code{write}, @code{lseek}, and @code{unlink}.  Our file
85 system has calls that are similar, but not identical, to these.  The
86 file system translates these calls into physical disk operations.  
87
88 All the basic functionality is there in the code above, so that the
89 filesystem is usable right off the bat.  In fact, you've been using it
90 in the previous two projects.  However, it has severe limitations
91 which you will remove.
92
93 While most of your work will be in @file{filesys}, you should be
94 prepared for interactions with all previous parts (as usual).
95
96 @node Problem 4-1 Large Files
97 @section Problem 4-1: Large Files
98
99 Modify the file system to allow the maximum size of a file to be as
100 large as the disk.  You can assume that the disk will not be larger
101 than 8 MB.  In the basic file system, each file is limited to a file
102 size of just under 64 kB.  Each file has a header (@code{struct
103 filehdr}) that is a table of direct pointers to the disk blocks for
104 that file.  Since the header is stored in one disk sector, the maximum
105 size of a file is limited by the number of pointers that will fit in
106 one disk sector.  Increasing the limit to 8 MB will require you to
107 implement doubly-indirect blocks.
108
109 @node Problem 4-2 File Growth
110 @section Problem 4-2: File Growth
111
112 Implement extensible files.  In the basic file system, the file size
113 is specified when the file is created.  One advantage of this is that
114 the FileHeader data structure, once created, never changes.  In UNIX
115 and most other file systems, a file is initially created with size 0
116 and is then expanded every time a write is made off the end of the
117 file.  Modify the file system to allow this.  As one test case, allow
118 the root directory file to expand beyond its current limit of ten
119 files.  Make sure that concurrent accesses to the file header remain
120 properly synchronized.
121
122 @node Problem 4-3 Subdirectories
123 @section Problem 4-3: Subdirectories
124
125 Implement a hierarchical name space.  In the basic file system, all
126 files live in a single directory.  Modify this to allow directories to
127 point to either files or other directories.  To do this, you will need
128 to implement routines that parse path names into a sequence of
129 directories, as well as routines that change the current working
130 directory and that list the contents of the current directory.  For
131 performance, allow concurrent updates to different directories, but
132 use mutual exclusion to ensure that updates to the same directory are
133 performed atomically (for example, to ensure that a file is deleted
134 only once).
135
136 Make sure that directories can expand beyond their original size just
137 as any other file can.
138
139 To take advantage of hierarchical name spaces in user programs,
140 provide the following syscalls:
141
142 @table @code
143 @item SYS_chdir
144 @itemx bool chdir (const char *@var{dir})
145 Attempts to change the current working directory of the process to
146 @var{dir}, which may be either relative or absolute.  Returns true if
147 successful, false on failure.
148
149 @item SYS_mkdir
150 @itemx bool mkdir (const char *dir)
151 Attempts to create the directory named @var{dir}, which may be either
152 relative or absolute.  Returns true if successful, false on failure.
153
154 @item SYS_lsdir
155 @itemx void lsdir (void)
156 Prints a list of files in the current directory to @code{stdout}, one
157 per line.
158 @end table
159
160 Also write the @command{ls} and @command{mkdir} user programs.  This
161 is straightforward once the above syscalls are implemented.  If Unix,
162 these are programs rather than built-in shell commands, but
163 @command{cd} is a shell command.  (Why?)
164
165 @node Problem 4-4 Buffer Cache
166 @section Problem 4-4: Buffer Cache
167
168 Modify the file system to keep a cache of file blocks.  When a request
169 is made to read or write a block, check to see if it is stored in the
170 cache, and if so, fetch it immediately from the cache without going to
171 disk.  (Otherwise, fetch the block from disk into cache, evicting an
172 older entry if necessary.)  You are limited to a cache no greater than
173 64 sectors in size.  Be sure to choose an intelligent cache
174 replacement algorithm.  Experiment to see what combination of use,
175 dirty, and other information results in the best performance, as
176 measured by the number of disk accesses.  (For example, metadata is
177 generally more valuable to cache than data.)  Document your
178 replacement algoritm in your design document.
179
180 In addition to the basic file caching scheme, your implementation
181 should also include the following enhancements:
182
183 @table @b
184 @item write-behind:
185 Instead of always immediately writing modified data to disk, dirty
186 blocks can be kept in the cache and written out sometime later.  Your
187 buffer cache should write behind whenever a block is evicted from the
188 cache.
189
190 @item read-ahead:
191 Your buffer cache should automatically fetch the next block of a file
192 into the cache when one block of a file is read, in case that block is
193 about to be read.
194 @end table
195
196 For each of these three optimizations, design a file I/O workload that
197 is likely to benefit from the enhancement, explain why you expect it
198 to perform better than on the original file system implementation, and
199 demonstrate the performance improvement.
200
201 Note that write-behind makes your filesystem more fragile in the face
202 of crashes.  Therefore, you should implement some manner to
203 periodically write all cached blocks to disk.  If you have
204 @code{timer_sleep()} from the first project working, this is an
205 excellent application for it.
206
207 Likewise, read-ahead is only really useful when done asynchronously.
208 That is, if a process wants disk block 1 from the file, it needs to
209 block until disk block 1 is read in, but once that read is complete,
210 control should return to the process immediately while the read
211 request for disk block 2 is handled asynchronously.  In other words,
212 the process will block to wait for disk block 1, but should not block
213 waiting for disk block 2.
214
215 FIXME
216 When you're implementing this, please make sure you have a scheme for
217 making any read-ahead and write-behind threads halt when Pintos is
218 ``done'' (when the user program has completed, etc), so that Pintos
219 will halt normally and print its various statistics.
220
221 @node File System Design Document Requirements
222 @section Design Document Requirements
223
224 As always, submit a design document file summarizing your design.  Be
225 sure to cover the following points :
226
227 @itemize @bullet
228 @item
229 How did you structure your inodes? How many blocks did you access
230 directly, via single-indirection, and/or via double-indirection?  Why?
231
232 @item
233 How did you structure your buffer cache? How did you perform a lookup
234 in the cache? How did you choose elements to evict from the cache?
235
236 @item
237 How and when did you flush the cache?
238 @end itemize
239
240 @node File System FAQs
241 @section FAQ
242
243 @enumerate 1
244 @item
245 @b{What extra credit opportunities are available for this assignment?}
246
247 @itemize @bullet
248 @item
249 We'll give out extra credit to groups that implement Unix-style
250 support for @file{.} and @file{..} in relative paths in their projects.
251
252 @item
253 We'll give some extra credit if you submit with VM enabled.  If you do
254 this, make sure you show us that you can run multiple programs
255 concurrently.  A particularly good demonstration is running
256 @file{capitalize} (with a reduced words file that fits comfortably on
257 your disk, of course).  So submit a file system disk that contains a
258 VM-heavy program like @file{capitalize}, so we can try it out.  And also
259 include the results in your test case file.
260
261 We feel that you will be much more satisfied with your cs140 ``final
262 product'' if you can get your VM working with your file system.  It's
263 also a great stress test for your FS, but obviously you have to be
264 pretty confident with your VM if you're going to submit this extra
265 credit, since you'll still lose points for failing FS-related tests,
266 even if the problem is in your VM code.
267
268 @item
269 A point of extra credit can be assigned if a user can recursively
270 remove directories from the shell command prompt.  Note that the
271 typical semantic is to just fail if a directory is not empty.
272 @end itemize
273
274 Make sure that you discuss any extra credit in your @file{README}
275 file.  We're likely to miss it if it gets buried in your design
276 document.
277
278 @item
279 @b{What exec modes for running Pintos do I absolutely need to
280 support?}
281
282 FIXME FIXME
283 The most standard mode is to run your Pintos with all the command
284 flags on one command line, like this: @samp{pintos -f -cp shell
285 shell -ex "shell"}.  However, you also need to support these flags
286 individually---especially since that's how the grader tests your
287 program.  Thus, you should be able to run the above instead as:
288
289 FIXME
290 @example
291 pintos -f
292 pintos -cp shell shell
293 pintos -ex "shell"
294 @end example
295
296 Note that this also provides a way for you to validate that your disks
297 are really persistent.  This is a common problem with a write behind
298 cache: if you don't shut down properly it will leave the disk in an
299 inconsistent state.
300
301 @item
302 @b{Will you test our file system with a different @code{DISK_SECTOR_SIZE}?}
303
304 No, @code{DISK_SECTOR_SIZE} will not change.
305
306 @item
307 @b{Will the @code{struct filehdr} take up space on the disk too?}
308
309 Yes.  Anything stored in @code{struct filehdr} takes up space on disk,
310 so you must include this in your calculation of how many entires will
311 fit in a single disk sector.
312
313 @item
314 File Growth FAQs
315
316 @enumerate 1
317 @item
318 @b{What is the largest file size that we are supposed to support?}
319
320 The disk we create will be 8 MB or smaller.  However, individual files
321 will have to be smaller than the disk to accommodate the metadata.
322 You'll need to consider this when deciding your @code{struct filehdr}
323 (inode) organization.
324 @end enumerate
325
326 @item
327 Subdirectory FAQs
328
329 @enumerate 1
330 @item
331 @b{What's the answer to the question in the spec about why
332 @command{ls} and @command{mkdir} are user programs, while @command{cd}
333 is a shell command?}
334
335 Each process maintains its own current working directory, so it's much
336 easier to change the current working directory of the shell process if
337 @command{cd} is implemented as a shell command rather than as another
338 user process.  In fact, Unix-like systems don't provide any way for
339 one process to change another process's current working directory.
340
341 @item
342 @b{When the spec states that directories should be able to grow beyond
343 ten files, does this mean that there can still be a set maximum number
344 of files per directory that is greater than ten, or should directories
345 now support unlimited growth (bounded by the maximum supported file
346 size)?}
347
348 We're looking for directories that can support arbitrarily large
349 numbers of files.  Now that directories can grow, we want you to
350 remove the concept of a preset maximum file limit.
351
352 @item
353 @b{When should the @code{lsdir} system call return?}
354
355 The @code{lsdir} system call should not return until after the
356 directory has been printed.  Here's a code fragment, and the desired
357 output:
358
359 @example
360 printf ("Start of directory\n");
361 lsdir ();
362 printf ("End of directory\n");
363 @end example
364
365 This code should create the following output:
366
367 @example
368 Start of directory
369 ...  directory contents ...
370 End of directory
371 @end example
372
373 @item
374 @b{Do we have to implement both absolute and relative pathnames?}
375
376 Yes.  Implementing @file{.} and @file{..} is extra credit, though.
377
378 @item
379 @b{Should @code{remove()} also be able to remove directories?}
380
381 Yes.  The @code{remove} system call should handle removal of both
382 regular files and directories.  You may assume that directories can
383 only be deleted if they are empty, as in Unix.
384 @end enumerate
385
386 @item
387 Buffer Cache FAQs
388
389 @enumerate 1
390 @item
391 @b{We're limited to a 64-block cache, but can we also keep a copy of
392 each @code{struct filehdr} for an open file inside @code{struct file},
393 the way the stub code does?}
394
395 No, you shouldn't keep any disk sectors stored anywhere outside the
396 cache.  That means you'll have to change the way the file
397 implementation accesses its corresponding inode right now, since it
398 currently just creates a new @code{struct filehdr} in its constructor
399 and reads the corresponding sector in from disk when it's created.
400
401 There are two reasons for not storing inodes in @code{struct file}.
402 First, keeping extra copies of inodes would be cheating the 64-block
403 limitation that we place on your cache.  Second, if two processes have
404 the same file open, you will create a huge synchronization headache
405 for yourself if each @code{struct file} has its own copy of the inode.
406
407 Note that you can store pointers to inodes in @code{struct file} if
408 you want, and you can store some other small amount of information to
409 help you find the inode when you need it.
410
411 Similarly, if you want to store one block of data plus some small
412 amount of metadata for each of your 64 cache entries, that's fine.
413
414 @item
415 @b{But why can't we store copies of inodes in @code{struct file}? We
416 don't understand the answer to the previous question.}
417
418 The issue regarding storing @code{struct filehdr}s has to do with
419 implementation of the buffer cache.  Basically, you can't store a
420 @code{struct filehdr *} in @code{struct filehdr}.  Each time you need
421 to read a @code{struct filehdr}, you'll have to get it either from the
422 buffer cache or from disk.
423
424 If you look at @code{file_read_at()}, it uses @code{hdr} directly
425 without having first read in that sector from wherever it was in the
426 storage hierarchy.  You are no longer allowed to do this.  You will
427 need to change @code{file_read_at} (and similar functions) so that it
428 reads @code{hdr} from the storage hierarchy before using it.
429 @end enumerate
430 @end enumerate