mruby/GC処理を読む
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[mrubyを読む]]
#contents
*はじめに [#d2829603]
今回はmrubyのGC周りを読みます。なお、対象としたバージョン...
*mrubyで用いられているGC [#q7672c7c]
いきなりソースに入る前にmrubyではどのようなGCが行われてい...
説明によるとmrubyで使っているGCは「3色インクリメンタルGC...
:白|マークされていない。アロケート直後はこの色
:灰色|自身はマークされているが子オブジェクトはマークされ...
:黒|自身も子オブジェクトもマークされている
マークというのはCRubyでおなじみマーク & スイープのマーク...
また、白については正確には白Aと白Bがあり、アロケートされ...
なお、一回のGCでどれだけGCするかをRubyレベルで設定するこ...
インクリメンタルGC、その他いろんなGCについて詳しく知りた...
*mrb_obj_alloc [#ac6b4a26]
ではまずオブジェクトをアロケートするmrb_obj_alloc()から見...
#code(C){{
struct RBasic*
mrb_obj_alloc(mrb_state *mrb, enum mrb_vtype ttype, struc...
{
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を行...
その後、オブジェクト生存数を増やしてオブジェクトの色を白...
なお、その前にやっている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...
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) * m...
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を発動す...
*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()は単調なので載せません。そこから呼ばれて...
#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) [#ied...
次に灰色オブジェクトの子オブジェクトをマーキングします。
#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引数です。マークされたオ...
*ところでこれどうやって動いてんの？ [#u2442e1b]
多分、ここまで読んでおいてけぼり感を感じている人もいると...
ではなくて、まじめに解説します。わかりにくいのはmrb_incre...
#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個の...
逆に前回mrb_incremental_gc()が呼ばれてから100個しかオブジ...
*incremental_sweep_phase(gc_state==GC_STATE_NONE) [#o2171...
さて、というわけでオブジェクトの解放を行うincremental_swe...
#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 g...
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;
}
}}
やっていることは以下の処理です。
+ヒープページの各オブジェクトを見て
+死んでいる（白色の）オブジェクトを解放
+生きている場合は色を白に塗り直し((最近のmrubyでは世代別G...
+解放した分、生存数を減らし
+スキャンした数を加算し
+スキャンした数が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_...
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_...
$ ./bin/mruby.exe -e 'class Foo; end; a = []; (1..10000)...
RuntimeError: arena overflow error
さて次に、というわけでCで書かれたメソッドに対してarena_id...
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の命令を実行している場合ってどうなってん...
#code(C){{
#define NEXT mrb->arena_idx = ai; i=*++pc; goto *optable[...
}}
*おわりに [#t35fbd72]
というわけでmrubyのGC処理を見てきました。インクリメンタル...
また、arenaはかなり難解でした。ここら辺、ドキュメントがあ...
終了行:
[[mrubyを読む]]
#contents
*はじめに [#d2829603]
今回はmrubyのGC周りを読みます。なお、対象としたバージョン...
*mrubyで用いられているGC [#q7672c7c]
いきなりソースに入る前にmrubyではどのようなGCが行われてい...
説明によるとmrubyで使っているGCは「3色インクリメンタルGC...
:白|マークされていない。アロケート直後はこの色
:灰色|自身はマークされているが子オブジェクトはマークされ...
:黒|自身も子オブジェクトもマークされている
マークというのはCRubyでおなじみマーク & スイープのマーク...
また、白については正確には白Aと白Bがあり、アロケートされ...
なお、一回のGCでどれだけGCするかをRubyレベルで設定するこ...
インクリメンタルGC、その他いろんなGCについて詳しく知りた...
*mrb_obj_alloc [#ac6b4a26]
ではまずオブジェクトをアロケートするmrb_obj_alloc()から見...
#code(C){{
struct RBasic*
mrb_obj_alloc(mrb_state *mrb, enum mrb_vtype ttype, struc...
{
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を行...
その後、オブジェクト生存数を増やしてオブジェクトの色を白...
なお、その前にやっている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...
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) * m...
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を発動す...
*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()は単調なので載せません。そこから呼ばれて...
#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) [#ied...
次に灰色オブジェクトの子オブジェクトをマーキングします。
#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引数です。マークされたオ...
*ところでこれどうやって動いてんの？ [#u2442e1b]
多分、ここまで読んでおいてけぼり感を感じている人もいると...
ではなくて、まじめに解説します。わかりにくいのはmrb_incre...
#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個の...
逆に前回mrb_incremental_gc()が呼ばれてから100個しかオブジ...
*incremental_sweep_phase(gc_state==GC_STATE_NONE) [#o2171...
さて、というわけでオブジェクトの解放を行うincremental_swe...
#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 g...
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;
}
}}
やっていることは以下の処理です。
+ヒープページの各オブジェクトを見て
+死んでいる（白色の）オブジェクトを解放
+生きている場合は色を白に塗り直し((最近のmrubyでは世代別G...
+解放した分、生存数を減らし
+スキャンした数を加算し
+スキャンした数が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_...
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_...
$ ./bin/mruby.exe -e 'class Foo; end; a = []; (1..10000)...
RuntimeError: arena overflow error
さて次に、というわけでCで書かれたメソッドに対してarena_id...
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の命令を実行している場合ってどうなってん...
#code(C){{
#define NEXT mrb->arena_idx = ai; i=*++pc; goto *optable[...
}}
*おわりに [#t35fbd72]
というわけでmrubyのGC処理を見てきました。インクリメンタル...
また、arenaはかなり難解でした。ここら辺、ドキュメントがあ...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
