Page Table は
- address space の複数化 (kernel, user space)
- memory の保護, isolation
- misc： user の stack overflow を unmapped page を挟むことで detect など
を実現する
Paging Hardware (mmu.h)
1ページは 4K byte.
概念的には 2^20 個の page table entry (PTE) があり、それぞれがページとそのフラグを表す
実際は 2^10, 2^10 の二段階のテーブル。
%CR3 が page directory を指す。page directory の各エントリ (4 byte) は一つの page table page を指す。
page table page の各エントリ (PTE) の値が va の下位ビットと合わせて 物理 address を指す。
例
va: | A(10) | B(10) | C(12) | とする。
%CR3 + 4A が page dir entry | D(20) | flag'(12) | を指す。
| D(20) | B(10) | 00 | が PTE | E(20) | flag(12) | を指す。
| E(20) | C(12) | が va が指す pa である。
flag は、P(present), W(writable), U(user accessible) など
page directory 自体もひとつのページであって、2^10 個の int を持っているから 4M ぴったり。
page table page も同様。
Kernel virtual memory
------------------------ <- 4G
| Mem mapped IO RW |
------------------------ <- 4G - 32M = DEVSPACE
| unused |
------------------------ <- KERNBASE + PHYSTOP (=224M)
| free memory RW | `kinit2` で free
------------------------ <- KERNBASE + 4M
| free memory RW | `kinit1` で free
------------------------ <- `end`
| kern data RW |
------------------------ <- `data`
| kern text, rodata R |
------------------------ <- KERNBASE + 1M = KERNLINK
| Mem mapped I/O RW |
------------------------ <- KERNBASE = 2G
PHYSTOP は物理メモリの量 (決め打ち)
上側の Mem mapped IO は同じ物理アドレスにマップする (direct map)
それ以外は KERNBASE 引いたところにマップする
これにより、カーネルからは va, pa の変換が容易。単に ±KERNBASE するだけ
Creating address space
実装的には、page が free <-> freelist という linked list にエントリが存在
freelist の各エントリは、その page 自体の場所に置かれる
kfree(va v) は v にエントリをつくり、freelist に追加する. ちなみに freelist は spin lock で守る.
kalloc は freelist の先頭をあげるだけ
main に来た時点では 4M しか map されていなくて、freelist は空。新しい page table の場所を得るために、まず end:KERNBASE+4M を free する。(kinit1)
続いて kalloc しながら上記のマッピングが指定された page table を作成し、それにスイッチする (kvmalloc)
最後に +4M:+PHYSTOP も kfree してセットアップ完了(kinit2)
User part of an address space
----- <- 2G
Heap (はじめは0)
Stack: 4M で固定
Stack guard: 4M
Data
Text
----- <- 0
とする。stack には、argv, argc, dummy return value (for _start?) がつまれる
argv[0]の値, ..., argv[0], ..., argv, argc, 0xFFFFFFF という感じ
exec の実装:
- 新しい page table を
setupkvmでつくる。(= カーネル部分は同じようにマッピングする) - kalloc しながら上のような low address からのマッピングを追加
- stack guard は U フラグを外しておく
- ELF binary の text, data を貼る
- user va から pa を経由して kernel va への変換をし、そこに貼る
- そのプロセス以外の場所に貼られたらやばいのでしっかりチェック
-
p->gpdirを 新しい page table に切り替え -
p->tf(trap frame) の eip <- elf.entry, esp を適切に設定 -
switchuvm(p)で page table を切り替え - 古い page table、その指す user addresses を free
sbrk (heap を増やす/減らすやつ) の実装:
p->sz, p->pgdir を操作して、必要があれば mapping を追加、削除すればよい
操作後、古い mapping が TLB に残ることを防ぐため、switchuvm を再び呼んで %CR3 を設定し直す
削除した mapping が残っていると、remap された他のCPUのプロセスのメモリを見れてしまう
Real world
xv6 に欠けているもの
- Demand paging from disk
- CoW fork
- Shared memory
- Lazy page allocation
- Automatically extending stack
- RAMサイズの推定