🦍

RustでWasm Runtimeを実装してみた

2023/04/24に公開

Rust

WebAssembly

tech

はじめに

最近Wasmの勢いがすごくて、ブラウザでPostgreSQLを動かせたり、DockerでWasmを動かせたりできます。

以前からWasm自体に興味があって、動作原理を知りたいと思ってchibiwasmというRuntimeを実装してみました。
Rustを選んだのは、最近Rustを勉強していてそれに慣れるためです。
苦労しましたが、*.wasmがどのようにして実行されるのかを理解できたので良かったです。

https://github.com/skanehira/chibiwasm

今回はWasmのバージョン1の仕様を満たすように実装して、テストスイートは正常系と実行時異常系のテストは通しましたが、バリデーションなどのテストはスキップしています。
また、少しだけバージョン2の命令とWASIを実装していて、RustからビルドしたHello Worldを標準出力するwasmバイナリも動きます。

本記事は実装したWasm Runtimeの概要と、実装を通して学んだことについて書いていきます。
Wasm自体についてはあんまり説明しないので、よく知らない方はこちらを一度読むとよいかと思います。

単語

本記事では次の意味で単語を使っているので、それを踏まえて読んで頂ければと思います。

単語	意味
wasmバイナリ	`*.wasm` ファイルそのもの
Wasm Runtime	`*.wasm` を実行する環境
Wasm Spec	Wasmの仕様書（バージョン1）
Wasm	仮想命令セットや実行環境の仕様
WASI（WebAssembly System Interface）	WasmからOSのリソースにアクセスするための仕様
wat	Wasmのテキスト形式（S式で記述する）

Wasmは簡単にいうとOS/CPUに依存しない仮想な命令セットやその実行環境の仕様を指します。雑にいうとJVMみたいなものです。
その仕様とおりに実行環境で実行できるファイルが*.wasmで、実行環境がWasm Runtimeと呼ばれたりします。

WASIに関してはイメージしづらいかと思いますが、簡潔にいうとOSに依存しないポータブルなシステムコールを定めた仕様です。
たとえば標準出力に文字を出力するのにfd_write(i32, i32, i32, i32) -> i32というPOSIXライクなシステムコールを実装する必要があります。

厳密にいうとfd_writeを実装しなくてもprint()のような関数を実装してメモリから文字読み取って出力できますが、仕様とおりに実装すれば他の言語でコンパイルしたwasmバイナリを実行できます。

Wasm Runtimeの概要

Wasm Runtime自体はスタックマシンとしてWasm Specで定義されています。
たとえば、次のようなi32型の数値2つを足す関数を記述したwatがあるとします。

(module
  (func $add (export "add") (param i32 i32) (result i32)
    (local.get 0)
    (local.get 1)
    (i32.add)
  )
)

この場合、2つの引数をスタックに積んでi32.add命令を処理するときスタックから2つの値をpopして加算した結果をstackにpushといった処理を行います。
TSを用いた擬似コードだとこんな感じでしょうか。
pcはプログラムカウンタで処理する命令を指しています。処理系ではよくやるパターンかと思います。

const stack: number[] = [];
const locals = [1, 2];
enum Inst {
  LocalGet,
  I32Add,
}

const insts = [
  Inst.LocalGet,
  0,
  Inst.LocalGet,
  1,
  Inst.I32Add
]

let pc = 0;

while (pc < insts.length) {
  const inst = insts[pc];
  switch (inst) {
    case Inst.LocalGet:
      const operand = insts[++pc];
      const value = locals[operand];
      stack.push(value);
      break;
    case Inst.I32Add:
      const a = stack.pop()!;
      const b = stack.pop()!;
      stack.push(a + b);
      break;
    // .. 他にも色々な命令の処理がある
  }
  pc++;
}

console.log("output:", stack.pop()); // output: 3

命令処理は簡潔にいうとこのようなことをやっているだけですが、他にも制御命令（ifなど）などがあってなかなか大変です。

