How many heaps does the .NET Compact framework use

While discussing the memory architecture with an internal customer, he inquired about how many heaps .NETCF creates. I’m not sure how it might be helpful to users, but the answer is 5. This has been touched upon in some blogs and presentations (e.g. MEDC 2005) but I thought I’d put up a handy list.

Heap	Description
JIT heap	This is the heap where the buffers of jitted code is placed. Unlike the desktop CLR under some circumstances the CLR does free jitted code by a processed named code-pitching (which I will cover in a later blog post)
GC heap	This is where all the managed objects resides. The garbage collector is responsible for managing all objects on this heap including compacting it when it gets fragmented.
Short-term heap	This is used for short-lived objects. E.g. while doing a number conversion for the System.Convert methods if temporary space is required by the underlying CLR native code then it is allocated from this heap only to be freed soon.
App-domain	This is used by the CLR to place things like assembly meta-data, application/appdomain/thread state information.
Process heap	This is the default heap where rest of the stuff goes in

Total Bytes in Use After GC – Perf counter

At least one of our customers were a bit confused with the .NET Compact Framework performance counter“Total Bytes in Use After GC” which is described as “The number of bytes of memory, native and managed, in use after the last garbage collection.”. The description lead him to believe it is the total memory in use by a given managed application. That is not true.

The memory inside a .NET Compact Framework managed application can be broadly classified into

1. Managed memory
2. Jitted code
3. Other native memory allocated by the CLR
4. Native memory allocated by other sub-systems like say a COM module or some other native modules which the managed application P/Invokes into.

The first three is managed by .NET Compact Framework by using 5 heaps. The counter mentioned above returns the sum of all bytes allocated in all of the first 3 categories. .NETCF doesn’t keep tab of memory allocated in category #4.

When does the .NET Compact Framework Garbage Collector run

Other than the exact when part this post applies equally for the desktop portion.

Disclaimer: This post is mainly indicative. When the GC runs is an implementation detail and shouldn't be relied on. This is not part of any contract or specification and may (most probably will) change.

The ECMA specification for Garbage Collection is intentionally vague about when an object will be collected (or freed up). The memory management cycle mentioned in the spec is as follows

1. When the object is created, memory is allocated for it, the constructor is run, and the object is considered live.

2. If no part of the object can be accessed by any possible continuation of execution, other than the running of finalizers, the object is considered no longer in use and it becomes eligible for finalization. [Note: Implementations might choose to analyze code to determine which references to an object can be used in the future. For instance, if a local variable that is in scope is the only existing reference to an object, but that local variable is never referred to in any possible continuation of execution from the current execution point in the procedure, an implementation might (but is not required to) treat the object as no longer in use. end note]

3. Once the object is eligible for finalization, at some unspecified later time the finalizer (§17.12) (if any) for the object is run. Unless overridden by explicit calls, the finalizer for the object is run once only.

4. Once the finalizer for an object is run, if that object, or any part of it, cannot be accessed by any possible continuation of execution, including the running of finalizers, the object is consideredinaccessible and the object becomes eligible for collection.

5. Finally, at some time after the object becomes eligible for collection, the garbage collector frees the memory associated with that object.

As you can see the specification doesn't even need an implementation to do code analysis to figure out garbage. It can simply use scoping rules (used anyway by the compiler to detect valid variable usage) for garbage detection. The specification also doesn't specify eventually when the objects are collected. The only need is that it is finalized and freed unspecified time later than the time when it goes out of use. This convenient open statement lets each GC implementers to choose whatever they deem fit for the purpose. Since even thread is not specified a concurrent GC or a non-concurrent GC can be used.

However, everyone wants to know exactly when their platform's GC is run. Here goes the non-exhaustive list for the .NET Compact Framework's Garbage Collector

1. Out of memory condition: 
   When the system fails to allocate or re-allocate memory a full GC is run to free up as much as possible and then allocation is re-attempted once more before giving up
2. After some significant allocation: 
   If one megabyte of memory is allocated since the last garbage collection then GC is fired.
