c - 在C中寻找垃圾收集的根源

Question

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

在使用malloc的程序中，我将使用自定义分配器。该自定义分配器将是所有从C程序中调用的分配器，并且可以是自定义init()。

垃圾收集器如何知道程序中所有的指针(根)？另外，给定自定义类型的指针，它如何获取其中的所有指针？

例如，如果有一个指向类列表的指针p，它里面有另一个指针。垃圾收集器如何知道它，以便对其进行标记？

更新:如果在初始化时将所有指针名称和类型都发送给GC，该怎么办？同样，也可以发送不同类型的结构，以便GC可以遍历树。这甚至是一个理智的想法，还是我快要疯了？

Answer 1

首先，C语言中的垃圾收集器(没有广泛的编译器和OS支持)必须保守一些，因为您无法区分合法指针和恰好具有看起来像指针的值的整数。甚至保守的垃圾收集器也难以实现。喜欢，真的很难。通常，您需要限制语言以获得可接受的内容:例如，如果隐藏或混淆了指针，则可能无法正确收集内存。如果您分配100个字节并仅保留指向分配的第十个字节的指针，则您的GC不太可能弄清楚您仍然需要该块，因为它将看不到开头。要控制的另一个非常重要的约束是内存对齐:如果指针可以位于未对齐的内存上，则收集器的速度可能会降低10倍甚至更慢。

要找到根，您需要知道堆栈的开始位置和堆栈的结束位置。注意复数形式:每个线程都有其自己的堆栈，您可能需要考虑到这一点，具体取决于您的目标。要知道堆栈从哪里开始，而无需输入特定于平台的详细信息(无论如何我都无法提供)，可以在当前线程的主要功能内使用汇编代码(仅在非线程可执行文件中使用main即可) )查询堆栈寄存器(x86上的esp，x86_64上的rsp仅命名这两个)。 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都要求堆栈框架在大于指针大小的边界上对齐，这意味着，如果您信任每个指针都在对齐的内存上，则可以将整个堆栈视为intptr_t*并检查是否有任何里面的模式看起来像任何托管指针。

显然，还有其他根源。全局变量可以(理论上)可以是根，而结构内部的字段也可以是根。寄存器也可以具有指向对象的指针。您需要分别考虑可能是根的全局变量(或完全禁止，这在我看来这不是一个坏主意)，因为自动发现这些变量将很困难(至少，我不知道该怎么做)在任何平台上)。

这些根可以导致在堆上进行引用，如果不注意，那里的内容可能会出错。

由于并非所有平台都提供malloc自省(introspection)(据我所知)，因此您需要实现扫描内存的概念，也就是GC知道的内存。它至少需要知道每个此类分配的地址和大小。当获得对其中之一的引用时，只需扫描它们以查找指针，就像对堆栈所做的一样。 (这意味着您应注意将指针对齐。如果让编译器执行其工作，通常是这种情况，但是在使用第三方API时仍要小心)。

这也意味着您不能将对可收集内存的引用放置到GC无法到达的地方。这是伤害最大的地方，您需要格外小心。否则，如果您的平台支持malloc内省(introspection)，则可以轻松地告诉您所指向的每个分配的大小，并确保不超出它们的范围。

这只是在摸索主题的表面。即使是单线程，垃圾收集器也非常复杂。当您将线程添加到混合中时，您将进入一个全新的痛苦世界。

苹果已经为Objective-C语言实现了这种保守的GC，并将其命名为libauto。他们已经将其开源，以及Mac OS X的许多低级技术的一部分，您可以find the source here。

我只能在这里引用“Hot Licks”:祝您好运!

好的，在继续之前，我忘记了一些非常重要的事情:编译器优化会破坏GC。如果您的编译器不知道您的GC，则它绝对不能将某些根放在堆栈上(仅在寄存器中处理它们)，而您会错过它们。如果您可以检查寄存器，那么对于单线程程序来说，这并不是太麻烦，但是对于多线程程序而言，同样如此。

另外还要特别注意分配的可中断性:您必须确保GC在返回新指针时不会踢入，因为它可以在分配给根之前立即收集它，并且在程序恢复时会进行分配指向程序的新悬挂指针。

这是解决该更新的更新:

Update: How about if I send all the pointer names and types to GC when I init it? Similarly, the structure of different types can also be sent so that GC can traverse the tree. Is this even a sane idea or am I just going crazy?

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

而且您可能无法使用堆栈中的根来执行此操作。