Memory barrier implementation for a garbage collector

I'm reading about garbage collectors implementations, specifically about mark-and-sweep on-the-fly collectors, and the fact that to allow the mutators work when the marking stage isn't finished (and so avoid stopping the world) a memory barrier must be used.

So, for example, if a marked (black) object is modified by the mutator to point to an unmarked (white) object, then the white object must be marked to gray (marked as live but not scanned yet).

But I can't find any detail of how tha开发者_如何学Ct can be implemented: how can I detect when a black object is changed and perform an action at that moment?

Maybe the confusing terminology is to blame. So-called barriers, in garbage collection terminology, are usually snippets of code that the compiler inserts before pointer reads and writes. Your program thus always executes the barrier code before every read and write. (You can also use virtual memory protection to get the effect of barriers.)

To maintain the tricolor invariant you allude to, the collector checks the color of an object before it writes through it. In this case, the write barrier can execute some action whenever it is about to change a black object to a gray one.

See http://www.memorymanagement.org/glossary/s.html#strong.tri-color.invariant for an overview, and this article for more details.

I'm reading about garbage collectors implementations, specifically about mark-and-sweep on-the-fly collectors, and the fact that to allow the mutators work when the marking stage isn't finished (and so avoid stopping the world) a memory barrier must be used.

I think you're confusing write barriers and memory barriers. Garbage collectors use write barriers to track the changing topology of the heap. A memory barrier is a low-level concurrency primitive that prevents memory operations from being reordered, both by the compiler and by the CPU itself.

So you want to search for GC write barriers. In particular, the Yuasa, Steele and Dijkstra write barriers.

Garbage collectors can also handle on-the-fly mutation of the heap topology using read barriers.