垃圾回收基础

常见的垃圾回收算法

常见的垃圾回收算法有 Mark-Sweep、Mark-Compact、Copying、Reference Counting。
mark-sweep 算法实现是，根据对象之间的引用关系（看做一张图），对可达的对象进行标记，标记完成以后保留这些有标记的存活的对象，释放掉其他死亡对象占用的空间
mark-compact的算法与mark-sweep类似，也是先标记，不过标记完成以后mark compact 对象还会挪动存活对象的位置，使得存活的对象在内存中的排列更加紧凑，减少内存碎片。
Copying 算法把堆分成两半，分配都只在其中半个进行，当半个堆快满的时候，进行垃圾回收，先把根集拷贝到另外半个堆中，然后扫描对象，拷贝这个被引用的对象，直到所有存活的对象都被拷贝到另外半个堆中。当另外半个堆又满了，再拷回来。
引用计数算法比较直接，当一个对象被引用的时候，就把他对应的引用数+1，当其他对象取消对他的引用的时候，将其引用数-1，如果引用数是0，就直接销毁这个对象。
这几种垃圾回收算法中，有一些是压缩的，有一些是非压缩的，对于压缩的垃圾回收算法来说，配合简单高效的sequential allocation，不用担心碎片问题，相比非压缩的就没有这种优势，不过挪动对象的位置，会破坏缓存局部性优势。
引用计数和其余三种的不同是，引用计数把垃圾回收的开销分摊到了每次写指针的时候（引用发生变化），不会像其他几种垃圾回收算法每次在垃圾回收进行的时候会让程序停顿下来。不过引用计数有一个问题是需要处理好自引用，两个对象之间的互相引用，多个对象之间引用（构成环，并且这个没有从根集到这个环中任何一个节点的通路），相比之下其余三种tracing 类型的垃圾回收算法就不会有这个问题。
还有一些垃圾回收算法是这几种的延伸和改造，比如分代垃圾回收算法，其基于一个经验，新创建的对象往往很快死亡，但主要是存活下来的对象往往会一直存活下去。
golang 采用的是 mark-sweep 垃圾回收算法，mark-sweep算法的详细步骤是，先扫描根集，根集包括全局变量（指针类型）、栈帧中的存活指针及对象、Finalizer相关结构等等。扫描根集中的对象，把根集引用的堆对象添加到工作队列中，当根集扫描结束，开始清空工作队列，取出每个对象，扫描其每一个指针类型的字段，把被指针指向的对象再次添加到工作队列中，并标记对象。直到工作队列不再有新的对象被添加，并且工作队列为空，标记结束，进入清扫阶段，清扫阶段就是把没有被标记的堆空间释放掉。
下边这段文字是golang源码中的注释，对golang的垃圾回收算法特点做了一个精炼的描述。
Garbage collector (GC). The GC runs concurrently with mutator threads, is type accurate (aka precise), allows multiple GC thread to run in parallel. It is a concurrent mark and sweep that uses a write barrier. It is non-generational and non-compacting. Allocation is done using size segregated per P allocation areas to minimize fragmentation while eliminating locks in the common case.
golang 的垃圾回收是类型精确（type accurate）的，在C语言中，指针可以存储在整形中，但是在golang中，如果把指针存在整形中，并且这个指针是唯一一个指向其引用对象的指针，那么当垃圾回收程序运行完成以后，这个指针指向的对象的地址空间就会被回收，因为垃圾回收程序只会把指针类型里边存的值当成指针，对于int这样的标量，是不会考虑的。
golang 的垃圾回收是不分代，也不压缩的，不分代是因为在编译阶段，会有逃逸分析这一步骤，经过逃逸分析，可以把一些可以分配在栈上的对象直接分配在栈中，而不是堆上。（逃逸分析还会把一些原本会分配在栈上的对象改为在堆中分配）。不压缩是因为golang的使用的分配器设计可以减轻内存碎片的问题，所以没有必要做压缩，并且如果压缩了，就要移动对象，又会带来一些性能上的损耗
golang 的垃圾回收还支持mutator 与 collector 并行，并且支持并发扫描和并发清扫。mutator 指的是执行用户代码的那些go routine，而 collector则是与垃圾回收相关的go routine。这两者并行带来的好处是程序可以在垃圾回收的时候不停顿，满足对延迟比较敏感的使用场景，并行其中一个难点是如何保持准确性，如果在标记过程中，对象之间的引用关系被mutator改变了，或者是有新的对象创建了，就可能会造成collector 错误回收存活对象的空间。新对象创建，可以直接把新对象标记上，这样就不会错误回收新对象了。而对象之间的引用关系变化（指针的写操作）可以通过写屏障来解决，详细请看write barrier 一节。

