Traps and system calls

traps=系统调用+异常+中断。本章着重讲traps概述以及traps中的系统调用。

对trap的处理包含四个部分：硬件处理、中断向量、trap handler、对应的处理函数

RISC-V trap machinery

image-20230618162437636

image-20230618162500928

在RISC-V中，异常通常是由于程序执行过程中的错误或非预期事件而引起的，包括故障（faults）、陷阱（traps）和中止（aborts）。中断（interrupts）则是由外部事件触发的，例如定时器到期、外部设备请求等。中断是异步事件，与当前正在执行的指令无关，因此会在任何时候发生。

xv6是基于RISC-V架构的。因此，发生异常的时候，就会跳转到统一的kernel trap，然后再在里面通过读取scause来进行相应处理。

发生中断的处理方式就和x86差不多了，都是通过中断向量实现的。

control register

risc-v为trap提供了一组寄存器：

  1. stvec

    trap handler的入口地址

  2. sepc

    原程序PC

  3. scause

    中断号

  4. sscratch

    TRAPFRAME地址

  5. sstatus

    是否允许中断，以及中断来自内核态还是用户态

The above registers relate to traps handled in supervisor mode, and they cannot be read or written in user mode.

There is an equivalent set of control registers for traps handled in machine mode; xv6 uses them only for the special case of timer interrupts.

每个CPU都有自己的一套这样的控制寄存器。

硬件处理步骤

时钟中断、device interrupt以及关中断的情况下，不会做以下步骤。

\1. If the trap is a device interrupt, and the sstatus SIE bit is clear, don’t do any of the following.

\2. Disable interrupts by clearing SIE.关中断

\3. Copy the pc to sepc.保存PC

\4. Save the current mode (user or supervisor) in the SPP bit in sstatus.保存mode

\5. Set scause to reflflect the trap’s cause.保存中断号

\6. Set the mode to supervisor.切换到内核态

\7. Copy stvec to the pc.将trap handler写入pc，开始执行trap handler【uservec or kernelvec？】

切换到内核页表、切换内核栈、保存寄存器现场这些工作交给操作系统完成。

Traps from user space

从用户态来的trap会经历怎么样的过程？

前面说到，下面需要进行页表的切换，页表的切换必然是接下来要做的指令的某个环节。那么为了让页表切换之后，CPU还知道要从哪里取指执行，就要让某段物理内存在内核空间和用户空间的虚拟地址一样。这样，不论页表是用户的还是内核的，都可以通过同样的虚拟地址访问到该段存放指令的物理内存从而继续执行。

这段虚拟地址就是trampoline。它在内核页表和用户页表都位于MAXVA的位置。

我感觉这段大概可以这么理解：

通过查看代码，可知trampoline段实际上存储的是trampoline.S中的数据，也即uservec和userret的汇编代码，也即执行切换页表我们实际上就是在执行trampoline里的代码。trampoline的存在，就可以使得每个页表的这部分都是这两个的代码，这样一来切换页表也就不影响指令流的执行。

p3

stevc存储的正是trampoline段中的uservec。

uservec

sscratch里面存的是trapframe的值。

trapframe存在于用户空间中，并且每个进程的trapframe所处位置固定是在trampoline下方。

image-20230111203357767

首先将寄存器的值都存入trapframe中；然后，再从trapframe中读取内核栈指针、当前CPUid，下一步要跳转的usertrap的地址，以及内核页表。最后，uservec切换到内核页表，并且jmp到usertrap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#in kernel/trampoline.S
	.section trampsec
.globl trampoline
trampoline:
.align 4
.globl uservec
uservec:    
	#
        # 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
        csrrw a0, sscratch, a0

        # save the user registers in TRAPFRAME
        sd ra, 40(a0)
        sd sp, 48(a0)
        # ...
        sd t6, 280(a0)

		# save the user a0 in p->trapframe->a0
        csrr t0, sscratch
        sd t0, 112(a0)

        # restore kernel stack pointer from p->trapframe->kernel_sp
        # 完成了内核栈的切换
        ld sp, 8(a0)

        # make tp hold the current hartid, from p->trapframe->kernel_hartid
        ld tp, 32(a0)

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

        # restore kernel page table from p->trapframe->kernel_satp
        ld t1, 0(a0)
        # 这里完成了页表的切换
        csrw satp, t1
        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
        jr t0

注：trampoline和trapframe有一些相通点。

trampoline为了保障某段物理内存的虚拟地址在内核栈和用户栈中不变，做出的努力是，在内核栈和用户栈都分配同一位置的PTE。

trapframe用于保护现场、用户态向内核态传递参数等等，做出的努力是，在用户栈分配同一位置的PTE，在内核态的局部变量中保存了自己的物理地址。

这两个说实话有点容易混起来，因为我想了半天trampoline可不可以用类似trapframe一样的方法，结论是不行。因为你trampoline的作用是维持指令序列依然不变，不会突然没掉；而trapframe段是用来存储数据而非执行的，对其的控制也是需要指令的。如果trampoline使用第二种方法，指令流就会断掉，更别说别的了。

usertrap

作用是得到trap发生的原因，并且执行对应的处理程序，然后返回结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
void
usertrap(void)
{
  int which_dev = 0;

  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.
  //首先把trap handler切换到kernel的，这样一来如果在kernel中发生trap就会由kernel的handler处理
  w_stvec((uint64)kernelvec);

  struct proc *p = myproc();
  
  //在当前进程中再次保存用户程序的原PC，防止之后sepc被覆盖
  // save user program counter.
  p->trapframe->epc = r_sepc();
  
  //根据cause号不同处理
  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.
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    //注意，在此处开启了中断
    intr_on();

    //调用syscall处理
    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();
}

执行对应的处理函数

比如说system call会修改trapframe中的a0为返回的结果，会获取trapframe中的各个参数。这个“保护现场“感觉是非常微妙的，它兼顾了保护现场和传递参数两个作用

usertrapret

回到用户态。之前陷入内核态对stvec、satp、sp、hartid、trap handler都做了适应内核态的改变，因而这里就需要改回原来适应用户态的样子，然后返回用户态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// return to user space
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();

  // 重置trapframe
  // send syscalls, interrupts, and exceptions to trampoline.S
  w_stvec(TRAMPOLINE + (uservec - trampoline));
  // set up trapframe values that uservec will need when
  // the process next re-enters the kernel.
  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.
  
  // set S Previous Privilege mode to User.
  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.
  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.
  uint64 fn = TRAMPOLINE + (userret - trampoline);
  ((void (*)(uint64,uint64))fn)(TRAPFRAME, satp);
}

