IBM Java Jvm GC实现内幕 (几年前的老文)

好言归正传，按照Sam Borman的说法IBM java 1.3.0的GC是HotSpot的2倍，如果在多对称架构中性能更加的高。IBMJava如何做到高性能的GC的呢？我把他们的这篇2万多字的文章浓缩一下介绍给大家。
IBM JVM的GC分为三个步骤，Mark phase(标记),Sweep phase(清扫),Compaction phase(内存紧缩).
在了解这些过程之前，我们先看一下IBMJava中的对象的Layout和Heap lay out
一个Java对象在IBM vm中的结构如下
1.size+flags
2.mptr
3.locknflags
4.objectdata
size+flags
   这是一个4byte的slot(32 平台)。这个slot的主要功能就是描述对象的尺寸。
由于IBMJava中的对象都是以8byte的倍数分配的，因此对象的尺寸其实就是真实尺寸/8存
放在4byte的slot中。另外在这个slot的低三位是保留字段起到标记对象的作用。他们分别为
   bit1:swapped bit，这个交换位被用于Compaction phase即内存紧缩阶段使用。同时
这一位在标记堆栈溢出的时候（mark stack overflow)也被用于标记NotYetScanned状态.
   bit2：dosed bit.这个位用于标示这个对象是否被某个堆栈或者寄存器reference到了。
。如果这个标志被至位则这个对象就不能在当前的GC cycle中被删除。而且如果某个reference指向的内存不是一个真实的reference比如是一个简单的float 或者integer变量但是它的值恰巧就是Heap中某个Object的地址的时候，我们就不能修改这个refernece。这种对象的bit2也被置为1。
   bit3:pinned bit。标记一个对象是否是一个一个钉扣对象(PINNED object)。一个Pinned
Object也不能被GC删除，因为他们可能在Heap之外被reference到了。典型的一个例子
就是Thread，还记得我上面说的僵死县城么？它不能被删除的道理就是这个。另外一种PinnedObject就是 JNI Object，即被本地代码使用的对象。
Mptr:
   在32平台上也是4byte的slot。Mptr有两个功能，
1。如果mptr不是一个数组，则Mptr指向一个方法块(method block)，你可以通过这个
method block来得到一个类块(class block)。这个类块，告诉你这个Object是属于哪个class
的实例。method block和class block由Class Loader分配，而不是heap在heap中进行分配
2。如果mptr是一个数组(Array)，mptr包含了这个对象中，数组的元素个数。
lockflags
    在32平台上也是4byte的slot，但是这个slot只有低4位被用到。
    bit2:是array flag.如果这个位被置位，那么这个对象就是一个数组同时mptr字段
就包含了数组的元素个数。
    bit4是hashed和moved bit.如果这个位被置位，那么他就告诉我们这个对象在被
hashed以后被删除了。
Object Data：
    就是这个对象本身的数据

Heap layout:
  heap top
  heap limit
  heap base

heap base是heap的起始地址，heap top是heap的结束地址。heaplimit 是当前程序使用
的那段heap可以进行扩展和收缩的极限。你可以用-Xmx参数在java运行的时候对heap top
和heap base进行控制。
Alloc bits 和 mark bits
   
  heap top           allocmax    markemax
  heap limit         alloc size  marksize
  heap base
上面这个结构描述了heap和alloc bits 以及,markbits之间的关系。allocbits和markbits
都是元素为1个bit的vector。他们与heap有同样的长度，下面是两个对象被分配以后在heap和两个vector
中的表现
heaptop      allocmax        markmax

heaplimit    allocsize         marksize

object2top
.
.
object2base  object2allocbit    object2markbit

object1top
.
object1base  object1allocbit
如上面的结构，如果一个对象在heap被alloc出来，那么在allocbits中就标示出这个对象的起始地址
所在的地址。allocbits中只标记起始地址。但是这个过程告诉我们这个对象在那里被创建，但是不告诉我们这个对象是否存活。
当在mark phase中如果某一个对象比如object2仍然存活，那么就在markbits中对应的地址上标记一下
The free list
  IBM jvm中的空闲块用用一个free list链标示。如图

freechunck1       freechunck2      freechunckn
size                   size             size
next------------->next--->.........next--->NULL
freeStorage       freeStorage      freestorge
有了这些基本概念我们来看看Mark phase的工作情况

MarkPhase
  GC的Mark phase将标记所有还活着的对象。这个标记所有可达对象的过程称为tracing。Jvm的活动状态（active state)是由下面几个部分组成的。1.每个线程的保存寄存器(saved registers)2.描述线程的堆栈3.Java类中的静态元素3.以及局部和全局的JNI(Java Native Interface)引用。在Jvm中的方法调用都在C Stack上引发一个Frame。这个Frame包含了，对象实例，为局部变量的assignment结果或者传入方法的参数。所有这些引用在Tracing过程中都被同等对待。实际上，我们可以把一个线程的堆栈看城一系列4-bytes slot的集合，然后对每一个堆栈都从顶向下对这些slot进行扫描。在扫描的过程中都必须校验每个slot是否指向heap当中的一个真实的对象。因为在前面我就说过，很有可能这些slot值仅仅是一个int或float但是他们的值恰巧就等于heap中的一个对象地址。因此在扫描的时候必须相当的保守，扫描的时候必须保证所有的指针都是一个对象，而且这个对象没有在GC中被删除。只有符合下面条件的slot才是一个指向对象的指针。1.必须以8-byte的倍数分配的内存2.必须在heap的范围之内(即大于heapbase小于heaptop)3.对应的allocbit必须置为1。满足这些条件的对象引用我们称为roots，并且把他们的dosed bit置为1表示不能被GC删除。我想大家已经知道C#中为何连Int和Float都是OBject的原因了吧。在C#中因为都是OBject因此，在tracing的过程中就减少了一次校验。这个减少对性能起到很大的影响。 如果扫描完成，那么Tracing过程便能安全精确的执行。也就是说我们可以在roots中通过reference找到他对应的objects，由于他们是真实的reference，那么我们就能够在compactionphase中移动对应的对象并且修改这些reference。

  Trace过程使用了一个可以容纳4k的slots的stack。所有的引用逐个push进入这个堆栈并且同时在markbits中进行标记。当push和mark的工作完成之后，我们开始pop出这些slot并且进行trace。
   常规的对象(非数组对象)将通过mptr去访问classblock，classblock将会告诉我们从这个对象中找到的其他对象的reference在那里？当我们在classblock找到一个refernce以后，如果发现他没有被mark，那么我们就在markallocbits中mark他然后把他再压入堆栈。

   数组对象利用mptr去访问每个数组元素，如果他们没有mark则mark然后压入堆栈。
Trace过程一直持续进行，直到堆栈为空。
MarkStack OverFlow
   由于markStack限制了尺寸，因此它可能会溢出。如果溢出发生，那么我们就设定一个全局的标志来表明发生了MarkStack OverFlow,然后我们将那些不能push入stack的OBject的bit1设定为NotYetScanned。然后当tracing过程完成以后，检验全局标志如果发现有overflow则把NotYetScanned的对象再次压入堆栈开始新的tracing过程。
并行Mark(Parallel Mark)
   由于使用逐位清扫(bitwise sweep)和内存紧缩规避功能，GC将化大部分的时间是用于Mark而非前面两项。这就导致了IBM JVM需要开发一个GC的并行版本。并行GC的目的不是以牺牲单CPU系统上的效能来换取在4，8路对称CPU系统上的高效率。
     并行Mark的基本思想就是通过多个辅助线程(helper thread)和一个共享工作的工具来减少Marking的时间。在单CPU系统中，执行GC工作的只有一个主线程。Parallel mark仍然需要这个主线程的参与，他充当了管理协调的角色。这个Thread所要执行的工作和单CPU上的一样多，包括他必须扫描C-Stack来鉴别需要收集的roots指针。一个有N路对称CPU的系统自动含有n-1个helper thread并且平均分布在每个CPU上，master thread将scan完的reference集合进行分块，然后交给helper thread独立完成mark工作。
