[HotSpot VM] 关于incremental update与SATB的一点理解

CMS和G1算法都涉及对可达对象的并发标记。并发标记的主要问题是collector在标记对象的过程中mutator可能正在改变对象引用关系图，从而造成漏标和错标。错标不会影响程序的正确性，只是造成所谓的浮动垃圾。但漏标则会导致可达对象被当做垃圾收集掉，从而影响程序的正确性。
为解决漏标问题，GC Handbook一书首先将对象分为三类，即所谓的black对象，grey对象和white对象。white对象是那些还没有被collector标记到的对象；grey对象是那些自身已经被标记到，但其所有引用字段还没有处理的对象；而black对象则是自身已经被标记到，且其引用的所有对象也已经被标记的对象。

基于上述分类，一个white对象在并发标记阶段会被漏标的充分必要条件是：
1、mutator插入了一个从black对象到该white对象的新引用
2、mutator删除了所有从grey对象到该white对象的直接或者间接引用。
因此，要避免对象的漏标，只需要打破上述2个条件中的任何一个即可。

Incremental update关注的是第一个条件的打破，即引用关系的插入。Incremental update利用write barrier将所有新插入的引用关系都记录下来，最后以这些引用关系的src为根STW地重新扫描一遍即避免了漏标问题。
SATB关注的是第二个条件的打破，即引用关系的删除。SATB利用pre write barrier将所有即将被删除的引用关系的旧引用记录下来，最后以这些旧引用为根STW地重新扫描一遍即可避免漏标问题。

不知我的上述理解是否正确，请R大指点。
一个疑问就是http://hllvm.group.iteye.com/group/topic/44381?page=2中，

R大写道

CMS的remark需要重新扫描mod-union table里的dirty card外加整个根集合

为什么还要“外加”扫描“整个根集合”。R大这里所说的根集合是指stack、register、global object这样的根吗，还是另有所指？？

只看 RednaxelaFX 的发言共 8 条回复

R
RednaxelaFX 2014-12-11 #1
LeafInWind 写道
Incremental update关注的是第一个条件的打破，即引用关系的插入。Incremental update利用write barrier将所有新插入的引用关系都记录下来，最后以这些引用关系的src为根STW地重新扫描一遍即避免了漏标问题。

Incremental update的write barrier会拦截所有新插入的引用关系，并且按需要记录新的引用关系。常见实现会判断例如：a.foo = b 那么a是否是黑色对象而b是否是白色对象。也有完全不做过滤的变种。CMS具体使用的write barrier是无条件的，跟HotSpot VM除G1外的其它GC的card marking基本一样。

LeafInWind 写道
SATB关注的是第二个条件的打破，即引用关系的删除。SATB利用pre write barrier将所有即将被删除的引用关系的旧引用记录下来，最后以这些旧引用为根STW地重新扫描一遍即可避免漏标问题。

对的。

LeafInWind 写道
一个疑问就是http://hllvm.group.iteye.com/group/topic/44381?page=2中，
R大写道
CMS的remark需要重新扫描mod-union table里的dirty card外加整个根集合
为什么还要“外加”扫描“整个根集合”。R大这里所说的根集合是指stack、register、global object这样的根吗，还是另有所指？？

在CMS remark的上下文里，根集合指stack、register、globals还有整个young gen。

要注意：CMS是一个old gen collector（不是whole heap collector）。既然只收集old gen，它必须把当前处于非收集区域的young gen算作是root。这跟一般的young GC时要把old gen的remembered set部分算作root的道理一样，只不过HotSpot没有用card table来记录young -> old引用（注），所以就干脆扫描整个young gen作为root。

在CMS initial mark的上下文里，根集合并不包括young gen而是只有stack、register、globals这些常规的。这是因为在接下来的CMS concurrent mark阶段CMS会顺着初始的根集合把young gen里的活对象都遍历了。所以从CMS initial mark + concurrent mark结合在一起的角度看，young gen仍然是根集合的一部分（因为被扫描但不被收集）。

但既然initial mark + concurrent mark已经扫过了young gen为啥还要再在remark时再扫？这就是因为CMS使用的incremental update write barrier是一种“grey mutator”做法。这在之前G1帖的回复里提到了。

如果把mutator也看作一个虚构的对象，那么它也应该有黑灰白的颜色划分。
所谓black mutator做法就是说mutator一旦被初始标记之后，到并发标记结束之前都不可以接触到白对象的指针，或者要确保接触到的白对象都被grey-protected（破坏条件2）；
所谓grey mutator则正好相反，在mutator被初始标记之后，到并发标记结束之前还可以继续接触白对象的指针，只要在标记结束前重新扫描一次完整的根集合即可。。

Incremental update write barrier都是grey mutator做法；SATB write barrier则是black mutator做法。

CMS remark阶段做的就是为了确保grey mutator正确性而重新扫描根集合，同时也要把card table和mod-union table记录下的在old gen里发生了变化的引用也重新扫描一遍。

==============================

前面说了CMS的write barrier非常简单，只是在card table记录一下改变的引用的出发端对应的card。那mod-union table是啥？

其实很简单：card table只有一份，既要用来支持young GC又要用来支持CMS。每次young GC过程中都涉及重置和重新扫描card table，这样是满足了young GC的需求，但却破坏了CMS的需求——CMS需要的信息可能被young GC给重置掉了。

为了避免丢失信息，就在card table之外另外加了一个bitmap叫做mod-union table。在CMS concurrent marking正在运行的过程中，每当发生一次young GC，当young
GC要重置card table里的某个记录时，就会更新mod-union table对应的bit。

这样，最后到CMS remark的时候，当时的card table外加mod-union table就足以记录在并发标记过程中old gen发生的所有引用变化了。

==============================

注：实际上HotSpot VM一般用的post-write barrier非常简单，就是无条件的记录下发生过引用关系变化的card：
```
void post_write_barrier(oop* field, oop val) {
  jbyte* card_ptr = card_for(field);
  *card_ptr = dirty_card;
}
```
这里既不关心field所在的分代，也不关心val的值，所以其实只要有引用改变，其对应的card都会被记录。也就是说这个card table记录的不只是old -> young引用，而是所有发生了变化的引用的出发端，无论在old还是young。

但是HotSpot VM只使用了old gen部分的card table，也就是说只关心old -> ?的引用。这是因为一般认为young gen的引用变化率（mutation rate）非常高，其对应的card table部分可能大部分都是dirty的，要把young gen当作root的时候与其扫描card table还不如直接扫描整个young gen。

==============================

CMS论文里的原始描述：
引用
Initial marking pause. Suspend all mutators and record all objects directly reachable from the roots (globals, stacks, registers) of the system.
Concurrent marking phase. Resume mutator operation. At the same time, initiate a concurrent marking phase, which marks a transitive closure of reachable objects. This closure is not guaranteed to contain all objects reachable at the end of marking, since concurrent updates of reference fields by the mutator may have prevented the marking phase from reaching some live objects. To deal with this complication, the algorithm also arranges to keep track of updates to reference fields in heap objects. This is the only interaction between the mutator and the collector.
Final marking pause. Suspend the mutators once again, and complete the marking phase by marking from the roots, considering modified reference fields in marked objects as additional roots. Since such fields contain the only references that the concurrent marking phase may not have observed, this ensures that the final transitive closure includes all objects reachable at the start of the final marking phase. It may also include some objects that became unreachable after they were marked. These will be collected during the next garbage collection cycle.
Concurrent sweeping phase. Resume the mutators once again, and sweep concurrently over the heap, deallocating unmarked objects. Care must be taken not to deallocate newly-allocated objects. This can be accomplished by allocating objects “live” (i.e., marked), at least during this phase.
L
LeafInWind 2014-12-12 #2
关于为什么要重新扫描根集合，我的理解如下，请R大指教。
假设有如下Java代码
```
public static void main(String[] args) {
  Animal p = new Dog();
  p.bark();
  p = new Horse();
  p.bark();
}
```
假设在如上代码第3行处，CMS gc开始，首先initial mark，local1（即局部变量p）作为一个root，其指向的Dog对象被标记。然后开始concurrent mark，main方法和collecotr并发执行：main将local1引用的对象从Dog对象修改为一个Horse对象，修改过程对应的字节码是astore1，该字节码不会引发write barrier（能引发write barrier的字节码只有putfield，putstatic和aastore），因此这个修改不会被记录下来；另一方面，collector显然只能标记从Dog对象出发的引用，因此Horse对象将永远是一个白对象。第三步，remark，此时如果不重新扫描根集合，显然local1到Horse对象的引用就漏掉了，因此必须重新扫描根集合。

