Linux页表
Linux 页表实现
转载or借鉴：
[虚拟地址转换一] - 基本流程 - 知乎 (zhihu.com)
[虚拟地址转换二] - 具体实现 - 知乎 (zhihu.com)
[虚拟地址转换三] - 多级页表 - 知乎 (zhihu.com)
虚拟地址转换的基本流程
好处
在Linux，Windows等操作系统中，为什么不直接使用Physical Address（物理地址），而要用Virtual Address（虚拟地址）呢？
因为使用虚拟地址可以带来诸多好处：
在支持多进程的系统中，如果各个进程的镜像文件都使用物理地址，则在加载到同一物理内存空间的时候，可能发生冲突。
直接使用物理地址，不便于进行进程地址空间的隔离。
物理内存是有限的，在物理内存整体吃紧时，可以让多个进程通过分时复用的方法共享一个物理页面（某个进程需要保存的内容可以暂时swap到外部的disk/flash），这有点类似于多线程分时复用共享CPU的方式。
既然使用虚拟地址，就涉及到将虚拟地址转换为物理地址的过程，这需要MMU（Memory Management Unit）和页表（page table）的共同参与。
术语介绍
1.MMU
MMU是处理器/核（processer）中的一个硬件单元，通常每个核有一个MMU。MMU由TLB(Translation Lookaside Buffer)和table walk unit 组成。
2.Page Table
page table是每个进程独有的，是软件实现的，是存储在main memory（比如DDR）中的。
Address Translation
因为访问内存中的页表相对耗时，尤其是在现在普遍使用多级页表的情况下，需要多次的内存访问，为了加快访问速度，系统设计人员为page table设计了一个硬件缓存 - TLB，CPU会首先在TLB中查找，因为在TLB中找起来很快。
TLB之所以快**，一是因为它含有的entries的数目较少，二是TLB是集成进CPU的，它几乎可以按照CPU的速度运行**。
TLB访问流程：
如果在TLB中找到了含有该虚拟地址的entry（TLB hit），则可从该entry中直接获取对应的物理地址，否则就不幸地TLB miss了，就得去查找当前进程的page table（这里其实可能用到paging structure caches）。这个时候，组成MMU的另一个部分table walk unit就被召唤出来了，这里面的table就是page table。
硬：使用table walk unit硬件单元来查找page table的方式被称为hardware TLB miss handling，通常被CISC架构的处理器（比如IA-32）所采用。它要在page table中查找不到，出现page fault的时候才会交由软件（操作系统）处理。
软：与之相对的通常被RISC架构的处理器（比如Alpha）采用的software TLB miss handling，TLB miss后CPU就不再参与了，由操作系统通过软件的方式来查找page table。使用硬件的方式更快，而使用软件的方式灵活性更强。IA-64提供了一种混合模式，可以兼顾两者的优点。
如果在page table中找到了该虚拟地址对应的entry的p（present）位是1，说明该虚拟地址对应的物理页面当前驻留在内存中，也就是page table hit。找到了还没完，接下来还有两件事要做：
既然是因为在TLB里找不到才找到这儿来的，自然要更新TLB。
进行权限检测，包括可读/可写/可执行权限，user/supervisor模式权限等。如果没有正确的权限，将触发SIGSEGV（Segmantation Fault，段错误）。
如果该虚拟地址对应的entry的p位是0，就会触发page fault（页错误），可能有这几种情况：
这个虚拟地址被分配后还从来没有被access过（比如malloc之后还没有操作分配到的空间，则不会真正分配物理内存）。触发page fault后分配物理内存，也就是demand paging，有了确定的demand了之后才分，然后将p位置1。
对应的这个物理页面的内容被换出到外部的disk/flash了，这个时候page table entry里存的是换出页面在外部swap area里暂存的位置，可以将其换回物理内存，再次建立映射，然后将p位置1。
虚拟地址转换的具体实现
讲述关于在TLB中具体是怎么找的，在page table中又是怎么"walk"的问题。
假设当前CPU支持的虚拟地址是14位，物理地址是12位，page size为64字节（这里要说明一下，通常情况下呢，虚拟地址和物理地址的位数是一样的，但其实并不一定需要一样，因为本来就可以多个虚拟地址指向同一个物理地址嘛）。
不管是虚拟地址还是物理地址，因为最小管理单位都是page，在转换过程中，代表page内的偏移地址（offset）的低位bits部分是不需要参与的，需要转换的只是代表page唯一性标识的高位bits部分，称作page number。由此产生了4个概念：VPN（virtual page number），PPN（physical page number），VPO（virtual page offset）和PPO（physical page offset）
VPO和PPO占的bit位数为log2 P，p为page size大小，即64，因而VPO和PPO的值为6。因为所有pages都是同样大小的，所以VPO始终等于PPO。
虚拟地址中剩下的bit位就成了VPN，物理地址中剩下的bit位就成了PPN。
方式跟mit6.s081所述相近
虚拟地址转换之多级页表
若内存容量较大，按照常规的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在PT表中找到对应的PT entry，这个PT entry中存放的是就是物理页面号（PPN, Physical Page Number）了。
在多级页表系统中，其实每级页表都可以视为一种“虚拟地址”向“物理地址”的转换，只是这里的“虚拟地址”是待转换的虚拟地址的一个位域子集，而除了最后一级页表PTE是直接指向物理页面的，其他级别页表里的“物理地址”都是指向对应下一级页表的首地址。
多级页表使用现状：
在32位处理器中，采用4KB的page大小，则虚拟地址中低12位为page offest，剩下高20位给页表，分成两级，每个级别占10个bit（10+10）。为什么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（9+9+9+9）。
为什么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），那么每级页表需要多达 2^18（262144)个entries。其实多级页表可理解位一种时间换空间的技术，所以设计每级页表具体占多大，就是一种时间和空间的平衡。
多级页表访问优化：
使用多级页表的方式对于减少页表自身占用的内存空间确实是非常有效的。然而，为此付出的代价就是增加了地址转换过程中对内存的访问次数，进而增加了转换时间。那在除了前面介绍的TLB之外，还有哪些可以减少内存访问次数，加快地址转换的方法呢？
一个是使用大页（large page），一个是使用paging structure caches。
虚拟地址转换- large page/hugepage
使用large page（在linux中对应的概念叫hugepage）可以优化对多级页表的访问时间，那处理器硬件层面是如何实现large page的呢？
在页表的任何级别，指向下一级的指针可以为空，表示该范围内没有有效的虚拟地址。中间级别也可以有特殊条目（设置了page size flag），表明它们直接指向large page。
large page的使用可以减少页表的级数，也就减少了查找页表的内存访问次数，而且对于同样entries数目的TLB，可以扩大TLB对内存地址的覆盖范围，减小TLB miss的概率。此外，因为页表本身也要占用内存空间，减少页表的大小也可以节约那么一丢丢的内存。
在使用large page的系统中，可能存在4KB，2MB，1GB等不同大小的page共存的情况，这就需要不同的TLB支持。
当然，使用large page也会带来一些问题，比如：
由于各种内存操作基本都要求按照page对齐，比如一个可执行文件映射到进程地址空间，根据文件大小的不同，平均算下来会浪费掉半个page size的物理内存，使用large page的话这个消耗就显得比较大了。
系统运行一段时间后，会很难再有大块的连续物理内存，这时分配large page将会变的很困难，所以通常需要在系统初始化的时候就划分出一段物理内存给large page用（类似于DMA的内存分配），这样就减少了一些灵活性。
large page在换出到外部的flash/disk和从flash/disk换入物理内存的过程会比normal size的page带来更大的开销。
（linux本来好像是不会交换大页面的，如1GB这种页面，但是现在Linux好像进入大页交换的final step了）
虚拟地址转换 - paging structure caches
在多级页表系统中，TLB其实只是最后一级PTE的缓存（对于large pages的TLB则最后一级是PDE或者PDPTE，本文以下的讨论都是针对非large page的情况），这和在单级页表中是一样的。
多级页表的查找是一个串行的，链式的过程。试想一下，访问在虚拟地址空间里连续的两个pages（比如起始地址分别为"0x0000123456789000"和"0x000012345678A000"），而这两个pages的PGD entry, PUD entry, PMD entry都是一样的，只有PTE不一样。
难道在通过n次内存访问（n等于页表级数）查找到第一个page的物理页面号后，在访问相邻的（虚拟地址层面）第二个page时还需要再老老实实，一步一步的从PGD往下找？这对于在追求性能方面可谓无所不用其极的现代处理器来说，是不可接受的。
既然PTE都可以被缓存，那前面几级的PMD, PUD, PGD也应该可以被缓存吗？是的，以intel的x86-64架构为例，它支持PDE cache（使用64位虚拟地址的bits 47:21作为index/tag，对应linux里的PMD entry）, PDPTE cache（使用64位虚拟地址的bits 47:30作为index/tag，对应linux里的PUD entry）, PML4 cache（使用64位虚拟地址的bits 47:39作为index/tag，对应linux里的PGD entry）。
除了最后一级页表PTE的entry是直接指向page外，其他级的页表的entry都是指向下一级页表首地址的，因此这些级的页表被称为paging structure，所以PDE cache，PDPTE cache和PML4 cache被统称为paging structure caches。在ARM中，这些caches被称为table walk caches（名字应该是来自MMU里的table walk unit）。
如果发生TLB miss, 相当于PTE cache中没找到，那就
从PDE cache中找，如果找到了则获得对应PT页表的首地址，可继续在PT中索引到PTE，需要1次内存访问；
没找到再从PDPTE cache中找，如果找到了则获得对应PD页表的首地址，然后在PD->PT中索引，需要2次内存访问；
还没找到再从PML4 cache中找，如果找到了则获得对应PDPT页表的首地址，然后在PDPT->PD->PT中索引，需要3次内存访问；
PML4 cache中也没有的话，那只能去DRAM里按照PML4->PDPT->PD->PT找了，需要4次内存访问。
Linux中的页表实现
页表是软件实现的，但是页表的查找是MMU完成的，所以硬件定义了页表的实现规则，软件可以做的只有选择页表的级数，是否使用huge page以及填充对应的权限标志位。
数据结构：
还是三级页表，但是添加了很多东西：
页表PGD的首地址是放在mm_struct中的，pgd_offset(), pmd_offset(), pmd_offset()分别用于从虚拟（线性）地址中提取查找PGD, PMD和PTE表所需的index。
不同的处理器支持的页表级数是不一样的，比如IA-32只支持2级，x64支持4级甚至5级，而Linux作为一个通用的操作系统，需要兼容不同的硬件平台，如果针对每种硬件平台进行不同的页表实现，那就太麻烦了。试想，如果Linux采用2级页表，对IA-32到是没问题，对x64就无能为力了，那如果Linux统一采用4级或5级页表，对x64的配合倒是刚刚好，那对IA-32呢？
其实不难，只要把表示PUD中PMD entry个数的"PTRS_PER_PMD"和表示PMD中PTE entry个数的"PTRS_PER_PMD"都设为1就可以了，相当于把中间两级的PUD和PMD折叠了起来，PGD就等同于直接指向PTE了。
进程页表的建立
内核加载一个进程后，需要为该进程创建属于它的页表。pgd_alloc(), pmd_alloc()和pte_alloc()分别用于创建PGD, PMD和PTE。
因为页表本身也是放在内存中的， 其本质上是由若干物理pages组成的，分配物理内存本身就是耗时的，加之在分配过程中需要关中断，而页表的创建和销毁又是很频繁的操作，而且现在的页表多达四级甚至五级，所以整个过程的系统开销是不可小觑的。
那怎么加速这一过程呢？加速最常用的就是cache啦，具体的做法是把要提供给页表创建的物理pages放到一组叫"quicklist"的链表中，以后销毁页表释放的页就往这个quicklist里送，创建页表需要的页就直接从这个quicklist里找，其实就是一个专用的freelist（原理和slab差不多），当然要比去整个物理内存的free pages list分配要快啦。
如果建立了新的映射关系，则需要调用mk_pte()创建一个新的页表项，因为页表描述符由物理页面号和权限控制位组成，所以新建页表项的工作主要就是填充这两部分内容，组装完成就可以调用set_pte()插入到对应的页表中去了。
内核页表的建立
内核刚被加载的时候，paging还没有打开，还工作在实模式。x86要求在打开paging之前（置位CR0寄存器的PG位），软件需要至少设置一个page directory和一个page table，从Linux实现的角度，就是至少要有一个PGD和一个PTE。
试想，打开paging后，操作系统给出的地址对于CPU来说就是虚拟地址了，这时如果还没有任何的页表，怎么去获得物理地址，进而操作物理内存呢？
为此，Linux采用的做法是：假设内核初始化时需要用到的物理内存不超过8MB（0x00000000到0x007fffff），若一个page为4KB，则这8MB内存共含有2048个pages，需要2048个PTE来映射。
一个PTE占4个字节，因此一共需要8KB的page（也就是2个page）来存储，这2个用作PTE页表的page用pg0和pg1表示，分别放在物理地址为"0x00102000"和"0x00103000"的位置。
而PGD则用一个叫"swapper_pg_dir"的变量表示，放在物理地址为"0x00101000"的位置，大小为1个page。因为这个临时页表的目的就是要让这8MB物理内存在实模式和打开paging的保护模式下都可以被访问，因此需要建立2个实模式下PGD entries的和2个用于保护模式的PGD entries。实模式下本来是没有什么虚拟地址的概念的，但也可以理解为是一种虚拟地址等于物理地址的特殊映射。
页表是使用虚拟地址作为index的，在32位两级页表中，高10位是PGD表的index，对于"0x00000000"到"0x007fffff"的地址，index就是0和1。对于内核空间来说，"0x00000000"到"0x007fffff"的物理地址在保护模式下对应的虚拟地址为"0xc0000000"到0xc07fffff，高10位是"1100000000b和1100000001b"，换算成10进制就是768和769。
实模式下的工作完成之后，就可以将"swapper_pg_dir"的物理地址放入CR3，置PG位为1，进入paging保护模式了。这时接力棒就叫到了paging_init()的手中，由它来完成正式的内核页表（被称为master kernel page table）的创建了。master kernel page table中PGD的首地址还是存在swapper_pg_dir变量中的。
Last updated
