HotSpot 的算法细节实现

文章 生存还是死亡？？介绍了两种对象存活判定算法：引用计数算法、可达性分析算法 (HotSpot VM 使用这种算法)

文章 垃圾收集算法 介绍了三种垃圾收集算法：标记-清楚算法、标记-复制算法、标记-整理算法

下面从六个角度总结一下 HotSpot VM 的算法实现细节

根节点枚举

可达性分析算法主要就做两件事：枚举根节点 & 查找引用链

耗时最长的查找引用链过程已经可以做到与用户线程一起并发执行，也就是不需要用户线程 STW

但是枚举根节点始终还是必须在一个能保障一致性的快照中才得以进行，否则在分析的过程中，根节点集合的对象引用关系还在不断的变化中

就如同麻麻在打扫房间的垃圾，可同时你却还在不停的制造垃圾，这种情况不仅会导致垃圾始终清理不完，还会导致你被打！！

下面给一段代码加深根节点枚举的过程中不能发生变化的理解：


public static void main(String[] args) {
    List<Integer> GCRoots = new ArrayList<>();
    GCRoots.add(1);
    GCRoots.add(2);
    GCRoots.add(3);
    for (int root : GCRoots) {     // 枚举 GCRoots
        // 从 root 向下查找引用链
        GCRoots.add(4);            //  变化点 1
        GCRoots.remove(2);         //  变化点 2
    }
}

上面的代码在运行过程中会抛出异常：


xxxxxxxxxx
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
    at java.util.ArrayList$Itr.next(ArrayList.java:861)
    at com.lfool.myself.Test01.main(Test01.java:20)

我们知道固定可以作为 GC Roots 的节点主要就那么几类：全局性的引用 (如：常量、类静态属性)，执行上下文 (如：栈帧中的本地变量表)

虽然目标明确，但如果每次确定 GC Roots 时都从内存中逐个检查未来也太慢了，更有甚者如果连哪些内存中存的是引用都不知道的话将难上加难

但好在目前主流 Java 虚拟机都是准确式垃圾收集，何为准确式垃圾收集？？它指虚拟机可以知道内存中某个位置的数据具体是什么类型！！

虽然知道了某个内存位置的数据类型，但在枚举根节点时还是要遍历所有的全局性引用和执行上下文，如果我们还能知道哪些地方存放着引用就好了

别慌，既然提到了，那必然可以做到！！在 HotSpot 的解决方案里，使用了一组称为 OopMap (Ordinary Object Pointer Map，普通对象映射) 的数据结构来到达这个目的

在 HotSpot 中，对象的类型信息里有记录自己的 OopMap，记录了该类型的对象内什么偏移量上是什么类型的数据。所以从对象开始向外的扫描可以是准确的；这些数据是在类加载过程中计算得到的

被 JIT 编译过后的方法也会在一些特定的位置记录下 OopMap，记录了执行到该方法的某条指令时，栈上和寄存器里哪些位置是引用。这样 GC 在扫描栈时只需要查找这些 OopMap 就知道哪里是引用

下面给出一个 OopMap 中具体的内容：OopMap {ebx=Oop [16]=Oop off=142}；它表示：EBX 寄存器和栈中偏移量为 16 的内存区域中各有一个普通对象指针的引用，有效范围为从 OopMap 所在指令到指令流的起始位置 + off (142) 为止！！

安全点

安全点的选取

在 OopMap 的协助下，HotSpot 可以快速准确地完成 GC Roots 枚举，但一个很现实的问题随之而来：可能导致引用关系变化，或者说导致 OopMap 内容变化的指令非常多，如果为每一条指令都生成对应的 OopMap，那将会需要大量额外的存储空间，这样垃圾收集伴随而来的空间成本也会变得无法忍受

实际上 HotSpot 也并没有为每条指令都生成 OopMap，只有在特定的位置记录这些信息，这些位置被称为安全点

有了安全点的设定，也就决定了用户程序执行时并非在代码指令流的任意位置都能够停下来开始垃圾收集，而是强制要求必须执行到达安全点才能够暂停

