genesis的空间站
0%

Lab Page Table

发表于
本文字数： 8.8k 阅读时长 ≈ 8 分钟

Lab Page Table

前置知识

一、xv6三级page table 原理

  1. 在xv6 virtual address中，分为index，offset和EXT三部分。其中offset对标最终翻译后的physical address的后十二位，表示当前4096bit大小的page中的偏移量，而index平分为三个9位索引，分别表示三级PTE中的物理地址偏移量。
  2. 关于page directory，你会发现它只有512个，也就是2的9次方，对应了index中被平分的三级索引。那么如何通过高一级的directory找到低一级的directory呢？其实只需要把上一级的PPN后面加上12个0，就是一个56位物理地址了，这个地址对应的就是下一级的directory，或者说它的第0个元素。那我们不能只找到directory，我们需要找到directory中特定的PTE，那只需要向上移动偏移量个单位就好了。（这就像在一个多层链表中找叶节点一样）当然，最高一级的directory不需要PPN，因为一开始satp就指向了最高一级的directory
  3. 根据上面一级一级翻译，最后得到的PPN后面不需要加12个0，而是加上offset，对应真正page中的4096位（2的十二次方），就是物理地址了。
  4. PTE中除了PPN，还有一部分flag位。通常有V表示下一级是否合法，RW表示是否读写，U表示是否可以被user权限访问，X表示是否可以被执行等等。
  5. 关于多级page table的作用。如果只有一级的话，那么在初始化process的时候就需要把所有物理地址的page table一次性载入主存，这些page table很大，会一下子占用大量空间。而process并不是一次就会把所有自己的空间都调用一遍，通常情况下只会调用很小一部分，那么最好的方法就是调用哪一部分载入哪一部分的page table。因此三级page table一开始需要载入一个最高级directory（2^9）每次调用时最多加入一个第二级和一个第三级（2^9），而不是一次性加入2^27个PTE，从而大大节约了开销。而cache中的TLB会暂存第一次找到的映射，从而减少重复查找。（注意：当你切换page table时，比如kernel 和 user pt的切换，你需要清空TLB，因为里面暂存的映射对于新的pt不再适用，这在task中有坑）

Task: Print a page table

这个task主要让我们熟悉一下三级页表。我们可以运用递归调用_vmprint()来输出每一层的页表。每进入新的一层，我们遍历整个层的页表，如果当前页表合法，我们便取出它的PPN并打印，如果它包含下一层页表，那么就调用_vmprint()进入下一层。

关于如何判断当前页表是否指向下一层，可看walk与uvmalloc函数，在这两个函数中，如果一个页表含有下一层，它只会设置PTE_V flag，否则就会全设置。

记得要加入到defs.h中以便被exec调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void
_vmprint(pagetable_t pagetable, int level)
{
  for(int i = 0; i < 512; i++)
  {
    pte_t pte = pagetable[i];
    if(pte & PTE_V) { // the PTE is valid 注意：这里运用位运算获取了标志位的二进制值
      uint64 pa = PTE2PA(pte);
      for(int j = 1; j <= level; j++)
        printf(".. ");
      printf("%d: pte %p pa %p\n", i, pte, pa);
      if((pte & (PTE_R|PTE_W|PTE_X)) == 0)// the PTE has a child
        _vmprint((pagetable_t)pa, level + 1);// 注意：若究其根源请移步walk, uvmalloc函数
    }
  }
}

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

Task: A kernel page table per process

这是一个极难的task，同时它与后面的进程切换课程内容有着密切的联系。建议学习完进程切换相关内容后回看这部分实现。

