std.allocator: false pointers

[via Digitalmars-d]

On Friday, 2 May 2014 at 15:55:06 UTC, Andrei Alexandrescu wrote:
> Hello,
>
>
> I'm currently doing a nice optimization in the tracing code: I 
> use the same bit (per block) to indicate "this memory is 
> allocated" and "this memory is marked as used during tracing".
>
> The way the trick works is, at the beginning of a collection 
> the GC marks all of its memory as deallocated (sic!). Then, it 
> traces through pointers and marks BACK as allocated the memory 
> that's actually used. At the end of tracing, there's no need to 
> do anything - what's used stays used, the rest is free by 
> default.
>
> This is unlike more traditional GCs, which use a SEPARATE bit 
> to mean "mark during tracing". At the beginning of the 
> collection, these "mark" bits are set to 0. Then collection 
> proceeds and marks with 1 all blocks that are actually used. As 
> the last step, collection deallocates all blocks that were 
> marked with 0 and were previously allocated.
>
> So the optimization consumes less memory and saves one pass. It 
> does have a disadvantage, however.
>
> Consider a false pointer. It will claim that a block that's 
> free is actually occupied, and the implementation can't 
> distinguish because it conflates the "mark" and the "allocated" 
> bit together. So it's possible that at the end of collection 
> there are blocks allocated that previously weren't. The 
> optimization is therefore sensitive to false pointers.
>
> Thoughts? How bad are false pointers (assuming we fix globals, 
> which only leaves the stack and registers)?

If destructors are still going to be called (see other thread), 
this trick is dangerous, because the resurrected objects might 
later on be destroyed again (double free).

I'm aware that this is still about untyped allocators, but if 
they are going to be used as a basis for typed allocators, things 
like this need to be considered already at this stage.