238P Operating Systems

Homework 5: Infinite files for xv6

In this assignment you'll increase the maximum size of an xv6 file. Currently xv6 files are limited to 140 sectors, or 71,680 bytes. 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 128 more block numbers, for a total of 12+128=140.

In this homework you will change the xv6 file system code to support a "linked-list" file addressing for files of infinite length (of course, in practice the file size will be limited by the size of your file system).

Preliminaries

Since mkfs initializes the file system to have fewer than 1000 free data blocks, too few to show off the changes you'll make. Modify FSSIZE inside param.h to read 128*128*16 blocks (or 128MB)

Download big.c into your xv6 directory, add them to the UPROGS list (same as you did for HW4), start up xv6, and run big. big writes 4 files: 1MB, 2MB, 4MB, and 8MB, and then reads them --- this will help you to test your solution. Big writes 64KB at a time, which is significantly faster (and yet it takes quite a bit of time). Feel free to edit big.c to adjust write size, and enable additional debug info.

Your Job

struct inode _________________ | | | type | ----------------- | | | major | ----------------- | .... | ----------------- | | | size | ----------------- | addrs[0] | -> ----------------- ----------------- | tbl1[0] | -> Physical ----------------- | ..... | -> Physical ----------------- | ..... | -> Physical ----------------- | ..... | ----------------- | tbl1[127] | -- ----------------- | ----------------------/ / \-> ----------------- | tbl1[0] | -> Physical ----------------- | ..... | -> Physical ----------------- | ..... | -> Physical ----------------- | ..... | ----------------- | tbl1[127] | -- ----------------- | ----------------------/ / .... more list elements \-> ----------------- | tbl1[0] | -> Physical ----------------- | ..... | -> Physical ----------------- | ..... | -> Physical ----------------- | ..... | ----------------- | tbl1[127] | -> 0 (NULL) // last element has "next" pointer as null -----------------

After you have modified bmap() you need to go into mkfs.c and modify iappend(). This c file gets run during the make process and builds the file system image which gets run with QEMU. The code and logic will be extremely similar to the code you had written in bmap().

If you have a hard time understanding what iappend() is doing, here is the annotated code

