From 7241838b4cecefb32bad4698e748fc31d008d94d Mon Sep 17 00:00:00 2001 From: Frans Kaashoek Date: Tue, 20 Aug 2019 20:23:18 -0400 Subject: Move labs into 6.828 repo. The lab text isn't dependent on specific xv6 code. Lab submission instructions etc. are likely going to be more MIT 6.828 specific. --- labs/fs.html | 360 ----------------------------------------------------------- 1 file changed, 360 deletions(-) delete mode 100644 labs/fs.html (limited to 'labs/fs.html') diff --git a/labs/fs.html b/labs/fs.html deleted file mode 100644 index a21e61f..0000000 --- a/labs/fs.html +++ /dev/null @@ -1,360 +0,0 @@ - - -Lab: file system - - - - -

Lab: file system

- -

In this lab you will add large files and mmap to the xv6 file system. - -

Large files

- -

In this assignment you'll increase the maximum size of an xv6 -file. Currently xv6 files are limited to 268 blocks, or 268*BSIZE -bytes (BSIZE is 1024 in xv6). This limit comes from the fact that an -xv6 inode contains 12 "direct" block numbers and one "singly-indirect" -block number, which refers to a block that holds up to 256 more block -numbers, for a total of 12+256=268. You'll change the xv6 file system -code to support a "doubly-indirect" block in each inode, containing -256 addresses of singly-indirect blocks, each of which can contain up -to 256 addresses of data blocks. The result will be that a file will -be able to consist of up to 256*256+256+11 blocks (11 instead of 12, -because we will sacrifice one of the direct block numbers for the -double-indirect block). - -

Preliminaries

- -

Modify your Makefile's CPUS definition so that it reads: -

-CPUS := 1
-

- -XXX doesn't seem to speedup things -

Add -

-QEMUEXTRA = -snapshot
-

-right before -QEMUOPTS -

-The above two steps speed up qemu tremendously when xv6 -creates large files. - -

mkfs initializes the file system to have fewer -than 1000 free data blocks, too few to show off the changes -you'll make. Modify param.h to -set FSSIZE to: -

-    #define FSSIZE       20000  // size of file system in blocks
-

- -

Download big.c into your xv6 directory, -add it to the UPROGS list, start up xv6, and run big. -It creates as big a file as xv6 will let -it, and reports the resulting size. It should say 140 sectors. - -

What to Look At

- -The format of an on-disk inode is defined by struct dinode -in fs.h. You're particularly interested in NDIRECT, -NINDIRECT, MAXFILE, and the addrs[] element -of struct dinode. Look Figure 7.3 in the xv6 text for a -diagram of the standard xv6 inode. - -

-The code that finds a file's data on disk is in bmap() -in fs.c. Have a look at it and make sure you understand -what it's doing. bmap() is called both when reading and -writing a file. When writing, bmap() allocates new -blocks as needed to hold file content, as well as allocating -an indirect block if needed to hold block addresses. - -

-bmap() deals with two kinds of block numbers. The bn -argument is a "logical block" -- a block number relative to the start -of the file. The block numbers in ip->addrs[], and the -argument to bread(), are disk block numbers. -You can view bmap() as mapping a file's logical -block numbers into disk block numbers. - -

Your Job

- -Modify bmap() so that it implements a doubly-indirect -block, in addition to direct blocks and a singly-indirect block. -You'll have to have only 11 direct blocks, rather than 12, -to make room for your new doubly-indirect block; you're -not allowed to change the size of an on-disk inode. -The first 11 elements of ip->addrs[] should be -direct blocks; the 12th should be a singly-indirect block -(just like the current one); the 13th should be your new -doubly-indirect block. - -

-You don't have to modify xv6 to handle deletion of files with -doubly-indirect blocks. - -

-If all goes well, big will now report that it -can write sectors. It will take big minutes -to finish. - -XXX this runs for a while! - -

Hints

- -

-Make sure you understand bmap(). Write out a diagram of the -relationships between ip->addrs[], the indirect block, the -doubly-indirect block and the singly-indirect blocks it points to, and -data blocks. Make sure you understand why adding a doubly-indirect -block increases the maximum file size by 256*256 blocks (really -1), -since you have to decrease the number of direct blocks by one). - -

-Think about how you'll index the doubly-indirect block, and -the indirect blocks it points to, with the logical block -number. - -

If you change the definition of NDIRECT, you'll -probably have to change the size of addrs[] -in struct inode in file.h. Make sure that -struct inode and struct dinode have the -same number of elements in their addrs[] arrays. - -

If you change the definition of NDIRECT, make sure to create a -new fs.img, since mkfs uses NDIRECT too to build the -initial file systems. If you delete fs.img, make on Unix (not -xv6) will build a new one for you. - -

If your file system gets into a bad state, perhaps by crashing, -delete fs.img (do this from Unix, not xv6). make will build a -new clean file system image for you. - -

Don't forget to brelse() each block that you -bread(). - -

You should allocate indirect blocks and doubly-indirect - blocks only as needed, like the original bmap(). - -

Optional challenge: support triple-indirect blocks. - -

Writing with a Log

- -Insert a print statement in bwrite (in bio.c) so that you get a -print every time a block is written to disk: - -

-  printf("bwrite block %d\n", b->blockno);
-

- -Build and boot a new kernel and run this: -

-  $ rm README
-

- -

You should see a sequence of bwrite prints after the rm.

- -

Annotate the bwrite lines with the kind of information that is -being written to the disk (e.g., "README's inode", "allocation -bitmap"). If the log is being written, note both that the log is being -written and also what kind of information is being written to the log. -
Mark with an arrow the first point at which, if a -crash occured, README would be missing after a reboot -(after the call to recover_from_log()). -

- - -

Crash safety

- -

This assignment explores the xv6 log in two parts. -First, you'll artificially create a crash which illustrates -why logging is needed. Second, you'll remove one -inefficiency in the xv6 logging system. - -

-Submit your solution before the beginning of the next lecture -to the submission -web site. - -

Creating a Problem

- -

-The point of the xv6 log is to cause all the disk updates of a -filesystem operation to be atomic with respect to crashes. -For example, file creation involves both adding a new entry -to a directory and marking the new file's inode as in-use. -A crash that happened after one but before the other would -leave the file system in an incorrect state after a reboot, -if there were no log. - -

-The following steps will break the logging code in a way that -leaves a file partially created. - -

-First, replace commit() in log.c with -this code: -

-#include "kernel/proc.h"
-void
-commit(void)
-{
-  int pid = myproc()->pid;
-  if (log.lh.n > 0) {
-    write_log();
-    write_head();
-    if(pid > 1)            // AAA
-      log.lh.block[0] = 0; // BBB
-    install_trans();
-    if(pid > 1)            // AAA
-      panic("commit mimicking crash"); // CCC
-    log.lh.n = 0; 
-    write_head();
-  }
-}
-

- -

-The BBB line causes the first block in the log to be written to -block zero, rather than wherever it should be written. During file -creation, the first block in the log is the new file's inode updated -to have non-zero type. -Line BBB causes the block -with the updated inode to be written to block 0 (whence -it will never be read), leaving the on-disk inode still marked -unallocated. The CCC line forces a crash. -The AAA lines suppress this buggy behavior for init, -which creates files before the shell starts. - -

-Second, replace recover_from_log() in log.c -with this code: -

-static void
-recover_from_log(void)
-{
-  read_head();      
-  printf("recovery: n=%d but ignoring\n", log.lh.n);
-  // install_trans();
-  log.lh.n = 0;
-  // write_head();
-}
-

- -

-This modification suppresses log recovery (which would repair -the damage caused by your change to commit()). - -

-Finally, remove the -snapshot option from the definition -of QEMUEXTRA in your Makefile so that the disk image will see the -changes. - -

-Now remove fs.img and run xv6: -

-  % rm fs.img ; make qemu
-

-Tell the xv6 shell to create a file: -

-  $ echo hi > a
-

- -

-You should see the panic from commit(). So far -it is as if a crash occurred in a non-logging system in the middle -of creating a file. - -

-Now re-start xv6, keeping the same fs.img: -

-  % make qemu
-

- -

-And look at file a: -

-  $ cat a
-

- -

- You should see panic: ilock: no type. Make sure you understand what happened. -Which of the file creation's modifications were written to the disk -before the crash, and which were not? - -

Solving the Problem

- -Now fix recover_from_log(): -

-static void
-recover_from_log(void)
-{
-  read_head();
-  cprintf("recovery: n=%d\n", log.lh.n);
-  install_trans();
-  log.lh.n = 0;
-  write_head();
-}
-

- -

-Run xv6 (keeping the same fs.img) and read a again: -

-  $ cat a
-

- -

-This time there should be no crash. Make sure you understand why -the file system now works. - -

-Why was the file empty, even though you created -it with echo hi > a? - -

-Now remove your modifications to commit() -(the if's and the AAA and BBB lines), so that logging works again, -and remove fs.img. - -

Streamlining Commit

- -

-Suppose the file system code wants to update an inode in block 33. -The file system code will call bp=bread(block 33) and update the -buffer data. write_log() in commit() -will copy the data to a block in the log on disk, for example block 3. -A bit later in commit, install_trans() reads -block 3 from the log (containing block 33), copies its contents into the in-memory -buffer for block 33, and then writes that buffer to block 33 on the disk. - -

-However, in install_trans(), it turns out that the modified -block 33 is guaranteed to be still in the buffer cache, where the -file system code left it. Make sure you understand why it would be a -mistake for the buffer cache to evict block 33 from the buffer cache -before the commit. - -

-Since the modified block 33 is guaranteed to already be in the buffer -cache, there's no need for install_trans() to read block -33 from the log. Your job: modify log.c so that, when -install_trans() is called from commit(), -install_trans() does not perform the needless read from the log. - -

To test your changes, create a file in xv6, restart, and make sure -the file is still there. - -XXX Does this speedup bigfile? - -XXX Maybe support lseek and modify shell to append to a file? - - - - -- cgit v1.2.3