tags: `Golang`

垃圾回收～～～

追蹤heap裡面的mem
刪除沒在用的
保留有在用的

主要有分兩大類
一. Reference counting
每個 obj 記住自己有被多少人連結到，歸零的時候順便回收
例如：

a = Person("A")     // new 一個 Person 的 instance，這個 instance 的 ref count = 1
b = a       // b 也去指相同的東西 ref count 再 +1
b = None    // ref count -1
a = None    // ref count -1 變成 0，記憶體釋放

問題：
circular references

a = Person("A")
b = Person("B")
a.friend = b
b.friend = a
a = None
b = None

雖然已經沒有任何變數直接指到新建的兩個 instance，，但實際上兩個 instance 還是互相 reference，讓 ref count 不會歸零。
所以只看 ref count 來回收還是有可能 memory leak
https://zhuanlan.zhihu.com/p/101781276
主要有兩種解決法

讓寫程式的人處理
譬如在 a.friend = b 時，指定這個是 weak pointer，讓它不列入 ref count 的計算。
好處是程式語言除了 reference counting 就不用做其他事了
壞處是碼農們沒寫好還是會 mem leak
讓電腦做
加入一些 tracing GC 來輔助處理這些 circular references 的問題
下面會再講這是啥～
好壞處就和上面相反

總結計數的方法

優點：好做，計數歸零就釋放，不會像 tracing GC 一樣，要找個時間來做 GC 讓程式暫停一陣子，

缺點：每次都增加減少 count 也會有效能問題，且是不能出錯的東西，甚至要用鎖之類的方法來確保不會有 race condition
且要額外處理迴圈引用的問題

二. Tracing: GC 啟動時從 roots 出發，再來找出沒在用的東西然後回收

可以想像成一個 graph，裡面的 node 是一塊一塊的記憶體，被程式 allocate 來使用，edge 就是 reference

roots 就是那些我們可以直接存取到的東西 (像是全域變數或是 goroutine stack)，由這些 roots 開始去做圖的 traverse，所有可以從這些 roots
連接到的東西都是還在使用的，到達不了的 node 就是垃圾

在這邊也有一種 weak pointer 但和 reference counting 的用法不同，這種 edge 是可以存取一個物件，但不保護這個物件不被回收

常見名詞：
Mutator: 改變那些記憶體reference的東西，像是我們的程式就是

Mutator roots: root set, root objects，可以直接被存取的物件，像是靜態或全域變數、參數、Goroutine stack的其他東西

Collector: 負責回收垃圾的程式

Copy GC

最原始的垃圾回收

把全部的記憶體切成兩份，一般時候都是用同一份

當要收垃圾的時候就是從 roots 出發 traverse，把不是垃圾的東西複製到另一份，然後原本的那一份就可以清空了（當作垃圾，不用真的清）

文章可以參考這個：https://zhuanlan.zhihu.com/p/28197216

Traverse 和複製時要注意的就是指標的值也要順便更新

缺點是空間要用很多

不過複製的時候可以順便讓記憶體更 compact 是好處

基本的 Mark and Sweep

https://liujiacai.net/blog/2018/07/08/mark-sweep/
就是簡單的收垃圾XD
網路上很多 pseudo code 可以看

先把其他在做的事情都停住 (Stop the world)
從 roots 出發把有用到的東西 mark 起來
掃過 heap 所有的物件，把沒用的清除
恢復運作

簡單可以發現問題點，有記憶體碎片、掃過整個 heap 很慢、要停止所有東西

https://stackoverflow.com/questions/23057531/what-are-the-advantages-and-disadvantages-of-having-mark-bits-together-and-separ
優化
Bitmap marking：用 bitmap 來紀錄哪些 object 是被 mark 住的
Lazy sweep：allocate 時才去做清垃圾，而且只清剛好需要的空間就好，平常只做標記

Mark-Compact

先把還有在用的標記起來然後 compact
https://en.wikipedia.org/wiki/Mark-compact_algorithm
目的就是要把還在使用的記憶體聚集在一起，減少記憶體碎片，碎片多就是母湯

