Linux スラブ・アロケーターの徹底調査

Linux のメモリー管理方法について学ぶ

オペレーティング・システムのパフォーマンスの良し悪しは、オペレーティング・システムがどれだけ効率的にリソースを管理できるかによってある程度決まります。かつてはヒープ・メモリー・マネージャーがメモリー管理の標準でしたが、フラグメント化、それにメモリーを再利用しなければならないということがパフォーマンスの弱点になっていました。現在 Linux® カーネルで使用されているのは、メモリーをサイズに応じたオブジェクトとして割り当てるという方法です。元々この方法が生まれたのは Solaris でしたが、だいぶ前から組み込みシステムで使用されています。この記事ではそんなスラブ・アロケーターの背後にある概念を探り、スラブ・アロケーターのインターフェースとその使用方法を検討します。

M. Tim Jones (mtj@mtjones.com), Consultant Engineer, Emulex

M. Tim Jones は、埋め込みソフトウェアのエンジニアであり、GNU/Linux Application Programming, AI Application Programming と BSD Sockets Programming from a Multilanguage Perspective の著者でもあります。エンジニアとして経歴は幅広く、静止衛星用のカーネル開発から埋め込みシステム・アーキテクチャー、そしてネットワーク・プロトコル開発まで経験しています。現在は Emulex Corp. のシニア主席エンジニアです。


developerWorks 貢献著者レベル

2007年 5月 15日

動的メモリー管理

メモリー管理の最終目標は、さまざまなユーザーがさまざまな用途で動的にメモリーを共有できるようにする方法を提供することです。メモリー管理には、以下の要件を同時に満たす方法が必要となります。

  • メモリー管理に必要な時間を最小限にする
  • 一般用途で使用できるメモリーを最大限にする (管理のオーバーヘッドを最小限にする)

メモリー管理は突き詰まるところ、上記のトレードオフのゼロサム・ゲームです。管理対象のメモリーを少なくする代わりに利用可能なメモリーの管理に時間をかけるというアルゴリズムを開発することもできれば、効率的にメモリーを管理する一方、使用するメモリーを多くするというアルゴリズムを開発することもできます。最終的には、その特定のアプリケーションの要件によってトレードオフのバランスが決まります。

初期のメモリー管理では、ヒープを基準にした割り当て手法が使われていました。この方法では、大きなメモリー・ブロック (ヒープ) からユーザーが定義した目的のためにメモリーを提供します。ユーザーはメモリー・ブロックが必要になると、指定のサイズを要求します。ヒープ・マネージャーは (特定のアルゴリズムを使用して) 利用可能なメモリーを調べ、メモリー・ブロックを返します。メモリーの検索で使用されるアルゴリズムは、ファースト・フィット (ヒープ内で最初に検出された、要求を満たすブロック) またはベスト・フィット (ヒープ内で最適に要求を満たすブロック) です。ユーザーはメモリーを使い終えると、メモリーをヒープに返します。

このヒープに基づく割り当て手法では、フラグメント化が根本的な問題となります。複数のメモリー・ブロックが割り当てられると、それぞれのブロックは順序もタイミングも関係なく戻されます。そのためヒープ内に穴ができやすくなり、空きメモリーの効率的な管理に必要な時間も長くなるからです。このアルゴリズムは、メモリー効率には優れているかもしれませんが (必要な分を割り当てるため)、ヒープの管理には時間がかかります。

管理の時間を短縮できるという点で優れているのは、バディ・メモリー割り当てと呼ばれる別のメモリー管理方法です。この手法では、メモリーを 2 のべき乗のパーティションに分割し、ベスト・フィット方式で要求されたメモリーを割り当てようとします。ユーザーがメモリーを解放すると、バディ・ブロック内のそのメモリーに隣接するメモリーも同じく解放されているかどうかが調べられます。解放されている場合は、フラグメント化を最小限にするためにブロックが結合されます。このアルゴリズムは時間効率の点で優れているとは言え、ベスト・フィット方式であることからメモリーを無駄にする可能性があります。

この記事では Linux カーネルのメモリー管理を取り上げ、特にスラブの割り当てによるメモリー管理メカニズムに焦点を絞ります。

スラブ・キャッシュ

