引用计数

Catalogue

1. 1. gc_inc 增加计数
2. 2. gc_dec 减少计数
3. 3. gc_update 引用更新

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

所有gc算法中引用计数最为特别,

相较于其他算法来说最明显的特点有:

1. 没有 stw(stop the world)时间
2. 没有 root的概念，不需要扫描栈

当然相较于其他算法来说弱点也很明显:

1. 增加了应用方的负担(需要时刻注意增减引用计数)
2. 通常需要搭载其他算法才能解决无法回收循环引用的问题

其他gc算法中基本没有对外提供api调用，对于应用层无感知，引用计数则需要开发者自己来维护跟踪分配的对象

• gc_inc: 引用计数 + 1 通常在更低级的分配器中默认指向
• gc_dec: 引用计数 - 1 为0 则直接回收
• gc_update: 许多情况下需要保证计数正确

gc_inc 增加计数

void gc_inc(void *ptr)
{
  //该内存属于哪个堆
  GC_Heap *gh;
  //该内存的header
  Header *hdr;

  //find header
  if (!(gh = is_pointer_to_heap(ptr))){
//      printf("not pointer\n");
    return;
  }
  if (!(hdr = get_header(gh, ptr))) {
    printf("not find header\n");
    return;
  }
  hdr->ref++;
}

is_pinter_to_heap：常规操作，进行合法性指针检查

get_header： 获取指针的头部，在确保该指针一定安全的情况下可以直接使用CURRENT_HEADER获取对象头

hdr->ref++: 直接递增即可

gc_dec 减少计数

减少计数的步骤要多一点，除了递减计数外还要执行一次检查，如果小于等于0则直接回收垃圾

void gc_dec(void *ptr)
{
  GC_Heap *gh;
  Header *hdr;
  //find header
  if (!(gh = is_pointer_to_heap(ptr))){
    return;
  }
  if (!(hdr = get_header(gh, ptr))) {
    printf("not find header\n");
    return;
  }
  hdr->ref -- ;
  
  //接下来执行计数检查
}

和递增计数一样，找到对象头后，直接hdr->ref--计数即可，接下来看当计数为0时执行回收的情况

if (hdr->ref == 0) {
  //对引用对象进行递归标记
  void *p;
  void *end = (void*)NEXT_HEADER(hdr);
  //对引用进行递归 减引用
  for (p = ptr; p < end; p++) {
    //对内存解引用，因为内存里面可能存放了内存的地址 也就是引用，需要进行引用的递归标记
    gc_dec(*(void **)p);
  }
  //回收
  gc_free(ptr);
}

对[p,end]的内存段进行扫描，递归进行child引用递归更新计数

最后调用gc_free释放当前内存块即可

gc_update 引用更新

p->next指向p2，在进行指针更新过后，没有任何对象在继续引用p2，所以在更新p->next的时候应该同时要gc_dec(p->next)来保证p2的计数正确,这就是gc_udpate的作用

void gc_update(void *ptr,void *obj)
{
  gc_inc(obj);
  gc_dec(*(void**)ptr);
  *(void**)ptr = obj;
}

1. 对目标对象obj进行计数 += 1，因为他被当前对象引用了
2. 如上面所说需要将被更新的指针进行计数 -= 1
3. 最后是更新即可

使用上面的例子:

typedef struct obj{
    struct obj* next;
    int         value;
}Obj;

Obj* p  = gc_malloc(sizeof(Obj));
p->next = gc_malloc(sizeof(obj));
Obj* p2 = gc_malloc(sizeof(Obj));

gc_update(&p->next,p2);
//等价于 p->next = p2;