操作系统MIT 6.S081 xv6内核（四）：Page Table实验

Print a page table实验

实验目的

当您启动xv6时，它应该像这样打印输出来描述第一个进程刚刚完成exec(),init时的页表：

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

打印内容，第一行是page table指针，后面为页表虚拟内存和物理内存，即每级页表内容。".."代表子表树的深度，数字代表页表项编号，后面每项为虚拟内存与物理内存的映射关系，在实验中，你的虚拟内存和上述应该是一致的，物理内存可以不同。

因此实验目标是通过遍历顶级页表及其子页表，将虚拟内存和物理内存指针打印出来，为了使系统启动打印以上输出，将函数调用放在第一个进程exec.c的代码中。

具体实现

在exec.c中的return argc之前插入
1
2
if(p->pid==1)
vmprint(p->pagetable,0);
vmprint由我们自己实现，参数后面介绍。

kernel/defs.h加入函数声明：

1	void vmprint(pagetable_t,uint64);

vmprint实现： recurlayers参数用于递归实现，初始时为0，打印page table指针；后面的结点使用迭代打印".. "，再递归打印子页表的信息；因为示例顺序是从上到下深度递归打印，而不是回溯，因此递归逻辑放在打印之后。

void vmprint(pagetable_t pagetable,uint64 recurlayers){
  if(recurlayers==0)        //起始时打印，递归不打印
    printf("page table %p\n",pagetable);
  for(int i=0;i<512;i++){    //顶级页表512个页表项
    pte_t pte=pagetable[i];
    uint64 child =PTE2PA(pte);  //子页表物理地址
    if((pte&PTE_V)&&recurlayers<=2){  //页表项有效，xv6采用三级页表，递归层数<=2就够了（退出逻辑）
      for(int j=0;j<recurlayers;j++) //打印..随层数增加
        printf(".. "); 
      printf("..%d: pte %p pa %p\n",i,pte,child);	
      vmprint((pagetable_t)child,recurlayers+1); //递归到下一层
    }
  }
}

完整commit详见：vmprint Done

A kernel page table per process实验

实验目的

这个实验主要为了下文第三个实验做铺垫。在进程的用户空间中，xv6会维护一个用户页表，这个页表包含虚拟内存到物理内存的映射；而目前系统只维护了一个系统内核页表kernel_pagetable，这个页表由所有的进程进行共享，因此每个用户进程的映射在内核中是无效的。因此如果内核想要使用用户的指针，必须通过walk将其转换成物理地址再使用。

现在我们想在进程中维护一个内核页表，这个内核页表为每个进程独有，这样内核页表可以直接采取用户空间的映射，每次从用户空间获取数据不需要通过walk实现，简化了数据跨态传输。

本实验的任务就是实现这样的一个内核页表，保证当前内核页表的维护、调度和原来的共享页表一致。

具体实现

在proc.h的struct proc结构体增加内核页表字段：pagetable_t knel_pagetable,这样进程创建就会创建一个内核页表对象。

然后了解内核页表内容包含了什么页面，将这些页面映射到进程内核页表中，再将这个页表映射到物理内存，以前的共享内核页表不再使用，首先我们先参考proc.c原来的内核页表是如何实现这样的映射关系的：调用了proc_pagetable，进行了三个工作：调用uvmcreate，作用是kalloc申请页帧，填充空数据，返回一个用于存放页表空间，然后调用mappages将trampoline和trapframe映射到物理内存，并且设置对应的页表项。

