超越容量的界限

现代操作系统不使用分段还是有一定的道理的. 有研究表明, Google数据中心中的1000台服务器在7分钟内就运行了上千个不同的程序, 其中有的是巨大无比的家伙(Google内部开发程序的时候为了避免不同计算机上的动态库不兼容的问题, 用到的所有库都以静态链接的方式成为程序的一部分, 光是程序的代码段就有几百MB甚至上GB的大小, 感兴趣的同学可以阅读这篇文章), 有的只是一些很小的测试程序. 让这些特征各异的程序都占用连续的存储空间并不见得有什么好处: 那些巨大无比的家伙们在一次运行当中只会触碰到很小部分的代码, 其实没有必要分配那么多内存把它们全部加载进来; 另一方面, 小程序运行结束之后, 它占用的存储空间就算被释放了, 也很容易成为"碎片空洞" - 只有比它更小的程序才能把碎片空洞用起来. 分段机制的简单朴素, 在现实情况中也许要付出巨大的代价.

事实上, 我们需要一种按需分配的虚存管理机制. 之所以分段机制不好实现按需分配, 就是因为段的粒度太大了, 为了实现这一目标, 我们需要反其道而行之: 把连续的存储空间分割成小片段, 以这些小片段为单位进行组织, 分配和管理. 这正是分页机制的核心思想.

在分页机制中, 这些小片段称为页面, 在虚拟地址空间和物理地址空间中也分别称为虚拟页和物理页. 分页机制做的事情, 就是把一个个的虚拟页分别映射到相应的物理页上. 显然, 这一映射关系并不像分段机制中只需要一个段基址寄存器就可以描述的那么简单. 分页机制引入了一个叫"页表"的结构, 页表中的每一个表项记录了一个虚拟页到物理页的映射关系, 来把不必连续的页面重新组织成连续的虚拟地址空间. 因此, 为了让分页机制支撑多任务操作系统的运行, 操作系统首先需要以物理页为单位对内存进行管理. 每当加载程序的时候, 就给程序分配相应的物理页(注意这些物理页之间不必连续), 并为程序准备一个新的页表, 在页表中填写程序用到的虚拟页到分配到的物理页的映射关系. 等到程序运行的时候, 操作系统就把之前为这个程序填写好的页表设置到MMU中, MMU就会根据页表的内容进行地址转换, 把程序的虚拟地址空间映射到操作系统所希望的物理地址空间上.

i386是x86史上首次引进分页机制的处理器, 它把物理内存划分成以4KB为单位的页面, 同时也采用了二级页表的结构. 为了方便叙述, i386给第一级页表取了个新名字叫"页目录". 虽然听上去很厉害, 但其实原理都是一样的. 每一张页目录和页表都有1024个表项, 每个表项的大小都是4字节, 除了包含页表(或者物理页)的基地址, 还包含一些标志位信息. 因此, 一张页目录或页表的大小是4KB, 要放在寄存器中是不可能的, 因此它们要放在内存中. 为了找到页目录, i386提供了一个CR3(control register 3)寄存器, 专门用于存放页目录的基地址. 这样, 页级地址转换就从CR3开始一步一步地进行, 最终将虚拟地址转换成真正的物理地址, 这个过程称为一次page walk.

                                                              PAGE FRAME
              +-----------+-----------+----------+         +---------------+
              |    DIR    |   PAGE    |  OFFSET  |         |               |
              +-----+-----+-----+-----+-----+----+         |               |
                    |           |           |              |               |
      +-------------+           |           +------------->|    PHYSICAL   |
      |                         |                          |    ADDRESS    |
      |   PAGE DIRECTORY        |      PAGE TABLE          |               |
      |  +---------------+      |   +---------------+      |               |
      |  |               |      |   |               |      +---------------+
      |  |               |      |   |---------------|              ^
      |  |               |      +-->| PG TBL ENTRY  |--------------+
      |  |---------------|          |---------------|
      +->|   DIR ENTRY   |--+       |               |
         |---------------|  |       |               |
         |               |  |       |               |
         +---------------+  |       +---------------+
                 ^          |               ^
+-------+        |          +---------------+
|  CR3  |--------+
+-------+

我们不打算给出分页过程的详细解释, 请你结合i386手册的内容和课堂上的知识, 尝试理解i386分页机制, 这也是作为分页机制的一个练习. i386手册中包含你想知道的所有信息, 包括这里没有提到的表项结构, 地址如何划分等.

页级转换的过程并不总是成功的, 因为i386也提供了页级保护机制, 实现保护功能就要靠表项中的标志位了. 我们对一些标志位作简单的解释:

• present位表示物理页是否可用, 不可用的时候又分两种情况:
  1. 物理页面由于交换技术被交换到磁盘中了, 这就是你在课堂上最熟悉的Page fault的情况之一了, 这时候可以通知操作系统内核将目标页面换回来, 这样就能继续执行了
  2. 进程试图访问一个未映射的线性地址, 并没有实际的物理页与之相对应, 因此这就是一个非法操作咯
• R/W位表示物理页是否可写, 如果对一个只读页面进行写操作, 就会被判定为非法操作
• U/S位表示访问物理页所需要的权限, 如果一个ring 3的进程尝试访问一个ring 0的页面, 当然也会被判定为非法操作

和分段机制相比, 分页机制更灵活, 甚至可以使用超越物理地址上限的虚拟地址. 现在我们从数学的角度来理解这两点. 撇去存储保护机制不谈, 我们可以把这分段和分页的过程分别抽象成两个数学函数:

  y = seg(x) = seg.base + x
  y = page(x)

可以看到, seg()函数只不过是做加法. 如果仅仅使用分段机制, 我们还要求段级地址转换的结果不能超过物理地址上限:

   y = seg(x) = seg.base + x < PMEM_MAX
=> x < PMEM_MAX - seg.base
=> x <= PMEM_MAX

我们可以得出这样的结论: 仅仅使用分段机制, 虚拟地址是无法超过物理地址上限的. 而分页机制就不一样了, 我们无法给出page()具体的解析式, 是因为填写页目录和页表实际上就是在用枚举自变量的方式定义page()函数, 这就是分页机制比分段机制灵活的根本原因. 虽然"页级地址转换结果不能超过物理地址上限"的约束仍然存在, 但我们只要保证每一个函数值都不超过物理地址上限即可, 并没有对自变量的取值作明显的限制, 当然自变量本身也就可以比函数值还大. 这就已经把分页的"灵活"和"允许使用超过物理地址上限"这两点特性都呈现出来了.

i386采用段页式存储管理机制. 不过仔细想想, 这只不过是把分段和分页结合起来罢了, 用数学函数来理解, 也只不过是个复合函数:

paddr = page(seg(swaddr))

而"虚拟地址空间"和"物理地址空间"这两个在操作系统中无比重要的概念, 也只不过是这个复合函数的定义域和值域而已.

最后, 支持分页机制的处理器能识别什么是页表吗? 我们以一个页面大小为1KB的一级页表的地址转换例子来说明这个问题:

pa = (pg_table[va >> 10] & ~0x3ff) | (va & 0x3ff);

可以看到, 处理器并没有表的概念: 地址转换的过程只不过是一些访存和位操作而已. 这再次向我们展示了计算机的本质: 一堆美妙的, 蕴含着深刻数学道理和工程原理的... 门电路! 然而这些小小的门电路操作却成为了今天多任务操作系统的基础, 支撑着千千万万程序的运行, 真不愧是人类的文明.

加入PTE

在AM的模型中, 由PTE模块来负责提供存储保护的能力. 为了在Nanos-lite中实现一个多任务操作系统, 我们需要在NEMU和AM中添加PTE的支持. 我们的第一个目标是首先让仙剑奇侠传运行在分页机制上, 然后再考虑多任务的支持.

准备内核页表

由于页表位于内存中, 但计算机启动的时候, 内存中并没有有效的数据, 因此我们不可能让计算机启动的时候就开启分页机制. 操作系统为了启动分页机制, 首先需要准备一些内核页表. 框架代码已经为我们实现好这一功能了(见nexus-am/am/arch/x86-nemu/src/pte.c的_pte_init()函数). 只需要在nanos-lite/src/main.c中定义宏HAS_PTE, Nanos-lite在初始化的时候首先就会调用init_mm()函数(在nanos-lite/src/mm.c中定义)来初始化MM. 这里的MM是指存储管理器(Memory Manager)模块, 它专门负责分页相关的存储管理.