3. Failure of allocating some native resources: 
   Internally .NET uses various native resources. Some native resource allocation can fail due to memory issues and GC is run before re-attempting
4. Profiler: 
   Profiler APIs build into the framework can force a GC
5. Forced GC: 
   System.GC class is provided in the BCL to force a collection
6. Application moves to background
   When the given application is moved to background collection is run

Obviously there can be small differences across various platforms on which .NET CF is implemented. However, the differences are small enough to ignore for this discussion.

Even though this list seems small it works pretty well across disparate systems like XBox and Windows Mobile. In the next post I'll try to get into why "production user code should never do a forced GC". I know that statement is a bit controversial (at least it got so in an internal thread).

How does the GC find object references

Most garbage collection algorithms needs to know all other objects referenced by a given object to correctly traverse object hierarchy. All of reference counting, mark-sweep and even coping collectors need it. Consider the mark algorithm that I used in mark-sweep GC

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 <>

        {

            Mark(children[i]); // recursively call mark

        }

    }

}

Here a critical piece is the line in red. Given the object header we need to be able to locate all other objects referenced by it (or are children of it in object reference graph). There are two basic ways to do this

Conservative GC

In case a GC is being plugged into an existing system in the form of a library and there is no easy way to modify the runtime then a conservative (as opposed to precise) system is used. A conservative GC considers every bit pattern on the heap to be a valid reference to another heap object. For the above case given a object header the GC needs to have the following basic information

1. The size of the object
2. Alignment of pointers (lets assume it to be 32bit for our case)

So once the GC gets a object pointer pObj it considers all 32bit patterns in between pObj and (pObj + sizeof(Object)) to be references to other child objects. It then uses some basic elimination like whether the value points inside the current heap for the system. If it doesn’t match any elimination logic then it is considered to be a reference.

Even though this approach seems a bit extreme, it works out well and the only flip side is that it returns false positives and hence some garbage which should’ve been collected is left out (e.g. because an int containing a value accidentally matches the address of an object on the heap).

Precise GC

In precise GC the GC precisely knows every reference held in a given object. This is possible only if the runtime generates and preserves this information. There are various ways to implement a precise GC and I'll qiuckly go over one of the ways to do it,

Every object has an object header which in turn contains a pointer to it’s type/class descriptor. This class descriptor has a special 32-bit field named ReferenceMap which is used to store reference information stored by a given type

So given an object pointer pObj the GC fetches the object header from before the pointer and then de-references the class descriptor pointer to get to the corresponding type’s Class descriptor. It then reads the ReferenceMap stored into it. To do all of the above the GC needs to know only the object header and class descriptor layout and not any other type information.

All references are 32-bit aligned and the ReferenceMap contains one bit per 32-bits of the object. If the bit is set it means that the corresponding 32-bit is a reference.

Let’s take the following class

class MyType

{

    public char a;

    public char b;

    public AnotherType t1;

    public int i;

    public AnotherType t2;

}

The memory layout of the class would be something like

The first two chars take 16 bits each. After that there are 3, 32-bit entities of which t1 and t2 (1st and 3rd) are references to other objects but i is not.

So the GC needs to know that given this object the 32-bits from 32nd and 96th are actually references. This is exactly what is encoded in RefMap field. It contains the bit-pattern 00000000000000000000000000001010 where the LSB is for the first 32 bits of the object (which is a+b in this case) and so on.

Since bit 1 of refmap is set it means (pObj + 1 * 32) is a reference. If that value is non-NULL then the GC can just de-reference it to get to the t1 object reference held by pObj.

Obviously it means that the maximum size of object that RefMap can encode is 32*4 = 128bytes. No points for guessing how it handles objects larger than that :)

Generational Garbage Collection

One of the primary disadvantage discussed in the post on mark-sweep garbage collection is that it introduces very large system pauses when the entire heap is marked and swept. One of the primary optimization employed to solve this issue is employing generational garbage collection. This optimization is based on the following observations

