メモリ管理

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

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

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

■連絡事項

卒業予定の4年生に対する「特別措置」は、今年度から廃止されました。単位 が必要な人は、普通に試験を受けて下さい。

■今日の大事な話

■メモリ管理

◆目標

■物理メモリの管理

struct page page[]、物理メモリ

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

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

◆ページ構造体

linux-3.12.6/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;
...
 162:	        void *virtual;
...
 180:	}

◆ページ構造体のflags(主要部分)

linux-3.12.6/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.12.6/arch/x86/include/asm/page_types.h
   8:	#define PAGE_SHIFT      12
   9:	#define PAGE_SIZE       (_AC(1,UL) << PAGE_SHIFT)

linux-3.12.6/include/uapi/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 より大きい所。

zone、DMA、NORMAL、HIMEM

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

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

ページ・フレームは、物理メモリ。 Linux カーネル内では、次のような手続きで、割り当てる。 struct pageへのポインタが得られた場合、メモリは割り当てられているが、論 理アドレス不明なので、そのままではプログラムでアクセスできない。論理ア ドレスが必要なら、void *page_address(page)を使って struct pageへのポイ ンタからアクセス可能な論理アドレスを得ることができる。

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

linux-3.12.6/include/linux/gfp.h

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

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

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

 374:	#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.12.6/include/linux/gfp.h
