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

标记清除算法

Catalogue
  1. 1. gc阶段
  2. 2. 标记阶段
    1. 2.1. 检查指针是否合法
    2. 2.2. 标记对象
    3. 2.3. 递归进行child标记
  3. 3. 清除阶段

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

标记-清除 算法主要分为两个过程:标记O(N)、清除O(N),接下来讲解gc的代码实现

文件结构

1
2
3
- Makefile     构建文件
- mark_sweep.c 主要代码实现
- test.c       测试用例

test:

1
2
> make
> ./gc

gc阶段

1
2
3
4
5
6
7
8
void  gc(void)
{
    //垃圾回收前 先从 root 开始 进行递归标记
    for(int i = 0;i < root_used;i++)
        gc_mark(roots[i].ptr);
    //标记完成后 在进行 清除 对于没有标记过的进行回收
    gc_sweep();
}
  1. 对根进行遍历，不清楚根可以去看(什么是Root?),进行可达性标记
  2. 进入清除阶段，将所有垃圾进行回收，释放可用空间，更新空闲链表

标记清除的实现主要就是标记(marked)，通过对根的访问，对所有可以追踪到的对象都进行标记mark = 1，标记阶段就完成任务了

清除阶段会遍历整个堆，所以复杂度是O(N)，随着堆的增加而呈线性增长，清除阶段会对每份内存进行判断，如果mark = 0则认定为垃圾对象，进行回收。

整个gc阶段就完成了，如果有释放垃圾，此时新分配的内存就可以重复利用刚才释放的空间了

标记阶段

接下来详细了解一下标记阶段，标记阶段主要完成四件事

  1. 判断当前指针是否合法
  2. 进行标记,如果已经标记过则不需要再次标记
  3. 对当前对象进行标记
  4. 对child引用进行递归标记

检查指针是否合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void gc_mark(void * ptr)
{
    GC_Heap *gh;
    Header *hdr;

    /* mark check */
    if (!(gh = is_pointer_to_heap(ptr))){
      return;
    } 
    if (!(hdr = get_header(gh, ptr))) {
      return;
    }
    if (!FL_TEST(hdr, FL_ALLOC)) {
      return;
    }
    if (FL_TEST(hdr, FL_MARK)) {
      return;
    }
}
  1. is_pointer_to_heap: 判断传入的指针是否是堆里的合法内存，通过地址范围判断
  2. get_header: 获取指针的对象头
  3. FL_*： 这个开头的是一些宏定义，可以进行位操作，这里是判断header->flags有没有设置 FL_ALLOC内存分配标志
  4. FL_TEST: 这里判断如果已经标记过了，不需要再次标记

标记对象

1
2
3
4
//.....
/* marking */
FL_SET(hdr, FL_MARK);
//.....

这里展开就是:

1
((Header*)hdr)->flags |= 0x2

对对象头进行标记，表明当前对象是可达对象，是合法对象，不能被清除

递归进行child标记

关于引用的标记其实就是遍历当前内存的地址空间，对每一个字节逐字扫描，发现了合法指针就进行标记,例如:

1
2
3
4
5
6
7
8
9
10
void main(){
    typedef struct obj{
        int         value;
        struct obj* next;
    }Obj;
    
    Obj* ptr  = gc_malloc(sizeof(Obj));
    ptr->next = gc_malloc(sizeof(Obj));
    ptr->next->next = gc_malloc(sizeof(Obj));
}

如果对p进行了标记，那么ptr->next也应该被标记，因为他们之间有引用关系，怎么做到的呢

对ptr的内存段start到end这个区间进行遍历

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

正常情况下遍历到(void*)ptr + sizeof(int)处应该就是p->next的地址，如此递归不放过任何的角落

  1. gc_mark(ptr)
  2. gc_mark(ptr->next)
  3. gc_mark(ptr->next->next)

标记完应该是这样的

清除阶段

清除阶段就简单啦，直接搜索堆，将所有的已使用却没标记的内存释放

  1. 遍历gc_heaps数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void     gc_sweep(void)
    {
        size_t i;
        Header *p, *pend, *pnext;

        //遍历所有的堆内存
        //因为所有的内存都从堆里申请，所以需要遍历堆找出待回收的内存
        for (i = 0; i < gc_heaps_used; i++) {
            //pend 堆内存结束为止
            pend = (Header *)(((size_t)gc_heaps[i].slot) + gc_heaps[i].size);
            //do ...
        }
    }

  2. 搜索heap查看该分块是否已经分配FL_ALLOC,没有该标志说明是空闲块，不需要理会

    1
    2
    3
    4
    5
    6
    7
    //堆的起始为止 因为堆的内存可能被分成了很多份，所以需要遍历该堆的内存
    for (p = gc_heaps[i].slot; p < pend; p = NEXT_HEADER(p)) {
        //查看该堆是否已经被使用
        if (FL_TEST(p, FL_ALLOC)) {
            //do..
        }
    }

  3. 解除标志，如果没有被标记过说明是垃圾: 进行gc_free

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    //查看该堆是否被标记过
    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);
    }

清除过后的堆应该是这样的: