深入剖析Linux內核反向映射機制

作者簡介

Cheetah，曾為U-boot社區和Linux內核社區提交過若干補丁，主要從事Linux相關系統軟體開發作業，負責Soc芯片BringUp及系統軟體開發，喜歡閱讀內核源代碼，在不斷的學習和作業中深入理解記憶體管理，行程調度，檔案系統，設備驅動等內核子系統，

為了系統的安全性，Linux內核將各個用戶行程運行在各自獨立的虛擬地址空間，用戶行程之間通過虛擬地址空間相互隔離，不能相互訪問，一個行程的奔潰不會影響到整個系統的例外也不會干擾到系統以及其他行程運行，

Linux內核可以通過共享記憶體的方式為系統節省大量記憶體，例如fork子行程的時候，父子行程通過只讀的方式共享所有的私有頁面，再比如通過IPC共享記憶體方式，各個不相干的行程直接可以共享一塊物理記憶體等等，

我們都知道作業系統開啟mmu之后cpu訪問到的都是虛擬地址，當cpu訪問一個虛擬地址的時候需要通過mmu將虛擬地址轉化為物理地址，這叫做正向映射，而與本文相關的是反向映射，它主要是通過物理頁來找到共享這個頁的所有的vma對應的頁表項，這是本文討論的問題，

本文目錄：
1.反向映射的發展
2.反向映射應用場景
3.匿名頁的反向映射
4.檔案頁的反向映射
5.ksm頁的反向映射
5.總結

注：反向映射機制是Linux內核虛擬記憶體管理的難點也是理解記憶體管理的關鍵技術之一！！

1.反向映射的發展

實際上在早期的Linux內核版本中是沒有反向映射的這個概念的，那個時候為了找到一個物理頁面對應的頁表項就需要遍歷系統中所有的mm組成的鏈表，然后對于每一個mm再遍歷每一個vma，然后查看這個vma是否映射了這頁，這個程序極其漫長而低效，有的時候不得不遍歷完所有的mm然后才能找映射到這個頁的所有pte，

后來人們發現了這個問題，就再描述物理頁面的page結構體中增加一個指標的方式來解決，通過這個指標來找到一個描述映射這個頁的所有pte的陣列結構，這對于反向映射查找所有pte易如反掌，但是帶來的是浪費記憶體的問題，

接著就在2.6內核的時候，內核大神們想到了復用page結構中的mapping欄位，然后通過紅黑樹的方式來組織所有映射這個頁的vma,形成了匿名頁和檔案頁的反向映射機制，

如下為匿名頁反向映射圖解：

如下為檔案頁反向映射圖解：

但是后來匿名頁的反向映射遇到了效率和鎖競爭激烈問題，就促使了目前使用的通過avc的方式聯系各層級反向映射結構然后將鎖的粒度降低的這種方式，可以看到反向映射的發展是伴隨著Linux內核的發展而發展，是一個不斷進行優化演進的程序，

2.反向映射應用場景

那么為何在Linux內核中需要反向映射這種機制呢？它究竟為了解決什么樣的問題而產生的呢？

試想有如下場景：
（1）一個物理頁面被多個行程的vma所映射，系統程序中發生了記憶體不足，需要回收一些頁面，正好發現這個頁面是適合我們回收利用的，我們能夠直接把這個頁面還給伙伴系統嗎？答案肯定是不能，因為這個頁面被很多個行程所共享，我們必須做的事情就是斷開這個頁面的所以映射關系，這就是反向映射所做的事情，
（2）一些情況我們需要將一個頁面遷移到另一個頁面，但是牽一發而動全身，可能有一些行程已經映射這個即將要遷移的頁面到自己的vma中，那么這個時候同樣需要我們知道究竟這個頁面被哪些vma所映射呢？這同樣是反向映射所做的事情，

實際上，反向映射的主要應用場景為記憶體回收和頁面遷移，當系統發生記憶體回收和頁面遷移的時候，對于每一個候選頁Linux內核都會判斷是否為映射頁，如果是，就會呼叫try_to_unmap 來解除頁表映射關系，本文也主要來從try_to_unmap函式來解讀反向映射機制，

如果我們在細致到其他的內核子系統會發現，在記憶體回收，記憶體碎片整理，CMA, 巨型頁，頁遷移等各個場景中都能發現反向映射所做的關鍵性的作業，所有理解反向映射機制在Linux內核中的實作是理解掌握這些子系統的基礎和關鍵性所在，否則你即將不能理解這些技術背后的脊髓所在，所以說理解反向映射這種機制對于理解Linux內核記憶體管理是至關重要的！！！

3.匿名頁的反向映射

