レガシーガジェット研究所

気になったことのあれこれ。

Linux Kernel ~ メモリ管理 スラブアロケータ編 ~

Linux Kernelを無限に読む会 ~ メモリ管理 Ver 2 ~

概要

「詳解Linux Kernel」を参考にVersion 2.6.11のコードリーディングをしていく。CPUのアーキテクチャは書籍に沿ってIntelx86とする。

引き続きはメモリ管理について見ていく。

概要

メモリ割り当てには基本的な単位としてページフレームを採用しており、数十バイトや数百バイトのメモリ割り当ての場合には無駄が生じてしまう。代替案として単一のページフレーム内に小さなメモリ領域を複数割り当てられるようにした。

スラブアロケータ

Solaris 2.4が初めて採用したスラブアロケータは以下のようなアルゴリズムで実装されている。

  • メモリ領域をデータ構造と関数を保持したオブジェクトとして扱い、オブジェクト毎にコンストラクタやデストラクタを保持する。初期処理の繰り返しを回避するため解放されたオブジェクトをすぐには破棄せず、新しいオブジェクトの要求に対してそのオブジェクトを使い回す。
  • カーネルは同じ種類のメモリ領域を繰り返し要求する傾向がある(プロセスを生成する時などに必要なプロセスディスクリプタやファイルディスクリプタテーブルなど)。同じ用途で使用されていたメモリは再利用することが可能なので、割り当てと解放を繰り返し行う必要がなく効率的にキャッシュすることができる。
  • 頻繁に要求されるオブジェクトに関しては予め複数個余分に作成しておくことで、メモリの断片化を避け効率化を測る。要求頻度の低いオブジェクトに関しては32バイトから132056バイトまで(2のべき乗毎)の13種類のメモリ領域リストから最も適切なサイズのメモリ領域を割り当てる。
  • バディアロケータの呼び出し回数を減らすことでハードウェアキャッシュの効率化が行われる。

スラブアロケータは同じ種類のオブジェクトをまとめて単一のキャッシュとして管理する。キャッシュ用のメモリ領域は複数のスラブ(未使用 or 部分的に使用中 or 使用中)に分割されており、各スラブには1つ以上の連続したページフレームが存在しオブジェクトが含まれる。

詳解 Linuxカーネル 第3版

キャッシュディスクリプタ

各キャッシュはkmem_cache_t構造体変数(キャッシュディスクリプタ)で表現される。

// include/linux/slab.h
typedef struct kmem_cache_s kmem_cache_t;

// mm/slab.c   
struct kmem_cache_s {
    struct array_cache *array[NR_CPUS]; /* 空きオブジェクト毎のローカルキャッシュへのポインタ。CPU毎に存在 */
    unsigned int      batchcount; /* ローカルキャッシュへ一度に行う、割り当て又は解放するオブジェクトの数 */
    unsigned int      limit; /* ローカルキャッシュ内に存在する空きオブジェクトの最大数。*/
    
    struct kmem_list3  lists; /* スラブリスト */
    unsigned int      objsize; /* キャッシュ内のオブジェクトのサイズ */
    unsigned int      flags;  /* キャッシュ内の静的属性 */
    unsigned int      num;    /* 1つのスラブ内にあるオブジェクトの数(単一のスラブ内に存在するオブジェクトサイズは同じ) */
    unsigned int      free_limit; /* スラブキャッシュ全体が保持可能なオブジェクトの最大数 */
    spinlock_t      spinlock; /* ロック用変数 */

    unsigned int      gfporder; /* 単一のスラブで必要となる連続するページフレーム数(2を底とする対数) */

    unsigned int      gfpflags; /* ページフレームを要求する際にバディシステムに指定するフラグ */

    size_t         colour;     /* スラブの色の数 */
    unsigned int      colour_off; /* メモリ境界のサイズ(基本的にはハードウェアキャッシュラインのサイズ) */
    unsigned int      colour_next;    /* 次に割り当てるスラブの色 */
    kmem_cache_t        *slabp_cache; /* スラブディスクリプタが配置されている汎用スラブキャッシュへのポインタ */
    unsigned int      slab_size; /* スラブディスクリプタ及び単一のスラブに含まれる全てのオブジェクトディスクリプタを足したものをメモリ境界に合わせたサイズ */
    unsigned int      dflags;     /* キャッシュの動的属性を表すフラグ */

    void (*ctor)(void *, kmem_cache_t *, unsigned long); /* コンストラクタ */

    void (*dtor)(void *, kmem_cache_t *, unsigned long); /* デストラクタ */

/* 4) cache creation/removal */
    const char        *name; /* スラブキャッシュ名 */
    struct list_head   next; /* キャッシュディスクリプタの双方向リスト */
    
/* 5) statistics */
    :
};

スラブのリストであるkmem_list3構造体は以下のように定義されている。

// mm/slab.c
struct kmem_list3 {
    struct list_head   slabs_partial; /* 部分的に使用中のオブジェクトを持つスラブディスクリプタ用の双方向リスト */
    struct list_head   slabs_full; /* 使用中オブジェクトを持つスラブディスクリプタ用の双方向リスト */
    struct list_head   slabs_free; /* 空きオブジェクトを持つスラブディスクリプタ用の双方向リスト */
    unsigned long free_objects; /* スラブ内の空きオブジェクトの数 */
    int        free_touched;
    unsigned long next_reap;
    struct array_cache *shared; /* ローカルキャッシュへのポインタ */
};

スラブディスクリプタ

キャッシュ中に存在する各スラブ(未使用 or 部分的に使用中 or 使用中)はslab構造体変数で表現される。

// mm/slab.c
struct slab {
    struct list_head   list; /* kmem_list3構造体のslabs_partial, slabs_fullまたはslabs_freeのいずれかのリスト */
    unsigned long     colouroff; /* スラブ内の先頭オブジェクトへのオフセット */
    void           *s_mem; /* スラブ内の先頭オブジェクト */
    unsigned int      inuse; /* スラブ内の使用中オブジェクト数 */
    kmem_bufctl_t       free; /* スラブ内の先頭空きオブジェクトへのインデックス */
};

スラブディスクリプタは以下の2つの箇所に配置することが可能。

場所 説明
外部スラブディスクリプタ スラブディスクリプタをスラブ外へ配置する。ISAのDMA転送に使用できず汎用キャッシュの1つに置かれており、malloc_sizes変数が指している。
内部スラブディスクリプタ スラブディスクリプタをスラブに割り当てたページフレームの先頭に配置する。

スラブアロケータは以下の場合に"内部スラブディスクリプタ"を選択する。

  • スラブオブジェクトのサイズが512バイトよりも小さい場合
  • スラブ内のバイト単位のメモリ断片が十分に大きくスラブディスクリプタ及びオブジェクトディスクリプタが配置可能な場合

外部ディスクリプタ方式を選択した場合キャッシュディスクリプタ(kmem_cache_t)のflagsメンバにCFLGS_OFF_SLABフラグがセットされる。

キャッシュディスクリプタ及びスラブディスクリプタの関係は以下。

詳解 Linuxカーネル 第3版

汎用キャッシュ及び特定の用途で用いられるキャッシュ

汎用キャッシュはスラブアロケータだけが使用し、特定の用途で用いられるキャッシュはカーネルの他の箇所からも使用される。

汎用キャッシュは以下の2つ。

  • kmem_cacheと呼ばれるスラブキャッシュ。カーネルが使用するキャッシュディスクリプタをそのオブジェクト内に格納する。kmem_cache_t構造体のcache_chace変数が保持している。
