# 2019q1 Homework6 (gc)
contributed by < `flawless0714` >
## OGC 運作機制
### reference counting
OGC 中實做 reference counting 的資料結構為 `gc_t`，其中的 `ref_count` 會在 `gc_init` (有使用到 OGC 的程式都需在初始化時(或開始動態配置記憶體前)執行此函數以初始化 OGC 的資料結構，倘若有多隻程式在使用 OGC，則自第二次開始 `gc_init` 只會增加 `ref_count`) 時加一，表示多一隻可能會使用到 OGC 所管理的記憶體的程式。
當要關閉 OGC (`gc_destory`) 時，會先透過 `ref_count` 檢查是否還有程式使用到 OGC 所管理的記憶體，若無則開始進行記憶體釋放等善後工作，反之 `gc_destory` 將直接結束。
:::info
`gc_destory` 或許可以加個例外處理或警告，以避免失敗時無聲無息的結束。
:::
### mark and sweep
#### gc_mark
```cpp
if (start > end)
swap_ptr(&start, &end);
```
確保 `start` 儲存的記憶體位置永遠低於 `end`。
```cpp
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` 前持續檢索 `ptr_map` 中保存的每一塊 heap 記憶體，若檢索到的記憶體為 reachable 且尚未標記(marked)，則對其進行標記，反之則繼續往下檢索。值得注意的是若有標記到某塊記憶體，則會以該塊記憶體的開始位置與結束位置繼續遞迴呼叫 `gc_mark`。
##### gc_ptr_index
```cpp
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_mark` 呼叫，用於回傳以給定記憶體做完 hash 並取完餘數(`PTR_MAP_SIZE`)後在 `ptr_map` 中找到的 `gc_list_t`。
##### list_search
```cpp
static inline gc_list_t *list_search(uintptr_t ptr, gc_list_t *e)
{
for (; e; e = e->next) {
if (ptr >= e->data.start && e->data.start + e->data.size >= ptr)
return e;
}
return NULL;
}
```
由 gc_ptr_index 呼叫，用於驗證給定的 `gc_list_t` 是否為 reachable 並且 `gc_list_t` 的保存的起始位置加上大小是否大於等於 `ptr`，是則回傳該 `gc_list_t`，反之。==這邊==不太理解為什麼 if statement 裡面要做這兩個檢查，我的理解是拿到 `ptr_map` 中的元素後應該只須驗證其是否為 reachable 就可以回傳了。
> 目前推測是為了避免拿到已經標記過得元素還回傳而造成效率下降，待確認。
##### HASH()
這個巨集用於對傳入的指標做 hash，位移為三個位元的原因==推測==為為了取得較稀有的記憶體位置，進而在取餘數(`HASH(ptr) % PTR_MAP_SIZE`)時降低拿到已經使用過的 index 的機率。待確認。
#### gc_sweep
```cpp
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++;
}
}
}
```
走訪整個 `ptr_map`，當遇到沒有 marked 的 `gc_list_t` 時將該節點釋放，並於 linked list 中移除該節點。
### gc_destory
```cpp
void gc_destroy(void)
{
__gc_object.ref_count--;
if (__gc_object.ref_count <= 0) {
__gc_object.ref_count = 0;
for (int i = -1; ++i < PTR_MAP_SIZE;) {
gc_list_t *m = __gc_object.ptr_map[i];
while (m) {
gc_list_t *tmp = m;
free((void *) (m->data.start));
m = m->next;
free(tmp);
}
__gc_object.ptr_map[i] = 0;
}
}
}
```
此函數開頭會先做 `ref_count--`，表示有一程式準備要結束，即不再使用 OGC 所管理的記憶體。接下來檢查 `ref_count` 是否為 0，假如為 0 即代表已沒有程式在使用 OGC 管理的記憶體，我們可以開始釋放所有 OGC 使用到的記憶體。
## OGC 已存在之缺陷
### unreachable code
```cpp=
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));
}
}
```
於 `util.c` 的 `gc_mark_stack` 這個函數中，第五行的 `__gc_object_globals` 從未 assign 數值，使得這個迴圈永遠不會被執行。
## 以多執行緒改寫 OGC
[主要程式碼](https://github.com/flawless0714/ogc/blob/master/src/gc_thread_funcs.c)
目前尚未完成(僅 `dummy` 通過測試)，還差 `gc_mark_stack` (不可用區域變數(thread 沒有共用 stack)) 與將架構改成在 `gc_init` 初始化完 OGC 後每個 user-program (`dummy`, `string-separate`) 以個別一個 thread 為執行單元去執行(以免失去 concurrency 之意義)。
:::warning
先標註 GC 程式中的 critical section，並且依據 CS:APP 第 12 章的手法去視覺化展現
:notes: jserv
:::
## 筆記
### uintptr_t
C99 中定義此資料型態可用於儲存指標(`void*`)，並可完好無缺的再轉型回 `void*`。通常要 cast 到 `uintptr_t` 前我們會先轉到 `void**`，再對這個指標的指標做一次 dereference 以取得 `void*` 的內容，最後再轉到 `uintptr_t`。
> 其實不太理解為什麼轉型到 `uintptr_t` 之前要先轉到 `void*` 去做處理，每個平台拿到的記憶體位置(address of operator)與指標中的內容都是該平台最大定址空間的資料型態，這樣應該跟直接轉型為 `uintptr_t` 是一樣的吧？從組合語言來看先轉 `void*` 去做處理的話會多一行以下組語:
> ```asm
> mov rax, QWORD PTR [rax]
> ```
> 像是 x86_64，也是上述 assembly 的平台，指標的內容都是 qword，那再多個轉 `QWORD PTR` 應該是不需要的吧？還是說這麼做其實有其他考量點？
:::warning
注意 alignment 的影響
:notes: jserv
:::
### pthread_detach
一般 pthread 須使用 `pthread_join` 來釋放其資源(若未釋放會導致部分資源(exit code...)要等到 process 結束時由 OS 回收。當 thread 多到個程度時會發生 memory leak)，而 `pthraed_join` 是個 blocking 的函數，有些時候我們不希望 thread 被 block，因為它可能還要趕著做其他事情。這時候我們就可以用 `pthread_detch` 來讓 child thread 完成工作時自行釋放所有資源。`pthread_detach` 可由 parent thread 呼叫或 child thread 自行呼叫，他的 parameter 是 thread id，在 child thread 中我們可以藉由呼叫 `pthread_self` 來取得自己的 tid，而在 parent thread 中則使用 `pthread_create` 的回傳值(即 tid)即可。
## 參考資料
- [uintptr_t](https://stackoverflow.com/questions/1845482/what-is-uintptr-t-data-type/1846648#1846648)
- [Garbage Collection vs Automatic Reference Counting](https://medium.com/computed-comparisons/garbage-collection-vs-automatic-reference-counting-a420bd4c7c81)
- [Multithreaded Programming](https://randu.org/tutorials/threads/)
###### tags: `linux2019`
Sign in with Wallet
Connect another wallet