Linux 页表初探

在虚拟内存中，页表是个映射表的概念, 即从进程能理解的线性地址( linear address ) 映射到存储器上的物理地址( phisical address )。

当一个进程在 CPU 上运行时，CPU 并不是直接访问物理内存地址的，而是通过虚拟地址空间间接访问物理内存的。

CPU 使用的地址都是虚拟地址，而数据存放在物理内存中，这个时候需要把虚拟地址转换为实际的物理地址，然后根据物理地址从物理内存中获取数据。

在操作系统中，虚拟地址转换是通过一个称为主存管理单元（Memory Management Unit, MMU）的硬件来提供转换的。MMU就是通过页表来进行查找进行转换成物理地址的。

本文对以 32 为逻辑地址空间的二级页表进行分析。

二级页表

系统采用二级页表时，会把 32 位虚拟地址空间分为 3 个部分，如下：

页目录表也是占用一个标志的 4k 页，由于每个页目录项占用 4 个字节，因此页目录表共有 1024 个表目录项（Page Directory Entry, PDE）。

页目录表中的每个页目录项都记录一个页表的物理页地址，物理页地址是指页的物理地址。而每个页表中也是有 1024 个页表项（Page Table Entry，PTE），每个页表项中也是一个物理页地址，最终数据写在这个页表项中指定的物理页内。 而12 位的偏移量就是用来寻址该物理页中某个具体的存储单元。

每个页表项保存的是一个物理页框的物理地址，而每个页框的基地址为 4k 的整数倍，因此物理地址的低12位无用的，所以把物理地址的低 12 位设置一些标志位。

页表项保存的地址如下：

其中，页框地址( PAGE FRAME ADDRESS )指定了一页内存的物理起始地址。因为内存页位于 4K 地 址边界上，所以其低 12 比特总是 0，因此表项的低 12 比特可挪作它用。

在一个页目录表中，表项的页框地址是一个页表的起始地址；在第二级页表中，页表项的页框地址则包含期望内存操作的物理内存页 地址。

图中的存在位（PRESENT – P）确定了一个页表项是否可以用于地址转换过程。P=1 表示该项可用。当目录表项或第二级表项的 P=0 时，则该表项是无效的，不能用于地址转换过程。此时该表项的所有其他比特位都可供程序使用；处理器不对这些位进行测试。

当 CPU 试图使用一个页表项进行地址转换时，如果此时任意一级页表项的 P=0，则处理器就会发出 页异常信号。此时缺页中断异常处理程序就可以把所请求的页面映射和加入到物理内存中，并且导致异 常的指令会被重新执行。

已访问（Accessed – A）和已修改（Dirty – D）比特位用于提供有关页使用的信息。除了页目录项中的已修改位，这些比特位将由硬件置位，但不复位。页目录项和页表项的小区别在于页表项有个已写位 D（Dirty），而页目录项则没有。

在对一页内存进行读或写操作之前，CPU 将设置相关的目录和二级页表项的已访问位。在向一个二 级页表项所涵盖的地址进行写操作之前，处理器将设置该二级页表项的已修改位，而页目录项中的已修 改位是不用的。当所需求的内存超出实际物理内存量时，内存管理程序就可以使用这些位来确定哪些页 可以从内存中取走，以腾出空间。内存管理程序还需负责检测和复位这些比特位。

读/写位（Read/Write – R/W）和用户/超级用户位（User/Supervisor – U/S）并不用于地址转换，但用 于分页级的保护机制，是由 CPU 在地址转换过程中同时操作的。

经过上述分析，二级页表地址转换原理是将 32 位虚拟地址拆分成高 10 位，中间10 位，低 12 位三个部分。它们的作用是：高 10 位作为页表的索引，用于在页目录表中定位一个页目录项 PDE，页目录项中有页表的物理地址，也就是定位到某个页表。中间 10 位作为物理页的索引，用于在页表内定位到某个页表项 PTE，页表项中有分配的物理页地址，也就是定位到了某个物理页。低 12 位作为页内偏移量用于在已经定位到的物理页内寻址。

转换过程如下：

1. 用虚拟地址的高10位乘以4，作为页目录表内的偏移地址，加上页目录表的物理地址，所得的和，便是页目录项的物理地址。读取该页目录项，从中获取到页表的物理地址。
2. 用虚拟地址的中间10位乘以4，作为页表内的偏移寻址，加上在第一步中得到的页表物理地址所得的和，便是页表项的物理地址。读取该页表项，从中获取分配的物理页地址。
3. 虚拟地址的高10位和中间10位分别是PDE和PTE的索引值，所以它们需要乘以4。但低12位就不是索引值啦，其表示的范围为0~0xfff，作为页内偏移最合适，所以虚拟地址的低12位加上第二步得到的物理页地址，所得到的和便是最终转换的物理地址。

