目錄

3.7伙伴分配器

3.7.1基本的伙伴分配器
3.7.2分區(qū)的伙伴分配器
3.7.3根據(jù)可移動性分組
3.7.4每處理器頁集合
3.7.5分配頁
3.7.6釋放頁

3.7伙伴分配器

內(nèi)核初始化完畢后，使用頁分配器管理物理頁，當(dāng)前使用的頁分配器是伙伴分配器，伙伴分配器的特點是算法簡單且效率高。

3.7.1基本的伙伴分配器

連續(xù)的物理頁稱為頁塊（page block）。階（order）是伙伴分配器的一個術(shù)語，是頁的數(shù)量單位，2n個連續(xù)頁稱為n階頁塊。滿足以下條件的兩個n階頁塊稱為伙伴（buddy）。

（1）兩個頁塊是相鄰的，即物理地址是連續(xù)的。

（2）頁塊的第一頁的物理頁號必須是2n的整數(shù)倍。

（3）如果合并成（n+1）階頁塊，第一頁的物理頁號必須是2n+1的整數(shù)倍。

這是伙伴分配器（buddy allocator）這個名字的來源。以單頁為例說明，0號頁和1號頁是伙伴，2號頁和3號頁是伙伴，1號頁和2號頁不是伙伴，因為1號頁和2號頁合并組成一階頁塊，第一頁的物理頁號不是2的整數(shù)倍。

伙伴分配器分配和釋放物理頁的數(shù)量單位是階。分配n階頁塊的過程如下。

（1）查看是否有空閑的n階頁塊，如果有，直接分配；如果沒有，繼續(xù)執(zhí)行下一步。

（2）查看是否存在空閑的（n+1）階頁塊，如果有，把（n+1）階頁塊分裂為兩個n階頁塊，一個插入空閑n階頁塊鏈表，另一個分配出去；如果沒有，繼續(xù)執(zhí)行下一步。

（3）查看是否存在空閑的（n+2）階頁塊，如果有，把（n+2）階頁塊分裂為兩個（n+1）階頁塊，一個插入空閑（n+1）階頁塊鏈表，另一個分裂為兩個n階頁塊，一個插入空閑n階頁塊鏈表，另一個分配出去；如果沒有，繼續(xù)查看更高階是否存在空閑頁塊。

釋放n階頁塊時，查看它的伙伴是否空閑，如果伙伴不空閑，那么把n階頁塊插入空閑的n階頁塊鏈表；如果伙伴空閑，那么合并為（n+1）階頁塊，接下來釋放（n+1）階頁塊。

內(nèi)核在基本的伙伴分配器的基礎(chǔ)上做了一些擴(kuò)展。

（1）支持內(nèi)存節(jié)點和區(qū)域，稱為分區(qū)的伙伴分配器（zoned buddy allocator）。

（2）為了預(yù)防內(nèi)存碎片，把物理頁根據(jù)可移動性分組。

（3）針對分配單頁做了性能優(yōu)化，為了減少處理器之間的鎖競爭，在內(nèi)存區(qū)域增加1個每處理器頁集合。

3.7.2分區(qū)的伙伴分配器

1．?dāng)?shù)據(jù)結(jié)構(gòu)

分區(qū)的伙伴分配器專注于某個內(nèi)存節(jié)點的某個區(qū)域。內(nèi)存區(qū)域的結(jié)構(gòu)體成員free_area用來維護(hù)空閑頁塊，數(shù)組下標(biāo)對應(yīng)頁塊的階數(shù)。結(jié)構(gòu)體free_area的成員free_list是空閑頁塊的鏈表（暫且忽略它是一個數(shù)組，3.7.3節(jié)將介紹），nr_free是空閑頁塊的數(shù)量。內(nèi)存區(qū)域的結(jié)構(gòu)體成員managed_pages是伙伴分配器管理的物理頁的數(shù)量，不包括引導(dǎo)內(nèi)存分配器分配的物理頁。

include/linux/mmzone.h struct zone {  …  /* 不同長度的空閑區(qū)域 */  struct free_area free_area[MAX_ORDER];  …  unsigned long managed_pages;  … } ____cacheline_internodealigned_in_smp; struct free_area {  struct list_head free_list[MIGRATE_TYPES];  unsigned long nr_free; };

MAX_ORDER是最大階數(shù)，實際上是可分配的最大階數(shù)加1，默認(rèn)值是11，意味著伙伴分配器一次最多可以分配頁。可以使用配置宏CONFIG_FORCE_MAX_ZONEORDER指定最大階數(shù)。

include/linux/mmzone.h /* 空閑內(nèi)存管理-分區(qū)的伙伴分配器 */ #ifndef CONFIG_FORCE_MAX_ZONEORDER #define MAX_ORDER 11 #else #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER #endif

2．根據(jù)分配標(biāo)志得到首選區(qū)域類型

申請頁時，最低的4個標(biāo)志位用來指定首選的內(nèi)存區(qū)域類型：

include/linux/gfp.h#define ___GFP_DMA 0x01u #define ___GFP_HIGHMEM 0x02u #define ___GFP_DMA32 0x04u #define ___GFP_MOVABLE 0x08u

標(biāo)志組合和首選的內(nèi)存區(qū)域類型的對應(yīng)關(guān)系如表3.5所示。

為什么要使用OPT_ZONE_DMA，而不使用ZONE_DMA？

因為DMA區(qū)域是可選的，如果不存在只能訪問16MB以下物理內(nèi)存的外圍設(shè)備，那么不需要定義DMA區(qū)域，OPT_ZONE_DMA就是ZONE_NORMAL，從普通區(qū)域申請頁。高端內(nèi)存區(qū)域和DMA32區(qū)域也是可選的。

include/linux/gfp.h #ifdef CONFIG_HIGHMEM #define OPT_ZONE_HIGHMEM ZONE_HIGHMEM #else #define OPT_ZONE_HIGHMEM ZONE_NORMAL #endif #ifdef CONFIG_ZONE_DMA #define OPT_ZONE_DMA ZONE_DMA #else #define OPT_ZONE_DMA ZONE_NORMAL #endif #ifdef CONFIG_ZONE_DMA32 #define OPT_ZONE_DMA32 ZONE_DMA32 #else #define OPT_ZONE_DMA32 ZONE_NORMAL #endif

內(nèi)核使用宏GFP_ZONE_TABLE定義了標(biāo)志組合到區(qū)域類型的映射表，其中GFP_ZONES_SHIFT是區(qū)域類型占用的位數(shù)，GFP_ZONE_TABLE把每種標(biāo)志組合映射到32位整數(shù)的某個位置，偏移是（標(biāo)志組合*區(qū)域類型位數(shù)），從這個偏移開始的GFP_ZONES_SHIFT個二進(jìn)制位存放區(qū)域類型。宏GFP_ZONE_TABLE是一個常量，編譯器在編譯時會進(jìn)行優(yōu)化，直接計算出結(jié)果，不會等到運行程序的時候才計算數(shù)值。

include/linux/gfp.h #define GFP_ZONE_TABLE (   (ZONE_NORMAL << 0 * GFP_ZONES_SHIFT)   | (OPT_ZONE_DMA << ___GFP_DMA * GFP_ZONES_SHIFT)   | (OPT_ZONE_HIGHMEM << ___GFP_HIGHMEM * GFP_ZONES_SHIFT)   | (OPT_ZONE_DMA32 << ___GFP_DMA32 * GFP_ZONES_SHIFT)   | (ZONE_NORMAL << ___GFP_MOVABLE * GFP_ZONES_SHIFT)   | (OPT_ZONE_DMA << (___GFP_MOVABLE | ___GFP_DMA) * GFP_ZONES_SHIFT)   | (ZONE_MOVABLE << (___GFP_MOVABLE | ___GFP_HIGHMEM) * GFP_ZONES_SHIFT)   | (OPT_ZONE_DMA32 << (___GFP_MOVABLE | ___GFP_DMA32) * GFP_ZONES_SHIFT)  )

內(nèi)核使用函數(shù)gfp_zone()根據(jù)分配標(biāo)志得到首選的區(qū)域類型：先分離出區(qū)域標(biāo)志位，然后算出在映射表中的偏移（區(qū)域標(biāo)志位*區(qū)域類型位數(shù)），接著把映射表右移偏移值，最后取出最低的區(qū)域類型位數(shù)。

include/linux/gfp.h static inline enum zone_type gfp_zone(gfp_t flags) {  enum zone_type z;  int bit = (__force int) (flags & GFP_ZONEMASK);  z = (GFP_ZONE_TABLE >> (bit * GFP_ZONES_SHIFT)) &  ((1 << GFP_ZONES_SHIFT) - 1);  VM_BUG_ON((GFP_ZONE_BAD >> bit) & 1);  return z; }

3．備用區(qū)域列表

如果首選的內(nèi)存節(jié)點和區(qū)域不能滿足頁分配請求，可以從備用的內(nèi)存區(qū)域借用物理頁，借用必須遵守以下原則。

（1）一個內(nèi)存節(jié)點的某個區(qū)域類型可以從另一個內(nèi)存節(jié)點的相同區(qū)域類型借用物理頁，例如節(jié)點0的普通區(qū)域可以從節(jié)點1的普通區(qū)域借用物理頁。

（2）高區(qū)域類型可以從低區(qū)域類型借用物理頁，例如普通區(qū)域可以從DMA區(qū)域借用物理頁。

（3）低區(qū)域類型不能從高區(qū)域類型借用物理頁，例如DMA區(qū)域不能從普通區(qū)域借用物理頁。

內(nèi)存節(jié)點的pg_data_t實例定義了備用區(qū)域列表，其代碼如下：

