gc
1.0.0
gc是保守的、线程本地的、标记和清除垃圾收集器的实现。该实现为标准 POSIX malloc() 、 calloc() 、 realloc()和free()调用提供了功能齐全的替代。
gc的重点是提供概念上干净的标记和清除 GC 实现，而无需深入研究特定于体系结构的优化（例如，请参阅 Boehm GC 来了解此类任务）。它应该特别适合学习目的，并且对各种优化开放（欢迎 PR！）。
gc的最初动机是我希望用 C 语言完全从头开始编写自己的 LISP - 这需要垃圾收集。
如果没有阅读其他人的工作的能力，这项工作是不可能完成的，尤其是 Boehm GC、orangeduck 的 tgc（也遵循小型和简单的理想）和垃圾收集手册。
gc实现中的基本概念和设计决策。 $ git clone [email protected]:mkirchner/gc.git
$ cd gc
使用clang编译器进行编译：
$ make test
要使用 GNU 编译器集合 (GCC)：
$ make test CC=gcc
测试应该成功完成。创建当前覆盖率报告：
$ make coverage
...
#include "gc.h"
...
void some_fun () {
...
int * my_array = gc_calloc ( & gc , 1024 , sizeof ( int ));
for ( size_t i = 0 ; i < 1024 ; ++ i ) {
my_array [ i ] = 42 ;
}
...
// look ma, no free!
}
int main ( int argc , char * argv []) {
gc_start ( & gc , & argc );
...
some_fun ();
...
gc_stop ( & gc );
return 0 ;
}这描述了核心 API，请参阅gc.h了解更多详细信息和低级 API。
为了初始化并开始垃圾收集，请使用gc_start()函数并传递堆栈底部地址：
void gc_start ( GarbageCollector * gc , void * bos );栈底参数bos需要指向堆栈分配的变量，并标记根查找（扫描）开始的堆栈低端。
垃圾收集可以停止、暂停和恢复
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );并且可以通过以下方式触发手动垃圾收集
size_t gc_run ( GarbageCollector * gc );gc支持malloc() 、 calloc()和realloc()风格的内存分配。各自的函数签名模仿 POSIX 函数（除了我们需要将垃圾收集器作为第一个参数传递）：
void * gc_malloc ( GarbageCollector * gc , size_t size );
void * gc_calloc ( GarbageCollector * gc , size_t count , size_t size );
void * gc_realloc ( GarbageCollector * gc , void * ptr , size_t size );可以通过扩展接口将指针传递给析构函数：
void * dtor ( void * obj ) {
// do some cleanup work
obj -> parent -> deregister ();
obj -> db -> disconnect ()
...
// no need to free obj
}
...
SomeObject * obj = gc_malloc_ext ( gc , sizeof ( SomeObject ), dtor );
... gc支持静态分配，仅当 GC 通过gc_stop()关闭时才会进行垃圾收集。只需使用适当的辅助函数：
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * ));静态分配需要一个指向终结函数的指针；如果不需要终结，只需设置为NULL 。
请注意， gc目前在收集静态变量时不保证特定的顺序，如果需要以特定顺序释放静态变量，用户应在调用gc_stop()之前按所需顺序对它们调用gc_free() ，请参见下文。
还可以使用以下命令触发显式内存释放
void gc_free ( GarbageCollector * gc , void * ptr );调用gc_free()保证 (a) 在适用的情况下终结/销毁ptr指向的对象，以及 (b) 释放ptr指向的内存，无论当前的垃圾回收调度如何，并且如果 GC 已执行，也将起作用。使用上面的gc_pause()暂停。
gc还提供了一个strdup()实现，它返回垃圾收集的副本：
char * gc_strdup ( GarbageCollector * gc , const char * s );垃圾收集背后的基本思想是自动化内存分配/释放周期。这是通过跟踪所有已分配的内存并定期触发仍已分配但无法访问的内存的释放来实现的。
许多高级垃圾收集器还实现了自己的内存分配方法（即替换malloc() ）。这通常使他们能够以更节省空间的方式布局内存或更快地访问，但代价是特定于架构的实现和增加的复杂性。 gc通过依靠 POSIX *alloc()实现并将内存管理和垃圾收集元数据分开来回避这些问题。这使得gc更容易理解，但当然，与更优化的方法相比，空间和时间效率也较低。
gc内部的核心数据结构是一个哈希映射，它将分配的内存的地址映射到该内存的垃圾收集元数据：
哈希映射中的项目是分配，用Allocation struct建模：
typedef struct Allocation {
void * ptr ; // mem pointer
size_t size ; // allocated size in bytes
char tag ; // the tag for mark-and-sweep
void ( * dtor )( void * ); // destructor
struct Allocation * next ; // separate chaining
} Allocation ;每个Allocation实例都包含一个指向已分配内存的指针、该位置已分配内存的大小、一个用于标记和清除的标记（见下文）、一个指向析构函数的可选指针以及一个指向下一个Allocation实例的指针（对于单独的链接，请参见下文）。
分配收集在AllocationMap中
typedef struct AllocationMap {
size_t capacity ;
size_t min_capacity ;
double downsize_factor ;
double upsize_factor ;
double sweep_factor ;
size_t sweep_limit ;
size_t size ;
Allocation * * allocs ;
} AllocationMap ;它与gc.c内的一组static函数一起，为公共 API 的实现提供哈希映射语义。
AllocationMap是GarbageCollector结构中的中心数据结构，它是公共 API 的一部分：
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ;基本数据结构就位后，任何gc_*alloc()内存分配请求都是一个两步过程：首先，通过系统（即标准malloc() ）功能分配内存，其次，将相关元数据添加或更新到哈希映射。
对于gc_free() ，使用指针在哈希映射中定位元数据，确定释放是否需要析构函数调用，如果需要则调用，释放托管内存并从哈希映射中删除元数据条目。
这些数据结构和相关接口支持管理构建垃圾收集器所需的元数据。
gc在两种情况下触发收集： (a) 当对系统分配的任何调用失败时（希望释放足够的内存来满足当前请求）； (b)当散列映射中的条目数量超过动态调整的高水位线时。
如果发生其中任何一种情况， gc都会停止运行，并对所有当前分配运行标记和清除垃圾收集。此功能在gc_run()函数中实现，该函数是公共 API 的一部分，并将所有工作委托给属于私有 API 的gc_mark()和gc_sweep()函数。
gc_mark()的任务是查找根并将从根引用的所有已知分配（或从根引用的分配，即传递性）标记为“已使用”。一旦标记完成， gc_sweep()就会迭代所有已知的分配并释放所有未使用的（即未标记的）分配，返回到gc_run()并且世界继续运行。
gc将保留可访问的内存分配并收集其他所有内容。如果满足以下任一条件，则分配被视为可达：
gc_start()的堆栈底部变量一样深（即bos是标记阶段期间考虑的最小堆栈地址）。gc_*alloc()分配的内容内部有一个指针指向分配内容。GC_TAG_ROOT 。朴素的标记和清除算法分两个阶段运行。首先，在标记阶段，算法查找并标记所有根分配以及从根可到达的所有分配。其次，在清除阶段，算法会遍历所有已知的分配，收集所有未标记并因此被视为无法访问的分配。
在标记阶段开始时，我们首先扫描所有已知的分配并使用GC_TAG_ROOT标记集找到显式根。每个根都是深度优先递归标记的起点。
gc随后检测堆栈中的所有根（从传递给gc_start()的堆栈底部指针bos开始）和寄存器（通过在标记阶段之前将它们转储到堆栈上）并使用它们作为起始点标记也是如此。
给定根分配，标记包括 (1) 将Allocation对象中的tag字段设置为GC_TAG_MARK ，以及 (2) 扫描分配的内存以查找指向已知分配的指针，并递归地重复该过程。
底层实现是一个简单的递归深度优先搜索，它扫描所有内存内容以查找潜在的引用：
void gc_mark_alloc ( GarbageCollector * gc , void * ptr )
{
Allocation * alloc = gc_allocation_map_get ( gc -> allocs , ptr );
if ( alloc && !( alloc -> tag & GC_TAG_MARK )) {
alloc -> tag |= GC_TAG_MARK ;
for ( char * p = ( char * ) alloc -> ptr ;
p < ( char * ) alloc -> ptr + alloc -> size ;
++ p ) {
gc_mark_alloc ( gc , * ( void * * ) p );
}
}
}在gc.c中， gc_mark()通过调用gc_mark_roots()标记堆栈上的已知根来启动标记过程。为了标记根，我们对所有已知的分配进行了一次完整的遍历。然后我们继续将寄存器转储到堆栈上。
为了使 CPU 寄存器内容可用于根查找， gc将它们转储到堆栈上。这是使用setjmp()以某种可移植的方式实现的，它在我们标记堆栈之前将它们存储在jmp_buf变量中：
...
/* Dump registers onto stack and scan the stack */
void ( * volatile _mark_stack )( GarbageCollector * ) = gc_mark_stack ;
jmp_buf ctx ;
memset ( & ctx , 0 , sizeof ( jmp_buf ));
setjmp ( ctx );
_mark_stack ( gc );
...使用volatile函数指针_mark_stack绕道到gc_mark_stack()函数是必要的，以避免内联对gc_mark_stack()的调用。
在标记所有可访问并因此可能仍在使用的内存之后，收集不可访问的分配就很简单了。这是gc_sweep()的实现：
size_t gc_sweep ( GarbageCollector * gc )
{
size_t total = 0 ;
for ( size_t i = 0 ; i < gc -> allocs -> capacity ; ++ i ) {
Allocation * chunk = gc -> allocs -> allocs [ i ];
Allocation * next = NULL ;
while ( chunk ) {
if ( chunk -> tag & GC_TAG_MARK ) {
/* unmark */
chunk -> tag &= ~ GC_TAG_MARK ;
chunk = chunk -> next ;
} else {
total += chunk -> size ;
if ( chunk -> dtor ) {
chunk -> dtor ( chunk -> ptr );
}
free ( chunk -> ptr );
next = chunk -> next ;
gc_allocation_map_remove ( gc -> allocs , chunk -> ptr , false);
chunk = next ;
}
}
}
gc_allocation_map_resize_to_fit ( gc -> allocs );
return total ;
}我们迭代哈希映射中的所有分配（ for循环），遵循每个链（带有chunk = chunk->next update 的while循环），并且（1）如果已标记块则取消标记；或者 (2) 调用该块的析构函数并释放未标记的内存，并保留我们释放的内存量的运行总数。
标记和扫描运行结束。停止的世界又恢复了，我们已经准备好迎接下一次奔跑了！
