查看原文
其他

golang 混合写屏障原理深入剖析,这篇文章给你梳理的明明白白!!!

奇伢 奇伢云存储 2020-12-18


  大纲  


  • 插入写屏障

  • 删除写屏障

  • 混合写屏障

  • golang 混合写屏障实现

    • 源码文件

    • 写屏障代码触发点

    • 对象置灰

    • 暂停 goroutine,栈扫描

  • 总结


网上很多文章对 golang 实现的插入写屏障说的挺详细,但是删除写屏障原理和混合写屏障的由来语焉不详,这篇文章目标是弄明白混合写屏障到底是怎么来的,解决什么问题,插入写屏障,删除写屏障的特点分别是什么?

基础知识复习前四篇文章:

  1. golang 垃圾回收 (一)概述篇
  2. golang 垃圾回收(二)屏障技术
  3. golang 垃圾回收(三)插入写屏障
  4. golang 垃圾回收 - 删除写屏障

首先明白一个前提,栈上,寄存器对象的赋值(插入,删除)不能 hook ,这个因为实力不允许(太复杂,做不到)。


    插入写屏障    


Dijkstra屏障

伪代码:

writePointer(slot, ptr): shade(ptr) *slot = ptr

总结

  1. 如果是纯粹的插入写屏障是满足强三色不变式的(永远不会出现黑色对象指向白色对象);
  2. 但是由于栈上对象无写屏障(不 hook),那么导致黑色的栈可能指向白色的堆对象,所以必须假定赋值器(mutator)是灰色赋值器,扫描结束之后,必须 STW 重新扫描栈才能确保不丢对象;
  3. STW 重新扫描栈再 goroutine 量大且活跃的场景,延迟不可控,经验值平均 10-100ms;

golang 1.5 之后实现的就是这种类型的插入写屏障。


  删除写屏障  


Yuasa-style 屏障

伪代码:

writePointer(slot, ptr) shade(*slot) *slot = ptr

总结

  1. 删除写屏障也叫基于快照的写屏障方案,必须在起始时,STW 扫描整个栈(注意了,是所有的 goroutine 栈),保证所有堆上在用的对象都处于灰色保护下,保证的是弱三色不变式;
  2. 由于起始快照的原因,起始也是执行 STW,删除写屏障不适用于栈特别大的场景,栈越大,STW 扫描时间越长,对于现代服务器上的程序来说,栈地址空间都很大,所以删除写屏障都不适用,一般适用于很小的栈内存,比如嵌入式,物联网的一些程序;
  3. 并且删除写屏障会导致扫描进度(波面)的后退,所以扫描精度不如插入写屏障;

思考问题:我不整机暂停 STW 栈,而是一个栈一个栈的快照,这样也没有 STW 了,是否可以满足要求?(这个就是当前 golang 混合写屏障的时候做的哈,虽然没有 STW 了,但是扫描到某一个具体的栈的时候,还是要暂停这一个 goroutine 的)

不行,纯粹的删除写屏障,起始必须整个栈打快照,要把所有的堆对象都处于灰色保护中才行。

举例:如果没有把栈完全扫黑,那么可能出现丢数据,如下:

初始状态

  1. A 是 g1 栈的一个对象,g1栈已经扫描完了,并且 C 也是扫黑了的对象;
  2. B 是 g2 栈的对象,指向了  C 和 D,g2 完全还没扫描,B 是一个灰色对象,D 是白色对象;

步骤一:g2 进行赋值变更,把 C 指向 D 对象,这个时候黑色的 C 就指向了白色的 D(由于是删除屏障,这里是不会触发hook的)

步骤二:把 B 指向 C 的引用删除,由于是栈对象操作,不会触发删除写屏障;


步骤三:清理,因为 C 已经是黑色对象了,所以不会再扫描,所以 D 就会被错误的清理掉。

解决办法有如下

方法一:栈上对象也 hook,所有对象赋值(插入,删除)都 hook(这个就不实际了);

所有的插入,删除如果都 hook ,那么一定都不会有问题,虽然本轮精度很差,但是下轮回收可以回收了。但是还是那句话,栈,寄存器的赋值 hook 是不现实的。

方法二:起始快照整栈跨找,扫黑,使得整个堆上的在用对象都处于灰色保护;

