https://www.bilibili.com/video/BV1fi4y1U76z?p=21&vd_source=c5b2d0d7bc377c0c35dbc251d95cf204

https://abcgao.com/archives/%E4%B8%89%E8%89%B2%E6%A0%87%E8%AE%B0%E6%B3%95

1. 概念定位

垃圾回收算法主要有有两种，可达性分析算法(追踪式垃圾回收算法) 和 引用计数法（ Reference counting ）。**三色标记法与复制、标清、标整一样，也属于追踪式垃圾回收算法**。三色标记法用来帮助完成并发场景下的垃圾标记判断工作。如果不需要并发能力，则没必要使用三色标记算法。三色标记算法解决了标记清除算法不能并发执行的问题

标记 - 整理算法是并行垃圾回收算法，主打高吞吐，不涉及并发。而标记 - 清除算法追求低延迟，所以有并发需求。所以要引入三色标记法来完成并发的目标。CMS 和 G1 都引入了三色标记法。

追踪式算法的核心思想是判断一个对象是否可触达，因为一旦对象不可触达就应该被 GC 回收了。那么如何得知一个对象是否可达呢？具体如下：

找出所有的全局变量和当前函数栈里的变量，标记为可达。
从已标记的数据开始，进一步标记它们可访问的变量，以此类推，也就是我们经常提到的 传递闭包。

标记法中有个算法叫 Mark-And-Sweep （标记清除），该算法是严格按照追踪式算法的思路实现的。首先为所有对象标记为 0，如果发现对象是可达的就会置为 1，一步步下去就会呈现一个类似树状的结果。待标记的步骤完成后，会将未被标记的对象统一清理，再次把所有的标记位设置成 0 方便下次清理。

这个算法最大的问题是 GC 执行期间需要把整个程序完全暂停，不能异步进行 GC 操作。因为在不同阶段标记清扫法的标志位 0 和 1 有不同的含义，那么新增的对象无论标记为什么都有可能意外删除这个对象。对实时性要求高的系统来说，这种需要长时间挂起的标记清扫法是不可接受的。所以就需要一个算法来解决 GC 运行时程序长时间挂起的问题。

2. 标记过程

三色标记法就是为了解决这个问题而出现的。它将对象标记为黑、白、灰三种颜色，黑色对象为可达对象，应该保留，白色对象为不可达对象，应该被清除，灰色作为中间过度态。如下图：
❕ ^44bdy0

三色标记图.gif

假设现在有白、灰、黑三个集合（表示当前对象的颜色），其遍历访问过程为：

初始时，所有对象都在【白色集合】中；
将 GC Roots 直接引用到的对象挪到【灰色集合】中；
从灰色集合中获取对象：
3.1. 将本对象直接引用到的其他对象全部挪到【灰色集合】中；
3.2. 将本对象挪到【黑色集合】里面。
重复步骤 3，直至【灰色集合】为空时结束。
结束后，仍在【白色集合】的对象即为 GC Roots 不可达，可以进行回收。

3. 优点特性

因为三色标记法多了一个白色的状态来存放不确定的对象，所以可以异步地执行。

当然异步执行的代价是可能会造成一些遗漏，因为那些早先被标记为黑色的对象可能目前已经是不可达的了。所以三色标记法是一个 false negative（假阴性）的算法。

除了异步标记的优点，三色标记法掌握了更多当前内存的信息，因此可以更加精确地按需调度，而不用像标记清扫法那样只能定时执行。

4. 存在问题

当 Stop The World （以下简称 STW）时，对象间的引用是不会发生变化的，可以轻松完成标记。
而当需要支持并发标记时，即标记期间应用线程还在继续跑，对象间的引用可能发生变化，多标和漏标的情况就有可能发生。

4.1. 浮动垃圾 (多标)

本来应该为白色是要回收的，而误标了颜色，使其本次 GC 阶段无法回收，即为多标。❕ ^ctng6t
浮动垃圾 (多标)：将原本应该被清除的对象，误标记为存活对象。后果是垃圾回收不彻底，不过影响不大，可以在下个周期被回收；

