Linux內(nèi)核源碼分析 (B.4) 深度剖析 Linux 伙伴系統(tǒng)的設(shè)計與實現(xiàn)
在上篇文章 《深入理解 Linux 物理內(nèi)存分配全鏈路實現(xiàn)》 中，筆者為大家詳細(xì)介紹了 Linux 內(nèi)存分配在內(nèi)核中的整個鏈路實現(xiàn)：
image.png
但是當(dāng)內(nèi)核執(zhí)行到 get_page_from_freelist 函數(shù)，準(zhǔn)備進(jìn)入伙伴系統(tǒng)執(zhí)行具體內(nèi)存分配動作的相關(guān)邏輯，筆者考慮到文章篇幅的原因，并沒有過多的著墨，算是留下了一個小尾巴。
那么本文筆者就為大家完整地介紹一下伙伴系統(tǒng)這部分的內(nèi)容，我們將基于內(nèi)核 5.4 版本的源碼來詳細(xì)的討論一下伙伴系統(tǒng)在內(nèi)核中的設(shè)計與實現(xiàn)。
文章概要.png
1. 伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)
image.png
如上圖所示，內(nèi)核會為 NUMA 節(jié)點中的每個物理內(nèi)存區(qū)域 zone 分配一個伙伴系統(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é)點中的物理內(nèi)存區(qū)域 ” 的內(nèi)容。
在本小節(jié)中，我們聚焦于伙伴系統(tǒng)相關(guān)的數(shù)據(jù)結(jié)構(gòu)介紹~~
struct zone { // 被伙伴系統(tǒng)所管理的物理內(nèi)存頁個數(shù) atomic_long_t managed_pages; // 伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu) struct free_area free_area[MAX_ORDER]; }
struct zone 結(jié)構(gòu)中的 managed_pages 用于表示該內(nèi)存區(qū)域內(nèi)被伙伴系統(tǒng)所管理的物理內(nèi)存頁數(shù)量。
而 managed_pages 的計算方式之前也介紹過了，它是通過 present_pages （不包含內(nèi)存空洞）減去內(nèi)核為應(yīng)對緊急情況而預(yù)留的物理內(nèi)存頁 reserved_pages 得到的。
從這里可以看出伙伴系統(tǒng)所管理的空閑物理內(nèi)存頁并不包含緊急預(yù)留內(nèi)存
伙伴系統(tǒng)的真正核心數(shù)據(jù)結(jié)構(gòu)就是這個 struct free_area 類型的數(shù)組 free_area[MAX_ORDER] 。MAX_ORDER 就是筆者在《深入理解 Linux 物理內(nèi)存分配全鏈路實現(xiàn)》 “ 的第一小節(jié) "1. 內(nèi)核物理內(nèi)存分配接口 ” 中介紹的分配階 order 的最大值減 1。
伙伴系統(tǒng)所分配的物理內(nèi)存頁全部都是物理上連續(xù)的，并且只能分配 2 的整數(shù)冪個頁，這里的整數(shù)冪在內(nèi)核中稱之為分配階 order。
在我們調(diào)用物理內(nèi)存分配接口時，均需要指定這個分配階 order，意思是從伙伴系統(tǒng)申請多少個物理內(nèi)存頁，假設(shè)我們指定分配階為 order，那么就會從伙伴系統(tǒng)中申請 2 的 order 次冪個物理內(nèi)存頁。
伙伴系統(tǒng)會將物理內(nèi)存區(qū)域中的空閑內(nèi)存根據(jù)分配階 order 劃分出不同尺寸的內(nèi)存塊，并將這些不同尺寸的內(nèi)存塊分別用一個雙向鏈表組織起來。
比如：分配階 order 為 0 時，對應(yīng)的內(nèi)存塊就是一個 page。分配階 order 為 1 時，對應(yīng)的內(nèi)存塊就是 2 個 pages。依次類推，當(dāng)分配階 order 為 n 時，對應(yīng)的內(nèi)存塊就是 2 的 order 次冪個 pages。
MAX_ORDER - 1 就是內(nèi)核中規(guī)定的分配階 order 的最大值，定義在 /include/linux/mmzone.h 文件中，最大分配階 MAX_ORDER - 1 = 10，也就是說一次，最多只能從伙伴系統(tǒng)中申請 1024 個內(nèi)存頁，對應(yīng) 4M 大小的連續(xù)物理內(nèi)存。
/* Free memory management - zoned buddy allocator. */ #ifndef CONFIG_FORCE_MAX_ZONEORDER #define MAX_ORDER 11
image.png
數(shù)組 free_area[MAX_ORDER] 中的索引表示的就是分配階 order，用于指定對應(yīng)雙向鏈表組織管理的內(nèi)存塊包含多少個 page。
我們可以通過 cat /proc/buddyinfo 命令來查看 NUMA 節(jié)點中不同內(nèi)存區(qū)域 zone 的伙伴系統(tǒng)當(dāng)前狀態(tài)：
image.png
上圖展示了不同內(nèi)存區(qū)域伙伴系統(tǒng)的 free_area[MAX_ORDER] 數(shù)組中，不同分配階對應(yīng)的內(nèi)存塊個數(shù)，從左到右依次是 0 階，1 階， … ，10 階對應(yīng)的雙向鏈表中包含的內(nèi)存塊個數(shù)。
以上內(nèi)容展示的只是伙伴系統(tǒng)的一個基本骨架，有了這個基本骨架之后，下面筆者繼續(xù)按照一步一圖的方式，來為大家揭開伙伴系統(tǒng)的完整樣貌。
我們先從 free_area[MAX_ORDER] 數(shù)組的類型 struct free_area 結(jié)構(gòu)開始談起~~~
struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; };
struct list_head { // 雙向鏈表 struct list_head *next, *prev; };
根據(jù)前邊的內(nèi)容我們知道 free_area[MAX_ORDER] 數(shù)組描述的只是伙伴系統(tǒng)的一個基本骨架，數(shù)組中的每一個元素統(tǒng)一組織存儲了相同尺寸的內(nèi)存塊。內(nèi)存塊的尺寸分為 0 階，1 階 ，… ，10 階，一共 MAX_ORDER 個尺寸。
struct free_area 主要描述的就是相同尺寸的內(nèi)存塊在伙伴系統(tǒng)中的組織結(jié)構(gòu)， nr_free 則表示的是該尺寸的內(nèi)存塊在當(dāng)前伙伴系統(tǒng)中的個數(shù)，這個值會隨著內(nèi)存的分配而減少，隨著內(nèi)存的回收而增加。
注意：nr_free 表示的可不是空閑內(nèi)存頁 page 的個數(shù)，而是空閑內(nèi)存塊的個數(shù)，對于 0 階的內(nèi)存塊來說 nr_free 確實表示的是單個內(nèi)存頁 page 的個數(shù)，因為 0 階內(nèi)存塊是由一個 page 組成的，但是對于 1 階內(nèi)存塊來說，nr_free 則表示的是 2 個 page 集合的個數(shù)，以此類推對于 n 階內(nèi)存塊來說，nr_free 表示的是 2 的 n 次方 page 集合的個數(shù)
這些相同尺寸的內(nèi)存塊在 struct free_area 結(jié)構(gòu)中是通過 struct list_head 結(jié)構(gòu)類型的雙向鏈表統(tǒng)一組織起來的。
按理來說，內(nèi)核只需要將這些相同尺寸的內(nèi)存塊在 struct free_area 中用一個雙向鏈表串聯(lián)起來就行了。
但是我們從源碼中卻看到內(nèi)核是用多個雙向鏈表來組織這些相同尺寸的內(nèi)存塊的，這些雙向鏈表組成一個數(shù)組 free_list[MIGRATE_TYPES]，該數(shù)組中雙向鏈表的個數(shù)為 MIGRATE_TYPES。
我們從 MIGRATE_TYPES 的字面意思上可以看出，內(nèi)核會根據(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 文件中：
enum migratetype { MIGRATE_UNMOVABLE, // 不可移動 MIGRATE_MOVABLE, // 可移動 MIGRATE_RECLAIMABLE, // 可回收 MIGRATE_PCPTYPES, // 屬于 CPU 高速緩存中的類型，PCP 是 per_cpu_pageset 的縮寫 MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, // 緊急內(nèi)存 #ifdef CONFIG_CMA MIGRATE_CMA, // 預(yù)留的連續(xù)內(nèi)存 CMA #endif #ifdef CONFIG_MEMORY_ISOLATION MIGRATE_ISOLATE, /* can't allocate from here */ #endif MIGRATE_TYPES // 不代表任何區(qū)域，只是單純表示一共有多少個遷移類型 };
MIGRATE_UNMOVABLE 表示不可移動的頁面類型，這種類型的物理內(nèi)存頁面是固定的不能隨意移動，內(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)存地址通過減去一個固定的偏移量就可以直接得到物理內(nèi)存地址，由于這種直接映射的關(guān)系，所以這部分內(nèi)存是不能移動的，因為一旦移動虛擬內(nèi)存地址就會發(fā)生變化，這樣一來虛擬內(nèi)存地址減去固定的偏移得到的物理內(nèi)存地址就不一樣了。
MIGRATE_MOVABLE 表示可以移動的內(nèi)存頁類型，這種頁面類型一般用于在進(jìn)程用戶空間中分配，因為在用戶空間中虛擬內(nèi)存與物理內(nèi)存都是通過頁表來動態(tài)映射的，物理頁移動之后，只需要改變頁表中的映射關(guān)系即可，而虛擬內(nèi)存地址并不需要改變。一切對進(jìn)程來說都是透明的。
MIGRATE_RECLAIMABLE 表示不能移動，但是可以直接回收的頁面類型，比如前面提到的文件緩存頁，它們就可以直接被回收掉，當(dāng)再次需要的時候可以從磁盤中繼續(xù)讀取生成?；蛘咭恍┥芷诒容^短的內(nèi)存頁，比如 DMA 緩存區(qū)中的內(nèi)存頁也是可以被直接回收掉。
MIGRATE_PCPTYPES 則表示 CPU 高速緩存中的頁面類型，PCP 是 per_cpu_pageset 的縮寫，每個 CPU 對應(yīng)一個 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，顧名思義它是一個分配連續(xù)物理內(nèi)存頁面的分配器用于分配連續(xù)的物理內(nèi)存。
大家可能好奇了，我們這節(jié)講到的伙伴系統(tǒng)分配的不也是連續(xù)的物理內(nèi)存嗎？為什么又會多出個 CMA 呢？
原因還是前邊我們多次提到的內(nèi)存碎片對內(nèi)存分配的巨大影響，隨著系統(tǒng)的長時間運行，不可避免的會產(chǎn)生內(nèi)存碎片，這些內(nèi)存碎片會導(dǎo)致在內(nèi)存充足的情況下卻依然找不到一片足夠大的連續(xù)物理內(nèi)存，伙伴系統(tǒng)在這種情況下就會失敗，而連續(xù)的物理內(nèi)存分配對于內(nèi)核來說又是剛需，比如：一些 DMA 設(shè)備只能訪問連續(xù)的物理內(nèi)存，內(nèi)核對于大頁的支持也需要連續(xù)的物理內(nèi)存。
所以為了解決這個問題，內(nèi)核會在系統(tǒng)剛剛啟動的時候，這時內(nèi)存還很充足，先預(yù)留一部分連續(xù)的物理內(nèi)存，這部分物理內(nèi)存就是 CMA 區(qū)域，這部分內(nèi)存可以被進(jìn)程正常的使用，當(dāng)有連續(xù)內(nèi)存分配需求時，內(nèi)核會通過頁面回收或者遷移的方式將這部分內(nèi)存騰出來給 CMA 分配。
CMA 的初始化是在伙伴系統(tǒng)初始化之前就已經(jīng)完成的
MIGRATE_ISOLATE 則是一個虛擬區(qū)域，用于跨越 NUMA 節(jié)點移動物理內(nèi)存頁，內(nèi)核可以將物理內(nèi)存頁移動到使用該頁最頻繁的 CPU 所在的 NUMA 節(jié)點中。
在介紹完這些物理頁面的遷移類型 MIGRATE_TYPES 之后，大家可能不禁有疑問，內(nèi)核為啥會設(shè)定這么多的頁面遷移類型呢 ？
答案還是為了解決前面我們反復(fù)提到的內(nèi)存碎片問題，當(dāng)系統(tǒng)長時間運行之后，隨著不同尺寸內(nèi)存的分配和釋放，就會引起內(nèi)存碎片，這些碎片會導(dǎo)致內(nèi)核在明明還有足夠內(nèi)存的前提下，仍然無法找到一塊足夠大的連續(xù)內(nèi)存分配。如下圖所示：
image.png
上圖中顯示的這 7 個空閑的內(nèi)存頁以碎片的形式存在于內(nèi)存中，這就導(dǎo)致明明還有 7 個空閑的內(nèi)存頁，但是最大的連續(xù)內(nèi)存區(qū)域只有 1 個內(nèi)存頁，當(dāng)內(nèi)核想要申請 2 個連續(xù)的內(nèi)存頁時就會導(dǎo)致失敗。
很長時間以來，物理內(nèi)存碎片一直是 Linux 操作系統(tǒng)的弱點，所以內(nèi)核在 2.6.24 版本中引入了以下方式來避免內(nèi)存碎片。
如果這些內(nèi)存頁是可以遷移的，內(nèi)核就會將空閑的內(nèi)存頁遷移至一起，已分配的內(nèi)存頁遷移至一起，形成了一整塊足夠大的連續(xù)內(nèi)存區(qū)域。
image.png
如果這些內(nèi)存頁是可以回收的，內(nèi)核也可以通過回收頁面的方式，整理出一塊足夠大的空閑連續(xù)內(nèi)存區(qū)域。
在我們清楚了以上介紹的基礎(chǔ)知識之后，再回過頭來看伙伴系統(tǒng)的這些核心數(shù)據(jù)結(jié)構(gòu)，是不是就變得容易理解了~~
struct zone { // 被伙伴系統(tǒng)所管理的物理頁數(shù) atomic_long_t managed_pages; // 伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu) struct free_area free_area[MAX_ORDER]; } struct free_area { struct list_head free_list[MIGRATE_TYPES]; unsigned long nr_free; };
首先伙伴系統(tǒng)會將物理內(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)前各個內(nèi)存區(qū)域中的伙伴系統(tǒng)中不同頁面遷移類型以及不同 order 尺寸的內(nèi)存塊個數(shù)。
image.png
page block order 表示系統(tǒng)中支持的巨型頁對應(yīng)的分配階，pages per block 表示巨型頁中包含的 pages 個數(shù)。
好了，現(xiàn)在我們已經(jīng)清楚了伙伴系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)全貌，接下來筆者會在這個基礎(chǔ)上繼續(xù)為大家介紹伙伴系統(tǒng)的核心工作原理~~
2. 到底什么是伙伴
我們前面一直在談伙伴系統(tǒng)，那么伙伴這個概念到底在內(nèi)核中是什么意思呢？其實下面這張伙伴系統(tǒng)的結(jié)構(gòu)圖已經(jīng)把伙伴的概念很清晰的表達(dá)出來了。
image.png
伙伴在我們?nèi)粘Ｉ钪泻x就是形影不離的好朋友，在內(nèi)核中也是如此，內(nèi)核中的伙伴指的是大小相同并且在物理內(nèi)存上是連續(xù)的兩個或者多個 page。
比如在上圖中，free_area[1] 中組織的是分配階 order = 1 的內(nèi)存塊，內(nèi)存塊中包含了兩個連續(xù)的空閑 page。這兩個空閑 page 就是伙伴。
free_area[10] 中組織的是分配階 order = 10 的內(nèi)存塊，內(nèi)存塊中包含了 1024 個連續(xù)的空閑 page。這 1024 個空閑 page 就是伙伴。
image.png
再比如上圖中的 page0 和 page 1 是伙伴，page2 到 page 5 是伙伴，page6 和 page7 又是伙伴。但是 page0 和 page2 就不能成為伙伴，因為它們的物理內(nèi)存是不連續(xù)的。同時 (page0 到 page3) 和 (page4 到 page7) 所組成的兩個內(nèi)存塊又能構(gòu)成一個伙伴。伙伴必須是大小相同并且在物理內(nèi)存上是連續(xù)的兩個或者多個 page。
3. 伙伴系統(tǒng)的內(nèi)存分配原理
在 《深入理解 Linux 物理內(nèi)存分配全鏈路實現(xiàn)》 一文中的第二小節(jié) " 2. 物理內(nèi)存分配內(nèi)核源碼實現(xiàn) "，筆者介紹了如下四個內(nèi)存分配的接口，內(nèi)核可以通過這些接口向伙伴系統(tǒng)申請內(nèi)存：
struct page *alloc_pages(gfp_t gfp, unsigned int order) unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order) unsigned long get_zeroed_page(gfp_t gfp_mask) unsigned long __get_dma_pages(gfp_t gfp_mask, unsigned int order)
image.png
首先我們可以根據(jù)內(nèi)存分配接口函數(shù)中的 gfp_t gfp_mask ，找到內(nèi)存分配指定的 NUMA 節(jié)點和物理內(nèi)存區(qū)域 zone ，然后找到物理內(nèi)存區(qū)域 zone 對應(yīng)的伙伴系統(tǒng)。
image.png
隨后內(nèi)核通過接口中指定的分配階 order，可以定位到伙伴系統(tǒng)的 free_area[order] 數(shù)組，其中存放的就是分配階為 order 的全部內(nèi)存塊。
最后內(nèi)核進(jìn)一步通過 gfp_t gfp_mask 掩碼中指定的頁面遷移類型 MIGRATE_TYPE，定位到 free_list[MIGRATE_TYPE]，這里存放的就是符合內(nèi)存分配要求的所有內(nèi)存塊。通過遍歷這個雙向鏈表就可以輕松獲得要分配的內(nèi)存。
image.png
比如我們向內(nèi)核申請 ( 2 ^ (order - 1)，2 ^ order ] 之間大小的內(nèi)存，并且這塊內(nèi)存我們指定的遷移類型為 MIGRATE_MOVABLE 時，內(nèi)核會按照 2 ^ order 個內(nèi)存頁進(jìn)行申請。
隨后內(nèi)核會根據(jù) order 找到伙伴系統(tǒng)中的 free_area[order] 對應(yīng)的 free_area 結(jié)構(gòu)，并進(jìn)一步根據(jù)頁面遷移類型定位到對應(yīng)的 free_list[MIGRATE_MOVABLE]，如果該遷移類型的 free_list 中沒有空閑的內(nèi)存塊時，內(nèi)核會進(jìn)一步到上一級鏈表也就是 free_area[order + 1] 中尋找。
如果 free_area[order + 1] 中對應(yīng)的 free_list[MIGRATE_MOVABLE] 鏈表中還是沒有，則繼續(xù)循環(huán)到更高一級 free_area[order + 2] 尋找，直到在 free_area[order + n] 中的 free_list[MIGRATE_MOVABLE] 鏈表中找到空閑的內(nèi)存塊。
但是此時我們在 free_area[order + n] 鏈表中找到的空閑內(nèi)存塊的尺寸是 2 ^ (order + n) 大小，而我們需要的是 2 ^ order 尺寸的內(nèi)存塊，于是內(nèi)核會將這 2 ^ (order + n) 大小的內(nèi)存塊逐級減半分裂，將每一次分裂后的內(nèi)存塊插入到相應(yīng)的 free_area 數(shù)組里對應(yīng)的 free_list[MIGRATE_MOVABLE] 鏈表中，并將最后分裂出的 2 ^ order 尺寸的內(nèi)存塊分配給進(jìn)程使用。
下面筆者舉一個具體的例子來為大家說明伙伴系統(tǒng)的整個內(nèi)存分配過程：
為了清晰地給大家展現(xiàn)伙伴系統(tǒng)的內(nèi)存分配過程，我們暫時忽略 MIGRATE_TYPES 相關(guān)的組織結(jié)構(gòu)
image.png
我們假設(shè)當(dāng)前伙伴系統(tǒng)中只有 order = 3 的空閑鏈表 free_area[3]，其余剩下的分配階 order 對應(yīng)的空閑鏈表中均是空的。 free_area[3] 中僅有一個空閑的內(nèi)存塊，其中包含了連續(xù)的 8 個 page。
現(xiàn)在我們向伙伴系統(tǒng)申請一個 page 大小的內(nèi)存（對應(yīng)的分配階 order = 0），那么內(nèi)核會在伙伴系統(tǒng)中首先查看 order = 0 對應(yīng)的空閑鏈表 free_area[0] 中是否有空閑內(nèi)存塊可供分配。
隨后內(nèi)核會根據(jù)前邊介紹的內(nèi)存分配邏輯，繼續(xù)升級到 free_area[1] , free_area[2] 鏈表中尋找空閑內(nèi)存塊，直到查找到 free_area[3] 發(fā)現(xiàn)有一個可供分配的內(nèi)存塊。這個內(nèi)存塊中包含了 8 個 連續(xù)的空閑 page，但是我們只要一個 page 就夠了，那該怎么辦呢？
于是內(nèi)核先將 free_area[3] 中的這個空閑內(nèi)存塊從鏈表中摘下，然后減半分裂成兩個內(nèi)存塊，分裂出來的這兩個內(nèi)存塊分別包含 4 個 page（分配階 order = 2）。
image.png
上圖分裂出的兩個內(nèi)存塊，黃色的代表原有內(nèi)存塊的前半部分，綠色代表原有內(nèi)存塊的后半部分。
隨后內(nèi)核會將分裂出的后半部分（圖中綠色部分，order = 2），插入到 free_rea[2] 鏈表中。
image.png
前半部分（圖中黃色部分，order = 2）繼續(xù)減半分裂，分裂出來的這兩個內(nèi)存塊分別包含 2 個 page（分配階 order = 1）。如下圖中第 4 步所示，前半部分為黃色，后半部分為紫色。同理按照前邊的分裂邏輯，內(nèi)核會將后半部分內(nèi)存塊（紫色部分，分配階 order = 1）插入到 free_area[1] 鏈表中。
image.png
前半部分（圖中黃色部分，order = 1）在上圖中的第 6 步繼續(xù)減半分裂，分裂出來的這兩個內(nèi)存塊分別包含 1 個 page（分配階 order = 0），前半部分為青色，后半部分為黃色。
后半部分插入到 frea_area[0] 鏈表中，前半部分返回給進(jìn)程，這時內(nèi)存分配成功，流程結(jié)束。
以上流程就是伙伴系統(tǒng)的核心內(nèi)存分配過程，下面我們再把內(nèi)存頁面的遷移屬性 MIGRATE_TYPES 考慮進(jìn)來，來看一下完整的伙伴系統(tǒng)內(nèi)存分配流程：
image.png
現(xiàn)在我們加上了內(nèi)存 MIGRATE_TYPES 的組織結(jié)構(gòu)，其實分配流程還是和核心流程一樣的，只不過上面提到的那些高階 order 的減半分裂情形都發(fā)生在各個 free_area[order] 中固定的 free_list[MIGRATE_TYPE] 里罷了。
比如我們要求分配的內(nèi)存遷移屬性要求是 MIGRATE_MOVABLE 類型，那么減半分裂流程分別發(fā)生在 free_area[2] ，free_area[1] ，free_area[0] 對應(yīng)的 free_list[MIGRATE_MOVABLE] 中，多了一個 free_list 的維度，僅此而已。
不過筆者這里想重點著墨的地方是內(nèi)存分配的一種異常情形，比如我們想要分配特定遷移類型的內(nèi)存，但是當(dāng)前伙伴系統(tǒng)所有 free_area[order] 里對應(yīng)的 free_list[MIGRATE_TYPE] 均無法滿足內(nèi)存分配的需求（沒有足夠特定遷移類型的空閑內(nèi)存塊）。那么這種場景下內(nèi)核會怎么處理呢？
其實同樣的問題我們在 《深入理解 Linux 物理內(nèi)存管理》 一文中也遇到過，當(dāng)時筆者介紹內(nèi)存 NUMA 架構(gòu)的時候提到，如果當(dāng)前 NUMA 節(jié)點無法滿足內(nèi)存分配時，內(nèi)核會跨越 NUMA 節(jié)點從其他節(jié)點上分配內(nèi)存。
typedef struct pglist_data { // NUMA 節(jié)點中的物理內(nèi)存區(qū)域個數(shù) int nr_zones; // NUMA 節(jié)點中的物理內(nèi)存區(qū)域 struct zone node_zones[MAX_NR_ZONES]; // NUMA 節(jié)點的備用列表 struct zonelist node_zonelists[MAX_ZONELISTS]; } pg_data_t;
每個 NUMA 節(jié)點的 struct pglist_data 結(jié)構(gòu)中都會包含一個 node_zonelists，其中包含了當(dāng)前NUMA 節(jié)點以及備用 NUMA 節(jié)點的所有內(nèi)存區(qū)域以及對應(yīng)的伙伴系統(tǒng)，當(dāng)前 NUMA 節(jié)點內(nèi)存不足時，內(nèi)核會從 node_zonelists 中的備用 NUMA 節(jié)點中分配內(nèi)存。
這里也是同樣的道理，當(dāng)伙伴系統(tǒng)中指定的遷移列表 free_list[MIGRATE_TYPE] 無法滿足內(nèi)存分配需求時，內(nèi)核根據(jù)不同遷移類型定義了不同的 fallback 規(guī)則：
/* * This array describes the order lists are fallen back to when * the free lists for the desirable migrate type are depleted * * The other migratetypes do not have fallbacks. */ static int fallbacks[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)存不足時，內(nèi)核會 fallback 到 MIGRATE_RECLAIMABLE 中去獲取，如果還是不足，則再次降級到 MIGRATE_MOVABLE 中獲取，如果仍然無法滿足內(nèi)存分配，才會失敗退出。
正常的分配流程先是從低階到高階依次查找空閑內(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)存塊，那么就分配一個盡可能大的內(nèi)存塊（從最高階開始查找），避免向其他鏈表引入內(nèi)存碎片。
筆者還是以上邊的例子說明，當(dāng)我們向伙伴系統(tǒng)申請 MIGRATE_UNMOVABLE 遷移類型的內(nèi)存時，假設(shè)內(nèi)核在伙伴系統(tǒng)中的 free_area[0] 到 free_area[10] 中的所有 free_list[MIGRATE_UNMOVABLE] 鏈表中均無法找到一個空閑的內(nèi)存塊。
那么就會 fallback 到 MIGRATE_RECLAIMABLE 類型，從最高階 free_area[10] 中的 free_list[MIGRATE_RECLAIMABLE] 鏈表開始查找，如果找到一個空閑的內(nèi)存塊，則首先會遷移到對應(yīng)的 order 的 free_list[MIGRATE_UNMOVABLE] 鏈表，然后流程繼續(xù)回到核心流程，在各個 free_area[order] 對應(yīng)的 free_list[MIGRATE_UNMOVABLE] 鏈表中執(zhí)行減半分裂。
這里大家只需要理解一下 fallback 的大概流程，詳細(xì)內(nèi)容筆者會在后面介紹伙伴系統(tǒng)實現(xiàn)的章節(jié)詳細(xì)解析~~~
4. 伙伴系統(tǒng)的內(nèi)存回收原理
內(nèi)存有分配就會有釋放，本小節(jié)我們就來看下如何將內(nèi)存塊釋放回伙伴系統(tǒng)中。在上個小節(jié)中筆者為大家介紹了伙伴系統(tǒng)內(nèi)存分配的完整流程，核心就是從高階 free_list 中尋找空閑內(nèi)存塊，然后依次減半分裂。
伙伴系統(tǒng)中的內(nèi)存回收剛好和內(nèi)存分配的過程相反，核心則是從低階 free_list 中尋找釋放內(nèi)存塊的伙伴，如果沒有伙伴則將要釋放的內(nèi)存塊插入到對應(yīng)分配階 order 的 free_list中。如果存在伙伴，則將釋放內(nèi)存塊與它的伙伴合并，作為一個新的內(nèi)存塊繼續(xù)到更高階的 free_list 中循環(huán)重復(fù)上述過程，直到不能合并為止。
伙伴的概念我們已經(jīng)在本文 《 2. 到底什么是伙伴 》小節(jié)中介紹過了，核心就是兩個伙伴內(nèi)存塊必須是大小相同并且在物理內(nèi)存上是連續(xù)的。
下面筆者還是舉一個具體的例子來為大家展現(xiàn)伙伴系統(tǒng)內(nèi)存回收的過程：
為了清晰地給大家展現(xiàn)伙伴系統(tǒng)的內(nèi)存回收過程，我們暫時忽略 MIGRATE_TYPES 相關(guān)的組織結(jié)構(gòu)
image.png
假設(shè)當(dāng)前伙伴系統(tǒng)的狀態(tài)如上圖所示，現(xiàn)在我們需要向伙伴系統(tǒng)釋放一個內(nèi)存頁（order = 0），編號為10。
這里筆者先來解釋下上圖伙伴系統(tǒng)中所管理的物理內(nèi)存頁后邊編號的含義：我們知道伙伴系統(tǒng)中所管理的全部是連續(xù)的物理內(nèi)存，既然是連續(xù)的，那么每個內(nèi)存頁 page 都會有一個固定的偏移（類似數(shù)組中的下標(biāo)）。
這一點我們在前邊的文章 《深入理解 Linux 物理內(nèi)存管理》的 “ 4.2 NUMA 節(jié)點描述符 pglist_data 結(jié)構(gòu) ” 小節(jié)中已經(jīng)介紹過了，在每個 NUMA 節(jié)點中，內(nèi)核通過一個 node_mem_map 數(shù)組來組織節(jié)點內(nèi)的物理內(nèi)存頁 page。
typedef struct pglist_data { // NUMA 節(jié)點id int node_id; // 指向 NUMA 節(jié)點內(nèi)管理所有物理頁 page 的數(shù)組 struct page *node_mem_map; }
上圖伙伴系統(tǒng)中所管理的內(nèi)存頁 page 只是被伙伴系統(tǒng)組織之后的視圖，下面是物理內(nèi)存頁在物理內(nèi)存上的真實視圖（包含要被釋放的內(nèi)存頁 10）：
image.png
有了這些基本概念之后，我回過頭來在看 page10 釋放回伙伴系統(tǒng)的整個過程：
下面的流程需要大家時刻對比內(nèi)存頁在物理內(nèi)存上的真實視圖，不要被伙伴系統(tǒng)的組織視圖所干擾。
image.png
由于我們要釋放的內(nèi)存塊只包含了一個物理內(nèi)存頁 page10，所以它的分配階 order = 0，首先內(nèi)核需要在伙伴系統(tǒng) free_area[0] 中查找與 page10 大小相等并且連續(xù)的內(nèi)存塊（伙伴）。
從物理內(nèi)存的真實視圖中我們可以看到 page11 是 page10 的伙伴，于是將 page11 從 free_area[0] 上摘下并與 page10 合并組成一個新的內(nèi)存塊（分配階 order = 1）。隨后內(nèi)核會在 free_area[1] 中查找新內(nèi)存塊的伙伴：
image.png
我們繼續(xù)對比物理內(nèi)存頁的真實視圖，發(fā)現(xiàn)在 free_area[1] 中 page8 和 page9 組成的內(nèi)存塊與 page10 和 page11 組成的內(nèi)存塊是伙伴，于是繼續(xù)將這兩個內(nèi)存塊（分配階 order = 1）繼續(xù)合并成一個新的內(nèi)存塊（分配階 order = 2）。隨后內(nèi)核會在 free_area[2] 中查找新內(nèi)存塊的伙伴：
image.png
繼續(xù)對比物理內(nèi)存頁的真實視圖，發(fā)現(xiàn)在 free_area[2] 中 page12，page13，page14，page15 組成的內(nèi)存塊與 page8，page9，page10，page11 組成的新內(nèi)存塊是伙伴，于是將它們從 free_area[2] 上摘下繼續(xù)合并成一個新的內(nèi)存塊（分配階 order = 3），隨后內(nèi)核會在 free_area[3] 中查找新內(nèi)存塊的伙伴：
image.png
對比物理內(nèi)存頁的真實視圖，我們發(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)存塊的伙伴，如果找到，則兩兩合并成一個新的內(nèi)存塊，隨后繼續(xù)到高階中去查找新內(nèi)存塊的伙伴，直到?jīng)]有伙伴可以合并。
一個是高階到低階分裂，一個是低階到高階合并。
5. 進(jìn)入伙伴系統(tǒng)的前奏
現(xiàn)在我們已經(jīng)清楚了伙伴系統(tǒng)的所有核心原理，但是干講原理總覺得 talk is cheap，還是需要 show 一下 code，所以接下來筆者會帶大家看一下內(nèi)核中伙伴系統(tǒng)的實現(xiàn)源碼，真刀真槍的來一下。
但真正進(jìn)入伙伴系統(tǒng)之前，內(nèi)核還是做了很多鋪墊工作，為了給大家解釋清楚這些內(nèi)容，我們還是需要重新回到上篇文章 《深入理解 Linux 物理內(nèi)存分配全鏈路實現(xiàn)》 “5. __alloc_pages 內(nèi)存分配流程總覽” 小節(jié)中留下的尾巴，正式來介紹下 get_page_from_freelist 函數(shù)。
在上篇文章 “3. 物理內(nèi)存分配內(nèi)核源碼實現(xiàn)” 小節(jié)中，筆者為大家介紹了 Linux 物理內(nèi)存分配的完整流程，我們知道物理內(nèi)存分配總體上分為兩個路徑，內(nèi)核首先嘗試的是在快速路徑下分配內(nèi)存，如果不行的話，內(nèi)核會走慢速路徑分配內(nèi)存。
無論是快速路徑還是慢速路徑下的內(nèi)存分配都需要最終調(diào)用 get_page_from_freelist 函數(shù)進(jìn)行最終的內(nèi)存分配。只不過，不同路徑下 get_page_from_freelist 函數(shù)的內(nèi)存分配策略以及需要考慮的內(nèi)存水位線會有所不同，其中慢速路徑下的內(nèi)存分配策略會更加激進(jìn)一些，這一點我們在上篇文章的相關(guān)章節(jié)內(nèi)容介紹中體會很深。
image.png
在每次調(diào)用 get_page_from_freelist 函數(shù)之前，內(nèi)核都會根據(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)容。
struct alloc_context { // 運行進(jìn)程 CPU 所在 NUMA 節(jié)點以及其所有備用 NUMA 節(jié)點中允許內(nèi)存分配的內(nèi)存區(qū)域 struct zonelist *zonelist; // NUMA 節(jié)點狀態(tài)掩碼 nodemask_t *nodemask; // 內(nèi)存分配優(yōu)先級最高的內(nèi)存區(qū)域 zone struct zoneref *preferred_zoneref; // 物理內(nèi)存頁的遷移類型分為：不可遷移，可回收，可遷移類型，防止內(nèi)存碎片 int migratetype; // 內(nèi)存分配最高優(yōu)先級的內(nèi)存區(qū)域 zone enum zone_type highest_zoneidx; // 是否允許當(dāng)前 NUMA 節(jié)點中的臟頁均衡擴(kuò)散遷移至其他 NUMA 節(jié)點 bool spread_dirty_pages; };
這里最核心的兩個參數(shù)就是 zonelist 和 preferred_zoneref。preferred_zoneref 表示當(dāng)前本地 NUMA 節(jié)點（優(yōu)先級最高），其中 zonelist 我們在 《深入理解 Linux 物理內(nèi)存管理》的 “ 4.3 NUMA 節(jié)點物理內(nèi)存區(qū)域的劃分 ” 小節(jié)中詳細(xì)介紹過，zonelist 里面包含了當(dāng)前 NUMA 節(jié)點在內(nèi)的所有備用 NUMA 節(jié)點的所有物理內(nèi)存區(qū)域，用于當(dāng)前 NUMA 節(jié)點沒有足夠空閑內(nèi)存的情況下進(jìn)行跨 NUMA 節(jié)點分配。
typedef struct pglist_data { // NUMA 節(jié)點中的物理內(nèi)存區(qū)域個數(shù) int nr_zones; // NUMA 節(jié)點中的物理內(nèi)存區(qū)域 struct zone node_zones[MAX_NR_ZONES]; // NUMA 節(jié)點的備用列表 struct zonelist node_zonelists[MAX_ZONELISTS]; } pg_data_t;
struct pglist_data 里的 node_zonelists 是一個全集，而 struct alloc_context 里的 zonelist 是在內(nèi)存分配過程中，根據(jù)指定的內(nèi)存分配策略從全集 node_zonelists 過濾出來的一個子集（允許進(jìn)行本次內(nèi)存分配的所有 NUMA 節(jié)點及其內(nèi)存區(qū)域）。
get_page_from_freelist 的核心邏輯其實很簡單，就是遍歷 struct alloc_context 里的 zonelist，挨個檢查各個 NUMA 節(jié)點中的物理內(nèi)存區(qū)域是否有足夠的空閑內(nèi)存可以滿足本次的內(nèi)存分配要求，如果可以滿足則進(jìn)入該物理內(nèi)存區(qū)域的伙伴系統(tǒng)中完整真正的內(nèi)存分配動作。
下面我們先來看一下 get_page_from_freelist 函數(shù)的完整邏輯：
image.png
/* * get_page_from_freelist goes through the zonelist trying to allocate * a page. */ static struct page * get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags, const struct alloc_context *ac) { struct zoneref *z; // 當(dāng)前遍歷到的內(nèi)存區(qū)域 zone 引用 struct zone *zone; // 最近遍歷的NUMA節(jié)點 struct pglist_data *last_pgdat = NULL; // 最近遍歷的NUMA節(jié)點中包含的臟頁數(shù)量是否在內(nèi)核限制范圍內(nèi) bool last_pgdat_dirty_ok = false; // 如果需要避免內(nèi)存碎片，則 no_fallback = true bool no_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)存 struct page *page; // 內(nèi)存分配過程中設(shè)定的水位線 unsigned long mark; // 檢查內(nèi)存區(qū)域所在 NUMA 節(jié)點是否在進(jìn)程所允許的 CPU 上 if (cpusets_enabled() && (alloc_flags & ALLOC_CPUSET) && !__cpuset_zone_allowed(zone, gfp_mask)) continue; // 每個 NUMA 節(jié)點中包含的臟頁數(shù)量都有一定的限制。 // 如果本次內(nèi)存分配是為 page cache 分配的 page，用于寫入數(shù)據(jù)（不久就會變成臟頁） // 這里需要檢查當(dāng)前 NUMA 節(jié)點的臟頁比例是否在限制范圍內(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)識，在本地節(jié)點無法滿足內(nèi)存分配的情況下(因為需要避免內(nèi)存碎片) // 這輪循環(huán)會遍歷 remote 節(jié)點（跨NUMA節(jié)點） if (no_fallback && nr_online_nodes > 1 && zone != ac->preferred_zoneref->zone) { int local_nid; // 如果本地節(jié)點分配內(nèi)存失敗是因為避免內(nèi)存碎片的原因，那么會繼續(xù)回到本地節(jié)點進(jìn)行 retry 重試同時取消 ALLOC_NOFRAGMENT（允許引入碎片） local_nid = zone_to_nid(ac->preferred_zoneref->zone); if (zone_to_nid(zone) != local_nid) { // 內(nèi)核認(rèn)為保證本地的局部性會比避免內(nèi)存碎片更加重要 alloc_flags &= ~ALLOC_NOFRAGMENT; goto retry; } } // 獲取本次內(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)) { int ret; // 如果本次內(nèi)存分配策略是忽略內(nèi)存水位線，那么就在本次遍歷到的zone里嘗試分配內(nèi)存 if (alloc_flags & ALLOC_NO_WATERMARKS) goto try_this_zone; // 如果本次內(nèi)存分配不能忽略內(nèi)存水位線的限制，那么就會判斷當(dāng)前 zone 所屬 NUMA 節(jié)點是否允許進(jìn)行內(nèi)存回收 if (!node_reclaim_enabled() || !zone_allows_reclaim(ac->preferred_zoneref->zone, zone)) // 不允許進(jìn)行內(nèi)存回收則繼續(xù)遍歷下一個 NUMA 節(jié)點的內(nèi)存區(qū)域 continue; // 針對當(dāng)前 zone 所在 NUMA 節(jié)點進(jìn)行內(nèi)存回收 ret = node_reclaim(zone->zone_pgdat, gfp_mask, order); switch (ret) { case NODE_RECLAIM_NOSCAN: // 返回該值表示當(dāng)前 NUMA 節(jié)點沒有必要進(jìn)行回收。比如快速分配路徑下就不處理頁面回收的問題 continue; case NODE_RECLAIM_FULL: // 返回該值表示通過掃描之后發(fā)現(xiàn)當(dāng)前 NUMA 節(jié)點并沒有可以回收的內(nèi)存頁 continue; default: // 該分支表示當(dāng)前 NUMA 節(jié)點已經(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)) goto try_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); return page; } else { ....... 省略 ..... } } // 內(nèi)存分配失敗 return NULL; }
與本文主題無關(guān)的非核心步驟大家通過筆者的注釋簡單了解即可，下面我們只介紹與本文主題相關(guān)的核心步驟。
雖然 get_page_from_freelist 函數(shù)的代碼比較冗長，但是其核心邏輯比較簡單，主干框架就是通過 for_next_zone_zonelist_nodemask 來遍歷當(dāng)前 NUMA 節(jié)點以及備用節(jié)點的所有內(nèi)存區(qū)域（zonelist），然后逐個通過 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ù)遍歷下一個 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)存分配全鏈路實現(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)存分配） unsigned int alloc_flags = ALLOC_WMARK_LOW;`
在上篇文章 “4. 內(nèi)存慢速分配入口 alloc_pages_slowpath” 小節(jié)的介紹中，我們知道在慢速路徑下，內(nèi)存分配策略中的水位線又被調(diào)整為了 WMARK_MIN：
`// 在慢速內(nèi)存分配路徑中，會進(jìn)一步放寬對內(nèi)存分配的限制，將內(nèi)存分配水位線調(diào)低到 WMARK_MIN // 也就是說內(nèi)存區(qū)域中的剩余內(nèi)存需要在 WMARK_MIN 水位線之上就可以進(jìn)行內(nèi)存分配了 unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;`
如果內(nèi)存分配仍然失敗，則內(nèi)核會將內(nèi)存分配策略中的水位線調(diào)整為 ALLOC_NO_WATERMARKS，表示再內(nèi)存分配時，可以忽略水位線的限制，再一次進(jìn)行重試。
不同的內(nèi)存水位線會影響到內(nèi)存分配邏輯，所以在通過 for_next_zone_zonelist_nodemask 遍歷 NUMA 節(jié)點中的物理內(nèi)存區(qū)域的一開始就需要獲取該內(nèi)存區(qū)域指定水位線的具體數(shù)值，內(nèi)核通過 wmark_pages 宏來獲?。?/p>
#define wmark_pages(z, i) (z->_watermark[i] + z->watermark_boost)
struct zone { // 物理內(nèi)存區(qū)域中的水位線 unsigned long _watermark[NR_WMARK]; // 優(yōu)化內(nèi)存碎片對內(nèi)存分配的影響，可以動態(tài)改變內(nèi)存區(qū)域的基準(zhǔn)水位線。 unsigned long watermark_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 只是用來快速檢測分配階 order = 0 情況下的相關(guān)水位線情況。
下面我們先來看下 zone_watermark_fast 的邏輯：
static inline bool zone_watermark_fast(struct zone *z, unsigned int order, unsigned long mark, int highest_zoneidx, unsigned int alloc_flags, gfp_t gfp_mask) { long free_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) { long usable_free; long reserved; // 可供本次內(nèi)存分配使用的符合要求的真實可用內(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); // 計算真正可供內(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]) return true; } // 近一步檢查內(nèi)存區(qū)域伙伴系統(tǒng)中是否有足夠的 order 階的內(nèi)存塊可供分配 if (__zone_watermark_ok(z, order, mark, highest_zoneidx, alloc_flags, free_pages)) return true; ........ 省略無關(guān)代碼 ....... // 水位線檢查失敗 return false; }
首先會通過 zone_page_state 來獲取當(dāng)前 zone 中剩余空閑內(nèi)存頁的總體容量 free_pages。
筆者在 《深入理解 Linux 物理內(nèi)存管理》的 “ 5. 內(nèi)核如何管理 NUMA 節(jié)點中的物理內(nèi)存區(qū)域 ” 小節(jié)中為大家介紹 struct zone 結(jié)構(gòu)體的時候提過，每個內(nèi)存區(qū)域 zone 里有一個 vm_stat 用來存放與 zone 相關(guān)的各種統(tǒng)計變量。
`struct zone { // 該內(nèi)存區(qū)域內(nèi)存使用的統(tǒng)計信息 atomic_long_t vm_stat[NR_VM_ZONE_STAT_ITEMS]; }`
內(nèi)核可以通過 zone_page_state 來訪問 vm_stat 從而獲取對應(yīng)的統(tǒng)計量，free_pages 就是其中的一個統(tǒng)計變量。但是這里大家需要注意的是 free_pages 表示的當(dāng)前 zone 里剩余空閑內(nèi)存頁的一個總量，是一個全集的概念。其中還包括了內(nèi)存區(qū)域的預(yù)留內(nèi)存 lowmem_reserve 以及為 highatomic 預(yù)留的緊急內(nèi)存。這些預(yù)留內(nèi)存都有自己特定的用途，普通內(nèi)存的申請不會用到預(yù)留內(nèi)存。
流程如果進(jìn)入到 if (!order) 分支的話表示本次內(nèi)存分配只是申請一個（order = 0）空閑的內(nèi)存頁，在這里會快速的檢測相關(guān)水位線情況是否滿足，如果滿足就會快速返回。
這里涉及到兩個重要的局部變量，筆者需要向大家交代一下：
-
usable_free：表示可供本次內(nèi)存分配使用的空閑內(nèi)存頁總量。前邊我們提到 free_pages 表示的是剩余空閑內(nèi)存頁的一個全集，里邊還包括很多不能進(jìn)行普通內(nèi)存分配的空閑內(nèi)存頁，比如預(yù)留內(nèi)存和緊急內(nèi)存。
-
reserved：表示本次內(nèi)存分配不能使用到的空閑內(nèi)存頁數(shù)量，這一部分的內(nèi)存頁數(shù)量計算是通過 __zone_watermark_unusable_free 函數(shù)完成的。最后使用 free_pages 減去 reserved 就可以得到真正的 usable_free 。
static inline long __zone_watermark_unusable_free(struct zone *z, unsigned int order, unsigned int alloc_flags) { // ALLOC_HARDER 的設(shè)置表示可以使用 high-atomic 緊急預(yù)留內(nèi)存 const bool alloc_harder = (alloc_flags & (ALLOC_HARDER|ALLOC_OOM)); long unusable_free = (1 << order) - 1; // 如果沒有設(shè)置 ALLOC_HARDER 則不能使用 high_atomic 緊急預(yù)留內(nèi)存 if (likely(!alloc_harder)) // 不可用內(nèi)存的數(shù)量需要統(tǒng)計上 high-atomic 這部分內(nèi)存 unusable_free += z->nr_reserved_highatomic; #ifdef CONFIG_CMA // 如果沒有設(shè)置 ALLOC_CMA 則表示本次內(nèi)存分配不能從 CMA 區(qū)域獲取 if (!(alloc_flags & ALLOC_CMA)) // 不可用內(nèi)存的數(shù)量需要統(tǒng)計上 CMA 區(qū)域中的空閑內(nèi)存頁 unusable_free += zone_page_state(z, NR_FREE_CMA_PAGES); #endif // 返回不可用內(nèi)存的數(shù)量，表示本次內(nèi)存分配不能使用的內(nèi)存容量 return unusable_free; }
如果 usable_free > mark + z->lowmem_reserve[highest_zoneidx] 條件為 true 表示當(dāng)前可用剩余內(nèi)存頁容量在水位線 mark 之上，可以進(jìn)行內(nèi)存分配，返回 true。
我們在 《深入理解 Linux 物理內(nèi)存管理》的 " 5.2 物理內(nèi)存區(qū)域中的水位線 " 小節(jié)中介紹水位線相關(guān)的計算邏輯的時候提過，水位線的計算是需要刨去 lowmem_reserve 預(yù)留內(nèi)存的，也就是水位線的值并不包含 lowmem_reserve 內(nèi)存在內(nèi)。
所以這里在判斷可用內(nèi)存是否滿足水位線的關(guān)系時需要加上這部分 lowmem_reserve ，才能得到正確的結(jié)果。
如果本次內(nèi)存分配申請的是高階內(nèi)存塊（ order > 0），則會進(jìn)入 __zone_watermark_ok 函數(shù)中，近一步判斷伙伴系統(tǒng)中是否有足夠的高階內(nèi)存塊能夠滿足 order 階的內(nèi)存分配：
bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark, int highest_zoneidx, unsigned int alloc_flags, long free_pages) { // 保證內(nèi)存分配順利進(jìn)行的最低水位線 long min = mark; int o; const bool alloc_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)存分配會比普通的 ALLOC_HARDER 策略更加努力激進(jìn)一些，所以這里水位線會降低二分之一 if (alloc_flags & ALLOC_OOM) min -= min / 2; else // ALLOC_HARDER 策略下水位線只會降低四分之一 min -= min / 4; } // 檢查當(dāng)前可用剩余內(nèi)存是否在指定水位線之上。 // 內(nèi)存的分配必須保證可用剩余內(nèi)存容量在指定水位線之上，否則不能進(jìn)行內(nèi)存分配 if (free_pages <= min + z->lowmem_reserve[highest_zoneidx]) return false; // 流程走到這里，對應(yīng)內(nèi)存分配階 order = 0 的情況下就已經(jīng) OK 了 // 剩余空閑內(nèi)存在水位線之上，那么肯定能夠分配一頁出來 if (!order) return true; // 但是對于 high-order 的內(nèi)存分配，這里還需要近一步檢查伙伴系統(tǒng) // 根據(jù)伙伴系統(tǒng)內(nèi)存分配的原理，這里需要檢查高階 free_list 中是否有足夠的空閑內(nèi)存塊可供分配 for (o = order; o < MAX_ORDER; o++) { // 從當(dāng)前分配階 order 對應(yīng)的 free_area 中檢查是否有足夠的內(nèi)存塊 struct free_area *area = &z->free_area[o]; int mt; // 如果當(dāng)前 free_area 中的 nr_free = 0 表示對應(yīng) free_list 中沒有合適的空閑內(nèi)存塊 // 那么繼續(xù)到高階 free_area 中查找 if (!area->nr_free) continue; // 檢查 free_area 中所有的遷移類型 free_list 是否有足夠的內(nèi)存塊 for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) { if (!free_area_empty(area, mt)) return true; } #ifdef CONFIG_CMA // 如果內(nèi)存分配指定需要從 CMA 區(qū)域中分配連續(xù)內(nèi)存 // 那么就需要檢查 MIGRATE_CMA 對應(yīng)的 free_list 是否是空 if ((alloc_flags & ALLOC_CMA) && !free_area_empty(area, MIGRATE_CMA)) { return true; } #endif // 如果設(shè)置了 ALLOC_HARDER，則表示可以從 HIGHATOMIC 區(qū)中的緊急預(yù)留內(nèi)存中分配，檢查對應(yīng) free_list if (alloc_harder && !free_area_empty(area, MIGRATE_HIGHATOMIC)) return true; } // 伙伴系統(tǒng)中的剩余內(nèi)存塊無法滿足 order 階的內(nèi)存分配 return false; }
在 __zone_watermark_ok 函數(shù)的開始需要計算出真正可用的剩余內(nèi)存 free_pages 。
`// 獲取真正可用的剩余空閑內(nèi)存頁數(shù)量 free_pages -= __zone_watermark_unusable_free(z, order, alloc_flags);`
緊接著內(nèi)核會根據(jù) ALLOC_HIGH 以及 ALLOC_HARDER 標(biāo)識來決定是否降低水位線的要求。在 《深入理解 Linux 物理內(nèi)存分配全鏈路實現(xiàn)》 一文中的 “3.1 內(nèi)存分配行為標(biāo)識掩碼 ALLOC_* ” 小節(jié)中筆者曾詳細(xì)的為大家介紹過這些 ALLOC_* 相關(guān)的掩碼，當(dāng)時筆者提了一句，當(dāng)內(nèi)存分配策略設(shè)置為 ALLOC_HIGH 或者 ALLOC_HARDER 時，會使內(nèi)存分配更加的激進(jìn)，努力一些。
當(dāng)時大家可能會比較懵，怎樣才算是激進(jìn)？怎樣才算是努力呢？
其實答案就在這里，當(dāng)內(nèi)存分配策略 alloc_flags 設(shè)置了 ALLOC_HARDER 時，水位線的要求會降低原來的四分之一，相當(dāng)于放款了內(nèi)存分配的限制。比原來更加努力使內(nèi)存分配成功。
當(dāng)內(nèi)存分配策略 alloc_flags 設(shè)置了 ALLOC_HIGH 時，水位線的要求會降低原來的二分之一，相當(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 之后，對于 order = 0 的內(nèi)存分配情形下，就已經(jīng) OK 了，可以放心直接進(jìn)行內(nèi)存分配了。
但是對于 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 中查找對應(yīng)的 free_list 中是否有足夠的內(nèi)存塊滿足 order 階的內(nèi)存分配要求。
-
如果有，那么水位線相關(guān)的校驗工作到此結(jié)束，內(nèi)核會直接去伙伴系統(tǒng)中申請 order 階的內(nèi)存塊。
-
如果沒有，則水位線校驗失敗，伙伴系統(tǒng)無法滿足本次的內(nèi)存分配要求。
image.png
5.3 內(nèi)存分配成功之后初始化 page
經(jīng)過 zone_watermark_ok 的校驗，現(xiàn)在內(nèi)存水位線符合內(nèi)存分配的要求，并且伙伴系統(tǒng)中有足夠的空閑內(nèi)存塊可供內(nèi)存分配申請，現(xiàn)在可以放心調(diào)用 rmqueue 函數(shù)進(jìn)入伙伴系統(tǒng)進(jìn)行內(nèi)存分配了。
rmqueue 函數(shù)封裝的正是伙伴系統(tǒng)的核心邏輯，這一部分的源碼實現(xiàn)筆者放在下一小節(jié)中介紹，這里我們先關(guān)注內(nèi)存分配成功之后，對于內(nèi)存頁 page 的初始化邏輯。
當(dāng)通過 rmqueue 函數(shù)從伙伴系統(tǒng)中成功申請到分配階為 order 大小的內(nèi)存塊時，內(nèi)核需要調(diào)用 prep_new_page 函數(shù)初始化這部分內(nèi)存塊，之后才能返回給進(jìn)程使用。
static void prep_new_page(struct page *page, unsigned int order, gfp_t gfp_flags, unsigned int alloc_flags) { // 初始化 struct page，清除一些頁面屬性標(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)中申請出來的，里面可能包含一些無用的標(biāo)記（上一次被使用過的，還沒清理），所以需要將這些無用標(biāo)記清理掉，并且在此基礎(chǔ)上根據(jù) gfp_flags 掩碼對 struct page 進(jìn)行初始化的準(zhǔn)備工作。
比如通過 set_page_private 將 struct page 里的 private 指針?biāo)赶虻膬?nèi)容清空，private 指針在內(nèi)核中的使用比較復(fù)雜，它會在不同場景下指向不同的內(nèi)容。
set_page_private(page, 0);
將頁面的使用計數(shù)設(shè)置為 1 ，表示當(dāng)前物理內(nèi)存頁正在被使用。
set_page_refcounted(page);
如果 gfp_flags 掩碼中設(shè)置了 ___GFP_ZERO，這時就需要將這些 page 初始化為零頁。
由于初始化頁面的準(zhǔn)備工作和本文的主線內(nèi)容并沒有多大的關(guān)聯(lián)，所以筆者這里只做簡單介紹，大家大概了解一下初始化做了哪些準(zhǔn)備工作即可。
5.3.2 設(shè)置復(fù)合頁 compound_page
復(fù)合頁 compound_page 本質(zhì)上就是通過兩個或者多個物理上連續(xù)的內(nèi)存頁 page 組裝成的一個在邏輯上看起來比普通內(nèi)存頁 page 更大的頁。它底層的依賴本質(zhì)還是一個一個的普通內(nèi)存頁 page。
我們都知道 Linux 管理內(nèi)存的最小單位是 page，每個 page 描述 4K 大小的物理內(nèi)存，但在一些內(nèi)核使用場景中，比如 slab 內(nèi)存池中，往往會向伙伴系統(tǒng)一次性申請多個普通內(nèi)存頁 page，然后將這些內(nèi)存頁 page 劃分為多個大小相同的小內(nèi)存塊，這些小內(nèi)存塊被 slab 內(nèi)存池統(tǒng)一管理。
slab 內(nèi)存池底層其實依賴的是多個普通內(nèi)存頁，但是內(nèi)核期望將這多個內(nèi)存頁統(tǒng)一成一個邏輯上的內(nèi)存頁來統(tǒng)一管理，這個邏輯上的內(nèi)存頁就是本小節(jié)要介紹的復(fù)合頁。
而在 Linux 內(nèi)存管理的架構(gòu)中都是統(tǒng)一通過 struct page 來管理內(nèi)存，復(fù)合頁卻是通過兩個或者多個物理上連續(xù)的內(nèi)存頁 page 組裝成的一個邏輯頁，那么復(fù)合頁的管理與普通頁的管理如何統(tǒng)一呢？
這就引出了本小節(jié)的主題——復(fù)合頁 compound_page，下面我們就來看下 Linux 如果通過統(tǒng)一的 struct page 結(jié)構(gòu)來描述這些復(fù)合頁（compound_page）：
雖然復(fù)合頁（compound_page）是由多個物理上連續(xù)的普通 page 組成的，但是在內(nèi)核的視角里它還是被當(dāng)做一個特殊內(nèi)存頁來看待。
下圖所示，是由 4 個連續(xù)的普通內(nèi)存頁 page 組成的一個 compound_page：
image.png
組成復(fù)合頁的第一個 page 我們稱之為首頁（Head Page），其余的均稱之為尾頁（Tail Page）。
我們來看一下 struct page 中關(guān)于描述 compound_page 的相關(guān)字段：
`struct page { // 首頁 page 中的 flags 會被設(shè)置為 PG_head 表示復(fù)合頁的第一頁 unsigned long flags; // 其余尾頁會通過該字段指向首頁 unsigned long compound_head; // 用于釋放復(fù)合頁的析構(gòu)函數(shù)，保存在首頁中 unsigned char compound_dtor; // 該復(fù)合頁有多少個 page 組成，order 還是分配階的概念，在首頁中保存 // 本例中的 order = 2 表示由 4 個普通頁組成 unsigned char compound_order; // 該復(fù)合頁被多少個進(jìn)程使用，內(nèi)存頁反向映射的概念，首頁中保存 atomic_t compound_mapcount; // 復(fù)合頁使用計數(shù)，首頁中保存 atomic_t compound_pincount; }`
首頁對應(yīng)的 struct page 結(jié)構(gòu)里的 flags 會被設(shè)置為 PG_head，表示這是復(fù)合頁的第一頁。
另外首頁中還保存關(guān)于復(fù)合頁的一些額外信息，比如：
-
用于釋放復(fù)合頁的析構(gòu)函數(shù)會保存在首頁 struct page 結(jié)構(gòu)里的 compound_dtor 字段中
-
復(fù)合頁的分配階 order 會保存在首頁中的 compound_order 中以及用于指示復(fù)合頁的引用計數(shù) compound_pincount，以及復(fù)合頁的反向映射個數(shù)（該復(fù)合頁被多少個進(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ù)合頁中的所有尾頁都會通過其對應(yīng)的 struct page 結(jié)構(gòu)中的 compound_head 指向首頁，這樣通過首頁和尾頁就組裝成了一個完整的復(fù)合頁 compound_page 。
image.png
在我們理解了 compound_page 的組織結(jié)構(gòu)之后，我們在回過頭來看 “6.3 內(nèi)存分配成功之后初始化 page” 小節(jié)中的 prep_new_page 函數(shù)：
當(dāng)內(nèi)核向伙伴系統(tǒng)申請復(fù)合頁 compound_page 的時候，會在 gfp_flags 掩碼中設(shè)置 __GFP_COMP 標(biāo)識，表次本次內(nèi)存分配要分配一個復(fù)合頁，復(fù)合頁中的 page 個數(shù)由分配階 order 決定。
當(dāng)內(nèi)核向伙伴系統(tǒng)申請了 2 ^ order 個內(nèi)存頁 page 時，大家注意在伙伴系統(tǒng)的視角中內(nèi)存還是一頁一頁的，伙伴系統(tǒng)并不知道有復(fù)合頁的存在，當(dāng)我們申請成功之后，需要在 prep_new_page 函數(shù)中將這 2 ^ order 個內(nèi)存頁 page 按照前面介紹的邏輯組裝成一個 復(fù)合頁 compound_page。
void prep_compound_page(struct page *page, unsigned int order) { int i; int nr_pages = 1 << order; // 設(shè)置首頁 page 中的 flags 為 PG_head __SetPageHead(page); // 首頁之后的 page 全部是尾頁，循環(huán)遍歷設(shè)置尾頁 for (i = 1; i < nr_pages; i++) prep_compound_tail(page, i); // 最后設(shè)置首頁相關(guān)屬性 prep_compound_head(page, order); }
static void prep_compound_tail(struct page *head, int tail_idx) { // 由于復(fù)合頁中的 page 全部是連續(xù)的，直接使用偏移即可獲得對應(yīng)尾頁 struct page *p = head + tail_idx; // 設(shè)置尾頁標(biāo)識 p->mapping = TAIL_MAPPING; // 尾頁 page 結(jié)構(gòu)中的 compound_head 指向首頁 set_compound_head(p, head); }
static __always_inline void set_compound_head(struct page *page, struct page *head) { WRITE_ONCE(page->compound_head, (unsigned long)head + 1); }
static void prep_compound_head(struct page *page, unsigned int order) { // 設(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)的實現(xiàn)
image.png
現(xiàn)在內(nèi)核通過前邊介紹的 get_page_from_freelist 函數(shù)，循環(huán)遍歷 zonelist 終于找到了符合內(nèi)存分配條件的物理內(nèi)存區(qū)域 zone。接下來就會通過 rmqueue 函數(shù)進(jìn)入到該物理內(nèi)存區(qū)域 zone 對應(yīng)的伙伴系統(tǒng)中實際分配物理內(nèi)存。
image.png
/* * Allocate a page from the given zone. Use pcplists for order-0 allocations. */ 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) { unsigned long flags; struct page *page; if (likely(order == 0)) { // 當(dāng)我們申請一個物理頁面（order = 0）時，內(nèi)核首先會從 CPU 高速緩存列表 pcplist 中直接分配，而不會走伙伴系統(tǒng)，提高內(nèi)存分配速度 page = rmqueue_pcplist(preferred_zone, zone, gfp_flags, migratetype, alloc_flags); goto out; } // 加鎖并關(guān)閉中斷，防止并發(fā)訪問 spin_lock_irqsave(&zone->lock, flags); // 當(dāng)申請頁面超過一個 （order > 0）時，則從伙伴系統(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)中申請分配階 order 大小的物理內(nèi)存塊 page = __rmqueue(zone, order, migratetype, alloc_flags); } while (page && check_new_pages(page, order)); // 解鎖 spin_unlock(&zone->lock); if (!page) goto failed; // 重新統(tǒng)計內(nèi)存區(qū)域中的相關(guān)統(tǒng)計指標(biāo) zone_statistics(preferred_zone, zone); // 打開中斷 local_irq_restore(flags); out: return page; failed: // 分配失敗 local_irq_restore(flags); return NULL; }
6.1 從 CPU 高速緩存列表中獲取內(nèi)存頁
內(nèi)核對只分配一頁物理內(nèi)存的情況做了特殊處理，當(dāng)只請求一頁內(nèi)存時，內(nèi)核會借助 CPU 高速緩存冷熱頁列表 pcplist 加速內(nèi)存分配的處理，此時分配的內(nèi)存頁將來自于 pcplist 而不是伙伴系統(tǒng)。
pcp 是 per_cpu_pageset 的縮寫，內(nèi)核會為每個 CPU 分配一個高速緩存列表，關(guān)于這部分內(nèi)容，筆者已經(jīng)在 《深入理解 Linux 物理內(nèi)存管理》一文中的 “ 5.7 物理內(nèi)存區(qū)域中的冷熱頁 ” 小節(jié)非常詳細(xì)的為大家介紹過了，忘記的同學(xué)可以在回看下。
在 NUMA 內(nèi)存架構(gòu)下，每個物理內(nèi)存區(qū)域都?xì)w屬于一個特定的 NUMA 節(jié)點，NUMA 節(jié)點中包含了一個或者多個 CPU，NUMA 節(jié)點中的每個內(nèi)存區(qū)域會關(guān)聯(lián)到一個特定的 CPU 上.
而每個 CPU 都有自己獨立的高速緩存，所以每個 CPU 對應(yīng)一個 per_cpu_pageset 結(jié)構(gòu)，用于管理這個 CPU 高速緩存中的冷熱頁。
所謂的熱頁就是已經(jīng)加載進(jìn) CPU 高速緩存中的物理內(nèi)存頁，所謂的冷頁就是還未加載進(jìn) CPU 高速緩存中的物理內(nèi)存頁，冷頁是熱頁的后備選項
每個 CPU 都可以訪問系統(tǒng)中的所有物理內(nèi)存頁，盡管訪問速度不同，因此特定的物理內(nèi)存區(qū)域 struct zone 不僅要考慮到所屬 NUMA 節(jié)點中相關(guān)的 CPU，還需要照顧到系統(tǒng)中的其他 CPU。
在 Linux 內(nèi)核中，系統(tǒng)會經(jīng)常請求和釋放單個頁面。如果針對每個 CPU，都為其預(yù)先分配一個用于緩存單個內(nèi)存頁面的高速緩存頁列表，用于滿足本地 CPU 發(fā)出的單頁內(nèi)存請求，就能提升系統(tǒng)的性能。所以在 struct zone 結(jié)構(gòu)中持有了系統(tǒng)中所有 CPU 的高速緩存頁列表 per_cpu_pageset。
struct zone { struct per_cpu_pages __percpu *per_cpu_pageset; }
struct per_cpu_pages { int count; /* pcplist 里的頁面總數(shù) */ int high; /* pcplist 里的高水位線，count 超過 high 時，內(nèi)核會釋放 batch 個頁面到伙伴系統(tǒng)中*/ int batch; /* pcplist 里的頁面來自于伙伴系統(tǒng)，batch 定義了每次從伙伴系統(tǒng)獲取或者歸還多少個頁面*/ // CPU 高速緩存列表 pcplist，每個遷移類型對應(yīng)一個 pcplist struct list_head lists[NR_PCP_LISTS]; };
當(dāng)內(nèi)核嘗試從 pcplist 中獲取一個物理內(nèi)存頁時，會首先獲取運行當(dāng)前進(jìn)程的 CPU 對應(yīng)的高速緩存列表 pcplist。然后根據(jù)指定的具體頁面遷移類型 migratetype 獲取對應(yīng)遷移類型的 pcplist。
當(dāng)獲取到符合條件的 pcplist 之后，內(nèi)核會調(diào)用 __rmqueue_pcplist 從 pcplist 中摘下一個物理內(nèi)存頁返回。
/* Lock and remove page from the per-cpu list */ static struct page *rmqueue_pcplist(struct zone *preferred_zone, struct zone *zone, gfp_t gfp_flags, int migratetype, unsigned int alloc_flags) { struct per_cpu_pages *pcp; struct list_head *list; struct page *page; unsigned long flags; // 關(guān)閉中斷 local_irq_save(flags); // 獲取運行當(dāng)前進(jìn)程的 CPU 高速緩存列表 pcplist pcp = &this_cpu_ptr(zone->pageset)->pcp; // 獲取指定頁面遷移類型的 pcplist list = &pcp->lists[migratetype]; // 從指定遷移類型的 pcplist 中移除一個頁面，用于內(nèi)存分配 page = __rmqueue_pcplist(zone, migratetype, alloc_flags, pcp, list); if (page) { // 統(tǒng)計內(nèi)存區(qū)域內(nèi)的相關(guān)信息 zone_statistics(preferred_zone, zone); } // 開中斷 local_irq_restore(flags); return page; }
pcplist 中緩存的內(nèi)存頁面其實全部來自于伙伴系統(tǒng)，當(dāng) pcplist 中的頁面數(shù)量 count 為 0 （表示此時 pcplist 里沒有緩存的頁面）時，內(nèi)核會調(diào)用 rmqueue_bulk 從伙伴系統(tǒng)中獲取 batch 個物理頁面添加到 pcplist，從伙伴系統(tǒng)中獲取頁面的過程參照本文 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)中的內(nèi)容。
隨后內(nèi)核會將 pcplist 中的第一個物理內(nèi)存頁從鏈表中摘下返回，count 計數(shù)減一。
/* Remove page from the per-cpu list, caller must protect the list */ static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype, unsigned int alloc_flags, struct per_cpu_pages *pcp, struct list_head *list) { struct page *page; do { // 如果當(dāng)前 pcplist 中的頁面為空，那么則從伙伴系統(tǒng)中獲取 batch 個頁面放入 pcplist 中 if (list_empty(list)) { pcp->count += rmqueue_bulk(zone, 0, pcp->batch, list, migratetype, alloc_flags); if (unlikely(list_empty(list))) return NULL; } // 獲取 pcplist 上的第一個物理頁面 page = list_first_entry(list, struct page, lru); // 將該物理頁面從 pcplist 中摘除 list_del(&page->lru); // pcplist 中的 count 減一 pcp->count--; } while (check_new_pcp(page)); return page; }
6.2 從伙伴系統(tǒng)中獲取內(nèi)存頁
在本文 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)中筆者詳細(xì)為大家介紹了伙伴系統(tǒng)的整個內(nèi)存分配原理，那么在本小節(jié)中，我們將正式進(jìn)入伙伴系統(tǒng)中，來看下伙伴系統(tǒng)在內(nèi)核中是如何實現(xiàn)的。
在前面介紹的 rmqueue 函數(shù)中，涉及到伙伴系統(tǒng)入口函數(shù)的有兩個：
-
__rmqueue_smallest 函數(shù)主要是封裝了整個伙伴系統(tǒng)關(guān)于內(nèi)存分配的核心流程，該函數(shù)中的代碼正是 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)所講的核心內(nèi)容。
-
__rmqueue 函數(shù)封裝的是伙伴系統(tǒng)的整個完整流程，底層調(diào)用了 __rmqueue_smallest 函數(shù)，它主要實現(xiàn)的是當(dāng)伙伴系統(tǒng) free_area 中對應(yīng)的遷移列表 free_list[MIGRATE_TYPE] 無法滿足內(nèi)存分配需求時， 內(nèi)存分配在伙伴系統(tǒng)中的 fallback 流程。這一點筆者也在 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)中詳細(xì)介紹過了。
當(dāng)我們向內(nèi)核申請的內(nèi)存頁超過一頁（order > 0）時，內(nèi)核就會進(jìn)入伙伴系統(tǒng)中為我們申請內(nèi)存。
如果內(nèi)存分配策略 alloc_flags 指定了 ALLOC_HARDER 時，就會調(diào)用 __rmqueue_smallest 直接進(jìn)入伙伴系統(tǒng)，從 free_list[MIGRATE_HIGHATOMIC] 鏈表中分配 order 大小的物理內(nèi)存塊。
image.png
如果分配失敗或者 alloc_flags 沒有指定 ALLOC_HARDER 則會通過 __rmqueue 進(jìn)入伙伴系統(tǒng)，這里會處理分配失敗之后的 fallback 邏輯。
/* * This array describes the order lists are fallen back to when * the free lists for the desirable migrate type are depleted * * The other migratetypes do not have fallbacks. */ static int fallbacks[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)的核心實現(xiàn)
我們還是以 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)中，介紹伙伴系統(tǒng)內(nèi)存分配核心原理時，所舉的示例為大家剖析伙伴系統(tǒng)的核心源碼實現(xiàn)。
假設(shè)當(dāng)前伙伴系統(tǒng)中只有 order = 3 的空閑鏈表 free_area[3] ，其中只有一個空閑的內(nèi)存塊，包含了連續(xù)的 8 個 page。其余剩下的分配階 order 對應(yīng)的空閑鏈表中均是空的。
image.png
現(xiàn)在我們向伙伴系統(tǒng)申請一個 page 大小的內(nèi)存（對應(yīng)的分配階 order = 0），經(jīng)過前面的介紹我們知道當(dāng)申請一個 page 大小的內(nèi)存時，內(nèi)核是從 pcplist 中進(jìn)行分配的，但是這里筆者為了方便給大家介紹伙伴系統(tǒng)，所以我們暫時讓它走伙伴系統(tǒng)的流程。
內(nèi)核會在伙伴系統(tǒng)中從當(dāng)前分配階 order 開始，依次遍歷 free_area[order] 里對應(yīng)的指定頁面遷移類型 free_list[MIGRATE_TYPE] 鏈表，直到找到一個合適尺寸的內(nèi)存塊為止。
image.png
在本示例中，內(nèi)核會在伙伴系統(tǒng)中首先查看 order = 0 對應(yīng)的空閑鏈表 free_area[0] 中是否有空閑內(nèi)存塊可供分配。如果有，則將該空閑內(nèi)存塊從 free_area[0] 摘下返回，內(nèi)存分配成功。
如果沒有，隨后內(nèi)核會根據(jù)前邊介紹的內(nèi)存分配邏輯，繼續(xù)升級到 free_area[1] , free_area[2] 鏈表中尋找空閑內(nèi)存塊，直到查找到 free_area[3] 發(fā)現(xiàn)有一個可供分配的內(nèi)存塊。這個內(nèi)存塊中包含了 8 個連續(xù)的空閑 page，然后將這 8 個 連續(xù)的空閑 page 組成的內(nèi)存塊依次進(jìn)行減半分裂，將每次分裂出來的后半部分內(nèi)存塊插入到對應(yīng)尺寸的 free_area 中，如下圖所示：
image.png
/* * Go through the free lists for the given migratetype and remove * the smallest available page from the freelists */ static __always_inline struct page *__rmqueue_smallest(struct zone *zone, unsigned int order, int migratetype) { unsigned int current_order; struct free_area *area; struct page *page; /* 從當(dāng)前分配階 order 開始在伙伴系統(tǒng)對應(yīng)的 free_area[order] 里查找合適尺寸的內(nèi)存塊*/ for (current_order = order; current_order < MAX_ORDER; ++current_order) { // 獲取當(dāng)前 order 在伙伴系統(tǒng)中對應(yīng)的 free_area[order] // 對應(yīng)上圖 free_area[3] area = &(zone->free_area[current_order]); // 從 free_area[order] 中對應(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ù)向上查找 // 對應(yīng)上圖 free_area[0]，free_area[1]，free_area[2] continue; // 如果在當(dāng)前 free_area[order] 中找到空閑內(nèi)存塊，則從 free_list[MIGRATE_TYPE] 鏈表中摘除 // 對應(yīng)上圖步驟 1：將內(nèi)存塊從 free_area[3] 中摘除 del_page_from_free_area(page, area); // 將摘下來的內(nèi)存塊進(jìn)行減半分裂并插入對應(yīng)的尺寸的 free_area 中 // 對應(yīng)上圖步驟 [2,3], [4,5], [6,7] expand(zone, page, order, current_order, area, migratetype); // 設(shè)置頁面的遷移類型 set_pcppage_migratetype(page, migratetype); // 內(nèi)存分配成功返回，對應(yīng)上圖步驟 8 return page; } // 內(nèi)存分配失敗返回 null return NULL; }
下面我們來看下減半分裂過程的實現(xiàn)，expand 函數(shù)中的參數(shù)在本節(jié)示例中：low = 指定分配階 order = 0，high = 最后遍歷到的分配階 order = 3。
static inline void expand(struct zone *zone, struct page *page, int low, int high, struct free_area *area, int migratetype) { // size = 8，表示當(dāng)前要進(jìn)行減半分裂的內(nèi)存塊是由 8 個連續(xù) page 組成的。 // 剛剛從 free_area[3] 上摘下 unsigned long size = 1 << high; // 依次進(jìn)行減半分裂，直到分裂出指定 order 的內(nèi)存塊出來 // 對應(yīng)上圖中的步驟 2，4，6 // 初始 high = 3 ,low = 0 while (high > low) { // free_area 要降到下一階，此時變?yōu)?free_area[2] area--; // 分配階要降級 high = 2 high--; // 內(nèi)存塊尺寸要減半，由 8 變成 4，表示要分裂出由 4 個連續(xù) page 組成的兩個內(nèi)存塊。 // 參考上圖中的步驟 2 size >>= 1; // 標(biāo)記為保護(hù)頁，當(dāng)其伙伴被釋放時，允許合并，參見 《4.伙伴系統(tǒng)的內(nèi)存回收原理》小節(jié) if (set_page_guard(zone, &page[size], high, migratetype)) continue; // 將本次減半分裂出來的第二個內(nèi)存塊插入到對應(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); // 本次分裂出來的第一個內(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 實現(xiàn)
當(dāng)我們向內(nèi)核申請的內(nèi)存頁面超過一頁（order > 0 ），并且內(nèi)存分配策略 alloc_flags 中并沒有設(shè)置 ALLOC_HARDER 的時候，內(nèi)存分配流程就會進(jìn)入 __rmqueue 走常規(guī)的伙伴系統(tǒng)分配流程。
static __always_inline struct page * __rmqueue(struct zone *zone, unsigned int order, int migratetype, unsigned int alloc_flags) { struct page *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)存塊時，就會進(jìn)入這個分支 ..... // 如果遷移類型是 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)) goto retry; } // 內(nèi)存分配成功 return page; }
從上述 __rmqueue 函數(shù)的源碼實現(xiàn)中我們可以看出，該函數(shù)處理了伙伴系統(tǒng)內(nèi)存分配的異常流程，即調(diào)用 __rmqueue_smallest 進(jìn)入伙伴系統(tǒng)分配內(nèi)存時，發(fā)現(xiàn)伙伴系統(tǒng)各個分配階 free_area[order] 中對應(yīng)的遷移列表 free_list[MIGRATE_TYPE] 無法滿足內(nèi)存分配需求時，__rmqueue_smallest 函數(shù)就會返回 null，伙伴系統(tǒng)內(nèi)存分配失敗。
隨后內(nèi)核就會進(jìn)入伙伴系統(tǒng)的 fallback 流程，這里對 MIGRATE_MOVABLE 遷移類型做了一下特殊處理，當(dāng)伙伴系統(tǒng)中 free_list[MIGRATE_MOVABLE] 沒有足夠空閑內(nèi)存塊時，會優(yōu)先降級到 CMA 區(qū)域內(nèi)進(jìn)行分配。
static __always_inline struct page *__rmqueue_cma_fallback(struct zone *zone, unsigned int order) { return __rmqueue_smallest(zone, order, MIGRATE_CMA); }
image.png
如果我們指定的頁面遷移類型并非 MIGRATE_MOVABLE 或者降級 CMA 之后仍然分配失敗，內(nèi)核就會進(jìn)入 __rmqueue_fallback 走常規(guī)的 fallback 流程，該函數(shù)封裝的正是筆者在 “3. 伙伴系統(tǒng)的內(nèi)存分配原理” 小節(jié)的后半部分介紹的 fallback 邏輯：
在 __rmqueue_fallback 函數(shù)中，內(nèi)核會根據(jù)預(yù)先定義的相關(guān) fallback 規(guī)則開啟內(nèi)存分配的 fallback 流程。fallback 規(guī)則在內(nèi)核中用一個 int 類型的二維數(shù)組表示，其中第一維表示需要進(jìn)行 fallback 的頁面遷移類型，第二維表示 fallback 的優(yōu)先級。后續(xù)內(nèi)核會按照這個優(yōu)先級 fallback 到具體的 free_list[fallback_migratetype] 中去分配內(nèi)存。
static int fallbacks[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)存不足時，內(nèi)核會 fallback 到 MIGRATE_RECLAIMABLE 中去獲取，如果還是不足，則再次降級到 MIGRATE_MOVABLE 中獲取，如果仍然無法滿足內(nèi)存分配，才會失敗退出。
static __always_inline bool __rmqueue_fallback(struct zone *zone, int order, int start_migratetype, unsigned int alloc_flags) { // 最終會 fall back 到伙伴系統(tǒng)的哪個 free_area 中分配內(nèi)存 struct free_area *area; // fallback 和正常的分配流程正好相反，是從最高階的free_area[MAX_ORDER - 1] 開始查找空閑內(nèi)存塊 int current_order; // 最初指定的內(nèi)存分配階 int min_order = order; struct page *page; // 最終計算出 fallback 到哪個頁面遷移類型 free_list 上 int fallback_mt; // 是否可以從 free_list[fallback] 中竊取內(nèi)存塊到 free_list[start_migratetype] 中 // start_migratetype 表示我們最初指定的頁面遷移類型 bool can_steal; // 如果設(shè)置了 ALLOC_NOFRAGMENT 表示不希望引入內(nèi)存碎片 // 在這種情況下內(nèi)核會更加傾向于分配一個盡可能大的內(nèi)存塊，避免向其他鏈表引入內(nèi)存碎片 if (alloc_flags & ALLOC_NOFRAGMENT) // pageblock_order 用于定義系統(tǒng)支持的巨型頁對應(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ù)降級到下一個分配階 free_area 中查找 if (fallback_mt == -1) continue; // can_steal 會在 find_suitable_fallback 的過程中被設(shè)置 // 當(dāng)我們指定的頁面遷移類型為 MIGRATE_MOVABLE 并且無法從其他 fallback 遷移類型列表中竊取頁面 can_steal = false 時 // 內(nèi)核會更加傾向于 fallback 分配最小的可用頁面，即尺寸和指定order最接近的頁面數(shù)量而不是尺寸最大的 // 因為這里的條件是分配可移動的頁面類型，天然可以避免永久內(nèi)存碎片，無需按照最大的尺寸分配 if (!can_steal && start_migratetype == MIGRATE_MOVABLE && current_order > order) goto find_smallest; // can_steal = true，則開始從 free_list[fallback] 列表中竊取頁面 goto do_steal; } return false; find_smallest: // 該分支目的在于尋找尺寸最貼近指定 order 大小的最小可用頁面 // 從指定 order 開始 fallback for (current_order = order; current_order < MAX_ORDER; current_order++) { area = &(zone->free_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 重試流程，此時 free_list[start_migratetype] 中已經(jīng)有足夠的內(nèi)存頁面可供分配了 return true; }
從上述內(nèi)存分配 fallback 源碼實現(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 核心邏輯實現(xiàn)
本小節(jié)我們來看下內(nèi)核定義的 fallback 規(guī)則具體的流程實現(xiàn)，fallback 規(guī)則定義如下，筆者在之前的章節(jié)中已經(jīng)多次提到過了，這里不在重復(fù)解釋，我們重點關(guān)注它的 fallback 流程實現(xiàn)。
static int fallbacks[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ù)中封裝了頁面遷移類型整個的 fallback 過程：
-
fallback 規(guī)則定義在 fallbacks[MIGRATE_TYPES][3] 二維數(shù)組中，第一維表示要進(jìn)行 fallback 的頁面遷移類型 migratetype。第二維 migratetype 遷移類型可以 fallback 到哪些遷移類型中，這些可以 fallback 的頁面遷移類型按照優(yōu)先級排列。
-
該函數(shù)的核心邏輯是在
for (i = 0;; i++)循環(huán)中按照 fallbacks[migratetype][i] 數(shù)組定義的 fallback 優(yōu)先級，依次在 free_area[order] 中對應(yīng)的 free_list[fallback] 列表中查找是否有空閑的內(nèi)存塊。
image.png
- 如果當(dāng)前 free_list[fallback] 列表中沒有空閑內(nèi)存塊，則繼續(xù)在 for 循環(huán)中降級到下一個 fallback 頁面遷移類型中去查找，也就是 for 循環(huán)中的 fallbacks[migratetype][i] 。直到找到空閑內(nèi)存塊為止，否則返回 -1。
int find_suitable_fallback(struct free_area *area, unsigned int order, int migratetype, bool only_stealable, bool *can_steal) { int i; // 最終選取的 fallback 頁面遷移類型 int fallback_mt; // 當(dāng)前 free_area[order] 中以無空閑頁面，則返回失敗 if (area->nr_free == 0) return -1; *can_steal = false; // 按照 fallback 優(yōu)先級，循環(huán)在 free_list[fallback] 中查詢是否有空閑內(nèi)存塊 for (i = 0;; i++) { // 按照優(yōu)先級獲取 fallback 頁面遷移類型 fallback_mt = fallbacks[migratetype][i]; if (fallback_mt == MIGRATE_TYPES) break; // 如果當(dāng)前 free_list[fallback] 為空則繼續(xù)循環(huán)降級查找 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) return fallback_mt; if (*can_steal) return fallback_mt; } return -1; }
// 這里竊取頁面的目的是從 fallback 類型的 freelist 中拿到一個高階的大內(nèi)存塊 // 之所以要竊取盡可能大的內(nèi)存塊是為了避免引入內(nèi)存碎片 // 但 MIGRATE_MOVABLE 類型的頁面本身就可以避免永久內(nèi)存碎片 // 所以 fallback MIGRATE_MOVABLE 類型的頁面時，會跳轉(zhuǎn)到 find_smallest 分支只需要選擇一個合適的 fallback 內(nèi)存塊即可 static bool can_steal_fallback(unsigned int order, int start_mt) { if (order >= pageblock_order) return true; if (order >= pageblock_order / 2 || start_mt == MIGRATE_RECLAIMABLE || start_mt == MIGRATE_UNMOVABLE || page_group_by_mobility_disabled) return true; // 跳轉(zhuǎn)到 find_smallest 分支選擇一個合適的 fallback 內(nèi)存塊 return false; }
can_steal_fallback 函數(shù)中定義了是否可以從 free_list[fallback] 竊取頁面到指定 free_list[migratetype] 中，邏輯如下：
- 如果我們指定的內(nèi)存分配階 order 大于等于 pageblock_order，則返回 true。pageblock_order 表示系統(tǒng)中支持的巨型頁對應(yīng)的分配階，默認(rèn)為伙伴系統(tǒng)中的最大分配階減一，我們可以通過
cat /proc/pagetypeinfo命令查看。
image.png
-
如果我們指定的頁面遷移類型為 MIGRATE_RECLAIMABLE 或者 MIGRATE_UNMOVABLE，則不管我們要申請的頁面尺寸有多大，內(nèi)核都會允許竊取頁面 can_steal = true ，因為它們最終會 fallback 到 MIGRATE_MOVABLE 可移動頁面類型中，這樣造成內(nèi)存碎片的情況會少一些。
-
當(dāng)內(nèi)核全局變量 page_group_by_mobility_disabled 設(shè)置為 1 時，則所有物理內(nèi)存頁面都是不可移動的，這時內(nèi)核也允許竊取頁面。
在系統(tǒng)初始化期間，所有頁都被標(biāo)記為 MIGRATE_MOVABLE 可移動的頁面類型，其他的頁面遷移類型都是后來通過 __rmqueue_fallback 竊取產(chǎn)生的。而是否能夠竊取 fallback 遷移類型列表中的頁面，就是本小節(jié)介紹的內(nèi)容。
7. 內(nèi)存釋放源碼實現(xiàn)
在 《深入理解 Linux 物理內(nèi)存分配全鏈路實現(xiàn)》 中的 “1. 內(nèi)核物理內(nèi)存分配接口” 小節(jié)中我們介紹了內(nèi)核分配物理內(nèi)存的相關(guān)接口：
struct page *alloc_pages(gfp_t gfp, unsigned int order) unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order) unsigned long get_zeroed_page(gfp_t gfp_mask) unsigned long __get_dma_pages(gfp_t gfp_mask, unsigned int order)
內(nèi)核釋放物理內(nèi)存的相關(guān)接口，這也是本小節(jié)的重點：
void __free_pages(struct page *page, unsigned int order); void free_pages(unsigned long addr, unsigned int order);
- __free_pages ： 同 alloc_pages 函數(shù)對應(yīng)，用于釋放 2 的 order 次冪個內(nèi)存頁，釋放的物理內(nèi)存區(qū)域起始地址由該區(qū)域中的第一個 page 實例指針表示，也就是參數(shù)里的 struct page *page 指針。
void __free_pages(struct page *page, unsigned int order) { if (put_page_testzero(page)) free_the_page(page, order); }
- free_pages：同 __get_free_pages 函數(shù)對應(yīng)，與 __free_pages 函數(shù)的區(qū)別是在釋放物理內(nèi)存時，使用了虛擬內(nèi)存地址而不是 page 指針。
void free_pages(unsigned long addr, unsigned int order) { if (addr != 0) { // 校驗虛擬內(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)存時需要非常謹(jǐn)慎小心，只能釋放屬于你自己的頁，傳遞了錯誤的 struct page 指針或者錯誤的虛擬內(nèi)存地址，或者傳遞錯了 order 值都可能會導(dǎo)致系統(tǒng)的崩潰。在內(nèi)核空間中，內(nèi)核是完全信賴自己的，這點和用戶空間不同。
另外內(nèi)核也提供了 __free_page 和 free_page 兩個宏，專門用于釋放單個物理內(nèi)存頁。
#define __free_page(page) __free_pages((page), 0) #define free_page(addr) free_pages((addr), 0)
我們可以看出無論是內(nèi)核定義的這些用于釋放內(nèi)存的宏或是輔助函數(shù)，它們最終會調(diào)用 __free_pages，這里正是釋放內(nèi)存的核心所在。
image.png
static inline void free_the_page(struct page *page, unsigned int order) { 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)存的流程是一樣的，在最開始首先都會檢查本次釋放或者分配的是否只是一個物理內(nèi)存頁（order = 0），如果是則直接釋放到 CPU 高速緩存列表 pcplist 中。如果不是則將內(nèi)存釋放回伙伴系統(tǒng)中。
struct zone { struct per_cpu_pages __percpu *per_cpu_pageset; } struct per_cpu_pages { int count; /* pcplist 里的頁面總數(shù) */ int high; /* pcplist 里的高水位線，count 超過 high 時，內(nèi)核會釋放 batch 個頁面到伙伴系統(tǒng)中*/ int batch; /* pcplist 里的頁面來自于伙伴系統(tǒng)，batch 定義了每次從伙伴系統(tǒng)獲取或者歸還多少個頁面*/ // CPU 高速緩存列表 pcplist，每個遷移類型對應(yīng)一個 pcplist struct list_head lists[NR_PCP_LISTS]; };
7.1 釋放內(nèi)存至 CPU 高速緩存列表 pcplist 中
/* * Free a 0-order page */ void free_unref_page(struct page *page) { unsigned long flags; // 獲取要釋放的物理內(nèi)存頁對應(yīng)的物理頁號 pfn unsigned long pfn = 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)核會通過 page_to_pfn 函數(shù)獲取要釋放內(nèi)存頁對應(yīng)的物理頁號，而物理頁號 pfn 的計算邏輯會根據(jù)內(nèi)存模型的不同而不同，關(guān)于 page_to_pfn 在不同內(nèi)存模型下的計算邏輯，大家可以回看下筆者之前文章 《深入理解 Linux 物理內(nèi)存管理》中的 “ 2. 從 CPU 角度看物理內(nèi)存模型 ” 小節(jié)。
最后通過 free_unref_page_commit 函數(shù)將內(nèi)存頁釋放至 CPU 高速緩存列表 pcplist 中，這里大家需要注意的是在釋放的過程中是不會響應(yīng)中斷的。
static void free_unref_page_commit(struct page *page, unsigned long pfn) { // 獲取內(nèi)存頁所在物理內(nèi)存區(qū)域 zone struct zone *zone = page_zone(page); // 運行當(dāng)前進(jìn)程的 CPU 高速緩存列表 pcplist struct per_cpu_pages *pcp; // 頁面的遷移類型 int migratetype; migratetype = get_pcppage_migratetype(page); // 內(nèi)核這里只會將 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)核這里會將 HIGHATOMIC 類型頁面當(dāng)做 MIGRATE_MOVABLE 類型處理 migratetype = MIGRATE_MOVABLE; } // 獲取運行當(dāng)前進(jìn)程的 CPU 高速緩存列表 pcplist pcp = &this_cpu_ptr(zone->pageset)->pcp; // 將要釋放的物理內(nèi)存頁添加到 pcplist 中 list_add(&page->lru, &pcp->lists[migratetype]); // pcplist 頁面計數(shù)加一 pcp->count++; // 如果 pcp 中的頁面總數(shù)超過了 high 水位線，則將 pcp 中的 batch 個頁面釋放回伙伴系統(tǒng)中 if (pcp->count >= pcp->high) { unsigned long batch = READ_ONCE(pcp->batch); // 釋放 batch 個頁面回伙伴系統(tǒng)中 free_pcppages_bulk(zone, batch, pcp); } }
這里筆者需要強(qiáng)調(diào)的是，內(nèi)核只會將 UNMOVABLE，MOVABLE，RECLAIMABLE 這三種頁面遷移類型放入 CPU 高速緩存列表 pcplist 中，其余的遷移類型均需釋放回伙伴系統(tǒng)。
enum migratetype { MIGRATE_UNMOVABLE, // 不可移動 MIGRATE_MOVABLE, // 可移動 MIGRATE_RECLAIMABLE, // 可回收 MIGRATE_PCPTYPES, // 屬于 CPU 高速緩存中的類型，PCP 是 per_cpu_pageset 的縮寫 MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, // 緊急內(nèi)存 #ifdef CONFIG_CMA MIGRATE_CMA, // 預(yù)留的連續(xù)內(nèi)存 CMA #endif #ifdef CONFIG_MEMORY_ISOLATION MIGRATE_ISOLATE, /* can't allocate from here */ #endif MIGRATE_TYPES // 不代表任何區(qū)域，只是單純的標(biāo)識遷移類型這個枚舉 };
關(guān)于頁面遷移類型的介紹，可回看本文 “1. 伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)” 小節(jié)的內(nèi)容。
通過 this_cpu_ptr 獲取運行當(dāng)前進(jìn)程的 CPU 高速緩存列表 pcplist，然后將要釋放的物理內(nèi)存頁添加到對應(yīng)遷移類型的 pcp->lists[migratetype]。
在 CPU 高速緩存列表 per_cpu_pages 中，每個遷移類型對應(yīng)一個 pcplist 。
如果當(dāng)前 pcplist 中的頁面數(shù)量 count 超過了規(guī)定的水位線 high 的值，說明現(xiàn)在 pcplist 中的頁面太多了，需要從 pcplist 中釋放 batch 個物理頁面到伙伴系統(tǒng)中。這個過程稱之為惰性合并。
根據(jù)本文 “4. 伙伴系統(tǒng)的內(nèi)存回收原理” 小節(jié)介紹的內(nèi)容，我們知道，單內(nèi)存頁直接釋放回伙伴系統(tǒng)會發(fā)生很多合并的動作，這里的惰性合并策略阻止了大量的無效合并操作。
7.2 伙伴系統(tǒng)回收內(nèi)存源碼實現(xiàn)
image.png
當(dāng)我們要釋放的內(nèi)存頁超過一頁（order > 0 ）時，內(nèi)核會將這些內(nèi)存頁回收至伙伴系統(tǒng)中，釋放內(nèi)存時伙伴系統(tǒng)的入口函數(shù)為 __free_pages_ok：
static void __free_pages_ok(struct page *page, unsigned int order) { unsigned long flags; int migratetype; // 獲取釋放內(nèi)存頁對應(yīng)的物理頁號 pfn unsigned long pfn = page_to_pfn(page); // 在將內(nèi)存頁回收至伙伴系統(tǒng)之前，需要將內(nèi)存頁 page 相關(guān)的無用屬性清理一下 if (!free_pages_prepare(page, order, true)) return; // 獲取頁面遷移類型，后續(xù)會將內(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)存的時候也是不響應(yīng)中斷的。
static void free_one_page(struct zone *zone, struct page *page, unsigned long pfn, unsigned int order, int migratetype) { // 加鎖 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); }
之前我們在 “4. 伙伴系統(tǒng)的內(nèi)存回收原理” 小節(jié)中介紹的伙伴系統(tǒng)內(nèi)存回收的全部邏輯就封裝在 __free_one_page 函數(shù)中，筆者這里建議大家在看下面相關(guān)源碼實現(xiàn)的內(nèi)容之前再去回顧下 5.3 小節(jié)的內(nèi)容。
下面我們還是以 5.3 小節(jié)中所舉的具體例子來剖析內(nèi)核如何將內(nèi)存釋放回伙伴系統(tǒng)中的完整實現(xiàn)過程。
在開始之前，筆者還是先把當(dāng)前伙伴系統(tǒng)中空閑內(nèi)存頁的真實物理視圖給大家貼出來方便大家對比，后面在查找需要合并的伙伴的時候需要拿這張圖來做對比才能清晰的理解：
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)時，內(nèi)核需要從內(nèi)存塊的當(dāng)前階（本例中 order = 0）開始在伙伴系統(tǒng) free_area[order] 中查找能夠合并的伙伴。
伙伴的定義筆者已經(jīng)在 “2. 到底什么是伙伴” 小節(jié)中詳細(xì)為大家介紹過了，伙伴的核心就是兩個尺寸大小相同并且在物理上連續(xù)的兩個空閑內(nèi)存塊，內(nèi)存塊可以由一個物理內(nèi)存頁組成的也可以是由多個物理內(nèi)存頁組成的。
如果在當(dāng)前階 free_area[order] 中找到了伙伴，則將釋放的內(nèi)存塊和它的伙伴內(nèi)存塊兩兩合并成一個新的內(nèi)存塊，隨后繼續(xù)到高階中去查找新內(nèi)存塊的伙伴，直到?jīng)]有伙伴可以合并為止。
image.png
/* * Freeing function for a buddy system allocator. */ static inline void __free_one_page(struct page *page, unsigned long pfn, struct zone *zone, unsigned int order, int migratetype) { // 釋放內(nèi)存塊與其伙伴內(nèi)存塊合并之后新內(nèi)存塊的 pfn unsigned long combined_pfn; // 伙伴內(nèi)存塊的 pfn unsigned long uninitialized_var(buddy_pfn); // 伙伴內(nèi)存塊的首頁 page 指針 struct page *buddy; // 伙伴系統(tǒng)中的最大分配階 unsigned int max_order; continue_merging: // 從釋放內(nèi)存塊的當(dāng)前分配階開始一直向高階合并內(nèi)存塊，直到不能合并為止 // 在本例中當(dāng)前分配階 order = 0，我們要釋放 page10 while (order < max_order - 1) { // 在 free_area[order] 中查找伙伴內(nèi)存塊的 pfn // 上圖步驟一中伙伴的 pfn 為 11 // 上圖步驟二中伙伴的 pfn 為 8 // 上圖步驟三中伙伴的 pfn 為 12 buddy_pfn = __find_buddy_pfn(pfn, order); // 根據(jù)偏移 buddy_pfn - pfn 計算伙伴內(nèi)存塊中的首頁 page 地址 // 步驟一伙伴首頁為 page11，步驟二伙伴首頁為 page8，步驟三伙伴首頁為 page12 buddy = page + (buddy_pfn - pfn); // 檢查伙伴 pfn 的有效性 if (!pfn_valid_within(buddy_pfn)) // 無效停止合并 goto done_merging; // 按照前面介紹的伙伴定義檢查是否為伙伴 if (!page_is_buddy(page, buddy, order)) // 不是伙伴停止合并 goto done_merging; // 將伙伴內(nèi)存塊從當(dāng)前 free_area[order] 列表中摘下，對比步驟一到步驟四 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，存儲在第一個 page 結(jié)構(gòu)中的 private 屬性中 set_page_order(page, order); // 將最終合并的內(nèi)存塊插入到伙伴系統(tǒng)對應(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ì)注釋，整個內(nèi)存釋放的過程還是不難理解的。
這里筆者想重點來講的是，內(nèi)核如何在 free_area 鏈表中查找伙伴內(nèi)存塊，以及如何判斷兩個內(nèi)存塊是否為伙伴關(guān)系。下面我們來一起看下這部分內(nèi)容：
image.png
7.3 如何查找伙伴
static inline unsigned long __find_buddy_pfn(unsigned long page_pfn, unsigned int order) { return page_pfn ^ (1 << order); }
內(nèi)核會通過 __find_buddy_pfn 函數(shù)根據(jù)當(dāng)前釋放內(nèi)存塊的 pfn，以及當(dāng)前釋放內(nèi)存塊的分配階 order 來確定其伙伴內(nèi)存塊的 pfn。
首先通過 1 << order 左移操作確定要查找伙伴內(nèi)存塊的分配階，因為伙伴關(guān)系最重要的一點就是它們必須是大小相等的兩個內(nèi)存塊。然后巧妙地通過與要釋放內(nèi)存塊的 pfn 進(jìn)行異或操作就得到了伙伴內(nèi)存塊的 pfn 。
7.4 如何判斷兩個內(nèi)存塊是否是伙伴
另外一個重要的輔助函數(shù)就是 page_is_buddy，內(nèi)核通過該函數(shù)來判斷給定兩個內(nèi)存塊是否為伙伴關(guān)系。筆者在 “2. 到底什么是伙伴” 小節(jié)中明確的給出了伙伴的定義，page_is_buddy 就是相關(guān)的內(nèi)核實現(xiàn)：
-
伙伴系統(tǒng)所管理的內(nèi)存頁必須是可用的，不能處于內(nèi)存空洞中，通過 page_is_guard 函數(shù)判斷。
-
伙伴必須是空閑的內(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)中。
-
兩個互為伙伴的內(nèi)存塊必須擁有相同的分配階 order，也就是它們之間的大小尺寸必須一致。通過
page_order(buddy) == order判斷 -
互為伙伴關(guān)系的內(nèi)存塊必須處于相同的物理內(nèi)存區(qū)域 zone 中。通過
page_zone_id(page) == page_zone_id(buddy)判斷。
同時滿足上述四點的兩個內(nèi)存塊即為伙伴關(guān)系，下面是內(nèi)核中關(guān)于判斷是否為伙伴關(guān)系的源碼實現(xiàn)：
static inline int page_is_buddy(struct page *page, struct page *buddy, unsigned int order) { if (page_is_guard(buddy) && page_order(buddy) == order) { if (page_zone_id(page) != page_zone_id(buddy)) return 0; return 1; } if (PageBuddy(buddy) && page_order(buddy) == order) { if (page_zone_id(page) != page_zone_id(buddy)) return 0; return 1; } return 0; }
總結(jié)
在本文的開頭，筆者首先為大家介紹了伙伴系統(tǒng)的核心數(shù)據(jù)結(jié)構(gòu)，目的是在介紹核心原理之前，先為大家構(gòu)建起伙伴系統(tǒng)的整個骨架。從整體上先認(rèn)識一下伙伴系統(tǒng)的全局樣貌。
image.png
然后又為大家闡述了伙伴系統(tǒng)中的這個伙伴到底是什么概念 ，以及如何通過 __find_buddy_pfn 來查找內(nèi)存塊的伙伴。如果通過 page_is_buddy 來判斷兩個內(nèi)存塊是否為伙伴關(guān)系。
在我們明白了伙伴系統(tǒng)的這些基本概念以及全局框架結(jié)構(gòu)之后，筆者詳細(xì)剖析了伙伴系統(tǒng)的內(nèi)存分配原理及其實現(xiàn)，其中重點著墨了從高階 freelist 鏈表到低階 freelist 鏈表的減半分裂過程實現(xiàn)，以及內(nèi)存分配失敗之后，伙伴系統(tǒng)的 fallback 過程實現(xiàn)。
image.png
最后又詳細(xì)剖析了伙伴系統(tǒng)內(nèi)存回收的原理以及實現(xiàn)，其中重點著墨了從低階 freelist 到高階 freelist 的合并過程。
image.png
好了，到這里關(guān)于伙伴系統(tǒng)的全部內(nèi)容就結(jié)束了，感謝大家的收看，我們下篇文章見~~~文章來源：http://www.zghlxwxcb.cn/news/detail-732740.html
本文轉(zhuǎn)自 https://mp.weixin.qq.com/s?__biz=Mzg2MzU3Mjc3Ng==&mid=2247487228&idx=1&sn=85e44fa5b090b29ab23ca6abf98da221&chksm=ce77c8bbf90041ad4958a3871a880a3f6d812e282530ea047d9eaf76d9f03aafb4b987a64ae9&scene=178&cur_album_id=2559805446807928833#rd，如有侵權(quán)，請聯(lián)系刪除。文章來源地址http://www.zghlxwxcb.cn/news/detail-732740.html
到了這里，關(guān)于Linux內(nèi)核源碼分析 (B.4) 深度剖析 Linux 伙伴系統(tǒng)的設(shè)計與實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
