trap执行流程

1. write通过执行ECALL指令来执行系统调用。ECALL指令会切换到具有supervisor mode的内核中。
2. 内核中执行的第一个指令是一个由汇编语言写的函数，叫做uservec。
3. 在这个汇编函数中，代码执行跳转到了由C语言实现的函数usertrap中，这个函数在trap.c中。
4. 在usertrap这个C函数中，我们执行了一个叫做syscall的函数。
5. 这个函数会在一个表单中，根据传入的代表系统调用的数字进行查找，并在内核中执行具体实现了系统调用功能的函数。对于我们来说，这个函数就是sys_write。
6. sys_write会将要显示数据输出到console上，当它完成了之后，它会返回给syscall函数,再返回给usertrap函数
7. usertrap()会调用一个函数叫做usertrapret，它也位于trap.c中，这个函数完成了部分方便在C代码中实现的返回到用户空间的工作
8. 汇编函数中会调用机器指令返回到用户空间，并且恢复ECALL之后的用户程序的执行

ecall 指令

我们是通过ecall走到trampoline page的，而ecall实际上只会改变三件事情：
第一，ecall将代码从user mode改到supervisor mode。
第二，ecall将程序计数器的值保存在了SEPC寄存器。我们可以通过打印程序计数器看到这里的效果，
第三，ecall会跳转到STVEC寄存器指向的指令。

接下来：

• 我们需要保存32个用户寄存器的内容，这样当我们想要恢复用户代码执行时，我们才能恢复这些寄存器的内容。
• 因为现在我们还在user page table，我们需要切换到kernel page table。
• 我们需要创建或者找到一个kernel stack，并将Stack Pointer寄存器的内容指向那个kernel stack。这样才能给C代码提供栈。
• 我们还需要跳转到内核中C代码的某些合理的位置。

uservec函数

为了能执行更新page table的指令，我们需要一些空闲的寄存器，这样我们才能先将page table的地址存在这些寄存器中，然后再执行修改SATP寄存器的指令。
对于保存用户寄存器，XV6在RISC-V上的实现包括了两个部分：
第一个部分是，XV6在每个user page table映射了trapframe page，这样每个进程都有自己的trapframe page。
trapframe page第一个数据保存了kernel page table地址，这将会是trap处理代码将要加载到SATP寄存器的数值。
第二部分是把trapframe page的地址加载到a0，也就是0x3fffffe000， 这是个常量。原来用户空间的A0会被写到sscratch这个寄存器中。所以，下面SD是存储质量，让每个寄存器被保存在了偏移量+a0的位置。

csrw sscratch, a0

li a0, TRAPFRAME
        
sd ra, 40(a0)
sd sp, 48(a0)
sd gp, 56(a0)

一直到

csrr t0, sscratch
sd t0, 112(a0)

把用户态原来A0寄存器的值，存到p->trapframe->a0中

ld sp, 8(a0)

这条指令正在将a0指向的内存地址往后数的第8个字节开始的数据加载到Stack Pointer寄存器。第8个字节开始的数据是内核的Stack Pointer（kernel_sp）。
trapframe中的kernel_sp是由kernel在进入用户空间之前就设置好的，它的值是这个进程的kernel stack

ld tp, 32(a0)

XV6会将CPU核的编号也就是hartid保存在tp寄存器, 这个寄存器表明当前运行在多核处理器的哪个核上

# load the address of usertrap(), from p->trapframe->kernel_trap
ld t0, 16(a0)

# fetch the kernel page table address, from p->trapframe->kernel_satp.
ld t1, 0(a0)

# install the kernel page table.
csrw satp, t1

上面3条指令执行完成之后，当前程序会从user page table切换到kernel page table。
最后一条指令是jr t0。执行了这条指令，我们就要从trampoline跳到内核的C代码中。这条指令的作用是跳转到t0指向的函数中。

usertrap函数

// 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();

