Shenandoah GC: Brooks pointers

I didn’t write about Shenandoah in a while. We first needed to clear up some issues around it, which is done now. The project is not dead yet, quite the contrary, we’re working feverishly. Just now, we are about concurrent evacuation to work 🙂

Last time I wrote about concurrent marking. Before I carry on, I want to introduce a new concept: Brooks pointers. The idea is that each object on the heap has one additional reference field. This field either points to the object itself, or, as soon as the object gets copied to a new location, to that new location. This will enable us to evacuate objects concurrently with mutator threads (how exactly this is done is a topic for a separate post).

One problem of course is that as soon as we have two copies of an object (one in from-space, one in to-space), we need to be careful to maintain consistency. This means that any changes to objects must happen in the to-space copy. This is achieved by putting barriers in various places (everything that writes to objects, or runtime code that uses objects) that resolve the object before writing into it or using it. If we don’t do that, we might end up with some threads using the old copy, and some threads using the new copy, which is, obviously, a problem. The barrier simply reads the brooks pointer field and returns the forwarded object to any code that uses it. In terms of machine code instructions, this means one additional read instruction for each write operation into the heap (and some read operations by the runtime). Infact, we currently need two instructions, the reason for which I’ll explain later.

Eventually, when evacuation is done, we need to somehow update all references to objects to point to the to-space locations. We do that by piggy-backing on the concurrent marking phase. When we traverse the heap for marking, we see all live objects and references, and whenever we visit an object, we update all its object references to point to the new locations of the referents.

There’s two tradeoffs with using brooks pointers: we need more heap space (ideally, one word per object), and we need more instructions to read and write objects.

Next time, I’ll start explaining how concurrent evacuation works.

Because there have been many requests: yes, Shenandoah will be open source. Our plan is to propose a JEP as soon as we can, and make it an OpenJDK project if possible.