Illustration created for “A Journey With Go”, made from the original Go Gopher, created by Renee French

本文基于 Go 1.13。關(guān)于內(nèi)存管理的概念的討論在我的文章 Go 中的內(nèi)存管理和分配[1] 中有詳細(xì)的解釋。

Go GC 的作用是回收不再使用的內(nèi)存。實(shí)現(xiàn)的算法是并發(fā)的三色標(biāo)記和清除回收法。本中文，我們研究三色標(biāo)記法，以及各個(gè)顏色的不同用處。

你可以在 Ken Fox 的 解讀垃圾回收算法[2] 中了解更多關(guān)于不同垃圾回收機(jī)制的信息。

標(biāo)記階段

這個(gè)階段瀏覽內(nèi)存來了解哪些塊兒是在被我們的代碼使用和哪些塊兒應(yīng)該被回收。

然而，因?yàn)?GC 和我們的 Go 程序并行，GC 掃描期間內(nèi)存中某些對(duì)象的狀態(tài)可能被改變，所以需要一個(gè)檢測(cè)這種可能的變化的方法。為了解決這個(gè)潛在的問題，實(shí)現(xiàn)了 寫屏障[3] 算法，GC 可以追蹤到任何的指針修改。使寫屏障生效的唯一條件是短暫終止程序，又名 “Stop the World”。

在進(jìn)程啟動(dòng)時(shí)，Go 也在每個(gè) processor 起了一個(gè)標(biāo)記 worker 來輔助標(biāo)記內(nèi)存。

然后，當(dāng) root 被加入到處理隊(duì)列中后，標(biāo)記階段就開始遍歷和用顏色標(biāo)記內(nèi)存。

為了了解在標(biāo)記階段的每一步，我們來看一個(gè)簡(jiǎn)單的程序示例：

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 不包含指針，因此它被儲(chǔ)存在一個(gè)專門存放不被其他對(duì)象引用的對(duì)象的 span 中。

不包含指針的結(jié)構(gòu)體儲(chǔ)存在專有的 span 中

這減少了 GC 的工作，因?yàn)闃?biāo)記內(nèi)存時(shí)不需要掃描這個(gè) span。

分配工作結(jié)束后，我們的程序強(qiáng)迫 GC 重復(fù)前面的步驟。下面是流程圖：

掃描內(nèi)存

GC 從棧開始，遞歸地順著指針找指針指向的對(duì)象，遍歷內(nèi)存。掃描到被標(biāo)記為 no scan 的 span 時(shí)，停止掃描。然而，這個(gè)工作是在多個(gè)協(xié)程中完成的，每個(gè)指針被加入到一個(gè) work pool 中的隊(duì)列。然后，后臺(tái)運(yùn)行的標(biāo)記 worker 從這個(gè) work pool 中拿到前面出列的 work，掃描這個(gè)對(duì)象然后把在這個(gè)對(duì)象里找到的指針加入到隊(duì)列。

garbage collector work pool

顏色標(biāo)記

worker 需要一種記錄哪些內(nèi)存需要掃描的方法。GC 使用一種 三色標(biāo)記算法[4]，工作流程如下：

• 開始時(shí)，所有對(duì)象都被認(rèn)為是白色
• root 對(duì)象(棧，堆，全局變量)被標(biāo)記為灰色

這個(gè)初始步驟完成后，GC 會(huì)：

• 選擇一個(gè)灰色的對(duì)象，標(biāo)記為黑色
• 追蹤這個(gè)對(duì)象的所有指針，把所有引用的對(duì)象標(biāo)記為灰色

然后，GC 重復(fù)以上兩步，直到?jīng)]有對(duì)象可被標(biāo)記。在這一時(shí)刻，對(duì)象非黑即白，沒有灰色。白色的對(duì)象表示沒有其他對(duì)象引用，可以被回收。

下面是前面例子的圖示：

初始狀態(tài)下，所有的對(duì)象被認(rèn)為是白色的。然后，遍歷到的且被其他對(duì)象引用的對(duì)象，被標(biāo)記為灰色。如果一個(gè)對(duì)象在被標(biāo)記為 no scan 的 span 中，因?yàn)樗恍枰粧呙瑁钥梢詷?biāo)記為黑色。

現(xiàn)在灰色的對(duì)象被加入到掃描隊(duì)列并被標(biāo)記為黑色：

對(duì)加入到掃描隊(duì)列的所有對(duì)象重復(fù)做相同的操作，直到?jīng)]有對(duì)象需要被處理：

處理結(jié)束時(shí)，黑色對(duì)象表示內(nèi)存中在使用的對(duì)象，白色對(duì)象是要被回收的對(duì)象。我們可以看到，由于 struct2 的實(shí)例是在一個(gè)匿名函數(shù)中創(chuàng)建的且不再存在于棧上，因此它是白色的且可以被回收。

歸功于每一個(gè) span 中的名為 gcmarkBits 的 bitmap 屬性，三色被原生地實(shí)現(xiàn)了，bitmap 對(duì) scan 中相應(yīng)的 bit 設(shè)為 1 來追蹤 scan。

我們可以看到，黑色和灰色表示的意義相同。處理的不同之處在于，標(biāo)記為灰色時(shí)是把對(duì)象加入到掃描隊(duì)列，而標(biāo)記為黑色時(shí)，不再掃描。

GC 最終 STW，清除每一次寫屏障對(duì) work pool 做的改變，繼續(xù)后續(xù)的標(biāo)記。

你可以在我的文章 Go GC 怎樣監(jiān)控你的應(yīng)用[5] 中找到關(guān)于并發(fā)處理和 GC 的標(biāo)記階段更詳細(xì)的描述。

runtime 分析器

Go 提供的工具使我們可以對(duì)每一步進(jìn)行可視化，觀察 GC 在我們的程序中的影響。開啟 tracing 運(yùn)行我們的代碼，可以看到前面所有步驟的一個(gè)概覽。下面是追蹤結(jié)果：

traces of the garbage collector

標(biāo)記 worker 的生命周期也可以在追蹤結(jié)果中以協(xié)程等級(jí)可視化。下面是在啟動(dòng)之前先在后臺(tái)等待標(biāo)記內(nèi)存的 Goroutine #33 的例子。

marking worker