一文看懂 | 物理內(nèi)存分配算法（伙伴系統(tǒng)）
內(nèi)核分配物理內(nèi)存時(shí)，是以內(nèi)存頁(yè)作為分配單位的。但有時(shí)候內(nèi)核需要分配一些物理內(nèi)存地址連續(xù)的內(nèi)存頁(yè)，所以，Linux內(nèi)核使用了 伙伴系統(tǒng)分配算法 來(lái)管理系統(tǒng)中的物理內(nèi)存頁(yè).
什么是 伙伴系統(tǒng)分配算法？下面將會(huì)進(jìn)行詳細(xì)的介紹。
什么是伙伴系統(tǒng)分配算法
在 Linux 內(nèi)核中，要分配內(nèi)存頁(yè)可以使用 alloc_pages() 函數(shù)來(lái)完成。而 alloc_pages() 函數(shù)最后會(huì)調(diào)用 rmqueue() 函數(shù)來(lái)分配內(nèi)存頁(yè), rmqueue() 函數(shù)原型如下:
static struct page * rmqueue(zone_t *zone, unsigned long order);
參數(shù) zone 是內(nèi)存管理區(qū), 而 order 是要分配 2order 個(gè)內(nèi)存頁(yè). 由于 rmqueue() 函數(shù)使用了伙伴系統(tǒng)算法, 所以下面先來(lái)介紹一下伙伴系統(tǒng)算法的原理.
伙伴系統(tǒng)算法 的核心是 伙伴，那什么是伙伴呢？在 Linux 內(nèi)核中，把兩個(gè)物理地址相鄰的內(nèi)存頁(yè)當(dāng)作成伙伴。
因?yàn)椋琇inux 是以頁(yè)面號(hào)來(lái)管理內(nèi)存頁(yè)的。所以，就是說(shuō)兩個(gè)相鄰頁(yè)面號(hào)的頁(yè)面是伙伴關(guān)系。但是并不是所有相鄰頁(yè)面號(hào)的頁(yè)面都是伙伴關(guān)系, 例如 0 號(hào)和 1 號(hào)頁(yè)面是伙伴關(guān)系，但是 1 號(hào)和 2 號(hào)就不是了。為什么呢? 這是因?yàn)槿绻?1 號(hào)頁(yè)面和 2 號(hào)頁(yè)面當(dāng)成伙伴關(guān)系，那么 0 號(hào)頁(yè)面就沒有伙伴從而變成孤島了。
那么給定一個(gè) i 號(hào)內(nèi)存頁(yè)，怎么找到他的伙伴內(nèi)存頁(yè)呢？通過(guò)觀察我們可以發(fā)現(xiàn)，如果頁(yè)面號(hào)是復(fù)數(shù)的，那么他的伙伴內(nèi)存頁(yè)要加 1。
如果頁(yè)面號(hào)是單數(shù)的，那么他的伙伴內(nèi)存頁(yè)要減 1。所以，對(duì)于給定一個(gè)頁(yè)面號(hào)為 i 的內(nèi)存頁(yè)，他的伙伴內(nèi)存頁(yè)號(hào)可以使用以下的代碼獲得：
if (i & 1) {
buddy = i - 1
} else {
buddy = i + 1
}
那么知道一個(gè)內(nèi)存頁(yè)的伙伴頁(yè)面有什么用呢？答案是為了合并為更大的內(nèi)存頁(yè)，例如把兩個(gè)單位為1的伙伴內(nèi)存頁(yè)合并成為一個(gè)單位為2的內(nèi)存頁(yè)(這時(shí)應(yīng)該稱為內(nèi)存塊)，把兩個(gè)單位為2的伙伴內(nèi)存塊合并為單位為4的內(nèi)存塊，以此類推。
所以，使用伙伴系統(tǒng)算法只能分配 2order (order為0,1,2,3...)個(gè)頁(yè)面。那么order是不是無(wú)限大呢？當(dāng)然不是，在Linux內(nèi)核中，order的最大值是 10。也就是說(shuō)在內(nèi)核中，最大能夠申請(qǐng)到一個(gè) 29 個(gè)頁(yè)面的內(nèi)存塊。
Linux 內(nèi)核將物理內(nèi)存劃分為 內(nèi)存管理區(qū) 進(jìn)行管理，內(nèi)存管理區(qū)使用結(jié)構(gòu)體 zone_struct 表示。
而在內(nèi)存管理區(qū)數(shù)據(jù)結(jié)構(gòu)中有個(gè)名為 free_area 類型為 free_area_t 的字段，他的作用就是用來(lái)管理內(nèi)存管理區(qū)內(nèi)的空閑物理內(nèi)存頁(yè). 定義如下：
#define MAX_ORDER 10
typedef struct free_area_struct {
struct list_head free_list;
unsigned int *map;
} free_area_t;
typedef struct zone_struct {
...
free_area_t free_area[MAX_ORDER]; // 用于伙伴分配算法
...
} zone_t;
free_area 是伙伴系統(tǒng)算法的核心，可以看到 free_area 有10個(gè)元素。每個(gè)元素都是一個(gè)類型為 free_area_t 的結(jié)構(gòu)體，free_area_t 結(jié)構(gòu)的 free_list 字段用于連接有相同頁(yè)面?zhèn)€數(shù)的內(nèi)存塊。map 字段是一個(gè)位圖，用于記錄伙伴內(nèi)存塊的使用情況。
Linux內(nèi)核使用 free_area[i] 管理 2i 個(gè)內(nèi)存頁(yè)面大小的內(nèi)存塊列表，例如 free_area[0] 就是管理1個(gè)內(nèi)存頁(yè)面大小的內(nèi)存塊(20等于1)；而 free_area[1] 則管理2個(gè)內(nèi)存頁(yè)面大小的內(nèi)存塊(21等于2)。如下圖所示：
管理物理內(nèi)存頁(yè)的 struct page 結(jié)構(gòu)中有個(gè) list 的字段，內(nèi)核就是通過(guò)這個(gè)字段把有著相同個(gè)數(shù)頁(yè)面的內(nèi)存塊連成一個(gè)鏈表的：
typedef struct page {
struct list_head list;
...
} mem_map_t;
前面我們說(shuō)過(guò)，在 free_area_t 結(jié)構(gòu)中有個(gè)名為 map 的字段，map 字段是一個(gè)位圖，每個(gè)位記錄著一對(duì)伙伴內(nèi)存塊的使用情況。舉個(gè)例子，如果一對(duì)伙伴內(nèi)存塊中的某一個(gè)內(nèi)存塊在使用，那么對(duì)應(yīng)的位就為 1，如果兩個(gè)伙伴內(nèi)存塊都是空閑或者使用，那么對(duì)應(yīng)的位就為 0。如下圖：
使用位圖來(lái)標(biāo)識(shí)伙伴內(nèi)存塊使用情況的原因是: 當(dāng)釋放內(nèi)存塊時(shí), 如果對(duì)應(yīng)的位是1的話, 那么說(shuō)明另外一個(gè)伙伴內(nèi)存塊是空閑狀態(tài)的, 所以釋放當(dāng)前內(nèi)存塊可以跟其伙伴內(nèi)存塊合并成一個(gè)更大的內(nèi)存塊了.
伙伴系統(tǒng)分配算法實(shí)現(xiàn)
我們來(lái)看看內(nèi)核在初始化內(nèi)存管理區(qū)時(shí)怎么初始化空閑內(nèi)存塊鏈表的，代碼如下：
void __init free_area_init_core(int nid, pg_data_t *pgdat, struct page **gmap,
unsigned long *zones_size, unsigned long zone_start_paddr,
unsigned long *zholes_size, struct page *lmem_map)
{
...
for (j = 0; j < MAX_NR_ZONES; j++) {
zone_t *zone = pgdat->node_zones + j;
unsigned long mask;
unsigned long size, realsize;
...
mask = -1; // 32位系統(tǒng)這個(gè)值等于0xffffffff
for (i = 0; i < MAX_ORDER; i++) { // 初始化free_area
unsigned long bitmap_size;
memlist_init(&zone->free_area[i].free_list); // 初始化空閑鏈表
mask += mask; // 這里等于: mask = mask << 1;
size = (size + ~mask) & mask; // 用于向上對(duì)齊
bitmap_size = size >> i; // 內(nèi)存塊個(gè)數(shù)
bitmap_size = (bitmap_size + 7) >> 3; // 因?yàn)橐粋€(gè)字節(jié)有8個(gè)位, 所以要除以8
bitmap_size = LONG_ALIGN(bitmap_size);
// 申請(qǐng)位圖內(nèi)存
zone->free_area[i].map =
(unsigned int *) alloc_bootmem_node(pgdat, bitmap_size);
}
...
}
...
}
上面的代碼首先為每個(gè)管理不同大小空閑內(nèi)存塊的 free_area_t 結(jié)構(gòu)初始化其 free_list 字段，然后根據(jù)其管理內(nèi)存塊的大小來(lái)計(jì)算需要多少個(gè)位來(lái)記錄伙伴內(nèi)存塊的關(guān)系，并保存到 map 字段中。
說(shuō)明一下，這里計(jì)算位圖的大小時(shí)為每個(gè)內(nèi)存塊申請(qǐng)了一個(gè)位。但事實(shí)上每個(gè)位記錄的是一對(duì)伙伴內(nèi)存塊的關(guān)系，所以需要除以 2。而現(xiàn)在明顯浪費(fèi)了一半的內(nèi)存，在后面的 Linux 版本中改進(jìn)了這個(gè)問題。
現(xiàn)在再回頭看看物理內(nèi)存分配 rmqueue() 函數(shù)的實(shí)現(xiàn):
static struct page * rmqueue(zone_t *zone, unsigned long order)
{
free_area_t * area = zone->free_area + order; // 獲取申請(qǐng)對(duì)應(yīng)大小內(nèi)存塊的空閑列表
unsigned long curr_order = order;
struct list_head *head, *curr;
unsigned long flags;
struct page *page;
spin_lock_irqsave(&zone->lock, flags);
do {
head = &area->free_list; // 空閑內(nèi)存塊鏈表
curr = memlist_next(head);
if (curr != head) { // 如果鏈表不為空
unsigned int index;
page = memlist_entry(curr, struct page, list); // 當(dāng)前內(nèi)存塊
if (BAD_RANGE(zone,page))
BUG();
memlist_del(curr);
index = (page - mem_map) - zone->offset; // 內(nèi)存塊所在內(nèi)存管理區(qū)的索引
MARK_USED(index, curr_order, area); // 標(biāo)記伙伴標(biāo)志位為已用
zone->free_pages -= 1 << order; // 減去內(nèi)存塊所占用的內(nèi)存頁(yè)數(shù)
// 把更大的內(nèi)存塊分裂為申請(qǐng)大小的內(nèi)存塊
page = expand(zone, page, index, order, curr_order, area);
spin_unlock_irqrestore(&zone->lock, flags);
set_page_count(page, 1);
if (BAD_RANGE(zone,page))
BUG();
DEBUG_ADD_PAGE
return page;
}
// 如果在當(dāng)前空閑鏈表中沒有空閑的內(nèi)存塊, 那么向空間更大的的空閑內(nèi)存塊鏈表中申請(qǐng)
curr_order++;
area++;
} while (curr_order < MAX_ORDER);
spin_unlock_irqrestore(&zone->lock, flags);
return NULL;
}
申請(qǐng)內(nèi)存塊時(shí)，首先會(huì)在大小一致的空閑鏈表中申請(qǐng)，如果大小一致的空閑鏈表沒有空閑的內(nèi)存塊，那么只能向空間更大的空閑內(nèi)存塊鏈表中申請(qǐng)。
如果申請(qǐng)到的內(nèi)存塊比要申請(qǐng)的大小大，那么需要調(diào)用 expand() 函數(shù)來(lái)把內(nèi)存塊分裂成指定大小的內(nèi)存塊。
大內(nèi)存塊分裂為小內(nèi)存塊的過(guò)程也很簡(jiǎn)單，舉個(gè)例子：
如果我們要申請(qǐng) order 為 2 的內(nèi)存塊(也就是大小為 4 個(gè)內(nèi)存頁(yè)的內(nèi)存塊)，但是 order 為 2 的空閑鏈表沒有空閑的內(nèi)存，那么只能向 order 為 3 的空閑內(nèi)存塊鏈表中申請(qǐng)。如果 order 為 3 的空閑鏈表有空閑內(nèi)存塊，那么就從 order 為 3 的鏈表中申請(qǐng)一塊空閑內(nèi)存塊。并且把此內(nèi)存塊分裂為2塊 order 為 2 的內(nèi)存塊，一塊添加到 order 為 2 的空閑鏈表中，另外一塊分配給用戶。如果 order 為 3 的空閑鏈表也沒有空閑內(nèi)存塊，那么只能向 order 為 4 的空閑鏈表中申請(qǐng)，如此類推。
expand() 函數(shù)的源碼如下：
static inline struct page * expand (zone_t *zone, struct page *page,
unsigned long index, int low, int high, free_area_t * area)
{
unsigned long size = 1 << high;
while (high > low) {
if (BAD_RANGE(zone,page))
BUG();
area--;
high--;
size >>= 1;
memlist_add_head(&(page)->list, &(area)->free_list); // 把分裂出來(lái)的一塊內(nèi)存塊添加到下一級(jí)空閑鏈表中
MARK_USED(index, high, area); // 標(biāo)記伙伴標(biāo)志位為已用
index += size;
page += size;
}
if (BAD_RANGE(zone,page))
BUG();
return page;
}
可以對(duì)照上面的思路來(lái)分析 expand() 函數(shù)。
我們接著來(lái)分析內(nèi)存塊的釋放，內(nèi)存塊的釋放是通過(guò) free_pages() 函數(shù)來(lái)實(shí)現(xiàn)的。而 free_pages() 函數(shù)最終會(huì)調(diào)用 __free_pages_ok() 函數(shù)，__free_pages_ok() 函數(shù)代碼如下：
static void __free_pages_ok (struct page *page, unsigned long order)
{
unsigned long index, page_idx, mask, flags;
free_area_t *area;
struct page *base;
zone_t *zone;
...
zone = page->zone;
mask = (~0UL) << order; // 獲取一個(gè)后order個(gè)位為0的長(zhǎng)整型數(shù)字
base = mem_map + zone->offset; // 獲取內(nèi)存管理區(qū)管理的開始內(nèi)存頁(yè)
page_idx = page - base; // 當(dāng)前頁(yè)面在內(nèi)存管理區(qū)的索引
if (page_idx & ~mask)
BUG();
index = page_idx >> (1 + order); // 伙伴標(biāo)記位索引
area = zone->free_area + order; // 內(nèi)存塊所在的空閑鏈表
spin_lock_irqsave(&zone->lock, flags);
zone->free_pages -= mask; // 添加釋放的內(nèi)存塊所占用的內(nèi)存頁(yè)數(shù)
while (mask + (1 << (MAX_ORDER-1))) { // 遍歷(MAX_ORDER-order-1, MAX_ORDER等于10)次, 也就是說(shuō)最多循環(huán)9次
struct page *buddy1, *buddy2;
if (area >= zone->free_area + MAX_ORDER)
BUG();
if (!test_and_change_bit(index, area->map)) // 如果伙伴內(nèi)存塊在使用狀態(tài), 那么退出循環(huán)
break;
buddy1 = base + (page_idx ^ -mask); // 伙伴內(nèi)存塊(-mask 等于 1<<order)
buddy2 = base + page_idx; // 當(dāng)前內(nèi)存塊
if (BAD_RANGE(zone,buddy1))
BUG();
if (BAD_RANGE(zone,buddy2))
BUG();
memlist_del(&buddy1->list); // 把伙伴內(nèi)存塊從空閑鏈表中刪除(因?yàn)橐喜楦蟮膬?nèi)存塊, 所以要從當(dāng)前的空閑鏈表中刪除)
mask <<= 1;
area++; // 向更大的空閑鏈表進(jìn)行合并操作
index >>= 1;
page_idx &= mask;
}
memlist_add_head(&(base + page_idx)->list, &area->free_list);
spin_unlock_irqrestore(&zone->lock, flags);
if (memory_pressure > NR_CPUS)
memory_pressure--;
}
釋放過(guò)程和分配過(guò)程是一對(duì)互逆的過(guò)程，釋放內(nèi)存塊時(shí)首先看看伙伴內(nèi)存塊的狀態(tài)。如果伙伴內(nèi)存塊是空閑狀態(tài)，那么就與伙伴內(nèi)存塊合并為更大的內(nèi)存塊，并且一直嘗試合并為更大的內(nèi)存塊。
直到伙伴內(nèi)存塊不是空閑狀態(tài)或者達(dá)到內(nèi)存塊的最大限制(order為9)停止合并過(guò)程，根據(jù)上面代碼的注釋可以慢慢理解。