# 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`。
:::danger
上述的 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`