虛擬地址、物理地址、邏輯地址、線性地址

虛擬地址又叫線性地址。linux沒有采用分段機制，所以邏輯地址和虛擬地址（線性地址）（在用戶態(tài)，內(nèi)核態(tài)邏輯地址專指下文說的線性偏移前的地址）是一個概念。物理地址自不必提。內(nèi)核的虛擬地址和物理地址，大部分只差一個線性偏移量。用戶空間的虛擬地址和物理地址則采用了多級頁表進行映射，但仍稱之為線性地址。

DMA/HIGH_MEM/NROMAL 分區(qū)

在x86結構中，Linux內(nèi)核虛擬地址空間劃分0~3G為用戶空間，3~4G為內(nèi)核空間(注意，內(nèi)核可以使用的線性地址只有1G)。內(nèi)核虛擬空間（3G~4G）又劃分為三種類型的區(qū)：

ZONE_DMA 3G之后起始的16MB

ZONE_NORMAL 16MB~896MB

ZONE_HIGHMEM 896MB ~1G

由于內(nèi)核的虛擬和物理地址只差一個偏移量：物理地址 = 邏輯地址 – 0xC0000000。所以如果1G內(nèi)核空間完全用來線性映射，顯然物理內(nèi)存也只能訪問到1G區(qū)間，這顯然是不合理的。HIGHMEM就是為了解決這個問題，專門開辟的一塊不必線性映射，可以靈活定制映射，以便訪問1G以上物理內(nèi)存的區(qū)域。從網(wǎng)上扣來一圖，

?

高端內(nèi)存的劃分，又如下圖，

?

?
?

內(nèi)核直接映射空間 PAGE_OFFSET~VMALLOC_START，kmalloc和__get_free_page()分配的是這里的頁面。二者是借助slab分配器，直接分配物理頁再轉(zhuǎn)換為邏輯地址（物理地址連續(xù)）。適合分配小段內(nèi)存。此區(qū)域 包含了內(nèi)核鏡像、物理頁框表mem_map等資源。

內(nèi)核動態(tài)映射空間 VMALLOC_START~VMALLOC_END，被vmalloc用到，可表示的空間大。

內(nèi)核永久映射空間 PKMAP_BASE ~ FIXADDR_START，kmap

內(nèi)核臨時映射空間 FIXADDR_START~FIXADDR_TOP，kmap_atomic

伙伴算法和slab分配器

伙伴Buddy算法解決了外部碎片問題.內(nèi)核在每個zone區(qū)管理著可用的頁面，按2的冪級（order）大小排成鏈表隊列，存放在free_area數(shù)組。

?

?

具體buddy管理基于位圖，其分配回收頁面的算法描述如下，

buddy算法舉例描述:

假設我們的系統(tǒng)內(nèi)存只有16個頁面RAM。因為RAM只有16個頁面，我們只需用四個級別（orders）的伙伴位圖（因為最大連續(xù)內(nèi)存大小為16個頁面），如下圖所示。

?

?

?

order（0）bimap有8個bit位（頁面最多16個頁面，所以16/2） order（1）bimap有4個bit位（order（0）bimap有8個bit位，所以8/2）； 也就是order（1）第一塊由兩個頁框page1 與page2組成與order（1）第2塊由兩個頁框page3 與page4組成，這兩個塊之間有一個bit位 order（2）bimap有2個bit位（order（1）bimap有4個bit位，所以4/2） order（3）bimap有1個bit位（order（2）bimap有4個bit位，所以2/2） 在order（0），第一個bit表示開始的2個頁面，第二個bit表示接下來的2個頁面，以此類推。因為頁面4已分配，而頁面5空閑，故第三個bit為1。 同樣在order（1）中，bit3是1的原因是一個伙伴完全空閑（頁面8和9），和它對應的伙伴（頁面10和11）卻并非如此，故以后回收頁面時，可以合并。

分配過程

當我們需要order（1）的空閑頁面塊時，則執(zhí)行以下步驟：

1、初始空閑鏈表為： order(0): 5, 10 order(1): 8 [8,9] order(2): 12 [12,13,14,15] order(3): 2、從上面空閑鏈表中，我們可以看出，order（1）鏈表上，有一個空閑的頁面塊，把它分配給用戶，并從該鏈表中刪除。 3、當我們再需要一個order（1）的塊時，同樣我們從order（1）空閑鏈表上開始掃描。 4、若在order（1）上沒有空閑頁面塊，那么我們就到更高的級別（order）上找，order（2）。 5、此時（order（1）上沒有空閑頁面塊）有一個空閑頁面塊，該塊是從頁面12開始。該頁面塊被分割成兩個稍微小一些order（1）的頁面塊，[12，13]和[14，15]。[14，15]頁面塊加到order（1）空閑鏈表中，同時[12，13]頁面塊返回給用戶。 6、最終空閑鏈表為： order(0): 5, 10 order(1): 14 [14,15] order(2): order(3):

回收過程

當我們回收頁面11（order 0）時，則執(zhí)行以下步驟：