Linux で使用されるスラブ・アロケーターは、当初、Jeff Bonwick が SunOS オペレーティング・システムに導入したアルゴリズムに基づいています。Jeff のアロケーターがその動作の中心とするのは、オブジェクト・キャッシングです。カーネル内では、ファイル記述子やその他の一般的な構造を含め、限られた一連のオブジェクトにかなりの量のメモリーが割り当てられますが、Jeff はカーネル内で通常のオブジェクトを初期化するのにかかる時間が、そのオブジェクの割り当てと割り当て解除にかかる時間を上回っていることに気付きました。彼が出した結論は、メモリーを解放してグローバル・プールに戻す代わりに、メモリーをその用途のために初期化した状態のままにするということです。例えば、メモリーを mutex 用に割り当てるとすると、mutex 初期化関数 (mutex_init) を実行しなければならないのはメモリーを最初に mutex に割り当てるときだけとなります。それ以降のメモリー割り当てでは初期化を行う必要はありません。メモリーはすでに、前の割り当て解除とデコンストラクターの呼び出しによって適切な状態になっているからです。

Linux スラブ・アロケーターは、このような概念などを使って、スペースと時間の両方の点で効率的なメモリー・アロケーターを構築します。

図 1 に、スラブ構造の構成の概略を示します。最上位にある cache_chain はスラブ・キャッシュのリンク・リストです。このリストは、目的の割り当てサイズに最も近いキャッシュを (リストを繰り返し処理して) 検索するベスト・フィット・アルゴリズムに役立ちます。cache_chain に含まれる要素は kmem_cache 構造参照 (キャッシュ) で、これが管理対象とする指定サイズのオブジェクト・プールを定義します。

図 1. スラブ・アロケーターの主要な構造
Figure 1. The major structures of the slab allocator

それぞれのキャッシュにはスラブ、つまりメモリーの隣接ブロック (通常はページ) のリストが含まれます。スラブには以下の 3 種類があります。

slabs_full
完全に割り当てられているスラブ
slabs_partial
部分的に割り当てられているスラブ
slabs_empty
空、または割り当てられたオブジェクトがないスラブ

slabs_emptyリストのスラブは、リープの第一候補であることに注意してください。リープとは、スラブで使用されているメモリーを他の用途のためにオペレーティング・システムに戻すプロセスです。

スラブ・リストに含まれるそれぞれのスラブは隣接するメモリー・ブロック (1 つ以上の連続ページ) です。このブロックはオブジェクトに分割されます。特定キャッシュでの割り当ておよび割り当て解除は、これらのオブジェクトが基本要素となります。注意すべき点は、スラブはスラブ・アロケーターにとって最小の割り当て単位だということです。そのため、拡張が必要な場合には、スラブ単位に拡張が行われます。通常は、スラブごとに多数のオブジェクトが割り当てられています。

スラブのオブジェクトを割り当てまたは割り当て解除すると、スラブ・リスト間でスラブ単位の移動が行われることになります。例えば、スラブ内ですべてのオブジェクトが使用されると、そのスラブは slabs_partial リストから slabs_full リストに移されます。スラブがフルの状態から 1 つのオブジェクトが割り当て解除された状態になると、slabs_full リストからslabs_partial リストに移されます。すべてのオブジェクトが割り当て解除された場合には、slabs_partial リストから slabs_emptyリストに移されます。

スラブの背後にある動機

スラブ・キャッシュ・アロケーターには、従来のメモリー管理スキームに勝る多くの利点があります。まず、カーネルはいずれも小さなオブジェクトの割り当てに依存し、これらのオブジェクトはシステムの存続期間中に何度も割り当てられますが、スラブ・キャッシュ・アロケーターは同じようなサイズのオブジェクトをキャッシュすることによって割り当てを行うため、通常発生するフラグメント化の問題がなくなります。また、スラブ・アロケーターでは共通オブジェクトの初期化もサポートするため、同じ目的で何度もオブジェクトを初期化する必要がありません。そして最後の利点として、スラブ・アロケーターはハードウェア・キャッシュのアライメントと色分けをサポートするため、異なるキャッシュ内のオブジェクトで同じキャッシュ・ラインを占有させて、キャッシュ使用率とパフォーマンスを向上させることができます。


