一步一步剖析Linux伙伴系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

Linux 內(nèi)存管理系列文章：

• 3.5 萬字 + 60 張圖 ｜一步一圖帶你深入理解 Linux 虛擬內(nèi)存管理

• 幾萬字 + 60 張圖 ｜一步一圖帶你深入理解 Linux 物理內(nèi)存管理

在上篇文章 《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 中，筆者為大家詳細(xì)介紹了 Linux 內(nèi)存分配在內(nèi)核中的整個(gè)鏈路實(shí)現(xiàn)：

image.png

但是當(dāng)內(nèi)核執(zhí)行到 get_page_from_freelist 函數(shù)，準(zhǔn)備進(jìn)入伙伴系統(tǒng)執(zhí)行具體內(nèi)存分配動(dòng)作的相關(guān)邏輯，筆者考慮到文章篇幅的原因，并沒有過多的著墨，算是留下了一個(gè)小尾巴。

那么本文筆者就為大家完整地介紹一下伙伴系統(tǒng)這部分的內(nèi)容，我們將基于內(nèi)核 5.4 版本的源碼來詳細(xì)的討論一下伙伴系統(tǒng)在內(nèi)核中的設(shè)計(jì)與實(shí)現(xiàn)。

文章概要.png

1. 伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)

image.png

如上圖所示，內(nèi)核會(huì)為 NUMA 節(jié)點(diǎn)中的每個(gè)物理內(nèi)存區(qū)域 zone 分配一個(gè)伙伴系統(tǒng)用于管理該物理內(nèi)存區(qū)域 zone 里的空閑內(nèi)存頁。

而伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)就封裝在 struct zone 里，關(guān)于 struct zone 結(jié)構(gòu)體的詳細(xì)介紹感興趣的朋友可以回看下筆者之前的文章 《深入理解 Linux 物理內(nèi)存管理》中第五小節(jié) “ 5. 內(nèi)核如何管理 NUMA 節(jié)點(diǎn)中的物理內(nèi)存區(qū)域 ” 的內(nèi)容。

在本小節(jié)中，我們聚焦于伙伴系統(tǒng)相關(guān)的數(shù)據(jù)結(jié)構(gòu)介紹~~

structzone{
//被伙伴系統(tǒng)所管理的物理內(nèi)存頁個(gè)數(shù)
atomic_long_tmanaged_pages;
//伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)
structfree_areafree_area[MAX_ORDER];
}

struct zone 結(jié)構(gòu)中的 managed_pages 用于表示該內(nèi)存區(qū)域內(nèi)被伙伴系統(tǒng)所管理的物理內(nèi)存頁數(shù)量。

而 managed_pages 的計(jì)算方式之前也介紹過了，它是通過 present_pages （不包含內(nèi)存空洞）減去內(nèi)核為應(yīng)對(duì)緊急情況而預(yù)留的物理內(nèi)存頁 reserved_pages 得到的。

從這里可以看出伙伴系統(tǒng)所管理的空閑物理內(nèi)存頁并不包含緊急預(yù)留內(nèi)存

伙伴系統(tǒng)的真正核心數(shù)據(jù)結(jié)構(gòu)就是這個(gè) struct free_area 類型的數(shù)組 free_area[MAX_ORDER] 。MAX_ORDER 就是筆者在《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 “ 的第一小節(jié) "1. 內(nèi)核物理內(nèi)存分配接口 ” 中介紹的分配階 order 的最大值減 1。

伙伴系統(tǒng)所分配的物理內(nèi)存頁全部都是物理上連續(xù)的，并且只能分配 2 的整數(shù)冪個(gè)頁，這里的整數(shù)冪在內(nèi)核中稱之為分配階 order。

在我們調(diào)用物理內(nèi)存分配接口時(shí)，均需要指定這個(gè)分配階 order，意思是從伙伴系統(tǒng)申請(qǐng)多少個(gè)物理內(nèi)存頁，假設(shè)我們指定分配階為 order，那么就會(huì)從伙伴系統(tǒng)中申請(qǐng) 2 的 order 次冪個(gè)物理內(nèi)存頁。

伙伴系統(tǒng)會(huì)將物理內(nèi)存區(qū)域中的空閑內(nèi)存根據(jù)分配階 order 劃分出不同尺寸的內(nèi)存塊，并將這些不同尺寸的內(nèi)存塊分別用一個(gè)雙向鏈表組織起來。

比如：分配階 order 為 0 時(shí)，對(duì)應(yīng)的內(nèi)存塊就是一個(gè) page。分配階 order 為 1 時(shí)，對(duì)應(yīng)的內(nèi)存塊就是 2 個(gè) pages。依次類推，當(dāng)分配階 order 為 n 時(shí)，對(duì)應(yīng)的內(nèi)存塊就是 2 的 order 次冪個(gè) pages。

MAX_ORDER - 1 就是內(nèi)核中規(guī)定的分配階 order 的最大值，定義在 /include/linux/mmzone.h 文件中，最大分配階 MAX_ORDER - 1 = 10，也就是說一次，最多只能從伙伴系統(tǒng)中申請(qǐng) 1024 個(gè)內(nèi)存頁，對(duì)應(yīng) 4M 大小的連續(xù)物理內(nèi)存。

/*Freememorymanagement-zonedbuddyallocator.*/
#ifndefCONFIG_FORCE_MAX_ZONEORDER
#defineMAX_ORDER11

image.png

數(shù)組 free_area[MAX_ORDER] 中的索引表示的就是分配階 order，用于指定對(duì)應(yīng)雙向鏈表組織管理的內(nèi)存塊包含多少個(gè) page。

我們可以通過 cat /proc/buddyinfo 命令來查看 NUMA 節(jié)點(diǎn)中不同內(nèi)存區(qū)域 zone 的伙伴系統(tǒng)當(dāng)前狀態(tài)：

image.png

上圖展示了不同內(nèi)存區(qū)域伙伴系統(tǒng)的 free_area[MAX_ORDER] 數(shù)組中，不同分配階對(duì)應(yīng)的內(nèi)存塊個(gè)數(shù)，從左到右依次是 0 階，1 階， ........ ，10 階對(duì)應(yīng)的雙向鏈表中包含的內(nèi)存塊個(gè)數(shù)。

以上內(nèi)容展示的只是伙伴系統(tǒng)的一個(gè)基本骨架，有了這個(gè)基本骨架之后，下面筆者繼續(xù)按照一步一圖的方式，來為大家揭開伙伴系統(tǒng)的完整樣貌。

我們先從 free_area[MAX_ORDER] 數(shù)組的類型 struct free_area 結(jié)構(gòu)開始談起~~~

structfree_area{
structlist_headfree_list[MIGRATE_TYPES];
unsignedlongnr_free;
};

structlist_head{
//雙向鏈表
structlist_head*next,*prev;
};

根據(jù)前邊的內(nèi)容我們知道 free_area[MAX_ORDER] 數(shù)組描述的只是伙伴系統(tǒng)的一個(gè)基本骨架，數(shù)組中的每一個(gè)元素統(tǒng)一組織存儲(chǔ)了相同尺寸的內(nèi)存塊。內(nèi)存塊的尺寸分為 0 階，1 階 ，........ ，10 階，一共 MAX_ORDER 個(gè)尺寸。

struct free_area 主要描述的就是相同尺寸的內(nèi)存塊在伙伴系統(tǒng)中的組織結(jié)構(gòu)， nr_free 則表示的是該尺寸的內(nèi)存塊在當(dāng)前伙伴系統(tǒng)中的個(gè)數(shù)，這個(gè)值會(huì)隨著內(nèi)存的分配而減少，隨著內(nèi)存的回收而增加。

注意：nr_free 表示的可不是空閑內(nèi)存頁 page 的個(gè)數(shù)，而是空閑內(nèi)存塊的個(gè)數(shù)，對(duì)于 0 階的內(nèi)存塊來說 nr_free 確實(shí)表示的是單個(gè)內(nèi)存頁 page 的個(gè)數(shù)，因?yàn)?0 階內(nèi)存塊是由一個(gè) page 組成的，但是對(duì)于 1 階內(nèi)存塊來說，nr_free 則表示的是 2 個(gè) page 集合的個(gè)數(shù)，以此類推對(duì)于 n 階內(nèi)存塊來說，nr_free 表示的是 2 的 n 次方 page 集合的個(gè)數(shù)

這些相同尺寸的內(nèi)存塊在 struct free_area 結(jié)構(gòu)中是通過 struct list_head 結(jié)構(gòu)類型的雙向鏈表統(tǒng)一組織起來的。

按理來說，內(nèi)核只需要將這些相同尺寸的內(nèi)存塊在 struct free_area 中用一個(gè)雙向鏈表串聯(lián)起來就行了。

但是我們從源碼中卻看到內(nèi)核是用多個(gè)雙向鏈表來組織這些相同尺寸的內(nèi)存塊的，這些雙向鏈表組成一個(gè)數(shù)組 free_list[MIGRATE_TYPES]，該數(shù)組中雙向鏈表的個(gè)數(shù)為 MIGRATE_TYPES。

我們從 MIGRATE_TYPES 的字面意思上可以看出，內(nèi)核會(huì)根據(jù)物理內(nèi)存頁的遷移類型將這些相同尺寸的內(nèi)存塊近一步通過不同的雙向鏈表重新組織起來。

free_area 是將相同尺寸的內(nèi)存塊組織起來，free_list 是在 free_area 的基礎(chǔ)上近一步根據(jù)頁面的遷移類型將這些相同尺寸的內(nèi)存塊劃分到不同的雙向鏈表中管理

而物理內(nèi)存頁面的遷移類型 MIGRATE_TYPES 定義在 /include/linux/mmzone.h 文件中：

enummigratetype{
MIGRATE_UNMOVABLE,//不可移動(dòng)
MIGRATE_MOVABLE,//可移動(dòng)
MIGRATE_RECLAIMABLE,//可回收
MIGRATE_PCPTYPES,//屬于CPU高速緩存中的類型，PCP是per_cpu_pageset的縮寫
MIGRATE_HIGHATOMIC=MIGRATE_PCPTYPES,//緊急內(nèi)存
#ifdefCONFIG_CMA
MIGRATE_CMA,//預(yù)留的連續(xù)內(nèi)存CMA
#endif
#ifdefCONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE,/*can'tallocatefromhere*/
#endif
MIGRATE_TYPES//不代表任何區(qū)域，只是單純表示一共有多少個(gè)遷移類型
};

MIGRATE_UNMOVABLE 表示不可移動(dòng)的頁面類型，這種類型的物理內(nèi)存頁面是固定的不能隨意移動(dòng)，內(nèi)核所需要的核心內(nèi)存大多數(shù)是從 MIGRATE_UNMOVABLE 類型的頁面中進(jìn)行分配，這部分內(nèi)存一般位于內(nèi)核虛擬地址空間中的直接映射區(qū)。

image.png

在內(nèi)核虛擬地址空間的直接映射區(qū)中，虛擬內(nèi)存地址與物理內(nèi)存地址都是直接映射的，虛擬內(nèi)存地址通過減去一個(gè)固定的偏移量就可以直接得到物理內(nèi)存地址，由于這種直接映射的關(guān)系，所以這部分內(nèi)存是不能移動(dòng)的，因?yàn)橐坏┮苿?dòng)虛擬內(nèi)存地址就會(huì)發(fā)生變化，這樣一來虛擬內(nèi)存地址減去固定的偏移得到的物理內(nèi)存地址就不一樣了。

MIGRATE_MOVABLE 表示可以移動(dòng)的內(nèi)存頁類型，這種頁面類型一般用于在進(jìn)程用戶空間中分配，因?yàn)樵谟脩艨臻g中虛擬內(nèi)存與物理內(nèi)存都是通過頁表來動(dòng)態(tài)映射的，物理頁移動(dòng)之后，只需要改變頁表中的映射關(guān)系即可，而虛擬內(nèi)存地址并不需要改變。一切對(duì)進(jìn)程來說都是透明的。

MIGRATE_RECLAIMABLE 表示不能移動(dòng)，但是可以直接回收的頁面類型，比如前面提到的文件緩存頁，它們就可以直接被回收掉，當(dāng)再次需要的時(shí)候可以從磁盤中繼續(xù)讀取生成?；蛘咭恍┥芷诒容^短的內(nèi)存頁，比如 DMA 緩存區(qū)中的內(nèi)存頁也是可以被直接回收掉。

MIGRATE_PCPTYPES 則表示 CPU 高速緩存中的頁面類型，PCP 是 per_cpu_pageset 的縮寫，每個(gè) CPU 對(duì)應(yīng)一個(gè) per_cpu_pageset 結(jié)構(gòu)，里面包含了高速緩存中的冷頁和熱頁。這部分的詳細(xì)內(nèi)容感興趣的可以回看下筆者的這篇文章 《深入理解 Linux 物理內(nèi)存管理》中的 “ 5.7 物理內(nèi)存區(qū)域中的冷熱頁 ” 小節(jié)。

MIGRATE_CMA 表示屬于 CMA 區(qū)域中的內(nèi)存頁類型，CMA 的全稱是 contiguous memory allocator，顧名思義它是一個(gè)分配連續(xù)物理內(nèi)存頁面的分配器用于分配連續(xù)的物理內(nèi)存。

大家可能好奇了，我們這節(jié)講到的伙伴系統(tǒng)分配的不也是連續(xù)的物理內(nèi)存嗎？為什么又會(huì)多出個(gè) CMA 呢？

原因還是前邊我們多次提到的內(nèi)存碎片對(duì)內(nèi)存分配的巨大影響，隨著系統(tǒng)的長(zhǎng)時(shí)間運(yùn)行，不可避免的會(huì)產(chǎn)生內(nèi)存碎片，這些內(nèi)存碎片會(huì)導(dǎo)致在內(nèi)存充足的情況下卻依然找不到一片足夠大的連續(xù)物理內(nèi)存，伙伴系統(tǒng)在這種情況下就會(huì)失敗，而連續(xù)的物理內(nèi)存分配對(duì)于內(nèi)核來說又是剛需，比如：一些 DMA 設(shè)備只能訪問連續(xù)的物理內(nèi)存，內(nèi)核對(duì)于大頁的支持也需要連續(xù)的物理內(nèi)存。

所以為了解決這個(gè)問題，內(nèi)核會(huì)在系統(tǒng)剛剛啟動(dòng)的時(shí)候，這時(shí)內(nèi)存還很充足，先預(yù)留一部分連續(xù)的物理內(nèi)存，這部分物理內(nèi)存就是 CMA 區(qū)域，這部分內(nèi)存可以被進(jìn)程正常的使用，當(dāng)有連續(xù)內(nèi)存分配需求時(shí)，內(nèi)核會(huì)通過頁面回收或者遷移的方式將這部分內(nèi)存騰出來給 CMA 分配。

CMA 的初始化是在伙伴系統(tǒng)初始化之前就已經(jīng)完成的

MIGRATE_ISOLATE 則是一個(gè)虛擬區(qū)域，用于跨越 NUMA 節(jié)點(diǎn)移動(dòng)物理內(nèi)存頁，內(nèi)核可以將物理內(nèi)存頁移動(dòng)到使用該頁最頻繁的 CPU 所在的 NUMA 節(jié)點(diǎn)中。

在介紹完這些物理頁面的遷移類型 MIGRATE_TYPES 之后，大家可能不禁有疑問，內(nèi)核為啥會(huì)設(shè)定這么多的頁面遷移類型呢 ？

答案還是為了解決前面我們反復(fù)提到的內(nèi)存碎片問題，當(dāng)系統(tǒng)長(zhǎng)時(shí)間運(yùn)行之后，隨著不同尺寸內(nèi)存的分配和釋放，就會(huì)引起內(nèi)存碎片，這些碎片會(huì)導(dǎo)致內(nèi)核在明明還有足夠內(nèi)存的前提下，仍然無法找到一塊足夠大的連續(xù)內(nèi)存分配。如下圖所示：

image.png

上圖中顯示的這 7 個(gè)空閑的內(nèi)存頁以碎片的形式存在于內(nèi)存中，這就導(dǎo)致明明還有 7 個(gè)空閑的內(nèi)存頁，但是最大的連續(xù)內(nèi)存區(qū)域只有 1 個(gè)內(nèi)存頁，當(dāng)內(nèi)核想要申請(qǐng) 2 個(gè)連續(xù)的內(nèi)存頁時(shí)就會(huì)導(dǎo)致失敗。

很長(zhǎng)時(shí)間以來，物理內(nèi)存碎片一直是 Linux 操作系統(tǒng)的弱點(diǎn)，所以內(nèi)核在 2.6.24 版本中引入了以下方式來避免內(nèi)存碎片。

如果這些內(nèi)存頁是可以遷移的，內(nèi)核就會(huì)將空閑的內(nèi)存頁遷移至一起，已分配的內(nèi)存頁遷移至一起，形成了一整塊足夠大的連續(xù)內(nèi)存區(qū)域。

image.png

如果這些內(nèi)存頁是可以回收的，內(nèi)核也可以通過回收頁面的方式，整理出一塊足夠大的空閑連續(xù)內(nèi)存區(qū)域。

在我們清楚了以上介紹的基礎(chǔ)知識(shí)之后，再回過頭來看伙伴系統(tǒng)的這些核心數(shù)據(jù)結(jié)構(gòu)，是不是就變得容易理解了~~

