0. 冲动&经历&演变

寻找知识最原始的冲动，经历，演变...
——《创刊词》

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

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

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

counter += 1counter -= 1counter == 0

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

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

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

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

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

1. 标记清除思路

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

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

2. 全局大锁

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

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

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

3. 分阶段加锁

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

  1. “无lock” 把图遍历一遍，同时记录遍历期间的 modify
  2. STW, 把 modify 的变量再遍历一遍

3.1 如何避免 LOCK

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

“转移节点”两种处理角度：

A.child=B.childA.childB.child=NULLB.child

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

路径 hook 分析

对应于可行的两种方案：

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

遍历结果会遇到两个问题

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

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

3.2 Hook 带来的问题

pop/push/ret
counter +/-

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

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

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

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

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

  1. 先 “加 Lock”：标记将要开始 GC
  2. ...
  3. ...
  4. ...
  5. 遍历结束，“加 Lock”：re-scan 发生了 modify 的栈，结束 GC 遍历

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

  1. 加 Lock
    1. 遍历所有的临时/全局等变量，获取堆依赖图的“广度遍历的初始节点”
    2. 标记将要开始 GC


  1. 通过 “删除路径 hook” 保证堆上的并发 modify 正确
  2. GC 线程开始遍历内存依赖图
  3. 遍历结束，“加 Lock”，取消 GC 遍历标记

未被选用的原因

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

4. 局部小锁

4.1 进一步思考阶段锁

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

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

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

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

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

  1. 新增路径屏障，无法保护“栈上的新增”
  2. 删除路径屏障，无法保护“栈上的删除”

4.2 再次分析“转移节点”

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

4.3 混合屏障

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

4.4 栈上的写怎么处理

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

4.5 相关源码

参考下面代码 & 汇编结果


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

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

缺点

+/-counter=0

5.3.2 标记清除

优点

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

缺点

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

6. 参考资料 & 致谢

7. 尾

大曰逝，逝曰远，远曰反
道法术器，溯本归原，愉悦求知 -- 《DreamService 创刊词》