Serial GC

文章首发公众号：Java 架构师联盟，每日更新技术好文

弱分代假说

Serial GC 是最经典也是最古老的垃圾回收器，使用-XX:+UseSerialGC 开启。它的 Java 堆符合弱分代假说（Weak GenerationalHypothesis）。弱分代假说的含义是大多数对象都在年轻时死亡，这个假说已经在各种不同编程范式或者编程语言中得到证实。与之相对的是强分代假说，它的含义是越老的对象越不容易死亡，但是支持该假说的证据稍显不足。人们注意到大部分对象的生命周期都非常短暂，这符合认知，因为在方法中分配局部变量几乎是最常见的操作，这些对象很多是用后即弃。

基于弱分代假说，虚拟机实现了分代堆模型，它将 Java 堆分为空间较大的老年代（Old Generation）和空间较小的新生代（YoungGeneration）。其中新生代容纳朝生夕死的新对象，在此区域发生垃圾回收较为频繁，老年代容纳生命周期较长的对象，可以简单认为多次垃圾回收后仍然存活的对象生命周期较长。老年代增长缓慢，因此发生垃圾回收的频率较低，这样的堆被称为分代堆。在分代堆模型中，GC 的工作不再是面向整个堆，而是“专代专收”，Young GC（以下简称 YGC）只回收新生代，Full GC（以下简称 FGC）回收整个堆。YGC 的出现使得 GC 无须遍历整个堆寻找存活对象，同时降低了老年代回收的频率。

分代堆受益于对象生命周期的区分，但是也受桎于它。之前只需要遍历整个堆即可找出所有存活对象，分代后却不能简单遍历单个分代，因为可能存在老年代指向新生代的引用，即跨代引用。如果只遍历新生代可能会错误标记一些本来存在引用的对象，继而杀死，而垃圾回收的原则是“宁可漏过不可错杀”，错误地清理存活对象是绝对不可以的。现在的问题是分代后新生代对象除了被 GC Root 引用外还会被老年代跨代引用，如果要遍历空间较大的老年代和 GC Root 才能找出新生代的存活对象，那么就失去了分代的优势，得不偿失。

跨代引用是所有分代式垃圾回收器必须面对的问题，为了处理跨代引用问题，需要一种名为记忆集（Remember Set，RSet）的数据结构来记录老年代指向新生代的引用。另一个问题是老年代很多对象可能已经实际死去，如果老年代死亡对象没有及时清理，新生代回收时会将 GCRoot 和这些老年代中已经死亡的对象当作根来寻找存活对象，导致本该死亡的新生代对象也被标记为存活对象，由此产生浮动垃圾，极端情况下浮动垃圾会抵消堆分代带来的收益。

记忆集暗示着 GC 拥有发现每个写对象操作的能力，每当对象写操作发生时，GC 会检查被写入对象是否位于不同分代并据此决定是否放入记忆集。赋予 GC 这种“发现所有写对象操作”能力的组件是 GC 屏障，具体到上下文中是写屏障。写对象操作属于代码执行系统的一部分，由 GC 屏障与 JIT 编译器、模板解释器合力完成。

在 Serial GC 中，FGC 遍历整个堆，不需要考虑跨代引用，YGC 只发生在新生代，需要处理跨代引用问题。Serial GC 使用的是一种名为卡表的粗粒度的记忆集，下面将展开具体介绍。

卡表

卡表（Card Table）是一种可以存储跨代引用的粗粒度的记忆集，它没有精确记录老年代中指向新生代的对象和引用，而是将老年代划分为 2 次幂大小的一些内存页，记录它们所在的内存页。用卡表来映射这些页，减少了记忆集本身的内存开销，同时也尽量避免了整个老年代的遍历。标准的卡表实现通常为一个 bitmap，它的每个 bit 对应一片内存页。如图 10-2 所示。

图 10-2 Card Table

当 Mutator 线程执行类成员变量赋值操作时，虚拟机会检查是否将一个老年代对象或引用赋值给新生代成员，如果是，则对成员变量所在内存页对应的卡表中的 bit 进行标记，后续只需要遍历卡表中标记过的 bit 对应的内存页，而无须遍历整个老年代。

