Share
Embed
Rustで作るフルスクラッチQEMU型エミュレータ
msyksphinz
March 20, 2021
Transcript
16 slides
-
TL; DR • QEMU型 (Binary Translation)の命令セットエミュレータを作った • QEMUについて調査する中で、QEMUがどのように命令を エミュレートしているのかを知る良い機会になった。 命令セット
エミュレータとは QEMUのTCG (Tiny Code Generator) Rustでコーディングする モチベーション 最適化技術 考察 -
命令セットエミュレータ(シミュレータ) ⚫様々なエミュレータ ⚫ 複数ターゲットアーキテクチャ向け:QEMU (x86, ARM, MIPS, RISC-V, ....) ⚫
命令セットシミュレータ ⚫ (無償、商用含め):Spike (RISC-V), Imperas Simulator (MIPS, RISC-V ...) ⚫ プレイステーション(2)とか (ePSXe) ⚫ 量子計算のシミュレータ ⚫ ハードウェアのシミュレータ (ハードウェア記述言語で記述された回路をシミュレーションする) RISC-V バイナリ 命令セットエミュレータ ARM バイナリ x86 バイナリ x86 (Intel) ARM ARM M1 00000000800000f4 : 800000f4: 00000093 li ra,0 800000f8: 00000113 li sp,0 800000fc: 00208733 add a4,ra,sp 80000100: 00000393 li t2,0 80000104: 00200193 li gp,2 80000108: 4e771063 bne a4,t2,800005e8 フェッチ デコード 実行 PC更新 -
QEMU • プロセッサエミュレータ • x86 (IA32/x86-64) • SPARC • MIPS
• ARM • SH4 • PowerPC • MicroBraze • RISC-V • etc... • システム全体をエミュレート できるのが特徴 • (定量的なデータは無いが)一般的な 命令セットシミュレータより高速 QEMUはエミュレータ界のLLVMだ Alpha i386 ARM/AArch64 m68k MicroBlaze MIPS nios2 PowerP C RISC-V RX SH SPARC AArch64/ARM i386 MIPS PowerPC RISC-V SPARC TCGに変換 TCG ホスト命令に変換 ゲストアーキテクチャ ホストアーキテクチャ -
エミュレーションの方法 インタプリタ型 • ゲスト命令を1命令ずつ解釈し、その動作 をプログラミング言語で模擬する • Spike (riscv-isa-sim) • Gem5
(?) バイナリ変換型 • ゲスト命令をホスト命令に変換し実行する • OVPSim • QEMU 長所 短所 インタプリタ型 実装・仕様修正が容易 任意のアーキテクチャに移植可能 (コンパイラが用意できれば) バイナリ変換型に対して 実行速度が遅い バイナリ変換型 インタプリタ型に対して 実行速度が速い 実装・仕様修正が困難 アーキテクチャの移植が困難 -
TCG(Tiny Code Generator)による中間表現 LLVMと同様に、QEMUも「ゲストISA」と「ホストISA」の間に中間言語を持っている Register Read Add Register Store 1命令だけではなく、実際には分岐を含まない連続した命令を
「TCGブロック」として一括して管理している。 この例では という RISC-V命令がTCGを経由して以下の3命令に変換される 実際にはTCG上で最適化が行われ、 1. すでにレジスタ値がx86レジスタ上にロードされている場合、 2. 次の命令が計算結果を即時使用する場合 の1命令に変換される。 TCG x86 -
QEMUをRustで書こう • QEMUと同じ「バイナリ変換型シミュレータ」をRustで書こうという モチベーション • もともとRISC-VエミュレータをRustで書いていた • 「Rustで書くと安全」という神話も知っていた • 「私は本当にTCGを理解したのか?」
• 答え合わせのためにフルスクラッチでQEMUを自作し、 Rustで書くことに意味があるのかを手を動かして探る。 • Rustで書いた自作バイナリ変換型シミュレータ「Dydra」 • https://github.com/msyksphinz-self/dydra • RISC-Vバイナリ → x86ホスト • 本当に勉強用に書いたので実用性は皆無 • (数か月前の成果で、最近飽きたので)、あまり メンテナンスできてません... http://blog.vmsplice.net/2020/08/why-qemu-should-move-from-c-to-rust.html RustでQEMUを書こうじゃないか、的なことを言っているブログ → -
共通コンポーネント ホストマシン用 コンポーネント (x86) ゲストマシン用 コンポーネント (RISC-V) 実装 ELFローダ ELF
PC レジスタ ファイル メモリモデル 1. フェッチ 2. RISC-V命令 デコード TCG 3. TCG→x86命令 変換 x86命令 ブロック 4. x86命令実行 システムレジスタ すでに当該命令をx86に 変換済みであれば、直接 x86命令を読み出す 制御モード エミュレーションモード -
自作QEMUのデバッグテクニック RISC-Vバイナリ デコード TCG生成 ここは デバッグできる • 問題点:自作QEMUがどんな命令を生成し実機でどのような結果になったのか、観察できない • 生成した命令の挙動をGDBなどで確認できない。DWARFまで生成できれば良いが...
• 解決策:自作QEMU on 本物QEMUで実行しログを取得し観察 自作QEMU RISC-Vバイナリ (本物の) QEMU x86 CPUコア 本物の を実行 自作の を動かす 実行対象は バイナリ 本物の が、自作 の実行結果を記録する 変換後バイナリの実行結果を含む x86命令 ここは デバッグできる 辛うじて デバッグできる CPUで実行 デバッグが困難 突然Exceptionが起きたりすると何が起きているのか分からない。 曼荼羅みたいな世界になる。 「仮想マシンの世界は仏教的?」という話を 聞いたことがあるような... -
(すごく頑張った)実装結果 riscv-tests (RISC-VのISAテストパタンセット) のAtomic命令以外のパタンをすべてPassさせた。 浮動小数点もサポートした(浮動小数点についてはQEMUがsoftfloatを使用しているためそのまま実装) MMUはサポートした(やってはいないが頑張ればLinux立ち上げまで行けるはず) • とりあえずDhrystoneを動かした ※ Dhrystone
: CPUベンチマーク界では最初に実行するベンチマーク 単純すぎてIntel Compilerでコンパイルすると最適化で中身が消えるとかなんとか 0 5 10 15 20 25 30 35 Spike 初期実装版 QEMU-5.1.0 実行時間(秒) インタプリタ型 シミュレータ 私が作ったやつ インタプリタ型には完勝。QEMUには完敗。 さて、QEMUに近づくためにはどうしたらいいんだ? -
QEMUの高速化テクニック TCG Block Chaining BEQ t0,t1,label • 実行後処理 • 次の命令の
TCGサーチ • TCG実行 へ変換された 命令の実行 次のブロック ②jmpのオペランドを 書き換える BEQ命令、実行1回目 次のブロックのアドレス BEQ t0,t1,label へ変換された 命令の実行 次のブロック ②次のブロックに 直接ジャンプ BEQ命令、実行2回目 ①比較条件 成立時 ①比較条件 成立時 TCGブロックからTCGブロックへのジャンプ 次のTCGブロックを実行するのに、一端制御側(Rust)に戻るのはもったいない。 すでにチェーンができていれば直接ジャンプする。 -
TCG Block Chaining導入結果 • 自作QEMUにTCG Block Chainingを実装した。 • Dhrystone: 3秒後半
→ 2秒前半まで向上 0 2 4 6 8 10 Spike 初期実装版 TCG Block Chaining 導入 QEMU-5.1.0 QEMUにとって、エミュレーションモードを終了し制御を戻すコストは大きい。 TCG Blockを検索し、再実行する回数を可能な限り減らすことがミソとなる。 (特にRustはHash関数が高速ではない、という話のため?) Rustの性能解析ツールを使ってPerfを取得 1. 大部分がRustによる制御コードで 2. エミュレーションモードの実行時間はわずか 制御部分の時間をどれだけ減らせるかがカギとなる エミュレーション 部分 制御部分 -
QEMUの高速化テクニック TCG Lookup and Jump レジスタ値ジャンプはBlock Chainingで予測はできない。 そこで、「ジャンプアドレスが計算できた段階で、そのアドレスの命令がTCGに変換されているか」を探索 すでに変換されていれば直接TCGブロックにジャンプ RET
(JR ra) へ変換された 命令の実行 次のブロック RET (JR ra) 次のジャンプ先が すでにブロック変換 されているかどうかを検索 へ変換された 命令の実行 次のブロック ヒット時は直接 ジャンプする (Rust側) TCGブロック探索 ポインタ設定 TCGブロック実行 -
TCG Lookup and Jump 導入結果 • 自作QEMUにTCG Lookup and Jumpを実装した。
• Dhrystone: 2秒前半→ ほぼ2秒まで向上 0 2 4 6 8 10 Spike 初期実装版 TCG Block Chaining 導入 TB Lookup and Jumpを実装 QEMU-5.1.0 QEMUにはまだ倍以上の差を付けられている。 今回実装できなかった様々な最適化が、QEMUには実装されている。 -
その他QEMUによるTCG最適化実行例 側 各命令でレジスタの 依存関係のある命令列 ホスト側 に を格納 に を格納 に
を格納 に を格納 に を格納 最初の命令が0+10=10から始まって いるため、この場合すべての命令で実 行前にレジスタ値が計算可能 全て定数生成命令に 変換されてしまった! 側 ホスト側 ホスト側 例1. 疑似的な依存関係のある命令を、依存関係の無い命令列に変換 例2. レジスタの依存関係による、明らかに不要なメモリアクセスを削減 -
Rustを使って良かったか? Rustは安全なプログラミングを提供する言語ではなかったか? Rustの言語としての安全性は「Rustコンパイラにより生成されるアセンブリ命令によるもの」 従って、それを破ると当然Rustで書いても安全ではないプログラムが作られてしまう。 実際にQEMUのアルゴリズムをそのままRustで実装すると 「ゴリゴリにメモリアクセスを制御する」必要が生じた → 大量のunsafe文を挿入する必要が生じた Rustのコンパイラがまかり知らぬ関数にジャンプする →
ジャンプ先で「アクセス権限を破る」ような動作をするが、それは許される。 Rustの安全性はコンパイラによる静的解析に依存する場所が多い。 例: Rustが配列外アクセスを防ぐのは、 そういうアセンブリ命令を 生成しているから。 最適化の例「Block Chaining」 はメモリ中のジャンプオフセットを 上書きする 静的に解析できない場所へジャンプして いるので当然。unsafeも使っている 単純にQEMUで実装されていることを 「Rustで書き直せば良いということではない」ということが分かった。 そのプログラミング言語に合うような書き方をしないと、結局意味がない。