API 関数

ここからは、スラブ・キャッシュの新規作成、キャッシュへのメモリー追加、キャッシュの破棄を行うためのアプリケーション・プログラム・インターフェース (API)、そしてキャッシュからのオブジェクトの割り当ておよび割り当て解除を実行する関数について説明します。

最初のステップは、スラブ・キャッシュ構造を作成することです。これは、以下のように静的に作成できます。

struct struct kmem_cache *my_cachep;

スラブ・キャッシュの Linux ソース

スラブ・キャッシュのソースは ./linux/mm/slab.c にあります。kmem_cache 構造は ./linux/mm/slab.c でも定義されています。この記事では、2.6.21 Linux カーネルでの現行の実装に焦点を絞って説明します。

この参照は、作成、削除、割り当てなどの他のスラブ・キャッシュ関数で使用されることになります。kmem_cache 構造には、中央演算処理装置 (CPU) ごとのデータ、一連の調整可能な値 (proc ファイル・システムからアクセス可能)、統計、そしてスラブ・キャッシュの管理に必要な要素が含まれます。

kmem_cache_create

kmem_cache_create は、新しいキャッシュを作成するためのカーネル関数です。この関数は通常、カーネルの初期化時、またはカーネル・モジュールを初めてロードするときに実行します。プロトタイプは以下のように定義されます。

struct kmem_cache *
kmem_cache_create( const char *name, size_t size, size_t align,
                       unsigned long flags;
                       void (*ctor)(void*, struct kmem_cache *, unsigned long),
                       void (*dtor)(void*, struct kmem_cache *, unsigned long));

name 引数が定義するキャッシュの名前は、proc ファイル・システム (/proc/slabinfo 内) がこのキャッシュを識別するために使用します。size 引数はこのキャッシュに対して作成するオブジェクトのサイズ、そして align 引数はそれぞれのオブジェクトに必要なアライメントを定義します。flags 引数が指定するのは、キャッシュに対して有効にするオプションです。表 1 にこれらのフラグを記載します。

表 1. kmem_cache_create のオプション (flags に指定) の抜粋リスト
オプション説明
SLAB_RED_ZONEオブジェクトのヘッダーとトレーラーにマーカーを挿入して、バッファー・オーバーランのチェックをサポートします。
SLAB_POISONスラブに既知のパターンを入力し、キャッシュ内のオブジェクトを監視できるようにします (オブジェクトはキャッシュが所有しますが、外部で監視されます)。
SLAB_HWCACHE_ALIGNこのキャッシュ内のオブジェクトをハードウェアのキャッシュ・ラインにアライメントするように指定します。

ctor引数と dtor 引数はそれぞれ、オプションのオブジェクト・コンストラクターおよびデコンストラクターです。コンストラクターとデコンストラクターはユーザーが指定するコールバック関数で、キャッシュから割り当てる新規オブジェクトは、コンストラクターによって初期化できます。

キャッシュが作成されると、その参照が kmem_cache_create関数によって返されます。ここで注意すべき点は、この関数はキャッシュにメモリーを割り当てないということです。メモリーは、キャッシュ (最初は空の状態) からのオブジェクト割り当てが試行されたときに refill操作によって割り当てられます。キャッシュのオブジェクトがすべて使用された場合にも、この操作でキャッシュにメモリーが追加されます。

kmem_cache_destroy

kmem_cache_destroyは、キャッシュを破棄するためのカーネル関数です。この関数は、カーネル・モジュールがアンロードされるときに呼び出されます。この関数を呼び出すのは、キャッシュが空になってからです。

void kmem_cache_destroy( struct kmem_cache *cachep );

kmem_cache_alloc

指定したキャッシュからオブジェクトを割り当てるには、kmem_cache_alloc 関数を使用します。オブジェクトを割り当てるキャッシュと一連のフラグは、呼び出し側が指定します。

void kmem_cache_alloc( struct kmem_cache *cachep, gfp_t flags );

この関数は、キャッシュからオブジェクトを返します。キャッシュが空の場合、この関数は cache_alloc_refill を呼び出してキャッシュにメモリーを追加することができます。kmem_cache_alloc のフラグ・オプションは、kmalloc のフラグ・オプションと同じです。表 2 に、フラグ・オブションの一部をリストします。

