# 2019q1W7下: 吳宗遠
###### tags: `Linux 核心設計`
## 簡述 OGC 裡頭 reference counting 的運作機制，以及如何實作出 mark and sweep。
mark and sweep 會掃描整個記憶體兩次，第一次掃描時 mark 會判斷記憶體中的每一個物件是否仍在使用，如果仍在使用則做一個標記，否則就不做標記，第二次掃描 sweep 清除沒有做標記的物件。
透過兩條 list ，第一條是以分配記憶體的物件，第二條是正在用的物件。只要在第一條且不再第二條的物件，就清除掉。

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

可以看見執行 gc_run 就會執行 mark and sweep。

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

可以看到它依序走訪 list 每個元素，並對仍在使用的做標記。而 gc_mark 呼叫 gc_ptr_index

gc_list_t *gc_ptr_index(uintptr_t ptr)
{
    if (ptr > __gc_object.max || ptr < __gc_object.min)
        return NULL;

    int h = HASH(ptr) % PTR_MAP_SIZE;
    gc_list_t *e;
    if ((e = list_search(ptr, __gc_object.ptr_map[h])))
        return e;

    for (int i = 0; ++i + h < PTR_MAP_SIZE || (h > i);) {
        if ((h > i) && (e = list_search(ptr, __gc_object.ptr_map[h - i])))
            return e;
        if ((h + i < PTR_MAP_SIZE) &&
            (e = list_search(ptr, __gc_object.ptr_map[h + i])))
            return e;
    }
    return NULL;
}

:::warning
上述程式碼使用 `HASH` 巨集的考量點為何？
:notes: jserv
:::

透過 list_search 去尋找是否在第二條 list 中。

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

而 gc_sweep 去判斷 list 每個元素的 marked 是否為 false，如果為 false 代表沒有被標記，執行 gc_mfree 去釋放記憶體和 gc_list_del 把該元素從 list 刪除。

## 改寫 tests/string-separate.c，提供支援 GC 的 strdup 實作，允許在 gc_run() 呼叫後，釋放沒有參照到的記憶體。

char *my_strdup(char *s)
{
    if(!s)
        return NULL;
    char *c =s;
    int size = 0;
    while(*c) {
        size++;
        c++;
    }
    char *word = gc_alloc(sizeof(char)*(size+1));
    int i;
    for(i=0 ;i < size ;i++){
        *(word+i) = *(s+i);
    }
    *(word+size) = '\0';
    
    return word;
}
int main(int argc, char *argv[])
{
    gc_init(&argc, 1);

    char **sep = my_strsep("hello,world", ',');
    assert(sep);

    char *dup1 = my_strdup(sep[0]);
    char *dup2 = my_strdup(sep[1]);
    assert(dup1);
    assert(dup2);
    printf("%s\n", sep[0]);
    printf("%s\n", sep[1]);

    printf("d1 =%s\n", dup1);
    printf("d2 =%s\n", dup2);
    gc_run();

    gc_dump_internals();
    gc_destroy();

    return 0;
}

執行結果

*** Validating tests/string-separate ***
hello
world
d1 =hello
d2 =world
## GC internals ##
 - GC.ptr_map[12]:
   { ptr: 0x56402a0e2260, size: 24, marked: 0 }
 - GC.ptr_map[22]:
   { ptr: 0x56402a0e22b0, size: 6, marked: 0 }
 - GC.ptr_map[42]:
   { ptr: 0x56402a0e2350, size: 6, marked: 0 }
	[ Verified ]