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

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

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

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

■今日の大事な話

■メモリ管理

◆目標

■物理メモリの管理

struct page page[]、物理メモリ

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

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

◆ページ構造体

linux-3.1.3/include/linux/mm_types.h

  40:	struct page {
...
  42:	        unsigned long flags;
...
  44:	        struct address_space *mapping;
...
  89:	                                atomic_t _count;
...
  95:	        struct list_head lru;
...
 101:	                unsigned long private;
...
 126:	        void *virtual;
...
 140:	}

◆ページ構造体のflags

linux-3.1.3/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 開放すべきページ

◆メモリ・ゾーン

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

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

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

zone、DMA、NORMAL、HIMEM

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

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

ページ・フレームは、物理メモリ。 Linux カーネル内では、次のような手続きで、割り当てる。 次のような手続きで、メモリを開放する。
linux-3.1.3/include/linux/gfp.h

 296:	static inline struct page *
 297:	__alloc_pages(gfp_t gfp_mask, unsigned int order,
 298:	                struct zonelist *zonelist)

 344:	extern unsigned long __get_free_pages(gfp_t gfp_mask, unsigned int order);

 324:	static inline struct page *
 325:	alloc_pages(gfp_t gfp_mask, unsigned int order)

 358:	extern void __free_pages(struct page *page, unsigned int order);
 359:	extern void free_pages(unsigned long addr, unsigned int order);
 363:	#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() に由来する。
説明
GFP_ATOMIC 高優先度。スリープ不可。割込みハンドラや下半分(bottom half)で使う。
GFP_NOIO スリープ可、入出力不可。
GFP_NOFS スリープ化、入出力可、ファイル操作不可。ファイルシステムの実装で使う(他のファイルシステムの操作を開始しない)。
GFP_KERNEL カーネル用メモリ通常の方法。スリープ可。ユーザ・プロセスのコンテキストで使う。
GFP_USER ユーザ空間用のメモリの通常の方法。スリープ可。
GFP_HIGHUSER HIGHMEMゾーンからの割当て。スリープ可。
GFP_DMADMAゾーンからの割当て。デバイス・ドライバ等が使う。
このようなフラグが存在する最も重要な理由は、スリープする可能性があるか ないかの違い。 その他に、どのゾーンからメモリを割り当てるべきかを表すものがある。

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

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

◆Buddyシステム

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

zone、free_area、page

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

zone、free_area、page

図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 0 (4KB) に、6 個、 2 1 (8KB) に、5 個、・・・、2 10 に2個の空きがある。 外部フラグメンテーションが起きると、大きな塊が少なくなる。

■kmallocとkfree

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

◆kmalloc()

C言語のユーザ空間で使えるライブラリ malloc() に似ている。
void *kmalloc(size_t size, gfp_t flags)
引数 結果: 最低限、size 分のメモリを割り当て、その先頭の番地(カーネル内の仮 想アドレス)を返す。割り当てられたメモリは、物理的にも連続になる。割当 てできない時には、NULL を返す。

◆kmalloc()のフラグの選択

◆kfree()

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

◆vmalloc()とvfree()

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

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

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

◆free list方式とその問題点

構造体の割当てには、free list 方式が使われることもある。 この方法では、メモリに空きがあっても、解放できるか簡単にはわからない。

free list、オブジェクト4個

図? フリーリストの例

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

free list、オブジェクト4個

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

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

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

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

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

ページフレーム3つ、スラブ1つ、オブジェクト6つ

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

◆kmem_cache_create()

struct kmem_cache *
kmem_cache_create (const char *name, size_t size, size_t align,
        unsigned long flags, void (*ctor)(void *))
引数 結果: 成功した時には、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.1.3/kernel/fork.c

 115:	static struct kmem_cache *task_struct_cachep;
...
 210:	void __init fork_init(unsigned long mempages)
 211:	{
...
 217:	        task_struct_cachep =
 218:	                kmem_cache_create("task_struct", sizeof(struct task_struct),
 219:	                        ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);
...
 242:	}

 111:	# define alloc_task_struct_node(node)           \
 112:	                kmem_cache_alloc_node(task_struct_cachep, GFP_KERNEL, node)
 113:	# define free_task_struct(tsk)                  \
 114:	                kmem_cache_free(task_struct_cachep, (tsk))

◆/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
% []
スラブ・アロケータには、2種類ある。

■クイズ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: 2012/02/07 17:11:59
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>