1. 在内核中执行任何操作之前，usertrap中先将STVEC指向了kernelvec变量，这是内核空间trap处理代码的位置，而不是用户空间trap处理代码的位置。
2. 我们通过调用myproc函数来得到当前运行的是什么进程 。myproc函数实际上会查找一个根据当前CPU核的编号索引的数组，CPU核的编号是hartid，如果你还记得，我们之前在uservec函数中将它存在了tp寄存器
3. 我们要把SEPC寄存器中的用户程序计数器保存到进程的数据结构中

接下来我们需要找出我们现在会在usertrap函数的原因。根据触发trap的原因，RISC-V的SCAUSE寄存器会有不同的数字。数字8表明，我们现在在trap代码中是因为系统调用.

存储在SEPC寄存器中的程序计数器，是用户程序中触发trap的指令的地址。但是当我们恢复用户程序时，我们希望在下一条指令恢复，也就是ecall之后的一条指令。所以对于系统调用，我们对于保存的用户程序计数器加4，这样我们会在ecall的下一条指令恢复。

最后会进入usertrapret

usertrapret函数

它首先关闭了中断。我们之前在系统调用的过程中是打开了中断的，这里关闭中断是因为我们将要更新STVEC寄存器指向用户空间的trap代码，而之前在内核中的时候，我们指向的是内核空间的trap代码。

设置了STVEC寄存器指向user trampoline代码。 之前我们指向内核的代码，现在需要指回USER TRAP代码。

intr_off();

// send syscalls, interrupts, and exceptions to uservec in trampoline.S
uint64 trampoline_uservec = TRAMPOLINE + (uservec - trampoline);
w_stvec(trampoline_uservec);

下面把kernal要用到的一些变量写进trapframe。因为当用户态再次执行ECALL或中断时，还需要用这里的值去恢复。

  p->trapframe->kernel_satp = r_satp();         // kernel page table
  p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack
  p->trapframe->kernel_trap = (uint64)usertrap;
  p->trapframe->kernel_hartid = r_tp();         // hartid for cpuid()

接下来我们要设置SSTATUS寄存器，这是一个控制寄存器。这个寄存器的SPP bit位控制了sret指令的行为，该bit为0表示下次执行sret的时候，我们想要返回user mode而不是supervisor mode。这个寄存器的SPIE bit位控制了，在执行完sret之后，是否打开中断。因为我们在返回到用户空间之后，我们的确希望打开中断，所以这里将SPIE bit位设置为1。修改完这些bit位之后，我们会把新的值写回到SSTATUS寄存器。

  unsigned long x = r_sstatus();
  x &= ~SSTATUS_SPP; // clear SPP to 0 for user mode
  x |= SSTATUS_SPIE; // enable interrupts in user mode
  w_sstatus(x);

我们在trampoline代码的最后执行了sret指令。这条指令会将程序计数器设置成SEPC寄存器的值，所以现在我们将SEPC寄存器的值设置成之前保存的用户程序计数器的值。

  // set S Exception Program Counter to the saved user pc.
  w_sepc(p->trapframe->epc);

接下来，我们根据user page table地址生成相应的SATP值，这样我们在返回到用户空间的时候才能完成page table的切换。把它当作函数的第一参数传给一会的汇编。因为只有trampoline中代码是同时在用户和内核空间中映射。但是我们现在还没有在trampoline代码中，我们现在还在一个普通的C函数中，所以这里我们将page table指针准备好。这个参数会存在a0寄存器中

  // tell trampoline.S the user page table to switch to.
  uint64 satp = MAKE_SATP(p->pagetable);

倒数第二行的作用是计算出我们将要跳转到汇编代码的地址。我们期望跳转的地址是tampoline中的userret函数，这个函数包含了所有能将我们带回到用户空间的指令。
倒数第一行，将trampoline_userret指针作为一个函数指针，执行相应的函数（也就是userret函数）并传入参数，参数存储在a0寄存器中, 也就是page table指针。

