从史前文明到女娲补天：Linux内存逆向映射（reverse mapping）技术的前世今生

本文简介

       关于Linux内存管理逆向映射技术的历史和现在的分析，投稿标题《逆向映射的演进》，后经过小编与郭大侠商议改为《Linux内存逆向映射（reverse mapping）技术的前世今生》。

作者简介

         郭健，一名普通的内核工程师，以钻研Linux内核代码为乐，热衷于技术分享，希望能汇集有同样想法的技术人，以蜗牛的心态探讨技术。

(小编画外音:郭大侠是我最佩服的大侠，他为人低调，技术精湛又虚怀若谷，实为我辈Linuxer之楷模。侠之大者，为国为民。)

一、前言

数学大师陈省身有一句话是这样说的：了解历史的变化是了解这门学科的一个步骤。今天，我把这句话应用到一个具体的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，我们该怎么办呢？

本身回收用户进程的物理页帧并不复杂，这需要memo