屏障技术在本书指内存屏障（Memory Barrier）。 它保障了代码描述中对内存的操作顺序 既不会在编译期被编译器进行调整，也不会在运行时被 CPU 的乱序执行所打乱， 是一种语言与语言用户间的契约。

4.3.1 并行标记清理产生的问题

在没有用户态代码并发修改三色抽象的情况下，回收可以正常结束。但并发回收的根本问题在于， 用户态代码在回收过程中会并发的更新对象图，从而赋值器和回收器可能对对象图的结构产生不同的认知， 这时以一个固定的三色波面作为回收过程前进的边界则不再合理。
我们不妨考虑赋值器的写操作，假设某个灰色对象 A 指向白色对象 B， 而此时赋值器并发的将黑色对象 C 指向（ref3）了白色对象 B， 并将灰色对象 A 对白色对象 B 的引用移除（ref2），则在继续扫描的过程中， 白色对象 B 永远不会被标记为黑色对象了（回收器不会重新扫描黑色对象）。 进而产生被错误回收的对象 B，如图 1 所示。
第四章 4.3 屏障技术 - 图1 图 1: 回收器正确性的破坏

4.3.2 弱三色不变性

垃圾回收器的正确性体现在：不应出现对象的丢失，也不应错误的回收还不需要回收的对象。 作为内存屏障的一种，写屏障（Write Barrier）是一个在并发垃圾回收器中才会出现的概念。
可以证明，当以下两个条件同时满足时会破坏垃圾回收器的正确性 [Wilson, 1992]：

  • 条件 1: 赋值器修改对象图，导致某一黑色对象引用白色对象；
  • 条件 2: 从灰色对象出发，到达白色对象的、未经访问过的路径被赋值器破坏。

只要能够避免其中任何一个条件，则不会出现对象丢失的情况，因为：

  • 如果条件 1 被避免，则所有白色对象均被灰色对象引用，没有白色对象会被遗漏；
  • 如果条件 2 被避免，即便白色对象的指针被写入到黑色对象中，但从灰色对象出发，总存在一条没有访问过的路径，从而找到到达白色对象的路径，白色对象最终不会被遗漏。

我们不妨将三色不变性所定义的波面根据这两个条件进行削弱：

  • 当满足原有的三色不变性定义（或上面的两个条件都不满足时）的情况称为强三色不变性（strong tricolor invariant）
  • 当赋值器令黑色对象引用白色对象时（满足条件 1 时）的情况称为弱三色不变性（weak tricolor invariant）

当赋值器进一步破坏灰色对象到达白色对象的路径时（进一步满足条件 2 时），即打破弱三色不变性， 也就破坏了回收器的正确性；或者说，在破坏强弱三色不变性时必须引入额外的辅助操作。 弱三色不变形的好处在于：只要存在未访问的能够到达白色对象的路径，就可以将黑色对象指向白色对象。

4.3.3 赋值器的颜色

如果我们考虑并发的用户态代码，回收器不允许同时停止所有赋值器， 就是涉及了存在的多个不同状态的赋值器。为了对概念加以明确，还需要换一个角度， 把回收器视为对象，把赋值器视为影响回收器这一对象的实际行为（即影响 GC 周期的长短）， 从而引入赋值器的颜色：

  • 黑色赋值器：已经由回收器扫描过，不会再次对其进行扫描。
  • 灰色赋值器：尚未被回收器扫描过，或尽管已经扫描过但仍需要重新扫描。

赋值器的颜色对回收周期的结束产生影响： 如果某种并发回收器允许灰色赋值器的存在，则必须在回收结束之前重新扫描对象图。 如果重新扫描过程中发现了新的灰色或白色对象，回收器还需要对新发现的对象进行追踪， 但是在新追踪的过程中，赋值器仍然可能在其根中插入新的非黑色的引用，如此往复， 直到重新扫描过程中没有发现新的白色或灰色对象。 于是，在允许灰色赋值器存在的算法，最坏的情况下， 回收器只能将所有赋值器线程停止才能完成其跟对象的完整扫描，也就是我们所说的 STW。

4.3.4 新分配对象的颜色

新的分配过程会导致赋值器持有新分配对象的引用。可想而知我们需要为新产生的对象分配适当的颜色。 可想而知，新分配对象的颜色会产生不同的影响：

  1. 如果新分配的对象为黑色或者灰色，则赋值器直接将其视为无需回收的对象，写入堆中；
  2. 如果新分配的对象为白色，则可以避免无意义的新对象保留到下一个垃圾回收的周期。

如果我们进一步思考，则能够发现，由于黑色赋值器由于已经被回收器扫描过， 不会再对其进行任何扫描，一旦其分配新的白色对象 则意味着会导致错误的回收。因此黑色赋值器不能产生白色对象， 除非赋值器能够保证分配的白色对象的引用能够被写入到灰色波面中， 但这实践起来并不容易。不难看出，为了简化实现复杂度，令新分配的对象为黑色通常是安全的。

4.3.5 赋值器屏障技术

我们在谈论垃圾回收器的写屏障时，其实是指赋值器的写屏障，即赋值器屏障。 赋值器屏障作为一种同步机制，使赋值器在进行指针写操作时，能够“通知”回收器，进而不会破坏弱三色不变性。
屏障上需要依赖多种操作来应对指针的插入和删除 [Pirinen, 1998]：

  • 扩大波面：将白色对象作色成灰色
  • 推进波面：扫描对象并将其着色为黑色
  • 后退波面：将黑色对象回退到灰色

