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

标记清除-多链表法

Catalogue
  1. 1. gc_malloc 内存分配
    1. 1.1. 计算索引
    2. 1.2. 分配空间
    3. 1.3. 扩充空间
  2. 2. 释放阶段
  3. 3. 标记阶段
  4. 4. 清除阶段

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

多链表法相较于单链表法提升了分配速度,在之前的gc_malloc分配中都是采用的单链表，在分配的时候需要去搜索单链表

多链表的好处就是省去了去查找块的时间，直接就获取了最近的空闲块

默认创建33个空闲链表Header *free_list[33]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
* 请求大小 bytes	        对齐后的大小 bytes        空闲链表的索引
* ----------------------------------------------------------------
*     1-8                    8                       0
*	  9-16                   16                       1
*	 17-24                   24                       2
*	 25-32                   32                       3
*	 33-40                   40                       4
*	 41-48                   48                       5
*	 49-56                   56                       6
*	 57-64                   64                       7
*	 65-72                   72                       8
*	  ...                   ...                     ...
*	241-248                 248                      30
*	249-256                 256                      31
*  >   256                                          32

文件结构

1
2
3
4
5
- gc.c         堆实现
- gc.h         头部定义
- Makefile     构建文件
- mark_sweep.c 主要代码实现
- test.c       测试用例

test:

1
2
> make
> ./gc

关于多链表的结构

接下来分析一下两种标记清除法的区别，标记和清除阶段都是一样的，主要需要分析下关于分配和释放的区别

gc_malloc 内存分配

  1. 根据size获取对应空闲链表中的索引
  2. 在对应的索引中进行搜索
  3. 如果步骤2没有搜索到则需要向操作系统申请一份内存扩充堆

计算索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void*   gc_malloc(size_t req_size)
{
    printf("gc_malloc :%ld\n",req_size);
    Header *p, *prevp;
    size_t do_gc = 0;
    if (req_size <= 0) return NULL;

    //对齐 字节
    req_size = ALIGN(req_size, PTRSIZE);
    int index = (req_size - 1) >> ALIGNMENT_SHIFT;

    if(index > MAX_SLICE_HEAP)
        index = HUGE_BLOCK;
    printf("gc_malloc :%d size:%ld\n",index,req_size);
    
    //do sth...
}

传入的req_size先加上HEADER_SIZE后进行字节对齐

然后通过req_size - 1 >> 3来获得索引，等价于(req_size - 1) / 8,因为当前都是根据PTRSIZE(sizeof(void*))8字节对齐的

得到索引后再判断一下，如果大于MAX_SLICE_HEAP == 31,说明字节数过大。大内存块统一走索引为32的空闲链表

分配空间

1
2
3
4
5
6
7
8
9
10
alloc:
//从空闲链表上去搜寻 空余空间
prevp = free_list[index];
//死循环 遍历
for (p = prevp; p; prevp = p, p = p->next_free) {
    //堆的内存足够
    if (p->size >= req_size) {
        //...
    }
}

free_ist[index]处开始遍历该空闲链表，如果找到满足的情况进行分配后返回

扩充空间

1
2
3
4
5
6
7
8
9
10
if (!do_gc && auto_gc) {
    gc();
    do_gc = 1;
    goto alloc;
}
    //上面说明 执行了gc之后 内存依然不够用 那么需要扩充堆大小
else if ((p = grow(req_size)) != NULL){
    goto alloc;
}
return NULL;

当无空闲链表可用时，先进行gc后进行grow新分配一份内存

如果都失败了则返回NULL

释放阶段

释放和之前的差不多，区别就是要对应索引

1
2
3
4
5
6
7
8
9
10
11
12
13
void    gc_free(void *ptr)
{
    DEBUG(printf("start free mem:%p\n",ptr));
    Header *target, *hit;
    int index;

    //通过内存地址向上偏移量找到  header头
    target = (Header *)ptr - 1;
    //回收的数据立马清空
    memset(ptr,0,target->size);

    index = (target->size - 1) >> ALIGNMENT_SHIFT;
}

根据字节数计算出索引

这里和之前的释放还是有点区别

1
2
3
4
5
6
7
8
9
10
//如果是小内存 不需要合并直接挂到最新的表头即可
if(index <= MAX_SLICE_HEAP){
    if(free_list[index]){
        target->next_free = free_list[index]->next_free;
        free_list[index]->next_free = target;
    }else{
        free_list[index] = target;
    }
    return;
}

现在不需要遍历空闲链表找到合适的位置进行插入和合并了,只需要插入表头即可,效率要高很多，复杂度为O(1)

只有大内存块继续走之前的合并流程

标记阶段

和mark-sweep篇标记阶段一样的

清除阶段

和mark-sweep篇清除阶段一样的

清除过后的情况应该是这样