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

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

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

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

■今日の大事な話

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

■メモリ管理

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

■物理メモリの管理

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

図? struct page page[]による物理メモリの管理

注意: 物理メモリを読み書きするには、論理アドレスが必要だが、論理アドレスがない(カーネル空間にマップされていない)こともある。

◆ページ構造体

linux-3.6.8/include/linux/mm_types.h

  41:	struct page {
...
  43:	        unsigned long flags;
...
  45:	        struct address_space *mapping;
...
 110:	                                atomic_t _count;
...
 117:	                struct list_head lru;
...
 165:	        void *virtual;
 179:	}
...
 187:	;

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

◆ページ構造体のflags

linux-3.6.8/include/linux/page-flags.h

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_writeback	書き戻し中
PG_compound	複合ページ
PG_reclaim	開放すべきページ

◆x86のページ・サイズ

2の12乗(1 << 12)==4096バイト。

linux-3.6.8/arch/x86/include/asm/page_types.h
   8:	#define PAGE_SHIFT      12
   9:	#define PAGE_SIZE       (_AC(1,UL) << PAGE_SHIFT)

linux-3.6.8/include/linux/const.h
  19:	#define __AC(X,Y)       (X##Y)
  20:	#define _AC(X,Y)        __AC(X,Y)

◆メモリ・ゾーン

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

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

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

図? メモリのゾーンへの分割

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

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

struct page *alloc_pages(gfp_mask,order): 2のorder乗(^order, 1 << order)単位でメモリを割り当てる。先頭のページフレームに対応した struct page へのポインタを返す。
unsigned long __get_free_pages(gfp_mask,order): alloc_pages() と同様にメモリを割り当てる。ただし、リターンするのは、論理アドレス。
struct page *alloc_page(gfp_mask): 1ページ割り当て、struct page へのポインタを返す。
unsigned long __get_free_page(gfp_mask): alloc_page() と同様にメモリを割り当てる。割り当てたメモリの論理アドレスを返す。
unsigned long get_zeroed_page(gfp_mask): __get_free_page() と同様にメモリを割り当て、割り当てたメモリの論理アドレスを返す。メモリは、0 で埋められる。

struct pageへのポインタが得られた場合、メモリは割り当てられているが、論理アドレス不明なので、そのままではプログラムでアクセスできない。論理アドレスが必要なら、void *page_address(page)を使って struct pageへのポインタからアクセス可能な論理アドレスを得ることができる。

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

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

linux-3.6.8/include/linux/gfp.h

 332:	static inline struct page *
 333:	alloc_pages(gfp_t gfp_mask, unsigned int order)

 352:	extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);
 353:	extern unsigned long get_zeroed_page(gfp_t gfp_mask);

 366:	extern void __free_pages(struct page *page, unsigned int order);
 367:	extern void free_pages(unsigned long addr, unsigned int order);

 372:	#define free_page(addr) free_pages((addr), 0)

◆gfp_t gfp_mask

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

linux-3.6.8/include/linux/gfp.h

型説明

GFP_ATOMIC 高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(bottom half)で使う。

GFP_NOIO スリープ可、入出力不可。

GFP_NOFS スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。

GFP_KERNEL カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。

GFP_USER ユーザ空間用のメモリの通常の方法。スリープ可。

GFP_HIGHUSER HIGHMEMゾーンからの割当て。スリープ可。

GFP_DMA DMAゾーンからの割当て。デバイス・ドライバ等が使う。

このようなフラグが存在する最も重要な理由は、スリープする可能性があるかないかの違い。その他に、どのゾーンからメモリを割り当てるべきかを表すものがある。

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

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

物理フレームの割当てと開放を繰り返していくと、外部フラグメンテーション (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: フラグ。gfp_mask。スリープしても良いか良くないかやその他の属性を表す。以下の kmalloc()のフラグの選択参照。

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

◆kmalloc()のフラグの選択

状況	フラグ
プロセスのコンテキスト、スリープ可能	`GFP_KERNEL`
プロセスのコンテキスト、スリープ不可	`GFP_ATOMIC`
割込みハンドラ	`GFP_ATOMIC`
割込みハンドラ後半(Softirq,Tasklet,後述)	`GFP_ATOMIC`
DMA可能なメモリ、スリープ可能	`GFP_DMA\|GFP_KERNEL`
DMA可能なメモリ、スリープ不可	`GFP_DMA\|GFP_ATOMIC`

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

void *kmem_cache_alloc_node(struct kmem_cache *cachep,gfp_t flags, int node)

void kmem_cache_free(struct kmem_cache *cachep, void *b)

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

kmem_cache_alloc_node() は、メモリ・アクセスが不均質なマルチプロセッサ用。メモリを割り当てるという働きは、kmem_cache_alloc() と同じ。ただし、 node で指定されたプロセッサで高速にアクセスできるメモリに割り当てられる。

◆利用例(task_struct)

linux-3.6.8/kernel/fork.c

 122:	static struct kmem_cache *task_struct_cachep;
...
 251:	void __init fork_init(unsigned long mempages)
 252:	{
...
 258:	        task_struct_cachep =
 259:	                kmem_cache_create("task_struct", sizeof(struct task_struct),
 260:	                        ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);
...
 283:	}
...
 124:	static inline struct task_struct *alloc_task_struct_node(int node)
 125:	{
 126:	        return kmem_cache_alloc_node(task_struct_cachep, GFP_KERNEL, node);
 127:	}
 128:	
 129:	static inline void free_task_struct(struct task_struct *tsk)
 130:	{
 131:	        kmem_cache_free(task_struct_cachep, tsk);
 132:	}

名前は、"task_struct"
大きさは、sizeof(struct task_struct) バイト
ARCH_MIN_TASKALIGN は、8-16が多い。キャッシュがよく効くように構造体の先頭番地をずらす。
SLAB_PANIC により、メモリが割り当てられなければ、panic (システム全体をクラッシュ)する。SLAB_NOTRACK は、デバッグ用( デバッグのためのメモリのトラックの対象とはしない)。
コンストラクタは、なし(NULL)。
struct task_struct の割当ては、alloc_task_struct_node(node)が使われる。 node は、プロセッサの番号。
開放は、free_task_struct()。

◆/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 可能なメモリ。

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

★問題(401) struct page

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

★問題(402) 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) スラブアロケータ

問題(402) のプログラムを、スラブアロケータを使って書き換えなさい。すなわち、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: 2013/02/03 16:26:23

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