include/linux/mmzone.htypedef struct pglist_data {  … struct zonelist node_zonelists[MAX_ZONELISTS];/* 備用區(qū)域列表 */ … } pg_data_t; enum { ZONELIST_FALLBACK, /* 包含所有內(nèi)存節(jié)點的備用區(qū)域列表 */#ifdef CONFIG_NUMA ZONELIST_NOFALLBACK, /* 只包含當(dāng)前內(nèi)存節(jié)點的備用區(qū)域列表(__GFP_THISNODE) */#endif  MAX_ZONELISTS }; #define MAX_ZONES_PER_ZONELIST (MAX_NUMNODES * MAX_NR_ZONES) struct zonelist {  struct zoneref _zonerefs[MAX_ZONES_PER_ZONELIST + 1]; }; struct zoneref {  struct zone *zone; /* 指向內(nèi)存區(qū)域的數(shù)據(jù)結(jié)構(gòu) */  int zone_idx; /* 成員zone指向的內(nèi)存區(qū)域的類型 */ };

UMA系統(tǒng)只有一個備用區(qū)域列表，按區(qū)域類型從高到低排序。假設(shè)UMA系統(tǒng)包含通區(qū)域和DMA區(qū)域，那么備用區(qū)域列表是：｛普通區(qū)域，DMA區(qū)域｝。

NUMA系統(tǒng)的每個內(nèi)存節(jié)點有兩個備用區(qū)域列表：一個包含所有內(nèi)存節(jié)點的區(qū)域，另一個只包含當(dāng)前內(nèi)存節(jié)點的區(qū)域。如果申請頁時指定標(biāo)志__GFP_THISNODE，要求只能從指定內(nèi)存節(jié)點分配物理頁，就需要使用指定內(nèi)存節(jié)點的第二個備用區(qū)域列表。

包含所有內(nèi)存節(jié)點的備用區(qū)域列表有兩種排序方法。

（1）節(jié)點優(yōu)先順序：先根據(jù)節(jié)點距離從小到大排序，然后在每個節(jié)點里面根據(jù)區(qū)域類型從高到低排序。

（2）區(qū)域優(yōu)先順序：先根據(jù)區(qū)域類型從高到低排序，然后在每個區(qū)域類型里面根據(jù)節(jié)點距離從小到大排序。

節(jié)點優(yōu)先順序的優(yōu)點是優(yōu)先選擇距離近的內(nèi)存，缺點是在高區(qū)域耗盡以前就使用低區(qū)域，例如DMA區(qū)域一般比較小，節(jié)點優(yōu)先順序會增大DMA區(qū)域耗盡的概率。區(qū)域優(yōu)先順序的優(yōu)點是減小低區(qū)域耗盡的概率，缺點是不能保證優(yōu)先選擇距離近的內(nèi)存。默認(rèn)的排序方法是自動選擇最優(yōu)的排序方法：如果是64位系統(tǒng)，因為需要DMA和DMA32區(qū)域的設(shè)備相對少，所以選擇節(jié)點優(yōu)先順序；如果是32位系統(tǒng)，選擇區(qū)域優(yōu)先順序。

可以使用內(nèi)核參數(shù)“numa_zonelist_order”指定排序方法：“d”表示默認(rèn)排序方法，“n”表示節(jié)點優(yōu)先順序，“z”表示區(qū)域優(yōu)先順序，大小寫字母都可以。在運行中可以使用文件“/proc/sys/vm/numa_zonelist_order”修改排序方法。

假設(shè)NUMA系統(tǒng)包含節(jié)點0和1，節(jié)點0包含普通區(qū)域和DMA區(qū)域，節(jié)點1只包含普通區(qū)域。

如果選擇節(jié)點優(yōu)先順序，兩個節(jié)點的備用區(qū)域列表如圖3.17所示。

圖3.17 節(jié)點優(yōu)先順序的備用區(qū)域列表

如果節(jié)點0的處理器申請普通區(qū)域的物理頁，應(yīng)該依次嘗試節(jié)點0的普通區(qū)域、節(jié)點0的DMA區(qū)域和節(jié)點1的普通區(qū)域。如果節(jié)點0的處理器申請DMA區(qū)域的物理頁，首選區(qū)域是節(jié)點0的DMA區(qū)域，備用區(qū)域列表沒有其他DMA區(qū)域可以選擇。

如果選擇區(qū)域優(yōu)先順序，兩個節(jié)點的備用區(qū)域列表如圖3.18所示。

圖3.18 區(qū)域優(yōu)先順序的備用區(qū)域列表

如果節(jié)點0的處理器申請普通區(qū)域的物理頁，應(yīng)該依次嘗試節(jié)點0的普通區(qū)域、節(jié)點1的普通區(qū)域和節(jié)點0的DMA區(qū)域。如果節(jié)點0的處理器申請DMA區(qū)域的物理頁，首選區(qū)域是節(jié)點0的DMA區(qū)域，備用區(qū)域列表沒有其他DMA區(qū)域可以選擇。

4．區(qū)域水線

首選的內(nèi)存區(qū)域在什么情況下從備用區(qū)域借用物理頁？這個問題要從區(qū)域水線開始說起。每個內(nèi)存區(qū)域有3個水線。

（1）高水線（high）：如果內(nèi)存區(qū)域的空閑頁數(shù)大于高水線，說明該內(nèi)存區(qū)域的內(nèi)存充足。

（2）低水線（low）：如果內(nèi)存區(qū)域的空閑頁數(shù)小于低水線，說明該內(nèi)存區(qū)域的內(nèi)存輕微不足。

（3）最低水線（min）：如果內(nèi)存區(qū)域的空閑頁數(shù)小于最低水線，說明該內(nèi)存區(qū)域的內(nèi)存嚴(yán)重不足。

include/linux/mmzone.h enum zone_watermarks {  WMARK_MIN,  WMARK_LOW,  WMARK_HIGH,  NR_WMARK }; struct zone {  …  /* 區(qū)域水線，使用*_wmark_pages(zone) 宏訪問 */  unsigned long watermark[NR_WMARK];  … } ____cacheline_internodealigned_in_smp;

最低水線以下的內(nèi)存稱為緊急保留內(nèi)存，在內(nèi)存嚴(yán)重不足的緊急情況下，給承諾“給我少量緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”的進(jìn)程使用。

設(shè)置了進(jìn)程標(biāo)志位PF_MEMALLOC的進(jìn)程可以使用緊急保留內(nèi)存，標(biāo)志位PF_MEMALLOC表示承諾“給我少量緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”。內(nèi)存管理子系統(tǒng)以外的子系統(tǒng)不應(yīng)該使用這個標(biāo)志位，典型的例子是頁回收內(nèi)核線程kswapd，在回收頁的過程中可能需要申請內(nèi)存。

如果申請頁時設(shè)置了標(biāo)志位__GFP_MEMALLOC，即調(diào)用者承諾“給我少量緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”，那么可以使用緊急保留內(nèi)存。

申請頁時，第一次嘗試使用低水線，如果首選的內(nèi)存區(qū)域的空閑頁數(shù)小于低水線，就從備用的內(nèi)存區(qū)域借用物理頁。如果第一次分配失敗，那么喚醒所有目標(biāo)內(nèi)存節(jié)點的頁回收內(nèi)核線程kswapd以異步回收頁，然后嘗試使用最低水線。如果首選的內(nèi)存區(qū)域的空閑頁數(shù)小于最低水線，就從備用的內(nèi)存區(qū)域借用物理頁。

計算水線時，有兩個重要的參數(shù)。

（1）min_free_kbytes是最小空閑字節(jié)數(shù)。默認(rèn)值=

，并且限制在范圍[128,65536]以內(nèi)。其中lowmem_kbytes是低端內(nèi)存大小，單位是KB。參考文件“mm/page_alloc.c”中的函數(shù)init_per_zone_wmark_min。可以通過文件“/proc/sys/vm/min_free_kbytes”設(shè)置最小空閑字節(jié)數(shù)。

（2）watermark_scale_factor是水線縮放因子。默認(rèn)值是10，可以通過文件“/proc/sys/vm/watermark_scale_factor”修改水線縮放因子，取值范圍是[1,1000]。

文件“mm/page_alloc.c”中的函數(shù)__setup_per_zone_wmarks()負(fù)責(zé)計算每個內(nèi)存區(qū)域的最低水線、低水線和高水線。

計算最低水線的方法如下。

（1）min_free_pages = min_free_kbytes對應(yīng)的頁數(shù)。

（2）lowmem_pages =所有低端內(nèi)存區(qū)域中伙伴分配器管理的頁數(shù)總和。

（3）高端內(nèi)存區(qū)域的最低水線= zone->managed_pages/1024，并且限制在范圍[32, 128]以內(nèi)（zone->managed_pages是該內(nèi)存區(qū)域中伙伴分配器管理的頁數(shù)，在內(nèi)核初始化的過程中引導(dǎo)內(nèi)存分配器分配出去的物理頁，不受伙伴分配器管理）。

（4）低端內(nèi)存區(qū)域的最低水線= min_free_pages * zone->managed_pages / lowmem_pages，即把min_free_pages按比例分配到每個低端內(nèi)存區(qū)域。

計算低水線和高水線的方法如下。

（1）增量= (最低水線/ 4, zone->managed_pages * watermark_scale_factor / 10000)取最大值。

（2）低水線=最低水線+增量。

（3）高水線=最低水線+增量* 2。

如果（最低水線/ 4）比較大，那么計算公式簡化如下。

（1）低水線=最低水線* 5/4。

（2）高水線=最低水線* 3/2。

5．防止過度借用

和高區(qū)域類型相比，低區(qū)域類型的內(nèi)存相對少，是稀缺資源，而且有特殊用途，例如DMA區(qū)域用于外圍設(shè)備和內(nèi)存之間的數(shù)據(jù)傳輸。為了防止高區(qū)域類型過度借用低區(qū)域類型的物理頁，低區(qū)域類型需要采取防衛(wèi)措施，保留一定數(shù)量的物理頁。

一個內(nèi)存節(jié)點的某個區(qū)域類型從另一個內(nèi)存節(jié)點的相同區(qū)域類型借用物理頁，后者應(yīng)該毫無保留地借用。

內(nèi)存區(qū)域有一個數(shù)組用于存放保留頁數(shù)：

include/linux/mmzone.h struct zone {  …  long lowmem_reserve[MAX_NR_ZONES];  … } ____cacheline_internodealigned_in_smp;

zone[i]->lowmem_reserve[j]表示區(qū)域類型i應(yīng)該保留多少頁不能借給區(qū)域類型j，僅當(dāng)j大于i時有意義。

zone[i]->lowmem_reserve[j]的計算規(guī)則如下：

(i < j):  zone[i]->lowmem_reserve[j]  = (當(dāng)前內(nèi)存節(jié)點上從zone[i + 1] 到zone[j]伙伴分配器管理的頁數(shù)總和) 157 第 3 章 內(nèi)存管理 / sysctl_lowmem_reserve_ratio[i] (i = j):  zone[i]->lowmem_reserve[j]= 0（相同的區(qū)域類型不應(yīng)該保留）(i > j):  zone[i]->lowmem_reserve[j]= 0（沒意義，不會出現(xiàn)低區(qū)域類型從高區(qū)域類型借用物理頁的情況）

數(shù)組sysctl_lowmem_reserve_ratio存放各種區(qū)域類型的保留比例，因為內(nèi)核不允許使用浮點數(shù)，所以使用倒數(shù)值。DMA區(qū)域和DMA32區(qū)域的默認(rèn)保留比例都是256，普通區(qū)域和高端內(nèi)存區(qū)域的默認(rèn)保留比例都是32。

mm/page_alloc.c int sysctl_lowmem_reserve_ratio[MAX_NR_ZONES-1] = { #ifdef CONFIG_ZONE_DMA  256, #endif #ifdef CONFIG_ZONE_DMA32  256, #endif #ifdef CONFIG_HIGHMEM  32, #endif  32, };

可以通過文件“/proc/sys/vm/lowmem_reserve_ratio”修改各種區(qū)域類型的保留比例。

3.7.3根據(jù)可移動性分組

在系統(tǒng)長時間運行后，物理內(nèi)存可能出現(xiàn)很多碎片，可用物理頁很多，但是最大的連續(xù)物理內(nèi)存可能只有一頁。內(nèi)存碎片對用戶程序不是問題，因為用戶程序可以通過頁表把連續(xù)的虛擬頁映射到不連續(xù)的物理頁。但是內(nèi)存碎片對內(nèi)核是一個問題，因為內(nèi)核使用直接映射的虛擬地址空間，連續(xù)的虛擬頁必須映射到連續(xù)的物理頁。內(nèi)存碎片是伙伴分配器的一個弱點。

為了預(yù)防內(nèi)存碎片，內(nèi)核根據(jù)可移動性把物理頁分為3種類型。

（1）不可移動頁：位置必須固定，不能移動，直接映射到內(nèi)核虛擬地址空間的頁屬于這一類。

（2）可移動頁：使用頁表映射的頁屬于這一類，可以移動到其他位置，然后修改頁表映射。

（3）可回收頁：不能移動，但可以回收，需要數(shù)據(jù)的時候可以重新從數(shù)據(jù)源獲取。后備存儲設(shè)備支持的頁屬于這一類。

內(nèi)核把具有相同可移動性的頁分組。為什么這種方法可以減少碎片？試想：如果不可移動頁出現(xiàn)在可移動內(nèi)存區(qū)域的中間，會阻止可移動內(nèi)存區(qū)域合并。這種方法把不可移動頁聚集在一起，可以防止不可移動頁出現(xiàn)在可移動內(nèi)存區(qū)域的中間。

內(nèi)核定義了以下遷移類型：

include/linux/mmzone.h enum migratetype {  MIGRATE_UNMOVABLE, /* 不可移動 */  MIGRATE_MOVABLE, /* 可移動 */  MIGRATE_RECLAIMABLE, /* 可回收 */  MIGRATE_PCPTYPES, /* 定義內(nèi)存區(qū)域的每處理器頁集合中鏈表的數(shù)量 */  MIGRATE_HIGHATOMIC = MIGRATE_PCPTYPES, /*高階原子分配，即階數(shù)大于0，并且分配頁時不能睡眠等待*/#ifdef CONFIG_CMA  MIGRATE_CMA, /* 連續(xù)內(nèi)存分配器 */ #endif #ifdef CONFIG_MEMORY_ISOLATION  MIGRATE_ISOLATE, /* 隔離，不能從這里分配 */ #endif  MIGRATE_TYPES };

前面3種是真正的遷移類型，后面的遷移類型都有特殊用途：MIGRATE_HIGHATOMIC用于高階原子分配（參考3.7.5節(jié)的“對高階原子分配的優(yōu)化處理”），MIGRATE_CMA用于連續(xù)內(nèi)存分配器（參考3.20節(jié)），MIGRATE_ISOLATE用來隔離物理頁（由連續(xù)內(nèi)存分配器、內(nèi)存熱插拔和從內(nèi)存硬件錯誤恢復(fù)等功能使用）。

對伙伴分配器的數(shù)據(jù)結(jié)構(gòu)的主要調(diào)整是把空閑鏈表拆分成每種遷移類型一條空閑鏈表。

include/linux/mmzone.h struct free_area {  struct list_head free_list[MIGRATE_TYPES];  unsigned long nr_free; };

只有當(dāng)物理內(nèi)存足夠大且每種遷移類型有足夠多的物理頁時，根據(jù)可移動性分組才有意義。全局變量page_group_by_mobility_disabled表示是否禁用根據(jù)可移動性分組。

vm_total_pages是所有內(nèi)存區(qū)域里面高水線以上的物理頁總數(shù)，pageblock_order是按可移動性分組的階數(shù)，pageblock_nr_pages是pageblock_order對應(yīng)的頁數(shù)。如果所有內(nèi)存區(qū)域里面高水線以上的物理頁總數(shù)小于（pageblock_nr_pages *遷移類型數(shù)量），那么禁用根據(jù)可移動性分組。

mm/page_alloc.c void __ref build_all_zonelists(pg_data_t *pgdat, struct zone *zone) {  …  if (vm_total_pages < (pageblock_nr_pages * MIGRATE_TYPES))  page_group_by_mobility_disabled = 1;  else  page_group_by_mobility_disabled = 0;  … }

pageblock_order是按可移動性分組的階數(shù)，簡稱分組階數(shù)，可以理解為一種遷移類型的一個頁塊的最小長度。如果內(nèi)核支持巨型頁，那么pageblock_order是巨型頁的階數(shù)，否則pageblock_order是伙伴分配器的最大分配階。

include/linux/pageblock-flags.h #ifdef CONFIG_HUGETLB_PAGE #ifdef CONFIG_HUGETLB_PAGE_SIZE_VARIABLE /* 巨型頁長度是可變的 */ extern unsigned int pageblock_order; #else /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */ /* 巨型頁長度是固定的 */ #define pageblock_order HUGETLB_PAGE_ORDER #endif /* CONFIG_HUGETLB_PAGE_SIZE_VARIABLE */ #else/*CONFIG_HUGETLB_PAGE*//* 如果編譯內(nèi)核時沒有開啟巨型頁，按伙伴分配器的最大分配階分組 */ #define pageblock_order (MAX_ORDER-1) #endif /* CONFIG_HUGETLB_PAGE */ #define pageblock_nr_pages (1UL << pageblock_order)

申請頁時，可以使用標(biāo)志__GFP_MOVABLE指定申請可移動頁，使用標(biāo)志__GFP_RECLAIMABLE指定申請可回收頁，如果沒有指定這兩個標(biāo)志，表示申請不可移動頁。函數(shù)gfpflags_to_migratetype用來把分配標(biāo)志轉(zhuǎn)換成遷移類型：

include/linux/gfp.h /* 把分配標(biāo)志轉(zhuǎn)換成遷移類型 */ #define GFP_MOVABLE_MASK (__GFP_RECLAIMABLE|__GFP_MOVABLE) #define GFP_MOVABLE_SHIFT 3 static inline int gfpflags_to_migratetype(const gfp_t gfp_flags) {  …  if (unlikely(page_group_by_mobility_disabled))  return MIGRATE_UNMOVABLE;  /* 根據(jù)可移動性分組 */  return (gfp_flags & GFP_MOVABLE_MASK) >> GFP_MOVABLE_SHIFT; }

如果禁用根據(jù)可移動性分組，那么總是申請不可移動頁。

申請某種遷移類型的頁時，如果這種遷移類型的頁用完了，可以從其他遷移類型盜用（steal）物理頁。內(nèi)核定義了每種遷移類型的備用類型優(yōu)先級列表：

mm/page_alloc.c static int fallbacks[MIGRATE_TYPES][4] = {  [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },  [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE, MIGRATE_MOVABLE, MIGRATE_TYPES },  [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_TYPES }, #ifdef CONFIG_CMA  [MIGRATE_CMA] = { MIGRATE_TYPES }, /* 從不使用 */ #endif #ifdef CONFIG_MEMORY_ISOLATION  [MIGRATE_ISOLATE] = { MIGRATE_TYPES }, /* 從不使用 */ #endif };

不可移動類型的備用類型按優(yōu)先級從高到低是：可回收類型和可移動類型。

可回收類型的備用類型按優(yōu)先級從高到低是：不可移動類型和可移動類型。

可移動類型的備用類型按優(yōu)先級從高到低是：可回收類型和不可移動類型。

如果需要從備用類型盜用物理頁，那么從最大的頁塊開始盜用，以避免產(chǎn)生碎片。

mm/page_alloc.c static inline bool __rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype) {  …  /* 在備用類型的頁塊鏈表中查找最大的頁塊 */  for (current_order = MAX_ORDER-1;  current_order >= order && current_order <= MAX_ORDER-1; --current_order){ area = &(zone->free_area[current_order]);  fallback_mt = find_suitable_fallback(area, current_order,  start_migratetype, false, &can_steal);  …  }  … }

釋放物理頁的時候，需要把物理頁插入物理頁所屬遷移類型的空閑鏈表，內(nèi)核怎么知道物理頁的遷移類型？內(nèi)存區(qū)域的zone結(jié)構(gòu)體的成員pageblock_flags指向頁塊標(biāo)志位圖，頁塊的大小是分組階數(shù)pageblock_order，我們把這種頁塊稱為分組頁塊。

include/linux/mmzone.h struct zone {  … #ifndef CONFIG_SPARSEMEM  /** 分組頁塊的標(biāo)志參考文件pageblock-flags.h。* 如果使用稀疏內(nèi)存模型，這個位圖在結(jié)構(gòu)體mem_section中。*/  unsigned long *pageblock_flags; #endif /* CONFIG_SPARSEMEM */  … } ____cacheline_internodealigned_in_smp;

每個分組頁塊在位圖中占用4位，其中3位用來存放頁塊的遷移類型。

include/linux/pageblock-flags.h /* 影響一個頁塊的位索引 */ enum pageblock_bits {  PB_migrate,  PB_migrate_end = PB_migrate + 3 - 1, /* 遷移類型需要3位 */  PB_migrate_skip,/* 如果被設(shè)置，內(nèi)存碎片整理跳過這個頁塊。*/  NR_PAGEBLOCK_BITS };

函數(shù)set_pageblock_migratetype()用來在頁塊標(biāo)志位圖中設(shè)置頁塊的遷移類型，函數(shù)get_pageblock_migratetype()用來獲取頁塊的遷移類型。

內(nèi)核在初始化時，把所有頁塊初始化為可移動類型，其他遷移類型的頁是盜用產(chǎn)生的。

mm/page_alloc.c free_area_init_core() -> free_area_init_core() -> memmap_init() -> memmap_init_zone() 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++) {  …  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);  }  } }

