« 好游戏不问年代 | 返回首页 | 用 C 实现一个变长数组 »

给 C 实现一个垃圾收集器

粽子节假期,欧洲杯开战。为了晚上不打瞌睡,我决定写程序提神。这三天的成果就是:实现了一个 C 用的垃圾收集器。感觉不错。

话说这 C 用的垃圾收集器,也不是没人做过,比如 这个 。不过它用的指针猜测的方法,总让人心里不塌实,也让人担心其收集的效率。

我希望做一个更纯粹的 gc for C/C++ 模块,接口保持足够简单。效率足够的高。三天下来,基本完成,正在考虑要不要放到 sourceforge 上开源。等过两天彻底测试过再做打算(或许再支持一下多线程收集)。

下面列一下设计目标和实现思路。

首先,采用标记清除的 gc 策略,这是目前公认的最有效的 gc 方案。远强过用引用计数的 boost::smart_ptr 那种。

接口保持足够简单,没有太多多余的东西需要使用者留意。

最重要的是效率,除了收集过程外,所有的 api 调用都要求是近似 O(1) 的时间复杂度。


先谈谈我对传统的标记清除的 gc 算法实现的一些看法。大多数实现中,都需要对 gc 模块分配出来的内存做特殊处理,在内存的头上放一些链接数据和预留标记位。IMHO ,当内存使用量较大,大过物理内存的量时,这种方案会导致收集过程异常缓慢。因为标记的过程需要访问几乎所有的内存块,这会导致大量的虚拟内存交换。就是说,无论你是否立即需要内存块里的数据,在收集过程中,每个内存块都需要碰一下。如果还包括设置标记的话,甚至需要改写虚拟内存中的数据。

我希望改进这一点,也就是说,那所有 gc 相关的数据集中在一起,整个收集过程,除了最终释放那些不再使用的内存外,不会碰用户数据块的内存。

gc 最重要的一点,就是要对堆栈上的数据进行关联。在收集发生时,堆栈上所有临时分配出来的内存块都不应该被释放掉。C 语言本身不提供堆栈遍历的特性,所以要想个自然的方案让用户可以方便的做到这点。

在用户的调用栈上,每个调用级上,临时分配的内存都被自然挂接在当前级别的堆栈挂接点上,一旦调用返回,当前级别的所有临时内存块都应该和根断开。当然,如果内存块作为返回值出现的话,需要保留。在 C 里,我们需要给每个函数的入口和出口都做一个监护,保证 gc 的正确工作。(如果是 C++ ,要稍微方便一点,在函数进入点设置一个 guard 对象即可)因为这个监护过程会非常频繁,对其的优化是重点工作。


最终,我的 gc 库暴露了 5 个 api 供用户使用:


void * gc_malloc(size_t sz, void (*free)(const void *));
void  gc_link(const void *parent, const void *prev, const void *child);
void gc_enter();
void gc_leave(const void *value, ... );
void gc_collect();

要申请内存时,可以调用 gc_malloc 申请 sz 大小的内存。free 函数指针可选。它提供一个机会,在内存真正释放之前做一些事情。

gc_link 用于建立内存块之间的联系。可以让 child 指针依赖 parent 指针。既,child 的生命期不会短于 parent 。这个 api 还可以取消 prev 和 parent 之间的联系。parent prev child 中任何一个都可以传空指针。当parent 为空时,child 挂接到根上。这通常用于维系全局变量的生命期。gc_link 保证 prev 在堆栈上有一次临时的引用。

gc_entergc_leave 当配对使用,放在一个函数或一段语句块的入口和出口处。夹在 enter 和 leave 之间的 gc_malloc 申请的内存块,生命期不会超过临近的 leave 指令。除非在 gc_leave 的参数中指明需要延长生命期。gc_leave 可以带多个指针,只需要最后一个以 0 结束。这通常用于函数的返回值。

gc_collect 用于垃圾收集,它可以在任何时机调用,把和根没有关联的内存块全部释放掉。堆栈上(没有闭合的 enter / leave 对)的所有 gc_malloc 分配的内存块都会被自动挂接在根上;用户也可以用 gc_link 主动挂接(parent 传 0)。


这套接口设计的应该是足够简洁了。用户只需要自己描述对象和对象之间的关系(使用 gc_link),别的不用太操心。

如果使用 C++ 可以进一步的封装,重载赋值操作符来做到这些。而 C 也可以定义一个宏来辅助(注意宏的一些问题,比如重复计算)。比如:


