知識(shí)總結(jié)：一篇就讓你入Linux內(nèi)核的大門

Linux的內(nèi)存管理可謂是學(xué)好Linux的必經(jīng)之路，也是Linux的關(guān)鍵知識(shí)點(diǎn)，有人說打通了內(nèi)存管理的知識(shí)，也就打通了Linux的任督二脈，這一點(diǎn)不夸張。有人問網(wǎng)上有很多Linux內(nèi)存管理的內(nèi)容，為什么還要看你這一篇，這正是我寫此文的原因，網(wǎng)上碎片化的相關(guān)知識(shí)點(diǎn)大都是東拼西湊，先不說正確性與否，就連基本的邏輯都沒有搞清楚，我可以負(fù)責(zé)任的說Linux內(nèi)存管理只需要看此文一篇就可以讓你入Linux內(nèi)核的大門，省去你東找西找的時(shí)間，讓你形成內(nèi)存管理知識(shí)的閉環(huán)。

文章比較長(zhǎng)，做好準(zhǔn)備，深呼吸，讓我們一起打開Linux內(nèi)核的大門！

Linux內(nèi)存管理之CPU訪問內(nèi)存的過程我喜歡用圖的方式來說明問題，簡(jiǎn)單直接：

藍(lán)色部分是cpu，灰色部分是內(nèi)存，白色部分就是cpu訪問內(nèi)存的過程，也是地址轉(zhuǎn)換的過程。在解釋地址轉(zhuǎn)換的本質(zhì)前我們先理解下幾個(gè)概念：

TLB：MMU工作的過程就是查詢頁表的過程。如果把頁表放在內(nèi)存中查詢的時(shí)候開銷太大，因此為了提高查找效率，專門用一小片訪問更快的區(qū)域存放地址轉(zhuǎn)換條目。（當(dāng)頁表內(nèi)容有變化的時(shí)候，需要清除TLB，以防止地址映射出錯(cuò)。）

Caches：cpu和內(nèi)存之間的緩存機(jī)制，用于提高訪問速率，armv8架構(gòu)的話上圖的caches其實(shí)是L2 Cache，這里就不做進(jìn)一步解釋了。

虛擬地址轉(zhuǎn)換為物理地址的本質(zhì)

我們知道內(nèi)核中的尋址空間大小是由CONFIG_ARM64_VA_BITS控制的，這里以48位為例，ARMv8中，Kernel Space的頁表基地址存放在TTBR1_EL1寄存器中，User Space頁表基地址存放在TTBR0_EL0寄存器中，其中內(nèi)核地址空間的高位為全1，（0xFFFF0000_00000000 ~ 0xFFFFFFFF_FFFFFFFF），用戶地址空間的高位為全0，（0x00000000_00000000 ~ 0x0000FFFF_FFFFFFFF）

有了宏觀概念，下面我們以內(nèi)核態(tài)尋址過程為例看下是如何把虛擬地址轉(zhuǎn)換為物理地址的。

我們知道linux采用了分頁機(jī)制，通常采用四級(jí)頁表，頁全局目錄（PGD），頁上級(jí)目錄（PUD），頁中間目錄（PMD），頁表（PTE）。如下：

從CR3寄存器中讀取頁目錄所在物理頁面的基址（即所謂的頁目錄基址），從線性地址的第一部分獲取頁目錄項(xiàng)的索引，兩者相加得到頁目錄項(xiàng)的物理地址。

第一次讀取內(nèi)存得到pgd_t結(jié)構(gòu)的目錄項(xiàng)，從中取出物理頁基址取出，即頁上級(jí)頁目錄的物理基地址。

從線性地址的第二部分中取出頁上級(jí)目錄項(xiàng)的索引，與頁上級(jí)目錄基地址相加得到頁上級(jí)目錄項(xiàng)的物理地址。

第二次讀取內(nèi)存得到pud_t結(jié)構(gòu)的目錄項(xiàng)，從中取出頁中間目錄的物理基地址。

從線性地址的第三部分中取出頁中間目錄項(xiàng)的索引，與頁中間目錄基址相加得到頁中間目錄項(xiàng)的物理地址。

第三次讀取內(nèi)存得到pmd_t結(jié)構(gòu)的目錄項(xiàng)，從中取出頁表的物理基地址。

從線性地址的第四部分中取出頁表項(xiàng)的索引，與頁表基址相加得到頁表項(xiàng)的物理地址。

第四次讀取內(nèi)存得到pte_t結(jié)構(gòu)的目錄項(xiàng)，從中取出物理頁的基地址。

從線性地址的第五部分中取出物理頁內(nèi)偏移量，與物理頁基址相加得到最終的物理地址。

第五次讀取內(nèi)存得到最終要訪問的數(shù)據(jù)。

整個(gè)過程是比較機(jī)械的，每次轉(zhuǎn)換先獲取物理頁基地址，再從線性地址中獲取索引，合成物理地址后再訪問內(nèi)存。不管是頁表還是要訪問的數(shù)據(jù)都是以頁為單位存放在主存中的，因此每次訪問內(nèi)存時(shí)都要先獲得基址，再通過索引（或偏移）在頁內(nèi)訪問數(shù)據(jù)，因此可以將線性地址看作是若干個(gè)索引的集合。

Linux內(nèi)存初始化有了armv8架構(gòu)訪問內(nèi)存的理解，我們來看下linux在內(nèi)存這塊的初始化就更容易理解了。

創(chuàng)建啟動(dòng)頁表：

在匯編代碼階段的head.S文件中，負(fù)責(zé)創(chuàng)建映射關(guān)系的函數(shù)是create_page_tables。create_page_tables函數(shù)負(fù)責(zé)identity mapping和kernel image mapping。

identity map：是指把idmap_text區(qū)域的物理地址映射到相等的虛擬地址上，這種映射完成后，其虛擬地址等于物理地址。idmap_text區(qū)域都是一些打開MMU相關(guān)的代碼。

kernel image map：將kernel運(yùn)行需要的地址（kernel txt、rodata、data、bss等等）進(jìn)行映射。

arch/arm64/kernel/head.S：

