MIT6.S081_2020_Lab3:page tables

实验要求

前言

本来想把MIT6.S081的每个lab都做一个总结，后来发现单单做一个lab3就已经很费力气，后续打算只将较难的实验总结出来

一、理清实验的目的：原本的流程存在什么问题？我们为什么要这样做？

虚拟地址(virtual address -va)到物理地址(physical address-pa)的转化需要借助MMU（内存管理单元MMU，Memory Management Unit），XV6 中MMU可以将satp中装载的内核页表上的虚拟地址转化为物理地址。

Xv6为每个进程维护一个页表，用以描述每个进程的用户地址空间（pagetable）；外加一个单独描述内核地址空间的页表（kernel_pagetable）（该页表始终在satp中装载）。

这种构造导致kernel_pagetable中没有存储 单一进程的虚拟地址与物理地址的映射关系，MMU无法根据给出的虚拟地址来直接得到对应的物理地址。

1.xv6对待用户地址传来的虚拟地址采用间接查询的方法来查询对应物理地址

这种方法的实现关键XV6采用的 虚拟地址与物理地址的映射关系 与 walk函数（kernel/vm.c）

1.1虚拟地址与物理地址映射

XV6系统的虚拟地址有64位，但本系统基于Sv39 RISC-V运行，这意味着它只使用64位虚拟地址的低39位；而高25位不使用。

低12位的Offset为字节偏移量，地址空间本身是以4096byte为单位进行分配的，Offset用于定位虚拟地址在页表中的起始位置。进行地址转化时，虚拟地址中的Offset应该保留在物理地址的低12位。

页表以三级的树型结构存储在物理内存中。

剩余27位（39-12）被分为3部分，用来索引不同层级的PTE（PageTable Entry）,可以将Page Table 理解为数组首元素，那么9位的地址可以看作偏移量，首元素地址+偏移量==PTE

PTE分为两部分：Physical Page Number（PPN） 与 FLags，PPN用于指出下一Page Table的地址（首元素地址），FLag表示操作系统拥有的权限（Xv6系统的权限管理简单，只拥有用户态和内核态的区别，没有引入多用户权限管理）。

以上的结构意味着，只需要给出虚拟地址与最高级页表对应的物理地址，我们可以不借助MMU就查询到虚拟地址最后所对应的物理地址。实际上walk函数就是基于这个思想实现的。

1.2walk函数

//根据Level不同，取出不同的偏移值
#define PXMASK          0x1FF // 9 bits
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
//将物理地址pa转化为pte地址，右移12位是去除OFFSET，左移10位是为FLAG留下空间
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
//将pte地址转化为pa
#define PTE2PA(pte) (((pte) >> 10) << 12)

// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va.  If alloc!=0,
// create any required page-table pages.

// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
//   39..63 -- must be zero.
//   30..38 -- 9 bits of level-2 index.
//   21..29 -- 9 bits of level-1 index.
//   12..20 -- 9 bits of level-0 index.
//    0..11 -- 12 bits of byte offset within the page.
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  //检查虚拟地址是否合法，MAXVA为虚拟地址的最大值
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];//去除va对应level的9bit地址，即pte
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      //查询的PTE暂时不存在
      //如果alloc==0或者剩余空间不足，那么就无法分配新的物理地址给PTE,返回0（失败）
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];//返回level为0的最低pte
}

1.3原来的copyin函数

//page以4096个字节为单位，取a所在page的结束地址
#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
//page以4096个字节为单位，取a所在page的起始地址
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))


// Look up a virtual address, return the physical address,
// or 0 if not mapped.
// Can only be used to look up user pages.
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0)
    return 0;
  if((*pte & PTE_V) == 0)
    return 0;
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}



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

从代码可以看出，原本的copyin函数就是通过使用walk函数查找va对应的pa，将数据从用户复制到内核。

1.4本实验的目的

将数据从用户复制到内核，原本需要借助walk函数查询三次页表，实验要求我们完成之后不借助walk函数，通过MMU来找到物理地址。

2.为什么要使用MMU？其相比walk函数优越在哪？

其实这个问题也可以理解为：既然通过使用函数调用的方式就可以将虚拟地址VA转化为物理地址PA，那么我们为什么还需要一个MMU硬件？

我们可以再将这个问题深化，为什么计算机许多功能，我们通过软件可以实现，还要设计一个专用的硬件来实现这个功能呢？

2.1专用硬件意味着对CPU占用的减少，会增加计算机的运行速度

CPU资源在计算机的运行过程中是很宝贵的，我们为常用的功能设计一个硬件，便可以减少对CPU资源的占用，让它分配给更需要的程序。比如GPU的诞生就是为了将图形相关的计算从CPU分离出来，提高计算机的运行效率。

