[gclist] Re: finding object prefix from infix pointer
Fri, 9 Jul 1999 14:15:40 +0200
|| Date: Fri, 9 Jul 1999 08:07:03 +0200
|| From: Francois-Rene Rideau <email@example.com>
|| 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
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
|| > 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