使用forwarding指针的深度优先GC算法 #
复制 GC 算法，最核心的就是如何实现复制。我们自己就可以很容易地写出一个基于深度优先搜索的算法，它的伪代码如下所示：
void copy_gc() {
for (obj in roots) {
*obj = copy(obj);
}
}
obj * copy(obj) {
new_obj = to_space.allocate(obj.size);
copy_data(new_obj, obj, size);
for (child in obj) {
*child = copy(child);
}
return new_obj;
}
上面的代码中缺少了对重复访问对象的判断。考虑到有两个对象 A 和 B，它们都引用了对象 C，而且它们都是活跃对象，现在我们对这个图进行深度优先遍历。
在遍历过程中，A 先拷到 to space，然后 C 又拷过去，这时候，空间里的引用是这种状态：
A 和 C 都拷到新的空间里了，原来的引用关系还是正确的。但我们的算法在拷贝 B 对象的时候，先完成 B 的拷贝，然后你就会发现，此时我们还会把 C 再拷贝一次。这样，在 To 空间里就会有两个 C 对象了，这显然是错的。我们必须要想办法解决这个问题。
通常来说，在一般的深度优先搜索算法中，我们只需要为每个结点增加一个标志位 visited，以表示这个结点是否被访问过。但这只能解决重复访问的问题，还有一件事情我们没有做到：新空间中 B 对象对 C 对象的引用没有修改。这是因为我们在对 B 进行拷贝的时候，并不知道它所引用的对象在新空间中的地址。
解决这个问题的办法是使用 forwarding 指针。也就是说每个对象的头部引入一个新的域（field），叫做 forwarding。正常状态下，它的值是 NULL，如果一个对象被拷贝到新的空间里以后，就把它的新地址设到旧空间对象的 forwarding 指针里。
当我们访问完 B 以后，对于它所引用的 C，我们并不能知道 C 是否被拷贝，更不知道它被拷贝到哪里去了。此时，我们就可以在 C 上留下一个地址，告诉后来的人，这个地址已经变化了，你要找的对象已经搬到新地方了，请沿着这个新地址去寻找目标对象。这就是 forwarding 指针的作用。下面的图展示了上面描述的过程：
如果你还不太明白，我再给你举一个形象点儿的例子：你拿到一张画，上面写着武穆遗书在临安皇宫花园里。等你去花园里找到一个盒子，却发现里面的武穆遗书已经不在了，里面留了另一幅画，告诉你它在铁掌峰第二指节。显然，有人移动过武穆遗书，并把新的地址告诉你了，等你第二次访问，到达临安的时候，根据新的地址就能找到真正的武穆遗书了。
到这里，我们就可以将 copy gc 的算法彻底完成了，完整的算法伪代码如下所示：
void copy_gc() {
for (obj in roots) {
*obj = copy(obj);
}
}
obj * copy(obj) {
if (!obj.visited) {
new_obj = to_space.allocate(obj.size);
copy_data(new_obj, obj, size);
obj.visited = true;
obj.forwarding = new_obj;
for (child in obj) {
*child = copy(child);
}
}
return obj.forwarding;
}
这样一来，我们就借助深度优先搜索算法完成了一次图的遍历。