2.2回归MMU本身，MMU等硬件可以通过TLB（Translation Look-aside Buffer）等机制来获得比CPU更快的速度

2.3既然计算机拥有MMU这个硬件，那么我们就应该尽量让MMU能实现的功能通过MMU实现，而非自己编写函数通过CPU实现

3.修改后的虚拟地址转化方式

1. MMU的实现需要我们在stap中设定正确的page table，这意味着我们在用户态与内核态的切换过程中，需要切换stap所指的page table，我们为每一个进程都设置一个proc_kernel_pagetable

2. 切换page table除了能够满足转化用户态的虚拟地址到物理地址的功能，还要保证内核态原本功能的正常运行。

   为了满足以上两点要求，势必要求我们对kernel_pagetable（描述内核地址空间的页表）的具体构成有更加深入的了解

二、进程地址空间的认识与修改

XV6 地址空间的介绍

1.物理地址的布局（图右）

/home/shui/xv6-labs-2020/kernel/memlayout.h

// 物理地址布局
// Physical memory layout

// qemu -machine virt is set up like this,
// based on qemu's hw/riscv/virt.c:
//
// 00001000 -- boot ROM, provided by qemu
// 02000000 -- CLINT
// 0C000000 -- PLIC
// 10000000 -- uart0 
// 10001000 -- virtio disk 
// 80000000 -- boot ROM jumps here in machine mode
//             -kernel loads the kernel here
// unused RAM after 80000000.

// the kernel uses physical memory thus:
// 80000000 -- entry.S, then kernel text and data
// end -- start of kernel page allocation area
// PHYSTOP -- end RAM used by the kernel

0x02000000-KERNBASE 为 I/O devices，为硬件对应的物理地址

KERNBASE(80000000)-end（*// first address after kernel .defined by kernel.ld.*） kernel 加载的区域，

end-PHYSTOP（#define PHYSTOP (KERNBASE + 128*1024*1024)） 实际参与Page分配（kalloc）的物理地址

2.内核地址空间（kernel_pagetable）的页表布局（图左）

​

2.1 内核使用“直接映射”获取内存和内存映射设备寄存器；也就是说，将资源映射到等于物理地址的虚拟地址。

那么意味着我们的proc_kernel_pagetable，需要模仿kernel_pagetable，映射内存和内存映射设备寄存器

kernel_pagetable 内核页表直接映射的相关代码：

/kernel/vm.c
    
/*
 * create a direct-map page table for the kernel.
 */
