使用单级页表的问题
上文为了演示的需要，使用的是一个单级页表。事实上，若内存容量较大，按照常规的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 Register）寄存器获得PD页表的起始物理地址（如果页表自己都用虚拟地址，那岂不是还得另外有个页表来转换，陷入死循环了……），然后从待转换的虚拟地址中取出高8位作为index找到对应的PD entry， 这个PD entry中存放的是它对应的PT页表的起始物理地址。
从待转换的虚拟地址中取出中间10位作为index在PE表中找到对应的PE entry，这个PE entry中存放的是就是物理页面号（PPN, Physical Page Number）了。
在多级页表系统中，其实每级页表都可以视为一种“虚拟地址”向“物理地址”的转换，只是这里的“虚拟地址”是待转换的虚拟地址的一个位域子集，而除了最后一级页表PTE是直接指向物理页面的，其他级别页表里的“物理地址”都是指向对应下一级页表的首地址。
再举一个更加鲜活的带有实际地址的例子，为了便于演示，使用一个PD，PT，page offset分别占4 bits, 4bits, 12bits的系统。
对于虚拟地址0x01ABC，其中“ABC”为page offset, 真正用来转换的只有高8位“0001”。PD index为00，对应PFN为第一行的0x3，然后找到0x3对应的PT表，PT index为01，对应PFN为第二行的0x23，这样就得到了PPN为0x23，加上page offset就是最后的物理地址0x23ABC。另外两个虚拟地址0x00000和0xFEED0的查找过程也是一样的。
如果真的只有这3个地址所在的page被用到，那么只需要 
个entries就可以了，而如果采用单级页表，则需要 
个entries。在32位系统中，进程的虚拟地址空间为4GB，但某个进程实际只用的页只占其中的一小部分，其分布是稀疏的，所以使用多级页表的方式是非常适合的。
值得注意的是，虽然每级页表使用的index的位宽不尽相同，但是每级页表的每个entry的大小都等于处理器的字长，比如在64位系统中就是8个字节。index只是相当于数组下标，它的位宽决定的是这级页表中有多少个entries。以使用48位虚拟地址的ARMv8-A为例，最后一级页表PTE中存放的是PPN，只需要中间的48-12=36位，高16位和低12位都没有用到。
这些空余的位空间可以被作为各种flag标识利用起来，关于这些flag的使用，会在后续的文章中详细介绍。
多级页表使用现状
在现代32位处理器中，采用4KB的page大小，则虚拟地址中低12位为page offest，剩下高20位给页表，适合做成两级，每个级别占10个bit（10+10）。对于intel的PAE（Physical Address Extension）模式，支持32位虚拟地址（为了保持和普通32位系统的程序兼容性）和36位物理地址，采用三级页表（2+9+9）。对于64位处理器，intel的IA32-e（x86-64）和ARMv8-A最开始都是只使用低48位，因而剩下中间的36位给页表，采用四级页表，每个级别占9个bit（9+9+9+9）。
之前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】。
为什么支持48位虚拟地址的64位系统就要采用四级或者五级页表，而不是和32位系统一样采用两级页表呢？我们来试下如果采用两级页表会怎样。中间的36位若分给两级页表，则每级页表占18位（18+18），那么每级页表需要多达 
（262144）个entries。其实多级页表可理解位一种时间换空间的技术，所以设计每级页表具体占多大，就是一种时间和空间的平衡。
操作系统支持
为了支持处理器的四级页表模式，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实际选择的页表级数和处理器架构有关，PUD只会存在于使用四级页表的处理器上，在只使用二级页表的处理器上，则只有PGD和PTE，没有PMD。
多级页表访问优化
使用多级页表的方式对于减少页表自身占用的内存空间确实是非常有效的。然而，为此付出的代价就是增加了地址转换过程中对内存的访问次数，进而增加了转换时间。那在除了前面介绍的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
参考:
[1] Four-level page tables
[2] Five-level page tables
[3] intel官方手册《5-Level Paging and 5-Level EPT》
