c - 如何实现平台无关的垃圾收集器？

Question

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

(1) gc_alloc()分配内存

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

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

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

有什么建议吗？

Answer 1

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

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

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

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

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

• 假设根集将由用户明确提供给您。
• 假设指针或 int 表示中没有陷阱位。
• 假设intptr_t可用或假定所有void * s 是严格排序的(即 < 和 > 与来自不同 malloc 的指针一起合理工作)
• 假设所有数据指针类型都具有与 void * 兼容的表示形式.
• 可选，但可以大大提高速度:硬编码指针对齐(这远非通用，需要特定于编译器和平台)这个假设会让你跳过 memcpy将指针指向已知对齐的位置，并且还将减少要检查的潜在指针的数量。

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

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