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

基本上，我有兴趣在 C 中编写一个 平台独立的 垃圾收集器，可能使用标记和清除算法或其常见变体之一。理想情况下，界面将按照以下方式工作:

(1) gc_alloc() 分配内存

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

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

我已经看过 Boehm 等人开发的 libgc 垃圾收集库。 al.，但它不是平台独立的；它刚刚被移植到许多不同的系统。我想实现一个不包含系统相关代码的垃圾收集器。速度不是大问题。

有什么建议么？

最佳答案

不幸的是，在 C 中创建真正独立于平台的垃圾收集器是不可能的。严格阅读 C 标准允许任何类型(除了 unsigned char )具有陷阱位 - 位，当它们具有错误值时，会导致系统发出异常信号(即，未定义的行为)。在为指针扫描分配的块时，您无法确定特定的内存块是否包含合法的指针值，或者一旦您尝试查看其中的值，它是否会陷入困境。

将指针检查为 int 也无济于事 - 不需要 int 类型来表示与指针兼容。 intptr_t 仅在最新的编译器上可用，而且我认为它的表示也不需要兼容。整数也可以有陷阱位。

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

但更大的问题是找到根集。 Bohem GC 和其他人倾向于扫描堆栈以及静态数据，以查找应该进入根集的指针。 如果不了解操作系统的内存布局 ，这是不可能的。所以你需要让用户明确标记根集的成员，这有点违背垃圾收集器的意义。

所以，简而言之，你不能在真正可移植的 C 中进行 GC。原则上，如果你做一些假设，你可以:

假设根集将由用户明确提供给您。

假设指针或 int 表示中没有陷阱位。

假设 intptr_t 可用或假设所有 void * 都是严格排序的(即，< 和 > 可以合理地使用来自不同 malloc 的指针)

假设所有数据指针类型都具有与 void * 兼容的表示。

可选，但大大提高了速度:硬编码指针的对齐方式(这远非通用，并且需要特定于编译器和平台)此假设将让您跳过 memcpy ing 指针到已知对齐位置，并且还将减少要检查的潜在指针的数量。

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

请注意，这一切仅适用于保守的 GC - 即盲目地工作，扫描数据中的指针而不知道它可能在哪里。如果您在 VM 上工作，那就容易多了 - 您可以为 VM 的所有分配构建统一的数据类型，明确列出可以找到指针的位置。有了这个加上一个显式的根集，你就可以构建一个非保守的 GC；这应该足以构建 VM 或解释器。

关于c - 如何实现独立于平台的垃圾收集器？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4969150/