MIT6.S081 xv6book chapter3

第三章的主题是页表，单看页表会很抽象，但页表背后的思想是地址空间的隔离。让每个进程都有自己的地址空间，保护地址空间不受他人侵犯。同时，页表管理的“页”，页内地址连续，以页为单位，避免页表过于庞大（多级页表也是为了实现这个目标）。同时，虚拟空间到物理空间的映射，多了几分实用trick，比如内核采用直接映射、内核页表下的guard page（未映射）、内核和用户相同的映射（trampoline page，多对一映射）。

本节融合了课程lec04的内容。虚拟地址的抽象是为了程序的隔离性，理解这点后就很容易了。

地址空间

先回顾一下，我们期望得到什么样的隔离结果？

我们期望的是，每个用户程序都被装进一个盒子里，这样它们就不会彼此影响了，同时它们与操作系统也相互独立。这样，如果某个应用程序无意或故意做了一些坏事，也不会影响到操作系统。这就是我们对于隔离性的期望。

所以，我们想要某种机制，能够将不同程序之间的内存隔离开来，这样类似的事情就不会发生。一种实现方式是地址空间（Address Spaces）。

这里的基本概念也很简单直观，我们给包括内核在内的所有程序专属的地址空间。每个应用程序都能看到0～n的地址空间，同时它们都认为这些地址空间都是自己专有的，其他进程无法访问。换句话说，这些地址空间彼此独立。

所以现在我们的问题是如何在一个物理内存上，创建不同的地址空间，因为归根到底，我们使用的还是一堆存放了内存信息的DRAM芯片。如何在一个物理内存上，创建不同的地址空间？最常见的方法，同时也是非常灵活的一种方法就是使用页表（Page Tables）。

页表

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

对于任何一条带有地址的指令，其中的地址应该认为是虚拟内存地址而不是物理地址。虚拟内存地址会被转到内存管理单元，内存管理单元会将虚拟地址翻译成物理地址。之后这个物理地址会被用来索引物理内存，并从物理内存加载，或者向物理内存存储数据。

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

怎么完成虚拟地址到物理地址的翻译呢？答案就是页表。MMU会有一个表单，表单中，一边是虚拟内存地址，另一边是物理内存地址。

同时，这张表单也需要保存在物理地址中，在运行时加载进内存。所以，CPU中需要有一些寄存器用来存放表单在物理内存中的地址（假设这个位置的物理内存地址是0x10，那么在RISC-V上一个叫做SATP的寄存器会保存地址0x10）。这样，CPU就可以告诉MMU，可以从哪找到将虚拟内存地址翻译成物理内存地址的表单。

那么，地址隔离的基本想法是每个应用程序都有自己独立的表单，并且这个表单定义了应用程序的地址空间。当操作系统将CPU从一个应用程序切换到另一个应用程序时，同时也需要切换SATP寄存器中的内容，从而指向新的进程保存在物理内存中的地址对应表单。这样的话，cat程序和Shell程序中相同的虚拟内存地址，就可以翻译到不同的物理内存地址，因为每个应用程序都有属于自己的不同的地址对应表单。

还有一个细节，表单是如何映射虚拟地址到物理地址的？如果为每个虚拟地址建立一个条目，那么64位的cpu内存很快就会被耗光。实际情况是以页为单位，每一页对应一条表单条目，每一次地址翻译都是针对一页。所以对于虚拟内存地址，我们可以将它划分为两个部分，index和offset，index用来查找page，offset对应的是一个page中的哪个字节。

学生提问：我想知道4096字节作为一个page，这在物理内存中是连续的吗？

Frans教授：是的，在物理内存中，这是连续的4096个字节。所以物理内存是以4096为粒度使用的。

同一个学生：所以offset才是12bit，这样就足够覆盖4096个字节？

Frans教授：是的，page中的每个字节都可以被offset索引到。

物理页是连续的，单个页面内是一片连续的空间。

多级页表

首先就是要理解单级页表的实现。

所谓页表，就是一个连续的数组，这个数组的元素是PTE（Page Table Entries）。

在xv6的实现上，一个进程都有自己的一个页表，这个页表就是一个64位的指针，指向数组开头地址。单级页表使用27位bit作为索引，这意味着，页表的大小也必须是这么大。在进程初始化时，必须分配2^27 * PTE大小的一个连续空间，作为存放PTE的仓库。这个仓库一开始是空的，尽管能通过索引访问仓库中的第k个PTE，但这个PTE的有效标识位是false，此时分配一个物理地址，将物理地址的高44位分配给PPN，这个PTE就有效了。

再看多级页表，xv6上实现的是3级页表，每个页表的大小是2^9PTE大小。SATP寄存器会指向最高一级的page directory的物理内存地址，之后我们用虚拟内存中index的高9bit用来索引最高一级的page directory，这样我们就能得到一个PPN，也就是物理page号。这个PPN指向了中间级的page directory。当我们在使用中间级的page directory时，我们通过虚拟内存地址中的L1部分完成索引。接下来会走到最低级的page directory，我们通过虚拟内存地址中的L0部分完成索引。*在最低级的page directory中，我们可以得到对应于虚拟内存地址的物理内存地址。

多级页表的好处就在于能够按需分配小页表。如果进程使用很少的地址空间，譬如只需要一个页面，那么在多级页表下只需要分配3个页表，大小是$3512PTE$。而在单级页表下，尽管我们只需要一个页，但仍然需要分配2^ 27*PTE大小的一个页表。

多级页表的坏处就在于访问内存多次。

a potential downside of three levels is that the CPU must load three PTEs from memory to perform the translation of the virtual address in the load/store instruction to a physical address

PTE为什么存的是物理地址而不是虚拟地址？其实PTE存的是物理地址的高44位。

Frans教授：让我来问自己的一个有趣的问题，为什么是PPN存在这些page directory中？为什么不是一个虚拟内存地址？

某学生回答：因为我们需要在物理内存中查找下一个page directory的地址。

Frans教授：是的，我们不能让我们的地址翻译依赖于另一个翻译，否则我们可能会陷入递归的无限循环中。所以page directory必须存物理地址。那SATP呢？它存的是物理地址还是虚拟地址？

某学生回答：还是物理地址，因为最高级的page directory还是存在物理内存中，对吧。

Frans教授：是的，这里必须是物理地址，因为我们要用它来完成地址翻译，而不是对它进行地址翻译。所以SATP需要知道最高一级的page directory的物理地址是什么。

为什么中间页表能通过最高级页表的44位物理地址找到56位的物理地址？剩下的12位偏移量从哪来的？

学生提问：我想知道我们是怎么计算page table的物理地址，是不是这样，我们从最高级的page table得到44bit的PPN，然后再加上虚拟地址中的12bit offset，就得到了完整的56bit page table物理地址？

Frans教授：我们不会加上虚拟地址中的offset，这里只是使用了12bit的0。所以我们用44bit的PPN，再加上12bit的0，这样就得到了下一级page directory的56bit物理地址。这里要求每个page directory都与物理page对齐（也就是page directory的起始地址就是某个page的起始地址，所以低12bit都为0）。

我：这其实也是困惑我蛮久的一个问题。其实一个页表的地址就是一个数组的开头地址，偏移量就是0。44位高位加上12位0，就能得到真实页表物理地址了。

三次索引，有一次没成功怎么办？

学生提问：当一个进程请求一个虚拟内存地址时，CPU会查看SATP寄存器得到对应的最高一级page table，这级page table会使用虚拟内存地址中27bit index的最高9bit来完成索引，如果索引的结果为空，MMU会自动创建一个page table吗？

Frans教授：不会的，MMU会告诉操作系统或者处理器，抱歉我不能翻译这个地址，最终这会变成一个page fault。如果一个地址不能被翻译，那就不翻译。就像你在运算时除以0一样，处理器会拒绝那样做。

页表缓存

To avoid the cost of loading PTEs from physical memory, a RISC-V CPU caches page table entries in a Translation Look-aside Buffer (TLB).

对于一个虚拟内存地址的寻址，需要读三次内存，这里代价有点高。所以实际中，几乎所有的处理器都会对于最近使用过的虚拟地址的翻译结果有缓存。这个缓存被称为：Translation Lookside Buffer（通常翻译成页表缓存）。

