Lab util: Unix utilities

This lab makes you familiar with xv6 and its system calls.

Boot xv6

Install QEMU and gcc for RISC-V following the directions on the tools page.

Fetch the xv6 source for the lab and check out a new branch for your solution to this lab:

$ git clone https://gitlab.cs.washington.edu/cse451/xv6-21au.git
Cloning into 'xv6-21au'...
...
$ cd xv6-21au
$ git checkout -b util origin/xv6-21au

The xv6-21au repository differs slightly from the book’s xv6-riscv in order to make the labs easier.

The files you will need for this and subsequent lab assignments in this course are distributed using the Git version control system. Above you created a new branch (“util”) for your solutions for the utilities lab. To learn more about Git, take a look at the Git user’s manual, or, you may find this CS-oriented overview of Git useful. Git allows you to keep track of the changes you make to the code. For example, if you are finished with one of the exercises, and want to checkpoint your progress, you can commit your changes by running:

$ git commit -am 'my solution for util lab exercise 1'
Created commit 60d2135: my solution for util lab exercise 1
 1 files changed, 1 insertions(+), 0 deletions(-)
$

You can keep track of your changes by using the git diff command. For example, git diff will display the changes to your code since your last commit, and git diff origin/xv6-21au will display the changes relative to the initial xv6-21au code. Here, origin/xv6-21au is the name of the git branch with the initial code you downloaded for the class.

Build xv6:

$ make
riscv64-unknown-elf-gcc    -c -o kernel/entry.o kernel/entry.S
...
$ make qemu
gcc -Werror -Wall -I. -o mkfs/mkfs mkfs/mkfs.c
...
xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$

If you type ls at the prompt, you should see output similar to the following:

$ ls
.              1 1 1024
..             1 1 1024
README         2 2 2226
xargstest.sh   2 3 93
lazytests      2 4 27672
cat            2 5 23496
echo           2 6 22352
forktest       2 7 13104
grep           2 8 26664
init           2 9 23160
kill           2 10 22280
ln             2 11 22152
ls             2 12 25704
mkdir          2 13 22416
rm             2 14 22408
sh             2 15 40416
stressfs       2 16 23376
usertests      2 17 125048
wc             2 18 24496
zombie         2 19 21648
cowtest        2 20 29352
uthread        2 21 27360
call           2 22 22184
kalloctest     2 23 27264
bcachetest     2 24 29736
alloctest      2 25 25824
specialtest    2 26 31944
console        3 27 0

These are the programs/files that mkfs includes in the initial file system. You just ran one of them: ls.

Quit QEMU

To quit QEMU, type Ctrl-a x, which means:

first press both Ctrl and a,
then release the keys, and
afterwards press x.

Git repositories

You may create a private fork of the xv6 repository for collaboration or backup (e.g., using the CSE GitLab). You can add this new repository as a git remote to which you can push/pull your commits. For example, to back up branch to a remote named “mybackup” for the repository at url, you can run:

$ git remote add mybackup <url>
$ git push mybackup <branch>

Keep repositories private

Do not host your lab code on publicly accessible web sites (e.g., GitHub) or file spaces (e.g., CSE GitLab’s non-private projects).

Grading and hand-in procedure

You can run make grade to test your solutions with the grading program. The TAs will use the same grading program to assign your lab submission a grade.

To turn in your assignments, use make tarball to make a tar file, and upload the file via Canvas.

If you have either uncomitted changes or untracked files, you will see output similar to the following:

 M hello.c
?? bar.c
?? foo.pyc
Untracked files will not be handed in.  Continue? [y/N]

Inspect the above lines and make sure all files that your lab solution needs are tracked (i.e., not listed in a line that begins with ??).

You can cause Git to track a new file that you create using git add filename.

sleep

Exercise

Implement the Unix program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.

Some hints:

Look at some of the other programs in user/ ((e.g., user/echo.c, user/grep.c, and user/rm.c)) to see how you can obtain the command-line arguments passed to a program.
If the user forgets to pass an argument, sleep should print an error message.
The command-line argument is passed as a string; you can convert it to an integer using atoi (see user/ulib.c).
Use the system call sleep.
See kernel/sysproc.c for the xv6 kernel code that implements the sleep system call (look for sys_sleep), user/user.h for the C definition of sleep callable from a user program, and user/usys.S for the assembler code that jumps from user code into the kernel for sleep.
Make sure main calls exit() in order to exit your program.
Add your sleep program to UPROGS in Makefile; once you’ve done that, make qemu will compile your program and you’ll be able to run it from the xv6 shell.

Run the program from the xv6 shell:

$ make qemu
...
init: starting sh
$ sleep 10
(nothing happens for a little while)
$

