巴德工作组

Boehm-Demers-Weiser 垃圾收集器

这是 C 和 C++ 保守垃圾收集器的版本 8.3.0（下一个版本开发）。

许可证：麻省理工学院风格

下载

您可能会在下载页面或 BDWGC 站点上找到更新/稳定的版本。

此外，开发存储库中还提供了最新的错误修复和新功能。

概述

这是一个通用的垃圾收集存储分配器。 使用的算法描述于：

• Boehm, H. 和 M. Weiser，“不合作环境中的垃圾收集”，软件实践与经验，1988 年 9 月，第 807-820 页。

• Boehm, H.、A. Demers 和 S. Shenker，“Mostly Parallel Garbage Collection”，ACM SIGPLAN '91 编程语言设计和实现会议记录，SIGPLAN 通知 26, 6（1991 年 6 月），第 157 页164.

• Boehm, H.，“节省空间的保守垃圾收集”，ACM SIGPLAN '91 编程语言设计和实现会议记录，SIGPLAN 通知 28, 6（1993 年 6 月），第 197-206 页。

• Boehm H.，“减少垃圾收集器缓存未命中”，2000 年内存管理国际研讨会论文集。

收集器和优化编译器之间可能的交互在中讨论

• Boehm, H. 和 D. Chase，“GC 安全 C 编译的建议”，《C 语言翻译杂志》4, 2（1992 年 12 月）。

• Boehm H.，“简单 GC 安全编译”，ACM SIGPLAN '96 编程语言设计和实现会议论文集。

与第二个参考文献中描述的收集器不同，该收集器在整个收集期间（默认）或在分配期间增量地停止变元的情况下运行。 （后者在较少的机器上受支持。）在最常见的平台上，它可以在有或没有线程支持的情况下构建。 在某些平台上，它可以利用多处理器来加速垃圾收集。

该收藏家背后的许多想法此前已被其他人探索过。 值得注意的是，Xerox PARC 在 20 世纪 80 年代初开发的一些运行时系统保守地扫描线程堆栈以定位可能的指针（参见 Paul Rovner，“将垃圾收集和运行时类型添加到强类型静态检查并发语言”施乐帕洛阿尔托研究中心 CSL 84-7)。 Doug McIlroy 编写了一个更简单的完全保守的收集器，它是版本 8 UNIX (tm) 的一部分，但似乎并未得到广泛使用。

包括使用收集器作为泄漏检测器的基本工具，以及使用收集器的相当复杂的字符串包“线”。 （参见 README.cords 和 H.-J. Boehm、R. Atkinson 和 M. Plass，“绳索：绳索的替代品”，软件实践和经验 25, 12（1995 年 12 月），第 1315-1330 页。与 Xerox Cedar 中的“rope”包非常相似，或者 SGI STL 或 g++ 发行版中的“rope”包。）

更多收集器文档可以在概述中找到。

GitHub 已知客户端页面上列出了收集器的一些已知用途。

一般说明

这是一个垃圾收集存储分配器，旨在用作 C 的 malloc 的插件替代品。

由于收集器不需要标记指针，因此它不会尝试确保回收所有不可访问的存储。 然而，根据我们的经验，它在回收未使用的内存方面通常比大多数使用显式释放的 C 程序更成功。 与手动引入的泄漏不同，未回收的内存量通常保持有限。

在下文中，“对象”被定义为由下述例程分配的存储器区域。

任何不打算收集的对象必须从其他此类可访问对象或从寄存器、堆栈、数据或静态分配的 bss 段指向。 堆栈或寄存器中的指针可以指向对象内的任何位置。如果收集器是使用定义的ALL_INTERIOR_POINTERS进行编译的，或者以其他方式设置了GC_all_interior_pointers （现在是默认值），则堆指针也是如此。

不使用ALL_INTERIOR_POINTERS进行编译可能需要从堆到对象开头的指针，从而减少垃圾对象的意外保留。 但对于大多数占用一小部分可能地址空间的程序来说，这似乎不再是一个重要问题。

有许多修改指针识别算法的例程。即使未定义ALL_INTERIOR_POINTERS ， GC_register_displacement也允许识别某些内部指针。 GC_malloc_ignore_off_page允许忽略一些指向大对象中间的指针，大大降低了意外保留大对象的概率。 对于大多数目的，如果您从非常大的对象的分配中收到收集器警告，似乎最好使用ALL_INTERIOR_POINTERS进行编译并使用GC_malloc_ignore_off_page 。 详细信息请参见此处。

警告：垃圾收集器看不到由标准（系统） malloc分配的内存内的指针。 因此，仅从这样的区域指向的对象可能会被过早地释放。 因此，建议标准malloc仅用于保证不包含指向垃圾可收集内存的指针的内存区域，例如 I/O 缓冲区。 C 语言自动、静态或寄存器变量中的指针可以正确识别。 （请注意， GC_malloc_uncollectable语义与标准 malloc 类似，但分配由收集器跟踪的对象。）

警告：收集器并不总是知道如何在与动态库关联的数据区域中查找指针。 如果您知道如何在操作系统上查找这些数据区域（请参阅GC_add_roots ），那么这很容易解决。 默认情况下，包含并使用在 SunOS、IRIX 5.X 和 6.X、HP/UX、Alpha OSF/1、Linux 和 Win32 下执行此操作的代码。 （有关 Windows 详细信息，请参阅 README.win32 和 README.win64。）在其他系统上，收集器可能不会考虑来自动态库数据区域的指针。 如果您正在编写一个依赖于收集器扫描动态库数据区域的程序，那么至少包含一次对GC_is_visible调用以确保这些区域对收集器可见可能是一个好主意。

请注意，垃圾收集器不需要被告知共享只读数据。 但是，如果共享库机制可能引入可能包含指针的不连续数据区域，则确实需要通知收集器。

大多数信号的信号处理可能会在收集期间以及分配过程的不间断部分期间被推迟。与标准 ANSI C malloc 一样，默认情况下，当另一个 malloc 调用可能正在进行时，从信号处理程序调用 malloc（和其他 GC 例程）是不安全的。

分配器/收集器还可以配置为线程安全操作。 （也可以实现完全的信号安全，但代价是每个 malloc 需要两次系统调用，这通常是不可接受的。）

警告：收集器不保证扫描线程本地存储（例如使用pthread_getspecific访问的类型）。 不过，收集器确实会扫描线程堆栈，因此通常最好的解决方案是确保存储在线程本地存储中的任何指针在其生命周期内也存储在线程的堆栈上。 （这可以说是一个长期存在的错误，但尚未修复。）

搭建和安装

构建收集器的方法有多种：

• CMake（这是推荐的方式）

• GNU autoconf/automake

• 之字形（实验）

• MS nmake（直接）

• 直接生成文件

• 手动C编译

CMake

构建 libgc（以及 libcord）并使用 cmake 运行测试的最简单方法：

 mkdir outcd 输出
cmake -Dbuild_tests=ON ..
cmake --build .ctest

这是构建库的最跨平台的方式。有关详细信息，请参阅 README.cmake。

GNU Autoconf/Automake

请注意，收集器源存储库不包含configure和类似的自动生成文件，因此从源存储库基于 autoconf 构建收集器的完整过程可能如下所示：

 ./autogen.sh
./配置
进行检查

GNU 风格的构建过程了解常用的目标和选项。 make install安装 libgc 和 libcord。 尝试./configure --help查看所有配置选项。 目前不可能以这种方式执行构建选项的所有组合。

有关详细信息，请参阅 README.autoconf。

之字形

使用 zig 构建和测试收集器的最简单形式是直接的：

 Zig 构建测试

可以通过使用变量来配置构建，例如zig build -Denable_redirect_malloc -Denable_threads=false 。 Zig 提供了出色的交叉编译功能，它的配置如下：

 zig build -Dtarget=riscv64-linux-musl

目前需要 zig 0.12 的 nightly 版本，可以从 https://ziglang.org/download/ 下载

