GC掃描棧

問題的關(guān)鍵在于這段代碼：

t?:=?T{...}
p?:=?&t
for?{
???if?…?{?p?=?…?}
}

編譯器決定在棧上分配 T鳄炉，并且因?yàn)榫幾g器無法跟蹤其地址結(jié)束的位置杜耙，所以編譯器保守地決定 t 始終是存活的。

但是在 for 循環(huán)中拂盯，當(dāng) p 被賦值時(shí)泥技，t 變成死亡的。
所以在 p 被重新分配之后磕仅，t 中的任何指針都可能保持一個(gè)它不應(yīng)該保持的對象存活。

我們將在棧上調(diào)用其地址被 “棧對象” 占用的變量簸呈，目標(biāo)是僅在棧對象中的數(shù)據(jù)真實(shí)存活時(shí)掃描棧對象榕订，即如果對象再次直接引用（如，t.x）或間接引用（如蜕便，p.x）劫恒。

我們開始像往常一樣掃描一個(gè)棧，從最低（最新）的棧幀開始轿腺，一直向上两嘴。
我們使用指針位圖來查找每個(gè)棧幀中的所有存活的指針。
通常族壳，棧對象的指針不會標(biāo)記為存活（但請參見下文）憔辫。
所有指向堆的指針都像往常一樣被標(biāo)記，任何指向棧的指針都被忽略(目前)仿荆。
對于遇到的每一幀贰您，我們查看該幀是否有棧對象。
對于該幀中的每個(gè)棧對象拢操，我們將其添加到棧對象列表中锦亦。

如果我們到達(dá)棧頂部并找不到棧對象，那么就結(jié)束了令境。

如果我們確實(shí)找到了一些棧對象杠园，我們必須再次掃描棧。

首先舔庶，我們將棧對象組織成一個(gè)數(shù)據(jù)結(jié)構(gòu)抛蚁，該結(jié)構(gòu)提供按地址快速查找的功能陈醒，可能是一個(gè)二叉樹。由于我們可以按地址順序枚舉棧對象篮绿，所以應(yīng)該很容易使用它們的地址作為 key 來生成二叉樹（在 O(n) 時(shí)間內(nèi)）孵延。

然后我們再次掃描棧，只查找指向棧的指針亲配。
對于任何這樣的指針尘应，我們在二叉樹中查找它們，看看它們是否指向任何棧對象吼虎。
如果是犬钢，我們將棧對象標(biāo)記為存活（如果我們還沒有這樣做），并將其放入正在掃描的工作列表中思灰。當(dāng)我們完成棧掃描時(shí)玷犹，我們現(xiàn)在在工作列表中有了棧對象的根集（root set）。
然后洒疚，我們不斷從工作列表中彈出一個(gè)對象并掃描它（可能將堆對象或其他棧對象標(biāo)記為存活）歹颓，直到工作列表為空。

我們可以為每個(gè)棧對象分配相鄰的空間來使用這個(gè)算法油湖。我們稱之為棧對象“header”巍扛。
header 可能包含二叉樹的左右指針，一個(gè)標(biāo)記位和用于單鏈表工作隊(duì)列的指針乏德。
header 有一些空間開銷撤奸，但是它應(yīng)該很小，并且可以自由分配喊括，因?yàn)樗皇鞘箺笠稽c(diǎn)胧瓜。
header 只需要在第一次掃描是找到棧對象時(shí)才初始化。因此我們可以在正常執(zhí)行期間將垃圾留在那里郑什。

記錄棧對象

我們在funcdata中為函數(shù)保留了一個(gè)額外的映射府喳，該函數(shù)包含幀中每個(gè)棧對象的幀偏移，大小和指針映射的列表蹦误。

請注意劫拢，只需要記錄具有指針的棧對象。

_FUNCDATA_StackObjects?=?4

堆棧對象相對較少强胰，因此棧對象數(shù)據(jù)的編碼不是很關(guān)鍵舱沧。
我們可以像這樣編碼棧對象funcdata：

（偏移大小（isptr）*）*

其中偶洋，每個(gè)對象在幀中編碼它的起始偏移量熟吏、它的大小以及該對象中每個(gè)指針 slot 的size/ptrSize 0/1項(xiàng)。