説明
GFP_ATOMIC 高優先度。スリープ不可。割込み処理の前半(割り込みハンドラ、top half)や後半(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()のフラグの選択

状況 フラグ
プロセスのコンテキスト、スリープ可能 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、オブジェクト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.12.6/kernel/fork.c

 123:	static struct kmem_cache *task_struct_cachep;

 252:	void __init fork_init(unsigned long mempages)
 253:	{
...
 259:	        task_struct_cachep =
 260:	                kmem_cache_create("task_struct", sizeof(struct task_struct),
 261:	                        ARCH_MIN_TASKALIGN, SLAB_PANIC | SLAB_NOTRACK, NULL);
...
 284:	}

 125:	static inline struct task_struct *alloc_task_struct_node(int node)
 126:	{
 127:	        return kmem_cache_alloc_node(task_struct_cachep, GFP_KERNEL, node);
 128:	}
 129:	
 130:	static inline void free_task_struct(struct task_struct *tsk)
 131:	{
 132:	        kmem_cache_free(task_struct_cachep, tsk);
 133:	}

◆/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種類ある。

■ユーザ・プロセスの仮想メモリの実現

◆OSに求められる機能(オペレーティングシステムI復習)

x86 には、その他、Multics 由来の「セグメント」がある。Linux 等の複数アー キテクチャで動作する OS は、x86 依存の機能には依存しない形で設計される。

◆Unixにおけるメモリに関するシステム・コールとライブラリ

システム・コール ライブラリ その他

◆Unixにおけるプロセスのアドレス空間の基本的な構造

テキスト、データ、BSS、スタック

図? プロセスのアドレス空間の構造

◆実行形式の構造

Linux では、実行形式として ELF(Executable and Linkable Format) が使われ ている。ELF ファイルは、readelf コマンドや objdump で容を観察できる。

ELF ファイルは、ヘッダとセクションの並びからなる。重要なセクションに は、.text, .rodata, .data がある。

$ cat hello.c [←]
main()
{
        printf("hello, %s!\n","world");
}
$ cc -o hello hello.c [←]
$ file hello [←]
hello: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, not stripped
$ size hello [←]
   text		   data	      bss	    dec	    hex	filename
   1159		       252          8	       1419     58b	hello
$ readelf -S hello [←]
There are 30 section headers, starting at offset 0x7f4:

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .interp           PROGBITS        08048134 000134 000013 00   A  0   0  1
...
  [13] .text             PROGBITS        08048310 000310 00018c 00  AX  0   0 16
...
  [15] .rodata           PROGBITS        080484b8 0004b8 00001e 00   A  0   0  4
...
  [24] .data             PROGBITS        080496c8 0006c8 000004 00  WA  0   0  4
  [25] .bss              NOBITS          080496cc 0006cc 000008 00  WA  0   0  4
...
  [28] .symtab           SYMTAB          00000000 000ca4 000410 10     29  45  4
$ []

■Linuxにおけるユーザプロセスのアドレス空間の実装

◆アドレス空間とメモリ・エリア

利用者プロセスのプログラムは、線形な(linear)アドレス空間で仮想アドレス を使って機械語命令を読み出したり、データを読み書きする。 (x86 では、セグメンテーションも使えるので、線形ではないアドレス空間も可 能だが、Linux では、他のアーキテクチャとの兼ね合いもあり、線形な空間を 使う。)

線形なアドレス空間は、メモリ・エリア(memory area)(または、memory region、memory interval)に分割される。

◆task_struct構造体とmm_struct構造体

カーネル内では、プロセスのメモリは、次の構造体で表される。
linux-3.12.6/include/linux/sched.h

1023:	struct task_struct {
...
1091:	        struct mm_struct *mm, *active_mm;
...
1414:	};
tast_struct の mm フィールド

task_struct、mm_struct、vm_area_struct

図? プロセス関連のメモリの構造体

◆mm_struct構造体

linux-3.12.6/include/linux/mm_types.h
 326:	struct mm_struct {
 327:	        struct vm_area_struct * mmap;           /* list of VMAs */
 328:	        struct rb_root mm_rb;
 329:	        struct vm_area_struct * mmap_cache;     /* last find_vma result */
...
 339:	        pgd_t * pgd;
 340:	        atomic_t mm_users;                      /* How many users with user space? */
 341:	        atomic_t mm_count;                      /* How many references to "struct mm_struct" (users count as 1) */
 342:	        int map_count;                          /* number of VMAs */
...
 364:	        unsigned long start_code, end_code, start_data, end_data;
 365:	        unsigned long start_brk, brk, start_stack;
 366:	        unsigned long arg_start, arg_end, env_start, env_end;
...
 439:	};

◆vm_area_struct構造体

linux-3.12.6/include/linux/mm_types.h

 228:	struct vm_area_struct {
...
 231:	        unsigned long vm_start;         /* Our start address within vm_mm. */
 232:	        unsigned long vm_end;           /* The first byte after our end address
...
 236:	        struct vm_area_struct *vm_next, *vm_prev;
 237:	
 238:	        struct rb_node vm_rb;
...
 250:	        struct mm_struct *vm_mm;        /* The address space we belong to. */
 251:	        pgprot_t vm_page_prot;          /* Access permissions of this VMA. */
 252:	        unsigned long vm_flags;         /* Flags, see mm.h. */
...
 278:	        const struct vm_operations_struct *vm_ops;
...
 283:	        struct file * vm_file;          /* File we map to (can be NULL). */
...
 292:	};
vm_area_structのvm_flagsの値(include/linux/mm.h)
フラグ説明
VM_READ 読み込み可
VM_WRITE 書き込み可
VM_EXEC 実行可
VM_SHARED 共有されている
VM_GROWSDOWN アドレスが小さい方に伸びる
VM_GROWSUP アドレスが大きい方に伸びる
VM_DENYWRITE 書き込み不可。
VM_EXECUTABLE 実行可能。
VM_LOCKED ロックされている。
VM_DONTCOPY コピー不可
VM_DONTEXPAND 拡張不可。

◆プロセスのアドレス空間の実装

プロセスのアドレス空間 は、次のような領域に分割されて実装されている。

mm_struct、アドレス空間、vm_area、実行形式ファイル

図? プロセスのアドレス空間の実現

各領域は、次のように実装されている。
テキスト
機械語を置く。VM_EXEC 属性と VM_READ属性が付いている。書き込み禁止 で共有可能。mm_struct の start_code と end_code が、開始番地と終了番地 を保持する。
データ(初期値付き)
データを置く。VM_READ|VM_WRITE 属性が付いている(以下同様)。共有不 可。ファイルに初期値が含まている。
BSS(初期値無しデータ)
0 で初期化されるデータを置く。ファイルに初期値が含まれない。
ヒープ
データを置く。malloc() の原資(の1つ)。brk() や sbrk() システム・ コールで大きさが変更される。番地が大きい方に伸びる。mm_struct の start_brk とbrk が開始番地と終了番地を保持する。
スタック
関数呼び出しのスタックが置かれる。スタック・ポインタが指す。局所変 数や関数の戻り番地が置かれる。スタックポインタが下限を越えて小さくなる と、自動拡張されることがあるる

◆プロセスのアドレス空間のレイアウト(動的リンクライブラリ)

元の実行形式に由来するテキスト、データ、スタックの他に、動的リンク・ラ イブラリに由来するテキストやデータのためのメモリ・エリアが作られる。 /proc/PID/maps というファイルを見ると、その様子が分かる。
$ echo $$ [←]
3981
$ ls /proc/$$ [←]
attr             cpuset   fd        maps        oom_adj    smaps   task
auxv             cwd      io        mem         oom_score  stat    wchan
cmdline          environ  limits    mounts      root       statm
coredump_filter  exe      loginuid  mountstats  schedstat  status
$ cat /proc/$$/maps  [←]
00110000-00114000 r-xp 00000000 08:02 490576     /lib/libnss_dns-2.5.so
00114000-00115000 r--p 00003000 08:02 490576     /lib/libnss_dns-2.5.so
00115000-00116000 rw-p 00004000 08:02 490576     /lib/libnss_dns-2.5.so
...
08047000-080f5000 r-xp 00000000 08:02 481554     /bin/bash
080f5000-080fa000 rw-p 000ae000 08:02 481554     /bin/bash
080fa000-080ff000 rw-p 080fa000 00:00 0 
09d66000-09e25000 rw-p 09d66000 00:00 0          [heap]
...
bffdd000-bfff2000 rw-p bffe9000 00:00 0          [stack]
$ wc /proc/$$/maps  [←]
45 263 2920 /proc/3981/maps
$ []
/proc/PID/maps のフィールドの意味
  1. メモリ・セグメントの開始番地と終了番地。
  2. アクセス許可。r(read), w(write), x(executable), p(private), s(shared)
  3. オフセット
  4. ブロック・デバイスのメジャー番号とマイナー番号。 8:2 なら、メジャー番号が、8、マイナー番号が2の意味。 デバイスに結びついていない場合には、00:00 になる。
  5. ファイルのinode番号。
  6. ファイル名。
ブロック・デバイスには、メジャー番号とマイナー番号がある。各ファイルに は、inode 番号がある。これらの3つの番号がわかると、カーネル内ではファイ ルを特定できる。(同じ inode 番号のファイルは、1つのブロック・デバイス内 では、1個しかない。) ファイル名は不要だが、/proc/PID/maps では、人間にとって 分かりやすいようにわざわざ表示している。

ブロック・デバイスのメジャー番号とマイナー番号は、ls -l でわかる。

$ ls -l /dev/sda2 [←]
brw-r----- 1 root disk 8, 2 Jan 24 12:00 /dev/sda2
$ []
ファイルの inode 番号は、ls -i でわかる。
$ ls -li /bin/bash [←]
481554 -rwxr-xr-x 1 root root 735004 Jan 22  2009 /bin/bash
$ ls -li /lib/libnss_dns-2.5.so [←]
490576 -rwxr-xr-x 1 root root 21948 Oct 26 08:16 /lib/libnss_dns-2.5.so
$ []

■ページテーブル

◆仮想アドレスと物理アドレス

MMU による変換方法は、ページテーブルに保存される。

CPU、MMU、ページテーブル、メモリ

図? MMUによる仮想アドレスから物理アドレスへの変換

◆1段のページ・テーブル

仮想アドレスの構成の 。 1ページが4KB (4096, 0x1000)で、仮想アドレスが32ビットの時。

p(20ビット)+offset

図? 1段のページテーブル

ページテーブルは、次のような配列になる。
unsigned int page_table[0x100000];
この配列の要素は、ページ・フレームの先頭番地(物理アドレス)。

MMU(ハードウェア) は、このページテーブルを使って、次のようにして仮想ア ドレスから物理アドレスを求める。以下は、MMU の動きを C 言語で説明したも の。

unsigned long int physical_address( unsigned long int virtual v ) {
    unsigned long int p, page, offset;
    p = v >> 12;         // 32中、上位20ビット(32-12==20)の取り出し
    offset = v & 0xfff;  // 下位 12 ビットの取り出し
    page = page_table[p];
    return( page + offset );
}

mm_struct、page_table、page frame

図? 1段のページテーブル

注意: 白い部分は、0 が入っている。0 の部分は、ページ・フレームが割り当 てられていないことを意味する。0 を保持するためにも、メモリが必要である。

page_table[] は、0x100000 個 == 1024 * 1024 個 == 1M 個の要素からなる。 1要素が 4 バイト(32ビット) なら、4MB のメモリが必要になる。

◆多段のページ・テーブル

実際のプロセスでは、使われていない空間が圧倒的に多い。 1段のページテーブルでは、ページテーブルを保持するためのメモリが多くなってしまう。 多くのCPUでは、多段のページテーブルを採用している。 アドレス空間のうち、使われていない部分のポインタを NULL にする。 Linux では、4段のページテーブルを想定している。

仮想アドレスの構成の 。 1ページが4KB、仮想アドレスが32ビットの時の分割の例(他の分割方法も考えら れる)

5+5+5+5+12

図? 仮想アドレスの4つの部分への分割例

mm_struct、PGD、PUD、PMD、PTE、page frame

図? 4段のページテーブル

unsigned int pgd[0x20];

unsigned long int physical_address( unsigned long int virtual v ) {
    unsigned int *pud, *pmd, *pte, p, q, r, s, page, offset;
    p = v >> (32-5) ;
    q = (v >> (32-10)) & 0x1f;
    r = (v >> (32-15)) & 0x1f;
    s = (v >> (32-20)) & 0x1f;
    offset = v & 0xfff;
    pud = pgd[p];
    pmd = pud[q];
    pte = pmd[r];
    page = pte[s]
    return( page + offset );
}

◆x86のページ・テーブル

x86 では、従来、2段のページテーブルを用いている。次のように対応させている。

10+12+12

図? 仮想アドレスの3つの部分への分割例

mm_struct、pgd、pte、page frame。

図? x86の2段のページテーブル

◆x86のページ・テーブル(PAE有効)

x86 で PAE(Physical Address Extension)が有効の時には、次のようになる。 PAE を使うと、仮想アドレスは、32ビットであるが、物理アドレスは、36ビットまで使えるようになる。

■ページ・フォールト

メモリが割り当てられていない場所をプロセスがアクセスした時には、ページ・ フォールトが発生する。 関数do_page_fault() がこのような処理を行う。この関数は、権限外のアクセ ス、たとえば、書き込み禁止のメモリに書き込みを試みた場合のエラーも処理 する。

◆x86 do_page_fault()

linux-3.12.6/arch/x86/mm/fault.c

1225:	dotraplinkage void __kprobes
1226:	do_page_fault(struct pt_regs *regs, unsigned long error_code)
1227:	{
...
1231:	        __do_page_fault(regs, error_code);
...
1233:	}

 997:	static void __kprobes
 998:	__do_page_fault(struct pt_regs *regs, unsigned long error_code)
 999:	{
1000:	        struct vm_area_struct *vma;
1001:	        struct task_struct *tsk;
1002:	        unsigned long address;
1003:	        struct mm_struct *mm;
1004:	        int fault;
1005:	        unsigned int flags = FAULT_FLAG_ALLOW_RETRY | FAULT_FLAG_KILLABLE;
1006:	
1007:	        tsk = current;
1008:	        mm = tsk->mm;
1009:	
1010:	        /* Get the faulting address: */
1011:	        address = read_cr2();
...
1138:	        vma = find_vma(mm, address);
1139:	        if (unlikely(!vma)) {
1140:	                bad_area(regs, error_code, address);
1141:	                return;
1142:	        }
1143:	        if (likely(vma->vm_start <= address))
1144:	                goto good_area;
1145:	        if (unlikely(!(vma->vm_flags & VM_GROWSDOWN))) {
1146:	                bad_area(regs, error_code, address);
1147:	                return;
1148:	        }
...
1161:	        if (unlikely(expand_stack(vma, address))) {
1162:	                bad_area(regs, error_code, address);
1163:	                return;
1164:	        }
...
1170:	good_area:
1171:	        if (unlikely(access_error(error_code, vma))) {
1172:	                bad_area_access_error(regs, error_code, address);
1173:	                return;
1174:	        }
...
1181:	        fault = handle_mm_fault(mm, vma, address, flags);
...
1223:	}

◆handle_mm_fault()

../src/mm-memory.c.npr

3839:	int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct *vma,
3840:	                    unsigned long address, unsigned int flags)
3841:	{
...
3859:	        ret = __handle_mm_fault(mm, vma, address, flags);
3873:	        return ret;
3874:	}

