x86エミュレータを自作する — 正解を知っているCPUに答え合わせさせる

ゲームボーイエミュレータを完成させた勢いで、次はx86に手を出した。最終目標は「ブラウザで32bit Linuxが起動し、busyboxシェルが叩ける」こと。今回はその第一歩、リアルモード8086が動くところまでの開発記である。

主役は命令の実装ではなく検証手法だ。x86にはゲームボーイのBlarggテストROMに相当する「これを流せば全部わかる」テストが存在しない。代わりに、正解を知っているCPUに答え合わせをさせる仕組みを作った。

コードはGitHubで公開している: https://github.com/yoshiharu-ishii/rustx86

この記事では図とコードで役割を分けている。図は「どこで何が起きるか」という全体の地図で、コードはその地図上の一点を実際に動かしている実物である。各図の下には対応するソースファイルへのリンクを置いたので、地図で位置を掴んでから実物を見に行ってほしい。

なぜx86は大変か
実行の仕組み
正解を知っているCPUに答え合わせさせる
緑のテストは、それ自体では何も証明しない
ランダムでは踏めない床があった
オラクルも嘘をつくことがある
932行になったので割った
まとめ

なぜx86は大変か

ゲームボーイのSM83と比べると、x86の面倒さは桁が違う。

命令が可変長: 1〜15バイト。プレフィクス(セグメント上書き、REP、LOCK)が任意個先頭に付く
歴史の地層: リアルモード→プロテクトモード→ページング→ロングモード。Linuxを起動するにはこの層を貫通する必要がある
EFLAGSの意味論: 全ALU命令がCF/OF/SF/ZF/AF/PFの6フラグを規則に従って更新する。特にAF(下位4bitからの桁上がり)とOF(符号付きオーバーフロー)は境界値でしか姿を現さない

3つ目が最大の敵だ。フラグが1ビットずれるバグは、Linux起動中に条件分岐がひとつ曲がって初めて発覚し、そこから原因の命令まで遡るのは地獄である。

実行の仕組み

まず全体像から。命令1個の実行はこう流れる。

rustx86の命令実行の流れ: プレフィクスを剥がしオペコードを読み、巨大なmatchで命令グループに振り分け、共通部品を経てレジスタとメモリを更新する

図の役割: 命令1個が通る道筋。この図の「巨大な match」が cpu/mod.rs で、下の段の共通部品が cpu/operand.rs cpu/alu.rs などにあたる。

コードの役割: 上の図の「ALUグリッド」の箱を実際に開けると、こうなっている。

x86のオペコードは一見でたらめだが、規則的な「格子」を持つ部分が大きい。たとえば 0x00〜0x3D はADD/OR/ADC/SBB/AND/SUB/XOR/CMPの8演算 × 6形式の格子になっていて、48命令が1つのハンドラで処理できる。

0x00..=0x3F if op & 7 <= 5 => {
    let kind = (op >> 3) & 7;   // 演算種別
    match op & 7 { /* 形式ごとにオペランドを解決 */ }
}

ゲームボーイで確立した「ビットパターンで畳む」方式がそのまま効く。畳めない歴史的な不規則部分(十進補正やストリング命令)だけ個別に書けばいい。実物は cpu/mod.rs の match にある。

正解を知っているCPUに答え合わせさせる

本題の検証手法だ。使ったのはUnicorn Engine、QEMUのCPUエミュレーション部分をライブラリとして切り出したものである。Rustから数行で呼べる形で「正確なx86」が手に入る。

これをオラクル(神託)として、同じ問題を自作CPUと解かせて答えを突き合わせる。co-simulation(比較実行)と呼ばれる、ハードウェア検証では定番の手法だ。

co-simの流れ: 同じ初期状態を自作CPUとUnicornオラクルに与えて1命令実行し、レジスタ・フラグ・メモリを突き合わせる

図の役割: 検証の1サイクル。実物は cosim/src/lib.rs (状態の定義と差分表示) と cosim/tests/alu.rs (オラクル呼び出しと命令テンプレート) に分かれている。