每个Helper thread都被分配了一个独立的本地mark stack，以及一个shareable queue。sharqueue将存放help thread在mark overflow的时候的NotyetScanned对象。然后由master thread将sharequeue中的对象balance到其他已经空闲的thread上去。
并发Mark(Concurrent mark)
    Concurrent mark的主要目的在于当heap增长的时候减少GC的pause time。只要heap到达heap limit的时候，Concurrent mark就会被执行。在Concurrent phase中，GC要求应用中的每个线程(不是指helper thread而是应用程序自己开启的线程以便充分利用系统资源)扫描他们自己的堆栈来得到roots。然后使用这些roots来同步的trace 可达对象。Tracing工作是由一个后台的低优先级的线程执行，同时程序自己开启的线程在分配内存的时候必须执行heap lock allocation。
     由于使用程序自己开启的线程并发的执行mark live objects，我们必须纪录那些已经trace过的object的变化。这个功能是采用一个叫写闸(write barrier) 来实现的。这个写闸在每次改变引用的时候被激活。它告诉我们什么时候一个对象被跟新过了，以便我们从新扫描那部分heap。写闸的具体实现是Heap会分配出512byte的内存段每个段都分配了一个byte在卡表中(card table)。无论何时一个对象的reference被更新cardtable将同步纪录这个对象的起始地址。使用Byte而不用bit的原因是写byte要比写bit快2倍，而且我们可能希望空余的bit会在未来被用到。

   当Concurrent mark执行完毕以后，STW collection(stop total world)将会被执行。stw的意思是指suspend所有程序自己开启的线程。因此我们可以看到如果使用Concurrent mark那么在mark的时候应用程序不会完全停止。只有收集需要进行collection时以后才执行stw。在上面的讨论中我们认为STW的mark,sweep,compaction可能会暂停应用程序很长时间。其实IBM的gc的停止比我们想象中要短的多。STW只有在下面这些条件才执行1.到达heap limited或者allocation fail2.System.gc方法被调用3.Concurrent mark 完成所有的工作因此我们可以通过调整系统参数来控制STW的执行。当STW执行之前，会扫描卡表检查那些heap需要从新trace，然后执行通常的sweep。

  

Concurrent mark带来的好处就是减少STW所带来的停顿时间。但是这也需要程序自己开启的线程付出一定的代价。这个代价就是需要执行heap lock allocation。这个代价的大小主要取决于CPU有多少超标量流水是空闲的。在Sun的HotSpot中仍然使用单个GC线程进行全部的mark工作，因此IBMJava的GC要快的多而且有跟少的延迟。

Sweep phase

    执行完mark以后就执行sweep。sweep phase其实是最有趣的一个阶段，在我们上面的讨论中一个比较尖锐的问题是GC控制对象的生存情况是否必要。这个在Sun的Java中可能存在，但是在IBMjava中GC根本不知道什么时候sweep了一个对象，甚至不知道sweep了那个对象。

在Sun的HotSpot种的sweep采用了通常的做法就是扫描allocbits和makrbits的交叉项，把那些没有交叉的内存给sweep掉。而在IBM种采用了一种相当高效的方法叫bitsweep。这种方法直接在markbits中寻找长时间不使用的0位（1位代表mark了0位代表空闲或者

需要sweep的内存）。一旦找到长时间不使用的0位，那么我们就去对照在Heap中对应的地址来决定需要释放的内存。如果空闲的总数超过512*Header size那么我们就把这个free块移到free list中。而那些小的内存片则不会放入free list，因为他们会在相邻的对象执行清除或者compact heap的时候被一起覆盖掉。采用了bitsweep以后，GC根本不需要删除单个对象，因为我们知道整个要删除的Chunck就是一个free storge。因此实际上，我们删除一个chunck的时候我们根本不知道删除了几个对象以及删除了那些对象。清扫完成以后，GC会把makrbit copy 到 allocbit上，保证所有的对象的reference都有效。因此myan提到effile中把refernece和本地的object分开处理，其实对于gc来说不是一个好主意。全部依靠reference可以一次清除多个对象，而分开处理就必须使用Hotspot的方法降低GC的性能。

