Project rCore: 地址空间

操作系统内存管理总结

Table of Contents

最近在写一个基于 rust 的操作系统 rCore,刚刚完成了地址空间 (address space) 的关键组件,这篇文章对其中的内容做一个总结。

综述

地址空间的实现需要软件加硬件相配合,硬件部分是 Memory Management Unit (MMU),它负责读取页表将虚拟地址转换为物理地址,软件部分是操作系统,它负责建立虚拟地址与物理地址之间的映射关系、维护页表等作用。

理论

页帧 (frame) 和页面 (page) 分别表示在物理内存和在虚拟内存中的若干个小块,可以理解内存是巨大的数组,将内存切分为大小相等的若干个小块,每个小块就是一个页帧,页帧的大小必须等于页面的大小,一般来说它的大小为 4 KB。

在应用的视角中只能看到虚拟内存,所以应用认为我在内存中是连续的,而实际情况是操作系统根据当前内存的情况将应用分散到放置到内存的不同区域中,这就导致了应用在实际的内存中是不连续的,就需要一个映射机制 <虚拟页号> -> <物理页号>,此时页表闪亮登场。

页表 (page table, pt) 由若干个页表项 (page table entry, pte) 组成的,每个 pte 的长度是 64 bits (8 bytes),页表项中承载的信息帮助将虚拟页号翻译为物理页号。

在进一步讲之前,先讲下 RISC-V 的 SV39 机制,虚拟内存共计 39 位,按照 4KB 的页面大小来算则页内偏移地址位 12 位(2^12 = 4KB),所以有 27 位的虚拟页号地址,物理地址共计 50 位,其中 38 位为物理页号,12 位为页内偏移。

要理解整个翻译过程,我们从最简单的一级页表开始讲起。已知虚拟页号长度小于物理页号长度,所以 pt 需要有 2^27 个 pte,这样虚拟页号就建立了与物理页号的一一映射关系,对于一个应用来说需要占用 8 * 2^27 = 1 GB 空间,这样很直观但是问题也很明显,一个应用用不了那么多的虚拟内存,实际内存只有 100 KB 的应用也需要有 1 GB 的 pt,这个完全是不可接受的,所以在实际设计中都是采用多级页表的方案。

多级页表可以类比字典树,总体思路就是“随用随加载”,我认为 rCore 教程中已经对该机制有非常详细且浅显的理解了,所以这里就不在赘述了,如果快表 (tlb) 不命中时,整个翻译过程如上图所示1,MMU 先从一级页表中找到二级页表的物理页号 (physical page num, ppn),然后从二级页表中找到三级页表的 ppn,最后从三级页表中找到该虚拟页号 (virtual page num, vpn) 实际的 ppn,该过程需要访存 4 次(3 次访问页表 + 1 次访问数据)。

转换关系

rCore 有四个与内存地址相关的数据结构,分别是 VirtPageNumVirtAddrPhysPageNumPhysAddr,从名字上就很自然的可以将他们分成两组:VirtXPhysX,分别表示虚拟地址和物理地址。为了方便我们都以物理地址为例,虚拟地址与其相似。

PhysPageNum 是指物理页号,PhysAddr 是指物理地址,他们之间的关系是 "PageAddr = PhysPageNum | 页内偏移",详见图 4.16。那么他们之间的转换关系是:

  • PhysPageNum -> PhysAddrr:直接将 PhysPageNum 左移 PAGE_SIZE_BIT 位。
  • PhysAddr -> PhysPageNum: 必须确保 PhysAddr 的页内偏移是 0,然后右移 PAGE_SIZE_BIT 位。

那么 VirtAddr 是如何转换为 PhysPageNum 的呢?

  • VirtAddr -> 调用 VirtAddr::into() 转换为 VirtPageNum -> 用 page_table 的 translate 方法获取 PageTableEntry -> 调用 PageTableEntry::ppn() 获取 PhysPageNum

软硬件结合

正如之前提到的一样,内存管理是需要软硬件相结合才能实现的,这里还是以 RISC-V 为例子,但是这里面隐含的道理是通用的。操作系统负责设置和切换寄存器数据、维护虚拟地址和物理地址的映射关系等工作,而硬件则负责机械的地址翻译、维护 tlb 等工作。

问题一:MMU 是纯硬件,每个应用都工作在自己的地址空间下,如何找到当前应用地址空间的一级页表的 ppn 呢?

关键就是一个名叫 satp 的寄存器,该寄存器根据不同位上的数据,控制地址空间的使能状态以及一级页表的 ppn。使能地址空间 MMU 就会启动,请求的地址都将视为虚拟地址而被翻译,反之则请求的地址都将视为物理地址。一级页表的 ppn 就很好理解了,一个地址空间对应一个一级页表,所以修改 satp 寄存器的 ppn 地址就相当于切换地址空间。

问题二:硬件不知道用户逻辑,应该如何才能正确维护映射关系呢?

代码详见:justxuewei/project-rCore

操作系统负责维护页表的逻辑,参见 src/mm/page_table.rs 文件,该文件中包含了 PagetTablePageTableEntry 分别表示页表和页表项,这里面有几个方法可以重点关注下:

  • mm::PageTable::find_pte_create(): 用于查找三级页表,创建二级/三级页表如果该页表不存在。
  • mm::PageTable::map(): 用于在三级页表中创建 ppn 与 vpn 的映射关系,保存在 pte 中。

操作系统负责维护程序中的逻辑段与页帧的映射关系,在 rCore 中是由 MapArea 实现的,该代码在 src/mm/memory_set.rs。所谓的逻辑段可以理解为程序的逻辑区域,比如 .text 表示代码区等等,一个逻辑段对应若干个页帧。一个应用全部的逻辑段就是该应用所占用的全部内存,在 rCore 中是由 MemorySet 实现的。

在目前的版本中并没有实现内存页帧的替换算法,主要是实现比较复杂,但是整体实现思路已经有了,需要在 pte 中标注页帧是否已经加载等信息,配合相关的算法实现。

Q&A

问题一:内核和应用地址空间是如何划分的?

整个内核使用同一个地址空间,内核地址空间包括 Low 和 High 两个部分,Trampoline, kernel stack 以及内核代码空间等等。每个应用都有一个自己的地址空间,所以在 trap 切换 mode 的时候必须更新 satp 寄存器以及刷新 TLB 等操作。

问题二:内核中是如何切换任务 (task) 的?

Kernel stack 中在内核 task 切换的时候会保存 TaskContext,在 trap 的时候保存的是 TrapContext。内核态任务切换不需要切换地址空间,所以就只需要保存几个基本的寄存器,比如 ra 、sp 和一些 callee 寄存器等,在 src/task/switch.S 文件中保存着切换逻辑,如下所示。

__switch 方法接受两个参数,当前正在运行的 task 的 TaskContext (cnt_task_cx) 和将要被切换的 task 的 TaskContext (next_task_cx),做的事情就是将当前 sp 和 ra 寄存器保存到 cnt_task_cx 中,这就意味在当 cnt_task_cx 作为将要被切换的 task 的时候可以继续在原来的位置运行。同时会将 next_task_cx 中保存的寄存器数据恢复,这样就切换到另一个数据流中了。在整个过程中不包含地址空间的切换。

  1. 图片中为了方便三级页表的位置为连续的,但是实际情况中页表的位置可能不连续。