分代回收算法

定义

给对象增加年龄属性，针对不同年龄的对象采用不同的算法。把刚生成的对象称为新生代对象，到达一定年龄的对象则称为老年代对象。

堆结构

堆总共需要利用4个空间，分别是生成空间、2 个大小相等的幸存空间以及老年代空间，并分别用 survivor1_ start、old_start 4个变量引用它们的开头。我们将生成空间和幸存空间合称为新生代空间。新生代对象会被分配到新生代空间，老年代对象则会被分配到老 年代空间里。此外我们准备出一个和堆不同的数组，称为记录集(remembered set)，设为 $rs。

分代回收示意图

需要注意的是，在新生代GC时，必须考虑到从老年代空间到新生代空间的引用。

记录集

记录集被用于高效地寻找从老年代对象到新生代对象的引用。具体来说，在新生代 GC 时将记录集看成根(像根一样的东西)，并进行搜索，以发现指向新生代空间的指针。

• 记录了引用的目标对象的记录集

  
  

• 记录了发出引用的对象的记录集

  
  

写入屏障

在分代垃圾回收中，为了将老年代对象记录到记录集里，我们利用写入屏障(write barrier)。在 应用程序更新对象间的指针的操作中，写入屏障是不可或缺的。

// $old_start 老年代起始地址
// obj 发出引用的对象
// new_obj 指针更新后成为引用目标的对象
write_barrier() {
    // 发出引用的对象是不是老年代对象
    // 指针更新后的引用的目标对象是不是新生代对象
    // 发出引用的对象是否还没有被记录到记录集中
    if(obj >= $old_start && new_obj < $old_start && obj.remembered == FALSE) {
        // $rs_index 是用于新记录对象的索引
        $rs[$rs_index] = obj;
        $rs_index++;
        obj.remembered = TRUE;
    }
    // 更新指针
    *field = new_obj;
}

对象结构

对象的头部中除了包含对象的种类和大小之外，还包含下面三种信息：
- 对象的年龄(age)
- 已经复制完毕的标志(forwarded)
- 已经向记录集记录完毕的标志(remembered)

分配

new_obj(size) {
    // 检查生成空间中是否存在 size 大小的分块
    if ($new_free + size >= $survivor1_start) {
        minor_gc();
        if ($new_free + size >= $survivor1_start) {
            allocation_fail();
        }
    }
    obj = $new_free;
    $new_free += size;
    // 对象初始化
    obj.age = 0;
    obj.forwarded = FALSE;
    obj.remembered = FALSE;
    obj.size = size;
    return obj;
}

新生代GC

copy(obj) {
    // 检测是否复制完毕
    if (obj.forwarded == FALSE) {
        // 检测对象的年龄
        if (obj.age < AGE_MAX) {
            // 复制到幸存空间
            copy_data($to_survivor_free, obj, obj.size);
            obj.forwarded = TRUE;
            obj.forwarding = $to_survivor_free;
            $to_survivor_free.age++;
            $to_survivor_free += obj.size;
            // 复制子对象
            for (child : children(obj)) {
                *child = copy(*child);
            }
        } else {
            // 晋升到老年代
            promote(obj);
        }
    }
    return obj.forwarding;
}

promote(obj) {
    // 老年代分配空间
    new_obj = allocate_in_old(obj);
    // 若失败，则进行老年代GC
    if (new_obj == NULL) {
        major_gc();
        new_obj = allocate_in_old(obj);
        if (new_obj == NULL) {
            allocation_fail();
        }
    }
    obj.forwarding = new_obj;
    obj.forwarded = TRUE;
    for (child : children(new_obj)) {
        // 检测obj 是否有指向新生代对象的指针
        if (*child < $old_start) {
            // 将new_obj添加到记录集中
            $rs[$rs_index] = new_obj;
            $rs_index++;
            new_obj.remembered = TRUE;
            return;
        }
    }
}

minor_gc() {
    // 分配To幸存空间的分块
    $to_survivor_free = $to_survivor_start;
    // 复制能从根找到的新生代对象
    for (r : $roots) {
        if (*r < $old_start) {
            *r = copy(*r);
        }
    }
    // 搜索记录集中记录的对象 $rs[i]，执行子对象的复制操作
    i=0
    while (i < $rs_index) {
        has_new_obj = FALSE
        for (child : children($rs[i])) {
            if (*child < $old_start) {
                *child = copy(*child);
                // 检测对象保留在新生代，还是晋升到老年代
                if (*child < $old_start) {
                    has_new_obj = TRUE;
                }
            }
        }
        // 若为FALSE，则老年代对象 $rs[i] 就已经没有指向新生代空间的引用了
        if (has_new_obj == FALSE) {
            // 将这个元素从记录集里删除
            $rs[i].remembered = FALSE;
            $rs_index--;
            swap($rs[i], $rs[$rs_index]);
        } else {
            i++;
        }
    }
    swap($from_survivor_start, $to_survivor_start);
}