ページテーブル - 1000行で作るOS

プログラムがメモリにアクセスする際、CPUではある変換が行われます。仮想アドレスから物理アドレスへの変換です。仮想アドレスと物理アドレスの対応表のことを 「ページテーブル」 と呼びます。ページテーブルを切り替えることで同じ仮想アドレスでも異なる物理アドレスにアクセスさせることができます。プロセスごとのメモリ空間 (仮想アドレス空間) を隔離し、またカーネルとアプリケーションがそれぞれ利用する領域を分けることで、システムの安全性を高めることができます。

本章では、プロセスごとに独立したメモリ空間を実現するためにページテーブルの構築・切り替え処理を実装します。

仮想アドレスの構造

本書では、RISC-Vのページング機構のうちSv32というモードを利用します。2段構造のページテーブルです。32ビットの仮想アドレスを、ページテーブル (1段目) のインデックス (VPN[1])、2段目のインデックス (VPN[0])、ページ内のオフセット (offset) に分割します。

これは説明されるより、実際にどのような値になるかを見た方が分かりやすいでしょう。 RISC-V Sv-32 Virtual Address Breakdown にアクセスして、値をいじって VPN がどうなるか観察してみてください。

以下がいくつかの例です:

仮想アドレス	`VPN[1]` (10 ビット)	`VPN[0]` (10ビット)	オフセット (12ビット)
0x1000_0000	0x040	0x000	0x000
0x1000_0000	0x040	0x000	0x000
0x1000_1000	0x040	0x001	0x000
0x1000_f000	0x040	0x00f	0x000
0x2000_f0ab	0x080	0x00f	0x0ab
0x2000_f012	0x080	0x00f	0x012
0x2000_f034	0x080	0x00f	0x045

よく観察すると、次のことに気づくと思います。

真ん中あたりのビット (VPN[0]) をいじっても、1段目のインデックスは変化しない。つまり、近いアドレスのページテーブルエントリは、同じ1段目のページテーブルに集中している。

下位ビットをいじっても、VPN[1]とVPN[0]ともに変わらない。つまり、同じ4KBのページ内のアドレスは、同じページテーブルエントリを参照する。

このように、近いアドレスはページテーブル中の同じ部分を使うようになります。参照の局所性 (Wikipedia) というプログラムの特性を利用することで、ページテーブルのサイズを小さく抑えられること、またページテーブルエントリのキャッシュ (TLB: Translation Lookaside Buffer) が効果的であることが分かります。

CPUはメモリアクセスする際に、VPN[1]とVPN[0]で対応するページテーブルのエントリを特定し、そのエントリの物理アドレスとoffsetを足し合わせることで、最終的にアクセスする物理アドレスを計算します。

ページテーブルの構築

ではSv32方式のページテーブルを構築してみましょう。まずは、いくつかのマクロを定義します。SATP_SV32は「Sv32モードでページングを有効化する」ことを示すsatpレジスタのビット、PAGE_*はページテーブルエントリに設定するビットです。

kernel.h
#define SATP_SV32 (1u << 31)
#define PAGE_V    (1 << 0)   // 有効化ビット
#define PAGE_R    (1 << 1)   // 読み込み可能
#define PAGE_W    (1 << 2)   // 書き込み可能
#define PAGE_X    (1 << 3)   // 実行可能
#define PAGE_U    (1 << 4)   // ユーザーモードでアクセス可能

次のmap_page関数は、1段目のページテーブル (table1)、マップしたい仮想アドレス (vaddr)、マップ先の物理アドレス (paddr)、ページテーブルエントリに設定するフラグ (flags) を受け取り、ページテーブルを構築します。

kernel.c
void map_page(uint32_t *table1, uint32_t vaddr, paddr_t paddr, uint32_t flags) {
    if (!is_aligned(vaddr, PAGE_SIZE))
        PANIC("unaligned vaddr %x", vaddr);

    if (!is_aligned(paddr, PAGE_SIZE))
        PANIC("unaligned paddr %x", paddr);

    uint32_t vpn1 = (vaddr >> 22) & 0x3ff;
    if ((table1[vpn1] & PAGE_V) == 0) {
        // 2段目のページテーブルが存在しないので作成する
        uint32_t pt_paddr = alloc_pages(1);
        table1[vpn1] = ((pt_paddr / PAGE_SIZE) << 10) | PAGE_V;
    }

    // 2段目のページテーブルにエントリを追加する
    uint32_t vpn0 = (vaddr >> 12) & 0x3ff;
    uint32_t *table0 = (uint32_t *) ((table1[vpn1] >> 10) * PAGE_SIZE);
    table0[vpn0] = ((paddr / PAGE_SIZE) << 10) | flags | PAGE_V;
}

