走進 golang gc
0。 衝動&經歷&演變
尋找知識最原始的衝動，經歷，演變。。。
——《創刊詞》
記憶體管理的目的是什麼？目的，防止記憶體洩漏；核心點，防止程式沒有可用記憶體，『回收』『不再被引用』的堆記憶體（因為棧記憶體隨時收縮自動釋放）。
那麼接下來就是，如何知道哪些記憶體『不再被引用』？
顯示管理
常見的有 C 語言，寫 C 的人應該都有過記憶體洩漏的噩夢。後來演生出來 C++，雖然繼承了 C 的各種包袱，但盡力透過解構函式、智慧指標、異常機制等等途徑嘗試解決記憶體問題。
引用計數
c++ 的智慧指標便是『引用計數』的思路，如果記憶體增加了新引用，
counter += 1
，同理
counter -= 1
，如果
counter == 0
釋放記憶體。包括，python、php 在內的許多語言都採用此等思路。
引用計數每次指標操作要進行 counter 的維護，如果 counter 變成 0 還要去 free， 容易拖慢
『
工作執行緒
』
。同時，引用計數無法解決
『
迴圈依賴
』
問題，引入程式 OOM 風險，增大編碼工作心智負擔。
標記清除
一個與『引用計數』不同的派系，不透過 counter 維護。使用 GC 執行緒，掃描堆空間的記憶體依賴關係，標記不被依賴的記憶體，回收之。如，java/golang 等
附註：策略優缺對比
可見，引用計數是把依賴關係的維護 & 回收記憶體，
分攤
到了每次操作。工作執行緒
順帶
做了記憶體管理的事。相對而言，標記清除是把 GC 工作完全
託管
給了 GC 執行緒，工作執行緒集中精力做業務邏輯。
引用計數沒有太多延展空間，java/golang 的 GC 走『標記清除』派系。透過細節最佳化，以期拿到最大收益：GC 標記執行緒與工作執行緒協作：加鎖。
如何減少鎖粒度？全域性大鎖（原始的標記清除） => 全域性分階段鎖（golang 1。5 的寫屏障） => 區域性小鎖（golang1。7 的混合屏障）=> 期待更徍
1。 標記清除思路
標記出所有不需要回收的物件，在標記完成後統一回收掉所有未被標記的物件。
細節
以區域性變數、全域性變數等變數為入口，遍歷堆記憶體的依賴關係。生成『堆節點依賴樹』，不在樹上的節點為可回收。
// https：//github。com/golang/go/blob/release-branch。go1。15/src/runtime/mgcmark。go#L60
// gcMarkRootPrepare queues root scanning jobs （stacks， globals， and some miscellany）
// and initializes scanning-related state。
func gcMarkRootPrepare（） {
// Compute how many data and BSS root blocks there are。
nBlocks ：= func（bytes uintptr） int {
return int（divRoundUp（bytes， rootBlockBytes））
}
work。nDataRoots = 0
work。nBSSRoots = 0
// Scan globals。
for _， datap ：= range activeModules（） {
nDataRoots ：= nBlocks（datap。edata - datap。data）
if nDataRoots > work。nDataRoots {
work。nDataRoots = nDataRoots
}
}
。。。。
}
2。 全域性大鎖
遍歷圖生成依賴樹，其準確性依賴於遍歷過程圖不發生變化。最簡單的做法是 Stop The World：透過一把大鎖，這個期間除了 GC 執行緒，其它執行緒全部暫停。
顯而易見，『全域性大鎖』不算一個極佳的方案。STW 導致程式的服務能力突然中止，而這種中止的時長 & 時機又具有不可遇見性。
所以，最佳化的重點就是讓鎖的影響降低……
3。 分階段加鎖
透過細化分析，我們拆成『必 lock』階段 & 『不必 lock』階段。比如：
『無lock』把圖遍歷一遍，同時記錄遍歷期間的 modify
STW， 把 modify 的變數再遍歷一遍
3.1 如何避免 LOCK
遍歷過程中的併發編輯如何處理？
『轉移節點』兩種處理角度：
賦值路徑 hook
在
A。child=B。child
後，將
A。child
標為有用
刪除路徑 hook
在
B。child=NULL
前，將
B。child
標為有用
注：Golang 1。5 使用第一種方案；Golang 1。7 混用兩種方案，以最大化最佳化
路徑 hook 分析
對應於可行的兩種方案：
在所有的『賦值路徑』（不區分轉移/賦值）後，無腦標記『有用』
在所有的『刪除路徑』（不區分轉移/刪除）前，無腦標記『有用』
遍歷結果會遇到兩個問題
錯標：本來還有用的記憶體，被標為無用（必須杜絕）
多標：本來無用的記憶體，被標為了有用（可以接受，比如：刪除了唯一路徑）
可見，透過 hook 的思路，可以『避免 Lock』。但是，真的 ok 嗎？
3.2 Hook 帶來的問題
複雜度
引數壓棧（棧自動釋放），這裡增加大量 hook，直至需要 hook
pop/push/ret
等彙編指令；協程棧 resize 導致轉移，又需要大量 hook…… ！！
效能問題
工作執行緒的『賦值/刪除操作』增加標記邏輯，性質等同於『引用計數』的
counter +/-
且邏輯更復雜。區域性性原理，這種主要影響棧上的操作。
結論，棧上的操作不可以加 Hook，只能作用在堆操作上。
3.3 Dijskra 屏障：Golang1.5 的階段鎖
由上面分析，輕易得出方案思路：
先『無 Lock』 遍歷記憶體依賴圖
遍歷期間透過 『賦值路徑 hook』保證堆上的併發 modify 正確
遍歷期間記錄發生了 modify 的棧
遍歷結束，『加 Lock』，re-scan 發生了 modify 的棧
進一步，由於只有 GC 期間需要 hook：
先 『加 Lock』：標記將要開始 GC
。。。
。。。
。。。
遍歷結束，『加 Lock』：re-scan 發生了 modify 的棧，結束 GC 遍歷
3.4 Yuasa 屏障：階段鎖另一種可行方案
加 Lock
遍歷所有的臨時/全域性等變數，獲取堆依賴圖的『廣度遍歷的初始節點』
標記將要開始 GC
透過 『刪除路徑 hook』 保證堆上的併發 modify 正確
GC 執行緒開始遍歷記憶體依賴圖
遍歷結束，『加 Lock』，取消 GC 遍歷標記
未被選用的原因
相對於『Dijskra 屏障』 沒有明顯優勢
對節點的處理過於悲觀，由『路徑分析』一節可知，併發中被『刪除』『唯一路徑』的節點仍被標為『有用』
4。 區域性小鎖
4.1 進一步思考階段鎖
為什麼
賦值路徑 hook
不像
Yuasa 屏障
起始掃描 STW 掃描棧？
掃描棧收集了『物件 A』但是由於棧上編輯沒有
新增路徑屏障
，物件 B 無法被保護
為什麼
刪除路徑 hook
不像
Dijskra 屏障
結尾 STW 掃描棧？
由於棧上沒有
刪除路徑屏障
，物件 B 無法無法被掃描到
由上面分析可知，屏障只能加在堆上
新增路徑屏障，無法保護『棧上的新增』
刪除路徑屏障，無法保護『棧上的刪除』
4.2 再次分析
『
轉移節點
』
天才，兩個屏障一起用，可以解決堆上所有問題。即可避免 Lock。
4.3 混合屏障
// https：//github。com/golang/proposal/blob/0bdeab75fa2b7e79fc41fd33f269a5ef6d92e407/design/17503-eliminate-rescan。md#alternative-barrier-approaches
writePointer（slot， ptr）：
shade（*slot）
shade（ptr）
*slot = ptr
既然在 『Yuasa 屏障』中，在獲取堆的初始節點後，僅靠『刪除路徑屏障』就可以正常 work。那麼，就沒必要一直『混合屏障』。
// https：//github。com/golang/proposal/blob/0bdeab75fa2b7e79fc41fd33f269a5ef6d92e407/design/17503-eliminate-rescan。md#proposal
writePointer
（
slot
，
ptr
）：
shade
（
*
slot
）
if
any
stack
is
scanning
：
shade
（
ptr
）
*
slot
=
ptr
// 進而演化
writePointer
（
slot
，
ptr
）：
shade
（
*
slot
）
if
current
stack
is
scanning
：
shade
（
ptr
）
*
slot
=
ptr
4.4 棧上的寫怎麼處理
區域性小鎖：鎖住被掃描棧對應的協程
// https：//github。com/golang/go/blame/release-branch。go1。15/src/runtime/mgc。go#L1945
// https：//github。com/golang/go/commit/d6625caf5397a52edc38e19d523a597b531a5f12
systemstack
（
func
（）
{
// 當前棧不被 modify， 保證 scan 是安全的
// We must not modify anything on the G stack。 However， stack shrinking is disabled for mark workers， so it is safe to read from the G stack。
casgstatus
（
gp
，
_Grunning
，
_Gwaiting
）
switch
_p_
。
gcMarkWorkerMode
{
default
：
throw
（
“gcBgMarkWorker： unexpected gcMarkWorkerMode”
）
case
gcMarkWorkerDedicatedMode
：
。。。
4.5 相關原始碼
參考下面程式碼 & 彙編結果
// go build -gcflags “-N -l -m” 。/a。go
package main
type BaseStruct struct {
name string
age int
}
type Tstruct struct {
base *BaseStruct
field0 int
}
func funcAlloc0 （a *Tstruct） {
a。base = new（BaseStruct）
}
func main（） {
a ：= new（Tstruct）
go funcAlloc0（a）
}
（gdb） disassemble
Dump of assembler code for function main。funcAlloc0：
。。。
0x0000000000456b4c <+60>： test %al，（%rdi）
# 這裡判斷是否開啟了屏障（垃圾回收的掃描併發過程，才會把這個標記開啟，沒有開啟的情況，對於堆上的賦值只是多走一次判斷開銷）
0x0000000000456b4e <+62>： cmpl $0x0，0x960fb（%rip） # 0x4ecc50
。。。
# 如果是開啟了屏障，那麼完成 a。base = xxx 的賦值就是在 gcWriteBarrier 函數里面了
0x0000000000456b68 <+88>： callq 0x44d170
。。。。
攢 Buffer
工作執行緒需要把自己標記的『灰色』節點提交給 GC 執行緒，透過 buffer 減少了執行緒通訊的次數
TEXT runtime·gcWriteBarrier
（
SB
）
，NOSPLIT，
$120
。。。
MOVQ R14，
（
p_wbBuf+wbBuf_next
）（
R13
）
# 檢查 buffer 佇列是否滿？
CMPQ R14，
（
p_wbBuf+wbBuf_end
）（
R13
）
# 賦值的前後兩個值都會被入隊
# 把 value 存到指定 buffer 位置
MOVQ AX， -16
（
R14
）
// Record value
# 把 *slot 存到指定 buffer 位置
MOVQ
（
DI
）
， R13
MOVQ R13， -8
（
R14
）
# 如果 wbBuffer 佇列滿了，flush，比如置灰，置黑等操作
JEQ flush
ret：
# 真正的賦值：*slot = val
。。。
RET
flush：
。。。
// 佇列滿了，統一處理，這個其實是一個批次最佳化手段
CALL runtime·wbBufFlush
（
SB
）
。。。
5。 附註
5.1 理論依據
5.1.1 三色不變式
透過不變式約束，保證任何有用的記憶體節點都不會錯標為無用。但不負責無用記憶體多標為有用。
三色標記
廣度遍歷過程中，不同遍歷狀態節點的『助記』標記。
黑色：已經被遍歷過了
灰色：待遍歷節點
白色：未觸及節點
強三色不變式
白色節點不允許存在黑色的上游節點
助解：如果某節點的上游節點已經『掃描結束』（黑色），當前節點至少為『待掃描』狀態（灰色）。
如果黑色節點為白色節點的『唯一』上游，這個節點就會被掃描漏掉。
弱三色不變式
強三色可以不滿足；必須保證一個前提，這個白色物件必須處於灰色物件的保護下。
助解：如果發生『掃描結束』節點變成某節點的上游，至少保證有一個『待掃描』節點為其上游。
只要有灰色節點作為白色節點的上游，這個節點就不會被掃描漏掉。
5.1.2 Dijskra 屏障示意圖（網路盜圖）
5.1.3 Yuasa 屏障示意圖（網路盜圖）
5.1.4 混合屏障示意圖（網路盜圖）
場景一
：物件被一個堆物件刪除引用，成為棧物件的下游
場景二
：物件被一個棧物件刪除引用，成為棧物件的下游
場景三
：物件被一個堆物件刪除引用，成為堆物件的下游
場景四
：物件被一個棧物件刪除引用，成為另一個堆物件的下游
5.2 Golang 的技巧
5.2.1 記憶體管理 BitMap
5.2.2 逃逸分析
為什麼需要了解逃逸分析？因為只有堆上物件的寫才會可能有寫屏障
go build -gcflags “-N -l -m” 。/a。go
在保證程式正確性的前提下，儘可能的把物件分配到棧上，這樣效能最好； 棧上的物件生命週期就跟隨 goroutine ，協程終結了，它就沒了。
5.2.3 禁止跨棧指標
不允許存在跨棧指標，因為當棧空間增長/縮減時，棧的記憶體段可能會變。而且，如果支援跨棧指標，那麼 Runtime 需要單獨維護這些指標，勢必增加 GC 開銷。
5.2.4 GC Assist
當存在新的記憶體分配時，會暫停分配記憶體過快的那些 goroutine，並將其轉去執行一些輔助標記（Mark Assist）的工作，從而達到放緩繼續分配、輔助 GC 的標記工作的目的。
5.3 策略優缺對比
5.3.1 引用計數
優點
直觀，每被引用一次
counter += 1
簡單，無需額外的執行緒（計算資源）、記憶體（儲存資源）去維護複雜的 GC 狀態
及時，一旦沒有使用，最後一個釋放的邏輯相繼釋放記憶體
缺點
影響效率：counter 的
+/-
、
counter=0
的 free，導致『工作執行緒』拖慢計算邏輯
迴圈依賴：記憶體洩漏，進而引入程式 OOM 風險
5.3.2 標記清除
優點
無需維護 counter， 工作執行緒專心工作
透過掃描所有節點的依賴關係，不擔心迴圈依賴引起的記憶體洩漏
缺點
額外的執行緒（計算資源）、記憶體（儲存資源）去維護複雜的 GC 狀態
GC 執行緒不能保證及時回收掉無用資源，導致系統顛簸
GC 執行緒與工作執行緒併發工作，需要一定的鎖機制，嚴重時系統『假死』
6。 參考資料 & 致謝
Golang GC基本原理與最佳化方向
Golang原始碼探索（三） GC的實現原理
golang 垃圾回收（二）屏障技術
Eliminate STW stack re-scanning
7。 尾
大曰逝，逝曰遠，遠曰反
道法術器，溯本歸原，愉悅求知 —— 《DreamService 創刊詞》
