第 15 章 机制：地址转换 ¶

这章是讲如何高效、灵活地虚拟化内存。

当 CPU 取指令或者执行一条访存指令的时候，它都是基于虚拟地址访问属于当前正在运行的应用的地址空间。

此时，CPU 中的 内存管理单元 (MMU, Memory Management Unit) 自动将这个虚拟地址进行 地址转换 (Address Translation) 变为一个物理地址，即这个应用的数据 / 指令的物理内存位置。

参考：rCore-Tutorial-Book-v3 # 增加硬件加速虚实地址转换

15.1 假设 ¶

假设：

1. 用户的地址空间必须连续地放在物理内存中；
2. 地址空间不是很大；
3. 每个地址空间大小完全一样。

15.2 一个例子 ¶

void func() {
    int x;
    x = x + 3; // this is the line of code we are interested in
}

128: movl 0x0(%ebx), %eax ;load 0+ebx into eax
132: addl $0x03, %eax ;add 3 to eax register
135: movl %eax, 0x0(%ebx) ;store eax back to mem

代码和数据都位于进程的地址口令你感觉，3 条指令序列位于地址 128（靠近头部的代码段），变量 x 的值位于地址 15 KB （在靠近底部的栈中）。

如果这 3 条指令执行，从进程的角度来看，发生了以下几次内存访问：

• 从地址 128 获取指令；
• 执行指令（从地址 15 KB 加载数据）；
• 从地址 132 获取命令；
• 执行命令（没有内存访问）；
• 从地址 135 获取指令；
• 执行指令（新值存入地址 15 KB）。

从程序的角度来看，它的地址空间（address space）从 0 开始到 16 KB 结束。它包含的所有内存引用都应该在这个范围内。然而，对虚拟内存来说，操作系统希望将这个进程地址空间放在物理内存的其他位置，并不一定从地址 0 开始。

因此我们遇到了如下问题：

• 怎样在内存中重定位这个进程，同时对该进程透明（transparent）？
• 怎么样提供一种虚拟地址空间从 0 开始的假象，而实际上地址空间位于另外某个物理地址？

例子：

15.3 动态（基于硬件）重定位 ¶

动态（基于硬件）重定位，最初只是一个简单的实现，称为基址加界限 (base and bound) 机制，有时又称为动态重定位 (dynamic relocation)。

每个 CPU 需要两个硬件寄存器：

• 基址 (base) 寄存器
• 界限 (bound) 寄存器，有时称为限制 (limit) 寄存器

程序真正运行时，操作系统会决定其在物理内存中的实际加载地址，并将起始地址记录在基址寄存器中。进程中使用的内存引用都是虚拟地址 (virtual address)，硬件将虚拟地址加上基址寄存器的值，得到物理地址 (physical address)，再发给内存系统。

界限寄存器被用来保存虚拟地址空间的大小，如果程序访问超过这个界限或者为负数的虚拟地址，CPU 将触发异常。（界限寄存器也可以记录地址空间结束的物理地址，硬件在转化虚拟地址到物理地址之后才去检查这个界限，逻辑上是等价的。）

转换示例 ¶

15.4 硬件支持：总结 ¶

15.5 操作系统的问题 ¶

硬件与操作系统的交互过程：