structzone{
//被伙伴系統(tǒng)所管理的物理頁數(shù)
atomic_long_tmanaged_pages;
//伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)
structfree_areafree_area[MAX_ORDER];
}

structfree_area{
structlist_headfree_list[MIGRATE_TYPES];
unsignedlongnr_free;
};

首先伙伴系統(tǒng)會(huì)將物理內(nèi)存區(qū)域 zone 中的空閑內(nèi)存頁按照分配階 order 將相同尺寸的內(nèi)存塊組織在 free_area[MAX_ORDER] 數(shù)組中：

image.png

隨后在 struct free_area 結(jié)構(gòu)中伙伴系統(tǒng)近一步根據(jù)這些相同尺寸內(nèi)存塊的頁面遷移類型 MIGRATE_TYPES，將相同遷移類型的物理頁面組織在 free_list[MIGRATE_TYPES] 數(shù)組中，最終形成了完整的伙伴系統(tǒng)結(jié)構(gòu)：

image.png

我們可以通過 cat /proc/pagetypeinfo 命令可以查看當(dāng)前各個(gè)內(nèi)存區(qū)域中的伙伴系統(tǒng)中不同頁面遷移類型以及不同 order 尺寸的內(nèi)存塊個(gè)數(shù)。

image.png

page block order 表示系統(tǒng)中支持的巨型頁對(duì)應(yīng)的分配階，pages per block 表示巨型頁中包含的 pages 個(gè)數(shù)。

好了，現(xiàn)在我們已經(jīng)清楚了伙伴系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)全貌，接下來筆者會(huì)在這個(gè)基礎(chǔ)上繼續(xù)為大家介紹伙伴系統(tǒng)的核心工作原理~~

2. 到底什么是伙伴

我們前面一直在談伙伴系統(tǒng)，那么伙伴這個(gè)概念到底在內(nèi)核中是什么意思呢？其實(shí)下面這張伙伴系統(tǒng)的結(jié)構(gòu)圖已經(jīng)把伙伴的概念很清晰的表達(dá)出來了。

image.png

伙伴在我們?nèi)粘Ｉ钪泻x就是形影不離的好朋友，在內(nèi)核中也是如此，內(nèi)核中的伙伴指的是大小相同并且在物理內(nèi)存上是連續(xù)的兩個(gè)或者多個(gè) page。

比如在上圖中，free_area[1] 中組織的是分配階 order = 1 的內(nèi)存塊，內(nèi)存塊中包含了兩個(gè)連續(xù)的空閑 page。這兩個(gè)空閑 page 就是伙伴。

free_area[10] 中組織的是分配階 order = 10 的內(nèi)存塊，內(nèi)存塊中包含了 1024 個(gè)連續(xù)的空閑 page。這 1024 個(gè)空閑 page 就是伙伴。

image.png

再比如上圖中的 page0 和 page 1 是伙伴，page2 到 page 5 是伙伴，page6 和 page7 又是伙伴。但是 page0 和 page2 就不能成為伙伴，因?yàn)樗鼈兊奈锢韮?nèi)存是不連續(xù)的。同時(shí) (page0 到 page3) 和 (page4 到 page7) 所組成的兩個(gè)內(nèi)存塊又能構(gòu)成一個(gè)伙伴。伙伴必須是大小相同并且在物理內(nèi)存上是連續(xù)的兩個(gè)或者多個(gè) page。

3. 伙伴系統(tǒng)的內(nèi)存分配原理

在 《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 一文中的第二小節(jié) " 2. 物理內(nèi)存分配內(nèi)核源碼實(shí)現(xiàn) "，筆者介紹了如下四個(gè)內(nèi)存分配的接口，內(nèi)核可以通過這些接口向伙伴系統(tǒng)申請(qǐng)內(nèi)存：

structpage*alloc_pages(gfp_tgfp,unsignedintorder)
unsignedlong__get_free_pages(gfp_tgfp_mask,unsignedintorder)
unsignedlongget_zeroed_page(gfp_tgfp_mask)
unsignedlong__get_dma_pages(gfp_tgfp_mask,unsignedintorder)

image.png

首先我們可以根據(jù)內(nèi)存分配接口函數(shù)中的 gfp_t gfp_mask ，找到內(nèi)存分配指定的 NUMA 節(jié)點(diǎn)和物理內(nèi)存區(qū)域 zone ，然后找到物理內(nèi)存區(qū)域 zone 對(duì)應(yīng)的伙伴系統(tǒng)。

image.png

隨后內(nèi)核通過接口中指定的分配階 order，可以定位到伙伴系統(tǒng)的 free_area[order] 數(shù)組，其中存放的就是分配階為 order 的全部?jī)?nèi)存塊。

最后內(nèi)核進(jìn)一步通過 gfp_t gfp_mask 掩碼中指定的頁面遷移類型 MIGRATE_TYPE，定位到 free_list[MIGRATE_TYPE]，這里存放的就是符合內(nèi)存分配要求的所有內(nèi)存塊。通過遍歷這個(gè)雙向鏈表就可以輕松獲得要分配的內(nèi)存。

image.png

比如我們向內(nèi)核申請(qǐng) ( 2 ^ (order - 1)，2 ^ order ] 之間大小的內(nèi)存，并且這塊內(nèi)存我們指定的遷移類型為 MIGRATE_MOVABLE 時(shí)，內(nèi)核會(huì)按照 2 ^ order 個(gè)內(nèi)存頁進(jìn)行申請(qǐng)。

隨后內(nèi)核會(huì)根據(jù) order 找到伙伴系統(tǒng)中的 free_area[order] 對(duì)應(yīng)的 free_area 結(jié)構(gòu)，并進(jìn)一步根據(jù)頁面遷移類型定位到對(duì)應(yīng)的 free_list[MIGRATE_MOVABLE]，如果該遷移類型的 free_list 中沒有空閑的內(nèi)存塊時(shí)，內(nèi)核會(huì)進(jìn)一步到上一級(jí)鏈表也就是 free_area[order + 1] 中尋找。

如果 free_area[order + 1] 中對(duì)應(yīng)的 free_list[MIGRATE_MOVABLE] 鏈表中還是沒有，則繼續(xù)循環(huán)到更高一級(jí) free_area[order + 2] 尋找，直到在 free_area[order + n] 中的 free_list[MIGRATE_MOVABLE] 鏈表中找到空閑的內(nèi)存塊。

但是此時(shí)我們?cè)?free_area[order + n] 鏈表中找到的空閑內(nèi)存塊的尺寸是 2 ^ (order + n) 大小，而我們需要的是 2 ^ order 尺寸的內(nèi)存塊，于是內(nèi)核會(huì)將這 2 ^ (order + n) 大小的內(nèi)存塊逐級(jí)減半分裂，將每一次分裂后的內(nèi)存塊插入到相應(yīng)的 free_area 數(shù)組里對(duì)應(yīng)的 free_list[MIGRATE_MOVABLE] 鏈表中，并將最后分裂出的 2 ^ order 尺寸的內(nèi)存塊分配給進(jìn)程使用。

下面筆者舉一個(gè)具體的例子來為大家說明伙伴系統(tǒng)的整個(gè)內(nèi)存分配過程：

為了清晰地給大家展現(xiàn)伙伴系統(tǒng)的內(nèi)存分配過程，我們暫時(shí)忽略 MIGRATE_TYPES 相關(guān)的組織結(jié)構(gòu)

image.png

我們假設(shè)當(dāng)前伙伴系統(tǒng)中只有 order = 3 的空閑鏈表 free_area[3]，其余剩下的分配階 order 對(duì)應(yīng)的空閑鏈表中均是空的。 free_area[3] 中僅有一個(gè)空閑的內(nèi)存塊，其中包含了連續(xù)的 8 個(gè) page。

現(xiàn)在我們向伙伴系統(tǒng)申請(qǐng)一個(gè) page 大小的內(nèi)存（對(duì)應(yīng)的分配階 order = 0），那么內(nèi)核會(huì)在伙伴系統(tǒng)中首先查看 order = 0 對(duì)應(yīng)的空閑鏈表 free_area[0] 中是否有空閑內(nèi)存塊可供分配。

隨后內(nèi)核會(huì)根據(jù)前邊介紹的內(nèi)存分配邏輯，繼續(xù)升級(jí)到 free_area[1] , free_area[2] 鏈表中尋找空閑內(nèi)存塊，直到查找到 free_area[3] 發(fā)現(xiàn)有一個(gè)可供分配的內(nèi)存塊。這個(gè)內(nèi)存塊中包含了 8 個(gè) 連續(xù)的空閑 page，但是我們只要一個(gè) page 就夠了，那該怎么辦呢？

于是內(nèi)核先將 free_area[3] 中的這個(gè)空閑內(nèi)存塊從鏈表中摘下，然后減半分裂成兩個(gè)內(nèi)存塊，分裂出來的這兩個(gè)內(nèi)存塊分別包含 4 個(gè) page（分配階 order = 2）。

image.png

上圖分裂出的兩個(gè)內(nèi)存塊，黃色的代表原有內(nèi)存塊的前半部分，綠色代表原有內(nèi)存塊的后半部分。

隨后內(nèi)核會(huì)將分裂出的后半部分（圖中綠色部分，order = 2），插入到 free_rea[2] 鏈表中。

image.png

前半部分（圖中黃色部分，order = 2）繼續(xù)減半分裂，分裂出來的這兩個(gè)內(nèi)存塊分別包含 2 個(gè) page（分配階 order = 1）。如下圖中第 4 步所示，前半部分為黃色，后半部分為紫色。同理按照前邊的分裂邏輯，內(nèi)核會(huì)將后半部分內(nèi)存塊（紫色部分，分配階 order = 1）插入到 free_area[1] 鏈表中。

image.png

前半部分（圖中黃色部分，order = 1）在上圖中的第 6 步繼續(xù)減半分裂，分裂出來的這兩個(gè)內(nèi)存塊分別包含 1 個(gè) page（分配階 order = 0），前半部分為青色，后半部分為黃色。

后半部分插入到 frea_area[0] 鏈表中，前半部分返回給進(jìn)程，這時(shí)內(nèi)存分配成功，流程結(jié)束。

以上流程就是伙伴系統(tǒng)的核心內(nèi)存分配過程，下面我們?cè)侔褍?nèi)存頁面的遷移屬性 MIGRATE_TYPES 考慮進(jìn)來，來看一下完整的伙伴系統(tǒng)內(nèi)存分配流程：

image.png

現(xiàn)在我們加上了內(nèi)存 MIGRATE_TYPES 的組織結(jié)構(gòu)，其實(shí)分配流程還是和核心流程一樣的，只不過上面提到的那些高階 order 的減半分裂情形都發(fā)生在各個(gè) free_area[order] 中固定的 free_list[MIGRATE_TYPE] 里罷了。

比如我們要求分配的內(nèi)存遷移屬性要求是 MIGRATE_MOVABLE 類型，那么減半分裂流程分別發(fā)生在 free_area[2] ，free_area[1] ，free_area[0] 對(duì)應(yīng)的 free_list[MIGRATE_MOVABLE] 中，多了一個(gè) free_list 的維度，僅此而已。

不過筆者這里想重點(diǎn)著墨的地方是內(nèi)存分配的一種異常情形，比如我們想要分配特定遷移類型的內(nèi)存，但是當(dāng)前伙伴系統(tǒng)所有 free_area[order] 里對(duì)應(yīng)的 free_list[MIGRATE_TYPE] 均無法滿足內(nèi)存分配的需求（沒有足夠特定遷移類型的空閑內(nèi)存塊）。那么這種場(chǎng)景下內(nèi)核會(huì)怎么處理呢？

其實(shí)同樣的問題我們?cè)?《深入理解 Linux 物理內(nèi)存管理》 一文中也遇到過，當(dāng)時(shí)筆者介紹內(nèi)存 NUMA 架構(gòu)的時(shí)候提到，如果當(dāng)前 NUMA 節(jié)點(diǎn)無法滿足內(nèi)存分配時(shí)，內(nèi)核會(huì)跨越 NUMA 節(jié)點(diǎn)從其他節(jié)點(diǎn)上分配內(nèi)存。

typedefstructpglist_data{
//NUMA節(jié)點(diǎn)中的物理內(nèi)存區(qū)域個(gè)數(shù)
intnr_zones;
//NUMA節(jié)點(diǎn)中的物理內(nèi)存區(qū)域
structzonenode_zones[MAX_NR_ZONES];
//NUMA節(jié)點(diǎn)的備用列表
structzonelistnode_zonelists[MAX_ZONELISTS];
}pg_data_t;

每個(gè) NUMA 節(jié)點(diǎn)的 struct pglist_data 結(jié)構(gòu)中都會(huì)包含一個(gè) node_zonelists，其中包含了當(dāng)前NUMA 節(jié)點(diǎn)以及備用 NUMA 節(jié)點(diǎn)的所有內(nèi)存區(qū)域以及對(duì)應(yīng)的伙伴系統(tǒng)，當(dāng)前 NUMA 節(jié)點(diǎn)內(nèi)存不足時(shí)，內(nèi)核會(huì)從 node_zonelists 中的備用 NUMA 節(jié)點(diǎn)中分配內(nèi)存。

這里也是同樣的道理，當(dāng)伙伴系統(tǒng)中指定的遷移列表 free_list[MIGRATE_TYPE] 無法滿足內(nèi)存分配需求時(shí)，內(nèi)核根據(jù)不同遷移類型定義了不同的 fallback 規(guī)則：