2段目のページテーブルを用意して、2段目の設定したいページテーブルエントリへマップ先の物理ページ番号とフラグを設定するだけです。

paddr / PAGE_SIZEとPAGE_SIZEで割っているのは、エントリに設定するのは物理アドレスではなく物理ページ番号だからです。

カーネルページのマッピング

ページテーブルにはアプリケーション (ユーザー空間) のマッピングだけでなく、カーネルのそれも設定する必要があります。

本書では、カーネルのマッピングは、カーネルの仮想アドレスと物理アドレスが一致するように設定します。こうすることで、ページングを有効化しても同じコードを引き続き実行できるようになります。

まずはカーネルのリンカスクリプトの修正です。カーネルが利用するアドレスの先頭 (__kernel_base) を定義します。

kernel.ld
ENTRY(boot)

SECTIONS {
    . = 0x80200000;
    __kernel_base = .;

. = 0x80200000の後ろに定義するよう注意してください。順番が逆だと、__kernel_baseの値がゼロになります。

次にプロセス管理構造体にページテーブルを追加します。1段目のページテーブルを指すポインタです。

kernel.h
struct process {
    int pid;
    int state;
    vaddr_t sp;
    uint32_t *page_table;
    uint8_t stack[8192];
};

最後に、create_process関数でカーネルのページをマッピングします。カーネルのページは、__kernel_baseから__free_ram_endまでの範囲です。こうすることで、静的に配置される領域 (.textなど) と、alloc_pages関数で動的に割り当てられる領域の両方を、カーネルはいつでもアクセスできるようにしておきます。

kernel.c
extern char __kernel_base[];

struct process *create_process(uint32_t pc) {
    /* 省略 */

    uint32_t *page_table = (uint32_t *) alloc_pages(1);

    // カーネルのページをマッピングする
    for (paddr_t paddr = (paddr_t) __kernel_base;
         paddr < (paddr_t) __free_ram_end; paddr += PAGE_SIZE)
        map_page(page_table, paddr, paddr, PAGE_R | PAGE_W | PAGE_X);

    proc->pid = i + 1;
    proc->state = PROC_RUNNABLE;
    proc->sp = (uint32_t) sp;
    proc->page_table = page_table;
    return proc;
}

ページテーブルの切り替え

最後に、プロセスの切り替え時にページテーブルを切り替えるようにします。

kernel.c
void yield(void) {
    /* 省略 */

    __asm__ __volatile__(
        "sfence.vma\n"
        "csrw satp, %[satp]\n"
        "sfence.vma\n"
        "csrw sscratch, %[sscratch]\n"
        :
        // 行末のカンマを忘れずに！
        : [satp] "r" (SATP_SV32 | ((uint32_t) next->page_table / PAGE_SIZE)),
          [sscratch] "r" ((uint32_t) &next->stack[sizeof(next->stack)])
    );

    switch_context(&prev->sp, &next->sp);
}

satpレジスタへの一段目のページテーブルを設定することで、ページテーブルを切り替えることができます。なお、物理ページ番号を指定するので、PAGE_SIZEで割っています。

ページテーブルの設定の前後に追加されている sfence.vma 命令は、「ページテーブルへの変更をきちんと完了させることを保証する (参考: メモリフェンス)」「ページテーブルエントリのキャッシュ (TLB) を消す」という意味合いがあります。

ブート時には、ページングが無効化されています (satpレジスタが設定されていない)。そのため、仮想アドレスと物理アドレスが一致しているかような挙動になります。

ページングのテスト

ページングを一通り実装したところで、実際に動かしてみましょう。

$ ./run.sh

starting process A
Astarting process B
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

表示内容は前章と全く同じです。ページングを有効化しても変化はありません。そこで、ページテーブルを上手く設定できているかをQEMUモニタを使って見てみましょう。

ページテーブルの内容を確認する

仮想アドレス0x80000000周辺が、どうマップされているかを見てみましょう。正しく設定されていれば、(仮想アドレス) == (物理アドレス)になるようにマップされているはずです。

QEMU 8.0.2 monitor - type 'help' for more information
(qemu) stop
(qemu) info registers
 ...
 satp     80080253
 ...

まず、satpレジスタの値を見てみると0x80080253になっています。これを仕様書の通り解釈すると 0x80080253 & 0x3fffff) * 4096 = 0x80253000 がページテーブルの一段目の先頭物理アドレスです。

