---
tags: System Software
---
# Garbage collector
## Overview
> [Garbage collection (computer science)](https://en.wikipedia.org/wiki/Garbage_collection_(computer_science))
我們都知道，通過 heap 的使用，可以動態的配置記憶體，相對於 stack 上的物件會有生命周期的限制，heap 提供了一定程度的便利性。但這也帶來了一定程度的風險，衍生出像是 [dangling pointer](https://en.wikipedia.org/wiki/Dangling_pointer)、[memory leak](https://en.wikipedia.org/wiki/Memory_leak)、double free pointer 這樣的問題。
因此，garbage collection 的相關演算法被提出以因應這些問題。garbage collection 是一種自動管理記憶體的機制，當某個記憶體空間將不再被程式 access 時，則借助 garbage collector 來返回這些空間，因此可以減少程式撰寫者對記憶體管理的負擔，也避免可能因此發生的錯誤。
garbage collection 雖然可以避免某些錯誤的發生，但其最大的缺點是實作此機制背後所帶來的成本。包含為了管理這些記憶體而需要的額外記憶體資源、以及垃圾回收機制啟動所帶來時間耗費都是需要被考慮的。
## Garbage
> [Garbage (computer science)](https://en.wikipedia.org/wiki/Garbage_(computer_science)#syntactic_garbage)
garbage 包含未來將不再使用的 datas、objects 或者一段記憶體，需要釋放這些 garbage 使得系統可以重用這些空間，以善用有限的記憶體資源。
garbage 可以區分為兩種:
* semantic garbage: 無法透過任何合法輸入以存取到的 object / data
* syntactic garbage: 指存在記憶體中但從 root set unreachable 的 object / data
> *Casually stated, syntactic garbage is data that cannot be reached, and semantic garbage is data that will not be reached.*
## Tracing
> [Tracing garbage collection](https://en.wikipedia.org/wiki/Tracing_garbage_collection)
Tracing 是 garbage collection 最常使用的機制，也是一般提到 garbage collection 所指的類型。大致來說，這類的方法從特定的 "root" 物件開始然後追蹤其引用的一系列 object chain，這些 object 被稱為 reachable，其他的物件則為 garbage 並應當被釋放。
reachable object 一般來說包含兩種情形:
* root set 是被 GC 直接默認為 reachable 的物件，包含來自 global 和 stack 上變數的 reference
* 任何對於 reachable object 的 reference
透過 reachability 來定義 garbage 是有侷限性的，對於 semantic garbage，還需要對於程式的額外分析，對於 syntactic garbage 則可以透過 reachable 的分析來蒐集並回收 garbage。
### Naïve mark-and-sweep
Tracing 可以再細分成不同的實作方式，mark-and-sweep 是其中一種。在這個方法中，每個記憶體的 object 額外配有一個 flag(例如用一個 bit 表示)。在 mark 階段，對整個 root set 的樹狀結構做搜尋，標註從每一個 root 開始指向的 object，以及往下所能遍歷的 object，換句話說，所有 reachable 的 object 最後都被標註起來。然後是 sweep 階段，檢視整個記憶體區域，將被標註的記憶體 flag 清空，而未標註的就直接釋放掉。
可以參考這張[動圖](https://en.wikipedia.org/wiki/File:Animation_of_the_Naive_Mark_and_Sweep_Garbage_Collector_Algorithm.gif)的解釋。
這樣的方法很單純，不過自然也就有許多缺點。最大的問題是整個 mark and sweep 運行的時候會需要暫停整個主程式的運行，影響了這個機制適合的應用場景。此外，整個記憶體的 working set 需要經歷至少兩次的掃描，在 locality 上可能導致額外的考量。
### Tri-color marking
Tri-color marking 以三種不同的標註來改進 performance 的議題。首先，假設我們擁有白、黑、灰三種集合。
* 白色集合代表被 GC 回收的候選
* 黑色集合表示未 reference 到白色集合的物件，從 root set reachable，因此不能被 GC 回收
* 灰色集合代表從 root set reachable，且等待被掃描以確認是否 reference 到 白色集合中的 object，且在掃描後加入黑色集合
將黑色集合初始化為空，從 root 直接 reference 的物件加入灰色集合，剩下的加入白色集合。每個時間點下，一個物件會存在 3 個集合中的其一。接著演算法的流程為:
1. 從灰色集合選擇一個物件加入，黑色集合
2. 將白色集合中 reference 到該灰色物件的物件加入灰色集合
3. 重複步驟 1 / 2 直到灰色集合中的物件為空
最後，黑色集合中包含所有 reachable 的物件，白色集合中的物件則是可以被回收的空間。
可以參考此[動圖](https://en.wikipedia.org/wiki/File:Animation_of_tri-color_garbage_collection.gif)的解釋。
因為不能從 root set reachable 的物件最後都被留在白色集合中，而且物件的移動只能是從白到灰、從灰到黑的兩個步驟，這使得此方法中存在一個重要的 tri-color invariant 特性: 黑色集合中的 object 不 reference 到白色集合中的 object，確保了當灰色集合為空時一定可以釋放白色集合中的所有空間。
Tri-color marking 最大的優點在於: 它不像 mark and sweep 方法需要長時間暫停整個主程式的運行，通過監視分配與釋放時使維護集合產生的變動，可以週期性的進行 garbage collection。也不需要頻繁搜索整個被使用的記憶體集合之狀況。
:::warning
實際的實作考量比這裡的敘述要複雜得多，需要更深入的探討
:::
## Reference counting
> [Reference counting](https://en.wikipedia.org/wiki/Reference_counting)
這類的做法是透過計數每個 object 的引用次數來維護，當每次 object 被引用時就將 reference 加一，而解除引用則減一，如果引用次數歸零，object 就可以被釋放。這個做法的好處包含:
* 可以保證不被使用的空間正確且立即的被釋放，不具不確定性
* 相較於 tracing 機制也得益於生命週期的定義而不需要長時間的暫停主程式
反之，此方法(naive form 下)也具備以下缺點:
* 無法處理 cycle reference(A reference 到 B 且 B reference 到 A)，它們會忽相牽制對方導致 reference count 無法歸零
* 對每個 object 都需要額外空間來儲存 reference count，在 tracing 機制中，標註資訊則可以隱式的藏在引用的指標變量中
* 對 reference count 的頻繁更新可能導致效率的低下。尤其在多執行續環境下，reference count 的增加或減少為確保正確性可能需要 atomic operation，牽涉到對 count 的加鎖因此可能影響運行效率
## TGC
> [orangeduck/tgc](https://github.com/orangeduck/tgc)
tgc 是一個小型的 mark and sweep garbage collector，我們可以透過閱讀其程式碼更清楚的掌握 mark and sweep GC 相關的實作方式。
### `tgc_start`
```cpp
void tgc_start(tgc_t *gc, void *stk) {
gc->bottom = stk;
gc->paused = 0;
gc->nitems = 0;
gc->nslots = 0;
gc->mitems = 0;
gc->nfrees = 0;
gc->maxptr = 0;
gc->items = NULL;
gc->frees = NULL;
gc->minptr = UINTPTR_MAX;
gc->loadfactor = 0.9;
gc->sweepfactor = 0.5;
}
```
* 以一個 local 變數的位置做為 `*stk` 傳遞，將一個 `tgc_t *gc` 結構做初始化
* `gc->nitems` 是目前所維護的 object 數量
* `gc->nslots` 則是目前 gc 可以維護的 object 最大數量
* `gc->items` 是一個動態配置的 `tgc_ptr_t` item 陣列，每個 item 都將會維護一個被配置的空間
* `UINTPTR_MAX` 是 `uintptr_t` 型態的最大值，後者是一個可以有效轉型成 `void*` 的指標得以轉型而成的型別，可以看做是指標指向的位址(詳見 C 語言規格書 )
> **7.20.1.4 Integer types capable of holding object pointers**
>
> The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer
>
> **uintptr_t**
### `tgc_alloc` / `tgc_alloc_opt`
```cpp
void *tgc_alloc(tgc_t *gc, size_t size)
{
return tgc_alloc_opt(gc, size, 0, NULL);
}
void *tgc_alloc_opt(tgc_t *gc, size_t size, int flags, void(*dtor)(void*))
{
void *ptr = malloc(size);
if (ptr != NULL) {
ptr = tgc_add(gc, ptr, size, flags, dtor);
}
return ptr;
}
```
### `tgc_add`
```cpp
static void *tgc_add(tgc_t *gc,
void *ptr,
size_t size,
int flags,
void(*dtor)(void*))
{
gc->nitems++;
gc->maxptr = ((uintptr_t)ptr) + size > gc->maxptr ?
((uintptr_t)ptr) + size : gc->maxptr;
gc->minptr = ((uintptr_t)ptr) < gc->minptr ?
((uintptr_t)ptr) : gc->minptr;
if (tgc_resize_more(gc)) {
tgc_add_ptr(gc, ptr, size, flags, dtor);
if (!gc->paused && gc->nitems > gc->mitems) {
tgc_run(gc);
}
return ptr;
} else {
gc->nitems--;
free(ptr);
return NULL;
}
}
```
* `gc->nitems` 是分配出的 object 總量，將其加一
* `gc->maxptr` 和 `gc->minptr` 記錄由 gc 所紀錄的指標範圍，在此範圍外的指標空間理應非 gc 的管理範圍
* `tgc_add_ptr` 將指標加入 gc 中維護
* 在 gc 非暫停狀態下 (`!gc->paused`) 且
* 如果 `tgc_resize_more` 返回 0 表示 gc 的 slot 需要增加但是記憶體配置出現問題，間接導致了配置的要求失敗(返回 NULL)
### `tgc_resize_more`
```cpp
static size_t tgc_ideal_size(tgc_t* gc, size_t size) {
size_t i, last;
size = (size_t)((double)(size+1) / gc->loadfactor);
for (i = 0; i < TGC_PRIMES_COUNT; i++) {
if (tgc_primes[i] >= size) { return tgc_primes[i]; }
}
last = tgc_primes[TGC_PRIMES_COUNT-1];
for (i = 0;; i++) {
if (last * i >= size) { return last * i; }
}
return 0;
}
static int tgc_resize_more(tgc_t *gc) {
size_t new_size = tgc_ideal_size(gc, gc->nitems);
size_t old_size = gc->nslots;
return (new_size > old_size) ? tgc_rehash(gc, new_size) : 1;
}
```
* `tgc_ideal_size` 根據直至目前所需維護的 object 數量(`size`)計算整個 gc 目前需要預先分配出的 slot(`gc->nslots`)，slot 數量會先根據 `tgc_primes` 的 table 成長，直到超越 table 中的最大值後變成倍數成長
* 如果計算出的 ideal size 大於原本的 slot 數量，需要透過 `tgc_rehash` 去擴充 gc 的 slot 數量和相關結構，否則直接回傳 1 即可
### `tgc_rehash`
```cpp
static int tgc_rehash(tgc_t* gc, size_t new_size) {
size_t i;
tgc_ptr_t *old_items = gc->items;
size_t old_size = gc->nslots;
gc->nslots = new_size;
gc->items = calloc(gc->nslots, sizeof(tgc_ptr_t));
if (gc->items == NULL) {
gc->nslots = old_size;
gc->items = old_items;
return 0;
}
for (i = 0; i < old_size; i++) {
if (old_items[i].hash != 0) {
tgc_add_ptr(gc,
old_items[i].ptr, old_items[i].size,
old_items[i].flags, old_items[i].dtor);
}
}
free(old_items);
return 1;
}
```
* 根據 `new_size` 更新 `gc->nslots`，然後將舊的 item 移動逐一移動到新的 item slot 中，返回 1
* 如果 calloc 無法在配置更多空建，則擴增失敗，返回 0
### `tgc_add_ptr`
```cpp
static size_t tgc_hash(void *ptr) {
return ((uintptr_t)ptr) >> 3;
}
static size_t tgc_probe(tgc_t* gc, size_t i, size_t h) {
long v = i - (h-1);
if (v < 0) { v = gc->nslots + v; }
return v;
}
static void tgc_add_ptr(tgc_t *gc,
void *ptr,
size_t size,
int flags,
void(*dtor)(void*))
{
tgc_ptr_t item, tmp;
size_t h, p, i, j;
i = tgc_hash(ptr) % gc->nslots; j = 0;
item.ptr = ptr;
item.flags = flags;
item.size = size;
item.hash = i+1;
item.dtor = dtor;
...
```
* 將 `ptr` 加入 gc 的維護中，首先透過 `tgc_hash(ptr) % gc->nslots` 可以從指標位址計算出對應的 slot index
* 可以看到 `tgc_hash` 就是直接捨去位址的後 3 個位元而已
* `item` 即將被加入某個 slot，其內容包含實際分配的指標 `ptr`、指定的 `flag`、分配的空間大小 `size`、其對應的 hash 值 `hash`(注意會是實際的 hash value + 1，0 被特別保留，可以間接代表不維護任何指標的 item)、以及物件被釋放時可能需要的 destructor `dtor`
```cpp
...
while (1) {
h = gc->items[i].hash;
if (h == 0) { gc->items[i] = item; return; }
if (gc->items[i].ptr == item.ptr) { return; }
p = tgc_probe(gc, i, h);
if (j >= p) {
tmp = gc->items[i];
gc->items[i] = item;
item = tmp;
j = p;
}
i = (i+1) % gc->nslots; j++;
}
}
```
* 接著遞迴找到實際要放入的 slot，這是因為指標位置的 hash 值可能與其他指標有 [collision](https://en.wikipedia.org/wiki/Collision_(computer_science))
* 從 `i` 對應的 slot 開始，如果 `gc->items[i].hash` 為 0 表示 slot 可以插入，則插入並返回
* `if (gc->items[i].ptr == item.ptr)` 如果指標已經目標位置，返回
* 如果 collision 發生，從 `tgc_probe` 後的程式碼主要是用來找尋下一個位置，可以看出 probe 方式是 linear probing
### `tgc_mark`
```cpp
static void tgc_mark(tgc_t *gc) {
size_t i, k;
jmp_buf env;
void (*volatile mark_stack)(tgc_t*) = tgc_mark_stack;
if (gc->nitems == 0) { return; }
for (i = 0; i < gc->nslots; i++) {
if (gc->items[i].hash == 0) { continue; }
if (gc->items[i].flags & TGC_MARK) { continue; }
if (gc->items[i].flags & TGC_ROOT) {
gc->items[i].flags |= TGC_MARK;
if (gc->items[i].flags & TGC_LEAF) { continue; }
for (k = 0; k < gc->items[i].size/sizeof(void*); k++) {
tgc_mark_ptr(gc, ((void**)gc->items[i].ptr)[k]);
}
continue;
}
}
```
* 將函式 `tgc_mark_stack` 初始化成一個 volitile 的 function pointer `mark_stack`，這是為了避免編譯器 inline `tgc_mark_stack` 這個函數
* for 迴圈首先將每個 flag 是 `TGC_ROOT` 的 items 做標註
* `TGC_ROOT` 表示 item 必須由程式撰寫者手動釋放而 gc 不會回收之
* 如果這個 root items 同時不是 `TGC_LEAF` 的話(表示指標往下可能指向另一個指標，這個 flag 可以讓 gc 不需要額外的工作檢查這個事實)，則往下標註可能的 chain
* 內層的 for 迴圈
* 先看看下圖展示的情境: 假設在 heap 上分配一個空間 $R$，位址範圍是 0x1000 ~ 0x103F，然後在 heap 上再分配一個指標 `void *` 大小的空間，指向 $R$ 的 0x1020 處，那麼追蹤時我們需要把 $R$ 空間按照 `void *` 大小切割並一一追蹤，才有機會得知有人 reference 到 0x20 這個位置
* 再回來看 `((void**)gc->items[i].ptr)[k]` 作為參數輸入的目的，就是將原本指標指向的空間切成 `void *` 的陣列，然後再一一去檢查這些 `void *` 是否被其他 gc 所維護的指標所指向，若是需要標註為 reachable
```cpp
...
memset(&env, 0, sizeof(jmp_buf));
setjmp(env);
mark_stack(gc);
}
```
* 這裡 [`setjmp`](https://man7.org/linux/man-pages/man3/setjmp.3.html) 的目的是將 register 的內容都加入 stack 中，如此一來 `mark_stack` 就可以正確的標註所有 local variables 所可以操作到的空間
### `tgc_mark_stack`
```cpp
static void tgc_mark_stack(tgc_t *gc) {
void *stk, *bot, *top, *p;
bot = gc->bottom; top = &stk;
if (bot == top) { return; }
if (bot < top) {
for (p = top; p >= bot; p = ((char*)p) - sizeof(void*)) {
tgc_mark_ptr(gc, *((void**)p));
}
}
if (bot > top) {
for (p = top; p <= bot; p = ((char*)p) + sizeof(void*)) {
tgc_mark_ptr(gc, *((void**)p));
}
}
}
```
* `mark_stack` 將 stack 所涵蓋的範圍視為是一個 `void *` 陣列，並檢查這些陣列元素所指向的內容是否 reachable
* 考慮 stack 是向位址高還是低處成長並往對應的方向搜索
### `tgc_mark_ptr`
* `*ptr` 可以想成是一段空間，則 `tgc_mark_ptr` 的作用就是檢查此空間是否在 gc 的維護中，如果是則標註之
* `*ptr` 空間的內容可能是其他指標，那麼如果 `*ptr` reachable，其所包含的指標所指內容也應為 reachable，因此遞迴呼叫 `tgc_mark_ptr` 標註整個連鎖
```cpp
static void tgc_mark_ptr(tgc_t *gc, void *ptr) {
size_t i, j, h, k;
if ((uintptr_t)ptr < gc->minptr
|| (uintptr_t)ptr > gc->maxptr) { return; }
i = tgc_hash(ptr) % gc->nslots; j = 0;
```
* 最初的 if 考慮 `ptr` 的位址範圍，如果不是在 gc 所記錄的分配範圍中，這些空間都是 unreachable
```cpp
while (1) {
h = gc->items[i].hash;
if (h == 0 || j > tgc_probe(gc, i, h)) { return; }
if (ptr == gc->items[i].ptr) {
if (gc->items[i].flags & TGC_MARK) { return; }
gc->items[i].flags |= TGC_MARK;
if (gc->items[i].flags & TGC_LEAF) { return; }
for (k = 0; k < gc->items[i].size/sizeof(void*); k++) {
tgc_mark_ptr(gc, ((void**)gc->items[i].ptr)[k]);
}
return;
}
i = (i+1) % gc->nslots; j++;
}
}
```
* 迴圈標註整個連鎖
### `tgc_sweep`
```cpp
void tgc_sweep(tgc_t *gc) {
size_t i, j, k, nj, nh;
if (gc->nitems == 0) { return; }
gc->nfrees = 0;
for (i = 0; i < gc->nslots; i++) {
if (gc->items[i].hash == 0) { continue; }
if (gc->items[i].flags & TGC_MARK) { continue; }
if (gc->items[i].flags & TGC_ROOT) { continue; }
gc->nfrees++;
}
```
* 紀錄需要被釋放的空間總數
:::danger
如果實作沒有錯誤，`TGC_ROOT` 的檢查應該可以排除?(在 mark 階段已經被標註)
:::
```cpp
gc->frees = realloc(gc->frees, sizeof(tgc_ptr_t) * gc->nfrees);
if (gc->frees == NULL) { return; }
i = 0; k = 0;
while (i < gc->nslots) {
if (gc->items[i].hash == 0) { i++; continue; }
if (gc->items[i].flags & TGC_MARK) { i++; continue; }
if (gc->items[i].flags & TGC_ROOT) { i++; continue; }
gc->frees[k] = gc->items[i]; k++;
memset(&gc->items[i], 0, sizeof(tgc_ptr_t));
j = i;
while (1) {
nj = (j+1) % gc->nslots;
nh = gc->items[nj].hash;
if (nh != 0 && tgc_probe(gc, nj, nh) > 0) {
memcpy(&gc->items[ j], &gc->items[nj], sizeof(tgc_ptr_t));
memset(&gc->items[nj], 0, sizeof(tgc_ptr_t));
j = nj;
} else {
break;
}
}
gc->nitems--;
}
```
* `gc->frees` 是一個 free list，遞迴將那些未被標註的 items 加入 free list
* 內層的 while 迴圈嘗試將偏離原本 hash value 應當對應的 slot(`tgc_probe` > 0)的 item 移動回來，這讓之後查 hash table 時 miss 的次數減少
* 表示總 item 數量的 `gc->nitems` 也要隨之減一
:::danger
`gc->frees` 既然在 sweep 結束後都會被釋放掉，`realloc` 有特別的意義嗎?
:::
```cpp
for (i = 0; i < gc->nslots; i++) {
if (gc->items[i].hash == 0) { continue; }
if (gc->items[i].flags & TGC_MARK) {
gc->items[i].flags &= ~TGC_MARK;
}
}
```
* 將所有的標註清除
:::danger
這個步驟有沒有可能和前一個迴圈做合併?
:::
```cpp
tgc_resize_less(gc);
gc->mitems = gc->nitems + (size_t)(gc->nitems * gc->sweepfactor) + 1;
for (i = 0; i < gc->nfrees; i++) {
if (gc->frees[i].ptr) {
if (gc->frees[i].dtor) { gc->frees[i].dtor(gc->frees[i].ptr); }
free(gc->frees[i].ptr);
}
}
free(gc->frees);
gc->frees = NULL;
gc->nfrees = 0;
}
```
* `tgc_resize_less` 根據變少的 item 數量縮減 gc 需要的 slot 空間
* `gc->mitems` 是在新增空間(`tgc_add`)時判斷是否先啟動 gc 機制回收的參數，假設這次 sweep 時的 `nitems` 為 $k$，到下一次啟動前增加了 $K$ / 2 + 1 的空間的話 `tgc_add` 的時候就會啟動 mark and sweep
* 呼叫 free list 中的 `ptr` 的 destructor 並且釋放
* 最後釋放 free list 並重置相關變數
### `tgc_free`
```cpp
void tgc_free(tgc_t *gc, void *ptr) {
tgc_ptr_t *p = tgc_get_ptr(gc, ptr);
if (p) {
if (p->dtor) {
p->dtor(ptr);
}
free(ptr);
tgc_rem(gc, ptr);
}
}
```
* `tgc_get_ptr` 取得對應的 item，啟動其 destructor 並且釋放
### `tgc_rem`
```cpp
static void tgc_rem(tgc_t *gc, void *ptr) {
tgc_rem_ptr(gc, ptr);
tgc_resize_less(gc);
gc->mitems = gc->nitems + gc->nitems / 2 + 1;
}
```
* `tgc_rem` 做將此 `ptr` 釋放後的調整，類似在 sweep 階段移動偏移的 item、調整 slot 總數量、 重設 `gc->mitems` 參數等工作
### 小結
從程式碼的設計，我們可以發現此 garbage collector 採取 conservative(保守) 原則，stack / heap 的內容會依據指標長度切分並當成是一個個指標來檢查，因此檢查為 reachable 的物件有機會實際上在未來都不會操作到，但卻被保留，比方說:
* 某個空間用來儲存數個 int 值，但這些 int 值視為指標位置時剛好對應 gc 維護的空間中，該空間會被標為 reachable
* `tgc_mark_stack` 中的涵蓋的範圍可能剛好包含已經脫離 scope 的某個函數曾經用到的地方，但因為後續的操作都沒覆蓋到該位置的內容，因此檢查時仍然保留該函數曾經 reachable 的空間
相關的 mechanism 也值得多加思考，例如 slot 的成長指數、`tgc_run` 的啟動時機、hash table 的改進等等。總而言之，通過這個精簡的實作，我們初步理解了一個 garbage collector 的運作行為，其中對於空間與時間效率需要考量的實作方式，算是一個很不錯的起點。
## Reference
> * [Days 11: 什麼是垃圾回收器？](https://ithelp.ithome.com.tw/articles/10204860)
> * [深入浅出垃圾回收（一）简介篇](https://liujiacai.net/blog/2018/06/15/garbage-collection-intro/)
> * [深入浅出垃圾回收（三）增量式 GC](https://liujiacai.net/blog/2018/08/04/incremental-gc/)
> * [V8 增量 GC 之三色标记](https://malcolmyu.github.io/2019/07/07/Tri-Color-Marking/)
## TODO
- [ ] 閱讀論文 [On-the-Fly Garbage Collection: An Exercise in Cooperation](https://lamport.azurewebsites.net/pubs/garbage.pdf)
- [ ] 閱讀論文 [A Unified Theory of Garbage Collection](https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf)
Sign in with Wallet
Connect another wallet