pagetable_t
proc_pagetable(struct proc *p)
{
  pagetable_t pagetable;

  // An empty page table.
  pagetable = uvmcreate();  //分配物理空间
  if(pagetable == 0)
    return 0;

  // map the trampoline code (for system call return)
  // at the highest user virtual address.
  // only the supervisor uses it, on the way
  // to/from user space, so not PTE_U.
  if(mappages(pagetable, TRAMPOLINE, PGSIZE,
              (uint64)trampoline, PTE_R | PTE_X) < 0){
    uvmfree(pagetable, 0);
    return 0;
  }

  // map the trapframe just below TRAMPOLINE, for trampoline.S.
  if(mappages(pagetable, TRAPFRAME, PGSIZE,
              (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  return pagetable;
}

可见共享页表只映射了TRAMPOLINE和TRAPFRAME（还有后面的内核栈空间），我们需要在vm.c定义映射函数：

//将kvmmap的参数增加knel_pagetable:映射到独享页表
void mykvmmap(uint64 va, uint64 pa, uint64 sz, int perm,pagetable_t knel_pagetable)
{
  if(mappages(knel_pagetable, va, sz, pa, perm) != 0)
    panic("mykvmmap");
}

//同kvminit,映射关系涵盖内存各个部分（除内核栈），CLINT是特殊的一个映射，将在test3讨论
pagetable_t mykvminit()
{
  pagetable_t knel_pagetable=(pagetable_t)kalloc();  //分配物理空间
  if(knel_pagetable==0)
    return 0;
  memset(knel_pagetable, 0, PGSIZE);

  // uart registers
  mykvmmap(UART0, UART0, PGSIZE, PTE_R | PTE_W,knel_pagetable);

  // virtio mmio disk interface
  mykvmmap(VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W,knel_pagetable);

  // CLINT
  mykvmmap(CLINT, CLINT, 0x10000, PTE_R | PTE_W,knel_pagetable);

  // PLIC
  mykvmmap(PLIC, PLIC, 0x400000, PTE_R | PTE_W,knel_pagetable);

  mykvmmap(KERNBASE, KERNBASE, (uint64)etext-KERNBASE, PTE_R | PTE_X,knel_pagetable);

  mykvmmap((uint64)etext, (uint64)etext, PHYSTOP-(uint64)etext, PTE_R | PTE_W,knel_pagetable);

  mykvmmap(TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X,knel_pagetable);
  return knel_pagetable;
}

在proc.c的allocproc实现相同的调用即可：

//allocproc函数：初始化独享页表的映射
  p->knel_pagetable=mykvminit();
  if(p->knel_pagetable==0){
  freeproc(p);
  release(&p->lock);
  return 0;
}

内核栈映射proc.c，还是先看procinit共享内核页表是如何实现的：

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

通过遍历进程，遍历时为每个进程申请物理内存，虚拟内存va = KSTACK((int) (p - proc))，即通过p-proc获取当前内核栈的编号，即第一个进程虚拟内存就是KSTACK0，然后KSTACK1......这样每个进程在内核中有一个独立的栈空间。

在我们独立进程页表，就没必要循环了，在proc.c的allocproc直接创建即可：

char *pa = kalloc();
if(pa == 0)
panic("kalloc");
uint64 va = KSTACK((int) (p - proc));  //不唯一，可自定义其他
mykvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W,p->knel_pagetable);
p->kstack = va;

修改proc.c中scheduler函数，scheduler是调度器函数，核心实现部分（加入内核页表切换后）：

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

        //加入内核页表切换
        mykvminithart(p->knel_pagetable);
        swtch(&c->context, &p->context); //调度器保留cpu上下文，加载选中进程上下文
    
        //调度器返回后
        kvminithart(); 

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;
        found = 1;
      }
      release(&p->lock);
    }
......
}

可以看见，调度循环不断地遍历，找到可以运行的进程，找到会将其置为运行中，并且保留目前CPU上下文到c->context,加载新进程上下文p->context，因此在此之前我们插入mykvminithart(p->knel_pagetable)进行进程内核页表的加载、刷新快表；一旦调度器返回（时间片完成、进程结束、阻塞等），切换回共享内核页表kvminithart()（这是tips要求的）。

其中：

void mykvminithart(pagetable_t knel_pagetable)                         
{
  w_satp(MAKE_SATP(knel_pagetable));
  sfence_vma();
}

修改清理进程内存函数freeproc，很多测试panic都是因为这个函数引起的，目的是及时能够清理页表占用的内存，否则我们自定义的分配函数mykvmmap很有可能失败。首先对内核栈空间进行清理:
1
2
uvmunmap(p->knel_pagetable,p->kstack,1,1);
p->kstack=0;
然后就是页表占用的空间了，这里有两种不同的方法进行清理，当然还会有其他实现：

第一种：proc_myfreewalk：对比freewalk，就是不会对叶子结点报panic，因为要清理的页表对象包含叶子结点，但是无需清理（tips内容），为什么不用清理，这主要考虑到内核的物理内存页帧可能是多个页表共享的，直接清理物理内存有可能导致崩溃；其次，清理PTE也可以将这个空间重新分配给其他页表，因此这样取消映射也是足够的。

