Associative Arrays improperly register a GC-allocated TypeInfo for element cleanup

[schveiguy]

This is a bit complicated, so bear with me...

the AA runtime uses TypeInfo for everything. However, the element type is actually a typeless blob of data, allocated using _d_newItemU, with a fake TypeInfo.

This fake TypeInfo (FTI) is constructed using a deal with Satan... er, low level routines without types. The entire purpose of this TypeInfo is to register a destructor to run when the entry is collected.

But how is this FTI allocated? Why, by using the GC of course!

What is the problem with this?

Suppose the associative array is created, along with this FTI, and someone keeps a pointer to an entry, but not the original AA. The GC comes along and collects the AA structure, and any other things (the bucket array, etc), but obviously not the FTI, because the leftover entry which still has a pointer to the FTI.

What happens when that last entry is collected? At that point both the entry and the FTI become garbage. This means that the finalizer of the entry is calling upon this FTI structure to finalize itself, but that FTI might already be collected and gone! In practice this might well work sometimes, because if the block isn't already reallocated (very likely), then the typeinfo bits are still intact.

But if the bits are garbage, you will get a fault. Possibly a null pointer dereference, but also possibly random behavior. It's also a possible vector for exploitation.

So what is the fix? The fix is to somehow keep that FTI allocated, or allocate it at compile time.

Given that we have this capability in the newaa code to build a type info for the entry (newaa does not depend on building a typeinfo at runtime), we should use this same mechanism for all AA. This might prove more difficult than a quick fix, but should still be addressed.

Another option is to store the AA TypeInfo instead of the FTI, and change the AA TypeInfo to behave differently when called to destroy from the GC (AA itself never has a dtor). The AA TypeInfo has the key and value typeinfos inside.

All this really should be replaced with a better mechanism.

[rikkimax]

I suspect the best solution here, which I was going to bring up at the monthly meeting in a couple of days, is to template the AA hooks and kill off TypeInfo entirely.

The plan already exists for templatisation, so doing this is kinda inevitable.

[schveiguy]

Yes, we have all the appropriate information. But this is a bigger task, because the GC is built on using TypeInfo to finalize blocks.

[schveiguy]

An even easier case -- if either key or value has a destructor, but neither contains pointers, the entry will be allocated as NO_SCAN, but with a finalizer set. So therefore, if the original AA is freed, the typeinfo also will be freed, because the NO_SCAN bit will prevent it from being seen.

Have a reliable reproduction here.

import core.memory;

struct S
{
    int x;
    ~this() {
    }
}

struct AAHolder
{
    S[int] aa;
}

S* getBadS()
{
    auto aaholder = new AAHolder;
    aaholder.aa[0] = S();
    auto s = 0 in aaholder.aa; // keep a pointer to the entry
    GC.free(aaholder); // but not a pointer to the AA.
    return s;
}

void stackStomp()
{
    uint[4096] x;
}

void main()
{
    import core.memory;
    auto s = getBadS();
    stackStomp(); // destroy any stale references to the aa or s except in the current frame
    GC.collect(); // should get rid of the fake type info
    foreach(i; 0 .. 1000) // try and reallocate the freed type info
        auto p = new void*[1];
    s = null; // clear any reference to the entry
    GC.collect(); // should segfault.
}