Ruby GC実装の歴史/Ruby2.0のGCを読む
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[Ruby GC実装の歴史を読む]]
#contents
*はじめに [#aa2fd836]
Ruby 2.0ではビットマップマーキングが導入されました。[[る...
*rb_newobj() [#ibc63795]
まずはとっかかりとしてrb_newobj()を見てみましょう。
以下のようになっています。
#code(C){{
if (UNLIKELY(!has_free_object)) {
if (!gc_prepare_free_objects(objspace)) {
during_gc = 0;
rb_memerror();
}
}
obj = (VALUE)objspace->heap.free_slots->freelist;
objspace->heap.free_slots->freelist = RANY(obj)->as.f...
if (objspace->heap.free_slots->freelist == NULL) {
unlink_free_heap_slot(objspace, objspace->heap.fr...
}
}}
#code(C){{
#define has_free_object (objspace->heap.free_slots && obj...
}}
一方、1.9.3の対応部分。
#code(C){{
if (UNLIKELY(!freelist)) {
if (!gc_lazy_sweep(objspace)) {
during_gc = 0;
rb_memerror();
}
}
obj = (VALUE)freelist;
freelist = freelist->as.free.next;
}}
#code(C){{
#define freelist objspace->heap.freelist
}}
似ていますが変わっています。全体のfreelistではなく個別（...
*heaps_slot構造体 [#h02933b0]
ではheaps_slot構造体を見てみましょう。
#code(C){{
struct heaps_slot {
struct heaps_header *header;
uintptr_t *bits;
RVALUE *freelist;
struct heaps_slot *next;
struct heaps_slot *prev;
struct heaps_slot *free_next;
};
struct heaps_header {
struct heaps_slot *base;
uintptr_t *bits;
RVALUE *start;
RVALUE *end;
size_t limit;
};
}}
同1.9.3。
#code(C){{
struct heaps_slot {
void *membase;
RVALUE *slot;
size_t limit;
struct heaps_slot *next;
struct heaps_slot *prev;
};
}}
heaps_header構造体（へのポインタ）、bits、先ほどのheaps_s...
*assign_heap_slot() [#nc4c0637]
新しく出てきたheaps_header構造体は謎のままheaps_slot構造...
#code(C){{
// ヒープとheaps_slotの確保
p = (RVALUE*)aligned_malloc(HEAP_ALIGN, HEAP_SIZE);
slot = (struct heaps_slot *)malloc(sizeof(struct heap...
slot->next = heaps;
if (heaps) heaps->prev = slot;
heaps = slot;
// ヒープの先頭をheaps_headerとして使うためにオフセット
membase = p;
p = (RVALUE*)((VALUE)p + sizeof(struct heaps_header));
// 参照設定
heaps->header = (struct heaps_header *)membase;
objspace->heap.sorted[hi] = heaps->header;
objspace->heap.sorted[hi]->start = p;
objspace->heap.sorted[hi]->end = (p + objs);
objspace->heap.sorted[hi]->base = heaps;
objspace->heap.sorted[hi]->limit = objs;
// 確保したヒープのビットマップ初期化
heaps->bits = (uintptr_t *)objspace->heap.free_bitmap;
objspace->heap.sorted[hi]->bits = (uintptr_t *)objspa...
objspace->heap.free_bitmap = objspace->heap.free_bitm...
memset(heaps->bits, 0, HEAP_BITMAP_LIMIT * sizeof(uin...
}}
どうやら確保したヒープの先頭をheaps_headerとして使ってい...
*gc_prepare_free_objects() [#c444e18f]
それではheaps_slot構造体の変更を眺めたところでGC部分を眺...
*gc_mark() [#x6d2eac3]
オブジェクトをマークしていく流れは1.9.3から変更はありませ...
#code(C){{
static void
gc_mark(rb_objspace_t *objspace, VALUE ptr)
{
if (!markable_object_p(objspace, ptr)) {
return;
}
if (LIKELY(objspace->mark_func_data == 0)) {
if (!gc_mark_ptr(objspace, ptr)) return; /* alrea...
push_mark_stack(&objspace->mark_stack, ptr);
}
else {
objspace->mark_func_data->mark_func(ptr, objspace...
}
}
}}
mark_func_dataとかはほっておいてgc_mark_ptr()に進みましょ...
#code(C){{
static int
gc_mark_ptr(rb_objspace_t *objspace, VALUE ptr)
{
register uintptr_t *bits = GET_HEAP_BITMAP(ptr);
if (MARKED_IN_BITMAP(bits, ptr)) return 0;
MARK_IN_BITMAP(bits, ptr);
objspace->heap.marked_num++;
return 1;
}
}}
ビットマップ来ました:-)。さて、GET_HEAP_BITMAPマクロが何...
#code(C){{
#define HEAP_HEADER(p) ((struct heaps_header *)(p))
#define GET_HEAP_HEADER(x) (HEAP_HEADER((uintptr_t)(x) & ...
#define GET_HEAP_BITMAP(x) (GET_HEAP_HEADER(x)->bits)
#define HEAP_ALIGN_LOG 14
enum {
HEAP_ALIGN = (1UL << HEAP_ALIGN_LOG),
HEAP_ALIGN_MASK = (~(~0UL << HEAP_ALIGN_LOG)),
}}
・・・(´・ω・｀)？ptrってVALUEでRVALUE構造体指しててその...
#code(C){{
p = (RVALUE*)aligned_malloc(HEAP_ALIGN, HEAP_SIZE);
}}
aligned_mallocはプラットフォーム対応でいろいろやっていま...
#code(C){{
#define GET_HEAP_HEADER(x) (HEAP_HEADER((uintptr_t)(x) & ...
}}
とすると確保したヒープの先頭アドレスが取り出せるというか...
*slot_sweep() [#b451618a]
オブジェクトのマーキングが終わったらlazy_sweep()→slot_swe...
*Copy on Write対策の考察 [#wcba51e4]
さて、というわけで2.0から導入されたビットマップマーキング...
マークではオブジェクトのヘッダフィールド上のFL_MARKフラ...
その後、すべてのオブジェクトをもう一度走査して、すべての...
これの問題点は、CoWのセマンティクスを破壊することだ: マ...
そう、1.9.3までのGCは''すべてのオブジェクトにFL_MARKして...
Bitmap Markingアルゴリズムの良い点は以下のとおりです。
- ビットマップは、オブジェクトヘッダにマークビットを置...
- 高い局所性
- マークはオブジェクトを変更しない。そして、スイープは...
- CoW friendly, ダーティキャッシュラインが少ない
となったことでオブジェクトごとにフラグを立てることなく、G...
後、見返すまで忘れていましたがfreelistをheaps_slotごとに...
*おわりに [#te72bdb5]
今回はRuby 2.0から導入されたGCのビットマップマーキングに...
終了行:
[[Ruby GC実装の歴史を読む]]
#contents
*はじめに [#aa2fd836]
Ruby 2.0ではビットマップマーキングが導入されました。[[る...
*rb_newobj() [#ibc63795]
まずはとっかかりとしてrb_newobj()を見てみましょう。
以下のようになっています。
#code(C){{
if (UNLIKELY(!has_free_object)) {
if (!gc_prepare_free_objects(objspace)) {
during_gc = 0;
rb_memerror();
}
}
obj = (VALUE)objspace->heap.free_slots->freelist;
objspace->heap.free_slots->freelist = RANY(obj)->as.f...
if (objspace->heap.free_slots->freelist == NULL) {
unlink_free_heap_slot(objspace, objspace->heap.fr...
}
}}
#code(C){{
#define has_free_object (objspace->heap.free_slots && obj...
}}
一方、1.9.3の対応部分。
#code(C){{
if (UNLIKELY(!freelist)) {
if (!gc_lazy_sweep(objspace)) {
during_gc = 0;
rb_memerror();
}
}
obj = (VALUE)freelist;
freelist = freelist->as.free.next;
}}
#code(C){{
#define freelist objspace->heap.freelist
}}
似ていますが変わっています。全体のfreelistではなく個別（...
*heaps_slot構造体 [#h02933b0]
ではheaps_slot構造体を見てみましょう。
#code(C){{
struct heaps_slot {
struct heaps_header *header;
uintptr_t *bits;
RVALUE *freelist;
struct heaps_slot *next;
struct heaps_slot *prev;
struct heaps_slot *free_next;
};
struct heaps_header {
struct heaps_slot *base;
uintptr_t *bits;
RVALUE *start;
RVALUE *end;
size_t limit;
};
}}
同1.9.3。
#code(C){{
struct heaps_slot {
void *membase;
RVALUE *slot;
size_t limit;
struct heaps_slot *next;
struct heaps_slot *prev;
};
}}
heaps_header構造体（へのポインタ）、bits、先ほどのheaps_s...
*assign_heap_slot() [#nc4c0637]
新しく出てきたheaps_header構造体は謎のままheaps_slot構造...
#code(C){{
// ヒープとheaps_slotの確保
p = (RVALUE*)aligned_malloc(HEAP_ALIGN, HEAP_SIZE);
slot = (struct heaps_slot *)malloc(sizeof(struct heap...
slot->next = heaps;
if (heaps) heaps->prev = slot;
heaps = slot;
// ヒープの先頭をheaps_headerとして使うためにオフセット
membase = p;
p = (RVALUE*)((VALUE)p + sizeof(struct heaps_header));
// 参照設定
heaps->header = (struct heaps_header *)membase;
objspace->heap.sorted[hi] = heaps->header;
objspace->heap.sorted[hi]->start = p;
objspace->heap.sorted[hi]->end = (p + objs);
objspace->heap.sorted[hi]->base = heaps;
objspace->heap.sorted[hi]->limit = objs;
// 確保したヒープのビットマップ初期化
heaps->bits = (uintptr_t *)objspace->heap.free_bitmap;
objspace->heap.sorted[hi]->bits = (uintptr_t *)objspa...
objspace->heap.free_bitmap = objspace->heap.free_bitm...
memset(heaps->bits, 0, HEAP_BITMAP_LIMIT * sizeof(uin...
}}
どうやら確保したヒープの先頭をheaps_headerとして使ってい...
*gc_prepare_free_objects() [#c444e18f]
それではheaps_slot構造体の変更を眺めたところでGC部分を眺...
*gc_mark() [#x6d2eac3]
オブジェクトをマークしていく流れは1.9.3から変更はありませ...
#code(C){{
static void
gc_mark(rb_objspace_t *objspace, VALUE ptr)
{
if (!markable_object_p(objspace, ptr)) {
return;
}
if (LIKELY(objspace->mark_func_data == 0)) {
if (!gc_mark_ptr(objspace, ptr)) return; /* alrea...
push_mark_stack(&objspace->mark_stack, ptr);
}
else {
objspace->mark_func_data->mark_func(ptr, objspace...
}
}
}}
mark_func_dataとかはほっておいてgc_mark_ptr()に進みましょ...
#code(C){{
static int
gc_mark_ptr(rb_objspace_t *objspace, VALUE ptr)
{
register uintptr_t *bits = GET_HEAP_BITMAP(ptr);
if (MARKED_IN_BITMAP(bits, ptr)) return 0;
MARK_IN_BITMAP(bits, ptr);
objspace->heap.marked_num++;
return 1;
}
}}
ビットマップ来ました:-)。さて、GET_HEAP_BITMAPマクロが何...
#code(C){{
#define HEAP_HEADER(p) ((struct heaps_header *)(p))
#define GET_HEAP_HEADER(x) (HEAP_HEADER((uintptr_t)(x) & ...
#define GET_HEAP_BITMAP(x) (GET_HEAP_HEADER(x)->bits)
#define HEAP_ALIGN_LOG 14
enum {
HEAP_ALIGN = (1UL << HEAP_ALIGN_LOG),
HEAP_ALIGN_MASK = (~(~0UL << HEAP_ALIGN_LOG)),
}}
・・・(´・ω・｀)？ptrってVALUEでRVALUE構造体指しててその...
#code(C){{
p = (RVALUE*)aligned_malloc(HEAP_ALIGN, HEAP_SIZE);
}}
aligned_mallocはプラットフォーム対応でいろいろやっていま...
#code(C){{
#define GET_HEAP_HEADER(x) (HEAP_HEADER((uintptr_t)(x) & ...
}}
とすると確保したヒープの先頭アドレスが取り出せるというか...
*slot_sweep() [#b451618a]
オブジェクトのマーキングが終わったらlazy_sweep()→slot_swe...
*Copy on Write対策の考察 [#wcba51e4]
さて、というわけで2.0から導入されたビットマップマーキング...
マークではオブジェクトのヘッダフィールド上のFL_MARKフラ...
その後、すべてのオブジェクトをもう一度走査して、すべての...
これの問題点は、CoWのセマンティクスを破壊することだ: マ...
そう、1.9.3までのGCは''すべてのオブジェクトにFL_MARKして...
Bitmap Markingアルゴリズムの良い点は以下のとおりです。
- ビットマップは、オブジェクトヘッダにマークビットを置...
- 高い局所性
- マークはオブジェクトを変更しない。そして、スイープは...
- CoW friendly, ダーティキャッシュラインが少ない
となったことでオブジェクトごとにフラグを立てることなく、G...
後、見返すまで忘れていましたがfreelistをheaps_slotごとに...
*おわりに [#te72bdb5]
今回はRuby 2.0から導入されたGCのビットマップマーキングに...
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
