ch08gc/barrier: writePointer 疑问

[yangxikun]

混合写屏障的算法思想伪代码：

// 混合写屏障
func writePointer(slot, ptr unsafe.Pointer) {
    shade(*slot)                // 对正在被覆盖的对象进行着色，通过将唯一指针从堆移动到栈来防止赋值器隐藏对象。
    if current stack is grey {  // 如果当前 goroutine 栈还未被扫描为黑色
        shade(ptr)              // 则对引用进行着色，通过将唯一指针从栈移动到堆中的黑色对象来防止赋值器隐藏对象
    }
    *slot = ptr
}

如果当前 goroutine 栈已扫描为黑色，而 ptr 为白色对象，此时如果不对 ptr 着色，是否就误回收了对象？

[yangxikun]

Dijkstra 插入屏障 的图示中：“此时A已经错误的着色，必须结束后的重新扫描”，这里不重新扫描也可以吧？因为可以在下一轮GC，把A回收掉
Yuasa 删除屏障 的图示中：DijkstraWritePointer(A.ref3, B)应该为YuasaWritePointer(C.ref3, B)，最后说“此时A已经发生丢失，必须依赖扫描开始前对整个堆栈的备份”，这里A已经没有其他对象引用它了，算是白色对象要被回收的，为何说A丢失了呢？

在上面2个图示中，是不是基于这样一个前提：对象C是栈上的根对象或堆上的从其他灰色对象可达的对象，而A，B都为堆上的对象？

如果Go中目前实现的混合写屏障对被修改对象和被引用对象都标记为灰色，那确实不会出现存活对象丢失的情况了。

[yangxikun]

这种说法是不对的，如果每次都是依赖下一轮的 GC 把对象回收掉，则最坏情况下可能对象永远都不会被回收掉，这是 GC 的正确性不满足。

当前轮的黑色对象没有被其他对象引用，在下一轮应该就会是白色对象了，怎么会出现 “最坏情况下可能对象永远都不会被回收掉”？

Yuasa 的整个例子中整个过程中，A 至始至终都没有被回收器访问到，那么仅从根对象出发，回收器是不可能知道 A 的存在的，也就是 A 的丢失。

没有被访问到说明是白色对象，回收器可以从内存分配器知道A的存在吧？

[yangxikun]

如果下一轮在赋值器的作用下又变为黑色了，就是最坏情况。对于回收器而言，赋值器的操作是不可知的，总是需要考虑最坏情况。

黑色对象已经不可达了，赋值器怎么修改到它呢？

不可以。回收器分配的时候仅仅只是返回可以使用的内存地址以及可以使用的内存大小，如果需要记录分配的所有对象的位置相当于对整个堆的情况进行备份，需要消耗更多的内存空间。

我看Golang源码通过 span 管理对象分配，span 有个 allocBits 负责记录其管理的对象是否分配出去了。释放白色对象，是直接通过 span. allocBits = span.gcmarkBits 实现的。

[PureWhiteWu]

你好，看了你们的讨论，有几个问题：

1. 如果是 GC 时根据追踪找到对象的话，如果我在 gc 不在执行的时候，直接在堆上分配一个对象，然后马上设为 nil，这时候岂不是无法找到我新分配的对象了？新分配的对象不就丢失了？
2. Dijkstra 写屏障如果不进行 STW 扫描，根据我的理解，那么在第二轮开始时，A 对象变成了白色，理论上来说这时候无论如何赋值器都无法使 A 回到黑色的（uintptr 直接赋值一个内存地址然后强转 unsafe.Pointer 这种骚操作除外），这时候带来的问题应该是 A 的丢失吧？因为这时候没有任何一条路径能够访问到 A，A 又不属于根对象。应该不是由于 A 会一直回到黑色导致的无法回收吧？不知道我的理解对不对？

[changkun]

@yangxikun @PureWhiteWu 前面的回复中由于个人的理解错误，固执的持续回复一些错误的言论，首先对错误的关闭 Issue 表示抱歉，并对提出如此重要的问题表示感谢。

---

@yangxikun 关于你的提出的质疑，确实是我此前理解的错误，我这里重新给出修改后的描述：

灰色赋值器的 Dijkstra 插入屏障的基本思想是避免满足条件 1：

// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)
    *slot = ptr
}

为了防止黑色对象指向白色对象，应该假设 *slot 可能会变为黑色，为了确保 ptr 不会在被赋值到 *slot 前变为白色，shade(ptr) 会先将指针 ptr 标记为灰色，进而避免了条件 1。如图所示：

Dijkstra 插入屏障的好处在于可以立刻开始并发标记。但存在两个缺点：

1. 由于 Dijkstra 插入屏障的“保守”，在一次回收过程中可能会残留一部分对象没有回收成功，只有在下一个回收过程中才会被回收；
2. 在标记阶段中，每次进行指针赋值操作时，都需要引入写屏障，这无疑会增加大量性能开销；为了避免造成性能问题，Go 团队在最终实现时，没有为所有栈上的指针写操作，启用写屏障，而是当发生栈上的写操作时，将栈标记为灰色，但此举产生了灰色赋值器，将会需要标记终止阶段 STW 时对这些栈进行重新扫描。

另一种比较经典的写屏障是黑色赋值器的 Yuasa 删除屏障。其基本思想是避免满足条件 2：

// 黑色赋值器 Yuasa 屏障
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot)
    *slot = ptr
}

