仮想メモリ 基礎

仮想メモリなしには、各プロセスが物理 RAM を直接見る。3 つが壊れる:

• 隔離。あらゆるプロセスがあらゆる他プロセス(カーネル含む)に 属するあらゆるメモリを読み書きできてしまう。信頼されないコードを安全に走らせる方法がなくなる。 マルチテナントサーバ、コンテナ、信頼されない JavaScript を走らせるブラウザ —— すべてカーネルと CPU が「1 プロセスが別プロセスのメモリを触れない」を強制することに依存している。
• アドレス空間計画。プロセスが 1 つの物理アドレス空間を共有していたら、 各プログラムは特定アドレスで走るようコンパイルされる必要があり、 両方が同じアドレスを欲しがる 2 プログラムが衝突する。リンカとローダがおかしくなる。 仮想メモリがあると、各プログラムは同じ固定仮想アドレスで走るようリンクされ —— カーネルがそれを物理 RAM 内のどこか空いている場所にマップする。
• オーバーコミット。実プログラムは実際に使うよりはるかに多い仮想メモリを割り当てる。 64 GB マシンで 200 GB Java ヒープは完全に普通 —— 仮想メモリは実際に触れられたページのみを物理 RAM で支え、 残りはスワップで支える(または単に割り当てない)ことをカーネルに許す。 これが fork() の COW が安い理由でもあり、malloc が 巨大サイズに対しても即座に返れる理由でもある。

1 段落で仕組み

ハードウェアはあらゆるメモリアクセスに追加ステップを加える。 命令は物理アドレスを直接参照するのではなく仮想アドレスを参照し、 CPU がプロセスごとのページテーブル(次節)経由でその場で 物理アドレスに翻訳する。翻訳は TLB(第 3 節)と呼ばれる 小さなハードウェアテーブルにキャッシュされるので、一般的なケースは無料。 仮想アドレスに物理裏付けがないとき、CPU はページフォールト(第 4 節)を発生させ、カーネルが何をするか決める —— ページを割り当てる、ディスクから 1 つスワップインする、 未マッピングメモリへのアクセスでプロセスを殺す。

コスト

翻訳は無料ではない。あらゆるメモリアクセスが TLB ルックアップのオーバーヘッドを負う。 TLB ミスは CPU がページテーブルをウォークする(x86-64 で 4 メモリ読み) ことを意味し、その後実際のアクセスが完了できる。カーネルがページテーブルを維持し、 それ自体がメモリを消費する(プロセスのマップサイズの ~0.2%)。 カーネルは物理メモリプールのバランスも保たなければならない —— 追い出し、スワップ、デマンドページングはすべて各ページフォールトでカーネルが行う決定。

コストにもかかわらず、仮想メモリはあらゆる汎用 OS で交渉の余地がない。 コストが受け入れられないケース —— 組み込みリアルタイムシステム、GPU シェーダ —— は仮想メモリを完全に回避する(単一の信頼されたプログラム、静的に既知のメモリ)か、 より単純なバリアント(ヒュージページ、固定翻訳)を使う。

メモリはページ単位で管理される:固定サイズの整列されたチャンク、 現代の一般的なあらゆる CPU で 4 KB(Apple Silicon は性能上の理由で 8 KB だが同じ発想)。 翻訳はページ粒度で動作する:仮想アドレスの下位 12 ビットはそのまま通る(ページ内オフセット)、 上位ビットが仮想アドレス空間のこの領域をどの物理ページが支えるかを選ぶ。

なぜツリーか

各仮想ページを物理フレームにマップする平らなテーブルは、 2³⁶ エントリが必要(4 KB ページの 48 ビット仮想アドレス用)—— プロセスごとに 64 GB のテーブル。明らかに不合理。解決はツリー: 必要な場所のみレベルが埋められる。多くのプロセスは最大数 GB を使う; そのページテーブルは数 MB を消費する。

x86-64 は 4 段ツリーを使う:PML4 → PDPT → PD → PT。 各段は 512 エントリ(9 ビットインデックス)、各エントリ 8 バイト、 各テーブルがちょうど 1 つの 4 KB ページに収まる。4 × 9 = 36 ビットのインデックス + 12 ビットオフセット = 48 ビット仮想アドレス。Linux は Ice Lake+(2019)上で5 段に拡張、57 ビット仮想アドレス(128 PB)用、 ただしカーネルがその余地を必要とするときのみ使用される。

エントリに何が入っているか

各テーブルエントリは 8 バイトで含む:次レベルテーブル(または葉での最終ページ)の物理アドレス、 およびパーミッションと状態のためのひと握りのビット。パーミッションビットは 読み、書き、実行(別個、x86-64 が NX ビットを追加した ~2003 年以来)、 ユーザ vs カーネルを強制する —— CPU はこれらを違反するあらゆるアクセスで fault する。 状態ビットには Present(このエントリが実際にどこかを指しているか)、Accessed(あらゆる読みで CPU がセット)、Dirty(あらゆる書きでセット)が含まれる。 カーネルは Accessed/Dirty を使ってどのページを追い出すか決める。

