Linux オブジェクトアロケータスラブアルゴリズム

[[414991]]

この記事はWeChatの公開アカウント「Linux Kernel Things」から転載したもので、著者はsongsong001です。この記事を転載する場合は、Linux Kernel Matters パブリックアカウントにご連絡ください。

この記事は比較的初期に書かれたため、当時は Linux-2.4.16 カーネルが使用されていましたが、全体的なソースコード分析には影響しません。

SLAB割り当てアルゴリズム

前のセクションでは、Linux カーネルがバディシステムアルゴリズムを使用してメモリページを管理することを説明しました。ただし、バディシステムアルゴリズムの割り当て単位はメモリページです。つまり、少なくとも 1 つ以上のメモリブロックを割り当てる必要があります。ただし、多くの場合、メモリページを割り当てる必要はありません。たとえば、200 バイトの構造を適用する場合、バディシステム割り当てアルゴリズムを使用して少なくとも 1 つのメモリページを適用しても、200 バイトのメモリしか使用しないと、残りの 3896 バイトが無駄になります。

小さなメモリのアプリケーションの問題を解決するために、Linux カーネルは SLAB 割り当てアルゴリズムを導入しました。Linux で使用される SLAB 割り当てアルゴリズムは、Jeff Bonwick が SunOS オペレーティングシステム用に最初に導入したアルゴリズムに基づいています。カーネルでは、ファイル記述子やその他の共通構造体などの限られたオブジェクトセットに大量のメモリが割り当てられます。ジェフは、カーネル内の共通オブジェクトの初期化に必要な時間が、それらの割り当てと割り当て解除に必要な時間を超えていることを発見しました。したがって、メモリはグローバルメモリプールに解放し戻すのではなく、特定の目的のために初期化された状態で保持する必要があるというのが彼の結論です。

SLAB 割り当てアルゴリズムをよりよく理解するために、まずアルゴリズムで使用されるデータ構造を紹介します。

関連するデータ構造

SLAB 割り当てアルゴリズムには 2 つの重要なデータ構造があります。1 つは kmem_cache_t で、もう 1 つは slab_t です。kmem_cache_t 構造を見てみましょう。

構造体 kmem_cache_s {
 /* 1) それぞれの割り当てと解放*/
    /*完全、部分的 まず、それから 無料*/
    構造体 list_head slabs_full;
    構造体 list_head slabs_partial;
    構造体 list_head slabs_free;
    符号なし整数オブジェクトサイズ;
    unsigned int flags; /* 定数フラグ */
    unsigned int num; /*スラブあたりのオブジェクト数 */
    spinlock_t スピンロック;
 #ifdef CONFIG_SMP
    符号なし整数バッチカウント;
 #終了
 
 /* 2) スラブの追加 /削除 */
    /*注文 スラブあたりのページ数 (2^n) */
    符号なし整数gfporder; 
 
    /* GFP フラグを強制します(例: GFP_DMA) */
    符号なし整数gfpフラグ; 
 
    size_t colour; /* キャッシュの色付け範囲 */
    unsigned int colour_off; /* 色のオフセット */
    unsigned int colour_next; /* キャッシュの色分け */
    kmem_cache_t *slabp_cache;
    符号なし整数増加;
    unsigned int dflags; /*動的フラグ */ 
 
    /* コンストラクタ関数 */
    void (*ctor)(void *, kmem_cache_t *, 符号なしロング); 
 
    /* デコンストラクタ関数 */
    void (*dtor)(void *, kmem_cache_t *, 符号なしロング); 
 
    unsigned long の失敗。 
 
 /* 3) キャッシュの作成/削除 */
文字            名前[CACHE_NAMELEN];
    構造体list_head次;
    ...
 };

以下では、 kmem_cache_t 構造体のより重要なフィールドを紹介します。

slab_full: 完全に割り当てられたスラブ
slab_partial: 部分的に割り当てられたスラブ
slab_free: 割り当てられていないスラブ
objsize: 保存されたオブジェクトのサイズ
num: スラブに格納できるオブジェクトの数
gfporder: スラブは2gfporderのメモリページから構成されます
colour/colour_off/colour_next: 着色領域のサイズ（後述）

slab_t 構造体は次のように定義されます。

 typedef 構造体 slab_s {
    構造体 list_head リスト;
    符号なしロングカラーオフ;
    void *s_mem; /* カラーオフセットを含む */
    unsigned int inuse; /*スラブ内のアクティブなオブジェクトの数*/
    kmem_bufctl_tが解放されます;
 } スラブt;

