Cycle-counting garbage collector

GC.cc

#include "GC.h"

#include <boost/foreach.hpp>


GCHeap::~GCHeap()
{
    fullCollect();
}


GCObject::~GCObject()
{
}


GCObject::GCObject()
{
    mGcRefCount = 0;
    mGcColour = GCHeap::gcInUseOrFree;
    mGcBuffered = 0;
}


void
GCObject::gcObjectIsAcyclic()
{
    mGcColour = GCHeap::gcAcyclic;
}


void
GCHeap::freeObject(GCObject* pObject)
{
    delete pObject;
}


void
GCHeap::release(GCObject* pObject)
{
    pObject->visitChildren(this, &GCHeap::decrement);
    pObject->mGcColour = gcInUseOrFree;
    if (!pObject->mGcBuffered)
    {
        freeObject(pObject);
    }
}


void
GCHeap::processIncDecBuffers()
{
    // Do increments
    BOOST_FOREACH(GCObject* obj, mIncBuffer)
    {
        ++obj->mGcRefCount;
        if (obj->mGcColour != gcAcyclic)
        {
            obj->mGcColour = gcInUseOrFree;
        }
    }

    StaticPodBuffer<GCObject*, sRootBufferHighwater> newRoots;

    // Do decrements
    BOOST_FOREACH(GCObject* obj, mDecBuffer)
    {
        --obj->mGcRefCount;
        if (obj->mGcColour == gcAcyclic)
        {
            // For acyclic objects, do the obvious thing.
            if (obj->mGcRefCount == 0)
            {
                release(obj);
            }
            continue;
        }

        if (obj->mGcRefCount == 0)
        {
            // This is garbage.
            obj->mGcColour = gcInUseOrFree;
        }
        else
        {
            // Possible root of a cycle.
            obj->mGcColour = gcPossibleCycleRoot;
        }

        // Either way, buffer the object.
        if (obj->mGcColour != gcAcyclic && !obj->mGcBuffered)
        {
            obj->mGcBuffered = 1;
            newRoots.push_back(obj);
        }
    }

    mIncBuffer.clear();
    mDecBuffer.clear();

    // Now, the root buffer contains no acyclic objects, and everything
    // there is either garbage or a possible cycle root.

    BOOST_FOREACH(GCObject* obj, newRoots)
    {
        if (obj->mGcRefCount == 0)
        {
            obj->mGcBuffered = 0;
            // The garbage case.
            release(obj);
        }
        else
        {
            // Possible root of a cycle.
            mCycleRoots.push_back(obj);
        }
    }
}


void
GCHeap::decrementAndMark(GCObject* pObject)
{
    if (pObject->mGcColour == gcAcyclic)
    {
        return;
    }
    --pObject->mGcRefCount;
    mark(pObject);
}


void
GCHeap::mark(GCObject* pObject)
{
    if (pObject->mGcColour != gcPossibleCycleMember)
    {
        pObject->mGcColour = gcPossibleCycleMember;
        pObject->visitChildren(this, &GCHeap::decrementAndMark);
    }
}


void
GCHeap::scanNonGarbage(GCObject* pObject)
{
    pObject->mGcColour = gcInUseOrFree;
    pObject->visitChildren(this, &GCHeap::incrementAndScan);
}


void
GCHeap::incrementAndScan(GCObject* pObject)
{
    if (pObject->mGcColour == gcAcyclic)
    {
        return;
    }
    ++pObject->mGcRefCount;
    if (pObject->mGcColour != gcInUseOrFree)
    {
        scanNonGarbage(pObject);
    }
}


void
GCHeap::scan(GCObject* pObject)
{
    if (pObject->mGcColour == gcPossibleCycleMember)
    {
        if (pObject->mGcRefCount > 0)
        {
            scanNonGarbage(pObject);
        }
        else
        {
            pObject->mGcColour = gcGarbageCycleMember;
            pObject->visitChildren(this, &GCHeap::scan);
        }
    }
}


void
GCHeap::reclaim(GCObject* pObject)
{
    if (pObject->mGcColour == gcGarbageCycleMember
        && !pObject->mGcBuffered)
    {
        pObject->mGcColour = gcInUseOrFree;
        pObject->visitChildren(this, &GCHeap::reclaim);
        freeObject(pObject);
    }
    if (pObject->mGcColour == gcAcyclic)
    {
        --pObject->mGcRefCount;
        if (pObject->mGcRefCount == 0)
        {
            release(pObject);
        }
    }
}


void
GCHeap::collectCycles()
{
    // Mark
    BOOST_FOREACH(GCObject* obj, mCycleRoots)
    {
        mark(obj);
    }

    // Scan
    BOOST_FOREACH(GCObject* obj, mCycleRoots)
    {
        scan(obj);
    }

    // Reclaim
    BOOST_FOREACH(GCObject* obj, mCycleRoots)
    {
        obj->mGcBuffered = 0;
        reclaim(obj);
    }

    mCycleRoots.clear();
}


void
GCHeap::partialCollect()
{
    processIncDecBuffers();

    // Only collect cycles if the root buffer is past the high water mark.
    if (mCycleRoots.size() >= sRootBufferHighwater)
    {
        collectCycles();
    }
}


