std.allocator: primitives for helping GC

[Andrei Alexandrescu via Digitalmars-d]

So far allocators have been quite GC-agnostic; deallocation would be 
needed for each allocation, and there was little structure to help tracing.

The primitive resolveInternalPointer has made a step toward more precise 
structuring of heaps, and now it's time to look at some real GC helpers.

These are markAllAsUnused, markAsUsed, and doneMarking. Find their 
description here:

http://erdani.com/d/phobos-prerelease/std_allocator.html

There are a few proof of concept implementations here:

https://github.com/andralex/phobos/blob/allocator/std/allocator.d

The basic idea is that the GC would initiate a collection by calling 
markAllAsUnused. That would cause the underlying untyped allocator to 
softly mark all memory as free, but without actually messing it up. 
(Many allocators are capable of implementing such a primitive cheaply.)

Then, the GC would trace objects starting from roots. Whenever it finds 
a used pointer, it would mark the corresponding memory as allocated by 
using markAsUsed, effectively undoing the soft freeing for it.

At the end of the process, what's left is the memory effectively in use. 
Everything else got free by construction.

It seems to me that these three primitives (together with 
resolveInternalPointer) are sufficient for conservative tracing. I plan 
to make tracing more precise by adding more structure, but the scanning 
logic will stay the same.

Now is the time to destroy. I might be missing something by a mile.


Andrei