読者です 読者をやめる 読者になる 読者になる

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

[ruby] Rubyのgc.cを読んでみたまとめ

しばらく前からtwitterRubyGC読んでるとか読んでないとか言って、結局エントリ書いてなかったのでまとめ。

RubyGCは、mark and sweepというアルゴリズムを用いている。これは、「必要だとわかっているオブジェクトからスタートして、再帰的にmarkをつけていき、最終的にmarkが無いものを開放するというものだ。まあ発想は素直といえば素直。

GCの流れを説明しよう。mark and sweepなので、markとsweepという2つのフェーズから構成されている。

まず、説明をわかりにくくするためにsweepフェーズから説明すると、オブジェクト用の領域に関してはmallocを使って確保したものをfreeせずに使いまわしている(たぶんそっちのほうが速いから)。free()のコストも馬鹿にならないのだ。だから、最初に書いたmarkがついていないものを開放するというのは、実際には空きオブジェクト領域のリストに繋がれることだ。そのため、Rubyのオブジェクトは、C言語の共用体を持ちいて(やや強引に)すべて同じサイズに揃えられている。

ただし、libcのmalloc/freeも相当いろいろ工夫をしているわけで、実際問題どちらが速いのかは自分にはわからない。現在のRubyの実装の場合は、おそらくfreeを使わない実装のほうがいいという判断なのだろう。参考:http://www.rubyist.net/~matz/20060925.html#p01

次がmarkフェーズだ。必要だとわかっているオブジェクト(これをルートオブジェクトと一般には呼ぶ。たぶん)からたどって、次々にmarkをつけていく。

RubyGCは、3つの領域にあるオブジェクトをルートとして走査する。
* Rubyインタプリタ構文木(現在のRuby構文木を直接実行する方式なのであった)
* Rubyレベルでの呼び出しスタックフレーム
* スタック領域
* シンボルテーブル
* Rubyのスレッド
* 登録されたスタティック変数・グローバル変数領域
* その他いろいろ。

実際のコードを見ると、まあまあわかる。省いてはいないが、コメントを編集してある。

