我也研究下云风的垃圾回收库

在网上闲逛时发现了一个云风写的垃圾回收库和源码学习文档，我也一起研究一下，一方面弥补一下我对gc知识理解的不足，另一方面督促自己把这个不足1000行代码确足够诡异的迷你gc库看完，搞清楚原理。

参考：
源码地址：http://manualgc.googlecode.com/svn/trunk/
另外一位同学写的分析文章：http://www.cppblog.com/darkdestiny/archive/2008/09/10/61528.html

写的挺详细，不过我还是记录一下自己理解的部分

我也从分配内存的gc_malloc函数开始
大家都知道由malloc,realloc,calloc分配内存需要释放，那么一个自动内存管理的库，自然需要重写这3个函数，实际上这个库重写了下面这3个函数

#define my_malloc malloc
#define my_free free
#define my_realloc realloc

具体看malloc函数前先看一下这个函数涉及到的主要的数据结构

struct node {
	int mark;
	union {
		struct {
			void * mem;
			struct link *children;
			void (*finalizer)(void *);
		} n;
		struct {
			intptr_t mem;
			struct link *children;
			intptr_t weak;
		} c;
		int free;
	} u;
};

struct hash_node {
	int id;
	struct hash_node *next;
};

struct hash_map	{
	struct hash_node **table;
	int size;
	struct hash_node *free;
	int number;
};

static struct {
	struct node *pool;
	int size;
	int free;
	int mark;
	bool cache_dirty;
	struct stack stack;
	struct hash_map map;
	struct cache_node cache[CACHE_SIZE];
} E;

E是这个库对内存管理的容器，我们今天看的主要是struct node *pool这个一维线性空间和struct hash_map这个hash表

实际上每个被分配的内存块会放入pool这个一维线性空间里，然后通过hash_map记录这个空间的id号，将来通过这个内存块的指针就能直接方便的通过hash找到pool的id，最终得到这个node的信息

看一下malloc是如何被重写的

void*
gc_malloc(size_t sz,void *parent,void (*finalizer)(void *))
{
	void *ret=my_malloc(sz);
	int id=map_id(ret);
	E.pool[id].u.n.finalizer=finalizer;
	if (parent) {
		gc_link(parent,0,ret);
	}
	else {
		stack_push(id);
	}
	return ret;
}

my_malloc实际就是malloc，然会调用map_id记录这块内存分配的信息

static int
map_id(void *p)
{
	int h=hash(p);
	struct hash_node *node=E.map.table[h & (E.map.size -1)];
	while (node) {
		if (E.pool[node->id].u.n.mem==p) {
			return node->id;
		}
		node=node->next;
	}
	if (E.map.number >= E.map.size) {
		map_expand();
	}

	++E.map.number;

	if (E.map.free) {
		node=E.map.free;
		E.map.free=node->next;
	}
	else {
		node=(struct hash_node *)my_malloc(sizeof(*node));
	}
	node->id=node_alloc(p);
	node->next=E.map.table[h & (E.map.size -1)];
	E.map.table[h & (E.map.size -1)]=node;

	return node->id;
}

函数首先根据指针地址计算一个hash值，具体算法我们就没必要细究了
然后根据hash值取出这个hash值对应的链表（这个也是链式hash结构）
接着while循环遍历链表，链表里存放的是这个被分配的内存块在E.pool这个一维线性空间内的id值，所以通过 if (E.pool[node->id].u.n.mem==p) 来查找是否是这个内存块

这里应该是找不到的，那么下面做得事情是：

1.将*p所指向的内存块分配到E.pool这个线性空间内，并得到这个被分配空间的id
2.将这个id号存入hashmap中，方面将来直接在E.pool中定位到这个空间

第一步工作实际执行的是以下代码

node=(struct hash_node *)my_malloc(sizeof(*node));
node->id=node_alloc(p);

第二步执行的是：

node->next=E.map.table[h & (E.map.size -1)];
E.map.table[h & (E.map.size -1)]=node;

再看一下 node_alloc(p)

static int
node_alloc(void *p)
{
	struct node *ret;
	if (E.free==-1) {
		int sz=E.size * 2;
		int i;
		if (sz==0) {
			sz=1024;
		}

		E.pool=(struct node *)my_realloc(E.pool,sz*sizeof(struct node));
		ret=E.pool + E.size;
		ret->u.n.children=0;

		for (i=E.size+1;i<sz;i++) {
			E.pool[i].u.free=i+1;
			E.pool[i].mark=-1;
			E.pool[i].u.n.children=0;
		}
		E.pool[sz-1].u.free=-1;
		E.free=E.size+1;
		E.size=sz;
	}
	else {
		ret=E.pool + E.free;
		E.free = E.pool[E.free].u.free;
	}
	ret->u.n.mem=p;
	ret->mark=0;
	ret->u.n.finalizer=0;
	if (ret->u.n.children) {
		ret->u.n.children->number=0;
	}
	return ret-E.pool;
}

通过gc_init函数得知这里执行的是E.free==-1这段分支

E.size初始也是0
所以实际上E.pool这个线性空间是在这时被realloc初始化的

ret=E.pool+e.size 也就是 ret=E.pool+0;即首个元素,下面的for循环是：
for(i=1;i<1024;i++)

即初始化一下这个一维空间的所有元素值
最有意思的是：E.pool[i].u.free=i+1;
就是说：
E.pool[1].u.free=2;
E.pool[2].u.free=3;
...
E.pool[1022].u.free=1023
E.pool[1023].u.free=-1

当前的E.free=1
最后返回的是ret-E.pool,根据前面的ret=E.pool+0,得知此时函数返回值是0
即E.pool这个一维空间是按id递增的顺序分配的

可以试着想象如果是第二次分配空间
E.free==-1条件不满足,(实际E.free=1)

所以执行

ret=E.pool + E.free;
E.free = E.pool[E.free].u.free;

即ret=E.pool+1,返回的ret-E.pool实际就是返回ID为1，可见是顺序递增的

另外可以看到
E.free=E.pool[E.free].u.free
实际上是：E.free=E.pool[1].u.free
而E.pool[1].u.free=2

所以第二次调用该函数后E.free=2

今天先看这么多，写的很乱，有兴趣的还是自己看源码吧

评论

3 楼 crackcell 2009-10-17  

收获颇丰，呵呵~

2 楼 bachmozart 2009-03-22  

mathgl 写道

线程安全么？

这个库没有考虑多线程的情况，就是一个标记清除算法的gc库，也不支持并行收集
具体用法在test.c里面有，为了保证垃圾收集的效率，作者在这个库的实现上做了很大的优化，大部分操作复杂性都是O(1)的，我主要也是想了解这部分

1 楼 mathgl 2009-03-22  

线程安全么？