聊聊ShenandoahGC的Brooks Pointers

原创

code4it

发布于 2019-03-22 23:54:32

1.5K0

文章被收录于专栏：码匠的流水账码匠的流水账

序

本文主要研究一下ShenandoahGC的Brooks Pointers

Shenandoah

Shenandoah面向low-pause-time的垃圾收集器，它的GC cycle主要有

Snapshot-at-the-beginning concurrent mark包括Init Mark(Pause)、Concurrent Mark、Final Mark(Pause)
Concurrent evacuation(这个阶段用到了Brooks Pointers(object version change with additional atomically changed indirection)进行copy)
Concurrent update references (optional)包括Init update Refs(Pause)、Concurrent update Refs、Final update Refs(Pause)

其中Final Mark或者Final update Refs之后都可能进行Concurrent cleanup，进行垃圾回收，reclaims region

Brooks Pointers

G1 GC在evacuation阶段是parallel的，但不是concurrent，ShenandoahGC为了做到concurrent copy使用了Brooks Pointers。

Rodney A. Brooks在<<Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware>>这篇论文提出了一种使用forwarding pointer来做到concurrent copy的方案，该方案在所有对象的内存结构上新增一个forwarding pointer，它要么指向对象自己，要么指向在to-region的自己的拷贝

其要点如下：

evacuation的第一步是拷贝from-region的对象到to-region
evacuation的第二步使用CAS改变from-region的对象的forwarding pointer由自己变为指向to-region的拷贝对象
evacuation的第三步就是遍历heap，更新引用到to-region的拷贝对象

如果在evacuation期间，其他线程通过旧的引用访问到了from-region的旧对象，它就需要根据旧对象的forwarding pointer找到to-region的拷贝对象；等所有旧对象的引用都更新完之后，后续就可以回收from-region的旧对象

示例代码

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循环，即先拷贝再进行CAS，如果CAS不成功则继续尝试拷贝和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
}

在evacuation阶段，对from-region的对象的写操作会触发该对象的evacuation操作(如果该对象在to-region还没有copy的话)

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先判断该对象是否在from-region且在to-region还没有copy，如果满足条件则进行拷贝，然后CAS修改旧对象的forwarding pointer指向拷贝对象

小结

Shenandoah面向low-pause-time的垃圾收集器，它在Concurrent evacuation阶段用到了Brooks Pointers(object version change with additional atomically changed indirection)进行copy，以实现concurrent copy
Rodney A. Brooks在<<Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware>>这篇论文提出了一种使用forwarding pointer来做到concurrent copy的方案，该方案在所有对象的内存结构上新增一个forwarding pointer，它要么指向对象自己，要么指向在to-region的自己的拷贝
evacuation的第一步是拷贝from-region的对象到to-region；evacuation的第二步使用CAS改变from-region的对象的forwarding pointer由自己变为指向to-region的拷贝对象；evacuation的第三步就是遍历heap，更新引用到to-region的拷贝对象