我正在尝试在 C 中实现一个简单的标记和清除垃圾收集器。算法的第一步是找到根。所以我的问题是如何在 C 程序中找到根源？
在使用 malloc 的程序中，我将使用自定义分配器。这个自定义分配器就是将从 C 程序调用的所有内容，并且可能是自定义 init()。
垃圾收集器如何知道程序中的所有指针（根）是什么？另外，给定一个自定义类型的指针，它如何获取其中的所有指针？
例如，如果有一个指针 p 指向一个类列表，它里面有另一个指针..说 q。垃圾收集器如何知道它，以便它可以标记它？
更新：如果我在初始化时将所有指针名称和类型发送给 GC 怎么样？同样，也可以发送不同类型的结构，让GC遍历树。这甚至是一个理智的想法还是我只是疯了？
首先，没有广泛的编译器和操作系统支持的 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 将要求堆栈帧在大于指针大小的边界上对齐，这意味着如果您相信每个指针都在对齐的内存上，您可以将整个堆栈视为 aintptr_t*并检查是否有任何模式inside 看起来像您的任何托管指针。
显然，还有其他根源。全局变量（理论上）可以是根，结构内的字段也可以是根。寄存器也可以有指向对象的指针。您需要单独考虑可以是根的全局变量（或完全禁止，在我看来这不是一个坏主意），因为自动发现这些变量会很困难（至少，我不知道该怎么做在任何平台上）。
这些根可能导致堆上的引用，如果你不小心，事情可能会出错。
由于并非所有平台都提供malloc自省（据我所知），因此您需要实现扫描内存的概念——即您的 GC 知道的内存。它至少需要知道每个此类分配的地址和大小。当您获得对其中之一的引用时，您只需扫描它们以查找指针，就像您为堆栈所做的那样。（这意味着你应该注意你的指针是对齐的。如果你让你的编译器完成它的工作，这通常是这种情况，但是当你使用第三方 API 时你仍然需要小心）。
这也意味着您不能将对可收集内存的引用放在 GC 无法到达的地方。这是最痛苦的地方，也是你需要格外小心的地方。否则，如果你的平台支持malloc 自省，你可以很容易地知道你得到一个指针的每个分配的大小，并确保你不会超出它们。
这只是触及了主题的表面。垃圾收集器非常复杂，即使是单线程的。当您将线程添加到组合中时，您将进入一个全新的伤害世界。
Apple 已经为 Objective-C 语言实现了这种保守的 GC，并将其命名为 libauto。他们已经开源了它，以及 Mac OS X 的大部分低级技术，你可以在这里找到源代码。
我只能在这里引用 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?
I guess you could allocate our memory then register it with the GC to tell it that it should be a managed resource. That would solve the interruptability problem. But then, be careful about what you send to third-party libraries, because if they keep a reference to it, your GC might not be able to detect it since they won't register their data structures with your GC.
And you likely won't be able to do that with roots on the stack.
根基本上都是静态和自动的对象指针。静态指针将链接到加载模块内。必须通过扫描堆栈帧来找到自动指针。当然，您不知道自动指针在堆栈帧中的什么位置。
一旦你有了根，你需要扫描对象并找到它们里面的所有指针。（这将包括指针数组。）为此，您需要识别类对象并以某种方式从中提取有关指针位置的信息。当然，在 C 语言中，许多对象不是虚拟的，并且其中没有类指针。
祝你好运！！
补充： 一种可以模糊地使您的任务成为可能的技术是“保守”垃圾收集。由于您打算拥有自己的分配器，因此您可以（以某种方式）跟踪分配大小和位置，因此您可以从存储中挑选任何指针大小的块并询问“这可能是指向我的一个对象的指针吗？” 当然，您永远无法确定，因为随机数据可能“看起来像”指向您的某个对象的指针，但您仍然可以通过这种机制扫描一大块存储空间（例如调用堆栈中的帧，或单个对象）并识别它可能解决的所有可能对象。
使用保守的收集器，您不能安全地进行对象重定位/压缩（在移动对象时修改指向对象的指针），因为您可能会意外修改看起来像对象指针但实际上对某些应用程序有意义的数据的“随机”数据。但是您可以识别未使用的对象并释放它们占用的空间以供重复使用。通过适当的设计，可以拥有非常有效的非压缩 GC。
（但是，如果您的 C 版本允许未对齐的指针扫描可能会非常慢，因为您必须尝试字节对齐的所有变化。）