chibiwasm実装自体はWasm Specをみつつ、他の方が実装したWasm Runtimeを参考にして実装を進めていきました。
細かく説明すると色々ありますが、大まか次のことをやっています。

wasmバイナリをデコードし、バイナリを表現したデータ構造（Module）に落とし込む
- バイナリにはi32.constといった命令群、メモリ定義、グローバル変数などがある
1の構造体を元に実行するためのデータ構造（Runtime）を生成する
- メモリの定義を元にメモリの確保と初期化（静的データの配置）し、それを保持する構造体を用意といった感じ
startセクションがあれば、指定された関数を処理する
- 関数は命令群を持っているため、先ほど提示したコードのように命令を処理していく

1. wasmバイナリのデコード

Wasmはモジュールという単位となっています。
1モジュール = 1wasmバイナリと考えてもらえればよいかと思います。
モジュール内ではセクションという単位でデータを管理していて、各セクション関数のシグネチャ情報やメモリ情報などが配置されています。

より詳細なセクションの説明に関してはWEBASSEMBLY USUI BOOKを読むとよいと思います。

chibiwasmの実装では次の構造体を用意しています。

セクションのデコードについて少し解説します。

セクションのバイナリ表現は次のような感じとなっています。

0000010: 03  ; section code
0000011: 02  ; section size
0000012: 01  ; num functions
0000013: 00  ; function 0 signature index
...

セクション先頭の1バイトはセクションの種類を表しています。
この例では、0x03なので関数セクションですね。
次の1バイトはセクションのサイズとなっていて、これでどこまで読み取って処理すればいいのかがわかります。
今回は0x02なので2バイト読み取って処理すればよいということになります。

各セクションのフォーマットもまた異なり、それぞれに応じてデコード処理が必要になります。
chibiwasmでは次のように実装しています。

2. Runtimeの生成

wasmバイナリを表現した構造体Moduleから実行時のデータ構造を用意します。
chibiwasmの場合は、大きく分けてRuntimeとStoreを使って表現しています。

Store

StoreはModuleからメモリや関数などの実体を生成したものを保持しています。

たとえば、モジュールに次のようなメモリとデータの定義があるとします。

(module
  (memory 1)
  (data (i32.const 0) "Hello, World!\n")
)

(memory 1)は最低1ページのメモリを確保する、という意味です。
メモリはページという単位で管理し、1ページ64KBiとWasm Specで定義されています。
(data ...)はメモリのoffset(今回は0)からHello, World!\nのバイト列を配置するという意味です。

これらの定義を元に、次のように実際にメモリーの実体を作成しています。

メモリの実体はVec<u8>になっています。メモリの読み書きは基本この配列への操作となります。
Wasmはセキュアといわれている理由のひとつは、このようにRuntime内のメモリしかアクセスできないためですね。

Runtime

Runtimeは作成したStoreをとスタック、フレーム情報を持ちます。
フレームは関数呼び出しがあるたびに作成されます。詳細は後述します。
基本的に命令を処理していって、メモリや関数呼び出しが必要の場合はStoreを通してそれらを扱います。

たとえば、Wasmにはメモリのサイズを取得するmemory.sizeという命令がありますが、メモリの実態はStoreが持っているので、Storeから借用するといった感じです。

3. 関数の処理

startセクションがある場合、指定された関数を実行します。

関数は内部と外部の2種類あります。
内部は自モジュール内で定義した関数、外部は他のモジュールまたはWASIからインポートした関数です。
それぞれ処理方法が異なるので、invoke_internal()とinvoke_external()を用意しています。

`invoke_internal()`

invoke_internal()では大まかに次の処理を行っています。

スタックから関数の引数をpop
関数の命令群やpc、sp（スタックポインタ）、引数などをもつ関数フレームをcall_stackにpush
関数フレームの命令群を処理
処理終わったら、call_stackから関数フレームをpopして、スタックの巻き戻しや戻り値のpushなどを行う

