On 4/30/14, Andrei Alexandrescu via Digitalmars-d <digitalmars-d@puremagic.com> wrote: > 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 >
I actually do have a design in mind for integrating your allocators with my GC design, but there are really only 3 methods that a user-land allocator needs to implement. Below are a few snippets from my current working design describing the `markAsReferenced`, `sweep`, and `free` methods, as implemented by the GC allocators. A user-space allocator will need to call `GC.takeOwnership` passing in the pointer to the memory and it's length in order to tell the GC that it wants to handle the scanning and sweeping of the block of memory itself. A method by the name of `markAsReferenced` accepting a single `size_t` containing a pointer to an object, or a pointer to the interior of an object that, if valid, lies within the allocator’s page. This should mark the object, and any heap-allocated value referenced by the object by passing a pointer to the object to `GC.markAsReferenced`, so that a subsequent call to `sweep` doesn’t result in one of the values referenced by this object being freed by another allocator. This should treat the final possible pointer as a special case to allow the compiler to perform tail-call optimizations. A method by the name of `sweep` accepting no parameters, returning a `size_t` with the number of objects freed. This return value will only ever be used for statistics, so, while it is encouraged for an allocator to implement this, it is permissible to unconditionally return `0`, as the return value will never be essential to the functioning of the GC. This method is to be invoked only after every root has been recursively marked as referenced. This method must not move any marked heap-allocated objects unless the global setting asyncSweep is disabled. An allocator is free to do whatever it wants with the freed allocations, however all freed allocations need to be passed to `GC.finalize` which will return true if the value is actually free due to pending finalizers. It is encouraged for allocator implementations to take lock contention into account when implementing this method, as the Allocator Dispatch may request an allocation while the sweep is still being performed. It is recommended for an allocator to treat a completely un-marked heap as a special case, so that, if there are finalizers pending, time is not wasted attempting to add them to the finalizer list. If there are no remaining live allocations belonging to an allocator, that allocator should pass a pointer to itself to `GC.releaseAllocator`, so that it can be released if it is no longer needed. A method by the name of `free` accepting a single pointer to an allocation owned by this allocator. This method should assume that the finalizer has already been called if applicable, and is free to use the block of memory in whatever way it wants. It is not required for an allocator to immediately make the memory available to be re-allocated, as it is permitted for it to wait until the next time that `sweep` is called. While generally errors should not be thrown in the GC, if a pointer to an object is passed to an allocator’s free method that is not in fact owned by that allocator, the allocator should throw an Error, due to the fact there are likely even bigger problems. It will be possible to catch this error via a global handler.