这个实验是至今为止做的最难的一个了，做了估计有一礼拜。。。。主要的坑有两个，也是重要的知识点，下面会详细记录。

为了方便在虚拟地址与物理地址之间的转换操作，做出以下宏定义：

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
#define PGSIZE 4096 // bytes per page
#define PGSHIFT 12  // bits of offset within a page

#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))

#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access

// shift a physical address to the right place for a PTE.
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)

#define PTE2PA(pte) (((pte) >> 10) << 12)

#define PTE_FLAGS(pte) ((pte) & 0x3FF) // PTE 前 10 位为标志位

// extract the three 9-bit page table indices from a virtual address.
#define PXMASK          0x1FF // 9 bits
#define PXSHIFT(level)  (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK) // 找 PPN （level）

// one beyond the highest possible virtual address.
// MAXVA is actually one bit less than the max allowed by
// Sv39, to avoid having to sign-extend virtual addresses
// that have the high bit set.
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))

typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs

页表机制

现在的 OS 都有页表机制。因为这是解决进程间独立，提高安全性和可维护性的高效做法。

页表机制是由软硬件共同实现的，这句话在之前就听说过，做了实验之后得到了深刻的理解。satp 这个寄存器就是实现分页机制最重要的一个寄存器。具体要去看 The RISC-V Instruction Set Manual
Volume II: Privileged Architecture 对应章节。总之对于 Sv39 地址空间的 riscv64 实现，给出一个虚拟地址，硬件会根据 satp 来将其映射成物理地址，可以用公式 PA = F(satp, VA) 来表示：

分页机制过程

这一步从虚拟地址到物理地址的地址转换是硬件帮我们完成的，那软件要做什么事呢？想一想，页表是需要人工创建出来的呀，所以软件就是在做创建页表并建立映射的工作。

1. Print a page table

实验说明：写一个函数，实现打印页表的功能。

函数签名：void vmprint(pagetable_t pagetable);

只要仔细查看 39 位虚拟地址的结构以及 PTE（页表条目）的结构，再对根页表做遍历就行了。

因为一个 PTE 占用 8 字节，所以一页页表只能存放 512 个 PTE，虚拟地址前 27 位的每 9 位来索引页表中的 PTE。经过三级索引后就能得到物理地址。

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
void vmprint(pagetable_t pagetable) {
    printf("page table %p\n", pagetable);
    int ptes_per_table = 512;
    for (int i = 0;i < ptes_per_table;++i) {
        uint64 *va = (uint64 *)(pagetable + i);
        pte_t l2pte = (pte_t)*va;
        // if pte is invalid
        if ((l2pte & PTE_V) == 0)
            continue;
        pagetable_t l2pagetable = (pagetable_t) PTE2PA(l2pte);
        printf("..%d: pte %p pa %p\n", i, l2pte, l2pagetable);
        for (int j = 0;j < ptes_per_table;++j) {
            uint64 *va = (uint64 *)(l2pagetable + j);
            pte_t l1pte = (pte_t) *va;
            if ((l1pte & PTE_V) == 0)
                continue;
            pagetable_t l1pagetable = (pagetable_t) PTE2PA(l1pte);
            printf(".. ..%d: pte %p pa %p\n", j, l1pte, l1pagetable);
            for (int k = 0;k < ptes_per_table;++k) {
                uint64 *va = (uint64 *)(l1pagetable + k);
                pte_t l0pte = (pte_t) *va;
                if ((l0pte & PTE_V) == 0)
                    continue;
                printf(".. .. ..%d: pte %p pa %p\n", k, l0pte,
                        PTE2PA(l0pte));
            }
        }
    }
}

2. A kernel page table per process

实验说明：为每一个进程都分配一个内核页表。

这个实验是为 lab 3 做铺垫的。所以也不是很难。

总共分两个步骤

  1. 分配一个进程时进行页表的分配和映射
  2. 结束一个进程时进行页表的解映射和销毁

一个进程内核页表，包括以下映射：

  • UART0，VIRTIO0，PLIC
  • 内核代码段
  • 内核数据段以及 RAM
  • TRAMPOLINE
  • 内核栈

不做 CLINT 的映射是因为，xv6 OS 限制了用户进程的最大虚拟地址必须小于内核最低处虚拟地址（0xC000000），而 CLINT 在虚拟地址 （0x2000000）处，因此会与用户进程虚拟地址冲突，因此不能对 CLINT 进行映射。

首先在 struct proc 中添加一个进程内核页字段。

1
2
3
4
5
6
7
8
9
kernel/proc.h:

struct proc {
···
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  // my code:
  pagetable_t proc_kern_pt;
};

然后学着 kvminit 函数实现一个 proc_kvminit 为 proc_kern_pt 创建内核映射。

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
kernel/vm.c:

//my code:
pagetable_t
proc_kvminit()
{
  pagetable_t pkpt = (pagetable_t) kalloc();
  memset((char *)pkpt, 0, PGSIZE);

  // uart registers
  mappages(pkpt, UART0, PGSIZE, UART0, PTE_R | PTE_W);

  // virtio mmio disk interface
  mappages(pkpt, VIRTIO0, PGSIZE, VIRTIO0, PTE_R | PTE_W);

  // CLINT
  // mappages(pkpt, CLINT, 0x10000, CLINT, PTE_R | PTE_W);

  // PLIC
  mappages(pkpt, PLIC, 0x400000, PLIC, PTE_R | PTE_W);

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

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

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

现在只剩下内核栈还没有完成映射了。

OS 为每一个进程都分配了一页内核栈，用于该进程陷入内核后执行内核函数。

阅读 procinit 函数来理解内核是如何给每个进程分配内核栈并做映射的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
kernel/proc.c:

 // initialize the proc table at boot time.
 void
 procinit(void)
 {
   struct proc *p;

   initlock(&pid_lock, "nextpid");
   for(p = proc; p < &proc[NPROC]; p++) {
       initlock(&p->lock, "proc");

       // Allocate a page for the process's kernel stack.
       // Map it high in memory, followed by an invalid
       // guard page.
       char *pa = kalloc();
       if(pa == 0)
         panic("kalloc");
       uint64 va = KSTACK((int) (p - proc));
       kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
       p->kstack = va;
   }
   kvminithart();
 }

由于我们会在每个进程的地址空间中（由 proc_kern_pt 确定）做内核栈的映射，因此这里就不需要为内核页表做映射了。所以对以上代码进行修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// initialize the proc table at boot time.
void
procinit(void)
{
  struct proc *p;

  initlock(&pid_lock, "nextpid");
  for(p = proc; p < &proc[NPROC]; p++) {
      initlock(&p->lock, "proc");

      // my code:
      // Allocate a page for the process's kernel stack.
      // Map it high in memory, followed by an invalid
      // guard page.
//      char *pa = kalloc();
//      if(pa == 0)
//        panic("kalloc");
//      uint64 va = KSTACK((int) (p - proc));
//      kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
//      p->kstack = va;
  }
//  kvminithart();
}

我们在 procalloc 函数中添加分配内核栈并做映射的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
kernel/proc.c:
 static struct proc*
 allocproc(void)
 {
	···
 found:
   p->pid = allocpid();

   // my code:
   p->proc_kern_pt = proc_kvminit();
   char *pa = kalloc();
   if(pa == 0)
       panic("kalloc");
   uint64 va = TRAMPOLINE - 2 * PGSIZE;
   mappages(p->proc_kern_pt, va, PGSIZE, (uint64)pa, PTE_R | PTE_W);
   p->kstack = va;
   ///////////////////////////////////////////////


这里把内核栈映射到 va = TRAMPOLINE - 2 * PGSIZE 还有一个好处，那就是如果栈溢出了，由于 va 以下的虚拟地址未作映射，会导致一个异常，以此来防止栈溢出而不自知。

然后实现在进程结束时解除映射并释放进程内核页表的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
kernel/proc.c:

 // my code:
 extern char etext[];
 void
 proc_freekpagetable(pagetable_t pagetable, uint64 kstack, uint64 sz) {
   uvmunmap(pagetable, UART0, 1, 0);
   uvmunmap(pagetable, VIRTIO0, 1, 0);
   // uvmunmap(pagetable, CLINT, 0x10000 / PGSIZE, 0);
   uvmunmap(pagetable, PLIC, 0x400000 / PGSIZE, 0);
   uvmunmap(pagetable, KERNBASE, ((uint64)etext - KERNBASE) / PGSIZE, 0);
   uvmunmap(pagetable, (uint64)etext, (PHYSTOP - (uint64)etext) / PGSIZE, 0);
   uvmunmap(pagetable, TRAMPOLINE, 1, 0);
   // uvmunmap(pagetable, 0, PGROUNDUP(sz) / PGSIZE, 0);
   uvmunmap(pagetable, kstack, 1, 1);
   freewalk(pagetable);
 }

在 freeproc 函数中进行页表的释放：

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
kernel/proc.c:

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);
  // my code:
  if (p->proc_kern_pt)
      proc_freekpagetable(p->proc_kern_pt, p->kstack, p->sz);
  p->proc_kern_pt = 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;
}

最后就是在 scheduler 函数中在切换进程前切换 进程内核页表，在没有进程运行时要切换回 内核页表。

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
kernel/proc.c:
    
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;
        // my code:
        w_satp(MAKE_SATP(p->proc_kern_pt)); // 切换进程前，先切换进程内核页表
        sfence_vma();
        /////////////////////////////////////
        swtch(&c->context, &p->context);
        // my code:
        kvminithart(); // 切换回内核页表
        /////////////////////////////////////
		···
      }
}

3. Simplify copyin/copyinstr

实验说明：原本用户空间的内容 copy 到内核空间时需要对用户空间的地址进行代码上的转换（人工查页表进行转换），变成物理地址（由于内核数据段的虚拟地址就是物理地址）；lab 3 就想实现省去代码上的地址转换，让用户空间中的内容能直接 copy 到内核空间。

解析：其实就是在 lab 2 的基础上，将用户空间的映射添加到进程内核页表中去。

总共三个地方涉及到了用户申请内存并做映射的操作：

  • fork
  • exec
  • sbrk

仔细阅读 uvmalloc 函数：

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
kernel/vm.c:

uint64
uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  char *mem;
  uint64 a;

  if(newsz < oldsz)
    return oldsz;

  oldsz = PGROUNDUP(oldsz);
  for(a = oldsz; a < newsz; a += PGSIZE){
    mem = kalloc();
    if(mem == 0){
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
    memset(mem, 0, PGSIZE);
    if(mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
      kfree(mem);
      uvmdealloc(pagetable, a, oldsz);
      return 0;
    }
  }
  return newsz;
}

可以看到这个函数是做了物理内存分配和映射的。但是我们不需要做真正的分配内存的事，只需要做个映射就足够了。因此自己实现一个 proc_uvmalloc:

1
2
3
4
5
6
7
8
9
10
11
12
kernel/vm.c:

// my code:
void
proc_uvmalloc(pagetable_t pt, pagetable_t npt, uint64 oldsz, uint64 newsz) {
    oldsz = PGROUNDUP(oldsz);
    for (uint64 a = oldsz; a < newsz; a += PGSIZE) {
        uint64 pa = walkaddr(pt, a); // 根据 进程页表 和 虚拟地址 来获得对于的物理地址
        if (0 != mappages(npt, a, PGSIZE, pa, PTE_W|PTE_X|PTE_R)) // 做映射
            panic("proc_uvmalloc\n");
    }
}

uvmcopy 这个函数是 fork 中需要用到的，因为要复制父进程的页表以及内存镜像。由于它也是做了内存的分配和映射，而我们仅仅需要映射，因此也自己实现一个 proc_uvmcopy：

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
kernel/vm.c:

int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  char *mem;

  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walk(old, i, 0)) == 0)
      panic("uvmcopy: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("uvmcopy: page not present");
    pa = PTE2PA(*pte);
    flags = PTE_FLAGS(*pte);
    if((mem = kalloc()) == 0)
      goto err;
    memmove(mem, (char*)pa, PGSIZE);
    if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
      kfree(mem);
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(new, 0, i / PGSIZE, 1);
  return -1;
}

// my code:
int
proc_uvmcopy(pagetable_t old, pagetable_t new, uint64 sz) {
    uint64 a;
    for (a = 0;a < sz;a += PGSIZE) {
        pte_t *pte = walk(old, a, 0);
        if (pte == 0 || (*pte & PTE_V) == 0)
            return -1;
        uint64 pa = PTE2PA(*pte);
        int flags = PTE_FLAGS(*pte) & (~PTE_U);
        if (0 != mappages(new, a, PGSIZE, pa, flags))
            return -1;
    }
    return 0;
}

fork 中需要改动的地方：由于 fork 函数的作用是，分配一个新进程并复制父进程的内存镜像，所以 uvmcopy 函数会被调用，在它被调用完后我们只需要调用自己实现的 proc_uvmcopy，为 进程内核页表 添加映射即可：

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
kernel/proc.c:

int
fork(void)
{
  int i, pid;
  struct proc *np;
  struct proc *p = myproc();

  // Allocate process.
  if((np = allocproc()) == 0){
    return -1;
  }

  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    panic("fork:uvmcopy\n");
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  // my code:
  if (0 != proc_uvmcopy(np->pagetable, np->proc_kern_pt, p->sz))
      panic("fork");
  ///////////////////////////////////////////////////////////////
  np->sz = p->sz;

exec ：一般在 fork 被调用完之后再调用，并根据可执行文件镜像，来加载内容到内存中。也就是说进程页表要重新分配过，同理 进程内核页表 也需要重新分配过。

这里就是那两个重要的坑出现的地方了：

  1. 进程内核页表 不能重新分配，而是在原来的基础上进行修改，把用户地址映射部分全部清除掉，根据可执行文件镜像来重新做映射。为什么不能重新分配呢？因为从 用户态 执行到内核态的 exec 函数的整个函数调用过程都记录在内核栈中，如果重新分配进程内核页表，也就会重新分配内核栈，但这个新的内核栈无法跟原来的匹配起来（即使将原来内核栈中的内容 memmove 到新的，也会出错），会出现意想不到的错误。
  2. 解除 进程内核页表 中用户空间的映射这个过程需要在确保 exec 执行成功的前提下进行，因为如果不这样的话，你提前解除了映射，在后面进程退出时会再解除以此从而导致 panic: uvmunmap: not map 错误。
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
kernel/exec.c:

  int
  exec(char *path, char **argv) {
      ···
          
      // push the array of argv[] pointers.
       sp -= (argc+1) * sizeof(uint64);
       sp -= sp % 16;
       if(sp < stackbase)
         goto bad;
       if(copyout(pagetable, sp, (char *)ustack, (argc+1)*sizeof(uint64)) < 0)
         goto bad;

       // my code: 要在保证代码不会去到 bad 时，做 uvmunmap 并做用户空间的映射
       uvmunmap(p->proc_kern_pt, 0, PGROUNDUP(p->sz) / PGSIZE, 0);
       proc_uvmalloc(pagetable, p->proc_kern_pt, 0, sz);
       ///////////////////////////////////////////////////////////////

       // arguments to user main(argc, argv)
       // argc is returned via the system call return
       // value, which goes in a0.
       p->trapframe->a1 = sp;

       // Save program name for debugging.
       for(last=s=path; *s; s++)
         if(*s == '/')
           last = s+1;
       safestrcpy(p->name, last, sizeof(p->name));

       // 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);

       // my code:
       if (p->pid == 1)
           vmprint(p->pagetable);
       return argc; // this ends up in a0, the first argument to main(argc, argv)
       
       bad:
      	···
  }