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

Question

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

(1)gc_alloc()分配内存

(2)gc_realloc()重新分配记忆

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

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

有什么建议？

Answer 1

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

将指针检查为int也无济于事 - 不需要int类型来使表示与指针兼容.intptr_t仅适用于最近的编译器,我不认为它的表示也需要兼容.而且int也可以有陷阱位.

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

但更大的问题是找到根集.Bohem GC和其他人倾向于扫描堆栈以及静态数据,以获取应该放在根集中的指针.如果不了解操作系统的内存布局,这是不可能的.因此,您需要让用户明确标记根集的成员,这类会使垃圾收集器失败.

因此,简而言之,您无法在真正的便携式C中制作GC .原则上,如果您做出一些假设,您可以:

• 假设用户将明确地为您提供根集.
• 假设指针或int表示中没有陷阱位.
• 假设intptr_t可或承担所有void *s的严格(即,有序<和>与不同的指针合理工作mallocations)
• 假设所有数据指针类型都具有与之兼容的表示void *.
• 可选,但提供了很大的速度提升:硬编码指针的对齐(这远非通用,并且需要特定于编译器和平台)这个假设将允许您跳过memcpy指向已知对齐位置的指针,并且还减少了要检查的潜在指针的数量.

如果你做出这些假设,你应该能够制作一个保守的标记扫描分配器.使用二叉树来保存有关分配位置的信息,并扫描分配的指针块中每个可能的对齐指针位置.然而,需要明确规定根定会让这一切毫无意义-这将是malloc与free一遍,但一定不明确的对象集合,你可以跳过它.不完全是GC应该提供的,但我想它可能有它的位置,例如,虚拟机的一部分(在这种情况下,根集将从虚拟机可用的信息派生).

请注意,这一切都只适用于保守的 GC - 即盲目工作,在不知道数据位置的情况下扫描数据中的指针.如果您正在使用VM,则更容易 - 您可以为VM的所有分配构建统一数据类型,以明确列出可以找到指针的位置.使用此加上一个显式的根集,您可以构建一个非保守的GC; 这应该足以构建VM或解释器.