メモリ重複排除（KSM）と同一ページ共有

なぜ重複排除なのか：同一内容ページの山

1 台のホストに同じゲスト OS の VM を何十台も載せると、各 VM のカーネルイメージ・共有ライブラリ・ゼロ埋めページなど、内容がまったく同じ物理ページ が大量に重複します。仮想記憶は同一プロセス内なら コピーオンライト（CoW） でページを共有できますが、CoW が共有できるのは fork で 系譜（来歴）がつながったページだけ です。別々に起動した VM どうし、無関係なプロセスどうしは、たとえ中身が 1 バイトも違わなくても別々の物理ページを占有します。

KSM（Kernel Samepage Merging） は、この「来歴は無関係だが内容は同一」なページを、物理的に 1 枚へ統合 する重複排除（メモリデデュプリケーション）機構です。Linux 2.6.32 で導入され、当初の主目的は KVM のゲストメモリ密度向上 でした。CoW が「同じ出自のページを共有し続ける」のに対し、KSM は 出自を問わず内容だけを見て後付けで共有させる ところが本質的な違いです。

対象の限定：MADV_MERGEABLE で登録する

KSM はメモリ全域を勝手に走査するわけではありません。アプリ（典型的には QEMU/KVM）が madvise(addr, len, MADV_MERGEABLE) を呼び、「この匿名領域は重複排除して良い」と明示登録 した範囲だけが対象です。対象は 匿名ページ（無名メモリ）に限られ、ページキャッシュ上のファイル裏付きページは対象外です。

/* QEMU 等がゲストRAM領域をKSMの走査対象に登録する */
madvise(guest_ram, ram_size, MADV_MERGEABLE);

登録された領域は ksmd というカーネルスレッドが定期的に走査します。挙動は sysfs のチューノブで制御します。

/sys/kernel/mm/ksm/
  run               : 1=走査開始, 0=停止, 2=停止して既存マージを解除
  pages_to_scan     : 1回の起床で走査するページ数（多いほど速いがCPU増）
  sleep_millisecs   : 走査と走査の間のスリープ
  pages_shared      : 安定木に存在する共有ページ（代表ページ）の枚数
  pages_sharing     : それらを参照している「重複していたぶん」の枚数＝節約量の目安

おおまかに言えば、pages_sharing の値がそのまま節約できた物理ページ数 に相当します（重複していた各参照は本来なら自前のページを 1 枚占有するはずだったため）。pages_shared は代表ページの枚数なので、メモリ上に残るのは pages_shared 枚、消えたのが pages_sharing 枚、というイメージです。走査速度（pages_to_scan と sleep_millisecs）は 重複排除の追従速度と CPU コストのトレードオフ を決める主ダイヤルです。

同一性の判定：安定木と不安定木

KSM の中核は 2 本の赤黒木（red-black tree）です。木のキーは ページの内容そのもの（ページ全体のバイト列を比較順序に使う）で、アドレスではありません。

• 安定木（stable tree）：すでにマージ済みで 書き込み不可（write-protected）に固定 されたページを格納する木。ここに載るページはもう内容が変わらないので、安定したキーとして木の比較に使えます。
• 不安定木（unstable tree）：まだマージされていない 候補ページ を暫定的に並べる木。これらは書き込み可能なままなので内容が変わりうり、木のキーとして不安定です。

ksmd は登録領域のページを 1 枚ずつ取り、次の順で照合します。

ksmd が1ページ candidate を処理する流れ:
  1. まず安定木を内容で検索する
       一致あり → candidate をそのマージ済みページへ統合（CoWで共有）
  2. 安定木に無ければ、ページのチェックサムを計算し
     前回スキャン時の値と比較する
       値が変化 → 最近書き換わった＝不安定。今回はマージ候補にしない
       値が不変 → 内容が落ち着いている可能性が高い
  3. 不変なら不安定木を内容で検索する
       一致あり → 2枚を新たにマージし、その結果を安定木へ昇格
                   （統合先を write-protect して安定化）
       一致なし → candidate を不安定木に挿入して次回に備える

ポイントは チェックサムによる安定性チェック です。直前のスキャンから内容が変わったページは、マージしてもすぐ書き込みで分裂する公算が高いので、無駄を避けて候補から外します。不安定木は 毎スキャンごとに作り直される（前回の木は破棄される）ため、変動するページがキーを腐らせる問題を構造的に回避しています。