/*
*Thisarraydescribestheorderlistsarefallenbacktowhen
*thefreelistsforthedesirablemigratetypearedepleted
*
*Theothermigratetypesdonothavefallbacks.
*/
staticintfallbacks[MIGRATE_TYPES][3]={
[MIGRATE_UNMOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
[MIGRATE_MOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_UNMOVABLE,MIGRATE_TYPES},
[MIGRATE_RECLAIMABLE]={MIGRATE_UNMOVABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
};

比如：MIGRATE_UNMOVABLE 類型的 free_list 內(nèi)存不足時(shí)，內(nèi)核會(huì) fallback 到 MIGRATE_RECLAIMABLE 中去獲取，如果還是不足，則再次降級(jí)到 MIGRATE_MOVABLE 中獲取，如果仍然無法滿足內(nèi)存分配，才會(huì)失敗退出。

正常的分配流程先是從低階到高階依次查找空閑內(nèi)存塊，然后將高階中的內(nèi)存塊依次減半分裂到低階 free_list 鏈表中。

內(nèi)存分配 fallback 流程則剛好是相反的，它是先從備用 fallback 類型的遷移列表中的最高階開始查找，找到一塊空閑內(nèi)存塊之后，先遷移到最初指定的 free_list[MIGRATE_TYPE] 鏈表中，然后在指定的 free_list[MIGRATE_TYPE] 鏈表執(zhí)行減半分裂。

內(nèi)核這里的 fallback 策略是：如果無法避免分配遷移類型不同的內(nèi)存塊，那么就分配一個(gè)盡可能大的內(nèi)存塊（從最高階開始查找），避免向其他鏈表引入內(nèi)存碎片。

筆者還是以上邊的例子說明，當(dāng)我們向伙伴系統(tǒng)申請(qǐng) MIGRATE_UNMOVABLE 遷移類型的內(nèi)存時(shí)，假設(shè)內(nèi)核在伙伴系統(tǒng)中的 free_area[0] 到 free_area[10] 中的所有 free_list[MIGRATE_UNMOVABLE] 鏈表中均無法找到一個(gè)空閑的內(nèi)存塊。

那么就會(huì) fallback 到 MIGRATE_RECLAIMABLE 類型，從最高階 free_area[10] 中的 free_list[MIGRATE_RECLAIMABLE] 鏈表開始查找，如果找到一個(gè)空閑的內(nèi)存塊，則首先會(huì)遷移到對(duì)應(yīng)的 order 的 free_list[MIGRATE_UNMOVABLE] 鏈表，然后流程繼續(xù)回到核心流程，在各個(gè) free_area[order] 對(duì)應(yīng)的 free_list[MIGRATE_UNMOVABLE] 鏈表中執(zhí)行減半分裂。

這里大家只需要理解一下 fallback 的大概流程，詳細(xì)內(nèi)容筆者會(huì)在后面介紹伙伴系統(tǒng)實(shí)現(xiàn)的章節(jié)詳細(xì)解析~~~

4. 伙伴系統(tǒng)的內(nèi)存回收原理

內(nèi)存有分配就會(huì)有釋放，本小節(jié)我們就來看下如何將內(nèi)存塊釋放回伙伴系統(tǒng)中。在上個(gè)小節(jié)中筆者為大家介紹了伙伴系統(tǒng)內(nèi)存分配的完整流程，核心就是從高階 free_list 中尋找空閑內(nèi)存塊，然后依次減半分裂。

伙伴系統(tǒng)中的內(nèi)存回收剛好和內(nèi)存分配的過程相反，核心則是從低階 free_list 中尋找釋放內(nèi)存塊的伙伴，如果沒有伙伴則將要釋放的內(nèi)存塊插入到對(duì)應(yīng)分配階 order 的 free_list中。如果存在伙伴，則將釋放內(nèi)存塊與它的伙伴合并，作為一個(gè)新的內(nèi)存塊繼續(xù)到更高階的 free_list 中循環(huán)重復(fù)上述過程，直到不能合并為止。

伙伴的概念我們已經(jīng)在本文 《 2. 到底什么是伙伴 》小節(jié)中介紹過了，核心就是兩個(gè)伙伴內(nèi)存塊必須是大小相同并且在物理內(nèi)存上是連續(xù)的。

下面筆者還是舉一個(gè)具體的例子來為大家展現(xiàn)伙伴系統(tǒng)內(nèi)存回收的過程：

為了清晰地給大家展現(xiàn)伙伴系統(tǒng)的內(nèi)存回收過程，我們暫時(shí)忽略 MIGRATE_TYPES 相關(guān)的組織結(jié)構(gòu)

image.png

假設(shè)當(dāng)前伙伴系統(tǒng)的狀態(tài)如上圖所示，現(xiàn)在我們需要向伙伴系統(tǒng)釋放一個(gè)內(nèi)存頁（order = 0），編號(hào)為10。

這里筆者先來解釋下上圖伙伴系統(tǒng)中所管理的物理內(nèi)存頁后邊編號(hào)的含義：我們知道伙伴系統(tǒng)中所管理的全部是連續(xù)的物理內(nèi)存，既然是連續(xù)的，那么每個(gè)內(nèi)存頁 page 都會(huì)有一個(gè)固定的偏移（類似數(shù)組中的下標(biāo)）。

這一點(diǎn)我們?cè)谇斑叺奈恼?《深入理解 Linux 物理內(nèi)存管理》的 “ 4.2 NUMA 節(jié)點(diǎn)描述符 pglist_data 結(jié)構(gòu) ” 小節(jié)中已經(jīng)介紹過了，在每個(gè) NUMA 節(jié)點(diǎn)中，內(nèi)核通過一個(gè) node_mem_map 數(shù)組來組織節(jié)點(diǎn)內(nèi)的物理內(nèi)存頁 page。

typedefstructpglist_data{
//NUMA節(jié)點(diǎn)id
intnode_id;
//指向NUMA節(jié)點(diǎn)內(nèi)管理所有物理頁page的數(shù)組
structpage*node_mem_map;
}

上圖伙伴系統(tǒng)中所管理的內(nèi)存頁 page 只是被伙伴系統(tǒng)組織之后的視圖，下面是物理內(nèi)存頁在物理內(nèi)存上的真實(shí)視圖（包含要被釋放的內(nèi)存頁 10）：

image.png

有了這些基本概念之后，我回過頭來在看 page10 釋放回伙伴系統(tǒng)的整個(gè)過程：

下面的流程需要大家時(shí)刻對(duì)比內(nèi)存頁在物理內(nèi)存上的真實(shí)視圖，不要被伙伴系統(tǒng)的組織視圖所干擾。

image.png

由于我們要釋放的內(nèi)存塊只包含了一個(gè)物理內(nèi)存頁 page10，所以它的分配階 order = 0，首先內(nèi)核需要在伙伴系統(tǒng) free_area[0] 中查找與 page10 大小相等并且連續(xù)的內(nèi)存塊（伙伴）。

從物理內(nèi)存的真實(shí)視圖中我們可以看到 page11 是 page10 的伙伴，于是將 page11 從 free_area[0] 上摘下并與 page10 合并組成一個(gè)新的內(nèi)存塊（分配階 order = 1）。隨后內(nèi)核會(huì)在 free_area[1] 中查找新內(nèi)存塊的伙伴：

image.png

我們繼續(xù)對(duì)比物理內(nèi)存頁的真實(shí)視圖，發(fā)現(xiàn)在 free_area[1] 中 page8 和 page9 組成的內(nèi)存塊與 page10 和 page11 組成的內(nèi)存塊是伙伴，于是繼續(xù)將這兩個(gè)內(nèi)存塊（分配階 order = 1）繼續(xù)合并成一個(gè)新的內(nèi)存塊（分配階 order = 2）。隨后內(nèi)核會(huì)在 free_area[2] 中查找新內(nèi)存塊的伙伴：

image.png

繼續(xù)對(duì)比物理內(nèi)存頁的真實(shí)視圖，發(fā)現(xiàn)在 free_area[2] 中 page12，page13，page14，page15 組成的內(nèi)存塊與 page8，page9，page10，page11 組成的新內(nèi)存塊是伙伴，于是將它們從 free_area[2] 上摘下繼續(xù)合并成一個(gè)新的內(nèi)存塊（分配階 order = 3），隨后內(nèi)核會(huì)在 free_area[3] 中查找新內(nèi)存塊的伙伴：

image.png

對(duì)比物理內(nèi)存頁的真實(shí)視圖，我們發(fā)現(xiàn)在 free_area[3] 中的內(nèi)存塊（page20 到 page 27）與新合并的內(nèi)存塊（page8 到 page15）雖然大小相同但是物理上并不連續(xù)，所以它們不是伙伴，不能在繼續(xù)向上合并了。于是內(nèi)核將 page8 到 pag15 組成的內(nèi)存塊（分配階 order = 3）插入到 free_area[3] 中，至此內(nèi)存釋放過程結(jié)束。

image.png

到這里關(guān)于伙伴系統(tǒng)內(nèi)存分配以及回收的核心原理筆者就為大家全部介紹完了，內(nèi)存分配和釋放的過程剛好是相反的過程。

內(nèi)存分配是從高階先查找到空閑內(nèi)存塊，然后依次減半分裂，將分裂后的內(nèi)存塊插入到低階的 free_list 中，將最后分裂出來的內(nèi)存塊分配給進(jìn)程。

內(nèi)存釋放是先從低階開始查找釋放內(nèi)存塊的伙伴，如果找到，則兩兩合并成一個(gè)新的內(nèi)存塊，隨后繼續(xù)到高階中去查找新內(nèi)存塊的伙伴，直到?jīng)]有伙伴可以合并。

一個(gè)是高階到低階分裂，一個(gè)是低階到高階合并。

5. 進(jìn)入伙伴系統(tǒng)的前奏

現(xiàn)在我們已經(jīng)清楚了伙伴系統(tǒng)的所有核心原理，但是干講原理總覺得 talk is cheap，還是需要 show 一下 code，所以接下來筆者會(huì)帶大家看一下內(nèi)核中伙伴系統(tǒng)的實(shí)現(xiàn)源碼，真刀真槍的來一下。

但真正進(jìn)入伙伴系統(tǒng)之前，內(nèi)核還是做了很多鋪墊工作，為了給大家解釋清楚這些內(nèi)容，我們還是需要重新回到上篇文章 《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 “5. __alloc_pages 內(nèi)存分配流程總覽” 小節(jié)中留下的尾巴，正式來介紹下 get_page_from_freelist 函數(shù)。

在上篇文章 “3. 物理內(nèi)存分配內(nèi)核源碼實(shí)現(xiàn)” 小節(jié)中，筆者為大家介紹了 Linux 物理內(nèi)存分配的完整流程，我們知道物理內(nèi)存分配總體上分為兩個(gè)路徑，內(nèi)核首先嘗試的是在快速路徑下分配內(nèi)存，如果不行的話，內(nèi)核會(huì)走慢速路徑分配內(nèi)存。

無論是快速路徑還是慢速路徑下的內(nèi)存分配都需要最終調(diào)用 get_page_from_freelist 函數(shù)進(jìn)行最終的內(nèi)存分配。只不過，不同路徑下 get_page_from_freelist 函數(shù)的內(nèi)存分配策略以及需要考慮的內(nèi)存水位線會(huì)有所不同，其中慢速路徑下的內(nèi)存分配策略會(huì)更加激進(jìn)一些，這一點(diǎn)我們?cè)谏掀恼碌南嚓P(guān)章節(jié)內(nèi)容介紹中體會(huì)很深。

image.png

在每次調(diào)用 get_page_from_freelist 函數(shù)之前，內(nèi)核都會(huì)根據(jù)新的內(nèi)存分配策略來重新初始化 struct alloc_context 結(jié)構(gòu)，alloc_context 結(jié)構(gòu)體中包含了內(nèi)存分配所需要的所有核心參數(shù)。詳細(xì)初始化過程可以回看上篇文章的 “3.3 prepare_alloc_pages” 小節(jié)的內(nèi)容。

structalloc_context{
//運(yùn)行進(jìn)程CPU所在NUMA節(jié)點(diǎn)以及其所有備用NUMA節(jié)點(diǎn)中允許內(nèi)存分配的內(nèi)存區(qū)域
structzonelist*zonelist;
//NUMA節(jié)點(diǎn)狀態(tài)掩碼
nodemask_t*nodemask;
//內(nèi)存分配優(yōu)先級(jí)最高的內(nèi)存區(qū)域zone
structzoneref*preferred_zoneref;
//物理內(nèi)存頁的遷移類型分為：不可遷移，可回收，可遷移類型，防止內(nèi)存碎片
intmigratetype;

//內(nèi)存分配最高優(yōu)先級(jí)的內(nèi)存區(qū)域zone
enumzone_typehighest_zoneidx;
//是否允許當(dāng)前NUMA節(jié)點(diǎn)中的臟頁均衡擴(kuò)散遷移至其他NUMA節(jié)點(diǎn)
boolspread_dirty_pages;
};

這里最核心的兩個(gè)參數(shù)就是 zonelist 和 preferred_zoneref。preferred_zoneref 表示當(dāng)前本地 NUMA 節(jié)點(diǎn)（優(yōu)先級(jí)最高），其中 zonelist 我們?cè)?《深入理解 Linux 物理內(nèi)存管理》的 “ 4.3 NUMA 節(jié)點(diǎn)物理內(nèi)存區(qū)域的劃分 ” 小節(jié)中詳細(xì)介紹過，zonelist 里面包含了當(dāng)前 NUMA 節(jié)點(diǎn)在內(nèi)的所有備用 NUMA 節(jié)點(diǎn)的所有物理內(nèi)存區(qū)域，用于當(dāng)前 NUMA 節(jié)點(diǎn)沒有足夠空閑內(nèi)存的情況下進(jìn)行跨 NUMA 節(jié)點(diǎn)分配。

typedefstructpglist_data{
//NUMA節(jié)點(diǎn)中的物理內(nèi)存區(qū)域個(gè)數(shù)
intnr_zones;
//NUMA節(jié)點(diǎn)中的物理內(nèi)存區(qū)域
structzonenode_zones[MAX_NR_ZONES];
//NUMA節(jié)點(diǎn)的備用列表
structzonelistnode_zonelists[MAX_ZONELISTS];
}pg_data_t;

struct pglist_data 里的 node_zonelists 是一個(gè)全集，而 struct alloc_context 里的 zonelist 是在內(nèi)存分配過程中，根據(jù)指定的內(nèi)存分配策略從全集 node_zonelists 過濾出來的一個(gè)子集（允許進(jìn)行本次內(nèi)存分配的所有 NUMA 節(jié)點(diǎn)及其內(nèi)存區(qū)域）。

get_page_from_freelist 的核心邏輯其實(shí)很簡(jiǎn)單，就是遍歷 struct alloc_context 里的 zonelist，挨個(gè)檢查各個(gè) NUMA 節(jié)點(diǎn)中的物理內(nèi)存區(qū)域是否有足夠的空閑內(nèi)存可以滿足本次的內(nèi)存分配要求，如果可以滿足則進(jìn)入該物理內(nèi)存區(qū)域的伙伴系統(tǒng)中完整真正的內(nèi)存分配動(dòng)作。

下面我們先來看一下 get_page_from_freelist 函數(shù)的完整邏輯：

image.png

/*
*get_page_from_freelistgoesthroughthezonelisttryingtoallocate
*apage.
*/
staticstructpage*
get_page_from_freelist(gfp_tgfp_mask,unsignedintorder,intalloc_flags,
conststructalloc_context*ac)
{
structzoneref*z;
//當(dāng)前遍歷到的內(nèi)存區(qū)域zone引用
structzone*zone;
//最近遍歷的NUMA節(jié)點(diǎn)
structpglist_data*last_pgdat=NULL;
//最近遍歷的NUMA節(jié)點(diǎn)中包含的臟頁數(shù)量是否在內(nèi)核限制范圍內(nèi)
boollast_pgdat_dirty_ok=false;
//如果需要避免內(nèi)存碎片，則no_fallback=true
boolno_fallback;

retry:
//是否需要避免內(nèi)存碎片
no_fallback=alloc_flags&ALLOC_NOFRAGMENT;
z=ac->preferred_zoneref;
//開始遍歷zonelist，查找可以滿足本次內(nèi)存分配的物理內(nèi)存區(qū)域zone
for_next_zone_zonelist_nodemask(zone,z,ac->highest_zoneidx,
ac->nodemask){
//指向分配成功之后的內(nèi)存
structpage*page;
//內(nèi)存分配過程中設(shè)定的水位線
unsignedlongmark;
//檢查內(nèi)存區(qū)域所在NUMA節(jié)點(diǎn)是否在進(jìn)程所允許的CPU上
if(cpusets_enabled()&&
(alloc_flags&ALLOC_CPUSET)&&
!__cpuset_zone_allowed(zone,gfp_mask))
continue;
//每個(gè)NUMA節(jié)點(diǎn)中包含的臟頁數(shù)量都有一定的限制。
//如果本次內(nèi)存分配是為pagecache分配的page，用于寫入數(shù)據(jù)（不久就會(huì)變成臟頁）
//這里需要檢查當(dāng)前NUMA節(jié)點(diǎn)的臟頁比例是否在限制范圍內(nèi)允許的
//如果沒有超過臟頁限制則可以進(jìn)行分配，如果已經(jīng)超過last_pgdat_dirty_ok=false
if(ac->spread_dirty_pages){
if(last_pgdat!=zone->zone_pgdat){
last_pgdat=zone->zone_pgdat;
last_pgdat_dirty_ok=node_dirty_ok(zone->zone_pgdat);
}

if(!last_pgdat_dirty_ok)
continue;
}

//如果內(nèi)核設(shè)置了避免內(nèi)存碎片標(biāo)識(shí)，在本地節(jié)點(diǎn)無法滿足內(nèi)存分配的情況下(因?yàn)樾枰苊鈨?nèi)存碎片)
//這輪循環(huán)會(huì)遍歷remote節(jié)點(diǎn)（跨NUMA節(jié)點(diǎn)）
if(no_fallback&&nr_online_nodes>1&&
zone!=ac->preferred_zoneref->zone){
intlocal_nid;
//如果本地節(jié)點(diǎn)分配內(nèi)存失敗是因?yàn)楸苊鈨?nèi)存碎片的原因，那么會(huì)繼續(xù)回到本地節(jié)點(diǎn)進(jìn)行retry重試同時(shí)取消ALLOC_NOFRAGMENT（允許引入碎片）
local_nid=zone_to_nid(ac->preferred_zoneref->zone);
if(zone_to_nid(zone)!=local_nid){
//內(nèi)核認(rèn)為保證本地的局部性會(huì)比避免內(nèi)存碎片更加重要
alloc_flags&=~ALLOC_NOFRAGMENT;
gotoretry;
}
}
//獲取本次內(nèi)存分配需要考慮到的內(nèi)存水位線，快速路徑下是WMARK_LOW,慢速路徑下是WMARK_MIN
mark=wmark_pages(zone,alloc_flags&ALLOC_WMARK_MASK);
//檢查當(dāng)前遍歷到的zone里剩余的空閑內(nèi)存容量是否在指定水位線mark之上
//剩余內(nèi)存容量在水位線之下返回false
if(!zone_watermark_fast(zone,order,mark,
ac->highest_zoneidx,alloc_flags,
gfp_mask)){
intret;

//如果本次內(nèi)存分配策略是忽略內(nèi)存水位線，那么就在本次遍歷到的zone里嘗試分配內(nèi)存
if(alloc_flags&ALLOC_NO_WATERMARKS)
gototry_this_zone;
//如果本次內(nèi)存分配不能忽略內(nèi)存水位線的限制，那么就會(huì)判斷當(dāng)前zone所屬NUMA節(jié)點(diǎn)是否允許進(jìn)行內(nèi)存回收
if(!node_reclaim_enabled()||
!zone_allows_reclaim(ac->preferred_zoneref->zone,zone))
//不允許進(jìn)行內(nèi)存回收則繼續(xù)遍歷下一個(gè)NUMA節(jié)點(diǎn)的內(nèi)存區(qū)域
continue;
//針對(duì)當(dāng)前zone所在NUMA節(jié)點(diǎn)進(jìn)行內(nèi)存回收
ret=node_reclaim(zone->zone_pgdat,gfp_mask,order);
switch(ret){
caseNODE_RECLAIM_NOSCAN:
//返回該值表示當(dāng)前NUMA節(jié)點(diǎn)沒有必要進(jìn)行回收。比如快速分配路徑下就不處理頁面回收的問題
continue;
caseNODE_RECLAIM_FULL:
//返回該值表示通過掃描之后發(fā)現(xiàn)當(dāng)前NUMA節(jié)點(diǎn)并沒有可以回收的內(nèi)存頁
continue;
default:
//該分支表示當(dāng)前NUMA節(jié)點(diǎn)已經(jīng)進(jìn)行了內(nèi)存回收操作
//zone_watermark_ok判斷內(nèi)存回收是否回收了足夠的內(nèi)存能否滿足內(nèi)存分配的需要
if(zone_watermark_ok(zone,order,mark,
ac->highest_zoneidx,alloc_flags))
gototry_this_zone;

continue;
}
}

try_this_zone:
//這里就是伙伴系統(tǒng)的入口，rmqueue函數(shù)中封裝的就是伙伴系統(tǒng)的核心邏輯
//從伙伴系統(tǒng)中獲取內(nèi)存
page=rmqueue(ac->preferred_zoneref->zone,zone,order,
gfp_mask,alloc_flags,ac->migratetype);
if(page){
//分配內(nèi)存成功，初始化內(nèi)存頁page
prep_new_page(page,order,gfp_mask,alloc_flags);
returnpage;
}else{
.......省略.....
}
}

//內(nèi)存分配失敗
returnNULL;
}

