Lab: traps

This lab explores how system calls are implemented using traps. You will first do a warm-up exercises with stacks and then you will implement an example of user-level trap handling.

Before you begin the traps lab, read Chapter 4 of the xv6 book, and related source files:

In this lab, there are several questions for you to answer. Questions are in boxes with a light orange background. Write each question and its answer in your notebook. Take photo(s) of your questions/answers and submit the photo(s) on Canvas.

The Linux grep command can be helpful on some questions. For example, suppose a question asks you about the macro TRAPFRAME. You can discover the definition and uses of the macro TRAPFRAME by issuing the following Linux grep command in the kernel directory. 

$ grep TRAPFRAME *.h
memlayout.h://   TRAPFRAME (p->trapframe, used by the trampoline)
memlayout.h:#define TRAPFRAME (TRAMPOLINE - PGSIZE)
memlayout.h:#define USYSCALL (TRAPFRAME - PGSIZE)
% grep TRAPFRAME *.c
proc.c:  if(mappages(pagetable, TRAPFRAME, PGSIZE,
proc.c:     uvmunmap(pagetable, TRAPFRAME, 1, 0);
proc.c:  uvmunmap(pagetable, TRAPFRAME, 1, 0);

In the directory of your xv6-labs, create two files: answers-traps.txt and time.txt that the grading script looks for. You can create these files by the following: 

$ echo > answers-traps.txt
$ echo 10 > time.txt
I use the information in your photo files and your lab-traps-handin.txt file that you submit on Canvas. I have retained these files and this grading script approach in case I want to use it in the future.

To start the lab, switch to the trap branch: 

  $ git fetch
  $ git checkout traps
  $ make clean

RISC-V assembly

It will be important to understand a bit of RISC-V assembly. You were exposed to ARM assembly in CPSC 305. RISC-V and ARM are both Reduced Instruction Set Computers (RISC). Recall that attributes of RISC architectures are

Moving from ARM to RISC-V is rather straightforward especially since we do not have to become expert assembly programmers for the course. There is a file user/call.c in your xv6 repo. make fs.img compiles it and also produces a readable assembly version of the program in user/call.asm.

The C code for user/call.c is the following. 

int g(int x) {
  return x+3;
}

int f(int x) {
  return g(x);
}

void main(void) {
  printf("%d %d\n", f(8)+1, 13);
  exit(0);
}

Read the code in call.asm for the functions g, f, and main. The instruction manual for RISC-V is on the reference page, if you need it. Answer the following questions in notebook.

1. Which registers contain arguments to functions? For example, which register holds 13 in main's call to printf?
2. Where is the call to function f in the assembly code for main? Where is the call to g? (Hint: the compiler may inline functions.)
3. At what address is the function printf located?
4. What value is in the register ra just after the jalr to printf in main?
5. Run the following code on Xv6. You will have to create a user program and add it to UPROGS in the Makefile.

Include the running of your program in your lab-traps-handin.txt. 

	unsigned int i = 0x00646c72;
	printf("H%x Wo%s", 57616, &i);
What is the output? Here's an ASCII table that maps bytes to characters.

The output depends on that fact that the RISC-V is little-endian. If the RISC-V were instead big-endian what would you set i to in order to yield the same output? Would you need to change 57616 to a different value?

Here's a description of little- and big-endian and a more whimsical description.

6. What are the attributes of a RISC architecture?
7. Compare a RISC architecture to a CISC architecture?

Backtrace

For debugging it is often useful to have a backtrace: a list of the function calls on the stack above the point at which the error occurred. To help with backtraces, the compiler generates machine code that maintains a stack frame on the stack corresponding to each function in the current call chain. Each stack frame contains of the return address, "saved frame pointer", saved registers, and local variables. The "saved frame pointer" points to the caller's stack frame, which has a "saved frame pointer" that points to its caller's stack frame. Register s0 contains a pointer to the current stack frame (it actually points to the the address of the saved return address on the stack plus 8). Your backtrace should begin with the value in s0, walk up the stack, and print the saved return address (ra) in each stack frame.

Implement a backtrace() function in kernel/printf.c. Insert a call to this function in sys_sleep, and then run bttest, which calls sys_sleep. You will have to add a backtrace function prototype in defs.h. Your output should be a list of return addresses with this form (but the numbers will likely be different): 

    $ bttest
    0x00000000800021f2
    0x0000000080002064
    0x0000000080001d26
The Linux program addr2line translates an address to a filename and line number using a file that has debug information in it. The file kernel/kernel has the Xv6 kernel's executable and debug information. addr2line reads addresses as input from standard input until you enter Ctrl-D. You can enter addresses one at a time, or copy/paste all three.

After bttest exit qemu. In a terminal window: run riscv64-linux-gnu-addr2line -e kernel/kernel (or riscv64-unknown-elf-addr2line -e kernel/kernel) and cut-and-paste the addresses from your backtrace, entering one address at a time, like this: 

    $ riscv64-linux-gnu-addr2line -e kernel/kernel
    0x00000000800021f2
    /home/faculty/ecooper/gustyx/kernel/sysproc.c:71
    0x0000000080002064
    /home/faculty/ecooper/gustyx/kernel/syscall.c:145
    0x0000000080001d26
    /home/faculty/ecooper/gustyx/kernel/trap.c:76
Or you can copy/paste all three like this: 
    $ riscv64-linux-gnu-addr2line -e kernel/kernel
    0x00000000800021f2
    0x0000000080002064
    0x0000000080001d26
    Ctrl-D
You should see something like this: 
    kernel/sysproc.c:71
    kernel/syscall.c:145
    kernel/trap.c:67

Some Hints

Once your backtrace is working, call it from panic in kernel/printf.c so that you see the kernel's backtrace when it panics.

Alarm

You do not have to implement this solution, but you must answer the questions.

In this exercise you'll add a feature to xv6 that periodically alerts a process as it uses CPU time. This might be useful for compute-bound processes that want to limit how much CPU time they chew up, or for processes that want to compute but also want to take some periodic action. More generally, you'll be implementing a primitive form of user-level interrupt/fault handlers; you could use something similar to handle page faults in the application, for example. Your solution is correct if it passes alarmtest and usertests -q.

You should add two new system calls: (1) sigalarm(interval, handler) system call. and (2) sigreturn() system call. If an application calls sigalarm(n, fn), then after every n "ticks" of CPU time that the program consumes, the kernel should cause application function fn() to be called. When fn() calls sigreturn(), the application should resume where it left off. The last statement in the function fn() will be a call to sigreturn().

A tick is a fairly arbitrary unit of time in xv6, determined by how often a hardware timer generates interrupts. If an application calls sigalarm(0, 0), the kernel should stop generating periodic alarm calls.

The following shows my implementation of the two system calls. 

uint64
sys_sigalarm(void)
{
  struct proc* p = myproc();
  argint(0, &p->interval);
  argaddr(1, &p->handler);
  p->regs = p->trapframe + sizeof(struct trapframe);
  return 0;
}

uint64
sys_sigreturn(void){
  struct proc* p = myproc();
  memmove(p->trapframe, p->regs, sizeof(struct trapframe));
  p->ticks = 0;
  return p->trapframe->a0;
}
15. Describe the three members added to the struct proc that are used by this implementation of the sigalarm and sigreturn system calls.

You'll find a file user/alarmtest.c in your xv6 repository. Add it to the Makefile. It won't compile correctly until you've added sigalarm and sigreturn system calls (see below).

alarmtest calls sigalarm(2, periodic) in test0 to ask the kernel to force a call to periodic() every 2 ticks, and then spins for a while. You can see the assembly code for alarmtest in user/alarmtest.asm, which may be handy for debugging. Your solution is correct when alarmtest produces output like this and usertests -q also runs correctly: 

$ alarmtest
test0 start
........alarm!
test0 passed
test1 start
...alarm!
..alarm!
...alarm!
..alarm!
...alarm!
..alarm!
...alarm!
..alarm!
...alarm!
..alarm!
test1 passed
test2 start
................alarm!
test2 passed
test3 start
test3 passed
$ usertest -q
...
ALL TESTS PASSED
$
16. The test0() in alarmtest.c is given by the following with line numbers. 
 1 void periodic() {
 2   count = count + 1;
 3   printf("alarm!\n");
 4   sigreturn();
 5 }
 6 
 7 void test0() {
 8   int i;
 9   printf("test0 start\n");
10   count = 0;
11   sigalarm(2, periodic);
12   for(i = 0; i < 1000*500000; i++){
13     if((i % 1000000) == 0)
14       write(2, ".", 1);
15     if(count > 0)
17       break;
18   }
19   sigalarm(0, 0);
20   if(count > 0){
21     printf("test0 passed\n");
22   } else {
23     printf("\ntest0 failed: the kernel never called the alarm handler\n");
24   }
25 }

A. What does line 11 do?

B. What happens during the loop on lines 12 through 18?

C. What does line 4 do?

D. What does line 19 do?

When you're done, your solution will be only a few lines of code, but it may be tricky to get it right. We'll test your code with the version of alarmtest.c in the original repository. You can modify alarmtest.c to help you debug, but make sure the original alarmtest says that all the tests pass.

Some Hints

17. The current code in usertrap() for a timer interrupt is the following. 
  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

Design the algorithm that will call the signal handler when the selected number of ticks has expired.

This requires some thought. You must examine the struct proc member ticks to see if it equal to the interval. If it is, what do you do? You do not call a function, because this is a timer interrupt. How do you manipulate the trap frame such that the sigalarm() handler is called?

If you study the remainder of this problem specification, you will get lots of clues as to how to design this.

Step 1: invoke handler

You want to first make sure the kernel can successfully jump to the alarm handler in user space. Modify the kernel to have a working sigalarm and a simplified sigreturn You can use test0 of alarmtest to test your changes. The alarm handler is test0 will print alarm! when it is called. Don't worry yet what happens after the "alarm!" output; it's OK for now if your program crashes after printing "alarm!". At this point, you just want the kernel to call the alarm handler. Here are some hints:

20. Several parts to this question.

A. What code executes initially when a trap/interrupt occurs?

B. What mode is the CPU in when it executes the trap handling code?

C. What page table is used when a trap/interrupt initially occurs?

D. What does the sfence RISC-V instruction do, and where is it used in the trap processing?

test1/test2()/test3(): resume interrupted code

Once you pass test0, test1, test2, and test3 run usertests -q to make sure you didn't break any other parts of the kernel.

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.