【Go笔记】垃圾回收

初探

• 垃圾回收作为内存管理的一部分，有三个重要功能：分配和管理新对象、识别正在使用的对象、清除不再使用的对象
• 传统没有垃圾回收的语言需要手动分配，释放内存，可能会产生很多内存泄露和野指针问题。垃圾回收不完全保证内存泄漏，但是重要保障
• 手动管理内存往往难以在本地模块内做出全局的内存管理，特别是多模块同时管理使用同一块内存的情况。垃圾回收将垃圾收集的工具托管给了具有全局视野的运行时代码
• 垃圾回收带来了额外的时间和内存成本，有时候还需要中断整个程序来处理，因此对于极致的速度时和内存要求绩效的场景（嵌入式、系统级程序等）并不适用，但是对大规模（分布式、集群等）是极佳选择
• 垃圾回收的常见指标：程序暂停空间、空间开销、回收及时性等

五种经典算法

¶标记-清扫 (Mark-Sweep)

• 分为两个主要阶段 - 扫描并标记当前活着的对象、清扫没有被标记的对象
• 是一种间接的垃圾回收算法，通过判断活着的对象来推断垃圾对象
• 从栈上的根对象开始扫，通过引用链，用DFS或BFS来扫描所有对象
• 通过黑灰白三色抽象来管理扫描对象的状态
• 可能会产生内存碎片或者空洞，会导致新对象的分配失败，比如中间区域被分配，两边各有20MB没有被分配，此时没有办法分配30MB空间，虽然总的剩余空间是足够的

¶标记-压缩 (Mark-Compress)

• 将分散的、活着的对象移动到更紧密的空间来解决内存碎片问题
• 分为标记和压缩两个阶段，标记阶段和标记清扫算法一致，压缩部分则是对整个堆内存进行搜索并将内存活动对象进行压缩填充
• 缺点是内存对象在内存的位置是随机的，这常常会破坏缓存的局部性。并且需要多的空间和时间开销来标记对象的移动以及更新指针，增加实现复杂性

¶半空间复制 (Semispace Copy)

• 空间换时间，只能使用一半内存空间，另一半用于快速压缩内存
• 笑出了内存碎片问题，压缩时间比标记压缩更短。
• 不分阶段，在扫描的时候就可以直接压缩，每个对象都会从fromspace复制到tospace，扫描完成即压缩完成

¶引用计数 (Reference Counting)

• 被引用就+1，取消引用就-1，引用归零的时候就被回收，十分质朴
• 简单高效，也不用需要大量内存空间，即使GC系统的一部分出现异常也有一部分对象正常回收
• 但是对一些没有破坏性操作会重复计数，如循环迭代，内存或寄存器难以承受；需要使用原子更新，难以处理自引用对象

¶分代GC

• 将对象按照存活时间进行划分，认为死去的对象一半都是新创建不久的，因此不会反复扫描旧对象，实现部分优化，大概率加快GC速度
• 但是没有办法及时回收老一代的对象，需要额外开销引用来区分新老对象

Go中的GC

• Go使用的是标记清扫算法的变体并发三色标记
• 垃圾回收的打断时间在Go的版本更新中不断减少，也可以由用户手动执行
• 1.0 - 单协程垃圾回收
• 1.1 - 多协程并行执行
• 1.5 - 允许用于协程和垃圾回收同时执行
• 1.6 - 大幅减少STW期间的任务
• 1.8 - 使用混合写屏障计数消除栈重新扫描时间

全流程

¶垃圾回收循环

¶标记准备阶段

• 最重要的任务是清扫上一阶段GC遗留的需要清扫的对象，这是懒清扫算法的结果。需要关注两个问题：如何决定需要多少标记协程以及如何调度标记协程
• 重置各种状态和统计指标、启动用于标记的协程、统计需要扫描的任务量、开启写屏障等
• 这些步骤大多在STW (Stop The World) 时进行
• 会为每一个P启动一个标记协程，但有些可能没有执行机会
• Go规定后台标记协程消耗的CPU应该接近25%，一般只要25%的P数量即可。但是由于不是所有数字都能整除4，所以会比较复杂，代码在startCycle()函数中
• dedicatedMarkWorkersNeeded - 完整的标记协程的数量
• fractionalUtilizationGoal - 小于1，比如P为2时它为0/25，代表每个P在标记阶段需要话25%的时间执行后台标记协程。超出时间后，当前的后台标记协程可以被抢占然后执行别的协程。
• 在标记准备阶段执行了STW，此时暂停所有协程。当关闭STW再启动的时候，每个P都会进入新一轮的调度循环。循环开始的时候，调度器会判断程序是否处于GC阶段，如果是则尝试判断当前P是否需要执行后台标记任务
• 如果dedicated...大于0，那就立即执行；如果fractional...大于0且执行标记任务的时间小于f...x当前标记周期时间，那么也执行，但是不会一直执行，会标记为gcMarkWorkerFractionalMode

