很遗憾,在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到已知对齐位置,并减少可能要检查的指针数。
如果您做出这些假设,那么您应该能够创建一个保守的标记-清除分配器。使用二叉树来保存有关分配位置的信息,并在已分配块中扫描每个可能的对齐指针位置以查找指针。然而,需要明确提供根集将使所有这些工作都毫无意义 - 这将变成像
malloc
和
free
一样,只是对于某些不明确定义的对象集,您可以跳过它。这并不完全符合GC应该提供的功能,但我想它可能有其作用,例如作为虚拟机的一部分(在这种情况下,根集将从虚拟机可用的信息中派生)。
请注意,所有这些仅适用于
保守的GC - 即,在不知道数据可能在哪里的情况下盲目地扫描指针的GC。如果您正在开发VM,则会更容易 - 您可以通过VM构建统一的数据类型,该类型明确列出了指针可以找到的位置。通过此加上明确的根集,您可以构建非保守型GC;这应足以构建VM或解释器。