GC 算法 #01：三色标记与写屏障

三色标记（Tri-color Marking）是现代并发 GC（G1、ZGC、Shenandoah、Go GC）的核心算法。它让 GC 标记阶段与用户程序（Mutator）并发执行，减少 Stop-The-World 时间。但并发执行会破坏标记正确性，写屏障（Write Barrier）是修复这一问题的关键机制。

相关文章：分代 GC · G1 GC（Region-based） · ZGC（染色指针与负载屏障）

目录

三色抽象

GC 用三种颜色标记堆中的对象：

白色（White）：尚未被 GC 访问到的对象
               → 标记结束时仍为白色 = 垃圾，可被回收

灰色（Gray）：已被 GC 发现（从根对象可达），但其引用的子对象尚未扫描
              → 待处理队列中的对象

黑色（Black）：已被 GC 完全扫描（自身 + 所有子对象均已处理）
               → 确认存活，本次 GC 不会回收

初始状态：所有对象白色
扫描根对象：根引用的对象变为灰色
标记完成：所有灰色消失，剩白（垃圾）和黑（存活）

三色不变式（Tri-color Invariant）：

强三色不变式：黑色对象不能直接引用白色对象
弱三色不变式：黑色对象可以引用白色对象，但该白色对象
              必须能从某个灰色对象（直接或间接）可达

两个不变式都能保证：GC 标记结束后，所有存活对象都是黑色

串行标记流程

// 无并发时的标记（Stop-The-World）
mark_phase():
    // 1. 初始化：所有对象标记为白色
    for obj in all_objects:
        obj.color = WHITE

    // 2. 灰化根对象（GC Roots: 栈变量、全局变量、静态字段）
    gray_queue = []
    for root in gc_roots:
        if root.ref != null:
            root.ref.color = GRAY
            gray_queue.push(root.ref)

    // 3. 迭代处理灰色对象
    while gray_queue not empty:
        obj = gray_queue.pop()
        obj.color = BLACK     // 标记为已完全扫描

        for child_ref in obj.fields:
            if child_ref != null and child_ref.color == WHITE:
                child_ref.color = GRAY
                gray_queue.push(child_ref)

    // 4. 清除白色对象（垃圾）
    sweep_phase()

并发标记的两个危险

并发执行时，用户程序（Mutator）在 GC 标记过程中修改引用关系，可能导致存活对象被错误回收。

危险 1：对象消失（漏标）

初始状态：
  A（黑）→ B（灰）→ C（白）
  GC 已将 A 标为黑色，正在处理 B

Mutator 执行（并发修改）：
  A.ref = C       // A 增加了对 C 的直接引用
  B.ref = null    // B 删除了对 C 的引用（C 失去了灰色父亲）

GC 继续处理 B：
  B 为黑，B 的 children 现在只有 null
  C 仍为白色

问题：
  C 现在只被 A 引用，A 已经是黑色（不会再扫描）
  C 是白色（GC 认为它是垃圾）
  实际上 C 是存活的（A 引用它）！
  → GC 回收 C → 程序崩溃

触发漏标的两个必要条件（同时满足才危险）：
  条件1：黑色对象插入了对白色对象的新引用（破坏强不变式）
  条件2：灰色对象到白色对象的所有路径被删除（白色失去灰色保护）

危险 2：浮动垃圾（少量，可接受）

初始状态：
  A（黑）→ B（白）    B 是垃圾

Mutator 执行：
  某对象新建了对 B 的引用（B 变为存活）

GC 已经过了扫描 B 的时机（A 已黑，不会回扫）：
  B 仍为白色 → 被回收

但这时 B 已经是存活对象了！

不是所有情况都危险——只有"本应存活却被回收"才危险
"本应回收却存活（浮动垃圾）"是允许的，下轮 GC 会处理

写屏障

写屏障是编译器在所有引用写操作前后插入的一小段代码，用于维护 GC 不变式。

Dijkstra 插入写屏障（Incremental Update）

// 触发时机：写 obj.field = new_ref（插入一条新引用）
// 动作：将 new_ref 染灰（保证黑色不直接指向未处理的白色）

write_barrier_dijkstra(obj, field, new_ref):
    if GC_is_running and new_ref != null and new_ref.color == WHITE:
        new_ref.color = GRAY         // 新引用的目标变灰
        gray_queue.push(new_ref)
    obj.field = new_ref              // 真正执行写操作

原理：
  保证强三色不变式：黑色对象插入对白色的引用时，白色变灰
  → 白色被重新加入扫描队列，不会漏标

代价：
  每次写引用都需要检查并可能入队，有额外开销
  标记结束后需要 re-scan 栈（因为栈上的黑色对象可能引用白色）
  Java G1 使用此方案

Yuasa 删除写屏障（Snapshot-At-The-Beginning, SATB）

// 触发时机：写 obj.field = new_ref（旧引用 old_ref 即将被覆盖）
// 动作：将 old_ref（即将被删除的引用目标）染灰

write_barrier_yuasa(obj, field, new_ref):
    old_ref = obj.field              // 保存旧引用
    obj.field = new_ref              // 真正执行写操作
    if GC_is_running and old_ref != null and old_ref.color == WHITE:
        old_ref.color = GRAY         // 旧引用目标变灰，防止被孤立
        gray_queue.push(old_ref)

