Talk about Brooks Pointers of ShenandoahGC.

  jdk12

Order

This article mainly studies Brooks Pointers of ShenandoahGC

Shenandoah

Shenandoah’s garbage collector for low-pause-time mainly includes

  • Snapshot-at-the-beginning concurrent markIncluding Init Mark(Pause), Concurrent Mark, Final Mark(Pause)
  • Concurrent evacuation(Brooks Pointers (object version change with additional atomically changed indirectionCopy)
  • Concurrent update references (optional)Including Init update Refs(Pause), Concurrent update Refs, Final update Refs(Pause)

After Final Mark or Final update Refs, it is possible to carry out Concurrent cleanup and garbage collection.

Brooks Pointers

The G1 GC is parallel in the evacuation phase, but not concurrent. ShenandoahGC uses Brooks Pointers in order to achieve concurrent copy.

Rodney A. Brooks proposed a method of using forwarding pointer in his paper < < trading dataspace for reduced time and codespace in real-time garbage collection on stock hardware > > Do concurrent copy, which adds a forwarding pointer to the memory structure of all objects, either pointing to the object itself or to its own copy in to-region

The main points are as follows:

  • The first step in evacuation is to copy the object from-region to to-region.
  • In the second step of evacuation, CAS is used to change the forwarding pointer of the object from-region from itself to a copy object to-region.
  • The third step of evacuation is to traverse heap and update the copied objects referenced to to-region

If other threads access the old object from-region through the old reference during evacuation, it needs to find the copy object of to-region according to the forwarding pointer of the old object; After all references to the old objects are updated, the old objects from-region can be reclaimed later.

Sample code

concurrent copy

class VersionUpdater<T, V> {
    final AtomicReference<T> ref = ...;
    void writeValue(V value) {
        do {
            T oldObj = ref.get();
            T newObj = copy(oldObj);
            newObj.set(value);
        } while (!ref.compareAndSet(oldObj, newObj));
    }
}

Do while loop is used here, i.e. copy before CAS, if CAS is unsuccessful, continue to try copy and CAS.

write barriers

stub Write(val, obj, offset) {
    if (evac-in-progress && // in evacuation phase
        in-collection-set(obj) && // target is in from-space
        fwd-ptrs-to-self(obj)) { // no copy yet
        val copy = copy(obj);
        *(copy + offset) = val; // actual write
        if (CAS(fwd-ptr-addr(obj), obj, copy)) {
            return; // success!
        }
    }
    obj = fwd-ptr(obj); // write to actual copy
    *(obj + offset) = val; // actual write
}

In the evaluation phase, a write to an object from-region triggers the evaluation of that object (If the object does not have copy in to-region)

evacuation

stub evacuate(obj) {
    if (in-collection-set(obj) && // target is in from-space
        fwd-ptrs-to-self(obj)) { // no copy yet
        copy = copy(obj);
        CAS(fwd-ptr-addr(obj), obj, copy);
    }
}

Evacuate first judges whether the object is in the from-region and there is no copy in the to-region. If the condition is met, then CAS modifies the forwarding pointer of the old object to point to the copied object

Summary

  • Shenandoah’s garbage collector for low-pause-time uses Brooks Pointers (object version change with additional atomically changed indirection) to implement concurrent copy
  • Rodney A. Brooks proposed a method of using forwarding pointer in his paper < < trading dataspace for reduced time and codespace in real-time garbage c ollection on stock hardware > > Do concurrent copy, which adds a forwarding pointer to the memory structure of all objects, either pointing to the object itself or to its own copy in to-region
  • The first step in evacuation is to copy the object from-region to to-region; ; In the second step of evacuation, CAS is used to change the forwarding pointer of the object from-region from itself to the copied object to-region. The third step of evacuation is to traverse heap and update the copied objects referenced to to-region

doc