1. Most objects die young
2. Over 90% garbage collected in a GC is newly created post the previous GC cycle
3. If an object survives a GC cycle the chances of it becoming garbage in the short term is low and hence the GC wastes time marking it again and again in each cycle

The optimization based on the above observations is to segregate objects by age into multiple generations and collect each with different frequencies.

This scheme has proven to work rather well and is widely used in many modern systems (including .NET).

Detailed algorithm

The objects can be segregated into age based generations in different ways, e.g. by time of creation. However one common way is to consider a newly created object to be in Generation 0 (Gen0) and then if it is not collected by a cycle of garbage collection then it is promoted to the next higher generation, Gen1. Similarly if an object in Gen1 survives a GC then that gets promoted to Gen2.

Lower generations are collected more often. This ensures lower system pauses. The higher generation collection is triggered fewer times.

How many generations are employed, varies from system to system. In .NET 3 generations are used. Here for simplicity we will consider a 2 generation system but the concepts are easily extended to more than 2.

Let us consider that the memory is divided into two contiguous blocks, one for Gen1 and the other for Gen0. At start memory is allocated only from Gen0 area as follows

So we have 4 objects in Gen0. Now one of the references is released

Now if GC is fired it will use mark and sweep on Gen0 objects and cleanup the two objects that are not reachable. So the final state after cleaning up is

The two surviving objects are then promoted to Gen1. Promotion includes copying the two objects to Gen1 area and then updating the references to them

Now assume a whole bunch of allocation/de-allocation has happened. Since new allocations are in Gen0 the memory layout looks like

 

The whole purpose of segregating into generations is to reduce the number of objects to inspect for marking. So the first root is used for marking as it points to a Gen0 object. While using the second root the moment the marker sees that the reference is into a Gen1 object it does not follow the reference, speeding up marking process.

Now if we only consider the Gen0 objects for marking then we only mark the objects indicated by ✓. The marking algorithm will fail to locate the Gen1 to Gen0 references (shown in red) and some object marking will be left out leading to dangling pointers.

One of the way to handle this is to somehow record all references from Gen1 to Gen0 (way to do that is in the next section) and then use these objects as new roots for the marking phase. If we use this method then we get a new set of marked objects as follows

This now gives the full set of marked objects. Post another GC and promotion of surviving objects to higher generation we get

At this point the next cycle as above resumes…

Tracking higher to lower generation references

In general applications there are very few (some studies show <>

Write barrier + card-table

First a table called a card table is created. This is essentially an array of bits. Each bit indicates if a given range of memory is dirty (contains a write to a lower generation object). E.g. we can use a single bit to mark a 4KB block.

 

Whenever an reference assignment is made in user code, instead of directly doing the assignment it is redirected to a small thunk (incase .NET the JITter does this). The thunk compares the assignees address to that of the Gen1 memory range. If the range falls within, then the thunk updates the corresponding bit in the card table to indicate that the range which the bit covers is now dirty (shown as red).

First marking uses only Gen0 objects. Once this is over it inspects the card table to locate dirty blocks. Then it considers every object in that dirty block to be new roots and marks objects using it.

As you can see that the 4KB block is just an optimization to reduce the size of the card table. If we increase the granularity to be per object then we can save marking time by having to consider only one object (in contrast to all in 4KB range) but our card table size will also significantly increase.

One of the flip sides is that the thunk makes reference assignment slower.

HW support

Hardware support also uses card table but instead of using thunk it simply uses special features exposed by the HW+OS for notification of dirty writes. E.g. it can use the Win32 api GetWriteWatch to get the list of pages where write happened and use that information to get the card table entries.

However, these kind of support is not available on all platforms (or older version of platforms) and hence is less utilized.

Handling overflow in mark stage

Let’s first recap the basic algorithm of the mark-sweep garbage collection. In C like pseudo code the algorithm looks like

void GC()

{

    HaltAllThreads();

    ObjectCollection roots = GetRoots();

    for(int i = 0; i <>

        Mark(roots[i]);

    Sweep();

}

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 <>

        {

            Mark(children[i]); // recursively call mark

        }

    }

}