userret

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
.globl userret
userret:
        # 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 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

Code: calling system calls

Chapter 2 ended with initcode.S invoking the exec system call (user/initcode.S:11). Let’s look at how the user call makes its way to the exec system call’s implementation in the kernel.要讲如何从用户态找到exec的代码了。

Code: system call arguments

讲的是系统调用时，是如何把用户态传递的地址转化为内核态地址的。

这个部分可以看看hit实验的实验3 6.7，讲得很详细，而且流程是差不多的。linux0.11的get_fs_byte()就相当于xv6的copyinstr。

Traps from kernel space

kernelvec

不同于用户态还得先潜入内核再潜出内核，内核的trap可简单多了，省去了切来切去各种东西的步骤，只需当做一个普通的函数调用就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# in kernel/kernelvec.S
.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 t6, 240(sp)

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

        // restore registers.
        ld ra, 0(sp)
        ld sp, 8(sp)
        # ...
        ld t5, 232(sp)
        ld t6, 240(sp)

        addi sp, sp, 256

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

kerneltrap

kerneltrap is prepared for two types of traps: device interrrupts and exceptions.

It calls devintr (kernel/trap.c:177) to check for and handle the former. If the trap isn’t a device interrupt, it must be an exception, and that is always a fatal error if it occurs in the xv6 kernel; the kernel calls panic and stops executing.

If kerneltrap was called due to a timer interrupt, and a process’s kernel thread is running (rather than a scheduler thread), kerneltrap calls yield to give other threads a chance to run.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// in kernel/trap.c
// interrupts and exceptions from kernel code go here via kernelvec,
// on whatever the current kernel stack is.
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");

  // 在此处的devintr对不同的设备进行不同的处理方式
  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);
}

Page-fault exceptions

似乎xv6是没有这个缺页exception的。这里主要讲解了三个可以利用缺页中断实现的优化：COW fork、lazy allocation、paging from disk。还提及了automatically extending stacks 以及memory-mapped fifiles。

Lab：Trap

This lab explores how system calls are implemented using traps. You will first do a warm-up exercises with stacks and then you will implement an example of user-level trap handling.

RISC-V assembly

题目和答案

参考：

Lab4: traps

There is a file user/call.c in your xv6 repo. make fs.img compiles it and also produces a readable assembly version of the program in user/call.asm.

Read the code in call.asm for the functions g, f, and main. Here are some questions that you should answer:

  1. a2

  2. 被inline掉了

  3. 0x64A

    image-20230111224927837

    auipc的作用是把立即数左移12位，低12位补0，和pc相加赋给指定寄存器。这里立即数是0，指定寄存器是ra，即ra=pc=0x30=48。jalr作用是跳转到立即数+指定寄存器处并且把ra的值置为下一条指令。因此jalr会跳转1562+48=1594=0x64A处，观察汇编代码可知确实在000000000000064a处。

  4. 0x38

  5. Run the following code.

    1
    2
    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?

    format,png

  6. 取决于寄存器a2（第3个参数）的值。

Backtrace

For debugging it is often useful to have a backtrace: a list of the function calls on the stack above the point at which the error occurred.

image-20230111232323444

The compiler puts in each stack frame a frame pointer that holds the address of the caller’s frame pointer. Your backtrace should use these frame pointers to walk up the stack and print the saved return address in each stack frame.

