操作系统MIT 6.S081 xv6内核（五）：Traps实验

RISC-V assembly实验

没有实验，回答问题

阅读call.asm中函数g、f和main的代码：

1. 哪些寄存器保存函数的参数？例如，在main对printf的调用中，哪个寄存器保存13？

• 答：函数参数从a0到a7存储，13是第三个参数，所以是a2保存；

2. main的汇编代码中对函数f的调用在哪里？对g的调用在哪里（提示：编译器可能会将函数内联）

• 答：提示已经给出答案，汇编代码的sp没有变动，也没有存入ra，说明没有进行函数调用，f8已经被函数内联优化并且提前算出答案11了，这一行调用就是打印12、13；

3. printf函数位于哪个地址？ 调用位置在

   30:   00000097            auipc   ra,0x0
   34:   5e6080e7            jalr    1510(ra) # 616 <printf>

• 答：存入pc0x30到ra，1510的16进制对应0x5e6，所以跳转地址是二者相加0x616；

4. 在main中printf的jalr之后的寄存器ra中有什么值？

• 答：0x38,寄存器存储返回PC地址执行下一条指令pc；

5. 运行以下代码：

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

   程序的输出是什么？这是将字节映射到字符的ASCII码表。如果RISC-V是大端存储，为了得到相同的输出，你会把i设置成什么？是否需要将57616更改为其他值？

• 答：%x打印16进制，即e110；一个16进制数的一位是4位，存储单元可以存储2个数字;RISCV采用小端存储，所以高到低址存储的是72，6c，64；十进制114，108，100，对应ASCII r l d，所以打印结果"He110 World";(存数据的是栈结构，小端就是先存不重要的高位，所以72最后存，最早取（猜的）)；

• %x代表16进制解析，这种情况下值的解析不会单独对某个字节进行，无论是大端还是小端存储，都是将其拼接再转换成16进制。（内存的存储分大小端，但是原字节序是不会变的），因此57616不应该变；

• 如果是大端存储，为了得到同样结果，72代表r需要最后存，最早取，大端先存低位，所以就是0x726c64；

6. 在下代码printf("x=%d y=%d", 3)中，“y=”之后将打印什么(注：答案不是一个特定的值)？为什么会发生这种情况？

• 答：x=3，y出现未定义行为，可能是栈中残存数据，或者未初始化的空间；

Backtrace 实验

实验目的

实际上本节就是模拟gdb的bt功能，例如运行到某个函数，想知道这个函数是哪些函数调用来的，换句话说，该函数运行完成应该返回到哪些函数，就是backtrace；所以目的是实现一个backtrace函数，使得系统调用sys_sleep时会打印函数调用的返回地址；使用命令bttest会触发sys_sleep，只需要在sys_sleep中调用函数backtrace即可。

这是使用bttest命令效果：

backtrace:
0x0000000080002cda
0x0000000080002bb6
0x0000000080002898

xv6还提供了一种工具验证上面的16进制地址是有效的，运行

riscv64-unknown-elf-addr2line -e kernel/kernel

将上述地址键入会得到对应的调用位置：

kernel/sysproc.c:74
kernel/syscall.c:224
kernel/trap.c:85

backtrace建议定义在kernel/printf.c文件；

具体实现

要实现查看函数调用地址，目前了解的方法只有一种：通过查看fp寄存器；从基础理论一文（RISCV栈部分）提到，RISCV函数调用就会生成新的StackFrame，其中fp指针指向栈底，这指针能索取到两个重要对象，一个是当前函数的返回地址RA（8个字节），也就是我们要打印的东西；一个是上一个函数的fp（8个字节）；

读取fp需要C语言内嵌汇编，已经给出，我们只需要添加到kernel/riscv.h即可：

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