常見的做法就是掃過 heap，然後把每個 obj 往邊邊移動就好
wikipedia裡面介紹了兩種方法

Table-based

是需要掃過記憶體兩次，第一次掃過時要用一個 break table 記住每個 obj 原本的位置還有預計要移動到的位置，然後就將該 obj 移動
第二個 pass 是要用 break table 調整這些 obj 裡面的 pointer

Break table 也是存在同一個 heap 內，搬移的時候可能會卡到，table 打散要重新排序(???)

LISP2 algorithm

是一個簡單多的演算法
要 3 個 pass

算出來每個 obj 預計會到哪
更新每個 obj 指出去的 pointer
移動~
其中第一步預計要移動去哪的資訊會存在各自 obj 中

Incremental GC

https://liujiacai.net/blog/2018/08/04/incremental-gc/#%E5%A2%9E%E9%87%8F%E5%BC%8F-GC-%E6%80%9D%E8%B7%AF

https://segmentfault.com/a/1190000022030353

https://titanwolf.org/Network/Articles/Article?AID=786c12ef-88b2-42da-984a-41ef4b5669d1#gsc.tab=0
不一次做完整個垃圾回收的動作 (其實 ref counting 就類似，但缺點不少)，每次停頓小(最重要的優點)，但 throughpu 會降低就是了

mark 的階段會被分成很多次

三色標記法（tricolor marking）

一樣從 roots 出發去 traverse 整個 obj graph，過程中會將 obj 們標成不同顏色
一開始 roots 都是灰色，其餘白色

黑：可以到達，且該節點的子節點都看過了
灰：可以到達，還沒去檢查該節點的子節點們
白：還沒到達，如果 mark 結束都還是白色就會被當作垃圾

標記階段可以被中斷，下次要開始時可以從灰色的子節點開始檢查
直到沒有灰色節點時就完成 mark 階段
灰色是用來記錄 mark 中斷後，又被 mutator 改變狀態的節點
新建的 obj 依照不同的方法會設為不同顏色

然而在標記階段中斷後再次開始前，我們的程式(mutator)可能會去改變這些 obj 之間的 reference，以下圖為例 (從上面網站抓來的)

改變後可能造成黑A直接 ref 到白D，下次 mark 再開始後因為 A 是黑色，導致 D 不會被掃到，誤當成垃圾

Tricolor invvariant

為了避免上述的情況發生，三色標記法限制了節點的顏色與 reference 的關係
下面兩種只要其中一種滿足即可

Strong Invariant: 黑色不可直接指到白色，上面那種情況我們不會再去檢查黑點的子節點，導致戊收垃圾

Weak Invariant: 黑可以直接指到白色，但這個白色必須是某個灰色節點的直接或間接後代

參考圖 https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/

D 在右圖是 B 的後代，所以允許 A 直接 reference

接下來就是當 mutator 在運作時，我們如何維持上述其中一種 invariant 了
在我們的程式 (mutator) 做事情時，需要插入一些 collector 的動作

read barrier
顧名思義讀資料的時候插入動作，防止 mutator 去讀白色的 obj

讀白色 obj 時就把它標成灰色
例：上面那個 Figure 7 在讀 D 的時候就把 D 塗成灰色

可以保證上面的 strong invariant
write barrier

https://www.mdeditor.tw/pl/prRu/zh-tw
https://www.mdeditor.tw/pl/pFz3/zh-tw
寫資料時插入動作，基本的有兩種
stack太多，如果開write barrier會很慢，通常只開heap，所以以下兩種方法需要再開始或結束時掃一次stack來處理，預防有白色被已掃過的stack指到

a. insert write barrier (dijkstra)
當 mutator 把黑色指向白色時，會將白色變成灰色，或者把黑色變成灰色 (前者好像比較常見)
如此一來就符合 strong invariant 了～
mark結束後要再掃一次stack，因為stack沒開wb，指到的東西可能是白色卻需要存活

