バディシステム
Rev.2を表示中。最新版はこちら。
バディシステムとは、バディ(仲間)という命名から、メモリー管理をある種の仲間で管理しようと言うものです。メモリーの仲間とは、物理的に連続するページです。1,2,4,8,16・・・という具合に、２を基底とする数の塊(実装する上で、この事が重要になってきます。)で管理すると言うものです。ただこれだけですが、バディシステムと言う名が有名になったのは、その考え方というより、その実装故でないかと、ソースを見て、プログラミングした人（結果的に設計も含めて）「すごいな〜。」という思いです。バディシステム空のページ取得は__rmqueue関数で行います。__rmqueue_smallest関数で取得し、できなければ__rmqueue_fallback関数から取得するようになっています。なんか同一オーダのブロックリストにカテゴリを設けており、その中からカテゴリーIDとしてmigratetypeで、指定してブロックを取得しているようです。__rmqueue_fallback関数では__rmqueue_smallest関数で取得できなかった場合、別のカテゴリーから取得するみたいです。取得に関しては__rmqueue_smallest関数と同じようです。
（このmigratetypeのカテゴリーが、システム的にどのような意味をもつのかよく分かりません。たぶんzoneでカテゴリを持たしているような意味合いではと・・・）
取得ページ数を指定するのにオーダという形で指定します。オーダは、1ページ取得なら2^0=1,２ページなら2^1,4ページなら2^2と言う具合に、取得ページ数の基底2の指数部となります。
static struct page *__rmqueue(struct zone *zone, unsigned int order,
int migratetype)
{
struct page *page;
page = __rmqueue_smallest(zone, order, migratetype);
if (unlikely(!page))
page = __rmqueue_fallback(zone, order, migratetype);
return page;
}
取得ブロックオーダ(order)から、MAX_ORDERまでforループで取得します。zone->free_area[current_order]は、指定したオーダのブロックフリーリストです。そのリストが空でないかlist_emptyマクロでチェックします。空だと上位のオーダからの取得になります。migratetypeは、同じオーダのブロックをある種のカテゴリーに分けているようで、取得順序をカテゴリーで行っているようですが、その意味するところはよく分かりません。ブロックリストは、list_headとするはarea->free_list[migratetype]に、page->lruを項目としてリストしています。目的とするブロックリストが空でないなら、list_entryマクロで先頭ページのページディスクリプタを取得できるわけです。
そしてlist_delマクロで、そのページをブロックリストから削除し、rmv_page_order関数でpage->private=0としています。（バディーシステムで管理されているページは、page->privateに管理リストのオーダがセットするようです。）
そのブロックオーダのリストは、１ブロックなくなり(area->nr_free--)、そして消費したページ数 1UL << orderです。従って__mod_zone_page_state関数で、フリーページ数をzone->vm_stat[NR_FREE_PAGES] -= (1UL << order)で更新しています。
そしてexpand関数をコールします。この関数がバディシステムの味噌となります。上位のオーダから取得した場合、残りのブロックを下位のオーダに繋ぎかえる処理を行います。指定したオーダから取得できた場合何もしません。
static struct page *__rmqueue_smallest(struct zone *zone, unsigned int order,
int migratetype)
{
unsigned int current_order;
struct free_area * area;
struct page *page;
for (current_order = order; current_order < MAX_ORDER; ++current_order) {
area = &(zone->free_area[current_order]);
if (list_empty(&area->free_list[migratetype]))
continue;
page = list_entry(area->free_list[migratetype].next,
struct page, lru);
list_del(&page->lru);
rmv_page_order(page);
area->nr_free--;
__mod_zone_page_state(zone, NR_FREE_PAGES, - (1UL << order));
expand(zone, page, order, current_order, area, migratetype);
return page;
}
return NULL;
}
引数のlowは取得したいオーダで、highは結果的に取得したオーダです。size = 1 << highは取得したページ数です。high > lowの時、下位オーダに繋ぎかえる必要があります。whileループで回しているのは、取得オーダが直上でなく、その上のオーダから取得した場合もありうるからです。(オーダ２でオーダ４から取得した場合)引数はareaは、取得したブロックリストです。area--でその下位のオーダのリストとなります。size >>= 1でつなぎかえるページ数となります。上位から取得したブロック数はかならず1つで、しかもその半分です。ここが２を基底とする個数でリストしている所以です。
page[size].lruは取得された片割れの先頭ページです。それをlist_addマクロでリスト登録し、set_page_order関数でpage=>privateに管理オーダをセットしています。上位上位のオーダから取得しても、２を基底とするリスト構造のためsize >>= 1するだけで、問題なく処理できるという実装にただただ関心させられました。
static inline void expand(struct zone *zone, struct page *page,
int low, int high, struct free_area *area,
int migratetype)
{
unsigned long size = 1 << high;
while (high > low) {
area--;
high--;
size >>= 1;
VM_BUG_ON(bad_range(zone, &page[size]));
list_add(&page[size].lru, &area->free_list[migratetype]);
area->nr_free++;
set_page_order(&page[size], high);
}
}
ブロックの解放についても同じことが言えます（と思います）。できるだけ連続するブロックを構築して、そのリストに繋ぐ処理が行う必要があり、解放したブロックが下位のブロックと連続となるかの判断も入ってきて、取得の処理よりは複雑になりそうだとは認識していますが・・・。補足
バディシステムからページフレームを取得する場合、1,2,4,8,16・・・と２のべき乗で取得するわけですが、それ以外の数のページフレームの獲得はどうなるか？という事ですが、バディシステムの実装からして、そのような個数で取得することはできません。取得数を上回る２のべき乗のオーダで取得します。そして余分に取得したページフレームを空きフレームとして返しています。カーネルは頻度に1フレームの要求を行うという事から、１フレームの関してバディシステム以外に、CPU変数としてそのフレームを管理しているようです。活性化キャッシュ、不活性化キャシュというようで、1フレームとしてはCPUのハードウエアーにキャッシュラインに乗っている可能性があるからだそうです。そして、上の余分なフレームはこのCPUのページキャッシュに返されていくみたいです。
実はオーダ0でフレームを要求した場合、直接バディシステムからフレームを取得いたしません。まずCPUのページフレームキャッシュから取得を試みるみたいで、もし取得できない場合、バディシステムからフレームを取得し、それをいったん、CPUのページフレームキャッシュに登録した後、そこから1フレームを取得するみたいです。
このあたり漠然としか分かりません。いま少し分かったら更新したいな。と思っています。
