6.2 垃圾回收

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

标记清扫算法

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

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

位图标记和内存布局

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

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

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

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

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

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

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

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

具体的内存布局如下图所示:
垃圾回收上篇 - 图1

精确的垃圾回收

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

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

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

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

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

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

  1.     struct MTypes
  2.     {
  3.         byte    compression;    // one of MTypes_*
  4.         bool    sysalloc;    // whether (void*)data is from runtime·SysAlloc
  5.         uintptr    data;
  6.     };

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

  1. MTypes_Empty:
  2.     所有的块都是free的，或者这个分配块的类型信息不可用。这种情况下data域是无意义的。
  3. MTypes_Single:
  4.     这个MSpan只包含一个块，data域存放类型信息，sysalloc域无意义
  5. MTypes_Words:
  6.     这个MSpan包含多个块(块的种类多于7)。这时data指向一个数组[NumBlocks]uintptr,，数组里每个元素存放相应块的类型信息
  7. MTypes_Bytes:
  8.     这个MSpan中包含最多7种不同类型的块。这时data域指下面这个结构体
  9.     struct {
  10.         type  [8]uintptr       // type[0] is always 0
  11.         index [NumBlocks]byte
  12.     }
  13.     第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存的。但是当类型不多时，可以把这些类型的指针集中起来放在数组中，然后存储数组索引。这是一个小的优化，可以节省内存空间。

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

  1. struct Type
  2. {
  3.     uintptr size;
  4.     uint32 hash;
  5.     uint8 _unused;
  6.     uint8 align;
  7.     uint8 fieldAlign;
  8.     uint8 kind;
  9.     Alg *alg;
  10.     void *gc;
  11.     String *string;
  12.     UncommonType *x;
  13.     Type *ptrto;
  14. };

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

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

  1.     for(;;) {
  2.         switch(pc[0]) {
  3.             case GC_PTR:
  4.             break;
  5.             case GC_SLICE:
  6.             break;
  7.             case GC_APTR:
  8.             break;
  9.             case GC_STRING:
  10.             continue;
  11.             case GC_EFACE:
  12.             if(eface->type == nil)
  13.                 continue;
  14.             break;
  15.             case GC_IFACE:
  16.             break;
  17.             case GC_DEFAULT_PTR:
  18.             while(stack_top.b <= end_b) {
  19.                 obj = *(byte**)stack_top.b;
  20.                 stack_top.b += PtrSize;
  21.                 if(obj >= arena_start && obj < arena_used) {
  22.                     *ptrbufpos++ = (PtrTarget){obj, 0};
  23.                     if(ptrbufpos == ptrbuf_end)
  24.                         flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
  25.                 }
  26.             }
  27.             case GC_ARRAY_START:
  28.             continue;
  29.             case GC_ARRAY_NEXT:
  30.             continue;
  31.             case GC_CALL:
  32.             continue;
  33.             case GC_MAP_PTR:
  34.             continue;
  35.             case GC_MAP_NEXT:
  36.             continue;
  37.             case GC_REGION:
  38.             continue;
  39.             case GC_CHAN_PTR:
  40.             continue;
  41.             case GC_CHAN:
  42.             continue;
  43.             default:
  44.             runtime·throw("scanblock: invalid GC instruction");
  45.             return;
  46.         }
  47.     }

小结

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

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

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