"GC 的认识" 文中写屏障部分有误

[choleraehyq]

dijkstra style barrier 需要栈重扫，不是因为文中说的原因，而是因为 Go 中出于性能考虑不对栈上保存的指针加 barrier。这一点在 proposal 17503 中讲的很清楚：“However, it also has disadvantages. In particular, it presents a trade-off for pointers on stacks: either writes to pointers on the stack must have write barriers, which is prohibitively expensive, or stacks must be permagrey. Go chooses the later, which means that many stacks must be re-scanned during STW. ”

对于文中的 case，并不影响 GC 的正确性，只是让 GC 更加保守。即使没有栈重扫，那个被错误染黑的 A 在下次 GC 也会被回收掉。

[choleraehyq]

cc @changkun @qcrao

[changkun]

@choleraehyq 您好，非常感谢反馈。你提到的提案中提及的原因我早些时候读到过，但并没有明确的参考文献进一步对这种实现方式提供进行形式化的证明，我对提案中描述内容存在二义性理解：到底是因为性能的选择造就了重扫，还是因为性能原因产生了重扫中更多的工作量。

相反，考虑大量的研究论文已经证明，重扫这一过程是允许灰色赋值器存在的回收器必备的一项属性，即只要允许灰色赋值器，为了满足前进保障，则必定存在重扫；除了此原因之外，并发回收器的正确性还依赖回收器的终止性。终止性的形式化证明体现在：在一轮回收任务中，开始标记时所需要清理的对象，必须在有限轮回收任务中被回收。文中给出的被错误染黑的对象无法从形式上证明能够在有限轮 GC 中不被染黑，必须依赖 STW 期间的重扫。
考虑以上两点原因，文中考虑的结果是：Go 在实现上有别于 Dijkstra 屏障的标准实现，因为性能原因选择不在栈上启用写屏障，因而造成了重扫中更多的工作量，从而增加了 STW 的时间，这也是 Go 为什么一定要切换到混合屏障的原因。

以上是我的个人分析，这也是文中选择提及的需要重扫原因。我目前暂时还没有机会与 Austin 讨论 GC 在历史上的一些设计决策，理解上或许仍然存在误区，如果您发现这个理解中存在明显问题，非常期待进一步指正，我们也可以再进一步讨论。

[choleraehyq]

关于你提到的两点原因，1. “重扫这一过程是允许灰色赋值器存在的回收器必备的一项属性” 有论文例子吗？2. 我没太明白为什么文中给错误染黑的对象不能被回收。A 已经不被任何地方引用了，为什么不能在下次 GC 被回收掉？

[changkun]

@choleraehyq

1. 例如 [1] 中就有提到：“All black objects in a page must be rescanned if the page is dirtied again before the end of a collection.” 其引用的 [BDS91, Boe91] 以及 [1] 这篇文章后续引用文章均有或详细或简略的提及这一点。

2. 我重新回顾了这一过程，确实是我理解错误。重扫是因为降低了对写屏障执行的要求，产生了灰色赋值器（而非使用了 Dijkstra 写屏障而产生了灰色赋值器，触犯了因果错误）。非常感谢能够指出这里的错误，得益于您的指正，一并修正了关于 Yuasa 屏障的一些错误描述，PR 随后提交。

[1] P. Wilson, Uniprocessor Garbage Collection Techniques https://www.cs.cmu.edu/~fp/courses/15411-f14/misc/wilson94-gc.pdf

[choleraehyq]

@changkun 你所引用的 “All black objects in a page must be rescanned if the page is dirtied again before the end of a collection.”，从 [1] 的上下文来看，似乎描述的是 Boehm style write barrier？

论文我没咋看过，但是 The Garbage Collection Handbook 这书 15.2.1 章节讲解了各种灰色赋值器的实现，以及各种实现的比较。其中写到了 Boehm style barrier 需要做 rescan，但是 dijkstra style barrier 没提到。我也不太明白为什么 dijkstra style barrier 需要 rescan。

[changkun]

@choleraehyq 对的，Boehm 屏障也是针对灰色赋值器的一种屏障技术，但没有彻底的避免灰色赋值器，从而需要重扫。The Garbage Collection Handbook 这本书我也曾仔细读过，不过书中关于屏障技术的言论没有给出详细证明，我印象里在相关言论的引用追查原始论文时，并没有发现足够详细的证明来辅助其观点，可能我有存在漏读（如果有希望指出），因此我在阅读中更倾向于重读原始论文。从原始的 On the fly Garbage collection 论文来看，分为 GC1 和 GC2 阶段，也就是我们现在理解的并发标记和并发清扫，没有重扫过程的。根据您提出的质疑，我重读这篇论文后同意您的看法，并已经在前面的 PR 中修正过了：

1. 原始的 Dijkstra 屏障没有重扫，是一种针对灰色赋值器的屏障。PR修正前例子中被染黑的垃圾属于标记过程已经启动后产生的垃圾，原论文中明确指出："new garbage could have been created between an appending phase and the preceding marking phase. We do require: however, that such garbage, existing at the beginning of an appending phase but not identified as such by the collector, will be appended in the next major cycle of the collector. "。
2. Go 由于对 Dijkstra 屏障实现的削弱（栈上写操作不启用WB），导致了部分灰色赋值器的存在（与 Boehm 屏障不同，此处是有意为之），进而需要重扫，导致了更长的 STW。
3. 由于 Yuasa 屏障的引入，不会导致灰色赋值器，进而消除了重扫。

[choleraehyq]

@changkun 赞，看起来我们完全达成共识了，感谢抽出时间一块探讨

[changkun]

@choleraehyq 依然非常感谢您能够质疑并指正错误😁