內存管理硬件結構

常見的內存分配函數有malloc，mmap等，但大家有沒有想過，這些函數在內核中是怎么實現的？換句話說，Linux內核的內存管理是怎么實現的？

內存管理的目的是管理系統中的內存，俗稱內存橋，換成專業屬于叫DDR。我們有必要先了解下計算機對內存管理的硬件結構。我們先看下關于地址的一些概念。

早期內存的使用方法

在計算機早期的發展階段，要運行一個程序，要把計算機程序，全部裝載在內存中，程序訪問的內存地址就是實際的物理地址。所以，當運行多個程序時，必須保證運行程序的使用的總的內存量要小于總的內存大小。那這種方式存在什么問題呢？

一個問題是進程地址空間不合理，任意的進程可以隨意修改其他進程的地址數據；二是內存使用效率很低，內存緊張時需要把整個進程交換到交換分區中，導致程序的使用效率很低。

分段

為了解決這兩個問題，當時的人們提出了分段的機制。它的核心思想是建立一個 虛擬地址空間，將一個程序分成代碼段，數據段，堆棧段什么的，每個段各自管理不同的數據。在虛擬地址空間和物理地址空間之間做映射，實現進程的隔離。

分頁

在分段機制中，程序也是全部裝載在內存中的，效率也很低。這個時候就提出了分頁機制：分頁這個技術仍然是一種虛擬地址空間到物理地址空間映射的機制。但是，粒度更加的小了。單位不是整個程序，而是某個“頁”，一段虛擬地址空間組成的某一頁映射到一段物理地址空間組成的某一頁。

程序在運行的時候，需要哪個頁面，我再把相關頁面交換進來。經常不用的頁面會交換到swap分區。分頁機制也是按需分配，這是操作系統的核心思想。

邏輯地址，線性地址（intel架構）

邏輯地址和線性地址是intel架構的概念，邏輯地址是程序產生的和段相關的那個部分，線性地址是邏輯地址轉換為物理地址的一個中間層。

在分段的方式中，邏輯地址是段的偏移地址，再加上基地址就是線性地址了。如果是做arm架構的，可以不用關注這部分。

虛擬地址

簡單的說就是可以尋址的一片空間。如果這個空間是虛擬的，我們就叫做虛擬地址空間；如果這個空間是真實存在的，我們就叫做物理地址空間。虛擬地址空間是可以任意的大的，因為是虛擬的。而物理地址空間是真實存在的，所以是有限的

物理地址

物理地址是CPU通過外部總線直接訪問的外部內存地址。如果系統啟動了分頁機制，系統啟動后必須通過查頁表的方式去獲取物理地址。

如果沒有啟動分頁機制，系統啟動后就通過直接變為了物理地址。

結構圖

在啟動MMU后，CPU訪問的是虛擬地址，虛擬地址經過MMU后轉換為物理地址，這種轉換通過查詢存儲在主存儲器的頁表完成。頻繁訪問主存儲器比較耗時，因此引入了TLB的概念。

TLB緩存了上一次虛擬地址到物理地址的轉換，TLB不存儲具體的數據，存儲的是頁表的表項。如果能在TLB中找到本次訪問的頁表項，就不需要再訪問主存了。我們把這個過程叫做TLB命中。如果沒有找到頁表項，這個時候只能去查詢頁表，我們叫做TLB Miss。如何查詢頁表的后面我們會詳細介紹。

假設，現在虛擬地址已經轉換為了物理地址。這個時候就會去找一級緩存?？匆患壘彺嬗袥]有需要的數據。我們這里采用的是物理索引（PI），物理標簽（PT）的方式?，F在的大部分cache都采用組相聯的方式，訪問cache地址會被分為偏移域，索引域，標記域三部分。如果一級緩存沒有相應的數據，就要訪問二級緩存了，如果二級緩存沒有數據，就要訪問主存儲器了。

還有一種情況，當系統物理內存短缺的時候，Linux內核中，有頁面回收的機制，會把不常用的頁面交換到swap分區中，這個動作叫做swap。這張圖就從硬件結構的角度解釋了內存管理的基本構成。

虛擬地址到物理地址的轉換

虛擬地址的32個bit位可以分為3個域，最高12bit位20~31位稱為L1索引，叫做PGD，頁面目錄。中間的8個bit位叫做L2索引，在Linux內核中叫做PT，頁表。最低的12位叫做頁索引。

在ARM處理器中，TTBRx寄存器存放著頁表基地址，我們這里的一級頁表有4096個頁表項。每個表項中存放著二級表項的基地址。我們可以通過虛擬地址的L1索引訪問一級頁表，訪問一級頁表相當于數組訪問。

二級頁表通常是動態分配的，可以通過虛擬地址的中間8bit位L2索引訪問二級頁表，在L2索引中存放著最終物理地址的高20bit位，然后和虛擬地址的低12bit位就組成了最終的物理地址。以上就是虛擬地址轉換為物理地址的過程。

MMU訪問頁表是硬件實現的，但頁表的創建和填充需要Linux內核來填充。通常，一級頁表和二級頁表存放在主存儲器中。

內存管理總覽

系統調用

Linux內核把用戶空間分為兩部分：用戶空間和內核空間。用戶進程運行在用戶空間，如果需要內存的話通過C庫提供的malloc，mmap，mlock，madvice，mremap函數。C庫的這些函數最終都會調用到內核的sys_xxx接口分配內存空間。如malloc函數是依賴內核的sys_brk接口分配內存空間的。mmap對應接口為sys_mmap。

我們以malloc函數為例，假設現在用戶態的內存短缺，就會通過sys_brk調用去堆上分配內存。在用戶空間分配的是虛擬內存，因此，在堆上分配的也是虛擬內存。

vm_area_struct

Linux內核把這些地址稱為進程地址空間。內核使用struct vm_area_struct 來管理這些進程地址空間。VMA主要管理內存的創建，插入，刪除，合并等操作。

由于每個不同質的虛擬內存區域功能和內部機制都不同，因此一個進程使用多個vm_area_struct結構來分別表示不同類型的虛擬內存區域。各個vm_area_struct結構使用鏈表或者樹形結構鏈接，方便進程快速訪問，如下圖所示：

vm_area_struct結構中包含區域起始和終止地址以及其他相關信息，同時也包含一個vm_ops指針，其內部可引出所有針對這個區域可以使用的系統調用函數。這樣，進程對某一虛擬內存區域的任何操作需要用要的信息，都可以從vm_area_struct中獲得。mmap函數就是要創建一個新的vm_area_struct結構，并將其與文件的物理磁盤地址相連。

缺頁中斷

缺頁中斷是實現了按需分配的思想。站在用戶角度，缺頁中斷后可分配的頁面有匿名頁面和page cache。匿名頁面指的是沒有關聯任何文件的頁面，比如進程通過mlock從堆上分配的內存。page cache是關聯了具體緩存的頁面。比如在看視頻時的緩存就是page cache。匿名頁面和page cache的產生需要頁面分配器完成。

伙伴系統

頁面分配器是以頁框為單位的。典型的頁面分配器就是伙伴系統。伙伴系統是一個結合了2的方冪個分配器和空閑緩沖區合并計技術的內存分配方案, 其基本思想很簡單。

內存被分成含有很多頁面的大塊, 每一塊都是2個頁面大小的方冪。如果找不到想要的塊, 一個大塊會被分成兩部分, 這兩部分彼此就成為伙伴。其中一半被用來分配，而另一半則空閑。這些塊在以后分配的過程中會繼續被二分直至產生一個所需大小的塊。當一個塊被最終釋放時， 其伙伴將被檢測出來，如果伙伴也空閑則合并兩者。

雖然伙伴算法實現不復雜，但頁面分配器是內核實現最復雜的系統之一。如果內存充足時，你需要多少內存，頁面分配器會給你分配多少。但如果內存緊張時，頁面分配器會做很多嘗試，比如開啟異步模式的頁面回收，memory compaction（內存規整）。如果經過嘗試后內存仍然不夠，這個時候會拿出重型武器oom kill會殺死一些進程。

slab分配器

剛剛我們講的都是以頁為單位分配的內存。但有時候我們需要幾個字節的內存怎么辦。這個時候就需要slab分配器。slab可以管理特定大小的內存，對于固定大小的內存就不需要VMA去管理了。頁面分配器是中央財政，slab是地方財政。如果地方需要種棵樹就不要勞煩中央財政了。

頁面回收

頁面回收實現了頁面換出的理念。當系統內存短缺的時候，系統需要換出一部分內存。這部分內存通常是page cache 或者匿名頁面。內核里面有個swap守護線程，當系統內存低于某個水位時，會被喚醒去掃描LRU（最近最少使用）鏈表，一般匿名頁面和page cache會添加到鏈表中。實際上，在內核中又將LRU鏈表做了細分，又細分為活躍鏈表，不活躍鏈表，匿名頁面鏈表，page cache鏈表。

內核相對比較喜歡回收page cache，干凈的page cache 直接合并就好了。對于臟的page cache需要寫回磁盤的一個動作。對于匿名頁面是不能直接合并的，匿名頁面一般都是進程的私有數據。一般這些匿名頁面數據需要回收時會swap out 到swap分區騰出空間，當這些進程再次需要這些數據時，才會從swap分區swap in。頁面回收我們會在后面詳細講解。

如果分配好了頁面，這個時候就要涉及到頁表的管理了。頁表分為內核頁表和進程頁表。內核提供了很多和內核頁表相關的函數，后續我們再分析。

再往下分析就是硬件層，比如MMU，TLB，cache，物理內存等，對于這部分我們不做深入分析。

反向映射

當進程分配內存并發生寫操作時，會分配虛擬地址并產生缺頁,進而分配物理內存并建立虛擬地址到物理地址的映射關系， 這個叫正向映射。

反過來， 通過物理頁面找到映射它的所有虛擬頁面叫反向映射（reverse-mapping, RMAP），它可以從page數據結構中找到映射這個page的虛擬地址空間，也就是我們講過的VMA這個東西，ramp系統是為頁面回收服務的，如果要回收一個匿名頁面或者page cache的時候， 需要把映射這個頁面的用戶PTE斷開映射關系才可以去回收。