含糊不清的存活對象（ambiguously live objects）

有了這種新機(jī)制，我們就可以在當(dāng)前編譯器中為含糊不清的存活對象去掉所有代碼牵寺。
我們只需要在存活的 ptr 位圖中標(biāo)記那些通過直接訪問（而不是通過指針）存活的指針悍引。
我們的新機(jī)制包含以前用于跟蹤棧對象的邏輯，該邏輯是：存活只是因?yàn)橹赶蛩鼈兊闹羔樋赡苁谴婊畹摹?/p>

其他說明

對象可以作為棧對象被列出帽氓，并在存活的 ptr 位圖中被標(biāo)記趣斤。
例如：

t?:=?T{}
p?:=?&t
f()
println(t.a)
g()
println(p.b)

在調(diào)用 f 時(shí)，t 中的指針將在 ptr 位圖中標(biāo)記為存活的（可能只標(biāo)記 t 的 a 字段）黎休。在調(diào)用 g 時(shí)不會浓领。

清除

清掃器（sweeper）由兩種不同的算法組成：

• 對象回收器查找和釋放 span 中未標(biāo)記的 slots。
  如果沒有標(biāo)記任何對象势腮，它可以釋放整個(gè) span联贩，但這不是它的目標(biāo)。
  可以通過 mcentral.cacheSpan（for mcentral spans）同步驅(qū)動捎拯，也可以通過 mheap_.sweepSpans 中所有正在使用的 spans 列表中的 sweepone 異步驅(qū)動泪幌。

• span 回收器查找不包含標(biāo)記對象的 span，并釋放整個(gè) span署照。
  這是一個(gè)單獨(dú)的算法祸泪，因?yàn)獒尫耪麄€(gè) spans 對于對象回收器來說是最困難的任務(wù)，但是在分配新 spans 時(shí)非常關(guān)鍵建芙。
  這個(gè)的入口點(diǎn)是 mheap_.reclaim浴滴，它是由堆區(qū)域中的頁面標(biāo)記位圖的順序掃描驅(qū)動的。

兩種算法最終都調(diào)用 mspan.sweep岁钓，它掃描單個(gè)堆 span。

棧對象和棧跟蹤

堆跟蹤解決了確定棧的哪些部分是存活的并且應(yīng)該被掃描的問題微王。它作為掃描單個(gè) goroutine 棧的一部分運(yùn)行屡限。

通常，靜態(tài)地確定堆棧的哪些部分是存活的很容易炕倘，因?yàn)橛脩舸a對棧對象有顯式的引用（讀和寫）钧大。
編譯器可以進(jìn)行簡單的數(shù)據(jù)流分析，以確定代碼中每個(gè)點(diǎn)的棧變量的活躍性罩旋。
有關(guān)該分析啊央，請參閱：$GOROOT/src/cmd/compile/internal/gc/plive.go

但是，當(dāng)我們獲取堆棧變量的地址時(shí)涨醋，確定該變量是否仍然存活就不太清楚了瓜饥。
我們?nèi)匀豢梢圆檎异o態(tài)訪問，但是通過指向變量的指針進(jìn)行的訪問通常很難靜態(tài)跟蹤浴骂。
該指針可以在棧上的函數(shù)之間傳遞乓土，有條件地保留等。

相反，我們將動態(tài)跟蹤指向棧變量的指針趣苏。
所有指向棧分配的變量的指針本身都將位于棧的某個(gè)位置（或者在相關(guān)位置狡相，如 defer），因此我們可以有效地找到它們食磕。

棧跟蹤被組織為迷你的垃圾收集跟蹤通道尽棕。這個(gè)垃圾收集中的對象是棧上的所有變量，這些變量的地址已被占用彬伦，它們本身包含一個(gè)指針滔悉。我們稱這些變量為 “棧對象”。

我們首先確定堆棧上的所有棧對象和可能指向棧的所有靜態(tài)存活指針媚朦。然后我們處理每個(gè)指針氧敢，看它是否指向棧對象。如果是询张，我們掃描該棧對象孙乖。棧對象可能包含指向堆的指針，在這種情況下份氧，這些指針將被傳遞給 主 GC唯袄。棧對象也可能包含指向棧的指針，在這種情況下蜗帜，我們將它們添加到棧指針集中恋拷。