然后就是在kernel/printf.c实现backtrace，直接看代码：首先通过r_fp获取当前页帧的fp即cur_frame，进入循环，cur_frame指向的是栈顶，而且地址向低延伸；因此cur_frame-1是为了得到fp的下一个指针，这里指向的是RA，也即返回地址，也就是上一个函数的地址解引用打印地址即可；cur_frame-2指针指向的是上一个StackFrame的fp，把他赋给cur_frame即可；因此循环退出条件就是上一个Stack Frame是存在的，如果不存在，说明cur_frame不会处于页帧中间，所以另一个判断方法可以是：PGROUNDDOWN((uint64)cur_frame)！=PGROUNDDOWN((uint64)cur_frame)则继续循环；

还有一些有趣的细节在注释提到。

void backtrace(void){
    printf("backtrace:\n");
  uint64 *cur_frame=(uint64*)r_fp(); //读取当前fp，uint64转uint64*转换成地址指针（这种转换是将一个无意义的uint64变成一个有意义的地址值，是合法的）
    //但是比较时又转换为uint64进行大小比较，另一种方法是对PGROUNDDOWN、PGROUNDUP强转uint64*比较
  while((uint64)cur_frame>PGROUNDDOWN((uint64)cur_frame)&&(uint64)cur_frame<PGROUNDUP((uint64)cur_frame)){
    printf("%p\n",*(cur_frame-1));
    cur_frame=(uint64*)(*(cur_frame-2));
  }
}

最后在sys_sleep添加调用、在kernel/defs.h添加函数声明即可；

完整Commit:Backtrace Done

Alarm实验

实验目的

本节实验是比较综合的实验，融合了syscalls、pagetable、traps三部分内容，但就步骤难度而言不是很大，就是第一次看到题目有点懵。本节实验旨在实现一个"警报"功能，具体而言，用户进程调用一个系统调用sigalarm(n,handler)，意味这进程每消耗n ticks（tick是时钟中断产生的单位时间，时间长短取决于时钟的设计），就会跳转到handler函数执行；特殊的，如果调用sigalarm(0,0),则代表取消该进程的alarm功能；另外，如果要从调用返回到原始的用户代码，需要使用另一个系统调用sigreturn函数。

实验的验证来自一个用户文件的测试代码user/alarmtest，测试函数有三个，对应了三个重点测试的地方。

test0用于判断系统调用能否正常调用sigalarm(n,handler)，并且能否在n ticks跳转到handler执行代码；为后续实现铺垫一下思路：sigalarm(2, periodic)调用是经过2 ticks执行periodic，如何计时这2 ticks的时间呢，答案就是在时间中断中判断，在基础理论中提到trap处理系统调用、时间中断、设备中断的代码在kernel/trap.c；每次中断经过的时间是tick，那么只需要在进程中增加一个计数变量，每达tick该变量++，只要变量大于2就跳转到periodic函数，因此进程还需要另一个字段来记录要跳转到哪个函数，通过函数指针来记录即可。

void
periodic()
{
  count = count + 1;  //递增
  printf("alarm!\n");
  sigreturn();  //从调用返回
}

// tests whether the kernel calls
// the alarm handler even a single time.
void
test0()
{
  int i;
  printf("test0 start\n");
  count = 0;
  sigalarm(2, periodic);  //设置每个2ticks触发一次periodic函数
  for(i = 0; i < 1000*500000; i++){ //CPU频率很快，单个tick时间内i可能已经叠加了几百万了，因此循环要那么大
    if((i % 1000000) == 0)  //每达一百万就打印
      write(2, ".", 1); //向stdout输出单个"."
    if(count > 0)  //periodic被调用就退出
      break;
  }
  sigalarm(0, 0);  //进程取消Alarm功能
  if(count > 0){   //判断是否调用过periodic
    printf("test0 passed\n");
  } else {
    printf("\ntest0 failed: the kernel never called the alarm handler\n");
  }
}

