メモリ管理、アドレス空間、ページテーブル

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

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

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

■連絡事項

卒業予定の４年生に対する特別措置として、2月9日火曜日6時間目 (16:45-18:00)に試験をすることを検討しています。対象者は、授業終了後、前に集まって下さい。

■今日の大事な話

アドレス空間
ページテーブル

■前回資料

◆kmem_cache_create()

印刷資料は、先週配布済み。

■ユーザ・プロセスのメモリ

カーネル内のメモリ割当て

alloc_pages(),alloc_page(),free_pages(): ページ単位
kmalloc(), kfree(): malloc(), free() と類似の API
kmem_cache_create(), kmem_cache_alloc(), kmem_cache_free(): スラブ・アロケータ

ユーザ空間のメモリ割当て

execve() で、アドレス空間を先に割り当てる
メモリは、最初にアクセスされた時に割り当てる
fork() では、Copy-on-write で共有する。最初の書き込みの時に割り当てる。

◆アドレス空間

利用者プロセスのプログラムは、線形な(linear)アドレス空間で仮想アドレスを使って機械語命令を読み出したり、データを読み書きする。

32ビットシステムで、0x00000000-0xffffffff
64ビットシステムで、0x00000000-0xffffffffffffffff (実際には、もう少し小さい。0x00ffffffffffff くらい。)

(x86 では、セグメンテーションも使えるので、線形ではないアドレス空間も可能だが、Linux では、他のアーキテクチャとの兼ね合いもあり、線形な空間を使う。)

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

メモリ・エリアには、開始番地と終了番地（または大きさ）がある。
メモリ・エリア毎に保護方法を変えられる。テキストを読み込み専用 (read-only)にするなど。
メモリ・エリア毎にファイルに対応させられる。

◆task_struct構造体とmm_struct構造体

カーネル内では、プロセスのメモリは、次の構造体で表される。

構造体 task_struct: 1プロセスで1個。
構造体 mm_struct: 普通、1プロセスで1個。(複数プロセスで共有されていることがある。)
構造体 vm_area: 1プロセスで複数。

include/linux/sched.h
1166: struct task_struct {
...
1221:         struct mm_struct *mm, *active_mm;
...
1483: };

tast_struct の mm フィールド

init_mm() で初期化される。
copy_mm() でコピーされる。(fork の時)
exit_mm() で後始末。

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

◆mm_struct構造体

include/linux/mm_types.h
 202: struct mm_struct {
 203:         struct vm_area_struct * mmap;           /* list of VMAs */
 204:         struct rb_root mm_rb;
 205:         struct vm_area_struct * mmap_cache;     /* last find_vma result */
...
 214:         pgd_t * pgd;
 215:         atomic_t mm_users;                      /* How many users with user space? */
 216:         atomic_t mm_count;                      /* How many references to "struct mm_struct" (users count as 1) */
 217:         int map_count;                          /* number of VMAs */
 218:         struct rw_semaphore mmap_sem;
 219:         spinlock_t page_table_lock;             /* Protects page tables and some counters */
 220: 
 221:         struct list_head mmlist;                /* List of maybe swapped mm's.  These are globally strung
 222:                                                  * together off init_mm.mmlist, and are protected
 223:                                                  * by mmlist_lock
 224:                                                  */
...
 237:         unsigned long start_code, end_code, start_data, end_data;
 238:         unsigned long start_brk, brk, start_stack;
 239:         unsigned long arg_start, arg_end, env_start, env_end;
...
 289: };

mmap: vm_area_struct の先頭を保持する。
mm_rb: メモリエリアを高速に探すための red-black tree を保持する。
mmap_cache: メモリ参照の局所生(locality)を生かして高速化するためのもの。
pgd: page global drectory へのポインタ。後述。
mm_users: 共有されている場合、そのプロセスの数。普通は、1。
mm_count: この構造体の参照カウンタ。0ならどのオブジェクトがも指されていない。
mm_list: mm_struct 構造体のリストを作るためのフィールド。
start_code, end_code: テキスト・セグメントの開始番地と終了番地。
start_brk, brk: ヒープの開始番地と終了番地。
start_stack: スタックの開始番地。
arg_start, arg_end: 引数の開始番地と終了番地。
env_start, env_end: 環境変数の開始番地と終了番地。