整栈扫黑,那么在用的堆上的对象是一定处于灰色堆对象的保护下的,之后配合堆对象删除写屏障就能保证在用对象不丢失。

方法三:加入插入写屏障的逻辑,C 指向 D 的时候,把 D 置灰,这样扫描也没问题。这样就能去掉起始 STW 扫描,从而可以并发,一个一个栈扫描。

细品下,这不就成了当前在用的混合写屏障了,所以我觉得正确的理解方式应该是:混合写屏障 = 删除写屏障 + 插入写屏障,必须先理解下删除写屏障,你才能理解混合写屏障。


  混合写屏障  


golang 1.5 之后已经实现了插入写屏障,但是由于栈对象赋值无法 hook 的原因,导致扫描完之后还有一次 STW 重新扫描栈的整机停顿,混合写屏障就是解决这个问题的。

论文里的伪代码:

writePointer(slot, ptr): shade(*slot) if current stack is grey: shade(ptr) *slot = ptr

golang 实际实现的伪代码:

writePointer(slot, ptr): shade(*slot) shade(ptr) *slot = ptr

总结

  1. 混合写屏障继承了插入写屏障的优点,起始无需 STW 打快照,直接并发扫描垃圾即可;
  2. 混合写屏障继承了删除写屏障的优点,赋值器是黑色赋值器,扫描过一次就不需要扫描了,这样就消除了插入写屏障时期最后 STW 的重新扫描栈;
  3. 混合写屏障扫描精度继承了删除写屏障,比插入写屏障更低,随着带来的是 GC 过程全程无 STW;
  4. 混合写屏障扫描栈虽然没有 STW,但是扫描某一个具体的栈的时候,还是要停止这个 goroutine 赋值器的工作的哈(针对一个 goroutine 栈来说,是暂停扫的,要么全灰,要么全黑哈,原子状态切换);

思考一个问题:混合写屏障是全面去除 STW 的一个改进,转而并发一个一个栈处理的方式(每个栈单独暂停),从而消除了整机 STW 的影响,带来了吞吐的提升。有没有想过,这种 STW 整个系统栈,而只暂停一个 goroutine 栈会不会有问题,我钻牛角尖的思考过一些奇怪的场景,比如下面:

初始状态

  1. goroutine 1 已经被扫描黑了(由于混合写屏障的场景,赋值器是黑色赋值器,之后不会在扫描了),goroutine 1 上的 A 对象 指向 nil ;
  2. B 唯一指向 C(灰色的栈对象 B,白色的 C 对象);

步骤一:赋值器(g1)把 A 指向 C,赋值器(g2)把 B 指向 nil,删除 B -> C 的引用,由于A,B 都是栈上的对象,所以这里的赋值都不会触发写屏障;


这样操作下来,是不是就有问题了?

黑色的 A 指向了白色的 C,并且是唯一指向。由于我们说混合写屏障这里是黑色赋值器,黑色的 goroutine 1 栈是不会再扫描了,那等扫描完了,C 岂不是被错误回收了 !!!

这里不会哈。因为这种情况不会出现,证明如下:

如果要实现如上所述场景,需要满足条件:

goroutine 1 栈上的黑色对象 A 引用白色对象 C 只有两种场景:

  1. goroutine 1 持有 goroutine 2 栈上的对象 B ;
  2. goroutine 1 对象 C;
  • g1 不能直接持有 B,不同栈的对象是无法相互访问的,否则就会溢出到堆上;
  • g1 不能直接持有 C,直接持有它就违反了假设,并且如果真是直接持有 C,C 一定是灰色的;

旁白,理解一句话,对象不是天上掉下来的,一定是有路可循的。

撇开这个上面的假设,如果 A 非要引用到 C ,可以通过 A 下面的一个对象 X ( X 指向 C)来获取,但如此一来,C 一定会处于灰色保护下;


  golang 混合写屏障实现  


源码文件

下面以 golang 1.13.3 版本源码演示举例。

golang 当前实际实现的是混合写屏障。这部分的代码在 src/runtime 这个下面,golang 是有运行时(runtime)的概念的,运行时是啥?就是语言层面就形成的管理逻辑,主要工作是 goroutine 创建,调度,销毁,内存分配,垃圾回收等逻辑。有了运行时,就可以保证 golang 业务代码的简单 和 语言本身的强大。