3748:	static int __handle_mm_fault(struct mm_struct *mm, struct vm_area_struct *vma,
3749:	                             unsigned long address, unsigned int flags)
3750:	{
3751:	        pgd_t *pgd;
3752:	        pud_t *pud;
3753:	        pmd_t *pmd;
3754:	        pte_t *pte;
...
3759:	retry:
3760:	        pgd = pgd_offset(mm, address);
3761:	        pud = pud_alloc(mm, pgd, address);
3762:	        if (!pud)
3763:	                return VM_FAULT_OOM;
3764:	        pmd = pmd_alloc(mm, pud, address);
3765:	        if (!pmd)
3766:	                return VM_FAULT_OOM;
...
3834:	        pte = pte_offset_map(pmd, address);
3835:	
3836:	        return handle_pte_fault(mm, vma, address, pte, pmd, flags);
3837:	}

◆handle_pte_fault()

linux-3.12.6/mm/memory.c
3689:	static int handle_pte_fault(struct mm_struct *mm,
3690:	                     struct vm_area_struct *vma, unsigned long address,
3691:	                     pte_t *pte, pmd_t *pmd, unsigned int flags)
3692:	{
3693:	        pte_t entry;
...
3696:	        entry = *pte;
...
3698:	                if (pte_none(entry)) {
3699:	                        if (vma->vm_ops) {
3700:	                                if (likely(vma->vm_ops->fault))
3701:	                                        return do_linear_fault(mm, vma, address,
3702:	                                                pte, pmd, flags, entry);
3703:	                        }
3704:	                        return do_anonymous_page(mm, vma, address,
3705:	                                                 pte, pmd, flags);
3706:	                }
3707:	                if (pte_file(entry))
3708:	                        return do_nonlinear_fault(mm, vma, address,
3709:	                                        pte, pmd, flags, entry);
3710:	                return do_swap_page(mm, vma, address,
3711:	                                        pte, pmd, flags, entry);
...
3743:	}