可以通過文件“/proc/pagetypeinfo”查看各種遷移類型的頁的分布情況。

3.7.4每處理器頁集合

內(nèi)核針對分配單頁做了性能優(yōu)化，為了減少處理器之間的鎖競爭，在內(nèi)存區(qū)域增加1個每處理器頁集合。

include/linux/mmzone.h struct zone {  …  struct per_cpu_pageset __percpu *pageset; /* 在每個處理器上有一個頁集合 */ … } ____cacheline_internodealigned_in_smp; struct per_cpu_pageset {  struct per_cpu_pages pcp;  … }; struct per_cpu_pages {  int count; /* 鏈表里面頁的數(shù)量 */  int high; /* 如果頁的數(shù)量達(dá)到高水線，需要返還給伙伴分配器 */  int batch; /* 批量添加或刪除的頁數(shù)量 */  struct list_head lists[MIGRATE_PCPTYPES]; /* 每種遷移類型一個頁鏈表 */ };

內(nèi)存區(qū)域在每個處理器上有一個頁集合，頁集合中每種遷移類型有一個頁鏈表。頁集合有高水線和批量值，頁集合中的頁數(shù)量不能超過高水線。申請單頁加入頁鏈表，或者從頁鏈表返還給伙伴分配器，都是采用批量操作，一次操作的頁數(shù)量是批量值。

默認(rèn)的批量值batch的計算方法如下。

（1）batch = zone->managed_pages / 1024，其中zone->managed_pages是內(nèi)存區(qū)域中由伙伴分配器管理的頁數(shù)量。

（2）如果batch超過(512 * 1024) / PAGE_SIZE，那么把batch設(shè)置為(512 * 1024) / PAGE_SIZE，其中PAGE_SIZE是頁長度。

（3）batch = batch / 4。

（4）如果batch小于1，那么把batch設(shè)置為1。

（5）batch = rounddown_pow_of_two(batch * 1.5) ? 1，其中rounddown_pow_of_two()用來把數(shù)值向下對齊到2的n次冪。

默認(rèn)的高水線是批量值的6倍。

可以通過文件“/proc/sys/vm/percpu_pagelist_fraction”修改比例值，最小值是8，默認(rèn)值是0。高水線等于（伙伴分配器管理的頁數(shù)量/比例值），同時把批量值設(shè)置為高水線的1/4。

從某個內(nèi)存區(qū)域申請某種遷移類型的單頁時，從當(dāng)前處理器的頁集合中該遷移類型的頁鏈表分配頁，如果頁鏈表是空的，先批量申請頁加入頁鏈表，然后分配一頁。

緩存熱頁是指剛剛訪問過物理頁，物理頁的數(shù)據(jù)還在處理器的緩存中。如果要申請緩存熱頁，從頁鏈表首部分配頁；如果要申請緩存冷頁，從頁鏈表尾部分配頁。

釋放單頁時，把頁加入當(dāng)前處理器的頁集合中。如果釋放緩存熱頁，加入頁鏈表首部；如果釋放緩存冷頁，加入頁鏈表尾部。如果頁集合中的頁數(shù)量大于或等于高水線，那么批量返還給伙伴分配器。

3.7.5分配頁

1．分配接口

頁分配器提供了以下分配頁的接口。

（1）alloc_pages(gfp_mask, order)請求分配一個階數(shù)為order的頁塊，返回一個page實例。

（2）alloc_page(gfp_mask)是函數(shù)alloc_pages在階數(shù)為0情況下的簡化形式，只分配一頁。

（3）__get_free_pages(gfp_mask, order)對函數(shù)alloc_pages做了封裝，只能從低端內(nèi)存區(qū)域分配頁，并且返回虛擬地址。

（4）__get_free_page(gfp_mask)是函數(shù)__get_free_pages在階數(shù)為0情況下的簡化形式，只分配一頁。

（5）get_zeroed_page(gfp_mask)是函數(shù)__get_free_pages在為參數(shù)gfp_mask設(shè)置了標(biāo)志位__GFP_ZERO且階數(shù)為0情況下的簡化形式，只分配一頁，并且用零初始化。

2．分配標(biāo)志位

分配頁的函數(shù)都帶一個分配標(biāo)志位參數(shù)，分配標(biāo)志位分為以下5類（標(biāo)志位名稱中的GFP是Get Free Pages的縮寫）。

（1）區(qū)域修飾符：指定從哪個區(qū)域類型分配頁，3.7.2節(jié)已經(jīng)描述了根據(jù)分配標(biāo)志得到首選區(qū)域類型的方法。

（2）頁移動性和位置提示：指定頁的遷移類型和從哪些內(nèi)存節(jié)點分配頁。

（3）水線修飾符。

（4）回收修飾符。

（5）行動修飾符。

因為這些標(biāo)志位總是組合使用，所以內(nèi)核定義了一些標(biāo)志位組合。常用的標(biāo)志位組合如下。

（1）GFP_ATOMIC：原子分配，分配內(nèi)核使用的頁，不能睡眠。調(diào)用者是高優(yōu)先級的，允許異步回收頁。

#define GFP_ATOMIC (__GFP_HIGH|__GFP_ATOMIC|__GFP_KSWAPD_RECLAIM)

（2）GFP_KERNEL：分配內(nèi)核使用的頁，可能睡眠。從低端內(nèi)存區(qū)域分配頁，允許異步回收頁和直接回收頁，允許讀寫存儲設(shè)備，允許調(diào)用到底層文件系統(tǒng)。

#defineGFP_KERNEL(__GFP_RECLAIM|__GFP_IO|__GFP_FS)

（3）GFP_NOWAIT：分配內(nèi)核使用的頁，不能等待。允許異步回收頁，不允許直接回收頁，不允許讀寫存儲設(shè)備，不允許調(diào)用到底層文件系統(tǒng)。

#define GFP_NOWAIT (__GFP_KSWAPD_RECLAIM)

（4）GFP_NOIO：不允許讀寫存儲設(shè)備，允許異步回收頁和直接回收頁。請盡量避免直接使用這個標(biāo)志位，應(yīng)該使用函數(shù)memalloc_noio_save和memalloc_noio_restore標(biāo)記一個不能讀寫存儲設(shè)備的范圍，前者設(shè)置進(jìn)程標(biāo)志位PF_MEMALLOC_NOIO，后者清除進(jìn)程標(biāo)志位PF_MEMALLOC_NOIO。

#define GFP_NOIO (__GFP_RECLAIM)

（5）GFP_NOFS：不允許調(diào)用到底層文件系統(tǒng)，允許異步回收頁和直接回收頁，允許讀寫存儲設(shè)備。請盡量避免直接使用這個標(biāo)志位，應(yīng)該使用函數(shù)memalloc_nofs_save和memalloc_nofs_restore標(biāo)記一個不能調(diào)用到文件系統(tǒng)的范圍，前者設(shè)置進(jìn)程標(biāo)志位PF_MEMALLOC_NOFS，后者清除進(jìn)程標(biāo)志位PF_MEMALLOC_NOFS。

#define GFP_NOFS (__GFP_RECLAIM | __GFP_IO)

（6）GFP_USER：分配用戶空間使用的頁，內(nèi)核或硬件也可以直接訪問，從普通區(qū)域分配，允許異步回收頁和直接回收頁，允許讀寫存儲設(shè)備，允許調(diào)用到文件系統(tǒng)，允許實施cpuset內(nèi)存分配策略。

#define GFP_USER (__GFP_RECLAIM | __GFP_IO | __GFP_FS | __GFP_HARDWALL)

（7）GFP_HIGHUSER：分配用戶空間使用的頁，內(nèi)核不需要直接訪問，從高端內(nèi)存區(qū)域分配，物理頁在使用的過程中不可以移動。

#define GFP_HIGHUSER (GFP_USER | __GFP_HIGHMEM)

（8）GFP_HIGHUSER_MOVABLE：分配用戶空間使用的頁，內(nèi)核不需要直接訪問，物理頁可以通過頁回收或頁遷移技術(shù)移動。

#define GFP_HIGHUSER_MOVABLE (GFP_HIGHUSER | __GFP_MOVABLE)

（9）GFP_TRANSHUGE_LIGHT：分配用戶空間使用的巨型頁，把分配的頁塊組成復(fù)合頁，禁止使用緊急保留內(nèi)存，禁止打印警告信息，不允許異步回收頁和直接回收頁。

#define GFP_TRANSHUGE_LIGHT ((GFP_HIGHUSER_MOVABLE | __GFP_COMP | __GFP_NOMEMALLOC | __GFP_NOWARN) & ~__GFP_RECLAIM)

（10）GFP_TRANSHUGE：分配用戶空間使用的巨型頁，和GFP_TRANSHUGE_LIGHT的區(qū)別是允許直接回收頁。

#define GFP_TRANSHUGE (GFP_TRANSHUGE_LIGHT | __GFP_DIRECT_RECLAIM)

3．復(fù)合頁

如果設(shè)置了標(biāo)志位__GFP_COMP并且分配了一個階數(shù)大于0的頁塊，頁分配器會把頁塊組成復(fù)合頁（compound page）。復(fù)合頁最常見的用處是創(chuàng)建巨型頁。

復(fù)合頁的第一頁叫首頁（head page），其他頁都叫尾頁（tail page）。一個由n階頁塊組成的復(fù)合頁的結(jié)構(gòu)如圖3.19所示。

圖3.19 復(fù)合頁的結(jié)構(gòu)

（1）首頁設(shè)置標(biāo)志PG_head。

（2）第一個尾頁的成員compound_mapcount表示復(fù)合頁的映射計數(shù)，即多少個虛擬頁映射到這個物理頁，初始值是?1。這個成員和成員mapping組成一個聯(lián)合體，占用相同的位置，其他尾頁把成員mapping設(shè)置為一個有毒的地址。

（3）第一個尾頁的成員compound_dtor存放復(fù)合頁釋放函數(shù)數(shù)組的索引，成員compound_order存放復(fù)合頁的階數(shù)n。這兩個成員和成員lru.prev占用相同的位置。

（4）所有尾頁的成員compound_head存放首頁的地址，并且把最低位設(shè)置為1。這個成員和成員lru.next占用相同的位置。

判斷一個頁是復(fù)合頁的成員的方法是：頁設(shè)置了標(biāo)志位PG_head（針對首頁），或者頁的成員compound_head的最低位是1（針對尾頁）。

結(jié)構(gòu)體page中復(fù)合頁的成員如下：

include/linux/mm_types.hstruct page {unsigned long flags;union {struct address_space *mapping;atomic_t compound_mapcount; /* 映射計數(shù)，第一個尾頁 *//* page_deferred_list().next -- 第二個尾頁 */};…union {struct list_head lru;/* 復(fù)合頁的尾頁 */struct {unsigned long compound_head; /* 首頁的地址，并且設(shè)置最低位 *//* 第一個尾頁 */#ifdef CONFIG_64BITunsignedintcompound_dtor;/*復(fù)合頁釋放函數(shù)數(shù)組的索引*/unsigned int compound_order; /* 復(fù)合頁的階數(shù) */#elseunsigned short int compound_dtor;unsigned short int compound_order;#endif};};…}；

4．對高階原子分配的優(yōu)化處理

高階原子分配：階數(shù)大于0，并且調(diào)用者設(shè)置了分配標(biāo)志位__GFP_ATOMIC，要求不能睡眠。

頁分配器對高階原子分配做了優(yōu)化處理，增加了高階原子類型（MIGRATE_HIGHATOMIC），在內(nèi)存區(qū)域的結(jié)構(gòu)體中增加1個成員“nr_reserved_highatomic”，用來記錄高階原子類型的總頁數(shù)，并且限制其數(shù)量：

zone->nr_reserved_highatomic < (zone->managed_pages / 100) + pageblock_nr_pages，即必須小于（伙伴分配器管理的總頁數(shù)/ 100 +分組階數(shù)對應(yīng)的頁數(shù)）。

include/linux/mmzone.hstruct zone {…unsigned long nr_reserved_highatomic;…} ____cacheline_internodealigned_in_smp;

執(zhí)行高階原子分配時，先從高階原子類型分配頁，如果分配失敗，從調(diào)用者指定的遷移類型分配頁。分配成功以后，如果內(nèi)存區(qū)域中高階原子類型的總頁數(shù)小于限制，并且頁塊的遷移類型不是高階原子類型、隔離類型和CMA遷移類型，那么把頁塊的遷移類型轉(zhuǎn)換為高階原子類型，并且把頁塊中沒有分配出去的頁移到高階原子類型的空閑鏈表中。

當(dāng)內(nèi)存嚴(yán)重不足時，直接回收頁以后仍然分配失敗，針對高階原子類型的頁數(shù)超過pageblock_nr_pages的目標(biāo)區(qū)域，把高階原子類型的頁塊轉(zhuǎn)換成申請的遷移類型，然后重試分配，其代碼如下：

mm/page_alloc.cstatic inline struct page *__alloc_pages_direct_reclaim(gfp_t gfp_mask, unsigned int order,unsigned int alloc_flags, const struct alloc_context *ac,unsigned long *did_some_progress){struct page *page = NULL;bool drained = false;*did_some_progress = __perform_reclaim(gfp_mask, order, ac);/* 直接回收頁 */if (unlikely(!(*did_some_progress)))return NULL;retry:page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);if (!page && !drained) {/* 把高階原子類型的頁塊轉(zhuǎn)換成申請的遷移類型 */unreserve_highatomic_pageblock(ac, false);drain_all_pages(NULL);drained = true;goto retry;}return page;}

如果直接回收頁沒有進(jìn)展超過16次，那么針對目標(biāo)區(qū)域，不再為高階原子分配保留頁，把高階原子類型的頁塊轉(zhuǎn)換成申請的遷移類型，其代碼如下：

mm/page_alloc.cstatic inline boolshould_reclaim_retry(gfp_t gfp_mask, unsigned order,struct alloc_context *ac, int alloc_flags,bool did_some_progress, int *no_progress_loops){…if (did_some_progress && order <= PAGE_ALLOC_COSTLY_ORDER)*no_progress_loops = 0;else(*no_progress_loops)++;if (*no_progress_loops > MAX_RECLAIM_RETRIES) {/* 在調(diào)用內(nèi)存耗盡殺手之前，用完為高階原子分配保留的頁 */return unreserve_highatomic_pageblock(ac, true);}…}

5．核心函數(shù)的實現(xiàn)

所有分配頁的函數(shù)最終都會調(diào)用到函數(shù)__alloc_pages_nodemask，這個函數(shù)被稱為分區(qū)的伙伴分配器的心臟。函數(shù)原型如下：

struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order,struct zonelist *zonelist, nodemask_t *nodemask);

參數(shù)如下。

（1）gfp_mask：分配標(biāo)志位。

（2）order：階數(shù)。

（3）zonelist：首選內(nèi)存節(jié)點的備用區(qū)域列表。如果指定了標(biāo)志位__GFP_THISNODE，選擇pg_data_t.node_zonelists[ZONELIST_NOFALLBACK]，否則選擇pg_data_t.node_zonelists[ZONELIST_FALLBACK]。

（4）nodemask：允許從哪些內(nèi)存節(jié)點分配頁，如果調(diào)用者沒有要求，可以傳入空指針。

算法如下。

（1）根據(jù)分配標(biāo)志位得到首選區(qū)域類型和遷移類型。

（2）執(zhí)行快速路徑，使用低水線嘗試第一次分配。

（3）如果快速路徑分配失敗，那么執(zhí)行慢速路徑。

頁分配器定義了以下內(nèi)部分配標(biāo)志位：

mm/internal.h#define ALLOC_WMARK_MIN WMARK_MIN /* 0x00，使用最低水線 */#define ALLOC_WMARK_LOW WMARK_LOW /* 0x01，使用低水線 */#define ALLOC_WMARK_HIGH WMARK_HIGH /* 0x02，使用高水線 */#define ALLOC_NO_WATERMARKS 0x04 /* 完全不檢查水線 */#define ALLOC_WMARK_MASK (ALLOC_NO_WATERMARKS-1) /* 得到水線位的掩碼 */#define ALLOC_HARDER 0x10 /* 試圖更努力分配 */#define ALLOC_HIGH 0x20 /* 設(shè)置了__GFP_HIGH，調(diào)用者是高優(yōu)先級的 */#define ALLOC_CPUSET 0x40 /* 檢查cpuset 是否允許進(jìn)程從某個內(nèi)存節(jié)點分配頁 */#define ALLOC_CMA 0x80 /* 允許從CMA（連續(xù)內(nèi)存分配器）遷移類型分配 */

（1）快速路徑?？焖俾窂秸{(diào)用函數(shù)get_page_from_freelist，函數(shù)的代碼如下：

mm/page_alloc.c1 static struct page *2 get_page_from_freelist(gfp_t gfp_mask, unsigned int order, int alloc_flags, 3 const struct alloc_context *ac) 4 { 5 struct zoneref *z = ac->preferred_zoneref; 6 struct zone *zone; 7 struct pglist_data *last_pgdat_dirty_limit = NULL; 8 9 for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx, 10 ac->nodemask) { 11 struct page *page; 12 unsigned long mark; 13 14 if (cpusets_enabled() && 15 (alloc_flags & ALLOC_CPUSET) && 16 !__cpuset_zone_allowed(zone, gfp_mask)) 17 continue; 18 19 if (ac->spread_dirty_pages) { 20 if (last_pgdat_dirty_limit == zone->zone_pgdat) 21 continue; 22 23 if (!node_dirty_ok(zone->zone_pgdat)) { 24 last_pgdat_dirty_limit = zone->zone_pgdat; 25 continue; 26 } 27 } 28 29 mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK]; 30 if (!zone_watermark_fast(zone, order, mark, 31 ac_classzone_idx(ac), alloc_flags)) { 32 int ret; 33 34 BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK); 35 if (alloc_flags & ALLOC_NO_WATERMARKS) 36 goto try_this_zone; 37 38 if (node_reclaim_mode == 0 || 39 !zone_allows_reclaim(ac->preferred_zoneref->zone, zone)) 40 continue; 41 42 ret = node_reclaim(zone->zone_pgdat, gfp_mask, order); 43 switch (ret) { 44 case NODE_RECLAIM_NOSCAN: 169170 45 /* 沒有掃描 */ 46 continue; 47 case NODE_RECLAIM_FULL: 48 /* 掃描過但是不可回收 */ 49 continue; 50 default: 51 /* 回收了足夠的頁，重新檢查水線 */ 52 if (zone_watermark_ok(zone, order, mark, 53 ac_classzone_idx(ac), alloc_flags)) 54 goto try_this_zone; 55 56 continue; 57 } 58 } 59 60 try_this_zone: 61 page = rmqueue(ac->preferred_zoneref->zone, zone, order, 62 gfp_mask, alloc_flags, ac->migratetype); 63 if (page) { 64 prep_new_page(page, order, gfp_mask, alloc_flags); 65 66 /* 如果這是一個高階原子分配，那么檢查這個頁塊是否應(yīng)該被保留 */ 67 if (unlikely(order && (alloc_flags & ALLOC_HARDER))) 68 reserve_highatomic_pageblock(page, zone, order); 69 70 return page; 71 } 72 } 73 74 return NULL; 75 }

第9行代碼，掃描備用區(qū)域列表中每個滿足條件的區(qū)域：“區(qū)域類型小于或等于首選區(qū)域類型，并且內(nèi)存節(jié)點在節(jié)點掩碼中的相應(yīng)位被設(shè)置”，處理如下。

1）第14～17行代碼，如果編譯了cpuset功能，調(diào)用者設(shè)置ALLOC_CPUSET要求使用cpuset檢查，并且cpuset不允許當(dāng)前進(jìn)程從這個內(nèi)存節(jié)點分配頁，那么不能從這個區(qū)域分配頁。

