- Page Table
Page Table
——实现 VM到PM的映射，提供 强隔离性
课前准备
OS 通过页表实现 VM到PM的映射，使得不同进程使用独立的地址空间，提供隔离性，以及一些特殊的功能：
- 不同进程共享内存：映射到同一PM
- mapping the same memory (a trampoline page) in several address spaces？
- 保护栈：unmapped page
Paging hardware
The flags and all other page hardware-related structures are defined in (kernel/riscv.h)
- risc-v 指令操作的都是 va，而非pa
- DRAM 通过 pa 索引
- PT 提供 va 到 pa 的映射
Sv39 RISC-V
（Supervisor Virtual）
va：高 25bit 保留，va = EXT+Index+Offset = 25+27+12 = ~+VPN+VPO
- 共 $2^{27}$ 个 PTE，PTE = PPN+flags = 44+10
- 页粒度：$2^{12}$ B = 4KB
pa：低10bit保留，pa= PPN+VPO+EXT = 44+12+10
translation 与 三级页表
risc-v 使用三级页表索引一个最终的PTE，每一级页表有 $2^{9}$ = 512 个 PTE，占用空间一页（$2^{9+3}$ B）
- PTE 均索引物理页号
任何页缺失，包括页表缺失，都会引发 page-fault exception，由 kernel 处理异常
- 大部分VM并没有被映射，这是很常见的情况
保留所有PT需要大量的内存，三级页表使得只需保留很少一部分PT在内存中，忽略没有被映射的页表
flags
- V：指向的页是否合法/被分配，索引未被分配的页会引发异常
- RWX：页是否可读写，及从此加载指令
- U：是否允许用户模式下的程序访问改页
satp 寄存器
存储根页表的物理地址，每个CPU都有自己的satp，可以更加方便快速地运行不同进程
Kernel address space
xv6 为每个进程维护一个页表，用于描述每个进程的用户地址空间，以及一个描述内核地址空间的单独页表：
- (kernel/memlayout.h) 声明了 xv6 内核内存布局的常量。
QEMU 计算机
QEMU 模拟了一个计算机
物理内存： 0x80000000 到至少 0x86400000
- xv6 将0x86400000称为 PHYSTOP
QEMU 模拟还包括 I/O 设备，将其接口暴露给软件，通过读写 0x80000000 以下的物理内存与其交互
- 接口例如例如磁盘接口
- 注意，与此地址交互时，是在与该硬件设备交互，而非RAM
direct mapping：va=pa，简化读写物理内存和设备的代码
非直接映射页：
- trampoline page：映射在VM的顶部。用户页表也有这种页。
- 一个物理页被映射两次：一次VM顶部，一次直接映射
- kernel stack pages & guard page：映射在顶部，以在其下方有一个 valid bit 未设置的 guard page 以防止栈溢出
- trampoline page：映射在VM的顶部。用户页表也有这种页。
- 权限 RX：trampoline and the kernel text
- RW：其他
- 无效：guard
Code: creating an address space
The translations include the kernel’s instructions and data, physical memory up to PHYSTOP, and memory ranges which are actually devices.
大部分用于操作地址空间和页表的 xv6 代码位于 vm.c 文件中（kernel/vm.c:1）
risc-v 启动时，main 调用 kvminit 创建内核页表，此过程发生在启用分页前，其地址直接映射到物理地址
main 调用 kvminithart 将根页表放入 satp 寄存器并启用分页。自此有了分页功能，但现有的vm直接映射到pm
main 调用 procinit 将所有进程的内核栈指针指向 KSTACK 生成的虚拟地址，从而为 guard page 预留空间
pagetable_t
指向根页表的指针
walk：MMU
模拟 MMU 查找 va 对应的最终的 PTE 的地址：
每9位下降到下一级页表直到最终的PTE，如果中间页表的 PTE 无效 且 alloc 参数被设置，则分配一个物理页，直到最低层
- MMU 在 TLB 中缓存 PTE。修改某个PTE时，CPU必须通知 TLB 某个 PTE 为 dirty 失效。
- 通过 sfence_vma 刷新当前CPU的 TLB
mappages
按页大小对齐为范围内的每对 va & pa 创建 PTE
调用 walk 找到 PTE，然后初始化 PTE 存储 PPN、权限位、以及 PTE_V
kvm & uvm
分别操作内核和用户页表，其余函数两者都用
- kvminit：先分配物理页保存根页表，然后调用 kvmmap 创建 PTE。
- kvmmap：只在启动时使用，调用mappages 创建 PTE
- kvminithart：将根页表放入 satp 寄存器并启用分页。现有的vm直接映射到pm
- 在 kvminithart 加载satp后 刷新
- 在返回用户空间前、切换用户页表时刷新 kernel/trampoline.S
copyout & copyin
在用户虚拟地址和内核之间复制数据
PM 分配
对象：页表、用户内存、内核栈和管道缓冲区
范围：内核末尾 and PHYSTOP
大小：一页，即 4KB
使用链表跟踪空闲页，分配即从该链表中移除空闲页，释放即插入到该链表中
Code: Physical memory allocator
kernel/kalloc.c:1
分配器
分配器使用自旋锁保护：
列表元素：
main 调用 kinit 来初始化 freelist，以容纳从内核末尾到 PHYSTOP 之间的每个 page
kinit 调用 freerange 通过释放，将这些page 添加到 freelist 中
freerange 使用 PGROUNDUP 确保只释放对其的物理内存
- PTE 只能引用 4KB 对齐的物理内存
freerange 调用 kfree 释放单个页：
- 将被释放页的每个字节设为1，也即是 垃圾值，希望这样能使代码崩溃
- 然后将 pa* 转化为 run*，插入到 freelist 中
使用 kalloc 分配内存时，即删除 freelist 所指向的第一个页
DRAM 数量
本应通过解析硬件提供的配置信息来确定可用的物理内存数量，但 xv6 假设机器有 128MB 的RAM
指针双重用途
分配器有时将地址视为整数，以便对其执行算术运算，如遍历
指针
所以充满着C类型转换
Process address space
每个进程都有独立的页表，在切换进程时也会切换页表
范围
进程的 VM 范围为：0~MAXVA，原则上允许一个进程寻址 256GB 的内存
- kernel/riscv.h:348
分配进程内存
进程请求分配用户内存是，xv6 使用kalloc分配物理页，然后创建 PTE、设置包含PTE_V的权限位
进程 VM 特点
- 隔离性：用户间的页表独立，可以映射到不同的物理内存
- 进程视角的内存 VM 是连续的，而它实际的 PM 可以不连续
- 顶部有一个页存放 trampoline code，thus a single page of physical memory shows up in all address spaces.？？？
initial stack 与 guard page
见上图。下方有一个 guard page 防止栈溢出，访问此页时会引发异常 page-fault exception。
- 真实的操作系统可能会有别的操作，比如访问 guard page 时为进程分配更多内存
Code: sbrk
growproc、uvmdealloc、uvmalloc：kernel/proc.c
Sbrk 是一个系统调用，用于进程缩小或扩展其内存，通过调用 growproc 实现
growproc 根据传入的 n 的正负调用 uvmalloc 或 uvmdealloc
- uvmalloc 调用 kalloc 分配物理内存，并调用 mappages 创建 PTE
- uvmdealloc 调用 uvmunmap，后者使用 walk 查找 PTE 从而找到 pa，然后调用 kfree 释放内存
——页表是唯一记录进程已分配 PM 的方式
Code: exec
kernel/exec.c
ELF：kernel/elf.h
根据文件系统上的某个文件初始化用户部分的地址空间：
打开文件，读取并根据 magic 检查ELF头，确定well-formed 后，创建新页表、分配物理内存、加载每个段到内存中。然后复制exec参数到栈顶，释放旧映像并返回
调用 namei 打开文件，然后通过 readi 读取文件的 ELF 头 elfhdr，以及 程序段头 proghdr
- ELF 头描述了程序的一些基本信息，而程序段头描述了必须加载到内存中的程序段
- xv6 程序只有一个程序段头，但其他系统可能会为指令和数据设置单独的段。
exec 会检查 ELF 开头的 magic number，若具有则假定文件具有完整的二进制格式 well-formed
- magic number：0x7F, ‘E’, ‘L’, ‘F’, or ELF_MAGIC
使用 proc.c 中的 proc_pagetable 为进程创建全新的页表，并使用 uvmalloc 为每个ELF段分配物理内存，然后使用 loadseg 将每个段加载到内存中
- loadseg 使用 walkaddr 检索到va对应的pa
此时以及分配好了栈页，但只为栈分配了一页。exec 将字符串逐个复制到栈顶，并在 ustack 中记录他们的指针，并在其末尾放置一个空指针。最终 ustack 的前三个条目是 fake PC、argc、argv
exec 在堆栈下放了一个 guard page，禁止栈溢出，使用多于其本身大小（1 page）的内存。
- 这还允许 exec 处理数量过多的参数，copyout 会返回-1
准备文件的新内存映像 memory image 时，如果遇到无效程序段，会释放新映像并返回-1。
- 这意味着 exec 必须等新映像成功创建后才可以释放旧映像
- 创建成功后即可切换到新页表并释放旧映像
安全问题：exec 将ELF文件中的字节复制到指定的 va 中，这是有风险的：如果指向内核会造成崩溃
- xv6 执行了许多检查以避免这些风险，例如，
if(ph.vaddr + ph.memsz < ph.vaddr)检查总和是否溢出 64 位整数 - 旧的 xv6 用户地址空间包含内核但不可读写，程序可利用这个漏洞攻击内核。RISC-V 版本下内核有单独的页表，loadseg 只会把数据加载到进程的页表中，而非内核的页表中
- xv6 执行了许多检查以避免这些风险，例如，
/init program section header
filesz 可能小于 memsz，其间隙应该用0填充，而非从文件读取数据
- memsz：段被分配的实际PM大小
- filesz：该文件的实际大小
Real World
与大多数操作系统一样，xv6 使用分页硬件来实现内存保护和映射。大多数操作系统通过结合分页和 page-fault exceptions 来实现更复杂的分页功能，而 xv6 相对简化了这些操作。
xv6 使用 va-pa 的 直接映射 简化内存操作，并假设在 0x8000000 处存在RAM，期望内核在此处被加载
- 实际硬件应将RAM和设备放在不可预测的物理地址处
- 成熟的内核设计利用页表将任意物理内存布局转化为可预测的内核虚拟地址布局
- RISC-V 支持PM级保护，而xv6没有这一特性
大 page 与 小 page
在内存较大的机器上，使用 RISC-V 的 super pages 完全ok
而小页允许以更精细的粒度分配物理内存、写入磁盘
内存分配
xv6 内核缺乏类似 malloc 的可以为小对象分配内存的分配器，也就无需为动态分配内存准备复杂的数据结构
内存分配一直是热门话题，其基本问题是如何有效利用有限的内存，并为未知的未来请求做好准备。如今，人们更关心速度而非空间效率。此外，一个更复杂的内核可能会分配许多不同大小的小块内存，而不仅仅是像 xv6 那样只分配 4096 字节的块；现实中的内核分配器需要同时处理小规模和大规模的分配。
地址空间：VM
一种隔离性实现方式：地址空间
隔离性
期望每个用户程序不会相互影响、也不会影响 OS
地址空间
给包括内核在内的所有程序专属独立的地址空间，也就不能引用任何不属于自己的内存
- 这样，程序若想向地址1000写入数据就只会写入自己地址空间的1000，而不会影响其他进程
所以现在我们的问题是 如何在一个物理内存上，创建不同的地址空间，最常见的方法就是 页表
页表
页表通过 处理器 + MMU 实现，处理器将 va 发送给 MMU，MMU 将 va 翻译为 pa 后索引 PM，然后向物理内存读写数据
- 内存管理单元（Memory Management Unit）
- CPU 使用的全部都是虚拟地址
为了将 va 翻译为 pa，需要有一个表单存储映射关系，即 页表
PT 通常来说也存储在内存中，也因此CPU中需要有寄存器 satp 存储页表的 pa，从而可以告诉 MMU 从哪里找 PT
- MMU不会保存PT，不会创建PT，无法翻译地址时告诉CPU发生错误
- 切换进程时需要切换PT，此时需要修改 satp 的值
工作机制
如果为64位机器的每一个地址都存储一个 PTE，那么需要耗费海量的空间存储 PT，实际情况中，RISC-V为每个 page 存储一个 PTE，粒度为 4KB，$2^{12}$ B
- 4KB大小的page，也就是说需要12个比特索引
- 页内部连续
我们将va分为两部分：index & offset，使用index查找page，offset 索引具体的字节
index 标识了物理内存的页号，MMU 通过 VPN 读取 PT 中的 PPN，也就是物理页号，PPN + VPO 共同组成了具体地址的指针
地址大小
va 的高25位没有使用，限制了VM的大小，那么现在一个进程的 VM 只有 $2^{39}$ B = 512 GB
- 新的处理器或许可以支持更大的地址空间，只需要将未使用的25bit拿出来做为虚拟内存地址的一部分即可
va = index + offset = 39 = 27 + 12，pa = PPN + VPO = 56 = 44 + 12
- 大多数主板还不支持2^56这么大的物理内存，但是原则上，如果你能造出这样的主板，那么最多可以支持2^56字节的物理内存
- PPO = VPO，所以此处直接用了VPO
- 56位的物理内存是设计人员决定的，他们预测物理内存在5年内不可能超过2^56这么大。主板上这时候只需要56根线
这样的大小设计允许有多个进程用光了虚拟内存，而物理内存完全还有冗余可以分配
index有27位，也就是说每个PT最多有2^27个条目，但这同样会消耗大量的内存，实际中使用多级页表减小 PT 的大小
xv6：三级页表
index = L2+L1+L0 = 9+9+9，最高9位的L2用于索引最高级的页表 page directory，每个PT的PPN要么指向下级页表的页号，要么指向最终数据的页号
- page table，page directory， page directory table 可以都当作 PT
- 最高级页表的页号后面跟9+9+12个0就是L1页表的物理地址，其余同理
- 三级页表查找由硬件实现。在XV6软件中，函数walk也实现了相同的功能
一个directory同样用一页存储，大小为4KB。一个PTE 8B = 2^3 B，共512=2^9个PTE
SATP 实际存储根页表的物理地址
多级页表的优点
所以这种3步得到物理地址的方式的优点是什么？
大多数进程只需要一个三级页表，即三个PT，约12KB的内存，索引 $2^{9+12}$ B = 2MB 的物理内存，而大部分内存是尚未被分配的，我们完全不需要为这些va分配PTE并存储到PT中
为什么要 walk 二次实现 MMU 的功能？
首先XV6中的walk函数设置了最初的page table，它需要对3级page table进行编程所以它首先需要能模拟3级page table。
- ？？？
其次，内核和进程都有自己的页表，无法访问对方的物理内存，此时内核需要访问对方的页表以获得一个自己可以读写的用户数据所在的物理内存…所以需要 walk 实现 MMU 的功能
为什么硬件不开发类似于walk函数的接口？
后面会说
flag
前面有，最重要的几个标志位是：VRWXU
为什么不把PPN放在一个va中？
我们要查物理地址就需要通过PPN，而若把PPN放在va中，则我们可能需要查这个va的PPN，进而陷入无限的递归——这样做完全没有必要，反而浪费了时间
SATP也是同理，我们需要存放物理地址
页表：虚拟化机制
page table提供了一层 level of indirecton，映射关系由OS完全掌控，可以实现各种各样的功能
- 例如：当出现page fault的时候，操作系统可以做哪些有意思的事情
改变用户所看见的视图，提供了非常大的灵活性
TLB：页表缓存
每次与内存交互都要查三次页表，这看起来代价很高，实际中可以通过缓存解决这个问题，也即我们所说的页表项PTE的缓存 Translation Lookside Buffer TLB
缓存工作原理
CPU传递va给MMU 时，MMU 首先查看TLB看看有没有缓存这个PTE。命中则与内存交互得到数据返回给CPU；否则与内存交互查询PT得到PTE，并与内存交互得到数据返回给CPU
为什么此处的缓存级别为PTE而非page？
有很多种方法都可以实现TLB，对于你们来说最重要的是知道TLB是存在的。TLB实现的具体细节不是我们要深入讨论的内容。这是处理器中的一些逻辑，对于操作系统来说是不可见的，操作系统也不需要知道TLB是如何工作的。
切换进程：清空TLB
你们需要知道TLB存在的唯一原因是，如果你切换了page table，操作系统需要告诉处理器当前正在切换page table，处理器会清空TLB。为本质上来说，如果你切换了page table，TLB中的缓存将不再有用，它们需要被清空，否则地址翻译可能会出错。
清空指令：sfence_vma
什么时候缓存？
整个CPU和MMU都在处理器芯片中，所以在一个RISC-V芯片中有多个CPU核，MMU和TLB存在于每一个CPU核里面。
RISC-V处理器有L1 cache，L2 Cache，有些cache是根据物理地址索引的，有些cache是根据虚拟地址索引的，由虚拟地址索引的cache位于MMU之前，由物理地址索引的cache位于MMU之后。
Kernel 页表
kernel 地址空间：
物理地址空间
右半部分的结构完全由硬件设计者决定，他们决定如果物理地址大于 0x80000000 会走向DRAM芯片，如果得到的物理地址低于0x80000000会走向不同的I/O设备
- 至于是哪个IO设备可以查看主板的手册
例如，地址0是保留的，地址0x10090000对应以太网，地址0x80000000对应DRAM。
以下内容基于QEMU模拟的计算机
unmapped 物理内存：boot ROM
此部分主要包含boot ROM，其结构为：未使用–boot ROM–未使用
当你对主板上电，主板做的第一件事情就是运行存储在boot ROM中的代码，当boot完成之后，会跳转到地址0x80000000，OS需要确保这个地址有一些数据以启动 OS
0x80000000之下：DRAM外的I/O设备
主要分为：中断控制器、Concole和显示器交互、与磁盘交互
我们向这些 “虚拟的物理内存” 读写即是在与实际设备交互，包括与DRAM物理内存的交互也是被虚拟化后的，实际的DRAM可不是一个大数组，这是一层抽象
最上方的 Unused
——DRAM不够了，这部分物理内存没被覆盖到
xv6 中设置为128MB
XV6 内核地址空间
内核地址空间的映射大多数都是 恒等映射：从最底部的设备到PHYSTOP
内核栈在VM中的位置很靠后，这是为了在其后放置一个 guard page，以防止栈溢出
- Guard page的PTE中Valid标志位未设置，会导致立即触发page fault
- 也就是说，guard page 未被映射到任何物理地址，它只是占据了虚拟地址空间的一段靠后的地址。
kernel stack 被映射了两次，在 靠后的虚拟地址 映射了一次，在PHYSTOP下的Kernel data中又映射了一次
- Kernel data 段中无 guard page
- 实际使用的时候用的是上面的部分，因为有Guard page会更加安全
- 每一个用户进程都有一个对应的kernel stack
通过设置 权限 我们可以尽早的发现Bug从而避免Bug
- Kernel text page：R-X
- Kernel data page：RW-
free memory
存储用户进程的 PT、text、data，耗尽时 fork 和 exec 会返回错误
理论上来说用户和内核的虚拟地址空间大小一样，但是用户的VM使用率更低
xv6 的实现
kvminit
设置 kernel 地址空间
先为最高级页表分配物理页，并初始化为全0
通过 kvmmap 为每一个 I/O 设备创建 PTE，其 va 和 pa 由宏定义的值指定
- memlayout.h
- 由代码可见，这是恒等映射/直接映射
分析
执行完第一个kvmmap时的kernel page table：
最高级页表位于 0x87fff000，只有一个页表项，其序号为0
中间页表位于
，只有一个页表项，其序号为128。最低级的页表，最终指向 UART0，即 0x10000000L，即：000000000 010000000 000000000 000000000000
- 0x10000000L 右移12位为VPN，再右移九位为二级页表的序号128（因为最高级页表序号为0）
- 根据 fl 部分可确定标志位，图中最低级PTE的标志为：0x7 = 0111，即：WRV，这意味着合法可读写，不可执行不可用户访问等等
kvminithart
设置 SATP 寄存器，使用 kvminit 刚设置好的页表——我们现在有了分页机制
- 此前用的是物理地址，此后使用的全都是虚拟地址
- 内核的映射基本全都是恒等映射，经过地址翻译0x80001110还是对应0x80001110。
- 切换进程时需要切换页表，一旦 SATP 设置错了，其结果是，要么覆盖掉别的数据进而造成奇怪的错误，要么访问到非法page产生 page fault
然后刷新 TLB
walk
模拟MMU进行地址翻译，返回 va 对应的 PTE 的指针
- 没有 TLB 这样的专门缓存
在翻译过程中，如果中间PTE不存在，若alloc被设置，则会分配一个临时的PTE初始化为0，并继续执行，否则直接返回0
即便有了分页机制，walk函数还能正常工作，这正是因为恒等映射
