GC初步

發表於   |   分類於

前面

本来是想在CPP相关的文里面讨论一下内存管理的事情，不过想了一想，还是放到编译相关的文章里面谈会更合适一些。

这次关于CG的讨论只关注一些基本原理以及算法，不涉及到并行GC等高级话题（水平不够Hold不住）。

正文

作用域(RAII的一个应用)

在C++中，我们知道一个对象的生存周期是与它的作用域有关的。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
struct Info
{
	int a;
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
};
int main(int argc, char** argv)
{
	{
		Info info(1);
		{
			Info i(2);
		}
	}
	return 0;
}

这就在一定程度上给我们一个方案：用一个对象包裹分配的内存地址，当该对象出了它作用域之后自动调用free/delete，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
struct Info
{
	int a;
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
	void say() { printf("this is %d\n", this->a); }
};

template<typename T>
struct SmartPtr
{
	T* ptr;
	SmartPtr(T* p) :ptr(p) {}
	~SmartPtr() { delete ptr; }
};

int main(int argc, char** argv)
{
	{
		SmartPtr<Info> i1(new Info(1));
		{
			SmartPtr<Info> i2(new Info(2));
			i2.ptr->say();
      // 注意赋值操作符带来的错误！！！
      // 如果i2是从i1而来： SmartPtr<Info> i2 = i1;
      // 那么，i2一旦出了作用域，就会连带将i1的内存释放掉，而这显然是不正确的！
		}
	}
	return 0;
}

这当然是不足以解决问题的——如果分配的内存希望能够在出了作用域之后继续存在怎么办？况且依旧无法对上面的代码注释中提到的情况作出应对。

引用计数

引用计数其实是很常见的，比如在操作系统中需要记录某内核对象的引用次数，只有当该对象的计数为0的时候才能销毁该对象；再比如COM对象的引用计数。示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
class Info
{
public:
	int a;
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
	void say() { printf("this is %d\n", this->a); }
};

template<typename T>
class SmartPtr
{
public:
	struct refStruct
	{
		T* ptr;
		int refc;

	}* sptr; // 注意这里并非是直接将计数放在Smartprt中，而是加了一层。
	SmartPtr() :sptr(0)
	{

	}
	SmartPtr(T* p) :sptr(0)
	{
		if (sptr == NULL)
		{
			sptr = new refStruct;
			printf("new refStruct here\n");
			sptr->ptr = p;
			sptr->refc = 1;
		}
	}
	~SmartPtr()
	{
		if (sptr != NULL)
		{
			--sptr->refc; // 析构的时候减少计数
			if (sptr->refc <= 0)
			{
				delete this->sptr->ptr;
				this->sptr->ptr = NULL;
				printf("dead refStruct here\n");
				delete this->sptr;
				this->sptr = NULL;
			}
		}
	}
	SmartPtr<T>& operator=(SmartPtr<T>& sp)
	{
		if (this != &sp)
		{
			this->sptr = sp.sptr;
			this->sptr->refc++; // 赋值的时候增加计数
		}
		return * this;
	}
	int refCount()
	{
		if (this->sptr)
		{
			return this->sptr->refc;
		}
	}
};

int main(int argc, char** argv)
{
	{
		SmartPtr<Info> i1(new Info(1));
		printf("i1 ref count: %d\n",i1.refCount());
		{
			SmartPtr<Info> i2(new Info(2));
			printf("i2 ref count: %d\n", i1.refCount());
			SmartPtr<Info> i3;
			i3 = i1;
			printf("i1 ref count: %d\n", i1.refCount());
			printf("i3 ref count: %d\n", i3.refCount());
		}
		printf("i1 ref count: %d\n", i1.refCount());
	}
	return 0;
}

其实上面的例子也就是shared_ptr的原理了。注意到引用计数字段并没有直接放在Smartptr对象中——因为计数只与原始指针有关，一旦直接放入Smartptr对象中，赋值的时候就会产生副本，计数递减就只是对副本的操作，从而使得内存泄漏。

附上面代码的结果：

result

僵局：循环引用

仅从结果来看，引用计数工作的很好。

然而确实如此么？请注意这样一个事实：上面的对象是没有包含其他对象的指针的！

我们将代码改动一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
template<typename T>
class SmartPtr
{
public:
	struct refStruct
	{
		T* ptr;
		int refc;

	}* sptr;
	SmartPtr() :sptr(0)
	{

	}
	SmartPtr(T* p) :sptr(0)
	{
		if (sptr == NULL)
		{
			sptr = new refStruct;
			printf("new refStruct here\n");
			sptr->ptr = p;
			sptr->refc = 1;
		}
	}
	~SmartPtr()
	{
		if (sptr != NULL)
		{
			--sptr->refc; // 析构的时候减少计数
			if (sptr->refc <= 0)
			{
				delete this->sptr->ptr;
				this->sptr->ptr = NULL;
				printf("dead refStruct here\n");
				delete this->sptr;
				this->sptr = NULL;
			}
		}
	}
	SmartPtr<T>& operator=(const SmartPtr<T>& sp)
	{
		if (this != &sp)
		{
			this->sptr = sp.sptr;
			this->sptr->refc++; // 赋值的时候增加计数
		}
		return * this;
	}
	int refCount()
	{
		if (this->sptr)
		{
			return this->sptr->refc;
		}
	}
};