当处理器第一次查找一个虚拟地址时，硬件通过3级page table得到最终的PPN，TLB会保存虚拟地址到物理地址的映射关系。这样下一次当你访问同一个虚拟地址时，处理器可以查看TLB，TLB会直接返回物理地址，而不需要通过page table得到结果。

我：这个缓存感觉有点鸡肋，只能查相同虚拟地址。原本以为可以实现相同页的缓存。

Frans教授：有很多种方法都可以实现TLB，对于你们来说最重要的是知道TLB是存在的。TLB实现的具体细节不是我们要深入讨论的内容。这是处理器中的一些逻辑，对于操作系统来说是不可见的，操作系统也不需要知道TLB是如何工作的。

你们需要知道TLB存在的唯一原因是，如果你切换了page table，操作系统需要告诉处理器当前正在切换page table，处理器会清空TLB。因为本质上来说，如果你切换了page table，TLB中的缓存将不再有用，它们需要被清空，否则地址翻译可能会出错。所以操作系统知道TLB是存在的，但只会时不时的告诉操作系统，现在的TLB不能用了，因为要切换page table了。

在RISC-V中，清空TLB的指令是sfence_vma。

地址转换是通过硬件进行的

To tell the hardware to use a page table, the kernel must write the physical address of the root page-table page into the satp register.

Instructions use only virtual addresses, which the paging hardware translates to physical addresses, and then sends to the DRAM hardware to read or write storage

学生提问：3级的page table是由操作系统实现的还是由硬件自己实现的？

Frans教授：这是由硬件实现的，所以3级 page table的查找都发生在硬件中。MMU是硬件的一部分而不是操作系统的一部分。在XV6中，有一个函数也实现了page table的查找，因为时不时的XV6也需要完成硬件的工作，所以XV6有这个叫做walk的函数，它在软件中实现了MMU硬件相同的功能。

学生提问：之前提到，硬件会完成3级 page table的查找，那为什么我们要在XV6中有一个walk函数来完成同样的工作？

Frans教授：非常好的问题。这里有几个原因，

首先XV6中的walk函数设置了最初的page table，它需要对3级page table进行编程所以它首先需要能模拟3级page table。

另一个原因或许你们已经在syscall实验中遇到了，就是内核与用户的交互。

在XV6中，内核有它自己的page table，用户进程也有自己的page table，用户进程指向sys_info结构体的指针存在于用户空间的page table，但是内核需要将这个指针翻译成一个自己可以读写的物理地址。如果你查看copy_in，copy_out，你可以发现内核会通过用户进程的page table，将用户的虚拟地址翻译得到物理地址，这样内核可以读写相应的物理内存地址。这就是为什么在XV6中需要有walk函数的一些原因。

学生提问：对于walk函数，我有一个比较困惑的地方，在写完SATP寄存器之后，内核还能直接访问物理地址吗？在代码里面看起来像是通过page table将虚拟地址翻译成了物理地址，但是这个时候SATP已经被设置了，得到的物理地址不会被认为是虚拟地址吗？

Frans教授：让我们来看kvminithart函数，这里的kernel_page_table是一个物理地址，并写入到SATP寄存器中。从那以后，我们的代码运行在一个我们构建出来的地址空间中。在之前的kvminit函数中，kvmmap会对每个地址或者每个page调用walk函数。

学生提问：我想知道，在SATP寄存器设置完之后，walk是不是还是按照相同的方式工作？

Frans：是的。它还能工作的原因是，内核设置了虚拟地址等于物理地址的映射关系，这里很重要，因为很多地方能工作的原因都是因为内核设置的地址映射关系是相同的。

一旦将page table的物理地址写入satp寄存器，以后代码中所有的地址都会被视为虚拟地址进行地址翻译。而内核还能正常工作的原因是它设置了恒等映射，虚拟地址与物理地址相同。

内核地址空间的映射

图中的右半部分的结构完全由硬件设计者决定。如你们上节课看到的一样，当操作系统启动时，会从地址0x80000000开始运行，这个地址其实也是由硬件设计者决定的。主板的设计人员决定了，在完成了虚拟到物理地址的翻译之后，如果得到的物理地址大于0x80000000会走向DRAM芯片，如果得到的物理地址低于0x80000000会走向不同的I/O设备。