void
GCHeap::fullCollect()
{
    processIncDecBuffers();
    collectCycles();
}

GC.h

#ifndef GC_HH_INCLUDED
#define GC_HH_INCLUDED

#ifndef STDLIB_H_INCLUDED
#include <stdlib.h>
#define STDLIB_H_INCLUDED
#endif

#ifndef STDINT_H_INCLUDED
#include <stdint.h>
#define STDINT_H_INCLUDED
#endif

#ifndef BOOST_UTILITY_HPP_INCLUDED
#include <boost/utility.hpp>
#define BOOST_UTILITY_HPP_INCLUDED
#endif

class GCHeap;
class GCObject;
class GCAcyclicObject;
template<typename T> class GCPtr; 

template<typename T, unsigned Size>
class StaticPodBuffer : private boost::noncopyable
{
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;

    typedef pointer iterator;
    typedef const_pointer const_iterator;

private:
    T mData[Size];
    T* mEnd;

public:
    StaticPodBuffer()
        : mEnd(mData)
    {
    }

    const_pointer begin() const
    {
        return mData;
    }

    pointer begin()
    {
        return mData;
    }

    const_pointer end() const
    {
        return mEnd;
    }

    pointer end()
    {
        return mEnd;
    }

    void push_back(const_reference pData)
    {
        *mEnd++ = pData;
    }

    void clear()
    {
        mEnd = mData;
    }

    size_t size() const
    {
        return mEnd - mData;
    }
};

class GCObject
{
private:
    friend class GCHeap;
    friend class GCAcyclicObject;

    uint32_t mGcRefCount : 28,
             mGcColour : 3,
             mGcBuffered : 1;

protected:
    virtual ~GCObject();

    GCObject();

    void gcObjectIsAcyclic();

public:
    virtual size_t size() const = 0;

    virtual void visitChildren(GCHeap* pHeap,
                               void (GCHeap::*pVisitor)(GCObject*)) = 0;
};


class GCAcyclicObject : public GCObject
{
public:
    GCAcyclicObject()
    {
        gcObjectIsAcyclic();
    }
};


class GCHeap
{
private:
    friend class GCObject;

    enum {
        sIncBufferSize = 1024,
        sIncBufferHighwater = 1024,
        sDecBufferSize = 1024,
        sDecBufferHighwater = 1024,
        sRootBufferSize = 16384,
        sRootBufferHighwater = 8192
    };

    StaticPodBuffer<GCObject*, sIncBufferSize> mIncBuffer;
    StaticPodBuffer<GCObject*, sDecBufferSize> mDecBuffer;
    StaticPodBuffer<GCObject*, sRootBufferSize> mCycleRoots;

    enum gc_colour_t {
        gcInUseOrFree = 0,	// black
        gcPossibleCycleMember,	// gray
        gcGarbageCycleMember,	// white
        gcPossibleCycleRoot,	// purple
        gcAcyclic 		// green
    };

    void release(GCObject* pObject);
    void freeObject(GCObject* pObject);

    void mark(GCObject* pObject);
    void decrementAndMark(GCObject* pObject);

    void scan(GCObject* pObject);
    void incrementAndScan(GCObject* pObject);
    void scanNonGarbage(GCObject* pObject);

    void reclaim(GCObject* pObject);

    void processIncDecBuffers();

    void collectCycles();

public:
    ~GCHeap();

    void increment(GCObject* pObject);

    void decrement(GCObject* pObject);

    void partialCollect();

    void fullCollect();

    template<typename T>
    GCPtr<T> make();

    template<typename T, typename Arg1>
    GCPtr<T> make(Arg1 const & arg1);

    template<typename T, typename Arg1, typename Arg2>
    GCPtr<T> make(Arg1 const & arg1, Arg2 const & arg2);
};


inline void
GCHeap::increment(GCObject* pObject)
{
    mIncBuffer.push_back(pObject);
    if (mIncBuffer.size() >= sIncBufferHighwater)
    {
        partialCollect();
    }
}


inline void
GCHeap::decrement(GCObject* pObject)
{
    mDecBuffer.push_back(pObject);
    if (mDecBuffer.size() >= sDecBufferHighwater)
    {
        partialCollect();
    }
}


struct GCPtrBase
{
    GCHeap* mHeap;
    GCObject* mObject;

    void acquire(GCHeap* pHeap, GCObject* pObject)
    {
        mHeap = pHeap;
        mObject = pObject;
        if (mObject)
        {
            mHeap->increment(mObject);
        }
    }

    void release()
    {
        if (mObject)
        {
            mHeap->decrement(mObject);
            mHeap = 0;
            mObject = 0;
        }
    }

    GCObject* move()
    {
        GCObject* ptr = mObject;
        mHeap = 0;
        mObject = 0;
        return ptr;
    }

    GCObject* copy()
    {
        if (mObject)
        {
            mHeap->increment(mObject);
        }
        return mObject;
    }

    GCPtrBase()
    {
        acquire(0, 0);
    }

