[LLVMdev] Garbage Collection Roots

[Talin]

Hi all,

I've been looking through the documentation 
(http://llvm.org/docs/GarbageCollection.html) on how to implement a 
garbage collector for LLVM and there's a couple of things that I don't 
quite understand. Specifically, it says that when a stack variable goes 
out of scope, you're supposed to assign a null value to it to indicate 
that the value is no longer live.

What I don't quite understand is how the GC can efficiently use this 
information.

The GC will generally have some data structure that represents a list of 
all current roots. Calling llvm.gcroot adds a pointer to the list. When 
the variable goes out of scope, you'll want to remove the pointer from 
the list. But merely assigning null to the value doesn't cause this to 
happen, it only prevents the object previously being pointed to from 
being traced. If the root pointer persists in the table long enough, 
that same stack address may get re-used for a different variable, which 
will be non-null, and cause bad things to happen.

It might be clearer if I explained what I want to do. The way that I 
manager root pointers is as follows: For each application thread, 
there's a pair of arrays stored in thread local data. One array is for 
adding roots, the other is for deleting roots. In other words, each time 
a root gets added, its address gets appended to the 'add' array; Each 
time a root is deleted, its pointer gets appended to the 'delete' array. 
Since both arrays are thread-local, there's no locking or 
synchronization required. If either list gets full, a collection cycle 
is triggered.

Since the roots aren't actually used *except* during a collection cycle, 
we don't both compacting the lists until the start of the next 
collection. At that time, the 'add' list is compacted by removing both 
duplicate entries and any entries found in the 'delete' list. The 'add' 
list is then used as the root set for the cycle.

In order for this to work, however, I definitely need a way to know when 
a reference has gone out of scope so that it can be added to the 
'deleted' list.

-- Talin