Parallel bitwise sweep

   IBMJava为了多对称系统也设计了并行版本的bitwise sweep。其原理和并行Mark一致。

Compaction phase

  当清扫完毕以后，就开始执行compaction。Java的compaction是相当复杂的。因为移动一个对象，必须修改他们所有的reference。而且如果一个reference是来自一个stack，并且我们不能确定它是否指向一个真实的object，可能它仅仅是一个float，那么这些object

就不能被移动。一个对象是否可以被移动设计到它的”dosed”位是被置位。同样pinned object，那些被JNI引用的对象，只有到Jni unnpined的时候才能被移动。Pinned object的可否移动的判断更加复杂。主要依赖于mptr低三位标示它是否被清扫掉。标示被清扫的 的位存在两个地方：1. The size + flags 字段，如果被标记到OLINK_IsSwapped. 2. mptr 被标记到GC_FirstSwapped。因此看来Java把int 这种普通类型和Object分开处理在GC中会造成过多的不能移动的对象和过多的碎片。对于GC来说很不明智，而且在其他地方也看不出有什么必要分开处理。

否则干吗还要做一个Integer类呢？而C#在这点上来说优势更大。

  IBM java中的Compaction算法为了避免过多的移动对象和利用移动处理一些没有被收集的空闲块因而出奇的复杂。他采用了一种和hotspot不同的算法。不过我们可以用一个很形象的例子来说明问题。把整个Heap想象成一个仓库，仓库堆放了不同尺寸的家具。由于出库的原因，家具之间存在着一定的空隙。Compaction的工作就是把家具往一个方向推来清理空隙。把靠近墙的家具推倒墙边，然后让第二个家具与第一件紧靠在一起。以此类推，然后所有得家具靠再一起，而空隙在另外一边。Pinned and dosed objects 不能被移动的情况会复杂化这个算法，但是主要思想不变。

 

紧缩规避(Compaction avoidance)

  Compaction avoidance的主要目的在于开辟较大内存的时候降Compaction的使用次数来保证GC pause time能够足够短。在Ibm jvm中的Compaction的执行条件如下：

1． 如果开辟一个大内存的时候遍例Free list发现没有合适的free storge激发alloc failure时间

2． 在上次GC过程中出现了一次alloc failure

3． 被激活的Heap(heap limited到heap base之间的heap)只有5%为free

4． 被激活的Heap不大于128K

IBM jvm在上面四个条件中满足一项就执行compaction。其中最为常见的是第一种，

为了避免Companction，Ibmjava采用了紧缩规避的方法。这个方法称为荒野内存(wilderness preservation),也就是在heap limit之上再开辟一块内存。这块内存保持原始状态，其大小为激活Heap的5%,默认设置为3M.如果一旦有一个大块内存需要开辟，而freelist中没有合适的storge的时候就使用wilderness preservation保证不抛出 alloc failure。一旦wilderness被用尽则产生一个alloc failure通知GC执行Compaction。通常来说wilderness preservation能够保证不使用Compaction，因为基本上使用到wilderness的对象是这个应用程序中最大的对象。



Ibm的JVM关键实现就是这样，我们可以看到ibmJVM使用的很多算法让我们原本考虑的一些gc的困难降低到了一个可以忍受的限度，比如STW的pause time，其实只涉及了sweep和compaction，mark phase在程序运行的同时就完成了基本不影响程序的正常工作。而且由于使用了bitsweep,和紧缩规避使得STW的时间大大降低，他们两个的工作量的总和不到Mark的30%。而且在多对称处理器上又采用并行mark和sweep，可以近一部的提高GC效率。