本Labでは、JOSカーネル向けにメモリ管理コードを実装する。物理メモリの割り当てを4096バイト単位（ページ）で行うアロケータと、仮想メモリの管理機能を開発する。

準備

Lab 1のブランチにLab 2のコードをマージする。新たに追加されるファイルは以下の通り:

• inc/memlayout.h
• kern/pmap.c
• kern/pmap.h
• kern/kclock.h
• kern/kclock.c

特にmemlayout.hとpmap.hには本Labで頻繁に参照する定義が含まれる。

Part 1: 物理ページ管理

OSは物理メモリの使用状況を追跡する必要がある。JOSではPCの物理メモリを4KB単位のページで管理し、struct PageInfoのチェーンで空きページを管理する。このアロケータを先に完成させてから仮想メモリの実装に進む（ページテーブル用の物理メモリ確保が必要なため）。

Exercise 1

kern/pmap.c内の以下の関数を実装する（指定された順序に従う）:

• boot_alloc()
• mem_init()（check_page_free_list(1)の呼び出しまで）
• page_init()
• page_alloc()
• page_free()

check_page_free_list()およびcheck_page_alloc()がテストに合格するようにコードを修正する。

boot_alloc の実装

カーネル起動直後はページテーブルが整っていないため、簡易アロケータでメモリを確保する。リンカが定義するendシンボルの直後から使用開始し、nextfreeを進めながら割り当てる。

if (n == 0)
    return nextfree;

result = nextfree;
nextfree = ROUNDUP(nextfree + n, PGSIZE);

if ((uint32_t)nextfree - KERNBASE > npages * PGSIZE)
    panic("boot_alloc: out of memory");

return result;

mem_init の実装（最初の部分）

struct PageInfoの配列を確保する:

uint32_t page_array_size = npages * sizeof(struct PageInfo);
pages = (struct PageInfo *) boot_alloc(page_array_size);
memset(pages, 0, page_array_size);

page_init の実装

物理メモリのレイアウトに従い、空きページと使用中ページを区別する。使用中と見なすページ:

• ページ0（リアルモードIDT・BIOS構造体）
• I/Oホール（IOPHYSMEM〜EXTPHYSMEM）
• カーネルコード領域（EXTPHYSMEM〜boot_alloc(0)が示す物理アドレス）

それ以外を空きページとしてpage_free_listに追加する。

page_alloc の実装

空きリストから先頭のPageInfoを取り出し、ALLOC_ZEROフラグが指定されていればページをゼロクリアする。

page_free の実装

解放されたページをpage_free_listに戻す。

テストが合格することを確認する。なお、kern/init.c内のmem_init()呼び出しが正しいか注意する（マージミスに注意）。

Part 2: 仮想メモリ

Exercise 2

x86の保護モードにおけるセグメンテーションとページ変換を理解する。

仮想アドレス・線形アドレス・物理アドレス

Cのポインタは仮想アドレス（オフセット部分）を指す。JOSではuintptr_tが仮想アドレス、physaddr_tが物理アドレスを表す型として使われる。

Exercise 3

QEMUモニタのxpコマンドとGDBのxコマンドで、仮想アドレス0xf0100000と物理アドレス0x100000のメモリ内容が一致することを確認する。

参照カウント

物理ページの多重マッピングを管理するため、pp_refで参照カウントを保持する。原則としてUTOPより下のページテーブルエントリが参照する回数だけカウントする。

ページテーブル管理

Exercise 4

kern/pmap.c内の以下の関数を実装する:

• pgdir_walk()
• boot_map_region()
• page_lookup()
• page_remove()
• page_insert()

pgdir_walk

与えられた仮想アドレスに対応するPTEへのポインタを返す。中間ページテーブルが存在せずcreateが真なら新たに割り当てる。

uint32_t pdx = PDX(va);
pte_t *pde = &pgdir[pdx];
if (*pde & PTE_P) {
    // ページテーブル既存
    return (pte_t *) KADDR(PTE_ADDR(*pde)) + PTX(va);
} else if (create) {
    struct PageInfo *pp = page_alloc(ALLOC_ZERO);
    if (!pp) return NULL;
    pp->pp_ref++;
    pte_t *pgtable_va = (pte_t *) page2kva(pp);
    *pde = page2pa(pp) | PTE_P | PTE_W | PTE_U;
    return &pgtable_va[PTX(va)];
} else {
    return NULL;
}

boot_map_region

連続する仮想アドレス範囲に物理アドレス範囲をマッピングする（起動時のみ使用）。

page_lookup

仮想アドレスに対応する物理ページのPageInfoを返す。PTEのアドレスをpte_storeに格納することもできる。

page_insert

物理ページを仮想アドレスにマッピングする。以前のマッピングがあればpage_removeで削除する。

