奇伢云存储

奇伢云存储

qiyaqingli

© 2021

深度剖析 Golang 的 GC 扫描对象实现

[toc]

之前阐述了 golang 垃圾回收通过保证三色不变式来保证回收的正确性,通过写屏障来实现业务赋值器和 gc 回收器正确的并发的逻辑。其中高概率的提到了“扫描队列”和“扫描对象”。队列这个逻辑非常容易理解,那么”扫描对象“ 这个你理解了吗?有直观的感受吗?这篇文章就是要把这个扫描的过程深入剖析下。

  1. 扫描的东西是啥?形象化描述下
  2. 怎么去做的扫描?形象化描述下

我们就是要把这两个抽象的概念搞懂,不能停留在语言级别浅层面,要知其然知其所以然。

扫描的目的

扫描到底是为了什么?

之前的文章我们深入剖析了垃圾回收的理论和实现,可以总结这么节点:

  1. 垃圾回收的根本目的是:“回收那些业务永远都不会再使用的内存块”;
  2. 扫描的目的则是:“把这些不再使用的内存块找出来”;

我们通过地毯式的扫描,从一些 root 起点开始,不断推进搜索,最终形成了一张有向可达的网,那些不在网里的就是没有被引用到的,也就是可回收的内存。

扫描的实现

扫描对象代码逻辑其实不简单,但主体线索很清晰,可以分为三部分:

  1. 编译阶段:编译期是非常重要的一环,针对静态类型做好标记准备(旁白:原则上编译期能做的绝对不留到运行期);
  2. 运行阶段:赋值器分配内存的时候,根据编译阶段的 type 标示,会为分配的对象内存设置好一个对应的指针标示的 bitmap;
  3. 扫描阶段:根据指针的 bitmap 标示,地毯式扫描;

编译阶段

结构体对齐

要理解编译阶段做的事情,那么首先要理解结构体对齐的基础知识。这个和 C 语言类似,golang 的结构体是有对齐规则的,也就是说,必要的时候可能会填充一些内存空间来满足对齐的要求。总结来说两条规则:

  1. 长度要对齐
  2. 地址要对齐
“长度要对齐”怎么理解?

结构体的长度要至少是内部最长的基础字段的整数倍。

举例:

type TestStruct struct {
	ptr uintptr     // 8 
	f1  uint32      // 4
	f2  uint8       // 1
}

这个结构体内存占用 size 多大?

答案是:16个字节,因为字段 ptr 是 uintptr 类型,占 8 字节,是内部字段最大的,TestStruct 整体长度要和 8 字节对齐。那么就是 16 字节了,而不是有些人想的 13 字节(8+4+1)。

dlv 调试如下:

(dlv) p typ
*runtime._type {
	size: 16,
    ...

字节示意图:

|--8 Byte--|--4 Byte--|--4 Byte--|
“地址要对齐”怎么理解?

字段的地址偏移要是自身长度的整数倍。

举例:

type TestStruct struct {
	ptr uintptr   // 8
	f1  uint8     // 1 
	f2  uint32    // 4
}

假设 new 一个 TestStruct 结构体 a 的地址是 0xc00008a010 ,那么 &a.ptr 是 0xc00008a010 (= a + 0),&a.f1 是 0xc00008a018 (= a + 8) ,&a.f2 是 0xc00008a01c (= a + 8 + 4) 。

dlv 调试如下:

(dlv) p &a.ptr
(*uintptr)(0xc00008a010)
(dlv) p &a.f1
(*uint8)(0xc00008a018)
(dlv) p &a.f2
(*uint32)(0xc00008a01c)

假设 TestStruct 分配对象 a 的地址是 0xc00008a010 ,解释如下:

  • ptr 是第一个字段,当然和结构体本身地址一样,相对偏移是 0,所以地址是 0xc00008a010 == 0xc00008a010 + 0
  • f1 是第二个字段,由于前一个字段 ptr 是 uintptr 类型(8字节),并且由于 f1 本身是 uint8 类型(1字节),所以 f1 从 8 偏移开始没毛病,所以 f1 的偏移地址从 0xc00008a018 == 0xc00008a010 + 8
  • f2 是第三个字段,由于前一个字段 f1 是 uint8(1字节),所以表面上看好像 f2 要接着 0xc00008a019 (= 0xc00008a018 +1) 这个地址才对,但是 f2 本身是 uint32 (4字节的类型),所以 f2 地址偏移至少要是 4 的倍数,所以 f2 的地址要从 0xc00008a01c (0xc00008a018 + 4)这个地址开始才对。也就是说,f1 到 f2 之间填充了一些不用的空间,为了地址对齐。

所以这样算下来,整个 TestStruct 的占用空间长度是 16字节 (8+1+3+4)。

指针位标记

golang 的所有类型都对应一个 _type 结构,可以在 runtime/type.go 里面找到,定义如下:

type _type struct {
	size       uintptr
	ptrdata    uintptr // size of memory prefix holding all pointers
	hash       uint32
	tflag      tflag
	align      uint8
	fieldalign uint8
	kind       uint8
	alg        *typeAlg
	// gcdata stores the GC type data for the garbage collector.
	// If the KindGCProg bit is set in kind, gcdata is a GC program.
	// Otherwise it is a ptrmask bitmap. See mbitmap.go for details.
	gcdata    *byte
	str       nameOff
	ptrToThis typeOff
}

比如我们定义了一个 Struct 如下:

type TestStruct struct {
	ptr uintptr
	f1  uint8
	f2  *uint8
	f3  uint32
	f4  *uint64
	f5  uint64
}

该结构 dlv 调试如下:

(dlv) p typ
*runtime._type {
	size: 48,
	ptrdata: 40,
	hash: 4075663022,
	tflag: tflagUncommon|tflagExtraStar|tflagNamed (7),
	align: 8,
	fieldalign: 8,
	kind: 25,
	alg: *runtime.typeAlg {hash: type..hash.main.TestStruct, equal: type..eq.main.TestStruct},
	gcdata: *20,
	str: 28887,
	ptrToThis: 49504,}

在编译期间,编译器就会在内部生成一个 _type 结构体与之对应。_type 里面重点解释几个和本次扫描主题相关的字段:

  1. size:类型长度,我们上面这个类型长度应该是 32 字节;
    1. 这里理解要应用上上面讲的结构体字节对齐的知识,这里就不再复述;
  2. ptrdata:指针截止的长度位置,我们 f4 是指针,所以包含指针的字段最多也就到 40 字节的位置,ptrdata==40;
    1. 要理解字节对齐哈;
  3. kind:表明类型,我们是自定义struct类型,所以 kind == 25
    1. kind 枚举定义在 runtime/typekind.go 文件里;
  4. gcdata:这个就重要了,这个就是指针的 bitmap,因为编译器他在编译分析的时候,肯定就知道了所有的类型结构,那么自然知道所有的指针位置。gcdata 是 *byte 类型(byte 数组),当前值是 20,20 转换成二进制数据就是 00010100 ,这个眼熟不?这个你要从右往左看就是 00101000(从低 bit 往高 bit 看),这个不就是刚好是 TestStruct 的指针 bitmap 嘛,每个 bit 表示一个指针大小(8 字节)的内存,00101000 第 3 个 bit 和第 5 个 bit 是 1,表示 第 3 个字段(第 3 个 8 字节的位置)和第 5 个字段(第 5 个 8 字节的位置)是存储的是指针类型,这里刚好就和 TestStruct.f2TestStruct.f4 对应起来。

划重点:这里重点回顾一下 uintptr 类型的问题,这里注意到,第一个字段 ptr(uintptr 类型)在指针的 bitmap 上是没有标记成指针类型的,这里一定要注意了,uintptr 是数值类型,非指针类型,用这个存储指针是无法保护对象的(扫描的时候 uintptr 指向的对象不会被扫描),这里就是实锤了。

小结

编译阶段给每个类型生成 _type 类型,内部对类型字段生成指针的 bitmap,这个是后面扫描行为的基础依据。

思考题:是否可以不用 bitmap,其实有个最简单最笨拙的扫描方式,我们可以不搞这个指针的 bitmap,我上来就直接扫描,每 8 字节的读取内存,然后去看这个内存块存储的值是否指向了一个对象?如果是我就保护起来。

这个实现理论上可以满足,但是有两个不能接受的缺陷:

  1. 精度太低,你编译期间不做准备,那运行期间就要来偿还这部分损耗,你无法判断是不是指针,所以只要指向了一个有效内存地址,就得无脑保护,这样就保护了很多不需要保护的内存块;
  2. 扫描太低效,必须全地址扫描,因为你没有 bitmap,无法识别是否有指针。也无法做优化,比如我们程序里面可能 一半以上的类型内是不包含指针的,这种根本就不需要扫描;

运行期内存分配

下一步就是赋值器的做的事情,也就是业务运行的过程中分配内存。分配内存的时候肯定要指定类型,调用 runtime.newobject 函数进行分配,本质上调用 mallocgc 函数来操作。mallocgc 函数做几件事情:

  1. 分配内存
  2. 内存采样
  3. gc 标记准备

我们这里重点分析给 gc 做扫描做的准备。在分配完堆内存之后,会调用一个函数 heapBitsSetType ,这个函数逻辑非常复杂,但是做的事情其实一句话能概括:“给 gc 扫描做准备,对分配的内存块做好标记,这小块内存中,哪些位置是指针,我们用一个 bitmap 对应记录下来”。这就是 heapBitsSetType 500 多行代码做的所有事情,之所以这么复杂是因为要判断各种情况。

heapBitsSetType 主要逻辑解析:

func heapBitsSetType(x, size, dataSize uintptr, typ *_type) {
    // ...

    // 最重要的两个步骤:
    // 通过分配地址反查获取到 heap 的 heapBits 结构(回忆下 golang 的内存地址管理)
    h := heapBitsForAddr(x)
    // 获取到类型的指针 bitmap;
    ptrmask := typ.gcdata // start of 1-bit pointer mask (or GC program, handled below)

    var (
        // ...
    )

    // 把 h.bitp 这个堆上的 bitmap 取出来;
    hbitp = h.bitp

    // 该类型的指针 bitmap
    p = ptrmask
    
    // ...
    if p != nil {
        // 把 bitmap 第一个字节保存起来
        b = uintptr(*p)
        // p 指向下一个字节
        p = add1(p)
        // 
        nb = 8
    }
    
    // 我们的是简单的 Struct 结构(48==48)
    if typ.size == dataSize {
        // nw == 5 == 40/8,说明扫描到第 5 个字段为止即可。
        // ptrdata 指明有指针的范围在[0, 40]以内,再往外确定就没有指针字段了;
        nw = typ.ptrdata / sys.PtrSize
    } else {
        nw = ((dataSize/typ.size-1)*typ.size + typ.ptrdata) / sys.PtrSize
    }

    switch {
    default:
        throw("heapBitsSetType: unexpected shift")

    case h.shift == 0:
        // b 是类型的   ptr bitmap  =>  00010100
        //              bitPointerAll   =>  00001111
        // hb => 0000 0100
        hb = b & bitPointerAll
        // bitScan => 0001 0000 
        // 0001 0000 | 0100 0000 | 1000 0000 
        // hb => 1101 0100
        hb |= bitScan | bitScan<<(2*heapBitsShift) | bitScan<<(3*heapBitsShift)
        // 赋值 hbitp => 1101 0100
        *hbitp = uint8(hb)
        // 指针往后一个字节(递进一个字节)
        hbitp = add1(hbitp)
        // b => 0000 0001
        b >>= 4
        // nb => 4
        nb -= 4

    case sys.PtrSize == 8 && h.shift == 2:
        // ...
    }

    // ...
    // 处理完了前 4 bit,接下来处理后 4 bit
    nb -= 4
    for {
        // b => 0000 0001
        // hb => 0000 0001
        hb = b & bitPointerAll
        // hb => 1111 0001
        hb |= bitScanAll
        if w += 4; w >= nw {
            // 处理完了,有指针的字段都包含在已经处理的 ptrmask 范围内了
            break
        }
        // ...
    }

Phase3:
    // Phase 3: Write last byte or partial byte and zero the rest of the bitmap entries.
    // 8 > 5
    if w > nw {
        // mask => 1
        mask := uintptr(1)<<(4-(w-nw)) - 1
        // hb => 0001 0001
        hb &= mask | mask<<4 // apply mask to both pointer bits and scan bits
    }

    // nw => 6
    nw = size / sys.PtrSize

    // ...

    if w == nw+2 {
        // 赋值 hbitp => 0001 0001
        *hbitp = *hbitp&^(bitPointer|bitScan|(bitPointer|bitScan)<<heapBitsShift) | uint8(hb)
    }

Phase4:
    // Phase 4: Copy unrolled bitmap to per-arena bitmaps, if necessary.
    // ...
}

所以,上面函数调用完,h.bitp 就给设置上了:

低字节 -> 高字节 [ 1101 0100 ], [ 0001 0001 ] |–前4*8字节–|–后4*8字节–|

这个就是 mallocgc 内存的时候做的事情。

总结就一句话:根据编译期间针对每个 struct 生成的 type 结构,来设置 gc 需要扫描的位图,也就是指针 bitmap。(旁白:每分配一块内存出去,我都会有一个 bitmap 对应到这个内存块,指明哪些地方有指针)。

运行扫描阶段

  1. 扫描以 markroot 开始,从栈,全局变量,寄存器等根对象开始扫描,创建一个有向引用图,把根对象投入到队列中,重点的一个函数就是 scanstack
  2. 另外异步的 goroutine 运行 gcDrain 函数,从队列里消费对象,并且扫描这个对象;
    1. 扫描调用的就是 scanobject 函数

下面重点介绍:scanstackscanobject 这个函数怎么扫描对象。

scanstack

这个函数是起点函数( 起始最原始的还是 markroot,但是我们这里梳理主线 ),该扫描栈上所有可达对象,因为栈是一个根,因为你做事情总要有个开始的地方,那么“栈”就是 golang 的起点。

func scanstack(gp *g, gcw *gcWork) {
    // ...
    // 扫描栈上所有的可达的对象
    state.buildIndex()
    for {
        p := state.getPtr()
        if p == 0 {
            break
        }
        // 获取一个到栈上对象
        obj := state.findObject(p)
        if obj == nil {
            continue
        }
        // 获取到这个对象的类型
        t := obj.typ
        // ...
        // 获取到这个类型内存块的 ptr 的 bitmap(编译期间编译器设置好)
        gcdata := t.gcdata
        var s *mspan
        if t.kind&kindGCProg != 0 {
            s = materializeGCProg(t.ptrdata, gcdata)
            gcdata = (*byte)(unsafe.Pointer(s.startAddr))
        }

        // 扫描这个对象
        // 起点:对象起始地址 => state.stack.lo + obj.off
        // 终点:t.ptrdata (还记得这个吧,这个指明了指针所在内的边界)
        // 指针 bitmap:t.gcdata
        scanblock(state.stack.lo+uintptr(obj.off), t.ptrdata, gcdata, gcw, &state)

        if s != nil {
            dematerializeGCProg(s)
        }
    }
    // ...
}

小结:

  1. 找到这个 goroutine 栈上的内存对象(一个个找,一个个处理);
  2. 找到对象之后,获取到这个对象的 type 结构,然后取出 type.ptrdata, type.gcdata ,从而我们就知道扫描的内存范围,和内存块上指针的所在位置;
  3. 调用 scanblock 扫描这个内存块;
scanblock

scanblock 这个函数不说你应该知道,这是一个非常底层且通用的函数,他的一切参数都是传入的,这个函数作为一个基础函数被很多地方调用:

/*
b0: 扫描开始的位置
n0: 扫描结束的长度
ptrmask: 指针的 bitmap
*/
func scanblock(b0, n0 uintptr, ptrmask *uint8, gcw *gcWork, stk *stackScanState) {
    b := b0
    n := n0
    // 扫描到长度 n 为止;
    for i := uintptr(0); i < n; {
        // 每个 bit 标识一个 8 字节,8个 bit (1个字节)标识 64 个字节;
        // 这里计算到合适的 bits
        bits := uint32(*addb(ptrmask, i/(sys.PtrSize*8)))
        // 如果整个 bits == 0,那么说明这 8 个 8 字节都没有指针引用,可以直接跳到下一轮
        if bits == 0 {
            i += sys.PtrSize * 8
            continue
        }
        // bits 非0,说明内部有指针引用,就必须一个个扫描查看;
        for j := 0; j < 8 && i < n; j++ {
            // 指针类型?只有标识了指针类型的,才有可能走到下面的逻辑去;
            if bits&1 != 0 {
                p := *(*uintptr)(unsafe.Pointer(b + i))
                if p != 0 {
                    if obj, span, objIndex := findObject(p, b, i); obj != 0 {
                        // 如果这 8 字节指向的是可达的内存对象,那么就投入扫描队列(置灰)保护起来;
                        greyobject(obj, b, i, span, gcw, objIndex)
                    } else if stk != nil && p >= stk.stack.lo && p < stk.stack.hi {
                        stk.putPtr(p)
                    }
                }
            }
            bits >>= 1
            i += sys.PtrSize
        }
    }
}

如果以上面的 TestStruct 结构举例的话,假设在栈上分配了对象 TestStruct{},地址是 0xc00007cf20,那么会从这个地址扫描 scanblock ( 0xc00007cf20, 40, 20, xxx)

type TestStruct struct {
	ptr uintptr
	f1  uint8
	f2  *uint8
	f3  uint32
	f4  *uint64
	f5  uint64
}

示意图如下:

a7e4ee595fdd3b7751b32a1b9a4fa643.png

最外层 for 循环一次就够了,里面 for 循环 5 次,扫描到 f4 字段就完了(还记得 type.ptrdata == 40 吧 )。只有 f2 ,f4 字段才会作为指针去扫描。如果 f2, f4 字段存储的是有效的指针,那么指向的对象会被保护起来(greyobject)。

小结:

  1. scanblock 这个函数非常简单,只扫描给定的一段内存块;
  2. 大循环每次递进 64 个字节,小循环每次递进 8 字节;
  3. 是否作为指针扫描是由 ptrmask 指定的;
  4. 只要长度和地址是对齐的,指针类型按 8 字节对齐,那么我们按照 8 字节递进扫描一定是全方位覆盖,不会漏掉一个对象的;
  5. 再次提醒下,uintptr 是数值类型,编译器不会标识成指针类型,所以不受扫描保护;

scanobject

gcDrain 这个函数就是从队列里不断获取,处理这些对象,最重要的一个就是调用 scanobject 继续扫描对象。

9710d8211bc53b5e30f280fcf17e9178.png

markroot 从根(栈)扫描,把扫描到的对象投入扫描队列。gcDrain 等函数从里面不断获取,不断处理,并且扫描这些对象,进一步挖掘引用关系,当扫描结束之后,那些没有扫描到的就是垃圾了。

还是 TestStruct 举例:

type TestStruct struct {
	ptr uintptr
	f1  uint8
	f2  *uint8
	f3  uint32
	f4  *uint64
	f5  uint64
}

如果一个创建在堆上的 TestStruct 对象被投入到扫描队列,对应的 type.gcdata0001 0100TestStruct 对应编译器创建的 type 类型如下:

(dlv) p typ
*runtime._type {
	size: 48,
	ptrdata: 40,
    ...
	gcdata: *20,
	... }

scanobject 逻辑如下:

/*
b   : 是对象的内存地址
gcw : 是扫描队列的封装
*/
func scanobject(b uintptr, gcw *gcWork) {
    // 通过对象地址 b 获取到这块内存地址对应的 hbits 
    hbits := heapBitsForAddr(b)
    // 通过对象地址 b 获取到这块内存地址所在的 span
    s := spanOfUnchecked(b)
    // span 的元素大小
    n := s.elemsize
    if n == 0 {
        throw("scanobject n == 0")
    }
    // ...
    var i uintptr
    // 每 8 个字节处理递进处理(因为堆上对象分配都是 span,每个 span 的内存块都是定长的,所以扫描边界就是 span.elemsize )
    for i = 0; i < n; i += sys.PtrSize {
        if i != 0 {
            hbits = hbits.next()
        }
        // 获取到内存块的 bitmap
        bits := hbits.bits()
        
        // 确认该整个内存块没有指针,直接跳出,节约时间;
        if i != 1*sys.PtrSize && bits&bitScan == 0 {
            break // no more pointers in this object
        }
        // 确认 bits 对应的小块内存没有指针,所以可以直接到下一轮
        // 如果是指针,那么就往下看看这 8 字节啥情况
        if bits&bitPointer == 0 {
            continue // not a pointer
        }

        // 把这 8 字节里面存的值取出来;
        obj := *(*uintptr)(unsafe.Pointer(b + i))
        // 如果 obj 有值,并且合法(不在一个 span 的内存块里)
        if obj != 0 && obj-b >= n {
            // 如果 obj 指向一个有效的对象,那么把这个对象置灰色,投入扫描队列,等待处理
            if obj, span, objIndex := findObject(obj, b, i); obj != 0 {
                greyobject(obj, b, i, span, gcw, objIndex)
            }
        }
    }
    // ...
}

小结:

  1. scanobject 的目的其实很简单:就是进一步发现引用关系,尽可能的把可达对象全覆盖;
  2. 这个地方就没有直接使用到 type ,而是使用到 mallocgc 时候的准备成果( heapBitsSetType 设置),每个内存块都对应了一个指针的 bitmap;

总结

  1. 要达到“正确并且高效的扫描”需要 编译期间运行分配期间扫描期间 三者配合处理;
  2. 内存对齐是非常重要的一个前提条件;
  3. 编译期间生成 type 类型,对用户定义的类型全方位分析,标记出所有的指针类型字段;
  4. 运行期间,赋值器分配内存的时候,根据 type 结构,设置和对象内存一一对应的 bitmap,标明指针所在位置,以便后续 gc 扫描;
  5. 回收器扫描期间,从根部开始扫描,遇到对象,则置灰,投入队列,并且不断的扫描这些对象指向的对象,直到结束。扫描的依据,就根据编译期间生成的 bitmap,分配期间设置的 bitmap 来识别哪些地方有指针,然后进一步处理;
  6. 扫描只需要给个开始地址,然后每 8 字节推进就可以扫描了,为了加快效率我们才有了指针的 bitmap (所以这个是个优化项);
  7. 再次强调下,定义的非指针类型不受保护,比如 uintptr 里面就算存储的是一个地址的值,也是不会被扫描到的;

坚持思考,方向比努力更重要。微信公众号关注我:奇伢云存储

关注我公众号, 获取更多干货