深入剖析Linux內(nèi)核反向映射機(jī)制

Cheetah，曾為 U-boot 社區(qū)和 Linux 內(nèi)核社區(qū)提交過(guò)若干補(bǔ)丁，主要從事 Linux 相關(guān)系統(tǒng)軟件開(kāi)發(fā)工作，負(fù)責(zé) Soc 芯片 BringUp 及系統(tǒng)軟件開(kāi)發(fā)，喜歡閱讀內(nèi)核源代碼，在不斷的學(xué)習(xí)和工作中深入理解內(nèi)存管理，進(jìn)程調(diào)度，文件系統(tǒng)，設(shè)備驅(qū)動(dòng)等內(nèi)核子系統(tǒng)。

為了系統(tǒng)的安全性，Linux 內(nèi)核將各個(gè)用戶進(jìn)程運(yùn)行在各自獨(dú)立的虛擬地址空間，用戶進(jìn)程之間通過(guò)虛擬地址空間相互隔離，不能相互訪問(wèn)，一個(gè)進(jìn)程的奔潰不會(huì)影響到整個(gè)系統(tǒng)的異常也不會(huì)干擾到系統(tǒng)以及其他進(jìn)程運(yùn)行。

Linux 內(nèi)核可以通過(guò)共享內(nèi)存的方式為系統(tǒng)節(jié)省大量?jī)?nèi)存，例如 fork 子進(jìn)程的時(shí)候，父子進(jìn)程通過(guò)只讀的方式共享所有的私有頁(yè)面。再比如通過(guò) IPC 共享內(nèi)存方式，各個(gè)不相干的進(jìn)程直接可以共享一塊物理內(nèi)存等等。

?

我們都知道操作系統(tǒng)開(kāi)啟 mmu 之后 cpu 訪問(wèn)到的都是虛擬地址，當(dāng) cpu 訪問(wèn)一個(gè)虛擬地址的時(shí)候需要通過(guò) mmu 將虛擬地址轉(zhuǎn)化為物理地址，這叫做正向映射。而與本文相關(guān)的是反向映射，它主要是通過(guò)物理頁(yè)來(lái)找到共享這個(gè)頁(yè)的所有的 vma 對(duì)應(yīng)的頁(yè)表項(xiàng)，這是本文討論的問(wèn)題。

本文目錄：
1. 反向映射的發(fā)展
2. 反向映射應(yīng)用場(chǎng)景
3. 匿名頁(yè)的反向映射
4. 文件頁(yè)的反向映射
5.ksm 頁(yè)的反向映射
5. 總結(jié)

注：反向映射機(jī)制是 Linux 內(nèi)核虛擬內(nèi)存管理的難點(diǎn)也是理解內(nèi)存管理的關(guān)鍵技術(shù)之一！！

?

1. 反向映射的發(fā)展

實(shí)際上在早期的 Linux 內(nèi)核版本中是沒(méi)有反向映射的這個(gè)概念的，那個(gè)時(shí)候?yàn)榱苏业揭粋€(gè)物理頁(yè)面對(duì)應(yīng)的頁(yè)表項(xiàng)就需要遍歷系統(tǒng)中所有的 mm 組成的鏈表，然后對(duì)于每一個(gè) mm 再遍歷每一個(gè) vma，然后查看這個(gè) vma 是否映射了這頁(yè)，這個(gè)過(guò)程極其漫長(zhǎng)而低效，有的時(shí)候不得不遍歷完所有的 mm 然后才能找映射到這個(gè)頁(yè)的所有 pte。

后來(lái)人們發(fā)現(xiàn)了這個(gè)問(wèn)題，就再描述物理頁(yè)面的 page 結(jié)構(gòu)體中增加一個(gè)指針的方式來(lái)解決，通過(guò)這個(gè)指針來(lái)找到一個(gè)描述映射這個(gè)頁(yè)的所有 pte 的數(shù)組結(jié)構(gòu)，這對(duì)于反向映射查找所有 pte 易如反掌，但是帶來(lái)的是浪費(fèi)內(nèi)存的問(wèn)題。

接著就在 2.6 內(nèi)核的時(shí)候，內(nèi)核大神們想到了復(fù)用 page 結(jié)構(gòu)中的 mapping 字段，然后通過(guò)紅黑樹(shù)的方式來(lái)組織所有映射這個(gè)頁(yè)的 vma,形成了匿名頁(yè)和文件頁(yè)的反向映射機(jī)制。

如下為匿名頁(yè)反向映射圖解：

?

如下為文件頁(yè)反向映射圖解：

但是后來(lái)匿名頁(yè)的反向映射遇到了效率和鎖競(jìng)爭(zhēng)激烈問(wèn)題，就促使了目前使用的通過(guò) avc 的方式聯(lián)系各層級(jí)反向映射結(jié)構(gòu)然后將鎖的粒度降低的這種方式?？梢钥吹椒聪蛴成涞陌l(fā)展是伴隨著 Linux 內(nèi)核的發(fā)展而發(fā)展，是一個(gè)不斷進(jìn)行優(yōu)化演進(jìn)的過(guò)程。