runtime 下有大量的汇编实现的代码,这部分主要是考虑极致的性能,其实大部分还是 golang 的逻辑代码,另外还有如下子目录,分别是 cgo,pprof 的支持等。

Go SDK 1.13.3├── runtime│   ├── cgo│   ├── debug│   ├── internal│   ├── msan│   ├── pprof│   ├── race│   └── trace

在 golang 源代码 mbarrier.go 里面有详细说明,但是提一点,golang 的实际实现其实做了一个简化,把 if 条件判断去掉了,这样的实现更简单,精度差一些。

怎么理解精度会差呢?

因为有了删除写屏障的加持,golang 的栈是黑色赋值器,扫描过是不需要再扫描的。所以如果栈式灰色的,才需要置灰色,否则是 pass 的。golang 处于短期实现的一个简单化处理,源码实现其实是没有这个判断的,所以自然精度就会差些,但是实际效果其实还行。

混合写屏障伪代码:

writePointer(slot, ptr):    // 旧值 置灰 shade(*slot) if current stack is grey:     // 新值 置灰 shade(ptr) *slot = ptr

golang 实际实现伪代码如下:

writePointer(slot, ptr): shade(*slot)    shade(ptr)     *slot = ptr

也就是是说,如果在垃圾回收阶段,只要是堆上的一个赋值 *slot = ptr 那么都会被 hook 住,然后把旧值(*slot)指向的对象,和新值(ptr)指向的对象都置灰(投到扫描队列)。

这个就是混合写屏障完整的逻辑了。


写屏障代码触发点

重点

  1. 写屏障的代码在编译期间生成好,之后不会再变化;
  2. 堆上对象赋值才会生成写屏障;
  3. 哪些对象分配在栈上,哪些分配在堆上?也是编译期间由编译器决定,这个过程叫做“逃逸分析”;

举例:

main.funcAlloc0

