Lab FS: Device Files & Symbolic Links

Your task is to extend the xv6 filesystem with support for special device files and for symbolic links. Additionally, there is extra credit available for extending it to support larger files via doubly indirect pointers.

To start the lab, update your repository and create a new branch for your solution:

$ git fetch origin
$ git checkout -b fs origin/main
$ make clean

Device Files

In this part of the lab you will extend xv6 by adding support for four different kinds of device files. These files appear as regular files in the file system hierarchy but are implemented by functions in the kernel instead of being backed by a physical disk.

• /dev/null: The null device is a special device that discards all data written to it. Reads from this device always return EOF.

$ echo hello > /dev/null
$ cat /dev/null
$

• /dev/zero: Like the null device, the zero device discards all data written to it. Reading from this device, however, produces an infinite stream of NUL bytes.

$ echo hello > /dev/zero
$ cat /dev/zero
[Never terminates]

• /dev/random: The random device produces an infinite stream of random bytes when read.

$ cat /dev/random
[Infinite stream of random bytes]

• /dev/uptime: This device file contains the number of clock ticks since boot, similar to the uptime system call.

$ cat /dev/uptime
19
$ cat /dev/uptime
45
$

When you have implemented these files, you can run the tests in xv6 with specialtest. Your solution must modify init to create the speical files using mknod; the test assumes they already exist. Your solution is complete when the tests produce the following output (and usertests still succeeds):

$ specialtest

START: test /dev/null
reading from /dev/null..
writing to /dev/null..
reading from /dev/null again..
SUCCESS: test /dev/null

START: test /dev/zero
writing to /dev/zero..
reading from /dev/zero..
SUCCESS: test /dev/zero

START: test /dev/uptime
Reading from /dev/uptime..
Reading from /dev/uptime again..
SUCCESS: test /dev/uptime

START: test /dev/random
Opening /dev/random..
reading from /dev/random four times..
SUCCESS: test /dev/random
$

Here’s one reasonable plan of attack.

• First, add new device types to kernel/file.h for each type of special device. You may choose either to use a different major device number for each type, or use one major number for all special files and differentiate among them using the minor number.

• Next, modify user/init.c to create the special device files using the mknod system call with the major and minor numbers you chose in the first step.

• Look at how the consoleread and consolewrite functions are implemented in kernel/console.c. You will need to implement similar functions for the new special devices, and initialize them in the devsw array.

• For /dev/uptime, you may assume that the process reads the entire value in one call to read. You must, however, implement a mechanism to return EOF on further reads to that file descriptor; otherwise the process (e.g., cat) will not know when to stop reading. One possibility is to use the off field in struct file, which is otherwise unused by device files.

• For your random number generator for /dev/random, a simple option is to use a xorshift generator, which can be implemented in a few lines of C. You may also implement a more secure one, such as Fortuna; however, note that the security is also dependent on your entropy source, which you won’t need to worry about for this lab.

Symbolic Links

The second part of this lab is to add support for symbolic links to xv6. Symbolic links (or soft links) refer to a linked file by pathname; when a symbolic link is opened, the kernel follows the link to the referred file. Symbolic links resemble hard links, but hard links are restricted to pointing to file on the same disk, while symbolic links can cross disk devices. Although xv6 doesn’t support multiple devices, implementing this system call is a good exercise to understand how pathname lookup works.

For this part of the lab, you will implement a the int symlink(const char *target, const char *linkpath) system call, which creates a new symbolic link at linkpath that refers to file named by target. See the POSIX specification on symlink for further information.

To test, add symlinktest to the Makefile and run it. Your solution is complete when the tests produce the following output (and usertests still succeeds):

$ symlinktest

START: test symlinks
Creating a
Linking b -> a
Writing to a
Reading from b
Removing a
Linking a -> b
Attempting to open b (cycle)
Symlinking c to nonexistent file
Creating symlink chain 1->2->3->4
SUCCESS: test symlinks
$

Here’s one reasonable plan of attack.

• First, create a new system call number for symlink, add an entry to user/usys.pl, user/user.h, and implement an empty sys_symlink. This will let you compile user/symlinktest.c once you add it to the Makefile.

• Add a new file type (T_SYMLINK) to kernel/stat.h to represent a symbolic link.

• Implement the symlink(target, linkpath) system call to create a new symbolic link at linkpath that refers to target. Note that target does not need to exist for the system call to succeed. You will need to choose somewhere to store the target path of a symbolic link, for example, in the inode’s data blocks. symlink should return an integer representing success (0) or failure (-1) similar to link and unlink. For crash safety, you will need to wrap your updates to the file system between begin_op and end_op calls (e.g., see sys_link).

• Modify the open system call to handle the case where the path refers to a symbolic link. If the file does not exist, open must fail.

• If the linked file is also a symbolic link, you must recursively follow it until a non-link file is reached. If the links form a cycle, you must return an error code. You may approximate this by returning an error code if the depth of links reaches some threshold (e.g., 10).

• Other system calls (e.g., link and unlink) must not follow symbolic links; these system calls operate on the symbolic link itself.

• You do not have to handle symbolic links to directories for this lab.

Larger Files (Extra Credit)

The final (and optional) part of this lab is to support larger files for xv6. By default, xv6 only supports files of up to 268 blocks (12 Direct, 256 Indirect). Your task is to increase the size of files xv6 supports by introducing doubly indirect pointers to inodes. This part is worth 15 points.

Without writing any code, if you add largefiletest to your Makefile then you should see the following output:

$ largefiletest
write failed at block number 268 on attempt 0

• Before you do anything else, you must first increase the size of the disk by editing FSSIZE in kernel/param.h to change it to 100000 (up from 2000).

• You need to modify the struct dinode and struct inode definitions to support the additional doubly indirect pointer. Note that there are alignment restrictions, so you can reduce the number of direct pointers NDIRECT to be 11 instead of 12. You can also update the other relevant macros at this time (e.g., MAXFILE).

• You need to update the implementation of bmap and itrunc in kernel/fs.c to take into consideration the new doubly indirect pointer. You can heavily rely on the existing implementation for the singly indirect pointer.

• If you see a panic from VirtIO, you are likely performing an invalid access which you will need to debug (e.g., out of bounds block address).

• Note that usertests also exercises large files in certain ways. You are finished with both largefiletest and usertest succeed.

Submission

You may run python3 grade_lab_fs.py to ensure that your code passes all of the tests.

When you are ready to submit your work to Gradescope to be automatically graded, you can run make gradescope which generates a submission.zip file that can be uploaded to Gradescope. This file should only contain the files that were changed as a result of completing the lab assignment.