【內(nèi)存管理】頁面分配機(jī)制

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

伙伴算法

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

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

何為伙伴

兩個(gè)塊大小相同

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

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

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

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

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

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

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

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

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

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

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

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

B0：4頁

B1：4頁

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

C0：2頁

C1：2頁

C2：2頁

C3：2頁

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

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

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

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

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

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

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

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

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

上面這張圖是內(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ù)語叫做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è)鏈表。分別表示對應(yīng)order的空閑鏈表。以上就是早期的伙伴系統(tǒng)的頁面分配器的實(shí)現(xiàn)。

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

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

遷移類型

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

MIGRATE_UNMOVABLE：在內(nèi)存中有固定位置，不能隨意移動(dòng)，比如內(nèi)核分配的內(nèi)存。那為什么內(nèi)核分配的不能遷移呢？因此要遷移頁面，首先要把物理頁面的映射關(guān)系斷開，在新的地方分配物理頁面，重新建立映射關(guān)系。在斷開映射關(guān)系的途中，如果內(nèi)核繼續(xù)訪問這個(gè)頁面，會(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)存，我們將其斷開后，用戶進(jìn)程再去訪問，就會(huì)產(chǎn)生缺頁中斷，重新去尋找可用物理內(nèi)存然后建立映射關(guān)系。

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

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

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

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

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

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

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

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

頁面分配函數(shù)

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

static inline struct page *alloc_pages(gfp_t gfp_mask, unsigned int order)

gfp_mask：gfp的全稱是get free page ， 因此gfp_mask表示頁面分配的方法。

gfp_mask

• 的具體分類后面我們會(huì)詳細(xì)介紹。order：頁面分配器使用伙伴系統(tǒng)按照順序請求頁面分配。所以只能以2的冪內(nèi)存分配。例如，請求order=3的頁面分配，最終會(huì)分配2 ^ 3 = 8頁。arm64當(dāng)前默認(rèn)

MAX_ORDER為11， 即最多一次性分配2 ^（MAX_ORDER-1）個(gè)頁。返回值：返回指向第一個(gè)page的struct page

指針

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

unsigned?long?__get_free_pages(gfp_t?gfp_mask,?unsigned?int?order)

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

#define?alloc_page(gfp_mask)?alloc_pages(gfp_mask,?0)

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

釋放函數(shù)

void?free_pages(unsigned?long?addr,?unsigned?int?order)

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

#define?__free_page(page)?__free_pages((page),?0)

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

#define?free_page(addr)?free_pages((addr),?0)

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

gfp_mask標(biāo)志位

行為修飾符

zone 修飾符

水位修飾符

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

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

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

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

struct?zonelist?{
?struct?zoneref?_zonerefs[MAX_ZONES_PER_ZONELIST?+?1];
};struct?zonelist

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

struct?zoneref?{
?struct?zone?*zone;?/*?Pointer?to?actual?zone?*/
?int?zone_idx;??/*?zone_idx(zoneref->zone)?*/
};

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

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

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

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

ZONE水位

頁面分配器是基于ZONE的機(jī)制來實(shí)現(xiàn)的，怎么去管理這些空閑頁面呢？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)是保留給特殊用途使用，屬于保留的頁框，用于原子的內(nèi)存請求操作。比如：當(dāng)我們在中斷上下文申請或者在不允許睡眠的地方申請內(nèi)存時(shí)，可以采用標(biāo)志

GFP_ATOMIC來分配內(nèi)存，此時(shí)才會(huì)允許我們使用保留在min水位以下的內(nèi)存。低水線(WMARK_LOW)：空閑頁數(shù)小數(shù)低水線，說明該內(nèi)存區(qū)域的內(nèi)存輕微不足。默認(rèn)情況下，該值為

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

WMARK_MAX的150%

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

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

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

per-cpu頁面分配

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

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

• • 為了提高單個(gè)頁框的申請和釋放效率，內(nèi)核建立了per-cpu頁面告訴緩存池其中存放了若干預(yù)先分配好的頁框

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

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

• 不必申請鎖不必進(jìn)行復(fù)雜的頁框分配操作

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

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

struct?per_cpu_pages?{
?int?count;??/*?number?of?pages?in?the?list?*/
?int?high;??/*?high?watermark,?emptying?needed?*/
?int?batch;??/*?chunk?size?for?buddy?add/remove?*/

?/*?Lists?of?pages,?one?per?migrate?type?stored?on?the?pcp-lists?*/
?struct?list_head?lists[MIGRATE_PCPTYPES];
};

count：表示高速緩存中的頁框數(shù)量。high ：緩存中頁框數(shù)量的最大值batch ：buddy allocator增加或刪除的頁框數(shù)lists：頁框鏈表。

本文參考

https://www.cnblogs.com/dennis-wong/p/14729453.html

https://blog.csdn.net/yhb1047818384/article/details/112298996

https://blog.csdn.net/u010923083/article/details/115916169

https://blog.csdn.net/farmwang/article/details/66975128