2.1.4 页式寻址实例
我们以Linux 0.10版本的内核为例，具体介绍一下页式内存管理机制。Linux 0.10版本的内核还不支持通过BIOS读取系统内存信息，只是硬编码了一个在当时看起来合理的尺寸16MB。Linux 0.10版的内核尚未采用平坦内存模型，不同程序有不同的地址空间，大家共享同一个页目录（1级页表），不同程序虽使用同一个页目录中不同的页目录项，但是有各自的页表（2级页表）。内核将1MB以下的内存地址空间留给内核自己及BIOS和显卡使用，从1MB开始，供所有任务使用，共15MB，每个页面大小是4KB，15MB物理内存被划分为15×1024×1024/4096=3840个页面，如图2-5所示。当然，1MB以下的内存依然使用页式管理，在内核初始化时（代码在head.s中）已经建好了页面映射关系，只不过这1MB内存属于内核和BIOS等专用，不能再将它们分配给其他任务使用。
图2-5 Linux 0.10版本内核内存使用概况
内核定义了一个数组mem_map记录页面的使用情况：
linux-0.10/mm/memory.c
#define LOW_MEM 0x100000
#define PAGING_MEMORY (15*1024*1024)
#define PAGING_PAGES (PAGING_MEMORY>>12)
static unsigned char mem_map [ PAGING_PAGES ] = {0,};
Linux 0.10版的内核只是使用一字节来记录一个物理页面的信息，从1.3.50版本开始，内核定义了一个更直观的结构体page来记录物理页面的信息，数组mem_map的元素也不再仅仅是一字节了，而是一个结构体page的实例：
linux-1.3.50/include/linux/mm.h
typedef struct page {
unsigned int count;
unsigned dirty:16,
age:6,
unused:9,
reserved:1;
unsigned long offset;
……
} mem_map_t;
extern mem_map_t * mem_map;
每次访存时，MMU首先从TLB中查找是否缓存了虚拟地址到物理地址的映射，如果没有，则从cr3寄存器中取出页表的根地址，即1级表的地址，也称为页目录（Page Directory），遍历页表，将虚拟机地址转换为物理地址。Linux 0.10版本的内核将页目录分配在内存起始位置，即0字节处。这里页表覆盖了IVT，但是此时已经进入了保护模式，保护模式使用IDT而不使用IVT，IVT已经完成它的任务了：
linux-0.10/boot/head.s
xorl %eax,%eax /* pg_dir is at 0x0000 */
movl %eax,%cr3 /* cr3 - page directory start */
当缺页异常发生时，将调用IDT中缺页异常处理函数：
linux-0.10/ mm/page.s
.globl _page_fault
_page_fault:
…
movl %cr2,%edx
pushl %edx
……
call _do_no_page
……
linux-0.10/ mm/memory.c
void do_no_page(unsigned long error_code,unsigned long address)
{
unsigned long tmp;
if (tmp=get_free_page())
if (put_page(tmp,address))
return;
do_exit(SIGSEGV);
}
缺页异常处理函数从cr2寄存器中取出线性地址，传递给函数do_no_page。do_no_page首先调用get_free_page申请一个空闲页面，然后调用put_page填充页表。
1.获取空闲页面
我们首先讨论获取空闲页面的函数get_free_page。get_free_page在mem_map中从后向前，查找值为0的项，即没有被占用的物理页面。然后将物理内存页面清零，并将物理页面的地址返回给调用者：
linux-0.10/ mm/memory.c
00 unsigned long get_free_page(void)
01 {
02 register unsigned long __res asm("ax");
03
04 __asm__("std ; repne ; scasb\n\t"
05 "jne 1f\n\t"
06 "movb $1,1(%%edi)\n\t"
07 "sall $12,%%ecx\n\t"
08 "addl %2,%%ecx\n\t"
09 "movl %%ecx,%%edx\n\t"
10 "movl $1024,%%ecx\n\t"
11 "leal 4092(%%edx),%%edi\n\t"
12 "rep ; stosl\n\t"
13 "movl %%edx,%%eax\n"
14 "1:"
15 :"=a" (__res)
16 :"0" (0),"i" (LOW_MEM),"c" (PAGING_PAGES),
17 "D" (mem_map+PAGING_PAGES-1)
18 :"di","cx","dx");
19 return __res;
20 }
函数get_free_page的精华在第4行代码。get_free_page使用指令scasb来找到数组mem_map中内容为0的项，scasb比较al寄存器的内容和edi寄存器指向的内存储存的字节，比较之后，edi寄存器根据EFLAGS寄存器中DF标志的设置自动递增或递减。如果DF标志为0，则edi寄存器递增；如果DF标志为1，则edi寄存器递减。第4行代码中，指令std设置了EFLAGS寄存器中的DF标识位，所以这里scasb每执行一次比较后，就将edi减去1字节。
scasb比较的2个寄存器al和edi分别在第1个约束和第5个约束中进行了初始化。第1个约束见第16行代码，这里使用了一种在内联汇编中称为Matching(Digit)constraints的约束方式，表示使用和第0个操作数相同的约束。第0个操作数的约束为使用eax寄存器引用变量__res，见第15行代码，结合到第1个约束上，就相当于“a”(0)，即将eax寄存器初始化为0。第5个约束，见第17行代码，这个约束将edi寄存器初始化为指向mem_map数组的末尾。
在scasb指令前，使用前缀repne修饰scasb，表示重复执行scasb。
综上，第4行代码的意义就是从数组mem_map的最后一个元素开始，一直到找到值为0的元素，或者计数寄存器ecx为0为止。计数寄存器ecx在输入约束部分初始化为页面数PAGING_PAGES，即数组mem_map的大小，见第16行代码。
如果找不到空闲的页面，如第5行代码所示，则直接跳到标号1处，返回0。
在找到空闲页面后，首先将mem_map中对应这个页面的字节设置为1，表示页面被占用了，见第6行代码。但是，为什么内存地址是edi寄存器加1呢？这和指令scasb有关。刚刚提到在执行完比较操作后，scasb会将edi减1，将指向数组mem_map中下一个准备比较的字节，因此需要将这个多减的1加回来。
然后就是计算获取的空闲页面的物理地址了。计数寄存器ecx初始化时指向最后一个页面，然后每比较一次就减1，所以在成功找到空闲页面后，ecx中记录的就是空闲页面序号。这个序号乘以页面尺寸，即4KB（见第7行代码），然后加上内存开始划分页面的起始位置，即LOW_MEM（见第8行代码），就是页面的物理地址了。第8行代码中的%2指代的就是输入约束中的立即数LOW_MEM。从第9行和第13行代码可知，页面起始地址最后会保存到eax寄存器，而输出部分的约束要求编译器将eax寄存器中的内容最后保存到变量__res，这个变量中的内容正是函数get_free_page返回的空闲页面地址。
在返回页面地址之前，函数get_free_page清除了空闲页面的垃圾内容，见第10～12行代码。这里使用stosl指令将eax寄存器的内容覆盖到寄存器edi指向的内存上，这也是第9行代码不直接将页面地址直接保存到eax寄存器的原因，因为这里还要使用eax寄存器中的0值。stosl指令的前缀是rep，所以这是个无条件循环，直到计数寄存器ecx的内容为0为止。在第10行代码中，计数寄存器ecx被设置为1024，stosl每次写4个字节，所以1024次循环正好访问了4096字节大小的页面。从页面的高地址处开始清零，所以第11行代码将edi寄存器指向了页面的末尾地址。
2.更新页表
申请到了空闲的物理页面后，缺页异常函数需要更新页表，这是通过函数put_page实现的：
linux-0.10/ mm/memory.c
01 unsigned long put_page(unsigned long page,unsigned long address)
02 {
03 unsigned long tmp, *page_table;
04 ……
05 page_table = (unsigned long *) ((address>>20) & 0xffc);
06 if ((*page_table)&1)
07 page_table = (unsigned long *)
08 (0xfffff000 & *page_table);
09 else {
10 if (!(tmp=get_free_page()))
11 return 0;
12 *page_table = tmp|7;
13 page_table = (unsigned long *) tmp;
14 }
15 page_table[(address>>12) & 0x3ff] = page | 7;
16 return page;
17 }
首先，我们来看一下第5行代码。直观感觉，这行代码是取页目录项的索引，但是这里只是将发生缺页异常的线性地址右移了20位。我们知道，线性地址的高10位用于页目录项的索引，所以理论上应该右移22位才对。我们的认知没错，只不过这里略去了一步操作，所以容易让人感到费解。这里是直接计算出了最终页目录项的地址，一个页目录项占据4字节，所以索引乘以4，就得出了索引所在页目录项相对于页目录基址的偏移。乘以4可以使用左移表示，所以下面的公式：
(address >> 22) << 2
最终简化为：
(address >> 20)
经过简化后，只是右移了20位。页目录中的每个表项是4字节的，因此，需要将地址按照4字节对齐到页目录项的起始位置，所以需要将最后2位清零，因此引出了0xffc：
(address>>20) & 0xffc
上述公式的结果就是索引对应的页目录项相对于页目录的基址的偏移。假设页目录的基址为pg_dir，那么这个页目录项的内存地址就是：
pg_dir + (address>>20) & 0xffc
而0.10内核的页目录在内存地址0处：
linux-0.10/boot/head.s
xorl %eax,%eax /* pg_dir is at 0x0000 */
movl %eax,%cr3 /* cr3 - page directory start */
即pg_dir为0，那么最终页目录项的内存地址就是偏移地址：
(address>>20) & 0xffc
对这个地址取值，如第5行代码所示，就读取了页目录项的内容。页目录项和页表项的格式如图2-6所示，这里略去了一些和代码不相关的属性。
图2-6 页目录项和页表项的格式
页目录项和页表项的格式大部分都很相似，页目录项中的第12～31位为指向下级页表的基址，页表项的第12～31位指向实际的物理页面。其中P位表示表项是否存在，读、写位（Read/Write，R/W）和用户、超级用户位（User/Supervisor，U/S）用于页级的保护机制。
第6行代码判断页目录项是否存在。如果页目录项存在，则读出页目录项中下级页表的基址，见第7～8行代码。否则，申请一个页面作为下级页表，同时更新页目录项，将新申请的下级页表基址填入页目录项，设置相关属性位，比如将P位设置为1，表示页目录项有效，见第10～13行代码。
到这里，无论页表是本来就已经存在，还是新申请的，最后需要做的就是使用新申请的物理页面更新相应的页表项。线性地址的中间10位，即第12～21位用于索引页表项，第15行代码就是设置相应的页表项指向新申请的空闲物理页面地址，更新页表项的相关属性。