◆vm_area_struct構造体


 134: struct vm_area_struct {
 135:         struct mm_struct * vm_mm;       /* The address space we belong to. */
 136:         unsigned long vm_start;         /* Our start address within vm_mm. */
 137:         unsigned long vm_end;           /* The first byte after our end address
 138:                                            within vm_mm. */
...
 141:         struct vm_area_struct *vm_next;
...
 144:         unsigned long vm_flags;         /* Flags, see mm.h. */
...
 146:         struct rb_node vm_rb;
...
 174:         struct vm_operations_struct * vm_ops;
...
 177:         unsigned long vm_pgoff;         /* Offset (within vm_file) in PAGE_SIZE
 178:                                            units, *not* PAGE_CACHE_SIZE */
 179:         struct file * vm_file;          /* File we map to (can be NULL). */
 180:         void * vm_private_data;         /* was vm_pte (shared mem) */
...
 189: };

vm_mm: 親の mm_struct 構造体へのポインタ
vm_start, vm_end: メモリ・エリアの開始番地と終了番地。
vm_next: 同じ mm_struct 内で、次の vm_area_struct 構造体を指す。
vm_flags: フラグ。下の表参照。
vm_rb: red-black tree のノードとなるためのデータ。
vm_ops: 関数へのポインタ。opsは、operations。open, close, unmap　を含む。
vm_file: 対応しているファイル。

vm_area_structのvm_flagsの値
フラグ	説明
VM_READ	読み込み可
VM_WRITE	書き込み可
VM_EXEC	実行可
VM_SHARED	共有されている
VM_GROWSDOWN	アドレスが小さい方に伸びる
VM_GROWSUP	アドレスが大きい方に伸びる
VM_DENYWRITE	書き込み不可。
VM_EXECUTABLE	実行可能。
VM_LOCKED	ロックされている。
VM_DONTCOPY	コピー不可
VM_DONTEXPAND	拡張不可。

◆プロセスのアドレス空間のレイアウト(実行形式のELFファイル)

プロセスの実行形式は、 ELF 形式(2009年12月1日の資料参照)。

重要なセクション
.text	機械語命令
.data	初期化された大域変数やstatic変数
.rodata	(.dataに置くべきもののうち)読み読み専用のもの)
.bss	初期化されない大域変数やstatic変数(OSが0に初期化)
.symtab	シンボル・テーブル
.strtab	文字列のテーブル。シンボル・テーブルの内容の文字列。

これが、メモリにマップされると、次のようなメモリ・エリアになる。

テキスト: 機械語を置く。exec 属性と read 属性をつける。mm_struct の start_code と end_code が、開始番地と終了番地を保持する。
データ: read/read 属性をつける。共有不可。mm_struct の start_data と end_data が、開始番地と終了番地を保持する。初期化されたデータは、ELF ファイルから読み込まれる。初期化されていないデータは、OS が 0 で初期化する。
ヒープ: malloc() の原資(の１つ)。brk() や sbrk() システム・コールで大きさが変更される。番地が大きい方に伸びる。 mm_struct の start_brk と brk が開始番地と終了番地を保持する。
スタック: 関数呼び出しのスタックが置かれる。スタック・ポインタが指す。局所変数や関数の戻り番地が置かれる。

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

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

その他に、動的リンク・ライブラリによりメモリ・エリアが作られる。

% echo $$ 
29068
% ls /proc/$$ 
attr     coredump_filter  exe  limits    mem         root   statm   wchan
auxv     cwd              fd   loginuid  mounts      smaps  status
cmdline  environ          io   maps      mountstats  stat   task
% head /proc/$$/maps 
00111000-00115000 r-xp 00000000 08:02 8454184    /lib/libnss_dns-2.3.4.so
00115000-00116000 r-xp 00003000 08:02 8454184    /lib/libnss_dns-2.3.4.so
00116000-00117000 rwxp 00004000 08:02 8454184    /lib/libnss_dns-2.3.4.so
00117000-0011a000 r-xp 00000000 08:02 2332418    /usr/lib/gconv/EUC-JP.so
0011a000-0011c000 rwxp 00002000 08:02 2332418    /usr/lib/gconv/EUC-JP.so
0024a000-00259000 r-xp 00000000 08:02 8454169    /lib/libresolv-2.3.4.so
00259000-0025a000 r-xp 0000f000 08:02 8454169    /lib/libresolv-2.3.4.so
0025a000-0025b000 rwxp 00010000 08:02 8454169    /lib/libresolv-2.3.4.so
0025b000-0025d000 rwxp 0025b000 00:00 0 
00280000-00289000 r-xp 00000000 08:02 8454260    /lib/libnss_files-2.3.4.so
% tail /proc/$$/maps 
08048000-0808f000 r-xp 00000000 08:02 4685902    /bin/tcsh
0808f000-08093000 rw-p 00047000 08:02 4685902    /bin/tcsh
08093000-080c3000 rw-p 08093000 00:00 0 
086c5000-08790000 rw-p 086c5000 00:00 0 
b7c69000-b7d4c000 r--p 01bba000 08:02 147457     /usr/lib/locale/locale-archive
b7d4c000-b7f4c000 r--p 00000000 08:02 147457     /usr/lib/locale/locale-archive
b7f4c000-b7f4e000 rw-p b7f4c000 00:00 0 
b7f5d000-b7f63000 r--s 00000000 08:02 2326613    /usr/lib/gconv/gconv-modules.cache
bfe79000-c0000000 rw-p bfe79000 00:00 0 
ffffe000-fffff000 r-xp 00000000 00:00 0 
% wc /proc/$$/maps 
45 261 2975 /proc/29068/maps
%

