Go GC 怎么標記內存？顏色是什么含義？圖解三色標記法
Illustration created for “A Journey With Go”, made from the original Go Gopher, created by Renee French
本文基于 Go 1.13。關于內存管理的概念的討論在我的文章 Go 中的內存管理和分配[1] 中有詳細的解釋。
Go GC 的作用是回收不再使用的內存。實現的算法是并發的三色標記和清除回收法。本中文，我們研究三色標記法，以及各個顏色的不同用處。
你可以在 Ken Fox 的 解讀垃圾回收算法[2] 中了解更多關于不同垃圾回收機制的信息。
標記階段
這個階段瀏覽內存來了解哪些塊兒是在被我們的代碼使用和哪些塊兒應該被回收。
然而，因為 GC 和我們的 Go 程序并行，GC 掃描期間內存中某些對象的狀態可能被改變，所以需要一個檢測這種可能的變化的方法。為了解決這個潛在的問題，實現了 寫屏障[3] 算法，GC 可以追蹤到任何的指針修改。使寫屏障生效的唯一條件是短暫終止程序，又名 “Stop the World”。
在進程啟動時，Go 也在每個 processor 起了一個標記 worker 來輔助標記內存。
然后，當 root 被加入到處理隊列中后，標記階段就開始遍歷和用顏色標記內存。
為了了解在標記階段的每一步，我們來看一個簡單的程序示例：
- type struct1 struct {
- a, b int64
- c, d float64
- e *struct2
- }
- type struct2 struct {
- f, g int64
- h, i float64
- }
- func main() {
- s1 := allocStruct1()
- s2 := allocStruct2()
- func () {
- _ = allocStruct2()
- }()
- runtime.GC()
- fmt.Printf("s1 = %X, s2 = %X\n", &s1, &s2)
- }
- //go:noinline
- func allocStruct1() *struct1 {
- return &struct1{
- e: allocStruct2(),
- }
- }
- //go:noinline
- func allocStruct2() *struct2 {
- return &struct2{}
- }
struct2 不包含指針，因此它被儲存在一個專門存放不被其他對象引用的對象的 span 中。
不包含指針的結構體儲存在專有的 span 中
這減少了 GC 的工作，因為標記內存時不需要掃描這個 span。
分配工作結束后，我們的程序強迫 GC 重復前面的步驟。下面是流程圖：
掃描內存
GC 從棧開始，遞歸地順著指針找指針指向的對象，遍歷內存。掃描到被標記為 no scan 的 span 時，停止掃描。然而，這個工作是在多個協程中完成的，每個指針被加入到一個 work pool 中的隊列。然后，后臺運行的標記 worker 從這個 work pool 中拿到前面出列的 work，掃描這個對象然后把在這個對象里找到的指針加入到隊列。
garbage collector work pool
顏色標記
worker 需要一種記錄哪些內存需要掃描的方法。GC 使用一種 三色標記算法[4]，工作流程如下：
- 開始時，所有對象都被認為是白色
- root 對象(棧，堆，全局變量)被標記為灰色
這個初始步驟完成后，GC 會：
- 選擇一個灰色的對象，標記為黑色
- 追蹤這個對象的所有指針，把所有引用的對象標記為灰色
然后，GC 重復以上兩步，直到沒有對象可被標記。在這一時刻，對象非黑即白，沒有灰色。白色的對象表示沒有其他對象引用，可以被回收。
下面是前面例子的圖示：
初始狀態下，所有的對象被認為是白色的。然后，遍歷到的且被其他對象引用的對象，被標記為灰色。如果一個對象在被標記為 no scan 的 span 中，因為它不需要被掃描，所以可以標記為黑色。
現在灰色的對象被加入到掃描隊列并被標記為黑色：
對加入到掃描隊列的所有對象重復做相同的操作，直到沒有對象需要被處理：
處理結束時，黑色對象表示內存中在使用的對象，白色對象是要被回收的對象。我們可以看到，由于 struct2 的實例是在一個匿名函數中創建的且不再存在于棧上，因此它是白色的且可以被回收。
歸功于每一個 span 中的名為 gcmarkBits 的 bitmap 屬性，三色被原生地實現了，bitmap 對 scan 中相應的 bit 設為 1 來追蹤 scan。
我們可以看到，黑色和灰色表示的意義相同。處理的不同之處在于，標記為灰色時是把對象加入到掃描隊列，而標記為黑色時，不再掃描。
GC 最終 STW，清除每一次寫屏障對 work pool 做的改變，繼續后續的標記。
你可以在我的文章 Go GC 怎樣監控你的應用[5] 中找到關于并發處理和 GC 的標記階段更詳細的描述。
runtime 分析器
Go 提供的工具使我們可以對每一步進行可視化，觀察 GC 在我們的程序中的影響。開啟 tracing 運行我們的代碼，可以看到前面所有步驟的一個概覽。下面是追蹤結果：
traces of the garbage collector
標記 worker 的生命周期也可以在追蹤結果中以協程等級可視化。下面是在啟動之前先在后臺等待標記內存的 Goroutine #33 的例子。
marking worker
