Linux內(nèi)存頁分配策略
伙伴系統(tǒng)分配算法
但有時(shí)候內(nèi)核需要分配一些物理內(nèi)存地址也連續(xù)的內(nèi)存頁, 所以Linux使用了 伙伴系統(tǒng)分配算法 來管理系統(tǒng)中的物理內(nèi)存頁.
上一節(jié)說過, 內(nèi)核使用 alloc_pages() 函數(shù)來分配內(nèi)存頁, 而 alloc_pages() 函數(shù)最后會(huì)調(diào)用 rmqueue() 函數(shù)來分配內(nèi)存頁, rmqueue() 函數(shù)原型如下:
static struct page * rmqueue(zone_t *zone, unsigned long order);參數(shù) zone 是內(nèi)存管理區(qū), 而 order 是要分配 2order 個(gè)內(nèi)存頁. 由于 rmqueue() 函數(shù)使用了伙伴系統(tǒng)算法, 所以下面先來介紹一下伙伴系統(tǒng)算法的原理.
伙伴系統(tǒng)算法的核心是 伙伴, 那什么是伙伴呢? 在Linux內(nèi)核中, 把兩個(gè)物理地址相鄰的內(nèi)存頁當(dāng)作成伙伴, 因?yàn)長inux是以頁面號(hào)來管理內(nèi)存頁的, 所以就是說兩個(gè)相鄰頁面號(hào)的頁面是伙伴關(guān)系. 但是并不是所有相鄰頁面號(hào)的頁面都是伙伴關(guān)系, 例如0號(hào)和1號(hào)頁面是伙伴關(guān)系, 但是1號(hào)和2號(hào)就不是了. 為什么呢? 這是因?yàn)槿绻?號(hào)頁面和2號(hào)頁面當(dāng)成伙伴關(guān)系, 那么0號(hào)頁面就沒有伙伴從而變成孤島了.
那么給定一個(gè) i 號(hào)內(nèi)存頁, 怎么找到他的伙伴內(nèi)存頁呢? 通過觀察我們可以發(fā)現(xiàn), 如果頁面號(hào)是復(fù)數(shù)的, 那么他的伙伴內(nèi)存頁要加1, 如果頁面號(hào)是單數(shù)的, 那么他的伙伴內(nèi)存頁要減1. 所以對(duì)于給定一個(gè)頁面號(hào)為 i 的內(nèi)存頁, 他的伙伴內(nèi)存頁號(hào)可以使用以下的代碼獲得:
if (i & 1) {
? ?buddy = i - 1
} else {
? ?buddy = i + 1
}那么知道一個(gè)內(nèi)存頁的伙伴頁面有什么用呢? 答案是為了合并為更大的內(nèi)存頁, 例如把兩個(gè)單位為1的伙伴內(nèi)存頁合并成為一個(gè)單位為2的內(nèi)存頁(這時(shí)應(yīng)該稱為內(nèi)存塊), 把兩個(gè)單位為2的伙伴內(nèi)存塊合并為單位為4的內(nèi)存塊, 以此類推.
所以, 使用伙伴系統(tǒng)算法只能分配 2order (order為0,1,2,3...)個(gè)頁面. 那么order是不是無限大呢? 當(dāng)然不是, 在Linux內(nèi)核中, order的最大值是 10. 也就是說在內(nèi)核中, 最大能夠申請(qǐng)到一個(gè) 29 個(gè)頁面的內(nèi)存塊.
上一節(jié)我們介紹過內(nèi)存管理區(qū)數(shù)據(jù)結(jié)構(gòu) struct zone_struct, 在內(nèi)存管理區(qū)數(shù)據(jù)結(jié)構(gòu)中有個(gè)名為 free_area 類型為 free_area_t 的字段, 他的作用就是用來管理內(nèi)存管理區(qū)內(nèi)的空閑物理內(nèi)存頁. 定義如下:
#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 字段用于連接有相同頁面?zhèn)€數(shù)的內(nèi)存塊. map 字段是一個(gè)位圖, 用于記錄伙伴內(nèi)存塊的使用情況.
Linux內(nèi)核使用 free_area[i] 管理 2i 個(gè)內(nèi)存頁面大小的內(nèi)存塊列表. 例如 free_area[0] 就是管理1個(gè)內(nèi)存頁面大小的內(nèi)存塊(20等于1), 而 free_area[1] 則管理2個(gè)內(nèi)存頁面大小的內(nèi)存塊(21等于2). 如下圖所示:
我們說過, 在管理物理內(nèi)存頁的 struct page 結(jié)構(gòu)中有個(gè) list 的字段, 內(nèi)核就是通過這個(gè)字段把有著相同個(gè)數(shù)頁面的內(nèi)存塊連成一個(gè)鏈表的:
typedef struct page {
struct list_head list;
...
} mem_map_t;前面我們說過, 在 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. 如下圖:
使用位圖來標(biāo)識(shí)伙伴內(nèi)存塊使用情況的原因是: 當(dāng)釋放內(nèi)存塊時(shí), 如果對(duì)應(yīng)的位是1的話, 那么說明另外一個(gè)伙伴內(nèi)存塊是空閑狀態(tài)的, 所以釋放當(dāng)前內(nèi)存塊可以跟其伙伴內(nèi)存塊合并成一個(gè)更大的內(nèi)存塊了.
【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【891587639】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??
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)存塊的大小來計(jì)算需要多少個(gè)位來記錄伙伴內(nèi)存塊的關(guān)系, 并保存到 map 字段中.
說明一下, 這里計(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)存頁數(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ù)來把內(nèi)存塊分裂成指定大小的內(nèi)存塊.
大內(nèi)存塊分裂為小內(nèi)存塊的過程也很簡單, 舉個(gè)例子: 如果我們要申請(qǐng)order為2的內(nèi)存塊(也就是大小為4個(gè)內(nèi)存頁的內(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); // 把分裂出來的一塊內(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ì)照上面的思路來分析 expand() 函數(shù).
我們接著來分析內(nèi)存塊的釋放, 內(nèi)存塊的釋放是通過 free_pages() 函數(shù)來實(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的長整型數(shù)字
? ?base = mem_map + zone->offset; // 獲取內(nèi)存管理區(qū)管理的開始內(nèi)存頁
? ?page_idx = page - base; ? ? ? ?// 當(dāng)前頁面在內(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)存頁數(shù)
? ?while (mask + (1 << (MAX_ORDER-1))) { // 遍歷(MAX_ORDER-order-1, MAX_ORDER等于10)次, 也就是說最多循環(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--;
}釋放過程和分配過程是一對(duì)互逆的過程, 釋放內(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)停止合并過程, 根據(jù)上面代碼的注釋可以慢慢理解.