// mm/slab.c
/* internal cache of cache description objs */
static kmem_cache_t cache_cache = {
    .lists      = LIST3_INIT(cache_cache.lists),
    .batchcount = 1,
    .limit      = BOOT_CPUCACHE_ENTRIES,
    .objsize    = sizeof(kmem_cache_t),
    .flags      = SLAB_NO_REAP,
    .spinlock   = SPIN_LOCK_UNLOCKED,
    .name       = "kmem_cache",
#if DEBUG
    .reallen    = sizeof(kmem_cache_t),
#endif
};
  • 汎用スラブキャッシュ。13種類(32,64,128,256,512,1024,2048,4096,8192,16384,32767,65536,131072)のサイズのキャッシュを、それぞれIASのDMA転送用とそれ以外で2つずつ、計26個のキャッシュディスクリプタmalloc_sizes配列変数が保持している。
// mm/slab.c
struct cache_sizes malloc_sizes[] = {
#define CACHE(x) { .cs_size = (x) },
#include <linux/kmalloc_sizes.h>
    { 0, }
#undef CACHE
};

// include/linux/slab.h
/* Size description struct for general caches. */
struct cache_sizes {
    size_t      cs_size;
    kmem_cache_t    *cs_cachep;
    kmem_cache_t    *cs_dmacachep;
};

// include/linux/kmalloc_sizes.h
#if (PAGE_SIZE == 4096)
    CACHE(32)
#endif
    CACHE(64)
#if L1_CACHE_BYTES < 64
    CACHE(96)
#endif
    CACHE(128)
#if L1_CACHE_BYTES < 128
    CACHE(192)
#endif
    CACHE(256)
    CACHE(512)
    CACHE(1024)
    CACHE(2048)
    CACHE(4096)
    CACHE(8192)
    CACHE(16384)
    CACHE(32768)
    CACHE(65536)
    CACHE(131072)

汎用スラブキャッシュの名前はcache_names構造体のcache_names配列変数で管理されており以下のように定義されている。

// mm/slab.c
struct cache_names {
    char *name;
    char *name_dma;
};

static struct cache_names __initdata cache_names[] = {
#define CACHE(x) { .name = "size-" #x, .name_dma = "size-" #x "(DMA)" },
#include <linux/kmalloc_sizes.h>
    { NULL, }
#undef CACHE
};

サイズ毎に別の名前が一時的に定義されたマクロによって設定されているのがわかる。

汎用キャッシュの初期化

// mm/slab.c

static struct semaphore cache_chain_sem; // セマフォ用変数
static struct list_head cache_chain; // キャッシュリスト

void __init kmem_cache_init(void)
{
    size_t left_over;
    struct cache_sizes *sizes;
    struct cache_names *names;

    /* 特定用途のスラブキャッシュを初期化 */
    init_MUTEX(&cache_chain_sem); // セマフォの初期化
    INIT_LIST_HEAD(&cache_chain); // リストの初期化
    list_add(&cache_cache.next, &cache_chain); // 特定用途キャッシュをリストに接続
    cache_cache.colour_off = cache_line_size(); // キャッシュラインサイズ
    cache_cache.array[smp_processor_id()] = &initarray_cache.cache; // 初期化したキャッシュを設定
    cache_cache.objsize = ALIGN(cache_cache.objsize, cache_line_size()); // キャッシュサイズをキャッシュラインにアラインメント
    cache_estimate(0, cache_cache.objsize, cache_line_size(), 0,
                &left_over, &cache_cache.num); // オブジェクトの個数を計算
    cache_cache.colour = left_over/cache_cache.colour_off; // 色を決定
    cache_cache.colour_next = 0;
    cache_cache.slab_size = ALIGN(cache_cache.num*sizeof(kmem_bufctl_t) +
                sizeof(struct slab), cache_line_size()); // スラブサイズを設定

    /* kmallocキャッシュの作成 */
    sizes = malloc_sizes; // 汎用スラブキャッシュの配列
    names = cache_names;

    /* スラブキャッシュをトラバース */
    while (sizes->cs_size) {
        /* キャッシュの作成 */
        sizes->cs_cachep = kmem_cache_create(names->name,
            sizes->cs_size, ARCH_KMALLOC_MINALIGN,
            (ARCH_KMALLOC_FLAGS | SLAB_PANIC), NULL, NULL);

        /* 内部スラブの場合 */
        if (!(OFF_SLAB(sizes->cs_cachep))) {
            offslab_limit = sizes->cs_size-sizeof(struct slab);
            offslab_limit /= sizeof(kmem_bufctl_t);
        }

        /* DMA転送用キャッシュの作成 */
        sizes->cs_dmacachep = kmem_cache_create(names->name_dma,
            sizes->cs_size, ARCH_KMALLOC_MINALIGN,
            (ARCH_KMALLOC_FLAGS | SLAB_CACHE_DMA | SLAB_PANIC),
            NULL, NULL);

        /* ポインタを次の要素へ */
        sizes++;
        names++;
    }
    
    {
        void * ptr;
        
        ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
        local_irq_disable(); // スピンロック
        memcpy(ptr, ac_data(&cache_cache), sizeof(struct arraycache_init)); // array_cache -> arraycache_initにデータ構造体を置き換える
        cache_cache.array[smp_processor_id()] = ptr;
        local_irq_enable(); // スピンロック解除
    
        ptr = kmalloc(sizeof(struct arraycache_init), GFP_KERNEL);
        local_irq_disable(); // スピンロック
        memcpy(ptr, ac_data(malloc_sizes[0].cs_cachep),
                sizeof(struct arraycache_init)); // array_cache -> arraycache_initにデータ構造体を置き換える
        malloc_sizes[0].cs_cachep->array[smp_processor_id()] = ptr;
        local_irq_enable(); // スピンロック解除
    }

    {
        kmem_cache_t *cachep;
        down(&cache_chain_sem); // セマフォを取得
        list_for_each_entry(cachep, &cache_chain, next)
            enable_cpucache(cachep); // キャッシュに包含可能なオブジェクト数を設定
        up(&cache_chain_sem); // セマフォを解放
    }

    g_cpucache_up = FULL; // キャッシュのステータスを更新

    register_cpu_notifier(&cpucache_notifier); // コールバック関数の設定
}

汎用キャッシュの解放

キャッシュの解放はkmem_cache_destroy()で行い、カーネルモジュールのアンロードなどからコールされることを想定している。

// mm/slab.c
/**
 * キャッシュディスクリプタを解放
 */
