在C中查找垃圾收集的根

Question

我正在尝试在C中实现一个简单的标记和清除垃圾收集器.算法的第一步是找到根.所以我的问题是如何在C程序中找到根源？

在使用malloc的程序中,我将使用自定义分配器.这个自定义分配器是从C程序调用的所有东西,也可以是自定义的init().

垃圾收集器如何知道程序中的所有指针(根)？另外,给定一个自定义类型的指针,它如何得到所有指针？

例如,如果有一个指向类列表的指针p,其中有另一个指针...说q.垃圾收集器如何知道它,以便它可以标记它？

更新:如果我在启动它时将所有指针名称和类型发送到GC怎么样？类似地,也可以发送不同类型的结构,以便GC可以遍历树.这甚至是一个理智的想法还是我只是疯了？

Answer 1

首先,垃圾收集器在C,没有广泛的编译器和操作系统的支持,必须是保守的,因为你不能合法的指针,出现这种情况有,看起来像一个指针的整数区分.甚至保守的垃圾收集者也很难实施.喜欢,真的很难.通常,您需要约束语言才能获得可接受的东西:例如,如果指针被隐藏或混淆,则可能无法正确收集内存.如果你分配100个字节并且只保留指向分配的第十个字节的指针,你的GC不太可能知道你仍然需要该块,因为它将看不到对开头的引用.控制的另一个非常重要的限制是内存对齐:如果指针可以在未对齐的内存上,则收集器可以减慢10倍或更差.

要找到根,您需要知道堆栈的起始位置以及堆栈的结束位置.注意复数形式:每个线程都有自己的堆栈,您可能需要考虑到这一点,具体取决于您的目标.要知道堆栈开始,没有进入特定平台的细节(我可能会无法提供反正),你可以用汇编代码当前线程(只是主函数中main的非螺纹可执行文件)查询堆栈寄存器(esp在x86上,rsp在x86_64上仅为这两个命名).Gcc和clang支持语言扩展,允许您将变量永久分配给寄存器,这应该使您更容易:

register void* stack asm("esp"); // replace esp with the name of your stack reg

(register是一种标准语言关键字,大部分时间被今天的编译器忽略,但加上它asm("register_name"),它可以让你做一些讨厌的东西.)

为了确保您不会忘记重要的根,您应该将该main函数的实际工作推迟到另一个.(在x86平台上,你也可以查询ebp/ rbp,堆栈框架基本指针,而且仍然在main函数中完成你的实际工作.)

int main(int argc, const char** argv, const char** envp)
{
    register void* stack asm("esp");
    // put stack somewhere
    return do_main(argc, argv, envp);
}

进入GC进行收集后,需要查询当前堆栈指针以查找已中断的线程.您将需要特定于设计和/或特定于平台的调用(尽管如果您在同一个线程上执行某些操作,上述技术仍然有效).

现在开始实际寻找根.好消息:大多数ABI都要求堆栈帧在大于指针大小的边界上对齐,这意味着如果您信任每个指针都在对齐的内存上,您可以将整个堆栈视为a intptr_t*并检查是否有任何模式里面看起来像你的任何托管指针.

显然,还有其他根源.全局变量可以(理论上)是根,结构内的字段也可以是根.寄存器也可以有指向对象的指针.你需要单独考虑可以作为根的全局变量(或者完全禁止这一点,在我看来这不是一个坏主意)因为自动发现那些很难(至少,我不知道怎么做)在任何平台上).

这些根可以导致堆上的引用,如果你不注意,事情可能会出错.

由于并非所有平台都提供malloc内省(据我所知),您需要实现扫描内存的概念 - 即GC知道的内存.它至少需要知道每个这种分配的地址和大小.当您获得对其中一个的引用时,您只需扫描它们以获取指针,就像您对堆栈所做的那样.(这意味着您应该注意指针是否已对齐.如果您让编译器完成其工作,通常就是这种情况,但在使用第三方API时仍需要小心).

这也意味着您无法将可收集内存的引用放到GC无法访问的位置.这是最痛苦的地方,也是你需要特别小心的地方.否则,如果您的平台支持malloc 内省,您可以轻松地告诉您获得指针的每个分配的大小,并确保不会超出它们.

这只是触及了主题的表面.垃圾收集器非常复杂,即使是单线程也是如此.当你为混音添加线程时,你会进入一个全新的伤害世界.

Apple已经为Objective-C语言实现了这样一个保守的GC,并将其命名为libauto.他们开源了它,以及Mac OS X的低级技术的很大一部分,你可以在这里找到源代码.

我只能在这里引用Hot Licks:祝你好运!

好的,在我走得更远之前,我忘记了一些非常重要的事情:编译器优化可能会破坏GC.如果你的编译器不知道你的GC,它很可能永远不会在堆栈上放置某些根(只在寄存器中处理它们),你会想念它们.如果您可以检查寄存器,这对于单线程程序来说不是太困难,但对于多线程程序来说,这又是一个巨大的混乱.

还要非常小心分配的可中断性:你必须确保你的GC在你返回一个新指针时无法启动,因为它可以在它被分配到根之前收集它,并且当你的程序恢复它时它将分配这个新的悬空指针指向你的程序.

这是一个解决编辑的更新:

更新:如果我在启动它时将所有指针名称和类型发送到GC怎么样？类似地,也可以发送不同类型的结构,以便GC可以遍历树.这甚至是一个理智的想法还是我只是疯了？

我想你可以分配我们的内存然后用GC注册它告诉它它应该是一个托管资源.这将解决可中断性问题.但是,请注意发送给第三方库的内容,因为如果他们保留对它的引用,那么GC可能无法检测到它,因为它们不会向GC注册其数据结构.

你很可能无法在堆栈上使用root.

Answer 2

根基本上都是静态和自动对象指针.静态指针将在加载模块内链接.必须通过扫描堆栈帧找到自动指针.当然,你不知道自动指针在堆栈框架中的位置.

一旦你有了根,你需要扫描对象并找到它们内的所有指针.(这将包括指针数组.)为此,您需要识别类对象,并以某种方式从中提取有关指针位置的信息.当然,在C中,许多对象不是虚拟的,并且在它们中没有类指针.

祝好运!!

补充: 一种可能模糊地使你的任务成为可能的技术是"保守"的垃圾收集.由于您打算拥有自己的分配器,您可以(以某种方式)跟踪分配大小和位置,因此您可以从存储中挑选任何指针大小的块,并询问"这可能是指向我的某个对象的指针吗？" 当然,您可以永远不知道,因为随机数据可能"看起来像"指向您的某个对象的指针,但您仍然可以通过此机制扫描一大块存储(如调用堆栈中的帧,或单个对象)并识别它可能解决的所有可能的对象.

对于保守的收集器,您无法安全地执行对象重定位/压缩(在移动对象时修改对象的指针),因为您可能会意外地修改看起来像对象指针的"随机"数据,但实际上对某些应用程序来说是有意义的数据.但是,您可以识别未使用的对象并释放它们占用的空间以便重复使用.通过适当的设计,可以实现非常有效的非压缩GC.

(但是,如果您的C版本允许未对齐的指针扫描可能会非常慢,因为您必须尝试字节对齐的每个变体.)