Transitioning to a type aware Garbage Collector

[Frits van Bommel]

Chris Miller wrote:
> On Mon, 22 Jan 2007 18:38:05 -0500, Walter Bright 
> <newshound at digitalmars.com> wrote:
> 
>> Andrei Alexandrescu (See Website For Email) wrote:
>>> Sounds great. Any possibility to type memory post factum (useful in 
>>> e.g. implementing allocators)? That is, allocate memory as void[] and 
>>> then mark it to be of type Foo.
>>
>> Looks like that will have to be implemented.
> 
> What about allocating a bigger chunk and dividing it up as a few types?
> 
> I have an idea how to make this work, all memory allocated could have 
> another chunk associated with it that denotes what are pointers. It 
> would only need to use one bit per pointer size.

counter-example:

union Tree
{
     int leaf;
     Tree* inner_node;
}

You need 2 bits to catch all cases :P.
(At least, if you want to allow a moving GC; your scheme should work for 
a non-moving collector)



A while back I thought up the following encoding for a moving GC:

Two bits: "follow" and "adjustable"

follow   adjustable    Meaning:
    0        0          Not a pointer.
    0        1          Weak pointer[1]
    1        0          May be a pointer[2]
    1        1          A normal pointer

follow: The GC follows these references to determine reachability
adjustable: The GC may adjust this value. A moving GC may only move an 
object if all references to it are adjustable.

(You can also think of "follow" as "GC may read this" and "adjustable" 
as "GC may write this")


[1]: Possible future feature. These should be set to null if the 
referenced object is collected.
I'm not yet sure what to do on explicit deletion; would it be too much 
trouble to require weak pointers to be nulled in that case?
For Object instances, you could use the Object.notify[Un]Register 
functions to achieve that. Unfortunately, that solution doesn't work for 
anything but class instances.
Also: weak pointers should probably be disallowed from occurring in unions.

[2]: For "mixed" union locations, void[], etc.
Can possibly also be used (temporarily) for pinned normal pointers.