◆赤黒木(red-black tree (rbtree))

赤黒木(red-black tree) は、平衡二分探索木(self-balancing binary search tree)の一種。 節は、赤と黒に分類される。

二分探索木とは、次のような二分木。 平衡木(balanced tree)、または、高さ平衡木(height-balanced tree)は、任意 の節で左右の高さの差が一定以下木。

Linux では、赤黒木をソートされた要素が並ぶリストを実現するために使っている。

◆Linux red-black treeの基本操作

型定義で、各要素に次の要素を含める。 検索
  1. 現在のノードとキーを比較
  2. 等しいなら見つかった
  3. キーが小さいなら左の枝へ
  4. キーが大きいなら右の枝へ
  5. 枝がなければキーは存在しない
挿入
  1. まず検索する。現在のノードと挿入したいデータのキーを比較する。
  2. キーが小さいなら左の枝を「親」にして検索を続ける。
  3. キーが大きいなら右の枝を「親」にして検索を続ける。
  4. キーが等しいならエラー(エラーにせず、重複を許すこともある)
  5. 子供がいない「親」が見つかる。
  6. 「親」から挿入したいデータへのリンクを作成する(rb_link_node())
  7. 平衡になるようにする(rebalancing, recoloring, rb_insert_color())

■課題2 メモリ管理

