When you read programming language holy wars, what irritates me is that when .NET compares to Go then magically arguments about GC start floating around, that some GC is magically better then others. I found that super irrational to that degree so I decide to do at least something.

My problem with GC comparison is that they obviously vague, cannot be proven and usually assume that GC is always come with runtime. And at this point, I don’t think it’s fair call that GC, and no CLR/JVM/Go runtime. So in order to fuel pointless debates, and because it’s fun, I think I can rip .NET GC out of dotnet/runtime repository and package it in the separate application which can be used for illustrative purposes.

As basis for this I would take hidden gem in the src/coreclr/gc/samples subfolder. Tehcnically you can just grab dotnet repo, clone it and build using ./build.cmd -s clr then you will have somewhere in the artifacts folder file gcsample.exe. That’s probably easy way, but not really convinient if some hothead decide that it’s inspirational enough and want more of GC. So I decide to unbundle build of GC sample from whole .NET build. Curent work in the repository on Codeberg. BTW, move your projects from GitHub to other forge.

Setup

Setup for building GC sample is have my repo folder, and dotnet/runtime in the runtime folder alongside with gcsample folder where actual work happens. I decide that this is easier for me since, I don’t like to have multiple cloned variants of runtime laying around. You may easiely tweak this to use submodules if you into that kind of things.

How to integrate GC into your application

GC by itself do not run in isolation, and it needs some basic runtime support for it’s work. Basically it have two important abstractions PAL/OS interface and runtime (or execution engine) support. PAL/OS interface is gratefully provided by CoreCLR itself. But the interface to EE we should provide by ourselves. For that we should implement following classes

  • GCToEEInterface this is an interface to execution engine
  • Thread this is abstraction to thread. This is not nescessary OS thread, it can be green thread if runtime will implement it.

We also implement helper class ThreadStore which will be abstraction over working with threads in the runtime.

GC does not ask us much out of API for Thread class. We would like to store allocation context and that would be enough to have minimal GC in our process. The more feature we add to our runtime, the more things we will add to this class and other plumbing. Note: The Thread here by design is virual thread which not nescessary should correspond 1-on-1 to OS thread abstraction.

class Thread
{
    uintptr_t m_alloc_context[16]; // Reserve enough space to fix allocation context

    friend class ThreadStore;
    Thread * m_pNext;

public:
    Thread()
    {
    }

    alloc_context* GetAllocContext()
    {
        return (alloc_context *)&m_alloc_context;
    }
};

ThreadStore would be also really simple.

class ThreadStore
{
public:
    // Get thread list starting from current thread.
    static Thread * GetThreadList(Thread * pThread);

    // Enlist current OS thread to be used for GC on it.
    static void AttachCurrentThread();
};

We don’t really need much out of EE interface. We definitely need interface for threads. Let’s look at the API which cover absolute minimum required

// Get Thread abstraction for the current thread.
Thread* GCToEEInterface::GetThread();

The GC uses Thread class later to get access to allocation context and do all magic.

Additional thread related functions.

// Get allocation conext for the curent thread.
gc_alloc_context * GCToEEInterface::GetAllocContext();

// Execution fn on the all allocation contexts with given parameter.
void GCToEEInterface::GcEnumAllocContexts (enum_alloc_context_func* fn, void* param);

// Get Id of the OS thread on which virtual thread running. 
uint64_t GCToEEInterface::GetThreadOSThreadId(Thread* thread)

// Start background GC thread
bool GCToEEInterface::CreateThread(void (*threadStart)(void*), void* arg, bool is_suspendable, const char* name)

Currently GCToEEInterface::GetAllocContext is mostly GCToEEInterface::GetThread()->GetAllocContext() and only used in DAC from what I see. Maybe that can be removed, or it’s here for standalone interface compatibility. I don’t know.

There other important parts of the GC to execution engine interface is suspension/resuming of EE.

// Ask execution engin to suspend it's operation for specific reason.
void GCToEEInterface::SuspendEE(SUSPEND_REASON reason);

