一, 前言
数学大师陈省身有一句话是这样说的: 了解历史的变化是了解这门学科的一个步骤. 今天, 我把这句话应用到一个具体的 Linux 模块: 了解逆向映射的最好的方法是了解它的历史. 本文介绍了 Linux 内核中的逆向映射机制如何从无到有, 如何从笨重到轻盈的历史过程, 通过这些历史的演进过程, 希望能对逆向映射有更加深入的理解.
二, 基础知识
在切入逆向映射的历史之前, 我们还是简单看看一些基础的概念, 这主要包括两个方面: 一个是逆向映射的定义, 另外一个是引入逆向映射的原因.
1, 什么是逆向映射(reverse mapping)?
在聊逆向映射之前, 我们先聊聊正向映射好了, 当你明白了正向映射, 逆向映射的概念也就易如反掌了. 所谓正向映射, 就是在已知虚拟地址和物理地址 (或者 page number,page struct) 的情况下, 为地址映射建立起完整的页表的过程. 例如, 进程分配了一段 VMA 之后, 并无对应的 page frame(即没有分配物理地址), 直到程序访问了这段 VMA 之后, 产生异常, 由内核为其分配物理页面并建立起所有的各级的 translation table. 通过正向映射, 我们可以将进程虚拟地址空间中的虚拟页面映射到对应的物理页面(page frame).
逆向映射相反, 在已知 page frame 的情况下(可能是 PFN, 可能是指向 page descriptor 的指针, 也可能是物理地址, 内核有各种宏定义用于在它们之间进行转换), 找到映射到该物理页面的虚拟页面们. 由于一个 page frame 可以在多个进程之间共享, 因此逆向映射的任务是把分散在各个进程地址空间中的所有的 page table entry 全部找出来.
一般来说, 一个进程的地址空间内不会把两个虚拟地址 mapping 到一个 page frame 上去, 如果有多个 mapping, 那么多半是这个 page 被多个进程共享. 最简单的例子就是采用 COW 的进程 fork, 在进程没有写的动作之前, 内核是不会分配新的 page frame 的, 因此父子进程共享一个物理页面. 还有一个例子和 c lib 相关, 由于 c lib 是基础库, 它会 file mapping 到很多进程地址空间中, 那么 c lib 中的程序正文段对应的 page frame 应该会有非常多的 page table entries 与之对应.
2, 为何需要逆向映射?
之所以建立逆向映射机制主要是为了方便页面回收. 当页面回收机制启动之后, 如果回收的 page frame 是位于内核中的各种内存 cache 中(例如 slab 内存分配器), 那么这些页面其实是可以直接回收, 没有相关的页表操作. 如果回收的是用户进程空间的 page frame, 那么在回收之前, 内核需要对该 page frame 进行 unmapping 的操作, 即找到所有的 page table entries, 然后进行对应的修改操作. 当然, 如果页面是 dirty 的, 我们还需要一些必要的磁盘 IO 操作.
可以给出一个实际的例子, 例如 swapping 机制, 在释放一个匿名映射页面的时候, 要求对所有相关的页表项进行更改, 将 swap area 和 page slot index 写入页表项中. 只有在所有指向该 page frame 的页表项修改完毕后才可以将该页交换到磁盘, 并且回收这个 page frame.demand paging 的场景是类似的, 只不过是需要把所有的 page table entry 清零, 这里就不赘述了.
三, 史前文明
盘古开天辟地之前, 宇宙混沌一片. 对于逆向映射这个场景, 我们的问题就是: 没有逆向映射之前, 混沌的内核世界是怎样的呢? 这一章主要是回答这个问题的, 分析的基础是 2.4.18 内核的源代码.
1, 没有逆向映射, 系统如何运作?
也许年轻的内核工程师很难想象没有逆向映射的内核世界, 但实际上 2.4 时期的内核就是这样的. 让我们想象一下, 我们自己就是 page reclaim 机制的维护者, 看看我们目前的困境: 如果没有逆向映射机制, 那么 struct page 中没有维护任何的逆向映射的数据. 这种情况下, 内核不可能通过简单的方法来找到 page frame 所对应的那些 PTEs. 当回收一个被多个进程共享的 page frame, 我们该怎么办呢?
本身回收用户进程的物理页帧并不复杂, 这需要 memory mapping 和 swapping 机制的支持. 这两种机制的工作原理类似, 只不过一个用于 file mapped page, 另外一个用于 anonymous page. 不过对于页面回收而言, 他们的工作原理类似: 就是把某些进程不常使用的 page frame 交换到磁盘上去, 同时解除进程和这个 page frame 的一切关系, 完成这两步之后, 这个物理页帧已经自由了, 可以回收到伙伴系统中.
OK, 了解了基本原理, 现在需要看看如何具体实现: 不常使用的 page frame 很好找(inactive lru 链表), 不过断绝 page frame 和进程们之间的关系很难, 因为没有逆向映射. 不过这难不倒 Linux 内核开发人员, 他们选择了扫描整个系统的各个进程的地址空间的方法.
2, 如何对进程地址空间进行扫描?
下图是一个对进程地址空间进行扫描的示意图:
系统中的所有进程地址空间 (memory descriptor) 被串成一个链表, 链表头就是 init_mm, 系统中所有的进程地址空间都挂在了这个链表中. 所谓 scan 当然就是沿着这条 mm 链表进行了. 当然, 页面回收算法尽量不 scan 整个系统的全部进程地址空间, 毕竟那是一个比较笨的办法. 回收算法可以考虑收缩内存 cache, 也可以遍历 inactive_list 来试图完成本次 reclaim 数目的要求(该链表中有些 page 不和任何进程相关), 如果通过这些方法释放了足够多的 page frame, 那么一切都搞定了, 不需要 scan 进程地址空间. 当然, 情况并非总是那么美好, 有时候, 必须启动进程物理页面回收过程才能满足页面回收的要求.
进程物理页面回收过程是通过调用 swap_out 函数完成的, 而 scan 进程地址空间的代码也是开始于这个函数. 该函数是一个三层嵌套结构:
(1) 首先沿着 init_mm, 对每一个进程地址空间进行扫描
(2) 在扫描一个进程地址空间的时候, 对属于该进程地址空间的每一个 VMA 进行扫描
(3) 在扫描每一个 VMA 的时候, 对属于该 VMA 的每一个 page 进行扫描
在扫描过程中, 如果命中了进程 A 的 page frame0, 由于该 page 只是被进程 A 使用(即只是被 A 进程 mapping), 那么可直接 unmap 并回收该 page. 对于共享页面, 我们不能这么处理了, 例如上图中的 page frame 1, 但 scan A 进程的时候, 如果条件符合, 那么我们会 unmap 该 page, 解除它和进程 A 的关系, 当然, 这时候不能回收该 page, 因为进程 X 还在使用该 page. 直到 scan 过程历经千山万水来到进程 X, 完成对 page frame 1 的 unmaping 操作, 该物理页面才可以真正会伙伴系统的怀抱.
3, 地址空间扫描的细节问题
首先, 第一个问题: 到底 scan 多少虚拟地址空间才停止 scan 呢? 当目标已经达到的时候, 例如本次 scan 打算 reclaim 32 个 page frame, 如果目标达到, 那么 scan 停止, 不需 scan 全部虚拟地址空间. 还有一种比较悲惨的情况, 那就是 scan 了系统中所有的地址空间之后, 仍然没有达成目标, 这时候也就可以停止了, 不过这属于 OOM 的处理了. 为了确保系统中的进程被均匀的 scan(毕竟 swap out 会影响进程性能, 我们肯定不能只逮住部分进程薅其羊毛), 每次 scan 完成后, 记录当前 scan 的位置(保存在 swap_mm 变量), 等下次又启动 scan 过程的时候, 从 swap_mm 开始继续 scan.
由于对性能有影响, swap out 需要雨露均沾, 各个进程都跑不掉. 同样的道理, 对于一个进程的地址空间, 我们一样也是需要公平对待, 因此需要保存每次 scan 的虚拟地址(mm->swap_address), 这样, 每次重启 scan 的时候, 总是从 swap_mm 那个地址空间的 mm->swap_address 虚拟地址开始 scan.
具体对一个 page frame 进行 swap out 的代码位于 try_to_swap_out 函数中, 在这个函数中, 如果条件满足, 会解除该 page frame 的该进程之间的关系, 完成必要的 IO 操作, 该 page reference count 减一, 对应的 pte 清零或者设定 swap entry 等. 当然, swap out 一个 page 之后, 我们并非一定能够回收它, 因为这个 page 很可能被多个进程共享. 而在 scan 过程中, 如果碰巧找到了该 page 对应的所有的页面表条目, 那么说明该页面已经不被任何进程引用, 这时候该 page frame 就会被逐出磁盘, 从而完成一个页面的回收.
四, 开天辟地
时间又回到 2002 年 1 月, 那时 VM 大神 Rik van Riel 遭遇了人生中的一次重大挫折, 他的耗费心血维护的代码被一个全新的 VM 子系统取代了. 不过 Rik van Riel 并没有消沉下去, 他在憋大招, 也就是传说中的 reverse mapping(后文简称 rmap). 本章主要描述第一个版本的 rmap, 代码来自 Linux 2.6.0.
1, 设计概念
如何构建 rmap? 最直观的想法就是针对每一个 page frame, 我们维护一个链表, 保存属于该 page 的所有 PTEs. 因此, Rik van Riel 给 struct page 增加了一个 pte chain 的成员, 以便把所有 mapping 到该 page 的 pte entry 指针给串起来. 这样想要 unmap 一个 page 就易如反掌了, 沿着这个 pte chain 就可以找到所有的 mappings. 一个基本的示意图如下, 下面的小节会给出更详细的解释.
2, 对 Struct page 的修改
Struct page 的修改如下:
- struct page {
- ......
- union {
- struct pte_chain *chain;
- pte_addr_t direct;
- } pte;
- ......
当然, 很多页面都不是共享的, 只有一个 pte entry, 因此 direct 直接指向那个 pte entry 就 OK 了. 如果存在页面共享的情况, 那么 chain 成员则会指向一个 struct pte_chain 的链表.
3, 定义 struct pte_chain
- struct pte_chain {
- unsigned long next_and_idx;
- pte_addr_t ptes[NRPTE];
- } ____cacheline_aligned;
如果 pte_chain 只保存一个 pte entry 的指针那么就太浪费了, 比较好的方法是把 struct pte_chain 对齐在 cache line 并让整个 struct pte_chain 占用一个 cache line. 除了 next_and_idx 用于指向下一个 pte_chain, 形成链表之外, 其余的空间都用于保存 pte entry 指针. 由于 pte entry 指针形成了数组, 因此我们还需要一个 index 指示下一个空闲的 pte entry pointer 的位置, 由于 pte_chain 对齐在 cache line, 因此 next_and_idx 的 LSB 的若干个 bit 是等于 0 的, 可以复用做 index.
4, 页面回收算法的修改
在进入基于 rmap 的页面回收算法之前, 让我们先回忆一下痛苦的过去. 假设一个物理页面 P 被 A 和 B 两个进程共享, 在过去, 释放 P 这个物理页面需要扫描进程地址空间, 首先 scan 到 A 进程, 解除 P 和 A 进程的关系, 但是这时候不能回收, B 进程还在使用该 page frame. 当然扫描过程最终会来到 B 进程, 只有在这时候才有机会回收这个物理页面 P. 你可能会问: 如果 scan B 进程地址空间的时候, A 进程又访问了 P 从而导致映射建立. 然后 scan A 的时候, B 进程又再次访问, 如此反反复复, 那么 P 不就永远无法回收了吗? 这个怎么办呢? 这个...... 理论上是这样的, 别问我, 其实我也很绝望.
有了 rmap, 页面回收算法顿时感觉轻松多了, 只要是页面回收算法看中的 page frame, 总是能够通过 try_to_unmap 解除和所有进程的关联, 从而将其回收到伙伴系统中. 如果该 page frame 没有共享(page flag 设定 PG_direct flag), 那么 page->pte.direct 直接命中 pte entry, 调用 try_to_unmap_one 来进行 unmap 的操作. 如果映射到了多个虚拟地址空间, 那么沿着 pte_chain 依次调用 try_to_unmap_one 来进行 unmap 的操作.
五, 女娲补天
虽然 Rik van Riel 开辟了逆向映射的新天地, 但是, 天和地都有着巨大的窟窿, 需要有人修补. 首先让我们看看这个 "巨大的窟窿" 是什么?
在引入第一个版本的 rmap 之后, Linux 的页面回收变得简单, 可控了, 但是这个简单的设计是有代价的: 每一个 struct page 增加一个指针成员, 在 32bit 的系统上也就是增加了 4B. 考虑到系统为了管理内存会为每一个 page frame 建立一个 struct page 对象, 引入 rmap 而导致的内存开销也不是一个小数目啊. 此外, share page 需要建立 pte_chain 链表, 也是一个不小的内存开销. 除了内存方面的压力, 第一个版本的 rmap 对性能也造成了一定的影响. 例如: 在 fork 操作的时候, 父子进程共享了很多的 page frame, 这样, 在 copy page table 的时候就会伴随大量的 pte_chain 的操作, 从而让 fork 的速度变得缓慢.
本章就是带领大家看看 object-based reverse mapping(后文简称 objrmap)是如何填补那个 "巨大的窟窿". 本章的代码来自 2.6.11 版本的内核.
1, 问题的引入
推动 rmap 优化的动力来自内存方面的压力, 与此相关的问题是: 32-bit 的 Linux 内核是否支持 4G 以上的 memory. 在 1999 年, Linus 的决定是: 32-bit 的 Linux 内核永远也不会支持 2G 以上的内存. 不过历史的洪流不可阻挡, 处理器厂商设计了扩展模块以便寻址更多的内存, 高端的服务器也配置了越来越多的内存. 这也迫使 Linus 改变之前的思路, 让 Linux 内核支持更大的内存.
红帽公司的 Andrea Arcangeli 当时正在做的工作就是让 32-bit 的 Linux 运行在配置超过 32G 内存的公司服务器上. 在这些服务器上往往启动大量的进程, 共享了大量的物理页帧, 消耗了大量的内存. 对于 Andrea Arcangeli 来说, 内存消耗的真正元凶是明确的: 逆向映射模块, 这个模块消耗了太多的 low memory, 从而导致了系统的各种 crash. 为了让自己的工作继续推进, 他必须解决 rmap 引入的内存扩展性 (memory scalability) 问题.
2,file mapped 的优化
并非只有 Andrea Arcangeli 关注到了 rmap 的内存问题, 在 2.5 版本的开发过程中, IBM 公司的 Dave McCracken 就已经提交了 patch, 试图在保证逆向映射功能的基础上, 同时又能修正 rmap 带来的各种问题.
Dave McCracken 的方案是一种基于对象的逆向映射机制. 在过去, 通过 rmap, 我们可以从 struct page 直接获取其对应的 ptes,objrmap 的方法借助其他的数据对象来完成从 struct page 检索到其对应 ptes 的过程, 这个过程的示意图如下:
对于 objrmap 而言, 寻找一个 page frame 的 mappings 是一个比较长的路径, 它借助了 VMA(struct vm_area_struct)这个数据对象. 我们知道对于某些 page frame 是有后备文件的, 这种类型的页面和某个文件相关, 例如进程的正文段和该进程的可执行文件相关. 此外, 进程可以调用 mmap()对某个文件进行 mapping. 对于这些页帧我们称之 file mapped page.
对于这些文件映射页面, 其 struct page 中有一个成员 mapping 指向一个 struct address_space,address_space 是和文件相关的, 它保存了文件 page cache 相关的信息. 当然, 我们这个场景主要关注一个叫做 i_mmap 的成员. 一个文件可能会被映射到多个进程的多个 VMA 中, 所有的这些 VMA 都被挂入到 i_mmap 指向的 Priority search tree 中.
当然, 我们最终的目标是 PTEs, 下面这幅图展示了如何从 VMA 和 struct page 中的信息导出该 page frame 的虚拟地址的:
而在 Linux kernel 中, 函数 vma_address 可以完成这个功能:
- static inline unsigned long
- vma_address(struct page *page, struct vm_area_struct *vma)
- {
- pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
- unsigned long address;
- address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
- return address;
- }
对于 file mapped page,page->index 表示的是映射到文件内的偏移(Byte 为单位), 而 vma->vm_pgoff 表示的是该 VMA 映射到文件内的偏移(page 为单位), 因此, 通过 vma->vm_pgoff 和 page->index 可以得到该 page frame 在 VMA 中的地址偏移, 再加上 vma->vm_start 就可以得到该 page frame 的虚拟地址. 有了虚拟地址和地址空间(vma->vm_mm), 我们就可以通过各级页表找到该 page 对应的 pte entry.
3, 匿名页面的优化
我们都知道, 用户空间进程的页面主要有两种, 一种是 file mapped page, 另外一种是 anonymous mapped page.Dave McCracken 的 objrmap 方案虽好, 但是只是适用于 file mapped page, 对于匿名映射页面, 这个方案无能为力. 因此, 我们必须为匿名映射页面也设计一种基于对象的逆向映射机制, 最后形成 full objrmap 方案.
为了解决内存扩展性的问题, Andrea Arcangeli 全力工作在 full objrmap 方案上, 不过他还有一个竞争对手, Hugh Dickins, 同时也提交了一系列 full objrmap 补丁, 试图并入内核主线, 显然, 在匿名映射页面上, 最后胜出的是 Andrea Arcangeli, 他的匿名映射方案如下图所示:
和 file mapped 类似, anonymous page 也是通过 VMA 来寻找 page frame 对应的 pte entry. 由于文件映射页面的 VMA 数量可能非常大, 因此我们采用 Priority search tree 这样的数据结构. 对于匿名映射页面, 其数量一般不会太大, 所以使用链表结构就 OK 了.
为了节省内存, 我们复用了 struct page 中的 mapping 指针: 一个 page frame 如果是 file mapped, 其 mapping 指针指向对应文件的 address_space 数据结构. 如果是 anonymous page, 那么 mapping 指针指向 anon_vma 数据结构. 虽然节省了内存, 但是降低了可读性, 但是由于内核会为每一个 page frame 建立一个对应的 struct page 数据对象, 该数据结构即便是增加 4B 对整个系统的内存消耗都是巨大的, 因此内核还是采用了较为丑陋的方式来定义 mapping 这个成员. 通过 struct page 中的 mapping 成员我们可以获得该 page 映射相关的信息, 总结如下:
(1) 等于 NULL, 表示该 page frame 不再内存中, 而是被 swap out 到磁盘去了.
(2) 如果不等于 NULL, 并且 least signification bit 等于 1, 表示该 page frame 是匿名映射页面, mapping 指向了一个 anon_vma 的数据结构.
(3) 如果不等于 NULL, 并且 least signification bit 等于 0, 表示该 page frame 是文件映射页面, mapping 指向了一个该文件的 address_space 数据结构.
通过 anon_vma 数据结构, 我们可以得到映射到该 page 的所有的 VMA, 至此, 匿名映射和 file mapped 汇合, 进一步解决的问题仅仅是如何从 VMA 到 pte entry 而已. 上一节, 我们描述了 vma_address 函数如何获取 file mapped page 的虚拟地址, 其实 anonymous page 的逻辑是一样的, 只不过 vma->vm_pgoff 和 page->index 的基础点不一样了, 对于 file mapped 的场景, 这个基础点是文件起始位置. 对于匿名映射, 起始点有两种情况, 一种是 share anonymous mapping, 起点位置是 0. 另外一种是 private anonymous mapping, 起点位置是 mapping 的虚拟地址(除以 page size). 但是不管如何, 从 VMA 和 struct page 得到对应虚拟地址的算法概念是类似的.
六, 卷土重来
full objrmap 进入内核之后, 看起来一切都很完美了, 比起她的前任, Rik van Riel 的 rmap 方案, objrmap 各方面的指标都是全面碾压 rmap. 首次将逆向映射引入内核的大神 Rik van Riel 遭受了第二次的打击, 不过他依然斗志昂扬并试图东山再起.
Objrmap 虽然完美, 不过晴朗的天空中飘着一朵乌云. 大神 Rik van Riel 敏锐的看到了逆向映射的那朵 "乌云", 提出了自己的解决方案. 本章主要描述新的 anon_vma 机制, 代码来自 4.4.6 内核.
1, 旧 anon_vma 机制有什么问题?
我们先一起来看看旧 anon_vma 机制下, 系统是如何运作的. VMA_P 是父进程的一个匿名映射的 VMA,A 和 C 都已经分配了 page frame, 而其他的 page 都还都没有分配物理页面. 在 fork 之后, 子进程 copy 了 VMA_P, 当然由于采用了 COW 技术, 这时候父子进程的匿名页面会共享, 同时在父子进程地址空间对应的 pte entry 中标注 write protect 的标记, 如下图所示:
按理说不同进程的匿名页面 (例如 stack,heap) 是私有的, 不会共享, 但是为了节省内存, 在父进程 fork 子进程之后, 父子进程对该页面执行写操作之前, 父子进程的匿名页是共享的, 所以这些 page frame 指向同一个 anon_vma. 当然, 共享只是短暂的, 一旦有 write 操作就会产生异常, 并在异常处理中分配 page frame, 解除父子进程匿名页面的共享, 具体如下图的 page A 所示:
这时候由于写操作, 父子进程原本共享的 page frame 已经不再共享, 然而, 这两个 page 却仍然指向同一个 anon_vma, 不仅如此, 对于 B 这样的页面, 一开始就没有在父子进程之间共享, 当首次访问的时候(无论是父进程还是子进程), 通过 do_anonymous_page 函数分配的 page frame 也是同样的指向一个 anon_vma. 也就是说, 父子进程的 VMA 共享一个 anon_vma.
在这种情况下, 我们看看 unmap page frame1 会发生什么. 毫无疑问, page frame1 对应的 struct page 的 mapping 成员指向了上图中的 anon_vma, 遍历 anon_vma 会命 VMA_P 和 VMA_C, 这里面, VMA_C 是无效的 VMA, 本来就不应该匹配到. 如果 anon_vma 的链表没有那么长, 那么整体性能也 OK. 然而, 在有些网路服务器中, 系统非常依赖 fork, 某个服务程序可能会 fork 巨大数量的子进程来处理服务请求, 在这种情况下, 系统性能严重下降. Rik van Riel 给出了一个具体的示例: 系统中有 1000 进程, 都是通过 fork 生成的, 每个进程的 VMA 有 1000 个匿名页. 根据目前的软件架构, anon_vma 链表中会有 1000 个 vma 的节点, 而系统中有一百万个匿名页面属于同一个 anon_vma.
这样的系统会导致什么样的问题呢? 我们一起来看看 try_to_unmap_anon 函数, 其代码框架如下:
- static int try_to_unmap_anon(struct page *page)
- {......
- anon_vma = page_lock_anon_vma(page);
- list_for_each_entry(vma, &anon_vma->head, anon_vma_node) {
- ret = try_to_unmap_one(page, vma);
- }
- spin_unlock(&anon_vma->lock);
- return ret;
- }
当系统中的一个 CPU 在执行 try_to_unmap_anon 函数的时候, 需要遍历 VMA 链表, 这时会持有 anon_vma->lock 这个自旋锁. 由于 anon_vma 存有了很多根本无关的 VMA, 通过, page table 的检索过程, 你就会发现这个 VMA 根本和准备 unmap 的 page 无关, 因此只能 scan 下一个 VMA, 整个过程需要消耗大量的时间, 延长了临界区(复杂度是 O(N)). 与此同时, 其他 CPU 在试获取这把锁的时候, 基本会被卡住, 这时候整个系统的性能可想而知了. 更加糟糕的是内核中并非只有 unmap 匿名页面的时候会上锁, 遍历 VMA 链表, 还有一些其他的场景也会这样(例如 page_referenced 函数). 想象一下, 一百万个页面共享这一个 anon_vma, 对 anon_vma->lock 自旋锁的竞争那是相当的激烈啊.
2, 改进的方案
旧的方案的症结所在是 anon_vma 承载了太多进程的 VMA 了, 如果能将其变成 per-process 的, 那么问题就解决了. Rik van Riel 的解决办法是为每一个进程创建一个 anon_vma 结构并通过各种数据结构把父子进程的 anon_vma(后面简称 AV)以及 VMA 链接在一起. 为了链接 anon_vma, 内核引入了一个新的结构, 称为 anon_vma_chain(后面简称 AVC):
struct anon_vma_chain {
struct vm_area_struct *vma;――指向该 AVC 对应的 VMA
struct anon_vma *anon_vma;――指向该 AVC 对应的 AV
struct list_head same_vma; ――链接入 VMA 链表的节点
struct rb_node rb;―――链接入 AV 红黑树的节点
- unsigned long rb_subtree_last;
- };
AVC 是一个神奇的结构, 每个 AVC 都有其对应的 VMA 和 AV. 所有指向相同 VMA 的 AVC 会被链接到一个链表中, 链表头就是 VMA 的 anon_vma_chain 成员. 而一个 AV 会管理若干的 VMA, 所有相关的 VMA(其子进程或者孙进程)都挂入红黑树, 根节点就是 AV 的 rb_root 成员.
这样的描述非常枯燥, 估计第一次接触逆向映射的同学是不会明白的, 不如我们一起来看看 AV,AVC 和 VMA 的 "大厦" 是如何搭建起来的.
3, 当 VMA 和 VA 首次相遇
由于采用了 COW 技术, 子进程和父进程的匿名页面往往是共享的, 直到其中之一发起写操作. 但是如果子进程执行了 exec 的系统调用, 加载了自己的二进制 image, 这时候, 子进程和父进程的执行环境 (包括匿名页面) 就分道扬镳了(参考 flush_old_exec 函数), 我们的场景就是从这么一个全新的 exec 后的进程开始. 当该进程的匿名映射 VMA 通过 page fault 分配第一个 page frame 的时候, 内核会构建下图所示的数据关系:
上图中的 AV0 就是该进程的 anon_vma, 由于它是一个顶级结构, 因此它的 root 和 parent 都是指向了自己. AV 这个数据结构当然为了管理 VMA 了, 不过新机制中, 这是通过 AVC 进行中转的. 上图中的 AVC0 搭建了该进程 VMA 和 AV 之间的桥梁, 分别有指针指向了 VMA0 和 AV0, 此外, AVC0 插入到 AV 的红黑树, 同时也会插入到 VMA 的链表中.
对于这个新分配的 page frame 而言, 它会 mapping 到 VMA 对应的某个虚拟地址上去, 为了维护逆向映射的关系, struct page 中的 mapping 指向了 AV0,index 成员指向了该 page 在整个 VMA0 中的偏移. 图中没有画出这个关系, 主要因为这是老生常谈了, 相信大家都已经熟悉.
VMA0 中随后可能会有若干的 page frame 被 mapping 到该 VMA 的某个虚拟页面, 不过上面的结构不会变化, 只不过每一个 page 中的 mapping 都指向了上图中的 AV0. 另外, 上图中那个虚线绿色 block 的 AVC0 其实等于那个绿色实线的 AVC0 block, 也就是说这时候该 VMA 只有一个 anon_vma_chain, 即 AVC0, 上图只是方便表示该 AVC 也会被挂入 VMA 的链表, 挂入 anon_vma 的红黑树而已.
如果想参考相关的代码可以仔细看看 do_anonymous_page 或者 do_cow_fault.
4, 在 fork 的时候, 匿名映射的 VMA 经历了什么?
一旦 fork, 那么子进程会 copy 父进程的 VMA(参考函数 dup_mmap), 子进程会有自己的 VMA, 同时也会分配自己的 AV(旧的机制下, 多个进程共享一个 AV, 而新的机制中, AV 是 per process 的), 然后建立父子进程之间的 VMA,VA 的 "大厦", 主要的步骤如下:
(1) 调用 anon_vma_clone 函数, 建立子进程 VMA 和 "父进程们"VA 的关系
(2) 建立子进程 VMA 和子进程 VA 的关系
怎样叫做建立 VMA 和 VA 的关系? 其实就是 anon_vma_chain_link 函数的调用过程, 步骤如下:
(1) 分配一个 AVC 结构, 成员指针指向对应的 VMA 和 VA
(2) 将该 AVC 加入 VMA 链表
(3) 将该 AVC 加入 VA 红黑树
我们一开始先别把事情搞得太复杂, 先看看一个全新进程 fork 子进程的场景. 这时候, 内核会构建下图所示的数据关系:
首先看看如何建立子进程 VMA1 和父进程 AV0 的关系, 这里需要遍历 VMA0 的 anon_vma_chain 链表, 当然现在这个链表只有一个 AVC0(link 到 AV0), 为了建立和父进程的联系, 我们分配了 AVC_x01, 它是一个桥梁, 连接了父子进程.(注: AVC_x01 中的 x 表示连接, 01 表示连接 level 0 和 level 1). 通过这个桥梁, 父进程可以找到子进程的 VMA(因为 AVC_x01 插入 AV0 的红黑树中), 而子进程也可以找到父进程的 AV(因为 AVC_x01 插入 VMA1 的链表中).
当然, 自己的 anon_vma 也需要创建. 在上图中, AV1 就是子进程的 anon_vma, 同时分配一个 AVC1 来连接该子进程的 VMA1 和 AV1, 并调用 anon_vma_chain_link 函数将 AVC1 插入 VMA1 的链表和 AV1 的红黑树中.
父进程也会创建其他新的子进程, 新创建的子进程的层次和 VMA1,VA1 的类似, 这里就不描述了. 不过需要注意的是: 父进程每创建一个子进程, AV0 的红黑树中会增加每一个起 "桥梁" 作用的 AVC, 以此连接到子进程的 VMA.
5, 构建三层大厦
上一节描述了父进程创建子进程的情况, 如果子进程再次 fork, 那么整个 VMA-VA 的大厦将形成三层结构, 具体如下图所示:
当然, 首先要进行的仍然是建立孙进程 VMA 和 "父进程们"VA 的关系, 这里的 "父进程们" 其实是泛指孙进程的上层的那些进程们. 对于这个场景,"父进程们" 指的就是上图中的 A 进程和 B 进程. 如何建立? 在 fork 的时候, 我们进行 VMA 的拷贝: 即分配 VMA2 并以 VMA1 为原型 copy 到 VMA2 中. Copy 是沿着 VMA1 的 AVC 链表进行的, 该链表有两个元素: AVC1 和 AVC_x01, 分别和父进程 A 和子进程 B 的 AV 关联. 因此, 在孙进程 C 中, 我们会分配 AVC_x02 和 AVC_x12 两个 AVC, 并建立 level 2 层和 level 0 层以及 level 1 层之间的关系.
同样的, 自己 level 的 anon_vma 也需要创建. 在上图中, AV2 就是孙进程 C 的 anon_vma, 同时分配一个 AVC2 来连接该孙进程的 VMA2 和 AV2, 并调用 anon_vma_chain_link 函数将 AVC2 插入 VMA2 的链表和 AV2 的红黑树中.
AV2 中的 root 指向 root AV, 也就是进程 A 的 AV.Parent 成员指向其 B 进程 (C 的父进程) 的 AV. 通过 Parent 这样的指针, 不同 level 的 AV 建立了父子关系, 而通过 root 指针, 每一个 level 的 AV 都可以寻找找到 root AV.
6,page frame 是如何加入 "大厦" 中?
前面几个小节重点讨论了 hierarchy AV 的结构是如何搭建起来的, 也就是描述 fork 的过程中, 父子进程的 VMA,AVC 和 AV 是如何联系的. 本小节我们将一起来看看父子进程之一访问页面, 发生了 page fault 的处理过程. 这个处理过程有两个场景, 一个是父子进程都没有 page frame, 这时候, 内核代码会调用 do_anonymous_page 分配 page frame 并调用 page_add_new_anon_rmap 函数建立该 page 和对应 VMA 的关系. 第二个场景复杂一点, 是父子共享匿名页面的场景, 当发生 write fault 的时候, 也是分配 page frame 并调用 page_add_new_anon_rmap 函数建立该 page 和对应 VMA 的关系, 具体代码位于 do_wp_page 函数. 无论哪一个场景, 最终都是将该 page 的 mapping 成员指向了该进程所属的 AV 结构.
7, 为何建立如此复杂的 "大厦"?
如果你能坚持读到这里, 那么说明你对枯燥文字的忍受能力还是很强的, 哈哈. Page,VMA,VAC,VA 组成了如此复杂的层次结构到底是为什么呢? 是为了打击你学习内核的兴趣吗? 非也, 让我们还是用一个实际的场景来说明这个 "大厦" 的功能.
我们通过下面的步骤建立起上图的结构:
(1) P 进程的某个 VMA 中有两类页面: 一类是有真实的物理页面的, 另外一类是还没有配备物理页面的. 上图中, 我们分别跟踪有物理页面的 A 以及还没有分配物理页面的 B.
(2) P 进程 fork 了 P1 和 P2
(3) P1 进程 fork 了 P12 进程
(4) P1 进程访问了 A 页面, 分配了 page frame2
(5) P12 进程访问了 B 页面, 分配了 page frame3
(6) P2 进程访问了 B 页面, 分配了 page frame1
(7) P2 进程 fork 了 P21 进程
经过上面的这一些动作之后, 我们来看看 page frame 共享的情况: 对于 P 进程的 page frame(是指该 page 的 mapping 成员指向 P 进程的 AV, 即上图中的 AV_P)而言, 他可能会被任何一个 level 的的子进程 VMA 中的 page 所有共享, 因此 AV_P 需要包括其子进程, 孙进程...... 的所有的 VMA. 而对于 P1 进程而言, AV_P1 则需要包括 P1 子进程, 孙进程...... 的所有的 VMA, 有一点可以确认: 至少父进程 P 和兄弟进程 P2 的 VMA 不需要包括在其中.
现在我们回头看看 AV 结构的大厦, 实际上是符合上面的需求的.
8, 页面回收的时候, 如何 unmap 一个 page frame 的所有的映射?
搭建了那么复杂的数据结构大厦就是为了应用, 我们一起看看页面回收的场景. 这个场景需要通过 page frame 找到所有映射到该物理页面的 VMAs. 有了前面的铺垫, 这并不复杂, 通过 struct page 中的 mapping 成员可以找到该 page 对应的 AV, 在该 AV 的红黑树中, 包含了所有的可能共享匿名页面的 VMAs. 遍历该红黑树, 对每一个 VMA 调用 try_to_unmap_one 函数就可以解除该物理页帧的所有映射.
OK, 我们再次回到这一章的开始, 看看那个长临界区导致的性能问题. 假设我们的服务器上有一个服务进程 A, 它 fork 了 999 个子进程来为世界各地的网友服务, 进程 A 有一个 VMA, 有 1000 个 page. 下面我们就一起来对比新旧机制的处理过程.
首先, 百万 page 共享一个 anon_vma 的情况在新机制中已经解决, 每一个进程都有自己特有的 anon_vma 对象, 每一个进程的 page 都指向自己特有的 anon_vma 对象. 在旧的机制中, 每次 unmap 一个 page 都需要扫描 1000 个 VMA, 而在新的机制中, 只有顶层的父进程 A 的 AV 中有 1000 个 VMA, 其他的子进程的 VMA 的数目都只有 1 个, 这大大降低了临界区的长度.
七, 后记
本文带领大家一起简略的了解了逆向映射的发展过程. 当然, 时间的车轮永不停息, 逆向映射机制还在不断的修正, 如果你愿意, 也可以了解其演进过程的基础上, 提出自己的优化方案, 在其历史上留下自己的印记.
来源: http://www.tuicool.com/articles/IJb2mma