# 2019q1W7下: 陳冠廷

### 測驗 `1`
程式碼中利用 `__gc_object.ptr_map[i]` 加速 linked list 存取
每當呼叫 `gc_alloc` 時，會在 hashmap 中對應的 linked list 插入一個`gc_list_t` 用於保存 malloc 的地址以及大小和一個 marked 的 flag，在稍後的 GC 流程中會使用到(注意在建立時不會設定 marked)
除此以外也會將 `__gc_object.ptr_num` 的值加 1

:::warning
搭配解釋 `HASH` 巨集的用法
:notes: jserv
:::

在 `__gc_object.ptr_num >= __gc_object.limit` 的情況下呼叫 `gc_alloc()` 就會觸發 `gc_run()` 執行 garbege collection，做法是從目前的 stack 頂端也就是下方程式碼中的 `&tmp` 開始，掃到最一開始在 main 中設定的 `__gc_object.stack_start`

void gc_mark_stack(void)
{
    uint8_t tmp;
    gc_mark(__gc_object.stack_start, &tmp);
    ...
}

int main(int argc, char *argv[])
{
    gc_init(&argc, 1);
    ...
}

將存在這個區段中的任意值取出來作為指標，接著到 hashmap 中查詢該指標是否是使用者透過 `gc_alloc()` 所配置的記憶體，若是則標註 `idx->data.marked` 並以相同方式繼續在該記憶體區段中 dfs 搜尋，若非就不做任何改變
:::warning
其實只是從`gc_mark_stack()`的 stack frame 隨便挑一個位置開始算到 `main()` 結束，所以實際上若是 stack 上有殘留沒被清除或覆蓋掉的`gc_alloc()`指標就會多算
:::

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

接著 `gc_sweep()` 會遍歷 `__gc_object.ptr_map` 將沒有被標記 (marked) 的指標 free 掉，並刪除 list 中該節點，要注意的是此時若是遇到有標記的指標會將該標記清除，至此完成一次的 GC

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