この記事は自作OS Advent Calendar 2016の24日目の記事として書かれました.

先日、再帰ページマッピングという面白い手法をRustでOSを書き直しているときに知りました.
自分の理解のためも兼ねて解説しようと思います.

OSのリポジトリはこちら.
Axel

ちなみに、Writing an OS in Rustを参考にしているのですが、Rustもうまいこと使いこなしているし、OSへの解説も丁寧で英語も読みやすい、素晴らしいサイトです.
(正直そっちを読んだほうが早いかもしれない)

謝辞

わざわざリプライを飛ばして誘ってくれた、@uchan_nosさんに感謝を.
自作OS Advent Calendar 2014を2年前にやった身としては大変うれしいです.
そして、しばらく自作OS熱が冷めている間に新しいコミュニティ(osdev-jp)が出来ていたようです.
全く気が付きませんでした.
もくもく会など参加していきたいです :)

用語

用語の差がいくつかあるので、この文章で使用する言葉をここに整理しておきます.
特にページングの用語はややこしい...

物理アドレス
- コンピュータ上に搭載されている物理的な主記憶装置の番地こと
仮想アドレス
- ページング機構によって物理アドレスに変換されるアドレスのこと
- 余談だが以下の記事が面白い
- 「Virtualを仮想と誤訳した責任は我々にあります」
ページ
- (ここでは)4KBの仮想メモリ領域
フレーム
- (ここでは)4KBの物理メモリ領域
ページテーブル
- ページエントリがいっぱい並んでいるテーブルのこと
- 構造によって、ページディレクトリポインタテーブルだの、ページディレクトリだの、ページテーブルだのと呼ばれる
- はっきり言ってよくわからないし、しばらく見てないと思い出せなくなるのでやめてほしい(2年前くらいににCで書いたコードが既によくわからない)
- なので、Writing an OS in Rustを真似してページングの段によってLevelというプレフィックスをつけて呼ぶことにした
- x86_64は4段ページングなので
  - Level4PageTable Level3PageTable Level2PageTable Level1PageTable
- となる、幾分かはましになったかなと思う
ページエントリ/エントリ
- ページングの情報を持っている構造体のこと
- x86_64では8バイトである
- こちらにもページテーブルと同様の命名にする
  - Level4PageEntry Level3PageEntry Level2PageEntry Level1PageEntry
ページング構造体
- ページングに関する情報を持つ構造体
- 上記のページテーブルとページエントリを特に区別なく呼ぶために導入

再帰ページマッピング

ページングそのものの詳しい解説に関してはインターネット上にたくさん良い記事があるので、そちらにおまかせしようと思います.

旧Axelはx86_32なので、2段ページングです.
うまいことページング構造体へアクセスする方法を知らなかったので、愚かにもOS起動時に全ページング構造体をメモリ上に確保していました.
そして、既にカーネルがマップされているエリアに含めてやることで、ページング構造体を操作するという手法を取っていました.
32ビット環境での最大メモリは4GBで、ページング構造体は4バイトなので大した量にはならないですが、64ビット環境で同じことはちょっと出来ません.

そこで、再帰ページマッピングです.
再帰ページマッピングの目的は仮想メモリ空間から物理メモリ空間にあるページング構造体をうまいこと操作することです.
これを使うことによってページング構造体にアクセスするためのページというものを減らすことが出来ます.
ただし、デメリットとして、仮想メモリ空間の末尾が専有されてしまいます.
しかし、現代のコンピュータで64ビット空間末尾までメモリが必要(16エクサバイト)ということは無いと思いますので当面は問題ないでしょう.
また、ハードウェア的にも使わないものを実装するのはコストが大きいという理由から48ビットから51ビットのCPUしかないそうです.

ページングの仮想アドレス変換処理

おさらいの意味も込めて、普通のページマッピングの仮想アドレス変換処理を見てみましょう.
自分はいつも忘れてしまいます.
例として入れておいた、仮想アドレスやページテーブルのアドレスは適当なものです.
図を見ると左から順に仮想アドレス解決が行われているのがわかると思います.

実装

さて、再帰ページマッピングするために必要なことは簡単です.
それは、あるLevel4PageEntryの指す先を、そのエントリが属するページテーブルの物理アドレスにすることです.
エントリの参照先が自分のテーブルなので再帰というわけですね.

さて、これだけ言われてもよくわからないので、以降は具体例と共に使用方法を説明します.
まずは、再帰ページマッピングの設定です.

nasmアセンブラで見てみましょう.
Level4PageTableのアドレスを0x1000とします.
これらのメモリ領域は歴史的な理由から使用可能な空きメモリ領域です.
詳細はOSDev.org -Memory_Map_(x86)を参照ください.

