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

分代回收算法

Catalogue
  1. 1. @分代概念
  2. 2. @gc_init 初始化
  3. 3. @minor_gc 新生代gc阶段
    1. 3.1. @minor_malloc 内存分配
    2. 3.2. @gc_copy 复制
    3. 3.3. @promote 晋升
    4. 3.4. @update_reference 更新引用
    5. 3.5. @write_barrier 写屏障
  4. 4. @major_gc 老年代gc
    1. 4.1. @gc_mark 标记阶段
    2. 4.2. @gc_sweep 清除阶段
    3. 4.3. @major_malloc

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

分代垃圾回收也是一种组合算法实现(gc复制 + 标记清除)，在了解之前先来看看几个关键字概念

@分代概念

新生代(newg): 作为内存分配区

幸存代(survivorfromg): 作为内存分配区

幸存代(survivorto): 新生代+幸存代执行复制算法,最终复制到幸存to区

老年代(oldg): 老年代单独执行标记清除算法

promote(晋升): 当前规定经历过3次gc后任然幸存的新生代对象会晋升为老年代对象，会拷贝到老年区

remember_set(记录集): 用于存储那些任然引用新生代对象的老年代对象，也是老年代的根ROOT

  1. 只从新生代和幸存代from分配内存
  2. 多次幸存后晋升为老年代,将对象拷贝到老年区
  3. 步骤2中如果晋升过后子对象还在新生代则记录到记录集中作为可达的根

@gc_init 初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void gc_init(size_t heap_size)
{
    //关闭自动扩充堆
    auto_grow = 0;

    //gc_heaps[3] 用于老年代堆区
    gc_heaps_used = 3;
    for (size_t i = 0; i < 4; i++){
        //使用sbrk 向操作系统申请大内存块
        void* p = sbrk(heap_size + PTRSIZE);
        if(p == NULL)exit(-1);

        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;
    }
    //初始化新生代空闲链表指针
    new_free_p = gc_heaps[newg].slot;
    //老年代分配需要用到空闲列表 通过gc_free 挂到空闲列表即可
    gc_free(gc_heaps[oldg].slot + 1);
}

当前主要固定四个内存区,new,from,to,old。并且关闭自动扩充堆

空闲指针free-list是专用于老年代的分配指针，在晋升的时候会从老年代区分配一份内存用于拷贝

空闲指针new_free_p是专用于内存分配指针，新内存都是从新生代区分配

@minor_gc 新生代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
void  minor_gc(void)
{
    //每次gc前将 free指向 to的开头
    gc_heaps[survivortog].slot->size = gc_heaps[survivortog].size;
    //初始化to空间的首地址
    to_free_p = gc_heaps[survivortog].slot;

    //递归进行复制  从 from  => to
    for(int i = 0;i < root_used;i++){
        void* forwarded;
        if(!(forwarded = gc_copy(roots[i].ptr))) continue;

        *(Header**)roots[i].optr = forwarded;
        //将root 所有的执行换到 to上
        roots[i].ptr = forwarded;
    }

    //更新跨代引用
    update_reference();

    //清空 新生代
    new_free_p = gc_heaps[newg].slot ;
    memset(new_free_p,0,gc_heaps[newg].size);
    new_free_p->size = gc_heaps[newg].size;


    //清空 幸存代  from
    memset(gc_heaps[survivorfromg].slot,0,gc_heaps[survivorfromg].size);
    gc_heaps[survivorfromg].slot->size = gc_heaps[survivorfromg].size;

    //交换 swap(幸存代from ,幸存代to);
    GC_Heap tmp             = gc_heaps[survivorfromg];
    gc_heaps[survivorfromg] = gc_heaps[survivortog];
    gc_heaps[survivortog]   = tmp;
}

新生代主要执行复制算法，将newg和fromg复制到tog空间，并置换from和to后结束新生代GC

主要流程和GC复制流程一致，可以去看gc复制的实现分析

  1. 搜索根执行拷贝到to区
  2. 更新引用
  3. 清空新生代，清空幸存代
  4. 交换from和to

@minor_malloc 内存分配

所有分配只能走新生代分配，直接从newg区分配一块空闲内存即可

1
2
3
4
5
6
7
8
9
10
11
12
if (new_free_p->size < req_size) {
    //一般是分块用尽会 才会执行gc 清除带回收的内存
    if (!do_gc) {
        do_gc = 1;
        //内存不够用的时候会触发 复制 释放空间
        //释放空间的时候会造成空间的压缩
        minor_gc();
        goto alloc;
    }
    printf("内存不够");
    return NULL;
}

  1. 从new_free_p执行的剩余空间分配一块足够大小的空间
  2. 内存不够则执行新生代gcminor_gc释放一定空闲内存

@gc_copy 复制

这里和复制算法稍微有点不一样，如果对象属于老年区则不作任何操作,复制只会拷贝新生代区的对象

1
2
3
4
5
6
if (!(gh = is_pointer_to_heap(ptr)))
    return NULL;
//查看该对象是否存在于 新生代 这里的get_header 只会去查找 新生代和两个幸存代
if (!(hdr = get_header(gh,ptr))) {
  return NULL;
}

同时在执行拷贝前需要检查年龄age是否小于3，否则需要晋升为老年代

1
2
3
4
5
6
7
8
9
10
//没有复制过  0
if(!IS_COPIED(hdr)){
    //判断年龄是否小于阈值
    if(hdr->age < AGE_MAX)
    {
     //拷贝
    }else{
        //晋升
    }
}

复制流程和之前的复制算法流程一样，可以去看之前的分析

@promote 晋升


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
void promote(void *ptr)
{
    Header* obj = CURRENT_HEADER(ptr);
    //1 从老年代空间分配出一块 内存 (老年代堆 完全采用 gc标记-清除算法来管理)
    void* new_obj_ptr = major_malloc(CURRENT_HEADER(ptr)->size);
    if(new_obj_ptr == NULL) abort();

    Header* new_obj   = CURRENT_HEADER(new_obj_ptr);
    //将obj 拷贝到 new_obj中
    memcpy(new_obj,obj,obj->size);

    obj->forwarding = new_obj;
    //标志已经复制过了 forwarded = true
    FL_SET(obj,FL_COPIED);

    //for child: obj 这里是为了检查老年代对象是否有对象依然指向新生代中
    for (void *p = ptr; p < (void*)NEXT_HEADER(obj); p++) {

        //解引用 如果该内存依然是指向的from，且有forwarding 则需要改了
        void *ptr = *(void**)p;
        GC_Heap *gh;
        Header *hdr;
        /* mark check */
        if (!(gh = is_pointer_to_heap(ptr))) continue;
        //查看该引用是否存在于 新生代 这里的get_header 只会去查找 新生代和两个幸存代
        if (!(hdr = get_header(gh,ptr)))     continue;
        //存在就要将 new_obj 加入集合
        rs[rs_index++] = new_obj_ptr;
        break;
    }

}

从老年代分配一块内存，将当前晋升对象拷贝过去

搜索子对象是否有在新生代和幸存区的，如果存在说明当前老年代对象有跨代引用，需要加入记录集remember_set管理

@update_reference 更新引用

这里的更新引用主要是针对跨代引用而言

如果某个对象没有加入ROOT，但是却被老年代引用了，这个时候就需要将它复制到幸存to区,如果不这么做的话，它就会被意外的清除了

如图所示,B对象没有加入根，在复制阶段无法被认定为活动对象，也就无法进行拷贝到幸存区，会被回收

但是他却被老年区的D对象引用，也应该被拷贝到幸存区

所以当前函数主要是处理这种情况，处理跨代引用的拷贝问题

需要注意一点: 当前函数会检查当老年代没有任何引用对象任然在新生代和幸存代时，会从记录集中剔除老年对象,那在老年代gc的时候会被清除，因为没有任何根能够搜索到该老年代对象了

@write_barrier 写屏障

为了让老年代对象任然保持活性，那么写入屏障是或不可缺的,想像下如下场景

  1. 某老年代对象已经没有任何跨代对象了,且已经被剔除记录集了，如果下一次老年代gc启动，则必定是最先被优化的那一批。
  2. 这时候新生代一个对象突然被老年代引用了，如果不做任何操作，我们在update_reference阶段是无法追踪到这个新生代引用对象的
  3. 这样导致步骤2中的新生代对象被无辜清除了，正确的做法是:在更新引用的时候需要判断下发出引用的对象是否属于老年代，然后需要记录记录集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
    //obj 在老年代
    //new_obj 在新生代
    //且 obj 未保存在 记忆集
    if(is_pointer_to_space(obj,oldg) &&
       !is_pointer_to_space(new_obj,oldg) &&
       !IS_REMEMBERED(obj))
    {
        rs[rs_index++] = obj;
        //设置该对象已经保存在了记忆集，无需再次保存
        FL_SET(obj,FL_REMEMBERED);
    }
    //obj->field = new_obj
    *(void **)field = new_obj_ptr;

}
  1. 检查对象是老年代，且被引用对象是新生代的情况
  2. 如果满足步骤1，则需要更新记录集

@major_gc 老年代gc

老年代gc完全按照标记清除算法执行，只是在搜索根的步骤换成了搜索记录集(remember_set)

1
2
3
4
5
6
7
8
9
10
void  major_gc(void)
{
    //rs 里的基本都是老年代
    for(int i = 0; i < rs_index; i ++) {
        //只对老年代 对象进行gc
        gc_mark(rs[i]);
    }
    //标记完成后 在进行 清除 对于没有标记过的进行回收
    gc_sweep();
}
  1. 进行记录集搜索并标记
  2. 进行清除回收未标记垃圾

@gc_mark 标记阶段

判断是否是老年代对象，如果不是则不需要标记

最后进行递归标记

可以看之前的标记清除章节

@gc_sweep 清除阶段

搜索老年代堆，对未标记内存进行回收

和之前标记清除章节一致

@major_malloc

从老年代堆中分配一份内存返回