Back To Basics: Generational Garbage Collection

This post is Part 8 in the series of posts on Garbage Collection (GC). Please see the index here.

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 < 1% of all references) of these type of references. However, they all need to be recorded. There are two general approached of doing this

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.

Back To Basics: Handling overflow in mark stage

This post is Part 7 in the series of posts on Garbage Collection (GC). Please see the index here.

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 < roots.Count(); ++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 < children.Count(); ++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 < roots.Count(); ++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 < children.Count(); ++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.

Installing S60 development tools on Windows 7

My first attempt to install Carbide on Win 7 failed. So I thought I’d document the exact steps I followed the second time to make that work

Install Pre-requisites

1. Perl
   1. I used ActivePerl 5.6.1.638
   2. To ensure UAC didn’t cause any issues I first launched an elevated command prompt by going to All Programs –> Accessories, right click on Command Prompt and choose Run as administrator
   3. In that I ran the command msiexec /i ActivePerl-5.6.1.638-MSWin32-x86.msi
   4. I choose the path c:\perl\bin
   5. I ran path command from another newly launched command prompt to ensure that c:\perl\bin is present in it (so Path environment variable is updated)
2. Java
   1. I downloaded jre-6u7-windows-i586-p.exe
   2. Right clicked on it and used Run as administrator to install it

Installing the S60 Tools

1. S60 SDK
   1. Downloaded S60_5th_Edition_SDK_v0_9_en.zip
   2. Unzipped to a folder
   3. Right clicked on setup.exe and used Run as administrator to install it
   4. Used c:\S60\devices\ as the install path. So my final installation is in C:\S60\devices\S60_5th_Edition_SDK_v0.9
2. Carbide
   1. Downloaded Carbide V2.0
   2. Right clicked on it and used Run as administrator to install it
   3. Used C:\Apps\ as the install path
3. PC Suite
   1. Downloaded Nokia_PC_Suite_7_1_18_0_eng_us_web.exe
   2. Right click on the exe and choose Troubleshoot compatibility
   3. In the wizard that opens click next
   4. Ensure the following is checked on the next page of that wizard
      
   5. Hit Next and in the next page choose Window Vista
   6. Go on hitting next and finally the installer will launch

At this point you are done and should be able to launch Carbide, Emulator and PC Suite.

Scott Guthrie’s visit to Microsoft India

I rarely blog about a photo but this is an exception. Scott Guthrie our Corporate Vice President for .NET Developer Platform was here in Hyderabad on a visit to Microsoft India. I had a chance to attend a bunch of product reviews and  meetings with him. Every person in our division and outside is in complete utter awe of this guy, it was inspirational to hear his ideas and visions around .NET and Silverlight.

Scott with a bunch of folks from .NET Compact Framework and Silverlight Mobile team. As you can guess Scott is in the center. I’m the one on the absolute right.

Back to Basics: 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 256. 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 < 256)
        ++obj.refCount;
}

void RefCountDecrement(Object obj)
{
    if(obj.refCount < 256)
        --obj.refCount;
}

The above algorithm allows correct refcounting for all objects whose refcount never goes upto 256. The moment it does it’s refcount sticks to 256 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.

Back To Basics: Copying Garbage Collection

This post is Part 5 in the series of posts on Garbage Collection (GC). Please see the index here.

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.

Back To Basics: Mark and Sweep Garbage Collection

This post is Part 4 in the series of posts on Garbage Collection (GC). Please see the index here.

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 here for 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.

Back To Basics: Reference Counting Garbage Collection

This is Part 3 in a series of post on GC, visit the list here.

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.

After becoming the .NET Compact Framework (.NETCF) dynamic memory management module owner I am continually learning a lot about the subject. Based on hallway discussion I figured out that a lot of developers are not very clear about the subject and would like to learn more. Most online material I encountered gets into too much of details and implementation for most casual readers.

So here is my attempt to write up a series on GC. I plan to cover the basic stuff and then move into details of .NET CF GC including performance, profiling. I plan to cover bits of desktop .NET GC as well (but for that Maoni’s blog is a better resource) The first two in this series is already published. I will keep this post updated to act as an index into the series.

1. Memory allocation, a walk down the history
2. Why use garbage collection
3. Reference Counting Garbage Collection
4. Mark-sweep garbage collection
5. Copying garbage collection
6. Optimizing reference counting garbage collection
7. Handling overflow in mark stage
8. Generational Garbage Collection
9. How does the GC find object references
10. More to come … :)

