自己动手做 GC (1)

自己动手，丰衣足食——垃圾回收 Part 1

提示：本文所用的语法为 C++11 语法。

看来我想要做一个 Visual Novel 引擎的愿望一直没有消失。我最近见到了 nw.js，不过我对一个难以自适应的呈现器展示动态的、元素主要是位图和渲染的文字的东西抱有怀疑的态度，毕竟 CSS3 没掌握，也还不了解精髓。因此我做着第二手准备，就是开发自己的脚本引擎，以此为基础构建完整的 VN 引擎。（内容啥的……那只能看会不会遇到合适的人了。）一方面这是我的梦想之一，另一方面即使最后 VN 引擎万一冷场了，至少还给我留下一个脚本解释器作为自学编译原理的成果嘛。

闲话少说。在一个脚本解释器中，特别是动态类型的，我认为垃圾回收扮演着至关重要的角色——负责所有对象的生命周期管理。所以，在以前尝试从编译器下手和从表现层下手之后，这次要从最基础的垃圾回收器（garbage collector，GC）下手。

纵观现代的 GC，主要有两种方式：引用计数（reference counting）和标记-清除（mark and sweep）。其中，后者还衍生出如标记-压缩（mark and compact）、分代回收（generational garbage collection）等技术。

引用计数的优点在于实时性。每个对象被引用时引用计数增加1，被解除引用后引用计数减少1，计数器为0时就直接回收了。这样可以保证对象在确定不被需要的时候立即回收。缺点是频繁地计算引用计数会有轻微的性能影响，以及循环引用（例如 A-B-C-A 三元闭环）会导致无法回收的问题。采用此方式的有微软的 COM 技术、Python 语言、KiriKiri 2/KAG3 等等。

标记-清除的优点在于在空闲（idle）时间内不影响程序运行。在内存使用达到了阈值之后，先停止世界（stop the world），挂起主程序，对每个可达（reachable）对象进行标记，然后清除不可达（unreachable）的对象。缺点是，如果不进行执行优化，对象数多时在挂起的时候会产生显著的停顿。而且管理上，例如如果要压缩（移动指针）、分代（设置写屏障，write barrier），编写的难度会比较大。采用此方式的有 C# 的虚拟机（无论是微软的还是 Mono 的）、Java 的虚拟机、各大浏览器中的 JavaScript 虚拟机等等。

综合考虑，我还是选择实现一个标记-清除的 GC。（有种感觉，哪个地方漏了减少计数就糟糕了。）为此我读过一些文献，不过上面的措辞还是比较含糊。

将所有全局对象和栈上的对象标记为可达，然后以这些对象为根，进行对象遍历。遍历完成后，释放未被标记的对象。

思想很简单，实现上有两个问题。

1. 如何保存所有的对象（因为要遍历）？
2. 对象之间的相互引用是如何保存的？

我看完之后总是想不出这个思想在计算机中的映射是如何的。后来脑子一抽，想既然从最简单的开始实现，那就用一个数组呗。于是我们就有了一个数组。

std::vector<void *> *m_pAllObjects;

考虑到在实现中纯指针操作会很麻烦，就封装为一个结构体。

struct GCRecord
{
    // 要使用的内存空间
    void *ptr;
};
std::vector<GCRecord *> *m_pAllObjects;

这样问题1就解决了。轮到问题2。先想到对象之间是 n:n 映射，所以每个引用域也必须是数组。于是改变GCRecord的结构如下。

struct GCRecord
{
    void *ptr;
    // 指向该对象的对象
    std::vector<GCRecord *> *references_in;
    // 该对象指向的对象
    std::vector<GCRecord *> *references_out;
};

为了预留分代回收和增量回收（incremental garbage collection）的实现空间，以及结合应用场景（动态类型的脚本解释器），再增加几个字段，然后添加成员函数。

struct GCRecord
{
    // 标记状态（黑白灰）
	AGC_MARK_STATE markState;
	void *ptr;
	std::vector<GCRecord *> *references_in;
	std::vector<GCRecord *> *references_out;
	// 给 ptr 分配的空间
	asize_t allocatedSize;
	// ptr 指向的类的类 ID
	unsigned long classID;

	GCRecord();
	~GCRecord();
};

（吐槽：上面的命名方式混合了 UNIX 小写+下划线命名法、匈牙利命名法和 camelCase 命名法，写的时候随手写的，要统一啊！）

在释放阶段，只有未被标记（不可达）的GCRecord的析构函数会被调用。因此，指向其的所有对象都是不可达的，应该释放。

GCRecord::~GCRecord()
{
	for (auto r : *references_in)
	{
		delete static_cast<GCRecord *>(r);
	}
	// destructor = find_destructor_by_classid(this->classID);
	// destructor(this->ptr)
	free(this->ptr);
	delete references_out;
	delete references_in;
}

OK，感觉这就是所需的数据结构了。那么接下来来构造一个简单的标记-清除回收器。思想很简单，标记+清除即可。

class PlanC
{

public:

    // 初始化成员
	static void Initialize();
	// 释放成员
	static void Uninitialize();

    // 收集 = 标记+清除
	static void Collect();

