新生代的垃圾回收：Copy GC之基本原理

据我所能查到的资料，基于复制的GC算法最早是Marvin Minsky提出来的。

这个算法的思路很简单，总的来说，就是把空间分成两部分，一个叫分配空间（Allocation Space），一个是幸存者空间（Survivor Space）。创建新的对象的时候都是在分配空间里创建。在GC的时候，把分配空间里的活动对象复制到Survivor Space，把原来的分配空间全部清空。然后把这两个空间交换，就是说Allocation Space变成下一轮的Survivor Space，现在的Survivor Space变成Allocation Space。

在有些文献中，或者实现中，allocation space也会被称为from space，survivor space也被称为to space。JVM代码中，这两套命名方式都会出现，所以搞清楚这点比较有好处。我们的文章中，为了方便后面解析JVM代码，还是使用from space和to space来指代分配空间和幸存者空间。

copy gc的想法很简单，但真要使用代码实现出来，还是有很多细节要处理的。我从最基本最原始的算法开始介绍，希望能从浅入深地把这个事情说清楚。

朴素的Copy算法

最早的，最简单的copy算法，是把程序运行的堆分成大小相同的两半，一半称为from空间，一半称为to空间。利用from空间进行分配，当空间不足以分配新的对象的时候，就会触发GC。GC会把存活的对象全部复制到to空间。当复制完成以后，会把 from 和 to 互换。

用图来表示就是这样的：

此时，from空间已经满了，A对象存活，A又引用了C和D，所以C和D也是活跃的。已经没有任何地方引用B对象了，那么B就是垃圾了。这时候，如果想再创建一个新的对象就不行了，这时就会执行GC算法，将A，C，D都拷贝到新的空间中去。

然后把原来的空间全部清空。这样，就完成了一次垃圾回收。

有几个问题要解决，第一个问题，如何判断A和B是否存活。因为C和D是被A引用的，那么，A如果是存活的，C和D就是存活的，这个相对简单一些。我们先看一下Java程序中怎么样的：

public static void foo() {
    A a = new A();
    bar();
    E e = new E();
}

public static void bar() {
    B b = new B();
}

在上面的例子中，在创建对象E的时候，已经从bar的调用中返回了。这个时候，对象a还存活于foo的调用栈里，而b已经没有任何地方会去引用它了——原来唯一的引用，bar的栈空间，已经消失了。所以b就变成了垃圾。而这个时候由于from空间不足，无法正确地创建E，所以，就会执行GC，这时候 b 做为垃圾就被回收了。

可见，如果存在一个从栈上出发到对象的引用，那么这个对象就是存活的。所以我们把栈上的这种引用称为roots。roots包含很多内容，除了栈上的引用，JNIHandle，Universe等等都会有向堆上的引用，但在我的文章里，只以栈上的引用做为roots来讲解。

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;
}

算法的开始是从roots的遍历开始，然后对每一个roots中的对象都执行copy方法。

如果这个对象没有被访问过，那么就在to space中分配一个与该对象大小相同的一块内存，然后把这个对象的所有数据都拷贝过去（copy data），然后把它的visited标记为true，它的forwarding记为新的地址。

接着遍历这个对象的所有引用，执行copy。这个过程是一个典型的深度优先搜索。

然后，还有最重要的一步，把forwarding做为返回值，返回给用者，让它更新引用。为什么要有forwarding这个属性呢？看起来很麻烦的样子，我直接在分配完了就把引用我的指针改掉不就行了吗？

考虑这样一种情况，A和B都引用了C：

然后我们执行copy算法，A先拷到to space，然后C又拷过去，这时候，空间里的引用是这种状态：

A和C都拷到新的对象里了，原来的引用关系还是正确的，美滋滋。但是B就惨了，它并不知道自己引用的C已经被拷贝了。当我们访问完B以后，对于它所引用的C，只看到C已经被搬走了，但并不知道搬到哪里去了。这就是forwarding的含义，我们可以在C上留下一个地址，告诉后来的人，这个地址已经失效了，你要找的对象已经搬到某某地了，然后你只要把引用更新到新的地址就好了。

举个例子，你有一个通讯录，上面记了你朋友家的地址在东北旺西路南口18号，当你按这个地址去找他的时候，看见他家门口贴了一张纸条，说我已经搬到北京西站南广场东81号了。好，那你就可以把这个新的地址更新到通讯录里了，下次，你按照新的地址还能找到你的朋友。

如上图所示，当B再去访问C的时候，就看到C已经被拷贝过了，而C通过forwarding指针引用了新的地址，那么B就可以根据这个新的地址把自己对C的引用变成对C'的引用。

Copy GC的特点

在普通的应用程序中，有大量的对象生命周期并不长，很多都是创建了以后没多久，就会变成垃圾（例如，一个函数通出以后，它所使用的局部变量都全都是垃圾了）。所以，在执行Copy GC时，存活的对象会比较少。我们执行Copy GC只要把还存活的对象拷贝到幸存者空间就可以了。当存活对象少的时候，GC算法的效率就会比较高。这时，算法就有很高的吞吐量。

至于Copy GC的更多内容，我们下期再讲。