根据灰色赋值器和黑色赋值器的不同，分别会有不同类别的赋值器屏障。我们针对两种不同 类型的赋值器来分别介绍两个与 Go 有关的赋值器屏障： 灰色赋值器的 Dijkstra 插入屏障与黑色赋值器的 Yuasa 删除屏障。

灰色赋值器的 Dijkstra 插入屏障

插入屏障（insertion barrier）技术，又称为增量更新屏障（incremental update）[Wilson, 1992] 。 其核心思想是把赋值器对已存活的对象集合的插入行为通知给回收器，进而产生可能需要额外（重新）扫描的对象。 如果某一对象的引用被插入到已经被标记为黑色的对象中，这类屏障会保守地将其作为非白色存活对象， 以满足强三色不变性。
Dijkstra 插入屏障 [Dijkstra et al. 1978] 作为诸多插入屏障中的一种， 对于插入到黑色对象中的白色指针，无论其在未来是否会被赋值器删除，该屏障都会将其标记为可达（着色）。 在这种思想下，避免满足条件 1 的出现：
// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot unsafe.Pointer, ptr unsafe.Pointer) {
shade(ptr)
slot = ptr
}
shade(ptr) 会将尚未变成灰色或黑色的指针 ptr 标记为灰色。通过保守的假设 *slot 可能会变为黑色， 并确保 ptr 不会在将赋值为 *slot 前变为白色，进而确保了强三色不变性。图 2 展示了三个对象之间，赋值器和回收器的对 ABC 对象图的操作，赋值器修改 ABC 之间的引用关系，而回收器根据引用关系进一步修改 ABC 各自的颜色。
第四章 4.3 屏障技术 - 图2 图 2: 使用 Dijkstra 写屏障的赋值器
Dijkstra 屏障的优势在于：

  1. 性能优势：它不需要对指针进行任何处理，因为指针的读操作通常比写操作高出一个或更多数量级。
  2. 前进保障：与 Steele 写屏障不同，对象可从白色到灰色单调转换为黑色，因此总工作量受到堆大小的限制。

Dijkstra 写屏障的缺点在于对性能的权衡：
但存在两个缺点：

  • 由于 Dijkstra 插入屏障的保守，在一次回收过程中可能会产生一部分被染黑的垃圾对象，只有在下一个回收过程中才会被回收；

  • 在标记阶段中，每次进行指针赋值操作时，都需要引入写屏障，这无疑会增加大量性能开销，为了避免造成性能问题，可以选择关闭栈上的指针写操作的 Dijkstra 屏障。当发生栈上的写操作时，将栈标记为恒灰（permagrey）的，但此举产生了灰色赋值器，将会需要标记终止阶段 STW 时对这些栈进行重新扫描。

    Dijkstra 屏障的正确性

    TODO: 形式化证明

    黑色赋值器的 Yuasa 删除屏障

    删除屏障（deletion barrier）技术，又称为基于起始快照的屏障（snapshot-at-the-beginning）。 其思想是当赋值器从灰色或白色对象中删除白色指针时，通过写屏障将这一行为通知给并发执行的回收器。 这一过程很像是在操纵对象图之前对图进行了一次快照。
    如果一个指针位于波面之前，则删除屏障会保守地将目标对象标记为非白色存活对象，进而避免条件 2 来满足弱三色不变性。 具体来说，Yuasa 删除屏障 [Yuasa, 1990] 对于在回收过程中，对于被赋值器删除最后一个指向这个对象导致该对象不可达的情况， 仍将其对象进行着色：
    // 黑色赋值器 Yuasa 屏障
    func YuasaWritePointer(slot unsafe.Pointer, ptr unsafe.Pointer) {
    shade(    slot)
    slot = ptr
    }
    为了防止丢失从灰色对象到白色对象的路径，应该假设     slot 可能会变为黑色， 为了确保 ptr 不会在被赋值到 slot 前变为白色，shade(slot) 会先将 slot 标记为灰色， 进而该写操作总是创造了一条灰色到灰色或者灰色到白色对象的路径，进而避免了条件 2。
    Yuasa 删除屏障的优势则在于不需要标记结束阶段的重新扫描， 结束时候能够准确的回收所有需要回收的白色对象。 缺陷是 Yuasa 删除屏障会拦截写操作，进而导致波面的退后，产生冗余的扫描，如图 3 所示。
    第四章 4.3 屏障技术 - 图3 *图 3: 使用 Yuasa 写屏障的赋值器

    Yuasa 屏障的正确性

    TODO: 形式化证明

    进一步阅读的参考文献

  • [Pirinen, 1998] Pekka P. Pirinen. 1998. Barrier techniques for incremental tracing. In Proceedings of the 1st international symposium on Memory management (ISMM ‘98). ACM, New York, NY, USA, 20-25.

  • [Yuasa, 1990] T. Yuasa. 1990. Real-time garbage collection on general-purpose machines. J. Syst. Softw. 11, 3 (March 1990), 181-198.
  • [Wilson, 1992] Raul R. Wilson. 1992. Uniprocessor Garbage Collection Techniques. In Proceedings of the International Workshop on Memory Management (IWMM ‘92), Yves Bekkers and Jaques Cohen (Eds.). Springer-Verlag, London, UK, UK, 1-42.
  • [Dijkstra et al. 1978] Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. 1978. On-the-fly garbage collection: an exercise in cooperation. Commun. ACM 21, 11 (November 1978), 966-975.