// Request execution engine to start operation.
void GCToEEInterface::RestartEE(bool /*_bFinishedGC*/);

there two values for SUSPEND_REASON

  • SUSPEND_FOR_GC which is for actual GC collection
  • SUSPEND_FOR_GC_PREP is for starting GC when background collection started, or when count of heaps changing. in the background GC.

I also comment out bFinishedGC parameter, since it’s not actually used anywhere in current GC.

Our implmentation would be simple, we just callback into global GC heap g_theGCHeap, and say that we are done.

void GCToEEInterface::SuspendEE(SUSPEND_REASON reason)
{
    // TODO: Implement EE suspention if we actually have EE.
    g_theGCHeap->SetGCInProgress(true);
}

void GCToEEInterface::RestartEE(bool bFinishedGC)
{
    // TODO: Implement EE restart if we actually have EE.
    g_theGCHeap->SetGCInProgress(false);
}

The g_theGCHeap have type IGCHeapInternal which is internal interface of GC which is used by execution engine to ask GC to do some work. That interface derived from IGCHeap. This is quite large interface to learn, but we can do that only when needed.

Last part which is needed for minimum GC hosting is providing method table for free object. This method table pointer which indicates that this area of memory is free.

MethodTable* GCToEEInterface::GetFreeObjectMethodTable();

Current implementation of GC uses array-like method table for marking free tables. We just use machinery which are currently in-place for that.

static MethodTable freeObjectMT;

MethodTable* GCToEEInterface::GetFreeObjectMethodTable()
{
    freeObjectMT.InitializeFreeObject();
    return &freeObjectMT;
}

After that all other methods of GCToEEInterface can be implemented as no-op.

The populating runtime metadata

Let’s convert simple C# application to C++ application

// One class declaration
class My
{
    public My m_pOther1;
    public int dummy_inbetween;
    public My m_pOther2;
}

// The actual application
My pObj = new My();
for (int i = 0; i < 1000000; i++)
{
    var pBefore = pObj.m_pOther1;
    var p = new My();
    var pAfter = pObj.m_pOther1;
    pObj.m_pOther1 = p;
}

var ohWeak = WeakReference.Create(pObj);
pObj = null;
GC.Collect();
Debug.Assert(ohWeak.IsAlive == false);

The C# class My would looks like this in C++.

class My : public Object {
public:
    Object * m_pOther1;
    int dummy_inbetween;
    Object * m_pOther2;
};

Now we should define method table for this class.

struct My_MethodTable
{
    // GCDesc
    CGCDescSeries m_series[2 /* Count of managed fields */];
    size_t m_numSeries; // Would be 2, to indicate size of m_series

    // The actual methodtable
    MethodTable m_MT;
};

GC expects MethodTable to be preceding with information about

  • count of GC managed series of objects;
  • array of descriptors for GC managed series of objects. One nice trick is that to make pointers appear as normal C++ pointers, negative offset is used for accessing m_numSeries and m_series from MethodTable* pointer.

Let’s populate My_MethodTable structure. We need three things

  • size of the managed object
  • mark object as not-array
  • mark object as object having managed pointers.

Let’s do that.

Calculating size of managed object is very simple. It’s size is regular C++ size of an object + size of ObjHeader. Also size cannot be less then MIN_OBJECT_SIZE, which is currently size of 2 pointers + size of ObjHeader.

In C++ it would be like this.

// 'My' contains the MethodTable*
uint32_t baseSize = sizeof(My);
// GC expects the size of ObjHeader (extra void*) to be included in the size.
baseSize = baseSize + sizeof(ObjHeader);
// Add padding as necessary. GC requires the object size to be at least MIN_OBJECT_SIZE.
My_MethodTable.m_MT.m_baseSize = max(baseSize, (uint32_t)MIN_OBJECT_SIZE);

My_MethodTable.m_MT.m_componentSize = 0;    // Array component size
My_MethodTable.m_MT.m_flags = MTFlag_ContainsGCPointers;