This algorithm is by nature recursive where in the marking phase we recursively mark every object and it’s children. However, recursion is not optimum in terms of both time and space usage. Each method call comes with additional overhead which is particularly more bothersome because GC is anyway run when the system is low on resource.

Controlling the depth of call stack in recursive algorithm is also hard. In the algorithm shown above the depth of the stack is equal to the length of the longest reference chain.

This is worked around by using general recursion to iteration conversion methods like using explicit marking stacks as show below

Stack g_MarkStack(MAX_SIZE);

void Init()

{

    g_MarkStack.RemoveAll();

}

void GC()

{

    HaltAllThreads();

    Init();

    ObjectCollection roots = GetRoots();

    for(int i = 0; i <>

        g_MarkStack.Push(roots[i]);

    Mark();

    Sweep();

}

void Mark()

{

    while(!g_MarkStack.Empty())

    {

        Object *pObj = g_MarkStack.Pop();

        if(!Marked(pObj))

        {

            MarkBit(pObj);

            ObjectCollection children = pObj->GetChildren();

            for(int i = 0; i <>

            {

                g_MarkStack.Push(children[i]);

            }

        }

    }

}

Using explicit marking stack we have removed the need for recursive algorithm. Now this is more deterministic and it is easy to figure out when the heap graph is too deep and the stack actually overflows (at the point of push we can check for g_MarkStack.IsFull())

Handling overflow

Explicit stack makes detecting and handling of stack overflow easier. It doesn’t however, remove the issue. The first cut attempt is to reduce the number of items being pushed into the stack. Objects are pushed onto the stack so that they behave as branch points so that once a child has been marked we can come back to it’s parent and branch off and mark it’s other children. So simple fixes like only pushing in case an object has two or more children does help in reducing the overflows

There are other ways to work around this problem like using alternate tree marking algorithm like Schorr-Waite graph marking algorithm

However, whatever method we try there will be large objects trees where the stack will run out of space and that needs to be handled.

.NET Compact framework uses a two level fall back scheme as explained below.

Using overflow stack

The basic mark stack used is a grow-able stack buffer which can grow to max 4KB. In case this overflows another small fixed sized stack is used which is called the overflow-stack. Objects where the overflow happens while marking are pushed on to this overflow stack. The children of these are not traversed.

This means a part of the tree is left out from marking and growth of the mark stark is kind of contained. The mark buffer unwinds and marking is started back on it. In the next pass marking is restarted considering the objects on the overflow-stack as roots. This is done iteratively. The idea here is that with each such pass, more and more of the tree is marked and hence the marking finally converges.

Overflow-arena

For really deep trees even the overflow-stack can overflow. To handle this the following steps are taken

1. .NETCF uses pooled memory where 64K sized memory pools are used and objects are sub-allocated from them. The memory pool where the overflowed object resides is located. Each of these pools contain two pointers which point to the first and the last objects in the pool that overflowed. These two pointers are updated to point to the currently overflowed object.
2. The header of the object where the overflow happened is marked with a special bit flag OBJFLAG_MARK_OVERFLOW.
3. At this point the object pool looks something like 
   
4. A global linklist of all such pools which has overflowed objects is also preserved
5. Once objects in mark-stack and overflow-stack is marked another pass is started which does the following 
   foreach Pool in Overflow-arena 
       foreach Obj >= Pool.header.start and Obj < Pool.header.end 
            if(obj.flag & OBJFLAG_MARK_OVERFLOW) 
                Mark(obj)

The very design of the .NETCF GC is to cater to low memory devices. Hence it very rarely needs to use the fall-back. The design ensures that GC is optimal for low memory usage but can scale up (albeit with perf cost) for large memory as well.

Optimizing reference counting garbage collection

One of the comments on my previous post on reference counting GC prompted this post. The comment goes as

“Ref counting GC seems to have some hard issues. How does it still get used?”

The advantages of reference counting GC is that it allows reclamation instantly after the object is no longer in use and that it spreads the GC cost across execution and hence does not suffer from the longer pauses like mark-sweep GC does. These makes it compelling to get used in some scenarios (e.g. interactive systems). However, it does suffer from some major drawbacks. In this post I will skim through the issues and how they are worked around in real systems.

Cyclic references

The fact that cyclic references cannot be handled by general refcounting mechanism is touted as it’s biggest draw back. A variety of approaches has been attempted to solve this. The two main categories of approaches include either ways to distinguish pointers that form a part of the cycle from those that do not or using back up mark-sweep GC.

Using a backup mark-sweep GC works pretty well in handling cyclic references. The idea is to have a regular refcounting GC that just ignores cyclic references. It fails to cleanup cyclic references that just builds up over time. When periodically the back up mark-sweep GC is run which cleans up objects with non-zero refcount that are not externally reachable.

Reducing the number of reference counting

Reference counting makes pointer manipulation very costly because every referencing/de-referencing results in book keeping to happen. One common approach to work around this, is to figure out what are the reference counting that can be safely deferred to be handled later.

For a lot of systems most references are taken in function local variables which takes references as the function is called and releases them as the function returns. Even inside functions iterators can walk over data structures like lists. Refcounting these can be very costly. These reference needn’t be explicitly counted right away as they  on the stack and can be accessed later.

However, for global variables and even class member variables assignments the reference count is updated.When on de-referencing an object the refcount goes to 0 it cannot be reclaimed because there can be some stack variable references to it (which was not counted). To handle this the object is placed on a special list which contains all objects whose ref count has hit 0 (e.g. ZeroRefCountList).

With this mode the execution can proceed as usual and every so often a special routine is fired which walks all the active thread’s call stack to locate the stack variable and then update object ref count as follows

 void UpdateRefCount()

{

    // Stack object references are not refcounted and so bump up their

    // refcount for all their occurrences

    foreach (object obj in stack)

        RefCountIncrement(obj)

    // At this point the ZeroRefCountList objects are updated to 

    // their latest ref count values. So 0 means really 0 refcount

    // and hence free them recursively 

    foreach (object obj in ZeroRefCountList)

    {

        if(refCount(obj) == 0)

        {

            foreach(Object child in obj.GetChildren)

                RecursiveDelete(child);

            free(obj);

        }

    }

    // reset the refcount to get it back to the state

    // where it was before calling UpdateRefCount

    foreach (object obj in stack)

        RefCountDecrement(obj);

}

The above routine is a condensed version of mark and sweep with the differences that it needn’t walk the entire memory and is not performance intensive.

Reduce space overhead

In the worst case every pointer in the system can point to a the same object and hence the refCount field is typically pointer sized so that it can store all the reference’s count. However, in reality this is seldom the case and being so conservative might result in a lot of space overhead per object. Say for a 32 bit system it means storing a 32 bit value for every object. For small sized objects that can mean upto 50% overhead.

To handle this a conservative estimate can be made to the maximum number of reference that an object can have. Let’s assume it to be 255. This needs a refcount field of 8 bits (1 byte) and that is stored in the object header. Post this the refcount is made as follows

void RefCountIncrement(Object obj)

{

    if(obj.refCount <>

        ++obj.refCount;

}

void RefCountDecrement(Object obj)

{

    if(obj.refCount <>

        --obj.refCount;

}

The above algorithm allows correct refcounting for all objects whose refcount never goes upto 255. The moment it does it’s refcount sticks to 255 and is never incremented or decremented. Typically these objects are fairly smaller in number but if they exist they are not reclaimed (sticks to the system). Once such accumulations of these happen in significant number (which will take a lot of time) a backup tracing GC is run to sweep the memory of these objects.

Why use backup mark-sweep GC as backup?

A bunch of the solutions mentioned above use mark-sweep GC as a solution. The question is if they are to be used then why not completely switch to mark-sweep and dump refcounting. The main reason is that refcounting act an an optimization for mark-sweep GC reducing system pauses (remember they typically halt execution completely) introduced by them and making them run less often.

Copying Garbage Collection

In my previous post I have discussed reference counting and mark-sweep garbage collector in some detail. This post is a quick intro into the copying GC. I’ll not be going into the gory details because this is not much used in the .NET world.

The copying GC conceptually breaks the memory into two regions. Let’s call the ping and pong as shown below.

The buffer Ping is initially used for allocation of memory. It maintains a pointer at the end of the last allocated memory and for each new request simply returns that pointer and then increments it to point to the new end. So at the beginning when no memory is allocated it points to the bottom. After a bunch of allocation this is what the it looks like

Allocation is very fast as it involves only incrementing a pointer. However, after a bunch of allocations the situation will arrive where current-Pointer + requested > Ping-top. This means no more memory can be allocated from Ping. It is at this time the GC is run.

Garbage collection involves enumerating the roots and then copying every live object from Ping to Pong. Since objects are moved in memory all their references have to be updated as well. After the copy the buffers are switched so that subsequent allocations can now happen from Pong. Ping remains clean for the next copy cycle.

For the example set above lets assume when the GC is run Object 1 and 3 are live but 2 isn’t. After GC runs the memory layout becomes

Advantages and disadvantages

The primary advantage is that allocation is extremely fast (almost equal to stack allocation) because out of memory checks is just a pointer check and actual allocation is just incrementing the free pointer. Since the GC compacts memory it maintains good locality of reference resulting in better cache hit ratios and hence faster execution.

The main disadvantage with copying GC is that almost double the memory space is required. Even though it is argued that in virtual memory based systems it shouldn’t be a problem because the un-used memory pages will simply be paged out to the disk, the argument is not essentially true. Specially during GC phase both the memory half's are touched (due to ping <-> pong copy) and the number of page-faults generated are much larger than other GC schemes.

Mark and Sweep Garbage Collection

Recap of definition

I’ll quickly repeat couple of definitions which are used in this post

1. Object: This is a unit of storage on the heap. It generally means an object in the object oriented sense but is equally applicable to a procedural language (e.g. a struct/native-type in C) or functional language.
2. Object/Reference graph: This is the directional graph of objects in memory. A typical sample is below. The nodes are objects in memory and the edges (arrows) are references one object holds to another (e.g. a pointer or reference in C/C++). There can be circular references between two nodes (Object 3 and Object 5) or nodes referencing themselves (Object 6). 
      
3. Roots: These are the set of nodes in the object graph from which the references start. These are typically references held in registers, local variable on the stack or global variables. The green nodes in the diagram above are roots.
4. Unreachable object: These are nodes in the graph which have no edge referencing them. The Orange node in the diagram above is an unreachable object. This is the node that the GC needs to clean/free because it is not reachable from any node and is hence garbage memory.

Mark-sweep GC

In the last post I discussed reference counting GC which continually tracks memory and frees them the moment they go out of reference. Mark and sweep GC takes a very different approach.

In this scheme memory is not freed the moment they become garbage. Actually no subsystem is used to keep track of memory as they are being used.

When the system starts running out of memory (or some other such trigger) the GC is fired. It first enumerates all the roots and then starts visiting the objects referenced by them recursively (essentially travelling the nodes in the memory graph). When it reaches an object it marks it with a special flag indicating that the object is reachable and hence not garbage. At the end of this mark phase it gets into the sweep phase. Any object in memory that is not marked by this time is garbage and the system disposes it.

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

It has three phases, enumeration of roots, marking all object references starting from the root and finally sweeping them.

Root Enumeration

As I mentioned above the root enumeration lists all references held in registers, global or static fields, local variables on the stack, function arguments on stack, etc… The runtime system needs to provide ways for the GC to collect the list of roots. E.g. in the case of .NET the JIT maintains the information on the active roots and provides APIs to the GC to enumerate them. The system can also do some form of dynamic analysis to further optimize it. Say a function accepts a pointer argument. Now while JITing the jitter can figure out that the argument is not being used through out the method and can drop it from the list of roots the moment it is last accessed in the method.

Mark

Typically every object is given some sort of header as I mentioned in my last post. This header contains a bit flag which is used to “mark” that object. 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 *)

Special memory layout is needed to handle this assumptions and I’ll try to cover how they are handled atleast in .NETCF in later post.

Compaction

Repeated allocation can actually fragment memory and slow allocation speed significantly (head over herefor a nice story on this). So many systems actually combine sweep with a compaction. This ensures fragmentation reduces and hence subsequent allocations are faster. However, when memory is compacted objects move and hence all references to them has to be updated to point to the new location.

When is the GC run

At the face of it, it seems that GC should be run when memory allocation fails. However, when memory allocation fails there is a high chance that GC will fail as well because it would need some working memory to function which won’t be available. So in real world systems GC is fired under a variety of conditions like

1. System is low on memory (enough for a GC to run but soon allocations are going to fail)
2. Memory it too much fragmented
3. After allocating a bunch of memory (e.g. .NET CF fires GC on allocating 1MB after the last GC)

This obviously varies from system to system and is carefully tuned to match the scenarios being supported.

Advantage and disadvantages

The primary advantage of mark-sweep is that it handles cyclic references naturally. Moreover, no additional overheads are added while normal execution (e.g. allocation, pointer manipulations). Combined with compaction it ensures good locality of reference and reduced fragmentation and hence optimal subsequent allocations.

However, mark-sweep pauses useful execution and walks entire memory marking and sweeping it. Hence it adds large freezes which is un-acceptable in most interactive systems. However, incremental variations of Mark-sweep are available which works around this limitation. Mark-sweep also starts thrashing when memory fills up as it fails to clean up memory and it gets triggered again and again as memory approaches exhaustion. Self tuning GC helps in this scenario.

Reference Counting Garbage Collection

Reference counting (refcounting) GC is one of the two primary GC mechanisms widely used. The basic workings of this GC is pretty simple and based on counting the number of reference to a memory block (or object) from other blocks. Each time memory is created or a reference to the object is assigned it’s refcount is bumped up. Each time a pointer is assigned away from it the refcount is reduced. When refcount of the block goes to 0, it means that no pointer references it and hence it is un-reachable and is garbage and can be reclaimed.

Let’s assume RefCount(VOID *pMem) gives us the reference count of the object at pMem. Then the following code shows how the reference count of a specific object in memory varies with the code flow.

Object * obj1 = new Object(); // RefCount(obj1) starts at 1 Object * obj2 = obj1;         // RefCount(obj1) incremented to 2 as new reference is added Object * obj3 = new Object();   obj2->SomeMethod(); obj2 = NULL;                  // RefCount(obj1) decremented to 1 as ref goes away obj1 = obj3;                  // RefCount(obj1) decremented to 0 and can be collected

As the execution flow mutates the state of the program, the refcount of each object is updated transparently and the block is freed when refcount hits 0. As you might guess this record keeping and collection can be implemented in various ways. Here I discuss one of them…

Storage structure and allocation

For each object the refcount has to be stored in some place. Since this field will be accessed very often it’s best to keep it inside or close to the object to preserve spatial locality of reference which has a lot of impact on performance (by ensuring good cache hit ratio). One of the approach we can take (which is most common) is to add a small header to the start of every object allocated. So each time allocation is asked for a object we allocate sizeof(header) + sizeof(type to be allocate). The memory layout looks like

As apparent from the diagram the pointer returned is at the start of the actual data and not the start of the data allocated. This means that the caller isn’t even aware of the header and can use the data as is. However the garbage collector knows that every object has this header and can use any object pointer to access this header.

The header structure we choose is

struct MemHeader {     UINT32 refCount; };

The allocation routine (in pseudo C) looks like

// cb is the number of bytes to be allocated PVOID GC_Alloc(size_t cb) {     // allocate MemHeader + cb but cast it to MemHeader     MemHeader* pHdr = (MemHeader*)PlatformAlloc(MEMHEADERSIZE + cb);     if (pHdr == NULL)         return NULL;      // set the initial refCount     pHdr->refCount = 1;      // increment the pointer by the size of MemHeader      // and make it point to the start of the actual data     ++pHdr;      return (PVOID)pHdr; }

When the GC wants to access the header it can simply use

inline MemHeader * GetHeader(PVOID pMem) {     return ((MemHeader*)pMem) - 1; }

Counting references

For every pointer updation the affected objects’ reference count has to be updated. E.g. for a pointer assignment of sort l = r the following needs to be done

void GC_UpdateRef(PVOID *l, PVOID r) {     // used for assignment of l = r          // increment ref count for r-value as an additional reference is being taken     if (r != NULL)         ++(GetHeader(r)->refCount);      // decrease ref count of l-value as it’s releasing it’s previous reference     GC_ReleaseRef(*l);      // do the final assignment     *l = r; }

However, this function has to be called for all pointer assignments and even when pointers go out of scope. This is the tricky part and is achieved by various ways

1. Compilers can insert call to GC_UpdateRef for all pointer assignment and also when references go out of scope (like it inserts call to destructors/finalizers)
2. For languages that support operator overriding this behavior can be added from outside. However, that might need some changes to the type system like making all garbage collectable types inherit from some common type (which then has the overriding added).

Freeing objects

The final piece is actually freeing objects when their reference count goes down to 0.

VOID GC_ReleaseRef(PVOID pMem) {     if (pMem == NULL)         return;      // get the memory header and decrement the refcount     MemHeader *pHdr = GetHeader(pMem);     --(pHdr->refCount);          // if ref count has gone down to zero, free it     if (pHdr->refCount == 0)     {         PlatformFree(pHdr);     } }

Even though this seems straightforward it is actually lacking a crucial block. Consider the following reference graph

Here if object 1 goes out of reference and gets reclaimed by GC_ReleaseRef then recursively we need to check (and free if required) all other references held by it. So in this particular case object 4 shouldn’t be freed (as object 2 has a ref to it) but both Object 3 and Object 5 needs to be freed. So the full method would be something like

VOID GC_ReleaseRef(PVOID pMem) {     if (pMem == NULL) return;     MemHeader *pHdr = GetHeader(pMem);     --(pHdr->refCount);     if (pHdr->refCount == 0)     {         foreach(PVOID pChild in Get_Child(pHdr))              GC_ReleaseRef(pChild);         PlatformFree(pHdr);     } }

The additional part are the lines in red. The assumption is that Get_Child returns all other references held by the object and we recursively free them. However, actually implementing Get_Child is hard. One of the mechanism used it to maintain compiler/type-system generated reference mask which I will cover that as a part of mark-sweep garbage collection.

Advantage/disadvantage of reference counting GC

Reference counting GC has a primary disadvantage. Which is used on it’s own it completely fails to handle circular references. Consider the following reference graph

Here Object2 refers to Object3 and vice-versa. Now if Object 1 releases the reference marked in red then both Object2 and Object3 becomes un-reachable and garbage. However, since they refer to each other both will have a refCount of 1 and will not get freed. To handle this situation ref counting GC is never used on it’s own. It is used in conjunction with some other GC like mark-sweep which is run periodically to clean these circular reference leaks.

Refcounting GC adds significant code/perf bloat as for every assignment calls to update refCount has to be added. Moreover, for multi-threaded system it can prove to be a major issue as locks have to be taken when updating refCount. Even the most performant atomic operations (e.g. Win32 InterlockedIncrement) are costly when used repeatedly. The header space cost which seems petty also eats into the system because for small objects they cause significant overhead. E.g. for an allocated int32 it adds 100% overhead (as the header is also 32 bit value).

Advantage besides being easy to implement is that objects gets re-claimed the moment they become garbage. This means if objects support destructors/finalizers then these are run pretty soon and system resources held by them return to the OS faster.

Reference counting GC ensures that the collection is distributed over the whole period of execution and hence for interactive system doesn’t result in system freezes like say mark-sweep GC does.