[数据结构与算法]HopSpot虚拟机垃圾回收算法实现细节

1. 根节点枚举——如何标记垃圾对象

在可达性分析算法中，从GC Roots集合开始进行自顶向下的搜索，每一条搜索路径都是一条引用链，当一个对象不在与任何一条引用链相关联时，可以被标记为垃圾对象。可达性分析算法的目标是找出所有与引用链不关联的对象。目前随着Java技术的不断发展，Java企业级应用越做越庞大，光是方法区的大小就常常有数百上千兆，里面包含大量的类、常量等信息，而方法区中类的静态属性引用的对象和常量引用的对象可以作为固定的GC Roots，如果以方法区为起点来检查每一个引用，势必会消耗大量的时间，造成查找过程效率低下。

解决方案：当用户线程停顿下之后，并不需要一个不漏的检查完所有执行上下文和全局的引用位置（虚拟机有办法可以直接得到哪些地方存放着对象引用）。HotSpot虚拟机使用一组成为OopMap的数据结构来实现（OopMap介绍参考：[1] 浅谈JVM中的OopMap ; [2] 虚拟机OopMap），HotSpot会在类加载完成时计算出对象内什么偏移量上是什么类型的数据，也会在特定位置记录下栈里和寄存器里哪些位置是引用。这样在扫描时就可以直接得知信息了。

OopMap简单介绍
可以把oopMap简单理解成是调试信息。在源代码里面每个变量都是有类型的，但是编译之后的代码就只有变量在栈上的位置了。oopMap就是一个附加的信息，告诉你栈上哪个位置本来是个什么东西。 这个信息是在JIT编译时跟机器码一起产生的。因为只有编译器知道源代码跟产生的代码的对应关系。 每个方法可能会有好几个oopMap，就是根据safepoint把一个方法的代码分成几段，每一段代码一个oopMap，作用域自然也仅限于这一段代码。 循环中引用多个对象，肯定会有多个变量，编译后占据栈上的多个位置。那这段代码的oopMap就会包含多条记录。

补充说明：迄今为止所有的垃圾收集器在根节点枚举这一步都是需要暂停用户线程的（也就是在初始标记时会触发 Stop The World），根节点枚举需要在一个能保证一致性的快照中进行（即在枚举过程中根节点集合的对象应用关系不会发生变化）。现在的可达性分析算法耗时最长的查找引用链的过程已经可以做到和用户线程一起并发执行。

2. 安全点——如何停顿用户线程

HotSpot可以在OopMap的协助下快速准确的完成GC Roots的枚举，但是导致OopMap内容变化的指令非常多，不能为每一条指令都生成对应的OopMap（会浪费大量的额外存储空间）。HotSpot会在特定位置记录这些信息，也就是 “安全点”，安全点决定了用户程序执行时并非在代码指令流的任意位置都能够停顿下来开始进行垃圾收集，而是强制要求必须执行到达安全点后才能暂停。

在垃圾收集时让所有线程都跑到最近的安全点的两种方案：抢断式中断 和 主动式中断：

• 抢断式中断：不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先将所有的用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程继续执行，让它一会在重新中断，直到跑到安全点上。
• 主动式中断：当垃圾收集需要中断线程时，不直接对线程操作，而是简单设置一个标记位，各个线程执行过程时会不断地主动去轮询这个标志，一旦发现中断标志为真时就自己在最近的安全点上主动中断挂起。轮询标记的地方和安全点是重合的。

补充说明：轮询操作在代码中会频繁出现，HotSpot使用内存保护陷进的方式把轮询操作精简至只有一条汇编指令的程度，比较高效。

3. 安全区域——如何停顿处于Sleep、Blocked状态的线程

安全点机制可以保证程序在执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点，那如果程序不执行时（没有分配处理器时间）呢？典型场景就是用户线程处于Sleep状态或者Blocked状态，这时候用户线程无法响应虚拟机的中断请求，不能再走到安全点去中断挂起自己。安全区域指能够确保在某一段代码片段之中，引用关系不会发生变化，在这个区域中的任意地方进行垃圾收集都是安全的。安全区域可以当做是扩展延长了的安全点。

补充说明：当用户线程进入安全区域时，这段时间内如果虚拟机要进行垃圾收集，则不用管这些已声明自己在安全区域中的线程；当线程要离开安全区域，它要检查虚拟机是否已经完成了根节点枚举过程，如果完成则当做无事发生，进行执行，否则它就必须一直等待，直到收到可以离开安全区域的信号为止。

4. 记忆表与卡表——如何处理跨代引用问题

分代收集理论

大多数商用虚拟机都采用了分代收集的思想，分代收集理论建立在两个假说之上：

• 弱分代假说：绝大多数对象都是朝生夕灭的
• 强分代假说：熬过越多次垃圾收集过程的对象就越难消亡
• 跨代引用假说：跨代引用相对于同代引用来说仅占极少数

设计规则

将Java堆划分出不同的区域，然后将回收对象依据年龄（对象熬过垃圾收集过程的次数）分配到不同的区域之中存储。通常堆空间会被分成新生代和老年代，在新生代中，每次垃圾收集时都会发现大批对象死去，每次回收后存活的少量对象会逐步晋升到老年代存放。

跨代引用

主流的垃圾收集器都是采用的分代回收机制，大多是分成新生代和老年代，不管是新生代的对象还是老年代的对象，它们都不是孤立的，对象之间可能存在着引用，比如一个新生代的对象被一个老年代的对象引用着，这种引用关系就是跨代引用。

垃圾回收器在新生代中会建立 “记忆表” 来避免将整个老年代加入到 GC Roots的扫描范围中。所有涉及到部分区域收集的垃圾回收器都会产生跨代引用问题。“记忆表” 是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构，最简单的实现方式是：用非收集区域中所有含跨代引用的对象数组来实现。

Class RememberedSet{
    Object[] set[SIZE];
}

在垃圾收集时，垃圾回收器只需要遍历 “记忆表” 来判断某一块非收集区域是否存在有指向收集区域的指针就可以了，并不需要了解这些跨代指针的全部细节。当然这样做的效率和成本都非常的高昂，在设计 “记忆表” 时可以考虑如下更加粗略的记录粒度来节省成本：

• 字长精度：每个记录精确到一个机器字长（也就是处理器的寻址位数，32 or 64），该字包含跨代指针
• 对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针
• 卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针

卡精度就是指的 “卡表” ，是目前最常用的一种记忆集具体实现形式，定义了记忆集的记录精度、与堆内存的映射关系等。（卡表和记忆集的关系如果HashMap和Map的关系）。HotSpot虚拟机以字节数组的形式实现卡表：

CARD_TABLE[this address >> 9] = 0;

数组的每一个元素对应其标识的内存区域中一块特定大小的内存块，称为 “卡页” ，大小是512个字节。一个 “卡页” 通常包含不止一个对象，只要卡页中存在一个或以上对象的字段存在着跨代指针，就将对应的卡表的数组元素设置为1，称这个元素变 “脏” ，否则标识为0。在垃圾收集时，只筛选出卡表中变脏的数据，就知道哪些页内存块包含跨代指针。

5. 写屏障——如何维护卡表状态

通过卡表来解决跨代引用问题，那么就存在另一个问题：卡表何时进行变脏？如何变脏？也就是卡表如何进行维护的问题。

毫无疑问，当有其他分代区域中对象引用了本区域对象时，其对应的卡表元素就会变脏（数组元素标识为1）。变脏的时间点原则上发生在引用类型字段赋值的那一刻。

写屏障可以看作在虚拟机层面对 “引用类型字段赋值” 这个动作的AOP切面，在引用对象赋值时会产生一个环形通知，供程序执行额外的动作，也就是说赋值的前后都在写屏障的覆盖范畴内。在赋值前的部分写屏障称为 “写前屏障” ，在赋值后的则称为 “写后屏障”。