page_remove

マッピングを解除し、参照カウントを減らす。TLB無効化も行う。

check_page()が成功することを確認する。

Part 3: カーネルアドレス空間

JOSは32ビット線形アドレス空間を2つに分割する。ユーザ環境はULIMより下の領域を使用し、カーネルは上位256MBを管理する。

Exercise 5

mem_init()でcheck_page()呼び出し以降のコードを実装し、check_kern_pgdir()とcheck_page_installed_pgdir()を通過させる。

• UPAGES領域にpages配列をマップ（読み取り専用、ユーザアクセス可）
• カーネルスタック領域（KSTACKTOP - KSTKSIZE）をbootstackにマップ（書き込み可）
• KERNBASEから物理メモリ全体（256MB）をリニアマッピング

size_t pages_size = ROUNDUP(npages * sizeof(struct PageInfo), PGSIZE);
boot_map_region(kern_pgdir, UPAGES, pages_size, PADDR(pages), PTE_U | PTE_P);

boot_map_region(kern_pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack), PTE_W | PTE_P);

uint32_t mem_size = 0xFFFFFFFF - KERNBASE + 1;
boot_map_region(kern_pgdir, KERNBASE, mem_size, 0, PTE_W | PTE_P);

質問と考察

1. ページテーブルエントリのレイアウト: 現在のページディレクトリには、UVPT（自己参照）、KERNBASEからの物理メモリマッピング、カーネルスタック、UPAGESのエントリが設定されている。
2. ユーザによるカーネルメモリの保護: PTE_Uビットが設定されていないため、ユーザモード（Ring 3）でアクセスするとページフォルトが発生する。
3. 最大物理メモリ容量: 2GB。UPAGES領域に割り当てる仮想空間は4MBで、1エントリ8バイトのPageInfoが格納できる物理ページ数は4MB/8B = 512Kページ、1ページ4KBなので最大2GB。
4. メモリ管理のオーバーヘッド: pages配列4MB + ページディレクトリ4KB + 512個のページテーブル（各4KB）= 2MB、合計約6MB。
5. EIPの切り替え: entry.Sでjmp *%eaxによりKERNBASE以上に切り替わる。その間、entry_pgdirが低アドレスと高アドレスの両方をマップしているため、低EIPのままでも実行が継続できる。この仕掛けが必要なのは、ページングを有効にした直後も低アドレスにあるコードを実行できるようにするため。

Challenge 1: PSE（4MBページ）の利用

KERNBASEのマッピングに4MBページ（PTE_PS）を使うことでページテーブルを節約する。まずCPUがPSEをサポートしているか確認し、CR4.PSEをセットした後、ページディレクトリエントリに直接4MBページの属性を設定する。

if (edx & (1 << 3)) { // PSE フラグ
    lcr4(rcr4() | CR4_PSE);
    for (i = 0; i < 64; ++i) {
        physaddr_t pa = i * PTSIZE;
        kern_pgdir[PDX(KERNBASE) + i] = pa | PTE_P | PTE_W | PTE_PS;
    }
}

テスト関数check_va2paを大ページに対応させる修正が必要。

Challenge 2: カーネルモニタの拡張

以下のコマンドを実装:

• showmappings: 仮想アドレス範囲のマッピングとパーミッションを表示
• setm: 指定した仮想アドレスのパーミッション（P/W/U）を変更
• dumpm: 仮想または物理アドレス範囲のメモリ内容をダンプ（ページ境界をまたぐ場合のエラーハンドリング付き）

実装例は省略するが、それぞれpgdir_walkやtlb_invalidateを適切に使用する。

Challenge 3: カーネルページテーブルの分離

ユーザ環境ごとに最小限のカーネルページ（IDT、GDT、TSS、カーネルスタック、割り込みエントリ）だけをマップするアプローチ。システムコールの引数受け渡しには、ユーザとカーネルの共有ページ（バッファ）を利用する。

Challenge 4: ユーザに4GB全体を提供する設計

カーネルが「跳ね回る（bouncing）」方式。割り込みエントリをユーザ空間の空きページに動的にマッピングし、システムコール時にCR3を切り替える。物理メモリへのアクセスはカーネルページテーブルを経由して行う。性能面でのオーバーヘッドと複雑さがトレードオフ。

Challenge 5: ページ割り当ての拡張（Buddy System）

連続した物理ページを効率的に割り当てるため、Buddy Systemを導入する。Order 0（4KB）からOrder 10（4MB）までの空きリストを管理し、要求サイズに応じて分割・併合を行う。

まとめ

Lab 2では物理アロケータと仮想メモリの基本を実装し、カーネルアドレス空間の設定まで行った。コードの記述・テストを通じて、ページングの動作とOSのメモリ管理の基礎を習得した。