Some hints:

  • Add the prototype for backtrace to kernel/defs.h so that you can invoke backtrace in sys_sleep.

  • The GCC compiler stores the frame pointer of the currently executing function in the register s0. Add the following function to kernel/riscv.h:

    1
    2
    3
    4
    5
    6
    7
    static inline uint64
    r_fp()
    {
      uint64 x;
      asm volatile("mv %0, s0" : "=r" (x) );
      return x;
    }

    and call this function in backtrace to read the current frame pointer. This function uses in-line assembly to read s0.

  • These lecture notes have a picture of the layout of stack frames. Note that the return address lives at a fixed offset (-8) from the frame pointer of a stackframe, and that the saved frame pointer lives at fixed offset (-16) from the frame pointer.

  • Xv6 allocates one page for each stack in the xv6 kernel at PAGE-aligned address. You can compute the top and bottom address of the stack page by using PGROUNDDOWN(fp) and PGROUNDUP(fp) (see kernel/riscv.h. These number are helpful for backtrace to terminate its loop.

感想

我超，这题真的是那怎能只叫一个拷打……

存储在s0中的栈帧指针

这个应该是risc-v的约定成俗的特性。我搜了一下risc-v的栈帧指针保存在哪个寄存器，看到了这样一篇文章：

risc-v 栈分析

image-20230112012358601

这个信息没有放在题干提示，是在考察信息检索能力吗（

栈的结构与栈帧的理解

image-20230112010749756

这是来自hint的栈结构。整个栈存储在一页中，由高地址向低地址增长。栈帧代表了一次函数调用，其中会存储如函数名、函数参数、局部变量等等信息。有几次函数调用就有几个栈帧，栈由栈帧组成。

s0中存储的栈帧指针fp指向的是栈帧的最高地址，如图fp所示。

我理解错了栈帧的定义，都怪我基础不大牢固也不认真思考【悲】我一开始以为stack frame指的是一个栈，也即一页空间【我知道栈帧这个中文名词，但遇到英语就短路了】。老师画的这个图也被我理解为多个栈，也即多页拼在一起，要打印的Return Address处于页的最顶部。我就在这个思路上一去不复返了，压根没有意识到一个进程只有一个栈【大悲】然后顺带脑补把r_fp()也曲解了，以为它的意思是读取当前栈【非常自然地认为有很多个栈←】的下一个栈的最低地址【因为栈换掉了，所以s0也会变成父亲的栈的地址】。于是就写出了这样的代码：

1
2
3
4
5
6
7
8
9
10
void
backtrace(){
   printf("backtrace:\n");
   uint64 kstack = PGROUNDUP((uint64)(myproc()->kstack)+1);
   uint64 nstack = 0;
   while((nstack=(uint64)r_fp())!=0){
         printf("%p\n",*((uint64*)(kstack-8)));
         kstack = nstack;
   }
}

结果最后死循环了。去看了别人的代码发现他们写的结构就跟我完全不一样。琢磨着画着图，最后找了stack frame的定义，才恍然大悟（

思路形成

我们只需遍历栈中所有栈帧，打印每个栈帧的Return Address部分就行。通过r_fp()获取第一个栈帧的位置，其他栈帧的位置由Prev.Frame获取。循环的界限是PGROUNDUP(r_fp())，因为栈只有一页的空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
void
backtrace(){
  printf("backtrace:\n");
  uint64 stack = r_fp();
  uint64 nstack = 0;
  uint64 top = PGROUNDUP(stack);
  while(stack!=top){
    nstack=*((uint64*)(stack-16));
    printf("%p\n",*((uint64*)(stack-8)));
    stack = nstack;
  }
}

Alarm

In this exercise you’ll add a feature to xv6 that periodically alerts a process as it uses CPU time. This might be useful for compute-bound processes that want to limit how much CPU time they chew up, or for processes that want to compute but also want to take some periodic action.

More generally, you’ll be implementing a primitive form of user-level interrupt/fault handlers; you could use something similar to handle page faults in the application, for example.

You should add a new sigalarm(interval, handler) system call. If an application calls sigalarm(n, fn), then after every n “ticks” of CPU time that the program consumes, the kernel should cause application function fn to be called. When fn returns, the application should resume where it left off.

感觉从alarm中可以窥见信号的实现思路：

image-20231218164244526

而alarm的机理感觉也有点类似。用户先通过sigalarm注册定时函数，内核在时钟中断的时候对该标记位进行检查，然后去do_signal回到用户态执行用户的signal handler，再通过sigreturn回到用户模式。sigalarm相当于一个信号注册函数，sigreturn也就是上图的sigreturn。

分析

初见思路

思路：sigalarm需要在用户程序在用户态运行的情况下，监测到用户程序已经运行了n个时间片，然后发出中断请求。我们会新设置一个中断类型alarm。kerneltrap接收到sigalarm的中断请求，检测到中断类型为alarm，就会在处理的时候调用fn。fn调用完就自然而然利用中断恢复到原来的现场了。所以要做的可以分为两部分。但问题是，如何让sigalarm在用户程序运行的同时监测n个时间片呢？难道得fork一个新的进程吗？然后父进程返回，子进程执行类似sleep里面那样的监测，直到时间片到了，就发送一个中断请求，让父进程停止，执行完fn回来之后就exit。

正确思路

可以看到，初见思路很多地方跟最后是不一样的。其中错得最离谱的，也是比较隐坑很容易因为想不明白就寄了的，是handler是个用户态的函数（。你不可能在内核态中调用fn，然后fn执行完后再自然而然地通过中断机制返回，因为你想要执行fn就必须进入用户态。这一点是需要一开始明确的。

明确了这一点后，让人更加不知道该怎么办了。那就一步步跟着指导书的脚步来思考吧。

part 1

首先，明确你需要实现什么。你需要实现两个系统调用，一个是sigalarm，一个是sigreturn。结合提示，可知实验设计者给我们的思路是，通过sigalarm设置定时函数，通过sigalarm(0,0)取消定时函数。每次时钟中断检测当前定时时间是否达到，若已达到，则跳到定时函数执行。定时函数执行完后，需要借助sigreturn，才能正确返回时钟中断前的程序点。

part 2

这又可拆解为几个要点：

  1. 如何实现“定时”？
  2. 时钟中断在内核态的usertrap被检测。怎么从usertrap出来跳到定时函数而非原程序执行点？
  3. 执行完定时函数后，怎么样才能回到原程序执行点？
part 3

一个个来说，首先是如何实现定时。这个很简单。参照sys_sleep的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
uint64
sys_sleep(void)
{
  int n;
  uint ticks0;

  backtrace();
  if(argint(0, &n) < 0)
    return -1;
  acquire(&tickslock);
  ticks0 = ticks;
  while(ticks - ticks0 < n){
    if(myproc()->killed){
      release(&tickslock);
      return -1;
    }
    sleep(&ticks, &tickslock);
  }
  release(&tickslock);

  return 0;
}

可知，我们可以用ticks表示当前系统滴答数。这样，我们就可以在proc域里维护一个变量lasttick，记录上一次执行handler时的滴答数。每次在时钟中断时检测，所以需要写在kernel/trap.c中的usertrap中。

part 4

然后，是怎么从usertrap出来跳到指定程序结束点。在书中，我们知道，sepc寄存器保存了中断前原程序的下一个执行点，sepc的备份存储在了proc域中的栈帧中。当中断返回时（在usertrapret中），会从栈帧中的epc字段读取sepc的备份赋值给sepc，再由sret帮助我们跳转到原程序点。因而，如果想要改变跳转点，我们只需要修改p->trapframe->epc就行。

part 5

最后，是如何从periodic回到原程序执行点。

image-20230113002057893

这是每次进行时钟中断时的栈情况和执行代码链：t1->trampoline->usertrap->handler。

再然后，handler调用了sigreturn，用户栈中就会产生sigreturn的栈帧：

image-20230113002434093

此时，如果sigreturn执行完，就会在这样的情况下执行handler的ret指令：

image-20230113002542335

ret指令会把栈帧弄走，也就是说会直接回到某个错误的地方去。这显然不大合适。所以，我们要做的，就是在sigreturn之后，不执行handler的ret指令，也不执行sigreturn的ret指令，而是直接恢复到时钟中断前的上下文。时钟中断前的上下文，会因在handler中调用sigreturn系统调用，而被覆盖，因而，我们就需要记录时钟中断前的上下文，也即在proc域中保存trapframe的一份拷贝savedtrap，每次时钟中断都更新一次savedtrap，然后在sigreturn调用的时候将proc原本的trapframe替换为savedtrap即可。这样一来，就完成了这道题。

感想

这题目确实最终代码看起来完全不难，但是非常地拷打。。。。我前前后后修修补补差不多一共花了五个小时之久。

计时怎么计，以及使用trapframe->epc来跳转这两点还是很容易想到的【话虽如此，其实也很曲折】。主要难点还是在怎么恢复现场。怎么说呢，我花了这么久做实验，但是实际笔记却写不出个鬼来，足以看出其复杂程度。

我主要还是思维固化了点，一直在想，怎么确保它正确返回现场。我一开始以为proc域保存一个寄存器状态，且只用在一开始设置定时函数也即sigalarm的时候保存一次就行了，并且认为其是epc。然而实际操作后发现usertrap崩了，并且epc中存储的并不是程序被时钟中断的地方，而是各种神奇的地方，具体我也忘了，反正不能行。我印象最深刻的是有一次停在了usys.S中的sigreturn的最后一个ret处。我就在想，也许是栈出了问题。于是我就想着直接在sigreturn的时候把epc指向栈帧中的return address，直接回到原执行段。我百度了一下，确实有这么个寄存器ra，存储着return address。于是我就把proc域的状态换成了ra，依然仅保存一次，最后发现还是不行，程序在test0之后就异常终止了，main也回不去，十分古怪，十分匪夷所思。我实在没忍住，百度了一下大家怎么做的，发现大家压根没有我这样的二选一的烦恼，是直接保存整个栈帧。而且也不是仅保存一次，而是每次时钟中断触发都保存一次。我觉得十分奇怪震惊，但此时已是差不多晚饭时间，我就先去吃了个饭（）

回来之后，我细细画了图【向正确思路part5中的那样】，发现我原来那个只保存两者之一，且都只保存一次的方式，确实完全不能行。但是，我发现两个一起保存，并且每次时钟中断保存的方法，似乎能行，而且，比保存一整个栈帧要聪明得多。于是我就去试了，发现还是不行。我再细想了一遍，发现，如果想回去原程序的现场，除了ra和epc，还有一个很重要的东西需要保存，那就是——用户栈指针sp！

也就是说，只需保存ra、epc、sp，就可以保证回到正确的时钟中断前的位置：

image-20230113005100895

此为handler中sigreturn执行完要返回时的状态。

当处在handler中时，sp的值为sigreturn处的栈帧。执行系统调用时，proc域中的上下文被覆盖，也即时钟中断前的上下文被覆盖。如果此时不对栈帧中的sp进行恢复，仅恢复ra和epc，在从sigreturn返回到epc对应处也即t1，t1执行ret想回到main的时候，就会回不去，而是回到了sigreturn要回的位置，也即handler的位置，然后不知不觉就寄了。所以，就需要防止sp被覆盖。因而，再保存一个状态sp，就可以保障回到正确的地方了。测试出来，kernel确实不再会panic了。

但是由于运行时很多除这三个以外的寄存器都被改过了，回是回得去，接下来干的活就不一定对了。因此为了保险以及通用性以及便利性来看，还是像别人那样直接保存栈帧比较ok。

还有一件事，就是上述错误中经常会出现的一个输出结果：

1
usertrap:unexpected cause scause = 0x0c

我留意了一下是什么意思。网上搜索得，scause=12，说明这是一个instruction page fault，而这个缺页错误说明了什么？：

image-20230113012355740

这样，一切都明朗了。出现了scause=0x0c的意思就是说pc里的值不恰当，也就是说上面错误的方法都会跳转到错误的地方去。

Lab：xv6 lazy page allocation

参考：https://blog.csdn.net/m0_53157173/article/details/131349366

来自书本：

Another widely-used feature is called lazy allocation, which has two parts:

  1. First, when an application calls sbrk, the kernel grows the address space, but marks the new addresses as not valid in the page table.
  2. Second, on a page fault on one of those new addresses, the kernel allocates physical memory and maps it into the page table.

The kernel allocates memory only when the application actually uses it.

Eliminate allocation from sbrk()

Your first task is to delete page allocation from the sbrk(n).

The sbrk(n) system call grows the process’s memory size by n bytes, and then returns the start of the newly allocated region (i.e., the old size). Your new sbrk(n) should just increment the process’s size (myproc()->sz) by n and return the old size. It should not allocate memory – so you should delete the call to growproc() (but you still need to increase the process’s size!).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  int sz = myproc()->sz;
  addr = sz;
  myproc()->sz = sz + n;
  //if(growproc(n) < 0)
  //  return -1;
  return addr;
}

