一、前言

數學大師陳省身有一句話是這樣說的：了解歷史的變化是了解這門學科的一個步驟。今天，我把這句話應用到一個具體的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個，這大大降低了臨界區的長度。

七、后記

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