Sapphire 算法简要分析
序
几个月前为了分析goroutine的垃圾回收去看了Sapphire算法的论文，在博客里面也贴了第一部分的译文，
不过太监了，对此表示遗憾。于是将该篇论文重新看了一遍，然后整理了一下大致思路。个人理解，水平有限
，可能有误还望大家批评指教！
概述
支持并发的语言（多线程等）的垃圾回收工作尤为复杂，大多语言采用了以标记-回收算法为主的回收机制，
然而在并发的环境下，在进行标记回收的过程中，应用程序新生成很多对象，也会对已经存在的对象进行引用，
或是对正在被复制的对象进行更改。所以为了保持垃圾回收的正确，往往需要较为严格的同步，这种同步会
导致所谓的STW(Stop the world)。举个极端的例子，GC的时候为了保证GC正确性，所有线程都必须暂停
下来！这样的例子当然过于极端，虽然回收过程会变得相当简单，但是在实际生产的系统中，往往100ms的
暂停都是难以容忍的。Sapphire算法提供了一种思路，相比传统的做法可以大大减少STW的时间，主要原因
是去掉了读屏障，只使用了写屏障（因为应用程序写的次数要远远低于读的次数，数据库的读写分离也是靠
这点进行的优化）。
内存分区
该算法定义了内存中的3个区域，分别为U、C和S。
U区域，是指Uncollected，在一个回收周期开始之后，内存中新申请的空间。
C区域，是指一个回收周期内，内存中已有的对象，它会在回收期间分为两个子区域：O区域，指Old
，当回收器运行时就已经在内存中的对象；N区域,指New，回收器运行过程中，会复制O区域的一部分对象
到新开辟的N区域。
S区域，是指正在运行的各线程的运行栈，由于栈中内存可以自动回收，而且一般都可能会被使用。
三色标记法
标记清楚法一般是指，对堆中没有被正在运行的程序所引用（可以认为是已经没有用的）的对象和被引用的对象
标记颜色，然后删除没有引用的对象，或者将被引用的对象复制到新区域，将所有指向旧对象的指针改到新对象，
然后全部清除旧区域的对象。三色标记法是另一种标记方法（前面说的可以认为是2色标记法），包含3种颜色：
白色：白色是不可达对象（这种对象要被清除掉）；黑色：黑色代表该对象自身是被强引用，而且自身的子引用
也被处理过了（这种对象就是要被留着的）；灰色：灰色代表该对象自己是被强引用，但是子引用还没有被处理
（这是一个中间状态，它最终会变成黑色，但它的子引用和孙引用等不一定是黑色）。
三色标记法有一个原则，永远不许黑色的对象指向白色的对象。
标记阶段
标记阶段分为3个步骤，预标记阶段来安装标记阶段的写屏障，根标记阶段处理非栈中的所有引用树的
根然后再经过堆栈标记阶段来完成标记。
- 预标记阶段
这个阶段安装一个写屏障，类似于以下形式：
// Mark Phase Write Barrier
// this is only for pointer stores
// the update is *p = q
// the p slot may be in U or O
// the q object may be in U or O
mark-phase-write(p, q) {
*p = q;
mark-write-barrier(q);
}
mark-write-barrier(q) {
if (old(q) && !marked(q)) {
// old && !marked means "white"
enqueue-object(q);
// enqueue object for collector
// to mark later
}
}这个写屏障的作用是，对于原本的操作*p = q，p和q都可能在U或者O区域，会触发写屏障，如果q是O区，并且还没有
被标记（即q为白色），就将其入队（准备标记为灰色）。这个屏障的作用就是如果有线程引用了白色的O或者U对象，那么
就准备把它标记为灰色。mutator（原文为此意为修改器，我写作线程）没有直接进行任何的标记，而是将要标记的对象入队，
留着让回收器去标记。可以认为入队的这些对象是“隐性”灰色，此内存屏障执行了黑不指白的原则。
那这里不直接标记的原因是什么呢？因为实际执行的时候会将标记和复制合并一起做，标记步骤会开辟新的空间来复制
对象，如果让线程去做这个开辟空间的操作会导致线程同步的瓶颈（具体来说就是标记、复制对象的时候可能会存在竞争条件）
。让回收器去做申请新的空间和复制过程则可以避免这一瓶颈。而且，每个线程有着自己的队列，进队的时候就不会有同步问题。
当回收器扫描每个线程的栈的时候，它也会清空这个队列，把所有对象移到一个回收器的输入队列中。
- 根标记阶段
根标记阶段遍历U中的对象，并且使用mark-write-barrier把所有U中对象所指向的C中白色对象染灰（因为U中对象一般是在使用之中）。
这个过程会逐渐将U中对象变黑。这个步骤中，向新创建的对象中储存，包括初始化，调用了mark-write-barrier，因此，
新创建的对象都会被认为是黑色的。因为回收器在执行这个写屏障，所以相关对象都会立即进入回收器的输入队列。（前面是线程
执行写屏障，所以对象都是进入了线程自己的队列，直到回收器扫描线程栈的时候才会进入回收器的输入队列）。
- 堆栈标记阶段
堆栈标记阶段，回收器从它的输入队列中拿出对象，判断这个对象是不是已经被标记了。如果已经被标记，那么不做处理
（可能已经被其他回收器或者自己处理了）。如果没有被标记，那么将它标记，并且放入“显性”灰色对象集合，来再次扫描
（扫描它的子引用）。对于每个“显性”灰色对象，它的子元素也会逐渐“变黑”，它自己会被认为已经是黑色。回收器会一直
重复这个过程，直到输入队列和灰色对象集合都空，这其实就是一个递归对灰色对象的各层子元素进行处理的过程。
虽然每个对象可能会在同一个或不同线程进入回收器队列超过一次，但是最终回收器都会标记这个对象，他不会再次进入回收器
队列。
堆栈标记阶段，还会寻找从S指向O的指针。它会停止某个线程到一个安全点，然后扫描这个线程的栈和寄存器，来寻找指向的
O中白色对象，这会对每一个引用（指向）调用标记阶段的写屏障（还可以使用栈屏障来限制这种暂停，跟前面的写屏障类似的
）这样他们也会逐渐“变黑”。当线程被停下来的时候，回收器将线程入队的对象移动到自己的队列里面（通过更改少量指针来
把整个队列抢占）。然后回收器继续这个线程的运行，去处理他自己的输入队列和灰色对象集合直到他们再次空。
扫描一个单独的线程的栈里面指向白色对象的指针很容易，但是要达到一种所有线程的栈里面都没有指向白色对象的指针的状态
并不容易。关键的问题在于即使在扫描完一个线程的栈之后，这个线程还是可能在栈中创建很多指向白色对象的指针，因为没有
读屏障来防止。但是线程不可能向堆中对象写入一个白色对象的指针，因为写屏障会把这个对象变成灰色。
如果在某两个时间点t1和t2，在这些时间点我们都完成了对每个线程的扫描，任何线程栈中都没有白色的指针，没有入队的
对象，而且回收器的输入队列和灰色对象集合在这段时间都是空的（注意最后一个逗号前的句子，指的是两个时间点的状态，
最后半句指的是整个时间段）。那么就可以说现在在S和标记过的O区域中没有白色的指针，因此标记过程完成了。
一个线程只能从一个可达到的灰色或者白色对象中得到一个白色的指针。t1到t2这段时间内没有对象是灰色的，所以线程
只能从白色对象中获取白色指针，而且这个线程必须已经有一个这个白色对象的指针。但是如果这个线程有任何白色的指针，
在它的栈被扫描的时候，它会丢弃他们，所以从那时起，线程不能获取任何白色的指针。所有的线程都是这样的情况，所以
线程栈中不会有任何白色的指针。最开始，被U中指针引用的O对象全部被添加到灰色对象集合而且被处理过了（根标记阶段)，而且从t1时刻起没有其他
的对象被添加到写屏障（因为没有入队的对象）。从一个黑色变量到一个白色对象的可到达对象链必须经过一个灰色
对象（三色染色法的基本原则），而且O中没有灰色对象，所以O中所有可到达对象已经被标记为黑色了。栈扫描这一步有两个可能有用的优化，一个是线程在上次被扫描后就一直被阻塞的，不需要再进行一次扫描；另外，如果使用
栈屏障，可以避免重新扫描上次扫描这个线程后没有重新进入过的区域。
由于指针分别储存在可能或者必须涉及到不同的写屏障，栈扫描要求线程必须在一个GC-consistent（垃圾回收一致）状态，
这个时候每个堆储存区域的写屏障都已经被安装了。
申请新空间以及复制
标记步骤标记的每个O对象都是可以到达的。一旦我们知道了可到达的O对象是哪些，就要为每个O对象分配一个新的N区域的
副本而且复制O对象的内容到新创建的N副本（复制阶段）。
- 申请阶段
一但所有可以到达的O对象都被标记，回收器申请新的空间到N区域，而且设置O对象的转发指针指向给他它相应
的N副本的内存地址。定义这种情况为Oforward（下文用转到）了N。这样对象就可以支持一个可以转发的指针，同时可以
允许对该对象正常的操作。
如果回收器在标记阶段保存了一张被扫描的对象的链表，就可以使用那张表来寻找O对象。转发指针可能可以代替这个表；如果
把两个阶段合并起来，我们就不需要一个显式的表了。
这个算法也需要能够从N获得他对应的O，可以用一个哈希表来实现（后面不需要的时候删掉)。如果没有用哈希表，而是用了
N到O的返回指针，那么到时候还得一个个删除。
- 复制阶段
复制阶段需要一个新的写屏障，来保持O和N相应对象的一致性；预复制阶段安装这个写屏障：
// Copy Phase Write Barrier
// handle ptrs, non-ptrs differently
// p->f = q is the desire update
// objects p, q may be in U or O
copy-write (p, f, q) {
p->f = q;
copy-write-barrier(p, f, q);
}
copy-write-barrier(p, f, q) {
if (forwarded(p)) {
pp = forward(p);
qq = fodward(q); // qq==q for non-ptrs`
pp->f = qq; // wrote 0 first, then N
}
}
forward(p) {
return (forwarded(p)? forwarding-address(p) : p);
}这个写屏障让O或U中进行p->f = q这种操作的时候，对其N的副本（如果有）做同样的操作。
不像大多数回收器的写屏障，这个写屏障允许向堆中对象写指针和数值。他做着和复制回收（replicating copying collection)
相同的事，不过要更紧的同步。它需要在不同代的对象（N和O）中储存指针时都能工作。但是最终，N的指针只会指向U或者N，
不会指向O，这也是一个原则。（也就是说O的指针可能指向O也可能指向N，但是没关系，因为会被清除，但是N不能指向O呀，不然
O死掉之后就内存非法引用了）。
复制阶段复制每个黑色的O对象到他相应的N中的副本。如果复制的是一个指向O的指针，这个指针要被改到指向本来指向的O
的N副本。这里可能会有个巧合，当回收期在复制对象的内容的时候，线程可能也在同时更新这个对象。copy-write-barrier
会导致线程把他们对O的更新扩展到N上面，这样线程就会和回收器进入竞争。我们不希望线程的写屏障变得更加复杂（因为会增加
性能损耗），所以在回收器里面放了一个阻碍函数：
// Collector word copying algorithm
// Goal: copy *p to *q
// p points to an O object field
// q points to the corresponding N field
copy-word(p, q) {
i = max-cycles; // number of times to
do { // try non-atomic copy loop
wo = *p;
wn = forward(wo);
// wn==wo for non-ptrs
*q = wn;
if (*p == wo) return;
// done if no change
} while (--i > 0);
wn = *q; // do these reads in order!
wo = *p;
wn2 = forward(wo);
// wn2==wo for non-ptrs
compare-and-swap (q, wn, wn2);
// address, old-value, new-value
// if the compare-and-swap fails, it's
// ol, because it means the mutator
// copied the new value
}这个阻碍函数放在回收器里面，就避免了正常的工作线程互相竞争，因为我们的垃圾回收要尽力避免对正常线程的影响。
这个复制函数，先是尝试非原子操作（因为CPU的一些关系，非原子操作往往性能要更好），尝试好几次都失败（操作
过程中工作线程改变了原值）就使用原子操作。CAS是一个很基础的并发原语，当地址的值与期望值相等时，会将该
地址的值改成新值。关于最后说即使compare-and-swap失败也是正确的，这个我的理解是，如果在这个过程（循环外）中，
q的值被工作线程改了，不管工作线程怎么改，它都会向p对应的N区域（q）写入应该的值。
调整阶段
最后一个阶段是调整阶段，分为：预调整,堆调整,线程调整以及结束调整。调整阶段的目的是系统地
清除现在线程可以看见和使用的O对象。预调整先安装一个写屏障来帮助跟踪可能包含指向O的指针的地方。然后确保没有堆指针
（U区域）指向O对象。然后开始任意调整所有线程。
开始的时候，没有N副本指向对应O副本的，然后我们要确保没有U和N指向O的。堆调整负责消除U中指向O的指针。没有
调整过的线程可能有指向O和N的指针，但是堆调整过的线程不会有任何指向O的指针。结束调整仅仅回复回收前使用
的写屏障，以及清理掉O区域。
只要存在没有调整过的线程，所有线程都必须同时更新O和N对象。通过使用一些互斥操作，先更新O或者先更新N都不会重要。
重要的是我们需要找到取消N到O的“跳转”的方法。
由于没调整过的线程可能同时访问同一个对象的O和N副本，对于指针的判断比如p==q就有点复杂了。
预调整阶段安装一个调整阶段的写屏障：
// Flip Phase Write Barrier
// p->f = q is the update
// object p may be in U, O, or N
// q may be a ptr or non-ptr:
// omit forwarding for non-ptrs
// if q is a ptr, it may refer
// to U, O, or N
flip-write(p, f, q) {
p->f = q;
if (forwarded(p)) {
// true for BOTH O and N copies so
// that this follows O->N or N->O
pp = forward(p);
qq = q;
if (old(qq)) qq = forward(qq);
// omit step above for non-ptrs
pp->f = qq;
}
}这个写屏障必须在堆调整之前安装，否则没调整过的线程可能在U中写入O的指针。这个屏障使得写入O对象或者N对象的O的
指针都会改成该指针指向的对象在N中的副本。写入其对应还有一个相等判断函数也要在这时安装：
// Pointer Comparison
pointer-equal(p, q) {
if (p == q) return true;
if (q == 0 || p == 0) return false;
return flip-pointer-equal(p, q);
}这也是这个算法唯一用到的一个读屏障，并且这个屏障实现起来很高效，而且使用频率很低。
堆调整很直接：扫描每个U中变量，如果是O的指针，则改向对应的N。因为这可能导致和工作者线程的竞争，所以
回收器要加入一个CAS操作，同样可以忽略CAS的失败。因为工作者线程在这个阶段只能写入N的指针（U中的
O指针都会被这个函数改成对应的N的，O对象和N对象中的指针经过写屏障都会修改成N的，感受到力量了么，这里处理
U，所以写屏障里面根本不写U的处理，为了性能，一字千金）。
// Heap-Flip: U space ptr forwarding
// p points to a U slot,
// that may point to an O object
flip-heap-pointer(p) {
q = *p;
if (old(q))
compare-and-swap(p, q, forward(q));
// avoid race with mutator
}在有预调整安装的写屏障存在的情况下线程调整也是很直接的。将栈和寄存器里面所有O对象都换成N版本就行了。
这个步骤也可以通过栈屏障来优化。用flip-heap-pointer就行了，任何新线程都要开始调整。
结束调整做一些清理工作。一旦所有线程都调整过了，我们可以关掉特殊的写屏障，切换回GC之前的。删掉N对象到O的
哈希表，清理掉O空间就完成了。