关于C语言中实现的GC

去年年底做了个ANSI-C的GC简单原型, 写完代码就扔在哪里, 也没有关注过，虽然写GC的过程中很有收获（比如学习了一个GC mark的非栈算法（3p算法)）,但是最终结果是还是应用起来相对比想象中的复杂性还是要高了一些。也就没管了，但是最后也没总结个文档出来。前两天看到云风的blog上面有他在这几天也写了一个GC for C的原型，基本上是另一个方向，基于 C 语言的指针而不是Handle, 因此看到他的Blog，颇有共同语言，遂回复并请教之，他也在回复中做了一些比较详尽的讨论。他是很有勇气的，把他的东西开源了，我那个玩意现在最后的设想，关于finalizer线程并没完全实现，（当时考虑到Geohm GC依赖于图的拓扑排序来finalize,所以做了一些思考，包括这个顺序本身的问题和finalize的线程，还有执行批量一次多少对象的finalize）.

既然有人也做了，我也可以把我的那个做法和基本的思考写出来，做个基本的回顾，不管成功失败，结果总是有一丁点的价值吧。

1.首先重点是接口，其实到底该给用户一个什么样界面，什么样的接口，甚至要提出需要的概念，是否够用，是决定了这个GC是否好用和有价值。当时思考这个问题真的非常的扰人。首先，在C语言，处于C的哲学，你必须够简洁，而且够用。一般的，在Java, C#这些已经有了GC的语言中，引用这个概念是显然的，在C里面，就要选一个，是Handle还是指针。这个后面会提到。另外，全局引用，对象之间的引用，栈上引用，还有甚至所谓寄存器引用(在Geohm GC的实现里面，扫描会饱含寄存器，所有架构相关可能存有引用的都会被扫到）。我的想法是把这个问题简单化，透明化：用户来搞，用户只维护两种引用：全局，对象间。全局引用使用引用计数来作为收集标志，并且他们是所谓的GC 根， 扫描总是从这些开始。（如果非要把根单数化，那么可以考虑有个根对象，跟对象和这些全局有着这些引用，但是这样的归纳看上去简洁了，实现确不如后来的有效率）。对象引用就是普通的赋值，不做赋值跟踪（使用C操作符=而不是定义宏，这个有缺陷，后面会说）。这些是否就够用了呢，基本上，差不多。有些细节，比如为了用户方便，实现一个所谓“基本数组”对象，就不提了。但是有个不能不提，那就是栈上引用的模拟，我是用一个对象，叫做Local frame, 每个线程使用线程局部存储来维护一个Local frame stack.可以push和pop. pop就是吧一个frame去掉，这个对象没了，那么栈上的对象引用也就解除。这个有好处就是GC有个很大的用途：一些紧凑的编程，需要产生不少所谓栈上的对象，而这些对象，用户并不想去自己来释放。少了这个，GC就少了很多威力。


2.Handle ,还是 void *?
这个问题是C里面实现GC的根本指导:要高的还是要低的。普通的C指针是比较简洁的，对用户很透明，但是关于在C里面应用Handle, 好处是很多的，虽然会增加用户代码，因为Handle本身有合法检查性方便，这样就不至于再给用户一把自宫刀子了。可以做内存重新整理，这一点很重要，GC在标记之后的垃圾清扫，使用何种策略是GC能不能带来好处的重大因素。一个整理内存的GC有着非常多的好处比如 没有碎片。

我的GC的指导是用户知道自己该让哪些对象，处于GC的内存管理之下，并且用户在提取Handle的指针的时候，可以处于GC关闭的保护，（我叫他做GC barrier，这个名字不太好去，和并行编程的那个barrier不是一个概念，就是防止用户提取指针的时候GC运行导致指针移动 ）。

到底该使用哪个方式，我觉得都是可行的，只是我个人认为Handle的方式在将来的扩展性可能要好些，当然，这是建立在用户多写handle相关的代码上，不过我觉得现在handle相关的代码很多，C程序员早就习惯了Handle了。


