每當(dāng)我倍感壓力以及有很多事情要做的時(shí)候，我總是有這樣一種反常的反應(yīng)，那就是希望做一些其他的事情來(lái)擺脫這種狀況。通常情況下，這些事情都是些我能夠編寫(xiě)并實(shí)現(xiàn)的獨(dú)立的小程序。

一天早上，我?guī)缀跻灰欢咽虑榻o整瘋了——我得看一本書(shū)、處理一些工作上的事情、還要準(zhǔn)備一場(chǎng)Strange Loop的演講，然后這時(shí)我突然想到：“我該寫(xiě)一個(gè)垃圾收集器了”。

是的，我知道那一刻讓我看上去有多瘋狂。不過(guò)我的神經(jīng)故障卻是你實(shí)現(xiàn)一段基礎(chǔ)的程序語(yǔ)言設(shè)計(jì)的免費(fèi)教程！在100行左右毫無(wú)新意的c代碼中，我設(shè)法實(shí)現(xiàn)一個(gè)基本的標(biāo)記和掃描模塊。

垃圾收集被認(rèn)為是有更多編程牛人出沒(méi)的水域之一，但在這里，我會(huì)給你一個(gè)漂亮的兒童游泳池去玩耍。可能這里面仍然會(huì)有一些能手，但至少這會(huì)是一個(gè)淺水區(qū)。

 精簡(jiǎn)、復(fù)用、再?gòu)?fù)用

垃圾收集背后有這樣一個(gè)基本的觀念：編程語(yǔ)言(大多數(shù)的)似乎總能訪問(wèn)無(wú)限的內(nèi)存。而開(kāi)發(fā)者可以一直分配、分配再分配——像魔法一樣，取之不盡用之不竭。

當(dāng)然，我們從來(lái)都沒(méi)有無(wú)限的內(nèi)存。所以計(jì)算機(jī)實(shí)現(xiàn)收集的方式就是當(dāng)機(jī)器需要分配一些內(nèi)存，而內(nèi)存又不足時(shí)，讓它收集垃圾。

“垃圾(Garbage)”在這里表示那些事先分配過(guò)但后來(lái)不再被使用的內(nèi)存。而基于對(duì)無(wú)限內(nèi)存的幻想，我們需要確保“不再被使用”對(duì)于編程語(yǔ)言來(lái)說(shuō)是非常安全的。要知道在你的程序試圖訪問(wèn)一些隨機(jī)的對(duì)象時(shí)它們卻剛好正在得到回收，這可不是一件好玩的事情。

為了實(shí)現(xiàn)收集，編程語(yǔ)言需要確保程序不再使用那個(gè)對(duì)象。如果該程序不能得到一個(gè)對(duì)象的引用，那么顯然它也不會(huì)再去使用它。所以關(guān)于”in use”的定義事實(shí)上非常簡(jiǎn)單：

1. 任何被一個(gè)變量引用的對(duì)象，仍然在作用域內(nèi)，就屬于”in use”狀態(tài)。
2. 任何被另一個(gè)對(duì)象引用的對(duì)象，仍在使用中，就是”in use”狀態(tài)。

如果對(duì)象A被一個(gè)變量引用，而它又有一些地方引用了對(duì)象B，那么B就是在使用中(“in use”)，因?yàn)槟隳軌蛲ㄟ^(guò)A來(lái)訪問(wèn)到它。

這樣到最后的結(jié)果就是得到一張可訪問(wèn)的對(duì)象圖——以一個(gè)變量為起點(diǎn)并能夠遍歷到的所有對(duì)象。任何不在圖中的對(duì)象對(duì)于程序來(lái)說(shuō)都是死的，而它的內(nèi)存也是時(shí)候被回收了。

 標(biāo)記并清理

有很多不同的方法可以實(shí)現(xiàn)關(guān)于查找和回收所有未被使用的對(duì)象的操作，但是最簡(jiǎn)單也是第一個(gè)被提出的算法就是”標(biāo)記-清除”算法。它由John McCarthy——Lisp(列表處理語(yǔ)言)的發(fā)明者提出，所以你現(xiàn)在做的事情就像是與一個(gè)古老的神在交流，但希望你別用一些洛夫克拉夫特式的方法——最后以你的大腦和視網(wǎng)膜的完全枯萎而結(jié)束。

該算法的工作原理幾乎與我們對(duì)”可訪問(wèn)性(reachability)”的定義完全一樣：