static void
garbage_collect()
{
    struct gc_list *list;
    struct FRAME * volatile frame; /* gcc 2.7.2.3 -O2 bug??  */
    jmp_buf save_regs_gc_mark;
    SET_STACK_END;

#ifdef HAVE_NATIVETHREAD
    if (!is_ruby_native_thread()) {
        rb_bug("cross-thread violation on rb_gc()");
    }
#endif
    /* GC中はGCしないで、Heapを追加する */
    if (dont_gc || during_gc) {
        if (!freelist) {
            add_heap();
        }
        return;
    }
    if (during_gc) return;
    during_gc++;

    /* (C言語レベルでの)関数呼び出しのスタック溢れを検出する*/
    init_mark_stack();

    /* Rubyインタプリタの構文木を走査 */
    gc_mark((VALUE)ruby_current_node, 0);

    /* Rubyの関数呼び出しスタックフレーム(たぶん)を走査*/
    for (frame = ruby_frame; frame; frame = frame->prev) {
        rb_gc_mark_frame(frame);
        if (frame->tmp) {
            struct FRAME *tmp = frame->tmp;
            while (tmp) {
                rb_gc_mark_frame(tmp);
                tmp = tmp->prev;
            }
        }
    }

    /* scope,つまりシンボルテーブルを走査*/
    gc_mark((VALUE)ruby_scope, 0);

    /*  なんだろうdynamic variables  */
    gc_mark((VALUE)ruby_dyna_vars, 0);
    if (finalizer_table) {
        mark_tbl(finalizer_table, 0);
    }

    FLUSH_REGISTER_WINDOWS;

    /* レジスタの内容を読み出して走査 */
    setjmp(save_regs_gc_mark);
    mark_locations_array((VALUE*)save_regs_gc_mark, sizeof(save_regs_gc_mark) / sizeof(VALUE *));


    /* スタックを走査 */
#if STACK_GROW_DIRECTION < 0
    rb_gc_mark_locations((VALUE*)STACK_END, rb_gc_stack_start);
#elif STACK_GROW_DIRECTION > 0
    rb_gc_mark_locations(rb_gc_stack_start, (VALUE*)STACK_END + 1);
#else
    if ((VALUE*)STACK_END < rb_gc_stack_start)
        rb_gc_mark_locations((VALUE*)STACK_END, rb_gc_stack_start);
    else
        rb_gc_mark_locations(rb_gc_stack_start, (VALUE*)STACK_END + 1);
#endif
#ifdef __ia64
    /* mark backing store (flushed register window on the stack) */
    /* the basic idea from guile GC code                         */
    rb_gc_mark_locations(rb_gc_register_stack_start, (VALUE*)rb_ia64_bsp());
#endif
#if defined(__human68k__) || defined(__mc68000__)
    rb_gc_mark_locations((VALUE*)((char*)STACK_END + 2),
                         (VALUE*)((char*)rb_gc_stack_start + 2));
#endif

    /* 各スレッドを走査 */
    rb_gc_mark_threads();

    /* 明示的に登録されたグローバル変数を登録する*/
    for (list = global_List; list; list = list->next) {
        rb_gc_mark_maybe(*list->varptr);
    }
    rb_mark_end_proc();
    rb_gc_mark_global_tbl();

    rb_mark_tbl(rb_class_tbl);
    rb_gc_mark_trap_list();


    /* special constants のために、インスタンス変数の一覧を走査する(意味わからナス) */
    rb_mark_generic_ivar_tbl();

    /* yaccとかlexまわりのオブジェクトを走査*/
    rb_gc_mark_parser();

    /* gc_mark objects whose marking are not completed*/
    do {
        while (!MARK_STACK_EMPTY) {
            if (mark_stack_overflow){
                gc_mark_all();
            }
            else {
                gc_mark_rest();
            }
        }
        rb_gc_abort_threads();
    } while (!MARK_STACK_EMPTY);

    /* 最後に、マークのついていないオブジェクトをを回収する*/
    gc_sweep();
}

スタック領域の走査だけちょっと詳しく調べた

個人的にスタック領域の調べ方が一番興味があったので、そこを重点的に調べた(というか、他は調べてない)。

一般に、スタックを「積む」というとアドレスが上昇していくことを連想するが、実はスタックの伸びる方向はCPUのアーキテクチャごとに違う。特にx86系のアーキテクチャでは上位番地から下位番地に向かって伸びていく。この方向は、ソース中の定数STACK_GROW_DIRECTIONであらわされ、configureスクリプトによって定義されている。

# in configure.in
case "$target_cpu" in
m68*|i?86|ia64|sparc*|alpha*) rb_cv_stack_grow_dir=-1;;

   ...

AC_DEFINE_UNQUOTED(STACK_GROW_DIRECTION, $rb_cv_stack_grow_dir)

ふむふむ。
ちなみに、未知のアーキテクチャだった場合は、以下のCコードを走らせて取得するようになってる。

/* in configure.in */
/* recurse to get rid of inlining */
static int
stack_growup_p(addr, n)
    volatile int *addr, n;
{
    volatile int end;
    if (n > 0)
    return *addr = stack_growup_p(addr, n - 1);
    else
    return (&end > addr);
}
int main()
{
    int x;
    return stack_growup_p(&x, 10);
}

よし、あとはスタックの開始アドレス(つまりプログラムが開始したときのフレームのアドレス)と現在の関数呼び出しのフレームのアドレスがわかれば、あとはそれをVALUEの配列として走査すればいい。

現在のフレームのアドレスは、alloca()関数が返すアドレスをそのまま使えばいい。allocaは、スタック領域から動的にメモリ領域を確保してくれる関数。(これが標準ライブラリで提供されていない場合は、いろいろがんばるらしい)。スタックのスタート地点は、ruby_init()の中で呼び出されるInit_stack()で設定される。つまり、プログラム実行の最初のほうに取得しておいて、後で使うということ(たぶん)。

というわけで、わかったようなわからないような説明終わり。

【広告】