一、前言

數(shù)學(xué)大師陳省身有一句話是這樣說(shuō)的：了解歷史的變化是了解這門(mén)學(xué)科的一個(gè)步驟。今天，我把這句話應(yīng)用到一個(gè)具體的Linux模塊：了解逆向映射的最好的方法是了解它的歷史。本文介紹了Linux內(nèi)核中的逆向映射機(jī)制如何從無(wú)到有，如何從笨重到輕盈的歷史過(guò)程，通過(guò)這些歷史的演進(jìn)過(guò)程，希望能對(duì)逆向映射有更加深入的理解。

二、基礎(chǔ)知識(shí)

在切入逆向映射的歷史之前，我們還是簡(jiǎn)單看看一些基礎(chǔ)的概念，這主要包括兩個(gè)方面：一個(gè)是逆向映射的定義，另外一個(gè)是引入逆向映射的原因。

1、什么是逆向映射（reverse mapping）？

在聊逆向映射之前，我們先聊聊正向映射好了，當(dāng)你明白了正向映射，逆向映射的概念也就易如反掌了。所謂正向映射，就是在已知虛擬地址和物理地址（或者page number、page struct）的情況下，為地址映射建立起完整的頁(yè)表的過(guò)程。例如，進(jìn)程分配了一段VMA之后，并無(wú)對(duì)應(yīng)的page frame（即沒(méi)有分配物理地址），直到程序訪問(wèn)了這段VMA之后，產(chǎn)生異常，由內(nèi)核為其分配物理頁(yè)面并建立起所有的各級(jí)的translation table。通過(guò)正向映射，我們可以將進(jìn)程虛擬地址空間中的虛擬頁(yè)面映射到對(duì)應(yīng)的物理頁(yè)面（page frame）。

逆向映射相反，在已知page frame的情況下（可能是PFN、可能是指向page descriptor的指針，也可能是物理地址，內(nèi)核有各種宏定義用于在它們之間進(jìn)行轉(zhuǎn)換），找到映射到該物理頁(yè)面的虛擬頁(yè)面?zhèn)儭Ｓ捎谝粋€(gè)page frame可以在多個(gè)進(jìn)程之間共享，因此逆向映射的任務(wù)是把分散在各個(gè)進(jìn)程地址空間中的所有的page table entry全部找出來(lái)。

一般來(lái)說(shuō)，一個(gè)進(jìn)程的地址空間內(nèi)不會(huì)把兩個(gè)虛擬地址mapping到一個(gè)page frame上去，如果有多個(gè)mapping，那么多半是這個(gè)page被多個(gè)進(jìn)程共享。最簡(jiǎn)單的例子就是采用COW的進(jìn)程fork，在進(jìn)程沒(méi)有寫(xiě)的動(dòng)作之前，內(nèi)核是不會(huì)分配新的page frame的，因此父子進(jìn)程共享一個(gè)物理頁(yè)面。還有一個(gè)例子和c lib相關(guān)，由于c lib是基礎(chǔ)庫(kù)，它會(huì)file mapping到很多進(jìn)程地址空間中，那么c lib中的程序正文段對(duì)應(yīng)的page frame應(yīng)該會(huì)有非常多的page table entries與之對(duì)應(yīng)。

2、為何需要逆向映射？

之所以建立逆向映射機(jī)制主要是為了方便頁(yè)面回收。當(dāng)頁(yè)面回收機(jī)制啟動(dòng)之后，如果回收的page frame是位于內(nèi)核中的各種內(nèi)存cache中（例如 slab內(nèi)存分配器），那么這些頁(yè)面其實(shí)是可以直接回收，沒(méi)有相關(guān)的頁(yè)表操作。如果回收的是用戶進(jìn)程空間的page frame，那么在回收之前，內(nèi)核需要對(duì)該page frame進(jìn)行unmapping的操作，即找到所有的page table entries，然后進(jìn)行對(duì)應(yīng)的修改操作。當(dāng)然，如果頁(yè)面是dirty的，我們還需要一些必要的磁盤(pán)IO操作。

可以給出一個(gè)實(shí)際的例子，例如swapping機(jī)制，在釋放一個(gè)匿名映射頁(yè)面的時(shí)候，要求對(duì)所有相關(guān)的頁(yè)表項(xiàng)進(jìn)行更改，將swap area和page slot index寫(xiě)入頁(yè)表項(xiàng)中。只有在所有指向該page frame的頁(yè)表項(xiàng)修改完畢后才可以將該頁(yè)交換到磁盤(pán)，并且回收這個(gè)page frame。demand paging的場(chǎng)景是類(lèi)似的，只不過(guò)是需要把所有的page table entry清零，這里就不贅述了。

三、史前文明

盤(pán)古開(kāi)天辟地之前，宇宙混沌一片。對(duì)于逆向映射這個(gè)場(chǎng)景，我們的問(wèn)題就是：沒(méi)有逆向映射之前，混沌的內(nèi)核世界是怎樣的呢？這一章主要是回答這個(gè)問(wèn)題的，分析的基礎(chǔ)是2.4.18內(nèi)核的源代碼。

1、沒(méi)有逆向映射，系統(tǒng)如何運(yùn)作？

也許年輕的內(nèi)核工程師很難想象沒(méi)有逆向映射的內(nèi)核世界，但實(shí)際上2.4時(shí)期的內(nèi)核就是這樣的。讓我們想象一下，我們自己就是page reclaim機(jī)制的維護(hù)者，看看我們目前的困境：如果沒(méi)有逆向映射機(jī)制，那么struct page中沒(méi)有維護(hù)任何的逆向映射的數(shù)據(jù)。這種情況下，內(nèi)核不可能通過(guò)簡(jiǎn)單的方法來(lái)找到page frame所對(duì)應(yīng)的那些PTEs。當(dāng)回收一個(gè)被多個(gè)進(jìn)程共享的page frame，我們?cè)撛趺崔k呢？