MS nmake

在 Windows 上，假设已安装并适当配置了 Microsoft 构建工具，则可以直接使用nmake构建库并运行测试，例如通过键入nmake -f NT_MAKEFILE check 。 但是，推荐的方法是使用如上所述的 cmake。

有关详细信息，请参阅 README.win32。

直接生成文件

对于旧式（经典）基于 makefile 的构建过程，输入make -f Makefile.direct check将自动构建 libgc、libcord，然后运行一些测试，例如gctest 。 该测试是对收集器功能的比较肤浅的测试。 失败通过核心转储或收集器损坏的消息来指示。 gctest在合理的 2023 年老式 64 位桌面上运行可能需要十几秒。它最多可能使用约 30 MB 的内存。

Makefile.direct 将生成一个库 libgc.a，您应该链接到该库。

手动C编译

最后，在大多数目标上，可以使用单个编译器调用直接构建和测试收集器，如下所示（示例缺乏多线程支持）：

 cc -I include -o gctest测试/gctest.c extra/gc.c && ./gctest

例如，这对于调试目的可能很方便。

可配置的宏

通过定义 README.macros 文件中列出的宏，可以在构建过程中更精确地配置库。

默认情况下，该库是在启用线程支持（即线程安全操作）的情况下构建的，除非通过以下方式明确禁用：

• -Denable_threads=false传递给cmake或zig build选项

• --disable-threads选项传递给./configure

收集器在默认配置下静默运行。如果出现问题，通常可以通过定义GC_PRINT_STATS或GC_PRINT_VERBOSE_STATS环境变量来更改。 这将为每个集合生成几行描述性输出。 （给定的统计数据表现出一些特殊性。由于各种原因，事情似乎没有加起来，最明显的是碎片损失。这些对于设计的程序gctest可能比您的应用程序更重要。）

原子操作

如果编译器支持原子内在函数，则现在可以选择使用（克隆） libatomic_ops 。 大多数现代编译器都是这样做的。 值得注意的例外是 MS 编译器（从 Visual Studio 2022 开始）。

如果需要，大多数操作系统发行版都有libatomic_ops包；或者，您可以从 https://github.com/ivmai/libatomic_ops 空间下载或克隆它。

可移植性

目前，收集器设计为在使用平面 32 位或 64 位地址空间的机器上运行，基本上无需修改。其中包括绝大多数工作站和 x86（i386 或更高版本）PC。

在少数情况下（例如，OS/2、Win32）会提供单独的 makefile；它们有一个单独的特定于主机的 docs/platforms/README.* 文件。

动态库仅在 SunOS/Solaris（甚至在最新的 Sun 3 发行版上该支持不起作用）、Linux、FreeBSD、NetBSD、IRIX、HP/UX、Win32（不是 win32s）和 DEC 上的 OSF/1 下得到完全支持AXP 机器以及 dyn_load.c 顶部附近列出的其他一些机器。 在其他计算机上，我们建议您执行以下操作之一：

1. 添加动态库支持（并将代码发送给我们）。

2. 使用库的静态版本。

3. 安排动态库使用标准 malloc。如果库存储指向垃圾收集对象的指针，这仍然很危险。但几乎所有标准接口都禁止这样做，因为它们正确地处理指向堆栈分配对象的指针。 （ strtok是一个例外。不要使用它。）

在所有情况下，我们都假设指针对齐与标准 C 编译器强制执行的一致。 如果您使用非标准编译器，您可能必须调整include/private/gc_priv.h中定义的对齐参数。 请注意，这也可能是打包记录/结构的问题，如果它们强制减少指针的对齐。

到非字节寻址或不使用 32 位或 64 位地址的机器的端口将需要付出很大的努力。 移植到普通的 MSDOS 或 win16 是很困难的。

对于尚未提及的机器或非标准编译器，此处提供了一些移植建议。

分配器的 C 接口

