MIT 6s081 lab 3:page tables

Lab3: page tables

作业地址：Lab: page tables (mit.edu)

本实验的目标：修改页表、简化从用户态拷贝数据到内核态的方法

其实页表就几个操作：创建页表、添加PTE项，查找PTE项，清空PTE项，释放PTE对应的物理空间，释放页表本身占用的物理空间

Print a page table (easy)

添加一个打印页表的内核函数

page table 0x0000000087f6e000
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
.. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
.. .. ..510: pte 0x0000000021fdd807 pa 0x0000000087f76000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

添加下列函数，并在/kernel/defs.h中声明

int             vmprint(pagetable_t pagetable); 

代码如下：通过迭代的方式遍历三级页表，PTE2PA函数用于获取页表条目PTE对应的物理地址PA

void vmprint(pagetable_t pagetable)
{
    // there are 2^9 = 512 PTEs in a page table.(一级页表)
    printf("page table %p\n", pagetable);
    for(int i = 0; i < 512; i++) { // 遍历一级页表
        pte_t pte = pagetable[i]; // 对于每一项，如果valid，并且RWX不全为1，说明这一条目有效
        if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0) {
          // this PTE points to a lower-level page table.
          uint64 pa_2 = PTE2PA(pte); // 得到二级页表
          printf("..%d: pte %p pa %p\n",i, pte, pa_2);
          
          // 遍历二级页表 
          for(int j = 0; j < 512; j++) {
              pte_t pte_2 = ((pagetable_t)pa_2)[j];
              if((pte_2 & PTE_V) && (pte_2 & (PTE_R|PTE_W|PTE_X)) == 0) {
                  uint64 pa_3 = PTE2PA(pte_2); // 得到三级页表
                  printf(".. ..%d: pte %p pa %p\n", j, pte_2, pa_3);
                  
                  // 遍历三级页表
                  for(int k = 0; k < 512; k++) {
                      pte_t pte_3 = ((pagetable_t)pa_3)[k];
                      if((pte_3 & PTE_V)) {
                        // printf("debug\n");
                          uint64 pa = PTE2PA(pte_3);
                          printf(".. .. ..%d: pte %p pa %p\n", k, pte_3, pa);
                      }
                  }
              }
          }
        }
    }

}

A kernel page table per process (hard)

xv6 原本的设计是，用户进程在用户态使用各自的用户态页表，但是一旦进入内核态（例如使用了系统调用），则切换到内核页表（通过修改 satp 寄存器，trampoline.S）。然而这个内核页表是全局共享的，也就是全部进程进入内核态都共用同一个内核态页表：

本 Lab 目标是让每一个进程进入内核态后，都能有自己的独立内核页表，为第三个实验做准备。也就是要把内核页表的内容拷贝一份给进程的内核页表副本，同时还拥有进程各自的内核栈，在不同的进程运行时，使用进程的内核页表副本，没有进程运行时，使用全局的内核页表。

创建进程的内核页表和内核栈

1、在进程的结构体proc.h中添加一个字段：

// Per-process state
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  struct proc *parent;         // Parent process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  // lab3 add
  pagetable_t ptb_k;           // kernel page table
};

2、 定义一个函数，用于在初始化进程的时候，初始化一个内核页表的副本（仿照/kernel/main.c中的kvminit函数为页表添加一些固定的映射如UART、CLINE、KERNBASE等，并仿照kvmmap函数，添加一个ptb_kvmmap函数，添加一个参数pagetable_t）；

