2019q1W7下: 劉正仁

測驗 1

OGC: Reference counting

OGC 中 reference counting 的機制相當簡單。利用 grep 查看程式碼中有那些地方更改到了 garbage collector 中 ref_count 的值，來進一步做程式碼的閱讀。

$ grep ref_count *.c -n
core.c:3:gc_t __gc_object = (gc_t){.ref_count = 0};
core.c:7:    if (__gc_object.ref_count) {
core.c:8:        __gc_object.ref_count++;
core.c:14:                         .ref_count = 1,
core.c:70:    __gc_object.ref_count--;
core.c:71:    if (__gc_object.ref_count <= 0) {
core.c:72:        __gc_object.ref_count = 0;

在其他程式碼中，開發者可能會多次呼叫 core.c 中的 gc_init，來代表使用（reference) 到 garbage collector。

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

在上述程式碼 3-6 行，為當已經有人使用了 garbage collector，其他人再次使用時，只會將 garbage collector 的 ref_count++，代表在其他程式碼中，有 ref_count 個地方使用到 garbage collector。

反之，當我們使用完 garbage collector 時，會呼叫 core.c 中 gc_destroy。這個函式很簡單，當 garbage collector 的 ref_count 減為 0 時，代表沒有人使用 garbage collector。程式碼就將由 garbage collector 控管的記憶體全部 free 掉。

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

OGC: Mark and sweep

程式碼中執行 mark & sweep 的動作在 core.c 中的 void gc_run(void)。

void gc_run(void)
{
    gc_mark_stack();
    gc_sweep();
}

gc_mark_stack 做完後，所有 reachable 的 memory block 都會被 mark。因此在接下來的 gc_sweep，這些 memory block 就不會被 free 掉，反之，沒有被 mark 的都會被 free 掉。

這邊觀看一下 gc_mark_stack.

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

程式碼第 4 行，程式碼呼叫 gc_mark，並傳入 __gc_object.stack_start, &tmp。用 test/dummy.c 這個測試碼，stack_start 為 &argc。

上述的 for 迴圈初始值會永遠保持 NULL，似乎是 BUG。我認為可以直接忽略。

$ grep stack_start *.c -n                                                                                                    
core.c:11:    __gc_object = (gc_t){.stack_start = ptr,
utils.c:36:    gc_mark(__gc_object.stack_start, &tmp);

再來看看 gc_mark 的行為

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_list_t 的指標，若有找到則查看此 memory block 有否被 mark，若無則 mark。然後繼續遞迴的搜索此 memory block 有沒有 gc_list_t 的指標。

以下用是上述程式碼的圖解

最後是 gc_sweep 做 garbage collection 的操作。

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

程式碼還算直覺，查看所有由 garbage collector 控管的 memory block，若其沒有被 mark (!e->data.marked)，就會被 free 掉，反之則將 marked 的 memory block 變為 unmark，留待下一輪的 garbage collection 處理。

tags: sysprog2019