Lazy allocation

Modify the code in trap.c to respond to a page fault from user space by mapping a newly-allocated page of physical memory at the faulting address, and then returning back to user space to let the process continue executing.

You should add your code just before the printf call that produced the “usertrap(): …” message. Modify whatever other xv6 kernel code you need to in order to get echo hi to work.

感想

思路

首先，要知道缺页中断的scause为13或15.【论我怎么知道的：被以前的实验逼出来的hhh】然后，要写在if条件的第二个分支。在该分支内，我们需要先获取出问题的地方的虚拟地址的值，然后申请新的一页，再map到当前页表中。

一个难以察觉的错误
描述

思路是很简单的，就是有小细节需要格外注意。

trap.c在mappages时，一定不能直接传入va，必须传入PGROUNDDOWN(va)。如果直接传入va，会爆出如下错误：

image-20230116154004538

但是，查看mappages的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  uint64 a, last;
  pte_t *pte;

  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  for(;;){
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    if(*pte & PTE_V)
      panic("remap");
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

我们可以看到，它在里面已经对va进行了处理了，使它变成了page-align的a变量。那么为什么，我们还要在外面再对va处理一次呢？

其实问题不是出在mappages中的a变量上，而是出现在mappages中的last变量上。比如，令va=PGSIZE+200，则a=PGSIZE，last=2*PGSIZE。这样一来，在下面的循环中，除了添加了刚刚申请的那页的映射以外，我们还多添加了新的一页，其物理地址为mem+PGSIZE。

这十分地危险！假设你要申请的va为proc->size的最后一页，那么，经过本次缺页中断之后，你事实上申请了两页，两页的地址分别为va和va+PGSIZE。而va+PGSIZE大于proc->size。也就是说，地址溢出了！

这会导致页表释放的时候出问题。以下是页表释放的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// in proc.c
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  uvmfree(pagetable, sz);
}

// in vm.c
void
uvmfree(pagetable_t pagetable, uint64 sz)
{
  if(sz > 0)
    uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
  freewalk(pagetable);
}

// in vm.c
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;

  if((va % PGSIZE) != 0)
    panic("uvmunmap: not aligned");

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    if((pte = walk(pagetable, a, 0)) == 0){
      printf("uvmunmap walk: %p\n",a);
      continue;
    }
    if((*pte & PTE_V) == 0){
      printf("uvmunmap: %p\n",a);
      continue;
    }
    printf("uvmunmap OK: %p\n",a);
    if(PTE_FLAGS(*pte) == PTE_V)
      panic("uvmunmap: not a leaf");
    if(do_free){
      uint64 pa = PTE2PA(*pte);
      kfree((void*)pa);
    }
    *pte = 0;
  }
}

