ZGC 笔记：Colored Pointers

26 Aug 2020 by fleuria

ZGC 是从 jdk11 中引进的新一代垃圾回收器，预期的停顿时间不超过 10ms，且停顿时间与堆大小无关，能够支持 tb 级的堆。

作为 go 的爱好者来看，go 的 GC 不是已经搞的不错了吗？按说也就 Initial Mark 有一点 STW，平时的 gc pause 也就 ms 以下？实际上 go GC 实现的效果距离 ZGC 的承诺还有很大距离，碰到大堆就不行了。它没有 compaction，而跑 compaction 好处多多：

  1. 避免堆碎片化，内存分配只需要跳一个指针；
  2. 经过 compaction，相关的对象通常能在内存上相邻，有助于局部性；
  3. 能够真正高速度地回收大量内存，Compaction 的执行时间只与活跃对象相关，与对象总数无关，活跃对象相比所有对象的占比越小，回收效率越高，反观 go 的 sweep 开销是跟对象数直接相关的；

然而并发 compaction 在工程上有很大的难度，在 ZGC 这代 GC 之前，整个行业除了 Azual System 的 Pauseless GC 也别无第二家有卖。compaction 意味着对象指针的重定位（relocation），在 CMS 与 G1GC 中，compaction 与 relocation 都是在年轻代的 STW 中完成的。

这就要求有个机制，能够并发地做到对象的 Relocation。

Load Barrier

在 ZGC 中这就是 Load Barrier 机制，它与 CMS / G1GC 的 Writer Barrier 有很大不同， 包括 INC Barrier 与 SATB Barrier 在内的 Write Barrier，皆生效于「对象修改对外引用」的时机。

Load Barrier 并非 Write Barrier 的直接反义，它生效于「解引用堆指针」的时机：

Object o = obj.FieldA
<Load barrier>
Object p = o         // no barrier, it's not dereferncing any heap reference

做的事情相对于 Write Barrier 也更多，而且在不同的阶段有不同的逻辑，除了 Mark 标记的跟踪，更能够发起移动对象（Relocate），乃至重定向引用（Remap），原地修改指针改指向新对象地址。

有两个问题需要思考一下：

  1. 在跟踪 Mark 标记方面，Write Barrier 会跟踪每一次写入操作，进行标记操作的入队，但放在 Load Barrier 场景下，每次读操作都入队就是一笔不菲的开销了，而且这种重复的入队操作没有意义，一个被多次访问过的引用，按说只需要入队一次即可；
  2. 怎样知道一个对象需不需要 Relocate？类似，一轮 GC 里一个对象只需要 Relocate 一次，relocate 过的对象按说就不需要重复做 relocate 的尝试；

Colored Pointer & Multi-Mapping

对于这两部种元信息，ZGC 使用了一套 Colored Pointer 技术，直接保存到指针里：

  1. Mark 过的指针，打上 Marked 标记，下次你再看到这个指针，就不要重复做 Mark 入队了。
  2. 重定向过的指针，打上 Remapped 标记，表示已经转移成功，就不要尝试对它做 Relocate 了。

ZGC 在设计上做了一个限制，只支持 64 位架构。众所周知 64 位架构里指针往往只实际使用 48 位用于寻址，这里没有用到的 16 位，可以用来存一些元信息。

这里有 4 个 bit 的元信息：

  • Finalizable：用于析构函数处理；
  • Remapped：表示该引用已完成重定向；
  • Marked0 和 Marked1：表示指针已被标记；

先忽略 Finalizable 这个 bit。

其中 Remapped、Marked0、Marked1 三个 bit，永远只有其中之一为 1，其他为 0。

一些架构如 ARM 支持 Pointer Masking 机制，可以告诉 CPU 一个 Pointer Mask，后面 CPU 在解引用时候就会忽略 mask 中指定的这几个 bit。不幸 x86 架构没有这一机制，对此 ZGC 使用了 Multi-Mapping 机制：

  +--------------------------------+ 0x0000140000000000 (20TB)
  |         Remapped View          |
  +--------------------------------+ 0x0000100000000000 (16TB)
  |     (Reserved, but unused)     |
  +--------------------------------+ 0x00000c0000000000 (12TB)
  |         Marked1 View           |
  +--------------------------------+ 0x0000080000000000 (8TB)
  |         Marked0 View           |
  +--------------------------------+ 0x0000040000000000 (4TB)

把 Remmaped View、Marked1 View、Marked0 View 全都指向同一块内存！相当于起到 Pointer Masking 相同的效果。

Mark 与 Relocate

Load Barrier 在不同阶段会做不同的事情，在 Mark 阶段，Load Barrier 做的事情就是将被访问的对象加入标记队列，继而将标记信息落到页面的 Bitmap 中。前面提到，将同一个引用被加入两次标记队列是没有必要的，因此在指针中增加标记 Marked0 或者 Marked1。如果下次访问到这个有 Marked 标记的引用，便不再重复加入到标记队列。

Mark 阶段结束后，经过 Mark 的对象即存活对象可用于移动。ZGC 不会一股脑将所有对象全部做 Relocate，而是有点像 G1GC 的做法，在所有页面中选择一个子集 Relocation Set。Reloccation Set 中的每个页面会有一个张 Forwarding Table，用于保存对象的移动状态。Relocation Set + Forwarding Table 的设计，一方面可以使 Relocation 阶段的执行时间更可控，另一方面也可以节省指针重定向信息的内存开销。反观 SGC 1.0 会在每个对象头维护一个 Forwarding Pointer，就不如 ZGC 这个 Forwarding Table 来的经济。

在 Relocate 阶段，GC 线程会遍历 Relocation Set 中的对象做移动。期间 Load Barrier 遇到 Marked 状态的指针时，会检查 Forwarding Table 中是否存在该引用，如果是，则修改指针内容到新地址，并标记为 Remapped。如果否，则主动发起移动并修改 Forwarding Table，这里会有一个竞争条件，其他线程与 GC 线程都会并发做 Relocate，会走一个 CAS 做仲裁。

Relocate 阶段会完成 Relocation Set 中对象的移动，但是期间指针的重定向（Remap）只会基于 Load Barrier 进行发起。一个存活的对象，在 Relocate 阶段中不一定会被真正访问到，那么这个引用就会仍属于 Marked 状态，到下次访问时仍得查一发 Forwarding Table 表。

这里不妨回到一个问题：为什么会有 Marked0 和 Marked1 两种标记位？

ZGC 会在下一轮 Mark 阶段遍历所有对象与引用的时候，“顺便” 将所有上一轮 Marked 状态的指针进行重定向（Remap），完成新一轮 Mark 阶段之后，上一轮 Marked 状态的指针，都能收敛为 Remapped 状态，所有的 Forwarding Table 也都能够释放了。简而言之，在下一轮 Mark 阶段中，会利用一个上一轮 Mark 阶段的信息，因此会搞两种标记位做区分。

References