# Garbage Collection 垃圾回收機制，從` 保守 `到` 精準 `。
contributed by ` JulianATA `
:::info
從基礎的 Garbage Collector 中的 `mark-and-sweep` 演算法開始，再來探討保守 `Conservative` 垃圾回收的缺點。
延伸 ` mark-and-sweep ` 介紹效能相較優秀的 ` Tri-colored `演算法。了解 ` GO ` 語言中，GC的基礎運作機制。
介紹精準 ` Precise ` 垃圾回收的好處與限制，透過 ` 文獻回顧 ` 與簡介專案 ` magpie ` 了解精準垃圾回收在 `C語言` 實現上的難點。
最後，以 Java8 為基礎，了解 JVM 中進階的垃圾回收機制。
:::
## mark-and-sweep 演算法
### Naive 運作機制:
包含兩個階段 `Mark` 標記和 `Sweep` 掃除。
#### `Mark` Phase
從 root 開始，找尋 `可到達` 的物件。 ( `Reachable Objects` )
標記 `可到達` 的物件。
#### `Sweep` Phase
從 heap 中，找尋未被標記的物件( `Unreachable Objects` )，即需要被清除的物件。
將未被標記的物件加入到 `free list` 中，準備清除。
將已被標記的物件重置為未被標記，以利下次的清掃。
### 如何實作
#### 簡單實作 `Mark`
1. 建立訪問清單 `todo` 將所有 root 中的物件加入。
2. 當 `todo` 中有物件時，執行以下3~4。
3. 從 `todo` 中選任一物件 `v` ，將其除外於 `todo`。
4. 如果 `v` 未被標記，標記 `v` ，將所有 `v` 包含的物件放到 `todo` 中。
#### 簡單實作 `Sweep`
1. 物件 `p` 從 `heap` 的最底層物件開始。
2. 當 `p` 還不是 `top` 的時候，執行以下3~5。
3. 如果 `p` 已被標記，則將其改為未標記。
4. 反之，將 `p` 的記憶體區塊加到 `free list` 中，準備清除。
5. 將 `p` 改為在 heap 中上一層的物件。 ( `using p <- p + sizeof(p)` )
#### 問題點 `1`
* 需要清除時，通常表示沒有記憶體空間。
* 但是， Mark 階段需要記憶體空間去創造訪問清單 。
* 訪問清單無法預測大小，因此無法預先保留。
:::info
解決方法
* 應用 `pointer reversal` ，用 `depth first search` 取代訪問清單。
:::
#### 問題點 `2`
* 有些物件沒有指標的空間。
:::info
解決方法
* 使用一個暫存器記憶其 `parent` 位置，就可以不用 `pointer reversal` 也能執行 `depth firsth search` 。
:::
## Tri-Color 演算法與 Golang
:::info
Reference: [Golang realtime garbage collector](https://www.youtube.com/watch?v=n59VtiRx34s)
:::
上述的基礎 ` mark and sweep ` 演算法有一個缺點。每次在執行 `mark` 的時候，都需要將 process 暫停。
* 在標記的時候，需要讓所有 object 維持不變，才能保持不出錯。
---
* 舉例： 以下 process 有物件 obj0, obj1, obj2, obj3
* 時間t0：執行 ` mark ` 將 ` reachable ` 物件標記。
* 時間t1：因為沒有暫停 process，出現 obj4 指向 obj3
* 時間t2: 執行 ` sweep `，刪除物件 obj3, obj4 產生錯誤。
因此，為了讓 ` mark and sweep ` 過程可以不暫停 process， 延伸出了` Tri-colored `演算法
### Tri-colored 演算法
* 使用 Breadth-first 的策略。
* 將物件用三種顏色來標記：
* 白色：未標記，在 sweep 的階段被清掃
* 灰色：已標記，目前 Breadth-first 的進行前緣。
* 黑色：已標記。
* 將新增物件，標記為灰色。
## Precise Garbage Collector
:::info
Paper Review: [Precise Garbage Collection for C](https://www.cs.utah.edu/plt/publications/ismm09-rwrf.pdf)
:::
### `Precise` GC vs.`Conservative` GC
#### 「保守」 Conservative
在 C 或 C++ 的實作中，`pointer` 的使用沒有硬性規定，因為可能會有 ` unreachable ` 的物件被標為 `reachable` ，原因可能為 type imprecision 或是 liveness imprecision 等等。
* **type imprecision:** 資料型別不明確的情況下，將 ` 非指標 ` 之資料型別作為指標尋找物件。
以下為實作 type imprecision 情況的程式 Based on [ogc](https://github.com/jserv/ogc) .
```clike
#include <assert.h>
#include "gc.h"
void ImPrecise(long *l)
{
int* Unreachable;
Unreachable = gc_alloc(sizeof(int));
assert(Unreachable);
*l = (long)Unreachable;
}
int main(int argc, char *argv[])
{
gc_init(&argc, 1);
long *l;
l = gc_alloc(sizeof(long));
assert(l);
ImPrecise(l);
gc_run();
gc_dump_internals();
gc_destroy();
return 0;
}
```
預計輸出
```bash
## GC internals ##
- GC.ptr_map[20]:
{ ptr: 0x7ffc624006a0, size: 8, marked: 0 }
```
實際輸出
```bash
## GC internals ##
- GC.ptr_map[20]:
{ ptr: 0x7fceecc006a0, size: 8, marked: 0 }
- GC.ptr_map[58]:
{ ptr: 0x7fceecc02bd0, size: 4, marked: 0 }
```
可以看到 `reachable` 的物件，應該只有 type 為 `long` 的 `l` 。
但是 `l` 中儲存的值 `剛好` 等於為一個 `unreachable` 物件的地址。
因此，GC 便保守地將其標為 `reachable` 。
#### 保守 GC 的缺點
> In our experience, however, conservative GC works
poorly for long-running programs, such as a web server, a programming environment, or an operating system kernel.
`Conservative GC` 在小型的程式中有不錯的效果。但在長期執行的 ` long-running ` 程式中，因為沒有持續的記憶體維護對於記憶體管理會造成很大的負擔。
#### PTL Scheme 看 GC
論文中提到對於 [PLT Scheme](https://zh.wikipedia.org/wiki/Racket) ( 現名為Racket ) 的實驗。
* PLT Scheme在當時使用的正是 Conservative GC，每天都會讓記憶體消耗殆盡，導致重新啟動。就算是學生寫的簡單程式，也需要在運行幾小時候重新啟動。
* 替換為 precise GC 後解決了這個問題。每次 Conservative GC 大概回收40MB，反之 Precise GC 可以回收100MB。
*
另外，在 Kernel 中，在使用 linked list 來管理執行緒 ` thread ` 的情況下，可能會造成 unbounded memory 的問題。
其中，很多問題的原因並不只是因為 ` type imprecision ` ，而是因為 ` liveness imprecision ` 。
#### C 語言使用 Precise GC 的限制:
:::info
固然，使用 Precise GC 可以回收更多記憶體，在使用上卻有許多限制。
例1：宣告的型別需要跟 run-time 的行為一樣，至少在「指標與非指標」變數之間，不能混用。
我們常使用 void* 作為 generic pointer type，也會造成他所指向的資料有模糊的狀況。
例2：處理 Union 的使用，也容易造成型態的混用。
:::
因此，讓C語言程式適應 Precise GC 的行為，是一大挑戰。
##### 指標與非指標
> For GC to work, all live objects must be reachable via pointer
chains starting from roots, which include static and local variables with pointer types.
為了讓 GC 可以如期執行，所有`活著`的物件都必須是從 `root` 藉由指標可達的。
為了讓 `precise` GC 能精準的控制資源，所有非指標類的都確保不會被當作 ` GC-allocated ` 物件的指標。
### magpie
## garbage collection in Java
###### tags: ` Cprogramming `
Sign in with Wallet
Connect another wallet