页表：是一种最受欢迎的操作系统提供给进程私有空间地址和内存的机制。页表决定了内存地址的意义，以及可以访问的内存部分。

页表在xv6中的作用

隔离不同进程的地址空间
复用物理内存：共享库

内存与地址空间

内存

内存与CPU直接交互，由RAM组成，断电后数据就会丢失。在这里我们可以将内存看作一个[0,max]的字节数组(RISC-V加载与储存数据都是以字节为单位，取单字或双字)，地址则是索引，那么CPU对内存进行读写也就和C语言中读写数组元素相似。

在第一章中，简述了进程是如何从磁盘加载到内存中的。那么下图就是内存中程序进程，分别由cat、sh、kernel等进程，那么按照内存是一个数组的假设，这些进程就会占据一段连续的空间。

WARNNING:在这种布局下，会出现一些问题。最明显的就是没有隔离性，在cat中使用指令那么我们就会修改sh的内存映像，更加危险的是会导致内核映像被修改。

(虚拟)地址空间

于是我们提供了地址空间(address space)这个抽象，地址空间就是给每一个进程一个独立的地址空间(虚拟的空间，都是从0到n)，给进程一种只有自己拥有整块内存空间的错觉。

如下图，对于sh、cat、OS这三个进程分配为三个独立的进程空间，如果这是cat还想修改1000地址的值，它也只能修改自己的地址空间了，而不能修改到sh进程的空间了。

address space.png

在地址空间的抽象下，我们实现了地址空间的抽象。实现了隔离性，这样其他进程也就不能访问其他进程的空间，更谈不上修改了。

challege:通过什么硬件支持才能够满足这种地址空间的抽象。并且如何在一个物理内存中复用多个内存，同时能够保持内存的隔离性。

分页硬件:MMU(RISCV)

地址转换

页表是在硬件中通过处理器和内存管理单元（Memory Management Unit）实现。

MMU:是集成到CPU内的一个组件，主要是负责读取虚拟内存的映射表(查看页表)，并通过映射表将虚拟地址转换为物理地址。

RISC-V指令可以操作虚拟地址(VA,virtual address)。

物理地址 PA：机器的RAM或是物理内存的索引
虚拟地址 VA：进程的内存空间索引

RISC-V页表硬件通过映射(mapping)VA到PA，连接了两种地址。对于任何一条带有地址的指令，其中的地址应该认为是虚拟内存地址而不是物理地址。包括我们在C语言程序打印的地址都是虚拟地址。

假设寄存器a0中是地址0x1000，那么这是一个虚拟内存地址。虚拟内存地址会被转到MMU。MMU会将虚拟地址翻译成物理地址。之后这个物理地址会被用来索引物理内存，并从物理内存加载，或者向物理内存存储数据。如下图所示

address map.png

从CPU的角度来说，一旦MMU打开了，它执行的每条指令中的地址都是虚拟内存地址。

地址翻译：MMU中会从内存加载0x1000虚拟地址的映射表到MMU中，如图中所示，0x1000的VA对应0xFFF0的PA。

satp(Supervisor Address Translation and Protection Registers)：存放映射表的物理内存地址。由于映射表保存在内存中，所以satp中保存的是物理地址可以让MMU找到内存中保存的映射表。例如在图例中VA = 0x1000，其中satp = 0x10的物理地址中保存的是这个VA的映射表。

每个程序都会有自己独立的映射表，并且这个映射表定义了应用的地址空间。当进程上下文切换时，同时也需要切换satp寄存器的内容，从而获得新的表单。这样的话就可以将相同的虚拟地址翻译为不同的物理地址了(读写satp寄存器是管理者模式的特权)。

那么这个映射表可以称为页表(page table)，在RISC-V中一个映射表可以有多大，对于每一个VA映射表中都会有一个条目，这样的话在64位寄存器中就会有$2^{64}$个地址。

那么在RISC-V中使用地址条目为粒度来管理，那么映射表也会十分巨大，内存会被这个映射表给耗尽。在实际情况下，不会是一个内存地址对应页表中的一个条目，接着会学习一下页表是如何在RISC-V中工作的。

页表

页表粒度

为每个页(page)创建一个映射表条目，因此每次地址翻译都是针对一个页。RISC-V页表是以4096($2^{12}$，一个页是4KB)字节块为粒度(由1字节转为4096字节)进行内存对齐。

虚拟地址配置

