How does a copying garbage collector ensure objects are not accessed while copied?

Question

On collection, the garbage collector copies all live objects into another memory space, thus discarding all garbage objects in the process. A forward pointer to the copied object in new space is installed into the 'old' version of an object to ensure the collector updates all remaining references to the object correctly and doesn't erroneously copy the same object twice.

This obviously works quite well for stop-the-world-collectors. However, since pause times are long with stop-the-world, nowadays most garbage collectors allow the mutator threads to run concurrently with the collector, only stopping the mutators for a short time to do the initial stack scan.

So how can the collector ensure that the 'old' version of an object is not accessed by the mutator while/after copying it? I imagine the mutators could check for the forward pointer with some sort of read barrier, however this seems to costly to me since variables are read so often.

Lurie

Answer 1

You pretty much need to use a read barrier or a write barrier. You're apparently already aware of read barriers so I won't try to get into them.

Writer barriers work because as long as you prevent writes from happening, you simply don't care whether somebody accesses the old or the new copy of the data. You set the write barrier, copy the data, and then start adjusting pointers. After the copy is made, you don't really care whether somebody reads the old or the new copy of the data, because the write barrier ensures they're identical. Once you're done adjusting pointers, everything will be working with the new data, so you revoke the write barrier.

There has been some work done with using page protection bits to mark an area of memory as read-only to create a write-barrier on fairly standard hardware. At least the last time I looked into it, however, this was still pretty much at a proof of concept stage -- working, but too slow to be very practical.

Goodrum

Answer 2

The Loaded Value Barrier implemented in Azul's Generational Pauseless Garbage Collector is an example of a solution to this problem. You can read about it in the article The Azul Garbage Collector posted on InfoQ in early 2011.

Allowedly

Of course Azul is not a simple semispace collector like that described in the question, although it does relocate objects. If the question is "how does a simple semispace collector avoid stopping the world?" then I suspect the answer is that it can't, but I don't know that for sure. – Lumenhour

The described algorithm uses an instruction of their specialized hardware to trap read access to copied object. They say it is possible to emulate their LVB on a x86 processor by adding multiple x86 instructions. However, they don't say anything specific and don't give any indications about performance. Also i suspect the required x86 instructions would probably increase code size significantly, thus deteriorating instruction cache performance – Lurie

@BillAskaga: See "appendix A". It doesn't cite specific benchmarks, but it does give a hand-waving argument that the extra instructions are "typically" almost free to execute. Sadly they don't quantify the typical code size cost. – Lumenhour

Answer 3

Disclaimer: this is related to java's Shenandoah GC only.

Your reasons are absolutely spot on for Shenandoah! Some details here for example.

In the not so long ago days, Shenandoah had write and read barriers for all primitive and reference types. The read barrier was actually just a single indirection via the forwarding pointer as you assume. Since they are so much more compared to writes (which was a much more complicated barrier), these read barriers were more expensive (cumulative time-wise) vs the write ones. This had to do with the sole fact that these are so darn many.

But, things have changed in jdk-13, when a Load Reference barrier was implemented. Thus only loads have a barrier, write happen the usual way. If you think about it, this makes perfect sense, in order to write to an Object field, you need to read that object first, as such if your barrier preserves the "to-space invariant", you will always read from the most recent and correct copy of the object; without the need to use a read barrier with a forwarding pointer.

Gourmand