Write a .NET garbage recyrator with C# (2)

Write a .NET garbage recyrator with C# (2)

existFirst partAmong them, we prepared the project and fixed the initialization problem caused by the Nativeaot tool chain. In this section, we will begin to realize our own GC (garbage recovery). The current goal is to build a simple GC as possible so that it can run basic .NET applications. This GC will only allocate memory allocation without recycling memory, similar toBump-Pointer GC proposed by Konrad Kokosa(Packing pointer GC).

The first step is to write the local interfaces required by GC. Currently there are the following four interfaces:

• IGCToCLR: Provide an execution engine API (such as hanging threads) for GC calls.
• IGCHeap: Main GC API.
• IGCHandleManager: Provide APIs that create or destroy the handle.
• IGCHandleStore: The underlying storage used by the handle manager.

in,IGCToCLRProvided by runtime, and the other three interfaces need to be implemented by GC.

In order to handle the interoperability with the local code, we will use the sameNativeObjects Library. What we need to do is define interfaces in C# and use[NativeObject]Sign the characteristics:

[NativeObject]
public unsafe interface IGCHeap
{
    /// <summary>
    /// Returns whether or not the given size is a valid segment size.
    /// </summary>
    bool IsValidSegmentSize(nint size);

    /// <summary>
    /// Returns whether or not the given size is a valid gen 0 max size.
    /// </summary>
    bool IsValidGen0MaxSize(nint size);

    /// <summary>
    /// Gets a valid segment size.
    /// </summary>
    nint GetValidSegmentSize(bool large_seg = false);

    [...]
}

Next, we can obtain the implementation of the interface through two ways:

1. Get the local pointer of the managed implementation.

   var gcHeap = new GCHeap();
   IntPtr gcHeapPtr = (gcHeap);
   // Give the pointer to native code
   // ...
   

2. Get the local custody pointer (Managed Pointer).

   // Receive the pointer from native code
   IntPtr ptr = ...
   var gcHeap = (ptr);
   // Use gcHeap like a normal managed object
   

These managed interfaces are essentiallyC# conversion version of C++ interface in .NET source code, so I won't introduce it in detail here.

Handle Store

The GC handle (GC Handles) is a very basic concept during the runtime of .NET. Even our simple GC needs to provide a certain degree of support. Fortunately, because of our GCMemory will not be released or moved, we can currently adopt a relatively simple implementation method.

A GC handle contains the following three parts of information:

1. Handle(Weak reference, strong reference, fixed reference (PINNED), etc.).
2. Object address(The memory address of the object pointed by the handle).
3. An extra information field with a pointer size(Used to store additional metadata).

Therefore, we can use a structure to represent the GC handle:

[StructLayout()]
public struct ObjectHandle
{
    public nint Object;
    public nint ExtraInfo;
    public HandleType Type;

    public override string ToString() => $"{Type} - {Object:x2} - {ExtraInfo:x2}";
}

public enum HandleType
{
    HNDTYPE_WEAK_SHORT = 0,
    HNDTYPE_WEAK_LONG = 1,
    HNDTYPE_WEAK_DEFAULT = 1,
    HNDTYPE_STRONG = 2,
    HNDTYPE_DEFAULT = 2,
    HNDTYPE_PINNED = 3,
    HNDTYPE_VARIABLE = 4,
    HNDTYPE_REFCOUNTED = 5,
    HNDTYPE_DEPENDENT = 6,
    HNDTYPE_ASYNCPINNED = 7,
    HNDTYPE_SIZEDREF = 8,
    HNDTYPE_WEAK_NATIVE_COM = 9
}

At present, not all handle types require additional information. Therefore, in theory, we can design special structures for different handle types to save space. But for our simple GC, this is not important, so this optimization will not be made.

Currently, we can use aFixed size arrayTo store the handle. In order to simplify the realization, we have the maximum number of handle to be coded as to10,000This quantity is enough to support the operation of the test application. However, due to our GCDo not recycle memory, which means that for applications with longer run time, the handle will always be exhausted. Therefore, we may need to redesign this part of the logic in the future.

public unsafe class GCHandleStore : IGCHandleStore
{
    private const int MaxHandles = 10_000;

