伙伴分配器的内核实现
主要參考了《深入linux內(nèi)核》和《Linux內(nèi)核深度解析》，另外簡單淺析了一下相關(guān)內(nèi)容
文章目錄
- 伙伴分配器
- 基本的伙伴分配器
- 分區(qū)的伙伴分配器
- 管理分區(qū)內(nèi)存的鏈表
- 根據(jù)分配標(biāo)志獲取首選區(qū)域類型
- 備用區(qū)域列表（從其他節(jié)點或區(qū)域借用物理頁）
- 區(qū)域水線
- 相關(guān)數(shù)據(jù)結(jié)構(gòu)
- 計算水位線
- 水位的變化
- 防止過度借用
- /proc/zoneinfo
- 根據(jù)可移動性分組
- 每處理器頁集合（分配單頁優(yōu)化）
- 分配標(biāo)志位
- 復(fù)合頁
- 對高階原子分配的優(yōu)化處理（MIGRATE_HIGHATOMIC）
- 分配頁
- 分配接口
- 核心函數(shù)的實現(xiàn)__alloc_pages_nodemask
- 快速分配 get_page_from_freelist
- 慢速分配 __alloc_pages_slowpath
- 釋放頁
- free_hot_cold_page
- __free_pages_ok
伙伴分配器
當(dāng)系統(tǒng)內(nèi)核初始化完畢后，使用頁分配器管理物理頁，使用的頁分配器是伙伴分配器，伙伴分配器的特點是算法簡單且高效。
基本的伙伴分配器
連續(xù)的物理頁稱為頁塊（page block）。階（order）是伙伴分配器的一個專業(yè)術(shù)語，是頁的數(shù)量單位，2 ^ n個連續(xù)頁稱為 n 階頁塊。 滿足以下條件的兩個n階頁塊稱為伙伴（buddy）：
1、兩個頁塊是相鄰的，即物理地址是連續(xù)的；
2、頁塊的第一頁的物理頁號必須是2n的整數(shù)倍；
3、如果合并成（n+1）階頁塊，第一頁的物理頁號必須是2n+1的整數(shù)倍。
伙伴分配器分配和釋放物理頁的數(shù)量單位為階。分配n階頁塊的過程如下：
1、查看是否有空閑的n階頁塊，如果有直接分配；否則，繼續(xù)執(zhí)行下一步；
2、查看是否存在空閑的 n+1 階頁塊，如果有，把 n+1 階頁塊分裂為兩個n階頁塊，一個插入空閑n階頁塊鏈表，另一個分配出去；否則繼續(xù)執(zhí)行下一步。
3、查看是否存在空閑的 n+2 階頁塊，如果有把 n+2 階頁塊分裂為兩個(n+2)階頁塊，一個插入空閑 n+1 階頁塊鏈表，另一個分裂為兩個n階頁塊，一個插入空間n階頁塊鏈表，另一個分配出去；如果沒有，繼續(xù)查看更高階是否存在空閑頁塊。
分區(qū)的伙伴分配器
內(nèi)核在基本的伙伴分配器基礎(chǔ)改進擴展
-
支持內(nèi)存節(jié)點和區(qū)域，稱為分區(qū)的伙伴分配器(zond buddy allocator) ;
-
為了預(yù)防內(nèi)存碎片，把物理頁根據(jù)可移動性分組；（分成不同的鏈表管理）
-
針對分配單頁做了性能優(yōu)化，為了減少處理器之間的鎖競爭，在內(nèi)存區(qū)域增加1個每處理器頁集合。
管理分區(qū)內(nèi)存的鏈表
分區(qū)的伙伴分配器專注于某個內(nèi)存節(jié)點的某個區(qū)域。內(nèi)存區(qū)域的結(jié)構(gòu)體成員free_area用來維護空閑頁塊，數(shù)組下標(biāo)對應(yīng)頁塊的階數(shù)。 系統(tǒng)內(nèi)存中的每個物理內(nèi)存頁（頁幀），都對應(yīng)于一個struct page實例,，每個內(nèi)存域都關(guān)聯(lián)了一個struct zone的實例，其中保存了用于管理伙伴數(shù)據(jù)的主要數(shù)數(shù)組。
struct zone {/* Read-mostly fields */.../* free areas of different sizes */struct free_area free_area[MAX_ORDER]; // 不同長度的空閑區(qū)域... };struct free_area {struct list_head free_list[MIGRATE_TYPES]; // MIGRATE_TYPESunsigned long nr_free; };MAX_ORDER是最大階數(shù)，實際上是可分配的最大階數(shù)減1，默認(rèn)值是11，意味著伙伴分配器一次最多可以分配2^10頁。
#ifndef CONFIG_FORCE_MAX_ZONEORDER #define MAX_ORDER 11 #else #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER #endif根據(jù)分配標(biāo)志獲取首選區(qū)域類型
申請頁時，最低的4個標(biāo)志位用來指定首選的內(nèi)存區(qū)域類型，內(nèi)核源碼如下：
include\linux\gfp.h
標(biāo)志組合
#define ___GFP_DMA 0x01u #define ___GFP_HIGHMEM 0x02u #define ___GFP_DMA32 0x04u #define ___GFP_MOVABLE 0x08u內(nèi)存區(qū)域類型
為什么要使用OPT_ZONE_DMA，而不使用ZONE_DMA？
因為DMA區(qū)域是可選的，如果不存在只能訪問16MB以下物理內(nèi)存的外圍設(shè)備，那么不需要定義DMA區(qū)域，OPT_ZONE_DMA就是ZONE_NORMAL，
從普通區(qū)域申請頁。高端內(nèi)存區(qū)域和DMA32區(qū)域也是可選的。
內(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個二進制位存放區(qū)域類型。
宏GFP_ZONE_TABLE是一個常量，編譯器在編譯時會進行優(yōu)化，直接計算出結(jié)果，不會等到運行程序的時候才計算數(shù)值。
#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ù)（作為zone_type所對應(yīng)的類型）。
備用區(qū)域列表（從其他節(jié)點或區(qū)域借用物理頁）
如果首選的內(nèi)存節(jié)點或區(qū)域不能滿足分配請求，可以從備用的內(nèi)存區(qū)域借用物理頁。
借用必須遵守相應(yīng)的規(guī)則：
- 一個內(nèi)存節(jié)點的某個區(qū)域類型可以從另一個內(nèi)存節(jié)點的相同區(qū)域類型借用物理頁，比如節(jié)點0的普通區(qū)域可以從節(jié)點1的普通區(qū)域借用物理頁;
- 高區(qū)域類型**（高地址的區(qū)域類型）可以從低區(qū)域類型（低地址的區(qū)域類型）**借用物理頁，比如普通區(qū)域可以從DMA區(qū)域借用物理頁;
- 低區(qū)域類型不能從高區(qū)域類型借用物理頁，比如DMA區(qū)域不能從普通區(qū)域借用物理頁。
內(nèi)存節(jié)點的pg_data_t實例已定義備用區(qū)域列表，內(nèi)核源碼如下：
include\linux\mmzone.h
typedef struct pglist_data {struct zone node_zones[MAX_NR_ZONES]; // 內(nèi)存區(qū)域數(shù)組struct zonelist node_zonelists[MAX_ZONELISTS]; // 備用區(qū)域列表int nr_zones; // 該節(jié)點包含的內(nèi)存區(qū)域數(shù)量 #ifdef CONFIG_FLAT_NODE_MEM_MAP /* means !SPARSEMEM */struct page *node_mem_map; // 頁描述符數(shù)組 #ifdef CONFIG_PAGE_EXTENSIONstruct page_ext *node_page_ext; // 頁的擴展屬性 #endif #endif...unsigned long node_start_pfn; // 該節(jié)點的起始物理頁號unsigned long node_present_pages; /// 物理頁的總數(shù)unsigned long node_spanned_pages; // 物理頁的總長度，包括空洞int node_id; // 節(jié)點標(biāo)識符... } pg_data_t;struct zonelist node_zonelists[MAX_ZONELISTS]; 中的成員項
enum {ZONELIST_FALLBACK, // 包含所有內(nèi)存點的備用區(qū)域列表 #ifdef CONFIG_NUMA/** The NUMA zonelists are doubled because we need zonelists that* restrict the allocations to a single node for __GFP_THISNODE.*/ZONELIST_NOFALLBACK, // 只包含當(dāng)前內(nèi)存節(jié)點的備用區(qū)域列表 #endifMAX_ZONELISTS }; 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ū)域列表有兩種排序方法:
a.節(jié)點優(yōu)先順序
- 先根據(jù)節(jié)點距離從小到大排序，然后在每個節(jié)點里面根據(jù)區(qū)域類型從高到低排序。
- 優(yōu)點是優(yōu)先選擇距離近的內(nèi)存，缺點是在高區(qū)域耗盡以前使用低區(qū)域。
b.區(qū)域優(yōu)先順序
- 先根據(jù)區(qū)域類型從高到低排序，然后在每個區(qū)域類型里面根據(jù)節(jié)點距離從小到大排序。
- 優(yōu)點是減少低區(qū)域耗盡的概率，缺點是不能保證優(yōu)先選擇距離近的內(nèi)存。
默認(rèn)的排序方法就是自動選擇最優(yōu)的排序方法：比如是64位系統(tǒng)，因為需要DMA和DMA32區(qū)域的備用相對少，所以選擇節(jié)點優(yōu)先順序；如果是32位系統(tǒng)，選擇區(qū)域優(yōu)先順序。
區(qū)域水線
首選的內(nèi)存區(qū)域什么情況下從備用區(qū)域借用物理頁呢？
每個內(nèi)存區(qū)域有3個水線
a.高水線（high）：如果內(nèi)存區(qū)域的空閑頁數(shù)大于高水線，說明內(nèi)存區(qū)域的內(nèi)存充足；
b.低水線（low）：如果內(nèi)存區(qū)域的空閑頁數(shù)小于低水線，說明內(nèi)存區(qū)域的內(nèi)存輕微不足；
c.最低水線（min）：如果內(nèi)存區(qū)域的空閑頁數(shù)小于最低水線，說明內(nèi)存區(qū)域的內(nèi)存嚴(yán)重不足。（需要開啟回收內(nèi)存的工作）
struct zone {/* Read-mostly fields *//* zone watermarks, access with *_wmark_pages(zone) macros */unsigned long watermark[NR_WMARK]; // 頁分配器使用的水線- 最低水線以下的內(nèi)存稱為緊急保留內(nèi)存，在內(nèi)存嚴(yán)重不足的緊急情況下，給承諾“分給我們少量的緊急保留內(nèi)存使用，我可以釋放更多的內(nèi)存”的進程使用。
- 設(shè)置了進程標(biāo)志位PF_MEMALLOC的進程可以使用緊急保留內(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)存。
相關(guān)數(shù)據(jù)結(jié)構(gòu)
watermark水位控制內(nèi)核源碼重要數(shù)據(jù)參數(shù)
enum zone_watermarks {WMARK_MIN,WMARK_LOW,WMARK_HIGH,NR_WMARK };#define min_wmark_pages(z) (z->watermark[WMARK_MIN]) #define low_wmark_pages(z) (z->watermark[WMARK_LOW]) #define high_wmark_pages(z) (z->watermark[WMARK_HIGH]) struct zone {/* Read-mostly fields *//* zone watermarks, access with *_wmark_pages(zone) macros */unsigned long watermark[NR_WMARK]; // 頁分配器使用的水線...unsigned long managed_pages; // 伙伴分配器管理的物理頁的數(shù)量unsigned long spanned_pages; // 當(dāng)前區(qū)域跨越的總頁數(shù)，包括空洞unsigned long present_pages; // 當(dāng)前區(qū)域存在的物理頁的數(shù)量，不包括空洞- spanned_pages: 代表的是這個zone中所有的頁，包含空洞，計算公式是: zone_end_pfn - zone_start_pfn
- present_pages： 代表的是這個zone中可用的所有物理頁，計算公式是：spanned_pages-hole_pages
- managed_pages： 代表的是通過buddy管理的所有可用的頁，計算公式是：present_pages - reserved_pages
- 三者的關(guān)系是： spanned_pages > present_pages > managed_pages
它們?nèi)咧g的關(guān)系: spanned_pages > present_pages > managed_pages。
計算水位線
內(nèi)核在初始化階段會調(diào)用 init_per_zone_wmark_min 來進行每個zone 的內(nèi)存水位線初始化，同時也會設(shè)置zone的lowmem_reserve 值
計算水線時，有兩個重要的參數(shù)。
min_free_kbytes代表的是系統(tǒng)保留空閑內(nèi)存的最低限，watermark[WMARK_MIN]的值是通過min_free_kbytes計算出來。
（1）min_free_kbytes是最小空閑字節(jié)數(shù)。默認(rèn)值 = 4 * sqrt(lowmem_kbytes)，并且限制在范圍[128,65536]以內(nèi)。
其中l(wèi)owmem_kbytes是超過high的水位的頁和，單位是KB。參考文件“mm/page_alloc.c”中的函數(shù)init_per_zone_wmark_min。可以通過文件“/proc/sys/vm/min_free_kbytes”設(shè)置最小空閑字節(jié)數(shù)。
- int __meminit init_per_zone_wmark_min(void) ...// lowmem中超過高水位的頁的總和，單位kbytes，就是lowmem中超過high的水位的頁乘以4得到lowmem_kybyteslowmem_kbytes = nr_free_buffer_pages() * (PAGE_SIZE >> 10);new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16);// min_free_kybtes最小不能小于128k，最大超過65535kif (new_min_free_kbytes > user_min_free_kbytes) { // int user_min_free_kbytes = -1;min_free_kbytes = new_min_free_kbytes;if (min_free_kbytes < 128)min_free_kbytes = 128;if (min_free_kbytes > 65536)min_free_kbytes = 65536; ...
（2）“watermark_scale_factor"這個系數(shù)，其默認(rèn)值為10，對應(yīng)內(nèi)存占比0.1%(10/10000)，可通過”/proc/ sys/vm/watermark_scale_factor"設(shè)置，最大為1000。當(dāng)它的值被設(shè)定為1000時，意味著"low"與"min"之間的差值，以及"high"與"low"之間的差值都將是內(nèi)存大小的10%(1000/10000)。
文件“mm/page_alloc.c”中的函數(shù)__setup_per_zone_wmarks()負(fù)責(zé)計算每個內(nèi)存區(qū)域的最低水線、低水線和高水線。
計算最低水線的方法如下：
高端內(nèi)存區(qū)域（ZONE_HIGHMEM）：這是32位時代的產(chǎn)物，內(nèi)核和用戶地址空間按1 : 3劃分，內(nèi)核地址空間只有1GB，不能把1GB以上的內(nèi)存直接映射到內(nèi)核地址空間，把不能直接映射的內(nèi)存劃分到高端內(nèi)存區(qū)域（采用間接映射）。通常把DMA區(qū)域、DMA32區(qū)域和普通區(qū)域統(tǒng)稱為低端內(nèi)存區(qū)域。64位系統(tǒng)的內(nèi)核虛擬地址空間非常大，不再需要高端內(nèi)存區(qū)域（內(nèi)核虛擬地址空間夠用）。
Linux的內(nèi)核空間（低端內(nèi)存、高端內(nèi)存）
-
（1）min_free_pages = min_free_kbytes對應(yīng)的頁數(shù)==（動態(tài)變化）==。
- min_free_kbytes = 4 * sqrt(lowmem_kbytes)，lowmem_kbytes中和 managed 與 當(dāng)前high水位的差值，詳解nr_free_zone_pages函數(shù)（mm\page_alloc.c)
- 高水線比較大的時候，最低水線比較小，因為kswap線程在很早就開啟了
- 高水線比較小的時候，最低水線比較大，因為kswap線程開啟比較晚，需要保留足夠內(nèi)存給它用
-
（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。
如下圖
水位的變化
下面這張時序圖能很好地表示水位的變化：
剩余內(nèi)存高于pages_high，說明剩余內(nèi)存比較多，沒有內(nèi)存壓力；
剩余內(nèi)存小于pages_high，說明內(nèi)存有一定壓力，但還可以滿足新內(nèi)存請求；
剩余內(nèi)存小于pages_low，說明內(nèi)存壓力比較大，剩余內(nèi)存不多了。這時，kswapd0 會被喚醒，執(zhí)行內(nèi)存回收，直至剩余內(nèi)存大于pages_high；
剩余內(nèi)存小于pages_min，說明進程可用的內(nèi)存都耗盡，僅內(nèi)核才可以分配內(nèi)存；
如果內(nèi)存消耗導(dǎo)致剩余內(nèi)存達到或超過了pages_min時，就會觸發(fā)直接回收（direct page reclaim）；
防止過度借用
和高區(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ī)則如下：
數(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_DMA256, #endif #ifdef CONFIG_ZONE_DMA32256, #endif #ifdef CONFIG_HIGHMEM32, #endif32, };可以通過文件“/proc/sys/vm/lowmem_reserve_ratio”修改各種區(qū)域類型的保留比例。
/proc/zoneinfo
Linux系統(tǒng)通常將主內(nèi)存劃分為三個區(qū)域。大多數(shù)內(nèi)存分配到ZONE_NORMAL區(qū)域 。 在低端，有16MB的內(nèi)存被分區(qū)到DMA區(qū)域ZONE_DMA中，該內(nèi)存被保留用于特定需要的情況。DMA內(nèi)存最常見的用戶是較舊的外設(shè)，它只能尋址24位內(nèi)存。在高端，ZONE_HIGHMEM包含內(nèi)核無法直接尋址的所有內(nèi)存。
并非所有系統(tǒng)都實現(xiàn)所有這些區(qū)域。一些較新的體系結(jié)構(gòu)不支持古老的外圍設(shè)備，而忽略了區(qū)域 ZONE_DMA。
一般來說，64位系統(tǒng)沒有尋址問題，也不需要ZONE_HIGHMEM。
IA64體系結(jié)構(gòu)決定了ZONE_DMA的另一種實現(xiàn)方式，將其定義為覆蓋4GB以下的所有內(nèi)存。
事實證明，4GB區(qū)域有很多用途。相當(dāng)多的設(shè)備在訪問不能用32位尋址的內(nèi)存時遇到問題。這些設(shè)備的驅(qū)動程序已經(jīng)被強制使用ZONE_DMA、I/O存儲器管理單元（在有ZONE_DMA的系統(tǒng)上）或緩沖區(qū)。這些解決方案都不是理想的：ZONE_DMA是一個小而稀缺的資源，IOMMU空間也可能稀缺，反彈緩沖區(qū)也很慢。如果在4GB邊界下可靠地分配DMA內(nèi)存，所有這些問題都可以避免。
在64位Linux操作系統(tǒng)上，分區(qū)如下：
最開始的16M內(nèi)存是DMA ZONE 內(nèi)存，DMA32 ZONE為16M~4G，高于4G的內(nèi)存為Normal ZONE。
內(nèi)存水位watermark
根據(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_CMAMIGRATE_CMA, /* 連續(xù)內(nèi)存分配器 */ #endif #ifdef CONFIG_MEMORY_ISOLATIONMIGRATE_ISOLATE, /* 隔離，不能從這里分配 */ #endifMIGRATE_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)整是把空閑鏈表拆分成每種遷移類型一條空閑鏈表。
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;elsepage_group_by_mobility_disabled = 0;…pageblock_order是按可移動性分組的階數(shù)，簡稱分組階數(shù)，可以理解為一種遷移類型的一個頁塊的最小長度。如果內(nèi)核支持巨型頁，那么pageblock_order是巨型頁的階數(shù)，否則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 3static 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)先級列表：
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)生碎片。
釋放物理頁的時候，需要把物理頁插入物理頁所屬遷移類型的空閑鏈表，內(nèi)核怎么知道物理頁的遷移類型？
內(nèi)存區(qū)域的zone結(jié)構(gòu)體的成員pageblock_flags指向頁塊標(biāo)志位圖，頁塊的大小是分組階數(shù)pageblock_order (MAX_ORDER-1)，我們把這種頁塊稱為分組頁塊。
每個分組頁塊在位圖中占用4位，其中3位用來存放頁塊的遷移類型。
include/linux/pageblock-flags.h
/* 影響一個頁塊的位索引 */ enum pageblock_bits {PB_migrate, // 0 ~ 2PB_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()
可以通過文件“/proc/pagetypeinfo”查看各種遷移類型的頁的分布情況。
每處理器頁集合（分配單頁優(yōu)化）
內(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ù)量達到高水線，需要返還給伙伴分配器 */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ù)量大于或等于高水線，那么批量返還給伙伴分配器。
分配標(biāo)志位
分配頁的函數(shù)都帶一個分配標(biāo)志位參數(shù)，分配標(biāo)志位分為以下5類（標(biāo)志位名稱中的GFP是Get Free Pages的縮寫）。
（1）區(qū)域修飾符：指定從哪個區(qū)域類型分配頁，“ 根據(jù)可移動性分組” 已經(jīng)描述了根據(jù)分配標(biāo)志得到首選區(qū)域類型的方法。
（2）頁移動性和位置提示：指定頁的遷移類型和從哪些內(nèi)存節(jié)點分配頁。
（3）高優(yōu)先級修飾符。
（4）回收修飾符。
（5）行動修飾符。
__GFP_COLD：調(diào)用者不期望分配的頁很快被使用，盡可能分配緩存冷頁（數(shù)據(jù)不在處理器的緩存中）。
__GFP_NOWARN：如果分配失敗，不要打印警告信息。
__GFP_COMP：把分配的頁塊組成復(fù)合頁（compound page）。
__GFP_ZERO：把頁用零初始化。
因為這些標(biāo)志位總是組合使用，所以內(nèi)核定義了一些標(biāo)志位組合。常用的標(biāo)志位組合如下。
（1）GFP_ATOMIC：原子分配，分配內(nèi)核使用的頁，不能睡眠。調(diào)用者是高優(yōu)先級的，允許異步回收頁。
（2）GFP_KERNEL：分配內(nèi)核使用的頁，可能睡眠。從低端內(nèi)存區(qū)域分配頁，允許異步回收頁和直接回收頁，允許讀寫存儲設(shè)備，允許調(diào)用到底層文件系統(tǒng)。
（3）GFP_NOWAIT：分配內(nèi)核使用的頁，不能等待。允許異步回收頁，不允許直接回收頁，不允許讀寫存儲設(shè)備，不允許調(diào)用到底層文件系統(tǒng)。
（4）GFP_NOIO：不允許讀寫存儲設(shè)備，允許異步回收頁和直接回收頁。
請盡量避免直接使用這個標(biāo)志位，應(yīng)該使用函數(shù)memalloc_noio_save和memalloc_noio_restore標(biāo)記一個不能讀寫存儲設(shè)備的范圍，前者設(shè)置進程標(biāo)志位PF_MEMALLOC_NOIO，后者清除進程標(biāo)志位PF_MEMALLOC_NOIO。
（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è)置進程標(biāo)志位PF_MEMALLOC_NOFS，后者清除進程標(biāo)志位PF_MEMALLOC_NOFS。
（6）GFP_USER：分配用戶空間使用的頁，內(nèi)核或硬件也可以直接訪問，從普通區(qū)域分配，允許異步回收頁和直接回收頁，允許讀寫存儲設(shè)備，允許調(diào)用到文件系統(tǒng)，允許實施cpuset內(nèi)存分配策略。
（7）GFP_HIGHUSER：分配用戶空間使用的頁，內(nèi)核不需要直接訪問，從高端內(nèi)存區(qū)域分配，物理頁在使用的過程中不可以移動。
（9）GFP_TRANSHUGE_LIGHT：分配用戶空間使用的巨型頁，把分配的頁塊組成復(fù)合頁，禁止使用緊急保留內(nèi)存，禁止打印警告信息，不允許異步回收頁和直接回收頁。
（10）GFP_TRANSHUGE：分配用戶空間使用的巨型頁，和GFP_TRANSHUGE_LIGHT的區(qū)別是允許直接回收頁。
復(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所示。
（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（針對尾頁）。
include/linux/mm_types.h
結(jié)構(gòu)體page中復(fù)合頁的成員如下：
struct 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_64BITunsigned int compound_dtor; /* 復(fù)合頁釋放函數(shù)數(shù)組的索引 */unsigned int compound_order; /* 復(fù)合頁的階數(shù) */ #elseunsigned short int compound_dtor;unsigned short int compound_order;#endif};};… }；對高階原子分配的優(yōu)化處理（MIGRATE_HIGHATOMIC）
高階原子分配：階數(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.h
struct 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.c
static 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; }如果直接回收頁沒有進展超過16次，那么針對目標(biāo)區(qū)域，不再為高階原子分配保留頁，把高階原子類型的頁塊轉(zhuǎn)換成申請的遷移類型，其代碼如下
mm/page_alloc.c
static inline bool should_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);}… }分配頁
分配接口
頁分配器提供了以下分配頁的接口。
（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情況下的簡化形式，只分配一頁，并且用零初始化。
核心函數(shù)的實現(xiàn)__alloc_pages_nodemask
在Linux內(nèi)核中，所有分配頁的函數(shù)最終都會調(diào)用到__alloc_pages_nodemask，此函數(shù)被稱為分區(qū)的伙伴分配器的心臟。
struct page *__alloc_pages_nodemask(gfp_t gfp_mask, unsigned int order, struct zonelist *zonelist, nodemask_t *nodemask)（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
/* The ALLOC_WMARK bits are used as an index to zone->watermark */ #define ALLOC_WMARK_MIN WMARK_MIN // 使用最低水線 #define ALLOC_WMARK_LOW WMARK_LOW // 低水線 #define ALLOC_WMARK_HIGH WMARK_HIGH // 高水線 #define ALLOC_NO_WATERMARKS 0x04 // 完全不檢查水線/* Mask to get the watermark bits */ #define ALLOC_WMARK_MASK (ALLOC_NO_WATERMARKS-1) // 得到水線位的掩碼#define ALLOC_HARDER 0x10 // 試圖更努力分配 #define ALLOC_HIGH 0x20 // 調(diào)用者是高優(yōu)先級 #define ALLOC_CPUSET 0x40 // 檢查cpuset是否允許進程從某個內(nèi)存節(jié)點分配頁 #define ALLOC_CMA 0x80 // 允許從CMA（連續(xù)內(nèi)存分配器）遷移類型分配快速分配 get_page_from_freelist
/** 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 = ac->preferred_zoneref;struct zone *zone;struct pglist_data *last_pgdat_dirty_limit = NULL;/*掃描備用區(qū)域列表中每個滿足條件的區(qū)域:區(qū)域類型小于或等待首選區(qū)域類型，并且內(nèi)存節(jié)點在節(jié)點掩碼中的相應(yīng)位被設(shè)置處理。*/for_next_zone_zonelist_nodemask(zone, z, ac->zonelist, ac->high_zoneidx,ac->nodemask) {struct page *page;unsigned long mark;/*如果編譯了cpuset功能，調(diào)用者設(shè)置ALLOC_CPUSET要求使用cpuset檢查，并且cpuset不允許當(dāng)前進程從這個內(nèi)存節(jié)點分配，那么不能從這個區(qū)域分配頁*/if (cpusets_enabled() &&(alloc_flags & ALLOC_CPUSET) &&!__cpuset_zone_allowed(zone, gfp_mask))continue;/*如果調(diào)用者設(shè)置標(biāo)志位_GFP_MRITE，表示文件系統(tǒng)申請分配一個頁頁緩存頁用來寫文件，那么檢查內(nèi)存節(jié)點的臟頁數(shù)量是否超過限制。如果超過就不能從這個區(qū)域分配頁*/if (ac->spread_dirty_pages) {if (last_pgdat_dirty_limit == zone->zone_pgdat)continue;if (!node_dirty_ok(zone->zone_pgdat)) {last_pgdat_dirty_limit = zone->zone_pgdat;continue;}}/* 檢查水線，如果（區(qū)域的空閑頁數(shù) - 申請的頁數(shù)）小于水線 */mark = zone->watermark[alloc_flags & ALLOC_WMARK_MASK];if (!zone_watermark_fast(zone, order, mark,ac_classzone_idx(ac), alloc_flags)) {int ret;/* Checked here to keep the fast path fast */BUILD_BUG_ON(ALLOC_NO_WATERMARKS < NR_WMARK);if (alloc_flags & ALLOC_NO_WATERMARKS)goto try_this_zone;/* 如果沒有開啟節(jié)點回收功能，或者當(dāng)前節(jié)點和首選節(jié)點之間的距離大于回收距離，不能從這個區(qū)域分配頁 */if (node_reclaim_mode == 0 ||!zone_allows_reclaim(ac->preferred_zoneref->zone, zone))continue;/* 從節(jié)點回收沒有映射到里進程虛擬地址空間的文件頁的塊分配器申請的頁，然后重新檢查水線， */ret = node_reclaim(zone->zone_pgdat, gfp_mask, order);switch (ret) {case NODE_RECLAIM_NOSCAN:/* did not scan */continue;case NODE_RECLAIM_FULL:/* scanned but unreclaimable */continue;default:/* did we reclaim enough */if (zone_watermark_ok(zone, order, mark,ac_classzone_idx(ac), alloc_flags))goto try_this_zone;continue;}}try_this_zone:/* 直接從當(dāng)前區(qū)域分配頁，調(diào)用rmqueue來分配 */page = rmqueue(ac->preferred_zoneref->zone, zone, order,gfp_mask, alloc_flags, ac->migratetype);// 如果分配成功，調(diào)用函數(shù)prep_new_page以初始化頁。如果是高階原子分配，并且區(qū)域中高階原子類型的頁數(shù)沒有超過限制，那么把分配的頁所屬的頁塊轉(zhuǎn)換為高階原子類型。if (page) {prep_new_page(page, order, gfp_mask, alloc_flags);/** If this is a high-order atomic allocation then check* if the pageblock should be reserved for the future*/if (unlikely(order && (alloc_flags & ALLOC_HARDER)))reserve_highatomic_pageblock(page, zone, order);return page;}}return NULL; }慢速分配 __alloc_pages_slowpath
如果低水線分配失敗，則執(zhí)行慢速路徑，慢速路徑是在函數(shù)__alloc_pages_slowpath中實現(xiàn)的，執(zhí)行流程如下圖
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)存耗盡殺手選擇一個進程殺死，然后嘗試分配。
頁分配器認(rèn)為階數(shù)大于3是昂貴的分配，有些地方做了特殊處理。
static 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;}/** We also sanity check to catch abuse of atomic reserves being used by* callers that are not in atomic context.*/if (WARN_ON_ONCE((gfp_mask & (__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)) ==(__GFP_ATOMIC|__GFP_DIRECT_RECLAIM)))gfp_mask &= ~__GFP_ATOMIC;retry_cpuset:compaction_retries = 0;no_progress_loops = 0;compact_priority = DEF_COMPACT_PRIORITY;/* 后面可能檢查cpuset是否允許當(dāng)前進程從哪些內(nèi)存節(jié)點申請頁，需要讀當(dāng)前進程的成員mems_allowed，使用順序鎖保護 */cpuset_mems_cookie = read_mems_allowed_begin();/** The fast path uses conservative alloc_flags to succeed only until* kswapd needs to be woken up, and to avoid the cost of setting up* alloc_flags precisely. So we do that now.*/// 把分配標(biāo)志位轉(zhuǎn)換成內(nèi)部分配標(biāo)志位alloc_flags = gfp_to_alloc_flags(gfp_mask);/** We need to recalculate the starting point for the zonelist iterator* because we might have used different nodemask in the fast path, or* there was a cpuset modification and we are retrying - otherwise we* could end up iterating over non-eligible zones endlessly.*/// 獲取首選的內(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);/** The adjusted alloc_flags might result in immediate success, so try* that first*/// 使用最低水線分配頁page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);if (page)goto got_pg;/** For costly allocations, try direct compaction first, as it's likely* that we have enough base pages and don't need to reclaim. For non-* movable high-order allocations, do that as well, as compaction will* try prevent permanent fragmentation by migrating from blocks of the* same migratetype.* Don't try this for allocations that are allowed to ignore* watermarks, as the ALLOC_NO_WATERMARKS attempt didn't yet happen.*/// 針對申請的階數(shù)大于0，滿足3個條件 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;/** Checks for costly allocations with __GFP_NORETRY, which* includes THP page fault allocations*/if (costly_order && (gfp_mask & __GFP_NORETRY)) {/** If compaction is deferred for high-order allocations,* it is because sync compaction recently failed. If* this is the case and the caller requested a THP* allocation, we do not want to heavily disrupt the* system, so we fail the allocation instead of entering* direct reclaim.*/if (compact_result == COMPACT_DEFERRED)goto nopage;/** Looks like reclaim/compaction is worth trying, but* sync compaction could be very expensive, so keep* using async compaction.*/compact_priority = INIT_COMPACT_PRIORITY;}}retry:/* Ensure kswapd doesn't accidentally go to sleep as long as we loop */// 確保頁回收線程在我們循環(huán)的時候不會意外地睡眠if (gfp_mask & __GFP_KSWAPD_RECLAIM)wake_all_kswapds(order, ac);if (gfp_pfmemalloc_allowed(gfp_mask))alloc_flags = ALLOC_NO_WATERMARKS;/** Reset the zonelist iterators if memory policies can be ignored.* These allocations are high priority and system rather than user* orientated.*/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);}/* Attempt with potentially adjusted zonelist and alloc_flags */// 使用可能調(diào)整過的區(qū)域列表和分配標(biāo)志page = get_page_from_freelist(gfp_mask, order, alloc_flags, ac);if (page)goto got_pg;/* Caller is not willing to reclaim, we can't balance anything */if (!can_direct_reclaim)goto nopage;/* Make sure we know about allocations which stall for too long */if (time_after(jiffies, alloc_start + stall_timeout)) {warn_alloc(gfp_mask & ~__GFP_NOWARN, ac->nodemask,"page allocation stalls for %ums, order:%u",jiffies_to_msecs(jiffies-alloc_start), order);stall_timeout += 10 * HZ;}/* Avoid recursion of direct reclaim */if (current->flags & PF_MEMALLOC)goto nopage;/* Try direct reclaim and then allocating */// 直接回收頁page = __alloc_pages_direct_reclaim(gfp_mask, order, alloc_flags, ac,&did_some_progress);if (page)goto got_pg;/* Try direct compaction and then allocating */// 針對申請階數(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;/* Do not loop if specifically requested */// 如果調(diào)用者不要求重試，則放棄if (gfp_mask & __GFP_NORETRY)goto nopage;/** Do not retry costly high order allocations unless they are* __GFP_REPEAT*/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;/** It doesn't make any sense to retry for the compaction if the order-0* reclaim is not able to make any progress because the current* implementation of the compaction depends on the sufficient amount* of free memory (see __compaction_suitable)*/// 申請階數(shù)大于0: 判斷是否應(yīng)該重試內(nèi)存碎片整理if (did_some_progress > 0 &&should_compact_retry(ac, order, alloc_flags,compact_result, &compact_priority,&compaction_retries))goto retry;/** It's possible we raced with cpuset update so the OOM would be* premature (see below the nopage: label for full explanation).*/// 如果cpuset修改允許當(dāng)前進程從那些內(nèi)存節(jié)點申請頁if (read_mems_allowed_retry(cpuset_mems_cookie))goto retry_cpuset;/* Reclaim has failed us, start killing things */// 使用內(nèi)存耗盡殺手選擇一個進程殺死page = __alloc_pages_may_oom(gfp_mask, order, ac, &did_some_progress);if (page)goto got_pg;/* Avoid allocations with no watermarks from looping endlessly */// 如果當(dāng)前進程正在被內(nèi)存耗盡殺手殺死，并且忽略水線或者不允緊急保留內(nèi)存if (test_thread_flag(TIF_MEMDIE) &&(alloc_flags == ALLOC_NO_WATERMARKS ||(gfp_mask & __GFP_NOMEMALLOC)))goto nopage;/* Retry as long as the OOM killer is making progress */// 如果內(nèi)存耗盡殺手取得進展，則重試if (did_some_progress) {no_progress_loops = 0;goto retry;}nopage:/** When updating a task's mems_allowed or mempolicy nodemask, it is* possible to race with parallel threads in such a way that our* allocation can fail while the mask is being updated. If we are about* to fail, check if the cpuset changed during allocation and if so,* retry.*/if (read_mems_allowed_retry(cpuset_mems_cookie))goto retry_cpuset;/** Make sure that __GFP_NOFAIL request doesn't leak out and make sure* we always retry*/if (gfp_mask & __GFP_NOFAIL) {/** All existing users of the __GFP_NOFAIL are blockable, so warn* of any new users that actually require GFP_NOWAIT*/if (WARN_ON_ONCE(!can_direct_reclaim))goto fail;/** PF_MEMALLOC request from this context is rather bizarre* because we cannot reclaim anything and only can loop waiting* for somebody to do a work for us*/WARN_ON_ONCE(current->flags & PF_MEMALLOC);/** non failing costly orders are a hard requirement which we* are not prepared for much so let's warn about these users* so that we can identify them and convert them to something* else.*/WARN_ON_ONCE(order > PAGE_ALLOC_COSTLY_ORDER);/** Help non-failing allocations by giving them access to memory* reserves but do not use ALLOC_NO_WATERMARKS because this* could deplete whole memory reserves which would just make* the situation worse*/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; }釋放頁
在CPU 訪問內(nèi)存時，因于這個操作比較慢，為了加快速度，
根據(jù)本地性原則，CPU在訪問主內(nèi)存時的時候會把附近的一塊數(shù)據(jù)都加載到CPU 的Cache 里，之后讀這與這塊數(shù)據(jù)都是在Cache 里做。
Linux 本來有伙伴系統(tǒng)分配內(nèi)存頁，為了加快單個內(nèi)存頁的分配，
Linux 在每個 inode 里 為每個CPU 分配了一個per_cpu_pageset （暫且叫頁緩存吧）。
每個 頁緩存包含一個冷頁緩存 和 一個熱頁緩存。
這主要是因為 內(nèi)核 用free_page 釋放單個內(nèi)存頁的時候會調(diào)用 free_hot_page。
剛釋放的內(nèi)存頁大概率還在CPU 的Cache 里，也就是說熱頁緩存里的頁很可能還在CPU 的 Cache里，
所以申請熱頁緩存并且立即使用會直接訪問 CPU 的Cache 速度會比較快。
頁分配器提供釋放頁的接口：
（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的代碼如下：
void __free_pages(struct page *page, unsigned int order) {// 引用計數(shù)減一，為0 執(zhí)行操作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以釋放頁。
free_hot_cold_page
函數(shù)free_hot_cold_page把一頁添加到每處理器頁集合中，如果頁集合中的頁數(shù)量大于或等于高水線，那么批量返還給伙伴分配器。第二個參數(shù)cold表示緩存冷熱程度，主動釋放的頁作為緩存熱頁，回收的頁作為緩存冷頁，因為回收的是最近最少使用的頁。
mm/page_alloc.c void 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); }__free_pages_ok
函數(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)前頁塊添加到空閑鏈表的尾部。
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++; }總結(jié)
以上是生活随笔為你收集整理的伙伴分配器的内核实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java搜索引擎mysql_用Java
- 下一篇： 计算机网络技术双机互联,快速实现双机互联