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はグローバル変数のコンストラクタであることを示す関数のフラグである。)
擬似コードは以下のようになる。
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