产生原因在于 GC 线程和应用线程的并发执行，比如 GC 线程先遍历到 E（已经变为灰色了），接下来应用执行了 objD.fieldE = null 又导致 D -> E 的引用断开
黑删灰
此刻之后，对象 E/F/G 是“应该”被回收的。然而因为 E 已经变为灰色了，其仍会被当作存活对象继续遍历下去。最终的结果是：这部分对象仍会被标记为存活，即本轮 GC 不会回收这部分内存。

浮动垃圾 -2 种来源 ^u9321a

这部分本应该回收但是没有回收到的内存，类似黑删灰的情况，被称之为“浮动垃圾”。浮动垃圾并不会影响应用程序的正确性，只是需要等到下一轮垃圾回收中才被清除。
另外，针对并发标记开始后的新对象，通常的做法是直接全部当成黑色，本轮不会进行清除。这部分对象期间可能会变为垃圾，这也算是浮动垃圾的一部分。

4.2. 对象消失 (漏标)

对象消失 (漏标)：将原本应该存活的对象，最终没有被标记为黑色，还是初始的白色，而被回收了。后果很严重，影响程序运行，是不可容忍的。

假设 GC 线程已经遍历到 E（变为灰色了），此时应用线程先执行了：

// Step1 读操作；对象E的成员变量fieldG的引用值，即对象G
var G = objE.fieldG; 
// Step2 写操作；灰色E 断开引用 白色G
objE.fieldG = null;
// Step3 写操作；黑色D 引用 白色G
objD.fieldG = G;

E -> G 断开，D 引用 G

此时切回 GC 线程继续跑，因为 E 已经没有对 G 的引用了，所以不会将 G 放到灰色集合；尽管因为 D 重新引用了 G，但因为 D 已经是黑色了，不会再重新做遍历处理。
最终导致的结果是：G 会一直停留在白色集合中，最后被当作垃圾进行清除。这直接影响到了应用程序的正确性，是不可接受的。

4.3. 漏标解决方案

❕ ^kkx1uo

漏标必须要同时满足以下两个条件：黑增灰删

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

这两个条件必须全部满足，才会出现对象消失的问题。那么我们只需要对上面条件进行破坏，破坏其中的任意一个，都可以防止对象消失问题的产生。这样就产生了两种解决方案：

增量更新：Incremental Update
原始快照：Snapshot At The Beginning(SATB)

增量更新破坏的是第一个条件，当黑色对象插入新的指向白色对象的引用时，就将这个新加入的引用记录下来，待并发标记完成后，重新对这种新增的引用记录进行扫描；
原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将白色对象的引用记录下来，待并发标记完成后，对该记录进行重新扫描。

HotSpot 虚拟机中，不管是新增还是删除，这种记录的操作都是通过写屏障实现的。我们可以将写屏障理解为 JVM 对引用修改操作的一层 AOP，注意它与内存屏障是两个不同的东西。

对于读写屏障，以 Java HotSpot VM 为例，其并发标记时对漏标的处理方案如下：
CMS：写屏障 + 增量更新
G1：写屏障 + SATB（原始快照）
ZGC：读屏障

4.3.1. 增量更新

增量更新破坏的是第一个条件，在新增一条引用时，将该记录保存。实际的实现中，通常是将引用相关的节点进行重新标记。考虑下图中的例子：

A、B、C 分别为黑、灰、白，起初 A→B、B→C，后来新增 A→C，而 B→C 断开
增量更新的方案是：将 A→C 这条新增的引用关系中 C 的引用保存起来，在并发扫描完成后，重新对这种新增的引用记录进行扫描。

上面就是一次引用关系修改导致的对象消失问题。增量更新进行的处理，就是将由 A 到 C 的这条新增的引用关系进行保存。首先看下 Dijkstra 等人提出的方式：

write_barrier(obj, field, newobj) {
    if (newobj.mark == FALSE) {
        newobj.mark = TRUE;
        push(newobj, $mark_stack);
    }
    *field = newobj;
}

