在內(nèi)核初始化完成之后, 內(nèi)存管理的責(zé)任就由伙伴系統(tǒng)來(lái)承擔(dān). 伙伴系統(tǒng)基于一種相對(duì)簡(jiǎn)單然而令人吃驚的強(qiáng)大算法.

Linux內(nèi)核使用二進(jìn)制伙伴算法來(lái)管理和分配物理內(nèi)存頁(yè)面, 該算法由Knowlton設(shè)計(jì), 后來(lái)Knuth又進(jìn)行了更深刻的描述.

伙伴系統(tǒng)是一個(gè)結(jié)合了2的方冪個(gè)分配器和空閑緩沖區(qū)合并計(jì)技術(shù)的內(nèi)存分配方案, 其基本思想很簡(jiǎn)單. 內(nèi)存被分成含有很多頁(yè)面的大塊, 每一塊都是2個(gè)頁(yè)面大小的方冪. 如果找不到想要的塊, 一個(gè)大塊會(huì)被分成兩部分, 這兩部分彼此就成為伙伴. 其中一半被用來(lái)分配, 而另一半則空閑. 這些塊在以后分配的過(guò)程中會(huì)繼續(xù)被二分直至產(chǎn)生一個(gè)所需大小的塊. 當(dāng)一個(gè)塊被最終釋放時(shí), 其伙伴將被檢測(cè)出來(lái), 如果伙伴也空閑則合并兩者.

內(nèi)核如何記住哪些內(nèi)存塊是空閑的

分配空閑頁(yè)面的方法

影響分配器行為的眾多標(biāo)識(shí)位

內(nèi)存碎片的問(wèn)題和分配器如何處理碎片

伙伴系統(tǒng)的結(jié)構(gòu)

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

系統(tǒng)內(nèi)存中的每個(gè)物理內(nèi)存頁(yè)（頁(yè)幀），都對(duì)應(yīng)于一個(gè)struct page實(shí)例, 每個(gè)內(nèi)存域都關(guān)聯(lián)了一個(gè)struct zone的實(shí)例，其中保存了用于管理伙伴數(shù)據(jù)的主要數(shù)數(shù)組

//  http://lxr.free-electrons.com/source/include/linux/mmzone.h?v=4.7#L324
struct zone
{
     /* free areas of different sizes */
    struct free_area        free_area[MAX_ORDER];
};


struct free_area是一個(gè)伙伴系統(tǒng)的輔助數(shù)據(jù)結(jié)構(gòu).
struct free_area {
    struct list_head        free_list[MIGRATE_TYPES];
    unsigned long           nr_free;
};

?

伙伴系統(tǒng)的分配器維護(hù)空閑頁(yè)面所組成的塊, 這里每一塊都是2的方冪個(gè)頁(yè)面, 方冪的指數(shù)稱為階.

階是伙伴系統(tǒng)中一個(gè)非常重要的術(shù)語(yǔ). 它描述了內(nèi)存分配的數(shù)量單位. 內(nèi)存塊的長(zhǎng)度是2^0,order , 其中order的范圍從0到MAX_ORDER

zone->free_area[MAX_ORDER]數(shù)組中階作為各個(gè)元素的索引, 用于指定對(duì)應(yīng)鏈表中的連續(xù)內(nèi)存區(qū)包含多少個(gè)頁(yè)幀.

數(shù)組中第0個(gè)元素的階為0, 它的free_list鏈表域指向具有包含區(qū)為單頁(yè)(2^0 = 1)的內(nèi)存頁(yè)面鏈表

數(shù)組中第1個(gè)元素的free_list域管理的內(nèi)存區(qū)為兩頁(yè)(2^1 = 2)

第3個(gè)管理的內(nèi)存區(qū)為4頁(yè), 依次類推.

直到 2^MAXORDER-1個(gè)頁(yè)面大小的塊

?

?

最大階MAX_ORDER與FORCE_MAX_ZONEORDER配置選項(xiàng)

一般來(lái)說(shuō)MAX_ORDER默認(rèn)定義為11, 這意味著一次分配可以請(qǐng)求的頁(yè)數(shù)最大是2^11=2048.

/* Free memory management - zoned buddy allocator.  */
#ifndef CONFIG_FORCE_MAX_ZONEORDER
#define MAX_ORDER 11
#else
#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif
#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

但如果特定于體系結(jié)構(gòu)的代碼設(shè)置了FORCE_MAX_ZONEORDER配置選項(xiàng), 該值也可以手工改變

例如，IA-64系統(tǒng)上巨大的地址空間可以處理MAX_ORDER = 18的情形，而ARM或v850系統(tǒng)則使用更小的值(如8或9). 但這不一定是由計(jì)算機(jī)支持的內(nèi)存數(shù)量比較小引起的，也可能是內(nèi)存對(duì)齊方式的要求所導(dǎo)致

可以參考一些架構(gòu)的Kconfig文件如下

?

比如arm64體系結(jié)構(gòu)的Kconfig配置文件的描述

config FORCE_MAX_ZONEORDER
int
default "14" if (ARM64_64K_PAGES && TRANSPARENT_HUGEPAGE)
default "12" if (ARM64_16K_PAGES && TRANSPARENT_HUGEPAGE)
default "11"

內(nèi)存區(qū)是如何連接的

內(nèi)存區(qū)中第1頁(yè)內(nèi)的鏈表元素, 可用于將內(nèi)存區(qū)維持在鏈表中。因此，也不必引入新的數(shù)據(jù)結(jié)構(gòu)來(lái)管理物理上連續(xù)的頁(yè)，否則這些頁(yè)不可能在同一內(nèi)存區(qū)中. 如下圖所示

?

?
?

伙伴不必是彼此連接的. 如果一個(gè)內(nèi)存區(qū)在分配其間分解為兩半, 內(nèi)核會(huì)自動(dòng)將未用的一半加入到對(duì)應(yīng)的鏈表中.

如果在未來(lái)的某個(gè)時(shí)刻, 由于內(nèi)存釋放的緣故, 兩個(gè)內(nèi)存區(qū)都處于空閑狀態(tài), 可通過(guò)其地址判斷其是否為伙伴. 管理工作較少, 是伙伴系統(tǒng)的一個(gè)主要優(yōu)點(diǎn).

基于伙伴系統(tǒng)的內(nèi)存管理專注于某個(gè)結(jié)點(diǎn)的某個(gè)內(nèi)存域, 例如, DMA或高端內(nèi)存域. 但所有內(nèi)存域和結(jié)點(diǎn)的伙伴系統(tǒng)都通過(guò)備用分配列表連接起來(lái).

下圖說(shuō)明了這種關(guān)系.

?

?

最后要注意, 有關(guān)伙伴系統(tǒng)和當(dāng)前狀態(tài)的信息可以在/proc/buddyinfo中獲取

?

?

內(nèi)核中很多時(shí)候要求分配連續(xù)頁(yè). 為快速檢測(cè)內(nèi)存中的連續(xù)區(qū)域, 內(nèi)核采用了一種古老而歷經(jīng)檢驗(yàn)的技術(shù): 伙伴系統(tǒng)

系統(tǒng)中的空閑內(nèi)存塊總是兩兩分組, 每組中的兩個(gè)內(nèi)存塊稱作伙伴. 伙伴的分配可以是彼此獨(dú)立的. 但如果兩個(gè)伙伴都是空閑的, 內(nèi)核會(huì)將其合并為一個(gè)更大的內(nèi)存塊, 作為下一層次上某個(gè)內(nèi)存塊的伙伴.

下圖示范了該系統(tǒng), 圖中給出了一對(duì)伙伴, 初始大小均為8頁(yè). 即系統(tǒng)中所有的頁(yè)面都是8頁(yè)的.

?

?

內(nèi)核對(duì)所有大小相同的伙伴（1、2、4、8、16或其他數(shù)目的頁(yè)），都放置到同一個(gè)列表中管理. 各有8頁(yè)的一對(duì)伙伴也在相應(yīng)的列表中.

如果系統(tǒng)現(xiàn)在需要8個(gè)頁(yè)幀, 則將16個(gè)頁(yè)幀組成的塊拆分為兩個(gè)伙伴. 其中一塊用于滿足應(yīng)用程序的請(qǐng)求, 而剩余的8個(gè)頁(yè)幀則放置到對(duì)應(yīng)8頁(yè)大小內(nèi)存塊的列表中.

如果下一個(gè)請(qǐng)求只需要2個(gè)連續(xù)頁(yè)幀, 則由8頁(yè)組成的塊會(huì)分裂成2個(gè)伙伴, 每個(gè)包含4個(gè)頁(yè)幀. 其中一塊放置回伙伴列表中，而另一個(gè)再次分裂成2個(gè)伙伴, 每個(gè)包含2頁(yè)。其中一個(gè)回到伙伴系統(tǒng)，另一個(gè)則傳遞給應(yīng)用程序.

在應(yīng)用程序釋放內(nèi)存時(shí), 內(nèi)核可以直接檢查地址, 來(lái)判斷是否能夠創(chuàng)建一組伙伴, 并合并為一個(gè)更大的內(nèi)存塊放回到伙伴列表中, 這剛好是內(nèi)存塊分裂的逆過(guò)程。這提高了較大內(nèi)存塊可用的可能性.

在系統(tǒng)長(zhǎng)期運(yùn)行時(shí)，服務(wù)器運(yùn)行幾個(gè)星期乃至幾個(gè)月是很正常的，許多桌面系統(tǒng)也趨向于長(zhǎng)期開機(jī)運(yùn)行，那么會(huì)發(fā)生稱為碎片的內(nèi)存管理問(wèn)題。頻繁的分配和釋放頁(yè)幀可能導(dǎo)致一種情況：系統(tǒng)中有若干頁(yè)幀是空閑的，但卻散布在物理地址空間的各處。換句話說(shuō)，系統(tǒng)中缺乏連續(xù)頁(yè)幀組成的較大的內(nèi)存塊，而從性能上考慮，卻又很需要使用較大的連續(xù)內(nèi)存塊。通過(guò)伙伴系統(tǒng)可以在某種程度上減少這種效應(yīng)，但無(wú)法完全消除。如果在大塊的連續(xù)內(nèi)存中間剛好有一個(gè)頁(yè)幀分配出去，很顯然這兩塊空閑的內(nèi)存是無(wú)法合并的.

在內(nèi)核版本2.6.24之后, 增加了一些有效措施來(lái)防止內(nèi)存碎片.

避免碎片

在第1章給出的簡(jiǎn)化說(shuō)明中, 一個(gè)雙鏈表即可滿足伙伴系統(tǒng)的所有需求. 在內(nèi)核版本2.6.23之前, 的確是這樣. 但在內(nèi)核2.6.24開發(fā)期間, 內(nèi)核開發(fā)者對(duì)伙伴系統(tǒng)的爭(zhēng)論持續(xù)了相當(dāng)長(zhǎng)時(shí)間. 這是因?yàn)榛锇橄到y(tǒng)是內(nèi)核最值得尊敬的一部分，對(duì)它的改動(dòng)不會(huì)被大家輕易接受

內(nèi)存碎片

伙伴系統(tǒng)的基本原理已經(jīng)在第1章中討論過(guò)，其方案在最近幾年間確實(shí)工作得非常好。但在Linux內(nèi)存管理方面，有一個(gè)長(zhǎng)期存在的問(wèn)題：在系統(tǒng)啟動(dòng)并長(zhǎng)期運(yùn)行后，物理內(nèi)存會(huì)產(chǎn)生很多碎片。該情形如下圖所示

?

?

假定內(nèi)存由60頁(yè)組成，這顯然不是超級(jí)計(jì)算機(jī)，但用于示例卻足夠了。左側(cè)的地址空間中散布著空閑頁(yè)。盡管大約25%的物理內(nèi)存仍然未分配，但最大的連續(xù)空閑區(qū)只有一頁(yè). 這對(duì)用戶空間應(yīng)用程序沒(méi)有問(wèn)題：其內(nèi)存是通過(guò)頁(yè)表映射的，無(wú)論空閑頁(yè)在物理內(nèi)存中的分布如何，應(yīng)用程序看到的內(nèi)存 似乎總是連續(xù)的。右圖給出的情形中，空閑頁(yè)和使用頁(yè)的數(shù)目與左圖相同，但所有空閑頁(yè)都位于一個(gè)連續(xù)區(qū)中。

但對(duì)內(nèi)核來(lái)說(shuō)，碎片是一個(gè)問(wèn)題. 由于(大多數(shù))物理內(nèi)存一致映射到地址空間的內(nèi)核部分, 那么在左圖的場(chǎng)景中, 無(wú)法映射比一頁(yè)更大的內(nèi)存區(qū). 盡管許多時(shí)候內(nèi)核都分配的是比較小的內(nèi)存, 但也有時(shí)候需要分配多于一頁(yè)的內(nèi)存. 顯而易見(jiàn), 在分配較大內(nèi)存的情況下, 右圖中所有已分配頁(yè)和空閑頁(yè)都處于連續(xù)內(nèi)存區(qū)的情形，是更為可取的.

很有趣的一點(diǎn)是, 在大部分內(nèi)存仍然未分配時(shí), 就也可能發(fā)生碎片問(wèn)題. 考慮圖3-25的情形.

只分配了4頁(yè)，但可分配的最大連續(xù)區(qū)只有8頁(yè)，因?yàn)榛锇橄到y(tǒng)所能工作的分配范圍只能是2的冪次.

?

?

我提到內(nèi)存碎片只涉及內(nèi)核，這只是部分正確的。大多數(shù)現(xiàn)代CPU都提供了使用巨型頁(yè)的可能性，比普通頁(yè)大得多。這對(duì)內(nèi)存使用密集的應(yīng)用程序有好處。在使用更大的頁(yè)時(shí)，地址轉(zhuǎn)換后備緩沖器只需處理較少的項(xiàng)，降低了TLB緩存失效的可能性。但分配巨型頁(yè)需要連續(xù)的空閑物理內(nèi)存！

很長(zhǎng)時(shí)間以來(lái)，物理內(nèi)存的碎片確實(shí)是Linux的弱點(diǎn)之一。盡管已經(jīng)提出了許多方法，但沒(méi)有哪個(gè)方法能夠既滿足Linux需要處理的各種類型工作負(fù)荷提出的苛刻需求，同時(shí)又對(duì)其他事務(wù)影響不大。

依據(jù)可移動(dòng)性組織頁(yè)

在內(nèi)核2.6.24開發(fā)期間，防止碎片的方法最終加入內(nèi)核。在我討論具體策略之前，有一點(diǎn)需要澄清。

文件系統(tǒng)也有碎片，該領(lǐng)域的碎片問(wèn)題主要通過(guò)碎片合并工具解決。它們分析文件系統(tǒng)，重新排序已分配存儲(chǔ)塊，從而建立較大的連續(xù)存儲(chǔ)區(qū). 理論上，該方法對(duì)物理內(nèi)存也是可能的，但由于許多物理內(nèi)存頁(yè)不能移動(dòng)到任意位置，阻礙了該方法的實(shí)施。因此，內(nèi)核的方法是反碎片(anti-fragmentation), 即試圖從最初開始盡可能防止碎片.

反碎片的工作原理如何?

為理解該方法，我們必須知道內(nèi)核將已分配頁(yè)劃分為下面3種不同類型。

頁(yè)的可移動(dòng)性，依賴該頁(yè)屬于3種類別的哪一種. 內(nèi)核使用的反碎片技術(shù), 即基于將具有相同可移動(dòng)性的頁(yè)分組的思想.

為什么這種方法有助于減少碎片?

由于頁(yè)無(wú)法移動(dòng), 導(dǎo)致在原本幾乎全空的內(nèi)存區(qū)中無(wú)法進(jìn)行連續(xù)分配. 根據(jù)頁(yè)的可移動(dòng)性, 將其分配到不同的列表中, 即可防止這種情形. 例如, 不可移動(dòng)的頁(yè)不能位于可移動(dòng)內(nèi)存區(qū)的中間, 否則就無(wú)法從該內(nèi)存區(qū)分配較大的連續(xù)內(nèi)存塊.

想一下, 上圖中大多數(shù)空閑頁(yè)都屬于可回收的類別, 而分配的頁(yè)則是不可移動(dòng)的. 如果這些頁(yè)聚集到兩個(gè)不同的列表中, 如下圖所示. 在不可移動(dòng)頁(yè)中仍然難以找到較大的連續(xù)空閑空間, 但對(duì)可回收的頁(yè), 就容易多了.

?

?

但要注意, 從最初開始, 內(nèi)存并未劃分為可移動(dòng)性不同的區(qū). 這些是在運(yùn)行時(shí)形成的. 內(nèi)核的另一種方法確實(shí)將內(nèi)存分區(qū), 分別用于可移動(dòng)頁(yè)和不可移動(dòng)頁(yè)的分配, 我會(huì)下文討論其工作原理. 但這種劃分對(duì)這里描述的方法是不必要的

避免碎片數(shù)據(jù)結(jié)構(gòu)

enum {
        MIGRATE_UNMOVABLE,
        MIGRATE_MOVABLE,
        MIGRATE_RECLAIMABLE,
        MIGRATE_PCPTYPES,       /* the number of types on the pcp lists */
        MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES,
#ifdef CONFIG_CMA
        /*
         * MIGRATE_CMA migration type is designed to mimic the way
         * ZONE_MOVABLE works.  Only movable pages can be allocated
         * from MIGRATE_CMA pageblocks and page allocator never
         * implicitly change migration type of MIGRATE_CMA pageblock.
         *
         * The way to use it is to change migratetype of a range of
         * pageblocks to MIGRATE_CMA which can be done by
         * __free_pageblock_cma() function.  What is important though
         * is that a range of pageblocks must be aligned to
         * MAX_ORDER_NR_PAGES should biggest page be bigger then
         * a single pageblock.
         */
        MIGRATE_CMA,
#endif
#ifdef CONFIG_MEMORY_ISOLATION
        MIGRATE_ISOLATE,        /* can't allocate from here */
#endif
        MIGRATE_TYPES
};

對(duì)于MIGRATE_CMA類型, 其中在我們使用ARM等嵌入式Linux系統(tǒng)的時(shí)候, 一個(gè)頭疼的問(wèn)題是GPU, Camera, HDMI等都需要預(yù)留大量連續(xù)內(nèi)存，這部分內(nèi)存平時(shí)不用，但是一般的做法又必須先預(yù)留著. 目前, Marek Szyprowski和Michal Nazarewicz實(shí)現(xiàn)了一套全新的Contiguous Memory Allocator. 通過(guò)這套機(jī)制, 我們可以做到不預(yù)留內(nèi)存，這些內(nèi)存平時(shí)是可用的，只有當(dāng)需要的時(shí)候才被分配給Camera，HDMI等設(shè)備. 內(nèi)核為此提供了函數(shù)is_migrate_cma來(lái)檢測(cè)當(dāng)前類型是否為MIGRATE_CMA, 該函數(shù)定義在include/linux/mmzone.h?v=4.7, line 69

/* In mm/page_alloc.c; keep in sync also with show_migration_types() there */
extern char * const migratetype_names[MIGRATE_TYPES];

#ifdef CONFIG_CMA
#  define is_migrate_cma(migratetype) unlikely((migratetype) == MIGRATE_CMA)
#else
#  define is_migrate_cma(migratetype) false
#endif

對(duì)伙伴系統(tǒng)數(shù)據(jù)結(jié)構(gòu)的主要調(diào)整, 是將空閑列表分解為MIGRATE_TYPE個(gè)列表, 可以參見(jiàn)free_area的定義include/linux/mmzone.h?v=4.7, line 88

struct free_area
{
    struct list_head        free_list[MIGRATE_TYPES];
    unsigned long           nr_free;
};
nr_free統(tǒng)計(jì)了所有列表上空閑頁(yè)的數(shù)目，而每種遷移類型都對(duì)應(yīng)于一個(gè)空閑列表
宏for_each_migratetype_order(order, type)可用于迭代指定遷移類型的所有分配階
#define for_each_migratetype_order(order, type) \
        for (order = 0; order < MAX_ORDER; order++) \
                for (type = 0; type < MIGRATE_TYPES; type++)

遷移備用列表fallbacks

如果內(nèi)核無(wú)法滿足針對(duì)某一給定遷移類型的分配請(qǐng)求, 會(huì)怎么樣?

此前已經(jīng)出現(xiàn)過(guò)一個(gè)類似的問(wèn)題, 即特定的NUMA內(nèi)存域無(wú)法滿足分配請(qǐng)求時(shí). 我們需要從其他內(nèi)存域中選擇一個(gè)代價(jià)最低的內(nèi)存域完成內(nèi)存的分配, 因此內(nèi)核在內(nèi)存的結(jié)點(diǎn)pg_data_t中提供了一個(gè)備用內(nèi)存域列表zonelists.

內(nèi)核在內(nèi)存遷移的過(guò)程中處理這種情況下的做法是類似的. 提供了一個(gè)備用列表fallbacks, 規(guī)定了在指定列表中無(wú)法滿足分配請(qǐng)求時(shí). 接下來(lái)應(yīng)使用哪一種遷移類型, 定義在mm/page_alloc.c?v=4.7, line 1799

/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 * 該數(shù)組描述了指定遷移類型的空閑列表耗盡時(shí)
 * 其他空閑列表在備用列表中的次序
 */
static int fallbacks[MIGRATE_TYPES][4] = {
    //  分配不可移動(dòng)頁(yè)失敗的備用列表
    [MIGRATE_UNMOVABLE]   = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_TYPES },
    //  分配可回收頁(yè)失敗時(shí)的備用列表
    [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_TYPES },
    //  分配可移動(dòng)頁(yè)失敗時(shí)的備用列表
    [MIGRATE_MOVABLE]     = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES },
#ifdef CONFIG_CMA
    [MIGRATE_CMA]     = { MIGRATE_TYPES }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
    [MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
#endif
};

該數(shù)據(jù)結(jié)構(gòu)大體上是自明的 : 每一行對(duì)應(yīng)一個(gè)類型的備用搜索域的順序, 在內(nèi)核想要分配不可移動(dòng)頁(yè)MIGRATE_UNMOVABLE時(shí), 如果對(duì)應(yīng)鏈表為空, 則遍歷fallbacks[MIGRATE_UNMOVABLE], 首先后退到可回收頁(yè)鏈表MIGRATE_RECLAIMABLE, 接下來(lái)到可移動(dòng)頁(yè)鏈表MIGRATE_MOVABLE, 最后到緊急分配鏈表MIGRATE_TYPES.

pageblock_order變量

全局變量和輔助函數(shù)盡管頁(yè)可移動(dòng)性分組特性總是編譯到內(nèi)核中，但只有在系統(tǒng)中有足夠內(nèi)存可以分配到多個(gè)遷移類型對(duì)應(yīng)的鏈表時(shí)，才是有意義的。由于每個(gè)遷移鏈表都應(yīng)該有適當(dāng)數(shù)量的內(nèi)存，內(nèi)核需要定義”適當(dāng)”的概念. 這是通過(guò)兩個(gè)全局變量pageblock_order和pageblock_nr_pages提供的. 第一個(gè)表示內(nèi)核認(rèn)為是”大”的一個(gè)分配階, pageblock_nr_pages則表示該分配階對(duì)應(yīng)的頁(yè)數(shù)。如果體系結(jié)構(gòu)提供了巨型頁(yè)機(jī)制, 則pageblock_order通常定義為巨型頁(yè)對(duì)應(yīng)的分配階. 定義在include/linux/pageblock-flags.h?v=4.7, line 44

#ifdef CONFIG_HUGETLB_PAGE

    #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE

        /* Huge page sizes are variable */
        extern unsigned int pageblock_order;

    #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */

    /* Huge pages are a constant size */
        #define pageblock_order         HUGETLB_PAGE_ORDER

    #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */

#else /* CONFIG_HUGETLB_PAGE */

    /* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
    #define pageblock_order         (MAX_ORDER-1)

#endif /* CONFIG_HUGETLB_PAGE */

#define pageblock_nr_pages      (1UL << pageblock_order)

在IA-32體系結(jié)構(gòu)上, 巨型頁(yè)長(zhǎng)度是4MB, 因此每個(gè)巨型頁(yè)由1024個(gè)普通頁(yè)組成, 而HUGETLB_PAGE_ORDER則定義為10. 相比之下, IA-64體系結(jié)構(gòu)允許設(shè)置可變的普通和巨型頁(yè)長(zhǎng)度, 因此HUGETLB_PAGE_ORDER的值取決于內(nèi)核配置.

如果體系結(jié)構(gòu)不支持巨型頁(yè), 則將其定義為第二高的分配階, 即MAX_ORDER - 1

/* If huge pages are not used, group by MAX_ORDER_NR_PAGES */
#define pageblock_order         (MAX_ORDER-1)

如果各遷移類型的鏈表中沒(méi)有一塊較大的連續(xù)內(nèi)存, 那么頁(yè)面遷移不會(huì)提供任何好處, 因此在可用內(nèi)存太少時(shí)內(nèi)核會(huì)關(guān)閉該特性. 這是在build_all_zonelists函數(shù)中檢查的, 該函數(shù)用于初始化內(nèi)存域列表. 如果沒(méi)有足夠的內(nèi)存可用, 則全局變量page_group_by_mobility_disabled設(shè)置為0, 否則設(shè)置為1.

內(nèi)核如何知道給定的分配內(nèi)存屬于何種遷移類型?

我們將在以后講解, 有關(guān)各個(gè)內(nèi)存分配的細(xì)節(jié)都通過(guò)分配掩碼指定.

內(nèi)核提供了兩個(gè)標(biāo)志，分別用于表示分配的內(nèi)存是可移動(dòng)的(__GFP_MOVABLE)或可回收的(__GFP_RECLAIMABLE).