/*
	HotSpot虚拟机的很多垃圾收集器都使用了写屏障
	在G1收集器出现之前的收集器都采用的是 写后屏障
*/
void oop_field_store(oop* field , oop new_value){
	// 引用字段赋值操作
	*field = new_value;
	// 写后屏障 完成卡表状态的更新
	post_write_barrier(field , new_value);
}

应用写屏障之后的虚拟机会为所有的赋值操作生成相应的指令，一旦收集器在写屏障中增加了更新卡表的操作，无论更新的是不是老年代对新生代对象的引用，每次只要对引用进行更新，就会产生额外的开销，但这个开销与Minor GC时扫描的整个老年代的代价相比还是低的多的。

6. 并发的可达性分析——如何解决用户、垃圾收集线程并发执行下的标记问题

可达性分析算法的理论上要求全过程都基于一个能保障一致性的快照中才能进行分析，意味着必须完全冻结用户线程的运行。但是为了减少用户线程的停顿时间，一些垃圾回收器会进行并发标记，即让用户线程和垃圾收集线程并发执行，这样就会产生一些问题：1. 把原本消亡的对象错误标记为存活；2. 把原本存活的对象错误标记为死亡。第一种情况只是产生了一些浮动垃圾而已，可以容忍，下次清理掉就行。而第二种情况就非常致命了，程序会因此发生错误。

想要解决或者降低用户线程的停顿时间，可以让用户线程和垃圾收集线程并发执行，那么就需要解决在标记过程中产生的动态标记的问题。在进行可达性分析时，引入了三色标记作为辅助工具进行遍历：

• 白色：表示对象尚未被垃圾收集器访问过。在可达性分析刚刚开始阶段所有的对象都是白色，若在分析结束后对象还是白色，则不可达
• 黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过了，黑色对象是安全存活的且不可能之间指向某个白色对象
• 灰色：表示对象已经被垃圾收集器访问过，但这个对象至少存在一个引用还没有被扫描

接下来通过示例图来演示一下可达性分析的过程：

step 1 ：初始状态只有GC Roots是黑色的，对象只有被黑色对象引用才能存活，否则会死亡。

step 2 ：扫描过程中以灰色对象为分界，从黑向白推进，进行标记。

step 3 ：扫描完成后，所有的白色对象都是垃圾对象，需要被清理，黑色对象全部安全存活。

step 4 ：用户线程在标记过程中进行了并发修改了引用关系，比如在扫描灰色节点时，原本的引用被切断了（绿色虚线），同时原来引用的对象又与已经扫描过的黑节点建立了新引用（红色实线）。

step 5 ：这种切断后重新被黑色对象引用的对象可能是原来的引用链中的一部分，由于黑色对象不会重复扫描，将导致扫描结束后出现的两个被黑色对象引用的对象仍然是白色，这个对象（蓝色实线指的对象）将被回收，非常危险。

当且仅当如下两个条件同时满足时，才会产生 “对象消失” 问题，即原本应该是黑色的对象被错误标记为白色：

• 赋值器插入一条或者多条从黑色对象到白色对象的新引用
• 赋值器删除全部从灰色对象到该白色对象的直接或者间接引用

破坏两个条件的任意一个即可防止发生 “对象消失” ，由此产生两种解决方案：

• 增量更新：破坏第一个条件，当黑色对象插入新的指向白色对象的引用关系时，就将这个新插入的引用记录下来，等扫描结束后再将这些记录过的引用关系中的黑色对象为根，重新进行扫描标记（黑色对象一旦新插入指向白色对象的引用后就变成灰色对象）。
• 原始快照：破坏第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个新插入的引用记录下来，等扫描结束后再将这些记录过的引用关系中的灰色对象为根，重新进行扫描标记（无论引用关系删除与否，都会按照刚刚开始扫描那一刻的对象图快照来进行搜索）。

本文参考周志明老师的《深入理解Java虚拟机》