# 2019q1 Homework6 (gc)
contributed by ` JulianATA `
另外研究 ` precise GC for c ` in [簡單 OGC 、保守 GC 與精準 GC for C](https://hackmd.io/s/ryXx6FDcV)

## Minimal mark-and-sweep garbage collector
### Naive 運作機制:
包含兩個階段 `Mark` 標記和 `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` )無法預測大小，因此無法預先保留。
:::info
解決方法
* 應用 `pointer reversal` ，用 `depth first search` 取代訪問清單。
:::
#### 問題點 `2`
* 有些物件沒有指標的空間。

:::info
解決方法
* 使用一個暫存器記憶其 `parent` 位置，就可以不用 `pointer reversal` 也能執行 `depth firsth search` 。
:::
## Type Imprecision
### 問題與實驗

在 C 或 C++ 的實作中，通常無法精確，因為可能會有 ` unreachable ` 的物件被標為 `reachable` ，原因可能為 type imprecision 或是 liveness imprecision 等等。

以下為實作 type imprecision 情況的程式 Based on [ogc](https://github.com/jserv/ogc) .

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

void ImPrecise(long *l)
{
    int* Unreachable;
    Unreachable = gc_alloc(sizeof(int));
    assert(Unreachable);
    *l = (long)Unreachable;
}

int main(int argc, char *argv[])
{
    gc_init(&argc, 1);
    long *l;
    l = gc_alloc(sizeof(long));
    assert(l);
    ImPrecise(l);
    gc_run();
    gc_dump_internals();
    gc_destroy();
    return 0;
}

預計輸出

## GC internals ##
 - GC.ptr_map[20]:
   { ptr: 0x7ffc624006a0, size: 8, marked: 0 }

實際輸出

## GC internals ##
 - GC.ptr_map[20]:
   { ptr: 0x7fceecc006a0, size: 8, marked: 0 }
 - GC.ptr_map[58]:
   { ptr: 0x7fceecc02bd0, size: 4, marked: 0 }

可以看到 `reachable` 的物件，應該只有 type 為 `long` 的 `l` 。
但是 `l` 中儲存的值 `剛好` 等於為一個 `unreachable` 物件的指標。
因此，「保守」的 GC 便將其標為 `reachable` 。
### 解決方法

###### tags: ` Cprogramming `