Golang 垃圾回收的流程

触发

golang垃圾回收程序运行的触发有三种方式，第一种是通过后台监控的go routine （用M代称）定时触发，如果 M 发现上一次垃圾回收已经是两分钟之前了，那么就会触发垃圾回收。当程序启动以后，会启动一个go routine （用G代称）专门用于垃圾回收，当M触发垃圾回收的时候，只需要把G放入运行队列，当G被调度的时候，就会执行垃圾回收的逻辑。
第二种方式是用户触发，开发者可以在程序中调用接口runtime.GC()触发垃圾回收。
第三种是heap live 超过触发阈值（gc trigger）时，会启动垃圾回收。heap live 的值等于上次垃圾回收以后被保留的空间大小加上自那以后又分配的空间大小，当mcache 从 mcentral 获取 mspan 的时候，这个值会上升（上升的大小等于mspan 空闲空间的大小），当mcache 将 mspan 归还到mcentral 的时候，heap live 会下降，下降的值等于mspan的空闲空间，简言之，mcache中的mspan中尚未分配的空间也会被记录到heap live中，而mcentral中的mspan，只有已经被分配出去的slots 才会记录到heap live 中。heap live 的值也会受到大对象分配影响，不过这些都是细节。
gc trigger 是一个运行过程中会动态调整的值。
当分配大对象时，或者是一个mspan被分配完毕时，都会触发一次检测，查看heap live 是否已经超过了 gc trigger ，如果超过了，就开始运行垃圾回收程序。

标记预备工作以及任务的划分

在进行标记工作之前，首先得确保上一次垃圾回收的清扫工作已经结束。然后为每个P创建一个专用于标记的go routine （mark worker），这些 worker 还不会投入工作，runtine 调度器在寻找下一个可运行的runtine 的时候，只会在写屏障开启的情况下才会调度 mark worker 运行，写屏障会在GCmark阶段打开。golang 把垃圾回收过程分为三个状态，分别是 GCoff 、GCmark、GCmarktermination，这三个状态的转移关系是 GCoff ==> GCmark ==> GCmarktermination ==> GCoff。当进行清扫工作的时候，垃圾回收程序处于的是GCoff状态，当新一轮垃圾回收开始，为每个P创建完mark worker之后，垃圾回收程序会执行STOP THE WORLD操作，然后就会把状态从GCoff转到GCmark
STOP THE WORLD操作指的是暂停所有正在运行的mutator，这个时候开启写屏障是最安全的，在START THE WORLD之后，写屏障是否开启这个标记位的修改肯定对于各个mutator都可见了。如果不通过STOP THE WORLD这种手段，那么就必须通过原子操作读写 写屏障的开启的标志，这样能保证准确性，但是会严重影响性能。开启写屏障以后，所有的写指针操作都会执行写屏障中的逻辑，并且新分配的对象也会被标记上。
在STOP THE WORLD 和 START THE WORLD之间，除了上述的几件事，还需要统计标记阶段的任务、标记所有微小对象分配器管理的内存块。除了这些就没有其他的了（杂项不考虑），STOP THE WORLD停顿的时候如果太久的话，会影响到用户程序，因为有些应用要求低延迟，STOP THE WORLD这段时间内是无法响应的。
在STOP THE WORLD的时候单独对tinyalloc blocks进行标记处理，因为开启写屏障之前，如果tiny allocator 在分配的时候使用了一个新的slot ，并且这个分配的微小对象在标记开始前已经失去了别的对象对他的引用，那么当开始标记的时候，这个slot仍然不会被标记，所以当再次在这个slot分配对象时，这个新分配的对象就会被误回收（当slot满足当前微小对象分配时，是不会对这个slot进行标记的，就算是开启了写屏障，这是为了提高性能）。因此，在STOP THE WORLD的时候，对微小对象分配器特殊处理，把tiny所在的slot给标记。