slab_t 構造体の各フィールドの目的は次のとおりです。

リスト: 接続 (完全/部分/空) チェーン
colouroff: 色補正
s_mem: ストレージオブジェクトの開始メモリアドレス
inuse: 割り当てられているオブジェクトの数
free: アイドルオブジェクトに接続するために使用されます

それらの関係は次の図に示されています。

SLAB割り当てアルゴリズムの初期化

SLAB 割り当てアルゴリズムの初期化は、次のように kmem_cache_init() 関数によって実行されます。

 void __init kmem_cache_init(void)
 {
    size_t 残り; 
 
    init_MUTEX(&cache_chain_sem);
    INIT_LIST_HEAD(&キャッシュチェーン); 
 
    kmem_cache_estimate(0, キャッシュキャッシュ.objsize, 0,
            &left_over、&cache_cache.num);
    if (!cache_cache.num)
        バグ（）; 
 
    cache_cache.colour = left_over / cache_cache.colour_off;
    キャッシュキャッシュ.color_next = 0;
 }

この関数は主に変数 cache_cache を初期化するために使用されます。cache_cache は次のように定義される kmem_cache_t 型の構造体変数です。

静的kmem_cache_t キャッシュキャッシュ = {
    slabs_full: LIST_HEAD_INIT(cache_cache.slabs_full)、
    slabs_partial: LIST_HEAD_INIT(cache_cache.slabs_partial)、
    slabs_free: LIST_HEAD_INIT(cache_cache.slabs_free)、
    オブジェクトサイズ: sizeof(kmem_cache_t)、
    フラグ: SLAB_NO_REAP、
    スピンロック: SPIN_LOCK_UNLOCKED、
    カラーオフ: L1_CACHE_BYTES、
名前: "kmem_cache" 、
 };

なぜこのようなオブジェクトが必要なのでしょうか。 kmem_cache_t 構造体自体も小さなメモリオブジェクトであるため、これもスラブアロケータによって割り当てられる必要がありますが、これにより「鶏が先か卵が先か」という疑問が生じます。システムが初期化されると、スラブアロケータは初期化されていないため、スラブアロケータを使用して kmem_cache_t オブジェクトを割り当てることはできません。この時点で、スラブアロケータは、kmem_cache_t 型の静的変数を定義することによってのみ管理できます。したがって、cache_cache 静的変数を使用してスラブアロケータを管理します。

上記のコードから、cache_cache の objsize フィールドが sizeof(kmem_cache_t) のサイズに設定されていることが分かります。つまり、このオブジェクトは主に、さまざまなタイプの kmem_cache_t オブジェクトを割り当てるために使用されます。

kmem_cache_init() 関数は、kmem_cache_estimate() 関数を呼び出して、スラブが保持できる cache_cache.objsize サイズのオブジェクトの数を計算し、それらを cache_cache.num フィールドに保存します。スラブ内のすべてのメモリをオブジェクトの割り当てに使用することは不可能です。たとえば、4096 バイトのスラブを使用して 22 バイトのオブジェクトを割り当てた場合、このオブジェクトは 186 個に分割できます。ただし、使用できない 4 バイトが残るため、このメモリの部分はシェーディング領域として使用されます。シェーディング領域の目的は、CPU がスラブをより効率的にキャッシュできるように、異なるスラブをずらすことです。もちろん、これは最適化の一部であり、スラブ割り当てアルゴリズムにはほとんど影響しません。つまり、スラブが色付けされていない場合でも、スラブ割り当てアルゴリズムは機能します。

kmem_cache_t オブジェクトアプリケーション

