GC掃描棧

問題的關鍵在于這段代碼：

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

編譯器決定在棧上分配 T，并且因為編譯器無法跟蹤其地址結束的位置，所以編譯器保守地決定 t 始終是存活的。

但是在 for 循環(huán)中，當 p 被賦值時，t 變成死亡的。
所以在 p 被重新分配之后，t 中的任何指針都可能保持一個它不應該保持的對象存活。

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

我們開始像往常一樣掃描一個棧，從最低（最新）的棧幀開始，一直向上。
我們使用指針位圖來查找每個棧幀中的所有存活的指針。
通常，棧對象的指針不會標記為存活（但請參見下文）。
所有指向堆的指針都像往常一樣被標記，任何指向棧的指針都被忽略(目前)。
對于遇到的每一幀，我們查看該幀是否有棧對象。
對于該幀中的每個棧對象，我們將其添加到棧對象列表中。

如果我們到達棧頂部并找不到棧對象，那么就結束了。

如果我們確實找到了一些棧對象，我們必須再次掃描棧。

首先，我們將棧對象組織成一個數(shù)據(jù)結構，該結構提供按地址快速查找的功能，可能是一個二叉樹。由于我們可以按地址順序枚舉棧對象，所以應該很容易使用它們的地址作為 key 來生成二叉樹（在 O(n) 時間內(nèi)）。

然后我們再次掃描棧，只查找指向棧的指針。
對于任何這樣的指針，我們在二叉樹中查找它們，看看它們是否指向任何棧對象。
如果是，我們將棧對象標記為存活（如果我們還沒有這樣做），并將其放入正在掃描的工作列表中。當我們完成棧掃描時，我們現(xiàn)在在工作列表中有了棧對象的根集（root set）。
然后，我們不斷從工作列表中彈出一個對象并掃描它（可能將堆對象或其他棧對象標記為存活），直到工作列表為空。

我們可以為每個棧對象分配相鄰的空間來使用這個算法。我們稱之為棧對象“header”。
header 可能包含二叉樹的左右指針，一個標記位和用于單鏈表工作隊列的指針。
header 有一些空間開銷，但是它應該很小，并且可以自由分配，因為它只是使棧幀更大一點。
header 只需要在第一次掃描是找到棧對象時才初始化。因此我們可以在正常執(zhí)行期間將垃圾留在那里。

記錄棧對象

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

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

_FUNCDATA_StackObjects?=?4

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

（偏移大?。╥sptr）*）*

其中，每個對象在幀中編碼它的起始偏移量、它的大小以及該對象中每個指針 slot 的size/ptrSize 0/1項。

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

有了這種新機制，我們就可以在當前編譯器中為含糊不清的存活對象去掉所有代碼。
我們只需要在存活的 ptr 位圖中標記那些通過直接訪問（而不是通過指針）存活的指針。
我們的新機制包含以前用于跟蹤棧對象的邏輯，該邏輯是：存活只是因為指向它們的指針可能是存活的。

其他說明

對象可以作為棧對象被列出，并在存活的 ptr 位圖中被標記。
例如：

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

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

清除

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

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

• span 回收器查找不包含標記對象的 span，并釋放整個 span。
  這是一個單獨的算法，因為釋放整個 spans 對于對象回收器來說是最困難的任務，但是在分配新 spans 時非常關鍵。
  這個的入口點是 mheap_.reclaim，它是由堆區(qū)域中的頁面標記位圖的順序掃描驅(qū)動的。

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

棧對象和棧跟蹤

堆跟蹤解決了確定棧的哪些部分是存活的并且應該被掃描的問題。它作為掃描單個 goroutine 棧的一部分運行。

通常，靜態(tài)地確定堆棧的哪些部分是存活的很容易，因為用戶代碼對棧對象有顯式的引用（讀和寫）。
編譯器可以進行簡單的數(shù)據(jù)流分析，以確定代碼中每個點的棧變量的活躍性。
有關該分析，請參閱：$GOROOT/src/cmd/compile/internal/gc/plive.go

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

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

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

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

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

?？赡苋缦滤荆?/strong>

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

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

foo() 有棧對象 A 和 B。

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

baz() 有一個棧對象 E 指向 C，一個局部變量 F 指向 E。

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

B 不會被掃描，因為沒有指向它的存活指針。

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

tips：棧對象與棧掃描

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

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

//?scanstack?掃描?goroutine?的棧，標灰所有在該棧上找到的指針。
//
//?scanstack?被標記為?go:systemstack，因為它在使用?workbuf?時不能被搶占。
//
//go:nowritebarrier
//go:systemstack
func?scanstack(gp?*g,?gcw?*gcWork)?{
......
????var?state?stackScanState
????state.stack?=?gp.stack
......
????//?查找并且掃描所有可達的棧對象。
????//?buildIndex?將?state.root?初始化為二叉搜索樹。
????//?應該在所有?addObject?調(diào)用之后但在調(diào)用?findObject?之前調(diào)用它。
????//?使用棧對象數(shù)組構造了一顆二叉查找樹。
????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