MIT 6.828 -- Lab 1: Unix Utilities

Lab 1 of MIT 6.828/6.S081 Fall 2019 is Unix utilities: using xv6 system calls to implement tools such as sleep, pingpong, primes, find, and xargs. This post explains the approach behind each program in detail, along with how a system call flows through xv6.

Before You Start

Before starting the lab, I recommend reading the materials for LEC1 on the course site. The Introduction is an overview of the course, and the examples are a few system programming samples; a quick skim of both is enough. Chapter 1 of the xv6 book deserves a more careful read, especially the parts on the fork(), exec(), pipe(), and dup() system calls, which the labs use later.

For setting up the lab environment, see the previous post. The xv6-riscv-fall19 project has two important directories. kernel holds the xv6 kernel source: besides the core code that makes the OS work (such as process scheduling), it contains the interfaces exposed to the outside (system calls). user holds user programs, such as the familiar ls and echo commands. The goal of this lab is to add user programs under user and implement the required features with the system calls the kernel provides.

Implementation Approach

Each lab is written on its own branch. In the xv6-riscv-fall19 directory, run git checkout util to switch to the util branch, and you can start writing programs. Below I mainly describe the approach; for the full lab code, see GitHub. (Update: after doing 2 labs on the 2019 version I switched to the 2020 version; for the new lab code, see xv6-labs-2020.)

When you're done, make grade runs the unit tests and scores the lab. It starts QEMU in gdb-server mode, and gradelib.py acts as a gdb client to test our programs. If make grade fails with Timeout! Failed to connect to QEMU, change line 325 of gradelib.py to self.sock.connect(("127.0.0.1", port)).

sleep

sleep makes the process sleep for a number of clock ticks (one tick in xv6 is 100ms). First create the source file user/sleep.c and include the header user.h, which declares the system calls and utility functions. The core code:

sleep(atoi(argv[1]));

Once it's written, append the line $U/_sleep\ to UPROGS in the Makefile. Run make qemu to build, and once you're in the shell, type sleep 10. If the process sleeps for about 1s, the program is correct.

pingpong

The parent process sends 1 byte to the child through a pipe, and after receiving it the child replies to the parent with 1 byte.

Since a pipe only flows one way, call pipe() twice to create two pipes, one for each direction. Use fork() to create the child. The child first does a read() on pipe 1 and then a write() on pipe 2; the parent does the opposite.

primes

primes prints the primes between 2 and 35. It works by recursively forking processes and connecting them with pipes, forming a pipeline that filters out the primes.

The first number p that each process receives is always prime. Each later number is dropped if it is divisible by p; otherwise it is passed on to the next process. See this article for details. Pseudocode:

void primes() {
  p = read from left         // the first number received from the left is always prime
  if (fork() == 0): 
    primes()                 // child: recurse
  else: 
    loop: 
      n = read from left     // parent: keep reading input from the left  
      if (p % n != 0): 
        write n to right     // not divisible by p, so pass it to the right   
}

Two more things to watch out for:

• Running out of file descriptors: xv6 limits fds to the range 0~15, and every pipe() creates two new fds, so if you don't close unneeded fds promptly, the process runs out of file descriptors. The approach here is to redirect to standard I/O so that no new fds are created: first close() the standard I/O fd, then use dup() to duplicate the needed pipe fd (it automatically lands on the lowest-numbered free fd, i.e. the standard I/O fd just closed), and then close both ends of the pipe (this only removes the descriptors; the underlying file object is not closed).
• Shutting down the pipeline: After all the primes are printed, every process on the pipeline needs to exit in turn. Before a parent process exits, close its standard input fd. read() then reads EOF (returns 0), at which point the child likewise closes its standard input fd and exits. This way every process along the chain exits.

find

find matches file names within a directory. The approach is to search the whole directory tree recursively.

Use open() to get an fd for the current path and fstat() to check the fd's type. If it's a file, compare it with the file name being searched for. If it's a directory, read() into a dirent struct in a loop to get the names of its child files and directories, join each name onto the current path, and recurse. Don't recurse into the . and .. entries in subdirectories.

xargs

xargs turns standard input into command-line arguments for a program. Combined with a pipe, it lets a command that can't read standard input use standard input as its arguments.

The examples in the lab show that xv6's xargs runs the command and prints the result every time you press Enter, until ctrl+d ends it. The Linux implementation instead keeps reading input and only runs the command and prints the result when it receives ctrl+d.

The approach uses two nested loops to read standard input:

• The inner loop reads one character at a time, splits arguments on spaces, and stores the argument strings in a 2D array. It breaks out of the loop when it reads 'n', and exits the program on ctrl+d (read returns a length <0).
• The outer loop fork()s a child for each line of input and calls exec() to run the command. Note that in the 2D argument array argv passed to exec, the first element argv[0] must be the command itself and the last element argv[size-1] must be 0, or the exec will fail.

How System Calls Work in xv6

Using system calls in the lab is simple, and they look no different from ordinary function calls. The actual call flow is fairly involved, though, and a few questions come up naturally: What does the full lifecycle of a system call look like? How is context switched between the user process and the kernel process? How are the system call's function name, arguments, and return value passed between the user process and the kernel process?

1. User-mode call

In user space, the function declarations for all system calls live in user.h. A call goes into usys.S and runs assembly instructions: it puts the corresponding system call number in register a7 and executes the ecall instruction to make the system call, with the function arguments in the 6 registers a0~a5. The ecall instruction triggers a software interrupt. The CPU pauses the user program and runs the kernel's interrupt handling logic instead, trapping into kernel mode.

2. Context switch

Interrupt handling is in kernel/trampoline.S. It first switches context: it saves the user process's register contents to memory (preserving its state) and restores the kernel's register contents. The kernel maintains a process array (holding up to 64 processes) that stores each process's state. The proc struct is defined in proc.h; it is xv6's implementation of the PCB (Process Control Block). The user program's register contents are temporarily saved in the proc->trapframe struct.

3. Kernel-mode execution

After the switch, trap.c/usertrap() is called, which then goes into syscall.c/syscall(). That function uses the system call number to look up a function pointer in an array and runs the system call function. The arguments are taken from the user process's trapframe (a0~a5), and the result is stored in the trapframe's a0 field. When the call finishes, another switch is needed: the kernel registers are saved to trapframe->kernel_*, then the user process data held in the trapframe is restored to the registers, returning to user space. The CPU resumes from where it was interrupted and gets the function's return value from register a0.

That completes the system call. It involves two process context switches, user process -> kernel process -> user process, along with two switches of the CPU's mode: user mode -> kernel mode -> user mode.

Lab code: https://github.com/zhayujie/xv6-riscv-fall19

Permalink: https://zhayujie.com/mit6828-lab-util.html