Rev.4を表示中。最新版はこちら。

バディシステムとは、バディ(仲間)という命名から、メモリー管理をある種の仲間で管理しようと言うものです。メモリーの仲間とは、物理的に連続するページです。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

バディシステムからページフレームを取得する場合、1,2,4,8,16・・・と２のべき乗で取得するわけですが、それ以外の数のページフレームの獲得はどうなるか？という事ですが、バディシステムの実装からして、そのような個数で取得することはできません。取得数を上回る２のべき乗のオーダで取得します。そして余分に取得したページフレームを空きフレームとして返しています。

カーネルは頻度に1フレームの要求を行うという事から、１フレームの関してバディシステム以外に、CPU変数としてそのフレームを管理しているようです。活性化キャッシュ、不活性化キャシュというようで、1フレームとしてはCPUのハードウエアーにキャッシュラインに乗っている可能性があるからだそうです。そして、上の余分なフレームはこのCPUのページキャッシュに返されていくみたいです。

実はオーダ0でフレームを要求した場合、直接バディシステムからフレームを取得いたしません。まずCPUのページフレームキャッシュから取得を試みるみたいで、もし取得できない場合、バディシステムからフレームを取得し、それをいったん、CPUのページフレームキャッシュに登録した後、そこから1フレームを取得するみたいです。このあたり漠然としか分かりません。いま少し分かったら更新したいな。と思っています。

補足2

MMU機能で、何故物理的に連続したページフレームとして確保する必要があるのか？と疑問がでてきます。LINUX詳解ではまず、「DMAで連続した物理ページが必要だと。」いうことです。これは理解できます。そして、「プロセスにおいて連続する必要が無い場合でも、連続したページを割り当てたらページテーブルを変更する必要がない。」とありますが、ほんとかな？　

ページテーブルはページ毎にエントリーがあり、アロケートした各ページ毎にページエントリーを更新する必要があると理解しています。ページテーブルの変更はキャッシュを無効にするため負荷の大きい処理となります。ここでの詳解の「ページテーブルを変更する必要がない。」は、ページテーブルを一気に更新できる。と読み砕きましたが・・・。

非連続としてページを獲得して、獲得毎にページテーブルを更新するのでなく、取得したページを管理し、取得後それ等のページのページテーブルに一気に更新する。という処理も考えられるわけですが、やはり連続したページを一気に取得し、それでもってページテーブルを順に更新した方が流れとしてスムーズだ。とは想像できます。
（カーネルのストレートマップとの関係もあるのでしょうか？）

DMAでかならず連続するページフレームを必要です。それ故バディシステムの必要性がでてきます。その延長線上でプロセスのページアロケートもあるのではと、理解しましたが・・・・。

また、プロセスのメモリー要求は遅延割り当てで、ページ毎のフォルトで割り当てられます。従って通常(?)は1ページ単位。そうなるとページはバディシステムというより、CPU変数のフレームキャッシュから割り当てられるわけで、バディシステムのプロセスメモリー要求で依存度はどれほどのものと言えるのでしょうか？

追記

MMUでなぜ連続するページで管理しなければならないか？という事ですか、ページ単位で管理するより、まとめて管理した方が、管理しやすく（上記のバディシステム）また、パイプラインとかキャッシュのハード的要素から効率的ということでは・・・。