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をリンクする必要があるのですが、スマートな方法が見つからずテキスト表現のまま無理やりリンクしています。lldを使えばいいのではないか?という情報を頂いたのですが、WebAssemblyのテキスト表現をELF形式に変換する方法がわかりませんでした。
  • WebAssemblyの直書きは辛い...バグると何も言わずに止まっちゃうし。
  • 公式の人は早くGCを組み込んで欲しい。やっぱりスタックを自由に走査できない環境でGCを書くのは無理がある。

  1. 現在のスタックの長さを記録しておけばリニアメモリにスタックの中身をすべて書き出すことはできる。ただしstore/load命令が整数と浮動小数点数で異なるので、スタックに積まれている全ての値について整数なのか浮動小数点数なのかという情報も保存しておく必要がある。

  2. 注1のようにスタックの中身をリニアメモリに書き出せれば、ルートセットが必要な方式も採用できる。