GC复制

Catalogue

1. 1. gc_init 初始化
2. 2. gc阶段
3. 3. @gc_copy 复制阶段
   1. 3.1. 检查是否已拷贝过
   2. 3.2. 拷贝对象到to空间
   3. 3.3. 递归扫描child对象
4. 4. @copy_reference 更新引用
   1. 4.1. 引用更新

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

复制算法，安全解决了标记清除算法中内存碎片的问题，每次执行gc时会将存活的对象全部拷贝到新的堆上,并且紧挨着排列

缺点是需要空出一个堆来作为存放区，带来的结果就是不能充分利用堆，在当前的实现中，总共初始化两个堆from,to堆，各占1/2

文件结构

- Makefile     构建文件
- copying.c    主要代码实现
- test.c       测试用例

test:

> make
> ./gc

gc复制算法主要流程如下:

1. gc_init: 这里固定生成2个堆,from，to
2. gc_copy: 搜索根，将所有可达对象全部拷贝到to堆
3. copy_reference: 复制过后，需要更新之前的引用关系

gc_init 初始化

void gc_init(size_t req_size)
{
    auto_gc   = 1;
    //关闭自动扩充堆
    auto_grow = 0;
    //使用sbrk 向操作系统申请大内存块
    void* from_p = sbrk(req_size + PTRSIZE );
    from.slot  = (Header *)ALIGN((size_t)from_p, PTRSIZE);
    from.slot->next_free = NULL;
    from.slot->size = req_size;
    from.size       = req_size;
    gc_free((void*)(from.slot + 1));
    DEBUG(printf("扩堆内存:%ld ptr:%p\n",req_size,from_p));

    //使用sbrk 向操作系统申请大内存块
    void* to_p = sbrk(req_size + PTRSIZE + HEADER_SIZE);
    to.slot  = (Header *)ALIGN((size_t)to_p, PTRSIZE);
    to.slot->next_free = NULL;
    to.slot->size = req_size;
    to.size = req_size;
}

auto_grow = 0 关闭自动扩充堆，为了聚焦于算法本身，我们只允许存在两个堆

接下来就是剩下两个堆，分别作为from,to堆使用

1. from作为内存分配的堆
2. to 作为每次gc后新的from堆(gc执行完后会swap(from,to))

gc阶段

void  gc(void)
{
    //每次gc前jiang free指向 to的开头
    to.slot->size = to.size;
    free_p = to.slot;

    //递归进行复制  从 from  => to
    for(int i = 0;i < root_used;i++){
        void* forwarded = gc_copy(roots[i].ptr);
        *(Header**)roots[i].optr = forwarded;
        //将root 所有的执行换到 to上
        roots[i].ptr = forwarded;
    }
    copy_reference();

    //清空 from
    memset(from.slot,0,from.size+HEADER_SIZE);

    //开始交换from 和to
    Header* tmp = from.slot;
    from.slot = to.slot;
    to.slot = tmp;
    //将空闲链表放到 to的最后一个索引
    free_list = free_p;
}

每次执行gc前，都会初始一个free_p指针，指向to堆的首地址，每发生一次拷贝，指针往后移，指向空余空间

接着就是进行根的扫描，将所有可达对象执行gc_copy拷贝到to堆，也就是当前free_p指向的空间

注意这里*(Header**)roots[i].optr = forwarded就是root篇讲的关于引用地址更新的问题

拷贝完成后,接着就是更新引用

最后就是交换from和to空间，之前的to空间继续作为from来使用

@gc_copy 复制阶段

复制阶段分为几个步骤:

1. 校验指针是否合法并获取对象头
2. 检查是否已经拷贝过
3. 从to空间分配新的空间用于存储待复制的对象
4. 递归扫描child引用对象

void* gc_copy(void * ptr)
{
    Header *hdr;

    if (!(hdr = get_header_by_from(ptr))) return NULL;
}

检查指针是否合法，并返回对象头

检查是否已拷贝过

//没有复制过  0
if(!IS_COPIED(hdr))
{
}
//forwarding 是带有header头部的，返回body即可
return hdr->forwarding+1;

通过IS_COPIED(hdr)宏来判断标志位是否设置，是否已经拷贝过了

拷贝后，都需要返回拷贝后的指针

拷贝对象到to空间

上面步骤如果没有拷贝过，则需要进行拷贝

1. 从to空间分配一个空闲地址

   //计算复制后的指针
   Header *forwarding = (Header*)free_p;
   //在准备分配前的总空间
   size_t total = forwarding->size;

2. 进行拷贝,并更新原有对象标志位为COPIED

   //分配一份内存 将源对象拷贝过来
   memcpy(forwarding, hdr, hdr->size);
   //标记为已拷贝
   FL_SET(hdr,FL_COPIED);
   hdr->flags = 1;

3. 更新to空间的下一个空闲指针

   //free 指向下一个 body
   free_p += hdr->size;
   //free_p 执行的剩余空间需要时刻维护着
   ((Header*)free_p)->size = total - hdr->size;

递归扫描child对象

当前对象拷贝过后，还需要对其child子对象引用进行拷贝，直接进行内存扫描即可

//从forwarding 指向的空间开始递归
for (void* p = (void*)(forwarding+1); p < (void*)NEXT_HEADER(forwarding); p++) {
    //对内存解引用，因为内存里面可能存放了内存的地址 也就是引用，需要进行引用的递归标记
    //递归进行 引用的拷贝
    gc_copy(*(void **)p);
}

@copy_reference 更新引用

上一步骤执行完拷贝以及递归拷贝子引用后，空间结构应该是这样

可以看到A,B被root直接引用，被拷贝到了to空间，而C被A引用，也同时被拷贝过去了

而且复制过后的空间，引用对象会连续排列在一起，如A,C,这同时也是复制算法的一个优点，加快缓存访问速度

引用更新

上面讲了拷贝过后的A任然指向了From的C，需要更正这一点，完全复制依赖关系

void copy_reference()
{
    //遍历所有对象
    for(int i = 0; i < root_used; i ++)
    {
        void* start =  roots[i].ptr;
        void* end   =  (void*)NEXT_HEADER(CURRENT_HEADER(start));

        //可能申请的内存 里面又包含了其他内存
        for (void *p = start; p < end;  p++) {

            Header* hdr;
            //解引用 如果该内存依然是指向的from，且有forwarding 则需要改了
            void *ptr = *(void**)p;
            if (!(hdr = get_header_by_from(ptr))) {
                continue;
            }
            if(hdr->forwarding){
                printf("拷贝引用 hdr:%p forwarding:%p\n",hdr,hdr->forwarding);
                *(Header**)p = hdr->forwarding + 1;
                break;
            }

        }
    }
}

1. 遍历所有的Root，判断是对象是否发生过拷贝if(hdr->forwarding)
2. 将拷贝的引用更新*(Header**)p = hdr->forwarding + 1