void proc_myfreewalk(pagetable_t knel_pagetable)
{
  // similar to the freewalk method
  // there are 2^9 = 512 PTEs in a page table.
  for(int i = 0; i < 512; i++){
    pte_t pte = knel_pagetable[i];
    if(pte & PTE_V){
      knel_pagetable[i] = 0;
    //非叶子结点执行清理
      if ((pte & (PTE_R|PTE_W|PTE_X)) == 0){
        uint64 child = PTE2PA(pte);
        proc_myfreewalk((pagetable_t)child);
      }
    }
  }
  kfree((void*)knel_pagetable);
}

第二种：proc_unmapknel_pagetable：调用了uvmunmap取消之前的映射关系，主要这里参数为0代表不要直接释放叶子内存，理由和上面是一致的，由于我们的内核栈、内存各部分的映射都被取消了，即所有末级页表的页表项都是0，因此全部页表都被认为是非叶子结点，也就可以直接调用freewalk，而无需改写了。

void proc_unmapknel_pagetable(pagetable_t knel_pagetable){
  // uart registers
  uvmunmap(knel_pagetable,UART0, 1, 0);
  // virtio mmio disk interface
  uvmunmap(knel_pagetable,VIRTIO0, 1,0);
  // CLINT
  uvmunmap(knel_pagetable,CLINT, 0x10000/PGSIZE, 0);
  // PLIC
  uvmunmap(knel_pagetable,PLIC, 0x400000/PGSIZE, 0);
  uvmunmap(knel_pagetable,KERNBASE,((uint64)etext-KERNBASE)/PGSIZE, 0);
  uvmunmap(knel_pagetable, (uint64)etext, (PHYSTOP-(uint64)etext)/PGSIZE, 0);
  uvmunmap(knel_pagetable,TRAMPOLINE, 1, 0);
  freewalk(knel_pagetable);
}

修改vm.c的kvmpa：virtio 磁盘驱动 virtio_disk.c调用这个函数将虚拟地址转换成物理地址，kernel_pagetable不再使用了，因此使用myproc()->knel_pagetable代替。
1
2
//pte = walk(kernel_pagetable, va, 0);改为：
pte =walk(myproc()->knel_pagetable,va,0);
记得包含头文件：
1
2
#include "spinlock.h"
#include "proc.h"
而且头文件顺序不能颠倒，否则有可能会报lock不兼容的错误，这谁又想到呢，卡了几十分钟才发现。。。

最后，基本就可以ac了，进入xv6键入查看是否通过全部测试；

usertests

完整commit参考:Myknel_pagetable Done

Simplify copyin/copyinstr实验

实验目的

从第二节实验，我们实现了进程独立的内核页表，现在我们需要利用这个页表实现简化的copyin、copyinstr操作，简化的地方就是不需要通过walk找到用户指针的物理内存，而是在内核中直接解引用。新的copyin_new、copyinstr_new函数已经实现并且定义在kernel/vmcopyin.c中，我们需要做的就是用它们替代旧的两个函数；

其次需要修改涉及内核、用户之间空间映射的函数，包括fork、exec、sbrk，以及用户进程初始化函数userinit。

这些修改会涉及两个问题，一个是PTE权限问题，一个是低地址的CLINT问题。

具体实现

使用kernel/vmcopyin.c中的copyin_new和copyinstr_new代替kernel/vm.c中的copyin和copyinstr(注释原函数)。

int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len){
  return copyin_new(pagetable,dst,srcva,len);
}
int copyinstr(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max){
  return copyinstr_new(pagetable,dst,srcva,max);
}

在kernel/defs.h添加函数声明：

1 2	int copyin_new(pagetable_t, char , uint64, uint64); int copyinstr_new(pagetable_t, char , uint64, uint64);

这两个新的函数都直接使用了虚拟地址向内核缓冲区dst拷贝数据，在旧函数中必须先通过walk将其转换成物理地址，才能进行拷贝，所以说明此时的虚拟地址在内核中是有效的，使这个地址有效的地方就是我们在进程中维护的独立的内核页表。

