mrubyのGCの仕組みを調べた

動機

LuaのAPIは、Lua内部で扱われる値に関してスタック上であれこれ操作出来るだけで、値自体を直接取得したり作成することはできない。 値を取り出したいときはスタック上の特定の場所にある値の型を調べて、その型の値を取り出すAPIを呼び出す、という具合になっている。 この場合、処理系で扱う値はすべて処理系側で管理されているので、ガベージコレクト(GC)できるのもわからんでもない。

しかしmrubyのAPIではスクリプト内部で扱う値をmrb_valueとしてC言語側に直接取り出せる。 この場合処理系の管理を逃れてしまうことはないのか。 またCの関数でmrubyのオブジェクトを作成した瞬間にGCが走った場合に、まだmrubyで管理している変数からの参照がなくて、解放されてしまったりしないのか。

大昔の事しか知らないけど、Rubyの場合はC側のスタック全部を調べていた（Rubyソースコード完全解説 - 第5章 ガ－ベージコレクション）ので、Cの拡張モジュールではその辺のことは何も考えずにすんでいたと思うが（グローバル変数やヒープはどうしてるんだろう？）、mrubyではどうやってGCしているのかを知りたい。

そのため、src/gc.cを読んでみた。

前提

まず基本的な知識として、mrubyで実際のメモリ確保をするallocf関数によって確保したメモリには、GC対象となるものとならないものの２種類がある。 mrubyの（単純じゃない）オブジェクトとして扱われるものだけがGC対象（マーク＆スイープされる）で、それ以外の単純なオブジェクトや内部で使うメモリなどは対象外で、手動で管理している。

実際にGC対象となるのは、Object, Class, String, Array, Hash, Range, Data, Procなどで、これらのオブジェクトを確保するにはmrb_obj_alloc()関数が使われる。 mrb_valueは、そのようなオブジェクトはポインタ、そうじゃない単純なオブジェクト(float, int, bool, シンボル)は実体として内部に持っている。 mrb_value自体はGC対象ではない。

GC対象となる構造体は頭に必ずMRB_OBJECT_HEADERを持っている（20バイト）：

#define MRB_OBJECT_HEADER \
  enum mrb_vtype tt:8;\
  uint32_t color:3;\
  uint32_t flags:21;\
  struct RClass *c;\
  struct RBasic *gcnext

colorがGCのマークとして使われる。

GC対象のオブジェクトはページ(heap_page)という単位で管理されている。 RVALUEというGC対象となるオブジェクトの共用体を、１ページにつきMRB_HEAP_PAGE_SIZE個(1024)保持することができる。 ちなみにMac OSXで試したところsizeof(RVALUE) = 48だった。

GCで管理されないものには、例えば文字列本体などがある。 文字列のオブジェクトはGC対象だけど、実際の文字列を格納しているメモリは文字列オブジェクトによって管理されているので、GC対象にする必要はない、ということ。 文字列オブジェクトが解放されるときに一緒に解放されるようになっている(obj_free()内でオブジェクトのタイプごとに後始末が書かれている)。

シンボルもGC対象ではない。 シンボルは確保しっぱなしになっていて、解放されるのはmrb_close()時にmrb_free_symtbl()が呼ばれた時だけ。

その他のGC対象外のメモリも、誰かが管理して適切に解放している、のだろう。

GCの処理

GC自体は三色インクリメンタルGCとのことで、基本的なGCの仕組み通り、ルートから辿れるオブジェクトにマークをしていって、マークされなかったオブジェクトを解放する、という手順になっている。

mrubyのGCは次の4つの状態を順に実行する：

1. ルートスキャン：ルートとなっているオブジェクト（グローバル変数など）をグレーに塗って、リストに追加する
2. インクリメンタルマーキング：グレーリストに登録されているオブジェクト取り出して黒に塗って、そいつから辿れるオブジェクトをグレーリストに登録する。リストが空になったら次に進む。
3. ファイナルマーキング：インクリメンタルマーキング中にミューテータによって変更・新規作成されたオブジェクトを調べて、黒白つける
4. インクリメンタルスイープ：ページごとに調べて、ごみとなった（白いままの）オブジェクトを解放する

1と3は一気に、2と4は少しずつ進められる。 マークの色は白、グレー、黒の3色で、白はマークされてない、グレーはマーク途中（自分自身はマーク済み、子は未チェック）、黒はマーク済み（子もチェック済み）。 白には2種類あって、1のルートスキャン完了時に使う白の色を切り替えて、以降に新しく作られたオブジェクトには別の白を使うことで、その回のスイープ時には対象外となる。