extern char etext[];  // kernel.ld sets this to end of kernel code.
pagetable_t init_ptb_k()
{
  pagetable_t ptb_k = (pagetable_t) kalloc();
  if(ptb_k == 0) return 0;

  memset(ptb_k, 0, PGSIZE);

  // 使用自定义的kvmmap函数进行一些必须有的内核页表项（UART0、VIRTIO0等）的映射
  ptb_kvmmap(ptb_k, UART0, UART0, PGSIZE, PTE_R | PTE_W);
  ptb_kvmmap(ptb_k, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);
  ptb_kvmmap(ptb_k, CLINT, CLINT, 0x10000, PTE_R | PTE_W);
  ptb_kvmmap(ptb_k, PLIC, PLIC, 0x400000, PTE_R | PTE_W);
  ptb_kvmmap(ptb_k, KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X);
  ptb_kvmmap(ptb_k, (uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W);
  ptb_kvmmap(ptb_k, TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);

  return ptb_k;
}

// 用于进程的内核页表副本的vmmap,添加了参数pagetable_t ptb_k
void ptb_kvmmap(pagetable_t ptb_k, uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(ptb_k, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

在allocproc函数中，调用init_ptb_k函数。在原本的使用内核页表的程序中，在kernel/main.c中procinit.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.

      // （lab3）move to allocproc
      // 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();
}

在allocproc中初始化内核页表副本和分配、映射进程对应的内核栈

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); 
  if(p->pagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
	
  // lab3 add begin
  // 在main.c/procinit()中对所有的64个进程预先分配了一个内核栈，用于用户进程陷入内核态后使用的栈
  p->ptb_k = init_ptb_k();
  // 1、删除procinit函数中对所有进程内核栈的分配和映射
  // 2、在各自的进程中对内核栈进行分配
  char *pa = kalloc();
  if(pa == 0)
    panic("kalloc");
  uint64 va = KSTACK((int) (p - proc));
  ptb_kvmmap(p->ptb_k, va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
  p->kstack = va; 
  
  // lab3 add end
  
  // 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;
}

切换到进程内核页表

scheduler函数用于对于cpu c，遍历全局的进程数组，找到第一个状态为RUNNABLE的进程，并切换到这个进程。

因此，仿照kvminithart()函数，在上下文切换之前，加载进程p提供的内核页表副本，并在返回时及时恢复全局的内核页表

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;
		
		//lab3 add begin
        // 切换成进程的内核页表副本
        if(p->ptb_k) {
            w_satp(MAKE_SATP(p->ptb_k));
            sfence_vma();
        }
         
        swtch(&c->context, &p->context); //通过swtch.S中的汇编程序进行cpu的上下文切换，在lab7中提及

        kvminithart(); // 需要及时恢复内核的页表
        // lab3 add end
        
        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;

        found = 1;
      }
      release(&p->lock);
    }
#if !defined (LAB_FS)
    if(found == 0) {
      // kvminithart(); // 恢复内核的页表
      intr_on();

      asm volatile("wfi");
    }
#else
    ;
#endif
  }
}

释放进程内核页表和内核栈

在进程销毁之前，需要释放进程中使用的空间，需要对之前创建的内核页表副本和内核栈进行释放。

注意：对于内核页表副本，只能释放页表本身占用的物理空间，不能释放页表的叶子节点对应的物理页（这会导致内核运行所需要的关键物理页被释放，导致内核崩溃。）

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

  // lab3 add begin
  // 释放进程的内核栈
  void * pa = (void *)kvmpa2(p->ptb_k, p->kstack); // 使用kvmpa2函数，传入页表和虚拟地址，返回物理地址
  kfree(pa);
  p->kstack = 0;

  // 释放进程对应的三级页表，但不释放物理页
  freewalk2(p->ptb_k);
  p->ptb_k = 0;

  p->state = UNUSED;
}

uint64 kvmpa2(pagetable_t ptb_k,uint64 va)
{
  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;

  pte = walk(ptb_k, va, 0);
  if(pte == 0)
    panic("kvmpa");
  if((*pte & PTE_V) == 0)
    panic("kvmpa");
  pa = PTE2PA(*pte);
  return pa+off;
}

void freewalk2(pagetable_t pagetable) // 递归释放内核页表的所有mapping，但是不释放对应的物理页
{
  // 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){ // 对于最高级和中间级，PTE_V为1，但PTE_R|W|X都为0
      // this PTE points to a lower-level page table.
      uint64 child = PTE2PA(pte); 
      freewalk2((pagetable_t)child);
      pagetable[i] = 0;
    }
    else if(pte & PTE_V){
      pagetable[i] = 0; //清空最后一级的页表项
    }
  }
  kfree((void*)pagetable); //释放每一级的页表占用的物理空间
}

