Linux內(nèi)核中的頁(yè)面分配機(jī)制

來(lái)源：嵌入式與Linux那些事公眾號(hào)

前言

Linux內(nèi)核中是如何分配出頁(yè)面的，如果我們站在CPU的角度去看這個(gè)問(wèn)題，CPU能分配出來(lái)的頁(yè)面是以物理頁(yè)面為單位的。也就是我們計(jì)算機(jī)中常講的分頁(yè)機(jī)制。本文就看下Linux內(nèi)核是如何管理，釋放和分配這些物理頁(yè)面的。

伙伴算法

伙伴系統(tǒng)的定義

大家都知道，Linux內(nèi)核的頁(yè)面分配器的基本算法是基于伙伴系統(tǒng)的，伙伴系統(tǒng)通俗的講就是以2^order 分配內(nèi)存的。這些內(nèi)存塊我們就稱為伙伴。

何為伙伴

兩個(gè)塊大小相同

兩個(gè)塊地址連續(xù)

兩個(gè)塊必須是同一個(gè)大塊分離出來(lái)的

下面我們舉個(gè)例子理解伙伴分配算法。假設(shè)我們要管理一大塊連續(xù)的內(nèi)存，有64個(gè)頁(yè)面，假設(shè)現(xiàn)在來(lái)了一個(gè)請(qǐng)求，要分配8個(gè)頁(yè)面?？偛荒馨?4個(gè)頁(yè)面全部給他使用吧。

截圖_20240623133911

首先把64個(gè)頁(yè)面一切為二，每部分32個(gè)頁(yè)面。

截圖_20240623134103

把32個(gè)頁(yè)面給請(qǐng)求者還是很大，這個(gè)時(shí)候會(huì)繼續(xù)拆分為16個(gè)。

截圖_20240623134157

最后會(huì)將16個(gè)頁(yè)面繼續(xù)拆分為8個(gè)，將其返回給請(qǐng)求者，這就完成了第一個(gè)請(qǐng)求。

截圖_20240623134617

這個(gè)時(shí)候，第二個(gè)請(qǐng)求者也來(lái)了，同樣的請(qǐng)求8個(gè)頁(yè)面，這個(gè)時(shí)候系統(tǒng)就會(huì)把另外8個(gè)頁(yè)面返回給請(qǐng)求者。

截圖_20240623134828

假設(shè)現(xiàn)在有第三個(gè)請(qǐng)求者過(guò)來(lái)了，它請(qǐng)求4個(gè)頁(yè)面。這個(gè)時(shí)候之前的8個(gè)頁(yè)面都被分配走了，這個(gè)時(shí)候就要從16個(gè)頁(yè)面的內(nèi)存塊切割了，切割后變?yōu)槊糠?個(gè)頁(yè)面。最后將8個(gè)頁(yè)面的內(nèi)存塊一分為二后返回給調(diào)用者。

截圖_20240623134934 截圖_20240623135122

假設(shè)前面分配的8個(gè)頁(yè)面都已經(jīng)用完了，這個(gè)時(shí)候可以把兩個(gè)8個(gè)頁(yè)面合并為16個(gè)頁(yè)面。

截圖_20240623135232

以上例子就是伙伴系統(tǒng)的簡(jiǎn)單的例子，大家可以通過(guò)這個(gè)例子通俗易懂的理解伙伴系統(tǒng)。

另外一個(gè)例子將要去說(shuō)明三個(gè)條件中的第三個(gè)條件：兩個(gè)塊必須要是從同一個(gè)大塊中分離出來(lái)的，這兩個(gè)塊才能稱之為伙伴，才能去合并為一個(gè)大塊。

我們以8個(gè)頁(yè)面的一個(gè)大塊為例子來(lái)說(shuō)明，如圖A0所示。將A0一分為二分，分別為 B0,B1。

B0：4頁(yè)

B1：4頁(yè)

再將B0，B1繼續(xù)切分：

C0：2頁(yè)

C1：2頁(yè)

C2：2頁(yè)

C3：2頁(yè)

最后可以將C0，C1，C2，C3切分為1個(gè)頁(yè)面大小的內(nèi)存塊。

我們從C列來(lái)看，C0，C1稱之為伙伴關(guān)系，C2，C3為伙伴關(guān)系。

