仮想メモリ 基礎

なければ各プロセスは物理 RAM を直接アドレスし、最初に壊れるのは隔離だ。下でプロセス A の 8 ページはフレームに散らばり、 B のページは A が名前を付けられないフレームにあり、A の最後の 2 ページはどこにもマップされていない。スライダーで A のページを辿り、マップの端を越えてほしい：

A に何が表現できないかに注目。B のフレームを名指しできる仮想アドレスは作れない。A のテーブルのどのエントリもそこを指さないからだ。隔離は検査ではなくマッピングの不在で、その強制はハードウェアがただでやる。

マップのない読みは大きな音で失敗する。そのアドレスを覆う領域がなく、プロセスは実行した命令で SIGSEGV を受け取る。大きな音は良いほうだ。静かなほうは実際に持つマッピングの中に落ち、ハードウェアに文句の付けようがなく、破壊は別の場所で出る。

2 つ目はアドレス空間の設計。1 つの物理空間を共有すれば、どのプログラムも他が欲しがらないアドレスを選ぶしかなく、どちらも 0x400000 を望む 2 つは同時に動けない。ここでは両方ともそこにリンクされている ——プログラム A と プログラム B。スライダーは B の置き場所を動かす：

B がコンパイルされたアドレスは仮想なので、ローダはバイナリを書き換えず、ページテーブルを埋めて飛ぶだけだ。 ASLR がほぼ無料なのも、同じバイナリの 2 つのコピーが1 組の読み取り専用フレームを共有しながらどちらも 0x400000 を自分のものと思えるのも、これが理由だ。

3 つ目はオーバーコミット。プログラムは触るより遥かに多く予約する。 64 GB のマシンに 200 GB の JVM ヒープは普通だ。予約のうち触れた部分だけが物理フレームを消費する。スライダーを上げ、予約が最初の幅のままなのを見てほしい：

72 GB —— RAM とスワップの合計 —— を超えると何が起こるか。malloc は失敗していない。約束したのはアドレス空間だけだ。失敗は後から、カーネルが満たせないフォールトとして、しかも OOM killer が選んだプロセスに落ちる。vm.overcommit_memory=0 の代価だ。

どれも無料ではない。アクセスそのものは L1 から約 1 ns。翻訳のオーバーヘッドはページテーブルを歩くアクセスの割合ぶんで、1 回あたり約 100 サイクルだ。 1000 アクセスあたりのミス数を上げてほしい：

オーバーヘッドが本来の仕事を追い越す速さに注目。 1000 回あたり 32 ミス —— 3.2%、大きなワーキングセットでは珍しくない —— で翻訳は当のアクセスと同じコストになる。この曲線が TLB の存在理由だ。ページテーブル自体はマップ量の約 0.2% を足す。請求書の小さい半分だ。

メモリはページ単位で管理される。一般的な CPU では 4 KB だ。翻訳はページ粒度なので下位 12 ビットはそのまま通り、上の4 つの 9 ビット欄がどのページかを選ぶ。 1 バイトずつ動かし、実際に動くものを見てほしい：

オフセットが動いてもフレームは変わらない。連続する 4096 個のアドレスが 1 つの翻訳を共有する。これが翻訳の割に合う理由だ —— 仕事はページごとに 1 回で、バイトごとではない。 4 KB 境界を越えれば PT インデックスが進み、フレームも変わる。

ではなぜツリーなのか。仮想ページごとにエントリを持つフラットな表は 2³⁶ エントリ × 8 バイトを要する。フラットな表と、同じ 4 MB をマップする4 段ツリーを並べて広げてほしい：

48 ビットでフラットな表はプロセスごとに 512 GiB。4 GB をマップしようが 4 KB だろうが 512 GiB だ。問われうる全アドレスに枠が要るからだ。ツリーはマップのある場所にしかノードを作らない。ここでは 4 KB ページ 5 枚 —— PML4、PDPT、PD 各 1、PT 2 —— で足りる。

x86-64 は36 のインデックスビットを 4 つの 9 ビット欄として使う。恣意的ではない。2⁹ × 8 バイトはちょうど 4096 で、どのテーブルも 1 ページになる。トラックを 1 目盛りずつ進めてほしい：

ロード数を見てほしい。4 回の依存したロード —— 次のアドレスは直前の段が返したエントリから出るので、メモリレベル並列性は効かない。Linux は Ice Lake で 57 ビット用の第 5 段を得たが、128 TB 超でのみ使い、 5 回目の依存ロードを払う。

各エントリは 8 バイト。40 ビットがフレーム番号、残りが権限と状態だ。許可するビットと拒否するビットはウォークと並行に検査される。アクセスを切り替え、このエントリをフォールトへ追い込んでほしい：

フォールトのエラーコードは「何が悪かったか」ではなく「何を試みたか」だ。ビット 0 はpresent、ビット 1 は書き込み、ビット 2 はユーザモード —— 0x7。カーネルはそこからバグかコピーオンライトかを決める。Accessed と Dirty は CPU が立て、ページ回収が読む。

ヒュージページは PS ビットが立ったエントリで、 CPU に「もう最終ページだ」と告げる。そのビットを 1 段ずつ上に設定し、ウォークが止まる段が上がるのを見てほしい：

2 つが同時に良くなる。依存ロードが 1 回減り、TLB エントリ 1 つが 4 KB でなく 2 MB を覆う。請求書は最後の読み出しだ。 100 KB を 2 MB で裏打ちすれば 1.9 MB が無駄になり、部分コピーオンライトができないので fork() 後の 1 バイトで 2 MB 全体がコピーされる。

どのツリーを歩くかを決めるレジスタは 1 つ —— x86 は CR3、ARM64 は TTBR0_EL1。最上位テーブルの物理アドレスを持つので、変えれば全翻訳が変わる。CPU を持つプロセスを動かし、同じ仮想アドレスが別の場所に落ちるのを見てほしい：

CR3 の下のツリーの差し替えが、コンテキストスイッチがメモリにすることであり、Meltdown 以後の KPTI ではカーネルに入るたびに起きることでもある。KPTI はツリーを 2 本持たせ、システムコールごとに切り替える。2018 年の性能低下の少なくない部分がここだ。

Translation Lookaside Buffer は最近のページ→フレーム対応を保持し、 L1 参照と並行に引かれる。だからヒットは実質ただで、ミスはウォークを払って結果を登録する。 8 エントリの TLB に 16 回のアクセスを流してほしい：

どのミスが避けられないかに注目。初回は必ずミスする —— 先に登録しようがない —— が、終盤のページ 17 は違う。ページ 70 に押し出されるまで常駐していた。8 スロットではこのループの 9 ページを抱えきれない。強制ミスは減るが容量ミスは減らず、スループットを決めるのは後者だ。

実際のハードウェアは階層で答える。小さな L1 dTLB、その後ろに大きな L2、それでも外れて初めてハードウェアのページウォーカが走り、ウォーカ自身もデータキャッシュ越しに読む。スライダーを下の段へ：

これは各段についての Intel Skylake〜Golden Cove の数字だ。4 KB ページで L1 dTLB 約 64、L2 約 1500 エントリ。テーブルがキャッシュにあるウォークで約 100 サイクル、なければ数百。 Apple M シリーズは L2 が約 3000 ある。

エントリ数 × ページサイズがカバー範囲 —— TLB が一度に記述できる量だ。ワーキングセットをカバー線の外へ押すと、ミス率は崖を落ちる：

ワーキングセットがカバー範囲を超えた瞬間、当たる確率はカバー÷ワーキングセットしかない。曲線は 1 − cov/ws で、2 倍のとき既に 50%。 1500 × 4 KB は 6 MB 弱。同じチップの L2 データキャッシュより小さい。キャッシュに収まっていても時間の 3 分の 1 をページテーブル歩きに使いうる。

ヒュージページはカバー範囲の項を直接攻める。エントリ数は変わらず、1 つが記述する量だけが変わる。同じ崖の下でページサイズを切り替えてほしい：

同じ 1500 エントリがカバー線をおよそ 6 MB、3 GB、 1.5 TB に置く。Redis、PostgreSQL の shared buffers、JVM ヒープ、 HPC 配列が求めるのは速いメモリではなく、崖を自分の外へ動かすことだ。perf stat -e dTLB-load-misses,dTLB-loads で測れる。キャッシュに収まるはずの負荷で約 1% を超えたら、その崖の上にいる。