所以，安全点的选定既不能太少以至于让垃圾收集器等待的时间过长；也不能太多以至于过分增加运行时的内存负担

安全点位置的选取基本上是以「是否具有让程序长时间执行的特征」为标准进行选定的，因为每条指令执行的时间都非常短暂，程序不太可能因为指令流长度太长而长时间执行

「长时间执行」的最明显特征就是指令序列的复用，例如：方法调用、循环跳转、异常跳等都属于指令序列的服用，所以只有具有这些功能的指令才会产生安全点

如何保证所有线程都到达安全点

上面讨论了安全点的选取问题，现在还有另外一个问题：线程只有到达了安全点，才可以停下来进行垃圾收集，如果只有一个线程还比较容易，但如果有非常多的线程 (事实上一个 JVM 进程中有许多线程)，垃圾收集器是如何保证垃圾收集时所有线程都到达了最近的安全点呢？？

这里有两种方法：抢先式中断 & 主动式中断

抢先式中断：当垃圾收集发生时，系统首先将所有线程中断，然后把没有到达安全点的线程恢复执行，直到它跑到最近的安全点上时再次中断 (现在几乎没有虚拟机实现采用该方法)

主动式中断：当垃圾收集发生时，只简单的设置一个标志位，各线程在执行的过程中会不断轮询这个标志，一旦发现中断标志为真时就主动在最近的安全点上中断挂起

然而轮询标志也不是无时无刻永不停歇的进行着，轮询标志的地方和安全点是重合的，如果在非安全点的地方也不停的轮询标志，就算标志为真，也还是需要执行到安全点才能停，所以不如直接在安全点时轮询一遍，如果为真就可以直接停下！！

另外，还需要在「所有创建对象」和「其他需要在 Java 堆上分配内存」的地方轮询标记，这是为了检查是否即将要发生垃圾收集，避免没有足够的内存分配新的对象

下面继续讨论一下轮询操作底层是如何实现的？！由于轮询操作在代码中非常频繁，这就要求它必须足够高效！！HotSpot 使用内存保护陷阱的方式，把轮询操作精简至只有一条汇编指令的程度

test指令就是 HotSpot 生成的轮询指令，当需要暂停用户线程时，虚拟机就把某个内存页设置为不可读，那线程执行到test指令时就会产生一个自陷异常信号，然后在预先注册的异常处理器中挂起线程实现等待，这样仅通过一条汇编指令便完成安全点轮询和触发线程中断！

安全区域

安全点机制保证了程序执行时，在不太长的时间内就会遇到可进入垃圾收集过程的安全点。但如果程序「不执行」呢？例如：用户线程处于 Sleep 的状态或者 Blocked 状态，这个时候线程无法响应虚拟机的中断请求，不能再走到安全的地方去中断挂起自己，虚拟机也显然不可能持续等待线程重新被激活分配处理器时间。对于这种情况，就必须引入安全区域来解决

安全区域是指能够确保在某一段代码片段中，引用关系不会发生变化，因此在这个区域中任意地方开始垃圾收集都是安全的

进入：首先用户线程执行到安全区域里面的代码时，首先会标识自己已经进入了安全区域，那么这段时间虚拟机发生垃圾收集时就不需要去管已声明自己在安全区域内的线程

离开：当用户线程要离开安全区域时，它就要检查虚拟机是否已经完成了根节点枚举，如果完成了，那么线程就当没事发生过，继续执行；否则就必须一直等待，直到收到可以离开安全区域的信号为止

记忆集与卡表

在文章 分代收集理论 中介绍了跨代引用，它用记忆集来优化根节点枚举，避免了全局检索，节约了时间开销，这一部分就详细谈谈记忆集是个什么东西？！

记忆集是一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构

如果不考虑效率和成本的话，最简单的实现可以用非收集区域中所有含跨代引用的对象数组来实现这个数据结构，但无论是空间占用还是维护成本都是相当高的

