垃圾回收上篇
2021.07

6.2 垃圾回收

Go语言中使用的垃圾回收使用的是标记清扫算法。进行垃圾回收时会stoptheworld。不过,在当前1.3版本中,实现了精确的垃圾回收和并行的垃圾回收,大大地提高了垃圾回收的速度,进行垃圾回收时系统并不会长时间卡住。

标记清扫算法

标记清扫算法是一个很基础的垃圾回收算法,该算法中有一个标记初始的root区域,以及一个受控堆区。root区域主要是程序运行到当前时刻的栈和全局数据区域。在受控堆区中,很多数据是程序以后不需要用到的,这类数据就可以被当作垃圾回收了。判断一个对象是否为垃圾,就是看从root区域的对象是否有直接或间接的引用到这个对象。如果没有任何对象引用到它,则说明它没有被使用,因此可以安全地当作垃圾回收掉。

标记清扫算法分为两阶段:标记阶段和清扫阶段。标记阶段,从root区域出发,扫描所有root区域的对象直接或间接引用到的对象,将这些对上全部加上标记。在回收阶段,扫描整个堆区,对所有无标记的对象进行回收。(补图)

位图标记和内存布局

既然垃圾回收算法要求给对象加上垃圾回收的标记,显然是需要有标记位的。一般的做法会将对象结构体中加上一个标记域,一些优化的做法会利用对象指针的低位进行标记,这都只是些奇技淫巧罢了。Go没有这么做,它的对象和C的结构体对象完全一致,使用的是非侵入式的标记位,我们看看它是怎么实现的。

堆区域对应了一个标记位图区域,堆中每个字(不是byte,而是word)都会在标记位区域中有对应的标记位。每个机器字(32位或64位)会对应4位的标记位。因此,64位系统中相当于每个标记位图的字节对应16个堆中的字节。

虽然是一个堆字节对应4位标记位,但标记位图区域的内存布局并不是按4位一组,而是16个堆字节为一组,将它们的标记位信息打包存储的。每组64位的标记位图从上到下依次包括:

16位的 特殊位 标记位
16位的 垃圾回收 标记位
16位的 无指针/块边界 的标记位
16位的 已分配 标记位

这样设计使得对一个类型的相应的位进行遍历很容易。

前面提到堆区域和堆地址的标记位图区域是分开存储的,其实它们是以mheap.arena_start地址为边界,向上是实际使用的堆地址空间,向下则是标记位图区域。以64位系统为例,计算堆中某个地址的标记位的公式如下:

偏移 = 地址 - mheap.arena_start
标记位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
标记位 = *标记位地址 >> 移位

然后就可以通过 (标记位 & 垃圾回收标记位),(标记位 & 分配位),等来测试相应的位。其中已分配的标记为1<,无指针/块边界是1<<16,垃圾回收的标记位为1<<32,特殊位1<<48

具体的内存布局如下图所示:

垃圾回收上篇

精确的垃圾回收

像C这种不支持垃圾回收的语言,其实还是有些垃圾回收的库可以使用的。这类库一般也是用的标记清扫算法实现的,但是它们都是保守的垃圾回收。为什么叫“保守”的垃圾回收呢?之所以叫“保守”是因为它们没办法获取对象类型信息,因此只能保守地假设地址区间中每个字都是指针。

无法获取对象的类型信息会造成什么问题呢?这里举两个例子来说明。先看第一个例子,假设某个结构体中是不包含指针成员的,那么对该结构体成员进行垃圾回收时,其实是不必要递归地标记结构体的成员的。但是由于没有类型信息,我们并不知道这个结构体成员不包含指针,因此我们只能对结构体的每个字节递归地标记下去,这显然会浪费很多时间。这个例子说明精确的垃圾回收可以减少不必要的扫描,提高标记过程的速度。

再看另一个例子,假设堆中有一个long的变量,它的值是8860225560。但是我们不知道它的类型是long,所以在进行垃圾回收时会把个当作指针处理,这个指针引用到了0x2101c5018位置。假设0x2101c5018碰巧有某个对象,那么这个对象就无法被释放了,即使实际上已经没任何地方使用它。这个例子说明,保守的垃圾回收某些情况下会出现垃圾无法被回收。虽然不会造成大的问题,但总是让人很不爽,都是没有类型信息惹的祸。

现在好了,Go在1.1版本中开始支持精确的垃圾回收。精确的垃圾回收首先需要的就是类型信息,上一节中讲过MSpan结构体,类型信息是存储在MSpan中的。从一个地址计算它所属的MSpan,公式如下:

