如何实现一个跨平台的垃圾收集器?

4
基本上,我想写一个平台无关的垃圾收集器,使用标记-清除算法或其常见变体之一,使用C编程语言。理想情况下,接口应按以下方式工作:
(1) gc_alloc() 分配内存
(2) gc_realloc() 重新分配内存
(3) gc_run() 运行垃圾收集器。
我已经查看了由Boehm等人开发的libgc垃圾收集库,但它不是平台无关的;它只是被移植到许多不同的系统。我想实现一个不包含任何系统相关代码的垃圾收集器。速度不是一个很大的问题。
有什么建议吗?

2
由于纯C语言无法访问整个堆栈,因此无法独立于平台地遍历堆栈以查找GC根。 - Steve Jessop
@bdonlan:说得好,我已经浏览了一些以前的问题并接受了最佳答案。 - user365636
@Steve 应该是正确的。不过,如果你能够替换自己的堆栈(或其他 GC root 源) - 例如在虚拟机/解释器中 - 应该是可能的。 - user395760
我在想是否有任何可能的解决方法——例如以某种其他方式存储对象指针列表。实际上,我对Lua(http://lua.org)使用的垃圾收集器实现很感兴趣;不幸的是,我发现该解释器的大部分代码非常密集且注释不足。 - user365636
@delnan:是的,但最终这只是在说可以使用可移植的C语言编写完整的C实现。这是正确的,但仅为您的托管实现提供垃圾收集器,而不是底层实现。您也可以在Jython或Lisp中编写C解释器,并为其实现GC。您将拥有一个带有垃圾回收功能的C实现,但您不会得到提问者想要的东西,即使现有的实现具有垃圾回收功能。 - Steve Jessop
2个回答

9
很遗憾,在C语言中很难做到真正意义上的跨平台垃圾回收。C标准允许任何类型(除了unsigned char)都有trap bit,即当这些位的值错误时会导致系统发出异常信号(即未定义行为)。在扫描指针分配块时,您无法确定特定内存块是否包含合法指针值,或者在尝试查看其中的值时是否会触发异常。
将指针作为int检查也没有帮助 - 没有任何int类型要求与指针兼容。intptr_t仅适用于非常新的编译器,我认为它的表示形式也不需要兼容。而且int也可能有陷阱位。
您还不知道指针的对齐要求。在指针没有对齐要求的平台上(即可以从任意字节开始的平台),这意味着您需要在每个字节停止,将其memcpy到适当的指针类型,并检查结果。哦,不同的指针类型也可以有不同的表示,这也是无法避免的。
但更大的问题是找到根集。 Bohem GC和其他垃圾回收器倾向于扫描堆栈以及静态数据,以查找应该放入根集的指针。这在不知道操作系统内存布局的情况下是不可能的。因此,您需要让用户显式标记根集成员,这有点破坏了垃圾回收器的作用。
因此,简而言之,在真正的可移植C中无法实现GC。原则上,如果做出一些假设,则可以:
- 假设用户将明确提供根集。 - 假设指针或int表示中没有trap bit。 - 假设intptr_t可用或假设所有void *都严格排序(即<和>对来自不同malloc的指针起作用) - 假设所有数据指针类型都与void *兼容。 - 可选但可大大提高速度:硬编码指针的对齐方式(这远非普及,需要与编译器和平台相关)。此假设将使您跳过将指针memcpy到已知对齐位置,并减少可能要检查的指针数。
如果您做出这些假设,那么您应该能够创建一个保守的标记-清除分配器。使用二叉树来保存有关分配位置的信息,并在已分配块中扫描每个可能的对齐指针位置以查找指针。然而,需要明确提供根集将使所有这些工作都毫无意义 - 这将变成像mallocfree一样,只是对于某些不明确定义的对象集,您可以跳过它。这并不完全符合GC应该提供的功能,但我想它可能有其作用,例如作为虚拟机的一部分(在这种情况下,根集将从虚拟机可用的信息中派生)。
请注意,所有这些仅适用于保守的GC - 即,在不知道数据可能在哪里的情况下盲目地扫描指针的GC。如果您正在开发VM,则会更容易 - 您可以通过VM构建统一的数据类型,该类型明确列出了指针可以找到的位置。通过此加上明确的根集,您可以构建非保守型GC;这应足以构建VM或解释器。

+1 很好的答案,谢谢。只有一个问题:你上面写道“C标准的严格解读允许任何类型(除了C)...”---你所说的“除了C”是什么意思? - user365636
糟糕,我是想说“unsigned char”的,怎么会出错了? :) - bdonlan
@Thomas 如果你认为这是一个很好的答案,那么你应该接受它。 - Jim Balter

0

对于一个标记清除算法,你只需要计算哪些对象可以从根集到达,是吗?(我已经有一段时间没有深入研究了……)

这可以通过为GC管理的对象创建单独的对象图来实现,“所有”你需要做的就是在分配或修改托管对象时添加适当的函数来管理该图。 如果您还为托管对象添加引用计数,将更容易计算哪些对象可以直接从堆栈引用中到达。

这可能很容易编写成相当独立于平台的代码,尽管这是否真正是垃圾收集器可能存在争议。

简单的伪代码展示了我的引用计数和图形管理意思:

some_object * pObject = gc_alloc(sizeof(some_object));
some_container * pContainer = gc_alloc(sizeof(some_container));

pContainer->pObject = pObject;
/* let the GC know that pContainer has a reference to pObject */
gc_object_reference(pContainer, pObject);

/* a new block of some kind */
{
    /* let the GC know we have a new reference for pObject */
    some_object * pReference = gc_reference(pObject); 

    /* do stuff */
    ...

    /* let the GC know that this reference is no longer used */
    gc_left_scope(pReference);
}

gc_left_scope(pObject);
gc_run(); /* should not be able to recycle anything, since there still is a live
           * reference to pContainer, and that has a reference to pObject
           */

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接