It's Not All Black and White
For the last 20 years (roughly half the history of garbage collection), "tricolor marking" has been used to describe the instantaneous state of a memory scan. In their classic paper "On-The-Fly Garbage Collection" (Communications of the ACM, November, 1978), Edsger Dijkstra, Leslie Lamport et al., clarified the process with pictures like these: black objects that have been traversed, white objects that have not been seen and may be garbage, and between them a moving wavefront of gray where (one hopes) forward progress is being made.
This coloring scheme has nothing to do with how the black objects are handled and the white objects disposed of. For instance, a copying collector might move black objects to a separate region of memory, updating pointers and perhaps reorganizing objects more compactly as it does so, while a mark-and-sweep algorithm like Great Circle's leaves all objects at their original addresses (the only robust option in a weakly typed language like C/C++, where unions and casts preclude certain knowledge of which machine words are really pointers). Tricolor marking is solely concerned with the topology of object references, not with their implementation; see Figure 2.
For a scan to proceed correctly, always ending with only black objects in the connected graph, the Dijkstra invariant should be maintained. No black object should ever point to a white object, because the collector is finished with black objects, and can never safely move to completion if these objects start pointing at strange new objects (white, by definition) behind its back. For the mutator to defy this invariant, it must do two things. First, it must read a pointer to a white object (if the mutator's machine registers have not yet been blackened, it may already have such a pointer on hand), then it must write that pointer into a black object behind the gray front. In Figure 2, the black Attic has been swept, but it has a Bed and a Chair. Since the Chair is still gray, its white Doily has never been seen by the collector. If the mutator comes upstairs and gets hold of the Doily, then hides it somewhere in the Attic, as shown in Figure 2(b), the collector will never encounter the Doily at all.
You may realize that a third condition must be met before a white object can really get lost: The original pointer (the copy of Doily in Chair) must be overwritten, as in Figure 2(c). Otherwise, while a pointer from black to white will exist (violating the Dijkstra invariant), the white object in question will still be grayed when the gray object pointing to it is blackened, and so will ultimately be successfully blackened itself. Algorithms that rely on this weakened Dijkstra invariant (which holds that no black object may hold the sole pointer to a white object) are called "snapshot collectors," because they keep a frozen image of all the references that the mutator may later break. The snapshot can result in wasteful overretention, but elegant and fast implementations may be achievable through POSIX process fork()ing.
-- J.W.B.
