数据结构

在了解G1垃圾回收器的算法前，先熟悉在G1中使用的一些数据结构和概念是有用的。如果只是想大概了解一下G1垃圾回收器，那么此节可以跳过。即便想详细了解G1回收器的细节也可以先跳过这一节，直接阅读下面的算法详解，遇到了不明白的数据结构和概念，再回来此处寻找解释。
G1垃圾回收器的复杂难懂，有很大一部分原因是因为这些数据结构。

Heap Region

本质上来说，G1垃圾回收器依然是一个分代垃圾回收器。但是它与一般的回收器所不同的是，它引入了额外的概念，Region。G1垃圾回收器把堆划分成一个个大小相同的Region。在HotSpot的实现中，整个堆被划分成2048左右个Region。每个Region的大小在1-32MB之间，具体多大取决于堆的大小。
G1垃圾回收器的分代也是建立在这些Region的基础上的。对于Region来说，它会有一个分代的类型，并且是唯一一个。即，每一个Region，它要么是young的，要么是old的。还有一类十分特殊的Humongous。所谓的Humongous，就是一个对象的大小超过了某一个阈值——HotSpot中是Region的1/2，那么它会被标记为Humongous。如果我们审视HotSpot的其余的垃圾回收器，可以发现这种对象以前被称为大对象，会被直接分配老年代。而在G1回收器中，则是做了特殊的处理。
G1并不要求相同类型的region要相邻。换言之，就是G1回收器不要求它们连续。当然在逻辑上，分代依旧是连续的。因此，一种典型的分配可能是：
G1垃圾回收器详解 - 图1
G1 Regions
注：图片来自G1: One Garbage Collector To Rule Them All
其中E代表的是Eden，S代表的是Survivor，H代表的是Humongous，剩余的深蓝色代表的是Old（或者Tenured），灰色的代表的是空闲的region。
每一个分配的Region，都可以分成两个部分，已分配的和未被分配的。它们之间的界限被称为top。总体上来说，把一个对象分配到Region内，只需要简单增加top的值。这个做法实际上就是bump-the-pointer。过程如下：
G1垃圾回收器详解 - 图2
Region内存分配
Region可以说是G1回收器一次回收的最小单元。即每一次回收都是回收N个Region。这个N是多少，主要受到G1回收的效率和用户设置的软实时目标有关。每一次的回收，G1会选择可能回收最多垃圾的Region进行回收。与此同时，G1回收器会维护一个空间Region的链表。每次回收之后的Region都会被加入到这个链表中。
每一次都只有一个Region处于被分配的状态中，被称为current region。在多线程的情况下，这会带来并发的问题。G1回收器采用和CMS一样的TLABs的手段。即为每一个线程分配一个Buffer，线程分配内存就在这个Buffer内分配。但是当线程耗尽了自己的Buffer之后，需要申请新的Buffer。这个时候依然会带来并发的问题。G1回收器采用的是CAS（Compate And Swap）操作。

为线程分配Buffer的过程大概是：

  1. 记录top值；
  2. 准备分配；
  3. 比较记录的top值和现在的top值，如果一样，则执行分配，并且更新top的值；否则，重复1；

显然的，采用TLABs的技术，就会带来碎片。举例来说，当一个线程在自己的Buffer里面分配的时候，虽然Buffer里面还有剩余的空间，但是却因为分配的对象过大以至于这些空闲空间无法容纳，此时线程只能去申请新的Buffer，而原来的Buffer中的空闲空间就被浪费了。Buffer的大小和线程数量都会影响这些碎片的多寡。

GC模式

G1中提供了三种模式垃圾回收模式，Young gc、Mixed gc 和 Full gc，在不同的条件下被触发。

1、Young gc

发生在年轻代的GC算法，一般对象（除了巨型对象）都是在eden region中分配内存，当所有eden region被耗尽无法申请内存时，就会触发一次young gc，这种触发机制和之前的young gc差不多，执行完一次young gc，活跃对象会被拷贝到survivor region或者晋升到old region中。
年轻代，默认占用堆大小由以下参数控制：
6df472a7dcb4f0d8cf20d78d85b885e7.png

2、Mixed gc