與本文主題無關(guān)的非核心步驟大家通過筆者的注釋簡(jiǎn)單了解即可，下面我們只介紹與本文主題相關(guān)的核心步驟。

雖然 get_page_from_freelist 函數(shù)的代碼比較冗長(zhǎng)，但是其核心邏輯比較簡(jiǎn)單，主干框架就是通過 for_next_zone_zonelist_nodemask 來遍歷當(dāng)前 NUMA 節(jié)點(diǎn)以及備用節(jié)點(diǎn)的所有內(nèi)存區(qū)域（zonelist），然后逐個(gè)通過 zone_watermark_fast 檢查這些內(nèi)存區(qū)域 zone 中的剩余空閑內(nèi)存容量是否在指定的水位線 mark 之上。如果滿足水位線的要求則直接調(diào)用 rmqueue 進(jìn)入伙伴系統(tǒng)分配內(nèi)存，分配成功之后通過 prep_new_page 初始化分配好的內(nèi)存頁 page。

如果當(dāng)前正在遍歷的 zone 中剩余空閑內(nèi)存容量在指定的水位線 mark 之下，就需要通過 node_reclaim 觸發(fā)內(nèi)存回收，隨后通過 zone_watermark_ok 檢查經(jīng)過內(nèi)存回收之后，內(nèi)核是否回收到了足夠的內(nèi)存以滿足本次內(nèi)存分配的需要。如果內(nèi)存回收到了足夠的內(nèi)存則 zone_watermark_ok = true 隨后跳轉(zhuǎn)到 try_this_zone 分支在本內(nèi)存區(qū)域 zone 中分配內(nèi)存。否則繼續(xù)遍歷下一個(gè) zone。

5.1 獲取內(nèi)存區(qū)域 zone 里指定的內(nèi)存水位線

get_page_from_freelist 函數(shù)中的內(nèi)存分配邏輯是要考慮內(nèi)存水位線的，滿足內(nèi)存分配要求的物理內(nèi)存區(qū)域 zone 中的剩余空閑內(nèi)存容量必須在指定內(nèi)存水位線之上。否則內(nèi)核則認(rèn)為內(nèi)存不足不能進(jìn)行內(nèi)存分配。

在上篇文章 《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 中的 “3.2 內(nèi)存分配的心臟 __alloc_pages” 小節(jié)的介紹中，我們知道在快速路徑下，內(nèi)存分配策略中的水位線設(shè)置為 WMARK_LOW：

//內(nèi)存區(qū)域中的剩余內(nèi)存需要在WMARK_LOW水位線之上才能進(jìn)行內(nèi)存分配，否則失敗（初次嘗試快速內(nèi)存分配）
unsignedintalloc_flags=ALLOC_WMARK_LOW;

在上篇文章 “4. 內(nèi)存慢速分配入口 alloc_pages_slowpath” 小節(jié)的介紹中，我們知道在慢速路徑下，內(nèi)存分配策略中的水位線又被調(diào)整為了 WMARK_MIN：

//在慢速內(nèi)存分配路徑中，會(huì)進(jìn)一步放寬對(duì)內(nèi)存分配的限制，將內(nèi)存分配水位線調(diào)低到WMARK_MIN
//也就是說內(nèi)存區(qū)域中的剩余內(nèi)存需要在WMARK_MIN水位線之上就可以進(jìn)行內(nèi)存分配了
unsignedintalloc_flags=ALLOC_WMARK_MIN|ALLOC_CPUSET;

如果內(nèi)存分配仍然失敗，則內(nèi)核會(huì)將內(nèi)存分配策略中的水位線調(diào)整為 ALLOC_NO_WATERMARKS，表示再內(nèi)存分配時(shí)，可以忽略水位線的限制，再一次進(jìn)行重試。

不同的內(nèi)存水位線會(huì)影響到內(nèi)存分配邏輯，所以在通過 for_next_zone_zonelist_nodemask 遍歷 NUMA 節(jié)點(diǎn)中的物理內(nèi)存區(qū)域的一開始就需要獲取該內(nèi)存區(qū)域指定水位線的具體數(shù)值，內(nèi)核通過 wmark_pages 宏來獲取：

#definewmark_pages(z,i)(z->_watermark[i]+z->watermark_boost)

structzone{
//物理內(nèi)存區(qū)域中的水位線
unsignedlong_watermark[NR_WMARK];
//優(yōu)化內(nèi)存碎片對(duì)內(nèi)存分配的影響，可以動(dòng)態(tài)改變內(nèi)存區(qū)域的基準(zhǔn)水位線。
unsignedlongwatermark_boost;
}

關(guān)于內(nèi)存區(qū)域 zone 中水位線的相關(guān)內(nèi)容介紹，大家可以回看下筆者之前的文章 《深入理解 Linux 物理內(nèi)存管理》 中 “ 5.2 物理內(nèi)存區(qū)域中的水位線 ” 小節(jié)。

5.2 檢查 zone 中剩余內(nèi)存容量是否滿足水位線要求

在我們通過 wmark_pages 獲取到當(dāng)前內(nèi)存區(qū)域 zone 的指定水位線 mark 之后，我們就需要近一步判斷當(dāng)前 zone 中剩余的空閑內(nèi)存容量是否在水位線 mark 之上，這是保證內(nèi)存分配順利進(jìn)行的必要條件。

內(nèi)核中判斷水位線的邏輯封裝在 zone_watermark_fast 和 __zone_watermark_ok 函數(shù)中，其中核心邏輯在 __zone_watermark_ok 里，zone_watermark_fast 只是用來快速檢測(cè)分配階 order = 0 情況下的相關(guān)水位線情況。

下面我們先來看下 zone_watermark_fast 的邏輯：

staticinlineboolzone_watermark_fast(structzone*z,unsignedintorder,
unsignedlongmark,inthighest_zoneidx,
unsignedintalloc_flags,gfp_tgfp_mask)
{
longfree_pages;
//獲取當(dāng)前內(nèi)存區(qū)域中所有空閑的物理內(nèi)存頁
free_pages=zone_page_state(z,NR_FREE_PAGES);

//快速檢查分配階order=0情況下相關(guān)水位線，空閑內(nèi)存需要刨除掉為highatomic預(yù)留的緊急內(nèi)存
if(!order){
longusable_free;
longreserved;
//可供本次內(nèi)存分配使用的符合要求的真實(shí)可用內(nèi)存，初始為free_pages
//free_pages為空閑內(nèi)存頁的全集其中也包括了不能為本次內(nèi)存分配提供內(nèi)存的空閑內(nèi)存
usable_free=free_pages;
//獲取本次不能使用的空閑內(nèi)存頁數(shù)量
reserved=__zone_watermark_unusable_free(z,0,alloc_flags);

//計(jì)算真正可供內(nèi)存分配的空閑頁數(shù)量：空閑內(nèi)存頁全集-不能使用的空閑頁
usable_free-=min(usable_free,reserved);
//如果可用的空閑內(nèi)存頁數(shù)量大于內(nèi)存水位線與預(yù)留內(nèi)存之和
//那么表示物理內(nèi)存區(qū)域中的可用空閑內(nèi)存能夠滿足本次內(nèi)存分配的需要
if(usable_free>mark+z->lowmem_reserve[highest_zoneidx])
returntrue;
}
//近一步檢查內(nèi)存區(qū)域伙伴系統(tǒng)中是否有足夠的order階的內(nèi)存塊可供分配
if(__zone_watermark_ok(z,order,mark,highest_zoneidx,alloc_flags,
free_pages))
returntrue;

........省略無關(guān)代碼.......

//水位線檢查失敗
returnfalse;
}

首先會(huì)通過 zone_page_state 來獲取當(dāng)前 zone 中剩余空閑內(nèi)存頁的總體容量 free_pages。

筆者在 《深入理解 Linux 物理內(nèi)存管理》的 “ 5. 內(nèi)核如何管理 NUMA 節(jié)點(diǎn)中的物理內(nèi)存區(qū)域 ” 小節(jié)中為大家介紹 struct zone 結(jié)構(gòu)體的時(shí)候提過，每個(gè)內(nèi)存區(qū)域 zone 里有一個(gè) vm_stat 用來存放與 zone 相關(guān)的各種統(tǒng)計(jì)變量。

structzone{
//該內(nèi)存區(qū)域內(nèi)存使用的統(tǒng)計(jì)信息
atomic_long_tvm_stat[NR_VM_ZONE_STAT_ITEMS];
}

內(nèi)核可以通過 zone_page_state 來訪問 vm_stat 從而獲取對(duì)應(yīng)的統(tǒng)計(jì)量，free_pages 就是其中的一個(gè)統(tǒng)計(jì)變量。但是這里大家需要注意的是 free_pages 表示的當(dāng)前 zone 里剩余空閑內(nèi)存頁的一個(gè)總量，是一個(gè)全集的概念。其中還包括了內(nèi)存區(qū)域的預(yù)留內(nèi)存 lowmem_reserve 以及為 highatomic 預(yù)留的緊急內(nèi)存。這些預(yù)留內(nèi)存都有自己特定的用途，普通內(nèi)存的申請(qǐng)不會(huì)用到預(yù)留內(nèi)存。

流程如果進(jìn)入到 if (!order) 分支的話表示本次內(nèi)存分配只是申請(qǐng)一個(gè)（order = 0）空閑的內(nèi)存頁，在這里會(huì)快速的檢測(cè)相關(guān)水位線情況是否滿足，如果滿足就會(huì)快速返回。

這里涉及到兩個(gè)重要的局部變量，筆者需要向大家交代一下：

• usable_free：表示可供本次內(nèi)存分配使用的空閑內(nèi)存頁總量。前邊我們提到 free_pages 表示的是剩余空閑內(nèi)存頁的一個(gè)全集，里邊還包括很多不能進(jìn)行普通內(nèi)存分配的空閑內(nèi)存頁，比如預(yù)留內(nèi)存和緊急內(nèi)存。

• reserved：表示本次內(nèi)存分配不能使用到的空閑內(nèi)存頁數(shù)量，這一部分的內(nèi)存頁數(shù)量計(jì)算是通過 __zone_watermark_unusable_free 函數(shù)完成的。最后使用 free_pages 減去 reserved 就可以得到真正的 usable_free 。

staticinlinelong__zone_watermark_unusable_free(structzone*z,
unsignedintorder,unsignedintalloc_flags)
{
//ALLOC_HARDER的設(shè)置表示可以使用high-atomic緊急預(yù)留內(nèi)存
constboolalloc_harder=(alloc_flags&(ALLOC_HARDER|ALLOC_OOM));
longunusable_free=(1<1;
//如果沒有設(shè)置ALLOC_HARDER則不能使用high_atomic緊急預(yù)留內(nèi)存
if(likely(!alloc_harder))
//不可用內(nèi)存的數(shù)量需要統(tǒng)計(jì)上high-atomic這部分內(nèi)存
unusable_free+=z->nr_reserved_highatomic;

#ifdefCONFIG_CMA
//如果沒有設(shè)置ALLOC_CMA則表示本次內(nèi)存分配不能從CMA區(qū)域獲取
if(!(alloc_flags&ALLOC_CMA))
//不可用內(nèi)存的數(shù)量需要統(tǒng)計(jì)上CMA區(qū)域中的空閑內(nèi)存頁
unusable_free+=zone_page_state(z,NR_FREE_CMA_PAGES);
#endif
//返回不可用內(nèi)存的數(shù)量，表示本次內(nèi)存分配不能使用的內(nèi)存容量
returnunusable_free;
}

如果 usable_free > mark + z->lowmem_reserve[highest_zoneidx] 條件為 true 表示當(dāng)前可用剩余內(nèi)存頁容量在水位線 mark 之上，可以進(jìn)行內(nèi)存分配，返回 true。

我們?cè)?《深入理解 Linux 物理內(nèi)存管理》的 " 5.2 物理內(nèi)存區(qū)域中的水位線 " 小節(jié)中介紹水位線相關(guān)的計(jì)算邏輯的時(shí)候提過，水位線的計(jì)算是需要刨去 lowmem_reserve 預(yù)留內(nèi)存的，也就是水位線的值并不包含 lowmem_reserve 內(nèi)存在內(nèi)。

所以這里在判斷可用內(nèi)存是否滿足水位線的關(guān)系時(shí)需要加上這部分 lowmem_reserve ，才能得到正確的結(jié)果。

如果本次內(nèi)存分配申請(qǐng)的是高階內(nèi)存塊（ order > 0），則會(huì)進(jìn)入 __zone_watermark_ok 函數(shù)中，近一步判斷伙伴系統(tǒng)中是否有足夠的高階內(nèi)存塊能夠滿足 order 階的內(nèi)存分配：

bool__zone_watermark_ok(structzone*z,unsignedintorder,unsignedlongmark,
inthighest_zoneidx,unsignedintalloc_flags,
longfree_pages)
{
//保證內(nèi)存分配順利進(jìn)行的最低水位線
longmin=mark;
into;
constboolalloc_harder=(alloc_flags&(ALLOC_HARDER|ALLOC_OOM));

//獲取真正可用的剩余空閑內(nèi)存頁數(shù)量
free_pages-=__zone_watermark_unusable_free(z,order,alloc_flags);

//如果設(shè)置了ALLOC_HIGH則水位線降低二分之一，使內(nèi)存分配更加努力激進(jìn)一些
if(alloc_flags&ALLOC_HIGH)
min-=min/2;

if(unlikely(alloc_harder)){
//在要進(jìn)行OOM的情況下內(nèi)存分配會(huì)比普通的ALLOC_HARDER策略更加努力激進(jìn)一些，所以這里水位線會(huì)降低二分之一
if(alloc_flags&ALLOC_OOM)
min-=min/2;
else
//ALLOC_HARDER策略下水位線只會(huì)降低四分之一
min-=min/4;
}

//檢查當(dāng)前可用剩余內(nèi)存是否在指定水位線之上。
//內(nèi)存的分配必須保證可用剩余內(nèi)存容量在指定水位線之上，否則不能進(jìn)行內(nèi)存分配
if(free_pages<=?min?+?z->lowmem_reserve[highest_zoneidx])
returnfalse;

//流程走到這里，對(duì)應(yīng)內(nèi)存分配階order=0的情況下就已經(jīng)OK了
//剩余空閑內(nèi)存在水位線之上，那么肯定能夠分配一頁出來
if(!order)
returntrue;

//但是對(duì)于high-order的內(nèi)存分配，這里還需要近一步檢查伙伴系統(tǒng)
//根據(jù)伙伴系統(tǒng)內(nèi)存分配的原理，這里需要檢查高階free_list中是否有足夠的空閑內(nèi)存塊可供分配
for(o=order;o//從當(dāng)前分配階order對(duì)應(yīng)的free_area中檢查是否有足夠的內(nèi)存塊
structfree_area*area=&z->free_area[o];
intmt;
//如果當(dāng)前free_area中的nr_free=0表示對(duì)應(yīng)free_list中沒有合適的空閑內(nèi)存塊
//那么繼續(xù)到高階free_area中查找
if(!area->nr_free)
continue;
//檢查free_area中所有的遷移類型free_list是否有足夠的內(nèi)存塊
for(mt=0;mtif(!free_area_empty(area,mt))
returntrue;
}

#ifdefCONFIG_CMA
//如果內(nèi)存分配指定需要從CMA區(qū)域中分配連續(xù)內(nèi)存
//那么就需要檢查MIGRATE_CMA對(duì)應(yīng)的free_list是否是空
if((alloc_flags&ALLOC_CMA)&&
!free_area_empty(area,MIGRATE_CMA)){
returntrue;
}
#endif
//如果設(shè)置了ALLOC_HARDER，則表示可以從HIGHATOMIC區(qū)中的緊急預(yù)留內(nèi)存中分配，檢查對(duì)應(yīng)free_list
if(alloc_harder&&!free_area_empty(area,MIGRATE_HIGHATOMIC))
returntrue;
}
//伙伴系統(tǒng)中的剩余內(nèi)存塊無法滿足order階的內(nèi)存分配
returnfalse;
}

在 __zone_watermark_ok 函數(shù)的開始需要計(jì)算出真正可用的剩余內(nèi)存 free_pages 。

//獲取真正可用的剩余空閑內(nèi)存頁數(shù)量
free_pages-=__zone_watermark_unusable_free(z,order,alloc_flags);

緊接著內(nèi)核會(huì)根據(jù) ALLOC_HIGH 以及 ALLOC_HARDER 標(biāo)識(shí)來決定是否降低水位線的要求。在 《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 一文中的 “3.1 內(nèi)存分配行為標(biāo)識(shí)掩碼 ALLOC_* ” 小節(jié)中筆者曾詳細(xì)的為大家介紹過這些 ALLOC_* 相關(guān)的掩碼，當(dāng)時(shí)筆者提了一句，當(dāng)內(nèi)存分配策略設(shè)置為 ALLOC_HIGH 或者 ALLOC_HARDER 時(shí)，會(huì)使內(nèi)存分配更加的激進(jìn)，努力一些。