; CR3にLevel4PageTableの物理アドレスを設定.
; このときメモリの初期化忘れに注意.
mov eax, 0x1000
mov cr3, eax

; Level4PageTableの最後のエントリを再帰するように設定.
; (0x3はPresent/Writableフラグ)
mov dword [0x1000 + 8 * 511], 0x00001003

実装はこれだけです.
簡単ですね！

どのように動くのか

私は実装だけ見ても全くわかりませんでした.
なので、順を追って考えてみました.
図に表すとこんな感じです.

これについて以降で説明していきます.
まず、上記実装でページマッピングがどうなっているか考えてみましょう.
初めは4段目です.
ページテーブルには、511番目のLevel4PageEntryだけが存在しています.
なので、仮想アドレス0b 111111111 XXXXXXXXX XXXXXXXXX XXXXXXXXX XXXXXXXXXXXX = 0xFF8XXXXXXXXXが有効になるはず、といきたいですがここで注意です.
なお、Xはdon't careとして、気にしないことにします.

正規形

上の方で、現在のCPUが持つ、物理アドレス幅は48ビットといいました.
しかし、仮想アドレス自体は64ビットなのです.
これはいずれ物理アドレス幅が64ビットになることを考えてのことです.
そして、将来の拡張のための措置として、正規形アドレス(Canonical form addresses)というものが存在します.
これは最下位ビットを0番としたとき、47番目のビットを48番目から63番目のビットにコピーしなければならないという決まりごとです.
符号拡張みたいなものですね.
この規則を守っているアドレスのことを正規形といいます.
また、これを守らないアドレスはCPUが例外を投げます.
こうすることによって、いま作成しているソフトが将来、メモリが拡張されたときに、拡張領域には手出し出来ないことが保証されますね.

ちなみに、この正規形アドレスの存在によって、64ビット空間は2つに分断されます(higher halfとlower half).
英語版Wikipediaにとてもわかり易い図があります.
カーネル領域を上位に、ユーザ領域を下位に配置するとなんかいい感じですね.

詳細は以下のリンクを参照です.
Wikipedia - X64 - メモリ管理
 Wikipedia - X86-64 - Canonical form addresses

どのように動くのか (続き)

0xFF8XXXXXXXXXのままでは、48番目以上が0扱いになってしまいます.
なので、これを正規形にしましょう.
0xFFFF FF8X XXXX XXXXとなりますね.

そして、511番目のLevel4PageEntryはLevel3PageTableを指します.
ここで再帰しているので、Level4PageTableがLevel3PageTableとして扱われます.
これで、4段目の解決は完了です.
次に3段目です.
ここでも結局同じテーブルを使用しているのでさっきと同様になります.
一気にやってしまいましょう.

上から順番に今有効な仮想アドレスを解決していくと、こんな感じですね.
4段 - 0b 111111111 XXXXXXXXX XXXXXXXXX XXXXXXXXX XXXXXXXXXXXX = 0xFFFF FF8X XXXX XXXX
3段 - 0b 111111111 111111111 XXXXXXXXX XXXXXXXXX XXXXXXXXXXXX = 0xFFFF FFFF CXXX XXXX
2段 - 0b 111111111 111111111 111111111 XXXXXXXXX XXXXXXXXXXXX = 0xFFFF FFFF FFEX XXXX
1段 - 0b 111111111 111111111 111111111 111111111 XXXXXXXXXXXX = 0xFFFF FFFF FFFF FXXX

ここでちょっと紛らわしいですが、実際に有効な仮想アドレスは1段目のみです.
4から2段は解決手順の途中を書き出したものということに注意してください.

最後に物理アドレスオフセットが残ってしまいました.
ここが、この手法のすごいところです.
Level1PageEntryは物理アドレス(フレーム)の先頭を指します.
再帰しているので今まで使ってきたページテーブルアドレスを再び使用します(ここでは0x1000).
なので、0xFFFF FFFF FFFF FXXXは0x1000 + 0xXXXにマップされることになります.
これでLevel4PageEntryの値を変更出来ますね.
ページとフレームの大きさは4KBなので、Level4PageTableのサイズ(8 * 512 = 4096)とぴったり同じです.
ページングはよく考えられているなあと感心させられます.

普通のページを設定してみる

ここまででLevel4PageEntryを操作出来るようになりました.
では、他の段のエントリはどうやるのでしょうか.
現時点では再帰マッピング用以外のエントリは存在しません.
(実際はOSのメモリ領域をページング有効化前に設定しないといけません.)
なので、仮想アドレス空間から何かしら設定してみましょう.
その中で他のエントリの設定について見ていきます.
ここではそれぞれのページテーブルとして、0x4000以降のアドレスを適当に選んで設定しています.

とりあえずnasmアセンブラです.