In case you have some suggestion send it my way and I will try to include that as well…

Windows 7 rocks

Ok I know this blog is not about Windows but I thought I’d share the love.

To me it looks like as is someone has combed through the entire user experience and fixed most of the stuff that bothered me.

The taskbar change alone are good enough for the upgrade. E.g. the taskbar feels very natural when set in vertical position (it didn’t work well in this configuration before). The icons in tray and the status bar can be dragged around and it actually shows download progress in the IE taskbar icon itself (See the green progress in the screenshot below). I can even close an app by hovering over it’s icon on the taskbar (no need to restore it and then travel across the entire screen and hit close button). The taskbar is very accessible through keyboard, hit Win+T and taskbar is in focus and then shift through the icons using the arrow keys.

The greatest shocker was when I connected my laptop to my TV and it instantly popped up the following, it then correctly picked up my TV’s resolution (1080p) and matched screen resolution to that. Almost felt magical…

I could go on and on (like the awesome window management features) but you can head over to Tim’s blog and read more details there.

Back to basics: Why use garbage collection

This is a part of a series of post on GC. See the index here

Garbage Collection does exactly what it’s more fancier name “Automatic dynamic memory management” suggests. As I discussed in my last post on Memory Allocation dynamic memory is hard to manage and GC attempts to do that automatically and relieves the coder from the hard task.

GC basically attempts to take care of two basic scenarios remove garbage and avoid dangling pointers. They are very inter-related but are different scenarios

Garbage Collect

Consider a typical object reference graph. In the graph every rectangle is an object and the arrows denote object references. So A is an object which references B. For a program to be able to use an object it should be in one of these reference chains. The reference chain start from what is called Root and are typically references held in registers, on stack as local variable or global variables.

Let’s assume that due to some operation, A relinquishes the reference to B and the graph becomes something like this…

 

Now B and hence C is not reachable from any valid root in the program and hence have become Garbage (un-reachable). The programmer must ensure to follow all reference and free (de-allocate them). One of the duty of a GC system is to automate this process by tracking down (using various algorithms) such objects and reclaim the memory used by them automatically. So in a GC system when the reference is broken it will figure out that B and hence C is not reachable and will de-allocate them.

Hanging/dangling reference

Let’s consider another object graph which is similar to the one above but in addition to A, another object A’ also has a reference to B (or in other words B is shared between them)

Even here after some operation object A doesn’t need reference to B. The programmer does what he thinks is right and de-allocates B and C

However, A’ still has a references to B and hence that reference is now hanging or in more specific term pointing to invalid memory and would typically return unpredictable result when accessed. The key here is the unpredictable behavior. It is not necessary that program will crash. Unless the memory location in B is re-used it will seem to have valid data and de-references from A’ will work fine. So the failure will come up in un-expected ways and totally un-related places in the program and will make locating the root cause extremely hard.

GC helps by automatically taking care of both of the above scenarios and ensuring that the system doesn’t land up in either of them.

How important is GC

If GC is so cool then why doesn’t all systems use GC. There are multiple reasons but with newer technology most of them are going away. One of the primary reasons of not using GC is the performance overhead. This makes GC a less lucrative deal for real-time systems, device drivers and even gaming platforms. However, there are examples where GC is used even for these systems, e.g. .NET Compact Framework (the team I work for) is used with full GC support very successfully in XNA games on Xbox.

However, on some systems like functional languages which relies a lot on closures and deferred execution of those, it makes execution flow very un-predictable and hence GC becomes almost mandatory.

Back To Basics: Memory allocation, a walk down the history

This is a part of a series of post on GC. See the index here

Most languages we deal with today support a whole bunch of different memory allocation options. We have an option to use static allocation, stack-allocation and heap allocation. However, same was not true in the pre-historic era, life was simple then and the earlier languages just supported static allocation, then slowly stack and then heap allocation came by and today we have come to expect automatic memory management from most new languages.

However, that didn’t really mean that there was no advantage is the simplistic approach taken by these early languages.

Static allocation

This is the simplest allocation option and was supported by initial languages like Fortran (early 50’s). All memory was allocated (reserved) during compile time and variable names were bound to the target memory and frozen. This had some serious limitation like variable memory couldn’t be supported. In case memory usage might vary the developer simply allocated the largest size he anticipated and used from it.

This also meant that size of all Data Structures were known at runtime (e.g. fixed length arrays, no link-lists). Since name binding happened statically, simple things we have come to expect over time like recursion was not possible because the second instantiation of a method would mean that same variables are accessed and since names are bound to addresses statically they would over-write data.

