メモリ管理、kmalloc、スラブアロケータ

					2010年01月26日
情報科学類 オペレーティングシステム II

                                       筑波大学 システム情報工学研究科 
                                       コンピュータサイエンス専攻, 電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/literacy-2009/2010-01-26
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

■連絡事項

卒業予定の４年生に対する特別措置として、2月9日火曜日6時間目 (16:45-18:00)に試験をすることを検討しています。対象者は、授業終了後、前に集まって下さい。

■今日の大事な話

kmalloc() の使い方
スラブ・アロケータの使い方

■前回資料

◆ページ構造体

印刷資料は、先週配布済み。

◆Buddyシステムの状態

/proc/buddyinfo を見ると、現在の空きページの状態が分かる。

% cat /proc/buddyinfo 
Node 0, zone      DMA      6      5      3      3      4      2      2      0      1      1      2 
Node 0, zone   Normal    476   2577    990    354    174    104     65     34     19      1    135 
Node 0, zone  HighMem   1416   2920   1718   1082    933    504    251    152     87     43     53 
%

この例では、DMA ゾーンの 2 ⁰ (4KB) に、6 個、 2 ¹ (8KB) に、5 個、・・・、2 ¹⁰ に2個の空きがある。外部フラグメンテーションが起きると、大きな塊が少なくなる。

■kmallocとkfree

物理メモリは、ページ単位（4KBのページフレーム単位）で管理している。しかし、カーネル内のデータ構造は、4KB にぴったりはまらない。 Linux でページ単位ではない単位でメモリを確保・開放できるには、次のような方法がある。

kmalloc(), kfree(): malloc(), free() と類似の API
スラブ・アロケータ

◆kmalloc()

C言語のユーザ空間で使えるライブラリ malloc() に似ている。

void *kmalloc(size_t size, gfp_t flags)

引数

size: バイト数
flags: フラグ(以下で説明)

結果: 最低限、size 分のメモリを割り当て、その先頭の番地（カーネル内の仮想アドレス）を返す。割り当てられたメモリは、物理的にも連続になる。割当てできない時には、NULL を返す。

◆kmalloc()のフラグ

次のものがよく使われる。特に GFP_KERNEL がよく使われる。

型	説明
GFP_ATOMIC	高優先度。スリープ不可。割込みハンドラや下半分(bottom half)で使う。
GFP_NOIO	スリープ可、入出力不可。
GFP_NOFS	スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。
GFP_KERNEL	カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。
GFP_USER	ユーザ空間用のメモリの通常の方法。スリープ可。
GFP_HIGHUSER	HIGHMEMゾーンからの割当て。スリープ可。
GFP_DMA	DMAゾーンからの割当て。デバイス・ドライバ等が使う。

スリープする可能性があるかないかが重要。
メモリが確保できない時には、ページアウトして確保する可能性がある。
ページアウトには、入出力が伴う。入出力中は、プロセスは、スリープする（blocked状態になる）。
割り込みハンドラ（授業の後で説明する）等、スリープできない場所がある。
入出力処理のためにメモリが必要になって、メモリを確保することがある。
メモリが確保できない時には、ページアウトして確保する可能性がある。
ページアウトには、入出力が伴う。
入出力処理のためにメモリが必要になって、メモリを確保することがある。
メモリが確保できない時には、ページアウトして確保する可能性がある。
ページアウトには、入出力が伴う。
入出力処理のためにメモリが必要になって、メモリを確保することがある。
メモリが確保できない時には、ページアウトして確保する可能性がある。
ページアウトには、入出力が伴う。
・・・。

◆kfree()

void kfree(const void *objp)

C言語のユーザ空間で使えるライブラリ free() と似ている。 kmalloc() で割り当てたメモリを解放する。

◆vmalloc()とvfree()

kmallc()/kfree() と似ているが、割り当てられるメモリは物理的に連続している保証はない。（カーネル空間の仮想アドレスとしては連続している。）

■スラブアロケータ(slab allocator)

同じ大きさの構造体を割り当てる時に使う。 kmalloc(), kfree() よりも、効率がよい。

◆free list方式とその問題点

構造体の割当てには、free list 方式が使われることもある。

構造体を割り当てる時には、free list から取り出す。
free list が空なら、構造体が複数入るような大きなメモリ(ページ単位)を割当て、free list につなぐ。
構造体が使われなくなったら、free list につなぐ。

この方法では、メモリに空きがあっても、解放できるか簡単にはわからない。

図? フリーリストの例

オブジェクトは、1ページに2個入る。オブジェクトが次の順番で開放された。

object 2
object 6
object 3
object 1

図? フリーリストの例(ページを意識)

object 2 と object 3 の部分は、1ページ空いている。

◆スラブ・アロケータの目標

よく使われるオブジェクトは、すぐに開放される傾向にある。その性質を生かすために「キャッシュ」する。
free list では、メモリ・フラグメンテーションが起きる。スラブ・アロケータでは、複数の未使用のメモリをつなげて大きくして、開放できる。
キャッシュは、マルチプロセッサでは、CPU ごとに割り当てたるなどして、ロックを減らす。
オブジェクトが別のキャッシュ・ラインに乗るように、「色をつける(colored)」。

スラブ・アロケータ自身は、__alloc_pages() 等のページ単位のメモリ割当て機能を呼出してメモリを確保する。

◆ページ・フレーム、スラブ、オブジェクトの関係

図? ページ・フレーム、スラブ、オブジェクトの関係

オブジェクトの大きさ(構造体の大きさ)は、プログラミングの都合で決まる。ページの大きさとは無関係。
１つのスラブは、ヘッダと複数のオブジェクトから構成される。
小さいオブジェクトは、1スラブが1つのページフレームに収まるようにすることが多い。
１つのスラブが、複数のページフレームにまたがることもある。