Your solution is correct if your program pauses when run as shown above. Run make grade to see if you indeed pass the sleep tests.

Note that make grade runs all tests, including the ones for the assignments below. If you want to run the grade tests for one assignment, type:

$ ./grade-lab-util sleep

This will run the grade tests that match “sleep”. Or, you can type:

$ make GRADEFLAGS=sleep grade

which does the same.

pingpong

Exercise

Write a program that uses Unix system calls to “ping-pong” a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “<pid>: received ping”, where <pid> is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “<pid>: received pong”, and exit. Your solution should be in the file user/pingpong.c.

Some hints:

Use pipe to create a pipe.
Use fork to create a child.
Use read to read from the pipe, and write to write to the pipe.
Use getpid to find the process ID of the calling process.
Add the program to UPROGS in Makefile.
User programs on xv6 have a limited set of library functions available to them. You can see the list in user/user.h; the source (other than for system calls) is in user/ulib.c, user/printf.c, and user/umalloc.c.

Run the program from the xv6 shell and it should produce the following output:

$ make qemu
...
init: starting sh
$ pingpong
4: received ping
3: received pong
$

Your solution is correct if your program exchanges a byte between two processes and produces output as shown above.

primes

Exercise

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

Some hints:

Be careful to close file descriptors that a process doesn’t need, because otherwise your program will run xv6 out of resources before the first process reaches 35.
Once the first process reaches 35, it should wait until the entire pipeline terminates, including all children, grandchildren, etc. Thus the main primes process should only exit after all the output has been printed, and after all the other primes processes have exited.
read returns zero when the write-side of a pipe is closed.
It’s simplest to directly write 32-bit (4-byte) ints to the pipes, rather than using formatted ASCII I/O.
You should create the processes in the pipeline as they are needed.
Add the program to UPROGS in Makefile.

Your solution is correct if it produces the following output:

$ make qemu
...
init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
$

find

Exercise

Write a simple version of the Unix find program: find all the files in a directory tree whose name matches a string. Your solution should be in the file user/find.c.

Some hints:

Look at user/ls.c to see how to read directories.
Use recursion to allow find to descend into sub-directories.
Don’t recurse into “.” and “..”.
Changes to the file system persist across runs of QEMU; to get a clean file system run make clean</kbd> and then make qemu.
You’ll need to use C strings. Have a look at K&R (the C book), for example Section 5.5.
Note that == does not compare strings like in Python. Use strcmp() instead.
Add the program to UPROGS in Makefile.

Your solution is correct if produces the following output (when the file system contains a file a/b):

$ make qemu
...
init: starting sh
$ echo > b
$ mkdir a
$ echo > a/b
$ find . b
./b
./a/b
$

xargs

Exercise

Write a simple version of the Unix xargs program: read lines from standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

The following example illustrates xarg’s behavior:

$ echo hello too | xargs echo bye
bye hello too
$

Note that the command here is “echo bye” and the additional arguments are “hello too”, making the command “echo bye hello too”, which outputs “bye hello too”.

Some hints:

Use fork and exec system call to invoke the command on each line of input. Use wait in the parent to wait for the child to complete running the command.
To read individual lines of input, read from stdin a character at a time until the newline character (‘\n’).
kernel/param.h declares MAXARG, which may be useful if you need to declare an argv array.
Add the program to UPROGS in Makefile.
Changes to the file system persist across runs of QEMU; to get a clean file system run make clean and then make qemu.

xargs, find, and grep combine well:

$ find . b | xargs grep hello

will run “grep hello” on each file named b in the directories below “.”.

To test your solution for xargs, run the shell script xargstest.sh. Your solution is correct if it produces the following output:

$ make qemu
...
init: starting sh
$ sh < xargstest.sh
$ $ $ $ $ $ hello
hello
hello
$ $

You may have to fix bugs in your find program. The output has many $ because the xv6 shell is primitive and doesn’t realize it is processing commands from a file instead of from the console, and prints a $ for each command in the file.

Optional challenges

Challenge: uptime

Write an uptime program that prints the uptime in terms of ticks using the uptime system call.

Challenge: regexp support for find

Support regular expressions in name matching. grep.c has some primitive support for regular expressions.

Challenge: modify the shell

The xv6 shell (user/sh.c) is a minimal shell and lacks many features found in real shell. You can improve it. Here are some suggestions:

Modify the shell to not print a $ when processing shell commands from a file.
Modify the shell to support wait.
Modify the shell to support lists of commands, separated by “;”.
Modify the shell to support sub-shells by implementing “(“ and “)”.
Modify the shell to support tab completion.
Modify the shell to keep a history of passed shell commands.
Modify the shell to allow users to edit the command line.

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