マージの実体：CoW への引き渡し

2 枚のページが同一と確定すると、KSM は 片方を代表ページとして残し、もう片方の物理ページを解放 します。そして元のページを参照していた仮想アドレスのページテーブルエントリ（PTE）を、代表ページを指すよう 張り替え、同時に書き込み不可 に設定します。これで複数の仮想ページが 1 枚の物理ページを共有し、メモリが浮きます。アドレス変換と PTE の基礎は 仮想記憶（ページング） を参照してください。

共有後にどちらかが 書き込もうとすると、write-protect によりページフォルトが発生 し、カーネルがその場で専用コピーを作って書き込み側に渡します。これはまさに コピーオンライト（CoW） の機構そのものです。つまり KSM は 「内容で同一ページを見つける検索エンジン」 であり、見つけた後の共有・分裂の保護は既存の CoW に委ねています。

マージ前:
  VM-A の仮想ページ ──▶ [物理ページ P]（内容X, 書込可）
  VM-B の仮想ページ ──▶ [物理ページ Q]（内容X, 書込可）

マージ後（KSMページとして共有）:
  VM-A の仮想ページ ─┐
                     ├─▶ [物理ページ P]（内容X, read-only / 安定木に登録）
  VM-B の仮想ページ ─┘   ※ Q は解放されメモリが浮く

VM-B が書き込んだ瞬間（CoW）:
  VM-A の仮想ページ ───▶ [物理ページ P]（内容X, read-only のまま）
  VM-B の仮想ページ ───▶ [物理ページ Q' のコピー]（書込可）

なお KSM ページは複数プロセスから参照される特殊な共有ページなので、内部的には rmap（逆引きマッピング） で「この物理ページを指す全 PTE」を辿れるようにしておき、書き込みフォルト時や解除時に一括で張り替えられるようにしています。

トレードオフ：CPU コストとサイドチャネル

KSM の利得（メモリ節約・VM 密度向上）には、はっきりした代償が伴います。

最大の論点は サイドチャネル（情報漏洩） です。あるページが KSM で共有されているとき、それへ 初回書き込みすると CoW フォルトと複製が走るため、書き込み時間が有意に長く なります。攻撃者は推測したい内容のページを自分のメモリに用意し、その書き込みレイテンシを測ることで、同一内容のページがホスト上の他テナントに存在するか を判定できます。これが成立すると、被害者プロセスが特定のライブラリ・ファイル・秘密値を持つかを外から推定でき、極端な例では総当たりで秘密の中身を 1 ページ単位で当てにいけます。これは投機実行系の漏洩とは独立した、メモリ共有そのものに起因する タイミング攻撃です。マイクロアーキテクチャ起因の漏洩との対比は 投機的実行の脆弱性とOSの緩和策 も参照すると、漏洩経路の違いが整理できます。

CoW と KSM は どちらも write-protect と書き込み時複製という同じ保護機構を共有 しますが、共有のきっかけが「来歴」か「内容の発見」か で根本的に異なります。KSM は CoW の保護機構を再利用しつつ、その適用範囲を「内容が一致する任意のページ」へ拡張した仕組みだと捉えると見通しが良くなります。

まとめ

• KSM は内容が同一の匿名ページを物理 1 枚に統合する重複排除機構。来歴を問わず内容だけで 別プロセス・別 VM 間のページも共有でき、KVM のゲスト密度向上が主用途。
• 走査対象は madvise(MADV_MERGEABLE) 登録領域に限定。ksmd が 安定木（マージ済み・write-protect 済み） と 不安定木（候補・毎回再構築） の 2 本の木で内容比較し、チェックサム で落ち着いたページだけをマージする。
• マージ後の共有・分裂の保護は コピーオンライト（CoW） に委譲する。見つける役が KSM、守る役が CoW という分業。
• 代償は 走査 CPU と、書き込みレイテンシ差から他テナントのページ内容を推測できる サイドチャネル。マルチテナントでは信頼境界をまたぐマージを避けるのが定石。

前提は 仮想記憶（ページング） と コピーオンライト（CoW）、漏洩経路の対比は 投機的実行の脆弱性とOSの緩和策 を併せて読むと、メモリ共有の利得とリスクが一体で理解できます。