当越来越多的对象晋升到老年代old region时，为了避免堆内存被耗尽，虚拟机会触发一个混合的垃圾收集器，即mixed gc，该算法并不是一个old gc，除了回收整个young region，还会回收一部分的old region，这里需要注意：是一部分老年代，而不是全部老年代，可以选择哪些old region进行收集，一般是选择回收效益最高的，也就是垃圾最多的region，从而可以对垃圾回收的耗时时间进行控制。
mixed gc中也有一个阈值参数 -XX:InitiatingHeapOccupancyPercent，当老年代大小占整个堆大小百分比达到该阈值时，会触发一次mixed gc.

3、Full gc

如果对象内存分配速度过快，mixed gc来不及回收，导致老年代被填满，就会触发一次full gc，G1的full gc算法就是单线程执行的serial old gc，会导致异常长时间的暂停时间，需要进行不断的调优，尽可能的避免full gc.
有2个条件同时满足则会触发full GC
1.拷贝存活对象晋升（promotion）失败，无法找到可用的空闲分区，GC日志记录为to-space exhausted。或者分配巨型对象无法在老年代找到连续足够的分区
20200201181222647c4g6hgxhbw5dfge_8.jpg
2.当发生第一个条件后，G1会尝试增加堆使用量，如果扩展失败，那么会触发安全措施机制同时发生full GC
full GC中，单个线程会对整个堆的所有代中所有分区做标记、清除以及压缩动作！！非常非常昂贵的操作！

算法会自动在young GC和mixed GC之间切换，并且定期触发Marking cycle phase。HotSpot的G1实现允许指定一个参数InitiatingHeapOccupancyPercent，在达到该参数的情况下，就会执行marking cycle phase。
算法并不使用在对象头增加字段来标记该对象，而是采用bitmap的方式来记录一个对象被标记的情况。这种记录方法的好处就是在使用这些标记信息的时候，仅仅需要扫描bitmap而已。G1统计一个region的存活的对象，就是依赖于bitmap的标记。

并发标记周期

算法的Marking cycle phase大概可以分成五个阶段：

  1. 初始标记：G1收集器扫描所有的根。该过程是和young GC的暂停过程一起的；
  2. 根区间扫描：扫描Survivor Regions中指向老年代的被初始标记标记的引用及引用的对象，这一个过程是并发进行的。但是该过程要在下一个young GC开始之前结束；
  3. 并发标记：并发标记阶段，标记整个堆的存活对象。该过程可以被young GC所打断。并发阶段产生的新的引用（或者引用的更新）会被SATB的write barrier记录下来；
  4. 重新标记：也叫final marking phase。该阶段只需要扫描SATB(Snapshot At The Beginning)的buffer，处理在并发阶段产生的新的存活对象的引用。作为对比，CMS的remark需要扫描整个mod union table的标记为dirty的entry以及全部根；
  5. 清除：清理阶段。该阶段会计算每一个region里面存活的对象，并把完全没有存活对象的Region直接放到空闲列表中。在该阶段还会重置Remember Set。该阶段在计算Region中存活对象的时候，是STW(Stop-the-world)的，而在重置Remember Set的时候，却是可以并行的；

    初始标记

    该阶段扫描所有的根，与CMS类似。所不同的是，该阶段是和young GC一起的。这里的young GC实际上是指的就是fully-young generational mode。

    Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Guide的原文是”This phase is piggybacked on a normal (STW) young garbage collection”。

根区间扫描

该过程主要是扫描Survivor region中指向老年代的，在initial mark phase标记的引用及其引用的对象。这是一个很奇怪的步骤，因为在前面不论是Parallel Collector还是CMS，都没有这么一个步骤。
要理解这一点，要注意的是，算法的两种模式，不论是young GC还是mixed GC，都需要回收young region。因为实际上RS是不记录从young region出发的指针，例如，这部分指针包括young region - young region，也包括young-region - old region指针。那么就可能出现一种情况，一个老年代的存活对象，只被年轻代的对象引用。在一次young GC中，这些存活的年轻代的对象会被复制到Survivor Region，因此需要扫描这些Survivor region来查找这些指向老年代的对象的引用，作为并发标记阶段扫描老年代的根的一部分。
在理解了这一点的基础上，那么对于阶段必须在下一次young GC启动前完成的要求，也就理解了。因为如果第二次的young GC启动了，那么这个过程中，survivor region就可能发生变化。这个时候执行root region phase就会产生错误的结果。

并发标记

在标记阶段，会使用到一个marking stack的东西。G1不断从marking stack中取出引用，递归扫描整个堆里的对象图，并且在bitmap上进行标记。这个递归过程采用的是深度遍历，会不断把对象的域入栈。
在并发标记阶段，因为应用还在运行，所以可能会有引用变更，包括现有引用指向别的对象，或者删除了一个引用，或者创建了一个新的对象等。G1采用的是使用SATB的并发标记算法。

在资料6中记录了使用SATB的两条原则：

  1. All accessible cells at the beginning of the garbage collection are eventually marked during the marked phase;
  2. Newly alocated cells during the garbage collection are never collected during the sweep phase of that garbage collection

在G1中，该算法的关键在于，如果在并发标记的时候，出现了引用修改（不包含新分配内存给对象），那么写屏障会把这些引用的原始值捕获下来，记录在log buffer中。而后再处理。后续的所有的标记，都是从原来的值出发，而不是从新的值出发的。
SATB是一个逻辑上存在概念，在实际中并没有任何真的实际的数据结构与之对应。叫这个名字，是因为，一旦进入了concurrent marking阶段，那么该在该阶段的运行过程中，即便应用修改了引用，但是因为SATB的写屏障记录下来了原始的值，在遍历整个堆查找存活对象的时候，使用的依然是原来的值。这就是在逻辑上保持了一个snapshot at the beginning of concurrent marking phase。
在处理新创建的对象，G1采用了不同的方式。G1用了两个TAMS变量了判断新创建的对象。一个叫做previous TAMS，一个叫做next TAMS。位于两者之间的对象就是新分配的对象。
并发标记阶段，bitmap和TAMS的作用如图：
2579123-c67e3b72dccbe99a.webp
bitmap和TAMS的作用
注：图片引自资料2
该图的详细解释如下：

  1. A是第一次marking cycle的initial marking阶段。next bitmap尚未标记任何存活对象，而此时的previous TAMS被初始化为region内存地址起始值，next TAMS被初始化为top。top实际上就是一个region未分配区域和已分配区域的分界点；
  2. B是经过concurrent marking阶段之后，进入了remark阶段。此时存活对象的扫描已经完成了，因此next bitmap构造好了，刚好代表的是当下状态中region中的内存使用情况。注意的是，此时top已经不再与next TAMS重合了，top和next TAMS之间的就是在前面标记阶段之时，新分配的对象；
  3. C代表的是clean up阶段。C和B比起来，next bitmap变成了previous bitmap，而在bitmap中标记为垃圾（也就是白色区域的）的对应的region的区域也被染成了浅灰色。这并不是指垃圾对象已经被清扫了，仅仅是标记出来了。同时next TAMS和previous TAMS也交换了角色；
  4. D代表的是下一个marking cycle的initial marking阶段，该阶段和A类似，next TAMS重新被初始化为top的值；

  5. EF就是BC的重复；

    重新标记

    该阶段是一个STW的阶段。引入该阶段的目的，是为了能够达到结束标记的目标。要结束标记的过程，要满足三个条件：

  6. concurrent marking已经追踪了所有的存活对象；

  7. marking stack是空的；
  8. 所有的log都被处理了；

前两个条件是很容易达到的，但是最后一个是很困难的。如果不引入一个STW的remark过程，那么应用会不断的更新引用，也就是说，会不断的产生log，因而永远也无法达成完成标记的条件。

清除

该阶段主要完成：

  1. 统计存活对象，这是利用RS和bitmap来完成的，统计的结果将会用来排序region，以用于下一次的CSet的选择；
  2. 重置RSet；
  3. 把空闲region放到空闲region列表中；

该阶段比较容易引起误解地方在于，Clean up并不会清理垃圾对象，也不会执行存活对象的拷贝。也就是说，在极端情况下，该阶段结束之后，空闲Region列表将毫无变化，JVM的内存使用情况也毫无变化。

GC两个关键难点跨代引用与并发标记


