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

搭配解釋 HASH 巨集的用法

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 搜尋，若非就不做任何改變

其實只是從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++;
        }
    }
}