# 2019q1 Homework6 (gc)
contributed by < `afcidk` >

* [F10: gc](https://hackmd.io/s/SkZpf5HiE)

## 資料結構
### \_\_gc\_ptr

struct __gc_ptr { 
    uintptr_t start;
    size_t size;
    bool marked;
};

gc_ptr 紀錄的是可能被配置過的記憶體區塊，我們需要開頭的位址、長度以及是否被 mark 過。

### \_\_gc\_list

struct __gc_list { 
    struct __gc_list *next;
    gc_ptr_t data;
};

gc_list 是一個 linked list，把所有的 gc_ptr 串起來。

### \_\_gc

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;
};

gc 是在整個程式裏面唯一的一個 garbage collector
* stack_start
gc 執行時起始的 stack 位址，在 test 中我們直接取 argc 的位址當作 stack 的起始位址。之後在執行 `gc_run` 的時候會以 stack_start 當起點開始掃。
* ptr_map
ptr_map 把記憶體分成數個相同大小的區塊來儲存，如果遇到已經被佔用的 ptr_map，會透過 linked list 來儲存起來。這樣做可以減少純粹使用 linked list 時搜尋需要花費的時間。
* ptr_num
當前的 gc 紀錄的 gc_ptr 數量，如果超過 limit 就會執行 garbage collect。
* limit
gc 中 garbage collect 的下限，如果當前 gc 紀錄的 gc_ptr 數量超過 limit 的話就會執行 garbage collect（gc_run）。
* ref_count
gc object 在整份程式中只能有一份 instance。ref_count 是用來紀錄 gc 當前有幾份 reference，當最後一個 reference 被刪除時，需要順帶把其佔用的記憶體空間也釋放掉。
* min, max
min 還有 max 用來標示當前 gc 維護的記憶體位址範圍。在 `gc_ptr_index` 中會先判斷我們傳入的指標是否在範圍內，若不是則不必尋找且回傳 NULL。

* globals
觀察程式碼，發現 globals 只可能被指派成 NULL, 推測一開始應該是想要對 global variable 做 garbage collection，但是還沒寫好或是因為某些原因忘記刪除而已。
> 說是這樣說，但是我想不太到 global variable 應該被 gc 的時間點

./src/utils.c:    for (gc_list_t *e = __gc_object.globals; e; e = e->next) {
./src/core.c:                         .globals = NULL};
./src/gc_internal.h:    gc_list_t *globals;