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

###### tags: `sysprog2019_q1`

## 作業要求
依據 [F10: gc](https://hackmd.io/s/SkZpf5HiE)
* 完成 [第 7 週測驗題 (下)](https://hackmd.io/s/Hy8aBIgYV) 所要求的 mark & sweep garbage collection 原理，解說和程式碼分析，需要涵蓋 reference counting 的實作和探討已有的缺陷;
* 改進 ogc 程式，自 [ogc](https://github.com/sysprog21/ogc) fork 出你的 repository，使其得以在多執行緒的環境下正確運作
* 比較其他 GC 實作，提出 ogc 改進計畫並落實
* 在 Linux 核心指出類似的 garbage collection 實作

## 開發紀錄
從 dummy.c 中的 main() 觀察 OGC 的運作機制，在剛開始的 gc_init() 中初始化一個全域的 gc_t 結構變數，並每次呼叫到 gc_init() 時 ref_count 就加一。
* ref_count ： 紀錄使用到此全域 `__gc_object` 的程式數量
* stack_start ： 指定 ptr 做為執行 gc 時的起始位置
* ptr_num : 紀錄配置記憶體的次數
* limit : 限制配置記憶體的次數
* ptr_map ： 用一個 hash table 紀錄每一次配置記憶體的相關資訊
* min, max : 紀錄目前 heap 的地址範圍

gc_t __gc_object = (gc_t){.ref_count = 0};

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

在使用 gc_alloc 配置記憶體空間並紀錄相關資訊，將這些資訊都存放在同一個 hash table 中，當 ptr_num >= limit 時啟動 gc。
* uintptr_t : 用於儲存指向 void 的指標，並可完整的再轉型回 void *。

依據 [C99 規格書](http://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 的說明
>7.18.1.4 Integer types capable of holding object pointers
>intptr_t :
The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer.

void *gc_alloc(size_t size)
{
    uintptr_t ptr;
    if (!(ptr = (uintptr_t) malloc(size)))
        return NULL;

    gc_ptr_t p = (gc_ptr_t){
        .start = ptr,
        .size = size,
        .marked = true,
    };
    if (__gc_object.min > ptr)
        __gc_object.min = ptr;
    if (__gc_object.max < ptr + size)
        __gc_object.max = ptr + size;
    gc_list_add(&__gc_object.ptr_map[HASH(ptr) % PTR_MAP_SIZE], p);
    __gc_object.ptr_num++;
    if (__gc_object.ptr_num >= __gc_object.limit)
        gc_run();
    return (void *) ptr;
}

hash funtion 為 `HASH(ptr) % PTR_MAP_SIZE`，當發生 collision 的時，則是以 singly linked list 的方式處理(Separate Chaining)。

#define HASH(ptr) ((uintptr_t) ptr >> 3)

void gc_list_add(gc_list_t **begin_list, gc_ptr_t data)
{
    if (!begin_list)
        return;

    gc_list_t *elem = malloc(sizeof(gc_list_t));
    *elem = (gc_list_t){.data = data, .next = *begin_list};
    *begin_list = elem;
}

接著這裡實作 gc 的方式為 mark & sweep garbage collection algorithm。

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

首先在 tmp 的 stack 位置跟 `__gc_object.stack_start` 作比較，為了確保 `stack_start` 小於 tmp。(因為後續走訪 stack 的方式會從記憶體的低位置往記憶體的高位置)
stack_start 接著到 hash table 中尋找是否是透過 gc_alloc() 所配置的記憶體空間，若是的話則將 marked 設為 1，直到走訪完整個記憶體區段。
發現第 5 行因為整個程式從未賦值給 `__gc_object_globals`，使的這個 for 迴圈不會被執行到。

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

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() 中會走訪整個 ptr_map 並主要做2件事。
* marked 為 1 : 將其設為 0
* marked 為 0 : 將其釋放掉並從 ptr_map 中移除

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

在 dummy.c 中的 main() 最後會呼叫 gc_destroy()，對 ref_count 做減一的動作並檢查是否還有其他程式在使用，若沒有其他程式再使用的話則釋放整個 OGC 管理到的記憶體。

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

### 多執行緒版本