以下例程旨在由用户直接调用。请注意，通常只需要GC_malloc 。如果收集器必须从非标准位置（例如，从收集器尚未理解的机器上的动态库数据区域）进行跟踪，则可能需要GC_clear_roots和GC_add_roots调用。在某些机器上，可能需要将GC_stackbottom设置为堆栈基数（底部）的良好近似值。

客户端代码可能包括gc.h ，它定义了以下所有内容以及许多其他内容。

1. GC_malloc(bytes) - 分配给定大小的对象。 与 malloc 不同，对象在返回给用户之前会被清除。当GC_malloc确定合适时，它将调用垃圾收集器。如果无法从操作系统获取足够的空间，GC_malloc 可能会返回 0。 这是空间不足最可能造成的后果。 其他可能的后果是函数调用将由于缺乏堆栈空间而失败，或者收集器将因无法维护其内部数据结构而以其他方式失败，或者关键的系统进程将失败并导致机器瘫痪。 大多数这些可能性与 malloc 实现无关。

2. GC_malloc_atomic(bytes) - 分配给定大小的对象，保证不包含任何指针。 不保证返回的对象被清除。 （始终可以替换为GC_malloc ，但会导致更快的收集时间。如果使用GC_malloc_atomic分配大型字符数组等，收集器可能会比静态分配更快地运行。）

3. GC_realloc(object, new_bytes) - 将对象的大小更改为给定大小。 返回指向新对象的指针，该指针可能与旧对象的指针相同，也可能不同。 当且仅当旧对象是原子的时，新对象才被视为原子的。 如果新对象是复合对象并且大于原始对象，则新添加的字节将被清除。这很有可能会分配一个新的对象。

4. GC_free(object) - 显式释放GC_malloc或GC_malloc_atomic或朋友返回的对象。 不是必需的，但如果性能至关重要，可以用来最小化集合。 对于非常小的对象（<= 8 字节）可能会造成性能损失。

5. GC_expand_hp(bytes) - 显式增加堆大小。 （如果垃圾收集未能回收足够的内存，这通常会自动完成。显式调用GC_expand_hp可能会阻止程序启动时不必要的频繁收集。）

6. GC_malloc_ignore_off_page(bytes) - 与GC_malloc相同，但客户端承诺在对象处于活动状态时保留指向对象的第一个 GC 堆块（512 .. 4096 字节或什至更多，取决于配置）内某处的指针。 （该指针通常应声明为 volatile，以防止编译器优化的干扰。）这是分配可能大于 100 KB 左右的任何内容的推荐方法。 （ GC_malloc可能会导致回收此类对象失败。）

7. GC_set_warn_proc(proc) - 可用于重定向来自收集器的警告。 此类警告应该很少见，并且在代码开发过程中不应被忽略。

8. GC_enable_incremental() - 启用分代和增量收集。 对于提供对页面脏信息的访问的机器上的大堆很有用。 一些脏位实现可能会干扰调试（通过捕获地址错误）并对系统调用的堆参数施加限制（因为系统调用内的写入错误可能无法很好地处理）。