本身回收用戶進(jìn)程的物理頁(yè)幀并不復(fù)雜，這需要memory mapping和swapping機(jī)制的支持。這兩種機(jī)制的工作原理類(lèi)似，只不過(guò)一個(gè)用于file mapped page，另外一個(gè)用于anonymous page。不過(guò)對(duì)于頁(yè)面回收而言，他們的工作原理類(lèi)似：就是把某些進(jìn)程不常使用的page frame交換到磁盤(pán)上去，同時(shí)解除進(jìn)程和這個(gè)page frame的一切關(guān)系，完成這兩步之后，這個(gè)物理頁(yè)幀已經(jīng)自由了，可以回收到伙伴系統(tǒng)中。

OK，了解了基本原理，現(xiàn)在需要看看如何具體實(shí)現(xiàn)：不常使用的page frame很好找（inactive lru鏈表），不過(guò)斷絕page frame和進(jìn)程們之間的關(guān)系很難，因?yàn)闆](méi)有逆向映射。不過(guò)這難不倒Linux內(nèi)核開(kāi)發(fā)人員，他們選擇了掃描整個(gè)系統(tǒng)的各個(gè)進(jìn)程的地址空間的方法。

2、如何對(duì)進(jìn)程地址空間進(jìn)行掃描？

下圖是一個(gè)對(duì)進(jìn)程地址空間進(jìn)行掃描的示意圖：

系統(tǒng)中的所有進(jìn)程地址空間（memory descriptor）被串成一個(gè)鏈表，鏈表頭就是init_mm，系統(tǒng)中所有的進(jìn)程地址空間都掛在了這個(gè)鏈表中。所謂scan當(dāng)然就是沿著這條mm鏈表進(jìn)行了。當(dāng)然，頁(yè)面回收算法盡量不scan整個(gè)系統(tǒng)的全部進(jìn)程地址空間，畢竟那是一個(gè)比較笨的辦法。回收算法可以考慮收縮內(nèi)存cache，也可以遍歷inactive_list來(lái)試圖完成本次reclaim數(shù)目的要求（該鏈表中有些page不和任何進(jìn)程相關(guān)），如果通過(guò)這些方法釋放了足夠多的page frame，那么一切都搞定了，不需要scan進(jìn)程地址空間。當(dāng)然，情況并非總是那么美好，有時(shí)候，必須啟動(dòng)進(jìn)程物理頁(yè)面回收過(guò)程才能滿足頁(yè)面回收的要求。

進(jìn)程物理頁(yè)面回收過(guò)程是通過(guò)調(diào)用swap_out函數(shù)完成的，而scan進(jìn)程地址空間的代碼也是開(kāi)始于這個(gè)函數(shù)。該函數(shù)是一個(gè)三層嵌套結(jié)構(gòu)：

（1） 首先沿著init_mm，對(duì)每一個(gè)進(jìn)程地址空間進(jìn)行掃描

（2） 在掃描一個(gè)進(jìn)程地址空間的時(shí)候，對(duì)屬于該進(jìn)程地址空間的每一個(gè)VMA進(jìn)行掃描

（3） 在掃描每一個(gè)VMA的時(shí)候，對(duì)屬于該VMA的每一個(gè)page進(jìn)行掃描

在掃描過(guò)程中，如果命中了進(jìn)程A的page frame0，由于該page只是被進(jìn)程A 使用（即只是被A進(jìn)程mapping），那么可直接unmap并回收該page。對(duì)于共享頁(yè)面，我們不能這么處理了，例如上圖中的page frame 1，但scan A進(jìn)程的時(shí)候，如果條件符合，那么我們會(huì)unmap該page，解除它和進(jìn)程A的關(guān)系，當(dāng)然，這時(shí)候不能回收該page，因?yàn)檫M(jìn)程X還在使用該page。直到scan過(guò)程歷經(jīng)千山萬(wàn)水來(lái)到進(jìn)程X，完成對(duì)page frame 1的unmaping操作，該物理頁(yè)面才可以真正會(huì)伙伴系統(tǒng)的懷抱。

3、地址空間掃描的細(xì)節(jié)問(wèn)題

首先，第一個(gè)問(wèn)題：到底scan多少虛擬地址空間才停止scan呢？當(dāng)目標(biāo)已經(jīng)達(dá)到的時(shí)候，例如本次scan打算reclaim 32個(gè)page frame，如果目標(biāo)達(dá)到，那么scan停止，不需scan全部虛擬地址空間。還有一種比較悲慘的情況，那就是scan了系統(tǒng)中所有的地址空間之后，仍然沒(méi)有達(dá)成目標(biāo)，這時(shí)候也就可以停止了，不過(guò)這屬于OOM的處理了。為了確保系統(tǒng)中的進(jìn)程被均勻的scan（畢竟swap out會(huì)影響進(jìn)程性能，我們肯定不能只逮住部分進(jìn)程薅其羊毛），每次scan完成后，記錄當(dāng)前scan的位置（保存在swap_mm變量），等下次又啟動(dòng)scan過(guò)程的時(shí)候，從swap_mm開(kāi)始繼續(xù)scan。

由于對(duì)性能有影響，swap out需要雨露均沾，各個(gè)進(jìn)程都跑不掉。同樣的道理，對(duì)于一個(gè)進(jìn)程的地址空間，我們一樣也是需要公平對(duì)待，因此需要保存每次scan的虛擬地址（mm->swap_address），這樣，每次重啟scan的時(shí)候，總是從swap_mm那個(gè)地址空間的mm->swap_address虛擬地址開(kāi)始scan。

具體對(duì)一個(gè)page frame進(jìn)行swap out的代碼位于try_to_swap_out函數(shù)中，在這個(gè)函數(shù)中，如果條件滿足，會(huì)解除該page frame的該進(jìn)程之間的關(guān)系，完成必要的IO操作，該page reference count減一，對(duì)應(yīng)的pte清零或者設(shè)定swap entry等。當(dāng)然，swap out一個(gè)page之后，我們并非一定能夠回收它，因?yàn)檫@個(gè)page很可能被多個(gè)進(jìn)程共享。而在scan過(guò)程中，如果碰巧找到了該page對(duì)應(yīng)的所有的頁(yè)面表?xiàng)l目，那么說(shuō)明該頁(yè)面已經(jīng)不被任何進(jìn)程引用，這時(shí)候該page frame就會(huì)被逐出磁盤(pán)，從而完成一個(gè)頁(yè)面的回收。

四、開(kāi)天辟地

時(shí)間又回到2002年1月，那時(shí)VM大神Rik van Riel遭遇了人生中的一次重大挫折，他的耗費(fèi)心血維護(hù)的代碼被一個(gè)全新的VM子系統(tǒng)取代了。不過(guò)Rik van Riel并沒(méi)有消沉下去，他在憋大招，也就是傳說(shuō)中的reverse mapping（后文簡(jiǎn)稱rmap）。本章主要描述第一個(gè)版本的rmap，代碼來(lái)自Linux 2.6.0。

1、設(shè)計(jì)概念

如何構(gòu)建rmap？最直觀的想法就是針對(duì)每一個(gè)page frame，我們維護(hù)一個(gè)鏈表，保存屬于該page的所有PTEs。因此，Rik van Riel給struct page增加了一個(gè)pte chain的成員，以便把所有mapping到該page的pte entry指針給串起來(lái)。這樣想要unmap一個(gè)page就易如反掌了，沿著這個(gè)pte chain就可以找到所有的mappings。一個(gè)基本的示意圖如下，下面的小節(jié)會(huì)給出更詳細(xì)的解釋。

2、對(duì)Struct page的修改

Struct page的修改如下：

struct page {

……

union {

struct pte_chain *chain;

pte_addr_t direct;

} pte;

……

當(dāng)然，很多頁(yè)面都不是共享的，只有一個(gè)pte entry，因此direct直接指向那個(gè)pte entry就OK了。如果存在頁(yè)面共享的情況，那么chain成員則會(huì)指向一個(gè)struct pte_chain的鏈表。

3、定義struct pte_chain

struct pte_chain {

unsigned long next_and_idx;

pte_addr_t ptes[NRPTE];

} ____cacheline_aligned;

如果pte_chain只保存一個(gè)pte entry的指針那么就太浪費(fèi)了，比較好的方法是把struct pte_chain對(duì)齊在cache line并讓整個(gè)struct pte_chain占用一個(gè)cache line。除了next_and_idx用于指向下一個(gè)pte_chain，形成鏈表之外，其余的空間都用于保存pte entry指針。由于pte entry指針形成了數(shù)組，因此我們還需要一個(gè)index指示下一個(gè)空閑的pte entry pointer的位置，由于pte_chain對(duì)齊在cache line，因此next_and_idx的LSB的若干個(gè)bit是等于0的，可以復(fù)用做index。

4、頁(yè)面回收算法的修改

在進(jìn)入基于rmap的頁(yè)面回收算法之前，讓我們先回憶一下痛苦的過(guò)去。假設(shè)一個(gè)物理頁(yè)面P被A和B兩個(gè)進(jìn)程共享，在過(guò)去，釋放P這個(gè)物理頁(yè)面需要掃描進(jìn)程地址空間，首先scan到A進(jìn)程，解除P和A進(jìn)程的關(guān)系，但是這時(shí)候不能回收，B進(jìn)程還在使用該page frame。當(dāng)然掃描過(guò)程最終會(huì)來(lái)到B進(jìn)程，只有在這時(shí)候才有機(jī)會(huì)回收這個(gè)物理頁(yè)面P。你可能會(huì)問(wèn)：如果scan B進(jìn)程地址空間的時(shí)候，A進(jìn)程又訪問(wèn)了P從而導(dǎo)致映射建立。然后scan A的時(shí)候，B進(jìn)程又再次訪問(wèn)，如此反反復(fù)復(fù)，那么P不就永遠(yuǎn)無(wú)法回收了嗎？這個(gè)怎么辦呢？這個(gè)……理論上是這樣的，別問(wèn)我，其實(shí)我也很絕望。

有了rmap，頁(yè)面回收算法頓時(shí)感覺(jué)輕松多了，只要是頁(yè)面回收算法看中的page frame，總是能夠通過(guò)try_to_unmap解除和所有進(jìn)程的關(guān)聯(lián)，從而將其回收到伙伴系統(tǒng)中。如果該page frame沒(méi)有共享（page flag設(shè)定PG_direct flag），那么page->pte.direct直接命中pte entry，調(diào)用try_to_unmap_one來(lái)進(jìn)行unmap的操作。如果映射到了多個(gè)虛擬地址空間，那么沿著pte_chain依次調(diào)用try_to_unmap_one來(lái)進(jìn)行unmap的操作。

五、女?huà)z補(bǔ)天

雖然Rik van Riel開(kāi)辟了逆向映射的新天地，但是，天和地都有著巨大的窟窿，需要有人修補(bǔ)。首先讓我們看看這個(gè)“巨大的窟窿”是什么？

在引入第一個(gè)版本的rmap之后，Linux的頁(yè)面回收變得簡(jiǎn)單、可控了，但是這個(gè)簡(jiǎn)單的設(shè)計(jì)是有代價(jià)的：每一個(gè)struct page增加一個(gè)指針成員，在32bit的系統(tǒng)上也就是增加了4B。考慮到系統(tǒng)為了管理內(nèi)存會(huì)為每一個(gè)page frame建立一個(gè)struct page對(duì)象，引入rmap而導(dǎo)致的內(nèi)存開(kāi)銷(xiāo)也不是一個(gè)小數(shù)目啊。此外，share page需要建立pte_chain鏈表，也是一個(gè)不小的內(nèi)存開(kāi)銷(xiāo)。除了內(nèi)存方面的壓力，第一個(gè)版本的rmap對(duì)性能也造成了一定的影響。例如：在fork操作的時(shí)候，父子進(jìn)程共享了很多的page frame，這樣，在copy page table的時(shí)候就會(huì)伴隨大量的pte_chain的操作，從而讓fork的速度變得緩慢。

本章就是帶領(lǐng)大家看看object-based reverse mapping（后文簡(jiǎn)稱objrmap）是如何填補(bǔ)那個(gè)“巨大的窟窿”。本章的代碼來(lái)自2.6.11版本的內(nèi)核。