我们完全不需要记录跨代引用指针的全部细节，只需要通过记忆集判断出某一块非收集区域是否存在有指向了收集区域的指针即可

在实现记忆集的时候，便可以选择更为粗旷的记录粒度来节省记忆集的存储和维护成本，下面给出一些可选择的记录精度：

字长精度：每个记录精确到一个机器字长，该字包含跨代指针
对象精度：每个记录精确到一个对象，该对象里有字段含有跨代指针
卡精度：每个记录精确到一块内存区域，该区域内有对象含有跨代指针

这里重点讲一讲第三种，也就是卡精度，它指的是用一种称为「卡表 (Card Table)」的方式去实现记忆集，也是目前最常用的一种记忆集的实现形式

由于卡表是目前最常用的实现形式，导致很多人将记忆集和卡表混为一谈，甚至认为它们俩是等价的，其实不然！！

记忆集只是一种抽象的数据结构，只定义了记忆集的行为意图，并没有定义其行为的具体实现；而卡表就是记忆集的一种具体实现，它定义了记忆集的记录精度、与堆内存的映射关系等

更形象一点，记忆集和卡表的关系类似于接口和实现类的关系，如：HashMap和Map的关系

卡表底层的数据结构可以简单到是一个字节数组，HotSpot 虚拟机也是这样实现的：


xxxxxxxxxx
CARD_TABLE [this address >> 9] = 1;

字节数组CARD_TABLE中每一个元素都对应着内存区域中一块特定大小的内存块，这个内存块被称为卡页 (Card Page)

$2^9$ ，也就是 512 字节

这里举个例子，假设内存地址的范围为 0 ~ 10，N = 2，那么就有：

内存地址 0, 1, 2, 3 对应CARD_TABLE中的第 0 个元素，因为它们右移 2 位后结果都为 0；换句话说内存地位为 0 ~ 3 的是一个卡页内存块
内存地址 4, 5, 6, 7 对应CARD_TABLE中的第 1 个元素，因为它们右移 2 位后结果都为 1；换句话说内存地位为 4 ~ 7 的是一个卡页内存块
内存地址 8, 9, 10 对应CARD_TABLE中的第 2 个元素，因为它们右移 2 位后结果都为 2；换句话说内存地位为 8 ~ 10 的是一个卡页内存块

回到 N = 9 的情况，如果卡表标识内存区域的起始地址是0x0000那么数组CARD_TABLE的第 0，1，2 个元素分别对应地址范围为0x0000 ~ 0x01FF，0x0200 ~ 0x03FF，0x0400 ~ 0x04FF的卡页内存块，如下图所示：

一个卡页的内存中通常包含不止一个对象，只要卡表页卡有一个 (或更多) 对象的字段存在着跨代指针，那就将对应卡表的数组元素的值标识为 1，称为这个元素变脏 (Dirty)，没有则标识为 0

在垃圾收集发生时，只要筛选出卡表中变脏的元素 (内存区域块)，就能轻易得出哪些卡页内存块中包含跨代指针，把它们加入 GC Roots 中一并扫描

写屏障

「OopMap + 安全点 + 安全区域」让 HotSpot 虚拟机可以在可控的空间成本下快速准确的完成 GC Roots 枚举；「记忆集」解决了存在跨代引用时缩减 GC Roots 扫描范围的问题

但我们还没有解决卡表元素如何维护的问题，即在对象改变引用关系时需要维护卡表的正确性，例如：何时变脏？谁把它们变脏？

卡表元素何时变脏：有其它分代区域中对象引用了本区域对象时，那么其它分代区域对应的卡表元素就应该变脏，变脏时间点原则上应该发生在引用类型字段赋值的那一刻

现在的问题在于如何变脏，也就是确定了某一时刻某一个区域变脏了，那如何把它记录成脏的状态呢？换句话说如何在对象赋值的那一刻去更新维护卡表呢？

如果是解释执行的场景，虚拟机负责每条字节码指令的执行，有充分的介入空间；如果是编译执行的场景，经过即时编译后的代码已经是纯粹的机器指令流，这就必须找到一个在机器码层面的手段，把维护卡表的动作放到每一个赋值操作之中

在 HotSpot 虚拟机里面是通过写屏障 (Write Barrier) 技术维护卡表状态的！！注意将此处的「写屏障」和低延迟收集器中的「读屏障」以及解决并发乱序执行问题中的「内存屏障」区分开来

写屏障可以看作在虚拟机层面对「引用类型字段赋值」这个动作的 AOP 切面，在引用对象赋值时会产生一个环形通知，以供程序执行额外的动作

环形通知是指赋值前后都在写屏障的覆盖范围内，在赋值前的部分的写屏障叫作写前屏障；在赋值后的部分的写屏障叫作写后屏障。HotSpot 虚拟机的许多收集器中都有使用到写屏障，但在 G1 收集器出现之前，其它收集器都只用到写后屏障

下面是一段更新卡表状态的简化逻辑：


xxxxxxxxxx
void oop_field_store(oop* field, oop new_value) {
    // 引用字段赋值操作
    *field = new_value;
    // 写后屏障，在这里完成卡表状态更新
    post_write_barrier(field, new_value);
}

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

除了写屏障的开销外，卡表在高并发场景下还面临着「伪共享 (False Sharing)」问题：现在中央处理器的缓存系统中是以缓存行为单位存储的，当多线程修改互相独立的变量时，如果这些变量恰好共享一个缓存行，就会彼此影响 (写回、无效化或者同步) 而导致性能降低。关于伪共享更详细的总结可见伪共享

假设处理器缓存行大小为 64 字节，由于一个卡表元素占 1 个字节，64 个卡表元素将共享同一个缓存行。这 64 个卡表元素对应的卡页总的内存为 32KB (64 x 512 字节)，也就是说如果不同线程更新的对象正好处于这 32KB 的内存区域中，就会导致更新卡表时正好写入同一个缓存行而影响性能

为了避免伪共享问题，一种简单的解决方案是不采用无条件的写屏障，而是先检查卡表标记，只有当卡表元素未标记过时才将其标记为变脏，修改后的卡表更新的逻辑如下面代码所示：


xxxxxxxxxx
if (CARD_TABLE [this address >> 9] != 1)
    CARD_TABLE [this address >> 9] = 1;

这就避免了无效更新导致缓存行失效的概率，从而提高了系统的性能。在 JDK7 之后，HotSpot 虚拟机增加了一个新的参数-XX:+UseCondCardMark，用来解决是否开启卡表更新的条件判断。开启后会增加一次额外判断的开销，但能够避免伪共享问题，两者各有性能损耗，是否打开需要根据应用实际运行情况来进行测试权衡

并发的可达性分析

可达性分析算法理论上要求全过程都基于一个能保障一致性的快照中才能够进行分析，这意味着必须全部冻结用户线程的运行

在 根节点枚举 步骤中，由于 GC Roots 相比起整个 Java 堆中全部的对象毕竟还算是极少数，且在各种优化技巧 (如：OopMap) 的加持下，它带来的停顿已经是非常短暂且相对固定 (不随堆容量而增长)

但是从 GC Roots 再继续往下遍历对象图，这一步骤的停顿时间就必定会与 Java 堆容量直接成正比例关系了：堆越大，存储的对象越多，对象图结构越复杂，要标记更多对象而产生的停顿时间自然就更长

要解决或者降低用户线程的停顿，就要先搞清楚为什么必须在一个能保障一致性的快照上才能进行对象图的遍历？这了能解释清楚这个问题，引入三色标记作为工具来辅助推导：