TLB が持つのはある 1 本のツリーの翻訳なので、翻訳を無効にする操作は写しも無効にしなければならない —— 1 つなら INVLPG、全部なら CR3 の再ロード。 ASID タグ以前は切り替えのたびに全部捨てていた。スイッチ回数を動かし、タグなしとタグ付きを比べてほしい：

アドレス空間識別子(Intel の PCID、2010 年の Westmere)があると、生き残る各エントリはどのツリー由来かのタグを持ち、スイッチは相手のエントリを使わないだけでよい。残るのは容量圧力だ。2010 年代にスイッチが安くなった最大の要因であり、 PCID を持たない CPU で KPTI が痛かった理由でもある。

present ビットの欠落や権限違反で CPU はトラップする。カーネルは CR2 からフォールトしたアドレスを読み、仮想メモリ領域の一覧を引き、直して命令をやり直すか、あきらめる。フォールトの種類を切り替え、コストを見てほしい：

3 つの結末は 5 万倍違う。マイナーフォールトはストレージに触れず、フレームを見つけるかゼロ埋めして戻る。数千サイクルだ。メジャーフォールトは読むので、コストはデバイスのものになる。不正なものは直らない。領域がなく、プロセスは SIGSEGV で終わる。

デマンドページングはこの上に建つ。1 GB の malloc は範囲を許可済みと記して返り、触れるまで何も裏打ちされない。割り当てを歩き、いま触れているページの後ろで常駐セットが 1 フォールトずつ育つのを見てほしい：

メガバイトではなくフォールト数に注目。1 MB あたり 256 回、 4 KB ページ 1 枚に 1 回だ。1 GB を確保して即埋めるサービスは約 262,000 回カーネルに入る。アロケータがアリーナを再利用し、MAP_POPULATE があり、VSZ でなく RSS を見る理由がこれだ。

mmap は同じ仕組みをファイルに向けたもの。マッピングは空で始まり、各ページの最初の読みがストレージまでフォールトし、それ以降はふつうのメモリだ。8 ページのファイルへの 12 回の読み、最後の 4 回は既読ページの再訪を進めてほしい：

I/O をしているのが初回タッチなので、コストはコードがそう言う場所にない。read() はなく、ときどき 78 µs かかる参照があるだけだ。mmap は熱いファイルへの反復ランダムアクセスに優れ、1 回きりの走査には向かない。そこは先読み付き read() が勝つ。

fork() はページテーブルをコピーし、ページはコピーしない。全フレームが両者で読み取り専用になり、参照カウントが上がる。書き込み回数を動かし、共有フレームが 1 つずつ私有のコピーへ割れるのを見てほしい：

コストは書かれたページだけで、共有のままはただだ。数 GB の fork が一瞬で終わる理由だ。鏡像が失敗モードで、子の生存中にヒープ全体を書く親は全体を複製する。コピーは書き込みフォールトで起こるので、メモリはそのときコミットされる。fork は戻った後で OOM を起こせる。

フレームが尽きるとカーネルは回収する。最も冷たいページを選び、スワップへ書き、エントリを not-present と記し、フレームを解放する。ワーキングセットを RAM より先へ引き、平均アクセスコストの動きを見てほしい：

絵ではなく倍率を見てほしい。3 回に 1 回がスワップに落ちても 3 分の 1 ではなく 400 倍遅くなる。80 ns と 100 µs だからだ。スワップが安全弁である理由、症状が数秒の無応答である理由がこれだ。

スワップの端を越えると、カーネルはページでなくプロセスを選び始める。 OOM killer は使用量と oom_score_adj で採点し、伝えておかないかぎりログ転送ではなくデータベースを選ぶ。

• 触らない巨大な予約。RAM でなく TLB 圧力を使う。
• 小領域の mmap/munmap の繰り返し。毎回システムコールとページテーブル編集と shootdown。
• 広い範囲への mlock。秘密のためで、速度のためではない。
• 大量書き込み直後の fork()。書かれたページは次の書き込みで起こるコピーの予約分だ。
• vm.overcommit_memory の放置。割り当ての失敗を後の OOM kill に変える。