MIT6.s081-2020 Lab3 Page Tables

lab 3 文档 (opens new window)

在本实验中，您将探索页表并修改它们以简化将数据从用户空间复制到内核空间的函数。

准备

git fetch
git checkout pgtbl
make clean

Print a page table

引言

为了帮助您了解 RISC-V 页表，并且可能有助于将来的调试，首要任务是编写一个打印页表内容的函数。

定义一个名为vmprint(). 它应该需要一个pagetable_t参数，并以下面描述的格式打印该页表。插入if(p->pid==1) vmprint(p->pagetable)在 exec.c 之前return argc, 打印第一个进程的页表。

实现

将vmprint函数添加到kernel/vm.c文件中并在kernel/defs.h文件中添加该函数的声明。

//vm.c
//...
int             copyinstr(pagetable_t, char *, uint64, uint64);
void            vmprint(pagetable_t);

使用格式符%p打印16进制数，使用kernel/riscv.h文件中定义的宏, 参考freewalk函数以递归的形式完成。

//kernel/riscv.h
#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
#define PTE2PA(pte) (((pte) >> 10) << 12)
//...
typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
//kernel/vm.c
// Recursively free page-table pages.
// All leaf mappings must already have been removed.
void
freewalk(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);
      freewalk((pagetable_t)child);
      pagetable[i] = 0;
    } else if(pte & PTE_V){
      panic("freewalk: leaf");
    }
  }
  kfree((void*)pagetable);
}

需要注意的说遍历到最后一层页表就停止，最后一层页表中页表项中W位，R位，X位起码有一位会被设置为1。

void vmprint_helper(pagetable_t pagetable,int dep) {
  for(int i = 0; i < 512; i++){
    pte_t pte = pagetable[i];
    if(pte & PTE_V){
      for(int j = 0; j < dep; j++) {
        if(j != 0){
          printf(" ");
        }
        printf("..");
      }
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte);
      printf("%d: pte %p pa %p\n",i,pte,child);
      if((pte & (PTE_R|PTE_W|PTE_X)) == 0){
        vmprint_helper((pagetable_t)child,dep + 1);
      }
    }
  }
}
//Print a page table
void vmprint(pagetable_t pagetable){
  // there are 2^9 = 512 PTEs in a page table.
  printf("page table %p\n",pagetable);
  vmprint_helper(pagetable,1);
}

结果

实验测试结果：

A kernel page table per process

引言

Xv6 有一个内核页表，每当它在内核中执行时都会使用它。内核页表直接映射到物理地址，因此内核虚拟地址x映射到物理地址x。Xv6 还为每个进程的用户地址空间提供了一个单独的页表，仅包含该进程的用户内存的映射，从虚拟地址零开始。因为内核页表不包含这些映射，所以用户地址在内核中是无效的。因此，当内核需要使用在系统调用中传递的用户指针（例如，传递给write())，内核必须首先将指针转换为物理地址。本节和下一节的目标是允许内核直接取消引用用户指针.

实现

这一部分是要求我们给每个进程维护一个各自不同的内核页表，当陷入内核时，切换到这个特有内核页表，内核就直接可以使用虚拟地址来访问系统调用参数了。按照HINT一步步做下去即可。

HINT1：将字段添加到struct proc用于进程的内核页表。

  pagetable_t pagetable;       // User page table
  pagetable_t kernel_pagetable;       // kernel page table New

HINT2：为新进程生成内核页表的合理方法，是参考kvminit实现生成一个新的页表而不是修改kernel_pagetable. 将会在allocproc中调用该函数.

