內(nèi)存管理的硬件結(jié)構(gòu)

內(nèi)存管理硬件結(jié)構(gòu)

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

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

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

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

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

分段

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

分頁(yè)

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

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

邏輯地址，線性地址（intel架構(gòu)）

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

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

虛擬地址

簡(jiǎn)單的說就是可以尋址的一片空間。如果這個(gè)空間是虛擬的，我們就叫做虛擬地址空間；如果這個(gè)空間是真實(shí)存在的，我們就叫做物理地址空間。虛擬地址空間是可以任意的大的，因?yàn)槭翘摂M的。而物理地址空間是真實(shí)存在的，所以是有限的

物理地址

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

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

結(jié)構(gòu)圖

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

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

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

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

虛擬地址到物理地址的轉(zhuǎn)換

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

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

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

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

內(nèi)存管理總覽

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

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

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

vm_area_struct

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

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

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

缺頁(yè)中斷

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

伙伴系統(tǒng)

頁(yè)面分配器是以頁(yè)框?yàn)閱挝坏摹５湫偷捻?yè)面分配器就是伙伴系統(tǒng)?；锇橄到y(tǒng)是一個(gè)結(jié)合了2的方冪個(gè)分配器和空閑緩沖區(qū)合并計(jì)技術(shù)的內(nèi)存分配方案, 其基本思想很簡(jiǎn)單。

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

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

slab分配器

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

頁(yè)面回收

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

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

如果分配好了頁(yè)面，這個(gè)時(shí)候就要涉及到頁(yè)表的管理了。頁(yè)表分為內(nèi)核頁(yè)表和進(jìn)程頁(yè)表。內(nèi)核提供了很多和內(nèi)核頁(yè)表相關(guān)的函數(shù)，后續(xù)我們?cè)俜治觥?/p>

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

反向映射

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

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

KSM

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

huge page

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

頁(yè)遷移

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

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

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

大塊連續(xù)的內(nèi)存一般是內(nèi)核所請(qǐng)求的，因?yàn)閷?duì)于用戶空間來講，大塊缺頁(yè)內(nèi)存都是通過缺頁(yè)中斷一塊一塊來分配的。

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

OOM

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

之所以會(huì)發(fā)生這種情況，是因?yàn)長(zhǎng)inux內(nèi)核在給某個(gè)進(jìn)程分配內(nèi)存時(shí)，會(huì)比進(jìn)程申請(qǐng)的內(nèi)存多分配一些。這是為了保證進(jìn)程在真正使用的時(shí)候有足夠的內(nèi)存，因?yàn)檫M(jìn)程在申請(qǐng)內(nèi)存后并不一定立即使用，當(dāng)真正使用的時(shí)候，可能部分內(nèi)存已經(jīng)被回收了。

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

內(nèi)存管理的一些數(shù)據(jù)結(jié)構(gòu)

線性映射

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

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

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

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

struct page

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

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

zone

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

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

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

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

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

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

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

pgd指向進(jìn)程所在的頁(yè)表，這里指的是進(jìn)程的頁(yè)表，進(jìn)程的一級(jí)頁(yè)表在fork的時(shí)候創(chuàng)建，進(jìn)程的二級(jí)頁(yè)表在實(shí)際使用的時(shí)候動(dòng)態(tài)創(chuàng)建，

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