页号 = (地址 - mheap.arena_start) >> 页大小
MSpan = mheap->map[页号]

接下来通过MSpan->type可以得到分配块的类型。这是一个MType的结构体:

    struct MTypes
    {
        byte    compression;    // one of MTypes_*
        bool    sysalloc;    // whether (void*)data is from runtime·SysAlloc
        uintptr    data;
    };

MTypes描述MSpan里分配的块的类型,其中compression域描述数据的布局。它的取值为MTypes_Empty,MTypes_Single,MTypes_Words,MTypes_Bytes四个中的一种。

MTypes_Empty:
    所有的块都是free的,或者这个分配块的类型信息不可用。这种情况下data域是无意义的。
MTypes_Single:
    这个MSpan只包含一个块,data域存放类型信息,sysalloc域无意义
MTypes_Words:
    这个MSpan包含多个块(块的种类多于7)。这时data指向一个数组[NumBlocks]uintptr,,数组里每个元素存放相应块的类型信息
MTypes_Bytes:
    这个MSpan中包含最多7种不同类型的块。这时data域指下面这个结构体
    struct {
        type  [8]uintptr       // type[0] is always 0
        index [NumBlocks]byte
    }
    第i个块的类型是data.type[data.index[i]]

表面上看MTypes_Bytes好像最复杂,其实这里的复杂程度是MTypes_Empty小于MTypes_Single小于MTypes_Bytes小于MTypes_Words的。MTypes_Bytes只不过为了做优化而显得很复杂。

上一节中说过,每一块MSpan中存放的块的大小都是一样的,不过它们的类型不一定相同。如果没有使用,那么这个MSpan的类型就是MTypes_Empty。如果存一个很大块,大于这个MSpan大小的一半,因此存不了其它东西了,那么这个MSpan的类型是MTypes_Single。假设存了多种块,每一块用一个指针,本来可以直接用MTypes_Words存的。但是当类型不多时,可以把这些类型的指针集中起来放在数组中,然后存储数组索引。这是一个小的优化,可以节省内存空间。

得到的类型信息最终是什么样子的呢?其实是一个这样的结构体:

struct Type
{
    uintptr size;
    uint32 hash;
    uint8 _unused;
    uint8 align;
    uint8 fieldAlign;
    uint8 kind;
    Alg *alg;
    void *gc;
    String *string;
    UncommonType *x;
    Type *ptrto;
};

不同类型的类型信息结构体略有不同,这个是通用的部分。可以看到这个结构体中有一个gc域,精确的垃圾回收就是利用类型信息中这个gc域实现的。

从gc出去其实是一段指令码,是对这种类型的数据进行垃圾回收的指令,Go中用一个状态机来执行垃圾回收指令码。大致的框架是类似下面这样子:

    for(;;) {
        switch(pc[0]) {
            case GC_PTR:
            break;
            case GC_SLICE:
            break;
            case GC_APTR:
            break;
            case GC_STRING:
            continue;
            case GC_EFACE:
            if(eface->type == nil)
                continue;
            break;
            case GC_IFACE:
            break;
            case GC_DEFAULT_PTR:
            while(stack_top.b <= end_b) {
                obj = *(byte**)stack_top.b;
                stack_top.b += PtrSize;
                if(obj >= arena_start && obj < arena_used) {
                    *ptrbufpos++ = (PtrTarget){obj, 0};
                    if(ptrbufpos == ptrbuf_end)
                        flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
                }
            }
            case GC_ARRAY_START:
            continue;
            case GC_ARRAY_NEXT:
            continue;
            case GC_CALL:
            continue;
            case GC_MAP_PTR:
            continue;
            case GC_MAP_NEXT:
            continue;
            case GC_REGION:
            continue;
            case GC_CHAN_PTR:
            continue;
            case GC_CHAN:
            continue;
            default:
            runtime·throw("scanblock: invalid GC instruction");
            return;
        }
    }

小结

Go语言使用标记清扫的垃圾回收算法,标记位图是非侵入式的,内存布局设计得比较巧妙。并且当前版本的Go实现了精确的垃圾回收。在精确的垃圾回收中,通过定位对象的类型信息,得到该类型中的垃圾回收的指令码,通过一个状态机解释这段指令码来执行特定类型的垃圾回收工作。

对于堆中任意地址的对象,找到它的类型信息过程为,先通过它在的内存页找到它所属的MSpan,然后通过MSpan中的类型信息找到它的类型信息。

不知道读者有没有注意一个细节,MType中的data值应该是存放Type结构体的指针,但它却是uintptr表示的。这是为什么呢?