kmem_cache_t はオブジェクトの管理と割り当てに使用されるため、スラブアロケータを使用する場合は、まず kmem_cache_t オブジェクトを申請する必要があります。kmem_cache_t オブジェクトを申請するには、kmem_cache_create() 関数を使用します。

 kmem_cache_t *
 kmem_cache_create (const char * name 、size_t size 、size_t offset 、
    符号なしロングフラグ、void (*ctor)(void*、kmem_cache_t *、符号なしロング)、
    void (*dtor)(void*, kmem_cache_t *, 符号なし long))
 {
    const char *func_nm = KERN_ERR "kmem_create: " ;
    size_t left_over、align、slab_size;
    kmem_cache_t *cachep = NULL ; 
 
    ... 
 
    キャッシュp = (kmem_cache_t *) kmem_cache_alloc(&cache_cache, SLAB_KERNEL);
    if (!cachep)
ゴートゥーオプス;
    memset(cachep, 0, sizeof(kmem_cache_t)); 
 
    ... 
 
    する {
        符号なし整数break_flag = 0;
カロリー消費量:
        kmem_cache_estimate(cachep->gfporder,サイズ, フラグ,
                        &left_over, &cachep->num);
        if (break_flag)
            壊す;
        （cachep->gfporder >= MAX_GFP_ORDER）の場合
            壊す;
        if (!cachep->num)
行く 次;
        if (flags & CFLGS_OFF_SLAB && cachep->num > offslab_limit) {
            cachep->gfporder --;  
            break_flag++;
 cal_wastageに移動します。
        } 
 
        (cachep->gfporder >= slab_break_gfp_order) の場合
            壊す; 
 
        ((left_over*8) <= (PAGE_SIZE<<cachep->gfporder)) の場合
            break; /* 許容可能な内部断片化。 */
次：
        cachep->gfporder++;
    } 一方で (1); 
 
    if (!cachep->num) {
        printk( "kmem_cache_create: キャッシュ %s を作成できませんでした。\n" , name );
        kmem_cache_free(&cache_cache, cachep);
        cachep = NULL ;
ゴートゥーオプス;
    }
    slab_size = L1_CACHE_ALIGN(cachep->num*sizeof(kmem_bufctl_t)+sizeof(slab_t)); 
 
    フラグとCFLGS_OFF_SLABとleft_over >= slab_sizeの場合{
        フラグ &= ~CFLGS_OFF_SLAB;
        left_over -= スラブサイズ;
    } 
 
    オフセット += (align-1);
    オフセット &= ~(align-1);
    if (!オフセット)
        オフセット = L1_CACHE_BYTES;
    cachep->colour_off = オフセット;
    cachep->colour = left_over/offset; 
 
    if (!cachep->gfporder && !(flags & CFLGS_OFF_SLAB))
        フラグ |= CFLGS_OPTIMIZE; 
 
    cachep->flags = フラグ;
    cachep->gfpflags = 0;
    if (フラグ & SLAB_CACHE_DMA)
        cachep->gfpflags |= GFP_DMA;
    spin_lock_init(&cachep->spinlock);
    cachep->objsize =サイズ;
    INIT_LIST_HEAD(&cachep->slabs_full);
    INIT_LIST_HEAD(&cachep->slabs_partial);
    INIT_LIST_HEAD(&cachep->slabs_free); 
 
    if (フラグ & CFLGS_OFF_SLAB)
        キャッシュp->slabp_cache = kmem_find_general_cachep(slab_size,0);
    cachep->ctor = ctor;
    cachep->dtor = dtor;
    strcpy(cachep-> name , name ); 
 
 #ifdef CONFIG_SMP
    (g_cpucache_up) の場合
        cpucache を有効にします(cachep);
 #終了
 
    ダウン(&cache_chain_sem);
    {
        構造体list_head *p; 
 
        list_for_each(p, &cache_chain) {
            kmem_cache_t *pc = list_entry(p, kmem_cache_t, next ); 
 
            if (!strcmp(pc-> name , name ))
                バグ（）;
        }
    } 
 
    list_add(&cachep-> next , &cache_chain);
    アップ(&cache_chain_sem);
おっと：
 cachepを返します。
 }

kmem_cache_create() 関数は非常に長いため、上記のコードでは、その原理をより明確に反映するために、あまり重要でない部分をいくつか削除しています。

kmem_cache_create() 関数では、kmem_cache_alloc() 関数が最初に呼び出され、kmem_cache_t オブジェクトに適用されます。kmem_cache_alloc() が呼び出されると、cache_cache 変数が渡されることがわかります。 kmem_cache_t オブジェクトを適用した後、主に kmem_cache_t オブジェクトのすべてのフィールドを初期化するために、初期化する必要があります。

スラブサイズとして必要なページ数を計算します。
スラブに割り当てることができるオブジェクトの数を計算します。
シェーディング領域情報を計算します。
slab_full / slab_partial / slab_free リストを初期化します。
要求された kmem_cache_t オブジェクトを cache_chain リストに保存します。

オブジェクトの割り当て

kmem_cache_t オブジェクトに適用した後、 kmem_cache_alloc() 関数を呼び出して、指定されたオブジェクトに適用します。 kmem_cache_alloc() 関数コードは次のとおりです。

