1、并发标记

Global concurrent marking基于SATB形式的并发标记。它具体分为下面几个阶段：1、初始标记（initial marking）：暂停阶段。扫描根集合，标记所有从根集合可直接到达的对象并将它们的字段压入扫描栈（marking stack）中等到后续扫描。G1使用外部的bitmap来记录mark信息，而不使用对象头的mark word里的mark bit。在分代式G1模式中，初始标记阶段借用young GC的暂停，因而没有额外的、单独的暂停阶段。2、并发标记（concurrent marking）：并发阶段。不断从扫描栈取出引用递归扫描整个堆里的对象图。每扫描到一个对象就会对其标记，并将其字段压入扫描栈。重复扫描过程直到扫描栈清空。过程中还会扫描SATB write barrier所记录下的引用。3、最终标记（final marking，在实现中也叫remarking）：暂停阶段。在完成并发标记后，每个Java线程还会有一些剩下的SATB write barrier记录的引用尚未处理。这个阶段就负责把剩下的引用处理完。同时这个阶段也进行弱引用处理（reference processing）。注意这个暂停与CMS的remark有一个本质上的区别，那就是这个暂停只需要扫描SATB buffer，而CMS的remark需要重新扫描mod-union table里的dirty card外加整个根集合，而此时整个young gen（不管对象死活）都会被当作根集合的一部分，因而CMS remark有可能会非常慢。4、清理（cleanup）：暂停阶段。清点和重置标记状态。这个阶段有点像mark-sweep中的sweep阶段，不过不是在堆上sweep实际对象，而是在marking bitmap里统计每个region被标记为活的对象有多少。这个阶段如果发现完全没有活对象的region就会将其整体回收到可分配region列表中。

1.1、初始标记阶段

在初始标记阶段，GC 线程首先会创建标记位图 next。nextTAMS 指的就是标记开始时 top 所在的位置，所以在这里我们将它和 top 对齐。在创建位图时，其大小也和 top 对齐，为“（top-bottom）/8”字节。这些处理都是和 mutator 并发进行的。

对可由根直接引用的对象进行标记的过程叫作根扫描。等所有区域的标记位图都创建完成之后，就可以开始进行根扫描了。

为了防止在根扫描的过程中根被修改，在这个过程中 mutator 是暂停执行的。虽然 G1GC 中采用的写屏障技术可以获知对象的修改，但是大多数根并不是对象，它们的修改并不能被写屏障获知，因此在进行根扫描时必须暂停 mutator 的执行。

根需要频繁修改，所以其中大部分不在写屏障可以获知的范围内。也许 G1GC 的设计者认为，与其频繁地通过写屏障去获知修改的方式，还不如直接暂停 mutator 来进行根扫描的方式性能更佳。如果一个对象本身被标记了，但其子对象并没有被扫描，我们就称它为未扫描对象。图使用灰色表示未扫描对象。虽然图中该对象已在根扫描中被标记，但其子对象还没有被扫描到，所以是未扫描对象（灰色）。也就是说，对象 C 持有子对象 A 和 E，但是因为根扫描不会扫描子对象，所以对象 C 作为未扫描对象被表示为灰色。未扫描对象 C 的处理会在后面中讲解。

完成根扫描后，mutator 会再次开启执行，GC 处理也会进入下一阶段。

1.2、并发标记阶段

在并发标记阶段，GC 线程继续扫描在初始标记阶段被标记过的对象，完成对大部分存活对象的标记。

并发标记阶段的一个重要特点是 GC 线程和 mutator 是并发执行的。因为 mutator 在执行过程中可能会改变对象之间的引用关系，所以如果只采用一般的标记方法，可能会发生“标记遗漏”2。因此，必须使用写屏障技术来记录对象间引用关系的变化。

1.2.1、SATB

SATB抽象的说就是在一次GC开始的时候是活的对象就被认为是活的，此时的对象图形成一个逻辑“快照”（snapshot）；然后在GC过程中新分配的对象都当作是活的。其它不可到达的对象就是死的了。SATB要维持“在GC开始时活的对象”的状态这个逻辑snapshot。除了从root出发把整个对象图mark下来之外，其实只需要用pre-write barrier把每次引用关系变化时旧的引用值记下来就好了。这样，等concurrent marker到达某个对象时，这个对象的所有引用类型字段的变化全都有记录在案，就不会漏掉任何在snapshot里活的对象。当然，很可能有对象在snapshot中是活的，但随着并发GC的进行它可能本来已经死了，但SATB还是会让它活过这次GC。

整个write barrier+oop_field_store是这样的：

C代码