    private readonly  _nativeObject;
    private readonly ObjectHandle* _store;
    private int _handleCount;

    public GCHandleStore()
    {
        _nativeObject = (this);
        _store = (ObjectHandle*)(MaxHandles, (nuint)sizeof(ObjectHandle));
    }

    public IntPtr IGCHandleStoreObject => _nativeObject;

    // TODO: Implement IGCHandleStore methods
}

IGCHandleStoreObjectProperties are used to exposeLocal pointer(Native pointer) to pass it to .NET.

Design choices about handle storage

In the process of implementation, I have considered using itFixedObjectHandle[]Array(and throughpinnedKeywords are fixed for its address) to replace directly using local memory. However, in the end I think this approach is "cheering", so it is decided to rely only on Nativeaot GCTo manage the metadata structureAnd the content of all exposure to the .NET should manually manage and store them in local memory.

Now we can achieve handle generation.IGCHandleStoreMultiple methods of the interface run the same logic:

public unsafe ref ObjectHandle CreateHandleOfType(GCObject* obj, HandleType type)
{
	return ref CreateHandleWithExtraInfo(obj, type, null);
}

public unsafe ref ObjectHandle CreateHandleOfType2(GCObject* obj, HandleType type, int heapToAffinitizeTo)
{
	return ref CreateHandleWithExtraInfo(obj, type, null);
}

public unsafe ref ObjectHandle CreateDependentHandle(GCObject* primary, GCObject* secondary)
{
	return ref CreateHandleWithExtraInfo(primary, HandleType.HNDTYPE_DEPENDENT, secondary);
}

public unsafe ref ObjectHandle CreateHandleWithExtraInfo(GCObject* obj, HandleType type, void* pExtraInfo)
{
    var index = (ref _handleCount) - 1;

    if (index >= MaxHandles)
    {
    ("Too many handles");
    }

    ref var handle = ref _store[index];

     = (nint)obj;
     = type;
     = (nint)pExtraInfo;

    return ref handle;
}

GCObject*Represents a pointCustody object(Managed Object) pointer. Although we will not solve the references (derference) at present,GCObjectThe layout of the structure imitates the hosted object format during the .NET runtime.

[StructLayout()]
public readonly struct GCObject
{
    public readonly IntPtr MethodTable;
    public readonly int Length;
}

IgchandleStore interfaceAlso exposed oneContainsHandleMethods, but there seems to be no place to actually use it when the .NET runtime. However, because it is relatively simple to achieve, we will still provide this method. In addition, we also added oneDumpHandlesMethods to check the status of the current handle when debugging GC.

public void DumpHandles()
{
    Write("GCHandleStore DumpHandles");

    for (int i = 0; i < _handleCount; i++)
    {
        Write($"Handle {i} - {_store[i]}");
    }
}

public bool ContainsHandle(ref ObjectHandle handle)
{
    var ptr = (ref handle);
    return ptr >= _store && ptr < _store + _handleCount;
}

At present, these realities are enough to meet our needs. However, in the future, we may introduce more complicatedHandle storage mechanism,for example:

• Storage structure based on segment-basedYou can dynamically expand as needed.
• Free-List, Used to reuse the released handle.

Handle Manager

During the runtime of .NET, the management of the handle involved two interfaces:IGCHandleManagerandIGCHandleStore. But why do you need these two different interfaces? Honestly, I'm not sure. Theoretically, these two interfacesCan be merged completely。

From a historical perspective, this may originate from the early design of .NET. At that time, there may be multiple handle storage (Handle Store) at that time, such asAppDomainsRelated mechanisms. However, this situation no longer exists.

IGCHandleManagerMainly provide the following functions:

• UnderlyingIGCHandleStore。
• Read or modify the meta -information of the handle.

so,Execution EngineNo need to care about how GC stores and manage the handle in memory.

internal unsafe class GCHandleManager : IGCHandleManager
{
    private readonly  _nativeObject;
    private readonly GCHandleStore _gcHandleStore;

    public GCHandleManager()
    {
        _gcHandleStore = new GCHandleStore();
        _nativeObject = (this);
    }