CGCDescSeries is an descriptor of GC series of managed pointers withing an object. It contains offset of the managed pointer series and adjusted size of the managed pointer series. Adjustment is made so internals can handle regular pointer to object and pointer to array of managed objects in same way.

My_MethodTable.m_numSeries = 2;

// The GC walks the series backwards. It expects the offsets to be sorted in descending order.
My_MethodTable.m_series[0].SetSeriesOffset(offsetof(My, m_pOther2)); // Specify offset inside My class.
My_MethodTable.m_series[0].SetSeriesCount(1); // Set count of managed pointers in series.
My_MethodTable.m_series[0].seriessize -= My_MethodTable.m_MT.m_baseSize; // Perform adjustment (this is how internals works.)

My_MethodTable.m_series[1].SetSeriesOffset(offsetof(My, m_pOther1));
My_MethodTable.m_series[1].SetSeriesCount(1);
My_MethodTable.m_series[1].seriessize -= My_MethodTable.m_MT.m_baseSize;

As you may notice, GCDescSeries objects layed out in memory in different order, since we use negative offset, so m_series[0] is information about last managed pointer within class — m_pOther2. More can be read in the GCDesc.h file

Once we populate that structure, we can obtain pointer to MethodTable* which is used for object allocation like this.

MethodTable * pMyMethodTable = &My_MethodTable.m_MT;

This value is what’s used, but GC knows that pMyMethodTable[-1] is m_numSeries, and walking from that it can obtain m_series content.

Initialization of our execution engine

Now we should initialize our execution engine and GC. The process is following

  • Initialize GC to EE interface
  • Ask GC to start initialization and give us internals
  • Initialize parts of GC which are requried for us
  • Initialize threads
  • Initialize method tables

that would looks like this

// Initialize system info
if (!GCToOSInterface::Initialize())
{
    return -1;
}

// Initialize GC heap
GcDacVars dacVars;
IGCHeap *pGCHeap;
IGCHandleManager *pGCHandleManager;
if (GC_Initialize(nullptr, &pGCHeap, &pGCHandleManager, &dacVars) != S_OK)
{
    return -1;
}

if (FAILED(pGCHeap->Initialize()))
    return -1;

// Initialize handle manager
if (!pGCHandleManager->Initialize())
    return -1;

// Initialize current thread
ThreadStore::AttachCurrentThread();

InitMethodTables();
MethodTable * pMyMethodTable = &My_MethodTable.m_MT;

Half of the things are given us by .NET team, other half was explained by me, so hopefully everything is clear.

Object allocation

The process of objcet allocation is relatively simple conceptually.

  • We take alloaction context from thread,
  • get size of the object to allocated from method table,
  • then ask GC to allocate space
  • Assign method table to the pointer.

That can be implemented like this.

// The fast paths for object allocation and write barriers is performance critical. They are often
// hand written in assembly code, etc.
// What you see here is super slow implementation for educational purposes.
Object * AllocateObject(MethodTable * pMT)
{
    alloc_context * acontext = GetThread()->GetAllocContext();

    size_t size = pMT->GetBaseSize();
    Object * pObject = g_theGCHeap->Alloc(acontext, size, 0);
    if (pObject == NULL)
        return NULL;

    pObject->RawSetMethodTable(pMT);

    return pObject;
}

but in real execution engine, that implementation is too slow, and you want in runtime have fast path which duplicate fast path of GC.

One optimization in C++ can be written like this.

Object * AllocateObject(MethodTable * pMT)
{
    alloc_context * acontext = GetThread()->GetAllocContext();
    Object * pObject;

    size_t size = pMT->GetBaseSize();

    uint8_t* result = acontext->alloc_ptr;
    uint8_t* advance = result + size;
    if (advance <= acontext->alloc_limit)
    {
        acontext->alloc_ptr = advance;
        pObject = (Object *)result;
    }
    else
    {
        pObject = g_theGCHeap->Alloc(acontext, size, 0);
        if (pObject == NULL)
            return NULL;
    }

    pObject->RawSetMethodTable(pMT);

    return pObject;
}

