# 8.2 寫屏障技術 屏障技術在本書指內存屏障（Memory Barrier）。 它保障了代碼描述中對內存的操作順序**既不會在編譯期被編譯器進行調整，也不會在運行時被 CPU 的亂序執行所打亂**， 是一種語言與語言用戶間的契約。 ## 8.2.1 并行標記清理產生的問題 在沒有用戶態代碼并發修改三色抽象的情況下，回收可以正常結束。但并發回收的根本問題在于， 用戶態代碼在回收過程中會并發的更新對象圖，從而賦值器和回收器可能對對象圖的結構產生不同的認知， 這時以一個固定的三色波面作為回收過程前進的邊界則不再合理。 我們不妨考慮賦值器的寫操作，假設某個灰色對象 A 指向白色對象 B， 而此時賦值器并發的將黑色對象 C 指向（ref3）了白色對象 B， 并將灰色對象 A 對白色對象 B 的引用移除（ref2），則在繼續掃描的過程中， 白色對象 B 永遠不會被標記為黑色對象了（回收器不會重新掃描黑色對象）。 進而產生被錯誤回收的對象 B，如圖 1 所示。 **圖 1: 回收器正確性的破壞** ## 8.2.2 弱三色不變性 垃圾回收器的正確性體現在：不應出現對象的丟失，也不應錯誤的回收還不需要回收的對象。 作為內存屏障的一種，寫屏障（Write Barrier）是一個在并發垃圾回收器中才會出現的概念。 可以證明，當以下兩個條件同時滿足時會破壞垃圾回收器的正確性 \[Wilson, 1992\]： * 條件 1: 賦值器修改對象圖，導致某一黑色對象引用白色對象； * 條件 2: 從灰色對象出發，到達白色對象的、未經訪問過的路徑被賦值器破壞。 只要能夠避免其中任何一個條件，則不會出現對象丟失的情況，因為： * 如果條件 1 被避免，則所有白色對象均被灰色對象引用，沒有白色對象會被遺漏； * 如果條件 2 被避免，即便白色對象的指針被寫入到黑色對象中，但從灰色對象出發，總存在一條沒有訪問過的路徑，從而找到到達白色對象的路徑，白色對象最終不會被遺漏。 我們不妨將三色不變性所定義的波面根據這兩個條件進行削弱： * 當滿足原有的三色不變性定義（或上面的兩個條件都不滿足時）的情況稱為強三色不變性（strong tricolor invariant） * 當賦值器令黑色對象引用白色對象時（滿足條件 1 時）的情況稱為弱三色不變性（weak tricolor invariant） 當賦值器進一步破壞灰色對象到達白色對象的路徑時（進一步滿足條件 2 時），即打破弱三色不變性， 也就破壞了回收器的正確性；或者說，在破壞強弱三色不變性時必須引入額外的輔助操作。 弱三色不變形的好處在于：**只要存在未訪問的能夠到達白色對象的路徑，就可以將黑色對象指向白色對象。** ### 8.2.3 賦值器的顏色 如果我們考慮并發的用戶態代碼，回收器不允許同時停止所有賦值器， 就是涉及了存在的多個不同狀態的賦值器。為了對概念加以明確，還需要換一個角度， 把回收器視為對象，把賦值器視為影響回收器這一對象的實際行為（即影響 GC 周期的長短）， 從而引入賦值器的顏色： * 黑色賦值器：已經由回收器掃描過，不會再次對其進行掃描。 * 灰色賦值器：尚未被回收器掃描過，或盡管已經掃描過但仍需要重新掃描。 賦值器的顏色對回收周期的結束產生影響： 如果某種并發回收器允許灰色賦值器的存在，則必須在回收結束之前重新掃描對象圖。 如果重新掃描過程中發現了新的灰色或白色對象，回收器還需要對新發現的對象進行追蹤， 但是在新追蹤的過程中，賦值器仍然可能在其根中插入新的非黑色的引用，如此往復， 直到重新掃描過程中沒有發現新的白色或灰色對象。 于是，在允許灰色賦值器存在的算法，最壞的情況下， 回收器只能將所有賦值器線程停止才能完成其跟對象的完整掃描，也就是我們所說的 STW。 ### 8.2.4 新分配對象的顏色 新的分配過程會導致賦值器持有新分配對象的引用。可想而知我們需要為新產生的對象分配適當的顏色。 可想而知，新分配對象的顏色會產生不同的影響： 1. 如果新分配的對象為黑色或者灰色，則賦值器直接將其視為無需回收的對象，寫入堆中； 2. 如果新分配的對象為白色，則可以避免無意義的新對象保留到下一個垃圾回收的周期。 如果我們進一步思考，則能夠發現，由于黑色賦值器由于已經被回收器掃描過， 不會再對其進行任何掃描，一旦其分配新的白色對象 則意味著會導致錯誤的回收。因此黑色賦值器不能產生白色對象， 除非賦值器能夠保證分配的白色對象的引用能夠被寫入到灰色波面中， 但這實踐起來并不容易。不難看出，為了簡化實現復雜度，**令新分配的對象為黑色通常是安全的。** ## 8.2.5 賦值器屏障技術 我們在談論垃圾回收器的寫屏障時，其實是指賦值器的寫屏障，即**賦值器屏障**。 賦值器屏障作為一種同步機制，使賦值器在進行指針寫操作時，能夠“通知”回收器，進而不會破壞弱三色不變性。 屏障上需要依賴多種操作來應對指針的插入和刪除 \[Pirinen, 1998\]： * 擴大波面：將白色對象作色成灰色 * 推進波面：掃描對象并將其著色為黑色 * 后退波面：將黑色對象回退到灰色 根據灰色賦值器和黑色賦值器的不同，分別會有不同類別的賦值器屏障。我們針對兩種不同 類型的賦值器來分別介紹兩個與 Go 有關的賦值器屏障： 灰色賦值器的 Dijkstra 插入屏障與黑色賦值器的 Yuasa 刪除屏障。 ### 灰色賦值器的 Dijkstra 插入屏障 **插入屏障（insertion barrier）技術**，又稱為**增量更新屏障（incremental update）**\[Wilson, 1992\] 。 其核心思想是把賦值器對已存活的對象集合的插入行為通知給回收器，進而產生可能需要額外（重新）掃描的對象。 如果某一對象的引用被插入到已經被標記為黑色的對象中，這類屏障會**保守地**將其作為非白色存活對象， 以滿足強三色不變性。 Dijkstra 插入屏障 \[Dijkstra et al. 1978\] 作為諸多插入屏障中的一種， 對于插入到黑色對象中的白色指針，無論其在未來是否會被賦值器刪除，該屏障都會將其標記為可達（著色）。 在這種思想下，避免滿足條件 1 的出現： 1 2 3 4 5 // 灰色賦值器 Dijkstra 插入屏障 func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) { shade(ptr) *slot = ptr } `shade(ptr)`會將尚未變成灰色或黑色的指針`ptr`標記為灰色。通過保守的假設`*slot`可能會變為黑色， 并確保`ptr`不會在將賦值為`*slot`前變為白色，進而確保了強三色不變性。圖 2 展示了三個對象之間，賦值器和回收器的對 ABC 對象圖的操作，賦值器修改 ABC 之間的引用關系，而回收器根據引用關系進一步修改 ABC 各自的顏色。 **圖 2: 使用 Dijkstra 寫屏障的賦值器** Dijkstra 屏障的優勢在于： 1. 性能優勢：它不需要對指針進行任何處理，因為指針的讀操作通常比寫操作高出一個或更多數量級。 2. 前進保障：與 Steele 寫屏障不同，對象可從白色到灰色單調轉換為黑色，因此總工作量受到堆大小的限制。 Dijkstra 寫屏障的缺點在于對性能的權衡： 但存在兩個缺點： * 由于 Dijkstra 插入屏障的保守，在一次回收過程中可能會產生一部分被染黑的垃圾對象，只有在下一個回收過程中才會被回收； * 在標記階段中，每次進行指針賦值操作時，都需要引入寫屏障，這無疑會增加大量性能開銷，為了避免造成性能問題，可以選擇關閉棧上的指針寫操作的 Dijkstra 屏障。當發生棧上的寫操作時，將棧標記為恒灰（permagrey）的，但此舉產生了灰色賦值器，將會需要標記終止階段 STW 時對這些棧進行重新掃描。 ### Dijkstra 屏障的正確性 TODO: 形式化證明 ### 黑色賦值器的 Yuasa 刪除屏障 **刪除屏障（deletion barrier）技術**，又稱為**基于起始快照的屏障（snapshot-at-the-beginning）**。 其思想是當賦值器從灰色或白色對象中刪除白色指針時，通過寫屏障將這一行為通知給并發執行的回收器。 這一過程很像是在操縱對象圖之前對圖進行了一次快照。 如果一個指針位于波面之前，則刪除屏障會保守地將目標對象標記為非白色存活對象，進而避免條件 2 來滿足弱三色不變性。 具體來說，Yuasa 刪除屏障 \[Yuasa, 1990\] 在回收過程中，對于被賦值器刪除最后一個指向這個對象導致該對象不可達的情況， 仍將其對象進行著色： 1 2 3 4 5 // 黑色賦值器 Yuasa 屏障 func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) { shade(*slot) *slot = ptr } 為了防止丟失從灰色對象到白色對象的路徑，應該假設 \*slot 可能會變為黑色， 為了確保 ptr 不會在被賦值到 \*slot 前變為白色，shade(\*slot) 會先將 \*slot 標記為灰色， 進而該寫操作總是創造了一條灰色到灰色或者灰色到白色對象的路徑，進而避免了條件 2。 Yuasa 刪除屏障的優勢則在于不需要標記結束階段的重新掃描， 結束時候能夠準確的回收所有需要回收的白色對象。 缺陷是 Yuasa 刪除屏障會攔截寫操作，進而導致波面的退后，產生冗余的掃描，如圖 3 所示。 **圖 3: 使用 Yuasa 寫屏障的賦值器** ### Yuasa 屏障的正確性 TODO: 形式化證明 ## 混合寫屏障 在諸多屏障技術中，Go 使用了 Dijkstra 與 Yuasa 屏障的結合， 即**混合寫屏障（Hybrid write barrier）技術**\[Clements and Hudson, 2016\]。 Go 在 1.8 的時候為了簡化 GC 的流程，同時減少標記終止階段的重掃成本， 將 Dijkstra 插入屏障和 Yuasa 刪除屏障進行混合，形成混合寫屏障，沿用至今。 ## 基本思想 該屏障提出時的基本思想是：對正在被覆蓋的對象進行著色，且如果當前棧未掃描完成， 則同樣對指針進行著色。 但在最終實現時原提案 \[Clements and Hudson, 2016\] 中對 ptr 的著色還額外包含 對執行棧的著色檢查，但由于時間有限，并未完整實現過，所以混合寫屏障在目前的實現是： ``` // 混合寫屏障 func HybridWritePointerSimple(slot *unsafe.Pointer, ptr unsafe.Pointer) { shade(*slot) shade(ptr) *slot = ptr } ``` 在 Go 1.8 之前，為了減少寫屏障的成本，Go 選擇沒有啟用棧上寫操作的寫屏障， 賦值器總是可以通過將一個單一的指針移動到某個已經被掃描后的棧， 從而導致某個白色對象被標記為灰色進而隱藏到黑色對象之下，進而需要對棧的重新掃描， 甚至導致棧總是灰色的，因此需要 STW。 混合寫屏障為了消除棧的重掃過程，因為一旦棧被掃描變為黑色，則它會繼續保持黑色， 并要求將對象分配為黑色。 混合寫屏障等同于 IBM 實時 JAVA 實現中使用的 Metronome 中使用的雙重寫屏障。 這種情況下，垃圾回收器是增量而非并發的，但最終必須處理嚴格限制的世界時間的相同問題。 ## 混合寫屏障的正確性 直覺上來說，混合寫屏障是可靠的。那么當我們需要在數學上邏輯的證明某個屏障是正確的，應該如何進行呢？ TODO：補充正確性證明的基本思想和此屏障的正確性證明 ## 實現細節 TODO: ## 批量寫屏障緩存 在這個 Go 1.8 的實現中，如果無條件對引用雙方進行著色，自然結合了 Dijkstra 和 Yuasa 寫屏障的優勢， 但缺點也非常明顯，因為著色成本是雙倍的，而且編譯器需要插入的代碼也成倍增加， 隨之帶來的結果就是編譯后的二進制文件大小也進一步增加。為了針對寫屏障的性能進行優化， Go 1.10 和 Go 1.11 中，Go 實現了批量寫屏障機制。 其基本想法是將需要著色的指針統一寫入一個緩存， 每當緩存滿時統一對緩存中的所有 ptr 指針進行著色。 TODO: ## 小結 并發回收的屏障技術歸根結底就是在利用內存寫屏障來保證強三色不變性和弱三色不變性。 早期的 Go 團隊實踐中選擇了從提出較早的 Dijkstra 插入屏障出發， 不可避免的在為了保證強三色不變性的情況下，需要對棧進行重掃。 而在后期的實踐中，Go 團隊提出了將 Dijkstra 和 Yuasa 屏障結合的混合屏障， 將強三色不變性進行了弱化，從而消除了對棧的重新掃描這一硬性要求，使得在未來實現全面并發 GC 成為可能。