[[mrubyを読む]]
#contents
*はじめに [#d2829603]
今回はmrubyのGC周りを読みます。なお、対象としたバージョンはcommit 04d24b3168です。
*mrubyで用いられているGC [#q7672c7c]
いきなりソースに入る前にmrubyではどのようなGCが行われているか確認しましょう。src/gc.cの先頭にmrubyで行っているGCについて書かれています。
説明によるとmrubyで使っているGCは「3色インクリメンタルGC」というもののようです。3色とは、
:白|マークされていない。アロケート直後はこの色
:灰色|自身はマークされているが子オブジェクトはマークされていない
:黒|自身も子オブジェクトもマークされている
マークというのはCRubyでおなじみマーク & スイープのマークのことです。
また、白については正確には白Aと白Bがあり、アロケートされたオブジェクトが次のスイープ時に即スイープされるということはないようです。
なお、一回のGCでどれだけGCするかをRubyレベルで設定することが可能です。ここら辺、処理の実行時間が何よりの興味対象である組み込み向けっぽいですね。
インクリメンタルGC、その他いろんなGCについて詳しく知りたい場合は[[author_nariさんのページ>http://wiki.livedoor.jp/author_nari/]]をご参照ください。
*mrb_obj_alloc [#ac6b4a26]
ではまずオブジェクトをアロケートするmrb_obj_alloc()から見てみましょう。
#code(C){{
struct RBasic*
mrb_obj_alloc(mrb_state *mrb, enum mrb_vtype ttype, struct RClass *cls)
{
struct RBasic *p;
if (mrb->gc_threshold < mrb->live) {
mrb_incremental_gc(mrb);
}
if (mrb->free_heaps == NULL) {
add_heap(mrb);
}
p = mrb->free_heaps->freelist;
mrb->free_heaps->freelist = ((struct free_obj*)p)->next;
if (mrb->free_heaps->freelist == NULL) {
unlink_free_heap_page(mrb, mrb->free_heaps);
}
mrb->live++;
gc_protect(mrb, p);
memset(p, 0, sizeof(RVALUE));
p->tt = ttype;
p->c = cls;
paint_partial_white(mrb, p);
return p;
}
}}
先頭で生存しているオブジェクトが閾値を超えていたらGCを行っています。その中身は後からじっくり見るので無視して先に進むとヒープ中のまだ使われていないオブジェクトを取り出しています。ここら辺のヒープの仕組みはCRubyと同じなので[[RHG>http://i.loveruby.net/ja/rhg/book/gc.html]]をご参照ください。（手抜き）
その後、オブジェクト生存数を増やしてオブジェクトの色を白に塗っています。
なお、その前にやっているgc_protect()の定義は以下のようになっています。
#code(C){{
void
mrb_gc_protect(mrb_state *mrb, mrb_value obj)
{
if (SPECIAL_CONST_P(obj)) return;
gc_protect(mrb, RBASIC(obj));
}
static void
gc_protect(mrb_state *mrb, struct RBasic *p)
{
if (mrb->arena_idx > MRB_ARENA_SIZE) {
/* arena overflow error */
mrb->arena_idx = MRB_ARENA_SIZE - 4; /* force room in arena */
mrb_raise(mrb, E_RUNTIME_ERROR, "arena overflow error");
}
mrb->arena[mrb->arena_idx++] = p;
}
}}
arenaという謎の変数が出現しました。この謎の変数についてはそのうち明らかになります。
*mrb_incremental_gc [#b4e49124]
さて、mrb_incremental_gc()に進みます。本物のコードは時間計測用のマクロが書かれていますが省いて載せます。
#code(C){{
void
mrb_incremental_gc(mrb_state *mrb)
{
size_t limit = 0, result = 0;
limit = (GC_STEP_SIZE/100) * mrb->gc_step_ratio;
while (result < limit) {
result += incremental_gc(mrb, limit);
if (mrb->gc_state == GC_STATE_NONE)
break;
}
if (mrb->gc_state == GC_STATE_NONE) {
gc_assert(mrb->live >= mrb->gc_live_after_mark);
mrb->gc_threshold = (mrb->gc_live_after_mark/100) * mrb->gc_interval_ratio;
if (mrb->gc_threshold < GC_STEP_SIZE) {
mrb->gc_threshold = GC_STEP_SIZE;
}
}
else {
mrb->gc_threshold = mrb->live + GC_STEP_SIZE;
}
}
}}
GC_STEP_SIZEは1024、gc_step_ratioのデフォルト値は200です。このことから一回のGCでは最大で2000個のオブジェクトが対象にされるんだろうなぁということがわかります。
関数の後半では生存オブジェクトの数に応じて次回GCを発動する閾値を更新しています。
*incremental_gc [#k7b2ec11]
ではincremental_gc()に進みましょう。
#code(C){{
static size_t
incremental_gc(mrb_state *mrb, size_t limit)
{
switch (mrb->gc_state) {
case GC_STATE_NONE:
root_scan_phase(mrb);
mrb->gc_state = GC_STATE_MARK;
flip_white_part(mrb);
return 0;
case GC_STATE_MARK:
if (mrb->gray_list) {
return incremental_marking_phase(mrb, limit);
}
else {
final_marking_phase(mrb);
prepare_incremental_sweep(mrb);
return 0;
}
case GC_STATE_SWEEP: {
size_t tried_sweep = 0;
tried_sweep = incremental_sweep_phase(mrb, limit);
if (tried_sweep == 0)
mrb->gc_state = GC_STATE_NONE;
return tried_sweep;
}
default:
/* unknown state */
gc_assert(0);
return 0;
}
}
}}
GCは三段階に分かれていることがわかります。
+ルートオブジェクトのマーキング
+灰色オブジェクトの子オブジェクトのマーキング
+マーキングされていない（白色オブジェクトの）スイープ
各段階について見ていきましょう。
*root_scan_phase(gc_state==GC_STATE_NONE) [#b43c2a2c]
まずルートオブジェクトを灰色にマーキングを行います。mrubyでは以下のオブジェクトがルートオブジェクトとして扱われています。
-グローバル変数
-arenaにあるオブジェクト
-Objectクラス
-レジスタスタック上のオブジェクト
-ensureブロック
-クロージャ（を構成するRProc, REnv, RClass）
-irepのpoolオブジェクト
root_scan_phase()は単調なので載せません。そこから呼ばれているmrb_gc_mark()だけ載せておきます。
#code(C){{
void
mrb_gc_mark(mrb_state *mrb, struct RBasic *obj)
{
if (obj == 0) return;
if (!is_white(obj)) return;
gc_assert(!is_dead(mrb, obj));
add_gray_list(mrb, obj);
}
}}
というわけですでに灰色か黒にマークされているオブジェクトは対象からはずれることがわかると思います。
*incremental_marking_phase(gc_state==GC_STATE_MARK) [#ied4d1e3]
次に灰色オブジェクトの子オブジェクトをマーキングします。
#code(C){{
static size_t
incremental_marking_phase(mrb_state *mrb, size_t limit)
{
size_t tried_marks = 0;
while (mrb->gray_list && tried_marks < limit) {
tried_marks += gc_gray_mark(mrb, mrb->gray_list);
}
return tried_marks;
}
}}
gc_gray_mark()では子オブジェクト((実はこの言い方は正確ではなくて、正しくはオブジェクトから参照されているオブジェクトです。例えば、オブジェクトのスーパークラスのオブジェクトなどがマーク対象になります))を灰色にマークした上でマークしたオブジェクトの数を返します((実際にはマークした後で改めて数を数えていますが、なんで分けてるんだろう？))。
この関数で注目対象となるのはlimit引数です。マークされたオブジェクトの数を数えることで一度のGCで一定以上の処理をしないでユーザプログラムに制御を返すということを実現しています。つまり、GC処理が呼ばれたからと言って常に参照されていないオブジェクトが解放されるわけではないということです。（それがインクリメンタルGCです）
*ところでこれどうやって動いてんの？ [#u2442e1b]
多分、ここまで読んでおいてけぼり感を感じている人もいると思います。そんな人のために解説、おいてけぼりって語源は妖怪から来てるんですよ。
ではなくて、まじめに解説します。わかりにくいのはmrb_incremental_gc()のここだと思います。
#code(C){{
while (result < limit) {
result += incremental_gc(mrb, limit);
if (mrb->gc_state == GC_STATE_NONE)
break;
}
}}
mrb_incremental_gc()が呼ばれた場合、スイープまで行われるときと途中で終わる場合があります。
例えば、前回のmrb_incremental_gc()が呼ばれてから4000個のオブジェクトが作られ、それらがどこからも参照されていない場合でも初めの2000個((gc_step_ratioがデフォルト値の場合))だけが解放されて残りの2000個は次にmrb_incremental_gcが呼ばれるまで解放されません。（whileの条件が成り立たなくなってループを抜けます）
逆に前回mrb_incremental_gc()が呼ばれてから100個しかオブジェクトが作成されなかった場合、一度のmrb_incremental_gc()で全部のオブジェクトが解放されます。（ifの条件が成り立ってループを抜けます）
*incremental_sweep_phase(gc_state==GC_STATE_NONE) [#o217155b]
さて、というわけでオブジェクトの解放を行うincremental_sweep_phase()に進みましょう。
#code(C){{
static size_t
incremental_sweep_phase(mrb_state *mrb, size_t limit)
{
struct heap_page *page = mrb->sweeps;
size_t tried_sweep = 0;
while (page && (tried_sweep < limit)) {
RVALUE *p = page->objects;
RVALUE *e = p + HEAP_PAGE_SIZE;
size_t freed = 0;
int dead_slot = 1;
int full = (page->freelist == NULL);
while (p<e) {
if (is_dead(mrb, &p->as.basic)) {
if (p->as.basic.tt != MRB_TT_FREE) {
obj_free(mrb, &p->as.basic);
p->as.free.next = page->freelist;
page->freelist = (struct RBasic*)p;
freed++;
}
}
else {
paint_partial_white(mrb, &p->as.basic); /* next gc target */
dead_slot = 0;
}
p++;
}
/* free dead slot */
if (dead_slot && freed < HEAP_PAGE_SIZE) {
struct heap_page *next = page->next;
unlink_heap_page(mrb, page);
unlink_free_heap_page(mrb, page);
mrb_free(mrb, page);
page = next;
}
else {
if (full && freed > 0) {
link_free_heap_page(mrb, page);
}
page = page->next;
}
tried_sweep += HEAP_PAGE_SIZE;
mrb->live -= freed;
mrb->gc_live_after_mark -= freed;
}
mrb->sweeps = page;
return tried_sweep;
}
}}
やっていることは以下の処理です。
+ヒープページの各オブジェクトを見て
+死んでいる（白色の）オブジェクトを解放
+生きている場合は色を白に塗り直し
+解放した分、生存数を減らし
+スキャンした数を加算し
+スキャンした数がlimitを超えたらループ終了
といった感じにインクリメンタルになっています。
*そういえばarenaの話はどこ行った？ [#h38660bc]
これまで見てきた中でarenaという謎の変数がありました。なんかアロケートしたオブジェクトのポインタを格納しているようだが何なんだ？この変数はというのが感想でしょう。さわだもその存在がよくわかりませんでした。
まず、第一に奇妙な点。include/mruby.h中のmrb_state.arenaの定義。
#code(C){{
#define MRB_ARENA_SIZE 1024 //256 up kusuda 2011/04/30
...
typedef struct mrb_state {
...
struct RBasic *arena[MRB_ARENA_SIZE];
...
} mrb_state;;
}}
え？mrubyって1024個しかオブジェクト使えないの？というのが率直な感想だと思いますがそんなことはありません。なので余計に謎な変数ということになります。
arenaを使っているところを探すとsrc/array.c中のinspect_ary()で使われていました。
#code(C){{
static mrb_value
inspect_ary(mrb_state *mrb, mrb_value ary, mrb_value list)
{
int i;
mrb_value s, arystr;
char head[] = { '[' };
char sep[] = { ',', ' ' };
char tail[] = { ']' };
/* check recursive */
for(i=0; i<RARRAY_LEN(list); i++) {
if (mrb_obj_equal(mrb, ary, RARRAY_PTR(list)[i])) {
return mrb_str_new(mrb, "[...]", 5);
}
}
mrb_ary_push(mrb, list, ary);
arystr = mrb_str_buf_new(mrb, 64);
mrb_str_buf_cat(mrb, arystr, head, sizeof(head));
for(i=0; i<RARRAY_LEN(ary); i++) {
int ai = mrb_gc_arena_save(mrb);
if (i > 0) {
mrb_str_buf_cat(mrb, arystr, sep, sizeof(sep));
}
if (mrb_type(RARRAY_PTR(ary)[i]) == MRB_TT_ARRAY) {
s = inspect_ary(mrb, RARRAY_PTR(ary)[i], list);
} else {
s = mrb_inspect(mrb, RARRAY_PTR(ary)[i]);
}
mrb_str_buf_cat(mrb, arystr, RSTRING_PTR(s), RSTRING_LEN(s));
mrb_gc_arena_restore(mrb, ai);
}
mrb_str_buf_cat(mrb, arystr, tail, sizeof(tail));
mrb_ary_pop(mrb, list);
return arystr;
}
}}
mrb_gc_arena_save()は現在のarena_idxの保存、mrb_gc_arena_restore()は保存したarena_idxの復元です。mrb_gc_arena_save()とmrb_gc_arena_restore()の間にはいくつかオブジェクトをアロケートしてそうな処理が入っているのでオブジェクト数の制限はCで書かれたメソッドに対してのみのものなようです。試しに上記の関数でmrb_gc_arena_restore()の呼び出しをコメントアウトして要素の多い配列をinspectしてみたら予想通りエラーになりました。
$ ./bin/mruby.exe -e 'class Foo; end; a = []; (1..10000).each do |i| a << Foo.new; end; p a'
RuntimeError: arena overflow error
さて次に、というわけでCで書かれたメソッドに対してarena_idxの調整が行われることがわかりました。自分が書くCメソッドは全部そんなことしないといけないの？と思われるかもしれませんがそんなことはありません。上記のinspect_ary()のように1関数中でオブジェクトを大量に生成する可能性のある場合のみ必要になります((ちなみに、2012/7/18に入った変更でMRB_ARENA_SIZEを-D指定できるようになりました))。arena_idxの設定と戻しはsrc/vm.c中のmrb_run()で行われてます。
mrb_run()の初めの方
#code(C){{
int ai = mrb->arena_idx;
}}
Cメソッドを呼ぶところ
#code(C){{
if (MRB_PROC_CFUNC_P(m)) {
mrb->stack[0] = m->body.func(mrb, recv);
mrb->arena_idx = ai;
}}
最後に、普通にVMの命令を実行している場合ってどうなってんの？という疑問の答えを示しておきましょう。ちょくちょくarena_idxが元に戻されるのであまり気にする必要はありません。((なお、「arena_idx戻しすぎじゃね？」という意見に反応されたのか、2012/7/31に入った変更でNEXT中でのarena_idx代入コードは削除されました))
#code(C){{
#define NEXT mrb->arena_idx = ai; i=*++pc; goto *optable[GET_OPCODE(i)]
}}
*おわりに [#t35fbd72]
というわけでmrubyのGC処理を見てきました。インクリメンタルGCが実装されており、CRubyでたまに問題となるGCで止まってしまうということはなさそうです。インクリメンタルGCは概念はわかっても実際コードを見るとどういう動きになるのかわかりにくいという問題があるように思いました。
また、arenaはかなり難解でした。ここら辺、ドキュメントがあるとうれしいなってことでこの読解記事が他のmrubyコードリーディングに挑む人の助けになれば幸いです。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
