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

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

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

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

■連絡事項

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

■今日の大事な話

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

◆カーネル内のメモリ割当て(前回)

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

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

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

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

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

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

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

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

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

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

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

◆task_struct構造体とmm_struct構造体

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

1220:	struct task_struct {
...
1284:	        struct mm_struct *mm, *active_mm;
...
1572:	};
tast_struct の mm フィールド

task_struct、mm_struct、vm_area_struct

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

◆mm_struct構造体

linux-3.1.3/include/linux/mm_types.h

 266:	struct mm_struct {
 267:	        struct vm_area_struct * mmap;           /* list of VMAs */
 268:	        struct rb_root mm_rb;
 269:	        struct vm_area_struct * mmap_cache;     /* last find_vma result */
...
 280:	        pgd_t * pgd;
 281:	        atomic_t mm_users;                      /* How many users with user space? */
 282:	        atomic_t mm_count;                      /* How many references to "struct mm_struct" (users count as 1) */
 283:	        int map_count;                          /* number of VMAs */
...
 288:	        struct list_head mmlist;                /* List of maybe swapped mm's.  These are globally strung
 289:	                                                 * together off init_mm.mmlist, and are protected
 290:	                                                 * by mmlist_lock
 291:	                                                 */
...
 299:	        unsigned long start_code, end_code, start_data, end_data;
 300:	        unsigned long start_brk, brk, start_stack;
 301:	        unsigned long arg_start, arg_end, env_start, env_end;
...
 365:	};

◆vm_area_struct構造体

linux-3.1.3/include/linux/mm_types.h

 178:	struct vm_area_struct {
 179:	        struct mm_struct * vm_mm;       /* The address space we belong to. */
 180:	        unsigned long vm_start;         /* Our start address within vm_mm. */
 181:	        unsigned long vm_end;           /* The first byte after our end address
 182:	                                           within vm_mm. */
 183:	
 184:	        /* linked list of VM areas per task, sorted by address */
 185:	        struct vm_area_struct *vm_next, *vm_prev;
 186:	
 187:	        pgprot_t vm_page_prot;          /* Access permissions of this VMA. */
 188:	        unsigned long vm_flags;         /* Flags, see mm.h. */
 189:	
 190:	        struct rb_node vm_rb;
...
 219:	        const struct vm_operations_struct *vm_ops;
...
 222:	        unsigned long vm_pgoff;         /* Offset (within vm_file) in PAGE_SIZE
 223:	                                           units, *not* PAGE_CACHE_SIZE */
 224:	        struct file * vm_file;          /* File we map to (can be NULL). */
 225:	        void * vm_private_data;         /* was vm_pte (shared mem) */
...
 233:	};
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.1.3/arch/x86/mm/fault.c

 987:	dotraplinkage void __kprobes
 988:	do_page_fault(struct pt_regs *regs, unsigned long error_code)
 989:	{
 990:	        struct vm_area_struct *vma;
 991:	        struct task_struct *tsk;
 992:	        unsigned long address;
 993:	        struct mm_struct *mm;
 994:	        int fault;
 995:	        int write = error_code & PF_WRITE;
 996:	        unsigned int flags = FAULT_FLAG_ALLOW_RETRY | FAULT_FLAG_KILLABLE |
 997:	                                        (write ? FAULT_FLAG_WRITE : 0);
 998:	
 999:	        tsk = current;
1000:	        mm = tsk->mm;
...
1003:	        address = read_cr2();
...
1119:	        vma = find_vma(mm, address);
...
1120:	        if (unlikely(!vma)) {
1121:	                bad_area(regs, error_code, address);
1122:	                return;
1123:	        }
1124:	        if (likely(vma->vm_start <= address))
1125:	                goto good_area;
1126:	        if (unlikely(!(vma->vm_flags & VM_GROWSDOWN))) {
1127:	                bad_area(regs, error_code, address);
1128:	                return;
1129:	        }
...
1142:	        if (unlikely(expand_stack(vma, address))) {
1143:	                bad_area(regs, error_code, address);
1144:	                return;
1145:	        }
...
1151:	good_area:
1152:	        if (unlikely(access_error(error_code, vma))) {
1153:	                bad_area_access_error(regs, error_code, address);
1154:	                return;
1155:	        }
...
1162:	        fault = handle_mm_fault(mm, vma, address, flags);
...
1195:	}

◆handle_mm_fault()

linux-3.1.3/mm/memory.c

3442:	int handle_mm_fault(struct mm_struct *mm, struct vm_area_struct *vma,
3443:	                unsigned long address, unsigned int flags)
3444:	{
3445:	        pgd_t *pgd;
3446:	        pud_t *pud;
3447:	        pmd_t *pmd;
3448:	        pte_t *pte;
...
3461:	        pgd = pgd_offset(mm, address);
3462:	        pud = pud_alloc(mm, pgd, address);
3463:	        if (!pud)
3464:	                return VM_FAULT_OOM;
3465:	        pmd = pmd_alloc(mm, pud, address);
3466:	        if (!pmd)
3467:	                return VM_FAULT_OOM;
...
3501:	        pte = pte_offset_map(pmd, address);
3502:	
3503:	        return handle_pte_fault(mm, vma, address, pte, pmd, flags);
3504:	}

◆handle_pte_fault()

linux-3.1.3/mm/memory.c
3386:	int handle_pte_fault(struct mm_struct *mm,
3387:	                     struct vm_area_struct *vma, unsigned long address,
3388:	                     pte_t *pte, pmd_t *pmd, unsigned int flags)
3389:	{
3390:	        pte_t entry;
...
3393:	        entry = *pte;
...
3395:	                if (pte_none(entry)) {
3396:	                        if (vma->vm_ops) {
3397:	                                if (likely(vma->vm_ops->fault))
3398:	                                        return do_linear_fault(mm, vma, address,
3399:	                                                pte, pmd, flags, entry);
3400:	                        }
3401:	                        return do_anonymous_page(mm, vma, address,
3402:	                                                 pte, pmd, flags);
3403:	                }
3404:	                if (pte_file(entry))
3405:	                        return do_nonlinear_fault(mm, vma, address,
3406:	                                        pte, pmd, flags, entry);
3407:	                return do_swap_page(mm, vma, address,
3408:	                                        pte, pmd, flags, entry);
...
3437:	}

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

★問題(501) /proc/PID/maps

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

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

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

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

問題(502) で、次のような2段のページテーブル (「x86のページ・テーブル」と同じ) を用いていたとする。 この時、ページテーブルに必要なメモリは何バイトになるか。ページテーブル の1エントリのバイトは、上位のページテーブルも下位のページテーブルも4バ イトとする。
Last updated: 2012/02/07 17:26:15
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>