Linux Kernel(2.6)の実装に関するメモ書き

スラブアロケータ


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

linux-2.6.16.1でのメモ。

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にキャッシュされているスラブがチェーンされる。オブジェクトを取得する際はfreeよりもこちらが優先される。
slabs_full
スラブ内のオブジェクトが全て割り当て済みもしくはarray_cacheにキャッシュされているスラブがチェーンされる。
slabs_free
スラブ内のオブジェクトが全てFreeなスラブがチェーンされる。

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

(*1) array_cacheは実際にはCPU毎に存在する。また、ノード内のCPUで共用しているsharedキャッシュも存在する。

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

メモリオブジェクトを解放するとキャッシュに戻される。キャッシュしているメモリオブジェクト数が一定数を越えると一部がキャッシュから削除されて、そのメモリオブジェクトはスラブ内で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にキャッシュする段階でフリーリストから外されるので、割り当て状態/キャッシュ状態どちらかの状態ということになる。


[その他]
objpの領域はBuddy Systemから確保されるのでページ境界にアライメントされている。
これに対し、メモリオブジェクトを配置する際にcolour_off分のオフセットを加えることで、メモリオブジェクト種別毎にアライメントがずれるようにしている。これによりCPUキャッシュの効率が高まることが期待できる。

4. 関数

4.1 キャッシュの作成

kmem_cache_create()でキャッシュを作成できる。

kmem_cache_create()

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

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


4.2メモリオブジェクトの確保

メモリを確保する時はkmem_cache_alloc()で確保する。kmem_cache_create()で返されたキャッシュへのポインタを指定する。

kmem_cache_alloc()のメモ
  • 処理の実体は____cache_alloc。
  • array_cacheからメモリオブジェクトを取得する。
  • array_cacheにオブジェクトがなかったらcache_alloc_refill()を呼び、slabs_partial,slabs_freeのスラブからオブジェクトをarray_cacheに移動する。
スラブにもオブジェクトがなかった場合は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を初期化




5. その他

スラブアロケータのキャッシュの状況は/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)のキャッシュがこれに該当する。


[内部関数のメモ]

cache_alloc_refill()
オブジェクト割り当て時にarray_cacheが空だった場合に、スラブ内のオブジェクトを新たにキャッシュする。

cache_grow()
新しいスラブを作成してslabs_freeにつなぐ。
オブジェクト割り当て時にslabs_freeもslabs_partialもなくなった時に使われる。

alloc_slabmgmt()
スラブを作成する。

slab_get_obj()
スラブのフリーリストからメモリオブジェクトを取得する。


最終更新 2006/07/07 21:01:54 - kztomita
(2006/03/27 14:13:08 作成)
添付ファイル
kmemcache.png - kztomita
slab.png - kztomita


リンク
最近更新したページ
検索