Rust自作x86エミュレータ、Linuxフルブート10秒への道 — デコードキャッシュとブロック連結で36→66 MIPS

Rust

Rustで依存ゼロのx86エミュレータを書いている。32bit Linux (Alpine 6.18) がブラウザ (WASM) でもネイティブでも起動するところまで来たが、問題は速度だった。シンプルなカーネルの起動に、ブラウザで2分半かかる。「動く」と「使える」の間には深い谷がある。

本稿はその谷を渡った記録である。最終的にネイティブ8.8秒・ブラウザ21秒まで縮んだ。数字の変遷だけでなく、「最適化でCPUの意味を壊していない」ことをどう機械的に証明したかが本稿の読みどころだと思う。

なぜ30 MIPSで頭打ちになるのか

最適化前のエミュレータは約30 MIPS (1秒に3000万命令) で頭打ちだった。1命令あたり34ns、M1のクロックでいうと約110サイクルである。ゲストの1命令にホストの110命令を払っている。

内訳はプロファイルではっきりしていた。

33%  cpu::step     — フェッチ + プレフィクス処理 + 巨大matchのディスパッチ
13%  modrm         — オペランドの毎回再デコード
12%  memmove       — 毎命令のCPU状態控え (352バイト) + REP転送
 8%  translate_for — ページング変換 (TLBヒット経路)

毎命令、こういうことをしている。

フェッチ → プレフィクス剥がし → 巨大match (間接分岐) → ModRM再デコード → 実行 → 帳簿

同じアドレスの同じ命令を、ループのたびに何百万回もデコードし直している。巨大matchの間接分岐はホストCPUの分岐予測を外し続ける。これは古典的なswitch型インタプリタの構造上限であり、コードを磨いても超えられない。構造を変えるしかない。

方針: 全量カタログと、意味不変の機械的証明

最適化に入る前に2つのルールを決めた。

1. 思いつく最適化を全部台帳に載せ、上から順に潰す。 案を小出しにすると「捨てた案」が発生する。効かなかった案も削除せず「寝かせ」として台帳に残す — 前提が変われば再訪するためだ。

2. 決定的命令数を意味不変の証明に使う。 このエミュレータは完全に決定的で、同じイメージを起動するとシェル到達までの命令数が毎回ビット単位で同じになる。Linuxなら580,999,942命令、ELKSなら28M命令。最適化した後にこの数字が1でもずれたら、速くなったのではなく意味が変わったことを意味する。逆に完全一致すれば、実行された命令列が同一であることの強い証拠になる。

最適化前:  シェル到達 = 580,999,942 命令
最適化後:  シェル到達 = 580,999,942 命令   ← 完全一致 = 意味不変の証明

この検証はCIにも入れてあり、3つのOS (ELKS / FreeDOS / Linux) をプロンプトまで実際に起動して命令数を毎回見張る。この網があるから、CPUの内側を大胆に触れる。

もう1つ、測定の規律として交互A/Bを徹底した。M1は熱ダレで数分のうちに5%以上ずれる。新旧のバイナリを続けて測ると熱の差を測ってしまうので、交互に走らせた差だけを信じる。

第1幕: 実行する量そのものを減らす (vmlinux直接ロード)

プロファイルより先に、起動の中身を見た。ブート全体の命令数を区間ごとに数えると、驚くことに55% (540M命令) が無言の区間で消えていた。カーネル本体ではない。bzImageの自己解凍ステブである。

bzImageは圧縮されたカーネルで、先頭の展開コードが自分自身を解凍してから本体に飛ぶ。エミュレータはこの解凍ループを律儀に1命令ずつ実行していた。

答えはFirecrackerと同じ判断にした。解凍はホスト側でやる。ELFの vmlinux を直接ロードして32bitエントリへ飛べば、ゲストは解凍を1命令も実行しない。

bzImage:  971M命令 (55%が解凍)
vmlinux:  580M命令               ← 起動の4割を「実行しない」ことで消した

第2幕: デコード済み命令キャッシュ (本丸)

構造の上限を破る本命。物理アドレスをキーに、デコード結果 (uop) を控える直接マップのキャッシュを足した。2回目からはデコードを飛ばして実行だけを行う。実CPUのuopキャッシュ、QEMU TCGのTBと同じ系譜である。

設計で一番こだわったのは意味論を二重実装しないことだ。

onebyte.rs (巨大match)   = 意味の原本
cpu/dcache/              = 速い写し — 実行は原本と同じ共通部品を呼ぶ

キャッシュの実行器は、従来経路と同じALU・シフト・ストリングのヘルパ関数を呼ぶ。「movの意味」を2箇所に書いたら、いつか片方だけ直して静かに壊れる。写しが持つのはデコード結果だけで、意味は常に1箇所にある。

対象命令は推測ではなく実測で選んだ。ブート624M命令のオペコード頻度を数えると、mov系24%、ALUグリッド16%、条件分岐10%…と上位が明確に出る。上位から順にuop化し、それ以外は従来のmatchへ落とす。フォールバックがあるから安全に刻める。カバレッジは最終的に99.0%になった。

