一、前言

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

二、基礎(chǔ)知識

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

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

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

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

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

2、為何需要逆向映射？

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

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

三、史前文明

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

1、沒有逆向映射，系統(tǒng)如何運作？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、開天辟地

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

1、設(shè)計概念

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

2、對Struct page的修改

Struct page的修改如下：

struct page {

……

union {

struct pte_chain *chain;

pte_addr_t direct;

} pte;

……

當(dāng)然，很多頁面都不是共享的，只有一個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指針形成了數(shù)組，因此我們還需要一個index指示下一個空閑的pte entry pointer的位置，由于pte_chain對齊在cache line，因此next_and_idx的LSB的若干個bit是等于0的，可以復(fù)用做index。

4、頁面回收算法的修改

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

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

五、女媧補天

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

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

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

1、問題的引入

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

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

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

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

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

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

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

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

而在linux kernel中，函數(shù)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表示的是映射到文件內(nèi)的偏移（Byte為單位），而vma->vm_pgoff表示的是該VMA映射到文件內(nèi)的偏移（page為單位），因此，通過vma->vm_pgoff和page->index可以得到該page frame在VMA中的地址偏移，再加上vma->vm_start就可以得到該page frame的虛擬地址。有了虛擬地址和地址空間（vma->vm_mm），我們就可以通過各級頁表找到該page對應(yīng)的pte entry。

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

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

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

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

為了節(jié)省內(nèi)存，我們復(fù)用了struct page中的mapping指針：一個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)核會為每一個page frame建立一個對應(yīng)的struct page數(shù)據(jù)對象，該數(shù)據(jù)結(jié)構(gòu)即便是增加4B對整個系統(tǒng)的內(nèi)存消耗都是巨大的，因此內(nèi)核還是采用了較為丑陋的方式來定義mapping這個成員。通過struct page中的mapping成員我們可以獲得該page映射相關(guān)的信息，總結(jié)如下：

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

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

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

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

六、卷土重來

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

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

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

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

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

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

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

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

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

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

struct anon_vma_chain {

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

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

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

struct rb_node rb;―――鏈接入AV紅黑樹的節(jié)點

unsigned long rb_subtree_last;

};

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

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

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

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

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

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

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

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

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

一旦fork，那么子進(jìn)程會copy父進(jìn)程的VMA（參考函數(shù)dup_mmap），子進(jìn)程會有自己的VMA，同時也會分配自己的AV（舊的機(jī)制下，多個進(jìn)程共享一個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)系？其實就是anon_vma_chain_link函數(shù)的調(diào)用過程，步驟如下：

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

（2） 將該AVC加入VMA鏈表

（3） 將該AVC加入VA紅黑樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8、頁面回收的時候，如何unmap一個page frame的所有的映射？

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

OK，我們再次回到這一章的開始，看看那個長臨界區(qū)導(dǎo)致的性能問題。假設(shè)我們的服務(wù)器上有一個服務(wù)進(jìn)程A，它fork了999個子進(jìn)程來為世界各地的網(wǎng)友服務(wù)，進(jìn)程A有一個VMA，有1000個page。下面我們就一起來對比新舊機(jī)制的處理過程。

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

七、后記

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