压缩算法-lisp2

Catalogue

1. 1. @gc_init 初始化
2. 2. @gc 阶段
3. 3. @gc_mark 标记阶段
4. 4. @set_forwarding_ptr 计算移动地址
5. 5. @adjust_ptr 更新引用
6. 6. @move_obj 移动对象

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

压缩算法,也是一种充分利用空间解决内存碎片的算法。相较于复制称为移动更为恰当,因为压缩算法中不会将对象从from搬到to,仅限于在当前堆内活动，将所有活动对象去全部移动到头部进行压缩

压缩算法相比复制算法解决了内存碎片和无法充分利用堆的问题,但也有新的问题产生，当前压缩算法的实现:lisp2:

• 在gc过程中需要遍历三次堆，堆内存较大情况下比较耗费时间
• 不能像gc复制算法那样将具有引用关系的对象就近排列加快访问速度

主要流程如下

1. gc_mark: 标记阶段，扫描root对活动对象进行标记
2. set_forwarding_ptr: 第一次遍历堆-计算活动对象移动后的地址
3. adjust_ptr: 第二次遍历堆-更新引用关系，所有的子类都要执行步骤2中计算出来的新地址
4. move_obj: 第三次遍历堆-移动对象执行压缩

@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 阶段

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

    //设置forwarding指针
    set_forwarding_ptr();
    //调整指针
    adjust_ptr();
    //移动对象
    move_obj();
}

1. 遍历root,对所有可达对象以及子对象进行标记
2. 计算活动对象将要移动后的目的地址
3. 更新活动对象的子对象指向新的地址
4. 移动所有活动对象到头部，执行压缩

@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进行递归引用标记

@set_forwarding_ptr 计算移动地址

主要是遍历堆，然后计算活动对象应该被移动到的目的地址

void     set_forwarding_ptr(void)
{
    size_t i;
    Header *p, *pend, *pnext ,*new_obj;

    //遍历所有的堆内存
    //因为所有的内存都从堆里申请，所以需要遍历堆找出待回收的内存
    for (i = 0; i < gc_heaps_used; i++) {
        //pend 堆内存结束为止
        pend = (Header *)(((size_t)gc_heaps[i].slot) + gc_heaps[i].size);
        p = gc_heaps[i].slot;
        new_obj = gc_heaps[i].slot;
        //堆的起始为止 因为堆的内存可能被分成了很多份，所以需要遍历该堆的内存
        for (; p < pend; p = NEXT_HEADER(p))
        {
            //查看该堆是否已经被使用
            if (FL_TEST(p, FL_ALLOC)) {
                //查看该堆是否被标记过
                if (FL_TEST(p, FL_MARK)) {
                    p->forwarding = new_obj;
                    //new_obj 继续下移 p个空间大小
                    new_obj = (void*)new_obj + p->size;
                }
            }
        }
    }
}

主要是设置双指针p,new_obj,同时从头部开始遍历，计算目的地址

1. p指针去寻找活动对象
2. 找到活动对象后将当前new_obj地址记下，并向后移动n字节

@adjust_ptr 更新引用

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所指向的地址

接下来就是遍历堆，这已经是第二次堆的遍历了，更新所有引用

@move_obj 移动对象

最后就简单了，第三次堆遍历直接将所有对象拷贝到目的地址即可

new_obj = p->forwarding;
memcpy(new_obj, p, p->size);
FL_UNSET(new_obj,FL_MARK);
//空闲链表下移
free_p = (void*)free_p + new_obj->size;
total -=  new_obj->size;

//这个时候free_p 后面就是空闲列表了
free_list = free_p;
//total 需要单独计算剩余空间
free_list->size = total;
free_list->next_free = NULL;
//方便测试 把空闲空间都清空
memset(free_list + 1,0,total);

这里要注意下,当前free_p的后面一定是空闲空间，前面一定是被压缩后的活动对象的空间，直接和free_p即可

顺带同时清除垃圾空间,到此就全部完成了gc