Michael Xi

Traps in xv6: Backtraces and Alarms

  • Operating System
  • Linux
Contents

RISC-V assembly (easy)

Understand the Question

Read the code in call.asm for the functions g, f, and main in file user/call.c. The instruction manual for RISC-V is on the reference page.

👇 call.c

#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"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);
}

👇 call.asm

user/_call:     file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <g>:
#include "kernel/param.h"
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

; compiler has inlined the body of function g into function f
; eliminating the call to g altogether

int g(int x) {
   0:	1141                	addi	sp,sp,-16  ; allocate 16 bytes of stack space
   2:	e422                	sd	  s0,8(sp)   ; save the old frame pointer on stack
   4:	0800                	addi	s0,sp,16   ; update frame pointer to new stack frame
  return x+3;
}
   6:	250d                	addiw	a0,a0,3    ; add 3 to the function argument 'x' (in a0), result stays in a0
   8:	6422                	ld	  s0,8(sp)   ; restore the old frame pointer from the stack
   a:	0141                	addi	sp,sp,16   ; deallocate the stack space
   c:	8082                	ret

000000000000000e <f>:

int f(int x) {
   e:	1141                	addi	sp,sp,-16
  10:	e422                	sd	  s0,8(sp)
  12:	0800                	addi	s0,sp,16
  return g(x);
}
  14:	250d                	addiw	a0,a0,3
  16:	6422                	ld	  s0,8(sp)
  18:	0141                	addi	sp,sp,16
  1a:	8082                	ret

; asm of main function call

000000000000001c <main>:

