[gclist] Re: finding object prefix from infix pointer

[marc.shapiro@inria.fr]

 || Date: Fri, 9 Jul 1999 08:07:03 +0200
 || From: Francois-Rene Rideau <fare@tunes.org>
 || Subject: [gclist] finding object prefix from infix pointer
 || 
 || But it looks like we've moved from the topic of implementing read/write
 || barriers to a _completely_ different (and orthogonal, it seems to me)
 || topic of identifying object head from an infix pointer (assuming your
 || implementation uses unguarded infix pointers).

I'm interested in a discussion of the alternatives: this is a costly
operation.

Hans, how does the conservative collector do this?

The plan in our PerDiS system (not yet implemented I think) is simply to
have a fixed-size bitmap associated with every fixed-sized sub-heap.
Assuming the allocation granularity is 16 bytes, each bit in the bitmap
says whether an object starts in this granule or not.  

However scanning a bitmap is very expensive. If performance suffers, I
am thinking of using hierachical bitmaps (Finlayson and Cheriton, SOSP
1987).  The leaves use the simple encoding (bit=1 means an object starts
at this granule).  A node in the tree is a bit whose value is the "or"
of its children.  If each node has, say 16 children, a 1 bit at the 1st
level says that an object starts somewhere in the corresponding
16*16=256 bytes; to find out exactly where, look at the underlying
leaves.  A 1 bit at level 2 says that an object starts somewhere in the
underlying 16*256=4K bytes.  You can continue up more levels but (for
this particular application) there is no point in encoding more than a
page.  The largest page size I'm aware of in modern OSes is 64 Kb; the
object-start information for such a page fits into 8.5 words with just 2
levels.

 || > I'm not sure of a situation where it's more than just a minor inconvenience
 || > to do such a BIBOP lookup.
 || 
 || However, the technique doesn't work in presence of BLOBs (or even BSOBs);

Sorry, these acronyms (BIBOP, BLOB, BSOB) are unfamiliar to me. Could you
explain?

                                                Marc