[gclist] write barrier

[David Gadbois]

   Date: Sat, 09 Mar 96 01:57:09 GMT
   From: geert@sun3.iaf.nl (Geert Bosch)

   Why wouldn't you implement write-barriers using the virtual memory
   management units all systems have nowadays?

Good question.  There are several issues in using VM management
hardware for write barrier implementation:

1. Access to VM support.  Some OSes just don't have it, even if the
capability is there.

2. Portability.  mprotect() is widely available in UNIX systems, but
what about other OSes?  And even with mprotect(), there is no standard
way of determining exactly which address faulted.  (It seems like
mprotect() was designed solely with /bin/sh in mind.)

3. Suitability.  The implementation of the VM protection mechanism may
not be very suited for GC use, and it may have bad performance
characteristics.  (Sea story: I was having a devil of a time getting
an application the used VM protection running under OSF/1.  It turned
out that the implementation of mprotect() used a fixed-sized array to
indicate changes in protection over VM regions, and the array was
defaultly really small, like 128 entries.)

4. Need.  For some applications, the number of writes that will hit
the write barrier is vanishingly small.  For example, functional
languages.  Another case is where you can statically determine when
some writes will not hit the barrier.  Object constructors in some
languages all into this category -- writes to new objects can't cross
the barrier.  In such cases, VM write-barrier support has to be really
quick, convenient, and portable before it wins over checking (some
subset of) writes "by hand."

5. Performance.  Changing protections may be expensive, especially if
the OS rejiggers internal tables every time protections change.
The amortized cost of taking barrier traps may be more expensive than
checking the barriers by hand.

6. Protection granularity.  If you are lucky enough to have access to
VM protection support, it usually at the page-level.  Such support may
have an unacceptably high overhead in systems that need object-level
protection.

All that said, using VM protection can be a win in some cases.

There are some other tricks you can play with VM support:

1. Dropping dirty condemned pages.  After a copying GC does its work,
there will be big regions of memory that have been modified but are
garbage.  Tell the VM system to drop it on the floor rather than
uselessly writing it out to backing store.

2. Scavenging/marking pages about to be paged out.  If the VM system
can inform the GC when a page is about to be flushed form memory, it
is good to be able to shift the GC's attention to it temporarily so it
doesn't have to fault the page back in later.

3. Wiring.  GCs often have predictable hot-spot areas of memory (mark
maps, BiBoP tables. etc.) that have access patterns that subvert
typical replacement policies.  It can be a win to force the memory
system to keep this stuff at a suitably high level of the memory
hierarchy.

5. Prefetching.  Marking and copying GCs typically scan over
larger-than-page-sized hunks of address space.  It's great if you can
arrange to have stuff paged/cached in just before the GC needs to look
at it.

6. Caching control.  A copying or marking GC will look at a range of
address space and not come back to it for a long while.  It would be
nice to be able to tell the VM system that the area is a good
candidate for replacement.

Note that all of these tricks can be applied to caching in higher
levels of the memory hierarchy.

(Disclaimer: My main application will always be bigger than an
affordable amount of main memory, so I worry a lot about paging and VM
performance.  Most folks don't have to.)

--David Gadbois