Mark and Sweep Garbage Collection Algorithm

The algorithm

At the top level the algorithm in C like Pseudocode looks as follows

void GC(){    HaltAllProcessing();    ObjectCollection roots = GetRoots();    for(int i = 0; i < roots.Count(); ++i)        Mark(roots[i]);    Sweep();}

Mark

The Mark procedure is recursive and acts as follows

void Mark(Object* pObj){    if (!Marked(pObj)) // Marked returns the marked flag from object header    {        MarkBit(pObj); // Marks the flag in obj header        // Get list of references that the current object has        // and recursively mark them as well        ObjectCollection children = pObj->GetChildren();        for(int i = 0; i < children.Count(); ++i)        {            Mark(children[i]); // recursively call mark        }	    }}

This is a recursive algorithm with heavy dose of simplification used and we will re-visit this in later posts on with actual implementation implications.

The recursion termination criteria is

  1. Either a node doesn’t have any children (leaf node)
  2. If it is already marked which ensures that we do not land in infinite recursion for circular references

At the end of this marking phase every object that can be reached using a reference from the roots would have been visited and it’s marked bit set.

Sweep

Sweep starts by iterating through the entire memory and frees memory blocks that are not marked. It also clears the Mark bit so that subsequent GC passes can correctly mark/unmark them (resets the memory to pre-mark state).

void Sweep(){    Object *pHeap = pHeapStart;    while(pHeap < pHeapEnd)    {        if (!Marked(pHeap))            Free(pHeap); // put it to the free object list        else            UnMarkBit(pHeap);        pHeap = GetNext(pHeap);    }}

There are a bunch of assumptions here which has to be met. Some of them are that the

  1. Entire heap can be iterated over
  2. Both free memory blocks and allocated objects have the same sort of header that can be queried with Marked
  3. You can find the next memory block when given one block (GetNext implemented)
  4. There is some sort of free memory pool which tracks the list of free memory and you can add a block to it by calling Free(Object *)