C 语言的保守垃圾收集器

Yasin HINISLIOGLU

4.96/5 (14投票s)

2008 年 12 月 22 日

GPL3

11分钟阅读

106464

本文介绍了使用 C 语言的垃圾回收和内存管理

引言

在 C# 和 Java 等所有现代语言中，我们都可以受益于垃圾收集。为什么不实现我们自己的呢？在本文中，我将尝试解释如何为 C 语言实现垃圾收集器。

什么是垃圾收集？

在 C 语言中，动态内存管理操作通过 malloc() 和 free() 函数完成。当需要一块内存区域时，程序员调用 malloc() 函数并获得该区域的指针，当不再使用时，通过 free() 函数释放该区域。这确实是一项非常简单的任务，您使用 malloc() 创建内存区域，并使用 free() 释放它。如果程序员忘记调用 free() 函数，或者应用程序在 free() 函数执行之前崩溃怎么办？如果未调用 free() 函数，操作系统将无法使用该区域，并且仍然认为它正在使用中。大量未释放的内存区域可能会严重影响系统性能。

此时便诞生了对自动化垃圾收集机制的需求。自动化垃圾收集机制保证在程序运行时分配的所有内存都在结束时被释放。

存在许多垃圾收集算法，例如标记-清除、复制、分代、引用计数等。在本文中，我将尝试解释标记-清除算法。

那关于“保守”呢？

垃圾收集器（从现在开始简称为 GC）不应强制开发人员标记数据或强制使用特殊的 datatype 作为指针。GC 还应该作用于现有的源代码。在不进行编译的情况下处理现有代码将是一个更优雅的解决方案。GC 不应强制更改编译器。保守垃圾收集方法提供了满足上述任务的 GC 解决方案。

为了正常工作，GC 应该了解以下任务：

积极使用的变量
哪个变量是指针，哪个不是
已分配内存的信息

在 GC 分配内存时可以收集有关已分配内存的信息。

在 C 语言中，可以通过对应用程序的堆、栈和静态数据进行特殊扫描来收集有关正在使用的变量的信息。此解决方案高度依赖硬件。

同样在 C 语言中，我们在运行时没有类型信息。这意味着，在运行时阶段，区分指针和非指针不是一件容易的事。我们同样得不到编译器的任何帮助。一旦我们有了关于正在积极使用的变量的信息，我们就可以用特殊的指针识别算法扫描此列表来区分指针。此步骤存在一些缺点，但可以通过优雅的算法提供效率。

保守方法允许开发人员在他们已经编写的代码中使用 GC，而无需对其进行任何更改。开发人员调用 malloc() 函数，并在代码中再也不调用 free() 。其余的由 GC 这个智能助手处理。

停止世界（Stop the World）方法

我提到我们扫描应用程序的内存区域。我们还需要释放未使用的内存区域。这些操作需要额外的 CPU 周期。因此，当进行垃圾收集时，我们需要使用 CPU。此时，有两种主要的方法来使用 CPU：停止世界方法和并发方法。

并发方法在不同的线程上处理 GC 周期。对于这种方法，需要复杂的锁定机制。因此，它带来了高性能，这是大多数现代架构所期望的。有关更多信息，您可以搜索三色标记算法。

停止世界方法会停止程序执行，进行垃圾收集，然后恢复程序执行。这有一个非常大的缺点：它不允许应用程序在进行垃圾收集时使用 CPU。这可能会导致应用程序在进行垃圾收集时暂停。此外，即使硬件有多个 CPU，我们也无法使用多处理器，这可能会造成很大的性能差距。尽管存在许多缺点，但它确实非常容易实现，因此在本文中我们将使用这种方法。

标记-清除算法

标记-清除算法是第一个处理循环引用的算法。该算法是与一些其他技术结合使用的最常用的垃圾收集器之一。

标记-清除算法是一种追踪式收集器，因此它会遍历所有可用的指针以区分已使用和未使用的内存区域。它包含两个阶段。第一个阶段是标记阶段。在标记阶段，GC 会遍历所有可用变量，并使用指针识别算法查找指针。一旦确定了指针，标记阶段会找到指针的堆区域并将它们标记为已使用。在第二阶段，GC 会遍历堆并选择未标记的区域。未标记的区域是当前未使用的内存区域。这些区域将被回收。

如前所述，标记-清除可以处理循环引用。此外，它对变量没有额外的开销。

根集（Root Sets）

保守 GC 面临两个主要困难：第一个是确定在哪里找到根集，第二个是如何识别指针。

根集可以描述为在时间 (t) 正在使用的变量。在没有编译器帮助的情况下查找根集是一个高度依赖系统和硬件的问题。根集可以在栈、寄存器和应用程序的静态区域找到。为了实现我们的 GC，我们需要找到这些内存区域的基地址。

GC 应该发现栈的底部和顶部。栈是应用程序的主栈。如果我们仔细观察 CPU 架构，我们会发现有一个专用的栈，其中保存了执行点的地址、传递给函数的参数以及局部变量。每个架构的栈增长方向可能不同。当在某些架构中将新项压入栈时，栈向下增长；在某些架构中，它向上增长。GC 应该意识到这一点。栈的底部和顶部地址可以通过 32 位架构的 EBP、ESP 和 DS 寄存器值的组合找到。也有其他方法。