为了防止丢失从灰色对象到白色对象的路径，应该假设 *slot 可能会变为黑色，为了确保 ptr 不会在被赋值到 *slot 前变为白色，shade(*slot) 会先将 *slot 标记为灰色，进而该写操作总是创造了一条灰色到灰色或者灰色到白色对象的路径，进而避免了条件 2。

Yuasa 删除屏障的优势则在于不需要标记结束阶段的重新扫描，结束时候能够准确的回收所有需要回收的白色对象。缺陷是 Yuasa 删除屏障会拦截写操作，进而导致波面的退后，产生“冗余”的扫描：

Go 在 1.8 的时候为了简化 GC 的流程，同时减少标记终止阶段的重扫成本，将 Dijkstra 插入屏障和 Yuasa 删除屏障进行混合，形成混合写屏障。该屏障提出时的基本思想是：对正在被覆盖的对象进行着色，且如果当前栈未扫描完成，则同样对指针进行着色。

---

@PureWhiteWu

1. 请忽视我此前的错误言论。针对你的问题来回答：被设置为 nil 的对象由于始终保持白色，在一轮 GC 结束后就被回收掉了，你的质疑是正确的。
2. 请忽视我此前的错误言论。针对你的问题来回答：Dijkstra 屏障需要进行重扫的原因并不是因为其本身就需要重扫，而是由于实际实现中对写屏障调用条件的弱化导致灰色赋值器的产生从而才产生的重扫。你的质疑是正确的。完整的修正参见上面贴出的内容。

[PureWhiteWu]

@changkun 非常感谢你的回复！让我受益良多！
我仍然有几个疑问，希望能够不吝赐教：

1. 如果采用 Dijkstra 写屏障，那么带来的问题是：
   a. 有可能部分对象需要下一轮 GC 才能释放，这个我觉得可能不是特别大的问题？（在我所遇到的大部分业务实践中，内存通常不是一个紧张的资源）
   b. 如果对栈上的指针修改也进行写屏障，不考虑性能问题，是否可以不需要标记终止阶段的 STW 重扫？
2. 如果采用 Yuasa 屏障，问题是：
   a. 是否在极端情况之下，标记将永远无法终止（波面永远在后退）？如果是，这个问题是怎么解决的？
   b. 仍然不太了解为什么 Yuasa 屏障需要在扫描前进行 snapshot，希望能够解答一二。
   c. 不考虑问题 a，是否由于可能导致重复扫描的性能原因，Go 团队没有直接采用 Yuasa 屏障，而是使用了混合写屏障？
3. 根据描述，目前的混合写屏障没有实现完整，那么如果完整实现了混合写屏障，是否就不需要 STW 了？
4. 目前的 GC，在扫描开始时和扫描终止阶段的 STW 具体是在做什么？是否能够移除？如果是，那这是一个工程实现复杂度的妥协还是其它原因导致目前存在 STW？
5. Yuasa 屏障图示中：
   
   初始状态的 C 是否应该是灰色的？

再次感谢你的分享和解答！

[changkun]

@PureWhiteWu

1a. 这个不是问题，在 On-the-fly Garbage Collection 这篇论文就有明确指出："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. "

1b. 是的，这就是原始的 Dijkstra 写屏障的描述，参见On-the-fly Garbage Collection。Go 的实现只是削弱了其条件

2a. Yuasa 屏障有终止性证明的，具体可以研读其论文：https://core.ac.uk/download/pdf/39218501.pdf

2b. 我目前认为 snapshot 可能一种误解，因为在 Wilson 的论文（Uniprocessor Garbage Collection Techniques https://www.cs.cmu.edu/~fp/courses/15411-f14/misc/wilson94-gc.pdf) 中把插入屏障和删除屏障分别成为增量更新（incremental update）和起始快照（snapshot-at-the-beginning）屏障。
所谓 snapshot，原意指在删除白色对象的指针时将结果通知给回收器。这个过程很像是对什么都还没有发生的对象图（纯白）进行了一次快照。

2c. Yuasa 最大的问题在于其精度太低，这一点在 Write Barrier Elision for Concurrent Garbage Collectors 这篇论文里面起始有相关数据说明，可以细读一下。但是我目前认为 Go 选择混合屏障引入的主要目的是为了在未来支持 ROC（当时 ROC 还没有被证明性能不行），以及原提案中提到的并发标记终止（消除 STW）等几个未来的演进方向。

3. 完整实现与否与 STW 并无直接联系，目前从标记终止阶段来看，STW 还承载了许多统计功能。

4. 扫描开始时一方面需要确保上一个阶段的垃圾已经全部回收，另一方面需要等待赋值器代码的全部停止，进行一些统计工作；能否移除是一个 Open Problem，取决于未来 Go 的回收器的发展方向
   对于追踪式的垃圾回收来说，STW 是必然的，因为恶意的用户代码可能对回收器的行为造成伤害；STW 是防止 OOM 的底线。从分代GC的研究进展可以看出，消除 STW 是一个工程问题，并不是说能够彻底的不再执行 STW，而是尽可能的通过一些参数控制、用户代码的行为预测，避免 Full GC，降低触发 STW 的概率。

5. 嗯，灰色应该更加严谨，展示一个黑色对象指向白色对象的初始状态是一个错误的示范。

[PureWhiteWu]

十分感谢你抽空进行解答！实在是受益良多！

[lancoLiu]

hi，想请教您一个问题，Yuasa 删除屏障是保证弱三色不变式，他是在指针删除时候才会触发去执行吗？这样子插入行为（假设我直接在黑色对象插入了白色对象）会直接破坏了强三色不变式。是我哪里理解有问题吗？望指教