[gclist] deferred reference counting

[Marc Shapiro]

There was recently a discussion in this list about "deferred reference
counting".  A related technique is used in Larchant.

Larchant is a large-scale distributed, persistent shared memory.  For the
purposes of this discussion you may ignore the persistence and distribution
aspects.

The important aspect here is that the memory is partitioned into "bunches"
i.e. clusters of logically-related objects.  The garbage collector maintains
special data structures for references that cross bunch boundaries: a stub for
an outgoing reference, a scion for an incoming reference.

A reference is a plain pointer and applications may freely assign pointers.
There is no write barrier, but we do have a way of telling which bunches have
been modified recently (they are called "GC-dirty").

Garbage collection is hybrid.  Each bunch can be traced independently of any
other bunch; the roots of the trace are its scions.  A trace produces a set of
stubs; the set difference between a stub set and its previous version serves
to update the corresponding scions.  Where a stub has appeared, the reference
count of the corresponding scion is incremented; where one disappears it is
decremented.  Increments and decrements are performed by asychronous messages
(delivered reliably, in order).

The bunch traces can run at any time, and examine the bunches in any order.
Therefore the increment and decrement messages are not necessarily sent in the
order that the mutator performed its assignments.  Counting remains safe under
the following conditions:

  - A trace must examine all GC-dirty bunches.
  - A trace sends all its increment messages before any of its decrement
    messages. 

This has been proved correct.  I can send a paper to those interested.

                                                Marc