[xv6]:trap

简介

xv6中的中断类型分为三种:
- 系统调用
  
  系统调用由ecall指令引发, 系统会由用户态陷入内核态(监管者模式, supervisor model)
- 异常
  
  异常通常是指用户或者内核做了一些不合法的事，如除以0或者使用无效虚拟地址
- 中断
  
  设备中断：当一个设备发出中断信号时，系统需要做出响应的响应
  
  时钟中断：当时钟发出中断时，就需要CPU放弃当前进程，重新调度
trap

在xv6中，统一将上面的三种中断称为trap, 以系统调用为例，当执行系统调用时，用户会由用户态进入到内核态，完成一些动作，然后返回，这个过程对于被中断的进程来说是透明的

四个阶段

xv6对于trap的处理通常分为四个阶段:
- 硬件自动处理
  
  当用户执行指令(如ecall)陷入trap时，硬件会自动的执行一些动作，通常是设置某些寄存器(如pc)的状态
- 进入汇编入口
  
  如上所说，陷入trap时pc的值可能会被置为某些特定寄存器的值，因此，在陷入中断之前，如果我们能够手动设置这些寄存器，那么当陷入中断时，就可以让程序跳转到指定的位置, 在xv6中，这个位置经常被设置为*.S文件中的某个label
  
  而在这些汇编入口中，可以执行一些预处理，如寄存器的保存，页表的切换等等
- 执行C处理程序
  
  通过跳转指令(jr), 可以从汇编入口跳转到对应的C处理程序，这些程序会对中断的类型进行更加精确的判断
- 执行系统调用或者设备驱动服务
  
  同样，这里也是更高层的C代码
其实还有第五个阶段，就是从中断中返回，同样，该过程需要做的就是恢复寄存器的值，切换页表，最后执行一条特殊的返回指令(如sret)真正地返回原状态

1. 内核Trap机制

之前说过，riscv中有三种模式: **M(机器模式), S(监管者模式), U(用户模式)**，在riscv中，当发生中断时，程序的控制权不会交给权限更低的模式, 因此，在S模式下发生的中断，永远不会交给U模式进行处理.

接下来将会介绍从U模式陷入S模式的相关机制

状态控制寄存器

当执行中断指令时，会有一些寄存器被自动的修改，其中，就包括了状态控制寄存器(CSR), 当陷入S模式时，硬件所做的操作如下

发生异常的指令的PC被存入sepc
scause被置为异常的类型
sstatus的SIE字段被置为0，用于关闭中断， sstaus的SPP字段被保存为中断发生前的模式
将模式转换为S
pc被设置为stvec
最后，执行新的pc

在上面的过程中，页表，即stap寄存器的值并没有改变，因此需要我们手动编码进行修改, 同时，用户的寄存器也没有保存，同样需要我们手动完成

2. 用户态->内核态

下面是xv6的源码分析, 仍然是以ecall指令为例

当执行ecall指令前，stvec的值为kernel/trampoline.S的uservec的地址

进程执行uservec段的汇编代码

