深度剖析Golang三色标记法（新手必看）

垃圾回收用于回收不再使用的内存（称之为垃圾），那么如何判断内存是否在使用呢？Go 语言使用的是三色标记法完成垃圾内存的标记。三色分别为黑色（已扫描内存）、灰色（待扫描内存）、白色（未扫描，即垃圾内存）。

Go 语言内存分配的基本单元是 mspan，查找空闲内存就是从比特位 allocBits 中查找满足条件的连续 0 比特位，其实除此之外还有一个比特位 gcmarkBits，用来实现内存的标记（0 代表白色，1 代表黑色），定义如下所示：

type mspan struct {
    gcmarkBits *gcBits
}

// 申请 mspan 时初始化
s.gcmarkBits = newMarkBits(s.nelems)

那灰色对象呢？一个比特位怎么表示三种颜色呢？想想如果用两个比特位表示黑灰白三种颜色的对象，那么在执行三色标记法第一步（从灰色对象集合中选择一个对象将其标为黑色）时，怎么选择灰色对象？遍历吗？

其实，Go 语言维护了一个灰色对象集合，并且灰色对象的 gcmarkBits 比特位已经被设置成 1 了。函数 runtime.greyobject 实现了对象标为灰色的逻辑，代码实现如下所示：

func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {
    // objIndex 为该内存块在 mspan 的索引位置
    mbits := span.markBitsForIndex(objIndex)
    // 如果已经被标记函数直接返回
    if mbits.isMarked() { return }
    mbits.setMarked() // 标记
    // 将该对象加入灰色对象集合
    if !gcw.putFast(obj) {
        gcw.put(obj)
    }
}

在上面的代码中，输入参数 objIndex 表示当前扫描的内存块在 mspan 的索引位置，所以根据 objIndex 可以获取到对应的 gcmarkBits 比特位。如果当前内存已经被标记，则函数直接返回；否则需要将其标记为灰色（对应比特位设置为 1 并添加到灰色对象集合）。

而垃圾回收的标记扫描过程实际上是一个循环，不断地从集合中获取灰色对象，并扫描、标记其引用的对象，核心代码如下所示：

for {
    // 获取灰色对象
    b := gcw.tryGetFast()
    if b == 0 {
        b = gcw.tryGet()
    }
    // 扫描、标记
    scanobject(b, gcw)
}

在上面的代码中，方法 gcw.tryGetFast、gcw.tryGet 用于从灰色对象集合中获取对象，函数 runtime.scanobject 用于扫描以及标记该对象引用的所有对象。

获取到灰色对象时，需要扫描以及标记该对象引用的所有对象，可是这时候怎么知道该灰色对象存储的是什么类型的数据呢？也就是说无法判断该灰色对象哪些字节存储的是指针。

Go 语言将 mspan 分为两种，分别存储包含指针的对象以及不包含指针的对象，所以只需要计算出灰色对象所属的 mspan，是不是就能判断该灰色对象是否存储指针了呢？那怎么判断哪些字节存储的是指针呢？总不能认为该灰色对象存储的都是指针吧。

这就需要根据额外的信息判断了，Go 语言采用比特位维护这些信息，每一个比特表示对应 8 字节内存是否存储指针，这些信息维护在 heapArena 对象。比特位的定义参考下面的代码：

// 计算 bitmap 需要多少字节
heapArenaBitmapBytes = heapArenaBytes / (goarch.PtrSize * 8 / 2)
type heapArena struct {
    bitmap [heapArenaBitmapBytes]byte
}

理论上该比特位需要耗费内存 64MB/64=1MB，可是上面的代码计算时，为什么还乘以 2 呢？其实 heapArena.bitmap 不仅记录了每一个 8 字节内存是否存储指针，还记录了后续内存是否需要继续扫描。为什么呢？

假设一个对象占用了 1024 字节的内存，并且只有第一个字段是指针类型，如果只使用一个比特表示对应 8 字节内存是否存储指针，那么总共需要扫描 128 次（1024 / 8=128）。所以 Go 语言使用 2 比特，分别表示每一个 8 字节内存是否存储指针，以及后续字节是否需要继续扫描，这样的话针对上述情况就只需要扫描一次了。这一逻辑可以在函数 runtime.scanobject 中看到，代码如下所示：

func scanobject(b uintptr, gcw *gcWork) {
    // 计算当前对象对应的比特位 bitmap
    hbits := heapBitsForAddr(b)
    // 计算当前对象所属 mspan
    s := spanOfUnchecked(b)
    // 该字段表示当前对象占用内存大小
    n := s.elemsize
    // 扫描这一块内存，函数 hbits.next() 用于移动到下一对位特位
    for i = 0; i < n; i, hbits = i+goarch.PtrSize, hbits.next() {
        bits := hbits.bits()
        // 不需要继续扫描后续内存
        if bits&bitScan == 0 {
            break
        }
        // 当前 8 字节内存没有存储指针
        if bits&bitPointer == 0 {
            continue
        }
        // obj 就是引用的对象
        obj := *(*uintptr)(unsafe.Pointer(b + i))
        // 引用其他对象才需要继续扫描，引用自己不需要扫描
        if obj != 0 && obj-b >= n {
            // 查找对象，加入灰色对象集合
            if obj, span, objIndex := findObject(obj, b, i); obj != 0 {
                greyobject(obj, b, i, span, gcw, objIndex)
            }
        }
    }
}

// 该函数是申请内存的入口函数
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    if !noscan {
        // 如果包含指针，需要维护比特位 bitmap
        heapBitsSetType(uintptr(x), size, dataSize, typ)
    }
}

在上面的代码中，第一步就是计算当前对象对应的比特位以及 mspan，接下来就是循环遍历对应比特位，判断是否需要继续扫描后续内存、当前内存是否存储的是指针、当前指针是否引用的是其他对象，最后将引用的对象添加到灰色对象集合。

注意，在申请内存的时候，需要根据当前内存存储的对象类型，手动维护 heapArena.bitmap 对应的比特位。

当整个标记扫描过程结束之后，白色对象就是需要回收的对象了。那么如何快速回收所有的白色对象呢：

mspan.allocBits 记录了内存空闲与否，0 表示空闲，1 表示已分配；
mspan.gcmarkBits 用于标记对象的颜色，0 表示白色（需要回收的对象）；1 表示黑色对象。

这两个比特位的含义是不是非常接近？所以，在标记扫描过程结束之后，理论上只需要将 mspan.gcmarkBits 赋值给 mspan.allocBit 就可以了。

最后，垃圾回收仅用于回收堆内存，所以标记扫描阶段也只会扫描堆内存，但是协程栈内存其实也是基于 mspan 申请的，那如何判断当前 mspan 管理的内存是堆内存还是栈内存呢？为此，Go 语言专门定义了一个字段（mspan.state）用于判断当前 mspan 管理的内存是堆内存还是栈内存。

深度剖析Golang三色标记法（新手必看）

相关文章