當(dāng)時(shí)大家可能會(huì)比較懵，怎樣才算是激進(jìn)？怎樣才算是努力呢？

其實(shí)答案就在這里，當(dāng)內(nèi)存分配策略 alloc_flags 設(shè)置了 ALLOC_HARDER 時(shí)，水位線的要求會(huì)降低原來的四分之一，相當(dāng)于放款了內(nèi)存分配的限制。比原來更加努力使內(nèi)存分配成功。

當(dāng)內(nèi)存分配策略 alloc_flags 設(shè)置了 ALLOC_HIGH 時(shí)，水位線的要求會(huì)降低原來的二分之一，相當(dāng)于更近一步放款了內(nèi)存分配的限制。比原來更加激進(jìn)些。

在調(diào)整完水位線之后，還是一樣的邏輯，需要判斷當(dāng)前可用剩余內(nèi)存容量是否在水位線之上，如果是，則水位線檢查完畢符合內(nèi)存分配的要求。如果不是，則返回 false 不能進(jìn)行內(nèi)存分配。

//內(nèi)存的分配必須保證可用剩余內(nèi)存容量在指定水位線之上，否則不能進(jìn)行內(nèi)存分配
free_pages<=?min?+?z->lowmem_reserve[highest_zoneidx])

在水位線 OK 之后，對(duì)于 order = 0 的內(nèi)存分配情形下，就已經(jīng) OK 了，可以放心直接進(jìn)行內(nèi)存分配了。

但是對(duì)于 high-order 的內(nèi)存分配情形，這里還需要近一步檢查伙伴系統(tǒng)是否有足夠的空閑內(nèi)存塊可以滿足本次 high-order 的內(nèi)存分配。

根據(jù)本文 《3. 伙伴系統(tǒng)的內(nèi)存分配原理》小節(jié)中，為大家介紹的伙伴系統(tǒng)內(nèi)存分配原理，內(nèi)核需要從當(dāng)前分配階 order 開始一直向高階 free_area 中查找對(duì)應(yīng)的 free_list 中是否有足夠的內(nèi)存塊滿足 order 階的內(nèi)存分配要求。

• 如果有，那么水位線相關(guān)的校驗(yàn)工作到此結(jié)束，內(nèi)核會(huì)直接去伙伴系統(tǒng)中申請(qǐng) order 階的內(nèi)存塊。

• 如果沒有，則水位線校驗(yàn)失敗，伙伴系統(tǒng)無法滿足本次的內(nèi)存分配要求。

image.png

5.3 內(nèi)存分配成功之后初始化 page

經(jīng)過 zone_watermark_ok 的校驗(yàn)，現(xiàn)在內(nèi)存水位線符合內(nèi)存分配的要求，并且伙伴系統(tǒng)中有足夠的空閑內(nèi)存塊可供內(nèi)存分配申請(qǐng)，現(xiàn)在可以放心調(diào)用 rmqueue 函數(shù)進(jìn)入伙伴系統(tǒng)進(jìn)行內(nèi)存分配了。

rmqueue 函數(shù)封裝的正是伙伴系統(tǒng)的核心邏輯，這一部分的源碼實(shí)現(xiàn)筆者放在下一小節(jié)中介紹，這里我們先關(guān)注內(nèi)存分配成功之后，對(duì)于內(nèi)存頁 page 的初始化邏輯。

當(dāng)通過 rmqueue 函數(shù)從伙伴系統(tǒng)中成功申請(qǐng)到分配階為 order 大小的內(nèi)存塊時(shí)，內(nèi)核需要調(diào)用 prep_new_page 函數(shù)初始化這部分內(nèi)存塊，之后才能返回給進(jìn)程使用。

staticvoidprep_new_page(structpage*page,unsignedintorder,gfp_tgfp_flags,
unsignedintalloc_flags)
{
//初始化structpage，清除一些頁面屬性標(biāo)記
post_alloc_hook(page,order,gfp_flags);

//設(shè)置復(fù)合頁
if(order&&(gfp_flags&__GFP_COMP))
prep_compound_page(page,order);

if(alloc_flags&ALLOC_NO_WATERMARKS)
//使用set_page_XXX(page)方法設(shè)置page的PG_XXX標(biāo)志位
set_page_pfmemalloc(page);
else
//使用clear_page_XXX(page)方法清除page的PG_XXX標(biāo)志位
clear_page_pfmemalloc(page);
}

5.3.1 初始化 struct page

由于現(xiàn)在我們拿到的 struct page 結(jié)構(gòu)是剛剛從伙伴系統(tǒng)中申請(qǐng)出來的，里面可能包含一些無用的標(biāo)記（上一次被使用過的，還沒清理），所以需要將這些無用標(biāo)記清理掉，并且在此基礎(chǔ)上根據(jù) gfp_flags 掩碼對(duì) struct page 進(jìn)行初始化的準(zhǔn)備工作。

比如通過 set_page_private 將 struct page 里的 private 指針?biāo)赶虻膬?nèi)容清空，private 指針在內(nèi)核中的使用比較復(fù)雜，它會(huì)在不同場(chǎng)景下指向不同的內(nèi)容。

set_page_private(page,0);

將頁面的使用計(jì)數(shù)設(shè)置為 1 ，表示當(dāng)前物理內(nèi)存頁正在被使用。

set_page_refcounted(page);

如果 gfp_flags 掩碼中設(shè)置了 ___GFP_ZERO，這時(shí)就需要將這些 page 初始化為零頁。

由于初始化頁面的準(zhǔn)備工作和本文的主線內(nèi)容并沒有多大的關(guān)聯(lián)，所以筆者這里只做簡(jiǎn)單介紹，大家大概了解一下初始化做了哪些準(zhǔn)備工作即可。

5.3.2 設(shè)置復(fù)合頁 compound_page

復(fù)合頁 compound_page 本質(zhì)上就是通過兩個(gè)或者多個(gè)物理上連續(xù)的內(nèi)存頁 page 組裝成的一個(gè)在邏輯上看起來比普通內(nèi)存頁 page 更大的頁。它底層的依賴本質(zhì)還是一個(gè)一個(gè)的普通內(nèi)存頁 page。

我們都知道 Linux 管理內(nèi)存的最小單位是 page，每個(gè) page 描述 4K 大小的物理內(nèi)存，但在一些內(nèi)核使用場(chǎng)景中，比如 slab 內(nèi)存池中，往往會(huì)向伙伴系統(tǒng)一次性申請(qǐng)多個(gè)普通內(nèi)存頁 page，然后將這些內(nèi)存頁 page 劃分為多個(gè)大小相同的小內(nèi)存塊，這些小內(nèi)存塊被 slab 內(nèi)存池統(tǒng)一管理。

slab 內(nèi)存池底層其實(shí)依賴的是多個(gè)普通內(nèi)存頁，但是內(nèi)核期望將這多個(gè)內(nèi)存頁統(tǒng)一成一個(gè)邏輯上的內(nèi)存頁來統(tǒng)一管理，這個(gè)邏輯上的內(nèi)存頁就是本小節(jié)要介紹的復(fù)合頁。

而在 Linux 內(nèi)存管理的架構(gòu)中都是統(tǒng)一通過 struct page 來管理內(nèi)存，復(fù)合頁卻是通過兩個(gè)或者多個(gè)物理上連續(xù)的內(nèi)存頁 page 組裝成的一個(gè)邏輯頁，那么復(fù)合頁的管理與普通頁的管理如何統(tǒng)一呢？

這就引出了本小節(jié)的主題——復(fù)合頁 compound_page，下面我們就來看下 Linux 如果通過統(tǒng)一的 struct page 結(jié)構(gòu)來描述這些復(fù)合頁（compound_page）：

雖然復(fù)合頁（compound_page）是由多個(gè)物理上連續(xù)的普通 page 組成的，但是在內(nèi)核的視角里它還是被當(dāng)做一個(gè)特殊內(nèi)存頁來看待。

下圖所示，是由 4 個(gè)連續(xù)的普通內(nèi)存頁 page 組成的一個(gè) compound_page：

image.png

組成復(fù)合頁的第一個(gè) page 我們稱之為首頁（Head Page），其余的均稱之為尾頁（Tail Page）。

我們來看一下 struct page 中關(guān)于描述 compound_page 的相關(guān)字段：

structpage{
//首頁page中的flags會(huì)被設(shè)置為PG_head表示復(fù)合頁的第一頁
unsignedlongflags;
//其余尾頁會(huì)通過該字段指向首頁
unsignedlongcompound_head;
//用于釋放復(fù)合頁的析構(gòu)函數(shù)，保存在首頁中
unsignedcharcompound_dtor;
//該復(fù)合頁有多少個(gè)page組成，order還是分配階的概念，在首頁中保存
//本例中的order=2表示由4個(gè)普通頁組成
unsignedcharcompound_order;
//該復(fù)合頁被多少個(gè)進(jìn)程使用，內(nèi)存頁反向映射的概念，首頁中保存
atomic_tcompound_mapcount;
//復(fù)合頁使用計(jì)數(shù)，首頁中保存
atomic_tcompound_pincount;
}

首頁對(duì)應(yīng)的 struct page 結(jié)構(gòu)里的 flags 會(huì)被設(shè)置為 PG_head，表示這是復(fù)合頁的第一頁。

另外首頁中還保存關(guān)于復(fù)合頁的一些額外信息，比如：

• 用于釋放復(fù)合頁的析構(gòu)函數(shù)會(huì)保存在首頁 struct page 結(jié)構(gòu)里的 compound_dtor 字段中
• 復(fù)合頁的分配階 order 會(huì)保存在首頁中的 compound_order 中以及用于指示復(fù)合頁的引用計(jì)數(shù) compound_pincount，以及復(fù)合頁的反向映射個(gè)數(shù)（該復(fù)合頁被多少個(gè)進(jìn)程的頁表所映射）compound_mapcount 均在首頁中保存。

關(guān)于 struct page 的 flags 字段的介紹，以及內(nèi)存頁反向映射原理，大家可以回看下筆者 《深入理解 Linux 物理內(nèi)存管理》中的 “ 6.4 物理內(nèi)存頁屬性和狀態(tài)的標(biāo)志位 flag ” 和 “ 6.1 匿名頁的反向映射 ” 小節(jié)。

復(fù)合頁中的所有尾頁都會(huì)通過其對(duì)應(yīng)的 struct page 結(jié)構(gòu)中的 compound_head 指向首頁，這樣通過首頁和尾頁就組裝成了一個(gè)完整的復(fù)合頁 compound_page 。

image.png

在我們理解了 compound_page 的組織結(jié)構(gòu)之后，我們?cè)诨剡^頭來看 "6.3 內(nèi)存分配成功之后初始化 page" 小節(jié)中的 prep_new_page 函數(shù)：

當(dāng)內(nèi)核向伙伴系統(tǒng)申請(qǐng)復(fù)合頁 compound_page 的時(shí)候，會(huì)在 gfp_flags 掩碼中設(shè)置 __GFP_COMP 標(biāo)識(shí)，表次本次內(nèi)存分配要分配一個(gè)復(fù)合頁，復(fù)合頁中的 page 個(gè)數(shù)由分配階 order 決定。

當(dāng)內(nèi)核向伙伴系統(tǒng)申請(qǐng)了 2 ^ order 個(gè)內(nèi)存頁 page 時(shí)，大家注意在伙伴系統(tǒng)的視角中內(nèi)存還是一頁一頁的，伙伴系統(tǒng)并不知道有復(fù)合頁的存在，當(dāng)我們申請(qǐng)成功之后，需要在 prep_new_page 函數(shù)中將這 2 ^ order 個(gè)內(nèi)存頁 page 按照前面介紹的邏輯組裝成一個(gè) 復(fù)合頁 compound_page。

voidprep_compound_page(structpage*page,unsignedintorder)
{
inti;
intnr_pages=1<//設(shè)置首頁page中的flags為PG_head
__SetPageHead(page);
//首頁之后的page全部是尾頁，循環(huán)遍歷設(shè)置尾頁
for(i=1;i//最后設(shè)置首頁相關(guān)屬性
prep_compound_head(page,order);
}

staticvoidprep_compound_tail(structpage*head,inttail_idx)
{
//由于復(fù)合頁中的page全部是連續(xù)的，直接使用偏移即可獲得對(duì)應(yīng)尾頁
structpage*p=head+tail_idx;
//設(shè)置尾頁標(biāo)識(shí)
p->mapping=TAIL_MAPPING;
//尾頁page結(jié)構(gòu)中的compound_head指向首頁
set_compound_head(p,head);
}

static__always_inlinevoidset_compound_head(structpage*page,structpage*head)
{
WRITE_ONCE(page->compound_head,(unsignedlong)head+1);
}

staticvoidprep_compound_head(structpage*page,unsignedintorder)
{
//設(shè)置首頁相關(guān)屬性
set_compound_page_dtor(page,COMPOUND_PAGE_DTOR);
set_compound_order(page,order);
atomic_set(compound_mapcount_ptr(page),-1);
atomic_set(compound_pincount_ptr(page),0);
}

6. 伙伴系統(tǒng)的實(shí)現(xiàn)

image.png

現(xiàn)在內(nèi)核通過前邊介紹的 get_page_from_freelist 函數(shù)，循環(huán)遍歷 zonelist 終于找到了符合內(nèi)存分配條件的物理內(nèi)存區(qū)域 zone。接下來就會(huì)通過 rmqueue 函數(shù)進(jìn)入到該物理內(nèi)存區(qū)域 zone 對(duì)應(yīng)的伙伴系統(tǒng)中實(shí)際分配物理內(nèi)存。

image.png

/*
*Allocateapagefromthegivenzone.Usepcplistsfororder-0allocations.
*/
staticinline
structpage*rmqueue(structzone*preferred_zone,
structzone*zone,unsignedintorder,
gfp_tgfp_flags,unsignedintalloc_flags,
intmigratetype)
{
unsignedlongflags;
structpage*page;

if(likely(order==0)){
//當(dāng)我們申請(qǐng)一個(gè)物理頁面（order=0）時(shí)，內(nèi)核首先會(huì)從CPU高速緩存列表pcplist中直接分配，而不會(huì)走伙伴系統(tǒng)，提高內(nèi)存分配速度
page=rmqueue_pcplist(preferred_zone,zone,gfp_flags,
migratetype,alloc_flags);
gotoout;
}
//加鎖并關(guān)閉中斷，防止并發(fā)訪問
spin_lock_irqsave(&zone->lock,flags);

//當(dāng)申請(qǐng)頁面超過一個(gè)（order>0）時(shí)，則從伙伴系統(tǒng)中進(jìn)行分配
do{
page=NULL;
if(alloc_flags&ALLOC_HARDER){
//如果設(shè)置了ALLOC_HARDER分配策略，則從伙伴系統(tǒng)的HIGHATOMIC遷移類型的freelist中獲取
page=__rmqueue_smallest(zone,order,MIGRATE_HIGHATOMIC);
}
if(!page)
//從伙伴系統(tǒng)中申請(qǐng)分配階order大小的物理內(nèi)存塊
page=__rmqueue(zone,order,migratetype,alloc_flags);
}while(page&&check_new_pages(page,order));
//解鎖
spin_unlock(&zone->lock);
if(!page)
gotofailed;
//重新統(tǒng)計(jì)內(nèi)存區(qū)域中的相關(guān)統(tǒng)計(jì)指標(biāo)
zone_statistics(preferred_zone,zone);
//打開中斷
local_irq_restore(flags);

out:
returnpage;

failed:
//分配失敗
local_irq_restore(flags);
returnNULL;
}

6.1 從 CPU 高速緩存列表中獲取內(nèi)存頁

內(nèi)核對(duì)只分配一頁物理內(nèi)存的情況做了特殊處理，當(dāng)只請(qǐng)求一頁內(nèi)存時(shí)，內(nèi)核會(huì)借助 CPU 高速緩存冷熱頁列表 pcplist 加速內(nèi)存分配的處理，此時(shí)分配的內(nèi)存頁將來自于 pcplist 而不是伙伴系統(tǒng)。

pcp 是 per_cpu_pageset 的縮寫，內(nèi)核會(huì)為每個(gè) CPU 分配一個(gè)高速緩存列表，關(guān)于這部分內(nèi)容，筆者已經(jīng)在 《深入理解 Linux 物理內(nèi)存管理》一文中的 “ 5.7 物理內(nèi)存區(qū)域中的冷熱頁 ” 小節(jié)非常詳細(xì)的為大家介紹過了，忘記的同學(xué)可以在回看下。

在 NUMA 內(nèi)存架構(gòu)下，每個(gè)物理內(nèi)存區(qū)域都?xì)w屬于一個(gè)特定的 NUMA 節(jié)點(diǎn)，NUMA 節(jié)點(diǎn)中包含了一個(gè)或者多個(gè) CPU，NUMA 節(jié)點(diǎn)中的每個(gè)內(nèi)存區(qū)域會(huì)關(guān)聯(lián)到一個(gè)特定的 CPU 上.

而每個(gè) CPU 都有自己獨(dú)立的高速緩存，所以每個(gè) CPU 對(duì)應(yīng)一個(gè) per_cpu_pageset 結(jié)構(gòu)，用于管理這個(gè) CPU 高速緩存中的冷熱頁。

所謂的熱頁就是已經(jīng)加載進(jìn) CPU 高速緩存中的物理內(nèi)存頁，所謂的冷頁就是還未加載進(jìn) CPU 高速緩存中的物理內(nèi)存頁，冷頁是熱頁的后備選項(xiàng)

每個(gè) CPU 都可以訪問系統(tǒng)中的所有物理內(nèi)存頁，盡管訪問速度不同，因此特定的物理內(nèi)存區(qū)域 struct zone 不僅要考慮到所屬 NUMA 節(jié)點(diǎn)中相關(guān)的 CPU，還需要照顧到系統(tǒng)中的其他 CPU。

在 Linux 內(nèi)核中，系統(tǒng)會(huì)經(jīng)常請(qǐng)求和釋放單個(gè)頁面。如果針對(duì)每個(gè) CPU，都為其預(yù)先分配一個(gè)用于緩存單個(gè)內(nèi)存頁面的高速緩存頁列表，用于滿足本地 CPU 發(fā)出的單頁內(nèi)存請(qǐng)求，就能提升系統(tǒng)的性能。所以在 struct zone 結(jié)構(gòu)中持有了系統(tǒng)中所有 CPU 的高速緩存頁列表 per_cpu_pageset。

structzone{
structper_cpu_pages__percpu*per_cpu_pageset;
}

structper_cpu_pages{
intcount;/*pcplist里的頁面總數(shù)*/
inthigh;/*pcplist里的高水位線，count超過high時(shí)，內(nèi)核會(huì)釋放batch個(gè)頁面到伙伴系統(tǒng)中*/
intbatch;/*pcplist里的頁面來自于伙伴系統(tǒng)，batch定義了每次從伙伴系統(tǒng)獲取或者歸還多少個(gè)頁面*/

//CPU高速緩存列表pcplist，每個(gè)遷移類型對(duì)應(yīng)一個(gè)pcplist
structlist_headlists[NR_PCP_LISTS];
};

當(dāng)內(nèi)核嘗試從 pcplist 中獲取一個(gè)物理內(nèi)存頁時(shí)，會(huì)首先獲取運(yùn)行當(dāng)前進(jìn)程的 CPU 對(duì)應(yīng)的高速緩存列表 pcplist。然后根據(jù)指定的具體頁面遷移類型 migratetype 獲取對(duì)應(yīng)遷移類型的 pcplist。

當(dāng)獲取到符合條件的 pcplist 之后，內(nèi)核會(huì)調(diào)用 __rmqueue_pcplist 從 pcplist 中摘下一個(gè)物理內(nèi)存頁返回。

/*Lockandremovepagefromtheper-cpulist*/
staticstructpage*rmqueue_pcplist(structzone*preferred_zone,
structzone*zone,gfp_tgfp_flags,
intmigratetype,unsignedintalloc_flags)
{
structper_cpu_pages*pcp;
structlist_head*list;
structpage*page;
unsignedlongflags;
//關(guān)閉中斷
local_irq_save(flags);
//獲取運(yùn)行當(dāng)前進(jìn)程的CPU高速緩存列表pcplist
pcp=&this_cpu_ptr(zone->pageset)->pcp;
//獲取指定頁面遷移類型的pcplist
list=&pcp->lists[migratetype];
//從指定遷移類型的pcplist中移除一個(gè)頁面，用于內(nèi)存分配
page=__rmqueue_pcplist(zone,migratetype,alloc_flags,pcp,list);
if(page){
//統(tǒng)計(jì)內(nèi)存區(qū)域內(nèi)的相關(guān)信息
zone_statistics(preferred_zone,zone);
}
//開中斷
local_irq_restore(flags);
returnpage;
}

pcplist 中緩存的內(nèi)存頁面其實(shí)全部來自于伙伴系統(tǒng)，當(dāng) pcplist 中的頁面數(shù)量 count 為 0 （表示此時(shí) pcplist 里沒有緩存的頁面）時(shí)，內(nèi)核會(huì)調(diào)用 rmqueue_bulk 從伙伴系統(tǒng)中獲取 batch 個(gè)物理頁面添加到 pcplist，從伙伴系統(tǒng)中獲取頁面的過程參照本文 "3. 伙伴系統(tǒng)的內(nèi)存分配原理" 小節(jié)中的內(nèi)容。

隨后內(nèi)核會(huì)將 pcplist 中的第一個(gè)物理內(nèi)存頁從鏈表中摘下返回，count 計(jì)數(shù)減一。

/*Removepagefromtheper-cpulist,callermustprotectthelist*/
staticstructpage*__rmqueue_pcplist(structzone*zone,intmigratetype,
unsignedintalloc_flags,
structper_cpu_pages*pcp,
structlist_head*list)
{
structpage*page;

do{
//如果當(dāng)前pcplist中的頁面為空，那么則從伙伴系統(tǒng)中獲取batch個(gè)頁面放入pcplist中
if(list_empty(list)){
pcp->count+=rmqueue_bulk(zone,0,
pcp->batch,list,
migratetype,alloc_flags);
if(unlikely(list_empty(list)))
returnNULL;
}
//獲取pcplist上的第一個(gè)物理頁面
page=list_first_entry(list,structpage,lru);
//將該物理頁面從pcplist中摘除
list_del(&page->lru);
//pcplist中的count減一
pcp->count--;
}while(check_new_pcp(page));

returnpage;
}

6.2 從伙伴系統(tǒng)中獲取內(nèi)存頁

在本文 "3. 伙伴系統(tǒng)的內(nèi)存分配原理" 小節(jié)中筆者詳細(xì)為大家介紹了伙伴系統(tǒng)的整個(gè)內(nèi)存分配原理，那么在本小節(jié)中，我們將正式進(jìn)入伙伴系統(tǒng)中，來看下伙伴系統(tǒng)在內(nèi)核中是如何實(shí)現(xiàn)的。

在前面介紹的 rmqueue 函數(shù)中，涉及到伙伴系統(tǒng)入口函數(shù)的有兩個(gè)：

• __rmqueue_smallest 函數(shù)主要是封裝了整個(gè)伙伴系統(tǒng)關(guān)于內(nèi)存分配的核心流程，該函數(shù)中的代碼正是 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)所講的核心內(nèi)容。

• __rmqueue 函數(shù)封裝的是伙伴系統(tǒng)的整個(gè)完整流程，底層調(diào)用了 __rmqueue_smallest 函數(shù)，它主要實(shí)現(xiàn)的是當(dāng)伙伴系統(tǒng) free_area 中對(duì)應(yīng)的遷移列表 free_list[MIGRATE_TYPE] 無法滿足內(nèi)存分配需求時(shí)， 內(nèi)存分配在伙伴系統(tǒng)中的 fallback 流程。這一點(diǎn)筆者也在 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)中詳細(xì)介紹過了。

當(dāng)我們向內(nèi)核申請(qǐng)的內(nèi)存頁超過一頁（order > 0）時(shí)，內(nèi)核就會(huì)進(jìn)入伙伴系統(tǒng)中為我們申請(qǐng)內(nèi)存。

如果內(nèi)存分配策略 alloc_flags 指定了 ALLOC_HARDER 時(shí)，就會(huì)調(diào)用 __rmqueue_smallest 直接進(jìn)入伙伴系統(tǒng)，從 free_list[MIGRATE_HIGHATOMIC] 鏈表中分配 order 大小的物理內(nèi)存塊。

image.png

如果分配失敗或者 alloc_flags 沒有指定 ALLOC_HARDER 則會(huì)通過 __rmqueue 進(jìn)入伙伴系統(tǒng)，這里會(huì)處理分配失敗之后的 fallback 邏輯。

/*
*Thisarraydescribestheorderlistsarefallenbacktowhen
*thefreelistsforthedesirablemigratetypearedepleted
*
*Theothermigratetypesdonothavefallbacks.
*/
staticintfallbacks[MIGRATE_TYPES][3]={
[MIGRATE_UNMOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
[MIGRATE_MOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_UNMOVABLE,MIGRATE_TYPES},
[MIGRATE_RECLAIMABLE]={MIGRATE_UNMOVABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
};

6.2.1 __rmqueue_smallest 伙伴系統(tǒng)的核心實(shí)現(xiàn)

我們還是以 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)中，介紹伙伴系統(tǒng)內(nèi)存分配核心原理時(shí)，所舉的示例為大家剖析伙伴系統(tǒng)的核心源碼實(shí)現(xiàn)。

假設(shè)當(dāng)前伙伴系統(tǒng)中只有 order = 3 的空閑鏈表 free_area[3] ，其中只有一個(gè)空閑的內(nèi)存塊，包含了連續(xù)的 8 個(gè) page。其余剩下的分配階 order 對(duì)應(yīng)的空閑鏈表中均是空的。

image.png

現(xiàn)在我們向伙伴系統(tǒng)申請(qǐng)一個(gè) page 大小的內(nèi)存（對(duì)應(yīng)的分配階 order = 0），經(jīng)過前面的介紹我們知道當(dāng)申請(qǐng)一個(gè) page 大小的內(nèi)存時(shí)，內(nèi)核是從 pcplist 中進(jìn)行分配的，但是這里筆者為了方便給大家介紹伙伴系統(tǒng)，所以我們暫時(shí)讓它走伙伴系統(tǒng)的流程。

內(nèi)核會(huì)在伙伴系統(tǒng)中從當(dāng)前分配階 order 開始，依次遍歷 free_area[order] 里對(duì)應(yīng)的指定頁面遷移類型 free_list[MIGRATE_TYPE] 鏈表，直到找到一個(gè)合適尺寸的內(nèi)存塊為止。

image.png

在本示例中，內(nèi)核會(huì)在伙伴系統(tǒng)中首先查看 order = 0 對(duì)應(yīng)的空閑鏈表 free_area[0] 中是否有空閑內(nèi)存塊可供分配。如果有，則將該空閑內(nèi)存塊從 free_area[0] 摘下返回，內(nèi)存分配成功。

如果沒有，隨后內(nèi)核會(huì)根據(jù)前邊介紹的內(nèi)存分配邏輯，繼續(xù)升級(jí)到 free_area[1] , free_area[2] 鏈表中尋找空閑內(nèi)存塊，直到查找到 free_area[3] 發(fā)現(xiàn)有一個(gè)可供分配的內(nèi)存塊。這個(gè)內(nèi)存塊中包含了 8 個(gè)連續(xù)的空閑 page，然后將這 8 個(gè) 連續(xù)的空閑 page 組成的內(nèi)存塊依次進(jìn)行減半分裂，將每次分裂出來的后半部分內(nèi)存塊插入到對(duì)應(yīng)尺寸的 free_area 中，如下圖所示：

image.png

/*
*Gothroughthefreelistsforthegivenmigratetypeandremove
*thesmallestavailablepagefromthefreelists
*/
static__always_inline
structpage*__rmqueue_smallest(structzone*zone,unsignedintorder,
intmigratetype)
{
unsignedintcurrent_order;
structfree_area*area;
structpage*page;

/*從當(dāng)前分配階order開始在伙伴系統(tǒng)對(duì)應(yīng)的free_area[order]里查找合適尺寸的內(nèi)存塊*/
for(current_order=order;current_order//獲取當(dāng)前order在伙伴系統(tǒng)中對(duì)應(yīng)的free_area[order]
//對(duì)應(yīng)上圖free_area[3]
area=&(zone->free_area[current_order]);
//從free_area[order]中對(duì)應(yīng)的free_list[MIGRATE_TYPE]鏈表中獲取空閑內(nèi)存塊
page=get_page_from_free_area(area,migratetype);
if(!page)
//如果當(dāng)前free_area[order]中沒有空閑內(nèi)存塊則繼續(xù)向上查找
//對(duì)應(yīng)上圖free_area[0]，free_area[1]，free_area[2]
continue;
//如果在當(dāng)前free_area[order]中找到空閑內(nèi)存塊，則從free_list[MIGRATE_TYPE]鏈表中摘除
//對(duì)應(yīng)上圖步驟1：將內(nèi)存塊從free_area[3]中摘除
del_page_from_free_area(page,area);
//將摘下來的內(nèi)存塊進(jìn)行減半分裂并插入對(duì)應(yīng)的尺寸的free_area中
//對(duì)應(yīng)上圖步驟[2,3],[4,5],[6,7]
expand(zone,page,order,current_order,area,migratetype);
//設(shè)置頁面的遷移類型
set_pcppage_migratetype(page,migratetype);
//內(nèi)存分配成功返回，對(duì)應(yīng)上圖步驟8
returnpage;
}
//內(nèi)存分配失敗返回null
returnNULL;
}

下面我們來看下減半分裂過程的實(shí)現(xiàn)，expand 函數(shù)中的參數(shù)在本節(jié)示例中：low = 指定分配階 order = 0，high = 最后遍歷到的分配階 order = 3。

staticinlinevoidexpand(structzone*zone,structpage*page,
intlow,inthigh,structfree_area*area,
intmigratetype)
{
//size=8，表示當(dāng)前要進(jìn)行減半分裂的內(nèi)存塊是由8個(gè)連續(xù)page組成的。
//剛剛從free_area[3]上摘下
unsignedlongsize=1<//依次進(jìn)行減半分裂，直到分裂出指定order的內(nèi)存塊出來
//對(duì)應(yīng)上圖中的步驟2，4，6
//初始high=3,low=0
while(high>low){
//free_area要降到下一階，此時(shí)變?yōu)閒ree_area[2]
area--;
//分配階要降級(jí)high=2
high--;
//內(nèi)存塊尺寸要減半，由8變成4，表示要分裂出由4個(gè)連續(xù)page組成的兩個(gè)內(nèi)存塊。
//參考上圖中的步驟2
size>>=1;
//標(biāo)記為保護(hù)頁，當(dāng)其伙伴被釋放時(shí)，允許合并，參見《4.伙伴系統(tǒng)的內(nèi)存回收原理》小節(jié)
if(set_page_guard(zone,&page[size],high,migratetype))
continue;
//將本次減半分裂出來的第二個(gè)內(nèi)存塊插入到對(duì)應(yīng)free_area[high]中
//參見上圖步驟3，5，7
add_to_free_area(&page[size],area,migratetype);
//設(shè)置內(nèi)存塊的分配階high
set_page_order(&page[size],high);

//本次分裂出來的第一個(gè)內(nèi)存塊繼續(xù)循環(huán)進(jìn)行減半分裂直到high=low
//即已經(jīng)分裂出來了指定order尺寸的內(nèi)存塊無需在進(jìn)行分裂了，直接返回
//參見上圖步驟2，4，6
}
}

6.2.2 __rmqueue 伙伴系統(tǒng)的 fallback 實(shí)現(xiàn)

當(dāng)我們向內(nèi)核申請(qǐng)的內(nèi)存頁面超過一頁（order > 0 ），并且內(nèi)存分配策略 alloc_flags 中并沒有設(shè)置 ALLOC_HARDER 的時(shí)候，內(nèi)存分配流程就會(huì)進(jìn)入 __rmqueue 走常規(guī)的伙伴系統(tǒng)分配流程。

static__always_inlinestructpage*
__rmqueue(structzone*zone,unsignedintorder,intmigratetype,
unsignedintalloc_flags)
{
structpage*page;

retry:
//首先進(jìn)入伙伴系統(tǒng)到指定頁面遷移類型的free_list[migratetype]獲取空閑內(nèi)存塊
//這里走的就是上小節(jié)中介紹的伙伴系統(tǒng)核心流程
page=__rmqueue_smallest(zone,order,migratetype);
if(unlikely(!page)){

.....當(dāng)伙伴系統(tǒng)中沒有足夠指定遷移類型migratetype的空閑內(nèi)存塊時(shí)，就會(huì)進(jìn)入這個(gè)分支.....

//如果遷移類型是MIGRATE_MOVABLE則優(yōu)先fallback到CMA區(qū)中分配內(nèi)存
if(migratetype==MIGRATE_MOVABLE)
page=__rmqueue_cma_fallback(zone,order);
//走常規(guī)的伙伴系統(tǒng)fallback流程，核心原理參見《3.伙伴系統(tǒng)的內(nèi)存分配原理》小節(jié)
if(!page&&__rmqueue_fallback(zone,order,migratetype,
alloc_flags))
gotoretry;
}
//內(nèi)存分配成功
returnpage;
}

從上述 __rmqueue 函數(shù)的源碼實(shí)現(xiàn)中我們可以看出，該函數(shù)處理了伙伴系統(tǒng)內(nèi)存分配的異常流程，即調(diào)用 __rmqueue_smallest 進(jìn)入伙伴系統(tǒng)分配內(nèi)存時(shí)，發(fā)現(xiàn)伙伴系統(tǒng)各個(gè)分配階 free_area[order] 中對(duì)應(yīng)的遷移列表 free_list[MIGRATE_TYPE] 無法滿足內(nèi)存分配需求時(shí)，__rmqueue_smallest 函數(shù)就會(huì)返回 null，伙伴系統(tǒng)內(nèi)存分配失敗。

隨后內(nèi)核就會(huì)進(jìn)入伙伴系統(tǒng)的 fallback 流程，這里對(duì) MIGRATE_MOVABLE 遷移類型做了一下特殊處理，當(dāng)伙伴系統(tǒng)中 free_list[MIGRATE_MOVABLE] 沒有足夠空閑內(nèi)存塊時(shí)，會(huì)優(yōu)先降級(jí)到 CMA 區(qū)域內(nèi)進(jìn)行分配。

static__always_inlinestructpage*__rmqueue_cma_fallback(structzone*zone,
unsignedintorder)
{
return__rmqueue_smallest(zone,order,MIGRATE_CMA);
}

image.png

如果我們指定的頁面遷移類型并非 MIGRATE_MOVABLE 或者降級(jí) CMA 之后仍然分配失敗，內(nèi)核就會(huì)進(jìn)入 __rmqueue_fallback 走常規(guī)的 fallback 流程，該函數(shù)封裝的正是筆者在 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)的后半部分介紹的 fallback 邏輯：