    public IntPtr IGCHandleManagerObject => _nativeObject;

    public GCHandleStore Store => _gcHandleStore;

    public bool Initialize()
    {
        return true;
    }

    public IntPtr GetGlobalHandleStore()
    {
        return _gcHandleStore.IGCHandleStoreObject;
    }

    public unsafe ref ObjectHandle CreateGlobalHandleOfType(GCObject* obj, HandleType type)
    {
        return ref _gcHandleStore.CreateHandleOfType(obj, type);
    }

    public ref ObjectHandle CreateDuplicateHandle(ref ObjectHandle handle)
    {
        ref var newHandle = ref _gcHandleStore.CreateHandleOfType((GCObject*), );
         = ;
        return ref newHandle;
    }

    public unsafe void SetExtraInfoForHandle(ref ObjectHandle handle, HandleType type, nint extraInfo)
    {
         = extraInfo;
    }

    public unsafe nint GetExtraInfoFromHandle(ref ObjectHandle handle)
    {
        return ;
    }

    public unsafe void StoreObjectInHandle(ref ObjectHandle handle, GCObject* obj)
    {
         = (nint)obj;
    }

    public unsafe bool StoreObjectInHandleIfNull(ref ObjectHandle handle, GCObject* obj)
    {
        var result = InterlockedCompareExchangeObjectInHandle(ref handle, obj, null);        
        return result == null;
    }

    public unsafe void SetDependentHandleSecondary(ref ObjectHandle handle, GCObject* obj)
    {
         = (nint)obj;
    }

    public unsafe GCObject* GetDependentHandleSecondary(ref ObjectHandle handle)
    {
        return (GCObject*);
    }

    public unsafe GCObject* InterlockedCompareExchangeObjectInHandle(ref ObjectHandle handle, GCObject* obj, GCObject* comparandObject)
    {
        return (GCObject*)(ref , (nint)obj, (nint)comparandObject);
    }

    public HandleType HandleFetchType(ref ObjectHandle handle)
    {
        return ;
    }
}

Notice: Only some of the methods we are currently implemented here. Other andHandle releaseThe relevant methods are not required for the time being, so they have not been implemented.

IGCHeap

IGCHeapIt is the core interface of GC. Usually when we mention the GC API, it is what we think of. This interface is very large, includingUp to 88 methodsBut for usSimplified version GCWe only need to implement some of the key methods.

GCHeapThe constructor of the class andIGCHandleStoreandIGCHandleManagerSimilar implementation, mainly used for itNative interop wrappers (Native Interop Wrappers)。

internal unsafe class GCHeap : 
{
    private readonly IGCToCLRInvoker _gcToClr;
    private readonly GCHandleManager _gcHandleManager;
    private readonly IGCHeap _nativeObject;

    public GCHeap(IGCToCLRInvoker gcToClr)
    {
        _gcToClr = gcToClr;
        _gcHandleManager = new GCHandleManager();

        _nativeObject = (this);
    }

    public IntPtr IGCHeapObject => _nativeObject;
    public IntPtr IGCHandleManagerObject => _gcHandleManager.IGCHandleManagerObject;
}

InitializeThe method is the first key method that GC needs to implement. This method will beEarly early in runningBe called, letting GC prepare everything you need to run the managed code. In the official GC of .NET,InitializeMainly used for:

• Calculate the size of the memory segment (SEGMENT) or region (Region)。
• Heap。
• Make necessary memory management settings。

However, because our GC is justThe most basic implementation, So you don't need to do these complicated initialization. But we still needSet write barrier。

This example is well shownIndependent GC API(Standalone GC API)A layer of packaging around the standard .NET GC, Rather than a reasonable API that truly faces custom GC design. Even if we don't plan to useCard table, the API still does not provide close or modifyWrite barrier, so we still need to initialize correctly.

Fortunately, Konrad Kokosa used one in his GC implementationSkill. existWorkstation GCIn the mode, check the target address before writing the card to write the card tableLocated in the GC management range. We can take advantage of this to make GC'sscopeSet to a special value so that all addresses areOut of this range,therebyIndirect disbuctionWrite a barrier.