// add a mapping to processes's kernel
// page table
void
uvmmap(pagetable_t pagetable, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(pagetable, va, sz, pa, perm) != 0)
    panic("uvmmap");
}
// create processes's kernel table
pagetable_t
proc_kvminit()
{
  pagetable_t proc_kernel_pagetable = (pagetable_t) kalloc();
  if(proc_kernel_pagetable == 0) {
    return 0;
  }
  memset(proc_kernel_pagetable, 0, PGSIZE);
  // uart registers
  uvmmap(proc_kernel_pagetable, UART0, UART0, PGSIZE, PTE_R | PTE_W);
  // virtio mmio disk interface
  uvmmap(proc_kernel_pagetable, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
  // CLINT
  uvmmap(proc_kernel_pagetable, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
  // PLIC
  uvmmap(proc_kernel_pagetable, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
  // map kernel text executable and read-only.
  uvmmap(proc_kernel_pagetable, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
  // map kernel data and the physical RAM we'll make use of.
  uvmmap(proc_kernel_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.
  uvmmap(proc_kernel_pagetable, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  return proc_kernel_pagetable;
}

为了保证后续kernel/proc.c能够调用方法，需要在kernel/defs.h文件中添加该函数的声明。

//vm.c
//...
void            uvmmap(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     proc_kvminit();

HINT3：确保每个进程的内核页表都有该进程的内核堆栈的映射。在未修改的 xv6 中，所有内核堆栈都设置在procinit. 您需要将部分或全部功能移至allocproc.

// 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);
     // uvmmap(p->kernel_pagetable, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
      p->kstack = va;*/
  }
 // kvminithart();
}
// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
static struct proc*
allocproc(void)
{
//...
found:
  p->pid = allocpid();
  p->kernel_pagetable = proc_kvminit();
  char *pa = kalloc();
  if(pa == 0)
    panic("kalloc");
  uint64 va = KSTACK((int) (p - proc));
  // kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  uvmmap(p->kernel_pagetable, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  p->kstack = va;
//...  
}

本操作含义是不再在procinit()方法中为每个进程分配内核栈，而是在allocproc()创建内核页表，并在内核页表上分配一个内核栈。

HINT4：调整scheduler()将进程的内核页表加载到内核的satp注册（见kvminithart寻找灵感）,scheduler()应该使用kernel_pagetable当没有进程正在运行时.

kernel/proc.c

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;
        proc_kvminithart(p->kernel_pagetable);
        swtch(&c->context, &p->context);
        // Process is done running for now.
        // It should have changed its p->state before coming back.
        kvminithart();
        c->proc = 0;

kernel/vm.c

void proc_kvminithart(pagetable_t pagetable) {
  w_satp(MAKE_SATP(pagetable));
  sfence_vma();
}

并在kernel/defs.h文件中添加该函数的声明

//vm.c
//...
void            uvmmap(pagetable_t, uint64, uint64, uint64, int);
pagetable_t     proc_kvminit();
void            proc_kvminithart(pagetable_t);

HINT5：释放进程的内核页表freeproc，该方法只来释放页表，而无需同时释放叶物理内存页面，可参考freewalk。

kernel/proc.c

void proc_freekernel_pagetable(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){  // not leaf.
        // this PTE points to a lower-level page table.
        uint64 child = PTE2PA(pte);
       proc_freekernel_pagetable((pagetable_t)child);
      }
    }
  }
  kfree((void*)pagetable);
}
static void
freeproc(struct proc *p)
{
  if(p->trapframe)
    kfree((void*)p->trapframe);
  p->trapframe = 0;
  if(p->kstack) {
    pte_t *pte = walk(p->kernel_pagetable, p->kstack, 0);
    if (pte == 0) return;
    kfree((void*)PTE2PA(*pte));
  }
  if(p->kernel_pagetable) {
    proc_freekernel_pagetable(p->kernel_pagetable);
  }
  if(p->pagetable)
    proc_freepagetable(p->pagetable, p->sz);
  p->pagetable = 0;
  p->kernel_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;
}

插曲

最后执行一下会报panic: kvmpa，需要在kvmpa将kernel_pagetable改为proc的kernel_pagetable。

原因：kvmpa()方法会在进程执行期间调用，此时需要修改为获取进程内核页表，而不是全局内核页表

解决方法：

kernel/vm.c

#include "spinlock.h"
#include "proc.h"
// translate a kernel virtual address to
// a physical address. only needed for
// addresses on the stack.
// assumes va is page aligned.
uint64
kvmpa(uint64 va)
{
  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;
  pte = walk(myproc()->kernel_pagetable, va, 0);	//New
  if(pte == 0)
    panic("kvmpa");
  if((*pte & PTE_V) == 0)
    panic("kvmpa");
  pa = PTE2PA(*pte);
  return pa+off;
}

Simplify copyin/copyinstr

引言

内核的 copyin函数读取用户指针指向的内存。它通过将它们转换为物理地址来实现这一点，内核可以直接取消引用。它通过在软件中遍历进程页表来执行此转换。你在这部分实验中的工作是将用户映射添加到每个进程的内核页表（在上一节中创建），以允许 copyin（以及相关的字符串函数 copyinstr) 直接取消引用用户指针。

实现

该部分内容主要目的是为了解决内核态数据到用户态的引用用户指针传递，按照HINT一步步做下去即可。

HINT1：用copy_new函数替代copyin，同时opyinstr_new函数替代copyinstr

// Copy from user to kernel.
// Copy len bytes to dst from virtual address srcva in a given page table.
// Return 0 on success, -1 on error.
int
copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  /**
  uint64 n, va0, pa0;
  while(len > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (srcva - va0);
    if(n > len)
      n = len;
    memmove(dst, (void *)(pa0 + (srcva - va0)), n);
    len -= n;
    dst += n;
    srcva = va0 + PGSIZE;
  }
  return 0;
  **/
  return copyin_new(pagetable, dst, srcva, len);
}
// Copy a null-terminated string from user to kernel.
// Copy bytes to dst from virtual address srcva in a given page table,
// until a '\0', or max.
// Return 0 on success, -1 on error.
int
copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
{
  /**
  uint64 n, va0, pa0;
  int got_null = 0;
  while(got_null == 0 && max > 0){
    va0 = PGROUNDDOWN(srcva);
    pa0 = walkaddr(pagetable, va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (srcva - va0);
    if(n > max)
      n = max;
    char *p = (char *) (pa0 + (srcva - va0));
    while(n > 0){
      if(*p == '\0'){
        *dst = '\0';
        got_null = 1;
        break;
      } else {
        *dst = *p;
      }
      --n;
      --max;
      p++;
      dst++;
    }
    srcva = va0 + PGSIZE;
  }
  if(got_null){
    return 0;
  } else {
    return -1;
  }
  **/
  return copyinstr_new(pagetable, dst, srcva, max);
}