ENTRY（stext）

bl preserve_boot_args

bl el2_setup // Drop to EL1， w0=cpu_boot_mode

adrp x23， __PHYS_OFFSET

and x23， x23， MIN_KIMG_ALIGN - 1 // KASLR offset， defaults to 0

bl set_cpu_boot_mode_flag

bl __create_page_tables

/*

* The following calls CPU setup code， see arch/arm64/mm/proc.S for

* details.

* On return， the CPU will be ready for the MMU to be turned on and

* the TCR will have been set.

*/

bl __cpu_setup // initialise processor

b __primary_switch

ENDPROC（stext）

__create_page_tables主要執(zhí)行的就是identity map和kernel image map：

__create_page_tables：

。..。..

create_pgd_entry x0， x3， x5， x6

mov x5， x3 // __pa（__idmap_text_start）

adr_l x6， __idmap_text_end // __pa（__idmap_text_end）

create_block_map x0， x7， x3， x5， x6

/*

* Map the kernel image （starting with PHYS_OFFSET）。

*/

adrp x0， swapper_pg_dir

mov_q x5， KIMAGE_VADDR + TEXT_OFFSET // compile time __va（_text）

add x5， x5， x23 // add KASLR displacement

create_pgd_entry x0， x5， x3， x6

adrp x6， _end // runtime __pa（_end）

adrp x3， _text // runtime __pa（_text）

sub x6， x6， x3 // _end - _text

add x6， x6， x5 // runtime __va（_end）

create_block_map x0， x7， x3， x5， x6

。..。..

其中調(diào)用create_pgd_entry進(jìn)行PGD及所有中間level（PUD， PMD）頁表的創(chuàng)建，調(diào)用create_block_map進(jìn)行PTE頁表的映射。關(guān)于四級(jí)頁表的關(guān)系如下圖所示，這里就不進(jìn)一步解釋了。

匯編結(jié)束后的內(nèi)存映射關(guān)系如下圖所示：

等內(nèi)存初始化后就可以進(jìn)入真正的內(nèi)存管理了，初始化我總結(jié)了一下，大體分為四步：

物理內(nèi)存進(jìn)系統(tǒng)前

用memblock模塊來對(duì)內(nèi)存進(jìn)行管理

頁表映射

zone初始化

Linux是如何組織物理內(nèi)存的？

node目前計(jì)算機(jī)系統(tǒng)有兩種體系結(jié)構(gòu)：

非一致性內(nèi)存訪問 NUMA（Non-Uniform Memory Access）意思是內(nèi)存被劃分為各個(gè)node，訪問一個(gè)node花費(fèi)的時(shí)間取決于CPU離這個(gè)node的距離。每一個(gè)cpu內(nèi)部有一個(gè)本地的node，訪問本地node時(shí)間比訪問其他node的速度快

一致性內(nèi)存訪問 UMA（Uniform Memory Access）也可以稱為SMP（Symmetric Multi-Process）對(duì)稱多處理器。意思是所有的處理器訪問內(nèi)存花費(fèi)的時(shí)間是一樣的。也可以理解整個(gè)內(nèi)存只有一個(gè)node。

zone

ZONE的意思是把整個(gè)物理內(nèi)存劃分為幾個(gè)區(qū)域，每個(gè)區(qū)域有特殊的含義

page

代表一個(gè)物理頁，在內(nèi)核中一個(gè)物理頁用一個(gè)struct page表示。

page frame

為了描述一個(gè)物理page，內(nèi)核使用struct page結(jié)構(gòu)來表示一個(gè)物理頁。假設(shè)一個(gè)page的大小是4K的，內(nèi)核會(huì)將整個(gè)物理內(nèi)存分割成一個(gè)一個(gè)4K大小的物理頁，而4K大小物理頁的區(qū)域我們稱為page frame

page frame num（pfn）

pfn是對(duì)每個(gè)page frame的編號(hào)。故物理地址和pfn的關(guān)系是：

物理地址》》PAGE_SHIFT = pfn

pfn和page的關(guān)系

內(nèi)核中支持了好幾個(gè)內(nèi)存模型：CONFIG_FLATMEM（平坦內(nèi)存模型）CONFIG_DISCONTIGMEM（不連續(xù)內(nèi)存模型）CONFIG_SPARSEMEM_VMEMMAP（稀疏的內(nèi)存模型）目前ARM64使用的稀疏的類型模式。

系統(tǒng)啟動(dòng)的時(shí)候，內(nèi)核會(huì)將整個(gè)struct page映射到內(nèi)核虛擬地址空間vmemmap的區(qū)域，所以我們可以簡(jiǎn)單的認(rèn)為struct page的基地址是vmemmap，則：

vmemmap+pfn的地址就是此struct page對(duì)應(yīng)的地址。

Linux分區(qū)頁框分配器頁框分配在內(nèi)核里的機(jī)制我們叫做分區(qū)頁框分配器（zoned page frame allocator），在linux系統(tǒng)中，分區(qū)頁框分配器管理著所有物理內(nèi)存，無論你是內(nèi)核還是進(jìn)程，都需要請(qǐng)求分區(qū)頁框分配器，這時(shí)才會(huì)分配給你應(yīng)該獲得的物理內(nèi)存頁框。當(dāng)你所擁有的頁框不再使用時(shí)，你必須釋放這些頁框，讓這些頁框回到管理區(qū)頁框分配器當(dāng)中。

有時(shí)候目標(biāo)管理區(qū)不一定有足夠的頁框去滿足分配，這時(shí)候系統(tǒng)會(huì)從另外兩個(gè)管理區(qū)中獲取要求的頁框，但這是按照一定規(guī)則去執(zhí)行的，如下：

如果要求從DMA區(qū)中獲取，就只能從ZONE_DMA區(qū)中獲取。

如果沒有規(guī)定從哪個(gè)區(qū)獲取，就按照順序從 ZONE_NORMAL -》 ZONE_DMA 獲取。

如果規(guī)定從HIGHMEM區(qū)獲取，就按照順序從 ZONE_HIGHMEM -》 ZONE_NORMAL -》 ZONE_DMA 獲取。

