內(nèi)存管理硬件結構

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

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

早期內(nèi)存的使用方法

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

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

分段

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

分頁

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

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

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

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

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

虛擬地址

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

物理地址

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

如果沒有啟動分頁機制，系統(tǒng)啟動后就通過直接變?yōu)榱宋锢淼刂贰?/p>

結構圖

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

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

假設，現(xiàn)在虛擬地址已經(jīng)轉換為了物理地址。這個時候就會去找一級緩存。看一級緩存有沒有需要的數(shù)據(jù)。我們這里采用的是物理索引（PI），物理標簽（PT）的方式。現(xiàn)在的大部分cache都采用組相聯(lián)的方式，訪問cache地址會被分為偏移域，索引域，標記域三部分。如果一級緩存沒有相應的數(shù)據(jù)，就要訪問二級緩存了，如果二級緩存沒有數(shù)據(jù)，就要訪問主存儲器了。

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

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

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

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

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

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

內(nèi)存管理總覽

系統(tǒng)調(diào)用

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

我們以malloc函數(shù)為例，假設現(xiàn)在用戶態(tài)的內(nèi)存短缺，就會通過sys_brk調(diào)用去堆上分配內(nèi)存。在用戶空間分配的是虛擬內(nèi)存，因此，在堆上分配的也是虛擬內(nèi)存。

vm_area_struct

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

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

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

缺頁中斷

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

伙伴系統(tǒng)

頁面分配器是以頁框為單位的。典型的頁面分配器就是伙伴系統(tǒng)?；锇橄到y(tǒng)是一個結合了2的方冪個分配器和空閑緩沖區(qū)合并計技術的內(nèi)存分配方案, 其基本思想很簡單。

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

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

slab分配器

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

頁面回收

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

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

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

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

反向映射

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

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

KSM

KSM，Kernel Samepage Merging，最早是用來優(yōu)化KVM虛擬機來發(fā)明的一種機制?，F(xiàn)在用來合并內(nèi)容相同的匿名頁面。

huge page

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

頁遷移

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

內(nèi)存規(guī)整

memory compaction，內(nèi)存規(guī)整模塊是為了緩解內(nèi)存碎片化的，系統(tǒng)運行的時間越長，就越容易產(chǎn)生內(nèi)存碎片，系統(tǒng)此時想分配連續(xù)的大塊內(nèi)存就變得越來越難。

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

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

OOM

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

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

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

內(nèi)存管理的一些數(shù)據(jù)結構

線性映射

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

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

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

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

struct page

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

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

zone

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

頁面分配器和頁面回收都是基于zone來管理的。zone 也是一個很重要的管理物理內(nèi)存的數(shù)據(jù)結構。

進程角度看內(nèi)存管理

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

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

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

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

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

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