I Tried To Write A Simple Garbage Collector


大概是四年前,在广州北京路的科技书店买下了这本讲垃圾回收的书。读完书的前半部分之后,姑且算是明白了基本的做法,但是一直没搞明白怎么将书中的伪代码落实到具体代码。直到某个凌晨三点多还睡不着的晚上,我终于想明白了一点:你不是只有一个起始点;你有 两个 。一个用来管理分配,一个用来清理垃圾。

姑且将前者称为yggdrasil……

The Plan

我们首先有负责管理所有被分配出来的对象的yggdrasil,还有引用这些被分配出来的对象的env:

before.png

我们沿着env给所有被env引用的对象做标记:

mark.png

于是我们就知道那些没有被标记的对象,而「没有被标记」=「env中没有」=「是可以被安全回收的垃圾」:

mark-sweep.png

最后我们将这些对象回收掉:

after-sweep.png

弄明白这些之后,做起来就非常简单了,就是普通的链表遍历和删除操作。

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字节,因为 xz 都会被标记。

Back

© 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