在 __rmqueue_fallback 函數(shù)中，內(nèi)核會(huì)根據(jù)預(yù)先定義的相關(guān) fallback 規(guī)則開啟內(nèi)存分配的 fallback 流程。fallback 規(guī)則在內(nèi)核中用一個(gè) int 類型的二維數(shù)組表示，其中第一維表示需要進(jìn)行 fallback 的頁面遷移類型，第二維表示 fallback 的優(yōu)先級(jí)。后續(xù)內(nèi)核會(huì)按照這個(gè)優(yōu)先級(jí) fallback 到具體的 free_list[fallback_migratetype] 中去分配內(nèi)存。

staticintfallbacks[MIGRATE_TYPES][3]={
[MIGRATE_UNMOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
[MIGRATE_MOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_UNMOVABLE,MIGRATE_TYPES},
[MIGRATE_RECLAIMABLE]={MIGRATE_UNMOVABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
};

比如：MIGRATE_UNMOVABLE 類型的 free_list 內(nèi)存不足時(shí)，內(nèi)核會(huì) fallback 到 MIGRATE_RECLAIMABLE 中去獲取，如果還是不足，則再次降級(jí)到 MIGRATE_MOVABLE 中獲取，如果仍然無法滿足內(nèi)存分配，才會(huì)失敗退出。

static__always_inlinebool
__rmqueue_fallback(structzone*zone,intorder,intstart_migratetype,
unsignedintalloc_flags)
{
//最終會(huì)fallback到伙伴系統(tǒng)的哪個(gè)free_area中分配內(nèi)存
structfree_area*area;
//fallback和正常的分配流程正好相反，是從最高階的free_area[MAX_ORDER-1]開始查找空閑內(nèi)存塊
intcurrent_order;
//最初指定的內(nèi)存分配階
intmin_order=order;
structpage*page;
//最終計(jì)算出fallback到哪個(gè)頁面遷移類型free_list上
intfallback_mt;
//是否可以從free_list[fallback]中竊取內(nèi)存塊到free_list[start_migratetype]中
//start_migratetype表示我們最初指定的頁面遷移類型
boolcan_steal;

//如果設(shè)置了ALLOC_NOFRAGMENT表示不希望引入內(nèi)存碎片
//在這種情況下內(nèi)核會(huì)更加傾向于分配一個(gè)盡可能大的內(nèi)存塊，避免向其他鏈表引入內(nèi)存碎片
if(alloc_flags&ALLOC_NOFRAGMENT)
//pageblock_order用于定義系統(tǒng)支持的巨型頁對(duì)應(yīng)的分配階
//默認(rèn)為最大分配階-1=9
min_order=pageblock_order;

//fallback內(nèi)存分配流程從最高階free_area開始查找空閑內(nèi)存塊（頁面遷移類型為fallback類型）
for(current_order=MAX_ORDER-1;current_order>=min_order;
--current_order){
//獲取伙伴系統(tǒng)中最高階的free_area
area=&(zone->free_area[current_order]);
//按照上述的內(nèi)存分配fallback規(guī)則查找最合適的fallback遷移類型
fallback_mt=find_suitable_fallback(area,current_order,
start_migratetype,false,&can_steal);
//如果沒有合適的fallback_mt，則繼續(xù)降級(jí)到下一個(gè)分配階free_area中查找
if(fallback_mt==-1)
continue;

//can_steal會(huì)在find_suitable_fallback的過程中被設(shè)置
//當(dāng)我們指定的頁面遷移類型為MIGRATE_MOVABLE并且無法從其他fallback遷移類型列表中竊取頁面can_steal=false時(shí)
//內(nèi)核會(huì)更加傾向于fallback分配最小的可用頁面，即尺寸和指定order最接近的頁面數(shù)量而不是尺寸最大的
//因?yàn)檫@里的條件是分配可移動(dòng)的頁面類型，天然可以避免永久內(nèi)存碎片，無需按照最大的尺寸分配
if(!can_steal&&start_migratetype==MIGRATE_MOVABLE
&¤t_order>order)
gotofind_smallest;
//can_steal=true，則開始從free_list[fallback]列表中竊取頁面
gotodo_steal;
}

returnfalse;

find_smallest:
//該分支目的在于尋找尺寸最貼近指定order大小的最小可用頁面
//從指定order開始fallback
for(current_order=order;current_orderfree_area[current_order]);
fallback_mt=find_suitable_fallback(area,current_order,
start_migratetype,false,&can_steal);
if(fallback_mt!=-1)
break;
}

do_steal:
//從上述流程獲取到的伙伴系統(tǒng)free_area中獲取free_list[fallback_mt]
page=get_page_from_free_area(area,fallback_mt);
//從free_list[fallback_mt]中竊取頁面到free_list[start_migratetype]中
steal_suitable_fallback(zone,page,alloc_flags,start_migratetype,
can_steal);
//返回到__rmqueue函數(shù)中進(jìn)行retry重試流程，此時(shí)free_list[start_migratetype]中已經(jīng)有足夠的內(nèi)存頁面可供分配了
returntrue;

}

從上述內(nèi)存分配 fallback 源碼實(shí)現(xiàn)中，我們可以看出內(nèi)存分配 fallback 流程正好和正常的分配流程相反：

• 伙伴系統(tǒng)正常內(nèi)存分配流程先是從低階到高階依次查找空閑內(nèi)存塊，然后將高階中的內(nèi)存塊依次減半分裂到低階 free_list 鏈表中。

• 伙伴系統(tǒng) fallback 內(nèi)存分配流程則是先從最高階開始查找，找到一塊空閑內(nèi)存塊之后，先遷移到最初指定的 free_list[start_migratetype] 鏈表中，然后在指定的 free_list[start_migratetype] 鏈表中執(zhí)行減半分裂。

6.2.3 fallback 核心邏輯實(shí)現(xiàn)

本小節(jié)我們來看下內(nèi)核定義的 fallback 規(guī)則具體的流程實(shí)現(xiàn)，fallback 規(guī)則定義如下，筆者在之前的章節(jié)中已經(jīng)多次提到過了，這里不在重復(fù)解釋，我們重點(diǎn)關(guān)注它的 fallback 流程實(shí)現(xiàn)。

staticintfallbacks[MIGRATE_TYPES][3]={
[MIGRATE_UNMOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
[MIGRATE_MOVABLE]={MIGRATE_RECLAIMABLE,MIGRATE_UNMOVABLE,MIGRATE_TYPES},
[MIGRATE_RECLAIMABLE]={MIGRATE_UNMOVABLE,MIGRATE_MOVABLE,MIGRATE_TYPES},
};

find_suitable_fallback 函數(shù)中封裝了頁面遷移類型整個(gè)的 fallback 過程：

1. fallback 規(guī)則定義在 fallbacks[MIGRATE_TYPES][3] 二維數(shù)組中，第一維表示要進(jìn)行 fallback 的頁面遷移類型 migratetype。第二維 migratetype 遷移類型可以 fallback 到哪些遷移類型中，這些可以 fallback 的頁面遷移類型按照優(yōu)先級(jí)排列。

2. 該函數(shù)的核心邏輯是在 for (i = 0;; i++) 循環(huán)中按照 fallbacks[migratetype][i] 數(shù)組定義的 fallback 優(yōu)先級(jí)，依次在 free_area[order] 中對(duì)應(yīng)的 free_list[fallback] 列表中查找是否有空閑的內(nèi)存塊。

image.png

3. 如果當(dāng)前 free_list[fallback] 列表中沒有空閑內(nèi)存塊，則繼續(xù)在 for 循環(huán)中降級(jí)到下一個(gè) fallback 頁面遷移類型中去查找，也就是 for 循環(huán)中的 fallbacks[migratetype][i] 。直到找到空閑內(nèi)存塊為止，否則返回 -1。

intfind_suitable_fallback(structfree_area*area,unsignedintorder,
intmigratetype,boolonly_stealable,bool*can_steal)
{
inti;
//最終選取的fallback頁面遷移類型
intfallback_mt;
//當(dāng)前free_area[order]中以無空閑頁面，則返回失敗
if(area->nr_free==0)
return-1;

*can_steal=false;
//按照fallback優(yōu)先級(jí)，循環(huán)在free_list[fallback]中查詢是否有空閑內(nèi)存塊
for(i=0;;i++){
//按照優(yōu)先級(jí)獲取fallback頁面遷移類型
fallback_mt=fallbacks[migratetype][i];
if(fallback_mt==MIGRATE_TYPES)
break;
//如果當(dāng)前free_list[fallback]為空則繼續(xù)循環(huán)降級(jí)查找
if(free_area_empty(area,fallback_mt))
continue;
//判斷是否可以從free_list[fallback]竊取頁面到指定free_list[migratetype]中
if(can_steal_fallback(order,migratetype))
*can_steal=true;

if(!only_stealable)
returnfallback_mt;

if(*can_steal)
returnfallback_mt;
}

return-1;
}

//這里竊取頁面的目的是從fallback類型的freelist中拿到一個(gè)高階的大內(nèi)存塊
//之所以要竊取盡可能大的內(nèi)存塊是為了避免引入內(nèi)存碎片
//但MIGRATE_MOVABLE類型的頁面本身就可以避免永久內(nèi)存碎片
//所以fallbackMIGRATE_MOVABLE類型的頁面時(shí)，會(huì)跳轉(zhuǎn)到find_smallest分支只需要選擇一個(gè)合適的fallback內(nèi)存塊即可
staticboolcan_steal_fallback(unsignedintorder,intstart_mt)
{
if(order>=pageblock_order)
returntrue;

if(order>=pageblock_order/2||
start_mt==MIGRATE_RECLAIMABLE||
start_mt==MIGRATE_UNMOVABLE||
page_group_by_mobility_disabled)
returntrue;
//跳轉(zhuǎn)到find_smallest分支選擇一個(gè)合適的fallback內(nèi)存塊
returnfalse;
}

can_steal_fallback 函數(shù)中定義了是否可以從 free_list[fallback] 竊取頁面到指定 free_list[migratetype] 中，邏輯如下：

1. 如果我們指定的內(nèi)存分配階 order 大于等于 pageblock_order，則返回 true。pageblock_order 表示系統(tǒng)中支持的巨型頁對(duì)應(yīng)的分配階，默認(rèn)為伙伴系統(tǒng)中的最大分配階減一，我們可以通過 cat /proc/pagetypeinfo 命令查看。

image.png

2. 如果我們指定的頁面遷移類型為 MIGRATE_RECLAIMABLE 或者 MIGRATE_UNMOVABLE，則不管我們要申請(qǐng)的頁面尺寸有多大，內(nèi)核都會(huì)允許竊取頁面 can_steal = true ，因?yàn)樗鼈冏罱K會(huì) fallback 到 MIGRATE_MOVABLE 可移動(dòng)頁面類型中，這樣造成內(nèi)存碎片的情況會(huì)少一些。

3. 當(dāng)內(nèi)核全局變量 page_group_by_mobility_disabled 設(shè)置為 1 時(shí)，則所有物理內(nèi)存頁面都是不可移動(dòng)的，這時(shí)內(nèi)核也允許竊取頁面。

在系統(tǒng)初始化期間，所有頁都被標(biāo)記為 MIGRATE_MOVABLE 可移動(dòng)的頁面類型，其他的頁面遷移類型都是后來通過 __rmqueue_fallback 竊取產(chǎn)生的。而是否能夠竊取 fallback 遷移類型列表中的頁面，就是本小節(jié)介紹的內(nèi)容。

7. 內(nèi)存釋放源碼實(shí)現(xiàn)

在 《深入理解 Linux 物理內(nèi)存分配全鏈路實(shí)現(xiàn)》 中的 “1. 內(nèi)核物理內(nèi)存分配接口” 小節(jié)中我們介紹了內(nèi)核分配物理內(nèi)存的相關(guān)接口：

structpage*alloc_pages(gfp_tgfp,unsignedintorder)
unsignedlong__get_free_pages(gfp_tgfp_mask,unsignedintorder)
unsignedlongget_zeroed_page(gfp_tgfp_mask)
unsignedlong__get_dma_pages(gfp_tgfp_mask,unsignedintorder)

內(nèi)核釋放物理內(nèi)存的相關(guān)接口，這也是本小節(jié)的重點(diǎn)：

void__free_pages(structpage*page,unsignedintorder);
voidfree_pages(unsignedlongaddr,unsignedintorder);

• __free_pages ： 同 alloc_pages 函數(shù)對(duì)應(yīng)，用于釋放 2 的 order 次冪個(gè)內(nèi)存頁，釋放的物理內(nèi)存區(qū)域起始地址由該區(qū)域中的第一個(gè) page 實(shí)例指針表示，也就是參數(shù)里的 struct page *page 指針。

void__free_pages(structpage*page,unsignedintorder)
{
if(put_page_testzero(page))
free_the_page(page,order);
}

• free_pages：同 __get_free_pages 函數(shù)對(duì)應(yīng)，與 __free_pages 函數(shù)的區(qū)別是在釋放物理內(nèi)存時(shí)，使用了虛擬內(nèi)存地址而不是 page 指針。

voidfree_pages(unsignedlongaddr,unsignedintorder)
{
if(addr!=0){
//校驗(yàn)虛擬內(nèi)存地址addr的有效性
VM_BUG_ON(!virt_addr_valid((void*)addr));
//將虛擬內(nèi)存地址addr轉(zhuǎn)換為page，最終還是調(diào)用__free_pages
__free_pages(virt_to_page((void*)addr),order);
}
}

在我們釋放內(nèi)存時(shí)需要非常謹(jǐn)慎小心，只能釋放屬于你自己的頁，傳遞了錯(cuò)誤的 struct page 指針或者錯(cuò)誤的虛擬內(nèi)存地址，或者傳遞錯(cuò)了 order 值都可能會(huì)導(dǎo)致系統(tǒng)的崩潰。在內(nèi)核空間中，內(nèi)核是完全信賴自己的，這點(diǎn)和用戶空間不同。

另外內(nèi)核也提供了 __free_page 和 free_page 兩個(gè)宏，專門用于釋放單個(gè)物理內(nèi)存頁。

#define__free_page(page)__free_pages((page),0)
#definefree_page(addr)free_pages((addr),0)

我們可以看出無論是內(nèi)核定義的這些用于釋放內(nèi)存的宏或是輔助函數(shù)，它們最終會(huì)調(diào)用 __free_pages，這里正是釋放內(nèi)存的核心所在。

image.png

staticinlinevoidfree_the_page(structpage*page,unsignedintorder)
{
if(order==0)
//如果釋放一頁的話，則直接釋放到CPU高速緩存列表pcplist中
free_unref_page(page);
else
//如果釋放多頁的話，則進(jìn)入伙伴系統(tǒng)回收這部分內(nèi)存
__free_pages_ok(page,order);
}

從這里我們看到伙伴系統(tǒng)回收內(nèi)存的流程和伙伴系統(tǒng)分配內(nèi)存的流程是一樣的，在最開始首先都會(huì)檢查本次釋放或者分配的是否只是一個(gè)物理內(nèi)存頁（order = 0），如果是則直接釋放到 CPU 高速緩存列表 pcplist 中。如果不是則將內(nèi)存釋放回伙伴系統(tǒng)中。

structzone{
structper_cpu_pages__percpu*per_cpu_pageset;
}

structper_cpu_pages{
intcount;/*pcplist里的頁面總數(shù)*/
inthigh;/*pcplist里的高水位線，count超過high時(shí)，內(nèi)核會(huì)釋放batch個(gè)頁面到伙伴系統(tǒng)中*/
intbatch;/*pcplist里的頁面來自于伙伴系統(tǒng)，batch定義了每次從伙伴系統(tǒng)獲取或者歸還多少個(gè)頁面*/

//CPU高速緩存列表pcplist，每個(gè)遷移類型對(duì)應(yīng)一個(gè)pcplist
structlist_headlists[NR_PCP_LISTS];
};

7.1 釋放內(nèi)存至 CPU 高速緩存列表 pcplist 中

/*
*Freea0-orderpage
*/
voidfree_unref_page(structpage*page)
{
unsignedlongflags;
//獲取要釋放的物理內(nèi)存頁對(duì)應(yīng)的物理頁號(hào)pfn
unsignedlongpfn=page_to_pfn(page);
//關(guān)閉中斷
local_irq_save(flags);
//釋放物理內(nèi)存頁至pcplist中
free_unref_page_commit(page,pfn);
//開啟中斷
local_irq_restore(flags);
}

首先內(nèi)核會(huì)通過 page_to_pfn 函數(shù)獲取要釋放內(nèi)存頁對(duì)應(yīng)的物理頁號(hào)，而物理頁號(hào) pfn 的計(jì)算邏輯會(huì)根據(jù)內(nèi)存模型的不同而不同，關(guān)于 page_to_pfn 在不同內(nèi)存模型下的計(jì)算邏輯，大家可以回看下筆者之前文章 《深入理解 Linux 物理內(nèi)存管理》中的 “ 2. 從 CPU 角度看物理內(nèi)存模型 ” 小節(jié)。

最后通過 free_unref_page_commit 函數(shù)將內(nèi)存頁釋放至 CPU 高速緩存列表 pcplist 中，這里大家需要注意的是在釋放的過程中是不會(huì)響應(yīng)中斷的。

staticvoidfree_unref_page_commit(structpage*page,unsignedlongpfn)
{
//獲取內(nèi)存頁所在物理內(nèi)存區(qū)域zone
structzone*zone=page_zone(page);
//運(yùn)行當(dāng)前進(jìn)程的CPU高速緩存列表pcplist
structper_cpu_pages*pcp;

//頁面的遷移類型
intmigratetype;
migratetype=get_pcppage_migratetype(page);

//內(nèi)核這里只會(huì)將UNMOVABLE,MOVABLE,RECLAIMABLE這三種頁面遷移類型放入pcplist中，其余的遷移類型均釋放回伙伴系統(tǒng)
if(migratetype>=MIGRATE_PCPTYPES){
if(unlikely(is_migrate_isolate(migratetype))){
//釋放回伙伴系統(tǒng)
free_one_page(zone,page,pfn,0,migratetype);
return;
}
//內(nèi)核這里會(huì)將HIGHATOMIC類型頁面當(dāng)做MIGRATE_MOVABLE類型處理
migratetype=MIGRATE_MOVABLE;
}
//獲取運(yùn)行當(dāng)前進(jìn)程的CPU高速緩存列表pcplist
pcp=&this_cpu_ptr(zone->pageset)->pcp;
//將要釋放的物理內(nèi)存頁添加到pcplist中
list_add(&page->lru,&pcp->lists[migratetype]);
//pcplist頁面計(jì)數(shù)加一
pcp->count++;
//如果pcp中的頁面總數(shù)超過了high水位線，則將pcp中的batch個(gè)頁面釋放回伙伴系統(tǒng)中
if(pcp->count>=pcp->high){
unsignedlongbatch=READ_ONCE(pcp->batch);
//釋放batch個(gè)頁面回伙伴系統(tǒng)中
free_pcppages_bulk(zone,batch,pcp);
}
}

這里筆者需要強(qiáng)調(diào)的是，內(nèi)核只會(huì)將 UNMOVABLE，MOVABLE，RECLAIMABLE 這三種頁面遷移類型放入 CPU 高速緩存列表 pcplist 中，其余的遷移類型均需釋放回伙伴系統(tǒng)。

enummigratetype{
MIGRATE_UNMOVABLE,//不可移動(dòng)
MIGRATE_MOVABLE,//可移動(dòng)
MIGRATE_RECLAIMABLE,//可回收
MIGRATE_PCPTYPES,//屬于CPU高速緩存中的類型，PCP是per_cpu_pageset的縮寫
MIGRATE_HIGHATOMIC=MIGRATE_PCPTYPES,//緊急內(nèi)存
#ifdefCONFIG_CMA
MIGRATE_CMA,//預(yù)留的連續(xù)內(nèi)存CMA
#endif
#ifdefCONFIG_MEMORY_ISOLATION
MIGRATE_ISOLATE,/*can'tallocatefromhere*/
#endif
MIGRATE_TYPES//不代表任何區(qū)域，只是單純的標(biāo)識(shí)遷移類型這個(gè)枚舉
};

關(guān)于頁面遷移類型的介紹，可回看本文 "1. 伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)" 小節(jié)的內(nèi)容。

通過 this_cpu_ptr 獲取運(yùn)行當(dāng)前進(jìn)程的 CPU 高速緩存列表 pcplist，然后將要釋放的物理內(nèi)存頁添加到對(duì)應(yīng)遷移類型的 pcp->lists[migratetype]。

在 CPU 高速緩存列表 per_cpu_pages 中，每個(gè)遷移類型對(duì)應(yīng)一個(gè) pcplist 。

如果當(dāng)前 pcplist 中的頁面數(shù)量 count 超過了規(guī)定的水位線 high 的值，說明現(xiàn)在 pcplist 中的頁面太多了，需要從 pcplist 中釋放 batch 個(gè)物理頁面到伙伴系統(tǒng)中。這個(gè)過程稱之為惰性合并。

根據(jù)本文 "4. 伙伴系統(tǒng)的內(nèi)存回收原理" 小節(jié)介紹的內(nèi)容，我們知道，單內(nèi)存頁直接釋放回伙伴系統(tǒng)會(huì)發(fā)生很多合并的動(dòng)作，這里的惰性合并策略阻止了大量的無效合并操作。

7.2 伙伴系統(tǒng)回收內(nèi)存源碼實(shí)現(xiàn)

image.png

當(dāng)我們要釋放的內(nèi)存頁超過一頁（order > 0 ）時(shí)，內(nèi)核會(huì)將這些內(nèi)存頁回收至伙伴系統(tǒng)中，釋放內(nèi)存時(shí)伙伴系統(tǒng)的入口函數(shù)為 __free_pages_ok：

staticvoid__free_pages_ok(structpage*page,unsignedintorder)
{
unsignedlongflags;
intmigratetype;
//獲取釋放內(nèi)存頁對(duì)應(yīng)的物理頁號(hào)pfn
unsignedlongpfn=page_to_pfn(page);
//在將內(nèi)存頁回收至伙伴系統(tǒng)之前，需要將內(nèi)存頁page相關(guān)的無用屬性清理一下
if(!free_pages_prepare(page,order,true))
return;
//獲取頁面遷移類型，后續(xù)會(huì)將內(nèi)存頁釋放至伙伴系統(tǒng)中的free_list[migratetype]中
migratetype=get_pfnblock_migratetype(page,pfn);
//關(guān)中斷
local_irq_save(flags);
//進(jìn)入伙伴系統(tǒng)，釋放內(nèi)存
free_one_page(page_zone(page),page,pfn,order,migratetype);
//開中斷
local_irq_restore(flags);
}

__free_pages_ok 函數(shù)的邏輯比較容易理解，核心就是在將內(nèi)存頁回收至伙伴系統(tǒng)之前，需要將這些內(nèi)存頁的 page 結(jié)構(gòu)清理一下，將無用的屬性至空，將清理之后干凈的 page 結(jié)構(gòu)回收至伙伴系統(tǒng)中。這里大家需要注意的是在伙伴系統(tǒng)回收內(nèi)存的時(shí)候也是不響應(yīng)中斷的。

staticvoidfree_one_page(structzone*zone,
structpage*page,unsignedlongpfn,
unsignedintorder,
intmigratetype)
{
//加鎖
spin_lock(&zone->lock);
//正式進(jìn)入伙伴系統(tǒng)回收內(nèi)存，《4.伙伴系統(tǒng)的內(nèi)存回收原理》小節(jié)介紹的邏輯全部封裝在這里
__free_one_page(page,pfn,zone,order,migratetype);
//釋放鎖
spin_unlock(&zone->lock);
}

之前我們?cè)?"4. 伙伴系統(tǒng)的內(nèi)存回收原理" 小節(jié)中介紹的伙伴系統(tǒng)內(nèi)存回收的全部邏輯就封裝在 __free_one_page 函數(shù)中，筆者這里建議大家在看下面相關(guān)源碼實(shí)現(xiàn)的內(nèi)容之前再去回顧下 5.3 小節(jié)的內(nèi)容。

