CMS算法实现 -3

总结下老年代GC各个步骤的主要处理流程。

1、InitialMarking / checkpointRootsInitialWork
其主要处理流程如下：

image.png

补充说明如下：

• 执行InitialMarking前markBitMap是空的，Resetting步骤负责将其清空，方便下一次GC时使用
• CMS下各Genaration的ensure_parsability方法都是空实现，这里主要是调用父类CollectedHeap::ensure_parsability的实现，该方法会将各线程已分配的TLAB用int数组填充掉，GC结束后需要分配对象则重新分配TLAB，这样做是为了便于年轻代eden区和from区整体清空；另外，该方法还会将上一次编译代码初始化对象对应的卡表项置为脏的，编译代码在初始化对象属性时，为了性能考虑会忽略BarrierSet，即不会将初始化的属性对应的卡表置为脏的，只是将其初始化对象对应的内存区域临时保存在线程属性中，此处是执行一个补偿，将对应的内存区域在卡表中置为脏的。
• 年轻代的save_marks方法是将三个区对应Space的_saved_mark_word置为top地址，老年代的save_marks方法是将CMS Space的_saved_mark_word置为end地址，同时开启promote跟踪，即会记录所有promote的oop，如果oop的对象头中包含锁等特殊信息还需要保存其对象头。
• 通知ClassLoaderDataGraph记录新创建的ClassLoader，主要是为了后面FinalMarking步骤时可以不用再完整的遍历一遍所有的ClassLoaderData，只需要遍历新创建的ClassLoaderData即可，一个ClassLoader实例对应一个ClassLoaderData。
• ClassLoaderData的claimed标识用于判断这个ClassLoaderData是否已经遍历过了，如果为true表示已经遍历过了，上述清除claimed标识就是将其全部置为false
• 上述步骤的打标都是在markBitMap中将对象地址对应的位置为1，表示该对象是一个存活对象
  根节点遍历时会遍历所有已加载的Klass对应的类class实例，如果其在老年代则将其打标，与年轻代只遍历刚加载的类class实例还在年轻代未promote到老年代不同。
• 遍历年轻代对象的引用类型属性时，如果是并行执行，则将年轻代的三个区的已分配内存区域切割成大小相等的内存块，多个并行的GC线程会原子的判断某个内存块的遍历任务是否已经被其他线程领走了，如果是则继续判断下一个内存块的遍历任务是否被领走了直到找到一个未被领走的遍历任务，然后处理该任务，处理完成则继续领取下一个任务，直到没有待处理的遍历任务，并行线程通知线程池任务执行完成，这一步的目的主要是为了找到年轻代对象持有的老年代对象的引用
• 遍历根节点对象的引用类型属性时，如果是并行执行，会将某一类根节点如线程调用栈帧中的，Universe中的作为单独的遍历任务，并行的GC线程找到未被执行的遍历任务开始执行，直到所有任务都执行完了，并行线程通知线程池任务执行完成，这一步的目的是为了找到已经被promote到老年代的根节点
• 保存_sweep_limit的目的是为了确认后面执行sweep时的边界，只清理_sweep_limit前面的内存，现有实现是将其置为end地址，如果发生扩容end地址就会变更

2、Marking / markFromRootsWork
其主要处理流程如下：

image.png

补充说明如下：

• 上述处理流程是单线程GC时的处理流程，如果是多线程，整体流程基本不变，遍历markBitMap中被打标的位时同样是将老年代的已使用内存空间分割成若干个内存块，每个内存块对应卡表的位的遍历作为一个单独的任务，GC线程不断的取出未领取的任务执行，直到所有的任务都执行完成，然后会尝试从全局共享的用于保存待处理oop的overflow_stack或者其他线程的保存待遍历oop的work_queue中取出oop来遍历，直到取不到oop为止，通知线程池任务执行完成，这样做是为了避免各线程负载不均衡，加速整个遍历任务的完成。单线程遍历时只要一个markStack用于保存待遍历的oop，markStack和overflow_stack的实现是一样的，如果他们满了都会终止遍历，然后从Stack中保存的oop中找出地址最低的一个oop并扩容，将该地址作为下一次循环遍历的起始地址，直到整个markBitMap遍历完成
• 注意Stack满了以后并不会终止整个遍历，而是在扩容完成后继续遍历，即整个遍历过程可能会有多次Stack满的情形，每次满了就会取地址最低的一个oop，会与上一次Stack满了取出的最低的oop地址做比较，如果更低则更新，等整个遍历完成了再从这个最低的oop地址处开始重新遍历，重新遍历时因为之前已经把大部分oop都在markBitMap中处理过了，所以实际处理的oop的个数会随着重新遍历的次数逐渐减少，直到全部遍历完成
• 遍历引用类型属性时，如果其指向的对象未打标则在markBitMap中打标并将其放到Stack中，然后就得检查是否需要yeild，如果需要则执行yeild，让业务线程优先执行，注意只有后台GC会检查是否需要yeild，因为后台GC执行Marking时没有STW，业务线程在正常执行，不能长时间阻塞业务线程的执行。
• 后台GC执行Marking期间，如果前台GC被激活了，则后台GC在遍历完一遍markBitMap后检查前台GC激活了就会退出，将restart_addr置为NULL，并返回false，这时GC的状态不会流转，前台GC继续执行Marking，而且是从老年代的bottom地址开始重新遍历，此前后台GC在markBitMap中已经打标的对象依然有效
  上述流程中判断是否需要yeild的实现如下：