b. delete write barrier (Yuasa)
若有一個指針指向一個 obj 且該 obj 為白或灰
當 mutator 此指針拿掉時，該 obj 要被塗成灰色

一開始需要掃roots，把roots直接指到的都塗灰
為何需要開始時掃stack-
http://www.yuasa.kuis.kyoto-u.ac.jp/~yuasa/ilc2002/slide.pdf
因為stack沒開rb，如果有一個root在stack上，若他直接指到某個obj，且這個pointer在這個obj被看到前，就被移除，那此obj可能被另外的黑色指到，就還是白色卻需要存活

一般來說 write barrier 的效率會比較好，因為 heap 讀比寫多很多

Generational GC

https://liujiacai.net/blog/2018/08/18/generational-gc/
分代，大部分的東西剛創建不久就會變成垃圾，所以把年輕和老的物件分開存
年輕的部分常常做ＧＣ，老的偶爾做

通常年輕的 obj 多，老的少
young -> old 的 pointer 比 old -> young 多

不動到 old，獨立回收 young 部分
考慮到 old -> young 的 pointer
可以新增 write barrier 做一些操作，當 old 指到 young 時就記住，把被指到的 young 當作 young gc 時的 root

若該 old 是變成垃圾，則 young 會暫時成為實際上是垃圾的 root
所以下次老 gc 時要清掉

獨立回收 old
要考慮到 young -> old 的 pointer
可以依照上面的方法來做，但通常 young -> old 的 pointer 數量較多
要記錄的東西會很多，可以直接把所有 young 當作 root set，反正不多

Go GC

一開始適用插入屏障後來改用混合型，結合插入和刪除寫屏障，去除了開頭或結束時的 scan

介紹怎麼讓 Go gc 更有效率
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html

https://golangpiter.com/system/attachments/files/000/001/718/original/GP_2019_-_An_Insight_Into_Go_Garbage_Collection.pdf?1572419303

https://www.mdeditor.tw/pl/prRu/zh-tw
https://www.mdeditor.tw/pl/pFz3/zh-tw

"" 引用上面文章的段落
在Go 語言 v1.7 版本之前，使用的是 Dijkstra 插入寫屏障保證強三色不變性，但是執行時並沒有在所有的垃圾收集根物件上開啟插入寫屏障。因為 Go 語言的應用程式可能包含成百上千的 goroutine，而垃圾收集的根物件一般包括全域性變數和棧物件，如果執行時需要在幾百個 goroutine 的棧上都開啟寫屏障，會帶來巨大的額外開銷，所以 Go 團隊在實現上選擇了在標記階段完成時暫停程式、將所有棧物件標記為灰色並重新掃描，在活躍 goroutine 非常多的程式中，重新掃描的過程需要佔用 10 ~ 100ms 的時間
""

https://studygolang.com/articles/27243

Hybrid write barrier

https://github.com/golang/proposal/blob/master/design/17503-eliminate-rescan.md

可以看 Proposal 和 Reasoning，有介紹為何他們可以消除開頭或結尾的掃描

writePointer(slot, ptr):
    shade(*slot)
    if current stack is grey:   
        shade(ptr)
    *slot = ptr

奇怪的例子
A->B
C->nil

都在 AC 都在 stack 上，若C黑，AB白
當變成
A -> nil
C -> B
時，因為是stack 所以wb都不會啟動？

B會被誤刪嗎

這裡說當混合寫屏障時，在掃描特定一個goroutine上的stack時還是要暫停，一次掃完(所以上面那種情況不會出現)
但不用像Yuasa一開始把全部stack掃完或是Dijkstra最後重掃
https://liqingqiya.github.io/golang/gc/%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6/%E5%86%99%E5%B1%8F%E9%9A%9C/2020/07/24/gc5.html

其餘連結
https://mcll.top/2020/04/14/gc-write-barrier/
https://www.bookstack.cn/read/qcrao-Go-Questions/spilt.3.GC-GC.md

原始碼
https://go.googlesource.com/go/+/go1.7beta2/src/runtime/mbarrier.go

垃圾回收！

tags: Golang