[gclist] write barrier

[Nick Barnes]

> A dumb question from a novice but very interested reader of this list:
> what's a "write barrier" and what role does it play in a GC?

A write barrier is a mechanism for executing some memory management
code when a write to some object takes place (that object is then
"behind the write barrier", or - informally - "write barrier-ed", or -
sloppily - "write-protected"). It can take the form of inlined code
(if memory management is integral to the compiler), or a
memory-protection fault which is handled by the memory management
code. There are also "read barriers", the nature of which is obvious.

The roles a write barrier can play in GC are a little trickier to
explain to a novice, but I'll give it a stab.

1. Consider a simple generational stop-and-collect collector, such as
the one which SML/NJ used to have. "Generational" means that data is
partitioned into old and new. This partition is useful to the GC for
two reasons: (a) because data tends to die young, collecting just new
data will probably free a lot of space, and (b) because pointers tend
to point from new objects to old objects, and not vice versa, it is
cheap to find all the pointers to new objects.

Property (b) is only true if you can tell when a pointer to a new
object has been written into an old object. Otherwise you have to scan
all the old objects to find pointers to new objects, which loses one
of the main advantages of generational GC. So you put the old data
behind a write barrier, and record those writes. When you come to GC
the new data, you know the only pointers from old to new are those
which you have recorded.

2. Consider a tracing GC (*) which is incremental or concurrent,
i.e. the user's program (the 'mutator') can run before the GC is
complete. Now there is an invariant: black objects do not point to
white objects. If the mutator writes a white pointer into a black
object, this invariant is broken and the GC can fail. There are two
basic solutions: prevent the mutator from seeing white objects ("read
barriers") or prevent the mutator from writing white pointers into
black objects ("write barriers"). The write barrier solution puts the
black objects behind a write barrier. When a white-on-black write
takes place there are various fixes: incrementally grey the white
object, regrey the black object, &c.

(*) For a tracing collector (marking or copying), one conceptually
colours the data white (not yet seen by the collector), black (alive
and scanned by the collector) and grey (alive but not yet scanned by
the collector). The collector proceeds by scanning grey objects for
pointers to white objects. The white objects found are turned grey,
and the grey objects scanned are turned black. When there are no more
grey objects, the collection is complete and all the white objects can
be recycled.

Nick Barnes, ne Haines, speaking for himself