gfpflags_to_migratetype函數(shù)

/* Convert GFP flags to their corresponding migrate type */
static inline int allocflags_to_migratetype(gfp_t gfp_flags)
{
    WARN_ON((gfp_flags & GFP_MOVABLE_MASK) == GFP_MOVABLE_MASK);

    if (unlikely(page_group_by_mobility_disabled))
        return MIGRATE_UNMOVABLE;

    /* Group based on mobility */
    return (((gfp_flags & __GFP_MOVABLE) != 0) << 1) |
        ((gfp_flags & __GFP_RECLAIMABLE) != 0);
}

如果停用了頁(yè)面遷移特性, 則所有的頁(yè)都是不可移動(dòng)的. 否則. 該函數(shù)的返回值可以直接用作free_area.free_list的數(shù)組索引.

pageblock_flags變量與其函數(shù)接口

最后要注意, 每個(gè)內(nèi)存域都提供了一個(gè)特殊的字段, 可以跟蹤包含pageblock_nr_pages個(gè)頁(yè)的內(nèi)存區(qū)的屬性. 即zone->pageblock_flags字段, 當(dāng)前只有與頁(yè)可移動(dòng)性相關(guān)的代碼使用, 參見(jiàn)include/linux/mmzone.h?v=4.7, line 367

struct zone
{
#ifndef CONFIG_SPARSEMEM
    /*
     * Flags for a pageblock_nr_pages block. See pageblock-flags.h.
     * In SPARSEMEM, this map is stored in struct mem_section
     */
    unsigned long       *pageblock_flags;
#endif /* CONFIG_SPARSEMEM */
};

在初始化期間, 內(nèi)核自動(dòng)確保對(duì)內(nèi)存域中的每個(gè)不同的遷移類型分組, 在pageblock_flags中都分配了足夠存儲(chǔ)NR_PAGEBLOCK_BITS個(gè)比特位的空間。當(dāng)前，表示一個(gè)連續(xù)內(nèi)存區(qū)的遷移類型需要3個(gè)比特位, 參見(jiàn)include/linux/pageblock-flags.h?v=4.7, line 28

/* Bit indices that affect a whole block of pages */
enum pageblock_bits {
    PB_migrate,
    PB_migrate_end = PB_migrate + 3 - 1,
            /* 3 bits required for migrate types */
    PB_migrate_skip,/* If set the block is skipped by compaction */

    /*
     * Assume the bits will always align on a word. If this assumption
     * changes then get/set pageblock needs updating.
     */
    NR_PAGEBLOCK_BITS
};

內(nèi)核提供set_pageblock_migratetype負(fù)責(zé)設(shè)置以page為首的一個(gè)內(nèi)存區(qū)的遷移類型, 該函數(shù)定義在mm/page_alloc.c?v=4.7, line 458, 如下所示

void set_pageblock_migratetype(struct page *page, int migratetype)
{
    if (unlikely(page_group_by_mobility_disabled &&
             migratetype < MIGRATE_PCPTYPES))
        migratetype = MIGRATE_UNMOVABLE;

    set_pageblock_flags_group(page, (unsigned long)migratetype,
                    PB_migrate, PB_migrate_end);
}

migratetype參數(shù)可以通過(guò)上文介紹的gfpflags_to_migratetype輔助函數(shù)構(gòu)建. 請(qǐng)注意很重要的一點(diǎn), 頁(yè)的遷移類型是預(yù)先分配好的, 對(duì)應(yīng)的比特位總是可用, 與頁(yè)是否由伙伴系統(tǒng)管理無(wú)關(guān). 在釋放內(nèi)存時(shí)，頁(yè)必須返回到正確的遷移鏈表。這之所以可行，是因?yàn)槟軌驈膅et_pageblock_migratetype獲得所需的信息. 參見(jiàn)include/linux/mmzone.h?v=4.7, line 84

#define get_pageblock_migratetype(page)                                 \
        get_pfnblock_flags_mask(page, page_to_pfn(page),                \
                        PB_migrate_end, MIGRATETYPE_MASK)

最后請(qǐng)注意, 在各個(gè)遷移鏈表之間, 當(dāng)前的頁(yè)面分配狀態(tài)可以從/proc/pagetypeinfo獲得.

初始化基于可移動(dòng)性的分組

在內(nèi)存子系統(tǒng)初始化期間, memmap_init_zone負(fù)責(zé)處理內(nèi)存域的page實(shí)例. 該函數(shù)完成了一些不怎么有趣的標(biāo)準(zhǔn)初始化工作，但其中有一件是實(shí)質(zhì)性的，即所有的頁(yè)最初都標(biāo)記為可移動(dòng)的. 參見(jiàn)mm/page_alloc.c?v=4.7, line 5224

/*
 * Initially all pages are reserved - free ones are freed
 * up by free_all_bootmem() once the early boot process is
 * done. Non-atomic initialization, single-pass.
 */
void __meminit memmap_init_zone(unsigned long size, int nid, unsigned long zone,
        unsigned long start_pfn, enum memmap_context context)
{
    /*  ......  */

    for (pfn = start_pfn; pfn < end_pfn; pfn++) {
        /*  ......  */
not_early:
        if (!(pfn & (pageblock_nr_pages - 1))) {
            struct page *page = pfn_to_page(pfn);

            __init_single_page(page, pfn, zone, nid);
            set_pageblock_migratetype(page, MIGRATE_MOVABLE);
        } else {
            __init_single_pfn(pfn, zone, nid);
        }
    }
}

在分配內(nèi)存時(shí), 如果必須”盜取”不同于預(yù)定遷移類型的內(nèi)存區(qū), 內(nèi)核在策略上傾向于”盜取”更大的內(nèi)存區(qū). 由于所有頁(yè)最初都是可移動(dòng)的, 那么在內(nèi)核分配不可移動(dòng)的內(nèi)存區(qū)時(shí), 則必須”盜取”.

實(shí)際上, 在啟動(dòng)期間分配可移動(dòng)內(nèi)存區(qū)的情況較少, 那么分配器有很高的幾率分配長(zhǎng)度最大的內(nèi)存區(qū), 并將其從可移動(dòng)列表轉(zhuǎn)換到不可移動(dòng)列表. 由于分配的內(nèi)存區(qū)長(zhǎng)度是最大的, 因此不會(huì)向可移動(dòng)內(nèi)存中引入碎片.

總而言之, 這種做法避免了啟動(dòng)期間內(nèi)核分配的內(nèi)存(經(jīng)常在系統(tǒng)的整個(gè)運(yùn)行時(shí)間都不釋放)散布到物理內(nèi)存各處, 從而使其他類型的內(nèi)存分配免受碎片的干擾，這也是頁(yè)可移動(dòng)性分組框架的最重要的目標(biāo)之一.

分配器API

分配內(nèi)存的接口

就伙伴系統(tǒng)的接口而言, NUMA或UMA體系結(jié)構(gòu)是沒(méi)有差別的, 二者的調(diào)用語(yǔ)法都是相同的.

所有函數(shù)的一個(gè)共同點(diǎn)是 : 只能分配2的整數(shù)冪個(gè)頁(yè).

因此，接口中不像C標(biāo)準(zhǔn)庫(kù)的malloc函數(shù)或bootmem和memblock分配器那樣指定了所需內(nèi)存大小作為參數(shù). 相反, 必須指定的是分配階, 伙伴系統(tǒng)將在內(nèi)存中分配2^0 rder頁(yè). 內(nèi)核中細(xì)粒度的分配只能借助于slab分配器(或者slub、slob分配器), 后者基于伙伴系統(tǒng)

?

在空閑內(nèi)存無(wú)法滿足請(qǐng)求以至于分配失敗的情況下，所有上述函數(shù)都返回空指針(比如alloc_pages和alloc_page)或者0(比如get_zeroed_page、__get_free_pages和__get_free_page).

因此內(nèi)核在各次分配之后都必須檢查返回的結(jié)果. 這種慣例與設(shè)計(jì)得很好的用戶層應(yīng)用程序沒(méi)什么不同, 但在內(nèi)核中忽略檢查會(huì)導(dǎo)致嚴(yán)重得多的故障

內(nèi)核除了伙伴系統(tǒng)函數(shù)之外, 還提供了其他內(nèi)存管理函數(shù). 它們以伙伴系統(tǒng)為基礎(chǔ), 但并不屬于伙伴分配器自身. 這些函數(shù)包括vmalloc和vmalloc_32, 使用頁(yè)表將不連續(xù)的內(nèi)存映射到內(nèi)核地址空間中, 使之看上去是連續(xù)的.

還有一組kmalloc類型的函數(shù), 用于分配小于一整頁(yè)的內(nèi)存區(qū). 其實(shí)現(xiàn).

