gc:C语言的垃圾回收库-中文
Table of Contentsgc:标记并清除C的垃圾回收致谢文档概述快速开始下载,编译和测试基本用法核心API启动,停止,暂停,恢复和运行GC内存分配和释放辅助功能基本概念数据结构垃圾收集可达性标记扫描算法寻找根源深度优先递归标记将寄存器转储到堆栈中Sweeping-扫地《gc:C语言的垃圾回收库-英文》gc:标记并清除C的垃圾回收gc是保守的,线程局部的,按标记清除的垃圾收集器的实现。该实
Table of Contents
gc:标记并清除C的垃圾回收
gc
是保守的,线程局部的,按标记清除的垃圾收集器的实现。该实施方式提供标准的POSIX一个全功能的替代malloc()
,calloc()
,realloc()
,和free()
电话。
重点gc
是在不深入研究特定于体系结构的优化的深度的情况下,提供标记-清除GC的概念上清晰的实现(例如,参见Boehm GC)。它应该特别适合于学习目的,并且可以进行各种优化(欢迎PR!)。
最初的动机gc
是我希望 完全从头开始用C语言编写我自己的LISP,而这需要进行垃圾回收。
致谢
如果没有阅读其他人的著作的能力,这项工作将是不可能的,最著名的是Boehm GC,Orangeduck的tgc(也遵循小巧而简单的理想)和The Garbage Collection Handbook。
文档概述
- 阅读下面的快速入门,了解如何快速入门
- 该概念介绍基本概念和设计决策进入实施
gc
。 - 与概念交织在一起,有一些实现部分详细介绍了核心组件的实现,请参见哈希映射实现,将堆栈中的寄存器转储,查找根以及 深度优先的递归标记。
快速开始
下载,编译和测试
$ git clone git@github.com: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
它描述了核心API,请参阅参考资料gc.h
以获取更多详细信息和低级API。
启动,停止,暂停,恢复和运行GC
为了初始化并开始垃圾回收,请使用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
当它收集静态变量时,当前不保证特定的顺序。如果需要以特定顺序释放静态var,则用户应在调用gc_free()
之前按所需顺序调用它们gc_stop()
,请参见下文。
也可以使用以下方法触发显式的内存释放
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);
基本概念
垃圾回收背后的基本思想是自动化内存分配/取消分配周期。这是通过跟踪所有已分配的内存并定期触发仍在分配但无法访问的内存的释放来实现的。
许多高级垃圾收集器还实现了自己的内存分配方法(即replace 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;
,以及内部的一组static
函数gc.c
,它们为公共API的实现提供哈希映射语义。
的AllocationMap
是在中央数据结构GarbageCollector
,其是公共API的一部分的结构:
typedef struct GarbageCollector {
struct AllocationMap* allocs;
bool paused;
void *bos;
size_t min_size;
} GarbageCollector;
有了基本的数据结构,任何gc_*alloc()
内存分配请求都是一个两步过程:首先,通过系统(即standard 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
随后检测堆栈中的所有根(从bos
传递给的堆栈底部指针开始gc_start()
)和寄存器(通过在标记阶段之前将它们转储到堆栈中)并将它们也用作标记的起点。
深度优先递归标记
给定根分配,标记包括(1)将对象中的tag
字段 设置Allocation
为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()
Sweeping - 扫地
在标记了所有可访问的并因此可能仍在使用的内存之后,收集不可达的分配是很简单的。这是来自的实现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
每个链(while
带有chunk = chunk->next
更新的循环)之后的哈希映射(循环)中的所有分配,并且(1)取消标记该块(如果已标记);或(2)在该块上调用析构函数并释放内存(如果未标记),从而保持我们释放的内存总量。
马克和扫杆比赛到此结束。已停止的世界将恢复,我们已准备好进行下一次运行!
更多推荐
所有评论(0)