inline void MarkFromRootsClosure::do_yield_check() {
  //业务线程分配对象时会请求CMS Thread执行yeild，should_yield返回true
  //foregroundGCIsActive为true，表示前台GC已激活，此时后台GC应该尽快终止GC，将剩余处理步骤交接给前台GC处理
  //yeild是类属性，其值为CMSYield && asynch，CMSYield 默认为true，表示允许yeild，asynch表示后台GC，即如果是前台GC执行或者前台GC激活了则if不成立
  if (ConcurrentMarkSweepThread::should_yield() &&
      !_collector->foregroundGCIsActive() &&
      _yield) {
    //执行yeild
    do_yield_work();
  }
}
 
void MarkFromRootsClosure::do_yield_work() {
  //进入此方法只能是CMS Thread,必须持有CMS Token
  assert(ConcurrentMarkSweepThread::cms_thread_has_cms_token(),
         "CMS thread should hold CMS token");
  //释放锁
  assert_lock_strong(_bitMap->lock());
  _bitMap->lock()->unlock();
  ConcurrentMarkSweepThread::desynchronize(true);
  //将需要yeild的计数减1
  ConcurrentMarkSweepThread::acknowledge_yield_request();
  _collector->stopTimer();
  GCPauseTimer p(_collector->size_policy()->concurrent_timer_ptr());
  if (PrintCMSStatistics != 0) {
    _collector->incrementYields();
  }
  //icms增量收集模式使用，默认不开启
  _collector->icms_wait();
 
  // See the comment in coordinator_yield()
  for (unsigned i = 0; i < CMSYieldSleepCount &&
                       ConcurrentMarkSweepThread::should_yield() &&
                       !CMSCollector::foregroundGCIsActive(); ++i) {
    //循环休眠1ms
    os::sleep(Thread::current(), 1, false);
    ConcurrentMarkSweepThread::acknowledge_yield_request();
  }
  
 //重新获取锁
  ConcurrentMarkSweepThread::synchronize(true);
  _bitMap->lock()->lock_without_safepoint_check();
  _collector->startTimer();
}

3、Precleaning / AbortablePreclean / preclean_work
Precleaning和AbortablePreclean的底层实现都是preclean_work，前者只调用了一次，预清理Reference实例，后者是循环调用了多次，每次都清理survivor区的对象，preclean_work的主要处理流程如下：

image.png

补充说明如下：

• 每次开始处理一种类型的Reference实例链表前和遍历一个对象前都要检查是否需要yeild，如果需要则执行yield
• 用来遍历modUnionTable中被打标位对应的内存区域和老年代脏的卡表项对应内存区域中的对象的实现类ScanMarkedObjectsAgainCarefullyClosure会检查被遍历的oop是否在markBitMap中打标，只有打标了才遍历其引用类型属性，实际上modUnionTable中被打标位对应的对象肯定是已经在markBitMap中打标了，但是脏的卡表项对应内存区域中的对象不一定打标了，即只处理引用关系发生变更的老年代对象，注意modUnionTable遍历完所有打标的位会被清理掉，脏的卡表项遍历完会被置为precleaned_card，下回遍历脏的卡表项时不会再次遍历它
• 遍历Klass对应的Class实例时会将其_accumulated_modified_oops置为1，FinalMarking再遍历时就不会遍历该Klass了，除非再此期间发生了年轻代GC
  4、FinalMarking / checkpointRootsFinalWork
  其主要处理流程如下：

image.png

补充说明如下：