フレームの構造は次のように定義しています。

instsは呼び出す関数の命令群です。

pcは呼び出す関数の命令を処理するためのプログラムカウンタです。
関数フレームごとにpcを分ける理由ですが、関数処理中に他の関数を呼び出すことがあるのでそれぞれどこまでpcを進めたかを管理する必要があるためです。

命令処理時に現在の関数フレームのpcをインクリメントして処理をしていく流れです。

spはスタックポインタで、関数呼び出し元に戻った場合、スタックを呼び出し時点の状態まで巻き戻す必要があるので、どこまで巻き戻せばいいかの情報となります。

arityは戻り値の数を示しています。関数に戻り値がある場合、その戻り値を最初にスタックからpopしてから、スタックを巻き戻し戻り値をpushするといった処理を行います。

localsは引数とローカル変数を保持しています。

labelsはラベルスタックです。ラベルはジャンプ命令で使うための情報で、次のデータを持ちます。

ラベルにはいくつか種類があって、たとえばloopはラベルで管理します。
ラベルはジャンプ先のpcを持っていて、これにより命令のジャンプができるようになります。
spはスタックの巻き戻しに使います。
startはloopのときだけ使うことがあります。loopは先頭に戻る場合とloopを抜ける場合の2つパターンがあり、それを表現するために分けています。

`invoke_external()`

外部関数の実行は少しややこしくて、外部モジュールをインポートした場合とWASIの場合があります。
それぞれ分けて説明します。

外部モジュールの関数
外部モジュール、つまりwasmバイナリをインポートした場合の処理はシンプルで、次のようにインポートしたモジュールのStoreを使って新しいRuntimeを作成して関数を実行するだけです。
外部モジュールの関数そのものはさらに別の外部モジュールの関数を再エクスポートしたものという場合もあるため、このような実装にしています。

WASI関数
WASIの場合、実体はwasmバイナリではなく普通にRustの関数を実行します。
外部モジュールとの違いはRuntimeを作成する必要がないことと、現在のStoreを使うことです。

このように、wasmバイナリじゃなければ好きに自分で関数を定義してそれを呼び出すことができるので、雑にprint()を実装してHello, Worldを出力できたりします。

今後について

ざーっと解説しましたが、多分分かりづらいと思うので、もし気になるのであればchibiwasmのコードを合わせて読み進めるとよいかもしれません。
コードは汚いので読みづらいかもですが…

なんともあれ、これで実装のベースはでき上がったので、あとは拡張してできることを増やしていきたいところです。
具体的に次のことができると楽しそうだなと思っています。

Docker/k8sとおしゃべりする
ruby.wasmを動かす

今年もRust Tokyoは開催されるらしいので、「自作Wasm Runtimeでruby.wasmを動かしてみた」という感じのタイトルでプロポーザルを出してみてるのも面白いかもしれません。

あと、以前にVim scriptでfib関数が動く程度のWasm Runtimeを書いたのですが、それを完成させるのも面白いかなと思っています。

さいごに

こういった仕様書を読み解きながら何か処理系を作るのははじめてで結構苦労しました。
むかしにWriting A Compiler In Goを写経したことがあって、なんとなく仕組みは雰囲気でわかっていたけど、やはり自分でスクラッチから書くと解像度が段違いですね。

個人的に関数呼出し周りの実装が一番おもしろかったです。
スタックはこんな感じで管理すればいいんだなや、フレームはこういうときに必要なんだと腑に落ちました。

バージョン1ではありますが、Wasm Runtimeを実装しきったことで大きな成長をしたと実感しています。
いつか「おれが考えた最強のぷろぐらみんぐ言語」を作るための基礎を少し身につけられたんじゃないかなと思っています。

言語処理系を作ってみたい方は、ぜひ一度書いてみてはいかがでしょうか？

謝辞

いろんな方が実装したWasm Runtimeを参考にさせていただきました。
ありがとうございました。

Runtime

記事/資料