【MIT6.S081】Lab4 trap backtrace

backtrace这个lab非常有意思，虽然实现的代码量不多，但是能让我们更好地理解栈、栈帧、指针、gdb的一些知识。

该实验的代码实现见：仓库commit

首先先解答一下【RISC-V assembly】中的一些问题：

Q: Which registers contain arguments to functions? For example, which register holds 13 in main's call to printf?
A: a0-a7, a2保存了13

Q: 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.)
A: 函数f和g被内联优化了

Q: At what address is the function printf located?
A: 0x000000000000064a

Q: What value is in the register ra just after the jalr to printf in main?
A: jalr指令的后一条指令的地址，也是当前pc寄存器中的地址

Q: Run the following code.
	 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.
---
A: output: He110 World 若risc-v为大端序，则i应该设置成0x726c6400；57616不需要变，因为无论是大端序还是小端序，其十六进制都为E110

Q: 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);
---
A: x=3 y=1403684968 y的值是一个随机值，因为本该传入printf的第三个参数并没有传入，而其对应的寄存器为a2，故y会使用a2中残存的值

这里的几个问题不是很难，涉及到了一些汇编、寄存器的知识，在接下来学习backtrace的时候将会有详细讨论。

backtrace需要我们做的事情可以概括为：在发生错误的点之上的堆栈上的函数调用列表，并在每个堆栈帧中打印保存的返回地址。

什么意思呢？就是例如在gdb调试中使用bt查看函数调用栈时，需要我们打印途中红色框中的地址。

该lab让我们在kernel/printf.c中实现一个backtrace函数。在sys_sleep中插入对此函数的调用，然后运行bttest这个测试程序将调用sleep（也就是会执行sys_sleep）。

首先，让我们来看看xv6中栈的结构：

                 .
                 .
    +->          .
    |   +-----------------+   |
    |   | return address  |   |
    |   |   previous fp ------+
    |   | saved registers |
    |   | local variables |
    |   |       ...       | <-+
    |   +-----------------+   |
    |   | return address  |   |
    +------ previous fp   |   |
        | saved registers |   |
        | local variables |   |
    +-> |       ...       |   |
    |   +-----------------+   |
    |   | return address  |   |
    |   |   previous fp ------+
    |   | saved registers |
    |   | local variables |
    |   |       ...       | <-+
    |   +-----------------+   |
    |   | return address  |   |
    +------ previous fp   |   |
        | saved registers |   |
        | local variables |   |
$fp --> |       ...       |   |
        +-----------------+   |
        | return address  |   |
        |   previous fp ------+
        | saved registers |
$sp --> | local variables |
        +-----------------+

栈是由高地址向低地址增长的，risc-v中sp寄存器代表“stack pointer”，即栈顶指针，fp寄存器代表“frame pointer”，为当前栈帧的指针。

假设有一个这样的程序：

#include <stdio.h>

void g() {
	printf("g()\n");
}

void f() {
	g();
	printf("f()\n");
}

int main() {
	f();
}

假设程序中的main函数里，函数f调用了函数g，那么在函数调用栈中从高地址到低地址三个函数的顺序为：main、f、g；当g函数执行完成后，其栈帧将会从栈中弹出，并且通过栈帧中的数据回到调用自身的下一条指令，即f中g的调用发生在第8行，当g执行完毕后，应该继续执行第9行的指令，这也就是“return address”。

我们可以通过内联汇编获取当前栈帧的的指针：

// kernel/riscv.h

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

然后不断遍历栈中的栈帧，打印其return address，直到遍历到最后一个栈帧。xv6在给栈分配内存时确保了每一个栈帧都在同一页中，这样的话可以通过PGROUNDDOWN(fp)宏来判断fp是否超出栈空间：

#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE - 1))

xv6中页的大小为4096B，故PGROUNDDOWN(a)可以获取a地址所在的页号，或者说这一页的最高地址，只要我们的fp不等于它，就说明我们还没有遍历到栈底。

fp - 8获取到return address的地址，fp - 16获取到当前栈帧的前一个栈帧的地址。由于xv6中获取的地址是用uint64来表示的，那么可将其强转为uint64*来将一个值解释为内存地址，之后便可以解引用这个地址获取其中的值了。

void backtrace() {
  uint64 fp = r_fp();
  printf("backtrace:\n");
  while (fp != PGROUNDDOWN(fp)) {
    uint64 *return_addr = (uint64 *)(fp - 8);
    fp = *(uint64 *)(fp - 16);
    printf("%p\n", *return_addr);
  }
}

当然，也不要忘记在kernel/def.h中声明backtrace，还有在sys_sleep中调用backtrace。