不过使用 bitmap 可能会相当慢，因为对 bitmap 其中一个 bit 标记时，需要读取整个机器字，更新，然后写回，另外在 RISC 处理器上执行 bit 操作也需要数条指令。一个有效的性能改进是使用 byte 数组代替 bitmap，虽然 byte 数组使用的内存是 bitmap 的 8 倍，但是总的内存占比仍然小于堆的 1%。HotSpot VM 的卡表由 CardTable 实现，它使用 byte 数组而非 bitmap，CardTable::byte_for 函数负责内存地址到卡表 byte 数组的映射，如代码清单 10-7 所示：

代码清单 10-7 CardTable::byte_for

jbyte* CardTable::byte_for(const void* p) const {jbyte* result = &_byte_map_base[uintptr_t(p) >> card_shift];return result;}

其中 card_shift 为 9。从实现中不难看出虚拟机将一片内存页定义为 512 字节，每当某个内存页存在跨代引用时就将 byte_map_base 数组对应的项标记为 dirty。

Young GC

Serial GC 将新生代命名为 DefNewGeneration，将老年代命名为 TenuredGeneration。DefNewGeneration 又将新生代划分为 Eden 空间和 Survivor 空间，而 Survivor 空间又可进一步划分为 From、To 空间，如图 10-3 所示。

图 10-3 Serial GC 新生代细节

YGC 使用复制算法清理新生代空间。关于 YGC 的一个常见场景是起初在 Eden 空间分配小对象，当 Eden 空间不足时发生 YGC，此时 Eden 空间和 From 空间的存活对象被标记，接着虚拟机将两个空间的存活对象转移到 To 空间，如果 To 空间不能容纳对象，那么会转移到老年代。如果 To 空间能够容纳对象，Eden 空间和 From 空间清空，From 空间和 To 空间交换角色，此时存在一个空的 Eden 空间、存在部分存活对象的 From 空间以及空的 To 空间，当下次 YGC 发生时，重复上述步骤。

当一些对象在多次 YGC 后仍然存活时，可以认为该对象生命周期较长，不属于朝生夕死的对象，所以 GC 会晋升该对象，将其从新生代的对象晋升到老年代。除了上述提到的普通情况外，还有一些特殊情况需要考虑，如起初 Eden 空间无法容纳大对象，老年代无法容纳晋升对象等。完整 YGC 逻辑的实现过程如代码清单 10-8 所示，它也包括了特殊清空的处理：

代码清单 10-8 DefNewGeneration::collect

void DefNewGeneration::collect(...) {...if (!collection_attempt_is_safe()) {// 检查老年代是否能容纳晋升对象heap->set_incremental_collection_failed();return;}FastScanClosure fsc_with_no_gc_barrier(...);FastScanClosure fsc_with_gc_barrier(...);CLDScanClosure cld_scan_closure(...);FastEvacuateFollowersClosure evacuate_followers(...);{ // 从GC Root出发扫描存活对象StrongRootsScope srs(0);heap->young_process_roots(&srs, &fsc_with_no_gc_barrier,&fsc_with_gc_barrier, &cld_scan_closure);}evacuate_followers.do_void();// 处理非GC Root直达、成员字段可达的对象... // 特殊处理软引用、弱引用、虚引用、final引用// 如果可以晋升，则清空Eden、From空间；交换From、To空间；调整老年代晋升阈值if (!_promotion_failed) {eden()->clear(SpaceDecorator::Mangle);from()->clear(SpaceDecorator::Mangle);swap_spaces();} else {// 否则通知老年代晋升失败，仍然交换From和To空间swap_spaces();_old_gen->promotion_failure_occurred();}...}

在做 YGC 之前需检查此次垃圾回收是否安全（collection_attempt_is_safe）。所谓是否安全是要判断在新生代全是需要晋升的存活对象的最坏情况下，老年代能否安全容纳这些新生代。如果可以再继续做 YGC。

young_process_roots()会扫描所有类型的 GC Root，并扫描卡表记忆集找出老年代指向新生代的引用，然后使用快速扫描闭包将它们复制到 To 空间。快速扫描闭包即 FastScanClosure，它将针对一个对象（线程、对象、klass 等）的操作抽象成闭包操作，然后传递到处理连续对象的逻辑代码中。由于 HotSpot VM 使用的 C++ 98 语言标准没有 lambda 表达式，所以只能使用类模拟出闭包[1]。FastScanClosure 闭包如代码清单 10-9 所示：

代码清单 10-9 FastScanClosure 闭包

template <class T> inline void FastScanClosure::do_oop_work(T* p) {// 从地址p处获取对象T heap_oop = RawAccess<>::oop_load(p);if (!CompressedOops::is_null(heap_oop)) {oop obj = CompressedOops::decode_not_null(heap_oop);// 如果对象位于新生代if ((HeapWord*)obj < _boundary) {// 如果对象有转发指针，相当于已复制过，那么可以直接使用已经复制后的对象，否则// 需要复制oop new_obj = obj->is_forwarded()?obj->forwardee(): _g->copy_to_survivor_space(obj);RawAccess<IS_NOT_NULL>::oop_store(p, new_obj);if (is_scanning_a_cld()) { // 根据情况设置gc_barrierdo_cld_barrier();} else if (_gc_barrier) {do_barrier(p);}}}}

从 GC Root 和老年代出发，所有能达到的对象都是活对象，FastScanClosure 会应用到每个活对象上。如果遇到已经设置了转发指针的对象，即已经复制过的，则直接返回复制后的对象，否则使用如代码清单 10-10 所示的 copy_to_survivor_space 进行复制：

代码清单 10-10 copy_to_survivor_space

oop DefNewGeneration::copy_to_survivor_space(oop old) {size_t s = old->size();oop obj = NULL;// 在To空间分配对象if (old->age() < tenuring_threshold()) {obj = (oop) to()->allocate_aligned(s);}// To空间分配失败，在老年代分配if (obj == NULL) {obj = _old_gen->promote(old, s);if (obj == NULL) {handle_promotion_failure(old);return old;}} else {// To空间分配成功const intx interval = PrefetchCopyIntervalInBytes;Prefetch::write(obj, interval); // 预取到缓存// 将对象复制到To空间Copy::aligned_disjoint_words((HeapWord*)old,(HeapWord*)obj,s);// 对象年龄增加obj->incr_age();age_table()->add(obj, s);}// 在对象头插入转发指针（使用新对象地址代替之前的对象地址，并设置对象头GC bit）old->forward_to(obj);return obj;}

copy_to_survivor_space()视情况将对象复制到 To 空间或者晋升到老年代，然后为老对象设置新对象地址，即可转发指针（ForwardingPointer）。设置转发指针的意义在于 GC Root 可能存在两个指向相同对象的槽位，如果简单移动对象，并将槽位修改为新的对象地址，第二个 GC Root 槽位就会访问到错误的老对象地址，而设置转发指针后，后续对老对象的访问将转发到正确的新对象上。

上述过程会触碰到 GC Root 和老年代出发直接可达的对象，并将它们移动到 To 空间（或者晋升老年代），这些移动后的对象可能包含引用字段，即可能间接可达其他对象。Serial GC 维护一个 save_mark 指针和已分配空间顶部（to()->top()）指针，To 空间底部到 save_mark 的区域中的对象表示自身和自身字段都扫描完成的对象，save_mark 到空间顶部的区域中的对象表示自身扫描完成但是自身字段未完成的对象。

FastEvacuateFollowersClosure 的任务就是扫描 save_mark 到空间顶部的对象，遍历它们的字段，并将这些能达到的对象移动到空间底部到 save_mark 的区域，然后向前推进 save_mark，直到 save_mark 等于空间顶部，扫描完成。

由于新生代对象可能移动到 To 空间，也可能晋升到老年代，所以上述逻辑对于老年代也同样适用。

Full GC

由于历史原因，FGC 的实现位于 serial/genMarkSweep。虽然从名字上看 SerialGC 的 FGC 的实现似乎是基于标记清除算法，但是实际上 FGC 是基于标记压缩算法实现，如图 10-4 所示。

图 10-4 Serial GC

FGC 使用的标记整理算法是基于 Donald E. Knuth 提出的 Lisp2 算法：首先标记（Mark）存活对象，然后把所有存活对象移动（Compact）到空间的一端。FGC 始于 TenuredGeneration::collect，它会在 GC 前后记录一些日志，可以使用-Xlog:gc*输出这些日志，如代码清单 10-11 所示：

代码清单 10-11 FGC 日志

GC(1) Phase 1: Mark live objectsGC(1) Phase 2: Compute new object addressesGC(1) Phase 3: Adjust pointersGC(1) Phase 4: Move objects

日志显示 FGC 过程分为四个阶段，如图 10-5 所示。

图 10-5 Serial GC 的 FGC 的四个阶段

1. 标记存活对象（Mark Live Object）

第一阶段虚拟机遍历所有类型的 GC Root，然后使用 XX::oops_do(root_closure)从该 GC Root 出发标记所有存活对象。XX 表示 GC Root 类型，root_closure 表示标记存活对象的闭包。root_closure 即 MarkSweep::FollowRootClosure 闭包，给它一个对象，就能标记这个对象、标记迭代标记对象的成员，以及标记对象所在的栈的所有对象及其成员，如代码清单 10-12 所示：

代码清单 10-12 标记存活对象

template <class T> inline void MarkSweep::follow_root(T* p) {// 如果引用指向的对象不为空且未标记T heap_oop = RawAccess<>::oop_load(p);if (!CompressedOops::is_null(heap_oop)) {oop obj = CompressedOops::decode_not_null(heap_oop);if (!obj->mark_raw()->is_marked()) {mark_object(obj); // 标记对象follow_object(obj); // 标记对象的成员}}follow_stack(); // 标记引用所在栈}// 如果对象是数组对象则标记数组，否则标记对象的成员inline void MarkSweep::follow_object(oop obj) {if (obj->is_objArray()) {MarkSweep::follow_array((objArrayOop)obj);} else {obj->oop_iterate(&mark_and_push_closure);}}void MarkSweep::follow_stack() { // 标记引用所在的整个栈do {// 如果待标记栈不为空则逐个标记while (!_marking_stack.is_empty()) {oop obj = _marking_stack.pop();follow_object(obj);}// 如果对象数组栈不为空则逐个标记if (!_objarray_stack.is_empty()) {ObjArrayTask task = _objarray_stack.pop();follow_array_chunk(objArrayOop(task.obj()), task.index());}}while(!_marking_stack.is_empty()||!_objarray_stack.is_empty());}// 标记数组的类型的Class和数组成员，比如String[] p = new String[2]// 对p标记会同时标记java.lang.Class，p[1],p[2]inline void MarkSweep::follow_array(objArrayOop array) {MarkSweep::follow_klass(array->klass());if (array->length() > 0) {MarkSweep::push_objarray(array, 0);}}

2. 计算对象新地址（Compute New Object Address）

标记完所有存活对象后，Serial GC 会为存活对象计算出新的地址，然后存放在对象头中，为接下来的对象整理（Compact）做准备。计算对象新地址的思想是先设置 cur_obj 和 compact_top 指向空间底部，然后从空间底部开始扫描，如果 cur_obj 扫描到存活对象，则将该对象的新地址设置为 compact_top，然后继续扫描，重复上述操作，直至 cur_obj 到达空间顶部。

3. 调整对象指针（Adjust Pointer）

虽然计算出了对象新地址，但是 GC Root 指向的仍然是老对象，同时对象成员引用的也是老的对象地址，此时通过调整对象指针可以修改这些指向关系，让 GC Root 指向新的对象地址，然后对象成员的引用也会相应调整为引用新的对象地址。

4. 移动对象（Move object）

当一切准备就绪后，就在新地址为对象分配了内存，且引用关系已经修改，但是新地址的对象并不包含有效数据，所以要从老对象地址处将对象数据逐一复制到新对象地址处，至此 FGC 完成。Serial GC 将重置 GC 相关数据结构，并用日志记录 GC 信息。

世界停顿

在 10.1.2 节讲过，世界停顿（Stop The World，STW）即所有 Mutator 线程暂停的现象。Serial GC 的 YGC 和 FGC 均使用单线程进行，所以 GC 工作时所有 Mutator 线程必须暂停，Java 堆越大，STW 越明显，且长时间的 STW 对于 GUI 程序或者其他要求伪实时、快速响应的程序是不可接受的，所以 STW 是垃圾回收技术中最让人诟病的地方之一：一方面所有 Mutator 线程走到安全点需要时间，另一方面 STW 后垃圾回收工作本身也需要大量时间。那么，能否利用现代处理器多核，并行化 STW 后垃圾回收中的部分工作呢？关于这一点，Parallel GC 给出了一份满意的答案。