借り初めのひみつきち

仮ブログです。

Rust 自作 OS 日記/Part 7 次世代の OS へ。

rust WebAssembly moe megos

myos の開発をはじめておよそ半年が経ちました。

前回の続き

前回の日記より実装も進歩してはりぼて OS でできることの８〜９割程度が myos でもできるようになりましたが、まだいくつか課題があります。

そもそも myos ははりぼて OS ベースではないし、はりぼて OS の再実装を目標としていたわけでもありません。 根本的な構造の違いによる非互換性もあります。元のカーネルのポリシーを曲げてまでそれ以上の互換性に拘る必要があるでしょうか？

64bit マルチコア対応のカーネルでスレッド非対応の 32bit アプリしか動かない現状はカーネルの無駄使いです。 いったんこの辺で完了として次のステップへ進む時がきました。

次世代のバイナリ形式

次世代のバイナリ形式といえば WebAssembly です。

f:id:neriring16:20201127115209p:plain

WebAssembly は紆余曲折を経て作られた次世代の新しい共通実行形式です。 名前で想像がつくように元々は Web で使うために生まれたバイナリ形式ですが、将来性を見出した人たちによっていろんな分野で使われはじめています。 WebAssembly には未来があります。

WebAssembly は S 式で記述されたアセンブリソーステキスト形式の .wat とバイナリ形式の .wasm があり、ツールを使えば相互に変換可能です。 我々が使うのはもちろんバイナリ形式の方です。

WebAssembly のランタイムはすでに色々な人が作っているので myos に簡単に組み込めるものもあるかもしれません。 が、自作します。

WebAssembly の読み方

wasm ファイルを読み込むには LEB128 というエンコードを理解する必要があります。 これは小さい数値は1バイト、大きな数値はより多くのバイト数を割り当てた可変長のバイト列にしてファイルサイズを節約するためのエンコードです。

LEB128 の場合は名前の通りリトルエンディアンで、1バイトの8ビットのうち下位7ビットを実際のデータ、最上位ビットを後続バイトのフラグに使います。 つまり、 0x00-0x7F までなら１バイト(7bit)のデータ、 0x80-0xFF なら後続のバイトが続き、最上位ビットが０になるまで繰り返します。 各バイトは7ビットずつシフトしていくのでちょっと中途半端なデータになるしエンコードやデコード処理が面倒ですが、一般に数値データの情報量は12bit程度(正確な数値忘れました)と言われており、32bitや64bitの数値を小さいサイズで表現できる事が多いです。

また、 LEB128 の亜種で Signed LEB128 というものもあり、バイト列から実際の値に変換する処理は同じですが、データ結果の最上位ビットが 1 だった場合は空いてる残りの上位ビットを全部 1 にして負の数値として扱います。Signed LEB128 では 0x7F が -1 となります。

wasm ファイルはこの LEB128 エンコードをほとんどの項目で採用しているため、 LEB128 のストリームのような感じになっています。 実際には階層構造となっているのでファイルの先頭から最後まで全ての LEB128 データが直接繋がっているわけではないですが。

wasm ファイルの構造は固定の識別子(Magic)とバージョン番号のあとに１２種類のセクションが並んでいます。 Custom 以外のセクションは並び順が決まっていて順番が守られていないと不正なデータになります。 そのため WAT のソースとは違う順番で並んでいる事があります。 これは先頭の方のセクションで定義したデータを後ろのセクションから参照する必要があるためです。 type セクションなどはソースで定義しなくても func で定義した内容が自動的に追加されます。

各セクションの構造は 1 バイトのセクション識別子と LEB128 エンコードされたセクションのサイズがあり、その後に実際の内容が続きます。 ほとんどのセクションはベクタ構造のため、最初の値は LEB128 エンコードされた項目数となっているセクションが多いです。

WebAssembly ではファイルやセクションの終わりは定義されておらず、ファイル先頭から順番にセクションを読み込んでファイルが終わったらそこで終了になります。データが壊れているときの挙動がちょっと怖いですね。

  • 0: custom セクション

WebAssembly の仕様書で定義されていないカスタムメタデータを格納するのに使います。 カスタムセクションはセクションの先頭に識別用の名前があります。

  • 1: type セクション

関数のシグネチャ（引数と戻り値の型の組み合わせ）を定義します。 将来他の使い道も想定しているようです。

  • 2: import セクション

