GO的GC辣雞回收（一）

2021 年 9 月 2 日
筆記

用戶程式通過記憶體分配器（Allocator）在堆上申請記憶體，而垃圾收集器（Collector）負責回收堆上的記憶體空間，記憶體分配器和垃圾收集器共同管理程式中的堆記憶體空間。

基本概念

垃圾分類

語義垃圾：也就是記憶體泄漏，指的是從語法上可達的對象，也就是被其他對象引用的，但是從語義上來講是垃圾。這類垃圾，垃圾回收是不管的
語法垃圾：從語法上是不可達的對象，也就是沒有對象引用了，這些垃圾是垃圾回收重點照顧的對象

垃圾回收演算法

常見的垃圾回收演算法：

引用計數：

某個對象的根引用計數變為0時，其所有節點均需被回收
標記壓縮：

將存活對象移動到一起，有效解決記憶體碎片問題
複製演算法：

將所有正在使用的對象從From空間複製到To空間，堆利用率只有一半，也能解決記憶體碎片問題
標記清除：

標記垃圾對象，然後再清除。解決不了記憶體碎片問題，需要與能盡量避免記憶體碎片的記憶體分配器使用，如tcmalloc

標記清除

標記清除演算法是最常見的垃圾收集演算法，標記清除收集器是跟蹤式垃圾收集器，其執行過程可以分為標記、清除兩個階段：

標記階段：從根對象出發查找並標記堆中所有存活的對象
清除階段：遍歷堆中的全部對象，回收未被標記的垃圾對象並將回收的記憶體加入空閑鏈表

傳統的標記清除演算法，垃圾收集器從垃圾收集的根對象出發，遞歸遍歷這些對象指向的子對象並將所有可達的對象標記成存活。標記結束後，垃圾收集器會依次遍歷堆中的對象並清除其中的垃圾，整個過程需要標記對象的存活狀態，所以用戶程式在垃圾收集的過程中不能執行，也就是常說的STW（Stop The World）。

三色抽象

為了解決原始標記清除演算法帶來的長時間STW，大部分追蹤式垃圾收集器都會實現三色標記演算法的變種以縮短STW的時間
三色標記演算法將程式中的對象分成白色、黑色、灰色：

白色對象：潛在的垃圾，也就是沒有被掃到的對象，其記憶體可能會被垃圾收集器回收
黑色對象：活躍的對象，包括不存在任何引用外部指針的對象以及從根對象可達的對象
灰色對象：活躍的對象，因為存在指向白色對象的外部指針，垃圾收集器會掃描這些對象的子對象

標記過程：
垃圾收集器開始工作的時候，不存在任何黑色對象，根對象會被標記成灰色，垃圾收集器只會從灰色對象集合中取出對象開始掃描，當灰色集合中不存在任何對象時，標記就會結束。

大致工作原理：

從灰色對象的集合中選擇一個灰色對象並將其標記成黑色
將黑色對象指向的所有對象都標記成灰色，保證該對象和被該對象引用的對象都不會被回收
重複上述兩個步驟直到不存在灰色對象

當三色標記結束後，應用程式的堆中就不存在任何灰色對象，我們只能看到黑色的存活對象以及白色的垃圾對象，垃圾收集器可以回收這些白色的垃圾。
缺陷：
由於用戶程式可能在標記執行的過程中修改對象的指針，所以三色標記清除演算法本身是不可以並發或者增量執行的，仍需要STW。如果本來不應該被回收的對象被回收了，這在記憶體管理中是非常嚴重的錯誤，這種錯誤稱為懸掛指針，也就是指針沒有指向特定類型的合法對象，影響了記憶體的安全性，想要並發或者增量標記對象就需要使用屏障技術。

屏障技術

記憶體屏障技術是一種屏障指令，可以讓CPU或編譯器在執行記憶體相關的操作時遵循特定的約束，目前多數的現代處理器都會亂序執行指令以最大化性能，但是該技術能夠保證記憶體操作的順序性，在記憶體屏障前執行的操作一定會先於記憶體屏障後執行的操作。想在並發或增量的標記演算法中保證正確性，需要達到兩種三色不變性的其中一種。

三色不變性：

強三色不變性：黑色對象不會指向白色對象，只會指向灰色對象或者黑色對象
弱三色不變性：黑色對象指向的白色對象必須包含一條從灰色對象經由多個白色對象的可達路徑

屏障技術分為讀屏障和寫屏障，但是由於讀屏障需要在讀操作中加入程式碼片段，所以對用戶程式的性能影響較大。解析一下go語言中使用的兩種寫屏障技術，插入寫屏障和刪除寫屏障。

插入寫屏障(DIJKSTRA)

writePointer(slot, ptr):
    shade(ptr)
    *slot = ptr

每當要執行*slot = ptr時，會先執行寫屏障通過shade函數嘗試改變指針顏色。如果ptr指針是白色，那麼會將該對象設置成灰色。

這張圖中可以看到，在一次正常的標記過程中，發生了用戶程式修改了指針引用（或者新插入了一個引用關係）的情況，如果我們採用插入寫屏障我們就需要將新指向的對象標為灰色，以此保證強三色不變性。（對於新指向的對象來說，屬於被插入一個引用，所以叫插入寫屏障)

在插入寫屏障中，我們的標記過程變成（關鍵第2步）：

基本標記流程不變，我們快進到垃圾收集器將根對象指向A對象標記成黑色，並將A對象指向的對象B標記成灰色。
這時用戶程式修改A對象的指針，將原本A對象指向B對象的指針指向C對象，這個時候就會觸發寫屏障將C對象標記為灰色，避免被錯誤回收。
垃圾收集器依次遍歷程式中的其他灰色對象，將他們分別標記成黑色

刪除寫屏障(YUASA)

writePointer(slot, ptr)
    shade(*slot)
    *slot = ptr

刪除寫屏障會在老對象的引用被刪除的時候，將白色的老對象塗成灰色，這樣就可以保證弱三色不變性，老對象引用的下游對象一定可以被灰色對象引用。

使用刪除寫屏障技術的垃圾收集器和用戶程式交替運行的場景中的標記過程：

垃圾收集器將根對象指向A對象標記成黑色並將A對象指向的對象B標記成灰色
如果這時用戶程式將B指向C的指針刪除，那麼C觸發刪除寫屏障，由於C是白色，所以被塗成灰色
垃圾收集器依次遍歷程式中的其他灰色對象，將他們分別標記成黑色

第二步觸發刪除寫屏障的著色，因為刪除了B指向C的指針，所以C和D分別違反強三色不變性和弱三色不變性，著色後保證了三色不變性，避免懸掛指針。

簡單來說就是，在改變指針指向的時候，原來指向的那個對象是白色的話就要變成灰色，以此保證弱三色不變性。（對於老對象來說，引用關係被解除了，所以叫刪除寫屏障）

增量和並發

兩種策略優化垃圾收集器不會以為回收垃圾導致長時間STW：

增量垃圾收集：增量得標記和清除垃圾，降低應用程式暫停的最長時間
並發垃圾手機：利用多核的計算資源，在用戶程式執行時並發標記和清除垃圾

由於兩種方式都需要垃圾收集器與用戶程式交替執行，所以需要配合屏障技術。

增量收集器

增量收集器將原本時間較長的暫停時間切分成多個更小的GC時間片。增量收集器需要配合三色標記法和屏障技術一起使用。將GC過程分段執行，雖然拉長了總的垃圾回收時間，但是減少了程式STW的時間。不過寫屏障還是有些開銷的。

並發收集器

利用多核優勢，將GC過程與用戶程式並行執行（大部分情況下），也是要配合屏障技術。