Lab: Xv6 and Unix utilities

This lab will familiarize you with xv6 and its system calls. You will learn how to create Unix/Linux utility programs using the Unix/Linux API. The Xv6 API is a simplfied Linux API. For example, the Xv6 API has a single exec function call to execute a new program within a process, whereas, Linux has a family of exec calls (ie., execp, execl, execvp, execlp).

You will create several Unix/Linux utility programs. All of the programs have a starting .c program that you must edit. For example, there is a kittycat.c program. You must design the code, edit the program, and test that it satisfies the requirements.

Boot xv6

You can do these labs on our CPSC server or on your own computer. If you use your own computer, have a look at the lab tools page for setup tips.

Fetch the git repository for the xv6 source for the lab:

$ git clone https://github.com/gustycooper/xv6-labs.git
Cloning into 'xv6-labs'...
...
$ cd xv6-labs

The repo is setup so that git checkouts the riscv branch when cloning the repo. You must switch to the util branch to conduct this lab.

$ git status
On branch riscv
Your branch is up to date with 'origin/riscv'.

nothing to commit, working tree clean
$ git checkout util

The xv6-labs repository differs slightly from the book's xv6-riscv; it mostly adds some files. If you are curious look at the git log:

$ git log

The files you will need for this and subsequent lab assignments are distributed using the Git version control system. For each of the labs you will checkout (git checkout util) a version of xv6 tailored for that 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. Running git diff will display the changes to your code since your last commit, and git diff origin/util will display the changes relative to the initial util code. Here, origin/util is the name of the git branch with the initial code you downloaded for the class.

Build and run xv6:

$ make qemu
riscv64-unknown-elf-gcc    -c -o kernel/entry.o kernel/entry.S
riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_UTIL -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
...
riscv64-unknown-elf-ld -z max-page-size=4096 -N -e main -Ttext 0 -o user/_zombie user/zombie.o user/ulib.o user/usys.o user/printf.o user/umalloc.o
riscv64-unknown-elf-objdump -S user/_zombie > user/zombie.asm
riscv64-unknown-elf-objdump -t user/_zombie | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > user/zombie.sym
mkfs/mkfs fs.img README  user/xargstest.sh 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/_grind user/_wc user/_zombie
nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 954 total 1000
balloc: first 591 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

xv6 kernel is booting

hart 2 starting
hart 1 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 508
kittycat.txt   2 3 597
xargstest.sh   2 4 93
cat            2 5 32848
echo           2 6 31696
forktest       2 7 15832
grep           2 8 36224
init           2 9 32200
kill           2 10 31664
ln             2 11 31480
ls             2 12 34792
mkdir          2 13 31712
rm             2 14 31704
sh             2 15 54144
stressfs       2 16 32592
usertests      2 17 180488
grind          2 18 47536
wc             2 19 33800
zombie         2 20 31064
kittycat       2 21 32864
sleep          2 22 31208
pingpong       2 23 31224
primes         2 24 31208
find           2 25 31208
xargs          2 26 31208
console        3 27 0

$ echo kittycat
kittycat
$ cat kittycat.txt
This is the text in the file kittycat.

Soft kitty, warm kitty, 
little ball of fur! 
Happy kitty, sleepy kitty, 
purr purr purr!
Xv6 kitty, Xv6 kitty,
grrr, grrr, grrr!

And the cat's in the cradle and the silver spoon
Little boy blue and the man in the moon
"When you coming home, dad?" "I don't know when"
But we'll get together then
You know we'll have a good time then

A long tailed cat sitting by the old rocking chair
Now he don't realize that there's a danger there
But he don't care no rock 'n' roll chair is gonna boogie on his day
'Cause when his tail took a low down, syncopate, yeah

xv6 has no ps command, but, if you type Ctrl-p, the kernel will print information about each process. If you try it now, you'll see two lines: one for init, and one for sh.

To quit qemu type: Ctrl-a x (press Ctrl and a at the same time, followed by x).

Grading and hand-in procedure

You can run make grade to test your solutions with the grading program. I will use the same grading program to assign your lab submission a grade. Separately, we will also have check-off meetings for labs (see Grading policy).

The lab code comes with GNU Make rules to make submission easier. After committing your final changes to the lab, type HERE::make handin to submit your lab. For detailed instructions on how to submit see below.

kittycat

Some Hints