1、問(wèn)題的引入

推動(dòng)rmap優(yōu)化的動(dòng)力來(lái)自內(nèi)存方面的壓力，與此相關(guān)的問(wèn)題是：32-bit的Linux內(nèi)核是否支持4G以上的memory。在1999年，Linus的決定是：32-bit的Linux內(nèi)核永遠(yuǎn)也不會(huì)支持2G以上的內(nèi)存。不過(guò)歷史的洪流不可阻擋，處理器廠商設(shè)計(jì)了擴(kuò)展模塊以便尋址更多的內(nèi)存，高端的服務(wù)器也配置了越來(lái)越多的內(nèi)存。這也迫使Linus改變之前的思路，讓Linux內(nèi)核支持更大的內(nèi)存。

紅帽公司的Andrea Arcangeli當(dāng)時(shí)正在做的工作就是讓32-bit的Linux運(yùn)行在配置超過(guò)32G內(nèi)存的公司服務(wù)器上。在這些服務(wù)器上往往啟動(dòng)大量的進(jìn)程，共享了大量的物理頁(yè)幀，消耗了大量的內(nèi)存。對(duì)于Andrea Arcangeli來(lái)說(shuō)，內(nèi)存消耗的真正元兇是明確的：逆向映射模塊，這個(gè)模塊消耗了太多的low memory，從而導(dǎo)致了系統(tǒng)的各種crash。為了讓自己的工作繼續(xù)推進(jìn)，他必須解決rmap引入的內(nèi)存擴(kuò)展性（memory scalability）問(wèn)題。

2、file mapped的優(yōu)化

并非只有Andrea Arcangeli關(guān)注到了rmap的內(nèi)存問(wèn)題，在2.5版本的開(kāi)發(fā)過(guò)程中，IBM公司的Dave McCracken就已經(jīng)提交了patch，試圖在保證逆向映射功能的基礎(chǔ)上，同時(shí)又能修正rmap帶來(lái)的各種問(wèn)題。

Dave McCracken的方案是一種基于對(duì)象的逆向映射機(jī)制。在過(guò)去，通過(guò)rmap，我們可以從struct page直接獲取其對(duì)應(yīng)的ptes，objrmap的方法借助其他的數(shù)據(jù)對(duì)象來(lái)完成從struct page檢索到其對(duì)應(yīng)ptes的過(guò)程，這個(gè)過(guò)程的示意圖如下：

對(duì)于objrmap而言，尋找一個(gè)page frame的mappings是一個(gè)比較長(zhǎng)的路徑，它借助了VMA（struct vm_area_struct）這個(gè)數(shù)據(jù)對(duì)象。我們知道對(duì)于某些page frame是有后備文件的，這種類(lèi)型的頁(yè)面和某個(gè)文件相關(guān)，例如進(jìn)程的正文段和該進(jìn)程的可執(zhí)行文件相關(guān)。此外，進(jìn)程可以調(diào)用mmap()對(duì)某個(gè)文件進(jìn)行mapping。對(duì)于這些頁(yè)幀我們稱之file mapped page。

對(duì)于這些文件映射頁(yè)面，其struct page中有一個(gè)成員mapping指向一個(gè)struct address_space，address_space是和文件相關(guān)的，它保存了文件page cache相關(guān)的信息。當(dāng)然，我們這個(gè)場(chǎng)景主要關(guān)注一個(gè)叫做i_mmap的成員。一個(gè)文件可能會(huì)被映射到多個(gè)進(jìn)程的多個(gè)VMA中，所有的這些VMA都被掛入到i_mmap指向的Priority search tree中。

當(dāng)然，我們最終的目標(biāo)是PTEs，下面這幅圖展示了如何從VMA和struct page中的信息導(dǎo)出該page frame的虛擬地址的：

而在linux kernel中，函數(shù)vma_address可以完成這個(gè)功能：

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;

}

對(duì)于file mapped page，page->index表示的是映射到文件內(nèi)的偏移（Byte為單位），而vma->vm_pgoff表示的是該VMA映射到文件內(nèi)的偏移（page為單位），因此，通過(guò)vma->vm_pgoff和page->index可以得到該page frame在VMA中的地址偏移，再加上vma->vm_start就可以得到該page frame的虛擬地址。有了虛擬地址和地址空間（vma->vm_mm），我們就可以通過(guò)各級(jí)頁(yè)表找到該page對(duì)應(yīng)的pte entry。

3、匿名頁(yè)面的優(yōu)化

我們都知道，用戶空間進(jìn)程的頁(yè)面主要有兩種，一種是file mapped page，另外一種是anonymous mapped page。Dave McCracken的objrmap方案雖好，但是只是適用于file mapped page，對(duì)于匿名映射頁(yè)面，這個(gè)方案無(wú)能為力。因此，我們必須為匿名映射頁(yè)面也設(shè)計(jì)一種基于對(duì)象的逆向映射機(jī)制，最后形成full objrmap方案。

為了解決內(nèi)存擴(kuò)展性的問(wèn)題，Andrea Arcangeli全力工作在full objrmap方案上，不過(guò)他還有一個(gè)競(jìng)爭(zhēng)對(duì)手，Hugh Dickins，同時(shí)也提交了一系列full objrmap補(bǔ)丁，試圖并入內(nèi)核主線，顯然，在匿名映射頁(yè)面上，最后勝出的是Andrea Arcangeli，他的匿名映射方案如下圖所示：

和file mapped類(lèi)似，anonymous page也是通過(guò)VMA來(lái)尋找page frame對(duì)應(yīng)的pte entry。由于文件映射頁(yè)面的VMA數(shù)量可能非常大，因此我們采用Priority search tree這樣的數(shù)據(jù)結(jié)構(gòu)。對(duì)于匿名映射頁(yè)面，其數(shù)量一般不會(huì)太大，所以使用鏈表結(jié)構(gòu)就OK了。

為了節(jié)省內(nèi)存，我們復(fù)用了struct page中的mapping指針：一個(gè)page frame如果是file mapped，其mapping指針指向?qū)?yīng)文件的address_space數(shù)據(jù)結(jié)構(gòu)。如果是anonymous page，那么mapping指針指向anon_vma數(shù)據(jù)結(jié)構(gòu)。雖然節(jié)省了內(nèi)存，但是降低了可讀性，但是由于內(nèi)核會(huì)為每一個(gè)page frame建立一個(gè)對(duì)應(yīng)的struct page數(shù)據(jù)對(duì)象，該數(shù)據(jù)結(jié)構(gòu)即便是增加4B對(duì)整個(gè)系統(tǒng)的內(nèi)存消耗都是巨大的，因此內(nèi)核還是采用了較為丑陋的方式來(lái)定義mapping這個(gè)成員。通過(guò)struct page中的mapping成員我們可以獲得該page映射相關(guān)的信息，總結(jié)如下：

（1） 等于NULL，表示該page frame不再內(nèi)存中，而是被swap out到磁盤(pán)去了。

（2） 如果不等于NULL，并且least signification bit等于1，表示該page frame是匿名映射頁(yè)面，mapping指向了一個(gè)anon_vma的數(shù)據(jù)結(jié)構(gòu)。

（3） 如果不等于NULL，并且least signification bit等于0，表示該page frame是文件映射頁(yè)面，mapping指向了一個(gè)該文件的address_space數(shù)據(jù)結(jié)構(gòu)。

通過(guò)anon_vma數(shù)據(jù)結(jié)構(gòu)，我們可以得到映射到該page的所有的VMA，至此，匿名映射和file mapped匯合，進(jìn)一步解決的問(wèn)題僅僅是如何從VMA到pte entry而已。上一節(jié)，我們描述了vma_address函數(shù)如何獲取file mapped page的虛擬地址，其實(shí)anonymous page的邏輯是一樣的，只不過(guò)vma->vm_pgoff和page->index的基礎(chǔ)點(diǎn)不一樣了，對(duì)于file mapped的場(chǎng)景，這個(gè)基礎(chǔ)點(diǎn)是文件起始位置。對(duì)于匿名映射，起始點(diǎn)有兩種情況，一種是share anonymous mapping，起點(diǎn)位置是0。另外一種是private anonymous mapping，起點(diǎn)位置是mapping的虛擬地址（除以page size）。但是不管如何，從VMA和struct page得到對(duì)應(yīng)虛擬地址的算法概念是類(lèi)似的。

六、卷土重來(lái)

full objrmap進(jìn)入內(nèi)核之后，看起來(lái)一切都很完美了，比起她的前任，Rik van Riel的rmap方案，objrmap各方面的指標(biāo)都是全面碾壓rmap。首次將逆向映射引入內(nèi)核的大神Rik van Riel遭受了第二次的打擊，不過(guò)他依然斗志昂揚(yáng)并試圖東山再起。

Objrmap雖然完美，不過(guò)晴朗的天空中飄著一朵烏云。大神Rik van Riel敏銳的看到了逆向映射的那朵“烏云“，提出了自己的解決方案。本章主要描述新的anon_vma機(jī)制，代碼來(lái)自4.4.6內(nèi)核。

1、舊anon_vma機(jī)制有什么問(wèn)題？

我們先一起來(lái)看看舊anon_vma機(jī)制下，系統(tǒng)是如何運(yùn)作的。VMA_P是父進(jìn)程的一個(gè)匿名映射的VMA，A和C都已經(jīng)分配了page frame，而其他的page都還都沒(méi)有分配物理頁(yè)面。在fork之后，子進(jìn)程copy了VMA_P，當(dāng)然由于采用了COW技術(shù)，這時(shí)候父子進(jìn)程的匿名頁(yè)面會(huì)共享，同時(shí)在父子進(jìn)程地址空間對(duì)應(yīng)的pte entry中標(biāo)注write protect的標(biāo)記，如下圖所示：

按理說(shuō)不同進(jìn)程的匿名頁(yè)面（例如stack、heap）是私有的，不會(huì)共享，但是為了節(jié)省內(nèi)存，在父進(jìn)程fork子進(jìn)程之后，父子進(jìn)程對(duì)該頁(yè)面執(zhí)行寫(xiě)操作之前，父子進(jìn)程的匿名頁(yè)是共享的，所以這些page frame指向同一個(gè)anon_vma。當(dāng)然，共享只是短暫的，一旦有write操作就會(huì)產(chǎn)生異常，并在異常處理中分配page frame，解除父子進(jìn)程匿名頁(yè)面的共享，具體如下圖的page A所示：

這時(shí)候由于寫(xiě)操作，父子進(jìn)程原本共享的page frame已經(jīng)不再共享，然而，這兩個(gè)page卻仍然指向同一個(gè)anon_vma，不僅如此，對(duì)于B這樣的頁(yè)面，一開(kāi)始就沒(méi)有在父子進(jìn)程之間共享，當(dāng)首次訪問(wèn)的時(shí)候（無(wú)論是父進(jìn)程還是子進(jìn)程），通過(guò)do_anonymous_page函數(shù)分配的page frame也是同樣的指向一個(gè)anon_vma。也就是說(shuō)，父子進(jìn)程的VMA共享一個(gè)anon_vma。

在這種情況下，我們看看unmap page frame1會(huì)發(fā)生什么。毫無(wú)疑問(wèn)，page frame1對(duì)應(yīng)的struct page的mapping成員指向了上圖中的anon_vma，遍歷anon_vma會(huì)命VMA_P和VMA_C，這里面，VMA_C是無(wú)效的VMA，本來(lái)就不應(yīng)該匹配到。如果anon_vma的鏈表沒(méi)有那么長(zhǎng)，那么整體性能也OK。然而，在有些網(wǎng)路服務(wù)器中，系統(tǒng)非常依賴fork，某個(gè)服務(wù)程序可能會(huì)fork巨大數(shù)量的子進(jìn)程來(lái)處理服務(wù)請(qǐng)求，在這種情況下，系統(tǒng)性能?chē)?yán)重下降。Rik van Riel給出了一個(gè)具體的示例：系統(tǒng)中有1000進(jìn)程，都是通過(guò)fork生成的，每個(gè)進(jìn)程的VMA有 1000個(gè)匿名頁(yè)。根據(jù)目前的軟件架構(gòu)，anon_vma鏈表中會(huì)有1000個(gè)vma 的節(jié)點(diǎn)，而系統(tǒng)中有一百萬(wàn)個(gè)匿名頁(yè)面屬于同一個(gè)anon_vma。

