ConservativeGCとは何か

RHGに見るとこうある

そこで、まずその数値がVALUEであるか(ポインタであるか)どうか調べてみて、それらしく見えるならば全てポインタとして扱うことにする。
このような手法を「保守的GC(conservative GC)」と呼ぶ。「とりあえず安全側に倒す」というところが保守的だということらしい。 

第5章 ガ−ベージコレクション
 
レジスタや関数スタック内に数値があるとポインタと区別がつかない。
とあるが、それは具体的にどういう事か。
私は頭が悪い子なのでミニマムなプログラムを作って試してみる。
 
以下は関数スタック内を覗いて、printfしたという簡単なお仕事。
たったの70行くらい

#include <stdio.h>
#include <stdlib.h>

int *stack_top, *stack_end;
int *heap_bottom, *heap_top;

//簡易版
int
is_pointer_to_heap(int *ptr)
{
    if(ptr < heap_bottom || ptr > heap_top) return 0;
    return 1;
}

//関数スタックをprintfしてるだけ
int
stack_look(void)
{
    int end = 5;
    int *tmp;
    stack_end = &end;

    printf("stack start = %p : stack_end = %p : under_grow? = %d \n\n", stack_top, stack_end, stack_top > stack_end);
    if (stack_top > stack_end) {
	tmp = stack_top;
	stack_top = stack_end;
	stack_end = tmp;
    }
    tmp = stack_top;
    while(tmp < stack_end) {
	printf("stack look = %p : is_pointer_to_heap? = %d\n", *tmp, is_pointer_to_heap((int *)*tmp));
	tmp++;
    }
}

//関数スタックにローカル変数とか溜めたかったので
int
stack_tmp(int i)
{
    long j = 0x804a008;  //これが数値(1)
    int *m;

    m = heap_bottom + 1; //これはHeap内をしようしてる箇所
    printf("pointer(VALUE if ruby) = %p\n\n", m);
    stack_look();

    // for optimaze
    i += j;
    *m = i;
    return *m;
}

//擬似的なHeap領域を作り出す
//まぁ違う言語のHeap領域だとでも思って
void
init_heap(void)
{
    heap_bottom = malloc(sizeof(int) * 10000);
    heap_top = heap_bottom + 1000;
    printf("heap_bottom = %p : heap_top = %p\n\n", heap_bottom, heap_top);
}

int
main(void) {
    int start = 0;
    stack_top = &start;
    init_heap();
    return stack_tmp(10);
}

 
出力はこうなった

heap_bottom = 0x804a008 : heap_top = 0x804afa8 //Heapの範囲

pointer(VALUE if ruby) = 0x804a00c //Rubyでいう所のVALUE

stack start = 0xbfd6f320 : stack_end = 0xbfd6f2e4 : under_grow? = 1 //関数スタックの始まりと終わり、あとは下に進むのかとか

stack look = 0x5 : is_pointer_to_heap = 0
stack look = 0xbfd6f308 : is_pointer_to_heap = 0
stack look = 0x80484ba : is_pointer_to_heap = 0
stack look = 0x8048673 : is_pointer_to_heap = 0
stack look = 0x804a00c : is_pointer_to_heap = 1
stack look = 0x804afa8 : is_pointer_to_heap = 1
stack look = 0xb7e151ae : is_pointer_to_heap = 0
stack look = 0x804a00c : is_pointer_to_heap = 1   //これが本当のポインタ
stack look = 0x804a008 : is_pointer_to_heap = 1   //これが実際には数値だがポインタと区別がつかないもの (1)
stack look = 0xbfd6f328 : is_pointer_to_heap = 0
stack look = 0x8048547 : is_pointer_to_heap = 0
stack look = 0xa : is_pointer_to_heap = 0
stack look = 0x80497a4 : is_pointer_to_heap = 0
stack look = 0xbfd6f338 : is_pointer_to_heap = 0
stack look = 0x8048579 : is_pointer_to_heap = 0

(1)の部分がheap内にはいっているポインタだと判断されている、が実際は数値である。
保守的GCは「とりあえず安全面に倒す」為、現在使用されているポインタという事にする。
 
レジスタも同じ理由で「安全面に(ry」の必要が生じる。
 
これがConservativeGCという事になる。
(あってるかなぁ。。。)
 
これがあるとCopyingGCとか作れない。
なぜかというと、ポインタを書き換えたと思っても数値を書き換える可能性があるから。
 
でも、Mostly-CopyingGC(可能なところだけCopying)というものがあって、
レジスタや関数スタックの様な数値が入る可能性のあるところは動かさずに、
確実にポインタだというもの。つまり、Object内から伸びているポインタなど
を移動するアルゴリズムも存在する。
 
何か最後は暴走ぎみですね。。。失礼。
 
ところで、ConservativeGCの反対にあるExactGCはみんな知ってると思うが、
その具体的な手法を知ってる方は意外と少ないはず。
いつかRubiniusの手法とか紹介したいな。