• Before you start coding, read Chapter 1 of the xv6 book.
• The code in user/kittycat.c is a duplicate of user/cat.c. You should study the code in user/kittycat.c to understand how the UNIX cat program works. cat places the contents of a file (or multiple files) to standard output. You can redirect cat's output or pipe it to another UNIX program.
• 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 passes an argument, kittycat should print the error message: kittycat: No args allowed.
• Ensure your kittycat program has been added 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
      $ kittycat
      This is the text in the file kittycat.

      Soft kitty, warm kitty, 
      little ball of fur! 
      Happy kitty, sleepy kitty, 
      purr purr purr!
      Xv6 kitty, Xv6 kitty,
      grrr, grrr, grrr!

      And the cat's in the cradle and the silver spoon
      Little boy blue and the man in the moon
      "When you coming home, dad?" "I don't know when"
      But we'll get together then
      You know we'll have a good time then

      A long tailed cat sitting by the old rocking chair
      Now he don't realize that there's a danger there
      But he don't care no rock 'n' roll chair is gonna boogie on his day
      'Cause when his tail took a low down, syncopate, yeah

      $ kittycat gusty
      kittycat: No args allowed
    

Testing

Your solution is correct if your program generates the output shown above. Run make grade to see if you indeed pass the kittycat 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 kittycat
   

     $ make GRADEFLAGS=kittycat grade
   

sleep

Some Hints

• Before you start coding, read Chapter 1 of the xv6 book.
• 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.
• main should call exit(0) when it is done.
• Ensure your sleep program has been added 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.
• Look at Kernighan and Ritchie's book The C programming language (second edition) (K&R) to learn about C.

Testing

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
   

     $ make GRADEFLAGS=sleep grade
   

pingpong

Some Hints

• Use pipe to create a pipe.
• Use fork to create a child.
• Use read to read from a pipe, and write to write to a pipe.
• Use getpid to find the process ID of the calling process.
• Ensure your pingpong program has been added UPROGS in Makefile; once you've done that, make qemu will compile your program and you'll
• 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.

Testing

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

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, &c. Thus the main primes process should only exit after all the output has been printed, and after all the other primes processes have exited.
• Hint: 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 only as they are needed.
• Ensure your primes program has been added UPROGS in Makefile; once you've done that, make qemu will compile your program and you'll

Testing

Your solution is correct if it implements a pipe-based sieve and 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 "..".
• Changes to the file system persist across runs of qemu; to get a clean file system run make clean 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.
• Ensure your find program has been added UPROGS in Makefile; once you've done that, make qemu will compile your program and you'll

Testing

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

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

xargs

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

Please note that xargs on UNIX makes an optimization where it will feed more than argument to the command at a time. We don't expect you to make this optimization. To make xargs on UNIX behave the way we want it to for this lab, please run it with the -n option set to 1. For instance

    $ (echo 1 ; echo 2) | xargs -n 1 echo
    1
    2
    $
  

Some Hints

• The first argument to xargs is the program to execute. The command xargs grep hello executes the program grep, which is the first argument passed to xargs
• xargs is typically used on the right side of a pipe. This means the left side of the pipe generates output that is seen as xargs standard input. xargs sees this standard input as a sequence of lines, each terminated with a \n.
• xargs executes the program on each line seen from standard input.
• Consider the example sequence of commands that works with three files a, b, and README. README exists and we use echo to create a and b. I have numbered the commands in order to reference them. You should enter the commands in the Xv6 shell as you study to better understand xargs.

  $ echo hello > b       [1] 
  $ cat b                [2] 
  hello
  $ echo 12README > a    [3] 
  $ echo b >> a          [4] 
  $ cat a                [5] 
  b
  README
  $ ls a b README        [6] 
  a              2 28 9
  b              2 27 6
  README         2 2 2227
  $ lss a b README       [7] 
  a
  b
  README
  $ lss b README         [8] 
  b
  README
  $ wc b                 [9] 
  1 1 6 b
  $ wc README            [10] 
  47 316 2227 README
  $ cat a | xargs wc     [11] 
  1 1 6 b
  47 316 2227 README
  $ lss b README | xargs wc [12] 
  1 1 6 b
  47 316 2227 README
        

  • Command [1] creates the file b to have one line (the string hello). echo echos the string hello to standard output and the > character redirects standard output to the file b. Command [2] cats b to standard output to show it contains hello.
  • Commands [3] and [4] create the file a to have two lines - line 1 is b and line 2 is README. This awkward use of the Xv6 cat creates a two line file. I fiddled around until I found a way to create a file with the two lines I wanted. Realize that the Xv6 cat is a simplified version of the Linux cat.
  • Command [5] shows that the file a has the desired two lines. Each line contains a name of a file in the current directory.
  • Commands [6] and [7] show the three files a, b, and README in the current directory. Notice the Xv6 ls command shows the file type (1 is file, 2 is directory, etc.), the inode number, and the size (in bytes). The lss command just shows the file names. We will use the lss command to pipe filenames to xargs wc so there are no spaces in the input stream to xargs.
  • Command [8] show the two files b and README in the current directory. If you compare the output of the cat a of command [5] to the output of lss b README of command [8], you will see they are identical. They both write the following to standard output.
    b\nREADME\n
    
  • Commands [9] and [10] count the lines, words, and characters in the files b and README.
  • Commands [11] and [12] demonstrate how xargs works. Both cat a and lss b README generate the same stream of characters to standard output, (i.e., b\nREADME\n) which is piped to the standard input of xargs. xargs reads the standard input and applies the command wc to each line, where a line is marked by the character '\n'. This means the commands [11] and [12] are equivalent to the following.

    $ wc b
    $ wc README
          

• xargs, find, and grep combine well. Consider the example sequence of commands.

  $ mkdir a                      [1] 
  $ echo hello > a/b             [2] 
  $ mkdir c                      [3] 
  $ echo hello > c/b             [4] 
  $ echo hello > b               [5] 
  $ find . b                     [6] 
  ./b
  ./a/b
  ./c/b
  $ grep hello b                 [7] 
  hello
  $ grep hello ./b               [8] 
  hello
  $ grep hello a/b               [9] 
  hello
  $ grep hello ./a/b             [10] 
  hello
  $ find . b | xargs grep hello  [11] 
  hello
  hello
  hello
        

  • Commands [1] through [5] use mkdir and echo to create subdirectories a and b, each of which has a file named b with the string hello. If you are typing this commands in the same session as the previous sample commands, you will have to remove the file a that we created earlier.
  • Command [6] shows the output of find . b, which shows a file b in the current directory and the subdirectories a and b. These three lines of output will be streamed to the standard input of xargs.
  • Commands [7] through [10] show various grep commands. grep searches a file for a string. Notice commands [7] and [8] both search the file b in the current directoy. Command [8] uses a path.
  • Command [11] shows the combinations of xargs, find, and grep. find generates three lines in standard output. Each line is a path of a file name. xargs applies the command grep hello to each of these lines. Command [11] is equivalent to the following.

    $ grep hello ./b
    $ grep hello ./a/b
    $ grep hello ./c/b
          

• xargs is the parent process and it will use fork and exec to invoke the command on each line of input. The exec-ed command is the child process. xargs will use wait to wait for the child to complete the command.

• To read individual lines of standard input, read a character at a time until a newline ('\n') appears.
• kernel/param.h declares MAXARG, which may be useful if you need to declare an argv array.
• Ensure your xargs program has been added UPROGS in Makefile; once you've done that, make qemu will compile your program and you'll
• Changes to the file system persist across runs of qemu; to get a clean file system run make clean and then make qemu.

High-level Design

Process args passed to xargs
Make sure it has at least one argument. 
For example, $ xargs wc
Create a char* array (e.g. xargv) for arguments to the exec call
Put the first arg passed to xargs in xargv[0]
The read loop will put values in xargv[1], xargv[2], ...
READLOOP:
Read 1 character from standard input
If the read returns 0, you exit READLOOP
If the character read is \n 
  if (fork() == 0)
    call exec with xargv
  else
    wait
else if the character read is a space
  move to next element of xargv
else
  concatenate character onto string to put into xargv
GOTO READLOOP

Testing

To test your solution for xargs, run the seqence of commands provided in the hints section. The shell script xargstest.sh has been provided. Its contents are the following.

mkdir a
echo hello > a/b
mkdir c
echo hello > c/b
echo hello > b
find . b | xargs grep hello

The program sh is the shell. You can use input redirection to redirect the contents xargstest.sh to the shell as shown next. You output should match this.

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

Submit the lab

This completes the lab. Make sure you pass all of the make grade tests. Read Lab Submissions for instructions on how to submit your lab.