回到最初那张图的右侧：物理地址的分布。可以看到最下面是未被使用的地址，这与主板文档内容是一致的（地址为0）。地址0x1000是boot ROM的物理地址，当你对主板上电，主板做的第一件事情就是运行存储在boot ROM中的代码，当boot完成之后，会跳转到地址0x80000000，操作系统需要确保那个地址有一些数据能够接着启动操作系统。

地址0x02000000对应CLINT，当你向这个地址执行读写指令，你是向实现了CLINT的芯片执行读写。这里你可以认为你直接在与设备交互，而不是读写物理内存。

学生提问：为什么物理地址最上面一大块标为未被使用？

Frans教授：物理地址总共有2^56那么多，但是你不用在主板上接入那么多的内存。所以不论主板上有多少DRAM芯片，总是会有一部分物理地址没有被用到。实际上在XV6中，我们限制了内存的大小是128MB。

接下来我会切换到第一张图的左边，这就是XV6的虚拟内存地址空间。当机器刚刚启动时，还没有可用的page，XV6操作系统会设置内核使用的虚拟地址空间，也就是这张图左边的地址分布。因为我们想让XV6尽可能的简单易懂，所以这里的虚拟地址到物理地址的映射，大部分是相等的关系。比如说内核会按照这种方式设置page table，虚拟地址0x02000000对应物理地址0x02000000。这意味着左侧低于PHYSTOP的虚拟地址，与右侧使用的物理地址是一样的。

除此之外，这里还有两件重要的事情：

第一件事情是内核栈的映射。

• kernel stack下有一个未映射的guard page，用来处理栈溢出
• kernel stack对应的物理地址被映射两次，一次是在高位的PHYSTOP下，另一次是在Kernel data中。就是说，有两个虚拟地址对应同一个物理地址。实际只用高位的虚拟地址，因为有guard page，更加安全。

这是众多你可以通过page table实现的有意思的事情之一。你可以向同一个物理地址映射两个虚拟地址，你可以不将一个虚拟地址映射到物理地址。可以是一对一的映射，一对多映射，多对一映射。

第二件事情是权限。例如Kernel text page被标位R-X，意味着你可以读它，也可以在这个地址段执行指令，但是你不能向Kernel text写数据。通过设置权限我们可以尽早的发现Bug从而避免Bug。对于Kernel data需要能被写入，所以它的标志位是RW-，但是你不能在这个地址段运行指令，所以它的X标志位未被设置。（注，所以，kernel text用来存代码，代码可以读，可以运行，但是不能篡改，kernel data用来存数据，数据可以读写，但是不能通过数据伪装代码在kernel中运行）

学生提问：对于不同的进程会有不同的kernel stack吗？

Frans：答案是的。每一个用户进程都有一个对应的kernel stack。

物理空间的分配

xv6 uses the physical memory between the end of the kernel and PHYSTOP for run-time allocation。

学生提问：用户程序的虚拟内存会映射到未使用的物理地址空间吗？

Frans教授：在kernel page table中，有一段Free Memory，它对应了物理内存中的一段地址。XV6使用这段free memory来存放用户进程的page table，text和data。如果我们运行了非常多的用户进程，某个时间点我们会耗尽这段内存，这个时候fork或者exec会返回错误。

同一个学生提问：这就意味着，用户进程的虚拟地址空间会比内核的虚拟地址空间小的多，是吗？

Frans教授：本质上来说，两边的虚拟地址空间大小是一样的。但是用户进程的虚拟地址空间使用率会更低。

我：这只是实际能使用的物理空间小而已。各个进程看到的虚拟地址空间大小是一样的。

物理空间的分配通过free list进行，每次从free list分配一个页面大小的内存给进程。

free list通过链表的形式追踪空闲页面。

Frans教授：当kernel创建了一个进程，针对这个进程的page table也会从Free memory中分配出来。内核会为用户进程的page table分配几个page，并填入PTE。在某个时间点，当内核运行了这个进程，内核会将进程的根page table的地址加载到SATP中。从那个时间点开始，处理器会使用内核为那个进程构建虚拟地址空间。