Detail of the jgc garbage collector

Posted on May 17, 2013 / Tags: jhc, jgc, gc, haskell

Table of contents


AjhcのデフォルトのGCはjgcでゲソ。 このjgcについての解説は @dec9ue 氏のプレゼン資料が詳しかったでゲソ。

小二病でもGCやりたい from dec9ue

これからAjhcを使って以下を実現したいでゲソ。

とすると、jgcに対してもう少し突っ込んだ理解を今しておいた方が良さそうでゲソ。

GCのルート

gc_perform_gc関数の前半でヒープにマーキングしているはずなので、読めばわかるはずじゃなイカ。

gc_perform_gc関数が開始すると…

  1. stack一時変数を初期化
  2. arenaの中身のused_bitを一般0クリア
  3. stack_check関数を呼び出してstack一時変数がroot_stack.ptr個分のエントリを格納できるか調べ
  4. stack一時変数のサイズが足りなければstack_grow関数でreallocを呼び出し拡張
  5. root_stack.stack配列の要素を一つずつgc_add_grey関数に食わせる
  6. gc_add_grey関数はroot_stack.stack配列の要素がヒープ中かどうかチェックする。nh_stuff配列の中にある要素は静的確保されたもの
  7. さらにgc_add_grey関数はroot_stack.stack配列の要素にused_bitが立ってないことを確認してから立てる
  8. 6と7に成功したらstack->stack配列に当該root_stack.stack配列の要素を積む
  9. BSDリストであるroot_StablePtrsを順番に辿る
  10. 6と7と同様にしてgc_add_grey関数でチェックした後stack->stack配列にroot_StablePtrsの要素を積む

ということはroot_stackとroot_StablePtrsの2つがGCルートということになるでゲソ。

ところでちょっと気になるんでゲソが、 root_StablePtrsをgc_add_grey関数にかける前にstack_checkをもう一度呼び出してstack一時変数のサイズが足りてるかチェックした方がいいんじゃなイカ… このままだとStablePtrの個数が多い場合にはふっとぶ気がするでゲソ。

root_stackとは何か

これはふつーのプログラムでは使われないようでゲソ。 jhcのGrinがgc_add_root関数を使うコード吐き出すことがあるようでゲソ。

ちょっとコードの意図が取りにくいでゲソが“E_”ではじまる関数はサンクの評価関数であるはずなので、 スタティックサンクだとGCルートになるんじゃなイカ? その時に“E_”ではじまる評価関数の中にgc_add_root関数が埋め込まれるはずでゲソ。 …でもなんかそのケースは稀な気がするでゲソ。 grinの最適化の中でほとんどのスタティックサンクは使用元の関数の中に展開されてしまいそうでゲソ。 簡単な例を作ってみてもgc_add_root関数が埋め込まれたC言語コードをajhcは吐き出さないようでゲソ。 まぁここではこんなものがGCルートになる可能性があるよ、ということでいいんじゃなイカ?

root_StablePtrsとは何か

Foreign.StablePtr.newStablePtr(これはGHCのAPI) をHaskellコードから呼ぶとstruct StablePtrがstableptr.cでmalloc確保されて、 root_StablePtrsに繋がれるんでゲソ。 つまりStablePtrを保管する器ということじゃなイカ。リストより木構造の方が良い気もするでゲソ…

他にGCルートになるものは?

さすがに上の2つだけがGCルートのはずないでゲソ。根っこがスカスカじゃなイカ。 もう一つGCルートがあり、それはC言語のミューテターがコツコツ作るGCスタックでゲソ。 gc_perform_gc関数の続きを読むと…

このコードはgcからgc_stack_baseまでの領域の差す先を entry_tポインタとしてgc_add_grey関数に食わせるでゲソ。 gcとgc_stack_baseはプログラム起動時には同じ場所を指しているでゲソ。

ところがミューテターの中にgc_frame0関数というのがよくあらわれるでゲソ。

このgc_frame0関数はイカのような実装で、つまり上のミューテターはGCルートに

の4つを登録しているでゲソ。

どーせs_alloc関数を呼ばないかぎりはGCは走らないので、 GCルートに追加するタイミングはs_alloc関数の直前まではあんまり厳密にしなくても良いはずでゲソ。 また、eval関数はサンクの評価を行なう可能性があり、その中でs_alloc関数を呼び出す可能性があるので、 その直前でGCルートを最新の情報に更新しておく必要があるはずでゲソ。

ミューテターをC言語で書いていても、コンパイルパイプラインで自動生成するようにすれば、 gc_frame0関数の挿入のようなアイデアも実装漏れが起きることを気にしないで実現できるでゲソ。 いいじゃなイカ! しかもこの“gc”という参照でゲソが、スコープを抜けると元の位置を自動的に指すようになっているでゲソ。 C言語のスコープを使った上手いスタックの実現方法でゲソ。

ただしこのjgcのGCスタックはC言語のスタックに強く紐づいているため、 再入を実現するためにはGCスタックもコンテキスト分持つ必要があるでゲソ。 例えばLWP毎に一つ必要になるはずでゲソ。 さらに多重割り込みを考慮すると割り込み毎に一つ必要になるはずじゃなイカ。

ミューテターにとってのクリティカルリージョンは?

まずイカの関数は単一のHaskellヒープをさわってしまうので、なんらかの排他処理が必要になるはずでゲソ。

これらの関数はajhc/rts/rts/gc_jgc.cで閉じているので、C言語実装で比較的容易に排他処理できそうでゲソ。 またgc_frame0マクロはgcポインタを作りなおすだけなのでゲソが、 コンストラクタを呼んでスマートポインタを得てからgcポインタの位置をずらしているでゲソ。 この方式のままだとコンストラクタ+GCルート登録までを排他するか、 自コンテキストから他コンテキストとでヒープを分けるか…とにかく使えるしろものではないじゃなイカ。 さらに並列実行の時にいったいどーやって誰がgc_perform_gcすれば良いのかは今のところアイデアがないでゲソ… 完全に並列GCにする方法があるのか、はたまたジャイアントロックするにしても他のコンテキストを停止させる方法があるのか謎でゲソ…

参照はループになるか?

おそらくループなることはないでゲソ。 gc_perform_gc関数を読むかぎりでは参照ループを検出しているようには見えないでゲソ。 それなら参照カウントを使ったGCを導入することも可能なんじゃなイカ? メジャーGCが走る頻度を下げることが可能かもしれないでゲソ。

GCを中断/再開できるか

jgcではGC開始時にused_bitを全クリアしていまうため、 マーキングフェーズが完全に完了しないかぎりヒープ領域の内でどこを使って良いのか判別できないでゲソ。 無理矢理回避策を考えるとするとビットマーク領域を2倍持っておいて、 一方を空き領域検索用に、一方を漸進的なマーキング用に使うというアイデアでゲソ。 ただ、ほんとうにこの実装で上手くいくかはやってみないとわからないところでゲソ…

blog comments powered by Disqus