上述中的页目录表和页表都存在于物理内存中，每个表中项保存的地址均为物理地址。二级页表占用的内存示意图如下：

每个进程均有一个页表，进程的页表保存在进程的 pgd 字段中

struct mm_struct {
....
pgd_t * pgd;
....
}

该字段为进程的页全局目录的虚拟地址，当进程切换时，CPU 会把下一个进程页表地址加载到CR3寄存器中，因此加载时会把 pgd 字段中的虚拟地址转换为物理地址。

asm volatile("movq %0,%%cr3" :: "r" (next->pgd) : "memory");

程序被第一次加载调度执行时有个入口地址，该入口地址为虚拟地址，当cpu得到该程序的入口虚拟基地址执行时，会通过页表（会先查找转换后援缓冲器TLB，又称块表，TLB是对页表的缓存，能够快速查找，TLB不命中，才会查页表）查找该虚拟地址对应的物理地址，然后通过物理地址获取相应的数据，程序也就这样一步一步的往下执行。

页面换入和换出

我们知道，物理内存是宝贵且有限的。当进程运行的越来越多，内存使用量也就越来越多。这个时候会导致内存紧缺。为了解决这种内存不足情况，操作系统会采用一定的页面替换算法把暂时不用的物理内存替换出去，保存到磁盘（交换设备）中，为其他急用的信息腾出空间，到需要时候再从磁盘上读进来。

在分析页面换入换出前，先了解下物理内存页面的管理。

为了方便物理内存页面的管理，每个内存页面都对应一个 page 数据结构。在系统初始化阶段，内核根据检测到的物理内存的大小，为每一个页面都建立一个 page 结构，形成一个page结构数组，并使一个全局量 mem_map 指向这个数组。同时，又按需将这些页面拼合成物理地址连续的许多内存页面“块”，在根据块的大小建立起若干“管理区”（zone），而在每个管理区中则设置一个空闲块列表，以便物理内存页面的分配使用。

与此类似，交换设备（通常是磁盘，也可是普通文件）的每个物理页面也要在内存中有个相应的数据结构，实际上只是一个计数，表示该页面是否已被分配使用，以及有几个用户在共享这个页面。对盘上页面的管理是按文件或磁盘设备来进行的。内核中定义了一个 swap_info_struct 数据结构，用以描述和管理用于页面交换的文件或设备。

struct swap_info_struct {
unsigned int flags;
int prio; /* swap priority */
struct file *swap_file;
struct block_device *bdev;
struct list_head extent_list;
struct swap_extent *curr_swap_extent;
unsigned old_block_size;
unsigned short * swap_map;
unsigned int lowest_bit;
unsigned int highest_bit;
unsigned int cluster_next;
unsigned int cluster_nr;
unsigned int pages;
unsigned int max;
unsigned int inuse_pages;
int next; /* next entry on swap list */
};

其中的指针 swap_map 指向一个数组，该数组中的每个无符号短整型即代表盘上（或普通文件中）的一个物理页面，而数组的下标则决定了该页面在盘上或文件中的位置。数组的大小取决于 pages，它表示该页面交换设备或文件的大小。设备上（或文件中，设备也是一个文件）的第一个页面，也即是 swap_map[0] 所代表的那个页面是不用于页面交换的，它包括了该设备或文件自身的一些信息以及表明哪些页面可供使用的位图。这些信息最初是把该设备格式化成页面交换区时设置的。根据不同页面交换区格式（以及版本），还有一些其他的页面也不提供页面交换使用。这些页面都集中在开头和结尾的地方，所以 swap_info_struct 中的 lowest_bit 和 hightest_bit 就说明文件中从什么地方开始到什么地方为止是提供页面交换使用的。另一个字段max则表示该设备或文件中最大的页面号，也就是设备或文件的物理大小。

Linux 内核允许使用多个页面交换设备（或文件），所以在内核中建立了一个 swap_info_struct 结构数组 swap_info。

static struct swap_info_struct swap_info[MAX_SWAPFILES];

就像通过 pte_t 数据结构（页面表项）将物理内存页面与虚拟页面建立联系一样，盘上页面也有这么一个 swp_entry_t 数据结构。

typedef struct {
unsigned long val;
} swp_entry_t;

一个 swp_entry_t 结构实际上只是一个 32 位无符号整数，这个整数分成3部分：

offset 表示页面在一个磁盘设备或文件中的位置，也就是文件中的逻辑页面号；而type则是指该页面在哪一个文件中，是个序号（一个可以容纳127个这样的文件，但实际上视系统的配置而定，远小于127）。