9. GC_register_finalizer(object, proc, data, 0, 0)和朋友 - 允许注册终结代码。 在对象变得无法访问后，将调用用户提供的终结代码 ( (*proc)(object, data) ）。对于更复杂的用途以及最终确定顺序问题，请参阅gc.h 。

全局变量GC_free_space_divisor可以从默认值 3 向上调整，以使用更少的空间和更多的收集时间，或者向下调整以获得相反的效果。 将其设置为 1 几乎会禁用集合并导致所有分配只会增加堆。

变量GC_non_gc_bytes通常为 0，可以更改以反映上述例程分配的内存量，这些内存不应被视为收集的候选者。 当然，不小心使用可能会导致内存消耗过多。

通过include/private/gc_priv.h顶部附近定义的参数可以进行一些额外的调整。

如果仅打算使用GC_malloc ，则可能适合定义：

#define malloc(n) GC_malloc(n)
#define calloc(m,n) GC_malloc((m)*(n))

对于小块非常分配密集的代码， gc_inline.h包含一些可以用来代替GC_malloc和朋友的分配宏。

垃圾收集器中的所有外部可见名称均以GC_开头。为了避免名称冲突，客户端代码应避免使用此前缀，访问垃圾收集器例程时除外。

有明确类型信息分配的规定。这很少是必要的。 详细信息可以在gc_typed.h中找到。

分配器的 C++ 接口

收集器的 Ellis-Hull C++ 接口包含在收集器发行版中。 如果您打算使用它，请键入./configure --enable-cplusplus && make （或cmake -Denable_cplusplus=ON . && cmake --build . ，或make -f Makefile.direct c++具体取决于您使用的构建系统）。这将创建 libgccpp.a 和 libgctba.a 文件，或其等效的共享库（libgccpp.so 和 libgctba.so）。 您应该链接第一个 (gccpp) 或第二个 (gctba)，但不能同时链接两者。 有关接口的定义，请参阅gc_cpp.h和此处。该接口尝试在不更改编译器的情况下近似 Ellis-Detlefs C++ 垃圾收集建议。

很多时候，还需要使用gc_allocator.h和其中声明的分配器来构造 STL 数据结构。 否则，STL 数据结构的子对象将使用系统分配器进行分配，并且它们引用的对象可能会被过早收集。

用作检漏仪

收集器可用于追踪旨在使用 malloc/free 运行的 C 程序中的泄漏（例如，具有极端实时性或可移植性限制的代码）。 为此，请在 Makefile 中定义FIND_LEAK 。每当发现未显式释放的不可访问对象时，这将导致收集器打印人类可读的对象描述。此类对象也会被自动回收。

如果所有对象都分配有GC_DEBUG_MALLOC （请参阅下一节），那么默认情况下，人类可读的对象描述将至少包含源文件和分配泄漏对象的行号。有时这可能就足够了。 （在一些机器上，它还会报告一个神秘的堆栈跟踪。如果这不是符号性的，有时可以通过使用tools/callprocs.sh foo调用程序“foo”来调用符号堆栈跟踪。它是一个短 shell调用 adb 将程序计数器值扩展为符号地址的脚本主要由 Scott Schwartz 提供。）

请注意，下一节中描述的调试工具有时在泄漏查找模式中可能稍微不太有效，因为在后者中GC_debug_free实际上会导致对象的重用。 （否则该对象将被简单地标记为无效。）此外，请注意，大多数 GC 测试并非设计为在FIND_LEAK模式下有意义地运行。

调试设施

例程GC_debug_malloc 、 GC_debug_malloc_atomic 、 GC_debug_realloc和GC_debug_free为收集器提供了备用接口，它为内存覆盖错误等提供了一些帮助。以这种方式分配的对象带有附加信息注释。 其中一些信息会在垃圾收集期间进行检查，并将检测到的不一致情况报告给 stderr。

如果显式释放该对象，或者在对象处于活动状态时调用收集器，则应捕获超出已分配对象末尾的写入的简单情况。 对象的第一次释放将清除与该对象关联的调试信息，因此意外地重复调用GC_debug_free将报告对象的释放而没有调试信息。 除了返回NULL之外，内存不足错误还会报告给 stderr。

首次调用此函数时会启用垃圾收集期间的GC_debug_malloc检查。 这将导致收集过程中速度减慢。 如果需要频繁的堆检查，可以通过显式调用GC_gcollect来实现，例如从调试器中。

GC_debug_malloc分配的对象不应传递给GC_realloc或GC_free ，反之亦然。 但是，如果两个池保持不同，则可以仅使用GC_debug_malloc分配某些对象，并将GC_malloc用于其他对象。 在这种情况下， GC_malloc分配的对象被误认为已被覆盖的可能性非常低。 这种情况发生的概率最多为 2**32 分之一。 如果从未调用GC_debug_malloc则此概率为零。

GC_debug_malloc 、 GC_debug_malloc_atomic和GC_debug_realloc采用两个额外的尾随参数：一个字符串和一个整数。 这些不由分配器解释。 它们存储在对象中（不复制字符串）。 如果检测到涉及对象的错误，则会打印它们。

还提供了宏GC_MALLOC 、 GC_MALLOC_ATOMIC 、 GC_REALLOC 、 GC_FREE 、 GC_REGISTER_FINALIZER等。 这些需要与相应的（非调试）例程相同的参数。 如果gc.h包含在定义的GC_DEBUG中，它们将调用这些函数的调试版本，并在适当的情况下将当前文件名和行号作为两个额外参数传递。 如果包含gc.h时未定义GC_DEBUG ，则所有这些宏将被定义为其非调试等效项。 ( GC_REGISTER_FINALIZER是必要的，因为指向带有调试信息的对象的指针实际上是指向从对象开始位移 16 个字节的指针，并且在调用终结例程时​​需要进行一些转换。有关标头中存储的详细信息，请参阅定义dbg_mlc.c 文件中的 oh 类型。）

增量/分代收集

收集器通常会在垃圾收集标记阶段期间中断客户端代码。 如果对于具有大堆的程序需要交互式响应，这可能是不可接受的。 收集器还可以在“分代”模式下运行，在该模式下，它通常尝试仅收集自上次垃圾收集以来分配的对象。此外，在此模式下，垃圾收集主要以增量方式运行，响应大量GC_malloc请求中的每一个请求，执行少量工作。

该模式通过调用GC_enable_incremental来启用。

仅当收集器有某种方式来判断哪些对象或页面最近被修改时，增量收集和分代收集才能有效减少暂停时间。 收集器使用两个信息源：

1. VM系统提供的信息。 这可以以多种形式之一来提供。 在 Solaris 2.X 下（也可能在其他类似系统下）可以从 /proc 文件系统读取有关脏页的信息。在其他系统（例如SunOS4.X）下，可以对堆进行写保护，并捕获由此产生的错误。在这些系统上，我们要求写入堆的系统调用（读取除外）由客户端代码专门处理。详细信息请参见os_dep.c 。

2. 程序员提供的信息。 如果库已正确编译，则在调用GC_end_stubborn_change后，该对象被视为脏对象。它通常不值得用于短暂的对象。请注意，由于缺少GC_end_stubborn_change或GC_reachable_here调用而导致的错误可能很少出现且难以追踪。

虫子

任何没有可识别指针的内存都将被回收。 对列表中的前向和后向链接进行异或并不能解决问题。

由于巧妙的优化，一些 C 优化器可能会丢失最后一个未加掩饰的指向内存对象的指针。 这在实践中几乎从未被观察到。

这不是实时收集器。 在标准配置中，收集所需的时间百分比在堆大小之间应保持不变。 但对于较大的堆，收集暂停将会增加。如果启用并行标记，它们将随着处理器数量的增加而减少。

（在 2007 年老式机器上，GC 时间可能约为每 MB 需要扫描和处理的可访问内存 5 毫秒。您的情况可能会有所不同。）增量/分代收集设施在某些情况下可能会有所帮助。

反馈、贡献、问题和通知

请将错误报告和新功能想法提交到 GitHub 问题。 提交前请检查是否尚未被其他人完成。

如果您想做出贡献，请向 GitHub 提交拉取请求。请在提交前以 clang-format 处理修改后的文件。

如果您需要帮助，请使用 Stack Overflow。较旧的技术讨论可在bdwgc邮件​​列表存档中找到 - 它可以作为压缩文件下载或在 Narkive 上浏览。

要获取新版本公告，请订阅 RSS 源。 （要通过电子邮件接收通知，可以设置第 3 方免费服务，例如 IFTTT RSS Feed。）要获得所有问题的通知，请在 GitHub 上观看该项目。

版权和保证、贡献者

我们的目的是让 bdwgc (libgc) 在免费和专有软件中都能轻松使用。 因此，我们希望动态或静态链接到客户端应用程序的 Boehm-Demers-Weiser 保守垃圾收集器代码由自己的许可证覆盖，这在精神上类似于 MIT 风格的许可证。

LICENSE 文件中提供了确切的许可信息。

所有贡献者都列在作者文件中。