では、ページテーブルの中身を見てみましょう。QEMUにはメモリの内容 (メモリダンプ) を表示するコマンドを用意しています。xpコマンドを使うと指定した物理アドレスのメモリダンプを表示できます。/xは16進数で表示することを意味します。/1024xのようにxの前に数字を書くと、その分表示してくれます。

xpではなくxコマンドを使うと、指定した仮想アドレスのメモリダンプを確認できます。後に設定するユーザー空間 (アプリケーション) では、カーネル空間とは違い仮想アドレスと物理アドレスが同一にならないため、ユーザー空間のメモリ内容を調べたいときに便利です。

ここでは仮想アドレス0x80000000に紐づく2段目のページテーブルが知りたいので、0x80000000 >> 22 = 512番目のエントリを見てみます。1エントリ4バイトなので、4をかけています。

(qemu) xp /x 0x80253000+512*4
0000000080253800: 0x20095001

1列目が物理アドレス、2列目以降がメモリの値です。ゼロではないので、なんらかの値が設定されていることがわかります。これを仕様書の通り解釈すると、(0x20095000 >> 10) * 4096 = 0x80254000 に2段目のページテーブルがあることがわかります。2段目のテーブル全体 (1024エントリ) をみてみましょう。

(qemu) xp /1024x 0x80254000
0000000080254000: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254010: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254020: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254030: 0x00000000 0x00000000 0x00000000 0x00000000
...
00000000802547f0: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254800: 0x2008004f 0x2008040f 0x2008080f 0x20080c0f
0000000080254810: 0x2008100f 0x2008140f 0x2008180f 0x20081c0f
0000000080254820: 0x2008200f 0x2008240f 0x2008280f 0x20082c0f
0000000080254830: 0x2008300f 0x2008340f 0x2008380f 0x20083c0f
0000000080254840: 0x200840cf 0x2008440f 0x2008484f 0x20084c0f
0000000080254850: 0x200850cf 0x2008540f 0x200858cf 0x20085c0f
0000000080254860: 0x2008600f 0x2008640f 0x2008680f 0x20086c0f
0000000080254870: 0x2008700f 0x2008740f 0x2008780f 0x20087c0f
0000000080254880: 0x200880cf 0x2008840f 0x2008880f 0x20088c0f
...

最初の方はゼロで埋まっていますが、(0x800バイト目) / 4 = 512エントリ目から値が埋まっています。512 << 12 = 0x200000であるため、2段目は0x200000バイト目の部分からマップされていることがわかります。一段目のベースアドレス (0x80000000) と足し合わせると、0x80200000となり、__kernel_baseの値と一致しています。

ここまでメモリダンプを自力で読んでみましたが、QEMUには使用中のページテーブルの設定情報を読みやすい形で表示するコマンドがあります。正しくマップされているかを最終確認したい場合はinfo memコマンドを使うとよいでしょう。

(qemu) info mem
vaddr    paddr            size     attr
-------- ---------------- -------- -------
80200000 0000000080200000 00001000 rwx--a-
80201000 0000000080201000 0000f000 rwx----
80210000 0000000080210000 00001000 rwx--ad
80211000 0000000080211000 00001000 rwx----
80212000 0000000080212000 00001000 rwx--a-
80213000 0000000080213000 00001000 rwx----
80214000 0000000080214000 00001000 rwx--ad
80215000 0000000080215000 00001000 rwx----
80216000 0000000080216000 00001000 rwx--ad
80217000 0000000080217000 00009000 rwx----
80220000 0000000080220000 00001000 rwx--ad
80221000 0000000080221000 0001f000 rwx----
80240000 0000000080240000 00001000 rwx--ad
80241000 0000000080241000 001bf000 rwx----
80400000 0000000080400000 00400000 rwx----
80800000 0000000080800000 00400000 rwx----
80c00000 0000000080c00000 00400000 rwx----
81000000 0000000081000000 00400000 rwx----
81400000 0000000081400000 00400000 rwx----
81800000 0000000081800000 00400000 rwx----
81c00000 0000000081c00000 00400000 rwx----
82000000 0000000082000000 00400000 rwx----
82400000 0000000082400000 00400000 rwx----
82800000 0000000082800000 00400000 rwx----
82c00000 0000000082c00000 00400000 rwx----
83000000 0000000083000000 00400000 rwx----
83400000 0000000083400000 00400000 rwx----
83800000 0000000083800000 00400000 rwx----
83c00000 0000000083c00000 00400000 rwx----
84000000 0000000084000000 00241000 rwx----