为了使得kernel/vmcopyin.c中的copyin_new和copyinstr_new发挥作用，我们需要在kernel/defs.h文件中添加该函数的声明。

//vmcopyin.c
int            copyin_new(pagetable_t, char *, uint64, uint64);
int            copyinstr_new(pagetable_t, char *, uint64, uint64);

HINT2：exec , fork , growproc 会改变进程的page table，需要加上随之改变进程kernel page table的逻辑。 修改fork 和 exec的最简单的办法就是，等进程的page table修改完后，kernel page table就把 [0,p->sz] 的内存映射复制一遍。可参考uvmcopy，其作用是在fork子进程时，拷贝父进程的页表。注意权限，需要把 PTE_U 去掉，否则内核没法使用。

其中growproc 分为n为正负两种情况，n为正时，需要复制 [sz,sz+n] 的映射，n为负时，需要把 [sz+n,sz] 的映射去掉，此外还需要加上一个限制。

kernel/vm.c

// Given a parent process's page table, copy
// its memory into a child's page table.
// Copies both the page table and the
// physical memory.
// returns 0 on success, -1 on failure.
// frees any allocated pages on failure.
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;
}
// used in fork, copy new content in process's page table to its kernel pagetable 
int proc_kernel_uvmcopy(pagetable_t proc_pagetable, pagetable_t kernel_pagetable,uint64 old_sz,uint64 new_sz) {
    //user space pagetable mapping to user kernel pagetable
void proc_kernel_uvmcopy(pagetable_t proc_pagetable, pagetable_t kernel_pagetable,uint64 old_sz,uint64 new_sz) {
  pte_t *pte, *kpte;
  uint64 va;
  if (new_sz >= PLIC)
    panic("proc_kernel_uvmcopy: user process space is overwritten to kernel process space");
  for(va = old_sz; va < new_sz;va += PGSIZE) {
    if((pte = walk(proc_pagetable, va, 0)) == 0)
      panic("proc_kernel_uvmcopy: pte should exist");
    if((kpte = walk(kernel_pagetable, va, 1)) == 0)
      panic("proc_kernel_uvmcopy: kpte should exist");
    *kpte = *pte;
    *kpte &= ~(PTE_U | PTE_W | PTE_X);
  }
  for(va = new_sz; va < old_sz; va += PGSIZE){
    if((kpte = walk(kernel_pagetable, va, 1)) == 0)
      panic("proc_kernel_uvmcopy: kpte should exist");
    *kpte &= ~PTE_V;
  }
}

修改fork方法，如下所示：

kernel/proc.c

// Create a new process, copying the parent.
// Sets up child kernel stack to return as if from fork() system call.
int
fork(void)
{
  //...
  // Copy user memory from parent to child.
  if(uvmcopy(p->pagetable, np->pagetable, p->sz) < 0){
    freeproc(np);
    release(&np->lock);
    return -1;
  }
  np->sz = p->sz;
  //Copy pagetable to kernel_pagetable
  if (proc_kernel_uvmcopy(np->pagetable,np->kernel_pagetable,0,np->sz) < 0) {
     freeproc(np);
     release(&np->lock);
     return -1;
  }
  //...
}

修改sys_sbrk()下的子函数growproc()，使其在内存扩张、缩小时，相应更改进程内核页表

//kernel/sysproc.c
uint64
sys_sbrk(void)
{
  int addr;
  int n;
  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  if(growproc(n) < 0)
    return -1;
  return addr;
}
//kernel/proc.c
// Grow or shrink user memory by n bytes.
// Return 0 on success, -1 on failure.
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;
    }
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);
  }
  proc_kernel_uvmcopy(p->pagetable,p->kernel_pagetable,p->sz,sz);
  proc_kvminithart(p->kernel_pagetable);
  p->sz = sz;
  return 0;
}