目前初始化MM的工作有两项, 第一项工作是将TRM提供的堆区起始地址作为空闲物理页的首地址, 将来会通过new_page()函数来分配空闲的物理页. 第二项工作是调用AM的_pte_init()函数, 填写内核的页目录和页表, 然后设置CR3寄存器, 最后通过设置CR0寄存器来开启分页机制. 这样以后, Nanos-lite就运行在分页机制之上了. 调用_pte_init()函数的时候还需要提供物理页的分配和回收两个回调函数, 用于在AM中获取/释放物理页. 为了简化实现, MM中采用顺序的方式对物理页进行分配, 而且分配后无需回收.

为了在NEMU中实现分页机制, 你需要添加CR3寄存器和CR0寄存器, 以及相应的操作它们的指令. 对于CR0寄存器, 我们只需要实现PG位即可. 如果发现CR0的PG位为1, 则开启分页机制, 从此所有虚拟地址的访问(包括vaddr_read(), vaddr_write())都需要经过分页地址转换. 为了让differential testing机制正确工作, 在restart()函数中我们需要对CR0寄存器初始化为0x60000011, 但我们不必关心其含义.

然后你需要对vaddr_read()和vaddr_write()函数作少量修改. 以vaddr_read()为例, 修改后如下:

uint32_t vaddr_read(vaddr_t addr, int len) {
    if (data cross the page boundary) {
        /* this is a special case, you can handle it later. */
        assert(0);
    }
    else {
        paddr_t paddr = page_translate(addr);
        return paddr_read(paddr, len);
    }
}

你需要理解分页地址转过的过程, 然后编写page_translate()函数. 另外由于我们不打算实现保护机制, 在page_translate()函数的实现中, 你务必使用assertion检查页目录项和页表项的present位, 如果发现了一个无效的表项, 及时终止NEMU的运行, 否则调试将会异常困难. 这通常是由于你的实现错误引起的, 请检查实现的正确性. 再次提醒, 只有进入保护模式并开启分页机制之后才会进行页级地址转换. 为了让differential testing机制正确工作, 你还需要实现分页机制中accessed位和dirty位的功能.

最后提醒一下页级地址转换时出现的一种特殊情况. 由于i386并没有严格要求数据对齐, 因此可能会出现数据跨越虚拟页边界的情况, 例如一条很长的指令的首字节在一个虚拟页的最后, 剩下的字节在另一个虚拟页的开头. 如果这两个虚拟页被映射到两个不连续的物理页, 就需要进行两次页级地址转换, 分别读出这两个物理页中需要的字节, 然后拼接起来组成一个完成的数据返回. MIPS作为一种RISC架构, 指令和数据都严格按照4字节对齐, 因此不会发生这样的情况, 否则MIPS CPU将会抛出异常, 可见软件灵活性和硬件复杂度是计算机科学中又一对tradeoff. 不过根据KISS法则, 你现在可以暂时不实现这种特殊情况的处理, 在判断出数据跨越虚拟页边界的情况之后, 先使用assert(0)终止NEMU, 等到真的出现这种情况的时候再进行处理.

让用户程序运行在分页机制上

成功实现分页机制之后, 你会发现仙剑奇侠传也同样成功运行了. 但仔细想想就会发现这其实不太对劲: 我们在_asye_init()中创建了内核的虚拟地址空间, 之后就再也没有切换过这一虚拟地址空间. 也就是说, 我们让仙剑奇侠传也运行在内核的虚拟地址空间之上! 这太不合理了, 虽然NEMU没有实现ring 3, 但用户进程还是应该有自己的一套虚拟地址空间. 更可况, Navy-apps之前让用户程序链接到0x4000000的位置, 是因为之前Nanos-lite并没有对空闲的物理内存进行管理; 现在引入了分页机制, 由MM来负责所有物理页的分配. 这意味着, 如果将来MM把0x4000000所在的物理页分配出去, 仙剑奇侠传的内容将会被覆盖! 因此, 目前仙剑奇侠传看似运行成功, 其实里面暗藏杀机.