• InitialMarking如果是前台GC执行的，则说明整个GC过程都是前台GC执行的，因为前台GC执行过程中是STW的，所以类的引用关系不会发生变更，前面的InitialMarking和Marking步骤已经完成了引用遍历和打标，就不需要在FinalMarking环节再次执行。但是如果InitialMarking是后台GC执行的，然后由前台GC继承后台GC执行剩余的步骤，因为从后台GC执行完InitialMarking到前台GC开始执行剩余的GC步骤，这个期间不是STW的，引用关系可能发生变更了，原来是年轻代的对象可能promote到老年代了，引用老年代的对象可能被回收了，所以需要二次遍历打标。
• 遍历脏的卡表项是为了找到老年代引用的刚被promote到老年代的对象，注意老年代脏的卡表项会在Precleaning或者AbortablePreclean时被遍历一遍且被置为preclean_card，所以此时遍历的脏的卡表项是上一次AbortablePreclean遍历脏的卡表项后产生的。跟Precleaning或者AbortablePreclean只遍历已打标对象的处理不同，FinalMarking判断对象在老年代且未打标，则将其打标，并遍历其引用类型属性。注意modUnionTable在遍历时是先找到一段被连续打标的位区域，将其置为0，然后再交给遍历器处理其对应的内存区域中的对象，所以modUnionTable遍历完成后就是空的。但是FinalMarking在遍历脏的卡表项时不会将其置为clean，这样下一次young gc时还可以遍历这部分脏的卡表项，从中找出老年代对象持有的年轻代对象的引用。
• 注意整个引用遍历打标过程不需要yeild，因为FinalMarking虽然是后台GC的一个步骤，但是其是通过VMThread在STW的状态下执行的，不需要yeild，而且要尽可能快的执行完成，即上述流程图中的yeild分支实际不会进入。
• 与InitialMarking不同，FinalMarking遍历根节点时不会遍历ClassLoaderData，而是另外单独遍历所有新创建的ClassLoaderData，然后将记录新创建的ClassLoaderData的标识置为false，因为之前老的ClassLoaderData已经在InitialMarking中遍历了一遍，ClassLoaderData的claimed标识也是true，无法二次遍历。
• FinalMarking执行二次遍历打标时，前面InitialMarking和Marking环节遍历打标的对象还是打标的，即二次遍历打标执行完后被标记的对象只多不少，原来是存活的对象被打标了，但是FinalMarking二次打标时该对象不是存活对象了，一样将其作为存活对象处理。

5、Sweeping / sweepWork
其主要处理流程如下：

image.png

补充说明如下：

• sweep_limit在生产版本下就是老年代的end地址，如果是debug版本则是老年代未分配内存的起始地址，这个地址是通过负责维护对象对应内存块的起始地址的BlockOffsetArray维护的。
• 在执行老年代内存块遍历前后会计算跟内存块合并相关的计数器，比如发生内存块合并的次数，内存块合并的内存大小等，这些数据用于决定sweep时是否需要合并当前内存块，合并的目的是为了保证在满足业务线程尽可能快的分配内存的前提下尽可能的将内存的碎片化减少，提高内存使用率
• 在FinalMarking环节已经完成了类卸载，但是其占用的元空间内存并没有归还该操作系统，只是归还给了元空间本身的内存管理类了，将should_purge置为true，那么下一次进入安全点后就会回收元空间本身的多余内存，参考负责元空间内存回收的purge_if_needed方法的调用链，该方法在purge完成后会将should_purge重新置为false。
• 上述流程中内存块是咋合并的了？空闲内存块本身还在负责空闲内存快管理的FreeList或者Dictionary中，如果需要合并必须将其从FreeList或者Dictionary中移除，而垃圾内存块本身就是需要回收的对象对应的内存块，它们在内存分配时就已经从FreeList或者Dictionary中移除了，不需要再次移除。负责内存块遍历的遍历器本身会维护一个属性freeFinger，表示已经处理过的内存的终止地址，只有将当前内存块初始化成待处理内存块或者归还待处理内存块时会更新该属性。如果当前遍历的内存块可以跟上一次遍历的即待处理的内存块合并则不更新该属性，直到碰到一个不能合并的内存块比如存活对象的内存块，则归还当前待处理的内存块，会将freeFinger到当前内存块的起始地址的内存块完整的归还到FreeList或者Dictionary中从而实现了内存块合并。如果当前遍历的内存块可以跟待处理的内存块合并，但是待处理的内存块为空，则将该内存块初始化为待处理的内存块，并更新freeFinger属性为该内存块的起始地址。
  purge_if_needed方法的调用链如下：

image.png

6、Resetting / reset
reset实际只干一件事，将markBitMap清空，如果是后台GC则分段清空，每清空一个内存段就需要检查是否需要yeild，为了避免CMSThread占用大量CPU时间，影响到关键业务操作的执行；如果是前台GC，则一次性清空，其主要流程如下：