外部（主に JavaScript）からインポートする項目を定義します。 モジュール名と実際の項目名を指定するため、モジュール名がネームスペースのような役割を果たしています。 なお、ここで定義された関数とバイナリ内部にある関数は連番となるので import 関数の分だけ定義と参照の番号がずれます。

  • 3: func セクション

このバイナリに含まれている関数を定義します。 実際にこのセクションにある情報は type のインデックスだけなので n 番目の関数の型が T であるということしかわかりません。 実際の関数の情報はこれより前の type や import セクションの内容に依存し、名前は export セクション、コードは code セクションにそれぞれ分かれています。

  • 4: table セクション

table は関数の識別子が入った配列で、このセクションでは table の大きさを決めます。 WebAssembly ではセキュリティのために間接呼び出しの call_indirect 命令で指定できるのは table のインデックスだけとなります。 将来的には複数の table が使えるような拡張を予定しているようですが、現状は 0〜1 個しかありません。

  • 5: memory セクション

memory というデータ構造を定義します。このセクションでは memory の大きさを決めます。 将来的には複数の memory が使えるような拡張を予定しているようですが、現状は 1 個しかありません。*1

memory というのは WebAssembly のデータ領域で、 export されていれば JavaScript からは ArrayBuffer とほぼ同じようにアクセスできます。 WebAssembly の memory は 64KB 単位を１ページとするので (memory 1) と指定すると 64KB のメモリーを割り当てる意味になり、小規模なアプリは大体この指定になります。ちょっと大雑把ですね。

  • 6: global セクション

グローバル変数を定義できます。あんまり使い道ない気がします。

  • 7: export セクション

外部にエクスポートする項目を定義します。 func、table、 memory、global にそれぞれ名前をつけて外部に公開することができます。 実際に JavaScript から WebAssembly を呼び出す場合ここのセクションを使います。

  • 8: start セクション

エントリポイントとなる function のインデックスを指定します。 エントリポイントは存在しない事も多いです。

  • 9: elem セクション

先述の table の内容をあらかじめ定義するセクションです。 table の x 番目には function の y 番目という感じでデータを定義します。

  • 10: code セクション

プログラムコードを定義します。 code セクションはさらに関数ごとに分かれて、それぞれの関数のローカル変数の定義と WebAssembly のバイトコード列があります。 WebAssembly バイトコードはオペコードのバイト値と必要に応じて LEB128 エンコードされたパラメータが繋がっているので、先頭から順番にちゃんとパースしていかないと命令の切れ目がよくわからなくなります。

  • 11: data セクション

データ領域の内容を定義します。 このセクションで定義した内容は起動前に memory の特定の領域に書き込まれます。 不思議なことに書き込む memory のオフセットはバイトコードの式で記述し、通常は { i32.const XXXX; end } のようなコード列になります。*2 メリットがよくわからないし複雑なバイトコードを書き込んだらどう解釈されるんでしょうか・・・

これらのセクションを順番に読み込んでメモリ上に構造体を作ればロード処理は完了です。 800行くらいかかりました。

ロードが終わったらバイトコードを実行します。

実例

例としてこのような WAT のソースをアセンブルしてみます。 内容は２つの引数を足し算した結果を返すだけのよくあるサンプルです。

(module
  (func $add (export "add") (param $a i32) (param $b i32) (result i32)
    local.get $a
    local.get $b
    i32.add
  )
)

すると以下のようなバイナリになります。

00 61 73 6D 01 00 00 00 01 07 01 60 02 7F 7F 01
7F 03 02 01 00 07 07 01 03 61 64 64 00 00 0A 09
01 07 00 20 00 20 01 6A 0B

これを分解してみます。

まず先頭の 00 61 73 6D はマジックナンバー、次の 01 00 00 00 はリトルエンディアンで 0x00000001 となり、バージョン 1 を表します。 ここまでの 8 バイトはすべての wasm ファイルで共通の固定値です。

続く 01 07 01 60 02 7F 7F 01 7F は 01 がセクション 1 (type) 07 がサイズ(7) を表します。 次の 01 はこのセクション全体の要素数(1)、 60 は関数タイプを表す固定値、 02 7F 7F は要素数 2 のベクタ [0x7f, 0x7F] で 0x7F は i32 を表しているので引数の型は (i32 i32) となり、次の 01 7F は戻り値の要素数(1) と型(0x7F = i32) を表し、 ここまでを逆アセンブルすると (type $0 (func (param i32) (param i32) (result i32))) となります。 この type セクションは func などから自動生成されるので元のソースには記述されていません。

