（七）Linux記憶體管理 - zoned page frame allocator - 2

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記憶體管理 - zoned page frame allocator - 2 - LoyenWang - 部落格園背景 By 魯迅 By 高爾基 說明： 1. Kernel版本：4.14 2. ARM64處理器，Contex A53，雙核 3. 使用工具：Source Insight 3.5， Visio 1.

https://www.cnblogs.com/LoyenWang/p/11666939.html