[boost] library proposal: garbage collection

From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2006-01-08 20:37:21

Dear boost developers,

the following proposal is about a small library for multithreaded garbage 
collection using only boost threads.

The major issues for a garbage collection system in C++ are the following:

1) knowing the root set of pointers.
2) knowing which objects are garbage collected.
3) performance of the collector in relation to multithreading.
4) the garbage collection algorithm.

I believe it is possible to make a garbage collection system using standard 
C++ and boost threads only. The following paragraphs analyse the issues and 
the proposed solutions.

--------------------------------------------------------------------------------------------------------
1) knowing the root set of pointers.

The root set of pointers is composed of:

a) the set of global pointers of the main thread.
b) the set of pointers allocated on the stack of each thread.

Since it is not possible to know where the stack of each thread is without 
using low-level non-portable techniques, I propose the following:

a) each garbage-collected thread shall have its own pointer stack allocated 
as thread-local-storage. The size of the pointer stack shall be analogous to 
the size of the hardware stack for the size of pointer of the machine.

b) a special pointer class will: 1) push itself in the current thread's 
pointer stack mentioned above, on construction and 2) pop itself from the 
current thread's pointer stack, on destruction.

The above solution makes it possible to:

a) know exactly where root pointers are: in the pointer stack of a 
garbage-collected thread.
b) be quite fast, since there is not going to be any synchronization: each 
thread will take care of its own pointer stack.

--------------------------------------------------------------------------------------------------------
2) knowing which objects are garbage collected.

The usual approach to knowing which objects are garbage-collected is to add 
each garbage-collected object to a global list of objects. But that solution 
is slower than what it could be, since access to the global list of objects 
must be serialized for all active threads.

My proposal is to have one thread-specific linked list of garbage collected 
objects; a special object class will provide 'operator new' that adds the 
allocated block to a thread-specific linked list of garbage collected 
objects. This class will also provide 'operator delete', in order to have 
manual object deallocation as well as automatic one.

--------------------------------------------------------------------------------------------------------
3) performance of the collector in relation to multithreading.

Since my proposal utilises thread local storage, there is no serialization 
penalty; therefore, the system can have as many threads as needed, without 
impact on performance.

--------------------------------------------------------------------------------------------------------
4) the garbage collection algorithm.

My proposal for the garbage collection algorithm is the following:

step 1: suspend all known garbage collected threads, except the current one.
step 2: traverse the root set of pointers of all known threads; mark 
reachable objects.
step 3: delete unreachable objects.
step 4: resume all previously suspended threads.

The algorithm should be invoked from inside 'operator new' when the amount 
of allocated memory exceeds a user-defined limit.

I propose a simple stop-the-world, then mark-and-sweep algorithm for the 
following reasons:

a) it is easy to implement.
b) it does not require access to the platform-specific stuff.

--------------------------------------------------------------------------------------------------------
In this section I present the proposed solution in the form of C++ code 
mixed with pseudo-code and comments, in order to understand the proposal 
better.

class gc_thread : public boost::thread {
public:
    gc_thread() {
        allocate thread-specific pointer stack
        allocate thread-specific object list
        place the thread-specific object list in a global list of object 
lists
        add thread in the global list of garbage-collected threads
    }

    ~gc_thread() {
        delete the thread-specific pointer stack
    }
};

template <class T> class gc_ptr {
public:
    gc_ptr() {
        push this pointer to the current thread's pointer stack
    }

    gc_ptr(const gc_ptr<T> &ptr) {
        push this pointer to the current thread's pointer stack
    }

    ~gc_ptr() {
        pop this pointer from the current thread's pointer stack
    }
};

class gc_object {
public:
    virtual ~gc_object() {
    }

    void *operator new(size_t size) {
        if (gc_memory_size > gc_max_memory_size) collect_garbage();
        block *result = ::operator new(size + sizeof(block));
        block->iterator = insert new block in the current thread's list of 
objects
        block->size = size;
        return result;
    }

    void operator delete(void *ptr) {
        erase iterator of block from current thread's list of objects
        if the current thread's list of objects is orphan (i.e. the thread 
has finished) and the list is empty, delete the list
        ::operator delete(ptr);
    }

    static void collect_garbage() {
        suspend all garbage-collected threads (except this)

        //change the mark flag in order to catch unreachable objects
        gc_mark = !gc_mark;

        //mark phase
        for each pointer stack S of each garbage-collected thread {
            for each pointer P in S {
                if P != null {
                    mark(P);
                }
            }
        }

        //sweep phase
        for each block B of each object list of each garbage collected 
thread {
            if (B.mark != gc_mark) delete B;
        }

        resume all garbage collected threads (except this)
    }

private:
    struct block {
        block_iterator it;
        size_t size;
        bool mark;
    };

    static bool gc_mark = false;
    static size_t gc_memory_size = 0;
    static size_t gc_max_memory_size = GC_DEFAULT_MEMORY_SIZE;

    static void mark(block *b) {
        if (b->mark == gc_mark) return; //block already marked
        b->mark = gc_mark;
        for each pointer P in block {
            if P is pointer then {
                mark(p);
            }
        }
    }
};

--------------------------------------------------------------------------------------------------------
Thank you for your attention.

Achilleas Margaritis