*参照元 [#l0463606]
#backlinks
*説明 [#r11e849d]
-パス: [[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 を探しに行く。
--適切なサイズではなかった場合、余分な領域を分割する。
**引数 [#n51b0c25]
-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 の選択に使われる
**返り値 [#beec5374]
-struct page *
--確保した領域の先頭ページ
--[[linux-4.4.1/page]]
**参考 [#p6d04f2d]
*実装 [#z10fda94]
/*
* 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 にされるみたい。
-このページは空き領域の先頭ではなくなったので page_order を削除する。
page_order はこのページを先頭として、2^n ページ連続した空き領域があるか？を表す値。
--[[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;
}
*コメント [#j5ecfd65]
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
