期末報告：GC

# 期末報告：GC contributed by <`TWPLrh`, `chengWei1123`> ## Goal 重做 [gc](https://hackmd.io/@sysprog/SkZpf5HiE?type=view) 作業，符合所有指定要求並彙整 [其他同學的成果](https://hackmd.io/@sysprog/S1Syl5RiV?type=view) ## Mark and Sweep 的實作 ### 概念 Mark and Sweep 分為 mark 和 Sweep 兩個階段 - Mark 階段：從 root set（ stack & globals list ）遞迴地拜訪可到達的記憶體區段，並將之標記 - Sweep 階段：拜訪所有記憶體區段（ ptr_map 中所有節點），並將沒被標記到的從 heap 中釋放如下圖 ![](https://i.imgur.com/phxlQhD.gif) ### 程式實作 #### 資料結構 ```c=1 struct __gc_ptr { uintptr_t start; size_t size; bool marked; }; ``` 紀錄一段記憶體空間的資訊 - start: 起始位置 - size: 區段大小 - marked: 有無被標記 ```c=1 struct __gc { void *stack_start; gc_list_t *ptr_map[PTR_MAP_SIZE]; size_t ptr_num; size_t limit; size_t ref_count; uintptr_t min, max; gc_list_t *globals; }; ``` - `stack_start`: 呼叫 gc_init 的 function 在 stack 上的位置，用來作為 root set 之起始位置 - `ptr_map` : 放 `__gc_object` 中 ptr 的 hash table - `ptr_num` : `__gc_object` 內 ptr 的數量 - `limit` : 當 ptr_num 大於等於 limit 時開始執行 `gc_run()` - `ref_count` : `__gc_object` 在 `gc_init()` 時會加 1 - `min, max` : `__gc_object` 內 ptr 所在的最小及最大的位置 - `globals` : `__gc_object` 內放全域變數的 singly-list #### gc_init() ```c=1 void gc_init(void *ptr, size_t limit) { if (__gc_object.ref_count) { __gc_object.ref_count++; return; } __gc_object = (gc_t){.stack_start = ptr, .ptr_map = {NULL}, .ptr_num = 0, .ref_count = 1, .limit = limit, .min = UINTPTR_MAX, .max = 0, .globals = NULL}; } ``` - 若 `__gc_object` 已被初始化，將 `ref_count` + `1`，否則就初始化。 ```c int main(int argc, char *argv[]) { gc_init(&argc, 1); .... } ``` - main function 中 argc 的位置作為 `stack_start` #### gc_destroy() ```c= void gc_destroy(void) { __gc_object.ref_count--; if (__gc_object.ref_count <= 0) { __gc_object.ref_count = 0; for (int i = -1; ++i < PTR_MAP_SIZE;) { gc_list_t *m = __gc_object.ptr_map[i]; while (m) { gc_list_t *tmp = m; free((void *) (m->data.start)); m = m->next; free(tmp); } __gc_object.ptr_map[i] = 0; } } } ``` - 和 `gc_init()` 相反，將 `gc_object` 的 `ref_count` - `1` - 如果 `ref_count <= 0` 則把 hash table 裏所有的節點和其資料清空 #### gc_alloc() ```c=1 void *gc_alloc(size_t size) { uintptr_t ptr; if (!(ptr = (uintptr_t) malloc(size))) return NULL; gc_ptr_t p = (gc_ptr_t){ .start = ptr, .size = size, .marked = true, }; if (__gc_object.min > ptr) __gc_object.min = ptr; if (__gc_object.max < ptr + size) __gc_object.max = ptr + size; gc_list_add(&__gc_object.ptr_map[HASH(ptr) % PTR_MAP_SIZE], p); __gc_object.ptr_num++; if (__gc_object.ptr_num >= __gc_object.limit) gc_run(); return (void *) ptr; } ``` - 用 malloc 分配大小 size 的記憶體位置 - `gc_ptr_t p` 儲存 ptr 的資訊 - 更新 `__gc_object` 的 min, max - 將 `p` 放入 hashtable 中 - 將 `ptr_num` 加 1 - 當 `ptr_num` 大於等於 `limit` 時開始執行 mark and sweep #### gc_mark_stack() ```c=1 void gc_mark_stack(void) { uint8_t tmp; gc_mark(__gc_object.stack_start, &tmp); for (gc_list_t *e = __gc_object.globals; e; e = e->next) { gc_mark((uint8_t *) (e->data.start), (uint8_t *) (e->data.start + e->data.size)); } } ``` - 宣告一個 tmp，用其位置做為 stack 的結束位置 - 對 local variable 做 mark - 對 global variable 做 mark #### gc_mark() ```c=1 void gc_mark(uint8_t *start, uint8_t *end) { if (start > end) swap_ptr(&start, &end); while (start < end) { gc_list_t *idx = gc_ptr_index((uintptr_t)(*((void **) start))); if (idx && idx->data.marked != true) { idx->data.marked = true; gc_mark((uint8_t *) (idx->data.start), (uint8_t *) (idx->data.start + idx->data.size)); } start++; } } ``` - start 到 end 代表要檢查的範圍，從 start 開始往 end 檢查 - `gc_ptr_index(ptr)` 回傳 ptr 在 hashtable 中節點的位置 - 如果找的到且沒被 marked 過的節點就將之 mark - 遞迴地檢查被標記的節點所代表的記憶體空間 #### gc_sweep() ```c=1 void gc_sweep(void) { for (int i = 0; ++i < PTR_MAP_SIZE;) { gc_list_t *e = __gc_object.ptr_map[i]; int k = 0; while (e) { if (!e->data.marked) { gc_mfree(e); e = e->next; gc_list_del(&__gc_object.ptr_map[i], k); } else { e->data.marked = false; e = e->next; } k++; } } } ``` - `gc_list_del(&__gc_object.ptr_map[i], k)` 刪除 hash table 中第 i 條 list 的第 k 個節點 - 何時要刪除？當 node 的 `marked` 是 `false` 時，代表該節點已經不是 reachable，則刪除 - 若該 node 依然是 reachable ，則將該節點的 `marked` 改為 `false` ## ogc 缺失 ### Global Pointer ```c=1 void gc_mark_stack(void) { uint8_t tmp; gc_mark(__gc_object.stack_start, &tmp); for (gc_list_t *e = __gc_object.globals; e; e = e->next) { gc_mark((uint8_t *) (e->data.start), (uint8_t *) (e->data.start + e->data.size)); } } ``` - `__gc_object` 中有 `gc_list_t globals` 在 trace 的過程發現 `gc_mark_stack()` 的 5~7 行是不會被執行到的，因而認為 `globals` 這個 list 是存放全域變數，所以我們寫了 `gc_add_global()` 把 `ptr` 加到 `globals` - [OGC - Fix global pointer.](https://github.com/TWPLrh/ogc/commit/4ebfdf875d2b93af163a2e4abc6ee0a3b39b8060) ### Reference Counting - 資料結構有包含 `ref_count`，但 Mark/Sweep 和 Reference Counting 是不同的演算法，所以不確定這裡的 `ref_count` 是代表什麼意思 - Reference Counting 是對每一個記憶體區塊做計數，如果某個變數被 reference N 次，那這個變數的 count 就是 N；如果 reference 的連結失效則 count 往下減 - 如果 count <= 0，就可以把這個記憶體區塊回收 ## 能在多執行序下執行的 ogc ### Mark 階段掃描每個 Thread 的 Stack ``` c=1 struct __gc { void *stack_start[THREAD_MAX]; size_t stack_size[THREAD_MAX]; gc_list_t *ptr_map[PTR_MAP_SIZE]; size_t ptr_num; size_t limit; size_t ref_count; uintptr_t min, max; gc_list_t *globals; }; ``` 使用 pthread library 做出的 thread 各自有一個 thread，所以我們改變 _gc_t 如上 - `THREAD_MAX`: Thread 數量的最大值 - `stack_start[THREAD_MAX]`: 每條 Thread 的 stack 之起始位置 - `stack_size[THREAD_MAX]`: 每條 Thread 的 stack 之大小 - `ref_count` : 目前有幾條 Thread 被 `__gc_object` 管理 ```c=1 pthread_attr_t attr; void * stackaddr; size_t stacksize; pthread_getattr_np(pthread_self(), &attr); pthread_attr_getstack(&attr, &stackaddr, &stacksize); __gc_object.stack_start[__gc_object.ref_count] = stackaddr; __gc_object.stack_size[__gc_object.ref_count] = stacksize; ``` 在 `gc_init()` 中加入上面的程式碼，變可以得到當下在執行的 thread 的 stack 資訊 ```c=1 for (int i = 0; i < __gc_object.ref_count; i++){ if(__gc_object.stack_start[i]){ gc_mark(__gc_object.stack_start[i], __gc_object.stack_start[i]+__gc_object.stack_size[i]); } } ``` 把 `gc_mark_stack` 裡中原本只能對單一執行緒處理的方式改成對各個執行緒處理 ### 對 __gc_object 做互斥存取控制在以下 function 的開頭和結尾分別加上 `pthread_mutex_lock()`, `pthread_mutex_unlock()` - `gc_init()` - `gc_alloc()` - `gc_free()` - `gc_run()` - `gc_destroy()` - `gc_add_global()` ## 與其他 gc 實作比較 ### Mark and Sweep 的缺點 `1.` Sweep 之後會造成 heap 區塊容易出現碎片，造成空間應用效率不彰 `2.` GC 運作時，會暫停程式的其他 Thread 執行( **Stop-the-world** ) ### 解決方法 : `1.` 使用 [Cheney's algorithm](https://en.wikipedia.org/wiki/Cheney%27s_algorithm) `2.` Incremental GC 的概念實作 [tricolor GC](http://sean.cm/a/tricolor-garbage-collector) ## Linux 核心中類似之 gc 實作 - [net/unix/garbage.c](https://elixir.bootlin.com/linux/latest/source/net/unix/garbage.c) - [fs/ubifs/gc.c](https://elixir.bootlin.com/linux/latest/source/fs/ubifs/gc.c) 兩種都類似於 Mark and Sweep，但在實作的方法有些不同 ## 統整其他同學的成果 ### casting [C99 standard](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) (7.18.1.4) 中提到： > 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 `uintptr_t` 可用於儲存指標(void \*)，並可完好無缺的再轉型回 void \* 。通常要 cast 到 uintptr_t 前我們會先轉到 void**，再對這個指標的指標做一次 dereference 以取得 > > void* 的內容，最後再轉到 uintptr_t >[flawless0714](https://hackmd.io/@flawless0714/SJYZfQuo4?type=view) ### `HASH` 用法 ```c gc_list_add(&__gc_object.ptr_map[HASH(ptr) % PTR_MAP_SIZE], p); ``` 使用 `HASH(ptr) % PTR_MAP_SIZE` 的方式找到對應到的 `ptr_map` bucket 其中 HASH define 如下 ``` c #define HASH(ptr) ((uintptr_t) ptr >> 3) ``` `ptr >> 3` 往右 shift 3 個 bit 是因為取 high-order bit 會讓數字變得更接近 random ，減少 collision，讓整個 hash function 更接近 uniform hash function `HASH(ptr) % PTR_MAP_SIZE` ，總共有編號 0~63 個 bucket ，會 mod `PTR_MAP_SIZE` 是為了分配到對應的 bucket >[rebvivi](https://hackmd.io/@1az9eaZgQwG38Qx2YiKXDw/r1u_y1IsV?type=view) ### thread’s stack address 要取得 thread's stack 的位置和大小，可以使用 - ```pthread_getattr_np(pthread_self(), &attr)``` - 先得到當前執行中的 thread's attribute - ```pthread_attr_getstack(&attr, &stackaddr, &stacksize)``` - 使用剛剛得到的 attribute 得到 stack address & stack size >[njjack](https://hackmd.io/@ev8EHwirRrap6evVCbZa7Q/Hkx_Q552N?type=view)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.