1、為什么要使用反向映射

物理內(nèi)存的分頁機(jī)制，一個PTE（Page Table Entry）對應(yīng)一個物理頁，但一個物理頁可以由多個PTE與之相對應(yīng)，當(dāng)該頁要被回收時，Linux2.4的做法是遍歷每個進(jìn)程的所有PTE判斷該P(yáng)TE是否與該頁建立了映射，如果建立則取消該映射，最后無PTE與該相關(guān)聯(lián)后才回收該頁。該方法顯而易見效率極低，因?yàn)槠錇榱瞬檎夷硞€頁的關(guān)聯(lián)PTE遍歷了所有的PTE，我們不禁想：如果把每個頁關(guān)聯(lián)的PTE保存在頁結(jié)構(gòu)里面，每次只需要訪問那些與之相關(guān)聯(lián)的PTE不很方便嗎？確實(shí)，2.4之后確實(shí)采用過此方法，為每個頁結(jié)構(gòu)（Page）維護(hù)一個鏈表，這樣確實(shí)節(jié)省了時間，但此鏈表所占用的空間及維護(hù)此鏈表的代價很大，在2.6中棄之不用，但反向映射機(jī)制的思想不過如此，所以還是有參考價值的，

2.6內(nèi)核新引入的反向映射

• 反向映射是2.6內(nèi)核中新引入的一個機(jī)制，主要是為了加速頁面置換的時候的效率，由于內(nèi)核中的頁面是不區(qū)分進(jìn)程的，多個進(jìn)程很有可能會共享一個頁面，內(nèi)核只管每個頁面必須和一個或者多個pte對應(yīng)，反過來，每一個present位為1的pte必須和一個頁面相對應(yīng)，這個反過來的對應(yīng)是個一一映射關(guān)系，但是前面的卻不然，也就是說頁面到pte的映射卻不是一一映射的關(guān)系，而在一個頁面將要被換出物理內(nèi)存的時候必須實(shí)時更新與之相關(guān)的各個pte，由此得出的問題就是必須掃描所有的進(jìn)程的所有的pte，只要找到pte所對應(yīng)的頁面是將要被換出的頁面就更新之，這樣效率未免太低下，為什么呢？因?yàn)轫撁姹粨Q出本應(yīng)該只涉及頁面和與該頁面相關(guān)的實(shí)體，如果為了找到這些所謂的相關(guān)實(shí)體而消耗大量的時間和空間資源，那么這必然是一個瓶頸，并且這個缺陷是一定可以彌補(bǔ)的，為什么可以彌補(bǔ)呢？因?yàn)槲覀冃枰龅膬H僅是記錄下和此頁面相關(guān)的實(shí)體就可以了，而不是通過遍歷尋找的方式，這樣可以濾去很多無關(guān)的查找，必然的一種可能是浪費(fèi)了空間來存儲額外的信息，帶來的優(yōu)惠就是節(jié)省了大量的時間，這就是反向映射的設(shè)計初衷，那么反向映射是怎么實(shí)現(xiàn)的呢？最簡單的實(shí)現(xiàn)就是在page數(shù)據(jù)結(jié)構(gòu)中擴(kuò)展一個字段，實(shí)際上是一個鏈表，里面鏈接所有指向這個page的pte，換出該頁面的時候遍歷這個鏈表就會得到所有的需要更新的pte，這也是2.6的早期版本中使用的方式：

如果linux和微軟一樣，那么代碼就到此為止了，事實(shí)證明這樣已經(jīng)很不錯了，是的，代碼優(yōu)美，效率又高，一切都不錯，但是linux開發(fā)中沒有最好只有更好，所有的物理內(nèi)存都有page結(jié)構(gòu)與之對應(yīng)，每個page結(jié)構(gòu)中保存一個pte聯(lián)合實(shí)在不是什么明智之舉，畢竟很多page根本就不需要pte反向映射，比如內(nèi)核使用的page以及很多只有一個進(jìn)程使用的匿名頁面，那么就必須想一個辦法，一個懶惰的辦法將這個反向映射的相關(guān)信息保存到一個用戶空間使用的結(jié)構(gòu)體之內(nèi)，就是說只有在使用反向映射的實(shí)體中才保存反向映射信息，否則不保存，這樣算法的時間復(fù)雜度不變，同時可以節(jié)省更多的空間，這樣一來2.6后來的內(nèi)核中就廢棄了以上的優(yōu)雅方式，使用了一種更加高效的方法，將反向映射信息保存到vm_area_struct結(jié)構(gòu)中，因?yàn)橹挥杏脩艨臻g的頁面才會有反向映射，而vm_area_struct是只有用戶空間進(jìn)程才有的數(shù)據(jù)結(jié)構(gòu)

2.6后期的方案利用了mapping的低位沒有用的特征從而使用了這些位，利用了一切可以利用的空間，并且這個方案將匿名反向映射和文件緩存反向映射分離，在文件反向映射中使用優(yōu)先級樹高效處理，相比前一個早期的版本性能提高了不少。2.6的后期版本中的反向映射解決方案的資料是比較多的，我就不多說了，但是早期的反向映射的資料比較少，因此本文就分析了代碼。本文主要想表達(dá)的意思就是linux的后期版本的性能基本都比以前的高，不管它的代碼的可讀性有多糟糕，其實(shí)閱讀linux代碼和理解代碼的關(guān)鍵就是理解作者的設(shè)計思想，最好的辦法就是看changelog，只要理解了changelog就可以理解作者的意圖，讀懂了代碼才可以修改代碼，才可以添加自己的邏輯，開發(fā)自己的內(nèi)核。

2、Linux2.6中是如何實(shí)現(xiàn)反向映射

（以下代碼均來自內(nèi)核版本2.6.11.）

2.1 與RM（Reverse Mapping）相關(guān)的結(jié)構(gòu)

page, address_space, vm_area_struct, mm_struct, anon_vma.

以下均顯示部分成員：

2.2 進(jìn)程地址空間

1. 每個進(jìn)程有個進(jìn)程描述符task_struct，其中有mm域指向該進(jìn)程的內(nèi)存描述符mm_struct。

2. 每個進(jìn)程都擁有一個內(nèi)存描述符，其中有PGD域，指向該進(jìn)程地址空間的全局頁目錄；mmap域指向第一個內(nèi)存區(qū)域描述符vm_area_strut1。

3. 進(jìn)程通過內(nèi)存區(qū)域描述符vm_area_struct管理內(nèi)存區(qū)域，每個內(nèi)存區(qū)域描述符都有vm_start和vm_end域指向該內(nèi)存區(qū)域的在虛擬內(nèi)存中的起始位置；vm_mm域指向該進(jìn)程的內(nèi)存描述符；每個vm_area_struct都有一個anon_vma域指向該進(jìn)程的anon_vma；

4. 每個進(jìn)程都有一個anon_vma，是用于鏈接所有vm_area_struct的頭結(jié)點(diǎn)，通過vm_area_struct的anon_vma_node構(gòu)成雙循環(huán)鏈表。

• 　最終形成了上圖。

• 現(xiàn)在假設(shè)我們要回收一個頁，我們要做的是訪問所有與該頁相關(guān)聯(lián)的PTE并修改之取消二者之間的關(guān)聯(lián)。與之相關(guān)聯(lián)的函數(shù)為：try_to_unmap。

2.3 try_to_unmap

2.3.1 try_to_unmap函數(shù)及PageOn宏 分析

2.3.2 try_to_unmap_anon函數(shù)及page_lock_anon_vma函數(shù)及l(fā)ist_for_each_entry宏 分析

• 還沒開始看文件系統(tǒng)一節(jié)，所以try_to_unmap_file沒看懂，所以此處只分析 try_to_unmap_anon函數(shù)，等看完vfs后再來補(bǔ)充吧。

2.3.3 try_to_unmap_one函數(shù)及vma_address函數(shù)及pdg_offset宏 分析

Linux采用三級頁表：

1. PGD：頂級頁表，由pgd_t項(xiàng)組成的數(shù)組，其中第一項(xiàng)指向一個二級頁表。

2. PMD：二級頁表，由pmd_t項(xiàng)組成的數(shù)組，其中第一項(xiàng)指向一個三級頁表（兩級處理器沒有物理的PMD）。

3. PTE：是一個頁對齊的數(shù)組，第一項(xiàng)稱為一個頁表項(xiàng)，由pte_t類型表示。一個pte_t包含了數(shù)據(jù)頁的物理地址。