メモリ管理、Buddyシステム、kmalloc、スラブアロケータ

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

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

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

■連絡事項

Softlab 研究室紹介

教官：板野肯三、新城靖、佐藤聡
募集：６人
テーマ：オペレーティング・システム、セキュリティ、分散システム、言語処理系、その他。
場所：3E302
日時
1. 2010年12月08日 (水) 16:45-18:00 (終了)
2. 2010年12月14日 (火) 16:45-18:00 (終了)
3. 2011年01月11日 (火) 16:45-18:00 (本日)

■今日の大事な話

Buddyシステムによる物理メモリの管理
kmalloc() と kfree()
スラブアロケータ

■メモリ管理

物理メモリを管理する。各メモリのフレームごとに、何に使われているのか、空いているのかを管理する。メモリが必要になったら、空いているものを割り当てる。
カーネル自身の論理アドレス空間を管理し、物理メモリを割り当てる。
ユーザ・プロセスに対して、論理アドレス空間を管理し、物理メモリを割り当てる。
空いているメモリが不足してきたら、ページアウトしたり、プロセスを殺して空きメモリを確保する。

■物理メモリの管理

Linux では、搭載されているメモリをページサイズ(4KB-8KBが一般的)で分割し管理する。それを物理ページ(physical page)、あるいは、ページ・フレーム(page frame)と呼ぶ。
1つのページ・フレームには、構造体 struct page で管理する。
全メモリは、構造体 struct page の配列として保持される。たとえば、ページサイズ 4KB で、1GB の物理メモリを持ったシステムでは、 1024*1024*1024/(4*1024) == 262,144 個の要素からなる配列で管理される。

◆ページ構造体

