Garbage-First Garbage Collection

1. INTRODUCTION

首先需要区分两个概念：hard real-time 和 soft real-time。如果目标是hard real-time，那系统有一次没有达到这个目标就认为是失败；如果目标是soft real-time，只需要大概率达到目标，允许系统出现没达到目标的情况，但是如果出现很多没有达到目标的情况系统可能已经出现问题。Garbage-First Garbage Collection(以下简称G1)是一个soft real-time系统，用户可以设置类似1s内最多暂停10ms这样的目标，G1保证大概率去实现。为了达到这个目标，G1使用了几项技术：

• 引入heap region的概念，将整个heap等分成多份region。仍然保留分代的概念，多个region组成逻辑上的Eden/Survivor/Old三个区。每个region维护一个Remembered Set(下面简称RSet)，记录所有region之外引用当前region对象的指针，只需要扫描RSet就可以对单个region单独回收，这是使用region方式的基础。
• 使用snapshot-at-the-beginning(SATB)作为concurrent-marking算法。这个算法有两个功能：1. 周期性分析全局可达性，提供completeness(完备性？)，即保证所有垃圾最后被识别出来；2. 计算每个region的live数据的数量，G1总是优先收集live数据比较少的region，即优先收集垃圾多的region，达到最高的回收效率，这也是Garbage First叫法的来源。
• G1使用以region为单位的粗粒度复制方式，通过建模可以评估每个region回收的时间，因此收集器可以选择在目标时间范围内的region进行回收；同时，为了避免违反目标，可以推迟回收

2. DATA STRUCTURES/MECHANISMS

2.1 Heap Layout/Heap Regions/Allocation

每个region是一段连续的virtual memory，分配的时候递增游标top，记录当前的分配地址。有一个region是concurrent allocation region，对象都在这个region上分配。为了避免多个线程分配的时候产生冲突，每个线程在当前分配region上都有一个thread-local allocation buffer(TLAB)，线程只在自己的TLAB上分配。空的region使用链表连接起来，一个当前分配region满了之后从链表上取出一个空的region进行分配。

2.2 Remembered Set Maintenance

每个region都有一个RSet，记录所有可能引用到这个region里的数据的外部指针。要维护这个RSet要求产生跨region引用的线程通知收集器，这是通过card table来实现：card table里每个字节对应heap中的512个字节的card，card table的状态(dirty表示对应的card有修改；clean表示对应的card没有修改)标记对应的card是否被修改过。每个线程有一个remembered set log，记录产生修改的card的buffer。同时还有一个全局的filled RS buffers集合。

RSet本身也是一个card的集合。为了避免冲突，每个GC线程在region中都有一个card集合，RSet是这些集合的union。RSet的修改通过每次指针修改后执行一个write barrier实现。比如执行x.f = y，rX rY分别对应x y的指针地址，这个时候要在y所在的region的RSet上记录x所在的card的地址，逻辑如下：

write barrier
第1 2行判断x和y是否是在同一个region上，如果是LogOfHeapRegion(region大小求对数)以上的地址是一样的，做XOR移位之后为0；第4行判断y是否是null，如果是也没必要修改；如果x和y不在同一个region且y不为null，则调用rs_enqueue方法。rs_enqueue方法首先读取rX对应的card table项，如果已经是dirty则不做任何处理(初始化的时候会对同一个对象进行多次修改，这里可以避免这种情况产生多条修改记录)；如果不是dirty状态置为dirty，rX对应的card放入线程的remembered set log；如果线程的remember set log已经满了(默认256项)，这个remember set log放入filled RS buffers，给线程重新分配一个remembered set log。

当filled RS buffers达到一个阈值的时候，有一个concurrent remembered set线程对里面的card进行处理：首先将card对应的card table项置为clean，这样对这个card里的对象进行的并发修改会重复上面的逻辑；然后检查card中所有的对象的field指针，如果这个指针指向外部的region，则在这个外部region的RSet上记录这个card的地址，到这里才真正更新了region的RSet。扫描card的所有对象的field指针这步很关键，在上面x.f = y的执行过程中rs_enqueue方法没有使用y所在region的信息，同一个线程中所有对x的修改只需要在在线程的remembered set log中记录一项，rs_enqueue第一步判断card table项为空可以不做处理就是通过这个扫描实现的(否则考虑x.f1 = z，z和y不在同一个region，如果没有扫描x的所有项就会漏掉更新z所在region的RSet)。

上面是有remembered set log和filled RS buffers通过异步操作来提高性能，这是一项优化，对RSet的操作还有另一项优化：hot card。hot card是指一个card被频繁修改，为了避免concurrent remembered set线程对hot card进行频繁处理(需要扫描card内所有对象的field是否指向别的RSet，并更新，这个过程比较耗时)，对于识别为hot card的会尽量推迟到下一次evacuation pause再处理。这里通过另一个记录card出现次数的card table实现，在上一次evacuation pause结束的时候这个card table会清空，concurrent remembered set线程每处理一次card就递增1，超过一定阈值就将这个card放入一个hot queue。当hot queue超过阈值大小的时候，会把超过的card发给concurrent remembered set线程去处理，逻辑跟正常处理card一样。

concurrent remembered set thread只有一个，如果修改很多，可能来不及处理，导致filled RS buffers变得很大。G1限制了filled RS buffer的大小，超过这个值提交remembered set log的线程要自己处理这些card。

2.3 Evacuation Pauses