class Info
{
public:
	int a;
	SmartPtr<Info> link; // 注意这里的link！！！
	Info(int va) :a(va) { printf("Hello, Info %d.\n", this->a); }
	~Info() { printf("Bye, Info %d.\n", this->a); }
	void Say() { printf("this is %d\n", this->a); }
	void LinkTo(const SmartPtr<Info>& link) { this->link = link; }
};

int main(int argc, char** argv)
{
	int* r1 = NULL;
	int* r2 = NULL;
	{
		SmartPtr<Info> i1(new Info(1));
		r1 = &i1.sptr->refc; // 取地址
		printf("i1 ref count: %d\n",i1.refCount());
		{
			SmartPtr<Info> i2(new Info(2));
			r2 = &i2.sptr->refc; // 取地址
			printf("i2 ref count: %d\n", i2.refCount());
			// 令其发生循环引用
			i1.sptr->ptr->LinkTo(i2);
			i2.sptr->ptr->LinkTo(i1);
			// 打印计数值
			printf("i1 ref count: %d\n", i1.refCount());
			printf("i2 ref count: %d\n", i2.refCount());
		}
		printf("i1 ref count: %d\n", i1.refCount());
	}
	//
	printf("Final: ref i1 = %d, ref i2 = %d\n", * r1, * r2);
	return 0;
}

附上上面的代码执行结果：

result

发现引用计数不再发挥效用了！！

图示会更加清楚：

eg

注意，这里在Info对象中添加的link字段。实际上，该字段可以认为是与Java/C#/Python中的引用一致的东西。前面的文章里面有提到过引用和指针之间是不同的，在这里将会有实际的体会：引用的概念比指针要更加高级与抽象。

如何破解这个僵局呢？

破局

破局的要点还是在上面那张图中：link->连线->方向+节点->有向图！

如果我们能够在GC之前把回边砍掉，从而恢复正确的引用计数，那么就可以正确完成垃圾回收了！

这里说明一下，上面的那张图实际上不是很正确：为了与计数对应而删掉了有向边——事实上有向边是没有删掉的（因为计数的减少并非有向边去掉导致的）。

在图中找出一个回边并不是个难事——遍历扫描一下就可以了。发现回边之后更改边两端的节点的引用计数即可。

然而在对一个图进行扫描的时候需要知道起点，而很多时候，分配的内存相互引用形成的图并非是一个连通图，于是这就引出了另外一个概念：Root集合。

Root集合与Mark-Sweep

所谓Root集合，其实就是GC回收时，扫描开始的“点”。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
SmartPtr<Info> g_i1(new Info(123));
SmartPtr<Info> g_i2(new Info(456));   // ----> ①

void addLinkTo(SmartPtr<Info>& ptr, int num)
{
	ptr.sptr->ptr->link = SmartPtr<Info>(new Info(num));
}

int main(int argc, char** argv)
{
	{
		addLinkTo(g_i1,789);						// ----> ②
		SmartPtr<Info> i1(new Info(1)); // ----> ③
		{
			SmartPtr<Info> i2(new Info(2)); // ----> ④
			addLinkTo(i1,11);			// ----> ⑤
		}
	}
	// ----> ⑥
	addLinkTo(g_i1,1234); // 这里把以前的789那个对象给顶替了。如果不对其进行回收的话，将会产生内存泄漏。
	//
	...
}

不难发现，Root集合一般而言，是由全局变量，静态变量，寄存器值，方法参数，或者是由程序入口所在域及其子域中的变量等构成的。

前面我们已经知道每次加一个Link，就可以在相应的节点上加上一条有向边，那么上面的代码可以对应下面的图，表号对应代码中的注释：

.

注意内容为789的那个节点。这个节点是可以确定属于垃圾的。通过以上的描述，也不难发现Root集合应当包含的节点。

当我们根据Root集合进行扫描的时候，把可达节点做上标记（Mark）并收集起来，然后将不可达节点删除（Sweep）掉，就可以完成GC过程了——这就是Mark-Sweep算法的原理。

至于Root节点们，当它们出了自己的作用域之后必然将会被删除，到那时，剩下的所有节点都不再是可达节点，从而会被全部回收（当然对于全局变量，程序一旦结束，OS也会回收这些内存的）。

更进一步：三色标记模型

注意，截至到上一个部分，我们都是在对图的结构稳定情况下进行处理的，也就是要求当GC进行的时候，整个程序都应当停下来，不再对内存进行分配，直到GC过程处理完毕，也就是通常所说的“Stop The World”。

对于实时性要求不高的场合，这不失为一种有效的解决方法，然而对于交互式系统和实时系统这是无法接受的——至少，对于一个自动驾驶系统，如果该减速停车的时候来了一次GC，后果不堪设想。

这就需要另外一系列行之有效的办法来将这个时间碎片化，分散出去。引用计数可以在一定程度上做到这些，但还不够，于是，增量收集登场了。

在这个过程中，增量/并行算法将“无用垃圾信息收集穿插于程序执行过程中，避免对程序的长时间打断”。通常，由于应用程序本身总是在改变图的结构，因此将程序视为“改变器”；而GC模块，则视为“回收器”。

三色标记模型作为对Mark-Sweep的拓展补充，在增量标记中发挥了重要的作用。

在前面介绍LCA的文章中已经对染色法有过一定的介绍了，这里依旧是分阶段进行染色的，不过略有不同。

  • 对于未访问过的对象，标记为白色；
  • 对于已经访问过，但是其子对象还没有访问过的对象，标记为灰色；
  • 对于连子对象也访问过的对象，标记为黑色。

显然Sweep阶段完成之后，白色节点是属于不可达节点的，应当删除。但就上面描述而言，似乎没有什么特别的地方。而三色标记模型则明确了两个要点：

  • 黑色节点是不能够直接指向白色节点的。
  • 所有的灰色节点都处于一个待处理的数据结构中，也就是说，灰色节点属于一个中间态。

应该明确这样的一点：标记颜色的目的，是为了保留当前结点的状态。

很显然，当改变器对图中的一个黑色结点进行更改的时候（注意，出现了黑色节点也就说明了Mark过程是正在进行（或者已经Sweep了）），例如进行了一个LinkTo的操作，这个操作使得黑色节点变成了灰色节点。这个更改必须被及时、高效地的通知给收集器，通常情况下，这需要使用到“写障碍”或者是“读障碍”，他们基本都是利用OS，对相应的内存加上“读/写”锁来完成的。

另一种流派，复制收集（Copying GC）

相对于Mark-Sweep而言，复制收集更加易于理解，但一样要进行一次扫描阶段。

复制收集的主要做法是首先为应用程序分配一个大内存，然后将其一分为两个Pool。

  • 初始化阶段任选一块内存作为Pool，命名为SrcPool，另一个命名为DestPool，应用程序的所有内存申请均从SrcPool中划分。

  • 当SrcPool中没有足够的可用空间时，触发GC。

  • GC的扫描阶段标记完毕可达节点。

  • GC的复制阶段将SrcPool中所有标记的可达节点复制到DestPool，复制完毕之后，交换两个Pool的引用。

剩下的就是以上过程的迭代了。很显然，两个Pool起到了内存池的作用，并且内存经过了整理压缩，一定程度上解决了内存碎片的问题，并提高内存页的命中率；但这种方式的一个不好的地方在于它至少要浪费一半的内存空间；更有甚者，如果采用DFS（无论是否显式栈），还是基于额外队列的BFS，都需要另外的空间。

由于Copying GC也是有着扫描这一过程，因此三色标记模型实际也是可以在这上面采用的。

Cheney算法

为了解决额外空间的问题，Cheney算法利用复制对象过程中的特点（对象复制过后是紧凑的），采用destPool中的scan到next中间部分的记录作为BFS的队列（scan与next是两个指针），从而解决了这一问题。

现在使用四个对象来简单说明一下这个算法：

Cheney

首先是R对象作为Root被首先复制到DestPool中。R中保存了对象C与D的引用，这两个引用依旧指向SrcPool。

于是复制C和D到DestPool中，同时更改R中两个引用的指向，使其正确。

此时D中的引用仍旧指向SrcPool。

复制对象E到DestPool中，更改对象D中对E的引用的指向。

图中的S与N代表了scan指针与next指针。当scan最终等于next的时候，对该Root的处理结束。

引用与指针的区别再一次体现了出来：这里的引用包含了指向SrcPool的指针，被以此为标识来说明引用的对象是否还处于SrcPool中。

在编译课程中的GC就使用了该算法，当然实际过程会相对麻烦一些。

世代收集

分代的思想是基于这样的事实的：

  • 总是有那么一部分内存是变化不大的；
  • 当一块内存在一次或者多次GC中存活下来，那么它继续存活的几率会比较高；
  • 新分配的对象总是会马上死亡，无法经过第二次GC。

于是可以按照“代”将堆划分出来，比如将堆为老中青三代：

  • 新分配的对象总是从青年堆中分配，GC总是首先在青年堆中进行；
  • 将青年堆中存活的对象复制到中年堆中；
  • 当中年堆满的时候进行一次在中年堆上的GC，存活下来的对象复制到老年堆中；
  • 当老年堆满的时候，进行一次老年队上的GC，此时可以用Mark-Sweep或者Copy-Compact（这是在当前堆上进行的，该方法类似于内存碎片整理）等方法进行回收，一般来讲，尽量还是在回收后将对象紧凑放置。

上面只是世代收集的思想，当然也可以分成更多世代，视设计而定。