XV6运行在Sv39 RISC-V上，也就是64位虚拟地址的低39位被使用，高25位未被使用,那么这样说虚拟地址的数量就有$2^{27}$大概就是512GB(未使用的25位在更新的CPU中也许会支持更大的空间)。

如下图所示：

虚拟地址，VA = 64位 = EXT(未使用，高25位) + index(中27位) + offset(低12位)
物理地址，PA = 56位 = PPN(中44位) + offset(低12位)

3.1.png

地址翻译

页(page)：由于一个页是4096字节，那么将一个页看作4096字节的数组，那么offset = $2^{12} = 4096$那么12位的offset刚好能够作为一个页的索引。
页表(page table)：在Sv39配置中，一个RISC-V页表是一个$2^{27}$(134,2127,728)页表条目(PTEs,page table entries)的数组。分页硬件通过使用VA中高39位中的27位作为页表的索引来查找PTE。
PTE：每一个包含了44位的物理页编号(PPN，Physical page number)和10位的标志位。
PA：56位的物理地址其中高44位是PTE中的PPN，低12位是复制虚拟地址中的偏移量。

在RISC-V中，物理内存地址是56bit。所以物理内存可以大于单个虚拟内存地址空间，但是也最多到$2^{56}$。

物理地址不是64位主要是因为主板只需要56根线；还有一个原因是这剩余的8位作为一个字节(8位)，那么64位就可以组成内存为$2^{56}$长度的字节数组。但是一般情况下并没有这么大的内存，56位PA还是用不完的。

地址翻译就是将VA中的27位index翻译位44位的page好，剩余的12位offset直接复制即可生成PA。

如下图，是通过页表找到相应页的过程

MMU通过stap的物理地址，从内存中读取页表
用VA中的index找到对应的PTE
用PTE中的PPN与VA，翻译得到PA
PA中的PPN在内存中找到对应的页
PA中的offset找到页中的对应的字节

read mem.png

三级页表

单级页表缺陷

如果使用单级页表，那么每一个进程的页表目录占$2^{27}$大小的内存。在机器上运行多个进程的话内存很快就会被耗尽了,并且我们要查找一个字节也十分的慢(最差的情况在$2^{27}$次才能找到想要的字节)。

多级页表组成

实际上，页表会是一个多级的页表(称为页目录，在risc-v中没有明显的区分page-table与page-directory)。在RISC-V中我们会将27位index分为3个9位的三级index（L2、L1、L0）,三级页表如下图所示。

每一个页目录大小也是一个页大小(内存以页为单位进行划分的)，那么一个页是4096字节，PTE是64位 = 8字节。那么一个页目录的$PTE=4096 / 8 = 512$，那么三级索引每一级index=9，那么$2^{9} = 512$也刚好能够作为一个页目录的索引。

3.2.png

PTE结构(了解)

63 - 54位：预留位，主要是未来的扩展，比如新的RISCV处理器出现后页表也可能发生改变。
53 - 10位：PPN，物理页编号
低十位为标志位，5-10位并不重要。
4位：表示该页能否被用户空间进程访问
1-3位：分别表示是否可以对这个页读、写、执行命令。
0位：valid标志位，表示这个物理页是否存在，设置为1是存在的页。如果读取PTE该位设置为0则会触发缺页异常。

三级页表如何执行

satp存储了根页表页L2(page-table page)的物理地址，将其加载入mmu。就可以获得下一级L1的PPN。
通过根目录的PPN找到中间级页目录，获得最后一级的PPN
在根据最后一级这个PPN+offset(VA中继承)就可以合成PA了。

注意：如何获得下一级的页目录的地址的？并不是加上VA的offset而是，通过PPN + 12bit的0，这样就是获得了下一级的页目录的56位PA。因此也就要求页目录需要与物理页对齐(简单来说就是页目录的起始位置就是某个页的起始地址，也就不需要页索引)

由于三级页表是树这样的数据结构，那么我们可以统计一下每一级页表最多有多少页

L2：1页：512PTE
L1：512页(上一级有512PTE) ： $512* 512PTE = 2^{18}PTE$。
L0：$2^{18}$页(上一级有$2^{18}$PTE) ：$2^{18} * 512 PTE = 2^{27}PTE$

三级页表相比于一级页表会多保存L2、L1页目录513页，内存看似是多了，但是实际上我们并不需要，让每一个页表页都存在。

三级页表的优势

节省内存空间：如果进程中有大部分地址没有使用。那么在三级页表下需要多少个PTE来映射指定的一个页(只有这一个页)？

