Better rooting strategies

[withoutboats]

Currently shifgrethor's GC implementation uses an intrusively doubly linked list of roots. This is copied from other previous GC implementations in Rust (its been pointed out to me that this is mostly because GC implementations have been by Mozilla people, and this is how Spidermonkey tracks dynamic roots).

This rooting strategy has some downsides. One is that you have to trace around the entire program while rooting: it has essentially the worst memory locality possible. Another is that every root is three times as large as a normal pointer.

In languages without an unmanaged heap, roots are often tracked through stack maps: compile time generated records of which addresses in each stack frame are roots. The tracer walks the stack using the map associated with each stack frame to find the roots in that frame. This strategy has some problems for us: its not clear how to implement this in a library, and Rust has an unmanaged heap, which necessarily can't be mapped at compile time.

I have an idea for a way to manage stack roots that I think is better. Stack roots are by design tied to a particular stack frame with a 'root lifetime, meaning the pointer that they root cannot escape that stackframe. In fact, the Gc pointer you get from a stack root doesn't contain any root metadata at all, there's an entirely separate pointer in the StackRoot type which is only accessed by the GC's tracing algorithm, and never the user.

An alternative design would be to maintain a global stack of roots somewhere in the heap. Every time we make a GC allocation using the StackRoot API, we push a new root onto that stack. When the StackRoot type drops, we pop that root. Instead of bouncing around the real stack, the GC tracer just iterates up the stack of roots.

I think this can be done with an identical API to the one we have now, but it might even be more flexible and require less macro magic. I think maybe we can have a normal StackRoot::new function and I think we can allow returning a stack rooted pointer as long as you return the root with it. This would require the stack of roots to not be strictly a stack, but instead allow out of order nulling of roots, because destructors could run out of order.

[withoutboats]

Implemented in 17f1803