Lab fs: Device files & symbolic links

Your task is to extend the xv6 filesystem with support for special device files and for symbolic links.

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

$ git fetch origin
$ git checkout -b fs origin/xv6-21au
$ 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.

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.

This completes the lab. In the lab directory, commit your changes, type make tarball, and submit the tarball through Canvas.