如果新引用的对象 newobj 没有被标记，那么就将其标记后堆到标记栈里。换句话说，如果 newobj 是白色对象，就把它涂成灰色。这样操作后的结果如下图所示：

此时 C 被涂成了灰色，它将在后续被重新扫描，阻止了对象消失。

Steele 提出了一种更严厉的方法，它相比 Dijkstra 的方法，可以减少错误标记的对象数量。就是直接把 A 涂成灰色，从根上再捋一遍

write_barrier(obj, field, newobj) {
    if($gc_phase == GC_MARK && obj.mark == TRUE && newobj.mark == FALSE) {
        obj.mark = FALSE;
        push(obj, $mark_stack);
    }
    *field = newobj;
}

如果在标记过程中发出引用的对象是黑色对象，且新的引用的目标对象为灰色或白色，那么我们就把发出引用的对象涂成灰色。这样操作后的结果如下图：

此时 A 由原来的黑色变成了灰色，将在后续被重新扫描。

4.3.2. 原始快照

原始快照破坏的是第二个条件，当灰色对象要删除指向白色对象的引用关系时，就将这个要删除的引用记录下来，并发扫描结束后，在将这些记录重新扫描一次。

write_barrier(obj, field, newobj) {
    oldobj = *field;
    if(gc_phase == GC_MARK && oldobj.mark == FALSE) {
        oldobj.mark = TRUE;
        push(oldobj, $mark_stack);
    }
    *field = newobj;
}

当 GC 进入到标记阶段且 oldobj 没被标记时，则标记 oldobj，并将其记录。也就是说，在标记阶段中如果指针更新前引用的 oldobj 是白色对象，就将其涂成灰色。

上图依旧是对象消失的例子。a 到 b 中，产生了一条由 A 到 C 的引用关系，这里并没有像增量更新那样将 A 或者 C 标为灰色，相反原始快照中允许出现从黑色指向白色的引用。而在从 b 到 c 中，删除了由 B 到 C 的引用关系。这时候就需要进行处理，将 C 涂为灰色。

4.3.3. 读写屏障

下面我们再来看看防止对象的漏标具体做法，不难分析，漏标只有同时满足以下两个条件时才会发生：

条件一：灰色对象断开了白色对象的引用（直接或间接的引用）；即灰色对象原来成员变量的引用发生了变化。
条件二：黑色对象重新引用了该白色对象；即黑色对象成员变量增加了新的引用。
从代码的角度看：

1
2
3

var G = objE.fieldG; // 1.读
objE.fieldG = null;  // 2.写
objD.fieldG = G;     // 3.写

读取对象 E 的成员变量 fieldG 的引用值，即对象 G；
对象 E 往其成员变量 fieldG，写入 null 值。
对象 D 往其成员变量 fieldG，写入对象 G ；

我们只要在上面这三步中的任意一步中做一些“手脚”，将对象 G 记录起来，然后作为灰色对象再进行遍历即可。比如放到一个特定的集合，等初始的 GC Roots 遍历完（并发标记），该集合的对象遍历即可（重新标记）。

注意: 重新标记通常是需要 STW 的，因为应用程序一直在跑的话，该集合可能会一直增加新的对象，导致永远都跑不完。当然，并发标记期间也可以将该集合中的大部分先跑了，从而缩短重新标记 STW 的时间，这个是优化问题了。

读屏障则是拦截第一步，写屏障用于拦截第二和第三步。它们的拦截的目的很简单：就是在读写前后，将对象 G 给记录下来。

4.3.3.1. 读屏障（Load Barrier）

oop oop_field_load(oop* field) {
     pre_load_barrier(field); // 读屏障-读取前操作
     return *field;
}

读屏障是直接针对第一步：var G = objE.fieldG; ，当读取成员变量时，一律记录下来：

void pre_load_barrier(oop* field, oop old_value) {  
     if($gc_phase == GC_CONCURRENT_MARK && !isMarkd(field)) {
          oop old_value = *field;
          remark_set.add(old_value); // 记录读取到的对象
     }
}

