2019q1W7下: 方鈺學

測驗 1

運作機制

延伸閱讀: Precise Garbage Collection for C 有 Linux 核心的 GC 使用案例

Contained two phases, Mark and Sweep.

Mark Phase

從 root 開始，找尋 可到達 的物件。 ( Reachable Objects )
標記 可到達 的物件。

Sweep Phase

從 heap 中，找尋未被標記的物件( Unreachable Objects )，即需要被清除的物件。
將未被標記的物件加入到 free list 中，準備清除。
將已被標記的物件重置為未被標記，以利下次的清掃。

如何實作

簡單實作 Mark

1. 建立訪問清單 todo 將所有 root 中的物件加入。
2. 當 todo 中有物件時，執行以下3~4。
3. 從 todo 中選任一物件 v ，將其除外於 todo。
4. 如果 v 未被標記，標記 v ，將所有 v 包含的物件放到 todo 中。

簡單實作 Sweep

1. 物件 p 從 heap 的最底層物件開始。
2. 當 p 還不是 top 的時候，執行以下3~5。
3. 如果 p 已被標記，則將其改為未標記。
4. 反之，將 p 的記憶體區塊加到 free list 中，準備清除。
5. 將 p 改為在 heap 中上一層的物件。 ( using p <- p + sizeof(p) )

問題點 1

• 需要清除時，通常表示沒有記憶體空間。
• 但是， Mark 階段需要記憶體空間去創造訪問清單( todo ) 。
• 訪問清單( todo )無法預測大小，因此無法預先保留。

解決方法

• 應用 pointer reversal ，用 depth first search 取代訪問清單。

問題點 2

• 有些物件沒有指標的空間。

解決方法

• 使用一個暫存器記憶其 parent 位置，就可以不用 pointer reversal 也能執行 depth firsth search 。

測驗 2

string-separate.c :

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "gc.h"

#define IS_DEL(c, d) (c == d)

static int count_words(char *s, char delimiter)
{
    int i = -1, words = 0;
    while (s[++i])
        if (((i != 0 && IS_DEL(s[i], delimiter) &&
              !IS_DEL(s[i - 1], delimiter)) ||
             (s[i + 1] == '\0' && !IS_DEL(s[i], delimiter))))
            words++;
    return words;
}

static char *get_word(char *s, char delimiter)
{
    int i = -1, size = 0;
    while (s[++i] && !IS_DEL(s[i], delimiter))
        size++;
    char *word = gc_alloc(sizeof(char) * (size + 1));
    word[size] = '\0';
    while (*s && !IS_DEL(*s, delimiter)) {
        *word++ = *s;
        s++;
    }
    return word - size;
}

char *my_strdup(char *s)
{
    if(!s)
        return NULL;
    int size = 0;
    int i = -1;
    while(s[++i])
        size++;
    char *word = gc_alloc(sizeof(char)*(size+1));
    word[size] = '\0';
    i = -1;
    while(s[++i]){
        word[i] = s[i];
    }
    return word;
}

char **my_strsep(char *s, char delimiter)
{
    if (!s)
        return NULL;

    char **tab;
    int size = count_words(s, delimiter);
    if (!(tab = gc_alloc((size + 1) * sizeof(char *))))
        return NULL;

    tab[size] = 0;
    char *str = s;
    while (*str) {
        if (!IS_DEL(*str, delimiter)) {
            *tab++ = get_word(str, delimiter);
            str += strlen(get_word(str, delimiter)) - 1;
        }
        str++;
    }
    return tab - size;
}

int main(int argc, char *argv[])
{
    gc_init(&argc, 1);

    char **sep = my_strsep("hello,world", ',');
    assert(sep);
    char *dup = my_strdup("hello,world");
    assert(dup);
    printf("%s\n", sep[0]);
    printf("%s\n", sep[1]);
    printf("%s\n", dup);
    gc_run();

    gc_dump_internals();
    gc_destroy();

    return 0;
}

strdup() :

char *my_strdup(char *s)
{
    if(!s)
        return NULL;
    int size = 0;
    int i = -1;
    while(s[++i])
        size++;
    char *word = gc_alloc(sizeof(char)*(size+1));
    word[size] = '\0';
    i = -1;
    while(s[++i]){
        word[i] = s[i];
    }
    return word;
}

tags: Cprogramming LinuxKernel