OS 学习记 之 XV6

XV6 是 MIT6.S081 操作系统这门课中使用的实验操作系统内核。它的作者之一就是大名鼎鼎的 Robert Morris，世界上第一个蠕虫病毒 Morris 就是出自他之手。XV6 传承了 Unix V6 操作系统内核的设计风格和结构，使用纯 C 语言编写，并运行在 RISC-V 处理器上。XV6 的代码不多，功能实现地也比较简单，性能和 Linux 也没办法比。但它麻雀虽小五脏俱全，非常适合学习操作系统的资料。在自学 MIT6.S081 这门课前，我虽然对操作系统有着大致的了解，但从未深入了解过它的一些实现细节，写这篇文章即是为了总结自己学到的知识，也是为了给其他学习路上的小伙伴一个参考。

什么是操作系统内核？

当刚拿到一台全新的计算机时，我们如果想要在上面编写程序运行，是非常麻烦的。比如你想读写硬盘上的一个文件，那你首先要查询你的硬盘所使用的协议，并根据它的协议编写代码，如果你换了个硬盘，或者想把代码放到其他计算机上运行，可能就不行了。除此之外，如果你有多个程序需要运行，你如何保证它们都能得到运行？如何保证程序 A 不会错误地修改程序 B 的内容？为此，操作系统诞生了。操作系统会在计算机启动之初接管所有硬件资源（CPU，内存，硬盘等），并与硬件相互配合，为用户程序提供一套简单易用的接口。用户程序运行在操作系统虚拟出来的理想世界里：读写文件，访问资源只需要调用操作系统提供的一组特殊函数（系统调用），也无需关心自己什么时候运行。这里需要特别注意的一点是操作系统的本质只是一个软件，与你编写的程序无异，光靠它自身也无法完成这么多 fancy 的特性，它必须与硬件紧密配合才行。

进程是操作系统内核提供的一个非常重要的抽象，它包含着一个程序所要运行所包含的所有东西，如：程序所打开的所有文件，运行栈，寄存器中存的状态，使用的内存等。这一个个抽象出来的进程，就是操作系统操控的单元，所有其他的特性都围绕这它展开。假如我们有两个用户程序，A 和 B，从逻辑上讲他们和操作系统之间的关系像这样：

          +------------+     +------------+
          |      A     |     |      B     |
          |            |     |            | 用户态
          +------------+     +------------+

------------------------------------------------------

          +----------------------------------+
          |                                  |
          |             kernel               | 内核态
          |                                  |
          +----------------------------------+

所有的用户程序运行在操作系统内核之上，彼此又相互独立，互不干扰。但如果从实际硬件实现上来看，这似乎是不可能的。前面提到，操作系统本身也只是一个软件，那么至少在单核处理器上，总要出现内核占用 CPU 运行一会儿，用户程序占用 CPU 运行一会儿的情况发生。从这个角度看用户程序根本不是运行在内核之上的。另外，物理内存在软件的角度下只是一个巨大的数组，那么用户程序之间，用户程序和内核之间使用的内存在不考虑间隙的情况下肯定是相邻的。那么如何保证不会出现访问其它程序内存这种恶意行为的发生呢？

诚然，如果只从软件的角度考虑这些特性确实很难实现，但我们在上文也提到，操作系统是软件和硬件相互配合的产物。接下来我们将看到更多的实现细节。

在此之前简要说下用户态和内核态是怎么在实际硬件上区分开的。RISC-V 处理器原生地支持三种模式：machine mode，supervisor mode 以及 user mode。machine mode 只在计算机刚启动时使用，主要用于配置计算机，内核态则对应着 supervisor mode，可以执行特权指令，如开启关闭中断等，而用户态则对应着 user mode，只能执行有限的一些指令。当满足某些特殊条件时，用户态的程序便可以跳到内核态，从 user mode 进入 supervisor mode，具体见下文。

为了达到上文所述的用户程序之间相互隔离的效果，操作系统内核提供了虚拟内存这一抽象。虚拟内存为每个程序都提供了一个独立的私有地址空间。有了虚拟内存，每个进程都认为自己的地址空间从 0x0 - 0xffffffff 结束，整个内存中除了内核就只有自己一个进程存在。当然虚拟内存顾名思义只是一个虚拟的视图，它没有对物理内存作任何的扩大。当用户程序访问虚拟内存中的一个地址时，它最终都要被映射到一个物理内存上。

实现虚拟内存最流行的办法是使用页表（page table）。首先，内核会将虚拟内存和物理内存都分成一份份大小相等的块，称为页（page），一般是 4KB。然后选取一个物理页作为一张表，其中保存着此进程的虚拟内存和物理内存之间的映射关系。我们将这个物理页的起始地址放到 RISC-V 处理器指定的一个寄存器中（stap），接着打开启用虚拟地址的开关，此后我们对地址的每次访问就都是虚拟地址了，硬件会根据我们页表中的映射关系将它翻译成真正的物理地址，无需我们手动干预。

因为每个进程都有自己独立的私有地址空间，也就是说进程 A 访问的 0x1234 和进程 B 访问的 0x1234 是不同的。那么每个进程就必须都要有自己的页表。因为页表逻辑上可以看作是一个哈希表，保存着“虚拟地址 <=> 物理地址”的映射关系，你自然不能有两个相同的 key，却指向不同的 value。当进程的执行发生切换时，我们需要将旧进程的页表地址保存下来，然后将页表寄存器设为新进程的页表起始地址。

接下来我们看一下内核的地址空间：

     virtual                           physical
+------------------+              +------------------+
|    trampoline    |              |                  |
+------------------+              |    unused        |
|    guard page    |              |                  |
+------------------+              |                  |
|    kstack0       |              |                  |
+------------------+              |                  |
|    guard page    |              |                  |
+------------------+              |                  |
|    kstack1       |              |                  |
+------------------+------------->+------------------+ 0x86400000
|    ...           |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|   free memory    |              |   free memory    |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
|                  |              |                  |
+------------------+              +------------------+
|   kernel data    +------------->|   kernel data    |
+------------------+              +------------------+
|   kernel text    +------------->|   kernel text    |
+------------------+ 0x80000000   +------------------+
|                  |              |                  |
|    driver        |              |    driver        |
|                  |              |                  |
+------------------+              +------------------+

首先在物理内存中我们从 0x80000000 开始以此放上内核的代码和内核的全局数据，后面所有可寻址的内存都属于内核可随意使用的空间，由内核的内存分配器（kalloc）管理。接着，我们将内核 0x80000000 - 0x86400000 之间的物理内存都一一直接映射到虚拟内存上（0x80000000 是内核代码的开始，0x86400000 则是物理可寻址的最大范围）。直接映射简化了物理内存的读写，比如向 kalloc 请求一个物理页，但是因为你启用了虚拟内存，他返回的实际是虚拟内存的地址，但是由于它两一一映射，所以不会有问题。

从上图我们可以看到物理内存的寻址范围是小于虚拟内存的。我们可以利用处在最顶层的虚拟内存将它们映射到一些更有用的地方。

• kstack。内核代码运行时使用的栈。每个进程都有自己的内核栈。
• guard page。保护页，不映射到任何物理页上，访问到它就说明内存栈溢出了。
• trapoline page。这个页被映射到虚拟内存的最顶端，在用户地址空间也都有这一份映射。它作为用户态进入内核态的跳板。

下面是普通的用户进程的地址空间：

+-------------+
|  trapoline  |
+-------------+
|  trapframe  |
+-------------+
|             |
|             |
|             |
|  heap       |
|             |
|             |
+-------------+
|  stack      |
+-------------+
|  guard page |
+-------------+
|             |
|   data      |
+-------------+
|             |
|   text      |
+-------------+  0x0

用户进程的地址空间要比内核的简单的多，它把代码和全局数据映射到从 0x0 开始的虚拟内存上。一定要注意这里是虚拟内存，它真正所处的位置要经过页表的转换，在物理内存上它应该处在上面说的 free memory 上。用户进程的最顶端仍然是 trapoline page，它和其他用户进程及内核一样，都映射到同一个物理页上。要设置一个 trapoline page 的原因会在下文详细展开。

我们这里说的中断严格意义上应该叫 trap。trap 具体分为三种：系统调用，异常和中断。我们继续通过最开始提出的问题解释它的使用场景：既然每个程序都要占用 CPU 资源运行一会儿，那么如果它不愿意退出怎么办？用户程序如何与内核沟通，获取自己想要的资源？

这些问题的答案还是在于硬件。RISC-V 处理器每隔一个固定的间隔就会触发一个时钟中断，强行停止当前运行的程序，并跳转到我们提前设置好的一个地址继续运行，将控制权重新交给内核。这个地址开始的代码并称为 trap handler，我们可以在这里进行对程序的调度，决定下一次运行哪个程序，这样就不会出现一个程序一直占着处理器资源不愿意退出的情况。

而为了实现用户空间到内核态的跳转，RISC-V 处理器提供了 ecall 系统调用指令（在 X86 上这个指令为 syscall）。我们使用的那些系统调用 C 函数，如 open，write，read 等，都是 ecall 系统调用的封装。在 XV6 下，它们长这样：

.global open
open:
 li a7, SYS_open
 ecall
 ret

可以看到 open 系统调用函数的实现仅仅只是一个 stub 代码，它没有做任何实际的工作，仅仅只是把 a7 寄存器设置为 SYS_open 这个 enum 值，然后执行 ecall 指令。而我们的处理器执行到 ecall 指令时，就会自动从用户态跳转到内核态，并开始执行 trap handler 的代码。在 XV6 中我们最终会执行到这里，下面只给出大致示意代码：

//
// handle an interrupt, exception, or system call from user space.
// called from trampoline.S
//
void
usertrap(void)
{
  struct proc *p = myproc();
  
  // save user program counter.
  p->trapframe->epc = r_sepc();
  // scause 寄存器中保存着引发此次 trap 的原因，如果它是 8，则说明为系统调用。
  if(r_scause() == 8){

    // 程序计数器保存着当前运行指令的位置，当我们执行完系统调用回来时，应指向下一条指令。
    p->trapframe->epc += 4;

    // an interrupt will change sstatus &c registers,
    // so don't enable until done with those registers.
    intr_on();
    // 系统调用的具体实现
    syscall();
  } else if (...) {
    // ...
  }
  // ...
}

系统调用的实现为：

void
syscall(void)
{
  int num;
  struct proc *p = myproc();
  // 从 a7 寄存器中读取实际要执行的是哪个系统调用
  num = p->trapframe->a7;
  if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
    // syscalls 数组保存着所有系统调用函数指针，我们通过 num 索引到实际代码并执行。
    // 返回值放在 a0 中。
    p->trapframe->a0 = syscalls[num]();
    acquire(&p->lock);
    // ...
  } else {
    // ...
  }
}

然而事实并没有上文说的那么简单。为了实现从用户态到内核态的跳转，我们还需要做其他很多事情。这一切的关键在于 RISC-V 处理器不会在用户态到内核态的切换中自动切换页表。也就是说，你的 trap handler 所在的位置必须可以被用户进程看到。因为这时页表没有切换，你只能看到用户进程的地址空间。所以，每个用户进程自己都有一个 trapoline page，和内核的 trapoline page 映射到同一个物理页上，trap handler 就放在那里。可以想象用户态和内核态是两个不同的宇宙，而 trapoline 则是沟通这两个宇宙的虫洞。在你进入内核世界之前，你当然还是在自己的宇宙，所以你需要某种方式在用户态宇宙中访问内核态宇宙，这个方式就是虫洞：它明明在用户态宇宙中，却也属于内核态宇宙的一部分。

此外，为了未来能够恢复用户进程的正常运行，我们还需要保存用户进程的各种状态，比如各个寄存器的值。这些信息会被放到 trapframe 中。下面用代码解释下详细过程：

1. 首先在创建进程的时候我们就会分配一个物理页作为 trapframe 并保存在进程的结构体中：

static struct proc*
allocproc(void)
{
  struct proc *p;
  // 寻找一个可用的进程
  for(p = proc; p < &proc[NPROC]; p++) {
    if(p->state == UNUSED) {
      goto found;
    }
    // ...
  }
  return 0;

// 如果找到了
found:
  // 请求一个物理页并把它转成 trapframe 的表示。
  if((p->trapframe = (struct trapframe *)kalloc()) == 0){
    // ...
  }
  // ...
}

1. 接着将它映射到合适的位置：

// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
pagetable_t
proc_pagetable(struct proc *p)
{
  pagetable_t pagetable;

  // An empty page table.
  pagetable = uvmcreate();
  if(pagetable == 0)
    return 0;
  
  // ...

  // map the trapframe just below TRAMPOLINE, for trampoline.S.
  if(mappages(pagetable, TRAPFRAME, PGSIZE,
              (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    // 失败处理。
  }

  return pagetable;
}

这样我们每每读写 trapoline 下面的那段虚拟内存，就相当于是在读写进程结构体中的 trapframe 字段。通过这种方式我们可以将所有寄存器中的值保存下来，供 struct proc* 进程结构体使用。

XV6 中 Lazy allocation 的实现

我们首先来看一下在 XV6 中用户程序向内核申请更多内存时会发生什么。顺着 XV6 中的调用链：

malloc -> morecore -> sbrk (syscall stub) -> sys_sbrk -> growproc -> uvmalloc 我们可以来到：

// Allocate PTEs and physical memory to grow process from oldsz to
// newsz, which need not be page aligned.  Returns new size or 0 on error.
uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  oldsz = PGROUNDUP(oldsz);
  // 将要分配的内存变成一定数量的 page。
  for(a = oldsz; a < newsz; a += PGSIZE){
    // 请求一个物理页。
    mem = kalloc();
    // 失败处理
    memset(mem, 0, PGSIZE);
    // 将虚拟地址 a 和物理地址 mem 映射到一起，在 pagetable 中保存映射关系。
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
        // 失败处理
    }
  }
  return newsz;
}

我们想象一个场景，如果我们请求了很大的内存，但是我们根本就没有使用到这么多资源，那么大多数物理页都被浪费了。为了优化这一点，我们可以在上面的代码中不实际请求物理页，而是简单地将各部分虚拟地址映射到 0 上，同时在页表中的对应页表项上做一个标记。而当我们的代码尝试访问这部分内存时，因为它对应的实际物理地址时非法的，所以会触发一个 trap，并跳到 trap handler 对应的代码中。因为当 trap 发生时硬件会将当时的虚拟地址保存在 stval 寄存器中，我们可以利用这点读出它，并在页表中寻找它所对应的页表项是否存在特定的标记。如果这些条件都满足，说明这个页是 lazy allocated 的，我们便可以在那时请求物理页并设置映射关系。

XV6 中进程的创建和 COW 优化

传统的 Unix 系统中进程的创建由 fork 和 exec 两个系统调用完成。fork 系统调用会创建一个新进程并复制父进程（用父进程填充子进程），而 exec 会读取硬盘上的一个 ELF （我们平时编译出来的可执行文件）并把它放到进程的虚拟内存中。

下面是 XV6 对于 fork 的大致实现：

// Create a new process, copying the parent.
// Sets up child kernel stack to return as if from fork() system call.
int
fork(void)
{
  // 分配一个进程
  if((np = allocproc()) == 0){
    return -1;
  }

  // 将父进程虚拟内存中的所有内存都深拷贝一份到自己的虚拟内存中。
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    // 失败处理
  }
  // ...

  // 子进程继承父进程打开的所有文件。
  for(i = 0; i < NOFILE; i++)
    if(p->ofile[i])
      np->ofile[i] = filedup(p->ofile[i]);
  
  // ...

  return pid;
}

同样的，深拷贝这些物理页是非常耗时的，而通常情况我们执行完 fork 后又会执行 exec 丢弃掉这些物理页。所以与 Lazy allocation 相似的，我们可以让父子进程都指向同一个物理页，并将页表项设为只读。当发生 trap 时，我们再根据去做实际的内存分配。唯一要特别小心的时我们要对这个物理页做引用计数，当没有虚拟页指向它时才做真正的释放（因为 fork 可能会多次调用，父进程 fork 了一个子进程，子进程又 fork 了一个孙子进程）。

XV6 的启动

上面说到操作系统内核本身也是一个软件，这没错，但它并不是一个普通的软件。如果我们要写一个内核的话，肯定不能只和普通软件一样直接用 clang/gcc 编译一下就行。因为编译器默认在 Linux 下面编出的可执行文件是 ELF 格式的，也就是 exec 能识别的格式。但是，处理器对于内核有着特殊的要求，我们必须手写 linker script，让代码按照要求去链接在一起，处理器才能跳转到正确的位置执行。比如在 XV6 中我们要求 _entry 这个符号必须在 0x80000000 这个地址上，因为这是处理器首先执行的位置。