2）第19～27行代碼，如果調(diào)用者設(shè)置標(biāo)志位__GFP_WRITE，表示文件系統(tǒng)申請分配一個頁緩存頁用于寫文件，那么檢查內(nèi)存節(jié)點的臟頁數(shù)量是否超過限制。如果超過限制，那么不能從這個區(qū)域分配頁。

3）第30行代碼，檢查水線，如果（區(qū)域的空閑頁數(shù)?申請的頁數(shù)）小于水線，處理如下。

• 第35行代碼，如果調(diào)用者要求不檢查水線，那么可以從這個區(qū)域分配頁。
• 第38～40行代碼，如果沒有開啟節(jié)點回收功能，或者當(dāng)前節(jié)點和首選節(jié)點之間的距離大于回收距離，那么不能從這個區(qū)域分配頁。
• 第42～57行代碼，從節(jié)點回收沒有映射到進(jìn)程虛擬地址空間的文件頁和塊分配器申請的頁，然后重新檢查水線，如果（區(qū)域的空閑頁數(shù)?申請的頁數(shù)）還是小于水線，那么不能從這個區(qū)域分配頁。

4）第61行代碼，從當(dāng)前區(qū)域分配頁。

5）第64～68行代碼，如果分配成功，調(diào)用函數(shù)prep_new_page以初始化頁。如果是高階原子分配，并且區(qū)域中高階原子類型的頁數(shù)沒有超過限制，那么把分配的頁所屬的頁塊轉(zhuǎn)換為高階原子類型。

函數(shù)zone_watermark_fast負(fù)責(zé)檢查區(qū)域的空閑頁數(shù)是否大于水線，其代碼如下：

mm/page_alloc.c1 static inline bool zone_watermark_fast(struct zone *z, unsigned int order,2 unsigned long mark, int classzone_idx, unsigned int alloc_flags)3 {4 long free_pages = zone_page_state(z, NR_FREE_PAGES);5 long cma_pages = 0;67 #ifdef CONFIG_CMA8 if (!(alloc_flags & ALLOC_CMA))9 cma_pages = zone_page_state(z, NR_FREE_CMA_PAGES);10 #endif1112 /* 只快速檢查0階 */13 if (!order && (free_pages - cma_pages) > mark + z->lowmem_reserve[classzone_idx])14 return true;1516 return __zone_watermark_ok(z, order, mark, classzone_idx, alloc_flags,17 free_pages);18 }

第7～14行代碼，針對0階執(zhí)行快速檢查。

1）第8行和第9行代碼，如果不允許從CMA遷移類型分配，那么不要使用空閑的CMA頁，必須把空閑頁數(shù)減去空閑的CMA頁數(shù)。

2）第13行代碼，如果空閑頁數(shù)大于（水線+低端內(nèi)存保留頁數(shù)），即（空閑頁數(shù)?申請的一頁）大于等于（水線+低端內(nèi)存保留頁數(shù)），那么允許從這個區(qū)域分配頁。

第16行代碼，如果是其他情況，那么調(diào)用函數(shù)__zone_watermark_ok進(jìn)行檢查。

函數(shù)__zone_watermark_ok更加仔細(xì)地檢查區(qū)域的空閑頁數(shù)是否大于水線，其代碼如下：

mm/page_alloc.c1 bool __zone_watermark_ok(struct zone *z, unsigned int order, unsigned long mark,2 int classzone_idx, unsigned int alloc_flags,3 long free_pages)4 {5 long min = mark;6 int o;7 const bool alloc_harder = (alloc_flags & ALLOC_HARDER);89 free_pages -= (1 << order) - 1;1011 if (alloc_flags & ALLOC_HIGH)12 min -= min / 2;1314 /* 如果調(diào)用者沒有要求更努力分配，那么減去為高階原子分配保留的頁數(shù) */15 if (likely(!alloc_harder))16 free_pages -= z->nr_reserved_highatomic;17 else18 min -= min / 4;1920 #ifdef CONFIG_CMA21 if (!(alloc_flags & ALLOC_CMA))22 free_pages -= zone_page_state(z, NR_FREE_CMA_PAGES);23 #endif2425 if (free_pages <= min + z->lowmem_reserve[classzone_idx])26 return false;2728 if (!order)29 return true;3031 /* 對于高階請求，檢查至少有一個合適的頁塊是空閑的 */32 for (o = order; o < MAX_ORDER; o++) {33 struct free_area *area = &z->free_area[o];34 int mt;3536 if (!area->nr_free)37 continue;3839 if (alloc_harder)40 return true;4142 for (mt = 0; mt < MIGRATE_PCPTYPES; mt++) {43 if (!list_empty(&area->free_list[mt]))44 return true;45 }4647 #ifdef CONFIG_CMA48 if ((alloc_flags & ALLOC_CMA) &&49 !list_empty(&area->free_list[MIGRATE_CMA])) {50 return true;51 }52 #endif53 }54 return false;55 }

第9行代碼，把空閑頁數(shù)減去申請頁數(shù)，然后減1。

第12行代碼，如果調(diào)用者是高優(yōu)先級的，把水線減半。

第15～18行代碼，如果調(diào)用者要求更努力分配，把水線減去1/4；如果調(diào)用者沒有要求更努力分配，把空閑頁數(shù)減去高階原子類型的頁數(shù)。

第21～22行代碼，如果不允許從CMA遷移類型分配，那么不能使用空閑的CMA頁，把空閑頁數(shù)減去空閑的CMA頁數(shù)。

第25行代碼，如果（空閑頁數(shù)?申請頁數(shù)+ 1）小于或等于（水線+低端內(nèi)存保留頁數(shù)），即（空閑頁數(shù)?申請頁數(shù)）小于（水線+低端內(nèi)存保留頁數(shù)），那么不能從這個區(qū)域分配頁。

第28行代碼，如果只申請一頁，那么允許從這個區(qū)域分配頁。

第32～53行代碼，如果申請階數(shù)大于0，檢查過程如下。

1）第39行代碼，如果調(diào)用者要求更努力分配，只要有一個階數(shù)大于或等于申請階數(shù)的空閑頁塊，就允許從這個區(qū)域分配頁。

2）第42～45行代碼，不可移動、可移動和可回收任何一種遷移類型，只要有一個階數(shù)大于或等于申請階數(shù)的空閑頁塊，就允許從這個區(qū)域分配頁。

3）第48～51行代碼，如果調(diào)用者指定從CMA遷移類型分配，CMA遷移類型只要有一個階數(shù)大于或等于申請階數(shù)的空閑頁塊，就允許從這個區(qū)域分配頁。

4）其他情況不允許從這個區(qū)域分配頁。

函數(shù)rmqueue負(fù)責(zé)分配頁，其代碼如下：

mm/page_alloc.c1 static inline2 struct page *rmqueue(struct zone *preferred_zone,3 struct zone *zone, unsigned int order,4 gfp_t gfp_flags, unsigned int alloc_flags,5 int migratetype)6 {7 unsigned long flags;8 struct page *page;910 if (likely(order == 0)) {11 page = rmqueue_pcplist(preferred_zone, zone, order,12 gfp_flags, migratetype);13 goto out;14 }1516 /* 如果申請階數(shù)大于1，不要試圖無限次重試。*/17 WARN_ON_ONCE((gfp_flags & __GFP_NOFAIL) && (order > 1));18 spin_lock_irqsave(&zone->lock, flags);1920 do {21 page = NULL;22 if (alloc_flags & ALLOC_HARDER) {23 page = __rmqueue_smallest(zone, order, MIGRATE_HIGHATOMIC);24 …25 }26 if (!page)27 page = __rmqueue(zone, order, migratetype);28 } while (page && check_new_pages(page, order));29 spin_unlock(&zone->lock);30 if (!page)31 goto failed;32 …33 local_irq_restore(flags);3435 out:36 VM_BUG_ON_PAGE(page && bad_range(zone, page), page);37 return page;3839 failed:40 local_irq_restore(flags);41 return NULL;42 }

第10～14行代碼，如果申請階數(shù)是0，那么從每處理器頁集合分配頁。

如果申請階數(shù)大于0，處理過程如下。

1）第22行和第23行代碼，如果調(diào)用者要求更努力分配，先嘗試從高階原子類型分配頁。

2）第27行代碼，從指定遷移類型分配頁。

函數(shù)rmqueue_pcplist負(fù)責(zé)從內(nèi)存區(qū)域的每處理器頁集合分配頁，把主要工作委托給函數(shù)__rmqueue_pcplist。函數(shù)__rmqueue_pcplist的代碼如下：

mm/page_alloc.c1 static struct page *__rmqueue_pcplist(struct zone *zone, int migratetype,2 bool cold, struct per_cpu_pages *pcp,3 struct list_head *list)4 {5 struct page *page;67 do {8 if (list_empty(list)) {9 pcp->count += rmqueue_bulk(zone, 0,10 pcp->batch, list,11 migratetype, cold);12 if (unlikely(list_empty(list)))13 return NULL;14 }1516 if (cold)17 page = list_last_entry(list, struct page, lru);18 else19 page = list_first_entry(list, struct page, lru);2021 list_del(&page->lru);22 pcp->count--;23 } while (check_new_pcp(page));2425 return page;26 }

第8～11行代碼，如果每處理器頁集合中指定遷移類型的鏈表是空的，那么批量申請頁加入鏈表。

第16～19行代碼，分配一頁，如果調(diào)用者指定標(biāo)志位__GFP_COLD要求分配緩存冷頁，就從鏈表尾部分配一頁，否則從鏈表首部分配一頁。

函數(shù)__rmqueue的處理過程如下。

1）從指定遷移類型分配頁，如果分配成功，那么處理結(jié)束。

2）如果指定遷移類型是可移動類型，那么從CMA類型盜用頁。

3）從備用遷移類型盜用頁。

mm/page_alloc.cstatic struct page *__rmqueue(struct zone *zone, unsigned int order,int migratetype){struct page *page;retry:page = __rmqueue_smallest(zone, order, migratetype);if (unlikely(!page)) {if (migratetype == MIGRATE_MOVABLE)page = __rmqueue_cma_fallback(zone, order);if (!page && __rmqueue_fallback(zone, order, migratetype))goto retry;}…return page;}

函數(shù)__rmqueue_smallest從申請階數(shù)到最大分配階數(shù)逐個嘗試：如果指定遷移類型的空閑鏈表不是空的，從鏈表取出第一個頁塊；如果頁塊階數(shù)比申請階數(shù)大，那么重復(fù)分裂頁塊，把后一半插入低一階的空閑鏈表，直到獲得一個大小為申請階數(shù)的頁塊。

mm/page_alloc.cstatic inlinestruct page *__rmqueue_smallest(struct zone *zone, unsigned int order,int migratetype){unsigned int current_order;struct free_area *area;struct page *page;/* 在首選遷移類型的空閑鏈表中查找長度合適的頁塊 */for (current_order = order; current_order < MAX_ORDER; ++current_order) {area = &(zone->free_area[current_order]);page = list_first_entry_or_null(&area->free_list[migratetype],struct page, lru);if (!page)continue;list_del(&page->lru);rmv_page_order(page);area->nr_free--;expand(zone, page, order, current_order, area, migratetype);set_pcppage_migratetype(page, migratetype);return page;}return NULL;}

函數(shù)__rmqueue_fallback負(fù)責(zé)從備用遷移類型盜用頁，從最大分配階向下到申請階數(shù)逐個嘗試，依次查看備用類型優(yōu)先級列表中的每種遷移類型是否有空閑頁塊，如果有，就從這種遷移類型盜用頁。

mm/page_alloc.cstatic inline bool__rmqueue_fallback(struct zone *zone, unsigned int order, int start_migratetype){struct free_area *area;unsigned int current_order;struct page *page;int fallback_mt;bool can_steal;/* 在備用遷移類型的空閑鏈表中找到最大的頁塊 */for (current_order = MAX_ORDER-1;current_order >= order && current_order <= MAX_ORDER-1;--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)continue;page = list_first_entry(&area->free_list[fallback_mt],struct page, lru);steal_suitable_fallback(zone, page, start_migratetype,can_steal);...return true;}return false;}

（2）慢速路徑。如果使用低水線分配失敗，那么執(zhí)行慢速路徑，慢速路徑是在函數(shù)__alloc_pages_slowpath中實現(xiàn)的，執(zhí)行流程如圖3.20所示，主要步驟如下。

圖3.20 慢速路徑

1）如果允許異步回收頁，那么針對每個目標(biāo)區(qū)域，喚醒區(qū)域所屬內(nèi)存節(jié)點的頁回收線程。

2）使用最低水線嘗試分配。

3）針對申請階數(shù)大于0：如果允許直接回收頁，那么執(zhí)行異步模式的內(nèi)存碎片整理，然后嘗試分配。

4）如果調(diào)用者承諾“給我少量緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”，那么在忽略水線的情況下嘗試分配。

5）直接回收頁，然后嘗試分配。

6）針對申請階數(shù)大于0：執(zhí)行同步模式的內(nèi)存碎片整理，然后嘗試分配。

7）如果多次嘗試直接回收頁和同步模式的內(nèi)存碎片整理，仍然分配失敗，那么使用殺傷力比較大的內(nèi)存耗盡殺手選擇一個進(jìn)程殺死，然后嘗試分配。

頁分配器認(rèn)為階數(shù)大于3是昂貴的分配，有些地方做了特殊處理。

函數(shù)__alloc_pages_slowpath的主要代碼如下：

mm/page_alloc.cstatic inline struct page *__alloc_pages_slowpath(gfp_t gfp_mask, unsigned int order,struct alloc_context *ac){bool can_direct_reclaim = gfp_mask & __GFP_DIRECT_RECLAIM;const bool costly_order = order > PAGE_ALLOC_COSTLY_ORDER;struct page *page = NULL;unsigned int alloc_flags;unsigned long did_some_progress;enum compact_priority compact_priority;enum compact_result compact_result;int compaction_retries;int no_progress_loops;unsigned long alloc_start = jiffies;unsigned int stall_timeout = 10 * HZ;unsigned int cpuset_mems_cookie;/* 申請階數(shù)不能超過頁分配器支持的最大分配階 */if (order >= MAX_ORDER) {WARN_ON_ONCE(!(gfp_mask & __GFP_NOWARN));return NULL;}...retry_cpuset:compaction_retries = 0;no_progress_loops = 0;compact_priority = DEF_COMPACT_PRIORITY;/** 后面可能檢查cpuset是否允許當(dāng)前進(jìn)程從哪些內(nèi)存節(jié)點申請頁，* 需要讀當(dāng)前進(jìn)程的成員mems_allowed。使用順序鎖保護(hù)*/cpuset_mems_cookie = read_mems_allowed_begin();/* 把分配標(biāo)志位轉(zhuǎn)換成內(nèi)部分配標(biāo)志位 */alloc_flags = gfp_to_alloc_flags(gfp_mask);/* 獲取首選的內(nèi)存區(qū)域 */ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,ac->high_zoneidx, ac->nodemask);if (!ac->preferred_zoneref->zone)goto nopage;/* 異步回收頁，喚醒頁回收線程 */if (gfp_mask & __GFP_KSWAPD_RECLAIM)wake_all_kswapds(order, ac);/* 使用最低水線分配頁 */page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);if (page)goto got_pg;/** 針對申請階數(shù)大于0，如果滿足以下3個條件。* （1）允許直接回收頁。* （2）申請階數(shù)大于3，或者指定遷移類型不是可移動類型。177 第 3 章 內(nèi)存管理* （3）調(diào)用者沒有承諾“給我少量緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”。* 那么執(zhí)行異步模式的內(nèi)存碎片整理*/if (can_direct_reclaim &&(costly_order ||(order > 0 && ac->migratetype != MIGRATE_MOVABLE))&& !gfp_pfmemalloc_allowed(gfp_mask)) {page = __alloc_pages_direct_compact(gfp_mask, order,alloc_flags, ac,INIT_COMPACT_PRIORITY,&compact_result);if (page)goto got_pg;/* 申請階數(shù)大于3，并且調(diào)用者要求不要重試 */if (costly_order && (gfp_mask & __GFP_NORETRY)) {/** 同步模式的內(nèi)存碎片整理最近失敗了，所以內(nèi)存碎片整理被延遲執(zhí)行，* 沒必要繼續(xù)嘗試分配*/if (compact_result == COMPACT_DEFERRED)goto nopage;/** 同步模式的內(nèi)存碎片整理代價太大，繼續(xù)使用異步模式的* 內(nèi)存碎片整理*/compact_priority = INIT_COMPACT_PRIORITY;}}retry:/* 確保頁回收線程在我們循環(huán)的時候不會意外地睡眠 */if (gfp_mask & __GFP_KSWAPD_RECLAIM)wake_all_kswapds(order, ac);/** 如果調(diào)用者承諾“給我少量緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”，* 則忽略水線*/if (gfp_pfmemalloc_allowed(gfp_mask))alloc_flags = ALLOC_NO_WATERMARKS;/** 如果調(diào)用者沒有要求使用cpuset，或者要求忽略水線，那么重新獲取區(qū)域列表*/if (!(alloc_flags & ALLOC_CPUSET) || (alloc_flags & ALLOC_NO_WATERMARKS)) {ac->zonelist = node_zonelist(numa_node_id(), gfp_mask);ac->preferred_zoneref = first_zones_zonelist(ac->zonelist,ac->high_zoneidx, ac->nodemask);}/* 使用可能調(diào)整過的區(qū)域列表和分配標(biāo)志嘗試 */page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);if (page)goto got_pg;/* 調(diào)用者不愿意等待，不允許直接回收頁，那么放棄 */if (!can_direct_reclaim)goto nopage;…/** 直接回收頁的時候給進(jìn)程設(shè)置了標(biāo)志位PF_MEMALLOC，在直接回收頁的過程中* 可能申請頁，為了防止直接回收遞歸，這里發(fā)現(xiàn)進(jìn)程設(shè)置了標(biāo)志位PF_MEMALLOC，* 立即放棄*/if (current->flags & PF_MEMALLOC)goto nopage;/* 直接回收頁 */page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,&did_some_progress);if (page)goto got_pg;/* 針對申請階數(shù)大于0，執(zhí)行同步模式的內(nèi)存碎片整理 */page = __alloc_pages_direct_compact(gfp_mask, order, alloc_flags, ac,compact_priority, &compact_result);if (page)goto got_pg;/* 如果調(diào)用者要求不要重試，那么放棄 */if (gfp_mask & __GFP_NORETRY)goto nopage;/* 如果申請階數(shù)大于3，并且調(diào)用者沒有要求重試，那么放棄 */if (costly_order && !(gfp_mask & __GFP_REPEAT))goto nopage;/* 檢查重新嘗試回收頁是否有意義 */if (should_reclaim_retry(gfp_mask, order, ac, alloc_flags,did_some_progress > 0, &no_progress_loops))goto retry;/** 申請階數(shù)大于0：判斷是否應(yīng)該重試內(nèi)存碎片整理。* did_some_progress > 0表示直接回收頁有進(jìn)展。* 如果直接回收頁沒有進(jìn)展，那么重試內(nèi)存碎片整理沒有意義，* 因為內(nèi)存碎片整理的當(dāng)前實現(xiàn)依賴足夠多的空閑頁*/if (did_some_progress > 0 &&should_compact_retry(ac, order, alloc_flags,compact_result, &compact_priority,&compaction_retries))goto retry;/* 如果cpuset修改了允許當(dāng)前進(jìn)程從哪些內(nèi)存節(jié)點申請頁，那么需要重試 */if (read_mems_allowed_retry(cpuset_mems_cookie))goto retry_cpuset;/* 使用內(nèi)存耗盡殺手選擇一個進(jìn)程殺死 */page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);if (page)goto got_pg;/** 如果當(dāng)前進(jìn)程正在被內(nèi)存耗盡殺手殺死，并且忽略水線或者不允許使用* 緊急保留內(nèi)存，那么不要無限循環(huán)*/if (test_thread_flag(TIF_MEMDIE) &&(alloc_flags == ALLOC_NO_WATERMARKS ||(gfp_mask & __GFP_NOMEMALLOC)))goto nopage;/* 如果內(nèi)存耗盡殺手取得進(jìn)展，那么重試 */if (did_some_progress) {no_progress_loops = 0;goto retry;}nopage:/* 如果cpuset修改了允許當(dāng)前進(jìn)程從哪些內(nèi)存節(jié)點申請頁，那么需要重試 */if (read_mems_allowed_retry(cpuset_mems_cookie))goto retry_cpuset;/* 確保不能失敗的請求沒有漏掉，總是重試 */if (gfp_mask & __GFP_NOFAIL) {/* 同時要求不能失敗和不能直接回收頁，是錯誤用法 */if (WARN_ON_ONCE(!can_direct_reclaim))goto fail;…/** 先使用標(biāo)志位ALLOC_HARDER|ALLOC_CPUSET嘗試分配，* 如果分配失敗，那么使用標(biāo)志位ALLOC_HARDER嘗試分配*/page = __alloc_pages_cpuset_fallback(gfp_mask, order, ALLOC_HARDER, ac);if (page)goto got_pg;cond_resched();goto retry;}fail:warn_alloc(gfp_mask, ac->nodemask,"page allocation failure: order:%u", order);got_pg:return page;}

