21日目までに仮想ページの割り当てと物理ページの割り当て・マッピングを実装してきました。今日は，このページレベルのメモリ管理機構を使って，ページよりも細かい単位でのメモリ割り当てを効率的に行うスラブアロケータを実装します。

スラブアロケータに移る前に，バグ（？）を直します。これまでのコードはNUMA-awareを前提で書いていたので，UMAの場合はコアゾーンのみしか利用できませんでした。UMAの場合は，NUMA-awareゾーンをすべてdomain=0として追加するように変更します。そのため，src/kernel/arch/x86_64/arch.cの_add_region_to_numa_zones()関数を以下のように変更します。

static void
_add_region_to_numa_zones(phys_memory_t *mem, acpi_t *acpi, uintptr_t base,
                          uintptr_t next)
{
    int i;
    uintptr_t s;
    uintptr_t t;
    int dom;

    if ( acpi->num_memory_region > 1 ) {
        for ( i = 0; i < acpi->num_memory_region; i++ ) {
            s = acpi->memory_domain[i].base;
            t = s + acpi->memory_domain[i].length;
            dom = acpi->memory_domain[i].domain;
            if ( base >= s && next <= t ) {
                /* Within the domain, then add this region to the buddy
                   system */
                phys_mem_buddy_add_region(mem->numazones[dom].heads,
                                          base + mem->p2v, next + mem->p2v);
            } else if ( base >= s ) {
                /* s <= base <= t < next */
                phys_mem_buddy_add_region(mem->numazones[dom].heads,
                                          base + mem->p2v, t + mem->p2v);
            } else if ( next <= t ) {
                /* base < s < next <= t */
                phys_mem_buddy_add_region(mem->numazones[dom].heads,
                                          s + mem->p2v, next + mem->p2v);
            }
        }
    } else {
        /* Non-NUMA (UMA) */
        phys_mem_buddy_add_region(mem->numazones[0].heads,
                                  base + mem->p2v, next + mem->p2v);
    }
}

elseブロックの範囲に記述したようにNon-NUMAのときに，domain=0に追加するようにしました。

スラブアロケータは，オブジェクト単位でメモリ領域を管理します。その実装の違いにより，Slab Allocatorの他，亜種としてSLUB (Unqueued Slab) Allocator，SLOB (Simple List of Blocks) Allocatorがあります。今回は単純なSlab Allocatorを実装します（ちゃんと違いを理解しているわけではないので違うかもしれないです……）。

まず，Slab Allocatorを実装する前に用語を説明します

• Cache: Cache（キャッシュ）は同一種類・同一サイズのオブジェクトを管理する単位です。キャッシュは複数のスラブで構成されます。Linuxで/proc/slabinfoを見たときにnameの列がCacheの種類を表します。
• Slab: Slab（スラブ）は連続したメモリ領域で，同一種類・同一サイズの複数のオブジェクトを含む領域です。

キャッシュとスラブとオブジェクトの関係をまとめると下図のようになります。

上図にも書いた通り，各キャッシュのスラブは以下の3種類のfree listで管理されます。

• オブジェクトが全て割り当てられていないスラブのリスト（Full）
• 一部のオブジェクトが割り当てられているスラブのリスト（Partial）
• 全てのオブジェクトが割り当て済みのスラブのリスト（Empty）

これを構造体で表すと，Slabヘッダは以下のように，連結リストの次のスラブへのポインタnext，属するキャッシュへのポインタcache，スラブ内に含まれるオブジェクト数nobjs，割り当て済みのオブジェクト数nused，オブジェクトの実体（配列）へのポインタobj_head，オブジェクトに関するフラグ配列marksで構成されます。Linuxなどでは，オブジェクトのオフセットを変えることで，セットアソシアティブ型のCPUキャッシュを効率的に使うという実装がされていますが，今回はそこまでは実装しません。おそらくそこまでこだわるのであれば，Linuxなどでも使われていないIntelのCache Allocation Technologyというキャッシュラインをコンテキスト毎に割り当てることのできる機能も使った方が良い気もします。

struct memory_slab_hdr {
    /* Pointer to the next slab header */
    memory_slab_hdr_t *next;
    /* Parent cache */
    memory_slab_cache_t *cache;
    /* The number of objects in this slab */
    int nobjs;
    /* The number of allocated objects */
    int nused;
    /* Pointer to the first object in this slab */
    void *obj_head;
    /* Free marks follows (nobjs byte) */
    uint8_t marks[0];
    /* Objects follow */
};