¶并发标记阶段

• 后台标记任务有三种不同的模式：DedicatedMode, FractionalMode, IdleMode
• DedicatedMode - 处理器单独负责标记对象
• FractionalMode - 协助标记后台，达到目标时间后会自行退出
• IdleMode - P没有可用G的时候，执行GC标记任务，直到被抢占
• 后台标记flag有4种，用于指定后台标记协程的不同行为
• gcDrainUntilPreempt - 当前标记协程处于可以被抢占的状态
• gcDrainFlushBgCredit - 会计算后台完成的标记任务量以减少并行标记期间用户协程执行辅助垃圾收集的工作量
• gcDrainIdle - 对应IdleMode模式
• gcDrainFractional - 对应FractionalMode模式
• 在DedicatedMode下，会一直执行后台标记任务，所以P的局部队列G执行不了。所以Go的做法是先执行可以被抢占的标记任务，如果标记协程被抢占了，那么就将抢占他的写成转移到全局队列中，并取消gcDrainUntilPreempt，不能被抢占
• 后台标记任务的三种模式都标记了gcDrainFlushBgCredit，会计算标记任务量

¶全局变量扫描

• 扫描的第一阶段是扫描根对象，在标记准备阶段会统计这次GC一共要扫描多少根对象，会采用原子加法避免并发问题
• 在Go中，根对象包括全局变量，span中的finalizer的任务数量，已经所有的协程栈。finalizer是Go对象绑定的析构器，内存释放的时候，需要调用这个函数，从而完整释放资源
• 然后是扫描全局变量，这需要编译与运行的共同努力，编译时确认全局变量中哪些位置包含指针，运行时确认全局变量被分配到哪一块内存
• 通过指针找到指针对应的mspan对象位置，然后标记span中的gcmarkBits以标记已找到

¶finalizer

• finalizer是析构起，用于释放对象，不会被栈上的活全局对象引用，因此需要单独处理。标记协程会遍历mspan中的specials链表，扫描finalizer所位于的元素（对象），然后扫描元素。注意这里并不能把这个对象直接加入根对象中，否则可能失去回收该对象的机会。同时需要扫描析构器字段fn，因为可能指向了堆中的内存，可能需要被回收
• 使用finalizer可以自动关闭释放用户忘记手动关闭释放的资源
• finalizer可以将函数的释放托管给GC，这样在例如CGO的高级场景中，用GC自动释放管理C语言部分的函数。finalizer函数并不一定要执行时机的内存释放，可以将当前指针存储起来有单独的协程定时释放

¶栈扫描

• 栈扫描是根对象扫描中最重要的部分，也需要编译和运行时的共同努力
• 编译时可以知道栈上有哪些指针，以及对象中哪一部分包含了指针
• 运行时能够计算出当前协程栈的所有栈帧信息，首先计算出栈帧布局，然后可以得知当前栈帧的函数参数、函数本地变量、寄存器SP、BP等一系列信息
• 每个栈帧的参数和局部变量都需要进行扫描，确认该对象是否仍然在使用，如果在使用则需要扫描位图判断对象中是否包含指针

¶栈对象

• 比如有时候p指针指向了对象t，之后p指针又指向别的地方去了，此时t并没有用，但按照保守算法t依然存在，因此可能出现内存泄露现象
• 为了解决内存泄露问题，Go引入了栈对象的概念，指栈上能被寻址的对象。编译器在编译时将所有栈对象都记录下来，同时追踪栈中所有可能指向栈对象的指针
• GC期间，所有的栈对象都会存储到一颗二叉搜索树中

¶扫描灰色对象