test1用于测试sigreturn能否返回到用户代码，确保调用sigreturn从断点执行的代码仍然是连续的。__attribute__ ((noinline))是gcc的属性声明，为了保证j只能通过函数调用改变值，i通过循环递增，正常情况下i递增，调用foo导致j也递增，因为调用了sigalarm(2,periodic)，所以很有可能某个时间点进入循环、未来得及调用foo情况下进入内核执行periodic（因为count=10，10次调用很难避免这种情况），如果返回时不是原来断点的位置，那么i和j不会相等，就可以判断返回函数sigreturn的设计是失败的。换言之，如果断点和返回是成功的，那么就算执行了periodic也能继续执行foo，那么i和j就是一致的。

void __attribute__ ((noinline)) foo(int i, int *j) { //noinline 属性告诉编译器不要将这个函数内联展开，即使在优化时也应该保持它作为一个独立的函数，也即保证只有发生函数调用才能改变里面的变量，不受编译器内联影响
  if((i % 2500000) == 0) {  //i每达250w就输出一个"."
    write(2, ".", 1);    //打印不是重点，只是为了简单标识i的变化
  }
  *j += 1; //每次调用foo函数j指针指向的整型变量+1
}

//
// tests that the kernel calls the handler multiple times.
//
// tests that, when the handler returns, it returns to
// the point in the program where the timer interrupt
// occurred, with all registers holding the same values they
// held when the interrupt occurred.
//
void
test1()
{
  int i;
  int j;

  printf("test1 start\n");
  count = 0;
  j = 0;
  sigalarm(2, periodic);
  for(i = 0; i < 500000000; i++){
    if(count >= 10)  //测试10次调用是否都能够返回正确的断点
      break;
    foo(i, &j);
  }
  if(count < 10){  //系统调用存在问题，调用没有足够的count递增
    printf("\ntest1 failed: too few calls to the handler\n");
  } else if(i != j){  //断点保存不当、返回位置不对，就会导致i!=j
    // the loop should have called foo() i times, and foo() should
    // have incremented j once per call, so j should equal i.
    // once possible source of errors is that the handler may
    // return somewhere other than where the timer interrupt
    // occurred; another is that that registers may not be
    // restored correctly, causing i or j or the address ofj
    // to get an incorrect value.
    printf("\ntest1 failed: foo() executed fewer times than it was called\n");
  } else {
    printf("test1 passed\n");
  }
}

test2是考虑一种特殊情况：用户进程处理系统调用sigalarm(2, slow_handler)跳转到slow_handler时，需要花费时间来处理slow_handler，这个时间sigalarm(2, slow_handler)可能会重复触发，这是实验不允许的，因为xv6没有足够完善的机制足够处理这种嵌套的中断，因此test2需要判断代码是否阻止了这种重复触发。

void
slow_handler()
{
  count++;
  printf("alarm!\n");
  if (count > 1) {  //重复陷入发生，实验失败
    printf("test2 failed: alarm handler called more than once\n");
    exit(1);
  } 
  for (int i = 0; i < 1000*500000; i++) {  //设置一个足够长的循环，使得用户进程有时间到达2tick以测试是否重复陷入
    asm volatile("nop"); //防止循环被编译器优化不执行，加一个汇编代码
  }
  sigalarm(0, 0);
  sigreturn();  
}

//
// tests that kernel does not allow reentrant alarm calls.
void
test2()
{
  int i;
  int pid;
  int status;

  printf("test2 start\n");
  if ((pid = fork()) < 0) {
    printf("test2: fork failed\n");
  }
  if (pid == 0) { //子进程
    count = 0;
    sigalarm(2, slow_handler); //设置Alarm
    for(i = 0; i < 1000*500000; i++){
      if((i % 1000000) == 0)
        write(2, ".", 1);
      if(count > 0)
        break;
    }
    if (count == 0) {  //系统调用出错，没有调用成功
      printf("\ntest2 failed: alarm not called\n");
      exit(1);
    }
    exit(0);
  }

  //父进程
  wait(&status);
  if (status == 0) {
    printf("test2 passed\n");
  }
}

具体实现

