虚拟地址转换[三] - 多级页表
🌲 使用单级页表的问题
上文为了演示的需要，使用的是一个单级页表。事实上，若内存容量较大，按照常规的4KB的page大小的话，page table entry的数目将会很大。因为page table是按照VPN（virtual page number）来索引查找的，如果把单级页表视作一个big array，则VPN就相当于数组下标，因此page table本身需要在内存中是连续分布的，而且即便没有使用到的page，也会占用一个entry。
为了解决这些问题，在现代32/64位处理器中，通常使用的都是多级页表，操作系统的实现中也提供了对多级页表的支持。
🌲 多级页表的查找方法
MMU中的table walk unit使用虚拟地址中位域的子集做为index，顺着页表层次结构的各个级别往下查找。以一个虚拟地址为30位，第一级页表PD（Page Directory）占8 bits，第二级页表PT（Page Table）占10 bits，页大小为4KB（占12 bits）的系统为例：
- 通过
PTBP（Page Table Base Pointer）寄存器获得PD页表的起始物理地址（如果页表自己都用虚拟地址，那岂不是还得另外有个页表来转换，陷入死循环了……），然后从待转换的虚拟地址中取出高8位作为index找到对应的PD entry， 这个PD entry中存放的是它对应的PT页表的起始物理地址。 - 从待转换的虚拟地址中取出中间10位作为
index在PT表中找到对应的PT entry，这个PT entry中存放的是就是物理页面号（PPN, Physical Page Number）了。
在多级页表系统中，其实每级页表都可以视为一种“虚拟地址”向“物理地址”的转换，只是这里的“虚拟地址”是待转换的虚拟地址的一个位域子集，而除了最后一级页表PTE是直接指向物理页面的，其他级别页表里的“物理地址”都是指向对应下一级页表的首地址。
再举一个更加鲜活的带有实际地址的例子，为了便于演示，使用一个PD，PT，page offset分别占4 bits, 4bits, 12bits的系统。
对于虚拟地址0x01ABC，其中ABC为page offset，真正用来转换的只有高8位0x01。PD index为0，对应PFN为第一行的0x3，然后找到0x3对应的PT表，PT index为1，对应PFN为第二行的0x23，这样就得到了PPN为0x23，加上page offset就是最后的物理地址0x23ABC。另外两个虚拟地址0x00000和0xFEED0的查找过程也是一样的。
如果真的只有这3个地址所在的page被用到，那么只需要$2^4+2 \times 2^4 = 48$个entries就可以了，而如果采用单级页表，则需要 $2^8=256$个entries。在32位系统中，进程的虚拟地址空间为4GB，但某个进程实际使用的页只占其中的一小部分，其分布是稀疏的，因此非常适合使用多级页表这种稀疏的级联数组(radix tree)来表示。
🌲 多级页表使用现状
在32位处理器中，采用4KB的page大小，则虚拟地址低12位为page offest，高20位给页表，分成两级，每个级别占10个bit。为什么32位系统的页表每级占10位，每个页的大小被设定为4KB而不是2KB或者8KB？
页表本身也是放在内存中的，也要占用内存空间，如果index为10位，则其可索引的范围是1024个entris，32位系统中，每级页表的每个entry的大小为4个字节，则每个页表的大小刚好是4KB。页表首地址也是要按页对齐的，如果占不满一个页，页中剩下的空间也就浪费了。80386引入分页机制的时候应该就考虑过把页设置为多大是最合适的，显然4KB的页大小对内存的利用是最充分的。
对于intel的PAE（Physical Address Extension）模式，支持32位虚拟地址（为了保持和普通32位系统的程序兼容性）和36位物理地址，采用三级页表（2+9+9）。对于64位处理器，intel的IA32-e（x86-64）和ARMv8-A最开始都是只使用低48位，中间的36位给页表，分成四级页表，每个级别占9个bit。
之前intel的手册中称这3种paging模式分别为32-bit paging，PAE paging和IA-32e paging，但现在的IA-32e已经支持使用低57位的五级页表模式，每个级别依然占9个bit（9+9+9+9+9），所以IA-32e paging被改成为4-level paging【1】。
为什么64位系统的页表每级占9位呢？为了和硬件配合，基于i386编写的linux也采用4KB的页大小作为内存管理的基本单位。处理器进入64位时代后，其实可以不再使用4KB作为一个页帧的大小，但可能为了提供硬件的向前兼容性以及和操作系统的兼容性吧，大部分64位处理器依然使用4KB作为默认的页大小（ARMv8-A还支持16KB和64KB的页大小）。因为64位系统中，每级页表的每个entry的大小为8个字节，如果index为9位，则每个页表的大小也刚好是4KB。
那为什么64位系统就要采用四级或者五级页表，而不是和32位系统一样采用两级页表呢？我们来试下如果采用两级页表会怎样。以采用48位虚拟地址为例，中间的36位若分给两级页表，则每级页表占18位（18+18），那么每级页表需要多达 （262144）个entries。其实多级页表可理解位一种时间换空间的技术，所以设计每级页表具体占多大，就是一种时间和空间的平衡。
每级页表指向的下一级都是按页对齐的，因此低12位就被空了出来。如果是采用48位虚拟地址的64位系统，则高16位也被空了出来。
这些空余的位空间可以被作为各种flag标识利用起来，关于这些flag的使用，请参考这篇文章。
🌲 操作系统支持
为了支持处理器的四级页表模式，Linux内核在之前PGD(page global directory)，PMD(page middle directory)，PTE(page table entry)三级页表的基础上，于2005年release的2.6.11版本加入了PUD(page upper directory) 。
为了支持处理器的五级页表模式，又于2017年release的4.12版本加入了P4D。PGD依然是顶层目录（关于为什么是向内插而不是向外插，请参考这篇文章），通过进程的mm_struct结构体获取到。当发生进程切换时，换入进程的页表的PGD的物理地址被装入CR3（for x86）/TTBRx（for ARM)寄存器中。关于Linux中页表的具体实现和使用，请参考这篇文章。
🌲 多级页表访问优化
使用多级页表的方式对于减少页表自身占用的内存空间确实是非常有效的。然而，为此付出的代价就是增加了地址转换过程中对内存的访问次数，进而增加了转换时间。那在除了前面介绍的TLB之外，还有哪些可以减少内存访问次数，加快地址转换的方法呢？
一个是使用大页（large page），一个是使用paging structure caches，具体将在本系列之后的文章介绍。
注【1】：从level的编号上看，是越高位bits的level编号越大，而在ARM里这是反过来的。不知是有意还是无意，x86里是数字越低代表特权级越高（ring 0 ~ ring3），而ARM里也是反过来的（EL0 ~ EL3）。
说明：本文部分例子来自 https://compas.cs.stonybrook.edu/~nhonarmand/courses/fa17/cse306/slides/06-paging.pdf
参考
- Four-level page tables
- Five-level page tables
- intel官方手册《5-Level Paging and 5-Level EPT》
- https://www.kernel.org/doc/Documentation/x86/x86_64/5level-paging.txt，讲linux中如何配置使用五级页表的。
转载：虚拟地址转换[三] - 多级页表