超シンプルなGCを書いてみた

超シンプルなGC(ガベージコレクション)を書いてみました。

基本的には stop and copy 方式と呼ばれているやつで、保守的(conservative)です。
また、stop and copy 方式ですので、メモリ領域へのアクセスにはダブルポインタが必要になります。

これを使ったサンプルプログラムを明日は考えます。
あんまり複雑なケースのテストをしていないので、たぶんバグがあると思われますが。

あと、これのバグ取りをするのに、初めてgdbのwatchを使った件。
ちょっと複雑なプログラムを書いて動作を確認したら、RubyのGCのコードを読書して
スタック領域とヒープ領域の操作の仕方を調べます。

simplegc.h

#ifndef __SIMPLE_GC_H__
#define __SIMPLE_GC_H__

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

typedef int ID;

#ifndef TRUE
# define TRUE 1
#endif

#ifndef FALSE
# define FALSE 0
#endif

/* object list node */
typedef struct _yz_objinfo {
	void*  addr;
	size_t size;
	ID     id;
	unsigned int is_atomic : 1;
	unsigned int is_marked : 1;

	struct _yz_objinfo* next;
	struct _yz_objinfo* prev;
} yz_objinfo_t;

#define LIST_INSERT_AFTER(pos, obj) do {			\
		if(pos == NULL) {							\
			pos = obj;								\
		}											\
		else {										\
			obj->next = pos->next;					\
			if(obj->next) obj->next->prev = obj;	\
			obj->prev = pos;						\
			pos->next = obj;						\
		}											\
	} while(0)

#define LIST_INSERT_BEFORE(pos, obj) do {			\
		if(pos == NULL) {							\
			pos = obj;								\
		}											\
		else {										\
			obj->prev = pos->prev;					\
			if(obj->prev) obj->prev->next = obj;	\
			obj->next = pos;						\
			pos->prev = obj;						\
		}											\
		pos = obj;									\
	} while(0)

#define LIST_DELETE(obj) do {						\
		if(obj->prev) {								\
			obj->prev->next = obj->next;			\
			obj->prev = NULL;						\
		}											\
		if(obj->next) {								\
			obj->next->prev = obj->prev;			\
			obj->next = NULL;						\
		}											\
	} while(0)


#define INIT_REGION_SIZE (40 * 1024) /* 40KB */
#define MEM_ALIGN_BASE 4

void  yz_gc_init();

ID    yz_gc_alloc(size_t size);
ID    yz_gc_alloc_atomic(size_t size);
ID    yz_gc_alloc_root(size_t size);

void  yz_gc_invoke(void);
void* yz_gc_get_raw_ptr(ID id);

#define p(id) yz_gc_get_raw_ptr(id)
#define pp(id,type) ((type*)yz_gc_get_raw_ptr(id))
#define pv(id,type) (*(type*)yz_gc_get_raw_ptr(id))


#endif /*  __SIMPLE_GC_H__ */

simplegc.c

#include "simplegc.h"

typedef struct _mem_region {
	size_t size;
	size_t tail;
	char*  region;
} yz_mem_region_t;

static yz_mem_region_t region;

static ID     last_id = 0;
static int    gc_init_called = 0;

static yz_objinfo_t *obj_space = NULL;
static yz_objinfo_t *roots = NULL;

static yz_objinfo_t* yz_allocate_memory(size_t size);
static yz_objinfo_t* yz_objinfo_new(void);
static void yz_gc_mark(yz_objinfo_t* p);

#define ALL_OBJ(list,var) for(var=list; var!=NULL; var=var->next)

void yz_gc_init() {
	if(gc_init_called) return;

	gc_init_called = 1;

	region.size   = INIT_REGION_SIZE;
	region.tail   = 0;
	region.region = malloc(region.size);

	assert(region.region);
}

static yz_objinfo_t* yz_objinfo_new(void) {
	return calloc(sizeof(yz_objinfo_t), 1);
}

ID yz_gc_alloc(size_t size) {
	yz_objinfo_t* t;

	yz_gc_init();

	t = yz_allocate_memory(size);
	t->id = last_id++;
	LIST_INSERT_BEFORE(obj_space, t);

	return t->id;
}

