From b70cd9ebd7f48762739f78dfacfebf84f0a5f66a Mon Sep 17 00:00:00 2001 From: Frans Kaashoek Date: Tue, 30 Jul 2019 14:33:09 -0400 Subject: Import big file assignment. --- labs/fs.html | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 145 insertions(+) create mode 100644 labs/fs.html (limited to 'labs/fs.html') diff --git a/labs/fs.html b/labs/fs.html new file mode 100644 index 0000000..c201d45 --- /dev/null +++ b/labs/fs.html @@ -0,0 +1,145 @@ + + +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(). + +

Memory-mapped files

+ + + + -- cgit v1.2.3