非カーネル用のスラブ・アロケータ

オペレーティング・システムのカーネルのオブジェクト・キャッシュとして利用されているスラブ・アロケータは、 単なる高速なアロケータではなく、 割付・初期化済みのオブジェクトを alloc して、 free の時点ではデストラクタを動かさずに、 次の alloc で free 時点の内容のまま返す働きがあります。 そのために、 フリー・リストをオブジェクトの外に作ったり、 alloc 中のオブジェクトも強制的にデストラクタを摘要してメモリを解放できるようにリストを辿って場所を求められるようになっています。 これは、 カーネルが扱うデータ型が限られている割に、 大きなオブジェクトを頻繁に割付・解放を繰り返し、 初期化結果は同じ内容になっていることが多い、 といったカーネル特有の事情に合わせてあるためです。

一方、 アプリケーションでは、 カーネルに比べると扱うデータ型が増える上に、 同じ内容のオブジェクトを使いまわす利点が減る傾向があります。 たいていの場合は割り付け時にコンストラクタを動かす方が都合が良いですし、 memchached のようにプレーンなデータの割付に使うときは前の内容を使えることの方が少なくて、 全部書き直してしまうことを前提にしても負荷が増えない傾向があります。 アプリケーションで、 スラブ・アロケータを使うときは、 同じサイズのオブジェクトを同じページに固めてフラグメンテーションがおきにくくするというメリットだけが欲しい場合がほとんどです。

free 後のデータを破壊してもかまわないとなると、 フリー・リストのリンクポインタ置き場に廃棄したオブジェクトの領域を直接使っても問題ありません。 さらに、 デスタラクタを動かしてから free するので、 生存しているデータをリストにつなげて管理しておく必要もなくなります。

以上から非カーネル用のスラブ・アロケータを考えてみます。

スラブ中にバッファ管理情報をオブジェクト外に持つ必要がなくなるので単純になります。 フリー・リストはスラブごとに別々にもたせておいた方が、 リストの更新でページのヒット率が悪化することがなくなるので、 この点はカーネル用と同じとします。 スラブ間のリンクは、 空になったスラブを廃棄するときにスラブを空きありスラブのリストから削除することがあるので、 相変わらず必要です。 ただし、 キャッシュで管理するスラブのリストは、 空きありリストだけでかまいません。 そういえば、 もはや利用中のオブジェクトを残しておくことがないので、 キャッシュという呼び方はふさわしくありませんし、 スラブ・リストと呼び変えることにしましょう。 そうなると、 データ構造は次のようになるのでしょう。 さらに、 オブジェクトの型ではなく、 サイズ単位でスラブのリストを作ることにすると、 スラブのリストが何本必要かはあらかじめ求めておくことができるので、 スラブ・リストのヘッダの個数は固定されて動的に管理する必要がなくなります。

enum { PAGESIZE = 4096 };   // 物理ページサイズ、およびファイル・システムのブロックサイズの典型値

union slab_type {
    struct {
        slab_type* linkprev;         // 空きを持つスラブのリスト用リンク
        slab_type* linknext;
        std::size_t obj_size;        // オブジェクトのサイズ
        std::size_t count;           // スラブ内の割り当て中オブジェクト個数
        std::uint32_t* freecell;     // スラブ内のフリー・リストはオブジェクト
    } h;                             // 領域にリンクを置き、 バッファ・コントロール
    std::uint32_t u32[PAGESIZE / 4]; // を省きます。
    std::uint8_t u8[PAGESIZE];
};

struct slablist_type {
    slab_type* linkprev;             // 空きを持つスラブだけをリストにします
    slab_type* linknext;
    std::size_t obj_size;            // オブジェクトのサイズ slab の同名メンバの初期値
    std::size_t count;               // このサイズのオブジェクトの全割り当て個数
};