ヒュージページ —— ウォークを短絡

「ヒュージページ(huge page)」は実は PS(page-size)ビットがセットされた ページテーブルエントリで、CPU にこのレベルのエントリが既に最終ページを指していて さらなるウォークが不要であることを伝える。x86-64 上:PS セットの PDPT エントリは 1 GB ページ; PS セットの PD エントリは 2 MB ページ;それ以外は通常の 4 KB。

ヒュージページには 2 つの性能上の利点がある:TLB ミス時にウォークするレベルが少ない (2 MB で 4 ではなく 3、1 GB で 4 ではなく 2)、各 TLB エントリが 512× または 262 144× 多くのメモリをカバーする(同じ TLB 容量がはるかに大きなワーキングセットに reach できる)。 コストは内部断片化(100 KB 割り当てが 2 MB ヒュージページに丸まると 1.9 MB 無駄)と より難しいデフラグ。Linux の透過ヒュージページ(THP)は割り当てが大きく連続的なときに 透過的に 4 KB 割り当てを 2 MB にプロモートする。

アドレス空間の切り替え

x86 の CR3 レジスタ(ARM64 の TTBR0_EL1)は最上位テーブルの物理アドレスを保持する。 それを変えると CPU が見るアドレス空間全体が変わる。これがプロセスコンテキストスイッチで 起こること —— そして post-Meltdown KPTI 下のあらゆる kernel↔user 遷移で起こり、 各 syscall のコストを倍にした。

Translation Lookaside Buffer は最近使用された(仮想ページ → 物理フレーム) マッピングのコンテンツアドレスキャッシュ。ヒット時、翻訳は本質的に 追加時間ゼロで完了する(~0.5 ns、メモリアクセスと完全に重なる)。 ミス時、CPU はページテーブルをウォークする —— x86-64 で 4 読み、 最近の拡張で 5 読み。

TLB 階層

現代の Intel コアは小さな L1 dTLB(4 KB ページで ~64 エントリ) をあらゆる load/store で直接アクセスし、より大きな L2 TLB(~1500 エントリ)を L1 ミスで参照する。両方とものミスがハードウェアページウォーカを トリガし、それ自体がデータキャッシュにあるページテーブルページから恩恵を受ける —— ページテーブルがキャッシュされた TLB ミスは ~100 サイクル、 キャッシュされていなければ 500+ サイクル可能。

ARM も似た構造を持つ。Apple M シリーズは異常に大きな TLB を持つとされる (最近の世代で ~3000 L2 エントリ)、M シリーズ CPU が大型ソフトウェアの ワーキングセットをこれほどうまく扱う理由の一部。

TLB カバレッジとワーキングセットの崖

TLB エントリ数 × ページサイズで、TLB がミスする前にカバーできるメモリ量がわかる。 1500 L2 エントリ × 4 KB ページ = 6 MB のカバレッジ。 ~6 MB を超えてランダムにメモリにアクセスするワークロードは、 ほとんどのアクセスで TLB をミスしページウォークのペナルティを払う。

ヒュージページは劇的にカバレッジを拡張する。同じ 1500 L2 エントリで 2 MB ページなら 3 GB のカバレッジ;1 GB ページなら 1.5 TB。 だからデータベース(Redis、MongoDB)、JVM、HPC コードが ヒュージページをこれほど気にする —— TLB ミスの崖を 500× から 260 000× 押し出す。

TLB フラッシュ

TLB は現在プロセスのページテーブルに対する翻訳を保持する。 翻訳を無効化するあらゆる変更 —— ページが追い出される、mmap 領域がアンマップされる、 copy-on-write フォールトがページテーブルエントリを書き換える —— は、 対応する TLB エントリの無効化を要求する。アーキテクチャは 単一エントリをフラッシュする特定の命令(x86 の INVLPG)、 または完全フラッシュを提供する。

高価なフラッシュはアドレス空間スイッチ。ASID(Address Space Identifier)タグ付け以前(Intel で Westmere 2010、すべての現代 ARM)、 異なるプロセスへの切り替えは TLB 全体を吹き飛ばすことを意味した —— あらゆる翻訳が失われる。ASID があると、TLB エントリがプロセスタグを持ち、 スイッチは各プロセスのエントリを保持し競合するもののみを吹き飛ばす。 これが 2010 年代にコンテキストスイッチが安くなった最大の理由。

TLB 圧力の測定

Linux 上:perf stat -e dTLB-load-misses,iTLB-load-missesで総ミス数;dTLB-loads で割ってミス率を得る。 キャッシュにあると主張するワークロードでミス率 1% 超は、 ワーキングセットが L1/L2 に収まっているにもかかわらず TLB を超えたことを示唆する —— その時点でヒュージページまたは小さなワーキングセットが解決策。

