Lab util: Unix utilities

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

Boot xv6

Set up the required tools 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/cse481a/xv6-20sp.git
Cloning into 'xv6-20sp'...
...
$ cd xv6-20sp
$ git checkout -b util origin/xv6-20sp

The xv6-20sp 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, running git diff will display the changes to your code since your last commit, and git diff origin/xv6-20sp will display the changes relative to the initial xv6-20sp code. Here, origin/xv6-20sp 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
riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie   -c -o kernel/start.o kernel/start.c
...
$ make qemu
...
mkfs/mkfs fs.img README user/xargstest.sh user/_lazytests user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_wc user/_zombie user/_cowtest user/_uthread user/_call user/_testsh user/_kalloctest user/_bcachetest user/_alloctest user/_specialtest 
nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 1954 total 2000
balloc: first 805 blocks have been allocated
balloc: write bitmap block at sector 45
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0 -no-user-config -device virtio-net-device,netdev=en0 -object filter-dump,id=f0,netdev=en0,file=en0.pcap -netdev type=user,id=en0

xv6 kernel is booting

virtio disk init 0
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 1982
xargstest.sh   2 3 93
lazytests      2 4 28736
cat            2 5 24104
echo           2 6 22944
forktest       2 7 13296
grep           2 8 27456
init           2 9 23696
kill           2 10 22920
ln             2 11 22864
ls             2 12 26344
mkdir          2 13 23016
rm             2 14 23008
sh             2 15 41896
stressfs       2 16 24024
usertests      2 17 122984
wc             2 18 25256
zombie         2 19 22408
cowtest        2 20 30448
uthread        2 21 28368
call           2 22 22952
testsh         2 23 40832
kalloctest     2 24 27960
bcachetest     2 25 30760
alloctest      2 26 26712
specialtest    2 27 33736
console        3 28 0

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

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>

Hand-in procedure

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.

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

sleep

Some hints:

• Look at some of the other programs in user/ 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 user/usys.S and kernel/sysproc.c).
• Make sure main calls exit() in order to exit your program.
• Add the program to UPROGS in Makefile and compile user programs by typing make fs.img.

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 behaves as shown above.

Optional: write an uptime program that prints the uptime in terms of ticks using the uptime system call.

pingpong

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.

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 behaves as shown above. The number before “:” is the process id of the process printing the output. You can get the process id by calling the system call getpid.

primes

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, you should arrange that the pipeline terminates cleanly, including all children (hint: read will return an end-of-file when the write-side of the pipe is closed).
• It’s simplest to directly write 32-bit ints to the pipes, rather than using formatted ASCII I/O.
• You should create the processes in the pipeline as they are needed.

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

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 “..”.
• You’ll need to use C strings. Have a look at K&R (the C book), for example Section 5.5.

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

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

xargs

The following example illustrates xarg’s behavior:

$ xargs echo bye
hello too
bye hello too
ctrl-d
$

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.
• Read from stdin a character at the time until the newline character (‘\n’).
• kernel/param.h declares MAXARG, which may be useful if you need to declare an argv.

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.

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