G1垃圾回收器深入探索——卡表、记忆集和SATB算法
G1垃圾回收器深入探索——卡表、记忆集和SATB算法
G1垃圾回收器是Java虚拟机中一个重要的组件，它通过将堆内存划分为多个区域（Region）来实现高效的垃圾回收。本文将深入探讨G1垃圾回收器中的三个核心组成部分：卡表（Card Table）、记忆集（Remembered Set）和SATB算法。
Card Table（卡表）
在进行YoungGC时，需要判断一个对象是否被引用。但是扫描整个Old区是一个非常耗时的操作。因此，JVM设计了CardTable，将Old区分为一个一个Card，一个Card包含多个对象。如果一个Card中的对象有引用指向Young区，则将其标记为Dirty Card。下次进行YoungGC时，只需要扫描这些Dirty Card即可。
Remembered Set（记忆集）
在GC的时候，对于old->young和old->old的跨代对象引用，不需要扫描整个堆找到谁引用了当前分区中的对象，只要扫描对应的CSet中的RSet即可。逻辑上说每个Region都有一个RSet，RSet记录了其他Region中的对象引用本Region中对象的关系，属于points-into结构（谁引用了我的对象）。
Card Table则是一种points-out（我引用了谁的对象）的结构，每个Card 覆盖一定范围的Heap（一般为512Bytes）。G1的RSet是在Card Table的基础上实现的：每个Region会记录下别的Region有指向自己的指针，并标记这些指针分别在哪些Card的范围内。这个RSet其实是一个Hash Table，Key是别的Region的起始地址，Value是一个集合，里面的元素是Card Table的Index集合。每个Region中都有一个RSet，记录其他Region到本Region的引用信息；使得垃圾回收器不需要扫描整个堆找到谁引用当前分区中的对象，只需要扫描RSet即可。而维系RSet中的引用关系靠post-write barrier和Concurrent refinement threads来维护。
记忆集结构：
卡表和记忆集的协作
这两个结构在年轻代的回收时候发生着主要作用。具体怎么执行的呢？核心就是我们的写屏障！
我们在一个指令前后加上屏障，更新卡表，卡表在合适的时候更新记忆集，然后我们的回收器直接去记忆集里拿数据就OK啦。
混合回收阶段的SATB算法
SATB算法的核心是三色标记法，不懂的可以跳转我的另外一篇文章，看看黑灰白三色标记法的具体原理。这里我只做简单的介绍。
三色标记法即将所有对象分为三种颜色：
- 白色：没有检查
- 灰色：自身被检查了，成员没被检查完（可以认为访问到了，但是正在被检查，就是图的遍历里那些在队列中的节点）
- 黑色：自身和成员都被检查完了
SATB算法的基本思想：
- 并发标记之前先给Region内存打个快照，标记线程基于这个快照独立进行标记。应用线程不会直接修改这个快照中的对象，也就是说应用线程不会干扰标记线程的工作。
- 应用线程新分配的对象都认为是活跃对象，实际在下一个并发标记周期进行标记。
- 并发标记过程中已存在对象的引用关系变更在Remark阶段单独进行处理。在并发标记阶段如果有引用关系被删除，就记录下来，Remark阶段对这些引用关系被删除的重标记，这个破坏了步骤一，即灰色对象断开了白色对象引用的时候，记录下来，后面重新把这个白色对象标记成存活对象。
我们结合图来看看：
我们把中间发生变动的放到SATB队列里，然后合并继续标记，所有SATB里面的对象直接默认存活。