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

2010-04-02
#gc #cplusplus

２度目のテスト（→１度目）。 今度は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_bitはnextの下位１ビットに埋め込むとかいうハックをすれば８バイトに減らせる。

オブジェクトを管理し、マークスイープ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は呼ばない。

使用のテスト：GCObjectとMarkSweepGCを継承して

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());
    }
};

関連記事

新着記事