int kmem_cache_destroy (kmem_cache_t * cachep)
{
    int i;

    lock_cpu_hotplug(); // CPU用のセマフォを取得

    down(&cache_chain_sem); // キャッシュリストのセマフォを取得

    list_del(&cachep->next);
    up(&cache_chain_sem); // キャッシュリストのセマフォを解放

    if (__cache_shrink(cachep)) { // 定義は以下
        :

/* キャッシュディスクリプタに対応するスラブを解放 */
static int __cache_shrink(kmem_cache_t *cachep)
{
    struct slab *slabp;
    int ret;

    drain_cpu_caches(cachep);

    check_irq_on();
    spin_lock_irq(&cachep->spinlock);

    for(;;) { // 未使用リストをトラバース(全ての解放されているべき)
        struct list_head *p;

        p = cachep->lists.slabs_free.prev;
        if (p == &cachep->lists.slabs_free) // 全て解放し終えた
            break;

        slabp = list_entry(cachep->lists.slabs_free.prev, struct slab, list);
        list_del(&slabp->list);

        cachep->lists.free_objects -= cachep->num; // 未使用オブジェクト数をデクリメント
        spin_unlock_irq(&cachep->spinlock);
        slab_destroy(cachep, slabp); // 定義は以下
        :

/* 
 * スラブに対応するオブジェクトを解放
 */
static void slab_destroy (kmem_cache_t *cachep, struct slab *slabp)
{
    :

スラブアロケータのページフレーム取得及び解放処理

スラブアロケータがスラブを作成する際は、ゾーン毎のページフレームアロケータを呼び出し連続するページフレームを取得する。当該処理はkmem_getpages()関数が行う。

// mm/slab.c
/*
 * cachep: キャッシュディスクリプタ
 * flags: ページフレームの要求方法を指定
 * nodeid: NUMAアーキテクチャの場合にノードの指定に使用する
 */
static void *kmem_getpages(kmem_cache_t *cachep, int flags, int nodeid)
{
    struct page *page;
    void *addr;
    int i;

    flags |= cachep->gfpflags;
    if (likely(nodeid == -1)) { // UMAアーキテクチャ
        page = alloc_pages(flags, cachep->gfporder); // ページの取得
    } else { // NUMAアーキテクチャ
        page = alloc_pages_node(nodeid, flags, cachep->gfporder); // ページの取得
    }
    if (!page) // ページフレームの取得に失敗
        return NULL;
    addr = page_address(page); // ページディスクリプタをアドレスに変換

    i = (1 << cachep->gfporder); // 取得したページフレーム数を算出
    if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
        atomic_add(i, &slab_reclaim_pages); // ユーザから要求があった際に回収可能なページフレーム数を増やす
    add_page_state(nr_slab, i);
    while (i--) {
        SetPageSlab(page); // ページフレームをスラブとして設定
        page++;
    }
    return addr;
}

// include/linux/page-flags.h
#define SetPageSlab(page)  set_bit(PG_slab, &(page)->flags)

スラブに割り当てたページフレームの回収にはkmem_freepages()関数を使用する。

// mm/slab.c
static void kmem_freepages(kmem_cache_t *cachep, void *addr)
{
    unsigned long i = (1<<cachep->gfporder); // ページフレーム数を算出
    struct page *page = virt_to_page(addr); // アドレスに対応するページディスクリプタを取得
    const unsigned long nr_freed = i;

    while (i--) { // 解放するページフレームをトラバース
        if (!TestClearPageSlab(page)) // PG_slabフラグを解除
            BUG();
        page++; // 次のページへ
    }
    sub_page_state(nr_slab, nr_freed);
    if (current->reclaim_state)
        current->reclaim_state->reclaimed_slab += nr_freed;
    free_pages((unsigned long)addr, cachep->gfporder); // ページフレームの解放
    if (cachep->flags & SLAB_RECLAIM_ACCOUNT)
        atomic_sub(1<<cachep->gfporder, &slab_reclaim_pages); // 回収可能なページフレーム数を減らす
}

// include/linux/page-flags.h
#define TestClearPageSlab(page)    test_and_clear_bit(PG_slab, &(page)->flags)

キャッシュへのスラブの割り当て及び解放

新たに作成したキャッシュはスラブ及び空きオブジェクトを保持していない。カーネルは以下の場合に新たなスラブをキャッシュに割り当てる。

  • 新しいオブジェクトの割り当てを要求された場合
  • キャッシュが空きオブジェクトを保持していない場合

上記の両方の条件を満たす場合にはスラブアロケータはcache_grow()関数を呼び出す。キャッシュディスクリプタに対してページフレームを確保し、(設定されていれば)コンストラクタや管理での初期化や管理部ジェクトの配置などを行う。

// mm/slab.c
static int cache_grow (kmem_cache_t * cachep, int flags, int nodeid)
{
    struct slab    *slabp;
    void       *objp;
    size_t      offset;
    int         local_flags;
    unsigned long  ctor_flags;

    ctor_flags = SLAB_CTOR_CONSTRUCTOR;
    local_flags = (flags & SLAB_LEVEL_MASK);
    if (!(local_flags & __GFP_WAIT)) // スリープが不可能
        ctor_flags |= SLAB_CTOR_ATOMIC; // コンストラクタにスリープできないことを知らせる

    check_irq_off();
    spin_lock(&cachep->spinlock); // キャッシュのロックを取得

    offset = cachep->colour_next; // 色の取得
    cachep->colour_next++; // 次の色へ
    if (cachep->colour_next >= cachep->colour)
        cachep->colour_next = 0;
    offset *= cachep->colour_off;

    spin_unlock(&cachep->spinlock); // キャッシュをアンロック

    if (local_flags & __GFP_WAIT) // スリープが可能な場合
        local_irq_enable(); // スピンロックを取得

    if (!(objp = kmem_getpages(cachep, flags, nodeid))) // ページフレームを取得
        goto failed;

    if (!(slabp = alloc_slabmgmt(cachep, objp, offset, local_flags))) // 管理用オブジェクトを作成
        goto opps1;

    set_slab_attr(cachep, slabp, objp); // スラブにオブジェクトを接続する

    cache_init_objs(cachep, slabp, ctor_flags); // コンストラクタでオブジェクトを初期化する

    if (local_flags & __GFP_WAIT)
        local_irq_disable();
    check_irq_off();
    spin_lock(&cachep->spinlock); // キャッシュのロックを取得

    list_add_tail(&slabp->list, &(list3_data(cachep)->slabs_free));
    STATS_INC_GROWN(cachep);
    list3_data(cachep)->free_objects += cachep->num; // 未使用オブジェクト数を加算
    spin_unlock(&cachep->spinlock); // 
    return 1;
opps1: // 失敗した
    kmem_freepages(cachep, objp); // ページフレームの解放
failed:
    if (local_flags & __GFP_WAIT)
        local_irq_disable(); // スピンロックの解除
    return 0;
}

以下に示すいれずかの場合にキャッシュからスラブを解放する。

  • スラブキャッシュの空きオブジェクトが多すぎる場合
  • 定期的なタイマによって空きオブジェクトだけを持つスラブを解放する場合

slab_destroy()がスラブ内の全てのページフレーム(オブジェクト)をページアロケータに解放する。

// mm/slab.c
static void slab_destroy (kmem_cache_t *cachep, struct slab *slabp)
{
    void *addr = slabp->s_mem - slabp->colouroff;
    
    if (cachep->dtor) { // デストラクタが設定されている場合
        int i;
        for (i = 0; i < cachep->num; i++) {
            void* objp = slabp->s_mem+cachep->objsize*i; // オブジェクトを取得
            (cachep->dtor)(objp, cachep, 0); // デストラクタを実行
        } 
    }
    
    /* RCUによってスラブが削除された場合 */
    if (unlikely(cachep->flags & SLAB_DESTROY_BY_RCU)) {
        struct slab_rcu *slab_rcu;

        slab_rcu = (struct slab_rcu *) slabp;
        slab_rcu->cachep = cachep;
        slab_rcu->addr = addr;
        call_rcu(&slab_rcu->head, kmem_rcu_free);
    } else {
        kmem_freepages(cachep, addr); // ページフレームを解放
        if (OFF_SLAB(cachep)) // 外部スラブの場合
            kmem_cache_free(cachep->slabp_cache, slabp);
    }
}

オブジェクトディスクリプタ

スラブとオブジェクトの関係は以下のようになっており、スラブディスクリプタの後ろにオブジェクトディスクリプタの配列が格納されている(スラブディスクリプタの配置位置によって、オブジェクトディスクリプタの配置位置も決定する)

詳解 Linuxカーネル 第3版

オブジェクトディスクリプタkmem_bufctl_t型のディスクリプタで表現され、オブジェクトディスクリプタ配列の各要素は、スラブ内に存在する各オブジェクトに対応する。

// include/asm-i386/types.h
typedef unsigned short kmem_bufctl_t;

空きオブジェクトは単方向リストを形成しており、オブジェクトディスクリプタは次の空きオブジェクトのインデックス値となっている(そのためオブジェクトが未使用の場合にのみ機能する)。最後の要素にはBUFCTL_ENDが設定される。

// mm/slab.c
#define BUFCTL_END (((kmem_bufctl_t)(~0U))-0)

オブジェクトのアラインメント

スラブアロケータが管理するオブジェクトはページ長(大抵の場合は4096バイト = 低位12bit)でアラインメントされる。通常アクセス対象のデータがワード長(メモリバスの幅)であるとプロセッサはより早くアクセスが可能となる。

kmem_cache_create()関数では指定がない場合、オブジェクトをワード長(BYTES_PER_WORD)に切り上げ、SLAB_HWCACHE_ALIGNの指定があればハードウェアの一次キャッシュサイズへのアラインメントを行う。

kmem_cache_t *
kmem_cache_create (const char *name, size_t size, size_t align,
    unsigned long flags, void (*ctor)(void*, kmem_cache_t *, unsigned long),
    void (*dtor)(void*, kmem_cache_t *, unsigned long))
{
    size_t left_over, slab_size, ralign;
    kmem_cache_t *cachep = NULL;
    :
    /* calculate out the final buffer alignment: */
    if (flags & SLAB_HWCACHE_ALIGN) {
        ralign = cache_line_size();
        while (size <= ralign/2)
            ralign /= 2;
    } else {
        ralign = BYTES_PER_WORD;
    }
    :
}

// mm/slab.c
#define    BYTES_PER_WORD      sizeof(void *)

キャッシュラインに合わせることはアクセス性能の向上に貢献するが、メモリのフラグメンテーションを促進させることとなるため、トレードオフの関係が生じていると言える。

スラブの色

単一のハードウェアキャッシュラインは複数のアドレスに対応している。そのため同じサイズのオブジェクトや同じオフセットに配置されたオブジェクトは比較的高い確率で同じキャッシュラインにマッピングされる。これの回避策としてスラブに色付けを行う。その色を元にメモリアロケータはオブジェクトを異なるリニアアドレスに分散させることでハードウェアキャッシュの性能を最大限に引き出す。

スラブがcolという色を持つ場合にはスラブとオブジェクトの配置は以下のようになる。

詳解 Linuxカーネル 第3版

  • col: 色
  • aln: メモリ境界
  • dsize: スラブディスクリプタのサイズ
  • osize: オブジェクトのサイズ
  • free: スラブ内の未使用バイト数
  • num: スラブ内に配置可能なオブジェクト数

同じ種類のオブジェクトを持つスラブには異なる色を設定することで各スラブの先頭オブジェクトの配置位置をズラし、同じキャッシュラインの奪い合いを回避させる。色の数はfree/alnとなるためfreeの値が十分に大きい場合のみ機能する。

スラブオブジェクトのローカルキャッシュ

プロセッサ間のスピンロックを減らしハードウェアキャッシュを有効に活用するため、スラブアロケータはローカルキャッシュを保持している。このキャッシュは空きオブジェクトへのポインタ配列となっており、スラブの割り当てと解放の大半はこのキャッシュに対するものとなる。

前述のキャッシュディスクリプタ(kmem_cache_t)のarrayメンバがローカルキャッシュとなっており、プロセッサの個数分の要素を保持する配列となっていることがわかる。

// include/linux/slab.h
typedef struct kmem_cache_s kmem_cache_t;

// mm/slab.c
struct kmem_cache_s {
    struct array_cache *array[NR_CPUS]; /* 空きオブジェクト毎のローカルキャッシュへのポインタ。CPU毎に存在 */
    
    :
    
    struct kmem_list3  lists; /* スラブリスト */

array_cache構造体は以下のように定義されている。

// mm/slab.c
struct array_cache {
    unsigned int avail; /* 使用可能なオブジェクトのポインタ数*/
    unsigned int limit; /* ローカルキャッシュ(ポインタ配列)のサイズ */
    unsigned int batchcount; /* 一度に処理するローカルキャッシュ内のオブジェクト数 */
    unsigned int touched; /* 直近でローカルキャッシュを使用しているかどうか */
};

上記からもわかる通りローカルキャッシュ自体にポインタ配列はなく、このディスクリプタの直後にポインタ配列が存在する。ポインタが参照するオブジェクトのキャッシュ自体は他のオブジェクト同様スラブ内に存在する。

マルチプロセッサ環境のスラブアロケータは、キャッシュディスクリプタlistメンバにもローカルキャッシュを保持しており、array_cache構造体のsharedメンバがローカルキャッシュへのポインタとなっている。

// mm/slab.c
struct kmem_list3 {
    :
    struct array_cache *shared; /* ローカルキャッシュへのポインタ */
};

sharedの名前の通り、この共有ローカルキャッシュと呼ばれるキャッシュは全てのCPUで共有され、CPU間での空きオブジェクトの移動を可能としている。

スラブオブジェクトの割り当てと解放

割り当てにはkmem_cache_alloc()を使用する。第一引数であるcachepは割り当てるキャッシュを、第二引数のflagsにはキャッシュ内のスラブが存在しなかった場合にゾーン内のページアロケータに渡すフラグを指定する。

// mm/slab.c

/**
 * kmem_cache_alloc - Allocate an object
 * @cachep: The cache to allocate from.
 * @flags: See kmalloc().
 *
 * Allocate an object from this cache.  The flags are only relevant
 * if the cache has no available objects.
 */
void * kmem_cache_alloc (kmem_cache_t *cachep, int flags)
{
    return __cache_alloc(cachep, flags);
}

static inline void * __cache_alloc (kmem_cache_t *cachep, int flags)
{
    unsigned long save_flags;
    void* objp;
    struct array_cache *ac;

    local_irq_save(save_flags); // 割り込みを禁止
    ac = ac_data(cachep); // カレントプロセッサに対応する空きオブジェクトのローカルキャッシュ情報へのポインタを取得
    
    // 使用可能なオブジェクトが存在する場合
    if (likely(ac->avail)) { 
        ac->touched = 1; // 最近ローカルキャッシュを使用したことを示すフラグを立てる
        
        // availをインデックスに利用可能なローカルキャッシュを取得する
        objp = ac_entry(ac)[--ac->avail];
        
    // 使用可能なオブジェクトが存在しない場合
    } else {
        objp = cache_alloc_refill(cachep, flags);
    }
    local_irq_restore(save_flags); // 割り込みを許可
    return objp;
}

// カレントプロセッサに対応する空きオブジェクトのローカルキャッシュ情報へのポインタを取得
static inline struct array_cache *ac_data(kmem_cache_t *cachep)
{
    // カレントプロセッサ番号をインデックスに要素を取得する
    return cachep->array[smp_processor_id()];
}

// array_cache直後に配置されている実際のローカルキャッシュへのポインタ配列を取得する
static inline void ** ac_entry(struct array_cache *ac)
{
    // array_cache直後の値をポインタとして、その参照先を
    // ローカルキャッシュとして扱っていることから、前述の通り
    // array_cacheの直後にローカルキャッシュへのポインタ配列が
    // 配置されていることがわかる。
    return (void**)(ac+1);
}

大抵の場合キャッシュにヒットしローカルキャッシュから空きオブジェクトを取得する。ヒットしなかった場合にはcache_alloc_refill()が呼び出される。

// mm/slab.c
static void* cache_alloc_refill(kmem_cache_t* cachep, int flags)
{
    int batchcount;
    struct kmem_list3 *l3;
    struct array_cache *ac;

    check_irq_off(); // 割り込みが禁止されているかを確認
    ac = ac_data(cachep); // ローカルキャッシュ情報を取得
retry:
    batchcount = ac->batchcount; // 一度に処理するローカルキャッシュの数を取得
    if (!ac->touched && batchcount > BATCHREFILL_LIMIT) { // 最大数よりも多い場合
        /* if there was little recent activity on this
        * cache, then perform only a partial refill.
        * Otherwise we could generate refill bouncing.
        */
        batchcount = BATCHREFILL_LIMIT; // 一度に処理するローカルキャッシュ数を最大値まで減らす
    }
    l3 = list3_data(cachep); // スラブのリストを取得

    BUG_ON(ac->avail > 0); // 使用可能数が0以上の場合 == バグ
    spin_lock(&cachep->spinlock); // スピンロックを取得

    if (l3->shared) { // CPU間で共有しているキャッシュが存在する
        struct array_cache *shared_array = l3->shared; // CPU間で共有しているキャッシュにアクセス
        if (shared_array->avail) { // 利用可能である場合

            if (batchcount > shared_array->avail) // 利用可能数が一度に処理する数よりも下回る場合
                batchcount = shared_array->avail; // 利用可能数を処理対象に設定
            
            shared_array->avail -= batchcount; //  取得数を利用可能数から差し引く
            ac->avail = batchcount; // ローカルキャッシュ利用可能数を増やす
            
            // CPU間の共有ローカルキャッシュからカレントプロセッサのローカルキャッシュにコピー
            memcpy(ac_entry(ac), &ac_entry(shared_array)[shared_array->avail],
                    sizeof(void*)*batchcount);

            shared_array->touched = 1; // 最近キャッシュにアクセスしたことを記録
            goto alloc_done;
        }
    }

    // CPU間で共有しているキャッシュが存在しなかった場合
    while (batchcount > 0) {
        struct list_head *entry;
        struct slab *slabp;

        /* Get slab alloc is to come from. */
        entry = l3->slabs_partial.next; // 一部使用済みのオブジェクトを持つスラブにアクセス
        if (entry == &l3->slabs_partial) { // 空きがない場合
            l3->free_touched = 1; // 未使用のオブジェクトだけを持つスラブにアクセス
            entry = l3->slabs_free.next;
            if (entry == &l3->slabs_free) // 空きがない場合
                goto must_grow; // スラブを確保する処理へ
        }

        slabp = list_entry(entry, struct slab, list); // リストからスラブを取得
        check_slabp(cachep, slabp);
        check_spinlock_acquired(cachep);

        while (slabp->inuse < cachep->num && batchcount--) {
            kmem_bufctl_t next;

            // 統計情報を更新
            STATS_INC_ALLOCED(cachep);
            STATS_INC_ACTIVE(cachep);
            STATS_SET_HIGH(cachep);

            /* 空きオブジェクトへのポインタを取得 */
            ac_entry(ac)[ac->avail++] = slabp->s_mem + slabp->free*cachep->objsize;

            slabp->inuse++; // 使用数を更新
            next = slab_bufctl(slabp)[slabp->free];
#if DEBUG
            slab_bufctl(slabp)[slabp->free] = BUFCTL_FREE;
#endif
                slabp->free = next;
        }
        check_slabp(cachep, slabp);

        /* スラブを適切なリストに繋ぐ */
        list_del(&slabp->list);
        if (slabp->free == BUFCTL_END)
            list_add(&slabp->list, &l3->slabs_full); // 全て使用中のリスト
        else
            list_add(&slabp->list, &l3->slabs_partial); // 一部使用中のリスト
    }

must_grow:
    l3->free_objects -= ac->avail; // フリーオブジェクトから使用可能なオブジェクト数を減算
alloc_done:
    spin_unlock(&cachep->spinlock); // スピンロックを解放

    // 利用可能なローカルキャッシュが存在しない場合
    if (unlikely(!ac->avail)) {
        int x;
        x = cache_grow(cachep, flags, -1); // スラブ内のキャッシュを増加させる
        
        // cache_grow can reenable interrupts, then ac could change.
        ac = ac_data(cachep); // ローカルキャッシュを再度取得
        if (!x && ac->avail == 0) // cahce_grow()に失敗
            return NULL;

        if (!ac->avail) // 有効なキャッシュがない
            goto retry; // 再度取得を試みる
    }
    ac->touched = 1; // 最近キャッシュにアクセスしたことを示す
    return ac_entry(ac)[--ac->avail]; // 取得したローカルキャッシュから取得
}

解放にはkmem_cache_free()を使用する。引数にはキャッシュとオブジェクトを指定する。

// mm/slab.c
/**
 * kmem_cache_free - Deallocate an object
 * @cachep: The cache the allocation was from.
 * @objp: The previously allocated object.
 *
 * Free an object which was previously allocated from this
 * cache.
 */
void kmem_cache_free (kmem_cache_t *cachep, void *objp)
{
    unsigned long flags;

    local_irq_save(flags); // 割り込みを禁止
    __cache_free(cachep, objp);
    local_irq_restore(flags); // ステータスレジスタの値をリストアする(ネストしていない場合は割り込みを許可
}

上記では割り込みを禁止し__cache_free()を呼び出している。

__cache_free()は以下のように定義されている。

// mm/slab.c
/*
 * __cache_free
 * Release an obj back to its cache. If the obj has a constructed
 * state, it must be in this state _before_ it is released.
 *
 * Called with disabled ints.
 */
static inline void __cache_free (kmem_cache_t *cachep, void* objp)
{
    struct array_cache *ac = ac_data(cachep); // ローカルキャッシュを取得

    check_irq_off(); // スピンロックを確認
    objp = cache_free_debugcheck(cachep, objp, __builtin_return_address(0));

    // ローカルキャッシュに利用可能なオブジェクトとして戻すことができる場合
    if (likely(ac->avail < ac->limit)) { 
        STATS_INC_FREEHIT(cachep); // 統計情報の更新
        ac_entry(ac)[ac->avail++] = objp; // 解放対象のオブジェクトを利用可能オブジェクトの配列に繋ぐ
        return;
    } else {
        STATS_INC_FREEMISS(cachep); // 統計情報の更新
        cache_flusharray(cachep, ac); // ローカルキャッシュが保持する空きオブジェクトを減らす
        ac_entry(ac)[ac->avail++] = objp; // 解放対象のオブジェクトを利用可能オブジェクトの配列に繋ぐ
    }
}

__cache_free()はローカルキャッシュに空きオブジェクトを戻すが、既にローカルキャッシュ内に十分な空きオブジェクトが存在する場合には、cache_flusharray()関数を用いてCPU間で共有しているキャッシュ若しくはスラブアロケータにローカルキャッシュ内のオブジェクトを渡すことでローカルキャッシュ内の利用可能オブジェクトを増やす。

// mm/slab.c
// ローカルキャッシュが保持する空きオブジェクトを減らす
static void cache_flusharray (kmem_cache_t* cachep, struct array_cache *ac)
{
    int batchcount;

    batchcount = ac->batchcount; // 一度に処理するオブジェクト数
#if DEBUG
    BUG_ON(!batchcount || batchcount > ac->avail);
#endif
    check_irq_off(); // 割り込みが無効になっているか
    spin_lock(&cachep->spinlock); // スピンロックを取得

    // 共有キャッシュが存在する場合はそちらにオブジェクトを渡す
    if (cachep->lists.shared) {
        struct array_cache *shared_array = cachep->lists.shared; // 共有キャッシュを取得
        int max = shared_array->limit-shared_array->avail; // 共有キャッシュに戻すことが可能なオブジェクト数を算出
        if (max) { // 共有キャッシュに戻すことが可能である場合

            // 一度に処理するオブジェクト数よりも共有キャッシュ内の空きが小さい場合
            if (batchcount > max) 
                batchcount = max; // 処理するオブジェクト数を調整
            
            // 共有キャッシュにローカルキャッシュ内のポインタを移動
            memcpy(&ac_entry(shared_array)[shared_array->avail],
                    &ac_entry(ac)[0],
                    sizeof(void*)*batchcount);
            shared_array->avail += batchcount; // 共有キャッシュ内の利用可能オブジェクト数を更新
            goto free_done; // 解放完了
        }
    }

    // スラブアロケータにローカルキャッシュを返却
    free_block(cachep, &ac_entry(ac)[0], batchcount);
free_done:
#if STATS
    :
    // 割愛
    :
#endif
    spin_unlock(&cachep->spinlock); // スピンロックの解放
    ac->avail -= batchcount; // ローカルキャッシュの利用可能数を更新
    // ローカルキャッシュ内の有効オブジェクトを先頭に集める
    memmove(&ac_entry(ac)[0], &ac_entry(ac)[batchcount],
            sizeof(void*)*ac->avail);
}

上記ではまずCPU間で共有しているキャッシュ内を確認し十分な空きスペースがあればそちらに空きオブジェクトを渡す。十分な空きスペースが存在しなかった場合にはfree_block()関数でローカルキャッシュ内のオブジェクトをスラブアロケータに渡す。

スラブアロケータに秋オブジェクトを返す際に使用されるfree_block()関数の定義は以下。

// mm/slab.c
/**
 * cachep: キャッシュ
 * objpp: オブジェクト
 * nr_objects: オブジェクト数
 */
static void free_block(kmem_cache_t *cachep, void **objpp, int nr_objects)
{
    int i;

    check_spinlock_acquired(cachep); // スピンロックが取得されているか確認

    /* NUMA: move add into loop */
    cachep->lists.free_objects += nr_objects; // スラブ内の空きオブジェクト数に解放数を加算

    for (i = 0; i < nr_objects; i++) {
        void *objp = objpp[i];
        struct slab *slabp;
        unsigned int objnr;

        slabp = GET_PAGE_SLAB(virt_to_page(objp)); // オブジェクトを管理するスラブを取得
        list_del(&slabp->list); // スラブのリストを削除
        objnr = (objp - slabp->s_mem) / cachep->objsize; // スラブ内のオブジェクトのインデックスを算出
        check_slabp(cachep, slabp);
#if DEBUG
        if (slab_bufctl(slabp)[objnr] != BUFCTL_FREE) {
            printk(KERN_ERR "slab: double free detected in cache '%s', objp %p.\n",
                        cachep->name, objp);
            BUG();
        }
#endif
        slab_bufctl(slabp)[objnr] = slabp->free; // オブジェクトディスクリプタに代入
        slabp->free = objnr; // オブジェクトディスクリプタのインデックスを代入(次の割り当て時に使用される)
        STATS_DEC_ACTIVE(cachep);
        slabp->inuse--; // 使用中のオブジェクト数を減らす
        check_slabp(cachep, slabp);

        // 使用中のオブジェクトが存在しなくなった場合
        if (slabp->inuse == 0) {

            // 空きオブジェクト数がリストの制限値を超過した場合スラブのページフレームをページフレームアロケータに開放する
            if (cachep->lists.free_objects > cachep->free_limit) {
                cachep->lists.free_objects -= cachep->num; // 未使用オブジェクト数を減算
                slab_destroy(cachep, slabp); // スラブを削除
            
            // 未使用オブジェクトだけを扱うスラブのリストに繋ぐ
            } else {
                list_add(&slabp->list,
                &list3_data_ptr(cachep, objp)->slabs_free);
            }
        
        // 一部のオブジェクトが使用中である場合
        } else {
            /* Unconditionally move a slab to the end of the
            * partial list on free - maximum time for the
            * other objects to be freed, too.
            */
            // 使用されているオブジェクトを持つスラブのリストに繋ぐ
            list_add_tail(&slabp->list,
                &list3_data_ptr(cachep, objp)->slabs_partial);
        }
    }
}

汎用オブジェクトの取得及び解放

汎用オブジェクトの取得にはkmalloc()関数を使用する。内部では__kmalloc()を呼び出しており、当該関数は以下のように定義されている。

/**
 * kmalloc - allocate memory
 * @size: 何バイトのメモリが要求されているか
 * @flags: どの種類のメモリを割り当てるか
 *
 * kmalloc()はカーネル内でメモリ割り当てに使用する一般的なメソッドである。
 *
 * @flagsはおそらく以下のいずれかが指定される
 *
 * %GFP_USER - ユーザに代わって割り当てる(おそらくスリープする)
 * %GFP_KERNEL - 通常のカーネルメモリとして割り当てる(おそらくスリープする)
 * %GFP_ATOMIC - スリープしない。割り込みハンドラ内などで使用される
 *
 * 加えて"GFP_DMA"フラグはDMAに適当なメモリの指定するたえに使用される可能性がある。
 * これは異なるプラットフォームでは異なるモノを意味する。例えばi386であればそれは
 * 先頭16MBから来るメモリでなければならない
 */
void * __kmalloc (size_t size, int flags)
{
    // 各サイズの汎用キャッシュ配列を取得
    struct cache_sizes *csizep = malloc_sizes;

    // 適切なサイズの汎用キャッシュを探す
    for (; csizep->cs_size; csizep++) {
        if (size > csizep->cs_size)
            continue;
#if DEBUG
        /* This happens if someone tries to call
        * kmem_cache_create(), or kmalloc(), before
        * the generic caches are initialized.
        */
        BUG_ON(csizep->cs_cachep == NULL);
#endif
        // DMA転送用が確認し、どのキャッシュから割り当てるかを決定する
        return __cache_alloc(flags & GFP_DMA ?
             csizep->cs_dmacachep : csizep->cs_cachep, flags);
    }
    return NULL;
}

先程見た__cache_alloc()関数を使用しており、指定されたサイズに最適なサイズの汎用キャッシュから割り当てているのがわかる。

解放にはkfree()関数を使用する。

/**
 * kfree - 割り当て済みのメモリを開放する
 * @objp: kmallocで返されたオブジェクトのポインタ
 *
 * kmalloc()で割り当てられたメモリ以外を開放してはならない
 */
void kfree (const void *objp)
{
    kmem_cache_t *c;
    unsigned long flags;

    // オブジェクトのポインタが存在しない
    if (!objp)
        return;
    local_irq_save(flags); // EFLAGSレジスタの値を保存し割り込みを禁止
    kfree_debugcheck(objp);
    c = GET_PAGE_CACHE(virt_to_page(objp)); // キャッシュディスクリプタを取得
    __cache_free(c, (void*)objp); // オブジェクトを対応するキャッシュに返す
    local_irq_restore(flags); // EFLAGSレジスタの値をリストア
}

処理はシンプルでオブジェクトに対応するキャッシュを取得し、そのキャッシュに対してオブジェクトを返す処理となっている。

非連続メモリ領域の管理

キャッシュ効率が良くメモリアクセスの回数を抑えることができるため、メモリ領域を連続したページフレームに割り当てることが望ましい。反対にメモリアクセスがそれほど頻繁に発生しない場合にはメモリの断片化を防ぐため非連続ページフレームへの割り当てを検討する価値がある。

Linuxでは非連続メモリ領域をいくつかの場所で使用している。

  • スワップ領域管理用データ
  • モジュール空間
  • I/Oドライバ用のバッファ
  • 高位メモリページフレーム

非連続メモリ領域のリニアアドレス

0xC0000000以降はカーネル空間となっており、当該番地以降のリニアアドレスは以下のように使用される。

  • カーネル空間の先頭(PAGE_OFFSET == 0xC0000000)に物理RAMの先頭から896MBを直接マッピング
  • カーネル空間の末尾に固定マッピングされたリニアドレス
  • PKMAP_BASEから高位メモリを永続的にマッピングするためのリニアアドレスが始まる
  • 残りのリニアアドレス領域は非連続メモリ領域として使用

VMALLOC_STARTの手前とVMALLOC_ENDの後ろに8MBの空間がはメモリ領域のout-of-boundを補足する目的で置かれている。

// include/asm-i386/page.h
#define __PAGE_OFFSET      (0xC0000000)
#define PAGE_OFFSET        ((unsigned long)__PAGE_OFFSET)

// include/asm-i386/pgtable.h
#define VMALLOC_OFFSET (8*1024*1024)
#define VMALLOC_START  (((unsigned long) high_memory + vmalloc_earlyreserve + \
           2*VMALLOC_OFFSET-1) & ~(VMALLOC_OFFSET-1))
#ifdef CONFIG_HIGHMEM
# define VMALLOC_END   (PKMAP_BASE-2*PAGE_SIZE)
#else
# define VMALLOC_END   (FIXADDR_START-2*PAGE_SIZE)
#endif

// include/asm-i386/highmem.h
// 永続的なカーネルマッピングの開始位置
#define PKMAP_BASE ( (FIXADDR_BOOT_START - PAGE_SIZE*(LAST_PKMAP + 1)) & PMD_MASK )

// include/asm-i386/fixmap.h
#define FIXADDR_BOOT_START (FIXADDR_TOP - __FIXADDR_BOOT_SIZE)

#define __FIXADDR_BOOT_SIZE    (__end_of_fixed_addresses << PAGE_SHIFT)

// 固定マップ用リニアアドレス
#define FIXADDR_START      (FIXADDR_TOP - __FIXADDR_SIZE)

#define FIXADDR_TOP    ((unsigned long)__FIXADDR_TOP)
#define __FIXADDR_TOP  0xfffff000

#define __FIXADDR_SIZE (__end_of_permanent_fixed_addresses << PAGE_SHIFT)

非連続メモリ領域のディスクリプタ

非連続メモリ領域に対応するディスクリプタは以下のように定義されている。

struct vm_struct {
    void           *addr; // 領域内の先頭ページフレームのリニアアドレス
    unsigned long     size; // メモリ領域のサイズ
    unsigned long     flags; // マッピングしているメモリの種類
    struct page        **pages; // ページディスクリプタのポインタ配列
    unsigned int      nr_pages; // 上記ポインタ配列の数
    unsigned long     phys_addr; // ハードウェアデバイスのI/O共有メモリとして使用しない場合は0
    struct vm_struct   *next; // 次のvm_struct構造体を指すポインタ
};

vm_structは単方向リストをなしており、vmlist変数がそのリストの先頭要素を指しており、そのリストを保護する目的でvmlist_lockが読み書きスピンロックとして定義されている。

// mm/vmalloc.c
DEFINE_RWLOCK(vmlist_lock);
struct vm_struct *vmlist;

vm_structflagsメンバには以下のような値を取る。

// include/linux/vmalloc.h
/* bits in vm_struct->flags */
#define VM_IOREMAP 0x00000001 /* ioremap()または同類関数により割り当てられたハードウェア上にあるオンボードメモリをマッピングしたメモリ領域 */
#define VM_ALLOC   0x00000002 /* vmalloc()によって割り当てられたページ */
#define VM_MAP     0x00000004 /* vmap()でマッピングされたページ */

空き領域がみつかった場合にそれを返す関数であるget_vm_area()関数では上記のスピンロック及びリストが使用されているのがわかる。

// mm/vmalloc.c
/**
 * get_vm_area  -  連続したカーネルの仮想領域を予約する
 *
 * @size:      領域のサイズ
 * @flags:     I/O mappingsのためのVM_IOREMAP もしくは VM_ALLOC
 *
 *  カーネルの仮想マッピングされた領域内のsizeで指定したサイズの領域を探し予約する
 *  成功時はvm_structのポインタを返し、失敗時にはNULLを返す
 */
struct vm_struct *get_vm_area(unsigned long size, unsigned long flags)
{
    return __get_vm_area(size, flags, VMALLOC_START, VMALLOC_END);
}

struct vm_struct *__get_vm_area(unsigned long size, unsigned long flags,
                unsigned long start, unsigned long end)
{
    struct vm_struct **p, *tmp, *area;
    unsigned long align = 1;
    unsigned long addr;

    // ioremap時のバリデーション
    if (flags & VM_IOREMAP) {
        int bit = fls(size);

        if (bit > IOREMAP_MAX_ORDER)
            bit = IOREMAP_MAX_ORDER;
        else if (bit < PAGE_SHIFT)
            bit = PAGE_SHIFT;

        align = 1ul << bit;
    }
    addr = ALIGN(start, align); // アラインメント

    area = kmalloc(sizeof(*area), GFP_KERNEL); // 汎用キャッシュからメモリ領域の取得
    if (unlikely(!area))
        return NULL;

    /*
    * 保護用のページを割り当てる
    */
    size += PAGE_SIZE;
    if (unlikely(!size)) {
        kfree (area);
        return NULL;
    }

    write_lock(&vmlist_lock); // vm_structリスト用のスピンロックを取得
    // リストを先頭(vmlist)からトラバースし空き領域を探す
    for (p = &vmlist; (tmp = *p) != NULL ;p = &tmp->next) {
        if ((unsigned long)tmp->addr < addr) {
            if((unsigned long)tmp->addr + tmp->size >= addr)
                addr = ALIGN(tmp->size + 
                         (unsigned long)tmp->addr, align);
            continue;
        }
        if ((size + addr) < addr)
            goto out;
        if (size + addr <= (unsigned long)tmp->addr)
            goto found;
        addr = ALIGN(tmp->size + (unsigned long)tmp->addr, align);
        if (addr > end - size)
            goto out;
    }

// 見つかった場合
found:
    // リストにvm_structを繋ぐ
    area->next = *p;
    *p = area;
    // vm_struct構造体を初期化
    area->flags = flags;
    area->addr = (void *)addr;
    area->size = size;
    area->pages = NULL;
    area->nr_pages = 0;
    area->phys_addr = 0;
    write_unlock(&vmlist_lock); // スピンロックを解放

    return area;

out:
    write_unlock(&vmlist_lock); // スピンロックを解放
    kfree(area); // 取得したメモリ領域を開放する
    if (printk_ratelimit())
        printk(KERN_WARNING "allocation failed: out of vmalloc space - use vmalloc=<size> to increase size.\n");
    return NULL;
}

非連続メモリ領域の割り当てと解放

割り当てにはvmalloc()関数を用いる。

// mm/vmalloc.c
/**
 * vmalloc  -  仮想的に連続したメモリを割り当てる
 *
 * @size:      割り当てサイズ
 *
 *  ページアロケータからサイズ以上のページを割り当て、それを連続するカーネルの
 *  仮想メモリ領域にマッピングする。
 *
 *  厳しいページアロケータの制御及び保護フラグのため、__vmalloc()を代わりに使用する。
 */
void *vmalloc(unsigned long size)
{
       return __vmalloc(size, GFP_KERNEL | __GFP_HIGHMEM, PAGE_KERNEL);
}

/**
 * __vmalloc  -  仮想的に連続しているメモリを予約する
 *
 * @size:      割り当てサイズ
 * @gfp_mask:  ページアロケータのためのフラグ
 * @prot:      割り当てたページの保護マスク
 *
 *  サイズをカバーできるページをgfp_maskフラグと共にページアロケータから割り当てる。
 *  protのページテーブル保護を用いて割り当てたページは連続する仮想領域にマップする。
 */
void *__vmalloc(unsigned long size, int gfp_mask, pgprot_t prot)
{
    struct vm_struct *area;
    struct page **pages;
    unsigned int nr_pages, array_size, i;
    
    // サイズのアライメント及びバリデーション
    size = PAGE_ALIGN(size); // アライメント
    if (!size || (size >> PAGE_SHIFT) > num_physpages)
        return NULL;

    // 空き領域を取得
    area = get_vm_area(size, VM_ALLOC);
    if (!area)
        return NULL;

    nr_pages = size >> PAGE_SHIFT; // ページ数に変換
    array_size = (nr_pages * sizeof(struct page *)); // ページ数のページディスクリプタ配列のサイズ

    area->nr_pages = nr_pages; // ページ数を更新
    
    /* この再帰呼び出しは厳しく制限されている */
    if (array_size > PAGE_SIZE) // ページサイズより大きい場合
        pages = __vmalloc(array_size, gfp_mask, PAGE_KERNEL); // 再帰呼び出し
    else
        pages = kmalloc(array_size, (gfp_mask & ~__GFP_HIGHMEM)); // 汎用キャッシュから割り当てる
    area->pages = pages; // 取得したページディスクリプタのポインタ配列
    
    // 取得できなかった場合
    if (!area->pages) {
        remove_vm_area(area->addr);
        kfree(area);
        return NULL;
    }
    memset(area->pages, 0, array_size); // 当該領域を0クリア

    // 取得した領域にページを割り当てる
    for (i = 0; i < area->nr_pages; i++) {
        // ページを割り当て、メモリディスクリプタのメンバであるリストにページディスクリプタを設定する
        area->pages[i] = alloc_page(gfp_mask);

        // 割り当てに失敗した場合
        if (unlikely(!area->pages[i])) {
            /* いくつかのページの割り当てに成功していた場合には__vunmap()関数でそれらを開放する */
            area->nr_pages = i;
            goto fail;
        }
    }
    
    // 新たなに取得した領域に対応したカーネル用のページテーブルを作成
    if (map_vm_area(area, prot, &pages))
        goto fail;
    return area->addr;

fail: // 割り当てに失敗した場合にはそれを開放する
    vfree(area->addr);
    return NULL;
}

上記ではまず最初に空き領域を探し、その空き領域にページディスクリプタを割り当てる。そしてそのページディスクリプタに対応するページを割り当て、最後にmap_vm_area()関数でカーネルのページテーブルにエントリを追加する。

解放にはvfree()関数を使用する。

/**
 * vfree  -  vmalloc()で割り当てたメモリを開放する
 *
 * @addr:      メモリのベースアドレス
 *
 *  仮想的に連続している領域(addrで開始する)を解放する。
 * おそらくこの関数は割り込みコンテキストからは呼び出されない
 */
void vfree(void *addr)
{
    BUG_ON(in_interrupt());
    __vunmap(addr, 1);
}

内部では__vunmap()を使用しており、これはvumap()関数からも呼び出される(呼び出す際の第二引数が異なる)

/**
 * vunmap  -  release virtual mapping obtained by vmap()で取得された仮想的なマッピングを開放する
 * @addr:      ベースになるメモリアドレス
 *
 *  (addrで開始する)vmap()から渡されたページ配列から作成された仮想的に連続するメモリ領域を開放する
 * 割り込みコンテキストからは呼び出されないだろう
 */
void vunmap(void *addr)
{
    BUG_ON(in_interrupt());
    __vunmap(addr, 0);
}

__vunmap()の定義は以下。

void __vunmap(void *addr, int deallocate_pages)
{
    struct vm_struct *area;

    // バリデーション
    if (!addr)
        return;
    if ((PAGE_SIZE-1) & (unsigned long)addr) {
        printk(KERN_ERR "Trying to vfree() bad address (%p)\n", addr);
        WARN_ON(1);
        return;
    }

    // 領域に対応するカーネル用ページテーブル内エントリを削除
    area = remove_vm_area(addr);

    // 存在しない領域を解放対象とした場合
    if (unlikely(!area)) {
        printk(KERN_ERR "Trying to vfree() nonexistent vm area (%p)\n",
                addr);
        WARN_ON(1);
        return;
    }
    
    // 当該フラグがセットされている場合はページフレームを開放する(ページフレームアロケータに返す)
    if (deallocate_pages) {
        int i;

        // ページ毎に処理
        for (i = 0; i < area->nr_pages; i++) {
            if (unlikely(!area->pages[i]))
                BUG();
            // どこからも参照されていない場合は当該ページを開放する
            __free_page(area->pages[i]);
        }

        if (area->nr_pages > PAGE_SIZE/sizeof(struct page *))
            vfree(area->pages);
        else
            kfree(area->pages); // ポインタ配列自体を解放
    }

    kfree(area); // vm_structを解放
    return;
}

まずカーネルのページテーブルから開放する領域に対応するPTEを削除し、次にその領域をページディスクリプタを解放。そして最後にそのメモリディスクリプタを開放する。

参考

Redisのセットアップについて考えてみる ~ Transparent Huge Pages ~

概要

Redisの設定について書かれた以下リンクに気になる点があったので考察してみる。

https://redis.io/topics/admin

続きを読む

Unix xv6 ~ 起動 ~

概要

xv6のコードリーティングを通してUnixの動作を追う。今回はCPUの起動からカーネルの起動直前までを見ていく。

xv6

xv6は、ANSI Cによる、6th Edition Unixマルチプロセッサx86システムへの再実装である。 xv6はMITにおけるオペレーティングシステムエンジニアリング(6.828)コースにて、教育を目的として使われている。 引用: https://ja.wikipedia.org/wiki/Xv6

ソースコードは以下。コード内にも多くのコメントが記述されており非常に理解し易くなっている。

https://github.com/mit-pdos/xv6-public

続きを読む

Unix xv6 ~ 起動イメージ ~

概要

xv6のコードリーティングを通してUnixの動作を追う。今回は起動イメージを見ていく。

リポジトリは以下。

https://github.com/mit-pdos/xv6-public

xv6

xv6は、ANSI Cによる、Sixth Edition Unixマルチプロセッサx86システムへの再実装である。 xv6はMITにおけるオペレーティングシステムエンジニアリング(6.828)コースにて、教育を目的として使われている。 LinuxBSDとは異なり、xv6は1セメスターで学習するのに十分なほどシンプルであり、Unixの重要な概念と構造を含んでいる。 引用: https://ja.wikipedia.org/wiki/Xv6

続きを読む

Linux Kernelへのパッチ作成及び送信手順

1. 変更を行う

2. コミットをrebaseし纏める

git rebase -i [commit id]

3. パッチの作成

git format-patch [commit id]

4. パッチの確認

./scripts/checkpatch.pl [patch file]

ここで何らかのエラーが出力される場合には修正を行う。

  • 変数宣言の空白行の有無

空白行を追加する。

WARNING: Missing a blank line after declarations
#21: FILE: kernel/sched/core.c:6706:
+       u64 quota, period;
+       if (cfs_percent < 0)
  • Signed-off-byの有無

コミット(git commit)時に-sのオプションを追加することでコミットに付加することが可能。git commit --amend -sなどコミット後の変更も可能。

ERROR: Missing Signed-off-by: line(s)

5. パッチを送信するメンテナの確認

./scripts/get_maintainer.pl [patch file]

出力例:

$ ./scripts/get_maintainer.pl 0001-feat-CFS-Bandwidth-add-an-interface-for-CFS-Bandwidt.patch
Ingo Molnar <mingo@redhat.com> (maintainer:SCHEDULER)
Peter Zijlstra <peterz@infradead.org> (maintainer:SCHEDULER)
linux-kernel@vger.kernel.org (open list:SCHEDULER)

6. パッチの送信

送信者以外にもメーリングリストや自身へのCCは推奨されている。

コマンド例:

$ git send-email \
--to='mingo@redhat.com'
--cc-cmd='./scripts/get_maintainer.pl --norolestats 0001-feat-CFS-Bandwidth-add-an-interface-for-CFS-Bandwidt.patch' \
--cc='peterz@infradead.org' \
--cc='linux-kernel@vger.kernel.org' \
--cc='princeontrojanhorse@gmail.com' \
0001-feat-CFS-Bandwidth-add-an-interface-for-CFS-Bandwidt.patch

参考