【笔记】rCore (RISC-V)：虚拟内存

Why

为什么需要虚拟内存，等价于为什么物理内存的分配策略不够好。

• 地址冲突问题：应用直接访问物理内存，这需要它在构建的时候就清楚所运行计算机的物理内存空间布局，还需规划自己需要被加载到哪个地址运行。 应用与应用之间如果出现物理地址冲突，解决起来麻烦。
• 内存和代码不安全：内核并没有对应用的访存行为进行任何保护措施，即便在 U 级别下，每个应用还可以读写其他程序的物理内存。这意味着其他应用的 数据和代码会被窃取和修改，甚至执行恶意代码。
• 内存利用率低：只依赖物理内存管理的话，内核无法灵活地给程序提供运行时的动态内存空间，因为一个应用结束后，它所占据的内存空间被释放，但无法 动态地给别的应用使用。

所以，为了方便应用开发以及更安全地管理物理内存，需要对内存管理进行抽象，最终提供安全易用的访存接口：基于分页机制的虚拟内存。

• 从应用程序运行的角度看，存在一个从“0”地址开始的非常大的可读/可写/可执行的地址空间（Address Space）
• 从操作系统的角度看，每个应用被局限在分配给它的物理内存空间中运行，无法读写其它应用和操作系统所在的内存空间

为什么采用分页内存管理（等价于为什么其他内存管理策略不够好）：

• 一个程序完全放置到物理内存的插槽（大小相同的区域）：映射简单，无外部碎片，但容易导致内部碎片
• 程序的各个段散布到物理内存上：无内部碎片，但容易导致外部碎片，并且管理起来复杂
• 所以结合以上两种策略的分页优点：始终以一个相同的、足够小的单位来分割内存，避免了外部碎片，同时内部碎片也非常小

What

只有物理内存的世界：地址 ＝ 内存位置。

在虚拟内存的世界：地址 ≠ 内存位置。

静态分配：在编译时已知变量所占的字节大小，于是给它们分配一块固定的内存将它们存储其中，这样变量在栈帧/数据段中的位置就被固定下来。

动态分配：随应用的运行，利用堆 (heap) 动态增减内存空间

• 当堆的大小固定，则变成连续内存分配算法问题
  • 优点：简单易实现、可以快速地通过基址和偏移量来访问
  • 缺点：造成内存碎片（外部碎片和内部碎片）、内存利用率不高
• 非连续内存分配算法：如分页和分段

内存碎片：在内存中存在许多小的、不连续的、无法被利用的空间

• 外部碎片：空闲内存（不属于任何在运行的应用）中存在的空间（由于太小而无法分配给提出申请内存空间的应用）
• 内部碎片：已分配内存块（属于某个在运行的应用）中未被利用的空间（占有这些区域的应用并不使用这块区域，操作系统也无法利用这块区域）

应用并不能看到内存碎片，它们只需使用系统标准库提供的内存申请/释放函数接口，让操作系统去管理动态内存。对 C 语言来说：

• void* malloc (size_t size) 从堆中分配一块大小为 size 字节的空间，并返回一个指向它的指针
• void free (void* ptr) 将这个已经分配的指针传给 free，即可在堆中回收这块空间

硬件为支持地址空间提供的机制：为了限制应用访问内存空间的范围并给操作系统提供内存管理的灵活性，计算机硬件引入了各种内存保护/映射/地址转换硬件机制，如 RISC-V 的基址-边界翻译和保护机制、x86 的分段机制、RISC-V/x86/ARM 都有的分页机制。如果在地址转换过程中，无法找到物理地址或访问权限有误，则处理器产生非法访问内存的异常错误。

地址空间给应用带来的优点：

• 统一：应用能够直接看到并访问的内存就只有操作系统提供的地址空间，且它的任何一次访存使用的地址都是虚拟地址，无论取指令来执行还是读写栈、堆或是全局数据段都是如此
• 隔离：每个应用独占一个地址空间，里面只含有自己的各个段，于是它可以随意规划属于它自己的各个段的分布而无需考虑和其他应用冲突
• 安全：应用只能通过虚拟地址读写它自己的地址空间，它完全无法访问、窃取和破坏其他应用的数据

How

1. 分页机制：建立虚拟内存和物理内存的页映射关系（与硬件支持，硬件细节与具体 CPU 相关，涉及地址映射机制）
   • MMU（Memory Management Unit，内存管理单元）允许操作系统为不同的进程提供独立的虚拟地址空间，同时将这些虚拟地址映射到物理内存地址。
   • TLB（Translation Lookaside Buffer）是 MMU 的一个组成部分，通过缓存最近或常用的页表项（PTE）来减少频繁进行地址转换的开销，加速虚拟地址到物理地址的转换过程。