釋放函數(shù)

有4個(gè)函數(shù)用于釋放不再使用的頁(yè)，與所述函數(shù)稍有不同

?

分配掩碼(gfp_mask標(biāo)志)

分配掩碼

前述所有函數(shù)中強(qiáng)制使用的mask參數(shù)，到底是什么語(yǔ)義?

我們知道Linux將內(nèi)存劃分為內(nèi)存域. 內(nèi)核提供了所謂的內(nèi)存域修飾符(zone modifier)(在掩碼的最低4個(gè)比特位定義), 來(lái)指定從哪個(gè)內(nèi)存域分配所需的頁(yè).

內(nèi)核使用宏的方式定義了這些掩碼, 一個(gè)掩碼的定義被劃分為3個(gè)部分進(jìn)行定義, 我們會(huì)逐步展開來(lái)講解, 參見(jiàn)include/linux/gfp.h?v=4.7, line 12~374, 共計(jì)26個(gè)掩碼信息, 因此后面__GFP_BITS_SHIFT = 26.

掩碼分類

Linux中這些掩碼標(biāo)志gfp_mask分為3種類型 :

?

內(nèi)核中掩碼的定義

內(nèi)核中的定義方式

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7

/*  line 12 ~ line 44  第一部分
 *  定義可掩碼所在位的信息, 每個(gè)掩碼對(duì)應(yīng)一位為1
 *  定義形式為  #define  ___GFP_XXX      0x01u
 */
/* Plain integer GFP bitmasks. Do not use this directly. */
#define ___GFP_DMA              0x01u
#define ___GFP_HIGHMEM          0x02u
#define ___GFP_DMA32            0x04u
#define ___GFP_MOVABLE          0x08u
/*  ......  */

/*  line 46 ~ line 192  第二部分
 *  定義掩碼和MASK信息, 第二部分的某些宏可能是第一部分一個(gè)或者幾個(gè)的組合
 *  定義形式為  #define  __GFP_XXX        ((__force gfp_t)___GFP_XXX)
 */
#define __GFP_DMA       ((__force gfp_t)___GFP_DMA)
#define __GFP_HIGHMEM   ((__force gfp_t)___GFP_HIGHMEM)
#define __GFP_DMA32     ((__force gfp_t)___GFP_DMA32)
#define __GFP_MOVABLE   ((__force gfp_t)___GFP_MOVABLE)  /* ZONE_MOVABLE allowed */
#define GFP_ZONEMASK    (__GFP_DMA|__GFP_HIGHMEM|__GFP_DMA32|__GFP_MOVABLE)

/*  line 194 ~ line 260  第三部分
 *  定義掩碼
 *  定義形式為  #define  GFP_XXX      __GFP_XXX
 */
#define GFP_DMA         __GFP_DMA
#define GFP_DMA32       __GFP_DMA32

其中GFP縮寫的意思為獲取空閑頁(yè)(get free page), __GFP_MOVABLE不表示物理內(nèi)存域, 但通知內(nèi)核應(yīng)在特殊的虛擬內(nèi)存域ZONE_MOVABLE進(jìn)行相應(yīng)的分配.

定義掩碼位

我們首先來(lái)看第一部分, 內(nèi)核源代碼中定義在include/linux/gfp.h?v=4.7, line 18 ~ line 44, 共計(jì)26個(gè)掩碼信息.

/* Plain integer GFP bitmasks. Do not use this directly. */
//  區(qū)域修飾符
#define ___GFP_DMA              0x01u
#define ___GFP_HIGHMEM          0x02u
#define ___GFP_DMA32            0x04u

//  行為修飾符
#define ___GFP_MOVABLE          0x08u       /* 頁(yè)是可移動(dòng)的 */
#define ___GFP_RECLAIMABLE      0x10u       /* 頁(yè)是可回收的 */
#define ___GFP_HIGH             0x20u       /* 應(yīng)該訪問(wèn)緊急分配池？ */
#define ___GFP_IO               0x40u       /* 可以啟動(dòng)物理IO？ */
#define ___GFP_FS               0x80u       /* 可以調(diào)用底層文件系統(tǒng)？ */
#define ___GFP_COLD             0x100u     /* 需要非緩存的冷頁(yè) */
#define ___GFP_NOWARN           0x200u     /* 禁止分配失敗警告 */
#define ___GFP_REPEAT           0x400u     /* 重試分配，可能失敗 */
#define ___GFP_NOFAIL           0x800u     /* 一直重試，不會(huì)失敗 */
#define ___GFP_NORETRY          0x1000u   /* 不重試，可能失敗 */
#define ___GFP_MEMALLOC         0x2000u     /* 使用緊急分配鏈表 */
#define ___GFP_COMP             0x4000u   /* 增加復(fù)合頁(yè)元數(shù)據(jù) */
#define ___GFP_ZERO             0x8000u   /* 成功則返回填充字節(jié)0的頁(yè) */
//  類型修飾符
#define ___GFP_NOMEMALLOC       0x10000u     /* 不使用緊急分配鏈表 */
#define ___GFP_HARDWALL         0x20000u     /* 只允許在進(jìn)程允許運(yùn)行的CPU所關(guān)聯(lián)的結(jié)點(diǎn)分配內(nèi)存 */
#define ___GFP_THISNODE         0x40000u     /* 沒(méi)有備用結(jié)點(diǎn)，沒(méi)有策略 */
#define ___GFP_ATOMIC           0x80000u    /* 用于原子分配，在任何情況下都不能中斷  */
#define ___GFP_ACCOUNT          0x100000u
#define ___GFP_NOTRACK          0x200000u
#define ___GFP_DIRECT_RECLAIM   0x400000u
#define ___GFP_OTHER_NODE       0x800000u
#define ___GFP_WRITE            0x1000000u
#define ___GFP_KSWAPD_RECLAIM   0x2000000u

定義掩碼

然后第二部分, 相對(duì)而言每一個(gè)宏又被重新定義如下, 參見(jiàn)include/linux/gfp.h?v=4.7, line 46 ~ line 192

/*
* Physical address zone modifiers (see linux/mmzone.h - low four bits)
*
* Do not put any conditional on these. If necessary modify the definitions
* without the underscores and use them consistently. The definitions here may
* be used in bit comparisons.
* 定義區(qū)描述符
*/
#define __GFP_DMA       ((__force gfp_t)___GFP_DMA)
#define __GFP_HIGHMEM   ((__force gfp_t)___GFP_HIGHMEM)
#define __GFP_DMA32     ((__force gfp_t)___GFP_DMA32)
#define __GFP_MOVABLE   ((__force gfp_t)___GFP_MOVABLE)  /* ZONE_MOVABLE allowed */
#define GFP_ZONEMASK    (__GFP_DMA|__GFP_HIGHMEM|__GFP_DMA32|__GFP_MOVABLE)

/*
* Page mobility and placement hints
*
* These flags provide hints about how mobile the page is. Pages with similar
* mobility are placed within the same pageblocks to minimise problems due
* to external fragmentation.
*
* __GFP_MOVABLE (also a zone modifier) indicates that the page can be
*   moved by page migration during memory compaction or can be reclaimed.
*
* __GFP_RECLAIMABLE is used for slab allocations that specify
*   SLAB_RECLAIM_ACCOUNT and whose pages can be freed via shrinkers.
*
* __GFP_WRITE indicates the caller intends to dirty the page. Where possible,
*   these pages will be spread between local zones to avoid all the dirty
*   pages being in one zone (fair zone allocation policy).
*
* __GFP_HARDWALL enforces the cpuset memory allocation policy.
*
* __GFP_THISNODE forces the allocation to be satisified from the requested
*   node with no fallbacks or placement policy enforcements.
*
* __GFP_ACCOUNT causes the allocation to be accounted to kmemcg (only relevant
*   to kmem allocations).
*/
#define __GFP_RECLAIMABLE ((__force gfp_t)___GFP_RECLAIMABLE)
#define __GFP_WRITE     ((__force gfp_t)___GFP_WRITE)
#define __GFP_HARDWALL   ((__force gfp_t)___GFP_HARDWALL)
#define __GFP_THISNODE  ((__force gfp_t)___GFP_THISNODE)
#define __GFP_ACCOUNT   ((__force gfp_t)___GFP_ACCOUNT)

/*
* Watermark modifiers -- controls access to emergency reserves
*
* __GFP_HIGH indicates that the caller is high-priority and that granting
*   the request is necessary before the system can make forward progress.
*   For example, creating an IO context to clean pages.
*
* __GFP_ATOMIC indicates that the caller cannot reclaim or sleep and is
*   high priority. Users are typically interrupt handlers. This may be
*   used in conjunction with __GFP_HIGH
 *
 * __GFP_MEMALLOC allows access to all memory. This should only be used when
 *   the caller guarantees the allocation will allow more memory to be freed
 *   very shortly e.g. process exiting or swapping. Users either should
 *   be the MM or co-ordinating closely with the VM (e.g. swap over NFS).
 *
 * __GFP_NOMEMALLOC is used to explicitly forbid access to emergency reserves.
 *   This takes precedence over the __GFP_MEMALLOC flag if both are set.
 */
