一、本节任务

二、要点（Traps and system calls）

有三种事件会使 CPU 暂停当前的指令执行，并强制将控制转移到处理该事件的特殊代码中：

1. 系统调用（ecall）；
2. 异常（如非法指令，除0，无效的虚拟地址）；
3. 设备中断（interrupt）；

在 xv6 中，这三种情况被统称为 trap，系统调用、异常、设备中断以同样的方式进入内核。

trap 的一般流程为：首先 trap 会使控制转移到内核，内核保存寄存器和一些其他状态信息；然后内核执行适当的处理程序（如系统调用的实现或设备驱动程序）；最后内核恢复保存的状态，并且从 trap 返回到原来执行的位置继续执行。

2.1 RISC-V 陷阱机制（RISC-V trap machinery）

每个 RISC-V CPU 都有一组控制寄存器，内核写入这些寄存器来告诉 CPU 如何处理陷阱，并且内核可以读取这些寄存器来找出已经发生的陷阱。下面是比较重要的几个寄存器：

1. stvec（supervisor trap-vector-base-address）：保存发生 trap 时需要跳转到的地址。内核会将陷阱处理函数的地址写入该寄存器，每次发生 trap 时，CPU 会跳转到 stvec 的地址处执行陷阱处理函数。
2. sepc（supervisor exception program counter）：当 trap 发生时，CPU 会将此时 PC（program counter）的值保存在这里（因为 PC 随后会被 stvec 的值覆盖）。sret（return from trap）指令会将 sepc 的值写回 PC 中，从而恢复到之前的 PC 处继续执行（当然，内核也可以修改 sepc 的值来控制程序在 sret 后的返回位置）。
3. scause：发生 trap 时，RSIC-V CPU 会写入一个数字到 scause 寄存器来表示发生 trap 的原因。 
4. sscratch：陷阱处理程序使用 sscratch 来避免在保存用户寄存器之前覆盖用户寄存器。 
5. sstatus：状态寄存器，用于控制和跟踪 CPU 当前的状态。比如其中的 SIE 位可以控制设备中断是否使能，如果内核清除了 SIE，RISC-V 将推迟设备中断，直到内核设置了 SIE。SPP 位指示陷阱是来自用户模式还是监督模式，并控制 sret 返回到什么模式。

上述寄存器与在 supervisor 模式下处理的陷阱有关，user 模式下不能读写这些寄存器。在 machine 模式下处理的陷阱也有一组类似的控制寄存器；xv6只在计时器中断的特殊情况下使用它们。多核芯片上的每个 CPU 都有自己的这些寄存器集，并且在任何给定时间可能有多个CPU处理陷阱。

在有 trap 发生时，RISC-V CPU 硬件所执行的操作如下：

1. 如果发生的是设备中断，并且 sstatus 的 SIE 位没有被设置，则不执行下面的操作；
2. 清除 sstatus 的 SIE 位，从而禁用中断；
3. 将当前 PC 的值写入 sepc 中；
4. 保存当前的特权级别（用户模式或者监督模式）到 sstatus 的 SPP 位中，方便恢复；
5. 根据当前发生 trap 的原因来设置 scause 寄存器；
6. 将当前模式切换为监督模式（supervisor mode）;
7. 将 stvec 的值写入 PC；
8. 在新的 PC 处开始执行。 

要注意的是，在硬件阶段，CPU 不会切换当前页表到内核页面表，也不会切换到内核中的堆栈，也不会保存除 pc 之外的任何寄存器，这些任务由内核代码完成，这样做的好处是能够为软件提供灵活性。

2.2 来自用户空间的陷阱（Traps from user space ）

xv6 处理陷阱的方式取决于在内核中还是在用户代码中执行时发生陷阱。下面介绍来自用户空间的陷阱。

如果用户程序进行了系统调用（ecall指令），或执行了非法操作，或者设备中断，则在用户空间中执行时可能会发生 trap。若发生 trap，在 CPU 执行完硬件操作后，会跳转到 uservec（kernel/trampoline.S）处执行，然后再跳转到 usertrap（kernel/trap.c）；当返回时，会先调用 usertrapret (kernel/trap.c) 然后调用 userret (kernel/trampoline.S)。