1、找到在order（0）伙伴位圖中代表頁面11的位，計算使用下面公示： index = page_idx >> (order + 1) = 11 >> (0 + 1) = 5 2、檢查上面一步計算位圖中相應bit的值。若該bit值為1，則和我們臨近的，有一個空閑伙伴。Bit5的值為1（注意是從bit0開始的，Bit5即為第6bit），因為它的伙伴頁面10是空閑的。 3、現(xiàn)在我們重新設置該bit的值為0，因為此時兩個伙伴（頁面10和頁面11）完全空閑。 4、我們將頁面10，從order（0）空閑鏈表中摘除。 5、此時，我們對2個空閑頁面（頁面10和11，order（1））進行進一步操作。 6、新的空閑頁面是從頁面10開始的，于是我們在order（1）的伙伴位圖中找到它的索引，看是否有空閑的伙伴，以進一步進行合并操作。使用第一步中的計算公司，我們得到bit 2（第3位）。 7、Bit 2（order（1）位圖）同樣也是1，因為它的伙伴頁面塊（頁面8和9）是空閑的。 8、重新設置bit2（order（1）位圖）的值，然后在order（1）鏈表中刪除該空閑頁面塊。 9、現(xiàn)在我們合并成了4頁面大小（從頁面8開始）的空閑塊，從而進入另外的級別。在order（2）中找到伙伴位圖對應的bit值，是bit1，且值為1，需進一步合并（原因同上）。 10、從oder（2）鏈表中摘除空閑頁面塊（從頁面12開始），進而將該頁面塊和前面合并得到的頁面塊進一步合并?，F(xiàn)在我們得到從頁面8開始，大小為8個頁面的空閑頁面塊。 11、我們進入另外一個級別，order（3）。它的位索引為0，它的值同樣為0。這意味著對應的伙伴不是全部空閑的，所以沒有再進一步合并的可能。我們僅設置該bit為1，然后將合并得到的空閑頁面塊放入order（3）空閑鏈表中。 12、最終我們得到大小為8個頁面的空閑塊，

?

?

buddy避免內(nèi)部碎片的努力

物理內(nèi)存的碎片化一直是Linux操作系統(tǒng)的弱點之一，盡管已經(jīng)有人提出了很多解決方法，但是沒有哪個方法能夠徹底的解決，memory buddy分配就是解決方法之一。 我們知道磁盤文件也有碎片化問題，但是磁盤文件的碎片化只會減慢系統(tǒng)的讀寫速度，并不會導致功能性錯誤，而且我們還可以在不影響磁盤功能的前提的下，進行磁盤碎片整理。而物理內(nèi)存碎片則截然不同，物理內(nèi)存和操作系統(tǒng)結合的太過于緊密，以至于我們很難在運行時，進行物理內(nèi)存的搬移（這一點上，磁盤碎片要容易的多；實際上mel gorman已經(jīng)提交了內(nèi)存緊縮的patch，只是還沒有被主線內(nèi)核接收）。 因此解決的方向主要放在預防碎片上。在2.6.24內(nèi)核開發(fā)期間，防止碎片的內(nèi)核功能加入了主線內(nèi)核。在了解反碎片的基本原理前，先對內(nèi)存頁面做個歸類：

不可移動頁面 unmoveable：在內(nèi)存中位置必須固定，無法移動到其他地方，核心內(nèi)核分配的大部分頁面都屬于這一類。

可回收頁面 reclaimable：不能直接移動，但是可以回收，因為還可以從某些源重建頁面，比如映射文件的數(shù)據(jù)屬于這種類別，kswapd會按照一定的規(guī)則，周期性的回收這類頁面。

可移動頁面 movable：可以隨意的移動。屬于用戶空間應用程序的頁屬于此類頁面，它們是通過頁表映射的，因此我們只需要更新頁表項，并把數(shù)據(jù)復制到新位置就可以了，當然要注意，一個頁面可能被多個進程共享，對應著多個頁表項。

防止碎片的方法就是把這三類page放在不同的鏈表上，避免不同類型頁面相互干擾?？紤]這樣的情形，一個不可移動的頁面位于可移動頁面中間，那么我們移動或者回收這些頁面后，這個不可移動的頁面阻礙著我們獲得更大的連續(xù)物理空閑空間。

?

每個zone區(qū)都有一個自己的失活凈頁面隊列，與此對應的是兩個跨zone的全局隊列，失活臟頁隊列 和 活躍隊列。這些隊列都是通過page結構的lru指針鏈入的。

思考：失活隊列的意義是什么(見)?內(nèi)核源代碼情景分析>

slab分配器：解決內(nèi)部碎片問題

內(nèi)核通常依賴于對小對象的分配，它們會在系統(tǒng)生命周期內(nèi)進行無數(shù)次分配。slab 緩存分配器通過對類似大小（遠小于1page）的對象進行緩存而提供這種功能，從而避免了常見的內(nèi)部碎片問題。此處暫貼一圖，關于其原理，常見參考文獻3。很顯然，slab機制是基于buddy算法的，前者是對后者的細化。

?

?

頁面回收/側重機制

頁面回收簡述

有頁面分配，就會有頁面回收。頁面回收的方法大體上可分為兩種：

一是主動釋放。就像用戶程序通過free函數(shù)釋放曾經(jīng)通過malloc函數(shù)分配的內(nèi)存一樣，頁面的使用者明確知道頁面什么時候要被使用，什么時候又不再需要了。 上面提到的前兩種分配方式，一般都是由內(nèi)核程序主動釋放的。對于直接從伙伴系統(tǒng)分配的頁面，這是由使用者使用free_pages之類的函數(shù)主動釋放的，頁面釋放后被直接放歸伙伴系統(tǒng)；從slab中分配的對象（使用kmem_cache_alloc函數(shù)），也是由使用者主動釋放的（使用kmem_cache_free函數(shù)）。

另一種頁面回收方式是通過linux內(nèi)核提供的頁框回收算法（PFRA）進行回收。頁面的使用者一般將頁面當作某種緩存，以提高系統(tǒng)的運行效率。緩存一直存在固然好，但是如果緩存沒有了也不會造成什么錯誤，僅僅是效率受影響而已。頁面的使用者不明確知道這些緩存頁面什么時候最好被保留，什么時候最好被回收，這些都交由PFRA來關心。