ID yz_gc_alloc_atomic(size_t size) {
	yz_objinfo_t* t;

	yz_gc_init();

	t = yz_allocate_memory(size);
	t->is_atomic = TRUE;
	t->id = last_id++;

	LIST_INSERT_BEFORE(obj_space, t);

	return t->id;
}

ID yz_gc_alloc_root(size_t size) {
	yz_objinfo_t* t;

	yz_gc_init();

	t= yz_allocate_memory(size);
	t->id = last_id++;
	LIST_INSERT_BEFORE(roots, t);

	return t->id;
}

static yz_objinfo_t* yz_allocate_memory(size_t size) {
	if(!gc_init_called) yz_gc_init();

	assert(size);
	assert(region.tail + size < region.size);

	yz_objinfo_t* obj = yz_objinfo_new();

	obj->size = size;
	obj->addr = & region.region[ region.tail ];

	region.tail += ((size-1) / MEM_ALIGN_BASE + 1) * MEM_ALIGN_BASE;

	return obj;
}


void yz_gc_invoke(void) {
	yz_objinfo_t* p;

	yz_mem_region_t new_region;

	if( region.tail * 1.0 / region.size > 0.8) {
		new_region.size = region.size * 2;
	}
	else {
		new_region.size = region.size;
	}
	new_region.tail = 0;
	new_region.region = malloc(region.size);

	assert(new_region.region);

	p = roots;

	/* mark phase */
	ALL_OBJ(roots,p) {
		yz_gc_mark(p);
	}

	{
		yz_objinfo_t* new_obj_space = NULL;
		yz_objinfo_t* new_roots = NULL;

		ALL_OBJ(roots, p) {
			if(p->is_marked) {
				yz_objinfo_t* new_place = yz_objinfo_new();

				new_place->size = p->size;
				new_place->id   = p->id;
				new_place->addr = new_region.region + new_region.tail;
				memmove(new_place->addr, p->addr, p->size);
				assert(!strncmp(p->addr, new_place->addr, p->size));

				LIST_INSERT_BEFORE(new_roots, new_place);

				new_region.tail
					+= ((new_place->size-1)/MEM_ALIGN_BASE + 1) * MEM_ALIGN_BASE;

				/*printf("[%d,%d] ", new_place->id, pv(new_place->id,int));*/
			}
		}

		ALL_OBJ(obj_space, p) {
			if(p->is_marked) {
				yz_objinfo_t* new_place = yz_objinfo_new();

				new_place->size = p->size;
				new_place->id   = p->id;
				new_place->addr = new_region.region + new_region.tail;
				memmove(new_place->addr, p->addr, p->size);
				assert(!strncmp(p->addr, new_place->addr, p->size));

				LIST_INSERT_BEFORE(new_obj_space, new_place);

				new_region.tail
					+= ((new_place->size-1)/MEM_ALIGN_BASE + 1) * MEM_ALIGN_BASE;

				/*printf("[%d,%d] ", new_place->id, pv(new_place->id,int));*/
			}
		}
		/*puts("");*/

		free(region.region);
		region = new_region;

		p = obj_space;
		while(p) {
			yz_objinfo_t* tmp = p;
			p = p->next;
			free(tmp);
		}
		p = roots;
		while(p) {
			yz_objinfo_t* tmp = p;
			p = p->next;
			free(tmp);
		}

		obj_space = new_obj_space;
		roots = new_roots;
	}
}

static void yz_gc_mark(yz_objinfo_t* p) {
	ID maybe_ref;
	int offset;
	char* pb = p->addr; /* byte access pointer */

	if(p->is_marked) {
		return;
	}
	p->is_marked = TRUE;

	if(p->is_atomic) {
		/* p has no reference */
		return;
	}

	for(offset=0;  offset < p->size;  offset+=sizeof(ID)) {
		yz_objinfo_t* t;
		maybe_ref = *(ID*)(pb + offset);
		ALL_OBJ(obj_space,t) {
			if(t->id == maybe_ref) {
				yz_gc_mark(t);
			}
		}
	}
}

void* yz_gc_get_raw_ptr(ID id) {
	yz_objinfo_t* p = obj_space;

	ALL_OBJ(obj_space,p) {
		if(p->id == id) {
			return p->addr;
		}
	}

	ALL_OBJ(roots, p) {
		if(p->id == id) {
			return p->addr;
		}
	}

	assert(0);
	return NULL;
}