6.828(2021) - rqdmap

代码存放于 rqdmap/6.828-2021下的各个Branch中

Trap

RISC-V的trap机制

在RISC-V中，使用ecall、发生exception和产生中断会使得CPU的控制流改变，转而去执行特殊任务以处理这些事件,这些事件被称为trap.

为了完成trap处理事件,RSIC-V CPU提供了一系列控制寄存器,其中比较重要的有以下几个:

stvec: 内核将处理函数的地址写入该寄存器,riscv跳转到该地址处理事件
spec: riscv保存PC计数器在该寄存器中,后续通过sret指令(从trap中返回时调用)将原计数器写回pc
scause: riscv在此处写入一个数值表示trap的原因
sscratch: 在开始trap处理时进行辅助
sstatus: 该寄存器中的SIE比特位决定是否允许设备中断,SPP比特位表明该trap来自用户还态还是内核态,并以此决定sret返回的状态.

对于所有的trap类型而言,riscv硬件将会依次执行下述的过程:

如果trap是硬件终端并且SIE比特位被清空,不执行下述操作
通过设置SIE禁止中断
sepc <- pc
SPP <- 当前模式(用户态,内核态)
scause <- trap的原因
进入内核态
pc <- stvec
在新的pc上开始执行

CPU并不会切换内核页表,不进入内核栈,并且除了PC不保存任何其余的寄存器,这些工作交给程序来完成.

用户态的trap

在用户空间中发生trap后,trap经过的路径分别是uservec和usertrap,返回时则分别经过usertrapret和userret.

由于riscv不会切换页表,因而在进程的用户页表和内核页表中都在地址TRAMPOLINE中映射了trampoline页,该页中就包括了uservec用于处理trap.

当uservec(kernel/trampoline.S)运行时,首先将会保存32位用户寄存器.由于所有的寄存器都被使用了,因而使用sscratch作为中转.在进入用户空间前,内核首先将sscratch设置为进程的trapframe结构地址,该结构体有很多空间来存储用户所有的寄存器:

 1struct trapframe {
/*   0 */ uint64 kernel_satp;   // kernel page table
/*   8 */ uint64 kernel_sp;     // top of process's kernel stack
/*  16 */ uint64 kernel_trap;   // usertrap()
/*  24 */ uint64 epc;           // saved user program counter
/*  32 */ uint64 kernel_hartid; // saved kernel tp
/*  40 */ uint64 ra;
/*  48 */ uint64 sp;
/*  56 */ uint64 gp;
/*  64 */ uint64 tp;
/*  72 */ uint64 t0;
/*  80 */ uint64 t1;
/*  88 */ uint64 t2;
/*  96 */ uint64 s0;
/* 104 */ uint64 s1;
/* 112 */ uint64 a0;
/* 120 */ uint64 a1;
/* 128 */ uint64 a2;
/* 136 */ uint64 a3;
/* 144 */ uint64 a4;
/* 152 */ uint64 a5;
/* 160 */ uint64 a6;
/* 168 */ uint64 a7;
/* 176 */ uint64 s2;
/* 184 */ uint64 s3;
/* 192 */ uint64 s4;
/* 200 */ uint64 s5;
/* 208 */ uint64 s6;
/* 216 */ uint64 s7;
/* 224 */ uint64 s8;
/* 232 */ uint64 s9;
/* 240 */ uint64 s10;
/* 248 */ uint64 s11;
/* 256 */ uint64 t3;
/* 264 */ uint64 t4;
/* 272 */ uint64 t5;
/* 280 */ uint64 t6;
38};

在每个进程创建时,xv6都将为p->trapframe结构分配一页空间,并将其映射到TRAPFRAME地址所对应的虚拟空间.由于这是物理地址,因而内核可以通过内核页表直接使用.

uservec交换a_0和sscratch,此时a0就包含了trapframe的地址,从而可以利用a0的地址来保存所有的寄存器信息(包括原来的a0本身)

随后进入到usertrap中(kernel/trap.c),其主要功能是确定trap的原因并对其进行处理.其首先修改stvec,当在内核中时,trap将由kernelvec处理.

1w_stvec((uint64)kernelvec);

随后其将保存sepc在trapfram而中,这是由于usertrap后续可能会调用yield来短暂的放弃内核空间,新的线程可能会修改sepc的结果.

然后根据系统调用, 设备终端,或其余情况来分别处理.当处理系统调用时,需要额外给epc加4,这是由于riscv处理系统调用时会将程序指针指向ecall指令,但是用户在做完系统调用后还需要执行后续的指令….(ecall和4有啥关系捏一条指令的长度大概是)

1p->trapframe->epc += 4;

在返回用户态时,首先调用的是usertrapret(kernel/trap.c).该函数将更新stvec指向uservec,并为其填写好trapframe中的若干域的内容,恢复sepc的值.最后调用trampoline页中的userret函数,将TRAPFRAME的值存放在a0,将用户页表的指针存放在a1.

执行userret函数(kernel/trampoline.S)时,其利用a1更新satp寄存器来切换到用户页表.由于trampoline页在内核页表和用户页表中被映射到了相同的虚拟地址,因而uservec在更新了satp后仍然可以继续执行.(???) userret利用trapframe中的信息恢复各个寄存器的信息,最终执行sret来回到用户态.

trampoline页的映射

在vm.c和proc.c文件中,我们可以看到内核页表和用户页表对于trampoline的映射,其中trampoline是定义在汇编中的物理地址.

确实是将同一个地址映射到了相同的虚拟地址中(TRAMPOLINE).

 1// kernel/vm.c:
 2// map the trampoline for trap entry/exit to
 3// the highest virtual address in the kernel.
 4kvmmap(kpgtbl, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
 5
 6// kernel/proc.c:
 7// map the trampoline code (for system call return)
 8// at the highest user virtual address.
 9// only the supervisor uses it, on the way
10// to/from user space, so not PTE_U.
11if(mappages(pagetable, TRAMPOLINE, PGSIZE,
12            (uint64)trampoline, PTE_R | PTE_X) < 0){
13  uvmfree(pagetable, 0);
14  return 0;
15}

trapframe页的映射

在每个进程创建(kernel/proc.c/allocproc())时,会使用kalloc对其进行分配空间,而kalloc是分配的物理地址,内核可以直接使用.

1// Allocate a trapframe page.
2if((p->trapframe = (struct trapframe *)kalloc()) == 0){
3  freeproc(p);
4  release(&p->lock);
5  return 0;
6}

内核态的trap

当内核代码产生trap后,内核将stvec指向kernelvec(kernel/kernelvec.S). 由于xv6正运行在内核中,因而kernelvec可以使用satp指向的页表,也可以使用栈指针指向的内核栈.

在kernelvec中,首先将32个寄存器的信息全部压入栈中,随后调用kerneltrap(trap.c). kerneltrap只处理两类trap:硬件中断和异常.如果该中断来自于一个时钟,则将调用yield(??? 后续章节会解释),当其余线程yield后再继续执行原线程.

当kerneltrap工作完成后,则将返回到kernelvec中,从栈用恢复所有的寄存器信息后调用sret恢复中断的内核代码.

COW和懒分配

COW(copy-on-write). 在fork时,不立刻复制一份物理页给子进程,而是将这些物理页以可读的权限映射给父子进程.只有当其中某个进程希望对其进行写操作时,才复制一份新的具有写权限的物理页给该进程.
懒分配. 应用调用sbrk请求更多内存空间时,内核仅仅记录下来需要的数量,但并不是实际分配物理内存,也不创建PTE.只有当发生页错误时,内核才实际分配物理页并映射到页表中.

Lock

xv6有两种锁：自旋锁和睡眠锁

自旋锁

这是一种错误的自旋锁实现：

 1void
 2acquire(struct spinlock *lk) // does not work!
 3{
 4    for(;;) {
 5        if(lk->locked == 0) {
 6            lk->locked = 1;
 7            break;
 8        }
 9    }
10}

在多处理器环境下，如果两个处理器同时通过了if判断，那么便会出现一个锁被多个CPU获取的情况，为此我们应该保证其为原子操作。

Xv6的acquire函数使用C库的调用__sync_lock_test_and_set，该调用最终使用了amoswap r, a指令，这个指令会读取地址a将寄存器r的内容写入该地址，再将a地址的内容写回寄存器r,从而达到交换内存地址内容和寄存器内容的作用，该交换指令由硬件保证只会被一个CPU使用；该调用的返回值为交换前的原始值。

通过该方式，acquire方式将不断循环的执行该C调用：每一轮调用都会将1写入到locked标志中，并检查原始locked标志的内容是多少；如果原始为0,那么当前CPU将跳出循环，获得锁，且锁的标志为1；如果原始为1,那么其余CPU正在持有锁，重复写入1到该标志也不影响任何情况。

当锁获得后，在cpu字段中写入当前cpu，便于后续调试用。

 1// Acquire the lock.
 2// Loops (spins) until the lock is acquired.
 3void
 4acquire(struct spinlock *lk)
 5{
 6  push_off(); // disable interrupts to avoid deadlock.
 7  if(holding(lk))
 8    panic("acquire");
 9
10  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
11  //   a5 = 1
12  //   s1 = &lk->locked
13  //   amoswap.w.aq a5, a5, (s1)
14  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
15    ;
16
17  // Tell the C compiler and the processor to not move loads or stores
18  // past this point, to ensure that the critical section's memory
19  // references happen strictly after the lock is acquired.
20  // On RISC-V, this emits a fence instruction.
21  __sync_synchronize();
22
23  // Record info about lock acquisition for holding() and debugging.
24  lk->cpu = mycpu();
25}

锁的释放也类似，清空cpu记录后通过原子操作amoswap释放锁。

 1// Release the lock.
 2void
 3release(struct spinlock *lk)
 4{
 5  if(!holding(lk))
 6    panic("release");
 7
 8  lk->cpu = 0;
 9
10  // Tell the C compiler and the CPU to not move loads or stores
11  // past this point, to ensure that all the stores in the critical
12  // section are visible to other CPUs before the lock is released,
13  // and that loads in the critical section occur strictly before
14  // the lock is released.
15  // On RISC-V, this emits a fence instruction.
16  __sync_synchronize();
17
18  // Release the lock, equivalent to lk->locked = 0.
19  // This code doesn't use a C assignment, since the C standard
20  // implies that an assignment might be implemented with
21  // multiple store instructions.
22  // On RISC-V, sync_lock_release turns into an atomic swap:
23  //   s1 = &lk->locked
24  //   amoswap.w zero, zero, (s1)
25  __sync_lock_release(&lk->locked);
26
27  pop_off();
28}

可重入(re-entrant)

可重入锁允许一个线程在拥有某个锁的情况下再次申请获得该锁。

中断处理函数

在中断处理函数获得锁之前，必须要关闭本地中断。否则，持有锁的内核代码会被中断处理程序打断，接着可能去争用这个已经被持有的自旋锁。结果导致，中断处理函数自旋，等待该锁重新可用，但是锁的持有者在该中断处理程序执行完毕之前不可能运行，这就成为了双重请求死锁。注意，需要关闭的只是当前处理器上的中断。因为中断发生在不同的处理器上，即使中断处理程序在同一锁上自旋，也不会妨碍锁的持有者（在不同处理器上）最终释放。

指令执行顺序

为了获得高性能，许多编译器和CPU并不会按照代码的实际顺序执行，这有可能会导致并发任务的错误。

1l = malloc(sizeof *l);
2l->data = data;
3acquire(&listlock);
4l->next = list;
5list = l;
6release(&listlock);

如果不加限制，编译器或CPU将L4的语句放在了release后的位置，那么就会有一小段窗口期其余处理器可能可以获得锁并且发现更新后的列表拥有一个为初始化的next字段。

为了解决CPU、硬件对代码重排序的问题，xv6使用__sync_synchronize()函数于release和require中。该函数是一个内存屏障，其告知编译器和CPU不得将内存的加载、写入操作的重排序超过该屏障。

睡眠锁

睡眠锁在等待时会自动释放CPU资源，并且允许开中断使得其余线程开始执行。具体将在下一节讨论。

多路复用

多路复用一般有几个难点：

如何进行进程切换？
如果保证切换对用户透明？
所有的CPU在共享的进程集合中进行进程切换，如何设计加锁方案？
进程退出时，如何释放自己的内核栈等资源？
多核处理器中，每一个核都要记住自己的进程信息以便于系统调用能够影响那个正确的进程内核状态。
sleep和wakeup函数允许续进程放弃CPU并且等待其余进程、中断来再次唤醒他，需要避免竞争以防唤醒信号的丢失。

上下文切换

callee and caller saved registers

参考 https://stackoverflow.com/questions/9268586/what-are-callee-and-caller-saved-registers

一个caller-saved寄存器通常用于保存一些暂时的量，并且不强制要求在函数调用过程中不被改变；而一个callee-saved寄存器则用于保存一些长生命周期的值，应当在函数调用过程中不被改变。

以usertrap为例，当产生一个时钟中断后，将调用yield()函数；yield函数调用sched函数，进而调用swtch函数；swtch函数将当前上下文环境存储到p->context中，并读取mycpu()->context环境，这个cpu的上下文环境预先定义好始终指向scheduler函数（实际上是切换到cpu的上下文，此时就会开始执行schudule（大概））swtch函数只存储callee-save寄存器，c编译器会自动生成caller-saved寄存器存储的代码。其不保存pc寄存器，但是会保存ra寄存器，该寄存器指向swtch的返回地址，即调用swtch函数的地址位置。

 1// Switch to scheduler.  Must hold only p->lock
 2// and have changed proc->state. Saves and restores
 3// intena because intena is a property of this
 4// kernel thread, not this CPU. It should
 5// be proc->intena and proc->noff, but that would
 6// break in the few places where a lock is held but
 7// there's no process.
 8void
 9sched(void)
10{
11  int intena;
12  struct proc *p = myproc();
13
14  if(!holding(&p->lock))
15    panic("sched p->lock");
16  if(mycpu()->noff != 1)
17    panic("sched locks");
18  if(p->state == RUNNING)
19    panic("sched running");
20  if(intr_get())
21    panic("sched interruptible");
22
23  intena = mycpu()->intena;
24  swtch(&p->context, &mycpu()->context);
25  mycpu()->intena = intena;
26}
27
28// Give up the CPU for one scheduling round.
29void
30yield(void)
31{
32  struct proc *p = myproc();
33  acquire(&p->lock);
34  p->state = RUNNABLE;
35  sched();
36  release(&p->lock);
37}

…占坑不填…

本节Lab的基本任务都比较简单，但是riscV内核到底是如何进行切换的仍然稍微有一些迷茫，期待UTLK解惑吧。。。