1. 第一步先把系统调用设置好，使得编译能够通过，和syscalls实验步骤基本一致。

   Makefile添加$U/_alarmtest\

   user/usys.pl脚本添加系统调用入口

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

   kernel/syscall.c添加声明和系统调用号

   extern uint64 sys_sigalarm(void);
   extern uint64 sys_sigreturn(void);
   [SYS_sigalarm] sys_sigalarm,
   [SYS_sigreturn] sys_sigreturn

   kernel/syscall.h定义调用号:

   #define SYS_sigalarm 22
   #define SYS_sigreturn 23

   两个系统调用函数定义在kernel/sysproc.c，这里先用return 0占坑，后面再写；

   uint64 sys_sigalarm(void){
     return 0;
   }
   uint64 sys_sigreturn(void){
     return 0;
   }

   alarmtest使用了系统调用的用户接口函数sigalarm和sigreturn，需要在user/user.h进行声明:

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

   至此，make qemu就可以通过编译并且启动系统了，然后需要对进程新增字段来辅助进行计时和函数跳转。

2. 进程新增字段

   kernel/proc.h中proc结构体中添加，表示经过ticks_num就跳转到函数alarm_handler，ticks_lastime持续计数，判断ticks_lastime是否到达ticks_num；

   uint64 ticks_num;  //能够跳转的ticks数目
   void (*alarm_handler)(void); //跳转的函数
   uint64 ticks_lastime;  //已经经过了多少ticks

   新增了字段，就要对进程的分配、回收的函数进行相应的处理： kernel/proc.c中allocproc函数和freeproc函数新增字段初始化：xv6不支持NULL，因此函数指针也是置0即可。

   p->ticks_num=0;
   p->alarm_handler=0;
   p->ticks_lastime=0;

   至此，每个进程初始化、回收都能够正确对新增字段进行配置，接下啦就是如何使用这些字段实现计算和函数跳转、返回了，这里先讨论如何实现计时和跳转。

3. 函数计时和跳转 首先要使用系统调用kernel/sysproc.c中的sys_sigalarm接收用户接口传递过来的变量，也就是我们之前实验的argint和argaddr函数，并且设置到进程变量：

   uint64 sys_sigalarm(void){
     int ticks_num;
     uint64 alarm_handler;
     if(argint(0,&ticks_num)<0) //sigalarm(n,handler)第1个参数n
       return -1;
     if(argaddr(1,&alarm_handler)<0){  //第2个参数handler
          return -1;
     }
     struct proc *p = myproc(); 
     p->ticks_num=ticks_num;  //设置变量
     p->alarm_handler=(void*)alarm_handler;
     p->ticks_lastime=0;  //未开始计数记0
     return 0;
   }

   随机就是利用这些参数计时和跳转了，从kernel/trap.c的时钟中断入手，通过进程变量ticks_lastime进行tick的计数，到达ticks_num跳转到alarm_handler，跳转的实现依赖于p->trapframe->epc，在基础理论一文提到，当异常发生时，sepc寄存器会存储用户恢复执行时的第一条指令，随后sepc会软件存储到p->trapframe，随机页表被内核替换，恢复执行时会从p->trapframe->epc重新装载sepc寄存器，用户指令从这里开始执行。

   if(which_dev == 2){ //代表时钟中断
     //yield();
     if(p->ticks_num>p->ticks_lastime)  //如果ticks_lastime没有到达p->ticks_num
       p->ticks_lastime++;  //递增
     else if(p->ticks_num==p->ticks_lastime){  //如果到达p->ticks_num
       p->ticks_lastime=0;  //下次重新计数
       p->trapframe->epc=(uint64)p->alarm_handler; //恢复执行跳转到p->alarm_handler
     } 
     else{
       yield();  //好像也没什么情况了，为了完整性，放弃cpu
     }     
   }

   至此，系统能完成sigalarm的调用，并且跳转到进程函数执行，使用alarmtest能够pass test0，但是这里我们也发现了问题，我们用函数地址直接覆盖p->trapframe->epc，原来的用户epc就找不到了，所以test1和test2返回时都会导致内核崩溃，这是合理的情况，所以接下来开始写sigreturn。

4. 在这里我们还需要增加两个字段，一个是用于备份用户trapframe的alarm_savetrapframe和防止从用户空间重复系统调用导致冲突的alarming_flag，从前面的描述这两个变量的存在理解起来应该是理所当然的。 kernel/proc.h添加：

   struct trapframe *alarm_savetrapframe;
   int alarming_flag; //标记是否alrming

   同理需要在allocproc和freeproc进行配置，仿照trapframe变量的分配和回收即可：

   //allocproc函数
   if((p->alarm_savetrapframe = (struct trapframe *)kalloc()) == 0){
       release(&p->lock);
       return 0;   
     }
   p->alarming_flag=0;
   
   //freeproc函数
   if(p->alarm_savetrapframe)
     kfree((void*)p->alarm_savetrapframe);
   p->alarm_savetrapframe = 0;
   p->alarming_flag=0;

   然后就是它们的使用了，问题在于在哪里进行备份和恢复呢？答案是在epc覆盖前备份，在sigreturn就恢复，这容易理解，不覆盖就没必要备份，不返回就没必要恢复。在下面的时间中断代码有几个语法细节，这里使用结构体指针trapframe解引用得到结构体成员（主要是31个用户寄存器值，具体寄存器查看基础理论一文）进行复制，也可以使用memmove将整块结构体内存复制，但注意正确大小是sizeof(struct trapframe)，我一开始使用p->trapframe实际上是指针大小就导致复制错误，要么使用sizeof(*p->trapframe)或者sizeof(struct trapframe)，不要踩坑。

   这里还定义了alarming_flag，如果epc一旦指定，该进程的跳转地址就确定，并且alarming_flag=1锁定，即使经过2 ticks也不会重复计数和重置用户的trapframe。

   if(which_dev == 2){
       //yield();
     if(p->ticks_num>p->ticks_lastime)
       p->ticks_lastime++;  //同前
     if(p->ticks_num==p->ticks_lastime&&p->alarming_flag==0){
       p->ticks_lastime=0;
       *p->alarm_savetrapframe=*p->trapframe; //新增：备份用户trapframe
       //memmove(p->alarm_savetrapframe,p->trapframe,sizeof(struct trapframe));
       p->trapframe->epc=(uint64)p->alarm_handler;
       p->alarming_flag=1;
     } 
     else{
       yield();
     }      
   }

   核心部分已经介绍差不多了，接下啦就是通过kernel/sysproc.c中的sigreturn恢复用户trapframe：将备份的alarm_savetrapframe重新复制到trapframe即可，这里隐藏一些寄存器细节，例如核心的epc也被重置为原始用户的断点，因此能够返回来用户函数执行。

   uint64 sys_sigreturn(void){
     struct proc *p = myproc();
     //memmove(p->trapframe,p->alarm_savetrapframe,sizeof(struct trapframe));
     *p->trapframe=*p->alarm_savetrapframe;
     p->alarming_flag=0;
     return 0;
   }

   至此，整个lab就做完了，使用alarmtest可以通过三个测试，这时候还需要尝试运行usertests，查看我们的修改是否对其他进程造成了影响，一般而言只要成功配置了进程的分配、回收就能通过；应当指出的是xv6是一个简化的系统，它的内存分配、命令鲁棒性、性能还不是很强大（在后面的实验也会引入一些有趣的策略加以改善），因此也有很大可能不会通过usertests，可能需要多试几次，并且观察是否反复卡在某个test，如果反复卡在某个test，那的确需要review一下代码看看是否有误操作；反之如果是偶有几个test出错是正常的，因为如果有命令失败就会导致failed，多尝试几次可能就pass all了。

使用命令：

make grade

完整commit参考：Alarm Done