Ruby GC実装の歴史を読む
はじめに †
Ruby 2.1ではRGenGC(Restricted Generation GC)が導入されました。今までのGCに対してどのように世代別GCが導入されたのか、Restrictedってどういう意味なのかなどについて見ていくことにしましょう。対象としたのは2.1.1です。すでに2.1.2出てますが読み始めたときは2.1.1だったので2.1.1で読解していきます。（ほぼ変わりはありません）
RGenGCのパラメータ †
gc.cを上から見ていくとまずRGenGCのパラメータをdefineしているところがあります。配布されているソースそのままだと各値は以下のようになるようです。
1
2
3
4
5
|
| #define RGENGC_DEBUG 0
#define RGENGC_CHECK_MODE 0
#define RGENGC_PROFILE 0
#define RGENGC_THREEGEN 0
#define RGENGC_ESTIMATE_OLDMALLOC 1
|
パラメータのうち上3つはデバッグ・プロファイリング用、下2つがGC動作用のようです。3世代GCは興味を惹かれますがデフォルトdisableなので無視して読むことにします:-P
rb_newobj() †
いつもながらにrb_newobj()から見ていきます。下請けのnewobj_of()中に以下のコードがあります。
1
|
| obj = heap_get_freeobj(objspace, heap_eden);
|
2.1以降、heapは複数持たれるようになったようです。heap_edenが通常のheap、もう一つのheap_tombはページ内のオブジェクトが全部使われなくなった（死んだ）際のつなぎ先のようです。こうすると解放候補から1個だけ取られるということがなくなるから効率が良くなるのかな？RGenGCとは関係のない変更のようです。
で、heap_get_freeobj()。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
-
|
|
-
-
|
|
!
-
|
!
!
!
| static inline VALUE
heap_get_freeobj(rb_objspace_t *objspace, rb_heap_t *heap)
{
RVALUE *p = heap->freelist;
while (1) {
if (p) {
heap->freelist = p->as.free.next;
return (VALUE)p;
}
else {
p = heap_get_freeobj_from_next_freepage(objspace, heap);
}
}
}
|
2.0でslotごとにfreelistを管理するようになったはずですが見た感じ全体のfreelistに戻ってます。ソースを流し読みした感じでは通常、heap->freelistはNULLなようでelseの方が実行されるみたいです。先に進みます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
-
|
|
|
|
-
|
!
|
|
|
|
|
|
|
!
| static RVALUE *
heap_get_freeobj_from_next_freepage(rb_objspace_t *objspace, rb_heap_t *heap)
{
struct heap_page *page;
RVALUE *p;
page = heap->free_pages;
while (page == NULL) {
page = heap_prepare_freepage(objspace, heap);
}
heap->free_pages = page->free_next;
heap->using_page = page;
p = page->freelist;
page->freelist = NULL;
return p;
}
|
heap_pageは2.0までのheaps_slotと同じようなものです。freeなページを取り出してusingにつなぎかえ、freeなページがない場合はheap_prepare_freepage()呼んで確保を行っています。
さらに進む。ちょっと長いので一部端折ります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
-
|
|
|
|
-
|
!
|
-
|
|
|
!
|
|
|
!
| static struct heap_page *
heap_prepare_freepage(rb_objspace_t *objspace, rb_heap_t *heap)
{
if (!heap_ready_to_gc(objspace, heap)) return heap->free_pages;
during_gc++;
if ((is_lazy_sweeping(heap) && gc_heap_lazy_sweep(objspace, heap)) || heap_increment(objspace, heap)) {
goto ok;
}
if (garbage_collect_body(objspace, 0, 0, GPR_FLAG_NEWOBJ) == 0) {
err:
during_gc = 0;
rb_memerror();
}
ok:
during_gc = 0;
return heap->free_pages;
}
|
garbage_collect_body() †
garbage_collect_body()に進む。プロファイル系のコードとかを消去すると以下のような感じ。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
-
-
|
!
-
|
|
!
-
|
!
-
|
!
|
|
|
|
|
|
|
|
|
!
| static int
garbage_collect_body(rb_objspace_t *objspace, int full_mark, int immediate_sweep, int reason)
{
if (full_mark) {
reason |= GPR_FLAG_MAJOR_BY_NOFREE;
}
if (objspace->rgengc.need_major_gc) {
reason |= objspace->rgengc.need_major_gc;
objspace->rgengc.need_major_gc = GPR_FLAG_NONE;
}
if (objspace->rgengc.remembered_shady_object_count > objspace->rgengc.remembered_shady_object_limit) {
reason |= GPR_FLAG_MAJOR_BY_SHADY;
}
if (objspace->rgengc.old_object_count > objspace->rgengc.old_object_limit) {
reason |= GPR_FLAG_MAJOR_BY_OLDGEN;
}
if (immediate_sweep) reason |= GPR_FLAG_IMMEDIATE_SWEEP;
full_mark = (reason & GPR_FLAG_MAJOR_MASK) ? TRUE : FALSE;
gc_marks(objspace, full_mark);
gc_sweep(objspace, immediate_sweep);
during_gc = 0;
return TRUE;
}
|
RGenGCに関するパラメータが出てきました。見た感じ、以下の場合にmajor GCが動くようです。
- need_major_gcに値が設定されているとき
- shadyオブジェクトがリミットを超えたとき
- oldオブジェクトがリミットを超えたとき
それぞれの条件に関する記述は今まで見てきた中にはまだ出てきていません。
gc_marks()に進む。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
-
|
|
|
|
|
|
-
|
|
|
|
-
|
|
|
|
!
!
-
|
!
|
|
!
| static void
gc_marks(rb_objspace_t *objspace, int full_mark)
{
struct mark_func_data_struct *prev_mark_func_data;
prev_mark_func_data = objspace->mark_func_data;
objspace->mark_func_data = 0;
if (full_mark == TRUE) {
objspace->rgengc.remembered_shady_object_count = 0;
objspace->rgengc.old_object_count = 0;
gc_marks_body(objspace, TRUE);
{
const double r = gc_params.oldobject_limit_factor;
objspace->rgengc.remembered_shady_object_limit = objspace->rgengc.remembered_shady_object_count * r;
objspace->rgengc.old_object_limit = objspace->rgengc.old_object_count * r;
}
}
else {
gc_marks_body(objspace, FALSE);
}
objspace->mark_func_data = prev_mark_func_data;
}
|
とりあえずリミットに関する処理が出てきました。oldobject_limit_factorのデフォルト値は2.0でmajor GCしたときからshadyかoldなオブジェクトの数が2倍になったらmajor GCを行うということになっているようです。
続いてgc_marks_body()。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
-
|
|
|
-
|
!
-
|
!
|
|
!
| static void
gc_marks_body(rb_objspace_t *objspace, int full_mark)
{
objspace->rgengc.parent_object_is_old = FALSE;
objspace->rgengc.during_minor_gc = full_mark ? FALSE : TRUE;
if (objspace->rgengc.during_minor_gc) {
rgengc_rememberset_mark(objspace, heap_eden);
}
else {
rgengc_mark_and_rememberset_clear(objspace, heap_eden);
}
gc_mark_roots(objspace, full_mark, 0);
gc_mark_stacked_objects(objspace);
}
|
major GCかminor GCかで処理が分かれています。まずはmajor GCの方を見ることにしましょう。
major GCの場合 †
というわけでrgengc_mark_and_rememberset_clear()。
1
2
3
4
5
6
7
8
9
10
11
|
-
|
|
-
|
|
|
!
!
| static void
rgengc_mark_and_rememberset_clear(rb_objspace_t *objspace, rb_heap_t *heap)
{
struct heap_page *page = heap->pages;
while (page) {
memset(&page->mark_bits[0], 0, HEAP_BITMAP_SIZE);
memset(&page->rememberset_bits[0], 0, HEAP_BITMAP_SIZE);
page = page->next;
}
}
|
mark_bitsは2.0から導入されたビットマップマーキングに関するものです。remembersetって何でしょうか？ということで先に進みます。後、minor GCの場合はマークをクリアしないことが予想されます。
gc_mark_roots()、gc_mark_stacked_objects()は毎度おなじみのルートオブジェクトのマーク、スタックに積んだオブジェクトの再帰的マーキングです。末端のgc_mark()を見てみましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
-
|
|
-
|
|
|
!
-
|
!
!
| static void
gc_mark(rb_objspace_t *objspace, VALUE ptr)
{
if (!is_markable_object(objspace, ptr)) return;
if (LIKELY(objspace->mark_func_data == 0)) {
rgengc_check_relation(objspace, ptr);
if (!gc_mark_ptr(objspace, ptr)) return;
push_mark_stack(&objspace->mark_stack, ptr);
}
else {
objspace->mark_func_data->mark_func(ptr, objspace->mark_func_data->data);
}
}
|
2.0のころと比べると、rgengc_check_relation()が増えています。rgengcのプレフィクスが示す通りRGenGCに関する処理のようです。
1
2
3
4
5
6
7
8
9
10
11
|
-
-
-
-
|
!
!
!
!
| static void
rgengc_check_relation(rb_objspace_t *objspace, VALUE obj)
{
if (objspace->rgengc.parent_object_is_old) {
if (!RVALUE_WB_PROTECTED(obj)) {
if (rgengc_remember(objspace, obj)) {
objspace->rgengc.remembered_shady_object_count++;
}
}
}
}
|
親がoldかつ自身がライトバリア保護されていない場合、rememberとされています。remember、つまり、覚えておく、です。
覚えておくってどういうことなのかわからないのでgc_mark_children()を見てみましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
-
|
|
|
|
|
-
|
|
|
|
!
-
|
|
!
|
|
-
|
-
-
|
|
|
|
!
-
|
|
-
|
|
!
!
!
-
|
!
!
|
|
| static void
gc_mark_children(rb_objspace_t *objspace, VALUE ptr)
{
register RVALUE *obj = RANY(ptr);
goto marking;
again:
if (LIKELY(objspace->mark_func_data == 0)) {
obj = RANY(ptr);
if (!is_markable_object(objspace, ptr)) return;
rgengc_check_relation(objspace, ptr);
if (!gc_mark_ptr(objspace, ptr)) return;
}
else {
gc_mark(objspace, ptr);
return;
}
marking:
if (LIKELY(objspace->mark_func_data == 0)) {
if (RVALUE_WB_PROTECTED(obj)) {
if (RVALUE_INFANT_P((VALUE)obj)) {
RVALUE_PROMOTE_INFANT((VALUE)obj);
objspace->rgengc.old_object_count++;
objspace->rgengc.parent_object_is_old = TRUE;
}
else {
objspace->rgengc.parent_object_is_old = TRUE;
if (!objspace->rgengc.during_minor_gc) {
objspace->rgengc.old_object_count++;
}
}
}
else {
objspace->rgengc.parent_object_is_old = FALSE;
}
}
(以下、従来通り)
|
infantは幼児、つまり、最後にGCしてから生まれたオブジェクトです。それがルートオブジェクトからたどれるということは生き残ったということなのでoldオブジェクトということになります。なお、ifの場合もelseの場合もparent_object_is_oldをTRUEにするなどコードが冗長になっているのは実際には3世代GCのコードが書かれているためです。
RVALUE_PROMOTE_INFANT()をデバッグコード省略して2世代GCに限定すると以下のような感じ。
1
2
3
4
5
6
|
-
|
|
!
| static inline void
RVALUE_PROMOTE_INFANT(VALUE obj)
{
FL_SET2(obj, FL_PROMOTED);
MARK_IN_BITMAP(GET_HEAP_OLDGEN_BITS(obj), obj);
}
|
minor GCの場合 †
さて、というわけでオブジェクトがoldに設定される個所は確認できました。WB_PROTECTEDって何？を解決する前にminor GCの場合について見ていきましょう。今まで見てきた中でmajor/minorが分岐していたところはどこだったでしょうか。答えは、
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
-
|
|
|
-
|
!
-
|
!
|
|
!
| static void
gc_marks_body(rb_objspace_t *objspace, int full_mark)
{
objspace->rgengc.parent_object_is_old = FALSE;
objspace->rgengc.during_minor_gc = full_mark ? FALSE : TRUE;
if (objspace->rgengc.during_minor_gc) {
rgengc_rememberset_mark(objspace, heap_eden);
}
else {
rgengc_mark_and_rememberset_clear(objspace, heap_eden);
}
gc_mark_roots(objspace, full_mark, 0);
gc_mark_stacked_objects(objspace);
}
|
です。during_minor_gcがTRUE（full_markがFALSE）を見ると前にも見たremembersetに関する処理がされてそうです。この部分がポイントではあるのですがその前になんでこれでmajor/minorが分けれてるかを確認しましょう。
2.0から、オブジェクトのマークとはビットマップ中のオブジェクトに対応するビットを立てることになりました。
もうビットが立っていたら改めてそれ以降（フィールド）のマーキングはしません。（gc_mark_ptr()参照）
ところで、full_markがTRUEの場合はマークされてるかビットをクリア（全部再確認）しますが、FALSEの場合はしません。
つまり、一度マークされたオブジェクトは次にmajor GCが起こるまではフィールドのチェックは行われません。これでオブジェクトが生きているかの確認処理を削減することができます。生きているとされているオブジェクトは実は死んでるかもしれませんが、一度生き残ったオブジェクトは長生きする（一時オブジェクトはすぐ死ぬ→回収される）という経験則を利用しています。まあ死んでるものはそのうち（major GCで）回収されます。
さて、以上、終わり、とできれば話は楽なのですがこれだけだと問題があります。それを説明するのがめんどくさい、というかさわだが参考にしたサイトに説明を丸投げします。読んで理解したら戻ってきてくださいね（ぉ
戻ってきていただきありがとうございます。そう、謎のremembersetとはnewなオブジェクトを参照してしまったoldオブジェクトです。先ほどの分岐でminor GCの場合に呼び出していたrgengc_rememberset_mark()ではremembersetに入れられたオブジェクトのマーキングを行っています。
ライトバリア周り †
では残りの問題を片付けましょう。残っているのは、ライトバリアです。参考サイトでは次の2つのことが述べられていました。
- newなオブジェクトを参照したoldはrembersetに送られる
- RARRAY_PTRマクロを使われるなど追っかけきれない場合はshady（WB_PROTECTEDではない）化する
それぞれ見ていきましょう。
old→newしたらremebersetに送られる †
オブジェクト間の参照関係ということで、Array#[]=を実装しているrb_ary_aset()を見てみましょう。ソースはarray.cに移ります。本当はもう少しいろいろやっていますがばっさり削って載せます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
-
|
|
|
|
|
!
-
|
!
| static VALUE
rb_ary_aset(int argc, VALUE *argv, VALUE ary)
{
long offset;
offset = NUM2LONG(argv[0]);
rb_ary_store(ary, offset, argv[1]);
return argv[1];
}
void
rb_ary_store(VALUE ary, long idx, VALUE val)
{
RARRAY_ASET(ary, idx, val);
}
|
RARRAY_ASETはruby.hに書かれているマクロです。
1
2
3
4
| -
|
|
!
| #define RARRAY_ASET(a, i, v) do { \
const VALUE _ary_ = (a); \
RB_OBJ_WRITE(_ary_, &RARRAY_CONST_PTR(_ary_)[i], (v)); \
} while (0)
|
RB_OBJ_WRITEマクロはファイル名と行番号を追加して同じくruby.hに書かれているrb_obj_write()を呼び出します。って、使ってないの？
1
2
3
4
5
6
7
8
|
-
|
|
|
|
!
| static inline VALUE
rb_obj_write(VALUE a, VALUE *slot, VALUE b, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
*slot = b;
rb_obj_written(a, Qundef , b, filename, line);
return a;
}
|
rb_obj_written()もruby.hに書かれています。
1
2
3
4
5
6
7
8
9
10
|
-
|
-
|
!
|
|
!
| static inline VALUE
rb_obj_written(VALUE a, RB_UNUSED_VAR(VALUE oldv), VALUE b, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
if (FL_TEST_RAW((a), FL_PROMOTED) && !SPECIAL_CONST_P(b)) {
rb_gc_writebarrier(a, b);
}
return a;
}
|
a、フィールドを変更しようとしたオブジェクトがoldだったらrb_gc_writebarrier()を呼び出しています。ここでgc.cに戻ります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
-
-
|
|
-
|
|
|
-
-
|
!
!
-
|
!
!
!
!
| void
rb_gc_writebarrier(VALUE a, VALUE b)
{
if (!RVALUE_OLD_P(b) && RVALUE_OLD_BITMAP_P(a)) {
rb_objspace_t *objspace = &rb_objspace;
if (!rgengc_remembered(objspace, a)) {
int type = BUILTIN_TYPE(a);
if ((type == T_ARRAY && RARRAY_LEN(a) >= 2 << 16) ||
(type == T_HASH && RHASH_SIZE(a) >= 2 << 16)) {
if (!rgengc_remembered(objspace, b)) {
rgengc_remember(objspace, b);
}
}
else {
rgengc_remember(objspace, a);
}
}
}
}
|
仕様通り、newなオブジェクトを参照したoldがremembersetに送られています。Array, Hashのサイズが65536以上だったらのコードは、親をrememberに入れてしまうとマーク時間が長くなってしまうからというハックっぽいですね。と思ったら2.1.2ではなくなってるようです。
管理しきれない場合はライトバリアを外す †
最後にRARRAY_PTRマクロを見てみましょう。再びruby.hです。
1
|
| #define RARRAY_PTR(a) ((VALUE *)RARRAY_CONST_PTR(RGENGC_WB_PROTECTED_ARRAY ? OBJ_WB_UNPROTECT((VALUE)a) : ((VALUE)a)))
|
unprotectされています。もう少し追いかけてみましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
-
|
-
-
|
!
|
!
|
!
| #define OBJ_WB_UNPROTECT(x) (x, __FILE__, __LINE__)
static inline VALUE
rb_obj_wb_unprotect(VALUE x, RB_UNUSED_VAR(const char *filename), RB_UNUSED_VAR(int line))
{
if (FL_TEST_RAW((x), FL_WB_PROTECTED)) {
if (FL_TEST_RAW((x), FL_PROMOTED)) {
rb_gc_writebarrier_unprotect_promoted(x);
}
RBASIC(x)->flags &= ~FL_WB_PROTECTED;
}
return x;
}
|
ここからgc.c。
1
2
3
4
5
6
7
8
9
10
11
12
|
-
|
|
-
|
|
|
|
!
!
| void
rb_gc_writebarrier_unprotect_promoted(VALUE obj)
{
rb_objspace_t *objspace = &rb_objspace;
if (RVALUE_OLD_P(obj)) {
RVALUE_DEMOTE_FROM_OLD(obj);
rgengc_remember(objspace, obj);
objspace->rgengc.remembered_shady_object_count++;
}
}
|
というわけでoldオブジェクトからshadyオブジェクトになりました。
で、結局何がRestrictedなのか †
- 本当ならold→newの参照をする可能性のあるところにはすべてライトバリアを入れたい
- が、そのためには過去の拡張ライブラリを全ビルドしないといけない
- だったら、ライトバリアされてなくても動けるようにしてライトバリア対応されているものを徐々に増やしていこう
というのが世代別GCを入れたけど、効果は限定されてますよ〜って意味なのかなと思います。過去の資産を大事にすることの大変さを感じるコードです(笑)
おわりに †
さて、2.1のGC（RGenGC）を見てきました。どういうものかは先に挙げた参考サイトやささださんの発表資料を見てください（ぉ
RGenGCを読むにあたって1.9.3、2.0と順に読んできましたが無駄ではなかったなと思います。1.9.3で入ったlazy sweep、2.0で入ったビットマップマーキングを踏まえたうえでさらにGCの時間を短くするにはどうすればいいかということでRGenGCが導入されていました。長くなりましたが（たまにしか読んでなくて時間がかかったという噂あり）これにてRuby GC実装の歴史を読むを終わりたいと思います。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