下面我們還是以 5.3 小節(jié)中所舉的具體例子來剖析內(nèi)核如何將內(nèi)存釋放回伙伴系統(tǒng)中的完整實(shí)現(xiàn)過程。

在開始之前，筆者還是先把當(dāng)前伙伴系統(tǒng)中空閑內(nèi)存頁的真實(shí)物理視圖給大家貼出來方便大家對(duì)比，后面在查找需要合并的伙伴的時(shí)候需要拿這張圖來做對(duì)比才能清晰的理解：

image.png

以下是系統(tǒng)中空閑內(nèi)存頁在當(dāng)前伙伴系統(tǒng)中的組織視圖，現(xiàn)在我們需要將 page10 釋放回伙伴系統(tǒng)中：

image.png

經(jīng)過 “4. 伙伴系統(tǒng)的內(nèi)存回收原理” 小節(jié)的內(nèi)容介紹我們知道，在將內(nèi)存塊釋放回伙伴系統(tǒng)時(shí)，內(nèi)核需要從內(nèi)存塊的當(dāng)前階（本例中 order = 0）開始在伙伴系統(tǒng) free_area[order] 中查找能夠合并的伙伴。

伙伴的定義筆者已經(jīng)在 “2. 到底什么是伙伴” 小節(jié)中詳細(xì)為大家介紹過了，伙伴的核心就是兩個(gè)尺寸大小相同并且在物理上連續(xù)的兩個(gè)空閑內(nèi)存塊，內(nèi)存塊可以由一個(gè)物理內(nèi)存頁組成的也可以是由多個(gè)物理內(nèi)存頁組成的。

如果在當(dāng)前階 free_area[order] 中找到了伙伴，則將釋放的內(nèi)存塊和它的伙伴內(nèi)存塊兩兩合并成一個(gè)新的內(nèi)存塊，隨后繼續(xù)到高階中去查找新內(nèi)存塊的伙伴，直到?jīng)]有伙伴可以合并為止。

image.png

/*
*Freeingfunctionforabuddysystemallocator.
*/
staticinlinevoid__free_one_page(structpage*page,
unsignedlongpfn,
structzone*zone,unsignedintorder,
intmigratetype)
{
//釋放內(nèi)存塊與其伙伴內(nèi)存塊合并之后新內(nèi)存塊的pfn
unsignedlongcombined_pfn;
//伙伴內(nèi)存塊的pfn
unsignedlonguninitialized_var(buddy_pfn);
//伙伴內(nèi)存塊的首頁page指針
structpage*buddy;
//伙伴系統(tǒng)中的最大分配階
unsignedintmax_order;

continue_merging:
//從釋放內(nèi)存塊的當(dāng)前分配階開始一直向高階合并內(nèi)存塊，直到不能合并為止
//在本例中當(dāng)前分配階order=0，我們要釋放page10
while(order1){
//在free_area[order]中查找伙伴內(nèi)存塊的pfn
//上圖步驟一中伙伴的pfn為11
//上圖步驟二中伙伴的pfn為8
//上圖步驟三中伙伴的pfn為12
buddy_pfn=__find_buddy_pfn(pfn,order);
//根據(jù)偏移buddy_pfn-pfn計(jì)算伙伴內(nèi)存塊中的首頁page地址
//步驟一伙伴首頁為page11，步驟二伙伴首頁為page8，步驟三伙伴首頁為page12
buddy=page+(buddy_pfn-pfn);
//檢查伙伴pfn的有效性
if(!pfn_valid_within(buddy_pfn))
//無效停止合并
gotodone_merging;
//按照前面介紹的伙伴定義檢查是否為伙伴
if(!page_is_buddy(page,buddy,order))
//不是伙伴停止合并
gotodone_merging;
//將伙伴內(nèi)存塊從當(dāng)前free_area[order]列表中摘下，對(duì)比步驟一到步驟四
del_page_from_free_area(buddy,&zone->free_area[order]);
//合并后新內(nèi)存塊首頁page的pfn
combined_pfn=buddy_pfn&pfn;
//合并后新內(nèi)存塊首頁page指針
page=page+(combined_pfn-pfn);
//以合并后的新內(nèi)存塊為基礎(chǔ)繼續(xù)向高階free_area合并
pfn=combined_pfn;
//繼續(xù)向高階free_area合并，直到不能合并為止
order++;
}

done_merging:
//表示在當(dāng)前伙伴系統(tǒng)free_area[order]中沒有找到伙伴內(nèi)存塊，停止合并
//設(shè)置內(nèi)存塊的分配階order，存儲(chǔ)在第一個(gè)page結(jié)構(gòu)中的private屬性中
set_page_order(page,order);
//將最終合并的內(nèi)存塊插入到伙伴系統(tǒng)對(duì)應(yīng)的free_are[order]中，上圖中步驟五
add_to_free_area(page,&zone->free_area[order],migratetype);

}

根據(jù)上圖展示的在內(nèi)存釋放過程中被釋放內(nèi)存塊從當(dāng)前階 free_area[order] 開始查找其伙伴并依次向高階 free_area 合并的過程以及結(jié)合筆者源碼中提供的詳細(xì)注釋，整個(gè)內(nèi)存釋放的過程還是不難理解的。

這里筆者想重點(diǎn)來講的是，內(nèi)核如何在 free_area 鏈表中查找伙伴內(nèi)存塊，以及如何判斷兩個(gè)內(nèi)存塊是否為伙伴關(guān)系。下面我們來一起看下這部分內(nèi)容：

image.png

7.3 如何查找伙伴

staticinlineunsignedlong
__find_buddy_pfn(unsignedlongpage_pfn,unsignedintorder)
{
returnpage_pfn^(1<

內(nèi)核會(huì)通過 __find_buddy_pfn 函數(shù)根據(jù)當(dāng)前釋放內(nèi)存塊的 pfn，以及當(dāng)前釋放內(nèi)存塊的分配階 order 來確定其伙伴內(nèi)存塊的 pfn。

首先通過 1 << order 左移操作確定要查找伙伴內(nèi)存塊的分配階，因?yàn)榛锇殛P(guān)系最重要的一點(diǎn)就是它們必須是大小相等的兩個(gè)內(nèi)存塊。然后巧妙地通過與要釋放內(nèi)存塊的 pfn 進(jìn)行異或操作就得到了伙伴內(nèi)存塊的 pfn 。

7.4 如何判斷兩個(gè)內(nèi)存塊是否是伙伴

另外一個(gè)重要的輔助函數(shù)就是 page_is_buddy，內(nèi)核通過該函數(shù)來判斷給定兩個(gè)內(nèi)存塊是否為伙伴關(guān)系。筆者在 "2. 到底什么是伙伴" 小節(jié)中明確的給出了伙伴的定義，page_is_buddy 就是相關(guān)的內(nèi)核實(shí)現(xiàn)：

1. 伙伴系統(tǒng)所管理的內(nèi)存頁必須是可用的，不能處于內(nèi)存空洞中，通過 page_is_guard 函數(shù)判斷。

2. 伙伴必須是空閑的內(nèi)存塊，這些內(nèi)存塊必須存在于伙伴系統(tǒng)中，組成內(nèi)存塊的內(nèi)存頁 page 結(jié)構(gòu)中的 flag 標(biāo)志設(shè)置了 PG_buddy 標(biāo)記。通過 PageBuddy 判斷這些內(nèi)存頁是否在伙伴系統(tǒng)中。

3. 兩個(gè)互為伙伴的內(nèi)存塊必須擁有相同的分配階 order，也就是它們之間的大小尺寸必須一致。通過 page_order(buddy) == order 判斷

4. 互為伙伴關(guān)系的內(nèi)存塊必須處于相同的物理內(nèi)存區(qū)域 zone 中。通過 page_zone_id(page) == page_zone_id(buddy) 判斷。

同時(shí)滿足上述四點(diǎn)的兩個(gè)內(nèi)存塊即為伙伴關(guān)系，下面是內(nèi)核中關(guān)于判斷是否為伙伴關(guān)系的源碼實(shí)現(xiàn)：

staticinlineintpage_is_buddy(structpage*page,structpage*buddy,
unsignedintorder)
{
if(page_is_guard(buddy)&&page_order(buddy)==order){
if(page_zone_id(page)!=page_zone_id(buddy))
return0;

return1;
}

if(PageBuddy(buddy)&&page_order(buddy)==order){
if(page_zone_id(page)!=page_zone_id(buddy))
return0;

return1;
}
return0;
}

總結(jié)

在本文的開頭，筆者首先為大家介紹了伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)，目的是在介紹核心原理之前，先為大家構(gòu)建起伙伴系統(tǒng)的整個(gè)骨架。從整體上先認(rèn)識(shí)一下伙伴系統(tǒng)的全局樣貌。

image.png

然后又為大家闡述了伙伴系統(tǒng)中的這個(gè)伙伴到底是什么概念 ，以及如何通過 __find_buddy_pfn 來查找內(nèi)存塊的伙伴。如果通過 page_is_buddy 來判斷兩個(gè)內(nèi)存塊是否為伙伴關(guān)系。

在我們明白了伙伴系統(tǒng)的這些基本概念以及全局框架結(jié)構(gòu)之后，筆者詳細(xì)剖析了伙伴系統(tǒng)的內(nèi)存分配原理及其實(shí)現(xiàn)，其中重點(diǎn)著墨了從高階 freelist 鏈表到低階 freelist 鏈表的減半分裂過程實(shí)現(xiàn)，以及內(nèi)存分配失敗之后，伙伴系統(tǒng)的 fallback 過程實(shí)現(xiàn)。

image.png

最后又詳細(xì)剖析了伙伴系統(tǒng)內(nèi)存回收的原理以及實(shí)現(xiàn)，其中重點(diǎn)著墨了從低階 freelist 到高階 freelist 的合并過程。

image.png

好了，到這里關(guān)于伙伴系統(tǒng)的全部?jī)?nèi)容就結(jié)束了，感謝大家的收看，我們下篇文章見。