/proc/PID/maps のフィールドの意味

メモリ・セグメントの開始番地と終了番地。
アクセス許可。r(read), w(write), x(executable), p(private), s(shared)
ブロック・デバイスのメジャー番号とマイナー番号。8:2 なら、メジャー番号が、8、マイナー番号が2の意味。
```
% ls -l /dev | egrep '8,.*2' 
brw-------  1 root root     8,   2 Jan  5 18:38 root
brw-rw----  1 root disk     8,   2 Jan  5 18:38 sda2
% 
```
デバイスに結びついていない場合には、00:00 になる。

ファイルのinode番号。例。

% ls -l /lib/libnss_dns-2.3.4.so 
-rwxr-xr-x  1 root root 22524 Jan 10  2009 /lib/libnss_dns-2.3.4.so
% ls -li /lib/libnss_dns-2.3.4.so 
8454184 -rwxr-xr-x  1 root root 22524 Jan 10  2009 /lib/libnss_dns-2.3.4.so
%

ファイル名。

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

メモリには、物理アドレスがふられている。
ユーザ・プロセスが実行されると、CPUは、仮想アドレス(virtual address) を出力する。
仮想アドレスのうち、上位は、MMU (MMU) により変換する。
仮想アドレスのうち、下位(ページサイズ分)は、そのままメモリに送られる。

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

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

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

仮想アドレスの構成の例。1ページが4KBで、仮想アドレスが32ビットの時。

上位20ビット: ページテーブルのインデックス
下位12ビット: ページ内オフセット

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

ページテーブルは、次のような配列になる。

unsigned int page_table[0x100000];

unsigned long int physical_address( unsigned long int virtual v ) {
    p = v >> 12;
    q = v & 0xfff;
    return( page_table[p] + q );
}

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

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

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

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

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

上位1ビット-5ビット: PGDのインデックス(5ビット)
上位5ビット-10ビット: PUDのインデックス(5ビット)
上位11ビット-15ビット: PMDのインデックス(5ビット)
上位16ビット-20ビット: ptのインデックス(5ビット)
下位12ビット: ページ内オフセット(12ビット)

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

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

PGD: Page Global Directory
PUD: Page Upper Directory
PMD: Page Middle Directory
Page Table Entryの配列 (pte の配列)

unsigned int pgd[0x20];

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

◆x86のページ・テーブル

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

p が 10 ビット
q が 0 ビット
r が 0 ビット
s が 10 ビット
t が 12 ビット

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

p が 2 ビット
q が 0 ビット
r が 9 ビット
s が 9 ビット
t が 12 ビット

■クイズ7 メモリ管理、アドレス空間、ページテーブル

★問題(701) /proc/`PID`/maps

/proc/PID/mapsの内容は、このページの中でどの構造体のリストを表示したものと考えられるか。次の点を答えなさい。

リストの起点を保持している構造体の名前とフィールド
リストにつながれている構造体の名前

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

仮想アドレスのサイズが32ビット、1ページの大きさが4KBとする。次の３ページが割り当てられてしたとする。

0x00000000 から 0x00000fff まで
0x00001000 から 0x00001fff まで
0xfffff000 から 0xffffffff まで

1段のページテーブルを用いていた場合、ページテーブルに必要なメモリは何バイトになるか。ページテーブルの1エントリのバイトは、4バイトとする。

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

問題(702) で、次のような2段のページテーブルを用いていたとする。

上位10ビット
上位11ビット-20ビット

この時、ページテーブルに必要なメモリは何バイトになるか。ページテーブルの1エントリのバイトは、上位のページテーブルも下位のページテーブルも4バイトとする。

Last updated: 2010/02/02 03:48:53

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