I Tried To Write A Simple Garbage Collector
大概是四年前,在广州北京路的科技书店买下了这本讲垃圾回收的书。读完书的前半部分之后,姑且算是明白了基本的做法,但是一直没搞明白怎么将书中的伪代码落实到具体代码。直到某个凌晨三点多还睡不着的晚上,我终于想明白了一点:你不是只有一个起始点;你有 两个 。一个用来管理分配,一个用来清理垃圾。
姑且将前者称为yggdrasil……
The Plan
我们首先有负责管理所有被分配出来的对象的yggdrasil,还有引用这些被分配出来的对象的env:
我们沿着env给所有被env引用的对象做标记:
于是我们就知道那些没有被标记的对象,而「没有被标记」=「env中没有」=「是可以被安全回收的垃圾」:
最后我们将这些对象回收掉:
弄明白这些之后,做起来就非常简单了,就是普通的链表遍历和删除操作。
The Code
The header gc.h
基本的数据结构定义:
struct ObjRef { bool marked; struct ObjRef* next; struct ObjRef* userlink; size_t size; void* data; };
其实这个东西一般不这么定义。我所知道的lua和cpython的gc,都是将next和marked这样的字段定义成某种通用的头部(Lua 5.4, CPython),然后为不同的对象定义不同的包含这个头部的类型;userlink部分则由不同对象包含的不同字段完成。也许以后我该抽空读一下对应的代码。
接口是很简单的:
// 初始化gc void GC_Init(size_t heapSize); // 分配对象 struct ObjRef* GC_Alloc(size_t dataSize); // Mark-sweep GC void GC_MarkSweep(); // 结束gc,清理掉所有还没有清理的对象 void GC_End();
同时,我需要一个能够反映gc分配发生错误的东西。
uint8_t errno; enum GC_ErrorType { // 分配ObjRef的malloc调用失败 MALLOC_FAIL = 1, // 分配具体内存的malloc调用失败 MALLOC_FAIL_DATA = 2, // 堆已满,GC未能清扫出必要的空间,不允许再分配对象 HEAP_FULL = 3, // 未初始化时即要求分配对象 USED_BEFORE_INIT = 4, // 已经初始化 ALREADY_INIT = 5, };
The implementation (gc.c
)
#include "gc.h"
参数定义和Bookkeeping的准备
我决定将默认的最大大小设为4MBytes。面对小型的程序,这个数字应该足够用了。
const size_t DEFAULT_HEAP_SIZE = 4 * 1024 * 1024; size_t HEAP_SIZE = DEFAULT_HEAP_SIZE; size_t CURRENT_HEAP_USAGE = 0;
为了简单起见我决定将yggdrasil定义成一个链表。 yggdrasil
作为yggdrasil的起点(同时也是Mark-sweep的起点), yggdrasilEnd
则是链表的末尾,往yggdrasil增添新分配的对象时需要得知这个信息。
struct ObjRef* yggdrasil; struct ObjRef* yggdrasilEnd;
初始化
bool inited = false; void GC_Init(size_t heapSize) { if (inited) { errno = ALREADY_INIT; return; } if (heapSize != 0) { HEAP_SIZE = heapSize; } CURRENT_HEAP_USAGE = 0; yggdrasil = NULL; inited = true; }
一个用于初始化 ObjRef
的帮助函数:
void _GC_InitRef(struct ObjRef* x, size_t designatedSize) { x->data = NULL; x->next = NULL; x->size = designatedSize; x->userlink = NULL; x->marked = false; }
对象分配
struct ObjRef* GC_Alloc(size_t dataSize) { struct ObjRef* res; // GC_Alloc不允许初始化前调用。 if (!inited) { errno = USED_BEFORE_INIT; return NULL; } if (dataSize + sizeof(struct ObjRef) + CURRENT_HEAP_USAGE > HEAP_SIZE) { // 预想的堆已经没有剩余的空间。 // 在这里GC,期望GC过后会空出足够的空间。如果还是没有空间,那么就失败。 GC_MarkSweep(); if (dataSize + sizeof(struct ObjRef) + CURRENT_HEAP_USAGE > HEAP_SIZE) { errno = HEAP_FULL; return NULL; } } // 开始分配内存。 res = (struct ObjRef*)malloc(sizeof(struct ObjRef)); if (!res) { errno = MALLOC_FAIL; return NULL; } _GC_InitRef(res, dataSize); res->data = (void*)malloc(dataSize); if (!res->data) { // NOTE: 注意这里。之前的ObjRef的malloc是成功的,所以这里要free回去。 free(res); errno = MALLOC_FAIL_DATA; return NULL; } // 将新分配的对象纳入管理范围。 // NOTE: init之后整棵yggdrasil为空,对应的变量没有任何reference。 // 这里为了能够在这样的场合下正确管理yggdrasil,设定成「第一个被分配的对象自动成为yggdrasil的根部」。 if (!yggdrasil) { yggdrasil = yggdrasilEnd = res; } else { yggdrasilEnd->next = res; yggdrasilEnd = res; } CURRENT_HEAP_USAGE += dataSize + sizeof(struct ObjRef); return res; }
垃圾回收
void _GC_Mark(); void _GC_Sweep(); // Mark-sweep就是mark之后sweep void GC_MarkSweep() { _GC_Mark(); _GC_Sweep(); } // Mark。注意我们这里走的是userlink而不是next。 // next是yggdrasil专用;userlink才是我们实际的reference。 // 但是这里会有一个问题:yggdrasil头部指向的对象和它所指向的对象必定会被标记。 // 这应该不会产生太大的麻烦:如果考虑到将这个东西用到语言的解释器里,会位于yggdrasil顶部的一般都 // 会是environment的root,但是这终究是个问题。 void _GC_Mark() { struct ObjRef* x = yggdrasil; while (x) { x->marked = true; x = x->userlink; } } // 释放对象的辅助函数。 void _GC_FreeRef(struct ObjRef* x) { free(x->data); CURRENT_HEAP_USAGE -= x->size + sizeof(struct ObjRef); free(x); } // sweep. void _GC_Sweep() { struct ObjRef* x = yggdrasil; struct ObjRef* y = yggdrasil->next; while (y) { // 寻找第一个没有被标记的对象 while (y && y->marked && y->next) { x = y; y = y->next; // 注意我们要在这里清除原本的标记,否则多次GC的标记会叠加,产生「是垃圾却没有被删掉」的 // 错误效果。 x->marked = false; } // 如果没有找到那么就结束。 if (!y) { return; } // 现在y只会有两种情况: // 1. y指向现在yggdrasil里的第一个没有被标记的对象(违反y->marked) // 2. y指向yggdrasil的末尾(违反y->next)。由于y->marked的存在,这个末尾一定是被标记的。 // 第2种情况也表示已经sweep完了,需要退出。清除标记的做法跟上面是同一个原因。 if (y->marked) { y->marked = false; break; } // 否则我们进行一个删除元素的操作。 x->next = y->next; _GC_FreeRef(y); // 我们还需要保证yggdrasilEnd必定指向yggdrasil的最后一个元素。 // 这里我们判断我们是否因为yggdrasilEnd没有被标记而去掉了yggdrasilEnd。如果我们正处于这种 // 情况之下,那么应该有两个条件: // 1. 此时的未修改的yggdrasilEnd的指向跟y相同。 // 2. x作为y的前一个对象,它此时的next指向为空。 if (!x->next && (yggdrasilEnd == y)) { yggdrasilEnd = x; } // 做完上面的操作之后,让y指向x的下一个对象,继续sweep。 y = x->next; } // 注意:我们在这里考虑和不考虑删掉yggdrasil根部的情况都是一样的,因为根部由于上面的那个mark // 函数的设定必定会被标记。 }
销毁GC
销毁GC只要清掉整个yggdrasil即可:
void GC_End() { struct ObjRef* x = yggdrasil; struct ObjRef* y; while (x) { if (x->size && x->data) { free(x->data); } y = x; x = x->next; free(y); } }
The test (main.c
)
在这个测试中我故意将堆设置成100Bytes的大小,目的是为了检查堆空间不足以分配对象时是否会触发gc。
int main() { GC_Init(100); printf("CurrentUsage: %zu\n", GC_CurrentUsage()); struct ObjRef* x = GC_Alloc(sizeof(int)); printf("CurrentUsage: %zu\n", GC_CurrentUsage()); struct ObjRef* y = GC_Alloc(sizeof(int)); printf("CurrentUsage: %zu\n", GC_CurrentUsage()); struct ObjRef* z = GC_Alloc(sizeof(int)); printf("CurrentUsage: %zu\n", GC_CurrentUsage()); x->userlink = z; GC_MarkSweep(); printf("CurrentUsage: %zu\n", GC_CurrentUsage()); GC_End(); }
输出结果如下:
// init之后 CurrentUsage: 0 // after x CurrentUsage: 44 // after y CurrentUsage: 88 // after z CurrentUsage: 88 // after x->userlink=z CurrentUsage: 88
可以看到:
- 为了分配
z
,其中有一个对象被回收掉了(这个对象是y
;因为x
是yggdrasil的根部,在这个gc里必定会被标记)。 - 设置
x->userlink = z
之后GC,最后的结果仍然是88字节,因为x
和z
都会被标记。
© Sebastian Higgins 2021 All Rights Reserved.
Content on this page is distributed under the CC BY-NC-SA 4.0 license unless further specified.
Last update: 2021.6.28