include/linux/mm_types.h
  34:	struct page {
  35:	        unsigned long flags;            /* Atomic flags, some possibly
  36:	                                         * updated asynchronously */
  37:	        atomic_t _count;                /* Usage count, see below. */
...
  48:	        union {
  49:	            struct {
  50:	                unsigned long private;          /* Mapping-private opaque data:
  57:	                struct address_space *mapping;  /* If low bit clear, points to
  64:	            };
...
  69:	            struct page *first_page;    /* Compound tail pages */
  70:	        };
...
  71:	        union {
  72:	                pgoff_t index;          /* Our offset within mapping. */
  73:	                void *freelist;         /* SLUB: freelist req. slab lock */
  74:	        };
  75:	        struct list_head lru;           /* Pageout list, eg. active_list
...
  89:	        void *virtual;                  /* Kernel virtual address (NULL if
  90:	                                           not kmapped, ie. highmem) */
...
 103:	};

count: ページの参照カウント。0 か負なら、そのページ・フレームは空いている( 他の目的で使ってよい)ことを意味する。 1以上なら、以下の目的で使われている。
- ページ・キャッシュ(page cache)
- プライベートなデータ
- プロセスのページテーブル
mappping: ページがページ・キャッシュ(ファイルの一部と対応しているメモリ)を保持している時、アドレス空間構造体(struct address_space)と結びつけられる。 mappping フィールドは、そのページがメンバとなっているアドレス空間構造体を指す。アドレス空間構造体が実現している「アドレス空間」とは、 inode等の「メモリ・オブジェクト」1個に属しているページの集まり。
lru: Least Recently Used でメモリ管理を行うための双方向リスト。 active_list (使われているメモリのリスト)か inactive_list (使われていないメモリのリスト、他の目的に使ってもよいメモリのリスト)につながれる。
virtual: そのページのカーネル内のアドレス。 high memory と呼ばれているメモリの場合、これは NULL になっているので、カーネル内のプログラムからアクセスする時には動的にマップする必要がある。

page構造体のflags(主要部分)
PG_locked	ページがピン留めされている。ページアウトされない。入出力の処理中に設定され、完了後に解除される。
PG_error	このページに対して入出力エラーが生じた。
PG_referenced	ディスク入出力のために参照されている。
PG_uptodate	ページの内容が有効である。入力処理が完了した。
PG_dirty	ページの内容が変更された。
PG_lru	ページングのための LRU リストにある。
PG_active	ページがアクティブである。
PG_slab	スラブ・アロケータで割り当てられた。
PG_arch_1	アーキテクチャ固有のページ状態
PG_reserved	ページアウト禁止、または、ブード時のメモリ・アロケータで割り当てられた
PG_private	ページの内容が無効(page->private が有効な内容を保持している)
PG_writeback	書き戻し中
PG_compound	複合ページ
PG_reclaim	開放すべきページ

◆メモリ・ゾーン

歴史的な都合やハードウェアの制約で、メモリ・ページを「ゾーン」と呼ばれる領域に分割して管理する。

よく使われるゾーンの種類。

ZONE_DMA: (古いデバイスでも) DMA でアクセス可能なページ・フレーム。 x86 では、0-16M。 ISA バスのデバイスで 0-16M しかアクセスできないものがあった。
ZONE_NORMAL: (古いデバイスの)DMA ではアクセスできないが、カーネルの仮想アドレス空間に常にマップされている。 x86 では、16MB-896MBまで。
ZONE_HIGMEM: 普段はカーネルの仮想アドレス空間にマップされていない。使うときにはマップして使い、使い終わったらアンマップする。 x86 では、896MB より大きい所。

◆zone構造体

include/linux/mmzone.h

 280:	struct zone {
...
 284:	        unsigned long watermark[NR_WMARK];
...
 321:	        struct free_area        free_area[MAX_ORDER];
...
 391:	        wait_queue_head_t       * wait_table;
 392:	        unsigned long           wait_table_hash_nr_entries;
 393:	        unsigned long           wait_table_bits;
...
 418:	        const char              *name;
 419:	} ____cacheline_internodealigned_in_smp;
...
 158:	enum zone_watermarks {
 159:	        WMARK_MIN,
 160:	        WMARK_LOW,
 161:	        WMARK_HIGH,
 162:	        NR_WMARK
 163:	};
... 
  23:	#ifndef CONFIG_FORCE_MAX_ZONEORDER
  24:	#define MAX_ORDER 11
  25:	#else
  26:	#define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
  27:	#endif
  28:	#define MAX_ORDER_NR_PAGES (1 << (MAX_ORDER - 1))

watermark: メモリがこの水位(warter mark)を下回ると、カーネルはメモリ不足対策を発動する。
free_area: 利用可能な領域を保持する。
wait_table, wait_table_hash_nr_entries, wait_table_bits: メモリが足りない時に、プロセスをスリープさせるために使う。スリープ中、カーネルは他のプロセスのメモリをページアウトするなどして空きメモリを作るようにがんばる。スリープから解除されたら、もう一度メモリを確保することを試みる。
name: ゾーンの名前。

◆ページフレームの割当てと開放

ページ・フレームは、物理メモリ。 Linux カーネル内では、次のような手続きで、割り当てる。gfp_mask については後述する。

alloc_pages(gfp_mask,order): 2のorder乗(^order, 1 << order)単位でメモリを割り当てる。先頭のページフレームに対応した struct page へのポインタを返す。
page_address(page): struct pageへのポインタからアクセス可能な論理アドレスを得る。
__get_free_pages(gfp_mask,order): 2のorder乗のメモリを割当て、論理アドレスを得る。
alloc_page(gfp_mask): 1ページ割り当て、struct page へのポインタを返す。
__get_free_page(gfp_mask): 1ページ割り当て、番地を返す。
get_zeroed_page(gfp_mask): 0 で埋められた1ページの論理アドレスを返す。

次のような手続きで、メモリを開放する。

__free_pages(page,order)
free_pages(addr, order)
free_page(order)

include/linux/gfp.h

 302:	static inline struct page *
 303:	alloc_pages(gfp_t gfp_mask, unsigned int order)
 304:	{
...
 306:	}
 316:	extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
 314:	#define alloc_page(gfp_mask) alloc_pages(gfp_mask, 0)

 328:	extern void __free_pages(struct page *page, unsigned int order);
 329:	extern void free_pages(unsigned long addr, unsigned int order);
 333:	#define free_page(addr) free_pages((addr), 0)

◆外部フラグメンテーション

物理フレームの割当てと開放を繰り返していくと、外部フラグメンテーション (external fragmentation) が生じる。全体としては空きメモリは存在しているのに、小さなメモリ・フレームがあちこちに分散していて、大きさのページフレームが存在しないためにメモリが割り当てられない状態に陥る。

◆Buddyシステム

「Buddy システム」は、Linux で使われている外部フラグメンテーションを起こしにくいメモリ割当てアルゴリズム。

利用可能なメモリ・ブロックのリストを管理する。リストの数は、MAX_ORDER個。
各リストは、2のべき乗の大きさのメモリ・ブロックを保持する( 2 ⁰, 2 ¹, 2 ², ..., 2 ^{(MAX_ORDER-1)}, )。
ページフレームの割当て(alloc_pages())では、必要な最小のメモリ・ブロックを割り当てる。(大きなブロックを温存する。) 2 ^order が欲しい時に、そのメモリがあれば、それを返す。なければ、2 ^order+1 を探して、それを半分に分割して、返す。（使わなかった分は、2 ^order のリストにつなぐ。）
ページフレームの開放(__free_pages())では、 2 ^order のサイズのブロックを利用可能なリストに接続する。同じ大きさのブロックの中で連続しているもの(buddy)がないかを探す。あれば、結合して大きなブロック(2 ^(order+1)) にしてリストに接続する。

図1(a) Buddyシステムによる空きページの管理(論理的な見方)

図1(b) Buddyシステムによる空きページの管理(線形な見方)

◆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_t)

