Marking bitmap

["Boehm, Hans" <hans_boehm at hp dot com>]

This needs to be handled extremely carefully.  The problem is that as a
result of conservative scanning the garbage collector might see a pointer to
an object on a free-list, or an otherwise incompletely built object.
Currently, that should be OK, though the correctness argument is ugly.  If
the first entry is not a pointer to a vtable, it is in fact a free-list next
pointer, and objects on the free-list are always cleared.  Since the mark
descriptor is at an offset of 1 word, the corresponding slot will both exist
and be zero in the next object on the free list.  Thus we end up not marking
the original object, which happens to be exactly correct.

Libgcj before the bitmap patch in fact had a similar problem, which
prevented me from running some of my code for longer than a few seconds.  I
suspect this was also the cause of some instability observed by others.  So
this issue does show up in practice.

It may be possible to work around this in the collector at the moment.  But
this gets harder with the thread-local free-list stuff that's in the 6.0
alpha versions.  The only robust workaround in the collector may be to use
different fields for the vtable pointer and collector free-list links,
presumably by moving the free-list link to the second word.  But that incurs
some other costs.  (On something like IA64, free-list traversals and
probably allocation take an extra cycle.  More generally, the collector can
no longer allocate single-word objects, e.g. for short C strings, especially
on 64-bit machines.  There may be cache issues, too.)

> From: Tom Tromey [mailto:tromey@cygnus.com]
> Bryce> Any thoughts on how bitmap marking is going to work with the V3
> Bryce> ABI? I think we'll have to move the class descriptor to the
> Bryce> class object itself, since there wont be a convenient vtable
> Bryce> slot, afaik. This means changes to the GC...
It also means adding GC overhead.  I suspect the overhead is not huge, but
will be significant in some cases.  Object scanning will require an extra
load and, more importantly, it will repeatedly access the class objects.
This is likely to cause more cache misses, especially since so much other
stuff is getting piped through the cache during the mark phase.
> 
> This is Alex's call.
> 
> One option might be to put the bitmap and the class pointer at offsets
> -1 and -2.
This is problematic for the reason I mentioned at the beginning.  If the
object is in fact on a free list, the next object may have garbage at that
offset (or it might be an unmapped address).
> 
> Another would be to add dummy virtual functions to Object whose slots
> would then be abused to hold the extra info.  This is relatively ugly.
But if it ends up at the current offset, things should just work, without
slowing anything down.  From my perspective this looks better than moving
the free-list links, which would have to be combined with one of the above
options.
> 
> Tom
>