[gclist] forwarding pointers & tag-free collection

[Fergus Henderson]

One difficult with tag-free copying collection is distinguishing
forwarding pointers from ordinary objects.  There's no easy way
to distinguish an untagged integer from a forwarding pointer.

Tolmach's paper on tag-free collection [1] mentions several
possible ways of handling this problem:

	(1) Store forwarding pointers in the first word of each object;
	    use a separate bit-map (1 bit per word in the from-space)
	    to distinguish which values are forwarding pointers.

	(2) For each type with at least one pointer field,
	    record the offset of the first pointer field;
	    store the forwarding pointer in that field.  Use address
	    range comparisons (or tag bits) to distinguish forwarding pointers.
	    For objects which don't have any pointer fields,
	  	(a) allocate an extra word for use as a forwarding pointer, or
		(b) keep a separate hash table to record which objects
		    contain forwarding pointers.

Any opinions on which of these is likely to be best?

Another difficulty which I have encountered, which was not mentioned in
Tolmach's paper, is that some of the run-time type descriptors that the
garbage collector uses are allocated on the heap, and may get
overwritten by forwarding pointers, before the collector has
finished using them!  One possible solution would be for
the routines that interpret these type descriptors to check for
and follow forwarding pointers.  Another possible solution would
be to allocate an extra word in each dynamically allocated type
descriptor, for use as a forwarding pointer.

References:
[1] Andrew Tolmach. Tag-free garbage collection using explicit type
parameters. In LFP '94 [30], pages 1--11.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.