正确的做法是, 我们应该让用户程序运行在操作系统为其分配的虚拟地址空间之上. 为此, 我们需要对工程作一些变动. 首先需要将navy-apps/Makefile.compile中的链接地址-Ttext参数改为0x8048000, 这是为了避免用户程序的虚拟地址空间与内核相互重叠, 从而产生非预期的错误. 同样的, nanos-lite/src/loader.c中的DEFAULT_ENTRY也需要作相应的修改. 这时, "虚拟地址作为物理地址的抽象"这一好处已经体现出来了: 原则上用户程序可以运行在任意的虚拟地址, 不受物理内存容量的限制. 我们让用户程序的代码从0x8048000附近开始, 这个地址已经超过了物理地址的最大值(NEMU提供的物理内存是128MB), 但分页机制保证了程序能够正确运行. 这样, 链接器和程序都不需要关心程序运行时刻具体使用哪一段物理地址, 它们只要使用虚拟地址就可以了, 而虚拟地址和物理地址之间的映射则全部交给操作系统的MM来管理.

然后, 我们让Nanos-lite通过load_prog()函数(在nanos-lite/src/proc.c中定义)来进行用户程序的加载:

--- nanos-lite/src/main.c
+++ nanos-lite/src/main.c
@@ -33,2 +33,1 @@
-  uintptr_t entry = loader(NULL, "/bin/pal");
-  ((void (*)(void))entry)();
+  load_prog("/bin/dummy");

我们先运行dummy, 是因为让仙剑奇侠传成功运行在虚拟地址空间上还需要进行一些额外的工作. load_prog()函数首先会通过_protect()函数(在nexus-am/am/arch/x86-nemu/src/pte.c中定义) 创建一个用户进程的虚拟地址空间, 这个虚拟地址空间除了内核映射之外就没有其它内容了. 框架代码在调用_protect()的时候用到了一个PCB的结构体, 我们会在后面再介绍它, 目前只需要知道虚拟地址空间的信息被存放在PCB结构体的as成员中即可. 然后load_prog()会调用loader()函数加载用户程序. 需要注意的是, 此时loader()不能直接把用户程序加载到内存位置0x8048000附近了, 因为这个地址并不在内核的虚拟地址空间中, 内核不能直接访问它. loader()要做的事情是, 获取用户程序的大小之后, 以页为单位进行加载:

• 申请一页空闲的物理页
• 把这一物理页映射到用户程序的虚拟地址空间中
• 从文件中读入一页的内容到这一物理页上

这一切都是为了让用户进程在将来可以正确地运行: 用户进程在将来使用虚拟地址访问内存, 在loader为用户进程准备的映射下, 虚拟地址被转换成物理地址, 通过这一物理地址访问到的物理内存, 恰好就是用户进程想要访问的数据. 为了提供映射一页的功能, 你需要在AM中实现_map()函数(在nexus-am/am/arch/x86-nemu/src/pte.c中定义). 它的函数原型如下

void _map(_Protect *p, void *va, void *pa);

功能是将虚拟地址空间p中的虚拟地址va映射到物理地址pa. 通过p->ptr可以获取页目录的基地址. 若在映射过程中发现需要申请新的页表, 可以通过回调函数palloc_f()向Nanos-lite获取一页空闲的物理页.

从loader()返回后, load_prog()会调用_switch()函数(在nexus-am/am/arch/x86-nemu/src/pte.c中定义), 切换到刚才为用户程序创建的地址空间. 最后跳转到用户程序的入口, 此时用户程序已经完全运行在分页机制上了.

for (int i = 0; i < NR_PDE; i ++) {
  updir[i] = kpdirs[i];
}

int mm_brk(uint32_t new_brk) {
  if (current->cur_brk == 0) {
    current->cur_brk = current->max_brk = new_brk;
  }
  else {
    if (new_brk > current->max_brk) {
      // TODO: map memory region [current->max_brk, new_brk)
      // into address space current->as


      current->max_brk = new_brk;
    }

    current->cur_brk = new_brk;
  }

  return 0;
}