頁分配器使用函數(shù)gfp_to_alloc_flags把分配標(biāo)志位轉(zhuǎn)換成內(nèi)部分配標(biāo)志位，其代碼如下：

mm/page_alloc.cstatic inline unsigned intgfp_to_alloc_flags(gfp_t gfp_mask){/* 使用最低水線，并且檢查cpuset是否允許當(dāng)前進(jìn)程從某個內(nèi)存節(jié)點分配頁 */unsigned int alloc_flags = ALLOC_WMARK_MIN | ALLOC_CPUSET;/* 假設(shè)__GFP_HIGH和ALLOC_HIGH相同，為了節(jié)省一個if分支 */BUILD_BUG_ON(__GFP_HIGH != (__force gfp_t) ALLOC_HIGH);alloc_flags |= (__force int) (gfp_mask & __GFP_HIGH);if (gfp_mask & __GFP_ATOMIC) {/* 原子分配 *//** 原子分配：* 如果沒有要求禁止使用緊急保留內(nèi)存，那么需要更努力地分配。* 如果要求禁止使用緊急保留內(nèi)存，那么不需要更努力地分配*/if (!(gfp_mask & __GFP_NOMEMALLOC))alloc_flags |= ALLOC_HARDER;/*對于原子分配，忽略cpuset。*/alloc_flags &= ~ALLOC_CPUSET;} else if (unlikely(rt_task(current)) && !in_interrupt())/* 如果當(dāng)前進(jìn)程是實時進(jìn)程，并且沒有被中斷搶占，那么需要更努力地分配 */alloc_flags |= ALLOC_HARDER;#ifdef CONFIG_CMA/* 可移動類型可以從CMA類型盜用頁 */if (gfpflags_to_migratetype(gfp_mask) == MIGRATE_MOVABLE)alloc_flags |= ALLOC_CMA;#endifreturn alloc_flags;}

3.7.6釋放頁

頁分配器提供了以下釋放頁的接口。

（1）void __free_pages(struct page *page, unsigned int order)，第一個參數(shù)是第一個物理頁的page實例的地址，第二個參數(shù)是階數(shù)。

（2）void free_pages(unsigned long addr, unsigned int order)，第一個參數(shù)是第一個物理頁的起始內(nèi)核虛擬地址，第二個參數(shù)是階數(shù)。

函數(shù)__free_pages的代碼如下：

mm/page_alloc.cvoid __free_pages(struct page *page, unsigned int order){if (put_page_testzero(page)) {if (order == 0)free_hot_cold_page(page, false);else__free_pages_ok(page, order);}}

首先把頁的引用計數(shù)減1，只有頁的引用計數(shù)變成零，才真正釋放頁：如果階數(shù)是0，不還給伙伴分配器，而是當(dāng)作緩存熱頁添加到每處理器頁集合中；如果階數(shù)大于0，調(diào)用函數(shù)__free_pages_ok以釋放頁。

函數(shù)free_hot_cold_page把一頁添加到每處理器頁集合中，如果頁集合中的頁數(shù)量大于或等于高水線，那么批量返還給伙伴分配器。第二個參數(shù)cold表示緩存冷熱程度，主動釋放的頁作為緩存熱頁，回收的頁作為緩存冷頁，因為回收的是最近最少使用的頁。

mm/page_alloc.cvoid free_hot_cold_page(struct page *page, bool cold){struct zone *zone = page_zone(page);struct per_cpu_pages *pcp;unsigned long flags;unsigned long pfn = page_to_pfn(page);int migratetype;if (!free_pcp_prepare(page))return;migratetype = get_pfnblock_migratetype(page, pfn);/* 得到頁所屬頁塊的遷移類型 */set_pcppage_migratetype(page, migratetype);/* page->index保存真實的遷移類型 */local_irq_save(flags);__count_vm_event(PGFREE);/** 每處理器集合只存放不可移動、可回收和可移動這3種類型的頁，* 如果頁的類型不是這3種類型，處理方法是：* （1）如果是隔離類型的頁，不需要添加到每處理器頁集合，直接釋放；* （2）其他類型的頁添加到可移動類型鏈表中，page->index保存真實的遷移類型。*/if (migratetype >= MIGRATE_PCPTYPES) {if (unlikely(is_migrate_isolate(migratetype))) {free_one_page(zone, page, pfn, 0, migratetype);goto out;}migratetype = MIGRATE_MOVABLE;}/* 添加到對應(yīng)遷移類型的鏈表中，如果是緩存熱頁，添加到首部，否則添加到尾部 */pcp = &this_cpu_ptr(zone->pageset)->pcp;if (!cold)list_add(&page->lru, &pcp->lists[migratetype]);elselist_add_tail(&page->lru, &pcp->lists[migratetype]);pcp->count++;/* 如果頁集合中的頁數(shù)量大于或等于高水線，那么批量返還給伙伴分配器 */if (pcp->count >= pcp->high) {unsigned long batch = READ_ONCE(pcp->batch);free_pcppages_bulk(zone, batch, pcp);pcp->count -= batch;}out:local_irq_restore(flags);}

函數(shù)__free_pages_ok負(fù)責(zé)釋放階數(shù)大于0的頁塊，最終調(diào)用到釋放頁的核心函數(shù)__free_one_page，算法是：如果伙伴是空閑的，并且伙伴在同一個內(nèi)存區(qū)域，那么和伙伴合并，注意隔離類型的頁塊和其他類型的頁塊不能合并。算法還做了優(yōu)化處理：

假設(shè)最后合并成的頁塊階數(shù)是order，如果order小于(MAX_ORDER?2)，則檢查(order+1)階的伙伴是否空閑，如果空閑，那么order階的伙伴可能正在釋放，很快就可以合并成(order+2)階的頁塊。為了防止當(dāng)前頁塊很快被分配出去，把當(dāng)前頁塊添加到空閑鏈表的尾部。

函數(shù)__free_pages_ok的代碼如下：

mm/page_alloc.c__free_pages_ok() -> free_one_page() -> __free_one_page()static inline void __free_one_page(struct page *page,unsigned long pfn,struct zone *zone, unsigned int order,int migratetype){unsigned long combined_pfn;unsigned long uninitialized_var(buddy_pfn);struct page *buddy;unsigned int max_order;/* pageblock_order是按可移動性分組的階數(shù) */max_order = min_t(unsigned int, MAX_ORDER, pageblock_order + 1);…continue_merging:/*如果伙伴是空閑的，和伙伴合并，重復(fù)這個操作直到階數(shù)等于(max_order-1)。*/while (order < max_order - 1) {buddy_pfn = __find_buddy_pfn(pfn, order);/* 得到伙伴的起始物理頁號 */buddy = page + (buddy_pfn - pfn); /* 得到伙伴的第一頁的page實例 */if (!pfn_valid_within(buddy_pfn))goto done_merging;/* 檢查伙伴是空閑的并且在相同的內(nèi)存區(qū)域 */if (!page_is_buddy(page, buddy, order))goto done_merging;/** 開啟了調(diào)試頁分配的配置宏CONFIG_DEBUG_PAGEALLOC，伙伴充當(dāng)警戒頁。*/if (page_is_guard(buddy)) {clear_page_guard(zone, buddy, order, migratetype);} else {/* 伙伴是空閑的，把伙伴從空閑鏈表中刪除 */list_del(&buddy->lru);zone->free_area[order].nr_free--;rmv_page_order(buddy);}combined_pfn = buddy_pfn & pfn;page = page + (combined_pfn - pfn);pfn = combined_pfn;order++;}if (max_order < MAX_ORDER) {/** 運行到這里，意味著階數(shù)大于或等于分組階數(shù)pageblock_order，* 阻止把隔離類型的頁塊和其他類型的頁塊合并*/if (unlikely(has_isolate_pageblock(zone))) {int buddy_mt;buddy_pfn = __find_buddy_pfn(pfn, order);buddy = page + (buddy_pfn - pfn);buddy_mt = get_pageblock_migratetype(buddy);/*如果一個是隔離類型的頁塊，另一個是其他類型的頁塊，不能合并 */if (migratetype != buddy_mt&& (is_migrate_isolate(migratetype) ||is_migrate_isolate(buddy_mt)))goto done_merging;}/* 如果兩個都是隔離類型的頁塊，或者都是其他類型的頁塊，那么繼續(xù)合并 */max_order++;goto continue_merging;}done_merging:set_page_order(page, order);/** 最后合并成的頁塊階數(shù)是order，如果order小于(MAX_ORDER-2)，* 則檢查(order+1)階的伙伴是否空閑，如果空閑，那么order階的伙伴可能正在釋放，* 很快就可以合并成(order+2)階的頁塊。為了防止當(dāng)前頁塊很快被分配出去，* 把當(dāng)前頁塊添加到空閑鏈表的尾部*/if ((order < MAX_ORDER-2) && pfn_valid_within(buddy_pfn)) {struct page *higher_page, *higher_buddy;combined_pfn = buddy_pfn & pfn;higher_page = page + (combined_pfn - pfn);buddy_pfn = __find_buddy_pfn(combined_pfn, order + 1);higher_buddy = higher_page + (buddy_pfn - combined_pfn);if (pfn_valid_within(buddy_pfn) &&page_is_buddy(higher_page, higher_buddy, order + 1)) {list_add_tail(&page->lru,&zone->free_area[order].free_list[migratetype]);goto out;}}/* 添加到空閑鏈表的首部 */list_add(&page->lru, &zone->free_area[order].free_list[migratetype]);out:zone->free_area[order].nr_free++;}

審核編輯：湯梓紅