一旦我們處理完所有指針（包括我們在處理過程中添加的指針），我們就找到了所有存活的棧對象厅缺。
任何死亡的棧對象都不會被掃描蔬顾，并且它們的內(nèi)容也不會保持堆對象存活。與 主 GC 不同湘捎，我們無法清除死亡的棧對象诀豁；它們一直處于垂死狀態(tài)，直到包含它們的棧幀被彈出窥妇。

椣鲜ぃ可能如下所示：

?+----------+
?|?foo()????|
?|?+------+?|
?|?|??A???|?|?<---\
?|?+------+?|?????|
?|??????????|?????|
?|?+------+?|?????|
?|?|??B???|?|?????|
?|?+------+?|?????|
?|??????????|?????|
?+----------+?????|
?|?bar()????|?????|
?|?+------+?|?????|
?|?|??C???|?|?<-\?|
?|?+----|-+?|???|?|
?|??????|???|???|?|
?|?+----v-+?|???|?|
?|?|??D??---------/
?|?+------+?|???|
?|??????????|???|
?+----------+???|
?|?baz()????|???|
?|?+------+?|???|
?|?|??E??-------/
?|?+------+?|
?|??????^???|
?|?F:?--/???|
?|??????????|
?+----------+

foo() 調(diào)用 bar() 調(diào)用 baz()。每個(gè)方法在棧上都有一個(gè)楨活翩。

foo() 有棧對象 A 和 B烹骨。

bar() 有棧對象 C 和 D, C 指向 D, D 指向 A。

baz() 有一個(gè)棧對象 E 指向 C材泄，一個(gè)局部變量 F 指向 E沮焕。

從局部變量 F 中的指針開始，我們最終將掃描所有 E拉宗、C遇汞、D 和 A （按照這個(gè)順序）。

B 不會被掃描，因?yàn)闆]有指向它的存活指針空入。

如果 B 也是靜態(tài)死的（這意味著 foo() 在調(diào)用 bar() 之后再也不會訪問 B）络它，那么 B 指向堆的指針就不被認(rèn)為是存活的。

tips：棧對象與棧掃描

//?stackObject?表示棧上的一個(gè)變量歪赢，該變量的地址已被占用化戳。
//
//go:notinheap
type?stackObject?struct?{
????off???uint32???????//?stack.lo?之上的偏移
????size??uint32???????//?對象的大小
????typ???*_type???????//?類型信息（對于?ptr/nonptr?位），如果對象已被掃描埋凯，則為?nil
????left??*stackObject?//?低地址對象
????right?*stackObject?//?高地址對象
}

//?如上可以看出棧對象是一個(gè)雙向鏈表
//?參見：go1.12beta2/src/runtime/mgcstack.go

//?scanstack?掃描?goroutine?的棧点楼，標(biāo)灰所有在該棧上找到的指針。
//
//?scanstack?被標(biāo)記為?go:systemstack白对，因?yàn)樗谑褂?workbuf?時(shí)不能被搶占掠廓。
//
//go:nowritebarrier
//go:systemstack
func?scanstack(gp?*g,?gcw?*gcWork)?{
......
????var?state?stackScanState
????state.stack?=?gp.stack
......
????//?查找并且掃描所有可達(dá)的棧對象。
????//?buildIndex?將?state.root?初始化為二叉搜索樹甩恼。
????//?應(yīng)該在所有?addObject?調(diào)用之后但在調(diào)用?findObject?之前調(diào)用它蟀瞧。
????//?使用棧對象數(shù)組構(gòu)造了一顆二叉查找樹。
????state.buildIndex()
????for?{

????????//?刪除并返回指向堆棧對象的潛在指針条摸。
????????//?如果沒有更多可用指針悦污，則返回0。
????????p?:=?state.getPtr()
????????if?p?==?0?{
????????????break
?????????}

????????//?findObject?返回包含地址?a?的堆棧對象（如果有）
????????obj?:=?state.findObject(p)
????????if?obj?==?nil?{
????????????continue
?????????}
......
?????}
......
}

//?參見：go1.12beta2/src/runtime/mgcmark.go