# 2019q1 Homework6 (gc)
contributed by < `rebvivi` >
###### tags: `linux2019`
* [F10: gc](https://hackmd.io/s/SkZpf5HiE)

## 作業要求
- 完成 第 7 週測驗題 (下) 所要求的 mark & sweep garbage collection 原理解說和程式碼分析
- 改進 ogc 程式，使其得以在多執行緒的環境下正確運作
- 比較其他 GC 實作，提出 ogc 改進計畫並落實

## mark & sweep garbage collection 原理解說和程式碼分析

>如果呼叫 `gc_init()` 代表使用 garbage collector
>
>在 `gc_init()` 會建立 `__gc_object` ，為了之後 `gc_alloc()` allocate memory
>

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

>當我們不需要使用 garbage collector 時，我們就會呼叫 `gc_destroy()`

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_alloc()` 會 allocate 一個 user 所要求的 memory size
>
>>在 16 行的地方，會在對應到的 `ptr_map` bucket 中新增 `p`，`p` 裡頭紀錄著我們 malloc 的起始位址、 malloc 的 size 、 一個紀錄是否被 marked 的欄位
>>
>>接著在 17 行的地方將 `__gc_object.ptr_num` +1
>>
>>第18行，如果 `__gc_object.ptr_num >= __gc_object.limit` ，也就是某個臨界數值，就會觸發 `gc_run()`，開始執行 mark & sweep garbage collection
>>

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

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

>在 `gc_alloc` 的第 16 行，我們是用 `HASH(ptr) % PTR_MAP_SIZE` 的方式找到對應到的 `ptr_map` bucket
>
>
>==以下是我的推測==
>`ptr >> 3` 往右 shift 3 個 bit 是因為取 high-order bit 會讓數字變得更接近 random
>，減少 collision，讓整個 hash function 更接近 uniform hash function
>
>
>`HASH(ptr) % PTR_MAP_SIZE` ，總共有編號 0~63 個 bucket ，會 mod `PTR_MAP_SIZE` 是為了分配到對應的 bucket

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

---
>第 3 行，宣告了一個 `tmp` ， `tmp` 所在的 address 會是已經使用過的 address 空間的後面
>
>第 4 行使用 `gc_mark()` ，將目前使用的 stack 的 starting address 到 ending address mark 起來

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()` 會 free 掉沒有被 marked 的物件的空間
>
>第 7 行的 if 中，如果物件沒有被 marked ，就會將它 free 掉
>
>第 11 行的 else 中，如果物件有被 marked ，就會將它改成沒有被 marked 的狀態

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