続く 03 02 01 00 は 03 がセクション 3 (func) 02 がサイズ (2) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 00 が内容 (type 0)を表します。 ここまで逆アセンブルすると (func $0 (type $0) (param i32) (param i32) (result i32)) と等価になりますが、このままではコードブロックが定義されていません。

続く 07 07 01 03 61 64 64 00 00 は 07 がセクション 7 (export)、次の 07 がサイズ (7) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 03 61 64 64 が関数名 (add) 、次の 00 はこの export が関数であることを表し、最後の 00 は関数のインデックス (0) を表します。 これを逆アセンブルすると (export "add" (func $0)) となります。元のソースでは func の中に隠れています。

最後の 0A 09 01 07 00 20 00 20 01 6A 0B は 0A がセクション 10 (code) 09 がサイズ(9) を表します。 次の 01 はこのセクション全体の要素数(1)、次の 07 は関数のサイズ(7)、次の 00 はローカル変数の要素数 (0)、残りの 20 00 20 01 6A 0B はコードで、これをさらに分解すると 20 00が get.local 0 20 01が get.local 1 6A が i32.add 0B が end となります。これを先ほどの func セクションと統合して逆アセンブルすると

 (func $0 (type $0) (param $0 i32) (param $1 i32) (result i32)
  local.get $0
  local.get $1
  i32.add
)

となります。

今までのセクションを統合して最後にルート要素として (module ) で囲むと

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

となり、これが完全な逆アセンブル結果になります。

スタックマシンと逆ポーランド記法

WebAssembly はスタックマシンのバイトコードを採用しています。 スタックマシンはデータをロードする時にスタックに push され、ストアはスタックから pop した値をストアし、演算命令は決まった数だけデータを pop してから結果を push します。 CPU の物理的なレジスタ構成に依存しないコードになるので中間言語としてよく使われる手法です。

また、スタックマシンのバイトコードは逆ポーランド記法の計算式とほぼ対応しています。 1 + 2 というよく知っている式を逆ポーランド記法にすると 1 2 + という式になり、これを WebAssembly のソースコードで記述すると

i32.const 1
i32.const 2
i32.add

となり、逆ポーランド記法の要素とバイトコードが 1:1 で対応しているのがわかるかと思います。

これらの操作を愚直に実装するとものすごい量の push と pop の繰り返しになるためとても遅くなりますが、簡単に実装できるので当面はこのまま実装します。 ロードストア系の命令と演算命令はスタックマシンを理解すれば比較的簡単に実装できます。

WebAssembly にポインタは存在しない

この辺りは JavaScript で WebAssembly を扱ったことがある人ならよく知っているかもしれません。

WebAssembly のデータ型は基本的に数値のみ (i32, i64, f32, f64) でオブジェクト参照もポインタもありません。 数値より複雑なデータ型はどうやって扱えばいいのでしょうか・・・？

ここで memory が登場します。

memory は JavaScript からは ArrayBuffer とほぼ同等のインターフェースを持った WebAssembly.Memory という型のオブジェクトで扱います。 WebAssembly のコードからはこの配列をメモリとみなしてデータの読み書きを行います。 メモリアクセスは i32 の数値を memory の配列のインデックス兼ポインターとして扱います。 ポインタというデータ型があるわけではなくメモリアクセス命令の方で意味を持たせるので低レベルの機械語に近いイメージです。

memory の範囲を超えるメモリアクセスは例外になりますが null ポインタは特に特別扱いされていません。 0 番地にデータを置くことも一応可能ですが、 null ポインタとの区別がつかなくなるので使わない方がいいです。

なお、現行バージョンでは memory は１つしか存在しませんが将来は複数に拡張する予定があるようです。 80286 の再来ですね。

ブロックと制御命令

WebAssembly では自由なアドレスに分岐できる命令が存在しません。

バイトコードは階層構造のブロックになっていて、分岐命令はブロックのネストに対する分岐として動作します。 しかし、ブロックの種類によってブロックを抜ける分岐とブロックの先頭に戻る分岐のどちらの動作になるか固定で指定できないため、ループの構造によっては複数のブロックが複雑に重なり合ったバイトコードになります。 いわゆる switch 文などを使った分岐先が多い関数の場合もものすごい量のブロックがネストしています。

ブロックに関わる命令として block, loop, if, else, end があります。

block 命令は分岐ラベルの付いたただのブロックです。 block に対する分岐は C 言語の break のようにブロックを抜ける動作をします。

