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