我试图在C中实现一个简单的标记和清除垃圾收集器。算法的第一步是找到根。所以我的问题是如何在C程序中找到根？
在使用malloc的程序中，我将使用自定义分配器。这个自定义分配器是所有将从C程序调用的分配器，并且可能是一个自定义init()。
垃圾收集器如何知道程序中所有的指针(根)是什么？此外，给定一个自定义类型的指针，它是如何获取其中的所有指针的？
例如，如果有一个指针p指向一个类列表，而该类列表中有另一个指针。比如q。垃圾收集器如何知道它，以便对其进行标记？
更新：如果我在初始化GC时将所有指针名称和类型发送给GC，怎么样？类似地，也可以发送不同类型的结构，以便GC可以遍历树。这是一个理智的想法吗？还是我快疯了？
首先，C中的垃圾收集器没有广泛的编译器和操作系统支持，的是保守的，因为您无法区分合法指针和恰好具有类似指针的值的整数。即使是保守的垃圾收集器也很难实现。就像，真的很难。通常，为了获得可接受的内容，您需要约束语言：例如，如果指针被隐藏或混淆，则可能无法正确收集内存。如果您分配了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，并且仍然在主函数中进行实际工作。)
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 to do集合，就需要查询当前堆栈指针以查找中断的线程。为此，您将需要特定于设计和/或特定于平台的调用(尽管如果您在同一个线程上执行一些东西，那么上面的技术仍然有效)。
真正的寻根行动现在就开始了。好消息：大多数ABI都要求堆栈帧在大于指针大小的边界上对齐，这意味着如果你相信每个指针都在对齐的内存上，你可以将整个堆栈视为intptr_t*，并检查其中的任何模式是否与任何托管指针相似。
显然，还有其他根源。全局变量(理论上)可以是根，结构内部的域也可以是根。寄存器也可以具有指向对象的指针。你需要单独考虑可能是根的全局变量(或者完全禁止，在我看来这不是一个坏主意)，因为自动发现这些变量很难(至少，我不知道如何在任何平台上做到这一点)。
这些根可能会导致堆上的引用，如果你不小心，这些引用可能会出错。
由于并非所有平台都提供malloc内省(据我所知)，因此您需要实现扫描内存的概念，即GC所知道的内存。它至少需要知道每个这样的分配的地址和大小。当您获得对其中一个的引用时，您只需扫描它们以查找指针，就像对堆栈所做的那样。(这意味着你应该注意你的指针是对齐的。如果你让编译器完成它的工作，通常情况下就是这样，但当你使用第三方API时，你仍然需要小心)。
这也意味着你不能把对可收集内存的引用放在GC无法访问的地方。这是最伤人的地方，你需要格外小心。否则，如果您的平台支持malloc内省，您可以很容易地告诉您获得指针的每个分配的大小，并确保不会超出它们。
这只是触及了主题的表面。垃圾收集器极其复杂，即使是单线程的。当你在混合中添加线程时，你就进入了一个全新的伤害世界。
苹果为Objective-C语言实现了这样一个保守的GC，并将其命名为libauto。他们已经开源了它，以及Mac OS X的大部分底层技术，你可以在这里找到源代码。
我只能在这里引用Hot Licks的话：祝你好运！
好吧，在我进一步讨论之前，我忘记了一件非常重要的事情：编译器优化可以破坏GC。如果你的编译器不知道你的GC，它很可能永远不会把某些根放在堆栈上(只在寄存器中处理它们)，你会错过它们。如果可以检查寄存器，这对单线程程序来说并不是太大问题，但对多线程程序来说，这又是一个巨大的麻烦。
还要非常小心分配的可中断性：您必须确保GC在返回新指针时不会启动，因为它可以在将指针分配给根之前收集指针，并且当程序恢复时，它会将新的悬挂指针分配给程序。
这里有一个解决编辑问题的更新：
更新：如果我在我初始化了吗？类似地，不同类型的结构也可以是发送，以便GC可以遍历树。这是一个理智的想法吗我只是疯了？
我想你可以分配我们的内存，然后向GC注册，告诉它应该是一个托管资源。这将解决可中断性问题。但是，要小心发送给第三方库的内容，因为如果他们保留对它的引用，GC可能无法检测到它，因为他们不会向GC注册数据结构。
而且你很可能无法用堆栈上的根来做到这一点。
根基本上都是静态和自动对象指针。静态指针将链接到加载模块内部。必须通过扫描堆栈帧来找到自动指针。当然，您不知道自动指针在堆栈帧中的何处。
一旦你有了根，你需要扫描对象并找到它们里面的所有指针。(这将包括指针数组。)为此，您需要识别类对象，并以某种方式从中提取有关指针位置的信息。当然，在C中，许多对象不是虚拟的，并且其中没有类指针。
祝你好运！！
添加：一种可能模糊地使您的任务成为可能的技术是"保守"垃圾收集。既然你打算拥有自己的分配器，你可以(以某种方式)跟踪分配大小和位置，这样你就可以从存储中挑选任何指针大小的区块，并问"这可能是指向我的一个对象的指针吗？"，扫描存储块(如调用堆栈中的帧或单个对象)，并识别可能寻址的所有可能对象。
使用保守的收集器，您无法安全地进行对象重新定位/压缩(在移动对象时修改指向对象的指针)，因为您可能会意外地修改"随机"数据，这些数据看起来像对象指针，但实际上对某些应用程序来说是有意义的数据。但是，您可以识别未使用的对象，并释放它们占用的空间以供重复使用。通过适当的设计，可以获得非常有效的非压实GC。
(然而，如果你的C版本允许未对齐的指针，扫描可能会非常慢，因为你必须尝试字节对齐的每一种变化。)