簡單來說，PFRA要做的事就是回收這些可以被回收的頁面。為了避免系統(tǒng)陷入頁面緊缺的困境，PFRA會在內(nèi)核線程中周期性地被調(diào)用運行?；蛘哂捎谙到y(tǒng)已經(jīng)頁面緊缺，試圖分配頁面的內(nèi)核執(zhí)行流程因為得不到需要的頁面，而同步地調(diào)用PFRA。

上面提到的后兩種分配方式，一般是由PFRA來進行回收的（或者由類似刪除文件、進程退出、這樣的過程來同步回收）。

?

PFRA回收一般頁面

而對于上面提到的前兩種頁面分配方式（直接分配頁面和通過slab分配對象），也有可能需要通過PFRA來回收。

頁面的使用者可以向PFRA注冊回調(diào)函數(shù)（使用register_shrink函數(shù)）。然后由PFRA在適當?shù)臅r機來調(diào)用這些回調(diào)函數(shù)，以觸發(fā)對相應頁面或?qū)ο蟮幕厥铡?/p>

其中較為典型的是對dentry的回收。dentry是由slab分配的，用于表示虛擬文件系統(tǒng)目錄結構的對象。在dentry的引用記數(shù)被減為0的時候，dentry并不是直接被釋放，而是被放到一個LRU鏈表中緩存起來，便于后續(xù)的使用。

而這個LRU鏈表中的dentry最終是需要被回收的，于是虛擬文件系統(tǒng)在初始化時，調(diào)用register_shrinker注冊了回收函數(shù)shrink_dcache_memory。

系統(tǒng)中所有文件系統(tǒng)的超級塊對象被存放在一個鏈表中，shrink_dcache_memory函數(shù)掃描這個鏈表，獲取每個超級塊的未被使用dentry的LRU，然后從中回收一些最老的dentry。隨著dentry的釋放，對應的inode將被減引用，也可能引起inode被釋放。

inode被釋放后也是放在一個未使用鏈表中，虛擬文件系統(tǒng)在初始化時還調(diào)用register_shrinker注冊了回調(diào)函數(shù)shrink_icache_memory，用來回收這些未使用的inode，從而inode中關聯(lián)的磁盤高速緩存也將被釋放。

?

另外，隨著系統(tǒng)的運行，slab中可能會存在很多的空閑對象（比如在對某一對象的使用高峰過后）。PFRA中的cache_reap函數(shù)就用于回收這些多余的空閑對象，如果某些空閑的對象正好能夠還原成一個頁面，則這個頁面可以被釋放回伙伴系統(tǒng)；

cache_reap函數(shù)要做的事情說起來很簡單。系統(tǒng)中所有存放對象池的kmem_cache結構連成一個鏈表，cache_reap函數(shù)掃描其中的每一個對象池，然后尋找可以回收的頁面，并將其回收。（當然，實際的過程要更復雜一點。）

關于內(nèi)存映射

前面說到，磁盤高速緩存和內(nèi)存映射一般由PFRA來進行回收。PFRA對這兩者的回收是很類似的，實際上，磁盤高速緩存很可能就被映射到了用戶空間。下面簡單對內(nèi)存映射做一些介紹：

內(nèi)存映射分為文件映射和匿名映射

文件映射是指代表這個映射的vma對應到一個文件中的某個區(qū)域。這種映射方式相對較少被用戶態(tài)程序顯式地使用，用戶態(tài)程序一般習慣于open一個文件、然后read/write去讀寫文件。

而實際上，用戶程序也可以使用mmap系統(tǒng)調(diào)用將一個文件的某個部分映射到內(nèi)存上（對應到一個vma），然后以訪存的方式去讀寫文件。盡管用戶程序較少這樣使用，但是用戶進程中卻充斥著這樣的映射：進程正在執(zhí)行的可執(zhí)行代碼（包括可執(zhí)行文件、lib庫文件）就是以這樣的方式被映射的。

實際上，文件映射是將文件的磁盤高速緩存中的頁面直接映射到了用戶空間（可見，文件映射的頁面是磁盤高速緩存頁面的子集），用戶可以0拷貝地對其進行讀寫。而使用read/write的話，則會在用戶空間的內(nèi)存和磁盤高速緩存間發(fā)生一次拷貝。

匿名映射相對于文件映射，代表這個映射的vma沒有對應到文件。對于用戶空間普通的內(nèi)存分配（堆空間、?？臻g），都屬于匿名映射。 顯然，多個進程可能通過各自的文件映射來映射到同一個文件上（比如大多數(shù)進程都映射了libc庫的so文件）；那匿名映射呢？實際上，多個進程也可能通過各自的匿名映射來映射到同一段物理內(nèi)存上，這種情況是由于fork之后父子進程共享原來的物理內(nèi)存（copy-on-write）而引起的。

文件映射又分為共享映射和私有映射。私有映射時，如果進程對映射的地址空間進行寫操作，則映射對應的磁盤高速緩存并不會直接被寫。而是將原有內(nèi)容復制一份，然后再寫這個復制品，并且當前進程的對應頁面映射將切換到這個復制品上去（寫時復制）。也就是說，寫操作是只有自己可見的。而對于共享映射，寫操作則會影響到磁盤高速緩存，是大家都可見的。

哪些頁面該回收

至于回收，磁盤高速緩存的頁面（包括文件映射的頁面）都是可以被丟棄并回收的。但是如果頁面是臟頁面，則丟棄之前必須將其寫回磁盤。

而匿名映射的頁面則都是不可以丟棄的，因為頁面里面存有用戶程序正在使用的數(shù)據(jù)，丟棄之后數(shù)據(jù)就沒法還原了。相比之下，磁盤高速緩存頁面中的數(shù)據(jù)本身是保存在磁盤上的，可以復現(xiàn)。

于是，要想回收匿名映射的頁面，只好先把頁面上的數(shù)據(jù)轉(zhuǎn)儲到磁盤，這就是頁面交換（swap）。顯然，頁面交換的代價相對更高一些。

