x86エミュレータ実装中に学んだ奇妙なこと
(timdbg.com)- Time Travel Debugging向けのCPUエミュレータをC++で書き直す過程で、x86/amd64では同じ動作でもエンコーディング・プレフィックス・実行モードに応じて異なる扱いが必要になる
int 3のCC単一バイトエンコーディング、ADD EAX, immの短い形式、効果のないREXプレフィックスのように、性能やデバッグに影響する代替表現が多いINC/DEC、CMPXCHG8B/CMPXCHG16B、shift/rotate命令はフラグ処理の方式が直感と異なり、エミュレータのバグにつながりやすい- shift countはオペランドサイズそのままでは適用されずマスクされるため、
shr eax,20hは32ビットレジスタを0にせず値を維持する - セグメントは32ビットおよび64ビットWindowsでのTEBアクセスに今も使われており、
FS/GSの意味やbase決定方式の違いが逆アセンブラやエミュレータ実装に直接影響する
TTDエミュレータ書き直しで見えてきたx86の細かな規則
- Time Travel Debuggingの一構成要素は、プロセス実行全体を命令レベルで記録するCPUエミュレータである
- 初代バージョンであるiDNAのエミュレータはほぼ全体がアセンブリで書かれており高速だったが、保守と拡張が難しかった
- 2つ目のバージョンではエミュレーション部分と、その後の大半の他部分をC++で書き直し、アセンブリ版の性能の大部分を維持しつつ、より管理しやすいコードベースを目指した
- CPUエミュレータを作るにはCPU動作の細部を漏れなく一致させる必要があり、x86経験者にとって馴染みのある規則も実装では改めて確認することになる
同じ命令を複数の方法で表現できるx86エンコーディング
- x86では同じ命令を複数のバイト列で表現できる
int 3はCD 03でもエンコードできるが、単一バイトのCCでもエンコード可能である- ソフトウェアブレークポイントとして使われるため、次ページがマップされていないメモリページ末尾の命令位置にもブレークポイントを置ける
- よく使うケースを短くするための代替エンコーディングもある
add eax, immは05ccccccccのように短く表現できる- 同じ値を
ECXに加えるには81c1ccccccccのようにさらに1バイト必要になる
EAXが“Accumulator register”と呼ばれるのは慣習だけではなく、実際にエンコーディング差を生み、短い命令はメインメモリから運ぶデータ量や命令キャッシュ使用量を減らして性能面で有利になりうる- コンパイラは可能な場合、こうした短いエンコーディングを活用できる
プレフィックスと15バイト命令長制限
- x86命令は動作を変えるプレフィックスバイトを持てる
- 64ビットコードでよく使われるREXプレフィックスは、32ビットコードより広いレジスタ範囲にアクセスするために使われる
- CPUは効果のないREXプレフィックスも受け入れる
4004ccは8ビットのadd al,0CChの前にREXバイトが付いた形だが、この場合REXには何の効果もない- REXプレフィックスを2つ並べてもCPUは実行でき、WinDbgを含む複数の逆アセンブラはこれに混乱することがある
- x86互換CPUでは現在の命令長の上限は15バイトである
- 15バイトを超える命令は無効命令と見なされ、例外を発生させる
- 古いCPUにはプレフィックスに関する別の制限もあり、
LOCKプレフィックスのように使用条件がより厳しいものもある
アドレスサイズとモードによって変わる解釈
- Address overrideプレフィックスは64ビットモードで32ビットアドレスを参照させることができる
488d0424はlea rax,[rsp]67488d0424は0x67プレフィックスのためlea rax,[esp]
- 32ビットコードではAddress overrideがアドレスモードを16ビットアドレスに変える
- 同じバイト列でも、コードセグメントのデフォルトのオペランドサイズとアドレスサイズを知らなければ正しく逆アセンブルしたり解釈したりできない
- 32ビットモードの
8b0424はmov eax,dword ptr [esp] - 64ビットモードの
8b0424はmov eax,dword ptr [rsp]
- 32ビットモードの
- x86で
INC regとDEC regに使われていた40〜4Fの範囲は、x64ではREX prefix bytesとして使われる- 32ビットモードでは
48 03 04 24はdec eaxとadd eax,dword ptr [esp]の2命令として解釈される - 64ビットモードでは
48030424がadd rax,qword ptr [rsp]という1命令として解釈される
- 32ビットモードでは
- AMD64の設計者は、64ビットモードでレジスタ集合を拡張するために
INC/DECの広いエンコーディング空間を新しいプレフィックスに使ったが、これらの命令には既にレジスタとメモリの両方をサポートする別エンコーディングが存在していた
WinDbgとINC regの64ビットモードでの落とし穴
- WinDbgは命令を常に32ビットモードのようにアセンブルするため、64ビットコードで
INC regをアセンブルしようとすると意図と異なる結果になることがある - 例では
inc eaxは実際のインクリメント命令ではなく、次の命令を修飾する無意味なREXプレフィックスに変わる - 結果としてそのバイト列は
incではなくjmp命令の前のプレフィックスとして解釈される
フラグ動作の例外
INC EAXはADD EAX, 1に似て見えるが、完全に同じではないADDはcarry flagを更新するINCはcarry flagを更新しない
- TTDエミュレータ実装中、この差を当初誤って実装しており、単体テストで見つかった
- 大半の算術・論理演算はoverflow、sign、zero、auxiliary carry、parity、carry flagを設定する
CMPXCHGもこれらのフラグを設定するが、CMPXCHG8BとCMPXCHG16Bはzero flagのみを変更する- 一部の命令はフラグの一部を未定義のまま残す
- shiftおよびrotate命令は、shift amountが1より大きいとoverflow flagを未定義のままにする
- 未定義フラグの実際の動作はshift演算の内部実装に関係しており、アーキテクチャによって異なる場合がある
- Atom系CPUがALUでより安価で遅い方式でbit shiftを実行するため未定義フラグ値が変わるという話もあるが、直接テストはしていない
shift命令のcountマスキング
66c1e810はshr ax,10hで、AXを16ビット右シフトするAXは16ビットレジスタなので結果は0になる
c1e820はshr eax,20hであり、表面的にはEAXを32ビット右シフトする命令に見える- 実際には
EAXの値は変化しない- Intel SDMではcountは
1Fhでマスクされ、rotationの下位5ビットだけが使われる REX.Wプレフィックスを使うとマスクは3Fhとなり、最大shift値は63ビットになる
- Intel SDMではcountは
- Microsoftの面接で「32ビットレジスタを単一命令でclearするすべての方法」を問う質問の中で、この動作が実際に問題になったことがある
- 面接官はshiftを使えば可能だと考えていたが、32ビットレジスタでは不可能だと答えた
32ビットと64ビットコードでも生きているセグメント
- セグメントメモリは16ビットコードの遺物のように見えるかもしれないが、32ビットおよび64ビットコードでも実際の効果がある
- 大半のOSはほぼフラットなメモリモデルを使い、セグメントbase addressを0にしているため、普段は意識しにくい
- 64ビットモードではCPUは
CS、DS、ES、SSのセグメントbaseを常に0として扱う
- 64ビットモードではCPUは
- 例外としてthread local storageには
FSやGSのような追加セグメントレジスタが使われる - 訂正として、
FS/GSセグメントのbaseは非特権コードでもrdfsbase、wrfsbase、rdgsbase、wrgsbase命令で読み書きできる- これらの命令はIvy Bridge、つまり2012年から利用可能である
Windows TEBアクセスとFS/GS
- Windowsでは
FSとGSはTEB(Thread Execution Block)を参照するために使われる - TEB構造体は構造体先頭のフラットアドレスを指すselfポインタを持ち、このアドレスはそのセグメントのbaseでもある
- 32ビットプロセスではTEBは
FSに置かれるGetLastErrorはfs:[00000018h]からTEB.NtTib.Selfを取得し、その後[eax+34h]からLastErrorValueを読む
- 64ビットプロセスではTEBは
GSに置かれるGetLastErrorはgs:[30h]からポインタを読み、[rax+68h]から値を取得する
- 64ビットOS上で動く32ビットプロセスは32ビットTEBと64ビットTEBの両方を持ち、32ビットプロセス内で動く64ビットWOWコードのように両方のTEBへアクセスする必要がある場面では有用である
セグメントbaseの決まり方もモードごとに異なる
FSとGSのbase addressを決めるCPU設定は、32ビットモードと64ビットモードで異なる- 32ビットモードでは、セグメントレジスタの実際の値がGlobal Descriptor TableとLocal Descriptor Tableで定義されたsegment descriptorを参照する
- 64ビットモードではbaseは2つのMSRで制御される
FS Base、Intel SDMでのIA32_FS_BASEGS Base、Intel SDMでのIA32_GS_BASE
- この構造のため、64ビットモードでは
FSとGSの実際のレジスタ値そのものは重要ではない- 重要なのはセグメントoverrideプレフィックスである
- WinDbgで32ビットプロセスをデバッグしているときは、
FSレジスタ値を使って「FS segment」の内容をdumpできる - 64ビットプロセスでは同じ方法は機能せず、セグメント値よりセグメントoverrideプレフィックスに意味がある
エミュレータ実装者が得る実務的な教訓
- x86エミュレータを作ると、命令エンコーディング、プレフィックス、フラグ、shift count、セグメントといったCPUの実際の動作を細かく扱わなければならない
- こうした規則のかなりの部分は一般的なコード記述ではほとんど役に立たないが、エミュレータ実装では直接的な要件になる
- 試行錯誤とメンタリングを通じて学んだことは多く、古いエミュレータ経験を持つDarek Mihockaとemulators.comもあわせて紹介されている
- x86最適化や低レベル動作に関心があるなら、Agner Fog’s websiteの資料が有用である
1件のコメント
Hacker News のコメント
ついでに BSF/BSR にも変わった点がある。Intel SDM は入力が 0 の場合、デスティネーションの値は未定義だとしているが、AMD はその場合デスティネーションは変更されないと文書化している
ところが glibc は、Intel でもデスティネーションが変更されないという未文書化の事実をそのまま利用している [1]。このせいで、自分のバイナリ変換器で問題の原因を見つけるのにかなり時間がかかった
また TZCNT/LZCNT は F3 プレフィックス付きの BSF/BSR エンコーディングだが、この拡張をサポートしない古いプロセッサではプレフィックスが黙って無視される。そのため同じコードが CPU によって異なる動作をするが、少なくともこれは文書化されている
エンコーディングでは人々がプレフィックスをよく悪く言うが、個人的にはそれが最悪ではない。よく知られていて、ある程度は文書化もされている。もっとひどい特異点もある。たとえば REX/VEX/EVEX.RXB 拡張ビットは、適用対象でなければ無視されるが、マスクレジスタ k0-k7 では #UD を起こす。ところがレジスタが ModRM.rm にエンコードされると、また拡張ビットが無視される
APX は特異点のレベルをさらに一段引き上げる。REX2 プレフィックスは汎用レジスタ r16-r31 はエンコードできるが xmm16-xmm31 はできず、EVEX プレフィックスは opcode によって複数のレイアウトがあり、レジスタに使われる拡張ビットもレジスタの種類によって異なる。XMM レジスタは X3:B3:rm と V4:X3:idx を使い、汎用レジスタは B4:B3:rm と X4:X3:idx を使う。1年たった今もまだ APX デコーダを完成できていないので、全リストは出せない
[1]: https://sourceware.org/bugzilla/show_bug.cgi?id=31748
EVEX については、opcode を読んで EVEX クラスを識別するまで生ビットを保持する方式でいこうとしている。つまり即値の前、おそらく ModRM の前の段階まで保持する計画だ
自分のデコーダはおおむねマニュアルの表に基づいており、コードはだいたい悪くない。インデントが過度でなく、段階もほとんど分離されているか識別しやすい。出力は JIT コードなので極端に効率的である必要はなく、読みやすいほうがいい。大半の時間が使われる場所でもない
それでもマニュアルが間違っていたり、全体を語っていなかったりする場合がいくつもある。表も何年も更新されておらず、たとえば K レジスタ命令もない。今後は手作業がもっと増えそうだ
先頭のコメントに状況が少し説明されている: https://github.com/qemu/qemu/blob/59084feb256c617063e0dbe7e6...
上で言ったように、まだ古いコードが処理している命令がいくつか残っていて、特に BT/BTS/BTR/BTC がそうだ。コードは書いたが、まだマージしていない
ところが 16ビットと 32ビットモードを切り替える 0x66 プレフィックスがある。これを BSWAP EAX に適用すると、未定義の奇妙なことが起きる
ある CPU アーキテクチャでは Intel と AMD の違いのようにプレフィックスが単に無視され、別のものでは自分が「内部スワップ」と呼んでいる動作をした。たとえば EAX に格納された4バイトのうち、1番目と2番目のバイトが入れ替わる
0x11223344 が 0x11332244 になる
かつて x86 は Intel の堀だったが、今では背負っていかなければならない悪夢のような重荷に見える
clz() という関数は存在するが、LZCNT が単に 0 入力のセマンティクスだけが異なる BSR だったなら、互換性を得るために実装で追加の減算をする程度は小さなコストだったように思う
同じプログラムをエミュレートした CPU でも実行し、各命令ごとに状態が同じか検証すれば、エミュレータがハードウェアを完全に模倣しているかテストできる
すごい人だ。アセンブリを書くのは単純に感じるし、縦に並んだ美学も好きだ
OP のような作業に少しでも近かった経験といえば、JS をやっている友人にスタックを理解させようとして、小さな ISA を持つミニ VM を一緒に作ったくらいだった: https://gist.github.com/darighost/2d880fe27510e0c90f75680bfe...
もっと深く掘り下げることもできたし、自分もそうしたかったが、そうすると本来の教育目的から外れてしまったように思う。その友人に、まだ一緒に勉強したいか連絡してみるべきだな。友人はすばらしい Web 開発でかなり稼いでいて深く掘り下げる時間がなく、自分は失業中で時間とエネルギーがほぼ無限の海のようにあるので、簡単ではない
Justine Tunney とそのエミュレータも見る価値がある。https://justine.lol/blinkenlights/
ドキュメントは CPU がどのように動作するかを見事に概観させてくれる
以前の議論はこちら: https://news.ycombinator.com/item?id=34636699
もう16か月も経ったなんて信じられない。時間が本当に早い
「CPUエミュレータを書くことがCPUの動作を本当に理解する最良の方法」という点には強く同意しない
最良の方法は、まともなコンピュータサイエンスの授業でやるように、ゲートレベルでCPUを作ることだ。縮小版ARMをゼロから作った作業は本当に面白かった
現代的なCPUエミュレータを作るほうがもう少し取り組みやすい挑戦で、一部だけ動いてもなお教育効果は大きい
ほとんどのソフトウェアエンジニアは、データハザード、キャッシュ無効化、パイプライン停止についての理解が不完全だ
しかし、意味のある作業に使いたいCPUをそうやって作り始めると、その細部への興味は薄れ始める。その時点では動作や仕様の複雑さのほうが面白くなり、エミュレータというアプローチのほうが扱いやすく、より多くの動作タイプを扱える
おもちゃではないアーキテクチャを12個ほど、速いエミュレータとして書き、いくつかJITトランスレータも作ったが、x86はいまだにPTSDものだ。こんなに汚いアーキテクチャは見たことがない。歴史も理由もあるが、それでもかなりひどい
最近サイドプロジェクトとしてx86-64デコーダのかなりの部分を実装したのだが [1]、最近はさらに複雑になっていることにかなり驚いた。自分の目的にはSandpile.org [2]が本当に役に立った
[1] 正確には、まだ公開されていない別のサイドプロジェクトのために作ったFabian Giesenのdisfilterのx86-64版: https://gist.github.com/lifthrasiir/df47509caac2f065032ef72e...
[2] https://sandpile.org/
大学で作った68kディスアセンブラは、Neoが「カンフーを知っている」と言う瞬間のようだった。高級言語からトランジスタまで、そして再び逆向きにコードについて推論させてくれる、欠けていたつながりだった
エミュレータ全体を書けば、それより一桁は効果的だと思う。良い記事だ
自分の記憶が間違っていたようだ。salsa20の変種と機械語がもともとcryp.toにあったと記憶していたが、Dan Bernsteinのサイトは https://cr.yp.to/ だった
スタートアップで保存データの暗号化、ストリーミング暗号化などを検討していたころ、Danのページには対象チップセットと命令セットごとに複数の実装があった。彼のアセンブラ表現からクロスコンパイルされたものだった
VMを使ってみて、2000年代初頭から半ば当時にどの命令セットがサポートされていたのかを見るのは興味深かった。テスト中には、VMがサポートすると主張していたものの実装が完全には対応しておらず、ときどき問題が起きることもあった
ここでRISCと比べてx86アセンブリがどれほどつらいかという話が多いのが面白い。自分はコードを再びオブジェクトファイルに分離するとき、正反対の問題がある
この用途ではx86の解析は本当に簡単で、MIPSは悪夢のようだった。主に気にするのがコードとデータへの参照だからだ。x86にはポインタサイズの即値定数があり、MIPSにはHI16/LO16再配置ペアがあって、レジスタ使用グラフ、コードフロー、分岐遅延命令と絡み合い、あらゆる問題が起きる
とはいえ、x86を褒めているわけではない
x86アセンブリとCを比較しながら学ぶ最大の点は、符号あり/なしが型ではなく演算の属性になることだ
フラグを活用できるとよいし、PPCやarmv7のような一部のアーキテクチャではそれがより簡単だが、x86はフラグをあまりにも簡単に上書きしてしまうため、値を活用するのが非常に難しい