IBM Java如何做到高性能GC的实现内幕

核心提示：IBM JVM的GC分为三个步骤，Mark phase(标记),Sweep phase(清扫),Compaction phase(内存紧缩). 在了解这些过程之前，IBM Java如何做到高性能GC的实现内幕，我们先看一下IBMjava中的对象的Layout和Heap lay out 一个Java对象在IBM vm中的

　　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那