Operating Systems #10 — Extending the xv6 File System

The last project was the file system. Three pieces: multi indirect to raise the file size limit, symbolic links, and buffered I/O to change the commit policy.

Design

Multi indirect

Add NDINDIRECT and NTINDIRECT macros for double and triple indirect. bmap reads the addr array out of the inode, so it needs changing; itrunc removes those addresses, so it needs the same treatment.

Symbolic links

Implement a symlink system call. The existing link is a hard link; symlink creates a new inode and stores the original file's path inside it.

Buffered I/O

Currently group commit commits once per transaction. Change it to commit when the buffer fills.

Implementation

1. Multi indirect

Macros. NDINDIRECT is the square of the number of addresses in an indirect block; NTINDIRECT is the cube.

NDINDIRECT, NTINDIRECT, and the enlarged MAXFILE.

dinode and inode. I added two more addr entries (double indirect and triple indirect). That makes the block size no longer divide evenly by the dinode size, which trips an assert during mkfs. You can either reduce the number of direct addresses or add padding; I chose padding. I updated the addrs count in inode and added padding there too.

dinode — two more addr entries plus padding.

Without matching padding, mkfs trips this assert.

inode changed the same way.

bmap. I added the double and triple indirect cases after the existing direct and indirect ones. Each step breads the block for the block number read at the previous step and does the appropriate arithmetic with bn to descend to the last level. At the last level the block holds addresses, so it reads and returns the one it needs.

bmap — the existing direct and indirect cases.

bmap — the double and triple indirect cases appended after them.

itrunc. Done the same way as bmap.

itrunc — descending in the same order as bmap to free the blocks.

iappend. Double and triple indirect added, as above.

The double and triple indirect cases added to iappend.

balloc (mkfs.c). I raised the nbitmap bound so it can hold the required number of bitmaps, set per block.

balloc in mkfs.c — raising the initial bitmap count.

2. Symbolic links

ln.c. Added -h (hard link) and -s (symbolic link) options.

ln.c — the -h and -s options.

sys_symlink. Adds an inode at the path given as new and uses writei to store old's path into new. On a later open, readi reads it back and control moves to the old path.

sys_symlink — writing old's path into new's inode.

sys_open. I added an O_LS open option, to keep ls from showing old's information next to the new file. Opening a symlink file walks a loop to find the original file's path and reads the data there.

sys_open — the O_LS option and the loop that follows the original path.

3. Buffered I/O

The sync() system call. If log.lh.n is 0 or more it calls commit() and returns log.lh.n; below 0 it returns -1.

The sync() system call.

end_op. I changed the commit condition. The log.outstanding condition exists for transactions, so I left it, and added log.lh.n + MAXOPBLOCKS > LOGSIZE — checking whether the next operation using the maximum number of blocks would exceed LOGSIZE, which means the log (the buffer) is running out. And I put sync() where the commit used to be.

end_op — the condition changed to check whether the buffer is running out.

Results

Multi indirect

A 5MB.txt built in through iappend was recognized as 5MB, each line filled with 1024 ones. It took about 15 minutes.

ls reporting 5MB.txt at 5,242,885 bytes.

Through mkfile, an 8MB file took about 10 minutes and a 16MB file about 18.

The 8MB and 16MB files produced by mkfile.

Symlinks

ln -s README hi creates a symlink to README. ls shows hi's own information next to it rather than README's, and cat hi prints README's contents.

ls shows hi's own information while cat hi prints README.

Deleting hi leaves README intact, and trying to open hi afterwards reports that the original file is missing.

README survives the deletion of hi.

Buffered I/O

I reused the mkfile test above and compared only the timings. The 8MB file took under a minute and the 16MB file four minutes — against 10 and 18 minutes before. That's what you get purely from batching writes until the buffer fills instead of committing to disk once per transaction.

Trouble shooting

iappend and indirect. Reading a newly created file was fine well past 70KB, but reading a file added built-in through iappend panicked at 70KB. iappend was reading from indirect and writing back into indirect; adding indirect2 and indirect3 to read through fixed it.

Not enough bitmap. Adding sufficiently large files through iappend wouldn't compile. It was a shortage of bitmap; changing balloc in mkfs.c as described above to raise the initial bitmap count fixed it.

ls showing the original's information. The original file's stat appeared next to the symlink file in ls. I gave open a new option so that reads from ls don't follow through to the original file.

Something I learned here: rm doesn't go through open. Since I made open read the link's original file, it seems that leaving rm alone still means deleting a link file doesn't delete the original.

Modifying log_write. I started by modifying log_write, and it stalled without syncing. I kept log_write's existing structure and moved the sync into end_op.

Closing the series

A semester split into eleven posts. Five lectures where you learn a name, labs where you find that name in the xv6 source, and three projects where you change it yourself.

Looking back, the three projects each took one subsystem: the scheduler, processes and threads, and the file system. I edited scheduler() in #7, added fields to struct proc in #9, and added addr entries to inode this time. What actually stayed with me from this course is having felt, by hand, what adding one more field to a data structure you'd only ever seen as a textbook diagram sets off — tripping an assert in mkfs, breaking copyuvm, panicking the kernel.