freewalk要求在uvmunmap中已经释放完所有的叶子结点。而由于uvmunmap中释放结点的va是从0递增到proc->size的，也因而，前面的那个大于proc->size的那页虽然还在页表中存在，但是不会被uvmunmap释放！这也就导致，接下来调用freewalk的时候，会发现该页的叶子结点仍然存在，从而导致freewalk: leaf。

可以结合uvmunmap和trap.c中的调试语句看下图的过程，可以看到非常清晰明了，0x14000这一页并没有在uvmunmap中释放！

trap.c中的调试语句：

1
2
3
4
printf("trap: %p,+PGSIZE = %p\n",PGROUNDDOWN(va),PGROUNDDOWN(va)+PGSIZE);
   if(mappages(p->pagetable,va, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
     kfree(mem);
   }

图：

image-20230116165910356

debug过程

看到freewalk: leaf这一错误，很容易联想到跟页表的释放有关。并且加上PGGROUNDDOWN就没问题，不加上才有问题，也很容易联想到跟mappages中多申请的那一页有关。但是具体是什么关系，这一点想要想到对我来说还是非常曲折的。

我一开始，以为是因为多申请的那一页（下面简称为B页好了）很有可能是其他进程在使用的，然后其他进程在echo进程释放页表前释放了页表，从而导致B页已经free了，这样一来uvmunmap说不定就能监测到对应物理页已经free，然后爆出panic。我一开始认为uvmunmap的这句话是用来监测物理页是否free的：

1
2
3
4
if((*pte & PTE_V) == 0){
   continue;
   //panic("uvmunmap: not mapped");
 }

然后顺理成章地，这边条件==0成立，然后continue，然后直到freewalk才发现该pte未释放。

但是，我仔细过脑子想了想，发现，就算物理页已经free了，但是，*pte依然存在，PTE_V也依然为1，这个条件是不成立的。也就是说，B页不会continue，而是会继续下面的正常释放的流程。也就是说，B页是可以正常释放的，我们的“B页已经free导致uvmunmap释放失败”的推论是错误的。

但究竟是为什么呢？肯定跟B页有关系，但是又不是这种关系，这让我十分地苦恼且烦躁，于是我就去打了会儿游戏。边玩的时候突然注意到一件非常可疑的事情。

image-20230116154004538

这是发生错误时退出的截图。有一个点引起了我的注意，就是echo hi并没有打印hi在console上。也就是说，这个panic是在echo执行前产生的！那么这个执行前是在哪呢？答案就是在exec中！

1
2
3
4
5
6
7
8
9
// in exec.c
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;
  p->sz = sz;
  p->trapframe->epc = elf.entry;  // initial program counter = main
  p->trapframe->sp = sp; // initial stack pointer
  // 这里！！！！！
  proc_freepagetable(oldpagetable, oldsz);

可以看到，这里调用了proc_freetable，从而跟freewalk有了联系。

但是，如果我们还坚持是因为B页错的，就需要找到一个可能会产生B页的地方，也就是验证shell准备执行echo命令，fork出一个子进程之后，又在exec free页表前，已经调用过sbrk函数，并且已经触发过缺页中断。这个验证其实很简单，只需要找sbrk在哪被调用过，哪边使用过heap内存【也即哪边涉及了指针赋值】就行了。

通过全局搜索，可知sbrk在user/umalloc.c下的malloc()被使用过，而在user/sh.c中，fork子进程之后：

1
2
if(fork1() == 0)
  runcmd(parsecmd(buf));

这其中的parsecmd()中malloc被使用过，并且发生了指针赋值！！也就是说，“是因为B页错的”这个结论是对的。

虽然这一段debug没有改变我们要证明“是B页在释放内存中出错的”的这个目的，但是确实带给了我很多这种执行时申请内存的知识，并且也让我突然想起了可以用printf debug。于是，我就去做了上面那个在trap.c中和uvmunmap中printf的调试语句，最终成功发现了结论。

实在是太艰苦了（）这告诉我们以后千万千万要注意，是否需要用到PGGROUNDDOWN。

一个漏掉未考虑的细节

摘自https://blog.csdn.net/m0_53157173/article/details/131349366

image-20231209011856305

image-20231209011932500

不过我以前好像是有考虑到这个的，但是我是这么做的：

image-20231209015238219

也就是相当于把它在addr parse的那段代码移进了walkaddr中。但是这样是不行的，查找可知argaddr的应用范围可比walkaddr广得多……

而为什么我下面的COW也是修改了walkaddr，而非修改argaddr，就可以达到同样的效果呢？这是因为cow只需对在内核中写用户页这种情况进行特殊处理，而这只有一个情况，也即只在copyout中发生。因而，我们只需修改walkaddr，就可以完全防范该情况了。

Lazytests and Usertests

We’ve supplied you with lazytests, an xv6 user program that tests some specific situations that may stress your lazy memory allocator. Modify your kernel code so that all of both lazytests and usertests pass.

感想

一个绷不住的错误

其实很简单，按照提示一步步做就行了。为什么我做得那么久那么崩溃呢？知道原因后我都笑嘻了。

在第一步修改sys_sbrk()的时候，我一下子没多想，使用了一句int sz = myproc()->sz，其实本来应该使用uint64的，使用int会溢出。这个伏笔就一直隐含到这里，然后大坑了我一笔。

一开始是发现lazytests的第二个，也就是oom过不去。我想了很久，也去网上找了别人的代码一步步对比下来看了，没有发现特别大的问题。于是我就在walk和sys_sbrk分别留下了调试信息：

1
2
3
4
5
// in walk()
  if(va >= MAXVA){
    printf("walk:va=%p,p->sz=%p,MAXVA=%p,pgva=%p\n",va,myproc()->sz,MAXVA,PGROUNDDOWN(va));
    panic("walk");
  }
1
2
3
4
5
6
7
// in sys_sbrk()
  if(n >= 0){
    uint64 tmp = n + sz;
    if(tmp > MAXVA || n + sz < n)       return -1;
    myproc()->sz = tmp;
    //printf("haha sb!sz=%p,n=%p\n",myproc()->sz,n);
  }

然后发现了这样的输出：

image-20230116225124363

可以看到，最后一次sz发生了数值溢出。

但是，此时我并没有悔改。我反而认为，“原本代码就是这么写的”。也就是说，我认为int sz是它原本内核代码给的。。。。。。在这样的情况下，我选择加上这样的条件判断：

1
if(tmp > MAXVA || ((tmp >> 31)& 1) == 1)       return -1;

之后确实没有溢出了，但是test fail了。此时我想，为什么非要用int而不用uint64呢？一阵令人不寒而栗的预感袭来，我连忙去看了proc.h里的sz的定义，发现，sz原本就应该是uint64类型的，是我错辣【悲】

只能说起到一种很好的教训。主要是这种问题实在没有想过自己会犯

代码

  • Handle the parent-to-child memory copy in fork() correctly.
1
2
3
4
5
6
7
// in vm.c uvmcopy()
    if((pte = walk(old, i, 0)) == 0)
      continue;
      //panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      continue;
      //panic("uvmcopy: page not present");
  • Handle negative sbrk() arguments.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  uint64 sz = myproc()->sz;
  addr = sz;
  if(n >= 0){
    uint64 tmp = n + sz;
    if(tmp > MAXVA || n + sz < n)       return -1;
    myproc()->sz = tmp;
    //printf("haha sb!sz=%p,n=%p\n",myproc()->sz,n);
  } else{
    if(n + sz > 0)
      myproc()->sz = uvmdealloc(myproc()->pagetable, sz, sz + n);
    else
      return -1;
  }
  //if(growproc(n) < 0)
  //  return -1;
  return addr;
}

  • Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().

  • Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.

  • Handle faults on the invalid page below the user stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
else if(scause == 13 || scause == 15){
    // 缺页中断
    uint64 va = r_stval();
    if(va >= p->sz ||  va < PGROUNDUP(p->trapframe->sp) ||PGROUNDDOWN(va) >= MAXVA){
      //printf("va=%p stack=%p\n",va,PGROUNDUP(r_sp()));
      p->killed = 1;
    } else{
      char* mem = kalloc();
      if(mem != 0){
        memset(mem, 0, PGSIZE);
        //printf("trap: %d %p\n",p->pid,PGROUNDDOWN(va));
        if(mappages(p->pagetable,PGROUNDDOWN(va), PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
          kfree(mem);
          p->killed = 1;
        }
      } else {
        p->killed = 1;
      }
    }
  }
  • Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.

我认为这里要是引起一个缺页中断可能会更酷，可能可以像lazytests里面这么做：

1
2
3
4
5
6
7
8
char *i, *prev_end, *new_end;

prev_end = sbrk(REGION_SZ);
new_end = prev_end + REGION_SZ;

// 这里触发了多次缺页中断
for (i = prev_end + PGSIZE; i < new_end; i += PGSIZE * PGSIZE)
  *(char **)i = i;

之后有机会再试试233

【试了一下，发现是可以的。在COW fork的 感想—一些错误和思考—在内核态中引发并处理缺页中断 这部分内容中详细说明了具体要怎么做。】

Lab: Copy-on-Write Fork for xv6

Parent and child can safely share phyical memory using copy-on-write fork, driven by page faults.

RISC-V has three different kinds of page fault: load page faults (when a load instruction cannot translate its virtual address), store page faults (when a store instruction cannot translate its virtual address), and instruction page faults (when the address for an instruction doesn’t translate).

The basic plan in COW fork is for the parent and child to initially share all physical pages, but to map them read-only. Thus, when the child or parent executes a store instruction, the RISC-V CPU raises a page-fault exception. In response to this exception, the kernel makes a copy of the page that contains the faulted address. It maps one copy read/write in the child’s address space and the other copy read/write in the parent’s address space. After updating the page tables, the kernel resumes the faulting process at the instruction that caused the fault.

PS【这个很重要】: COW fork() makes freeing of the physical pages that implement user memory a little trickier. A given physical page may be referred to by multiple processes’ page tables, and should be freed only when the last reference disappears.

感想

思路

思路还是很直观的。

我们只需要在fork的时候，标记父子进程的所有PTE都为read-only，然后之后就会遇到不同scause的缺页中断，针对特定的scause，新建物理页面，拷贝物理页面，然后重新设置映射即可。而对于其提出的需要标记某页是否能够释放，则需要统计每页的ref数，当ref==1的时候才可以释放。

分析

总分析

其实可以把任务简单拆分为三部分。第一部分是实现基本的cow fork的逻辑，第二部分是引用计数释放内存，第三部分是解决copyin/copyout时在内核态发生的缺页中断。我认为本实验的难点事实上在第二部分【悲】我可能有大于3/4的时间都花在第二部分上了吧。

第一部分是实现cow fork的基本逻辑，也就是修改fork中对页表的拷贝以及在usertrap中添加对缺页中断的处理，这很直观，没什么好说的。

第三部分要么跟上面的lazy allocation一样，在kernel/vm.c walkaddr()中把缺页中断搬过去，要么向我在主要难点与错误—在内核态中引发并处理缺页中断这一部分那样做。

我们分析这一部分主要讲的是我认为最难的地方，也就是第二部分。其实第二部分的思路也很直观：创建一个数组，index为所有能用的内存的address/PGSIZE，用来记录引用数；然后在每次增加引用时，对应元素++；每次减少引用时，对应元素–。

虽然思路很简单很直观，但是实现起来非常地非常地非常地考验细节（我就非常不擅长这一点）。下面，我就先阐述一下第二部分的这个方法需要分割为哪几部分，其他我遇到的印象较深的bug和对一些地方的思考，都放在了下一部分，也即主要难点与错误。

引用数实现分析

创建一个数组，index为所有能用的内存的address/PGSIZE，用来记录引用数；然后在每次增加引用时，对应元素++；每次减少引用时，对应元素–。

数组的大小和数据类型

由kernel/kalloc.c中的kinit()：

1
2
3
4
5
6
7
8
void
kinit()
{
  initlock(&kmem.lock, "kmem");
  // freerange用来把参数地址范围内的物理页加入freelist中
  // end是内核的结束地址
  freerange(end, (void*)PHYSTOP);
}

可知，事实上，我们整个程序，包括用户和内核，能用的内存空间为0~PHYSTOP。因而，我们事实上只需要建一个PHYSTOP/PGSIZE这么大的数组就行。我算了一下大概是2^19次方。

然后，我感觉这种小系统应该不会有过多的对某一页的重复引用，因而，为了节省空间，我将数据类型定为了char。最好还是别定成uchar，因为这东西要是0–的话会溢出变为255，很可怕。

什么时候增减引用

我认为这里是非常考验细节和头脑清晰度的，也就是我卡了很久最后也没弄出来的部分【悲】

可以分为三种情况来讲。我们的引用计数必须完美适应这三种情况：

  1. 不经由页表，通过kalloc和kfree直接使用物理页

    这就要求我们在kalloc的时候置引用数为1，然后kfree的时候对引用数先-1，再判断是否归零。

  2. 经由页表，但与cow fork无关

    增加页表项：mappages->kalloc，因而满足要求1即可。

    删除页表项：uvmunmap。当do_free==1时，满足要求1即可。

  3. 经由页表，与cow fork有关

    copy父进程页表时：在cowcopy中，每增加一次子进程的映射，就需要增加一次引用数

    在用户态/内核态发生缺页中断：发生缺页中断后，对原来物理页的引用数需要-1【我就是漏了这一点……】

    删除页表项：uvmunmap。当do_free==0时，当对应页表项有COW标记，则减少引用数

所以，我们需要在三个文件进行修改：

  1. kalloc.c

    增加数组定义，在kalloc和kfree中增加引用数修改

  2. vm.c

    在cowcopy和uvmunmap中增加引用数修改

  3. trap.c

    在usertrap的缺页中断中增加引用计数修改

并发安全

这里我也没想到【悲】

由于我们的pages数组会在多个文件、多个进程间使用，所以它必须在被锁保护的区域中被使用。

主要难点与错误

scause=2

image-20230117161404719

这个发生在我还没有实现第二部分的时候。搜索了一下，scause=2为Illegal instruction，而且sepc的这个1004的值也非常诡异。这应该是因为fork子进程释放了指令段内存，导致主进程执行错误

kernel无法启动

在kinit中

1
2
3
4
5
6
7
8
void
kinit()
{
  initlock(&kmem.lock, "kmem");
  initlock(&pages_lock,"pages");
  memset(pages, 0, (2<<19));
  freerange(end, (void*)PHYSTOP);
}

会通过freerange初始化freelist。在freerange中：

1
2
3
4
5
6
7
8
9
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE){
    kfree(p);
  }
}