肝は同じ初期状態を両方に与えること。レジスタもフラグもメモリも揃えて1命令だけ走らせ、実行後の全状態を比較する。食い違えば自作CPUのバグで、しかも「どの命令の、どの入力で、どのフラグが」という粒度で即座に分かる。

生成はランダムだが、完全なランダムバイト列は撒かない。ほとんどが無効命令になって無駄だからだ。代わりに「このオペコードはこういう形」というテンプレートを定義し、オペランドと初期値だけを振る。初期値には0x00/0x01/0x0F/0x10/0x7F/0x80/0xFFといった境界値を高頻度で混ぜる。AFやOFは境界を踏まないと姿を現さないからである。

緑のテストは、それ自体では何も証明しない

ALU全8演算・メモリオペランド・シフト/回転・乗除算・十進補正・ストリング命令、と実装してテンプレートを足していったところ、全部一発で通った。

ここで手を止めた。テストが緑なのは、実装が正しいからか、テストが何も見ていないからか。区別がつかない。

そこで、わざとCPUを壊して検出されるかを確かめた(変異テスト)。ADCのAFフラグ計算からキャリーの加算を1箇所落とす。

[ADC r/m8,r8] code=[10, d4] regs=[8000, 19ff, ...] flags_in=CF|PF
  FLAGS: ours=PF|SF oracle=PF|AF|SF (差分 AF)

即座に捕まった。命令、入力レジスタ、違うフラグまで出る。これでハーネスは信用できる。

ランダムでは踏めない床があった

ところが、2つ目の変異で問題が露呈した。十進補正命令DAAの境界値を 0x99 から 0x9A にずらしてみたところ、3000ケース流しても検出できなかった。

理由は単純で、ALがちょうど 0x9A になるケースを踏み損ねていたのだ。ランダム生成は広く浅く探索するので、1点だけの境界には当たりにくい。

DAAのような十進補正命令は、ALの値とCF/AFだけで分岐が決まる。状態空間は 256 × 3 × 4 しかない。ならば総当たりすればいい。

co-sim mismatch [DAA] code=[27] AX=009a flags_in=-
  AX: ours=00a0 oracle=0000

切り替えた途端、まさに 0x9A で一発で捕まった。状態空間が小さいならランダムより総当たりという、当たり前だが実際に踏むまで気づかない使い分けである。

オラクルも嘘をつくことがある

もう一つ面白い引っかかりがあった。ストリング命令のテストで、こんな差分が出た。

[MOVSB] SI: ours=0000 oracle=ffff
        DI: ours=1060 oracle=105f
        IP: ours=1001 oracle=1000

自作CPU側はSI/DIを更新しているのに、オラクル側は何も変わっていない。IPすら進んでいない。つまりUnicornは命令を実行しなかった。

原因はランダムなDIがコード領域を指していたことだった。QEMUは自己書き換えコードを検出すると、生成済みの変換ブロックを捨てて命令をやり直す。1命令だけ実行する設定だとその「やり直し」で止まってしまう。自作CPUのバグではなく、オラクル側の都合である。SI/DIをデータ領域に収めて解決した。

オラクルは正しいが、オラクルの使い方は間違えられる。差分が出たとき「自分が悪い」と決めつけないのも大事だと学んだ。

932行になったので割った

命令を増やすうちに cpu.rs が932行に育った。プロテクトモードを実装すれば確実に倍以上になる。

分割にあたって、命令ごとに1ファイルにはしなかった。x86の命令は数百あるし、そもそもALUグリッドのように48命令が1ハンドラで処理される構造を壊してしまう。代わりに、振り分け表と共通部品を分けた。

ファイル	役割	行数
`cpu/mod.rs`	オペコードの振り分け表(巨大なmatch)	502
`cpu/operand.rs`	ModRM解決、オペランドアクセス、スタック	116
`cpu/alu.rs`	8演算とフラグ計算	96
`cpu/shift.rs`	シフトと回転	94
`cpu/string.rs`	ストリング命令とREP	119
`cpu/decimal.rs`	十進補正	73