反向映射

反向映射機制是為了更新進程頁表項，使得更加有效地回收1個共享頁面，反向映射技術的實現主要是基於頁表項鍊表。

基本介紹

• 中文名：反向映射
• 外文名：reverse mapping

反向映射機制

在Linux記憶體管理器中，頁表保持對進程使用的記憶體物理頁的追蹤，它們將虛擬頁映射到物理頁。有些頁可能不是長時間使用，它們應該被交換出去。但是在交換出去之前，我們首先要做的就是要更新使用該交換頁的每1個進程的頁表項。為了更新進程頁表項，以往為了確定某個要回收的物理頁面都被哪些頁表項引用，必須要遍歷所有進程，這是1項非常耗資源和時間的工程。所以引入反向映射(RMAP)機制，使得更加有效地回收1個共享頁面，反向映射技術的實現主要是基於頁表項鍊表。

作業系統為每1個物理頁面都維護了1個鍊表，所有與該物理頁面關聯的頁表項都會被放到這個鍊表上，建立了物理頁面和所有映射了該物理頁面的頁表項之間的1種關聯，從而讓作業系統可以快速定位引用了該物理頁面的所有頁表項，不再是遍歷每個進程的頁表。該機制中記憶體管理器為每1個物理頁建立了1個鍊表，包含了指向當前映射那個頁的每1個進程的頁表條目(Page-TableEntries，PTE)的指針。然而基於頁表項鍊表存在為每個物理頁面維護這樣1個鍊表，同樣需要占用大量的記憶體空間造成空間資源的消耗。回收1個物理頁面的時候，需要先獲取該鍊表上的鎖，然後遍歷相應的反向映射鍊表，鍊表上的項越多，需要的時間越多，造成時間資源消耗越大。為了解決這一弊端引入基於對象的反向映射機制。

基於對象的反向映射機制

基於對象的反向映射機制也是為物理頁面設定1個用於反向映射的鍊表，但是鍊表上的節點不再是引用該物理頁面的所有頁表項，而是相應的虛擬記憶體區域(vm_area_struct結構)，虛擬記憶體區域通過記憶體描述符(mm_struct結構)找到頁全局目錄，從而找到相應的頁表項，在一定程度上也節約了記憶體空間。用於表示虛擬記憶體區域的描述符比用於表示頁面的描述符要少得多，所以遍歷基於對象的反向映射鍊表所消耗的時間也會少很多。所以在一定程度上減少了空間資源和時間資源的消耗。

基於對象的反向映射的實現，數據結構page結構中與基於對象的反向映射相關的關鍵欄位:_mapcount和mapping。

struct page{

atomic_t _mapcount;

union{

……

struct {

……

struct

address _space* mapping;

};

……

};

欄位_mapcount表明共享該物理頁面的頁表項的數目。該計數器可用於快速檢查該頁面除所有者之外有多少個使用者在使用，初始值是－1，每增加一個使用者，該計數器加1。欄位mapping用於區分匿名頁面和基於檔案映射的頁面，如果該欄位的最低位被置位了，那么該欄位包含的是指向anon_vma用於匿名頁面結構的指針;否則，該欄位包含指向address_space結構的用於基於檔案映射頁面指針。

反向映射機制的優勢

使用基於對象的反向映射機制改善了查找映射到指定物理頁對應的虛擬頁的記憶體管理的瓶頸，並且可以快速定位引用了某個物理頁面的所有頁表項，這極大地方便了作業系統進行頁面回收。相對於之前的遍歷方法來說，基於對象的反向映射機制在很大程度上減少了作業系統在頁面回收上所占用的CPU時間。相對於之前的單純的反向映射機制來說，在一定程度上也解決了要消耗掉一定的記憶體空間的問題。

Linux 2.6中反向映射方法

Object-page Rmap技術

Linux2.6版核心融合的反向映射技術是基於頁的反向映射，它提供了一個發現哪些進程正在使用給定的記憶體物理頁的機制。不再是遍歷每個進程的頁表，記憶體管理器為每一個物理頁建立了一個鍊表，包含了指向當前映射這個頁的每一個進程的頁表條目（page-tableentries,PTE）的指針。這個鍊表叫做PTE鏈。PTE鏈極大地提高了找到那些映射到指定頁的進程的速度，如圖所示。

Linux2.6版核心中用structpte_chain*chain結構來描述反向映射指針結構，並將此結構加入page數據結構中：

typedef struct page{

……

struct pte_chain* chain;

……}

前面已經講過分頁單元把所有的RAM分為固定長度的頁框，也叫物理頁（page frame）。線性地址也被分成固定長度為單位的組。把線性地址映射到物理地址的數據結構稱為頁表（page table）。當某個進程執行的時候，核心才將該進程的部分虛擬地址映射到物理地址，並且在這個進程的頁表中做相應的修改，跟蹤這種映射關係。現在加入structpte_chain*chain結構以後，利用這個結構，當虛擬地址映射到物理地址時，structpte_chain *chain同時也記錄著映射到該物理地址的進程的頁表條目，進程頁表中記錄的是進程虛擬地址映射到物理地址的關係，這樣就行成了雙向映射。即可以通過頁表，查找到指定虛擬地址所映射的物理地址的位置，也可以根據page結構查找到映射到指定物理地址的進程的頁表條目的位置。此外，structpte_chain*chain還可組成的指針結構，因為在linux系統中存在多個虛擬地址指向通一個物理地址，也就是多個進程共享同一個物理頁，此時，每個structpte_chain*chain指針分別指向映射到該物理地址的進程的頁表條目。

反向頁表技術的主要設計思想是在傳統頁表基礎上，為每個物理頁增加一個反向指針集合，指向使用該物理頁的各個頁表項，形成物理地址到虛地址的反向映射。如圖所示，其中虛線部分表示反向頁表結構。使用反向映射技術帶來性能的提高是非常明顯的，但是同時也增加了系統的開銷。首先是記憶體開銷，PTE鏈的每一個條目使用4個位元組來存儲指向頁表條目的指針，用另外4個位元組來存儲指向鏈的下一個條目的指針。節點的Next指針採用32位，所以在32位硬體上不能使用高端記憶體，低端記憶體的使用對運行很多進程大量數據的伺服器來說競爭非常激烈，例如在一個512M記憶體的系統中，有128K個物理頁，這樣就需要有128KB*(sizeof(structpte_chain))的記憶體被分配用於pte_chain的結構。對於這種對低端記憶體的占用過多對於伺服器的套用不利。此外，基於頁面的反向映射在還帶來了一些其他的複雜性。當頁與一個進程產生映射時，必須為這個頁建立反向映射。

同樣，當一個進程釋放對頁的映射時，相應的反向映射也必須都刪除掉。這情況在進程生成和退出時會進行大量的操作。而且所有這些操作都必須在鎖定情況下進行，鎖定情況的增加也不易於並行多進程的套用。對那些執行很多派生和退出的應用程式來說，這可能會非常浪費並且增加很多開銷。下面主要看下加入反向映射技術以後為了與系統正向頁表保持一致性而對反向頁表進行建立和動態增刪的維護過程。

反向頁表的維護

在系統運行過程中，正向頁表將不斷改變虛實地址的映射關係，反向頁表是維護實虛地址映射關係的頁表，故反向頁表將隨正向頁表的變化而動態改變.反向頁表的維護是在任何一個PTE中的物理地址發生改變時，此時反向頁表都需要進行修改，以正確反映當前的實虛映射關係。反向頁表的維護主要發生在頁失效中斷、頁遷移中斷和換頁和交換過程中。

頁失效中斷

當邏輯頁面沒有對應的物理頁面時,系統會進入頁失效中斷處理。頁失效中斷處理例程將為該邏輯頁面準備合適的物理頁面，並將該物理頁面的地址填寫到PTE中.頁失效發生的情況主要有寫時拷貝、檔案頁失效、匿名頁失效、交換頁失效。寫時拷貝的基本思想是將一個物理頁面(舊頁)標記為唯讀，而將其所包含的虛地址訪問位(VMA)標識為可寫.任何對頁面的寫操作都會與頁級保護相衝突，然後觸發一個頁失效.當頁失效處理程式注意到頁級保護和虛地址訪問位(VMA)的保護不一致時，它將創建該頁的一個可寫拷貝(新頁)作為替代頁.此時需要修改寫進程的頁表和新舊物理頁的反向頁表，刪除舊頁反向頁表中有關寫進程的項，並為新頁分配反向頁表，在該表中填加寫進程中指向它的頁表項地址。此時，我們使用反向頁表建立例程為物理頁建立反向頁表數據結構。檔案頁是指映射到磁碟檔案的虛擬頁，當對該類虛擬頁進行訪問發生失效時，頁失效處理例程負資分配一個新物理頁，將所缺頁內容從磁碟載入記憶體物理頁中，而後將物理頁地址添寫到虛擬頁的PTE表項中。此時，我們使用反向頁表建立例程為物理頁建立反向頁表數據結構。匿名頁是指供進程堆疊使用的頁，當對該類虛擬頁進行首次訪問時，會發生頁失效。頁失效處理例程負責為其分配新頁，並初始化為全零，而後將物理頁地址添寫到虛擬頁的PTE表項中。此時，我們使用反向頁表建立例程為物理頁建立反向頁表數據結構。交換頁是指被暫時交換到交換設備上，不在記憶體物理頁中的虛擬頁.頁失效處理例程分配新的物理頁，並將缺頁的內容從交換設備上換入到新分配的物理頁中，而後將物理頁地址添寫到虛擬頁的PTE表項中。此時，我們使用反向頁表建立例程為物理頁建立反向頁表數據結構。以上四種情況中都存在分配新物理頁的情況，這些物理頁創建反向頁表結構，並填寫正確的PTE。

頁遷移和複製

頁遷移和頁複製過程中，根據中斷給出的需要遷移的物理頁地址，通過查閱反向頁表，可以快速、準確地定位所有的PTE。頁遷移過程中，需要釋放舊頁，刪除其反向頁表，並為遷移後的新頁重新分配反向頁表，且把所有映射到該物理頁的頁表項虛地址寫入反向頁表中。我們將舊物理頁中的反向頁表結構賦予給新物理頁，舊物理頁指向該反向頁表結構的指針隨物理頁的釋放而刪除。頁複製過程中，需要產生原物理頁的拷貝頁，此時一個多對一映射分裂為兩個多對一映射，每個物理頁的反向頁表，都應僅包含實際訪問它的PTE。此時根據新生成的PTE調用反向頁表建立例程為新物理頁建立反向頁表結構，調用反向頁表刪除例程刪除舊物理頁中對應的PTE。

交換和換頁

為了提高記憶體的有效利用率，作業系統通過換頁和交換機制將暫時不用的進程頁寫到交換設備，釋放占用的物理頁。換頁和交換機制通過系統中運行的守護進程swapper實現。在守護進程將暫時不用的進程頁寫到交換設備，釋放占用的物理頁時，反向頁表隨物理頁的釋放而進行刪除操作。根據當時情況調用反向頁表的建立和刪除例程，完成維護工作。Linux2.6採用的基於頁反向映射方法儘管有一些折衷，但可以證明反向映射是對Linux記憶體管理器的一個頗有價值的修改。通過這一途徑，查找定位映射某個頁的進程這一嚴重瓶頸被最小化為只需要一個簡單的操作。當大型應用程式向核心請求大量記憶體和多個進程共享記憶體時，反向映射幫助系統繼續有效地運行和擴展，對Linux作為大型伺服器的性能和穩定性方面都有很大的提高。所以接著要做的就是在反向映射的基礎上，進行技術改進來減少反向映射帶來的記憶體占用和系統時間花費上所帶來的問題。

p頁直接方法

P頁直接方法就是加入到Linux2.6核心中減少反向映射帶來的記憶體開銷的一種方法。雖然進程共享同一個物理頁在Linux進程操作中是常見現象，但這種兩個或者更多個進程共享同一個物理頁的情況並不是Linux虛擬映射機制的普遍情況。基於這種情況的分析，為了減少反向映射指針對記憶體尤其是低端記憶體的消耗，在Linux2.6核心中可以將反向映射指針structpte_chain*chain用結構體union代替加入page數據結構中：typedefstructpage{……union{structpte_chain*chain;pte_addr_tdirect;}Pte;……}用這種方法就叫做P頁直接方法（page-directapproach）。如果只有一個進程映射到這個物理頁，那么在建立影射關心的時候，就可以用一個叫做“direct”的指針來代替鍊表，直接指向映射到這個物理頁的進程的頁表條目。當然，只有在這個個頁只是由一個惟一的進程映射時就可以進行這種最佳化，這種映射關係在Linux虛擬地址到物理地址記憶體映射當中還是占絕大部分。採用這種最佳化以後，單獨的“direct”指針雖然也是占用低端記憶體，但所占大小比用structpte_chain結構小很多。不過如果稍後這個頁被另一個進程所映射，它必須刪除“direct”指針，然後重新去建立PTE鏈。同樣，當structpte_chain*chain指針鍊表只剩一個指針的時候，還需要考慮是否轉化成“direct”指針。而且這種在“direct”指針和structpte_chain*chain指針鍊表之間進行轉換也會浪費很多系統時間。此外，還需要設定一個標記用來告訴記憶體管理器什麼時候這種最佳化對一個給定的頁有效，即標記是使用“direct”指針還是使用structpte_chain*chain指針鍊表。所以，綜合來看，採用P頁直接方法只是減少了一部分對低端記憶體的占用，對提高反向映射指針的效率並沒有帶來太大的改變。要想降低反向映射帶來的時間記憶體開銷還必須仔細分析系統核心，提出更行之有效的方法。