[gclist] Weak locators in a reference listing DGC

Helmut Rubasch Helmut.Rubasch@jk.uni-linz.ac.at
Sat, 16 Oct 1999 20:03:18 +0200

I am just implementing a distributed garbage collector based on
reference listing / SSP-chains and ran into a (?) problem with the weak
locators described in the literature (locators used to shortcut the path
to the object skipping a number of stub-scion-pairs).

I think, that in some cases it can happen, that a weak locator points to
a node, where no stub or scion of this object (nor the objects itself)
are present (any more). So there is no way for the runtime system
(pathfinder) to find the object.

The easiest scenario I could think of is a 3-node (A,B,C) system with 2
objects (a and b, both initially on node A), where object a is
referenced from the local rootset (on A) and b is referenced by a.

Migrating object a to node B and then to node C also leaves a trace of
stubs and scions for object b on the nodes B and C.
The weak locator of object b on node C indicates, that  the original
b-object is still on node A.

The problem (?) is, that if you migrate object b from node A to node B,
a local garbage collection on node A can reclaim the stub/exit-item on
node A (not referenced by any strong locator), while b's weak locator on
node C still points to node A --- finding the real object b starting
from node C will be impossible.

Now three solutions, that one could think of:

1.) also use the WEAK locators for DGC-purposes (don't remove a scion
referenced by a strong OR WEAK locator)

BUT: how is a scion supposed to know about a weak locator referencing
it??? (would need additional messages)

2.) the scenario described here cannot happen and so this "problem" can
never occur

THEN: sorry for posting...

3.) just don't use weak locators and live with larger hops while tracing
SSPs to the real object

thanks for any advice/help/critics

Helmut Rubasch