背景 By 魯迅 By 高爾基 說明： 1. Kernel版本：4.14 2. ARM64處理器，Contex A53，雙核 3. 使用工具：Source Insight 3.5， Visio 1. 概述 本文將分析 。 伙伴系統，是通過將物理記憶體劃分為頁面來進行管理的系統，支持連續的物理頁面分配和 ...
背景
Read the fucking source code!--By 魯迅A picture is worth a thousand words.--By 高爾基
說明：
- Kernel版本：4.14
- ARM64處理器，Contex-A53，雙核
- 使用工具：Source Insight 3.5， Visio
1. 概述
本文將分析Buddy System。
Buddy System伙伴系統，是通過將物理記憶體劃分為頁面來進行管理的系統，支持連續的物理頁面分配和釋放。此外，使用與碎片相關的演算法來確保最大的連續頁面。
先通過一個例子大體介紹一下原理吧：
空閑的物理頁框按大小分組成0~MAX_ORDER個鏈表，每個鏈表存放頁框的大小為2的n次冪，其中n在0 ~ MAX_ORDER-1中取值。
假設請求分配2^8 = 256個頁框塊：
- 檢查
n = 8的鏈表，檢查是否有空閑塊，找到了則直接返回； - 沒有找到滿足需求的，則查找
n = 9的鏈表，找到512大小空閑塊，拆分成兩個256大小塊，將其中一個256大小塊返回，另一個256大小塊添加到n = 8的鏈表中； - 在
n = 9的鏈表中沒有找到合適的塊，則查找n = 10的鏈表，找到1024大小空閑塊，將其拆分成512 + 256 + 256大小的塊，返回需要獲取的256大小的塊，將剩下的512大小塊插入n = 9鏈表中，剩下的256大小塊插入n = 8的鏈表中；
合併過程是上述流程的逆過程，試圖將大小相等的Buddy塊進行合併成單獨的塊，並且會迭代合併下去，嘗試合併成更大的塊。合併需要滿足要求：
- 兩個
Buddy塊大小一致； - 它們的物理地址連續；
- 第一個
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頁面分配的流程如下圖所示：
從上圖中可以看出，在頁面進行分配的時候，有以下四個步驟：
- 如果申請的是
order = 0的頁面，直接選擇從pcp中進行分配，並直接退出； order > 0時，如果分配標誌中設置了ALLOC_HARDER，則從free_list[MIGRATE_HIGHATOMIC]的鏈表中進行頁面分配，分配成功則返回；- 前兩個條件都不滿足，則在正常的
free_list[MIGRATE_*]中進行分配，分配成功則直接則返回； - 如果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;
}從代碼中可以看出：
- 從申請的
order大小開始查找目標MIGRATE類型鏈表中頁表，如果沒有找到，則從更大的order中查找，直到MAX_ORDER； - 查找到頁表之後，從對應的鏈表中刪除掉，並調用
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指向合併後的開始位置，繼續往上一階進行合併處理；
按照慣例，再來張圖片吧：
不得不說，還有很多細節沒有去扣，一旦沉淪，將難以自拔，待續吧。
