algorithmgc-learning算法实现
algorithm, c, copying-or-marking, gc
Source
Edit
History

GC复制-标记清除

Catalogue
  1. 1. gc_init 初始化
  2. 2. gc阶段
    1. 2.1. 扫描Root
    2. 2.2. 执行拷贝和清除
    3. 2.3. 递增from-to空间
  3. 3. @gc_mark_or_copy 标记或拷贝
  4. 4. @gc_copy 复制阶段
    1. 4.1. 检查是否已拷贝过
    2. 4.2. 拷贝对象到to空间
    3. 4.3. 递归扫描child对象
  5. 5. @copy_reference 更新引用
  6. 6. @gc_sweep 执行清除
  7. 7. @remove_from 回收from空间

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

copying-or-marking是一种组合算法，结合了复制法和标记清除法来优化复制算法无法完整利用空间(通常来说只能利用1/2堆)的问题

程序默认初始化N个堆，那么有:

1
2
3
4
5
gc次数   from堆索引    to堆索引    标记清除堆范围
----------------------------------------------
1        heaps[0]      heaps[1]    heaps[2-(N-1)]           
2        heaps[1]      heaps[2]    heaps[3-(N-1)]
.....

这种组合方式既能结合了复制算法的优点，又能优化对应的缺点，目前来说空间利用率可以达到(N-1)/N,最多浪费1/N的空间

同时作为标记清除算法的对应堆也不用担心内存碎片的问题，因为每次gc后，from和to对换后进行自增，慢慢迭代后对所有堆进行了复制

复制算法部分和之前一样，gc标记清除部分也和之前一样，接下来分析如何组合应用

文件结构

1
2
3
4
- Makefile     构建文件
- copying.c    复制算法实现
- mark-sweep.c 标记清除算法实现
- test.c       测试用例

test:

1
2
> make
> ./gc

gc复制+标记清除算法主要流程如下:

  1. gc_init: 初始化N个堆，0作为to，1作为from
  2. gc_mark_or_copy: 搜索根，将所有可达对象进行拷贝或者标记
  3. copy_reference: 复制过后，需要更新之前的引用关系
  4. gc_sweep: 对其他堆执行标记清除算法
  5. 交换from,to, 进行递增

gc_init 初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void gc_init(size_t heap_size)
{
    //关闭扩充堆
    auto_grow = 0;
    for (size_t i = 0; i < gc_heaps_used; i++){
        //使用sbrk 向操作系统申请大内存块
        void* p = sbrk(heap_size + PTRSIZE);
        gc_heaps[i].slot = (Header *)ALIGN((size_t)p, PTRSIZE);
        gc_heaps[i].size = heap_size;
        gc_heaps[i].slot->size = heap_size;
        gc_heaps[i].slot->next_free = NULL;
        //默认情况下0 是给 to堆使用的  不需要挂载到 free_list 空闲链表上
        if(i) gc_free(gc_heaps[i].slot + 1);
    }
}

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

除了我们规定的0作为to堆外，其他都需要更新到空闲链表上

所有当调用gc_malloc()时，分配的内存既可能来自from，也可能来自mark堆

gc阶段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void  gc(void)
{
    printf("执行gc复制----\n");
    //每次gc前将 free指向 to的开头
    gc_heaps[to].slot->size = gc_heaps[to].size;
    free_p = gc_heaps[to].slot;

    //递归进行复制  从 from  => to
    for(int i = 0;i < root_used;i++){
        void* forwarded = gc_mark_or_copy(roots[i].ptr);
        *(Header**)roots[i].optr = forwarded;
        //将root 所有的执行换到 to上
        roots[i].ptr = forwarded;
    }
    copy_reference();
    //其他部分执行gc清除
    gc_sweep();
    //首先将free_p 指向的剩余空间  挂载到空闲链表上 
    //其实就是将原先to剩余的空间继续利用起来

    //如果没有剩余空间了则不进行操作
    if(free_p < ((void*)gc_heaps[to].slot + gc_heaps[to].size))
        gc_free((Header*)free_p+1);
    //在gc的时候 from已经全部复制到to堆
    //这个时候需要清空from堆，但是在此之前我们需要将free_list空闲指针还保留在from堆上的去除
    remove_from();
    /**
     * 清空 from 空间前:
     * 因为空闲链表 还指着from空间的，所以需要更新free_list 指针
     * 
     */
    memset(gc_heaps[from].slot,0,gc_heaps[from].size+HEADER_SIZE);

    //开始交换from 和to
    to = from;
    from = (from + 1)%10;
}

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

扫描Root

接着就是进行根的扫描，将所有可达对象执行gc_mark_or_copy,这个函数会进行判断

  1. 如果对象来自mark堆则不发生拷贝，直接标记即可
  2. 如果对象来自from堆则需要发生拷贝
1
2
3
4
void* forwarded = gc_mark_or_copy(roots[i].ptr);
*(Header**)roots[i].optr = forwarded;
//将root 所有的执行换到 to上
roots[i].ptr = forwarded;

如果只是进行了标记，forwarded就是本身

如果执行了拷贝，forwarded执向的是to空间的新对象地址

执行拷贝和清除

对发生了复制的空间进行引用更新

对标记清除区域执行清除

1
2
3
copy_reference();
//其他部分执行gc清除
gc_sweep();

递增from-to空间

1
2
3
4
5
6
7
8
9
10
11
remove_from();
/**
 * 清空 from 空间前:
 * 因为空闲链表 还指着from空间的，所以需要更新free_list 指针
 * 
 */
memset(gc_heaps[from].slot,0,gc_heaps[from].size+HEADER_SIZE);

//开始交换from 和to
to = from;
from = (from + 1)%10;
  1. gc执行完毕后,from区域作为新的to区域，需要清理from的依赖关系
  2. 最后resetfrom堆
  3. 开始交换from-to

@gc_mark_or_copy 标记或拷贝

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 对该对象进行标记 或拷贝
 * 并进行子对象标记 或拷贝
 * 返回to空间的 body
 * @param ptr
 */
void* gc_mark_or_copy(void* ptr)
{
    if(is_pointer_to_space(ptr,from))
        return gc_copy(ptr);   
    return gc_mark(ptr);
}

直接判断对象是否属于from堆来决定是拷贝还是标记

@gc_copy 复制阶段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void* gc_copy(void *ptr)
{
    Header  *hdr;
    GC_Heap *gh;
    if (!(gh = is_pointer_to_space(ptr,from))) return NULL;
    if (!(hdr = get_header(gh,ptr))) return NULL;
    assert(FL_TEST(hdr,FL_ALLOC));
    //没有复制过  0 
    if(!IS_COPIED(hdr)){
        //.....执行拷贝
        //从forwarding 指向的空间开始递归
        for (void* p = (void*)(forwarding + 1); p < (void*)NEXT_HEADER(forwarding); p++) {
            //对内存解引用，因为内存里面可能存放了内存的地址 也就是引用，需要进行引用的递归标记
            //递归进行 引用的拷贝
            gc_mark_or_copy(*(void **)p);
        }
        //返回body
        return forwarding + 1;
    }
    //forwarding 是带有header头部的，返回body即可
    return hdr->forwarding+1;
}

和之前一样，只有在对child子对象递归判断时需要调用gc_mark_or_copy来决定是复制还是标记

检查是否已拷贝过

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

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

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

拷贝对象到to空间

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

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

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

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

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

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

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

递归扫描child对象

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

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

@copy_reference 更新引用

和复制法一样

@gc_sweep 执行清除

在root扫描阶段，除了会复制from堆上的内存外，其他堆都需要执行标记

对图中除from,to以外的所有未标记的内存进行回收，已标记的置为未标记等待下次gc在进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//copying-or-mark/mark-sweep.c

/**
 * 清除 未标记内存 进行回收利用
 */
void     gc_sweep(void)
{
    size_t i;
    Header *p, *pend, *pnext;

    //遍历所有的堆内存
    //因为所有的内存都从堆里申请，所以需要遍历堆找出待回收的内存
    for (i = 0; i < gc_heaps_used; i++) {
        //to 和 from堆不需要进行清除
        if(i == from || i == to) continue;
        //pend 堆内存结束为止
        pend = (Header *)(((size_t)gc_heaps[i].slot) + gc_heaps[i].size);
        //堆的起始为止 因为堆的内存可能被分成了很多份，所以需要遍历该堆的内存
        for (p = gc_heaps[i].slot; p < pend; p = NEXT_HEADER(p)) {
            //1. 是否已分配
            //2. 是否标记
            //3. 未标记回收
        }
    }
}
  1. 在清除阶段过滤掉from,to堆,if(i == from || i == to) continue;
  2. 接下来和之前一样,找到未标记且分配过的内存，进行回收

@remove_from 回收from空间

这里主要指的是在from已经完全拷贝到to空间之后，空闲链表free_list依然有空闲的节点指向from

这个时候就是找出free_list列表中还存留的from指针，找到后剔除