[gclist] Distributed Garbage Collection Revisited 1

[Matthew Fuchs]

Helena,
> 
> Sorry about this. Is very dificult to explain what I am thinking by eamil.
> I am going to try to design an example:
> 
> 
>                   ___________________
>                  /                  |
>                  |                  |
>                  V                  |
>          R1    ScionA1              |
>          |       |                  |
>          V       V                  |
>        ObjA2<--ObjA1                |
>          |       |                  |
>          |       V                  |
>          \---->StubB1               |
>                  |       Space A    |                    
>                  |      ----------  |
>                  V       Space B    |
>          R2    ScionB1              |
>          |       |                  |
>          V       V                  |
>        ObjB2<--ObjB1                |
>                  |                  |
>                  V                  |
>                StubA1               |
>                  |                  |
>                  \-------------------
> 
> This is the example I was thinking. If you start a back-serach say at object
> A1, the algorithm will colour grey ScionA1, StubA1, ObjB1, ScionB1, say at
> time 1. T time 2, ObjA2 invokes ObjB1 that copies <ObjB1,StubA1> to ObjB2.
> ObjB1 was acessed and it is grey.
> Am I write?
> 
You are right, but it's not important.  Keep in mind that the
algorithm first searches out from a source (in this case A1) and then
retreats back to it.

In this case, we have two live objects, R1 and R2 (I made a slight
change to your picture).  If nothing changes, when the search reaches
StubB1, it will query both A1, which will return grey, and A2, which
will (in turn) query R1 and then return black, so B1 knows it is alive
and passes that information to ScionB1, ObjB1, StubA1, ScionA1, and
back to ObjA1, the source.

In your case, the search has only made it to ScionB1 when ObjB2 learns
of StubA1.  At this point StubA1 is waiting on answers to its status
requests from its children (in this case only 1, ObjB1) so it
logically queries ObjB2 on its status, which is live.  It is a
possible optimization to decide this is best accomplished by a local
GC before StubA1 reports its status to ScionA1 as the outward search
contracts towards the source.  Another idea might be to play tricks
with r/w bits on the memory page containing StubA1.  The only barrier
is that StubA1 must find out the status of ObjB2 (by whatever means)
before it reports back to ScionA1.  The logic of the algorithm should
not depend on locality.  Of course, in this case, StubA1 would find
out it is alive from ScionB1 anyway.

The real trick is showing that, if this is the initial graph and the
final graph is:

>                   ___________________
>                  /                  |
>                  |                  |
>                  V                  |
>          R1    ScionA1              |
>          |       |                  |
>          V       V                  |
>        ObjA2<--ObjA1                |
>                  |                  |
>                  V                  |
>                StubB1               |
>                  |       Space A    |                    
>                  |      ----------  |
>                  V       Space B    |
>          R2    ScionB1              |
>          |       |                  |
>          V       V                  |
>        ObjB2<--ObjB1                |
>          |       |                  |
>          |       V                  |
>          \---->StubA1               |
>                  |                  |
>                  \-------------------

there is no point in time at which the trace would miss both R1 and
R2, thereby negligently collecting the entire cycle.  I've laid this
out in fairly excruciating detail in previous messages, so I won't do
so again here.

Matthew Fuchs
matt@wdi.disney.com
http://galt.cs.nyu.edu/students/fuchs