void main(void) {
  1c:	1141                	addi	sp,sp,-16
  1e:	e406                	sd	  ra,8(sp)   ; save the return address on the stack
  20:	e022                	sd	  s0,0(sp)
  22:	0800                	addi	s0,sp,16

  ; preparing for printf

  printf("%d %d\n", f(8)+1, 13);
  24: 4635                  li    a2,13      ; load immediate 13 into a2 (3rd argument for printf)
  26: 45b1                  li    a1,12      ; load immediate 12 into a1 (2nd argument for printf, result of f(8)+1)
  28: 00000517              auipc a0,0x0     ; set up the a0 register to current program counter (PC)
  2c: 7a050513              addi  a0,a0,1952 ; adjust the pointer to the actual memory address of the format string

  ; calling printf

  30:	00000097          	auipc	ra,0x0       ; prepare return address register (ra) with current PC value
  34:	5f8080e7          	jalr	1528(ra)     ; jumps to address calculated by adding 1528 to the value in ra, call printf

	; exiting program
  exit(0);
  38:	4501                	li	a0,0         ; load the immediate value 0 into a0, exit status
  3a:	00000097          	auipc	ra,0x0       ; set the current pc as ra
  3e:	274080e7          	jalr	628(ra) # 2ae <exit> ; call the exit function by jumping to the address calculated from ra plus 628

Solution

  1. Which registers contain arguments to functions? For example, which register holds 13 in the main’s call to printf?

    • a2 register holds 13 in the main’s call to printf.
    • a0, a1, and a2 registers hold the first, second, and third function arguments accordingly.
    • In fact, registers from a0 to a7 hold the function arguments. If more arguments are passed, then the rest of the arguments are passed to the stack.

  2. Where is the call to function f in the assembly code for the main? Where is the call to g? (Hint: the compiler may inline functions.)

    The function f is called not directly from main but rather prepared as an argument setup for printf. In another word, it’s pre-calculated.

  3. At what address is the function printf located?

    The base address for printf is computed from ra plus an offset of 1528.

  4. What value is in the register ra just after the jalr to printf in main?

    The value in the ra is the address of the instruction immediately following the jalr instruction (i.e., the address where execution should resume after printf completes).

  5. Run the following code:

    unsigned int i = 0x00646c72;
printf("H%x Wo%s", 57616, &i);

    With %s in functions like printf, the string is always read from the starting address (low) to the higher addresses, one byte (character) at a time

    What is the output?

    • The output is HE110 World
    • Decimal 57616 in hex is E110
    • 0x00646c72 is rld
      • 0x72 → r
      • 0x6c → l
      • 0x64 → d
      • 0x00 → \0

    The output depends on the 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?

    • i should be 0x726c6400
    • There is no need to change 57616 because the hexadecimal interpretation does not depend on endianness for individual integer values

  6. In the following code, what is going to be printed after 'y='? (note: the answer is not a specific value.) Why does this happen?

    printf("x=%d y=%d", 3);

    After y=, nothing specific is printed; it’s undefined behavior because printf expects two integer arguments for %d placeholders, but only one is provided. In practice, this might print a garbage value or cause a runtime error. This happens because printf tries to access a second integer argument that was not provided, leading to unpredictable behavior.

Backtrace (moderate)

Understand the Question

The goal is to 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. Your output should be as follows:

backtrace:
0x0000000080002cda
0x0000000080002bb6
0x0000000080002898

The backtrace should use the frame pointers in each stack frame to walk up the stack and print the saved return address in each stack frame.

Some important facts for implementing backtrace:

  1. The stack grows downward in RISC-V, so to backtrace the stack frames, we need to walk upwards.
  2. Frame Pointer (FP) is a fixed pointer that always points to the top of the current Stack Frame.
  3. The pointer to the previous frame is at FP - 16
  4. The pointer to the current return address is at FP - 8
  5. Xv6 allocates one page for each stack in the xv6 kernel. You can compute the top and bottom addresses of the stack page by using PGROUNDDOWN(fp) and PGROUNDUP(fp). These numbers are useful for backtrace to terminate its loop of walking upwards.

Solution

In kernel/riscv.h:

static inline uint64
r_fp()
{
  uint64 x;
  asm volatile("mv %0, s0" : "=r" (x));
  return x;
}

In kernel/printf.c:

void backtrace() {
  uint64 fp;   /* frame pointer */uint64 top;  /* top of stack */uint64 down; /* bottom of stack */

  /* get current frame pointer */fp = r_fp();

  /* get address range of stack */top = PGROUNDUP(fp);
  down = PGROUNDDOWN(fp);

  printf("backtrace:\n");

  while (fp <= top && fp >= down) {
    uint64 ra = *(uint64 *)(fp - 8);
    fp = *(uint64 *)(fp - 16);
    printf("%p\n", ra);
  }
}

Add the backtrace function call to sys_sleep function call in sysproc.c, the output is:

michaelxi@michaelxi-VirtualBox:~/xv6-labs-2021$ addr2line -e kernel/kernel
0x00000000800020e6
0x0000000080001fac
0x0000000080001c96
0x0000000000000012
/home/michaelxi/xv6-labs-2021/kernel/sysproc.c:66
/home/michaelxi/xv6-labs-2021/kernel/syscall.c:140
/home/michaelxi/xv6-labs-2021/kernel/trap.c:7

Alarm (hard)

Understand the Question

The goal is to add a feature to xv6 that periodically alerts a process as it uses CPU time. Specifically, we need to add a new sigalarm(interval, handler) 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 returns, the application should resume where it left off.

  • “Tick” is arbitrary, and for each time interrupt event, the tick increments one.
  • If an application calls sigalarm(0, 0), the kernel should stop generating periodic alarm calls.

Solution

First, setting up system call routine:

👇 Declarations in user/user.h

int sigalarm(int ticks, void (*handler)());
int sigreturn(void);

👇 Update user/usys.pl to generate updated user/usys.S

entry("sigalarm");
entry("sigreturn");

👇 Update kernel/syscall.h and kernel/syscall.c to allow alarmtest to invoke the sigalarm and sigreturn system calls

#define SYS_sigalarm  22
#define SYS_sigreturn 23
extern uint64 sys_sigalarm(void);
extern uint64 sys_sigreturn(void);

static uint64 (*syscalls[])(void) = {
	[SYS_sigalarm]  sys_sigalarm,
	[SYS_sigreturn] sys_sigreturn,
};

Second, implement sigalarm and sigreturn system calls, and the timer interrupt handling logic

In kernel/sysproc.c, implement these two syscall functions:

uint64 sys_sigalarm(void) {
  int ticks;
  uint64 handler;
  // Get first argument
  if(argint(0, &ticks) < 0)
    return -1;
  // Get second argument
  if(argaddr(1, &handler) < 0)
    return -1;
  // Save the arguments into proc struct
  struct proc *p = myproc();
  p->interval = ticks;
  p->handler = handler;

  return 0;
}

And the sys_sigreturn function:

/* Return the previous execution properly */
uint64 sys_sigreturn(void) {
  struct proc *p = myproc();

  // Recover from handler function
  p->trapframe->ra = p->ra;
  p->trapframe->sp = p->sp;
  p->trapframe->gp = p->gp;
  p->trapframe->tp = p->tp;
  p->trapframe->t0 = p->t0;
  p->trapframe->t1 = p->t1;
  p->trapframe->t2 = p->t2;
  p->trapframe->s0 = p->s0;
  p->trapframe->s1 = p->s1;
  p->trapframe->a0 = p->a0;
  p->trapframe->a1 = p->a1;
  p->trapframe->a2 = p->a2;
  p->trapframe->a3 = p->a3;
  p->trapframe->a4 = p->a4;
  p->trapframe->a5 = p->a5;
  p->trapframe->a6 = p->a6;
  p->trapframe->a7 = p->a7;
  p->trapframe->s2 = p->s2;
  p->trapframe->s3 = p->s3;
  p->trapframe->s4 = p->s4;
  p->trapframe->s5 = p->s5;
  p->trapframe->s6 = p->s6;
  p->trapframe->s7 = p->s7;
  p->trapframe->s8 = p->s8;
  p->trapframe->s9 = p->s9;
  p->trapframe->s10 = p->s10;
  p->trapframe->s11 = p->s11;
  p->trapframe->t3 = p->t3;
  p->trapframe->t4 = p->t4;
  p->trapframe->t5 = p->t5;
  p->trapframe->t6 = p->t6;
  p->trapframe->epc = p->epc;

  // Set in_handler state to false
  p->handler_on = 0;

  return 0;
}

Modify the proc struct in kernel/proc.h to add additional fields for alarm:

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // wait_lock must be held when using this:
  struct proc *parent;         // Parent process

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)

  // 🌟 alarm private fields
  int interval;                // ticks interval
  uint64 handler;              // handler address
  int ticks_pass;              // ticks passed since last call
  int handler_on;              // 0 means no handler, 1 means handler exists

  uint64 epc;
  uint64 ra;
  uint64 sp;
  uint64 gp;
  uint64 tp;
  uint64 t0;
  uint64 t1;
  uint64 t2;
  uint64 s0;
  uint64 s1;
  uint64 a0;
  uint64 a1;
  uint64 a2;
  uint64 a3;
  uint64 a4;
  uint64 a5;
  uint64 a6;
  uint64 a7;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
  uint64 t3;
  uint64 t4;
  uint64 t5;
  uint64 t6;
};