對(duì)，就是這樣。我猜你可能已經(jīng)想到了，對(duì)吧？如果是，那你可能就成為了一位被引用了數(shù)百次的文章的作者。所以這件事情的教訓(xùn)就是，想要在CS(計(jì)算機(jī)科學(xué))領(lǐng)域中出名，你不必開(kāi)始就搞出一個(gè)很牛的東西，你只需要第一個(gè)整出來(lái)即可，哪怕這玩意看上去很搓。

對(duì)象對(duì)

在我們落實(shí)這兩個(gè)步驟之前，讓我們先做些不相關(guān)的準(zhǔn)備工作。我們不會(huì)為一種語(yǔ)言真正實(shí)現(xiàn)一個(gè)解釋器——沒(méi)有分析器，字節(jié)碼、或任何這種愚蠢的東西。但我們確實(shí)需要一些少量的代碼來(lái)創(chuàng)建一些垃圾去收集。

讓我們假裝我們正在為一種簡(jiǎn)單的語(yǔ)言編寫(xiě)一個(gè)解釋器。它是動(dòng)態(tài)類型，并且有兩種類型的變量：int 和 pair。 下面是用枚舉來(lái)標(biāo)示一個(gè)對(duì)象的類型：

typedef enum { 
  OBJ_INT, 
  OBJ_PAIR 
} ObjectType; 

其中，pair可以是任何一對(duì)東西，兩個(gè)int、一個(gè)int和另一個(gè)pair，什么都可以。隨你怎么想都行。因?yàn)橐粋€(gè)對(duì)象在虛擬機(jī)中可以是這兩個(gè)當(dāng)中的任意一種類型，所以在c中實(shí)現(xiàn)對(duì)象的典型方法是時(shí)用一個(gè)標(biāo)記聯(lián)合體(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; 

這個(gè)Object結(jié)構(gòu)擁有一個(gè)type字段表示它是哪種類型的值——要么是int要么是pair。接下來(lái)用一個(gè)union來(lái)持有這個(gè)int或是pair的數(shù)據(jù)。如果你對(duì)c語(yǔ)言很生疏，一個(gè)union就是一個(gè)結(jié)構(gòu)體，它將字段重疊在內(nèi)存中。由于一個(gè)給定的對(duì)象只能是int或是pair，我們沒(méi)有任何理在一個(gè)單獨(dú)的對(duì)象中同時(shí)為所有這3個(gè)字段分配內(nèi)存。一個(gè)union就搞定。帥吧。

小虛擬機(jī)

現(xiàn)在我們可以將其包裝在一個(gè)小的虛擬機(jī)結(jié)構(gòu)中了。它(指虛擬機(jī))在這里的角色是用一個(gè)棧來(lái)存儲(chǔ)在當(dāng)前作用域內(nèi)的變量。大多數(shù)語(yǔ)言虛擬機(jī)要么是基于棧 (如JVM和CLR)的，要么是基于寄存器(如Lua)的。但是不管哪種情況，實(shí)際上仍然存在這樣一個(gè)棧。它用來(lái)存放在一個(gè)表達(dá)式中間需要用到的臨時(shí)變量 和局部變量。

我們來(lái)簡(jiǎn)潔明了地建立這個(gè)模型，如下：

#define STACK_MAX 256 
  
typedef struct { 
  Object* stack[STACK_MAX]; 
  int stackSize; 
} VM; 

現(xiàn)在我們得到了一個(gè)合適的基本數(shù)據(jù)結(jié)構(gòu)，接下來(lái)我們一起敲些代碼來(lái)創(chuàng)建些東西。首先，我們來(lái)寫(xiě)一個(gè)方法創(chuàng)建并初始化一個(gè)虛擬機(jī)：

VM* newVM() { 
  VM* vm = malloc(sizeof(VM)); 
  vm->stackSize = 0; 
  return vm; 
} 

一旦我們得到了虛擬機(jī)，我們需要能夠操作它的堆棧：

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]; 
} 

好了，現(xiàn)在我們能敲些玩意到”變量”中了，我們需要能夠?qū)嶋H的創(chuàng)建對(duì)象。首先來(lái)一些輔助函數(shù)：

Object* newObject(VM* vm, ObjectType type) { 
  Object* object = malloc(sizeof(Object)); 
  object->typetype = type; 
  return object; 
} 

它實(shí)現(xiàn)了內(nèi)存的分配和設(shè)置類型標(biāo)記。我們一會(huì)兒會(huì)重溫它的。利用它，我們可以編寫(xiě)方法將每種類型的對(duì)象壓到虛擬機(jī)的棧上：

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; 
} 

