MIT6.S081 Lab-3: Page Tables

Posted on Edited on
开始麻烦起来了啊......

可以说，相比于前两次lab，这次lab难度陡增大概相当于PVZ beta版轻松过白天草地之后在黑夜草地被橄榄球读报碾爆，对于这个门槛教授也没什么好办法

我们已经在尽力降低入门内核编程的难度了，但是接触到虚拟内存，它就是很难

但是个人觉得CG编程才是真的难，细节比这个多了一万倍

教授也表示相比于我们这种初学者来说可能自己多的就是一个debug经验。。。

个人认为这次lab的难点主要在于理解我们要干什么，明白要干什么才能比较容易地想明白怎么做，写代码自然就会比较好下手。

1. vmprint\text{1. vmprint}

要求是编写一个小函数vmprint，并且在exec中调用它，使其能够输示出当前进程三级页表的内容。这也是为debug提供了一个有用的工具虽然我还没用。

这个非常简单，基本上把walk函数照抄过来改改就行，毕竟说到底这就是个树的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void vmprint(pagetable_t pagetable)
{
  static int dep = 0;
  if(!dep) printf("page table %p\n", pagetable);
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if((pte & PTE_V) && ((pte & (PTE_R|PTE_W|PTE_X)) == 0)){
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte);
      for(int j = 1; j <= dep; j++)
        printf(".. ");
      printf("..%d: pte %p pa %p\n", i, pte, child);
      dep++;
      vmprint((pagetable_t)child);
      dep--;
    }
    else if(pte & PTE_V)
    {
      for(int j = 1; j <= dep; j++)
        printf(".. ");
      printf("..%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
    }
  }
}

2. Per-process kernel page table\text{2. Per-process kernel page table}

从这里开始，真正难起来了。

2.1. 为什么要做这个\text{2.1. 为什么要做这个}

我们在系统调用的时候，用户进程可能会把指针作为参数。但是这个指针是用户地址空间的虚拟地址，它既不是物理地址，也不是内核地址空间的虚拟地址。xv6\text{xv6}目前只有一个公用的内核页表，很可能没有有这个虚拟地址的正确映射，如果在开启了虚拟内存的情况下，在内核态直接对此指针解引用很可能报错或者返回一个错误的东西，这很好理解，我们用内核页表去翻译一个用户空间的虚拟地址显然是没什么意义的。

copyin函数负责了系统调用参数的传递。目前的xv6\text{xv6}为了解决这个问题，在copyin中首先使用walk函数模拟分页硬件翻译出传递的虚拟地址（使用用户进程页表）对应的物理地址，再进行处理。由于在内核地址空间中，内核的代码以及数据段的地址和物理地址是相同的，直接使用物理地址访存就行。

这很麻烦，我们希望能够在内核态下对用户地址空间的指针解引用得到正确结果，这就需要对每个用户进程都维护一个内核页表，将用户地址空间的映射也保存在里面。这样只要我们保证我们使用了正确的页表，就可以直接解引用。

为此，本次lab分了两步，第一步是为每个进程都创建内核页表并且正确完成页表的创建，切换以及释放，第二步是完成页表的维护，并简化copyin。本次任务也就是这里的第一步。

2.2. Coding\text{2.2. Coding}

有很多方法能够实现这个要求，个人的解决方法是共享除了进程内核栈以外的所有虚拟地址。当然，对于每个进程虚拟地址的维护放在下一步来完成。

在原来公用的内核页表中，对于每个进程都维护了内核栈。这一点也可以在代码中看清楚：在procinit函数中，将每个进程的内核栈地址都在内核页表中映射了一遍。这种因进程而异的地址我们抽离出来，单独在进程自己的内核页表中进行映射。而其他部分对所有进程来说都是一样的，共享就行（这里我们暂时不考虑用户地址空间本身的差异）。

因此我们首先可以写出一个创建进程内核页表的函数

1
2
3
4
5
6
7
pagetable_t kvminitproc(pagetable_t uvm)
{
  pagetable_t pt = kalloc();
  for(int i = 0; i < 512; i++)
    pt[i] = kernel_pagetable[i];
  return pt;
}

这个非常简单，内核自己有一份kernel_pagetable，它原来保存着所有进程内核栈的映射，现在我们把进程内核栈的映射留给进程内核页表来维护，内核自己的页表就是我们需要的公共部分，直接复制零级页表就行。这个函数只会在创建进程时调用。

下一步是完成内核栈的映射，这一步同样在创建进程时完成。原本这个事情是在procinit中一次性给所有进程分配完成的，现在我们将其移至allocproc中完成

1
2
3
4
5
6
7
8
9
10
11
void
procinit(void)
{
  struct proc *p;
  
  initlock(&pid_lock, "nextpid");
  for(p = proc; p < &proc[NPROC]; p++) {
      initlock(&p->lock, "proc");
  }
  kvminithart();
}
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
static struct proc*
allocproc(void)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state == UNUSED) {
      goto found;
    } else {
      release(&p->lock);
    }
  }
  return 0;

found:
  p->pid = allocpid();

  // Allocate a trapframe page.
  if((p->trapframe = (struct trapframe *)kalloc()) == 0){
    release(&p->lock);
    return 0;
  }

  // An empty user page table.
  p->pagetable = proc_pagetable(p);
  // Allocate a page for the process's kernel stack.
  // Map it high in memory, followed by an invalid
  // guard page.
  p->kvm = kvminitproc(p->pagetable);
  uint64 va = KSTACK((int)(p - proc));
  // now we map the kernel stack
  char *pa = kalloc();
  if(pa == 0)
    panic("kalloc");
  kvmmap_proc(p->kvm, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  p->kstack = va;
  if(p->pagetable == 0 || p->kvm == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  // Set up new context to start executing at forkret,
  // which returns to user space.
  memset(&p->context, 0, sizeof(p->context));
  p->context.ra = (uint64)forkret;
  p->context.sp = p->kstack + PGSIZE;

  return p;
}

其中的辅助函数kvmmap_proc可以对着kvmmap照猫画虎完成

1
2
3
4
5
void kvmmap_proc(pagetable_t kvm_pt, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kvm_pt, va, sz, pa, perm) != 0)
    panic("kvmmap_proc");
}

procinit现在只负责初始化所有进程锁，不再管理内核栈映射，所以在我们在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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  
  c->proc = 0;
  for(;;){
    // Avoid deadlock by ensuring that devices can interrupt.
    intr_on();
    
    int found = 0;
    for(p = proc; p < &proc[NPROC]; p++) {
      acquire(&p->lock);
      if(p->state == RUNNABLE) {
        // Switch to chosen process.  It is the process's job
        // to release its lock and then reacquire it
        // before jumping back to us.
        p->state = RUNNING;
        c->proc = p;
        if(p->kvm)
        {
          w_satp(MAKE_SATP(p->kvm));
          sfence_vma();
          swtch(&c->context, &p->context);
          // Process is done running for now.
          // It should have changed its p->state before coming back.
          kvminithart();
        }
        else panic("scheduler");
        c->proc = 0;

        found = 1;
      }
      release(&p->lock);
    }
#if !defined (LAB_FS)
    if(found == 0) {
      intr_on();
      asm volatile("wfi");
    }
#else
    ;
#endif
  }
}

需要注意的是在swtch以后要及时切换回kernel_pagetable也就是内核本身使用的页表。

进程结束之后我们要释放页表，由于我们除了内核栈以外的部分都是共享内核页表的，我们只需要释放掉零级页表就行，不需要把一二级页表以及物理页也释放掉，但是仅仅如此是不够的。内核栈的物理页不是共享的，是进程自己管理的，我们需要把内核栈的映射以及物理页都释放掉，这可以使用uvmunmap函数虽然从名字上看这个是给用户虚拟页表用的但是实际上并没有什么区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  if(p->kvm) 
  {
    uvmunmap(p->kvm, p->kstack, 1, 1);
    kfree((void*)p->kvm);
  }
  p->kvm = 0;
  p->pagetable = 0;
  p->sz = 0;
  p->pid = 0;
  p->parent = 0;
  p->name[0] = 0;
  p->chan = 0;
  p->killed = 0;
  p->xstate = 0;
  p->state = UNUSED;
}

2.3. 题外话: 内核自己的栈空间从哪儿来\text{2.3. 题外话: 内核自己的栈空间从哪儿来}

前面说了，内核页表给每个进程都维护了内核栈的映射，换句话说所有用户程序都有内核抽象出来的栈空间。但是内核自己运行也是需要栈的，这个栈在虚拟内存启用之前就应当存在，但是从道理上讲，操作系统是开机后第一个启动的程序，也是直接接触硬件的程序，没有其他任何程序或者机制能给操作系统内核也抽象一个栈空间出来。

实际上，xv6\text{xv6}内核通过一个很神奇的方式创建了自己的栈空间。在start.c中可以看到操作系统申请了一个数组stack0，在编译出来的entry.S中可以看到操作系统干的第一件事儿是把stack0的末尾地址加载到了sp(栈指针寄存器)中。

这就很好理解了，有了栈指针寄存器和一片连续的物理内存，这就搞出了一个栈。

3. Simplify copyin\text{3. Simplify copyin}

任务已经限制了用户虚拟内存地址不超过PLIC\text{PLIC}，这一定程度上简化了我们的工作，我们只需要考虑把用户部分的映射复制在内核页表PLIC\text{PLIC}以下的地址即可。

虽然如此，还是很难。。。在这里说按照我的做法的几个坑点吧

  1. 除了内核栈，任何时候都不要释放其他物理页，任何时候任何复制都只复制页表不复制物理页。除了释放进程，任何时候都不要释放页表的任何部分。

  2. 在复制页表的时候，尤其注意分配的单位是页，而虚拟地址可能没有按照页对齐。可以参照uvmalloc的方法来分配，这个地方如果错了，在测试sbrk的时候如果内存扩张少于一页就会出错。

改动的地方比较多，这里不全部列出来了，可以看github\text{github}