[gclist] Hughes' algorithm

[Paul R. Wilson]

>From shapiro@prof.inria.fr Thu Mar 21 02:40:04 1996
>Subject: Re: [gclist] Hughes' algorithm
>
> || I don't see how you can ever detect termination.  For example, there may
> || be no unpropagated 3 marks left in the system, but if there are 4 marks or
> || 5 marks, you can't tell whether GC 3 has actually terminated or
> || not---since 4 marks or 5 marks can clobber 3 marks, it may be that there
> || are things that were reachable for GC 3 _and_still_are_, but the 3 marks
> || have been hidden by clobbering them with 4's and 5's.
>
>If a 3 mark has been clobbered by a 5, that means that the object was still
>reachable at timestamp 5.  When the global minimum reaches 3, 4 or 5 the
>object will not be collected, which is safe.  If you detect termination and
>reach a global minimum for 5, you don't need to worry about 3 any more.

I still don't understand how this can be correct, without more synchronization
than I take Hughes to use.  A global minimum of 5 only means that all of
the 3 marks have either been propagated OR been clobbered by 5's.  It
doesn't mean that all of the 3 marks have been propagated as far as
they will go.

Suppose I have a very long list, which takes a very long time to traverse.
Initially, everything has mark 0---it's never been traversed at all.
For simplicity, assume that this list is so long we'll never actually
finish tracing it.

I start a mark 1 going around the system, and it makes a little headway
on this list.  Later, I start mark 2, and again later I start mark 3.

At some point, all of the 1 marks may get clobbered by 2's or 3's,
even if the list has never been traversed completely.  Without some
constraint on the order of propagation, it may happen that 2's and 3's
catch up with and clobber all of the 1's.  Still, the list may not
have ever been fully traversed.  It may still be mostly marked 0,
but the first few items may have been marked 1, and later clobbered
by 2 or 3.  There are no 1 marks left, yet the list was live when
GC 1 was started, and still is.

In this situation, the absence of 1 marks does not indicate that GC 1
has terminated.  It just means that all of the 1 marks have either
been completely propagated OR clobbered.  Clobbered marks are
problematic, because they *don't* mean that we finished an earlier
trace---they mean we forgot about it.  This still seems like a bug.

>Also, a process traces its roots in decreasing timestamp order.  So, you first
>trace from mark 5, then from mark 4, then 3, etc.  This ensures that each
>object is marked with the maximum possible timestamp.
>
>I think this answers your question.

Actually, it seems to me that this is just making it worse.  If we
preferentially propagate high marks, we will tend to clobber and
forget about lower marks, perhaps without ever tracing all of the
items that were reachable by the low marks.  In effect, we keep
short-circuiting earlier GC's, rather than finishing them.  We're
losing reachability information about old GC's, before they're finished,
by starting new ones and clobbering their marks.