編寫你的第一個垃圾收集器
每當我倍感壓力以及有很多事情要做的時候，我總是有這樣一種反常的反應，那就是希望做一些其他的事情來擺脫這種狀況。通常情況下，這些事情都是些我能夠編寫并實現的獨立的小程序。
一天早上，我幾乎要被一堆事情給整瘋了——我得看一本書、處理一些工作上的事情、還要準備一場Strange Loop的演講，然后這時我突然想到：“我該寫一個垃圾收集器了”。
是的，我知道那一刻讓我看上去有多瘋狂。不過我的神經故障卻是你實現一段基礎的程序語言設計的免費教程！在100行左右毫無新意的c代碼中，我設法實現一個基本的標記和掃描模塊。
垃圾收集被認為是有更多編程牛人出沒的水域之一，但在這里，我會給你一個漂亮的兒童游泳池去玩耍。可能這里面仍然會有一些能手，但至少這會是一個淺水區。
精簡、復用、再復用
垃圾收集背后有這樣一個基本的觀念：編程語言(大多數的)似乎總能訪問無限的內存。而開發者可以一直分配、分配再分配——像魔法一樣，取之不盡用之不竭。
當然，我們從來都沒有無限的內存。所以計算機實現收集的方式就是當機器需要分配一些內存，而內存又不足時，讓它收集垃圾。
“垃圾(Garbage)”在這里表示那些事先分配過但后來不再被使用的內存。而基于對無限內存的幻想，我們需要確保“不再被使用”對于編程語言來說是非常安全的。要知道在你的程序試圖訪問一些隨機的對象時它們卻剛好正在得到回收，這可不是一件好玩的事情。
為了實現收集，編程語言需要確保程序不再使用那個對象。如果該程序不能得到一個對象的引用，那么顯然它也不會再去使用它。所以關于”in use”的定義事實上非常簡單：
- 任何被一個變量引用的對象，仍然在作用域內，就屬于”in use”狀態。
- 任何被另一個對象引用的對象，仍在使用中，就是”in use”狀態。
如果對象A被一個變量引用，而它又有一些地方引用了對象B，那么B就是在使用中(“in use”)，因為你能夠通過A來訪問到它。
這樣到最后的結果就是得到一張可訪問的對象圖——以一個變量為起點并能夠遍歷到的所有對象。任何不在圖中的對象對于程序來說都是死的，而它的內存也是時候被回收了。
標記并清理
有很多不同的方法可以實現關于查找和回收所有未被使用的對象的操作，但是最簡單也是第一個被提出的算法就是”標記-清除”算法。它由John McCarthy——Lisp(列表處理語言)的發明者提出，所以你現在做的事情就像是與一個古老的神在交流，但希望你別用一些洛夫克拉夫特式的方法——最后以你的大腦和視網膜的完全枯萎而結束。
該算法的工作原理幾乎與我們對”可訪問性(reachability)”的定義完全一樣：
- 從根節點開始，依次遍歷整個對象圖。每當你訪問到一個對象，在上面設置一個”標記(mark)”位，置為true。
- 一旦搞定，找出所有標記位為”not”的對象集，然后刪除它們。
對，就是這樣。我猜你可能已經想到了，對吧？如果是，那你可能就成為了一位被引用了數百次的文章的作者。所以這件事情的教訓就是，想要在CS(計算機科學)領域中出名，你不必開始就搞出一個很牛的東西，你只需要第一個整出來即可，哪怕這玩意看上去很搓。
對象對
在我們落實這兩個步驟之前，讓我們先做些不相關的準備工作。我們不會為一種語言真正實現一個解釋器——沒有分析器，字節碼、或任何這種愚蠢的東西。但我們確實需要一些少量的代碼來創建一些垃圾去收集。
讓我們假裝我們正在為一種簡單的語言編寫一個解釋器。它是動態類型，并且有兩種類型的變量：int 和 pair。 下面是用枚舉來標示一個對象的類型：
- typedef enum {
- OBJ_INT,
- OBJ_PAIR
- } ObjectType;
其中，pair可以是任何一對東西，兩個int、一個int和另一個pair，什么都可以。隨你怎么想都行。因為一個對象在虛擬機中可以是這兩個當中的任意一種類型，所以在c中實現對象的典型方法是時用一個標記聯合體(tagged union)。
- typedef struct sObject {
- ObjectType type;
- union {
- <span style="color: #999999;">/* OBJ_INT */</span>
- int value;
- <span style="color: #999999;"> /* OBJ_PAIR */</span>
- struct {
- struct sObject* head;
- struct sObject* tail;
- };
- };
- } Object;
這個Object結構擁有一個type字段表示它是哪種類型的值——要么是int要么是pair。接下來用一個union來持有這個int或是pair的數據。如果你對c語言很生疏，一個union就是一個結構體，它將字段重疊在內存中。由于一個給定的對象只能是int或是pair，我們沒有任何理在一個單獨的對象中同時為所有這3個字段分配內存。一個union就搞定。帥吧。
小虛擬機
現在我們可以將其包裝在一個小的虛擬機結構中了。它(指虛擬機)在這里的角色是用一個棧來存儲在當前作用域內的變量。大多數語言虛擬機要么是基于棧 (如JVM和CLR)的，要么是基于寄存器(如Lua)的。但是不管哪種情況，實際上仍然存在這樣一個棧。它用來存放在一個表達式中間需要用到的臨時變量 和局部變量。
我們來簡潔明了地建立這個模型，如下：
- #define STACK_MAX 256
- typedef struct {
- Object* stack[STACK_MAX];
- int stackSize;
- } VM;
現在我們得到了一個合適的基本數據結構，接下來我們一起敲些代碼來創建些東西。首先，我們來寫一個方法創建并初始化一個虛擬機：
- VM* newVM() {
- VM* vm = malloc(sizeof(VM));
- vm->stackSize = 0;
- return vm;
- }
一旦我們得到了虛擬機，我們需要能夠操作它的堆棧：
- void push(VM* vm, Object* value) {
- assert(vm->stackSize < STACK_MAX, "Stack overflow!");
- vm->stack[vm->stackSize++] = value;
- }
- Object* pop(VM* vm) {
- assert(vm->stackSize > 0, "Stack underflow!");
- return vm->stack[--vm->stackSize];
- }
好了，現在我們能敲些玩意到”變量”中了，我們需要能夠實際的創建對象。首先來一些輔助函數：
- Object* newObject(VM* vm, ObjectType type) {
- Object* object = malloc(sizeof(Object));
- object->typetype = type;
- return object;
- }
它實現了內存的分配和設置類型標記。我們一會兒會重溫它的。利用它，我們可以編寫方法將每種類型的對象壓到虛擬機的棧上：
- void pushInt(VM* vm, int intValue) {
- Object* object = newObject(vm, OBJ_INT);
- object->value = intValue;
- push(vm, object);
- }
- Object* pushPair(VM* vm) {
- Object* object = newObject(vm, OBJ_PAIR);
- object->tail = pop(vm);
- object->head = pop(vm);
- push(vm, object);
- return object;
- }
這就是我們的小小虛擬機。如果我們有調用這些方法的解析器和解釋器，那我們手上就有了一種對上帝都誠實的語言。而且，如果我們有無限的內存，它甚至能夠運行真正的程序。可惜咱們沒有，所以讓我們來收集些垃圾吧。
標記
第一個階段就是標記(marking)。我們需要掃遍所有可以訪問到的對象，并設置其標志位。現在我們需要做的第一件事就是為對象添加一個標志位(mark bit)：
- typedef struct sObject {
- unsigned char marked;
- <span style="color: #999999;">/* Previous stuff... */</span>
- } Object;
一旦我們創建了一個新的對象，我們將修改newObject()方法初始化marked為0。為了標記所有可訪問的對象，我們從內存中的變量入手，這樣就意味著要掃一遍堆棧。看上去就像這樣：
- void markAll(VM* vm)
- {
- for (int i = 0; i < vm->stackSize; i++) {
- mark(vm->stack[i]);
- }
- }
里面又調用了mark。我們來分幾步搭建它。第一：
- void mark(Object* object) {
- object->marked = 1;
- }
毫無疑問，這是最重要的一點。我們標記了這個對象自身是可訪問的，但記住，我們還需要處理對象中的引用：可訪問性是遞歸的。如果該對象是一個pair，它的兩個字段也是可訪問的。操作很簡單：
- void mark(Object* object) {
- object->marked = 1;
- if (object->type == OBJ_PAIR) {
- mark(object->head);
- mark(object->tail);
- }
- }
但是這里有一個bug。你看到了嗎？我們正在遞歸，但我們沒有檢查循環。如果你有一堆pair在一個循環中相互指向對方，這就會造成棧溢出并崩潰。
為了解決這個情況，我們僅需要做的是在訪問到了一個已經處理過的對象時，退出即可。所以完整的mark()方法應該是：
- void mark(Object* object) {
- /* If already marked, we're done. Check this first
- to avoid recursing on cycles in the object graph. */
- if (object->marked) return;
- object->marked = 1;
- if (object->type == OBJ_PAIR) {
- mark(object->head);
- mark(object->tail);
- }
- }
現在我們可以調用markAll()方法了，它會準確的標記內存中所有可訪問的對象。我們已經成功一半了！
清理
下一個階段就是清理一遍所有我們已經分配過(內存)的對象并釋放那些沒有被標記過的(對象)。但這里有一個問題：所有未被標記的對象——我們所定義的——都不可達！我們都不能訪問到它們！
虛擬機已經實現了對象引用的語義：所以我們只在變量和pair元素中儲存指向對象的指針。當一個對象不再被任何指針指向時，那我們就完全失去它了，而這也實際上造成了內存泄露。
解決這個問題的訣竅是：虛擬機可以有它自己的對象引用，而這不同于對語言使用者可讀的那種語義。換句話說，我們自己可以保留它們的痕跡。
這么做最簡單的方法是僅維持一張由所有分配過(內存)的對象(組成)的鏈表。我們在這個鏈表中將對象自身擴展為一個節點：
- typedef struct sObject {
- /* The next object in the list of all objects. */
- struct sObject* next;
- /* Previous stuff... */
- } Object;
虛擬機會保留這個鏈表頭的痕跡：
- typedef struct {
- /* The first object in the list of all objects. */
- Object* firstObject;
- /* Previous stuff... */
- } VM;
在newVM()方法中我們確保將firstObject初始化為NULL。無論何時創建一個對象，我們都將其添加到鏈表中：
- Object* newObject(VM* vm, ObjectType type) {
- Object* object = malloc(sizeof(Object));
- object->typetype = type;
- object->marked = 0;
- /* Insert it into the list of allocated objects. */
- object->next = vm->firstObject;
- vm->firstObject = object;
- return object;
- }
這樣一來，即便是語言找不到一個對像，它還是可以被實現。想要清理并刪除那些未被標記的對象，我們只需要遍歷該鏈表：
- void sweep(VM* vm)
- {
- Object** object = &vm->firstObject;
- while (*object) {
- if (!(*object)->marked) {
- /* This object wasn't reached, so remove it from the list
- and free it. */
- Object* unreached = *object;
- *object = unreached->next;
- free(unreached);
- } else {
- /* This object was reached, so unmark it (for the next GC)
- and move on to the next. */
- (*object)->marked = 0;
- object = &(*object)->next;
- }
- }
- }
這段代碼讀起來有點棘手，因為那個指針(指object)指向的是一個指針，但是通過它的工作你會發現它還是非常簡單的。它只是掃遍了整張鏈表。只要它碰到了一個未被標記的對象，它就會釋放該對象的內存并將其從鏈表中移除。最后，我們將會刪除所有不可訪問的對象。
祝賀你！我們已經有了一個垃圾收集器！現在只剩下一點工作了：實際調用它！首先我們將這兩個階段整合在一起：
- void gc(VM* vm) {
- markAll(vm);
- sweep(vm);
- }
沒有比這更明顯的”標記-清除”算法了。現在最棘手的是搞清楚什么時候來實際調用它。”內存不足(low on memory)”是個什么意思？尤其是對于現在的計算機，它們幾乎擁有無限的虛擬內存！
事實證明，我們沒有完全正確或錯誤的答案。這真的取決于你使用虛擬機的目的以及讓它運行在什么樣的硬件上。為了讓這個例子看上去很簡單，我們僅在進行了一定數量的內存分配之后開始收集。事實上一些語言的實現就是這么做的，而這也很容易。
我們將邀請虛擬機來追蹤我們到底創建了多少(對象)：
- typedef struct {
- /* The total number of currently allocated objects. */
- int numObjects;
- /* The number of objects required to trigger a GC. */
- int maxObjects;
- /* Previous stuff... */
- } VM;
接下來，初始化：
- VM* newVM() {
- /* Previous stuff... */
- vm->numObjects = 0;
- vm->maxObjects = INITIAL_GC_THRESHOLD;
- return vm;
- }
其中，INITIAL_GC_THRESHOLD為你啟動第一個GC(垃圾收集器)的對象數量。較小的值會更節省內存，而較大的值則更省時。自己看著辦吧。
每當我們創建一個對象，我們增加numObjects，如果它達到最大值就啟動一次收集：
- Object* newObject(VM* vm, ObjectType type) {
- if (vm->numObjects == vm->maxObjects) gc(vm);
- /* Create object... */
- vm->numObjects++;
- return object;
- }
我不會費心的顯示它(指numObjects)，但是我們也會稍微調整sweep()方法，每釋放一次就遞減numObjects。最后，我們修改了gc()方法來更新最大值：
- void gc(VM* vm) {
- int numObjects = vm->numObjects;
- markAll(vm);
- sweep(vm);
- vm->maxObjects = vm->numObjects * 2;
- }
每次收集之后，我們更新maxObjects——以進行收集后仍在活動的對象為基準。乘法器讓我們的堆隨著活動中的對象數量的增加而增加。同樣，也會隨著一些對象最終被釋放掉而自動減少。
最后
你成功了！如果你全部照做了，那你現在已經得到了一個簡單的垃圾收集算法的句柄。如果你想看完整的代碼，在這里。我再強調一點，盡管這個收集器很簡單，但它可不是一個玩具。
你可以在這上面做一大堆的優化(像在GC和程序設計語言這些事情中，90%的努力都在優化上)，但它的核心代碼可是真正的GC。它與目前Ruby和Lua中的收集器非常的相似。你可以使用一些類似的代碼到你的項目中。去做些很酷的事情吧！
原文鏈接：http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/
