std.allocator: false pointers

[Steven Schveighoffer via Digitalmars-d]

On Fri, 02 May 2014 11:55:11 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> 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)?

False pointers are less of a problem in 64-bit code, but you can run into  
worse issues. If you are not zeroing the memory when deallocating, then if  
it mysteriously comes alive again, it has the ghost of what could be a  
pointer to other code. Your blocks are more likely to resurrect once one  
of them resurrects.

Why not keep the 3 states, but just treat unmarked blocks as free? Then  
the next time you go through tracing, change the bit to free if it was  
already marked.

This doesn't save on the bit space, but I think the savings there is  
minimal anyway. However, it does allow the final pass to be saved.

-Steve