WebAssemblyリンカのGC

GCの基本

  • GC = garbege collection (プログラミング言語のランタイムのGCとは異なる)
  • リンカに渡されたすべてのコード(データ)を愚直にすべて出力すると、サイズが大きくなりすぎてしまう。
  • 出力ファイルは使われるコード(データ)のみを含むようにしたい。
  • 入力ファイルのセクションを最小単位として、サイズを最適化する

(Wasmの場合、ディスアセンブルせずにCodeセクションをそれぞれの関数本体を分割できるため、関数単位でGCが行われるのかと誤解していた...)

アルゴリズム

mark and sweep GCのmarkと同じ原理で使われるセクションを再帰的にマークする。つまり、明らかに使われるシンボルから初めて、関数呼び出しやグローバル変数のアクセスによって辿りつけるセクションをマークしていく。リロケータブルなオブジェクトファイルは関数呼び出しやグローバル変数へのアクセスに対して、リロケーションを持つ。

int ret = 42;

int main() {
    return ret;
}

例えば、上記のコードを-cをつけてコンパイルすると、以下のようなリロケーションが生成される。(__stack_pointerはリンカが生成する特別なシンボル)

  - relocations for section: 4 (Code) [3]
   - R_WASM_GLOBAL_INDEX_LEB offset=0x000006(file=0x00008c) symbol=1 <env.__stack_pointer>
   - R_WASM_MEMORY_ADDR_LEB offset=0x00002b(file=0x0000b1) symbol=2 <ret>
   - R_WASM_FUNCTION_INDEX_LEB offset=0x00003b(file=0x0000c1) symbol=0 <__main_void>

wasmの場合はこの最初のセクションはエントリーポイント、no-stripなシンボル、init functionが所属するセクションとretained segmentsが該当する。(init functionsはグローバル変数のコンストラクタであることを示す関数のフラグである。)

github.com

擬似コードは以下のようになる。

set visited;
stack work_list;
for each section
  if section is a GC root {
    work_list.push_back(section);
    visited.insert(section);
  }
while (work_list.size()) {
  section sec = work_list.back();
  work_list.pop_back();
  for each section referenced by sec
    if (visited.insert(section))
      work_list.push_back(section);
}

from https://maskray.me/blog/2021-02-28-linker-garbage-collection

参考