#define __GFP_ATOMIC    ((__force gfp_t)___GFP_ATOMIC)
#define __GFP_HIGH      ((__force gfp_t)___GFP_HIGH)
#define __GFP_MEMALLOC  ((__force gfp_t)___GFP_MEMALLOC)
#define __GFP_NOMEMALLOC ((__force gfp_t)___GFP_NOMEMALLOC)

/*
 * Reclaim modifiers
 *
 * __GFP_IO can start physical IO.
 *
 * __GFP_FS can call down to the low-level FS. Clearing the flag avoids the
 *   allocator recursing into the filesystem which might already be holding
 *   locks.
 *
 * __GFP_DIRECT_RECLAIM indicates that the caller may enter direct reclaim.
 *   This flag can be cleared to avoid unnecessary delays when a fallback
 *   option is available.
 *
 * __GFP_KSWAPD_RECLAIM indicates that the caller wants to wake kswapd when
 *   the low watermark is reached and have it reclaim pages until the high
 *   watermark is reached. A caller may wish to clear this flag when fallback
 *   options are available and the reclaim is likely to disrupt the system. The
 *   canonical example is THP allocation where a fallback is cheap but
 *   reclaim/compaction may cause indirect stalls.
 *
 * __GFP_RECLAIM is shorthand to allow/forbid both direct and kswapd reclaim.
 *
 * __GFP_REPEAT: Try hard to allocate the memory, but the allocation attempt
 *   _might_ fail.  This depends upon the particular VM implementation.
 *
 * __GFP_NOFAIL: The VM implementation _must_ retry infinitely: the caller
 *   cannot handle allocation failures. New users should be evaluated carefully
 *   (and the flag should be used only when there is no reasonable failure
 *   policy) but it is definitely preferable to use the flag rather than
 *   opencode endless loop around allocator.
 *
 * __GFP_NORETRY: The VM implementation must not retry indefinitely and will
 *   return NULL when direct reclaim and memory compaction have failed to allow
 *   the allocation to succeed.  The OOM killer is not called with the current
 *   implementation.
 */
#define __GFP_IO        ((__force gfp_t)___GFP_IO)
#define __GFP_FS        ((__force gfp_t)___GFP_FS)
#define __GFP_DIRECT_RECLAIM    ((__force gfp_t)___GFP_DIRECT_RECLAIM) /* Caller can reclaim */
#define __GFP_KSWAPD_RECLAIM    ((__force gfp_t)___GFP_KSWAPD_RECLAIM) /* kswapd can wake */
#define __GFP_RECLAIM ((__force gfp_t)(___GFP_DIRECT_RECLAIM|___GFP_KSWAPD_RECLAIM))
#define __GFP_REPEAT    ((__force gfp_t)___GFP_REPEAT)
#define __GFP_NOFAIL    ((__force gfp_t)___GFP_NOFAIL)
#define __GFP_NORETRY   ((__force gfp_t)___GFP_NORETRY)

/*
 * Action modifiers
 *
 * __GFP_COLD indicates that the caller does not expect to be used in the near
 *   future. Where possible, a cache-cold page will be returned.
 *
 * __GFP_NOWARN suppresses allocation failure reports.
 *
 * __GFP_COMP address compound page metadata.
 *
 * __GFP_ZERO returns a zeroed page on success.
 *
 * __GFP_NOTRACK avoids tracking with kmemcheck.
 *
 * __GFP_NOTRACK_FALSE_POSITIVE is an alias of __GFP_NOTRACK. It's a means of
 *   distinguishing in the source between false positives and allocations that
 *   cannot be supported (e.g. page tables).
 *
 * __GFP_OTHER_NODE is for allocations that are on a remote node but that
 *   should not be accounted for as a remote allocation in vmstat. A
 *   typical user would be khugepaged collapsing a huge page on a remote
 *   node.
 */
#define __GFP_COLD      ((__force gfp_t)___GFP_COLD)
#define __GFP_NOWARN    ((__force gfp_t)___GFP_NOWARN)
#define __GFP_COMP      ((__force gfp_t)___GFP_COMP)
#define __GFP_ZERO      ((__force gfp_t)___GFP_ZERO)
#define __GFP_NOTRACK   ((__force gfp_t)___GFP_NOTRACK)
#define __GFP_NOTRACK_FALSE_POSITIVE (__GFP_NOTRACK)
#define __GFP_OTHER_NODE ((__force gfp_t)___GFP_OTHER_NODE)

/* Room for N __GFP_FOO bits */
#define __GFP_BITS_SHIFT 26
#define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))

給出的常數(shù)，其中一些很少使用，因此我不會(huì)討論。其中最重要的一些常數(shù)語(yǔ)義如下所示

其中在開始的位置定義了對(duì)應(yīng)的區(qū)修飾符,

?

?

其次還定義了我們程序和函數(shù)中所需要的掩碼MASK的信息, 由于其中__GFP_DMA, __GFP_DMA32, __GFP_HIGHMEM, __GFP_MOVABLE是在內(nèi)存中分別有對(duì)應(yīng)的內(nèi)存域信息, 因此我們定義了內(nèi)存域的掩碼GFP_ZONEMASK, 參見(jiàn)include/linux/gfp.h?v=4.7, line 57

#define GFP_ZONEMASK    (__GFP_DMA|__GFP_HIGHMEM|__GFP_DMA32|__GFP_MOVABLE)

接著內(nèi)核定義了行為修飾符

/* __GFP_WAIT表示分配內(nèi)存的請(qǐng)求可以中斷。也就是說(shuō)，調(diào)度器在該請(qǐng)求期間可隨意選擇另一個(gè)過(guò)程執(zhí)行，或者該請(qǐng)求可以被另一個(gè)更重要的事件中斷. 分配器還可以在返回內(nèi)存之前, 在隊(duì)列上等待一個(gè)事件(相關(guān)進(jìn)程會(huì)進(jìn)入睡眠狀態(tài)).

雖然名字相似，但__GFP_HIGH與__GFP_HIGHMEM毫無(wú)關(guān)系，請(qǐng)不要弄混這兩者\(yùn)

那自然還有__GFP_BITS_SHIFT來(lái)表示我們所有的掩碼位, 由于我們共計(jì)26個(gè)掩碼位

/* Room for N __GFP_FOO bits */
#define __GFP_BITS_SHIFT 26
#define __GFP_BITS_MASK ((__force gfp_t)((1 << __GFP_BITS_SHIFT) - 1))

可以同時(shí)指定這些分配標(biāo)志, 例如

ptr = kmalloc(size, __GFP_IO | __GFP_FS);

說(shuō)明頁(yè)分配器(最終會(huì)調(diào)用alloc_page)在分配時(shí)可以執(zhí)行I/O, 在必要時(shí)還可以執(zhí)行文件系統(tǒng)操作. 這就讓內(nèi)核有很大的自由度, 以便它盡可能找到空閑的內(nèi)存來(lái)滿足分配請(qǐng)求. 大多數(shù)分配器都會(huì)執(zhí)行這些修飾符, 但一般不是這樣直接指定, 而是將這些行為描述符標(biāo)志進(jìn)行分組, 即類型標(biāo)志

掩碼分組

最后來(lái)看第三部分, 由于這些標(biāo)志幾乎總是組合使用，內(nèi)核作了一些分組，包含了用于各種標(biāo)準(zhǔn)情形的適當(dāng)?shù)臉?biāo)志. 稱之為類型標(biāo)志,

類型標(biāo)志指定所需的行為和區(qū)描述符以安城特殊類型的處理, 正因?yàn)檫@一點(diǎn), 內(nèi)核總是趨于使用正確的類型標(biāo)志, 而不是一味地指定它可能用到的多種描述符. 這么做既簡(jiǎn)單又不容易出錯(cuò)誤.如果有可能的話, 在內(nèi)存管理子系統(tǒng)之外, 總是把下列分組之一用于內(nèi)存分配. 在內(nèi)核源代碼中, 雙下劃線通常用于內(nèi)部數(shù)據(jù)和定義. 而這些預(yù)定義的分組名沒(méi)有雙下劃線前綴, 點(diǎn)從側(cè)面驗(yàn)證了上述說(shuō)法.