In kernel/trap.c, modify the usertrap function to add alarm logic into timer interrupt handling.

Here’s the formatted and code-blocked version of the usertrap function:

// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
void usertrap(void)
{
  int which_dev = 0;

  if((r_sstatus() & SSTATUS_SPP) != 0)
    panic("usertrap: not from user mode");

  // send interrupts and exceptions to kerneltrap(),
  // since we're now in the kernel.
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  // save user program counter.
  p->trapframe->epc = r_sepc();

  if(r_scause() == 8){
    // system call
    if(p->killed)
      exit(-1);

    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();

    syscall();
  } else if((which_dev = devintr()) != 0){
    // ok
  } else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }

  if(p->killed)
    exit(-1);

  // 🌟 if it's a timer interrupt and currently no handler is on
  if (which_dev == 2 && p->handler_on == 0) {
    // tick count plus one
    p->ticks_pass += 1;

    // check if alarm should be enabled
    if (p->ticks_pass % p->interval == 0) {
      // reset ticks pass and set handler status to prevent re-enter
      p->ticks_pass = 0;
      p->handler_on = 1;

      // save the trapframe registers for future return
      p->epc = p->trapframe->epc;
      p->ra  = p->trapframe->ra;
      p->sp  = p->trapframe->sp;
      p->gp  = p->trapframe->gp;
      p->tp  = p->trapframe->tp;
      p->t0  = p->trapframe->t0;
      p->t1  = p->trapframe->t1;
      p->t2  = p->trapframe->t2;
      p->s0  = p->trapframe->s0;
      p->s1  = p->trapframe->s1;
      p->a0  = p->trapframe->a0;
      p->a1  = p->trapframe->a1;
      p->a2  = p->trapframe->a2;
      p->a3  = p->trapframe->a3;
      p->a4  = p->trapframe->a4;
      p->a5  = p->trapframe->a5;
      p->a6  = p->trapframe->a6;
      p->a7  = p->trapframe->a7;
      p->s2  = p->trapframe->s2;
      p->s3  = p->trapframe->s3;
      p->s4  = p->trapframe->s4;
      p->s5  = p->trapframe->s5;
      p->s6  = p->trapframe->s6;
      p->s7  = p->trapframe->s7;
      p->s8  = p->trapframe->s8;
      p->s9  = p->trapframe->s9;
      p->s10 = p->trapframe->s10;
      p->s11 = p->trapframe->s11;
      p->t3  = p->trapframe->t3;
      p->t4  = p->trapframe->t4;
      p->t5  = p->trapframe->t5;
      p->t6  = p->trapframe->t6;

      // redirect to handler
      p->trapframe->epc = p->handler;
    }

    // give up CPU since it's a timer interrupt
    yield();
  }

  usertrapret();
}

Note that inside the handler function of the testing program, it calls sigreturn() to recover the previous program’s context.

The final test outputs are as follows, indicating that all tests are passed:

$ ./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

← All posts