mark worker 是并发扫描的，根集是中的元素来自于各个部分，比较大的部分都会被划分成小块，mark worker每次处理一个小块，扫描标记里边的根集合。对于BSS 和 DATA ，会以256KB大小进行划分，mspan占用的空间以512页进行划分，而栈以go routine的个数划分。
例如、如果DATA可以按256KB分成3块、BSS分成5块、mspan按512页分成10份、整个程序有5个go routine，那么根集的扫描工作量就是 3 + 5 + 10 + 5 = 23 ，collector 中用一个变量c来记录下一个一小份的任务，当一个mark worker 领取任务的时候，只需要把markrootNext + 1，而他领取到的任务就是原来的markrootNext 。根据这个值就可以知道是扫描位于哪里的根，[0,3) 表示扫描的是位于DATA 的部分，[18,23)表示的是扫描栈中的根，如果markrootNext是19就代表扫描第二个go routine的栈。

下图为伪代码

这边可以看到一个细节，就是在统计DATA和BSS片段数量的时候，使用了max。一个程序可能有多个modules构成（下图中画了3个），每个module都有DATA和BSS，work.nDataRoots 和 work.nBSSRoots 只保存最大的片段数量，并且在扫描的时候，每个module的DATA和BSS 相同标号的片段是一起扫描的。nStackRoots 的数量就等于allgs的长度，allgs 是一个切片，里边存储了所有go routine 的指针(不包括g0)

gcDrain 中包含了扫描根集的逻辑，gcDrain会被多个mark worker 并发执行，markroot会根据job 判断这个任务片段是位于DATA还是BSS还是栈或是其他。

标记根集以及清空Work Buffer

扫描BSS和DATA，需要通过位图（pointer mask）来指示哪里有指针，pointer mask 存在模块信息中。

上图是使用pointer mask （pointerMask）标记地址位于[begin,begin + sizeOfBlock)范围内指针的伪代码。其中pointerSize表示的是指针的大小，在64位平台下，指针的大小是8字节。findHeapObject 函数的作用是找到给定地址（addr）中存储的对象，如果addr这个地址不是go-heap中的，那么返回的obj就是空的，go-heap 指的就是per-P segregated allocator 管理的地址空间（不包括手动管理的mspan），obj 就是 mspan中的某个slot。grepObject的操作就是把这个slot在mspan中用于标记的位图中标记上，并且把该对象加入到work buffer中，后续对其进行扫描。

在根集扫描结束后，需要清空work buffer，清空work buffer 的过程就是从work buffer中取出对象，扫描对象。不过扫描对象的过程，可能会新增新的对象到work buffer中。下图是清空work buffer的伪代码实现（和Golang源码还是有很大的不同）

清扫

当标记结束以后，就开始进行并发清扫，每个mspan都是一个独立的清扫任务，后台有一个专门负责清扫的go routine，当标记阶段结束以后，会将其唤醒，除此之外，mutator 也会参与到清扫工作中。
后台清扫的 go routine 会从mcentral 的两个span Set （fullUnswept、partialUnswept）中逐个取出mspan 进行清扫，清扫结束后，如果发现这个mspan完全空闲，就会释放这个mspan，并且将其管理的页面归还到页面分配器中，并且更新页面分配器中的summary。如果mspan任有部分slot正在使用，那么就将其放回到mcentral中 partial Swept 对应的那个span Set 中
当mcache从mcentral中获取一个mspan的时候，如果mcentral中没有已经清扫过的mspan，那么只能获取一个没有清扫过的，对其执行清扫操作后用于使用。除此之外，mutator 本身也要承担一部分GC的工作，所以如果有大对象分配的需求，或者是从mcentral中获取mspan，就需要执行清扫工作，并把清扫的那部分mspan释放掉。
清扫一个mspan最重要的两项工作是把那些已经变成垃圾但是带有finalizer对象的finalizer放到 finalizer的执行队列中，等待后续被执行、另外一项工作是处理位图，处理位图非常简单，保存分配状态的位图只需要使用保存标记状态的位图替换即可，而至于保存标记状态的位图需要重新申请。