uservec:    
	    # 该段为用户中断(ecall)的起始地址
        # 使用监管者模式，但是仍然使用用户的页表
        # trap.c sets stvec to point here, so
        # traps from user space start here,
        # in supervisor mode, but with a
        # user page table.
        #
        # sscratch points to where the process's p->trapframe is
        # mapped into user space, at TRAPFRAME.
        #
        
	   # swap a0 and sscratch
        # so that a0 is TRAPFRAME
        # 将TRAPFRAME的地址置于a0中，原a0寄存器的值写入到了sscratch寄存器中
        # 这里暂时借用了a0寄存器用做基址，存储TRAPFRAME
        csrrw a0, sscratch, a0

        # save the user registers in TRAPFRAME
        # 保存用户(Caller)寄存器
        # sd为存储双字(64bit)指令，ra --> ao + 40
        sd ra, 40(a0)
        sd sp, 48(a0)
        sd gp, 56(a0)
        sd tp, 64(a0)
        sd t0, 72(a0)
        sd t1, 80(a0)
        sd t2, 88(a0)
        sd s0, 96(a0)
        sd s1, 104(a0)
        sd a1, 120(a0)
        sd a2, 128(a0)
        sd a3, 136(a0)
        sd a4, 144(a0)
        sd a5, 152(a0)
        sd a6, 160(a0)
        sd a7, 168(a0)
        sd s2, 176(a0)
        sd s3, 184(a0)
        sd s4, 192(a0)
        sd s5, 200(a0)
        sd s6, 208(a0)
        sd s7, 216(a0)
        sd s8, 224(a0)
        sd s9, 232(a0)
        sd s10, 240(a0)
        sd s11, 248(a0)
        sd t3, 256(a0)
        sd t4, 264(a0)
        sd t5, 272(a0)
        sd t6, 280(a0)

	    # save the user a0 in p->trapframe->a0
        # 之前使用a0寄存器作为基址，现在将a0寄存器的原本值保存到trapframe中
        csrr t0, sscratch
        sd t0, 112(a0)
        
        # 下面这些操作会读取陷入监管者模式前用户的TRAPFRAME中的某些寄存器
        # restore kernel stack pointer from p->trapframe->kernel_sp
        # 读取sp
        ld sp, 8(a0)

        # make tp hold the current hartid, from p->trapframe->kernel_hartid
        # 读取tp, tp是线程id
        ld tp, 32(a0)

        # load the address of usertrap(), p->trapframe->kernel_trap
        # 读取TRAPFRAME中的usertrap()的地址 
        ld t0, 16(a0)

        # restore kernel page table from p->trapframe->kernel_satp
        # 从TRAPFRAME首部取出kernel page table, 然后将其置于satp
        # 此刻，进程使用的便是内核页表了
        ld t1, 0(a0)
        csrw satp, t1
        # sfence.vma 指令用于刷新TLB, 当两个参数均为x0(zero)的时候，就会刷新整个TLB表
        sfence.vma zero, zero

        # a0 is no longer valid, since the kernel page
        # table does not specially map p->tf.

        # jump to usertrap(), which does not return
        # 执行usertrap()
        jr t0

这里执行的操作包括: 保存用户寄存器, 切换用户页表为内核页表，读取sp指针, 最后跳转到usertrap函数, 该函数的地址保存在进程

TRAPFRAME + 16地址处

在这里可以看出，TRAPFRAME的作用就是在进行模式切换的时候，保存这些用户寄存器

程序来到trap.c, 执行usertrap()函数

void
usertrap(void)
{
  int which_dev = 0;

  // 当陷入trap进入监督者模式的时候，sstatus寄存器的SPP字段会保存
  // 陷入trap前的模式(硬件自动完成), 在这里检查其是否是从用户模式陷入的中断
  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.
  // 将stvec的值改为kernelvec 
  // 因为我们现在已经进入内核模式了，在内核模式陷入中断也会
  // 将PC的值指向stvec
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  // save user program counter.
  // 导致trap发生的指令(ecall)的PC会被置于sepc寄存器中
  // 在这里，将其置于进程的trapframe中
  p->trapframe->epc = r_sepc();
  
  // scause寄存器中会存储导致trap的类型
  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.
    // 这里很关键, epc在执行完ecall指令后会被置为ecall指令的地址，我们应该将其置为下一条指令的地址
    // 不然会陷入无限循环
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    // 在trampoline.S中保存完用户模式下的寄存器之后，就可以打开设备中断了
    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);

  // give up the CPU if this is a timer interrupt.
  // 软件中断
  if(which_dev == 2)
    yield();

  usertrapret();
}

在这里会执行一些检查操作，并且执行如下动作:

将stvec改为内核中断处理程序的地址，因为此时进程已经进入了内核态
将p->trapframe->epc置为ecall的下一条指令，在从中断返回时会跳转到该位置
打开中断，此时用户寄存器已经保存完毕，也切换为了内核页表，可以打开中断

再次之前，RISCV在进入trap的时候已经隐式地执行了关中断操作
执行系统调用
准备中断返回，执行uertrapret()中断返回程序

执行usertrapret(), 进行中断返回

