[[Ruby GC実装の歴史を読む]]
#contents
*はじめに [#ke1e71c3]
先日、Ruby 2.2がリリースされました。またGCが改良されたので読みます。今回入ったのは、[[RincGC>https://bugs.ruby-lang.org/projects/ruby-trunk/wiki/RincGC_ja]]とのことだそうです。ちなみにRGenGCとは違い、Rは何かの頭文字ではなさそうです。
*GC_ENABLE_INCREMENTAL_MARK [#i52e4b85]
gc.cを上から見ていくと、
#code(C){{
#ifndef GC_ENABLE_INCREMENTAL_MARK
#define GC_ENABLE_INCREMENTAL_MARK USE_RINCGC
#endif
}}
というコードがあります。どうやら、RincGCはこのマクロで制御されているようです。「ん？インクリメンタルマーク？スイープはいいの？」と思いましたが、スイープについては1.9.3ですでに[[lazy sweepが導入されている>Ruby GC実装の歴史/Ruby1.9.3のGCを読む]]のでもうインクリメンタルになっているのでしたね。
というコードがあります。どうやら、RincGCはこのマクロで制御されているようです。「ん？インクリメンタルマーク？スイープはいいの？」と思いましたが、スイープについては[[1.9.3ですでにlazy sweepが導入されている>Ruby GC実装の歴史/Ruby1.9.3のGCを読む]]のでもうインクリメンタルになっているのでしたね。
GC_ENABLE_INCREMENTAL_MARKで検索してみると以下が見つかります。
#code(C){{
typedef struct rb_heap_struct {
RVALUE *freelist;
struct heap_page *free_pages;
struct heap_page *using_page;
struct heap_page *pages;
struct heap_page *sweep_pages;
#if GC_ENABLE_INCREMENTAL_MARK
struct heap_page *pooled_pages;
#endif
size_t page_length; /* total page count in a heap */
size_t total_slots; /* total slot count (page_length * HEAP_OBJ_LIMIT) */
} rb_heap_t;
}}
同様にrb_objspace_tにもインクリメンタルマーク関連の変数が増えています。
#code(C){{
typedef struct rb_objspace {
....
struct {
enum gc_stat stat : 2;
unsigned int immediate_sweep : 1;
unsigned int dont_gc : 1;
unsigned int dont_incremental : 1;
unsigned int during_gc : 1;
unsigned int gc_stressful: 1;
#if USE_RGENGC
unsigned int during_minor_gc : 1;
#endif
#if GC_ENABLE_INCREMENTAL_MARK
unsigned int during_incremental_marking : 1;
#endif
} flags;
....
#if USE_RGENGC
struct {
VALUE parent_object;
int need_major_gc;
size_t last_major_gc;
size_t remembered_wb_unprotected_objects;
size_t remembered_wb_unprotected_objects_limit;
size_t old_objects;
size_t old_objects_limit;
#if RGENGC_ESTIMATE_OLDMALLOC
size_t oldmalloc_increase;
size_t oldmalloc_increase_limit;
#endif
#if RGENGC_CHECK_MODE >= 2
struct st_table *allrefs_table;
size_t error_count;
#endif
} rgengc;
#if GC_ENABLE_INCREMENTAL_MARK
struct {
size_t pooled_slots;
size_t step_slots;
} rincgc;
#endif
#endif /* USE_RGENGC */
} rb_objspace_t;
}}
インクリメンタルGCと世代別GCは独立してそうな気もしますがライトバリアが必要らしいのでRincGCはRGenGCが前提のようです。
この他、以下の関数前方宣言があります。
#code(C){{
#if GC_ENABLE_INCREMENTAL_MARK
static void gc_marks_step(rb_objspace_t *objspace, int slots);
static void gc_marks_continue(rb_objspace_t *objspace, rb_heap_t *heap);
#endif
}}
インクリメンタルGCを知っていれば関数名だけで何してそうか予想はつきますが、中断したマーキングを再開していると思われます。
*heap_prepare() [#k29af5ce]
gc.cを上から見ていくと以下のheap_prepare()が見つかります。
#code(C){{
static void
heap_prepare(rb_objspace_t *objspace, rb_heap_t *heap)
{
if (RGENGC_CHECK_MODE) assert(heap->free_pages == NULL);
#if GC_ENABLE_LAZY_SWEEP
if (is_lazy_sweeping(heap)) {
gc_sweep_continue(objspace, heap);
}
#endif
#if GC_ENABLE_INCREMENTAL_MARK
else if (is_incremental_marking(objspace)) {
gc_marks_continue(objspace, heap);
}
#endif
if (heap->free_pages == NULL &&
(will_be_incremental_marking(objspace) || heap_increment(objspace, heap) == FALSE) &&
gc_start(objspace, FALSE, FALSE, FALSE, GPR_FLAG_NEWOBJ) == FALSE) {
rb_memerror();
}
}
}}
オブジェクトが必要な時に、メモリが確保できなくなったらまずgc_start()が動き、その後はgc_marks_continue()が動くと想像されます。
gc_start()は長いので一部だけ。
#code(C){{
static int
gc_start(rb_objspace_t *objspace, const int full_mark, const int immediate_mark, const unsigned int immediate_sweep, int reason)
{
int do_full_mark = full_mark;
...
if (ruby_gc_stressful) {
int flag = FIXNUM_P(ruby_gc_stress_mode) ? FIX2INT(ruby_gc_stress_mode) : 0;
if ((flag & (1<<gc_stress_no_major)) == 0) {
do_full_mark = TRUE;
}
objspace->flags.immediate_sweep = !(flag & (1<<gc_stress_no_immediate_sweep));
}
else {
#if USE_RGENGC
if (objspace->rgengc.need_major_gc) {
reason |= objspace->rgengc.need_major_gc;
do_full_mark = TRUE;
}
else if (RGENGC_FORCE_MAJOR_GC) {
reason = GPR_FLAG_MAJOR_BY_FORCE;
do_full_mark = TRUE;
}
objspace->rgengc.need_major_gc = GPR_FLAG_NONE;
#endif
}
#if GC_ENABLE_INCREMENTAL_MARK
if (!GC_ENABLE_INCREMENTAL_MARK || objspace->flags.dont_incremental || immediate_mark) {
objspace->flags.during_incremental_marking = FALSE;
}
else {
objspace->flags.during_incremental_marking = do_full_mark;
}
#endif
}}
インクリメンタルGCが有効になるのはfull_markの時だけのようです。いろいろ設定した後、gc_marks()が呼ばれます。
#code(C){{
static void
gc_marks(rb_objspace_t *objspace, int full_mark)
{
gc_prof_mark_timer_start(objspace);
PUSH_MARK_FUNC_DATA(NULL);
{
/* setup marking */
#if USE_RGENGC
gc_marks_start(objspace, full_mark);
if (!is_incremental_marking(objspace)) {
gc_marks_rest(objspace);
}
#else /* USE_RGENGC */
...
#endif
}
POP_MARK_FUNC_DATA();
gc_prof_mark_timer_stop(objspace);
}
static void
gc_marks_start(rb_objspace_t *objspace, int full_mark)
{
/* start marking */
gc_report(1, objspace, "gc_marks_start: (%s)\n", full_mark ? "full" : "minor");
gc_stat_transition(objspace, gc_stat_marking);
#if USE_RGENGC
if (full_mark) {
#if GC_ENABLE_INCREMENTAL_MARK
objspace->rincgc.step_slots = (objspace->marked_slots * 2) / ((objspace->rincgc.pooled_slots / HEAP_OBJ_LIMIT) + 1);
if (0) fprintf(stderr, "objspace->marked_slots: %d, objspace->rincgc.pooled_page_num: %d, objspace->rincgc.step_slots: %d, \n",
(int)objspace->marked_slots, (int)objspace->rincgc.pooled_slots, (int)objspace->rincgc.step_slots);
#endif
objspace->flags.during_minor_gc = FALSE;
objspace->profile.major_gc_count++;
objspace->rgengc.remembered_wb_unprotected_objects = 0;
objspace->rgengc.old_objects = 0;
objspace->rgengc.last_major_gc = objspace->profile.count;
objspace->marked_slots = 0;
rgengc_mark_and_rememberset_clear(objspace, heap_eden);
}
else {
objspace->flags.during_minor_gc = TRUE;
objspace->marked_slots =
objspace->rgengc.old_objects +
objspace->rgengc.remembered_wb_unprotected_objects; /* long lived objects are marked already */
objspace->profile.minor_gc_count++;
rgengc_rememberset_mark(objspace, heap_eden);
}
#endif
gc_mark_roots(objspace, NULL);
gc_report(1, objspace, "gc_marks_start: (%s) end, stack in %d\n", full_mark ? "full" : "minor", (int)mark_stack_size(&objspace->mark_stack));
}
}}
gc_mark_roots()が呼ばれることで例によってルートオブジェクトから参照できるオブジェクトがマークスタックに積まれます。
ここで重要なのは、「ルートオブジェクトから参照されるオブジェクトを積むだけで、それらをトラバースしてマークしていかない」ということです。
*gc_marks_continue() [#m1feac46]
もう一回、オブジェクト取得要求が来ると、heap_prepare()はgc_marks_continue()を呼び出します。
#code(C){{
static void
gc_marks_continue(rb_objspace_t *objspace, rb_heap_t *heap)
{
int slots = 0;
const char *from;
if (RGENGC_CHECK_MODE) assert(dont_gc == FALSE);
gc_enter(objspace, "marks_continue");
PUSH_MARK_FUNC_DATA(NULL);
{
if (heap->pooled_pages) {
while (heap->pooled_pages && slots < HEAP_OBJ_LIMIT) {
struct heap_page *page = heap_move_pooled_pages_to_free_pages(heap);
slots += page->free_slots;
}
from = "pooled-pages";
}
else if (heap_increment(objspace, heap)) {
slots = heap->free_pages->free_slots;
from = "incremented-pages";
}
if (slots > 0) {
gc_report(2, objspace, "gc_marks_continue: provide %d slots from %s.\n", slots, from);
gc_marks_step(objspace, (int)objspace->rincgc.step_slots);
}
else {
gc_report(2, objspace, "gc_marks_continue: no more pooled pages (stack depth: %d).\n", (int)mark_stack_size(&objspace->mark_stack));
gc_marks_rest(objspace);
}
}
POP_MARK_FUNC_DATA();
gc_exit(objspace, "marks_continue");
}
}}
pooled_pagesを操作する箇所は出てきていませんが、スイープする際に設定されるようです。一回目はgc_marks_rest()に行くと思います。もうメモリがないので一部だけマークして、ということもできないからと思われます。二回目以降はオブジェクト要求に対しプールしてあるページを利用し、徐々にマーキングを進めていく、という戦略なのでしょう。
まあ今回の主題はインクリメンタルマーキングなのでgc_marks_step()に進みましょう。
#code(C){{
static void
gc_marks_step(rb_objspace_t *objspace, int slots)
{
if (RGENGC_CHECK_MODE) assert(is_marking(objspace));
if (gc_mark_stacked_objects_incremental(objspace, slots)) {
if (gc_marks_finish(objspace)) {
/* finish */
gc_sweep(objspace);
}
}
if (0) fprintf(stderr, "objspace->marked_slots: %d\n", (int)objspace->marked_slots);
}
}}
マークスタックにあるオブジェクトをインクリメンタルにマークして、最後に終了処理をしていると予想されます。
#code(C){{
static int
gc_mark_stacked_objects_incremental(rb_objspace_t *objspace, size_t count)
{
return gc_mark_stacked_objects(objspace, TRUE, count);
}
/**
* incremental: 0 -> not incremental (do all)
* incremental: n -> mark at most `n' objects
*/
static inline int
gc_mark_stacked_objects(rb_objspace_t *objspace, int incremental, size_t count)
{
mark_stack_t *mstack = &objspace->mark_stack;
VALUE obj;
#if GC_ENABLE_INCREMENTAL_MARK
size_t marked_slots_at_the_beggining = objspace->marked_slots;
size_t popped_count = 0;
#endif
while (pop_mark_stack(mstack, &obj)) {
if (obj == Qundef) continue; /* skip */
if (RGENGC_CHECK_MODE && !RVALUE_MARKED(obj)) {
rb_bug("gc_mark_stacked_objects: %s is not marked.", obj_info(obj));
}
gc_mark_children(objspace, obj);
#if GC_ENABLE_INCREMENTAL_MARK
if (incremental) {
if (RGENGC_CHECK_MODE && !RVALUE_MARKING(obj)) {
rb_bug("gc_mark_stacked_objects: incremental, but marking bit is 0");
}
CLEAR_IN_BITMAP(GET_HEAP_MARKING_BITS(obj), obj);
popped_count++;
if (popped_count + (objspace->marked_slots - marked_slots_at_the_beggining) > count) {
break;
}
}
else {
/* just ignore marking bits */
}
#endif
}
if (RGENGC_CHECK_MODE >= 3) {
gc_verify_internal_consistency(Qnil);
}
if (is_mark_stack_empty(mstack)) {
shrink_stack_chunk_cache(mstack);
return TRUE;
}
else {
return FALSE;
}
}
}}
途中でbreakしているのが肝です。これにより、「一部のマークが終わったら処理を抜ける（GC以外の処理を行う）」ということを実現しています。
*gc_marks_finish() [#ucec8dad]
最後に、終了処理のgc_marks_finish()。
#code(C){{
static int
gc_marks_finish(rb_objspace_t *objspace)
{
#if GC_ENABLE_INCREMENTAL_MARK
/* finish incremental GC */
if (is_incremental_marking(objspace)) {
if (heap_eden->pooled_pages) {
heap_move_pooled_pages_to_free_pages(heap_eden);
gc_report(1, objspace, "gc_marks_finish: pooled pages are exists. retry.\n");
return FALSE; /* continue marking phase */
}
if (RGENGC_CHECK_MODE && is_mark_stack_empty(&objspace->mark_stack) == 0) {
rb_bug("gc_marks_finish: mark stack is not empty (%d).", (int)mark_stack_size(&objspace->mark_stack));
}
gc_mark_roots(objspace, 0);
if (is_mark_stack_empty(&objspace->mark_stack) == FALSE) {
gc_report(1, objspace, "gc_marks_finish: not empty (%d). retry.\n", (int)mark_stack_size(&objspace->mark_stack));
return FALSE;
}
#if RGENGC_CHECK_MODE >= 2
if (gc_verify_heap_pages(objspace) != 0) {
rb_bug("gc_marks_finish (incremental): there are remembered old objects.");
}
#endif
objspace->flags.during_incremental_marking = FALSE;
/* check children of all marked wb-unprotected objects */
gc_marks_wb_unprotected_objects(objspace);
}
#endif /* GC_ENABLE_INCREMENTAL_MARK */
...
}
}}
また、gc_mark_roots()を呼んでいます。これは、「インクリメンタルマーキング中にルートオブジェクトから参照されるようになったオブジェクトがあるかもしれないからもう一回スキャンしてみる」ということのようです。
もう一つ、gc_marks_finish()では、gc_marks_wb_unprotected_objects()という関数を呼び出しています。この関数では、初めにあげたささださんの解説にある「ライトバリアで保護されていないマークされているオブジェクトを再スキャンする」という処理を行っています。
#code(C){{
static void
gc_marks_wb_unprotected_objects(rb_objspace_t *objspace)
{
struct heap_page *page = heap_eden->pages;
while (page) {
bits_t *mark_bits = page->mark_bits;
bits_t *wbun_bits = page->wb_unprotected_bits;
RVALUE *p = page->start;
RVALUE *offset = p - NUM_IN_PAGE(p);
size_t j;
for (j=0; j<HEAP_BITMAP_LIMIT; j++) {
bits_t bits = mark_bits[j] & wbun_bits[j];
if (bits) {
p = offset + j * BITS_BITLENGTH;
do {
if (bits & 1) {
gc_report(2, objspace, "gc_marks_wb_unprotected_objects: marked shady: %s\n", obj_info((VALUE)p));
if (RGENGC_CHECK_MODE > 0) {
assert(RVALUE_WB_UNPROTECTED((VALUE)p));
assert(RVALUE_MARKED((VALUE)p));
}
gc_mark_children(objspace, (VALUE)p);
}
p++;
bits >>= 1;
} while (bits);
}
}
page = page->next;
}
gc_mark_stacked_objects_all(objspace);
}
}}
*おわりに [#x8e850f3]
今回は2.2で導入されたRincGCを見てきました。基本的には普通のインクリメンタルGC（のマーキング部分）ですが、「もう一回スキャンしてみる」やライトバリア対応など徐々に機能追加したためにいろいろ頑張っている処理も見られました。この辺は[[初めからインクリメンタルGCなmruby>mruby/GC処理を読む]]とは異なる部分に思います。
では、2.3でGCが改良されないことを祈って終わりとしたいと思います（ぇ
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