2. 每个应用都有一个表示地址映射关系的 页表 (Page Table) ，里面记录了该应用地址空间中的每个虚拟页面映射到物理内存中的哪个物理页帧， 即数据实际被内核放在哪里。我们可以用页号来代表二者，因此如果将页表看成一个键值对，其键的类型为虚拟页号，值的类型则为物理页号。当 MMU 进行地址转换的时候，虚拟地址会分为两部分（虚拟页号，页内偏移），MMU 首先找到虚拟地址所在虚拟页面的页号，然后查当前应用的页表，根据虚拟页号找到物理页号； 最后按照虚拟地址的页内偏移，给物理页号对应的物理页帧的起始地址加上一个偏移量，这就得到了实际访问的物理地址。

SV39 分页机制

花了好几天理解这部分知识，我发现最大的难点在于没有理解地址的映射关系是什么，它并不是数学上的一个抽象函数，而是一个具体的数据结构。

加上好多抽象的名词，但其实它们也都是具体事物的一个书面说法而已：

• SV39 适用于 64 位架构，所以虚拟和物理地址都是 64 位
• VA (virtual address, 虚拟地址)：开启分页之后，程序（包括 OS 和应用程序）看到的地址都是虚拟地址
  • 从地址格式上看，分成 [25, 27, 12] 三个部分，其中最低 12 位表示偏移量，27 位为 VPN，高 25 位所有位与第 38 位相同
• PA (physical address, 物理地址)：每个虚拟地址都不一定有物理地址；虚拟地址只有被 OS 映射（分配）到物理地址之后，它才有物理地址去读写数据
  • 虚拟地址被映射到物理地址之后，意味着一块虚拟地址区域不一定是连续存储在物理内存：即程序看到的连续区域可能在一个页面存储，也可能跨多个页存储
  • 从地址格式上看，分成 [8, 44, 12] 三个部分，其中最低 12 位表示偏移量，44 位为 PPN
• 物理页帧：SV39 要求物理地址空间被划分成 4KB 大小的连续区域，也就是说，每个区域的开头地址是 4KB 对齐的
  • 页帧按照需要才会被管理起来：OS 按需分配页帧，并对已经使用的页帧进行记录
  • 页帧是 SV39 内存分配的最小单位：OS 分配一块连续的内存最少应为 4KB
  • 也可以存在大页分配，大页的地址转换方式与这里描述的小页并不同，暂时不涉及它
  • 一个物理页帧可以存放一个页表，也可以存放实际的数据
• 页表 (Page Table)：
  • 每个页表存放在一个完整物理页帧内，它占据 4KB，被划分成 512 个 64 位的页表项
  • 一个页表其实就是一个连续的、外部 4KB 对齐、内部 8 字节对齐的物理内存区域 [PTE; 512]，索引号为 VPN（的一部分），元素 PTE 为 PPN 和一些位信息
  • SV39 是 3 级页表结构，意味着通常使用 3 个页表来存储一个虚拟地址空间与物理内存的映射
  • 第 1 级页表被称为根页表，satp CSR 所存根页表所在的物理页号
• 页表项 (PTE, Page Table Entry)：
  • 长度为 64 位，主要包含一些控制位和一个 PPN
  • 页表项具有两种类型：非叶节点（页目录表，非末级页表）和叶节点（页表，末级页表）
  • 页目录表的用途为“指针”，它包含的 PPN 指向下一级页表的开头的物理地址；它的控制位状态必须是：V=1 且 R/W/X 均为 0
  • 末级页表也充当“指针”，它包含的 PPN 指向实际存放数据的物理页帧的开头地址；它的控制位状态必须是 V=1 且 R/W/X 不全为 0
• VPN (virtual page number, 虚拟页号)：
  • 即一个 VA 的中间 27 位，它被划分为 [9, 9, 9] 三个部分，每个 9 位代表的数字作为一个页表上的索引（刚好 512 个索引号）
  • 查表/地址映射：对于 3 级页表来说，最高的 9 位提供根页表的索引号，然后得知第 2 级页表的物理页帧；中间的 9 位用于在第 2 级页表索引到第 3 级页表的页帧； 最低 9 位用在第 3 级页表中，索引到存放数据的页帧；最后 VA 的最低 12 位在这个数据页帧上进行偏移，得到 VA 所指向的 PA。
• PPN (physical page number, 物理页号)：
  • 即一个 PA 的中间 44 位，同时也是一个页表项中的 44 位，表示一个物理页帧，指向这个页帧的开头地址
  • 恒等映射：虚拟地址与物理地址重合，即 VPN 与 PPN 相同，这主要发生在 OS 内
  • 非恒等映射：应用程序的 VPN 和 PPN 并不相同
• satp CSR：
  • MODE 为 8 时，表示启用 SV39 分页机制
  • ASID 表示地址空间标识符（与进程有关）
  • PPN 存的是根页表所在的物理页号