內(nèi)核中根據(jù)不同的分配需求有6個(gè)函數(shù)接口來請(qǐng)求頁框，最終都會(huì)調(diào)用到__alloc_pages_nodemask。

struct page *

__alloc_pages_nodemask（gfp_t gfp_mask， unsigned int order， int preferred_nid，

nodemask_t *nodemask）

{

page = get_page_from_freelist（alloc_mask， order， alloc_flags， &ac）;//fastpath分配頁面：從pcp（per_cpu_pages）和伙伴系統(tǒng)中正常的分配內(nèi)存空間

。..。..

page = __alloc_pages_slowpath（alloc_mask， order， &ac）;//slowpath分配頁面：如果上面沒有分配到空間，調(diào)用下面函數(shù)慢速分配，允許等待和回收

。..。..

}

在頁面分配時(shí)，有兩種路徑可以選擇，如果在快速路徑中分配成功了，則直接返回分配的頁面；快速路徑分配失敗則選擇慢速路徑來進(jìn)行分配?？偨Y(jié)如下：

正常分配（或叫快速分配）：

如果分配的是單個(gè)頁面，考慮從per CPU緩存中分配空間，如果緩存中沒有頁面，從伙伴系統(tǒng)中提取頁面做補(bǔ)充。

分配多個(gè)頁面時(shí)，從指定類型中分配，如果指定類型中沒有足夠的頁面，從備用類型鏈表中分配。最后會(huì)試探保留類型鏈表。

慢速（允許等待和頁面回收）分配：

當(dāng)上面兩種分配方案都不能滿足要求時(shí)，考慮頁面回收、殺死進(jìn)程等操作后在試。

Linux頁框分配器之伙伴算法static struct page *

get_page_from_freelist（gfp_t gfp_mask， unsigned int order， int alloc_flags，

const struct alloc_context *ac）

{

for_next_zone_zonelist_nodemask（zone， z， ac-》zonelist， ac-》high_zoneidx， ac-》nodemask）

{

if （！zone_watermark_fast（zone， order， mark， ac_classzone_idx（ac）， alloc_flags））

{

ret = node_reclaim（zone-》zone_pgdat， gfp_mask， order）;

switch （ret） {

case NODE_RECLAIM_NOSCAN：

continue;

case NODE_RECLAIM_FULL：

continue;

default：

if （zone_watermark_ok（zone， order， mark， ac_classzone_idx（ac）， alloc_flags））

goto try_this_zone;

continue;

}

}

try_this_zone： //本zone正常水位

page = rmqueue（ac-》preferred_zoneref-》zone， zone， order， gfp_mask， alloc_flags， ac-》migratetype）;

}

return NULL;

}

首先遍歷當(dāng)前zone，按照HIGHMEM-》NORMAL的方向進(jìn)行遍歷，判斷當(dāng)前zone是否能夠進(jìn)行內(nèi)存分配的條件是首先判斷free memory是否滿足low water mark水位值，如果不滿足則進(jìn)行一次快速的內(nèi)存回收操作，然后再次檢測(cè)是否滿足low water mark，如果還是不能滿足，相同步驟遍歷下一個(gè)zone，滿足的話進(jìn)入正常的分配情況，即rmqueue函數(shù)，這也是伙伴系統(tǒng)的核心。

Buddy 分配算法

在看函數(shù)前，我們先看下算法，因?yàn)槲乙恢闭J(rèn)為有了“道”的理解才好進(jìn)一步理解“術(shù)”。

假設(shè)這是一段連續(xù)的頁框，陰影部分表示已經(jīng)被使用的頁框，現(xiàn)在需要申請(qǐng)一個(gè)連續(xù)的5個(gè)頁框。這個(gè)時(shí)候，在這段內(nèi)存上不能找到連續(xù)的5個(gè)空閑的頁框，就會(huì)去另一段內(nèi)存上去尋找5個(gè)連續(xù)的頁框，這樣子，久而久之就形成了頁框的浪費(fèi)。為了避免出現(xiàn)這種情況，Linux內(nèi)核中引入了伙伴系統(tǒng)算法（Buddy system）。把所有的空閑頁框分組為11個(gè)塊鏈表，每個(gè)塊鏈表分別包含大小為1，2，4，8，16，32，64，128，256，512和1024個(gè)連續(xù)頁框的頁框塊。最大可以申請(qǐng)1024個(gè)連續(xù)頁框，對(duì)應(yīng)4MB大小的連續(xù)內(nèi)存。每個(gè)頁框塊的第一個(gè)頁框的物理地址是該塊大小的整數(shù)倍，如圖：

假設(shè)要申請(qǐng)一個(gè)256個(gè)頁框的塊，先從256個(gè)頁框的鏈表中查找空閑塊，如果沒有，就去512個(gè)頁框的鏈表中找，找到了則將頁框塊分為2個(gè)256個(gè)頁框的塊，一個(gè)分配給應(yīng)用，另外一個(gè)移到256個(gè)頁框的鏈表中。如果512個(gè)頁框的鏈表中仍沒有空閑塊，繼續(xù)向1024個(gè)頁框的鏈表查找，如果仍然沒有，則返回錯(cuò)誤。頁框塊在釋放時(shí)，會(huì)主動(dòng)將兩個(gè)連續(xù)的頁框塊合并為一個(gè)較大的頁框塊。

從上面可以知道Buddy算法一直在對(duì)頁框做拆開合并拆開合并的動(dòng)作。Buddy算法牛逼就牛逼在運(yùn)用了世界上任何正整數(shù)都可以由2^n的和組成。這也是Buddy算法管理空閑頁表的本質(zhì)?？臻e內(nèi)存的信息我們可以通過以下命令獲?。?/p>

也可以通過echo m 》 /proc/sysrq-trigger來觀察buddy狀態(tài)，與/proc/buddyinfo的信息是一致的：

Buddy 分配函數(shù)

static inline

struct page *rmqueue（struct zone *preferred_zone，

struct zone *zone， unsigned int order，

gfp_t gfp_flags， unsigned int alloc_flags，

int migratetype）