?

2. 反向映射應(yīng)用場(chǎng)景

那么為何在 Linux 內(nèi)核中需要反向映射這種機(jī)制呢？它究竟為了解決什么樣的問(wèn)題而產(chǎn)生的呢？

試想有如下場(chǎng)景：

（1）一個(gè)物理頁(yè)面被多個(gè)進(jìn)程的 vma 所映射，系統(tǒng)過(guò)程中發(fā)生了內(nèi)存不足，需要回收一些頁(yè)面，正好發(fā)現(xiàn)這個(gè)頁(yè)面是適合我們回收利用的，我們能夠直接把這個(gè)頁(yè)面還給伙伴系統(tǒng)嗎？答案肯定是不能。因?yàn)檫@個(gè)頁(yè)面被很多個(gè)進(jìn)程所共享，我們必須做的事情就是斷開(kāi)這個(gè)頁(yè)面的所以映射關(guān)系，這就是反向映射所做的事情。

（2）一些情況我們需要將一個(gè)頁(yè)面遷移到另一個(gè)頁(yè)面，但是牽一發(fā)而動(dòng)全身，可能有一些進(jìn)程已經(jīng)映射這個(gè)即將要遷移的頁(yè)面到自己的 vma 中，那么這個(gè)時(shí)候同樣需要我們知道究竟這個(gè)頁(yè)面被哪些 vma 所映射呢？這同樣是反向映射所做的事情。

實(shí)際上，反向映射的主要應(yīng)用場(chǎng)景為內(nèi)存回收和頁(yè)面遷移，當(dāng)系統(tǒng)發(fā)生內(nèi)存回收和頁(yè)面遷移的時(shí)候，對(duì)于每一個(gè)候選頁(yè) Linux 內(nèi)核都會(huì)判斷是否為映射頁(yè)，如果是，就會(huì)調(diào)用 try_to_unmap 來(lái)解除頁(yè)表映射關(guān)系，本文也主要來(lái)從 try_to_unmap 函數(shù)來(lái)解讀反向映射機(jī)制。

如果我們?cè)诩?xì)致到其他的內(nèi)核子系統(tǒng)會(huì)發(fā)現(xiàn)，在內(nèi)存回收，內(nèi)存碎片整理，CMA, 巨型頁(yè)，頁(yè)遷移等各個(gè)場(chǎng)景中都能發(fā)現(xiàn)反向映射所做的關(guān)鍵性的工作，所有理解反向映射機(jī)制在 Linux 內(nèi)核中的實(shí)現(xiàn)是理解掌握這些子系統(tǒng)的基礎(chǔ)和關(guān)鍵性所在，否則你即將不能理解這些技術(shù)背后的脊髓所在，所以說(shuō)理解反向映射這種機(jī)制對(duì)于理解 Linux 內(nèi)核內(nèi)存管理是至關(guān)重要的?。?！

?

3. 匿名頁(yè)的反向映射

匿名頁(yè)的共享主要發(fā)生在父進(jìn)程 fork 子進(jìn)程的時(shí)候，父 fork 子進(jìn)程時(shí)，會(huì)復(fù)制所有 vma 給子進(jìn)程，并通過(guò)調(diào)用 dup_mmap->anon_vma_fork 建立子進(jìn)程的 rmap 以及和長(zhǎng)輩進(jìn)程 rmap 關(guān)系結(jié)構(gòu)：

?

主要通過(guò) anon_vma 這個(gè)數(shù)據(jù)結(jié)構(gòu)體中的紅黑樹(shù)將共享父進(jìn)程的頁(yè)的所有子進(jìn)程的 vma 聯(lián)系起來(lái)（通過(guò) anon_vma_chain 來(lái)聯(lián)系對(duì)應(yīng)的 vma 和 av），當(dāng)然這個(gè)關(guān)系建立比較復(fù)雜，涉及到 vma,avc 和 av 這些數(shù)據(jù)結(jié)構(gòu)體。.

而在缺頁(yè)異常 do_anonymous_page 的時(shí)候?qū)?page 和 vma 相關(guān)聯(lián)。

當(dāng)內(nèi)存回收或頁(yè)面遷移的時(shí)候，內(nèi)核路徑最終會(huì)調(diào)用到：

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

對(duì)于候選頁(yè)，會(huì)拿到候選頁(yè)相關(guān)聯(lián)的 anon_vma，然后從 anon_vma 的紅黑樹(shù)中遍歷到所有共享這個(gè)頁(yè)的 vma，然后對(duì)于每一個(gè) vma 通過(guò) try_to_unmap_one 來(lái)處理相對(duì)應(yīng)的頁(yè)表項(xiàng)，將映射關(guān)系解除。

