← OSと低レイヤのしくみ コース
6. ページテーブルウォーク — 仮想アドレスが物理アドレスになるまで
RISC-V の Sv39 を例に、1つの仮想アドレスが3段のページテーブルを辿って物理アドレスに変わるまでを図で追っていきましょう。
① 仮想アドレスを4つに切り分ける
仮想アドレス (64ビットレジスタ上)有効なのは下位39ビットだけ
ビット位置で機械的に分割する
VPN[2]bits 38:30 (9ビット)
1段目の索引VPN[1]bits 29:21 (9ビット)
2段目の索引VPN[0]bits 20:12 (9ビット)
3段目の索引page offsetbits 11:0 (12ビット)
ページ内の位置- ・VPN は Virtual Page Number(仮想ページ番号)の略で、ページテーブルの何番目の要素かを表す添字です
- ・offset が12ビットなので、1ページの大きさは 2^12 = 4096 バイト(PAGESIZE)です
- ・9ビットの索引が3つあるので 9+9+9+12 = 39ビット。これが「Sv39」という名前の由来です
- ・bits 63:39 は bit 38 と同じ値でなければならず、違反するとページフォルト例外になります
仮想アドレスは意味のある塊に分かれています。上位27ビットは「表の何番目を見るか」を3回分、下位12ビットは「ページの中の何バイト目か」です。
② 出発点は satp レジスタ
satp レジスタ (64ビット)Supervisor Address Translation and Protection
フィールドに分かれている
MODEbits 63:60 (4ビット)
8 = Sv39ASIDbits 59:44 (16ビット)
アドレス空間の識別子PPNbits 43:0 (44ビット)
最上位表の物理ページ番号PPN × 4096 で物理アドレスに直す
レベル2 ページテーブルの先頭物理メモリ上の 4KiB 領域
512個のPTEが並ぶ- ・MODE が 0 のときは Bare(変換なし、仮想アドレス=物理アドレス)。8 で Sv39 変換が有効になります
- ・satp が持つのは物理ページ番号なので、実際のアドレスにするには PAGESIZE 倍します
- ・ASID があることで、プロセスを切り替えても TLB を全部捨てずに済みます
変換の出発点は satp レジスタです。ここに入っているのはアドレスそのものではなく物理ページ番号で、4096倍すると最上位ページテーブルの物理アドレスになります。
③ PTE の中身 — 次の段への矢印
PTE (8バイト)表1個あたり 512 個並ぶ
上位は行き先、下位は属性
PPN[2]bits 53:28 (26ビット)
PPN[1]bits 27:19 (9ビット)
PPN[0]bits 18:10 (9ビット)
RSW / 属性ビットbits 9:0
下位10ビットの内訳
RSWbits 9:8
OSが自由に使ってよい2ビットD A G Ubit 7 / 6 / 5 / 4
Dirty, Accessed, Global, UserX W Rbit 3 / 2 / 1
実行 / 書込 / 読出Vbit 0
Valid: 有効かどうか- ・V=0 のPTEを踏んだ時点でページフォルト例外になります
- ・R・W・X が3つとも0のPTEは「葉ではない」= 次の段のページテーブルを指す、という意味になります
- ・逆に R・W・X のどれかが1なら、そのPTEは葉(leaf)で、そこで変換が終わります
- ・PPN[2] だけ26ビット幅で、3つ合わせて 26+9+9 = 44ビットの物理ページ番号になります
- ・PTE が 8 バイト(PTESIZE)、1ページが 4096 バイトなので、1つの表に 4096/8 = 512 個 = 2^9 個。索引が9ビットなのはこのためです
PTEは「次に行くべき物理ページ番号」と「このページに何をしてよいか」を1つの64ビットに詰めたものです。R/W/X が全部0なら、まだ途中の段だという合図になります。
④ 1段目 — VPN[2] で引く
レベル2 表の先頭satp.PPN × 4096
VPN[2]9ビットの索引値
先頭 + VPN[2] × 8 バイト = PTE のアドレス
レベル2 の PTE を1個読む物理メモリへの実アクセス1回目
V=1 かつ R=W=X=0 を確認
この PTE の PPN次の表の物理ページ番号
×4096 して次の先頭へ- ・PTE1個が8バイトなので、索引には 8 を掛けてバイト単位のずれにします
- ・仕様の変換手順は a = satp.ppn × PAGESIZE から始まり、この「PTEのPPNを次のテーブルの先頭にする」操作を段ごとに繰り返します
- ・ここで読むのは物理アドレスです。変換前なので再帰的に変換がかかることはありません
最初の1回はこうです。表の先頭に索引×8を足してPTEを1個読み、そのPPNが次の表の場所になります。この動作を段ごとに繰り返すだけです。
⑤ 3段を辿りきる
レベル2 の表VPN[2] で引く
起点は satp.PPNPTE.PPN × 4096 が次の表の先頭
レベル1 の表VPN[1] で引く
メモリアクセス2回目PTE.PPN × 4096 が次の表の先頭
レベル0 の表VPN[0] で引く
メモリアクセス3回目ここの PTE は R・W・X のどれかが1 = 葉
最終 PTE目的のページの PPN を持つ
- ・LEVELS = 3 なので、レベル0まで降りる場合の3回が最大のメモリアクセス回数です
- ・葉に着いたら、アクセス種別と R/W/X/U ビットを突き合わせて権限違反がないか検査されます
- ・途中の段で葉が現れることもあり、レベル1の葉は 2MiB、レベル2の葉は 1GiB のページになります(その分アクセス回数は減ります)
- ・この読み出しを毎回やると遅いので、実機では結果を TLB に覚えておきます
同じ操作を繰り返すのがページテーブルウォークの実体です。1段進むごとに物理メモリを1回読むので、変換1件あたり最大3回のアクセスがかかります。
⑥ 最後は連結するだけ
最終 PTE の PPN44ビット
元の page offset12ビット (bits 11:0)
上下に連結する(計算ではなく単なる結合)
物理アドレス56ビット
pa = PPN×4096 + offset- ・offset は変換の間ずっと手つかずのまま最後まで運ばれます
- ・ページ内の相対位置は変換で変わらないので、足し算ではなくビットの連結で済みます
- ・Sv39 の仮想アドレスは39ビットですが、PPN が44ビットなので物理アドレスは 44+12 = 56ビットになります
最後の一手は驚くほど単純です。葉のPTEが持つPPNの下に、最初に切り出しておいたoffsetをそのまま繋げれば物理アドレスの完成です。
⑦ なぜ3段に分けるのか
もし単段だったら仮想ページ 2^27 個を全部並べる
27ビット分の索引必要なメモリを計算すると
2^27 × 8バイト = 1GiBプロセス1個につき、連続領域で
使わない領域の分も確保実際のプロセスのアドレス空間は
コード低い側に少し
広大な未使用領域ほとんどが穴
スタック高い側に少し
3段なら、穴の部分は表を作らなくてよい
必要な枝だけを作る上位段の PTE を V=0 のままにする
その先の表は存在しなくてよい- ・レベル2のPTEを1つ無効にすると、その配下 2^18 ページ分(1GiB相当)がまとめて「未マップ」になります
- ・実際に使うのは表数枚ぶんの数十KiBで済み、疎なアドレス空間との相性が良くなります
- ・代償が変換1回あたり最大3回のメモリアクセスで、これを TLB のキャッシュで埋め合わせる設計です
多段にする理由はメモリの節約です。アドレス空間はほとんどが穴なので、穴の部分の表を作らずに済ませたい。その代わり辿る回数が増える、というトレードオフになっています。