GO 語言學習筆記: 垃圾回收機制剖析

一、引言

（一）垃圾回收 概述

垃圾回收（Garbage Collection，GC） 是 Go 語言的核心特性之一，是實現內存自動管理的一種形式。golang 的自動垃圾回收屏蔽了複雜且容易出錯的內存操作，讓開發變得更加簡單、高效。在 Go 語言中，從實現機制上來說，垃圾回收可能是最複雜的模塊了。瞭解垃圾回收的機制，有助於更好地理解 Go 語言的內存管理機制，從而更好的使用 Go 語言進行開發。

（二）垃圾回收相關組件

使用自帶垃圾回收特性的編程語言開發應用程序中，垃圾回收涉及到一下三個組件：

二、標記 - 清除 算法

Go 語言使用標記 - 清除（Mark-Sweep）算法來進行內存垃圾回收。（關於其他經典的垃圾回收算法，參考本文 <相關知識> 一節。Mark-Sweep 算法執行過程可以分成標記（Mark）和清除（Sweep）兩個階段：

什麼是根對象？

根對象主要是指應用程序中通過變量可以直接訪問的對象。

如圖所示，假設應用程序在堆上申請了 A-J 共 10 個內存對象。其中可以被程序中的變量直接訪問的只有對象 A 和 B（分別被變量 a、b 直接訪問），因此根對象只有 A 和 B。其他內存對象都是間接訪問，不是根對象。

a = &A
b = &B
a.f1 : &C
a.f2 : &D
a.f1.f1 : &F
a.f1.f2 : &G
a.f1.f3 : &H
b.f1 : &E
b.f1.f1 : &I
// 其他爲列出的成員字段的值均爲空

圖中因爲所有的對象都可以通過根對象訪問到，因此沒有內存對象要回收。

如果應用程序之後將對象 C 成員對 H 的引用去除，a.f1.f3 = nil,

此時 H 對象變爲從根對象不可達的待回收對象。

以上 就是'標記 - 清除'算法的主要過程。

三、三色標記法

（一）原始 <標記 - 清除> 算法的不足

原始的 Mark-Sweep 算法流程上相對簡單，但是在實際應用中有一定的限制條件。在垃圾回收的整個過程中，如果應用程序併發進行內存相關操作，可能導致活躍對象被錯誤回收。

如上圖所示，在標記階段根對象 A 做 DFS 遍歷完成後，Mutator 併發修改了對內存對象 D 的引用關係（增加了 A 對象對 D 對象的引用，刪除了 B 對象對 D 對象的引用），然後 Collector 在對根對象 B 做 DFS 遍歷。最終導致的結果是，從根對象 A 可以到達對象 D（即 D 是活躍的），但是標記結果顯示對象 D 是可以被回收的內存對象，從而錯誤釋放了對象 D 的內存。

在原始 <標記 - 清除> 算法中，要保證活躍對象不被被錯誤回收，需要滿足以下必要條件：**活躍白色對象必須從白色的根對象可達。**這個條件在併發和增量執行的過程中其實是很難保證的，因而：原始的 Mark-Sweep 算法會在垃圾回收階段 Stop-The-World，不支持併發和增量執行

Go 語言使用三色標記法和屏障技術來支持併發和增量執行。

（二）三色標記法

三色標記算法將所有的內存對象抽象爲黑、白、灰三類。

三色標記法的基本過程

  1. 垃圾回收開始前，所有的內存對象都是白色；

  2. 垃圾回收開始時，所有根對象被標記會灰色；

  3. 從灰色對象集合，選取一個灰色對象，將其下游白色對象置灰，將自己置爲黑色；

  4. 重複第 3 步驟，直至灰色對象集合爲空。

三色標記法只能由白->灰->黑單調變色

用三色波面圖來描述：

**三色標記法本身仍然不能保證併發和增量執行的正確性。**在併發和增量執行的場景下，

活躍對象（白色）被錯誤回收的必要條件：

  1. 不存在從灰色對象到達該白色對象的路徑。（該白色對象在標記階段不會再被掃描到）

  2. 存在從黑色對象到達該白色對象的路徑。（否則結合 1 的話，該白色對象本來就是一個需要被回收的垃圾對象）

但是三色標記法讓併發和增量執行的實現變得容易。回到 <標記 - 清除> 中的異常例子。

因爲活躍對象（白色）被錯誤回收的兩個條件都是必要條件，要保證活躍對象都被發現，我們可以兩個條件都破壞，也可以只破壞一個條件。由此，就衍生了兩種三色不變性：

Go 語言的三色不變性通過引入屏障技術來實現。