Even though this seems to be pretty restrictive this had some advantages. The most obvious is robustness and predictable behavior. Since there are no runtime memory allocation, there is no possibility of running out of memory (so no OutOfMemoryException :) ). The execution was also very fast because there is no memory to manage and no stack/heap to tear down. Moreover the compiler could emit direct memory accesses instruction without going through any indirection (as symbol->address mapping doesn’t change).

Stack Allocation

The first languages to bring in stack allocation was Algol in late 50’s. This worked past some limitations of static allocation by supporting memory frames that got pushed onto the system stack as procedures were called. What this meant was that based on the input parameters of a method it could push a different sized frame and hence had variable memory allocation (atleast for method local variables). However, return value had to be of fixed size (fixed by compile time) because the caller would need to know how much was left behind by callee on the stack.

Recursion was possible because every invocation would have it’s exclusive frame, and hence when a method returned the frame would unwind (pop) and memory allocated by it would be no longer available to the callee.

Obviously with this came reduced robustness because based on control flow the program could get out of stack and the additional stack management overhead reduced speed (though not significantly).

Even though it wasn’t much but it still was a huge improvement…

Heap Allocation

Funny to call it so but this is the state of the art in memory allocation :) and has remained so for a long time (with some improvements).

With heap data could be allocated in chunks of variable size and later de-allocated. There is no ordering requirement in-between the allocation and de-allocation unlike the stack frames where callee memory gets deallocated before the caller. So now it was possible to allocate and pass variable sized memory around (e.g. from Callee to Caller). It was easier to manage memory better, e.g. by using growable non-contiguous lists over arrays, model data closer to their real life existence like a tree.

With the heap allocation life seemed simpler at first but actually became harder. Robustness nose-dived. Memory allocated dynamically had to be managed carefully because if allocated memory is not de-allocated after it’s use is over, it becomes garbage and un-available (called memory leak) and slowly runs out of space. At the end the dreaded out of memory scenario comes up where there is no more memory left to be allocated to the requestor and the program fails to continue. Heap allocation is also a costly operation and can have severe perf implications.

Even with all the tooling support it still remains hard to locate memory leaks and constitutes one of the harder classes of bugs to be tackled.

Garbage Collection

LISP in 1959 started a new technique called Automatic Memory Management known by the more popular term Garbage Collection (GC). This tries to address the memory leak issue by needing explicit memory allocation but removing the need to de-allocate memory. Instead it provides language facilities that actually hunt down the un-used memory and automatically free them without user-code intervention.

As you might guess that even though GC increases robustness and reduces coding overhead significantly it also has performance implications. This makes using GC in hard in a whole bunch of scenarios. E.g. you typically do not expect to see a GC being used for a real-time system or a system driver (but there are exceptions to this as well); but you do expect to see it in a web-development platform that manages huge amount of memory and can sometimes live with a bit of response delay when the GC is actually running.

Putting it all together

Most modern programming languages support all three forms of storage. E.g. C++ or C# supports all 3.

Even though all of them might be available at the same time, the choice of usage is key to ensure robustness and meet performance goals of a program. Unfortunately a lot of developers take a casual approach to it and later land up into trouble when the memory foot-print become larger and harder to handle.

Consider the following pseudo-code

void foo()
{
    MyType m1;                                   // Option-1 stack allocation
    MyType* m2 = AllocateOnHeap(sizeof(MyType)); // Option-2 heap allocation
    ...
    if (SomeCond)
       foo();     // recursive call    
    ...
    DeAllocate(m);
}

-

Here foo is called in recursion. If MyType is of significant size and we use option-1 of using stack allocation then the depth of recursion supported by the method will be significantly reduced because each function call will need additional stack space to accommodate MyType. However, if we use heap (Option-2) then the stack needed will be significantly lower (increase in depth of recursion) but since heap allocation is much slower the speed will suffer. Based on the size of MyType, the need of the program the allocation would have to be carefully chosen.

Based on target domain different languages have chosen

When the spell checkers attack

Today Boing Boing had a post about the Cupertino effect in which spell-checkers erroneously change valid words. I had worked on Adobe Acrobat and Adobe FrameMaker's spell checking feature and do happen to appreciate the headache with getting them right.

I face Cupertino effect most often while typing in Indian names because most word-processors don't recognize them. For my wife's name Somtapa the offered spelling is Stomata followed by Sumatra. So I started calling her Stomata until it got onto her nerves and something very similar to the photo above happened to me