一、解决跨代引用：记忆集
记忆集（Remembered Set）：一种用于记录从非收集区域指向收集区域的指针集合的抽象数据结构，在对象层面来说就是非收集区域对象对收集区域对象的引用的记录。
它存放在收集区域，比如在新生代里面存放着老年代对新生代对象的每一个引用。这样在收集新生代的时候，我们就可以根据记忆集知道哪些对象被老年代对象所引用，不能回收，这就解决了跨代引用的问题。
记忆集根据记录的精度分三类：
字长精度：记录的是老年代指向新生代地址。
对象精度：记录的是老年代引用的新生代对象。
卡精度：记录的是新生代一段地址是否存在被老年代引用的记录。
二、记忆集的实现：卡表
卡表（Card Table）：是以第三种卡精度的方式实现的记忆集，也是目前最常用的方式。记忆集是抽象的概念，而卡表就是记忆集的一种具体实现。
卡表最简单的形式可以是一个字节数组，HotSpot就是这样实现的。
CARD_TABLE [this address >> 9] = 0;
大致示意图：
G1垃圾回收器详解 - 图6
把地址的值右移9位相当于除于512就是卡表索引，每字节512为一组对应卡表同一个元素，一组就是一个卡页，如果这个卡页中只要有一个对象被其他区域对象所引用，对应卡表元素的值就变成1，也就是所谓的元素变脏。
在垃圾回收时，只要筛选出卡表中变脏的元素，就能轻易得出哪些卡页对应的内存包含跨代指针，把他们加入GC Rootsz中一并扫描。
三、卡表数据的收集：写屏障
写屏障：可以看成是虚拟机层面在”引用类型字段赋值“这个动作的AOP切面，引用对象赋值的时候产生一个环形通知，进行一些额外的处理，这样就是引用对象赋值这个操作都在写屏障的覆盖范围内，赋值前的写屏障叫写前屏障，复制后的写屏障叫写后屏障。
这样我们就可以通过写屏障，一旦发生赋值操作就可以把引用的更新写进卡表。
四、并发的可达性标记
上一篇文章我们知道，有些垃圾收集器实现了用户线程和收集器的标记线程并发运行的场景，但是用户现场很可能造成引用的更改，那么标记对象可能就不准确。
像下面这种情况:
G1垃圾回收器详解 - 图7
在可达性分析中我们把完成分析的标成黑色，正在分析的标成灰色，未分析的标成白色。在第一步正在分析对象B，对象C引用着对象D。这时用户线程使对象A引用对象D,而对象C不在引用对象D。由于A已经分析过了，不会再进行分析，最终就会造成对象D没有在引用链上而被回收，这样系统就会出现异常了！
要解决这个问题，首先就要分析出现这个问题出现的原因，要同时满足如下两个条件：
赋值器插入了一条或多条从黑色到白色对象的新引用；
赋值前删除了全部从灰色到该白色对象的直接或间接引用；
所以要解决这个问题也简单，只要破坏一个条件就不会出现了。最终有两种解决方案：增量更新（Incremental Update）和原始快照（Snapshot At The Beginning,SATB）
1、增量更新
只要有黑色对象新加了指向白色对象的引用关系，把这个新插入的引用记录下来，等并发扫描结束后，在将这个黑色对象为根重新扫描。
增量更新破坏了第一个条件，使新加的对象都能重新回到引用链上。
2、原始快照
当灰色对象删除指向白色对象的引用关系时，就记录这个将要删除的引用，并发扫描结束后，在以白色对象为根重新扫描一次。
原始快照破坏的是第二个条件，也就是说不管引用关系是否删除，都会按照扫描那一刻的对象图快照进行搜索。这样就保证了对象一定能在调用链上，不过会有少量确实应该回收的存在。
CMS用的增量更新，G1则是原始快照.
五、总结
记忆集记录着收集区域被其他区域引用的数据（地址，对象，内存段）。
卡表是记忆集的具体实现。卡表可以是一个简单的字节数组结构，数组的索引表示的是收集区域的一段内存区域，而元素的值就代表着对应的地址上是否被其他区域所引用。
JVM通过实现AOP切面对“引用对象赋值”操作进行监听，实现把跨代引用记录到记忆集中。
并发的可达性标记可能造成存活对象丢失。丢失的条件是对象从还没有被分析完成对象的引用中移除，然后又被加入到已经完成分析对象的引用中，导致对象没有标记在引用链上而被回收。解决的方案分别是增量更新（破坏第一条）、原始快照（破坏第二条）。
CMS收集器采用的是增量更新，G1则是采用的原始快照。