Handle方式的实现比较简单，一般就是一个Handle向量表，和一个堆来存储对象。细节就不说了，将来我的那个也开源吧，最近没有时间，还是要整理一下。

3.GC Thread
这是个困扰我的问题，虽然我早就定下使用一个Thread来做GC的方式。我还没有仔细的看过云风的代码，如果没有猜错，是在用户线程环境下做收集的。我的GC 有 Thread，然而Thread，众所周知，是移植性最大的挑战。首先，当GC在收集的时候，用户到底是把自己的所有线程暂停，还是仅仅是：当GC收集的时候，用户进入Barrier会被挡住，或者如果当前有用户在Barrier保护内，GC就不能收集。（这里有潜在分配/barrier死锁，不在这里细微讨论了，是可解的）。我采用的是后者，但是这并不能说这就是安全的，用户要知道这一点。在一些嵌入式系统上，我们可以简单的关闭中断（吓死人）来防止线程调度，来保护GC收集的时候不会到其他线程导致冲突，这在别的系统上是不可行的，在别的系统上，比如linux，可以参考Geohm GC里面挂起所有线程的办法。

另外，就是Finalizer Thread。这个应该不能放到GC Thread里面，因为把客户代码放到GC Thread简直就是自取灭亡。必须通过另外一个Thread, 或者多个-_-~。 这个我的代码没有实现，因为最后没有想好一个比较好的finalizer顺序。。。。在下面finalizer会提。

使用Thread可能是很自然的，然而在GC for C这样的里面使用Thread是有很大风险的，我的GC有一个OS Porting层，然而这层的接口比较潦草，仅仅是Thread mutex semaphore这些基本实现，并不考虑各种系统的区别。也许直接用posix的比较好，谁知道呢，win的支持不好，@#@$MS@#Q@.

4.隔代收集。
内存整理是个很耗费时间的事情，基于标记-清除或者整理都有这个比较郁闷的僵死时间。这也是早年GC老被人嘲笑的原因。现在有很多成熟的基于隔代收集的算法，这些算法的效率已经非常不错了。然而他们需要一个特点：追踪对象引用的赋值操作，或者说就是要知道某个对象在某时候引用了一个别的object,则需要立刻记录并作一些处理。这个在整体上会有一些效率的耗费，但是获得的是比较短的收集时间。

5.finalizer：
现在很多GC都支持一个所谓的finalize, 来实现GC辅助的资源管理。在 Geohm GC 中，使用拓扑序来call这些finalizer function. 这是个很不错的想法，可惜我没有实现。不过在现实中，对象引用有环的图应该是很容易发生的，但是话说回来，如果依赖finalizer来做资源释放，而本身存在环，这就有点不大对劲了，（不过也是有可能的）。这就不太好做了。我当时想就简单点，随便找个顺序，释放得了。另外，finalizer也需要一个线程，并且优先级要比较低，从一个队列去取对象来调用。这时候，我们再需要一个标记，就是一个对象在mark为不可要的时候，还有finalizer没有call之前也是不能被收集的（如果有finalizer function的话）。当call了之后，标记就置位。

6.Marking算法：
研究GC的应该都会看到那个比较彪悍的不要栈的通过节点缓存（不存父亲指针）的方式图遍历算法，（我叫他3P算法,三个人名字，怪长的），其实实际上，栈的简单深度有限遍历算法也是很有用的，因为我的GC并不是整个系统都在用，所以出现GC回首时，内存无法供给一个动态栈并不是很容发生。反而那个3p算法会需要一个每个节点计数器的存储开销，这个计数器可能并不需要，一般的一些书得介绍因为把对象描述几位几位的省出来一个计数器，有时候并不一定，呵呵。

这个东西做的时间有点长了，记得不太清楚，也不知道有些忘了写出来。先写这么多吧，不然以后忘了就比较失败了。

另，比较佩服云风的精神，开源是需要勇气的，面对回复也是需要勇气的。