[gclist] Dgc implementation notes

[Arturo Bejar]

Hi all,

It seems that this is the only one of the algorithms kicking around that 
has actually been implemented, and as Gustavo points out you learn a lot 
about these things when you do so, so I wanted to talk a little about how 
we implemented it in hopes that the group finds it useful.

As described before we work closely with the local GC. We modified the 
java garbage collector so that it generates the inverse reference graph 
for us, it also gives us the list of suspects for cycles. And we do this 
in clusters of objects rather than the specific objects themselves, let 
me explain.

Keeping an IRG for every object in a machine can be difficult, specially 
if have to work from an existing system that doesn't build one up. So 
what we have is kind of a logical cluster of objects, our modified gc 
starts sweeping at the export tables, if a marked object is found it 
stops. If it gets all the way to an imported object then a suspect has 
been found (a 'cluster' of objects that is only referred remotely as well 
referring to other objects remotely), and we run the algorithm from 
there. The irg inside the scope of that machine is kept by the import 
entry which allows for very efficient runs of the algorithm.

We are also implementing a form of lazy memory of the identifiers used in 
the run so that even when a node is done it remembers the identifier for 
a period of time in case there there is another request kicking around, 
we also leverage positive and negative results in the propagation of the 
responses, if a suspect node is discovered to be garbage while it is 
wating to send of the next batch of requests, it propagates negatively, 
we also pass on positive results promiscuosly keeping the expense of 
concurrent requests down.

Our implementation has served us well and I hope that the algorithm and 
some of the insights gained in the implementation are useful to the group.

Arturo

___________________________________________________________________
Arturo Bejar                   "What you can see, you can achieve."
arturo@communities.com                          - J. Verne, sort of