#define GFP_ATOMIC      (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)
#define GFP_KERNEL      (__GFP_RECLAIM | __GFP_IO | __GFP_FS)
#define GFP_KERNEL_ACCOUNT (GFP_KERNEL | __GFP_ACCOUNT)
#define GFP_NOWAIT      (__GFP_KSWAPD_RECLAIM)
#define GFP_NOIO        (__GFP_RECLAIM)
#define GFP_NOFS        (__GFP_RECLAIM | __GFP_IO)
#define GFP_TEMPORARY   (__GFP_RECLAIM | __GFP_IO | __GFP_FS | \
                         __GFP_RECLAIMABLE)
#define GFP_USER        (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL)
#define GFP_DMA         __GFP_DMA
#define GFP_DMA32       __GFP_DMA32
#define GFP_HIGHUSER    (GFP_USER | __GFP_HIGHMEM)
#define GFP_HIGHUSER_MOVABLE    (GFP_HIGHUSER | __GFP_MOVABLE)
#define GFP_TRANSHUGE   ((GFP_HIGHUSER_MOVABLE | __GFP_COMP | \
                         __GFP_NOMEMALLOC | __GFP_NORETRY | __GFP_NOWARN) & \
                         ~__GFP_RECLAIM)

/* Convert GFP flags to their corresponding migrate type */
#define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)
#define GFP_MOVABLE_SHIFT 3

?

?

其中GFP_NOIO和GFP_NOFS, 分別明確禁止I/O操作和訪問(wèn)VFS層, 但同時(shí)設(shè)置了__GFP_RECLAIM，因此可以被回收

而GFP_KERNEL和GFP_USER. 分別是內(nèi)核和用戶分配的默認(rèn)設(shè)置。二者的失敗不會(huì)立即威脅系統(tǒng)穩(wěn)定性, GFP_KERNEL絕對(duì)是內(nèi)核源代碼中最常使用的標(biāo)志 |

最后內(nèi)核設(shè)置了碎片管理的可移動(dòng)依據(jù)組織頁(yè)的MASK信息GFP_MOVABLE_MASK,

/* Convert GFP flags to their corresponding migrate type */
#define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE)
#define GFP_MOVABLE_SHIFT 3

在你編寫的絕大多數(shù)代碼中, 用么用到的是GFP_KERNEL, 要么是GFP_ATOMIC, 當(dāng)然各個(gè)類型標(biāo)志也均有其應(yīng)用場(chǎng)景

?

總結(jié)

我們從注釋中找到這樣的信息, 可以作為參考

bit       result
=================
0x0    => NORMAL
0x1    => DMA or NORMAL
0x2    => HIGHMEM or NORMAL
0x3    => BAD (DMA+HIGHMEM)
0x4    => DMA32 or DMA or NORMAL
0x5    => BAD (DMA+DMA32)
0x6    => BAD (HIGHMEM+DMA32)
0x7    => BAD (HIGHMEM+DMA32+DMA)
0x8    => NORMAL (MOVABLE+0)
0x9    => DMA or NORMAL (MOVABLE+DMA)
0xa    => MOVABLE (Movable is valid only if HIGHMEM is set too)
0xb    => BAD (MOVABLE+HIGHMEM+DMA)
0xc    => DMA32 (MOVABLE+DMA32)
0xd    => BAD (MOVABLE+DMA32+DMA)
0xe    => BAD (MOVABLE+DMA32+HIGHMEM)
0xf    => BAD (MOVABLE+DMA32+HIGHMEM+DMA)

GFP_ZONES_SHIFT must be <= 2 on 32 bit platforms.

很有趣的一點(diǎn)是，沒(méi)有__GFP_NORMAL常數(shù)，而內(nèi)存分配的主要負(fù)擔(dān)卻落到ZONE_NORMAL內(nèi)存域

內(nèi)核考慮到這一點(diǎn), 提供了一個(gè)函數(shù)gfp_zone來(lái)計(jì)算與給定分配標(biāo)志兼容的最高內(nèi)存域. 那么內(nèi)存分配可以從該內(nèi)存域或更低的內(nèi)存域進(jìn)行, 該函數(shù)定義在include/linux/gfp.h?v=4.7, line 394

#if defined(CONFIG_ZONE_DEVICE) && (MAX_NR_ZONES-1) <= 4
/* ZONE_DEVICE is not a valid GFP zone specifier */
#define GFP_ZONES_SHIFT 2
#else
#define GFP_ZONES_SHIFT ZONES_SHIFT
#endif

#if 16 * GFP_ZONES_SHIFT > BITS_PER_LONG
#error GFP_ZONES_SHIFT too large to create GFP_ZONE_TABLE integer
#endif

由于內(nèi)存域修飾符的解釋方式不是那么直觀, 表3-7給出了該函數(shù)結(jié)果的一個(gè)例子, 其中DMA和DMA32內(nèi)存域相同. 假定在下文中沒(méi)有設(shè)置__GFP_MOVABLE修飾符.

?

如果__GFP_DMA和__GFP_HIGHMEM都沒(méi)有設(shè)置, 則首先掃描ZONE_NORMAL, 后面是ZONE_DMA

如果設(shè)置了__GFP_HIGHMEM沒(méi)有設(shè)置__GFP_DMA，則結(jié)果是從ZONE_HIGHMEM開始掃描所有3個(gè)內(nèi)存域。

如果設(shè)置了__GFP_DMA，那么__GFP_HIGHMEM設(shè)置與否沒(méi)有關(guān)系. 只有ZONE_DMA用于3種情形. 這是合理的, 因?yàn)橥瑫r(shí)使用__GFP_HIGHMEM和__GFP_DMA沒(méi)有意義. 高端內(nèi)存從來(lái)都不適用于DMA

設(shè)置__GFP_MOVABLE不會(huì)影響內(nèi)核的決策，除非它與__GFP_HIGHMEM同時(shí)指定. 在這種情況下, 會(huì)使用特殊的虛擬內(nèi)存域ZONE_MOVABLE滿足內(nèi)存分配請(qǐng)求. 對(duì)前文描述的內(nèi)核的反碎片策略而言, 這種行為是必要的.

除了內(nèi)存域修飾符之外, 掩碼中還可以設(shè)置一些標(biāo)志.

下圖中給出了掩碼的布局，以及與各個(gè)比特位置關(guān)聯(lián)的常數(shù). __GFP_DMA32出現(xiàn)了幾次，因?yàn)樗赡芪挥诓煌牡胤?

?

?

?

與內(nèi)存域修飾符相反, 這些額外的標(biāo)志并不限制從哪個(gè)物理內(nèi)存段分配內(nèi)存, 但確實(shí)可以改變分配器的行為. 例如, 它們可以修改查找空閑內(nèi)存時(shí)的積極程度.

4.3 分配頁(yè)

4.3.1 內(nèi)存分配統(tǒng)一到alloc_pages接口

通過(guò)使用標(biāo)志、內(nèi)存域修飾符和各個(gè)分配函數(shù)，內(nèi)核提供了一種非常靈活的內(nèi)存分配體系.盡管如此, 所有接口函數(shù)都可以追溯到一個(gè)簡(jiǎn)單的基本函數(shù)(alloc_pages_node)

分配單頁(yè)的函數(shù)alloc_page和__get_free_page, 還有__get_dma_pages是借助于宏定義的.

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L483
#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L500
#define __get_free_page(gfp_mask) \
    __get_free_pages((gfp_mask), 0)`

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L503
#define __get_dma_pages(gfp_mask, order) \
    __get_free_pages((gfp_mask) | GFP_DMA, (order))

get_zeroed_page的實(shí)現(xiàn)也沒(méi)什么困難, 對(duì)__get_free_pages使用__GFP_ZERO標(biāo)志，即可分配填充字節(jié)0的頁(yè). 再返回與頁(yè)關(guān)聯(lián)的內(nèi)存區(qū)地址即可.

//  http://lxr.free-electrons.com/source/mm/page_alloc.c?v=4.7#L3900
unsigned long get_zeroed_page(gfp_t gfp_mask)
{
        return __get_free_pages(gfp_mask | __GFP_ZERO, 0);
}
EXPORT_SYMBOL(get_zeroed_page);

__get_free_pages調(diào)用alloc_pages完成內(nèi)存分配, 而alloc_pages又借助于alloc_pages_node

__get_free_pages函數(shù)的定義在mm/page_alloc.c?v=4.7, line 3883

//  http://lxr.free-electrons.com/source/mm/page_alloc.c?v=4.7#L3883
unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order)
{
    struct page *page;

    /*
     * __get_free_pages() returns a 32-bit address, which cannot represent
     * a highmem page
     */
    VM_BUG_ON((gfp_mask & __GFP_HIGHMEM) != 0);

    page = alloc_pages(gfp_mask, order);
    if (!page)
        return 0;
    return (unsigned long) page_address(page);
}
EXPORT_SYMBOL(__get_free_pages);

在這種情況下， 使用了一個(gè)普通函數(shù)而不是宏， 因?yàn)閍lloc_pages返回的page實(shí)例需要使用輔助

函數(shù)page_address轉(zhuǎn)換為內(nèi)存地址. 在這里，只要知道該函數(shù)可根據(jù)page實(shí)例計(jì)算相關(guān)頁(yè)的線性內(nèi)存地址即可. 對(duì)高端內(nèi)存頁(yè)這是有問(wèn)題的

這樣, 就完成了所有分配內(nèi)存的API函數(shù)到公共的基礎(chǔ)函數(shù)alloc_pages的統(tǒng)一

?

?

?

?

所有體系結(jié)構(gòu)都必須實(shí)現(xiàn)的標(biāo)準(zhǔn)函數(shù)clear_page, 可幫助alloc_pages對(duì)頁(yè)填充字節(jié)0, 實(shí)現(xiàn)如下表所示

?

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

既然所有的內(nèi)存分配API函數(shù)都可以追溯掉alloc_page函數(shù), 從某種意義上說(shuō)，該函數(shù)是伙伴系統(tǒng)主要實(shí)現(xiàn)的”發(fā)射臺(tái)”.

alloc_pages函數(shù)的定義是依賴于NUMA或者UMA架構(gòu)的, 定義如下

#ifdef CONFIG_NUMA

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L465
static inline struct page *
alloc_pages(gfp_t gfp_mask, unsigned int order)
{
        return alloc_pages_current(gfp_mask, order);
}

#else

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L476
#define alloc_pages(gfp_mask, order) \
                alloc_pages_node(numa_node_id(), gfp_mask, order)
#endif

UMA結(jié)構(gòu)下的alloc_pages是通過(guò)alloc_pages_node函數(shù)實(shí)現(xiàn)的, 下面我們看看alloc_pages_node函數(shù)的定義, 在include/linux/gfp.h?v=4.7, line 448

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L448
/*
 * Allocate pages, preferring the node given as nid. When nid == NUMA_NO_NODE,
 * prefer the current CPU's closest node. Otherwise node must be valid and
 * online.
 */
static inline struct page *alloc_pages_node(int nid, gfp_t gfp_mask,
                        unsigned int order)
{
    if (nid == NUMA_NO_NODE)
        nid = numa_mem_id();

    return __alloc_pages_node(nid, gfp_mask, order);
}

內(nèi)核假定傳遞給改alloc_pages_node函數(shù)的結(jié)點(diǎn)nid是被激活, 即online的.但是為了安全它還是檢查并警告內(nèi)存結(jié)點(diǎn)不存在的情況. 接下來(lái)的工作委托給__alloc_pages, 只需傳遞一組適當(dāng)?shù)膮?shù), 其中包括節(jié)點(diǎn)nid的備用內(nèi)存域列表zonelist.

現(xiàn)在__alloc_pages函數(shù)沒(méi)什么特別的, 它直接將自己的所有信息傳遞給__alloc_pages_nodemask來(lái)完成內(nèi)存的分配

//  http://lxr.free-electrons.com/source/include/linux/gfp.h?v=4.7#L428
static inline struct page *
__alloc_pages(gfp_t gfp_mask, unsigned int order,
        struct zonelist *zonelist)
{
    return __alloc_pages_nodemask(gfp_mask, order, zonelist, NULL);
}

伙伴系統(tǒng)的心臟__alloc_pages_nodemask

內(nèi)核源代碼將__alloc_pages稱之為”伙伴系統(tǒng)的心臟”(`the ‘heart’ of the zoned buddy allocator“), 因?yàn)樗幚淼氖菍?shí)質(zhì)性的內(nèi)存分配.

由于”心臟”的重要性, 我將在下文詳細(xì)介紹該函數(shù).

__alloc_pages函數(shù)定義在include/linux/gfp.h?v=4.7#L428

//  http://lxr.free-electrons.com/source/mm/page_alloc.c?v=4.7#L3779
/*
 * This is the 'heart' of the zoned buddy allocator.
 */
struct page *
__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,
            struct zonelist *zonelist, nodemask_t *nodemask)
{
    struct page *page;
    unsigned int cpuset_mems_cookie;
    unsigned int alloc_flags = ALLOC_WMARK_LOW|ALLOC_FAIR;
    gfp_t alloc_mask = gfp_mask; /* The gfp_t that was actually used for allocation */
    struct alloc_context ac = {
        .high_zoneidx = gfp_zone(gfp_mask),
        .zonelist = zonelist,
        .nodemask = nodemask,
        .migratetype = gfpflags_to_migratetype(gfp_mask),
    };

    if (cpusets_enabled()) {
        alloc_mask |= __GFP_HARDWALL;
        alloc_flags |= ALLOC_CPUSET;
        if (!ac.nodemask)
            ac.nodemask = &cpuset_current_mems_allowed;
    }

    gfp_mask &= gfp_allowed_mask;

    lockdep_trace_alloc(gfp_mask);

    might_sleep_if(gfp_mask & __GFP_DIRECT_RECLAIM);

    if (should_fail_alloc_page(gfp_mask, order))
        return NULL;

    /*
     * Check the zones suitable for the gfp_mask contain at least one
     * valid zone. It's possible to have an empty zonelist as a result
     * of __GFP_THISNODE and a memoryless node
     */
    if (unlikely(!zonelist->_zonerefs->zone))
        return NULL;

    if (IS_ENABLED(CONFIG_CMA) && ac.migratetype == MIGRATE_MOVABLE)
        alloc_flags |= ALLOC_CMA;

retry_cpuset:
    cpuset_mems_cookie = read_mems_allowed_begin();

    /* Dirty zone balancing only done in the fast path */
    ac.spread_dirty_pages = (gfp_mask & __GFP_WRITE);

    /*
     * The preferred zone is used for statistics but crucially it is
     * also used as the starting point for the zonelist iterator. It
     * may get reset for allocations that ignore memory policies.
     */
    ac.preferred_zoneref = first_zones_zonelist(ac.zonelist,
                    ac.high_zoneidx, ac.nodemask);
    if (!ac.preferred_zoneref) {
        page = NULL;
        goto no_zone;
    }

    /* First allocation attempt */
    page = get_page_from_freelist(alloc_mask, order, alloc_flags, &ac);
    if (likely(page))
        goto out;

    /*
     * Runtime PM, block IO and its error handling path can deadlock
     * because I/O on the device might not complete.
     */
    alloc_mask = memalloc_noio_flags(gfp_mask);
    ac.spread_dirty_pages = false;

    /*
     * Restore the original nodemask if it was potentially replaced with
     * &cpuset_current_mems_allowed to optimize the fast-path attempt.
     */
    if (cpusets_enabled())
        ac.nodemask = nodemask;
    page = __alloc_pages_slowpath(alloc_mask, order, &ac);

no_zone:
    /*
     * When updating a task's mems_allowed, it is possible to race with
     * parallel threads in such a way that an allocation can fail while
     * the mask is being updated. If a page allocation is about to fail,
     * check if the cpuset changed during allocation and if so, retry.
     */
    if (unlikely(!page && read_mems_allowed_retry(cpuset_mems_cookie))) {
        alloc_mask = gfp_mask;
        goto retry_cpuset;
    }

out:
    if (kmemcheck_enabled && page)
        kmemcheck_pagealloc_alloc(page, order, gfp_mask);

    trace_mm_page_alloc(page, order, alloc_mask, ac.migratetype);

    return page;
}
EXPORT_SYMBOL(__alloc_pages_nodemask);

__free_pages

類似地，內(nèi)存釋放函數(shù)也可以歸約到一個(gè)主要的函數(shù)(__free_pages), 只是用不同的參數(shù)調(diào)用而已

前面我們講過(guò)內(nèi)核釋放的兩個(gè)主要函數(shù)有__free_page和free_page,

void free_pages(unsigned long addr, unsigned int order)
{
    if (addr != 0) {
        VM_BUG_ON(!virt_addr_valid((void *)addr));
        __free_pages(virt_to_page((void *)addr), order);
    }
}

free_pages和__free_pages之間的關(guān)系通過(guò)函數(shù)而不是宏建立, 因?yàn)槭紫缺仨殞⑻摂M地址轉(zhuǎn)換為指向struct page的指針

virt_to_page將虛擬內(nèi)存地址轉(zhuǎn)換為指向page實(shí)例的指針. 基本上, 這是講解內(nèi)存分配函數(shù)時(shí)介紹的page_address輔助函數(shù)的逆過(guò)程.

下圖以圖形化方式綜述了各個(gè)內(nèi)存釋放函數(shù)之間的關(guān)系

?

?

審核編輯：湯梓紅

?