スラブキャッシュはこのスラブをfree list形式で管理します。スラブキャッシュの構造体memory_slab_cache_tでは，名前nameとオブジェクトサイズsizeこのfree list freelist，名前での検索のための二分木のポインタを定義します。

typedef struct {
    memory_slab_hdr_t *partial;
    memory_slab_hdr_t *full;
    memory_slab_hdr_t *empty;
} memory_slab_free_list_t;
struct memory_slab_cache {
    char name[MEMORY_SLAB_CACHE_NAME_MAX];
    size_t size;
    memory_slab_free_list_t freelist;
    /* Search tree */
    memory_slab_cache_t *left;
    memory_slab_cache_t *right;
};

このスラブアロケータの構造体として以下の構造体も定義します。memは昨日まで実装してきたページ単位のメモリ管理構造体でrootはスラブキャッシュの二分木のルートです。

typedef struct {
    memory_t *mem;
    memory_slab_cache_t *root;
} memory_slab_allocator_t;

src/kernel/memory.cも大きくなってきたので，スラブアロケータはsrc/kernel/slab.cに実装します。memory_slab_init()関数でスラブアロケータの初期化をします。初期化後にスラブキャッシュを作成するのですが，スラブキャッシュのサイズはページサイズよりも大幅に小さいオブジェクトなので，こちらもスラブで管理しようと思います。そのため，スラブアロケータの初期化時に，スラブキャッシュ構造体用にページ単位でメモリを割り当てて，それをスラブとして使い，このスラブキャッシュをオブジェクトとして割り当てます。これまでの物理メモリ・仮想メモリ管理のにわたま問題よりは，小さい単位で閉じるので，そこまで注意は必要無いですが，オブジェクトの割り当てとスラブの準備が循環参照にならないように注意して実装します。

まず，スラブアロケータのい初期化関数を定義します。仮想メモリアロケータとしてメモリ管理構造体memへのポインタをスラブアロケータで保持するようにします。

int
memory_slab_init(memory_slab_allocator_t *slab, memory_t *mem)
{
    int ret;

    slab->mem = mem;
    slab->root = NULL;

    /* Create a slab cache for slab cache */
    ret = _slab_cache_init(slab);
    if ( ret < 0 ) {
        return -1;
    }

    return 0;
}

前述した通り，スラブキャッシュもスラブオブジェクトとして実装します。そのため，その初期化だけは，以下の専用の関数を呼ぶことにします。方針としては，オブジェクトサイズsizeof(memory_slab_cache_t)の（今回は8ページ分の）スラブを_new_slab()関数で作成します。この関数は，仮想メモリからの割り当てにしか依存しないため，循環参照には他の関数とも共有します。スラブの割り当てに成功したら，作成したスラブからオブジェクトを一つ取り出し，それをスラブキャッシュとして，残りのスラブをこのキャッシュのpartial free listに追加します。最後に，このスラブキャッシュを名前で検索できるようにスラブアロケータの木構造のルートrootに追加します。_new_slab()および_add_slab_cache()の実装はsrc/kernel/slab.cを参照してください。

static int
_slab_cache_init(memory_slab_allocator_t *slab)
{
    memory_slab_hdr_t *s;
    memory_slab_cache_t *cache;
    int ret;

    /* Allocate one slab for the full free list */
    s = _new_slab(slab, sizeof(memory_slab_cache_t));
    if ( NULL == s ) {
        return -1;
    }

    /* Take the first object */
    s->marks[0] = 0;
    s->nused++;
    cache = s->obj_head;
    kstrlcpy(cache->name, MEMORY_SLAB_CACHE_NAME, MEMORY_SLAB_CACHE_NAME_MAX);
    cache->size = sizeof(memory_slab_cache_t);
    cache->freelist.partial = s;
    cache->freelist.full = NULL;
    cache->freelist.empty = NULL;
    cache->left = NULL;
    cache->right = NULL;
    s->cache = cache;

    /* Add to the cache tree */
    ret = _add_slab_cache(&slab->root, cache);
    kassert( ret == 0 );

    return 0;
}

メモリの割り当ては，スラブキャッシュのpartialまたはfullのfree listからスラブを取り出して，オブジェクトを割り当てるだけです。以下にその実装を掲載します。スラブヘッダーのmarksはオブジェクトが割り当てられていない場合に1を代入するビットマップですので，それを参照して空きオブジェクトを探します。このとき，fullまたはpartialが空の場合，初期化時にも使用した_new_slab()関数で新規のスラブ割り当てを試みます。最後に，オブジェクトを割り当てた後に，スラブのオブジェクト割り当てカウンタをインクリメントし，オブジェクト数と一致したらこちらをempty free listに移動します。

void *
memory_slab_alloc(memory_slab_allocator_t *slab, const char *name)
{
    memory_slab_cache_t *c;
    memory_slab_hdr_t *s;
    int i;
    void *obj;

    /* Find the slab cache corresponding to the name */
    c = _find_slab_cache(slab->root, name);
    if ( NULL == c ) {
        /* Not found */
        return NULL;
    }

    if ( NULL == c->freelist.partial && NULL == c->freelist.full ) {
        /* No object found, then try to allocate a new slab */
        s = _new_slab(slab, c->size);
        if ( NULL == s ) {
            /* Could not allocate a new slab */
            return NULL;
        }
        s->cache = c;
        c->freelist.full = s;
    }

    if ( NULL == c->freelist.partial ) {
        kassert( c->freelist.full != NULL );
        /* Take one full slab to the partial */
        c->freelist.partial = c->freelist.full;
        c->freelist.full = c->freelist.full->next;
    }

    /* Get an object */
    s = c->freelist.partial;
    obj = NULL;
    for ( i = 0; i < s->nobjs; i ++ ) {
        if ( s->marks[i] ) {
            /* Found a free object */
            obj = s->obj_head + c->size * i;
            s->marks[i] = 0;
            s->nused++;
            break;
        }
    }

    /* Check if the slab is still partial or becomes empty */
    if ( s->nused == s->nobjs ) {
        /* Move this partial slab to the empty free list */
        c->freelist.partial = s->next;
        s->next = c->freelist.empty;
        c->freelist.empty = s;
    }

    return obj;
}

オブジェクトの解放を行うmemory_slab_free()関数を実装します。コードは以下に掲載します。こちらの関数は，まず_find_slab_cache()関数で指定した名前のスラブキャッシュを検索します。次に，partialおよびempty free listからこのオブジェクトが属するスラブを検索します。検索は_find_slab_for_object()関数で行います。この関数の実装はsrc/kernel/slab.cを参照してください。見つかったスラブに対してオブジェクトのインデックスを計算し，marksビットマップの対応するエントリに1を代入してそのオブジェクトを解放します。解放後，emptyスラブであった場合は，partialリストに追加します。また，スラブの割り当てカウンタをデクリメントし，カウンタが0になっていったらfull free listに追加します。

void
memory_slab_free(memory_slab_allocator_t *slab, const char *name, void *obj)
{
    memory_slab_cache_t *c;
    memory_slab_hdr_t *s;
    int waspartial;
    memory_slab_hdr_t **head;
    uintptr_t off;
    int idx;

    /* Find the slab cache corresponding to the name */
    c = _find_slab_cache(slab->root, name);
    if ( NULL == c ) {
        /* Not found */
        return;
    }

    /* Search a slab containing the object */
    waspartial = 1;
    s = _find_slab_for_object(c, c->freelist.partial, obj);
    if ( NULL == s ) {
        /* Not found, then try to search empty list */
        waspartial = 0;
        s = _find_slab_for_object(c, c->freelist.empty, obj);
        if ( NULL == s ) {
            /* Not found */
            return;
        }
    }

    /* Calculate the offset and the index */
    off = obj - s->obj_head;
    idx = off / c->size;
    kassert( idx < s->nobjs );

    /* Mark as free */
    s->marks[idx] = 1;
    s->nused--;

    if ( !waspartial ) {
        /* Remove from emtpy, then add to the partial */
        head = &c->freelist.empty;
        while ( *head ) {
            if ( *head == s ) {
                /* Found, then remove s */
                *head = s->next;
                break;
            }
            head = &(*head)->next;
        }
        /* Add it to the partial list */
        s->next = c->freelist.partial;
        c->freelist.partial = s;
    }

    if ( s->nused == 0 ) {
        /* Remove from partial, then add to the full */
        head = &c->freelist.partial;
        while ( *head ) {
            if ( *head == s ) {
                /* Found, then remove s */
                *head = s->next;
                break;
            }
            head = &(*head)->next;
        }
        /* Add it to the full list */
        s->next = c->freelist.full;
        c->freelist.full = s;
    }
}

