三色标记垃圾回收

三色标记算法

颜色定义

// 对象的三种状态
const (
    white = 0  // 未访问（可能存活或垃圾）
    gray  = 1  // 已访问，但引用的对象未访问
    black = 2  // 已访问，引用的对象也已访问
)

标记流程

func GC() {
    // 1. 标记准备
    for _, obj := range roots {
        obj.color = gray
    }
    
    // 2. 并发标记
    for hasGray() {
        obj := getGray()
        
        // 扫描灰色对象的所有引用
        for ref := range obj.refs {
            if ref.color == white {
                ref.color = gray  // 标记引用为灰色
            }
        }
        
        obj.color = black  // 标记自己为黑色
    }
    
    // 3. 清除白色对象
    for _, obj := range allObjects {
        if obj.color == white {
            free(obj)  // 回收垃圾
        }
    }
}

图解

初始：所有对象白色
┌───┐     ┌───┐     ┌───┐
│ A │────>│ B │────>│ C │
└───┘     └───┘     └───┘
白色      白色      白色

步骤 1：根对象变为灰色
┌───┐     ┌───┐     ┌───┐
│ A │────>│ B │────>│ C │
└───┘     └───┘     └───┘
灰色      白色      白色

步骤 2：A -> 黑色, B -> 灰色
┌───┐     ┌───┐     ┌───┐
│ A │────>│ B │────>│ C │
└───┘     └───┘     └───┘
黑色      灰色      白色

步骤 3：B -> 黑色, C -> 灰色
┌───┐     ┌───┐     ┌───┐
│ A │────>│ B │────>│ C │
└───┘     └───┘     └───┘
黑色      黑色      灰色

步骤 4：C -> 黑色
┌───┐     ┌───┐     ┌───┐
│ A │────>│ B │────>│ C │
└───┘     └───┘     └───┘
黑色      黑色      黑色

清除：无白色对象，无垃圾

并发问题

问题场景

时间线：
1. GC：标记 A 为黑色（已扫描）
2. 用户：A.C = nil（删除引用）
3. 用户：B.C = C（添加引用，B 是黑色）
4. GC：不会再次扫描 A 和 B
5. 结果：C 永远是白色，被错误回收

图示：
初始：A ──> C, B ──> nil
1. GC 标记 A 为黑色
2. 用户：A.C = nil
3. 用户：B.C = C（B 是黑色）
4. GC 完成：A(黑), B(黑), C(白)
5. 清除：C 被回收 ❌（错误！）

写屏障

插入写屏障（Dijkstra）

// 在插入引用时触发
func writeBarrier(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)  // 将引用标记为灰色
    *slot = ptr
}

// 示例
B.C = C
// 自动触发：
shade(C)  // C 变为灰色

特点：

• 保证强三色不变性（黑色对象不会引用白色对象）
• 需要重新扫描栈

删除写屏障（Yuasa）

// 在删除引用时触发
func writeBarrier(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot)  // 将原引用标记为灰色
    *slot = ptr
}

// 示例
A.C = nil
// 自动触发：
shade(C)  // C 变为灰色

特点：

• 保证弱三色不变性（黑色对象引用的白色对象会被保存）
• 回收精度较低

Go 1.18+ 混合屏障

// 栈上：不启用屏障（STW 时扫描）
func stackScan() {
    // STW 阶段扫描栈
}

// 堆上：启用插入写屏障
func heapWrite(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)  // 插入时标记为灰色
    *slot = ptr
}

策略：

• 第一次 GC：正常标记
• 后续 GC：使用混合屏障
• 栈扫描：STW 阶段完成