swp_entry_t 和 pte_t 两种数据结构大小相同，关系非常密切。当一个页面在内存中时，页面表中的表项pte_t的最低位P标志为1，表示页面在内存中，而其余各位指明物理内存页面的地址及页面的属性。当一个页面在磁盘上时，则相应的页面表项不再指向一个物理内存页面，而是变成了一个 swp_entry_t 表项，指示着这个页面的去向。由于此时其最低位为 0，表示页面不在内存，所以 CPU 中的 MMU 单元对其余各位都忽略不顾，而留待系统软件自己来加以解释。在 Linux 内核中，就用它来唯一地确定一个页面在盘上的位置，包括在哪一个文件或设备，以及页面在此文件中的相对位置。

因此，当页面在内存时，页面表中的相应表项确定了地址的映射关系；当页面不在内存中，则指明了物理页面的去向和所在。

在页面交换中，只有映射到用户空间的页面才会被换出，而内核，即系统空间的页面不在此列。在内核中可以访问所有的物理页面，换言之所有的物理页面在系统空间中都是有映射的。所谓“用户空间的页面”，是指在至少一个进程的用户空间中有映射的页面，反之则为（只能有）内核使用的页面。

按页面的内容和性质，用户空间的页面有如下几种：

• 普通的用户空间页面，包括进程的代码段、数据段、堆栈段，以及动态分配的“存储堆”。其中有些页面从用户程序及进程的角度看是静态的（如代码段），但从系统的角度来看仍是动态分配的。
• 通过系统调用 mmap（）映射到用户空间的已打开文件的内容。
• 进程间的共享内存区。

这些页面既涉及分配、使用和回收，也涉及页面的换入和换出。

当系统挑选出若干内存页面准备换出时，将这些页面的内容写入相应的磁盘页面中，并且将相应的页面表项的内容改成指向盘上页面（P标志位为0，表示页面不在内存中），但是所占据的内存页并不立即释放，而是将其 page 结构留在一个“暂存”（cache）队列（或缓冲队列）中，只是使其从“活跃状态”转入了“不活跃状态”。至于其最后释放，则推迟到以后有条件地进行。这样，若在一个页面被换出以后立即又受到访问而发生异常，就可以从物理页面的暂存队列中找回相应的页面，再次为之建立映射。这样就不需要从盘上读取了。

换入换出流程：

当 CPU 把虚拟地址发给 MMU 进行地址转换时，MMU 发现页表中没有到物理内存的映射，则发生缺页异常中断，缺页异常程序根据虚拟地址从盘上找到相应的盘页面，然后从物理内存中查找一个空闲的内存页，若找到，则把盘页面内容加载到物理内存中，然后修改页表。若找不到空间的内存页，则根据页面替换算法把一些物理内存页换出到磁盘中，然后修改替换出去的内存页对应的页表项，页表项内容指向替换到磁盘的位置（swp_entry_t ）。

当访问被替换出去的内存时，通过查找页表，根据表项pte_t的最低位P标志位（为0，表示页面不在内存），则把pte_t指向的地址转换成swp_entry_t，然后从磁盘中加载换出的内存页。

请求分页虚拟地址转换流程总结

• MMU接收CPU传过来的逻辑地址后并自动按页面大小把它从某位起分解成2部分：页号和页内偏移;
• 以页号为索引搜索块表TLB；
• 若命中，立即送出页框号，并与页内偏移量拼接成物理地址，然后进行访问权限检查，若获得通过，进程就可以访问物理地址；
• 若不命中，由硬件以页号为索引搜索进程页表，页表基地址由硬件寄存器CR3 指出；
• 若在页表中找到此页面，说明所反问的页面已在主存中，可送出页框号，并与页内偏移量拼接成物理地址，然后进行访问权限检查，若获得通过，进程就可以访问物理地址，同时要把这个页面信息装入块表 TLB，以备再次访问；
• 若发现页表中对应的页面失效或没有，MMU 发出缺页中断，请求操作系统进行处理，MMU 工作到此结束。

MMU 发现缺页并发出缺页中断，存储管理接收控制，进行缺页中断处理的过程如下：

1. 挂起请求的缺页进程；
2. 根据页表项，找到存放此页的磁盘物理地址；
3. 查看主存是否有空闲页，若有则找出，修改主存管理表和相应页表项的内容，转到步骤6；
4. 如果主存中无空闲页框，按照页面替换算法选择淘汰页面，检查其是否被写过或修改过，若否转到步骤6；若是转到步骤5；
5. 淘汰页面被写过或修改过，将其内容写回磁盘的原先位置；
6. 进行调页，把页面装入主存所分配的页框中，同时修改进程页表项；
7. 返回进程断点，重新启动被中断的指令。