同理，page0 和 page1也為伙伴關(guān)系，因?yàn)樗麄兌际菑腃0分割出來(lái)的。

截圖_20240623140813

假設(shè)，page0正在使用，page1 和 page2都是空閑的。那page1 和 page 2 可以合并成一個(gè)大的內(nèi)存塊嗎？

我們從上下級(jí)的關(guān)系來(lái)看，page 1，page 2 并不屬于一個(gè)大內(nèi)存塊切割而來(lái)的，不屬于伙伴關(guān)系。

如果我們把page 1 page 2，page4 page 5 合并了，看下結(jié)果會(huì)是什么樣子。

截圖_20240623141028

page0和page3 就會(huì)變成大內(nèi)存塊中孤零零的空洞了。page 0 和 page3 就無(wú)法再和其他塊合并了。這樣就形成了外碎片化。因此，內(nèi)核的伙伴系統(tǒng)是極力避免這種清空發(fā)生的。

伙伴系統(tǒng)在內(nèi)核中的實(shí)現(xiàn)

下面我們看下內(nèi)核中是怎么實(shí)現(xiàn)伙伴系統(tǒng)的。

截圖_20240623143810

上面這張圖是內(nèi)核中早期伙伴系統(tǒng)的實(shí)現(xiàn)

內(nèi)核中把內(nèi)存以2^order 為單位分為多個(gè)鏈表。order范圍為[0，MAX_ORDER-1]，MAX_ORDER一般為11。因此，Linux內(nèi)核中可以分配的最大的內(nèi)存塊為2^10= 4M，術(shù)語(yǔ)叫做page block。

內(nèi)核中有一個(gè)叫free_area的數(shù)據(jù)結(jié)構(gòu)，這個(gè)數(shù)據(jù)結(jié)構(gòu)為鏈表的數(shù)組。數(shù)組的大小為MAX_ORDER。數(shù)組的每個(gè)成員為一個(gè)鏈表。分別表示對(duì)應(yīng)order的空閑鏈表。以上就是早期的伙伴系統(tǒng)的頁(yè)面分配器的實(shí)現(xiàn)。

現(xiàn)在的伙伴系統(tǒng)中的頁(yè)面分配器的實(shí)現(xiàn)，為了解決內(nèi)存碎片化的問(wèn)題，在Linux內(nèi)核2.6.4中引入了遷移類型的 算法緩解內(nèi)存碎片化的問(wèn)題。

我們看這張圖，現(xiàn)在的頁(yè)面分配器中，每個(gè)free_area數(shù)組成員中都增加了一個(gè)遷移類型。也就是說(shuō)在每個(gè)order鏈表中多增加了一個(gè)鏈表。例如，order = 0 的鏈表中，新增了MOVABLE 鏈表，UNMOVABLE 鏈表，RECLAIMABLE鏈表。隨著內(nèi)核的發(fā)展，遷移類型越來(lái)越多，但常用的就那三個(gè)。

遷移類型

在Linux內(nèi)核2.6.4內(nèi)核中引入了反碎片化的概念，反碎片化就是根據(jù)遷移類型來(lái)實(shí)現(xiàn)的。我們知道遷移類型 是根據(jù)page block來(lái)劃分的。我們看下常用的遷移類型。

MIGRATE_UNMOVABLE：在內(nèi)存中有固定位置，不能隨意移動(dòng)，比如內(nèi)核分配的內(nèi)存。那為什么內(nèi)核分配的不能遷移呢？因此要遷移頁(yè)面，首先要把物理頁(yè)面的映射關(guān)系斷開(kāi)，在新的地方分配物理頁(yè)面，重新建立映射關(guān)系。在斷開(kāi)映射關(guān)系的途中，如果內(nèi)核繼續(xù)訪問(wèn)這個(gè)頁(yè)面，會(huì)導(dǎo)致oop錯(cuò)誤或者系統(tǒng)crash。因?yàn)閮?nèi)核是敏感區(qū)，內(nèi)核必須保證它使用的內(nèi)存是安全的。這一點(diǎn)和用戶進(jìn)程不一樣。如果是用戶進(jìn)程使用的內(nèi)存，我們將其斷開(kāi)后，用戶進(jìn)程再去訪問(wèn)，就會(huì)產(chǎn)生缺頁(yè)中斷，重新去尋找可用物理內(nèi)存然后建立映射關(guān)系。

