[ruby] Rubyのgc.cを読んでみたまとめ
しばらく前からtwitterでRubyのGC読んでるとか読んでないとか言って、結局エントリ書いてなかったのでまとめ。
RubyのGCは、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をつけていく。
RubyのGCは、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()で設定される。つまり、プログラム実行の最初のほうに取得しておいて、後で使うということ(たぶん)。
というわけで、わかったようなわからないような説明終わり。