インクリメンタルに処理している間にミューテータ側からオブジェクトの書き換えが起こることに対応するため、ライトバリアという仕組みを使っている。 勝手な思い込みで、ライトバリアというのはコピーオンライトのようなMMUの機能かなんかを使ってバリアを張ったフィールド内の書き換えを検知して、割り込みかなんかで処理するのかと思っていたのだけどそうじゃなくて、オブジェクトの値を書き換える所でmrb_write_barrier()もしくはmrb_field_write_barrier()関数を手動で呼び出すことで、すでにマークフェーズによって黒に塗られていたらグレーに戻してリストにつないでおいて、3のファイナルマーキングフェーズでもう一度調べる、という処理をしている。

世代別GCも入っている。 若いか若くないかはページ単位で管理されている。 ページがすべてオブジェクトで埋まっていてかつそのページがマイナーGCのスイープを1回生き延びたら、昇格して次回以降のマイナーGCのスイープは免除される。

ちなみに、インクリメンタルGCが進められるのはmrb_obj_alloc()が行われる時だけ。 （生きている＋前回のGCから生成された）オブジェクトの数がgc_thresholdを超えたらインクリメンタルGCが進められる。

参考：

• mruby/GC処理を読む - Code Reading Wiki
• mrubyのGC解説まとめ - GC Advent Calendar - I am Cruby!
• GC/extend/IncrementalGC - GCアルゴリズム詳細解説 - livedoor Wiki（ウィキ）

作成中のオブジェクトが削除されない仕組み

知りたかった、C側で作成中のオブジェクトが不用意に解放されないか、という点だけど、これはmrb_obj_alloc()でオブジェクトを作成した段階でmrb_gc_protect()関数でarenaという領域に自動的に追加されて、arenaにあるオブジェクトはroot_scan_phase()によってマークされるので大丈夫、ということになっていた。

arenaはスタック構造(LIFO)になっていて、mrb_gc_protect()ではarena_idxを増やしていくだけ、arena_idxが戻るのはmrb_gc_arena_save()で取得したarenaの位置をmrb_gc_arena_restore()で復元するとき、となっている。

これによって一部問題が生じる可能性がある。 mrb_define_method()などで登録したCの関数内でオブジェクトを生成している場合にはその外部でarenaの保存〜復元がされているのであまり問題ないが、そうじゃなくてアプリケーションの地のプログラム側でオブジェクトを生成している場合には溜まっていく一方になってしまうので、arena_save〜restoreを自分で呼び出す必要がある。

参考：

• “arena overflow error” で mruby がとまるときの対策 - tokuhirom’s blog.
• How to use mrb_gc_arena_save and mrb_gc_arena_restore? Improve API? · Issue #887 · mruby/mruby

ということで、arenaに自動的に追加されるのでGCが適切に行われる、という仕組みだった。 Cからmrb_valueは取得できるけど、それを保存しておいてずっと使う、といったことはできない。 例えばglutDisplayFunc()にmrubyのブロックを登録したいと思ったら、mruby側でその参照を保持していないとGCされてしまう。

不明な点

マイナーGCの場合はインクリメンタルじゃなくてストップザワールドしている！？ いくらマイナーGCとはいえ、恩恵をうけるのはスイープだけだし、直感的にはそんなに軽くないような。 なにか理由があるんだろうか？

void
mrb_incremental_gc(mrb_state *mrb)
{
  ...
  if (is_minor_gc(mrb)) {
    do {
      incremental_gc(mrb, ~0);
    } while (mrb->gc_state != GC_STATE_NONE);
  }
  else {
    ...

※追記：マイナーGCでは若いオブジェクトの数を調整できるので、インクリメンタルじゃなくても大丈夫とのこと。マイナーGCでは、スイープ時に黒くなっているオブジェクトを白に戻さずそのままにするので、ライトバリアで変更があったものか、新たにルートに追加されたものだけが次回のマークでチェックされる。

また、マイナーGCからメジャーGCに切り替わるときにclear_all_old()を呼び出してるけど、必要あるんだろうか。

あと、メジャーGCが走るのはマイナーGCし終わった時に残ったオブジェクトの数が前回メジャーGCしたあとに残ったオブジェクトの数x200(DEFAULT_MAJOR_GC_INC_RATIO)以上だった時となっていて、直感的には多すぎるように感じるけど、妥当なのか？

メジャーGCが行われるとすべてのページは若返ってしまうけど、空きができた時だけ若返るではだめだろうか？