走进 Golang 垃圾回收

查看原文

其他

走进 Golang 垃圾回收

Go开发大全 2021-01-31

（给Go开发大全加星标）

来源：DreamService
https://zhuanlan.zhihu.com/p/342792030

【导读】本文结合Golang底层源码和汇编代码，深入解析了go语言垃圾回收机制的设计和实现

0. 冲动&经历&演变

内存管理的目的是什么？目的，防止内存泄漏；核心点，防止程序没有可用内存，『回收』『不再被引用』的堆内存（因为栈内存随时收缩自动释放）。

那么接下来就是，如何知道哪些内存『不再被引用』？

显示管理 常见的有 C 语言，写 C 的人应该都有过内存泄漏的噩梦。后来演生出来 C++，虽然继承了 C 的各种包袱，但尽力通过析构函数、智能指针、异常机制等等途径尝试解决内存问题。

引用计数 c++ 的智能指针便是『引用计数』的思路，如果内存增加了新引用，counter += 1，同理 counter \-= 1，如果 counter == 0 释放内存。包括，python、php 在内的许多语言都采用此等思路。

引用计数每次指针操作要进行 counter 的维护，如果 counter 变成 0 还要去 free, 容易拖慢『工作线程』。同时，引用计数无法解决『循环依赖』问题，引入程序 OOM 风险，增大编码工作心智负担。

标记清除 一个与『引用计数』不同的派系，不通过 counter 维护。使用 GC 线程，扫描堆空间的内存依赖关系，标记不被依赖的内存，回收之。如，java/golang 等

附注：策略优缺对比

可见，引用计数是把依赖关系的维护 & 回收内存，分摊到了每次操作。工作线程顺带做了内存管理的事。相对而言，标记清除是把 GC 工作完全托管给了 GC 线程，工作线程集中精力做业务逻辑。

引用计数没有太多延展空间，java/golang 的 GC 走『标记清除』派系。通过细节优化，以期拿到最大收益：GC 标记线程与工作线程协作：加锁。

如何减少锁粒度？全局大锁（原始的标记清除） => 全局分阶段锁（golang 1.5 的写屏障） => 局部小锁（golang1.7 的混合屏障）=> 期待更徍

1. 标记清除思路

标记出所有不需要回收的对象，在标记完成后统一回收掉所有未被标记的对象。

细节以局部变量、全局变量等变量为入口，遍历堆内存的依赖关系。生成『堆节点依赖树』，不在树上的节点为可回收。

// https://github.com/golang/go/blob/release-branch.go1.15/src/runtime/mgcmark.go#L60
// gcMarkRootPrepare queues root scanning jobs (stacks, globals, and some miscellany) 
// and initializes scanning-related state.
func gcMarkRootPrepare() {
	// Compute how many data and BSS root blocks there are.
	nBlocks := func(bytes uintptr) int {
		return int(divRoundUp(bytes, rootBlockBytes))
	}

	work.nDataRoots = 0
	work.nBSSRoots = 0
	// Scan globals.
	for _, datap := range activeModules() {
		nDataRoots := nBlocks(datap.edata - datap.data)
		if nDataRoots > work.nDataRoots {
			work.nDataRoots = nDataRoots
		}
	}

    ....
}

2. 全局大锁

遍历图生成依赖树，其准确性依赖于遍历过程图不发生变化。最简单的做法是 Stop The World：通过一把大锁，这个期间除了 GC 线程，其它线程全部暂停。

显而易见，『全局大锁』不算一个极佳的方案。STW 导致程序的服务能力突然中止，而这种中止的时长 & 时机又具有不可遇见性。

所以，优化的重点就是让锁的影响降低……

3. 分阶段加锁

通过细化分析，我们拆成『必 lock』阶段 & 『不必 lock』阶段。比如：

『无lock』把图遍历一遍，同时记录遍历期间的 modify
STW, 把 modify 的变量再遍历一遍

3.1 如何避免 LOCK

遍历过程中的并发编辑如何处理？

『转移节点』两种处理角度：

赋值路径 hook 在 A.child=B.child 后，将 A.child 标为有用
删除路径 hook 在 B.child=NULL 前，将 B.child 标为有用

注：Golang 1.5 使用第一种方案；Golang 1.7 混用两种方案，以最大化优化

路径 hook 分析

对应于可行的两种方案：

在所有的『赋值路径』（不区分转移/赋值）后，无脑标记『有用』
在所有的『删除路径』（不区分转移/删除）前，无脑标记『有用』

遍历结果会遇到两个问题

错标：本来还有用的内存，被标为无用（必须杜绝）
多标：本来无用的内存，被标为了有用（可以接受，比如：删除了唯一路径）

可见，通过 hook 的思路，可以『避免 Lock』。但是，真的 ok 吗？

3.2 Hook 带来的问题

复杂度 参数压栈（栈自动释放），这里增加大量 hook，直至需要 hook pop/push/ret 等汇编指令；协程栈 resize 导致转移，又需要大量 hook…… ！！

性能问题 工作线程的『赋值/删除操作』增加标记逻辑，性质等同于『引用计数』的counter +/- 且逻辑更复杂。局部性原理，这种主要影响栈上的操作。

结论，栈上的操作不可以加 Hook，只能作用在堆操作上。

3.3 Dijskra 屏障：Golang1.5 的阶段锁

由上面分析，轻易得出方案思路：

先『无 Lock』遍历内存依赖图
遍历期间通过『赋值路径 hook』保证堆上的并发 modify 正确
遍历期间记录发生了 modify 的栈
遍历结束，『加 Lock』，re-scan 发生了 modify 的栈

进一步，由于只有 GC 期间需要 hook:

先『加 Lock』：标记将要开始 GC
...
...
...
遍历结束，『加 Lock』：re-scan 发生了 modify 的栈，结束 GC 遍历

3.4 Yuasa 屏障：阶段锁另一种可行方案

加 Lock
遍历所有的临时/全局等变量，获取堆依赖图的『广度遍历的初始节点』
标记将要开始 GC
通过『删除路径 hook』保证堆上的并发 modify 正确
GC 线程开始遍历内存依赖图
遍历结束，『加 Lock』，取消 GC 遍历标记

未被选用的原因

相对于『Dijskra 屏障』没有明显优势
对节点的处理过于悲观，由『路径分析』一节可知，并发中被『删除』『唯一路径』的节点仍被标为『有用』

4. 局部小锁

4.1 进一步思考阶段锁

为什么赋值路径 hook不像Yuasa 屏障 起始扫描 STW 扫描栈？

扫描栈收集了『对象 A』但是由于栈上编辑没有新增路径屏障，对象 B 无法被保护

为什么 删除路径 hook 不像 Dijskra 屏障 结尾 STW 扫描栈？

由于栈上没有删除路径屏障，对象 B 无法无法被扫描到

由上面分析可知，屏障只能加在堆上

新增路径屏障，无法保护『栈上的新增』
删除路径屏障，无法保护『栈上的删除』

4.2 再次分析『转移节点』

天才，两个屏障一起用，可以解决堆上所有问题。即可避免 Lock。

4.3 混合屏障

// https://github.com/golang/proposal/blob/0bdeab75fa2b7e79fc41fd33f269a5ef6d92e407/design/17503-eliminate-rescan.md#alternative-barrier-approaches

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

既然在『Yuasa 屏障』中，在获取堆的初始节点后，仅靠『删除路径屏障』就可以正常 work。那么，就没必要一直『混合屏障』。

// https://github.com/golang/proposal/blob/0bdeab75fa2b7e79fc41fd33f269a5ef6d92e407/design/17503-eliminate-rescan.md#proposal

writePointer(slot, ptr):
    shade(*slot)
    if any stack is scanning:
        shade(ptr)
    *slot = ptr
    
// 进而演化
writePointer(slot, ptr):
    shade(*slot)
    if current stack is scanning:
        shade(ptr)
    *slot = ptr

4.4 栈上的写怎么处理

局部小锁：锁住被扫描栈对应的协程

// https://github.com/golang/go/blame/release-branch.go1.15/src/runtime/mgc.go#L1945
// https://github.com/golang/go/commit/d6625caf5397a52edc38e19d523a597b531a5f12

systemstack(func() {
    // 当前栈不被 modify, 保证 scan 是安全的
    // We must not modify anything on the G stack. However, stack shrinking is disabled for mark workers, so it is safe to read from the G stack.
 casgstatus(gp, _Grunning, _Gwaiting)
  switch _p_.gcMarkWorkerMode {
   default:
    throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
   case gcMarkWorkerDedicatedMode:
        ...

4.5 相关源码

参考下面代码 & 汇编结果

// go build -gcflags "-N -l -m" ./a.go 

package main
type BaseStruct struct {
    name string
    age  int
}
type Tstruct struct {
    base   *BaseStruct
    field0 int
}

func funcAlloc0 (a *Tstruct) {
    a.base = new(BaseStruct)
}

func main() {
    a := new(Tstruct)
    
    go funcAlloc0(a)
}

(gdb) disassemble 
Dump of assembler code for function main.funcAlloc0:
   ...
   0x0000000000456b4c <+60>:    test   %al,(%rdi)
   # 这里判断是否开启了屏障（垃圾回收的扫描并发过程，才会把这个标记打开，没有打开的情况，对于堆上的赋值只是多走一次判断开销）
   0x0000000000456b4e <+62>:    cmpl   $0x0,0x960fb(%rip)        # 0x4ecc50 <runtime.writeBarrier>
   ...
   # 如果是开启了屏障，那么完成 a.base = xxx 的赋值就是在 gcWriteBarrier 函数里面了
   0x0000000000456b68 <+88>:    callq  0x44d170 <runtime.gcWriteBarrier>
   ....

攒 Buffer 工作线程需要把自己标记的『灰色』节点提交给 GC 线程，通过 buffer 减少了线程通信的次数

TEXT runtime·gcWriteBarrier(SB),NOSPLIT,$120
  ...
  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 队列满了，flush，比如置灰，置黑等操作
  JEQ  flush
ret:
  # 真正的赋值：*slot = val 
  ...
  RET

flush:
  ...
  //  队列满了，统一处理，这个其实是一个批量优化手段
  CALL  runtime·wbBufFlush(SB)
  ...

5. 附注

5.1 理论依据

5.1.1 三色不变式

通过不变式约束，保证任何有用的内存节点都不会错标为无用。但不负责无用内存多标为有用。

三色标记

广度遍历过程中，不同遍历状态节点的『助记』标记。

黑色：已经被遍历过了
灰色：待遍历节点
白色：未触及节点

强三色不变式

白色节点不允许存在黑色的上游节点

助解：如果某节点的上游节点已经『扫描结束』（黑色），当前节点至少为『待扫描』状态（灰色）。

如果黑色节点为白色节点的『唯一』上游，这个节点就会被扫描漏掉。

弱三色不变式

强三色可以不满足；必须保证一个前提，这个白色对象必须处于灰色对象的保护下。

助解：如果发生『扫描结束』节点变成某节点的上游，至少保证有一个『待扫描』节点为其上游。

只要有灰色节点作为白色节点的上游，这个节点就不会被扫描漏掉。

5.1.2 Dijskra 屏障示意图（网络盗图）

5.1.3 Yuasa 屏障示意图（网络盗图）

5.1.4 混合屏障示意图（网络盗图）

场景一：对象被一个堆对象删除引用，成为栈对象的下游

场景二：对象被一个栈对象删除引用，成为栈对象的下游

场景三：对象被一个堆对象删除引用，成为堆对象的下游

场景四：对象被一个栈对象删除引用，成为另一个堆对象的下游

5.2 Golang 的技巧

5.2.1 内存管理 BitMap

5.2.2 逃逸分析

为什么需要了解逃逸分析？因为只有堆上对象的写才会可能有写屏障

go build \-gcflags "-N \-l \-m" ./a.go

在保证程序正确性的前提下，尽可能的把对象分配到栈上，这样性能最好；栈上的对象生命周期就跟随 goroutine ，协程终结了，它就没了。

5.2.3 禁止跨栈指针

不允许存在跨栈指针，因为当栈空间增长/缩减时，栈的内存段可能会变。而且，如果支持跨栈指针，那么 Runtime 需要单独维护这些指标，势必增加 GC 开销。

5.2.4 GC Assist

当存在新的内存分配时，会暂停分配内存过快的那些 goroutine，并将其转去执行一些辅助标记（Mark Assist）的工作，从而达到放缓继续分配、辅助 GC 的标记工作的目的。

5.3 策略优缺对比

5.3.1 引用计数

优点

直观，每被引用一次 counter += 1
简单，无需额外的线程(计算资源)、内存(存储资源)去维护复杂的 GC 状态
及时，一旦没有使用，最后一个释放的逻辑相继释放内存

缺点

影响效率：counter 的 +/-、counter=0 的 free，导致『工作线程』拖慢计算逻辑
循环依赖：内存泄漏，进而引入程序 OOM 风险

5.3.2 标记清除

优点

无需维护 counter, 工作线程专心工作
通过扫描所有节点的依赖关系，不担心循环依赖引起的内存泄漏

缺点

额外的线程(计算资源)、内存(存储资源)去维护复杂的 GC 状态
GC 线程不能保证及时回收掉无用资源，导致系统颠簸
GC 线程与工作线程并发工作，需要一定的锁机制，严重时系统『假死』

6. 参考资料 & 致谢

Golang GC基本原理与优化方向
Golang源码探索(三) GC的实现原理
golang 垃圾回收（二）屏障技术
Eliminate STW stack re-scanning

- EOF -

一把短刀，怎么就让他连捅18人？！

向杨大市长道歉

向不容妄议的杨市长道歉

以色列搞大了：伊朗说要直接出兵参战

黄晓菁，这位杭州泰隆银行女员工自爆视频火了，带给我们那些思考？