LLVMのGC(ガベージコレクション)サポートを使ってみる - Aizu Advent Calendar 2013(1日目)

Aizu Advent Calendar 2013、今年もやっていきます！宜しくお願いします。
一日目の @yutopp です。

今回は、日本語の資料が乏しいような気がする、LLVMのガベージコレクションサポートについてサラっと調べてみました。
ドキュメントは Accurate Garbage Collection with LLVM — LLVM 3.4 documentation になります。

実験には、Linux Mint 15(64bit)、Clang 3.4 svn(194075)、LLVM 3.4 svn(194075) を用いています。

ちなみに今回ガベージコレクション自体は実装していません。~~申し訳 of the world~~

ガ・ベ・コ・レ、始まります

まずガベージコレクションについて。Wikipediaの記事を読むと良いです。
ガベージコレクション - Wikipedia

プログラムによって確保されたメモリ領域は、しっかり解放を行わないと闇に飲まれるので良くないのですが、頻繁にメモリ領域を確保するプログラムを書くと、それらをしっかり解放させるのは大変だったりします。
そこでガベージコレクションが登場します。ガベージコレクションはこの解放処理を自動で行なってくれるので、あるとそこそこ楽なわけです。

ガベージコレクションのアルゴリズムは色々な種類がありますが、大方ルートを辿るような動作をします。
ルートとは、メモリ領域を指し示す一番根本の部分のことを指します。大体複数存在します。
そして、このルートを辿っていくと、プログラム中で使われているメモリ領域が分かります。

例えば、C++で、ルートはスタックとレジスタとします。メモリ領域を指し示すポインタの値は、スタックやレジスタに配置されます。しかし、スタックなどにはポインタ以外の値(整数値)も配置されるため、ガベージコレクションを行う際に正しくポインタだけの値をたどる事ができません。

そこで、ポインタの値かどうか怪しいときは、その領域に触れない、または、その怪しい値もポインタの値とみなして生存判定をすることがあります。
このような振る舞いのガベージコレクションを”保守的なガベージコレクション”といいます。
そんな振る舞いのおかげで、プログラムは安全な方向に倒れます。(怪しいポインタや指すメモリ領域が勝手にいじられないため)
このガベージコレクションは、言語や処理系のサポートを必要としないのが利点で、実装もしやすいのですが、メモリリークなどが発生する場合あります。

一方で、ルート上の値がポインタかその他の値かを厳密に判別するガベージコレクションを”正確なガベージコレクション”といいます。
この厳密に判別のためには、言語処理系のサポートが欠かせないため、実装がややこしくなります。
また、処理系による実行時のサポートのため動作が遅くなることもあります。
しかし、全ての領域を正確に回収することができるので、まあこっちを使いたいですよね。

保守的なガベージコレクションであれば、LLVMなどのサポートは必要なく実装できる…。でもやっぱり正確なガベージコレクションを実装したい！
そこで、LLVMは、この正確なガベージコレクションを実装するためのサポートを提供してくれています。ヤッター！

正確なガベージコレクションのためのサポート

もう一度言いますが、ガベージコレクション自体は実装していません。つらい！
とりあえず、ガベージコレクションのサポートのテストをリポジトリに置いてみました。
yutopp/llvm-gc-support-test · GitHub

LLVMは、正確なガベージコレクションに必要なルート上のオブジェクトを判別するために、以下の方法を提供しています。

組み込みのShadowStack実装
独自のコード生成pluginの読み込み

ShadowStackは、汎用なスタック上の情報を記録するための手法だそうです。ポータブルな実装な分、オーバーヘッドが結構大きいとか書いてありましたが、見た感じそんなことなさそう…
このShadowStackは、LLVMの組み込みとあってデフォルトで利用できるため、手始めにはとても助かります。
ShadowStackのオーバーヘッドが気になるなど、別の手法の実装を使いたい場合は、自身でLLVMのGCサポート用のクラスをC++で実装し、LLVMに読み込ませることで拡張が可能です。

今回はShadowStackのみを利用してみます。

サンプルの説明

それぞれのディレクトリにコードが置いてあり、そのディレクトリで ./build をすれば、実行形式 a.out が生成されます。ｱ…windowsの方は自力でなんとかして下さい…

shadow_stack以下のファイルの説明です。

entry.cpp
- main関数を定義してあります。この関数から、個々のサンプルのf()が呼び出されます。

llvm_shadow_stack.cpp
- LLVMのドキュメントを参考にしたShadowStack用の定義です。

oreore_runtime.cpp
- 俺々ランタイムです。なんちゃってメモリアロケータと、GCルートのクローラと、ちょっとした関数が込めてあります。

それぞれのtest_functionの先頭には、C++で書いたらこうなるかなーというコードが書かれています。

simple_function_call/test_function.ll
- gc領域の関数呼び出しテスト

simple_nested_function_call/test_function.ll
- ネストされたgc領域の関数呼び出しテスト

simple_nested_with_no_gc_function_call/test_function.ll
- 途中に普通の領域の関数を挟んだ、ネストされたgc領域の関数呼び出しテスト

with_metadata/test_function.ll
- ShadowStackを調べるのに使った残りファイル

それぞれの *_function_call では、ループをひたすら回す処理が書いてあり、その中で毎回int型のメモリを確保するmy_allocを呼んでいます。
そして、俺々ランタイムのなんちゃってメモリアロケータは、10個しかメモリ領域を管理できない出来損ないです。
なので、メモリを10回確保して開放しないでいると、11回目のメモリ確保でガベージコレクションがトリガされるようになっています。
実際に実行してみると、(多分)そのような挙動をしていることがわかります。

ガベージコレクションサポートを受けるには

まず関数に gc "name" の指定をつけます。"name" の部分は使用するプラグインの名前になります。"shadow-stack" はデフォルトで使うことができます。
次に、GC管理下に置くポインタをおく領域を alloca にて作成し、@llvm.gcroot でマークを行います。
LLVMはmem2regの最適化によって、alloca で確保した領域もSSA形式に変換してしまう可能性があるので、マークを行う必要があります。
また、全ての @llvm.gcroot の呼び出しは、最初のBasicBlockで行われる必要があるようです。
@llvm.gcroot の第1引数は必ずalloca命令かallocaのbitcastを参照する値でなければなりません。
第2引数には、ポインタに関連付けられたメタデータへのポインタが入りますが、このポインタは*必ず*定数もしくはglobalな値のアドレスである必要があります。利用しない場合はnullを渡せば良いようです。

リードバリアと、ライトバリアは、@llvm.gcread と @llvm.gcwrite 組み込み命令で実現できます。

あとは、アロケータがガベージコレクションのトリガを引いた際に、ルートを巡ってガベージコレクションを行うなりなんなりするだけです。多分！

LLVM Language Reference Manual — LLVM 3.4 documentation
Accurate Garbage Collection with LLVM — LLVM 3.4 documentation

ShadowStackについて

自分がShadowStackについてよく分かっていなかったので、LLVMではどのように実装されているか見てみました。
組み込みのShadowStackを生成するプラグインのコードは LLVM: ShadowStackGC.cpp Source File にありました。
また、ここで出てくる型や変数の定義は Accurate Garbage Collection with LLVM — LLVM 3.4 documentation となります。

以下は、with_metadata/test_function.ll を -filetype=asm で llc に食わせた結果のアセンブリにコメントを加えたものです。

	.file	"test_function.ll"
	.text
	.globl	f
	.align	16, 0x90
	.type	f,@function
f:                                      # @f
	.cfi_startproc
# BB#0:                                 # %entry
# !!!!!!!!!!!!!!!!!!!!!!!!
# !!!! -> [1]
# !!!!!!!!!!!!!!!!!!!!!!!!
	mov	rax, qword ptr [rip + llvm_gc_root_chain]
	mov	qword ptr [rsp - 24], __gc_f
	mov	qword ptr [rsp - 16], 0
	mov	qword ptr [rsp - 32], rax
	lea	rax, qword ptr [rsp - 32]
	mov	qword ptr [rip + llvm_gc_root_chain], rax
	mov	qword ptr [rsp - 8], 0
# !!!!!!!!!!!!!!!!!!!!!!!!
# !!!! -> [2]
# !!!!!!!!!!!!!!!!!!!!!!!!
	mov	rax, qword ptr [rsp - 32]
	mov	qword ptr [rip + llvm_gc_root_chain], rax
	ret
.Ltmp0:
	.size	f, .Ltmp0-f
	.cfi_endproc

	.type	.Lstr.1,@object         # @str.1
	.section	.rodata.str1.16,"aMS",@progbits,1
	.align	16
.Lstr.1:
	.asciz	"How is your progress?"
	.size	.Lstr.1, 22

	.type	.Lstr.2,@object         # @str.2
	.section	.rodata.str1.1,"aMS",@progbits,1
.Lstr.2:
	.asciz	"Doudesuka?"
	.size	.Lstr.2, 11

	.type	llvm_gc_root_chain,@object # @llvm_gc_root_chain
	.section	.bss.llvm_gc_root_chain,"aGw",@nobits,llvm_gc_root_chain,comdat
	.weak	llvm_gc_root_chain
	.align	8
llvm_gc_root_chain:
	.quad	0
	.size	llvm_gc_root_chain, 8

	.type	__gc_f,@object          # @__gc_f
	.section	.rodata,"a",@progbits
	.align	16
# !!!!!!!!!!!!!!!!!!!!!!!!
# !!!! -> [3]
# !!!!!!!!!!!!!!!!!!!!!!!!
__gc_f:
	.long	2                       # 0x2
	.long	2                       # 0x2
	.quad	.Lstr.1
	.quad	.Lstr.2
	.size	__gc_f, 24


	.section	".note.GNU-stack","",@progbits

ビックリマークで囲んであるところが重要なところです。
[1] は、新しいStackEntryを生成し、新しいStackEntryへllvm_gc_root_chainのリストをつなぎ替える部分です。
この時点で、llvm_gc_root_chainに新しいスタックフレームのStackEntryへのアドレスが代入され、この新しいスタックフレームのStackEntryに古いllvm_gc_root_chainの値がコピーされます。
ここを抜けると、スタックの状態はこのようになっています。
f:id:yutopp:20131129145240p:plain
また、metadataをもつRootsが、配列の先頭に配置されるようになっているようです。

[2] は、llvm_gc_root_chainのリストを、このスタックフレームに入る前のものにつなぎ直す処理です。

[3] は、FrameMapという構造で、GCのセクションの分だけ生成されるようです。
f:id:yutopp:20131129145251p:plain

llvm_gc_root_chainは、このStackEntryをつなぐ単方向リストの先頭です。
よって、

for( StackEntry* entry=llvm_gc_root_chain; entry!=nullptr; entry=entry->Next ) {
    unsigned i = 0;

    // For roots [0, NumMeta), the metadata pointer is in the FrameMap.
    for( ;i < entry->Map->NumMeta; ++i ) {
        // entry->Roots[i] と entry->Map->Meta[i] で 各ルートとメタデータにアクセスできる
    }

    // For roots [NumMeta, NumRoots), the metadata pointer is null.
    for( ;i < entry->Map->NumRoots; ++i ) {
        // entry->Roots[i] で 各ルートにアクセスできる。メタデータは無し
    }
}

というコードで、スタック上のルートを巡ることができるようになりました！やりました！
でもマルチスレッド環境だと大変なことになりますねこれは…

おわりに

色々足りない感はありますが、ここで筆を置くことにします。
こう言い換えろ→論文に死んでも書いてはいけない言葉３０読書猿Classic: between / beyond readers

Boost.AsioやリンカやGCの実装についてはまた今度書きます！！！！！
さて、Aizu Advent Calendar 2013、2日目は Hiroyuki Sano さんです！宜しくおねがいします！！！！

yutopp's blog

サンドバッグになりたい