MIGRATE_MOVABLE：可以隨意移動(dòng)，用戶態(tài)app分配的內(nèi)存，mlock，mmap分配的 匿名頁(yè)面。

MIGRATE_RECLAIMABLE：不能移動(dòng)可以刪除回收，比如文件映射。

內(nèi)存碎片化的產(chǎn)生

伙伴系統(tǒng)的遷移算法可以解決一些碎片化的問(wèn)題，但在內(nèi)存管理的方面，長(zhǎng)期存在一個(gè)問(wèn)題。從系統(tǒng)啟動(dòng)，長(zhǎng)期運(yùn)行之后，經(jīng)過(guò)大量的分配-釋放過(guò)程，還是會(huì)產(chǎn)生很多碎片，下面我們看下，這些碎片是怎么產(chǎn)生的。

我們以8個(gè)page的內(nèi)存塊為例，假設(shè)page3是被內(nèi)核使用的，比如alloc_page(GFP_KERNRL)，所以它屬于不可移動(dòng)的頁(yè)面，它就像一個(gè)樁一樣，插入在一大塊內(nèi)存的中間。

盡管其他的頁(yè)面都是空閑頁(yè)面，導(dǎo)致page0 ~ page 7 不能合并為一個(gè)大塊的內(nèi)存。

下面我們看下，遷移類型是怎么解決這類問(wèn)題的。我們知道，遷移算法是以page block為單位工作的，一個(gè)page block大小就是頁(yè)面分配器能分配的最大內(nèi)存塊。也就是說(shuō)，一個(gè)page block 中的頁(yè)面都是屬于一個(gè)遷移類型的。所以，就不會(huì)存在上面說(shuō)的多個(gè)page中夾著一個(gè)不可遷移的類型的情況。

頁(yè)面分配和釋放常用的函數(shù)

頁(yè)面分配函數(shù)

alloc_pages是內(nèi)核中常用的分配物理內(nèi)存頁(yè)面的函數(shù)， 用于分配2^order個(gè)連續(xù)的物理頁(yè)。

staticinlinestructpage*alloc_pages(gfp_tgfp_mask,unsignedintorder)

gfp_mask：gfp的全稱是get free page， 因此gfp_mask表示頁(yè)面分配的方法。gfp_mask的具體分類后面我們會(huì)詳細(xì)介紹。

order：頁(yè)面分配器使用伙伴系統(tǒng)按照順序請(qǐng)求頁(yè)面分配。所以只能以2的冪內(nèi)存分配。例如，請(qǐng)求order=3的頁(yè)面分配，最終會(huì)分配2 ^ 3 = 8頁(yè)。arm64當(dāng)前默認(rèn)MAX_ORDER為11， 即最多一次性分配2 ^（MAX_ORDER-1）個(gè)頁(yè)。

返回值：返回指向第一個(gè)page的struct page指針

__get_free_page() 是頁(yè)面分配器提供給調(diào)用者的最底層的內(nèi)存分配函數(shù)。它分配連續(xù)的物理內(nèi)存。__get_free_page() 函數(shù)本身是基于 buddy 實(shí)現(xiàn)的。在使用 buddy 實(shí)現(xiàn)的物理內(nèi)存管理中最小分配粒度是以頁(yè)為單位的。

unsignedlong__get_free_pages(gfp_tgfp_mask,unsignedintorder)

返回值：返回第一個(gè)page映射后的虛擬地址。

#definealloc_page(gfp_mask)alloc_pages(gfp_mask,0)

alloc_page 是宏定義，邏輯是調(diào)用 alloc_pages，傳遞給 order 參數(shù)的值為 0，表示需要分配的物理頁(yè)個(gè)數(shù)為 2 的 0 次方，即 1 個(gè)物理頁(yè)，需要用戶傳遞參數(shù) GFP flags。

釋放函數(shù)

voidfree_pages(unsignedlongaddr,unsignedintorder)

釋放2^order大小的頁(yè)塊,傳入?yún)?shù)是頁(yè)框首地址的虛擬地址

