压缩算法-two-finger

Catalogue

1. 1. @gc_init 初始化
2. 2. @gc 阶段
3. 3. @gc_mark 标记阶段
4. 4. @move_obj 移动压缩
   1. 4.1. 逻辑实现
5. 5. @adjust_ptr 更新引用

github: https://github.com/brewlin/garbage-collect

two-finger相比lisp2而言优化了gc效率，只需要执行两次堆的遍历，但同时也多了限制条件,那就是需要保证每个对象的内存块大小一致

通过固定块大小，就可以去除之前set_forwarding_ptr计算移动地址的步骤，因为内存块都是一样的，所以直接移动即可

主要流程如下

1. gc_mark: 标记阶段，扫描root对活动对象进行标记
2. move: 第一次遍历堆-双端同时遍历开始移动拷贝
3. adjust_ptr: 第二次遍历堆-更新引用关系

two-finger和lisp2的区别:

• two-finger 只需要2次堆遍历，而lisp2需要三次
• two-finger 规定每个对象大小必须一致, lisp2无要求
• two-finger 不需要移动全部对象(注意这点区别),可以用填空来描述这一行为

@gc_init 初始化

void gc_init(size_t heap_size)
{
    //关闭自动扩充堆
    auto_grow = 0;

    gc_heaps_used = 1;
    //使用sbrk 向操作系统申请大内存块
    void* p = sbrk(heap_size + PTRSIZE);
    gc_heaps[0].slot = (Header *)ALIGN((size_t)p, PTRSIZE);
    gc_heaps[0].size = heap_size;
    gc_heaps[0].slot->size = heap_size;
    gc_heaps[0].slot->next_free = NULL;
    //将堆初始化到free_list 链表上
    gc_free(gc_heaps[0].slot + 1);
}

为了聚焦算法实现本身，这里只固定申请一个堆，且关闭自动扩充堆auto_grow = 0

@gc 阶段

void  gc(void)
{
    printf("start gc()\n");
    //gc 递归标记
    for(int i = 0;i < root_used;i++)
        gc_mark(roots[i].ptr);

    //移动对象
    move_obj();
    //调整指针
    adjust_ptr();
}

1. 遍历root,对所有可达对象以及子对象进行标记
2. 直接移动对象即可，因为每个对象大小都一致，直接移动等分距离即可
3. 更新活动对象的子对象指向新的地址

@gc_mark 标记阶段

扫描root根，这里是模拟的root，真实的root可以参考gc-try实现的扫描系统栈

for(int i = 0;i < root_used;i++)
    gc_mark(roots[i].ptr);

void* gc_mark(void *ptr){
    //检查指针是否合法

    /* marking */
    FL_SET(hdr, FL_MARK);
    for (void* p = ptr; p < (void*)NEXT_HEADER(hdr); p++) {
        gc_mark(*(void **)p);
    }
    return ptr;
}

常规操作，对当前指针进行检查，然后扫描当前指针执行的内存段，对child进行递归引用标记

@move_obj 移动压缩

注意和lisp的移动的区别，这里采用两个指针空闲指针和live指针

• 空闲指针从头遍历，总是去寻找空位
• live指针从尾遍历, 总是去寻找存活对象
• 当两个指针相遇的时候结束压缩

两个指针就像是两个手指一样，所以取名two-finger

逻辑实现

void move_obj()
{
    free_list = gc_heaps[i].slot;
    total = gc_heaps[i].size;
    while (true) {
        //遍历到第一个非标记的地方，也就是空闲区
        while (FL_TEST(free_list, FL_ALLOC) && FL_TEST(free_list, FL_MARK) && free_list < live)
        {
            FL_UNSET(free_list,FL_MARK);
            total -= free_list->size;
            free_list = NEXT_HEADER(free_list);
        }
        //遍历到第一个被标记了的地方，这样就会将这个地方拷贝到上面的空闲区
        while (!FL_TEST(live, FL_MARK) && live > gc_heaps[i].slot)
            //TODO:因为反向遍历的时候 没有域且内存非等分，所以不能通过 -= mem_size 来遍历
            live = (Header *) ((void *) live - 1);
        //进行拷贝
        if (free_list < live)
        {
            FL_UNSET(live, FL_MARK);
            memcpy(free_list, live, live->size);
            live->forwarding = free_list;
            total -= live->size;
        } else {
            break;
        }
    }

    free_list->size = total;
    free_list->next_free = NULL;
    //方便测试 把空闲空间都清空
    memset(free_list + 1,0,total);

}

采用2层循环，三个循环来实现压缩

1. 外层循环 在两个指针相遇时结束，压缩也结束了
2. 内层第一个循环，总是去寻找第一个空位
3. 内层第二个循环，总是从尾部反向遍历寻找存活对象

核心就是每个对象大小都是一样的，所以在进行填补的时候直接拷贝即可

@adjust_ptr 更新引用

和lisp2算法一样，更新子对象的引用

1. 初始时block3引用了block4,且block3应该移动到block1处，block4应该移动到block2处
2. 更新后block3不再引用block4而是将要移动后的block2的位置

void adjust_ptr()
{
    //遍历所有对象
    for(int i = 0; i < root_used; i ++){
        Header* forwarding =  CURRENT_HEADER(roots[i].ptr)->forwarding;
        roots[i].ptr = forwarding+1;
        *(Header**)roots[i].optr = forwarding+1;
    }

    //堆的起始为止 因为堆的内存可能被分成了很多份，所以需要遍历该堆的内存
    for (p = gc_heaps[i].slot; p < pend; p = NEXT_HEADER(p))
    {
        //可能申请的内存 里面又包含了其他内存
        for (void* obj = p+1; obj < (void*)NEXT_HEADER(p); obj++)
        {
            //正确找到了 child 引用
            GC_Heap *gh;
            Header  *hdr;
            if (!(gh = is_pointer_to_heap(*(void**)obj))) continue;
            if((hdr = get_header(gh,*(void**)obj))) {
                *(Header **) obj = hdr->forwarding + 1; //更新引用
            }
        }
    }

}

先更新root，因为所有活动对象的内存都发生了移动，需要更新栈变量存储的地址，也就是更新root所指向的地址