2.6内核新引入的反向映射_网络反向映射

（本文基于2.6.1内核，参考2.6.9内核）反向映射是2.6内核中新引入的一个机制，主要是为了加速页面置换的时候的效率，由于内核中的页面是不区分进程的，多个进程很有可能会共享一个页面，内核只管每个页面必须和一个或者多个pte对应，反过来，每一个present位为1的pte必须和一个页面相对应，这个反过来的对应是个一一映射关系，但是前面的却不然，也就是说页面到pte的映射却不是一一映射的关系，而在一个页面将要被换出物理内存的时候必须实时更新与之相关的各个pte，由此得出的问题就是必须扫描所有的进程的所有的pte，只要找到pte所对应的页面是将要被换出的页面就更新之，这样效率未免太低下，为什么呢？因为页面被换出本应该只涉及页面和与该页面相关的实体，如果为了找到这些所谓的相关实体而消耗大量的时间和空间资源，那么这必然是一个瓶颈，并且这个缺陷是一定可以弥补的，为什么可以弥补呢？因为我们需要做的仅仅是记录下和此页面相关的实体就可以了，而不是通过遍历寻找的方式，这样可以滤去很多无关的查找，必然的一种可能是浪费了空间来存储额外的信息，带来的优惠就是节省了大量的时间，这就是反向映射的设计初衷，那么反向映射是怎么实现的呢？最简单的实现就是在page数据结构中扩展一个字段，实际上是一个链表，里面链接所有指向这个page的pte，换出该页面的时候遍历这个链表就会得到所有的需要更新的pte，这也是2.6的早期版本中使用的方式：

struct page {

...//别的字段就此略过

union {

struct pte_chain *chain;

pte_addr_t direct;

} pte; //这个联合式新增的

...

};

struct pte_chain {

unsigned long next_and_idx;

pte_addr_t ptes[NRPTE]; //一切为了效率，采用了缓存对齐的方式可以最小化缓存缺失

} ____cacheline_aligned;

我已经不能用除了艺术之外的其他词汇来形容以下这个函数了，当然linux内核不管艺术不艺术，最终美丽的代码终成泡影，换来的是高效，linux就是这样，下面的page_add_rmap函数好在巧妙的使用了pte_chain结构：

struct pte_chain * page_add_rmap(struct page *page, pte_t *ptep, struct pte_chain *pte_chain)

{

pte_addr_t pte_paddr = ptep_to_paddr(ptep); //得到pte的地址

struct pte_chain *cur_pte_chain;

if (!pfn_valid(page_to_pfn(page)) || PageReserved(page))

return pte_chain;

pte_chain_lock(page);

if (page->pte.direct == 0) { //新分配的页面肯定只有自己拥有pte指向，新分配的page的pte.direct肯定为0

page->pte.direct = pte_paddr; //下一次该page的pte.direct字段就不为0了

SetPageDirect(page); //设置Direct标志

inc_page_state(nr_mapped);

goto out; //第一次分配的页面不需要什么反向映射，直接返回，实际上第一次分配这个page时，待这个函数返回后，pte_chain将会被释放掉，因为它没有用

}

if (PageDirect(page)) { //如果第二次该page被引用，那么就需要反向映射了，第二次引用该页面时一共有两个pte引用之，第一个就是该页面刚刚被分配时的page->pte.direc，第二个就是当前调用的pte_paddr

ClearPageDirect(page); //清楚掉Direct标志，表明它开始使用反向映射了

pte_chain->ptes[NRPTE-1] = page->pte.direct; //从后向前设置

pte_chain->ptes[NRPTE-2] = pte_paddr;

pte_chain->next_and_idx = pte_chain_encode(NULL, NRPTE-2);

page->pte.direct = 0; //这里设置为0岂不是下次又要到上面的if (page->pte.direct == 0)里面去了，哈哈，注意page的pte是个联合体而不是结构体

page->pte.chain = pte_chain; //这个设置将使得下次上面的if (page->pte.direct == 0)通不过！

pte_chain = NULL; /* We consumed it */

goto out;

}

cur_pte_chain = page->pte.chain; //如果该page第三次被引用，那么就要从这里开始了

if (cur_pte_chain->ptes[0]) { //已经到了第一个，说明一个pte_chain已经满了，因为各个pte是从pte_chain的后面向前面推进的

pte_chain->next_and_idx = pte_chain_encode(cur_pte_chain, NRPTE - 1);

page->pte.chain = pte_chain; //下次将使用新的pte_chain

pte_chain->ptes[NRPTE-1] = pte_paddr;

pte_chain = NULL; //将pte_chain设置为NULL，目的是在外面不被释放，因为我们已经使用了

goto out;

}

cur_pte_chain->ptes[pte_chain_idx(cur_pte_chain) - 1] = pte_paddr;

cur_pte_chain->next_and_idx--; //向前推进

out:

pte_chain_unlock(page);

return pte_chain; //如果没有使用参数传进来的pte_chain，那么返回它，调用者负责释放它，只要返回一个非NULL的pte_chain就说明传进来的pte_chain没有被使用，外面的调用这需要释放之，这是本着谁申请谁释放这一基本的编程原则来的

}

上面的函数其实一点也不复杂，只要仔细阅读一定可以理解的，看完了上面的add，那么这个函数所做的一切在什么地方使用呢？答案当然是在unmap的时候，那么看一下try_to_unmap吧：

int try_to_unmap(struct page * page)

{

struct pte_chain *pc, *next_pc, *start;

int ret = SWAP_SUCCESS;

int victim_i = -1;

...

if (PageDirect(page)) { //如果是第一个页面，那么说明只有一个引用，更新之即可

ret = try_to_unmap_one(page, page->pte.direct);

if (ret == SWAP_SUCCESS) {

page->pte.direct = 0;

ClearPageDirect(page);

}

goto out;

}

start = page->pte.chain; //否则就需要遍历pte.chain了

for (pc = start; pc; pc = next_pc) { //遍历所有的pte_chain

int i;

next_pc = pte_chain_next(pc);

if (next_pc)

prefetch(next_pc);

for (i = pte_chain_idx(pc); i < NRPTE; i++) { //遍历一个pte_chain数组的ptes

pte_addr_t pte_paddr = pc->ptes[i]; //这样就找到了一个pte

...

switch (try_to_unmap_one(page, pte_paddr)) {

...//结果码处理

}

}

}

...

}

如果linux和微软一样，那么代码就到此为止了，事实证明这样已经很不错了，是的，代码优美，效率又高，一切都不错，但是linux开发中没有最好只有更好，所有的物理内存都有page结构与之对应，每个page结构中保存一个pte联合实在不是什么明智之举，毕竟很多page根本就不需要pte反向映射，比如内核使用的page以及很多只有一个进程使用的匿名页面，那么就必须想一个办法，一个懒惰的办法将这个反向映射的相关信息保存到一个用户空间使用的结构体之内，就是说只有在使用反向映射的实体中才保存反向映射信息，否则不保存，这样算法的时间复杂度不变，同时可以节省更多的空间，这样一来2.6后来的内核中就废弃了以上的优雅方式，使用了一种更加高效的方法，将反向映射信息保存到vm_area_struct结构中，因为只有用户空间的页面才会有反向映射，而vm_area_struct是只有用户空间进程才有的数据结构

void page_add_anon_rmap(struct page *page, struct vm_area_struct *vma, unsigned long address)

{

struct anon_vma *anon_vma = vma->anon_vma; //这个anon_vma是一定要有的，如果在fork的时候有两个vma公用了一个page，那么page显然影响了两个pte，这两个pte可以通过这两个vma得到

pgoff_t index;

anon_vma = (void *) anon_vma + PAGE_MAPPING_ANON;

index = (address - vma->vm_start) >> PAGE_SHIFT;

index += vma->vm_pgoff;

index >>= PAGE_CACHE_SHIFT - PAGE_SHIFT;

if (atomic_inc_and_test(&page->_mapcount)) {

page->index = index;

page->mapping = (struct address_space *) anon_vma; //2.6的稍微后期的版本中巧妙使用page的mapping字段存储了反向映射的信息，当然光有page的字段不行，必须要有有个地方将pte链接在一起才行，这个结构就是上面的anon_vma，这个anon_vma是vma中多出来的字段，可能浪费了一些空间，但是说实话vma中页面在物理内存的数量与page的数量相比还是要少啊，因此相比前一个解决方案还是节省了空间。

inc_page_state(nr_mapped);

}

}

2.6后期的方案利用了mapping的低位没有用的特征从而使用了这些位，利用了一切可以利用的空间，并且这个方案将匿名反向映射和文件缓存反向映射分离，在文件反向映射中使用优先级树高效处理，相比前一个早期的版本性能提高了不少。2.6的后期版本中的反向映射解决方案的资料是比较多的，我就不多说了，但是早期的反向映射的资料比较少，因此本文就分析了代码。本文主要想表达的意思就是linux的后期版本的性能基本都比以前的高，不管它的代码的可读性有多糟糕，其实阅读linux代码和理解代码的关键就是理解作者的设计思想，最好的办法就是看changelog，只要理解了changelog就可以理解作者的意图，读懂了代码才可以修改代码，才可以添加自己的逻辑，开发自己的内核。