Ledの日記： SLUBアロケータとは何ぞや

Linuxカーネルのアップデートに関連して、
SLUBアロケータがどうなってるのか解説している記事を翻訳してみた。

翻訳を終えて：
  どうも要領を得ない説明で、わかるような、わからないような。
  何がどう定義されているか、厳密な話はやっぱり「そーす嫁」ってことなんだろうかな。
  全体として、ついいろんな語にことわり書きを沢山付けてしまうあたり、プログラマーの言葉遣いってのは英語圏でも変わんないんだな。

以下翻訳。
--
slabアロケータは何年もの間Linuxカーネルのメモリ管理の中核を担ってきた。このアロケータは（低レベルなページアロケータのてっぺんである）特定のサイズのオブジェクトのキャッシュを管理し、高速かつ効率的なメモリ割り当てを行っている。カーネルハッカーはこのslabコードに関してはあまり触れてこなかった、というのは複雑でなおかつ多くの場合うまく動いているからだ。

Christoph Lameterはslabアロケータがうまく働いてくれない状況に直面した一人である。彼は何度も日々長くなる不平のリストを持っていた。slabアロケータはオブジェクトのキューをいくつか保持しており、このキューはメモリ割り当てを高速にするが多少処理を複雑にしている。それに加えて、記憶容量のオーバーヘッドはシステムのサイズに併せて大きくなる傾向にある。

SLABオブジェクトキューはノード、CPUにつきひとつ存在する。alienキャッシュキューは、それぞれのプロセッサやノードのためにキューの配列さえも保持している。とても大きいシステムに於いては、キューやキューの中のオブジェクトの数は指数的に大きくなりうる。我々の用意したプロセッサあたり1kノードのシステムでは、こうしたキューのためのオブジェクトへの参照を保持するためだけに数ギガバイトが使用される。恐れるべきは、いつかそうしたキューのためにマシンのメモリが消費し尽くされてしまうことだ。

それだけでなく、各slab（１つ以上の連続したページで、オブジェクトはそこから割り当てられる）は先頭にメタデータの塊を持っていて、オブジェクトの割り当てを難しくしている。メモリが残り少なくなったときにキャッシュの消去を行うコードはさらに別のレベルで話を複雑にしている。同様の話がまだまだある。

Christophはそこで SLUB アロケータをslabコードの置き換えとすることを考えた。ほとんどのキューや関連するオーバーヘッドを削減することで、SLUBはより良いパフォーマンスとスケーラビリティを約束し、一般にslab構造を単純化する一方で、現行のslabアロケータのインターフェースは維持する。

SLUBアロケータにおいては、ひとつのslabは単純にひとつ以上のページからなり、それらはあるサイズのオブジェクトと併せてきちんと固められている。確保されていないオブジェクトは連結リストとして保持されているという例外はあるものの、slabの中にはメタデータは存在しない。メモリ確保の要求が来た場合、上記連結リストの最初のオブジェクトが確保され、リストから削除され、そして要求元へ返される。

slab毎にあるメタデータが無いことで、読者はその「先頭のオブジェクト」がどう見付けられるかを不思議に思うかもしれない。答えは、SLUBアロケータがシステムのメモリマップに関連する情報を詰め込んでいることだ。その関連データというのは、slabを構成するページに関連づけられたページ構造である。このstructページを大きくするのはひどく嫌われるが、SLUBアロケータはさらに共用体を加えることで、この複雑な構造をさらに複雑にする。結果として、structページには新しいフィールドが３つ追加されるが、それらは関連づけられたページがslabの一部である場合に意味を持つ:
        void *freelist;
        short unsigned int inuse;
        short unsigned int offset;
slabの使用において、freelistはslab中で最初の未使用オブジェクト、inuseはそのslabの中で確保済のオブジェクトの数、offsetはアロケータに対して次の未使用オブジェクトの位置を示す。SLUBアロケータは未使用オブジェクトに対してRCUを使用することがあるが、そのためには「次のオブジェクト」ポインタをオブジェクト自身の外に置く必要があり、offsetポインタはそのポインタがどこにセットされたかを知るためのアロケータのたどる道筋である。

slabが最初にアロケータによって作成されたとき、まだそこには使用済オブジェクトは存在しない。一度オブジェクトが確保されることにより、それは「部分使用」slabとなりkmemキャッシュ構造のリストの中に格納される。このぱっちはスケーラビリティのためのものであるので、実のところ、システム中のNUMAノード一つにつき「部分使用」リストがある。しかし、これは部分使用slabでシステムが埋まってしまう前にノード間でつながる。

NUMAノードの間においてさえもキャッシュラインが上下するのを防ぐため、CPU毎にactive slabの配列がある。workqueueを通して走る特殊なスレッドがあり、これはCPU毎のslabの使用状況を監視している。もしCPU毎のslabが使われていなければ、他のプロセッサが使用できるように部分使用リストの中に戻される。

もしも一つのslabの中のオブジェクトが全て確保された場合、アロケータはそのslabのことを単純に一気に忘れてしまう。この満杯slabの中のオブジェクトが開放されると、アロケータはシステムメモリマップを通してこのslabを再確保し、適切な部分使用リストへ戻す。あるslabの中の全てのオブジェクトが開放された場合（これはinuseカウンタで検出できる）、そのslab全体がアロケータへ返却される。

SLUBアロケータの面白い機能の一つとして、同様のサイズやパラメータのオブジェクトのslabを合体させてしまうことが挙げられる。結果システムで使用されるslabの数が減り（50%減った例もある）、slab確保の局所性が向上し、slabメモリの断片化が減少する。このパッチには以下の記述がある：

気を付けるべきは、なにはともあれカーネルの未知のバグがこのマージ機能によって明らかになる可能性があることだ。なぜならば壊れたオブジェクトが異なった方法で配置され、異なった近隣オブジェクトの破壊をするかもしれないからだ。こういうのを見付けるには、sanity checkを有効にするべきだ。

バグが目立つようになるというのは一般にいいことだが、SLUBアロケータが広く使われるようなると、こうしたバグが全て潰されるまで奇妙な振舞を示すかもしれない。

これからは適用が拡大される：SLUBアロケータは今 -mm ツリーに置かれているが、2.6.22では主流に取り込まれる。5-10%の効率向上が報告されているため、シンプルになったコードは魅力的である。もしも取り込まれた場合、しばらくの間SLUBは現状のslabアロケータと共存するだろう（そして小さなシステムのためにはSLOBアロケータというのもある）。もっと長い目で見れば、現状のslabアロケータはその役目を終えつつある。