image.png

7、mark_sweep_phase1
其主要流程如下：

image.png

补充说明如下：

• 上述根节点遍历不区分对象是老年代还是年轻代的，只要遍历到了就都在对象头打标，注意这里不是用markBitMap来记录对象的存活。
• 执行堆内存压缩必须要卸载类，没有相关参数控制其不执行类卸载，不过执行完类卸载并不会将should_purge置为true，即不会触发元空间的内存回收，可以参考ClassLoaderDataGraph::set_should_purge方法的调用链。
• 上述引用类型属性遍历不是正常GC使用的oop_iterate方法，而是follow_contents方法，不过两者的底层实现即找到某个对象所持有的所有引用类型属性的方法是一样的

8、mark_sweep_phase2
mark_sweep_phase2的实现比较简单，就是依次调用老年代和年轻代对应Space的prepare_for_compaction方法，该方法用于计算对象复制的地址并将其写入对象头中，其主要流程如下：

image.png

计算对象复制地址并写入对象头是在CompactibleFreeListSpace::forward方法中实现的，其处理流程如下：

image.png

补充说明如下：

• 年轻代的first_compaction_space就是eden区，该区的next_compaction_space就是from区，正常情况下from区的 next_compaction_space是null，如果出现promote失败，则会变成to区；年轻代的first_compaction_space就是CMS Space，next_compaction_space为null，可以参考set_next_compaction_space方法的调用链。即内存压缩时先将对象拷贝到老年代，如果老年代空间不足了再拷贝到年轻代的eden区，eden区不足了再拷贝到from区。
• 上述流程中记录一段连续存活对象的内存区域是通过在第一个非存活对象的地址处用指针的方式初始化一个数据结构，然后记录存活对象的起始地址，等多个连续的存活对象遍历完了碰到第一个非存活对象，则记录存活对象的终止地址，并在第一个非存活对象处再次初始化一个数据结构。保存存活对象的内存区域的目的是为了方便下一步处理时可以跳过非存活对象，快速的完成遍历。
• compact_top是Space的一个实例属性，当内存压缩完成后会将bottom地址修改为compact_top，compact_top之前的地址分配给了内存压缩时复制的对象，新分配对象只能从compact_top之后开始了。
• 如果compact_top地址等于对象地址，说明该对象不需要执行拷贝了，否则就需要将compact_top写入对象头中作为复制地址保存起来

set_next_compaction_space方法的调用链如下：

image.png

9、mark_sweep_phase3
其主要处理流程如下：

image.png

补充说明如下：

• 因为mark_sweep_phase1中已经把所有的ClassLoaderData遍历了一遍，其claimed标识已经置为true了，为了能够二次遍历，这里必须将claimed标识再次清除干净。
• 这一步遍历根节点时，只遍历根节点引用本身即oop，不去处理其所指向的对象，这个是后面遍历老年代和年轻代对象时干的，这一步只是从其指向对象的对象头中取出对象的复制地址，即第二步mark_sweep_phase2计算的地址，然后让oop指向新的地址，注意oop本身是oopDesc的别名，所以oop实际是保存对象地址的8字节内存块的地址，修改这8字节内存块中的数据为新地址，就可以让这个oop*指向新地址了，业务线程就可以无感知的访问到新对象了。
• JNI弱引用oop保存在一个全局的JNIBlock中，里面也是保存了oop*，同样需要让其指向对象新地址；各Reference链表是通过一个链表头oop和各Reference实例的discovered属性构成一个链表的，各各Reference实例的discovered属性指向的oop的调整在后面的老年代和年轻代对象遍历时会完成，此处只调整链表头oop即可。
• 先遍历老年代，再遍历年轻代，底层调用的都是各自的Space的adjust_pointers方法，该方法遍历存活对象的引用类型属性时用的是adjust_pointers方法，其底层实现跟follow_contents基本一致，这两方法都是专门为堆内存压缩准备的。
• 从第一个非存活对象地址处获取下一个存活对象的地址时，是将非存活对象转换成一个对象，然后从对象头中取出下一个存活对象的地址，这种方式跟写入下一个存活对象地址的方式完全不同，是两个完全不同的类，但是逻辑依然是对的，这是因为类虽然不同，但是两者都是操作第一个非存活对象地址后的第一个8字节数据。

10、mark_sweep_phase4
mark_sweep_phase4的实现比较简单，就是依次调用老年代和年轻代对应Space的compact方法，用于完成对象复制，重置bottom地址，其主要流程如下：

image.png