C言語でWASMインタプリタを実装した話
概要
公式のcore testが全て(UTF8, WAT, SIMD関連のものは除く)通るWASMインタプリタをC言語でフルスクラッチで実装した。自作WASMランタイムで省略されがちなValidation Stageも実装した。この記事はWebAssembly Advent Calendar 2023の三日目の記事である。
目的
このWASMランタイムを実装するにあたり、「できるだけ仕様に従って実装する」ことを心掛けた。WASMの仕様書は以下のissueが立つほど読みにくいものとなっているが、ランタイムをどのように実装すべきかが詳しく書いてあり、一応仕様書を頑張って読めばランタイムが作れるようになっている。
この自作WASMランタイムの目的は、できるだけ仕様に従った実装を与えることで、仕様の理解を助けることである。早さや効率性よりも分かりやすさを優先しているため、実用には向かない。仕様書を読んで、実装に困った際に参照してほしい。
実装の規模感
「tiny」といいつつ、ソースコードは空白行含めて6000行弱になっている。完成まで2カ月弱かかった。
WASM Specの概観
Wasm Specは以下の画像のように章分けされている。「Structure」ではWASMモジュールが形式的に定義され、「Binary Format」でそれがバイナリとしてどう表現されるかが定義される。「Validation」や「Execution」では「Structure」で定義された形式的なWASMモジュールをどのように検証し、実行するかが述べられている。WASMランタイムには「Decode」, 「Validation」, 「Execution」という三つの段階があるが、それぞの段階をこの仕様にできるだけ従って実装した。
工夫した点
Exceptional C
WASMランタイムでは多くの箇所で検証を行うため、「条件が成り立つか調べ、成り立たなかった場合はエラーを返す」という処理を頻繁に使う。ifとreturnを使うとごちゃごちゃするため、以下のようなマクロを定義した。
これを用いると、例えば以下のように「例外処理」が実現できる。ifとreturnを多用するよりも分かりやすいコードになっていると思う。このアイデアはWasm3からもらった。
VECTORマクロ
C言語には動的配列がない上に、Generic Programmingをすることが難しい。そこで、VECTORマクロを以下のように定義した。
これを使うことで、C言語であっても以下のように書く事ができる。
上はValidationで使うContextという構造を定義したものだが、VECTORマクロを使うことで、仕様書の記述とほぼ一対一に対応させることができている。
この他に、VECTOR_FOR_EACHやVECTOR_APPENDのようなマクロも定義した。これは以下のように使うことができる。
Software paging
WASMの仕様では線形メモリの1pageは64KiBと定義されており、メモリがインスタンス化される際は最小値として設定されたページ数が確保される。さらにWASMにはmemory.growという命令があり、最大値として設定されたページ数までページを増やすことができる。
簡単なプログラムであれば64Kibもメモリを使うことはまずないので、実際に64Kibの割り当てを行うのは非効率である。さらに仮想メモリがないシステムでは64Kibも連続したメモリを割り当てるのは非現実的である。そこで以下のように、ソフトウェアによりページングを実現した。
3段ページングを採用しているため、メモリインスタンスには4つのエントリしか必要ない。
この実装により「必要なぶんだけメモリを割り当てる」ということが実現できている。
辛かった点
end命令
WASMのend命令は 「なんのendか」によって処理が変わる。loop, block, if命令のendの場合は基本的に以下の処理を行う。
しかし「When the end of a block is reached without a jump or trap aborting it」とあるように、brやbr_if命令によってこのendに飛んできた場合は例外である。
さらに関数のendの場合は基本的に以下の処理を行う。
しかしこれも「When the end of a function is reached without a jump (i.e. return, ) or trap aborting it」とあるように、return命令が実行された場合は例外である。
つまり、end命令を正しく実行するためには「if, loop, block命令のendか否か。そうである場合brやbr_if命令によってendに到達しているか否か」、「関数のendか否か。そうである場合return命令が実行されているか否か」を考慮する必要があり、仕様書にはさらっと書いてあるが実装するのはかなり大変だった。
公式のテストスイート
公式がテストスイートを用意しており、自作WASMランタイムでもこれをテストに用いている。今回通したcoreテストは以下。
これを見ると「各命令ごとにテストがあるんだな」と思うだろうが、実際はそうではない。例えばbr.wast, if.wastのような制御命令のテストには「call_indirect」という命令が含まれており、これをサポートするまでは制御命令のテストを通すことができない。つまり、このテストスイートはランタイムがある程度育ってからでないと通すことができず、インクリメンタルな開発には向かないのである。一つ一つ通していくという感じではなく、ある時点になると突然沢山のテストが通せるようになるという感じなので、開発の初期段階ではテストをなかなか通すことができず、苦労した。
WASM Specへの貢献
WASMランタイムを実装する中で、仕様書にバグや不明瞭な点を見つけて報告した。具体的には4つのissueと1つのPRを投げた。
考察
WASMはAssemblyなのか？
実装してみて分かったことは、WASMの命令は抽象度がかなり高いということである。ifやloopが命令として存在しているし、call_indirect(関数テーブルを用いた関数呼び出し)や、convert(Cの型キャストみたいなやつ)も命令として存在している。そのため、WASMはAssemblyというよりインタプリタ言語である。命令の抽象度が高いため、命令の実行部分がかなり長くなる。例えばcall_indirect命令の実行部分は以下のようになっている。
ifやloopは比較と条件分岐があれば実装できるため、新たに命令として定義する必要はないのだが、それでも命令として用意されているのはできるだけバイナリサイズを小さく、しかし"高級な"ことをできるようにしたいというモチベーションがあるからだと推測できる。
WASMはなぜportableなのか?
WASMのDesign Goalsの一つに「Portable」がある。OSやCPUに依存しない「汎用的なバイナリ」を作れることがWASMの利点の一つであるが、その汎用性は結局、 「みんなが使っているから」 実現されている。みんなに使ってもらうためには仕様が大きすぎず、かつある程度高級なことができる必要がある。WASMの命令は上で見た通り抽象度が高い。これはコンパイラ等、言語処理系の実装者からすると嬉しいことである。さらにWASMは(今のところ)個人でもランタイムを作れるほど小さい仕様になっている。だからWASMは色んな環境で動くし、CやRustといった様々な言語からWASMにコンパイルすることが可能になっている。しかし、この状態が続くとは限らない。WASMにGCを導入するという話があるように、これからどんどん仕様が大きく、複雑になっていくことが予想される。その結果、ランタイムの実装者が一部の機能をサポートしないという選択を下し、汎用だったはずのWASMバイナリが結局ランタイム依存になる恐れがある。そうなるともはやWASMを使う意味がなくなってくる。WASMが廃れないためにも、仕様を拡張する前に原点に立ち返り、「本当にそれは必要か」を考える必要があるように思う。
WASMはなぜセキュアなのか?
WASMのDesing Goalsに「Safe」がある。WASMがセキュアなのは多くの場所でチェックが行われるためである。たとえばValidationでは、関数の型と命令列の型が一致するかや、未定義の関数を呼び出していないかがチェックされる。Executionでは整数オーバーフローやゼロ除算はもちろん、メモリの範囲外にアクセスしていないかや、未定義のテーブル要素にアクセスしていないかがチェックされる。実装して思ったことは「WASMは検証に向いたバイナリ形式である」ということだ。例えばModule内の関数(importされたものも含む)には0からのインデックスが付き、call命令ではこのインデックスを指定する。ネイティブの機械語とは異なりアドレスを指定するわけではないため、検証が容易になっている。
また、WASMの「メモリ」は0番地からのフラットなバイト配列であり、上で見た通り使うページ数をあらかじめ宣言する仕様になっているため、loadやstore等、メモリアクセス命令の実行時に範囲外アクセスを検知することが容易になっている。(検証できるのはあくまで宣言されたページ範囲に収まっていることだけであることに注意)
たとえ将来WASMが廃れたとしても「検証容易な中間言語としてのWASM」の価値は残り続けると考えられる。
おわりに
仕様に従って実装したことでWASMの仕様書が読めるようになったし、WASMに対する理解度が格段に上がったと感じる。WASM Specはお世辞にも読みやすいとはいえないため、機会があれば「WASM Specの読み方」という記事を書いてみたいと思う。
Discussion