標記 - 清除>算法和 <三色標記法> 本身都不能保證在併發和增量執行的場景下垃圾回收的正確性，那麼引入<三色標記法> 的優勢是什麼，我們還需要結合屏障技術來看。（參考插入寫屏障最後的對比）

四、屏障技術

內存屏障技術是一種 CPU 屏障指令，用於讓 CPU 和編譯器對屏障指令前後的內存操作的執行順序進行強制約束。現在處理器爲了優化性能，經常會改變程序指令的執行順序，而內存屏障技術則是用來對一些內存操作的執行順序進行強制約束。內存屏障指令前的內存操作一定會在內存屏障指令後的操作之前執行。

內存屏障技術本身並不能用來保證三色不變性。但是我們可以利用內存屏障技術在內存操作之前執行特定的（用於保護三色不變性）的指令（執行特定代碼）（就像 Hook 一樣）。

（一）哪些內存操作適合啓用寫屏障

我們可以吧內存操作分爲以下幾種：

  1. 堆對象的讀：

  2. 堆對象的寫：

  3. 棧對象的讀：

  4. 棧對象的寫：

所有對象的讀對性能都有比較高的性能要求；棧對象的讀寫一方面對性能要求高，一方面棧對象啓用寫屏障的實現難度較大。因而在 Go 語言語境下，只對堆對象的寫啓用寫屏障。

（二）插入寫屏障

插入寫屏障由 Dijkstra 1978 年在《An exercise in cooperation. Communications of the ACM, 21(11), 966–975, 1978.》提出，可以用來保證內存對象的強三色不變性。

插入寫屏障的基本含義：當 Mutator 在增加一個內存對象 A 到另一個內存對象 B 的指向時（在有向圖中增加 A->B 這條邊），引入內存屏障，將內存對象 B 置灰。

插入寫屏障可以用下面的僞代碼表示：

// DijkstraWritePointer : 插入寫屏障
// @param slot ： 上游對象中用來指向下游對象的插槽，比如c.f1=&d, 則slog爲&c.f1
// @param ptr  ： 下游對象的地址，
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr)   // 着色，置灰
    *slot = ptr  // 讓slot對應的上游對象中增加對ptr對應的下游對象的引用。
}

我們看下插入寫屏障如何保證強三色不變性：

先假設棧對象也開啓了寫屏障

仍然以前面的例子來說明：

當插入 C->D 這條邊時，觸發插入寫屏障。

用僞代碼描述的話，大概是這樣子：沒有插入寫屏障時，Mutator 原本增加 C->D:

    c.f1 = &d

引入插入寫屏障後,

    DijkstraWritePointer(&c.f1, &d)

插入寫屏障因爲在新增對象引用時，直接把被引用的對象置灰；因此不會存在黑色對象直接指向白色對象的情況，而且被應用對象及其下游對象通過灰色對象必然可達（因爲被引用本身就是灰色對象）

再引入棧對象不啓用寫屏障這一限制條件：

對於插入寫屏障算法來說，如果棧對象不開啓插入寫屏障，在回收過程中，如果把一個對象插入到棧對象（黑色）的下游，則可能不會被發現，最終導致被錯誤回收。

如圖，增加 A->B,A->D 兩條邊的時候都不會觸發插入寫屏障

Go 語言早期的做法是，標記階段結束後，STW，重新掃描一遍棧對象（此處 STW 佔用大概 10ms-100ms）。對於棧空間 STW 期間的掃描標記，只需要將被棧對象直接引用的堆空間對象直接置黑（不需要置灰），因爲其下游子對象是通過寫屏障處理的。

對比三色標記和原始的標記清除算法

在原始的 <標記 - 清除> 算法中，使用新增黑色對象對白色對象的引用時，將白色對象置爲黑色（需要先遞歸處理白色對象的下游），也能避免活躍內存對象被錯誤回收。

（三）刪除寫屏障

刪除寫屏障有 Yuasa 在 1990 年的論文 Real-time garbage collection on general-purpose machines 提出。

刪除寫屏障的基本含義：當 Mutator 在刪除一個內存對象 A 到另一個內存對象 B 的指向時（在有向圖中刪除 A->B 這條邊），引入內存屏障，將內存對象 B 置灰。

插入寫屏障可以用下面的僞代碼表示：

// YuasaWritePointer : 刪除寫屏障
// @param slot ： 上游對象中用來指向下游對象的插槽，比如a.f1=&d, 則slog爲&a.f1
// @param ptr  ： 下游對象的地址，比如a.f1=&d, 則ptr爲&d. ptr 可能爲nil
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(*slot) // 着色，把插槽原來指向的對象置灰（注意這裏是*slot，不是slot）
    *slot = ptr  // 插槽指向新的對象，也可能指向nil
}

我們看下刪除寫屏障如何保證弱三色不變性：

