如何实现独立于平台的垃圾收集器？

Question

基本上，我对在platform-independent C中编写一个垃圾收集器感兴趣，可能使用标记和扫描算法或其常见的变体之一。理想情况下，接口将按照以下思路工作：

(1) gc_alloc()分配内存

(2) gc_realloc()重新分配内存

(3) gc_run()运行垃圾收集器。

我已经看过了由Boehm et开发的libgc垃圾收集库。但是它并不是独立于平台的，它只是被移植到许多不同的系统上。我想实现一个垃圾收集器，它不包含依赖于系统的代码。速度不是个大问题。

有什么建议吗？

Answer 1

不幸的是，在C中不可能产生真正独立于平台的垃圾收集器。对C标准的严格读取允许任何类型(unsigned char除外)具有陷阱位位，当它们有错误的值时，导致系统发出异常信号(即，未定义的行为)。当扫描已分配的块以查找指针时，您无法确定某个特定内存块是否包含合法指针值，或者当您试图查看其中的值时，它是否会被捕获。

检查指针作为int也没有帮助-不需要int类型具有与指针兼容的表示形式。intptr_t只能在最近的编译器上使用，我也不认为它的表示必须兼容。而ints也有陷阱位。

您也不知道指针的对齐要求。在指针没有对齐要求的平台上(即，可以从任何字节开始)，这意味着您需要停止在每个字节，memcpy到一个合适的指针类型，并检查结果。哦，不同的指针类型也可以有不同的表示，这也是不可避免的。

但更大的问题是找到根集。Bohem GC和其他人倾向于扫描堆栈以及静态数据，以查找应该在根集中传递的指针。--如果不了解操作系统的内存布局，这是不可能的。因此，您将需要让用户显式地标记根集的成员，这样就会击败垃圾收集器的点。

因此，简而言之，您不能在真正的便携C中生成GC。原则上，如果您做了一些假设，您就可以做到：

representations.

• Assume

• 假定用户将显式地给出根集。

• 假设指针中没有陷阱位，或者int void *.

• Optional，intptr_t是可用的，或者假定所有void *都是严格排序的(即，<和>可以合理地处理来自不同mallocations)

• Assume的指针-所有数据指针类型都具有与void *.

• Optional，兼容的表示形式，但提供了很大的速度提升:硬编码指针的对齐(这远远不是通用的)，这一假设将允许您跳过指向已知对齐位置的memcpying指针，并且还将减少要检查的潜在指针的数量。

如果你做了这些假设，你应该能够做一个保守的标记扫描分配器。使用二叉树保存有关分配位置的信息，并扫描分配块中每个可能对齐指针位置的指针。但是，显式提供根集的需要将使这一切变得毫无意义--这将再次是malloc和free，但对于某个定义不明确的对象集，您可以跳过它。不完全是GC应该提供的，但我认为它可能有它的位置，例如，作为虚拟机的一部分(在这种情况下，根集将从虚拟机可用的信息中派生出来)。

请注意，这一切只适用于保守的GCs -即那些盲目工作的GC，在不知道数据可能在哪里的情况下扫描数据中的指针。如果您正在处理VM，这要容易得多--您可以为VM为所有分配构建统一的数据类型，该VM显式列出可以找到指针的位置。通过这一点加上一个显式根集，您可以构建一个非保守的GC；这应该足以构建VM或解释器。

Answer 2

对于标记和扫描算法，您真正需要做的就是计算哪些对象可以从根集到达，对吗？(我很久以前就不知道这个了.)

这可以由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
           */