2015年10月15日
JavaScriptでx86エミュレータを書く
WRITING AN X86 EMULATOR IN JAVASCRIPT
(2015-09-13)by Tadeu Zagallo
本記事は、原著者の許諾のもとに翻訳・掲載しております。
背景
コンピュータ・サイエンスのバックグラウンドを持たない者として、私は常々もっと低いレベルでプログラムのしくみを理解したい、そこに多くのエネルギーを費やしたいと考えてきました。
そこで、まずは基本を身につけるためにプログラミングの入門書である﹃ Programming from the Ground Up ﹄を入手したのですが、なかなか学習を始められずにいました。そんな時、ちょうどブラジルまでの11時間にも及ぶフライトが予定されており、それがこの本を読み始めるにはもってこいの機会となったのです。
読んでみると、この本がすっかり気に入ってしまいました。ただ、事例がLinux x86 GNUアセンブリ言語で書かれていたのです。私は64ビットのMac OS Xユーザでした…。アセンブラ、リンカフラグの例や、
i386
と x86_64
間のシンタックスを理解するのにはインターネットが欠かせないほど悪戦苦闘しました…。
︵ i386
では、 exit
システムコールへの戻り値は %e
bx
にではなく、スタックに格納されなければなりません。また、 x86_64
では、システムコール番号に 0x2000000
のオフセットを考慮する必要があることや、レジスタが異なること、 i
nt $0x80
ではなく syscall
を使わなくてはいけないことなどが分かりました…。こうしたことは、アセンブリ言語から始めた場合、いずれも容易なことではありません︶。
そのあたりは一旦考えないことにしようと思いましたが、やはりそうもいかず、とりあえずダミーとなるx86のパーサを書き始めることにしました。PCのバッテリーが切れるまでに、手始めとして行うにはちょうど良かったのです︵機内では電源が使えないこと以上に不便なことはないですね︶。
数ヶ月後、英チェルシーのスタジアムでFacebookのハッカソンが予定されていたのですが、その機会に、実際にバイナリがどう実行されるのかを理解するため、x86エミュレータを実装してみようと思いました。
このプロジェクトに取り組んでもらうため、関係者を説得するのは容易ではありませんでした。私がおかしくなったわけではないということ、そして私自身、正しいエミュレータを書くことがいかに難しいかを当然承知した上で言っているのだということを分かってもらうには時間がかかりました。さらに、あくまで 楽しみ
のためだけにエミュレータを書くこと、非常に基本的なケースのみを対象にするつもりだということを説明するのにも苦労しました。それでも、最終的にはUri Baghinに参加できることになったのです。
目標
初期の目標は、x86の最もシンプルなプログラムを実行することでした。それは、単にコード0
でプログラムを終了することです。
# program.s
.section __TEXT,__text
.globl start
start:
mov $0x1, %eax
push $0x0
call _syscall
_syscall:
int $0x80
Mac OS Xで上記のプログラムをビルドする方法は以下の通りです。
$ as -static -arch i386 -o program.o program.s
$ ld -static -arch i386 -o program program.o
テストするために、次のコマンドで実行と終了コードの確認ができます。
$ ./program
$ echo $?
そこで、私たちは問題を2つに分けることにしました。バイナリで実際のアセンブリ命令を見つけることと、それを実行することです。
注釈‥ バイナリのレイアウトをよりよく可視化するために、 MachOView をお勧めします。これは、バイナリ自体を調べるときに非常に便利です。 バイナリのアセンブリコードを見つけるためには、ロードコマンドを読み取る必要があります。具体的には
“KISS”︵Keep It Simple, Stupid︶の原則に従い、生成されたバイナリを
Mach-Oバイナリフォーマット
バイナリには単なるアセンブリコードよりも多くの情報が含まれています。レイアウトやアーキテクチャのサポート、仮想メモリへのロード、シンボルなどに関する情報です。注釈‥ バイナリのレイアウトをよりよく可視化するために、 MachOView をお勧めします。これは、バイナリ自体を調べるときに非常に便利です。 バイナリのアセンブリコードを見つけるためには、ロードコマンドを読み取る必要があります。具体的には
LC_SEGMENT
ロードコマンドです。これにはバイナリのセグメントを仮想メモリにマップするための情報が含まれているのです。
LC_SEGMENT
ロードコマンドには、いくつかのフィールドがあります。
●コマンド︵この場合は LC_SEGMENT
︶
●コマンドサイズ
●セグメント名︵例えば __TEXT
︶
●仮想マシン︵VM︶アドレス︵セグメントがコピーされる仮想メモリの場所︶
●VMサイズ︵セグメントが使用する仮想メモリのサイズ︶
●ファイルオフセット︵バイナリにおけるセグメントの位置︶
●ファイルサイズ︵バイナリにおけるセグメントのサイズ︶
●VMプロテクションの最大値︵VMに許された最大の保護レベル︶
●VMプロテクションの初期値︵VMに対する初期の保護レベル︶
●セクション数︵セグメントに含まれるセクションの数︶
●フラグ︵フラグの一覧は mach-o/loader.h の s
truct segment_command
の直後のコードで確認できます︶
しかし、とりあえずはVMプロテクションとフラグを無視して、単に F
ile Offset
から File Offset + File
Size
までのバイナリのコンテンツを、 VM Address
から VM Address + VM Size
までの仮想メモリ︵このケースではシンプルな ArrayBuffer
として実装されている︶にコピーします。
次は、 LC_UNIXTHREAD
ロードコマンドです。これにより、プログラムのメインスレッドの実行についての初期状態が分かります。
ここで重要なことは、 %eip
︵命令ポインタ︶の初期値です。これにより、最初のプログラム命令の仮想メモリにおける位置、つまりコードが実際に開始される位置が分かります︵注釈‥サンプルのコードでは、レジスタをシミュレートするのではなくPCと呼ばれるグローバル変数を使っています︶。
バイナリの実行
さて、仮想メモリにプログラムコードをマップできて、コードの初めにポインタを合わせるところまで来たので、あとはただ
実行する必要があります。面白いのは、x86には可変サイズの命令があることです。そのため、どのくらいのバイトになるのか、最初にオペコードを読まなければなりません。
“KISS”︵Keep It Simple, Stupid︶の原則に従い、生成されたバイナリを
objdump
で逆アセンブルしました。 objdump
は binutils
パッケージと共にインストールすることができるCLIです。すると次のようになります。
$ brew install binutils # if you don't have it installed yet
$ gobjdump -d program
Disassembly of section .text:
00001ff2 <start>:
1ff2: b8 01 00 00 00 mov $0x1,%eax
1ff7: 6a 00 push $0x0
1ff9: e8 00 00 00 00 call 1ffe <_syscall>
00001ffe <_syscall>:
1ffe: cd 80 int $0x80
機能を全て整えたエミュレータを実装しようとは思っていなかったため、とりあえず必要なオペコードのシンタックスを探したところ、x86向けの適切なリファレンス http://ref.x86asm.net/coder.html が見つかりました。
そこで、オペコードから関数へのマップ(本当にプレーンなJavaScriptオブジェクトで実装しました)を作成しました。関数は、オペコードにより必要となれば、より多くのデータを読み取るための役割を担います。例えば次のようなものがあります。
var Functions = {};
Functions[0x6a] = function () {
// Push one byte
push(read(1));
};
読み込んだオペコードが実はオペコードの接頭語だった場合は、次のバイトにある実際のオペコードを読み取らなければなりません。
var Fn0x0f = {
// jge
0x8d: function () {
var dist = read(4);
if (!NG) {
PC += dist;
}
},
// ...
};
Functions[0x0f] = function () {
// Call the actual function inside the prefix
var fn = read(1);
Fn0x0f[fn]();
};
最後に取り上げたいのは、システムコールです。実際にシミュレートする必要があるため、システムコール番号から関数へのマップをもう一つ使います。
var Syscalls = {};
Syscalls[0x01] = function () {
// Fake exit, since there's no OS
console.log('Program returned %s', Stack[Registers[ESP + 1]]);
PC = -1; // Mark the program as ended by setting the program counter to -1
};
バイナリのロードには、 File API を使いました。htmlのページは、バイナリをドロップする
input
があるエントリーポイントであり、そのアウトプットはコンソールに表示されます。
サンプルコード
ハッカソンの結果として出来上がったコードは、この gist で見ることができます。ここには、説明の通り3つのファイルがあります。ローダー︵mach-o.js
︶、オペコードのロジック︵ x8
6.js
︶、そしてエントリーポイントとして機能する index.
html
です。このコードは基本的なアセンブリ言語とC言語を実行させることができます。
注釈‥libcを実行させることはできませんので、C言語は -st
atic –nostdlib
でコンパイルし、カスタムアセンブリのブートストラップを提供する必要があります。
なお、このコードは全てハッカソンの機会に書かれた、非常にシンプルなものだということを改めてご認識ください。そのため、もっと読みやすいものにする︵または、そうした点をより良くする︶というところにはあまり注力されておらず、それ以上の書き直しということもしていないものになっています。
それでも、 C言語
で書いて clang -O3
でコンパイルした fibonacci(40)
を実行するには十分でした。 9分47
秒
という驚異的な実行時間を叩き出しましたが。
追記‥ HackerNews
で こちらのコメント を読み、 D
ataView
を Uint8Array
と交換したところ、今や fibonacci(40)
は 1分53秒
と、断然速くなりました。 こちらの比較 によれば、 Perl
や ruby 1.8
よりも速いものになったようです。
監修者
古川陽介
株式会社リクルート プロダクト統括本部 プロダクト開発統括室 グループマネジャー 株式会社ニジボックス デベロップメント室 室長 Node.js 日本ユーザーグループ代表
株式会社リクルート プロダクト統括本部 プロダクト開発統括室 グループマネジャー 株式会社ニジボックス デベロップメント室 室長 Node.js 日本ユーザーグループ代表
複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。
現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。
2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。
Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。
- Twitter: @yosuke_furukawa
- Github: yosuke-furukawa