200 行 C 代码编写你的第一个垃圾收集器

1. 从根节点开始，依次遍历整个对象图。每当你访问到一个对象，在上面设置一个”标记(mark)”位，置为true。
2. 一旦搞定，找出所有标记位为”not”的对象集，然后删除它们。

在我们落实这两个步骤之前，让我们先做些不相关的准备工作。我们不会为一种语言真正实现一个解释器——没有分析器，字节码、或任何这种愚蠢的东西。但我们确实需要一些少量的代码来创建一些垃圾去收集。

让我们假装我们正在为一种简单的语言编写一个解释器。它是动态类型，并且有两种类型的变量：int 和 pair。 下面是用枚举来标示一个对象的类型：

typedef enum {    OBJ_INT,    OBJ_PAIR  } ObjectType;

其中，pair可以是任何一对东西，两个int、一个int和另一个pair，什么都可以。随你怎么想都行。因为一个对象在虚拟机中可以是这两个当中的任意一种类型，所以在c中实现对象的典型方法是时用一个标记联合体(tagged union)。

typedef struct sObject {    ObjectType type;      union {      /* OBJ_INT */      int value;        /* OBJ_PAIR */      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->type = 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;    /* Previous stuff... */  } 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;

Object* newObject(VM* vm, ObjectType type) {    Object* object = malloc(sizeof(Object));    object->type = 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;      }    }  }

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

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

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

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