# 2019q1 Homework6 (gc) contributed by < `tony2037` > ## Complete [第 7 週測驗題 (下)](https://hackmd.io/s/Hy8aBIgYV) ### **reference counting** & **mark and sweep** - references: - [17.2| Mark and Sweep](https://www.youtube.com/watch?v=2XKifr16o7Y) - work flow - mark phase - 從 **root** 出發 (v) - if(mark(v) == 0) mark(v) $\leftarrow1$ - 設 可從 v reach $v_1 ... v_n$ - 把 $v_1 ... v_n$ 放進 **todo list** - 剩下的 unreachable 的 會在 **sweep phase** 被 free - sweep phase - 找出 $mark=0$ 的 objects, 放進 free list, 這些 objects 就是 garbage - 把 $mark=1$ 的 $mark$ 設為 1 ### 改寫 tests/string-separate.c - my_strdup ```clike= char *my_strdup(char *s){ size_t size = strlen(s); char *dup = gc_alloc(sizeof(char) * (size + 1)); dup[size] = '\0'; strcpy(dup, s); return dup; } ``` - main ```clike= + char *s = my_strdup("Hello World"); + assert(s); + gc_dump_internals(); ``` 基本上就是使用 **gc library** 可以利用 **gc_dump_internals()** 記憶體配置的變化 ## [ogc](https://github.com/tony2037/ogc) ### Analysis - **void \*gc_alloc(size_t size)** 配置記憶體, 來看看具體上做了什麼事吧 ```clike= uintptr_t ptr; if (!(ptr = (uintptr_t) malloc(size))) return NULL; ``` 就是直接呼叫 **malloc(size)** 配置記憶體 ```clike= gc_ptr_t p = (gc_ptr_t){ .start = ptr, .size = size, .marked = true, }; ``` 把相關 attributes 配置好, 包括 **ptr**: address, **size**: 就是 size, 還有後續使用 **mark and sweep** 要用到的 **marked** 而 **gc_ptr_t** structure is defined in `gc_internal.h` ```clike= struct __gc_ptr { uintptr_t start; size_t size; bool marked; }; typedef struct __gc_ptr gc_ptr_t; ``` 其中又在 `gc_internal.h` 定義了一個 **globel gc object** ```clike= struct __gc { void *stack_start; gc_list_t *ptr_map[PTR_MAP_SIZE]; size_t ptr_num; size_t limit; size_t ref_count; uintptr_t min, max; gc_list_t *globals; }; typedef struct __gc gc_t; /* global GC object */ extern gc_t __gc_object; ``` **ptr_map** 就是 **roots** 對應 [17.2| Mark and Sweep](https://www.youtube.com/watch?v=2XKifr16o7Y) 的 **todo list** **gc_list_t** 的定義如下, 看起來就是一個 **singly-linked list** ```clike= struct __gc_list { struct __gc_list *next; gc_ptr_t data; }; typedef struct __gc_list gc_list_t; ``` 那麼我就好奇了, 如何決定一個 root 到底要擺在 **ptr_map**哪裡勒? 回去看到 **gc_alloc(size)** ```clike= gc_list_add(&__gc_object.ptr_map[HASH(ptr) % PTR_MAP_SIZE], p); ``` 看來就是 **HASH** 之後 take remainder(餘數), 而這邊的 **HASH** 也就是向右位移 3 bits 最後, 在 **gc_alloc** 結尾 ```clike= if (__gc_object.ptr_num >= __gc_object.limit) gc_run(); ``` 如果超過 pointers number 的上限就會啟動 **gc_run()** 也就是 gargage collection 機制 - **void gc_free(void \*ptr)** ```clike= void gc_free(void *ptr) { gc_list_t *lst = __gc_object.ptr_map[HASH(ptr) % PTR_MAP_SIZE]; if (lst && gc_list_exist(lst, (uintptr_t) lst)) { gc_list_del(&lst, (uintptr_t) lst); gc_mfree(lst); } } ``` 看懂 **gc_alloc(size)**, **gc_free(ptr)** 就簡單多了 基本就是靠著 **HASH, 取餘數** 找到所屬的 linked-list, 然後 free 了 整個 list (?) :::warning 這邊我不是很確定 ::: **Mark and Sweep** - **void gc_mark(uint8_t \*start, uint8_t \*end)** ```clike= 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++; } } ``` (swap(&start, &end) 基本就是確保 end address > start address, 不然就交換) 要講這個 function 就得先看到 **gc_ptr_index** ```clike= 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; } ``` **gc_ptr_index** 就是 **given a pointer, return the header within singly-linked list that the pointer is between header's start and header's end(start + size)** 所以總結來說 **gc_mark** 就是 給定 起始位址 (start), 終止位址(end), 我要把這段範圍的 reachable elements 全部 mark 起來, 怎麼找呢, 每個位置 (start++) 透過 **gc_ptr_index** 找到對應的 **singly-linked list** elements, mark 為 reachable, 並且遞迴呼叫 **gc_mark()**, start address 為 start, end address 為 start + size. - **void gc_sweep(void)** ```clike= 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++; } } } ``` 所以就是 traverse **ptr_map** 的每個 **singly-linked list** 然後沒有被 **marked** 的就會被 **free** :::warning 說實在的, 我真心不懂 **gc_mfree(e)** 這個 function 真的不會造成 memory leak 嗎？ ::: :::success 應該不會, 因為 start address = header address ::: ### Multithreading 總之先寫了一個 multithread allocate memory 版本 - `tests/multi.c` ```clike= #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <pthread.h> #include "gc.h" void *sample(void *h) { void **ptr = gc_alloc(10); *ptr = gc_alloc(11); *ptr += 3; gc_dump_internals(); return NULL; } void *hello(void *ptr) { printf("Hello world"); return ptr; } int main(int argc, char *argv[]) { pthread_t t1, t2, t3; gc_init(&argc, 1); int ret = 0; if((ret = pthread_create(&t1, NULL, *hello, NULL))) { fprintf(stderr,"Error - pthread_create() return code: %d\n",ret); exit(EXIT_FAILURE); } if((ret = pthread_create(&t2, NULL, *sample, NULL))) { fprintf(stderr,"Error - pthread_create() return code: %d\n",ret); exit(EXIT_FAILURE); } if ((ret = pthread_join(t2, NULL))) { fprintf(stderr,"Error - pthread_join() return code: %d\n",ret); exit(EXIT_FAILURE); } if((ret = pthread_create(&t3, NULL, *hello, NULL))) { fprintf(stderr,"Error - pthread_create() return code: %d\n",ret); exit(EXIT_FAILURE); } if ((ret = pthread_join(t1, NULL))) { fprintf(stderr,"Error - pthread_join() return code: %d\n",ret); exit(EXIT_FAILURE); } if ((ret = pthread_join(t2, NULL))) { fprintf(stderr,"Error - pthread_join() return code: %d\n",ret); exit(EXIT_FAILURE); } if ((ret = pthread_join(t3, NULL))) { fprintf(stderr,"Error - pthread_join() return code: %d\n",ret); exit(EXIT_FAILURE); } gc_destroy(); return 0; } ``` 透過 **gdb** 發現都是在 **gc_mark** 的時候被中斷(SIGSEGV) ``` 28 void gc_mark(uint8_t *start, uint8_t *end) │ │29 { │ │30 if (start > end) │ │31 swap_ptr(&start, &end); │ │32 while (start < end) { │ >│33 gc_list_t *idx = gc_ptr_index((uintptr_t)(*((void **) start))); │ │34 if (idx && idx->data.marked != true) { │ │35 idx->data.marked = true; │ │36 gc_mark((uint8_t *) (idx->data.start), │ │37 (uint8_t *) (idx->data.start + idx->data.size)); │ │38 } │ │39 start++; │ │40 } │ │41 } ``` 看來需要對這邊做點處理, 直覺想到 [pthread_mutex_lock](https://linux.die.net/man/3/pthread_mutex_lock) :::info 失敗 ::: ### 使用 **valgrind** 檢測 ``` ==6141== Thread 3: ==6141== Conditional jump or move depends on uninitialised value(s) ==6141== at 0x401268: gc_ptr_index (utils.c:15) ==6141== by 0x400F0D: gc_mark (core.c:46) ==6141== by 0x401393: gc_mark_stack (utils.c:36) ==6141== by 0x401027: gc_run (core.c:77) ==6141== by 0x400D2D: gc_alloc (alloc.c:22) ==6141== by 0x4009AB: sample (multi.c:9) ==6141== by 0x4E416B9: start_thread (pthread_create.c:333) ==6141== ==6141== Conditional jump or move depends on uninitialised value(s) ==6141== at 0x401275: gc_ptr_index (utils.c:15) ==6141== by 0x400F0D: gc_mark (core.c:46) ==6141== by 0x401393: gc_mark_stack (utils.c:36) ==6141== by 0x401027: gc_run (core.c:77) ==6141== by 0x400D2D: gc_alloc (alloc.c:22) ==6141== by 0x4009AB: sample (multi.c:9) ==6141== by 0x4E416B9: start_thread (pthread_create.c:333) ==6141== ==6141== ==6141== Process terminating with default action of signal 11 (SIGSEGV) ==6141== Bad permissions for mapped region at address 0x6823000 ==6141== at 0x400F03: gc_mark (core.c:46) ==6141== by 0x401393: gc_mark_stack (utils.c:36) ==6141== by 0x401027: gc_run (core.c:77) ==6141== by 0x400D2D: gc_alloc (alloc.c:22) ==6141== by 0x4009AB: sample (multi.c:9) ==6141== by 0x4E416B9: start_thread (pthread_create.c:333) ``` > > 看起來是存取到 invalid memory... 但不知道從何下手 > ```clike= 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)); } } ``` ```clike= 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++; } } ``` 應該是 start -> end 的過程中存取到其他 threads's memory :::warning 我不確定, **gc_mark_stack** 中: ```clike= uint8_t tmp; &tmp ``` 的技巧應該是拿到 **stack** end 的 address. ::: # 需要一點靈感 :::warning 我需要一點提示 不知道有沒有什麼資源可以參考 ::: # 嘗試在 thread 建立時先把 stack pointer 存起來, 然後在 `gc_mark_stack` 時不再從 global stack pointer 開始 mark 改從每個 thread 的 sp 開始 :::danger 結果就是不知道為什麼有時候是可以運作的, 有時候造樣觸發 segmentation fault ``` parallels@parallels-vm:~/Desktop/ogc$ ./tests/multi Segmentation fault (core dumped) parallels@parallels-vm:~/Desktop/ogc$ ./tests/multi Segmentation fault (core dumped) parallels@parallels-vm:~/Desktop/ogc$ ./tests/multi Segmentation fault (core dumped) parallels@parallels-vm:~/Desktop/ogc$ ./tests/multi Hello world## GC internals ## - GC.ptr_map[34]: { ptr: 0x7fbd1c000910, size: 11, marked: 0 } ## GC internals ## - GC.ptr_map[34]: { ptr: 0x7fbd1c000910, size: 11, marked: 0 } ``` ::: - [ ] `gc_internal.h` ```clike= struct __gc { ... void *multi_stack_start[100]; bool multithreading; }; ``` * `multi_stack_start`: 用來存 threads 的 sp * `multithreading`: 表示 gc_object 是不是在 multithreading 的假設下運行, 對應 `gc_mark_stack` 的 `start` 如何選擇 - [ ] `src/core.c` ```clike= void gc_run(void) { (__gc_object.multithreading) ? gc_mark_stack(__gc_object.multi_stack_start[pthread_self() % 100]) : gc_mark_stack(__gc_object.stack_start); gc_sweep(); } ``` 如果是 `mulithreading` 的話, `start` 會根據 `thread_id` 從 array 裡面找 - [ ] `src/util.c` ```clike= void gc_run(void) { (__gc_object.multithreading) ? gc_mark_stack(__gc_object.multi_stack_start[pthread_self() % 100]) : gc_mark_stack(__gc_object.stack_start); gc_sweep(); } ``` :::info 這邊找到幾個可能有用的 function `pthread_attr_getstack` `pthread_self` 現在的目標是在 只在該 thread 上的 stack 做 gc, 所以能確保不要存取到其他 thread 的 address 應該就沒問題了 ::: :::warning 先標註 GC 程式中的 critical section，並且依據 CS:APP 第 12 章的手法去視覺化展現 :notes: jserv ::: :::info TODO --- * TLS (Thread Local Storage) :::