    // 在堆上分配内存（不在根中）
	static void *AllocHeap(asize_t size);
	// 在全局对象堆上分配内存（在根中）
	static void *AllocGlobal(asize_t size);

private:

    // 标记
	static void Mark();
	// 清除
	static void Sweep();

};

初始化和释放就太简单了，执行该执行的操作即可。现在来看看标记的过程。

void PlanC::Mark()
{
	queue<GCRecord *> records;

	// 全局对象
	for (auto iter : *m_pGlobalSet)
	{
		if (iter)
		{
			records.push(iter);
		}
	}
	// 当前的栈环境
	for (auto iter : *m_pRuntimeStack)
	{
		if (iter)
		{
			records.push(iter);
		}
	}

    // 以下就是经典的非递归的图的广度遍历啦
	asize_t xs = records.size();
	while (xs > 0)
	{
		GCRecord *rec = records.front();
		// 标记为已经遍历（黑色）
		rec->markState = AGC_MARK_BLACK;
		records.pop();
		xs--;
		for (auto r2 : *rec->references_out)
		{
		    // 灰色和白色都是不用回收的对象
			if (r2->markState != AGC_MARK_BLACK)
			{
				records.push(r2);
				xs++;
			}
		}
	}
}

标记完毕之后就是清除。

void PlanC::Sweep()
{
	GCRecord *p;
	unsigned int c = m_pAllObjects->size();
	for (auto iter = m_pAllObjects->begin(); c > 0;)
	{
	    // 过滤空指针
		if (*iter)
		{
			if ((*iter)->markState == AGC_MARK_WHITE)
			{
			    // 由于 iter 即将无效，这里需要保存其指向的位置（类型是 GCRecord *）
				p = static_cast<GCRecord *>(*iter);
				m_uAllocatedSize -= p->allocatedSize;
				// 然后调用析构函数释放空间
				delete p;
				iter = m_pAllObjects->erase(iter);
				c--;
			}
			else
			{
			    // 将处理过的对象标记为未被遍历（白色）
			    (*iter)->markState = AGC_MARK_WHITE;
				// vector::erase() 的陷阱
				// http://blog.csdn.net/yang3wei/article/details/7589344
				iter++;
				c--;
			}
		}
		else
		{
		    // 对于空指针，不需要执行操作
		}
	}
}

在附上的代码中漏了重置状态为AGC_MARK_WHITE的那一行。

最后的PlanC::Collect()函数是二者的综合。

void PlanC::Collect()
{
	PlanC::Mark();
	PlanC::Sweep();
	// 利用 vector::swap() 释放 vector 不自动释放的空间
	// http://www.cnblogs.com/viviman/archive/2012/10/29/2775104.html
	ClearVector(*m_pAllObjects);
}

至此一个思想简单、实现简单的标记-清除 GC 就完成了，在不考虑增量回收、写屏障等等的情况下。来实测一下。

#include <iostream>

int main()
{
    PlanC::Initialize();
	std::cout << "Ready.\r\n";
	getchar();
	for (auto j = 0; j < 3; j++)
	{
		std::cout << "Begin!\r\n";
		for (auto i = 0; i < 10000; i++)
		{
			PlanC::AllocHeap(100 * 1024);
		}
		std::cout << "Filled.\r\n";
		getchar();
		PlanC::Collect();
		std::cout << "Collected.\r\n";
	}
	getchar();
	return 0;
}

上面的代码会分配大约 990 MB 的内存，所以请内存不足的同学谨慎运行。

有细心的同学可能会注意到，在PlanC::Sweep()中有一行：

m_uAllocatedSize -= p->allocatedSize;

这是一个可调的内存阈值。在完整的代码中，设置了一个内存阈值，当分配的内存即将超过阈值时强制垃圾回收。可以将m_uAllocatedSize设置为512 * 1024 * 1024（512 MB），在运行上面的代码时会触发超过3次垃圾回收。（那是自然……）

---

现在问题来了。试着运行并观察现象的同学可能会发现，运行结束后并没有像料想的那样收回全部内存，而是会剩下一些。

我的实验数据如下。

1. Win32，三次回收（j = 3）。内存阈值 2 GB 时剩余大约 60 MB，阈值 512 MB 时候剩余大约 30 MB。
2. Win32，单次回收（j = 1）。内存阈值 2 GB 时剩余大约 90 MB。
3. x64，三次回收（j = 3）。内存阈值 512 MB 时剩余大约 90 MB。

大约也可以看出，这是某些指针域未释放的缘故。不过目前还没找到原因。

---

现在的代码中还存在问题。

• GCRecord::~GCRecord()中未判明指针的有效性。当 A->B->C 这样的情况发生时，如果 B 先被释放了，那么在释放 C 时就会发生一个无效指针的错误。（实际上，在遍历的时候每个 GCRecord 是独立加入的，在 Sweep() 中也不进行耦合处理，所以实际上每个 GCRecord 被单独销毁，不会影响其他的 GCRecord。
• 压力小于10000的时候回收的过程就有明显的停顿感了。这是有待增量回收解决的。

日后分解吧！

---

附件：完整(?)代码