uint64 trampoline_userret = TRAMPOLINE + (userret - trampoline);
  ((void (*)(uint64))trampoline_userret)(satp);

userret 函数

第一件事就是把之前a0存的pagetable指针放到satp寄存器中,随后把trapframe的地址放进a0;
csrw 用于将一个值写入到控制和状态寄存器（CSR）
li 用于将一个立即数（即直接编码在指令中的数值）加载到一个寄存器中

sfence.vma zero, zero
csrw satp, a0
sfence.vma zero, zero

li a0, TRAPFRAME

下面就是从TRAPFRAME开始恢复之前用户态的寄存器的值了.

最后我们把TRAPFRAME里存的函数返回值a0放进a0寄存器

# restore user a0
 ld a0, 112(a0)
        
# return to user mode and user pc.
# usertrapret() set up sstatus and sepc.
sret

sret是我们在kernel中的最后一条指令，当我执行完这条指令：
程序会切换回user mode
SEPC寄存器的数值会被拷贝到PC寄存器（程序计数器）
重新打开中断

利用虚拟内存可以做的有趣的事

虚拟内存有两个主要的优点

1. 隔离性。虚拟内存使得操作系统可以为每个应用程序提供属于它们自己的地址空间。所以一个应用程序不可能有意或者无意的修改另一个应用程序的内存数据。
2. 一层抽象.trampoline page，它使得内核可以将一个物理内存page映射到多个用户地址空间中。guard page，它同时在内核空间和用户空间用来保护Stack。

关键思想：在page fault时改变页表

通过page fault，内核可以更新page table，这是一个非常强大的功能.

什么样的信息对于page fault是必须的?

1. 出错的虚拟内存地址，或者是触发page fault的源
2. 出错的原因(存在SCAUSE寄存器中)

• 13表示是因为load引起的page fault；
• 15表示是因为store引起的page fault；

• 12表示是因为指令执行引起的page fault

  
  
  image.png

3. 引起page fault时的程序计数器值(tf->epc)
   这表明了page fault在用户空间发生的位置.因为在page fault handler中我们或许想要修复page table，并重新执行对应的指令。理想情况下，修复完page table之后，指令就可以无错误的运行了。

Lazy page allocation

image.png

在XV6中，sbrk的实现默认是eager allocation。这表示了，一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。设想自己写了一个应用程序，读取了一些输入然后通过一个矩阵进行一些运算。你需要为最坏的情况做准备，比如说为最大可能的矩阵分配内存，但是应用程序可能永远也用不上这些内存.使用虚拟内存和page fault handler，我们完全可以用某种更聪明的方法来解决这里的问题，这里就是利用lazy allocation.
sbrk系统调基本上不做任何事情，唯一需要做的事情就是提升p->sz.之后在某个时间点，应用程序使用到了新申请的那部分内存，这时会触发page fault，因为我们还没有将新的内存映射到page table。所以，如果我们解析一个大于旧的p->sz，但是又小于新的p->sz（注，也就是旧的p->sz + n）的虚拟地址，我们希望内核能够分配一个内存page，并且重新执行指令。

Zero Fill On Demand

当你查看一个用户程序的地址空间时，存在text区域，data区域，同时还有一个BSS区域（注，BSS区域包含了未被初始化或者初始化为0的全局或者静态变量）。当编译器在生成二进制文件时，编译器会填入这三个区域。text区域是程序的指令，data区域存放的是初始化了的全局变量，BSS包含了未被初始化或者初始化为0的全局变量。

我只需要分配一个page，这个page的内容全是0。然后将所有虚拟地址空间的全0的page都map到这一个物理page上。这样至少在程序启动的时候能节省大量的物理内存分配。

在写入时复制页面，并在应用地址空间中映射它为读/写

image.png

Copy On Write Fork

xv6 fork从父进程复制所有页面（参见fork()）;但fork经常紧接着执行exec, 就会直接丢弃那些复制了的页面.

解决方案是在父子进程之间共享地址空间,修改标志位为只读.

image.png

要写的时候,复制出来一份,2边都改成读写.

image.png

使用PTEs中额外可用的系统位（RSW）

当内核在管理这些page table时，对于copy-on-write相关的page，内核可以设置相应的bit位，这样当发生page fault时，我们可以发现如果copy-on-write bit位设置了，我们就可以执行相应的操作了。

需要对物理页面进行引用计数

父进程退出时我们需要更加的小心，因为我们要判断是否能立即释放相应的物理page。如果有子进程还在使用这些物理page,就不能释放.
困难重重: https://lwn.net/Articles/849638/

Demand Paging

程序的二进制文件可能非常的巨大，将它全部从磁盘加载到内存中将会是一个代价很高的操作。又或者data区域的大小远大于常见的场景所需要的大小，我们并不一定需要将整个二进制都加载到内存中。

按需从文件中加载页面

• 分配 page table entries，但将它们标记为on-demand
• 在错误时，从文件中读入page并更新pagetable
• 需要保留一些元信息，说明页面在磁盘上的位置
• 这些信息通常在称为virtual memory area（VMA）的结构中
• 如果文件大过物理内存, 把最远使用过的page置换进磁盘. the A(cess) bit 在PTE 帮助 kernel 实现 LRU.

Memory Mapped Files

将完整或者部分文件加载到内存中，这样就可以通过内存地址相关的load或者store指令来操纵文件.
为了支持这个功能，一个现代的操作系统会提供一个叫做mmap的系统调用。

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

下面开始讲解这次的LAB

Alarm

test 0的核心就是修改EPC.

EPC（Exception Program Counter）寄存器扮演着重要的角色，特别是在异常处理和中断处理中。EPC存储了发生异常或中断时程序的地址，这允许处理器在处理完异常或中断后返回到正确的位置继续执行程序。

p->trapframe->epc = (uint64)p->alarmhandler;

test1/2/3

what registers do you need to save and restore to resume the interrupted code correctly?

因为我们要再次回到最开始用户态执行的地方.中间我们跳到了用户态alarmhandler的地方.这里面的代码执行,会修改掉用户态的寄存器的值.所以我们需要把之前用户态的寄存器都要存下来.

*p->alarmtrapframe = *p->trapframe;

Prevent re-entrant calls to the handler
增加一个isalarming的状态,如果是true,就不做跳转

if (p->tickspassed >= p->alarminterval && !p->isalarming) {
....
}

Make sure to restore a0. sigreturn is a system call, and its return value is stored in a0
把之前在用户态保存下来的实际返回值,当作sys_sigreturn的返回值,就可以达到这个效果.

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

Print the names of the functions and line numbers in backtrace() instead of numerical addresses

核心思路: 首先修改make文件, 结合生成的asm文件提取所有命令的内存地址,然后调用addr2line 获得方法名 和 行号. 写进一个文件,并且让文件系统映射这个文件进xv6. 随后在内核启动的时候, 读取文件内容, 把地址和对应的方法名和行号,存进2个数组.
当调用backtrace() 函数的时候,可以用地址,在数组里做2分查找,找到对应的方法名和信息,就可以实现这个功能.

1699718206599.png

生成出来的文件大概长这样:

1699718241727.png

随后就是读取文件, 加载进数组. 我新建了一个debugtbl.c
这里用了一个缓存读文件的技巧,来减少readi的调用次数. 我是1次读了一个PGSIZE. 如果cache里还有行,就直接从cache里读出下一行.
2分查找的代码,是找到最大的小于等于当前输入地址的那个索引,随后去debugtbl_info 读取方法名和行号.

#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "param.h"
#include "stat.h"
#include "spinlock.h"
#include "proc.h"
#include "sleeplock.h"
#include "fs.h"
#include "buf.h"
#include "file.h"