• 根对象收集完成之后，会从这些被标记为灰色的内存对象出发，扫描整个堆内存中活对象。扫描中，会尽量让标记对象进入本地队列中以减少锁的使用
• 进行扫描的时候，使用相同的原理，先从本地队列中找标记对象，没有就从全局变量中找。然后就实行BFS的扫描策略了
• 为了剪枝，Go通过gcmarkBits检查对象是否已经被扫描过了，也会通过heapArena中元数据中储存的是否含有指针以及需要被扫描的bitmap来判断是否要继续扫描这个span内对应的对象

¶标记终止阶段与调步算法

• 统计一些指标，比如统计用时，统计强制开始GC的次数，更新下一次触发GC需要达到的堆目标，关闭读写屏障等
• 终止阶段会再次进入STW

¶调步算法原因

• 重要阶段是计算下一次触发GC需要到达的堆目标，运用了垃圾回收的调步算法
• 使用并发的三色标记在GC的过程中，用户协程可能分配了大量内存，所以在GC的过程中，程序占用的内存大小实际上超过了我们设定出发GC的目标。所以需要堆程序进行估计，从而在达到内存占用量之前就启动GC，确保在GC结束之后，占用内存的大小刚好在目标内存附近

¶调步算法目标

• 简而言之，算出提前触发GC的最佳时间，以逼近最终内存目标，需要依赖本次GC的阶段差额（GC完成后占用内存与目标内存之间的差距）
• 第一个目标：最小化目标占用内存与GC完成后的占用内存的差距
• 第二个目标：预计执行的CPU占用率接近25%。
• 如果用户协程执行了过多的辅助标记，那么会导致GC完成之后占用内存偏小，因为用户协程将本来用来分配内存的时间用来执行辅助标记了

¶调步算法步骤

• 计算目标内存与GC完成后的占用内存的偏差，偏差率=(目标增长率-触发率)-(实际增长率-触发率)
• 目标增长率 = 目标内存 / 上一次GC完成后的标记内存 - 1
• 触发率 = 触发GC时的占用内存 / 上一次GC完成后的标记内存 - 1
• 实际增长率 = GC完成之后的内存 / 上一次GC完成后的内存标记 - 1
• 不过，为了修复辅助标记嗲来的偏差，计算辅助标记所用时间，最终的偏差率调整为偏差率=(目标增长率-触发率)-调成率×(实际增长率-触发率)，其中调整率=GC标记阶段的CPU占用率/目标CPU占用率
• 公式中可以看出，实际增长率和辅助标记的时长都会影响到最终的偏差率。下一次GC的触发率会渐进调整，每次只调整偏差的一半下次GC触发率=上次GC触发率+0.5×偏差率
• 计算完GC触发率之后，需要计算目标内存大小，其大小取决于本次GC扫描后的占用内存以及gcpercent的大小。gcpercent可以由用户自行设置，用户设置的是基准值，实际值会由gc通过前文的公式自行调整。当gopercent设置为0的时候，将禁用Go的GC

¶辅助标记

• 在并发标记阶段，扫描内存的同时用户协程也不断被分配内存，当用户协程内存分配速度快到标记协程来不及扫描的时候，GC标记阶段就永远无法结束，因而无法完成完整的GC周期，造成内存泄露
• 为了解决这个问题，当用户协程被分配了超过限度的内存的时候，会将其暂停并切换到辅助标记工作。策略是X = assistWorkPerByte × M，其中X是GC标记需要多扫描的内存，M是新分配的内存，assistWorkPerByte是每字节需要完成多少扫描工作，因为一个对象里面并不是所有的内存都需要扫描
• 在GC并发标记阶段，用户协程分配内存的时候，会先检查是否已经完成了指定的扫描工作。用户协程会从gcAssistBytes中获取内存，类似于内存资产池，也有本地和全局。局部没有了就从全局获取。全局资产池都没有了，那就需要停止用户协程，执行辅助标记协程。如果标记完了还是没有，那就进入休眠，当有资产的时候就会逐一唤醒

¶屏障技术

