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

### ref_count
原先看程式碼時，發現`ref_count` 只有在 `gc_init()` 和 `gc_destroy()` 之中被使用，分別做加 1 和減 1 的操作，且 `gc_init()` 和 `gc_destroy()` 的呼叫時機，只有在測試程式中的 main 函式開始和結束時，猜測一個 garbage collector（一個 `__gc_object`） 可能被多個 process 使用到，而 `ref_count` 記錄的就是這些 process 的個數。
然而考量 garbage collector 用來回收 heap 中的空間，其使用場景較可能是被多個 thread 共用，`ref_count` 則是記錄 thread 個數。同時可以發現目前程式碼中 `gc_init()` 呼叫時機，以及結構 `gc_t` 其實尚不適用 multi-thread 環境

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

:::warning
先標註 GC 程式中的 critical section，並且依據 CS:APP 第 12 章的手法去視覺化展現
:notes: jserv
:::

### gc_alloc( )
`gc_t` 的資料成員 `ptr_map[ ]` 用來維護所有 `gc_alloc()` 配置的記憶體空間。 `ptr_map[ ]` 是一個 hash table ，以 singly linked list chainging 處理 collision ，hash funtion 為 `HASH(ptr) % PTR_MAP_SIZE` ，其中 `ptr` 為呼叫 malloc 的回傳值。
每一次呼叫 `gc_alloc()` 配置記憶體空間時，會呼叫 `gc_list_add()` 建立一 `gc_list_t` 型別的物件 `elem` ，並根據配置的記憶體位址(即 `ptr`) 插入 `ptr_map[ ]` 中對應的 linked list

簡述流程：
gc_alloc() -> malloc() -> 根據 malloc 回傳地址找到適當位置 -> gc_list_add()，將 elem 插入 linked list

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

### mark and sweap

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

### mutithread

在 mutithread 環境中，某一條 thread 呼叫 mark() 只會 mark 這一條 thread 的 reachable 的 object ，若接著直接呼叫 sweap() ，會把其他 thread 的 reachable object 也回收掉。
為了解決上述問題，先採取比較直覺但看起來沒效率的作法，每一次 mark 都檢查所有 thread 的 stack ，mark 每個 thread 的 reachable object 之後才 sweap。
原來的程式碼中 mark 時需要有 stack 的起始位置 (__gc_object.stack_start) 和目前 stack pointer 的位置 (gc_mark_stack 中的 tmp)。multithreading 版本中，呼叫 `pthread_attr_getstack()` 得到 stack 的起始位置 (stackaddr) 和大小 (stacksize);但是 mark 時不知如何拿到其他 thread 目前 stack pointer 的位置，暫時先用很笨的方法，用 (stackaddr + stacksize) 代替
(參考 [get a thread's stack address](https://stackoverflow.com/questions/8729384/can-i-get-a-threads-stack-address-from-pthread-self) )

void gc_init(size_t limit)
{
    if(__gc_object.ref_count == THREAD_MAXNUM){
        return;
    }
    if(__gc_object.ref_count == 0){
        __gc_object.limit = limit;
    }
    pthread_attr_t attr;
    void * stackaddr;
    size_t stacksize;

    pthread_getattr_np(pthread_self(), &attr);
    pthread_attr_getstack( &attr, &stackaddr, &stacksize );

    for(int i = __gc_object.ref_count; ; i = (i + 1) % THREAD_MAXNUM){
        if(!__gc_object.stack_start[i]){
            __gc_object.stack_start[i] = (uintptr_t)stackaddr;
	    __gc_object.stack_size[i] = stacksize;
        }
    }
    __gc_object.ref_count++;
}

void gc_mark_stack(void)
{
    //uint8_t tmp;
    for(int i=0; i < THREAD_MAXNUM; i++){
        if(!__gc_object.stack_start[i]){
            gc_mark(__gc_object.stack_start[i], __gc_object.stack_start[i] + __gc_object.stack_size[i]);
        }
    }
    ...
}