Ruby GC実装の歴史を読む

はじめに †

先日、Ruby 2.2がリリースされました。またGCが改良されたので読みます。今回入ったのは、RincGCとのことだそうです。ちなみにRGenGCとは違い、Rは何かの頭文字ではなさそうです。

↑

GC_ENABLE_INCREMENTAL_MARK †

gc.cを上から見ていくと、

Everything is expanded.Everything is shortened.
  1
  2
  3

 
 
 

#ifndef GC_ENABLE_INCREMENTAL_MARK
#define GC_ENABLE_INCREMENTAL_MARK USE_RINCGC
#endif

というコードがあります。どうやら、RincGCはこのマクロで制御されているようです。「ん？インクリメンタルマーク？スイープはいいの？」と思いましたが、スイープについては1.9.3ですでにlazy sweepが導入されているのでもうインクリメンタルになっているのでしたね。

GC_ENABLE_INCREMENTAL_MARKで検索してみると以下が見つかります。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13

-
|
|
|
|
|
|
|
|
|
|
|
!

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にもインクリメンタルマーク関連の変数が増えています。

Everything is expanded.Everything is shortened.
  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
 45

-
|
-
|
|
|
|
|
|
|
|
|
|
|
|
!
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
!
|
-
|
|
!
|
|
!

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が前提のようです。

この他、以下の関数前方宣言があります。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4

 
 
 
 

#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() †

gc.cを上から見ていくと以下のheap_prepare()が見つかります。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22

 
 
-
|
|
|
-
|
!
|
|
-
|
!
|
|
|
|
-
|
!
!

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()は長いので一部だけ。

Everything is expanded.Everything is shortened.
  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

 
 
-
|
|
-
|
|
-
|
!
|
|
!
-
|
-
|
|
!
-
|
|
!
|
|
|
!
|
|
-
|
!
-
|
!
|

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<
            do_full_mark = TRUE;
        }
 
        objspace->flags.immediate_sweep = !(flag & (1<}
    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()が呼ばれます。

Everything is expanded.Everything is shortened.
  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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60

 
 
-
|
|
|
-
|
|
|
|
-
|
!
|
|
|
|
!
|
|
!
 
 
 
-
|
|
|
|
|
-
|
|
|
|
|
|
|
|
|
|
|
|
|
!
-
|
|
|
|
|
|
!
|
|
|
|
|
!

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() †

もう一回、オブジェクト取得要求が来ると、heap_prepare()はgc_marks_continue()を呼び出します。

Everything is expanded.Everything is shortened.
  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

 
 
-
|
|
|
|
|
|
|
|
-
-
-
|
|
!
|
!
-
|
|
!
|
-
|
|
!
-
|
|
!
!
|
|
|
!

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()に進みましょう。

Everything is expanded.Everything is shortened.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13

 
 
-
|
|
-
-
|
|
!
!
|
!

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);
}

マークスタックにあるオブジェクトをインクリメンタルにマークして、最後に終了処理をしていると予想されます。

Everything is expanded.Everything is shortened.
  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
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58

 
 
-
|
!
 
-
|
|
!
 
 
-
|
|
|
|
|
|
|
-
|
|
-
|
!
|
|
|
-
-
|
!
|
|
|
-
|
!
!
-
|
!
|
!
|
-
|
!
|
-
|
|
!
-
|
!
!

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() †

最後に、終了処理のgc_marks_finish()。

Everything is expanded.Everything is shortened.
  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

 
 
-
|
|
-
-
|
|
|
!
|
-
|
!
|
|
|
-
|
|
!
|
|
-
|
!
|
|
|
|
|
!
|
|
!

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()という関数を呼び出しています。この関数では、初めにあげたささださんの解説にある「ライトバリアで保護されていないマークされているオブジェクトを再スキャンする」という処理を行っています。

Everything is expanded.Everything is shortened.
  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

 
 
-
|
|
-
|
|
|
|
|
|
-
|
|
-
|
|
-
-
|
-
|
|
!
|
!
|
|
!
!
!
|
|
!
|
|
!

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
            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);
}
↑

おわりに †

今回は2.2で導入されたRincGCを見てきました。基本的には普通のインクリメンタルGC（のマーキング部分）ですが、「もう一回スキャンしてみる」やライトバリア対応など徐々に機能追加したためにいろいろ頑張っている処理も見られました。この辺は初めからインクリメンタルGCなmrubyとは異なる部分に思います。

では、2.3でGCが改良されないことを祈って終わりとしたいと思います（ぇ

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS