マークスイープGCのテスト2

2010-04-02

2度目のテスト(→1度目)。 今度はGC本見たからすっきりしたはず。

GC対象となるオブジェクトのベースクラス:

class GCObject {
GCObject* next;
bool mark_bit : 1;
public:
GCObject() { }
virtual ~GCObject() { }
virtual void mark() { this->mark_bit = true; }
protected:
bool marked() { return mark_bit; }
friend class MarkSweepGC;
};

作られたオブジェクトはスイープフェーズですべてをたどるために、単方向リストでつなぐためのメンバnextと、マークビットのメンバmark_bitを持つ。 継承するオブジェクトが内部にGCObjectを指すメンバを持つ場合は mark() メソッドをオーバーライドしてそれらもマークするようにする。 構造体のサイズはvtbl(4)+next(4)+mark_bit(4) = 12。 デカい…。 mark_bitnextの下位1ビットに埋め込むとかいうハックをすれば8バイトに減らせる。

オブジェクトを管理し、マークスイープGCするクラス:

class MarkSweepGC {
GCObject* chain;
public:
MarkSweepGC() : chain(NULL) { }
void collect_garbage() {
this->mark_phase();
this->sweep_phase();
}
protected:
GCObject* alloc_object(size_t size) {
GCObject* p = static_cast<GCObject*>(malloc(size));
if (p == NULL) {
this->collect_garbage();
p = static_cast<GCObject*>(malloc(size));
if (p == NULL) {
error_exit("Out of memory");
}
}
p->mark_bit = false;
p->next = this->chain;
this->chain = p;
return p;
}
void free_object(GCObject* p) {
free(p);
}

virtual void mark_phase() = 0;
void sweep_phase() {
GCObject* prev = NULL;
for (GCObject* p = this->chain; p != NULL; ) {
if (p->mark_bit) {
p->mark_bit = false;
prev = p;
p = p->next;
} else {
GCObject* next = p->next;
if (prev == NULL) this->chain = next;
else prev->next = next;
p->~GCObject();
free_object(p);
p = next;
}
}
}
};

GCするオブジェクトは alloc_object() メソッドで確保する。 そのため直接newは呼ばずに、確保したメモリ領域にplacement newでコンストラクタを呼び出す。 作られたオブジェクトはすべてchainにつながれる。

GCの開始にはcollect_garbage()を呼びだすか、allocate_object()内でメモリ確保に失敗すると呼び出される。 mark_phase()は継承先で独自に実装して、ルートからたどれるGCObjectをマークする必要がある。 sweep_phase() は共通で、全オブジェクトを順にたどっていって、マークされてたら削除しないでマークをはずし、マークされてなかたら削除する。 placement newを使って確保したオブジェクトなので、直接deleteは呼ばない。

使用のテスト:GCObjectMarkSweepGCを継承して

class Value : public GCObject {
Value* child;
public:
Value() : GCObject(), child(NULL) { }
virtual void mark() { if (this->child != NULL) this->child->mark(); }
};

class Context : public MarkSweepGC {
map<const string, Value*> buf;
public:
void alloc(const string& key) {
Value* p = new(alloc_object(sizeof(*p))) Value(); // placement new
this->buf[key] = p;
}
void remove(const string& key) {
this->buf.erase(this->buf.find(key));
}
virtual void mark_phase() {
struct Functor {
void operator ()(map<string, Value*>::value_type& e) { if (e.second != NULL) e.second->mark(); }
};
for_each(this->buf.begin(), this->buf.end(), Functor());
}
};