這就是我們的小小虛擬機(jī)。如果我們有調(diào)用這些方法的解析器和解釋器，那我們手上就有了一種對(duì)上帝都誠(chéng)實(shí)的語(yǔ)言。而且，如果我們有無(wú)限的內(nèi)存，它甚至能夠運(yùn)行真正的程序?？上г蹅儧](méi)有，所以讓我們來(lái)收集些垃圾吧。

標(biāo)記

第一個(gè)階段就是標(biāo)記(marking)。我們需要掃遍所有可以訪問(wèn)到的對(duì)象，并設(shè)置其標(biāo)志位。現(xiàn)在我們需要做的第一件事就是為對(duì)象添加一個(gè)標(biāo)志位(mark bit)：

typedef struct sObject { 
  unsigned char marked; 
  <span style="color: #999999;">/* Previous stuff... */</span> 
} Object; 

一旦我們創(chuàng)建了一個(gè)新的對(duì)象，我們將修改newObject()方法初始化marked為0。為了標(biāo)記所有可訪問(wèn)的對(duì)象，我們從內(nèi)存中的變量入手，這樣就意味著要掃一遍堆棧?？瓷先ゾ拖襁@樣：

void markAll(VM* vm) 
{ 
  for (int i = 0; i < vm->stackSize; i++) { 
    mark(vm->stack[i]); 
  } 
} 

里面又調(diào)用了mark。我們來(lái)分幾步搭建它。第一：

void mark(Object* object) { 
  object->marked = 1; 
} 

毫無(wú)疑問(wèn)，這是最重要的一點(diǎn)。我們標(biāo)記了這個(gè)對(duì)象自身是可訪問(wèn)的，但記住，我們還需要處理對(duì)象中的引用：可訪問(wèn)性是遞歸的。如果該對(duì)象是一個(gè)pair，它的兩個(gè)字段也是可訪問(wèn)的。操作很簡(jiǎn)單：

void mark(Object* object) { 
  object->marked = 1; 
  
  if (object->type == OBJ_PAIR) { 
    mark(object->head); 
    mark(object->tail); 
  } 
} 

但是這里有一個(gè)bug。你看到了嗎？我們正在遞歸，但我們沒(méi)有檢查循環(huán)。如果你有一堆pair在一個(gè)循環(huán)中相互指向?qū)Ψ?，這就會(huì)造成棧溢出并崩潰。

為了解決這個(gè)情況，我們僅需要做的是在訪問(wèn)到了一個(gè)已經(jīng)處理過(guò)的對(duì)象時(shí)，退出即可。所以完整的mark()方法應(yīng)該是：

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); 
  } 
} 

現(xiàn)在我們可以調(diào)用markAll()方法了，它會(huì)準(zhǔn)確的標(biāo)記內(nèi)存中所有可訪問(wèn)的對(duì)象。我們已經(jīng)成功一半了！

清理

下一個(gè)階段就是清理一遍所有我們已經(jīng)分配過(guò)(內(nèi)存)的對(duì)象并釋放那些沒(méi)有被標(biāo)記過(guò)的(對(duì)象)。但這里有一個(gè)問(wèn)題：所有未被標(biāo)記的對(duì)象——我們所定義的——都不可達(dá)！我們都不能訪問(wèn)到它們！

虛擬機(jī)已經(jīng)實(shí)現(xiàn)了對(duì)象引用的語(yǔ)義：所以我們只在變量和pair元素中儲(chǔ)存指向?qū)ο蟮闹羔槨．?dāng)一個(gè)對(duì)象不再被任何指針指向時(shí)，那我們就完全失去它了，而這也實(shí)際上造成了內(nèi)存泄露。

解決這個(gè)問(wèn)題的訣竅是：虛擬機(jī)可以有它自己的對(duì)象引用，而這不同于對(duì)語(yǔ)言使用者可讀的那種語(yǔ)義。換句話說(shuō)，我們自己可以保留它們的痕跡。

這么做最簡(jiǎn)單的方法是僅維持一張由所有分配過(guò)(內(nèi)存)的對(duì)象(組成)的鏈表。我們?cè)谶@個(gè)鏈表中將對(duì)象自身擴(kuò)展為一個(gè)節(jié)點(diǎn)：

typedef struct sObject { 
  /* The next object in the list of all objects. */ 
  struct sObject* next; 
  
  /* Previous stuff... */ 
} Object; 