這樣的系統(tǒng)會(huì)導(dǎo)致什么樣的問(wèn)題呢？我們一起來(lái)看看try_to_unmap_anon函數(shù)，其代碼框架如下：

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;

}

當(dāng)系統(tǒng)中的一個(gè)CPU在執(zhí)行try_to_unmap_anon函數(shù)的時(shí)候，需要遍歷VMA鏈表，這時(shí)會(huì)持有anon_vma->lock這個(gè)自旋鎖。由于anon_vma存有了很多根本無(wú)關(guān)的VMA，通過(guò)，page table的檢索過(guò)程，你就會(huì)發(fā)現(xiàn)這個(gè)VMA根本和準(zhǔn)備unmap的page無(wú)關(guān)，因此只能scan下一個(gè)VMA，整個(gè)過(guò)程需要消耗大量的時(shí)間，延長(zhǎng)了臨界區(qū)（復(fù)雜度是O（N））。與此同時(shí)，其他CPU在試獲取這把鎖的時(shí)候，基本會(huì)被卡住，這時(shí)候整個(gè)系統(tǒng)的性能可想而知了。更加糟糕的是內(nèi)核中并非只有unmap匿名頁(yè)面的時(shí)候會(huì)上鎖、遍歷VMA鏈表，還有一些其他的場(chǎng)景也會(huì)這樣（例如page_referenced函數(shù)）。想象一下，一百萬(wàn)個(gè)頁(yè)面共享這一個(gè)anon_vma，對(duì)anon_vma->lock自旋鎖的競(jìng)爭(zhēng)那是相當(dāng)?shù)募ち野　?/p>

2、改進(jìn)的方案

舊的方案的癥結(jié)所在是anon_vma承載了太多進(jìn)程的VMA了，如果能將其變成per-process的，那么問(wèn)題就解決了。Rik van Riel的解決辦法是為每一個(gè)進(jìn)程創(chuàng)建一個(gè)anon_vma結(jié)構(gòu)并通過(guò)各種數(shù)據(jù)結(jié)構(gòu)把父子進(jìn)程的anon_vma（后面簡(jiǎn)稱AV）以及VMA鏈接在一起。為了鏈接anon_vma，內(nèi)核引入了一個(gè)新的結(jié)構(gòu)，稱為anon_vma_chain（后面簡(jiǎn)稱AVC）：

struct anon_vma_chain {

struct vm_area_struct *vma;――指向該AVC對(duì)應(yīng)的VMA

struct anon_vma *anon_vma;――指向該AVC對(duì)應(yīng)的AV

struct list_head same_vma; ――鏈接入VMA鏈表的節(jié)點(diǎn)

struct rb_node rb;―――鏈接入AV紅黑樹(shù)的節(jié)點(diǎn)

unsigned long rb_subtree_last;

};

AVC是一個(gè)神奇的結(jié)構(gòu)，每個(gè)AVC都有其對(duì)應(yīng)的VMA和AV。所有指向相同VMA的AVC會(huì)被鏈接到一個(gè)鏈表中，鏈表頭就是VMA的anon_vma_chain成員。而一個(gè)AV會(huì)管理若干的VMA，所有相關(guān)的VMA（其子進(jìn)程或者孫進(jìn)程）都掛入紅黑樹(shù)，根節(jié)點(diǎn)就是AV的rb_root成員。

這樣的描述非常枯燥，估計(jì)第一次接觸逆向映射的同學(xué)是不會(huì)明白的，不如我們一起來(lái)看看AV、AVC和VMA的“大廈”是如何搭建起來(lái)的。

3、當(dāng)VMA和VA首次相遇

由于采用了COW技術(shù)，子進(jìn)程和父進(jìn)程的匿名頁(yè)面往往是共享的，直到其中之一發(fā)起寫(xiě)操作。但是如果子進(jìn)程執(zhí)行了exec的系統(tǒng)調(diào)用，加載了自己的二進(jìn)制image，這時(shí)候，子進(jìn)程和父進(jìn)程的執(zhí)行環(huán)境（包括匿名頁(yè)面）就分道揚(yáng)鑣了（參考flush_old_exec函數(shù)），我們的場(chǎng)景就是從這么一個(gè)全新的exec后的進(jìn)程開(kāi)始。當(dāng)該進(jìn)程的匿名映射VMA通過(guò)page fault分配第一個(gè)page frame的時(shí)候，內(nèi)核會(huì)構(gòu)建下圖所示的數(shù)據(jù)關(guān)系：

上圖中的AV0就是該進(jìn)程的anon_vma，由于它是一個(gè)頂級(jí)結(jié)構(gòu)，因此它的root和parent都是指向了自己。AV這個(gè)數(shù)據(jù)結(jié)構(gòu)當(dāng)然為了管理VMA了，不過(guò)新機(jī)制中，這是通過(guò)AVC進(jìn)行中轉(zhuǎn)的。上圖中的AVC0搭建了該進(jìn)程VMA和AV之間的橋梁，分別有指針指向了VMA0和AV0，此外，AVC0插入到AV的紅黑樹(shù)，同時(shí)也會(huì)插入到VMA的鏈表中。

對(duì)于這個(gè)新分配的page frame而言，它會(huì)mapping到VMA對(duì)應(yīng)的某個(gè)虛擬地址上去，為了維護(hù)逆向映射的關(guān)系，struct page中的mapping指向了AV0，index成員指向了該page在整個(gè)VMA0中的偏移。圖中沒(méi)有畫(huà)出這個(gè)關(guān)系，主要因?yàn)檫@是老生常談了，相信大家都已經(jīng)熟悉。