会对每一项进行一次kfree。因而，我们需要在kfree前先增加一次引用，要不然会寄。

在缺页中断时减少对物理页的引用数

image-20230117213903706

注意此处不能直接让pages[pa/PGSIZE]–，一定要借助kfree。当此进程为引用pa的最后一个进程的时候，如果仅减少引用数，就会造成内存泄漏。kfree可以既减少引用数，又在适当的时候对物理页释放，可谓一举两得。kfree的这个双重作用思想也在uvmunmap中体现了。

在内核态中引发并处理缺页中断

Modify copyout() to use the same scheme as page faults when it encounters a COW page.

我们所做的第一第二部分仅仅是完成了对来自用户态的缺页中断的完美处理，还尚未处理来自内核态的缺页中断。因而，这个修改copyin和copyout的点实际上就是要我们处理内核态的缺页中断。

这次实验跟上次的lazy allocation一样，都可以直接在walkaddr进行特殊处理，并且差不多要把usertrap的全部代码挪过来【具体见lazy allocation的代码】。不过，我想出了另一个流氓的方法（也就是说其实原理感觉是不大对233）。我选择直接在kernel引发一个访问用户页面的缺页中断，然后在kerneltrap中处理这个中断，就像usertrap一样。

但由于在walkaddr中发生的中断处于内核状态下，所以就进不了usertrap。我们应该在kerneltrap中再次添加和usertrap一样的中断处理。我们会像这样引发一个中断：

1
2
3
if((*pte & PTE_COW) != 0){
  if((*pte & PTE_W) == 0){
    *(char*)va = 1;// 此处不能用pa哦

然后在kerneltrap中这样处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
if(r_scause() == 15){
    // 只要写入引起的缺页中断
    uint64 va = r_stval();
    pte_t *pte;
    uint64 pa;
    uint flags;

    if((pte = walk(p->pagetable, va, 0)) == 0)
        p->killed = 1;
    else if((*pte & PTE_V) == 0)
        p->killed = 1;
    else {
        sepc += 4;
        pa = PTE2PA(*pte);
        flags = PTE_FLAGS(*pte);

        char* mem;
        if((mem = kalloc())!=0){
            memmove(mem, (char*)pa, PGSIZE);
            // 设置为新的物理页地址
            *pte = PA2PTE(mem);
            kfree((void*)pa);
            // 设置新的flag，标记为可写
            flags = (flags | PTE_W | PTE_COW);
            *pte = ((*pte) | flags);
        } else{
            p->killed = 1;
        }
    }
  } else if((which_dev = devintr()) == 0){

但是，这样做是不行的。

会在这里卡住，会无限次不断进入kerneltrap。

image-20230117235028133

造成这个的原因，经过一番曲折的debug之后，我发现，只要像usertrap中的syscall分支一样：

1
2
3
4
5
6
7
8
9
if(r_scause() == 8){
    // system call
    
    // 重点是这里
    // sepc points to the ecall instruction,
    // but we want to return to the next instruction.
    p->trapframe->epc += 4;
    // ...
  }

加上这句话就行：

1
sepc += 4;

所以，结果就非常显而易见了，是因为一直卡在这句话执行不下去：

1
*(char*)va = 1;

这是因为缺页中断会返回到原代码句中执行，所以就会继续回到这句话。而我们知道，此时正处于内核态，并没有开启地址映射，所以此处其实是非法地址越界了。但是我们的目的确实已经达到了（因为va通过stval寄存器被传递到了kerneltrap），所以我们这里只需跳过这句即可。

这也是为什么说我这个方法虽然实现了，但本质上其实非常流氓，不算是kerneltrap。

Update：验收的时候跟学长说了一下这个点，学长表示不算流氓，反而在内核（至少内核赛）中算是一个比较通用的手法hh没想到还误打误撞上了

它带来的好处是，当地址不合法的时候可以减少开销。

具体来说，内核中一般会将地址空间分为多个vma，因而检查地址越界无需像xv6那样简单查页表，只需查地址是否在对应的vma中即可。所以，直接把这东西转到一个硬件的缺页中断中实现，事实上确实是减少了地址非法时的开销。

除了这一点外，还有一点很重要的是，由于walkaddr是需要返回一个pa的，因而我们需要手动再把pa在缺页中断后更新一下：

1
2
3
4
5
6
7
8
pa = PTE2PA(*pte);
if((*pte & PTE_COW) != 0){
  if((*pte & PTE_W) == 0){
    *(char*)va = 1;
    pa = PTE2PA(*pte);
  }
}
return pa;

总之，做了这两个关键步骤后，也能启动了，也能过cowtest了。所以下面的代码也就贴上了这里的版本。

心得

本次实验耗时经典五小时（包含笔记时间就是六个半小时了hhh），算是平均水平。很遗憾也很难受的一点是，我的错误最终还是没有自己想出来，而是参考了别人的代码才改对的。思路很简单，但是细节也依然非常多非常坑，还是得再加把劲。

代码

我们只需要在fork的时候，标记父子进程的所有PTE都为read-only，然后之后就会遇到不同scause的缺页中断，针对特定的scause，新建物理页面，拷贝物理页面，然后重新设置映射即可。而对于其提出的需要标记某页是否能够释放，则需要统计每页的ref数，当ref==1的时候才可以释放。

定义COW标记

1
2
3
4
// in kernel/riscv.h
#define PTE_V (1L << 0) 
// ...
#define PTE_COW (1L << 5)

引用数组初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// in kernel/kalloc.c
char pages[(2<<19)];
struct spinlock pages_lock;

void
kinit()
{ 
  initlock(&kmem.lock, "kmem");
  initlock(&pages_lock,"pages");
  memset(pages, 0, (2<<19));
  freerange(end, (void*)PHYSTOP);
}
void
freerange(void *pa_start, void *pa_end)
{
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE){
    pages[(uint64)p/PGSIZE] = 1;
    kfree(p);
  }
}

申请和释放页时增删引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// in kernel/kalloc.c
void *
kalloc(void)
{
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);
  if(r){
    acquire(&pages_lock);
    // 在这
    pages[(uint64)r/PGSIZE] = 1;
    release(&pages_lock);
  }
  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}
void
kfree(void *pa)
{
  struct run *r;

  acquire(&pages_lock);
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP || pages[(uint64)pa/PGSIZE] <= 0 )
    panic("kfree");
  // 每次kfree都会减少引用
  pages[(uint64)pa/PGSIZE]--;
  // 说明此时页面还被其他东西引用着，不能释放
  if(pages[((uint64)pa)/PGSIZE] > 0){
    release(&pages_lock);
    return;
  }
  release(&pages_lock);
    
  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);
  r = (struct run*)pa;

  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