★問題(201) struct page

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

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

以下は、ユーザ空間でメモリを割当て、利用し、開放するプログラムの一部である。
struct s1 {
   /* 省略 */
};
利用
   struct s1 *p;
   p = malloc( sizeof(struct s1) );
   use( p );
   free( p );
このプログラムを、カーネル内で動かすことを想定してkmalloc() と kfree() を使って書き換えなさい。ただし、gfp のフラグとしては、GFP_KERNEL を使いなさい。
利用
   struct s1 *p;
   /*回答*/
   use( p );
   /*回答*/

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

問題(202) のプログラムを、スラブアロケータを使って書き換 えなさい。すなわち、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 );
   /*回答*/

★問題(204) 1段のページテーブル

仮想アドレスのサイズが32ビット、1ページの大きさが4KBとする。 次の3ページが割り当てられてしたとする。 1段のページテーブル を用いていた場合、ページテーブルの形と内容はどうなるか。簡単に図で書きなさい。 また、 ページテーブルに必要なメモリは何バ イトになるか。ページテーブルの1エントリのバイトは、4バイトとする。 なお、末端のページ・フレームに必要なメモリ(この場合は、3ページ、12KB)は、 ページテーブルに必要なメモリではないので、計算に入れない。

★問題(205) 2段のページテーブル

問題(204) で、次のような2段のページテーブル (「x86のページ・テーブル」と同じ) を用いていたとする。 この場合、ページテーブルの形と内容はどうなるか。簡単に図で書きなさい。 また、ページテーブルに必要なメモリは何バイトになるか。ページテーブル の1エントリのバイトは、上位のページテーブルも下位のページテーブルも4バ イトとする。
Last updated: 2014/01/31 17:18:37
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>