自己动手写GC 虚拟机c数据结构GC

有时候事情多得我喘不过气来的时候，我会出现一种异常反应，好像找点别的事做，就能远离烦恼了。通常我会写些自己能完成的独立的小程序。

有一天早上，我正在写的书，工作中的事情，还有要为Strang Loop准备的分享，这些东西让我感到快崩溃了，突然间我想到，“我要写一个垃圾回收程序”。

是的，我知道这听起来有点疯狂。不过你可以把我这个神经的想法当成是一份编程语言基础的免费教程。通过百来行普通的C代码，我实现了一个标记删除的收集器，你懂的，它确实能回收内存。

在程序开发领域，垃圾回收就像一片鲨鱼出没的水域，不过在本文中，这只是个儿童池，你可以随意玩耍。（说不定还是会有鲨鱼，不过至少水浅多了不是？）


少用，重用，循环用

垃圾回收思想是源于编程语言似乎需要无穷尽的内存。开发人员可以一直一直的分配内存，它就像是魔法一般，永远不会失败。

当然了，机器的内存不可能是无限的。所以解决办法就是，当程序需要分配内存并且意识到内存已经不足了，它开始进行垃圾回收。

在这里，“垃圾”是指那些已经分配出去但现在不再使用的内存。为了让内存看起来是取之不尽的，语言本身对于什么是“不再使用的”应当十分谨慎。不然的话当你的程序正要访问那些对象的时候，你却要回收它们，这可不是闹着玩的。

为了能进行垃圾回收，语言本身得确定程序无法再使用这些对象。如果拿不到对象的引用，当然也就无法使用它们了。那么定义什么是“在使用中的”就很简单了：

1. 如果对象被作用域中的变量引用的话，那么它就是在使用中的；
2. 如果对象被在使用中的对象引用的话，那么它也是在使用中的。

第二条规则是递归的。如果对象A被一个变量引用，并且它有个字段引用了对象B，那么B也是正在使用中的，因为通过A你能对它进行访问。

最后就是一张可达对象的图了——以一个变量为起点，你能够遍历到的所有对象。不在这张可达对象图里的对象对程序来说都是没用的，那么它占有的内存就可以回收了。

标记-清除

查找及回收无用对象的方法有很多种，最简单也是最早的一种方法，叫“标记-清除法”。它是由John McCathy发明的，他同时还发明了Lisp和beards，因此你用它来实现的话就像是和远古大神交流一般，不过希望你可不要被他那套给*了。

这和我们定义可达性的过程简直是一样的：

1. 从根对象开始，遍历整个对象图。每访问一个对象，就把一个标记位设成true。
2. 一旦完成遍历，找出所有没有被标记过的对象，并清除掉它们。

这样就OK了。你肯定觉得这些你也能想到吧？如果你早点想到，你写的这个论文可能就被无数人引用了。要知道，想在计算机界混出点名堂，你根本不需要有什么特别天才的想法，蠢主意也行，只要你是第一个提出来的。

一组对象

在我们开始实现这两点前，让我们先做一些准备工作。我们并不是要真正去实现一门语言的解释器——没有解析器，字节码或者任何这些破玩意儿——不过我们确实需要写一点代码，生成一些垃圾，这样我们才有东西可回收。

假设我们正在写一门小语言的解释器。它是动态类型的，有两种对象：int以及pair。下面是一个定义对象类型的枚举：

typedef enum {
  OBJ_INT,
  OBJ_PAIR
} ObjectType;

一对(pair)对象可以是任意类型的，比如两个int，一个int一个pair，什么都行。有这些就足够你用的了。由于VM机里的对象可是是这些中的任意一种，在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，没有理由说在内存里同时分配三个字段给它们。一个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;
}

这都是给我们这个迷你的虚拟机准备的。如果我们有个解析器和解释器来调用这些函数，我们就。并且，如果我们的内存是无限大的话，它简直就可以运行真实的程序了。不过当然不可能了，所以我们得进行垃圾回收。


Marky mark（这该怎么翻译，这货难道是作者喜爱的一个演员？不过下面肯定是讲标记的）


第一个阶段是标记阶段。我们需要遍历所有的可达对象，并且设置它们的标记位。需要做的第一件事就是给Object加一个标记位：

typedef struct sObject {
  unsigned char marked;
  /* Previous stuff... */
} Object;

我们得修改下newObject()函数，当我们创建新对象的时候，把这个maked字段初始化成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;
}

毫不夸张的说，这可是最重要的一个bit位了。我们把这个对象标记成可达的了，不过记住，我们还得处理对象的引用：可达性是递归的。如果对象是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了，它能正确的标记内存中所有的可达对象。已经完成一半了！


Sweepy sweep
(凯尔特人的疯狂支持者，参考http://www.urbandictionary.com/define.php?term=sweep%20sweep，看完就懂了）

下一个阶段就是遍历所有分配的对象，释放掉那些没有被标记的了。不过这里有个问题：那些没被标记的对象，是不可达的！我们没法访问到它们！

虚拟机已经实现了关于对象引用的语义：所以我们只在变量中存储了对象的指针。一旦某个对象没有人引用了，我们将会彻底的失去它，并导致了内存泄露。

解决这个的小技巧就是VM可以有属于自己的对象引用，这个和语义中的引用是不同的，那个引用对开发人员是可见的。也就是说，我们可以自己去记录这些对象。

最简单的方法就是为所有分配地宾对象维护一个链表。我们将Object扩展成一个链表的节点：

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

不可能有比这更直白的标记-清除的实现了。最有难度的是我们在什么时候调用这个函数呢？内存紧张是什么意思，尤其是在几乎有无限的虚拟内存现代计算机里？

这其实并没有标准答案。这取决于你如何使用你的虚拟机并且它运行在什么样的硬件上了。为了让这个例子简单点，我们在分配一定数量对象后进行回收。确实有一些语言是这么实现的，同时这也很容易实现。

我们扩展了一下 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;
}

INITIAL_GC_THRESHOLD 就是触发GC时分配的对象个数。保守点的话就设置的小点，希望GC花的时间少点的话就设置大点。看你的需要了。

当创建对象时，我们会增加这个numOjbects值，如果它到达最大值了，就执行一次垃圾回收：

Object* newObject(VM* vm, ObjectType type) {
  if (vm->numObjects == vm->maxObjects) gc(vm);

  /* Create object... */

  vm->numObjects++;
  return object;
}

我们还得调整下sweep函数，每次释放对象的时候进行减一。最后，我们修改下gc()来更新这个最大值：

void gc(VM* vm) {
  int numObjects = vm->numObjects;

  markAll(vm);
  sweep(vm);

  vm->maxObjects = vm->numObjects * 2;
}

每次回收之后，我们会根据存活对象的数量，更新maxOjbects的值。这里乘以2是为了让我们的堆能随着存活对象数量的增长而增长。同样的，如果大量对象被回收之后，堆也会随着缩小。

麻雀虽小


终于大功告成了！如果你坚持看完了，那么你现在也掌握一种简单的垃圾回收的算法了。如果你想查看完整的源代码，请点击这里。我得强调一下，这个回收器麻雀虽小，五脏俱全。

在它上面你可以做很多优化（在GC和编程语言里，做的90%的事情都是优化），不过这里的核心代码就是一个完整的真实的垃圾回收器。它和Ruby和Lua之前的回收器非常相像。你可以在你的产品中随意使用这些代码。现在就开始动手吧！


原创文章转载请注明出处：http://it.deepinmind.com

英文原文链接