kmalloc() や __get_free_pages(), alloc_pages(), alloc_page() では、 gfp_t のフラグ(gfp_mask) として、次のものがよく使われる。特に GFP_KERNEL がよく使われる。gfp は、__get_free_pages() に由来する。

型	説明
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: フラグ。SLAB_PANIC が指定されると、メモリの割当てに失敗すれば、システムがクラッシュする。SLAB_CACHE_DMA が指定されると、ZONE_DMA のメモリに割り当てられる。
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
 112:	static struct kmem_cache *task_struct_cachep;
...
 202:	void __init fork_init(unsigned long mempages)
 203:	{
...
 206:	#define ARCH_MIN_TASKALIGN      L1_CACHE_BYTES
...
 209:	        task_struct_cachep =
 210:	                kmem_cache_create("task_struct", sizeof(struct task_struct),
 211:	                        ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);
...
 110:	# define alloc_task_struct()    kmem_cache_alloc(task_struct_cachep, GFP_KERNEL)
 111:	# define free_task_struct(tsk)  kmem_cache_free(task_struct_cachep, (tsk))

L1_CACHE_BYTES で、構造体の番地を少しずつずらしながら、キャッシュのラインがぶつからないようにする。
SLAB_PANIC により、メモリが割り当てられなければ、panic (システム全体をクラッシュ)する。
コンストラクタは、なし。

◆struct slab

mm/slab.c
 200:	struct slab {
 201:	        struct list_head list;
 202:	        unsigned long colouroff;
 203:	        void *s_mem;            /* including colour offset */
 204:	        unsigned int inuse;     /* num of objs active in slab */
 205:	        kmem_bufctl_t free;
...
 207:	};

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

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

◆kmem_list3

mm/slab.c
 269:	struct kmem_list3 {
 270:	        struct list_head slabs_partial; /* partial list first, better asm code */
 271:	        struct list_head slabs_full;
 272:	        struct list_head slabs_free;
...
 281:	};

スラブの分類

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

図? スラブのリスト

空きなくなると、__get_free_pages() でBuddyシステムから取得する。
全部空きが、あるしきい値以上に増えると、free_pages() でBuddyシステムに返却する。

■クイズ4 メモリ管理、Buddyシステム、kmalloc、スラブアロケータ

★問題(401) struct page

struct pageの大きさは、アーキテクチャやコンパイル時のオプションによって異なる。あるシステムで、struct pageの大きさが 40 バイトであったとする。そのシステムに、1GB のメモリが搭載されていた時、struct pageのために、何 MBのメモリが使われるか。ページサイズは、4KBとする。

★問題(402) Buddyシステム

図1 Buddyシステムによる空きページの管理次のようなメモリ要求と開放がなされた時に、どのようなページが返されるか。ページ・フレーム番号で答えなさい。

1ページの確保
1ページの確保
1ページの確保
1ページの確保
1ページの確保

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

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

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

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

利用
   struct s1 *p;
   /*回答*/
   use( p );
   /*回答*/

問題(403) のプログラムを、スラブアロケータを使って書き換えなさい。すなわち、kmem_cache_create()、kmem_cache_alloc()、および、 kmem_cache_free()を使って書き換えなさい。ただし、kmem_cache_create() の第3引数のalign としては、0を、第4引数のflagsとしては、SLAB_PANIC、第5引数のコンストラクタとしては、NULL を指定しなさい。

初期化
   /*回答*/

利用
   struct s1 *p;
   /*回答*/
   use( p );
   /*回答*/

Last updated: 2011/01/11 14:19:55

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