• 屏障技术可以解决用户协程和标记协程并发工作时的准确性问题，确保所有被引用的对象都能被扫描到
• 保证并发标记准确性需要遵守的原则，即强、弱三色不变性。强三色不变性指所有白色对象都不能被黑色对象引用。弱三色不变形指不允许白色被黑色对象引用，但是白色对象必须有一条路径始终被灰色对象引用。
• 一种策略是Dijkstra风格的插入屏障，如果目标对象src是黑色，那就把新引用的对象标成灰色
• 另一种策略是Yuasa删除屏障，在对象被解除引用之后，会立即将原引用对象标记为灰色。这样即使没有写屏障，在插入的时候也不会破坏三色不变性
• 这两种屏障在写入和删除时重新标记颜色保证了三色不变性，解决准确性问题，但是会产生浮动垃圾，可能标记一个已经变成垃圾的对象。这些浮动垃圾会在下一次垃圾回收中被回收。
• 这两种屏障独立存在并且正常工作的前提是并发标记期间所有的写入操作都用了屏障技术，但是实际上不会这样，大多数语言不会对栈上的操作或寄存器上的操作应用屏障技术，因为栈上的操作是最频繁的，运用屏障技术会大大减慢程序速度。
• 简而言之：插入屏障就是如果直接插在黑色上就变成灰色，符合强三色原理；删除屏障就是在断除引用关系的同时，引用的对象也标成灰色，这样满足弱三色原理。
• 在Go1.8之前，使用了插入平展，但是依然需要在标记终止期间STW阶段重新扫描根对象，以保证三色标记的一致性。在Go1.8之后，为了解决重复扫描的问题，使用了混合写屏障技术，同时结合了上述两种风格的屏障
• 混合写屏障依赖编译时和运行时的共同努力，在标记准备阶段STW会打开写屏障，并做好标记。编译器会在所有堆写入或删除操作前判断当前是否为GC标记阶段，如果是就执行混合写屏障标记对象。
• 在标记的时候，gcWriteBarrier会将所有被标记的指针放入缓冲池中，在容量满了之后，一次性全部刷新到扫描任务池中，最后执行扫描

¶垃圾清扫

• 垃圾标记工作完成之后，所有活着的对象都已经标记，然后就要开始清扫了
• 使用gcSweep函数，先将清扫协程的状态变成running，然后在结束STW的阶段开始重新调度循环的时候优先执行清扫协程
• 注意，程序中只有一个垃圾清扫协程，并且与用户协程同时运行。清扫协程在程序启动的时候一起启动，但是不会一直running
• 清扫协程采取懒清扫的策略，在执行少量清扫工作后，通过Gosched让渡自己的执行确立，不需要一直执行。因此在出发下一阶段垃圾回收后，可能有没有被清理的内存，需要将它们清扫完

¶懒清扫逻辑

• 清扫以span为单位，先从mheap中的清扫队列中取出需要清扫的span，然后开始清扫
• 清扫的时候，最重要的一步是将gcmarkBits位图赋值给allocBits位图，gcmarkBits的位为1的时候，代表该对象为活的，如果allocBits为0说明需要被回收。完成赋值时候，就可以使用allocBits来标记垃圾对象的内存了。
• 如果gcmarkBits整个为0，说明所有对象都亖了，此时整个span都被mheap回收，并更新整个内存基数树。如果并不完全为空，那么就再丢到mheap的清扫列表中。
• 这种方式并没有直接将内存释放被操作系统，而是组织内存内部循环

¶辅助清扫

• 如果剩余的span太多，那么就会大大拖后下一次GC开始的时间。所以与辅助标记类似，清扫也可以由用户协程辅助进行
• 目前有两个时机判断是否需要辅助扫描：需要向mcentrel申请内存的时候、在大对象分配的时候
• 这两个时间会判断当前清扫page数量与目标的关系，如果没达到目标就还是辅助清扫直到达到目标
• 辅助标记策略会尽可能地保证在下次触发GC的时候，已经扫描了所有待扫描的span

¶系统驻留内存清楚

• 驻留内存 (RSS) 是RAM保留的进程占用的内存部分，是从操作系统分配的内存
• 清除策略占用当前线程CPU 1%的时间来进行清除，因此在大部分时间里面，清除协程处于休眠状态
• 清除协程一次只能清除一个物理页，基本思路是在基数树中找到连续的没有被操作系统回收的内存，当pallocBits和scavenged对应的位同时为0的时候，这个page可以被清扫