%define TO_LEVEL3_OFFSET(index) (index << 30)
%define TO_LEVEL2_OFFSET(index) (index << 21)
%define TO_LEVEL1_OFFSET(index) (index << 12)

LEVEL4_INDEX equ 8
LEVEL3_INDEX equ 16
LEVEL2_INDEX equ 32
LEVEL1_INDEX equ 64

; Set Level4PageEntry.
mov rax, 0xFFFFFFFFFFFFF000
mov dword [rax + 8 * LEVEL4_INDEX], 0x00004003

; Set Level3PageEntry.
mov rax, 0xFFFFFFFFFFE00000 + TO_LEVEL1_OFFSET(LEVEL4_INDEX)
mov dword [rax + 8 * LEVEL3_INDEX], 0x00005003

; Set Level2PageEntry.
mov rax, 0xFFFFFFFFC0000000 + TO_LEVEL1_OFFSET(LEVEL3_INDEX) + TO_LEVEL2_OFFSET(LEVEL4_INDEX)
mov dword [rax + 8 * LEVEL2_INDEX], 0x00006003

; Set Level1PageEntry.
mov rax, 0xFFFFFF8000000000 + TO_LEVEL1_OFFSET(LEVEL2_INDEX) + TO_LEVEL2_OFFSET(LEVEL3_INDEX) + TO_LEVEL3_OFFSET(LEVEL4_INDEX)
mov dword [rax + 8 * LEVEL1_INDEX], 0x00007003

; Test for writing the mapped memory.
mov rdi, 0x0000040404040000
xor rax, rax
mov rcx, 4096 / 8
rep stosq

そして、実行するとマッピングが以下のようになります.

	仮想アドレス	物理アドレス
Level4PageTable	0xFFFF FFFF FFFF F000	0x0000 0000 0000 1000
Level3PageTable	0xFFFF FFFF FFE0 8000	0x0000 0000 0000 4000
Level2PageTable	0xFFFF FFFF C101 0000	0x0000 0000 0000 5000
Level1PageTable	0xFFFF FF82 0202 0000	0x0000 0000 0000 6000
物理アドレス	0x0000 0404 0404 0000	0x0000 0000 0000 7000

これだけ見てもいきなり過ぎますね.
上から順に考えてみましょう.

一番上にあるのはマクロです.

%define TO_LEVEL3_OFFSET(index) (index << 30)
%define TO_LEVEL2_OFFSET(index) (index << 21)
%define TO_LEVEL1_OFFSET(index) (index << 12)

これらは引数に添え字を取って、各段のアドレスオフセットに変換します.
といっても、添字をそれぞれの位置にシフトしているだけです.
なので、これをページエントリの0番目のアドレスに足すと、その添字のページエントリのアドレスになるわけですね.

その次にあるのでは、それぞれの段の添字です.
特に意味もなく切りのいい値を選びました.

; Set Level4PageEntry.
mov rax, 0xFFFFFFFFFFFFF000
mov dword [rax + 8 * LEVEL4_INDEX], 0x00004003

これについては、ここまで説明したとおり、LEVEL4_INDEX番目のLevel4PageEntryに値を設定しています.
ここでは物理アドレス0x4000をLevel3PageTableのアドレスとしました.

4段目を設定したので次はもちろん3段目です.
3段目のページテーブルは物理アドレス0x4000に設定したのでした.
ここにどうやってアクセスしましょうか？
もちろん再帰ページマッピングでいけます.

; Set Level3PageEntry.
mov rax, 0xFFFFFFFFFFE00000 + TO_LEVEL1_OFFSET(LEVEL4_INDEX)
mov dword [rax + 8 * LEVEL3_INDEX], 0x00005003

ここで考えるのはLevel1PageEntryの指す先が0x4000になればよいということです.
これは、Level1PageEntryの指す先が実際にアクセスする物理アドレスだからです.
1つ目の図を見るとわかりやすいはずです.
なので、それらを満たす仮想アドレスを探すことになります.

まず、4, 3, 2段は関係ないので再帰させます.
0b 111111111 111111111 111111111 XXXXXXXXX XXXXXXXXXXXX = 0xFFFF FFFF FFEX XXXX
これで、2段目までです.
ここに、1段目のオフセットを足さなければいけません.
そのために、TO_LEVEL1_OFFSETを使用しています.
そして、今1段目に設定したいのは先程0x4000を設定したLEVEL4_INDEX番目のエントリです.
実際の計算は0xFFFFFFFFFFE00000 + (8 << 12)となりますので、0xFFF FFFF FFFE0 8000を使ってLevel3PageEntryを設定することになります.
あとは、ここにエントリのオフセットを足すだけですね.
ここでは物理アドレス0x5000をLevel2PageTableのアドレスとしました.

