HotSpot GC 算法细节

1 根节点枚举

虽然固定的 GC Roots 节点在全局性的引用(如常量或类静态属性)与执行上下文(如栈帧中的本地变量表)中目标明确,但查找过程要做到高效并非一件容易的事情。随着 Java 应用规模的不断扩大,方法区的大小通常就有几百上千兆,里面的类、常量等更是极多,如果要逐个检查以这里为起点的引用,肯定需要消耗大量时间。

迄今为止,所有的垃圾收集器在根节点枚举这一步骤都必须暂停用户线程,因此也需要面临“Stop The World”的困扰。尽管可达性分析算法耗时最长的查找引用链的过程已经可以做到与用户线程一起并发,但根节点枚举仍需要在保证一致性的快照中进行,否则在枚举过程中如果有变化,分析出来的结果的准确性也就无法保证。这是导致垃圾收集过程必须停顿所有用户线程的其中一个重要原因,即使是号称停顿时间可控或几乎不会发生停顿的 Shenandoah、ZGC 等收集器,枚举根节点时也必须停顿。

由于目前主流的 Java 虚拟机使用的是准确式垃圾收集,所以当用户线程停顿下来时,并不需要完全检查所有执行上下文和全局引用位置,虚拟机可以直接获取存放对象引用的位置。

注释
  • 准确式垃圾收集 (Precise Garbage Collection) 是一种垃圾回收算法,它可以精确地找出程序中哪些对象是垃圾,以便将其回收。在这种算法中,垃圾收集器必须遍历整个堆内存,标记所有存活的对象,并回收未被标记的对象。
    • 准确式垃圾收集通常采用的是"标记-清除"、“标记-复制”、“标记-整理"等算法,其核心是在垃圾回收过程中 进行可达性分析,即标记程序中所有仍在使用的对象,将其保留下来,而未被标记的对象则被认为是垃圾并被回收。
    • 准确式垃圾收集通常需要在垃圾回收期间暂停程序执行,以便进行全局的可达性分析。但现代的垃圾回收器已经可以做到分代、增量、并发、并行等技术手段,以尽量减少垃圾回收期间的停顿时间,提高应用程序的响应性和吞吐量。
  • 非准确式垃圾收集 (Non-precise Garbage Collection) 相对于准确式垃圾收集,它不需要精确地确定哪些对象是可达的,而是通过某种简化的方式来判断哪些对象可能是垃圾,从而进行回收。这种算法的主要优点是速度快,但代价是回收可能不够精确,可能会回收一些仍然被引用的对象,或者一些垃圾对象被误判为存活对象而未被回收。

HotSpot 使用一组名为 OopMap 的数据结构来达到这个目的:一旦类加载动作完成,HotSpot 就会计算对象内部的偏移量,以及这些偏移量上是什么类型的数据。在即时编译过程中,HotSpot 也会在特定的位置记录下栈里和寄存器里哪些位置是引用。这样,在垃圾收集器扫描时,就可以直接得知这些信息,而不需要真正一个不漏地从方法区等 GC Roots 开始查找。