void
usertrapret(void)
{
  struct proc *p = myproc();

  // we're about to switch the destination of traps from
  // kerneltrap() to usertrap(), so turn off interrupts until
  // we're back in user space, where usertrap() is correct.
  // 关中断
  intr_off();

  // send syscalls, interrupts, and exceptions to trampoline.S
  // 将stvec置为trampoline.S中的uservec
  w_stvec(TRAMPOLINE + (uservec - trampoline));

  // set up trapframe values that uservec will need when
  // the process next re-enters the kernel.
  // 保存进程的内核trapframe中的内核相关变量
  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()

  // set up the registers that trampoline.S's sret will use
  // to get to user space.
  // 从监管者模式中返回到用户模式需要执行sret指令
  // 该指令会将pc设置为spec, 将权限由监管者模式置为sstaus.ssp字段所规定的模式 
  // set S Previous Privilege mode to User.
  // 设置sstatus的ssp字段为用户模式
  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);

  // set S Exception Program Counter to the saved user pc.
  // ecall的下一条指令
  w_sepc(p->trapframe->epc);

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

  // jump to trampoline.S at the top of memory, which 
  // switches to the user page table, restores user registers,
  // and switches to user mode with sret.
  // fn是trampoline.S中userret处的地址
  uint64 fn = TRAMPOLINE + (userret - trampoline);
  // 该行的意思时，将fn解释成一个void (*)(uint64, uint64)类型的函数，然后以TRAPFRAME,
  // satp作为参数调用
  ((void (*)(uint64,uint64))fn)(TRAPFRAME, satp);
}

该函数中执行的操作包括:

关中断，因为接下来要修改寄存器的值
修改stvec, 使其恢复为trampoline.S中的uservec
修改spec, 将其置为p->trapframe-epc，即中断指令的下一条地址
修改sstatus的SPP字段，将其置为为用户模式
跳转到trampoline.S的userret

执行userret处的汇编代码

userret:
        # 该段指令负责将进程由监管者模式转换为用户模式
        # 具体工作包括:
        # 1. 恢复用户寄存器
        # 2. 从内核页表切换为用户页表
        # 3. 执行sret指令真正的返回, 该指令会修改sstaus, 以及pc
        # userret(TRAPFRAME, pagetable)
        # switch from kernel to user.
        # usertrapret() calls here.
        # a0: TRAPFRAME, in user page table.
        # a1: user page table, for satp.

        # switch to the user page table.
        # 切换用户页表
        csrw satp, a1
        sfence.vma zero, zero

        # put the saved user a0 in sscratch, so we
        # can swap it with our a0 (TRAPFRAME) in the last step.
        # 与之前保存时的动作对应
        ld t0, 112(a0)
        csrw sscratch, t0

        # restore all but a0 from TRAPFRAME
        ld ra, 40(a0)
        ld sp, 48(a0)
        ld gp, 56(a0)
        ld tp, 64(a0)
        ld t0, 72(a0)
        ld t1, 80(a0)
        ld t2, 88(a0)
        ld s0, 96(a0)
        ld s1, 104(a0)
        ld a1, 120(a0)
        ld a2, 128(a0)
        ld a3, 136(a0)
        ld a4, 144(a0)
        ld a5, 152(a0)
        ld a6, 160(a0)
        ld a7, 168(a0)
        ld s2, 176(a0)
        ld s3, 184(a0)
        ld s4, 192(a0)
        ld s5, 200(a0)
        ld s6, 208(a0)
        ld s7, 216(a0)
        ld s8, 224(a0)
        ld s9, 232(a0)
        ld s10, 240(a0)
        ld s11, 248(a0)
        ld t3, 256(a0)
        ld t4, 264(a0)
        ld t5, 272(a0)
        ld t6, 280(a0)

	    # restore user a0, and save TRAPFRAME in sscratch
        csrrw a0, sscratch, a0
        
        # return to user mode and user pc.
        # usertrapret() set up sstatus and sepc.
        # 真正的返回
        sret

该阶段所做的操作包括:

恢复用户寄存器
切换回用户页表
执行sret中断返回指令, 该指令会将pc置为spec, 将模式置为sstaus的SPP字段，即之前设置的用户模式

3. 内核中的trap

内核态的trap不会发生模式的转变，因此没有用户态的中断那么复杂

当trap发生在内核态时，我们不需要对 satp进行处理，因为不需要更换模式，也就不需要更改页表

这里只需要在该进程对应的内核栈中开辟一段新的frame，将这些值保存在当前内核栈上就行了

kernelvec.S

	#
        # interrupts and exceptions while in supervisor
        # mode come here.
        #
        # push all registers, call kerneltrap(), restore, return.
        #
        # 内核态下的中断处理
        # 当发生中断或异常时，只需要给当前的内核栈开辟新的空间(frame)
        # 然后保存当前的寄存器即可
        # 当中断处理结束，恢复寄存器，释放内核栈空间
.globl kerneltrap
.globl kernelvec
.align 4
kernelvec:
        // make room to save registers.
        // 在内核(监管者)模式下，如果发生中断，不需要更换页表操作
        addi sp, sp, -256

        // save the registers.
        sd ra, 0(sp)
        sd sp, 8(sp)
        sd gp, 16(sp)
        sd tp, 24(sp)
        sd t0, 32(sp)
        sd t1, 40(sp)
        sd t2, 48(sp)
        sd s0, 56(sp)
        sd s1, 64(sp)
        sd a0, 72(sp)
        sd a1, 80(sp)
        sd a2, 88(sp)
        sd a3, 96(sp)
        sd a4, 104(sp)
        sd a5, 112(sp)
        sd a6, 120(sp)
        sd a7, 128(sp)
        sd s2, 136(sp)
        sd s3, 144(sp)
        sd s4, 152(sp)
        sd s5, 160(sp)
        sd s6, 168(sp)
        sd s7, 176(sp)
        sd s8, 184(sp)
        sd s9, 192(sp)
        sd s10, 200(sp)
        sd s11, 208(sp)
        sd t3, 216(sp)
        sd t4, 224(sp)
        sd t5, 232(sp)
        sd t6, 240(sp)

	// call the C trap handler in trap.c
        call kerneltrap

        // restore registers.
        ld ra, 0(sp)
        ld sp, 8(sp)
        ld gp, 16(sp)
        // not this, in case we moved CPUs: ld tp, 24(sp)
        ld t0, 32(sp)
        ld t1, 40(sp)
        ld t2, 48(sp)
        ld s0, 56(sp)
        ld s1, 64(sp)
        ld a0, 72(sp)
        ld a1, 80(sp)
        ld a2, 88(sp)
        ld a3, 96(sp)
        ld a4, 104(sp)
        ld a5, 112(sp)
        ld a6, 120(sp)
        ld a7, 128(sp)
        ld s2, 136(sp)
        ld s3, 144(sp)
        ld s4, 152(sp)
        ld s5, 160(sp)
        ld s6, 168(sp)
        ld s7, 176(sp)
        ld s8, 184(sp)
        ld s9, 192(sp)
        ld s10, 200(sp)
        ld s11, 208(sp)
        ld t3, 216(sp)
        ld t4, 224(sp)
        ld t5, 232(sp)
        ld t6, 240(sp)

        addi sp, sp, 256

        // return to whatever we were doing in the kernel.
        sret

        #
        # machine-mode timer interrupt.
        #
.globl timervec
.align 4
timervec:
        # start.c has set up the memory that mscratch points to:
        # scratch[0,8,16] : register save area.
        # scratch[32] : address of CLINT's MTIMECMP register.
        # scratch[40] : desired interval between interrupts.
        
        csrrw a0, mscratch, a0
        sd a1, 0(a0)
        sd a2, 8(a0)
        sd a3, 16(a0)

        # schedule the next timer interrupt
        # by adding interval to mtimecmp.
        ld a1, 32(a0) # CLINT_MTIMECMP(hart)
        ld a2, 40(a0) # interval
        ld a3, 0(a1)
        add a3, a3, a2
        sd a3, 0(a1)

        # raise a supervisor software interrupt.
	li a1, 2
        csrw sip, a1

        ld a3, 16(a0)
        ld a2, 8(a0)
        ld a1, 0(a0)
        csrrw a0, mscratch, a0

        mret

内核trap处理程序只需要处理三种trap：

如果是硬件中断，就调用相应处理程序处理

如果是时钟中断(时钟中断属于硬件中断)，那么就让出处理器（由于调度给其它进程的时候，可能会导致新的traps, sepc 、sstatus寄存器可能被修改，因此最后要对其进行恢复)
如果是异常,那么xv6会并调用 panic终止执行

内核态陷阱处理完毕时，直接从frame中取出寄存器的值，然后删去之前在内核栈中开辟的空间

trap.c

void 
kerneltrap()
{
  int which_dev = 0;
  uint64 sepc = r_sepc();
  uint64 sstatus = r_sstatus();
  uint64 scause = r_scause();
  
  if((sstatus & SSTATUS_SPP) == 0)
    panic("kerneltrap: not from supervisor mode");
  if(intr_get() != 0)
    panic("kerneltrap: interrupts enabled");

  if((which_dev = devintr()) == 0){
    printf("scause %p\n", scause);
    printf("sepc=%p stval=%p\n", r_sepc(), r_stval());
    panic("kerneltrap");
  }

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2 && myproc() != 0 && myproc()->state == RUNNING)
    yield();

  // the yield() may have caused some traps to occur,
  // so restore trap registers for use by kernelvec.S's sepc instruction.
  w_sepc(sepc);
  w_sstatus(sstatus);
}

