Re: Conservative GC isn't safe

["Björn Lindqvist" <bjourne@gmail.com>]

>> If, in this case, “frob” were something that could trigger GC, then stack scanning would not see “obj”, at least not in this stack frame.  And if the caller is doing something like:
>>
>>   Ffrob_array_elts (get_vector_of_stuff ());
>>
>> then the caller needn’t retain any other references to “obj” either.
>
> Again, 'obj' will be somewhere on the stack up the call frames.
> Otherwise, how did it wind up in your frob-array-elts function?

With the 64bit x86 sysv abi, the compiler will put the return value of
get_vector_of_stuff () in the RDI register when calling the function
so value might never exist on the stack. It is different from 32bit
architectures where parameters are mostly passed on the stack. Then in
the loop in Ffrob_array_elts the base pointer in RDI pointing to
get_vector_of_stuff() might be overwritten which would cause the
object to be lost completely.

The first problem is easy to deal with by pushing all general purpose
registers onto the stack before running the gc.

The other problem is that RDI might contain an interior pointer to
get_vector_of_stuff () can be solved too. Like this:

a) Add all allocated objects to an ordered set O, keyed by address.
b) For each pointer P to trace:
c) If P does not point to an object header:
d) Find the object in O with the largest address < P and trace that one instead.

The ordered set can be implemented as a red-black tree so the lookup
in d) will be a fast O(log N) operation. This method is often used to
trace code heaps because return addresses are a form of interior
pointers. But it should work for data heaps too.


-- 
mvh/best regards Björn Lindqvist