对 xv6 的 trap 处理设计的一个主要限制是，RISC-V 硬件在处理陷阱时不会切换页表。这意味着 stvec 中的陷阱处理程序地址必须在用户页表中有一个有效的映射，因为这是在陷阱处理代码开始执行时有效的页表。此外，xv6的陷阱处理代码需要切换到内核页表；为了能够在切换之后继续执行，内核页表还必须具有stvec所指向的处理程序的映射。

xv6 使用了一个 trampoline 页面来满足这些要求。trampoline 页面包含 uservec，即 stvec 指向的trap 处理程序。trampoline 页面被映射到每个进程页表中的 TRAMPOLINE 地址上，它位于虚拟地址空间的顶部，trampoline 页面也被映射到内核页表中的 TRAMPOLINE 地址上。因为 trampoline 页面映射在用户页面表中，没有 PTE_U 标志，陷阱在监督模式下开始执行。因为 trampoline 页面被映射到内核虚拟地址空间中的相同地址上，所以 trap 处理程序在切换到内核页表后可以继续执行。

此处的 trap 处理程序在物理内存中只有一份，只是在每个进程创建的时候都会在其用户页表中建立从虚拟地址 TRAMPOLINE 到实际页面的映射（页表项），使得 PC 能通过用户页表访问 TRAMPOLINE 对应的 trap 处理程序，并且在内核页表中也存在从虚拟地址 TRAMPOLINE 到实际页面的映射（页表项），所以在切换到内核页表时可以继续执行 trap 处理程序。

uservec 陷阱处理程序的代码在 kernel/trampoline.S 中，当 uservec 开始执行时，需要保存当前进程的执行上下文，包括 32 个通用寄存器的值，以便在陷阱返回到用户空间时可以恢复它们，但此时已经没有多余的寄存器来保存存放这些值的内存起始地址的寄存器，这时候就可以使用之前提到的 sscratch 寄存器，先将 a0 寄存器的值暂时放到 sscratch 中，然后存放上下文的内存基地址（TRAPFRAME）放到 a0 中，接下来就将 32 个寄存器的值存入对应进程的 trapframe 结构体中。xv6 在每个进程中使用一页来存放 trapframe 结构体，地址为 TRAPFRAME，就在 TRAMPOLINE 的下面一页。在切换为内核页表之前，uservec 使用 TRAPFRAME 来访问该地址，在切换到内核页表后则使用进程的 p->trapframe 来访问。

trapframe 包含当前进程的内核栈地址（kernel_sp）、当前 CPU 的 hartid、usertrap 函数的地址（kernel_trap）以及内核页表的地址（kernel_satp）。uservec 检索这些值，将 satp 切换到内核页表，并调用 usertrap。

usertrap 函数要做的事情就是确定 trap 的原因，并处理它，然后返回。该函数会先修改 stvec 的值为 kernelvec，使得当在内核中发生了 trap 的时候会调用 kernelvec 而不是 uservec；然后保存当前 sepc 的内容，因为 usertrap 可能会调用 yield 来切换到另一个进程的内核线程，而该进程可能会返回到用户空间，在此过程中它可能会修改 sepc；然后根据 scause 的值判断 trap 的类型，如果是系统调用，则执行 syscall() 函数，如果是设备中断， 则执行 devintr()，其他情况则判断为异常，内核会 kill 当前异常进程；最后如果是定时器中断则让出 CPU，然后调用 usertrapret。

usertrapret 函数内会设置 trapframe 以及设置一些控制寄存器，然后调用 trampoline.S 中的 userret 函数，并且将用户页表地址 satp 作为参数传入。

userret 函数先切换当前内核页表为用户进程页表，然后恢复进程的上下文（在 uservec 中保存的寄存器），最终执行 sret 返回到用户空间。

2.3 来自内核空间的陷阱（Traps from kernel space）

不同于用户空间的 trap，在内核空间的时候发生 trap，stvec 指向 kernelvec（kernel/kernelvec.S），所以会跳转到 kernelvec 处执行。kernelvec 保存当前执行的内核线程的寄存器到其内核栈上，返回时再恢复。                                                                     