I move bumpting of current allocation pointer on the allocation context in simple cases. that’s exactly how gc_heap::allocate works, but you don’t do down the abstractions well, to trigger that, and short circuit that. Further, it is practical to write this code in assembly to control exact output of the machine code to get more bits of perf.

Write barrier

Last piece of puzze for our execution environment would be write barrier where our primitive EE help GC by informing what we change some parts of data. GC uses card table to track each 256 bytes of managed heap. That block of 256 bytes called card. Card table is collection of bytes, each byte representing 256 bytes or managed heap. If value of byte in card table is 0xFF, then card is dirty, and GC knows, that it should look more closely into this objects to understand what’s to keep and what to throw away.

So write barrier is just

  • writing new value to the managed object
  • updating card table.
#if defined(HOST_64BIT)
// Card byte shift is different on 64bit.
#define card_byte_shift     11
#else
#define card_byte_shift     10
#endif

#define card_byte(addr) (((size_t)(addr)) >> card_byte_shift)

inline void ErectWriteBarrier(Object ** dst, Object * ref)
{
    // if the dst is outside of the heap (unboxed value classes) then we
    //      simply exit
    if (((uint8_t*)dst < g_gc_lowest_address) || ((uint8_t*)dst >= g_gc_highest_address))
        return;

    // volatile is used here to prevent fetch of g_card_table from being reordered
    // with g_lowest/highest_address check above. See comments in StompWriteBarrier
    uint8_t* pCardByte = (uint8_t *)*(volatile uint8_t **)(&g_gc_card_table) + card_byte((uint8_t *)dst);
    if(*pCardByte != 0xFF)
        *pCardByte = 0xFF;
}

// Here our function which we will use in our C++ application with managed memory.
void WriteBarrier(Object ** dst, Object * ref)
{
    *dst = ref;
    ErectWriteBarrier(dst, ref);
}

Conversion of program

Now it’s time to convert program presented earlier.

// Allocate instance of MyObject
Object * pObj = AllocateObject(pMyMethodTable);
if (pObj == NULL)
    return -1;

// Create strong handle and store the object into it
// We need strong handle, otherwise value would be eliminated as part of GC somewhere in the middle.
OBJECTHANDLE oh = HndCreateHandle(g_HandleTableMap.pBuckets[0]->pTable[GetCurrentThreadHomeHeapNumber()], HNDTYPE_DEFAULT, pObj);
if (oh == NULL)
    return -1;

for (int i = 0; i < 1000000; i++)
{
    My * pBefore = ((My *)HndFetchHandle(oh))->m_pOther1;

    // Allocate more instances of the same object
    Object * p = AllocateObject(pMyMethodTable);
    if (p == NULL)
        return -1;

    My * pAfter = ((My *)HndFetchHandle(oh))->m_pOther1;

    // See how GC triggered inside AllocateObject moved objects around
    if (pBefore != pAfter)
        printf("GC moved object from %p to %p at iteration %d\n", pBefore, pAfter, i);

    // Store the newly allocated object into a field using WriteBarrier
    WriteBarrier((Object **)&(((My *)HndFetchHandle(oh))->m_pOther1), p);
}

// Create weak handle that points to our object
OBJECTHANDLE ohWeak = HndCreateHandle(g_HandleTableMap.pBuckets[0]->pTable[GetCurrentThreadHomeHeapNumber()], HNDTYPE_WEAK_DEFAULT, HndFetchHandle(oh));
if (ohWeak == NULL)
    return -1;

// Destroy the strong handle so that nothing will be keeping out object alive
HndDestroyHandle(HndGetHandleTable(oh), HNDTYPE_DEFAULT, oh);

// Explicitly trigger full GC
pGCHeap->GarbageCollect();

// Verify that the weak handle got cleared by the GC
assert(HndFetchHandle(ohWeak) == NULL);
printf("Weak handle cleared by GC\n");

printf("Done\n");

If you want to look at whole source code as one file, and play with it - goto repository on Codeberg. Have fun!