#define MAX_LINE_LENGTH 96
#define MAX_ROW_LENGTH 4096
uint debugtbl_addr[MAX_ROW_LENGTH];
char debugtbl_info[MAX_ROW_LENGTH][MAX_LINE_LENGTH];
int debugtbl_row = 0;
char cache[PGSIZE];
int cache_idx = 0;
int cache_cnt = 0;


int readline(struct inode *ip, uint *off, char *buf) {
  int i = 0, n;
  while (i < MAX_LINE_LENGTH) {
    while (i < MAX_LINE_LENGTH && cache_cnt > cache_idx) {
      buf[i] = cache[cache_idx++];
      if (buf[i] == '\n') {
        buf[i] = 0;
        return i;
      }
      i++;
    }
    if (i == MAX_LINE_LENGTH) {
      panic("line char overflow");
      return -1;
    }
    n = readi(ip, 0, (uint64)cache, *off, PGSIZE);
    if (n <= 0) break; // Error or end of file
    *off += n;
    cache_cnt = n;
    cache_idx = 0;
  }
  
  return i; // Return the length of the line
}

int readfile(struct inode *ip) {
  uint off = 0; // Offset in the file
  int n;
  char buf[MAX_LINE_LENGTH];

  while ((n = readline(ip, &off, buf)) > 0) {
    uint addr = 0;
    if (n < 8) {
      panic("debugtbl format error");
    }
    for(int i = 0; i < 8; i++) {
      char c = buf[i];
      if (c >= '0' && c <= '9') c = c - '0';
      else if (c >= 'a' && c <= 'f') c = c - 'a' + 10;
      else panic("invalid address content");
      addr = (addr << 4) | c;
    }
    debugtbl_addr[debugtbl_row] = addr;
    memmove(debugtbl_info[debugtbl_row++], buf + 9, n); 
  }
  return n < 0 ? -1 : 0;
}

int initdebugtbl(){
    struct inode *ip;
    begin_op();
    if((ip = namei("/debugtbl")) == 0){
        end_op();
        return -1;
    }
    ilock(ip);
    if (readfile(ip) < 0)
    goto bad;
    iunlockput(ip);
  end_op();
  ip = 0;   
  return 0;
bad:
  if(ip){
    iunlockput(ip);
    end_op();
  }
  return -1;
}

int get_debuginfo(uint64 address) {
  uint left = 0;
  uint right = debugtbl_row - 1;
  while(left <= right){
      int mid = (left + right) >> 1;
      if(address < debugtbl_addr[mid]){
      right = mid - 1;
      }else{
      left = mid + 1;
      }
  }
  return left - 1;
}

void backtrace()
{
  int idx;
  printf("backtrace:\n");
  uint64 fp = r_fp(); // get the frame pointer value
  for (uint64 i = fp; PGROUNDDOWN(fp) == PGROUNDDOWN(i); i = *(uint64*)(i - 16)) {
    uint64 addr = *(uint64*)(i - 8);
    if ((idx = get_debuginfo(addr)) < 0)
      printf("%p\n", addr);
    else
      printf("%p %s\n", addr, debugtbl_info[idx]);
  }
}

这里关于initdebugtbl 什么时候去调用,我做了一些DEBUG. 一开始我是打算放在main.c中各种初始化时.但是发现始终不能work,根本原因时那时还没有进程的结构体维护在cpu, 第一个进程是在初始化完后,在scheduler()方法里 要去执行userinit被创建出来. 这里会切到用户态,然后调用exec的系统调用,去执行userinit命令.
那么我们可以在内核态的exec处,判断当前proc->pid是不是为1 (第一个进程), 是的话,就initdebugtbl; 来在内核态完成初始化debug table的工作.
随后exec userinit 后,创建出来的shell进程, pid为2了.

1699718737227.png

测试效果

1699718486261.png