以下は，新規スラブキャッシュを作成する関数です。方針としては非常にシンプルで，最初に既存のスラブキャッシュとの重複確認ため，木構造から第二引数で指定したキャッシュを探す_find_slab_cache()関数を呼びます（こちらの実装はsrc/kernel/slab.cを参照してください）。重複していなければ，slab_cacheという名前のスラブキャッシュからオブジェクトの割り当てを行い，キャッシュの設定をします。スラブキャッシュのfree listはすべて空でも良いですが，スラブキャッシュを作成するということは，今後オブジェクトの割り当てが行われるはずなので，新規のスラブを_new_slab()関数で作成します。こちらで作成したスラブをfullのfree listに追加します（メモリ不足でスラブの作成に失敗してNULLが返ってきていてもこの時点では問題ないため，NULLチェックをせずにfree listに入れてしまっています）。ここまで終わったら，_add_slab_cache()を呼んで検索木に追加します。

int
memory_slab_create_cache(memory_slab_allocator_t *slab, const char *name,
                         size_t size)
{
    memory_slab_cache_t *cache;
    memory_slab_hdr_t *s;
    int ret;

    /* Duplicate check */
    cache = _find_slab_cache(slab->root, name);
    if ( NULL != cache ) {
        /* Already exists */
        return -1;
    }

    /* Try to allocate a memory_slab_cache_t from the named slab cache */
    cache = memory_slab_alloc(slab, MEMORY_SLAB_CACHE_NAME);
    if ( NULL == cache ) {
        return -1;
    }
    kstrlcpy(cache->name, name, MEMORY_SLAB_CACHE_NAME_MAX);
    cache->size = size;
    cache->freelist.partial = NULL;
    cache->freelist.full = NULL;
    cache->freelist.empty = NULL;
    cache->left = NULL;
    cache->right = NULL;

    /* Allocate one slab for the full free list */
    s = _new_slab(slab, size);
    s->cache = cache;
    cache->freelist.full = s;

    /* Add to the cache tree */
    ret = _add_slab_cache(&slab->root, cache);
    kassert( ret == 0 );

    return 0;
}

カーネル内でのメモリ割り当て関数kmalloc()用のスラブキャッシュを作成します。kmalloc()用のスラブキャッシュの名前はkmalloc-Nにします。Nには，オブジェクトのサイズを入れます。今回はN=8, 16, 32, 64, 96, 128, 192, 256, 512, 1024, 2048, 4096, 8192で作成します。初期化とkmalloc用のスラブキャッシュの作成はsrc/kernel/arch/x86_64/arch.cで実装しています（アーキテクチャ依存ではないので，そのうち移動したいです）。

    int i;
    static int kmalloc_sizes[] = { 8, 16, 32, 64, 96, 128, 192, 256, 512, 1024,
                                   2048, 4096, 8192 };
    char cachename[MEMORY_SLAB_CACHE_NAME_MAX];

    /* Initialize the slab allocator */
    ret = memory_slab_init(&kvar->slab, &kvar->mm);
    if ( ret < 0 ) {
        panic("Failed to initialize the slab allocator");
    }

    /* Initialize the kmalloc slab caches */
    for ( i = 0; i < (int)(sizeof(kmalloc_sizes) / sizeof(int)); i++ ) {
        ksnprintf(cachename, MEMORY_SLAB_CACHE_NAME_MAX, "kmalloc-%d",
                  kmalloc_sizes[i]);
        memory_slab_create_cache(&kvar->slab, cachename, kmalloc_sizes[i]);
    }

メモリの割り当て・解放テストをするために，いつものようにsrc/kernel/arch/x86_64/arch.cで以下のようなコードを書きました。

    /* Testing memory allocator */
    void *ptr;
    ptr = memory_slab_alloc(&kvar->slab, "kmalloc-64");
    print_hex(base, (uintptr_t)ptr, 8);
    base += 80;
    ptr = memory_slab_alloc(&kvar->slab, "kmalloc-64");
    print_hex(base, (uintptr_t)ptr, 8);
    base += 80;
    memory_slab_free(&kvar->slab, "kmalloc-64", ptr);
    ptr = memory_slab_alloc(&kvar->slab, "kmalloc-64");
    print_hex(base, (uintptr_t)ptr, 8);
    base += 80;

今日はスラブアロケータを実装しました。kmalloc()やkfree()関数自体はまだ実装できていませんが，スラブアロケータを使って簡単に実装できます。これでメモリ管理を一段落とさせて，残り2日でマルチタスクとシステムコールまわりの実装をしていこうと思います。