Is interlocked increment followed by comparison thread safe?

Sorry about the blog title, my imagination failed me :(.

In our internal alias someone asked the question "Is the following thread safe"

if(Interlocked.Increment(ref someInt) == CONSTANT_VAL)
{
    doSomeStuff();
}

My instant reaction was no because even though the increment is done in a thread safe way using System.Threading.Interlocked class, the comparison that follows is not safe.

My reasoning was that the "if" expression can be broken down to the following operations

1. Fetch of someInt
   
2. Increment operation
   
3. Write back of someInt
   
4. Comparison

The first 3 are done inside the Increment method and it provides concurrency protection and hence cannot be interleaved by another instruction.

So if two threads are running in parallel (one marked in red and the other in green) I assumed that the following interleaving is possible

1. someInt is 4 and CONSTANT_VAL is 5
   
2. Fetch of someint      -> someInt ==4
   
3. Increment operation   -> someInt ==5
   
4. Write back of someint -> someInt ==5
   
5. Fetch of someint      -> someInt == 5
   
6. Increment operation   -> someInt == 6
   
7. Write back of someint -> someInt == 6
   
8. comparison            -> compare 6 & CONSTANT_VAL
   
9. comparison            -> compare 6 & CONSTANT_VAL

This means that the comparison of both thread will fail.

However, someone responded back that I was wrong as the return value is being used and not the written back value. This made me do some more investigation.

If I see the JITted code then it looks like

if (Interlocked.Increment(ref someInt) == CONSTANT_VAL)
00000024  lea         ecx,ds:[002B9314h] 
0000002a  call        796F1221 
0000002f  mov         esi,eax 
00000031  cmp         esi,5

The call (at 0x000002a) is to the native code inside CLR which in turn calls Win32 api (InterlockedIncrement).

However, the last 2 lines are the interesting ones. Register EAX contains the return value and comparison is happening against that and CONSTANT_VAL. So even if the second thread had already changed the value of someInt it doesn’t have any effect as the return of the first increment is being used and not the safeInt value in memory. So first comparison (step 8 above) will actually compare CONSTANT_VAL against 5 and succeed.

C/C++ Compile Time Asserts

The Problem

Run time asserts are fairly commonly used in C++. As the MSDN documentation for assert states

"(assert) Evaluates an expression and, when the result is false, prints a diagnostic message and aborts the program."

There is another type of asserts which can be used to catch code issues right at the time of compilation. These are called static or compile-time asserts. These asserts can be used to do compile time validations and are very effectively used in the .NET Compact Framework code base.

E.g. you have two types Foo and Bar and your code assumes (may be for a reinterpret_cast) that they are of the same size. Now being in separate places there is always a possibility that someone modifies one without changing the other and that results in some weird bugs. How do you express this assumption in code? Obviously you can do a run-time check like

assert(sizeof(foo) == sizeof(bar));

If that code is not hit during running this assert will not get fired. This might be caught in testing later. However, if you notice carefully all of the information is available during compilation (both the type and the sizeof is resolved while compilation). So we should be able to do compile time validation, with-something to the effect

COMPILE_ASSERT(sizeof(int) == sizeof(char));

This should be tested during compilation and hence whether the code is run or not the assert should fail.

The Solution

There are many ways to get this done. I will discuss two quick ways

Array creation

You can create a MACRO expression as follows

#define COMPILE_ASSERT(x) extern int __dummy[(int)x]

This macro works as follows

// compiles fine 
COMPILE_ASSERT(sizeof(int) == sizeof(unsigned)); 
// error C2466: cannot allocate an array of constant size 0
COMPILE_ASSERT(sizeof(int) == sizeof(char)); 

The first expression gets expanded to int __dummy[1] and compiles fine, but the later expands to int __dummy[0] and fails to compile.

The advantage of this approach is that it works for both C and C++, however, the failure message is very confusing and doesn't indicate what the failure is for. It is left to the developer to visit the line of compilation failure to see that it's a COMPILE_ASSERT.

sizeof on incomplete type

This approach works using explicit-specialization of template types and the fact that sizeof of incomplete types fail to compile.

Consider the following

namespace static_assert
{
    template <bool> struct STATIC_ASSERT_FAILURE;
    template <> struct STATIC_ASSERT_FAILURE<true> { enum { value = 1 }; };
}

Here we defined the generic type STATIC_ASSERT_FAILURE. As you see the type is incomplete (no member definition). However we do provide a explicit-specialization of that type for the value true. However, the same for false is not provided. This means that sizeof(STATIC_ASSERT_FAILURE<true>) is valid but sizeof(STATIC_ASSERT_FAILURE<false>) is not. This can be used to create a compile time assert as follows

namespace static_assert
{
    template <bool> struct STATIC_ASSERT_FAILURE;
    template <> struct STATIC_ASSERT_FAILURE<true> { enum { value = 1 }; };

    template<int x> struct static_assert_test{};
}

#define COMPILE_ASSERT(x) \
    typedef ::static_assert::static_assert_test<\
        sizeof(::static_assert::STATIC_ASSERT_FAILURE< (bool)( x ) >)>\
            _static_assert_typedef_

Here the error we get is as follows

// compiles fine
COMPILE_ASSERT(sizeof(int) == sizeof(unsigned)); 
// error C2027: use of undefined type 'static_assert::STATIC_ASSERT_FAILURE<__formal>
COMPILE_ASSERT(sizeof(int) == sizeof(char)); 

So the advantage is that the STATIC_ASSERT_FAILURE is called out right at the point of failure and is more obvious to figure out

The macro expansion is as follows

1. typedef static_assert_test< sizeof(STATIC_ASSERT_FAILURE<false>) >  _static_assert_typedef_
   
2. typedef static_assert_test< sizeof(incomplete type) >  _static_assert_typedef_

Similarly for true the type is not incomplete and the expansion is

1. typedef static_assert_test< sizeof(STATIC_ASSERT_FAILURE<true>) >  _static_assert_typedef_
   
2. typedef static_assert_test< sizeof(valid type with one enum member) >  _static_assert_typedef_
   
3. typedef static_assert_test< 1 > _static_assert_typedef_

Put it all together

All together the following source gives a good working point to create static or compile time assert that works for both C and C++

#ifdef __cplusplus

#define JOIN( X, Y ) JOIN2(X,Y)
#define JOIN2( X, Y ) X##Y

namespace static_assert
{
    template <bool> struct STATIC_ASSERT_FAILURE;
    template <> struct STATIC_ASSERT_FAILURE<true> { enum { value = 1 }; };

    template<int x> struct static_assert_test{};
}

#define COMPILE_ASSERT(x) \
    typedef ::static_assert::static_assert_test<\
        sizeof(::static_assert::STATIC_ASSERT_FAILURE< (bool)( x ) >)>\
            JOIN(_static_assert_typedef, __LINE__)

#else // __cplusplus

#define COMPILE_ASSERT(x) extern int __dummy[(int)x]

#endif // __cplusplus

#define VERIFY_EXPLICIT_CAST(from, to) COMPILE_ASSERT(sizeof(from) == sizeof(to)) 

#endif // _COMPILE_ASSERT_H_

The only extra part is the JOIN macros. They just ensure that the typedef is using new names each time and doesn't give type already exists errors.

More Reading

1. Boost static_assert has an even better implementation that takes cares of much more scenarios and compiler quirks. Head over to the source at http://www.boost.org/doc/libs/1_36_0/boost/static_assert.hpp
   
2. Modern C++ Design by the famed Andrei Alexandrescu

Taking my job more seriously

I generally take my work very seriously. However, the following from SICP was still my favorite quote

"I think that it's extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don't think we are. I think we're responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don't become missionaries. Don't feel as if you're Bible salesmen. The world has too many of those already. What you know about computing other people will learn. Don't feel as if the key to successful computing is only in your hands. What's in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.''

However, couple of days back I was lying in a cold room with a doctor probing my Thyroid gland with ultrasound beams. She went on explaining the details of the tumor that I had, pointing to the screen. In my mind I was thinking about folks who have to code for these things and how careful they need to be.

The first thing I did when I came out of the room is search for whether .NET Compact Framework gets used for these kinds of equipment. Of the hundreds of pages I hit the one titled "Control System for Lung Ventilation Equipment with Windows CE , Microsoft .Net Compact Framework and Visual Studio Team System" struck me. Mostly because it had two products I personally coded for (NETCF and VSTS). There were even more life saving equipment listed on the search page.

It was a very humbling experience. I made a little vow, I'll be more careful when I code from tomorrow.

Silverlight on Nokia S60 devices

In many of my blog posts (e.g.here and here) I refer to .NET Compact Framework and Symbian OS (S60) and obviously folks keep asking me via comments (or assume) that we are porting .NETCF on S60 devices. So I thought it's time to clarify :)

The short answer is that we are not porting .NETCF to S60 devices, but we are porting the Silverlight on S60 devices. This was jointly announced by Microsoft and Nokia, read Nokia's press release here.

We are in very early stage of development and it is very hard to tell how much will be in it (e.g. will it be SL v1.0 or v2.0). However, we are working hard and as and when more details emerge I will share it out from this blog. So keep reading.

Who halted the code

Today a bed time story involving un-initialized variable access and a weird coincidence.

Couple of weeks back I was kind of baffled with a weird issue I was facing with the .NET Compact Framework Jitter. We were making the Jitter work for Symbian OS (S60) emulator. The S60 emulator is a Windows process and hence we needed to bring up the i386 Jitter in our code base. After running some JITted code the application would stop executing with the message "Execution halted" in the stack trace.

Now obviously the user didn't halt anything and the program was a simple hello world.

After some debugging I found an interesting thing. For the debug build the Symbian C compiler memsets un-initialized variables to 0xcccc. This is fairly standard and is used to catch un-initialized variable access.

However, our Jit code had a bug such that in some scenario it was not emitting function call/returns correctly. So instead of returning we were executing arbitrary memory. But instead of some sort of access violation (or some thing equally bad) the execution was actually halting.

The reason was we started executing un-initialized data. Now this data is 0xcccc. The S60 debugger uses interrupt 3 (INT 3) for inserting breakpoints and the following line reveals the rest of the story

For i386 the instruction used for inserting breakpoint and the pattern used for un-initialized data matched and the debugger thought that it hit a breakpoint.

Hex signatures

Frequently in code we need to add bit patterns or magic numbers. Since hex numbers have the alphabets A-F folks become creative and create all kinds of interesting words. Typical being 0xDEAD, 0xBEEF, 0xFEED or various combination of these like 0xFEEDBEEF. However, someone actually used the following in a sample

0xbed1babe

No naming the guilty :)