static void 
eval(void *parent,void **node,void *child)
{
    gc_link(parent,*node,child);
    *node=child;
}

#define EVAL(obj, prop, value) eval( (obj), & ((obj)-> ## prop), (value))

struct tree {
    struct tree *left;
    struct tree *right;
};

struct tree *
new_node()
{
    struct tree *n=(struct tree *)gc_malloc(sizeof(*n),0);
    memset(n,0,sizeof(*n));
    return p;
}

struct tree *
foo()
{
    struct tree *t;
    gc_enter();

    t=new_node();
    EVAL(t,left,new_node());
    EVAL(t,right,new_node());

    gc_leave(t,0);

    return t;
}

上面这个 foo 函数演示了 gc 模块的基本用法:构造了一个节点 t ,以及另外两个临时节点连接到 t 的 left 和 right 两个成员上。最后把 t 返回。


下面谈一下优化:

为了让用户数据块和关联数据分离,所以模块内部实现的时候,将指针映射到了内部 id 上,这里使用了一个 hash map 。这样,可以使用 id 保持相互关联的信息。

对象之间的关联信息是一个图结构。图的边的构建和变动复杂度较大。在实现时,做了一个 cache ,在 gc_link 的时候,不直接增删边。而是缓存对图变更的请求,并在缓冲期间合并一些操作。例如,一些临时的关联信息,可能因为周期很短,在 collect 发生前就已经解除关联,其操作就会被抵消掉。

cache 了大量操作后,对操作进行排序。批量修改图的边时,也可以减少大量的运算。(内部数据结构对图的每个节点的孩子采用一个有序数组保存,比较适合批量增删)

gc_entergc_leave 是优化的重点。因为这个调用最为频繁。而 gc_collect 发生较少,对象频繁进出堆栈,不需要重复挂接。

采用另一个 cache ,直接保存内存指针,甚至可以不做 hash map 查询(映射到内部 id ),只到 collect 发生时再一次计算。临时对象存在于堆栈上时,是一个树结构,而非图结构的关联关系(每个堆栈上的调用级是一个树节点)。这也有利于优化处理。


整个实现代码只用了 600 多行,但是却写了三个晚上。主要是为了提高处理效率(时间和空间效率),设计了一些精巧的数据结构,控制起来非常麻烦,写起来也很是小心。这次完成后,就可以替换掉去年实现的一个不太地道的 gc 模块了。当时的那个需要依赖一个单根的类树,用起来要麻烦的多。

如果日后开源的话,还有一些事情要做:代码需要更规范,补上更详细的测试代码,以及支持 64 位系统等。


6 月 10 日补充:

今天把它在 google code 上开源了,用的 BSD 的许可协议。第一个版本还很 dirty 。没有怎么测试,可能还有许多 bug 。

有兴趣的同学可以在这里用 svn check out (尚未 release ,没做下载包) :

http://code.google.com/p/manualgc/

ps. 我的英文很滥,注释和说明可以无视。

Comments

