How is (dynamic) memory traversed by a garbage collector?

Question

I've read about the different kinds of GC and how they work. All involve traversing the set of memory which might potentially be reclaimed, but nothing I've read gives any indication as to how this is actually done. Would something like the following be way off the mark?

void* myAlloc(size_t size)
{
    if (needToGc())
        gc();
    void* obj = malloc(size);
    if (!obj)
        outOfMemory(); // or maybe GC and try once more
    *alloced = obj;
    *alloced = *alloced + 1;
    return obj;
}
void gc()
{
    // go through memory pointed to in `alloced`
}

I suspect so, but it's the only thing that's come to mind...

Answer 1

There is a lot of variety in garbage collectors, depending on requirements (memory overhead, latency, data layout, …). Some of my answer may not apply to some sophisticated collectors.

First, there is no need for needToGc: the garbage collector is triggerred if malloc fails.

As to how memory is traversed, the garbage collector's task is to separate memory that's in use from memory that's not in use, and reclaim the latter. The basic principle is that memory is in use if it is reachable from the program. This is determined as follows:

• Some root objects are deemed reachable. For example, anything on the stack is reachable, and any global variable is reachable.

• If a reachable object points to another object, then that other object is also reachable.

• Anything left over is unreachable, hence deemed not in use and reclaimable.

When the garbage collector is triggered, it goes over all the root objects, and for each of them recursively traverses objects that are reachable. Once the collector has traversed all reachable objects, it reclaims the objects that were not traversed.

A simple technique for this traversal is called mark-and-sweep. Every object contains a mark bit which is initially 0. When the traversal function reaches an object, it looks at the mark bit: if the mark bit is 1, the object has already been traversed; if the mark bit is 0, the traversal function sets it to 1 and calls itself recursively on every object to which the current object points to. The mark phase consists of calling the traversal function for every root object. It is followed by the sweep phase, which iterates over all allocated objects: if an object is still marked 0, it is freed; otherwise its mark is reset to 0.

Most garbage collectors out there are based on mark-and-sweep, though usually with considerable added sophistication.

See the wikipedia article for more information and other pointers.