{

if （likely（order == 0）） { //如果order=0則從pcp中分配

page = rmqueue_pcplist（preferred_zone， zone， order， gfp_flags， migratetype）;

}

do {

page = NULL;

if （alloc_flags & ALLOC_HARDER） {//如果分配標(biāo)志中設(shè)置了ALLOC_HARDER，則從free_list［MIGRATE_HIGHATOMIC］的鏈表中進(jìn)行頁面分配

page = __rmqueue_smallest（zone， order， MIGRATE_HIGHATOMIC）;

}

if （！page） //前兩個(gè)條件都不滿足，則在正常的free_list［MIGRATE_*］中進(jìn)行分配

page = __rmqueue（zone， order， migratetype）;

} while （page && check_new_pages（page， order））;

。..。..

}

Linux分區(qū)頁框分配器之水位我們講頁框分配器的時(shí)候講到了快速分配和慢速分配，其中伙伴算法是在快速分配里做的，忘記的小伙伴我們?cè)倏聪拢?/p>

static struct page *

get_page_from_freelist（gfp_t gfp_mask， unsigned int order， int alloc_flags，

const struct alloc_context *ac）

{

for_next_zone_zonelist_nodemask（zone， z， ac-》zonelist， ac-》high_zoneidx， ac-》nodemask）

{

if （！zone_watermark_fast（zone， order， mark， ac_classzone_idx（ac）， alloc_flags））

{

ret = node_reclaim（zone-》zone_pgdat， gfp_mask， order）;

switch （ret） {

case NODE_RECLAIM_NOSCAN：

continue;

case NODE_RECLAIM_FULL：

continue;

default：

if （zone_watermark_ok（zone， order， mark， ac_classzone_idx（ac）， alloc_flags））

goto try_this_zone;

continue;

}

}

try_this_zone： //本zone正常水位

page = rmqueue（ac-》preferred_zoneref-》zone， zone， order， gfp_mask， alloc_flags， ac-》migratetype）;

}

return NULL;

}

可以看到在進(jìn)行伙伴算法分配前有個(gè)關(guān)于水位的判斷，今天我們就看下水位的概念。

簡(jiǎn)單的說在使用分區(qū)頁面分配器中會(huì)將可以用的free pages與zone里的水位（watermark）進(jìn)行比較。

水位初始化

nr_free_buffer_pages 是獲取ZONE_DMA和ZONE_NORMAL區(qū)中高于high水位的總頁數(shù)nr_free_buffer_pages = managed_pages - high_pages

min_free_kbytes 是總的min大小，min_free_kbytes = 4 * sqrt（lowmem_kbytes）

setup_per_zone_wmarks 根據(jù)總的min值，再加上各個(gè)zone在總內(nèi)存中的占比，然后通過do_div就計(jì)算出他們各自的min值，進(jìn)而計(jì)算出各個(gè)zone的水位大小。min，low，high的關(guān)系如下：low = min *125%;

high = min * 150%

minhigh = 46

setup_per_zone_lowmem_reserve 當(dāng)從Normal失敗后，會(huì)嘗試從DMA申請(qǐng)分配，通過lowmem_reserve［DMA］，限制來自Normal的分配請(qǐng)求。其值可以通過/proc/sys/vm/lowmem_reserve_ratio來修改。

從這張圖可以看出：

如果空閑頁數(shù)目min值，則該zone非常缺頁，頁面回收壓力很大，應(yīng)用程序?qū)憙?nèi)存操作就會(huì)被阻塞，直接在應(yīng)用程序的進(jìn)程上下文中進(jìn)行回收，即direct reclaim。

如果空閑頁數(shù)目小于low值，kswapd線程將被喚醒，并開始釋放回收頁面。

如果空閑頁面的值大于high值，則該zone的狀態(tài)很完美， kswapd線程將重新休眠。

Linux頁框分配器之內(nèi)存碎片化整理什么是內(nèi)存碎片化

Linux物理內(nèi)存碎片化包括兩種：內(nèi)部碎片化和外部碎片化。

內(nèi)部碎片化：

指分配給用戶的內(nèi)存空間中未被使用的部分。例如進(jìn)程需要使用3K bytes物理內(nèi)存，于是向系統(tǒng)申請(qǐng)了大小等于3Kbytes的內(nèi)存，但是由于Linux內(nèi)核伙伴系統(tǒng)算法最小顆粒是4K bytes，所以分配的是4Kbytes內(nèi)存，那么其中1K bytes未被使用的內(nèi)存就是內(nèi)存內(nèi)碎片。

外部碎片化：

指系統(tǒng)中無法利用的小內(nèi)存塊。例如系統(tǒng)剩余內(nèi)存為16K bytes，但是這16K bytes內(nèi)存是由4個(gè)4K bytes的頁面組成，即16K內(nèi)存物理頁幀號(hào)#1不連續(xù)。在系統(tǒng)剩余16K bytes內(nèi)存的情況下，系統(tǒng)卻無法成功分配大于4K的連續(xù)物理內(nèi)存，該情況就是內(nèi)存外碎片導(dǎo)致。

碎片化整理算法

Linux內(nèi)存對(duì)碎片化的整理算法主要應(yīng)用了內(nèi)核的頁面遷移機(jī)制，是一種將可移動(dòng)頁面進(jìn)行遷移后騰出連續(xù)物理內(nèi)存的方法。

假設(shè)存在一個(gè)非常小的內(nèi)存域如下：

藍(lán)色表示空閑的頁面，白色表示已經(jīng)被分配的頁面，可以看到如上內(nèi)存域的空閑頁面（藍(lán)色）非常零散，無法分配大于兩頁的連續(xù)物理內(nèi)存。

下面演示一下內(nèi)存規(guī)整的簡(jiǎn)化工作原理，內(nèi)核會(huì)運(yùn)行兩個(gè)獨(dú)立的掃描動(dòng)作：第一個(gè)掃描從內(nèi)存域的底部開始，一邊掃描一邊將已分配的可移動(dòng)（MOVABLE）頁面記錄到一個(gè)列表中：