// 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_new(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len)
{
  struct proc *p = myproc(); //获取cpu进程
  //虚拟地址越界，复制后虚拟地址越界，len小于0非法
  if (srcva >= p->sz || srcva+len >= p->sz || srcva+len < srcva)
    return -1;
  memmove((void *) dst, (void *)srcva, len);  //将虚拟地址空间直接拷贝到内核缓冲区
  stats.ncopyin++;   // XXX lock  //计数，lock代表该变量可能由多个进程共享，需要加锁保护
  return 0;                                                               
}

// 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_new(pagetable_t pagetable, char *dst, uint64 srcva, uint64 max)
{
  struct proc *p = myproc();
  char *s = (char *) srcva;  //浅拷贝，s指向的地址就是srcva的地址
                                                                         
  stats.ncopyinstr++;   // XXX lock
  for(int i = 0; i < max && srcva + i < p->sz; i++){
    dst[i] = s[i];    //直接将srcva地址复制到dst
    if(s[i] == '\0')
      return 0;
  }
  return -1;
}

这个lab省略了copyin_new与内核交互的细节，所以也遗留了一些问题，例如：内核如何区分读入的是虚拟地址还是物理地址？另一个重要的问题是，直接拷贝确实跳过了walk流程，但是内核如何理解这个虚拟地址呢，和原来拷贝方法差异又在哪里呢？用户虚拟地址为什么必须定在0~CLINT？

这是一个关键的点，也是我看到两个新函数产生最大的问题。答案在理论基础已经略微提到过，但是那时候只是把它当成规律一样看待，没有想到其深层的意义：原始的流程是通过walk得到物理地址拷贝到内核空间，注意此时又会产生新的内存虚拟地址，内核必须又通过页表找到物理内存，这个页表就是kernel_pagetable；万幸的是，内核的页表是简单的，大部分采用的是直接映射，除了跳板页和内核栈页，以及没有映射的guard page（详见xv6基础理论。

而新流程是如何呢？答案是直接将用户虚拟地址变成了内存虚拟地址。此时我们维护的独立进程内核页表（knel_pagetable）仍然采用的是直接映射（从实验二的mykvminit可以看出），此时接下来我们做的工作是将用户页表拷贝到内存页表（后文），所以这部分用户映射只能使用0~CLINT，因为高地址都被定义成xv6的直接映射；这样内核就能够区分来自用户的映射和来自物理内存的映射了，这就造成我们需要的效果：通过用户虚拟地址，内核就能得到内核页表指向的物理内存指针。

只有理解了这点，后面的工作才会显得理所应当：将用户页表映射到内核页表。

kernel/vm.c参考uvmcopy添加页表拷贝函数uvm2kvm，并在defs.h声明，相比uvmcopy，无需进行新的物理内存拷贝，去除了kalloc和memmove。新增了oldsz参数，因为映射可以不从0开始，此时则需要上对齐到页帧。

int uvm2kvm(pagetable_t old, pagetable_t new, uint64 oldsz,uint64 newsz)
{
  pte_t *pte_user;
  uint64 pa, i;
  uint flags;
  //参考uvmcopy
  uint64 start=PGROUNDUP(oldsz);  //新增上对齐；
  for(i = start; i < newsz; i += PGSIZE){
    if((pte_user = walk(old, i, 0)) == 0) 
      panic("uvm2kvm: pte should exist"); 
    if((*pte_user & PTE_V) == 0)
      panic("uvm2kvm: page not present");
    pa = PTE2PA(*pte_user);
    flags = PTE_FLAGS(*pte_user);
    if(mappages(new,i,PGSIZE,pa,flags&~PTE_U)!=0){
      uvmunmap(new, start, (i-start)/ PGSIZE, 0);
      return -1;
    }
  }
  return 0;
}

注释kernel/vm.c下CLINT的映射和解映射；

//mykvminit
//mykvmmap(CLINT, CLINT, 0x10000, PTE_R | PTE_W,knel_pagetable);

//proc_unmapknel_pagetable
//uvmunmap(knel_pagetable,CLINT, 0x10000/PGSIZE, 0);

为了防止用户虚拟地址越界，需要在用户页表虚拟内存分配uvmalloc判断是否越界

1 2	if(newsz>=PLIC) return 0;