原理：
  保证弱三色不变式：即将被删除的白色引用在删除前变灰
  → 即使后来失去所有路径，也已经在队列中等待扫描
  → 可能产生浮动垃圾（本该回收的对象被灰化为存活），下轮处理

代价：
  产生浮动垃圾（保守，宁多扫描不漏掉）
  Go GC 早期使用此方案

混合写屏障（Go 1.14+ 方案）

Go 的混合写屏障（Hybrid Write Barrier）：
  1. 将新写入的 new_ref 染灰（Dijkstra 插入屏障）
  2. 将被覆盖的 old_ref 染灰（Yuasa 删除屏障）

write_barrier_hybrid(obj, field, new_ref):
    old_ref = obj.field

    // 插入屏障：new_ref 变灰
    if GC_is_running and new_ref != null:
        shade(new_ref)

    // 删除屏障：old_ref 变灰
    if GC_is_running and old_ref != null:
        shade(old_ref)

    obj.field = new_ref

    def shade(ref):
        if ref.color == WHITE:
            ref.color = GRAY
            gray_queue.push(ref)

优势：
  不需要 re-scan 栈（Dijkstra 的缺点被消除）
  减少浮动垃圾（比纯 Yuasa 更精准）
  STW 时间更短

完整伪代码

并发标记完整流程

concurrent_mark():
    // Phase 1: Initial Mark（STW，极短）
    STW_begin()
    gray_queue = []
    for root in gc_roots:           // 只扫描 GC Roots
        if root.ref != null:
            shade(root.ref)
    STW_end()

    // Phase 2: Concurrent Mark（与用户程序并发）
    // 此阶段用户程序持续修改引用，写屏障捕获变化
    while gray_queue not empty:
        obj = gray_queue.pop()
        obj.color = BLACK
        for child in obj.fields:
            if child != null:
                shade(child)
    // 并发期间写屏障可能持续向 gray_queue 添加对象

    // Phase 3: Remark（STW，处理并发期间的漏网之鱼）
    STW_begin()
    // Dijkstra 方案：re-scan 所有线程栈（因为栈对象不受写屏障保护）
    for thread in all_threads:
        for ref in thread.stack_roots:
            shade(ref)
    while gray_queue not empty:
        process_gray()
    STW_end()

    // Phase 4: Concurrent Sweep（并发清理）
    for obj in all_objects:
        if obj.color == WHITE:
            free(obj)
        else:
            obj.color = WHITE    // 为下次 GC 重置颜色

执行追踪

演示写屏障如何捕获并发修改（混合写屏障）：

初始对象图：
  Root → A（黑）→ B（灰，在队列中）→ C（白）

GC 正在处理 B 时，Mutator 执行：
  1. A.ref2 = C    // A 新增对 C 的引用
     触发混合写屏障：
       new_ref=C，shade(C) → C 变灰，加入 gray_queue ✅
       old_ref=null（A 原来没有 ref2），不需要处理
  
  2. B.ref = null  // B 删除对 C 的引用
     触发混合写屏障：
       old_ref=C（C 已经变灰了），shade(C) → C 已灰，不重复入队

GC 继续处理灰色队列：
  处理 B：B.ref=null，B 变黑，无子对象
  处理 C：C 的子对象 D 变灰，C 变黑

最终结果：A（黑），B（黑），C（黑），D（黑）→ 所有存活对象正确保留 ✅

各 GC 实现对比

异常场景

写屏障的性能开销

写屏障在每次引用写操作都执行，高频写入时开销可观

测量（Java G1）：
  写屏障约增加 10~20% 的指针写操作开销
  在写密集型程序（如大量对象连接、链表操作）中体感明显

Go 的优化：
  混合写屏障只在 GC 标记阶段开启
  GC 结束后，写屏障关闭，没有任何额外开销
  GC 触发频率低 → 写屏障开启时间短 → 整体影响小

浮动垃圾（Floating Garbage）

Yuasa/SATB 方案的必然产物：
  并发标记开始后才死亡的对象 → 已被染灰 → 本次不回收
  → 成为"浮动垃圾"，下次 GC 才回收

影响：
  内存使用量比理论值稍高（通常 < 5%）
  不影响正确性（不会漏掉存活对象）
  对 GC 频率较高的场景（如 Go）影响更小

漏标 = 程序崩溃

如果写屏障没有正确实现，漏标会导致：
  存活对象被当做垃圾回收
  → 后续访问该内存 → 读到损坏数据或已被重用的对象
  → JVM/Go runtime panic 或数据损坏

这是 GC 实现中最严重的 bug 类型
测试方法：
  1. 高并发 + 大堆的压力测试
  2. 专用 GC 正确性测试（WeakReference 检测、SATB 正确性验证）

参考资料

• Dijkstra, E.W. et al. (1978). On-the-fly garbage collection: An exercise in cooperation
• Hudson, R. & Moss, J.E.B. (1992). Incremental collection of mature objects
• Go GC 文档：https://go.dev/doc/gc-guide
• JEP 333: ZGC - https://openjdk.org/jeps/333