メモリ管理、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 研究室紹介

■今日の大事な話

■メモリ管理

◆目標

■物理メモリの管理

◆ページ構造体

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:	};
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))

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

ページ・フレームは、物理メモリ。 Linux カーネル内では、次のような手続きで、割り当てる。gfp_mask について は後述する。 次のような手続きで、メモリを開放する。
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 で使われている外部フラグメンテーションを起 こしにくいメモリ割当てアルゴリズム。

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()のフラグ(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_DMADMAゾーンからの割当て。デバイス・ドライバ等が使う。
このようなフラグが存在する必要性。

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

◆利用例(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))

◆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:	};

slabs_partial、slab、slab

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

◆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、スラブ、

図? スラブのリスト

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

★問題(401) struct page

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

★問題(402) Buddyシステム

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

★問題(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 );
   /*回答*/

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

問題(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>