?

4. 文件頁(yè)的反向映射

文件頁(yè)的共享主要發(fā)生在多個(gè)進(jìn)程共享 libc 庫(kù)，同一個(gè)庫(kù)文件可以只需要讀取到 page cache 一次，然后通過(guò)各個(gè)進(jìn)程的頁(yè)表映射到各個(gè)進(jìn)程的 vma 中。

?

管理共享文件頁(yè)的所以 vma 是通過(guò) address_space 的區(qū)間樹(shù)來(lái)管理，在 mmap 或者 fork 的時(shí)候?qū)?vma 加入到這顆區(qū)間樹(shù)中：

發(fā)生文件映射缺頁(yè)異常的時(shí)候，將 page 和 address_space 相關(guān)聯(lián)。

當(dāng)內(nèi)存回收或頁(yè)面遷移的時(shí)候，內(nèi)核路徑最終會(huì)調(diào)用到：

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

對(duì)于每一個(gè)候選的文件頁(yè)，如果是映射頁(yè)，就會(huì)遍歷 page 所對(duì)應(yīng)的 address_space 的區(qū)間樹(shù)，對(duì)于每一個(gè)滿足條件的 vma，調(diào)用 try_to_unmap_one 來(lái)找到 pte 并解除映射關(guān)系。

?

5.ksm 頁(yè)的反向映射

ksm 機(jī)制是內(nèi)核將頁(yè)面內(nèi)容完全相同的頁(yè)面進(jìn)行合并（ksm 管理的都是匿名頁(yè)），將映射到這個(gè)頁(yè)面的頁(yè)表項(xiàng)標(biāo)記為只讀，然后釋放掉原來(lái)的頁(yè)表，來(lái)達(dá)到節(jié)省大量?jī)?nèi)存的目的，這對(duì)于 host 中開(kāi)多個(gè)虛擬機(jī)的應(yīng)用場(chǎng)景非常有用。

ksm 機(jī)制中會(huì)管理兩課紅黑樹(shù)，一棵是 stable tree,一棵是 unstable tree，stable tree 中的每個(gè)節(jié)點(diǎn) stable_node 中管理的頁(yè)面都是頁(yè)面內(nèi)容完全相同的頁(yè)面（被叫做 kpage）,共享 kpage 的頁(yè)面的頁(yè)表項(xiàng)都會(huì)標(biāo)記為只讀，而且對(duì)于原來(lái)的候選頁(yè)都會(huì)有 rmap_item 來(lái)描述他的反向映射（其中的 anon_vma 成員的紅黑樹(shù)是描述映射這個(gè)候選頁(yè)的所有 vma 的集合），合并的時(shí)候會(huì)加入到對(duì)應(yīng)的 stable tree 節(jié)點(diǎn)和鏈表中。

當(dāng)內(nèi)存回收或頁(yè)面遷移的時(shí)候，內(nèi)核路徑最終會(huì)調(diào)用到：

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

對(duì)于一個(gè) ksm 頁(yè)面，反向映射的時(shí)候，會(huì)拿到 ksm 頁(yè)面對(duì)應(yīng)的節(jié)點(diǎn)，然后遍歷節(jié)點(diǎn)的 hlist 鏈表，拿到每一個(gè) anon_vma，然后就和上面介紹的匿名頁(yè)的反向映射一樣了，從 anon_vma 的紅黑樹(shù)中找到所有的 vma，最后 try_to_unmap_one 來(lái)找到 pte 并解除映射關(guān)系。

?

6. 總結(jié)

前面我們介紹了反向映射的三種類(lèi)型，匿名頁(yè)，文件頁(yè)和 ksm 頁(yè)的反向映射,分別通過(guò) page 所對(duì)應(yīng)的的 vma, address_space, stable_node 結(jié)構(gòu)來(lái)查找 vma。當(dāng)然我們只是介紹了 Linux 內(nèi)核中的反向映射的冰山一角，主要是 try_to_unmap 函數(shù)，其實(shí)每種反向映射各個(gè)數(shù)據(jù)結(jié)構(gòu)建立的過(guò)程錯(cuò)綜復(fù)雜，一篇文章三言兩語(yǔ)也說(shuō)不清楚，他們散落在 Linux 內(nèi)核源代碼的進(jìn)程創(chuàng)建 fork，內(nèi)存映射 mmap,缺頁(yè)異常處理，文件系統(tǒng)等各個(gè)角落。

誠(chéng)然，如果我們搞不清楚各種反正映射所對(duì)應(yīng)的各種數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系，或者只是有一些概念上的了解，并沒(méi)有真正掌握這種機(jī)制的實(shí)現(xiàn)原理，對(duì)于我們來(lái)理解 Linux 內(nèi)核虛擬內(nèi)存管理來(lái)說(shuō)是一種障礙，不懂得反向映射，內(nèi)存管理中的很多問(wèn)題是搞不明白的！