JavaScriptでx86エミュレータを書く

背景

コンピュータ・サイエンスのバックグラウンドを持たない者として、私は常々もっと低いレベルでプログラムのしくみを理解したい、そこに多くのエネルギーを費やしたいと考えてきました。

そこで、まずは基本を身につけるためにプログラミングの入門書である『Programming from the Ground Up』を入手したのですが、なかなか学習を始められずにいました。そんな時、ちょうどブラジルまでの11時間にも及ぶフライトが予定されており、それがこの本を読み始めるにはもってこいの機会となったのです。

読んでみると、この本がすっかり気に入ってしまいました。ただ、事例がLinux x86 GNUアセンブリ言語で書かれていたのです。私は64ビットのMac OS Xユーザでした…。アセンブラ、リンカフラグの例や、i386とx86_64間のシンタックスを理解するのにはインターネットが欠かせないほど悪戦苦闘しました…。

（i386では、exitシステムコールへの戻り値は%ebxにではなく、スタックに格納されなければなりません。また、x86_64では、システムコール番号に0x2000000のオフセットを考慮する必要があることや、レジスタが異なること、int $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つに分けることにしました。バイナリで実際のアセンブリ命令を見つけることと、それを実行することです。

Mach-Oバイナリフォーマット

バイナリには単なるアセンブリコードよりも多くの情報が含まれています。レイアウトやアーキテクチャのサポート、仮想メモリへのロード、シンボルなどに関する情報です。

Mach-O Binary image
注釈： バイナリのレイアウトをよりよく可視化するために、MachOViewをお勧めします。これは、バイナリ自体を調べるときに非常に便利です。

バイナリのアセンブリコードを見つけるためには、ロードコマンドを読み取る必要があります。具体的にはLC_SEGMENTロードコマンドです。これにはバイナリのセグメントを仮想メモリにマップするための情報が含まれているのです。

LC_SEGMENTロードコマンドには、いくつかのフィールドがあります。

  • コマンド（この場合はLC_SEGMENT）
  • コマンドサイズ
  • セグメント名（例えば__TEXT）
  • 仮想マシン（VM）アドレス（セグメントがコピーされる仮想メモリの場所）
  • VMサイズ（セグメントが使用する仮想メモリのサイズ）
  • ファイルオフセット（バイナリにおけるセグメントの位置）
  • ファイルサイズ（バイナリにおけるセグメントのサイズ）
  • VMプロテクションの最大値（VMに許された最大の保護レベル）
  • VMプロテクションの初期値（VMに対する初期の保護レベル）
  • セクション数（セグメントに含まれるセクションの数）
  • フラグ（mach-o/loader.hのstruct segment_commandの直後のコードで確認できます）

しかし、とりあえずはVMプロテクションとフラグを無視して、単にFile OffsetからFile Offset + File Sizeまでのバイナリのコンテンツを、VM AddressからVM Address + VM Sizeまでの仮想メモリ（このケースではシンプルなArrayBufferとして実装されている）にコピーします。

次は、LC_UNIXTHREADロードコマンドです。これにより、プログラムのメインスレッドの実行についての初期状態が分かります。

ここで重要なことは、%eip（命令ポインタ）の初期値です。これにより、最初のプログラム命令の仮想メモリにおける位置、つまりコードが実際に開始される位置が分かります（注釈：サンプルのコードでは、レジスタをシミュレートするのではなくPCと呼ばれるグローバル変数を使っています）。

バイナリの実行

さて、仮想メモリにプログラムコードをマップできて、コードの初めにポインタを合わせるところまで来たので、あとはただ実行する必要があります。面白いのは、x86には可変サイズの命令があることです。そのため、どのくらいのバイトになるのか、最初にオペコードを読まなければなりません。

x86 Instruction Format
“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）、オペコードのロジック（x86.js）、そしてエントリーポイントとして機能するindex.htmlです。このコードは基本的なアセンブリ言語とC言語を実行させることができます。

注釈：libcを実行させることはできませんので、C言語は-static –nostdlibでコンパイルし、カスタムアセンブリのブートストラップを提供する必要があります。

なお、このコードは全てハッカソンの機会に書かれた、非常にシンプルなものだということを改めてご認識ください。そのため、もっと読みやすいものにする（または、そうした点をより良くする）というところにはあまり注力されておらず、それ以上の書き直しということもしていないものになっています。

それでも、C言語で書いてclang -O3でコンパイルしたfibonacci(40)を実行するには十分でした。9分47秒という驚異的な実行時間を叩き出しましたが。

追記：HackerNewsでこちらのコメントを読み、DataViewをUint8Arrayと交換したところ、今やfibonacci(40)は1分53秒と、断然速くなりました。こちらの比較によれば、Perlやruby 1.8よりも速いものになったようです。

Previous Post