Header-Only, Reference-Counting, Arena-based Garbage Collector (Working version)

README.md

gcx.h is a working garbage collector, header-only. It is a reference-counting garbage collector but it does not matter if you increase/decrease the refcount because if you dump an entire arena (aka 'frame') all the allocated memory pointers will get dumped alongside.

This is a very simple garbage collector. I have created it as a temporary solution for my projects, until I develop something more complex and sophistated. It's only hundred-odd lines. It is a header-only library, has a header guard and all the functions are static-inlined. You can include this file once in your file, and you can include it again because the functions are local to a single file. Alternatively, you can wget this file as a C file, remove the static keywords, and use it as a proper source file. It's entirely up to you.

As I said in the title, it is an arena-based garbage collector. Every arena is called a frame_t structure. The 'proper' way to use this garbage collector:

1- Create a frame/arena for every, or every other, structure/portion of your program. 2- Every time you need to allocate memory, request a 'subframe'. 3- Allocate/deallocate the subframe as needed. 4- Every time you need a copy of the data, request a copy, and the refcount shall increase automatically. Every time you need to get rid of the data, use the proper function, and the reference shall decrease. 5- If you have the resources, you can automatiically increase the refcounts --- it does so by looking in the static region of the program, and below (or above, according to how you look at it) the program break for instances of that pointer --- and increase it by one if it sees the pointer. Keep in mind that this aspect is prety so-and-so. Don't rely on it much. 6- Whenever you need to collect, you can call the function and it shall collect the dead references.

The example.c file contains an example of using all the functions.

Thanks.

example.c

#include "commonx/gcx.h"
#include <stdio.h>

int 
main(int argc, char** argv)
{
	frame_t* frame = new_frame("my_frame");
	frame_t* subf  = new_subframe(&frame, "my_subframe");
	ALLOC_ERR res  = allocate_subframe(frame, "my_subframe", 8);
	if (res < 0)
		return res;
	uint64_t num   = (uint64_t)copy_into_subframe(frame, 
			"my_subframe",
			(void*)UINT64_MAX, 0, 8);
	printf("%lu\n", num);
	ALLOC_ERR res2 = reallocate_subframe(frame, "my_subframe", 16);
	if (res2 < 0)
		return res2;
	void* data    = set_subframe(frame, "my_subframe", 
			1, 0, 16);
	printf("%lu", *((uint64_t*)data) & 0xffffffffffffffff);
	uint64_t numcpy = (uint64_t)get_subframe_copy(frame, 
			"my_subframe");
	printf("%lu\n", numcpy);
	iter_and_collect_frame(frame);
	numcpy = (uint64_t)get_subframe_copy(frame, "my_subframe");
	printf("%lu\n", numcpy);
	destroy_subframe_copy(frame, "my_subframe");
	destroy_subframe_copy(frame, "my_subframe");
	iter_and_collect_frame(frame);
	dump_frame(frame);
	

}

gcx.h

#ifndef TOOLX_GCX_H_
#define TOOLX_GCX_H_

#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>
#include <sys/types.h>

extern int etext, edata, end;

static uint64_t
hash64(const char* str)
{
    uint64_t h = 0x100;
    char c;
    while ((c = *str++)) {
        h ^= c;
        h *= 1111111111111111111u;
    }
    return h ^ h>>32;
}

typedef struct 
Memory frame_t;

typedef struct 
Memory
{
	frame_t*	next;
	uint64_t	hash;
	size_t		refcnt;
	char*		memory;
	size_t		size;
}
frame_t;

static inline frame_t*
new_frame(const char* id)
{
	frame_t* frame = calloc(1, sizeof(frame_t));
	frame->hash 	= hash64(id);
	return frame;
}



static inline void
dump_frame(frame_t* frame)
{
	for (frame_t* subf = frame; subf != NULL; subf = frame)
	{
		frame = subf->next;
		if (subf->memory != NULL) 
			free(subf->memory);
		free(subf);
	}
}

static inline frame_t*
new_subframe(frame_t** frame, const char* id)
{
	uint64_t hash = hash64(id);

	frame_t* subf  = calloc(1, sizeof(frame_t));
	subf->hash     = hash;
	subf->next     = *frame;
	*frame	      = subf;
	
	return subf;
}

static inline frame_t*
get_subframe(frame_t* frame, const char* id)
{
	uint64_t hash = hash64(id);

	for (frame_t* subf = frame; subf != NULL; subf = subf->next)
	{
		if (subf->hash == hash)
		{
			return subf;
		}
	}

}

#define ALLOC_NO_ERR	0
#define ALLOC_ERR_MEM	-1
#define ALLOC_ERR_SIZE  -2

#define ALLOC_ERR	int

static inline ALLOC_ERR
allocate_subframe(frame_t* frame, const char* id, size_t size)
{
	frame_t* subf 	= get_subframe(frame, id);

	void* new_subf  = calloc(1, size);

	if (new_subf == NULL)
		return ALLOC_ERR_MEM;

	subf->memory 	= new_subf;
	subf->size	= size;

	return ALLOC_NO_ERR;
}

static inline ALLOC_ERR
reallocate_subframe(frame_t* frame, const char* id, size_t new_size)
{
	frame_t* subf 	= get_subframe(frame, id);
	
	if (subf->size >= new_size)
		return ALLOC_ERR_SIZE;

	void* new_subf	= realloc(subf->memory, new_size);
	
	if (new_subf == NULL)
		return ALLOC_ERR_MEM;

	subf->memory	= new_subf;
	subf->size	= new_size;

	return ALLOC_NO_ERR;
}

static inline ALLOC_ERR
deallocate_subframe(frame_t* frame, const char* id)
{
	frame_t* subf 	= get_subframe(frame, id);

	subf->refcnt = 0;
	free(subf->memory);

	return ALLOC_NO_ERR;
}

static inline void*
copy_into_subframe(frame_t* frame, 
		const char* id, 
		void* data, 
		size_t size,
		size_t offset)
{
	frame_t* subf 	= get_subframe(frame, id);

	if (subf->size < size)
		reallocate_subframe(frame, id, size);
	
	subf->refcnt++;
	return (void*)memmove(&subf->memory[offset], 
			&((char*)data)[0], size);
}

static inline void*
set_subframe(frame_t* frame, 
	const char* id, 
	long data, 
	size_t size,
	size_t offset)
{
	frame_t* subf	= get_subframe(frame, id);

	if (subf->size < size)
		reallocate_subframe(frame, id, size);
	
	subf->refcnt++;
	return (void*)memset(&subf->memory[offset], data, size);
}

static inline void*
get_subframe_copy(frame_t* frame, const char* id)
{
	frame_t* subf 	= get_subframe(frame, id);
	subf->refcnt++;
	return subf->memory;
}

static inline void
destroy_subframe_copy(frame_t* frame, const char* id)
{
	frame_t* subf 	= get_subframe(frame, id);
	subf->refcnt--;
}

static inline void
autocount_refcnt(frame_t* frame)
{
	void* pbrk 	= sbrk(0);
	void* next;
	
	for (next = --pbrk; next != NULL; --next)
	{
		if (next == frame->memory)
			frame->refcnt++;

	}

	for (next = (void*)&edata; next != (void*)&end; ++next)
	{
		if (next == frame->memory)
			frame->refcnt++;
	}
}


static inline void
iter_and_collect_frame(frame_t* frame)
{
	for (frame_t* subf = frame; subf != NULL; subf = subf->next)
	{
		if (!subf->refcnt)
			free(subf->memory);
	}
}

#endif