匿名映射的頁面可以被交換到磁盤上的交換文件或交換分區(qū)上（分區(qū)即是設備，設備即也是文件。所以下文統(tǒng)稱為交換文件）。

于是，除非頁面被保留或被上鎖（頁面標記PG_reserved/PG_locked被置位。某些情況下，內(nèi)核需要暫時性地將頁面保留，避免被回收），所有的磁盤高速緩存頁面都可回收，所有的匿名映射頁面都可交換。

盡管可以回收的頁面很多，但是顯然PFRA應當盡可能少地去回收/交換（因為這些頁面要從磁盤恢復，需要很大的代價）。所以，PFRA僅當必要時才回收/交換一部分很少被使用的頁面，每次回收的頁面數(shù)是一個經(jīng)驗值：32。

于是，所有這些磁盤高速緩存頁面和匿名映射頁面都被放到了一組LRU里面。（實際上，每個zone就有一組這樣的LRU，頁面都被放到自己對應的zone的LRU中。）

一組LRU由幾對鏈表組成，有磁盤高速緩存頁面（包括文件映射頁面）的鏈表、匿名映射頁面的鏈表、等。一對鏈表實際上是active和inactive兩個鏈表，前者是最近使用過的頁面、后者是最近未使用的頁面。

進行頁面回收的時候，PFRA要做兩件事情，一是將active鏈表中最近最少使用的頁面移動到inactive鏈表、二是嘗試將inactive鏈表中最近最少使用的頁面回收。

確定最近最少使用

現(xiàn)在就有一個問題了，怎么確定active/inactive鏈表中哪些頁面是最近最少使用的呢？

?

一種方法是排序，當頁面被訪問時，將其移動到鏈表的尾部（假設回收從頭部開始）。但是這就意味著頁面在鏈表中的位置可能頻繁移動，并且移動之前還必須先上鎖（可能有多個CPU在同時訪問），這樣做對效率影響很大。

linux內(nèi)核采用的是標記加順序的辦法。當頁面在active和inactive兩個鏈表之間移動時，總是將其放到鏈表的尾部（同上，假設回收從頭部開始）。

頁面沒有在鏈表間移動時，并不會調(diào)整它們的順序。而是通過訪問標記來表示頁面是否剛被訪問過。如果inactive鏈表中已設置訪問標記的頁面再被訪問，則將其移動到active鏈表中，并且清除訪問標記。（實際上，為了避免訪問沖突，頁面并不會直接從inactive鏈表移動到active鏈表，而是有一個pagevec中間結構用作緩沖，以避免鎖鏈表。）

頁面的訪問標記有兩種情況，一是放在page->flags中的PG_referenced標記，在頁面被訪問時該標記置位。對于磁盤高速緩存中（未被映射）的頁面，用戶進程通過read、write之類的系統(tǒng)調(diào)用去訪問它們，系統(tǒng)調(diào)用代碼中會將對應頁面的PG_referenced標記置位。 而對于內(nèi)存映射的頁面，用戶進程可以直接訪問它們（不經(jīng)過內(nèi)核），所以這種情況下的訪問標記不是由內(nèi)核來設置的，而是由mmu。在將虛擬地址映射成物理地址后，mmu會在對應的頁表項上置一個accessed標志位，表示頁面被訪問。（同樣的道理，mmu會在被寫的頁面所對應的頁表項上置一個dirty標志，表示頁面是臟頁面。）

頁面的訪問標記（包括上面兩種標記）將在PFRA處理頁面回收的過程中被清除，因為訪問標記顯然是應該有有效期的，而PFRA的運行周期就代表這個有效期。page->flags中的PG_referenced標記可以直接清除，而頁表項中的accessed位則需要通過頁面找到其對應的頁表項后才能清除（見下文的“反向映射”）。

那么，回收過程又是怎樣掃描LRU鏈表的呢？ 由于存在多組LRU（系統(tǒng)中有多個zone，每個zone又有多組LRU），如果PFRA每次回收都掃描所有的LRU找出其中最值得回收的若干個頁面的話，回收算法的效率顯然不夠理想。

linux內(nèi)核PFRA使用的掃描方法是：定義一個掃描優(yōu)先級，通過這個優(yōu)先級換算出在每個LRU上應該掃描的頁面數(shù)。整個回收算法以最低的優(yōu)先級開始，先掃描每個LRU中最近最少使用的幾個頁面，然后試圖回收它們。如果一遍掃描下來，已經(jīng)回收了足夠數(shù)量的頁面，則本次回收過程結束。否則，增大優(yōu)先級，再重新掃描，直到足夠數(shù)量的頁面被回收。而如果始終不能回收足夠數(shù)量的頁面，則優(yōu)先級將增加到最大，也就是所有頁面將被掃描。這時，就算回收的頁面數(shù)量還是不足，回收過程都會結束。

每次掃描一個LRU時，都從active鏈表和inactive鏈表獲取當前優(yōu)先級對應數(shù)目的頁面，然后再對這些頁面做處理：如果頁面不能被回收（如被保留或被上鎖），則放回對應鏈表頭部（同上，假設回收從頭部開始）；否則如果頁面的訪問標記置位，則清除該標記，并將頁面放回對應鏈表尾部（同上，假設回收從頭部開始）；否則頁面將從active鏈表被移動到inactive鏈表、或從inactive鏈表被回收。

?

被掃描到的頁面根據(jù)訪問標記是否置位來決定其去留。那么這個訪問標記是如何設置的呢？有兩個途徑，一是用戶通過read/write之類的系統(tǒng)調(diào)用訪問文件時，內(nèi)核操作磁盤高速緩存中的頁面，會設置這些頁面的訪問標記（設置在page結構中）；二是進程直接訪問已映射的頁面時，mmu會自動給對應的頁表項加上訪問標記（設置在頁表的pte中）。關于訪問標記的判斷就基于這兩個信息。（給定一個頁面，可能有多個pte引用到它。如何知道這些pte是否被設置了訪問標記呢？那就需要通過反向映射找到這些pte。下面會講到。）

