Skip to content

Instantly share code, notes, and snippets.

@Chubek

Chubek/README.md

Created November 26, 2023 12:10
Show Gist options
  • Save Chubek/9b635453ec0efd79e3f50f3abff0dc45 to your computer and use it in GitHub Desktop.
Save Chubek/9b635453ec0efd79e3f50f3abff0dc45 to your computer and use it in GitHub Desktop.
Download ZIP
Header-Only, Reference-Counting, Arena-based Garbage Collector (Working version)
Raw
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.

Raw
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);
}
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment