陈浪平的博客
0%

xv6-2020-lab3解析

发表于 更新于 分类于 Disqus：
本文字数： 9.5k 阅读时长 ≈ 9 分钟

先导知识

xv6为每一个进程都创建一张页表，除此之外还有一张表用来描述内核的虚拟地址映射（这有很多不合理之处，之后的实验会手动修改）。

下图是原始的xv6的内核的内存映射图：

可以看到，大部分的映射的线都是水平的，也就是虚拟地址直接映射到物理内存，只有最上面的那些是斜着映射到RAM中的，而且看样子似乎能够覆盖掉内核的代码段。

除此之外，内核还包含了每一个进程的内核栈的映射。内核栈的映射也是直接把虚拟地址直接映射到物理地址上。

具体怎么映射，可以看代码是怎么实现的。

首先是在main中，有这样的初始化代码：

1
2
3
4
kinit();         // physical page allocator
kvminit();       // create kernel page table
kvminithart();   // turn on paging
procinit();      // process table

kinit

物理页面初始化的一个函数。由于此时还没有开启分页，所以物理地址和虚拟地址之间是一一映射的。

这个初始化比较简单，本质上就是首先获取锁，然后把从end开始（注释里面写的是内核后的第一个地址，物理地址是0x80027020），PHYSTOP（0x88000000，不知道为什么图里是0x864000000）结束的所有的物理内存空间都设置成垃圾的内容（全是1）。

kvminit

首先获取一个空闲的页面，称为kernel_pagetable，将这个页面作为页目录表的根目录（目前从代码里面还是看不出具体是在哪个地址），然后把上图中的UART0、VIRTIO0、CLINT、PLIC这些地址一一映射，然后映射一下内核的代码段（上述的Kernel Text），注意这里设置了R-X，所以这里保证了内核的代码是不可以修改的。然后映射一下Kernel Data和Free Memory这两个区域（代码中是一起映射的），它们的flag是RW，最后还映射了Trampoline，物理地址是由trampoline.S进行指定的。注意，图中的guard page和kstack没有映射。

kvminithart

简单来说就是把上面得到的kernel_pagetable的地址放到satp这个寄存器中，然后flush一下TLB。这是因为寄存器的值一旦更新，必然需要重新

在这之后，CPU处理的所有的地址，就需要到satp寄存器指向的页表中，进行地址转换了。

procinit

在这个函数中，为每一个（xv6的系统是直接申请一个结构体的数组）进程都分配好了一个内核栈。然后这些内核栈使用kvm进行映射的，也就是到目前为止，还是只有内核一张页表，即kernel_pagetable。

当xv6变化页表的时候，必须需要通知CPU重新加载一下TLB，而这个正好是在kvminithart()里实现的，所以当所有进程的内核栈设置完成之后，在调用一次kvminithart即可。

分配物理内存

每次当进程需要更多的内存的时候，它就会向操作系统申请，那在xv6中就首先使用kalloc这个函数分配物理内存，然后把对应的映射放到该进程的页表中去。

原有代码

vm.c

  • walk：给定一个虚拟地址，在某个页表中返回它的PTE。
  • walkaddr：给定一个虚拟地址，在某个页表中找到它的物理地址。（实现原理就是先用walk找到pte，然后转换）
  • mappages：给定一个虚拟地址和物理地址，把它们俩的映射关系安装到给定的页表中。由此函数引出kvmmap，专门服务于内核页表。

Print a page table（简单）

编写一个打印页表内容的函数。lab中提示了一些比较有用的：

  • 推荐阅读一下freewalk，会很有用。
  • 十六进制可以用%p进行打印。这条有点问题，我自己的Ubuntu上测试，如果要打印0x开始，且一共有16位，不够用零补足的数字，应该是需要用%#016x进行输出，而使用%p是不会有前导零的，可能是xv6做了特殊优化吧。

最后代码还是很简单的：

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 == 4){
    return;
  }
  if(level == 0){
    printf("page table %p\n",pagetable);
    vmprint(pagetable,level+1);
    return;
  }
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if(pte & PTE_V){
      // this PTE points to a lower-level page table.
      if (level == 1){
        printf("..");
      }else if (level == 2){
        printf(".. ..");
      }else if (level == 3){
        printf(".. .. ..");
      }
      printf("%d: pte %p ",i,pte);
      uint64 pa = PTE2PA(pte);
      printf("pa %p\n",pa);
      vmprint((pagetable_t)pa,level+1);
      // vmprint((pagetable_t)child);
    } else if(pte & PTE_V){
      return;
    }
  }
}

其中的pa其实就是下一级页表的地址。而从PTE转换成pa也非常简单，就是一个宏：#define PTE2PA(pte) (((pte) >> 10) << 12)。移动10位把flag给去掉，然后再右移12位，补上0就是pa了。这里可能会有人对offset提出疑问，你这不是把offset全部变成0了吗？这里得到的是页的地址，而页由于是4K一页（在xv6）中，所以最后的12位必然是0，这里不是某个数据的地址。

image-20210413161832614

结合上图解释一下vmprint的输出结果。page0输出的是什么，page2里有什么？user mode运行的时候，进程可以读取/写入page1吗？

image-20210413163141395

可以看到这两页是紧紧挨着的，所以大胆猜测一下就是stack和guard page了。其中2的地址比较低，所以2是guard page。

A kernel page table per process（困难）

xv6内核只有一个页表，而内核的内存是直接映射的，也就是内核的虚拟内存的地址就是物理内存的地址。

但是对于进程就不是这样了。对于每一个进程，xv6都有一个页表，该页表的虚拟地址从0开始。由于内核的页表并没有包含用户进程的这些内容，这就导致了要传递一些东西的时候，就会比较麻烦。比如现在用户进程希望调用一个系统调用，并且用户给内核传入一个地址作为参数，这个系统调用就是能够把这个地址里放入指定的东西，对，和上个lab中做过的那个sys_info系统调用有点类似，但是区别是这个例子是用户传入，而lab2里面是内核生成。如果内核需要获取对应的地址，那它不得不首先拿到用户进程的页表，然后找到对应的物理地址，再把对应的数据放到物理内存中去。

这个问题的本质在于，我们现在只有1个全局的内核页表和N个用户进程的页表，我们需要自己改造一下，实现每个进程有一个自己的用户页表和一个内核页表。这样每个进程在内核态的时候，可以使用它自己的内核页表（内核页表包含了用户的地址映射和内核的地址映射）。

所以我们现在希望，让每个进程独立拥有一个同时映射了用户内存区和内核内存区的内核页表，这样可以使用这个内核页表，在用户内存区和内核内存区之间传递数据。这部分实验首先完成一部分。

首先修改proc.h，用来修改进程的结构。因为每一个进程都需要持有一个内核的页表，就像它持有自己的用户页表一样。还需要更新一下scheduler，这样进行进程切换的时候，内核表也跟着切换。这里的话，可以先让每个进程的内核页表都指向那个全局的页表。

hints：

  • struct proc里面必然需要增加一个指向内核页表的指针了。
  • 推荐新写一版kvminit()，它能够为每一个进程的内核页表进行初始化，而不是去修改原来的kernel_pagetable。推荐在allocproc()中调用这个新的函数。
  • 确保每个进程的页表中都有内核栈的映射。在原始的版本中，xv6的内核栈是在procinit()函数中进行初始化的。你可能需要进行修改。
  • 在scheduler()这个函数中，重新刷新一下stap这个寄存器为新的进程的内核页表。
  • 如果没有进程的时候，scheduler()需要使用内核页表kernel_pagetable。
  • 在函数freeproc中释放对应的空间。

上面的这些内容是

修改数据结构

首先必然是修改kernel/proc.h文件，为进程的数据结构proc，直接新增一个内核页表。

1
pagetable_t kpagetable;      // Kernel page table

创建进程的内核页表

那就仿照内核自己的页表是怎么初始化的，我们也怎么做即可。

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
pagetable_t
proc_kernel_pagetable_init()
{
  pagetable_t kpagetable;
  kpagetable = (pagetable_t) kalloc();
  if (kpagetable == 0) 
    return 0;
  memset(kpagetable, 0, PGSIZE);
  uvmmap(kpagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);
  uvmmap(kpagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
  uvmmap(kpagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
  uvmmap(kpagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
  uvmmap(kpagetable, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
  uvmmap(kpagetable, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
  uvmmap(kpagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  return kpagetable;
}

// 将制定的va-pa的映射关系安装到指定的页表中
void 
uvmmap(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(pagetable, va, sz, pa, perm) != 0)
    panic("uvmmap");
}

创建内核栈

由于之前的进程的内核栈是在内核页表里面进行初始化的，但是现在明显不需要，而是需要放到proc.c/allocproc函数中。

首先需要把原来的内核栈的创建给删除，就可以直接把procinit()整个弄成空函数就可以了。

然后就是按照hint的建议，在allcoproc()函数中进行内核栈等操作，由于内核栈的分配必须先有进程的内核页表分配，所以先分配一下进程的内核页表，然后分配对应内核栈，并且把内核栈的虚拟地址和物理地址的映射关系装到进程的内核页表里面。

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
// An empty user page table.
p->pagetable = proc_pagetable(p);
if(p->pagetable == 0){
  freeproc(p);
  release(&p->lock);
  return 0;
}

// 同时也需要申请一个内核页表
p->kpagetable = proc_kernel_pagetable_init();
if(p->kpagetable == 0){
  // 发生错误，进行处理(就是抄上面的)
  freeproc(p);
  release(&p->lock);
  return 0;
}

// 分配内核栈
char *pa = kalloc();
if(pa == 0)
  panic("kalloc");
uint64 va = KSTACK((int) (p - proc));
// 把内核栈的映射放到对应的进程的内核的页表中
uvmmap(p->kpagetable, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
p->kstack = va;

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

这里有一个地方我个人觉得有点问题，就是上面的虚拟地址的创建代码：uint64 va = KSTACK((int) (p - proc));，因为我是直接抄的之前的内核页表，而内核页表里面必须要保证所有进程的内核栈是分开的，而如果是现在每个进程有了自己的内核页表，则其实是可以放在一个地方的。所以我觉得改成uint64 va = TRAMPOLINE - 2 * PGSIZE;，这样所有的进程的内核栈的虚拟地址都是一样的。

调度程序

调度的时候用的页表必然就是进程自己的内核页表了。

1
2
3
4
5
6
7
8
9
10
11
12
13
p->state = RUNNING;
c->proc = p;
// 切换内核的页表
w_satp(MAKE_SATP(p->kpagetable));
sfence_vma();
swtch(&c->context, &p->context);

// 隔了几行
if(found == 0) {
  intr_on();
  kvminithart();	// 如果没有进程运行，那么是需要使用内核自己的页表的
  asm volatile("wfi");
}

销毁内核栈

当进程死亡的时候，我们当然需要回收内核栈。

1
2
3
4
5
6
7
8
9
// 释放内核栈
if (p->kstack)
{
pte_t* pte = walk(p->kpagetable, p->kstack, 0);
if (pte == 0)
panic("freeproc: kstack");
kfree((void*)PTE2PA(*pte));
}
p->kstack = 0;

这里主要是为了回收物理内存。

销毁进程的内核页表

1
2
3
4
5
6
if(p->pagetable)
  proc_freepagetable(p->pagetable, p->sz);
if (p->kpagetable)
  proc_freekpt(p->kpagetable);
p->pagetable = 0;
p->kpagetable = 0;

当然最重要的就是proc_freekpt()这个函数了。那就是抄呗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void 
proc_freekpt(pagetable_t pagetable)
{
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if((pte & PTE_V)){
      pagetable[i] = 0;
      if ((pte & (PTE_R|PTE_W|PTE_X)) == 0)
      {
        uint64 child = PTE2PA(pte);
        proc_freekpt((pagetable_t)child);
      }
    } else if(pte & PTE_V){
      panic("proc free kpt: leaf");
    }
  }
  kfree((void*)pagetable);
}

大功告成？

我自己到这一步以为自己做完了，然后运行了一下，发现提示错误，根据错误信息知道是panic("kvmpa");被触发了。仔细看了一下对应的函数kvmpa()，这个函数的作用是把内核的虚拟地址转成物理地址，且仅仅对内核栈有效。所以这里也是需要修改的。pte = walk(myproc()->kpagetable, va, 0);修改成对应的进程的内核页表之后，这部分实验就完成了。

简化copyin/copyinstr（困难）

内核的copyin函数是从用户指针所指向的内存区域获取内容。其实就是把虚拟地址转换成物理地址，然后利用指针操作访问对应的地址，一一拷贝。当然因为是从用户进程中拿到指针真正指向的物理地址，所以需要先获取用户进程的页表，然后通过用户页表获取物理地址。

这部分的要求就是：把用户映射这部分放到内核页表中。

xv6的内核部分是放在物理内存的高地址处（由于一一映射的关系，在虚拟地址也是高处）的，而用户进程则是从虚拟地址低处开始的，所以这其实为我们实现这个lab提供了帮助。为了防止用户的虚拟地址超过导致覆盖掉内核，xv6的解决办法是在PLIC中存放了上界值。

Hints：

  • 在copyin()中利用新创建的copyin_new来代替。确保它能成功工作之后再去替换copyinstr()。
  • 在一些函数中，当内核切换了用户的页表，需要同步修改进程的内核页表。这些函数包括fork(), exec(), 和 sbrk()。
  • 不要忘记第一个用户进程的页表，在 userinit中。
  • PTE的权限位，在进程的内核页表中，应该设置成什么？如果设置成了PTE_U那么内核就不能访问了。
  • 别忘记上面说的PLIC限制。

Linux的页表和我们上面实现的本质是一样的，一个进程对应一个内核页表，但是这样会遭到侧信道攻击。

OK，有了上面的知识，就可以开始写代码实现了。其实本质上说穿了就是改这四个函数，在里面加上页表的复制代码，一种是抽象出对应的复制函数，这样在这四个函数中直接使用就可以了；还有另外一种是分别去这四个函数中实现。

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
void
u2kvmcopy(pagetable_t pagetable, pagetable_t kpagetable, uint64 start, uint64 end)
{
  pte_t *pte_from, *pte_to;
  uint64 a, pa;
  uint flags;

  // 参数检查
  if (end < start)
    return;

  // 从全新的一页开始
  start = PGROUNDUP(start);
  for (a = start; a < end; a += PGSIZE)
  {
    // 首先分别找到两个PTE
    if ((pte_from = walk(pagetable, a, 0)) == 0)
      panic("u2kvmcopy");
    if ((pte_to = walk(kpagetable, a, 1)) == 0)
      panic("u2kvmcopy");
    pa = PTE2PA(*pte_from);
    // 在拷贝到内核页表中，需要清除掉PTE_U这个标志位
    flags = (PTE_FLAGS(*pte_from) & (~PTE_U));
    *pte_to = PA2PTE(pa) | flags;
  }
}

然后去四个函数中一一进行操作就可以了。

fork

1
2
3
4
5
6
np->state = RUNNABLE;

// 复制内核页表
u2kvmcopy(np->pagetable, np->kpagetable, 0, np->sz);

release(&np->lock);

exec

1
u2kvmcopy(pagetable, p->kpagetable, 0, sz);

sbrk

这个本质上是系统调用，而系统调用本质上其实就是用的growproc()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    // 如果是增加的话，小心超过界限
    if(PGROUNDUP(sz + n) >= PLIC)
      return -1;
    if((sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
    u2kvmcopy(p->pagetable, p->kpagetable, sz-n, sz);
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
    u2kvmcopy(p->pagetable, p->kpagetable, sz, sz-n);
  }
  
  p->sz = sz;
  return 0;
}

userinit

1
2
p->state = RUNNABLE;
u2kvmcopy(p->pagetable, p->kpagetable, 0, p->sz);

最后不要忘了把copyin修改成新的就可以了。

讨论

做完这个lab之后，我有不少的疑问。

首先就是关于一个进程的内核页表的问题。在初始化代码中，我其实把整个内核空间都映射了一遍，且每个进程都是相同的，那为什么不能让内核的二级页表、三级页表只用一个呢？如果我这么做，每个进程都会创建N个二级页表和三级页表，虽然这些页表的内容都是一样的，但是还是存在多份，这里是不是可以优化一下呢？

查询资料以及和同学交流之后发现，这里确实是有点问题，空间浪费太严重了，Linux中的做法是只有第一级的页表是复制的，而且是必须支付的代价，然后就是共享的了。

在lab的最后也提到了，可以利用super-pages这个标志位来实现一样的功能。但是我个人觉得应该用的Global这个标志位。

同时也提到了，我们这里的内核页表是从0开始映射的，但是实际上并不是，因为实际中最开始的那页是空着的，这样任何的指向NULL的指针就会立刻引发一个fault。

最后，这个lab每次运行make grade都有奇奇怪怪的错误。