修改exec()，在用户进程页表重新生成完后，取消进程内核页表之前的映射，在进程内核页表，建立新进程页表的映射。

kernel/exec.c

int
exec(char *path, char **argv)
{
  //...
  // Commit to the user image.
  oldpagetable = p->pagetable;
  p->pagetable = pagetable;
  p->sz = sz;
  // new logic added
  // change to kernel page table
  if (proc_kernel_uvmcopy(p->pagetable,p->kernel_pagetable,0,p->sz) == -1) {
    goto bad;
  }
  // switch to the new kernel page table
  proc_kvminithart(p->kernel_pagetable);
  //...
}

HINT3：不要忘记将第一个进程的用户页表包含在其内核页表中userinit.

kernel/proc.c

userinit(void)
{
  struct proc *p;
  p = allocproc();
  initproc = p;
  // allocate one user page and copy init's instructions
  // and data into it.
  uvminit(p->pagetable, initcode, sizeof(initcode));
  p->sz = PGSIZE;
  // prepare for the very first "return" from kernel to user.
  p->trapframe->epc = 0;      // user program counter
  p->trapframe->sp = PGSIZE;  // user stack pointer
  safestrcpy(p->name, "initcode", sizeof(p->name));
  p->cwd = namei("/");
  p->state = RUNNABLE;
  proc_kernel_uvmcopy(p->pagetable, p->kernel_pagetable, 0, p->sz);
  release(&p->lock);
}

结果

实验测试结果：

总结

简单的写一下lab 3的总结吧，做之前最好把概念理清楚，确实蛮有难度的。

第一部分：打印三级页表、页表项的虚拟地址以及物理地址，利用递归就可以完成，leaf pte的判断的判断条件即递归结束条件，可以参考vm.c中部分函数的源代码。leaf pte可以通过pte中的flag进行判断，即leaf pte才含有PTE_W，PTE_X，PTE_R。

第二部分：由于历史原因部分os将内核和用户进程独立分为两个page table，本lab的初衷是为了利用好进程之间的isolation，为每个用户进程分配一个内核页表(初始时的映射和全局内核页表相同)，释放进程的同时也要将进程的内核页表释放，注意不将叶子pte的物理内存释放，初始化时也是同样的。注意到procinit函数里已经为每个用户进程通过全局内核页表分配好了内核栈，HINT中要求把该部分迁移到分配用户进程是时分配栈，另外kvmpa函数中也有个坑，需要将全局内核页表替换为当前用户进程的内核页表。

第三部分：将用户进程页表载入到用户的内核页表后，系统调用传参时所用到的copyin或者copyinstr就不需要再间接的将该参数的虚拟地址通过用户页表转换为物理地址之后再处理了，简化了一步walk的操作，直接dereference即可。copy页表映射时可以参考mvmcopy函数，fork中有相关页表复制的内容，但不是全部参考，可能会出现remap的情况，因此考虑不使用mappages函数即可，具体内容上述已经介绍完全。注意sbrk时相关函数growproc的overflow检测，以及虚拟地址空间减少时要从用户内核页表中unmap掉相关内容，增加时正常复制即可。exec函数中copy前需要取消进程内核页表之前的映射并重新建立新进程页表的映射或将用户内核页表的映射清空或者保存后置换页表。其他都按hint去做就行了。

总的来说：在调试过程中，遇到比较常见的问题是释放页表时各种 panic，需要耐住性子，反复琢磨。

The devil is in the details.