虛擬機(jī)會(huì)保留這個(gè)鏈表頭的痕跡：

typedef struct { 
  /* The first object in the list of all objects. */ 
  Object* firstObject; 
  
  /* Previous stuff... */ 
} VM; 

在newVM()方法中我們確保將firstObject初始化為NULL。無(wú)論何時(shí)創(chuàng)建一個(gè)對(duì)象，我們都將其添加到鏈表中：

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; 
} 

這樣一來(lái)，即便是語(yǔ)言找不到一個(gè)對(duì)像，它還是可以被實(shí)現(xiàn)。想要清理并刪除那些未被標(biāo)記的對(duì)象，我們只需要遍歷該鏈表：

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; 
    } 
  } 
} 

這段代碼讀起來(lái)有點(diǎn)棘手，因?yàn)槟莻€(gè)指針(指object)指向的是一個(gè)指針，但是通過(guò)它的工作你會(huì)發(fā)現(xiàn)它還是非常簡(jiǎn)單的。它只是掃遍了整張鏈表。只要它碰到了一個(gè)未被標(biāo)記的對(duì)象，它就會(huì)釋放該對(duì)象的內(nèi)存并將其從鏈表中移除。最后，我們將會(huì)刪除所有不可訪問(wèn)的對(duì)象。

祝賀你！我們已經(jīng)有了一個(gè)垃圾收集器！現(xiàn)在只剩下一點(diǎn)工作了：實(shí)際調(diào)用它！首先我們將這兩個(gè)階段整合在一起：

void gc(VM* vm) { 
  markAll(vm); 
  sweep(vm); 
} 

沒(méi)有比這更明顯的”標(biāo)記-清除”算法了。現(xiàn)在最棘手的是搞清楚什么時(shí)候來(lái)實(shí)際調(diào)用它。”內(nèi)存不足(low on memory)”是個(gè)什么意思？尤其是對(duì)于現(xiàn)在的計(jì)算機(jī)，它們幾乎擁有無(wú)限的虛擬內(nèi)存！

事實(shí)證明，我們沒(méi)有完全正確或錯(cuò)誤的答案。這真的取決于你使用虛擬機(jī)的目的以及讓它運(yùn)行在什么樣的硬件上。為了讓這個(gè)例子看上去很簡(jiǎn)單，我們僅在進(jìn)行了一定數(shù)量的內(nèi)存分配之后開(kāi)始收集。事實(shí)上一些語(yǔ)言的實(shí)現(xiàn)就是這么做的，而這也很容易。

我們將邀請(qǐng)?zhí)摂M機(jī)來(lái)追蹤我們到底創(chuàng)建了多少(對(duì)象)：

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; 

接下來(lái)，初始化：

VM* newVM() { 
  /* Previous stuff... */ 
  
  vm->numObjects = 0; 
  vm->maxObjects = INITIAL_GC_THRESHOLD; 
  return vm; 
} 

其中，INITIAL_GC_THRESHOLD為你啟動(dòng)第一個(gè)GC(垃圾收集器)的對(duì)象數(shù)量。較小的值會(huì)更節(jié)省內(nèi)存，而較大的值則更省時(shí)。自己看著辦吧。

每當(dāng)我們創(chuàng)建一個(gè)對(duì)象，我們?cè)黾觧umObjects，如果它達(dá)到最大值就啟動(dòng)一次收集：

Object* newObject(VM* vm, ObjectType type) { 
  if (vm->numObjects == vm->maxObjects) gc(vm); 
  
  /* Create object... */ 
  
  vm->numObjects++; 
  return object; 
} 

我不會(huì)費(fèi)心的顯示它(指numObjects)，但是我們也會(huì)稍微調(diào)整sweep()方法，每釋放一次就遞減numObjects。最后，我們修改了gc()方法來(lái)更新最大值：

void gc(VM* vm) { 
  int numObjects = vm->numObjects; 
  
  markAll(vm); 
  sweep(vm); 
  
  vm->maxObjects = vm->numObjects * 2; 
} 

每次收集之后，我們更新maxObjects——以進(jìn)行收集后仍在活動(dòng)的對(duì)象為基準(zhǔn)。乘法器讓我們的堆隨著活動(dòng)中的對(duì)象數(shù)量的增加而增加。同樣，也會(huì)隨著一些對(duì)象最終被釋放掉而自動(dòng)減少。

最后

原文鏈接：http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/

譯文鏈接：http://blog.jobbole.com/53376/