在原始的xv6中，所有process共用一个kernel pagetable，这显然是不利于isolation的，因此我们需要给每一个process都添加一个kpagetable。如此，在进行进程切换时用户进程进入内核态的时候就可以直接使用自己的kpagetable，而不是通过walk来模拟MMU寻找物理地址了。

  1. 在proc结构体中加入新的field。
    1
    pagetable_t kpagetable;      // new kernel page table
  2. 添加kpgtbl映射函数并在初始化的时候为kpgtbl添加映射。
    1
    2
    3
    4
    5
    6
    7
    8
    // add a mapping to the per-process page table
    // 你会发现mappages可用复用，只需要封装一下就好
    void 
    ukvmmap(pagetable_t ukpagetable, uint64 va, uint64 pa, uint64 sz, int perm)
    {
      if(mappages(ukpagetable, va, sz, pa, perm) != 0)
        panic("ukvmmap");
    }
    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
    // create a direct-map page table
    // return nullptr when kalloc fails
    pagetable_t
    ukvminit()
    {
      pagetable_t kpagetable = (pagetable_t) kalloc();//为每个process创建独有的kernel page table
      
      if(kpagetable == 0)
        return kpagetable;

      memset(kpagetable, 0, PGSIZE);

      //照搬常数映射
      // uart registers
      ukvmmap(kpagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);

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

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

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

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

      // map kernel data and the physical RAM we'll make use of.
      ukvmmap(kpagetable, (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(kpagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
      
      return kpagetable;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    // allocproc()
      //为每一个进程分配一个kernel page table
    found:

    ···

      p->kpagetable = ukvminit();
      if(p->kpagetable == 0){
        freeproc(p);
        release(&p->lock);
        return 0;
      }
  3. 为kernel stack添加映射，但不分配物理页，因为这只是映射，真正的物理页在procinit的时候已经分配了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // allocproc()
      //仿照procinit中添加kernel stack映射
      uint64 va = KSTACK((int) (p - proc));
      pte_t pa = kvmpa(va);//pa可以直接算
      memset((void*)pa, 0, PGSIZE);// 刷新？
      ukvmmap(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)); // 初始化context以保存寄存器状态(进程切换)
      p->context.ra = (uint64)forkret;
      p->context.sp = p->kstack + PGSIZE;

      return p;
  4. 在进程切换调度函数scheduler中，当切换到目标进程内核态时，要切换目标进程的内核页表；当切换回来的时候，要恢复全局内核页表。(注意，为什么我们都设置了进程内核页表却还要切换全局内核页表呢？详情请见后记)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // scheduler()
            //切换到即将运行的process的kernel page table
            w_satp(MAKE_SATP(p->kpagetable));
            sfence_vma();
            swtch(&c->context, &p->context);

            // Process is done running for now.
            // It should have changed its p->state before coming back.
            //当process运行结束后，要切换回全局kernel page table
            kvminithart();
  5. 当销毁进程的时候，我们需要回收它的内核页表。我们不需要释放最底层的内核页表的物理地址，只需要释放间接映射的页。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // 取消映射
    void
    ukvmunmap(pagetable_t pagetable, uint64 va, uint64 npages)
    {
      uint64 a;
      pte_t *pte;

      if((va % PGSIZE) != 0)
        panic("ukvmunmap: not aligned");

      for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
        if((pte = walk(pagetable, a, 0)) == 0)
          *pte = 0;
        if((*pte & PTE_V) == 0)
          *pte = 0;
        if(PTE_FLAGS(*pte) == PTE_V)
           panic("ukvmunmap: not a leaf");
        }
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //释放页表 注意：最底层的公用物理地址无需释放，因为当我们free pt和kpt时，free pt会清掉物理地址
    void
    ufreewalk(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) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
          // this PTE points to a lower-level page table.
          uint64 child = PTE2PA(pte);
          ufreewalk((pagetable_t)child);
          pagetable[i] = 0;
        }
        pagetable[i] = 0;
      }
      kfree((void*)pagetable);
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void
    freeprockvm(struct proc *p)
    {
      pagetable_t kpagetable = p->kpagetable;
      // 按分配顺序的逆序来销毁映射, 但不回收物理地址
      ukvmunmap(kpagetable, p->kstack, PGSIZE/PGSIZE);
      ukvmunmap(kpagetable, TRAMPOLINE, PGSIZE/PGSIZE);
      ukvmunmap(kpagetable, (uint64)etext, (PHYSTOP-(uint64)etext)/PGSIZE);
      ukvmunmap(kpagetable, KERNBASE, ((uint64)etext-KERNBASE)/PGSIZE);
      ukvmunmap(kpagetable, PLIC, 0x400000/PGSIZE);
      ukvmunmap(kpagetable, CLINT, 0x10000/PGSIZE);
      ukvmunmap(kpagetable, VIRTIO0, PGSIZE/PGSIZE);
      ukvmunmap(kpagetable, UART0, PGSIZE/PGSIZE);
      ufreewalk(kpagetable);
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // freeproc()
    ···
      p->state = UNUSED;
      if(p->kpagetable) {
        freeprockvm(p);
        p->kpagetable = 0;
      }
      if(p->kstack)
        p->kstack = 0;

Task: simplify copyin/copyinstr

这个task是上一个task的后续。因为kpagetable和pagetable前半段映射是一样的，这样的话我们才可以进入内核态后直接运用MMU进行寻址。如果pagetable发生了变化，那么kpagetable也需要发生变化。实验手册提示我们这些变化发生在fork, sbrk, exec中。

  1. 首先我们写一个辅助函数来帮助我们把pagetable复制到kpagetable。
    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
    52
    53
    54
    // vm.c
    // 类似mappages来映射
    int
    umappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
    {
      uint64 a, last;
      pte_t *pte;

      a = PGROUNDDOWN(va);
      last = PGROUNDDOWN(va + size - 1);
      for(;;){
        if((pte = walk(pagetable, a, 1)) == 0)
          return -1;
        //if(*pte & PTE_V)//?:能否直接强制复制? // 确实不需要考虑有效位
        //  panic("remap");//?:是否需要panic?
        *pte = PA2PTE(pa) | perm | PTE_V;
        if(a == last)
          break;
        a += PGSIZE;
        pa += PGSIZE;
      }
      return 0;
    }

    int
    pagecopy(pagetable_t old, pagetable_t new, uint64 begin, uint64 end)
    {
      pte_t *pte;
      uint64 pa, i;
      uint flags;
      begin = PGROUNDUP(begin);//向上取整到页面边界


      for(i = begin; i < end; i += PGSIZE){
        if((pte = walk(old, i, 0)) == 0)
          panic("pagecopy walk oldpage nullptr");
        if((*pte & PTE_V) == 0)
          panic("pagecopy oldpage pte not valid");
        pa = PTE2PA(*pte);
        flags = PTE_FLAGS(*pte) & (~PTE_U);//标记位设为非user，因为内核模式无法访问PTE_U页面
        //if((mem = kalloc()) == 0)
        //  goto err;
        //memmove(mem, (char*)pa, PGSIZE);//?:无需申请额外的页？ // 后记：确实不需要申请，因为在调用这个函数之前就已经申请了
        if(umappages(new, i, PGSIZE, pa, flags) != 0){
          //kfree(mem);无需释放
          goto err;
        }
      }
      return 0;

     err:
      uvmunmap(new, begin, (i - begin) / PGSIZE, 0);//最后一位设0表示不释放用户态页表物理空间
      return -1;
    }
  2. 修改fork(), exec(), sbrk()和userinit();

fork()

1
2
3
4
5
6
7
//同步pagetable 与 kpagetable
if(pagecopy(np->pagetable, np->kpagetable, 0, np->sz) != 0){
  freeproc(np);
  release(&np->lock);
  return -1;
}
np->parent = p;

exec()

1
2
3
4
5
6
//uvmunmap(p->kpagetable, 0, PGROUNDUP(oldsz)/PGSIZE, 0);//消除旧的映射但不需要
if(pagecopy(p->pagetable, p->kpagetable, 0, p->sz) < 0)//复制page table
  goto bad;

w_satp(MAKE_SATP(p->kpagetable));//载入satp寄存器
sfence_vma();//刷新映射

sbrk()

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

  sz = p->sz;
  if(n > 0){
    if(sz + n > PLIC || (sz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {//不能溢出
      return -1;
    }
    if(pagecopy(p->pagetable, p->kpagetable, p->sz, sz) != 0) {
      return -1;
    }//同步增量
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
    if(sz != p->sz) {
      uvmunmap(p->kpagetable, PGROUNDUP(sz), (PGROUNDUP(p->sz) - PGROUNDUP(sz)) / PGSIZE, 0);
    }//同步缩量
  }
  //ukvminithard(p->kpagetable);
  p->sz = sz;
  return 0;
}

userinit()

1
pagecopy(p->pagetable, p->kpagetable, 0, p->sz);//copy

后记

关于scheduler全局页表切换，这个问题困惑了我许久，经过大量回看源码与课程笔记最后得以解决，并大大加深了我对于进程切换的理解。
首先，scheduler函数不能多开！一个cpu里只能有一个scheduler，不管它是在running，runnable还是别的。(这也是为什么在里面会有死循环)当进程调用它时，不是通过函数调用，而是通过切换context来直接转换，每次它切换到其他进程之前，它的状态都会被保存等待下一次调用。
所以，当每次调用scheduler的时候，(除首次以外)都会直接进入上一次调用scheduler的位置(也就是swtch后面)。理所应当，此时应该由调用者的内核页表切换到scheduler的内核页表。(因为当进程内核态切换scheduler的时候，它只是恢复了scheduler的寄存器就直接切过来了，没有切换页表的操作)
但是，scheduler作为一个特殊内核进程，它没有proc结构体！(lec11中Robert教授答学生问)因此它只能使用全局内核页表。