CPU が present ビットがセットされていないページテーブルエントリ (またはパーミッション違反、まだウォーク可能でないレベル)に遭遇すると、 カーネルへトラップする。カーネルは CR2 からフォールトしたアドレスを読み、 簿記(プロセスごとの VMA —— virtual memory area —— リスト)で そこに何があるべきか調べ、状況を修正して戻るか、SIGSEGV でプロセスを殺す。

デマンドページング

malloc で 1 GB を要求しても、カーネルは実際には 1 GB の物理メモリを 割り当てない。仮想アドレスを VMA リスト内で「許可されているがまだ裏付けがない」と マークし、即座に返る。実際にページに触れたときだけページフォールトが発生し、 カーネルが物理フレームを割り当て、ゼロ化し、ページテーブルに接続し、コードを再開する。 触られない割り当てはコストゼロ。これがオーバーコミットを機能させる仕組み。

mmap

mmap はファイルまたは無名のゼロ化メモリで裏付けされた VMA を作成する。 メモリマップファイルを読むのはポインタをデリファレンスするだけ; 最初のアクセスでのページフォールトがファイルを物理フレームに読み込み、マップする。 後続のアクセスはキャッシュヒット速度。書き込み可能マッピングへの書き込みは最終的に ファイルへのライトバックをトリガする(ページキャッシュ経由、file-system primer 参照)。

mmap は共有ライブラリがロードされる方法でもあり(各プロセスが libc.so を読み取り専用共有でマップ)、 プロセス間の共有メモリが機能する方法でもある(shm_open + mmap)。

コピーオンライト(COW)

fork() はページテーブルを複製するが各ページを読み取り専用にマークし、 物理フレームの参照カウントを増やす。親と子は誰かが書くまで同じページを見る —— その時点で書き込みが fault をトリガし、カーネルが新しいフレームを割り当て、 ページをコピーし、そのプロセスのページテーブルを更新して、再開する。 書かれないページは永遠に共有のまま;書かれるページは各々 1 回のコピーコスト。

COW が複数 GB ヒープを持つプロセスでも fork() が瞬時である理由。 redis BGSAVE 子プロセスでの 1 ページへの小さな変更が、 redis データセットサイズよりずっと少ないメモリで済む理由でもある —— 変更されたページのみが複製される。

スワップ

物理メモリが不足すると、カーネルはページを追い出す:LRU ヒューリスティックで 1 つ選び、 スワップ(ディスクパーティションまたはファイル)に書き、 ページテーブルを not-present-but-in-swap にマークし、物理フレームを解放する。 プロセスが最終的にそのページに再びアクセスすると、fault がスワップから 物理フレームへの読み込みをトリガする —— 通常のメモリアクセスに見えるものが ミリ秒レイテンシになる。

スワップは安全弁であり、性能機能ではない。ワーキングセットがアクティブに スワップへ溢れると、アプリケーションが数秒のバーストで無応答になる現象として現れる。 プロダクションサーバは通常 vm.swappiness=0 または低値とタイトなメモリ予算で スワップを完全に回避する。

OOM killer

物理メモリ + スワップが枯渇しカーネルがさらに必要なとき、OOM killer で 殺すプロセスを選ぶ。スコアはメモリ使用量、nice 値、 oom_score_adj(明示的なプロセスごとのバイアス)を考慮する。 誤設定されたシステムはデータベースや SSH デーモンを OOM 殺ししうる。 ミッションクリティカルプロセスに oom_score_adj を設定する (またはメモリ予約付きの cgroup の下で走らせる)のがそれらを保護する方法。

コードレビューの赤旗

• 使わない大量メモリの事前予約。物理 RAM はコストしないがページテーブルメモリをコストし、アクセスを遅くする (全範囲の TLB 圧力)。触るものだけマップする。
• 小さな領域の mmap と munmap を繰り返す。各々が syscall であり高価なページテーブル修正。プールして割り当てるか、 より大きな固定 mmap 領域を使う。
• 巨大な範囲を mlock でピン留め。ページをスワップから締め出し、カーネルがメモリをバランスするのを阻止する。 セキュリティ(秘密がスワップに当たるのを防ぐ)に使う、性能のためには使わない。
• 最近大量に write バーストしたプロセスでの fork()。最近書かれたすべてのページがダーティで、親または子の次の書き込みで COW コピーされる。 大きな可変ワーキングセットを持つ fork ヘビーなサーバは、メモリの大半を複製する。
• プロダクションで vm.overcommit_memory を無視。カーネルのデフォルト(1 = 常に許可)は、物理メモリ + スワップが満たせない要求に対してもmalloc を成功させる;OOM killer が後で発火し、しばしば間違ったプロセスを殺す。 メモリクリティカルなホストでは 2(厳格)を設定しovercommit_ratio をチューニングする。