修改fork时对页表的复制操作，并标记引用数增加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// in kernel/proc.c fork()
  // Copy user memory from parent to child.
  if(cowcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
// in kernel/vm.c
int
cowcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      panic("cowcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("cowcopy: page not present");
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    // 去除flag中的PTE_W，并且给父子的都安上没有PTE_W的flag
    flags = (flags & (~PTE_W));
    flags = (flags | PTE_COW);
    *pte = ((*pte) & (~PTE_W));
    *pte = ((*pte) | PTE_COW);
    if(mappages(new, i, PGSIZE, (uint64)pa, flags) != 0){
      goto err;
    }
    // 标记物理页的引用数增加
    acquire(&pages_lock);
    pages[pa/PGSIZE]++;
    release(&pages_lock);
  }
  return 0;
 err:
  // 失败了不能释放物理内存
  uvmunmap(new, 0, i / PGSIZE, 0);
  return -1;
}

处理缺页中断，标记引用数减少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
} else if(r_scause() == 15){
  // 只要求写入引起的缺页中断
  uint64 va = r_stval();
  pte_t *pte;
  uint64 pa;
  uint flags;

  if((pte = walk(p->pagetable, va, 0)) == 0)
      p->killed = 1;
  else if((*pte & PTE_V) == 0)
      p->killed = 1;
  else {
      pa = PTE2PA(*pte);
      flags = PTE_FLAGS(*pte);

      char* mem;
      if((mem = kalloc())!=0){
          memmove(mem, (char*)pa, PGSIZE);
          // 设置为新的物理页地址
          *pte = PA2PTE(mem);
          // 减少引用，引用归零时释放
          kfree((void*)pa);
          // 设置新的flag，标记为可写
          flags = (flags | PTE_W | PTE_COW);
          *pte = ((*pte) | flags);
      } else{
          p->killed = 1;
      }
  }
}

uvmunmap时减少引用数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
  uint64 a;
  pte_t *pte;
  // ...

  for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
    // ...
    uint64 pa = PTE2PA(*pte);
    if(do_free){
      kfree((void*)pa);
    }else {
      acquire(&pages_lock);
      if(((*pte) & PTE_COW) != 0){
          pages[pa/PGSIZE]--;
      }
      release(&pages_lock);
    }
    *pte = 0;
  }
}

修改walkaddr

在walkaddr中触发缺页中断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  // 在这里
  if((*pte & PTE_COW) != 0){
    if((*pte & PTE_W) == 0){
      // 触发缺页中断
      *(char*)va = 1;
      // 更新pa值
      pa = PTE2PA(*pte);
    }
  }
  return pa;
}
在kerneltrap内补上对缺页中断的处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void
kerneltrap()
{
  uint64 sepc = r_sepc();
  // ...
  if(r_scause() == 15){
    // 只要写入引起的缺页中断
    uint64 va = r_stval();
    pte_t *pte;
    uint64 pa;
    uint flags;

    if((pte = walk(p->pagetable, va, 0)) == 0)
        p->killed = 1;
    else if((*pte & PTE_V) == 0)
        p->killed = 1;
    else {
        // 注意，这个很重要！！！！！
        sepc += 4;
        pa = PTE2PA(*pte);
        flags = PTE_FLAGS(*pte);
                                 
        char* mem;
        if((mem = kalloc())!=0){
            memmove(mem, (char*)pa, PGSIZE);
            // 设置为新的物理页地址
            *pte = PA2PTE(mem);
            kfree((void*)pa);
            // 设置新的flag，标记为可写
            flags = (flags | PTE_W | PTE_COW);
            *pte = ((*pte) | flags);
        } else{
            p->killed = 1;
        }
    }
  } else if((which_dev = devintr()) == 0){
    printf("scause %p\n", scause);
    printf("sepc=%p stval=%p\n", r_sepc(), r_stval());
    panic("kerneltrap");
  }
  // ...
}