    GCPtrBase(const GCPtrBase& pRhs)
    {
        acquire(pRhs.mHeap, pRhs.mObject);
    }

    GCPtrBase(GCHeap* pHeap, GCObject* pObject)
    {
        acquire(pHeap, pObject);
    }

    void swap(GCPtrBase& pRhs)
    {
        std::swap(mHeap, pRhs.mHeap);
        std::swap(mObject, pRhs.mObject);
    }

    void reset()
    {
        release();
    }

    ~GCPtrBase()
    {
        release();
    }
};


template<typename T>
class GCPtr : private GCPtrBase
{
public:
    GCPtr(GCHeap* pHeap, T* pObject)
        : GCPtrBase(pHeap, pObject)
    {
    }

    GCPtr(const GCPtr& pRhs)
        : GCPtrBase(pRhs)
    {
    }

    GCPtr()
    {
    }

    ~GCPtr()
    {
    }

    T* copy()
    {
        return static_cast<T*>(GCPtrBase::copy());
    }

    T* move()
    {
        return static_cast<T*>(GCPtrBase::move());
    }

    T& operator*() const
    {
        return *static_cast<T*>(mObject);
    }

    T* operator->() const
    {
        return static_cast<T*>(mObject);
    }

    T* get() const
    {
        return static_cast<T*>(mObject);
    }

    void swap(GCPtr<T>& pRhs)
    {
        GCPtrBase::swap(pRhs);
    }

    GCPtr<T>& operator=(GCPtr<T>& pRhs)
    {
        if (this != &pRhs)
        {
            release();
            acquire(pRhs);
        }
        return *this;
    }
};


template<typename T>
inline GCPtr<T>
GCHeap::make()
{
    return GCPtr<T>(this, new T());
}


template<typename T, typename Arg1>
inline GCPtr<T>
GCHeap::make(Arg1 const & arg1)
{
    return GCPtr<T>(this, new T(arg1));
}


template<typename T, typename Arg1, typename Arg2>
inline GCPtr<T>
GCHeap::make(Arg1 const & arg1, Arg2 const & arg2)
{
    return GCPtr<T>(this, new T(arg1, arg2));
}

#endif

testGC.cc

#include "GC.hh"
#include <iostream>
#include <vector>
#include <boost/foreach.hpp>


class GCInteger : public GCAcyclicObject
{
private:
    int mInt;

public:
    GCInteger(int pInt)
        : mInt(pInt)
    {
    }

    size_t size() const
    {
        return sizeof(*this);
    }

    void visitChildren(GCHeap* pHeap,
                       void (GCHeap::*pVisitor)(GCObject*))
    {
    }

    int value() const
    {
        return mInt;
    }

    ~GCInteger()
    {
    }
};


class GCArray : public GCObject
{
public:
    std::vector<GCObject*> mObjects;

    GCArray()
    {
    }

    size_t size() const
    {
        return sizeof(*this) + mObjects.size() * sizeof(GCObject*);
    }

    void visitChildren(GCHeap* pHeap,
                       void (GCHeap::*pVisitor)(GCObject*))
    {
        BOOST_FOREACH(GCObject* obj, mObjects)
        {
            (pHeap->*pVisitor)(obj);
        }
    }

    ~GCArray()
    {
    }
};


int
main()
{
    GCHeap heap;

    {
        GCPtr<GCArray> arrMaster(heap.make<GCArray>());
        {
            GCPtr<GCInteger> int42(heap.make<GCInteger>(42));
            GCPtr<GCInteger> int63(heap.make<GCInteger>(63));

            GCPtr<GCArray> arr1(heap.make<GCArray>());
            GCPtr<GCArray> arr2(heap.make<GCArray>());
            GCPtr<GCArray> arr3(heap.make<GCArray>());
            GCPtr<GCArray> arr4(heap.make<GCArray>());

            arrMaster->mObjects.push_back(arrMaster.copy());
            arrMaster->mObjects.push_back(arr1.copy());
            arrMaster->mObjects.push_back(arr2.copy());
            arrMaster->mObjects.push_back(arr3.copy());
            arrMaster->mObjects.push_back(arr4.copy());
            arrMaster->mObjects.push_back(int42.copy());

            arr1->mObjects.push_back(arr1.copy());
            arr1->mObjects.push_back(arr2.copy());
            arr1->mObjects.push_back(arr3.copy());
            arr1->mObjects.push_back(arr4.copy());
            arr1->mObjects.push_back(int63.copy());

            arr2->mObjects.push_back(arr1.copy());
            arr2->mObjects.push_back(arr2.copy());
            arr2->mObjects.push_back(arr3.copy());
            arr2->mObjects.push_back(arr4.copy());

            arr3->mObjects.push_back(arr1.copy());
            arr3->mObjects.push_back(arr2.copy());
            arr3->mObjects.push_back(arr3.copy());
            arr3->mObjects.push_back(arr4.copy());

            arr4->mObjects.push_back(arr1.copy());
            arr4->mObjects.push_back(arr2.copy());
            arr4->mObjects.push_back(arr3.copy());
            arr4->mObjects.push_back(arr4.copy());
        }
        heap.fullCollect();
    }
}