静的インライン void * kmem_cache_alloc_one_tail (kmem_cache_t *cachep、slab_t *slabp)
 {
    void *objp; 
 
    ... 
 
    slabp->inuse++;
    objp = slabp->s_mem + slabp-> free *cachep->objsize;
    slabp-> free =slab_bufctl(slabp)[slabp-> free ]; 
 
    slabp-> free == BUFCTL_END の場合、
        list_del(&slabp->list);
        list_add(&slabp->list, &cachep->slabs_full);
    } 
 
 objpを返します。
 } 
 
 #kmem_cache_alloc_one(cachep) を定義します \
 （{\
    構造体 list_head * slabs_partial, * エントリ; \
    slab_t *slabp; \
                                                    \
    slabs_partial = &(cachep)->slabs_partial; \
    エントリ = slabs_partial-> next ; \
    if (可能性は低い(entry == slabs_partial)) { \
        構造体 list_head *slabs_free; \
        slabs_free = &(cachep)->slabs_free; \
        エントリ = slabs_free-> next ; \
        if (可能性は低い(エントリ == slabs_free)) \
 alloc_new_slabに移動します。\
        list_del(エントリ); \
        list_add(エントリ、slabs_partial); \
    } \
    slabp = list_entry(エントリ、slab_t、リスト); \
    kmem_cache_alloc_one_tail(cachep, slabp); \
 }) 
 
静的インライン void * __kmem_cache_alloc (kmem_cache_t *cachep, intフラグ)
 {
    符号なし long save_flags;
    void* オブジェクト; 
 
    kmem_cache_alloc_head(cachep、フラグ);
もう一度やり直してください：
    ローカルIRQを保存(保存フラグ);
    ...
    objp = kmem_cache_alloc_one(cachep); 
 
    local_irq_restore(フラグを保存);
 objpを返します。
新しいスラブの割り当て:
    ...
    local_irq_restore(フラグを保存);
    kmem_cache_grow(cachep, flags) の場合
try_againに移動します。
戻る  NULL ;
 } 
 
 void * kmem_cache_alloc (kmem_cache_t *cachep、 intフラグ)
 {
 __kmem_cache_alloc(cachep, flags) を返します。
 }

kmem_cache_alloc() 関数は上記のように展開されます。 kmem_cache_alloc() 関数の主な手順は次のとおりです。

kmem_cache_t オブジェクトの slab_partial リストから利用可能なスラブがあるかどうかを確認します。利用可能な場合は、スラブから直接オブジェクトを割り当てます。

slab_partial リストに使用可能なスラブがない場合、slab_free リストから使用可能なスラブが検索されます。使用可能なスラブがある場合は、スラブからオブジェクトが割り当てられ、スラブが slab_partial リストに配置されます。

slab_free リストに使用可能なスラブがない場合、 kmem_cache_grow() 関数が呼び出され、新しいスラブを申請してオブジェクトを割り当てます。 kmem_cache_grow() 関数は、__get_free_pages() 関数を呼び出してメモリページを要求し、スラブを初期化します。

スラブの構造は次のとおりです。

灰色の部分は色付きの領域、緑色の部分はスラブ管理構造、黄色の部分は空きオブジェクトリストのインデックス、赤色の部分はオブジェクトエンティティです。スラブ構造体の s_mem フィールドがオブジェクトエンティティリストの開始アドレスを指していることがわかります。

オブジェクトを割り当てるときは、まずスラブ構造の空きフィールドを通じて、利用可能な空きオブジェクトがあるかどうかを確認します。空きフィールドには、空きオブジェクトリストの最初のノードのインデックスが格納されます。

オブジェクトのリリース

オブジェクトの解放は比較的簡単で、主に kmem_cache_free() 関数を呼び出すことによって行われ、 kmem_cache_free() 関数は最終的に kmem_cache_free_one() 関数を呼び出します。コードは次のとおりです。

静的インライン void kmem_cache_free_one(kmem_cache_t *cachep, void *objp)
 {
    slab_t* slabp; 
 
    CHECK_PAGE(virt_to_page(objp)); 
 
    slabp = GET_PAGE_SLAB(virt_to_page(objp)); 
 
    {
        符号なし整数objnr = (objp-slabp->s_mem)/cachep->objsize; 
 
        slab_bufctl(slabp)[objnr] = slabp->解放;
        slabp-> free = objnr;
    }
    STATS_DEC_ACTIVE(キャッシュ); 
     
    {
 int inuse = slabp->inuse;
        if (可能性は低い(! --slabp->inuse)) {  
            list_del(&slabp->list);
            list_add(&slabp->list, &cachep->slabs_free);
        }そうでない場合 (inuse == cachep->num の可能性は低い) {
            list_del(&slabp->list);
            list_add(&slabp->list, &cachep->slabs_partial);
        }
    }
 }