匿名頁的共享主要發生在父行程fork子行程的時候，父fork子行程時，會復制所有vma給子行程，并通過呼叫dup_mmap->anon_vma_fork建立子行程的rmap以及和長輩行程rmap關系結構：

主要通過anon_vma這個資料結構體中的紅黑樹將共享父行程的頁的所有子行程的vma聯系起來（通過anon_vma_chain 來聯系對應的vma和av），當然這個關系建立比較復雜，涉及到vma,avc和av這些資料結構體，.

而在缺頁例外do_anonymous_page的時候將page和vma相關聯，

當記憶體回識訓頁面遷移的時候，內核路徑最侄訓呼叫到：

try_to_unmap //mm/rmap.c
->rmap_walk
  ->rmap_walk_anon
     ->anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root,pgoff_start, pgoff_end)
         ->rwc->rmap_one
			->try_to_unmap_one

對于候選頁，會拿到候選頁相關聯的anon_vma，然后從anon_vma的紅黑樹中遍歷到所有共享這個頁的vma，然后對于每一個vma通過try_to_unmap_one來處理相對應的頁表項，將映射關系解除，

4.檔案頁的反向映射

檔案頁的共享主要發生在多個行程共享libc庫，同一個庫檔案可以只需要讀取到page cache一次，然后通過各個行程的頁表映射到各個行程的vma中，

管理共享檔案頁的所以vma是通過address_space的區間樹來管理，在mmap或者fork的時候將vma加入到這顆區間樹中：

發生檔案映射缺頁例外的時候，將page和address_space相關聯，

當記憶體回識訓頁面遷移的時候，內核路徑最侄訓呼叫到：

try_to_unmap //mm/rmap.c
->rmap_walk
  ->rmap_walk_file
    ->vma_interval_tree_foreach(vma, &mapping>i_mmap,pgoff_start, pgoff_end) 
         ->rwc->rmap_one

對于每一個候選的檔案頁，如果是映射頁，就會遍歷page所對應的address_space的區間樹，對于每一個滿足條件的vma，呼叫try_to_unmap_one來找到pte并解除映射關系，

5.ksm頁的反向映射

ksm機制是內核將頁面內容完全相同的頁面進行合并（ksm管理的都是匿名頁），將映射到這個頁面的頁表項標記為只讀，然后釋放掉原來的頁表，來達到節省大量記憶體的目的，這對于host中開多個虛擬機的應用場景非常有用，

ksm機制中會管理兩課紅黑樹，一棵是stable tree,一棵是unstable tree，stable tree中的每個節點stable_node中管理的頁面都是頁面內容完全相同的頁面（被叫做kpage）,共享kpage的頁面的頁表項都會標記為只讀，而且對于原來的候選頁都會有rmap_item來描述他的反向映射（其中的anon_vma成員的紅黑樹是描述映射這個候選頁的所有vma的集合），合并的時候會加入到對應的stable tree節點和鏈表中，

當記憶體回識訓頁面遷移的時候，內核路徑最侄訓呼叫到：

try_to_unmap //mm/rmap.c
->rmap_walk
   ->rmap_walk_ksm  //mm/ksm.c
        -> hlist_for_each_entry(rmap_item, &stable_node->hlist, hlist)
 	->anon_vma_interval_tree_foreach(vmac, &anon_vma->rb_root,0, ULONG_MAX) 
	  ->rwc->rmap_one

對于一個ksm頁面，反向映射的時候，會拿到ksm頁面對應的節點，然后遍歷節點的hlist鏈表，拿到每一個anon_vma，然后就和上面介紹的匿名頁的反向映射一樣了，從anon_vma的紅黑樹中找到所有的vma，最后try_to_unmap_one來找到pte并解除映射關系，

6.總結

前面我們介紹了反向映射的三種型別，匿名頁，檔案頁和ksm頁的反向映射,分別通過page所對應的的vma, address_space, stable_node結構來查找vma，當然我們只是介紹了Linux內核中的反向映射的冰山一角，主要是try_to_unmap函式，其實每種反向映射各個資料結構建立的程序錯綜復雜，一篇文章三言兩語也說不清楚，他們散落在Linux內核源代碼的行程創建fork，記憶體映射mmap,缺頁例外處理，檔案系統等各個角落，

誠然，如果我們搞不清楚各種反正映射所對應的各種資料結構之間的關系，或者只是有一些概念上的了解，并沒有真正掌握這種機制的實作原理，對于我們來理解Linux內核虛擬記憶體管理來說是一種障礙，不懂得反向映射記憶體管理 中的很多問題是搞不明白的！

（END）

相關閱讀：《深入剖析Linux內核反向映射機制》在線視頻
更多精彩，盡在"Linux閱碼場"，掃描下方二維碼關注