先假設棧對象也開啓了寫屏障

仍然以前面的例子來說明：

當刪除 B->D 這條邊時，觸發刪除寫屏障。

用僞代碼描述的話，大概是這樣子：沒有刪除寫屏障時，Mutator 原本刪除 B->D:

    b.f1 = nil

引入刪除寫屏障後,

    YuasaWritePointer(&b.f1, nil)

刪除寫屏障因爲在刪除對象引用關係時，將原來的被引用對象置灰，即直接創造了一條到達被引用對象（包括其下游對象）的路徑，因而破壞了'不存在從灰色對象到達該白色對象的路徑。'這個條件。實現了弱三色不變性。

再引入棧對象不啓用寫屏障這一限制條件：

對於刪除寫屏障算法來說，如果棧對象不開啓插入寫屏障，在回收過程中，如果把一個對象從棧對象直接下游移動到其他對象（黑色對象）直接下游，則可能不會被發現，最終導致被錯誤回收。

上圖中，因爲 C 屬於棧對象，因此在刪除 C->D 時，不會觸發刪除寫屏障。爲了解決這個問題，要求刪除寫屏障掃描棧對象必須 STW。刪除寫屏障在棧掃描時的 STW 必須是全局的，我們可以結合具體的場景來分析：STW 主要是爲了規避兩種場景的錯誤回收：

  1. 將堆對象從一個棧對象下游移動到一個黑色的棧對象下游。

  2. 將堆對象從一個棧對象下游移動到一個黑色堆對象下游。

第一種場景只會在一個 goroutine 下出現（goroutine 有獨立棧） 第二種場景可以發生不同 goroutine。

只在 goroutine 維度 STW 無法保證第二種場景垃圾回收能正確回收。

（四）混合寫屏障

插入寫屏障和刪除寫屏障針對棧對象不開啓寫屏障的限制條件都有了解決方案，都能夠滿足三色不變性。但是他們也有各自的短板：

引入混合寫屏障的設計目標，主要是要補齊插入 / 刪除寫屏障中的 STW 短板。其設計思想是：在刪除寫屏障的基礎上，引入插入寫屏障，從而實現刪除寫屏障的全局 STW 進化爲 goroutine 維度的 STW。（但是 Go 語言的演進是從插入寫屏障 -> 混合寫屏障，很多網上文章的描述反而不好理解）

// 混合寫屏障僞代碼
func HybridWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
 shade(*slot) // 刪除寫屏障
 shade(ptr)   // 插入寫屏障
 *slot = ptr
}

在刪除寫屏障中，我們已經列舉了需要 STW 進行棧掃描的場景。

  1. 將堆對象從一個棧對象下游移動到一個黑色的棧對象下游。

  2. 將堆對象從一個棧對象下游移動到一個黑色堆對象下游。

第一種場景是在同一個 goroutine 進行的， 第二種場景，因爲是將棧對象下游移動到黑色的堆對象下游，如果我們對堆對象開啓插入寫屏障，就可以保證對象不被錯誤回收。從而實現了在混合寫屏障下，只需要做 goroutine 的 STW。

五、相關知識

五種經典的垃圾回收算法

Go 語言底層原理剖析中介紹了五種經典的垃圾回收算法。1. 標記 - 清除： 兩階段，第一階段標記存活的內存對象，第二階段清掃未被標記的對象。2. 標記 - 壓縮： 通過將分散的、活着的對象移動到更緊密的空間來解決內存碎片問題。也是兩階段，第一階段掃描存活的內存對象，並將其壓縮到空閒的區域，3. 半空間複製： '標記 - 壓縮'的演化版本，保留一半空間用於壓縮，通過空間換時間，犧牲一半內存空間換取壓縮的效率提升。4. 引用計數： 每個對象都包含一個引用計數，每當其他對象引用了此對象時，引用計數就會增加。每個對象都包含一個引用計數，每當其他對象引用了此對象時，引用計數就會增加。5. 分代 GC： 將對象按照存活時間進行劃分。優先回收剛創建不久的對象。

六、參考文獻

  1. 《Go 語言底層原理剖析》第 19、20 章

  2. Go 語言設計與實現 --7.2 垃圾收集器

  3. Mark-and-Sweep: Garbage Collection Algorithm

  4. Tri-color marking

  5. Barrier techniques for incremental tracing

  6. wikipedia:

  7. On-the-fly garbage collection: an exercise in cooperation.

  8. Real-time garbage collection on general-purpose machines

  9. Golang 三色標記 + 混合寫屏障 GC 模式全分析

  10. golang 垃圾回收（五）混合寫屏障

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/unea4yejRkZ7zuiHItm2-Q

猜你喜歡