void iappend(uint inum, void *xp, int n) { char *p = (char*)xp; uint fbn, off, n1; struct dinode din; char buf[BSIZE]; uint indirect[NINDIRECT]; uint x; // Read inode number inum into &din rinode(inum, &din); // inode might already have some data, offset is the last byte it has off = xint(din.size); // While we have bytes to write into the inode, loop while(n > 0){ // Get the block number of the last block from the offset fbn = off / BSIZE; assert(fbn < MAXFILE); // if block number is still inside direct blocks ... if(fbn < NDIRECT){ // is block allocated? if(xint(din.addrs[fbn]) == 0){ // no allocate it by incrementing freeblock pointer din.addrs[fbn] = xint(freeblock++); } // allocated ... get the block x = xint(din.addrs[fbn]); } else { // oh no... it's an indirect block if(xint(din.addrs[NDIRECT]) == 0){ // was first level of indirection allocated? din.addrs[NDIRECT] = xint(freeblock++); } // read the sector that contains the 1 level indirect table // into indirect rsect(xint(din.addrs[NDIRECT]), (char*)indirect); // check if the entry already allocated in the table if(indirect[fbn - NDIRECT] == 0){ // not allocated, allocate a new block and update // the first level indirect table indirect[fbn - NDIRECT] = xint(freeblock++); // write first level table back to disk wsect(xint(din.addrs[NDIRECT]), (char*)indirect); } // get the sector number x = xint(indirect[fbn-NDIRECT]); } n1 = min(n, (fbn + 1) * BSIZE - off); // read sector rsect(x, buf); //copy data into buf bcopy(p, buf + off - (fbn * BSIZE), n1); // write back the sector wsect(x, buf); n -= n1; off += n1; p += n1; } din.size = xint(off); // write back the inode winode(inum, &din); }

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

What to Look At

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.

Hints

Make sure you understand bmap(). Write out a diagram of the relationships between ip->addrs[], the direct blocks, the list blocks. Make sure you understand why adding linked list addressing block allows you to have files of infinite size.

If your file system gets into a bad state, perhaps by crashing, you may need to delete fs.img (do this from Unix, not xv6).

Extra Credit 1 (10%)
Writing a large file to disk in xv6 is incredibly slow. It gets slower the fuller the disk gets(hint). There are two ways to speed up writing a file to disk. In extra_credit.txt explain why when the disk gets fuller writing gets slower-- Explain how you can mitigate this problem. Second, explain the other way to speed up writes and why that works (hint log.c).

Extra Credit 2 (20%)
Implement these changes, in xv6, resolving all panics and failed assertions that arise. Do a crappy timing experiment using a stop watch. Explain how much speed up occured.


Home
Homework 5: Infinite files for xv6 In this assignment you'll increase the maximum size of an xv6 file. Currently xv6 files are limited to 140 sectors, or 71,680 bytes. 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 128 more block numbers, for a total of 12+128=140. In this homework you will change the xv6 file system code to support a "linked-list" file addressing for files of infinite length (of course, in practice the file size will be limited by the size of your file system). Preliminaries Modify your Makefile's `CPUS` definition so that it reads: CPUS := 1 This speeds up qemu when xv6 creates large files. Since `mkfs` initializes the file system to have fewer than 1000 free data blocks, too few to show off the changes you'll make. Modify FSSIZE inside `param.h` to read 12812816 blocks (or 128MB) #define FSSIZE 12812816 Finally, to make your code compile in `fs.h` change MAXFILE to #define MAXFILE 1282048 While we will support files of infinite length, in practice xv6 too much depends on the MAXFILE constant. So to make the build system happy, lets change it to some large value. Download big.c into your xv6 directory, add them to the UPROGS list (same as you did for HW4), start up xv6, and run `big`. `big` writes 4 files: 1MB, 2MB, 4MB, and 8MB, and then reads them --- this will help you to test your solution. Big writes 64KB at a time, which is significantly faster (and yet it takes quite a bit of time). Feel free to edit `big.c` to adjust write size, and enable additional debug info. Your Job Modify bmap() so that it implements a liked-list system. The one and only element of ip->addrs[] (ip->addrs[0]) should point to the head of the list (an indirect block that contains 127 pointers to the data blocks, and one (the last 4 bytes of the 512 block) pointer pointing to the next indirect block on the list as in the figure blow). The last element of the list should have the "next" pointer set to 0 (we know that 0 block contains the boot loader, so it's ok, to use it as a NULL). An ascii examble illustrates the layout of the linked list: struct inode _________________ \| \| \| type \| ----------------- \| \| \| major \| ----------------- \| .... \| ----------------- \| \| \| size \| ----------------- \| addrs[0] \| -> ----------------- ----------------- \| tbl1[0] \| -> Physical ----------------- \| ..... \| -> Physical ----------------- \| ..... \| -> Physical ----------------- \| ..... \| ----------------- \| tbl1[127] \| -- ----------------- \| ----------------------/ / \-> ----------------- \| tbl1[0] \| -> Physical ----------------- \| ..... \| -> Physical ----------------- \| ..... \| -> Physical ----------------- \| ..... \| ----------------- \| tbl1[127] \| -- ----------------- \| ----------------------/ / .... more list elements \-> ----------------- \| tbl1[0] \| -> Physical ----------------- \| ..... \| -> Physical ----------------- \| ..... \| -> Physical ----------------- \| ..... \| ----------------- \| tbl1[127] \| -> 0 (NULL) // last element has "next" pointer as null ----------------- After you have modified `bmap()` you need to go into `mkfs.c` and modify `iappend()`. This c file gets run during the make process and builds the file system image which gets run with QEMU. The code and logic will be extremely similar to the code you had written in bmap(). If you have a hard time understanding what iappend() is doing, here is the annotated code void iappend(uint inum, void xp, int n) { char p = (char)xp; uint fbn, off, n1; struct dinode din; char buf[BSIZE]; uint indirect[NINDIRECT]; uint x; // Read inode number inum into &din rinode(inum, &din); // inode might already have some data, offset is the last byte it has off = xint(din.size); // While we have bytes to write into the inode, loop while(n > 0){ // Get the block number of the last block from the offset fbn = off / BSIZE; assert(fbn < MAXFILE); // if block number is still inside direct blocks ... if(fbn < NDIRECT){ // is block allocated? if(xint(din.addrs[fbn]) == 0){ // no allocate it by incrementing freeblock pointer din.addrs[fbn] = xint(freeblock++); } // allocated ... get the block x = xint(din.addrs[fbn]); } else { // oh no... it's an indirect block if(xint(din.addrs[NDIRECT]) == 0){ // was first level of indirection allocated? din.addrs[NDIRECT] = xint(freeblock++); } // read the sector that contains the 1 level indirect table // into indirect rsect(xint(din.addrs[NDIRECT]), (char)indirect); // check if the entry already allocated in the table if(indirect[fbn - NDIRECT] == 0){ // not allocated, allocate a new block and update // the first level indirect table indirect[fbn - NDIRECT] = xint(freeblock++); // write first level table back to disk wsect(xint(din.addrs[NDIRECT]), (char)indirect); } // get the sector number x = xint(indirect[fbn-NDIRECT]); } n1 = min(n, (fbn + 1) * BSIZE - off); // read sector rsect(x, buf); //copy data into buf bcopy(p, buf + off - (fbn * BSIZE), n1); // write back the sector wsect(x, buf); n -= n1; off += n1; p += n1; } din.size = xint(off); // write back the inode winode(inum, &din); } You don't have to modify xv6 to handle deletion of files with linked-list blocks. 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`, and the `addrs[]` element of `struct dinode`. Look here 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. Hints Make sure you understand `bmap()`. Write out a diagram of the relationships between `ip->addrs[]`, the direct blocks, the list blocks. Make sure you understand why adding linked list addressing block allows you to have files of infinite size. If your file system gets into a bad state, perhaps by crashing, you may need to delete `fs.img` (do this from Unix, not xv6). Don't forget to `brelse()` each block that you `bread()`. You should allocate linked list blocks as needed, like the original `bmap()`. Our solution was done in around 50 lines of code. Extra Credit 1 (10%) Writing a large file to disk in xv6 is incredibly slow. It gets slower the fuller the disk gets(hint). There are two ways to speed up writing a file to disk. In extra_credit.txt explain why when the disk gets fuller writing gets slower-- Explain how you can mitigate this problem. Second, explain the other way to speed up writes and why that works (hint log.c). Extra Credit 2 (20%) Implement these changes, in xv6, resolving all panics and failed assertions that arise. Do a crappy timing experiment using a stop watch. Explain how much speed up occured.

Updated: June, 2019