表 2. kmem_cache_alloc および kmalloc カーネル関数のフラグ・オプション
フラグ説明
GFP_USERユーザー用のメモリーを割り当てます (この呼び出しはスリープ状態になる場合があります)。
GFP_KERNELカーネルの RAM からメモリーを割り当てます (この呼び出しはスリープ状態になる場合があります)。
GFP_ATOMICこの呼び出しでのスリープ状態を抑止します (割り込みハンドラーに便利です)。
GFP_HIGHUSER高位メモリーから割り当てます。

SNUMA の場合のスラブ割り当て

NUMA (Non-Uniform Memory Access) アーキテクチャーの場合、指定したノードに対する割り当て関数は kmem_cache_alloc_node となります。

kmem_cache_zalloc

カーネル関数 kmem_cache_zalloc は kmem_cache_alloc と同様ですが、唯一異なる点として、この関数はオブジェクトを呼び出し側に返す前に memset を実行してオブジェクトをクリアします。

kmem_cache_free

オブジェクトを解放してスラブに返すには、kmem_cache_free を使用します。呼び出し側がキャッシュ参照と解放するオブジェクトを指定します。

void kmem_cache_free( struct kmem_cache *cachep, void *objp );

kmalloc and kfree

カーネルで最もよく使われるメモリー管理関数は、kmallockfreeです。この 2 つの関数のプロトタイプは、以下のように定義されます。

void *kmalloc( size_t size, int flags );
void kfree( const void *objp );

kmalloc の引数は、要求するオブジェクトの割り当てサイズと一連のフラグだけです (表 2 の抜粋リストを参照)。ただし、kmallockfree は前に定義された関数と同じようにスラブ・キャッシュを使用します。kmalloc 関数は、オブジェクトを割り当てるための特定のスラブ・キャッシュを指定する代わりに、サイズ制約を満たすキャッシュを見つけるために使用可能なキャッシュを繰り返し処理します。キャッシュが見つかると、オブジェクトが割り当てられます ( __kmem_cache_alloc を使用)。kfree でオブジェクトを解放するには、virt_to_cache を呼び出してオブジェクトの割り当て元となったキャッシュを判断します。この関数によって返されたキャッシュ参照が __cache_free で使用されて、オブジェクトが解放されます。

汎用オブジェクトの割り当て

スラブ・ソースの内部には、kmem_find_general_cachep という関数が用意されています。この関数は、キャッシュを検索して必要なオブジェクト・サイズに最も適合するスラブ・キャッシュを見つけます。

その他の関数

スラブ・キャッシュ API には、上記の他にも便利な関数が多数用意されています。例えば kmem_cache_size 関数は、該当するキャッシュが管理するオブジェクトのサイズを返します。また、 kmem_cache_name を呼び出して、特定キャッシュの名前 (キャッシュ作成時に定義された名前) を検索することもできます。キャッシュを縮小するにはキャッシュ内のフリー・スラブを解放するという方法を使いますが、それには kmem_cache_shrink の呼び出しを実行します。ただし、このアクション (リープ) はカーネルが (kswapd により) 一定の間隔で自動的に行うことに注意してください。

unsigned int kmem_cache_size( struct kmem_cache *cachep );
const char *kmem_cache_name( struct kmem_cache *cachep );
int kmem_cache_shrink( struct kmem_cache *cachep );

スラブ・キャッシュの使用例

以下に記載する一連のコード・スニペットで、スラブ・キャッシュの新規作成、キャッシュからのオブジェクトの割り当てと割り当て解除、そしてキャッシュの破棄を例示します。まず初めに必要なのは、kmem_cacheオブジェクトの定義と初期化です (リスト 1 を参照)。この特定のキャッシュには 32 バイトのオブジェクトが含まれます。また、flags 引数 SLAB_HWCACHE_ALIGNで定義しているように、キャッシュはハードウェア・キャッシュにアライメントされます。

リスト 1. スラブ・キャッシュの新規作成
static struct kmem_cache *my_cachep;