◆kmem_cache_create()

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

引数

name: 文字列の名前。/proc/slabinfo で使われる。
size: オブジェクトのサイズ。
align: オブジェクトに必要なアラインメント。
flags: フラグ。
ctor: オブジェクトのコンストラクタ。関数へのポインタ。

結果: 成功した時には、struct kmem_cache へのポインタ。失敗するとNULL。新しいページが割り当てられた時には、ctor で指定された関数が呼ばれる。

◆kmem_cache_destroy()

void kmem_cache_destroy(struct kmem_cache *c)

kmem_cache_create() で割り当てた struct kmem_cache *を開放する。 shutdown (電源を切る操作)で呼ばれることがある。

◆kmem_cache_alloc()とkmem_cache_free()

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

生成した struct kmem_cache *を使ってオブジェクトのメモリを割り当てる。割り当てたオブジェクトのメモリは、kmem_cache_free()で開放する。

◆/proc/slabinfo

/proc/slabinfo を見ると、スラブアロケータの状態がわかる。

% cat /proc/slabinfo  
slabinfo - version: 2.0
# name            <active_objs> <num_objs> <objsize> <objperslab> <pagesperslab> : tunables <batchcount> <limit> <sharedfactor> : slabdata <active_slabs> <num_slabs> <sharedavail>
ip_conntrack_expect      0      0    256   15    1 : tunables  120   60    8 : slabdata      0      0      0
ip_conntrack          22     50    384   10    1 : tunables   54   27    8 : slabdata      5      5      0
nfs_direct_cache       0      0     68   58    1 : tunables  120   60    8 : slabdata      0      0      0
nfs_write_data        36     42    512    7    1 : tunables   54   27    8 : slabdata      6      6      0
...
task_struct           84    115   1408    5    2 : tunables   24   12    8 : slabdata     23     23      0
anon_vma             767   1130     16  226    1 : tunables  120   60    8 : slabdata      5      5      0
pgd                   54    238     32  119    1 : tunables  120   60    8 : slabdata      2      2      0
pmd                  123    123   4096    1    1 : tunables   24   12    8 : slabdata    123    123      0
size-131072(DMA)       0      0 131072    1   32 : tunables    8    4    0 : slabdata      0      0      0
size-131072            0      0 131072    1   32 : tunables    8    4    0 : slabdata      0      0      0
size-65536(DMA)        0      0  65536    1   16 : tunables    8    4    0 : slabdata      0      0      0
size-65536             2      2  65536    1   16 : tunables    8    4    0 : slabdata      2      2      0
...
size-32             8314   8925     32  119    1 : tunables  120   60    8 : slabdata     75     75      0
kmem_cache           150    150    256   15    1 : tunables  120   60    8 : slabdata     10     10      0
%

スラブ・アロケータには、２種類ある。

専用。たとえば、task_struct なら、sizeof(struct task_struct) としてキャッシュに保存。前半に表示される。
汎用。いくつかの大きさのメモリ。32、64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072。後半の size-番号 。 DMA が付いているものは、DMA 可能なメモリ。

◆利用例(task_struct)

kernel/fork.c
 171: void __init fork_init(unsigned long mempages)
 172: {
...
 178:         task_struct_cachep =
 179:                 kmem_cache_create("task_struct", sizeof(struct task_struct),
 180:                         ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);

  99: # define alloc_task_struct()    kmem_cache_alloc(task_struct_cachep, GFP_KERNEL)
 100: # define free_task_struct(tsk)  kmem_cache_free(task_struct_cachep, (tsk))

◆struct slab

 224: struct slab {
 225:         struct list_head list;
 226:         unsigned long colouroff;
 227:         void *s_mem;            /* including colour offset */
 228:         unsigned int inuse;     /* num of objs active in slab */
 229:         kmem_bufctl_t free;
 230:         unsigned short nodeid;
 231: };

list: スラブのリストを作る。
colouroff: 「色」のオフセット。
s_mem: スラブの最初のオブジェクトへのポインタ。
inuse: スラブ中の利用されているオブジェクトの数。
free: 配列は、スラブの空きを管理する配列の添字(最初の利用可能なオブジェクトの添字)を保持する。

図? ページ・フレーム、スラブ、オブジェクトの関係

◆kmem_list3

mm/slab.c
 293: struct kmem_list3 {
 294:         struct list_head slabs_partial; /* partial list first, better asm code */
 295:         struct list_head slabs_full;
 296:         struct list_head slabs_free;
...
 305: };

スラブの分類

部分的に利用(slabs_partial)
全部利用(slabs_full)
全部空き(slabs_free)

全部空きが、あるしきい値以上に増えると、Buddyシステムに返却する。

図? スラブのリスト

■クイズ6 メモリ管理、kmalloc、スラブアロケータ

★問題(601) kmalloc()とkfree()

以下は、ユーザ空間でメモリを割当て、利用し、開放するプログラムの一部である。

   struct s1 *p;
   p = malloc( sizeof(struct s1) );
   use( p );
   free( p );

このプログラムを、カーネル内で動かすことを想定してkmalloc() と kfree() を使って書き換えなさい。

★問題(602) スラブアロケータ

問題(601) のプログラムを、スラブアロケータを使って書き換えなさい。すなわち、kmem_cache_create()、kmem_cache_alloc()、および、 kmem_cache_free()を使って書き換えなさい。

Last updated: 2010/01/26 13:40:10

Yasushi Shinjo / <yas@is.tsukuba.ac.jp>