For those keeping score at home, I've just updated
https://github.com/andralex/phobos/blob/allocator/std/allocator.d
https://github.com/andralex/phobos/blob/allocator/std/typed_allocator.d
with an extremely rudimentary example of how tracing would work with a
typed allocator.
The basic idea (factoring out all system-y things such as pausing all
threads and enumerating all registers, stacks, globals, and
thread-locals) is:
1. The typed allocator marks all memory as "unused".
2. Scan all pointers either conservatively or not. This is the
interesting part.
3. Done marking.
For 2, the current approach is to plant a pointer to function during
allocation. That pointer knows what type had been allocated there and
knows how to trace objects of that type. Once the indirect call has been
made (starting from a root), no more indirect calls - scanDirect
functions get instantiated for all fields appropriately. For each type,
scanDirect scans all fields that in turn contain indirections.
This is a "pay-as-you-go" scheme in which scanning functions are
generated (transitively) only for types that are, in fact, allocated on
that heap.
Andrei