另外第二掃描是從內(nèi)存域的頂部開始，掃描可以作為頁面遷移目標(biāo)的空閑頁面位置，然后也記錄到一個(gè)列表里面：

等兩個(gè)掃描在域中間相遇，意味著掃描結(jié)束，然后將左邊掃描得到的已分配的頁面遷移到右邊空閑的頁面中，左邊就形成了一段連續(xù)的物理內(nèi)存，完成頁面規(guī)整。

碎片化整理的三種方式

static struct page *

__alloc_pages_direct_compact（gfp_t gfp_mask， unsigned int order，

unsigned int alloc_flags， const struct alloc_context *ac，

enum compact_priority prio， enum compact_result *compact_result）

{

struct page *page;

unsigned int noreclaim_flag;

if （！order）

return NULL;

noreclaim_flag = memalloc_noreclaim_save（）;

*compact_result = try_to_compact_pages（gfp_mask， order， alloc_flags， ac，

prio）;

memalloc_noreclaim_restore（noreclaim_flag）;

if （*compact_result 《= COMPACT_INACTIVE）

return NULL;

count_vm_event（COMPACTSTALL）;

page = get_page_from_freelist（gfp_mask， order， alloc_flags， ac）;

if （page） {

struct zone *zone = page_zone（page）;

zone-》compact_blockskip_flush = false;

compaction_defer_reset（zone， order， true）;

count_vm_event（COMPACTSUCCESS）;

return page;

}

count_vm_event（COMPACTFAIL）;

cond_resched（）;

return NULL;

}

在linux內(nèi)核里一共有3種方式可以碎片化整理，我們總結(jié)如下：

Linux slab分配器在Linux中，伙伴系統(tǒng)是以頁為單位分配內(nèi)存。但是現(xiàn)實(shí)中很多時(shí)候卻以字節(jié)為單位，不然申請(qǐng)10Bytes內(nèi)存還要給1頁的話就太浪費(fèi)了。slab分配器就是為小內(nèi)存分配而生的。slab分配器分配內(nèi)存以Byte為單位。但是slab分配器并沒有脫離伙伴系統(tǒng)，而是基于伙伴系統(tǒng)分配的大內(nèi)存進(jìn)一步細(xì)分成小內(nèi)存分配。

他們之間的關(guān)系可以用一張圖來描述：

流程分析

kmem_cache_alloc 主要四步：

先從 kmem_cache_cpu-》freelist中分配，如果freelist為null

接著去 kmem_cache_cpu-》partital鏈表中分配，如果此鏈表為null

接著去 kmem_cache_node-》partital鏈表分配，如果此鏈表為null

重新分配一個(gè)slab。

Linux 內(nèi)存管理之vmalloc根據(jù)前面的系列文章，我們知道了buddy system是基于頁框分配器，kmalloc是基于slab分配器，而且這些分配的地址都是物理內(nèi)存連續(xù)的。但是隨著碎片化的積累，連續(xù)物理內(nèi)存的分配就會(huì)變得困難，對(duì)于那些非DMA訪問，不一定非要連續(xù)物理內(nèi)存的話完全可以像malloc那樣，將不連續(xù)的物理內(nèi)存頁框映射到連續(xù)的虛擬地址空間中，這就是vmap的來源）（提供把離散的page映射到連續(xù)的虛擬地址空間），vmalloc的分配就是基于這個(gè)機(jī)制來實(shí)現(xiàn)的。

vmalloc最小分配一個(gè)page，并且分配到的頁面不保證是連續(xù)的，因?yàn)関malloc內(nèi)部調(diào)用alloc_page多次分配單個(gè)頁面。

vmalloc的區(qū)域就是在上圖中VMALLOC_START - VMALLOC_END之間，可通過/proc/vmallocinfo查看。

vmalloc流程

主要分以下三步：

從VMALLOC_START到VMALLOC_END查找空閑的虛擬地址空間（hole）

根據(jù)分配的size，調(diào)用alloc_page依次分配單個(gè)頁面。

把分配的單個(gè)頁面，映射到第一步中找到的連續(xù)的虛擬地址。把分配的單個(gè)頁面，映射到第一步中找到的連續(xù)的虛擬地址。

Linux進(jìn)程的內(nèi)存管理之缺頁異常當(dāng)進(jìn)程訪問這些還沒建立映射關(guān)系的虛擬地址時(shí)，處理器會(huì)自動(dòng)觸發(fā)缺頁異常。

ARM64把異常分為同步異常和異步異常，通常異步異常指的是中斷（可看《上帝視角看中斷》），同步異常指的是異常。關(guān)于ARM異常處理的文章可參考《ARMv8異常處理簡(jiǎn)介》。

當(dāng)處理器有異常發(fā)生時(shí)，處理器會(huì)先跳轉(zhuǎn)到ARM64的異常向量表中：

ENTRY（vectors）

kernel_ventry 1， sync_invalid // Synchronous EL1t

kernel_ventry 1， irq_invalid // IRQ EL1t

kernel_ventry 1， fiq_invalid // FIQ EL1t

kernel_ventry 1， error_invalid // Error EL1t

kernel_ventry 1， sync // Synchronous EL1h

kernel_ventry 1， irq // IRQ EL1h

kernel_ventry 1， fiq_invalid // FIQ EL1h

kernel_ventry 1， error_invalid // Error EL1h

kernel_ventry 0， sync // Synchronous 64-bit EL0

kernel_ventry 0， irq // IRQ 64-bit EL0

kernel_ventry 0， fiq_invalid // FIQ 64-bit EL0

kernel_ventry 0， error_invalid // Error 64-bit EL0

#ifdef CONFIG_COMPAT

kernel_ventry 0， sync_compat， 32 // Synchronous 32-bit EL0

kernel_ventry 0， irq_compat， 32 // IRQ 32-bit EL0

kernel_ventry 0， fiq_invalid_compat， 32 // FIQ 32-bit EL0

kernel_ventry 0， error_invalid_compat， 32 // Error 32-bit EL0

#else

kernel_ventry 0， sync_invalid， 32 // Synchronous 32-bit EL0

kernel_ventry 0， irq_invalid， 32 // IRQ 32-bit EL0

kernel_ventry 0， fiq_invalid， 32 // FIQ 32-bit EL0

kernel_ventry 0， error_invalid， 32 // Error 32-bit EL0

#endif

END（vectors）

以el1下的異常為例，當(dāng)跳轉(zhuǎn)到el1_sync函數(shù)時(shí)，讀取ESR的值以判斷異常類型。根據(jù)類型跳轉(zhuǎn)到不同的處理函數(shù)里，如果是data abort的話跳轉(zhuǎn)到el1_da函數(shù)里，instruction abort的話跳轉(zhuǎn)到el1_ia函數(shù)里：

el1_sync：

kernel_entry 1

mrs x1， esr_el1 // read the syndrome register

lsr x24， x1， #ESR_ELx_EC_SHIFT // exception class

cmp x24， #ESR_ELx_EC_DABT_CUR // data abort in EL1

b.eq el1_da

cmp x24， #ESR_ELx_EC_IABT_CUR // instruction abort in EL1

b.eq el1_ia

cmp x24， #ESR_ELx_EC_SYS64 // configurable trap

b.eq el1_undef

cmp x24， #ESR_ELx_EC_SP_ALIGN // stack alignment exception

b.eq el1_sp_pc

cmp x24， #ESR_ELx_EC_PC_ALIGN // pc alignment exception

b.eq el1_sp_pc

cmp x24， #ESR_ELx_EC_UNKNOWN // unknown exception in EL1

b.eq el1_undef

cmp x24， #ESR_ELx_EC_BREAKPT_CUR // debug exception in EL1

b.ge el1_dbg

b el1_inv

流程圖如下：

do_page_fault

static int __do_page_fault（struct mm_struct *mm， unsigned long addr，

unsigned int mm_flags， unsigned long vm_flags，

struct task_struct *tsk）

{

struct vm_area_struct *vma;

int fault;

vma = find_vma（mm， addr）;

fault = VM_FAULT_BADMAP; //沒有找到vma區(qū)域，說明addr還沒有在進(jìn)程的地址空間中

if （unlikely（！vma））

goto out;

if （unlikely（vma-》vm_start 》 addr））

goto check_stack;

/*

* Ok， we have a good vm_area for this memory access， so we can handle

* it.

*/

good_area://一個(gè)好的vma

/*

* Check that the permissions on the VMA allow for the fault which

* occurred.

*/

if （?。╲ma-》vm_flags & vm_flags）） {//權(quán)限檢查

fault = VM_FAULT_BADACCESS;

goto out;

}

//重新建立物理頁面到VMA的映射關(guān)系

return handle_mm_fault（vma， addr & PAGE_MASK， mm_flags）;

check_stack：

if （vma-》vm_flags & VM_GROWSDOWN && ！expand_stack（vma， addr））

goto good_area;

out：

return fault;

}

從__do_page_fault函數(shù)能看出來，當(dāng)觸發(fā)異常的虛擬地址屬于某個(gè)vma，并且擁有觸發(fā)頁錯(cuò)誤異常的權(quán)限時(shí)，會(huì)調(diào)用到handle_mm_fault函數(shù)來建立vma和物理地址的映射，而handle_mm_fault函數(shù)的主要邏輯是通過__handle_mm_fault來實(shí)現(xiàn)的。

__handle_mm_fault

static int __handle_mm_fault（struct vm_area_struct *vma， unsigned long address，

unsigned int flags）

{

。..。..

//查找頁全局目錄，獲取地址對(duì)應(yīng)的表項(xiàng)

pgd = pgd_offset（mm， address）;

//查找頁四級(jí)目錄表項(xiàng)，沒有則創(chuàng)建

p4d = p4d_alloc（mm， pgd， address）;

if （！p4d）

return VM_FAULT_OOM;

//查找頁上級(jí)目錄表項(xiàng)，沒有則創(chuàng)建

vmf.pud = pud_alloc（mm， p4d， address）;

。..。..

//查找頁中級(jí)目錄表項(xiàng)，沒有則創(chuàng)建

vmf.pmd = pmd_alloc（mm， vmf.pud， address）;

。..。..

//處理pte頁表

return handle_pte_fault（&vmf）;

}

do_anonymous_page

匿名頁缺頁異常，對(duì)于匿名映射，映射完成之后，只是獲得了一塊虛擬內(nèi)存，并沒有分配物理內(nèi)存，當(dāng)?shù)谝淮卧L問的時(shí)候：

如果是讀訪問，會(huì)將虛擬頁映射到０頁，以減少不必要的內(nèi)存分配

如果是寫訪問，用alloc_zeroed_user_highpage_movable分配新的物理頁，并用０填充，然后映射到虛擬頁上去

如果是先讀后寫訪問，則會(huì)發(fā)生兩次缺頁異常：第一次是匿名頁缺頁異常的讀的處理（虛擬頁到0頁的映射），第二次是寫時(shí)復(fù)制缺頁異常處理。

從上面的總結(jié)我們知道，第一次訪問匿名頁時(shí)有三種情況，其中第一種和第三種情況都會(huì)涉及到0頁。

do_fault

do_swap_page

上面已經(jīng)講過，pte對(duì)應(yīng)的內(nèi)容不為0（頁表項(xiàng)存在），但是pte所對(duì)應(yīng)的page不在內(nèi)存中時(shí)，表示此時(shí)pte的內(nèi)容所對(duì)應(yīng)的頁面在swap空間中，缺頁異常時(shí)會(huì)通過do_swap_page（）函數(shù)來分配頁面。

do_swap_page發(fā)生在swap in的時(shí)候，即查找磁盤上的slot，并將數(shù)據(jù)讀回。

換入的過程如下：

查找swap cache中是否存在所查找的頁面，如果存在，則根據(jù)swap cache引用的內(nèi)存頁，重新映射并更新頁表；如果不存在，則分配新的內(nèi)存頁，并添加到swap cache的引用中，更新內(nèi)存頁內(nèi)容完成后，更新頁表。

換入操作結(jié)束后，對(duì)應(yīng)swap area的頁引用減1，當(dāng)減少到0時(shí)，代表沒有任何進(jìn)程引用了該頁，可以進(jìn)行回收。

int do_swap_page（struct vm_fault *vmf）

{

。..。..

//根據(jù)pte找到swap entry， swap entry和pte有一個(gè)對(duì)應(yīng)關(guān)系

entry = pte_to_swp_entry（vmf-》orig_pte）;

。..。..

if （！page）

//根據(jù)entry從swap緩存中查找頁， 在swapcache里面尋找entry對(duì)應(yīng)的page

//Lookup a swap entry in the swap cache

page = lookup_swap_cache（entry， vma_readahead ？ vma ： NULL，

vmf-》address）;

//沒有找到頁

if （！page） {

if （vma_readahead）

page = do_swap_page_readahead（entry，

GFP_HIGHUSER_MOVABLE， vmf， &swap_ra）;

else

//如果swapcache里面找不到就在swap area里面找，分配新的內(nèi)存頁并從swap area中讀入

page = swapin_readahead（entry，

GFP_HIGHUSER_MOVABLE， vma， vmf-》address）;

。..。..

//獲取一個(gè)pte的entry，重新建立映射

vmf-》pte = pte_offset_map_lock（vma-》vm_mm， vmf-》pmd， vmf-》address，

&vmf-》ptl）;

。..。..

//anonpage數(shù)加1，匿名頁從swap空間交換出來，所以加1

//swap page個(gè)數(shù)減1，由page和VMA屬性創(chuàng)建一個(gè)新的pte

inc_mm_counter_fast（vma-》vm_mm， MM_ANONPAGES）;

dec_mm_counter_fast（vma-》vm_mm， MM_SWAPENTS）;

pte = mk_pte（page， vma-》vm_page_prot）;

。..。..

flush_icache_page（vma， page）;

if （pte_swp_soft_dirty（vmf-》orig_pte））

pte = pte_mksoft_dirty（pte）;

//將新生成的PTE entry添加到硬件頁表中

set_pte_at（vma-》vm_mm， vmf-》address， vmf-》pte， pte）;

vmf-》orig_pte = pte;

//根據(jù)page是否為swapcache

if （page == swapcache） {

//如果是，將swap緩存頁用作anon頁，添加反向映射rmap中

do_page_add_anon_rmap（page， vma， vmf-》address， exclusive）;

mem_cgroup_commit_charge（page， memcg， true， false）;

//并添加到active鏈表中

activate_page（page）;

//如果不是

} else { /* ksm created a completely new copy */

//使用新頁面并復(fù)制swap緩存頁，添加反向映射rmap中

page_add_new_anon_rmap（page， vma， vmf-》address， false）;

mem_cgroup_commit_charge（page， memcg， false， false）;

//并添加到lru鏈表中

lru_cache_add_active_or_unevictable（page， vma）;

}

//釋放swap entry

swap_free（entry）;

。..。..

if （vmf-》flags & FAULT_FLAG_WRITE） {

//有寫請(qǐng)求則寫時(shí)復(fù)制

ret |= do_wp_page（vmf）;

if （ret & VM_FAULT_ERROR）

ret &= VM_FAULT_ERROR;

goto out;

}

。..。..

return ret;

}

do_wp_page

走到這里說明頁面在內(nèi)存中，只是PTE只有讀權(quán)限，而又要寫內(nèi)存的時(shí)候就會(huì)觸發(fā)do_wp_page。

do_wp_page函數(shù)用于處理寫時(shí)復(fù)制（copy on write），其流程比較簡(jiǎn)單，主要是分配新的物理頁，拷貝原來頁的內(nèi)容到新頁，然后修改頁表項(xiàng)內(nèi)容指向新頁并修改為可寫（vma具備可寫屬性）。

static int do_wp_page（struct vm_fault *vmf）

__releases（vmf-》ptl）

{

struct vm_area_struct *vma = vmf-》vma;

//從頁表項(xiàng)中得到頁幀號(hào)，再得到頁描述符，發(fā)生異常時(shí)地址所在的page結(jié)構(gòu)

vmf-》page = vm_normal_page（vma， vmf-》address， vmf-》orig_pte）;

if （！vmf-》page） {

//沒有page結(jié)構(gòu)是使用頁幀號(hào)的特殊映射

/*

* VM_MIXEDMAP ！pfn_valid（） case， or VM_SOFTDIRTY clear on a

* VM_PFNMAP VMA.

*

* We should not cow pages in a shared writeable mapping.

* Just mark the pages writable and/or call ops-》pfn_mkwrite.

*/

if （（vma-》vm_flags & （VM_WRITE|VM_SHARED）） ==

（VM_WRITE|VM_SHARED））

//處理共享可寫映射

return wp_pfn_shared（vmf）;

pte_unmap_unlock（vmf-》pte， vmf-》ptl）;

//處理私有可寫映射

return wp_page_copy（vmf）;

}

/*

* Take out anonymous pages first， anonymous shared vmas are

* not dirty accountable.

*/

if （PageAnon（vmf-》page） && ！PageKsm（vmf-》page）） {

int total_map_swapcount;

if （！trylock_page（vmf-》page）） {

//添加原來頁的引用計(jì)數(shù)，方式被釋放

get_page（vmf-》page）;

//釋放頁表鎖

pte_unmap_unlock（vmf-》pte， vmf-》ptl）;

lock_page（vmf-》page）;

vmf-》pte = pte_offset_map_lock（vma-》vm_mm， vmf-》pmd，

vmf-》address， &vmf-》ptl）;

if （！pte_same（*vmf-》pte， vmf-》orig_pte）） {

unlock_page（vmf-》page）;

pte_unmap_unlock（vmf-》pte， vmf-》ptl）;

put_page（vmf-》page）;

return 0;

}

put_page（vmf-》page）;

}

//單身匿名頁面的處理

if （reuse_swap_page（vmf-》page， &total_map_swapcount）） {

if （total_map_swapcount == 1） {

/*

* The page is all ours. Move it to

* our anon_vma so the rmap code will

* not search our parent or siblings.

* Protected against the rmap code by

* the page lock.

*/

page_move_anon_rmap（vmf-》page， vma）;

}

unlock_page（vmf-》page）;

wp_page_reuse（vmf）;

return VM_FAULT_WRITE;

}

unlock_page（vmf-》page）;

} else if （unlikely（（vma-》vm_flags & （VM_WRITE|VM_SHARED）） ==

（VM_WRITE|VM_SHARED））） {

//共享可寫，不需要復(fù)制物理頁，設(shè)置頁表權(quán)限即可

return wp_page_shared（vmf）;

}

/*

* Ok， we need to copy. Oh， well.。

*/

get_page（vmf-》page）;

pte_unmap_unlock（vmf-》pte， vmf-》ptl）;

//私有可寫，復(fù)制物理頁，將虛擬頁映射到物理頁

return wp_page_copy（vmf）;

}

Linux 內(nèi)存管理之CMACMA是reserved的一塊內(nèi)存，用于分配連續(xù)的大塊內(nèi)存。當(dāng)設(shè)備驅(qū)動(dòng)不用時(shí)，內(nèi)存管理系統(tǒng)將該區(qū)域用于分配和管理可移動(dòng)類型頁面；當(dāng)設(shè)備驅(qū)動(dòng)使用時(shí)，此時(shí)已經(jīng)分配的頁面需要進(jìn)行遷移，又用于連續(xù)內(nèi)存分配；其用法與DMA子系統(tǒng)結(jié)合在一起充當(dāng)DMA的后端，具體可參考《沒有IOMMU的DMA操作》。

CMA區(qū)域 cma_areas 的創(chuàng)建

CMA區(qū)域的創(chuàng)建有兩種方法，一種是通過dts的reserved memory，另外一種是通過command line參數(shù)和內(nèi)核配置參數(shù)。

dts方式：

reserved-memory {

/* global autoconfigured region for contiguous allocations */

linux，cma {

compatible = “shared-dma-pool”;

reusable;

size = 《0 0x28000000》;

alloc-ranges = 《0 0xa0000000 0 0x40000000》;

linux，cma-default;

};

};

device tree中可以包含reserved-memory node，系統(tǒng)啟動(dòng)的時(shí)候會(huì)打開rmem_cma_setup

RESERVEDMEM_OF_DECLARE（cma， “shared-dma-pool”， rmem_cma_setup）;

command line方式：cma=nn［MG］@［start［MG］［-end［MG］］］

static int __init early_cma（char *p）

{

pr_debug（“%s（%s）

”， __func__， p）;

size_cmdline = memparse（p， &p）;

if （*p ！= ‘@’） {

/*

if base and limit are not assigned，

set limit to high memory bondary to use low memory.

*/

limit_cmdline = __pa（high_memory）;

return 0;

}

base_cmdline = memparse（p + 1， &p）;

if （*p ！= ‘-’） {

limit_cmdline = base_cmdline + size_cmdline;

return 0;

}

limit_cmdline = memparse（p + 1， &p）;

return 0;

}

early_param（“cma”， early_cma）;

系統(tǒng)在啟動(dòng)的過程中會(huì)把cmdline里的nn， start， end傳給函數(shù)dma_contiguous_reserve，流程如下：

setup_arch---》arm64_memblock_init---》dma_contiguous_reserve-》dma_contiguous_reserve_area-》cma_declare_contiguous

將CMA區(qū)域添加到Buddy System

為了避免這塊reserved的內(nèi)存在不用時(shí)候的浪費(fèi)，內(nèi)存管理模塊會(huì)將CMA區(qū)域添加到Buddy System中，用于可移動(dòng)頁面的分配和管理。CMA區(qū)域是通過cma_init_reserved_areas接口來添加到Buddy System中的。

static int __init cma_init_reserved_areas（void）

{

int i;

for （i = 0; i 《 cma_area_count; i++） {

int ret = cma_activate_area（&cma_areas［i］）;

if （ret）

return ret;

}

return 0;

}

core_initcall（cma_init_reserved_areas）;

其實(shí)現(xiàn)比較簡(jiǎn)單，主要分為兩步：

把該頁面設(shè)置為MIGRATE_CMA標(biāo)志

通過__free_pages將頁面添加到buddy system中

CMA分配

《沒有IOMMU的DMA操作》里講過，CMA是通過cma_alloc分配的。cma_alloc-》alloc_contig_range（。..， MIGRATE_CMA，。..），向剛才釋放給buddy system的MIGRATE_CMA類型頁面，重新“收集”過來。

用CMA的時(shí)候有一點(diǎn)需要注意：

也就是上圖中黃色部分的判斷。CMA內(nèi)存在分配過程是一個(gè)比較“重”的操作，可能涉及頁面遷移、頁面回收等操作，因此不適合用于atomic context。比如之前遇到過一個(gè)問題，當(dāng)內(nèi)存不足的情況下，向U盤寫數(shù)據(jù)的同時(shí)操作界面會(huì)出現(xiàn)卡頓的現(xiàn)象，這是因?yàn)镃MA在遷移的過程中需要等待當(dāng)前頁面中的數(shù)據(jù)回寫到U盤之后，才會(huì)進(jìn)一步的規(guī)整為連續(xù)內(nèi)存供gpu/display使用，從而出現(xiàn)卡頓的現(xiàn)象。

總結(jié)至此，從CPU開始訪問內(nèi)存，到物理頁的劃分，再到內(nèi)核頁框分配器的實(shí)現(xiàn)，以及slab分配器的實(shí)現(xiàn)，最后到CMA等連續(xù)內(nèi)存的使用，把Linux內(nèi)存管理的知識(shí)串了起來，算是形成了整個(gè)閉環(huán)。相信如果掌握了本篇內(nèi)容，肯定打開了Linux內(nèi)核的大門，有了這個(gè)基石，祝愿大家接下來的內(nèi)核學(xué)習(xí)越來越輕松。

原文標(biāo)題：萬字整理，肝翻Linux內(nèi)存管理所有知識(shí)點(diǎn)

文章出處：【微信公眾號(hào)：strongerHuang】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq