MIT 6.s081 Lab3: Page Table

MIT 6.s081
,

lab3 属实是重量级，折磨了我好长时间。做 lab3 之前一定一定一定要先仔细的看 xv6 book 和任务指导书，不然就是无头苍蝇乱碰了。

同时还有 kernel/memlayout.h、kernel/vm.c、kernel/kalloc.c 都需要认真看看相关代码。

Lab3 就是要给每一个进程都添加一个自己的内核页表，并且把用户页表中的映射给复制进去，在进程进入内核态之后，可以使用进程中的内核页表，通过硬件来进行寻址。在实现这个 lab 之前，xv6 只能从用户态传入一个地址，但是这个地址在内核中是无法使用的，因为内核页表中没有这个映射，所以只能通过软件模拟 MMU 来进行寻址，效率不高。

Print a page table (easy)

任务书上说是可以帮助后面的 debug，但是我没有用到。不过可以做到对于 xv6 的页表有一个初步的认识。

xv6 的页表如上图所示。在 CPU 的 satp 寄存器中存储了第二层页表的物理地址，它里面存储了 512 条 PTE（page table entry），每条 PTE 的高 44 位 PPN 用于计算出下一层页表的物理地址或者拼接出存储数据的物理地址。一条虚拟地址被分成了 L2、L1、L0 各 9 bit，对应着三层页表，分别指出三层页表中的 PTE。还有 offset，占 12 bit，用于和第 0 层的 PPN 拼接得到数据的物理地址。

所以要打印这个页表，我们就要从第二层开始，逐层遍历 PTE 并打印，然后取出下一层的页表开始遍历打印，直到最低层。

pagetable_t 其实就是一个 uint64 类型的指针，其实也就是一个数组，数组中有 512 个元素对应 512 条 PTE，进行遍历的过程中要判断 PTE 是否有效，无效就不打印，还要判断 PTE 是否指向下一层的页表，如果是就将 PTE 转化成下一层页表的物理地址，递归到下一层进行打印，否则就直接打印。根据任务指导书，具体如何判断 PTE 参考 kernel/vm.c#freewalk 函数。

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
void
_vmprint(pagetable_t pagetable, int level) {
  if (level == -1) {
    return;
  }
  int i;
  for (i = 0; i < 512; i++) {
    pte_t pte = pagetable[i];
    if (pte & PTE_V) {
      if (level != 0 && !((pte & (PTE_R | PTE_W | PTE_X)) == 0)) continue;
      uint64 pa = PTE2PA(pte);
      int j;
      for (j = level; j <= 2; j++)
      {
        if (j == 2) {
          printf("..");
        } else {
          printf(".. ");
        }
      }
      printf("%d: pte %p pa %p\n", i, pte, pa);
      _vmprint((pagetable_t) pa, level-1);
    }
    continue;
  }
}

void
vmprint(pagetable_t pagetable) {
  printf("page table %p\n", pagetable);
  _vmprint(pagetable, 2);
}

A kernel pagetable per process (hard)

xv6 中，每个进程都有一个自己的用户空间页表，这个页表只包含该进程的用户地址空间的映射。在内核中有一个单独的内核页表，所有的进程进入内核态后，都是用的是这个内核页表。所以用户地址在内核中是无法使用的，因为内核页表中没有对该地址的映射，只能通过 walk 来模拟 MMU 将用户虚拟地址再转化为物理地址使用。

所以部分的任务就是给每个进程都弄一个自己的内核页表，并且在下个部分将用户空间页表中的映射复制到自己的内核页表中，这样在进入内核态的时候就可以直接使用这些映射了。

首先，我们在 strcut proc 中添加一个 kpagetable 变量来存储内核页表。

1
pagetable_t kpagetable;      // Process's kernel pagetable

我们需要在创建进程的时候给他复制一份内核页表，内核页表是通过 kernel/vm.c#kvminit 初始化，在其中使用 kernel/vm.c#kvmmap 进行一些映射，我们需要修改版的 kvminit 函数和 kvmmap 函数来对进程的内核页表进行修改。因为这两个函数只是针对全局的 kernel_pagetable，没办法传参数。照着写就可以了。

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
void
ukvmmap(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(pagetable, va, sz, pa, perm) != 0)
    panic("ukvmmap");
}

pagetable_t
proc_kpagetable(struct proc *p) 
{
  pagetable_t pagetable;
  pagetable = uvmcreate();
  if (pagetable == 0) return 0;

  // uart registers
  ukvmmap(pagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  ukvmmap(pagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT
  ukvmmap(pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  ukvmmap(pagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);

  // map kernel text executable and read-only.
  ukvmmap(pagetable, KERNBASE, KERNBASE, (uint64) etext - KERNBASE, PTE_R | PTE_X);

  // map kernel data and the physical RAM we'll make use of.
  ukvmmap(pagetable, (uint64) etext, (uint64) etext, PHYSTOP - (uint64) etext, PTE_R | PTE_W);

  // map the trampoline for trap entry/exit to
  // the highest virtual address in the kernel.
  ukvmmap(pagetable, TRAMPOLINE, (uint64) trampoline, PGSIZE, PTE_R | PTE_X);

  return pagetable;
}

接着在 kernel/proc.c#allocproc 中调用上述函数来初始化进程的内核页表。

1
2
3
4
5
6
7
// ... kernel/proc.c#allocproc
p->kpagetable = proc_kpagetable(p);
  if (p->kpagetable == 0) {
  freeproc(p);
  release(&p->lock);
  return 0;
}

按照任务说明书，我们需要将进程的内核栈映射到内核页表中，原本内核栈的初始化是在 kernel/proc.c#procinit 中，现在我们将内核栈放在 allocproc 中来分配，就跟在内核页表初始化之后。

1
2
3
4
5
6
7
// ... kernel/proc.c#allocproc
char *pa = kalloc();
if(pa == 0)
  panic("kalloc");
uint64 va = KSTACK((int) (p - proc));
ukvmmap(p->kpagetable, va, (uint64) pa, PGSIZE, PTE_R | PTE_W);
p->kstack = va;

到这里内核页表就初始化完成了。接下来修改 kernel/proc.c#scheduler 函数，因为当前每个进程有了自己的内核页表，那么在进入内核态之后就要使用自己的页表，也就是将第二层页表的物理地址放入 satp 寄存器中，在进程执行完之后一定要把全局的内核页表再设置回去。

1
2
3
4
5
6
7
// ... kernel/proc.c#scheduler
p->state = RUNNING;
c->proc = p;
w_satp(MAKE_SATP(p->kpagetable));
sfence_vma(); // 使用 vma 指令清除 TLB 缓存，否则可能访问到其他进程的数据！
swtch(&c->context, &p->context);
kvminithart(); // 在切换完毕之后使用 kvminithart 将全局内核页表设置会 satp

接下来就是释放页表空间了，这一部分也卡了我很久。在 kernel/proc.c#freeproc 中是释放进程的逻辑，我们要在这里面添加释放进程的内核页表的逻辑。

1
2
3
if(p->kpagetable)
  proc_freekpagetable(p, p->sz);
p->kpagetable = 0;

proc_freekpagetable 函数的实现主要干了两件事，第一是释放掉进程的内核栈，第二是取消了进程的内核页表中的映射，但是一定不能释放映射指向的物理地址！因为进程的内核页表仅仅只是复制了映射。我们只释放页表本身的空间。

仿照 freewalk 实现了 proc_freekpagetable 函数，只释放掉页表页，而不释放最低层 PTE 指向的物理内存，具体做法是判断 PTE 是否还是指向下一层页表，如果是才进到下一层释放，这样就不会进到数据页中去释放内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
void freekpagetable(pagetable_t pagetable) {
  int i;
  for (i = 0; i < 512; i++)
  {
    pte_t pte = pagetable[i];
    if ((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) { // 判断是否还有下一层
      uint64 child = PTE2PA(pte);
      freekpagetable((pagetable_t) child);
      pagetable[i] = 0;
    }
  }
  kfree((void*) pagetable);
}

到这里 usertests 测试就可以通过了。

Simplify copyin/copyinstr (hard)

这部分就是在刚刚给进程添加的内核页表中添加用户地址空间的映射。那么在内核中就可以直接使用用户空间地址，使用硬件 MMU 进行寻址，相比于用软件模拟 MMU 寻址效率更高。目标就是将 kernel/vm.c#copyin 和 kernel/vm.c#copyinstr 分别替换成 kernel/vmcopyin.c#copyin_new 和 kernel/vmcopyin.c#copyinstr_new。所以我们要在修改用户页表的每一处也对进程的内核页表都进行同步才能做到这一点。

首先仿照 kernel/vm.c#uvmcopy 实现 kernel/vm.c#uvmcopypg 用以拷贝页表，因为 uvmcopy 是在 fork 的时候把父进程的内存拷贝给子进程，所以它新分配了物理内存给子进程，所以我们不能直接用，因为内核页表仅仅只是拷贝映射，而拷贝映射的空间在 allocproc 时就已经分配了。

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
int
uvmcopypg(pagetable_t pagetable, pagetable_t kpagetable, uint64 sz, uint64 start)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;

  for (i = PGROUNDUP(start); i < sz; i+=PGSIZE){
    if((pte = walk(pagetable, i, 0)) == 0)
      panic("uvmcopypg: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopypg: page not present");
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte) & ~PTE_U; // 一定要设置 U 标识符，否则内核无法访问这个 PTE

    if(mappages(kpagetable, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
  }

  return 0;

  err:
  uvmunmap(kpagetable, PGROUNDUP(start), (i - PGROUNDUP(start)) / PGSIZE, 0);
  return -1;
  
}

接下来按照提示，分别在 kernel/proc.c#userinit、kernel/proc.c#fork、kernel/exec.c#exec、kernel/proc.c#growproc 中添加同步内核页表的代码。

userinit

1
2
3
4
5
6
// ...
// 在进程页表初始化完成之后拷贝页表
// copy pagetable's mappings to kpagetable, but don't copy pa.
if (uvmcopypg(p->pagetable, p->kpagetable, p->sz, 0) < 0) {
  panic("uvmcopypg: fail to copy pagetable to kpagetable!");
}

fork

1
2
3
4
5
6
7
// ...
// 在子进程拷贝完父进程的用户页表后，再将子进程的用户页表拷贝给内核页表
if(uvmcopypg(np->pagetable, np->kpagetable, p->sz, 0) < 0) {
  freeproc(np);
  release(&np->lock);
  return -1;
}

exec

1
2
3
4
5
6
7
8
9
10
11
12
// ...
safestrcpy(p->name, last, sizeof(p->name));

// 在成功生成 user image 后，先清除原本的内核页表，再将新的用户页表拷贝到内核页表
uvmunmap(p->kpagetable, 0, PGROUNDUP(oldsz) / PGSIZE, 0);
if (uvmcopypg(pagetable, p->kpagetable, sz, 0) < 0) {
  goto bad;
}

// Commit to the user image.
oldpagetable = p->pagetable;
p->pagetable = pagetable;

growproc

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
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
    // 在进程空间扩容并且进程用户页表扩容之后，将扩容的那部分数据拷贝到内核页表
    if (uvmcopypg(p->pagetable, p->kpagetable, sz, sz-n)< 0) {
      // 如果拷贝失败了，那么进程就要缩回到原本的容量
      sz = uvmdealloc(p->pagetable, sz, sz-n);
      return -1;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
    // 在进程空间缩小后并且进程页表页表也缩小之后，将缩小的那部分映射给去掉
    int npages = (PGROUNDUP(sz-n) - PGROUNDUP(sz)) / PGSIZE;
    uvmunmap(p->kpagetable, PGROUNDUP(sz), npages, 0);
  }
  p->sz = sz;
  return 0;
}

由于操作系统最低的虚拟地址在 0xC000000，也就是 PLIC 寄存器的地址，如果用户地址空间范围到了 0xC000000 之上，那么就会覆盖掉内核的数据。我们要限制用户地址空间不能超过这个地址。所以我们在 growproc 中判断，如果新的 sz 大于等于 PLIC 了，那么就直接返回 -1 而不执行扩容。

最后就是一个很大的坑，也就是上述全部实现之后会报 remap 的错误，返回去看 xv6 book 之后才发现，在 PLIC 之下还有一段数据是 CLINT，所以如果映射到了这一段，而这里是我们在初始化内核页表的时候就进行映射了的，所以会报 remap 错误。

查看 start.c 后发现 CLINT 仅在内核启动的时候需要，也就是说用户进程在内核中并不需要使用到这一段，所以干脆直接在初始化内核页表的时候不进行这部分的映射了。

测试结果

总结

这个 lab3 确实难度不低，首先要对 xv6 的页表机制有一个比较深入的理解，然后 DEBUG 也比较难，我除了用 gdb 调试之外，还用了很多 panic 来尽早的发现是在哪里错了。如果不仔细读 xv6 book 把他理解清除的话大抵是做不出来了吧。