# 2019q1W7下: 方鈺學 ## 測驗 `1` ### 運作機制 :::info 延伸閱讀: [Precise Garbage Collection for C](https://www.cs.utah.edu/plt/publications/ismm09-rwrf.pdf) 有 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` : ```clike #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()` : ```clike 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`