[gclist] Re: precise access barrier with hardware dirty bits

marc.shapiro@inria.fr marc.shapiro@inria.fr
Fri, 9 Jul 1999 13:37:16 +0200

 || Date: Thu, 8 Jul 1999 19:21:34 +0200
 || From: Francois-Rene Rideau <fare@tunes.org>
 || Subject: [gclist] precise access barrier with hardware dirty bits
 || The idea was to use dirty bits of paging hardware to achieve
 || _precise_ read or write barriers for a GC or persistent store, by
 || using one logical page mapping by logical object on a same
 || (physical) page? i.e. a same physical page P1 could contain three
 || logical objects A, B, C, at different offsets, and would accordingly
 || be mapped three times at different addresses logical virtual memory.

Assaf Schuster and his Millepede group published a paper on this
technique (which they call "Millipages") at the recent OSDI (Operating
Systems Design and Implementation) symposium.  They use if for detecting
reads and writes, both for controlling their DSM, and for GC.  I haven't
yet read the paper, but I was told that the performance figures in it
are pretty disappointing.  The costs of multiplying the virtual memory
data structures by n (if there are n object per page), and the
corresponding cache pollution, overwhelms the benefits.

Willy Zwaenepoel's group at Rice University has turned the idea around
quite nicely relying on indirection pointers (for Java).  He maps each
page exactly 3 times: one mappping is no-access, one is read-only, one
is read-write.  To change the protection of a particular object you just
change the pointer in the indirection table.  The mappings are aligned
such that you only need to do a very simple bitwise operation on the
pointers.  Assuming a page contains more than 3 objects on average (a
reasonable assumption), this technique is far less costly than
millipages in terms of virtual memory management.  On the flip side,
applications have to pay for the extra indirections.  Willy suggests a
number of compile-time optimizations which I don't quite remember, and
in the end his figures are quite impressive.  I don't think Willy's
group uses this for GC, only for DSM control.