tgc is a tiny garbage collector for C written in ~500 lines of code and based
on the Cello Garbage Collector.
#include "tgc.h"
static tgc_t gc;
static void example_function() {
char *message = tgc_alloc(&gc, 64);
strcpy(message, "No More Memory Leaks!");
}
int main(int argc, char **argv) {
tgc_start(&gc, &argc);
example_function();
tgc_stop(&gc);
}tgc is a conservative, thread local, mark and sweep garbage collector,
which supports destructors, and automatically frees memory allocated by
tgc_alloc and friends after it becomes unreachable.
A memory allocation is considered reachable by tgc if...
- a pointer points to it, located on the stack at least one function call
deeper than the call to
tgc_start, or, - a pointer points to it, inside memory allocated by
tgc_allocand friends.
Otherwise a memory allocation is considered unreachable.
Therefore some things that don't qualify an allocation as reachable are, if...
- a pointer points to an address inside of it, but not at the start of it, or,
- a pointer points to it from inside the
staticdata segment, or, - a pointer points to it from memory allocated by
malloc,calloc,reallocor any other non-tgcallocation methods, or, - a pointer points to it from a different thread, or,
- a pointer points to it from any other unreachable location.
Given these conditions, tgc will free memory allocations some time after
they become unreachable. To do this it performs an iteration of mark and
sweep when tgc_alloc is called and the number of memory allocations exceeds
some threshold. It can also be run manually with tgc_run.
Memory allocated by tgc_alloc can be manually freed with tgc_free, and
destructors (functions to be run just before memory is freed), can be
registered with tgc_set_dtor.
void tgc_start(tgc_t *gc, void *stk);Start the garbage collector on the current thread, beginning at the stack
location given by the stk variable. Usually this can be found using the
address of any local variable, and then the garbage collector will cover all
memory at least one function call deeper.
void tgc_stop(tgc_t *gc);Stop the garbage collector and free its internal memory.
void tgc_run(tgc_t *gc);Run an iteration of the garbage collector, freeing any unreachable memory.
void tgc_pause(tgc_t *gc);
void tgc_resume(tgc_t *gc);Pause or resume the garbage collector. While paused the garbage collector will not run during any allocations made.
void *tgc_alloc(gc_t *gc, size_t size);Allocate memory via the garbage collector to be automatically freed once it becomes unreachable.
void *tgc_calloc(gc_t *gc, size_t num, size_t size);Allocate memory via the garbage collector and initalise it to zero.
void *tgc_realloc(gc_t *gc, void *ptr, size_t size);Reallocate memory allocated by the garbage collector.
void tgc_free(gc_t *gc, void *ptr);Manually free an allocation made by the garbage collector. Runs any destructor if registered.
void *tgc_alloc_opt(tgc_t *gc, size_t size, int flags, void(*dtor)(void*));Allocate memory via the garbage collector with the given flags and destructor.
For the flags argument, the flag TGC_ROOT may be specified to indicate that
the allocation is a garbage collection root and so should not be
automatically freed and instead will be manually freed by the user with
tgc_free. Because roots are not automatically freed, they can exist in
normally unreachable locations such as in the static data segment or in
memory allocated by malloc.
The flag TGC_LEAF may be specified to indicate that the allocation is a
garbage collection leaf and so contains no pointers to other allocations
inside. This can benefit performance in many cases. For example, when
allocating a large string there is no point the garbage collector scanning
this allocation - it can take a long time and doesn't contain any pointers.
Otherwise the flags argument can be set to zero.
The dtor argument lets the user specify a destructor function to be run
just before the memory is freed. Destructors have many uses, for example they
are often used to automatically release system resources (such as file handles)
when a data structure is finished with them. For no destructor the value NULL
can be used.
void *tgc_calloc_opt(tgc_t *gc, size_t num, size_t size, int flags, void(*dtor)(void*));Allocate memory via the garbage collector with the given flags and destructor and initalise to zero.
void tgc_set_dtor(tgc_t *gc, void *ptr, void(*dtor)(void*));Register a destructor function to be called after the memory allocation ptr
becomes unreachable, and just before it is freed by the garbage collector.
void tgc_set_flags(tgc_t *gc, void *ptr, int flags);Set the flags associated with a memory allocation, for example the value
TGC_ROOT can be used to specify that an allocation is a garbage collection
root.
int tgc_get_flags(tgc_t *gc, void *ptr);Get the flags associated with a memory allocation.
void(*tgc_get_dtor(tgc_t *gc, void *ptr))(void*);Get the destructor associated with a memory allocation.
size_t tgc_get_size(tgc_t *gc, void *ptr);Get the size of a memory allocation.
Definitely! While there is no way to create a completely safe/portable garbage collector in C this collector doesn't use any platform specific tricks and only makes the most basic assumptions about the platform, such as that the architecture using a continuous call stack to implement function frames.
It should be safe to use for more or less all reasonable architectures found
in the wild and has been tested on Linux, Windows, and OSX, where it was easily
integrated into several large real world programs (see examples) such as
bzip2 and oggenc without issue.
Saying all of that, there are the normal warnings - this library performs undefined behaviour as specified by the C standard and so you use it at your own risk - there is no guarantee that something like a compiler or OS update wont mysteriously break it.
In this unlikely case tgc will treat the data as a pointer and assume that
the memory allocation it points to is still reachable. If this is causing your
application trouble by not allowing a large memory allocation to be freed
consider freeing it manually with tgc_free.
Due to the way tgc works, it always needs a pointer to the start of each
memory allocation to be reachable. This can break algorithms such as the
following, which work by incrementing a pointer.
void bad_function(char *y) {
char *x = tgc_alloc(&gc, strlen(y) + 1);
strcpy(x, y);
while (*x) {
do_some_processsing(x);
x++;
}
}Here, when x is incremented, it no longer points to the start of the memory
allocation made by tgc_alloc. Then during do_some_processing, if a sweep
is performed, x will be declared as unreachable and the memory freed.
If the pointer x is also stored elsewhere such as inside a heap structure
there is no issue with incrementing a copy of it - so most of the time you
don't need to worry, but occasionally you may need to adjust algorithms which
do significant pointer arithmetic. For example, in this case the pointer can be
left as-is and an integer used to index it instead:
void good_function(char *y) {
int i;
char *x = tgc_alloc(&gc, strlen(y) + 1);
strcpy(x, y);
for (i = 0; i < strlen(x); i++) {
do_some_processsing(&x[i]);
}
}For now this is the behaviour of tgc until I think of a way to
deal with offset pointers nicely.
Variables are only considered reachable if they are one function call shallower
than the call to tgc_start. If optimisations are enabled somtimes the
compiler will inline functions which removes this one level of indirection.
The most portable way to get compilers not to inline functions is to call them
through volatile function pointers.
static tgc_t gc;
void please_dont_inline(void) {
...
}
int main(int argc, char **argv) {
tgc_start(&gc, &argc);
void (*volatile func)(void) = please_dont_inline;
func();
tgc_stop(&gc);
return 1;
}Unfortunately tgc doesn't work properly with setjmp and longjmp since
these functions can cause complex stack behaviour. One simple option is to
disable the garbage collector while using these functions and to re-enable
it afterwards.
The garbage collector scans the stack memory and this naturally contains
uninitialised values. It scans memory safely, but if you are running through
Valgrind these accesses will be reported as warnings/errors. Other than this
tgc shouldn't have any memory errors in Valgrind, so the easiest way to
disable these to examine any real problems is to run Valgrind with the option
--undef-value-errors=no.
At the moment tgc has decent performance - it is competative with many
existing memory management systems - but definitely can't claim to be the
fastest garbage collector on the market. Saying that, there is a fair amount of
low hanging fruit for anyone interested in optimising it - so some potential to
be faster exists.
For a basic mark and sweep garbage collector two things are required. The first thing is a list of all of the allocations made by the program. The second is a list of all the allocations in use by the program at any given time. With these two things the algorithm is simple - compare the two lists and free any allocations which are in the first list, but not in the second - exactly those allocations which are no longer in use.
To get a list of all the allocations made by the progam is relatively
simple. We make the programmer use a special function we've prepared (in this
case tgc_alloc) which allocates memory, and then adds a pointer to that
memory to an internal list. If at any point this allocation is freed (such as
by tgc_free), it is removed from the list.
The second list is the difficult one - the list of allocations in use by the program. At first, with C's semantics, pointer arithematic, and all the crazy flexibility that comes with it, it might seem like finding all the allocations in use by the program at any point in time is impossible, and to some extent you'd be right. It can actually be shown that this problem reduces to the halting problem in the most general case - even for languages saner than C - but by slightly adjusting our problem statement, and assuming we are only dealing with a set of well behaved C programs of some form, we can come up with something that works.
First we have to relax our goal a little. Instead of trying to find all of
the memory allocations in use by a program, we can instead try to find all
the reachable memory allocations - those allocations which have a pointer
pointing to them somewhere in the program's memory. The distinction here is
subtle but important. For example, I could write a C program which makes an
allocation, encodes the returned pointer as a string, and performs rot13 on
that string, later on decoding the string, casting it back to a pointer,
and using the memory as if nothing had happened. This is a perfectly valid, C
program, and the crazy memory allocation is is use throughout. It is just
that during the pointer's rot13 encoding there is no practical way to know
that this memory allocation is still going to be used later on.
So instead we want to make a list of all memory allocations which are pointed to by pointers in the program's memory. For most well behaved C programs this is enough to tell if an allocation is in use.
In general, memory in C exists in three different segments. We have the stack, the heap, and the data segment. This means - if a pointer to a certain allocation exists in the program's memory it must be in one of these locations. Now the challenge is to find these locations, and scan them for pointers.
The data segment is the most difficult - there is no portable way to get the bounds of this segment. But because the data segment is somewhat limited in use we can choose to ignore it - we tell users that allocations only pointed to from the data segment are not considered reachable.
As an aside, for programmers coming from other languages, this might seem like a poor solution - to simply ask the programmer not to store pointers to allocations in this segment - and in many ways it is. It is never a good interface to request the programmer do something in the documentation - instead it is better to handle every edge case to make it impossible for them to create an error. But this is C - in C programmers are constantly asked not to do things which are perfectly possible. In fact - one of the very things this library is trying to deal with is the fact that programmers are only asked to make sure they free dynamically allocated memory - there is no system in place to enforce this. So for C this is a perfectly reasonable interface. And there is an added advantage - it makes the implementation far more simple - far more adaptable. In other words - Worse Is Better.
With the data segment covered we have the heap and the stack. If we consider
only the heap allocations which have been made via tgc_alloc and friends then
our job is again made easy - in our list of all allocations we also store the
size of each allocation. Then, if we need to scan one of the memory regions
we've allocated, the task is made easy.
With the heap and the data segment covered, this leaves us with the stack - this is the most tricky segment. The stack is something we don't have any control over, but we do know that for most reasonable implementations of C, the stack is a continuous area of memory that is expanded downwards (or for some implementations upwards, but it doesn't matter) for each function call. It contains the most important memory in regards to reachability - all of the local variables used in functions.
If we can get the memory addresses of the top and the bottom of the stack we can scan the memory inbetween as if it were heap memory, and add to our list of reachable pointers all those found inbetween.
Assuming the stack grows from top to bottom we can get a conservative approximation of the bottom of the stack by just taking the address of some local variable.
void *stack_bottom(void) {
int x;
return &x;
}This address should cover the memory of all the local variables for whichever
function calls it. For this reason we need to ensure two things before we
actually do call it. First we want to make sure we flush all of the values in
the registers onto the stack so that we don't miss a pointer hiding in a
register, and secondly we want to make sure the call to stack_bottom isn't
inlined by the compiler.
We can spill the registers into stack memory in a somewhat portable way with
setjmp - which puts the registers into a jmp_buf variable. And we can
ensure that the function is not inlined by only calling it via a volatile
function pointer. The volatile keyword forces the compiler to always manually
read the pointer value from memory before calling the function, ensuring it
cannot be inlined.
void *get_stack_bottom(void) {
jmt_buf env;
setjmp(env);
void *(*volatile f)(void) = stack_bottom;
return f();
}To get the top of the stack we can again get the address of a local variable.
This time it is easier if we simply ask the programmer to supply us with one.
If the programmer wishes for the garbage collector to scan the whole stack he
can give the address of a local variable in main. This address should cover
all function calls one deeper than main. This we can store in some global
(or local) variable.
static void *stack_top = NULL;
int main(int argc, char **argv) {
stack_top = &argc;
run_program(argc, argv);
return 1;
}Now, at any point we can get a safe approximate upper and lower bound of the
stack memory, allowing us to scan it for pointers. We interprit each bound as a
void ** - a pointer to an array of pointers, and iterate, interpriting the
memory inbetween as pointers.
void mark(void) {
void **p;
void **t = stack_top;
void **b = get_stack_bottom();
for (p = t; p < b; p++) {
scan(*p);
}
}