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

## 環境

* 4.19.36-1-MANJARO
* gcc (GCC) 8.3.0

## ogc 原理
### init , destroy
orc 的運作從函式 `gc_init` 開始，到函式 `gc_destroy` 被呼叫時結束，整個 garbage collector 使用一個全局變數 `__gc_object` 記錄狀態，`__gc_object` 的類型定義於 `gc_internal.h` 中，如下：

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

在這個結構中，變數 `stack_start` 用於記錄整個程式 stack 的起始位置，`ptr_map` 為一個用於記錄以分配記憶體的 hash table，`ptr_num` 記錄以分配記憶體塊的數量，`limit` 用於限制 garbage collector 中容許存在的以分配記憶體塊的上限，當分配的記憶體塊上限大於此值時，garbage collector 就會開始 garbage collection，`ref_count` 記錄函式 `gc_init` 被呼叫的次數，以決定當函式 `gc_destroy` 呼叫時採取的行為，`min`，`max` 記錄 heap 的上下界限，可用來判斷要操做的記憶體是否合法，而變數 `globals` 的用途暫時還不清楚
再看到函式 `gc_init` 與 `gc_destroy` ：

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

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

可以發現都只是在操作 `__gc_object` 中記錄的資料

### mark , sweep
ogc 採用 [Mark and Sweep](https://www.youtube.com/watch?v=2XKifr16o7Y)，在每次執行函式 `gc_run` 時會先呼叫函式 `gc_mark_stack` 檢查 stack 中是否存在之前分配的記憶體塊的位址，若找到就代表該記憶體塊仍在使用中因此其標記為 `true`，之後呼叫函式 `gc_sweep` 將未被標記為 `true` 的記憶體塊釋放，此機制的關鍵函式在 `gc_mark` 與 `gc_sweep`，其實作如下：

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

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