1列目から順に、仮想アドレス、物理アドレス (マップ先)、サイズ (16進バイト数)、属性を表しています。属性はrが読み込み可能、wが書き込み可能、xが実行可能を表します。また、aとdは、それぞれCPUが「ページにアクセスしたことがある」、「ページに書き込みしたことがある」ことを表しています。実際に使われているページをOSが把握するための補助的な情報です。

ページテーブルの設定ミスは、初学者にとってはデバッグがかなり難しい部分です。もし上手く動かない場合は、「付録: ページングのデバッグ」を参照してください。

ページングのデバッグ (おまけ)

ページテーブルの設定は難易度が少し高く、ミスに気づきにくいものです。そこで、本章ではよくあるページングのミスを題材に、どうデバッグできるかを見ていきます。

モードの設定し忘れ

まずはsatpレジスタにモードを設定し忘れた場合です。次のように抜いてみましょう。

kernel.c
    __asm__ __volatile__(
        "sfence.vma\n"
        "csrw satp, %[satp]\n"
        "sfence.vma\n"
        :
        : [satp] "r" (((uint32_t) next->page_table / PAGE_SIZE)) // SATP_SV32を忘れた
    );

実際に動かしてみると、きちんと動作しているように見えるはずです。これは、ページテーブルの場所が指定されてはいますがページングが無効化されているままだからです。この場合、QEMUモニタのinfo memコマンドで確認すると、次のように表示されます。

(qemu) info mem
No translation or protection

物理ページ番号ではなく物理アドレスを指定している

次に物理ページ番号ではなく物理アドレスでページテーブルを指定してしまった時です。

kernel.c
    __asm__ __volatile__(
        "sfence.vma\n"
        "csrw satp, %[satp]\n"
        "sfence.vma\n"
        :
        : [satp] "r" (SATP_SV32 | ((uint32_t) next->page_table)) // シフトし忘れ
    );

OSを起動してinfo memコマンドで確認すると、次のように空っぽになっているはずです。

$ ./run.sh

QEMU 8.0.2 monitor - type 'help' for more information
(qemu) stop
(qemu) info mem
vaddr    paddr            size     attr
-------- ---------------- -------- -------

レジスタダンプを見て、CPUが何をしているのかを確認しましょう。

(qemu) info registers

CPU#0
 V      =   0
 pc       80200188
 ...
 scause   0000000c
 ...

80200188をllvm-addr2lineで確認すると例外ハンドラの先頭アドレス、例外の発生理由 (scauseレジスタ) は仕様書によると「Instruction page fault」に該当します。

より具体的に何が起きているのかをQEMUのログから見てみましょう。

run.sh
$QEMU -machine virt -bios default -nographic -serial mon:stdio --no-reboot \
    -d unimp,guest_errors,int,cpu_reset -D qemu.log \
    -kernel kernel.elf

Invalid read at addr 0x253000800, size 4, region '(null)', reason: rejected
riscv_cpu_do_interrupt: hart:0, async:0, cause:0000000c, epc:0x80200580, tval:0x80200580, desc=exec_page_fault
Invalid read at addr 0x253000800, size 4, region '(null)', reason: rejected
riscv_cpu_do_interrupt: hart:0, async:0, cause:0000000c, epc:0x80200188, tval:0x80200188, desc=exec_page_fault
Invalid read at addr 0x253000800, size 4, region '(null)', reason: rejected
riscv_cpu_do_interrupt: hart:0, async:0, cause:0000000c, epc:0x80200188, tval:0x80200188, desc=exec_page_fault

最初のページフォルトの例外発生箇所 (epcレジスタ) の値は0x80200580で、llvm-objdumpで確認するとsatpレジスタを設定した直後の命令を指している。つまり、ページングを有効化した直後にページフォルトが発生している。
2番目以降のページフォルトはみな同じ値が続いていく。例外発生箇所は0x80200188で、llvm-objdumpで確認すると例外ハンドラの先頭アドレスを指している。このログが無限に続いていくことから、例外ハンドラを実行しようとして再度例外 (ページフォルト) が発生していることがわかる。
info registersコマンドを見ると、satpレジスタの値は0x80253000で、仕様書に従って物理アドレスを計算すると (0x80253000 & 0x3fffff) * 4096 = 0x253000000 で、これは32ビットのアドレス空間に収まらない。このことから、異常な値が入っていることがわかる。

このように、QEMUのログとレジスタダンプ、メモリダンプを確認していきながら、どこがおかしいのかを探していくことができます。ただし、デバッグで最も大事なことは「仕様書をしっかり読む」ことです。「仕様書の記述を見落としていた・勘違いしていた」ということが大変よくあります。