下面代码是 HotSpot 虚拟机客户端模式下生成的一段 String::hashCode() 方法的汇编代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
[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

可以看到,在 0x026eb7a9 处的 call 指令有一个 OopMap 记录,其中记录了 EBX 寄存器和栈中偏移量为 16 的内存区域中各有一个普通对象指针 (Ordinary Object Pointer,OOP) 的引用,有效范围为从调用指令开始直到 0x026eb730(指令流的起始位置)加上 142(OopMap 记录的偏移量)= 0x026eb7be,也就是 hlt 指令为止的范围。

2 安全点

OopMap 的协助下,HotSpot 可以快速准确地完成 GC Roots 枚举,但由于可能导致引用关系变化的指令非常多,为每一条指令都生成对应的 OopMap 将会消耗大量的额外存储空间。实际上,HotSpot 只在特定的位置记录了这些信息,这些位置被称为安全点 (Safepoint)。在这些位置上,所有线程都需要到达一个安全点并停顿下来,才能进行垃圾收集相关的操作。这样做可以保证 OopMap 内容的正确性,并避免由于指令执行导致引用关系变化而造成的不一致性问题。

安全点机制要求用户程序必须执行到安全点后才能开始垃圾收集。因此,安全点的选定既不能太少以至于让收集器等待时间过长,也不能太过频繁以至于过分增大收集器运行时的内存负荷。安全点位置的选取基本上是以 “是否具有让程序长时间执行的特征” 为标准进行选定的,因为每条指令执行的时间都非常短暂,程序不太可能因为指令流长度太长而长时间执行。具有让程序长时间执行的特征包括方法调用、循环跳转、异常跳转等,这些指令的执行过程可能涉及到大量的内存访问和数据处理,因此是产生安全点的主要来源。

对于安全点,还有一个需要考虑的问题,就是在垃圾收集发生时,如何让所有线程(不包括执行 JNI 调用的线程)都跑到最近的安全点,然后停顿下来。这里有两种方案可供选择:抢先式中断 (Preemptive Suspension)主动式中断 (Voluntary Suspension)

  • 抢先式中断不需要线程的执行代码主动配合,在垃圾收集发生时,系统首先中断所有用户线程。如果发现有线程被中断时不在安全点上,就恢复这条线程的执行,让它稍后再重新中断,直到到达安全点为止。现在几乎没有虚拟机采用抢先式中断。
  • 主动式中断指的是当垃圾收集需要中断线程时,不直接对线程进行操作,而是简单地设置一个标志位。各个线程执行过程中会不断地主动轮询这个标志,一旦发现中断标志为 true,则会在最近的安全点上主动挂起。轮询标志的地方和安全点是重合的,同时还需要在所有创建对象和需要在 Java 堆上分配内存的地方检查是否即将发生垃圾收集,以避免没有足够的内存分配新对象。

由于轮询操作在代码中会频繁出现,这要求它必须足够高效。HotSpot 使用内存保护陷阱的方式,把轮询操作精简至只有一条汇编指令的程度。下面的 test 指令就是 HotSpot 生成的轮询指令:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

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

3 安全区域

安全点机制保证了程序执行时,在不太长的时间内就会遇到可进入垃圾收集过程的安全点,但对于那些没有被分配时间片而处于休眠或阻塞状态的线程,安全点机制则无能为力。这些线程无法响应中断请求,也不能走到安全点挂起自己,而虚拟机也不能一直等待线程获得时间片。为了解决这种情况,我们必须引入安全区域(Safe Region)。

安全区域可以看作是代码中的一个片段,该片段能够保证在其中引用关系不会发生变化,因此在这个区域中的任意位置开始垃圾收集都是安全的。可以将安全区域视为安全点的扩展。

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

在实际应用中,安全区域往往被用于一些需要使用底层资源(如文件系统、网络连接等)的代码块,这些代码块的执行通常比较耗时,也容易导致线程无法及时响应中断请求。

4 记忆集和卡表

记忆集是为了解决跨代引用的问题而设计的。在垃圾收集器对新生代进行垃圾回收时,为了避免扫描整个老年代,垃圾收集器会在新生代中建立记忆集数据结构,记录所有跨越新生代和老年代的引用。

Note
事实上并不只有新生代、老年代间才存在跨代引用的问题,所有涉及部分区域收集 (Partial GC) 行为的垃圾收集器,典型的如 G1、ZGC 和 Shenandoah 收集器,都会面临相同的问题。

如果我们不考虑效率和成本的话,最简单的实现可以用非收集区域中所有含跨代引用的对象数组来实现这个数据结构,伪代码如下:

1
2
3
Class RememberedSet {
    Object[] set[OBJECT_INTERGENERATIONAL_REFERENCE_SIZE];
}

在垃圾收集的场景中,收集器只需要通过记忆集判断某一块非收集区域中的某个对象是否存在指向收集区域的引用,而不需要了解这些跨代引用的全部细节。因此,在实现记忆集时,设计者可以选择更粗糙的记录粒度来减少存储和维护成本。

下面列举了一些可供选择的记录精度:

  • 字长精度:每个记录精确到一个机器字长(就是处理器的寻址位数,如常见的 32 位或 64 位,这个精度决定了机器访问物理内存地址的指针长度),该字包含跨代指针。
  • 对象精度:每个记录精确到一个对象,该对象里有字段含有跨代指针。
  • 卡精度:每个记录精确到一块内存区域,该区域内有对象含有跨代指针。

其中,第三种“卡精度”所指的是用一种称为 “卡表” (Card Table) 的方式去实现记忆集,这也是目前最常用的一种记忆集实现形式。

4.1 卡表

卡表 (Card Table) 是一种在分代垃圾收集器中使用的一种记忆集实现,用于记录跨代指针和非收集区域之间的引用关系,以提高跨代垃圾收集的效率。

HotSpot 虚拟机中的卡表就是一个字节数组。以下代码是 HotSpot 默认的卡表标记逻辑:

1
CARD_TABLE [this address >> 9] = 0;
  • CARD_TABLE 中的每一个元素都对应着其标识的内存区域中的一块特定大小的内存块,这个内存块被称作 “卡页” (Card Page)。一般来说,卡页大小都是以 2 的 N 次幂的字节数,通过上面代码可以看出 HotSpot 中使用的卡页是 2 的 9 次幂,即 512 字节。
  • 如果卡表标识内存区域的起始地址是 0x0000 的话,数组 CARD_TABLE 的第 0、1、2 号元素,分别对应了地址范围为 0x0000~0x01FF0x0200~0x03FF0x0400~0x05FF 的卡页内存块。

在卡表中,一个卡页通常包含不止一个对象,只要卡页内有一个或多个对象的字段存在着跨代指针,那么对应卡表的数组元素的值就会被设为 1,被称为这个元素变脏 (Dirty),否则就标识为 0。在垃圾收集发生时,只需筛选出卡表中变脏的元素,就能轻松确定哪些卡页内存块中包含跨代指针,将其加入 GC Roots 中,一并扫描即可。

卡表的实现通常需要使用硬件的特性来提高扫描的效率,例如 x86 架构的处理器支持 PCD (Page-Level Cache Disable) 和 PWT (Page-Level Write Through) 特性,可以避免卡表中标记为 dirty 的卡片被缓存在处理器的 L1 缓存中,从而减少扫描的开销。

5 写屏障

写屏障 (Write Barrier) 是一种与并发垃圾收集密切相关的技术。它是垃圾收集器在进行并发标记阶段,通过记录对象引用关系变化的技术,保证在并发标记期间不会遗漏任何存活对象。

在 Java 虚拟机的垃圾收集器中,有两种写屏障技术:基于插桩的写屏障和基于编译器的写屏障。

  • 基于插桩的写屏障就是在程序运行过程中,为每个对象插入一个钩子 (Hook),当程序执行修改对象引用的指令时,钩子就会被触发,记录下这次引用的变化。
  • 基于编译器的写屏障则是在编译器对程序进行优化的过程中,为对象引用的修改点插入钩子。这种方式可以减少在程序运行时对修改点的遍历,提高垃圾收集器的执行效率。

写屏障是垃圾收集器实现并发标记的关键技术之一,可以确保垃圾收集器在进行并发标记时不会错过任何存活对象,同时也能减少并发标记过程中的内存占用,提高垃圾收集器的效率。

6 并发的可达性分析

当前主流编程语言的垃圾收集器基本上都是依靠可达性分析算法来判定对象是否存活的。可达性分析算法理论上要求全过程都基于一个能保障一致性的快照来分析,这意味着必须全程冻结用户线程的运行。在根节点枚举过程中,由于 GC Roots 数量少而且有各种优化技巧(如 OopMap)加持,它带来的停顿已经非常短暂且相对固定(不随堆容量而增长)了。但是,从 GC Roots 再继续往下遍历对象图的过程不可避免地与 Java 堆的容量呈正相关:堆越大,存储的对象越多,对象图结构越复杂,停顿时间就越长。标记阶段是所有追踪式垃圾收集算法的共同特征,如果这个阶段会随着堆变大而等比例增加停顿时间,其影响就会波及几乎所有的垃圾收集器。如果能够削减这部分停顿的时间,将会获得系统性的好处。

6.1 为什么标记过程依赖一致性快照?

JVM 的并发标记过程依赖一致性快照,是因为在并发标记的过程中,应用程序线程可能会修改对象图的引用关系,而这些修改可能会导致对象在垃圾收集器的标记过程中被漏掉或者被重复标记,从而导致垃圾收集的不准确。因此,为了保证垃圾收集的准确性,需要在标记过程中使用一致性快照来冻结对象图,以保证对象图的引用关系不会在标记过程中发生变化。

如果没有一致性快照,而且用户线程修改引用关系与收集器标记过程同时进行,就会导致以下两个问题:

  • 一是把原本消亡的对象错误标记为存活。这种还算可以忍受,只不过产生了一点逃过本次收集的浮动垃圾而已,下次收集清理掉就好。
  • 另一种是把原本存活的对象错误标记为已消亡。这就是非常致命的后果了,会导致程序运行错误。

下面我们通过三色标记 (Tri-color Marking) 工具来演示这样的致命错误具体是如何产生的:

三色标记工具

把遍历对象图过程中遇到的对象,按照“是否访问过”这个条件标记成以下三种颜色:

  • 白色:表示对象尚未被垃圾收集器访问过。

    显然在可达性分析刚刚开始的阶段,所有的对象都是白色的,若在分析结束的阶段,仍然是白色的对象,即代表不可达。

  • 黑色:表示对象已经被垃圾收集器访问过,且这个对象的所有引用都已经扫描过。

    黑色的对象代表已经扫描过,它是安全存活的,如果有其他对象引用指向了黑色对象,无须重新扫描一遍。黑色对象不可能直接(不经过灰色对象)指向某个白色对象。

  • 灰色:表示对象已经被垃圾收集器访问过,但这个对象上至少存在一个引用还没有被扫描过。
三色标记工具演示

6.2 如何解决并发扫描时对象消失的问题?

Wilson 于 1994 年在理论上证明了,当且仅当以下两个条件同时满足时,会产生“对象消失”的问题(即原本应该是黑色的对象被误标为白色):

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

因此,要解决并发扫描时的对象消失问题,只需破坏这两个条件的任意一个即可。由此分别产生了两种解决方案:

  • 增量更新 (Incremental Update)

    增量更新要破坏的是第一个条件:当黑色对象插入新的指向白色对象的引用关系时,就将这个新插入的引用记录下来。等并发扫描结束后,将这些记录过的引用关系中的黑色对象作为根,重新扫描一次。简单来说,黑色对象一旦插入指向白色对象的引用,就会重新变为灰色对象。

  • 原始快照 (Snapshot At The Beginning, SATB)

    原始快照要破坏的是第二个条件:当灰色对象要删除指向白色对象的引用关系时,就将这个要删除的引用记录下来,在并发扫描结束之后,再将这些记录过的引用关系中的灰色对象为根,重新扫描一次。这也可以简化理解为,无论引用关系删除与否,重新扫描时都会使用开始扫描那一刻的对象图快照。

以上无论是对引用关系记录的插入还是删除,虚拟机的记录操作都是通过写屏障实现的。在 HotSpot 虚拟机中,增量更新和原始快照这两种解决方案都有实际应用。比如 CMS 是基于增量更新来做并发标记的,G1、Shenandoah 则是用原始快照来实现的。


欢迎关注我的公众号,第一时间获取文章更新:

微信公众号

相关内容