根页目录下我们需要一个索引为0的PTE(1)，指向中间为页目录也需要一个索引为0的PTE(2)，最后指向最低的页目录(页表)。因此在这三步下我们只需要分配3个页($3*512$PTE)就可以了。如果是单级页表方案中，如果我们查找一个页表还是需要用$2^{27}$个PTE。所需要的空间页大大的减少了。

查找页的效率提高：在3级页表中查找到一个页最差的情况为$3*512$次，而在单级页表中查找一个页最差的情况则是$2^{27}$次。3级页表的方案查找效率也大大提升
能够提高内存的安全性，防止应用程序越界访问内存。

快表(TLB)

TLB = Translation Lookaside Buffer

在三级页表中，当从内存中加载或是存储数据时，基本上都是左三次内存查找。那么对于PA寻址，需要读取三次内存，代价也十分的高。但在实际中，每一个处理器都会对最近使用的VA翻译结果(PPN)都有缓存，这个缓存也被称作为TLB，通常保存PTE的缓存。

因此当CPU第一次翻译VA，通过三次查找页表可以获得最终的PPN，TLB会保存虚拟地址到物理地址的映射关系。那么下一次访问同一个VA时，查看TLB就会直接通过映射得到PA。(应该保存的是VA的index与最终的PPN的映射)

内核地址空间

Xv6为每一个进程维护了一个页表，用于描述每个进程的用户地址空间，加上一个描述单独内核地址空间的页表。

如下图3.3，是xv6中内核地址空间的布局。
3.3.png

物理地址，图右

RISC-V处理器中有4个核，每一个核都有自己的MMU和TLB。

0 - 0x1000：保留的地址
0x1000：boot程序ROM(存在于BIOS中)起始的地址，当主板加电工作，boot程序中的代码就会跳转到0x800000000启动xv6。
0x02000000：CLINT（Core Local Interruptor）也是中断的一部分。
0x0C000000：PLIC中断控制器（Platform-Level Interrupt Controller）
0x10000000：UART0（Universal Asynchronous Receiver/Transmitter）负责与Console和显示器交互。
0x10001000：VIRTIO disk，与磁盘进行交互。
0x8000000 - $2^{56}-1$：是DRAM或内存的地址，0x80000000(KERNBASE)也就是内核进程的起始位置

向IO地址执行读写指令，实际上是实现了IO设备的芯片执行读写，可以认作为直接于设备交互，而不是在读写物理内存。

(内核)虚拟地址，图左

Xv6中内核进程的VA与PA是直接映射的(大部分是相等的关系)，也就是VA=PA。

特别的，有两个类页不是直接映射的。

trampoline页：位于虚拟地址空间的顶部，内核与用户有相同的映射。这个物理页(包含进出内核的代码)映射了到内核虚拟地址空间两次，一次在虚拟地址空间的顶部，一次是直接映射。
kernel stack页(pages)：每一个进程都有自己的内核栈，映射在虚拟地址的高地址中，其中有未映射的保护页(guard page)，这些保护页是无效页(PTE中User位清空)，如果内核栈页溢出，就会触发缺页异常(page fault)并且内核也会崩溃。如果没有保护页发生内核栈溢出将会重写内核内存，会导致错误的操作。

保护页不会映射到物理内存，所以不会浪费物理内存，只是占据了虚拟地址空间的一段靠后的地址。

同时内核栈页被虚拟内存映射了两次，在靠后的地址映射了一次，在PHYSTOP下的data段映射了一次，实际上使用的是靠后的一部分，因为是有保护页的保护。

页权限

Kernel text page标记位R-X，可以读取或在该地址执行指令，但是不能向该页写入数据。(该页用于存放代码，因此可以读与执行)
Kernel text page需要能够被写入，所以是RW-权限。并且不能执行该地址段的指令，所以X标志位没有设置。(该页用于存储数据，能够读写)

通过权限设置，我们可以就可以尽早的发现Bug，出现Page fault就可以处理这些错误了。

代码：创建地址空间

vm.c

大部分操作地址空间和页表的xv6代码存在于vm.c中。重要的数据结构是指向RISC-V的顶层页表页的指针pagetable_t。

1 2	typedef uint64 pte_t; typedef uint64 *pagetable_t; // 512 PTEs

重要的函数

walk，它可以找到虚拟地址指向的PTE。
mappages，为新的的映射创建PTE ，参数分别为页表地址、虚拟地址、物理地址、标志位。