1. void oop_field_store(oop* field, oop new_value) {
2. pre_write_barrier(field); // pre-write barrier: for maintaining SATB invariant
3. *field = new_value; // the actual store
4. post_write_barrier(field, new_value); // post-write barrier: for tracking cross-region reference
5. }

按照汤浅式SATB barrier的设计，pre-write barrier里面的抽象逻辑应当如下：

C++代码

1. void pre_write_barrier(oop* field) {
2. if ($gc_phase == GC_CONCURRENT_MARK) { // SATB invariant only maintained during concurrent marking
3. oop old_value = *field;
4. if (old_value != null && !is_marked(old_value)) {
5. mark_object(old_value);
6. $mark_stack->push(old_value); // scan all of old_value's fields later
7. }
8. }
9. }

在每次引用关系发生变化时，旧的引用所指向的对象就会被mark上，其子孙也会被递归mark上，这样就不会漏mark任何对象，snapshot的完整性也就得到了保证。但实际去看G1的论文和代码，会发现它的pre-write barrier却是类似这样的：

C++代码

1. void pre_write_barrier(oop* field) {
2. oop old_value = *field;
3. if (old_value != null) {
4. if ($gc_phase == GC_CONCURRENT_MARK) { // SATB invariant only maintained during concurrent marking
5. $current_thread->satb_mark_queue->enqueue(old_value);
6. }
7. }
8. }

这比原本的汤浅式设计少了些东西：没有检查目标对象是否已经mark，也不去对目标对象做mark和扫描它的字段。实际上该做的事情还是得做，只是不在这里做而已。后面讲到logging barrier的时候就会展开说明了。（Pre-write barrier的实际代码有好几个版本，其中最简单明白的版本是：

C++代码

1. // This notes that we don't need to access any BarrierSet data
2. // structures, so this can be called from a static context.
3. template <class T> static void write_ref_field_pre_static(T* field, oop newVal) {
4. T heap_oop = oopDesc::load_heap_oop(field);
5. if (!oopDesc::is_null(heap_oop)) {
6. enqueue(oopDesc::decode_heap_oop(heap_oop));
7. }
8. }

enqueue动作的实际代码则在G1SATBCardTableModRefBS::enqueue(oop pre_val)。它判断当前是否在concurrent marking phase用的是：

C++代码

1. JavaThread::satb_mark_queue_set().is_active()

SATBMarkQueueSet只有在concurrent marking时才会被置为active。）

1.2.2、logging write barrier 为了尽量减少write barrier对mutator性能的影响，G1将一部分原本要在barrier里做的事情挪到别的线程上并发执行。实现这种分离的方式就是通过logging形式的write barrier：mutator只在barrier里把要做的事情的信息记（log）到一个队列里，然后另外的线程从队列里取出信息批量完成剩余的动作。以SATB write barrier为例，每个Java线程有一个独立的、定长的SATBMarkQueue，mutator在barrier里只把old_value压入该队列中。一个队列满了之后，它就会被加到全局的SATB队列集合SATBMarkQueueSet里等待处理，然后给对应的Java线程换一个新的、干净的队列继续执行下去。并发标记（concurrent marker）会定期检查全局SATB队列集合的大小。当全局集合中队列数量超过一定阈值后，concurrent marker就会处理集合里的所有队列：把队列里记录的每个oop都标记上，并将其引用字段压到标记栈（marking stack）上等后面做进一步标记。

1.3、最终标记阶段

终标记阶段的处理是暂停处理，需要暂停 mutator 的运行。因为未装满的 SATB 本地队列不会被添加到 SATB 队列集合中，所以在并发标记阶段结束后，各个线程的 SATB 本地队列中可能仍然存在待扫描的对象。而最终标记阶段就会扫描这些“残留的 SATB 本地队列”。在图中，队列中保存了对象 G 和 H 的引用。因此在扫描 SATB 本地队列之后，对象 G 和 H，以及对象 H 的子对象 I 都会被标记。

1.4、存活对象计数

这个步骤会扫描各个区域的标记位图 next，统计区域内存活对象的字节数，然后将其存入区域内的 next_marked_bytes 中。图 中的存活对象是 A、C、E、G、H 和 I，因此计算出的总字节数 56 会被存入 next_marked_bytes 中。对象 E 虽然只有头部的 1 个比特被标记了，但参与统计的是它的真实大小，即 16 字节。

1.5、收尾工作

收尾工作所操作的数据中有些是和 mutator 共享的，因此需要暂停 mutator 的运行。在此期间 GC 线程会逐个扫描每个区域，将标记位图 next 中的并发标记结果移动到标记位图 prev 中，再对并发标记中使用过的标记值进行重置，为下次并发标记做好准备。