#define__free_page(page)__free_pages((page),0)

釋放一個(gè)頁(yè)，傳入?yún)?shù)是指向該頁(yè)對(duì)應(yīng)的虛擬地址

#definefree_page(addr)free_pages((addr),0)

釋放一個(gè)頁(yè)，傳入?yún)?shù)是頁(yè)框首地址的虛擬地址

gfp_mask標(biāo)志位

行為修飾符

zone 修飾符

水位修飾符

GFP_MASK和zone 以及遷移類型的關(guān)系

GFP_MASK除了表示分配行為之外，還可以表示從那些ZONE來(lái)分配內(nèi)存。還可以確定從那些遷移類型的page block 分配內(nèi)存。

我們以ARM為例，由于ARM架構(gòu)沒(méi)有ZONE_DMA的內(nèi)存，因此只能從ZONE_HIGHMEM或者ZONE_NOMAL中分配.

在內(nèi)核中有兩個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)表示從那些地方開(kāi)始分配內(nèi)存。

structzonelist{
structzoneref_zonerefs[MAX_ZONES_PER_ZONELIST+1];
};structzonelist

zonelist是一個(gè)zone的鏈表。一次分配的請(qǐng)求是在zonelist上執(zhí)行的。開(kāi)始在鏈表的第一個(gè)zone上分配，如果失敗，則根據(jù)優(yōu)先級(jí)降序訪問(wèn)其他zone。zlcache_ptr 指向zonelist的緩存。為了加速對(duì)zonelist的讀取操作 ,用_zonerefs 保存zonelist中每個(gè)zone的index。

structzoneref{
structzone*zone;/*Pointertoactualzone*/
intzone_idx;/*zone_idx(zoneref->zone)*/
};

頁(yè)面分配器是基于ZONE來(lái)設(shè)計(jì)的，因此頁(yè)面的分配有必要確定那些zone可以用于本次頁(yè)面分配。系統(tǒng)會(huì)優(yōu)先使用ZONE_HIGHMEM，然后才是ZONE_NORMAL 。

基于zone 的設(shè)計(jì)思想，在分配物理頁(yè)面的時(shí)候理應(yīng)以zone_hignmem優(yōu)先，因?yàn)閔ign_mem 在zone_ref中排在zone_normal的前面。而且，ZONE_NORMAL是線性映射的，線性映射的內(nèi)存會(huì)優(yōu)先給內(nèi)核態(tài)使用。

頁(yè)面分配的時(shí)候從那個(gè)遷移類型中分配出內(nèi)存呢?

函數(shù)static inline int gfp_migratetype(const gfp_t gfp_flags)可以根據(jù)掩碼類型轉(zhuǎn)換出遷移類型，從那個(gè)遷移類型分配頁(yè)面。比如GFP_KERNEL是從UNMOVABLE類型分配頁(yè)面的。

ZONE水位

頁(yè)面分配器是基于ZONE的機(jī)制來(lái)實(shí)現(xiàn)的，怎么去管理這些空閑頁(yè)面呢？Linux內(nèi)核中定義了三個(gè)警戒線，WATERMARK_MIN，WATERMARK_LOW，WATERMARK_HIGH。大家可以看下面這張圖，就是分配水位和警戒線的關(guān)系。

最低水線(WMARK_MIN)：當(dāng)剩余內(nèi)存在min以下時(shí)，則系統(tǒng)內(nèi)存壓力非常大。一般情況下min以下的內(nèi)存是不會(huì)被分配的，min以下的內(nèi)存默認(rèn)是保留給特殊用途使用，屬于保留的頁(yè)框，用于原子的內(nèi)存請(qǐng)求操作。比如：當(dāng)我們?cè)谥袛嗌舷挛纳暾?qǐng)或者在不允許睡眠的地方申請(qǐng)內(nèi)存時(shí)，可以采用標(biāo)志GFP_ATOMIC來(lái)分配內(nèi)存，此時(shí)才會(huì)允許我們使用保留在min水位以下的內(nèi)存。

低水線(WMARK_LOW)：空閑頁(yè)數(shù)小數(shù)低水線，說(shuō)明該內(nèi)存區(qū)域的內(nèi)存輕微不足。默認(rèn)情況下，該值為WMARK_MIN的125%

高水線(WMARK_HIGH)：如果內(nèi)存區(qū)域的空閑頁(yè)數(shù)大于高水線，說(shuō)明該內(nèi)存區(qū)域水線充足。默認(rèn)情況下，該值為WMARK_MAX的150%

在進(jìn)行內(nèi)存分配的時(shí)候，如果分配器（比如buddy allocator）發(fā)現(xiàn)當(dāng)前空余內(nèi)存的值低于”low”但高于”min”，說(shuō)明現(xiàn)在內(nèi)存面臨一定的壓力，那么在此次內(nèi)存分配完成后，kswapd將被喚醒，以執(zhí)行內(nèi)存回收操作。在這種情況下，內(nèi)存分配雖然會(huì)觸發(fā)內(nèi)存回收，但不存在被內(nèi)存回收所阻塞的問(wèn)題，兩者的執(zhí)行關(guān)系是異步的

對(duì)于kswapd來(lái)說(shuō)，要回收多少內(nèi)存才算完成任務(wù)呢？只要把空余內(nèi)存的大小恢復(fù)到”high”對(duì)應(yīng)的watermark值就可以了，當(dāng)然，這取決于當(dāng)前空余內(nèi)存和”high”值之間的差距，差距越大，需要回收的內(nèi)存也就越多?！眑ow”可以被認(rèn)為是一個(gè)警戒水位線，而”high”則是一個(gè)安全的水位線。

如果內(nèi)存分配器發(fā)現(xiàn)空余內(nèi)存的值低于了”min”，說(shuō)明現(xiàn)在內(nèi)存嚴(yán)重不足。這里要分兩種情況來(lái)討論，一種是默認(rèn)的操作，此時(shí)分配器將同步等待內(nèi)存回收完成，再進(jìn)行內(nèi)存分配，也就是direct reclaim。還有一種特殊情況，如果內(nèi)存分配的請(qǐng)求是帶了PF_MEMALLOC標(biāo)志位的，并且現(xiàn)在空余內(nèi)存的大小可以滿足本次內(nèi)存分配的需求，那么也將是先分配，再回收。

per-cpu頁(yè)面分配

內(nèi)核會(huì)經(jīng)常請(qǐng)求和釋放單個(gè)頁(yè)框，比如網(wǎng)卡驅(qū)動(dòng)。

頁(yè)面分配器分配和釋放頁(yè)面的時(shí)候需要申請(qǐng)一把鎖：zone->lock

為了提高單個(gè)頁(yè)框的申請(qǐng)和釋放效率，內(nèi)核建立了per-cpu頁(yè)面告訴緩存池

其中存放了若干預(yù)先分配好的頁(yè)框

當(dāng)請(qǐng)求單個(gè)頁(yè)框時(shí)，直接從本地cpu的頁(yè)框告訴緩存池中獲取頁(yè)框

體現(xiàn)了預(yù)先建立緩存池的優(yōu)勢(shì)，而且是每個(gè)CPU有一個(gè)獨(dú)立的緩存池

不必申請(qǐng)鎖

不必進(jìn)行復(fù)雜的頁(yè)框分配操作

per-cpu數(shù)據(jù)結(jié)構(gòu)

由于頁(yè)框頻繁的分配和釋放，內(nèi)核在每個(gè)zone中放置了一些事先保留的頁(yè)框。這些頁(yè)框只能由來(lái)自本地CPU的請(qǐng)求使用。zone中有一個(gè)成員pageset字段指向per-cpu的高速緩存，高速緩存由struct per_cpu_pages數(shù)據(jù)結(jié)構(gòu)來(lái)描述。

structper_cpu_pages{
intcount;/*numberofpagesinthelist*/
inthigh;/*highwatermark,emptyingneeded*/
intbatch;/*chunksizeforbuddyadd/remove*/

/*Listsofpages,onepermigratetypestoredonthepcp-lists*/
structlist_headlists[MIGRATE_PCPTYPES];
};

count：表示高速緩存中的頁(yè)框數(shù)量。

high ：緩存中頁(yè)框數(shù)量的最大值

batch ：buddy allocator增加或刪除的頁(yè)框數(shù)

lists：頁(yè)框鏈表。