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<<0,无指针/块边界是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表示的。这是为什么呢？