13 func funcAlloc0 (a *Tstruct) { 14 a.base = new(BaseStruct) // new 一个BaseStruct结构体,赋值给 a.base 字段 15 }

反汇编就能看到编译出的代码,如下:


在合适的位置,编译器给你程序添加的指令函数 runtime·gcWriteBarrier,这个就是入口,每次堆对象赋值,如果开启了垃圾回收开关,都会去里面转一圈。

实现伪代码如下:

if runtime.writeBarrier.enabled { runtime.gcWriteBarrier(ptr, val)} else { *ptr = val}

注意参数 gcWriteBarrier 传值在 golang 里是个特例,这里用的是寄存器( golang 的惯例是用栈来传递的,但是考虑性能原因,这里必须用寄存器了),详情见文章 golang 垃圾回收(二)屏障技术

runtime·gcWriteBarrier

这个函数是个纯汇编的函数,golang 按照不同的 cpu 指令集实现的,路径可以去看 src/runtime/asm_amd64.s 这个文件。


代码注释如下:

TEXT runtime·gcWriteBarrier(SB),NOSPLIT,$120
get_tls(R13) MOVQ g(R13), R13 MOVQ g_m(R13), R13 MOVQ m_p(R13), R13 MOVQ (p_wbBuf+wbBuf_next)(R13), R14
LEAQ 16(R14), R14 MOVQ R14, (p_wbBuf+wbBuf_next)(R13) // 检查 buffer 队列是否满? CMPQ R14, (p_wbBuf+wbBuf_end)(R13)
// 赋值的前后两个值都会被入队
// 把 value 存到指定 buffer 位置 MOVQ AX, -16(R14) // Record value // 把 *slot 存到指定 buffer 位置 MOVQ (DI), R13 MOVQ R13, -8(R14)
// 如果 wbBuffer 队列满了,那么就下刷处理,比如置灰,置黑等操作 JEQ flushret: // 赋值:*slot = val MOVQ 104(SP), R14 MOVQ 112(SP), R13 MOVQ AX, (DI) RETflush: 。。。
// 队列满了,统一处理,这个其实是一个批量优化手段 CALL runtime·wbBufFlush(SB) 。。。
JMP ret

混合写屏障的两个 shade 直接操作就是上面的两行汇编赋值了:

// 把 value 存到指定 buffer 位置MOVQ AX, -16(R14) // Record value// 把 *slot 存到指定 buffer 位置MOVQ (DI), R13MOVQ R13, -8(R14)

runtime·gcWriteBarrier 函数干啥的,这个函数其实只干两件事:

  1. 执行写请求(原本就要做的事情)
  2. 处理 GC 相关的逻辑(投队列,置灰色保护)

那为什么上面 gcWriteBarrier 这个函数怎么复杂?

其实是做的一个优化处理,每次触发写屏障的时候( hook ),我们当然可以直接shade(ptr),但是我们知道,毕竟这段写屏障的代码是比业务多出来的,这些都是开销,我们能快就快,每次这样做太零散,我们可以攒一批,一批队列满了,一批去入队,置灰色。这样效率更高。一般情况下,只需要简单入队就行了,buf 满了之后,才 flush 去批量置灰,这样写屏障对业务的影响就更小了,wbBuf 就是这个队列的实现。

wbBufFlush

这个函数 wbBufFlush 是 golang 实现的,在文件 src/runtime/mwbbuf.go 里。本质上是封装调用 wbBufFlush1 ,这个函数才是 hook 写操作想要做的事情,这个函数做两个事情:

  1. 批量循环处理 buf 队列里的值;
  2. shade(这个值);

对象置灰

说了这么久“置灰色”,那么到底写屏障是怎么置灰色的?实现如何。其实本质下就下面一行代码,在文件 src/runtime/mwbbuf.go 的函数 wbBufFlush1

// Enqueue the greyed objects.gcw.putBatch(ptrs[:pos])

在 golang 里面,到底什么样的是灰色对象?

  1. 只要在扫描队列中的对象,就是灰色的。

其实,白,灰,黑 三色这个是我们认为抽象出来的概念,也就是所谓的三色标记法,那么这个概念落到实处,又是怎么样的实现。

golang 内部对象并没有保存颜色的属性,三色只是对他们的状态的描述,是通过一个队列 + 掩码位图 来实现的:

  • 白色对象:对象所在 span 的 gcmarkBits 中对应的 bit 为 0,不在队列;
  • 灰色对象:对象所在 span 的 gcmarkBits 中对应的 bit 为 1,且对象在扫描队列中;
  • 黑色对象:对象所在 span 的 gcmarkBits 中对应的 bit 为 1,且对象已经从扫描队列中处理并摘除掉;


暂停 goroutine,栈扫描

扫描某个栈的函数 scang  ,实现在文件 src/runtime/proc.go 里。scang 即为 scan goroutine 的意思,gc 扫描 goroutine 的时候,必须暂停 goroutine,也就是 block 住它,这段时间这个 goroutine 的业务是暂停的,直到扫描完 goroutine 的 stack 就可以放开了。

scangmarkroot 函数里调用(位于 src/runtime/mgcmark.go ),实现如下:

// 切系统调度栈systemstack(func() { userG := getg().m.curg // 如果是在自己的 goroutine 运行的时候去协助处理 gc 任务,恰好处理到自己的时候,需要做些处理; selfScan := gp == userG && readgstatus(userG) == _Grunning if selfScan { casgstatus(userG, _Grunning, _Gwaiting) userG.waitreason = waitReasonGarbageCollectionScan }
// 扫描 goroutine 栈 scang(gp, gcw)
if selfScan { casgstatus(userG, _Gwaiting, _Grunning) }})

scang 这个函数是非常重要的事情,这个函数灰阻塞扫描一个 goroutine,直到扫描栈(注意了,只需要扫描完栈)完成就可以解锁了。

代码如下( src/runtime/proc.go ):