kernel/proc.c中userinit添加：
1
uvm2kvm(p->pagetable,p->knel_pagetable,0,p->sz);
初始化进程时会将用户页表复制到内核页表中；

kernel/proc.c中fork子进程页表复制完成添加：

//copy child process userpage to knel_pagetable;
if(uvm2kvm(np->pagetable, np->knel_pagetable, 0, np->sz)<0){
  freeproc(np);
  release(&np->lock);
  return -1; 
}

将子进程的用户页表复制到内核页表中。

另一个需要调整的为sbrk函数，其是一个系统调用函数，用于将进程数据段大小（堆大小）扩大，原型被定义在kernel/syscall.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;   //返回进程新的大小
}

其获取参数需要扩展的字节数n，调用kernel/proc.c中的growproc函数为进程扩展n个字节，具体函数如下

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;
    }
  //加入用户、内核映射逻辑
  if(uvm2kvm(p->pagetable,p->knel_pagetable,sz-n,sz)!=0)
    return -1;
  } else if(n < 0){
    sz = uvmdealloc(p->pagetable, sz, sz + n);//减掉了n，为sz-n
    //加入用户、内核映射逻辑
    kvmdealloc(p->knel_pagetable,sz-n,sz); //注意n是负数，是sz-n
  }
  p->sz = sz; //更新进程大小
  return 0;
}

当n大于0（空间扩展），growproc调用uvmalloc函数开辟新页帧存放n大小物理内存，并且在用户页表p->pagetable设置映射关系；因此这部分映射关系也要通过uvm2kvm映射到内核页表；当n小于0，growproc调用uvmdealloc压缩空间，取消用户页表映射并且释放物理内存，但是对于内核页表，取消映射就足够了，不需要释放物理内存，因此我们自己在vm.c实现一个：

//参考uvmdealooc，唯一不同是uvmunmap参数0，即取消映射不会释放物理内存
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); //参数0
  }
  return newsz;
}

调用时注意参数问题，尤其是kvmdealloc的调用，我一时间没反应过来n是负数，写成了kvmdealloc(p->knel_pagetable,sz+n,sz)来压缩空间，发现总会触发map的panic。

最后一个涉及用户向内核传递数据的为系统第一个启动进程kernel/exec.c中的exec函数，系统启动时调用fork产生进程，exec这类命名是进程函数族，用于不新建进程的前提下执行其他进程资源而且不会返回，这里作为xv6首个进程，还承担了检查elf可执行文件、加载elf可执行文件、命令行初始化等脏活，等完成后需要将该进程换成用户空间执行的进程。userinit发生在这个函数调用之后，因此在这里我们还需要手动完成干脏活的旧页表和新用户进程页表的更替，加入：
1
2
uvmunmap(p->knel_pagetable,0,oldsz/PGSIZE,0); //取消旧页表的映射，只是为了安全
uvm2kvm(p->pagetable,p->knel_pagetable,0,p->sz); //新增映射
至此，配置流程应该结束，在第二节实验中我们使用了两种方法进行进程内存的回收，对于proc_myfreewalk(p->knel_pagetable)是没问题的，因为我们直接清理了非叶子结点。但是如果使用的是proc_unmapknel_pagetable(p->knel_pagetable)方法，因为其是取消了所有叶子结点映射再调用freewalk，如果此时清理内存，会出现：freewalk panic: leaf，这是因为有叶子结点，这些叶子结点就来自0~CLINT存在的用户映射。但每次映射都是进程大小而不是CLINT，因此必须加上
1
uvmunmap(p->knel_pagetable,0,PGROUNDUP(p->sz)/PGSIZE,0);
PGROUNDUP上对齐保证参数是整数。

如果有未描述的地方，参考完整commit：Copyin/Copystr Done

总结

这个lab是有关页表的内容，通过这个lab可以比较深刻地理解虚拟内存分配、调度以及分页机制的奥妙。就步骤而言不算复杂，但是往深处想，这需要独立思考，也发现有很多东西需要自己理解，而且有很多答案并不那么确定，我也尝试将它写出来，使得每一步都有合理的原因，当然也少不了是我的猜想、别的大佬的猜想、没有人发表过的问题等等，是否正确还需要更多人给出意见和交流~