这个答案的版本带有漂亮的目录和更多内容。
我会更正任何报告的错误。如果您想进行大的修改或添加缺失的方面,请在您自己的答案中进行以获得应得的声望。可以直接合并小编辑。
示例代码
最小化示例:https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S
像编程中的其他所有一样,真正理解它的唯一方法是使用最小化的示例进行操作。
使这成为“困难”主题的原因是,最小示例很大,因为您需要制作自己的小型操作系统。
英特尔手册
虽然没有具体的示例很难理解,但请尽快熟悉手册。
英特尔在Intel手册第3卷系统编程指南-325384-056US 2015年9月的第4章“分页”中描述了分页。
特别有趣的是图4-4“带32位分页的CR3和分页结构条目格式”,其中给出了关键数据结构。
MMU
分页由CPU的内存管理单元(MMU)执行。与许多其他部件(例如x87协处理器,APIC)一样,早期它也是由独立芯片执行的,后来被集成到了CPU中。但该术语仍在使用中。
常规事实
逻辑地址是“常规”用户空间代码中使用的内存地址(例如,在
mov eax,[rsi]
中
rsi
的内容)。
首先,分段将它们转换为线性地址,然后再通过分页将线性地址转换为物理地址。
(logical) ------------------> (linear) ------------> (physical)
segmentation paging
大多数情况下,我们可以将物理地址视为索引实际的RAM硬件内存单元,但这并非完全正确,因为存在以下原因:
分页仅在保护模式下可用。在保护模式下使用分页是可选的。如果cr0
寄存器的PG
位被设置,则打开分页。
分页与分段
分页和分段之间的一个主要区别是:
- 分页将RAM分成称为页面的等大小块
- 分段将内存分成任意大小的块
这是分页的主要优点,因为等大小的块使得管理更加容易。
分页已经变得如此流行,以至于在64位模式下的x86-64中放弃了对分段的支持,这是新软件的主要操作模式,在兼容模式下仍然存在,该模式模拟IA32。
应用
分页用于在现代操作系统上实现进程的虚拟地址空间。使用虚拟地址,操作系统可以以以下方式将两个或更多并发进程放入单个RAM中:
- 两个程序都不需要知道对方
- 两个程序的内存可以根据需要增长和缩小
- 程序之间的切换非常快
- 一个程序永远无法访问另一个进程的内存
分页历史上是在分段之后出现的,并在现代操作系统(如Linux)中大量取代了分段,因为使用固定大小的页面来管理内存块比使用可变长度的段更容易。
硬件实现
与保护模式下的分段类似(其中修改段寄存器会触发从GDT或LDT加载),分页硬件使用内存中的数据结构来完成其工作(例如页表、页目录等)。
这些数据结构的格式由硬件固定,但操作系统需要正确设置和管理这些数据结构在RAM中,并告诉硬件在哪里找到它们(通过cr3
)。
有些其他的架构几乎完全将分页交给软件处理,因此TLB未命中会运行一个由操作系统提供的函数来遍历页表并将新映射插入到TLB中。这样可以让操作系统选择页表格式,但使得硬件无法像x86那样将页行走与乱序执行的其他指令重叠。
示例:简化的单级分页方案
这是一个示例,展示了如何在一个简化版的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
在哪里:
页面表位于 RAM 上。例如,它们可以位于以下位置:
--------------> 0xFFFFFFFF
--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1
--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2
--------------> 0x0
两个页表的初始位置是任意的,并由操作系统控制。这取决于操作系统来确保它们不重叠!
每个进程都不能直接访问任何页面表,虽然它可以向操作系统发出请求,导致页面表被修改,例如请求更大的堆或栈段。
一个页面是4KB(12位)的一块内存,由于地址有32位,所以只需要20位(20 + 12 = 32,因此16进制表示中的5个字符)来标识每个页面。该值由硬件固定。
页面表项
一个页面表是...页面表项的表!
表项的确切格式由硬件固定。
在这个简化的例子中,页面表项仅包含两个字段:
bits function
----- -----------------------------------------
20 physical address of the start of the page
1 present flag
在这个例子中,硬件设计者可以选择
L = 21
。
大多数实际的页表条目还有其他字段。
由于内存是按字节寻址而不是按位寻址,因此将东西对齐到21位是不切实际的。因此,即使在这种情况下只需要21位,硬件设计者也可能会选择
L = 32
以加快访问速度,并保留剩余的位用于后续使用。在x86上,
L
的实际值为32位。
单级方案中的地址转换
一旦操作系统设置好了页表,线性地址和物理地址之间的地址转换就由硬件完成。
当操作系统想要激活进程1时,它将
cr3
设置为
PT1
,即进程1的表的开头。
如果进程1想要访问线性地址
0x00000001
,则分页硬件电路自动为操作系统执行以下操作:
split the linear address into two parts:
| page (20 bits) | offset (12 bits) |
So in this case we would have:
- page = 0x00000
- offset = 0x001
look into Page table 1 because cr3
points to it.
look entry 0x00000
because that is the page part.
The hardware knows that this entry is located at RAM address PT1 + 0 * L = PT1
.
since it is present, the access is valid
by the page table, the location of page number 0x00000
is at 0x00001 * 4K = 0x00001000
.
to find the final physical address we just need to add the offset:
00001 000
+ 00000 001
-----------
00001 001
because 00001
is the physical address of the page looked up on the table and 001
is the offset.
As the name indicates, the offset is always simply added the physical address of the page.
the hardware then gets the memory at that physical location.
同样地,对于进程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,以下翻译将会发生:
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中。
操作系统可以根据页面表项的其余内容发现这种情况,因为如果未设置“present”标志,则页面表项的其他条目完全由操作系统自行处理。
例如,在Linux中,“present = 0”时:
无论如何,操作系统需要知道是哪个地址造成了页面错误才能处理问题。这就是为什么聪明的IA32开发人员在发生页面错误时将
cr2
的值设置为该地址。异常处理程序可以直接查看
cr2
来获取地址。
简化
使这个例子更容易理解的现实简化:
示例:多级分页方案
单级分页方案的问题在于它会占用太多的RAM:4G / 4K = 每个进程1M条目。如果每个条目长度为4字节,那么每个进程将使用4M,即使对于台式电脑来说也太多了:
ps -A | wc -l
显示我现在正在运行244个进程,所以这将占用约1GB的RAM!因此,x86开发人员决定使用减少RAM使用的多级方案。该系统的缺点是访问时间略长。在用于32位处理器且没有PAE的简单的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
操作系统分配给进程1的页面表为
PT1 = 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
操作系统给进程1分配的页表为 PT2 = 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
位置:
PD1
:进程1页目录在RAM上的初始位置。
PT1
和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
分组后得到:
0000000010 0000000001 000000000100
0x2 0x1 0x4
这给出了:
- 页目录项 = 0x2
- 页表项 = 0x1
- 偏移量 = 0x4
因此,硬件查找页目录的第二个条目。
页目录表指示页表位于0x80000 * 4K = 0x80000000
。这是进程的第一个RAM访问。
由于页表项为0x1
,硬件查看位于0x80000000
的页表的第一项,该项告诉它物理页位于地址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位架构
64位地址对于当前的RAM大小仍然过多,因此大多数架构将使用更少的位数。
x86_64使用48位(256 TiB),传统模式的PAE已经允许52位地址(4 PiB)。
这48位中的12位已经保留给偏移量,剩下36位。
如果采用两级方法,则最佳分配是两个18位级别。
但这意味着页目录将具有256K个条目,这将占用太多RAM:接近32位架构的单层分页!
因此,64位架构创建了更进一步的页面级别,通常为3或4个。
x86_64在9 | 9 | 9 | 12方案中使用4个级别,以便上层仅占用2^9个更高级别条目。
PAE
物理地址扩展。
32位系统只能寻址4GB内存。
这对于大型服务器来说成为了限制,因此英特尔在Pentium Pro中引入了PAE机制。
为了缓解问题,英特尔添加了4条新的地址线,使得可以寻址64GB。
如果开启PAE,则页面表结构也会被改变。它被改变的确切方式取决于PSE是否开启。
通过cr4
的PAE
位可以开启或关闭PAE。
即使可寻址内存总量为64GB,单个进程仍然只能使用最多4GB。但操作系统可以将不同的进程放置在不同的4GB块上。
PSE
页面大小扩展。
允许页面长度为4M(如果开启PAE,则为2M),而不是4K。
通过cr4
的PSE
位可以开启或关闭PSE。
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位已经无法容纳更多的条目了,因为它们都被20个地址位和12个有意义或保留的标志位填满了。
原因是20位不再足以表示页表的地址:现在需要24位,因为处理器添加了4根额外的线路。
因此,设计人员决定将条目大小增加到64位,并使它们适合单个页表中,必须将条目数减少到2^9而不是2^10。
起始的2是一个新的页级别,称为Page Directory Pointer Table(PDPT),因为它“指向”页目录并填充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位。将2留给PDPT,以使其与没有PSE的PAE情况保持一致,剩下21位用于偏移量,这意味着页面宽度为2M而不是4M。
TLB
翻译预读缓存(TLB)是用于分页地址的缓存。
由于它是一个缓存,因此它与CPU缓存共享许多设计问题,例如关联级别。
本节将描述一个简化的全关联TLB,具有4个单地址条目。请注意,像其他缓存一样,真实的TLB通常不是全关联的。
基本操作
在线性地址和物理地址之间进行转换后,它会被存储在TLB中。例如,一个4个条目的TLB的起始状态如下:
valid linear physical
------ ------- ---------
> 0 00000 00000
0 00000 00000
0 00000 00000
0 00000 00000
“>”符号表示需要被替换的当前条目。
在将页面线性地址“00003”转换为物理地址“00005”后,TLB变成了:
valid linear physical
------ ------- ---------
1 00003 00005
> 0 00000 00000
0 00000 00000
0 00000 00000
在将00007
翻译为00009
之后,它变成了:
valid linear physical
------ ------- ---------
1 00003 00005
1 00007 00009
> 0 00000 00000
0 00000 00000
现在如果需要再次翻译
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
添加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更昂贵。
使条目无效
当cr3
改变时,所有TLB条目都会失效,因为将要使用新进程的新页面表,所以旧条目很可能没有任何意义。
x86还提供了invlpg
指令,可以明确地使单个TLB条目无效。其他体系结构提供了更多的指令来使TLB条目无效,例如使给定范围内的所有条目无效。
一些x86 CPU超出了x86规范的要求,并提供了比它所保证的更多的一致性,在修改页面表条目并在未缓存在TLB中时使用它们之间的 关系。 显然,Windows 9x依赖于此以确保正确性,但现代AMD CPU不提供一致的页面遍历。即使是Intel CPU也不会提供一致性,尽管它们必须检测到错误的推测才能做到这一点。 利用这一点可能不是一个好主意,因为可能没有太多收益,而且会导致难以调试的微妙的时间敏感问题。
Linux内核用法
The Linux内核广泛使用x86的分页功能,以允许快速进程切换和小数据碎片化。在v4.2中,请查看arch/x86/文件夹下的include/asm/pgtable*、include/asm/page*、mm/pgtable*和mm/page*等文件。似乎没有定义表示页面的结构体,只有宏:include/asm/page_types.h特别有意思。摘录如下:
arch/x86/include/uapi/asm/processor-flags.h
定义了CR0
,尤其是PG
位的位置:
#define X86_CR0_PG_BIT 31 /* Paging */
参考文献
免费:
非免费: