背景

• Read the fucking source code! --By 魯迅
• A picture is worth a thousand words. --By 高爾基

說明：

1. Kernel版本：4.14
2. ARM64處理器，Contex-A53，雙核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

本文將分析Buddy System，
Buddy System伙伴系統，是通過將物理記憶體劃分為頁面來進行管理的系統，支持連續的物理頁面分配和釋放，此外，使用與碎片相關的演算法來確保最大的連續頁面，

先通過一個例子大體介紹一下原理吧：
空閑的物理頁框按大小分組成0~MAX_ORDER個鏈表，每個鏈表存放頁框的大小為2的n次冪，其中n在0 ~ MAX_ORDER-1中取值，

假設請求分配2^8 = 256個頁框塊：

1. 檢查n = 8的鏈表，檢查是否有空閑塊，找到了則直接回傳；
2. 沒有找到滿足需求的，則查找n = 9的鏈表，找到512大小空閑塊，拆分成兩個256大小塊，將其中一個256大小塊回傳，另一個256大小塊添加到n = 8的鏈表中；
3. 在n = 9的鏈表中沒有找到合適的塊，則查找n = 10的鏈表，找到1024大小空閑塊，將其拆分成512 + 256 + 256大小的塊，回傳需要獲取的256大小的塊，將剩下的512大小塊插入n = 9鏈表中，剩下的256大小塊插入n = 8的鏈表中；

合并程序是上述流程的逆程序，試圖將大小相等的Buddy塊進行合并成單獨的塊，并且會迭代合并下去，嘗試合并成更大的塊，合并需要滿足要求：

1. 兩個Buddy塊大小一致；
2. 它們的物理地址連續；
3. 第一個Buddy塊的起始地址為 (2 x N x 4K)的整數倍，其中4K為頁面大小，N為Buddy塊的大小；

struct page結構中，與Buddy System相關的欄位有：

• _mapcount： 用于標記page是否處在Buddy System中，設定成-1或PAGE_BUDDY_MAPCOUNT_VALUE(-128)；
• private： 一個2^k次冪的空閑塊的第一個頁描述符中，private欄位存放了塊的order值，也就是k值；
• index： 存放MIGRATE型別；
• _refcount： 用戶使用計數值，沒有用戶使用為0，有使用的話則增加；

合并時如下圖所示：

2. Buddy頁面分配

Buddy頁面分配的流程如下圖所示：

從上圖中可以看出，在頁面進行分配的時候，有以下四個步驟：

1. 如果申請的是order = 0的頁面，直接選擇從pcp中進行分配，并直接退出；
2. order > 0時，如果分配標志中設定了ALLOC_HARDER，則從free_list[MIGRATE_HIGHATOMIC]的鏈表中進行頁面分配，分配成功則回傳；
3. 前兩個條件都不滿足，則在正常的free_list[MIGRATE_*]中進行分配，分配成功則直接則回傳；
4. 如果3中分配失敗了，則查找后備型別fallbacks[MIGRATE_TYPES][4]，并將查找到的頁面移動到所需的MIGRATE型別中，移動成功后，重新嘗試分配；

如下圖：

上述分配的程序，前3個步驟都會呼叫到__rmqueue_smallest，第4步呼叫__rmqueue_fallback，將從這兩個函式來分析，

2.1 __rmqueue_smallest

__rmqueue_smallest的源代碼比較簡單，貼上來看看吧：

static inline
struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
						int migratetype)
{
	unsigned int current_order;
	struct free_area *area;
	struct page *page;

	/* Find a page of the appropriate size in the preferred list */
	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;
}

從代碼中可以看出：

1. 從申請的order大小開始查找目標MIGRATE型別鏈表中頁表，如果沒有找到，則從更大的order中查找，直到MAX_ORDER；
2. 查找到頁表之后，從對應的鏈表中洗掉掉，并呼叫expand函式進行處理；

expand函式的處理邏輯就跟本文概述中講的例子一樣，當在大的order鏈表中申請到了記憶體后，剩余部分會插入到其他的order鏈表中，來一張圖就清晰了：

2.2 __rmqueue_fallback

當上述程序沒有分配到記憶體時，便會開始從后備遷移型別中進行分配，
其中，定義了一個全域的二維fallbacks的陣列，并根據該陣列進行查找，代碼如下：

/*
 * This array describes the order lists are fallen back to when
 * the free lists for the desirable migrate type are depleted
 */
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 }, /* Never used */
#endif
#ifdef CONFIG_MEMORY_ISOLATION
	[MIGRATE_ISOLATE]     = { MIGRATE_TYPES }, /* Never used */
#endif
};

__rmqueue_fallback完成的主要作業就是從后備fallbacks中找到一個遷移型別頁面塊，將其移動到目標型別中，并重新進行分配，
下圖將示例整個流程：

3. Buddy頁面釋放

頁面釋放是申請的逆程序，相對來說要簡單不少，先看一下函式呼叫圖吧：

當order = 0時，會使用Per-CPU Page Frame來釋放，其中：

• MIGRATE_UNMOVABLE, MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE三個按原來的型別釋放；
• MIGRATE_CMA, MIGRATE_HIGHATOMIC型別釋放到MIGRATE_UNMOVABLE型別中；
• MIGRATE_ISOLATE型別釋放到Buddy系統中；
  此外，在PCP釋放的程序中，發生溢位時，會呼叫free_pcppages_bulk()來回傳給Buddy系統，來一張圖就清晰了：
  

在整個釋放程序中，核心函式為__free_one_page，該函式的核心邏輯部分如下所示：

continue_merging:
	while (order < max_order - 1) {
		buddy_pfn = __find_buddy_pfn(pfn, order);
		buddy = page + (buddy_pfn - pfn);

		if (!pfn_valid_within(buddy_pfn))
			goto done_merging;
		if (!page_is_buddy(page, buddy, order))
			goto done_merging;
		/*
		 * Our buddy is free or it is CONFIG_DEBUG_PAGEALLOC guard page,
		 * merge with it and move up one order.
		 */
		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++;
	}

• __find_buddy_pfn： 根據釋放頁面的pfn計算對應的buddy_pfn，比如pfn = 0x1000, order = 3，則buddy_pfn = 0x1008，pfn = 0x1008, order = 3，則buddy_pfn = 0x1000；
• page_is_buddy：將page和buddy進行配對處理，判斷是否能配對；
• 進行combine之后，再將pfn指向合并后的開始位置，繼續往上一階進行合并處理；

按照慣例，再來張圖片吧：

不得不說，還有很多細節沒有去扣，一旦沉淪，將難以自拔，待續吧，

標籤：Linux

上一篇：Linux在丟失的情況下重置密碼

下一篇：分布式快取和預取相關的有趣的鏈接