Lab3.内存管理
最后更新于
最后更新于
在进行本实验之前，你需要进行分支管理，请在工程目录下输入以下命令：
对于内存管理，我想大家对相关概念也比较熟悉，从逻辑地址到物理地址之间的地址变换，到动态内存的分配与回收，再到虚拟内存中的分段式、分页式内存管理，大家在操作系统理论课中也学习过。在本次实验中，我们会主要聚焦于虚拟内存，具体来说，我们会聚焦于xv6中页表相关的内容。
相信在理论课的学习中你们对页表有了足够的了解，接下来我们会根据xv6的页表来详细探讨。xv6是基于SV39页表运行的，这种页表只使用64位虚拟地址的低39位。那么高25位有什么作用？高25位保留下来可以供未来RISC-V定义更多级别的转换，这也是RISC-V的灵活之处。此外，SV39 分页模式规定 64 位虚拟地址的 [63:39]这 25 位必须和第 38 位相同，否则 MMU 会直接认定它是一个 不合法的虚拟地址。
我们先来看看SV39页表进行虚拟地址和物理地址转换的过程。
如图所示，页表在逻辑上是由一个由2的27次方个PTE(Page Table Entries)组成的数组。每个PTE包含一个44位的PPN和一些标志位。在转换过程中，虚拟地址39位中的前27位索引页表，找到一个PTE，然后生成一个56位的物理地址，其中前44位来自PTE的PPN，后12位来自虚拟地址的偏移（Offset），这个偏移量必须是12位，因为在RISC-V中一个页是4KB，也就是4096字节。
事实上，实际的页表被设计为三级页表。
之前所说的27位的索引，实际上分为了三个等长的索引，分别是的L2、L1、L0，这三个等长的索引各9位，所以每一级页表有2的9次方，即512个PTE。分页硬件使用27位中的前9位（L2）在根页表页面中选择PTE，中间9位（L1）在下一级页表页面中选择PTE，最后9位（L0）选择最终的PTE。此外，最高一级页表的PPN用于指向中间级页表，中间级页表的PPN用于指向最后一级页表，而最后一级页表的PPN就是物理地址中的PPN。下面是三级页表和PTE的具体内容的图示：
我们可以看到PTE中有10位被设置为标志位。
PTE_V：指示PTE是否存在。
PTE_R：控制是否允许指令读取到页面。
PTE_W：控制是否允许指令写入到页面。
PTE_X：控制CPU是否可以将页面内容解释为指令并执行它们。
PTE_U：控制用户模式下的指令是否被允许访问页面。
在kernel/riscv.h中我们可以看到上述相关结构的定义。
每个进程都会有一个属于自己的单独页表，进行进程切换时，也会切换页表。在xv6中，一个进程的用户内存从虚拟地址0开始，到MAXVA。当进程向xv6请求更多的用户内存时，xv6会使用kernel/kalloc.c中的kalloc来分配物理页面，然后将PTE加到进程页表中。下面是进程地址空间的布局图：
其中除了我们熟悉的data，text，stack，heap段外，还有其他一些段，guard page的作用是针对用户栈检测是否溢出，trampoline和trapframe的作用在此先不讨论。
在xv6中，只有一个内核空间的页表，描述了内核虚拟地址访问物理内存和各种硬件资源。kernel/memlayout.h声明了xv6内核内存布局的常量，阅读代码会发现相关信息和下图中的描述一模一样。
事实上，上图右半部分的硬件资源结构完全由硬件设计者决定，正如你们之前的操作中发现，操作系统从从地址0x80000000开始运行，这个地址其实也是由硬件设计者决定的。在这里，我们是使用了QEMU来模拟了这样一台计算机。从物理地址0x80000000开始并至少到0x86400000结束的RAM（物理内存），xv6称结束地址为PHYSTOP。QEMU模拟还包括I/O设备，如磁盘接口。QEMU将设备接口作为内存映射控制寄存器暴露给软件，这些寄存器位于物理地址空间0x80000000以下。内核可以通过读取/写入这些特殊的物理地址与设备交互，这种读取和写入与设备硬件而不是RAM通信。
内核使用直接映射的方式获取内存和内存映射设备寄存器。也就是说，将资源映射到等于物理地址的虚拟地址。例如，内核本身在虚拟地址空间和物理内存中都位于KERNBASE=0x80000000。直接映射简化了读取或写入物理内存的内核代码。
当然，如图所示，也有部分的内核虚拟地址不是通过直接映射，这里暂时不展开讨论。
回到xv6的代码中，操作系统如何创建一个地址空间？
“源码面前，了无秘密”，接下来需要你仔细阅读代码，搞清楚xv6的内存管理机制。
💡 注意！
在开始下面的练习之前，请保证你已经浏览了下面的文件并对其中的代码有了基本的认识：
kernel/memlayout.h：它捕获了内存的布局。
kernel/vm.c：包含大多数虚拟内存相关的代码。
kernel/kalloc.c：包含分配和释放物理内存的代码。
🖊️ 打印页表
你需要实现一个简单的工具，帮你了解三级页表的构造，以及有助于你后续进行页表相关的调试。
在
kernel/vm.c中实现vmprint()，它应当接收一个pagetable_t作为参数，其中kernel/riscv.h末尾处相关的宏定义会对你有帮助。如果你不知道怎么实现该函数，可以参考freewalk()。打印页表格式如下：
第一行显示字符“page table”和整个页表的内存始址。之后的每行对应一个PTE，包含树中指向页表页的PTE。每个PTE行都有一些“..”的缩进表明它在树中的深度。每个PTE行显示其在页表页中的PTE索引、PTE比特位以及从PTE提取的物理地址。不要打印无效的PTE。在上面的示例中，顶级页表页具有条目0和255的映射。条目0的下一级只映射了索引0，该索引0的下一级映射了条目0、1和2。
具体来说，第二行，“..”表示 L2 级页目录，后面的 0 表示一个有效页表项在 L2 级页目录中的索引号；“pte ” 后面的
0x0000000021fda801表 示 的 是 该 PTE 的bits值 ； 而“pa”后面的0x0000000087f6a000，表示的是该页表项所对应的物理地址。第三行，“.. ..”表示的是 L1 级页目录，其他的和上面的表述相同。
你的代码可能会发出与上面显示的不同的物理地址。条目数和虚拟地址应相同。
在
exec.c中的return argc之前插入if(p->pid==1) vmprint(p->pagetable)，可以打印第一个进程的页表，启动xv6时可以验证你的结果是否正确。使用
python3 grade-lab-3 pte可以测试你的程序。
完成了打印页表，相信你对xv6的三级页表机制有了一定的了解，接下来我们需要使用vmprint()作为工具，探索xv6中创建内核地址空间的细节，看看内核虚拟地址是如何直接映射到物理内存的。
🖊️ 调试
kvminit()，验证映射关系使用gdb在
kvminit()处设置一个断点，选择其中一个kvmmap函数映射的I/O设备，在其后面用vmprint打印它的页表，完成之后，根据三级页表的构造，通过物理地址验证打印页表中的PTE序号，这一步可以利用gdb的打印功能完成。
现在新的问题产生了，我们在上面讨论了页表，而我们知道，如果我们需要的页不在物理内存中，就会发生缺页异常（page fault）。正常来说，操作系统对于不同的异常会有异常处理程序，而xv6是一个极其简单的操作系统，遭遇异常时，它的处理方式也非常简单：如果用户空间中发生异常，内核将终止故障进程。如果内核中发生异常，则内核会崩溃。
在现代计算机中，遭遇缺页异常可以使用lazy allocation，copy-on-write fork，demand paging，memory mapped files等方式来处理。接下来我们会讨论并在xv6中实现lazy allocation，这是一种较为简单的处理方式。
在讨论lazy allocation之前，思考一下，我们要处理缺页异常，什么信息是重要的？显然，我们需要知道出错的虚拟地址，缺页异常的类型，以及触发缺页异常的指令的地址。
首先看看一个重要的系统调用：sbrk。sbrk是xv6提供的系统调用，它使得用户应用程序能扩大自己的heap。当一个应用程序启动的时候，sbrk指向的是heap的最底端，同时也是stack的最顶端。
在xv6中sbrk的主要功能是由kernel/proc.c中的函数growproc实现的，growproc根据n是正的还是负的调用uvmalloc或uvmdealloc。uvmalloc用kalloc分配物理内存，并用mappages将PTE添加到用户页表中。uvmdealloc调用uvmunmap，uvmunmap使用walk来查找对应的PTE，并使用kfree来释放PTE引用的物理内存。具体的细节可以阅读源码进行思考。
所以，当sbrk实际发生或者被调用的时候，内核会分配一些物理内存，并将这些内存映射到用户应用程序的地址空间，然后将内存内容初始化为0，再返回sbrk系统调用。这样，应用程序可以通过多次sbrk系统调用来增加它所需要的内存。类似的，应用程序还可以通过给sbrk传入负数作为参数，来减少或者压缩它的地址空间。
但是，目前的xv6中一旦调用了sbrk，内核会立即分配应用程序所需要的物理内存。实际上，对于应用程序来说很难预测自己需要多少内存，所以通常来说，应用程序倾向于申请多于自己所需要的内存。这意味着，进程的内存消耗会增加许多，但是有部分内存永远也不会被应用程序所使用到。
而lazy allocation要解决的问题，就是在调用sbrk时，仅仅是记录增长，但不分配物理内存，当之后应用程序使用到了新申请的那部分内存，因为我们还没有分配內存，所以会触发缺页异常，于是这时候我们就可以分配內存，使得程序重新执行下去。
🖊️ 取消
sbrk的内存分配修改
kernel/sysproc.c中的函数sys_sbrk()，使得系统调用sbrk只增加进程內存的大小，但不分配內存。修改完成后，在xv6中输入：
echo hi，你会发现出现了缺页异常。
注意观察此时缺页异常的打印结果，输出了scause寄存器内容，我们可以看到它的值是15，查阅RISC-V手册可以发现这是一个Store page fault。事实上，在RISC-V中，缺页异常只有Load page fault和Store page fault两种，分别对应的scause寄存器的值为13和15。
那么要如何解决这个缺页异常？观察缺页异常的打印，可以看到首先出现异常的是usertrap()，没有正确处理scause寄存器值为15的问题，于是我们定位到函数usertrap()，可以看到，这里有scause寄存器值为8时针对系统调用的处理，所以我们需要在此添加缺页异常的处理：
首先我们会打印一些调试信息，在哪个虚拟地址发生了缺页异常。然后如果没有物理内存可以分配了，我们会杀死进程；如果有物理内存，首先会将内存内容设置为0，之后将物理页指向用户地址空间中合适的虚拟内存地址。具体来说，我们首先将虚拟地址向下取整，再将物理内存地址跟取整之后的虚拟内存地址的关系加到页表中，对应的PTE需要设置常用的权限标志位。
再次在xv6中运行echo hi，你会发现并没有正常工作。这里出现了两个缺页异常，且与上一步一样的是，uvmunmap在报错。
🖊️ 解决这个panic
定位到代码中的这个panic，思考一下这里没有映射的內存是什么內存。事实上，这个panic的意思是我们删除了并不存在映射关系的页面，想想lazy allocation的机制，想办法解决掉这个panic。
解决掉这个panic之后，两个缺页异常仍然存在，但是
echo hi已经可以正常工作了。
到这里，已经实现了一个简单版本的lazy allocation，然而，这里并没有检查触发缺页错误的虚拟地址小于sbrk()分配的内存大小时的情况，也没有考虑如果sbrk()申请的內存是负数的情况。想想看，申请的內存是负数意味着什么？
🖊️ 完善lazy allocation
首先基于上述的工作，处理
sbrk()申请的內存是负数的情况，以及如果某个进程在高于sbrk()分配的任何虚拟内存地址上出现缺页异常，则中止该进程，同时用户栈下面的无效页面上发生的异常也是中止进程，注意阅读kernel/proc.h文件，对这一步很有帮助。处理所有因为页不存在而发生的panic，解决方法和上面的panic是一样的。注意，在
fork()中父到子内存拷贝中也涉及该问题。处理这种情形：进程从
sbrk()向系统调用（如read或write）传递有效地址，但尚未分配该地址的内存。阅读内核中read和write的代码，观察其使用了什么函数进行用户态和内核态页表的拷贝，在相应的函数中添加对缺页异常进行处理的机制。使用
python3 grade-lab-3 lazytests和python3 grade-lab-3 usertests分别进行测试，如果两个测试都通过了，证明你的解决方案是正确的。
🗨️ 扩展阅读：Copy On Write Fork
事实上，常见操作系统都会使用COW Fork这个机制。
COW Fork中方法是让父子最初共享所有物理页面，但将它们映射为只读。因此，当子级或父级执行存储指令时，CPU引发缺页异常。为了响应此异常，内核复制了包含异常地址的页面。它在子级的地址空间中映射一个权限为读/写的副本，在父级的地址空间中映射另一个权限为读/写的副本。更新页表后，内核会在导致故障的指令处恢复故障进程的执行。由于内核已经更新了相关的PTE以允许写入，所以错误指令现在将正确执行。
当释放页面时，我们需要对于每一个物理内存页面的引用进行计数，当我们释放虚拟页面时，我们将物理内存页面的引用数减1，如果引用数等于0，那么我们就能释放该页面。
有兴趣的同学，可以在xv6中实现COW Fork的功能，这是一个很有挑战性且很有趣的任务。