static void init_my_cache( void )
{

   my_cachep = kmem_cache_create( 
                  "my_cache",            /* Name */
                  32,                    /* Object Size */
                  0,                     /* Alignment */
                  SLAB_HWCACHE_ALIGN,    /* Flags */
                  NULL, NULL );          /* Constructor/Deconstructor */

   return;
}

スラブ・キャッシュを割り当てたら、今度はそこからオブジェクトを割り当てます。リスト 2 に、キャッシュからのオブジェクトの割り当ておよび割り当て解除の例を記載します。この例では他に 2 つの関数も使用しています。

リスト 2. オブジェクトの割り当てと割り当て解除
int slab_test( void )
{
  void *object;

  printk( "Cache name is %s\n", kmem_cache_name( my_cachep ) );
  printk( "Cache object size is %d\n", kmem_cache_size( my_cachep ) );

  object = kmem_cache_alloc( my_cachep, GFP_KERNEL );

  if (object) {

    kmem_cache_free( my_cachep, object );

  }

  return 0;
}

最後のリスト 3 は、スラブ・キャッシュを破棄する例です。呼び出し側は、破棄操作の間にキャッシュからのオブジェクト割り当てが試行されないようにする必要があります。

リスト 3. スラブ・キャッシュの破棄
static void remove_my_cache( void )
{

  if (my_cachep) kmem_cache_destroy( my_cachep );

  return;
}

スラブへの proc インターフェース

proc ファイル・システムは、システム内でアクティブなすべてのスラブ・キャッシュを簡単に監視する方法を提供します。/proc/slabinfo という名前のこのファイルは、ユーザー空間からアクセスできるいくつかの調整可能な値だけでなく、すべてのスラブ・キャッシュに関する詳細情報も提供します。現行バージョンのスラブ情報にはヘッダーも含まれるので、出力が多少読みやすくなっています。このファイルが提供する情報は、システム内にあるスラブ・キャッシュごとのオブジェクトの数、アクティブなオブジェクトの数、オブジェクトのサイズです (スラブごとのオブジェクトとページと併せて)。また、一連の調整可能な値とスラブ・データも含まれています。

特定のスラブ・キャッシュを調整するには、単にスラブ・キャッシュ名と 3 つの調整可能なパラメーターをストリングとして /proc/slabinfo ファイルにエコー出力するだけで実行できます。以下は、制限とバッチカウントを増やし、共有項目はそのままにする例です (フォーマットは "キャッシュ名 制限 バッチカウント 共有項目" となります)。

# echo "my_cache 128 64 8" > /proc/slabinfo

limit フィールドは、CPU ごとにキャッシュに入れるオブジェクトの最大数を指定します。batchcount フィールドは、CPU 単位のキャッシュが空になったときにそこへ転送するグローバル・キャッシュ・オブジェクトの最大数です。shared パラメーターは、SMP (Symmetric MultiProcessing) システムに対する共有動作を指定します。

proc ファイル・システムでスラブ・キャッシュのパラメーターを調整するには、スーパーユーザー特権が必要であることに注意してください。


SLOB アロケーター

小規模な組み込みシステムには、SLOB と呼ばれるスラブ・エミュレーション層があります。スラブに置き換わるこの層は小規模な組み込み Linux システムでは有利ですが、最大 512KB のメモリーを確保するので、フラグメント化や、拡張性が乏しいといった欠点があります。CONFIG_SLAB を無効にすると、カーネルはこの SLOB アロケーターを使うようになります。詳細は、「参考文献」セクションを参照してください。


さらに詳細を調べるには

スラブ・キャッシュ・アロケーターのソース・コードは、実際には、Linux カーネルでは理解しやすいコードの 1 つとして挙げられます。関数コールの間接的な部分を除けば、このソースは直観的で、概して十分にコメントが書かれています。スラブ・キャッシュ・アロケーターについてもっと知りたいという方には、メカニズムに関する最新資料であるこのソースから取り掛かることをお勧めします。以下の「参考文献」セクションではスラブ・キャッシュ・アロケーターについて説明している資料をいくつか紹介していますが、残念ながら、いずれの資料も現行の 2.6 実装には時代遅れです。

参考文献

学ぶために

製品や技術を入手するために

議論するために

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=236140
ArticleTitle=Linux スラブ・アロケーターの徹底調査
publish-date=05152007