public HResult Initialize()
{
    Write("Initialize GCHeap");

    var parameters = new WriteBarrierParameters
    {
        operation = ,
        is_runtime_suspended = true,
        ephemeral_low = -1 // 
    };

    _gcToClr.StompWriteBarrier(&parameters);

    return HResult.S_OK;
}

We canSet the minimum value of the GC address range (ephemeral_low) is the maximum possible addressIn this way, the address of all objects will exceed the scope of GC monitoring. This makes the writing barrier not execute the card table update, so as to achieveThe effect of "blocking" write barrier。

If you don't use this technique, we need:

• Allocate memory for the card tableAnd assign it toWriteBarrierParametersStructuredcard_tableField.
• Make sure that the card table is large enough, can overwrite the entire heap (each byte of card table maps 2KB of memory).

However, this will bringTwo issues：

1. How to manage the boundary of the pile (bookkeeping)?
   We useMemory allocation, and the address range it returns isUnpredictableTherefore, it is difficult for us to calculate the accurate range of the heap.
2. How to allocate a large card table?
   If you cannot dynamically adjust the size, we may need to allocate oneOversizedThe card table is used to adapt to possible stacked size, which will cause memory waste.

Unfortunately, this techniqueAvailable for Workstation GC only. existServer GCIn the mode, the writing barrier does not check whether the target address is within the scope of GC management, soMust provide a valid card table. At present, our solution will not supportServer GC(For our GC, after all,The concept of Server GC itself is meaninglessThis is another example of the design details of the .NET GC design "leaked" to independent GC API).

AllocIt is the core method of GC, it is called whenever a thread needs memory to allocate a new object. Therefore, we must introduce"Allocation Context)The concept.

If the thread must apply to the GC every time the object is allocated, it will lead toSerious performance problems. To solve this problem, GC adoptedAllocation context：

• GC will allocate a piece of memory to each thread, called"Assignment" context "。
• The thread can be in this distribution contextAllocation of objects by yourselfThere is no need to request GC every time.
• Only when all over allocating the context consultedMaybeUnder special circumstances(Such as the object with a terminal), the thread will request the GC for new memory allocation.

Here is the basic structure of the allocation context (i.e., the memory blocks assigned to each thread by GC):

[StructLayout()]
public unsafe struct gc_alloc_context
{
    public nint alloc_ptr;
    public nint alloc_limit;
    public long alloc_bytes;
    public long alloc_bytes_uoh;

    public void* gc_reserved_1;
    public void* gc_reserved_2;
    public int alloc_count;
}

alloc_ptrPoints to the available position in the current allocation context, andalloc_limitThen the end position of the allocation context is marked. In addition, the distribution also contains multiple fields to track the allocation statistics of the thread, and the fields of the two pointer size. These fields are determined by GC how to use themselves. In standard GC, these fields are used to mark the heap associated with threads, and I'm inPrevious articleThis has also used this.

Now, our allocation strategy is kept simple:

1. DeepenAllocAt this time, first check whether there is enough space for the current allocation context:
   • If there is space, we only need to increasealloc_ptr, To complete the object allocation.
   • This method avoids frequent application of memory from GC and improves distribution efficiency.
2. If the allocation context is not large enough:
   • We allocate 32KB of new memory blocks as new allocation context.
   • Special circumstances: If the object to be assigned is greater than32KB, then directlyAllocate accurate memory blocks, Not using standard 32KB blocks.

public GCObject* Alloc(ref gc_alloc_context acontext, nint size, GC_ALLOC_FLAGS flags)
{
    var result = acontext.alloc_ptr;
    var advance = result + size;

    if (advance <= acontext.alloc_limit)
    {
    // The allocation context is big enough for this allocation
    acontext.alloc_ptr = advance;
    return (GCObject*)result;
    }

    // The allocation context is too small, we need to allocate a new one
    var growthSize = (size, 32 * 1024) + ;
    var newPages = (IntPtr)((nuint)growthSize);

    var allocationStart = newPages + ;
    acontext.alloc_ptr = allocationStart + size;
    acontext.alloc_limit = newPages + growthSize;

    return (GCObject*)allocationStart;
}

You may notice that weThe start address of the allocation context is offset(Right nowalloc_ptrMove backwardbyte). The reason is as follows:

• AllocNeed to return oneGCObject*, That is to pointCustody objectpointer.
• In .NET,The reference of the hosting object does not directly point to the starting position of the objectInsteadMethod table pointer of the object。
• In front of the starting position of the object, there is a pointer size field for storageObject Header (Object Header)。
• Therefore, when distributing objects, we need to offset, make sure that the returned pointer points to the Method Table correctly.

+-----------------+ 
| Object header   | 
+-----------------+
| MethodTable*    |   <----- GCObject*
+-----------------+
|                 |
| Data            |
|                 |
+-----------------+

This design is guaranteed.NETWhen accessing an object, the type information and metadata of the object can be correctly found during the runtime.

IGCHeapIn the interface, we also need to implement the last method:GarbageCollect。
At present, we will not really execute garbage recycling (GC), but we canUse it to output debugging information,For example:

• Dump (DUMP) currently stored information。
• Print memory allocation, convenient for subsequent optimization of GC implementation.

public HResult GarbageCollect(int generation, bool low_memory_p, int mode)
{
    Write("GarbageCollect");
    _gcHandleManager.();
    return HResult.S_OK;
}

Basic functions have been completed

We have implemented all the necessary GC interfaces and can now beGC_InitializeMethods GeneralConnect。

[UnmanagedCallersOnly(EntryPoint = "_GC_Initialize")]
    public static unsafe HResult GC_Initialize(IntPtr clrToGC, IntPtr* gcHeap, IntPtr* gcHandleManager, GcDacVars* gcDacVars)
    {
    Write("GC_Initialize");

var clrToGc = (clrToGC);
var gc = new GCHeap(clrToGc);

*gcHeap = ;
*gcHandleManager = ;

return HResult.S_OK;
}

Because our GCDo not support the server GC modeWe need extra codes:

1. passIClrToGCinterfaceGet the GC configuration at the time of running。
2. If Server GC is enabled, the initialization is terminated directly。

Local codeIn the method, parametersMust be a single byte encoding stringAnd .NET'sstringuseUTF-16(Two bytes are stored in one character). In order to avoid string conversion, we useu8Get the suffix directlyUTF-8String.

[UnmanagedCallersOnly(EntryPoint = "_GC_Initialize")]
public static unsafe HResult GC_Initialize(IntPtr clrToGC, IntPtr* gcHeap, IntPtr* gcHandleManager, GcDacVars* gcDacVars)
{
    Write("GC_Initialize");

    var clrToGc = (clrToGC);

    fixed (byte* privateKey = "gcServer"u8, publicKey = ""u8)
    {
        (privateKey, publicKey, out var gcServerEnabled);

        if (gcServerEnabled)
        {
            Write("This GC isn't compatible with server GC. Set DOTNET_gcServer=0 to disable it.");
            return HResult.E_FAIL;
        }
    }

    var gc = new GCHeap(clrToGc);

    *gcHeap = ;
    *gcHandleManager = ;

    return HResult.S_OK;
}

To test this GC, we wrote oneSimple console application, It will:

1. Allocate several objects (including a large object).
2. Operate oneDependentHandle(For verificationIHandleStoreCode).
3. Call(),triggerDumpHandlesCode, output current handle information.

Although the test case is not complicated, it can run completely without collapse! In the console, most log information is the GC method called during runtime, and we have not fully implemented these methods.

In order to verify the GC more rigorous, we tried to runDashboard app (after upgrading to .NET 9 and disabling Server GC), no obvious error was found.

Of course, the current GC still has the following problems:

• All allocated memory cannot be recycled,lead toSerious memory leakage。
• The maximum number of handles is fixedAfter reaching the upper limit, the application will collapse.

Let this GCReally run in production environmentThere are still a lot of work to be completed.

Next, we will add diagnostic code to display details of managed objects for subsequent debugging. This may sound simple, butBecause GC runs in its own operation, it cannot use reflex or .NET standard API to check the hosting object, this brings certain challenges to debugging.

The example code of this article has been uploaded toGitHubInterested readers can download and study by themselves.

Original link

/writing-a-net-gc-in-c-part-2/