void
kvminit()
{
  //分配page 
  kernel_pagetable = (pagetable_t) kalloc();
  //用0填充page继续初始化
  memset(kernel_pagetable, 0, PGSIZE);
  //直接映射I/0设备
  // uart registers
  kvmmap(UART0, UART0, PGSIZE, PTE_R | PTE_W);

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

  // CLINT
  kvmmap(CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  kvmmap(PLIC, PLIC, 0x400000, PTE_R | PTE_W);

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

  // map kernel data and the physical RAM we'll make use of.
  kvmmap((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.
  kvmmap(TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
}

// add a mapping to the kernel page table.
// only used when booting.
// does not flush TLB or enable paging.
void
kvmmap(uint64 va, uint64 pa, uint64 sz, int perm)
{
  if(mappages(kernel_pagetable, va, sz, pa, perm) != 0)
    panic("kvmmap");
}

//在pagetable上映射va到pa

// Create PTEs for virtual addresses starting at va that refer to
// physical addresses starting at pa. va and size might not
// be page-aligned. Returns 0 on success, -1 if walk() couldn't
// allocate a needed page-table page.
int
mappages(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");
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

初始化进程自己的内核页表,这个kernelpagetable可以看作proc_kernel_pagetable：

pagetable_t
uvmkernelpagetableinit(){
  pagetable_t kernelpagetable=uvmcreate();
  if(kernelpagetable==0)
    return 0;
  // uart registers
  uvmmap(kernelpagetable,UART0, UART0, PGSIZE, PTE_R | PTE_W);

  // virtio mmio disk interface
  uvmmap(kernelpagetable,VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);

  // CLINT 用户进程的最大地址空间不能超过plic，所以不要映射plic
  // uvmmap(kernelpagetable,CLINT, CLINT, 0x10000, PTE_R | PTE_W);

  // PLIC
  uvmmap(kernelpagetable,PLIC, PLIC, 0x400000, PTE_R | PTE_W);

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

  // map kernel data and the physical RAM we'll make use of.
  uvmmap(kernelpagetable,(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(kernelpagetable,TRAMPOLINE, (uint64)trampoline, PGSIZE, PTE_R | PTE_X);
  return kernelpagetable;
}

2.2在原本的内核页表中（kernel_pagetable），每一个进程都有对应的内核栈，我们应该确保进程自身的内核页表(proc_kernel_pagetable)，拥有进程自身的内核栈

kernel_pagetable为每一个进程分配内核栈：

// 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);
      p->kstack = va;
  }
  kvminithart();
}

本来的kernel_pagetable为每一个进程分配内核栈，在为每一个进程增加一个proc_kernel_pagetable后，我们只在没有进程运行时才在stap中加载kernel_pagetable，所以proc_kernel_pagetable上映射的kstack与kernel_pagetable不同也可以

/kernel/proc.c static struct proc* allocproc(void)


//在进程的内核页表中设置直接映射，并设置guard page，
  char *pa = kalloc();
      if(pa == 0)
        panic("kalloc");
      uint64 va = KSTACK((int) (p - proc));
      uvmmap(p->kernelpagetable,va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
      p->kstack = va;

// map kernel stacks beneath the trampoline,
// each surrounded by invalid guard pages.
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE）

2.2.1guard page是什么？

每个进程都有自己的内核栈，它将映射到偏高一些的地址，这样xv6在它之下就可以留下一个未映射的保护页(guard page)。保护页的PTE是无效的（也就是说PTE_V没有设置），所以如果内核溢出内核栈就会引发一个异常，内核触发panic。如果没有保护页，栈溢出将会覆盖其他内核内存，引发错误操作。恐慌崩溃（panic crash）是更可取的方案。（注：Guard page不会浪费物理内存，它只是占据了虚拟地址空间的一段靠后的地址，但并不映射到物理地址空间。）

2.3 在内核更改进程的用户映射的每一处（pagetable），都以相同的方式更改进程的内核页表（proc_kernel_pagetable）

因为MMU本身也是需要内核页表中实际存在虚拟地址到物理地址的映射关系的，那么在涉及到用户映射的时候，我们需要将进程页表（pagetable）虚拟地址到物理地址的映射关系同步到进程的内核页表（proc_kernel_pagetable）上，实际上我们可以通过修改更多代码，让进程的内核页表完全顶替内核页表的作用，只是一口吃不成一个大胖子，我们应该先确保进程内核页表的实现，再考虑去除进程页表（实际上本人没有进行去除操作）。

//将old页表中beginsz至endsz的内容，复制到new页表的beginsz至endsz
void
utkvmcopy(pagetable_t old, pagetable_t new, uint64 beginsz, uint64 endsz){
  pte_t *pte_from, *pte_to;
  beginsz = PGROUNDUP(beginsz);
  for (uint64 i = beginsz; i < endsz; i += PGSIZE){
    if((pte_from = walk(old, i, 0)) == 0)
      panic("utkvmcopy: src pte does not exist");
    if((pte_to = walk(new, i, 1)) == 0)
      panic("utkvmcopy: pte walk failed");
    uint64 pa = PTE2PA(*pte_from);
    uint flags = (PTE_FLAGS(*pte_from)) & (~PTE_U);
    *pte_to = PA2PTE(pa) | flags;
  }
}

2.3.1什么时候内核页表（pagetable）会有映射关系的改变？

我们需要搞明白xv6系统每一个进程的生成方式：除了pid=1的进程是在启动阶段生成，其余的进程都是通过fork方式从父进程中生成，我们需要复制映射关系倘若我们需要执行不同的代码，fork之后进程exec操作，将进程结构中存储的代码替换掉，我们需要修改映射关系

倘若进程空间不足或过多，使用sbrk函数分配新空间，我们需要增删映射关系

进程运行结束后，释放页表时，应该去除进程pagetable上的映射的关系

而xv6本身针对于上述情况下pagetable上的映射关系变化的代码已经很完善了，我们无需做任何修改，只需要在相关代码中添加

utkvmcopy(p->pagetable,p->kernelpagetable,0,sz);

便可以让proc_kernel_pagetable中存有虚拟地址到物理地址的映射关系

2.4 切换进程时(kernel/proc.c/scheduler(void)),切换stap所指的页表,并刷新TLB

void
uvminithart(pagetable_t kernelpagetable){
// supervisor address translation and protection;
// holds the address of the page table.
  w_satp(MAKE_SATP(kernelpagetable));
  // flush the TLB.
  sfence_vma();
}

三、存在的问题

I/O设备的虚拟地址是直接映射的，而我们将page_table上的映射关系直接复制到了proc_kernel_pagetable上，这意味这va的大小不能超过最低的I/O设备的地址空间

四、其他

1.为什么要使用三级页表而非一级页表（来自课堂学生提问）

Frans教授：这是个好问题，这的原因是，3级page table中，大量的PTE都可以不存储。比如，对于最高级的page table里面，如果一个PTE为空，那么你就完全不用创建它对应的中间级和最底层page table，以及里面的PTE。所以，这就是像是在整个虚拟地址空间中的一大段地址完全不需要有映射一样。