//lab3 add end

调试

xv6 kernel is booting

hart 2 starting
hart 1 starting
panic: kvmpa

陷入了kvmpa

查询调用kvmpa的函数：发现只有

kernel/virtio_disk.c

注意到在virtio磁盘驱动virtio_disk.c中调用了kvmpa()将虚拟地址转换为物理地址，这个函数需要改为kvmpa2，因此此时使用的页表是进程的内核页表副本。

disk.desc[idx[0]].addr = (uint64) kvmpa2(myproc()->ptb_k ,(uint64) &buf0); // 这里不能用内核的页表了，因为已经切换成进程的页表了

调用usertests，结果：

test opentest: OK
test writetest: OK
test writebig: OK
test createtest: OK
test openiput: OK
test exitiput: OK
test iput: OK
test mem: OK
test pipe1: OK
test preempt: kill... wait... OK
test exitwait: OK
test rmdot: OK
test fourteen: OK
test bigfile: OK
test dirfile: OK
test iref: OK
test forktest: OK
test bigdir: OK
ALL TESTS PASSED

Simplify copyin/copyinstr (hard)

一开始没看懂是啥意思，英语太差了。。。找了好多博客才看明白要干啥。指导书的提示也很清晰，基本坑的点都提到了。但是容易写错，debug也很麻烦。实在搞不出来就看了答案，要保证思路是大致差不多的。也就是把进程的页表拷贝到进程的内核页表副本。

替换copyin内部的实现为对copyin_new的调用，替换copyinstr内部的实现为对copyinstr_new的调用。

在每个进程的内核页表副本中添加用户地址的映射，从而copyin和copyinstr能够正常工作。

因为进程的虚拟地址空间是从0开始的，根据指导书的提升，把进程的这部分空间移到内核虚拟地址空间PLIC下面这段空间，CLINT这段空间只有在boot过程会使用，后续不需要使用。

因此在kvminit()函数中保留对CLINT的映射，在用户进程创建的内核页表副本中去除对CLINT的映射。

所以这个实验要做的就是把进程的虚拟地址空间对应的页表 拷贝到前面那个实验为每个进程创建的内核页表副本，从而提高copyin的速度（原来copyin是先使用进程的页表把虚拟地址空间翻译成物理地址空间，然后再进行访问。）

也就是要在所有对进程的页表进行修改的地方，都要同步修改操作到进程的内核页表副本里面。

[mit6.s081] 笔记 Lab3: Page tables | 页表 | Miigon’s blog

根据指导书：需要同步的地方有：fork、exec、sbrk函数，以及在kernel/main.c中创建的第一个用户进程。

创建工具方法（copy、缩小）

首先为页表的copy和缩小编写工具方法：

• kvmcopymappings用于将 从oldstart开始的sz字节的PTE拷贝到new
• kvmdealloc用于将PTE从oldsz缩减到newsz，但不释放实际内存

// 参考int uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)，实现进程的页表拷贝到内核的页表，但不拷贝对应的物理页内存
int kvmcopymappings(pagetable_t src, pagetable_t dst, uint64 start, uint64 sz)
{
  pte_t *pte;
  uint64 pa, i;
  uint flags;
  // prevent re-mapping already mapped pages (eg. when doing growproc)
  for(i = PGROUNDUP(start); i < start + sz; i += PGSIZE){
    if((pte = walk(src, i, 0)) == 0)
      panic("kvmcopymappings: pte should exist");
    if((*pte & PTE_V) == 0)
      panic("kvmcopymappings: page not present");
    pa = PTE2PA(*pte);

    flags = PTE_FLAGS(*pte) & (~PTE_U); //清空PTE_U flag，这里要注意，指导书有提示，要清除这个标志。内核才能访问这个页

    if(mappages(dst, i, PGSIZE, pa, flags) != 0){
      goto err;
    }
  }
  return 0;

 err:
  uvmunmap(dst, PGROUNDUP(start), (i-PGROUNDUP(start)) / PGSIZE, 0); //把前面的页全部释放掉（PTE），但不释放物理页
  return -1;
}


// 参考uvmdealloc，将程序内存从oldsz缩减到newsz，但不释放实际内存，用于同步用户页表程序内存映射与内核页表程序内存映射的同步
uint64 kvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
{
  if(newsz >= oldsz)
    return oldsz;

  if(PGROUNDUP(newsz) < PGROUNDUP(oldsz)){
    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 0);
  }

  return newsz;
}

fork

修改fork函数，调用kvmcopymappings进行拷贝

// Copy user memory from parent to child.
  // 添加将用户页表拷贝到内核页表
  if((uvmcopy(p->pagetable, np->pagetable, p->sz) < 0) || (kvmcopymappings(np->pagetable, np->ptb_k, 0, p->sz) < 0))
  {
    freeproc(np);
    release(&np->lock);
    return -1;
  }

exec

添加检查，防止程序内存超过PLIC

 if(ph.vaddr + ph.memsz < ph.vaddr)
      goto bad;
    uint64 sz1;
    if((sz1 = uvmalloc(pagetable, sz, ph.vaddr + ph.memsz)) == 0)
      goto bad;
    if(sz1 >= PLIC) { // 添加检测，防止程序大小超过 PLIC
      goto bad; 
    }
    sz = sz1;
    if(ph.vaddr % PGSIZE != 0)
      goto bad;
    if(loadseg(pagetable, ph.vaddr, ip, ph.off, ph.filesz) < 0)
      goto bad;

清除原来内核页表对程序内存的映射，然后重建建立映射

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

  //清除内核页表中对程序内存的旧映射，重新建立映射
  uvmunmap(p->ptb_k, 0, PGROUNDUP(oldsz)/PGSIZE, 0);
  kvmcopymappings(pagetable, p->ptb_k, 0, sz);
    
  // 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);

sbrk/growproc

sbrk实际调用的是growproc，对扩大和缩小都进行同步

int
growproc(int n)
{
  uint sz;
  struct proc *p = myproc();

  sz = p->sz;
  if(n > 0){
    uint64 newsz;
    if((newsz = uvmalloc(p->pagetable, sz, sz + n)) == 0) {
      return -1;
    }
    // 内核中的页表的映射同步扩大
    if(sz + n > PLIC) return -1; 
    if(kvmcopymappings(p->pagetable, p->ptb_k, sz, n) != 0){
      uvmdealloc(p->pagetable, newsz, sz);
      return -1;
    }
    sz = newsz;
  } else if(n < 0){
    uvmdealloc(p->pagetable, sz, sz + n);

    // 内核页表中的映射同步缩小
    sz = kvmdealloc(p->ptb_k, sz, sz + n); //释放sz 到sz+n 的映射，但不释放对应的物理页，在uvmdealloc(p->pagetable,sz,sz + n)已经删过了
  }
  p->sz = sz;
  return 0;

userinit

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

  //对于init进程，第一个用户进程，添加同步映射
  kvmcopymappings(p->pagetable, p->ptb_k, 0, p->sz);
  // 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;
  release(&p->lock);
}

提交

$ make grade
$ make qemu-gdb
pte printout: OK (2.8s) 
== Test answers-pgtbl.txt == answers-pgtbl.txt: FAIL 
    Cannot read answers-pgtbl.txt
== Test count copyin == 
$ make qemu-gdb
count copyin: OK (0.6s) 
== Test usertests == 
$ make qemu-gdb
(151.9s) 
== Test   usertests: copyin == 
  usertests: copyin: OK 
== Test   usertests: copyinstr1 == 
  usertests: copyinstr1: OK 
== Test   usertests: copyinstr2 == 
  usertests: copyinstr2: OK 
== Test   usertests: copyinstr3 == 
  usertests: copyinstr3: OK 
== Test   usertests: sbrkmuch == 
  usertests: sbrkmuch: OK 
== Test   usertests: all tests == 
  usertests: all tests: OK 
== Test time == 
time: OK 
Score: 61/66
make: *** [Makefile:316: grade] Error 1