GC算法实践(三) 标记-压缩算法

本文将实现垃圾回收算法中的标记-压缩算法。

1.标记-压缩算法简介

标记-压缩算法的基本思路：

1. 标记阶段。该阶段与标记-清除算法中的标记算法一样。

   遍历根对象及其引用的对象。假设每个对象都有个标记位flag，对根对象集合中的每个根对象，从根对象出发，对可以访问到的每个对象的标记位flag设为1（活动对象）。

2. 压缩阶段。该阶段分3步，依次是：

   1. 计算当前活动堆中活动对象移动后的地址。该步骤需要从堆的开始遍历堆，对每个标记为活动的对象，计算其移动后的地址并记住。仍然可以把堆当做一个链表来遍历。

   2. 更新到活动对象的引用。该步骤是从根对象出发，遍历根对象所引用到的每个对象，更新根对象到它的引用。即：如果根对象的某个字段引用了一个活动对象，那么要把该字段的值更新为它所引用的活动对象移动后的地址。

      若对象obj有字段b，该字段当前引用的对象的地址为为B，B移动后的地址为newB，那么需要执行如下操作：

      obj->b = newB

   3. 移动活动对象。该步骤需要遍历堆，从堆的开始寻找活动对象，然后往堆的开始地址方向移动，让活动对象都挨在一起存放在堆一侧，空闲空间集中在堆的另一侧，以达到压缩的目的。

标记-压缩算法的优点是垃圾回收在当前活动堆中进行，不需要借助另外的堆，充分利用了内存空间。缺点是压缩阶段需要2次遍历堆，1次遍历根对象及其引用的对象，比较耗时。

压缩阶段的前两个步骤涉及到对象移动后的地址，我们需要记住每个活动对象移动前后地址的对应关系。可以借用一张表来解决，如：

移动前的地址	移动后的地址
0x00250FF8	0x00250FE4
0x00251010	0x00250FFC
0x00251040	0x00251018

表格的创建是在第一步完成的，第二步需要根据移动前的地址从表格中查找移动后的地址。该方法的缺点是需要多次搜索表格，效率低。

可以把移动后的地址作为对象的一个字段，这样就可以直接获取活动对象移动后的地址。即把对象的结构改为如下：

typedef struct _Object {
    char flag;
    ushort length;
    char* new_addr; // 移动后的地址
    char* fields;
}Object;

缺点就是每个对象多占用了4个字节的空间（对于32位机器）。本文中采用该方法来查找移动后的地址。

以下是该算法操作前后，当前活动堆中的对象分布示意图

2.算法实现

标记算法此处省略，参考上篇文章。标记步骤中会把活动对象的flag字段设为1。

2.1 计算堆中活动对象移动后的地址

参考如下代码：

void _compute_new_addr(Heap *heap) {
    char *tmp_addr = heap->start_addr;
    char *new_addr = tmp_addr;
    Object *obj;
    int obj_size;

    while(tmp_addr < heap->free_addr) {
        obj = (Object*)tmp_addr;
        obj_size = OBJ_SIZE(obj);
        if (obj->flag == 1) { // object is active
            obj->new_addr = new_addr;
            new_addr += obj_size;
        }
        tmp_addr += obj_size;
    }
}
void compute_new_addr() {
    _compute_new_addr(cur_heap);
}

基本思路是把堆当做一个链表来遍历，遍历的范围是堆的当前已用空间，即start_addr至free_addr之间的对象。其中变量new_addr是下一个活动对象移动后的地址，只有遇到活动对象(flag=1)才能更新该变量的值。

2.2更新到活动对象的引用

Object* update_ref_one(Object *obj) {
    Object *sub_obj;
    int index;

    // update each sub object
    for(index=1; index<obj->length; index++) {
        sub_obj = OBJ_GET_OBJ(obj, index);
        if (NULL != sub_obj && sub_obj->new_addr != NULL) {
            OBJ_SET_OBJ(obj, index, (Object*)(sub_obj->new_addr));
            printf("object[%d],fields[%d]=%p <= %p\n", OBJ_GET_INT(obj,0), index, sub_obj, sub_obj->new_addr);
            update_ref_one(sub_obj);
        }
    }

    return (Object*)(obj->new_addr);
}
void update_ref(Object *root[], int len) {
    int i;
    for(i=0; i<len; i++) {
        root[i] = update_ref_one(root[i]);
    }   
}

