这个答案的版本有一个很好的目录和更多内容 http://www.cirosantilli.com/x86-paging.
我将纠正报告的任何错误。如果您想进行较大的修改或添加缺失的方面,请根据您自己的答案进行修改,以获得当之无愧的代表。较小的编辑可以直接合并。
示例代码
最小的例子:https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S
就像编程中的其他事情一样,真正理解这一点的唯一方法是使用最少的示例。
使这个主题成为“困难”主题的原因是最小的示例很大,因为您需要制作自己的小型操作系统。
英特尔手册
尽管如果没有示例就无法理解,但请尽快熟悉手册。
Intel 描述了分页英特尔手册第 3 卷系统编程指南 - 325384-056US 2015 年 9 月 https://web.archive.org/web/20151025081259/http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-system-programming-manual-325384.pdf第 4 章“寻呼”。
特别有趣的是图 4-4“CR3 和具有 32 位分页的分页结构条目的格式”,它给出了关键的数据结构。
MMU
分页是由内存管理单元 https://en.wikipedia.org/wiki/Memory_management_unit(MMU) CPU 的一部分。像许多其他人一样(例如x87 协处理器 https://en.wikipedia.org/wiki/X87, APIC https://en.wikipedia.org/wiki/Advanced_Programmable_Interrupt_Controller),早期是由单独的芯片实现,后来集成到CPU中。但这个词仍然被使用。
普遍事实
逻辑地址是“常规”用户空间代码中使用的内存地址(例如,rsi
in mov eax, [rsi]
).
首先分段将它们转换为线性地址,然后分页将线性地址转换为物理地址。
(logical) ------------------> (linear) ------------> (physical)
segmentation paging
大多数时候,我们可以将物理地址视为对实际 RAM 硬件内存单元的索引,但这并不是 100% 正确,因为:
- 内存映射 I/O 区域 https://en.wikipedia.org/wiki/Memory-mapped_I/O
- 多通道内存 https://en.wikipedia.org/wiki/Multi-channel_memory_architecture
寻呼仅在保护模式下可用。在保护模式下使用分页是可选的。寻呼已开启,当且仅当PG
的一点cr0
寄存器已设置。
分页与分段
分页和分段之间的一个主要区别是:
- 分页将 RAM 分成大小相等的块,称为页面
- 分段将内存分割成任意大小的块
这是分页的主要优点,因为相同大小的块使事情更易于管理。
分页变得越来越流行,以至于 x86-64 中的 64 位模式(新软件的主要操作模式)中放弃了对分段的支持,它仅存在于模拟 IA32 的兼容模式中。
应用
分页用于在现代操作系统上实现进程虚拟地址空间。通过虚拟地址,操作系统可以通过以下方式在单个 RAM 上容纳两个或多个并发进程:
- 两个程序都不需要了解对方
- 两个程序的内存都可以根据需要增长和收缩
- 程序之间的切换非常快
- 一个程序永远无法访问另一个进程的内存
历史上,分页是在分段之后出现的,并且在现代操作系统(例如 Linux)中虚拟内存的实现中很大程度上取代了它,因为管理固定大小的页面内存块比管理可变长度的段更容易。
硬件实现
与保护模式下的分段(修改段寄存器会触发 GDT 或 LDT 的加载)类似,分页硬件使用内存中的数据结构来完成其工作(页表、页目录等)。
这些数据结构的格式是固定的通过硬件,但是由操作系统来正确设置和管理 RAM 上的这些数据结构,并告诉硬件在哪里找到它们(通过cr3
).
其他一些架构将分页几乎完全交给软件处理,因此 TLB 未命中会运行操作系统提供的函数来遍历页表并将新映射插入到 TLB 中。这使得页表格式由操作系统选择,但使其硬件不可能像 x86 那样将页面行走与其他指令的无序执行重叠 https://stackoverflow.com/questions/32256250/what-happens-after-a-l2-tlb-miss.
示例:简化的单级分页方案
这是一个分页操作的例子简化的x86架构的版本
来实现虚拟内存空间。
页表
操作系统可以为他们提供以下页表:
操作系统给进程1的页表:
RAM location physical address present
----------------- ----------------- --------
PT1 + 0 * L 0x00001 1
PT1 + 1 * L 0x00000 1
PT1 + 2 * L 0x00003 1
PT1 + 3 * L 0
... ...
PT1 + 0xFFFFF * L 0x00005 1
操作系统给进程2的页表:
RAM location physical address present
----------------- ----------------- --------
PT2 + 0 * L 0x0000A 1
PT2 + 1 * L 0x0000B 1
PT2 + 2 * L 0
PT2 + 3 * L 0x00003 1
... ... ...
PT2 + 0xFFFFF * L 0x00004 1
Where:
-
PT1
and PT2
:表 1 和表 2 在 RAM 上的初始位置。
样本值:0x00000000
, 0x12345678
, etc.
由操作系统决定这些值。
-
L
:页表项的长度。
-
present
:表示该页存在于内存中。
页表位于 RAM 上。例如,它们可以位于:
--------------> 0xFFFFFFFF
--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1
--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2
--------------> 0x0
两个页表在 RAM 上的初始位置是任意的并且由操作系统控制。由操作系统来确保它们不重叠!
每个进程都不能直接接触任何页表,尽管它可以向操作系统发出导致页表修改的请求,例如请求更大的堆栈或堆段。
一个页面是一个 4KB(12 位)的块,由于地址有 32 位,因此只需要 20 位(20 + 12 = 32,因此 5 个十六进制字符)来标识每个页面。该值由硬件固定。
页表条目
页表是...页表条目的表!
表条目的确切格式是固定的通过硬件.
在这个简化的示例中,页表条目仅包含两个字段:
bits function
----- -----------------------------------------
20 physical address of the start of the page
1 present flag
所以在这个例子中硬件设计者可以选择L = 21
.
大多数实际页表条目都有其他字段。
以 21 位对齐是不切实际的,因为内存是按字节而不是按位寻址的。因此,即使在这种情况下只需要 21 位,硬件设计人员也可能会选择L = 32
为了使访问速度更快,只需保留剩余位以供以后使用。实际值L
在 x86 上是 32 位。
单层方案中的地址转换
一旦操作系统设置了页表,线性地址和物理地址之间的地址转换就完成了通过硬件.
当操作系统想要激活进程1时,它设置cr3
to PT1
,进程一的表的开始。
如果进程1想要访问线性地址0x00000001
, 寻呼hardware电路自动为操作系统执行以下操作:
-
将线性地址分成两部分:
| page (20 bits) | offset (12 bits) |
所以在这种情况下我们会有:
-
查看页表 1 因为cr3
指向它。
-
看条目0x00000
因为那是页面部分。
硬件知道该条目位于 RAM 地址PT1 + 0 * L = PT1
.
-
因为它存在,所以访问是有效的
-
通过页表,页码的位置0x00000
is at 0x00001 * 4K = 0x00001000
.
-
要找到最终的物理地址,我们只需要添加偏移量:
00001 000
+ 00000 001
-----------
00001 001
because 00001
是在表中查找到的页面的物理地址,001
是偏移量。
顾名思义,偏移量总是简单地添加页面的物理地址。
-
然后硬件获取该物理位置的内存。
同样,流程 1 会发生以下翻译:
linear physical
--------- ---------
00000 002 00001 002
00000 003 00001 003
00000 FFF 00001 FFF
00001 000 00000 000
00001 001 00000 001
00001 FFF 00000 FFF
00002 000 00002 000
FFFFF 000 00005 000
例如,访问地址时00001000
,页面部分是00001
硬件知道其页表项位于 RAM 地址:PT1 + 1 * L
(1
因为页面部分),这就是它将寻找它的地方。
当操作系统想要切换到进程2时,它需要做的就是使cr3
指向第2页。就是这么简单!
现在流程 2 将会发生以下翻译:
linear physical
--------- ---------
00000 002 00001 002
00000 003 00001 003
00000 FFF 00001 FFF
00001 000 00000 000
00001 001 00000 001
00001 FFF 00000 FFF
00003 000 00003 000
FFFFF 000 00004 000
相同的线性地址对于不同的进程转换为不同的物理地址,仅取决于里面的值cr3
.
通过这种方式,每个程序都可以期望其数据开始于0
并结束于FFFFFFFF
,无需担心确切的物理地址。
页面错误
如果进程 1 尝试访问不存在的页面内的地址怎么办?
硬件通过页面错误异常通知软件。
然后通常由操作系统注册异常处理程序来决定必须做什么。
访问不在表上的页可能是编程错误:
int is[1];
is[2] = 1;
但在某些情况下它可能是可以接受的,例如在 Linux 中:
-
该程序想要增加其堆栈。
它只是尝试访问给定可能范围内的某个字节,如果操作系统满意,它就会将该页面添加到进程地址空间。
-
该页面已交换到磁盘。
操作系统需要在进程后面做一些工作才能将页面返回到 RAM 中。
操作系统可以根据页表条目的其余部分的内容发现这种情况,因为如果当前标志被清除,则页表条目的其他条目完全留给操作系统做它想要的事情。
例如,在 Linux 上,当存在 = 0 时:
无论如何,操作系统需要知道哪个地址生成了页面错误才能处理该问题。这就是为什么优秀的 IA32 开发人员将值设置为cr2
每当发生页面错误时都会访问该地址。然后异常处理程序可以查看cr2
获取地址。
简化
对现实的简化使这个示例更容易理解:
-
所有实际的寻呼电路都使用多级寻呼来节省空间,但这显示了一个简单的单级方案。
-
页表仅包含两个字段:20 位地址和 1 位存在标志。
实际页表总共包含12个字段,因此其他功能已被省略。
示例:多级分页方案
单级分页方案的问题是它会占用太多 RAM:4G / 4K = 1M 条目per过程。如果每个条目长 4 个字节,则为 4M每个进程,即使对于台式计算机来说也太多了:ps -A | wc -l
说我现在正在运行 244 个进程,因此这将占用大约 1GB 的 RAM!
因此,x86 开发人员决定使用多级方案来减少 RAM 使用量。
该系统的缺点是访问时间稍长。
在用于不带 PAE 的 32 位处理器的简单 3 级分页方案中,32 个地址位划分如下:
| directory (10 bits) | table (10 bits) | offset (12 bits) |
每个进程必须有且仅有一个与其关联的页目录,因此它将至少包含2^10 = 1K
页目录条目,比单级方案所需的最小 1M 要好得多。
页表仅根据操作系统的需要进行分配。每个页表都有2^10 = 1K
页目录条目
页目录包含...页目录条目!页目录项与页表项相同,除了它们指向页表的 RAM 地址而不是表的物理地址。由于这些地址只有 20 位宽,因此页表必须位于 4KB 页面的开头。
cr3
现在指向当前进程的页目录在 RAM 上的位置,而不是页表。
页表条目在单级方案中根本不会改变。
页表从单级方案发生变化,因为:
- 每个进程最多可以有 1K 个页表,每页一个目录项。
- 每个页表恰好包含 1K 个条目,而不是 1M 个条目。
在前两个级别上使用 10 位的原因(而不是说,12 | 8 | 12
)是每个页表条目的长度为 4 个字节。那么页目录和页表的 2^10 条目将很好地适合 4Kb 页面。这意味着为此目的分配和释放页面可以更快、更简单。
多级方案中的地址转换
操作系统给进程1的页目录:
RAM location physical address present
--------------- ----------------- --------
PD1 + 0 * L 0x10000 1
PD1 + 1 * L 0
PD1 + 2 * L 0x80000 1
PD1 + 3 * L 0
... ...
PD1 + 0x3FF * L 0
操作系统将页表提供给进程 1PT1 = 0x10000000
(0x10000
* 4K):
RAM location physical address present
--------------- ----------------- --------
PT1 + 0 * L 0x00001 1
PT1 + 1 * L 0
PT1 + 2 * L 0x0000D 1
... ...
PT1 + 0x3FF * L 0x00005 1
操作系统将页表提供给进程 1PT2 = 0x80000000
(0x80000
* 4K):
RAM location physical address present
--------------- ----------------- --------
PT2 + 0 * L 0x0000A 1
PT2 + 1 * L 0x0000C 1
PT2 + 2 * L 0
... ...
PT2 + 0x3FF * L 0x00003 1
where:
-
PD1
:进程1的页目录在RAM上的初始位置。
-
PT1
and PT2
:进程 1 的页表 1 和页表 2 在 RAM 上的初始位置。
因此,在此示例中,页目录和页表可以存储在 RAM 中,如下所示:
----------------> 0xFFFFFFFF
----------------> PT2 + 0x3FF * L
Page Table 1
----------------> PT2
----------------> PD1 + 0x3FF * L
Page Directory 1
----------------> PD1
----------------> PT1 + 0x3FF * L
Page Table 2
----------------> PT1
----------------> 0x0
我们来翻译一下线性地址0x00801004
一步步。
我们假设cr3 = PD1
,即指向刚才描述的页面目录。
在二进制中,线性地址是:
0 0 8 0 1 0 0 4
0000 0000 1000 0000 0001 0000 0000 0100
分组为10 | 10 | 12
gives:
0000000010 0000000001 000000000100
0x2 0x1 0x4
这使:
- 页目录项 = 0x2
- 页表项 = 0x1
- 偏移量 = 0x4
因此硬件寻找页目录的条目2。
页目录表表示页表位于0x80000 * 4K = 0x80000000
。这是该进程的第一次 RAM 访问。
由于页表项是0x1
,硬件查看页表的条目 10x80000000
,这告诉它物理页位于地址0x0000C * 4K = 0x0000C000
。这是该进程的第二次 RAM 访问。
最后分页硬件加上偏移量,最终地址为0x0000C004
.
翻译地址的其他示例包括:
linear 10 10 12 split physical
-------- --------------- ----------
00000001 000 000 001 00001001
00001001 000 001 001 page fault
003FF001 000 3FF 001 00005001
00400000 001 000 000 page fault
00800001 002 000 001 0000A001
00801008 002 001 008 0000C008
00802008 002 002 008 page fault
00B00001 003 000 000 page fault
如果页目录项或页表项不存在,则会发生页错误。
如果操作系统想要同时运行另一个进程,它会给第二个进程一个单独的页目录,并将该目录链接到单独的页表。
64 位架构
对于当前的 RAM 大小来说,64 位的地址仍然太多,因此大多数架构将使用更少的位。
x86_64 使用 48 位 (256 TiB),传统模式的 PAE 已经允许 52 位地址 (4 PiB)。
这 48 位中的 12 位已为偏移量保留,剩下 36 位。
如果采用 2 级方法,则最佳分割将是两个 18 位级。
但这意味着页面目录将具有2^18 = 256K
条目,这会占用太多 RAM:接近 32 位架构的单级分页!
因此,64 位架构创建了更多的页面级别,通常为 3 或 4。
x86_64 在一个中使用 4 个级别9 | 9 | 9 | 12
方案,这样上层只占用2^9
更高级别的条目。
PAE
物理地址扩展。
使用 32 位时,只能寻址 4GB RAM。
这开始成为大型服务器的限制,因此英特尔向 Pentium Pro 引入了 PAE 机制。
为了缓解这个问题,Intel增加了4条新的地址线,这样就可以寻址64GB。
如果 PAE 打开,页表结构也会改变。更改的具体方式取决于 PSE 是打开还是关闭。
PAE 通过以下方式打开和关闭PAE
bit of cr4
.
即使总可寻址内存为 64GB,单个进程仍然只能使用最多 4GB。然而,操作系统可以将不同的进程放在不同的 4GB 块上。
PSE
页面尺寸扩展。
允许页面长度为 4M(如果 PAE 打开,则为 2M)而不是 4K。
PSE 通过以下方式打开和关闭PSE
bit of cr4
.
PAE 和 PSE 页表方案
如果 PAE 和 PSE 之一处于活动状态,则使用不同的寻呼级别方案:
-
无 PAE 和 PSE:10 | 10 | 12
-
无 PAE 和 PSE:10 | 22
.
22 是 4Mb 页内的偏移量,因为 22 位地址为 4Mb。
-
PAE 且无 PSE:2 | 9 | 9 | 12
使用两次 9 而不是 10 的设计原因是,现在条目不再适合 32 位,而 32 位全部由 20 个地址位和 12 个有意义或保留标志位填充。
原因是 20 位已经不足以表示页表的地址:现在需要 24 位,因为处理器添加了 4 条额外的线。
因此,设计者决定将条目大小增加到 64 位,并且为了使它们适合单个页表,有必要将条目数量减少到 2^9 而不是 2^10。
开头 2 是一个新的页面级别,称为页面目录指针表 (PDPT),因为它points到页目录并填写32位线性地址。 PDPT 也是 64 位宽。
cr3
现在指向 PDPT,它必须位于前四个 4GB 内存上,并按 32 位倍数对齐以提高寻址效率。这意味着现在cr3
有 27 个有效位,而不是 20 个:2^5 为 32 倍数 * 2^27 来完成第一个 4GB 的 2^32。
-
PAE 和 PSE:2 | 9 | 21
设计者决定保留 9 位宽的字段以使其适合单个页面。
剩下 23 位。为 PDPT 留下 2,以与没有 PSE 的 PAE 情况保持一致,为偏移留下 21,这意味着页面宽度为 2M,而不是 4M。
TLB
转换先行缓冲区 (TLB) 是分页地址的高速缓存。
由于它是缓存,因此它共享CPU缓存的许多设计问题,例如关联级别。
本节将描述具有 4 个单地址条目的简化全关联 TLB。请注意,与其他缓存一样,真正的 TLB 通常不是完全关联的。
基本操作
线性地址和物理地址之间发生转换后,它被存储在 TLB 上。例如,4 条目 TLB 以以下状态启动:
valid linear physical
------ ------- ---------
> 0 00000 00000
0 00000 00000
0 00000 00000
0 00000 00000
The >
表示当前要替换的条目。
在页线性地址之后00003
被转换为物理地址00005
,TLB 变为:
valid linear physical
------ ------- ---------
1 00003 00005
> 0 00000 00000
0 00000 00000
0 00000 00000
经过第二次翻译后00007
to 00009
它成为了:
valid linear physical
------ ------- ---------
1 00003 00005
1 00007 00009
> 0 00000 00000
0 00000 00000
Now if 00003
需要再次翻译,硬件首先查找TLB并通过单次RAM访问找出其地址00003 --> 00005
.
当然,00000
不在 TLB 上,因为没有有效条目包含00000
作为钥匙。
换货政策
当 TLB 填满时,旧地址将被覆盖。就像 CPU 缓存一样,替换策略是一个潜在复杂的操作,但一个简单合理的启发式方法是删除最近最少使用的条目 (LRU)。
使用 LRU,从状态开始:
valid linear physical
------ ------- ---------
> 1 00003 00005
1 00007 00009
1 00009 00001
1 0000B 00003
adding 0000D -> 0000A
会给出:
valid linear physical
------ ------- ---------
1 0000D 0000A
> 1 00007 00009
1 00009 00001
1 0000B 00003
CAM
使用 TLB 使转换速度更快,因为初始转换需要一次访问每个 TLB 级别,这意味着在简单的 32 位架构上为 2,但在 64 位架构上则为 3 或 4。
TLB 通常作为一种昂贵的 RAM 类型来实现,称为内容可寻址存储器 (CAM)。 CAM 在硬件上实现关联映射,即给定键(线性地址)检索值的结构。
映射也可以在 RAM 地址上实现,但 CAM 映射可能需要比 RAM 映射少得多的条目。
例如,一张地图,其中:
- 键和值都有 20 位(简单分页方案的情况)
- 每次最多需要存储4个值
可以存储在具有 4 个条目的 TLB 中:
linear physical
------- ---------
00000 00001
00001 00010
00010 00011
FFFFF 00000
然而,要使用 RAM 来实现这一点,需要有 2^20 个地址:
linear physical
------- ---------
00000 00001
00001 00010
00010 00011
... (from 00011 to FFFFE)
FFFFF 00000
这比使用 TLB 更昂贵。
使条目无效
When cr3
如果发生更改,所有 TLB 条目都会失效,因为将使用新进程的新页表,因此任何旧条目都不可能具有任何意义。
x86 还提供invlpg
显式使单个 TLB 条目无效的指令。其他架构为无效的 TLB 条目提供更多指令,例如使给定范围内的所有条目无效。
一些 x86 CPU 超出了 x86 规范的要求,并提供了比它所保证的更多的一致性,当页表条目尚未缓存在 TLB 中时,在修改页表条目和使用它之间 http://blog.stuffedcow.net/2015/08/pagewalk-coherence/。显然 Windows 9x 依赖于此来确保正确性,但现代 AMD CPU 不提供连贯的页面遍历。英特尔 CPU 确实如此,尽管它们必须检测错误推测才能这样做。利用这一点可能是一个坏主意,因为可能没有太多好处,并且存在导致难以调试的微妙时序敏感问题的巨大风险。
Linux内核使用
Linux 内核广泛使用 x86 的分页功能,以允许快速进程切换和小数据碎片。
In v4.2
,看下面arch/x86/
:
include/asm/pgtable*
include/asm/page*
mm/pgtable*
mm/page*
似乎没有定义任何结构来表示页面,只有宏:include/asm/page_types.h
特别有趣。摘抄:
#define _PAGE_BIT_PRESENT 0 /* is present */
#define _PAGE_BIT_RW 1 /* writeable */
#define _PAGE_BIT_USER 2 /* userspace addressable */
#define _PAGE_BIT_PWT 3 /* page write through */
arch/x86/include/uapi/asm/processor-flags.h
定义CR0
,特别是PG
位位置:
#define X86_CR0_PG_BIT 31 /* Paging */
参考书目
Free:
非免费: