GC实现原理学习笔记

原文在此：Golang源码探索(三) GC的实现原理

• 内存分为了3个区域, 在X64上大小分别是spans:512M, bitmap:16G和arena:512G
• go的gc保证了go更适合做高并发服务，减少响应时间。
• bitmap区域用于表示arena区域中哪些地址保存了对象, 并且对象中哪些地址包含了指针.
• bitmap区域中一个byte(8 bit)对应了arena区域中的四个指针大小的内存, 也就是2 bit对应一个指针大小的内存.
• 所以bitmap区域的大小是 512GB / 指针大小(8 byte) / 4 = 16GB.
• bitmap中的byte和arena的对应关系从末尾开始, 也就是随着内存分配会向两边扩展
• spans区域用于表示arena区中的某一页(Page)属于哪个span
• spans区域中一个指针(8 byte)对应了arena区域中的一页(在go中一页=8KB).
• 所以spans的大小是 512GB / 页大小(8KB) * 指针大小(8 byte) = 512MB.
• 当一个对象的内容可能在生成该对象的函数结束后被访问, 那么这个对象就会分配在堆上
• 在C语言中函数返回在栈上的对象的指针是非常危险的事情, 但在go中却是安全的, 因为这个对象会自动在堆上分配.

span结构：

image-20200714181612653

通常一个span包含了多个大小相同的元素, 一个元素会保存一个对象, 除非:

• span用于保存大对象, 这种情况span只有一个元素
• span用于保存极小对象且不包含指针的对象(tiny object), 这种情况span会用一个元素保存多个对象

span中有一个freeindex标记下一次分配对象时应该开始搜索的地址, 分配后freeindex会增加,
在freeindex之前的元素都是已分配的, 在freeindex之后的元素有可能已分配, 也有可能未分配.

allocBits用于标记哪些元素是已分配的, 哪些元素是未分配的.

span每次GC以后都可能会回收掉一些元素, allocBits用于标记哪些元素是已分配的, 哪些元素是未分配的.
使用freeindex + allocBits可以在分配时跳过已分配的元素, 把对象设置在未分配的元素中,
但因为每次都去访问allocBits效率会比较慢, span中有一个整数型的allocCache用于缓存freeindex开始的bitmap, 缓存的bit值与原值相反.

每次gc以后gcmarkBits会变为allocBits.

• span根据大小可以分为67个类型
• 为了分配对象时有更好的性能, 各个P中都有span的缓存(也叫mcache)
• 各个P中按span类型的不同, 有67*2=134个span的缓存,有无指针。
• GC扫描对象的时候对于noscan的span可以不去查看bitmap区域来标记子对象, 这样可以大幅提升标记的效率.

请求内存的流程

• 首先从P的缓存(mcache)获取
• 然后从全局缓存(mcentral)获取, 全局缓存中有可用的span的列表
• 最后从mheap获取, mheap中也有span的自由列表, 如果都获取失败则从arena区域分配

首先GC有四个阶段, 它们分别是:

• Sweep Termination: 对未清扫的span进行清扫, 只有上一轮的GC的清扫工作完成才可以开始新一轮的GC
• Mark: 扫描所有根对象, 和根对象可以到达的所有对象, 标记它们不被回收
• Mark Termination: 完成标记工作, 重新扫描部分根对象(要求STW)
• Sweep: 按标记结果清扫span

在GC过程中会有两种后台任务(G), 一种是标记用的后台任务, 一种是清扫用的后台任务.

• 标记用的后台任务会在需要时启动, 可以同时工作的后台任务数量大约是P的数量的25%, 也就是go所讲的让25%的cpu用在GC上的根据.
• 清扫用的后台任务在程序启动时会启动一个, 进入清扫阶段时唤醒.

目前整个GC流程会进行两次STW(Stop The World), 第一次是Mark阶段的开始, 第二次是Mark Termination阶段.
第一次STW会准备根对象的扫描, 启动写屏障(Write Barrier)和辅助GC(mutator assist).
第二次STW会重新扫描部分根对象, 禁用写屏障(Write Barrier)和辅助GC(mutator assist).

公式中的"目标Heap增长率"可以通过设置环境变量"GOGC"调整, 默认值是100, 增加它的值可以减少GC的触发.
设置"GOGC=off"可以彻底关掉GC.

在go内部对象并没有保存颜色的属性, 三色只是对它们的状态的描述,

白色的对象在它所在的span的gcmarkBits中对应的bit为0,
灰色的对象在它所在的span的gcmarkBits中对应的bit为1, 并且对象在标记队列中,
黑色的对象在它所在的span的gcmarkBits中对应的bit为1, 并且对象已经从标记队列中取出并处理.
gc完成后, gcmarkBits会移动到allocBits然后重新分配一个全部为0的bitmap, 这样黑色的对象就变为了白色.

go在1.9开始启用了混合写屏障(Hybrid Write Barrier)

混合写屏障会同时标记指针写入目标的"原指针"和“新指针".

标记原指针的原因是, 其他运行中的线程有可能会同时把这个指针的值复制到寄存器或者栈上的本地变量,
因为复制指针到寄存器或者栈上的本地变量不会经过写屏障, 所以有可能会导致指针不被标记, 试想下面的情况:

[go] b = obj
[go] oldx = nil
[gc] scan oldx...
[go] oldx = b.x // 复制b.x到本地变量, 不进过写屏障
[go] b.x = ptr // 写屏障应该标记b.x的原值
[gc] scan b...
如果写屏障不标记原值, 那么oldx就不会被扫描到.

标记新指针的原因是, 其他运行中的线程有可能会转移指针的位置, 试想下面的情况:

[go] a = ptr
[go] b = obj
[gc] scan b...
[go] b.x = a // 写屏障应该标记b.x的新值
[go] a = nil
[gc] scan a...
如果写屏障不标记新值, 那么ptr就不会被扫描到.

• 为了防止heap增速太快, 在GC执行的过程中如果同时运行的G分配了内存, 那么这个G会被要求辅助GC做一部分的工作.
• 在GC的标记阶段首先需要标记的就是"根对象", 从根对象开始可到达的所有对象都会被认为是存活的.
  根对象包含了全局变量, 各个G的栈上的变量等, GC会先扫描根对象然后再扫描根对象可到达的所有对象.
• GC的标记阶段会使用"标记队列"来确定所有可从根对象到达的对象都已标记, 上面提到的"灰色"的对象就是在标记队列中的对象.像广度优先搜索

启动后台标记任务时，对每个P启动一个，这里虽然为每个P启动了一个后台标记任务, 但是可以同时工作的只有25%。

image-20200715110116090

1. go触发gc会从gcStart函数开始:
2. 函数gcBgMarkStartWorkers用于启动后台标记任务, 先分别对每个P启动一个
3. gcResetMarkState函数会重置标记相关的状态:
4. stopTheWorldWithSema函数会停止整个世界, 这个函数必须在g0中运行:
5. finishsweep_m函数会清扫上一轮GC未清扫的span, 确保上一轮GC已完成:
6. 进行一些初始化变量设置
7. gcMarkRootPrepare函数会计算扫描根对象的任务数量
8. gcMarkTinyAllocs函数会标记所有tiny alloc等待合并的对象:
9. startTheWorldWithSema函数会重新启动世界:
10. 重启世界后各个M会重新开始调度, 调度时会优先使用上面提到的findRunnableGCWorker函数查找任务, 之后就有大约25%的P运行后台标记任务.
11. 后台标记任务的函数是gcBgMarkWorker
12. 被用来标记的p会把所有的g都踢到全局队列里面去。
13. gcDrain函数扫描完根对象。
14. 在所有后台标记任务都把标记队列消费完毕时, 会执行gcMarkDone函数准备进入完成标记阶段
15. 在并行GC中gcMarkDone会被执行两次, 第一次会禁止本地标记队列然后重新开始后台标记任务, 第二次会进入完成标记阶段
16. gcMarkTermination函数会进入完成标记阶段
17. gcSweep函数会唤醒后台清扫任务
18. 后台清扫任务的函数是bgsweep
19. 从bgsweep和前面的分配器可以看出扫描阶段的工作是十分懒惰(lazy)的,实际可能会出现前一阶段的扫描还未完成, 就需要开始新一轮的GC的情况,所以每一轮GC开始之前都需要完成前一轮GC的扫描工作(Sweep Termination阶段).

有疑问加站长微信联系（非本文作者）