自己書き換えコード (Linuxもブート時にalternativesで自分を書き換える) は、コードを控えたページへの書き込みがページ世代を進めることで検出する。古い控えは世代照合で自然に外れる。

効果: ネイティブ 21.7s → 16.3s (-25%)
      ブラウザはさらに効いて約2倍 — wasmは間接分岐の予測ペナルティが重く、
      分岐を消す最適化ほどネイティブより効く

第3幕: 控えは「メモリに触る命令」だけ (C4)

プロファイルの12%を占めていたmemmoveの正体は、フォールト巻き戻し用のCPU状態控え (352バイト/命令) だった。

x86の約束として、ページフォールトした命令は「何も起きなかったこと」になる必要がある。書き換え途中のレジスタを残すと、ハンドラ復帰後の再実行が汚れの上に積む。だから毎命令、実行前にCPU全体を控えていた。

だが考えてみれば、レジスタ間演算・条件分岐・leaはページフォールトを起こしようがない。メモリに触らないからだ。デコードキャッシュのuopは自分がメモリに触るかを静的に知っているので、触るものだけ控えるように変えた。

// 控えは「メモリに触るuop」だけ。キャッシュ済み命令のフェッチは
// ページ内で完結する (跨ぎはデコード時に拒否) ので、フォールトの
// 出どころはデータアクセスだけ — 触らないなら巻き戻しは起きない
if exec::may_touch_memory(&uop) {
    m.guard_save();
}

効果: 交互A/B 22.0s → 20.8s (-5%)

第4幕: ブロック連結 — 期待10〜20%が43%になった

最後がQEMUのblock chaining相当。従来は1命令実行するたびに外側のループへ戻り、「デバッガ判定・HLT判定・BIOS入口判定・アドレス変換」のはしごを払い直していた。

これを、次の命令が同じ物理ページに居るかぎり走り続けるループに変えた。面白いのは、ブロック表のような新しいデータ構造を一切作らなかったことだ。

従来:   [外側のはしご] → 照合 → 実行 → [外側のはしご] → 照合 → 実行 → …
連結後: [外側のはしご] → 照合 → 実行 → 照合 → 実行 → 照合 → 実行 → …
                          └── 同一ページ内なら pa+len でスロット照合に直行 ──┘

分岐で途切れないのが効いた。ジャンプ先が同じページ内なら物理アドレスを差し替えて続行するので、ホットループがまるごと連結される。カーネルのmemcpyもハッシュ計算も、ほぼ外側に戻らずに回る。

ただし、意味を守るための約束を4つ置いた。

  1. 時計は1命令粒度のまま。 連結中も毎命令TSCを進め、装置tickを外側と同じ順序で刻む。だから決定的命令数は崩れない
  2. 割り込みの受付点も1命令粒度のまま。 毎命令の境界で保留を確認し、受けられるなら連結を打ち切る。配送されるタイミングは非連結時と完全に同じ
  3. キャッシュのタグ+世代照合は毎命令やる。 連結が省くのはアドレス変換と外側のはしごだけで、照合は省かない。自己書き換えの検出は従来と同一
  4. 単発ステップの契約を守る。 デバッガとco-simが使うstep()は連結量0で「1命令だけ進む」まま
効果: 交互A/B 22.6s → 12.9s (-43%)   ← 期待の2〜4倍効いた

はしごとアドレス変換が毎命令のコストの半分近くを占めていた、ということだ。プロファイルで「ここが重い」と出ていた個々の関数より、毎命令の固定費の合計が本丸だった。

結果

段階 ネイティブ 実効速度
最適化前 (bzImage) 約2分 13 MIPS
vmlinux直接ロード 21.7s 26.7 MIPS
+ デコードキャッシュ 16.3s 35.6 MIPS
+ 控え削減 + ブロック連結 8.8s 66.2 MIPS

ブラウザ (WASM) はヘッドレスで13.6秒 (44.2 MIPS)、実ブラウザのフル起動で21秒。起動済みスナップショットからの復帰なら数秒である。

そして5倍速くなった後も、シェル到達の決定的命令数は580,999,942命令のまま1つも動いていない。全最適化を通して、実行された命令列がビット単位で同一だったという証明である。

教訓

  • switch型インタプリタの30 MIPSは構造の上限。 微修正では超えられない。実測でも、メモリ経路の小手先の修正は全てノイズに沈んだ
  • 意味の原本と速い写しを分ける。 速い経路が意味論を持ち始めたら二重実装の始まり。写しは原本と同じ部品を呼ぶ
  • 決定性は最強の検証装置。 「命令数が完全一致するか」だけで、最適化・リファクタの意味不変が機械的に確かめられる。この数字はCIが毎回見張っている
  • 固定費を疑う。 プロファイルに名前が出る関数より、毎命令の帳簿の合計が支配的なことがある。ブロック連結が43%効いたのはそのためだ

出口条件は100 MIPSに置いていて、残りの手札 (命令ペア融合、トレース化、JIT) は台帳に温存してある。次はGUI (フレームバッファ) とネットワーク (virtio-net) — 速さの地力はできた。

コメント

タイトルとURLをコピーしました