How does the C# garbage collector find objects whose only reference is an interior pointer?

Question

In C#, ref and out params are, as far as I know, passed by passing only the raw address of the relevant value. That address may be an interior pointer to an element in an array or a field within an object.

If a garbage collection occurs, it's possible that the only reference to some object is through one of these interior pointers, as in:

using System;

public class Foo
{
    public int field;

    public static void Increment(ref int x) {
        System.GC.Collect();
        x = x + 1;
        Console.WriteLine(x);
    }

    public static void Main()
    {
        Increment(ref new Foo().field);
    }
}

In that case, the GC needs to find the beginning of the object and treat the entire object as reachable. How does it do that? Does it have to scan the entire heap looking for the object that contains that pointer? That seems slow.

Answer 1

The garbage collector will have a fast way to find the start of an object from a managed interior pointer. From there it can obviously mark the object as "referenced" when doing the sweeping phase.

Don't have the code for the Microsoft collector but they would use something similar to Go's span table which has a fast lookup for different "spans" of memory which you can key on the most significant X bits of the pointer depending on how large you choose the spans to be. From there they use the fact that each span contains X number of objets of the same size to very quickly find the header of the one you have. It's pretty much an O(1) operation. Obviously the Microsoft heap will be different since it's allocated sequentially without regard for object size but they will have some sort of O(1) lookup structure.

https://github.com/puppeh/gcc-6502/blob/master/libgo/runtime/mgc0.c

// Otherwise consult span table to find beginning.
// (Manually inlined copy of MHeap_LookupMaybe.)
k = (uintptr)obj>>PageShift;
x = k;
x -= (uintptr)runtime_mheap.arena_start>>PageShift;
s = runtime_mheap.spans[x];
if(s == nil || k < s->start || (const byte*)obj >= s->limit || s->state != MSpanInUse)
    return false;
p = (byte*)((uintptr)s->start<<PageShift);
if(s->sizeclass == 0) {
    obj = p;
} else {
    uintptr size = s->elemsize;
    int32 i = ((const byte*)obj - p)/size;
    obj = p+i*size;
}

Note that the .NET garbage collector is a copying collector so managed/interior pointers need to be updated whenever the object is moved during a garbage collection cycle. The GC will be aware of where in the stack interior pointers are for each stack frame based on the method parameters known at JIT time.

Answer 2

Your code compiles to

    IL_0001: newobj instance void Foo::.ctor()
    IL_0006: ldflda int32 Foo::'field'
    IL_000b: call void Foo::Increment(int32&)

AFAIK, the ldflda instruction creates a reference to the object containing the field, for as long as the address is on the stack (until the call completes).