PFRA不傾向于從active鏈表回收匿名映射的頁面，因為用戶進程使用的內(nèi)存一般相對較少，且回收的話需要進行交換，代價較大。所以在內(nèi)存剩余較多、匿名映射所占比例較少的情況下，都不會去回收匿名映射對應的active鏈表中的頁面。（而如果頁面已經(jīng)被放到inactive鏈表中，就不再去管那么多了。）

反向映射

像這樣，在PFRA處理頁面回收的過程中，LRU的inactive鏈表中的某些頁面可能就要被回收了。

如果頁面沒有被映射，直接回收到伙伴系統(tǒng)即可（對于臟頁，先寫回、再回收）。否則，還有一件麻煩的事情要處理。因為用戶進程的某個頁表項正引用著這個頁面呢，在回收頁面之前，還必須給引用它的頁表項一個交待。 于是，問題就來了，內(nèi)核怎么知道這個頁面被哪些頁表項所引用呢？為了做到這一點，內(nèi)核建立了從頁面到頁表項的反向映射。

通過反向映射可以找到一個被映射的頁面對應的vma，通過vma->vm_mm->pgd就能找到對應的頁表。然后通過page->index得到頁面的虛擬地址。再通過虛擬地址從頁表中找到對應的頁表項。（前面說到的獲取頁表項中的accessed標記，就是通過反向映射實現(xiàn)的。）

頁面對應的page結構中，page->mapping如果最低位置位，則這是一個匿名映射頁面，page->mapping指向一個anon_vma結構；否則是文件映射頁面，page->mapping文件對應的address_space結構。（顯然，anon_vma結構和address_space結構在分配時，地址必須要對齊，至少保證最低位為0。）

對于匿名映射的頁面，anon_vma結構作為一個鏈表頭，將映射這個頁面的所有vma通過vma->anon_vma_node鏈表指針連接起來。每當一個頁面被（匿名）映射到一個用戶空間時，對應的vma就被加入這個鏈表。

對于文件映射的頁面，address_space結構除了維護了一棵用于存放磁盤高速緩存頁面的radix樹，還為該文件映射到的所有vma維護了一棵優(yōu)先搜索樹。因為這些被文件映射到的vma并不一定都是映射整個文件，很可能只映射了文件的一部分。所以，這棵優(yōu)先搜索樹除了索引到所有被映射的vma，還要能知道文件的哪些區(qū)域是映射到哪些vma上的。每當一個頁面被（文件）映射到一個用戶空間時，對應的vma就被加入這個優(yōu)先搜索樹。于是，給定磁盤高速緩存上的一個頁面，就能通過page->index得到頁面在文件中的位置，就能通過優(yōu)先搜索樹找出這個頁面映射到的所有vma。

上面兩步中，神奇的page->index做了兩件事，得到頁面的虛擬地址、得到頁面在文件磁盤高速緩存中的位置。

vma->vm_start記錄了vma的首虛擬地址，vma->vm_pgoff記錄了該vma在對應的映射文件（或共享內(nèi)存）中的偏移，而page->index記錄了頁面在文件（或共享內(nèi)存）中的偏移。

通過vma->vm_pgoff和page->index能得到頁面在vma中的偏移，加上vma->vm_start就能得到頁面的虛擬地址；而通過page->index就能得到頁面在文件磁盤高速緩存中的位置。

頁面換入換出

在找到了引用待回收頁面的頁表項后，對于文件映射，可以直接把引用該頁面的頁表項清空。等用戶再訪問這個地址的時候觸發(fā)缺頁異常，異常處理代碼再重新分配一個頁面，并去磁盤里面把對應的數(shù)據(jù)讀出來就行了（說不定，頁面在對應的磁盤高速緩存里面已經(jīng)有了，因為其他進程先訪問過）。這就跟頁面映射以后，第一次被訪問的情形一樣；

對于匿名映射，先將頁面寫回到交換文件，然后還得在頁表項中記錄該頁面在交換文件中的index。

頁表項中有一個present位，如果該位被清除，則mmu認為頁表項無效。在頁表項無效的情況下，其他位不被mmu關心，可以用來存儲其他信息。這里就用它們來存儲頁面在交換文件中的index了（實際上是交換文件號+交換文件內(nèi)的索引號）。

將匿名映射的頁面交換到交換文件的過程（換出過程）與將磁盤高速緩存中的臟頁寫回文件的過程很相似。

交換文件也有其對應的address_space結構，匿名映射的頁面在換出時先被放到這個address_space對應磁盤高速緩存中，然后跟臟頁寫回一樣，被寫回到交換文件中。寫回完成后，這個頁面才被釋放（記住，我們的目的是要釋放這個頁面）。

那么為什么不直接把頁面寫回到交換文件，而要經(jīng)過磁盤高速緩存呢？因為，這個頁面可能被映射了多次，不可能一次性把所有用戶進程的頁表中對應的頁表項都修改好（修改成頁面在交換文件中的索引），所以在頁面被釋放的過程中，頁面被暫時放在磁盤高速緩存上。

而并不是所有頁表項的修改過程都是能成功的（比如在修改之前頁面又被訪問了，于是現(xiàn)在又不需要回收這個頁面了），所以頁面放到磁盤高速緩存的時間也可能會很長。

同樣，將匿名映射的頁面從交換文件讀出的過程（換入過程）也與將文件數(shù)據(jù)讀出的過程很相似。

先去對應的磁盤高速緩存上看看頁面在不在，不在的話再去交換文件里面讀。文件里的數(shù)據(jù)也是被讀到磁盤高速緩存中的，然后用戶進程的頁表中對應的頁表項將被改寫，直接指向這個頁面。

這個頁面可能不會馬上從磁盤高速緩存中拿下來，因為如果還有其他用戶進程也映射到這個頁面（它們的對應頁表項已經(jīng)被修改成了交換文件的索引），他們也可以引用到這里。直到?jīng)]有其他的頁表項再引用這個交換文件索引時，頁面才可以從磁盤高速緩存中被取下來。

最后的必殺

前面說到，PFRA可能掃描了所有的LRU還沒辦法回收需要的頁面。同樣，在slab、dentry cache、inode cache、等地方，可能也無法回收到頁面。

這時，如果某段內(nèi)核代碼一定要獲得頁面呢（沒有頁面，系統(tǒng)可能就要崩潰了）？PFRA只好使出最后的必殺技——OOM（out of memory）。所謂的OOM就是尋找一個最不重要的進程，然后將其殺死。通過釋放這個進程所占有的內(nèi)存頁面，以緩解系統(tǒng)壓力。

5.內(nèi)存管理架構

?

?
?

針對上圖，說幾句，

地址映射(圖：左中)

linux內(nèi)核使用頁式內(nèi)存管理，應用程序給出的內(nèi)存地址是虛擬地址，它需要經(jīng)過若干級頁表一級一級的變換，才變成真正的物理地址。

想一下，地址映射還是一件很恐怖的事情。當訪問一個由虛擬地址表示的內(nèi)存空間時，需要先經(jīng)過若干次的內(nèi)存訪問，得到每一級頁表中用于轉(zhuǎn)換的頁表項（頁表是存放在內(nèi)存里面的），才能完成映射。也就是說，要實現(xiàn)一次內(nèi)存訪問，實際上內(nèi)存被訪問了N+1次（N=頁表級數(shù)），并且還需要做N次加法運算。

所以，地址映射必須要有硬件支持，mmu（內(nèi)存管理單元）就是這個硬件。并且需要有cache來保存頁表，這個cache就是TLB（Translation lookaside buffer）。

盡管如此，地址映射還是有著不小的開銷。假設cache的訪存速度是內(nèi)存的10倍，命中率是40%，頁表有三級，那么平均一次虛擬地址訪問大概就消耗了兩次物理內(nèi)存訪問的時間。

于是，一些嵌入式硬件上可能會放棄使用mmu，這樣的硬件能夠運行VxWorks（一個很高效的嵌入式實時操作系統(tǒng)）、linux（linux也有禁用mmu的編譯選項）、等系統(tǒng)。

但是使用mmu的優(yōu)勢也是很大的，最主要的是出于安全性考慮。各個進程都是相互獨立的虛擬地址空間，互不干擾。而放棄地址映射之后，所有程序?qū)⑦\行在同一個地址空間。于是，在沒有mmu的機器上，一個進程越界訪存，可能引起其他進程莫名其妙的錯誤，甚至導致內(nèi)核崩潰。

在地址映射這個問題上，內(nèi)核只提供頁表，實際的轉(zhuǎn)換是由硬件去完成的。那么內(nèi)核如何生成這些頁表呢？這就有兩方面的內(nèi)容，虛擬地址空間的管理和物理內(nèi)存的管理。（實際上只有用戶態(tài)的地址映射才需要管理，內(nèi)核態(tài)的地址映射是寫死的。）

虛擬地址管理(圖：左下)

每個進程對應一個task結構，它指向一個mm結構，這就是該進程的內(nèi)存管理器。（對于線程來說，每個線程也都有一個task結構，但是它們都指向同一個mm，所以地址空間是共享的。）

mm->pgd指向容納頁表的內(nèi)存，每個進程有自已的mm，每個mm有自己的頁表。于是，進程調(diào)度時，頁表被切換（一般會有一個CPU寄存器來保存頁表的地址，比如X86下的CR3，頁表切換就是改變該寄存器的值）。所以，各個進程的地址空間互不影響（因為頁表都不一樣了，當然無法訪問到別人的地址空間上。但是共享內(nèi)存除外，這是故意讓不同的頁表能夠訪問到相同的物理地址上）。

用戶程序?qū)?nèi)存的操作（分配、回收、映射、等）都是對mm的操作，具體來說是對mm上的vma（虛擬內(nèi)存空間）的操作。這些vma代表著進程空間的各個區(qū)域，比如堆、棧、代碼區(qū)、數(shù)據(jù)區(qū)、各種映射區(qū)、等等。

用戶程序?qū)?nèi)存的操作并不會直接影響到頁表，更不會直接影響到物理內(nèi)存的分配。比如malloc成功，僅僅是改變了某個vma，頁表不會變，物理內(nèi)存的分配也不會變。

假設用戶分配了內(nèi)存，然后訪問這塊內(nèi)存。由于頁表里面并沒有記錄相關的映射，CPU產(chǎn)生一次缺頁異常。內(nèi)核捕捉異常，檢查產(chǎn)生異常的地址是不是存在于一個合法的vma中。如果不是，則給進程一個"段錯誤"，讓其崩潰；如果是，則分配一個物理頁，并為之建立映射。

物理內(nèi)存管理(圖：右上)

那么物理內(nèi)存是如何分配的呢？

首先，linux支持NUMA（非均質(zhì)存儲結構），物理內(nèi)存管理的第一個層次就是介質(zhì)的管理。pg_data_t結構就描述了介質(zhì)。一般而言，我們的內(nèi)存管理介質(zhì)只有內(nèi)存，并且它是均勻的，所以可以簡單地認為系統(tǒng)中只有一個pg_data_t對象。

每一種介質(zhì)下面有若干個zone。一般是三個，DMA、NORMAL和HIGH。

DMA：因為有些硬件系統(tǒng)的DMA總線比系統(tǒng)總線窄，所以只有一部分地址空間能夠用作DMA，這部分地址被管理在DMA區(qū)域（這屬于是高級貨了）；

HIGH：高端內(nèi)存。在32位系統(tǒng)中，地址空間是4G，其中內(nèi)核規(guī)定3~4G的范圍是內(nèi)核空間，0~3G是用戶空間（每個用戶進程都有這么大的虛擬空間）（圖：中下）。前面提到過內(nèi)核的地址映射是寫死的，就是指這3~4G的對應的頁表是寫死的，它映射到了物理地址的0~1G上。（實際上沒有映射1G，只映射了896M。剩下的空間留下來映射大于1G的物理地址，而這一部分顯然不是寫死的）。所以，大于896M的物理地址是沒有寫死的頁表來對應的，內(nèi)核不能直接訪問它們（必須要建立映射），稱它們?yōu)楦叨藘?nèi)存（當然，如果機器內(nèi)存不足896M，就不存在高端內(nèi)存。如果是64位機器，也不存在高端內(nèi)存，因為地址空間很大很大，屬于內(nèi)核的空間也不止1G了）；

NORMAL：不屬于DMA或HIGH的內(nèi)存就叫NORMAL。

在zone之上的zone_list代表了分配策略，即內(nèi)存分配時的zone優(yōu)先級。一種內(nèi)存分配往往不是只能在一個zone里進行分配的，比如分配一個頁給內(nèi)核使用時，最優(yōu)先是從NORMAL里面分配，不行的話就分配DMA里面的好了（HIGH就不行，因為還沒建立映射），這就是一種分配策略。

每個內(nèi)存介質(zhì)維護了一個mem_map，為介質(zhì)中的每一個物理頁面建立了一個page結構與之對應，以便管理物理內(nèi)存。

每個zone記錄著它在mem_map上的起始位置。并且通過free_area串連著這個zone上空閑的page。物理內(nèi)存的分配就是從這里來的，從 free_area上把page摘下，就算是分配了。（內(nèi)核的內(nèi)存分配與用戶進程不同，用戶使用內(nèi)存會被內(nèi)核監(jiān)督，使用不當就"段錯誤"；而內(nèi)核則無人監(jiān)督，只能靠自覺，不是自己從free_area摘下的page就不要亂用。）

建立地址映射

內(nèi)核需要物理內(nèi)存時，很多情況是整頁分配的，這在上面的mem_map中摘一個page下來就好了。比如前面說到的內(nèi)核捕捉缺頁異常，然后需要分配一個page以建立映射。

說到這里，會有一個疑問，內(nèi)核在分配page、建立地址映射的過程中，使用的是虛擬地址還是物理地址呢？首先，內(nèi)核代碼所訪問的地址都是虛擬地址，因為CPU指令接收的就是虛擬地址（地址映射對于CPU指令是透明的）。但是，建立地址映射時，內(nèi)核在頁表里面填寫的內(nèi)容卻是物理地址，因為地址映射的目標就是要得到物理地址。

那么，內(nèi)核怎么得到這個物理地址呢？其實，上面也提到了，mem_map中的page就是根據(jù)物理內(nèi)存來建立的，每一個page就對應了一個物理頁。

于是我們可以說，虛擬地址的映射是靠這里page結構來完成的，是它們給出了最終的物理地址。然而，page結構顯然是通過虛擬地址來管理的（前面已經(jīng)說過，CPU指令接收的就是虛擬地址）。那么，page結構實現(xiàn)了別人的虛擬地址映射，誰又來實現(xiàn)page結構自己的虛擬地址映射呢？沒人能夠?qū)崿F(xiàn)。

這就引出了前面提到的一個問題，內(nèi)核空間的頁表項是寫死的。在內(nèi)核初始化時，內(nèi)核的地址空間就已經(jīng)把地址映射寫死了。page結構顯然存在于內(nèi)核空間，所以它的地址映射問題已經(jīng)通過“寫死”解決了。

由于內(nèi)核空間的頁表項是寫死的，又引出另一個問題，NORMAL（或DMA）區(qū)域的內(nèi)存可能被同時映射到內(nèi)核空間和用戶空間。被映射到內(nèi)核空間是顯然的，因為這個映射已經(jīng)寫死了。而這些頁面也可能被映射到用戶空間的，在前面提到的缺頁異常的場景里面就有這樣的可能。映射到用戶空間的頁面應該優(yōu)先從HIGH區(qū)域獲取，因為這些內(nèi)存被內(nèi)核訪問起來很不方便，拿給用戶空間再合適不過了。但是HIGH區(qū)域可能會耗盡，或者可能因為設備上物理內(nèi)存不足導致系統(tǒng)里面根本就沒有HIGH區(qū)域，所以，將NORMAL區(qū)域映射給用戶空間是必然存在的。

但是NORMAL區(qū)域的內(nèi)存被同時映射到內(nèi)核空間和用戶空間并沒有問題，因為如果某個頁面正在被內(nèi)核使用，對應的page應該已經(jīng)從free_area被摘下，于是缺頁異常處理代碼中不會再將該頁映射到用戶空間。反過來也一樣，被映射到用戶空間的page自然已經(jīng)從free_area被摘下，內(nèi)核不會再去使用這個頁面。

內(nèi)核空間管理(圖：右下)

除了對內(nèi)存整頁的使用，有些時候，內(nèi)核也需要像用戶程序使用malloc一樣，分配一塊任意大小的空間。這個功能是由slab系統(tǒng)來實現(xiàn)的。

slab相當于為內(nèi)核中常用的一些結構體對象建立了對象池，比如對應task結構的池、對應mm結構的池、等等。 而slab也維護有通用的對象池，比如"32字節(jié)大小"的對象池、"64字節(jié)大小"的對象池、等等。內(nèi)核中常用的kmalloc函數(shù)（類似于用戶態(tài)的malloc）就是在這些通用的對象池中實現(xiàn)分配的。

slab除了對象實際使用的內(nèi)存空間外，還有其對應的控制結構。有兩種組織方式，如果對象較大，則控制結構使用專門的頁面來保存；如果對象較小，控制結構與對象空間使用相同的頁面。

除了slab，linux 2.6還引入了mempool（內(nèi)存池）。其意圖是：某些對象我們不希望它會因為內(nèi)存不足而分配失敗，于是我們預先分配若干個，放在mempool中存起來。正常情況下，分配對象時是不會去動mempool里面的資源的，照常通過slab去分配。到系統(tǒng)內(nèi)存緊缺，已經(jīng)無法通過slab分配內(nèi)存時，才會使用 mempool中的內(nèi)容。

頁面換入換出(圖：左上)(圖：右上)

頁面換入換出又是一個很復雜的系統(tǒng)。內(nèi)存頁面被換出到磁盤，與磁盤文件被映射到內(nèi)存，是很相似的兩個過程（內(nèi)存頁被換出到磁盤的動機，就是今后還要從磁盤將其載回內(nèi)存）。所以swap復用了文件子系統(tǒng)的一些機制。

頁面換入換出是一件很費CPU和IO的事情，但是由于內(nèi)存昂貴這一歷史原因，我們只好拿磁盤來擴展內(nèi)存。但是現(xiàn)在內(nèi)存越來越便宜了，我們可以輕松安裝數(shù)G的內(nèi)存，然后將swap系統(tǒng)關閉。于是swap的實現(xiàn)實在讓人難有探索的欲望，在這里就不贅述了。

用戶空間內(nèi)存管理

malloc是libc的庫函數(shù)，用戶程序一般通過它（或類似函數(shù)）來分配內(nèi)存空間。

libc對內(nèi)存的分配有兩種途徑，一是調(diào)整堆的大小，二是mmap一個新的虛擬內(nèi)存區(qū)域（堆也是一個vma）。

在內(nèi)核中，堆是一個一端固定、一端可伸縮的vma（圖：左中）。可伸縮的一端通過系統(tǒng)調(diào)用brk來調(diào)整。libc管理著堆的空間，用戶調(diào)用malloc分配內(nèi)存時，libc盡量從現(xiàn)有的堆中去分配。如果堆空間不夠，則通過brk增大堆空間。

當用戶將已分配的空間free時，libc可能會通過brk減小堆空間。但是堆空間增大容易減小卻難，考慮這樣一種情況，用戶空間連續(xù)分配了10塊內(nèi)存，前9塊已經(jīng)free。這時，未free的第10塊哪怕只有1字節(jié)大，libc也不能夠去減小堆的大小。因為堆只有一端可伸縮，并且中間不能掏空。而第10塊內(nèi)存就死死地占據(jù)著堆可伸縮的那一端，堆的大小沒法減小，相關資源也沒法歸還內(nèi)核。

當用戶malloc一塊很大的內(nèi)存時，libc會通過mmap系統(tǒng)調(diào)用映射一個新的vma。因為對于堆的大小調(diào)整和空間管理還是比較麻煩的，重新建一個vma會更方便（上面提到的free的問題也是原因之一）。

那么為什么不總是在malloc的時候去mmap一個新的vma呢？第一，對于小空間的分配與回收，被libc管理的堆空間已經(jīng)能夠滿足需要，不必每次都去進行系統(tǒng)調(diào)用。并且vma是以page為單位的，最小就是分配一個頁；第二，太多的vma會降低系統(tǒng)性能。缺頁異常、vma的新建與銷毀、堆空間的大小調(diào)整、等等情況下，都需要對vma進行操作，需要在當前進程的所有vma中找到需要被操作的那個（或那些）vma。vma數(shù)目太多，必然導致性能下降。（在進程的vma較少時，內(nèi)核采用鏈表來管理vma；vma較多時，改用紅黑樹來管理。）

用戶的棧

與堆一樣，棧也是一個vma（圖：左中），這個vma是一端固定、一端可伸（注意，不能縮）的。這個vma比較特殊，沒有類似brk的系統(tǒng)調(diào)用讓這個vma伸展，它是自動伸展的。

當用戶訪問的虛擬地址越過這個vma時，內(nèi)核會在處理缺頁異常的時候?qū)⒆詣訉⑦@個vma增大。內(nèi)核會檢查當時的棧寄存器（如：ESP），訪問的虛擬地址不能超過ESP加n（n為CPU壓棧指令一次性壓棧的最大字節(jié)數(shù)）。也就是說，內(nèi)核是以ESP為基準來檢查訪問是否越界。

但是，ESP的值是可以由用戶態(tài)程序自由讀寫的，用戶程序如果調(diào)整ESP，將棧劃得很大很大怎么辦呢？內(nèi)核中有一套關于進程限制的配置，其中就有棧大小的配置，棧只能這么大，再大就出錯。

對于一個進程來說，棧一般是可以被伸展得比較大（如：8MB）。然而對于線程呢？

首先線程的棧是怎么回事？前面說過，線程的mm是共享其父進程的。雖然棧是mm中的一個vma，但是線程不能與其父進程共用這個vma（兩個運行實體顯然不用共用一個棧）。于是，在線程創(chuàng)建時，線程庫通過mmap新建了一個vma，以此作為線程的棧（大于一般為：2M）。

可見，線程的棧在某種意義上并不是真正棧，它是一個固定的區(qū)域，并且容量很有限。