sequenceDiagram
    participant ProgramA as 程序 A（用户模式）
    participant ProgramB as 程序 B（用户模式）
    participant OS as 操作系统（内核模式）
    participant Hardware as 硬件

    Note over ProgramA, Hardware: 启动
    OS->>Hardware: 初始化陷阱表
    Note over Hardware: 记住以下地址:<br>系统调用处理程序<br>时钟处理程序<br>非法内存处理程序<br>非常指令处理程序
    OS->>Hardware: 开始中断时钟
    Note over Hardware: 开始时钟, 在 x ms 后中断
    Note over OS: 初始化进程表, 初始化空闲列表

    Note over ProgramA, Hardware: 运行
    Note over OS: 在进程表中分配条目
    Note over OS: 为进程分配内存
    Note over OS: 设置基址/界限寄存器
    Note over OS: 恢复 A 的寄存器    

    OS->>ProgramA: 跳到 A（最初）的程序计数器
    Note over ProgramA: 运行
    ProgramA->>Hardware: 获取指令
    Note over Hardware: 转换虚拟地址并获取
    Hardware->>ProgramA: 返回指令
    Note over ProgramA: 执行指令
    ProgramA->>Hardware: 加载/保存
    Note over Hardware: 确保地址不越界
    Note over Hardware: 转换虚拟地址并获取
    Hardware->>ProgramA: 返回指令
    Note over ProgramA: 执行

    Note over ProgramA, Hardware: 时钟中断
    ProgramA->>OS: 陷入
    Note over OS: 将寄存器 (A) 保存到进程结构 (A) 
    Note over OS: 从进程结构 (B) 恢复寄存器 (B)
    OS->>ProgramB: 从陷入返回（进入 B）
    Note over ProgramB: 运行
    ProgramB->>Hardware: 执行错误的加载
    Note over Hardware: 加载越界
    Hardware->>OS: 跳到陷阱处理程序
    Note over OS: 决定终止进程 B
    Note over OS: 回收 B 的内存
    Note over OS: 移除 B 在进程表中的条目

作业 ¶

ARG seed 1
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x0000363c (decimal 13884)
  Limit  : 290

Virtual Address Trace
  VA  0: 0x0000030e (decimal:  782) --> PA or segmentation violation?
  VA  1: 0x00000105 (decimal:  261) --> PA or segmentation violation?
  VA  2: 0x000001fb (decimal:  507) --> PA or segmentation violation?
  VA  3: 0x000001cc (decimal:  460) --> PA or segmentation violation?
  VA  4: 0x0000029b (decimal:  667) --> PA or segmentation violation?

ARG seed 0
ARG address space size 1k
ARG phys mem size 16k

Base-and-Bounds register information:

  Base   : 0x00003082 (decimal 12418)
  Limit  : 472

Virtual Address Trace
  VA  0: 0x000001ae (decimal:  430) --> PA or segmentation violation?
  VA  1: 0x00000109 (decimal:  265) --> PA or segmentation violation?
  VA  2: 0x0000020b (decimal:  523) --> PA or segmentation violation?
  VA  3: 0x0000019e (decimal:  414) --> PA or segmentation violation?
  VA  4: 0x00000322 (decimal:  802) --> PA or segmentation violation?
  VA  5: 0x00000136 (decimal:  310) --> PA or segmentation violation?
  VA  6: 0x000001e8 (decimal:  488) --> PA or segmentation violation?
  VA  7: 0x00000255 (decimal:  597) --> PA or segmentation violation?
  VA  8: 0x000003a1 (decimal:  929) --> PA or segmentation violation?
  VA  9: 0x00000204 (decimal:  516) --> PA or segmentation violation?

$ ./relocation.py -s 1 -n 10 -l 100 -b 16284 -c

$ ./relocation.py -s 1 -n 10 -l 100 -b 16284 -a 32m -p 1g -c

import numpy as np
import matplotlib.pyplot as plt

# 定义常量
address_size = 1 << 10
phys_size = 4 << 10
iterations = 300

# 预先生成所有需要的随机地址
random_addresses = np.random.randint(0, address_size, size=(phys_size, iterations))

# 通过累计求和计算每个限制值下的有效地址分数
valid_counts = np.sum(random_addresses < np.arange(phys_size)[:, None], axis=1)

# 计算有效地址的平均分数
valid_fraction = valid_counts / iterations

# 绘图
fig = plt.figure()
x = np.linspace(1, phys_size, phys_size)
plt.plot(x, valid_fraction, color="teal")
plt.ylim(0, 1)
plt.margins(0)
plt.xlabel("Limit")
plt.ylabel("Valid fraction (Average)")
plt.savefig("valid_fraction.png", dpi=227)
plt.show()