满足一定条件后(后面会解释)，G1停止所有的线程，开始一次evacuation pause：选取一个region集合，称为collection set(后面称为CSet)，然后这个region集合中的活对象拷贝到堆的其他region中，释放CSet占用的空间。这里需要STW(stop the world)是为了做compact，因为对象的移动对mutator来说必须是原子的，在并发环境下要满足这种原子性代价比较高。

为了尽量缩短evacuation pause的时间，G1尽量利用多线程去处理。第一步是串行选择CSet，然后进入主要的并行阶段。GC线程竞争获取任务：扫描remember set log，更新RSet；扫描RSet和其他GC root，得到活对象；撤离活对象。这些任务只要保证只有一个任务在执行，不需要显式的同步。

2.4 Generational Garbage-First

新创建的对象更有可能成为垃圾，也更有可能成为指针修改的目标，这是分代收集带来的优势。在选取mutator allocation region的时候直接将其指定为young区，这也会将这个region加入下一次回收的CSet里。带来的好处是：young region中的修改不需要考虑remembered set的处理，因为young region中存活对象到了survivor区之后会作为标记的root开始标记。

CSet中可能只包含young region，也可能是所有young region和部分non-young region的混合，两者的处理方式是一致的，分别对应fully young和partially young的evacuation pause模式

2.5 Concurrent Marking

并发标记很重要，在G1中主要有两个功能：保证收集完备性和存活数据信息。G1使用snatshot at the beginning(SATB)并发标记算法，基本思想是保证识别出所有标记开始时刻的垃圾，提供那个时间点对象的一个snapshot。标记过程成新产生的对象之间标记为活的，不需要trace，这大大减少了并发标记的消耗。

2.5.1 Marking Data Structure

有两个标记bitmap，分别为previous bitmap和next bitmap，其中previous bitmap保存这上次标记结束时候的信息，next bitmap记录本次标记的信息，可能还在构建。bitmap中每一位对应一个对象。使用一个mark stack来保存已经标记但是尚未扫描的对象，这个的用法下面会讲到。

2.5.2 Initial Marking Pause/Concurrent Marking

标记的第一步是并发清除next bitmap，然后Initial Marking Pause会停止所有mutator线程，在next bitmap上标记所有从root可达的对象(在分代模式下这个过程是依附于一次young evacuation pause，即在evacuation的时候顺带执行)。每个region会维护两个top at mark start(TAMS)，即标记开始时候的region的top位置(top往下是已分配对象区域，往上是未分配对象区域，可以在上面分配新对象)，分别是previous TAMS和next TAMS。初始标记STW的时候将每个region的top复制到next TAMS，并发标记的时候在next TAMS往上的对象之间认为是已标记(相当于隐式标记，省去更新bitmap的开销)，previous bitmap则保存这上一次标记next bitmap的位置。下图中B和E展示了隐式标记的部分。

TAMS

Initial Marking Pause完成之后mutator线程重新启动，并发标记阶段启动，这个过程和CMS的标记类似：顺序遍历next bitmap，找到一个存活对象为cur，再遍历cur的引用，如果引用在cur之前，则标记完后放入上面说的mark stack中；如果在cur之后则简单标记即可，后面顺序遍历的时候还会再次遍历到。遍历完cur的引用之后查看mark stack，如果不为空在取出顶部的对象按照上面的方式继续遍历，直到标记栈为空。

2.5.3 Concurrent Marking Write Barrier

上面使用TAMS解决了新分配对象的问题，这里很简单，只要在next TAMS之上的对象就是新分配对象，隐式标记为存活对象。但是无法解决原来的对象某个引用修改的问题。比如在初始标记的时候r.f = x，其中x = y；并发标记的时候修改为r.f = z，如果没有进行处理，x和y就无法追溯到，变成垃圾，这就违背了SATB的基础：在最开始标记的时候没有标记到的才是垃圾。因此SATB 标记要求mutator线程记录上面r.f = x的位置。这里使用pre write barrier(相对于RSet的post write barrier)，其过程是：首先判断是否在并发标记阶段，如果不是则不需要记录；如果是判断r.f是否为null，如果是则返回；如果r.f不是null则将r.f的地址(这里就是x)放入当前线程的SATB缓存，类似remembered set log的处理方式，缓存满了之后加入到一个全局的已完成标记缓存集合，并发标记线程会定期检查这个集合，达到一定阈值就暂停标记，进行处理，处理方式和上面顺序遍历next bitmap的方式一样。

2.5.4 Final Marking Pause

标记阶段满足下面两个条件就认为处理完成：1. 当并发标记已经遍历所有已标记对象和mark stack中的对象 2. 上一步的SATB标记缓存已经处理完。其中1很容易检测是否满足，但是2就比较困难，这一步的STW就是为了可靠完成第2步，这里对标记缓存进行并行处理。

2.5.5 Live Data Counting and Cleanup

当最终标记结束之后，gc线程会重新检查每个region，计算TAMS以下标记的数量。标记过程中发生的evacuation pause可能会增加某些region的next TAMS，因此需要一次STW来完成计数。next bitmap和previous bitmap交换角色，next TAMS的值复制到previous TAMS也是发生在这个时候。最后clean阶段会根据GC效率对region进行排序。对于没有包含存活数据的region则在这个阶段直接回收，这一步可以并行执行。

本来只想做下笔记，发现最后成翻译了。
参考 Garbage-First Garbage Collection