静态区域保存在 32 位 CPU 的数据段寄存器中，并存储在运行应用程序的堆中。静态区域是保存局部静态变量和全局变量的内存块。在实际应用程序中，我们可能有一些全局变量和局部静态变量保存指针。GC 应该意识到这些变量。

寄存器是硬件的 CPU 寄存器。这些内存区域高度依赖系统。GC 应该意识到在 GC 发生之前保存在寄存器中的根集。回收正在使用的内存区域可能会导致严重的错误。

指针识别

保守 GC 面临的第二个困难是识别指针。在 C 和 C++ 语言中，指针可以存储在整数变量中。在某些情况下，区分一个指针和一个 32 位整数值并不容易。由于 GC 没有编译器的帮助，它必须自己处理指针的识别。一般来说，保守垃圾收集器的方法是“GC 必须将它遇到的任何字（整数）视为潜在指针，除非它能证明不是”¹。

在此步骤中，GC 应该意识到指向指针的指针。在此项目中，我实现了深度优先搜索作为指针遍历算法。为了识别指针，GC 应该进行一些测试步骤来过滤掉非指针。

一个潜在指针是否指向原子指针。
一个潜在指针是否指向应用程序堆。
一个潜在指针是否指向根集。如果是，则执行指针遍历算法以查找它指向堆的哪个部分。
如果潜在指针指向堆，则遍历已分配块以查找它指向的确切块。

原子指针是由 GC 本身使用的指针。GC 应该区分这些指针和实际应用程序指针。GC 还应该允许开发人员识别自定义原子指针。原子指针在指针识别阶段被跳过，GC 不将其识别为指针。GC 永远不会触及这些指针的内存区域。

如果一个潜在指针通过了这些测试，它就被视为一个指针，并在标记阶段被标记为已使用。指针识别存在一些缺陷，例如虚假指针。虚假指针是持有堆地址的整数值。假设我们有一个整数 i ，它持有随机的 32 位值，并假设该值为 0x003932e8 。当发生 GC 时，我们还有一个指针 p ，它指向 0x003932e8 堆地址，大小以 MB 为单位。p 被设置为 NIL 并且不再使用。应用程序请求新的内存块，但由于内存不足，GC 无法分配空闲空间，并进入收集阶段。在收集阶段，p 应该被回收，所以它不再被使用，但是 i 实际上可能被识别为一个指针，而它并不是。这种情况可能很麻烦。Boehm 报告说，某些类别的数据，例如大型压缩位图，以过高的概率引入了虚假引用 [Boehm, 1993]。

实现

在进行了大量的理论信息之后，让我们来看看我们如何实现这种自动化内存管理器。

如前所述，我们将设计的 GC 将高度依赖于系统和硬件。我们将使用 IA32 架构和 Windows 操作系统。

GC 首先要做的是找到根集。可以通过检索最后一个创建的变量的地址来找到栈顶。在 Windows 环境中，最后一个创建的变量的地址可用于使用 VirtualQuery 函数查询活动内存块。该函数会告知相关内存区域的基地址和其他属性²。在对栈顶调用 VirtualQuery 函数后，我们可以检索完整的栈根集。这个根集为我们提供了当前正在使用的变量。定义 static 根集需要再次调用 VirtualQuery 函数。这次我们使用创建的 static 局部变量来查询内存区域。寄存器根可以通过使用 asm 指令检索。

当开发人员调用 GC 的 malloc 函数时，我们的代码应该向该内存块添加额外的头部信息。该块被链接到双向链表。使用此列表，我们可以存储和查询哪些内存区域是由 GC 分配的。在我的实现中，分配不调用收集步骤（当系统内存不足时应该这样做），它只使用低级 malloc 创建新的内存区域并返回该块的地址。在未来的版本中，我的 gc_malloc 实现应该以更智能、更优雅的方式工作。

在我们的实现中，开发人员应该能够调用 GC 的 collect 函数。不建议调用此函数，但为了灵活性，我们可以允许开发人员调用我们的 collect 函数。Collect 函数应该调用以下步骤。首先，它应该确定根集，然后依次调用标记和清除阶段。

在标记阶段，GC 应该遍历整个根集。代码应该为根集中的每个可能的指针调用指针识别步骤。一旦可能的指针通过了识别步骤，代码就应该将其标记为已使用（在我当前的实现中，我有两个列表。第一个列表保存已使用的区域，第二个列表保存空闲区域。当我将一个指针标记为已使用时，我将其从已使用区域中移除并链接到一个空闲区域，这减少了清除阶段的 CPU 使用率）。

在清除阶段，GC 应该遍历整个堆。在此步骤中，只有已标记的区域不会被回收，其余的将被回收。（在我当前的实现中，当我不再需要时，我就会释放内存区域。这可能会导致性能损失。在此步骤中可以使用更高级的方法。）

GC 最后要做的是在应用程序退出时回收整个堆。我们可以使用标准 C 的 atexit() 函数。在该函数中，我们将遍历整个堆以回收所有使用的内存。

源代码和最后的几句话

本项目是一个开源项目。请随时加入本项目。如果您希望参与此项目，请告诉我。项目的源代码库可以在此处找到。

请注意，该项目正在积极开发中。此外，当前版本支持一个完全工作的 GC 机制，并且在性能方面存在许多不足。