这种做法是保守的，但也是安全的。因为条件二中【黑色对象重新引用了该白色对象】，重新引用的前提是：得获取到该白色对象，此时已经读屏障就发挥作用了。

4.3.3.2. 写屏障（Store Barrier）

给某个对象的成员变量赋值时，其底层代码大概长这样：

/**
 * @param field 某对象的成员变量，如 D.fieldG
 * @param new_value 新值，如 null
 */
void oop_field_store(oop* field, oop new_value) { 
     *field = new_value; // 赋值操作
}

所谓的写屏障，其实就是指在赋值操作前后，加入一些处理（类似于 AOP 的概念）：

void oop_field_store(oop* field, oop new_value) {  
      pre_write_barrier(field); // 写屏障-写前操作
      *field = new_value; 
      post_write_barrier(field, value);  // 写屏障-写后操作
}

4.3.4. 解决方案

4.3.4.1. 写屏障 + SATB

4.3.4.2. 写屏障 + 增量更新

4.4. 其他补充

4.4.1. 为什么 G1 用 SATB？CMS 用增量更新？

增量更新：黑色对象新增一条指向白色对象的引用，那么要进行深入扫描白色对象及它的引用对象。

原始快照：灰色对象删除了一条指向白色对象的引用，实际上就产生了浮动垃圾，好处是不需要像 CMS 那样 remark，再走一遍 root trace 这种相当耗时的流程。

4.4.2. ZGC 只使用了读屏障

而 ZGC 有一个标志性的设计是它采用的染色指针技术，染色指针可以大幅减少在垃圾收集过程中内存屏障的使用数量，设置内存屏障，尤其是写屏障的目的通常是为了记录对象引用的变动情况，如果讲这些信息直接维护在指针中，显然可以省去一些专门的记录操作。而 ZGC 没有使用写屏障，只使用了读屏障，显然对性能大有裨益的。

5. 记忆集 - 写屏障 - 卡表

❕ ^1uy99j

5.1. 记忆集

一个对象被不同区域引用的问题
一个 Region 不可能是孤立的，一个 Region 中的对象可能被其他任意 Region 中对象引用，判断对象存活时，是否需要扫描整个 Java 堆才能保证准确
在其他的分代收集器，也存在这样的问题（而 G1 更突出）回收新生代也不得不同时扫描老年代
这样的话会降低 MinorGC 的效率；

记忆集也叫 rememberSet，垃圾收集器在新生代中建立了记忆集这样的数据结构，用来避免把整个老年代加入到 GC ROOTS 的扫描范围中。对于记忆集来说，我们可以理解为他是一个抽象类，那么具体实现它的方法将由子类去完成。这里我们简单列举一下实现记忆集的三种方式：

1.字长精度
2.对象精度
3.卡精度（卡表）

5.2. 写屏障

❕ ^l180q9

每次 Reference 类型数据写操作时，都会产生一个 Write Barrier 暂时中断操作；然后检查将要写入的引用指向的对象是否和该 Reference 类型数据在不同的 Region（其他收集器：检查老年代对象是否引用了新生代对象）；
如果不同，通过 Card Table(卡表) 把相关引用信息记录到引用指向对象的所在 Region 对应的 Remembered Set 中；
当进行垃圾收集时，在 GC 根节点的枚举范围加入 Remembered Set；就可以保证不进行全局扫描，也不会有遗漏。

5.3. 卡表

❕ ^qpslqo

卡表 (Card Table) 是一种对记忆集的具体实现。主要定义了记忆集的记录精度、与堆内存的映射关系等。卡表中的每一个元素都对应着一块特定大小的内存块，这个内存块我们称之为卡页（card page），当存在跨带引用的时候，它会将卡页标记为 dirty。那么 JVM 对于卡页的维护也是通过写屏障的方式，这也就是为什么刚刚我们跟进写屏障操作到最后会发现它会对卡表进行一系列的操作。

5.4. 关系

逻辑上说每个 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。