Back To Basics: Finding your stack usage

Handling stack overflow is a critical requirement for most Virtual Machines. For .NET Compact framework (NETCF) it is more important because it runs on embedded devices with very little memory and hence little stack space.

The .NETCF Execution Engine (EE) needs to detect stack overflows and report it via StackOverflowException. To do this it uses some logic which we internally refer to as StackCheck (that will be covered in a later post). The algorithm needs fair prediction of stack usage for system APIs (e.g. Win32 APIs or for Symbian OS, S60 APIs).

Each time we target a new platform we do some measurements in addition to referring to specs :) to find it's stack characteristics. As we are currently making the NETCF work on Symbian OS we are doing these measurements again. So I thought of sharing how we are going about measuring stack usage using simple watermarking.

The technique

Step:1

On method Entry store the two current and max stack values. This typically available via system APIs which in case of Symbian is available over the TThreadStackInfo class (iBase, iLimit and other members).

                       +---------------+
                       |               |
                       |               |
                       |               |
current stack ------>  +---------------+
                       |               |
                       |   Available   |
                       |    Stack      |
                       |               |
                       |               |
                       |               |
                       |               |
Stack limit ---------> +---------------+
                       |               |
                       |               |
                       .               .
                       .               .
                       .               . 

Step :2

Get a pointer on to the current stack pointer. How to get the pointer will vary based on the target platform. Options include system APIs, de-referencing stack pointer register (e.g. ESP register on x86) or simply creating a local variable on the stack and getting it's pointer.

Then Memset the whole region from current stack to the total available with some known pattern, e.g. 0xDEAD (a larger signature is a better approach to ensure there is no accidental match)

                       +---------------+
                       |               |
                       |               |
                       |               |
current stack ------>  +---------------+
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
Stack limit ---------> +---------------+
                       |               |
                       |               |
                       .               .
                       .               .
                       .               . 

Step: 3

Make an OS or whatever call you want to measure.

                       +---------------+
                       |               |
                       |               |
                       |               |
current stack ------>  +---------------+
                       |     1231      | --+
                       |     1231      |   |
                       |     D433      |   +--> Stack usage
                       |     D324      |   |
                       |     3453      | --+
                       |     DEAD      |
                       |     DEAD      |
                       |     DEAD      |
Stack limit ---------> +---------------+
                       |               |
                       |               |
                       .               .
                       .               .
                       .               . 

Step 4:

When the call returns the stack will get modified. Iterate through the memory starting from the current stack pointer looking for the first occurrence of the pattern you’ve set in Step:2. This is the water mark and is the point till which the stack got used by the OS call. Subtract the water mark from the original entry point saved in Step 1 and you have the stack usage.