int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
  uint64 a, last;
  pte_t *pte;

  if(size == 0)
    panic("mappages: size");

  a = PGROUNDDOWN(va);
  last = PGROUNDDOWN(va + size - 1);
  for(;;){
    if((pte = walk(pagetable, a, 1)) == 0)
      return -1;
    if(*pte & PTE_V)
      panic("mappages: remap");
    *pte = PA2PTE(pa) | perm | PTE_V;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

copyout与copyin，由系统调用提供，复制数据到或从用(to and from)户虚拟地址空间

1 2	int copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len);

在更早的引导顺序中，main调用kvminit使用kvmmake创建内核页表。这个调用在xv6在RISC-V开启分页之前发生。根据内核需求，调用kvmmap去创建翻译。

proc_mapstack分配内核栈给每一个进程。在该函数中调用kvmmap通过KSTATK映射到虚拟地址生成，而且保存了无效页(保护页)。

walk函数

walk模拟了RISC-V分页硬件一样为虚拟地址查找PTE。wakl按照三级页表规则一级一级的去查找。如果PTE无效，也就是需要的页没有分配，如果alloc的参数设置了，那么walk分配一个新的页表并将该页表物理地址放入PTE。最后返回第三级页表PTE的地址。

---vm.c
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
  if(va >= MAXVA)
    panic("walk");

  for(int level = 2; level > 0; level--) {
    pte_t *pte = &pagetable[PX(level, va)];
    if(*pte & PTE_V) {
      pagetable = (pagetable_t)PTE2PA(*pte);
    } else {
      if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
        return 0;
      memset(pagetable, 0, PGSIZE);
      *pte = PA2PTE(pagetable) | PTE_V;
    }
  }
  return &pagetable[PX(0, va)];
}

main.c

main函数调用kvminithart创建内核页表。它将根页表页的地址写入satp寄存器，然后CPU使用内核页表翻译地址。

TLB

每个RISV-V CPU缓存PTE在TLB中，当xv6更换页表，TLB必须告诉CPU无效相应以缓存的TLB条目(如果不更换，在切换进程时，相同的VA就会篡改前一个进程的内存)。

RISC-V中有一个指令sfence.vma，它可以刷新当前CPU的TLB。xv6重载satp后在kvinithart中执行sfence.vam，并且在trampoline代码中返回到用户空间之前，切换到用户页表。

物理内存分配

内核必须在运行期(run-time)为页表、用户内存、内核栈、管道缓存，分配和释放物理内存。

Xv6在运行期能够分配的物理内存在内核结束和PHYSTOP之间。它分配和释放是以4096字节一页为单位。内核使用一个(数据域为空)链表freelist(kernel/kalloc.c)跟踪空闲物理内存，在syscall实验中我们也使用过这个链表统计空闲内存。

用户地址空间

每个进程都有自己单独的页表，当xv6切换进程，它将会切换页表。图3.4展示了比图2.3更加详细的用户进程空间分配。

用户进程的地址空间都是从0增长到MAXVA，规则上一个进程能够达到256GB但是xv6的物理内存只有128MB，#define PHYSTOP (KERNBASE + 128*1024*1024)。
进程地址空间由页(pages)组成，包含了程序的文本段(text)、初始化数据段(data)、栈页(one page)、堆页(pages)。并且这些页的全是都是RWU。
栈是一个单独页，显示的是exec创建的初始内容。包含了命令行参数的字符串，由一个数组指针指向它们位于栈顶端，在他下面是允许程序在main启动的值。
为检查用户分配栈内存是否溢出，xv6放置一个保护页(PTE_U被清空)在栈页正下方。如果栈溢出进程会尝试使用栈下方的地址，那么硬件会生成缺页异常。
xv6使用kalloc分配物理页，然后添加PTE到进程页表，PTE指向新的物理页。Xv6设置PTE的flag标志位。大部分进程不会使用整个用户地址空间，xv6也会

3.4.png

页表优点

隔离性：不同的进程的页表翻译相同用户地址到不同的物理内存页，因此每个进程有自己私有的地址空间
进程地址连续性：每个进程看见自己的内存都是一段连续的从0开始的虚拟地址，但进程的物理内存并不一定是连续的。
可复用：内核映射trampoline页的代码在用户地址空间的顶部(PTE_U = 0，用户不能对该页进行操作)，因此单一的页可以通过物理内存加载到所有进程的地址空间中。