同様の考えでLevel2PageEntryを操作していきます.

; Set Level2PageEntry.
mov rax, 0xFFFFFFFFC0000000 + TO_LEVEL1_OFFSET(LEVEL3_INDEX) + TO_LEVEL2_OFFSET(LEVEL4_INDEX)
mov dword [rax + 8 * LEVEL2_INDEX], 0x00006003

; Set Level1PageEntry.
mov rax, 0xFFFFFF8000000000 + TO_LEVEL1_OFFSET(LEVEL2_INDEX) + TO_LEVEL2_OFFSET(LEVEL3_INDEX) + TO_LEVEL3_OFFSET(LEVEL4_INDEX)
mov dword [rax + 8 * LEVEL1_INDEX], 0x00007003

Level2PageTableは物理アドレス0x5000に存在します.
つまり、Level1PageEntryの指す先が0x5000になればよいということです.
と、ここでよく考えてみると、このことが書かれているのは物理アドレス0x4000にあるLevel3PageTableの中のエントリです.
なので、2段目にここを見てあげなければなりません.

4, 3段は再帰で飛ばします.
0b 111111111 111111111 XXXXXXXX XXXXXXXXX XXXXXXXXXXXX = 0xFFFF FFFF CXXX XXXX
ここに、2段目のオフセットとして、TO_LEVEL2_OFFSET(LEVEL4_INDEX)、1段目のオフセットとして、TO_LEVEL1_OFFSET(LEVEL3_INDEX)を足してやれば、
0xFFFFFFFFC1010000となり、設定したいLevel2PageTableに対応する仮想アドレスの完成です.
あとはオフセットを足すだけです.

最後のLevel1PageEntryの操作も同様の流れです.

もっとうまいこと設定してみる

仮想アドレス越しにページング構造体の設定を見てきました.
それぞれの段のアクセスの仕方をここで整理してみましょう.

Level4PageEntry - 0xFFFFFFFFFFFFF000 + 8 * LEVEL4_INDEX
Level3PageEntry - 0xFFFFFFFFFFE00000 + 8 * LEVEL3_INDEX + TO_LEVEL1_OFFSET(LEVEL4_INDEX)
Level2PageEntry - 0xFFFFFFFFC0000000 + 8 * LEVEL2_INDEX + TO_LEVEL1_OFFSET(LEVEL3_INDEX) + TO_LEVEL2_OFFSET(LEVEL4_INDEX)
Level1PageEntry - 0xFFFFFF8000000000 + 8 * LEVEL1_INDEX + TO_LEVEL1_OFFSET(LEVEL2_INDEX) + TO_LEVEL2_OFFSET(LEVEL3_INDEX) + TO_LEVEL3_OFFSET(LEVEL4_INDEX)

なにやら規則的な感じがしますね？
LEVEL4_INDEXがLevel3PageEntryのところで1段目になり、Level2PageEntryのところで2段目になり、Level1PageEntryのところで3段目になっています.
他の添字も、上の方に移動しています.
添字は9ビットなので、9ビットずつ左シフトしているということですね.
そして、ベースとなるアドレスも合わせて左シフトしています.
これを利用すると、いちいち段のオフセットを計算する手間が省けます！

なので、先程のコードは以下のように修正します.

mov rax, 0xFFFFFFFFFFFFF000

add rax, 8 * LEVEL4_INDEX
mov dword [rax], 0x00004003

shl rax, 9
add rax, 8 * LEVEL3_INDEX
mov dword [rax], 0x00005003

shl rax, 9
add rax, 8 * LEVEL2_INDEX
mov dword [rax], 0x00006003

shl rax, 9
add rax, 8 * LEVEL1_INDEX
mov dword [rax], 0x00007003

mov rdi, 0x0000040404040000
xor rax, rax
mov rcx, 4096 / 8
rep stosq

オフセットの計算処理すら不要になり大変さっぱりしました.
さらに、値がことなるだけで処理は同じですから、関数を作ってループ処理で一気にページエントリの設定なんてものできそうです.
このことから、0xFFFFFFFFFFFFF000を元に、シフト演算と加算を繰り返して全てのページング構造体にアクセス可能ということがわかりました.
めっちゃ便利ですね.

終わりに

ごちゃごちゃとした記事ですがここまで読んで頂けたら幸いです.
もし間違いやおかしいところがあれば是非コメントをください.

References

Writing an OS in Rust - Page Tables
OSDev.org - Page Tables - Recursive mapping
OSDev.org forum - Recursive mapping questions
OSDev.org forum - Self-referencing pm4l and -2GB kernel
OSDev.org forum - Page table addressing in 64-bit mode
OSDev.org - Memory Management Unit

x86_64での再帰ページマッピング

謝辞

用語