白色：表示对象尚未被垃圾收集器访问过。显然在可达性分析刚刚开始的阶段，所有的对象都是白色的，若在分析结束的阶段，仍然是白色的对象，即代表不可达
黑色：表示对象已经被垃圾收集器访问过，且这个对象的所有引用都已经扫描过。黑色的对象代表以及扫描过，它是安全存活的，如果有其它对象引用指向了黑色对象，无须重新扫描一遍。黑色对象不可能直接 (不经过灰色对象) 指向某个白色对象
灰色：表示对象已经被垃圾收集器访问过，但这个对象至少存在一个引用还没有被扫描过

关于可达性分析的扫描过程，可以想象成一股以灰色为波峰的波纹从黑向白推进的过程，如果用户线程此时是冻结的，只有 GC 线程在工作，那肯定不会有任何问题

但如果用户线程和 GC 线程是并发工作的呢？垃圾收集器在对象图上标记颜色，同时用户线程在修改引用关系 (即：修改对象图的结构)，这样可能会出现两种后果：

把原本消亡的对象错误的标记为存活，但这种情况可以容忍，只不过产生了一点逃过本次收集的浮动垃圾而已，下次收集清理掉就好
把原本存活的对象错误的标记为死亡，这种情况是致命的！！

下面展示了扫描过程中的三种状态：

初始状态：只有 GC Roots 是黑色的，箭头表示引用，它是有向的，对象只有被黑色对象引用才能存活

扫描过程中：以灰色为波峰的波纹从黑向白推进，灰色对象是黑、白对象的分界线

扫描完成：此时黑色对象就是存活的对象，白色对象就是已经消亡可回收的对象

注意：黑色对象表示已经扫描过的对象，不会再次被扫描；灰色对象表示当前正在被扫描的对象

下面来介绍上面提到过在并发情况下的两种错误情况，先来第一种：把原本消亡的对象错误的标记为存活

假设当前正在扫描灰色对象，然后某个用户线程将一个黑色对象的引用删除了，由于黑色对象不会再次被扫描，所以将导致本应该消亡的两个对象被标记为存活，侥幸躲过了这次回收，如下图所示：

第一种错误情况问题不大，下次清理掉就好，下面来介绍致命性的第二种情况：把原本存活的对象错误的标记为死亡

假设当前正在扫描灰色对象，然后某个用户线程删除了一个该灰色对象的引用，同时添加了一个黑色对象的引用，由于黑色对象不会再次被扫描，所以将导致本应该存活的对象被标记为死亡，如下图所示：

对于第一种错误情况，强调过多次问题不大，所以可以不用处理它，我们的重心在第二种致命的错误情况，它的出现当且仅当同时满足以下两个条件：

赋值器插入了一条或多条从黑色对象到白色对象的新引用，如上图的步骤 2
赋值器删除了全部从灰色对象到该白色对象 (该白色对象指条件一中插入新引用所指向的白色对象) 的直接或间接引用，如上图的步骤 1，图的左边删除了直接引用，图的右边删除了间接引用

既然上面的两个条件必须同时满足才会出现致命性错误，那只需要破坏任意一个条件即可避免致命性错误的出现，所以产生了两种解决方案：增量更新 (Incremental Update) 和 原始快照 (SATB)

增量更新破坏的是第一个条件，由于黑色对象是已经被扫描过且不会再次被扫描的对象，只需要将这个新插入的引用记录下来，等并发扫描结束后，再以这些记录过的引用关系中的黑色对象为根，重新扫描一遍！

原始快照破坏的是第二个条件，只需要将这个要删除的引用记录下来，等并发扫描结束后，再以这些记录过的引用关系中的灰色对象为根，重新扫描一遍！即无论删除与否，都会按照原始对象图进行搜索

设想一种情况，假设使用原始快照的方案，但只满足第二个条件，这时就会出现把本应该消亡的对象标记为存活的情况，不过这问题不大，上面强调过

以上无论对引用关系记录的插入还是删除，虚拟机的记录操作都是通过 写屏障 实现的。在 HotSpot 虚拟机中，增量更新和原始快照这两种解决方案都有实际应用，如：CMS 使用的是增量更新；G1 使用的的是原始快照

写在后面

👇👇👇👇👇👇👇👇👇👇👇👇