linux-4.4.1/__rmqueue_smallest() の履歴(No.3)

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• linux-4.4.1/__rmqueue_smallest() へ行く。
  • 1 (2017-09-25 (月) 17:53:34)
  • 2 (2017-09-25 (月) 18:08:06)
  • 3 (2017-09-26 (火) 20:27:37)

参照元†

• linux-4.4.1/__rmqueue()
• linux-4.4.1/__rmqueue_cma_fallback()
• linux-4.4.1/buffered_rmqueue()

説明†

• パス: linux-4.4.1/mm/page_alloc.c

• 与えられたマイグレーションの種類（MIGRATE_XXX）から free_list を探し、 要求されたサイズに合う最も小さい領域を返す。

• 主なデータ構造と処理の流れ
  • zone を探す（この関数に来た時点で既に決定されている、zone 引数で指定される）
    • ZONE_DMA, ZONE_NORMAL など
  • free_area を探す（確保するサイズのオーダーに応じて別れている）
    • 1ページ（オーダー 0）
    • 2ページ（オーダー 1）
    • 4ページ（オーダー 2）
    • 8ページ（オーダー 3）
    • ...
    • オーダーは MAX_ORDER - 1 が最大
  • free_list を探す（2^n ページの空き領域の先頭ページが並んだリスト）

    free_area[0] : [page 0], [page 8], [page 12]
    free_area[1] : [page 2, 3], [page 10, 11]
    free_area[2] : [page 4, 5, 6, 7]
    ...

• 構造体の定義

  struct zone {
  	...
  	struct free_area free_area[MAX_ORDER]
  
  strict free_area {
  	...
  	struct list_head free_list[MIGRATE_TYPES];

• もし見つからなければ、より大きいサイズ用の free_area を探しに行く。
  • 適切なサイズではなかった場合、余分な領域を分割する。

引数†

• struct zone *zone
  • メモリゾーン
  • linux-4.4.1/zone
• unsigned int order
  • 確保するページ数のオーダー、2 のべき乗で指定する
  • 0 なら 1 ページ、1 なら 2 ページ、n なら 2^n ページ
  • free_area の選択に使われる
• int migratetype
  • マイグレーションの種類、MIGRATE_XXX を指定する
  • free_list の選択に使われる

返り値†

• struct page *
  • 確保した領域の先頭ページ
  • linux-4.4.1/page

参考†

実装†

/*
 * Go through the free lists for the given migratetype and remove
 * the smallest available page from the freelists
 */
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;

• current_order は要求されたオーダー（order）以上、かつ空いている領域の中での最小のオーダーを表す。
  • order = 2 で、オーダー 2, 3, 4, 5 用の free_area が空いていれば、current_order = 2
  • order = 2 で、オーダー 4, 5 用の free_area が空いていれば、current_order = 4
  • linux-4.4.1/free_area
  • linux-4.4.1/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]);
		if (list_empty(&area->free_list[migratetype]))
			continue;

• リストが空なら、より大きい領域用の free_area を探す。
  • linux-4.4.1/list_empty()

		page = list_entry(area->free_list[migratetype].next,
							struct page, lru);
		list_del(&page->lru);
		rmv_page_order(page);
		area->nr_free--;

• free_list の先頭の領域を得て（list_entry）、リストから削除（list_del）する。
• free_area の空き容量が 1 減る。
  • linux-4.4.1/list_entry()
  • linux-4.4.1/list_del()
• page_order はこのページが何ページ連続した空き領域か？を表す。 空き領域ではなくなったので page_order が 0 にされるみたい。
  • linux-4.4.1/rmv_page_order()

		expand(zone, page, order, current_order, area, migratetype);
		set_pcppage_migratetype(page, migratetype);
		return page;

• free_list から取得した領域は大きすぎる可能性があるため、 余分な領域を分割して、小さい領域用の free_area に追加する。
  • 例えば、要求されたサイズが 2（order = 2, 4 pages）なのに、 free_list から取得した領域が 5（current_order = 5, 32 pages）だとする。
  • 領域を 4, 4, 8, 16 と分割し、先頭の 4ページだけを使う。残りの 4, 8, 16ページの領域は使わない。 空き領域として適切な free_area に追加しておく。
  • linux-4.4.1/expand()
  • linux-4.4.1/set_pcppage_migratetype()

	}

	return NULL;
}

コメント†