2.4 写时拷贝（copy-on-write)

对于 xv6 中的 fork 系统调用来说，每次都会复制父进程的所有内存空间以及页表，但由于大多数 fork 系统调用都会接着 exec 系统调用，在 exec 中会重新创建进程的内存地址空间，并且释放之前由 fork 系统调用拷贝的空间，所以导致效率十分低下，这时候就提出了写时拷贝（copy-on-write），就是在调用 fork 系统调用时不拷贝父进程的内存空间，此时父进程和子进程共享内存空间，当子进程要往内存中写数据的时候再进行拷贝，这样当 fork 后面紧接着 exec 系统调用时，就可以剩下拷贝父进程内存空间的时间。

2.5  懒分配（lazy allocation）

当应用程序通过调用 sbrk 请求更多内存时，内核会注意到大小的增加，但不分配物理内存，也不会为新的虚拟地址范围创建 pte。一旦程序使用这段地址引起页故障时，内核才会分配一个物理内存页面，并将其映射到页表中。这样的话，应用程序不使用的部分就不会加载到内存中。但频繁的发生页故障也会增加内核和用户切换的开销，操作系统可以通过为每个页故障分配一批连续的页面，而不是一个页面来降低这个成本。

2.6 需求分页（demand paging）

对于 xv6 来说，exec 系统调用会将整个文件装载进内存，但这样效率太过于低下，并且不一定会用到文件的所有部分，需求分页（demand paging）就能很好地解决这个问题，需求分页只会将要用到的页面装载进来，遇到没装载的页面会引发一个页故障（page fault）来装载页面。

挑战：当文件大小大于物理内存空间大小怎么办？使用大于物理内存的虚拟地址空间。

使用大于物理内存的虚拟地址空间必然会涉及到页替换，这时候引入了最近最少使用算法（least-recently used (LRU)），这个算法会使用到前面的 access 位。

2.7 内存映射文件（memory-mapped files）

能够使用 load 和 store 来访问文件，能够读写文件的一部分。Unix 使用一个系统调用来实现：

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

内核装载文件需要的页面，当内存满了的时候，换出使用频率最少的页面。

2.8 页故障（page fault）

页故障一般发生在如下几种情况：

1. 使用了页表中没有映射的页面；
2. 用户使用了其没有权限访问的页面（没有 PTE_U）；
3. 使用了页面不允许了操作（PTE_R, PTE_W, PTE_X）;

RISC-V 区分了三种页面错误： load page fault（当加载指令无法转换其虚拟地址时）、store page fault（当存储指令无法转换其虚拟地址时）和 instruction page fault（当程序计数器中的地址无法转换时）。scause 寄存器指示页面故障的类型，而 stval 寄存器包含无法转换的地址。

三、Lab traps: Traps

在开始本实验之前，请阅读 xv6 book 的第四章，并且阅读如下源码：

kernel/trampoline.S：用户空间切换到内核空间和返回的相关汇编代码；

kernel/trap.c：处理所有中断的代码；

3.1 RISC-V assembly (easy)

执行 make fs.img，在 user 目录下会生成 call.c 的汇编指令 call.asm，此部分要求阅读 call.asm 的 riscv 汇编，回答如下问题：

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

在函数调用中，函数的参数一般存放到寄存器 a0~a7 中，如果超出的这些寄存器的存放范围，则会将多余的参数存入栈中。在 call.c 的 main 函数调用 printf("%d %d\n", f(8)+1, 13); 时，13 存放在 a2 中。

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.)

可以看到， 在 riscv 汇编中，编译器直接计算出了 f(8)+1 的结果（12），没有函数调用过程。

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? 

使用 GDB 调试可以看到在跳转到 printf 函数后，ra 的内容为 0x38，即 jalr 的下一条指令。

5. 大端小端没有谁优谁劣，各自优势便是对方劣势：

小端模式 ：强制转换数据不需要调整字节内容，1、2、4字节的存储方式一样。
大端模式 ：符号位的判定固定为第一个字节，容易判断正负。

3.2 Backtrace (moderate)

函数调用时，栈的视图如下： 

 

可以看到 fp 指针的下面 8 字节偏移为 ra 的值，往下 16 字节偏移为上一个 fp 的值。

而本部分就是要实现一个函数 backtrace，该函数能打印当前函数之前的函数调用列表。

实现：

在 kernel/defs.h 中添加 backtrace 函数的原型：

在 kernel/riscv.h 中实现读取 fp (s0) 寄存器的函数: 

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

最后再到 kernel/printf.c 中实现 backtrace 函数:

void backtrace()
{
  uint64 fp = r_fp();
  uint64 pre_fp = *(uint64 *)(fp - 16);
  uint64 ra = *(uint64 *)(fp - 8);
  printf("%p\n", ra);

  while(PGROUNDDOWN(fp) == PGROUNDDOWN(pre_fp))
  {
    fp = pre_fp;
    pre_fp = *(uint64 *)(fp - 16);
    ra = *(uint64 *)(fp - 8);
    printf("%p\n", ra);
  }
}

然后在 sys_sleep 中调用 backtrace，在 qemu 中执行 bttest 打印内容如下：

同时，在 panic 函数里面调用 backtrace 能够系统每次 panic 都能打印出调用地址列表，方便我们调试。 

3.3 Alarm (hard)

此部分要实现一个 sigalarm(n, fn) 函数，作用是进程每消耗 n 个 cpu tick，就会执行 fn 函数，执行完 fn 函数后，进程继续返回之前执行位置继续执行。当程序调用 sigalarm(0, 0) 时，就停止这个功能。

实现：

在 Makefile 中加入 alarmtest.c。

在 user/user.h 中添加系统调用的原型：

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

在 user/usys.pl 中添加如下内容：

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

在 kernel/syscall.h 中添加系统调用号：

#define SYS_sigalarm  22
#define SYS_sigreturn 23

在 kernel/syscall.c 中添加系统函数声明：

extern uint64 sys_sigalarm(void);
extern uint64 sys_sigreturn(void);

[SYS_sigalarm]  sys_sigalarm,
[SYS_sigreturn] sys_sigreturn,

在 struct proc 结构体（kernel/proc.h）中添加几个成员，其中 ticks 为初始 sigalarm 设置的 tick，handler 为函数指针，remain_ticks 表示自调用 sigalarm 后剩余的 ticks，alarm_frame 用来保存一些寄存器使得在调用 sigreturn 后能恢复 trapframe；inalarm 防止重复进入 handler 函数。

int ticks;
void (*handler)();
int remain_ticks;
struct trapframe *alarmframe;
int inalarm;

在 kernel/proc.c 的 allocproc() 函数中初始化这三个参数：

p->ticks = 0;
p->handler = 0;
p->remain_ticks = 0;
p->inalarm = 0;
if((p->alarmframe = (struct trapframe *)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
}

在 freeproc() 函数中要释放 alarmframe 的页面：

if(p->alarmframe)
    kfree((void*)p->alarmframe);
p->alarmframe = 0;

在 kernel/sysproc.c 中实现这两个系统函数：

uint64 sys_sigalarm(void)
{
  int ticks;
  uint64 handler;
  argint(0, &ticks);
  argaddr(1, &handler);

  struct proc *p = myproc();
  p->ticks = ticks;
  p->handler = (void (*)())handler;
  p->remain_ticks = ticks;

  return 0;
}

uint64 sys_sigreturn(void)
{
  struct proc *p = myproc();
  *p->trapframe = *p->alarmframe;
  p->inalarm = 0;
  return p->trapframe->a0;
}

 在 kernel/trap.c 的 usertarp() 函数中，每次遇到时钟中断就执行如下内容：

// give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
  {
    if(p->inalarm == 0 && p->ticks != 0 && p->remain_ticks != 0)
    {
      p->remain_ticks--;
      if(p->remain_ticks == 0)
      {
        *p->alarmframe = *p->trapframe;
        p->inalarm = 1;
        p->trapframe->epc = (uint64)p->handler;
        p->remain_ticks = p->ticks;
      }
    }
    yield();
  }

最后成功通过测验：