WebAssemblyで自作言語用のGCを書く
前回の続きです。
概要
前回の記事ではWebAssemblyを出力するMLのサブセットコンパイラを作りました。しかし、WebAssemblyにはGabage Collection (GC) が未だに実装されていないため(2019/7/8時点)、メモリ管理は全て自分で行う必要があります。前回は超適当mallocで間に合わせていたのですが、今回はmalloc, freeを含むGCをWebAssembly(手書き)で作りました。
GCを含むMLコンパイラのソースコードはここで、GC本体はここです。
WebAssemblyの基礎知識
WebAssemblyはスタックマシンで実行される言語であり、各命令は引数をスタックのトップから取り出し結果をスタックのトップに積みます。トップ以外のスタックの中身を自由に見ることはできません1。また、スタックの他にもリニアメモリも持ち、i32.store
, i32.load
といった命令でアクセスすることができます。リニアメモリは以下のような特徴を持ちます。
- アドレスは0から始まる
- アドレスは32bit
- 整数又は浮動小数点数をstore/loadできる
GCの実装
GCを書く前にまずmallocとfreeが必要です。今回はfree listでブロックを管理する簡単なものを書きました。各ブロックは下図のような構造になっていて、次のブロックのアドレス、ブロックサイズ、フラグ、確保したメモリを保持します。フラグにはfree listの終端かどうかの情報とブロックが使用中かどうかの情報が入っています。それぞれ4byteずつ使うのでmallocのためのヘッダだけで12byteも使います。贅沢ですね。
+-------------------------------------------------------+ | next block address | block size | flags | contents | | 4bytes | 4bytes | 4bytes | 4*n bytes | +-------------------------------------------------------+
mallocはfree listを先頭から走査して要求されたサイズ以上の空きブロックがあれば確保、最後まで走査して該当するブロックがなければ末尾に新たにブロックを作ります。freeは指定されたブロックの状態を空きブロックに変えるだけです。空きブロック同士を結合する処理はめんどくさいのでやっていません。
このmallocとfreeを使ってGCを作ります。『ガベージコレクション』によれば、GCには次の3種類があります。
- マーク・アンド・スイープ
- コピーGC
- 参照カウント
このうち、マーク・アンド・スイープとコピーGCは生きているオブジェクトを探索するのにルートセットが必要です。ルートセットは一般にレジスタ、スタック、グローバル変数から構成されます。ところが、WebAssemblyではスタックの中身を自由に見ることができないためルートセットが必要なGCは採用できません2。このため今回は参照カウント方式でGCを実装しました。
gc_malloc
を呼び出すとmalloc
が指定されたサイズ+GCのヘッダサイズ分のメモリをリニアメモリ上に確保し、GCの管理情報を書き込んだ上でそのアドレスを返します。GCの管理領域は下図のようになっていて、確保したメモリのサイズ、参照カウントの値、フラグ、オブジェクトのためのメモリ領域から構成されています。フラグには参照カウント時に行う深さ優先探索用のビットと格納しているオブジェクトが値(整数値又は浮動小数点数)か否かの情報が含まれます。
+----------------------------------------------------+ | memory size | reference count | flags | contents | | 4bytes | 4bytes | 4bytes | 4*n bytes | +----------------------------------------------------+
これがmallocのcontentsの中に入っているので実際にはこのようになります。
+---------------+------------+--------+--------------------------------------------------------+ | next malloc | malloc | malloc | malloc contents | | block address | block size | flags | +----------------------------------------------------+ | | 4bytes | 4bytes | 4bytes | | memory size | reference count | flags | contents | | | | | | | 4bytes | 4bytes | 4bytes | 4*n bytes | | | | | | +----------------------------------------------------+ | +---------------+------------+--------+--------------------------------------------------------+
参照カウントはコンパイラが変数のスコープに応じてオブジェクトの参照カウントを増減させるコード(gc_increase_rc
, gc_decrease_rc
)を挿入することで操作します。基本的にオブジェクトの作成時に参照カウントが1増加し、そのオブジェクトを指す変数のスコープが終了したところで参照カウントが1減らします。参照カウントが0になるとそのオブジェクトは解放され、またそのオブジェクトが保持していたアドレスが指すオブジェクトの参照カウントを1減らします。この操作は再帰的に行われます。ただし、解放されたオブジェクトが値だった場合はこの再帰的な操作は行われません。
↓gc_increase_rc
, gc_decrease_rc
はこんな感じで挿入される
(i32.const 1) (i32.store))) (; let fun_fib_0 end ;) (call $gc_increase_rc) (get_local $val_b_6) (call $gc_decrease_rc) (drop) (get_local $val_a_5) (call $gc_decrease_rc) (drop)
基本的に参照カウントの操作は変数のスコープと連動させればよいのですが、関数終了時には特殊な処理が必要になります。関数内のローカル変数が指すオブジェクトは関数の終端で解放されますが、関数の戻り値が開放されるオブジェクトを含む場合、すでに解放されたオブジェクトが関数の戻り値に含まれることになります。このようなバグを防ぐためには、関数内のローカル変数を開放する処理を行う前に戻り値オブジェクトの参照カウントをインクリメントしておく必要があります。
その他にも配列の要素を書き換えるときは前のオブジェクトの参照カウントを減らしてから、新しく代入するオブジェクトの参照カウントをインクリメントする必要があるなど、細かいところでいろいろハマりました。
結果
フィボナッチ数列を第10項まで計算するプログラムでプログラム終了時のメモリ使用量をGC有りの場合と無しの場合で結果を比較してみると、以下のようになりました。使用メモリの4分の3ぐらいを解放できているのでそれなりに(僕が)満足できる結果です。
- | メモリ使用量 |
---|---|
GCなし | 22868byte |
GCあり | 4660byte |
let rec fib n = if n < 3 then 1 else let a = fib (n - 1) in let b = fib (n - 2) in a + b in let rec print x = if 10 < x then 1 else let a = fib x in print_i32 a; print (x+1) in print 0
参考リンク
- WebAssemblyでGCを実装する
GCの管理領域の設計はほとんどこの記事のものをそのまま使っています。 - WebAssemblyでGC
bitmap式のMark and SweepのGCを書く話。