4. page fault 技巧

当CPU无法转换一个虚拟地址时，即相应的用户页表里没有这一项映射，或者相关权限要求不满足时，就会产生我们熟知的page fault根据执行指令的不同，缺页错误又可以细分为三种：

Load Page Faults：无法转换的虚拟地址位于一条加载（读）指令中。Scause：13
Store Page Faults：无法转换的虚拟地址位于一条存储（写）指令中。Scause：15
Instruction Page Faults：无法转换的虚拟地址位于一条执行指令中。Scause：12

RISC-V会将代表缺页错误类型的数字存放进scause寄存器中，同时将无法转换的虚拟地址存放在stval寄存器中

1. copy-on-write(COW)

使用场景

在程序中，当我们调用 fork创建一个子进程后，经常第一件事情就是调用 exec运行一些其他程序。这里看起来有点浪费，因为 fork创建了父进程page的完整的拷贝，而 exec做的第一件事情就是创造新的page, 然后释放这些拷贝而来的page
基本思想

与上面问题对应的优化则是：当我们创建子进程时，直接共享父进程的物理页

这里可以设置子进程的PTE指向父进程对应的物理页，然后将共享的页设置为read-only, 以确保隔离性

在某个时间点，当某个进程需要更改共享的内容时，我们会得到page fault, 此时内核将页错误相关的物理页拷贝到新分配的物理页中，并将新分配的物理页映射到发生异常的进程里，由于新分配的page现在仅对父/子进程可见，原page现在仅对子/父进程有效，因此，内核会自动将这些page设置为可读写
引用计数

当一个进程决定释放一个页或者结束本进程时，我们不能立即释放相应的物理页，因为可能还有其他进程也在使用这些物理页。所以我们需要对于每一个物理页的引用进行计数，当某个进程释放一个物理页时，我们将物理页的引用数减1。如果引用数等于0，那么我们才真正去释放物理页

2. zero fill on demand

当编译器在生成二进制文件时，会向BSS区填写未被初始化或者初始化为0的全局变量。但其实这里的BSS区域特别浪费空间：假如在C语言中定义了一个特别大的矩阵作为全局变量，它的元素初始值都是0，那么我们没有必要为这个矩阵所有元素分配空间，只需要记住这个矩阵的内容是0就行。

具体的操作就是在物理内存中，我们只分配一个内容全是0的页。然后将所有虚拟地址空间中存储值全为0的页都映射到这一个物理页上，并抹去映射中 PTE_W相关的flag标记

之后在某个时间点，应用程序尝试写BSS中的一个页时，就会得到page fault，进入陷阱。这时我们就可以在物理内存中申请一个真正的物理页，将其内容设置为0，设置相应的PTE为可写，然后将发生异常的虚拟的页指向刚申请的物理页

3. demand paging

XV6会将用户空间里的所有有效区域（text区， data区）全部映射至页表中，并将它们从磁盘中全部加载到内存里。这其实是一个代价很高的操作，我们并不一定需要将整个二进制都加载到内存中，可以直到应用程序实际需要这些指令的时候再加载内存。

所以我们为text和data分配好地址段，但是相应的PTE并不对应任何物理页。对于这些PTE，我们只需要将valid bit位设置为0即可。当发生page fault时，我们在page fault处理程序中再去从程序文件中读取相应页的数据，加载到内存中，然后将这些物理页映射到页表中，最后再重新执行指令

4. lazy page allocation

在XV6中，一旦调用了 sbrk，内核会立即分配应用程序所需要的物理内存。但是实际上应用程序很难预测自己需要多少内存，所以通常应用程序倾向于申请多于自己所需要的内存。这意味着进程的内存消耗会增加许多，但是有部分内存永远也不会被应用程序所使用到。

利用lazy allocation我们可以解决这里的问题。即像 sbrk这样的系统调用并不会真正去分配物理内存。如果应用程序使用到了新申请的那部分内存，就会触发页错误。这时page fault handler才去实际分配一个物理页，将这个页映射到用户页表中，最后重新执行指令。

内存耗尽:

当发生内存耗尽的情况，可以选择撤回操作，即将内存中的某些Page刷新回磁盘，然后它们的位置就空出来了

上面这些技术均是关于page fault的一些技巧，更重要的是它们对于进程来说完全是透明的，硬件会自动的完成这些事

xv6

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

[xv6]:内存管理上一篇

[xv6]:内核启动下一篇