func scang(gp *g, gcw *gcWork) { // 栈扫描是否完成的标识 gp.gcscandone = false
// 轮询的时长间隔 const yieldDelay = 10 * 1000 var nextYield int64
// 循环loop: for i := 0; !gp.gcscandone; i++ { // 读取 goroutine 的状态标识; switch s := readgstatus(gp); s { default: dumpgstatus(gp) throw("stopg: invalid status")
// 如果是已经释放的 goroutine,那么跳出; case _Gdead: // No stack. gp.gcscandone = true break loop
// 拷贝栈的过程,等一下,稍后需要重试; case _Gcopystack: // Stack being switched. Go around again.
// 如果该是 goroutine 是已经挂起的状态(非运行状态) case _Grunnable, _Gsyscall, _Gwaiting: // 重要:设置扫描标识(GScan)这个标识会阻塞该 goroutine 的运行,直到栈扫描完成; if castogscanstatus(gp, s, s|_Gscan) { if !gp.gcscandone { // 调用 scanstack 扫描栈 scanstack(gp, gcw) gp.gcscandone = true } // 重启 goroutine ,这个 goroutine 又可以继续跑业务代码了; restartg(gp) break loop }
// 如果已经是扫描状态了,那么说明别的地方已经在扫描这个g栈了,等别人完成就好了; case _Gscanwaiting: // newstack is doing a scan for us right now. Wait.
// 如果这个 goroutine 是一个 runing 状态,那么需要抢占调度,然后让它自己去扫描 g 栈,现场就等他自己扫描完之后就好了; // 这里只需要设置抢占标识和扫描标识就可以了,真正的扫描现场在这个 gp 自己运行现场; case _Grunning: if gp.preemptscan && gp.preempt && gp.stackguard0 == stackPreempt { break }
// 打上 Scan 标识,通知 gp 抢占调度,让它自己扫描栈; if castogscanstatus(gp, _Grunning, _Gscanrunning) { if !gp.gcscandone { // 打上抢占标识 gp.preemptscan = true gp.preempt = true // 设置魔数标识 gp.stackguard0 = stackPreempt } // 设置完抢占标识,就可以把 goroutine 的 Scan 去掉了,下面就是循环等待它自己处理完了; casfrom_Gscanstatus(gp, _Gscanrunning, _Grunning) } }
if i == 0 { nextYield = nanotime() + yieldDelay } if nanotime() < nextYield { procyield(10) } else { osyield() nextYield = nanotime() + yieldDelay/2 } }
gp.preemptscan = false // cancel scan request if no longer needed}

scang 处理非 running 三种状态转换:

v

scang 处理 running 状态:


总结下 scang 做的最重要的两个事情

  1. 如果 goroutine 是已经挂起的状态了( _Grunnable_Gsyscall_Gwaiting ):
    1. 首先,goroutine 设置上 Gscan ;
    2. 扫描栈 scanstack
    3. 重启 goroutine 状态,去掉 Gscan 状态标识;
  2. 如果 goruotine 是 running 状态,那么就不是在现场扫描了,而是抢占通知 goroutine 本身去扫描,扫描完了,通过 gp.gcscandone 来识别;
    1. goroutine 设置了这个抢占标识之后,goroutine 能立马识别到,然后自己扫描栈,扫描完了设置 gp.gcscandone = true
    2. 设置 gp.preemptscan = truegp.preempt = truegp.stackguard0 = stackPreempt
    3. 等待 gp.gcscandone 为 true ,为 true 的时候,说明 goroutine 自己已经扫描完了,scang 就可以退出了;

scanstack

这个函数简单就提一下,本质上是调用 scanblock 来扫描栈内存,接收参数为开始地址和结束边界,从而确定扫描范围。

扫描的实现非常朴实,就是一个个内存块,扫描分析,读一个,分析一个,发现指针投入队列,步进长度是以指针长度( 8 字节 )。

/*bo :开始地址n0 :内存块长度(结束边界),字节数ptrmask :掩码*/ func scanblock(b0, n0 uintptr, ptrmask *uint8, gcw *gcWork, stk *stackScanState) { b := b0 n := n0
for i := uintptr(0); i < n; { // 获取位图 bits := uint32(*addb(ptrmask, i/(sys.PtrSize*8))) // 如果整个 bits 为 0 ,就不需要往下走了,跳过 8 个指针的长度( 8*8 = 64 ); // 这里也说明下面是每 8 个指针处理一批; if bits == 0 { i += sys.PtrSize * 8 continue } // 8 个指针处理 for j := 0; j < 8 && i < n; j++ { // if bits&1 != 0 { // Same work as in scanobject; see comments there. // 把对应内存地址里面存储的值取出来 p := *(*uintptr)(unsafe.Pointer(b + i)) if p != 0 { // 如果是指针,那么就投入扫描队列,置灰色( greyobject 这个和前面 置灰 是一样的,只是封装的函数略有不同) if obj, span, objIndex := findObject(p, b, i); obj != 0 { greyobject(obj, b, i, span, gcw, objIndex) } else if stk != nil && p >= stk.stack.lo && p < stk.stack.hi { stk.putPtr(p) } } } // bit 位图移去一 bit bits >>= 1 // 内存地址前进一个指针长度(8) i += sys.PtrSize } }}

抢占调度

golang goroutine 的抢占调度是协商性质的(旁白:抢占只针对文明人,粗鲁人你抢占不了),不过这个是在 golang 1.14 之前的历史了,因为 golang 1.14 实现了真正的抢占,是基于异步信号的抢占,这种就不管协程本身文不文明了。咱们这里说的是 golang 1.13 哈。

总结一句话:系统想让某个 goroutine 自己放弃执行权,会给这个协程设置一个魔数,协程调用函数的时候,会有机会看到这个魔数标识,识别这个魔数标识到了就可以切走 cpu 了。

go 1.13 抢占实现是:

  1. 给这个协程设置一个的魔数( stackguard ),每个函数的入口会比较当前栈寄存器值和 stackguard 值来决定是否触发 morestack 函数,(这是一个抢占调度点);
    1. scang  里面有这么一行代码:gp.stackguard0 = stackPreempt
  2. goroutine 协程调用函数的时候,会检查是否需要栈扩容,如果被设置了抢占标示,那么就会调用函数 newstack
  3. newstack 里面判断是否是特殊值 stackPreempt ,这种特殊值目的不在于扩容,而在于抢占调度;

在 golang 里面,只要有函数调用,就会有感知抢占的时机,STW 就是基于这个实现的。

newstack

newstack 本质上是一个分配 goroutine 栈的函数,位于 src/runtime/stack.go,但是里面有配合抢占调度的逻辑,这部分逻辑是非常重要的;

// src/runtime/stack.go: newstack
// 如果开启了抢占调度标识if preempt { // g0 栈是系统调度栈,不能抢占; if gp == thisg.m.g0 { throw("runtime: preempt g0") } if thisg.m.p == 0 && thisg.m.locks == 0 { throw("runtime: g is running but p is not") } // 下面的逻辑就是和 scang 交互同步的; // 设置 Gwaiting 标识,表明 goroutine 在做别的事情,业务程序已经被 block 了 casgstatus(gp, _Grunning, _Gwaiting) if gp.preemptscan { // goroutine 设置 Gscan 标识 for !castogscanstatus(gp, _Gwaiting, _Gscanwaiting) { // ... } if !gp.gcscandone { // 调用 scanstack 扫描栈(scang 那边就是在等这里扫描完成) gcw := &gp.m.p.ptr().gcw scanstack(gp, gcw) // 扫描完成 gp.gcscandone = true } // 扫描完了,去掉抢占标识 gp.preemptscan = false gp.preempt = false // 扫描完了,去除掉 Gscan 标识 casfrom_Gscanstatus(gp, _Gscanwaiting, _Gwaiting) // 扫描完了,goroutine 切换成 Grunning 状态 casgstatus(gp, _Gwaiting, _Grunning) gp.stackguard0 = gp.stack.lo + _StackGuard gogo(&gp.sched) // never return } // ...}


  总结  


  1. 虽然 golang 是先实现的插入写屏障,后实现的混合写屏障,但是从理解上,应该是先理解删除写屏障,后理解混合写屏障会更容易理解;
  2. 插入写屏障没有完全保证完整的强三色不变式(栈对象的影响),所以赋值器是灰色赋值器,最后必须 STW 重新扫描栈;
  3. 混合写屏障消除了所有的 STW,实现的是黑色赋值器,不用 STW 扫描栈;
  4. 混合写屏障的精度和删除写屏障的一致,比以前插入写屏障要低;
  5. 混合写屏障扫描栈式逐个暂停,逐个扫描的,对于单个 goroutine 来说,栈要么全灰,要么全黑;
  6. 暂停机制通过复用 goroutine 抢占调度机制来实现;



往期推荐



golang 垃圾回收 - 删除写屏障

golang 垃圾回收(三)插入写屏障

golang 垃圾回收(二)屏障技术

golang 垃圾回收 (一)概述篇

golang 内存管理分析





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


来都来了,点个在看再走叭~~

Modified on

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存