Tri-Color Marking Explained: Avoid GC Mis‑marks and Boost Java Performance

The GC (Garbage Collector) aims to reclaim memory, consisting of two main steps: marking and sweeping.

Introduction to Tri‑Color Marking

Tri‑color marking is used to efficiently identify reclaimable memory blocks.

Tri‑color marking classifies objects during traversal based on whether they have been visited:

White: objects not yet visited; if still white after analysis, they are unreachable.

Black: objects already visited and all their references scanned; they are safely alive.

Gray: objects visited but at least one reference has not yet been scanned.

Tri‑Color Marking Process

Marking steps:

When GC starts concurrently, all objects are white.

All GC Roots are marked gray.

If a gray object has no child references, it becomes black; otherwise its children are added to the gray set and the current object remains gray.

Repeat step 3 until the gray set is empty; remaining white objects are unreachable and become garbage.

After marking, white objects reachable only from GC Roots are reclaimed.

Mis‑mark

A mis‑mark occurs when both of the following conditions are met:

A black object creates a reference to a white object.

All references from gray objects to a white object are removed.

Solutions to Mis‑mark

Breaking either condition resolves the issue. Two approaches are used: Incremental Update and Snapshot‑At‑The‑Beginning (STAB).

Incremental Update

When a black object inserts a new reference to a white object, the new reference is recorded and, after the concurrent scan finishes, the black object is treated as a root and rescanned. Effectively, the black object becomes gray again.

Snapshot At The Beginning (STAB)

When a gray object removes a reference to a white object, the removal is recorded. After the concurrent scan, the gray object is treated as a root and rescanned, ensuring the marking follows the object‑graph snapshot taken at the start of the scan.

Leak and Over‑mark

Mis‑marks can be further divided into leak (under‑mark) and over‑mark.

Over‑mark – Floating Garbage

If during marking the code executes

object.E = null

, object E becomes gray and its successors (F, G) remain reachable in this round, causing them to survive as "floating garbage" that will be reclaimed in a later GC cycle.

Leak – Read/Write Barriers

Write Barrier (Store Barrier)

When assigning to an object's field, additional logic is inserted before and after the write.

<code>/**
 * @param field 某个对象的成员属性
 * @param new_value 新值，如：null
 */
void oop_field_store(oop* field, oop new_value) {
    *field = new_value // 赋值操作
}
</code>

With a write barrier:

<code>void oop_field_store(oop* field, oop new_value) {
    pre_write_barrier(field); // 写屏障-写前屏障
    *field = new_value; // 赋值操作
    pre_write_barrier(field); // 写屏障-写后屏障
}
</code>

Write Barrier + SATB

When a field's reference changes, the old reference is recorded to preserve the initial object graph (Snapshot‑At‑The‑Beginning).

<code>void pre_write_barrier(oop* field) {
    oop old_value = *field; // 获取旧值
    remark_set.add(old_value); // 记录原来的引用对象
}
</code>

SATB breaks condition one: a gray object disconnects from a white object, preventing under‑mark.

Optimization: if not in the concurrent marking phase or the object is already marked, recording is unnecessary.

<code>void pre_write_barrier(oop* field) {
    // 处于GC并发标记阶段 且 该对象没有被标记（访问）过
    if ($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
        oop old_value = *field; // 获取旧值
        remark_set.add(old_value); // 记录原来的引用对象
    }
}
</code>

Write Barrier + Incremental Update

When a new reference is added, it is recorded for later scanning.

<code>void post_write_barrier(oop* field, oop new_value) {
    if ($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
        remark_set.add(new_value); // 记录新引用的对象
    }
}
</code>

Incremental Update breaks condition two: a black object re‑references a white object, preventing under‑mark.

Read Barrier (Load Barrier)

<code>oop oop_field_load(oop* field) {
    pre_load_barrier(field); // 读屏障-读取前操作
    return *field;
}
</code>

The read barrier records the old value when a field is accessed.

<code>void pre_load_barrier(oop* field, oop old_value) {
    if ($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
        oop old_value = *field;
        remark_set.add(old_value); // 记录读取到的对象
    }
}
</code>

Tri‑Color Marking and Garbage Collectors

Incremental Update is used by the CMS collector; Snapshot‑At‑The‑Beginning is employed by G1 and Shenandoah collectors.

References

https://www.jianshu.com/p/12544c0ad5c1

https://hllvm-group.iteye.com/group/topic/44381

https://www.oracle.com/webfolder/technetwork/tutorials/obe/java/G1GettingStarted/index.html

https://tech.meituan.com/2016/09/23/g1.html

《深入理解 JVM 虚拟机-第三版》周志明