algorithmgc-learning算法实现
algorithm, c, gc, tri-color-mark
Source
Edit
History

三色标记清除

Catalogue
  1. 1. @gc 阶段
  2. 2. @stack 存储灰色对象的栈
  3. 3. @root_scan_phase 根部扫描阶段
  4. 4. @mark_phase 标记阶段
  5. 5. @sweep_phase 清除阶段
  6. 6. 关于gc安全的两点
    1. 6.1. 写入屏障
    2. 6.2. 分配安全

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

当前实现的三色标记是一种增量式-标记清除算法,解决了标记清除算法中stw过长的问题，增量迭代演进式回收,而不是一次性标记和回收所有对象，优化了stw暂停时间过长的问题

  • 白色: 未搜索过的对象
  • 灰色: 正在搜索的对象，其实就是child引用没有扫描完的对象
  • 黑色: 搜索完成后的对象

当多个阶段全部标记完成后任然是白色的对象就是垃圾对象，应该回收

既然是增量，说明标记阶段每次只执行一部分，清除阶段也只执行一部分

  • gc_phase: 表示当前所在阶段
  • max_mark：每阶段需要标记的灰色对象的最大数量
  • mar_sweep: 每阶段需要清除的白色垃圾对象的最大数量

gc过程主要分为如下流程

  1. 标记阶段: 扫描根,进行多阶段标记，每次发现的白色对象转换为灰色对象丢入栈内
  2. 清除阶段: 多阶段清除垃圾，只清除白色垃圾(未标记的)

在增量gc多个阶段之间有新的对象产生、更新等，会涉及到安全问题，需要有个写入屏障

@gc 阶段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//tri-color.c

void  gc(void)
{
    printf("执行gc\n");
    switch(gc_phase){
        case GC_ROOT_SCAN:
            root_scan_phase();
            return;
        case GC_MARK:
            mark_phase();
            return;
        case GC_SWEEP:
            sweep_phase();
    }
}

每次执行gc都会继续执行之前中断的阶段，如

  • 根扫描
  • 标记阶段
  • 清除阶段

完全执行完清除阶段后，下一阶段又回到根扫描上

@stack 存储灰色对象的栈

实现了一个简单的栈，用于存储灰色对象，每次扫描到存活对象后直接入栈，转为灰色对象

在标记阶段会递归标记其子对象，完成后出栈，转为黑色对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//stack.h

typedef struct link_list
{
    void*             value;
    struct link_list *next;
}Link;

typedef struct stack_header
{
    Link* head;
    Link* tail;
}Stack;

void push(Stack* stk,void* v);
int empty(Stack* stk);
void* pop(Stack* stk);
  • push 入栈
  • pop 出栈
  • empty 是否为空

@root_scan_phase 根部扫描阶段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void root_scan_phase()
{
    //垃圾回收前 先从 root 开始 进行递归标记
    for(int i = 0;i < root_used;i++)
    {
        void* ptr = roots[i].ptr;
        GC_Heap *gh;
        Header *hdr;
        if (!(gh = is_pointer_to_heap(ptr))) continue;
        if (!(hdr = get_header(gh, ptr)))    continue;
        if (!FL_TEST(hdr, FL_ALLOC))         continue;
        if (FL_TEST(hdr, FL_MARK))           continue;

        //标记为灰色 并入栈
        FL_SET(hdr, FL_MARK);
        push(&stack,ptr);
    }
    gc_phase = GC_MARK;

}

当前是直接将所有存活对象作为灰色对象推入标记栈中,结束了扫描阶段

但是在标记阶段其实还是会进行多次根扫描，因为多个阶段之间可能发生了更新，新增对象等，需要多次进行扫描

第一次gc的时候这里扫描完就可以直接进入下一阶段了

@mark_phase 标记阶段

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
//tri-color.c