KSM

KSM，Kernel Samepage Merging，最早是用來優化KVM虛擬機來發明的一種機制?，F在用來合并內容相同的匿名頁面。

huge page

huge page，通常用來分配2M或者1G大小的頁，目前在服務器系統中用的比較多。使用huge page可以減少TLB miss的次數，假如現在需要2M的頁面，一個page是4K，最壞的情況下需要TLB miss 5次，如果使用2M的頁面，只需要TLB miss 1次。每次TLB miss 對系統的損耗很大。

頁遷移

頁遷移，內核中有些頁面是可以遷移的，比如匿名頁面。頁遷移在內核很多模塊都被廣泛使用，比如memory compaction（內存規整）。

內存規整

memory compaction，內存規整模塊是為了緩解內存碎片化的，系統運行的時間越長，就越容易產生內存碎片，系統此時想分配連續的大塊內存就變得越來越難。

大塊連續的內存一般是內核所請求的，因為對于用戶空間來講，大塊缺頁內存都是通過缺頁中斷一塊一塊來分配的。

內存規整的實現原理也不復雜，在一個zoom中有兩個掃描器，分別從頭到尾和從尾到頭掃描，一個去查找zoom中有那些頁面可以遷移的，另外一個去掃描有那些空閑的頁，兩個掃描器在zoom中相遇的時候，掃描就停止了。這個時候內存規整模塊就知道zoom中有那些頁面可以遷移到空閑頁面。經過這么一折騰，就可以騰出一個大的連續的物理空間了。

OOM

在經過內存規整，頁面遷移等操作后，如果系統還不能分配出系統需要的頁面，Linux就要使用最后一招了，殺敵一千，自損八百，OOM killer會找一些占用內存比較多的進程殺掉來釋放內存。

之所以會發生這種情況，是因為Linux內核在給某個進程分配內存時，會比進程申請的內存多分配一些。這是為了保證進程在真正使用的時候有足夠的內存，因為進程在申請內存后并不一定立即使用，當真正使用的時候，可能部分內存已經被回收了。

比如 當一個進程申請2G內存時，內核可能會分配2.5G的內存給它.通常這不會導致什么問題。然而一旦系統內大量的進程在使用內存時，就會出現內存供不應求，很快就會導致內存耗盡。這時就會觸發這個oom killer，它會選擇性的殺掉某個進程以保證系統能夠正常運行。

內存管理的一些數據結構

線性映射

我們以32位系統為例，我們知道進程最大的地址訪問空間是4G，0~3GB是用戶空間，3 ~ 4GB是內核空間。

如果物理空間是大于1GB，內核空間如何訪問大于1GB的空間呢？站在內核的角度，低地址段是線性映射，高地址段是高端映射。

那線性映射和高端映射是如何劃分的呢？不同的體系結構有不同的劃分方法。在ARM32中是線性映射大小為760M。線性映射就是直接把物理地址空間映射到3G ~ 4G的地址空間，這段映射關系就變得比較簡單了，內核訪問時直接使用虛擬地址減去偏移量（page offset）就得到物理地址了。

如果要訪問高端內存就麻煩一點，1G的物理內存空間有限，不能把所有地址都映射到線性地址空間。如果要訪問高端內存就要通過動態映射的方式訪問了。

struct page

struct page數據結構是用來抽象物理頁面的。這個數據結構很重要，很多內核代碼都是圍繞這個struct page 展開的。

此外還有個很重要的mem_map[]數組，是用來存放每一個struct page數據結構的。通過數組，我們可以很方便的通過page找到頁幀號，頁幀號全稱叫page frame number ，pfm。

zone

除了page結構，還有個很重要的數據結構叫zone。前面講到了物理內存劃分為兩部分，線性映射和高端內存。zone也是根據這個來劃分的。線性映射部分叫zone normal，高端內存區域叫zone high。

頁面分配器和頁面回收都是基于zone來管理的。zone 也是一個很重要的管理物理內存的數據結構。

進程角度看內存管理

看完物理內存的管理結構，接下來從進程的角度看下虛擬內存是怎么管理的。

用戶空間有3G的大小，這3GB的大小也做了劃分，0 ~ 1GB 屬于代碼段，數據段，堆空間。1G ~ 3G 屬于mmap空間。

每個進程都有一個管理進程的數據結構，操作系統中叫做PCB，進程控制塊，linux內核中就用task_struct描述進程控制塊，task_struct內容非常多，后面我們會詳細講解，今天我們只關注mm成員。

mm成員會指向mm_struct描述進程管理的內存資源，我們這里只關注mmap，pgd。mmap指向該進程的VMA的鏈表。我們知道進程地址空間使用VMA來管理，VMA是離散的，所以內核使用兩種方式來管理VMA：鏈表和紅黑樹。

pgd指向進程所在的頁表，這里指的是進程的頁表，進程的一級頁表在fork的時候創建，進程的二級頁表在實際使用的時候動態創建，

以上這張圖就從進程的角度講述了內存管理的概貌。