聊聊GC是如何快速枚举根节点的

本文已收录至Github，推荐阅读 ? Java随想录

微信公众号：Java随想录

CSDN： 码农BookSea

世界上最快乐的事，莫过于为理想而奋斗。——苏格拉底

HotSpot使用的是可达性分析算法，该算法需要进行根节点枚举，查找根节点枚举的过程要做到高效并非一件容易的事情，现在Java应用越做越庞大，光是方法区的大小就常有数百上千兆，里面的类、常量等更是恒河沙数（一种修辞手法），若要逐个检查以这里为起源的引用肯定得消耗不少时间。

大家可以思考下，如果你是JVM的开发者，你会怎么去做？

看完这一章节，你或许会跟我一样，感叹JVM开发者的智慧。

什么是根节点枚举

顾名思义，根节点枚举就是找出所有的GC Roots。

固定可作为GC Roots的节点主要在全局性的引用（例如常量或类静态属性）与执行上下文（例如栈帧中的本地变量表）中。

固定可作为GC Roots的对象包括以下几种（摘抄自《深入理解虚拟机 第3版》）：

• 在虚拟机栈（栈帧中的本地变量表）中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等。
• 在方法区中常量引用的对象，譬如字符串常量池（String Table）里的引用。
• 在本地方法栈中JNI（即通常所说的Native方法）引用的对象。
• Java虚拟机内部的引用，如基本数据类型对应的Class对象，一些常驻的异常对象（比如NullPointExcepiton、OutOfMemoryError）等，还有系统类加载器。
• 所有被同步锁（synchronized关键字）持有的对象。
• 反映Java虚拟机内部情况的JMXBean、JVMTI中注册的回调、本地代码缓存等。

根节点枚举存在的问题

迄今为止，所有收集器在根节点枚举这一步骤时都是必须暂停用户线程的，因此毫无疑问根节点枚举与之前提及的整理内存碎片一样会面临相似的“Stop The World”的困扰。根节点枚举必须在一个能保障一致性的快照中才得以进行——这里“一致性”的意思是整个枚举期间执行子系统看起来就像被冻结在某个时间点上。

为什么要这么做？

如果不”冻结”的话，根节点集合的对象引用关系在不断变化，那么分析结果准确性也就无法保证。所以即使是号称停顿时间可控，或者（几乎）不会发生停顿的CMS、G1、ZGC等收集器，在枚举根节点这一步也是必须要停顿的。

如何解决根节点枚举的问题

目前主流Java虚拟机使用的都是准确式垃圾收集（准确式 GC 使用的对象访问定位方式是直接指针访问），所以当用户线程停顿下来之后，其实并不需要一个不漏地检查完所有执行上下文和全局的引用位置，虚拟机应当是有办法直接得到哪些地方存放着对象引用的。
在HotSpot的解决方案里，是使用一组称为OopMap的数据结构来达到这个目的。OopMap可以理解为就是映射表，存储栈上的对象引用的信息，这是一种空间换时间的做法。在 GC Roots 枚举时，只需要遍历每个栈桢的 OopMap，通过 OopMap 存储的信息，快捷地找到 GC Roots。

用大白话说，其实就是用类似映射表这种手段记录下来引用关系，时不时去更新下映射表，然后根节点枚举只需要扫描映射表就知道哪些地方存放引用了，而不用去进行全局扫描。

安全点

OK，问题又来了，既然OopMap是一个映射表，这个表什么时候被更新？要知道引用关系变化是十分频繁的，如果引用每变化一次就更新对应的OopMap，那将会需要大量的额外存储空间，这样垃圾收集伴随而来的空间成本就会变得无法忍受的高昂。

解决这个的办法就是安全点，事实上，只是在“特定的位置”记录了这些信息，这些位置被称为安全点（Safepoint）。因此GC不是随时随地来的，得到达安全点时才可以开始GC。

一般会在如下几个位置选择安全点：

• 循环的末尾
• 方法临返回前
• 调用方法之后
• 抛异常的位置

但是还有一个问题是需要考虑的：如何在垃圾收集发生时让所有线程都跑到最近的安全点，然后停顿下来。

有两种方案可供选择：抢先式中断（Preemptive Suspension）和主动式中断（Voluntary Suspension）。

• 抢先式中断：不需要线程的执行代码主动去配合，在垃圾收集发生时，系统首先把所有用户线程全部中断，如果发现有用户线程中断的地方不在安全点上，就恢复这条线程执行，让它一会再重新中断，直到跑到安全点上。现在几乎没有虚机实现采用抢先式中断来暂停线程响应GC事件。
• 主动式中断：当垃圾收集需要中断线程的时候，不直接对线程操作，仅仅简单地设置一个标志位，各个线程执行过程时会不停地主动去轮询这个标志，一旦发现中断标志为真时就自己在最的安全点上主动中断挂起。轮询标志的地方和安全点是重合的，另外还要加上所有创建对象和其他需要在Java堆上分配内存的地方，这是为了检查是否即将要发生垃圾收集，避免没有足够内存分配新对象。

安全区域

安全点的设计似乎已经完美解决如何停顿用户线程，但是仍然有问题，安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但是，程序“不执行”的时候呢？

所谓的程序不执行就是没有分配处理器时间，典型的场景便是用户线程处于Sleep状态或者Blocked状态，这时候线程无法响应虚拟机的中断请求，不能再走到安全的地方去中断挂起自己。对于这种情况，JVM引入安全区域（Safe Region）来解决。

安全区域是指能够确保在某一段代码片段之中，引用关系不会发生变化，因此，在这个区域中任意地方开始垃圾收集都是安全的。我们也可以把安全区域看作被扩展拉伸了的安全点。

当用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域，那样当这段时间里虚拟机要发起垃圾收集时就不必去管这些已声明自己在安全区域内的线程了。**当线程要离开安全区域时，它要检查虚拟机是否已经完成了根节点枚举（或者垃圾收集过程中其他需要暂停用户线程的阶段），如果完成了，那线程就当作没事发生过，继续执行；否则它就必须一直等待，直到收到可以离开安全区域的信号为止。

如果本篇博客有任何错误和建议，欢迎给我留言指正。文章持续更新，可以关注公众号第一时间阅读。