void mark_phase()
{
    //1 全部将灰色标记完了在进行下一个清除阶段
    //2 未全部标记完则继续进行标记

    int scan_root = 0;
    for (int i = 0; i < max_mark; ++i) {
        //如果为空就继续去扫描一下root  看看在gc休息期间是否有新的没有进行标记
        if(empty(&stack)){
            //如果扫描过了root，但是依然没有新增灰色对象 则结束标记
            if(scan_root >= 1) {
                gc_phase = GC_SWEEP;
                break;
            }
            root_scan_phase();
            scan_root++;
            continue;
        }
        void* obj = pop(&stack);
        Header* hdr = CURRENT_HEADER(obj);
        //递归对child 进行标记
        for (void* p = obj; p < (void*)NEXT_HEADER(hdr); p++) {
            //对内存解引用，因为内存里面可能存放了内存的地址 也就是引用，需要进行引用的递归标记
            gc_mark(*(void **)p);
        }
    }
    //所有gc扫描完以后 只有空栈的话 说明标记完毕 需要进行清扫
    if(empty(&stack)){
        gc_phase = GC_SWEEP;
    }

}

scan_root标志用于在标记栈为空的时候，悄悄再去扫描一下根，看看是否有新的活动对象产生

max_mark标志用于指示每次只标记固定数量的灰色对象(栈里的都是灰色对象)

1
2
3
4
for (void* p = obj; p < (void*)NEXT_HEADER(hdr); p++) {
    //对内存解引用，因为内存里面可能存放了内存的地址 也就是引用，需要进行引用的递归标记
    gc_mark(*(void **)p);
}

递归扫描标记子对象(和标记清除章节一致)

最后判断如果灰色对象标记完了，则进入下一阶段GC_SWEEP

1
2
3
if(empty(&stack)){
    gc_phase = GC_SWEEP;
}

@sweep_phase 清除阶段

也是多阶段清除，每次只清除固定max_sweep个白色垃圾，并记下索引，下次继续清除

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
//tri-color.c
void sweep_phase(void)
{
    size_t i;
    Header *p, *pend, *pnext;

    //遍历所有的堆内存
    //因为所有的内存都从堆里申请，所以需要遍历堆找出待回收的内存
    for (i = sweeping; i < gc_heaps_used && i < max_sweep + sweeping; i++) {
        //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)) {
            //查看该堆是否已经被使用
            if (FL_TEST(p, FL_ALLOC)) {
                //查看该堆是否被标记过
                if (FL_TEST(p, FL_MARK)) {
                    DEBUG(printf("解除标记 : %p\n", p));
                    //取消标记，等待下次来回收，如果在下次回收前
                    //1. 下次回收前发现该内存又被重新访问了，则不需要清除
                    //2. 下次回收前发现该内存没有被访问过，所以需要清除
                    FL_UNSET(p, FL_MARK);
                }else {
                    DEBUG(printf("清除回收 :\n"));
                    gc_free(p+1);
                }
            }
        }
    }

    //如果堆扫描完则 切换到root扫描
    sweeping = i;
    if(i == gc_heaps_used){
        sweeping = 0;
        gc_phase = GC_ROOT_SCAN;
    }
}

堆扫描完后，又重新回到GC_ROOT_SCAN阶段

关于gc安全的两点

写入屏障

处在gc执行后的暂停阶段期间，程序对对象又进行了更新会产生不可预料的后果，如下图所示:

  1. 首先E没有被Root管理，扫描根的时候无法扫描到，只有扫描C的子对象时才能标记到C
  2. A,B对象已经是黑色对象了，不需要在进行扫描了，是觉得的安全对象
  3. 此时C到E的引用被切断了，E被黑色对象B引用
  4. 如果不做任何操作，E将会在gc结束后备清除

这就是写入屏障的重要性，保证了在gc执行的多阶段暂停之间任然保证逻辑正确

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//tri-color.c

void write_barrier(void *obj_ptr,void *field,void* new_obj_ptr)
{

    Header* obj     = CURRENT_HEADER(obj_ptr);
    Header* new_obj = CURRENT_HEADER(new_obj_ptr);
    //如果老对象已经被标记了 就要检查新对象是否标记了
    if(IS_MARKED(obj)){
        if(!IS_MARKED(new_obj)){
            FL_SET(new_obj,FL_MARK);
            push(&stack,new_obj_ptr);
        }
    }
    //obj->field = new_obj
    *(void **)field = new_obj_ptr;

}

如上面所说，在更新对象的时候需要判断，如果原对象是一个黑色对象，则需要将当前对象标记为灰色后推入标记栈中

等待下次标记阶段扫描当前对象，解决了更新安全问题

分配安全

在gc暂停阶段期间新申请对象需要注意如果新申请的内存在清除内存的后方，只需要默认进行设置为黑色,防止被误回收