loop 命令は繰り返し実行するブロックです。 loop に対する分岐は C 言語の continue のようにブロックの先頭に戻る動作をします。

if 命令は条件分岐のためのブロック、 else 命令は if とセットで使うブロックでペアになる if が実行されなかった時に代わりに実行されます。 if 〜 else ブロックは

比較命令
if
  expr1
  ..
else
  expr2
  ..
end

のような構造になり、通常は比較命令とセットで使います。

end はブロックの終端を表す命令です。ブロック命令のないトップレベルで end 命令があった場合は関数ブロックの終端を意味します。 つまりブロックのネストはバイトコード上では

block
    expr
end

のような構造になります。

なお、 else ブロックが続く if ブロックは else 命令が end 命令を兼ねているので、この場合 if ブロックには end 命令がありません。

ブロックには戻り値の型を指定することができ、ブロックを終了するときはスタックトップの値を戻り値として利用します。 繰り返しループされるブロックに戻り値を指定した場合の動きは仕様書を読んでもよくわかりませんでした。 for ループのような機能を実現するためにループ先頭で使うんでしょうか？

br 命令は分岐命令です。分岐対象は先述のようにブロックとなります。 対象ブロックの種類によって前方分岐か後方分岐か動作が変化します。 現在のネストを基準にしているので br 0 は現在いる最深ブロックを対象に分岐します。 また、分岐元と分岐先のスタックレベルが違う場合は巻き戻し処理が行われます。

br_if は条件分岐命令です。通常は比較命令とセットで比較命令の結果をスタックトップから取り出し、条件が成立した場合のみ分岐を実行します。

br_table 命令は C の switch 文で使います。スタックトップの値を取り出して命令の直後に続いているテーブルから表引きで分岐します。分岐表のためにとても長いバイトコードになります。

このように WebAssembly の制御命令は結構複雑な動作をするものが多いです。

関数呼び出しと引数とローカル変数

関数を呼び出すときは type セクションで定義した型の引数を push するとそれがパラメータとして渡ります。 一般的な C 言語の ABI と異なり、一番最初に push された値が一番左のパラメータ、一番最後に push された値が一番右のパラメータになります。 関数の中では一番左のパラメータは一番若い番号 (0) のローカル変数としてアクセスできます。

関数実行時にパラメータとローカル変数はまとめてひとつの配列のようなものに入れてローカル変数として渡されます。 引数以外のローカル変数は code セクションの関数本体の最初の方に定義されており、関数実行時には 0 で初期化されます。

call 命令は import セクションまたは func セクションで定義された関数の番号を指定して呼び出します。 両者は連番になっており、 import された関数の方が若い番号になります。

call_indirect 命令は table のインデックスを指定して関数を呼び出します。 table の内容は JavaScript からも操作することができますが WebAssembly のバイトコードから table の内容に直接アクセスする方法はありません。

return 命令は関数を終了して呼び出し元に戻るショートカット命令です。 関数のトップレベルにある end 命令でも関数を終了します。

標準 API の問題

WebAssembly には標準の API が存在しません。

WebAssembly 単体では数値演算か、 memory の中のバイト列を変更するくらいしかできません。

JavaScript から呼び出す場合は呼び出す JavaScript に完全に依存した構造となります。

ブラウザ外の実行環境では WASI という規格の標準化が進められている最中ですが、まだ正式版がリリースされておらず、 個人的には WASI はあまりいけてないかなと思っています。

その他の API の選択肢となるとあまり候補がありません。 WebAssembly は import/export を使って拡張が容易ですし、せっかく自作 OS を作っているので独自 API を考えていくのもいいかなと思います。

Minimum Viable Product

WebAssembly には MVP (Minimum Viable Product) と呼ばれる目標があり、現在は主要なブラウザで WebAssembly MVP がサポートされています。

すでにいくつか触れた通り、将来拡張予定の機能が MVP 実装では一部制限されています。 最初から目標を高くしすぎると実装が困難で時間もかかるので、最小限の機能をとりあえずまとめてリリースという感じでしょうか？

しかし、 WebAssembly MVP をフルスクラッチで実装しようと思うと意外と高い目標であることがわかります。

現状の myos ではここまで紹介した機能のすべてを実装することがまだできていません。 また、そもそも現状の myos でサポートできない機能もあるので myos における WemAssembly MVP の実装完了はまだまだ先になりそうです。

*1:理論上は 0 個も可能ですが、メモリを使わないプログラムはほぼあり得ないので

*2:ちなみに elem セクションなどにも同様の仕様があります