遍历根对象及其所引用的对象，思路跟标记对象的一样，又要用到递归。

更新到活动对象的引用：

OBJ_SET_OBJ(obj, index, (Object*)(sub_obj->new_addr));

记得要更新根对象集合中的引用：

root[i] = update_ref_one(root[i]);

2.3 移动活动对象

void _move_object(Heap *heap) {
    char *tmp_addr = heap->start_addr;
    char *new_addr;
    Object *obj;
    int obj_size;

    while(tmp_addr < heap->free_addr) {
        obj = (Object*)tmp_addr;
        obj_size = OBJ_SIZE(obj);
        if (obj->flag == 1) { // object is active
            obj->flag = 0;
            if (obj != obj->new_addr) { // need to move 
                new_addr = obj->new_addr;
                obj->new_addr = NULL;

                printf("move: object[%d]%p => %p, size=%d\n", OBJ_GET_INT(obj,0), obj, new_addr, obj_size);

                memmove(new_addr, (char*)obj, obj_size);
                OBJ_SET_FIELDS((Object*)new_addr, new_addr);
            } else {
                obj->new_addr = NULL;
            }
        }
        tmp_addr += obj_size;
    }

    heap->free_addr = new_addr + obj_size;
}
void move_object() {
    _move_object(cur_heap);
}

移动对象前先把对象的flag和new_addr字段恢复为初始值：

obj->flag = 0;
obj->new_addr = NULL;

然后用memmove函数进行内存拷贝：

OBJ_SET_FIELDS((Object*)new_addr, new_addr);

移动完对象后，这个操作也很重要：

OBJ_SET_FIELDS((Object*)new_addr, new_addr);

因为Object的fields字段也是引用。

考虑到有的对象实际上不需要移动，移动前我们加了个判断：

if (obj != obj->new_addr) {

最后记得更新堆的可用空间首地址，即heap的free_addr字段：

heap->free_addr = new_addr + obj_size;

3.测试

3.1 构建测试场景

void test_alloc_memory2() {
    Object *objects[8];
    int obj_len[8] = {3,2,4,2,3,4,2,3};
    int i;

    for(i=0; i<8; i++) {
        objects[i] = new_object(obj_len[i]);
        OBJ_SET_INT(objects[i], 0, i);
    }

    OBJ_SET_OBJ(objects[1], 1, objects[4]); // objects[1]->objects[4]
    OBJ_SET_OBJ(objects[0], 1, objects[1]); // objects[0]->objects[1]
    OBJ_SET_OBJ(objects[0], 2, objects[5]); // objects[0]->objects[5]
    OBJ_SET_OBJ(objects[2], 1, objects[7]); // objects[2]->objects[7]

    root[0] = objects[0];
    root[1] = objects[2]; // objects[3] and objects[6] are garbage
}

创建了8个大小不同的对象，设置其中两个对象为不可达的对象（即垃圾）。

创建对象后，堆中对象及其引用关系示意图如下：

3.2 测试

测试代码如下：

int main() {
    init_heap();

    printf("after alloc...");
    test_alloc_memory2();
    dump_heaps();

    printf("after mark...");
    mark_objects(root, 2);
    dump_heaps();

    printf("after compute...\n"); 
    compute_new_addr();
    dump_heaps();

    printf("update_ref...\n");
    update_ref(root, 2);

    printf("\nmove object...\n");
    move_object();

    printf("\nafter move...\n");
    dump_heaps();

    dump_active_objects(root, 2);
    printf("\n");

    return 0;
}

3.3 测试输出与结果

标记后 堆的内容如下：

计算堆中活动对象移动后的地址后 堆的内容如下：

更新到活动对象的引用 过程的输出：

object[2],fields[1]=00251040 <= 00251018的含义为：

对象object[2]中索引为1的字段原来的值是 00251040，把该字段的值设为00251018，即让它指向00251018`这个地址。

移动活动对象过程的输出：

object[7]00251040 => 00251018, size=24的含义为：

把首地址为00251040的对象object[7]，复制到地址00251018，复制的字节数为24，该对象占用24个字节。

移动之后堆的内容如下：

当前堆中只有活动对象，对象能够正常访问，且保持了原有的引用关系，说明代码运行OK。