Ruby GC実装の歴史を読む
はじめに †
Ruby 2.0ではビットマップマーキングが導入されました。るびまの記事などを参照するとビットマップマーキングはCopy on Writeとの相性をよくするためのものなようです。では早速どういう実装なのか、どこら辺がCoWと相性がいいのかについて見ていくことにしましょう。対象としたのは2.0.0-p451です。
rb_newobj() †
まずはとっかかりとしてrb_newobj()を見てみましょう。
以下のようになっています。
1
2
3
4
5
6
7
8
9
10
11
12
| -
-
|
|
!
!
-
|
!
| if (UNLIKELY(!has_free_object)) {
if (!gc_prepare_free_objects(objspace)) {
during_gc = 0;
rb_memerror();
}
}
obj = (VALUE)objspace->heap.free_slots->freelist;
objspace->heap.free_slots->freelist = RANY(obj)->as.free.next;
if (objspace->heap.free_slots->freelist == NULL) {
unlink_free_heap_slot(objspace, objspace->heap.free_slots);
}
|
1
|
| #define has_free_object (objspace->heap.free_slots && objspace->heap.free_slots->freelist)
|
一方、1.9.3の対応部分。
1
2
3
4
5
6
7
8
9
| -
-
|
|
!
!
| if (UNLIKELY(!freelist)) {
if (!gc_lazy_sweep(objspace)) {
during_gc = 0;
rb_memerror();
}
}
obj = (VALUE)freelist;
freelist = freelist->as.free.next;
|
1
|
| #define freelist objspace->heap.freelist
|
似ていますが変わっています。全体のfreelistではなく個別（局所的な）のheaps_slotからオブジェクトを取り出しています。このあたりがCoW対応っぽい感じです。
heaps_slot構造体 †
ではheaps_slot構造体を見てみましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| -
|
|
|
|
|
|
!
-
|
|
|
|
|
!
| struct heaps_slot {
struct heaps_header *header;
uintptr_t *bits;
RVALUE *freelist;
struct heaps_slot *next;
struct heaps_slot *prev;
struct heaps_slot *free_next;
};
struct heaps_header {
struct heaps_slot *base;
uintptr_t *bits;
RVALUE *start;
RVALUE *end;
size_t limit;
};
|
同1.9.3。
1
2
3
4
5
6
7
| -
|
|
|
|
|
!
| struct heaps_slot {
void *membase;
RVALUE *slot;
size_t limit;
struct heaps_slot *next;
struct heaps_slot *prev;
};
|
heaps_header構造体（へのポインタ）、bits、先ほどのheaps_slot単位のfreelist、空きオブジェクトのあるheaps_slotをつないでそうなfree_nextが追加されています。bitsはビットマップマーキングに関連してそうな名前です。
assign_heap_slot() †
新しく出てきたheaps_header構造体は謎のままheaps_slot構造体を割り当てるassign_heap_slot()を見てみましょう。長いので抜き出して載せます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| -
!
-
!
-
!
-
!
| p = (RVALUE*)aligned_malloc(HEAP_ALIGN, HEAP_SIZE);
slot = (struct heaps_slot *)malloc(sizeof(struct heaps_slot));
slot->next = heaps;
if (heaps) heaps->prev = slot;
heaps = slot;
membase = p;
p = (RVALUE*)((VALUE)p + sizeof(struct heaps_header));
heaps->header = (struct heaps_header *)membase;
objspace->heap.sorted[hi] = heaps->header;
objspace->heap.sorted[hi]->start = p;
objspace->heap.sorted[hi]->end = (p + objs);
objspace->heap.sorted[hi]->base = heaps;
objspace->heap.sorted[hi]->limit = objs;
heaps->bits = (uintptr_t *)objspace->heap.free_bitmap;
objspace->heap.sorted[hi]->bits = (uintptr_t *)objspace->heap.free_bitmap;
objspace->heap.free_bitmap = objspace->heap.free_bitmap->next;
memset(heaps->bits, 0, HEAP_BITMAP_LIMIT * sizeof(uintptr_t));
|
どうやら確保したヒープの先頭をheaps_headerとして使っている様子です。なお、objspace->heap.sortedは2.0になって型がheaps_headerに変更されているので気をつけてください。baseにheaps_slotを入れている（逆参照）のが鍵っぽい気がします。また、objspace->heap.free_bitmapはビットマップマーキングに関連してそうです。
gc_prepare_free_objects() †
それではheaps_slot構造体の変更を眺めたところでGC部分を眺めていきましょう。2.0になってgc_lazy_sweepからgc_prepare_free_objectsという名前にリネームされたようですが中身は同じです。
gc_mark() †
オブジェクトをマークしていく流れは1.9.3から変更はありません。変わっているのは実際のマーク処理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
-
-
|
!
|
-
|
|
!
-
|
!
!
| static void
gc_mark(rb_objspace_t *objspace, VALUE ptr)
{
if (!markable_object_p(objspace, ptr)) {
return;
}
if (LIKELY(objspace->mark_func_data == 0)) {
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);
}
}
|
mark_func_dataとかはほっておいてgc_mark_ptr()に進みましょう。
1
2
3
4
5
6
7
8
9
|
-
|
|
|
|
|
!
| static int
gc_mark_ptr(rb_objspace_t *objspace, VALUE ptr)
{
register uintptr_t *bits = GET_HEAP_BITMAP(ptr);
if (MARKED_IN_BITMAP(bits, ptr)) return 0;
MARK_IN_BITMAP(bits, ptr);
objspace->heap.marked_num++;
return 1;
}
|
ビットマップ来ました:-)。さて、GET_HEAP_BITMAPマクロが何をしているか見てみましょう。
1
2
3
4
5
6
7
8
9
|
-
|
|
| #define HEAP_HEADER(p) ((struct heaps_header *)(p))
#define GET_HEAP_HEADER(x) (HEAP_HEADER((uintptr_t)(x) & ~(HEAP_ALIGN_MASK)))
#define GET_HEAP_BITMAP(x) (GET_HEAP_HEADER(x)->bits)
#define HEAP_ALIGN_LOG 14
enum {
HEAP_ALIGN = (1UL << HEAP_ALIGN_LOG),
HEAP_ALIGN_MASK = (~(~0UL << HEAP_ALIGN_LOG)),
|
・・・(´・ω・｀)？ptrってVALUEでRVALUE構造体指しててそのアドレスにマスクをかけたらheaps_header構造体へのポインタが取り出せる？とここで先ほどしれっと流したところが重要だったようです。assign_heap_slotの該当部分をもう一度載せます。
1
|
| p = (RVALUE*)aligned_malloc(HEAP_ALIGN, HEAP_SIZE);
|
aligned_mallocはプラットフォーム対応でいろいろやっていますが要するに第1引数で指定したアライメント境界にメモリを確保するというもののようです。つまり、
1
|
| #define GET_HEAP_HEADER(x) (HEAP_HEADER((uintptr_t)(x) & ~(HEAP_ALIGN_MASK)))
|
とすると確保したヒープの先頭アドレスが取り出せるというからくりのようです。これがわかれば後はbitsで指されたビットマップのオブジェクト対応部分に生存フラグを立てるだけです。
slot_sweep() †
オブジェクトのマーキングが終わったらlazy_sweep()→slot_sweep()と進んでビットが立っていないオブジェクトが解放されます。めんどくさいので見ておいてください（ぇ
Copy on Write対策の考察 †
さて、というわけで2.0から導入されたビットマップマーキングを見てきました。どこら辺がCoW対策なのでしょうか。って、答えはすでにご本人様が答えていますが。
マークではオブジェクトのヘッダフィールド上のFL_MARKフラグを立てる。
その後、すべてのオブジェクトをもう一度走査して、すべての死んでいるオブジェクトのマークを外す。
これの問題点は、CoWのセマンティクスを破壊することだ: マークするすべてのページがDirtyになってしまう.
そう、1.9.3までのGCはすべてのオブジェクトにFL_MARKしているため、「変更があった時だけ子プロセス用に新しくページを確保する」というCoWのメリットを台無しにしてしまっていたのです。それが、
Bitmap Markingアルゴリズムの良い点は以下のとおりです。
- ビットマップは、オブジェクトヘッダにマークビットを置くよりも、ビットを密集した領域に格納する
- 高い局所性
- マークはオブジェクトを変更しない。そして、スイープは生きているオブジェクトを変更しない。
- CoW friendly, ダーティキャッシュラインが少ない
となったことでオブジェクトごとにフラグを立てることなく、GCのためだけにオブジェクトのメモリを変更することはなくなったためにCoWフレンドリーになったということのようです。（当然、オブジェクトの状態が変わった場合はCoWされます）
後、見返すまで忘れていましたがfreelistをheaps_slotごとに持つようになったのも書き換えられる範囲を限定する（CoWが起こりにくくする）ためでしょう。
おわりに †
今回はRuby 2.0から導入されたGCのビットマップマーキングについて見てきました。Copy on Writeについてわかってないとなんでこんなことしているのか？ってコードになっています。ここら辺、ハイレベルな言語ではなくローレベルな言語の醍醐味って感じに思いました。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