之前以为如果重新扫描根集合，那岂不是initial mark和concurrent mark两个阶段所做的工作都白做了，整个对象关系图又需要重新标记一遍。现在想想其实不是的，因为每个root的扫描过程在触及到一个marked对象的时候就会终止，而concurrent mark阶段正常情况应该已经完成了绝大部分可达对象的标记。
R
RednaxelaFX 2014-12-12 #3
上面的例子不太对。CMS在整个收集过程中让所有新创建的对象都是黑色的，所以上面例子里p = new Horse()之后p持有的是黑对象的指针，没问题。
也就是说在CMS GC进行中创建的对象在这轮收集都会保证存活。这样虽然会有floating garbage问题，但实现起来比较简单，收集速度受影响较小。

实际有问题的情况是：
```
void test() {
  MyObject q = foo(); // this is white
  MyObject p = new MyObject(); // this is implicitly black
  p.someField = q; // black -> white
}

MyObject foo() {
  MyObject q = bar(); // this is white
  return q; // mutator keeps white pointer on stack
}

MyObject bar() {
  MyObject p = getGreyObject();  // this is grey
  MyObject q = p.getWhiteField(); // this is white
  return q; // mutator keeps white pointer on stack
}
```
类似这样的代码。Mutator可能会从一个灰对象的字段得到一个白对象的引用，然后一直持有那个引用；或者一个新创建的对象（在young gen里）也可能会持有这个白对象的引用。

LeafInWind 写道
之前以为如果重新扫描根集合，那岂不是initial mark和concurrent mark两个阶段所做的工作都白做了，整个对象关系图又需要重新标记一遍。现在想想其实不是的，因为每个root的扫描过程在触及到一个marked对象的时候就会终止，而concurrent mark阶段正常情况应该已经完成了绝大部分可达对象的标记。

这个对的。
L
LeafInWind 2014-12-12 #4
R大这个例子，是否还应该添加一个操作，即删除bar方法中那个从grey对象到white对象的引用。

另外又修改了一下我的例子，请R大看看这个对不对
```
public static void main(String[] args) {  
  Animal p = new Dog();  
  p.child = new Dog();
  p.child.bark();  
  Animal q = p.child;
  p.child = null;  
  q.bark();  
}
```
假设第4行代码执行完毕后CMS开始，initial mark将local1指向的Dog对象标记，然后concurrent mark开始，假设main“先”执行，“Animal q = p.child”使得local2（即局部变量q）指向p.child，但由于这个引用关系是通过astore_2字节码添加的，该字节码没有write barrier，且p.child这个操作对应的字节码getfiled也没有read barrier，因此刚添加的这个从q到p.child的引用并不会被card table或者mod-union table记录下来，然后执行“p.child = null”使得灰对象p到白对象p.child的引用关系被删除了，但由于是incremental update而非SATB，引用关系的删除也没有记录。
因此，remark阶段必须重新扫描root，否则q到p.child的引用关系就丢失了。

不知上面这个例子对吗，请R大指教
R
RednaxelaFX 2014-12-12 #5
LeafInWind 写道
R大这个例子，是否还应该添加一个操作，即删除bar方法中那个从grey对象到white对象的引用。

我只是示意一下为啥incremental update write barrier的做法会是grey mutator而已。要真的引发问题的话是应该断开那个grey -> white引用。

LeafInWind 写道
另外又修改了一下我的例子，请R大看看这个对不对
public static void main(String[] args) { Animal p = new Dog(); p.child = new Dog(); p.child.bark(); Animal q = p.child; p.child = null; q.bark(); }

假设第4行代码执行完毕后CMS开始，initial mark将local1指向的Dog对象标记，然后concurrent mark开始，假设main“先”执行，“Animal q = p.child”使得local2（即局部变量q）指向p.child，但由于这个引用关系是通过astore_2字节码添加的，且p.child对应的字节码getfiled也没有read barrier，因此刚添加的这个从q到p.child的引用并不会被card table或者mod-union table记录下来，然后执行“p.child = null”使得灰对象p到白对象p.child的引用关系被删除了，但由于是incremental update而非SATB，引用关系的删除也没有记录。
因此，remark阶段必须重新扫描root，否则q到p.child的引用关系就丢失了。

不知上面这个例子对吗，请R大指教
这个对了～
L

LeafInWind 2014-12-12 #6

R大写道
这个对了～

那么请教R大，如果能够为像astore_X这样的字节码也添加write barrier，记下相应的root，那是否可以避免incremental update在remark阶段对root集合的重新扫描，而只扫描记录了的那部分root？
R

RednaxelaFX 2014-12-17 #7

LeafInWind 写道
那么请教R大，如果能够为像astore_X这样的字节码也添加write barrier，记下相应的root，那是否可以避免incremental update在remark阶段对root集合的重新扫描，而只扫描记录了的那部分root？

因为没见过实际有实现这么做，我不太肯定。理论上这么做我觉得是可以的。

至于为啥没有实际实现这么做，我的猜测有几点：

1、stack和young gen都属于数据快速变化的区域，在这种区域上使用write barrier的受益比较差：原本使用write barrier + remembered set就是为了减少需要扫描的非收集区域的大小，只扫描有变化的部分即可。但调用栈的变化非常频繁，特别是在短小函数/方法多的情况下更加如此。这样write barrier可能会让remembered set把stack和young gen的很大部分区域都记录下来，效益就小了。

2、更糟糕的是，stack和young gen里某个地址上的数据可能会随着 (1)栈帧的出入 (2)与concurrent marking并发执行的young GC 而变成完全不相关的东西。例如说，本来在地址0x3000是某个方法foo()的栈帧的slot 2，过了一会儿它变成了方法bar()的栈帧的return address。这样remembered set就不能只记录引用来源的地址，而必须记录引用自身，这样要记录的数据搞不好比扫描整个root set还大。

有一种跟楼主想像的东西相关但不一样的东西，叫做stack barrier。这是假设一个很深的调用栈的比较老的部分会存活比较长的时间而不变（例如一个主线程上有很深的调用栈的话，最低下的main()的栈帧可能一直都没变过）。这样就没必要在每次扫描根集合时都扫描整个栈，而可以只扫描变化的栈帧。出于性能与精度的权衡，常见的实现是每隔n个栈帧（例如n=25）修改栈帧的返回地址，也就是“劫持”函数的返回到一个特殊的stub里去通知从这个栈帧以上的部分有发生变化。这样重新扫描的时候就只要扫描这里以上的部分，而以下的部分则重用上次扫描记录下来的root list。

这种stack barrier在以下论文里提出：
P. Cheng, R. Harper, and P. Lee. Generational stack collection and profile-driven pretenuring. In 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 162-173, Montreal, Quebec, June 1998. ACM Press.
L

LeafInWind 2014-12-22 #8

感谢R大的回复，关于incremental update的疑问终于都搞清了。