スラブアロケータ

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

1. 概要

Buddy Systemでは物理ページ単位のメモリの確保になるため、あるメモリオブジェクト(例えばプロセスのtask_structとか)を動的に確保するのには向いていない。スラブアロケータではBuddy Systemとの間に入り、メモリオブジェクトの確保／解放機能を提供する。

スラブアロケータでは、あらかじめメモリオブジェクトに対してキャッシュ(kmem_cache)を作っておき、そのキャッシュからメモリオブジェクトを取得する形をとる。キャッシュは足りなくなれば自動的に確保されるようになっている。

Slabから取得するバッファはBuddy Systemから取得しており、以下の特徴がある。

仮想アドレスに対して物理ページが割り当て済み(アクセスしてPageFaultになることはない)
物理的に連続ページ

2. スラブアロケータの特長

スラブアロケータはメモリ確保に関して以下の効率化を行っている。

(1) メモリ使用量の効率化

Linuxに限らずメモリ確保処理では2^nサイズの決められた大きさのサイズでしかメモリを確保できないものがあり、無駄が生じることがあった(例えば36Byteの領域を確保しようとすると、64Byte確保される)。スラブアロケータでは、メモリオブジェクトのサイズ(*1)で確保されるのでメモリの使用効率がよい。

(*1) 実際にはアライメントにより少しサイズが大きくなる。

(2) CPUキャッシュメモリの効率化

メモリオブジェクトの先頭アドレスがページ先頭に揃わないように、スラブ毎にずらしているので、CPUキャッシュメモリの特定Lineへのアクセス集中がなくなり、実行速度の向上が期待できる。

3. スラブアロケータのデータ構造

スラブアロケータのデータ構造を図1に示す。

図1 kmem_cacheの全体構造

cache_chainがkmem_cacheのリストになっている。kmem_cacheはメモリオブジェクトの種類毎にある管理テーブル。図1では"rpc_buffers"と"rpc_tasks"。kmem_cache_create()で新しいメモリオブジェクト用のキャッシュを作るとここに新しいkmem_cacheがチェーンされる。

割り当てられるメモリオブジェクトはスラブの中に配列状に並んでおり、kmem_cache内のslabs_partial,full,freeの3つのリストからチェーンされている。3つのリストはそれぞれ表1に示すような役割を持つ。

表1 スラブのリスト

リスト	説明
slabs_partial	スラブ内の一部のオブジェクトが割り当て済みもしくはarray_cacheにキャッシュされているスラブがチェーンされる。
slabs_full	スラブ内のオブジェクトが全て割り当て済みもしくはarray_cacheにキャッシュされているスラブがチェーンされる。
slabs_free	スラブ内のオブジェクトが全てFreeなスラブがチェーンされる。

実際の割り当ての際には、スラブ内のメモリオブジェクトはキャッシュ(array_cache)を経由して行われる。array_cacheのentry配列はキャッシュしているメモリオブジェクトへのポインタを持つ。availはキャッシュしているオブジェクト数を持つ。array_cacheを使用することで、同じメモリ領域が繰り返し使用されてCPUキャッシュメモリの効率が良くなると思われる。

割り当て時にキャッシュがなくなると、スラブから空いているメモリオブジェクトをキャッシュに入れる。この時、スラブにメモリオブジェクトが無くなってしまった場合は、新たなスラブが作成される。

メモリオブジェクトを解放するとキャッシュに戻される。キャッシュしているメモリオブジェクト数が一定数を越えると一部がキャッシュから削除されて、そのメモリオブジェクトはスラブ内でFreeになる。

スラブの構造の詳細を図2に示す。

図2 スラブの構造

スラブにはスラブ内にメモリオブジェクトを持つ形式(図2左側)とスラブの外にメモリオブジェクトを持つ形式(図2右側:OffSlab形式)がある。kmem_cacheを作成する時にスラブのサイズが既定値を越えるようだとOffSlab形式になる。以下の説明では図左側のケースで説明する。

スラブの管理データとしてstruct slabがある。struct slabの直後にスラブに収容するメモリオブジェクト数分のkmem_bufctl_t(unsigned intのtypedef)の配列がある。図2はn+1個のメモリオブジェクトを持っている。kmem_bufctl_t[]の後に実際に割り当てられるメモリオブジェクトが配列状に並んでいる。struct slabのs_memはこのメモリオブジェクト配列の先頭を指している。

kmem_bufctl_t[]はメモリオブジェクトのフリーリストとなっている。#xのkmem_bufctl_t[]エントリは#xのメモリオブジェクトに対応している。
struct slabのfreeがフリーリスト先頭のkmem_bufctl_t[]の要素番号を持ち、そこからkmem_bufctl_t[]に格納されている次のオブジェクトの要素番号をたどってFreeなメモリオブジェクト取得できる。リスト最後のkmem_bufctl_t[]にはBUFCTL_ENDが格納されている。図2では#1のオブジェクトが割り当て済みの状態を示しており、フリーリストにはkmem_bufctl_t[1]はつながれていない。

表1にも示したが、スラブ内のメモリオブジェクトが全てFreeならばスラブはslabs_freeにつながれ、一部だけFreeならば、slabs_partialにつながれる。Freeがなければslabs_fullにつながれる。

なお、フリーリストにないということは、そのオブジェクトが割り当てられているということではない。メモリオブジェクトはarray_cacheにキャッシュする段階でフリーリストから外されるので、割り当て状態/キャッシュ状態どちらかの状態ということになる。

[キャッシュ作成]
kmem_cache_create()

        kmem_cache_alloc()でキャッシュを自分自身から取得する。

        Slabが必要とするページ数(cachep->gfporder)
        Slabあたりのobject数(cachep->num)を計算する。
                :
        objectサイズが大きい場合はCFLGS_OFF_SLABを立てる。
                :
        この時点ではまだ、Slab/Objectは作成しない。
        alloc時にobject取得に失敗してkmem_cache_grow()で作成される。

[オブジェクト確保]
kmem_cache_alloc()
        __kmem_cache_alloc()
                指定キャッシュのslabs_partial/freeからobjectを割り当てる。
                objectが無ければ
                kmem_cache_grow()
                                :
                        object用にkmem_getpages()でBuddy Systemからページを取得する。
                        (仮想<->物理アドレスのマッピングは既に済んでいる。「物理メモリ管理.txt」参照)
                                :
                        kmem_cache_slabmgmt()
                                off-slabの場合はkmem_cache_alloc()でslabも取得
                                :
                        Slabとobjectを初期化

その他

スラブアロケータのキャッシュの状況は/proc/slabinfoで確認できる。

slabinfo - version: 2.1
# name            <active_objs> <num_objs> ...
rpc_buffers            8      8   2048 ...
rpc_tasks              8     15    256 ...
rpc_inode_cache        6      7    512 ...
   :
   :

kmalloc()で確保するメモリもスラブアロケータから取得している。/proc/slabinfoで表示されるsize-xx,size-xx(DMA)のキャッシュがこれに該当する。