# 垃圾收集实现
上篇主要讲了一些垃圾收集算法的原理，那么到了生产实践中，又是另一番模样了，本篇会从实现角度来描述虚拟机的垃圾收集机制
# 根节点枚举
在枚举根节点，也就是在全局中寻找GC Roots的时候，即便是从一些带范围性的地方，比如全局性的引用（如常量或类静态属性）和执行上下文（如栈帧中的局部变量表）中查找，要做到高效也是非常难的，逐个检查引用需要消耗很多时间
哪怕至今，虽然在可达性分析里耗时最长的查找引用链的过程，已经可以做到与用户线程一起并发，但是任何垃圾收集器在根节点枚举这一步，都必须暂停用户线程，和之前提到的整理内存碎片一样会面临“Stop The World”，因为在整个枚举期间，整个子系统都必须看起来像冻结在某个时间点一样，不允许出现在枚举过程中，根节点集合的对象引用关系仍在不断变化的情况。如果这点无法满足，那么分析结果的准确性也无法得到保证，这也是垃圾收集过程必须停顿用户线程的其中一个重要原因
由于目前市面上主流Java虚拟机都是准确式垃圾收集（即虚拟机有能力知道内存中某个位置的数据具体是什么类型，能知道这里存放的是基本类型数据还是引用类型数据，且无需像基于句柄的对象查找方式一样多一次间接查找开销），虚拟机有办法直接知道哪些地方存放的对象引用。在HotSpot的解决方案里，使用了一组称为OopMap的数据结构来实现，在类加载动作完成后，虚拟机会把对象内什么偏移量上是什么类型的数据计算出来，在即时编译过程中，也会在特定的位置记录下栈里和寄存器里哪些位置是引用，这样收集器在扫描的时候可以直接得到这些信息，无需一个个从方法区等GC Roots开始查找
OopMap记录的是栈上局部变量到堆上对象的引用关系，它的作用是在垃圾收集时，GC线程需要扫描栈上的引用类型，来确认并标记引用的对象是否可以回收，但问题在于，栈上的局部变量表里，只有一部分数据是引用类型的，也是收集器所关注的，如果扫描整个栈，是对资源的一种浪费，所以利用OopMap把栈上代表引用的位置都记录下来，这样到了GC的时候，GC线程可以直接读取到引用，不用全栈扫描
一个线程对应一个栈，一个栈由多个栈帧组成，一个栈帧对应一次方法调用，一个方法中会有多个安全点，当发生GC时，线程会运行到最近的一个安全点停下来，然后更新自己的OopMap，让GC线程可以快速找到这些被引用的对象
还有个地方需要注意的是，在字节码被编译成汇编码后，变量类型信息都是丢失的，留下的只有变量在栈上的位置信息了，而OopMap就是这样一个附加信息，能告诉你栈上这个位置对应到编译前原本有些什么，这个信息是在编译时产生的，因为也只有编译器能将这两部分信息关联起来。每个方法可能会有多个OopMap，比如循环体中引用的多个对象等，编译后会占据栈上的多个位置
[Verified Entry Point]
0x026eb730: mov %eax,-0x8000(%esp)
…………
;; ImplicitNullCheckStub slow case
0x026eb7a9: call 0x026e83e0 ; OopMap{ebx=Oop [16]=Oop off=142}
;*caload
; - java.lang.String::hashCode@48 (line 1489)
; {runtime_call}
0x026eb7ae: push $0x83c5c18 ; {external_word}
0x026eb7b3: call 0x026eb7b8
0x026eb7b8: pusha
0x026eb7b9: call 0x0822bec0 ; {runtime_call}
0x026eb7be: hlt
2
3
4
5
6
7
8
9
10
11
12
13
上面是HotSpot虚拟机在客户端模式下生成的一段String::hashCode()方法的本地代码，在0x026eb7a9处的call指令有OopMap记录，它指明EBX寄存器和栈中偏移量为16的内存区域中各有一个普通对象指针（Ordinary Object Pointer，OOP）的引用，有效范围为从call指令开始直到0x026eb730（指令流的起始位置）+142（OopMap记录的偏移量）=0x026eb7be，即hlt指令为止
# 安全点（Safepoint）
有了OopMap，虚拟机就可以快速准确地完成GC Roots的根节点枚举，但是如果为每个会引起OopMap内容变化的指令都生成对应的OopMap，那存储空间的代价是非常高的，在哪些地方来记录OopMap比较合适呢
一些特定的地方，才会记录OopMap信息，这些地方被称为安全点（Safepoint）。当要开始发生GC时，不是任何地方都可以让用户线程停顿下来并开始GC工作的，而是强制必须执行到达安全点才可以暂停用户线程，因此，安全点的选择，既不能太少，让垃圾收集器等待时间过长，也不能太多，导致运行时的内存负荷过大。安全点的位置选择基本上是以“是否具有让程序长时间执行的特征”为标准来确定的，长时间执行最明显特征就是指令序列的复用，比如方法调用、循环跳转、异常跳转等都属于指令序列复用
那么用户线程怎么知道自己到达了安全点呢？有两种方案可选：
- 抢先式中断（Preemptive Suspension）
- 主动式中断（Voluntary Suspension）
抢先式中断不需要线程主动配合，当GC时，系统先把所有用户线程中断，然后如果发现有线程中断的地方不在安全点上，就恢复线程执行，一会再次中断，直到跑到安全点上，基本上没有虚拟机会采用这种方式
主动式中断的思想是，设立一个标志位，用户线程在执行的时候，会去不停轮询标志位，当GC时，标记位被置为真，表示要开始GC了，线程会开始准备在自己最近的安全点主动中断挂起。轮询标志的地方和安全点是同一个地方
0x01b6d627: call 0x01b2b210 ; OopMap{[60]=Oop off=460}
; *invokeinterface size
; - Client1::main@113 (line 23)
; {virtual_call}
0x01b6d62c: nop ; OopMap{[60]=Oop off=461}
; *if_icmplt
; - Client1::main@118 (line 23)
0x01b6d62d: test %eax,0x160100 ; {poll}
0x01b6d633: mov 0x50(%esp),%esi
0x01b6d637: cmp %eax,%esi
2
3
4
5
6
7
8
9
10
如上，由于轮询会频繁被执行，所以必须保证简单高效，HotSpot使用内存保护陷阱的方式，把轮询操作精简到只有一条汇编代码的程度，当需要GC了，虚拟机把0x160100的内存页设置为不可读，线程执行到test指令就会产生一个自陷异常信号，然后在预先注册的异常处理器中挂起线程实现等待，这样就通过仅仅一条汇编指令完成了安全点的轮询和触发线程中断操作了
# 安全区域（Safe Region）
虽然有了安全区，以及主动式中断，但是对于那些本就是没有在执行的线程怎么办呢，比如Sleep或Blocked状态的线程，这个时候并没有分配处理器时间片给它们，这里，就必须引入安全区域（Safe Region）来解决这个问题
安全区域能确保在某段代码片段之中，引用关系不会发生变化，因此在这个区域中任意地方开始垃圾收集都是安全的，当用户线程执行到安全区域里的代码时，会标识自己已经进入安全区域，那么虚拟机要发起垃圾收集的时候就无需去管已经声明自己在安全区域的线程了，当线程要离开安全区域，它要去检查虚拟机是否已经完成了根节点枚举，如果完成了，就继续执行，如果没有完成，就要一直等待，直到收到可以离开安全区域的信号为止
# 记忆集与卡表（Remember Set & Card Table）
记忆集是一种用于记录从非收集区域指向待收集区域的指针集合的抽象数据结构，为了解决之前提到的跨代引用问题，但是如果记录全部的跨代引用对象，对空间占用和维护来说成本都十分高昂
而实际上，收集器只需要知道一块非收集区域里是否存在到待收集区域的引用就可以了，无需知道所有跨代指针的细节，较为粗粒度的记录粒度能节省不少成本：
- 字长精度：每个记录精确到一个机器字长（处理器的寻址位数，常说的32/64位系统就是这个意思）
- 对象精度：每个记录精确到一个对象，对象里有字段包含跨代指针
- 卡精度：每个记录精确到一块内存区域，区域里有对象含有跨代指针
其中第3种就是使用一种称为卡表（Card Table）的方式来实现记忆集，可以说卡表是记忆集的一种实现，在HotSpot虚拟机中，下面这行代码就是默认的卡表标记逻辑
CARD_TABLE [this address >> 9] = 0;
CARD_TABLE是个字节数组，它里边每一个元素，都对应着其标识的一块特定大小内存区域，这个内存区域被称为卡页（Card Page），一般来说，卡页大小都是2的整数次幂的字节数，上面代码可以看出HotSpot中卡页事2的9次幂，即512字节（地址右移9位，相当于用地址除以512），也就是说，如果卡表标识的内存区域，起始地址是0x0000，那么CARD_TABLE[0]就对应了0x0000~0x01FF，CARD_TABLE[1]就对应了0x0200~0x03FF，这样依次类推
那么卡页中呢，就记录了不止一个对象，只要该卡页中有一个或更多对象的字段存在跨代引用，那么这个卡页对应的卡表的数组元素的值，就会被标记为1，标识这个元素变脏了，当GC时，只要筛选出卡表中值为1的元素，就能知道它包含了跨代引用，加入GC Roots一并扫描
那么为什么卡表用Byte数组而不是bit数组呢，这样占用空间不是更小吗，答案是处于速度考量，现代计算机硬件都是最小按字节寻址，没有直接存储一个bit的指令，用bit的话还不得不多消耗几条shift+mask命令，这就得不偿失了
# 写屏障（Write Barrier）
卡表卡页解决了GC Roots扫描范围过大的问题，同时呢，也带来了新的维护问题，卡表何时变脏，谁来使卡表变脏呢
卡表何时变脏，这个是非常明确的，当对象赋值的一刻去维护卡表卡页就可以了，解释执行的字节码还好处理，但如果是编译后的机器指令流呢，就必须找到一个方法把维护卡表的操作放到每一个赋值操作中
HotSpot虚拟机是通过写屏障来维护卡表状态的，这个词可能不太好理解，如果是经常使用Spring开发的同学应该对AOP就很熟悉了，写屏障就可以看作是虚拟机层面对引用类型字段赋值这个动作的AOP切面，在赋值前叫写前屏障（Pre-Write Barrier），在赋值后的叫写后屏障（Post-Write Barrier），直到G1收集器出现之前，其他收集器都只用到了写后屏障
void oop_field_store(oop* field, oop new_value) {
// 引用字段赋值操作
*field = new_value;
// 写后屏障，在这里完成卡表状态的更新
post_write_barrier(field, new_value);
}
2
3
4
5
6
上面就是一段更新卡表状态的简化逻辑，应用了写屏障后，虚拟机会为所有赋值操作生成相应指令，一旦收集器在写屏障中增加了这个操作，无论是否老年代对新生代对象的跨代引用，每次赋值，都会产生额外的开销，不过比起Minor GC时扫描整个老年代的代价是低得多的
除了额外开销之外，写屏障还会在高并发场景下遇到伪共享（False Sharing）问题，现代CPU的缓存系统中是以缓存行（Cache Line）为单位存储的，当多个线程修改互相独立的变量时，这些变量又恰好共享了同一个缓存行，就会彼此影响（写回，无效化或者同步）而导致性能降低
假设处理器的缓存行大小为64字节，由于一个卡表元素占1个字节，64个卡表元素将共享同一个缓存行，这64个卡表元素对应卡页总内存为32KB（64x512字节），也就是说，如果不同线程更新的对象，正好处于这32KB内存区域时，就会导致伪共享问题而影响性能，为了避免它，一种简单解决方案就是先检查卡表标记，只有当卡表元素未被标记过时才将其标记为变脏，如下
if (CARD_TABLE [this address >> 9] != 0)
CARD_TABLE [this address >> 9] = 0;
2
在JDK7之后，HotSpot虚拟机增加了一个新的参数-XX:+UseCondCardMark，用来决定是否开启卡表更新的条件，开启会增加一次额外判断开销，但可以避免伪共享问题带来的性能下降，需要自行权衡
# 并发的可达性分析
在可达性分析时，必须保证在一致性的快照中才能进行，也就意味着需要冻结全部用户线程，在根节点枚举过程中，已经可以通过OopMap这种方式优化不少停顿时间了，起码不随着Java堆中对象数量正比例增长了，但是遍历对象图这个过程，整个停顿时间就和堆内对象数量成正比了，也和对象图结构复杂度有关
那么，想要进一步降低停顿时间，我们就要知道为什么必须要在一个能保障一致性的快照上，才能遍历对象图，为了解释这个问题，我们引入三色标记（Tri-color Marking）作为工具，把遍历对象图过程中遇到的对象，按照“是否访问过”标记成以下三种颜色：
- 白色：表示对象尚未被垃圾收集器访问到
- 黑色：表示对象已经被垃圾收集器访问过
- 灰色：表示对象已经被垃圾收集器访问过，但这个对象至少存在一个引用还没有被访问过
我们假设收集器在对象图上开始标记颜色了，如果用户线程都是暂停的，不会有任何问题，那么如果用户线程和收集器线程是并发工作的呢，可能会出现两种后果：
- 把原本消亡的对象错误标记成存活，这不是什么严重问题，下次收集大概率会清理掉它们
- 把原本存活的对象错误标记成已消亡，这就会导致致命后果了
此时是初始状态，只有GC Roots是黑色，需要注意一下箭头，因为扫描是顺着引用关系来遍历对象图，所以是有向的，只有被黑色对象引用的对象才能存活，否则消亡
在遍历过程中，以灰色为波峰的波纹从黑向白推进，灰色对象是黑白对象的分界线
遍历顺利完成，此时黑色对象都是存活的，白色对象已被标记消亡，可被回收
假如，在遍历过程中，用户线程并发修改了引用关系，一个灰色对象切断了到白色对象的引用，然后原来被引用的白色对象，又和已遍历过的黑色对象建立了引用关系
又假如，这种切断后重新被黑色对象引用的对象可能是原有引用链中的一部分，由于黑色对象不会被再次遍历，会导致遍历结束后出现两个被黑色对象引用的对象仍然是白色，这个对象就会消失
Wilson在1994年从理论上证明了，当且仅当以下两个条件同时满足时，会产生对象消失的问题，即原本黑色的对象被误标记为白色：
- 赋值器插入了一条或多条从黑色对象到白色对象的新引用
- 赋值器删除了全部从灰色对象到该白色对象的直接或间接引用
那么我们要解决并发扫描时的对象消失问题，只需要破坏其中一个条件即可，分别对应两种方案：
- 增量更新（Incremental Update）：破坏第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就把这个新插入的引用记录下来，等扫描完成后，再把这些记录过的引用关系中的黑色对象为根的，重新扫描一次（即黑色对象一旦新插入了指向白色对象的引用之后，它就变回灰色对象了）
- 原始快照（Snapshot At The Beginning, SATB）：破坏第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，在并发扫描结束后，再将这些记录过的引用关系中的灰色对象为根，重新扫描一次（即无论引用关系删除与否，都会按照刚刚开始扫描的那一刻的对象图快照来进行搜索）
以上两种方案都有实际应用，比如CMS基于增量更新，G1，Shenandoah则是基于原始快照来实现的
# 总结
到这里，我们已经知道了如何完成根节点枚举的两个阶段的实现与优化方案，下篇我们会开始进一步针对各个虚拟机来一起看下各自的特征，以及整个垃圾收集实现的发展历程