VMA0中隨后可能會(huì)有若干的page frame被mapping到該VMA的某個(gè)虛擬頁(yè)面，不過(guò)上面的結(jié)構(gòu)不會(huì)變化，只不過(guò)每一個(gè)page中的mapping都指向了上圖中的AV0。另外，上圖中那個(gè)虛線綠色block的AVC0其實(shí)等于那個(gè)綠色實(shí)線的AVC0 block，也就是說(shuō)這時(shí)候該VMA只有一個(gè)anon_vma_chain，即AVC0，上圖只是方便表示該AVC也會(huì)被掛入VMA的鏈表，掛入anon_vma的紅黑樹(shù)而已。

如果想?yún)⒖枷嚓P(guān)的代碼可以仔細(xì)看看do_anonymous_page或者do_cow_fault。

4、在fork的時(shí)候，匿名映射的VMA經(jīng)歷了什么？

一旦fork，那么子進(jìn)程會(huì)copy父進(jìn)程的VMA（參考函數(shù)dup_mmap），子進(jìn)程會(huì)有自己的VMA，同時(shí)也會(huì)分配自己的AV（舊的機(jī)制下，多個(gè)進(jìn)程共享一個(gè)AV，而新的機(jī)制中，AV是per process的），然后建立父子進(jìn)程之間的VMA、VA的“大廈”，主要的步驟如下：

（1） 調(diào)用anon_vma_clone函數(shù)，建立子進(jìn)程VMA和“父進(jìn)程們”VA的關(guān)系

（2） 建立子進(jìn)程VMA和子進(jìn)程VA的關(guān)系

怎樣叫做建立VMA和VA的關(guān)系？其實(shí)就是anon_vma_chain_link函數(shù)的調(diào)用過(guò)程，步驟如下：

（1） 分配一個(gè)AVC結(jié)構(gòu)，成員指針指向?qū)?yīng)的VMA和VA

（2） 將該AVC加入VMA鏈表

（3） 將該AVC加入VA紅黑樹(shù)

我們一開(kāi)始先別把事情搞得太復(fù)雜，先看看一個(gè)全新進(jìn)程fork子進(jìn)程的場(chǎng)景。這時(shí)候，內(nèi)核會(huì)構(gòu)建下圖所示的數(shù)據(jù)關(guān)系：

首先看看如何建立子進(jìn)程VMA1和父進(jìn)程AV0的關(guān)系，這里需要遍歷VMA0的anon_vma_chain鏈表，當(dāng)然現(xiàn)在這個(gè)鏈表只有一個(gè)AVC0（link到AV0），為了建立和父進(jìn)程的聯(lián)系，我們分配了AVC_x01，它是一個(gè)橋梁，連接了父子進(jìn)程。（注：AVC_x01中的x表示連接，01表示連接level 0和level 1）。通過(guò)這個(gè)橋梁，父進(jìn)程可以找到子進(jìn)程的VMA（因?yàn)锳VC_x01插入AV0的紅黑樹(shù)中），而子進(jìn)程也可以找到父進(jìn)程的AV（因?yàn)锳VC_x01插入VMA1的鏈表中）。

當(dāng)然，自己的anon_vma也需要?jiǎng)?chuàng)建。在上圖中，AV1就是子進(jìn)程的anon_vma，同時(shí)分配一個(gè)AVC1來(lái)連接該子進(jìn)程的VMA1和AV1，并調(diào)用anon_vma_chain_link函數(shù)將AVC1插入VMA1的鏈表和AV1的紅黑樹(shù)中。

父進(jìn)程也會(huì)創(chuàng)建其他新的子進(jìn)程，新創(chuàng)建的子進(jìn)程的層次和VMA1、VA1的類(lèi)似，這里就不描述了。不過(guò)需要注意的是：父進(jìn)程每創(chuàng)建一個(gè)子進(jìn)程，AV0的紅黑樹(shù)中會(huì)增加每一個(gè)起“橋梁”作用的AVC，以此連接到子進(jìn)程的VMA。

5、構(gòu)建三層大廈

上一節(jié)描述了父進(jìn)程創(chuàng)建子進(jìn)程的情況，如果子進(jìn)程再次fork，那么整個(gè)VMA-VA的大廈將形成三層結(jié)構(gòu)，具體如下圖所示：

當(dāng)然，首先要進(jìn)行的仍然是建立孫進(jìn)程VMA和“父進(jìn)程們”VA的關(guān)系，這里的“父進(jìn)程們”其實(shí)是泛指孫進(jìn)程的上層的那些進(jìn)程們。對(duì)于這個(gè)場(chǎng)景，“父進(jìn)程們”指的就是上圖中的A進(jìn)程和B進(jìn)程。如何建立？在fork的時(shí)候，我們進(jìn)行VMA的拷貝：即分配VMA2并以VMA1為原型copy到VMA2中。Copy是沿著VMA1的AVC鏈表進(jìn)行的，該鏈表有兩個(gè)元素：AVC1和 AVC_x01，分別和父進(jìn)程A和子進(jìn)程B的AV關(guān)聯(lián)。因此，在孫進(jìn)程C中，我們會(huì)分配AVC_x02和AVC_x12兩個(gè)AVC，并建立level 2層和level 0層以及l(fā)evel 1層之間的關(guān)系。

同樣的，自己level的anon_vma也需要?jiǎng)?chuàng)建。在上圖中，AV2就是孫進(jìn)程C的anon_vma，同時(shí)分配一個(gè)AVC2來(lái)連接該孫進(jìn)程的VMA2和AV2，并調(diào)用anon_vma_chain_link函數(shù)將AVC2插入VMA2的鏈表和AV2的紅黑樹(shù)中。

AV2中的root指向root AV，也就是進(jìn)程A的AV。Parent成員指向其B進(jìn)程（C的父進(jìn)程）的AV。通過(guò)Parent這樣的指針，不同level的AV建立了父子關(guān)系，而通過(guò)root指針，每一個(gè)level的AV都可以尋找找到root AV。

6、page frame是如何加入“大廈”中？

前面幾個(gè)小節(jié)重點(diǎn)討論了hierarchy AV的結(jié)構(gòu)是如何搭建起來(lái)的，也就是描述fork的過(guò)程中，父子進(jìn)程的VMA、AVC和AV是如何聯(lián)系的。本小節(jié)我們將一起來(lái)看看父子進(jìn)程之一訪問(wèn)頁(yè)面，發(fā)生了page fault的處理過(guò)程。這個(gè)處理過(guò)程有兩個(gè)場(chǎng)景，一個(gè)是父子進(jìn)程都沒(méi)有page frame，這時(shí)候，內(nèi)核代碼會(huì)調(diào)用do_anonymous_page分配page frame并調(diào)用page_add_new_anon_rmap函數(shù)建立該page和對(duì)應(yīng)VMA的關(guān)系。第二個(gè)場(chǎng)景復(fù)雜一點(diǎn)，是父子共享匿名頁(yè)面的場(chǎng)景，當(dāng)發(fā)生write fault的時(shí)候，也是分配page frame并調(diào)用page_add_new_anon_rmap函數(shù)建立該page和對(duì)應(yīng)VMA的關(guān)系，具體代碼位于do_wp_page函數(shù)。無(wú)論哪一個(gè)場(chǎng)景，最終都是將該page的mapping成員指向了該進(jìn)程所屬的AV結(jié)構(gòu)。

7、為何建立如此復(fù)雜的“大廈”？

如果你能堅(jiān)持讀到這里，那么說(shuō)明你對(duì)枯燥文字的忍受能力還是很強(qiáng)的，哈哈。Page、VMA、VAC、VA組成了如此復(fù)雜的層次結(jié)構(gòu)到底是為什么呢？是為了打擊你學(xué)習(xí)內(nèi)核的興趣嗎？非也，讓我們還是用一個(gè)實(shí)際的場(chǎng)景來(lái)說(shuō)明這個(gè)“大廈”的功能。

我們通過(guò)下面的步驟建立起上圖的結(jié)構(gòu)：

（1） P進(jìn)程的某個(gè)VMA中有兩類(lèi)頁(yè)面： 一類(lèi)是有真實(shí)的物理頁(yè)面的，另外一類(lèi)是還沒(méi)有配備物理頁(yè)面的。上圖中，我們分別跟蹤有物理頁(yè)面的A以及還沒(méi)有分配物理頁(yè)面的B。

（2） P進(jìn)程fork了P1和P2

（3） P1進(jìn)程fork了P12進(jìn)程

（4） P1進(jìn)程訪問(wèn)了A頁(yè)面，分配了page frame2

（5） P12進(jìn)程訪問(wèn)了B頁(yè)面，分配了page frame3

（6） P2進(jìn)程訪問(wèn)了B頁(yè)面，分配了page frame1

（7） P2進(jìn)程fork了P21進(jìn)程

經(jīng)過(guò)上面的這一些動(dòng)作之后，我們來(lái)看看page frame共享的情況：對(duì)于P進(jìn)程的page frame（是指該page 的mapping成員指向P進(jìn)程的AV，即上圖中的AV_P）而言，他可能會(huì)被任何一個(gè)level的的子進(jìn)程VMA中的page所有共享，因此AV_P需要包括其子進(jìn)程、孫進(jìn)程……的所有的VMA。而對(duì)于P1進(jìn)程而言，AV_P1則需要包括P1子進(jìn)程、孫進(jìn)程……的所有的VMA，有一點(diǎn)可以確認(rèn)：至少父進(jìn)程P和兄弟進(jìn)程P2的VMA不需要包括在其中。

現(xiàn)在我們回頭看看AV結(jié)構(gòu)的大廈，實(shí)際上是符合上面的需求的。

8、頁(yè)面回收的時(shí)候，如何unmap一個(gè)page frame的所有的映射？

搭建了那么復(fù)雜的數(shù)據(jù)結(jié)構(gòu)大廈就是為了應(yīng)用，我們一起看看頁(yè)面回收的場(chǎng)景。這個(gè)場(chǎng)景需要通過(guò)page frame找到所有映射到該物理頁(yè)面的VMAs。有了前面的鋪墊，這并不復(fù)雜，通過(guò)struct page中的mapping成員可以找到該page對(duì)應(yīng)的AV，在該AV的紅黑樹(shù)中，包含了所有的可能共享匿名頁(yè)面的VMAs。遍歷該紅黑樹(shù)，對(duì)每一個(gè)VMA調(diào)用try_to_unmap_one函數(shù)就可以解除該物理頁(yè)幀的所有映射。

OK，我們?cè)俅位氐竭@一章的開(kāi)始，看看那個(gè)長(zhǎng)臨界區(qū)導(dǎo)致的性能問(wèn)題。假設(shè)我們的服務(wù)器上有一個(gè)服務(wù)進(jìn)程A，它fork了999個(gè)子進(jìn)程來(lái)為世界各地的網(wǎng)友服務(wù)，進(jìn)程A有一個(gè)VMA，有1000個(gè)page。下面我們就一起來(lái)對(duì)比新舊機(jī)制的處理過(guò)程。

首先，百萬(wàn)page共享一個(gè)anon_vma的情況在新機(jī)制中已經(jīng)解決，每一個(gè)進(jìn)程都有自己特有的anon_vma對(duì)象，每一個(gè)進(jìn)程的page都指向自己特有的anon_vma對(duì)象。在舊的機(jī)制中，每次unmap一個(gè)page都需要掃描1000個(gè)VMA，而在新的機(jī)制中，只有頂層的父進(jìn)程A的AV中有1000個(gè)VMA，其他的子進(jìn)程的VMA的數(shù)目都只有1個(gè)，這大大降低了臨界區(qū)的長(zhǎng)度。

七、后記

本文帶領(lǐng)大家一起簡(jiǎn)略的了解了逆向映射的發(fā)展過(guò)程。當(dāng)然，時(shí)間的車(chē)輪永不停息，逆向映射機(jī)制還在不斷的修正，如果你愿意，也可以了解其演進(jìn)過(guò)程的基礎(chǔ)上，提出自己的優(yōu)化方案，在其歷史上留下自己的印記。