靠不住
我在openvpn buffer.h中看到了类似的代码。
代码链接打不开,非常想看的说,
俺的理解,把堆的使用方式,分成两种,一种是原来的堆的使用方式,用来存放生命周期不好决定的对象,另外一种就是把堆当栈来用,这些对象的生命周期有一定的依赖性,要么依赖某个对象,要么依赖某个函数,如果是依赖函数的话,就跟栈的出与入一样使用了
又看了一遍文章,感觉非常棒。
没测试 64 bit 下,程序用了一些 union ,可能需要把一些地方改成 intptr_t
程序 在 64位机器上 运行 崩溃 是什么原因?
好厉害啊!Thx。 这下内存管理就简单啰
写的不错
@cloud: 谢谢。最近看到glibc里的obstack,感觉有mainloop的程序,用obstack来管理内存也不错,mainloop可以写成这样: while (!quit) { obstack_init(mem_pool); quit=mainloop(); //mainloop里各函数需要的内存都用obstack_alloc来分配 obstack_free(mem_pool, NULL); } 云风觉得这样做可以吗?也可能我想的不太对。
@anon 比较合适的做法是在 gc 的内存翻越临界值后,设置一个标记。 然后在 mainloop 之外, leave 之后,判断这个标记,调用 collect 。 在 malloc 后检查临界值,然后调用 collect 也可以。但是会使峰值内存占用扩大一倍左右。因为当前 loop 占用的临时内存会无法立刻被回收掉。 诸如 java 这样内设 gc 的语言,其实也会有类似的问题(没有很好的 collect 时机),导致峰值内存占用量比实际需要的大。即,collect 发生时,一些即将作废的内存,还没有立刻失去引用。gc 是收集了一部分,而去期待下一次再回收这个部分。
@cloud 谢谢你的回答。在google code的例子里你给出下面的使用方式: while (!quit) { gc_enter(); quit=mainloop(); gc_leave(0); } 有些疑问:gc_leave不会回收已经过生命期的内存吧?那么在mainloop里应该是每次都会去分配新的内存,而gc_leave又不会回收,在循环过很多次后会不会导致很多garbage的产生?如果回收必须用gc_collect才可以,那么gc_collect又该写在哪里呢?
@anon 你可以检查 malloc 然后调用 abort 或者 exit 也可以做别的打算,比如返回 NULL 这个跟你的需求来定。
云风你好,问一个很弱的问题,看了你在google code中gc的实现代码,发现在实现中没有检查内存分配错误(比如map_expand的实现),如果在实际程序中使用,可能会导致因为内存分配失败导致segment fault,该如何修改才能避免这种情况?
写这个东西如果是为了练手,挺好。如果不是,建议再仔细研究一下现有的垃圾收集器,不要第二次发明轮子。
很期待云风的这个GC将来能支持多线程或同步收集。
“话说这 C 用的垃圾收集器,也不是没人做过,比如 这个 。不过它用的指针猜测的方法,总让人心里不塌实,也让人担心其收集的效率。” 有点扯 楼主是说Boehm-Demers-Weiser他们的收集器靠不住?
能不能给些这个收集器多线程方面的建议啊?
我觉得云风的代码写得很好啊。看起来很简洁清晰,不会是整理过了吧。
提个建议. 多线程GC可以考虑用OpenMP来写.
看得出来,云风也是一完美主义者。
handle的好处很多。 比如动态的内存位置这样的优势,随时对数据进行整理和搬移而不用去通知使用者。 直接用裸体的void*,感觉很冷。。。
@tigerdx8 当然可以,为空就什么都不干. 我昨天补了个简易的文档。
gc_malloc的参数finalization能为NULL吗?
@mike 我觉得这是在用理论去套设计,对于一些“成例”来说,虽然有“复合功能函数”之嫌,但是并不会造成什么障碍,而且可以简化接口。 看来云风受lua源码的影响很大呀。
@mike realloc 我认为是一个很好的设计,有了 realloc 后,malloc 和 free 都是多余的。如果一个模块需要重定义内存分配器,传一个 realloc 足够了。反过来, malloc/free 则不能替代 realloc 。 ============== 用realloc 代替 malloc/free, 会造成"函数名和功能不一致"的缺点,设计上应该尽可能避免.
不过觉得之所以C里手工用GC的价值不如直接用脚本层(隐藏了调用), 当然了,虚拟机GC的实现也可以直接用这套GC库:)
资源的引用是图结构的, 对于动态资源的管理更应该是属于系统的,人工对于动态的管理只有在预先做一定假设的情况才能实现. 对于复杂的项目,多多少少,程序员都会实现各种GC.
使用GC不仅是方便的理由, 而是本质的理由.
云风你好啊,你果然根本就不是人,是程序的神,是指针!!佩服!!
gc 存在的理由很多,简化开发是一个重要原因,但不是全部。对于底层开发更不是。 siney 应该记得上次在北京听的那个 Andrei 讲的 Lock-Free Data Structures 。 可以回忆一下没有 gc 的代价。那个 session , andrei 花了 80% 的时间讲解在没有 gc 的时候怎么解决资源释放的问题。而代码实现的大部分也是在绕过 gc 。 用不用 gc 最终是看整体的需求的。当对系统内的资源的生命期无法预测的时候,自动化管理就有必要。 自动化管理可以用 gc 也可以用引用计数。IMHO ,若不考虑混合方案,严格意义上的引用计数方案(不准用 raw 指针,全部用 smart ptr)比 gc 方案(所有指针都是 gc ptr)要低效的多。 已知资源的生命期则又是一种实现方法,可以有比 gc 更好的资源管理手段。比如 os 对进程的管理,apache 对连接的管理等等。 当单一模块规模较小时,又可以完全使用手工管理。即在代码逻辑上保证生命期正确。但当软件规模变大时,这几乎行不通。必须在更高层次结合自动化的方案。只是引用计数更容易实现罢了。
@Siney, 我说的是 main loop, 就是循环。 main loop 是一次又一次反复进入的。比如说消息循环。 用了 gc 后,就不再需要 c++ 的 new 和 delete . enter 和 leave 在实现上等价于调整堆栈指针,其代价比 C++ 的 new /delete 要小的多,和对象数量无关。和 C 编译器为函数调用生成的保存寄存器值的代价近似( C 函数调用的开销和函数体积无关)。
云风的意思似乎是这样: while(1){ enter .... leave }
引用"@Siney 大部分情况下,enter 和 leave 是不用关注的。比如游戏这种有明显的 main loop 的结构。你就当成是一个大函数, 在进入 main loop 前 enter 一下,退出 main loop 后 leave 一下足够了。 " 如果是这样,该gc的用处也不大,因为: 1)一旦游戏main loop结束,意味着app exit,gc与否都无所谓,因为系统会强制回收内存; 2)给予观点1,这势必造成更小粒度的调用enter,leave,这同样会陷入c++的new/delete矛盾,如何选择gc的粒度,以及需要调用enter、leave、link等一系列函数才能在合适的地方collect,我认为该gc方案没有减轻程序员的工作。 最后云风似乎不认为gc是为了方便程序员而设计,而是软件合理设计的需要,对此我不以为然,编程语言本无gc,c语言亦然,我相信存在很多设计合理而没有使用gc的c程序。而我们目标的java、c#等语言提出gc的理由也无非是方便程序开发。
对于GC你有如下几种选择: NotGC 不进行GC HumanGC 人肉GC LibGC 库GC SystemGC 系统GC 至于云风的GC,我定义为LGC。 自然,你拥有无限内存的情况下,NGC是不错的选择。 Just A Joke.
@Siney 大部分情况下,enter 和 leave 是不用关注的。比如游戏这种有明显的 main loop 的结构。你就当成是一个大函数, 在进入 main loop 前 enter 一下,退出 main loop 后 leave 一下足够了。 @mike realloc 我认为是一个很好的设计,有了 realloc 后,malloc 和 free 都是多余的。如果一个模块需要重定义内存分配器,传一个 realloc 足够了。反过来, malloc/free 则不能替代 realloc 。 当然到了 C++ 时代,realloc 就是个多余的东西了。 @teddy 既然都做过,这样比较有共同话题 :) 暴露给用户 handle 还是 raw pointer 我是仔细考虑过的。最终希望被 handle 隐藏起来。这跟 malloc 不返回给用户 handle 的道理类似。 毕竟使用 handle 会增加用户许多代码。而交给用户 raw pointer 更符合 C 的哲学。另外,有这样一个间接层比较方便实现 weak pointer 。对内部数据结构设计也更方便。handle 可以尽快的回收,不用担心有泄露。 你说的 local frame 对应到 enter/leave 上,我们的设计是一致的. 不过我在实现上做了一些优化。local frame 上的东西并不直接 link 到一个 object 上,而是做了 cache ,保证到 stack 的引用操作足够的快。这个可以参考具体实现。 只做全局对象的话,设计会简单的多。其实大量代码都是为了实现对象间引用的。我认为不做对象间引用,这套东西就没有意义了。 to 不留名的那位, 我留了 finalization 方法。 ps. 看来需要整理 faq 了。另外,我不觉得 gc 是用来给程序员偷懒用的,用不用 gc 是软件合理设计的需要。
怎么没有下载了?删除下载了吗?
如果C一些库需要自己Rlease的handler,怎么解决,手工释放?
没觉的有多好, 只是增加代码复杂.
晕,我也做了一个,不过不是给用户指针的,还是给handle的,因为虽然指针可以回查,但是考虑指针可以做算术运算,太灵活了,给用户handle,并且在从handle提出指针的时候做临时关闭gc的动作。因为我也提供了一个线程。现在看来,我做的太复杂了,用起来很让人不太舒服。0)0.,.云风的看上去更实用一些。因为接口保持简单是非常重要的,不然的话,给用户一个GC只是给了另外一把自宫的刀子。 我的handle使用只有两个方式:全局和对象之间,全局用户要做引用计数,对象之间不需要。局部引用采用local frame 来做,相当于对象间的。 作为那个enter/leave, 我的叫做local frame,是可以push和pop,并且有局部引用的概念, 因为用户new一个handle的时候希望是global的还是局部引用的,pop只解除局部引用,其实local frame 相当于一个object. 那个用户link object,对于数组可能比较繁杂的,所以我是得应该给用户一个已经做好的“低级”数组对象建议取代C数组比较好。 目前比较难办的是做隔代收集,很难去跟踪handle赋值。 我也是业余做着玩的,没想到真的还有别人做,关注一下,也学习一下。 另,那个Geohm GC也是挺强的,不过是保守式的,会有泄漏,另外架构依赖,无法很容易移植,但是是简单的。
给C用的GC接口就是这样用!如果用C写自己的脚本引擎,就可以把把enter和leave隐藏在虚拟机内部了。何必太执着于语言细节呢?
考虑 realloc 的接口设计,realloc 第一个参数传 0 ,等同于 malloc 。 第 2 个参数传 0 则等价于 free ==================== realloc 的接口设计,这是一个典型的不好的设计.
我想说,如果gc要这样使用,还有gc的意义吗? gc不就是为了让程序员偷懒吗,这样反而更繁琐了,如果忘记了enter、leave对会怎么样?
我觉得指责云风代码质量的话。。。实在是难以想象
云风,从你这里学到了好多东西,看你的文章有一种醍醐灌顶的感觉。
全局变量 E 是留给以后替换用的。 CRT 中默认的内存分配器都不能携带 heap 参数。E 相当于一个 heap 。改到自己的代码里用的话,可以将 E 改成用 gc_init 创建出来,并由 gc_exit 销毁。别的 api 都需要传入这个参数。 变量名和函数名的问题: 因为我的英文太滥,又不想用汉语拼音做变量名,所以就这样了。 其实接口设计完毕后,代码怎么实现都无所谓了。这段代码暴露出来的东西,除了接口外,就是 CRT 的内存分配函数,可以通过定义好的宏修改掉,或者干脆做成函数指针由 gc_init 注册到 E 里面。
可能他觉得代码中的某些变量名不易读,不符合他们那里的约定吧,尤其有个全局变量E。 没什么关系啦,主要还是拿来学习的,看懂了原理才是最重要的,觉得不爽自己再实现一边也可,我想云风也应该是出于这个目的才开源的。加油!!!
quick and dirty 啦。 这些代码的确不容易理解。因为考虑到效率,设计了一些奇怪的数据结构。 这些也不是写来给人看的,是写出来用的。btw, 不过我很奇怪楼下的说这样的代码一定要重构?我没觉得我写了什么离经叛道的东西啊,这么严重?
今天看了云风的代码,以前都没见过,不过看了有点失望,虽说代码回归C我也不是持反对意见,不过可读性个人觉得实在太差,看不出什么水平来。不知道是开源了才是这样么?如果是项目里面的在我们这边这些代码肯定是要被重构掉。不过开源分享的精神我非常喜欢,支持。
整套api的正交性还是不错的,错误处理能力很弱啊,如果考虑加入到一个透明性要求很高的系统中,错误处理要更强才能满足需要。 接口的设计或多或少会受到实现中数据结构的影响吧,这里的gc_link是否有点暴露过多的细节了呢?
云风真的不是个人,佩服啊
考虑 realloc 的接口设计,realloc 第一个参数传 0 ,等同于 malloc 。 第 2 个参数传 0 则等价于 free 。
因为有可能需要这样一个原子操作。 如果只是要建立连接,可以用 gc_link (parent,0,child); 只是断开连接,可以用 gc_link (parent,prev,0); 这个 api 之所以要同时实现两者,是要模拟 a->b = c 这样的操作。 不正交指哪方面?
对 gc_link 的功能有些不太明白。调用一次 gc_link 是可以在建立 parent 与 child 关联的同时消除 parent 与 prev 间的关联么? 如果是这样的话,api是否显得有些不正交啊。  
一定要开源啊,说明我没完全看明白
支持开源,好让我拜读一下!
不错。。。
知道这个讨论不好,不过带有gc的c还是c吗?
同样期待开源,一开始可以发布一个0.001版本,然后大家都来研究研究。:)
太厉害了
支持开源,开源后一步一步来,没必要全部整理好了才开源
没句柄。不习惯 void * gc_new(size_t sz, void (*free)(const void *));
哈哈。一上班就看到新东西,愉快

Post a comment

非这个主题相关的留言请到:留言本